aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie/difftree_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'utils/merkletrie/difftree_test.go')
-rw-r--r--utils/merkletrie/difftree_test.go429
1 files changed, 429 insertions, 0 deletions
diff --git a/utils/merkletrie/difftree_test.go b/utils/merkletrie/difftree_test.go
new file mode 100644
index 0000000..6a193af
--- /dev/null
+++ b/utils/merkletrie/difftree_test.go
@@ -0,0 +1,429 @@
+package merkletrie_test
+
+import (
+ "bytes"
+ "fmt"
+ "reflect"
+ "sort"
+ "strings"
+ "testing"
+ "unicode"
+
+ "srcd.works/go-git.v4/utils/merkletrie"
+ "srcd.works/go-git.v4/utils/merkletrie/internal/fsnoder"
+
+ . "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type DiffTreeSuite struct{}
+
+var _ = Suite(&DiffTreeSuite{})
+
+type diffTreeTest struct {
+ from string
+ to string
+ expected string
+}
+
+func (t diffTreeTest) innerRun(c *C, context string, reverse bool) {
+ comment := Commentf("\n%s", context)
+ if reverse {
+ comment = Commentf("%s [REVERSED]", comment.CheckCommentString())
+ }
+
+ a, err := fsnoder.New(t.from)
+ c.Assert(err, IsNil, comment)
+ comment = Commentf("%s\n\t from = %s", comment.CheckCommentString(), a)
+
+ b, err := fsnoder.New(t.to)
+ c.Assert(err, IsNil, comment)
+ comment = Commentf("%s\n\t to = %s", comment.CheckCommentString(), b)
+
+ expected, err := newChangesFromString(t.expected)
+ c.Assert(err, IsNil, comment)
+
+ if reverse {
+ a, b = b, a
+ expected = expected.reverse()
+ }
+ comment = Commentf("%s\n\texpected = %s", comment.CheckCommentString(), expected)
+
+ results, err := merkletrie.DiffTree(a, b, fsnoder.HashEqual)
+ c.Assert(err, IsNil, comment)
+
+ obtained, err := newChanges(results)
+ c.Assert(err, IsNil, comment)
+
+ comment = Commentf("%s\n\tobtained = %s", comment.CheckCommentString(), obtained)
+
+ c.Assert(obtained, changesEquals, expected, comment)
+}
+
+func (t diffTreeTest) run(c *C, context string) {
+ t.innerRun(c, context, false)
+ t.innerRun(c, context, true)
+}
+
+type change struct {
+ merkletrie.Action
+ path string
+}
+
+func (c change) String() string {
+ return fmt.Sprintf("<%s %s>", c.Action, c.path)
+}
+
+func (c change) reverse() change {
+ ret := change{
+ path: c.path,
+ }
+
+ switch c.Action {
+ case merkletrie.Insert:
+ ret.Action = merkletrie.Delete
+ case merkletrie.Delete:
+ ret.Action = merkletrie.Insert
+ case merkletrie.Modify:
+ ret.Action = merkletrie.Modify
+ default:
+ panic(fmt.Sprintf("unknown action type: %d", c.Action))
+ }
+
+ return ret
+}
+
+type changes []change
+
+func newChanges(original merkletrie.Changes) (changes, error) {
+ ret := make(changes, len(original))
+ for i, c := range original {
+ action, err := c.Action()
+ if err != nil {
+ return nil, err
+ }
+ switch action {
+ case merkletrie.Insert:
+ ret[i] = change{
+ Action: merkletrie.Insert,
+ path: c.To.String(),
+ }
+ case merkletrie.Delete:
+ ret[i] = change{
+ Action: merkletrie.Delete,
+ path: c.From.String(),
+ }
+ case merkletrie.Modify:
+ ret[i] = change{
+ Action: merkletrie.Modify,
+ path: c.From.String(),
+ }
+ default:
+ panic(fmt.Sprintf("unsupported action %d", c.Action))
+ }
+ }
+
+ return ret, nil
+}
+
+func newChangesFromString(s string) (changes, error) {
+ ret := make([]change, 0)
+
+ s = strings.TrimSpace(s)
+ s = removeDuplicatedSpace(s)
+ s = turnSpaceIntoLiteralSpace(s)
+
+ if s == "" {
+ return ret, nil
+ }
+
+ for _, chunk := range strings.Split(s, " ") {
+ change := change{
+ path: string(chunk[1:]),
+ }
+
+ switch chunk[0] {
+ case '+':
+ change.Action = merkletrie.Insert
+ case '-':
+ change.Action = merkletrie.Delete
+ case '*':
+ change.Action = merkletrie.Modify
+ default:
+ panic(fmt.Sprintf("unsupported action descriptor %q", chunk[0]))
+ }
+
+ ret = append(ret, change)
+ }
+
+ return ret, nil
+}
+
+func removeDuplicatedSpace(s string) string {
+ var buf bytes.Buffer
+
+ var lastWasSpace, currentIsSpace bool
+ for _, r := range s {
+ currentIsSpace = unicode.IsSpace(r)
+
+ if lastWasSpace && currentIsSpace {
+ continue
+ }
+ lastWasSpace = currentIsSpace
+
+ buf.WriteRune(r)
+ }
+
+ return buf.String()
+}
+
+func turnSpaceIntoLiteralSpace(s string) string {
+ return strings.Map(
+ func(r rune) rune {
+ if unicode.IsSpace(r) {
+ return ' '
+ }
+ return r
+ }, s)
+}
+
+func (cc changes) Len() int { return len(cc) }
+func (cc changes) Swap(i, j int) { cc[i], cc[j] = cc[j], cc[i] }
+func (cc changes) Less(i, j int) bool { return strings.Compare(cc[i].String(), cc[j].String()) < 0 }
+
+func (cc changes) equals(other changes) bool {
+ sort.Sort(cc)
+ sort.Sort(other)
+ return reflect.DeepEqual(cc, other)
+}
+
+func (cc changes) String() string {
+ var buf bytes.Buffer
+ fmt.Fprintf(&buf, "len(%d) [", len(cc))
+ sep := ""
+ for _, c := range cc {
+ fmt.Fprintf(&buf, "%s%s", sep, c)
+ sep = ", "
+ }
+ buf.WriteByte(']')
+ return buf.String()
+}
+
+func (cc changes) reverse() changes {
+ ret := make(changes, len(cc))
+ for i, c := range cc {
+ ret[i] = c.reverse()
+ }
+
+ return ret
+}
+
+type changesEqualsChecker struct {
+ *CheckerInfo
+}
+
+var changesEquals Checker = &changesEqualsChecker{
+ &CheckerInfo{Name: "changesEquals", Params: []string{"obtained", "expected"}},
+}
+
+func (checker *changesEqualsChecker) Check(params []interface{}, names []string) (result bool, error string) {
+ a, ok := params[0].(changes)
+ if !ok {
+ return false, "first parameter must be a changes"
+ }
+ b, ok := params[1].(changes)
+ if !ok {
+ return false, "second parameter must be a changes"
+ }
+
+ return a.equals(b), ""
+}
+
+func do(c *C, list []diffTreeTest) {
+ for i, t := range list {
+ t.run(c, fmt.Sprintf("test #%d:", i))
+ }
+}
+
+func (s *DiffTreeSuite) TestEmptyVsEmpty(c *C) {
+ do(c, []diffTreeTest{
+ {"()", "()", ""},
+ {"A()", "A()", ""},
+ {"A()", "()", ""},
+ {"A()", "B()", ""},
+ })
+}
+
+func (s *DiffTreeSuite) TestBasicCases(c *C) {
+ do(c, []diffTreeTest{
+ {"()", "()", ""},
+ {"()", "(a<>)", "+a"},
+ {"()", "(a<1>)", "+a"},
+ {"()", "(a())", ""},
+ {"()", "(a(b()))", ""},
+ {"()", "(a(b<>))", "+a/b"},
+ {"()", "(a(b<1>))", "+a/b"},
+ {"(a<>)", "(a<>)", ""},
+ {"(a<>)", "(a<1>)", "*a"},
+ {"(a<>)", "(a())", "-a"},
+ {"(a<>)", "(a(b()))", "-a"},
+ {"(a<>)", "(a(b<>))", "-a +a/b"},
+ {"(a<>)", "(a(b<1>))", "-a +a/b"},
+ {"(a<>)", "(c())", "-a"},
+ {"(a<>)", "(c(b()))", "-a"},
+ {"(a<>)", "(c(b<>))", "-a +c/b"},
+ {"(a<>)", "(c(b<1>))", "-a +c/b"},
+ {"(a<>)", "(c(a()))", "-a"},
+ {"(a<>)", "(c(a<>))", "-a +c/a"},
+ {"(a<>)", "(c(a<1>))", "-a +c/a"},
+ {"(a<1>)", "(a<1>)", ""},
+ {"(a<1>)", "(a<2>)", "*a"},
+ {"(a<1>)", "(b<1>)", "-a +b"},
+ {"(a<1>)", "(b<2>)", "-a +b"},
+ {"(a<1>)", "(a())", "-a"},
+ {"(a<1>)", "(a(b()))", "-a"},
+ {"(a<1>)", "(a(b<>))", "-a +a/b"},
+ {"(a<1>)", "(a(b<1>))", "-a +a/b"},
+ {"(a<1>)", "(a(b<2>))", "-a +a/b"},
+ {"(a<1>)", "(c())", "-a"},
+ {"(a<1>)", "(c(b()))", "-a"},
+ {"(a<1>)", "(c(b<>))", "-a +c/b"},
+ {"(a<1>)", "(c(b<1>))", "-a +c/b"},
+ {"(a<1>)", "(c(b<2>))", "-a +c/b"},
+ {"(a<1>)", "(c())", "-a"},
+ {"(a<1>)", "(c(a()))", "-a"},
+ {"(a<1>)", "(c(a<>))", "-a +c/a"},
+ {"(a<1>)", "(c(a<1>))", "-a +c/a"},
+ {"(a<1>)", "(c(a<2>))", "-a +c/a"},
+ {"(a())", "(a())", ""},
+ {"(a())", "(b())", ""},
+ {"(a())", "(a(b()))", ""},
+ {"(a())", "(b(a()))", ""},
+ {"(a())", "(a(b<>))", "+a/b"},
+ {"(a())", "(a(b<1>))", "+a/b"},
+ {"(a())", "(b(a<>))", "+b/a"},
+ {"(a())", "(b(a<1>))", "+b/a"},
+ })
+}
+
+func (s *DiffTreeSuite) TestHorizontals(c *C) {
+ do(c, []diffTreeTest{
+ {"()", "(a<> b<>)", "+a +b"},
+ {"()", "(a<> b<1>)", "+a +b"},
+ {"()", "(a<> b())", "+a"},
+ {"()", "(a() b<>)", "+b"},
+ {"()", "(a<1> b<>)", "+a +b"},
+ {"()", "(a<1> b<1>)", "+a +b"},
+ {"()", "(a<1> b<2>)", "+a +b"},
+ {"()", "(a<1> b())", "+a"},
+ {"()", "(a() b<1>)", "+b"},
+ {"()", "(a() b())", ""},
+ {"()", "(a<> b<> c<> d<>)", "+a +b +c +d"},
+ {"()", "(a<> b<1> c() d<> e<2> f())", "+a +b +d +e"},
+ })
+}
+
+func (s *DiffTreeSuite) TestVerticals(c *C) {
+ do(c, []diffTreeTest{
+ {"()", "(z<>)", "+z"},
+ {"()", "(a(z<>))", "+a/z"},
+ {"()", "(a(b(z<>)))", "+a/b/z"},
+ {"()", "(a(b(c(z<>))))", "+a/b/c/z"},
+ {"()", "(a(b(c(d(z<>)))))", "+a/b/c/d/z"},
+ {"()", "(a(b(c(d(z<1>)))))", "+a/b/c/d/z"},
+ })
+}
+
+func (s *DiffTreeSuite) TestSingleInserts(c *C) {
+ do(c, []diffTreeTest{
+ {"()", "(z<>)", "+z"},
+ {"(a())", "(a(z<>))", "+a/z"},
+ {"(a())", "(a(b(z<>)))", "+a/b/z"},
+ {"(a(b(c())))", "(a(b(c(z<>))))", "+a/b/c/z"},
+ {"(a<> b<> c<>)", "(a<> b<> c<> z<>)", "+z"},
+ {"(a(b<> c<> d<>))", "(a(b<> c<> d<> z<>))", "+a/z"},
+ {"(a(b(c<> d<> e<>)))", "(a(b(c<> d<> e<> z<>)))", "+a/b/z"},
+ {"(a(b<>) f<>)", "(a(b<>) f<> z<>)", "+z"},
+ {"(a(b<>) f<>)", "(a(b<> z<>) f<>)", "+a/z"},
+ })
+}
+
+func (s *DiffTreeSuite) TestDebug(c *C) {
+ do(c, []diffTreeTest{
+ {"(a(b<>) f<>)", "(a(b<> z<>) f<>)", "+a/z"},
+ })
+}
+
+// root
+// / | \
+// / | ----
+// f d h --------
+// /\ / \ |
+// e a j b/ g
+// | / \ |
+// l n k icm
+// |
+// o
+// |
+// p/
+func (s *DiffTreeSuite) TestCrazy(c *C) {
+ crazy := "(f(e(l<1>) a(n(o(p())) k<1>)) d<1> h(j(i<1> c<2> m<>) b() g<>))"
+ do(c, []diffTreeTest{
+ {
+ crazy,
+ "()",
+ "-d -f/e/l -f/a/k -h/j/i -h/j/c -h/j/m -h/g",
+ }, {
+ crazy,
+ crazy,
+ "",
+ }, {
+ crazy,
+ "(d<1>)",
+ "-f/e/l -f/a/k -h/j/i -h/j/c -h/j/m -h/g",
+ }, {
+ crazy,
+ "(d<1> h(b() g<>))",
+ "-f/e/l -f/a/k -h/j/i -h/j/c -h/j/m",
+ }, {
+ crazy,
+ "(d<1> f(e(l()) a()) h(b() g<>))",
+ "-f/e/l -f/a/k -h/j/i -h/j/c -h/j/m",
+ }, {
+ crazy,
+ "(d<1> f(e(l<1>) a()) h(b() g<>))",
+ "-f/a/k -h/j/i -h/j/c -h/j/m",
+ }, {
+ crazy,
+ "(d<2> f(e(l<2>) a(s(t<1>))) h(b() g<> r<> j(i<> c<3> m<>)))",
+ "+f/a/s/t +h/r -f/a/k *d *f/e/l *h/j/c *h/j/i",
+ }, {
+ crazy,
+ "(f(e(l<2>) a(n(o(p<1>)) k<>)) h(j(i<1> c<2> m<>) b() g<>))",
+ "*f/e/l +f/a/n/o/p *f/a/k -d",
+ }, {
+ crazy,
+ "(f(e(l<1>) a(n(o(p(r<1>))) k<1>)) d<1> h(j(i<1> c<2> b() m<>) g<1>))",
+ "+f/a/n/o/p/r *h/g",
+ },
+ })
+}
+
+func (s *DiffTreeSuite) TestSameNames(c *C) {
+ do(c, []diffTreeTest{
+ {
+ "(a(a(a<>)))",
+ "(a(a(a<1>)))",
+ "*a/a/a",
+ }, {
+ "(a(b(a<>)))",
+ "(a(b(a<>)) b(a<>))",
+ "+b/a",
+ }, {
+ "(a(b(a<>)))",
+ "(a(b()) b(a<>))",
+ "-a/b/a +b/a",
+ },
+ })
+}
generated by cgit (git 2.34.1) at 2024-11-01 22:33:28 +0000