From 01d15bccf3b1dcc51516b1f64d50950b31d7f8fb Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Fri, 6 Mar 2026 21:19:56 +0800 Subject: Urgh I made some wrong amends and I'm too tired to separate the commits out this time ancestor: Split out of reachability mergebase: Add merge base routines internal/commitquery: Add commit query context engine thingy internal/peel: Shared tag peeling errors: Shared object query errors internal/testgit: Add rooted repo helpers; remove raw path access objectstore/memory: Add in-memory object store objectid: Add Compare helper --- ancestor/ancestor.go | 45 ++++ ancestor/integration_test.go | 133 +++++++++++ ancestor/unit_test.go | 118 ++++++++++ config/config_test.go | 62 ++--- diff/trees/diff_test.go | 77 +++--- errors/doc.go | 2 + errors/missing.go | 18 ++ errors/type.go | 31 +++ format/commitgraph/read/read_test.go | 16 +- format/pack/ingest/ingest_test.go | 138 +++-------- internal/commitquery/ancestor.go | 30 +++ internal/commitquery/bits.go | 14 ++ internal/commitquery/commit.go | 17 ++ internal/commitquery/compare.go | 25 ++ internal/commitquery/context.go | 32 +++ internal/commitquery/errors.go | 5 + internal/commitquery/generation.go | 43 ++++ internal/commitquery/graph_pos.go | 107 +++++++++ internal/commitquery/load.go | 14 ++ internal/commitquery/marks.go | 67 ++++++ internal/commitquery/merge_bases.go | 105 +++++++++ internal/commitquery/node.go | 39 ++++ internal/commitquery/oid.go | 95 ++++++++ internal/commitquery/parent.go | 27 +++ internal/commitquery/populate.go | 42 ++++ internal/commitquery/priority_queue.go | 68 ++++++ internal/commitquery/reduce.go | 166 +++++++++++++ internal/peel/peel.go | 50 ++++ internal/testgit/repo_commit_tree_env.go | 51 ++++ internal/testgit/repo_fs.go | 86 +++++++ internal/testgit/repo_open_commit_graph.go | 26 +++ internal/testgit/repo_open_object_store.go | 29 +++ internal/testgit/repo_open_repository.go | 25 ++ internal/testgit/repo_open_root.go | 87 +++++++ internal/testgit/repo_properties.go | 5 - internal/testgit/repo_remove_loose_object.go | 22 ++ internal/testgit/repo_run.go | 52 ++++- mergebase/base.go | 43 ++++ mergebase/compute.go | 56 +++++ mergebase/integration_test.go | 308 ++++++++++++++++++++++++ mergebase/mergebase.go | 19 ++ mergebase/query.go | 24 ++ mergebase/seq.go | 47 ++++ mergebase/unit_test.go | 335 +++++++++++++++++++++++++++ objectid/objectid.go | 7 + objectstore/loose/helpers_test.go | 13 +- objectstore/loose/read_test.go | 4 +- objectstore/loose/write_test.go | 12 +- objectstore/memory/add.go | 21 ++ objectstore/memory/algorithm.go | 8 + objectstore/memory/doc.go | 2 + objectstore/memory/object.go | 9 + objectstore/memory/read_bytes.go | 37 +++ objectstore/memory/read_header.go | 17 ++ objectstore/memory/read_reader.go | 29 +++ objectstore/memory/read_size.go | 13 ++ objectstore/memory/store.go | 24 ++ objectstore/objectstore.go | 1 + objectstore/packed/helpers_test.go | 13 +- objectstore/packed/read_test.go | 40 ++-- reachability/ancestor.go | 122 ---------- reachability/errors.go | 39 ---- reachability/helpers.go | 5 +- reachability/integration_test.go | 101 +------- reachability/peel.go | 37 --- reachability/unit_test.go | 246 ++++---------------- reachability/walk.go | 2 +- reachability/walk_expand_commits.go | 3 +- reachability/walk_expand_objects.go | 5 +- reachability/walk_verify.go | 3 +- refstore/loose/loose_test.go | 37 +-- refstore/packed/packed_test.go | 25 +- repository/refs_test.go | 30 +-- repository/stored_test.go | 86 +------ repository/traversal_test.go | 76 ++++-- repository/write_loose_test.go | 44 +--- 76 files changed, 2932 insertions(+), 980 deletions(-) create mode 100644 ancestor/ancestor.go create mode 100644 ancestor/integration_test.go create mode 100644 ancestor/unit_test.go create mode 100644 errors/doc.go create mode 100644 errors/missing.go create mode 100644 errors/type.go create mode 100644 internal/commitquery/ancestor.go create mode 100644 internal/commitquery/bits.go create mode 100644 internal/commitquery/commit.go create mode 100644 internal/commitquery/compare.go create mode 100644 internal/commitquery/context.go create mode 100644 internal/commitquery/errors.go create mode 100644 internal/commitquery/generation.go create mode 100644 internal/commitquery/graph_pos.go create mode 100644 internal/commitquery/load.go create mode 100644 internal/commitquery/marks.go create mode 100644 internal/commitquery/merge_bases.go create mode 100644 internal/commitquery/node.go create mode 100644 internal/commitquery/oid.go create mode 100644 internal/commitquery/parent.go create mode 100644 internal/commitquery/populate.go create mode 100644 internal/commitquery/priority_queue.go create mode 100644 internal/commitquery/reduce.go create mode 100644 internal/peel/peel.go create mode 100644 internal/testgit/repo_commit_tree_env.go create mode 100644 internal/testgit/repo_fs.go create mode 100644 internal/testgit/repo_open_commit_graph.go create mode 100644 internal/testgit/repo_open_object_store.go create mode 100644 internal/testgit/repo_open_repository.go create mode 100644 internal/testgit/repo_open_root.go create mode 100644 internal/testgit/repo_remove_loose_object.go create mode 100644 mergebase/base.go create mode 100644 mergebase/compute.go create mode 100644 mergebase/integration_test.go create mode 100644 mergebase/mergebase.go create mode 100644 mergebase/query.go create mode 100644 mergebase/seq.go create mode 100644 mergebase/unit_test.go create mode 100644 objectstore/memory/add.go create mode 100644 objectstore/memory/algorithm.go create mode 100644 objectstore/memory/doc.go create mode 100644 objectstore/memory/object.go create mode 100644 objectstore/memory/read_bytes.go create mode 100644 objectstore/memory/read_header.go create mode 100644 objectstore/memory/read_reader.go create mode 100644 objectstore/memory/read_size.go create mode 100644 objectstore/memory/store.go delete mode 100644 reachability/ancestor.go delete mode 100644 reachability/errors.go delete mode 100644 reachability/peel.go 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) + } + }) +} diff --git a/config/config_test.go b/config/config_test.go index 8364b264..3f166202 100644 --- a/config/config_test.go +++ b/config/config_test.go @@ -3,8 +3,6 @@ package config_test import ( "bytes" "os" - "os/exec" - "path/filepath" "strings" "testing" @@ -16,7 +14,9 @@ import ( func openConfig(t *testing.T, testRepo *testgit.TestRepo) *os.File { t.Helper() - cfgFile, err := os.Open(filepath.Join(testRepo.Dir(), "config")) + root := testRepo.OpenGitRoot(t) + + cfgFile, err := root.Open("config") if err != nil { t.Fatalf("failed to open config: %v", err) } @@ -30,14 +30,10 @@ func gitConfigGet(t *testing.T, testRepo *testgit.TestRepo, key string) string { return testRepo.Run(t, "config", "--get", key) } -func gitConfigGetE(testRepo *testgit.TestRepo, key string) (string, error) { - //nolint:noctx - cmd := exec.Command("git", "config", "--get", key) //#nosec G204 - cmd.Dir = testRepo.Dir() - cmd.Env = testRepo.Env() - out, err := cmd.CombinedOutput() +func gitConfigGetE(t *testing.T, testRepo *testgit.TestRepo, key string) (string, error) { + t.Helper() - return strings.TrimSpace(string(out)), err + return testRepo.RunE(t, "config", "--get", key) } func lookupValue(cfg *config.Config, section, subsection, key string) string { @@ -463,20 +459,15 @@ func TestConfigErrorCases(t *testing.T) { } } -func TestConfigEOFAfterKeyAgainstGit(t *testing.T) { //nolint:dupl +func TestConfigEOFAfterKeyAgainstGit(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}) - cfgPath := filepath.Join(testRepo.Dir(), "config") - cfgData := []byte("[Core]BAre") - err := os.WriteFile(cfgPath, cfgData, 0o600) - if err != nil { - t.Fatalf("failed to write config: %v", err) - } + testRepo.WriteFile(t, "config", cfgData, 0o600) - gitValue, gitErr := gitConfigGetE(testRepo, "Core.BAre") + gitValue, gitErr := gitConfigGetE(t, testRepo, "Core.BAre") furConfig, furErr := config.ParseConfig(bytes.NewReader(cfgData)) if (gitErr == nil) != (furErr == nil) { @@ -493,20 +484,15 @@ func TestConfigEOFAfterKeyAgainstGit(t *testing.T) { //nolint:dupl }) } -func TestConfigNULValueAgainstGit(t *testing.T) { //nolint:dupl +func TestConfigNULValueAgainstGit(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}) - cfgPath := filepath.Join(testRepo.Dir(), "config") - cfgData := []byte("[Core]BAre=\x00") - err := os.WriteFile(cfgPath, cfgData, 0o600) - if err != nil { - t.Fatalf("failed to write config: %v", err) - } + testRepo.WriteFile(t, "config", cfgData, 0o600) - gitValue, gitErr := gitConfigGetE(testRepo, "Core.BAre") + gitValue, gitErr := gitConfigGetE(t, testRepo, "Core.BAre") furConfig, furErr := config.ParseConfig(bytes.NewReader(cfgData)) if (gitErr == nil) != (furErr == nil) { @@ -523,20 +509,15 @@ func TestConfigNULValueAgainstGit(t *testing.T) { //nolint:dupl }) } -func TestConfigCarriageReturnSeparatorAgainstGit(t *testing.T) { //nolint:dupl +func TestConfigCarriageReturnSeparatorAgainstGit(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}) - cfgPath := filepath.Join(testRepo.Dir(), "config") - cfgData := []byte("[Core \"sub\"]\rBAre") - err := os.WriteFile(cfgPath, cfgData, 0o600) - if err != nil { - t.Fatalf("failed to write config: %v", err) - } + testRepo.WriteFile(t, "config", cfgData, 0o600) - gitValue, gitErr := gitConfigGetE(testRepo, "Core.sub.BAre") + gitValue, gitErr := gitConfigGetE(t, testRepo, "Core.sub.BAre") furConfig, furErr := config.ParseConfig(bytes.NewReader(cfgData)) if (gitErr == nil) != (furErr == nil) { @@ -559,16 +540,14 @@ func FuzzConfig(f *testing.F) { f.Add([]byte("[core \"sub\"]\nbare = true"), "core.sub.bare") type fuzzRepoState struct { - repo *testgit.TestRepo - cfgPath string + repo *testgit.TestRepo } repos := make(map[objectid.Algorithm]fuzzRepoState, len(objectid.SupportedAlgorithms())) for _, algo := range objectid.SupportedAlgorithms() { testRepo := testgit.NewRepo(f, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) repos[algo] = fuzzRepoState{ - repo: testRepo, - cfgPath: filepath.Join(testRepo.Dir(), "config"), + repo: testRepo, } } @@ -579,12 +558,9 @@ func FuzzConfig(f *testing.F) { t.Fatalf("missing fuzz repo state for %v", algo) } - err := os.WriteFile(state.cfgPath, cfgData, 0o600) - if err != nil { - t.Fatalf("failed to write config: %v", err) - } + state.repo.WriteFile(t, "config", cfgData, 0o600) - gitValue, gitErr := gitConfigGetE(state.repo, gitKey) + gitValue, gitErr := gitConfigGetE(t, state.repo, gitKey) furConfig, furErr := config.ParseConfig(bytes.NewReader(cfgData)) if furErr == nil && furConfig == nil { diff --git a/diff/trees/diff_test.go b/diff/trees/diff_test.go index 1664bdf8..27d6b416 100644 --- a/diff/trees/diff_test.go +++ b/diff/trees/diff_test.go @@ -2,8 +2,6 @@ package trees_test import ( "errors" - "os" - "path/filepath" "testing" "codeberg.org/lindenii/furgit/diff/trees" @@ -19,37 +17,37 @@ func TestDiffComplexNestedChanges(t *testing.T) { testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper repo := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: false}) - writeTestFile(t, filepath.Join(repo.Dir(), "README.md"), "initial readme\n") - writeTestFile(t, filepath.Join(repo.Dir(), "unchanged.txt"), "leave me as-is\n") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "file_a.txt"), "alpha v1\n") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "nested", "file_b.txt"), "beta v1\n") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "nested", "deeper", "file_c.txt"), "gamma v1\n") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "nested", "deeper", "old.txt"), "old branch\n") - writeTestFile(t, filepath.Join(repo.Dir(), "treeB", "legacy.txt"), "legacy root\n") - writeTestFile(t, filepath.Join(repo.Dir(), "treeB", "sub", "retired.txt"), "retired\n") + writeTestFile(t, repo, "README.md", "initial readme\n") + writeTestFile(t, repo, "unchanged.txt", "leave me as-is\n") + writeTestFile(t, repo, "dir/file_a.txt", "alpha v1\n") + writeTestFile(t, repo, "dir/nested/file_b.txt", "beta v1\n") + writeTestFile(t, repo, "dir/nested/deeper/file_c.txt", "gamma v1\n") + writeTestFile(t, repo, "dir/nested/deeper/old.txt", "old branch\n") + writeTestFile(t, repo, "treeB/legacy.txt", "legacy root\n") + writeTestFile(t, repo, "treeB/sub/retired.txt", "retired\n") repo.Run(t, "add", ".") baseTreeID := parseID(t, algo, repo.Run(t, "write-tree")) - writeTestFile(t, filepath.Join(repo.Dir(), "README.md"), "updated readme\n") + writeTestFile(t, repo, "README.md", "updated readme\n") repo.Run(t, "rm", "-f", "dir/file_a.txt") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "nested", "file_b.txt"), "beta v2\n") + writeTestFile(t, repo, "dir/nested/file_b.txt", "beta v2\n") repo.Run(t, "rm", "-f", "dir/nested/deeper/old.txt") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "nested", "deeper", "new.txt"), "new branch entry\n") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "nested", "deeper", "branch", "info.md"), "branch info\n") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "nested", "deeper", "branch", "subbranch", "leaf.txt"), "leaf data\n") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "nested", "deeper", "branch", "subbranch", "deep", "final.txt"), "final artifact\n") - writeTestFile(t, filepath.Join(repo.Dir(), "dir", "newchild.txt"), "brand new sibling\n") + writeTestFile(t, repo, "dir/nested/deeper/new.txt", "new branch entry\n") + writeTestFile(t, repo, "dir/nested/deeper/branch/info.md", "branch info\n") + writeTestFile(t, repo, "dir/nested/deeper/branch/subbranch/leaf.txt", "leaf data\n") + writeTestFile(t, repo, "dir/nested/deeper/branch/subbranch/deep/final.txt", "final artifact\n") + writeTestFile(t, repo, "dir/newchild.txt", "brand new sibling\n") repo.Run(t, "rm", "-r", "-f", "treeB") - writeTestFile(t, filepath.Join(repo.Dir(), "features", "alpha", "README.md"), "alpha docs\n") - writeTestFile(t, filepath.Join(repo.Dir(), "features", "alpha", "beta", "gamma.txt"), "gamma payload\n") - writeTestFile(t, filepath.Join(repo.Dir(), "modules", "v2", "core", "main.go"), "package core\n") - writeTestFile(t, filepath.Join(repo.Dir(), "root_addition.txt"), "root level file\n") + writeTestFile(t, repo, "features/alpha/README.md", "alpha docs\n") + writeTestFile(t, repo, "features/alpha/beta/gamma.txt", "gamma payload\n") + writeTestFile(t, repo, "modules/v2/core/main.go", "package core\n") + writeTestFile(t, repo, "root_addition.txt", "root level file\n") repo.Run(t, "add", ".") updatedTreeID := parseID(t, algo, repo.Run(t, "write-tree")) - store := openLooseStore(t, filepath.Join(repo.Dir(), ".git", "objects"), algo) + store := openLooseStore(t, repo, algo) readTree := makeReadTree(t, store, algo) baseTree := mustReadTree(t, readTree, baseTreeID) updatedTree := mustReadTree(t, readTree, updatedTreeID) @@ -103,22 +101,22 @@ func TestDiffDirectoryAddDeleteDeep(t *testing.T) { testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper repo := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: false}) - writeTestFile(t, filepath.Join(repo.Dir(), "old_dir", "old.txt"), "stale directory\n") - writeTestFile(t, filepath.Join(repo.Dir(), "old_dir", "sub1", "legacy.txt"), "legacy path\n") - writeTestFile(t, filepath.Join(repo.Dir(), "old_dir", "sub1", "nested", "end.txt"), "legacy end\n") + writeTestFile(t, repo, "old_dir/old.txt", "stale directory\n") + writeTestFile(t, repo, "old_dir/sub1/legacy.txt", "legacy path\n") + writeTestFile(t, repo, "old_dir/sub1/nested/end.txt", "legacy end\n") repo.Run(t, "add", ".") originalTreeID := parseID(t, algo, repo.Run(t, "write-tree")) repo.Run(t, "rm", "-r", "-f", "old_dir") - writeTestFile(t, filepath.Join(repo.Dir(), "fresh", "alpha", "beta", "new.txt"), "brand new directory\n") - writeTestFile(t, filepath.Join(repo.Dir(), "fresh", "alpha", "docs", "note.md"), "docs note\n") - writeTestFile(t, filepath.Join(repo.Dir(), "fresh", "alpha", "beta", "gamma", "delta.txt"), "delta payload\n") + writeTestFile(t, repo, "fresh/alpha/beta/new.txt", "brand new directory\n") + writeTestFile(t, repo, "fresh/alpha/docs/note.md", "docs note\n") + writeTestFile(t, repo, "fresh/alpha/beta/gamma/delta.txt", "delta payload\n") repo.Run(t, "add", ".") nextTreeID := parseID(t, algo, repo.Run(t, "write-tree")) - store := openLooseStore(t, filepath.Join(repo.Dir(), ".git", "objects"), algo) + store := openLooseStore(t, repo, algo) readTree := makeReadTree(t, store, algo) originalTree := mustReadTree(t, readTree, originalTreeID) nextTree := mustReadTree(t, readTree, nextTreeID) @@ -155,29 +153,16 @@ type diffExpectation struct { newNil bool } -func writeTestFile(t *testing.T, path, data string) { +func writeTestFile(t *testing.T, repo *testgit.TestRepo, path, data string) { t.Helper() - err := os.MkdirAll(filepath.Dir(path), 0o755) - if err != nil { - t.Fatalf("create directory for %s: %v", path, err) - } - - err = os.WriteFile(path, []byte(data), 0o644) - if err != nil { - t.Fatalf("write %s: %v", path, err) - } + repo.WriteFileAll(t, path, []byte(data), 0o755, 0o644) } -func openLooseStore(t *testing.T, objectsPath string, algo objectid.Algorithm) *loose.Store { +func openLooseStore(t *testing.T, repo *testgit.TestRepo, algo objectid.Algorithm) *loose.Store { t.Helper() - root, err := os.OpenRoot(objectsPath) - if err != nil { - t.Fatalf("OpenRoot(%q): %v", objectsPath, err) - } - - t.Cleanup(func() { _ = root.Close() }) + root := repo.OpenObjectsRoot(t) store, err := loose.New(root, algo) if err != nil { diff --git a/errors/doc.go b/errors/doc.go new file mode 100644 index 00000000..32afcd10 --- /dev/null +++ b/errors/doc.go @@ -0,0 +1,2 @@ +// Package errors defines error types shared across furgit. +package errors diff --git a/errors/missing.go b/errors/missing.go new file mode 100644 index 00000000..3ca27583 --- /dev/null +++ b/errors/missing.go @@ -0,0 +1,18 @@ +package errors + +import ( + "fmt" + + "codeberg.org/lindenii/furgit/objectid" +) + +// ObjectMissingError indicates that a referenced object is absent from the +// repository object store. +type ObjectMissingError struct { + OID objectid.ObjectID +} + +// Error implements error. +func (e *ObjectMissingError) Error() string { + return fmt.Sprintf("missing object %s", e.OID) +} diff --git a/errors/type.go b/errors/type.go new file mode 100644 index 00000000..82ca993a --- /dev/null +++ b/errors/type.go @@ -0,0 +1,31 @@ +package errors + +import ( + "fmt" + + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objecttype" +) + +// ObjectTypeError indicates that a referenced object has a different type than +// what the operation expected. +type ObjectTypeError struct { + OID objectid.ObjectID + Got objecttype.Type + Want objecttype.Type +} + +// Error implements error. +func (e *ObjectTypeError) Error() string { + gotName, gotOK := objecttype.Name(e.Got) + if !gotOK { + gotName = fmt.Sprintf("type(%d)", e.Got) + } + + wantName, wantOK := objecttype.Name(e.Want) + if !wantOK { + wantName = fmt.Sprintf("type(%d)", e.Want) + } + + return fmt.Sprintf("object %s has type %s, want %s", e.OID, gotName, wantName) +} diff --git a/format/commitgraph/read/read_test.go b/format/commitgraph/read/read_test.go index 35384930..234ece6b 100644 --- a/format/commitgraph/read/read_test.go +++ b/format/commitgraph/read/read_test.go @@ -2,7 +2,6 @@ package read_test import ( "errors" - "os" "path/filepath" "strconv" "strings" @@ -174,22 +173,11 @@ func TestBloomUnavailableWithoutChangedPaths(t *testing.T) { func openReader(tb testing.TB, testRepo *testgit.TestRepo, mode read.OpenMode) *read.Reader { tb.Helper() - objectsPath := filepath.Join(testRepo.Dir(), "objects") - - root, err := os.OpenRoot(objectsPath) - if err != nil { - tb.Fatalf("os.OpenRoot(%q): %v", objectsPath, err) - } + root := testRepo.OpenObjectsRoot(tb) reader, err := read.Open(root, testRepo.Algorithm(), mode) - - closeErr := root.Close() - if closeErr != nil { - tb.Fatalf("close objects root: %v", closeErr) - } - if err != nil { - tb.Fatalf("read.Open(%q): %v", objectsPath, err) + tb.Fatalf("read.Open(objects): %v", err) } return reader diff --git a/format/pack/ingest/ingest_test.go b/format/pack/ingest/ingest_test.go index 13f7ee85..8f50b3d1 100644 --- a/format/pack/ingest/ingest_test.go +++ b/format/pack/ingest/ingest_test.go @@ -3,6 +3,7 @@ package ingest_test import ( "bytes" "errors" + "io/fs" "os" "path/filepath" "strings" @@ -11,7 +12,6 @@ import ( "codeberg.org/lindenii/furgit/format/pack/ingest" "codeberg.org/lindenii/furgit/internal/testgit" "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/repository" ) // fixturePath returns one fixture file path for the selected algorithm. @@ -99,27 +99,17 @@ func fixtureOID(t *testing.T, algo objectid.Algorithm, key string) objectid.Obje // verifyReindexOracle regenerates idx/rev with upstream git index-pack and // compares bytes with files produced by ingest. -func verifyReindexOracle(t *testing.T, repo *testgit.TestRepo, packPath, idxPath, revPath string) { +func verifyReindexOracle(t *testing.T, repo *testgit.TestRepo, packName, idxName, revName string) { t.Helper() oracleDir := t.TempDir() oracleIdxPath := filepath.Join(oracleDir, "oracle.idx") - _ = repo.Run(t, "index-pack", "--rev-index", "-o", oracleIdxPath, packPath) + _ = repo.Run(t, "index-pack", "--rev-index", "-o", oracleIdxPath, filepath.Join("objects", "pack", packName)) oracleRevPath := strings.TrimSuffix(oracleIdxPath, ".idx") + ".rev" - idxRoot, err := os.OpenRoot(filepath.Dir(idxPath)) - if err != nil { - t.Fatalf("open idx root: %v", err) - } + packRoot := repo.OpenPackRoot(t) - defer func() { - err := idxRoot.Close() - if err != nil { - t.Fatalf("close idx root: %v", err) - } - }() - - gotIdx, err := idxRoot.ReadFile(filepath.Base(idxPath)) + gotIdx, err := packRoot.ReadFile(idxName) if err != nil { t.Fatalf("read idx: %v", err) } @@ -145,7 +135,7 @@ func verifyReindexOracle(t *testing.T, repo *testgit.TestRepo, packPath, idxPath t.Fatal("idx bytes differ from git index-pack output") } - gotRev, err := idxRoot.ReadFile(filepath.Base(revPath)) + gotRev, err := packRoot.ReadFile(revName) if err != nil { t.Fatalf("read rev: %v", err) } @@ -169,17 +159,7 @@ func TestIngestNonThinPackWritesPackIdxRev(t *testing.T) { receiver := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - packRoot, err := os.OpenRoot(filepath.Join(receiver.Dir(), "objects", "pack")) - if err != nil { - t.Fatalf("open pack root: %v", err) - } - - defer func() { - err = packRoot.Close() - if err != nil { - t.Fatalf("close pack root: %v", err) - } - }() + packRoot := receiver.OpenPackRoot(t) result, err := ingest.Ingest(bytes.NewReader(packBytes), packRoot, algo, false, true, nil) if err != nil { @@ -209,11 +189,8 @@ func TestIngestNonThinPackWritesPackIdxRev(t *testing.T) { t.Fatalf("stat rev: %v", err) } - idxPath := filepath.Join(receiver.Dir(), "objects", "pack", result.IdxName) - packPath := filepath.Join(receiver.Dir(), "objects", "pack", result.PackName) - revPath := filepath.Join(receiver.Dir(), "objects", "pack", result.RevName) - _ = receiver.Run(t, "verify-pack", "-v", idxPath) - verifyReindexOracle(t, receiver, packPath, idxPath, revPath) + _ = receiver.Run(t, "verify-pack", "-v", filepath.Join("objects", "pack", result.IdxName)) + verifyReindexOracle(t, receiver, result.PackName, result.IdxName, result.RevName) receiver.UpdateRef(t, "refs/heads/main", head) _ = receiver.Run(t, "fsck", "--full", "--strict", "--no-progress", "--no-dangling") @@ -227,21 +204,9 @@ func TestIngestThinPackWithoutFixReturnsUnresolved(t *testing.T) { thinPack := fixtureBytes(t, algo, "thin.pack") receiver := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - packDir := filepath.Join(receiver.Dir(), "objects", "pack") - - packRoot, err := os.OpenRoot(packDir) - if err != nil { - t.Fatalf("open pack root: %v", err) - } + packRoot := receiver.OpenPackRoot(t) - defer func() { - err = packRoot.Close() - if err != nil { - t.Fatalf("close pack root: %v", err) - } - }() - - _, err = ingest.Ingest(bytes.NewReader(thinPack), packRoot, algo, false, true, nil) + _, err := ingest.Ingest(bytes.NewReader(thinPack), packRoot, algo, false, true, nil) if err == nil { t.Fatal("Ingest error = nil, want error") } @@ -251,13 +216,15 @@ func TestIngestThinPackWithoutFixReturnsUnresolved(t *testing.T) { t.Fatalf("Ingest error type = %T (%v), want *ThinPackUnresolvedError", err, err) } - matches, err := filepath.Glob(filepath.Join(packDir, "pack-*.pack")) + entries, err := fs.ReadDir(packRoot.FS(), ".") if err != nil { - t.Fatalf("glob pack files: %v", err) + t.Fatalf("ReadDir(pack): %v", err) } - if len(matches) != 0 { - t.Fatalf("found finalized pack files after failure: %v", matches) + for _, entry := range entries { + if strings.HasSuffix(entry.Name(), ".pack") { + t.Fatalf("found finalized pack file after failure: %v", entry.Name()) + } } }) } @@ -271,46 +238,14 @@ func TestIngestThinPackWithFixThin(t *testing.T) { thinPack := fixtureBytes(t, algo, "thin.pack") receiver := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - packRoot, err := os.OpenRoot(filepath.Join(receiver.Dir(), "objects", "pack")) - if err != nil { - t.Fatalf("open pack root: %v", err) - } - - defer func() { - err = packRoot.Close() - if err != nil { - t.Fatalf("close pack root: %v", err) - } - }() + packRoot := receiver.OpenPackRoot(t) - _, err = ingest.Ingest(bytes.NewReader(basePack), packRoot, algo, false, false, nil) + _, err := ingest.Ingest(bytes.NewReader(basePack), packRoot, algo, false, false, nil) if err != nil { t.Fatalf("ingest base pack: %v", err) } - receiverRoot, err := os.OpenRoot(receiver.Dir()) - if err != nil { - t.Fatalf("open receiver root: %v", err) - } - - defer func() { - err = receiverRoot.Close() - if err != nil { - t.Fatalf("close receiver root: %v", err) - } - }() - - receiverRepo, err := repository.Open(receiverRoot) - if err != nil { - t.Fatalf("repository.Open(receiver): %v", err) - } - - defer func() { - err = receiverRepo.Close() - if err != nil { - t.Fatalf("close receiver repo: %v", err) - } - }() + receiverRepo := receiver.OpenRepository(t) result, err := ingest.Ingest(bytes.NewReader(thinPack), packRoot, algo, true, true, receiverRepo.Objects()) if err != nil { @@ -321,11 +256,8 @@ func TestIngestThinPackWithFixThin(t *testing.T) { t.Fatal("ThinFixed = false, want true") } - idxPath := filepath.Join(receiver.Dir(), "objects", "pack", result.IdxName) - packPath := filepath.Join(receiver.Dir(), "objects", "pack", result.PackName) - revPath := filepath.Join(receiver.Dir(), "objects", "pack", result.RevName) - _ = receiver.Run(t, "verify-pack", "-v", idxPath) - verifyReindexOracle(t, receiver, packPath, idxPath, revPath) + _ = receiver.Run(t, "verify-pack", "-v", filepath.Join("objects", "pack", result.IdxName)) + verifyReindexOracle(t, receiver, result.PackName, result.IdxName, result.RevName) receiver.UpdateRef(t, "refs/heads/main", head) _ = receiver.Run(t, "fsck", "--full", "--strict", "--no-progress", "--no-dangling") }) @@ -343,21 +275,9 @@ func TestIngestPackTrailerMismatch(t *testing.T) { packBytes[len(packBytes)-1] ^= 0xff receiver := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - packDir := filepath.Join(receiver.Dir(), "objects", "pack") + packRoot := receiver.OpenPackRoot(t) - packRoot, err := os.OpenRoot(packDir) - if err != nil { - t.Fatalf("open pack root: %v", err) - } - - defer func() { - err = packRoot.Close() - if err != nil { - t.Fatalf("close pack root: %v", err) - } - }() - - _, err = ingest.Ingest(bytes.NewReader(packBytes), packRoot, algo, false, true, nil) + _, err := ingest.Ingest(bytes.NewReader(packBytes), packRoot, algo, false, true, nil) if err == nil { t.Fatal("Ingest error = nil, want error") } @@ -367,13 +287,15 @@ func TestIngestPackTrailerMismatch(t *testing.T) { t.Fatalf("Ingest error type = %T (%v), want *PackTrailerMismatchError", err, err) } - matches, err := filepath.Glob(filepath.Join(packDir, "pack-*.pack")) + entries, err := fs.ReadDir(packRoot.FS(), ".") if err != nil { - t.Fatalf("glob pack files: %v", err) + t.Fatalf("ReadDir(pack): %v", err) } - if len(matches) != 0 { - t.Fatalf("found finalized pack files after failure: %v", matches) + for _, entry := range entries { + if strings.HasSuffix(entry.Name(), ".pack") { + t.Fatalf("found finalized pack file after failure: %v", entry.Name()) + } } }) } diff --git a/internal/commitquery/ancestor.go b/internal/commitquery/ancestor.go new file mode 100644 index 00000000..78149c6a --- /dev/null +++ b/internal/commitquery/ancestor.go @@ -0,0 +1,30 @@ +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/bits.go b/internal/commitquery/bits.go new file mode 100644 index 00000000..36ffff29 --- /dev/null +++ b/internal/commitquery/bits.go @@ -0,0 +1,14 @@ +package commitquery + +type markBits uint8 + +const ( + markLeft markBits = 1 << iota + markRight + markStale + markResult +) + +const ( + allMarks = markLeft | markRight | markStale | markResult +) diff --git a/internal/commitquery/commit.go b/internal/commitquery/commit.go new file mode 100644 index 00000000..548aae4d --- /dev/null +++ b/internal/commitquery/commit.go @@ -0,0 +1,17 @@ +package commitquery + +import ( + commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" +) + +// Commit stores the metadata needed by commit-domain queries. +type Commit struct { + ID objectid.ObjectID + Parents []Parent + CommitTime int64 + Generation uint64 + HasGeneration bool + GraphPos commitgraphread.Position + HasGraphPos bool +} diff --git a/internal/commitquery/compare.go b/internal/commitquery/compare.go new file mode 100644 index 00000000..748ef712 --- /dev/null +++ b/internal/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 (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 new file mode 100644 index 00000000..f39c32c8 --- /dev/null +++ b/internal/commitquery/context.go @@ -0,0 +1,32 @@ +// Package commitquery provides private commit-domain query routines. +package commitquery + +import ( + commitgraphread "codeberg.org/lindenii/furgit/format/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/errors.go b/internal/commitquery/errors.go new file mode 100644 index 00000000..e99011d0 --- /dev/null +++ b/internal/commitquery/errors.go @@ -0,0 +1,5 @@ +package commitquery + +import "errors" + +var errBadGenerationOrder = errors.New("commitquery: priority queue violated generation ordering") diff --git a/internal/commitquery/generation.go b/internal/commitquery/generation.go new file mode 100644 index 00000000..c5edcd9f --- /dev/null +++ b/internal/commitquery/generation.go @@ -0,0 +1,43 @@ +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 new file mode 100644 index 00000000..2031e3d8 --- /dev/null +++ b/internal/commitquery/graph_pos.go @@ -0,0 +1,107 @@ +package commitquery + +import commitgraphread "codeberg.org/lindenii/furgit/format/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 new file mode 100644 index 00000000..b795f7d9 --- /dev/null +++ b/internal/commitquery/load.go @@ -0,0 +1,14 @@ +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 new file mode 100644 index 00000000..f88fdf25 --- /dev/null +++ b/internal/commitquery/marks.go @@ -0,0 +1,67 @@ +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 new file mode 100644 index 00000000..b0171f5e --- /dev/null +++ b/internal/commitquery/merge_bases.go @@ -0,0 +1,105 @@ +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 + } + + candidates, err := paintDownToCommon(ctx, left, []NodeIndex{right}, 0) + if err != nil { + return nil, err + } + + 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) ([]NodeIndex, error) { + ctx.BeginMarkPhase() + + ctx.SetMarks(left, markLeft) + + if len(rights) == 0 { + return []NodeIndex{left}, nil + } + + queue := NewPriorityQueue(ctx) + queue.PushNode(left) + + for _, right := range rights { + ctx.SetMarks(right, markRight) + queue.PushNode(right) + } + + lastGeneration := generationInfinity + results := make([]NodeIndex, 0, 4) + + for queueHasNonStale(ctx, queue) { + idx := queue.PopNode() + + generation := ctx.EffectiveGeneration(idx) + if generation > lastGeneration { + return nil, errBadGenerationOrder + } + + lastGeneration = generation + if generation < minGeneration { + break + } + + flags := ctx.Marks(idx) & (markLeft | markRight | markStale) + if flags == (markLeft | markRight) { + if !ctx.HasAnyMarks(idx, markResult) { + ctx.SetMarks(idx, markResult) + results = append(results, idx) + } + + flags |= markStale + } + + for _, parent := range ctx.Parents(idx) { + if ctx.HasAllMarks(parent, flags) { + continue + } + + ctx.SetMarks(parent, flags) + queue.PushNode(parent) + } + } + + out := results[:0] + for _, idx := range results { + if !ctx.HasAnyMarks(idx, markStale) { + out = append(out, idx) + } + } + + return out, nil +} + +func queueHasNonStale(ctx *Context, queue *PriorityQueue) bool { + for _, idx := range queue.items { + if !ctx.HasAnyMarks(idx, markStale) { + return true + } + } + + return false +} diff --git a/internal/commitquery/node.go b/internal/commitquery/node.go new file mode 100644 index 00000000..7abf381d --- /dev/null +++ b/internal/commitquery/node.go @@ -0,0 +1,39 @@ +package commitquery + +import ( + commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" +) + +// NodeIndex identifies one internal query node. +type NodeIndex int + +// node stores one mutable commit traversal node. +type node struct { + id objectid.ObjectID + + parents []NodeIndex + + commitTime int64 + generation uint64 + + hasGeneration bool + hasGraphPos bool + loaded bool + + graphPos commitgraphread.Position + marks markBits + + touchedPhase uint32 +} + +// newNode allocates one empty internal node. +func (ctx *Context) newNode(id objectid.ObjectID) NodeIndex { + count := len(ctx.nodes) + + idx := NodeIndex(count) + + ctx.nodes = append(ctx.nodes, node{id: id}) + + return idx +} diff --git a/internal/commitquery/oid.go b/internal/commitquery/oid.go new file mode 100644 index 00000000..7ba05eb5 --- /dev/null +++ b/internal/commitquery/oid.go @@ -0,0 +1,95 @@ +package commitquery + +import ( + stderrors "errors" + + giterrors "codeberg.org/lindenii/furgit/errors" + commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" + "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 +} + +// CommitTime returns the committer timestamp used for one internal node. +func (ctx *Context) CommitTime(idx NodeIndex) int64 { + return ctx.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] + if ok { + err := ctx.ensureLoaded(idx) + if err != nil { + return 0, err + } + + return idx, nil + } + + idx = ctx.newNode(id) + ctx.byOID[id] = idx + + err := ctx.loadByOID(idx) + if err != nil { + delete(ctx.byOID, id) + + return 0, err + } + + return idx, nil +} + +// loadByOID populates one node from an object ID. +func (ctx *Context) loadByOID(idx NodeIndex) error { + id := ctx.nodes[idx].id + + if ctx.graph != nil { + pos, err := ctx.graph.Lookup(id) + if err != nil { + var notFound *commitgraphread.NotFoundError + if !stderrors.As(err, ¬Found) { + return err + } + } else { + return ctx.loadCommitAtGraphPos(idx, pos) + } + } + + ty, content, err := ctx.store.ReadBytesContent(id) + if err != nil { + if stderrors.Is(err, objectstore.ErrObjectNotFound) { + return &giterrors.ObjectMissingError{OID: id} + } + + return err + } + + if ty != objecttype.TypeCommit { + return &giterrors.ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit} + } + + commitObj, err := object.ParseCommit(content, id.Algorithm()) + if err != nil { + return err + } + + parents := make([]Parent, 0, len(commitObj.Parents)) + for _, parentID := range commitObj.Parents { + parents = append(parents, Parent{ID: parentID}) + } + + commit := Commit{ + ID: id, + Parents: parents, + CommitTime: commitObj.Committer.WhenUnix, + } + + return ctx.populateNode(idx, commit) +} diff --git a/internal/commitquery/parent.go b/internal/commitquery/parent.go new file mode 100644 index 00000000..17695e09 --- /dev/null +++ b/internal/commitquery/parent.go @@ -0,0 +1,27 @@ +package commitquery + +import ( + commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" +) + +// Parent references one commit parent. +type Parent 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 +} + +// resolveParent resolves one parent descriptor to one internal node. +func (ctx *Context) resolveParent(parent Parent) (NodeIndex, error) { + if parent.HasGraphPos { + return ctx.ResolveGraphPos(parent.GraphPos) + } + + return ctx.ResolveOID(parent.ID) +} diff --git a/internal/commitquery/populate.go b/internal/commitquery/populate.go new file mode 100644 index 00000000..87d65bf8 --- /dev/null +++ b/internal/commitquery/populate.go @@ -0,0 +1,42 @@ +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/priority_queue.go b/internal/commitquery/priority_queue.go new file mode 100644 index 00000000..a7a4876e --- /dev/null +++ b/internal/commitquery/priority_queue.go @@ -0,0 +1,68 @@ +package commitquery + +import "container/heap" + +// PriorityQueue orders internal nodes using one query context's comparator. +type PriorityQueue struct { + ctx *Context + items []NodeIndex +} + +// NewPriorityQueue builds one empty priority queue over one query context. +func NewPriorityQueue(ctx *Context) *PriorityQueue { + queue := &PriorityQueue{ctx: ctx} + heap.Init(queue) + + return queue +} + +// Len reports the number of queued items. +func (queue *PriorityQueue) Len() int { + return len(queue.items) +} + +// Less reports whether one heap slot sorts ahead of another. +func (queue *PriorityQueue) Less(left, right int) bool { + return queue.ctx.Compare(queue.items[left], queue.items[right]) > 0 +} + +// Swap exchanges two heap slots. +func (queue *PriorityQueue) Swap(left, right int) { + queue.items[left], queue.items[right] = queue.items[right], queue.items[left] +} + +// Push appends one heap element. +func (queue *PriorityQueue) Push(item any) { + idx, ok := item.(NodeIndex) + if !ok { + panic("commitquery: heap push item is not a NodeIndex") + } + + queue.items = append(queue.items, idx) +} + +// Pop removes one heap element. +func (queue *PriorityQueue) Pop() any { + last := len(queue.items) - 1 + item := queue.items[last] + queue.items = queue.items[:last] + + return item +} + +// PushNode inserts one internal node. +func (queue *PriorityQueue) PushNode(idx NodeIndex) { + heap.Push(queue, idx) +} + +// PopNode removes the highest-priority internal node. +func (queue *PriorityQueue) PopNode() NodeIndex { + item := heap.Pop(queue) + + idx, ok := item.(NodeIndex) + if !ok { + panic("commitquery: heap pop item is not a NodeIndex") + } + + return idx +} diff --git a/internal/commitquery/reduce.go b/internal/commitquery/reduce.go new file mode 100644 index 00000000..497ff443 --- /dev/null +++ b/internal/commitquery/reduce.go @@ -0,0 +1,166 @@ +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/internal/peel/peel.go b/internal/peel/peel.go new file mode 100644 index 00000000..a3e84b8d --- /dev/null +++ b/internal/peel/peel.go @@ -0,0 +1,50 @@ +// Package peel peels Git object references through annotated tags. +package peel + +import ( + stderrors "errors" + + giterrors "codeberg.org/lindenii/furgit/errors" + "codeberg.org/lindenii/furgit/object" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore" + "codeberg.org/lindenii/furgit/objecttype" +) + +// ToCommit peels annotated tags transitively until a commit is reached. +func ToCommit(store objectstore.Store, id objectid.ObjectID) (objectid.ObjectID, error) { + for { + ty, _, err := store.ReadHeader(id) + if err != nil { + if stderrors.Is(err, objectstore.ErrObjectNotFound) { + return objectid.ObjectID{}, &giterrors.ObjectMissingError{OID: id} + } + + return objectid.ObjectID{}, err + } + + if ty != objecttype.TypeTag { + if ty != objecttype.TypeCommit { + return objectid.ObjectID{}, &giterrors.ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit} + } + + return id, nil + } + + _, content, err := store.ReadBytesContent(id) + if err != nil { + if stderrors.Is(err, objectstore.ErrObjectNotFound) { + return objectid.ObjectID{}, &giterrors.ObjectMissingError{OID: id} + } + + return objectid.ObjectID{}, err + } + + tag, err := object.ParseTag(content, id.Algorithm()) + if err != nil { + return objectid.ObjectID{}, err + } + + id = tag.Target + } +} diff --git a/internal/testgit/repo_commit_tree_env.go b/internal/testgit/repo_commit_tree_env.go new file mode 100644 index 00000000..ee949b5c --- /dev/null +++ b/internal/testgit/repo_commit_tree_env.go @@ -0,0 +1,51 @@ +package testgit + +import ( + "slices" + "strings" + "testing" + + "codeberg.org/lindenii/furgit/objectid" +) + +// CommitTreeWithEnv creates one commit from a tree and message, optionally with +// parents, using additional environment variables for the git subprocess. +func (testRepo *TestRepo) CommitTreeWithEnv( + tb testing.TB, + extraEnv []string, + tree objectid.ObjectID, + message string, + parents ...objectid.ObjectID, +) objectid.ObjectID { + tb.Helper() + + args := make([]string, 0, 2+2*len(parents)+2) + + args = append(args, "commit-tree", tree.String()) + for _, parent := range parents { + args = append(args, "-p", parent.String()) + } + + args = append(args, "-m", message) + hex := testRepo.runWithExtraEnv(tb, extraEnv, args...) + + id, err := objectid.ParseHex(testRepo.algo, hex) + if err != nil { + tb.Fatalf("parse commit-tree output %q: %v", hex, err) + } + + return id +} + +func (testRepo *TestRepo) runWithExtraEnv(tb testing.TB, extraEnv []string, args ...string) string { + tb.Helper() + + env := slices.Concat(testRepo.env, extraEnv) + + out, err := testRepo.runBytesWithEnv(tb, nil, testRepo.dir, env, args...) + if err != nil { + tb.Fatalf("git %v failed: %v\n%s", args, err, out) + } + + return strings.TrimSpace(string(out)) +} diff --git a/internal/testgit/repo_fs.go b/internal/testgit/repo_fs.go new file mode 100644 index 00000000..56acbfcf --- /dev/null +++ b/internal/testgit/repo_fs.go @@ -0,0 +1,86 @@ +package testgit + +import ( + "os" + "path/filepath" + "testing" +) + +// OpenFile opens one file relative to the repository root. +func (testRepo *TestRepo) OpenFile(tb testing.TB, name string) *os.File { + tb.Helper() + + root := testRepo.OpenRoot(tb) + + file, err := root.Open(name) + if err != nil { + tb.Fatalf("Open(%q): %v", name, err) + } + + return file +} + +// ReadFile reads one file relative to the repository root. +func (testRepo *TestRepo) ReadFile(tb testing.TB, name string) []byte { + tb.Helper() + + root := testRepo.OpenRoot(tb) + + data, err := root.ReadFile(name) + if err != nil { + tb.Fatalf("ReadFile(%q): %v", name, err) + } + + return data +} + +// WriteFile writes one file relative to the repository root. +func (testRepo *TestRepo) WriteFile(tb testing.TB, name string, data []byte, perm os.FileMode) { + tb.Helper() + + root := testRepo.OpenRoot(tb) + + err := root.WriteFile(name, data, perm) + if err != nil { + tb.Fatalf("WriteFile(%q): %v", name, err) + } +} + +// WriteFileAll writes one file relative to the repository root, creating any +// missing parent directories first. +func (testRepo *TestRepo) WriteFileAll( + tb testing.TB, + name string, + data []byte, + dirPerm os.FileMode, + filePerm os.FileMode, +) { + tb.Helper() + + root := testRepo.OpenRoot(tb) + + dir := filepath.Dir(name) + if dir != "." { + err := root.MkdirAll(dir, dirPerm) + if err != nil { + tb.Fatalf("MkdirAll(%q): %v", dir, err) + } + } + + err := root.WriteFile(name, data, filePerm) + if err != nil { + tb.Fatalf("WriteFile(%q): %v", name, err) + } +} + +// Remove removes one path relative to the repository root. +func (testRepo *TestRepo) Remove(tb testing.TB, name string) { + tb.Helper() + + root := testRepo.OpenRoot(tb) + + err := root.Remove(name) + if err != nil { + tb.Fatalf("Remove(%q): %v", name, err) + } +} diff --git a/internal/testgit/repo_open_commit_graph.go b/internal/testgit/repo_open_commit_graph.go new file mode 100644 index 00000000..4db7261b --- /dev/null +++ b/internal/testgit/repo_open_commit_graph.go @@ -0,0 +1,26 @@ +package testgit + +import ( + "testing" + + commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" +) + +// OpenCommitGraph opens the repository commit-graph and registers cleanup on +// the caller. +func (testRepo *TestRepo) OpenCommitGraph(tb testing.TB) *commitgraphread.Reader { + tb.Helper() + + objectsRoot := testRepo.OpenObjectsRoot(tb) + + graph, err := commitgraphread.Open(objectsRoot, testRepo.Algorithm(), commitgraphread.OpenSingle) + if err != nil { + tb.Fatalf("commitgraphread.Open: %v", err) + } + + tb.Cleanup(func() { + _ = graph.Close() + }) + + return graph +} diff --git a/internal/testgit/repo_open_object_store.go b/internal/testgit/repo_open_object_store.go new file mode 100644 index 00000000..aac71d60 --- /dev/null +++ b/internal/testgit/repo_open_object_store.go @@ -0,0 +1,29 @@ +package testgit + +import ( + "testing" + + "codeberg.org/lindenii/furgit/objectstore" + "codeberg.org/lindenii/furgit/repository" +) + +// OpenObjectStore opens the repository object store and registers cleanup on +// the caller. +// +//nolint:ireturn +func (testRepo *TestRepo) OpenObjectStore(tb testing.TB) objectstore.Store { + tb.Helper() + + root := testRepo.OpenGitRoot(tb) + + repo, err := repository.Open(root) + if err != nil { + tb.Fatalf("repository.Open: %v", err) + } + + tb.Cleanup(func() { + _ = repo.Close() + }) + + return repo.Objects() +} diff --git a/internal/testgit/repo_open_repository.go b/internal/testgit/repo_open_repository.go new file mode 100644 index 00000000..fbc98383 --- /dev/null +++ b/internal/testgit/repo_open_repository.go @@ -0,0 +1,25 @@ +package testgit + +import ( + "testing" + + "codeberg.org/lindenii/furgit/repository" +) + +// OpenRepository opens the repository and registers cleanup on the caller. +func (testRepo *TestRepo) OpenRepository(tb testing.TB) *repository.Repository { + tb.Helper() + + root := testRepo.OpenGitRoot(tb) + + repo, err := repository.Open(root) + if err != nil { + tb.Fatalf("repository.Open: %v", err) + } + + tb.Cleanup(func() { + _ = repo.Close() + }) + + return repo +} diff --git a/internal/testgit/repo_open_root.go b/internal/testgit/repo_open_root.go new file mode 100644 index 00000000..4530c604 --- /dev/null +++ b/internal/testgit/repo_open_root.go @@ -0,0 +1,87 @@ +package testgit + +import ( + "errors" + "os" + "testing" +) + +// OpenRoot opens the repository root directory and registers cleanup on the +// caller. +func (testRepo *TestRepo) OpenRoot(tb testing.TB) *os.Root { + tb.Helper() + + root, err := os.OpenRoot(testRepo.dir) + if err != nil { + tb.Fatalf("os.OpenRoot: %v", err) + } + + tb.Cleanup(func() { + _ = root.Close() + }) + + return root +} + +// OpenGitRoot opens the repository gitdir and registers cleanup on the caller. +// +// For bare repositories, this is the repository root itself. For non-bare +// repositories, this is the .git directory under the worktree root. +func (testRepo *TestRepo) OpenGitRoot(tb testing.TB) *os.Root { + tb.Helper() + + repoRoot := testRepo.OpenRoot(tb) + + gitRoot, err := repoRoot.OpenRoot(".git") + if err == nil { + tb.Cleanup(func() { + _ = gitRoot.Close() + }) + + return gitRoot + } + + if !errors.Is(err, os.ErrNotExist) { + tb.Fatalf("OpenRoot(.git): %v", err) + } + + return repoRoot +} + +// OpenObjectsRoot opens the objects directory and registers cleanup on the +// caller. +func (testRepo *TestRepo) OpenObjectsRoot(tb testing.TB) *os.Root { + tb.Helper() + + gitRoot := testRepo.OpenGitRoot(tb) + + objectsRoot, err := gitRoot.OpenRoot("objects") + if err != nil { + tb.Fatalf("OpenRoot(objects): %v", err) + } + + tb.Cleanup(func() { + _ = objectsRoot.Close() + }) + + return objectsRoot +} + +// OpenPackRoot opens the objects/pack directory and registers cleanup on the +// caller. +func (testRepo *TestRepo) OpenPackRoot(tb testing.TB) *os.Root { + tb.Helper() + + objectsRoot := testRepo.OpenObjectsRoot(tb) + + packRoot, err := objectsRoot.OpenRoot("pack") + if err != nil { + tb.Fatalf("OpenRoot(pack): %v", err) + } + + tb.Cleanup(func() { + _ = packRoot.Close() + }) + + return packRoot +} diff --git a/internal/testgit/repo_properties.go b/internal/testgit/repo_properties.go index 3a489124..703cef1c 100644 --- a/internal/testgit/repo_properties.go +++ b/internal/testgit/repo_properties.go @@ -2,11 +2,6 @@ package testgit import "codeberg.org/lindenii/furgit/objectid" -// Dir returns the repository directory path. -func (testRepo *TestRepo) Dir() string { - return testRepo.dir -} - // Algorithm returns the object ID algorithm configured for this repository. func (testRepo *TestRepo) Algorithm() objectid.Algorithm { return testRepo.algo diff --git a/internal/testgit/repo_remove_loose_object.go b/internal/testgit/repo_remove_loose_object.go new file mode 100644 index 00000000..ec3d8c2d --- /dev/null +++ b/internal/testgit/repo_remove_loose_object.go @@ -0,0 +1,22 @@ +package testgit + +import ( + "fmt" + "testing" + + "codeberg.org/lindenii/furgit/objectid" +) + +// RemoveLooseObject removes one loose object file from the repository. +func (testRepo *TestRepo) RemoveLooseObject(tb testing.TB, id objectid.ObjectID) { + tb.Helper() + + root := testRepo.OpenObjectsRoot(tb) + hex := id.String() + path := fmt.Sprintf("%s/%s", hex[:2], hex[2:]) + + err := root.Remove(path) + if err != nil { + tb.Fatalf("remove loose object %s: %v", id, err) + } +} diff --git a/internal/testgit/repo_run.go b/internal/testgit/repo_run.go index 162a0d72..448b88f0 100644 --- a/internal/testgit/repo_run.go +++ b/internal/testgit/repo_run.go @@ -22,6 +22,15 @@ func (testRepo *TestRepo) RunBytes(tb testing.TB, args ...string) []byte { return testRepo.runBytes(tb, nil, testRepo.dir, args...) } +// RunE executes git and returns trimmed textual output plus any command error. +func (testRepo *TestRepo) RunE(tb testing.TB, args ...string) (string, error) { + tb.Helper() + + out, err := testRepo.runBytesE(nil, testRepo.dir, args...) + + return strings.TrimSpace(string(out)), err +} + // RunInput executes git with stdin and returns trimmed textual output. func (testRepo *TestRepo) RunInput(tb testing.TB, stdin []byte, args ...string) string { tb.Helper() @@ -39,19 +48,48 @@ func (testRepo *TestRepo) RunInputBytes(tb testing.TB, stdin []byte, args ...str func (testRepo *TestRepo) runBytes(tb testing.TB, stdin []byte, dir string, args ...string) []byte { tb.Helper() + + out, err := testRepo.runBytesE(stdin, dir, args...) + if err != nil { + tb.Fatalf("git %v failed: %v\n%s", args, err, out) + } + + return out +} + +func (testRepo *TestRepo) runBytesE(stdin []byte, dir string, args ...string) ([]byte, error) { + return testRepo.runBytesWithEnvNoHelper(stdin, dir, testRepo.env, args...) +} + +// runBytesWithEnv executes git using the supplied environment. +func (testRepo *TestRepo) runBytesWithEnv( + tb testing.TB, + stdin []byte, + dir string, + env []string, + args ...string, +) ([]byte, error) { + tb.Helper() + + return testRepo.runBytesWithEnvNoHelper(stdin, dir, env, args...) +} + +// runBytesWithEnvNoHelper executes git using the supplied environment without +// touching testing helper state. +func (testRepo *TestRepo) runBytesWithEnvNoHelper( + stdin []byte, + dir string, + env []string, + args ...string, +) ([]byte, error) { //nolint:noctx cmd := exec.Command("git", args...) //#nosec G204 cmd.Dir = dir - cmd.Env = testRepo.env + cmd.Env = env if stdin != nil { cmd.Stdin = bytes.NewReader(stdin) } - out, err := cmd.CombinedOutput() - if err != nil { - tb.Fatalf("git %v failed: %v\n%s", args, err, out) - } - - return out + return cmd.CombinedOutput() } diff --git a/mergebase/base.go b/mergebase/base.go new file mode 100644 index 00000000..ee0473b3 --- /dev/null +++ b/mergebase/base.go @@ -0,0 +1,43 @@ +package mergebase + +import ( + commitgraphread "codeberg.org/lindenii/furgit/format/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) + seq := query.Seq() + + var ( + first objectid.ObjectID + ok bool + ) + + seq(func(id objectid.ObjectID) bool { + first = id + ok = true + + return false + }) + + err := query.Err() + if err != nil { + return objectid.ObjectID{}, false, err + } + + if !ok { + return objectid.ObjectID{}, false, nil + } + + return first, true, nil +} diff --git a/mergebase/compute.go b/mergebase/compute.go new file mode 100644 index 00000000..0fae0aed --- /dev/null +++ b/mergebase/compute.go @@ -0,0 +1,56 @@ +package mergebase + +import ( + "slices" + + "codeberg.org/lindenii/furgit/internal/commitquery" + "codeberg.org/lindenii/furgit/internal/peel" + "codeberg.org/lindenii/furgit/objectid" +) + +func (query *Bases) compute() ([]objectid.ObjectID, error) { + leftCommit, err := peel.ToCommit(query.store, query.left) + if err != nil { + return nil, err + } + + rightCommit, err := peel.ToCommit(query.store, query.right) + if err != nil { + return nil, err + } + + ctx := commitquery.NewContext(query.store, query.graph) + + leftIdx, err := ctx.ResolveOID(leftCommit) + if err != nil { + return nil, err + } + + rightIdx, err := ctx.ResolveOID(rightCommit) + if err != nil { + return nil, err + } + + candidates, err := commitquery.MergeBases(ctx, leftIdx, rightIdx) + if err != nil { + 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)) + } + }) + + out := make([]objectid.ObjectID, 0, len(candidates)) + for _, idx := range candidates { + out = append(out, ctx.ID(idx)) + } + + return out, nil +} diff --git a/mergebase/integration_test.go b/mergebase/integration_test.go new file mode 100644 index 00000000..07180159 --- /dev/null +++ b/mergebase/integration_test.go @@ -0,0 +1,308 @@ +package mergebase_test + +import ( + "maps" + "slices" + "strings" + "testing" + + "codeberg.org/lindenii/furgit/internal/testgit" + "codeberg.org/lindenii/furgit/mergebase" + "codeberg.org/lindenii/furgit/objectid" +) + +func TestQueryMatchesGitMergeBaseAll(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + testRepo := testgit.NewRepo(t, testgit.RepoOptions{ + ObjectFormat: algo, + Bare: true, + RefFormat: "files", + }) + + _, tree1 := testRepo.MakeSingleFileTree(t, "base.txt", []byte("base\n")) + base := testRepo.CommitTree(t, tree1, "base") + + _, tree2 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n")) + left := testRepo.CommitTree(t, tree2, "left", base) + + _, tree3 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n")) + right := testRepo.CommitTree(t, tree3, "right", base) + + tag := testRepo.TagAnnotated(t, "right-tag", right, "right-tag") + + store := testRepo.OpenObjectStore(t) + + query := mergebase.Query(store, nil, left, tag) + got := oidSetFromSeq(query.Seq()) + + err := query.Err() + if err != nil { + t.Fatalf("query.Err(): %v", err) + } + + 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 := mergebase.Query(store, nil, left, right) + got := oidSetFromSeq(query.Seq()) + + err := query.Err() + if err != nil { + t.Fatalf("query.Err(): %v", err) + } + + 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 := mergebase.Base(store, nil, 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 := mergebase.Query(store, graph, left, right) + got := oidSetFromSeq(query.Seq()) + + err := query.Err() + if err != nil { + t.Fatalf("query.Err(): %v", err) + } + + 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 := mergebase.Base(store, graph, 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) + + got, ok, err := mergebase.Base(store, nil, 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 = mergebase.Base(store, graph, 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) + } + }) +} + +// oidSetFromSeq collects one object ID sequence into a set. +func oidSetFromSeq(seq func(func(objectid.ObjectID) bool)) map[objectid.ObjectID]struct{} { + out := make(map[objectid.ObjectID]struct{}) + + seq(func(id objectid.ObjectID) bool { + out[id] = struct{}{} + + return true + }) + + 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/mergebase/mergebase.go b/mergebase/mergebase.go new file mode 100644 index 00000000..dc0bcf6c --- /dev/null +++ b/mergebase/mergebase.go @@ -0,0 +1,19 @@ +// Package mergebase computes best common ancestors between commits. +package mergebase + +import ( + commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore" +) + +// Bases is one iterator merge-base query. +type Bases struct { + store objectstore.Store + graph *commitgraphread.Reader + left objectid.ObjectID + right objectid.ObjectID + + seqUsed bool + err error +} diff --git a/mergebase/query.go b/mergebase/query.go new file mode 100644 index 00000000..e2c7e54f --- /dev/null +++ b/mergebase/query.go @@ -0,0 +1,24 @@ +package mergebase + +import ( + commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore" +) + +// Query builds one single-use 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/mergebase/seq.go b/mergebase/seq.go new file mode 100644 index 00000000..e7891737 --- /dev/null +++ b/mergebase/seq.go @@ -0,0 +1,47 @@ +package mergebase + +import ( + "errors" + "iter" + + "codeberg.org/lindenii/furgit/objectid" +) + +// Seq returns the merge-base sequence. It is single-use. +func (query *Bases) Seq() iter.Seq[objectid.ObjectID] { + if query.seqUsed { + return func(yield func(objectid.ObjectID) bool) { + _ = yield + + if query.err == nil { + query.err = errors.New("mergebase: sequence already consumed") + } + } + } + + query.seqUsed = true + + return func(yield func(objectid.ObjectID) bool) { + if query.err != nil { + return + } + + bases, err := query.compute() + if err != nil { + query.err = err + + return + } + + for _, id := range bases { + if !yield(id) { + return + } + } + } +} + +// Err returns the terminal error, if any, once Seq has been consumed. +func (query *Bases) Err() error { + return query.err +} diff --git a/mergebase/unit_test.go b/mergebase/unit_test.go new file mode 100644 index 00000000..55c7c9ae --- /dev/null +++ b/mergebase/unit_test.go @@ -0,0 +1,335 @@ +package mergebase_test + +import ( + "errors" + "fmt" + "maps" + "slices" + "testing" + + 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" + "codeberg.org/lindenii/furgit/objecttype" +) + +// commitBody serializes one minimal commit body. +func commitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte { + buf := fmt.Appendf(nil, "tree %s\n", tree.String()) + for _, parent := range parents { + buf = append(buf, fmt.Appendf(nil, "parent %s\n", parent.String())...) + } + + buf = append(buf, []byte("\nmsg\n")...) + + return buf +} + +// tagBody serializes one minimal annotated tag body. +func tagBody(target objectid.ObjectID, targetType objecttype.Type) []byte { + targetName, ok := objecttype.Name(targetType) + if !ok { + panic("invalid tag target type") + } + + return fmt.Appendf(nil, "object %s\ntype %s\ntag t\n\nmsg\n", target.String(), targetName) +} + +// collectSeq collects one object ID sequence into a slice. +func collectSeq(seq func(func(objectid.ObjectID) bool)) []objectid.ObjectID { + var out []objectid.ObjectID + + seq(func(id objectid.ObjectID) bool { + out = append(out, id) + + return true + }) + + return out +} + +// toSet converts one slice of object IDs into a set. +func toSet(ids []objectid.ObjectID) map[objectid.ObjectID]struct{} { + set := make(map[objectid.ObjectID]struct{}, len(ids)) + for _, id := range ids { + set[id] = struct{}{} + } + + return set +} + +// containsID reports whether one set contains one object ID. +func containsID(set map[objectid.ObjectID]struct{}, id objectid.ObjectID) bool { + _, ok := set[id] + + return ok +} + +// mustSerializeTree serializes one tree or fails the test. +func mustSerializeTree(tb testing.TB, tree *object.Tree) []byte { + tb.Helper() + + body, err := tree.SerializeWithoutHeader() + if err != nil { + tb.Fatalf("SerializeWithoutHeader: %v", err) + } + + return body +} + +// TestQueryLinearHistory reports one linear-history merge base. +func TestQueryLinearHistory(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("f"), + ID: blob, + }}})) + base := store.AddObject(objecttype.TypeCommit, commitBody(tree)) + left := store.AddObject(objecttype.TypeCommit, commitBody(tree, base)) + right := store.AddObject(objecttype.TypeCommit, commitBody(tree, left)) + + query := mergebase.Query(store, nil, left, right) + got := collectSeq(query.Seq()) + + err := query.Err() + if err != nil { + t.Fatalf("query.Err(): %v", err) + } + + if !slices.Equal(got, []objectid.ObjectID{left}) { + t.Fatalf("Query(left, right)=%v, want [%s]", got, left) + } + + first, ok, err := mergebase.Base(store, nil, left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if !ok { + t.Fatal("Base(left, right) unexpectedly reported no base") + } + + if first != left { + t.Fatalf("Base(left, right)=%s, want %s", first, left) + } + }) +} + +func TestQueryPeelsAnnotatedTags(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("left"), + ID: blob, + }}})) + rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("right"), + ID: blob, + }}})) + base := store.AddObject(objecttype.TypeCommit, commitBody(leftTree)) + left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree, base)) + right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree, base)) + tag := store.AddObject(objecttype.TypeTag, tagBody(right, objecttype.TypeCommit)) + + query := mergebase.Query(store, nil, left, tag) + got := collectSeq(query.Seq()) + + err := query.Err() + if err != nil { + t.Fatalf("query.Err(): %v", err) + } + + if !slices.Equal(got, []objectid.ObjectID{base}) { + t.Fatalf("Query(left, tag)=%v, want [%s]", got, base) + } + }) +} + +func TestQueryCrissCrossReturnsAllBestCommonAncestors(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + rootTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("root"), + ID: blob, + }}})) + base1Tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("base1"), + ID: blob, + }}})) + base2Tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("base2"), + ID: blob, + }}})) + leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("left"), + ID: blob, + }}})) + rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("right"), + ID: blob, + }}})) + root := store.AddObject(objecttype.TypeCommit, commitBody(rootTree)) + base1 := store.AddObject(objecttype.TypeCommit, commitBody(base1Tree, root)) + base2 := store.AddObject(objecttype.TypeCommit, commitBody(base2Tree, root)) + left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree, base1, base2)) + right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree, base2, base1)) + + query := mergebase.Query(store, nil, left, right) + got := toSet(collectSeq(query.Seq())) + + err := query.Err() + if err != nil { + t.Fatalf("query.Err(): %v", err) + } + + 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 := mergebase.Base(store, nil, left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if !ok { + t.Fatal("Base(left, right) unexpectedly reported no base") + } + + if !containsID(want, first) { + t.Fatalf("Base(left, right)=%s, want one of %v", first, slices.Collect(maps.Keys(want))) + } + }) +} + +func TestQueryReturnsNoResultWhenNoCommonAncestorExists(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + leftBlob := store.AddObject(objecttype.TypeBlob, []byte("left\n")) + leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("left"), + ID: leftBlob, + }}})) + rightBlob := store.AddObject(objecttype.TypeBlob, []byte("right\n")) + rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("right"), + ID: rightBlob, + }}})) + left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree)) + right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree)) + + query := mergebase.Query(store, nil, left, right) + got := collectSeq(query.Seq()) + + err := query.Err() + if err != nil { + t.Fatalf("query.Err(): %v", err) + } + + if len(got) != 0 { + t.Fatalf("Query(left, right)=%v, want no results", got) + } + + _, ok, err := mergebase.Base(store, nil, left, right) + if err != nil { + t.Fatalf("Base(left, right): %v", err) + } + + if ok { + t.Fatal("Base(left, right) unexpectedly reported a base") + } + }) +} + +func TestQueryRejectsNonCommitAfterPeel(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("f"), + ID: blob, + }}})) + commit := store.AddObject(objecttype.TypeCommit, commitBody(tree)) + tagToTree := store.AddObject(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree)) + + query := mergebase.Query(store, nil, commit, tagToTree) + _ = collectSeq(query.Seq()) + + err := query.Err() + 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) + } + + if typeErr.Got != objecttype.TypeTree || typeErr.Want != objecttype.TypeCommit { + t.Fatalf("unexpected type error: %+v", typeErr) + } + }) +} + +func TestQuerySeqSingleUse(t *testing.T) { + t.Parallel() + + testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper + store := memory.New(algo) + blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n")) + tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + Mode: object.FileModeRegular, + Name: []byte("f"), + ID: blob, + }}})) + base := store.AddObject(objecttype.TypeCommit, commitBody(tree)) + left := store.AddObject(objecttype.TypeCommit, commitBody(tree, base)) + right := store.AddObject(objecttype.TypeCommit, commitBody(tree, left)) + + query := mergebase.Query(store, nil, left, right) + + _ = collectSeq(query.Seq()) + again := collectSeq(query.Seq()) + + if len(again) != 0 { + t.Fatalf("second Seq() unexpectedly yielded %v", again) + } + + err := query.Err() + if err == nil { + t.Fatal("expected error after second Seq()") + } + + if err.Error() != "mergebase: sequence already consumed" { + t.Fatalf("unexpected error: %v", err) + } + }) +} diff --git a/objectid/objectid.go b/objectid/objectid.go index df56b2d8..1c169b29 100644 --- a/objectid/objectid.go +++ b/objectid/objectid.go @@ -4,6 +4,7 @@ package objectid import ( //#nosec G505 + "bytes" "encoding/hex" "fmt" ) @@ -52,6 +53,12 @@ func (id *ObjectID) RawBytes() []byte { return id.data[:size:size] } +// Compare lexicographically compares two object IDs by their canonical byte +// representation. +func Compare(left, right ObjectID) int { + return bytes.Compare(left.RawBytes(), right.RawBytes()) +} + // ParseHex parses an object ID from hex for the specified algorithm. func ParseHex(algo Algorithm, s string) (ObjectID, error) { var id ObjectID diff --git a/objectstore/loose/helpers_test.go b/objectstore/loose/helpers_test.go index 4b0bb60e..6cc50163 100644 --- a/objectstore/loose/helpers_test.go +++ b/objectstore/loose/helpers_test.go @@ -2,8 +2,6 @@ package loose_test import ( "io" - "os" - "path/filepath" "testing" "codeberg.org/lindenii/furgit/internal/testgit" @@ -13,17 +11,10 @@ import ( "codeberg.org/lindenii/furgit/objecttype" ) -func openLooseStore(t *testing.T, repoPath string, algo objectid.Algorithm) *loose.Store { +func openLooseStore(t *testing.T, testRepo *testgit.TestRepo, algo objectid.Algorithm) *loose.Store { t.Helper() - objectsPath := filepath.Join(repoPath, "objects") - - root, err := os.OpenRoot(objectsPath) - if err != nil { - t.Fatalf("OpenRoot(%q): %v", objectsPath, err) - } - - t.Cleanup(func() { _ = root.Close() }) + root := testRepo.OpenObjectsRoot(t) store, err := loose.New(root, algo) if err != nil { diff --git a/objectstore/loose/read_test.go b/objectstore/loose/read_test.go index 1efc1682..44e25910 100644 --- a/objectstore/loose/read_test.go +++ b/objectstore/loose/read_test.go @@ -21,7 +21,7 @@ func TestLooseStoreReadAgainstGit(t *testing.T) { _, treeID, commitID := testRepo.MakeCommit(t, "subject\n\nbody") tagID := testRepo.TagAnnotated(t, "v1", commitID, "tag message") - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) tests := []struct { name string @@ -108,7 +108,7 @@ func TestLooseStoreErrors(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}) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) notFoundID, err := objectid.ParseHex(algo, strings.Repeat("0", algo.HexLen())) if err != nil { diff --git a/objectstore/loose/write_test.go b/objectstore/loose/write_test.go index 5604c5b0..a7b12622 100644 --- a/objectstore/loose/write_test.go +++ b/objectstore/loose/write_test.go @@ -14,7 +14,7 @@ func TestLooseStoreWriteReaderContentAgainstGit(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}) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) content := []byte("written-by-content-reader\n") expectedHex := testRepo.RunInput(t, content, "hash-object", "-t", "blob", "--stdin") @@ -54,7 +54,7 @@ func TestLooseStoreWriteReaderFullAgainstGit(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}) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) body := []byte("full-reader-body\n") @@ -91,7 +91,7 @@ func TestLooseStoreReaderValidationErrors(t *testing.T) { t.Run("content overflow", func(t *testing.T) { t.Parallel() testRepo := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) _, err := store.WriteReaderContent(objecttype.TypeBlob, 1, bytes.NewReader([]byte("hello"))) if err == nil { @@ -102,7 +102,7 @@ func TestLooseStoreReaderValidationErrors(t *testing.T) { t.Run("content short", func(t *testing.T) { t.Parallel() testRepo := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) _, err := store.WriteReaderContent(objecttype.TypeBlob, 5, bytes.NewReader([]byte("x"))) if err == nil { @@ -113,7 +113,7 @@ func TestLooseStoreReaderValidationErrors(t *testing.T) { t.Run("full malformed header", func(t *testing.T) { t.Parallel() testRepo := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) _, err := store.WriteReaderFull(bytes.NewReader([]byte("not-a-header"))) if err == nil { @@ -124,7 +124,7 @@ func TestLooseStoreReaderValidationErrors(t *testing.T) { t.Run("full size mismatch", func(t *testing.T) { t.Parallel() testRepo := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) raw := []byte("blob 1\x00hello") diff --git a/objectstore/memory/add.go b/objectstore/memory/add.go new file mode 100644 index 00000000..80d0022f --- /dev/null +++ b/objectstore/memory/add.go @@ -0,0 +1,21 @@ +package memory + +import ( + "codeberg.org/lindenii/furgit/objectheader" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objecttype" +) + +// AddObject stores one object body and returns its object ID. +func (store *Store) AddObject(ty objecttype.Type, body []byte) objectid.ObjectID { + header, ok := objectheader.Encode(ty, int64(len(body))) + if !ok { + panic("failed to encode object header") + } + + raw := append(append([]byte(nil), header...), body...) + id := store.algo.Sum(raw) + store.objects[id] = storedObject{ty: ty, content: append([]byte(nil), body...)} + + return id +} diff --git a/objectstore/memory/algorithm.go b/objectstore/memory/algorithm.go new file mode 100644 index 00000000..db43272e --- /dev/null +++ b/objectstore/memory/algorithm.go @@ -0,0 +1,8 @@ +package memory + +import "codeberg.org/lindenii/furgit/objectid" + +// Algorithm returns the object ID algorithm used by the store. +func (store *Store) Algorithm() objectid.Algorithm { + return store.algo +} diff --git a/objectstore/memory/doc.go b/objectstore/memory/doc.go new file mode 100644 index 00000000..cb40d466 --- /dev/null +++ b/objectstore/memory/doc.go @@ -0,0 +1,2 @@ +// Package memory provides one in-memory object store. +package memory diff --git a/objectstore/memory/object.go b/objectstore/memory/object.go new file mode 100644 index 00000000..940af328 --- /dev/null +++ b/objectstore/memory/object.go @@ -0,0 +1,9 @@ +package memory + +import "codeberg.org/lindenii/furgit/objecttype" + +// storedObject is one in-memory object entry. +type storedObject struct { + ty objecttype.Type + content []byte +} diff --git a/objectstore/memory/read_bytes.go b/objectstore/memory/read_bytes.go new file mode 100644 index 00000000..31c5b3d1 --- /dev/null +++ b/objectstore/memory/read_bytes.go @@ -0,0 +1,37 @@ +package memory + +import ( + "codeberg.org/lindenii/furgit/objectheader" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore" + "codeberg.org/lindenii/furgit/objecttype" +) + +// ReadBytesFull reads one full object, including the object header. +func (store *Store) ReadBytesFull(id objectid.ObjectID) ([]byte, error) { + obj, ok := store.objects[id] + if !ok { + return nil, objectstore.ErrObjectNotFound + } + + header, ok := objectheader.Encode(obj.ty, int64(len(obj.content))) + if !ok { + panic("failed to encode object header") + } + + raw := make([]byte, len(header)+len(obj.content)) + copy(raw, header) + copy(raw[len(header):], obj.content) + + return raw, nil +} + +// ReadBytesContent reads one object body. +func (store *Store) ReadBytesContent(id objectid.ObjectID) (objecttype.Type, []byte, error) { + obj, ok := store.objects[id] + if !ok { + return objecttype.TypeInvalid, nil, objectstore.ErrObjectNotFound + } + + return obj.ty, append([]byte(nil), obj.content...), nil +} diff --git a/objectstore/memory/read_header.go b/objectstore/memory/read_header.go new file mode 100644 index 00000000..1d0aff15 --- /dev/null +++ b/objectstore/memory/read_header.go @@ -0,0 +1,17 @@ +package memory + +import ( + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore" + "codeberg.org/lindenii/furgit/objecttype" +) + +// ReadHeader reads one object header. +func (store *Store) ReadHeader(id objectid.ObjectID) (objecttype.Type, int64, error) { + obj, ok := store.objects[id] + if !ok { + return objecttype.TypeInvalid, 0, objectstore.ErrObjectNotFound + } + + return obj.ty, int64(len(obj.content)), nil +} diff --git a/objectstore/memory/read_reader.go b/objectstore/memory/read_reader.go new file mode 100644 index 00000000..2e3feda1 --- /dev/null +++ b/objectstore/memory/read_reader.go @@ -0,0 +1,29 @@ +package memory + +import ( + "bytes" + "io" + + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objecttype" +) + +// ReadReaderFull reads one full object through a reader. +func (store *Store) ReadReaderFull(id objectid.ObjectID) (io.ReadCloser, error) { + raw, err := store.ReadBytesFull(id) + if err != nil { + return nil, err + } + + return io.NopCloser(bytes.NewReader(raw)), nil +} + +// ReadReaderContent reads one object body through a reader. +func (store *Store) ReadReaderContent(id objectid.ObjectID) (objecttype.Type, int64, io.ReadCloser, error) { + ty, content, err := store.ReadBytesContent(id) + if err != nil { + return objecttype.TypeInvalid, 0, nil, err + } + + return ty, int64(len(content)), io.NopCloser(bytes.NewReader(content)), nil +} diff --git a/objectstore/memory/read_size.go b/objectstore/memory/read_size.go new file mode 100644 index 00000000..3ca7789a --- /dev/null +++ b/objectstore/memory/read_size.go @@ -0,0 +1,13 @@ +package memory + +import "codeberg.org/lindenii/furgit/objectid" + +// ReadSize reads one object size. +func (store *Store) ReadSize(id objectid.ObjectID) (int64, error) { + _, size, err := store.ReadHeader(id) + if err != nil { + return 0, err + } + + return size, nil +} diff --git a/objectstore/memory/store.go b/objectstore/memory/store.go new file mode 100644 index 00000000..f7513094 --- /dev/null +++ b/objectstore/memory/store.go @@ -0,0 +1,24 @@ +package memory + +import ( + "codeberg.org/lindenii/furgit/objectid" +) + +// Store is one in-memory object store. +type Store struct { + algo objectid.Algorithm + objects map[objectid.ObjectID]storedObject +} + +// New builds one empty in-memory store for one object format. +func New(algo objectid.Algorithm) *Store { + return &Store{ + algo: algo, + objects: make(map[objectid.ObjectID]storedObject), + } +} + +// Close closes the in-memory store. +func (store *Store) Close() error { + return nil +} diff --git a/objectstore/objectstore.go b/objectstore/objectstore.go index 58b091ef..a68175ac 100644 --- a/objectstore/objectstore.go +++ b/objectstore/objectstore.go @@ -11,6 +11,7 @@ import ( // ErrObjectNotFound indicates that an object does not exist in a backend. // TODO: This might need to be an interface or otherwise be able to encapsulate multiple concrete backends'. +// XXX: Don't remove this in favor of errors.ObjectMissingError yet due to pressure of allocation large error structs. var ErrObjectNotFound = errors.New("objectstore: object not found") // Store reads Git objects by object ID. diff --git a/objectstore/packed/helpers_test.go b/objectstore/packed/helpers_test.go index 1b517294..581c0dd7 100644 --- a/objectstore/packed/helpers_test.go +++ b/objectstore/packed/helpers_test.go @@ -3,8 +3,6 @@ package packed_test import ( "fmt" "io" - "os" - "path/filepath" "strconv" "strings" "testing" @@ -16,17 +14,10 @@ import ( "codeberg.org/lindenii/furgit/objecttype" ) -func openPackedStore(t *testing.T, repoPath string, algo objectid.Algorithm) *packed.Store { +func openPackedStore(t *testing.T, testRepo *testgit.TestRepo, algo objectid.Algorithm) *packed.Store { t.Helper() - packPath := filepath.Join(repoPath, "objects", "pack") - - root, err := os.OpenRoot(packPath) - if err != nil { - t.Fatalf("OpenRoot(%q): %v", packPath, err) - } - - t.Cleanup(func() { _ = root.Close() }) + root := testRepo.OpenPackRoot(t) store, err := packed.New(root, algo) if err != nil { diff --git a/objectstore/packed/read_test.go b/objectstore/packed/read_test.go index 02ef4e75..435bc350 100644 --- a/objectstore/packed/read_test.go +++ b/objectstore/packed/read_test.go @@ -4,8 +4,7 @@ import ( "bytes" "errors" "fmt" - "os" - "path/filepath" + "io/fs" "strconv" "strings" "testing" @@ -20,7 +19,7 @@ func TestPackedStoreReadAgainstGit(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper testRepo, ids := createPackedFixtureRepo(t, algo) - store := openPackedStore(t, testRepo.Dir(), algo) + store := openPackedStore(t, testRepo, algo) for _, id := range ids { t.Run(id.String(), func(t *testing.T) { @@ -106,7 +105,7 @@ func TestPackedStoreErrors(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper testRepo, _ := createPackedFixtureRepo(t, algo) - store := openPackedStore(t, testRepo.Dir(), algo) + store := openPackedStore(t, testRepo, algo) notFoundID, err := objectid.ParseHex(algo, strings.Repeat("0", algo.HexLen())) if err != nil { @@ -172,7 +171,7 @@ func TestPackedStoreNewValidation(t *testing.T) { testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper testRepo, _ := createPackedFixtureRepo(t, algo) - store := openPackedStore(t, testRepo.Dir(), algo) + store := openPackedStore(t, testRepo, algo) err := store.Close() if err != nil { @@ -190,14 +189,9 @@ func TestPackedStoreInvalidAlgorithm(t *testing.T) { t.Parallel() testRepo := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: objectid.AlgorithmSHA1, Bare: true}) - root, err := os.OpenRoot(testRepo.Dir()) - if err != nil { - t.Fatalf("OpenRoot(%q): %v", testRepo.Dir(), err) - } - - t.Cleanup(func() { _ = root.Close() }) + root := testRepo.OpenPackRoot(t) - _, err = packed.New(root, objectid.AlgorithmUnknown) + _, err := packed.New(root, objectid.AlgorithmUnknown) if !errors.Is(err, objectid.ErrInvalidAlgorithm) { t.Fatalf("packed.New invalid algorithm error = %v", err) } @@ -227,7 +221,7 @@ func TestPackedStoreReadHeaderUsesResolvedObjectSizeForDelta(t *testing.T) { testRepo.Repack(t, "-a", "-d", "-f", "--window=128", "--depth=128") deltaID, wantResolvedSize := findDeltaObjectWithResolvedSizeMismatch(t, testRepo, algo) - store := openPackedStore(t, testRepo.Dir(), algo) + store := openPackedStore(t, testRepo, algo) _, gotSize, err := store.ReadHeader(deltaID) if err != nil { @@ -252,16 +246,28 @@ func TestPackedStoreReadHeaderUsesResolvedObjectSizeForDelta(t *testing.T) { func findDeltaObjectWithResolvedSizeMismatch(t *testing.T, testRepo *testgit.TestRepo, algo objectid.Algorithm) (objectid.ObjectID, int64) { t.Helper() - idxFiles, err := filepath.Glob(filepath.Join(testRepo.Dir(), "objects", "pack", "*.idx")) + packRoot := testRepo.OpenPackRoot(t) + + entries, err := fs.ReadDir(packRoot.FS(), ".") if err != nil { - t.Fatalf("Glob idx: %v", err) + t.Fatalf("ReadDir(pack): %v", err) + } + + var idxName string + + for _, entry := range entries { + if strings.HasSuffix(entry.Name(), ".idx") { + idxName = entry.Name() + + break + } } - if len(idxFiles) == 0 { + if idxName == "" { t.Fatalf("no idx files found") } - verifyOut := testRepo.Run(t, "verify-pack", "-v", idxFiles[0]) + verifyOut := testRepo.Run(t, "verify-pack", "-v", "objects/pack/"+idxName) for line := range strings.SplitSeq(strings.TrimSpace(verifyOut), "\n") { fields := strings.Fields(line) if len(fields) < 7 { diff --git a/reachability/ancestor.go b/reachability/ancestor.go deleted file mode 100644 index 584ec0e3..00000000 --- a/reachability/ancestor.go +++ /dev/null @@ -1,122 +0,0 @@ -package reachability - -import ( - "errors" - - commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read" - "codeberg.org/lindenii/furgit/objectid" -) - -// IsAncestor reports whether ancestor is reachable from descendant via commit -// parent edges. -// -// Both inputs are peeled through annotated tags before commit traversal. -func (r *Reachability) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, error) { - ancestorCommit, err := r.peelRootToCommit(ancestor) - if err != nil { - return false, err - } - - descendantCommit, err := r.peelRootToCommit(descendant) - if err != nil { - return false, err - } - - if ancestorCommit == descendantCommit { - return true, nil - } - - graphResult, graphUsed, err := r.isAncestorGraph(ancestorCommit, descendantCommit) - if err != nil { - return false, err - } - - if graphUsed { - return graphResult, nil - } - - walk := r.Walk(DomainCommits, nil, map[objectid.ObjectID]struct{}{descendantCommit: {}}) - for id := range walk.Seq() { - if id == ancestorCommit { - return true, nil - } - } - - err = walk.Err() - if err != nil { - return false, err - } - - return false, nil -} - -func (r *Reachability) isAncestorGraph(ancestor, descendant objectid.ObjectID) (bool, bool, error) { - if r.graph == nil { - return false, false, nil - } - - ancestorPos, err := r.graph.Lookup(ancestor) - if err != nil { - var notFound *commitgraphread.NotFoundError - if errors.As(err, ¬Found) { - return false, false, nil - } - - return false, true, err - } - - descendantPos, err := r.graph.Lookup(descendant) - if err != nil { - var notFound *commitgraphread.NotFoundError - if errors.As(err, ¬Found) { - return false, false, nil - } - - return false, true, err - } - - ancestorCommit, err := r.graph.CommitAt(ancestorPos) - if err != nil { - return false, true, err - } - - ancestorGeneration := ancestorCommit.GenerationV2 - stack := []commitgraphread.Position{descendantPos} - visited := make(map[commitgraphread.Position]struct{}, 64) - - for len(stack) > 0 { - pos := stack[len(stack)-1] - stack = stack[:len(stack)-1] - - if _, ok := visited[pos]; ok { - continue - } - - visited[pos] = struct{}{} - - if pos == ancestorPos { - return true, true, nil - } - - commit, err := r.graph.CommitAt(pos) - if err != nil { - return false, true, err - } - - if commit.GenerationV2 < ancestorGeneration { - continue - } - - if commit.Parent1.Valid { - stack = append(stack, commit.Parent1.Pos) - } - - if commit.Parent2.Valid { - stack = append(stack, commit.Parent2.Pos) - } - - stack = append(stack, commit.ExtraParents...) - } - - return false, true, nil -} diff --git a/reachability/errors.go b/reachability/errors.go deleted file mode 100644 index 0f0c6047..00000000 --- a/reachability/errors.go +++ /dev/null @@ -1,39 +0,0 @@ -package reachability - -import ( - "fmt" - - "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/objecttype" -) - -// ObjectMissingError indicates that a referenced object is absent from the store. -type ObjectMissingError struct { - OID objectid.ObjectID -} - -func (e *ObjectMissingError) Error() string { - return fmt.Sprintf("reachability: missing object %s", e.OID) -} - -// ObjectTypeError indicates that a referenced object has a different type than -// what traversal expected on that edge. -type ObjectTypeError struct { - OID objectid.ObjectID - Got objecttype.Type - Want objecttype.Type -} - -func (e *ObjectTypeError) Error() string { - gotName, gotOK := objecttype.Name(e.Got) - if !gotOK { - gotName = fmt.Sprintf("type(%d)", e.Got) - } - - wantName, wantOK := objecttype.Name(e.Want) - if !wantOK { - wantName = fmt.Sprintf("type(%d)", e.Want) - } - - return fmt.Sprintf("reachability: object %s has type %s, want %s", e.OID, gotName, wantName) -} diff --git a/reachability/helpers.go b/reachability/helpers.go index 9fdc99d8..02c3c726 100644 --- a/reachability/helpers.go +++ b/reachability/helpers.go @@ -4,6 +4,7 @@ import ( "errors" "fmt" + giterrors "codeberg.org/lindenii/furgit/errors" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objectstore" "codeberg.org/lindenii/furgit/objecttype" @@ -39,7 +40,7 @@ func (r *Reachability) readHeaderType(id objectid.ObjectID) (objecttype.Type, er ty, _, err := r.store.ReadHeader(id) if err != nil { if errors.Is(err, objectstore.ErrObjectNotFound) { - return objecttype.TypeInvalid, &ObjectMissingError{OID: id} + return objecttype.TypeInvalid, &giterrors.ObjectMissingError{OID: id} } return objecttype.TypeInvalid, err @@ -61,7 +62,7 @@ func (r *Reachability) readBytesContent(id objectid.ObjectID) ([]byte, error) { _, content, err := r.store.ReadBytesContent(id) if err != nil { if errors.Is(err, objectstore.ErrObjectNotFound) { - return nil, &ObjectMissingError{OID: id} + return nil, &giterrors.ObjectMissingError{OID: id} } return nil, err diff --git a/reachability/integration_test.go b/reachability/integration_test.go index c7c5c63d..6b043d92 100644 --- a/reachability/integration_test.go +++ b/reachability/integration_test.go @@ -3,17 +3,16 @@ package reachability_test import ( "errors" "fmt" + "io/fs" "maps" - "os" - "path/filepath" "slices" "strings" "testing" + giterrors "codeberg.org/lindenii/furgit/errors" "codeberg.org/lindenii/furgit/internal/testgit" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/reachability" - "codeberg.org/lindenii/furgit/repository" ) func TestWalkCommitsMatchesGitRevList(t *testing.T) { @@ -163,51 +162,6 @@ func TestWalkObjectsMatchesGitRevListObjects(t *testing.T) { }) } -func TestIsAncestorMatchesGitMergeBase(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") - - r := openReachabilityFromTestRepo(t, testRepo) - - got, err := r.IsAncestor(c1, tag) - if err != nil { - t.Fatalf("IsAncestor(c1, tag): %v", err) - } - - want := gitMergeBaseIsAncestor(t, testRepo, c1, c2) - if got != want { - t.Fatalf("IsAncestor(c1, tag)=%v, want %v", got, want) - } - - got, err = r.IsAncestor(c3, c2) - if err != nil { - t.Fatalf("IsAncestor(c3, c2): %v", err) - } - - want = gitMergeBaseIsAncestor(t, testRepo, c3, c2) - if got != want { - t.Fatalf("IsAncestor(c3, c2)=%v, want %v", got, want) - } - }) -} - func TestCheckConnectedMissingObject(t *testing.T) { t.Parallel() @@ -220,14 +174,11 @@ func TestCheckConnectedMissingObject(t *testing.T) { _, treeID, commitID := testRepo.MakeCommit(t, "missing") - err := os.Remove(looseObjectPath(testRepo.Dir(), treeID)) - if err != nil { - t.Fatalf("remove tree object: %v", err) - } + testRepo.RemoveLooseObject(t, treeID) r := openReachabilityFromTestRepo(t, testRepo) - err = r.CheckConnected( + err := r.CheckConnected( reachability.DomainObjects, nil, map[objectid.ObjectID]struct{}{commitID: {}}, @@ -236,7 +187,7 @@ func TestCheckConnectedMissingObject(t *testing.T) { t.Fatal("expected error") } - var missing *reachability.ObjectMissingError + var missing *giterrors.ObjectMissingError if !errors.As(err, &missing) { t.Fatalf("expected ObjectMissingError, got %T (%v)", err, err) } @@ -267,7 +218,7 @@ func TestWalkOnPackedOnlyRepo(t *testing.T) { testRepo.Repack(t, "-ad") testRepo.Run(t, "prune-packed") - assertPackedOnly(t, testRepo.Dir()) + assertPackedOnly(t, testRepo) r := openReachabilityFromTestRepo(t, testRepo) walk := r.Walk( @@ -298,21 +249,7 @@ func TestWalkOnPackedOnlyRepo(t *testing.T) { func openReachabilityFromTestRepo(t *testing.T, testRepo *testgit.TestRepo) *reachability.Reachability { t.Helper() - root, err := os.OpenRoot(testRepo.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - t.Cleanup(func() { _ = root.Close() }) - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - t.Cleanup(func() { _ = repo.Close() }) - - return reachability.New(repo.Objects()) + return reachability.New(testRepo.OpenObjectStore(t)) } func oidSetFromSeq(seq func(func(objectid.ObjectID) bool)) map[objectid.ObjectID]struct{} { @@ -379,14 +316,6 @@ func gitRevListSet( return set } -func gitMergeBaseIsAncestor(t *testing.T, testRepo *testgit.TestRepo, a, b objectid.ObjectID) bool { - t.Helper() - // testgit.Run fatals on non-zero status, so we compare merge-base output. - mb := testRepo.Run(t, "merge-base", a.String(), b.String()) - - return mb == a.String() -} - func sortedOIDStrings(set map[objectid.ObjectID]struct{}) []string { out := make([]string, 0, len(set)) for id := range set { @@ -398,18 +327,12 @@ func sortedOIDStrings(set map[objectid.ObjectID]struct{}) []string { return out } -func looseObjectPath(repoDir string, id objectid.ObjectID) string { - hex := id.String() - - return filepath.Join(repoDir, "objects", hex[:2], hex[2:]) -} - -func assertPackedOnly(t *testing.T, repoDir string) { +func assertPackedOnly(t *testing.T, testRepo *testgit.TestRepo) { t.Helper() - objectsDir := filepath.Join(repoDir, "objects") + objectsRoot := testRepo.OpenObjectsRoot(t) - entries, err := os.ReadDir(objectsDir) + entries, err := fs.ReadDir(objectsRoot.FS(), ".") if err != nil { t.Fatalf("ReadDir(objects): %v", err) } @@ -421,13 +344,13 @@ func assertPackedOnly(t *testing.T, repoDir string) { } if len(name) == 2 && isHexDirName(name) { - subEntries, err := os.ReadDir(filepath.Join(objectsDir, name)) + subEntries, err := fs.ReadDir(objectsRoot.FS(), name) if err != nil { t.Fatalf("ReadDir(objects/%s): %v", name, err) } if len(subEntries) != 0 { - t.Fatalf("found loose objects in %s", filepath.Join(objectsDir, name)) + t.Fatalf("found loose objects in objects/%s", name) } } } diff --git a/reachability/peel.go b/reachability/peel.go deleted file mode 100644 index 5f24982e..00000000 --- a/reachability/peel.go +++ /dev/null @@ -1,37 +0,0 @@ -package reachability - -import ( - "codeberg.org/lindenii/furgit/object" - "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/objecttype" -) - -// peelRootToCommit peels annotated tags transitively until a commit is reached. -func (r *Reachability) peelRootToCommit(id objectid.ObjectID) (objectid.ObjectID, error) { - for { - ty, err := r.readHeaderType(id) - if err != nil { - return objectid.ObjectID{}, err - } - - if ty != objecttype.TypeTag { - if ty != objecttype.TypeCommit { - return objectid.ObjectID{}, &ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit} - } - - return id, nil - } - - content, err := r.readBytesContent(id) - if err != nil { - return objectid.ObjectID{}, err - } - - tag, err := object.ParseTag(content, id.Algorithm()) - if err != nil { - return objectid.ObjectID{}, err - } - - id = tag.Target - } -} diff --git a/reachability/unit_test.go b/reachability/unit_test.go index 2fef2b48..dea6d38b 100644 --- a/reachability/unit_test.go +++ b/reachability/unit_test.go @@ -1,109 +1,40 @@ package reachability_test import ( - "bytes" "errors" "fmt" - "io" "maps" "slices" "testing" + giterrors "codeberg.org/lindenii/furgit/errors" "codeberg.org/lindenii/furgit/internal/testgit" "codeberg.org/lindenii/furgit/object" - "codeberg.org/lindenii/furgit/objectheader" "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/objectstore" + "codeberg.org/lindenii/furgit/objectstore/memory" "codeberg.org/lindenii/furgit/objecttype" "codeberg.org/lindenii/furgit/reachability" ) -type storeObject struct { - ty objecttype.Type - content []byte -} - type memStore struct { - algo objectid.Algorithm - objects map[objectid.ObjectID]storeObject + *memory.Store + readBytesByObjectID map[objectid.ObjectID]int } -func newMemStore(algo objectid.Algorithm) *memStore { +// newCountingMemStore builds one in-memory store that records content-read +// counts by object ID. +func newCountingMemStore(algo objectid.Algorithm) *memStore { return &memStore{ - algo: algo, - objects: make(map[objectid.ObjectID]storeObject), + Store: memory.New(algo), readBytesByObjectID: make(map[objectid.ObjectID]int), } } -func (store *memStore) ReadBytesFull(id objectid.ObjectID) ([]byte, error) { - obj, ok := store.objects[id] - if !ok { - return nil, objectstore.ErrObjectNotFound - } - - header, ok := objectheader.Encode(obj.ty, int64(len(obj.content))) - if !ok { - panic("failed to encode object header") - } - - raw := make([]byte, len(header)+len(obj.content)) - copy(raw, header) - copy(raw[len(header):], obj.content) - - return raw, nil -} - func (store *memStore) ReadBytesContent(id objectid.ObjectID) (objecttype.Type, []byte, error) { - obj, ok := store.objects[id] - if !ok { - return objecttype.TypeInvalid, nil, objectstore.ErrObjectNotFound - } - store.readBytesByObjectID[id]++ - return obj.ty, append([]byte(nil), obj.content...), nil -} - -func (store *memStore) ReadReaderFull(id objectid.ObjectID) (io.ReadCloser, error) { - raw, err := store.ReadBytesFull(id) - if err != nil { - return nil, err - } - - return io.NopCloser(bytes.NewReader(raw)), nil -} - -func (store *memStore) ReadReaderContent(id objectid.ObjectID) (objecttype.Type, int64, io.ReadCloser, error) { - ty, content, err := store.ReadBytesContent(id) - if err != nil { - return objecttype.TypeInvalid, 0, nil, err - } - - return ty, int64(len(content)), io.NopCloser(bytes.NewReader(content)), nil -} - -func (store *memStore) ReadSize(id objectid.ObjectID) (int64, error) { - _, size, err := store.ReadHeader(id) - if err != nil { - return 0, err - } - - return size, nil -} - -func (store *memStore) ReadHeader(id objectid.ObjectID) (objecttype.Type, int64, error) { - obj, ok := store.objects[id] - if !ok { - return objecttype.TypeInvalid, 0, objectstore.ErrObjectNotFound - } - - return obj.ty, int64(len(obj.content)), nil -} - -func (store *memStore) Close() error { - return nil + return store.Store.ReadBytesContent(id) } func commitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte { @@ -151,17 +82,17 @@ func TestWalkDomainCommitsIncludesTagNodes(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - store := newMemStore(algo) - blob := store.addObject(objecttype.TypeBlob, []byte("blob\n")) - tree := store.addObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + store := newCountingMemStore(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, }}})) - commit1 := store.addObject(objecttype.TypeCommit, commitBody(tree)) - commit2 := store.addObject(objecttype.TypeCommit, commitBody(tree, commit1)) - tag1 := store.addObject(objecttype.TypeTag, tagBody(commit2, objecttype.TypeCommit)) - tag2 := store.addObject(objecttype.TypeTag, tagBody(tag1, objecttype.TypeTag)) + commit1 := store.AddObject(objecttype.TypeCommit, commitBody(tree)) + commit2 := store.AddObject(objecttype.TypeCommit, commitBody(tree, commit1)) + tag1 := store.AddObject(objecttype.TypeTag, tagBody(commit2, objecttype.TypeCommit)) + tag2 := store.AddObject(objecttype.TypeTag, tagBody(tag1, objecttype.TypeTag)) r := reachability.New(store) walk := r.Walk(reachability.DomainCommits, nil, map[objectid.ObjectID]struct{}{tag2: {}}) @@ -186,14 +117,14 @@ func TestWalkExcludesHavesCompletely(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - store := newMemStore(algo) - blob := store.addObject(objecttype.TypeBlob, []byte("blob\n")) - tree := store.addObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + store := newCountingMemStore(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)) + commit := store.AddObject(objecttype.TypeCommit, commitBody(tree)) r := reachability.New(store) walk := r.Walk(reachability.DomainCommits, map[objectid.ObjectID]struct{}{commit: {}}, map[objectid.ObjectID]struct{}{commit: {}}) @@ -215,14 +146,14 @@ func TestWalkDomainCommitsRejectsNonCommitRootAfterPeel(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - store := newMemStore(algo) - blob := store.addObject(objecttype.TypeBlob, []byte("blob\n")) - tree := store.addObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + store := newCountingMemStore(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, }}})) - tag := store.addObject(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree)) + tag := store.AddObject(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree)) r := reachability.New(store) walk := r.Walk(reachability.DomainCommits, nil, map[objectid.ObjectID]struct{}{tag: {}}) @@ -233,7 +164,7 @@ func TestWalkDomainCommitsRejectsNonCommitRootAfterPeel(t *testing.T) { t.Fatal("expected error") } - var typeErr *reachability.ObjectTypeError + var typeErr *giterrors.ObjectTypeError if !errors.As(err, &typeErr) { t.Fatalf("expected ObjectTypeError, got %T (%v)", err, err) } @@ -248,17 +179,17 @@ func TestWalkDomainCommitsHaveTagStopsTraversal(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - store := newMemStore(algo) - blob := store.addObject(objecttype.TypeBlob, []byte("blob\n")) - tree := store.addObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + store := newCountingMemStore(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, }}})) - commit1 := store.addObject(objecttype.TypeCommit, commitBody(tree)) - commit2 := store.addObject(objecttype.TypeCommit, commitBody(tree, commit1)) - tag1 := store.addObject(objecttype.TypeTag, tagBody(commit2, objecttype.TypeCommit)) - tag2 := store.addObject(objecttype.TypeTag, tagBody(tag1, objecttype.TypeTag)) + commit1 := store.AddObject(objecttype.TypeCommit, commitBody(tree)) + commit2 := store.AddObject(objecttype.TypeCommit, commitBody(tree, commit1)) + tag1 := store.AddObject(objecttype.TypeTag, tagBody(commit2, objecttype.TypeCommit)) + tag2 := store.AddObject(objecttype.TypeTag, tagBody(tag1, objecttype.TypeTag)) r := reachability.New(store) walk := r.Walk( @@ -287,23 +218,23 @@ func TestWalkDomainObjectsRecursesTreesAndSkipsBlobContentReads(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - store := newMemStore(algo) + store := newCountingMemStore(algo) - blob1 := store.addObject(objecttype.TypeBlob, []byte("b1\n")) - blob2 := store.addObject(objecttype.TypeBlob, []byte("b2\n")) - gitlinkTarget := store.algo.Sum([]byte("external-submodule")) + blob1 := store.AddObject(objecttype.TypeBlob, []byte("b1\n")) + blob2 := store.AddObject(objecttype.TypeBlob, []byte("b2\n")) + gitlinkTarget := store.Algorithm().Sum([]byte("external-submodule")) - subtree := store.addObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + subtree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ Mode: object.FileModeRegular, Name: []byte("nested"), ID: blob2, }}})) - rootTree := store.addObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{ + rootTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{ {Mode: object.FileModeRegular, Name: []byte("a"), ID: blob1}, {Mode: object.FileModeDir, Name: []byte("dir"), ID: subtree}, {Mode: object.FileModeGitlink, Name: []byte("submodule"), ID: gitlinkTarget}, }})) - commit := store.addObject(objecttype.TypeCommit, commitBody(rootTree)) + commit := store.AddObject(objecttype.TypeCommit, commitBody(rootTree)) r := reachability.New(store) walk := r.Walk(reachability.DomainObjects, nil, map[objectid.ObjectID]struct{}{commit: {}}) @@ -332,15 +263,15 @@ func TestCheckConnectedReturnsConcreteMissingObject(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - store := newMemStore(algo) - blob := store.addObject(objecttype.TypeBlob, []byte("blob\n")) - tree := store.addObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{ + store := newCountingMemStore(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, }}})) - missingParent := store.algo.Sum([]byte("missing-parent")) - commit := store.addObject(objecttype.TypeCommit, commitBody(tree, missingParent)) + missingParent := store.Algorithm().Sum([]byte("missing-parent")) + commit := store.AddObject(objecttype.TypeCommit, commitBody(tree, missingParent)) r := reachability.New(store) @@ -349,7 +280,7 @@ func TestCheckConnectedReturnsConcreteMissingObject(t *testing.T) { t.Fatal("expected error") } - var missing *reachability.ObjectMissingError + var missing *giterrors.ObjectMissingError if !errors.As(err, &missing) { t.Fatalf("expected ObjectMissingError, got %T (%v)", err, err) } @@ -364,7 +295,7 @@ func TestWalkInvalidDomainReturnsPlainError(t *testing.T) { t.Parallel() testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - r := reachability.New(newMemStore(algo)) + r := reachability.New(newCountingMemStore(algo)) walk := r.Walk(reachability.Domain(99), nil, nil) _ = collectSeq(walk.Seq()) @@ -376,78 +307,6 @@ func TestWalkInvalidDomainReturnsPlainError(t *testing.T) { }) } -func TestIsAncestor(t *testing.T) { - t.Parallel() - - testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - store := newMemStore(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)) - - r := reachability.New(store) - - ok, err := r.IsAncestor(c1, tag) - if err != nil { - t.Fatalf("IsAncestor(c1, tag): %v", err) - } - - if !ok { - t.Fatal("expected c1 to be ancestor of tag->c2") - } - - ok, err = r.IsAncestor(c3, c2) - if err != nil { - t.Fatalf("IsAncestor(c3, c2): %v", err) - } - - if ok { - t.Fatal("did not expect c3 to be ancestor of c2") - } - }) -} - -func TestIsAncestorRejectsNonCommitAfterPeel(t *testing.T) { - t.Parallel() - - testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper - store := newMemStore(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)) - - r := reachability.New(store) - - _, err := r.IsAncestor(commit, tagToTree) - if err == nil { - t.Fatal("expected error") - } - - var typeErr *reachability.ObjectTypeError - if !errors.As(err, &typeErr) { - t.Fatalf("expected ObjectTypeError, got %T (%v)", err, err) - } - }) -} - func mustSerializeTree(tb testing.TB, tree *object.Tree) []byte { tb.Helper() @@ -458,16 +317,3 @@ func mustSerializeTree(tb testing.TB, tree *object.Tree) []byte { return body } - -func (store *memStore) addObject(ty objecttype.Type, body []byte) objectid.ObjectID { - header, ok := objectheader.Encode(ty, int64(len(body))) - if !ok { - panic("failed to encode object header") - } - - raw := append(append([]byte(nil), header...), body...) - id := store.algo.Sum(raw) - store.objects[id] = storeObject{ty: ty, content: append([]byte(nil), body...)} - - return id -} diff --git a/reachability/walk.go b/reachability/walk.go index e6de8684..dc2f32fd 100644 --- a/reachability/walk.go +++ b/reachability/walk.go @@ -4,7 +4,7 @@ import ( "codeberg.org/lindenii/furgit/objectid" ) -// Walk is one single-use iterator-style traversal. +// Walk is one single-use iterator traversal. type Walk struct { reachability *Reachability domain Domain diff --git a/reachability/walk_expand_commits.go b/reachability/walk_expand_commits.go index e72092f4..ac24be91 100644 --- a/reachability/walk_expand_commits.go +++ b/reachability/walk_expand_commits.go @@ -3,6 +3,7 @@ package reachability import ( "fmt" + "codeberg.org/lindenii/furgit/errors" "codeberg.org/lindenii/furgit/object" "codeberg.org/lindenii/furgit/objecttype" ) @@ -63,7 +64,7 @@ func (walk *Walk) expandCommits(item walkItem) ([]walkItem, error) { return []walkItem{{id: tag.Target, want: objecttype.TypeInvalid}}, nil case objecttype.TypeTree, objecttype.TypeBlob, objecttype.TypeInvalid, objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta: - return nil, &ObjectTypeError{OID: item.id, Got: ty, Want: objecttype.TypeCommit} + return nil, &errors.ObjectTypeError{OID: item.id, Got: ty, Want: objecttype.TypeCommit} } return nil, fmt.Errorf("reachability: unreachable object type %d", ty) diff --git a/reachability/walk_expand_objects.go b/reachability/walk_expand_objects.go index 9dc2ff80..1f634c26 100644 --- a/reachability/walk_expand_objects.go +++ b/reachability/walk_expand_objects.go @@ -3,6 +3,7 @@ package reachability import ( "fmt" + "codeberg.org/lindenii/furgit/errors" "codeberg.org/lindenii/furgit/object" "codeberg.org/lindenii/furgit/objecttype" ) @@ -14,7 +15,7 @@ func (walk *Walk) expandObjects(item walkItem) ([]walkItem, error) { } if item.want != objecttype.TypeInvalid && ty != item.want { - return nil, &ObjectTypeError{OID: item.id, Got: ty, Want: item.want} + return nil, &errors.ObjectTypeError{OID: item.id, Got: ty, Want: item.want} } switch ty { @@ -76,7 +77,7 @@ func (walk *Walk) expandObjects(item walkItem) ([]walkItem, error) { return []walkItem{{id: tag.Target, want: tag.TargetType}}, nil case objecttype.TypeInvalid, objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta: - return nil, &ObjectTypeError{OID: item.id, Got: ty, Want: item.want} + return nil, &errors.ObjectTypeError{OID: item.id, Got: ty, Want: item.want} } return nil, fmt.Errorf("reachability: unreachable object type %d", ty) diff --git a/reachability/walk_verify.go b/reachability/walk_verify.go index 82eb7566..5b1b498d 100644 --- a/reachability/walk_verify.go +++ b/reachability/walk_verify.go @@ -1,6 +1,7 @@ package reachability import ( + "codeberg.org/lindenii/furgit/errors" "codeberg.org/lindenii/furgit/object" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objecttype" @@ -13,7 +14,7 @@ func (walk *Walk) validateCommitObject(id objectid.ObjectID) error { } if ty != objecttype.TypeCommit { - return &ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit} + return &errors.ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit} } content, err := walk.readBytesContent(id) diff --git a/refstore/loose/loose_test.go b/refstore/loose/loose_test.go index 7b295bbb..912d7c9e 100644 --- a/refstore/loose/loose_test.go +++ b/refstore/loose/loose_test.go @@ -2,8 +2,6 @@ package loose_test import ( "errors" - "os" - "path/filepath" "slices" "testing" @@ -14,15 +12,10 @@ import ( "codeberg.org/lindenii/furgit/refstore/loose" ) -func openLooseStore(t *testing.T, repoPath string, algo objectid.Algorithm) *loose.Store { +func openLooseStore(t *testing.T, testRepo *testgit.TestRepo, algo objectid.Algorithm) *loose.Store { t.Helper() - root, err := os.OpenRoot(repoPath) - if err != nil { - t.Fatalf("OpenRoot(%q): %v", repoPath, err) - } - - t.Cleanup(func() { _ = root.Close() }) + root := testRepo.OpenGitRoot(t) store, err := loose.New(root, algo) if err != nil { @@ -40,7 +33,7 @@ func TestLooseResolveAndResolveFully(t *testing.T) { testRepo.UpdateRef(t, "refs/heads/main", commitID) testRepo.SymbolicRef(t, "HEAD", "refs/heads/main") - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) resolvedHead, err := store.Resolve("HEAD") if err != nil { @@ -93,7 +86,7 @@ func TestLooseResolveFullyCycle(t *testing.T) { testRepo.SymbolicRef(t, "refs/heads/a", "refs/heads/b") testRepo.SymbolicRef(t, "refs/heads/b", "refs/heads/a") - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) _, err := store.ResolveFully("refs/heads/a") if err == nil { @@ -112,7 +105,7 @@ func TestLooseListPattern(t *testing.T) { testRepo.UpdateRef(t, "refs/tags/v1.0.0", commitID) testRepo.SymbolicRef(t, "HEAD", "refs/heads/main") - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) allRefs, err := store.List("") if err != nil { @@ -161,7 +154,7 @@ func TestLooseListPatternMatrix(t *testing.T) { testRepo.UpdateRef(t, "refs/tags/v1", commitID) testRepo.SymbolicRef(t, "HEAD", "refs/heads/main") - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) tests := []struct { pattern string @@ -223,21 +216,11 @@ func TestLooseMalformedDetachedRef(t *testing.T) { testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper testRepo := testgit.NewRepo(t, testgit.RepoOptions{ObjectFormat: algo, Bare: true}) - refPath := filepath.Join(testRepo.Dir(), "refs", "heads", "bad") - - err := os.MkdirAll(filepath.Dir(refPath), 0o755) - if err != nil { - t.Fatalf("MkdirAll: %v", err) - } - - err = os.WriteFile(refPath, []byte("not-a-hash\n"), 0o644) - if err != nil { - t.Fatalf("WriteFile: %v", err) - } + testRepo.WriteFileAll(t, "refs/heads/bad", []byte("not-a-hash\n"), 0o755, 0o644) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) - _, err = store.Resolve("refs/heads/bad") + _, err := store.Resolve("refs/heads/bad") if err == nil { t.Fatalf("Resolve(malformed) expected error") } @@ -253,7 +236,7 @@ func TestLooseShorten(t *testing.T) { testRepo.UpdateRef(t, "refs/tags/main", commitID) testRepo.UpdateRef(t, "refs/remotes/origin/main", commitID) - store := openLooseStore(t, testRepo.Dir(), algo) + store := openLooseStore(t, testRepo, algo) shortHead, err := store.Shorten("refs/heads/main") if err != nil { diff --git a/refstore/packed/packed_test.go b/refstore/packed/packed_test.go index 9d6b2fe1..e5a56dda 100644 --- a/refstore/packed/packed_test.go +++ b/refstore/packed/packed_test.go @@ -14,15 +14,10 @@ import ( "codeberg.org/lindenii/furgit/refstore/packed" ) -func openPackedRefStoreFromRepo(t *testing.T, repoPath string, algo objectid.Algorithm) *packed.Store { +func openPackedRefStoreFromRepo(t *testing.T, testRepo *testgit.TestRepo, algo objectid.Algorithm) *packed.Store { t.Helper() - root, err := os.OpenRoot(repoPath) - if err != nil { - t.Fatalf("OpenRoot(repo): %v", err) - } - - defer func() { _ = root.Close() }() + root := testRepo.OpenGitRoot(t) store, err := packed.New(root, algo) if err != nil { @@ -37,11 +32,6 @@ func openPackedRefStoreFromContent(t *testing.T, content string, algo objectid.A dir := t.TempDir() - err := os.WriteFile(dir+"/packed-refs", []byte(content), 0o644) - if err != nil { - t.Fatalf("WriteFile(packed-refs): %v", err) - } - root, err := os.OpenRoot(dir) if err != nil { t.Fatalf("OpenRoot(temp): %v", err) @@ -49,6 +39,11 @@ func openPackedRefStoreFromContent(t *testing.T, content string, algo objectid.A defer func() { _ = root.Close() }() + err = root.WriteFile("packed-refs", []byte(content), 0o644) + if err != nil { + t.Fatalf("WriteFile(packed-refs): %v", err) + } + return packed.New(root, algo) } @@ -61,7 +56,7 @@ func TestPackedResolveAndPeeled(t *testing.T) { tagID := testRepo.TagAnnotated(t, "v1.0.0", commitID, "annotated tag") testRepo.PackRefs(t, "--all", "--prune") - store := openPackedRefStoreFromRepo(t, testRepo.Dir(), algo) + store := openPackedRefStoreFromRepo(t, testRepo, algo) resolvedMain, err := store.Resolve("refs/heads/main") if err != nil { @@ -125,7 +120,7 @@ func TestPackedListAndShorten(t *testing.T) { testRepo.UpdateRef(t, "refs/remotes/origin/main", commitID) testRepo.PackRefs(t, "--all", "--prune") - store := openPackedRefStoreFromRepo(t, testRepo.Dir(), algo) + store := openPackedRefStoreFromRepo(t, testRepo, algo) all, err := store.List("") if err != nil { @@ -180,7 +175,7 @@ func TestPackedListPatternMatrix(t *testing.T) { testRepo.UpdateRef(t, "refs/tags/v1", commitID) testRepo.PackRefs(t, "--all", "--prune") - store := openPackedRefStoreFromRepo(t, testRepo.Dir(), algo) + store := openPackedRefStoreFromRepo(t, testRepo, algo) tests := []struct { pattern string diff --git a/repository/refs_test.go b/repository/refs_test.go index 8d8c604e..8b2676a2 100644 --- a/repository/refs_test.go +++ b/repository/refs_test.go @@ -1,14 +1,12 @@ package repository_test import ( - "os" "testing" "codeberg.org/lindenii/furgit/internal/testgit" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objecttype" "codeberg.org/lindenii/furgit/ref" - "codeberg.org/lindenii/furgit/repository" ) func TestOpenFilesRefFormat(t *testing.T) { @@ -25,19 +23,7 @@ func TestOpenFilesRefFormat(t *testing.T) { repoHarness.UpdateRef(t, "refs/heads/main", commitID) repoHarness.SymbolicRef(t, "HEAD", "refs/heads/main") - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) if repo.Algorithm() != algo { t.Fatalf("Algorithm = %v, want %v", repo.Algorithm(), algo) @@ -114,19 +100,7 @@ func writeMainAndHead(t *testing.T, repoHarness *testgit.TestRepo) objectid.Obje func assertResolveFully(t *testing.T, repoHarness *testgit.TestRepo, name string, want objectid.ObjectID) { t.Helper() - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) resolved, err := repo.Refs().ResolveFully(name) if err != nil { diff --git a/repository/stored_test.go b/repository/stored_test.go index 0ca88664..cefb4cbe 100644 --- a/repository/stored_test.go +++ b/repository/stored_test.go @@ -2,14 +2,12 @@ package repository_test import ( "fmt" - "os" "strings" "testing" "codeberg.org/lindenii/furgit/internal/testgit" "codeberg.org/lindenii/furgit/object" "codeberg.org/lindenii/furgit/objectid" - "codeberg.org/lindenii/furgit/repository" ) func TestReadStoredTyped(t *testing.T) { @@ -24,19 +22,7 @@ func TestReadStoredTyped(t *testing.T) { blobID, treeID, commitID := repoHarness.MakeCommit(t, "stored types") - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) blob, err := repo.ReadStoredBlob(blobID) if err != nil { @@ -93,19 +79,7 @@ func TestResolveTreeEntry(t *testing.T) { childTreeID := repoHarness.Mktree(t, fmt.Sprintf("100644 blob %s\tleaf.txt\n", blobID)) rootTreeID := repoHarness.Mktree(t, fmt.Sprintf("040000 tree %s\tdir\n", childTreeID)) - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) rootTree, err := repo.ReadStoredTree(rootTreeID) if err != nil { @@ -141,19 +115,7 @@ func TestResolveTreeEntryErrors(t *testing.T) { blobID := repoHarness.HashObject(t, "blob", []byte("body\n")) rootTreeID := repoHarness.Mktree(t, fmt.Sprintf("100644 blob %s\tfile.txt\n", blobID)) - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) rootTree, err := repo.ReadStoredTree(rootTreeID) if err != nil { @@ -176,19 +138,7 @@ func TestResolveTreeEntryErrors(t *testing.T) { blobID := repoHarness.HashObject(t, "blob", []byte("body\n")) rootTreeID := repoHarness.Mktree(t, fmt.Sprintf("100644 blob %s\tdir\n", blobID)) - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) rootTree, err := repo.ReadStoredTree(rootTreeID) if err != nil { @@ -227,19 +177,7 @@ func TestResolveTreeEntryDeepPath(t *testing.T) { parts = append(parts, []byte("leaf.txt")) - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) rootTree, err := repo.ReadStoredTree(currentTree) if err != nil { @@ -287,19 +225,7 @@ func TestReadStoredTreeMixedModes(t *testing.T) { ), ) - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) rootTree, err := repo.ReadStoredTree(rootTreeID) if err != nil { diff --git a/repository/traversal_test.go b/repository/traversal_test.go index ff3614dc..d5eaabb4 100644 --- a/repository/traversal_test.go +++ b/repository/traversal_test.go @@ -31,7 +31,8 @@ func TestRepositoryDepthFirstEnumerationFromHEAD(t *testing.T) { repoHarness.UpdateRef(t, "refs/heads/main", commit2) repoHarness.SymbolicRef(t, "HEAD", "refs/heads/main") - walkRepositoryFromHead(t, repoHarness.Dir()) + root := repoHarness.OpenGitRoot(t) + walkRepositoryFromRoot(t, root, "test repo") }) } @@ -39,38 +40,51 @@ func TestRepositoryDepthFirstEnumerationCurrentWorktree(t *testing.T) { t.Parallel() worktreeRoot := filepath.Clean("..") - gitPath := filepath.Join(worktreeRoot, ".git") - info, err := os.Stat(gitPath) + worktreeFS, err := os.OpenRoot(worktreeRoot) if err != nil { - t.Fatalf("stat %q: %v", gitPath, err) + t.Fatalf("os.OpenRoot(%q): %v", worktreeRoot, err) + } + + defer func() { _ = worktreeFS.Close() }() + + info, err := worktreeFS.Stat(".git") + if err != nil { + t.Fatalf("stat %q: %v", filepath.Join(worktreeRoot, ".git"), err) } if info.IsDir() { - walkRepositoryFromHead(t, gitPath) + gitRoot, err := worktreeFS.OpenRoot(".git") + if err != nil { + t.Fatalf("OpenRoot(.git): %v", err) + } + + defer func() { _ = gitRoot.Close() }() + + walkRepositoryFromRoot(t, gitRoot, filepath.Join(worktreeRoot, ".git")) return } if !info.Mode().IsRegular() { - t.Fatalf("%q is neither a directory nor a regular file", gitPath) + t.Fatalf("%q is neither a directory nor a regular file", filepath.Join(worktreeRoot, ".git")) } - content, err := os.ReadFile(gitPath) //#nosec G304 + content, err := worktreeFS.ReadFile(".git") if err != nil { - t.Fatalf("read %q: %v", gitPath, err) + t.Fatalf("read %q: %v", filepath.Join(worktreeRoot, ".git"), err) } line := strings.TrimSpace(string(content)) prefix := "gitdir: " if !strings.HasPrefix(line, prefix) { - t.Fatalf("%q file does not begin with %q", gitPath, prefix) + t.Fatalf("%q file does not begin with %q", filepath.Join(worktreeRoot, ".git"), prefix) } gitdirRel := strings.TrimSpace(line[len(prefix):]) if gitdirRel == "" { - t.Fatalf("%q contains empty gitdir path", gitPath) + t.Fatalf("%q contains empty gitdir path", filepath.Join(worktreeRoot, ".git")) } gitdirPath := gitdirRel @@ -78,42 +92,54 @@ func TestRepositoryDepthFirstEnumerationCurrentWorktree(t *testing.T) { gitdirPath = filepath.Join(worktreeRoot, gitdirPath) } - commondirPath := filepath.Join(gitdirPath, "commondir") + gitRoot, err := os.OpenRoot(gitdirPath) + if err != nil { + t.Fatalf("os.OpenRoot(%q): %v", gitdirPath, err) + } + + defer func() { _ = gitRoot.Close() }() - commondirContent, err := os.ReadFile(commondirPath) //#nosec G304 + commondirContent, err := gitRoot.ReadFile("commondir") if err != nil { - t.Fatalf("read %q: %v", commondirPath, err) + t.Fatalf("read %q: %v", filepath.Join(gitdirPath, "commondir"), err) } repoPath := strings.TrimSpace(string(commondirContent)) if repoPath == "" { - t.Fatalf("%q contains empty repo path", commondirPath) + t.Fatalf("%q contains empty repo path", filepath.Join(gitdirPath, "commondir")) } if filepath.IsAbs(repoPath) { - walkRepositoryFromHead(t, repoPath) + repoRoot, err := os.OpenRoot(repoPath) + if err != nil { + t.Fatalf("os.OpenRoot(%q): %v", repoPath, err) + } + + defer func() { _ = repoRoot.Close() }() + + walkRepositoryFromRoot(t, repoRoot, repoPath) return } repoPath = filepath.Join(gitdirPath, repoPath) - walkRepositoryFromHead(t, repoPath) -} - -func walkRepositoryFromHead(t *testing.T, repoPath string) { - t.Helper() - - root, err := os.OpenRoot(repoPath) + repoRoot, err := os.OpenRoot(repoPath) if err != nil { t.Fatalf("os.OpenRoot(%q): %v", repoPath, err) } - defer func() { _ = root.Close() }() + defer func() { _ = repoRoot.Close() }() + + walkRepositoryFromRoot(t, repoRoot, repoPath) +} + +func walkRepositoryFromRoot(t *testing.T, root *os.Root, label string) { + t.Helper() repo, err := repository.Open(root) if err != nil { - t.Fatalf("repository.Open(root for %q): %v", repoPath, err) + t.Fatalf("repository.Open(root for %q): %v", label, err) } defer func() { _ = repo.Close() }() @@ -129,7 +155,7 @@ func walkRepositoryFromHead(t *testing.T, repoPath string) { } if objectsRead <= 0 { - t.Fatalf("no objects were enumerated from HEAD (%s)", fmt.Sprintf("%q", repoPath)) + t.Fatalf("no objects were enumerated from HEAD (%s)", fmt.Sprintf("%q", label)) } } diff --git a/repository/write_loose_test.go b/repository/write_loose_test.go index 6cd9b8a1..6b0a8572 100644 --- a/repository/write_loose_test.go +++ b/repository/write_loose_test.go @@ -2,13 +2,11 @@ package repository_test import ( "bytes" - "os" "testing" "codeberg.org/lindenii/furgit/internal/testgit" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objecttype" - "codeberg.org/lindenii/furgit/repository" ) func TestWriteLooseBytesContent(t *testing.T) { @@ -21,19 +19,7 @@ func TestWriteLooseBytesContent(t *testing.T) { RefFormat: "files", }) - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) content := []byte("write-loose-bytes-content\n") @@ -72,19 +58,7 @@ func TestWriteLooseReaderContent(t *testing.T) { RefFormat: "files", }) - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) content := []byte("write-loose-reader-content\n") @@ -111,19 +85,7 @@ func TestWriteLooseFull(t *testing.T) { }) _, _, commitID := repoHarness.MakeCommit(t, "write-loose-full") - root, err := os.OpenRoot(repoHarness.Dir()) - if err != nil { - t.Fatalf("os.OpenRoot: %v", err) - } - - defer func() { _ = root.Close() }() - - repo, err := repository.Open(root) - if err != nil { - t.Fatalf("repository.Open: %v", err) - } - - defer func() { _ = repo.Close() }() + repo := repoHarness.OpenRepository(t) raw, err := repo.Objects().ReadBytesFull(commitID) if err != nil { -- cgit v1.3.1-10-gc9f91