Repository: aai-institute/lakefs-spec

Issue:
Strange behavior with files containing `__` 
### What happened?

```
❯ lakectl fs ls -r lakefs://sample/test-venky/data/foo/
object          2024-12-12 23:32:03 -0800 PST    2.7 kB          data/foo/bar/axe.just
object          2024-12-12 23:26:00 -0800 PST    0 B             data/foo/bar/quux/widg.txt
object          2024-12-12 23:26:00 -0800 PST    0 B             data/foo/bar__baz.txt
```

```
p = UPath("lakefs://sample/test-venky/data/foo", use_listings_cache=False)
list(p.fs.find(p, withdirs=True))
---
['sample/test-venky/data/foo',
 'sample/test-venky/data/foo/bar/',
 'sample/test-venky/data/foo/bar__baz.txt']
```
 
Where did `foo/bar/*/` go? 


`p.fs.walk()` has the same behavior, but `p.fs.ls(p, recursive=True)` returns the right information


The files do exist if you drill down and look explicitly for them

```
p = UPath("lakefs://sample/test-venky/data/foo/bar/axe", use_listings_cache=False)
p.fs.ls(p)
---
[{'checksum': 'a87e010a318457fd39f9525e6d1c576d',
  'content-type': 'application/octet-stream',
  'mtime': 1734075123,
  'name': 'sample/test-venky/data/foo/bar/axe.just',
  'size': 2696,
  'type': 'object'}]
```

A further problem is that this leads to fs.walk reporting non-existent files:

```
p = UPath("lakefs://sample/test-venky/data/foo/", use_listings_cache=False)
list(p.fs.walk(p))
---
[('sample/test-venky/data/foo', ['bar'], ['bar__baz.txt']),
 ('sample/test-venky/data/foo/bar', [], ['', 'bar__baz.txt'])]
```

^ notice that bar__baz.txt is returned twice, once under foo/  and once under bar/ -- the second instance is just wrong

### What did you expect to happen?

The pattern seems to be that if you have if you have a folder x/ and a file x__<whatever> as siblings, the children of x/ are hidden somehow

### lakeFS-spec version

0.11.0

### lakeFS version

0.7.1

Hints from issue comments:
@AdrianoKF: Thanks for your detailed report, @indigoviolet! I'll investigate and get back to you soon.@AdrianoKF: @indigoviolet, I've pushed a potential fix for the issue you are seeing in PR #298.

Can you test if the fix works for you? (`pip install git+https://github.com/aai-institute/lakefs-spec.git@issue-297` should work)

The double underscores in the filename turned out to be a red herring. In a nutshell, the `ls` method was incorrectly including files that matched a prefix of its argument, which is why you were seeing the `data/foo/bar__baz.txt` file included in `ls("data/foo/bar")` since its name has `data/foo/bar` as a prefix. This error then affected all the other methods on the filesystem, which transitively rely on the results of `ls`.

Solution patch:
diff --git a/src/lakefs_spec/spec.py b/src/lakefs_spec/spec.py
index 8da521f6..18666c22 100644
--- a/src/lakefs_spec/spec.py
+++ b/src/lakefs_spec/spec.py
@@ -365,7 +365,7 @@ def info(self, path: str | os.PathLike[str], **kwargs: Any) -> dict[str, Any]:
             except ServerException as e:
                 raise translate_lakefs_error(e, rpath=path)
 
-        out = self.ls(path, detail=True, recursive=True, **kwargs)
+        out = self.ls(path, detail=True, recursive=False, **kwargs)
         if not out:
             raise FileNotFoundError(errno.ENOENT, os.strerror(errno.ENOENT), path)
 
@@ -504,8 +504,8 @@ def ls(
 
         kwargs["prefix"] = prefix
 
-        info = []
         # stat infos are either the path only (`detail=False`) or a dict full of metadata
+        info = []
         delimiter = "" if recursive else "/"
         reference = lakefs.Reference(repository, ref, client=self.client)
 
@@ -521,6 +521,17 @@ def ls(
                         }
                     )
                 elif isinstance(obj, ObjectInfo):
