package merkletrie import ( "fmt" "io" "github.com/go-git/go-git/v5/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 }