aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/difftree/internal/merkletrie
diff options
context:
space:
mode:
Diffstat (limited to 'plumbing/difftree/internal/merkletrie')
-rw-r--r--plumbing/difftree/internal/merkletrie/doc.go30
-rw-r--r--plumbing/difftree/internal/merkletrie/frame.go79
-rw-r--r--plumbing/difftree/internal/merkletrie/frame_test.go69
-rw-r--r--plumbing/difftree/internal/merkletrie/iter.go167
-rw-r--r--plumbing/difftree/internal/merkletrie/iter_fixtures_test.go330
-rw-r--r--plumbing/difftree/internal/merkletrie/iter_test.go176
-rw-r--r--plumbing/difftree/internal/merkletrie/node.go65
-rw-r--r--plumbing/difftree/internal/merkletrie/node_test.go68
-rw-r--r--plumbing/difftree/internal/merkletrie/noder.go20
9 files changed, 1004 insertions, 0 deletions
diff --git a/plumbing/difftree/internal/merkletrie/doc.go b/plumbing/difftree/internal/merkletrie/doc.go
new file mode 100644
index 0000000..f8c3b2f
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/doc.go
@@ -0,0 +1,30 @@
+package merkletrie
+
+/*
+Package merkletrie gives support for n-ary trees that are at the same
+time Merkle trees and Radix trees, and provides an efficient tree
+comparison algorithm for them.
+
+Git trees are Radix n-ary trees in virtue of the names of their
+tree entries. At the same time, git trees are Merkle trees thanks to
+their hashes.
+
+When comparing git trees, the simple approach of alphabetically sorting
+their elements and comparing the resulting lists is not enough as it
+depends linearly on the number of files in the trees: When a directory
+has lots of files but none of them has been modified, this approach is
+very expensive. We can do better by prunning whole directories that
+have not change, by just by looking at their hashes. This package
+provides the tools to do exactly that.
+
+This package defines Radix-Merkle trees as nodes that should have:
+- a hash: the Merkle part of the Radix-Merkle tree
+- a key: the Radix part of the Radix-Merkle tree
+
+The Merkle hash condition is not enforced by this package though. This
+means that node hashes doesn't have to take into account the hashes of
+their children, which is good for testing purposes.
+
+Nodes in the Radix-Merkle tree are abstracted by the Noder interface.
+The intended use is that git.Tree implements this interface.
+*/
diff --git a/plumbing/difftree/internal/merkletrie/frame.go b/plumbing/difftree/internal/merkletrie/frame.go
new file mode 100644
index 0000000..a40c6ad
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/frame.go
@@ -0,0 +1,79 @@
+package merkletrie
+
+import (
+ "bytes"
+ "fmt"
+)
+
+const sep = "/"
+
+// A frame represents siblings in a trie, along with the path to get to
+// them. For example the frame for the node with key `b` in this trie:
+//
+// a
+// / \
+// / \
+// / \
+// b c
+// /|\ / \
+// y z x d e
+// |
+// g
+//
+// would be:
+//
+// f := frame{
+// base: "a/b", // path to the siblings
+// stack: []Node{z, y, x} // in reverse alphabetical order
+// }
+type frame struct {
+ base string // absolute key of their parents
+ stack []Noder // siblings, sorted in reverse alphabetical order by key
+}
+
+// newFrame returns a frame for the children of a node n.
+func newFrame(parentAbsoluteKey string, n Noder) *frame {
+ return &frame{
+ base: parentAbsoluteKey + sep + n.Key(),
+ stack: n.Children(),
+ }
+}
+
+func (f *frame) String() string {
+ var buf bytes.Buffer
+ _, _ = buf.WriteString(fmt.Sprintf("base=%q, stack=[", f.base))
+
+ sep := ""
+ for _, e := range f.stack {
+ _, _ = buf.WriteString(sep)
+ sep = ", "
+ _, _ = buf.WriteString(fmt.Sprintf("%q", e.Key()))
+ }
+
+ _ = buf.WriteByte(']')
+
+ return buf.String()
+}
+
+func (f *frame) top() (Noder, bool) {
+ if len(f.stack) == 0 {
+ return nil, false
+ }
+
+ top := len(f.stack) - 1
+
+ return f.stack[top], true
+}
+
+func (f *frame) pop() (Noder, bool) {
+ if len(f.stack) == 0 {
+ return nil, false
+ }
+
+ top := len(f.stack) - 1
+ ret := f.stack[top]
+ f.stack[top] = nil
+ f.stack = f.stack[:top]
+
+ return ret, true
+}
diff --git a/plumbing/difftree/internal/merkletrie/frame_test.go b/plumbing/difftree/internal/merkletrie/frame_test.go
new file mode 100644
index 0000000..0ef036a
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/frame_test.go
@@ -0,0 +1,69 @@
+package merkletrie
+
+import . "gopkg.in/check.v1"
+
+type FrameSuite struct{}
+
+var _ = Suite(&FrameSuite{})
+
+func (s *FrameSuite) TestNewFrameFromLeaf(c *C) {
+ n := newNode(
+ []byte("hash"),
+ "key",
+ []*node{},
+ )
+
+ frame := newFrame("foo", n)
+
+ expectedString := `base="foo/key", stack=[]`
+ c.Assert(frame.String(), Equals, expectedString)
+
+ obtainedTopNode, obtainedTopOK := frame.top()
+ c.Assert(obtainedTopNode, IsNil)
+ c.Assert(obtainedTopOK, Equals, false)
+
+ obtainedPopNode, obtainedPopOK := frame.top()
+ c.Assert(obtainedPopNode, IsNil)
+ c.Assert(obtainedPopOK, Equals, false)
+}
+
+func (s *FrameSuite) TestNewFrameFromParent(c *C) {
+ leaf0 := newNode([]byte("leaf0 hash"), "leaf0 key", []*node{})
+ leaf1 := newNode([]byte("leaf1 hash"), "leaf1 key", []*node{})
+ leaf2 := newNode([]byte("leaf2 hash"), "leaf2 key", []*node{})
+ leaf3 := newNode([]byte("leaf3 hash"), "leaf3 key", []*node{})
+ parent := newNode(
+ []byte("parent hash"),
+ "parent key",
+ []*node{leaf3, leaf0, leaf2, leaf1}, // not alphabetically sorted
+ )
+
+ frame := newFrame("foo", parent)
+
+ expectedString := `base="foo/parent key", stack=["leaf3 key", "leaf2 key", "leaf1 key", "leaf0 key"]`
+ c.Assert(frame.String(), Equals, expectedString)
+
+ checkTopAndPop(c, frame, leaf0, true)
+ checkTopAndPop(c, frame, leaf1, true)
+ checkTopAndPop(c, frame, leaf2, true)
+ checkTopAndPop(c, frame, leaf3, true)
+ checkTopAndPop(c, frame, nil, false)
+}
+
+func checkTopAndPop(c *C, f *frame, expectedNode *node, expectedOK bool) {
+ n, ok := f.top()
+ if expectedNode == nil {
+ c.Assert(n, IsNil)
+ } else {
+ c.Assert(n, DeepEquals, expectedNode)
+ }
+ c.Assert(ok, Equals, expectedOK)
+
+ n, ok = f.pop()
+ if expectedNode == nil {
+ c.Assert(n, IsNil)
+ } else {
+ c.Assert(n, DeepEquals, expectedNode)
+ }
+ c.Assert(ok, Equals, expectedOK)
+}
diff --git a/plumbing/difftree/internal/merkletrie/iter.go b/plumbing/difftree/internal/merkletrie/iter.go
new file mode 100644
index 0000000..e175966
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/iter.go
@@ -0,0 +1,167 @@
+package merkletrie
+
+// Iter is a radix tree iterator that will traverse the trie in
+// depth-first pre-order. Entries are traversed in (case-sensitive)
+// alphabetical order for each level.
+//
+// This is the kind of traversal you will expect when listing
+// ordinary files and directories recursively, for example:
+//
+// Trie Traversal order
+// ---- ---------------
+// .
+// / | \ a
+// / | \ b
+// b a z ===> b/a
+// / \ b/c
+// c a z
+//
+//
+// The Step method will return the next item, the Next method will do
+// the same but without descending deeper into the tree (i.e. skipping
+// the contents of "directories").
+//
+// The name of the type and its methods are based on the well known "next"
+// and "step" operations, quite common in debuggers, like gdb.
+type Iter struct {
+ // tells if the iteration has started.
+ hasStarted bool
+ // Each level of the tree is represented as a frame, this stack
+ // keeps track of the frames wrapping the current iterator position.
+ // The iterator will "step" into a node by adding its frame to the
+ // stack, or go to the next element at the same level by poping the
+ // current frame.
+ frameStack []*frame
+}
+
+// NewIter returns a new iterator for the trie with its root at n.
+func NewIter(n Noder) *Iter {
+ ret := &Iter{}
+ ret.push(newFrame("", n))
+
+ return ret
+}
+
+func (iter *Iter) top() (*frame, bool) {
+ if len(iter.frameStack) == 0 {
+ return nil, false
+ }
+
+ top := len(iter.frameStack) - 1
+
+ return iter.frameStack[top], true
+}
+
+func (iter *Iter) pop() (*frame, bool) {
+ if len(iter.frameStack) == 0 {
+ return nil, false
+ }
+
+ top := len(iter.frameStack) - 1
+ ret := iter.frameStack[top]
+ iter.frameStack[top] = nil
+ iter.frameStack = iter.frameStack[:top]
+
+ return ret, true
+}
+
+func (iter *Iter) push(f *frame) {
+ iter.frameStack = append(iter.frameStack, f)
+}
+
+const (
+ descend = true
+ dontDescend = false
+)
+
+// Next returns the next node without descending deeper into the tree
+// and true. If there are no more entries it returns nil and false.
+func (iter *Iter) Next() (Noder, bool) {
+ return iter.advance(dontDescend)
+}
+
+// Step returns the next node in the tree, descending deeper into it if
+// needed. If there are no more nodes in the tree, it returns nil and
+// false.
+func (iter *Iter) Step() (Noder, bool) {
+ return iter.advance(descend)
+}
+
+// advances the iterator in whatever direction you want: descend or
+// dontDescend.
+func (iter *Iter) advance(mustDescend bool) (Noder, bool) {
+ node, ok := iter.current()
+ if !ok {
+ return nil, false
+ }
+
+ // The first time we just return the current node.
+ if !iter.hasStarted {
+ iter.hasStarted = true
+ return node, ok
+ }
+ // following advances will involve dropping already seen nodes
+ // or getting into their children
+
+ ignoreChildren := node.NumChildren() == 0 || !mustDescend
+ if ignoreChildren {
+ // if we must ignore the current node children, just drop
+ // it and find the next one in the existing frames.
+ _ = iter.drop()
+ node, ok = iter.current()
+ return node, ok
+ }
+
+ // if we must descend into the current's node children, drop the
+ // parent and add a new frame with its children.
+ _ = iter.drop()
+ iter.push(newFrame(node.Key(), node))
+ node, _ = iter.current()
+
+ return node, true
+}
+
+// returns the current frame and the current node (i.e. the ones at the
+// top of their respective stacks.
+func (iter *Iter) current() (Noder, bool) {
+ f, ok := iter.top()
+ if !ok {
+ return nil, false
+ }
+
+ n, ok := f.top()
+ if !ok {
+ return nil, false
+ }
+
+ return n, true
+}
+
+// removes the current node and all the frames that become empty as a
+// consecuence of this action. It returns true if something was dropped,
+// and false if there were no more nodes in the iterator.
+func (iter *Iter) drop() bool {
+ frame, ok := iter.top()
+ if !ok {
+ return false
+ }
+
+ _, ok = frame.pop()
+ if !ok {
+ return false
+ }
+
+ for { // remove empty frames
+ if len(frame.stack) != 0 {
+ break
+ }
+
+ _, _ = iter.pop()
+ frame, ok = iter.top()
+ if !ok {
+ break
+ }
+ }
+
+ return true
+}
diff --git a/plumbing/difftree/internal/merkletrie/iter_fixtures_test.go b/plumbing/difftree/internal/merkletrie/iter_fixtures_test.go
new file mode 100644
index 0000000..20bddaf
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/iter_fixtures_test.go
@@ -0,0 +1,330 @@
+package merkletrie
+
+// this files contains fixtures for testing the Iter.
+//
+// - iter... functions returns iterators for newly created trees
+// for example:
+//
+// + iterLeaf returns an iterator for simple tree with just the root.
+//
+// + iter2Horizontal returns an iterator for a tree with 2 nodes, both
+// childs of the root.
+//
+// - runs... contains sets of tests, indexed by a string that helps
+// to understand each test: "nsn" means next, then step, then next
+// again. The test also contains the expected keys of the nodes you
+// will get when calling the operations over the correspoding trees:
+// Example: runs2HorizontalSorted with iter2HorizontalSorted and so on.
+
+func iterLeaf() *Iter {
+ root := newNode(hash, "root", empty)
+ return NewIter(root)
+}
+
+var runs0 = map[string][]test{
+ "nn": {{next, ""}, {next, ""}},
+ "ns": {{next, ""}, {step, ""}},
+ "sn": {{step, ""}, {next, ""}},
+ "ss": {{step, ""}, {step, ""}},
+}
+
+// root
+// |
+// a
+func iter1() *Iter {
+ a := newNode(hash, "a", empty)
+ root := newNode(hash, "root", []*node{a})
+ return NewIter(root)
+}
+
+var runs1 = map[string][]test{
+ "nn": {{next, "a"}, {next, ""}},
+ "ns": {{next, "a"}, {step, ""}},
+ "sn": {{step, "a"}, {next, ""}},
+ "ss": {{step, "a"}, {step, ""}},
+}
+
+// root
+// / \
+// a b
+func iter2HorizontalSorted() *Iter {
+ a := newNode(hash, "a", empty)
+ b := newNode(hash, "b", empty)
+ root := newNode(hash, "root", []*node{a, b})
+ return NewIter(root)
+}
+
+// root
+// / \
+// b a
+func iter2HorizontalReverse() *Iter {
+ a := newNode(hash, "a", empty)
+ b := newNode(hash, "b", empty)
+ root := newNode(hash, "root", []*node{b, a})
+ return NewIter(root)
+}
+
+var runs2Horizontal = map[string][]test{
+ "nnn": {{next, "a"}, {next, "b"}, {next, ""}},
+ "nns": {{next, "a"}, {next, "b"}, {step, ""}},
+ "nsn": {{next, "a"}, {step, "b"}, {next, ""}},
+ "nss": {{next, "a"}, {step, "b"}, {step, ""}},
+ "snn": {{step, "a"}, {next, "b"}, {next, ""}},
+ "sns": {{step, "a"}, {next, "b"}, {step, ""}},
+ "ssn": {{step, "a"}, {step, "b"}, {next, ""}},
+ "sss": {{step, "a"}, {step, "b"}, {step, ""}},
+}
+
+// root
+// |
+// a
+// |
+// b
+func iter2VerticalSorted() *Iter {
+ b := newNode(hash, "b", empty)
+ a := newNode(hash, "a", []*node{b})
+ root := newNode(hash, "root", []*node{a})
+ return NewIter(root)
+}
+
+var runs2VerticalSorted = map[string][]test{
+ "nnn": {{next, "a"}, {next, ""}, {next, ""}},
+ "nns": {{next, "a"}, {next, ""}, {step, ""}},
+ "nsn": {{next, "a"}, {step, "b"}, {next, ""}},
+ "nss": {{next, "a"}, {step, "b"}, {step, ""}},
+ "snn": {{step, "a"}, {next, ""}, {next, ""}},
+ "sns": {{step, "a"}, {next, ""}, {step, ""}},
+ "ssn": {{step, "a"}, {step, "b"}, {next, ""}},
+ "sss": {{step, "a"}, {step, "b"}, {step, ""}},
+}
+
+// root
+// |
+// b
+// |
+// a
+func iter2VerticalReverse() *Iter {
+ a := newNode(hash, "a", empty)
+ b := newNode(hash, "b", []*node{a})
+ root := newNode(hash, "root", []*node{b})
+ return NewIter(root)
+}
+
+var runs2VerticalReverse = map[string][]test{
+ "nnn": {{next, "b"}, {next, ""}, {next, ""}},
+ "nns": {{next, "b"}, {next, ""}, {step, ""}},
+ "nsn": {{next, "b"}, {step, "a"}, {next, ""}},
+ "nss": {{next, "b"}, {step, "a"}, {step, ""}},
+ "snn": {{step, "b"}, {next, ""}, {next, ""}},
+ "sns": {{step, "b"}, {next, ""}, {step, ""}},
+ "ssn": {{step, "b"}, {step, "a"}, {next, ""}},
+ "sss": {{step, "b"}, {step, "a"}, {step, ""}},
+}
+
+// root
+// /|\
+// c a b
+func iter3Horizontal() *Iter {
+ a := newNode(hash, "a", empty)
+ b := newNode(hash, "b", empty)
+ c := newNode(hash, "c", empty)
+ root := newNode(hash, "root", []*node{c, a, b})
+ return NewIter(root)
+}
+
+var runs3Horizontal = map[string][]test{
+ "nnnn": {{next, "a"}, {next, "b"}, {next, "c"}, {next, ""}},
+ "nnns": {{next, "a"}, {next, "b"}, {next, "c"}, {step, ""}},
+ "nnsn": {{next, "a"}, {next, "b"}, {step, "c"}, {next, ""}},
+ "nnss": {{next, "a"}, {next, "b"}, {step, "c"}, {step, ""}},
+ "nsnn": {{next, "a"}, {step, "b"}, {next, "c"}, {next, ""}},
+ "nsns": {{next, "a"}, {step, "b"}, {next, "c"}, {step, ""}},
+ "nssn": {{next, "a"}, {step, "b"}, {step, "c"}, {next, ""}},
+ "nsss": {{next, "a"}, {step, "b"}, {step, "c"}, {step, ""}},
+ "snnn": {{step, "a"}, {next, "b"}, {next, "c"}, {next, ""}},
+ "snns": {{step, "a"}, {next, "b"}, {next, "c"}, {step, ""}},
+ "snsn": {{step, "a"}, {next, "b"}, {step, "c"}, {next, ""}},
+ "snss": {{step, "a"}, {next, "b"}, {step, "c"}, {step, ""}},
+ "ssnn": {{step, "a"}, {step, "b"}, {next, "c"}, {next, ""}},
+ "ssns": {{step, "a"}, {step, "b"}, {next, "c"}, {step, ""}},
+ "sssn": {{step, "a"}, {step, "b"}, {step, "c"}, {next, ""}},
+ "ssss": {{step, "a"}, {step, "b"}, {step, "c"}, {step, ""}},
+}
+
+// root
+// |
+// b
+// |
+// c
+// |
+// a
+func iter3Vertical() *Iter {
+ a := newNode(hash, "a", empty)
+ c := newNode(hash, "c", []*node{a})
+ b := newNode(hash, "b", []*node{c})
+ root := newNode(hash, "root", []*node{b})
+ return NewIter(root)
+}
+
+var runs3Vertical = map[string][]test{
+ "nnnn": {{next, "b"}, {next, ""}, {next, ""}, {next, ""}},
+ "nnns": {{next, "b"}, {next, ""}, {next, ""}, {step, ""}},
+ "nnsn": {{next, "b"}, {next, ""}, {step, ""}, {next, ""}},
+ "nnss": {{next, "b"}, {next, ""}, {step, ""}, {step, ""}},
+ "nsnn": {{next, "b"}, {step, "c"}, {next, ""}, {next, ""}},
+ "nsns": {{next, "b"}, {step, "c"}, {next, ""}, {step, ""}},
+ "nssn": {{next, "b"}, {step, "c"}, {step, "a"}, {next, ""}},
+ "nsss": {{next, "b"}, {step, "c"}, {step, "a"}, {step, ""}},
+ "snnn": {{step, "b"}, {next, ""}, {next, ""}, {next, ""}},
+ "snns": {{step, "b"}, {next, ""}, {next, ""}, {step, ""}},
+ "snsn": {{step, "b"}, {next, ""}, {step, ""}, {next, ""}},
+ "snss": {{step, "b"}, {next, ""}, {step, ""}, {step, ""}},
+ "ssnn": {{step, "b"}, {step, "c"}, {next, ""}, {next, ""}},
+ "ssns": {{step, "b"}, {step, "c"}, {next, ""}, {step, ""}},
+ "sssn": {{step, "b"}, {step, "c"}, {step, "a"}, {next, ""}},
+ "ssss": {{step, "b"}, {step, "c"}, {step, "a"}, {step, ""}},
+}
+
+// root
+// / \
+// c a
+// |
+// b
+func iter3Mix1() *Iter {
+ a := newNode(hash, "a", empty)
+ b := newNode(hash, "b", empty)
+ c := newNode(hash, "c", []*node{b})
+ root := newNode(hash, "root", []*node{c, a})
+ return NewIter(root)
+}
+
+var runs3Mix1 = map[string][]test{
+ "nnnn": {{next, "a"}, {next, "c"}, {next, ""}, {next, ""}},
+ "nnns": {{next, "a"}, {next, "c"}, {next, ""}, {step, ""}},
+ "nnsn": {{next, "a"}, {next, "c"}, {step, "b"}, {next, ""}},
+ "nnss": {{next, "a"}, {next, "c"}, {step, "b"}, {step, ""}},
+ "nsnn": {{next, "a"}, {step, "c"}, {next, ""}, {next, ""}},
+ "nsns": {{next, "a"}, {step, "c"}, {next, ""}, {step, ""}},
+ "nssn": {{next, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
+ "nsss": {{next, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
+ "snnn": {{step, "a"}, {next, "c"}, {next, ""}, {next, ""}},
+ "snns": {{step, "a"}, {next, "c"}, {next, ""}, {step, ""}},
+ "snsn": {{step, "a"}, {next, "c"}, {step, "b"}, {next, ""}},
+ "snss": {{step, "a"}, {next, "c"}, {step, "b"}, {step, ""}},
+ "ssnn": {{step, "a"}, {step, "c"}, {next, ""}, {next, ""}},
+ "ssns": {{step, "a"}, {step, "c"}, {next, ""}, {step, ""}},
+ "sssn": {{step, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
+ "ssss": {{step, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
+}
+
+// root
+// / \
+// b a
+// |
+// c
+func iter3Mix2() *Iter {
+ b := newNode(hash, "b", empty)
+ c := newNode(hash, "c", empty)
+ a := newNode(hash, "a", []*node{c})
+ root := newNode(hash, "root", []*node{b, a})
+ return NewIter(root)
+}
+
+var runs3Mix2 = map[string][]test{
+ "nnnn": {{next, "a"}, {next, "b"}, {next, ""}, {next, ""}},
+ "nnns": {{next, "a"}, {next, "b"}, {next, ""}, {step, ""}},
+ "nnsn": {{next, "a"}, {next, "b"}, {step, ""}, {next, ""}},
+ "nnss": {{next, "a"}, {next, "b"}, {step, ""}, {step, ""}},
+ "nsnn": {{next, "a"}, {step, "c"}, {next, "b"}, {next, ""}},
+ "nsns": {{next, "a"}, {step, "c"}, {next, "b"}, {step, ""}},
+ "nssn": {{next, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
+ "nsss": {{next, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
+ "snnn": {{step, "a"}, {next, "b"}, {next, ""}, {next, ""}},
+ "snns": {{step, "a"}, {next, "b"}, {next, ""}, {step, ""}},
+ "snsn": {{step, "a"}, {next, "b"}, {step, ""}, {next, ""}},
+ "snss": {{step, "a"}, {next, "b"}, {step, ""}, {step, ""}},
+ "ssnn": {{step, "a"}, {step, "c"}, {next, "b"}, {next, ""}},
+ "ssns": {{step, "a"}, {step, "c"}, {next, "b"}, {step, ""}},
+ "sssn": {{step, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
+ "ssss": {{step, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
+}
+
+// root
+// / | \
+// / | ----
+// f d h --------
+// /\ / \ |
+// e a j b g
+// | / \ |
+// l n k icm
+// |
+// o
+// |
+// p
+func iterCrazy() *Iter {
+ l := newNode(hash, "l", empty)
+ e := newNode(hash, "e", []*node{l})
+
+ p := newNode(hash, "p", empty)
+ o := newNode(hash, "o", []*node{p})
+ n := newNode(hash, "n", []*node{o})
+ k := newNode(hash, "k", empty)
+ a := newNode(hash, "a", []*node{n, k})
+ f := newNode(hash, "f", []*node{e, a})
+
+ d := newNode(hash, "d", empty)
+
+ i := newNode(hash, "i", empty)
+ c := newNode(hash, "c", empty)
+ m := newNode(hash, "m", empty)
+ j := newNode(hash, "j", []*node{i, c, m})
+ b := newNode(hash, "b", empty)
+ g := newNode(hash, "g", empty)
+ h := newNode(hash, "h", []*node{j, b, g})
+
+ root := newNode(hash, "root", []*node{f, d, h})
+ return NewIter(root)
+}
+
+var (
+ n = next
+ s = step
+)
+
+var runsCrazy = map[string][]test{
+ "nn nn n": {{n, "d"}, {n, "f"}, {n, "h"}, {n, ""}, {n, ""}},
+ "nn nn s": {{n, "d"}, {n, "f"}, {n, "h"}, {n, ""}, {s, ""}},
+ "nn ns n": {{n, "d"}, {n, "f"}, {n, "h"}, {s, "b"}, {n, "g"}},
+ "nn ns s": {{n, "d"}, {n, "f"}, {n, "h"}, {s, "b"}, {s, "g"}},
+ "nn sn n": {{n, "d"}, {n, "f"}, {s, "a"}, {n, "e"}, {n, "h"}},
+ "nn sn s": {{n, "d"}, {n, "f"}, {s, "a"}, {n, "e"}, {s, "l"}},
+ "nn ss n": {{n, "d"}, {n, "f"}, {s, "a"}, {s, "k"}, {n, "n"}},
+ "nn ss s": {{n, "d"}, {n, "f"}, {s, "a"}, {s, "k"}, {s, "n"}},
+ "ns nn n": {{n, "d"}, {s, "f"}, {n, "h"}, {n, ""}, {n, ""}},
+ "ns nn s": {{n, "d"}, {s, "f"}, {n, "h"}, {n, ""}, {s, ""}},
+ "ns ns n": {{n, "d"}, {s, "f"}, {n, "h"}, {s, "b"}, {n, "g"}},
+ "ns ns s": {{n, "d"}, {s, "f"}, {n, "h"}, {s, "b"}, {s, "g"}},
+ "ns sn n": {{n, "d"}, {s, "f"}, {s, "a"}, {n, "e"}, {n, "h"}},
+
+ "ns ss ns ss": {
+ {n, "d"}, {s, "f"},
+ {s, "a"}, {s, "k"},
+ {n, "n"}, {s, "o"},
+ {s, "p"}, {s, "e"},
+ },
+
+ "ns ss ns sn": {
+ {n, "d"}, {s, "f"},
+ {s, "a"}, {s, "k"},
+ {n, "n"}, {s, "o"},
+ {s, "p"}, {n, "e"},
+ },
+
+ "nn ns ns ss nn": {
+ {n, "d"}, {n, "f"},
+ {n, "h"}, {s, "b"},
+ {n, "g"}, {s, "j"},
+ {s, "c"}, {s, "i"},
+ {n, "m"}, {n, ""},
+ },
+}
diff --git a/plumbing/difftree/internal/merkletrie/iter_test.go b/plumbing/difftree/internal/merkletrie/iter_test.go
new file mode 100644
index 0000000..65116e1
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/iter_test.go
@@ -0,0 +1,176 @@
+package merkletrie
+
+import . "gopkg.in/check.v1"
+
+type IterSuite struct{}
+
+var _ = Suite(&IterSuite{})
+
+// we don't care about hashes for iterating the tree, so
+// use this hash for every object
+var hash = []byte{}
+
+// leafs have no children, use this empty list.
+var empty = []*node{}
+
+// test a defined as an operation to run on an iterator and the key of
+// the node expected to be returned by the operation. Use "" as the
+// expected key for when there are no more objects in the tree.
+type test struct {
+ operation int // next or step
+ expected string // key of the expected node, "" for nil node
+}
+
+// test.operation
+const (
+ next = iota
+ step
+)
+
+// goes over a list of tests, calling each operation on the iter and
+// checking that the obtained result is equal to the expected result
+func runTests(c *C, description string, iter *Iter, list []test) {
+ var obtained Noder
+ var ok bool
+ var comment CommentInterface
+
+ for i, t := range list {
+ comment = Commentf("description %q, operation #%d",
+ description, i+1)
+
+ switch t.operation {
+ case next:
+ obtained, ok = iter.Next()
+ case step:
+ obtained, ok = iter.Step()
+ default:
+ c.Fatalf("invalid operation %d", t.operation)
+ }
+
+ if t.expected == "" {
+ c.Assert(ok, Equals, false, comment)
+ c.Assert(obtained, IsNil, comment)
+ } else {
+ c.Assert(ok, Equals, true, comment)
+ c.Assert(obtained.Key(), Equals, t.expected, comment)
+ }
+ }
+}
+
+// a simple tree consisting on just a leaf
+func (s *IterSuite) TestLeaf(c *C) {
+ for description, tests := range runs0 {
+ runTests(c, description, iterLeaf(), tests)
+ }
+}
+
+// root
+// |
+// a
+func (s *IterSuite) TestOneChild(c *C) {
+ for description, tests := range runs1 {
+ runTests(c, description, iter1(), tests)
+ }
+}
+
+// root
+// / \
+// a b
+func (s *IterSuite) Test2HorizontalSorted(c *C) {
+ for description, tests := range runs2Horizontal {
+ runTests(c, description, iter2HorizontalSorted(), tests)
+ }
+}
+
+// root
+// / \
+// b a
+func (s *IterSuite) Test2HorizontalReverse(c *C) {
+ for description, tests := range runs2Horizontal {
+ runTests(c, description, iter2HorizontalReverse(), tests)
+ }
+}
+
+// root
+// |
+// a
+// |
+// b
+func (s *IterSuite) Test2VerticalSorted(c *C) {
+ for description, tests := range runs2VerticalSorted {
+ runTests(c, description, iter2VerticalSorted(), tests)
+ }
+}
+
+// root
+// |
+// b
+// |
+// a
+func (s *IterSuite) Test2VerticalReverse(c *C) {
+ for description, tests := range runs2VerticalReverse {
+ runTests(c, description, iter2VerticalReverse(), tests)
+ }
+}
+
+// root
+// /|\
+// c a b
+func (s *IterSuite) Test3Horizontal(c *C) {
+ for description, tests := range runs3Horizontal {
+ runTests(c, description, iter3Horizontal(), tests)
+ }
+}
+
+// root
+// |
+// b
+// |
+// c
+// |
+// a
+func (s *IterSuite) Test3Vertical(c *C) {
+ for description, tests := range runs3Vertical {
+ runTests(c, description, iter3Vertical(), tests)
+ }
+}
+
+// root
+// / \
+// c a
+// |
+// b
+func (s *IterSuite) Test3Mix1(c *C) {
+ for description, tests := range runs3Mix1 {
+ runTests(c, description, iter3Mix1(), tests)
+ }
+}
+
+// root
+// / \
+// b a
+// |
+// c
+func (s *IterSuite) Test3Mix2(c *C) {
+ for description, tests := range runs3Mix2 {
+ runTests(c, description, iter3Mix2(), tests)
+ }
+}
+
+// root
+// / | \
+// / | ----
+// f d h --------
+// /\ / \ |
+// e a j b g
+// | / \ |
+// l n k icm
+// |
+// o
+// |
+// p
+func (s *IterSuite) TestCrazy(c *C) {
+ for description, tests := range runsCrazy {
+ runTests(c, description, iterCrazy(), tests)
+ }
+}
diff --git a/plumbing/difftree/internal/merkletrie/node.go b/plumbing/difftree/internal/merkletrie/node.go
new file mode 100644
index 0000000..99be5b8
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/node.go
@@ -0,0 +1,65 @@
+package merkletrie
+
+import (
+ "sort"
+ "strings"
+)
+
+// A node is a Noder implementation for testing purposes: It is easier
+// to create test trees using nodes than using real git tree objects.
+type node struct {
+ hash []byte
+ key string
+ children []*node
+}
+
+// newNode returns a new Node with the given hash, key and children
+// (children can be specified in any order).
+func newNode(hash []byte, key string, children []*node) *node {
+ sort.Sort(reverseAlphabeticallyByKey(children))
+
+ return &node{
+ hash: hash,
+ key: key,
+ children: children,
+ }
+}
+
+// Hash returns the hash of the node.
+func (n *node) Hash() []byte {
+ return n.hash
+}
+
+// Key returns the key of the node.
+func (n *node) Key() string {
+ return n.key
+}
+
+// NumChildren returns the number of children.
+func (n *node) NumChildren() int {
+ return len(n.children)
+}
+
+// Children returns the node's children in reverse key alphabetical
+// order.
+func (n *node) Children() []Noder {
+ ret := make([]Noder, n.NumChildren())
+ for i := range n.children {
+ ret[i] = n.children[i]
+ }
+ return ret
+}
+
+type reverseAlphabeticallyByKey []*node
+
+func (a reverseAlphabeticallyByKey) Len() int {
+ return len(a)
+}
+
+func (a reverseAlphabeticallyByKey) Swap(i, j int) {
+ a[i], a[j] = a[j], a[i]
+}
+
+func (a reverseAlphabeticallyByKey) Less(i, j int) bool {
+ return strings.Compare(a[i].key, a[j].key) > 0
+}
diff --git a/plumbing/difftree/internal/merkletrie/node_test.go b/plumbing/difftree/internal/merkletrie/node_test.go
new file mode 100644
index 0000000..1622952
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/node_test.go
@@ -0,0 +1,68 @@
+package merkletrie
+
+import (
+ "testing"
+
+ . "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type NodeSuite struct{}
+
+var _ = Suite(&NodeSuite{})
+
+func (s *NodeSuite) TestHash(c *C) {
+ n := newNode([]byte("the_hash"), "the_key", []*node{})
+
+ expected := []byte("the_hash")
+ c.Assert(expected, DeepEquals, n.Hash())
+}
+
+func (s *NodeSuite) TestKey(c *C) {
+ n := newNode([]byte("the_hash"), "the_key", []*node{})
+
+ expected := "the_key"
+ c.Assert(expected, Equals, n.Key())
+}
+
+func (s *NodeSuite) TestNoChildren(c *C) {
+ n := newNode([]byte{}, "", []*node{})
+
+ expectedNumChildren := 0
+ c.Assert(n.NumChildren(), Equals, expectedNumChildren)
+
+ expectedChildren := []Noder{}
+ c.Assert(n.Children(), DeepEquals, expectedChildren)
+}
+
+func (s *NodeSuite) TestOneChild(c *C) {
+ child := newNode([]byte("child"), "child", []*node{})
+ parent := newNode([]byte("parent"), "parent", []*node{child})
+
+ expectedNumChildren := 1
+ c.Assert(parent.NumChildren(), Equals, expectedNumChildren)
+
+ expectedChildren := []Noder{Noder(child)}
+ c.Assert(parent.Children(), DeepEquals, expectedChildren)
+}
+
+func (s *NodeSuite) TestManyChildren(c *C) {
+ child0 := newNode([]byte("child0"), "child0", []*node{})
+ child1 := newNode([]byte("child1"), "child1", []*node{})
+ child2 := newNode([]byte("child2"), "child2", []*node{})
+ child3 := newNode([]byte("child3"), "child3", []*node{})
+ // children are added unsorted.
+ parent := newNode([]byte("parent"), "parent", []*node{child1, child3, child0, child2})
+
+ expectedNumChildren := 4
+ c.Assert(parent.NumChildren(), Equals, expectedNumChildren)
+
+ expectedChildren := []Noder{ // sorted alphabetically by key
+ Noder(child3),
+ Noder(child2),
+ Noder(child1),
+ Noder(child0),
+ }
+ c.Assert(parent.Children(), DeepEquals, expectedChildren)
+}
diff --git a/plumbing/difftree/internal/merkletrie/noder.go b/plumbing/difftree/internal/merkletrie/noder.go
new file mode 100644
index 0000000..3566657
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/noder.go
@@ -0,0 +1,20 @@
+package merkletrie
+
+// The Noder interface is implemented by the elements of a Merkle Trie.
+type Noder interface {
+ // Hash returns the hash of the element.
+ Hash() []byte
+ // Key returns the key of the element.
+ Key() string
+ // Children returns the children of the element, sorted
+ // in reverse key alphabetical order.
+ Children() []Noder
+ // 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
+}
generated by cgit (git 2.34.1) at 2024-09-20 13:28:22 +0000