aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie/doubleiter.go
diff options
context:
space:
mode:
authorAlberto Cortés <alcortesm@gmail.com>2017-02-13 10:28:39 +0100
committerGitHub <noreply@github.com>2017-02-13 10:28:39 +0100
commit1fdfe887278bf1e6039215fa5f48e5b497c20bee (patch)
treeb11025cdf41f8eac57af54d6c8202290d78afe13 /utils/merkletrie/doubleiter.go
parent87a84b1cb90149cf81e76be46811341a30e4a367 (diff)
downloadgo-git-1fdfe887278bf1e6039215fa5f48e5b497c20bee.tar.gz
add difftree for noders (#262)
difftree for noders
Diffstat (limited to 'utils/merkletrie/doubleiter.go')
-rw-r--r--utils/merkletrie/doubleiter.go187
1 files changed, 187 insertions, 0 deletions
diff --git a/utils/merkletrie/doubleiter.go b/utils/merkletrie/doubleiter.go
new file mode 100644
index 0000000..6f5e538
--- /dev/null
+++ b/utils/merkletrie/doubleiter.go
@@ -0,0 +1,187 @@
+package merkletrie
+
+import (
+ "fmt"
+ "io"
+
+ "srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+// A doubleIter is a convenience type to keep track of the current
+// noders in two merkletries that are going to be iterated in parallel.
+// It has methods for:
+//
+// - iterating over the merkletries, both at the same time or
+// individually: nextFrom, nextTo, nextBoth, stepBoth
+//
+// - checking if there are noders left in one or both of them with the
+// remaining method and its associated returned type.
+//
+// - comparing the current noders of both merkletries in several ways,
+// with the compare method and its associated returned type.
+type doubleIter struct {
+ from struct {
+ iter *Iter
+ current noder.Path // nil if no more nodes
+ }
+ to struct {
+ iter *Iter
+ current noder.Path // nil if no more nodes
+ }
+ hashEqual noder.Equal
+}
+
+// NewdoubleIter returns a new doubleIter for the merkletries "from" and
+// "to". The hashEqual callback function will be used by the doubleIter
+// to compare the hash of the noders in the merkletries. The doubleIter
+// will be initialized to the first elements in each merkletrie if any.
+func newDoubleIter(from, to noder.Noder, hashEqual noder.Equal) (
+ *doubleIter, error) {
+ var ii doubleIter
+ var err error
+
+ if ii.from.iter, err = NewIter(from); err != nil {
+ return nil, fmt.Errorf("from: %s", err)
+ }
+ if ii.from.current, err = ii.from.iter.Next(); turnEOFIntoNil(err) != nil {
+ return nil, fmt.Errorf("from: %s", err)
+ }
+
+ if ii.to.iter, err = NewIter(to); err != nil {
+ return nil, fmt.Errorf("to: %s", err)
+ }
+ if ii.to.current, err = ii.to.iter.Next(); turnEOFIntoNil(err) != nil {
+ return nil, fmt.Errorf("to: %s", err)
+ }
+
+ ii.hashEqual = hashEqual
+
+ return &ii, nil
+}
+
+func turnEOFIntoNil(e error) error {
+ if e != nil && e != io.EOF {
+ return e
+ }
+ return nil
+}
+
+// NextBoth makes d advance to the next noder in both merkletries. If
+// any of them is a directory, it skips its contents.
+func (d *doubleIter) nextBoth() error {
+ if err := d.nextFrom(); err != nil {
+ return err
+ }
+ if err := d.nextTo(); err != nil {
+ return err
+ }
+
+ return nil
+}
+
+// NextFrom makes d advance to the next noder in the "from" merkletrie,
+// skipping its contents if it is a directory.
+func (d *doubleIter) nextFrom() (err error) {
+ d.from.current, err = d.from.iter.Next()
+ return turnEOFIntoNil(err)
+}
+
+// NextTo makes d advance to the next noder in the "to" merkletrie,
+// skipping its contents if it is a directory.
+func (d *doubleIter) nextTo() (err error) {
+ d.to.current, err = d.to.iter.Next()
+ return turnEOFIntoNil(err)
+}
+
+// StepBoth makes d advance to the next noder in both merkletries,
+// getting deeper into directories if that is the case.
+func (d *doubleIter) stepBoth() (err error) {
+ if d.from.current, err = d.from.iter.Step(); turnEOFIntoNil(err) != nil {
+ return err
+ }
+ if d.to.current, err = d.to.iter.Step(); turnEOFIntoNil(err) != nil {
+ return err
+ }
+ return nil
+}
+
+// Remaining returns if there are no more noders in the tree, if both
+// have noders or if one of them doesn't.
+func (d *doubleIter) remaining() remaining {
+ if d.from.current == nil && d.to.current == nil {
+ return noMoreNoders
+ }
+
+ if d.from.current == nil && d.to.current != nil {
+ return onlyToRemains
+ }
+
+ if d.from.current != nil && d.to.current == nil {
+ return onlyFromRemains
+ }
+
+ return bothHaveNodes
+}
+
+// Remaining values tells you whether both trees still have noders, or
+// only one of them or none of them.
+type remaining int
+
+const (
+ noMoreNoders remaining = iota
+ onlyToRemains
+ onlyFromRemains
+ bothHaveNodes
+)
+
+// Compare returns the comparison between the current elements in the
+// merkletries.
+func (d *doubleIter) compare() (s comparison, err error) {
+ s.sameHash = d.hashEqual(d.from.current, d.to.current)
+
+ fromIsDir := d.from.current.IsDir()
+ toIsDir := d.to.current.IsDir()
+
+ s.bothAreDirs = fromIsDir && toIsDir
+ s.bothAreFiles = !fromIsDir && !toIsDir
+ s.fileAndDir = !s.bothAreDirs && !s.bothAreFiles
+
+ fromNumChildren, err := d.from.current.NumChildren()
+ if err != nil {
+ return comparison{}, fmt.Errorf("from: %s", err)
+ }
+
+ toNumChildren, err := d.to.current.NumChildren()
+ if err != nil {
+ return comparison{}, fmt.Errorf("to: %s", err)
+ }
+
+ s.fromIsEmptyDir = fromIsDir && fromNumChildren == 0
+ s.toIsEmptyDir = toIsDir && toNumChildren == 0
+
+ return
+}
+
+// Answers to a lot of questions you can ask about how to noders are
+// equal or different.
+type comparison struct {
+ // the following are only valid if both nodes have the same name
+ // (i.e. nameComparison == 0)
+
+ // Do both nodes have the same hash?
+ sameHash bool
+ // Are both nodes files?
+ bothAreFiles bool
+
+ // the following are only valid if any of the noders are dirs,
+ // this is, if !bothAreFiles
+
+ // Is one a file and the other a dir?
+ fileAndDir bool
+ // Are both nodes dirs?
+ bothAreDirs bool
+ // Is the from node an empty dir?
+ fromIsEmptyDir bool
+ // Is the to Node an empty dir?
+ toIsEmptyDir bool
+}