From 040b572d95e4ca27e1ada6113c405b8a1eb4a669 Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Wed, 11 Mar 2026 20:41:32 +0800 Subject: commitquery: Merge from ancestor and mergebases --- commitquery/ancestor.go | 48 +++++ commitquery/ancestor_integration_test.go | 132 ++++++++++++ commitquery/ancestor_unit_test.go | 117 +++++++++++ commitquery/bits.go | 14 ++ commitquery/commit.go | 17 ++ commitquery/compare.go | 25 +++ commitquery/context.go | 34 +++ commitquery/errors.go | 5 + commitquery/generation.go | 43 ++++ commitquery/graph_pos.go | 107 ++++++++++ commitquery/load.go | 14 ++ commitquery/marks.go | 71 +++++++ commitquery/merge_bases.go | 171 +++++++++++++++ commitquery/mergebase_integration_test.go | 311 ++++++++++++++++++++++++++++ commitquery/mergebase_unit_test.go | 332 ++++++++++++++++++++++++++++++ commitquery/node.go | 39 ++++ commitquery/oid.go | 101 +++++++++ commitquery/parent.go | 27 +++ commitquery/populate.go | 42 ++++ commitquery/priority_queue.go | 68 ++++++ commitquery/reduce.go | 166 +++++++++++++++ 21 files changed, 1884 insertions(+) create mode 100644 commitquery/ancestor.go create mode 100644 commitquery/ancestor_integration_test.go create mode 100644 commitquery/ancestor_unit_test.go create mode 100644 commitquery/bits.go create mode 100644 commitquery/commit.go create mode 100644 commitquery/compare.go create mode 100644 commitquery/context.go create mode 100644 commitquery/errors.go create mode 100644 commitquery/generation.go create mode 100644 commitquery/graph_pos.go create mode 100644 commitquery/load.go create mode 100644 commitquery/marks.go create mode 100644 commitquery/merge_bases.go create mode 100644 commitquery/mergebase_integration_test.go create mode 100644 commitquery/mergebase_unit_test.go create mode 100644 commitquery/node.go create mode 100644 commitquery/oid.go create mode 100644 commitquery/parent.go create mode 100644 commitquery/populate.go create mode 100644 commitquery/priority_queue.go create mode 100644 commitquery/reduce.go (limited to 'commitquery') diff --git a/commitquery/ancestor.go b/commitquery/ancestor.go new file mode 100644 index 00000000..671ea460 --- /dev/null +++ b/commitquery/ancestor.go @@ -0,0 +1,48 @@ +package commitquery + +import "codeberg.org/lindenii/furgit/objectid" + +// IsAncestor reports whether ancestor is reachable from descendant through +// commit parent edges. +// +// Both inputs are peeled through annotated tags before commit traversal. +func (query *Query) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, error) { + ancestorIdx, err := query.resolveCommitish(ancestor) + if err != nil { + return false, err + } + + descendantIdx, err := query.resolveCommitish(descendant) + if err != nil { + return false, err + } + + return query.isAncestor(ancestorIdx, descendantIdx) +} + +func (query *Query) isAncestor(ancestor, descendant nodeIndex) (bool, error) { + if ancestor == descendant { + return true, nil + } + + ancestorGeneration := query.effectiveGeneration(ancestor) + descendantGeneration := query.effectiveGeneration(descendant) + + if ancestorGeneration != generationInfinity && + descendantGeneration != generationInfinity && + ancestorGeneration > descendantGeneration { + return false, nil + } + + minGeneration := uint64(0) + if ancestorGeneration != generationInfinity { + minGeneration = ancestorGeneration + } + + err := query.paintDownToCommon(ancestor, []nodeIndex{descendant}, minGeneration) + if err != nil { + return false, err + } + + return query.hasAnyMarks(ancestor, markRight), nil +} diff --git a/commitquery/ancestor_integration_test.go b/commitquery/ancestor_integration_test.go new file mode 100644 index 00000000..a25697aa --- /dev/null +++ b/commitquery/ancestor_integration_test.go @@ -0,0 +1,132 @@ +package commitquery_test + +import ( + "errors" + "testing" + + "codeberg.org/lindenii/furgit/commitquery" + giterrors "codeberg.org/lindenii/furgit/errors" + "codeberg.org/lindenii/furgit/internal/testgit" + "codeberg.org/lindenii/furgit/objectid" +) + +func TestIsMatchesGitMergeBase(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + testRepo := testgit.NewRepo(t, testgit.RepoOptions{ + ObjectFormat: algo, + Bare: true, + RefFormat: "files", + }) + + _, tree1 := testRepo.MakeSingleFileTree(t, "one.txt", []byte("one\n")) + c1 := testRepo.CommitTree(t, tree1, "c1") + + _, tree2 := testRepo.MakeSingleFileTree(t, "two.txt", []byte("two\n")) + c2 := testRepo.CommitTree(t, tree2, "c2", c1) + + _, tree3 := testRepo.MakeSingleFileTree(t, "three.txt", []byte("three\n")) + c3 := testRepo.CommitTree(t, tree3, "c3", c2) + + tag := testRepo.TagAnnotated(t, "tip", c2, "tip") + + store := testRepo.OpenObjectStore(t) + + got, err := commitquery.New(store, nil).IsAncestor(c1, tag) + if err != nil { + t.Fatalf("Is(c1, tag): %v", err) + } + + want := gitMergeBaseIsAncestor(t, testRepo, c1, c2) + if got != want { + t.Fatalf("Is(c1, tag)=%v, want %v", got, want) + } + + got, err = commitquery.New(store, nil).IsAncestor(c3, c2) + if err != nil { + t.Fatalf("Is(c3, c2): %v", err) + } + + want = gitMergeBaseIsAncestor(t, testRepo, c3, c2) + if got != want { + t.Fatalf("Is(c3, c2)=%v, want %v", got, want) + } + }) +} + +func TestIsMatchesGitMergeBaseWithCommitGraph(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + testRepo := testgit.NewRepo(t, testgit.RepoOptions{ + ObjectFormat: algo, + Bare: true, + RefFormat: "files", + }) + + _, tree1 := testRepo.MakeSingleFileTree(t, "one.txt", []byte("one\n")) + c1 := testRepo.CommitTree(t, tree1, "c1") + + _, tree2 := testRepo.MakeSingleFileTree(t, "two.txt", []byte("two\n")) + c2 := testRepo.CommitTree(t, tree2, "c2", c1) + + testRepo.UpdateRef(t, "refs/heads/main", c2) + testRepo.SymbolicRef(t, "HEAD", "refs/heads/main") + testRepo.CommitGraphWrite(t, "--reachable") + + store := testRepo.OpenObjectStore(t) + graph := testRepo.OpenCommitGraph(t) + + got, err := commitquery.New(store, graph).IsAncestor(c1, c2) + if err != nil { + t.Fatalf("Is(c1, c2): %v", err) + } + + want := gitMergeBaseIsAncestor(t, testRepo, c1, c2) + if got != want { + t.Fatalf("Is(c1, c2)=%v, want %v", got, want) + } + }) +} + +func TestIsMissingObject(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + testRepo := testgit.NewRepo(t, testgit.RepoOptions{ + ObjectFormat: algo, + Bare: true, + RefFormat: "files", + }) + + _, treeID, commitID := testRepo.MakeCommit(t, "missing") + + testRepo.RemoveLooseObject(t, treeID) + + store := testRepo.OpenObjectStore(t) + + _, err := commitquery.New(store, nil).IsAncestor(treeID, commitID) + if err == nil { + t.Fatal("expected error") + } + + missing, ok := errors.AsType[*giterrors.ObjectMissingError](err) + if !ok { + t.Fatalf("expected ObjectMissingError, got %T (%v)", err, err) + } + + if missing.OID != treeID { + t.Fatalf("missing oid = %s, want %s", missing.OID, treeID) + } + }) +} + +// gitMergeBaseIsAncestor reports Git's merge-base ancestry answer. +func gitMergeBaseIsAncestor(t *testing.T, testRepo *testgit.TestRepo, left, right objectid.ObjectID) bool { + t.Helper() + + out := testRepo.Run(t, "merge-base", left.String(), right.String()) + + return out == left.String() +} diff --git a/commitquery/ancestor_unit_test.go b/commitquery/ancestor_unit_test.go new file mode 100644 index 00000000..6edb05be --- /dev/null +++ b/commitquery/ancestor_unit_test.go @@ -0,0 +1,117 @@ +package commitquery_test + +import ( + "errors" + "fmt" + "testing" + + giterrors "codeberg.org/lindenii/furgit/errors" + "codeberg.org/lindenii/furgit/internal/testgit" + "codeberg.org/lindenii/furgit/object" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore/memory" + "codeberg.org/lindenii/furgit/objecttype" + + "codeberg.org/lindenii/furgit/commitquery" +) + +// ancestorCommitBody serializes one minimal commit body. +func ancestorCommitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte { + buf := fmt.Appendf(nil, "tree %s\n", tree.String()) + for _, parent := range parents { + buf = append(buf, fmt.Appendf(nil, "parent %s\n", parent.String())...) + } + + buf = append(buf, []byte("\nmsg\n")...) + + return buf +} + +// ancestorTagBody serializes one minimal annotated tag body. +func ancestorTagBody(target objectid.ObjectID, targetType objecttype.Type) []byte { + targetName, ok := objecttype.Name(targetType) + if !ok { + panic("invalid tag target type") + } + + return fmt.Appendf(nil, "object %s\ntype %s\ntag t\n\nmsg\n", target.String(), targetName) +} + +// mustSerializeAncestorTree serializes one tree or fails the test. +func mustSerializeAncestorTree(tb testing.TB, tree *object.Tree) []byte { + tb.Helper() + + body, err := tree.SerializeWithoutHeader() + if err != nil { + tb.Fatalf("SerializeWithoutHeader: %v", err) + } + + return body +} + +func TestIs(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + tree := store.AddObject(objecttype.TypeTree, mustSerializeAncestorTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("f"), + ID: blob, + }}})) + c1 := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(tree)) + c2 := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(tree, c1)) + otherBlob := store.AddObject(objecttype.TypeBlob, []byte("other-blob\n")) + otherTree := store.AddObject(objecttype.TypeTree, mustSerializeAncestorTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("g"), + ID: otherBlob, + }}})) + c3 := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(otherTree)) + tag := store.AddObject(objecttype.TypeTag, ancestorTagBody(c2, objecttype.TypeCommit)) + + ok, err := commitquery.New(store, nil).IsAncestor(c1, tag) + if err != nil { + t.Fatalf("Is(c1, tag): %v", err) + } + + if !ok { + t.Fatal("expected c1 to be ancestor of tag->c2") + } + + ok, err = commitquery.New(store, nil).IsAncestor(c3, c2) + if err != nil { + t.Fatalf("Is(c3, c2): %v", err) + } + + if ok { + t.Fatal("did not expect c3 to be ancestor of c2") + } + }) +} + +func TestIsRejectsNonCommitAfterPeel(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + tree := store.AddObject(objecttype.TypeTree, mustSerializeAncestorTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("f"), + ID: blob, + }}})) + commit := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(tree)) + tagToTree := store.AddObject(objecttype.TypeTag, ancestorTagBody(tree, objecttype.TypeTree)) + + _, err := commitquery.New(store, nil).IsAncestor(commit, tagToTree) + if err == nil { + t.Fatal("expected error") + } + + if _, ok := errors.AsType[*giterrors.ObjectTypeError](err); !ok { + t.Fatalf("expected ObjectTypeError, got %T (%v)", err, err) + } + }) +} diff --git a/commitquery/bits.go b/commitquery/bits.go new file mode 100644 index 00000000..36ffff29 --- /dev/null +++ b/commitquery/bits.go @@ -0,0 +1,14 @@ +package commitquery + +type markBits uint8 + +const ( + markLeft markBits = 1 << iota + markRight + markStale + markResult +) + +const ( + allMarks = markLeft | markRight | markStale | markResult +) diff --git a/commitquery/commit.go b/commitquery/commit.go new file mode 100644 index 00000000..f4709270 --- /dev/null +++ b/commitquery/commit.go @@ -0,0 +1,17 @@ +package commitquery + +import ( + commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" +) + +// commitData stores the metadata needed by commit-domain queries. +type commitData struct { + ID objectid.ObjectID + Parents []parentRef + CommitTime int64 + Generation uint64 + HasGeneration bool + GraphPos commitgraphread.Position + HasGraphPos bool +} diff --git a/commitquery/compare.go b/commitquery/compare.go new file mode 100644 index 00000000..f64b5b3f --- /dev/null +++ b/commitquery/compare.go @@ -0,0 +1,25 @@ +package commitquery + +import "codeberg.org/lindenii/furgit/objectid" + +// Compare compares two internal nodes using merge-base queue ordering. +func (query *Query) compare(left, right nodeIndex) int { + leftGeneration := query.effectiveGeneration(left) + rightGeneration := query.effectiveGeneration(right) + + switch { + case leftGeneration < rightGeneration: + return -1 + case leftGeneration > rightGeneration: + return 1 + } + + switch { + case query.nodes[left].commitTime < query.nodes[right].commitTime: + return -1 + case query.nodes[left].commitTime > query.nodes[right].commitTime: + return 1 + } + + return objectid.Compare(query.nodes[left].id, query.nodes[right].id) +} diff --git a/commitquery/context.go b/commitquery/context.go new file mode 100644 index 00000000..8e19138e --- /dev/null +++ b/commitquery/context.go @@ -0,0 +1,34 @@ +// Package commitquery answers commit ancestry and merge-base queries. +package commitquery + +import ( + commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore" +) + +// Query owns the mutable node arena for commit-domain queries over one object +// store. +type Query struct { + store objectstore.Store + graph *commitgraphread.Reader + + nodes []node + + byOID map[objectid.ObjectID]nodeIndex + byGraphPos map[commitgraphread.Position]nodeIndex + + markPhase uint32 + touched []nodeIndex +} + +// New builds one reusable commit query arena over one object store and optional +// commit-graph reader. +func New(store objectstore.Store, graph *commitgraphread.Reader) *Query { + return &Query{ + store: store, + graph: graph, + byOID: make(map[objectid.ObjectID]nodeIndex), + byGraphPos: make(map[commitgraphread.Position]nodeIndex), + } +} diff --git a/commitquery/errors.go b/commitquery/errors.go new file mode 100644 index 00000000..e99011d0 --- /dev/null +++ b/commitquery/errors.go @@ -0,0 +1,5 @@ +package commitquery + +import "errors" + +var errBadGenerationOrder = errors.New("commitquery: priority queue violated generation ordering") diff --git a/commitquery/generation.go b/commitquery/generation.go new file mode 100644 index 00000000..05228b29 --- /dev/null +++ b/commitquery/generation.go @@ -0,0 +1,43 @@ +package commitquery + +import ( + "math" + + "codeberg.org/lindenii/furgit/objectid" +) + +// EffectiveGeneration returns one node's generation value. +func (query *Query) effectiveGeneration(idx nodeIndex) uint64 { + if !query.nodes[idx].hasGeneration { + return generationInfinity + } + + return query.nodes[idx].generation +} + +const ( + generationInfinity = uint64(math.MaxUint64) +) + +func compareByGeneration(query *Query) func(nodeIndex, nodeIndex) int { + return func(left, right nodeIndex) int { + leftGeneration := query.effectiveGeneration(left) + rightGeneration := query.effectiveGeneration(right) + + switch { + case leftGeneration < rightGeneration: + return -1 + case leftGeneration > rightGeneration: + return 1 + } + + switch { + case query.nodes[left].commitTime < query.nodes[right].commitTime: + return -1 + case query.nodes[left].commitTime > query.nodes[right].commitTime: + return 1 + } + + return objectid.Compare(query.nodes[left].id, query.nodes[right].id) + } +} diff --git a/commitquery/graph_pos.go b/commitquery/graph_pos.go new file mode 100644 index 00000000..b1d27129 --- /dev/null +++ b/commitquery/graph_pos.go @@ -0,0 +1,107 @@ +package commitquery + +import commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" + +// resolveGraphPos resolves one commit-graph position to one internal query node. +func (query *Query) resolveGraphPos(pos commitgraphread.Position) (nodeIndex, error) { + idx, ok := query.byGraphPos[pos] + if ok { + err := query.ensureLoaded(idx) + if err != nil { + return 0, err + } + + return idx, nil + } + + commit, err := query.graph.CommitAt(pos) + if err != nil { + return 0, err + } + + idx, ok = query.byOID[commit.OID] + if !ok { + idx = query.newNode(commit.OID) + query.byOID[commit.OID] = idx + } + + query.byGraphPos[pos] = idx + query.nodes[idx].graphPos = pos + query.nodes[idx].hasGraphPos = true + + err = query.loadCommitAtGraphPos(idx, pos) + if err != nil { + delete(query.byGraphPos, pos) + + return 0, err + } + + return idx, nil +} + +// loadByGraphPos populates one node from a commit-graph position. +func (query *Query) loadByGraphPos(idx nodeIndex) error { + pos := query.nodes[idx].graphPos + + return query.loadCommitAtGraphPos(idx, pos) +} + +func (query *Query) loadCommitAtGraphPos(idx nodeIndex, pos commitgraphread.Position) error { + commit, err := query.graph.CommitAt(pos) + if err != nil { + return err + } + + parents := make([]parentRef, 0, 2+len(commit.ExtraParents)) + + if commit.Parent1.Valid { + parentOID, err := query.graph.OIDAt(commit.Parent1.Pos) + if err != nil { + return err + } + + parents = append(parents, parentRef{ + ID: parentOID, + GraphPos: commit.Parent1.Pos, + HasGraphPos: true, + }) + } + + if commit.Parent2.Valid { + parentOID, err := query.graph.OIDAt(commit.Parent2.Pos) + if err != nil { + return err + } + + parents = append(parents, parentRef{ + ID: parentOID, + GraphPos: commit.Parent2.Pos, + HasGraphPos: true, + }) + } + + for _, parentPos := range commit.ExtraParents { + parentOID, err := query.graph.OIDAt(parentPos) + if err != nil { + return err + } + + parents = append(parents, parentRef{ + ID: parentOID, + GraphPos: parentPos, + HasGraphPos: true, + }) + } + + data := commitData{ + ID: commit.OID, + Parents: parents, + CommitTime: commit.CommitTimeUnix, + Generation: commit.GenerationV2, + HasGeneration: commit.GenerationV2 != 0, + GraphPos: pos, + HasGraphPos: true, + } + + return query.populateNode(idx, data) +} diff --git a/commitquery/load.go b/commitquery/load.go new file mode 100644 index 00000000..58ed7bf3 --- /dev/null +++ b/commitquery/load.go @@ -0,0 +1,14 @@ +package commitquery + +// ensureLoaded completes one node's metadata load if it has not been loaded yet. +func (query *Query) ensureLoaded(idx nodeIndex) error { + if query.nodes[idx].loaded { + return nil + } + + if query.nodes[idx].hasGraphPos { + return query.loadByGraphPos(idx) + } + + return query.loadByOID(idx) +} diff --git a/commitquery/marks.go b/commitquery/marks.go new file mode 100644 index 00000000..de008789 --- /dev/null +++ b/commitquery/marks.go @@ -0,0 +1,71 @@ +package commitquery + +// Marks returns the mark bits of one internal node. +func (query *Query) marks(idx nodeIndex) markBits { + return query.nodes[idx].marks +} + +// HasAnyMarks reports whether one internal node has any requested bit. +func (query *Query) hasAnyMarks(idx nodeIndex, bits markBits) bool { + return query.nodes[idx].marks&bits != 0 +} + +// HasAllMarks reports whether one internal node already has all requested bits. +func (query *Query) hasAllMarks(idx nodeIndex, bits markBits) bool { + return query.nodes[idx].marks&bits == bits +} + +// SetMarks ORs one set of mark bits into one internal node. +func (query *Query) setMarks(idx nodeIndex, bits markBits) { + newBits := bits &^ query.nodes[idx].marks + if newBits == 0 { + return + } + + query.trackTouched(idx) + query.nodes[idx].marks |= bits +} + +// ClearMarks removes one set of mark bits from one internal node. +func (query *Query) clearMarks(idx nodeIndex, bits markBits) { + if query.nodes[idx].marks&bits == 0 { + return + } + + query.trackTouched(idx) + query.nodes[idx].marks &^= bits +} + +// BeginMarkPhase starts one tracked mark-mutation phase. +func (query *Query) beginMarkPhase() { + for _, idx := range query.touched { + query.nodes[idx].marks = 0 + } + + query.markPhase++ + if query.markPhase == 0 { + query.markPhase++ + for i := range query.nodes { + query.nodes[i].touchedPhase = 0 + } + } + + query.touched = query.touched[:0] +} + +// ClearTouchedMarks clears the provided bits from all nodes touched in the +// current mark phase. +func (query *Query) clearTouchedMarks(bits markBits) { + for _, idx := range query.touched { + query.nodes[idx].marks &^= bits + } +} + +func (query *Query) trackTouched(idx nodeIndex) { + if query.nodes[idx].touchedPhase == query.markPhase { + return + } + + query.nodes[idx].touchedPhase = query.markPhase + query.touched = append(query.touched, idx) +} diff --git a/commitquery/merge_bases.go b/commitquery/merge_bases.go new file mode 100644 index 00000000..c63bb82f --- /dev/null +++ b/commitquery/merge_bases.go @@ -0,0 +1,171 @@ +package commitquery + +import ( + "slices" + + "codeberg.org/lindenii/furgit/objectid" +) + +// MergeBases reports all merge bases in Git's merge-base --all order. +// +// Both inputs are peeled through annotated tags before commit traversal. +func (query *Query) MergeBases(left, right objectid.ObjectID) ([]objectid.ObjectID, error) { + leftIdx, err := query.resolveCommitish(left) + if err != nil { + return nil, err + } + + rightIdx, err := query.resolveCommitish(right) + if err != nil { + return nil, err + } + + candidates, err := query.mergeBases(leftIdx, rightIdx) + if err != nil { + return nil, err + } + + slices.SortFunc(candidates, func(left, right nodeIndex) int { + switch { + case query.commitTime(left) > query.commitTime(right): + return -1 + case query.commitTime(left) < query.commitTime(right): + return 1 + default: + return objectid.Compare(query.id(left), query.id(right)) + } + }) + + out := make([]objectid.ObjectID, 0, len(candidates)) + for _, idx := range candidates { + out = append(out, query.id(idx)) + } + + return out, nil +} + +// MergeBase reports one merge base between left and right, if any. +func (query *Query) MergeBase(left, right objectid.ObjectID) (objectid.ObjectID, bool, error) { + bases, err := query.MergeBases(left, right) + if err != nil { + return objectid.ObjectID{}, false, err + } + + if len(bases) == 0 { + return objectid.ObjectID{}, false, nil + } + + return bases[0], true, nil +} + +func (query *Query) mergeBases(left, right nodeIndex) ([]nodeIndex, error) { + if left == right { + return []nodeIndex{left}, nil + } + + err := query.paintDownToCommon(left, []nodeIndex{right}, 0) + if err != nil { + return nil, err + } + + candidates := query.collectMarkedResults() + + if len(candidates) <= 1 { + slices.SortFunc(candidates, query.compare) + + return candidates, nil + } + + query.clearTouchedMarks(allMarks) + + reduced, err := removeRedundant(query, candidates) + if err != nil { + return nil, err + } + + slices.SortFunc(reduced, query.compare) + + return reduced, nil +} + +func (query *Query) paintDownToCommon(left nodeIndex, rights []nodeIndex, minGeneration uint64) error { + query.beginMarkPhase() + + query.setMarks(left, markLeft) + + if len(rights) == 0 { + query.setMarks(left, markResult) + + return nil + } + + queue := newPriorityQueue(query) + queue.PushNode(left) + + for _, right := range rights { + query.setMarks(right, markRight) + queue.PushNode(right) + } + + lastGeneration := generationInfinity + + for query.queueHasNonStale(queue) { + idx := queue.PopNode() + + generation := query.effectiveGeneration(idx) + if generation > lastGeneration { + return errBadGenerationOrder + } + + lastGeneration = generation + if generation < minGeneration { + break + } + + flags := query.marks(idx) & (markLeft | markRight | markStale) + if flags == (markLeft | markRight) { + query.setMarks(idx, markResult) + + flags |= markStale + } + + for _, parent := range query.parents(idx) { + if query.hasAllMarks(parent, flags) { + continue + } + + query.setMarks(parent, flags) + queue.PushNode(parent) + } + } + + return nil +} + +func (query *Query) queueHasNonStale(queue *priorityQueue) bool { + for _, idx := range queue.items { + if !query.hasAnyMarks(idx, markStale) { + return true + } + } + + return false +} + +func (query *Query) collectMarkedResults() []nodeIndex { + out := make([]nodeIndex, 0, 4) + + for _, idx := range query.touched { + if !query.hasAnyMarks(idx, markResult) { + continue + } + + if query.hasAnyMarks(idx, markStale) { + continue + } + + out = append(out, idx) + } + + return out +} diff --git a/commitquery/mergebase_integration_test.go b/commitquery/mergebase_integration_test.go new file mode 100644 index 00000000..30477454 --- /dev/null +++ b/commitquery/mergebase_integration_test.go @@ -0,0 +1,311 @@ +package commitquery_test + +import ( + "maps" + "slices" + "strings" + "testing" + + "codeberg.org/lindenii/furgit/commitquery" + "codeberg.org/lindenii/furgit/internal/testgit" + "codeberg.org/lindenii/furgit/objectid" +) + +func TestQueryMatchesGitMergeBaseAll(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + testRepo := testgit.NewRepo(t, testgit.RepoOptions{ + ObjectFormat: algo, + Bare: true, + RefFormat: "files", + }) + + _, tree1 := testRepo.MakeSingleFileTree(t, "base.txt", []byte("base\n")) + base := testRepo.CommitTree(t, tree1, "base") + + _, tree2 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n")) + left := testRepo.CommitTree(t, tree2, "left", base) + + _, tree3 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n")) + right := testRepo.CommitTree(t, tree3, "right", base) + + tag := testRepo.TagAnnotated(t, "right-tag", right, "right-tag") + + store := testRepo.OpenObjectStore(t) + + query := commitquery.New(store, nil) + + all, err := query.MergeBases(left, tag) + if err != nil { + t.Fatalf("query.All(): %v", err) + } + + got := oidSetFromSlice(all) + + want := gitMergeBaseAllSet(t, testRepo, left, tag) + if !maps.Equal(got, want) { + t.Fatalf("Query(left, tag) mismatch:\n got=%v\nwant=%v", sortedOIDStrings(got), sortedOIDStrings(want)) + } + }) +} + +func TestQueryCrissCrossMatchesGitMergeBaseAll(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + testRepo := testgit.NewRepo(t, testgit.RepoOptions{ + ObjectFormat: algo, + Bare: true, + RefFormat: "files", + }) + + _, tree1 := testRepo.MakeSingleFileTree(t, "root.txt", []byte("root\n")) + root := testRepo.CommitTree(t, tree1, "root") + + _, tree2 := testRepo.MakeSingleFileTree(t, "base1.txt", []byte("base1\n")) + base1 := testRepo.CommitTree(t, tree2, "base1", root) + + _, tree3 := testRepo.MakeSingleFileTree(t, "base2.txt", []byte("base2\n")) + base2 := testRepo.CommitTree(t, tree3, "base2", root) + + _, tree4 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n")) + left := testRepo.CommitTree(t, tree4, "left", base1, base2) + + _, tree5 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n")) + right := testRepo.CommitTree(t, tree5, "right", base2, base1) + + store := testRepo.OpenObjectStore(t) + + query := commitquery.New(store, nil) + + all, err := query.MergeBases(left, right) + if err != nil { + t.Fatalf("query.All(): %v", err) + } + + got := oidSetFromSlice(all) + + want := gitMergeBaseAllSet(t, testRepo, left, right) + if !maps.Equal(got, want) { + t.Fatalf("Query(left, right) mismatch:\n got=%v\nwant=%v", sortedOIDStrings(got), sortedOIDStrings(want)) + } + + first, ok, err := query.MergeBase(left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if !ok { + t.Fatal("Base(left, right) unexpectedly reported no base") + } + + if !containsID(want, first) { + t.Fatalf("Base(left, right)=%s, want one of %v", first, slices.Collect(maps.Keys(want))) + } + }) +} + +func TestQueryMatchesGitMergeBaseAllWithCommitGraph(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + testRepo := testgit.NewRepo(t, testgit.RepoOptions{ + ObjectFormat: algo, + Bare: true, + RefFormat: "files", + }) + + _, tree1 := testRepo.MakeSingleFileTree(t, "root.txt", []byte("root\n")) + root := testRepo.CommitTree(t, tree1, "root") + + _, tree2 := testRepo.MakeSingleFileTree(t, "base1.txt", []byte("base1\n")) + base1 := testRepo.CommitTree(t, tree2, "base1", root) + + _, tree3 := testRepo.MakeSingleFileTree(t, "base2.txt", []byte("base2\n")) + base2 := testRepo.CommitTree(t, tree3, "base2", root) + + _, tree4 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n")) + left := testRepo.CommitTree(t, tree4, "left", base1, base2) + + _, tree5 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n")) + right := testRepo.CommitTree(t, tree5, "right", base2, base1) + + testRepo.UpdateRef(t, "refs/heads/main", right) + testRepo.SymbolicRef(t, "HEAD", "refs/heads/main") + testRepo.CommitGraphWrite(t, "--reachable") + + store := testRepo.OpenObjectStore(t) + graph := testRepo.OpenCommitGraph(t) + + query := commitquery.New(store, graph) + + all, err := query.MergeBases(left, right) + if err != nil { + t.Fatalf("query.All(): %v", err) + } + + got := oidSetFromSlice(all) + + want := gitMergeBaseAllSet(t, testRepo, left, right) + if !maps.Equal(got, want) { + t.Fatalf("Query(left, right) with commit-graph mismatch:\n got=%v\nwant=%v", sortedOIDStrings(got), sortedOIDStrings(want)) + } + + first, ok, err := query.MergeBase(left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if !ok { + t.Fatal("Base(left, right) unexpectedly reported no base") + } + + if !containsID(want, first) { + t.Fatalf("Base(left, right)=%s, want one of %v", first, slices.Collect(maps.Keys(want))) + } + }) +} + +func TestBaseMatchesGitMergeBaseWithoutAll(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + testRepo := testgit.NewRepo(t, testgit.RepoOptions{ + ObjectFormat: algo, + Bare: true, + RefFormat: "files", + }) + + _, tree1 := testRepo.MakeSingleFileTree(t, "root.txt", []byte("root\n")) + root := testRepo.CommitTree(t, tree1, "root") + + _, tree2 := testRepo.MakeSingleFileTree(t, "base1.txt", []byte("base1\n")) + base1 := testRepo.CommitTreeWithEnv(t, []string{ + "GIT_AUTHOR_DATE=1234567890 +0000", + "GIT_COMMITTER_DATE=1234567890 +0000", + }, tree2, "base1", root) + + _, tree3 := testRepo.MakeSingleFileTree(t, "base2.txt", []byte("base2\n")) + base2 := testRepo.CommitTreeWithEnv(t, []string{ + "GIT_AUTHOR_DATE=1234567990 +0000", + "GIT_COMMITTER_DATE=1234567990 +0000", + }, tree3, "base2", root) + + _, tree4 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n")) + left := testRepo.CommitTree(t, tree4, "left", base1, base2) + + _, tree5 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n")) + right := testRepo.CommitTree(t, tree5, "right", base2, base1) + + store := testRepo.OpenObjectStore(t) + + query := commitquery.New(store, nil) + + got, ok, err := query.MergeBase(left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if !ok { + t.Fatal("Base(left, right) unexpectedly reported no base") + } + + want := gitMergeBaseOne(t, testRepo, left, right) + if got != want { + t.Fatalf("Base(left, right)=%s, want %s", got, want) + } + + testRepo.UpdateRef(t, "refs/heads/main", right) + testRepo.SymbolicRef(t, "HEAD", "refs/heads/main") + testRepo.CommitGraphWrite(t, "--reachable") + + graph := testRepo.OpenCommitGraph(t) + + got, ok, err = commitquery.New(store, graph).MergeBase(left, right) + if err != nil { + t.Fatalf("Base(left, right) with commit-graph: %v", err) + } + + if !ok { + t.Fatal("Base(left, right) with commit-graph unexpectedly reported no base") + } + + if got != want { + t.Fatalf("Base(left, right) with commit-graph=%s, want %s", got, want) + } + }) +} + +// oidSetFromSlice collects one object ID slice into a set. +func oidSetFromSlice(ids []objectid.ObjectID) map[objectid.ObjectID]struct{} { + out := make(map[objectid.ObjectID]struct{}) + + for _, id := range ids { + out[id] = struct{}{} + } + + return out +} + +// gitMergeBaseAllSet returns Git's merge-base --all output as a set. +func gitMergeBaseAllSet( + t *testing.T, + testRepo *testgit.TestRepo, + left objectid.ObjectID, + right objectid.ObjectID, +) map[objectid.ObjectID]struct{} { + t.Helper() + + out := testRepo.Run(t, "merge-base", "--all", left.String(), right.String()) + set := make(map[objectid.ObjectID]struct{}) + + for line := range strings.SplitSeq(strings.TrimSpace(out), "\n") { + line = strings.TrimSpace(line) + if line == "" { + continue + } + + id, err := objectid.ParseHex(testRepo.Algorithm(), line) + if err != nil { + t.Fatalf("parse merge-base oid %q: %v", line, err) + } + + set[id] = struct{}{} + } + + return set +} + +// gitMergeBaseOne returns Git's merge-base output without --all. +func gitMergeBaseOne( + t *testing.T, + testRepo *testgit.TestRepo, + left objectid.ObjectID, + right objectid.ObjectID, +) objectid.ObjectID { + t.Helper() + + out := strings.TrimSpace(testRepo.Run(t, "merge-base", left.String(), right.String())) + if out == "" { + t.Fatal("git merge-base returned no output") + } + + id, err := objectid.ParseHex(testRepo.Algorithm(), out) + if err != nil { + t.Fatalf("parse merge-base oid %q: %v", out, err) + } + + return id +} + +func sortedOIDStrings(set map[objectid.ObjectID]struct{}) []string { + out := make([]string, 0, len(set)) + for id := range set { + out = append(out, id.String()) + } + + slices.Sort(out) + + return out +} diff --git a/commitquery/mergebase_unit_test.go b/commitquery/mergebase_unit_test.go new file mode 100644 index 00000000..daa3c3c6 --- /dev/null +++ b/commitquery/mergebase_unit_test.go @@ -0,0 +1,332 @@ +package commitquery_test + +import ( + "errors" + "fmt" + "maps" + "slices" + "testing" + + "codeberg.org/lindenii/furgit/commitquery" + giterrors "codeberg.org/lindenii/furgit/errors" + "codeberg.org/lindenii/furgit/internal/testgit" + "codeberg.org/lindenii/furgit/object" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore/memory" + "codeberg.org/lindenii/furgit/objecttype" +) + +// commitBody serializes one minimal commit body. +func commitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte { + buf := fmt.Appendf(nil, "tree %s\n", tree.String()) + for _, parent := range parents { + buf = append(buf, fmt.Appendf(nil, "parent %s\n", parent.String())...) + } + + buf = append(buf, []byte("\nmsg\n")...) + + return buf +} + +// tagBody serializes one minimal annotated tag body. +func tagBody(target objectid.ObjectID, targetType objecttype.Type) []byte { + targetName, ok := objecttype.Name(targetType) + if !ok { + panic("invalid tag target type") + } + + return fmt.Appendf(nil, "object %s\ntype %s\ntag t\n\nmsg\n", target.String(), targetName) +} + +// toSet converts one slice of object IDs into a set. +func toSet(ids []objectid.ObjectID) map[objectid.ObjectID]struct{} { + set := make(map[objectid.ObjectID]struct{}, len(ids)) + for _, id := range ids { + set[id] = struct{}{} + } + + return set +} + +// containsID reports whether one set contains one object ID. +func containsID(set map[objectid.ObjectID]struct{}, id objectid.ObjectID) bool { + _, ok := set[id] + + return ok +} + +// mustSerializeTree serializes one tree or fails the test. +func mustSerializeTree(tb testing.TB, tree *object.Tree) []byte { + tb.Helper() + + body, err := tree.SerializeWithoutHeader() + if err != nil { + tb.Fatalf("SerializeWithoutHeader: %v", err) + } + + return body +} + +// TestQueryLinearHistory reports one linear-history merge base. +func TestQueryLinearHistory(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("f"), + ID: blob, + }}})) + base := store.AddObject(objecttype.TypeCommit, commitBody(tree)) + left := store.AddObject(objecttype.TypeCommit, commitBody(tree, base)) + right := store.AddObject(objecttype.TypeCommit, commitBody(tree, left)) + + query := commitquery.New(store, nil) + + got, err := query.MergeBases(left, right) + if err != nil { + t.Fatalf("query.All(): %v", err) + } + + if !slices.Equal(got, []objectid.ObjectID{left}) { + t.Fatalf("Query(left, right)=%v, want [%s]", got, left) + } + + first, ok, err := query.MergeBase(left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if !ok { + t.Fatal("Base(left, right) unexpectedly reported no base") + } + + if first != left { + t.Fatalf("Base(left, right)=%s, want %s", first, left) + } + }) +} + +func TestQueryPeelsAnnotatedTags(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("left"), + ID: blob, + }}})) + rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("right"), + ID: blob, + }}})) + base := store.AddObject(objecttype.TypeCommit, commitBody(leftTree)) + left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree, base)) + right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree, base)) + tag := store.AddObject(objecttype.TypeTag, tagBody(right, objecttype.TypeCommit)) + + query := commitquery.New(store, nil) + + got, err := query.MergeBases(left, tag) + if err != nil { + t.Fatalf("query.All(): %v", err) + } + + if !slices.Equal(got, []objectid.ObjectID{base}) { + t.Fatalf("Query(left, tag)=%v, want [%s]", got, base) + } + }) +} + +func TestQueryCrissCrossReturnsAllBestCommonAncestors(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + rootTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("root"), + ID: blob, + }}})) + base1Tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("base1"), + ID: blob, + }}})) + base2Tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("base2"), + ID: blob, + }}})) + leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("left"), + ID: blob, + }}})) + rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("right"), + ID: blob, + }}})) + root := store.AddObject(objecttype.TypeCommit, commitBody(rootTree)) + base1 := store.AddObject(objecttype.TypeCommit, commitBody(base1Tree, root)) + base2 := store.AddObject(objecttype.TypeCommit, commitBody(base2Tree, root)) + left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree, base1, base2)) + right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree, base2, base1)) + + query := commitquery.New(store, nil) + + all, err := query.MergeBases(left, right) + if err != nil { + t.Fatalf("query.All(): %v", err) + } + + got := toSet(all) + + want := map[objectid.ObjectID]struct{}{base1: {}, base2: {}} + if !maps.Equal(got, want) { + t.Fatalf("Query(left, right)=%v, want %v", slices.Collect(maps.Keys(got)), slices.Collect(maps.Keys(want))) + } + + first, ok, err := query.MergeBase(left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if !ok { + t.Fatal("Base(left, right) unexpectedly reported no base") + } + + if !containsID(want, first) { + t.Fatalf("Base(left, right)=%s, want one of %v", first, slices.Collect(maps.Keys(want))) + } + }) +} + +func TestQueryReturnsNoResultWhenNoCommonAncestorExists(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + leftBlob := store.AddObject(objecttype.TypeBlob, []byte("left\n")) + leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("left"), + ID: leftBlob, + }}})) + rightBlob := store.AddObject(objecttype.TypeBlob, []byte("right\n")) + rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("right"), + ID: rightBlob, + }}})) + left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree)) + right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree)) + + query := commitquery.New(store, nil) + + got, err := query.MergeBases(left, right) + if err != nil { + t.Fatalf("query.All(): %v", err) + } + + if len(got) != 0 { + t.Fatalf("Query(left, right)=%v, want no results", got) + } + + _, ok, err := query.MergeBase(left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if ok { + t.Fatal("Base(left, right) unexpectedly reported a base") + } + }) +} + +func TestQueryRejectsNonCommitAfterPeel(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("f"), + ID: blob, + }}})) + commit := store.AddObject(objecttype.TypeCommit, commitBody(tree)) + tagToTree := store.AddObject(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree)) + + query := commitquery.New(store, nil) + + _, err := query.MergeBases(commit, tagToTree) + if err == nil { + t.Fatal("expected error") + } + + typeErr, ok := errors.AsType[*giterrors.ObjectTypeError](err) + if !ok { + t.Fatalf("expected ObjectTypeError, got %T (%v)", err, err) + } + + if typeErr.Got != objecttype.TypeTree || typeErr.Want != objecttype.TypeCommit { + t.Fatalf("unexpected type error: %+v", typeErr) + } + }) +} + +func TestQueryAllIsRepeatable(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("f"), + ID: blob, + }}})) + base := store.AddObject(objecttype.TypeCommit, commitBody(tree)) + left := store.AddObject(objecttype.TypeCommit, commitBody(tree, base)) + right := store.AddObject(objecttype.TypeCommit, commitBody(tree, left)) + + query := commitquery.New(store, nil) + + first, err := query.MergeBases(left, right) + if err != nil { + t.Fatalf("query.MergeBases() first call: %v", err) + } + + again, err := query.MergeBases(left, right) + if err != nil { + t.Fatalf("query.MergeBases() second call: %v", err) + } + + if !slices.Equal(again, first) { + t.Fatalf("second All()=%v, want %v", again, first) + } + + if len(first) == 0 { + t.Fatal("first MergeBases() unexpectedly returned no results") + } + + first[0] = objectid.ObjectID{} + + third, err := query.MergeBases(left, right) + if err != nil { + t.Fatalf("query.MergeBases() third call: %v", err) + } + + if third[0] == (objectid.ObjectID{}) { + t.Fatal("query.MergeBases() exposed internal slice state") + } + }) +} diff --git a/commitquery/node.go b/commitquery/node.go new file mode 100644 index 00000000..cd357631 --- /dev/null +++ b/commitquery/node.go @@ -0,0 +1,39 @@ +package commitquery + +import ( + commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" +) + +// nodeIndex identifies one internal query node. +type nodeIndex int + +// node stores one mutable commit traversal node. +type node struct { + id objectid.ObjectID + + parents []nodeIndex + + commitTime int64 + generation uint64 + + hasGeneration bool + hasGraphPos bool + loaded bool + + graphPos commitgraphread.Position + marks markBits + + touchedPhase uint32 +} + +// newNode allocates one empty internal node. +func (query *Query) newNode(id objectid.ObjectID) nodeIndex { + count := len(query.nodes) + + idx := nodeIndex(count) + + query.nodes = append(query.nodes, node{id: id}) + + return idx +} diff --git a/commitquery/oid.go b/commitquery/oid.go new file mode 100644 index 00000000..68adbf5d --- /dev/null +++ b/commitquery/oid.go @@ -0,0 +1,101 @@ +package commitquery + +import ( + stderrors "errors" + + commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" + giterrors "codeberg.org/lindenii/furgit/errors" + "codeberg.org/lindenii/furgit/internal/peel" + "codeberg.org/lindenii/furgit/object" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore" + "codeberg.org/lindenii/furgit/objecttype" +) + +func (query *Query) id(idx nodeIndex) objectid.ObjectID { + return query.nodes[idx].id +} + +func (query *Query) commitTime(idx nodeIndex) int64 { + return query.nodes[idx].commitTime +} + +func (query *Query) resolveOID(id objectid.ObjectID) (nodeIndex, error) { + idx, ok := query.byOID[id] + if ok { + err := query.ensureLoaded(idx) + if err != nil { + return 0, err + } + + return idx, nil + } + + idx = query.newNode(id) + query.byOID[id] = idx + + err := query.loadByOID(idx) + if err != nil { + delete(query.byOID, id) + + return 0, err + } + + return idx, nil +} + +func (query *Query) resolveCommitish(id objectid.ObjectID) (nodeIndex, error) { + commitID, err := peel.ToCommit(query.store, id) + if err != nil { + return 0, err + } + + return query.resolveOID(commitID) +} + +// loadByOID populates one node from an object ID. +func (query *Query) loadByOID(idx nodeIndex) error { + id := query.nodes[idx].id + + if query.graph != nil { + pos, err := query.graph.Lookup(id) + if err != nil { + if _, ok := stderrors.AsType[*commitgraphread.NotFoundError](err); !ok { + return err + } + } else { + return query.loadCommitAtGraphPos(idx, pos) + } + } + + ty, content, err := query.store.ReadBytesContent(id) + if err != nil { + if stderrors.Is(err, objectstore.ErrObjectNotFound) { + return &giterrors.ObjectMissingError{OID: id} + } + + return err + } + + if ty != objecttype.TypeCommit { + return &giterrors.ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit} + } + + commitObj, err := object.ParseCommit(content, id.Algorithm()) + if err != nil { + return err + } + + parents := make([]parentRef, 0, len(commitObj.Parents)) + for _, parentID := range commitObj.Parents { + parents = append(parents, parentRef{ID: parentID}) + } + + commit := commitData{ + ID: id, + Parents: parents, + CommitTime: commitObj.Committer.WhenUnix, + } + + return query.populateNode(idx, commit) +} diff --git a/commitquery/parent.go b/commitquery/parent.go new file mode 100644 index 00000000..1c59e102 --- /dev/null +++ b/commitquery/parent.go @@ -0,0 +1,27 @@ +package commitquery + +import ( + commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" +) + +// parentRef references one commit parent. +type parentRef struct { + ID objectid.ObjectID + GraphPos commitgraphread.Position + HasGraphPos bool +} + +// Parents returns resolved parent node indices for one internal node. +func (query *Query) parents(idx nodeIndex) []nodeIndex { + return query.nodes[idx].parents +} + +// resolveParent resolves one parent descriptor to one internal node. +func (query *Query) resolveParent(parent parentRef) (nodeIndex, error) { + if parent.HasGraphPos { + return query.resolveGraphPos(parent.GraphPos) + } + + return query.resolveOID(parent.ID) +} diff --git a/commitquery/populate.go b/commitquery/populate.go new file mode 100644 index 00000000..cc71955f --- /dev/null +++ b/commitquery/populate.go @@ -0,0 +1,42 @@ +package commitquery + +import "fmt" + +// populateNode fills one node's metadata and resolves its parents. +func (query *Query) populateNode(idx nodeIndex, commit commitData) error { + if query.nodes[idx].loaded { + if query.nodes[idx].id != commit.ID { + return fmt.Errorf("commitquery: node identity mismatch: have %s, got %s", query.nodes[idx].id, commit.ID) + } + + return nil + } + + query.nodes[idx].id = commit.ID + query.nodes[idx].commitTime = commit.CommitTime + query.nodes[idx].generation = commit.Generation + query.nodes[idx].hasGeneration = commit.HasGeneration + + if commit.HasGraphPos { + query.nodes[idx].graphPos = commit.GraphPos + query.nodes[idx].hasGraphPos = true + query.byGraphPos[commit.GraphPos] = idx + } + + query.nodes[idx].loaded = true + query.nodes[idx].parents = query.nodes[idx].parents[:0] + + for _, parent := range commit.Parents { + parentIdx, err := query.resolveParent(parent) + if err != nil { + query.nodes[idx].loaded = false + query.nodes[idx].parents = nil + + return err + } + + query.nodes[idx].parents = append(query.nodes[idx].parents, parentIdx) + } + + return nil +} diff --git a/commitquery/priority_queue.go b/commitquery/priority_queue.go new file mode 100644 index 00000000..0ca57f7d --- /dev/null +++ b/commitquery/priority_queue.go @@ -0,0 +1,68 @@ +package commitquery + +import "container/heap" + +// priorityQueue orders internal nodes using one query context's comparator. +type priorityQueue struct { + query *Query + items []nodeIndex +} + +// newPriorityQueue builds one empty priority queue over one query context. +func newPriorityQueue(query *Query) *priorityQueue { + queue := &priorityQueue{query: query} + heap.Init(queue) + + return queue +} + +// Len reports the number of queued items. +func (queue *priorityQueue) Len() int { + return len(queue.items) +} + +// Less reports whether one heap slot sorts ahead of another. +func (queue *priorityQueue) Less(left, right int) bool { + return queue.query.compare(queue.items[left], queue.items[right]) > 0 +} + +// Swap exchanges two heap slots. +func (queue *priorityQueue) Swap(left, right int) { + queue.items[left], queue.items[right] = queue.items[right], queue.items[left] +} + +// Push appends one heap element. +func (queue *priorityQueue) Push(item any) { + idx, ok := item.(nodeIndex) + if !ok { + panic("commitquery: heap push item is not a nodeIndex") + } + + queue.items = append(queue.items, idx) +} + +// Pop removes one heap element. +func (queue *priorityQueue) Pop() any { + last := len(queue.items) - 1 + item := queue.items[last] + queue.items = queue.items[:last] + + return item +} + +// PushNode inserts one internal node. +func (queue *priorityQueue) PushNode(idx nodeIndex) { + heap.Push(queue, idx) +} + +// PopNode removes the highest-priority internal node. +func (queue *priorityQueue) PopNode() nodeIndex { + item := heap.Pop(queue) + + idx, ok := item.(nodeIndex) + if !ok { + panic("commitquery: heap pop item is not a nodeIndex") + } + + return idx +} diff --git a/commitquery/reduce.go b/commitquery/reduce.go new file mode 100644 index 00000000..ac85d619 --- /dev/null +++ b/commitquery/reduce.go @@ -0,0 +1,166 @@ +package commitquery + +import ( + "slices" +) + +// removeRedundant removes redundant merge-base candidates. +func removeRedundant(query *Query, candidates []nodeIndex) ([]nodeIndex, error) { + for _, idx := range candidates { + if query.effectiveGeneration(idx) != generationInfinity { + return removeRedundantWithGen(query, candidates), nil + } + } + + return removeRedundantNoGen(query, candidates) +} + +func removeRedundantNoGen(query *Query, candidates []nodeIndex) ([]nodeIndex, error) { + redundant := make([]bool, len(candidates)) + work := make([]nodeIndex, 0, len(candidates)-1) + filledIndex := make([]int, 0, len(candidates)-1) + + for i, candidate := range candidates { + if redundant[i] { + continue + } + + work = work[:0] + filledIndex = filledIndex[:0] + + minGeneration := query.effectiveGeneration(candidate) + + for j, other := range candidates { + if i == j || redundant[j] { + continue + } + + work = append(work, other) + filledIndex = append(filledIndex, j) + + otherGeneration := query.effectiveGeneration(other) + if otherGeneration < minGeneration { + minGeneration = otherGeneration + } + } + + err := query.paintDownToCommon(candidate, work, minGeneration) + if err != nil { + return nil, err + } + + if query.hasAnyMarks(candidate, markRight) { + redundant[i] = true + } + + for j, other := range work { + if query.hasAnyMarks(other, markLeft) { + redundant[filledIndex[j]] = true + } + } + + query.clearTouchedMarks(allMarks) + } + + out := make([]nodeIndex, 0, len(candidates)) + for i, idx := range candidates { + if !redundant[i] { + out = append(out, idx) + } + } + + return out, nil +} + +func removeRedundantWithGen(query *Query, candidates []nodeIndex) []nodeIndex { + sorted := append([]nodeIndex(nil), candidates...) + slices.SortFunc(sorted, compareByGeneration(query)) + + minGeneration := query.effectiveGeneration(sorted[0]) + minGenPos := 0 + countStillIndependent := len(candidates) + + query.beginMarkPhase() + + walkStart := make([]nodeIndex, 0, len(candidates)*2) + + for _, idx := range candidates { + query.setMarks(idx, markResult) + + for _, parent := range query.parents(idx) { + if query.hasAnyMarks(parent, markStale) { + continue + } + + query.setMarks(parent, markStale) + walkStart = append(walkStart, parent) + } + } + + slices.SortFunc(walkStart, compareByGeneration(query)) + + for _, idx := range walkStart { + query.clearMarks(idx, markStale) + } + + for i := len(walkStart) - 1; i >= 0 && countStillIndependent > 1; i-- { + stack := []nodeIndex{walkStart[i]} + query.setMarks(walkStart[i], markStale) + + for len(stack) > 0 { + top := stack[len(stack)-1] + + if query.hasAnyMarks(top, markResult) { + query.clearMarks(top, markResult) + + countStillIndependent-- + if countStillIndependent <= 1 { + break + } + + if top == sorted[minGenPos] { + for minGenPos < len(sorted)-1 && query.hasAnyMarks(sorted[minGenPos], markStale) { + minGenPos++ + } + + minGeneration = query.effectiveGeneration(sorted[minGenPos]) + } + } + + if query.effectiveGeneration(top) < minGeneration { + stack = stack[:len(stack)-1] + + continue + } + + pushed := false + + for _, parent := range query.parents(top) { + if query.hasAnyMarks(parent, markStale) { + continue + } + + query.setMarks(parent, markStale) + stack = append(stack, parent) + pushed = true + + break + } + + if !pushed { + stack = stack[:len(stack)-1] + } + } + } + + out := make([]nodeIndex, 0, len(candidates)) + for _, idx := range candidates { + if !query.hasAnyMarks(idx, markStale) { + out = append(out, idx) + } + } + + query.clearTouchedMarks(markStale | markResult) + + return out +} -- cgit v1.3.1-10-gc9f91