package difftree import ( "bytes" "fmt" "io" "sort" "strings" "srcd.works/go-git.v4/plumbing" "srcd.works/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("", 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 }