remove old utils/difftree package. (#74)

Implementation is now in tree_diff.go.

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()
-}