add initial implementation of fi-prune-empty

1 files changed, 162 insertions, 0 deletions

diff --git a/fi-prune-empty/main.go b/fi-prune-empty/main.go
new file mode 100644
index 0000000..6f7b767
--- /dev/null
+++ b/fi-prune-empty/main.go
@@ -0,0 +1,162 @@
+// 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/>.
+
+package main
+
+import (
+	"fmt"
+	"io"
+	"os"
+	"sort"
+
+	"git.lukeshu.com/go/libfastimport"
+	"github.com/pkg/errors"
+)
+
+func abort(err error) {
+	fmt.Fprintln(os.Stderr, "Error:", 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
+}
+
+// expects --full-tree
+func main() {
+	frontend := libfastimport.NewFrontend(os.Stdin, nil, nil)
+	backend := libfastimport.NewBackend(os.Stdout, nil, nil)
+
+	replace := map[string]string{}
+	fixupMark := func(m string) string {
+		if r, ok := replace[m]; ok {
+			return r
+		}
+		return m
+	}
+
+	ancestors := map[string]map[string]struct{}{}
+	trees := map[string]Tree{}
+	addCommit := func(c string, parents []string, tree Tree) {
+		cAncestors := map[string]struct{}{}
+		for _, parent := range parents {
+			parent = fixupMark(parent)
+			cAncestors[parent] = struct{}{}
+			for ancestor := range ancestors[parent] {
+				cAncestors[ancestor] = struct{}{}
+			}
+		}
+		ancestors[c] = cAncestors
+		trees[c] = tree
+	}
+	// subsumedBy(c, commits) determines if commit 'c' is an
+	// ancestor of any of the commits given in 'commits'.
+	subsumedBy := func(c string, commits []string) bool {
+		for _, c2 := range commits {
+			c2 = fixupMark(c2)
+			if c2 == c {
+				continue
+			}
+			if _, ok := ancestors[c2][c]; ok {
+				return true
+			}
+		}
+		return false
+	}
+	pruneParents := func(commits []string) []string {
+		var ret []string
+		for _, c := range commits {
+			c = fixupMark(c)
+			if !subsumedBy(c, commits) {
+				ret = append(ret, c)
+			}
+		}
+		return ret
+	}
+
+	commitMeta := libfastimport.CmdCommit{}
+	commitFile := Tree{}
+	for {
+		cmd, err := frontend.ReadCmd()
+		if err != nil {
+			if err == io.EOF {
+				break
+			}
+			abort(err)
+		}
+
+		switch cmdt := cmd.(type) {
+
+		case libfastimport.CmdCommit:
+			commitMeta = cmdt
+			commitFile = Tree{}
+		case libfastimport.CmdCommitEnd:
+			mark := fmt.Sprintf(":%d", commitMeta.Mark)
+			parents := pruneParents(append([]string{commitMeta.From}, commitMeta.Merge...))
+			sort.Stable(commitFile)
+
+			// decide whether to skip this commit
+			if len(parents) == 1 && TreesEqual(trees[parents[0]], commitFile) {
+				replace[mark] = parents[0]
+				continue
+			}
+
+			// remember the commit
+			addCommit(mark, parents, commitFile)
+
+			// emit the commit
+			commitMeta.From = parents[0]
+			commitMeta.Merge = parents[1:]
+			if err := backend.Do(commitMeta); err != nil {
+				abort(err)
+			}
+			if err := backend.Do(libfastimport.FileDeleteAll{}); err != nil {
+				abort(err)
+			}
+			for _, file := range commitFile {
+				if err := backend.Do(file); err != nil {
+					abort(err)
+				}
+			}
+		case libfastimport.FileDeleteAll:
+			// do nothing
+		case libfastimport.FileModify:
+			commitFile = append(commitFile, cmdt)
+
+		case libfastimport.CmdBlob, libfastimport.CmdCheckpoint, libfastimport.CmdReset, libfastimport.CmdFeature, libfastimport.CmdOption, libfastimport.CmdDone:
+			err := backend.Do(cmd)
+			if err != nil {
+				abort(err)
+			}
+		case libfastimport.CmdComment:
+		default:
+			abort(errors.Errorf("Unexpected command: %[1]T(%#[1]v)", cmd))
+		}
+	}
+}