path: root/fi-prune-empty/main.go

// Copyright 2019  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/>.

// Command fi-prune-empty prunes a fast-import stream, removing empty
// commits and empty merges.
package main

import (
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
	"time"

	"git.lukeshu.com/go/libfastimport"
	"github.com/pkg/errors"

	"git.parabola.nu/~lukeshu/fastimport-go-utils/fiutil"
)

func usage() {
	fmt.Printf("Usage: git fast-export --full-tree | %s | git fast-import\n", os.Args[0])
	fmt.Printf("Prunes a fast-import stream, removing empty commits and empty merges\n")
	os.Exit(0)
}

func main() {
	if len(os.Args) == 2 && os.Args[1] == "--help" {
		usage()
	}
	if len(os.Args) != 1 {
		fiutil.ErrUsage(fmt.Sprintf("expected 0 arguments, got %d", len(os.Args)-1))
	}

	frontend := libfastimport.NewFrontend(os.Stdin, os.Stdin, nil)
	backend := libfastimport.NewBackend(os.Stdout, os.Stdout, nil)

	filter := NewPruneEmpty(backend)
	if err := fiutil.RunHandler(frontend, filter); err != nil {
		fmt.Fprintf(os.Stderr, "%s: error: %v\n", os.Args[0], err)
		os.Exit(1)
	}
}

type Tree []libfastimport.FileModify

func (t Tree) Len() int           { return len(t) }
func (t Tree) Less(i, j int) bool { return t[i].Path < t[j].Path }
func (t Tree) Swap(i, j int)      { t[i], t[j] = t[j], t[i] }

func TreesEqual(a, b Tree) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

type PruneEmpty struct {
	backend *libfastimport.Backend

	// history
	replace map[string]string

	// history
	ancestors map[string]map[string]struct{}
	trees     map[string]Tree
	refs      map[string]string

	// current commit
	commitMeta libfastimport.CmdCommit
	commitFile Tree

	// statistics
	commitsIn  int
	commitsOut int
	beg        time.Time
}

func NewPruneEmpty(backend *libfastimport.Backend) *PruneEmpty {
	return &PruneEmpty{
		backend: backend,

		// history
		replace: map[string]string{},

		// history
		ancestors: map[string]map[string]struct{}{},
		trees:     map[string]Tree{},
		refs:      map[string]string{},

		// current commit
		commitMeta: libfastimport.CmdCommit{},
		commitFile: Tree{},

		// statistics
		beg: time.Now(),
	}
}

func (h *PruneEmpty) fixupMark(m string) string {
	if r, ok := h.replace[m]; ok {
		return r
	}
	return m
}

func (h *PruneEmpty) addCommit(c string, parents []string, tree Tree) {
	cAncestors := map[string]struct{}{}
	for _, parent := range parents {
		parent = h.fixupMark(parent)
		cAncestors[parent] = struct{}{}
		for ancestor := range h.ancestors[parent] {
			cAncestors[ancestor] = struct{}{}
		}
	}
	h.ancestors[c] = cAncestors
	h.trees[c] = tree
}

// subsumedBy(c, commits) determines if commit 'c' is an
// ancestor of any of the commits given in 'commits'.
func (h *PruneEmpty) subsumedBy(c string, commits []string) bool {
	for _, c2 := range commits {
		c2 = h.fixupMark(c2)
		if c2 == c {
			continue
		}
		if _, ok := h.ancestors[c2][c]; ok {
			return true
		}
	}
	return false
}
func (h *PruneEmpty) pruneParents(commits []string) []string {
	var ret []string
	for _, c := range commits {
		c = h.fixupMark(c)
		if c != "" && !h.subsumedBy(c, commits) {
			ret = append(ret, c)
		}
	}
	return ret
}

////////////////////////////////////////////////////////////////////////////////

// commit //////////////////////////////////////////////////////////////////////
func (h *PruneEmpty) CmdCommit(cmd libfastimport.CmdCommit) error {
	if cmd.Mark < 0 {
		return errors.Errorf("refusing to process commit to %q without mark", cmd.Ref)
	}
	h.commitMeta = cmd
	h.commitFile = Tree{}
	return nil
}
func (h *PruneEmpty) CmdCommitEnd(cmd libfastimport.CmdCommitEnd) error {
	h.commitsIn++
	defer func() {
		h.backend.Do(libfastimport.CmdProgress{
			Str: fmt.Sprintf("[%s] %d commits => %d commits (%.2f commit/s)",
				os.Args[0],
				h.commitsIn, h.commitsOut,
				float64(h.commitsIn)/time.Since(h.beg).Seconds()),
		})
	}()

	mark := fmt.Sprintf(":%d", h.commitMeta.Mark)
	from := h.commitMeta.From
	if from == "" {
		from = h.refs[h.commitMeta.Ref]
	}
	parents := h.pruneParents(append([]string{from}, h.commitMeta.Merge...))
	sort.Stable(h.commitFile)

	// decide whether to skip this commit
	switch len(parents) {
	case 0:
		if len(h.commitFile) == 0 {
			h.replace[mark] = ""
			return nil
		}
		h.commitMeta.From = ""
		h.commitMeta.Merge = nil
	case 1:
		if TreesEqual(h.trees[parents[0]], h.commitFile) {
			h.replace[mark] = parents[0]
			h.refs[h.commitMeta.Ref] = parents[0]
			return nil
		}
		fallthrough
	default:
		h.commitMeta.From = parents[0]
		h.commitMeta.Merge = parents[1:]
	}
	h.commitsOut++

	// remember the commit
	h.addCommit(mark, parents, h.commitFile)
	if h.commitMeta.From == "" && h.refs[h.commitMeta.Ref] != "" {
		return errors.Errorf("refusing to reset ref %q from %q", h.commitMeta.Ref, h.refs[h.commitMeta.Ref])
	}
	h.refs[h.commitMeta.Ref] = mark

	// emit the commit
	if err := h.backend.Do(h.commitMeta); err != nil {
		return err
	}
	if err := h.backend.Do(libfastimport.FileDeleteAll{}); err != nil {
		return err
	}
	for _, file := range h.commitFile {
		if err := h.backend.Do(file); err != nil {
			return err
		}
	}

	return nil
}

