Merge branch 'jc/tree-improvements' into 'master'

localrepo: Refactor and improvements to tree functions

See merge request https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5642

Merged-by: Justin Tobler <jtobler@gitlab.com>
Approved-by: Justin Tobler <jtobler@gitlab.com>
Reviewed-by: Patrick Steinhardt <psteinhardt@gitlab.com>
Reviewed-by: karthik nayak <knayak@gitlab.com>
Co-authored-by: John Cai <jcai@gitlab.com>

10 files changed, 1295 insertions, 365 deletions

diff --git a/internal/git/localrepo/commit_test.go b/internal/git/localrepo/commit_test.go
index c089c1db7..17d3cae8c 100644
--- a/internal/git/localrepo/commit_test.go
+++ b/internal/git/localrepo/commit_test.go
@@ -32,13 +32,23 @@ func TestWriteCommit(t *testing.T) {
 	require.NoError(t, err)
 
 	treeEntryA := TreeEntry{Path: "file", Mode: "100644", OID: blobID}
-	treeA, err := repo.WriteTree(ctx, []TreeEntry{treeEntryA})
-	require.NoError(t, err)
+	treeA := &TreeEntry{
+		Type:    Tree,
+		Mode:    "040000",
+		Entries: []*TreeEntry{&treeEntryA},
+	}
+	require.NoError(t, treeA.Write(
+		ctx,
+		repo))
 
-	treeB, err := repo.WriteTree(ctx, []TreeEntry{
-		{Path: "file", Mode: "100644", OID: changedBlobID},
-	})
-	require.NoError(t, err)
+	treeB := &TreeEntry{
+		Type: Tree,
+		Mode: "040000",
+		Entries: []*TreeEntry{
+			{Path: "file", Mode: "100644", OID: changedBlobID},
+		},
+	}
+	require.NoError(t, treeB.Write(ctx, repo))
 	commitA, err := repo.WriteCommit(
 		ctx,
 		WriteCommitConfig{
@@ -47,7 +57,7 @@ func TestWriteCommit(t *testing.T) {
 			CommitterName:  "Tazmanian Devil",
 			CommitterEmail: "taz@devils.org",
 			Message:        "I ❤️  Tazmania",
-			TreeID:         treeA,
+			TreeID:         treeA.OID,
 		},
 	)
 	require.NoError(t, err)
@@ -59,7 +69,7 @@ func TestWriteCommit(t *testing.T) {
 			CommitterName:  "Daffy Duck",
 			CommitterEmail: "daffy@ducks.org",
 			Message:        "Big beak",
-			TreeID:         treeB,
+			TreeID:         treeB.OID,
 		},
 	)
 	require.NoError(t, err)
@@ -80,7 +90,7 @@ func TestWriteCommit(t *testing.T) {
 		{
 			desc: "with commit message",
 			cfg: WriteCommitConfig{
-				TreeID:         treeA,
+				TreeID:         treeA.OID,
 				AuthorName:     "Scrooge Mcduck",
 				AuthorEmail:    "chief@ducks.org",
 				CommitterName:  "Mickey Mouse",
@@ -90,7 +100,7 @@ func TestWriteCommit(t *testing.T) {
 				Message:        "my custom message\n\ntrailer\n",
 			},
 			expectedCommit: strings.Join([]string{
-				"tree " + string(treeA),
+				"tree " + string(treeA.OID),
 				fmt.Sprintf(
 					"author Scrooge Mcduck <chief@ducks.org> %d %s",
 					commitDate.Unix(),
@@ -110,7 +120,7 @@ func TestWriteCommit(t *testing.T) {
 		{
 			desc: "with multiple parents",
 			cfg: WriteCommitConfig{
-				TreeID:         treeA,
+				TreeID:         treeA.OID,
 				Parents:        []git.ObjectID{commitA, commitB},
 				AuthorName:     "Scrooge Mcduck",
 				AuthorEmail:    "chief@ducks.org",
@@ -121,7 +131,7 @@ func TestWriteCommit(t *testing.T) {
 				Message:        "my custom message",
 			},
 			expectedCommit: strings.Join([]string{
-				"tree " + treeA.String(),
+				"tree " + treeA.OID.String(),
 				"parent " + commitA.String(),
 				"parent " + commitB.String(),
 				fmt.Sprintf(
@@ -141,7 +151,7 @@ func TestWriteCommit(t *testing.T) {
 		{
 			desc: "with reference",
 			cfg: WriteCommitConfig{
-				TreeID:         treeA,
+				TreeID:         treeA.OID,
 				Parents:        []git.ObjectID{commitA, commitB},
 				AuthorName:     "Scrooge Mcduck",
 				AuthorEmail:    "chief@ducks.org",
@@ -153,7 +163,7 @@ func TestWriteCommit(t *testing.T) {
 				Reference:      "refs/heads/foo",
 			},
 			expectedCommit: strings.Join([]string{
-				"tree " + treeA.String(),
+				"tree " + treeA.OID.String(),
 				"parent " + commitA.String(),
 				"parent " + commitB.String(),
 				fmt.Sprintf(
@@ -203,14 +213,19 @@ func TestWriteCommit_validation(t *testing.T) {
 
 	blobID, err := repo.WriteBlob(ctx, "", strings.NewReader("foo"))
 	require.NoError(t, err)
-	treeID, err := repo.WriteTree(ctx, []TreeEntry{
-		{
-			OID:  blobID,
-			Mode: "100644",
-			Path: "file1",
+	tree := &TreeEntry{
+		Type: Tree,
+		Mode: "040000",
+		Entries: []*TreeEntry{
+			{
+				OID:  blobID,
+				Mode: "100644",
+				Path: "file1",
+			},
 		},
-	})
-	require.NoError(t, err)
+	}
+	require.NoError(t, tree.Write(ctx, repo))
+	treeID := tree.OID
 
 	testCases := []struct {
 		desc        string
diff --git a/internal/git/localrepo/list_entries.go b/internal/git/localrepo/list_entries.go
deleted file mode 100644
index e5a0115a6..000000000
--- a/internal/git/localrepo/list_entries.go
+++ /dev/null
@@ -1,98 +0,0 @@
-package localrepo
-
-import (
-	"bytes"
-	"context"
-	"errors"
-	"fmt"
-	"io"
-	"strings"
-
-	"gitlab.com/gitlab-org/gitaly/v15/internal/git"
-)
-
-var (
-	// ErrNotExist indicates that the requested tree does not exist, either because the revision
-	// is invalid or because the path is not valid.
-	ErrNotExist = errors.New("invalid object name")
-	// ErrNotTreeish indicates that the requested revision or path does not resolve to a tree
-	// object.
-	ErrNotTreeish = errors.New("not treeish")
-)
-
-// ListEntriesConfig is configuration that can be passed to ListEntries.
-type ListEntriesConfig struct {
-	// Recursive indicates whether the listing shall be recursive or not.
-	Recursive bool
-	// RelativePath is the relative path at which listing of entries should be started.
-	RelativePath string
-}
-
-// ListEntries lists tree entries for the given treeish. By default, this will do a non-recursive
-// listing starting from the root of the given treeish. This behaviour can be changed by passing a
-// config.
-func (repo *Repo) ListEntries(
-	ctx context.Context,
-	treeish git.Revision,
-	cfg *ListEntriesConfig,
-) ([]*TreeEntry, error) {
-	if cfg == nil {
-		cfg = &ListEntriesConfig{}
-	}
-
-	flags := []git.Option{git.Flag{Name: "-z"}}
-	if cfg.Recursive {
-		flags = append(flags,
-			git.Flag{Name: "-r"},
-			git.Flag{Name: "-t"},
-		)
-	}
-
-	relativePath := cfg.RelativePath
-	if relativePath == "." {
-		relativePath = ""
-	}
-
-	var stderr bytes.Buffer
-	cmd, err := repo.Exec(ctx, git.Command{
-		Name:  "ls-tree",
-		Args:  []string{fmt.Sprintf("%s:%s", treeish, relativePath)},
-		Flags: flags,
-	}, git.WithStderr(&stderr))
-	if err != nil {
-		return nil, fmt.Errorf("spawning git-ls-tree: %w", err)
-	}
-
-	objectHash, err := repo.ObjectHash(ctx)
-	if err != nil {
-		return nil, fmt.Errorf("detecting object hash: %w", err)
-	}
-
-	parser := NewParser(cmd, objectHash)
-	var entries []*TreeEntry
-	for {
-		entry, err := parser.NextEntry()
-		if err != nil {
-			if errors.Is(err, io.EOF) {
-				break
-			}
-
-			return nil, fmt.Errorf("parsing tree entry: %w", err)
-		}
-
-		entries = append(entries, entry)
-	}
-
-	if err := cmd.Wait(); err != nil {
-		errorMessage := stderr.String()
-		if strings.HasPrefix(errorMessage, "fatal: not a tree object") {
-			return nil, ErrNotTreeish
-		} else if strings.HasPrefix(errorMessage, "fatal: Not a valid object name") {
-			return nil, ErrNotExist
-		}
-
-		return nil, fmt.Errorf("waiting for git-ls-tree: %w, stderr: %q", err, errorMessage)
-	}
-
-	return entries, nil
-}
diff --git a/internal/git/localrepo/list_entries_test.go b/internal/git/localrepo/list_entries_test.go
deleted file mode 100644
index 0c9c03efa..000000000
--- a/internal/git/localrepo/list_entries_test.go
+++ /dev/null
@@ -1,159 +0,0 @@
-package localrepo
-
-import (
-	"testing"
-
-	"github.com/stretchr/testify/require"
-	"gitlab.com/gitlab-org/gitaly/v15/internal/git"
-	"gitlab.com/gitlab-org/gitaly/v15/internal/git/gittest"
-	"gitlab.com/gitlab-org/gitaly/v15/internal/testhelper"
-	"gitlab.com/gitlab-org/gitaly/v15/internal/testhelper/testcfg"
-)
-
-func TestListEntries(t *testing.T) {
-	t.Parallel()
-
-	cfg := testcfg.Build(t)
-	ctx := testhelper.Context(t)
-
-	repoProto, repoPath := gittest.CreateRepository(t, ctx, cfg, gittest.CreateRepositoryConfig{
-		SkipCreationViaService: true,
-	})
-	repo := NewTestRepo(t, cfg, repoProto)
-
-	blobID := gittest.WriteBlob(t, cfg, repoPath, []byte("blob contents"))
-	emptyTreeID := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{})
-	treeWithBlob := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
-		{OID: blobID, Mode: "100644", Path: "nonexecutable"},
-		{OID: blobID, Mode: "100755", Path: "executable"},
-	})
-	treeWithSubtree := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
-		{OID: emptyTreeID, Mode: "040000", Path: "subdir"},
-	})
-	treeWithNestedSubtrees := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
-		{OID: treeWithSubtree, Mode: "040000", Path: "nested-subdir"},
-	})
-	treeWithSubtreeAndBlob := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
-		{OID: treeWithSubtree, Mode: "040000", Path: "subdir"},
-		{OID: blobID, Mode: "100644", Path: "blob"},
-	})
-	treeWithSubtreeContainingBlob := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
-		{OID: treeWithSubtreeAndBlob, Mode: "040000", Path: "subdir"},
-	})
-
-	for _, tc := range []struct {
-		desc            string
-		treeish         git.Revision
-		cfg             *ListEntriesConfig
-		expectedResults []*TreeEntry
-		expectedErr     error
-	}{
-		{
-			desc:    "empty tree",
-			treeish: emptyTreeID.Revision(),
-		},
-		{
-			desc:    "tree with blob",
-			treeish: treeWithBlob.Revision(),
-			expectedResults: []*TreeEntry{
-				{Mode: "100755", Type: Blob, OID: blobID, Path: "executable"},
-				{Mode: "100644", Type: Blob, OID: blobID, Path: "nonexecutable"},
-			},
-		},
-		{
-			desc:    "tree with subtree",
-			treeish: treeWithSubtree.Revision(),
-			expectedResults: []*TreeEntry{
-				{Mode: "040000", Type: Tree, OID: emptyTreeID, Path: "subdir"},
-			},
-		},
-		{
-			desc:    "nested trees",
-			treeish: treeWithNestedSubtrees.Revision(),
-			expectedResults: []*TreeEntry{
-				{Mode: "040000", Type: Tree, OID: treeWithSubtree, Path: "nested-subdir"},
-			},
-		},
-		{
-			desc:    "recursive nested trees",
-			treeish: treeWithNestedSubtrees.Revision(),
-			cfg: &ListEntriesConfig{
-				Recursive: true,
-			},
-			expectedResults: []*TreeEntry{
-				{Mode: "040000", Type: Tree, OID: treeWithSubtree, Path: "nested-subdir"},
-				{Mode: "040000", Type: Tree, OID: emptyTreeID, Path: "nested-subdir/subdir"},
-			},
-		},
-		{
-			desc:    "nested subtree",
-			treeish: treeWithNestedSubtrees.Revision(),
-			cfg: &ListEntriesConfig{
-				RelativePath: "nested-subdir",
-			},
-			expectedResults: []*TreeEntry{
-				{Mode: "040000", Type: Tree, OID: emptyTreeID, Path: "subdir"},
-			},
-		},
-		{
-			desc:    "nested recursive subtree",
-			treeish: treeWithSubtreeContainingBlob.Revision(),
-			cfg: &ListEntriesConfig{
-				RelativePath: "subdir",
-				Recursive:    true,
-			},
-			expectedResults: []*TreeEntry{
-				{Mode: "100644", Type: Blob, OID: blobID, Path: "blob"},
-				{Mode: "040000", Type: Tree, OID: treeWithSubtree, Path: "subdir"},
-				{Mode: "040000", Type: Tree, OID: emptyTreeID, Path: "subdir/subdir"},
-			},
-		},
-		{
-			desc:    "recursive nested trees and blobs",
-			treeish: treeWithSubtreeAndBlob.Revision(),
-			cfg: &ListEntriesConfig{
-				Recursive: true,
-			},
-			expectedResults: []*TreeEntry{
-				{Mode: "100644", Type: Blob, OID: blobID, Path: "blob"},
-				{Mode: "040000", Type: Tree, OID: treeWithSubtree, Path: "subdir"},
-				{Mode: "040000", Type: Tree, OID: emptyTreeID, Path: "subdir/subdir"},
-			},
-		},
-		{
-			desc:    "listing blob fails",
-			treeish: blobID.Revision(),
-			// We get a NotExist error here because it's invalid to suffix an object ID
-			// which resolves to a blob with a colon (":") given that it's not possible
-			// to resolve a subpath.
-			expectedErr: ErrNotExist,
-		},
-		{
-			desc:    "valid revision with invalid path",
-			treeish: treeWithSubtree.Revision(),
-			cfg: &ListEntriesConfig{
-				RelativePath: "does-not-exist",
-			},
-			expectedErr: ErrNotExist,
-		},
-		{
-			desc:    "valid revision with path pointing to blob",
-			treeish: treeWithSubtreeAndBlob.Revision(),
-			cfg: &ListEntriesConfig{
-				RelativePath: "blob",
-			},
-			expectedErr: ErrNotTreeish,
-		},
-		{
-			desc:        "listing nonexistent object fails",
-			treeish:     "does-not-exist",
-			expectedErr: ErrNotExist,
-		},
-	} {
-		t.Run(tc.desc, func(t *testing.T) {
-			results, err := repo.ListEntries(ctx, tc.treeish, tc.cfg)
-			require.Equal(t, tc.expectedErr, err)
-			require.Equal(t, tc.expectedResults, results)
-		})
-	}
-}
diff --git a/internal/git/localrepo/objects.go b/internal/git/localrepo/objects.go
index c9fb2345b..7586886af 100644
--- a/internal/git/localrepo/objects.go
+++ b/internal/git/localrepo/objects.go
@@ -185,6 +185,25 @@ type InvalidObjectError string
 
 func (err InvalidObjectError) Error() string { return fmt.Sprintf("invalid object %q", string(err)) }
 
+// ReadObjectInfo attempts to read the object info based on a revision.
+func (repo *Repo) ReadObjectInfo(ctx context.Context, rev git.Revision) (*catfile.ObjectInfo, error) {
+	infoReader, cleanup, err := repo.catfileCache.ObjectInfoReader(ctx, repo)
+	if err != nil {
+		return nil, fmt.Errorf("getting object info reader: %w", err)
+	}
+	defer cleanup()
+
+	objectInfo, err := infoReader.Info(ctx, rev)
+	if err != nil {
+		if catfile.IsNotFound(err) {
+			return nil, InvalidObjectError(rev)
+		}
+		return nil, fmt.Errorf("getting object info %w", err)
+	}
+
+	return objectInfo, nil
+}
+
 // ReadObject reads an object from the repository's object database. InvalidObjectError
 // is returned if the oid does not refer to a valid object.
 func (repo *Repo) ReadObject(ctx context.Context, oid git.ObjectID) ([]byte, error) {
diff --git a/internal/git/localrepo/objects_test.go b/internal/git/localrepo/objects_test.go
index c57c66c1b..107ab1f92 100644
--- a/internal/git/localrepo/objects_test.go
+++ b/internal/git/localrepo/objects_test.go
@@ -280,6 +280,49 @@ func testRepoReadObject(t *testing.T, ctx context.Context) {
 	}
 }
 
+func TestRepoReadObjectInfo(t *testing.T) {
+	t.Parallel()
+
+	ctx := testhelper.Context(t)
+	cfg, repo, repoPath := setupRepo(t)
+	blobID := gittest.WriteBlob(t, cfg, repoPath, []byte("content"))
+	objectHash, err := repo.ObjectHash(ctx)
+	require.NoError(t, err)
+
+	for _, tc := range []struct {
+		desc               string
+		oid                git.ObjectID
+		content            string
+		expectedErr        error
+		expectedObjectInfo catfile.ObjectInfo
+	}{
+		{
+			desc:        "missing object",
+			oid:         git.ObjectID("abcdefg"),
+			expectedErr: InvalidObjectError("abcdefg"),
+		},
+		{
+			desc:    "valid object",
+			oid:     blobID,
+			content: "content",
+			expectedObjectInfo: catfile.ObjectInfo{
+				Oid:    blobID,
+				Type:   "blob",
+				Size:   7,
+				Format: objectHash.Format,
+			},
+		},
+	} {
+		t.Run(tc.desc, func(t *testing.T) {
+			info, err := repo.ReadObjectInfo(ctx, git.Revision(tc.oid))
+			require.Equal(t, tc.expectedErr, err)
+			if tc.expectedErr == nil {
+				require.Equal(t, tc.expectedObjectInfo, *info)
+			}
+		})
+	}
+}
+
 func TestRepo_ReadObject_catfileCount(t *testing.T) {
 	t.Parallel()
 
diff --git a/internal/git/localrepo/tree.go b/internal/git/localrepo/tree.go
index cfb1e722d..3d6d5f5f8 100644
--- a/internal/git/localrepo/tree.go
+++ b/internal/git/localrepo/tree.go
@@ -3,10 +3,16 @@ package localrepo
 import (
 	"bytes"
 	"context"
+	"errors"
 	"fmt"
+	"io"
+	"path/filepath"
+	"sort"
+	"strings"
 
 	"gitlab.com/gitlab-org/gitaly/v15/internal/git"
 	"gitlab.com/gitlab-org/gitaly/v15/internal/helper/text"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/structerr"
 )
 
 // ObjectType is an Enum for the type of object of
@@ -37,6 +43,33 @@ func (e Entries) Less(i, j int) bool {
 	return e[i].Type < e[j].Type
 }
 
+// TreeEntriesByPath allows a slice of *TreeEntry to be sorted by Path
+type TreeEntriesByPath []*TreeEntry
+
+func (b TreeEntriesByPath) Len() int {
+	return len(b)
+}
+
+func (b TreeEntriesByPath) Swap(i, j int) {
+	b[i], b[j] = b[j], b[i]
+}
+
+func (b TreeEntriesByPath) Less(i, j int) bool {
+	iPath, jPath := b[i].Path, b[j].Path
+
+	// git has an edge case for subtrees where they are always appended with
+	// a '/'. See https://github.com/git/git/blob/v2.40.0/read-cache.c#L491
+	if b[i].Type == Tree {
+		iPath += "/"
+	}
+
+	if b[j].Type == Tree {
+		jPath += "/"
+	}
+
+	return iPath < jPath
+}
+
 // ToEnum translates a string representation of the object type into an
 // ObjectType enum.
 func ToEnum(s string) ObjectType {
@@ -52,19 +85,6 @@ func ToEnum(s string) ObjectType {
 	}
 }
 
-func fromEnum(t ObjectType) string {
-	switch t {
-	case Tree:
-		return "tree"
-	case Blob:
-		return "blob"
-	case Submodule:
-		return "commit"
-	default:
-		return "unknown"
-	}
-}
-
 // TreeEntry represents an entry of a git tree object.
 type TreeEntry struct {
 	// OID is the object ID the tree entry refers to.
@@ -75,6 +95,8 @@ type TreeEntry struct {
 	Path string
 	// Type is the type of the tree entry.
 	Type ObjectType
+	// Entries is a slice of this tree's entries.
+	Entries []*TreeEntry
 }
 
 // IsBlob returns whether or not the TreeEntry is a blob.
@@ -82,52 +104,268 @@ func (t *TreeEntry) IsBlob() bool {
 	return t.Type == Blob
 }
 
-// WriteTree writes a new tree object to the given path. This function does not verify whether OIDs
-// referred to by tree entries actually exist in the repository.
-func (repo *Repo) WriteTree(ctx context.Context, entries []TreeEntry) (git.ObjectID, error) {
-	var tree bytes.Buffer
+var (
+	// ErrTreeNotExist indicates that the requested tree does not exist, either because the revision
+	// is invalid or because the path is not valid.
+	ErrTreeNotExist = errors.New("invalid object name")
+	// ErrNotTreeish indicates that the requested revision or path does not resolve to a tree
+	// object.
+	ErrNotTreeish = errors.New("not treeish")
+)
+
+// listEntries lists tree entries for the given treeish.
+func (repo *Repo) listEntries(
+	ctx context.Context,
+	treeish git.Revision,
+	relativePath string,
+	recursive bool,
+) ([]*TreeEntry, error) {
+	flags := []git.Option{git.Flag{Name: "-z"}}
+	if recursive {
+		flags = append(flags,
+			git.Flag{Name: "-r"},
+			git.Flag{Name: "-t"},
+		)
+	}
+
+	if relativePath == "." {
+		relativePath = ""
+	}
+
+	var stderr bytes.Buffer
+	cmd, err := repo.Exec(ctx, git.Command{
+		Name:  "ls-tree",
+		Args:  []string{fmt.Sprintf("%s:%s", treeish, relativePath)},
+		Flags: flags,
+	}, git.WithStderr(&stderr))
+	if err != nil {
+		return nil, fmt.Errorf("spawning git-ls-tree: %w", err)
+	}
+
+	objectHash, err := repo.ObjectHash(ctx)
+	if err != nil {
+		return nil, fmt.Errorf("detecting object hash: %w", err)
+	}
+
+	parser := NewParser(cmd, objectHash)
+	var entries []*TreeEntry
+	for {
+		entry, err := parser.NextEntry()
+		if err != nil {
+			if errors.Is(err, io.EOF) {
+				break
+			}
+
+			return nil, fmt.Errorf("parsing tree entry: %w", err)
+		}
+
+		entries = append(entries, entry)
+	}
+
+	if err := cmd.Wait(); err != nil {
+		errorMessage := stderr.String()
+		if strings.HasPrefix(errorMessage, "fatal: not a tree object") {
+			return nil, ErrNotTreeish
+		} else if strings.HasPrefix(errorMessage, "fatal: Not a valid object name") {
+			return nil, ErrTreeNotExist
+		}
+
+		return nil, structerr.New("waiting for git-ls-tree: %w", err).WithMetadata("stderr", errorMessage)
+	}
+
+	return entries, nil
+}
+
+// depthByPath must be called only on cleaned paths
+func depthByPath(path string) int {
+	return strings.Count(path, "/") + 1
+}
+
+// treeStack is a stack data structure used by walk() to do a breadth-first walk
+// of the outputof ls-tree -r.
+type treeStack []*TreeEntry
+
+func (t treeStack) peek() *TreeEntry {
+	if len(t) == 0 {
+		return nil
+	}
+
+	return t[len(t)-1]
+}
+
+func (t *treeStack) push(e *TreeEntry) {
+	*t = append(*t, e)
+}
+
+func (t *treeStack) pop() *TreeEntry {
+	e := t.peek()
+	if e == nil {
+		return nil
+	}
+
+	*t = (*t)[:len(*t)-1]
+
+	return e
+}
+
+// populate scans through the output of ls-tree -r, and constructs a TreeEntry
+// object.
+func (t *TreeEntry) populate(
+	ctx context.Context,
+	repo *Repo,
+) error {
+	if t.OID == "" {
+		return errors.New("oid is empty")
+	}
+
+	t.Entries = nil
+
+	entries, err := repo.listEntries(
+		ctx,
+		git.Revision(t.OID),
+		"",
+		true,
+	)
+	if err != nil {
+		return err
+	}
+
+	stack := treeStack{t}
+
+	// The outpout of ls-tree -r is the following:
+	// a1
+	// dir1/file2
+	// dir2/file3
+	// f2
+	// f3
+	// Whenever we see a tree, push it onto the stack since we will need to
+	// start adding to that tree's entries.
+	// When we encounter an entry that has a lower depth than the previous
+	// entry, we know that we need to pop the tree entry off to get back to the
+	// parent tree.
 	for _, entry := range entries {
-		entryType := entry.Type
-
-		if entryType == Unknown {
-			switch entry.Mode {
-			case "100644":
-				fallthrough
-			case "100755":
-				fallthrough
-			case "120000":
-				entryType = Blob
-			case "040000":
-				entryType = Tree
-			case "160000":
-				entryType = Submodule
+		if levelsToPop := len(stack) - depthByPath(entry.Path); levelsToPop > 0 {
+			for i := 0; i < levelsToPop; i++ {
+				stack.pop()
+			}
+		}
+
+		entry.Path = filepath.Base(entry.Path)
+		stack.peek().Entries = append(
+			stack.peek().Entries,
+			entry,
+		)
+
+		if entry.Type == Tree {
+			stack.push(entry)
+		}
+	}
+
+	if err != nil {
+		return fmt.Errorf("listing entries: %w", err)
+	}
+
+	return nil
+}
+
+func (t *TreeEntry) walk(dirPath string, callback func(path string, entry *TreeEntry) error) error {
+	nextDirPath := filepath.Join(dirPath, t.Path)
+	if err := callback(dirPath, t); err != nil {
+		return err
+	}
+
+	for _, entry := range t.Entries {
+		if err := entry.walk(nextDirPath, callback); err != nil {
+			return err
+		}
+	}
+
+	return nil
+}
+
+// Walk will walk the whole tree structure and call callback on every entry of
+// the tree in a depth-first like fashion.
+func (t *TreeEntry) Walk(callback func(path string, entry *TreeEntry) error) error {
+	for _, e := range t.Entries {
+		if err := e.walk(t.Path, callback); err != nil {
+			return err
+		}
+	}
+
+	return nil
+}
+
+// Write does a depth first walk, writing new trees when the OID of the
+// TreeEntry is empty.
+func (t *TreeEntry) Write(
+	ctx context.Context,
+	repo *Repo,
+) error {
+	var err error
+
+	if t.OID != "" {
+		return nil
+	}
+
+	for _, e := range t.Entries {
+		if e.Type == Tree && e.OID == "" {
+			if err := e.Write(ctx, repo); err != nil {
+				return err
 			}
 		}
+	}
 
-		oid := entry.OID
+	treeOID, err := repo.writeEntries(ctx, t.Entries)
+	if err != nil {
+		return fmt.Errorf("writing tree: %w", err)
+	}
+
+	t.OID = treeOID
+	return nil
+}
+
+// writeTreeEntries writes a new tree object from a slice of entries. This function does not verify whether OIDs
+// referred to by tree entries actually exist in the repository.
+func (repo *Repo) writeEntries(ctx context.Context, entries []*TreeEntry) (git.ObjectID, error) {
+	var tree bytes.Buffer
+
+	sort.Stable(TreeEntriesByPath(entries))
+
+	for _, entry := range entries {
+		mode := strings.TrimPrefix(entry.Mode, "0")
+		formattedEntry := fmt.Sprintf("%s %s\000", mode, entry.Path)
+
+		oidBytes, err := entry.OID.Bytes()
+		if err != nil {
+			return "", err
+		}
 
-		formattedEntry := fmt.Sprintf("%s %s %s\t%s\000", entry.Mode, fromEnum(entryType), oid.String(), entry.Path)
 		if _, err := tree.WriteString(formattedEntry); err != nil {
 			return "", err
 		}
+
+		if _, err := tree.Write(oidBytes); err != nil {
+			return "", err
+		}
 	}
 
 	options := []git.Option{
-		git.Flag{Name: "-z"},
-		git.Flag{Name: "--missing"},
+		git.ValueFlag{Name: "-t", Value: "tree"},
+		git.Flag{Name: "-w"},
+		git.Flag{Name: "--stdin"},
 	}
 
 	var stdout, stderr bytes.Buffer
 	if err := repo.ExecAndWait(ctx,
 		git.Command{
-			Name:  "mktree",
+			Name:  "hash-object",
 			Flags: options,
 		},
 		git.WithStdout(&stdout),
 		git.WithStderr(&stderr),
 		git.WithStdin(&tree),
 	); err != nil {
-		return "", err
+		return "", structerr.New("%w", err).WithMetadata("stderr", stderr.String())
 	}
 
 	objectHash, err := repo.ObjectHash(ctx)
@@ -142,3 +380,71 @@ func (repo *Repo) WriteTree(ctx context.Context, entries []TreeEntry) (git.Objec
 
 	return treeOID, nil
 }
+
+// readTreeConfig is configuration that can be passed to ReadTree.
+type readTreeConfig struct {
+	recursive bool
+	// relativePath is the relative path at which listing of entries should be started.
+	relativePath string
+}
+
+// ReadTreeOption is an option that modifies the behavior of ReadTree()
+type ReadTreeOption func(c *readTreeConfig)
+
+// WithRecursive returns all entries recursively, but "flattened" in the sense
+// that all subtrees and their entries get returned as Entries, each entry with
+// its full path.
+func WithRecursive() ReadTreeOption {
+	return func(c *readTreeConfig) {
+		c.recursive = true
+	}
+}
+
+// WithRelativePath will cause ReadTree to return a tree at the relative path.
+func WithRelativePath(relativePath string) ReadTreeOption {
+	return func(c *readTreeConfig) {
+		c.relativePath = relativePath
+	}
+}
+
+// ReadTree gets a tree object with all of the direct children populated.
+// Walk can be called to populate every level of the tree.
+func (repo *Repo) ReadTree(ctx context.Context, treeish git.Revision, options ...ReadTreeOption) (*TreeEntry, error) {
+	var c readTreeConfig
+
+	for _, opt := range options {
+		opt(&c)
+	}
+
+	if c.relativePath == "." {
+		c.relativePath = ""
+	}
+
+	treeOID, err := repo.ResolveRevision(ctx, git.Revision(string(treeish)+":"+c.relativePath))
+	if err != nil {
+		return nil, fmt.Errorf("getting revision: %w", err)
+	}
+
+	rootEntry := &TreeEntry{
+		OID:  treeOID,
+		Type: Tree,
+		Mode: "040000",
+	}
+
+	if c.recursive {
+		if err := rootEntry.populate(ctx, repo); err != nil {
+			return nil, err
+		}
+	} else {
+		if rootEntry.Entries, err = repo.listEntries(
+			ctx,
+			treeish,
+			c.relativePath,
+			c.recursive,
+		); err != nil {
+			return nil, fmt.Errorf("listEntries: %w", err)
+		}
+	}
+
+	return rootEntry, nil
+}
diff --git a/internal/git/localrepo/tree_test.go b/internal/git/localrepo/tree_test.go
index 2aac6d8ea..0b6fb330c 100644
--- a/internal/git/localrepo/tree_test.go
+++ b/internal/git/localrepo/tree_test.go
@@ -2,21 +2,29 @@ package localrepo
 
 import (
 	"bytes"
+	"context"
 	"os"
 	"path/filepath"
+	"sort"
+	"strings"
 	"testing"
 
 	"github.com/stretchr/testify/require"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/git"
 	"gitlab.com/gitlab-org/gitaly/v15/internal/git/gittest"
 	"gitlab.com/gitlab-org/gitaly/v15/internal/helper/text"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/structerr"
 	"gitlab.com/gitlab-org/gitaly/v15/internal/testhelper"
 	"gitlab.com/gitlab-org/gitaly/v15/internal/testhelper/testcfg"
 )
 
-func TestWriteTree(t *testing.T) {
+func TestTreeEntry_Write(t *testing.T) {
 	cfg := testcfg.Build(t)
 	ctx := testhelper.Context(t)
 
+	gitVersion, err := gittest.NewCommandFactory(t, cfg).GitVersion(ctx)
+	require.NoError(t, err)
+
 	repoProto, repoPath := gittest.CreateRepository(t, ctx, cfg, gittest.CreateRepositoryConfig{
 		SkipCreationViaService: true,
 	})
@@ -28,14 +36,19 @@ func TestWriteTree(t *testing.T) {
 	blobID, err := repo.WriteBlob(ctx, "file", bytes.NewBufferString("foobar\n"))
 	require.NoError(t, err)
 
-	treeID, err := repo.WriteTree(ctx, []TreeEntry{
-		{
-			OID:  blobID,
-			Mode: "100644",
-			Path: "file",
+	tree := &TreeEntry{
+		Type: Tree,
+		Mode: "040000",
+		Entries: []*TreeEntry{
+			{
+				OID:  blobID,
+				Mode: "100644",
+				Path: "file",
+			},
 		},
-	})
-	require.NoError(t, err)
+	}
+	require.NoError(t, tree.Write(ctx, repo))
+	treeID := tree.OID
 
 	nonExistentBlobID, err := repo.WriteBlob(ctx, "file1", bytes.NewBufferString("content"))
 	require.NoError(t, err)
@@ -44,13 +57,14 @@ func TestWriteTree(t *testing.T) {
 	require.NoError(t, os.Remove(nonExistentBlobPath))
 
 	for _, tc := range []struct {
-		desc            string
-		entries         []TreeEntry
-		expectedEntries []TreeEntry
+		desc              string
+		entries           []*TreeEntry
+		expectedEntries   []TreeEntry
+		expectedErrString string
 	}{
 		{
 			desc: "entry with blob OID",
-			entries: []TreeEntry{
+			entries: []*TreeEntry{
 				{
 					OID:  blobID,
 					Mode: "100644",
@@ -67,7 +81,7 @@ func TestWriteTree(t *testing.T) {
 		},
 		{
 			desc: "entry with tree OID",
-			entries: []TreeEntry{
+			entries: []*TreeEntry{
 				{
 					OID:  treeID,
 					Mode: "040000",
@@ -84,7 +98,7 @@ func TestWriteTree(t *testing.T) {
 		},
 		{
 			desc: "mixed tree and blob entries",
-			entries: []TreeEntry{
+			entries: []*TreeEntry{
 				{
 					OID:  treeID,
 					Mode: "040000",
@@ -121,7 +135,7 @@ func TestWriteTree(t *testing.T) {
 		},
 		{
 			desc: "entry with nonexistent object",
-			entries: []TreeEntry{
+			entries: []*TreeEntry{
 				{
 					OID:  nonExistentBlobID,
 					Mode: "100644",
@@ -136,12 +150,69 @@ func TestWriteTree(t *testing.T) {
 				},
 			},
 		},
+		{
+			desc: "entry with duplicate file",
+			entries: []*TreeEntry{
+				{
+					OID:  blobID,
+					Mode: "100644",
+					Path: "file",
+				},
+				{
+					OID:  nonExistentBlobID,
+					Mode: "100644",
+					Path: "file",
+				},
+			},
+			expectedErrString: "duplicateEntries: contains duplicate file entries",
+		},
+		{
+			desc: "entry with malformed mode",
+			entries: []*TreeEntry{
+				{
+					OID:  blobID,
+					Mode: "1006442",
+					Path: "file",
+				},
+			},
+			expectedErrString: "badFilemode: contains bad file modes",
+		},
+		{
+			desc: "tries to write .git file",
+			entries: []*TreeEntry{
+				{
+					OID:  blobID,
+					Mode: "040000",
+					Path: ".git",
+				},
+			},
+			expectedErrString: "hasDotgit: contains '.git'",
+		},
 	} {
 		tc := tc
 		t.Run(tc.desc, func(t *testing.T) {
 			t.Parallel()
+			tree := &TreeEntry{
+				Type:    Tree,
+				Mode:    "040000",
+				Entries: tc.entries,
+			}
+
+			err := tree.Write(ctx, repo)
+			oid := tree.OID
+			if tc.expectedErrString != "" {
+				if gitVersion.HashObjectFsck() {
+					switch e := err.(type) {
+					case structerr.Error:
+						stderr := e.Metadata()["stderr"].(string)
+						strings.Contains(stderr, tc.expectedErrString)
+					default:
+						strings.Contains(err.Error(), tc.expectedErrString)
+					}
+				}
+				return
+			}
 
-			oid, err := repo.WriteTree(ctx, tc.entries)
 			require.NoError(t, err)
 
 			output := text.ChompBytes(gittest.Exec(t, cfg, "-C", repoPath, "ls-tree", "-r", string(oid)))
@@ -179,3 +250,710 @@ func TestWriteTree(t *testing.T) {
 		})
 	}
 }
+
+func TestTreeEntryByPath(t *testing.T) {
+	t.Parallel()
+
+	testCases := []struct {
+		desc     string
+		input    []*TreeEntry
+		expected []*TreeEntry
+	}{
+		{
+			desc: "all blobs",
+			input: []*TreeEntry{
+				{
+					Type: Blob,
+					Path: "abc",
+				},
+				{
+					Type: Blob,
+					Path: "ab",
+				},
+				{
+					Type: Blob,
+					Path: "a",
+				},
+			},
+			expected: []*TreeEntry{
+				{
+					Type: Blob,
+					Path: "a",
+				},
+				{
+					Type: Blob,
+					Path: "ab",
+				},
+				{
+					Type: Blob,
+					Path: "abc",
+				},
+			},
+		},
+		{
+			desc: "blobs and trees",
+			input: []*TreeEntry{
+				{
+					Type: Blob,
+					Path: "abc",
+				},
+				{
+					Type: Tree,
+					Path: "ab",
+				},
+				{
+					Type: Blob,
+					Path: "a",
+				},
+			},
+			expected: []*TreeEntry{
+				{
+					Type: Blob,
+					Path: "a",
+				},
+				{
+					Type: Tree,
+					Path: "ab",
+				},
+				{
+					Type: Blob,
+					Path: "abc",
+				},
+			},
+		},
+		{
+			desc: "trees get sorted with / appended",
+			input: []*TreeEntry{
+				{
+					Type: Tree,
+					Path: "a",
+				},
+				{
+					Type: Blob,
+					Path: "a+",
+				},
+			},
+			expected: []*TreeEntry{
+				{
+					Type: Blob,
+					Path: "a+",
+				},
+				{
+					Type: Tree,
+					Path: "a",
+				},
+			},
+		},
+		{
+			desc: "blobs get sorted without / appended",
+			input: []*TreeEntry{
+				{
+					Type: Blob,
+					Path: "a",
+				},
+				{
+					Type: Blob,
+					Path: "a+",
+				},
+			},
+			expected: []*TreeEntry{
+				{
+					Type: Blob,
+					Path: "a",
+				},
+				{
+					Type: Blob,
+					Path: "a+",
+				},
+			},
+		},
+	}
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			sort.Stable(TreeEntriesByPath(tc.input))
+
+			require.Equal(
+				t,
+				tc.expected,
+				tc.input,
+			)
+		})
+	}
+}
+
+func TestReadTree(t *testing.T) {
+	t.Parallel()
+
+	cfg := testcfg.Build(t)
+	ctx := testhelper.Context(t)
+
+	repoProto, repoPath := gittest.CreateRepository(t, ctx, cfg, gittest.CreateRepositoryConfig{
+		SkipCreationViaService: true,
+	})
+	repo := NewTestRepo(t, cfg, repoProto)
+
+	blobID := gittest.WriteBlob(t, cfg, repoPath, []byte("blob contents"))
+	emptyTreeID := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{})
+	treeWithBlob := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
+		{OID: blobID, Mode: "100644", Path: "nonexecutable"},
+		{OID: blobID, Mode: "100755", Path: "executable"},
+	})
+	treeWithSubtree := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
+		{OID: emptyTreeID, Mode: "040000", Path: "subdir"},
+	})
+	treeWithNestedSubtrees := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
+		{OID: treeWithSubtree, Mode: "040000", Path: "nested-subdir"},
+	})
+	treeWithSubtreeAndBlob := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
+		{OID: treeWithSubtree, Mode: "040000", Path: "subdir"},
+		{OID: blobID, Mode: "100644", Path: "blob"},
+	})
+	treeWithSubtreeContainingBlob := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
+		{OID: treeWithSubtreeAndBlob, Mode: "040000", Path: "subdir"},
+	})
+
+	for _, tc := range []struct {
+		desc         string
+		treeish      git.Revision
+		options      []ReadTreeOption
+		cfg          *readTreeConfig
+		expectedTree TreeEntry
+		expectedErr  error
+	}{
+		{
+			desc:    "empty tree",
+			treeish: emptyTreeID.Revision(),
+			expectedTree: TreeEntry{
+				OID:  emptyTreeID,
+				Type: Tree,
+				Mode: "040000",
+			},
+		},
+		{
+			desc:    "tree with blob",
+			treeish: treeWithBlob.Revision(),
+			expectedTree: TreeEntry{
+				OID:  treeWithBlob,
+				Type: Tree,
+				Mode: "040000",
+				Entries: []*TreeEntry{
+					{Mode: "100755", Type: Blob, OID: blobID, Path: "executable"},
+					{Mode: "100644", Type: Blob, OID: blobID, Path: "nonexecutable"},
+				},
+			},
+		},
+		{
+			desc:    "tree with subtree",
+			treeish: treeWithSubtree.Revision(),
+			expectedTree: TreeEntry{
+				OID:  treeWithSubtree,
+				Type: Tree,
+				Mode: "040000",
+				Entries: []*TreeEntry{
+					{Mode: "040000", Type: Tree, OID: emptyTreeID, Path: "subdir"},
+				},
+			},
+		},
+		{
+			desc:    "nested trees",
+			treeish: treeWithNestedSubtrees.Revision(),
+			expectedTree: TreeEntry{
+				OID:  treeWithNestedSubtrees,
+				Type: Tree,
+				Mode: "040000",
+				Entries: []*TreeEntry{
+					{Mode: "040000", Type: Tree, OID: treeWithSubtree, Path: "nested-subdir"},
+				},
+			},
+		},
+		{
+			desc:    "recursive nested trees",
+			treeish: treeWithNestedSubtrees.Revision(),
+			options: []ReadTreeOption{WithRecursive()},
+			expectedTree: TreeEntry{
+				OID:  treeWithNestedSubtrees,
+				Type: Tree,
+				Mode: "040000",
+				Entries: []*TreeEntry{
+					{
+						Mode: "040000",
+						Type: Tree,
+						OID:  treeWithSubtree,
+						Path: "nested-subdir",
+						Entries: []*TreeEntry{
+							{
+								Mode: "040000",
+								Type: Tree,
+								OID:  emptyTreeID,
+								Path: "subdir",
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			desc:    "nested subtree",
+			treeish: treeWithNestedSubtrees.Revision(),
+			options: []ReadTreeOption{WithRelativePath("nested-subdir")},
+			expectedTree: TreeEntry{
+				OID:  treeWithSubtree,
+				Type: Tree,
+				Mode: "040000",
+				Entries: []*TreeEntry{
+					{Mode: "040000", Type: Tree, OID: emptyTreeID, Path: "subdir"},
+				},
+			},
+		},
+		{
+			desc:    "nested recursive subtree",
+			treeish: treeWithSubtreeContainingBlob.Revision(),
+			options: []ReadTreeOption{
+				WithRelativePath("subdir"),
+				WithRecursive(),
+			},
+			expectedTree: TreeEntry{
+				OID:  treeWithSubtreeAndBlob,
+				Type: Tree,
+				Mode: "040000",
+				Entries: []*TreeEntry{
+					{Mode: "100644", Type: Blob, OID: blobID, Path: "blob"},
+					{
+						Mode: "040000",
+						Type: Tree,
+						OID:  treeWithSubtree,
+						Path: "subdir",
+						Entries: []*TreeEntry{
+							{
+								Mode: "040000",
+								Type: Tree,
+								OID:  emptyTreeID,
+								Path: "subdir",
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			desc:    "recursive nested trees and blobs",
+			treeish: treeWithSubtreeAndBlob.Revision(),
+			options: []ReadTreeOption{
+				WithRecursive(),
+			},
+			expectedTree: TreeEntry{
+				OID:  treeWithSubtreeAndBlob,
+				Type: Tree,
+				Mode: "040000",
+				Entries: []*TreeEntry{
+					{Mode: "100644", Type: Blob, OID: blobID, Path: "blob"},
+					{
+						Mode: "040000",
+						Type: Tree,
+						OID:  treeWithSubtree,
+						Path: "subdir",
+						Entries: []*TreeEntry{
+							{
+								Mode: "040000",
+								Type: Tree,
+								OID:  emptyTreeID,
+								Path: "subdir",
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			desc:    "listing blob fails",
+			treeish: blobID.Revision(),
+			// We get a NotExist error here because it's invalid to suffix an object ID
+			// which resolves to a blob with a colon (":") given that it's not possible
+			// to resolve a subpath.
+			expectedErr: git.ErrReferenceNotFound,
+		},
+		{
+			desc:    "valid revision with invalid path",
+			treeish: treeWithSubtree.Revision(),
+			options: []ReadTreeOption{
+				WithRelativePath("does-not-exist"),
+			},
+			expectedErr: git.ErrReferenceNotFound,
+		},
+		{
+			desc:    "valid revision with path pointing to blob",
+			treeish: treeWithSubtreeAndBlob.Revision(),
+			options: []ReadTreeOption{
+				WithRelativePath("blob"),
+			},
+			expectedErr: ErrNotTreeish,
+		},
+		{
+			desc:        "listing nonexistent object fails",
+			treeish:     "does-not-exist",
+			expectedErr: git.ErrReferenceNotFound,
+		},
+	} {
+		tc := tc
+		t.Run(tc.desc, func(t *testing.T) {
+			t.Parallel()
+
+			tree, err := repo.ReadTree(ctx, tc.treeish, tc.options...)
+			if tc.expectedErr != nil {
+				require.ErrorIs(t, err, tc.expectedErr)
+				return
+			}
+			require.Equal(t, tc.expectedTree, *tree)
+		})
+	}
+}
+
+func TestWriteTreeRecursively(t *testing.T) {
+	cfg := testcfg.Build(t)
+
+	testCases := []struct {
+		desc      string
+		setupTree func(*testing.T, string) *TreeEntry
+	}{
+		{
+			desc: "every level has a new tree",
+			setupTree: func(t *testing.T, repoPath string) *TreeEntry {
+				blobA := gittest.WriteBlob(t, cfg, repoPath, []byte("a"))
+
+				return &TreeEntry{
+					OID:  "",
+					Type: Tree,
+					Mode: "040000",
+					Entries: []*TreeEntry{
+						{
+							OID:  "",
+							Type: Tree,
+							Mode: "040000",
+							Path: "dirA",
+							Entries: []*TreeEntry{
+								{
+									OID:  "",
+									Mode: "040000",
+									Type: Tree,
+									Path: "dirB",
+									Entries: []*TreeEntry{
+										{
+											OID:  blobA,
+											Type: Blob,
+											Mode: "100644",
+											Path: "file1",
+										},
+									},
+								},
+							},
+						},
+					},
+				}
+			},
+		},
+		{
+			desc: "only some new trees",
+			setupTree: func(t *testing.T, repoPath string) *TreeEntry {
+				blobA := gittest.WriteBlob(t, cfg, repoPath, []byte("a"))
+				blobB := gittest.WriteBlob(t, cfg, repoPath, []byte("b"))
+				blobC := gittest.WriteBlob(t, cfg, repoPath, []byte("c"))
+				blobD := gittest.WriteBlob(t, cfg, repoPath, []byte("d"))
+				dirDTree := gittest.WriteTree(
+					t,
+					cfg,
+					repoPath,
+					[]gittest.TreeEntry{
+						{
+							OID:  blobC,
+							Mode: "100644",
+							Path: "file3",
+						},
+						{
+							OID:  blobD,
+							Mode: "100644",
+							Path: "file4",
+						},
+					})
+				dirCTree := gittest.WriteTree(
+					t,
+					cfg,
+					repoPath,
+					[]gittest.TreeEntry{
+						{
+							OID:  dirDTree,
+							Mode: "040000",
+							Path: "dirD",
+						},
+					},
+				)
+
+				return &TreeEntry{
+					OID:  "",
+					Type: Tree,
+					Mode: "040000",
+					Entries: []*TreeEntry{
+						{
+							OID:  "",
+							Type: Tree,
+							Mode: "040000",
+							Path: "dirA",
+							Entries: []*TreeEntry{
+								{
+									OID:  "",
+									Mode: "040000",
+									Type: Tree,
+									Path: "dirB",
+									Entries: []*TreeEntry{
+										{
+											OID:  blobA,
+											Type: Blob,
+											Mode: "100644",
+											Path: "file1",
+										},
+										{
+											OID:  blobB,
+											Type: Blob,
+											Mode: "100644",
+											Path: "file2",
+										},
+									},
+								},
+							},
+						},
+						{
+							OID:  dirCTree,
+							Type: Tree,
+							Mode: "040000",
+							Path: "dirC",
+							Entries: []*TreeEntry{
+								{
+									OID:  dirDTree,
+									Mode: "040000",
+									Type: Tree,
+									Path: "dirD",
+									Entries: []*TreeEntry{
+										{
+											OID:  blobC,
+											Type: Blob,
+											Mode: "100644",
+											Path: "file3",
+										},
+										{
+											OID:  blobD,
+											Type: Blob,
+											Mode: "100644",
+											Path: "file4",
+										},
+									},
+								},
+							},
+						},
+					},
+				}
+			},
+		},
+	}
+
+	for _, tc := range testCases {
+		tc := tc
+		t.Run(tc.desc, func(t *testing.T) {
+			t.Parallel()
+
+			ctx := testhelper.Context(t)
+			repoProto, repoPath := gittest.CreateRepository(t, ctx, cfg, gittest.CreateRepositoryConfig{
+				SkipCreationViaService: true,
+			})
+			repo := NewTestRepo(t, cfg, repoProto)
+
+			treeEntry := tc.setupTree(t, repoPath)
+			require.NoError(t, treeEntry.Write(
+				ctx,
+				repo,
+			))
+
+			requireTreeEquals(t, ctx, repo, treeEntry.OID, treeEntry)
+		})
+	}
+}
+
+func requireTreeEquals(
+	t *testing.T,
+	ctx context.Context,
+	repo *Repo,
+	treeOID git.ObjectID,
+	expect *TreeEntry,
+) {
+	tree, err := repo.ReadTree(ctx, git.Revision(treeOID))
+	require.NoError(t, err)
+
+	for i, entry := range tree.Entries {
+		if tree.Entries[i].OID != "" {
+			require.Equal(t, expect.Entries[i].Mode, entry.Mode)
+			require.Equal(t, expect.Entries[i].Type, entry.Type)
+			require.Equal(t, expect.Entries[i].OID, entry.OID)
+			require.Equal(t, expect.Entries[i].Path, entry.Path)
+		} else {
+			objectInfo, err := repo.ReadObjectInfo(
+				ctx,
+				git.Revision(entry.OID),
+			)
+			require.NoError(t, err)
+
+			require.Equal(t, expect.Entries[i].Type, ToEnum(objectInfo.Type))
+		}
+
+		if entry.Type == Tree {
+			requireTreeEquals(t, ctx, repo, entry.OID, expect.Entries[i])
+		}
+	}
+}
+
+func TestReadTree_WithRecursive(t *testing.T) {
+	t.Parallel()
+
+	cfg := testcfg.Build(t)
+	ctx := testhelper.Context(t)
+
+	testCases := []struct {
+		desc        string
+		setupTree   func(t *testing.T, repoPath string) (git.ObjectID, TreeEntry)
+		expectedErr error
+	}{
+		{
+			desc: "flat tree",
+			setupTree: func(t *testing.T, repoPath string) (git.ObjectID, TreeEntry) {
+				blobA := gittest.WriteBlob(t, cfg, repoPath, []byte("a"))
+				blobB := gittest.WriteBlob(t, cfg, repoPath, []byte("b"))
+
+				treeID := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
+					{
+						Mode: "100644",
+						Path: "fileA",
+						OID:  blobA,
+					},
+					{
+						Mode: "100644",
+						Path: "fileB",
+						OID:  blobB,
+					},
+				})
+				return gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("master"),
+						gittest.WithTree(treeID)),
+					TreeEntry{
+						OID:  treeID,
+						Mode: "040000",
+						Type: Tree,
+						Entries: []*TreeEntry{
+							{
+								Mode: "100644",
+								Path: "fileA",
+								OID:  blobA,
+								Type: Blob,
+							},
+							{
+								Mode: "100644",
+								Path: "fileB",
+								OID:  blobB,
+								Type: Blob,
+							},
+						},
+					}
+			},
+		},
+		{
+			desc: "nested tree",
+			setupTree: func(t *testing.T, repoPath string) (git.ObjectID, TreeEntry) {
+				blobA := gittest.WriteBlob(t, cfg, repoPath, []byte("a"))
+				blobB := gittest.WriteBlob(t, cfg, repoPath, []byte("b"))
+				blobC := gittest.WriteBlob(t, cfg, repoPath, []byte("c"))
+				dirATree := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
+					{
+						Mode: "100644",
+						Path: "file1InDirA",
+						OID:  blobA,
+					},
+				})
+
+				treeID := gittest.WriteTree(t, cfg, repoPath, []gittest.TreeEntry{
+					{
+						Mode: "100644",
+						Path: "fileB",
+						OID:  blobB,
+					},
+					{
+						Mode: "100644",
+						Path: "fileC",
+						OID:  blobC,
+					},
+					{
+						Mode: "040000",
+						Path: "dirA",
+						OID:  dirATree,
+					},
+				})
+
+				return gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("master"),
+						gittest.WithTree(treeID)),
+					TreeEntry{
+						OID:  treeID,
+						Mode: "040000",
+						Type: Tree,
+						Entries: []*TreeEntry{
+							{
+								Mode: "040000",
+								Path: "dirA",
+								Type: Tree,
+								OID:  dirATree,
+								Entries: []*TreeEntry{
+									{
+										Mode: "100644",
+										Path: "file1InDirA",
+										OID:  blobA,
+										Type: Blob,
+									},
+								},
+							},
+							{
+								Mode: "100644",
+								Path: "fileB",
+								OID:  blobB,
+								Type: Blob,
+							},
+							{
+								Mode: "100644",
+								Path: "fileC",
+								OID:  blobC,
+								Type: Blob,
+							},
+						},
+					}
+			},
+		},
+	}
+
+	for _, tc := range testCases {
+		tc := tc
+		t.Run(tc.desc, func(t *testing.T) {
+			t.Parallel()
+
+			repoProto, repoPath := gittest.CreateRepository(
+				t,
+				ctx,
+				cfg,
+				gittest.CreateRepositoryConfig{
+					SkipCreationViaService: true,
+				})
+			repo := NewTestRepo(t, cfg, repoProto)
+
+			commitID, expectedTree := tc.setupTree(t, repoPath)
+
+			tree, err := repo.ReadTree(
+				ctx,
+				git.Revision(commitID),
+				WithRecursive(),
+			)
+			require.NoError(t, err)
+			require.Equal(t, expectedTree, *tree)
+		})
+	}
+}
diff --git a/internal/git/version.go b/internal/git/version.go
index 5048007fa..43cff0475 100644
--- a/internal/git/version.go
+++ b/internal/git/version.go
@@ -75,6 +75,14 @@ func (v Version) IsSupported() bool {
 	return !v.LessThan(minimumVersion)
 }
 
+// HashObjectFsck detects whether or not the given Git version will do fsck
+// checks when git-hash-object writes objects.
+func (v Version) HashObjectFsck() bool {
+	return !v.LessThan(Version{
+		major: 2, minor: 40, patch: 0,
+	})
+}
+
 // PatchIDRespectsBinaries detects whether the given Git version correctly handles binary diffs when
 // computing a patch ID. Previous to Git v2.39.0, git-patch-id(1) just completely ignored any binary
 // diffs and thus would consider two diffs the same even if a binary changed.
diff --git a/internal/gitaly/service/commit/tree_entries.go b/internal/gitaly/service/commit/tree_entries.go
index d7974a2b7..441d02b56 100644
--- a/internal/gitaly/service/commit/tree_entries.go
+++ b/internal/gitaly/service/commit/tree_entries.go
@@ -6,6 +6,7 @@ import (
 	"encoding/json"
 	"errors"
 	"fmt"
+	"path/filepath"
 	"sort"
 
 	"github.com/grpc-ecosystem/go-grpc-middleware/logging/logrus/ctxlogrus"
@@ -93,10 +94,12 @@ func (s *server) sendTreeEntries(
 	// git-ls-tree(1) is worse than using a long-lived catfile process. We thus fall back to
 	// using catfile readers to answer these non-recursive queries.
 	if recursive {
-		treeEntries, err := repo.ListEntries(ctx, git.Revision(revision), &localrepo.ListEntriesConfig{
-			Recursive:    recursive,
-			RelativePath: path,
-		})
+		tree, err := repo.ReadTree(
+			ctx,
+			git.Revision(revision),
+			localrepo.WithRelativePath(path),
+			localrepo.WithRecursive(),
+		)
 		if err != nil {
 			// Design wart: we do not return an error if the request does not
 			// point to a tree object, but just return nothing.
@@ -105,24 +108,27 @@ func (s *server) sendTreeEntries(
 			}
 
 			// Same if we try to list tree entries of a revision which doesn't exist.
-			if errors.Is(err, localrepo.ErrNotExist) {
+			if errors.Is(err, localrepo.ErrTreeNotExist) || errors.Is(err, git.ErrReferenceNotFound) {
 				return nil
 			}
 
-			return fmt.Errorf("listing tree entries: %w", err)
+			return fmt.Errorf("reading tree: %w", err)
 		}
 
-		entries = make([]*gitalypb.TreeEntry, 0, len(treeEntries))
-		for _, entry := range treeEntries {
+		if err := tree.Walk(func(dir string, entry *localrepo.TreeEntry) error {
+			if entry.OID == tree.OID {
+				return nil
+			}
+
 			objectID, err := entry.OID.Bytes()
 			if err != nil {
 				return fmt.Errorf("converting tree entry OID: %w", err)
 			}
 
-			treeEntry, err := git.NewTreeEntry(
+			newEntry, err := git.NewTreeEntry(
 				revision,
 				path,
-				[]byte(entry.Path),
+				[]byte(filepath.Join(dir, entry.Path)),
 				objectID,
 				[]byte(entry.Mode),
 			)
@@ -130,7 +136,11 @@ func (s *server) sendTreeEntries(
 				return fmt.Errorf("converting tree entry: %w", err)
 			}
 
-			entries = append(entries, treeEntry)
+			entries = append(entries, newEntry)
+
+			return nil
+		}); err != nil {
+			return fmt.Errorf("listing tree entries: %w", err)
 		}
 	} else {
 		var err error
diff --git a/internal/gitaly/service/operations/submodules.go b/internal/gitaly/service/operations/submodules.go
index 1162a8f8a..a2a413a07 100644
--- a/internal/gitaly/service/operations/submodules.go
+++ b/internal/gitaly/service/operations/submodules.go
@@ -71,30 +71,31 @@ func (s *Server) updateSubmodule(ctx context.Context, quarantineRepo *localrepo.
 	// tree with the new tree abcabc. Continue iterating up the tree,
 	// writing a new tree object each time.
 	for {
-		entries, err := quarantineRepo.ListEntries(
+		tree, err := quarantineRepo.ReadTree(
 			ctx,
-
 			git.Revision("refs/heads/"+string(req.GetBranch())),
-			&localrepo.ListEntriesConfig{
-				RelativePath: path,
-			})
+			localrepo.WithRelativePath(path),
+			localrepo.WithRecursive(),
+		)
 		if err != nil {
-			if strings.Contains(err.Error(), "invalid object name") {
+			if errors.Is(err, git.ErrReferenceNotFound) {
 				return "", fmt.Errorf("submodule: %s", git2go.LegacyErrPrefixInvalidSubmodulePath)
 			}
 
 			return "", fmt.Errorf("error reading tree: %w", err)
 		}
 
-		var newEntries []localrepo.TreeEntry
-		var newTreeID git.ObjectID
+		var newEntries []*localrepo.TreeEntry
+		if err := tree.Walk(func(path string, entry *localrepo.TreeEntry) error {
+			if entry.OID == tree.OID {
+				return nil
+			}
 
-		for _, entry := range entries {
 			// If the entry's path does not match, then we simply
 			// want to retain this tree entry.
 			if entry.Path != base {
-				newEntries = append(newEntries, *entry)
-				continue
+				newEntries = append(newEntries, entry)
+				return nil
 			}
 
 			// If we are at the submodule we want to replace, check
@@ -102,35 +103,42 @@ func (s *Server) updateSubmodule(ctx context.Context, quarantineRepo *localrepo.
 			// if it's not a submodule.
 			if filepath.Join(path, entry.Path) == string(req.GetSubmodule()) {
 				if string(entry.OID) == req.GetCommitSha() {
-					return "",
-						//nolint:stylecheck
-						fmt.Errorf(
-							"The submodule %s is already at %s",
-							req.GetSubmodule(),
-							replaceWith,
-						)
+					//nolint:stylecheck
+					return fmt.Errorf(
+						"The submodule %s is already at %s",
+						req.GetSubmodule(),
+						replaceWith,
+					)
 				}
 
 				if entry.Type != localrepo.Submodule {
-					return "", fmt.Errorf("submodule: %s", git2go.LegacyErrPrefixInvalidSubmodulePath)
+					return fmt.Errorf("submodule: %s", git2go.LegacyErrPrefixInvalidSubmodulePath)
 				}
 			}
 
 			// Otherwise, create a new tree entry
 			submoduleFound = true
 
-			newEntries = append(newEntries, localrepo.TreeEntry{
+			newEntries = append(newEntries, &localrepo.TreeEntry{
 				Mode: entry.Mode,
 				Path: entry.Path,
 				OID:  replaceWith,
 			})
+
+			return nil
+		}); err != nil {
+			return "", err
 		}
 
-		newTreeID, err = quarantineRepo.WriteTree(ctx, newEntries)
-		if err != nil {
+		newTree := &localrepo.TreeEntry{
+			Type:    localrepo.Tree,
+			Mode:    "040000",
+			Entries: newEntries,
+		}
+		if err := newTree.Write(ctx, quarantineRepo); err != nil {
 			return "", fmt.Errorf("write tree: %w", err)
 		}
-		replaceWith = newTreeID
+		replaceWith = newTree.OID
 
 		if path == "." {
 			break