1 files changed, 47 insertions, 5 deletions

diff --git a/object/tree/parse.go b/object/tree/parse.go
index 5b01fa05..bd6ed3b0 100644
--- a/object/tree/parse.go
+++ b/object/tree/parse.go
@@ -14,10 +14,22 @@ import (
 // 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).
+//
+// The returned tree aliases body:
+// each entry's Name shares body's backing array.
+// The tree inherits body's lifetime
+// and must not be mutated unless body may be.
+// Use [Tree.Clone] for an independent copy.
+//
+// Labels: Life-Parent, Mut-No.
 func Parse(body []byte, objectFormat id.ObjectFormat) (*Tree, error) {
 	tree := new(Tree)
 	idSize := objectFormat.Size()
-	seen := make(map[string]struct{})
+
+	const minEntryOverhead = 5 + 1 + 1 + 1 // mode, space, name, NUL
+	if estimate := len(body) / (minEntryOverhead + idSize); estimate > 0 {
+		tree.entries = make([]Entry, 0, estimate)
+	}
 
 	i := 0
 	for i < len(body) {
@@ -38,7 +50,7 @@ func Parse(body []byte, objectFormat id.ObjectFormat) (*Tree, error) {
 			return nil, fmt.Errorf("%w: missing name terminator at offset %d", ErrInvalidTree, i)
 		}
 
-		name := string(body[i : i+nul])
+		name := body[i : i+nul]
 		i += nul + 1
 
 		err = validateName(name)
@@ -67,14 +79,44 @@ func Parse(body []byte, objectFormat id.ObjectFormat) (*Tree, error) {
 			}
 		}
 
-		if _, dup := seen[entry.Name]; dup {
+		if entryMode == mode.Directory && hasNonDirNamed(tree.entries, entry.Name) {
 			return nil, fmt.Errorf("%w: duplicate entry name %q", ErrInvalidTree, entry.Name)
 		}
 
-		seen[entry.Name] = struct{}{}
-
 		tree.entries = append(tree.entries, entry)
 	}
 
 	return tree, nil
 }
+
+// hasNonDirNamed reports whether entries, sorted in Git tree order,
+// holds a non-directory entry whose name equals name.
+//
+// The match sorts immediately below a directory of the same name,
+// so the search gallops from the back before binary searching the bracket.
+func hasNonDirNamed(entries []Entry, name []byte) bool {
+	lo, hi := 0, len(entries)
+
+	for stride := 1; stride < hi-lo; stride *= 2 {
+		mid := hi - stride
+		if nameCompare(entries[mid].Name, entries[mid].Mode == mode.Directory, name, false) < 0 {
+			lo = mid + 1
+
+			break
+		}
+
+		hi = mid
+	}
+
+	for lo < hi {
+		mid := lo + (hi-lo)/2
+		if nameCompare(entries[mid].Name, entries[mid].Mode == mode.Directory, name, false) < 0 {
+			lo = mid + 1
+		} else {
+			hi = mid
+		}
+	}
+
+	return lo < len(entries) &&
+		nameCompare(entries[lo].Name, entries[lo].Mode == mode.Directory, name, false) == 0
+}