object/tree: Add basic tree functions

9 files changed, 297 insertions, 3 deletions

diff --git a/object/tree/append.go b/object/tree/append.go
new file mode 100644
index 00000000..9985e668
--- /dev/null
+++ b/object/tree/append.go
@@ -0,0 +1,45 @@
+package tree
+
+import (
+	"slices"
+
+	"lindenii.org/go/furgit/object/header"
+	"lindenii.org/go/furgit/object/tree/mode"
+	"lindenii.org/go/furgit/object/typ"
+)
+
+// AppendWithoutHeader renders the raw tree body bytes.
+//
+// It trusts the package invariant that the entries are valid and ordered,
+// so it does not revalidate them.
+func (tree *Tree) AppendWithoutHeader(dst []byte) ([]byte, error) {
+	var bodyLen int
+	for _, entry := range tree.entries {
+		bodyLen += mode.MaxModeDigits + 1 + len(entry.Name) + 1 + entry.ID.ObjectFormat().Size()
+	}
+
+	dst = slices.Grow(dst, bodyLen)
+
+	for _, entry := range tree.entries {
+		dst = entry.Mode.Append(dst)
+		dst = append(dst, ' ')
+		dst = append(dst, entry.Name...)
+		dst = append(dst, 0)
+		dst = append(dst, entry.ID.RawBytes()...)
+	}
+
+	return dst, nil
+}
+
+// AppendWithHeader renders the raw object (header + body).
+func (tree *Tree) AppendWithHeader(dst []byte) ([]byte, error) {
+	// TODO: Try to not allocate?
+	body, err := tree.AppendWithoutHeader(nil)
+	if err != nil {
+		return dst, err
+	}
+
+	dst = header.Append(dst, typ.TypeTree, uint64(len(body)))
+
+	return append(dst, body...), nil
+}
diff --git a/object/tree/compare.go b/object/tree/compare.go
new file mode 100644
index 00000000..78bf56a4
--- /dev/null
+++ b/object/tree/compare.go
@@ -0,0 +1,50 @@
+package tree
+
+// nameCompare compares two tree entry names using Git tree ordering rules.
+//
+// Git orders entries by name,
+// treating directory names as if they carried a trailing '/'.
+// entryIsTree and searchIsTree indicate
+// whether the respective names belong to subtree entries.
+func nameCompare(entryName string, entryIsTree bool, searchName string, searchIsTree bool) int {
+	entryLen := len(entryName)
+	if entryIsTree {
+		entryLen++
+	}
+
+	searchLen := len(searchName)
+	if searchIsTree {
+		searchLen++
+	}
+
+	n := min(entryLen, searchLen)
+
+	for i := range n {
+		ec := byte('/')
+		if i < len(entryName) {
+			ec = entryName[i]
+		}
+
+		sc := byte('/')
+		if i < len(searchName) {
+			sc = searchName[i]
+		}
+
+		if ec < sc {
+			return -1
+		}
+
+		if ec > sc {
+			return 1
+		}
+	}
+
+	switch {
+	case entryLen < searchLen:
+		return -1
+	case entryLen > searchLen:
+		return 1
+	default:
+		return 0
+	}
+}
diff --git a/object/tree/doc.go b/object/tree/doc.go
new file mode 100644
index 00000000..30a5b526
--- /dev/null
+++ b/object/tree/doc.go
@@ -0,0 +1,7 @@
+// Package tree provides parsed tree objects and tree serialization.
+//
+// A [Tree] is a fully materialized Git tree object.
+// It keeps its entries sorted and duplicate-free internally;
+// callers build trees with [Tree.Insert] and read them with [Tree.Entries],
+// neither of which exposes the internal storage.
+package tree
diff --git a/object/tree/insert.go b/object/tree/insert.go
new file mode 100644
index 00000000..e7fce5e9
--- /dev/null
+++ b/object/tree/insert.go
@@ -0,0 +1,75 @@
+package tree
+
+import (
+	"errors"
+	"fmt"
+	"slices"
+	"strings"
+
+	"lindenii.org/go/furgit/object/tree/mode"
+)
+
+// ErrInvalidTree indicates a malformed tree object or tree entry.
+var ErrInvalidTree = errors.New("object/tree: invalid tree")
+
+// Insert adds an entry to the tree while preserving Git tree ordering.
+//
+// It rejects entries with an invalid name or mode,
+// and entries whose name conflicts with one already present.
+func (tree *Tree) Insert(entry Entry) error {
+	if err := validateName(entry.Name); err != nil {
+		return err
+	}
+
+	if !entry.Mode.IsValid() {
+		return fmt.Errorf("%w: entry %q has invalid mode", ErrInvalidTree, entry.Name)
+	}
+
+	if _, found := tree.find(entry.Name); found {
+		return fmt.Errorf("%w: entry %q already exists", ErrInvalidTree, entry.Name)
+	}
+
+	isTree := entry.Mode == mode.Directory
+
+	insertAt, _ := slices.BinarySearchFunc(tree.entries, entry, func(existing Entry, target Entry) int {
+		return nameCompare(existing.Name, existing.Mode == mode.Directory, target.Name, isTree)
+	})
+
+	tree.entries = slices.Insert(tree.entries, insertAt, entry)
+
+	return nil
+}
+
+// find returns the index of the entry with the given name, if present.
+//
+// A name conflicts whether stored as a blob-like or as a subtree entry,
+// so both orderings are searched.
+func (tree *Tree) find(name string) (int, bool) {
+	for _, searchIsTree := range [...]bool{true, false} {
+		index, ok := slices.BinarySearchFunc(tree.entries, name, func(existing Entry, target string) int {
+			return nameCompare(existing.Name, existing.Mode == mode.Directory, target, searchIsTree)
+		})
+		if ok && tree.entries[index].Name == name {
+			return index, true
+		}
+	}
+
+	return 0, false
+}
+
+// validateName checks that name is a structurally valid tree entry name.
+func validateName(name string) error {
+	if name == "" {
+		return fmt.Errorf("%w: empty entry name", ErrInvalidTree)
+	}
+
+	if strings.IndexByte(name, 0) >= 0 {
+		return fmt.Errorf("%w: entry name %q contains NUL", ErrInvalidTree, name)
+	}
+
+	if strings.IndexByte(name, '/') >= 0 {
+		return fmt.Errorf("%w: entry name %q contains '/'", ErrInvalidTree, name)
+	}
+
+	return nil
+}
diff --git a/object/tree/mode/mode.go b/object/tree/mode/mode.go
index 70b6fd38..7f7be163 100644
--- a/object/tree/mode/mode.go
+++ b/object/tree/mode/mode.go
@@ -20,5 +20,5 @@ const (
 	Gitlink Mode = 0o160000
 )
 
