aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/difftree/difftree.go
diff options
context:
space:
mode:
authorSantiago M. Mola <santi@mola.io>2016-12-14 23:12:44 +0100
committerMáximo Cuadros <mcuadros@gmail.com>2016-12-14 23:12:44 +0100
commit0af572dd21c0aa79d13745b633ee24ba6c4d6cf1 (patch)
tree49e81e74e82d84fd88b2fc1e4b0dc7c7bfe9c40f /plumbing/difftree/difftree.go
parentdf0f38af83f972f026d7e14150f3d37b95f13484 (diff)
downloadgo-git-0af572dd21c0aa79d13745b633ee24ba6c4d6cf1.tar.gz
move plumbing from top level package to plumbing (#183)
* plumbing: rename Object -> EncodedObject. * plumbing/storer: rename ObjectStorer -> EncodedObjectStorer. * move difftree to plumbing/difftree. * move diff -> utils/diff * make Object/Tag/Blob/Tree/Commit/File depend on storer. * Object and its implementations now depend only on storer.EncodedObjectStorer, not git.Repository. * Tests are decoupled accordingly. * move Object/Commit/File/Tag/Tree to plumbing/object. * move Object/Commit/File/Tag/Tree to plumbing/object. * move checkClose to utils/ioutil. * move RevListObjects to plumbing/revlist.Objects. * move DiffTree to plumbing/difftree package. * rename files with plural nouns to singular * plumbing/object: add GetBlob/GetCommit/GetTag/GetTree.
Diffstat (limited to 'plumbing/difftree/difftree.go')
-rw-r--r--plumbing/difftree/difftree.go253
1 files changed, 253 insertions, 0 deletions
diff --git a/plumbing/difftree/difftree.go b/plumbing/difftree/difftree.go
new file mode 100644
index 0000000..3bc4d63
--- /dev/null
+++ b/plumbing/difftree/difftree.go
@@ -0,0 +1,253 @@
+package git
+
+import (
+ "bytes"
+ "fmt"
+ "io"
+ "sort"
+ "strings"
+
+ "gopkg.in/src-d/go-git.v4/plumbing"
+ "gopkg.in/src-d/go-git.v4/plumbing/object"
+)
+
+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)
+
+ 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:]
+ }
+ }
+
+ // 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)
+ if err != nil {
+ var empty plumbing.Hash
+ return empty, fmt.Errorf("cannot find file %s in tree: %s", path, err)
+ }
+
+ return file.Hash, nil
+}