diff options
Diffstat (limited to 'commitquery')
47 files changed, 0 insertions, 2191 deletions
diff --git a/commitquery/commit_data.go b/commitquery/commit_data.go deleted file mode 100644 index dff6a91c..00000000 --- a/commitquery/commit_data.go +++ /dev/null @@ -1,17 +0,0 @@ -package commitquery - -import ( - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - objectid "codeberg.org/lindenii/furgit/object/id" -) - -// 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/doc.go b/commitquery/doc.go deleted file mode 100644 index 269512df..00000000 --- a/commitquery/doc.go +++ /dev/null @@ -1,6 +0,0 @@ -// Package commitquery provides commit ancestry and merge-base queries -// over object storage. -// -// It uses commit-ish object IDs, peeling annotated tags when needed, -// and can use an optional commit-graph reader for performance. -package commitquery diff --git a/commitquery/errors.go b/commitquery/errors.go deleted file mode 100644 index 0006c86b..00000000 --- a/commitquery/errors.go +++ /dev/null @@ -1,6 +0,0 @@ -package commitquery - -import "errors" - -// errBadGenerationOrder reports an invalid priority-queue ordering. -var errBadGenerationOrder = errors.New("commitquery: priority queue violated generation ordering") diff --git a/commitquery/mark_bits.go b/commitquery/mark_bits.go deleted file mode 100644 index b10c833b..00000000 --- a/commitquery/mark_bits.go +++ /dev/null @@ -1,17 +0,0 @@ -package commitquery - -// markBits stores one set of traversal marks on one node. -type markBits uint8 - -// markLeft, markRight, markStale, and markResult track traversal state. -const ( - markLeft markBits = 1 << iota - markRight - markStale - markResult -) - -// allMarks is the union of all defined mark bits. -const ( - allMarks = markLeft | markRight | markStale | markResult -) diff --git a/commitquery/node.go b/commitquery/node.go deleted file mode 100644 index 7432a719..00000000 --- a/commitquery/node.go +++ /dev/null @@ -1,25 +0,0 @@ -package commitquery - -import ( - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - objectid "codeberg.org/lindenii/furgit/object/id" -) - -// 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 -} diff --git a/commitquery/node_commit_time.go b/commitquery/node_commit_time.go deleted file mode 100644 index 07c1f4e8..00000000 --- a/commitquery/node_commit_time.go +++ /dev/null @@ -1,6 +0,0 @@ -package commitquery - -// commitTime returns one node's commit time. -func (query *query) commitTime(idx nodeIndex) int64 { - return query.nodes[idx].commitTime -} diff --git a/commitquery/node_compare.go b/commitquery/node_compare.go deleted file mode 100644 index cf072af2..00000000 --- a/commitquery/node_compare.go +++ /dev/null @@ -1,25 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// compare orders 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/node_generation.go b/commitquery/node_generation.go deleted file mode 100644 index 03283cf6..00000000 --- a/commitquery/node_generation.go +++ /dev/null @@ -1,45 +0,0 @@ -package commitquery - -import ( - "math" - - objectid "codeberg.org/lindenii/furgit/object/id" -) - -// 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 -} - -// generationInfinity sorts nodes without a known generation last. -const ( - generationInfinity = uint64(math.MaxUint64) -) - -// compareByGeneration builds one comparator ordered by generation first. -func (query *query) compareByGeneration() 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/node_id.go b/commitquery/node_id.go deleted file mode 100644 index 8ec0b126..00000000 --- a/commitquery/node_id.go +++ /dev/null @@ -1,8 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// id returns one node's object ID. -func (query *query) id(idx nodeIndex) objectid.ObjectID { - return query.nodes[idx].id -} diff --git a/commitquery/node_index.go b/commitquery/node_index.go deleted file mode 100644 index 06122d62..00000000 --- a/commitquery/node_index.go +++ /dev/null @@ -1,4 +0,0 @@ -package commitquery - -// nodeIndex identifies one internal query node. -type nodeIndex int diff --git a/commitquery/node_new.go b/commitquery/node_new.go deleted file mode 100644 index 14a35262..00000000 --- a/commitquery/node_new.go +++ /dev/null @@ -1,14 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// 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/node_parents.go b/commitquery/node_parents.go deleted file mode 100644 index a98a774f..00000000 --- a/commitquery/node_parents.go +++ /dev/null @@ -1,6 +0,0 @@ -package commitquery - -// parents returns resolved parent node indices for one internal node. -func (query *query) parents(idx nodeIndex) []nodeIndex { - return query.nodes[idx].parents -} diff --git a/commitquery/node_populate.go b/commitquery/node_populate.go deleted file mode 100644 index 26fb5629..00000000 --- a/commitquery/node_populate.go +++ /dev/null @@ -1,42 +0,0 @@ -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/parent_ref.go b/commitquery/parent_ref.go deleted file mode 100644 index 08d224df..00000000 --- a/commitquery/parent_ref.go +++ /dev/null @@ -1,13 +0,0 @@ -package commitquery - -import ( - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - objectid "codeberg.org/lindenii/furgit/object/id" -) - -// parentRef references one commit parent. -type parentRef struct { - ID objectid.ObjectID - GraphPos commitgraphread.Position - HasGraphPos bool -} diff --git a/commitquery/queries.go b/commitquery/queries.go deleted file mode 100644 index 33709783..00000000 --- a/commitquery/queries.go +++ /dev/null @@ -1,26 +0,0 @@ -package commitquery - -import ( - "sync" - - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - objectfetch "codeberg.org/lindenii/furgit/object/fetch" -) - -// Queries provides commit-domain queries over one object fetcher -// and optional commit-graph reader. -// -// Queries reuses internal mutable query workers across operations. -// -// Labels: MT-Safe. -type Queries struct { - fetcher *objectfetch.Fetcher - graph *commitgraphread.Reader - - mu sync.Mutex - idle []*query - maxIdle int -} - -// TODO: Research a shared arena, or perhaps worker-reconciliation -// schemes if a complete shared arena proves to be too contentious. diff --git a/commitquery/queries_acquire.go b/commitquery/queries_acquire.go deleted file mode 100644 index a3aa0e58..00000000 --- a/commitquery/queries_acquire.go +++ /dev/null @@ -1,17 +0,0 @@ -package commitquery - -// acquire removes one worker from the idle pool or allocates one new worker. -func (queries *Queries) acquire() *query { - queries.mu.Lock() - defer queries.mu.Unlock() - - count := len(queries.idle) - if count == 0 { - return newQuery(queries.fetcher, queries.graph) - } - - q := queries.idle[count-1] - queries.idle = queries.idle[:count-1] - - return q -} diff --git a/commitquery/queries_is_ancestor.go b/commitquery/queries_is_ancestor.go deleted file mode 100644 index e2c955c6..00000000 --- a/commitquery/queries_is_ancestor.go +++ /dev/null @@ -1,14 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// IsAncestor reports whether ancestor is reachable from descendant through -// commit parent edges. -// -// Both inputs are peeled through annotated tags before commit traversal. -func (queries *Queries) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, error) { - query := queries.acquire() - defer queries.release(query) - - return query.IsAncestor(ancestor, descendant) -} diff --git a/commitquery/queries_is_ancestor_integration_test.go b/commitquery/queries_is_ancestor_integration_test.go deleted file mode 100644 index 7e8886a9..00000000 --- a/commitquery/queries_is_ancestor_integration_test.go +++ /dev/null @@ -1,133 +0,0 @@ -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/object/fetch" - objectid "codeberg.org/lindenii/furgit/object/id" -) - -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(fetch.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(fetch.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(fetch.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(fetch.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/queries_is_ancestor_unit_test.go b/commitquery/queries_is_ancestor_unit_test.go deleted file mode 100644 index 002c49ae..00000000 --- a/commitquery/queries_is_ancestor_unit_test.go +++ /dev/null @@ -1,166 +0,0 @@ -package commitquery_test - -import ( - "errors" - "fmt" - "testing" - - giterrors "codeberg.org/lindenii/furgit/errors" - "codeberg.org/lindenii/furgit/internal/testgit" - "codeberg.org/lindenii/furgit/object/fetch" - objectid "codeberg.org/lindenii/furgit/object/id" - "codeberg.org/lindenii/furgit/object/store/memory" - objecttree "codeberg.org/lindenii/furgit/object/tree" - objecttype "codeberg.org/lindenii/furgit/object/type" - - "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 := targetType.Name() - 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 *objecttree.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, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("blob\n")) - if err != nil { - t.Fatal(err) - } - - tree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeAncestorTree(t, &objecttree.Tree{Entries: []objecttree.TreeEntry{{ - Mode: objecttree.FileModeRegular, - Name: []byte("f"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - c1, err := store.WriteBytesContent(objecttype.TypeCommit, ancestorCommitBody(tree)) - if err != nil { - t.Fatal(err) - } - - c2, err := store.WriteBytesContent(objecttype.TypeCommit, ancestorCommitBody(tree, c1)) - if err != nil { - t.Fatal(err) - } - - otherBlob, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("other-blob\n")) - if err != nil { - t.Fatal(err) - } - - otherTree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeAncestorTree(t, &objecttree.Tree{Entries: []objecttree.TreeEntry{{ - Mode: objecttree.FileModeRegular, - Name: []byte("g"), - ID: otherBlob, - }}})) - if err != nil { - t.Fatal(err) - } - - c3, err := store.WriteBytesContent(objecttype.TypeCommit, ancestorCommitBody(otherTree)) - if err != nil { - t.Fatal(err) - } - - tag, err := store.WriteBytesContent(objecttype.TypeTag, ancestorTagBody(c2, objecttype.TypeCommit)) - if err != nil { - t.Fatal(err) - } - - ok, err := commitquery.New(fetch.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(fetch.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, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("blob\n")) - if err != nil { - t.Fatal(err) - } - - tree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeAncestorTree(t, &objecttree.Tree{Entries: []objecttree.TreeEntry{{ - Mode: objecttree.FileModeRegular, - Name: []byte("f"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - commit, err := store.WriteBytesContent(objecttype.TypeCommit, ancestorCommitBody(tree)) - if err != nil { - t.Fatal(err) - } - - tagToTree, err := store.WriteBytesContent(objecttype.TypeTag, ancestorTagBody(tree, objecttype.TypeTree)) - if err != nil { - t.Fatal(err) - } - - _, err = commitquery.New(fetch.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/queries_merge_base.go b/commitquery/queries_merge_base.go deleted file mode 100644 index 28de7fe2..00000000 --- a/commitquery/queries_merge_base.go +++ /dev/null @@ -1,11 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// MergeBase reports one merge base between left and right, if any. -func (queries *Queries) MergeBase(left, right objectid.ObjectID) (objectid.ObjectID, bool, error) { - query := queries.acquire() - defer queries.release(query) - - return query.MergeBase(left, right) -} diff --git a/commitquery/queries_merge_bases.go b/commitquery/queries_merge_bases.go deleted file mode 100644 index 74c5054a..00000000 --- a/commitquery/queries_merge_bases.go +++ /dev/null @@ -1,13 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// MergeBases reports all merge bases in Git's merge-base --all order. -// -// Both inputs are peeled through annotated tags before commit traversal. -func (queries *Queries) MergeBases(left, right objectid.ObjectID) ([]objectid.ObjectID, error) { - query := queries.acquire() - defer queries.release(query) - - return query.MergeBases(left, right) -} diff --git a/commitquery/queries_merge_bases_integration_test.go b/commitquery/queries_merge_bases_integration_test.go deleted file mode 100644 index 4fdfdf16..00000000 --- a/commitquery/queries_merge_bases_integration_test.go +++ /dev/null @@ -1,312 +0,0 @@ -package commitquery_test - -import ( - "maps" - "slices" - "strings" - "testing" - - "codeberg.org/lindenii/furgit/commitquery" - "codeberg.org/lindenii/furgit/internal/testgit" - "codeberg.org/lindenii/furgit/object/fetch" - objectid "codeberg.org/lindenii/furgit/object/id" -) - -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(fetch.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(fetch.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(fetch.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(fetch.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(fetch.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/queries_merge_bases_unit_test.go b/commitquery/queries_merge_bases_unit_test.go deleted file mode 100644 index 3e302536..00000000 --- a/commitquery/queries_merge_bases_unit_test.go +++ /dev/null @@ -1,485 +0,0 @@ -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/fetch" - objectid "codeberg.org/lindenii/furgit/object/id" - "codeberg.org/lindenii/furgit/object/store/memory" - "codeberg.org/lindenii/furgit/object/tree" - objecttype "codeberg.org/lindenii/furgit/object/type" -) - -// 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 := targetType.Name() - 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 *tree.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, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("blob\n")) - if err != nil { - t.Fatal(err) - } - - tree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("f"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - base, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(tree)) - if err != nil { - t.Fatal(err) - } - - left, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(tree, base)) - if err != nil { - t.Fatal(err) - } - - right, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(tree, left)) - if err != nil { - t.Fatal(err) - } - - query := commitquery.New(fetch.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, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("blob\n")) - if err != nil { - t.Fatal(err) - } - - leftTree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("left"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - rightTree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("right"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - base, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(leftTree)) - if err != nil { - t.Fatal(err) - } - - left, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(leftTree, base)) - if err != nil { - t.Fatal(err) - } - - right, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(rightTree, base)) - if err != nil { - t.Fatal(err) - } - - tag, err := store.WriteBytesContent(objecttype.TypeTag, tagBody(right, objecttype.TypeCommit)) - if err != nil { - t.Fatal(err) - } - - query := commitquery.New(fetch.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, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("blob\n")) - if err != nil { - t.Fatal(err) - } - - rootTree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("root"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - base1Tree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("base1"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - base2Tree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("base2"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - leftTree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("left"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - rightTree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("right"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - root, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(rootTree)) - if err != nil { - t.Fatal(err) - } - - base1, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(base1Tree, root)) - if err != nil { - t.Fatal(err) - } - - base2, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(base2Tree, root)) - if err != nil { - t.Fatal(err) - } - - left, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(leftTree, base1, base2)) - if err != nil { - t.Fatal(err) - } - - right, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(rightTree, base2, base1)) - if err != nil { - t.Fatal(err) - } - - query := commitquery.New(fetch.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, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("left\n")) - if err != nil { - t.Fatal(err) - } - - leftTree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("left"), - ID: leftBlob, - }}})) - if err != nil { - t.Fatal(err) - } - - rightBlob, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("right\n")) - if err != nil { - t.Fatal(err) - } - - rightTree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("right"), - ID: rightBlob, - }}})) - if err != nil { - t.Fatal(err) - } - - left, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(leftTree)) - if err != nil { - t.Fatal(err) - } - - right, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(rightTree)) - if err != nil { - t.Fatal(err) - } - - query := commitquery.New(fetch.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, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("blob\n")) - if err != nil { - t.Fatal(err) - } - - tree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("f"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - commit, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(tree)) - if err != nil { - t.Fatal(err) - } - - tagToTree, err := store.WriteBytesContent(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree)) - if err != nil { - t.Fatal(err) - } - - query := commitquery.New(fetch.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, err := store.WriteBytesContent(objecttype.TypeBlob, []byte("blob\n")) - if err != nil { - t.Fatal(err) - } - - tree, err := store.WriteBytesContent(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{ - Mode: tree.FileModeRegular, - Name: []byte("f"), - ID: blob, - }}})) - if err != nil { - t.Fatal(err) - } - - base, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(tree)) - if err != nil { - t.Fatal(err) - } - - left, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(tree, base)) - if err != nil { - t.Fatal(err) - } - - right, err := store.WriteBytesContent(objecttype.TypeCommit, commitBody(tree, left)) - if err != nil { - t.Fatal(err) - } - - query := commitquery.New(fetch.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/queries_new.go b/commitquery/queries_new.go deleted file mode 100644 index 5eae7990..00000000 --- a/commitquery/queries_new.go +++ /dev/null @@ -1,22 +0,0 @@ -package commitquery - -import ( - "runtime" - - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - objectfetch "codeberg.org/lindenii/furgit/object/fetch" -) - -// New builds one concurrent-safe commit query service over one object fetcher -// and optional commit-graph reader. -// -// Labels: Deps-Borrowed, Life-Parent. -func New(fetcher *objectfetch.Fetcher, graph *commitgraphread.Reader) *Queries { - maxIdle := max(runtime.GOMAXPROCS(0), 1) - - return &Queries{ - fetcher: fetcher, - graph: graph, - maxIdle: maxIdle, - } -} diff --git a/commitquery/queries_release.go b/commitquery/queries_release.go deleted file mode 100644 index 5d0b2fde..00000000 --- a/commitquery/queries_release.go +++ /dev/null @@ -1,15 +0,0 @@ -package commitquery - -// release resets one worker and returns it to the idle pool if there is room. -func (queries *Queries) release(q *query) { - q.resetForReuse() - - queries.mu.Lock() - defer queries.mu.Unlock() - - if len(queries.idle) >= queries.maxIdle { - return - } - - queries.idle = append(queries.idle, q) -} diff --git a/commitquery/query.go b/commitquery/query.go deleted file mode 100644 index 65e90ec8..00000000 --- a/commitquery/query.go +++ /dev/null @@ -1,23 +0,0 @@ -package commitquery - -import ( - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - objectfetch "codeberg.org/lindenii/furgit/object/fetch" - objectid "codeberg.org/lindenii/furgit/object/id" -) - -// query stores one mutable reusable worker and its cached node arena. -// -// Labels: MT-Unsafe. -type query struct { - fetcher *objectfetch.Fetcher - graph *commitgraphread.Reader - - nodes []node - - byOID map[objectid.ObjectID]nodeIndex - byGraphPos map[commitgraphread.Position]nodeIndex - - markPhase uint32 - touched []nodeIndex -} diff --git a/commitquery/query_collect_marked_results.go b/commitquery/query_collect_marked_results.go deleted file mode 100644 index 7139fb9b..00000000 --- a/commitquery/query_collect_marked_results.go +++ /dev/null @@ -1,20 +0,0 @@ -package commitquery - -// collectMarkedResults returns touched nodes marked as non-stale results. -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/query_ensure_loaded.go b/commitquery/query_ensure_loaded.go deleted file mode 100644 index 830e9b19..00000000 --- a/commitquery/query_ensure_loaded.go +++ /dev/null @@ -1,14 +0,0 @@ -package commitquery - -// ensureLoaded completes one node's metadata load if it is not 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/query_has_marks.go b/commitquery/query_has_marks.go deleted file mode 100644 index 22f44bd4..00000000 --- a/commitquery/query_has_marks.go +++ /dev/null @@ -1,11 +0,0 @@ -package commitquery - -// 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 -} diff --git a/commitquery/query_is_ancestor.go b/commitquery/query_is_ancestor.go deleted file mode 100644 index c21892c8..00000000 --- a/commitquery/query_is_ancestor.go +++ /dev/null @@ -1,49 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// 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) -} - -// isAncestor answers one ancestry query between two resolved internal nodes. -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/query_load_by_graph_pos.go b/commitquery/query_load_by_graph_pos.go deleted file mode 100644 index 718d99b5..00000000 --- a/commitquery/query_load_by_graph_pos.go +++ /dev/null @@ -1,8 +0,0 @@ -package commitquery - -// 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) -} diff --git a/commitquery/query_load_by_oid.go b/commitquery/query_load_by_oid.go deleted file mode 100644 index f9c956ee..00000000 --- a/commitquery/query_load_by_oid.go +++ /dev/null @@ -1,41 +0,0 @@ -package commitquery - -import ( - stderrors "errors" - - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" -) - -// 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) - } - } - - commit, err := query.fetcher.ExactCommit(id) - if err != nil { - return err - } - - parents := make([]parentRef, 0, len(commit.Object().Parents)) - for _, parentID := range commit.Object().Parents { - parents = append(parents, parentRef{ID: parentID}) - } - - commitData := commitData{ - ID: id, - Parents: parents, - CommitTime: commit.Object().Committer.WhenUnix, - } - - return query.populateNode(idx, commitData) -} diff --git a/commitquery/query_load_commit_at_graph_pos.go b/commitquery/query_load_commit_at_graph_pos.go deleted file mode 100644 index f63b6385..00000000 --- a/commitquery/query_load_commit_at_graph_pos.go +++ /dev/null @@ -1,64 +0,0 @@ -package commitquery - -import commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - -// loadCommitAtGraphPos populates one node from one commit-graph record. -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/query_mark_phase.go b/commitquery/query_mark_phase.go deleted file mode 100644 index 0814df38..00000000 --- a/commitquery/query_mark_phase.go +++ /dev/null @@ -1,36 +0,0 @@ -package commitquery - -// 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 - } -} - -// trackTouched records one node in the current mark phase. -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/query_marks_get.go b/commitquery/query_marks_get.go deleted file mode 100644 index 28136d84..00000000 --- a/commitquery/query_marks_get.go +++ /dev/null @@ -1,6 +0,0 @@ -package commitquery - -// marks returns the mark bits of one internal node. -func (query *query) marks(idx nodeIndex) markBits { - return query.nodes[idx].marks -} diff --git a/commitquery/query_merge_base.go b/commitquery/query_merge_base.go deleted file mode 100644 index e1ba3126..00000000 --- a/commitquery/query_merge_base.go +++ /dev/null @@ -1,17 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// 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 -} diff --git a/commitquery/query_merge_bases.go b/commitquery/query_merge_bases.go deleted file mode 100644 index 384ee019..00000000 --- a/commitquery/query_merge_bases.go +++ /dev/null @@ -1,45 +0,0 @@ -package commitquery - -import ( - "slices" - - objectid "codeberg.org/lindenii/furgit/object/id" -) - -// 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 -} diff --git a/commitquery/query_merge_bases_internal.go b/commitquery/query_merge_bases_internal.go deleted file mode 100644 index 2d133435..00000000 --- a/commitquery/query_merge_bases_internal.go +++ /dev/null @@ -1,34 +0,0 @@ -package commitquery - -import "slices" - -// mergeBases returns internal merge-base candidates for two resolved nodes. -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 -} diff --git a/commitquery/query_new.go b/commitquery/query_new.go deleted file mode 100644 index 0f23a321..00000000 --- a/commitquery/query_new.go +++ /dev/null @@ -1,19 +0,0 @@ -package commitquery - -import ( - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - objectfetch "codeberg.org/lindenii/furgit/object/fetch" - objectid "codeberg.org/lindenii/furgit/object/id" -) - -// newQuery builds one empty mutable worker over one object fetcher and graph. -// -// Labels: Deps-Borrowed, Life-Parent. -func newQuery(fetcher *objectfetch.Fetcher, graph *commitgraphread.Reader) *query { - return &query{ - fetcher: fetcher, - graph: graph, - byOID: make(map[objectid.ObjectID]nodeIndex), - byGraphPos: make(map[commitgraphread.Position]nodeIndex), - } -} diff --git a/commitquery/query_paint_down_to_common.go b/commitquery/query_paint_down_to_common.go deleted file mode 100644 index e152e159..00000000 --- a/commitquery/query_paint_down_to_common.go +++ /dev/null @@ -1,67 +0,0 @@ -package commitquery - -import "codeberg.org/lindenii/furgit/internal/priorityqueue" - -// paintDownToCommon propagates left and right marks downward until common nodes. -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 := priorityqueue.New(func(left, right nodeIndex) bool { - return query.compare(left, right) > 0 - }) - queue.Push(left) - - for _, right := range rights { - query.setMarks(right, markRight) - queue.Push(right) - } - - lastGeneration := generationInfinity - - for queue.Len() > 0 { - idx, ok := queue.Pop() - if !ok { - break - } - - if query.hasAnyMarks(idx, markStale) { - continue - } - - 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.Push(parent) - } - } - - return nil -} diff --git a/commitquery/query_reduce.go b/commitquery/query_reduce.go deleted file mode 100644 index b7ea5df1..00000000 --- a/commitquery/query_reduce.go +++ /dev/null @@ -1,166 +0,0 @@ -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) -} - -// removeRedundantNoGen removes redundant candidates without generation data. -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 -} - -// removeRedundantWithGen removes redundant candidates using generation data. -func removeRedundantWithGen(query *query, candidates []nodeIndex) []nodeIndex { - sorted := append([]nodeIndex(nil), candidates...) - slices.SortFunc(sorted, query.compareByGeneration()) - - 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, query.compareByGeneration()) - - 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/commitquery/query_reset.go b/commitquery/query_reset.go deleted file mode 100644 index 11f7cb3e..00000000 --- a/commitquery/query_reset.go +++ /dev/null @@ -1,10 +0,0 @@ -package commitquery - -// resetForReuse clears transient state before one worker returns to the pool. -func (query *query) resetForReuse() { - for _, idx := range query.touched { - query.nodes[idx].marks = 0 - } - - query.touched = query.touched[:0] -} diff --git a/commitquery/query_resolve_commitish.go b/commitquery/query_resolve_commitish.go deleted file mode 100644 index 1e14a1c0..00000000 --- a/commitquery/query_resolve_commitish.go +++ /dev/null @@ -1,13 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// resolveCommitish peels one commit-ish object ID and resolves the commit. -func (query *query) resolveCommitish(id objectid.ObjectID) (nodeIndex, error) { - id, err := query.fetcher.PeelToCommitID(id) - if err != nil { - return 0, err - } - - return query.resolveOID(id) -} diff --git a/commitquery/query_resolve_graph_pos.go b/commitquery/query_resolve_graph_pos.go deleted file mode 100644 index dce8fc22..00000000 --- a/commitquery/query_resolve_graph_pos.go +++ /dev/null @@ -1,40 +0,0 @@ -package commitquery - -import commitgraphread "codeberg.org/lindenii/furgit/format/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 -} diff --git a/commitquery/query_resolve_oid.go b/commitquery/query_resolve_oid.go deleted file mode 100644 index ad47829c..00000000 --- a/commitquery/query_resolve_oid.go +++ /dev/null @@ -1,28 +0,0 @@ -package commitquery - -import objectid "codeberg.org/lindenii/furgit/object/id" - -// resolveOID resolves one commit object ID to one internal query node. -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 -} diff --git a/commitquery/query_resolve_parent.go b/commitquery/query_resolve_parent.go deleted file mode 100644 index 6cd75898..00000000 --- a/commitquery/query_resolve_parent.go +++ /dev/null @@ -1,10 +0,0 @@ -package commitquery - -// 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/query_set_clear_marks.go b/commitquery/query_set_clear_marks.go deleted file mode 100644 index b9619338..00000000 --- a/commitquery/query_set_clear_marks.go +++ /dev/null @@ -1,22 +0,0 @@ -package commitquery - -// 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 -} |