blob: e56dee701f2ae4c7d7a55315c4ea8a05d8620f6a [file] [log] [blame]
package merkletrie
import (
"fmt"
"io"
"gopkg.in/src-d/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
}