diff options
| -rw-r--r-- | utils/difftree/difftree.go | 194 | ||||
| -rw-r--r-- | utils/difftree/difftree_test.go | 404 |
2 files changed, 0 insertions, 598 deletions
diff --git a/utils/difftree/difftree.go b/utils/difftree/difftree.go deleted file mode 100644 index e2cb9a5..0000000 --- a/utils/difftree/difftree.go +++ /dev/null @@ -1,194 +0,0 @@ -package difftree - -import ( - "bytes" - "fmt" - "io" - "sort" - "strings" - - "gopkg.in/src-d/go-git.v4" - "gopkg.in/src-d/go-git.v4/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 - File *git.File -} - -func (c *Change) String() string { - return fmt.Sprintf("<Action: %s, Path: %s, Size: %d>", c.Action, c.File.Name, c.File.Size) -} - -type Changes []*Change - -func newEmpty() Changes { - return make([]*Change, 0, 0) -} - -func New(a, b *git.Tree) (Changes, 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].File.Name, c[j].File.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 *git.Tree) (Changes, error) { - changes := newEmpty() - - var action Action - var tree *git.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) - } - - insert := &Change{ - Action: action, - File: file, - } - changes = append(changes, insert) - } - - 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 *git.Tree) (Changes, error) { - result := newEmpty() - - 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].File.Name, bChanges[0].File.Name); { - case comp == 0: // append as "Modify" or ignore if not changed - modified, err := hasChange(a, b, aChanges[0].File.Name) - if err != nil { - return nil, err - } - if modified { - bChanges[0].Action = Modify - result = append(result, bChanges[0]) - } else { - } - 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 *git.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 *git.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/utils/difftree/difftree_test.go b/utils/difftree/difftree_test.go deleted file mode 100644 index 767807c..0000000 --- a/utils/difftree/difftree_test.go +++ /dev/null @@ -1,404 +0,0 @@ -package difftree - -import ( - "os" - "sort" - "testing" - - "gopkg.in/src-d/go-git.v4" - "gopkg.in/src-d/go-git.v4/core" - "gopkg.in/src-d/go-git.v4/formats/packfile" - "gopkg.in/src-d/go-git.v4/storage/memory" - - . "gopkg.in/check.v1" -) - -func Test(t *testing.T) { TestingT(t) } - -type DiffTreeSuite struct { - repos map[string]*git.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]*git.Repository, 0) - for _, fixRepo := range fixtureRepos { - store := memory.NewStorage() - s.repos[fixRepo.url], _ = git.NewRepository(store) - - f, err := os.Open(fixRepo.packfile) - c.Assert(err, IsNil) - - r := packfile.NewSeekable(f) - d := packfile.NewDecoder(r) - - err = d.Decode(store.ObjectStorage()) - c.Assert(err, IsNil) - - c.Assert(f.Close(), IsNil) - } -} - -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.File.Name != vb.File.Name || - va.File.Size != vb.File.Size { - return false - } - } - - return true -} - -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 := "<Action: Insert, Path: bla, Size: 12>" - change := &Change{ - Action: Insert, - File: &git.File{Name: "bla", Blob: git.Blob{Size: 12}}, - } - obtained := change.String() - c.Assert(obtained, Equals, expected) - - expected = "<Action: Delete, Path: bla, Size: 12>" - change = &Change{ - Action: Delete, - File: &git.File{Name: "bla", Blob: git.Blob{Size: 12}}, - } - obtained = change.String() - c.Assert(obtained, Equals, expected) - - expected = "<Action: Modify, Path: bla, Size: 12>" - change = &Change{ - Action: Modify, - File: &git.File{Name: "bla", Blob: git.Blob{Size: 12}}, - } - 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 = "[<Action: Modify, Path: bla, Size: 12>]" - changes = make([]*Change, 1) - changes[0] = &Change{Action: Modify, File: &git.File{Name: "bla", Blob: git.Blob{Size: 12}}} - obtained = changes.String() - c.Assert(obtained, Equals, expected) - - expected = "[<Action: Modify, Path: bla, Size: 12>, <Action: Insert, Path: foo/bar, Size: 124>]" - changes = make([]*Change, 2) - changes[0] = &Change{Action: Modify, File: &git.File{Name: "bla", Blob: git.Blob{Size: 12}}} - changes[1] = &Change{Action: Insert, File: &git.File{Name: "foo/bar", Blob: git.Blob{Size: 124}}} - obtained = changes.String() - c.Assert(obtained, Equals, expected) -} - -func (s *DiffTreeSuite) TestNew(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, File: &git.File{Name: "README", Blob: git.Blob{Size: 0}}}, - }, - }, - { - "git://github.com/dezfowler/LiteMock.git", - "b7965eaa2c4f245d07191fe0bcfe86da032d672a", - "", - Changes{ - {Action: Delete, File: &git.File{Name: "README", Blob: git.Blob{Size: 0}}}, - }, - }, - { - "git://github.com/githubtraining/example-branches.git", - "", - "f0eb272cc8f77803478c6748103a1450aa1abd37", - Changes{ - {Action: Insert, File: &git.File{Name: "README.md", Blob: git.Blob{Size: 359}}}, - }, - }, - { - "git://github.com/githubtraining/example-branches.git", - "f0eb272cc8f77803478c6748103a1450aa1abd37", - "", - Changes{ - {Action: Delete, File: &git.File{Name: "README.md", Blob: git.Blob{Size: 359}}}, - }, - }, - { - "git://github.com/githubtraining/example-branches.git", - "f0eb272cc8f77803478c6748103a1450aa1abd37", - "f0eb272cc8f77803478c6748103a1450aa1abd37", - Changes{}, - }, - { - "git://github.com/github/gem-builder.git", - "", - "9608eed92b3839b06ebf72d5043da547de10ce85", - Changes{ - {Action: Insert, File: &git.File{Name: "README", Blob: git.Blob{Size: 1176}}}, - {Action: Insert, File: &git.File{Name: "gem_builder.rb", Blob: git.Blob{Size: 1956}}}, - {Action: Insert, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 687}}}, - }, - }, - { - "git://github.com/github/gem-builder.git", - "9608eed92b3839b06ebf72d5043da547de10ce85", - "", - Changes{ - {Action: Delete, File: &git.File{Name: "README", Blob: git.Blob{Size: 1176}}}, - {Action: Delete, File: &git.File{Name: "gem_builder.rb", Blob: git.Blob{Size: 1956}}}, - {Action: Delete, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 687}}}, - }, - }, - { - "git://github.com/github/gem-builder.git", - "9608eed92b3839b06ebf72d5043da547de10ce85", - "9608eed92b3839b06ebf72d5043da547de10ce85", - Changes{}, - }, - { - "git://github.com/toqueteos/ts3.git", - "", - "764e914b75d6d6df1fc5d832aa9840f590abf1bb", - Changes{ - {Action: Insert, File: &git.File{Name: "examples/bot.go", Blob: git.Blob{Size: 287}}}, - {Action: Insert, File: &git.File{Name: "examples/raw_shell.go", Blob: git.Blob{Size: 1269}}}, - {Action: Insert, File: &git.File{Name: "helpers.go", Blob: git.Blob{Size: 782}}}, - {Action: Insert, File: &git.File{Name: "README.markdown", Blob: git.Blob{Size: 34}}}, - {Action: Insert, File: &git.File{Name: "ts3.go", Blob: git.Blob{Size: 4251}}}, - }, - }, - { - "git://github.com/toqueteos/ts3.git", - "764e914b75d6d6df1fc5d832aa9840f590abf1bb", - "", - Changes{ - {Action: Delete, File: &git.File{Name: "examples/bot.go", Blob: git.Blob{Size: 287}}}, - {Action: Delete, File: &git.File{Name: "examples/raw_shell.go", Blob: git.Blob{Size: 1269}}}, - {Action: Delete, File: &git.File{Name: "helpers.go", Blob: git.Blob{Size: 782}}}, - {Action: Delete, File: &git.File{Name: "README.markdown", Blob: git.Blob{Size: 34}}}, - {Action: Delete, File: &git.File{Name: "ts3.go", Blob: git.Blob{Size: 4251}}}, - }, - }, - { - "git://github.com/toqueteos/ts3.git", - "764e914b75d6d6df1fc5d832aa9840f590abf1bb", - "764e914b75d6d6df1fc5d832aa9840f590abf1bb", - Changes{}, - }, - { - "git://github.com/github/gem-builder.git", - "9608eed92b3839b06ebf72d5043da547de10ce85", - "6c41e05a17e19805879689414026eb4e279f7de0", - Changes{ - {Action: Modify, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 1828}}}, - }, - }, - { - "git://github.com/github/gem-builder.git", - "6c41e05a17e19805879689414026eb4e279f7de0", - "89be3aac2f178719c12953cc9eaa23441f8d9371", - Changes{ - {Action: Modify, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 1247}}}, - {Action: Insert, File: &git.File{Name: "gem_eval_test.rb", Blob: git.Blob{Size: 2245}}}, - {Action: Insert, File: &git.File{Name: "security.rb", Blob: git.Blob{Size: 1361}}}, - {Action: Insert, File: &git.File{Name: "security_test.rb", Blob: git.Blob{Size: 875}}}, - }, - }, - { - "git://github.com/github/gem-builder.git", - "89be3aac2f178719c12953cc9eaa23441f8d9371", - "597240b7da22d03ad555328f15abc480b820acc0", - Changes{ - {Action: Modify, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 1221}}}, - }, - }, - { - "git://github.com/github/gem-builder.git", - "597240b7da22d03ad555328f15abc480b820acc0", - "0260380e375d2dd0e1a8fcab15f91ce56dbe778e", - Changes{ - {Action: Modify, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 1794}}}, - {Action: Modify, File: &git.File{Name: "gem_eval_test.rb", Blob: git.Blob{Size: 4220}}}, - {Action: Insert, File: &git.File{Name: "lazy_dir.rb", Blob: git.Blob{Size: 695}}}, - {Action: Insert, File: &git.File{Name: "lazy_dir_test.rb", Blob: git.Blob{Size: 1276}}}, - {Action: Modify, File: &git.File{Name: "security.rb", Blob: git.Blob{Size: 2134}}}, - {Action: Modify, File: &git.File{Name: "security_test.rb", Blob: git.Blob{Size: 1184}}}, - }, - }, - { - "git://github.com/github/gem-builder.git", - "0260380e375d2dd0e1a8fcab15f91ce56dbe778e", - "597240b7da22d03ad555328f15abc480b820acc0", - Changes{ - {Action: Modify, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 1221}}}, - {Action: Modify, File: &git.File{Name: "gem_eval_test.rb", Blob: git.Blob{Size: 2245}}}, - {Action: Delete, File: &git.File{Name: "lazy_dir.rb", Blob: git.Blob{Size: 695}}}, - {Action: Delete, File: &git.File{Name: "lazy_dir_test.rb", Blob: git.Blob{Size: 1276}}}, - {Action: Modify, File: &git.File{Name: "security.rb", Blob: git.Blob{Size: 1361}}}, - {Action: Modify, File: &git.File{Name: "security_test.rb", Blob: git.Blob{Size: 875}}}, - }, - }, - { - "git://github.com/github/gem-builder.git", - "0260380e375d2dd0e1a8fcab15f91ce56dbe778e", - "ca9fd470bacb6262eb4ca23ee48bb2f43711c1ff", - Changes{ - {Action: Modify, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 1768}}}, - {Action: Modify, File: &git.File{Name: "security.rb", Blob: git.Blob{Size: 2092}}}, - {Action: Modify, File: &git.File{Name: "security_test.rb", Blob: git.Blob{Size: 1180}}}, - }, - }, - { - "git://github.com/github/gem-builder.git", - "fe3c86745f887c23a0d38c85cfd87ca957312f86", - "b7e3f636febf7a0cd3ab473b6d30081786d2c5b6", - Changes{ - {Action: Modify, File: &git.File{Name: "gem_eval.rb", Blob: git.Blob{Size: 1696}}}, - {Action: Modify, File: &git.File{Name: "gem_eval_test.rb", Blob: git.Blob{Size: 4622}}}, - {Action: Insert, File: &git.File{Name: "git_mock", Blob: git.Blob{Size: 45}}}, - {Action: Modify, File: &git.File{Name: "lazy_dir.rb", Blob: git.Blob{Size: 921}}}, - {Action: Modify, File: &git.File{Name: "lazy_dir_test.rb", Blob: git.Blob{Size: 1617}}}, - {Action: Modify, File: &git.File{Name: "security.rb", Blob: git.Blob{Size: 2179}}}, - }, - }, - { - "git://github.com/rumpkernel/rumprun-xen.git", - "1831e47b0c6db750714cd0e4be97b5af17fb1eb0", - "51d8515578ea0c88cc8fc1a057903675cf1fc16c", - Changes{ - {Action: Modify, File: &git.File{Name: "Makefile", Blob: git.Blob{Size: 4166}}}, - {Action: Modify, File: &git.File{Name: "netbsd_init.c", Blob: git.Blob{Size: 953}}}, - {Action: Modify, File: &git.File{Name: "rumphyper_stubs.c", Blob: git.Blob{Size: 766}}}, - {Action: Delete, File: &git.File{Name: "sysproxy.c", Blob: git.Blob{Size: 47101}}}, - }, - }, - { - "git://github.com/rumpkernel/rumprun-xen.git", - "1831e47b0c6db750714cd0e4be97b5af17fb1eb0", - "e13e678f7ee9badd01b120889e0ec5fdc8ae3802", - Changes{ - {Action: Modify, File: &git.File{Name: "app-tools/rumprun", Blob: git.Blob{Size: 6492}}}, - }, - }, - } { - 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 *git.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 := New(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)) - } -} - -func tree(repo *git.Repository, commitHashStr string) (*git.Tree, error) { - if commitHashStr == "" { - return nil, nil - } - - commit, err := repo.Commit(core.NewHash(commitHashStr)) - if err != nil { - return nil, err - } - - return commit.Tree() -} |