aboutsummaryrefslogtreecommitdiff
path: root/object/tree
diff options
context:
space:
mode:
Diffstat (limited to 'object/tree')
-rw-r--r--object/tree/entry.go39
-rw-r--r--object/tree/helpers_test.go114
-rw-r--r--object/tree/insert.go23
-rw-r--r--object/tree/lookup.go14
-rw-r--r--object/tree/mode.go12
-rw-r--r--object/tree/name.go51
-rw-r--r--object/tree/parse.go58
-rw-r--r--object/tree/parse_test.go76
-rw-r--r--object/tree/remove.go24
-rw-r--r--object/tree/serialize.go55
-rw-r--r--object/tree/serialize_test.go73
-rw-r--r--object/tree/tree.go7
-rw-r--r--object/tree/type.go10
13 files changed, 556 insertions, 0 deletions
diff --git a/object/tree/entry.go b/object/tree/entry.go
new file mode 100644
index 00000000..cddcde73
--- /dev/null
+++ b/object/tree/entry.go
@@ -0,0 +1,39 @@
+package tree
+
+import (
+ "bytes"
+
+ objectid "codeberg.org/lindenii/furgit/object/id"
+)
+
+// TreeEntry represents a single entry in a tree.
+type TreeEntry struct {
+ Mode FileMode
+ Name []byte
+ ID objectid.ObjectID
+}
+
+func (tree *Tree) entry(name []byte, searchIsTree bool) *TreeEntry {
+ low, high := 0, len(tree.Entries)-1
+ for low <= high {
+ mid := low + (high-low)/2
+ entry := &tree.Entries[mid]
+
+ cmp := TreeEntryNameCompare(entry.Name, entry.Mode, name, searchIsTree)
+ if cmp == 0 {
+ if bytes.Equal(entry.Name, name) {
+ return entry
+ }
+
+ return nil
+ }
+
+ if cmp < 0 {
+ low = mid + 1
+ } else {
+ high = mid - 1
+ }
+ }
+
+ return nil
+}
diff --git a/object/tree/helpers_test.go b/object/tree/helpers_test.go
new file mode 100644
index 00000000..3da92ce4
--- /dev/null
+++ b/object/tree/helpers_test.go
@@ -0,0 +1,114 @@
+package tree_test
+
+import (
+ "bytes"
+ "fmt"
+ "strings"
+ "testing"
+
+ "codeberg.org/lindenii/furgit/internal/testgit"
+ "codeberg.org/lindenii/furgit/object/tree"
+)
+
+func buildGitMktreeInput(entries []tree.TreeEntry) string {
+ var b strings.Builder
+ for _, e := range entries {
+ fmt.Fprintf(&b, "%o %s %s\t%s\n", e.Mode, mktreeTypeFromMode(e.Mode), e.ID.String(), e.Name)
+ }
+
+ return b.String()
+}
+
+func mktreeTypeFromMode(mode tree.FileMode) string {
+ switch mode {
+ case tree.FileModeDir:
+ return "tree"
+ case tree.FileModeRegular, tree.FileModeExecutable, tree.FileModeSymlink:
+ return "blob"
+ case tree.FileModeGitlink:
+ return "commit"
+ default:
+ return ""
+ }
+}
+
+func gitLsTreeNames(out []byte) [][]byte {
+ if len(out) == 0 {
+ return nil
+ }
+
+ parts := bytes.Split(out, []byte{0})
+ if len(parts) > 0 && len(parts[len(parts)-1]) == 0 {
+ parts = parts[:len(parts)-1]
+ }
+
+ names := make([][]byte, 0, len(parts))
+ for _, name := range parts {
+ names = append(names, append([]byte(nil), name...))
+ }
+
+ return names
+}
+
+func adversarialRootEntries(t *testing.T, testRepo *testgit.TestRepo) []tree.TreeEntry {
+ t.Helper()
+
+ blobA := testRepo.HashObject(t, "blob", []byte("blob-A\n"))
+ blobB := testRepo.HashObject(t, "blob", []byte("blob-B\n"))
+ blobC := testRepo.HashObject(t, "blob", []byte("blob-C\n"))
+
+ subDirA := testRepo.Mktree(t,
+ fmt.Sprintf("100644 blob %s\tnested-a.txt\n100755 blob %s\trun-a.sh\n", blobA.String(), blobB.String()))
+ subDirB := testRepo.Mktree(t,
+ fmt.Sprintf("100644 blob %s\tnested-b.txt\n100644 blob %s\tz-last\n", blobB.String(), blobC.String()))
+ subDirC := testRepo.Mktree(t,
+ fmt.Sprintf("120000 blob %s\tlink-c\n100644 blob %s\tchild\n", blobC.String(), blobA.String()))
+ subDirD := testRepo.Mktree(t,
+ fmt.Sprintf("100644 blob %s\tleaf\n", blobA.String()))
+
+ return []tree.TreeEntry{
+ {Mode: tree.FileModeRegular, Name: []byte("z"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("A"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("aa"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("a0"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("a-"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("a."), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("a_"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("a~"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("Z"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("0"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("9"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("00"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("这是一些非 ASCII 的字符"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("𲰼是新进入 Unicode 的字符"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("Emoji 👀"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("_"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("-dash"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("dot.file"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte(".hidden"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("CAPS"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("caps"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("mixCase"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("name with space"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("name-with-dash"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("name.with.dot"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("name_with_underscore"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("tilde~name"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("brace{name}"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("plus+name"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("equal=name"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("at@name"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("percent%name"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("caret^name"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("comma,name"), ID: blobA},
+ {Mode: tree.FileModeRegular, Name: []byte("semi;name"), ID: blobB},
+ {Mode: tree.FileModeRegular, Name: []byte("paren(name)"), ID: blobC},
+ {Mode: tree.FileModeRegular, Name: []byte("bracket[name]"), ID: blobA},
+ {Mode: tree.FileModeExecutable, Name: []byte("exec.sh"), ID: blobB},
+ {Mode: tree.FileModeSymlink, Name: []byte("sym.link"), ID: blobC},
+ {Mode: tree.FileModeDir, Name: []byte("dir"), ID: subDirA},
+ {Mode: tree.FileModeDir, Name: []byte("dir0"), ID: subDirB},
+ {Mode: tree.FileModeDir, Name: []byte("dir.space"), ID: subDirC},
+ {Mode: tree.FileModeDir, Name: []byte("x"), ID: subDirD},
+ }
+}
diff --git a/object/tree/insert.go b/object/tree/insert.go
new file mode 100644
index 00000000..bca4aa49
--- /dev/null
+++ b/object/tree/insert.go
@@ -0,0 +1,23 @@
+package tree
+
+import (
+ "fmt"
+ "sort"
+)
+
+// InsertEntry inserts a tree entry while preserving Git ordering.
+func (tree *Tree) InsertEntry(newEntry TreeEntry) error {
+ if tree.entry(newEntry.Name, true) != nil || tree.entry(newEntry.Name, false) != nil {
+ return fmt.Errorf("object: tree: entry %q already exists", newEntry.Name)
+ }
+
+ newIsTree := newEntry.Mode == FileModeDir
+ insertAt := sort.Search(len(tree.Entries), func(i int) bool {
+ return TreeEntryNameCompare(tree.Entries[i].Name, tree.Entries[i].Mode, newEntry.Name, newIsTree) >= 0
+ })
+ tree.Entries = append(tree.Entries, TreeEntry{})
+ copy(tree.Entries[insertAt+1:], tree.Entries[insertAt:])
+ tree.Entries[insertAt] = newEntry
+
+ return nil
+}
diff --git a/object/tree/lookup.go b/object/tree/lookup.go
new file mode 100644
index 00000000..957b31c4
--- /dev/null
+++ b/object/tree/lookup.go
@@ -0,0 +1,14 @@
+package tree
+
+// Entry looks up a tree entry by name.
+func (tree *Tree) Entry(name []byte) *TreeEntry {
+ if len(tree.Entries) == 0 {
+ return nil
+ }
+
+ if e := tree.entry(name, true); e != nil {
+ return e
+ }
+
+ return tree.entry(name, false)
+}
diff --git a/object/tree/mode.go b/object/tree/mode.go
new file mode 100644
index 00000000..b1cbc6bc
--- /dev/null
+++ b/object/tree/mode.go
@@ -0,0 +1,12 @@
+package tree
+
+// FileMode represents the mode of a file in a Git tree.
+type FileMode uint32
+
+const (
+ FileModeDir FileMode = 0o40000
+ FileModeRegular FileMode = 0o100644
+ FileModeExecutable FileMode = 0o100755
+ FileModeSymlink FileMode = 0o120000
+ FileModeGitlink FileMode = 0o160000
+)
diff --git a/object/tree/name.go b/object/tree/name.go
new file mode 100644
index 00000000..02af3292
--- /dev/null
+++ b/object/tree/name.go
@@ -0,0 +1,51 @@
+package tree
+
+// TreeEntryNameCompare compares names using Git tree ordering rules.
+func TreeEntryNameCompare(entryName []byte, entryMode FileMode, searchName []byte, searchIsTree bool) int {
+ isEntryTree := entryMode == FileModeDir
+
+ entryLen := len(entryName)
+ if isEntryTree {
+ entryLen++
+ }
+
+ searchLen := len(searchName)
+ if searchIsTree {
+ searchLen++
+ }
+
+ n := min(searchLen, entryLen)
+
+ for i := range n {
+ var ec, sc byte
+ if i < len(entryName) {
+ ec = entryName[i]
+ } else {
+ ec = '/'
+ }
+
+ if i < len(searchName) {
+ sc = searchName[i]
+ } else {
+ sc = '/'
+ }
+
+ if ec < sc {
+ return -1
+ }
+
+ if ec > sc {
+ return 1
+ }
+ }
+
+ if entryLen < searchLen {
+ return -1
+ }
+
+ if entryLen > searchLen {
+ return 1
+ }
+
+ return 0
+}
diff --git a/object/tree/parse.go b/object/tree/parse.go
new file mode 100644
index 00000000..10bef968
--- /dev/null
+++ b/object/tree/parse.go
@@ -0,0 +1,58 @@
+package tree
+
+import (
+ "bytes"
+ "fmt"
+ "strconv"
+
+ objectid "codeberg.org/lindenii/furgit/object/id"
+)
+
+// Parse decodes a tree object body.
+func Parse(body []byte, algo objectid.Algorithm) (*Tree, error) {
+ var entries []TreeEntry
+
+ i := 0
+ for i < len(body) {
+ space := bytes.IndexByte(body[i:], ' ')
+ if space < 0 {
+ return nil, fmt.Errorf("object: tree: missing mode terminator")
+ }
+
+ modeBytes := body[i : i+space]
+ i += space + 1
+
+ nul := bytes.IndexByte(body[i:], 0)
+ if nul < 0 {
+ return nil, fmt.Errorf("object: tree: missing name terminator")
+ }
+
+ nameBytes := body[i : i+nul]
+ i += nul + 1
+
+ idEnd := i + algo.Size()
+ if idEnd > len(body) {
+ return nil, fmt.Errorf("object: tree: truncated child object id")
+ }
+
+ id, err := objectid.FromBytes(algo, body[i:idEnd])
+ if err != nil {
+ return nil, err
+ }
+
+ i = idEnd
+
+ mode, err := strconv.ParseUint(string(modeBytes), 8, 32)
+ if err != nil {
+ return nil, fmt.Errorf("object: tree: parse mode: %w", err)
+ }
+
+ entries = append(entries, TreeEntry{
+ Mode: FileMode(mode),
+ Name: append([]byte(nil), nameBytes...),
+ ID: id,
+ })
+ }
+
+ return &Tree{Entries: entries}, nil
+}
diff --git a/object/tree/parse_test.go b/object/tree/parse_test.go
new file mode 100644
index 00000000..6f00220e
--- /dev/null
+++ b/object/tree/parse_test.go
@@ -0,0 +1,76 @@
+package tree_test
+
+import (
+ "bytes"
+ "testing"
+
+ "codeberg.org/lindenii/furgit/internal/testgit"
+ objectid "codeberg.org/lindenii/furgit/object/id"
+ "codeberg.org/lindenii/furgit/object/tree"
+)
+
+func TestTreeParseFromGit(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})
+ entries := adversarialRootEntries(t, testRepo)
+
+ inserted := &tree.Tree{}
+ for _, entry := range entries {
+ err := inserted.InsertEntry(entry)
+ if err != nil {
+ t.Fatalf("InsertEntry(%q): %v", entry.Name, err)
+ }
+ }
+
+ treeID := testRepo.Mktree(t, buildGitMktreeInput(inserted.Entries))
+
+ rawBody := testRepo.CatFile(t, "tree", treeID)
+
+ parsed, err := tree.Parse(rawBody, algo)
+ if err != nil {
+ t.Fatalf("ParseTree: %v", err)
+ }
+
+ if len(parsed.Entries) != len(inserted.Entries) {
+ t.Fatalf("entry count = %d, want %d", len(parsed.Entries), len(inserted.Entries))
+ }
+
+ for i := range inserted.Entries {
+ got := parsed.Entries[i]
+
+ want := inserted.Entries[i]
+ if got.Mode != want.Mode || got.ID != want.ID || !bytes.Equal(got.Name, want.Name) {
+ t.Fatalf("entry[%d] mismatch: got (%o,%q,%s) want (%o,%q,%s)",
+ i, got.Mode, got.Name, got.ID, want.Mode, want.Name, want.ID)
+ }
+ }
+
+ lsNames := gitLsTreeNames(testRepo.RunBytes(t, "ls-tree", "--name-only", "-z", treeID.String()))
+ if len(lsNames) != len(parsed.Entries) {
+ t.Fatalf("ls-tree names = %d, want %d", len(lsNames), len(parsed.Entries))
+ }
+
+ for i := range lsNames {
+ if !bytes.Equal(lsNames[i], parsed.Entries[i].Name) {
+ t.Fatalf("ordering mismatch at %d: git=%q parsed=%q", i, lsNames[i], parsed.Entries[i].Name)
+ }
+ }
+
+ for _, want := range inserted.Entries {
+ got := parsed.Entry(want.Name)
+
+ if got == nil {
+ t.Fatalf("Entry(%q) returned nil", want.Name)
+ }
+
+ if got.Mode != want.Mode || got.ID != want.ID {
+ t.Fatalf("Entry(%q) mismatch", want.Name)
+ }
+ }
+
+ if parsed.Entry([]byte("does-not-exist")) != nil {
+ t.Fatalf("Entry on missing name should be nil")
+ }
+ })
+}
diff --git a/object/tree/remove.go b/object/tree/remove.go
new file mode 100644
index 00000000..9eb42028
--- /dev/null
+++ b/object/tree/remove.go
@@ -0,0 +1,24 @@
+package tree
+
+import (
+ "bytes"
+ "fmt"
+)
+
+// RemoveEntry removes a tree entry by name.
+func (tree *Tree) RemoveEntry(name []byte) error {
+ if len(tree.Entries) == 0 {
+ return fmt.Errorf("object: tree: entry %q not found", name)
+ }
+
+ for i := range tree.Entries {
+ if bytes.Equal(tree.Entries[i].Name, name) {
+ copy(tree.Entries[i:], tree.Entries[i+1:])
+ tree.Entries = tree.Entries[:len(tree.Entries)-1]
+
+ return nil
+ }
+ }
+
+ return fmt.Errorf("object: tree: entry %q not found", name)
+}
diff --git a/object/tree/serialize.go b/object/tree/serialize.go
new file mode 100644
index 00000000..be31297b
--- /dev/null
+++ b/object/tree/serialize.go
@@ -0,0 +1,55 @@
+package tree
+
+import (
+ "errors"
+ "strconv"
+
+ objectheader "codeberg.org/lindenii/furgit/object/header"
+ objecttype "codeberg.org/lindenii/furgit/object/type"
+)
+
+// SerializeWithoutHeader renders the raw tree body bytes.
+func (tree *Tree) SerializeWithoutHeader() ([]byte, error) {
+ var bodyLen int
+
+ for _, entry := range tree.Entries {
+ mode := strconv.FormatUint(uint64(entry.Mode), 8)
+ bodyLen += len(mode) + 1 + len(entry.Name) + 1 + entry.ID.Size()
+ }
+
+ body := make([]byte, bodyLen)
+ pos := 0
+
+ for _, entry := range tree.Entries {
+ mode := strconv.FormatUint(uint64(entry.Mode), 8)
+ pos += copy(body[pos:], mode)
+ body[pos] = ' '
+ pos++
+ pos += copy(body[pos:], entry.Name)
+ body[pos] = 0
+ pos++
+ id := entry.ID.Bytes()
+ pos += copy(body[pos:], id)
+ }
+
+ return body, nil
+}
+
+// SerializeWithHeader renders the raw object (header + body).
+func (tree *Tree) SerializeWithHeader() ([]byte, error) {
+ body, err := tree.SerializeWithoutHeader()
+ if err != nil {
+ return nil, err
+ }
+
+ header, ok := objectheader.Encode(objecttype.TypeTree, int64(len(body)))
+ if !ok {
+ return nil, errors.New("object: tree: failed to encode object header")
+ }
+
+ raw := make([]byte, len(header)+len(body))
+ copy(raw, header)
+ copy(raw[len(header):], body)
+
+ return raw, nil
+}
diff --git a/object/tree/serialize_test.go b/object/tree/serialize_test.go
new file mode 100644
index 00000000..9c9a2f1c
--- /dev/null
+++ b/object/tree/serialize_test.go
@@ -0,0 +1,73 @@
+package tree_test
+
+import (
+ "testing"
+
+ "codeberg.org/lindenii/furgit/internal/testgit"
+ objectid "codeberg.org/lindenii/furgit/object/id"
+ "codeberg.org/lindenii/furgit/object/tree"
+)
+
+func TestTreeSerialize(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})
+ entries := adversarialRootEntries(t, testRepo)
+ obj := &tree.Tree{}
+
+ for i := len(entries) - 1; i >= 0; i-- {
+ err := obj.InsertEntry(entries[i])
+ if err != nil {
+ t.Fatalf("InsertEntry(%q): %v", entries[i].Name, err)
+ }
+ }
+
+ if len(obj.Entries) < 32 {
+ t.Fatalf("expected at least 32 entries, got %d", len(obj.Entries))
+ }
+
+ dup := obj.Entries[0]
+
+ err := obj.InsertEntry(dup)
+ if err == nil {
+ t.Fatalf("duplicate InsertEntry should fail")
+ }
+
+ removed := obj.Entries[len(obj.Entries)/2]
+
+ err = obj.RemoveEntry(removed.Name)
+ if err != nil {
+ t.Fatalf("RemoveEntry(%q): %v", removed.Name, err)
+ }
+
+ if obj.Entry(removed.Name) != nil {
+ t.Fatalf("Entry(%q) should be nil after remove", removed.Name)
+ }
+
+ err = obj.RemoveEntry([]byte("no-such-entry"))
+ if err == nil {
+ t.Fatalf("RemoveEntry missing entry should fail")
+ }
+
+ err = obj.InsertEntry(removed)
+ if err != nil {
+ t.Fatalf("re-InsertEntry(%q): %v", removed.Name, err)
+ }
+
+ if obj.Entry(removed.Name) == nil {
+ t.Fatalf("Entry(%q) should exist after reinsert", removed.Name)
+ }
+
+ wantTreeID := testRepo.Mktree(t, buildGitMktreeInput(obj.Entries))
+
+ rawObj, err := obj.SerializeWithHeader()
+ if err != nil {
+ t.Fatalf("SerializeWithHeader: %v", err)
+ }
+
+ gotTreeID := algo.Sum(rawObj)
+ if gotTreeID != wantTreeID {
+ t.Fatalf("tree id mismatch: got %s want %s", gotTreeID, wantTreeID)
+ }
+ })
+}
diff --git a/object/tree/tree.go b/object/tree/tree.go
new file mode 100644
index 00000000..3ea6f1ee
--- /dev/null
+++ b/object/tree/tree.go
@@ -0,0 +1,7 @@
+// Package tree provides representations, parsers, and serializers for tree objects.
+package tree
+
+// Tree represents a Git tree object.
+type Tree struct {
+ Entries []TreeEntry
+}
diff --git a/object/tree/type.go b/object/tree/type.go
new file mode 100644
index 00000000..416544af
--- /dev/null
+++ b/object/tree/type.go
@@ -0,0 +1,10 @@
+package tree
+
+import objecttype "codeberg.org/lindenii/furgit/object/type"
+
+// ObjectType returns TypeTree.
+func (tree *Tree) ObjectType() objecttype.Type {
+ _ = tree
+
+ return objecttype.TypeTree
+}
generated by cgit v1.3.1-10-gc9f91 (git 2.54.0) at 2026-05-25 13:13:58 +0000