path: root/fi-prune-empty2/prune.go

package main

import (
	"fmt"

	"github.com/pkg/errors"
	"github.com/spf13/pflag"

	"git.lukeshu.com/go/libfastimport"
)

type PruneArg int

const (
	PruneNever PruneArg = iota
	PruneAuto
	PruneAlways
)

func (a *PruneArg) String() string {
	switch *a {
	case PruneNever:
		return "never"
	case PruneAuto:
		return "auto"
	case PruneAlways:
		return "always"
	default:
		panic("not reached")
	}
}

func (a *PruneArg) Set(str string) error {
	switch str {
	case "never":
		*a = PruneNever
	case "auto":
		*a = PruneAuto
	case "always":
		*a = PruneAlways
	default:
		return errors.Errorf("valid values are %q, got %q", []string{"never", "auto", "always"}, str)
	}
	return nil
}
func (a *PruneArg) Type() string {
	return "{never|auto|always}"
}

var _ pflag.Value = (*PruneArg)(nil)

type Pruner struct {
	pruneEmpty       PruneArg
	pruneFastForward PruneArg
	existingReplace  ExistingReplaceArg
	newReplace       NewReplaceArg

	srcRepo   *GitRepo
	dstStream *libfastimport.Backend

	replace map[Mark]Mark

	ancestors map[Mark]map[Mark]struct{} // all ancestors, not just immediate parents
	tree      map[Mark]Tree

	newhash2mark map[Hash]Mark
}

func NewPruner(
	pruneEmpty, pruneFastForward PruneArg,
	srcdir string, dst *libfastimport.Backend,
) *Pruner {
	return &Pruner{
		pruneEmpty:       pruneEmpty,
		pruneFastForward: pruneFastForward,

		srcRepo:   &GitRepo{Dir: srcdir},
		dstStream: dst,

		replace: make(map[Mark]Mark),

		ancestors: make(map[Mark]map[Mark]struct{}),
		tree:      make(map[Mark]Tree),

		newhash2mark: make(map[Hash]Mark),
	}
}

func (p *Pruner) debug(msg string) {
	p.dstStream.Do(libfastimport.CmdComment{
		Comment: " " + msg,
	})
}

func (p *Pruner) GotMark(mark Mark, hash Hash) bool {
	if omark, ok := p.newhash2mark[hash]; ok {
		p.replace[mark] = omark
		delete(p.tree, mark)
		return false
	}
	p.newhash2mark[hash] = mark
	return true
}

func (p *Pruner) FixCommitIsh(str string) string {
	mark, err := AsMark(str)
	if err != nil {
		return str
	}
	mark = p.FixMark(mark)
	if mark < 0 {
		return ""
	}
	return fmt.Sprintf(":%d", mark)
}

func (p *Pruner) FixMark(mark Mark) Mark {
	for {
		rmark, ok := p.replace[mark]
		if ok {
			mark = rmark
		} else {
			break
		}
	}
	return mark
}

func (p *Pruner) ProcessCommit(commit Commit) (*Commit, error) {
	shouldPrune, err := p.shouldPrune(commit)
	if err != nil {
		return nil, err
	}
	if shouldPrune {
		commit.Parents = p.pruneParents(commit.Parents)
		if len(commit.Parents) == 0 {
			p.replace[commit.Mark] = -1
		} else {
			p.replace[commit.Mark] = commit.Parents[0]
		}
		return nil, nil
	}

	ancestors := map[Mark]struct{}{}
	for _, parent := range commit.Parents {
		ancestors[parent] = struct{}{}
		for ancestor := range p.ancestors[parent] {
			ancestors[ancestor] = struct{}{}
		}
	}
	p.ancestors[commit.Mark] = ancestors
	p.tree[commit.Mark] = commit.Tree

	return &commit, nil
}

