path: root/utils/merkletrie/doubleiter.go

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
}