aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--utils/merkletrie/internal/frame/frame.go91
-rw-r--r--utils/merkletrie/internal/frame/frame_test.go108
-rw-r--r--utils/merkletrie/iter.go212
-rw-r--r--utils/merkletrie/iter_test.go462
4 files changed, 873 insertions, 0 deletions
diff --git a/utils/merkletrie/internal/frame/frame.go b/utils/merkletrie/internal/frame/frame.go
new file mode 100644
index 0000000..fd06307
--- /dev/null
+++ b/utils/merkletrie/internal/frame/frame.go
@@ -0,0 +1,91 @@
+package frame
+
+import (
+ "bytes"
+ "fmt"
+ "sort"
+ "strings"
+
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+// A Frame is a collection of siblings in a trie, sorted alphabetically
+// by name.
+type Frame struct {
+ // siblings, sorted in reverse alphabetical order by name
+ stack []noder.Noder
+}
+
+type byName []noder.Noder
+
+func (a byName) Len() int { return len(a) }
+func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a byName) Less(i, j int) bool {
+ return strings.Compare(a[i].Name(), a[j].Name()) < 0
+}
+
+// New returns a frame with the children of the provided node.
+func New(n noder.Noder) (*Frame, error) {
+ children, err := n.Children()
+ if err != nil {
+ return nil, err
+ }
+
+ sort.Sort(sort.Reverse(byName(children)))
+ return &Frame{
+ stack: children,
+ }, nil
+}
+
+// String returns the quoted names of the noders in the frame sorted in
+// alphabeticall order by name, surrounded by square brackets and
+// separated by comas.
+//
+// Examples:
+// []
+// ["a", "b"]
+func (f *Frame) String() string {
+ var buf bytes.Buffer
+ _ = buf.WriteByte('[')
+
+ sep := ""
+ for i := f.Len() - 1; i >= 0; i-- {
+ _, _ = buf.WriteString(sep)
+ sep = ", "
+ _, _ = buf.WriteString(fmt.Sprintf("%q", f.stack[i].Name()))
+ }
+
+ _ = buf.WriteByte(']')
+
+ return buf.String()
+}
+
+// First returns, but dont extract, the noder with the alphabetically
+// smaller name in the frame and true if the frame was not empy.
+// Otherwise it returns nil and false.
+func (f *Frame) First() (noder.Noder, bool) {
+ if f.Len() == 0 {
+ return nil, false
+ }
+
+ top := f.Len() - 1
+
+ return f.stack[top], true
+}
+
+// Drop extracts the noder with the alphabetically smaller name in the
+// frame or does nothing if the frame was empty.
+func (f *Frame) Drop() {
+ if f.Len() == 0 {
+ return
+ }
+
+ top := f.Len() - 1
+ f.stack[top] = nil
+ f.stack = f.stack[:top]
+}
+
+// Len returns the number of noders in the frame.
+func (f *Frame) Len() int {
+ return len(f.stack)
+}
diff --git a/utils/merkletrie/internal/frame/frame_test.go b/utils/merkletrie/internal/frame/frame_test.go
new file mode 100644
index 0000000..9cc0994
--- /dev/null
+++ b/utils/merkletrie/internal/frame/frame_test.go
@@ -0,0 +1,108 @@
+package frame
+
+import (
+ "fmt"
+ "testing"
+
+ "srcd.works/go-git.v4/utils/merkletrie/internal/fsnoder"
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
+
+ . "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type FrameSuite struct{}
+
+var _ = Suite(&FrameSuite{})
+
+func (s *FrameSuite) TestNewFrameFromEmptyDir(c *C) {
+ A, err := fsnoder.New("A()")
+ c.Assert(err, IsNil)
+
+ frame, err := New(A)
+ c.Assert(err, IsNil)
+
+ expectedString := `[]`
+ c.Assert(frame.String(), Equals, expectedString)
+
+ first, ok := frame.First()
+ c.Assert(first, IsNil)
+ c.Assert(ok, Equals, false)
+
+ first, ok = frame.First()
+ c.Assert(first, IsNil)
+ c.Assert(ok, Equals, false)
+
+ l := frame.Len()
+ c.Assert(l, Equals, 0)
+}
+
+func (s *FrameSuite) TestNewFrameFromNonEmpty(c *C) {
+ // _______A/________
+ // | / \ |
+ // x y B/ C/
+ // |
+ // z
+ root, err := fsnoder.New("A(x<> y<> B() C(z<>))")
+ c.Assert(err, IsNil)
+ frame, err := New(root)
+ c.Assert(err, IsNil)
+
+ expectedString := `["B", "C", "x", "y"]`
+ c.Assert(frame.String(), Equals, expectedString)
+
+ l := frame.Len()
+ c.Assert(l, Equals, 4)
+
+ checkFirstAndDrop(c, frame, "B", true)
+ l = frame.Len()
+ c.Assert(l, Equals, 3)
+
+ checkFirstAndDrop(c, frame, "C", true)
+ l = frame.Len()
+ c.Assert(l, Equals, 2)
+
+ checkFirstAndDrop(c, frame, "x", true)
+ l = frame.Len()
+ c.Assert(l, Equals, 1)
+
+ checkFirstAndDrop(c, frame, "y", true)
+ l = frame.Len()
+ c.Assert(l, Equals, 0)
+
+ checkFirstAndDrop(c, frame, "", false)
+ l = frame.Len()
+ c.Assert(l, Equals, 0)
+
+ checkFirstAndDrop(c, frame, "", false)
+}
+
+func checkFirstAndDrop(c *C, f *Frame, expectedNodeName string, expectedOK bool) {
+ first, ok := f.First()
+ c.Assert(ok, Equals, expectedOK)
+ if expectedOK {
+ c.Assert(first.Name(), Equals, expectedNodeName)
+ }
+
+ f.Drop()
+}
+
+// a mock noder that returns error when Children() is called
+type errorNoder struct{}
+
+func (e *errorNoder) Hash() []byte { return nil }
+func (e *errorNoder) Name() string { return "" }
+func (e *errorNoder) String() string { return "" }
+func (e *errorNoder) IsDir() bool { return true }
+func (e *errorNoder) Children() ([]noder.Noder, error) {
+ return nil, fmt.Errorf("mock error")
+}
+func (e *errorNoder) NumChildren() (int, error) {
+ return 0, fmt.Errorf("mock error")
+}
+
+func (s *FrameSuite) TestNewFrameErrors(c *C) {
+ _, err := New(&errorNoder{})
+ c.Assert(err, Not(IsNil))
+}
diff --git a/utils/merkletrie/iter.go b/utils/merkletrie/iter.go
new file mode 100644
index 0000000..44cba70
--- /dev/null
+++ b/utils/merkletrie/iter.go
@@ -0,0 +1,212 @@
+package merkletrie
+
+import (
+ "fmt"
+ "io"
+
+ "srcd.works/go-git.v4/utils/merkletrie/internal/frame"
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+// Iter is an iterator for merkletries (only the trie part of the
+// merkletrie is relevant here, it does not use the Hasher interface).
+//
+// The iteration is performed in depth-first pre-order. Entries at each
+// depth are traversed in (case-sensitive) alphabetical order.
+//
+// This is the kind of traversal you will expect when listing ordinary
+// files and directories recursively, for example:
+//
+// Trie Traversal order
+// ---- ---------------
+// .
+// / | \ c
+// / | \ d/
+// d c z ===> d/a
+// / \ d/b
+// b a z
+//
+//
+// This iterator is somewhat especial as you can chose to skip whole
+// "directories" when iterating:
+//
+// - The Step method will iterate normally.
+//
+// - the Next method will not descend deeper into the tree.
+//
+// For example, if the iterator is at `d/`, the Step method will return
+// `d/a` while the Next would have returned `z` instead (skipping `d/`
+// and its descendants). The name of the these two methods are based on
+// the well known "next" and "step" operations, quite common in
+// debuggers, like gdb.
+//
+// The paths returned by the iterator will be relative, if the iterator
+// was created from a single node, or absolute, if the iterator was
+// created from the path to the node (the path will be prefixed to all
+// returned paths).
+type Iter struct {
+ // Tells if the iteration has started.
+ hasStarted bool
+ // The top of this stack has the current node and its siblings. The
+ // rest of the stack keeps the ancestors of the current node and
+ // their corresponding siblings. The current element is always the
+ // top element of the top frame.
+ //
+ // When "step"ping into a node, its children are pushed as a new
+ // frame.
+ //
+ // When "next"ing pass a node, the current element is dropped by
+ // popping the top frame.
+ frameStack []*frame.Frame
+ // The base path used to turn the relative paths used internally by
+ // the iterator into absolute paths used by external applications.
+ // For relative iterator this will be nil.
+ base noder.Path
+}
+
+// NewIter returns a new relative iterator using the provider noder as
+// its unnamed root. When iterating, all returned paths will be
+// relative to node.
+func NewIter(n noder.Noder) (*Iter, error) {
+ return newIter(n, nil)
+}
+
+// NewIterFromPath returns a new absolute iterator from the noder at the
+// end of the path p. When iterating, all returned paths will be
+// absolute, using the root of the path p as their root.
+func NewIterFromPath(p noder.Path) (*Iter, error) {
+ return newIter(p, p) // Path implements Noder
+}
+
+func newIter(root noder.Noder, base noder.Path) (*Iter, error) {
+ ret := &Iter{
+ base: base,
+ }
+
+ frame, err := frame.New(root)
+ if err != nil {
+ return nil, err
+ }
+ ret.push(frame)
+
+ return ret, nil
+}
+
+func (iter *Iter) top() (*frame.Frame, bool) {
+ if len(iter.frameStack) == 0 {
+ return nil, false
+ }
+ top := len(iter.frameStack) - 1
+
+ return iter.frameStack[top], true
+}
+
+func (iter *Iter) push(f *frame.Frame) {
+ iter.frameStack = append(iter.frameStack, f)
+}
+
+const (
+ doDescend = true
+ dontDescend = false
+)
+
+// Next returns the path of the next node without descending deeper into
+// the trie and nil. If there are no more entries in the trie it
+// returns nil and io.EOF. In case of error, it will return nil and the
+// error.
+func (iter *Iter) Next() (noder.Path, error) {
+ return iter.advance(dontDescend)
+}
+
+// Step returns the path to the next node in the trie, descending deeper
+// into it if needed, and nil. If there are no more nodes in the trie,
+// it returns nil and io.EOF. In case of error, it will return nil and
+// the error.
+func (iter *Iter) Step() (noder.Path, error) {
+ return iter.advance(doDescend)
+}
+
+// Advances the iterator in the desired direction: descend or
+// dontDescend.
+//
+// Returns the new current element and a nil error on success. If there
+// are no more elements in the trie below the base, it returns nil, and
+// io.EOF. Returns nil and an error in case of errors.
+func (iter *Iter) advance(wantDescend bool) (noder.Path, error) {
+ current, err := iter.current()
+ if err != nil {
+ return nil, err
+ }
+
+ // The first time we just return the current node.
+ if !iter.hasStarted {
+ iter.hasStarted = true
+ return current, nil
+ }
+
+ // Advances means getting a next current node, either its first child or
+ // its next sibling, depending if we must descend or not.
+ numChildren, err := current.NumChildren()
+ if err != nil {
+ return nil, err
+ }
+
+ mustDescend := numChildren != 0 && wantDescend
+ if mustDescend {
+ // descend: add a new frame with the current's children.
+ frame, err := frame.New(current)
+ if err != nil {
+ return nil, err
+ }
+ iter.push(frame)
+ } else {
+ // don't descend: just drop the current node
+ iter.drop()
+ }
+
+ return iter.current()
+}
+
+// Returns the path to the current node, adding the base if there was
+// one, and a nil error. If there were no noders left, it returns nil
+// and io.EOF. If an error occurred, it returns nil and the error.
+func (iter *Iter) current() (noder.Path, error) {
+ if topFrame, ok := iter.top(); !ok {
+ return nil, io.EOF
+ } else if _, ok := topFrame.First(); !ok {
+ return nil, io.EOF
+ }
+
+ ret := make(noder.Path, 0, len(iter.base)+len(iter.frameStack))
+
+ // concat the base...
+ ret = append(ret, iter.base...)
+ // ... and the current node and all its ancestors
+ for i, f := range iter.frameStack {
+ t, ok := f.First()
+ if !ok {
+ panic(fmt.Sprintf("frame %d is empty", i))
+ }
+ ret = append(ret, t)
+ }
+
+ return ret, nil
+}
+
+// removes the current node if any, and all the frames that become empty as a
+// consecuence of this action.
+func (iter *Iter) drop() {
+ frame, ok := iter.top()
+ if !ok {
+ return
+ }
+
+ frame.Drop()
+ // if the frame is empty, remove it and its parent, recursively
+ if frame.Len() == 0 {
+ top := len(iter.frameStack) - 1
+ iter.frameStack[top] = nil
+ iter.frameStack = iter.frameStack[:top]
+ iter.drop()
+ }
+}
diff --git a/utils/merkletrie/iter_test.go b/utils/merkletrie/iter_test.go
new file mode 100644
index 0000000..52d567a
--- /dev/null
+++ b/utils/merkletrie/iter_test.go
@@ -0,0 +1,462 @@
+package merkletrie_test
+
+import (
+ "fmt"
+ "io"
+ "strings"
+ "testing"
+
+ "srcd.works/go-git.v4/utils/merkletrie"
+ "srcd.works/go-git.v4/utils/merkletrie/internal/fsnoder"
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
+
+ . "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type IterSuite struct{}
+
+var _ = Suite(&IterSuite{})
+
+// A test is a list of operations we want to perform on an iterator and
+// their expected results.
+//
+// The operations are expresed as a sequence of `n` and `s`,
+// representing the amount of next and step operations we want to call
+// on the iterator and their order. For example, an operations value of
+// "nns" means: call a `n`ext, then another `n`ext and finish with a
+// `s`tep.
+//
+// The expeced is the full path of the noders returned by the
+// operations, separated by spaces.
+//
+// For instance:
+//
+// t := test{
+// operations: "ns",
+// expected: "a a/b"
+// }
+//
+// means:
+//
+// - the first iterator operation has to be Next, and it must return a
+// node called "a" with no ancestors.
+//
+// - the second operation has to be Step, and it must return a node
+// called "b" with a single ancestor called "a".
+type test struct {
+ operations string
+ expected string
+}
+
+// Runs a test on the provided iterator, checking that the names of the
+// returned values are correct. If not, the treeDescription value is
+// printed along with information about mismatch.
+func (t test) run(c *C, iter *merkletrie.Iter,
+ treeDescription string, testNumber int) {
+
+ expectedChunks := strings.Split(t.expected, " ")
+ if t.expected == "" {
+ expectedChunks = []string{}
+ }
+
+ if len(t.operations) < len(expectedChunks) {
+ c.Fatalf("malformed test %d: not enough operations", testNumber)
+ return
+ }
+
+ var obtained noder.Path
+ var err error
+ for i := range t.operations {
+ comment := Commentf("\ntree: %q\ntest #%d (%q)\noperation #%d (%q)",
+ treeDescription, testNumber, t.operations, i, t.operations[i])
+
+ switch t.operations[i] {
+ case 'n':
+ obtained, err = iter.Next()
+ if err != io.EOF {
+ c.Assert(err, IsNil)
+ }
+ case 's':
+ obtained, err = iter.Step()
+ if err != io.EOF {
+ c.Assert(err, IsNil)
+ }
+ default:
+ c.Fatalf("unknown operation at test %d, operation %d (%s)\n",
+ testNumber, i, t.operations[i])
+ }
+ if i >= len(expectedChunks) {
+ c.Assert(err, Equals, io.EOF, comment)
+ continue
+ }
+
+ c.Assert(err, IsNil, comment)
+ c.Assert(obtained.String(), Equals, expectedChunks[i], comment)
+ }
+}
+
+// A testsCollection value represents a tree and a collection of tests
+// we want to perfrom on iterators of that tree.
+//
+// Example:
+//
+// .
+// |
+// ---------
+// | | |
+// a b c
+// |
+// z
+//
+// var foo testCollection = {
+// tree: "(a<> b(z<>) c<>)"
+// tests: []test{
+// {operations: "nns", expected: "a b b/z"},
+// {operations: "nnn", expected: "a b c"},
+// },
+// }
+//
+// A new iterator will be build for each test.
+type testsCollection struct {
+ tree string // a fsnoder description of a tree.
+ tests []test // the collection of tests we want to run
+}
+
+// Executes all the tests in a testsCollection.
+func (tc testsCollection) run(c *C) {
+ root, err := fsnoder.New(tc.tree)
+ c.Assert(err, IsNil)
+
+ for i, t := range tc.tests {
+ iter, err := merkletrie.NewIter(root)
+ c.Assert(err, IsNil)
+ t.run(c, iter, root.String(), i)
+ }
+}
+
+func (s *IterSuite) TestEmptyNamedDir(c *C) {
+ tc := testsCollection{
+ tree: "A()",
+ tests: []test{
+ {operations: "n", expected: ""},
+ {operations: "nn", expected: ""},
+ {operations: "nnn", expected: ""},
+ {operations: "nnns", expected: ""},
+ {operations: "nnnssnsnns", expected: ""},
+ {operations: "s", expected: ""},
+ {operations: "ss", expected: ""},
+ {operations: "sss", expected: ""},
+ {operations: "sssn", expected: ""},
+ {operations: "sssnnsnssn", expected: ""},
+ },
+ }
+ tc.run(c)
+}
+
+func (s *IterSuite) TestEmptyUnnamedDir(c *C) {
+ tc := testsCollection{
+ tree: "()",
+ tests: []test{
+ {operations: "n", expected: ""},
+ {operations: "nn", expected: ""},
+ {operations: "nnn", expected: ""},
+ {operations: "nnns", expected: ""},
+ {operations: "nnnssnsnns", expected: ""},
+ {operations: "s", expected: ""},
+ {operations: "ss", expected: ""},
+ {operations: "sss", expected: ""},
+ {operations: "sssn", expected: ""},
+ {operations: "sssnnsnssn", expected: ""},
+ },
+ }
+ tc.run(c)
+}
+
+func (s *IterSuite) TestOneFile(c *C) {
+ tc := testsCollection{
+ tree: "(a<>)",
+ tests: []test{
+ {operations: "n", expected: "a"},
+ {operations: "nn", expected: "a"},
+ {operations: "nnn", expected: "a"},
+ {operations: "nnns", expected: "a"},
+ {operations: "nnnssnsnns", expected: "a"},
+ {operations: "s", expected: "a"},
+ {operations: "ss", expected: "a"},
+ {operations: "sss", expected: "a"},
+ {operations: "sssn", expected: "a"},
+ {operations: "sssnnsnssn", expected: "a"},
+ },
+ }
+ tc.run(c)
+}
+
+// root
+// / \
+// a b
+func (s *IterSuite) TestTwoFiles(c *C) {
+ tc := testsCollection{
+ tree: "(a<> b<>)",
+ tests: []test{
+ {operations: "nnn", expected: "a b"},
+ {operations: "nns", expected: "a b"},
+ {operations: "nsn", expected: "a b"},
+ {operations: "nss", expected: "a b"},
+ {operations: "snn", expected: "a b"},
+ {operations: "sns", expected: "a b"},
+ {operations: "ssn", expected: "a b"},
+ {operations: "sss", expected: "a b"},
+ },
+ }
+ tc.run(c)
+}
+
+// root
+// |
+// a
+// |
+// b
+func (s *IterSuite) TestDirWithFile(c *C) {
+ tc := testsCollection{
+ tree: "(a(b<>))",
+ tests: []test{
+ {operations: "nnn", expected: "a"},
+ {operations: "nns", expected: "a"},
+ {operations: "nsn", expected: "a a/b"},
+ {operations: "nss", expected: "a a/b"},
+ {operations: "snn", expected: "a"},
+ {operations: "sns", expected: "a"},
+ {operations: "ssn", expected: "a a/b"},
+ {operations: "sss", expected: "a a/b"},
+ },
+ }
+ tc.run(c)
+}
+
+// root
+// /|\
+// c a b
+func (s *IterSuite) TestThreeSiblings(c *C) {
+ tc := testsCollection{
+ tree: "(c<> a<> b<>)",
+ tests: []test{
+ {operations: "nnnn", expected: "a b c"},
+ {operations: "nnns", expected: "a b c"},
+ {operations: "nnsn", expected: "a b c"},
+ {operations: "nnss", expected: "a b c"},
+ {operations: "nsnn", expected: "a b c"},
+ {operations: "nsns", expected: "a b c"},
+ {operations: "nssn", expected: "a b c"},
+ {operations: "nsss", expected: "a b c"},
+ {operations: "snnn", expected: "a b c"},
+ {operations: "snns", expected: "a b c"},
+ {operations: "snsn", expected: "a b c"},
+ {operations: "snss", expected: "a b c"},
+ {operations: "ssnn", expected: "a b c"},
+ {operations: "ssns", expected: "a b c"},
+ {operations: "sssn", expected: "a b c"},
+ {operations: "ssss", expected: "a b c"},
+ },
+ }
+ tc.run(c)
+}
+
+// root
+// |
+// b
+// |
+// c
+// |
+// a
+func (s *IterSuite) TestThreeVertical(c *C) {
+ tc := testsCollection{
+ tree: "(b(c(a())))",
+ tests: []test{
+ {operations: "nnnn", expected: "b"},
+ {operations: "nnns", expected: "b"},
+ {operations: "nnsn", expected: "b"},
+ {operations: "nnss", expected: "b"},
+ {operations: "nsnn", expected: "b b/c"},
+ {operations: "nsns", expected: "b b/c"},
+ {operations: "nssn", expected: "b b/c b/c/a"},
+ {operations: "nsss", expected: "b b/c b/c/a"},
+ {operations: "snnn", expected: "b"},
+ {operations: "snns", expected: "b"},
+ {operations: "snsn", expected: "b"},
+ {operations: "snss", expected: "b"},
+ {operations: "ssnn", expected: "b b/c"},
+ {operations: "ssns", expected: "b b/c"},
+ {operations: "sssn", expected: "b b/c b/c/a"},
+ {operations: "ssss", expected: "b b/c b/c/a"},
+ },
+ }
+ tc.run(c)
+}
+
+// root
+// / \
+// c a
+// |
+// b
+func (s *IterSuite) TestThreeMix1(c *C) {
+ tc := testsCollection{
+ tree: "(c(b<>) a<>)",
+ tests: []test{
+ {operations: "nnnn", expected: "a c"},
+ {operations: "nnns", expected: "a c"},
+ {operations: "nnsn", expected: "a c c/b"},
+ {operations: "nnss", expected: "a c c/b"},
+ {operations: "nsnn", expected: "a c"},
+ {operations: "nsns", expected: "a c"},
+ {operations: "nssn", expected: "a c c/b"},
+ {operations: "nsss", expected: "a c c/b"},
+ {operations: "snnn", expected: "a c"},
+ {operations: "snns", expected: "a c"},
+ {operations: "snsn", expected: "a c c/b"},
+ {operations: "snss", expected: "a c c/b"},
+ {operations: "ssnn", expected: "a c"},
+ {operations: "ssns", expected: "a c"},
+ {operations: "sssn", expected: "a c c/b"},
+ {operations: "ssss", expected: "a c c/b"},
+ },
+ }
+ tc.run(c)
+}
+
+// root
+// / \
+// b a
+// |
+// c
+func (s *IterSuite) TestThreeMix2(c *C) {
+ tc := testsCollection{
+ tree: "(b() a(c<>))",
+ tests: []test{
+ {operations: "nnnn", expected: "a b"},
+ {operations: "nnns", expected: "a b"},
+ {operations: "nnsn", expected: "a b"},
+ {operations: "nnss", expected: "a b"},
+ {operations: "nsnn", expected: "a a/c b"},
+ {operations: "nsns", expected: "a a/c b"},
+ {operations: "nssn", expected: "a a/c b"},
+ {operations: "nsss", expected: "a a/c b"},
+ {operations: "snnn", expected: "a b"},
+ {operations: "snns", expected: "a b"},
+ {operations: "snsn", expected: "a b"},
+ {operations: "snss", expected: "a b"},
+ {operations: "ssnn", expected: "a a/c b"},
+ {operations: "ssns", expected: "a a/c b"},
+ {operations: "sssn", expected: "a a/c b"},
+ {operations: "ssss", expected: "a a/c b"},
+ },
+ }
+ tc.run(c)
+}
+
+// root
+// / | \
+// / | ----
+// f d h --------
+// /\ / \ |
+// e a j b/ g
+// | / \ |
+// l n k icm
+// |
+// o
+// |
+// p/
+func (s *IterSuite) TestCrazy(c *C) {
+ tc := testsCollection{
+ tree: "(f(e(l<>) a(n(o(p())) k<>)) d<> h(j(i<> c<> m<>) b() g<>))",
+ tests: []test{
+ {operations: "nnnnn", expected: "d f h"},
+ {operations: "nnnns", expected: "d f h"},
+ {operations: "nnnsn", expected: "d f h h/b h/g"},
+ {operations: "nnnss", expected: "d f h h/b h/g"},
+ {operations: "nnsnn", expected: "d f f/a f/e h"},
+ {operations: "nnsns", expected: "d f f/a f/e f/e/l"},
+ {operations: "nnssn", expected: "d f f/a f/a/k f/a/n"},
+ {operations: "nnsss", expected: "d f f/a f/a/k f/a/n"},
+ {operations: "nsnnn", expected: "d f h"},
+ {operations: "nsnns", expected: "d f h"},
+ {operations: "nsnsn", expected: "d f h h/b h/g"},
+ {operations: "nsnss", expected: "d f h h/b h/g"},
+ {operations: "nssnn", expected: "d f f/a f/e h"},
+ },
+ }
+ tc.run(c)
+}
+
+// .
+// |
+// a
+// |
+// b
+// / \
+// z h
+// / \
+// d e
+// |
+// f
+func (s *IterSuite) TestNewIterFromPath(c *C) {
+ tree, err := fsnoder.New("(a(b(z(d<> e(f<>)) h<>)))")
+ c.Assert(err, IsNil)
+
+ z := find(c, tree, "z")
+
+ iter, err := merkletrie.NewIterFromPath(z)
+ c.Assert(err, IsNil)
+
+ n, err := iter.Next()
+ c.Assert(err, IsNil)
+ c.Assert(n.String(), Equals, "a/b/z/d")
+
+ n, err = iter.Next()
+ c.Assert(err, IsNil)
+ c.Assert(n.String(), Equals, "a/b/z/e")
+
+ n, err = iter.Step()
+ c.Assert(err, IsNil)
+ c.Assert(n.String(), Equals, "a/b/z/e/f")
+
+ _, err = iter.Step()
+ c.Assert(err, Equals, io.EOF)
+}
+
+func find(c *C, tree noder.Noder, name string) noder.Path {
+ iter, err := merkletrie.NewIter(tree)
+ c.Assert(err, IsNil)
+
+ for {
+ current, err := iter.Step()
+ if err != io.EOF {
+ c.Assert(err, IsNil)
+ } else {
+ c.Fatalf("node %s not found in tree %s", name, tree)
+ }
+
+ if current.Name() == name {
+ return current
+ }
+ }
+}
+
+type errorNoder struct{}
+
+func (e *errorNoder) Name() string { return "" }
+func (e *errorNoder) String() string { return "" }
+func (e *errorNoder) Hash() []byte { return nil }
+func (e *errorNoder) IsDir() bool { return true }
+func (e *errorNoder) Children() ([]noder.Noder, error) {
+ return nil, fmt.Errorf("mock error")
+}
+func (e *errorNoder) NumChildren() (int, error) {
+ return 0, fmt.Errorf("mock error")
+}
+
+func (s *IterSuite) TestNewIterFailsOnChildrenErrors(c *C) {
+ _, err := merkletrie.NewIter(&errorNoder{})
+ c.Assert(err, Not(IsNil))
+}
generated by cgit (git 2.34.1) at 2024-11-10 09:23:51 +0000