// file commands ///////////////////////////////////////////////////////////////
func (h *PruneEmpty) FileModify(cmd libfastimport.FileModify) error {
	h.commitFile = append(h.commitFile, cmd)
	return nil
}
func (h *PruneEmpty) FileModifyInline(cmd libfastimport.FileModifyInline) error {
	return errors.New("unexpected inline \"filemodify\" command; must use a mark")
}
func (h *PruneEmpty) FileCopy(cmd libfastimport.FileCopy) error {
	return errors.New("unexpected \"filecopy\" command: this filter requires --full-tree")
}
func (h *PruneEmpty) FileRename(cmd libfastimport.FileRename) error {
	return errors.New("unexpected \"filerename\" command: this filter requires --full-tree")
}
func (h *PruneEmpty) FileDelete(cmd libfastimport.FileDelete) error {
	return errors.New("unexpected \"filedelete\" command: this filter requires --full-tree")
}
func (h *PruneEmpty) FileDeleteAll(cmd libfastimport.FileDeleteAll) error {
	// do nothing
	return nil
}

// note commands ///////////////////////////////////////////////////////////////
func (h *PruneEmpty) NoteModify(cmd libfastimport.NoteModify) error {
	return errors.Errorf("unsupported (but known) command %T", cmd)
}
func (h *PruneEmpty) NoteModifyInline(cmd libfastimport.NoteModifyInline) error {
	return errors.Errorf("unsupported (but known) command %T", cmd)
}

// other commands //////////////////////////////////////////////////////////////
func (h *PruneEmpty) CmdBlob(cmd libfastimport.CmdBlob) error             { return h.backend.Do(cmd) }
func (h *PruneEmpty) CmdCheckpoint(cmd libfastimport.CmdCheckpoint) error { return h.backend.Do(cmd) }
func (h *PruneEmpty) CmdComment(cmd libfastimport.CmdComment) error       { return h.backend.Do(cmd) }
func (h *PruneEmpty) CmdDone(cmd libfastimport.CmdDone) error             { return h.backend.Do(cmd) }
func (h *PruneEmpty) CmdOption(cmd libfastimport.CmdOption) error         { return h.backend.Do(cmd) }
func (h *PruneEmpty) CmdProgress(cmd libfastimport.CmdProgress) error     { return h.backend.Do(cmd) }
func (h *PruneEmpty) CmdReset(cmd libfastimport.CmdReset) error           { return h.backend.Do(cmd) }
func (h *PruneEmpty) CmdTag(cmd libfastimport.CmdTag) error               { return h.backend.Do(cmd) }

func (h *PruneEmpty) CmdCatBlob(cmd libfastimport.CmdCatBlob) (sha1 string, data string, err error) {
	if strings.HasPrefix(cmd.DataRef, ":") {
		cmd.DataRef = h.fixupMark(cmd.DataRef)
	}
	return h.backend.CatBlob(cmd)
}
func (h *PruneEmpty) CmdGetMark(cmd libfastimport.CmdGetMark) (sha1 string, err error) {
	cmd.Mark, _ = strconv.Atoi(h.fixupMark(fmt.Sprintf(":%d", cmd.Mark))[1:])
	return h.backend.GetMark(cmd)
}
func (h *PruneEmpty) CmdLs(cmd libfastimport.CmdLs) (mode libfastimport.Mode, dataref string, path libfastimport.Path, err error) {
	if strings.HasPrefix(cmd.DataRef, ":") {
		cmd.DataRef = h.fixupMark(cmd.DataRef)
	}
	return h.backend.Ls(cmd)
}

func (h *PruneEmpty) CmdFeature(cmd libfastimport.CmdFeature) error {
	switch cmd.Feature {
	case "date-format":
		if cmd.Argument != "raw" {
			return errors.Errorf("date-format=%q: only supports the %q format", cmd.Argument, "raw")
		}
		return h.backend.Do(cmd)
	case "export-marks", "relative-marks", "no-relative-marks", "force", "import-marks", "import-marks-if-exists", "get-mark", "cat-blob", "ls":
		return h.backend.Do(cmd)
	case "notes":
		return errors.Errorf("unsupported (but known) command %T", cmd)
	case "done":
		return h.backend.Do(cmd)
	default:
		return errors.Errorf("unknown feature %q", cmd.Feature)
	}
}