func (p *Pruner) wasEmpty(commit Commit) (bool, error) {
	commitHash := commit.OriginalOID
	// git rev-parse commit^@
	parents, err := p.srcRepo.Parents(commitHash)
	if err != nil {
		return false, err
	}
	if len(parents) != 1 {
		return false, nil
	}
	// git rev-parse commit^{tree}
	tree, err := p.srcRepo.Tree(commitHash)
	if err != nil {
		return false, err
	}
	// git rev-parse parent^{tree}
	parentTree, err := p.srcRepo.Tree(parents[0])
	if err != nil {
		return false, err
	}
	return (tree == parentTree), nil
}

func (p *Pruner) wasFastForward(commit Commit) (bool, error) {
	commitHash := commit.OriginalOID
	// git rev-parse commit^@
	parents, err := p.srcRepo.Parents(commitHash)
	if err != nil {
		return false, err
	}
	if len(parents) < 2 {
		return false, nil
	}
	// git merge-base --independent parents
	independentParentsBytes, err := p.srcRepo.Cmd(append([]string{"merge-base", "--independent"}, AsArgs(parents...)...)...).Output()
	if err != nil {
		return false, err
	}
	independentParents, err := LinesAsHashes(independentParentsBytes)
	if err != nil {
		return false, err
	}
	if len(independentParents) != 1 {
		return false, nil
	}
	// git rev-parse commit^{tree}
	tree, err := p.srcRepo.Tree(commitHash)
	if err != nil {
		return false, err
	}
	// git rev-parse parent^{tree}
	parentTree, err := p.srcRepo.Tree(independentParents[0])
	if err != nil {
		return false, err
	}
	return (tree == parentTree), nil
}

func (p *Pruner) isEmpty(commit Commit) (bool, error) {
	switch len(commit.Parents) {
	case 0:
		return len(commit.Tree) == 0, nil
	case 1:
		return TreesEqual(commit.Tree, p.tree[commit.Parents[0]]), nil
	default:
		return false, nil
	}
}

func (p *Pruner) isAncestor(ancestor, descendant Mark) bool {
	_, ret := p.ancestors[descendant][ancestor]
	return ret
}

func (p *Pruner) pruneParents(arg []Mark) []Mark {
	var ret []Mark
outer:
	for _, candidateDescendant := range arg {
	inner:
		for _, other := range arg {
			if other == candidateDescendant {
				continue inner
			}
			// Make sure candidateDescendent isn't an ancestor of anything else.
			if p.isAncestor(candidateDescendant, other) {
				continue outer
			}
		}
		ret = append(ret, candidateDescendant)
	}
	return ret
}

func (p *Pruner) isFastForward(commit Commit) (bool, error) {
	if len(commit.Parents) < 2 {
		return false, nil
	}
	commit.Parents = p.pruneParents(commit.Parents)
	return p.isEmpty(commit)
}

func (p *Pruner) shouldPrune(commit Commit) (bool, error) {
	switch p.pruneEmpty {
	case PruneAlways:
		isEmpty, err := p.isEmpty(commit)
		if err != nil {
			return false, err
		}
		if isEmpty {
			return true, nil
		}
	case PruneAuto:
		isEmpty, err := p.isEmpty(commit)
		if err != nil {
			return false, err
		}
		wasEmpty, err := p.wasEmpty(commit)
		if err != nil {
			return false, err
		}
		if isEmpty && !wasEmpty {
			return true, nil
		}
	}
	switch p.pruneFastForward {
	case PruneAlways:
		isFastForward, err := p.isFastForward(commit)
		if err != nil {
			return false, err
		}
		if isFastForward {
			return true, nil
		}
	case PruneAuto:
		isFastForward, err := p.isFastForward(commit)
		if err != nil {
			return false, err
		}
		wasFastForward, err := p.wasFastForward(commit)
		if err != nil {
			return false, err
		}
		if isFastForward && !wasFastForward {
			return true, nil
		}
	}
	return false, nil
}