package merkletrie_test import ( "bytes" ctx "context" "fmt" "reflect" "sort" "strings" "testing" "unicode" "gopkg.in/src-d/go-git.v4/utils/merkletrie" "gopkg.in/src-d/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) innerRunCtx(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.DiffTreeContext(ctx.Background(), 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) t.innerRunCtx(c, context, false) t.innerRunCtx(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", 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: 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", }, }) } func (s *DiffTreeSuite) TestIssue275(c *C) { do(c, []diffTreeTest{ { "(a(b(c.go<1>) b.go<2>))", "(a(b(c.go<1> d.go<3>) b.go<2>))", "+a/b/d.go", }, }) } func (s *DiffTreeSuite) TestIssue1057(c *C) { p1 := "TestAppWithUnicodéPath" p2 := "TestAppWithUnicodéPath" c.Assert(p1 == p2, Equals, false) do(c, []diffTreeTest{ { fmt.Sprintf("(%s(x.go<1>))", p1), fmt.Sprintf("(%s(x.go<1>) %s(x.go<1>))", p1, p2), fmt.Sprintf("+%s/x.go", p2), }, }) // swap p1 with p2 do(c, []diffTreeTest{ { fmt.Sprintf("(%s(x.go<1>))", p2), fmt.Sprintf("(%s(x.go<1>) %s(x.go<1>))", p1, p2), fmt.Sprintf("+%s/x.go", p1), }, }) } func (s *DiffTreeSuite) TestCancel(c *C) { t := diffTreeTest{"()", "(a<> b<1> c() d<> e<2> f())", "+a +b +d +e"} comment := Commentf("\n%s", "test cancel:") 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) comment = Commentf("%s\n\texpected = %s", comment.CheckCommentString(), expected) context, cancel := ctx.WithCancel(ctx.Background()) cancel() results, err := merkletrie.DiffTreeContext(context, a, b, fsnoder.HashEqual) c.Assert(results, IsNil, comment) c.Assert(err, ErrorMatches, "operation canceled") }