localrepo: Turn TreeEntry into a tree data structure

Currently, a TreeEntry is a flat data structure in the sense that it
represents a single entry but does not have any children. A git tree
object has children though.

Change this by adding an Entries member to the TreeEntry struct. This
way, we can represent a real tree data structure.

Also, add a GetTree() function that can get an entire tree. We can
consolidate ListEntries() into GetTree().

6 files changed, 686 insertions, 287 deletions

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/tree.go b/internal/git/localrepo/tree.go
index f72224ea7..c08ecc9f7 100644
--- a/internal/git/localrepo/tree.go
+++ b/internal/git/localrepo/tree.go
@@ -3,7 +3,10 @@ package localrepo
 import (
 	"bytes"
 	"context"
+	"errors"
 	"fmt"
+	"io"
+	"path/filepath"
 	"sort"
 	"strings"
 
@@ -92,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.
@@ -99,7 +104,198 @@ 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
+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 {
+		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
+}
+
+// WriteTree 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) WriteTree(ctx context.Context, entries []*TreeEntry) (git.ObjectID, error) {
 	var tree bytes.Buffer
@@ -155,3 +351,71 @@ func (repo *Repo) WriteTree(ctx context.Context, entries []*TreeEntry) (git.Obje
 
 	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 3b7daf026..8a5e0bb02 100644
--- a/internal/git/localrepo/tree_test.go
+++ b/internal/git/localrepo/tree_test.go
@@ -9,6 +9,7 @@ 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/helper/text"
 	"gitlab.com/gitlab-org/gitaly/v15/internal/structerr"
@@ -368,3 +369,380 @@ func TestTreeEntryByPath(t *testing.T) {
 		})
 	}
 }
+
+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 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/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 7a96194ef..ecf919c20 100644
--- a/internal/gitaly/service/operations/submodules.go
+++ b/internal/gitaly/service/operations/submodules.go
@@ -71,15 +71,14 @@ 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)
 			}
 
@@ -87,14 +86,16 @@ func (s *Server) updateSubmodule(ctx context.Context, quarantineRepo *localrepo.
 		}
 
 		var newEntries []*localrepo.TreeEntry
-		var newTreeID git.ObjectID
+		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
+				return nil
 			}
 
 			// If we are at the submodule we want to replace, check
@@ -102,17 +103,16 @@ 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)
 				}
 			}
 
@@ -124,9 +124,13 @@ func (s *Server) updateSubmodule(ctx context.Context, quarantineRepo *localrepo.
 				Path: entry.Path,
 				OID:  replaceWith,
 			})
+
+			return nil
+		}); err != nil {
+			return "", err
 		}
 
-		newTreeID, err = quarantineRepo.WriteTree(ctx, newEntries)
+		newTreeID, err := quarantineRepo.WriteTree(ctx, newEntries)
 		if err != nil {
 			return "", fmt.Errorf("write tree: %w", err)
 		}