aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie/noder
diff options
context:
space:
mode:
Diffstat (limited to 'utils/merkletrie/noder')
-rw-r--r--utils/merkletrie/noder/noder.go59
-rw-r--r--utils/merkletrie/noder/noder_test.go94
-rw-r--r--utils/merkletrie/noder/path.go59
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()
+}