diff options
37 files changed, 846 insertions, 951 deletions
diff --git a/ancestor/ancestor.go b/ancestor/ancestor.go deleted file mode 100644 index 51684250..00000000 --- a/ancestor/ancestor.go +++ /dev/null @@ -1,45 +0,0 @@ -// Package ancestor answers commit ancestry queries. -package ancestor - -import ( - commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" - "codeberg.org/lindenii/furgit/internal/commitquery" - "codeberg.org/lindenii/furgit/internal/peel" - "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/objectstore" -) - -// Is reports whether ancestor is reachable from descendant through commit -// parent edges. -// -// Both inputs are peeled through annotated tags before commit traversal. -func Is( - store objectstore.Store, - graph *commitgraphread.Reader, - ancestor objectid.ObjectID, - descendant objectid.ObjectID, -) (bool, error) { - ancestorCommit, err := peel.ToCommit(store, ancestor) - if err != nil { - return false, err - } - - descendantCommit, err := peel.ToCommit(store, descendant) - if err != nil { - return false, err - } - - ctx := commitquery.NewContext(store, graph) - - ancestorIdx, err := ctx.ResolveOID(ancestorCommit) - if err != nil { - return false, err - } - - descendantIdx, err := ctx.ResolveOID(descendantCommit) - if err != nil { - return false, err - } - - return commitquery.IsAncestor(ctx, ancestorIdx, descendantIdx) -} 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/ancestor/integration_test.go b/commitquery/ancestor_integration_test.go index fa630f57..a25697aa 100644 --- a/ancestor/integration_test.go +++ b/commitquery/ancestor_integration_test.go @@ -1,14 +1,13 @@ -package ancestor_test +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" - - "codeberg.org/lindenii/furgit/ancestor" ) func TestIsMatchesGitMergeBase(t *testing.T) { @@ -34,7 +33,7 @@ func TestIsMatchesGitMergeBase(t *testing.T) { store := testRepo.OpenObjectStore(t) - got, err := ancestor.Is(store, nil, c1, tag) + got, err := commitquery.New(store, nil).IsAncestor(c1, tag) if err != nil { t.Fatalf("Is(c1, tag): %v", err) } @@ -44,7 +43,7 @@ func TestIsMatchesGitMergeBase(t *testing.T) { t.Fatalf("Is(c1, tag)=%v, want %v", got, want) } - got, err = ancestor.Is(store, nil, c3, c2) + got, err = commitquery.New(store, nil).IsAncestor(c3, c2) if err != nil { t.Fatalf("Is(c3, c2): %v", err) } @@ -79,7 +78,7 @@ func TestIsMatchesGitMergeBaseWithCommitGraph(t *testing.T) { store := testRepo.OpenObjectStore(t) graph := testRepo.OpenCommitGraph(t) - got, err := ancestor.Is(store, graph, c1, c2) + got, err := commitquery.New(store, graph).IsAncestor(c1, c2) if err != nil { t.Fatalf("Is(c1, c2): %v", err) } @@ -107,7 +106,7 @@ func TestIsMissingObject(t *testing.T) { store := testRepo.OpenObjectStore(t) - _, err := ancestor.Is(store, nil, treeID, commitID) + _, err := commitquery.New(store, nil).IsAncestor(treeID, commitID) if err == nil { t.Fatal("expected error") } diff --git a/ancestor/unit_test.go b/commitquery/ancestor_unit_test.go index b6ca7b58..6edb05be 100644 --- a/ancestor/unit_test.go +++ b/commitquery/ancestor_unit_test.go @@ -1,4 +1,4 @@ -package ancestor_test +package commitquery_test import ( "errors" @@ -12,11 +12,11 @@ import ( "codeberg.org/lindenii/furgit/objectstore/memory" "codeberg.org/lindenii/furgit/objecttype" - "codeberg.org/lindenii/furgit/ancestor" + "codeberg.org/lindenii/furgit/commitquery" ) -// commitBody serializes one minimal commit body. -func commitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte { +// 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())...) @@ -27,8 +27,8 @@ func commitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte { return buf } -// tagBody serializes one minimal annotated tag body. -func tagBody(target objectid.ObjectID, targetType objecttype.Type) []byte { +// 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") @@ -37,8 +37,8 @@ func tagBody(target objectid.ObjectID, targetType objecttype.Type) []byte { return fmt.Appendf(nil, "object %s\ntype %s\ntag t\n\nmsg\n", target.String(), targetName) } -// mustSerializeTree serializes one tree or fails the test. -func mustSerializeTree(tb testing.TB, tree *object.Tree) []byte { +// mustSerializeAncestorTree serializes one tree or fails the test. +func mustSerializeAncestorTree(tb testing.TB, tree *object.Tree) []byte { tb.Helper() body, err := tree.SerializeWithoutHeader() @@ -55,23 +55,23 @@ func TestIs(t *testing.T) { 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{{ + 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, commitBody(tree)) - c2 := store.AddObject(objecttype.TypeCommit, commitBody(tree, c1)) + 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, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + 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, commitBody(otherTree)) - tag := store.AddObject(objecttype.TypeTag, tagBody(c2, objecttype.TypeCommit)) + c3 := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(otherTree)) + tag := store.AddObject(objecttype.TypeTag, ancestorTagBody(c2, objecttype.TypeCommit)) - ok, err := ancestor.Is(store, nil, c1, tag) + ok, err := commitquery.New(store, nil).IsAncestor(c1, tag) if err != nil { t.Fatalf("Is(c1, tag): %v", err) } @@ -80,7 +80,7 @@ func TestIs(t *testing.T) { t.Fatal("expected c1 to be ancestor of tag->c2") } - ok, err = ancestor.Is(store, nil, c3, c2) + ok, err = commitquery.New(store, nil).IsAncestor(c3, c2) if err != nil { t.Fatalf("Is(c3, c2): %v", err) } @@ -97,15 +97,15 @@ func TestIsRejectsNonCommitAfterPeel(t *testing.T) { 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{{ + 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, commitBody(tree)) - tagToTree := store.AddObject(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree)) + commit := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(tree)) + tagToTree := store.AddObject(objecttype.TypeTag, ancestorTagBody(tree, objecttype.TypeTree)) - _, err := ancestor.Is(store, nil, commit, tagToTree) + _, err := commitquery.New(store, nil).IsAncestor(commit, tagToTree) if err == nil { t.Fatal("expected error") } diff --git a/internal/commitquery/bits.go b/commitquery/bits.go index 36ffff29..36ffff29 100644 --- a/internal/commitquery/bits.go +++ b/commitquery/bits.go diff --git a/internal/commitquery/commit.go b/commitquery/commit.go index fccd52b2..f4709270 100644 --- a/internal/commitquery/commit.go +++ b/commitquery/commit.go @@ -5,10 +5,10 @@ import ( "codeberg.org/lindenii/furgit/objectid" ) -// Commit stores the metadata needed by commit-domain queries. -type Commit struct { +// commitData stores the metadata needed by commit-domain queries. +type commitData struct { ID objectid.ObjectID - Parents []Parent + Parents []parentRef CommitTime int64 Generation uint64 HasGeneration 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/internal/commitquery/errors.go b/commitquery/errors.go index e99011d0..e99011d0 100644 --- a/internal/commitquery/errors.go +++ b/commitquery/errors.go 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/mergebase/integration_test.go b/commitquery/mergebase_integration_test.go index 3d85409d..30477454 100644 --- a/mergebase/integration_test.go +++ b/commitquery/mergebase_integration_test.go @@ -1,4 +1,4 @@ -package mergebase_test +package commitquery_test import ( "maps" @@ -6,8 +6,8 @@ import ( "strings" "testing" + "codeberg.org/lindenii/furgit/commitquery" "codeberg.org/lindenii/furgit/internal/testgit" - "codeberg.org/lindenii/furgit/mergebase" "codeberg.org/lindenii/furgit/objectid" ) @@ -34,9 +34,9 @@ func TestQueryMatchesGitMergeBaseAll(t *testing.T) { store := testRepo.OpenObjectStore(t) - query := mergebase.Query(store, nil, left, tag) + query := commitquery.New(store, nil) - all, err := query.All() + all, err := query.MergeBases(left, tag) if err != nil { t.Fatalf("query.All(): %v", err) } @@ -77,9 +77,9 @@ func TestQueryCrissCrossMatchesGitMergeBaseAll(t *testing.T) { store := testRepo.OpenObjectStore(t) - query := mergebase.Query(store, nil, left, right) + query := commitquery.New(store, nil) - all, err := query.All() + all, err := query.MergeBases(left, right) if err != nil { t.Fatalf("query.All(): %v", err) } @@ -91,7 +91,7 @@ func TestQueryCrissCrossMatchesGitMergeBaseAll(t *testing.T) { t.Fatalf("Query(left, right) mismatch:\n got=%v\nwant=%v", sortedOIDStrings(got), sortedOIDStrings(want)) } - first, ok, err := mergebase.Base(store, nil, left, right) + first, ok, err := query.MergeBase(left, right) if err != nil { t.Fatalf("Base(left, right): %v", err) } @@ -138,9 +138,9 @@ func TestQueryMatchesGitMergeBaseAllWithCommitGraph(t *testing.T) { store := testRepo.OpenObjectStore(t) graph := testRepo.OpenCommitGraph(t) - query := mergebase.Query(store, graph, left, right) + query := commitquery.New(store, graph) - all, err := query.All() + all, err := query.MergeBases(left, right) if err != nil { t.Fatalf("query.All(): %v", err) } @@ -152,7 +152,7 @@ func TestQueryMatchesGitMergeBaseAllWithCommitGraph(t *testing.T) { t.Fatalf("Query(left, right) with commit-graph mismatch:\n got=%v\nwant=%v", sortedOIDStrings(got), sortedOIDStrings(want)) } - first, ok, err := mergebase.Base(store, graph, left, right) + first, ok, err := query.MergeBase(left, right) if err != nil { t.Fatalf("Base(left, right): %v", err) } @@ -200,7 +200,9 @@ func TestBaseMatchesGitMergeBaseWithoutAll(t *testing.T) { store := testRepo.OpenObjectStore(t) - got, ok, err := mergebase.Base(store, nil, left, right) + query := commitquery.New(store, nil) + + got, ok, err := query.MergeBase(left, right) if err != nil { t.Fatalf("Base(left, right): %v", err) } @@ -220,7 +222,7 @@ func TestBaseMatchesGitMergeBaseWithoutAll(t *testing.T) { graph := testRepo.OpenCommitGraph(t) - got, ok, err = mergebase.Base(store, graph, left, right) + got, ok, err = commitquery.New(store, graph).MergeBase(left, right) if err != nil { t.Fatalf("Base(left, right) with commit-graph: %v", err) } diff --git a/mergebase/unit_test.go b/commitquery/mergebase_unit_test.go index 7ba1ed66..daa3c3c6 100644 --- a/mergebase/unit_test.go +++ b/commitquery/mergebase_unit_test.go @@ -1,4 +1,4 @@ -package mergebase_test +package commitquery_test import ( "errors" @@ -7,9 +7,9 @@ import ( "slices" "testing" + "codeberg.org/lindenii/furgit/commitquery" giterrors "codeberg.org/lindenii/furgit/errors" "codeberg.org/lindenii/furgit/internal/testgit" - "codeberg.org/lindenii/furgit/mergebase" "codeberg.org/lindenii/furgit/object" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objectstore/memory" @@ -83,9 +83,9 @@ func TestQueryLinearHistory(t *testing.T) { left := store.AddObject(objecttype.TypeCommit, commitBody(tree, base)) right := store.AddObject(objecttype.TypeCommit, commitBody(tree, left)) - query := mergebase.Query(store, nil, left, right) + query := commitquery.New(store, nil) - got, err := query.All() + got, err := query.MergeBases(left, right) if err != nil { t.Fatalf("query.All(): %v", err) } @@ -94,7 +94,7 @@ func TestQueryLinearHistory(t *testing.T) { t.Fatalf("Query(left, right)=%v, want [%s]", got, left) } - first, ok, err := mergebase.Base(store, nil, left, right) + first, ok, err := query.MergeBase(left, right) if err != nil { t.Fatalf("Base(left, right): %v", err) } @@ -130,9 +130,9 @@ func TestQueryPeelsAnnotatedTags(t *testing.T) { right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree, base)) tag := store.AddObject(objecttype.TypeTag, tagBody(right, objecttype.TypeCommit)) - query := mergebase.Query(store, nil, left, tag) + query := commitquery.New(store, nil) - got, err := query.All() + got, err := query.MergeBases(left, tag) if err != nil { t.Fatalf("query.All(): %v", err) } @@ -180,9 +180,9 @@ func TestQueryCrissCrossReturnsAllBestCommonAncestors(t *testing.T) { left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree, base1, base2)) right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree, base2, base1)) - query := mergebase.Query(store, nil, left, right) + query := commitquery.New(store, nil) - all, err := query.All() + all, err := query.MergeBases(left, right) if err != nil { t.Fatalf("query.All(): %v", err) } @@ -194,7 +194,7 @@ func TestQueryCrissCrossReturnsAllBestCommonAncestors(t *testing.T) { t.Fatalf("Query(left, right)=%v, want %v", slices.Collect(maps.Keys(got)), slices.Collect(maps.Keys(want))) } - first, ok, err := mergebase.Base(store, nil, left, right) + first, ok, err := query.MergeBase(left, right) if err != nil { t.Fatalf("Base(left, right): %v", err) } @@ -229,9 +229,9 @@ func TestQueryReturnsNoResultWhenNoCommonAncestorExists(t *testing.T) { left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree)) right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree)) - query := mergebase.Query(store, nil, left, right) + query := commitquery.New(store, nil) - got, err := query.All() + got, err := query.MergeBases(left, right) if err != nil { t.Fatalf("query.All(): %v", err) } @@ -240,7 +240,7 @@ func TestQueryReturnsNoResultWhenNoCommonAncestorExists(t *testing.T) { t.Fatalf("Query(left, right)=%v, want no results", got) } - _, ok, err := mergebase.Base(store, nil, left, right) + _, ok, err := query.MergeBase(left, right) if err != nil { t.Fatalf("Base(left, right): %v", err) } @@ -265,9 +265,9 @@ func TestQueryRejectsNonCommitAfterPeel(t *testing.T) { commit := store.AddObject(objecttype.TypeCommit, commitBody(tree)) tagToTree := store.AddObject(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree)) - query := mergebase.Query(store, nil, commit, tagToTree) + query := commitquery.New(store, nil) - _, err := query.All() + _, err := query.MergeBases(commit, tagToTree) if err == nil { t.Fatal("expected error") } @@ -298,16 +298,16 @@ func TestQueryAllIsRepeatable(t *testing.T) { left := store.AddObject(objecttype.TypeCommit, commitBody(tree, base)) right := store.AddObject(objecttype.TypeCommit, commitBody(tree, left)) - query := mergebase.Query(store, nil, left, right) + query := commitquery.New(store, nil) - first, err := query.All() + first, err := query.MergeBases(left, right) if err != nil { - t.Fatalf("query.All() first call: %v", err) + t.Fatalf("query.MergeBases() first call: %v", err) } - again, err := query.All() + again, err := query.MergeBases(left, right) if err != nil { - t.Fatalf("query.All() second call: %v", err) + t.Fatalf("query.MergeBases() second call: %v", err) } if !slices.Equal(again, first) { @@ -315,18 +315,18 @@ func TestQueryAllIsRepeatable(t *testing.T) { } if len(first) == 0 { - t.Fatal("first All() unexpectedly returned no results") + t.Fatal("first MergeBases() unexpectedly returned no results") } first[0] = objectid.ObjectID{} - third, err := query.All() + third, err := query.MergeBases(left, right) if err != nil { - t.Fatalf("query.All() third call: %v", err) + t.Fatalf("query.MergeBases() third call: %v", err) } if third[0] == (objectid.ObjectID{}) { - t.Fatal("query.All() exposed internal slice state") + t.Fatal("query.MergeBases() exposed internal slice state") } }) } diff --git a/internal/commitquery/node.go b/commitquery/node.go index f4979bfe..cd357631 100644 --- a/internal/commitquery/node.go +++ b/commitquery/node.go @@ -5,14 +5,14 @@ import ( "codeberg.org/lindenii/furgit/objectid" ) -// NodeIndex identifies one internal query node. -type NodeIndex int +// nodeIndex identifies one internal query node. +type nodeIndex int // node stores one mutable commit traversal node. type node struct { id objectid.ObjectID - parents []NodeIndex + parents []nodeIndex commitTime int64 generation uint64 @@ -28,12 +28,12 @@ type node struct { } // newNode allocates one empty internal node. -func (ctx *Context) newNode(id objectid.ObjectID) NodeIndex { - count := len(ctx.nodes) +func (query *Query) newNode(id objectid.ObjectID) nodeIndex { + count := len(query.nodes) - idx := NodeIndex(count) + idx := nodeIndex(count) - ctx.nodes = append(ctx.nodes, node{id: id}) + query.nodes = append(query.nodes, node{id: id}) return idx } diff --git a/internal/commitquery/oid.go b/commitquery/oid.go index 927c0220..68adbf5d 100644 --- a/internal/commitquery/oid.go +++ b/commitquery/oid.go @@ -5,27 +5,25 @@ import ( 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" ) -// ID returns the canonical object ID of one internal node. -func (ctx *Context) ID(idx NodeIndex) objectid.ObjectID { - return ctx.nodes[idx].id +func (query *Query) id(idx nodeIndex) objectid.ObjectID { + return query.nodes[idx].id } -// CommitTime returns the committer timestamp used for one internal node. -func (ctx *Context) CommitTime(idx NodeIndex) int64 { - return ctx.nodes[idx].commitTime +func (query *Query) commitTime(idx nodeIndex) int64 { + return query.nodes[idx].commitTime } -// ResolveOID resolves one commit object ID to one internal query node. -func (ctx *Context) ResolveOID(id objectid.ObjectID) (NodeIndex, error) { - idx, ok := ctx.byOID[id] +func (query *Query) resolveOID(id objectid.ObjectID) (nodeIndex, error) { + idx, ok := query.byOID[id] if ok { - err := ctx.ensureLoaded(idx) + err := query.ensureLoaded(idx) if err != nil { return 0, err } @@ -33,12 +31,12 @@ func (ctx *Context) ResolveOID(id objectid.ObjectID) (NodeIndex, error) { return idx, nil } - idx = ctx.newNode(id) - ctx.byOID[id] = idx + idx = query.newNode(id) + query.byOID[id] = idx - err := ctx.loadByOID(idx) + err := query.loadByOID(idx) if err != nil { - delete(ctx.byOID, id) + delete(query.byOID, id) return 0, err } @@ -46,22 +44,31 @@ func (ctx *Context) ResolveOID(id objectid.ObjectID) (NodeIndex, error) { 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 (ctx *Context) loadByOID(idx NodeIndex) error { - id := ctx.nodes[idx].id +func (query *Query) loadByOID(idx nodeIndex) error { + id := query.nodes[idx].id - if ctx.graph != nil { - pos, err := ctx.graph.Lookup(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 ctx.loadCommitAtGraphPos(idx, pos) + return query.loadCommitAtGraphPos(idx, pos) } } - ty, content, err := ctx.store.ReadBytesContent(id) + ty, content, err := query.store.ReadBytesContent(id) if err != nil { if stderrors.Is(err, objectstore.ErrObjectNotFound) { return &giterrors.ObjectMissingError{OID: id} @@ -79,16 +86,16 @@ func (ctx *Context) loadByOID(idx NodeIndex) error { return err } - parents := make([]Parent, 0, len(commitObj.Parents)) + parents := make([]parentRef, 0, len(commitObj.Parents)) for _, parentID := range commitObj.Parents { - parents = append(parents, Parent{ID: parentID}) + parents = append(parents, parentRef{ID: parentID}) } - commit := Commit{ + commit := commitData{ ID: id, Parents: parents, CommitTime: commitObj.Committer.WhenUnix, } - return ctx.populateNode(idx, commit) + return query.populateNode(idx, commit) } diff --git a/internal/commitquery/parent.go b/commitquery/parent.go index 809a1fd5..1c59e102 100644 --- a/internal/commitquery/parent.go +++ b/commitquery/parent.go @@ -5,23 +5,23 @@ import ( "codeberg.org/lindenii/furgit/objectid" ) -// Parent references one commit parent. -type Parent struct { +// 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 (ctx *Context) Parents(idx NodeIndex) []NodeIndex { - return ctx.nodes[idx].parents +func (query *Query) parents(idx nodeIndex) []nodeIndex { + return query.nodes[idx].parents } // resolveParent resolves one parent descriptor to one internal node. -func (ctx *Context) resolveParent(parent Parent) (NodeIndex, error) { +func (query *Query) resolveParent(parent parentRef) (nodeIndex, error) { if parent.HasGraphPos { - return ctx.ResolveGraphPos(parent.GraphPos) + return query.resolveGraphPos(parent.GraphPos) } - return ctx.ResolveOID(parent.ID) + 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/internal/commitquery/priority_queue.go b/commitquery/priority_queue.go index d6dbf54f..0ca57f7d 100644 --- a/internal/commitquery/priority_queue.go +++ b/commitquery/priority_queue.go @@ -4,13 +4,13 @@ import "container/heap" // priorityQueue orders internal nodes using one query context's comparator. type priorityQueue struct { - ctx *Context - items []NodeIndex + query *Query + items []nodeIndex } // newPriorityQueue builds one empty priority queue over one query context. -func newPriorityQueue(ctx *Context) *priorityQueue { - queue := &priorityQueue{ctx: ctx} +func newPriorityQueue(query *Query) *priorityQueue { + queue := &priorityQueue{query: query} heap.Init(queue) return queue @@ -23,7 +23,7 @@ func (queue *priorityQueue) Len() int { // Less reports whether one heap slot sorts ahead of another. func (queue *priorityQueue) Less(left, right int) bool { - return queue.ctx.Compare(queue.items[left], queue.items[right]) > 0 + return queue.query.compare(queue.items[left], queue.items[right]) > 0 } // Swap exchanges two heap slots. @@ -33,9 +33,9 @@ func (queue *priorityQueue) Swap(left, right int) { // Push appends one heap element. func (queue *priorityQueue) Push(item any) { - idx, ok := item.(NodeIndex) + idx, ok := item.(nodeIndex) if !ok { - panic("commitquery: heap push item is not a NodeIndex") + panic("commitquery: heap push item is not a nodeIndex") } queue.items = append(queue.items, idx) @@ -51,17 +51,17 @@ func (queue *priorityQueue) Pop() any { } // PushNode inserts one internal node. -func (queue *priorityQueue) PushNode(idx NodeIndex) { +func (queue *priorityQueue) PushNode(idx nodeIndex) { heap.Push(queue, idx) } // PopNode removes the highest-priority internal node. -func (queue *priorityQueue) PopNode() NodeIndex { +func (queue *priorityQueue) PopNode() nodeIndex { item := heap.Pop(queue) - idx, ok := item.(NodeIndex) + idx, ok := item.(nodeIndex) if !ok { - panic("commitquery: heap pop item is not a NodeIndex") + 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 +} diff --git a/internal/commitquery/ancestor.go b/internal/commitquery/ancestor.go deleted file mode 100644 index d050ce08..00000000 --- a/internal/commitquery/ancestor.go +++ /dev/null @@ -1,30 +0,0 @@ -package commitquery - -// IsAncestor reports whether ancestor is reachable from descendant through -// commit parent edges. -func IsAncestor(ctx *Context, ancestor, descendant NodeIndex) (bool, error) { - if ancestor == descendant { - return true, nil - } - - ancestorGeneration := ctx.EffectiveGeneration(ancestor) - descendantGeneration := ctx.EffectiveGeneration(descendant) - - if ancestorGeneration != generationInfinity && - descendantGeneration != generationInfinity && - ancestorGeneration > descendantGeneration { - return false, nil - } - - minGeneration := uint64(0) - if ancestorGeneration != generationInfinity { - minGeneration = ancestorGeneration - } - - err := paintDownToCommon(ctx, ancestor, []NodeIndex{descendant}, minGeneration) - if err != nil { - return false, err - } - - return ctx.HasAnyMarks(ancestor, markRight), nil -} diff --git a/internal/commitquery/compare.go b/internal/commitquery/compare.go deleted file mode 100644 index 748ef712..00000000 --- a/internal/commitquery/compare.go +++ /dev/null @@ -1,25 +0,0 @@ -package commitquery - -import "codeberg.org/lindenii/furgit/objectid" - -// Compare compares two internal nodes using merge-base queue ordering. -func (ctx *Context) Compare(left, right NodeIndex) int { - leftGeneration := ctx.EffectiveGeneration(left) - rightGeneration := ctx.EffectiveGeneration(right) - - switch { - case leftGeneration < rightGeneration: - return -1 - case leftGeneration > rightGeneration: - return 1 - } - - switch { - case ctx.nodes[left].commitTime < ctx.nodes[right].commitTime: - return -1 - case ctx.nodes[left].commitTime > ctx.nodes[right].commitTime: - return 1 - } - - return objectid.Compare(ctx.nodes[left].id, ctx.nodes[right].id) -} diff --git a/internal/commitquery/context.go b/internal/commitquery/context.go deleted file mode 100644 index bafbb5c4..00000000 --- a/internal/commitquery/context.go +++ /dev/null @@ -1,32 +0,0 @@ -// Package commitquery provides private commit-domain query routines. -package commitquery - -import ( - commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" - "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/objectstore" -) - -// Context owns the mutable node arena for one commit query. -type Context struct { - store objectstore.Store - graph *commitgraphread.Reader - - nodes []node - - byOID map[objectid.ObjectID]NodeIndex - byGraphPos map[commitgraphread.Position]NodeIndex - - markPhase uint32 - touched []NodeIndex -} - -// NewContext builds one empty query context over one object store and optional commit-graph reader. -func NewContext(store objectstore.Store, graph *commitgraphread.Reader) *Context { - return &Context{ - store: store, - graph: graph, - byOID: make(map[objectid.ObjectID]NodeIndex), - byGraphPos: make(map[commitgraphread.Position]NodeIndex), - } -} diff --git a/internal/commitquery/generation.go b/internal/commitquery/generation.go deleted file mode 100644 index c5edcd9f..00000000 --- a/internal/commitquery/generation.go +++ /dev/null @@ -1,43 +0,0 @@ -package commitquery - -import ( - "math" - - "codeberg.org/lindenii/furgit/objectid" -) - -// EffectiveGeneration returns one node's generation value. -func (ctx *Context) EffectiveGeneration(idx NodeIndex) uint64 { - if !ctx.nodes[idx].hasGeneration { - return generationInfinity - } - - return ctx.nodes[idx].generation -} - -const ( - generationInfinity = uint64(math.MaxUint64) -) - -func compareByGeneration(ctx *Context) func(NodeIndex, NodeIndex) int { - return func(left, right NodeIndex) int { - leftGeneration := ctx.EffectiveGeneration(left) - rightGeneration := ctx.EffectiveGeneration(right) - - switch { - case leftGeneration < rightGeneration: - return -1 - case leftGeneration > rightGeneration: - return 1 - } - - switch { - case ctx.nodes[left].commitTime < ctx.nodes[right].commitTime: - return -1 - case ctx.nodes[left].commitTime > ctx.nodes[right].commitTime: - return 1 - } - - return objectid.Compare(ctx.nodes[left].id, ctx.nodes[right].id) - } -} diff --git a/internal/commitquery/graph_pos.go b/internal/commitquery/graph_pos.go deleted file mode 100644 index 437f86e6..00000000 --- a/internal/commitquery/graph_pos.go +++ /dev/null @@ -1,107 +0,0 @@ -package commitquery - -import commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" - -// ResolveGraphPos resolves one commit-graph position to one internal query node. -func (ctx *Context) ResolveGraphPos(pos commitgraphread.Position) (NodeIndex, error) { - idx, ok := ctx.byGraphPos[pos] - if ok { - err := ctx.ensureLoaded(idx) - if err != nil { - return 0, err - } - - return idx, nil - } - - commit, err := ctx.graph.CommitAt(pos) - if err != nil { - return 0, err - } - - idx, ok = ctx.byOID[commit.OID] - if !ok { - idx = ctx.newNode(commit.OID) - ctx.byOID[commit.OID] = idx - } - - ctx.byGraphPos[pos] = idx - ctx.nodes[idx].graphPos = pos - ctx.nodes[idx].hasGraphPos = true - - err = ctx.loadCommitAtGraphPos(idx, pos) - if err != nil { - delete(ctx.byGraphPos, pos) - - return 0, err - } - - return idx, nil -} - -// loadByGraphPos populates one node from a commit-graph position. -func (ctx *Context) loadByGraphPos(idx NodeIndex) error { - pos := ctx.nodes[idx].graphPos - - return ctx.loadCommitAtGraphPos(idx, pos) -} - -func (ctx *Context) loadCommitAtGraphPos(idx NodeIndex, pos commitgraphread.Position) error { - commit, err := ctx.graph.CommitAt(pos) - if err != nil { - return err - } - - parents := make([]Parent, 0, 2+len(commit.ExtraParents)) - - if commit.Parent1.Valid { - parentOID, err := ctx.graph.OIDAt(commit.Parent1.Pos) - if err != nil { - return err - } - - parents = append(parents, Parent{ - ID: parentOID, - GraphPos: commit.Parent1.Pos, - HasGraphPos: true, - }) - } - - if commit.Parent2.Valid { - parentOID, err := ctx.graph.OIDAt(commit.Parent2.Pos) - if err != nil { - return err - } - - parents = append(parents, Parent{ - ID: parentOID, - GraphPos: commit.Parent2.Pos, - HasGraphPos: true, - }) - } - - for _, parentPos := range commit.ExtraParents { - parentOID, err := ctx.graph.OIDAt(parentPos) - if err != nil { - return err - } - - parents = append(parents, Parent{ - ID: parentOID, - GraphPos: parentPos, - HasGraphPos: true, - }) - } - - data := Commit{ - ID: commit.OID, - Parents: parents, - CommitTime: commit.CommitTimeUnix, - Generation: commit.GenerationV2, - HasGeneration: commit.GenerationV2 != 0, - GraphPos: pos, - HasGraphPos: true, - } - - return ctx.populateNode(idx, data) -} diff --git a/internal/commitquery/load.go b/internal/commitquery/load.go deleted file mode 100644 index b795f7d9..00000000 --- a/internal/commitquery/load.go +++ /dev/null @@ -1,14 +0,0 @@ -package commitquery - -// ensureLoaded completes one node's metadata load if it has not been loaded yet. -func (ctx *Context) ensureLoaded(idx NodeIndex) error { - if ctx.nodes[idx].loaded { - return nil - } - - if ctx.nodes[idx].hasGraphPos { - return ctx.loadByGraphPos(idx) - } - - return ctx.loadByOID(idx) -} diff --git a/internal/commitquery/marks.go b/internal/commitquery/marks.go deleted file mode 100644 index f88fdf25..00000000 --- a/internal/commitquery/marks.go +++ /dev/null @@ -1,67 +0,0 @@ -package commitquery - -// Marks returns the mark bits of one internal node. -func (ctx *Context) Marks(idx NodeIndex) markBits { - return ctx.nodes[idx].marks -} - -// HasAnyMarks reports whether one internal node has any requested bit. -func (ctx *Context) HasAnyMarks(idx NodeIndex, bits markBits) bool { - return ctx.nodes[idx].marks&bits != 0 -} - -// HasAllMarks reports whether one internal node already has all requested bits. -func (ctx *Context) HasAllMarks(idx NodeIndex, bits markBits) bool { - return ctx.nodes[idx].marks&bits == bits -} - -// SetMarks ORs one set of mark bits into one internal node. -func (ctx *Context) SetMarks(idx NodeIndex, bits markBits) { - newBits := bits &^ ctx.nodes[idx].marks - if newBits == 0 { - return - } - - ctx.trackTouched(idx) - ctx.nodes[idx].marks |= bits -} - -// ClearMarks removes one set of mark bits from one internal node. -func (ctx *Context) ClearMarks(idx NodeIndex, bits markBits) { - if ctx.nodes[idx].marks&bits == 0 { - return - } - - ctx.trackTouched(idx) - ctx.nodes[idx].marks &^= bits -} - -// BeginMarkPhase starts one tracked mark-mutation phase. -func (ctx *Context) BeginMarkPhase() { - ctx.markPhase++ - if ctx.markPhase == 0 { - ctx.markPhase++ - for i := range ctx.nodes { - ctx.nodes[i].touchedPhase = 0 - } - } - - ctx.touched = ctx.touched[:0] -} - -// ClearTouchedMarks clears the provided bits from all nodes touched in the -// current mark phase. -func (ctx *Context) ClearTouchedMarks(bits markBits) { - for _, idx := range ctx.touched { - ctx.nodes[idx].marks &^= bits - } -} - -func (ctx *Context) trackTouched(idx NodeIndex) { - if ctx.nodes[idx].touchedPhase == ctx.markPhase { - return - } - - ctx.nodes[idx].touchedPhase = ctx.markPhase - ctx.touched = append(ctx.touched, idx) -} diff --git a/internal/commitquery/merge_bases.go b/internal/commitquery/merge_bases.go deleted file mode 100644 index 62ab9bd6..00000000 --- a/internal/commitquery/merge_bases.go +++ /dev/null @@ -1,116 +0,0 @@ -package commitquery - -import "slices" - -// MergeBases computes fully reduced merge bases using one query context. -func MergeBases(ctx *Context, left, right NodeIndex) ([]NodeIndex, error) { - if left == right { - return []NodeIndex{left}, nil - } - - err := paintDownToCommon(ctx, left, []NodeIndex{right}, 0) - if err != nil { - return nil, err - } - - candidates := collectMarkedResults(ctx) - - if len(candidates) <= 1 { - slices.SortFunc(candidates, ctx.Compare) - - return candidates, nil - } - - ctx.ClearTouchedMarks(allMarks) - - reduced, err := removeRedundant(ctx, candidates) - if err != nil { - return nil, err - } - - slices.SortFunc(reduced, ctx.Compare) - - return reduced, nil -} - -func paintDownToCommon(ctx *Context, left NodeIndex, rights []NodeIndex, minGeneration uint64) error { - ctx.BeginMarkPhase() - - ctx.SetMarks(left, markLeft) - - if len(rights) == 0 { - ctx.SetMarks(left, markResult) - - return nil - } - - queue := newPriorityQueue(ctx) - queue.PushNode(left) - - for _, right := range rights { - ctx.SetMarks(right, markRight) - queue.PushNode(right) - } - - lastGeneration := generationInfinity - - for queueHasNonStale(ctx, queue) { - idx := queue.PopNode() - - generation := ctx.EffectiveGeneration(idx) - if generation > lastGeneration { - return errBadGenerationOrder - } - - lastGeneration = generation - if generation < minGeneration { - break - } - - flags := ctx.Marks(idx) & (markLeft | markRight | markStale) - if flags == (markLeft | markRight) { - ctx.SetMarks(idx, markResult) - - flags |= markStale - } - - for _, parent := range ctx.Parents(idx) { - if ctx.HasAllMarks(parent, flags) { - continue - } - - ctx.SetMarks(parent, flags) - queue.PushNode(parent) - } - } - - return nil -} - -func queueHasNonStale(ctx *Context, queue *priorityQueue) bool { - for _, idx := range queue.items { - if !ctx.HasAnyMarks(idx, markStale) { - return true - } - } - - return false -} - -func collectMarkedResults(ctx *Context) []NodeIndex { - out := make([]NodeIndex, 0, 4) - - for _, idx := range ctx.touched { - if !ctx.HasAnyMarks(idx, markResult) { - continue - } - - if ctx.HasAnyMarks(idx, markStale) { - continue - } - - out = append(out, idx) - } - - return out -} diff --git a/internal/commitquery/populate.go b/internal/commitquery/populate.go deleted file mode 100644 index 87d65bf8..00000000 --- a/internal/commitquery/populate.go +++ /dev/null @@ -1,42 +0,0 @@ -package commitquery - -import "fmt" - -// populateNode fills one node's metadata and resolves its parents. -func (ctx *Context) populateNode(idx NodeIndex, commit Commit) error { - if ctx.nodes[idx].loaded { - if ctx.nodes[idx].id != commit.ID { - return fmt.Errorf("commitquery: node identity mismatch: have %s, got %s", ctx.nodes[idx].id, commit.ID) - } - - return nil - } - - ctx.nodes[idx].id = commit.ID - ctx.nodes[idx].commitTime = commit.CommitTime - ctx.nodes[idx].generation = commit.Generation - ctx.nodes[idx].hasGeneration = commit.HasGeneration - - if commit.HasGraphPos { - ctx.nodes[idx].graphPos = commit.GraphPos - ctx.nodes[idx].hasGraphPos = true - ctx.byGraphPos[commit.GraphPos] = idx - } - - ctx.nodes[idx].loaded = true - ctx.nodes[idx].parents = ctx.nodes[idx].parents[:0] - - for _, parent := range commit.Parents { - parentIdx, err := ctx.resolveParent(parent) - if err != nil { - ctx.nodes[idx].loaded = false - ctx.nodes[idx].parents = nil - - return err - } - - ctx.nodes[idx].parents = append(ctx.nodes[idx].parents, parentIdx) - } - - return nil -} diff --git a/internal/commitquery/reduce.go b/internal/commitquery/reduce.go deleted file mode 100644 index 917f2fa2..00000000 --- a/internal/commitquery/reduce.go +++ /dev/null @@ -1,166 +0,0 @@ -package commitquery - -import ( - "slices" -) - -// removeRedundant removes redundant merge-base candidates. -func removeRedundant(ctx *Context, candidates []NodeIndex) ([]NodeIndex, error) { - for _, idx := range candidates { - if ctx.EffectiveGeneration(idx) != generationInfinity { - return removeRedundantWithGen(ctx, candidates), nil - } - } - - return removeRedundantNoGen(ctx, candidates) -} - -func removeRedundantNoGen(ctx *Context, 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 := ctx.EffectiveGeneration(candidate) - - for j, other := range candidates { - if i == j || redundant[j] { - continue - } - - work = append(work, other) - filledIndex = append(filledIndex, j) - - otherGeneration := ctx.EffectiveGeneration(other) - if otherGeneration < minGeneration { - minGeneration = otherGeneration - } - } - - err := paintDownToCommon(ctx, candidate, work, minGeneration) - if err != nil { - return nil, err - } - - if ctx.HasAnyMarks(candidate, markRight) { - redundant[i] = true - } - - for j, other := range work { - if ctx.HasAnyMarks(other, markLeft) { - redundant[filledIndex[j]] = true - } - } - - ctx.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(ctx *Context, candidates []NodeIndex) []NodeIndex { - sorted := append([]NodeIndex(nil), candidates...) - slices.SortFunc(sorted, compareByGeneration(ctx)) - - minGeneration := ctx.EffectiveGeneration(sorted[0]) - minGenPos := 0 - countStillIndependent := len(candidates) - - ctx.BeginMarkPhase() - - walkStart := make([]NodeIndex, 0, len(candidates)*2) - - for _, idx := range candidates { - ctx.SetMarks(idx, markResult) - - for _, parent := range ctx.Parents(idx) { - if ctx.HasAnyMarks(parent, markStale) { - continue - } - - ctx.SetMarks(parent, markStale) - walkStart = append(walkStart, parent) - } - } - - slices.SortFunc(walkStart, compareByGeneration(ctx)) - - for _, idx := range walkStart { - ctx.ClearMarks(idx, markStale) - } - - for i := len(walkStart) - 1; i >= 0 && countStillIndependent > 1; i-- { - stack := []NodeIndex{walkStart[i]} - ctx.SetMarks(walkStart[i], markStale) - - for len(stack) > 0 { - top := stack[len(stack)-1] - - if ctx.HasAnyMarks(top, markResult) { - ctx.ClearMarks(top, markResult) - - countStillIndependent-- - if countStillIndependent <= 1 { - break - } - - if top == sorted[minGenPos] { - for minGenPos < len(sorted)-1 && ctx.HasAnyMarks(sorted[minGenPos], markStale) { - minGenPos++ - } - - minGeneration = ctx.EffectiveGeneration(sorted[minGenPos]) - } - } - - if ctx.EffectiveGeneration(top) < minGeneration { - stack = stack[:len(stack)-1] - - continue - } - - pushed := false - - for _, parent := range ctx.Parents(top) { - if ctx.HasAnyMarks(parent, markStale) { - continue - } - - ctx.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 !ctx.HasAnyMarks(idx, markStale) { - out = append(out, idx) - } - } - - ctx.ClearTouchedMarks(markStale | markResult) - - return out -} diff --git a/mergebase/base.go b/mergebase/base.go deleted file mode 100644 index 278fbed2..00000000 --- a/mergebase/base.go +++ /dev/null @@ -1,30 +0,0 @@ -package mergebase - -import ( - commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" - "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/objectstore" -) - -// Base reports one merge base between left and right, if any. -// -// Both inputs are peeled through annotated tags before commit traversal. -func Base( - store objectstore.Store, - graph *commitgraphread.Reader, - left objectid.ObjectID, - right objectid.ObjectID, -) (objectid.ObjectID, bool, error) { - query := Query(store, graph, left, right) - - bases, err := query.All() - if err != nil { - return objectid.ObjectID{}, false, err - } - - if len(bases) == 0 { - return objectid.ObjectID{}, false, nil - } - - return bases[0], true, nil -} diff --git a/mergebase/compute.go b/mergebase/compute.go deleted file mode 100644 index 76d2294c..00000000 --- a/mergebase/compute.go +++ /dev/null @@ -1,73 +0,0 @@ -package mergebase - -import ( - "slices" - - "codeberg.org/lindenii/furgit/internal/commitquery" - "codeberg.org/lindenii/furgit/internal/peel" - "codeberg.org/lindenii/furgit/objectid" -) - -// All returns all merge bases in Git's merge-base --all order. -func (query *Bases) All() ([]objectid.ObjectID, error) { - if query.computed { - return slices.Clone(query.bases), query.err - } - - query.computed = true - - leftCommit, err := peel.ToCommit(query.store, query.left) - if err != nil { - query.err = err - - return nil, err - } - - rightCommit, err := peel.ToCommit(query.store, query.right) - if err != nil { - query.err = err - - return nil, err - } - - ctx := commitquery.NewContext(query.store, query.graph) - - leftIdx, err := ctx.ResolveOID(leftCommit) - if err != nil { - query.err = err - - return nil, err - } - - rightIdx, err := ctx.ResolveOID(rightCommit) - if err != nil { - query.err = err - - return nil, err - } - - candidates, err := commitquery.MergeBases(ctx, leftIdx, rightIdx) - if err != nil { - query.err = err - - return nil, err - } - - slices.SortFunc(candidates, func(left, right commitquery.NodeIndex) int { - switch { - case ctx.CommitTime(left) > ctx.CommitTime(right): - return -1 - case ctx.CommitTime(left) < ctx.CommitTime(right): - return 1 - default: - return objectid.Compare(ctx.ID(left), ctx.ID(right)) - } - }) - - query.bases = make([]objectid.ObjectID, 0, len(candidates)) - for _, idx := range candidates { - query.bases = append(query.bases, ctx.ID(idx)) - } - - return slices.Clone(query.bases), nil -} diff --git a/mergebase/mergebase.go b/mergebase/mergebase.go deleted file mode 100644 index 772dc355..00000000 --- a/mergebase/mergebase.go +++ /dev/null @@ -1,20 +0,0 @@ -// Package mergebase computes best common ancestors between commits. -package mergebase - -import ( - commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" - "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/objectstore" -) - -// Bases is one merge-base query over two commit roots. -type Bases struct { - store objectstore.Store - graph *commitgraphread.Reader - left objectid.ObjectID - right objectid.ObjectID - - computed bool - bases []objectid.ObjectID - err error -} diff --git a/mergebase/query.go b/mergebase/query.go deleted file mode 100644 index 9a934377..00000000 --- a/mergebase/query.go +++ /dev/null @@ -1,24 +0,0 @@ -package mergebase - -import ( - commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read" - "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/objectstore" -) - -// Query builds one merge-base query over two commit roots. -// -// Both inputs are peeled through annotated tags before commit traversal. -func Query( - store objectstore.Store, - graph *commitgraphread.Reader, - left objectid.ObjectID, - right objectid.ObjectID, -) *Bases { - return &Bases{ - store: store, - graph: graph, - left: left, - right: right, - } -} diff --git a/receivepack/hooks/reject_force_push.go b/receivepack/hooks/reject_force_push.go index cf5ddaea..4bc749a5 100644 --- a/receivepack/hooks/reject_force_push.go +++ b/receivepack/hooks/reject_force_push.go @@ -5,7 +5,7 @@ import ( "errors" "fmt" - "codeberg.org/lindenii/furgit/ancestor" + "codeberg.org/lindenii/furgit/commitquery" "codeberg.org/lindenii/furgit/objectid" objectmix "codeberg.org/lindenii/furgit/objectstore/mix" receivepack "codeberg.org/lindenii/furgit/receivepack" @@ -46,7 +46,7 @@ func RejectForcePush() receivepack.Hook { continue } - ok, err := ancestor.Is(objects, nil, current.ID, update.NewID) + ok, err := commitquery.New(objects, nil).IsAncestor(current.ID, update.NewID) if err != nil { return nil, fmt.Errorf("check fast-forward %s: %w", update.Name, err) } |