From 844169a739fb8bf1f252d416f10d8c7034db9fe2 Mon Sep 17 00:00:00 2001 From: Alberto Cortés Date: Wed, 23 Nov 2016 15:20:32 +0100 Subject: difftree: merkletrie internal package with iterator (#133) --- difftree/internal/radixmerkle/doc.go | 30 ++ difftree/internal/radixmerkle/frame.go | 79 +++++ difftree/internal/radixmerkle/frame_test.go | 69 +++++ difftree/internal/radixmerkle/iter.go | 167 +++++++++++ .../internal/radixmerkle/iter_fixtures_test.go | 330 +++++++++++++++++++++ difftree/internal/radixmerkle/iter_test.go | 176 +++++++++++ difftree/internal/radixmerkle/node.go | 65 ++++ difftree/internal/radixmerkle/node_test.go | 68 +++++ difftree/internal/radixmerkle/noder.go | 20 ++ 9 files changed, 1004 insertions(+) create mode 100644 difftree/internal/radixmerkle/doc.go create mode 100644 difftree/internal/radixmerkle/frame.go create mode 100644 difftree/internal/radixmerkle/frame_test.go create mode 100644 difftree/internal/radixmerkle/iter.go create mode 100644 difftree/internal/radixmerkle/iter_fixtures_test.go create mode 100644 difftree/internal/radixmerkle/iter_test.go create mode 100644 difftree/internal/radixmerkle/node.go create mode 100644 difftree/internal/radixmerkle/node_test.go create mode 100644 difftree/internal/radixmerkle/noder.go (limited to 'difftree/internal') diff --git a/difftree/internal/radixmerkle/doc.go b/difftree/internal/radixmerkle/doc.go new file mode 100644 index 0000000..f8c3b2f --- /dev/null +++ b/difftree/internal/radixmerkle/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/difftree/internal/radixmerkle/frame.go b/difftree/internal/radixmerkle/frame.go new file mode 100644 index 0000000..a40c6ad --- /dev/null +++ b/difftree/internal/radixmerkle/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/difftree/internal/radixmerkle/frame_test.go b/difftree/internal/radixmerkle/frame_test.go new file mode 100644 index 0000000..0ef036a --- /dev/null +++ b/difftree/internal/radixmerkle/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/difftree/internal/radixmerkle/iter.go b/difftree/internal/radixmerkle/iter.go new file mode 100644 index 0000000..e175966 --- /dev/null +++ b/difftree/internal/radixmerkle/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/difftree/internal/radixmerkle/iter_fixtures_test.go b/difftree/internal/radixmerkle/iter_fixtures_test.go new file mode 100644 index 0000000..20bddaf --- /dev/null +++ b/difftree/internal/radixmerkle/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/difftree/internal/radixmerkle/iter_test.go b/difftree/internal/radixmerkle/iter_test.go new file mode 100644 index 0000000..65116e1 --- /dev/null +++ b/difftree/internal/radixmerkle/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/difftree/internal/radixmerkle/node.go b/difftree/internal/radixmerkle/node.go new file mode 100644 index 0000000..99be5b8 --- /dev/null +++ b/difftree/internal/radixmerkle/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/difftree/internal/radixmerkle/node_test.go b/difftree/internal/radixmerkle/node_test.go new file mode 100644 index 0000000..1622952 --- /dev/null +++ b/difftree/internal/radixmerkle/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/difftree/internal/radixmerkle/noder.go b/difftree/internal/radixmerkle/noder.go new file mode 100644 index 0000000..3566657 --- /dev/null +++ b/difftree/internal/radixmerkle/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 +} -- cgit