fix(tvix/nar-bridge): Fix directory stack tracking r/6602

Previously, nar-bridge, had a couple of bugs with tracking the current
directory when traversing a NAR file.

The included test case looks like:
```
/ (dir)
/test (dir)
/test/tested (file)
/tested (file)
```

Previously, we would do a string prefix match between the current node
and the top of the directory stack to determine if the node is in the
directory. In this case `/test` is a substring of `/tested`; however,
`/tested` is not in the `/test` directory. The fix is to append a `/` to
the directory name when doing the prefix match, so `/test/` is not a
prefix of `/tested`.

Additionally, when popping the stack, we need to continuously pop the
stack until the new node is in the directory at the top of the stack
(stopping before we pop the root directory)

Example:
```
/ (dir)
/a (dir)
/a/b (dir)
/a/b/c (file)
/z (file)
```

Previously, `z` would end up in directory `/a` because we only the pop
the stack once.

The included test case requires both of these issues to be fixed for it
to pass, so I think it is sufficient.

Change-Id: I22f601babf04d39d85535ba7ad585d3970757211
Reviewed-on: https://cl.tvl.fyi/c/depot/+/9348
Tested-by: BuildkiteCI
Reviewed-by: flokli <flokli@flokli.de>
Autosubmit: Connor Brewster <cbrewster@hey.com>

3 files changed, 39 insertions, 5 deletions

diff --git a/tvix/nar-bridge/pkg/reader/reader.go b/tvix/nar-bridge/pkg/reader/reader.go
index 6d34cd168d..9ff7b3fedb 100644
--- a/tvix/nar-bridge/pkg/reader/reader.go
+++ b/tvix/nar-bridge/pkg/reader/reader.go
@@ -190,15 +190,21 @@ func (r *Reader) Import(
 			// Check for valid path transitions, pop from stack if needed
 			// The nar reader already gives us some guarantees about ordering and illegal transitions,
 			// So we really only need to check if the top-of-stack path is a prefix of the path,
-			// and if it's not, pop from the stack.
+			// and if it's not, pop from the stack. We do this repeatedly until the top of the stack is
+			// the subdirectory the new entry is in, or we hit the root directory.
 
 			// We don't need to worry about the root node case, because we can only finish the root "/"
 			// If we're at the end of the NAR reader (covered by the EOF check)
-			if len(stack) > 0 && !strings.HasPrefix(hdr.Path, stack[len(stack)-1].path) {
-				err := popFromStack()
-				if err != nil {
-					return nil, fmt.Errorf("unable to pop from stack: %w", err)
+			for {
+				// We never want to pop the root directory until we're completely done.
+				if len(stack) > 1 && !strings.HasPrefix(hdr.Path, stack[len(stack)-1].path+"/") {
+					err := popFromStack()
+					if err != nil {
+						return nil, fmt.Errorf("unable to pop from stack: %w", err)
+					}
+					continue
 				}
+				break
 			}
 
 			if hdr.Type == nar.TypeSymlink {
diff --git a/tvix/nar-bridge/pkg/reader/reader_test.go b/tvix/nar-bridge/pkg/reader/reader_test.go
index 6ca1ca2d74..1ba9c9651c 100644
--- a/tvix/nar-bridge/pkg/reader/reader_test.go
+++ b/tvix/nar-bridge/pkg/reader/reader_test.go
@@ -566,3 +566,31 @@ func TestCallbackErrors(t *testing.T) {
 		require.ErrorIs(t, err, targetErr)
 	})
 }
+
+// TestPopDirectories is a regression test that ensures we handle the directory
+// stack properly.
+//
+// This test case looks like:
+//
+// / (dir)
+// /test (dir)
+// /test/tested (file)
+// /tested (file)
+//
+// We used to have a bug where the second `tested` file would appear as if
+// it was in the `/test` dir because it has that dir as a string prefix.
+func TestPopDirectories(t *testing.T) {
+	f, err := os.Open("../../testdata/popdirectories.nar")
+	require.NoError(t, err)
+	defer f.Close()
+
+	r := reader.New(f)
+	_, err = r.Import(
+		context.Background(),
+		func(fileReader io.Reader) error { return nil },
+		func(directory *storev1pb.Directory) error {
+			return directory.Validate()
+		},
+	)
+	require.NoError(t, err)
+}
diff --git a/tvix/nar-bridge/testdata/popdirectories.nar b/tvix/nar-bridge/testdata/popdirectories.nar
new file mode 100644
index 0000000000..74313aca52
--- /dev/null
+++ b/tvix/nar-bridge/testdata/popdirectories.nar
Binary files differ