| package merkletrie_test |
| |
| import ( |
| "fmt" |
| "io" |
| "strings" |
| |
| "gopkg.in/src-d/go-git.v4/utils/merkletrie" |
| "gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/fsnoder" |
| "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" |
| |
| . "gopkg.in/check.v1" |
| ) |
| |
| 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 expressed 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 expected 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, b := 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 (%c)\n", |
| testNumber, i, b) |
| } |
| 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{ noder.Noder } |
| |
| func (e *errorNoder) Children() ([]noder.Noder, error) { |
| return nil, fmt.Errorf("mock error") |
| } |
| |
| func (s *IterSuite) TestNewIterNil(c *C) { |
| i, err := merkletrie.NewIter(nil) |
| c.Assert(err, IsNil) |
| _, err = i.Next() |
| c.Assert(err, Equals, io.EOF) |
| } |
| |
| func (s *IterSuite) TestNewIterFailsOnChildrenErrors(c *C) { |
| _, err := merkletrie.NewIter(&errorNoder{}) |
| c.Assert(err, ErrorMatches, "mock error") |
| } |