Golang interfaces and pointers

I can’t write this article fully right now, but here’s a quick lesson I learned.

In one of my projects, I had multiple types of binary trees: prefix trees (i.e. tries) and binary search trees (BSTs). My tree types (i.e. PrefixTree, BinarySearchTree) each had a different node type (i.e. PrefixNode, BstNode) because a PrefixTree stored a different kind of data than a BinarySearchTree. Also the prefix tree was using path-copying to save some space.

I was trying to write a generic method Hash(root *Node) that computed a Merkle hash of a prefix tree or a binary search tree. However, since their node types differed, I needed to define a Go interface and have Hash operate on the interface.

Long story short, if you ever need to define an interface type like Node for a binary tree’s node, don’t do this:

Bad node.go:

package authtree

import "xcrypto"

const (
    NODE_TYPE_INTERNAL = byte(0x1)
    NODE_TYPE_LEAF = byte(0x2)
    NODE_TYPE_EMPTY = byte(0x3)
)

type Node interface {
    GetLeftChild() *Node
    GetRightChild() *Node
    IsLeaf() bool

    GetInternalNodeData() []byte    // In BSTs, internal nodes have data. In prefix trees, data is only in the leaf
    GetLeafData() []byte    // In BSTs and prefix trees, leafs have data

    Resolve() *Node // In path-copying trees, some nodes are references to other nodes and need to be resolved

    GetHash() []byte    // returns the hash of the node, or nil if not set
    SetHash([]byte)     // sets the hash of the node to the specified one
}

// Recursively computes the hash of the node. Uses 'emptyHash' as the hash of
// the subtrees that are empty. Follows reference nodes as well.
func Hash2(root *Node, emptyHash []byte) []byte {
    root = root.Resolve()   // follow path-copying references

    var nodeData []byte = make([]byte, 0)

    if root.IsLeaf() {
        data := root.GetLeafData()
        nodeData = append(nodeData, NODE_TYPE_LEAF)
        nodeData = append(nodeData, data...)
    } else {
        var leftHash, rightHash []byte

        if root.GetLeftChild() != nil {
            leftHash = Hash2(root.GetLeftChild(), emptyHash)
        } else {
            leftHash = emptyHash
        }

        if root.GetRightChild() != nil {
            rightHash = Hash2(root.GetRightChild(), emptyHash)
        } else {
            rightHash = emptyHash
        }

        nodeData = append(nodeData, NODE_TYPE_INTERNAL)
        nodeData = append(nodeData, leftHash...)
        nodeData = append(nodeData, rightHash...)
    }

    root.SetHash(xcrypto.Hash(nodeData))

    return root.GetHash()
}

The errors when you try to build the Hash2 method:

$ go build authtree/
# authtree
authtree/node1.go:28: root.Resolve undefined (type *Node has no field or method Resolve)
authtree/node1.go:32: root.IsLeaf undefined (type *Node has no field or method IsLeaf)
authtree/node1.go:33: root.GetLeafData undefined (type *Node has no field or method GetLeafData)
authtree/node1.go:39: root.GetLeftChild undefined (type *Node has no field or method GetLeftChild)
authtree/node1.go:40: root.GetLeftChild undefined (type *Node has no field or method GetLeftChild)
authtree/node1.go:45: root.GetRightChild undefined (type *Node has no field or method GetRightChild)
authtree/node1.go:46: root.GetRightChild undefined (type *Node has no field or method GetRightChild)
authtree/node1.go:56: root.SetHash undefined (type *Node has no field or method SetHash)
authtree/node1.go:58: root.GetHash undefined (type *Node has no field or method GetHash)

The reason this did not work is because my PrefixNode and BinarySearchNode types used pointer receivers for their methods. However, Go does not let you implement the Node interface type using pointer receivers. For instance, this won’t “count” as an implementation for Node::GetLeftChild:

func (node *BstNode) GetLeftChild() *BstNode {
    return node.LeftChild
}

At first, this was very confusing. Why would Go not let me implement the interface using pointer receivers? While I am sure there’s an answer to this question, here’s how to get around it:

Good node.go:

package authtree

import "xcrypto"

const (
    NODEPTR_TYPE_INTERNAL = byte(0x1)
    NODEPTR_TYPE_LEAF = byte(0x2)
    NODEPTR_TYPE_EMPTY = byte(0x3)
)

type NodePtr interface {
    GetLeftChild() NodePtr
    GetRightChild() NodePtr
    IsLeaf() bool

    GetInternalNodeData() []byte    // In BSTs, internal nodes have data. In prefix trees, data is only in the leaf
    GetLeafData() []byte    // In BSTs and prefix trees, leafs have data

    Resolve() NodePtr // In path-copying trees, some nodes are references to other nodes and need to be resolved

    GetHash() []byte    // returns the hash of the node, or nil if not set
    SetHash([]byte)     // sets the hash of the node to the specified one
}

// Recursively computes the hash of the node. Uses 'emptyHash' as the hash of
// the subtrees that are empty. Follows reference nodes as well.
func Hash(root NodePtr, emptyHash []byte) []byte {
    root = root.Resolve()   // follow path-copying references

    var nodeData []byte = make([]byte, 0)

    if root.IsLeaf() {
        data := root.GetLeafData()
        nodeData = append(nodeData, NODE_TYPE_LEAF)
        nodeData = append(nodeData, data...)
    } else {
        var leftHash, rightHash []byte

        if root.GetLeftChild() != nil {
            leftHash = Hash(root.GetLeftChild(), emptyHash)
        } else {
            leftHash = emptyHash
        }

        if root.GetRightChild() != nil {
            rightHash = Hash(root.GetRightChild(), emptyHash)
        } else {
            rightHash = emptyHash
        }

        nodeData = append(nodeData, NODE_TYPE_INTERNAL)
        nodeData = append(nodeData, leftHash...)
        nodeData = append(nodeData, rightHash...)
    }

    root.SetHash(xcrypto.Hash(nodeData))

    return root.GetHash()
}

Now, my *PrefixNode and *BstNode pointer types implement the NodePtr interface! Problem solved!

Written on August 17, 2015