+                    # Skip over prefix-only matches, e.g., given:
+                    #
+                    # foo/
+                    # ├── bar/
+                    # │   └── ...
+                    # └── bar__baz.txt
+                    #
+                    # `ls("foo/bar")` should not include `bar__baz.txt`
+                    if not (prefix == "" or prefix.endswith("/")) and obj.path != prefix:
+                        continue
+
                     info.append(
                         {
                             "checksum": obj.checksum,
diff --git a/src/lakefs_spec/util.py b/src/lakefs_spec/util.py
index 7e1cff3b..1a8c8d57 100644
--- a/src/lakefs_spec/util.py
+++ b/src/lakefs_spec/util.py
@@ -7,6 +7,7 @@
 import os
 import re
 import sys
+from collections import namedtuple
 from collections.abc import Callable, Generator, Iterable, Iterator
 from typing import Any, Protocol
 
@@ -16,6 +17,8 @@
 lakefs_sdk_version = tuple(int(v) for v in __lakefs_sdk_version__.split("."))
 del __lakefs_sdk_version__
 
+_ParsedUri = namedtuple("_ParsedUri", ("repository", "ref", "resource"))
+
 
 class PaginatedApiResponse(Protocol):
     pagination: Pagination
@@ -115,16 +118,28 @@ def parse(path: str) -> tuple[str, str, str]:
         If the path does not conform to the lakeFS URI format.
     """
 
-    # First regex reflects the lakeFS repository naming rules:
-    # only lowercase letters, digits and dash, no leading dash, minimum 3, maximum 63 characters
-    # https://docs.lakefs.io/understand/model.html#repository
-    # Second regex is the branch: Only letters, digits, underscores and dash, no leading dash.
-    path_regex = re.compile(r"(?:lakefs://)?([a-z0-9][a-z0-9\-]{2,62})/(\w[\w\-]*)/(.*)")
-    results = path_regex.fullmatch(path)
-    if results is None:
-        raise ValueError(
-            f"expected path with structure lakefs://<repo>/<ref>/<resource>, got {path!r}"
-        )
-
-    repo, ref, resource = results.groups()
+    uri_parts = {
+        "protocol": r"^(?:lakefs://)?",  # leading lakefs:// protocol (optional)
+        "repository": r"(?P<repository>[a-z0-9][a-z0-9\-]{2,62})/",
+        "ref expression": r"(?P<ref>\w[\w\-]*)/",
+        "resource": r"(?P<resource>.*)",
+    }
+
+    groups: dict[str, str] = {}
+    start = 0
+    for group, regex in uri_parts.items():
+        # we parse iteratively to improve the error message for the user if an invalid URI is given.
+        # by going front to back and parsing each part successively, we obtain the current path segment,
+        # and print it out to the user if it does not conform to our assumption of the lakeFS URI spec.
+        match = re.match(regex, path[start:])
+        # the next part of the URI is marked by a slash, or the end if we're parsing the resource.
+        segment = path[start : path.find("/", start)]
+        if match is None:
+            raise ValueError(
+                f"not a valid lakeFS URI: {path!r} (hint: invalid {group} {segment!r})"
+            )
+        groups.update(match.groupdict())
+        start += match.end()
+
+    repo, ref, resource = _ParsedUri(**groups)
     return repo, ref, resource


Test patch:
diff --git a/tests/regression/test_gh_297.py b/tests/regression/test_gh_297.py
new file mode 100644
index 00000000..8d3cc36f
--- /dev/null
+++ b/tests/regression/test_gh_297.py
@@ -0,0 +1,48 @@
+import os
+
+from lakefs import Branch, Repository
+
+from lakefs_spec.spec import LakeFSFileSystem
+
+
+def test_gh_297(
+    fs: LakeFSFileSystem,
+    repository: Repository,
+    temp_branch: Branch,
+) -> None:
+    """
+    Regression test for GitHub issue 297: Strange behavior with files containing `__`
+
+    https://github.com/aai-institute/lakefs-spec/issues/297
+    """
+
+    root_dir = "data/foo"
+    files = [
+        f"{root_dir}/bar/axe.just",
+        f"{root_dir}/bar/quux/widg.txt",
+        f"{root_dir}/bar_baz.txt",
+    ]
+    prefix = f"lakefs://{repository.id}/{temp_branch.id}"
+
+    for file in files:
+        fs.pipe(f"{prefix}/{file}", b"data")
+
+    # -- fs.find() should list all files
+    # In #297, the `__` in the filename caused the `find` method to return
+    # just the `foo/bar/` directory and the `foo/bar__baz.txt` file.
+    found_files = fs.find(f"{prefix}/{root_dir}")
+    assert set(found_files) == {f"{repository.id}/{temp_branch.id}/{f}" for f in files}
+
+    # -- fs.walk() should list all files exactly once
+    result = list(fs.walk(f"{prefix}/{root_dir}"))
+    found_files = set()
+    for entry in result:
+        rootdir = entry[0]
+        for filename in entry[2]:
+            found_files.add(os.path.join(rootdir, filename))
+
+    assert found_files == {f"{repository.id}/{temp_branch.id}/{f}" for f in files}
+
+    # Check that the files are present
+    for file in files:
+        assert fs.isfile(f"{prefix}/{file}")
diff --git a/tests/test_ls.py b/tests/test_ls.py
index b001e4b8..c9a08935 100644
--- a/tests/test_ls.py
+++ b/tests/test_ls.py
@@ -142,7 +142,7 @@ def test_ls_no_detail(fs: LakeFSFileSystem, repository: Repository) -> None:
     expected = [f"{resource}/lakes.source.md"]
     # first, verify the API fetch does the expected...
     assert fs.ls(resource, detail=False) == expected
-    assert list(fs.dircache.keys()) == [resource]
+    assert set(fs.dircache.keys()) == {resource}
 
     # ...as well as the cache fetch.
     assert fs.ls(resource, detail=False) == expected
@@ -150,12 +150,6 @@ def test_ls_no_detail(fs: LakeFSFileSystem, repository: Repository) -> None:
     # One API call for the directory object, and one for listing its contents
     assert counter.count("objects_api.list_objects") == 2
 
-    # test the same thing with a subfolder + file prefix
-    resource = f"{prefix}/images/duckdb"
-    fs.ls(resource, detail=False)
-
-    assert set(fs.dircache.keys()) == {f"{prefix}/data", f"{prefix}/images"}
-
 
 def test_ls_dircache_remove_uncached(
     fs: LakeFSFileSystem,
diff --git a/tests/test_spec_utils.py b/tests/test_spec_utils.py
index 50b98047..d86eb0a4 100644
--- a/tests/test_spec_utils.py
+++ b/tests/test_spec_utils.py
@@ -31,13 +31,13 @@ def test_path_parsing_success(path: str, repo: str, ref: str, resource: str) ->
     "path,expected_exception",
     [
         # repo name illegally begins with hyphen
-        ("-repo/my-ref/resource.txt", pytest.raises(ValueError, match="expected path .*")),
+        ("-repo/my-ref/resource.txt", pytest.raises(ValueError, match="invalid repository")),
         # repo name contains an illegal uppercase letter
-        ("Repo/my-ref/resource.txt", pytest.raises(ValueError, match="expected path .*")),
+        ("Repo/my-ref/resource.txt", pytest.raises(ValueError, match="invalid repository")),
         # missing repo name
-        ("my-ref/resource.txt", pytest.raises(ValueError, match="expected path .*")),
+        ("my-ref/resource.txt", pytest.raises(ValueError, match="invalid ref expression")),
         # illegal branch name
-        ("repo/my-ref$$$/resource.txt", pytest.raises(ValueError, match="expected path .*")),
+        ("repo/my-ref$$$/resource.txt", pytest.raises(ValueError, match="invalid ref expression")),
     ],
 )
 def test_path_parsing_failure(path: str, expected_exception: AbstractContextManager) -> None: