Sass hangs when a file is imported from a location with a large file tree

[Tyoneb]

Issue

Summary

I have a scss file that contains an @import or @use statement that references a file in another location. That other location is provided using the --load-path CLI option. When I try to run sass on that single file, it hangs for what seems like an infinite amount of time (more than 10 minutes).

Details

• Operating System: Windows
• Runtime environment: NodeJS

Analysis

Root cause

I dug in your source code and understood that the root cause is the algorithm that walks up the source file location and caches the directories names with their "real" case (io.dart#_realCasePath). In my case, while walking up, it falls into a directory with more than 10000 subfolders and gets stuck there because the current implementation of io/js.dart#dirExists based on sequential synchronous calls to fs.existsSync and fs.statsSync is extremely costly (in my case, I measured ~1min for 1000 folders).

Based on the following comment in the code, you already know that the current implementation performs poorly:

TODO(nweiz): Use an SDK function for this when dart-lang/sdk#35370 and/or nodejs/node#24942 are fixed, or at least use FFI functions.

I looked at the mentioned issues and it seems that none of them get a lot of attention and they may never get implemented (especially on NodeJS side).

Proposal

Based on the discussions in the aforementioned issues, it seems important to avoid symbolic links resolution but I don't fully grasp why and I'm no expert on those, so the proposal below may not be valid...

I think you could leverage the NodeJS API fs.realpath.native to check whether or not the path contains a symbolic link, and if doesn't, you don't have to explore the entire file tree to get the proper case since realpath.native already returns it. If there is a symbolic link, then you can fall back to your existing mechanism.

I don't know Dart but here is what it could look like in JS:

const realPath = fs.realpathSync.native(path)
if (realPath.toUpperCase() === path.toUpperCase()) {
  // No symbolic link
  let reconstructed
  realPath.split(path.sep).forEach((part) => {
    reconstructed = reconstructed ? join(reconstructed, part) : part
    _realCasePath.putIfAbsent(reconstructed)
  })
  return realPath
}
return helper(path)

It's not perfect because it does not address the case of paths with symbolic links but it would noticeably speed up the path computation and caching for all other cases (especially if you get rid of the "walk up" mechanism as you already know the entire path has the correct case).

[nex3]

I agree that we could add a "fast path" here for the no-symlink case. We can't do the exact case-insensitive comparison you're suggesting, because it's possible that there's a symlink to a target that has the same name with a different case, but we can at least check at each level to see if it's a symlink and run realpath() if not before we fall back to the exhaustive directory-listing approach.

[ntkme]

I'm wondering why would we care about the "real" case if the filesystem is case-insensitive. If I understand correctly there are a few use cases for this:

1. Deduplicate and cache sass modules loading.
2. Print path in error reporting.

In case of deduplicate and cache case, I think what we care is that if the file is inside a case-insensitive mount, and where is the mount boundary. Even if we lowercase all path components within the case-insensitive file system boundary, it will still guarantee it always point to the same file regardless of what the case is. Let's say, / is case-sensitive, and /mnt/data is case-insensitive, then with in /mnt/data - /mnt/data/Path/File.scss effectively has no difference than /mnt/data/path/file.scss. Therefore, I'd argue in this use case the "real case" doesn't matter as we can always just normalize to everything to lowercase.

In case of error reporting, we can always just report the original case that the user is using in the stylesheet. User might import the same file twice in difference casing, so tracking and reporting the "original case" might be tricky. However, on the other hand we can argue that's more of a cosmetic issue that even if we report a different casing, as long as it's the same file it's not a huge problem.

So in my opinion we can just need a normalization to a "consistent-case", and "real-case" is not necessarily needed. If we simply do that the performance and compatibility issues would just go away, with the cost of a small potential cosmetic issue. In order to reliably and correctly handle this, we need to know file system case-sensitivity and mount boundaries, which might be difficult, but will be way faster than listing directories.

I hope I didn't miss any other fundamental reason why real case is needed.

[ntkme]

Technically assuming file system is case sensitive or not based on OS is not entirely safe. Although it's not very common, but it's possible to have case-insensitive mount on linux, and case-sensitive mount on mac and windows.

[ntkme]

Well, after another thought, getting the file system case sensitivity and getting the real case of a file might be equally challenging, as both likely require some syscall via ffi to be efficient.

[nex3]

It's not just about caching, it's about correctness. Sass's module system behavior is based on the concept of each module having a "canonical URL". If you load a module that has the same canonical URL as an existing module, it will just return that existing module, with whatever state it already has. If you, for example, create a symlink to that module's SCSS and load it with a different canonical URL, its contents will be re-evaluated and you'll have two different copies of this module in memory with potentially two different states. But URL comparisons are case-sensitive, and we don't want to create a situation where someone loads path/to/File.scss and path/to/file.scss in different places and finds that they unexpectedly create different modules despite referring to the same file.

You're right that merely enforcing consistency would be sufficient here, but that would require 100% confidence that we know exactly which paths are or are not case-sensitive. This isn't an API that any standard library provides, and as you point out, it's not any easier to provide it ourselves than it would be to call out to the OS-level case canonicalization logic. So we rely on the heuristic that Windows and Mac OS might be case-sensitive and rely on manual resolution to determine what the actual case is. That said, I think symlinks should be a pretty narrow edge-case, so relying on the library-level realpath functions is likely to be sufficient to completely mitigate the performance issue here.

[ntkme]

Here is a proof of concept patch normalizing potentially case-insensitive path components all to lower case instead of real case by testing path casing at each level. I haven't tested this extensively, but I think the only case it might be broken is that the definition of case folding of a filesystem might differ from the case folding used in .toLowerCase() and .toUpperCase(). As far as I know, Dart, JS, and Mac/Windows file systems all use Unicode CaseFolding, but they might have different unicode version which might have slightly different folding table, thus might have inconsistency in some corner cases.

diff --git a/lib/src/io.dart b/lib/src/io.dart
index c0cabd83..9419aecb 100644
--- a/lib/src/io.dart
+++ b/lib/src/io.dart
@@ -7,8 +7,6 @@ import 'package:path/path.dart' as p;
 import 'io/interface.dart'
     if (dart.library.io) 'io/vm.dart'
     if (dart.library.js) 'io/js.dart';
-import 'utils.dart';
-import 'util/character.dart';
 
 export 'io/interface.dart'
     if (dart.library.io) 'io/vm.dart'
@@ -39,36 +37,27 @@ String _realCasePath(String path) {
 
   if (!_couldBeCaseInsensitive) return path;
 
-  if (isWindows) {
-    // Drive names are *always* case-insensitive, so convert them to uppercase.
-    var prefix = p.rootPrefix(path);
-    if (prefix.isNotEmpty && prefix.codeUnitAt(0).isAlphabetic) {
-      path = prefix.toUpperCase() + path.substring(prefix.length);
-    }
-  }
-
   String helper(String path) {
-    var dirname = p.dirname(path);
-    if (dirname == path) return path;
-
     return _realCaseCache.putIfAbsent(path, () {
-      var realDirname = helper(dirname);
-      var basename = p.basename(path);
-
       try {
-        var matches = listDir(realDirname)
-            .where(
-              (realPath) => equalsIgnoreCase(p.basename(realPath), basename),
-            )
-            .toList();
-
-        return switch (matches) {
-          [var match] => match,
-          // If the file doesn't exist, or if there are multiple options
-          // (meaning the filesystem isn't actually case-insensitive), use
-          // `basename` as-is.
-          _ => p.join(realDirname, basename),
-        };
+        var components = p.split(path);
+        for (var i = 0; i < components.length; i++) {
+          var originalComponent = components[i];
+          var lowerComponent = originalComponent.toLowerCase();
+          var upperComponent = originalComponent.toUpperCase();
+          if (lowerComponent != upperComponent) {
+            components[i] = upperComponent;
+            var upperPath = p.joinAll(components.sublist(0, i + 1));
+            components[i] = lowerComponent;
+            var lowerPath = p.joinAll(components.sublist(0, i + 1));
+            if (!(fileExists(lowerPath) &&
+                fileExists(upperPath) &&
+                isIdenticalFile(lowerPath, upperPath))) {
+              components[i] = originalComponent;
+            }
+          }
+        }
+        return p.joinAll(components);
       } on FileSystemException catch (_) {
         // If there's an error listing a directory, it's likely because we're
         // trying to reach too far out of the current directory into something
diff --git a/lib/src/io/interface.dart b/lib/src/io/interface.dart
index 29182eb4..dcff3649 100644
--- a/lib/src/io/interface.dart
+++ b/lib/src/io/interface.dart
@@ -92,3 +92,5 @@ set exitCode(int value) => throw '';
 /// periodically rather than using a native filesystem monitoring API.
 Future<Stream<WatchEvent>> watchDir(String path, {bool poll = false}) =>
     throw '';
+
+bool isIdenticalFile(String path1, String path2) => throw '';
diff --git a/lib/src/io/js.dart b/lib/src/io/js.dart
index d072ff40..fd2455d5 100644
--- a/lib/src/io/js.dart
+++ b/lib/src/io/js.dart
@@ -344,3 +344,6 @@ Future<Stream<WatchEvent>> watchDir(String path, {bool poll = false}) async {
     return completer.future;
   }
 }
+
+bool isIdenticalFile(String path1, String path2) =>
+    fs.statSync(path1).ino == fs.statSync(path2).ino;
diff --git a/lib/src/io/vm.dart b/lib/src/io/vm.dart
index 7d7631b1..9511d2b8 100644
--- a/lib/src/io/vm.dart
+++ b/lib/src/io/vm.dart
@@ -114,3 +114,6 @@ Future<Stream<WatchEvent>> watchDir(String path, {bool poll = false}) async {
 
   return stream;
 }
+
+bool isIdenticalFile(String path1, String path2) =>
+    io.FileSystemEntity.identicalSync(path1, path2);

[nex3]

According to this writeup, it sounds like Windows casing logic doesn't necessarily match Unicode and in fact may differ to some degree from volume to volume. I think it's likely to be safer to just rely on realpath with a slow path for symlinks.

[ntkme]

Sounds good. I think there is one small edge case for the purposed solution with realpath: if we're in a case-sensitive file system on mac, and I have a symlink dir -> DIR, then we will end up resolve .../dir/main.scss as .../DIR/main.scss.

This can be fixed by adding an inode equal check on the symlink vs symlink realpath. Or we can do lstatSync(file).isSymbolicLink on each level before do realpath.

[nex3]

I think the in-progress PR I have brewing avoids that issue.

[Tyoneb]

Wow, thank you guys for the super fast reaction time on this issue!