aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/difftree
diff options
context:
space:
mode:
Diffstat (limited to 'plumbing/difftree')
-rw-r--r--plumbing/difftree/change.go121
-rw-r--r--plumbing/difftree/change_adaptor.go61
-rw-r--r--plumbing/difftree/change_adaptor_test.go413
-rw-r--r--plumbing/difftree/change_test.go300
-rw-r--r--plumbing/difftree/difftree.go246
-rw-r--r--plumbing/difftree/difftree_test.go523
-rw-r--r--plumbing/difftree/treenoder.go141
7 files changed, 1269 insertions, 536 deletions
diff --git a/plumbing/difftree/change.go b/plumbing/difftree/change.go
new file mode 100644
index 0000000..c636577
--- /dev/null
+++ b/plumbing/difftree/change.go
@@ -0,0 +1,121 @@
+package difftree
+
+import (
+ "bytes"
+ "fmt"
+ "strings"
+
+ "srcd.works/go-git.v4/plumbing/object"
+ "srcd.works/go-git.v4/utils/merkletrie"
+)
+
+// Change values represent a detected change between two git trees. For
+// modifications, From is the original status of the node and To is its
+// final status. For insertions, From is the zero value and for
+// deletions To is the zero value.
+type Change struct {
+ From ChangeEntry
+ To ChangeEntry
+}
+
+var empty = ChangeEntry{}
+
+// Action returns the kind of action represented by the change, an
+// insertion, a deletion or a modification.
+func (c *Change) Action() (merkletrie.Action, error) {
+ if c.From == empty && c.To == empty {
+ return merkletrie.Action(0),
+ fmt.Errorf("malformed change: empty from and to")
+ }
+ if c.From == empty {
+ return merkletrie.Insert, nil
+ }
+ if c.To == empty {
+ return merkletrie.Delete, nil
+ }
+
+ return merkletrie.Modify, nil
+}
+
+// Files return the files before and after a change.
+// For insertions from will be nil. For deletions to will be nil.
+func (c *Change) Files() (from, to *object.File, err error) {
+ action, err := c.Action()
+ if err != nil {
+ return
+ }
+
+ if action == merkletrie.Insert || action == merkletrie.Modify {
+ to, err = c.To.Tree.TreeEntryFile(&c.To.TreeEntry)
+ if err != nil {
+ return
+ }
+ }
+
+ if action == merkletrie.Delete || action == merkletrie.Modify {
+ from, err = c.From.Tree.TreeEntryFile(&c.From.TreeEntry)
+ if err != nil {
+ return
+ }
+ }
+
+ return
+}
+
+func (c *Change) String() string {
+ action, err := c.Action()
+ if err != nil {
+ return fmt.Sprintf("malformed change")
+ }
+
+ return fmt.Sprintf("<Action: %s, Path: %s>", action, c.name())
+}
+
+func (c *Change) name() string {
+ if c.From != empty {
+ return c.From.Name
+ }
+
+ return c.To.Name
+}
+
+// ChangeEntry values represent a node that has suffered a change.
+type ChangeEntry struct {
+ // Full path of the node using "/" as separator.
+ Name string
+ // Parent tree of the node that has changed.
+ Tree *object.Tree
+ // The entry of the node.
+ TreeEntry object.TreeEntry
+}
+
+// Changes represents a collection of changes between two git trees.
+// Implements sort.Interface lexicographically over the path of the
+// changed files.
+type Changes []*Change
+
+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()
+}
diff --git a/plumbing/difftree/change_adaptor.go b/plumbing/difftree/change_adaptor.go
new file mode 100644
index 0000000..edc20b3
--- /dev/null
+++ b/plumbing/difftree/change_adaptor.go
@@ -0,0 +1,61 @@
+package difftree
+
+// The folowing functions transform changes types form the merkletrie
+// package to changes types from this package.
+
+import (
+ "fmt"
+
+ "srcd.works/go-git.v4/plumbing/object"
+ "srcd.works/go-git.v4/utils/merkletrie"
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+func newChange(c merkletrie.Change) (*Change, error) {
+ ret := &Change{}
+
+ var err error
+ if ret.From, err = newChangeEntry(c.From); err != nil {
+ return nil, fmt.Errorf("From field: ", err)
+ }
+
+ if ret.To, err = newChangeEntry(c.To); err != nil {
+ return nil, fmt.Errorf("To field: ", err)
+ }
+
+ return ret, nil
+}
+
+func newChangeEntry(p noder.Path) (ChangeEntry, error) {
+ if p == nil {
+ return empty, nil
+ }
+
+ asTreeNoder, ok := p.Last().(*treeNoder)
+ if !ok {
+ return ChangeEntry{}, fmt.Errorf("cannot transform non-TreeNoders")
+ }
+
+ return ChangeEntry{
+ Name: p.String(),
+ Tree: asTreeNoder.parent,
+ TreeEntry: object.TreeEntry{
+ Name: asTreeNoder.name,
+ Mode: asTreeNoder.mode,
+ Hash: asTreeNoder.hash,
+ },
+ }, nil
+}
+
+func newChanges(src merkletrie.Changes) (Changes, error) {
+ ret := make(Changes, len(src))
+ var err error
+ for i, e := range src {
+ ret[i], err = newChange(e)
+ if err != nil {
+ return nil, fmt.Errorf("change #%d: %s", err)
+ }
+ }
+
+ return ret, nil
+}
diff --git a/plumbing/difftree/change_adaptor_test.go b/plumbing/difftree/change_adaptor_test.go
new file mode 100644
index 0000000..2ce2c54
--- /dev/null
+++ b/plumbing/difftree/change_adaptor_test.go
@@ -0,0 +1,413 @@
+package difftree
+
+import (
+ "os"
+ "sort"
+
+ "srcd.works/go-git.v4/plumbing"
+ "srcd.works/go-git.v4/plumbing/object"
+ "srcd.works/go-git.v4/plumbing/storer"
+ "srcd.works/go-git.v4/storage/filesystem"
+ "srcd.works/go-git.v4/utils/merkletrie"
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
+
+ "github.com/src-d/go-git-fixtures"
+ . "gopkg.in/check.v1"
+)
+
+type ChangeAdaptorSuite struct {
+ fixtures.Suite
+ Storer storer.EncodedObjectStorer
+ Fixture *fixtures.Fixture
+}
+
+func (s *ChangeAdaptorSuite) SetUpSuite(c *C) {
+ s.Suite.SetUpSuite(c)
+ s.Fixture = fixtures.Basic().One()
+ sto, err := filesystem.NewStorage(s.Fixture.DotGit())
+ c.Assert(err, IsNil)
+ s.Storer = sto
+}
+
+func (s *ChangeAdaptorSuite) tree(c *C, h plumbing.Hash) *object.Tree {
+ t, err := object.GetTree(s.Storer, h)
+ c.Assert(err, IsNil)
+ return t
+}
+
+var _ = Suite(&ChangeAdaptorSuite{})
+
+// utility function to build Noders from a tree and an tree entry.
+func newNoder(t *object.Tree, e object.TreeEntry) noder.Noder {
+ return &treeNoder{
+ parent: t,
+ name: e.Name,
+ mode: e.Mode,
+ hash: e.Hash,
+ }
+}
+
+// utility function to build Paths
+func newPath(nn ...noder.Noder) noder.Path { return noder.Path(nn) }
+
+func (s *ChangeAdaptorSuite) TestTreeNoderHashHasMode(c *C) {
+ hash := plumbing.NewHash("aaaa")
+ mode := object.FileMode
+
+ treeNoder := &treeNoder{
+ hash: hash,
+ mode: mode,
+ }
+
+ expected := []byte{
+ 0xaa, 0xaa, 0x00, 0x00, // original hash is aaaa and 16 zeros
+ 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00,
+ 0xa4, 0x81, 0x00, 0x00, // object.FileMode in little endian
+ }
+
+ c.Assert(treeNoder.Hash(), DeepEquals, expected)
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangeInsert(c *C) {
+ tree := &object.Tree{}
+ entry := object.TreeEntry{
+ Name: "name",
+ Mode: os.FileMode(42),
+ Hash: plumbing.NewHash("aaaaa"),
+ }
+ path := newPath(newNoder(tree, entry))
+
+ expectedTo, err := newChangeEntry(path)
+ c.Assert(err, IsNil)
+
+ src := merkletrie.Change{
+ From: nil,
+ To: path,
+ }
+
+ obtained, err := newChange(src)
+ c.Assert(err, IsNil)
+ action, err := obtained.Action()
+ c.Assert(err, IsNil)
+ c.Assert(action, Equals, merkletrie.Insert)
+ c.Assert(obtained.From, Equals, ChangeEntry{})
+ c.Assert(obtained.To, Equals, expectedTo)
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangeDelete(c *C) {
+ tree := &object.Tree{}
+ entry := object.TreeEntry{
+ Name: "name",
+ Mode: os.FileMode(42),
+ Hash: plumbing.NewHash("aaaaa"),
+ }
+ path := newPath(newNoder(tree, entry))
+
+ expectedFrom, err := newChangeEntry(path)
+ c.Assert(err, IsNil)
+
+ src := merkletrie.Change{
+ From: path,
+ To: nil,
+ }
+
+ obtained, err := newChange(src)
+ c.Assert(err, IsNil)
+ action, err := obtained.Action()
+ c.Assert(err, IsNil)
+ c.Assert(action, Equals, merkletrie.Delete)
+ c.Assert(obtained.From, Equals, expectedFrom)
+ c.Assert(obtained.To, Equals, ChangeEntry{})
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangeModify(c *C) {
+ treeA := &object.Tree{}
+ entryA := object.TreeEntry{
+ Name: "name",
+ Mode: os.FileMode(42),
+ Hash: plumbing.NewHash("aaaaa"),
+ }
+ pathA := newPath(newNoder(treeA, entryA))
+ expectedFrom, err := newChangeEntry(pathA)
+ c.Assert(err, IsNil)
+
+ treeB := &object.Tree{}
+ entryB := object.TreeEntry{
+ Name: "name",
+ Mode: os.FileMode(42),
+ Hash: plumbing.NewHash("bbbb"),
+ }
+ pathB := newPath(newNoder(treeB, entryB))
+ expectedTo, err := newChangeEntry(pathB)
+ c.Assert(err, IsNil)
+
+ src := merkletrie.Change{
+ From: pathA,
+ To: pathB,
+ }
+
+ obtained, err := newChange(src)
+ c.Assert(err, IsNil)
+ action, err := obtained.Action()
+ c.Assert(err, IsNil)
+ c.Assert(action, Equals, merkletrie.Modify)
+ c.Assert(obtained.From, Equals, expectedFrom)
+ c.Assert(obtained.To, Equals, expectedTo)
+}
+
+func (s *ChangeAdaptorSuite) TestEmptyChangeFails(c *C) {
+ change := &Change{
+ From: empty,
+ To: empty,
+ }
+ _, err := change.Action()
+ c.Assert(err, ErrorMatches, "malformed change.*")
+
+ _, _, err = change.Files()
+ c.Assert(err, ErrorMatches, "malformed change.*")
+
+ str := change.String()
+ c.Assert(str, Equals, "malformed change")
+}
+
+type noderMock struct{ noder.Noder }
+
+func (s *ChangeAdaptorSuite) TestNewChangeFailsWithChangesFromOtherNoders(c *C) {
+ src := merkletrie.Change{
+ From: newPath(noderMock{}),
+ To: nil,
+ }
+ _, err := newChange(src)
+ c.Assert(err, Not(IsNil))
+
+ src = merkletrie.Change{
+ From: nil,
+ To: newPath(noderMock{}),
+ }
+ _, err = newChange(src)
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestChangeStringFrom(c *C) {
+ expected := "<Action: Delete, Path: foo>"
+ change := Change{}
+ change.From.Name = "foo"
+
+ obtained := change.String()
+ c.Assert(obtained, Equals, expected)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeStringTo(c *C) {
+ expected := "<Action: Insert, Path: foo>"
+ change := Change{}
+ change.To.Name = "foo"
+
+ obtained := change.String()
+ c.Assert(obtained, Equals, expected)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesInsert(c *C) {
+ tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+ change := Change{}
+ change.To.Name = "json/long.json"
+ change.To.Tree = tree
+ change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+
+ from, to, err := change.Files()
+ c.Assert(err, IsNil)
+ c.Assert(from, IsNil)
+ c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesInsertNotFound(c *C) {
+ tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+ change := Change{}
+ change.To.Name = "json/long.json"
+ change.To.Tree = tree
+ // there is no object for this hash
+ change.To.TreeEntry.Hash = plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
+
+ _, _, err := change.Files()
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesDelete(c *C) {
+ tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+ change := Change{}
+ change.From.Name = "json/long.json"
+ change.From.Tree = tree
+ change.From.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+
+ from, to, err := change.Files()
+ c.Assert(err, IsNil)
+ c.Assert(to, IsNil)
+ c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesDeleteNotFound(c *C) {
+ tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+ change := Change{}
+ change.From.Name = "json/long.json"
+ change.From.Tree = tree
+ // there is no object for this hash
+ change.From.TreeEntry.Hash = plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
+
+ _, _, err := change.Files()
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesModify(c *C) {
+ tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+ change := Change{}
+ change.To.Name = "json/long.json"
+ change.To.Tree = tree
+ change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+ change.From.Name = "json/long.json"
+ change.From.Tree = tree
+ change.From.TreeEntry.Hash = plumbing.NewHash("9a48f23120e880dfbe41f7c9b7b708e9ee62a492")
+
+ from, to, err := change.Files()
+ c.Assert(err, IsNil)
+ c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
+ c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeEntryFailsWithOtherNoders(c *C) {
+ path := noder.Path{noderMock{}}
+ _, err := newChangeEntry(path)
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestChangeEntryFromNilIsZero(c *C) {
+ obtained, err := newChangeEntry(nil)
+ c.Assert(err, IsNil)
+ c.Assert(obtained, Equals, ChangeEntry{})
+}
+
+func (s *ChangeAdaptorSuite) TestChangeEntryFromSortPath(c *C) {
+ tree := &object.Tree{}
+ entry := object.TreeEntry{
+ Name: "name",
+ Mode: os.FileMode(42),
+ Hash: plumbing.NewHash("aaaaa"),
+ }
+ path := newPath(newNoder(tree, entry))
+
+ obtained, err := newChangeEntry(path)
+ c.Assert(err, IsNil)
+
+ c.Assert(obtained.Name, Equals, entry.Name)
+ c.Assert(obtained.Tree, Equals, tree)
+ c.Assert(obtained.TreeEntry, DeepEquals, entry)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeEntryFromLongPath(c *C) {
+ treeA := &object.Tree{}
+ entryA := object.TreeEntry{
+ Name: "nameA",
+ Mode: os.FileMode(42),
+ Hash: plumbing.NewHash("aaaa"),
+ }
+
+ treeB := &object.Tree{}
+ entryB := object.TreeEntry{
+ Name: "nameB",
+ Mode: os.FileMode(24),
+ Hash: plumbing.NewHash("bbbb"),
+ }
+
+ path := newPath(
+ newNoder(treeA, entryA),
+ newNoder(treeB, entryB),
+ )
+
+ obtained, err := newChangeEntry(path)
+ c.Assert(err, IsNil)
+
+ c.Assert(obtained.Name, Equals, entryA.Name+"/"+entryB.Name)
+ c.Assert(obtained.Tree, Equals, treeB)
+ c.Assert(obtained.TreeEntry, Equals, entryB)
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangesEmpty(c *C) {
+ expected := "[]"
+ changes, err := newChanges(nil)
+ c.Assert(err, IsNil)
+ obtained := changes.String()
+ c.Assert(obtained, Equals, expected)
+
+ expected = "[]"
+ changes, err = newChanges(merkletrie.Changes{})
+ c.Assert(err, IsNil)
+ obtained = changes.String()
+ c.Assert(obtained, Equals, expected)
+}
+
+func (s *ChangeAdaptorSuite) TestNewChanges(c *C) {
+ treeA := &object.Tree{}
+ entryA := object.TreeEntry{Name: "nameA"}
+ pathA := newPath(newNoder(treeA, entryA))
+ changeA := merkletrie.Change{
+ From: nil,
+ To: pathA,
+ }
+
+ treeB := &object.Tree{}
+ entryB := object.TreeEntry{Name: "nameB"}
+ pathB := newPath(newNoder(treeB, entryB))
+ changeB := merkletrie.Change{
+ From: pathB,
+ To: nil,
+ }
+ src := merkletrie.Changes{changeA, changeB}
+
+ changes, err := newChanges(src)
+ c.Assert(err, IsNil)
+ c.Assert(len(changes), Equals, 2)
+ action, err := changes[0].Action()
+ c.Assert(err, IsNil)
+ c.Assert(action, Equals, merkletrie.Insert)
+ c.Assert(changes[0].To.Name, Equals, "nameA")
+ action, err = changes[1].Action()
+ c.Assert(err, IsNil)
+ c.Assert(action, Equals, merkletrie.Delete)
+ c.Assert(changes[1].From.Name, Equals, "nameB")
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangesFailsWithOtherNoders(c *C) {
+ change := merkletrie.Change{
+ From: nil,
+ To: newPath(noderMock{}),
+ }
+ src := merkletrie.Changes{change}
+
+ _, err := newChanges(src)
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestSortChanges(c *C) {
+ c1 := &Change{}
+ c1.To.Name = "1"
+
+ c2 := &Change{}
+ c2.From.Name = "2"
+ c2.To.Name = "2"
+
+ c3 := &Change{}
+ c3.From.Name = "3"
+
+ changes := Changes{c3, c1, c2}
+ sort.Sort(changes)
+
+ c.Assert(changes[0].String(), Equals, "<Action: Insert, Path: 1>")
+ c.Assert(changes[1].String(), Equals, "<Action: Modify, Path: 2>")
+ c.Assert(changes[2].String(), Equals, "<Action: Delete, Path: 3>")
+}
diff --git a/plumbing/difftree/change_test.go b/plumbing/difftree/change_test.go
new file mode 100644
index 0000000..cda4ff9
--- /dev/null
+++ b/plumbing/difftree/change_test.go
@@ -0,0 +1,300 @@
+package difftree
+
+import (
+ "os"
+ "sort"
+
+ "srcd.works/go-git.v4/plumbing"
+ "srcd.works/go-git.v4/plumbing/object"
+ "srcd.works/go-git.v4/plumbing/storer"
+ "srcd.works/go-git.v4/storage/filesystem"
+ "srcd.works/go-git.v4/utils/merkletrie"
+
+ fixtures "github.com/src-d/go-git-fixtures"
+ . "gopkg.in/check.v1"
+)
+
+type ChangeSuite struct {
+ fixtures.Suite
+ Storer storer.EncodedObjectStorer
+ Fixture *fixtures.Fixture
+}
+
+func (s *ChangeSuite) SetUpSuite(c *C) {
+ s.Suite.SetUpSuite(c)
+ s.Fixture = fixtures.ByURL("https://github.com/src-d/go-git.git").
+ ByTag(".git").One()
+ sto, err := filesystem.NewStorage(s.Fixture.DotGit())
+ c.Assert(err, IsNil)
+ s.Storer = sto
+}
+
+func (s *ChangeSuite) tree(c *C, h plumbing.Hash) *object.Tree {
+ t, err := object.GetTree(s.Storer, h)
+ c.Assert(err, IsNil)
+ return t
+}
+
+var _ = Suite(&ChangeSuite{})
+
+func (s *ChangeSuite) TestInsert(c *C) {
+ // Commit a5078b19f08f63e7948abd0a5e2fb7d319d3a565 of the go-git
+ // fixture inserted "examples/clone/main.go".
+ //
+ // On that commit, the "examples/clone" tree is
+ // 6efca3ff41cab651332f9ebc0c96bb26be809615
+ //
+ // and the "examples/colone/main.go" is
+ // f95dc8f7923add1a8b9f72ecb1e8db1402de601a
+
+ path := "examples/clone/main.go"
+ name := "main.go"
+ mode := os.FileMode(100644)
+ blob := plumbing.NewHash("f95dc8f7923add1a8b9f72ecb1e8db1402de601a")
+ tree := plumbing.NewHash("6efca3ff41cab651332f9ebc0c96bb26be809615")
+
+ change := &Change{
+ From: empty,
+ To: ChangeEntry{
+ Name: path,
+ Tree: s.tree(c, tree),
+ TreeEntry: object.TreeEntry{
+ Name: name,
+ Mode: mode,
+ Hash: blob,
+ },
+ },
+ }
+
+ action, err := change.Action()
+ c.Assert(err, IsNil)
+ c.Assert(action, Equals, merkletrie.Insert)
+
+ from, to, err := change.Files()
+ c.Assert(err, IsNil)
+ c.Assert(from, IsNil)
+ c.Assert(to.Name, Equals, name)
+ c.Assert(to.Blob.Hash, Equals, blob)
+
+ str := change.String()
+ c.Assert(str, Equals, "<Action: Insert, Path: examples/clone/main.go>")
+}
+
+func (s *ChangeSuite) TestDelete(c *C) {
+ // Commit f6011d65d57c2a866e231fc21a39cb618f86f9ea of the go-git
+ // fixture deleted "utils/difftree/difftree.go".
+ //
+ // The parent of that commit is
+ // 9b4a386db3d98a4362516a00ef3d04d4698c9bcd.
+ //
+ // On that parent commit, the "utils/difftree" tree is
+ // f3d11566401ce4b0808aab9dd6fad3d5abf1481a.
+ //
+ // and the "utils/difftree/difftree.go" is
+ // e2cb9a5719daf634d45a063112b4044ee81da13ea.
+
+ path := "utils/difftree/difftree.go"
+ name := "difftree.go"
+ mode := os.FileMode(100644)
+ blob := plumbing.NewHash("e2cb9a5719daf634d45a063112b4044ee81da13e")
+ tree := plumbing.NewHash("f3d11566401ce4b0808aab9dd6fad3d5abf1481a")
+
+ change := &Change{
+ From: ChangeEntry{
+ Name: path,
+ Tree: s.tree(c, tree),
+ TreeEntry: object.TreeEntry{
+ Name: name,
+ Mode: mode,
+ Hash: blob,
+ },
+ },
+ To: empty,
+ }
+
+ action, err := change.Action()
+ c.Assert(err, IsNil)
+ c.Assert(action, Equals, merkletrie.Delete)
+
+ from, to, err := change.Files()
+ c.Assert(err, IsNil)
+ c.Assert(to, IsNil)
+ c.Assert(from.Name, Equals, name)
+ c.Assert(from.Blob.Hash, Equals, blob)
+
+ str := change.String()
+ c.Assert(str, Equals, "<Action: Delete, Path: utils/difftree/difftree.go>")
+}
+
+func (s *ChangeSuite) TestModify(c *C) {
+ // Commit 7beaad711378a4daafccc2c04bc46d36df2a0fd1 of the go-git
+ // fixture modified "examples/latest/latest.go".
+ // the "examples/latest" tree is
+ // b1f01b730b855c82431918cb338ad47ed558999b.
+ // and "examples/latest/latest.go" is blob
+ // 05f583ace3a9a078d8150905a53a4d82567f125f.
+ //
+ // The parent of that commit is
+ // 337148ef6d751477796922ac127b416b8478fcc4.
+ // the "examples/latest" tree is
+ // 8b0af31d2544acb5c4f3816a602f11418cbd126e.
+ // and "examples/latest/latest.go" is blob
+ // de927fad935d172929aacf20e71f3bf0b91dd6f9.
+
+ path := "utils/difftree/difftree.go"
+ name := "difftree.go"
+ mode := os.FileMode(100644)
+ fromBlob := plumbing.NewHash("05f583ace3a9a078d8150905a53a4d82567f125f")
+ fromTree := plumbing.NewHash("b1f01b730b855c82431918cb338ad47ed558999b")
+ toBlob := plumbing.NewHash("de927fad935d172929aacf20e71f3bf0b91dd6f9")
+ toTree := plumbing.NewHash("8b0af31d2544acb5c4f3816a602f11418cbd126e")
+
+ change := &Change{
+ From: ChangeEntry{
+ Name: path,
+ Tree: s.tree(c, fromTree),
+ TreeEntry: object.TreeEntry{
+ Name: name,
+ Mode: mode,
+ Hash: fromBlob,
+ },
+ },
+ To: ChangeEntry{
+ Name: path,
+ Tree: s.tree(c, toTree),
+ TreeEntry: object.TreeEntry{
+ Name: name,
+ Mode: mode,
+ Hash: toBlob,
+ },
+ },
+ }
+
+ action, err := change.Action()
+ c.Assert(err, IsNil)
+ c.Assert(action, Equals, merkletrie.Modify)
+
+ from, to, err := change.Files()
+ c.Assert(err, IsNil)
+
+ c.Assert(from.Name, Equals, name)
+ c.Assert(from.Blob.Hash, Equals, fromBlob)
+ c.Assert(to.Name, Equals, name)
+ c.Assert(to.Blob.Hash, Equals, toBlob)
+
+ str := change.String()
+ c.Assert(str, Equals, "<Action: Modify, Path: utils/difftree/difftree.go>")
+}
+
+func (s *ChangeSuite) TestEmptyChangeFails(c *C) {
+ change := &Change{}
+
+ _, err := change.Action()
+ c.Assert(err, ErrorMatches, "malformed.*")
+
+ _, _, err = change.Files()
+ c.Assert(err, ErrorMatches, "malformed.*")
+
+ str := change.String()
+ c.Assert(str, Equals, "malformed change")
+}
+
+func (s *ChangeSuite) TestErrorsFindingChildsAreDetected(c *C) {
+ // Commit 7beaad711378a4daafccc2c04bc46d36df2a0fd1 of the go-git
+ // fixture modified "examples/latest/latest.go".
+ // the "examples/latest" tree is
+ // b1f01b730b855c82431918cb338ad47ed558999b.
+ // and "examples/latest/latest.go" is blob
+ // 05f583ace3a9a078d8150905a53a4d82567f125f.
+ //
+ // The parent of that commit is
+ // 337148ef6d751477796922ac127b416b8478fcc4.
+ // the "examples/latest" tree is
+ // 8b0af31d2544acb5c4f3816a602f11418cbd126e.
+ // and "examples/latest/latest.go" is blob
+ // de927fad935d172929aacf20e71f3bf0b91dd6f9.
+
+ path := "utils/difftree/difftree.go"
+ name := "difftree.go"
+ mode := os.FileMode(100644)
+ fromBlob := plumbing.NewHash("aaaa") // does not exists
+ fromTree := plumbing.NewHash("b1f01b730b855c82431918cb338ad47ed558999b")
+ toBlob := plumbing.NewHash("bbbb") // does not exists
+ toTree := plumbing.NewHash("8b0af31d2544acb5c4f3816a602f11418cbd126e")
+
+ change := &Change{
+ From: ChangeEntry{
+ Name: path,
+ Tree: s.tree(c, fromTree),
+ TreeEntry: object.TreeEntry{
+ Name: name,
+ Mode: mode,
+ Hash: fromBlob,
+ },
+ },
+ To: ChangeEntry{},
+ }
+
+ _, _, err := change.Files()
+ c.Assert(err, ErrorMatches, "object not found")
+
+ change = &Change{
+ From: empty,
+ To: ChangeEntry{
+ Name: path,
+ Tree: s.tree(c, toTree),
+ TreeEntry: object.TreeEntry{
+ Name: name,
+ Mode: mode,
+ Hash: toBlob,
+ },
+ },
+ }
+
+ _, _, err = change.Files()
+ c.Assert(err, ErrorMatches, "object not found")
+}
+
+func (s *ChangeSuite) TestChangesString(c *C) {
+ expected := "[]"
+ changes := Changes{}
+ obtained := changes.String()
+ c.Assert(obtained, Equals, expected)
+
+ expected = "[<Action: Modify, Path: bla>]"
+ changes = make([]*Change, 1)
+ changes[0] = &Change{}
+ changes[0].From.Name = "bla"
+ changes[0].To.Name = "bla"
+
+ obtained = changes.String()
+ c.Assert(obtained, Equals, expected)
+
+ expected = "[<Action: Modify, Path: bla>, <Action: Delete, Path: foo/bar>]"
+ changes = make([]*Change, 2)
+ changes[0] = &Change{}
+ changes[0].From.Name = "bla"
+ changes[0].To.Name = "bla"
+ changes[1] = &Change{}
+ changes[1].From.Name = "foo/bar"
+ obtained = changes.String()
+ c.Assert(obtained, Equals, expected)
+}
+
+func (s *ChangeSuite) TestChangesSort(c *C) {
+ changes := make(Changes, 3)
+ changes[0] = &Change{}
+ changes[0].From.Name = "z"
+ changes[0].To.Name = "z"
+ changes[1] = &Change{}
+ changes[1].From.Name = "b/b"
+ changes[2] = &Change{}
+ changes[2].To.Name = "b/a"
+
+ expected := "[<Action: Insert, Path: b/a>, " +
+ "<Action: Delete, Path: b/b>, " +
+ "<Action: Modify, Path: z>]"
+
+ sort.Sort(changes)
+ c.Assert(changes.String(), Equals, expected)
+}
diff --git a/plumbing/difftree/difftree.go b/plumbing/difftree/difftree.go
index 869f496..76c5f27 100644
--- a/plumbing/difftree/difftree.go
+++ b/plumbing/difftree/difftree.go
@@ -2,252 +2,24 @@ package difftree
import (
"bytes"
- "fmt"
- "io"
- "sort"
- "strings"
- "srcd.works/go-git.v4/plumbing"
"srcd.works/go-git.v4/plumbing/object"
+ "srcd.works/go-git.v4/utils/merkletrie"
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
)
-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
- From ChangeEntry
- To ChangeEntry
-}
-
-type ChangeEntry struct {
- Name string
- Tree *object.Tree
- TreeEntry object.TreeEntry
-}
-
-func (c *Change) Files() (from, to *object.File, err error) {
- if c.Action == Insert || c.Action == Modify {
- to, err = c.To.Tree.TreeEntryFile(&c.To.TreeEntry)
- if err != nil {
- return
- }
-
- }
-
- if c.Action == Delete || c.Action == Modify {
- from, err = c.From.Tree.TreeEntryFile(&c.From.TreeEntry)
- if err != nil {
- return
- }
- }
-
- return
-}
-
-func (c *Change) String() string {
- return fmt.Sprintf("<Action: %s, Path: %s>", c.Action, c.name())
-}
-
-func (c *Change) name() string {
- if c.From.Name != "" {
- return c.From.Name
- }
-
- return c.To.Name
-}
-
-type Changes []*Change
-
-func newEmpty() Changes {
- return make([]*Change, 0, 0)
-}
-
func DiffTree(a, b *object.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 *object.Tree) (Changes, error) {
- changes := newEmpty()
-
- var action Action
- var tree *object.Tree
- if a == nil {
- action = Insert
- tree = b
- } else {
- action = Delete
- tree = a
- }
-
- w := object.NewTreeWalker(tree, true)
- defer w.Close()
-
- for {
- path, entry, err := w.Next()
- if err == io.EOF {
- break
- } else if err != nil {
- return nil, fmt.Errorf("cannot get next file: %s", err)
- }
-
- if entry.Mode.IsDir() {
- continue
- }
-
- c := &Change{Action: action}
-
- if action == Insert {
- c.To.Name = path
- c.To.TreeEntry = entry
- c.To.Tree = tree
- } else {
- c.From.Name = path
- c.From.TreeEntry = entry
- c.From.Tree = tree
- }
-
- changes = append(changes, c)
- }
-
- 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 *object.Tree) ([]*Change, error) {
- var result []*Change
-
- aChanges, err := newWithEmpty(a, nil)
- if err != nil {
- return nil, fmt.Errorf("cannot create nil-diff of source tree: %s", err)
- }
- sort.Sort(aChanges)
+ from := newTreeNoder(a)
+ to := newTreeNoder(b)
- 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 {
- c := mergeInsertAndDeleteIntoModify(aChanges[0], bChanges[0])
- result = append(result, c)
- }
-
- 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:]
- }
+ hashEqual := func(a, b noder.Hasher) bool {
+ return bytes.Equal(a.Hash(), b.Hash())
}
- // 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 mergeInsertAndDeleteIntoModify(a, b *Change) *Change {
- c := &Change{Action: Modify}
- c.From.Name = a.From.Name
- c.From.Tree = a.From.Tree
- c.From.TreeEntry = a.From.TreeEntry
- c.To.Name = b.To.Name
- c.To.Tree = b.To.Tree
- c.To.TreeEntry = b.To.TreeEntry
-
- return c
-}
-
-func hasChange(a, b *object.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 *object.Tree, path string) (plumbing.Hash, error) {
- file, err := tree.File(path)
+ merkletrieChanges, err := merkletrie.DiffTree(from, to, hashEqual)
if err != nil {
- var empty plumbing.Hash
- return empty, fmt.Errorf("cannot find file %s in tree: %s", path, err)
+ return nil, err
}
- return file.Hash, nil
+ return newChanges(merkletrieChanges)
}
diff --git a/plumbing/difftree/difftree_test.go b/plumbing/difftree/difftree_test.go
index 7679d0f..e2519b3 100644
--- a/plumbing/difftree/difftree_test.go
+++ b/plumbing/difftree/difftree_test.go
@@ -4,14 +4,15 @@ import (
"sort"
"testing"
- "github.com/src-d/go-git-fixtures"
"srcd.works/go-git.v4/plumbing"
"srcd.works/go-git.v4/plumbing/format/packfile"
"srcd.works/go-git.v4/plumbing/object"
"srcd.works/go-git.v4/plumbing/storer"
"srcd.works/go-git.v4/storage/filesystem"
"srcd.works/go-git.v4/storage/memory"
+ "srcd.works/go-git.v4/utils/merkletrie"
+ "github.com/src-d/go-git-fixtures"
. "gopkg.in/check.v1"
)
@@ -33,12 +34,6 @@ func (s *DiffTreeSuite) SetUpSuite(c *C) {
s.cache = make(map[string]storer.EncodedObjectStorer)
}
-func (s *DiffTreeSuite) tree(c *C, h plumbing.Hash) *object.Tree {
- t, err := object.GetTree(s.Storer, h)
- c.Assert(err, IsNil)
- return t
-}
-
func (s *DiffTreeSuite) commitFromStorer(c *C, sto storer.EncodedObjectStorer,
h plumbing.Hash) *object.Commit {
@@ -76,108 +71,48 @@ func (s *DiffTreeSuite) storageFromPackfile(f *fixtures.Fixture) storer.EncodedO
var _ = Suite(&DiffTreeSuite{})
-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) TestChangeFilesInsert(c *C) {
- tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
-
- change := &Change{Action: Insert}
- change.To.Name = "json/long.json"
- change.To.Tree = tree
- change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
-
- from, to, err := change.Files()
- c.Assert(err, IsNil)
- c.Assert(from, IsNil)
- c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
-}
-
-func (s *DiffTreeSuite) TestChangeFilesDelete(c *C) {
- tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
-
- change := &Change{Action: Delete}
- change.From.Name = "json/long.json"
- change.From.Tree = tree
- change.From.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
-
- from, to, err := change.Files()
- c.Assert(err, IsNil)
- c.Assert(to, IsNil)
- c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
-}
-
-func (s *DiffTreeSuite) TestChangeFilesModify(c *C) {
- tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
-
- change := &Change{Action: Modify}
- change.To.Name = "json/long.json"
- change.To.Tree = tree
- change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
- change.From.Name = "json/long.json"
- change.From.Tree = tree
- change.From.TreeEntry.Hash = plumbing.NewHash("9a48f23120e880dfbe41f7c9b7b708e9ee62a492")
-
- from, to, err := change.Files()
- c.Assert(err, IsNil)
- c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
- c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
+type expectChange struct {
+ Action merkletrie.Action
+ Name string
}
-func (s *DiffTreeSuite) TestChangeString(c *C) {
- expected := "<Action: Insert, Path: foo>"
- change := &Change{Action: Insert}
- change.From.Name = "foo"
-
- obtained := change.String()
- c.Assert(obtained, Equals, expected)
+func assertChanges(a Changes, c *C) {
+ for _, changes := range a {
+ action, err := changes.Action()
+ c.Assert(err, IsNil)
+ switch action {
+ case merkletrie.Insert:
+ c.Assert(changes.From.Tree, IsNil)
+ c.Assert(changes.To.Tree, NotNil)
+ case merkletrie.Delete:
+ c.Assert(changes.From.Tree, NotNil)
+ c.Assert(changes.To.Tree, IsNil)
+ case merkletrie.Modify:
+ c.Assert(changes.From.Tree, NotNil)
+ c.Assert(changes.To.Tree, NotNil)
+ default:
+ c.Fatalf("unknown action: %d", action)
+ }
+ }
}
-func (s *DiffTreeSuite) TestChangesString(c *C) {
- expected := "[]"
- changes := newEmpty()
- obtained := changes.String()
- c.Assert(obtained, Equals, expected)
-
- expected = "[<Action: Modify, Path: bla>]"
- changes = make([]*Change, 1)
- changes[0] = &Change{Action: Modify}
- changes[0].From.Name = "bla"
+func equalChanges(a Changes, b []expectChange, c *C) bool {
+ if len(a) != len(b) {
+ return false
+ }
- obtained = changes.String()
- c.Assert(obtained, Equals, expected)
+ sort.Sort(a)
- expected = "[<Action: Modify, Path: bla>, <Action: Insert, Path: foo/bar>]"
- changes = make([]*Change, 2)
- changes[0] = &Change{Action: Modify}
- changes[0].From.Name = "bla"
- changes[1] = &Change{Action: Insert}
- changes[1].From.Name = "foo/bar"
- obtained = changes.String()
- c.Assert(obtained, Equals, expected)
-}
+ for i, va := range a {
+ vb := b[i]
+ action, err := va.Action()
+ c.Assert(err, IsNil)
+ if action != vb.Action || va.name() != vb.Name {
+ return false
+ }
+ }
-type expectChange struct {
- Action Action
- Name string
+ return true
}
func (s *DiffTreeSuite) TestDiffTree(c *C) {
@@ -186,186 +121,209 @@ func (s *DiffTreeSuite) TestDiffTree(c *C) {
commit1 string // the commit of the first tree
commit2 string // the commit of the second tree
expected []expectChange // the expected list of []changeExpect
- }{{
- "https://github.com/dezfowler/LiteMock.git",
- "",
- "",
- []expectChange{},
- }, {
- "https://github.com/dezfowler/LiteMock.git",
- "b7965eaa2c4f245d07191fe0bcfe86da032d672a",
- "b7965eaa2c4f245d07191fe0bcfe86da032d672a",
- []expectChange{},
- }, {
- "https://github.com/dezfowler/LiteMock.git",
- "",
- "b7965eaa2c4f245d07191fe0bcfe86da032d672a",
- []expectChange{
- {Action: Insert, Name: "README"},
+ }{
+ {
+ "https://github.com/dezfowler/LiteMock.git",
+ "",
+ "",
+ []expectChange{},
+ },
+ {
+ "https://github.com/dezfowler/LiteMock.git",
+ "b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+ "b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+ []expectChange{},
+ },
+ {
+ "https://github.com/dezfowler/LiteMock.git",
+ "",
+ "b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+ []expectChange{
+ {Action: merkletrie.Insert, Name: "README"},
+ },
},
- }, {
- "https://github.com/dezfowler/LiteMock.git",
- "b7965eaa2c4f245d07191fe0bcfe86da032d672a",
- "",
- []expectChange{
- {Action: Delete, Name: "README"},
+ {
+ "https://github.com/dezfowler/LiteMock.git",
+ "b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+ "",
+ []expectChange{
+ {Action: merkletrie.Delete, Name: "README"},
+ },
},
- }, {
- "https://github.com/githubtraining/example-branches.git",
- "",
- "f0eb272cc8f77803478c6748103a1450aa1abd37",
- []expectChange{
- {Action: Insert, Name: "README.md"},
+ {
+ "https://github.com/githubtraining/example-branches.git",
+ "",
+ "f0eb272cc8f77803478c6748103a1450aa1abd37",
+ []expectChange{
+ {Action: merkletrie.Insert, Name: "README.md"},
+ },
},
- }, {
- "https://github.com/githubtraining/example-branches.git",
- "f0eb272cc8f77803478c6748103a1450aa1abd37",
- "",
- []expectChange{
- {Action: Delete, Name: "README.md"},
+ {
+ "https://github.com/githubtraining/example-branches.git",
+ "f0eb272cc8f77803478c6748103a1450aa1abd37",
+ "",
+ []expectChange{
+ {Action: merkletrie.Delete, Name: "README.md"},
+ },
},
- }, {
- "https://github.com/githubtraining/example-branches.git",
- "f0eb272cc8f77803478c6748103a1450aa1abd37",
- "f0eb272cc8f77803478c6748103a1450aa1abd37",
- []expectChange{},
- }, {
- "https://github.com/github/gem-builder.git",
- "",
- "9608eed92b3839b06ebf72d5043da547de10ce85",
- []expectChange{
- {Action: Insert, Name: "README"},
- {Action: Insert, Name: "gem_builder.rb"},
- {Action: Insert, Name: "gem_eval.rb"},
+ {
+ "https://github.com/githubtraining/example-branches.git",
+ "f0eb272cc8f77803478c6748103a1450aa1abd37",
+ "f0eb272cc8f77803478c6748103a1450aa1abd37",
+ []expectChange{},
},
- }, {
- "https://github.com/github/gem-builder.git",
- "9608eed92b3839b06ebf72d5043da547de10ce85",
- "",
- []expectChange{
- {Action: Delete, Name: "README"},
- {Action: Delete, Name: "gem_builder.rb"},
- {Action: Delete, Name: "gem_eval.rb"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "",
+ "9608eed92b3839b06ebf72d5043da547de10ce85",
+ []expectChange{
+ {Action: merkletrie.Insert, Name: "README"},
+ {Action: merkletrie.Insert, Name: "gem_builder.rb"},
+ {Action: merkletrie.Insert, Name: "gem_eval.rb"},
+ },
},
- }, {
- "https://github.com/github/gem-builder.git",
- "9608eed92b3839b06ebf72d5043da547de10ce85",
- "9608eed92b3839b06ebf72d5043da547de10ce85",
- []expectChange{},
- }, {
- "https://github.com/toqueteos/ts3.git",
- "",
- "764e914b75d6d6df1fc5d832aa9840f590abf1bb",
- []expectChange{
- {Action: Insert, Name: "README.markdown"},
- {Action: Insert, Name: "examples/bot.go"},
- {Action: Insert, Name: "examples/raw_shell.go"},
- {Action: Insert, Name: "helpers.go"},
- {Action: Insert, Name: "ts3.go"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "9608eed92b3839b06ebf72d5043da547de10ce85",
+ "",
+ []expectChange{
+ {Action: merkletrie.Delete, Name: "README"},
+ {Action: merkletrie.Delete, Name: "gem_builder.rb"},
+ {Action: merkletrie.Delete, Name: "gem_eval.rb"},
+ },
},
- }, {
- "https://github.com/toqueteos/ts3.git",
- "764e914b75d6d6df1fc5d832aa9840f590abf1bb",
- "",
- []expectChange{
- {Action: Delete, Name: "README.markdown"},
- {Action: Delete, Name: "examples/bot.go"},
- {Action: Delete, Name: "examples/raw_shell.go"},
- {Action: Delete, Name: "helpers.go"},
- {Action: Delete, Name: "ts3.go"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "9608eed92b3839b06ebf72d5043da547de10ce85",
+ "9608eed92b3839b06ebf72d5043da547de10ce85",
+ []expectChange{},
},
- }, {
- "https://github.com/toqueteos/ts3.git",
- "764e914b75d6d6df1fc5d832aa9840f590abf1bb",
- "764e914b75d6d6df1fc5d832aa9840f590abf1bb",
- []expectChange{},
- }, {
- "https://github.com/github/gem-builder.git",
- "9608eed92b3839b06ebf72d5043da547de10ce85",
- "6c41e05a17e19805879689414026eb4e279f7de0",
- []expectChange{
- {Action: Modify, Name: "gem_eval.rb"},
+ {
+ "https://github.com/toqueteos/ts3.git",
+ "",
+ "764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+ []expectChange{
+ {Action: merkletrie.Insert, Name: "README.markdown"},
+ {Action: merkletrie.Insert, Name: "examples/bot.go"},
+ {Action: merkletrie.Insert, Name: "examples/raw_shell.go"},
+ {Action: merkletrie.Insert, Name: "helpers.go"},
+ {Action: merkletrie.Insert, Name: "ts3.go"},
+ },
},
- }, {
- "https://github.com/github/gem-builder.git",
- "6c41e05a17e19805879689414026eb4e279f7de0",
- "89be3aac2f178719c12953cc9eaa23441f8d9371",
- []expectChange{
- {Action: Modify, Name: "gem_eval.rb"},
- {Action: Insert, Name: "gem_eval_test.rb"},
- {Action: Insert, Name: "security.rb"},
- {Action: Insert, Name: "security_test.rb"},
+ {
+ "https://github.com/toqueteos/ts3.git",
+ "764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+ "",
+ []expectChange{
+ {Action: merkletrie.Delete, Name: "README.markdown"},
+ {Action: merkletrie.Delete, Name: "examples/bot.go"},
+ {Action: merkletrie.Delete, Name: "examples/raw_shell.go"},
+ {Action: merkletrie.Delete, Name: "helpers.go"},
+ {Action: merkletrie.Delete, Name: "ts3.go"},
+ },
},
- }, {
- "https://github.com/github/gem-builder.git",
- "89be3aac2f178719c12953cc9eaa23441f8d9371",
- "597240b7da22d03ad555328f15abc480b820acc0",
- []expectChange{
- {Action: Modify, Name: "gem_eval.rb"},
+ {
+ "https://github.com/toqueteos/ts3.git",
+ "764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+ "764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+ []expectChange{},
},
- }, {
- "https://github.com/github/gem-builder.git",
- "597240b7da22d03ad555328f15abc480b820acc0",
- "0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
- []expectChange{
- {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"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "9608eed92b3839b06ebf72d5043da547de10ce85",
+ "6c41e05a17e19805879689414026eb4e279f7de0",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "gem_eval.rb"},
+ },
},
- }, {
- "https://github.com/github/gem-builder.git",
- "0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
- "597240b7da22d03ad555328f15abc480b820acc0",
- []expectChange{
- {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"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "6c41e05a17e19805879689414026eb4e279f7de0",
+ "89be3aac2f178719c12953cc9eaa23441f8d9371",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "gem_eval.rb"},
+ {Action: merkletrie.Insert, Name: "gem_eval_test.rb"},
+ {Action: merkletrie.Insert, Name: "security.rb"},
+ {Action: merkletrie.Insert, Name: "security_test.rb"},
+ },
},
- }, {
- "https://github.com/github/gem-builder.git",
- "0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
- "ca9fd470bacb6262eb4ca23ee48bb2f43711c1ff",
- []expectChange{
- {Action: Modify, Name: "gem_eval.rb"},
- {Action: Modify, Name: "security.rb"},
- {Action: Modify, Name: "security_test.rb"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "89be3aac2f178719c12953cc9eaa23441f8d9371",
+ "597240b7da22d03ad555328f15abc480b820acc0",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "gem_eval.rb"},
+ },
},
- }, {
- "https://github.com/github/gem-builder.git",
- "fe3c86745f887c23a0d38c85cfd87ca957312f86",
- "b7e3f636febf7a0cd3ab473b6d30081786d2c5b6",
- []expectChange{
- {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"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "597240b7da22d03ad555328f15abc480b820acc0",
+ "0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "gem_eval.rb"},
+ {Action: merkletrie.Modify, Name: "gem_eval_test.rb"},
+ {Action: merkletrie.Insert, Name: "lazy_dir.rb"},
+ {Action: merkletrie.Insert, Name: "lazy_dir_test.rb"},
+ {Action: merkletrie.Modify, Name: "security.rb"},
+ {Action: merkletrie.Modify, Name: "security_test.rb"},
+ },
},
- }, {
- "https://github.com/rumpkernel/rumprun-xen.git",
- "1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
- "51d8515578ea0c88cc8fc1a057903675cf1fc16c",
- []expectChange{
- {Action: Modify, Name: "Makefile"},
- {Action: Modify, Name: "netbsd_init.c"},
- {Action: Modify, Name: "rumphyper_stubs.c"},
- {Action: Delete, Name: "sysproxy.c"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+ "597240b7da22d03ad555328f15abc480b820acc0",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "gem_eval.rb"},
+ {Action: merkletrie.Modify, Name: "gem_eval_test.rb"},
+ {Action: merkletrie.Delete, Name: "lazy_dir.rb"},
+ {Action: merkletrie.Delete, Name: "lazy_dir_test.rb"},
+ {Action: merkletrie.Modify, Name: "security.rb"},
+ {Action: merkletrie.Modify, Name: "security_test.rb"},
+ },
},
- }, {
- "https://github.com/rumpkernel/rumprun-xen.git",
- "1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
- "e13e678f7ee9badd01b120889e0ec5fdc8ae3802",
- []expectChange{
- {Action: Modify, Name: "app-tools/rumprun"},
+ {
+ "https://github.com/github/gem-builder.git",
+ "0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+ "ca9fd470bacb6262eb4ca23ee48bb2f43711c1ff",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "gem_eval.rb"},
+ {Action: merkletrie.Modify, Name: "security.rb"},
+ {Action: merkletrie.Modify, Name: "security_test.rb"},
+ },
},
- }} {
+ {
+ "https://github.com/github/gem-builder.git",
+ "fe3c86745f887c23a0d38c85cfd87ca957312f86",
+ "b7e3f636febf7a0cd3ab473b6d30081786d2c5b6",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "gem_eval.rb"},
+ {Action: merkletrie.Modify, Name: "gem_eval_test.rb"},
+ {Action: merkletrie.Insert, Name: "git_mock"},
+ {Action: merkletrie.Modify, Name: "lazy_dir.rb"},
+ {Action: merkletrie.Modify, Name: "lazy_dir_test.rb"},
+ {Action: merkletrie.Modify, Name: "security.rb"},
+ },
+ },
+ {
+ "https://github.com/rumpkernel/rumprun-xen.git",
+ "1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
+ "51d8515578ea0c88cc8fc1a057903675cf1fc16c",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "Makefile"},
+ {Action: merkletrie.Modify, Name: "netbsd_init.c"},
+ {Action: merkletrie.Modify, Name: "rumphyper_stubs.c"},
+ {Action: merkletrie.Delete, Name: "sysproxy.c"},
+ },
+ },
+ {
+ "https://github.com/rumpkernel/rumprun-xen.git",
+ "1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
+ "e13e678f7ee9badd01b120889e0ec5fdc8ae3802",
+ []expectChange{
+ {Action: merkletrie.Modify, Name: "app-tools/rumprun"},
+ },
+ },
+ } {
f := fixtures.ByURL(t.repository).One()
sto := s.storageFromPackfile(f)
@@ -388,43 +346,10 @@ func (s *DiffTreeSuite) TestDiffTree(c *C) {
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,
+ c.Assert(equalChanges(obtained, t.expected, c), Equals, true,
Commentf("subtest:%d\nrepo=%s\ncommit1=%s\ncommit2=%s\nexpected=%s\nobtained=%s",
i, t.repository, 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.From.Tree, IsNil)
- c.Assert(changes.To.Tree, NotNil)
- case Delete:
- c.Assert(changes.From.Tree, NotNil)
- c.Assert(changes.To.Tree, IsNil)
- case Modify:
- c.Assert(changes.From.Tree, NotNil)
- c.Assert(changes.To.Tree, NotNil)
- }
- }
-}
-
-func equalChanges(a Changes, b []expectChange) bool {
- if len(a) != len(b) {
- return false
- }
-
- sort.Sort(a)
-
- for i, va := range a {
- vb := b[i]
- if va.Action != vb.Action || va.name() != vb.Name {
- return false
- }
- }
-
- return true
-}
diff --git a/plumbing/difftree/treenoder.go b/plumbing/difftree/treenoder.go
new file mode 100644
index 0000000..c0ed948
--- /dev/null
+++ b/plumbing/difftree/treenoder.go
@@ -0,0 +1,141 @@
+package difftree
+
+// A treenoder is a helper type that wraps git trees into merkletrie
+// noders.
+//
+// As a merkletrie noder doesn't understand the concept of modes (e.g.
+// file permissions), the treenoder includes the mode of the git tree in
+// the hash, so changes in the modes will be detected as modifications
+// to the file contents by the merkletrie difftree algorithm. This is
+// consistent with how the "git diff-tree" command works.
+import (
+ "encoding/binary"
+ "io"
+ "os"
+
+ "srcd.works/go-git.v4/plumbing"
+ "srcd.works/go-git.v4/plumbing/object"
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+type treeNoder struct {
+ parent *object.Tree // the root node is its own parent
+ name string // empty string for the root node
+ mode os.FileMode
+ hash plumbing.Hash
+ children []noder.Noder // memoized
+}
+
+func newTreeNoder(t *object.Tree) *treeNoder {
+ if t == nil {
+ return &treeNoder{}
+ }
+
+ return &treeNoder{
+ parent: t,
+ name: "",
+ mode: os.ModeDir,
+ hash: t.Hash,
+ }
+}
+
+func (t *treeNoder) isRoot() bool {
+ return t.name == ""
+}
+
+func (t *treeNoder) String() string {
+ return "treeNoder <" + t.name + ">"
+}
+
+func (t *treeNoder) Hash() []byte {
+ return append(t.hash[:], modeToBytes(t.mode)...)
+}
+
+// mode in little endian (endianess is an arbitrary decission).
+func modeToBytes(m os.FileMode) []byte {
+ ret := make([]byte, 4)
+ binary.LittleEndian.PutUint32(ret, uint32(m))
+ return ret
+}
+
+func (t *treeNoder) Name() string {
+ return t.name
+}
+
+func (t *treeNoder) IsDir() bool {
+ return t.mode.IsDir()
+}
+
+// Children will return the children of a treenoder as treenoders,
+// building them from the children of the wrapped git tree.
+func (t *treeNoder) Children() ([]noder.Noder, error) {
+ if !t.mode.IsDir() {
+ return noder.NoChildren, nil
+ }
+
+ // children are memoized for efficiency
+ if t.children != nil {
+ return t.children, nil
+ }
+
+ // the parent of the returned children will be ourself as a tree if
+ // we are a not the root treenoder. The root is special as it
+ // is is own parent.
+ parent := t.parent
+ if !t.isRoot() {
+ var err error
+ if parent, err = t.parent.Tree(t.name); err != nil {
+ return nil, err
+ }
+ }
+
+ return transformChildren(parent)
+}
+
+// Returns the children of a tree as treenoders.
+// Efficiency is key here.
+func transformChildren(t *object.Tree) ([]noder.Noder, error) {
+ var err error
+ var e object.TreeEntry
+
+ // there will be more tree entries than children in the tree,
+ // due to submodules and empty directories, but I think it is still
+ // worth it to pre-allocate the whole array now, even if sometimes
+ // is bigger than needed.
+ ret := make([]noder.Noder, 0, len(t.Entries))
+
+ walker := object.NewTreeWalker(t, false) // don't recurse
+ // don't defer walker.Close() for efficiency reasons.
+ for {
+ _, e, err = walker.Next()
+ if err == io.EOF {
+ break
+ }
+ if err != nil {
+ walker.Close()
+ return nil, err
+ }
+
+ ret = append(ret, &treeNoder{
+ parent: t,
+ name: e.Name,
+ mode: e.Mode,
+ hash: e.Hash,
+ })
+ }
+ walker.Close()
+
+ return ret, nil
+}
+
+// len(t.tree.Entries) != the number of elements walked by treewalker
+// for some reason because of empty directories, submodules, etc, so we
+// have to walk here.
+func (t *treeNoder) NumChildren() (int, error) {
+ children, err := t.Children()
+ if err != nil {
+ return 0, err
+ }
+
+ return len(children), nil
+}
generated by cgit (git 2.34.1) at 2024-11-10 07:25:17 +0000