From affc06dec90529073b5a3b76291b953232f034d9 Mon Sep 17 00:00:00 2001 From: Antonio Jesus Navarro Perez Date: Wed, 22 Feb 2017 15:49:37 +0100 Subject: plumbing/object: move difftree to object package - To avoid ciclic dependency errors, we move all the difftree files to object package. - Added Diff method to Tree object. --- plumbing/object/change.go | 120 ++++++++++ plumbing/object/change_adaptor.go | 60 +++++ plumbing/object/change_adaptor_test.go | 412 +++++++++++++++++++++++++++++++++ plumbing/object/change_test.go | 299 ++++++++++++++++++++++++ plumbing/object/difftree.go | 62 +++++ plumbing/object/difftree_test.go | 381 ++++++++++++++++++++++++++++++ plumbing/object/tree.go | 4 + plumbing/object/treenoder.go | 140 +++++++++++ 8 files changed, 1478 insertions(+) create mode 100644 plumbing/object/change.go create mode 100644 plumbing/object/change_adaptor.go create mode 100644 plumbing/object/change_adaptor_test.go create mode 100644 plumbing/object/change_test.go create mode 100644 plumbing/object/difftree.go create mode 100644 plumbing/object/difftree_test.go create mode 100644 plumbing/object/treenoder.go (limited to 'plumbing/object') diff --git a/plumbing/object/change.go b/plumbing/object/change.go new file mode 100644 index 0000000..5e32e5b --- /dev/null +++ b/plumbing/object/change.go @@ -0,0 +1,120 @@ +package object + +import ( + "bytes" + "fmt" + "strings" + + "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 *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, 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 *Tree + // The entry of the node. + TreeEntry 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/object/change_adaptor.go b/plumbing/object/change_adaptor.go new file mode 100644 index 0000000..e97fd93 --- /dev/null +++ b/plumbing/object/change_adaptor.go @@ -0,0 +1,60 @@ +package object + +import ( + "fmt" + + "srcd.works/go-git.v4/utils/merkletrie" + "srcd.works/go-git.v4/utils/merkletrie/noder" +) + +// The folowing functions transform changes types form the merkletrie +// package to changes types from this package. + +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: 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/object/change_adaptor_test.go b/plumbing/object/change_adaptor_test.go new file mode 100644 index 0000000..fb2636b --- /dev/null +++ b/plumbing/object/change_adaptor_test.go @@ -0,0 +1,412 @@ +package object + +import ( + "os" + "sort" + + "srcd.works/go-git.v4/plumbing" + "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) *Tree { + t, err := 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 *Tree, e 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 := 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 := &Tree{} + entry := 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 := &Tree{} + entry := 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 := &Tree{} + entryA := 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 := &Tree{} + entryB := 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 := "" + change := Change{} + change.From.Name = "foo" + + obtained := change.String() + c.Assert(obtained, Equals, expected) +} + +func (s *ChangeAdaptorSuite) TestChangeStringTo(c *C) { + expected := "" + 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 := &Tree{} + entry := 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 := &Tree{} + entryA := TreeEntry{ + Name: "nameA", + Mode: os.FileMode(42), + Hash: plumbing.NewHash("aaaa"), + } + + treeB := &Tree{} + entryB := 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 := &Tree{} + entryA := TreeEntry{Name: "nameA"} + pathA := newPath(newNoder(treeA, entryA)) + changeA := merkletrie.Change{ + From: nil, + To: pathA, + } + + treeB := &Tree{} + entryB := 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, "") + c.Assert(changes[1].String(), Equals, "") + c.Assert(changes[2].String(), Equals, "") +} diff --git a/plumbing/object/change_test.go b/plumbing/object/change_test.go new file mode 100644 index 0000000..b47e92a --- /dev/null +++ b/plumbing/object/change_test.go @@ -0,0 +1,299 @@ +package object + +import ( + "os" + "sort" + + "srcd.works/go-git.v4/plumbing" + "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) *Tree { + t, err := 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: 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, "") +} + +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: 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, "") +} + +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: TreeEntry{ + Name: name, + Mode: mode, + Hash: fromBlob, + }, + }, + To: ChangeEntry{ + Name: path, + Tree: s.tree(c, toTree), + TreeEntry: 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, "") +} + +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: 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: 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 = "[]" + 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 = "[, ]" + 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 := "[, " + + ", " + + "]" + + sort.Sort(changes) + c.Assert(changes.String(), Equals, expected) +} diff --git a/plumbing/object/difftree.go b/plumbing/object/difftree.go new file mode 100644 index 0000000..e6e0cb0 --- /dev/null +++ b/plumbing/object/difftree.go @@ -0,0 +1,62 @@ +package object + +import ( + "bytes" + "os" + + "srcd.works/go-git.v4/utils/merkletrie" + "srcd.works/go-git.v4/utils/merkletrie/noder" +) + +// DiffTree compares the content and mode of the blobs found via two +// tree objects. +func DiffTree(a, b *Tree) (Changes, error) { + from := newTreeNoder(a) + to := newTreeNoder(b) + + merkletrieChanges, err := merkletrie.DiffTree(from, to, hashEqual) + if err != nil { + return nil, err + } + + return newChanges(merkletrieChanges) +} + +// check if the hash of the contents is different, if not, check if +// the permissions are different (but taking into account deprecated +// file modes). On a treenoder, the hash of the contents is codified +// in the first 20 bytes of the data returned by Hash() and the last +// 4 bytes is the mode. +func hashEqual(a, b noder.Hasher) bool { + hashA, hashB := a.Hash(), b.Hash() + contentsA, contentsB := hashA[:20], hashB[:20] + + sameContents := bytes.Equal(contentsA, contentsB) + if !sameContents { + return false + } + + modeA, modeB := hashA[20:], hashB[20:] + + return equivalentMode(modeA, modeB) +} + +func equivalentMode(a, b []byte) bool { + if isFilish(a) && isFilish(b) { + return true + } + return bytes.Equal(a, b) +} + +var ( + file = modeToBytes(FileMode) + fileDeprecated = modeToBytes(FileModeDeprecated) + // remove this by fixing plumbing.Object mode ASAP + fileGoGit = modeToBytes(os.FileMode(0644)) +) + +func isFilish(b []byte) bool { + return bytes.Equal(b, file) || + bytes.Equal(b, fileDeprecated) || + bytes.Equal(b, fileGoGit) +} diff --git a/plumbing/object/difftree_test.go b/plumbing/object/difftree_test.go new file mode 100644 index 0000000..594c49d --- /dev/null +++ b/plumbing/object/difftree_test.go @@ -0,0 +1,381 @@ +package object + +import ( + "os" + "sort" + + "srcd.works/go-git.v4/plumbing" + "srcd.works/go-git.v4/plumbing/format/packfile" + "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" +) + +type DiffTreeSuite struct { + fixtures.Suite + Storer storer.EncodedObjectStorer + Fixture *fixtures.Fixture + cache map[string]storer.EncodedObjectStorer +} + +func (s *DiffTreeSuite) 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 + s.cache = make(map[string]storer.EncodedObjectStorer) +} + +func (s *DiffTreeSuite) commitFromStorer(c *C, sto storer.EncodedObjectStorer, + h plumbing.Hash) *Commit { + + commit, err := GetCommit(sto, h) + c.Assert(err, IsNil) + return commit +} + +func (s *DiffTreeSuite) storageFromPackfile(f *fixtures.Fixture) storer.EncodedObjectStorer { + sto, ok := s.cache[f.URL] + if ok { + return sto + } + + sto = memory.NewStorage() + + pf := f.Packfile() + + defer pf.Close() + + n := packfile.NewScanner(pf) + d, err := packfile.NewDecoder(n, sto) + if err != nil { + panic(err) + } + + _, err = d.Decode() + if err != nil { + panic(err) + } + + s.cache[f.URL] = sto + return sto +} + +var _ = Suite(&DiffTreeSuite{}) + +type expectChange struct { + Action merkletrie.Action + Name string +} + +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 equalChanges(a Changes, b []expectChange, c *C) bool { + if len(a) != len(b) { + return false + } + + sort.Sort(a) + + 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 + } + } + + return true +} + +func (s *DiffTreeSuite) TestDiffTree(c *C) { + for i, t := range []struct { + repository string // the repo name as in localRepos + 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: merkletrie.Insert, 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: merkletrie.Insert, 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: 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", + "", + []expectChange{ + {Action: merkletrie.Delete, Name: "README"}, + {Action: merkletrie.Delete, Name: "gem_builder.rb"}, + {Action: merkletrie.Delete, Name: "gem_eval.rb"}, + }, + }, + { + "https://github.com/github/gem-builder.git", + "9608eed92b3839b06ebf72d5043da547de10ce85", + "9608eed92b3839b06ebf72d5043da547de10ce85", + []expectChange{}, + }, + { + "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/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/toqueteos/ts3.git", + "764e914b75d6d6df1fc5d832aa9840f590abf1bb", + "764e914b75d6d6df1fc5d832aa9840f590abf1bb", + []expectChange{}, + }, + { + "https://github.com/github/gem-builder.git", + "9608eed92b3839b06ebf72d5043da547de10ce85", + "6c41e05a17e19805879689414026eb4e279f7de0", + []expectChange{ + {Action: merkletrie.Modify, Name: "gem_eval.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", + "89be3aac2f178719c12953cc9eaa23441f8d9371", + "597240b7da22d03ad555328f15abc480b820acc0", + []expectChange{ + {Action: merkletrie.Modify, Name: "gem_eval.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/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/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) + + var tree1, tree2 *Tree + var err error + if t.commit1 != "" { + tree1, err = s.commitFromStorer(c, sto, + plumbing.NewHash(t.commit1)).Tree() + c.Assert(err, IsNil, + Commentf("subtest %d: unable to retrieve tree from commit %s and repo %s: %s", i, t.commit1, t.repository, err)) + } + + if t.commit2 != "" { + tree2, err = s.commitFromStorer(c, sto, + plumbing.NewHash(t.commit2)).Tree() + c.Assert(err, IsNil, + Commentf("subtest %d: unable to retrieve tree from commit %s and repo %s", i, t.commit2, t.repository, err)) + } + + obtained, err := DiffTree(tree1, tree2) + c.Assert(err, IsNil, + Commentf("subtest %d: unable to calculate difftree: %s", i, err)) + obtainedFromMethod, err := tree1.Diff(tree2) + c.Assert(err, IsNil, + Commentf("subtest %d: unable to calculate difftree: %s. Result calling Diff method from Tree object returns an error", i, err)) + + c.Assert(obtained, DeepEquals, obtainedFromMethod) + + 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 (s *DiffTreeSuite) TestIssue279(c *C) { + // HashEqual should ignore files if the only change is from a 100664 + // mode to a 100644 or vice versa. + from := &treeNoder{ + hash: plumbing.NewHash("d08e895238bac36d8220586fdc28c27e1a7a76d3"), + mode: os.FileMode(0100664), + } + to := &treeNoder{ + hash: plumbing.NewHash("d08e895238bac36d8220586fdc28c27e1a7a76d3"), + mode: os.FileMode(0100644), + } + c.Assert(hashEqual(from, to), Equals, true) + c.Assert(hashEqual(to, from), Equals, true) + + // but should detect if the contents of the file also changed. + to = &treeNoder{ + hash: plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"), + mode: os.FileMode(0100644), + } + c.Assert(hashEqual(from, to), Equals, false) + c.Assert(hashEqual(to, from), Equals, false) +} diff --git a/plumbing/object/tree.go b/plumbing/object/tree.go index 436ac32..d39c315 100644 --- a/plumbing/object/tree.go +++ b/plumbing/object/tree.go @@ -299,6 +299,10 @@ func (t *Tree) buildMap() { } } +func (from *Tree) Diff(to *Tree) (Changes, error) { + return DiffTree(from, to) +} + // treeEntryIter facilitates iterating through the TreeEntry objects in a Tree. type treeEntryIter struct { t *Tree diff --git a/plumbing/object/treenoder.go b/plumbing/object/treenoder.go new file mode 100644 index 0000000..73d96e2 --- /dev/null +++ b/plumbing/object/treenoder.go @@ -0,0 +1,140 @@ +package object + +// 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/utils/merkletrie/noder" +) + +type treeNoder struct { + parent *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 *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 *Tree) ([]noder.Noder, error) { + var err error + var e 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 := 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 +} -- cgit From cb51ef358e081b5214e3884bd618d1d3fedf8eb1 Mon Sep 17 00:00:00 2001 From: Antonio Jesus Navarro Perez Date: Wed, 22 Feb 2017 17:34:25 +0100 Subject: Added documentation to Diff method --- plumbing/object/tree.go | 1 + 1 file changed, 1 insertion(+) (limited to 'plumbing/object') diff --git a/plumbing/object/tree.go b/plumbing/object/tree.go index d39c315..ef5e140 100644 --- a/plumbing/object/tree.go +++ b/plumbing/object/tree.go @@ -299,6 +299,7 @@ func (t *Tree) buildMap() { } } +// Diff returns a list of changes between this tree and the provided one func (from *Tree) Diff(to *Tree) (Changes, error) { return DiffTree(from, to) } -- cgit