object: Split each object type into its own package v0.1.108

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
+}