3 files changed, 212 insertions, 0 deletions
diff --git a/utils/merkletrie/noder/noder.go b/utils/merkletrie/noder/noder.go
new file mode 100644
index 0000000..d6b3de4
--- /dev/null
+++ b/utils/merkletrie/noder/noder.go
@@ -0,0 +1,59 @@
+// Package noder provide an interface for defining nodes in a
+// merkletrie, their hashes and their paths (a noders and its
+// ancestors).
+//
+// The hasher interface is easy to implement naively by elements that
+// already have a hash, like git blobs and trees.  More sophisticated
+// implementations can implement the Equal function in exotic ways
+// though: for instance, comparing the modification time of directories
+// in a filesystem.
+package noder
+
+import "fmt"
+
+// Hasher interface is implemented by types that can tell you
+// their hash.
+type Hasher interface {
+	Hash() []byte
+}
+
+// Equal functions take two hashers and return if they are equal.
+//
+// These functions are expected to be faster than reflect.Equal or
+// reflect.DeepEqual because they can compare just the hash of the
+// objects, instead of their contents, so they are expected to be O(1).
+type Equal func(a, b Hasher) bool
+
+// The Noder interface is implemented by the elements of a Merkle Trie.
+//
+// There are two types of elements in a Merkle Trie:
+//
+// - file-like nodes: they cannot have children.
+//
+// - directory-like nodes: they can have 0 or more children and their
+// hash is calculated by combining their children hashes.
+type Noder interface {
+	Hasher
+	fmt.Stringer // for testing purposes
+	// Name returns the name of an element (relative, not its full
+	// path).
+	Name() string
+	// IsDir returns true if the element is a directory-like node or
+	// false if it is a file-like node.
+	IsDir() bool
+	// Children returns the children of the element.  Note that empty
+	// directory-like noders and file-like noders will both return
+	// NoChildren.
+	Children() ([]Noder, error)
+	// NumChildren returns the number of children this element has.
+	//
+	// This method is an optimization: the number of children is easily
+	// calculated as the length of the value returned by the Children
+	// method (above); yet, some implementations will be able to
+	// implement NumChildren in O(1) while Children is usually more
+	// complex.
+	NumChildren() (int, error)
+}
+
+// NoChildren represents the children of a noder without children.
+var NoChildren = []Noder{}
diff --git a/utils/merkletrie/noder/noder_test.go b/utils/merkletrie/noder/noder_test.go
new file mode 100644
index 0000000..14bef4a
--- /dev/null
+++ b/utils/merkletrie/noder/noder_test.go
@@ -0,0 +1,94 @@
+package noder
+
+import . "gopkg.in/check.v1"
+
+type NoderSuite struct{}
+
+var _ = Suite(&NoderSuite{})
+
+type noderMock struct {
+	name     string
+	hash     []byte
+	isDir    bool
+	children []Noder
+}
+
+func (n noderMock) String() string             { return n.Name() }
+func (n noderMock) Hash() []byte               { return n.hash }
+func (n noderMock) Name() string               { return n.name }
+func (n noderMock) IsDir() bool                { return n.isDir }
+func (n noderMock) Children() ([]Noder, error) { return n.children, nil }
+func (n noderMock) NumChildren() (int, error)  { return len(n.children), nil }
+
+// Returns a sequence with the noders 3, 2, and 1 from the
+// following diagram:
+//
+//   3
+//   |
+//   2
+//   |
+//   1
+//  / \
+// c1  c2
+//
+// This is also the path of "1".
+func nodersFixture() []Noder {
+	n1 := &noderMock{
+		name:     "1",
+		hash:     []byte{0x00, 0x01, 0x02},
+		isDir:    true,
+		children: childrenFixture(),
+	}
+	n2 := &noderMock{name: "2"}
+	n3 := &noderMock{name: "3"}
+	return []Noder{n3, n2, n1}
+}
+
+// Returns a collection of 2 noders: c1, c2.
+func childrenFixture() []Noder {
+	c1 := &noderMock{name: "c1"}
+	c2 := &noderMock{name: "c2"}
+	return []Noder{c1, c2}
+}
+
+// Returns the same as nodersFixture but sorted by name, this is: "1",
+// "2" and then "3".
+func sortedNodersFixture() []Noder {
+	n1 := &noderMock{
+		name:     "1",
+		hash:     []byte{0x00, 0x01, 0x02},
+		isDir:    true,
+		children: childrenFixture(),
+	}
+	n2 := &noderMock{name: "2"}
+	n3 := &noderMock{name: "3"}
+	return []Noder{n1, n2, n3} // the same as nodersFixture but sorted by name
+}
+
+// returns nodersFixture as the path of "1".
+func pathFixture() Path {
+	return Path(nodersFixture())
+}
+
+func (s *NoderSuite) TestString(c *C) {
+	c.Assert(pathFixture().String(), Equals, "3/2/1")
+}
+
+func (s *NoderSuite) TestLast(c *C) {
+	c.Assert(pathFixture().Last().Name(), Equals, "1")
+}
+
+func (s *NoderSuite) TestPathImplementsNoder(c *C) {
+	p := pathFixture()
+	c.Assert(p.Name(), Equals, "1")
+	c.Assert(p.Hash(), DeepEquals, []byte{0x00, 0x01, 0x02})
+	c.Assert(p.IsDir(), Equals, true)
+
+	children, err := p.Children()
+	c.Assert(err, IsNil)
+	c.Assert(children, DeepEquals, childrenFixture())
+
+	numChildren, err := p.NumChildren()
+	c.Assert(err, IsNil)
+	c.Assert(numChildren, Equals, 2)
+}
diff --git a/utils/merkletrie/noder/path.go b/utils/merkletrie/noder/path.go
new file mode 100644
index 0000000..c992f7e
--- /dev/null
+++ b/utils/merkletrie/noder/path.go
@@ -0,0 +1,59 @@
+package noder
+
+import "bytes"
+
+// Path values represent a noder and its ancestors.  The root goes first
+// and the actual final noder the path is refering to will be the last.
+//
+// A path implements the Noder interface, redirecting all the interface
+// calls to its final noder.
+//
+// Paths build from an empty Noder slice are not valid paths and should
+// not be used.
+type Path []Noder
+
+// String returns the full path of the final noder as a string, using
+// "/" as the separator.
+func (p Path) String() string {
+	var buf bytes.Buffer
+	sep := ""
+	for _, e := range p {
+		_, _ = buf.WriteString(sep)
+		sep = "/"
+		_, _ = buf.WriteString(e.Name())
+	}
+
+	return buf.String()
+}
+
+// Last returns the final noder in the path.
+func (p Path) Last() Noder {
+	return p[len(p)-1]
+}
+
+// Hash returns the hash of the final noder of the path.
+func (p Path) Hash() []byte {
+	return p.Last().Hash()
+}
+
+// Name returns the name of the final noder of the path.
+func (p Path) Name() string {
+	return p.Last().Name()
+}
+
+// IsDir returns if the final noder of the path is a directory-like
+// noder.
+func (p Path) IsDir() bool {
+	return p.Last().IsDir()
+}
+
+// Children returns the children of the final noder in the path.
+func (p Path) Children() ([]Noder, error) {
+	return p.Last().Children()
+}
+
+// NumChildren returns the number of children the final noder of the
+// path has.
+func (p Path) NumChildren() (int, error) {
+	return p.Last().NumChildren()
+}