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

// Copyright 2019-2021  Luke Shumaker <lukeshu@parabola.nu>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

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

	parents map[Mark]map[Mark]struct{}
	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),

		parents: 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
	}

	p.parents[commit.Mark] = func() map[Mark]struct{} {
		parents := make(map[Mark]struct{}, len(commit.Parents))
		for _, parent := range commit.Parents {
			parents[parent] = struct{}{}
		}
		return parents
	}()
	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
}

// isEmpty returns whether `git commit` would require `--allow-empty`
// in order to create that commit.
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 {
	isDescendentMemo := make(map[Mark]bool)
	var isDescendent func(desc Mark) bool
	isDescendent = func(desc Mark) bool {
		if ret, ok := isDescendentMemo[desc]; ok {
			return ret
		}
		ret := false
		for descParent := range p.parents[desc] {
			if descParent == ancestor || isDescendent(descParent) {
				ret = true
				break
			}
		}
		isDescendentMemo[desc] = ret
		return ret
	}
	return isDescendent(descendant)
}

// pruneParents prunes "duplicate" parents of a commit.  It is
// equivalent to running `git merge-base --independent` in the
// destination repo (note: it isn't possible for us to run anything in
// the destination repo).
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) {
	if commit.ExcludedParents {
		// If there are any excluded parents, then we can't
		// reason about it.  Keep the commit.
		return false, nil
	}
	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
}