aboutsummaryrefslogtreecommitdiffstats
path: root/difftree
diff options
context:
space:
mode:
Diffstat (limited to 'difftree')
-rw-r--r--difftree/internal/merkletrie/doc.go30
-rw-r--r--difftree/internal/merkletrie/frame.go79
-rw-r--r--difftree/internal/merkletrie/frame_test.go69
-rw-r--r--difftree/internal/merkletrie/iter.go167
-rw-r--r--difftree/internal/merkletrie/iter_fixtures_test.go330
-rw-r--r--difftree/internal/merkletrie/iter_test.go176
-rw-r--r--difftree/internal/merkletrie/node.go65
-rw-r--r--difftree/internal/merkletrie/node_test.go68
-rw-r--r--difftree/internal/merkletrie/noder.go20
9 files changed, 0 insertions, 1004 deletions
diff --git a/difftree/internal/merkletrie/doc.go b/difftree/internal/merkletrie/doc.go
deleted file mode 100644
index f8c3b2f..0000000
--- a/difftree/internal/merkletrie/doc.go
+++ /dev/null
@@ -1,30 +0,0 @@
-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/merkletrie/frame.go b/difftree/internal/merkletrie/frame.go
deleted file mode 100644
index a40c6ad..0000000
--- a/difftree/internal/merkletrie/frame.go
+++ /dev/null
@@ -1,79 +0,0 @@
-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/merkletrie/frame_test.go b/difftree/internal/merkletrie/frame_test.go
deleted file mode 100644
index 0ef036a..0000000
--- a/difftree/internal/merkletrie/frame_test.go
+++ /dev/null
@@ -1,69 +0,0 @@
-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/merkletrie/iter.go b/difftree/internal/merkletrie/iter.go
deleted file mode 100644
index e175966..0000000
--- a/difftree/internal/merkletrie/iter.go
+++ /dev/null
@@ -1,167 +0,0 @@
-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/merkletrie/iter_fixtures_test.go b/difftree/internal/merkletrie/iter_fixtures_test.go
deleted file mode 100644
index 20bddaf..0000000
--- a/difftree/internal/merkletrie/iter_fixtures_test.go
+++ /dev/null
@@ -1,330 +0,0 @@
-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/merkletrie/iter_test.go b/difftree/internal/merkletrie/iter_test.go
deleted file mode 100644
index 65116e1..0000000
--- a/difftree/internal/merkletrie/iter_test.go
+++ /dev/null
@@ -1,176 +0,0 @@
-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/merkletrie/node.go b/difftree/internal/merkletrie/node.go
deleted file mode 100644
index 99be5b8..0000000
--- a/difftree/internal/merkletrie/node.go
+++ /dev/null
@@ -1,65 +0,0 @@
-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/merkletrie/node_test.go b/difftree/internal/merkletrie/node_test.go
deleted file mode 100644
index 1622952..0000000
--- a/difftree/internal/merkletrie/node_test.go
+++ /dev/null
@@ -1,68 +0,0 @@
-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/merkletrie/noder.go b/difftree/internal/merkletrie/noder.go
deleted file mode 100644
index 3566657..0000000
--- a/difftree/internal/merkletrie/noder.go
+++ /dev/null
@@ -1,20 +0,0 @@
-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-11-14 18:26:14 +0000