Graphviz

最近看了许多比较酷炫的数据结构的实现，例如 Trie ， Skip List ，B-Tree 等，看代码的时候经常会想，要是有什么工具可以帮助我们将内存中的结构体绘制出来就好了，搜了一下 github ，发现早已经有大佬帮我们实现过了。

下面以二叉搜索树为例，来看一下如何使用 graphviz 绘制内存中的结构体。二叉树的定义非常简单，每个节点都有一个左节点和右节点，用于指向自己的左子树和右子树。

type Node struct {
    val   int
    left  *Node
    right *Node
}

func (n *Node) Insert(val int) error {
    if n == nil {
        return errors.New("Cannot insert a value into a nil tree")
    }
    switch {
    case val == n.val:
        return nil
    case val < n.val:
        if n.left == nil {
            n.left = &Node{val: val}
            return nil
        }
        return n.left.Insert(val)
    case val > n.val:
        if n.right == nil {
            n.right = &Node{val: val}
            return nil
        }
        return n.right.Insert(val)
    }
    return nil
}

type Tree struct {
    Root  *Node
}

func (t *Tree) Insert(val int) error {
    if t.root == nil {
        t.Root = &Node{val: val}
        return nil
    }
    return t.Root.Insert(value)
}

在 main 函数中我们构造一个二叉树，并向该树中随意插入一些值，最后我们使用 memviz.Map(os.Stdout, &tree) 将该树对应的 DOT 形态输出到标准输出中。

import "github.com/bradleyjkemp/memviz"

func main() {
    tree := &Tree{}
    values := []int{4, 2, 6, 1, 3, 5, 7}
    for i := 0; i < len(values); i++ {
        err := tree.Insert(values[i])
        if err != nil {
            log.Fatal("Error inserting value '", values[i], "': ", err)
        }
    }
    memviz.Map(os.Stdout, &tree)
}

利用 unix pipe 将 go run main.go 得到的结果输入到 dot 命令中。

$ go run main.go | dot -Tpng -o output.png | open output.png

dot 命令相当于 graphviz 的一个子命令，它专门用于绘制有向图，除了 dot 之外，还有 neato ，twopi ，circo ，fdp ，sfdp ，patchword 和osage ，它们的用法与 dot 完全一致，只是它们的用处稍稍不同，例如 neato 比较适合用来绘制无向图。

下面我们来看一下（ memviz.Map(os.Stdout, &tree) ）的实现，该函数的实现主要依靠 golang 中的反射机制（ reflect ），利用 reflect 可以在运行时审查元素的类型，然后根据其类型，构造符合 dot 的语法的模版就行了。

func Map(w io.Writer, is ...interface{}) {
    var iVals []reflect.Value
    for _, i := range is {
        iVal := reflect.ValueOf(i)
        if !iVal.CanAddr() {
            if iVal.Kind() != reflect.Ptr && iVal.Kind() != reflect.Interface {
                fmt.Fprint(w, "error: cannot map unaddressable value")
                return
             }
             iVal = iVal.Elem()
        }
        iVals = append(iVals, iVal)
    }

    m := &mapper{
        w,
        map[nodeKey]nodeID{nilKey: 0},
        map[nodeKey]string{nilKey: "nil"},
        2,
    }

    fmt.Fprintln(w, "digraph structs {")
    fmt.Fprintln(w, "  node [shape=Mrecord];")
    for _, iVal := range iVals {
        m.mapValue(iVal, 0, false)
    }
    fmt.Fprintln(w, "}")
}