-// maxModeDigits is the largest number of octal digits in any canonical mode.
-const maxModeDigits = 6
+// MaxModeDigits is the largest number of octal digits in any canonical mode.
+const MaxModeDigits = 6
diff --git a/object/tree/mode/parse.go b/object/tree/mode/parse.go
index 7839a89a..3009c154 100644
--- a/object/tree/mode/parse.go
+++ b/object/tree/mode/parse.go
@@ -21,7 +21,7 @@ func Parse(raw []byte) (Mode, error) {
 		return 0, fmt.Errorf("%w: zero-padded mode %q", ErrInvalidMode, raw)
 	}
 
-	if len(raw) > maxModeDigits {
+	if len(raw) > MaxModeDigits {
 		return 0, fmt.Errorf("%w: mode %q too long", ErrInvalidMode, raw)
 	}
 
diff --git a/object/tree/parse.go b/object/tree/parse.go
new file mode 100644
index 00000000..b1069918
--- /dev/null
+++ b/object/tree/parse.go
@@ -0,0 +1,72 @@
+package tree
+
+import (
+	"bytes"
+	"fmt"
+
+	"lindenii.org/go/furgit/object/id"
+	"lindenii.org/go/furgit/object/tree/mode"
+)
+
+// Parse decodes a tree object body into a fully materialized Tree.
+//
+// It enforces canonical modes, nonempty slash-free names,
+// correctly sized object IDs, and strictly increasing Git tree order.
+// It does not enforce fsck-level name policy
+// (for example ".", "..", ".git", or platform-specific aliases).
+func Parse(body []byte, objectFormat id.ObjectFormat) (*Tree, error) {
+	tree := new(Tree)
+	idSize := objectFormat.Size()
+
+	i := 0
+	for i < len(body) {
+		space := bytes.IndexByte(body[i:], ' ')
+		if space < 0 {
+			return nil, fmt.Errorf("%w: missing mode terminator at offset %d", ErrInvalidTree, i)
+		}
+
+		entryMode, err := mode.Parse(body[i : i+space])
+		if err != nil {
+			return nil, fmt.Errorf("%w: %w", ErrInvalidTree, err)
+		}
+
+		i += space + 1
+
+		nul := bytes.IndexByte(body[i:], 0)
+		if nul < 0 {
+			return nil, fmt.Errorf("%w: missing name terminator at offset %d", ErrInvalidTree, i)
+		}
+
+		name := string(body[i : i+nul])
+		i += nul + 1
+
+		if err := validateName(name); err != nil {
+			return nil, err
+		}
+
+		idEnd := i + idSize
+		if idEnd > len(body) {
+			return nil, fmt.Errorf("%w: truncated object id at offset %d", ErrInvalidTree, i)
+		}
+
+		oid, err := objectFormat.FromBytes(body[i:idEnd])
+		if err != nil {
+			return nil, fmt.Errorf("%w: object id at offset %d: %w", ErrInvalidTree, i, err)
+		}
+
+		i = idEnd
+
+		entry := Entry{Mode: entryMode, Name: name, ID: oid}
+
+		if len(tree.entries) > 0 {
+			prev := tree.entries[len(tree.entries)-1]
+			if nameCompare(prev.Name, prev.Mode == mode.Directory, entry.Name, entryMode == mode.Directory) >= 0 {
+				return nil, fmt.Errorf("%w: entry %q out of order or duplicated", ErrInvalidTree, entry.Name)
+			}
+		}
+
+		tree.entries = append(tree.entries, entry)
+	}
+
+	return tree, nil
+}
diff --git a/object/tree/tree.go b/object/tree/tree.go
new file mode 100644
index 00000000..431df649
--- /dev/null
+++ b/object/tree/tree.go
@@ -0,0 +1,35 @@
+package tree
+
+import (
+	"slices"
+
+	"lindenii.org/go/furgit/object/id"
+	"lindenii.org/go/furgit/object/tree/mode"
+)
+
+// Tree represents a fully materialized Git tree object.
+//
+// The zero value is an empty tree.
+// Entries are stored sorted by Git tree ordering and are duplicate-free;
+// use [Tree.Insert] to add entries and [Tree.Entries] to read them.
+//
+// Labels: MT-Unsafe.
+type Tree struct {
+	entries []Entry
+}
+
+// Entry represents a single entry in a tree.
+type Entry struct {
+	Mode mode.Mode
+	Name string
+	ID   id.ObjectID
+}
+
+// Entries returns a copy of the tree's entries in Git tree order.
+//
+// Mutating the returned slice does not affect the tree.
+//
+// Labels: Life-Independent.
+func (tree *Tree) Entries() []Entry {
+	return slices.Clone(tree.entries)
+}
diff --git a/object/tree/type.go b/object/tree/type.go
new file mode 100644
index 00000000..125e0bcc
--- /dev/null
+++ b/object/tree/type.go
@@ -0,0 +1,10 @@
+package tree
+
+import "lindenii.org/go/furgit/object/typ"
+
+// ObjectType returns TypeTree.
+func (tree *Tree) ObjectType() typ.Type {
+	_ = tree
+
+	return typ.TypeTree
+}