From 61c530655c44f3581738a497ce4d4175658d59c6 Mon Sep 17 00:00:00 2001 From: Máximo Cuadros Date: Fri, 5 Aug 2016 13:20:26 +0200 Subject: difftree changes to provide both files --- tree_diff.go | 205 ++++++++++++++++++++++++++++ tree_diff_test.go | 398 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 603 insertions(+) create mode 100644 tree_diff.go create mode 100644 tree_diff_test.go diff --git a/tree_diff.go b/tree_diff.go new file mode 100644 index 0000000..9c550dd --- /dev/null +++ b/tree_diff.go @@ -0,0 +1,205 @@ +package git + +import ( + "bytes" + "fmt" + "io" + "sort" + "strings" + + "gopkg.in/src-d/go-git.v3/core" +) + +type Action int + +func (a Action) String() string { + switch a { + case Insert: + return "Insert" + case Delete: + return "Delete" + case Modify: + return "Modify" + default: + panic(fmt.Sprintf("unsupported action: %d", a)) + } +} + +const ( + Insert Action = iota + Delete + Modify +) + +type Change struct { + Action + Name string + Files [2]*File +} + +func (c *Change) String() string { + return fmt.Sprintf("", c.Action, c.Name) +} + +type Changes []*Change + +func newEmpty() Changes { + return make([]*Change, 0, 0) +} + +func DiffTree(a, b *Tree) ([]*Change, error) { + if a == b { + return newEmpty(), nil + } + + if a == nil || b == nil { + return newWithEmpty(a, b) + } + + return newDiffTree(a, b) +} + +func (c Changes) Len() int { + return len(c) +} + +func (c Changes) Swap(i, j int) { + c[i], c[j] = c[j], c[i] +} + +func (c Changes) Less(i, j int) bool { + return strings.Compare(c[i].Name, c[j].Name) < 0 +} + +func (c Changes) String() string { + var buffer bytes.Buffer + buffer.WriteString("[") + comma := "" + for _, v := range c { + buffer.WriteString(comma) + buffer.WriteString(v.String()) + comma = ", " + } + buffer.WriteString("]") + + return buffer.String() +} + +func newWithEmpty(a, b *Tree) (Changes, error) { + changes := newEmpty() + + var action Action + var tree *Tree + if a == nil { + action = Insert + tree = b + } else { + action = Delete + tree = a + } + + iter := tree.Files() + defer iter.Close() + + for { + file, err := iter.Next() + if err == io.EOF { + break + } else if err != nil { + return nil, fmt.Errorf("cannot get next file: %s", err) + } + + var files [2]*File + if action == Insert { + files[1] = file + } else { + files[0] = file + } + + changes = append(changes, &Change{ + Action: action, + Name: file.Name, + Files: files, + }) + } + + return changes, nil +} + +// FIXME: this is very inefficient, but correct. +// The proper way to do this is to implement a diff-tree algorithm, +// while taking advantage of the tree hashes to avoid traversing +// subtrees when the hash is equal in both inputs. +func newDiffTree(a, b *Tree) ([]*Change, error) { + result := make([]*Change, 0) + + aChanges, err := newWithEmpty(a, nil) + if err != nil { + return nil, fmt.Errorf("cannot create nil-diff of source tree: %s", err) + } + sort.Sort(aChanges) + + bChanges, err := newWithEmpty(nil, b) + if err != nil { + return nil, fmt.Errorf("cannot create nil-diff of destination tree: %s", err) + } + sort.Sort(bChanges) + + for len(aChanges) > 0 && len(bChanges) > 0 { + switch comp := strings.Compare(aChanges[0].Name, bChanges[0].Name); { + case comp == 0: // append as "Modify" or ignore if not changed + modified, err := hasChange(a, b, aChanges[0].Name) + if err != nil { + return nil, err + } + + if modified { + result = append(result, &Change{ + Action: Modify, + Name: aChanges[0].Name, + Files: [2]*File{aChanges[0].Files[0], bChanges[0].Files[1]}, + }) + } + + aChanges = aChanges[1:] + bChanges = bChanges[1:] + case comp < 0: // delete first a change + result = append(result, aChanges[0]) + aChanges = aChanges[1:] + case comp > 0: // insert first b change + result = append(result, bChanges[0]) + bChanges = bChanges[1:] + } + } + + // append all remaining changes in aChanges, if any, as deletes + // append all remaining changes in bChanges, if any, as inserts + result = append(result, aChanges...) + result = append(result, bChanges...) + + return result, nil +} + +func hasChange(a, b *Tree, path string) (bool, error) { + ha, err := hash(a, path) + if err != nil { + return false, err + } + + hb, err := hash(b, path) + if err != nil { + return false, err + } + + return ha != hb, nil +} + +func hash(tree *Tree, path string) (core.Hash, error) { + file, err := tree.File(path) + if err != nil { + var empty core.Hash + return empty, fmt.Errorf("cannot find file %s in tree: %s", path, err) + } + + return file.Hash, nil +} diff --git a/tree_diff_test.go b/tree_diff_test.go new file mode 100644 index 0000000..93b9b74 --- /dev/null +++ b/tree_diff_test.go @@ -0,0 +1,398 @@ +package git + +import ( + "os" + "sort" + + "gopkg.in/src-d/go-git.v3/core" + "gopkg.in/src-d/go-git.v3/formats/packfile" + + . "gopkg.in/check.v1" +) + +type DiffTreeSuite struct { + repos map[string]*Repository +} + +var _ = Suite(&DiffTreeSuite{}) + +func (s *DiffTreeSuite) SetUpSuite(c *C) { + fixtureRepos := [...]struct { + url string + packfile string + }{ + {"git://github.com/github/gem-builder.git", + "fixtures/pack-1ea0b3971fd64fdcdf3282bfb58e8cf10095e4e6.pack"}, + {"git://github.com/githubtraining/example-branches.git", + "fixtures/pack-bb8ee94710d3fa39379a630f76812c187217b312.pack"}, + {"git://github.com/rumpkernel/rumprun-xen.git", + "fixtures/pack-7861f2632868833a35fe5e4ab94f99638ec5129b.pack"}, + {"git://github.com/mcuadros/skeetr.git", + "fixtures/pack-36ef7a2296bfd526020340d27c5e1faa805d8d38.pack"}, + {"git://github.com/dezfowler/LiteMock.git", + "fixtures/pack-0d9b6cfc261785837939aaede5986d7a7c212518.pack"}, + {"git://github.com/tyba/storable.git", + "fixtures/pack-0d3d824fb5c930e7e7e1f0f399f2976847d31fd3.pack"}, + {"git://github.com/toqueteos/ts3.git", + "fixtures/pack-21b33a26eb7ffbd35261149fe5d886b9debab7cb.pack"}, + } + + s.repos = make(map[string]*Repository, 0) + for _, fixRepo := range fixtureRepos { + s.repos[fixRepo.url] = NewPlainRepository() + + f, err := os.Open(fixRepo.packfile) + c.Assert(err, IsNil) + + r := packfile.NewSeekable(f) + d := packfile.NewDecoder(r) + err = d.Decode(s.repos[fixRepo.url].Storage) + c.Assert(err, IsNil) + + c.Assert(f.Close(), IsNil) + } +} + +func (s *DiffTreeSuite) TestActionString(c *C) { + expected := "Insert" + action := Insert + obtained := action.String() + c.Assert(obtained, Equals, expected) + + expected = "Delete" + action = Delete + obtained = action.String() + c.Assert(obtained, Equals, expected) + + expected = "Modify" + action = Modify + obtained = action.String() + c.Assert(obtained, Equals, expected) + + action = 37 + c.Assert(func() { action.String() }, + PanicMatches, "unsupported action: 37") +} + +func (s *DiffTreeSuite) TestChangeString(c *C) { + expected := "" + change := &Change{ + Action: Insert, + Name: "foo", + } + + obtained := change.String() + c.Assert(obtained, Equals, expected) +} + +func (s *DiffTreeSuite) TestChangesString(c *C) { + expected := "[]" + changes := newEmpty() + obtained := changes.String() + c.Assert(obtained, Equals, expected) + + expected = "[]" + changes = make([]*Change, 1) + changes[0] = &Change{Action: Modify, Name: "bla"} + obtained = changes.String() + c.Assert(obtained, Equals, expected) + + expected = "[, ]" + changes = make([]*Change, 2) + changes[0] = &Change{Action: Modify, Name: "bla"} + changes[1] = &Change{Action: Insert, Name: "foo/bar"} + obtained = changes.String() + c.Assert(obtained, Equals, expected) +} + +func (s *DiffTreeSuite) TestDiffTree(c *C) { + for i, t := range []struct { + repo string // the repo name as in localRepos + commit1 string // the commit of the first tree + commit2 string // the commit of the second tree + expected Changes // the expected list of changes + }{ + { + "git://github.com/dezfowler/LiteMock.git", + "", + "", + Changes{}, + }, + { + "git://github.com/dezfowler/LiteMock.git", + "b7965eaa2c4f245d07191fe0bcfe86da032d672a", + "b7965eaa2c4f245d07191fe0bcfe86da032d672a", + Changes{}, + }, + { + "git://github.com/dezfowler/LiteMock.git", + "", + "b7965eaa2c4f245d07191fe0bcfe86da032d672a", + Changes{ + {Action: Insert, Name: "README"}, + }, + }, + { + "git://github.com/dezfowler/LiteMock.git", + "b7965eaa2c4f245d07191fe0bcfe86da032d672a", + "", + Changes{ + {Action: Delete, Name: "README"}, + }, + }, + { + "git://github.com/githubtraining/example-branches.git", + "", + "f0eb272cc8f77803478c6748103a1450aa1abd37", + Changes{ + {Action: Insert, Name: "README.md"}, + }, + }, + { + "git://github.com/githubtraining/example-branches.git", + "f0eb272cc8f77803478c6748103a1450aa1abd37", + "", + Changes{ + {Action: Delete, Name: "README.md"}, + }, + }, + { + "git://github.com/githubtraining/example-branches.git", + "f0eb272cc8f77803478c6748103a1450aa1abd37", + "f0eb272cc8f77803478c6748103a1450aa1abd37", + Changes{}, + }, + { + "git://github.com/github/gem-builder.git", + "", + "9608eed92b3839b06ebf72d5043da547de10ce85", + Changes{ + {Action: Insert, Name: "README"}, + {Action: Insert, Name: "gem_builder.rb"}, + {Action: Insert, Name: "gem_eval.rb"}, + }, + }, + { + "git://github.com/github/gem-builder.git", + "9608eed92b3839b06ebf72d5043da547de10ce85", + "", + Changes{ + {Action: Delete, Name: "README"}, + {Action: Delete, Name: "gem_builder.rb"}, + {Action: Delete, Name: "gem_eval.rb"}, + }, + }, + { + "git://github.com/github/gem-builder.git", + "9608eed92b3839b06ebf72d5043da547de10ce85", + "9608eed92b3839b06ebf72d5043da547de10ce85", + Changes{}, + }, + { + "git://github.com/toqueteos/ts3.git", + "", + "764e914b75d6d6df1fc5d832aa9840f590abf1bb", + Changes{ + {Action: Insert, Name: "examples/bot.go"}, + {Action: Insert, Name: "examples/raw_shell.go"}, + {Action: Insert, Name: "helpers.go"}, + {Action: Insert, Name: "README.markdown"}, + {Action: Insert, Name: "ts3.go"}, + }, + }, + { + "git://github.com/toqueteos/ts3.git", + "764e914b75d6d6df1fc5d832aa9840f590abf1bb", + "", + Changes{ + {Action: Delete, Name: "examples/bot.go"}, + {Action: Delete, Name: "examples/raw_shell.go"}, + {Action: Delete, Name: "helpers.go"}, + {Action: Delete, Name: "README.markdown"}, + {Action: Delete, Name: "ts3.go"}, + }, + }, + { + "git://github.com/toqueteos/ts3.git", + "764e914b75d6d6df1fc5d832aa9840f590abf1bb", + "764e914b75d6d6df1fc5d832aa9840f590abf1bb", + Changes{}, + }, + { + "git://github.com/github/gem-builder.git", + "9608eed92b3839b06ebf72d5043da547de10ce85", + "6c41e05a17e19805879689414026eb4e279f7de0", + Changes{ + {Action: Modify, Name: "gem_eval.rb"}, + }, + }, + { + "git://github.com/github/gem-builder.git", + "6c41e05a17e19805879689414026eb4e279f7de0", + "89be3aac2f178719c12953cc9eaa23441f8d9371", + Changes{ + {Action: Modify, Name: "gem_eval.rb"}, + {Action: Insert, Name: "gem_eval_test.rb"}, + {Action: Insert, Name: "security.rb"}, + {Action: Insert, Name: "security_test.rb"}, + }, + }, + { + "git://github.com/github/gem-builder.git", + "89be3aac2f178719c12953cc9eaa23441f8d9371", + "597240b7da22d03ad555328f15abc480b820acc0", + Changes{ + {Action: Modify, Name: "gem_eval.rb"}, + }, + }, + { + "git://github.com/github/gem-builder.git", + "597240b7da22d03ad555328f15abc480b820acc0", + "0260380e375d2dd0e1a8fcab15f91ce56dbe778e", + Changes{ + {Action: Modify, Name: "gem_eval.rb"}, + {Action: Modify, Name: "gem_eval_test.rb"}, + {Action: Insert, Name: "lazy_dir.rb"}, + {Action: Insert, Name: "lazy_dir_test.rb"}, + {Action: Modify, Name: "security.rb"}, + {Action: Modify, Name: "security_test.rb"}, + }, + }, + { + "git://github.com/github/gem-builder.git", + "0260380e375d2dd0e1a8fcab15f91ce56dbe778e", + "597240b7da22d03ad555328f15abc480b820acc0", + Changes{ + {Action: Modify, Name: "gem_eval.rb"}, + {Action: Modify, Name: "gem_eval_test.rb"}, + {Action: Delete, Name: "lazy_dir.rb"}, + {Action: Delete, Name: "lazy_dir_test.rb"}, + {Action: Modify, Name: "security.rb"}, + {Action: Modify, Name: "security_test.rb"}, + }, + }, + { + "git://github.com/github/gem-builder.git", + "0260380e375d2dd0e1a8fcab15f91ce56dbe778e", + "ca9fd470bacb6262eb4ca23ee48bb2f43711c1ff", + Changes{ + {Action: Modify, Name: "gem_eval.rb"}, + {Action: Modify, Name: "security.rb"}, + {Action: Modify, Name: "security_test.rb"}, + }, + }, + { + "git://github.com/github/gem-builder.git", + "fe3c86745f887c23a0d38c85cfd87ca957312f86", + "b7e3f636febf7a0cd3ab473b6d30081786d2c5b6", + Changes{ + {Action: Modify, Name: "gem_eval.rb"}, + {Action: Modify, Name: "gem_eval_test.rb"}, + {Action: Insert, Name: "git_mock"}, + {Action: Modify, Name: "lazy_dir.rb"}, + {Action: Modify, Name: "lazy_dir_test.rb"}, + {Action: Modify, Name: "security.rb"}, + }, + }, + { + "git://github.com/rumpkernel/rumprun-xen.git", + "1831e47b0c6db750714cd0e4be97b5af17fb1eb0", + "51d8515578ea0c88cc8fc1a057903675cf1fc16c", + Changes{ + {Action: Modify, Name: "Makefile"}, + {Action: Modify, Name: "netbsd_init.c"}, + {Action: Modify, Name: "rumphyper_stubs.c"}, + {Action: Delete, Name: "sysproxy.c"}, + }, + }, + { + "git://github.com/rumpkernel/rumprun-xen.git", + "1831e47b0c6db750714cd0e4be97b5af17fb1eb0", + "e13e678f7ee9badd01b120889e0ec5fdc8ae3802", + Changes{ + {Action: Modify, Name: "app-tools/rumprun"}, + }, + }, + } { + repo, ok := s.repos[t.repo] + c.Assert(ok, Equals, true, + Commentf("subtest %d: repo %s not found", i, t.repo)) + + tree1, err := tree(repo, t.commit1) + c.Assert(err, IsNil, + Commentf("subtest %d: unable to retrieve tree from commit %s and repo %s: %s", i, t.commit1, t.repo, err)) + + var tree2 *Tree + if t.commit1 == t.commit2 { + tree2 = tree1 + } else { + tree2, err = tree(repo, t.commit2) + c.Assert(err, IsNil, + Commentf("subtest %d: unable to retrieve tree from commit %s and repo %s", i, t.commit2, t.repo, err)) + } + + obtained, err := DiffTree(tree1, tree2) + c.Assert(err, IsNil, + Commentf("subtest %d: unable to calculate difftree: %s", i, err)) + c.Assert(equalChanges(obtained, t.expected), Equals, true, + Commentf("subtest:%d\nrepo=%s\ncommit1=%s\ncommit2=%s\nexpected=%s\nobtained=%s", + i, t.repo, t.commit1, t.commit2, t.expected, obtained)) + + assertChanges(obtained, c) + } +} + +func assertChanges(a Changes, c *C) { + for _, changes := range a { + switch changes.Action { + case Insert: + c.Assert(changes.Files[0], IsNil) + c.Assert(changes.Files[1], NotNil) + case Delete: + c.Assert(changes.Files[0], NotNil) + c.Assert(changes.Files[1], IsNil) + case Modify: + c.Assert(changes.Files[0], NotNil) + c.Assert(changes.Files[1], NotNil) + } + } +} + +func equalChanges(a, b Changes) bool { + if a == nil && b == nil { + return true + } + + if a == nil || b == nil { + return false + } + + if len(a) != len(b) { + return false + } + + sort.Sort(a) + sort.Sort(b) + + for i, va := range a { + vb := b[i] + if va.Action != vb.Action || va.Name != vb.Name { + return false + } + } + + return true +} + +func tree(repo *Repository, commitHashStr string) (*Tree, error) { + if commitHashStr == "" { + return nil, nil + } + + commit, err := repo.Commit(core.NewHash(commitHashStr)) + if err != nil { + return nil, err + } + + return commit.Tree(), nil +} -- cgit