Path handling on case-insensitive file systems

[MichaReiser]

Discussion related to #16400

I am starting this discussion to provide some more background on the problem with case-insensitive file systems and discuss different approaches.

The fundemental problems are:

1. Users can provide paths on the CLI and in configurations that don't match the casing on the file system. For example, you can run knot check SRC in a project with a src folder and Red Knot will happily index the files in the src folder on case-insensitive file systems. However, the constructed paths use SRC/a.py instead of src/a.py because the syscall to list a directory doesn't return full paths for its files but only relative paths that Red Knot concatenates with the user-provided path.
2. Red Knot uses file watchers to sync its virtual file system (tracks which file exists) and keep track of which files are part of the project. The events from the file watchers use the paths as provided by the operating system that match the casing on disk. The discrepancy between the indexed and watched files lead to stale entries in the virtual file system
3. Python's module resolver seems to be case sensitive even on case-insensitive file system. For example, from C import C fails if the module on this is c.py even on mac os (see Audit how we determine whether a file is a "Python source file" #13691). According to that issue, Mypy has special handling for this and it seems so does Pyright (because it raises an error for the previously given example).

How can these incorrect paths manifest:

• Red Knot will fail to update after a file changed because it doesn't update the last modified timestamp in the virtual file system
• Red Knot will fail to add or remove files from a project when they get created / deleted because the file watcher paths don't match any of the paths passed to knot check <PATHS>
• The diagnostics use the paths as provided on the CLI instead of using their real casing (e.g. TEST/a.py when running knot check TEST even if the folder's real name is test.

Whatever solution we end up with, we should optimize for the case where file paths are unique, ignoring their casing. It should be extremely rare to find projects with files that only differ in their casing, considering that the two popular platforms Windows and MacOS don't support it by default and it can be fairly confusing for devs.

[MichaReiser]

Keeping the virtual file-system (Files) up to date

This is the easiest to solve, as long as it's someone else's problem to ensure that only one entry exists in Files for every unique path on the disk (e.g., it should not contain a.py and A.py on a case-insensitive file system).

Files provides many sync_* methods (per file, per path) that force the virtual file system to sync its state with that on disk. We can simply make those methods case-insensitive. The only fall-out of this is that we perform some unnecessary stat calls, but that's a relatively small cost and also only the case for case-sensitive file systems where two paths only differ in casing.

[MichaReiser]

What does Pyright do?

I don't understand what Pyright does in full detail but it has a realCasePath method

https://github.com/microsoft/pyright/blob/c2ca7969f9780abab054662840798186c08cfd5f/packages/pyright-internal/src/common/realFileSystem.ts#L411-L441

What it does is roughly to canonicalize the path and use that path unless it is a symlink. Pyright calls realCasePath whenever it receives an "untrusted path" on the CLI, in the module resolver, etc.

The main downside of this approach is that it requires a canonicalize call for every resolved module and each CLI- or configuration-provided path only to deal with the edge case that a user provides an incorrectly cased path.

Pyright can skip the realCasePath on case sensitive systems:

https://github.com/microsoft/pyright/blob/1110ff90e462cea7ebba28b0da2b5d5b81fd08e7/packages/pyright-internal/src/tests/harness/testHost.ts#L71-L87

Mypy does something similar in their module resolver code with the exception that Mypy uses os.listdir on the parent directory to get a file's real casing. os.listdir has the advantage that it also works with symlinked files but I suspect it's slightly slower (and requires another cache that requires invalidating ugh)

https://github.com/python/mypy/blob/c32d11e60f04a0798292c438186199ccdec0db61/mypy/fscache.py#L221-L243

[MichaReiser]

I just noticed that Pyright also tracks the is case sensitive flag with each URI and performs case-insensitive* comparison for common path operations if it is false

https://github.com/microsoft/pyright/blob/2e397e9a0a84818342712af7639114b48e274a7a/packages/pyright-internal/src/common/uri/fileUri.ts#L167-L185

This is similar to what TypeScript does.

It's not entirely clear to me why it is necessary unless we want to allow globs to be case-insensitive on case-insensitive file systems. I don't think we should do that (git is case-sensitive!) and instead require that globs are case-sensitive.

[MichaReiser]

What does TypeScript do?

TypeScript also uses a similar approach to detect if the file system is case sensitive (we should probably say that Pyright uses a similar approach to TypeScript):

https://github.com/microsoft/TypeScript/blob/4a18b5cf8d41975c86cde25a0b2229f81e3b08d2/src/compiler/sys.ts#L1722-L1729

The flag is then passed through to different functions: E.g. matching files

https://github.com/microsoft/TypeScript/blob/1c4083f4edc71cb1744a62013732e3c95d05a035/src/compiler/utilities.ts#L9725

TypeScript is similar to Pyright in that it uses a GetCanonicalFileName function to canonicalize file paths.

https://github.com/microsoft/TypeScript/blob/4a18b5cf8d41975c86cde25a0b2229f81e3b08d2/src/compiler/core.ts#L2373-L2377

You can see how the method is a no-op on case sensitive systems but TypeScript lower cases path on all other systems.

https://github.com/microsoft/TypeScript/blob/4a18b5cf8d41975c86cde25a0b2229f81e3b08d2/src/compiler/core.ts#L1839-L1879

[MichaReiser]

What does CPython do

That's very important for us because we want to model CPython's module resolver as accurately as possible.

CPython's module resolver is case sensitive (with few legacy exceptions). That means, you can't import a module a.py with import A. This is good, because it ensures your code will work on all platforms. It's unfortunate for us, because there's no native API to get the real cased path (dotnet/runtime#14321)

I looked into what CPython does and it seems it caches the real file names per directory and resolves those names exactly once. Using listdir has the advantage that it also works for symlinked files.

For some more details, see #13691 (comment)

[MichaReiser]

Updating the files that are part of the project

This seems to be the most challenging problem. Let's say you run knot check SRC in a directory with the following content:

- src
  | - a.py
  | - b.py 

- script.py

Red Knot will pick up the src/a.py and src/b.py on a case-insensitive file system, but it indexes them as SRC/a.py and SRC/b.py

What's unclear to me is how we'd handle an event that a new file src/c.py was added because the path src/c.py won't match the path SRC provided on the CLI. Now, whether the file should be added to the files included when checking the project depends on whether the file system is case-sensitive (it should be included on case-insensitive file systems but not on case-sensitive file systems).

@sharkdp do you have an idea for how we could avoid knowing whether the file system is case-sensitive in this case?

Removing is another case that requires special handling, but we can rely on the file system to determine the right "steps."

• To a case-insensitive search for all files that match that path and are part of the project
• For paths with different casing, probe the file system to see if that path still exists. If not, remove it (it's obviously gone); otherwise, keep it.

The only thing we'd have to be extra careful about is avoiding interning two paths for the same File that differ only in casing on case-insensitive file systems.

One downside of this approach (unless we respect the casing anyway) is that include and exclude matches may not match as expected if a CLI provided path uses the wrong casing.

[sharkdp]

@sharkdp do you have an idea for how we could avoid knowing whether the file system is case-sensitive in this case?

I do not. It seems to me like what you propose here (adding something like realCasePath) is the right approach.

The main downside of this approach is that it requires a canonicalize call for every resolved module and each CLI- or configuration-provided path only to deal with the edge case that a user provides an incorrectly cased path.

Right. Let's hope that the number of of provided paths in big projects is usually much smaller than the number of actual paths?

[MichaReiser]

TLDR: I'm leaning towards adding a realCasePath method and using it everywhere where we build paths that don't come from the file system (module resolver, CLI provided paths).

The extra cost for CLI arguments should be negligible because most CLI invocations only have a few paths. The biggest added overhead comes from the module resolver but it seems that Python's forcing our hand and that we have to perform this check.

[sharkdp]

One use case that seems very common is that someone would rename a file from e.g. Module.py to module.py or vice-versa. I think this is an interesting edge case both on case-sensitive and case-insensitive (but case-preserving) file systems.

Seems like rust-analyzer and/or VS code have/had problems with this: rust-lang/rust-analyzer#9581 rust-lang/rust-analyzer#9947 rust-lang/rust-analyzer#15300

[MichaReiser]

I remember a related bug to this for Ruff's VS code extension and the way I remember it is that VS code doesn't propagate the casing update... which is problematic for all downstream tools.