aboutsummaryrefslogtreecommitdiff
path: root/ancestor
diff options
context:
space:
mode:
Diffstat (limited to 'ancestor')
-rw-r--r--ancestor/ancestor.go45
-rw-r--r--ancestor/integration_test.go133
-rw-r--r--ancestor/unit_test.go118
3 files changed, 296 insertions, 0 deletions
diff --git a/ancestor/ancestor.go b/ancestor/ancestor.go
new file mode 100644
index 00000000..ad90bd33
--- /dev/null
+++ b/ancestor/ancestor.go
@@ -0,0 +1,45 @@
+// Package ancestor answers commit ancestry queries.
+package ancestor
+
+import (
+ commitgraphread "codeberg.org/lindenii/furgit/format/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/ancestor/integration_test.go b/ancestor/integration_test.go
new file mode 100644
index 00000000..d13c86ed
--- /dev/null
+++ b/ancestor/integration_test.go
@@ -0,0 +1,133 @@
+package ancestor_test
+
+import (
+ "errors"
+ "testing"
+
+ 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) {
+ 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 := ancestor.Is(store, nil, 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 = ancestor.Is(store, nil, 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 := ancestor.Is(store, graph, 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 := ancestor.Is(store, nil, treeID, commitID)
+ if err == nil {
+ t.Fatal("expected error")
+ }
+
+ var missing *giterrors.ObjectMissingError
+ if !errors.As(err, &missing) {
+ 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/ancestor/unit_test.go b/ancestor/unit_test.go
new file mode 100644
index 00000000..827aeb8f
--- /dev/null
+++ b/ancestor/unit_test.go
@@ -0,0 +1,118 @@
+package ancestor_test
+
+import (
+ "errors"
+ "fmt"
+ "testing"
+
+ giterrors "codeberg.org/lindenii/furgit/errors"
+ "codeberg.org/lindenii/furgit/internal/testgit"
+ "codeberg.org/lindenii/furgit/object"
+ "codeberg.org/lindenii/furgit/objectid"
+ "codeberg.org/lindenii/furgit/objectstore/memory"
+ "codeberg.org/lindenii/furgit/objecttype"
+
+ "codeberg.org/lindenii/furgit/ancestor"
+)
+
+// commitBody serializes one minimal commit body.
+func commitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte {
+ buf := fmt.Appendf(nil, "tree %s\n", tree.String())
+ for _, parent := range parents {
+ buf = append(buf, fmt.Appendf(nil, "parent %s\n", parent.String())...)
+ }
+
+ buf = append(buf, []byte("\nmsg\n")...)
+
+ return buf
+}
+
+// tagBody serializes one minimal annotated tag body.
+func tagBody(target objectid.ObjectID, targetType objecttype.Type) []byte {
+ targetName, ok := objecttype.Name(targetType)
+ if !ok {
+ panic("invalid tag target type")
+ }
+
+ return fmt.Appendf(nil, "object %s\ntype %s\ntag t\n\nmsg\n", target.String(), targetName)
+}
+
+// mustSerializeTree serializes one tree or fails the test.
+func mustSerializeTree(tb testing.TB, tree *object.Tree) []byte {
+ tb.Helper()
+
+ body, err := tree.SerializeWithoutHeader()
+ if err != nil {
+ tb.Fatalf("SerializeWithoutHeader: %v", err)
+ }
+
+ return body
+}
+
+func TestIs(t *testing.T) {
+ t.Parallel()
+
+ testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+ store := memory.New(algo)
+ blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+ tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(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))
+ otherBlob := store.AddObject(objecttype.TypeBlob, []byte("other-blob\n"))
+ otherTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(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))
+
+ ok, err := ancestor.Is(store, nil, 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 = ancestor.Is(store, nil, c3, c2)
+ if err != nil {
+ t.Fatalf("Is(c3, c2): %v", err)
+ }
+
+ if ok {
+ t.Fatal("did not expect c3 to be ancestor of c2")
+ }
+ })
+}
+
+func TestIsRejectsNonCommitAfterPeel(t *testing.T) {
+ t.Parallel()
+
+ testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+ store := memory.New(algo)
+ blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+ tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+ Mode: object.FileModeRegular,
+ Name: []byte("f"),
+ ID: blob,
+ }}}))
+ commit := store.AddObject(objecttype.TypeCommit, commitBody(tree))
+ tagToTree := store.AddObject(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree))
+
+ _, err := ancestor.Is(store, nil, commit, tagToTree)
+ if err == nil {
+ t.Fatal("expected error")
+ }
+
+ var typeErr *giterrors.ObjectTypeError
+ if !errors.As(err, &typeErr) {
+ t.Fatalf("expected ObjectTypeError, got %T (%v)", err, err)
+ }
+ })
+}
generated by cgit v1.3.1-10-gc9f91 (git 2.54.0) at 2026-05-25 16:27:32 +0000