[VFS][WIP] More consistent handling of hybrid paths of Windows+Posix styles

[amccarth]

Summary

This is a counter-proposal to the fix suggested in

https://reviews.llvm.org/D74488

VFS paths can be a hybrid of Windows and Posix styles, so the sys::path methods sometimes cannot handle them. This generalizes the VFS-specific canonicalize function to remove traversal components from these possibly hybrid paths.

THIS NEEDS TESTS.

[john.brawn]

This causes a lot of test failures in llvm/unittests/Support/VirtualFileSystemTest.cpp. A lot of them use //root as a root directory, and e.g. looking at the MappedFiles test what's happening is:

• //root/foo/bar/a is added to the DummyFileSystem
• getFromYAMLString used on a YAML string that maps //root/file1 to //root/foo/bar/a
• The //root/foo/bar/a is canonicalized to /root/foo/bar/a
• O->status("//root/file1") matches the //root/file1 in the YAML, but the subsequent lookup tries to find /root/foo/bar/a which doesn't match the //root/foo/bar/a that was added to the DummyFileSystem so we get a "file not found" error

[amccarth]

That's strange. I thought I'd run all the LLVM and Clang VFS tests before posting this patch.

I'll look into it some more when I get a chance. I was not aware that Posix treats (exactly) two slashes at the root as "special." These VFS hybrid paths are really a pain, since a double backslash at the root means a UNC path, but we mostly treat slashes and backslashes as interchangeable. What a mess.

[amccarth]

In D74777#1882613, @john.brawn wrote:

This causes a lot of test failures in llvm/unittests/Support/VirtualFileSystemTest.cpp. A lot of them use //root as a root directory, and e.g. looking at the MappedFiles test what's happening is:

• //root/foo/bar/a is added to the DummyFileSystem
• getFromYAMLString used on a YAML string that maps //root/file1 to //root/foo/bar/a
• The //root/foo/bar/a is canonicalized to /root/foo/bar/a
• O->status("//root/file1") matches the //root/file1 in the YAML, but the subsequent lookup tries to find /root/foo/bar/a which doesn't match the //root/foo/bar/a that was added to the DummyFileSystem so we get a "file not found" error

I cannot reproduce the problem you're reporting. For example:

D:\src\llvm\build\ninja_dbg\unittests\Support\SupportTests.exe --gtest_filter=VFSFromYAMLTest.MappedFiles
Note: Google Test filter = VFSFromYAMLTest.MappedFiles
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from VFSFromYAMLTest
[ RUN      ] VFSFromYAMLTest.MappedFiles
[       OK ] VFSFromYAMLTest.MappedFiles (3 ms)
[----------] 1 test from VFSFromYAMLTest (10 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (27 ms total)
[  PASSED  ] 1 test.

In fact, if I make canonicalize preserve both slashes at the root whenever they exist, then I get failures even creating the file system from the yaml because sys::path::is_absolute no longer thinks //root/file1 is an absolute path.

I'm showing the result from VFSFromYAMLTest.MappedFiles because that's the specific example you gave. But all of the clang VFS tests and LLVM Support tests pass for me with this patch.

[john.brawn]

Running that command (with this patch applied to trunk revision 56ac9d30d35632969baa39829ebc8465ed5937ef) I get

Note: Google Test filter = VFSFromYAMLTest.MappedFiles
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from VFSFromYAMLTest
[ RUN      ] VFSFromYAMLTest.MappedFiles
C:\Users\johbra01\llvm-project\llvm\unittests\Support\VirtualFileSystemTest.cpp(1411): error: Value of: S.getError()
  Actual: true
Expected: false
[  FAILED  ] VFSFromYAMLTest.MappedFiles (30 ms)
[----------] 1 test from VFSFromYAMLTest (94 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (232 ms total)
[  PASSED  ] 0 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] VFSFromYAMLTest.MappedFiles

 1 FAILED TEST

And I also see this same failure on Linux. I'll try looking into this some more to make sure I'm not doing something strange somehow.

[john.brawn]

Doing a clean checkout and build on Linux using the following commands I get the same test error:

git clone https://github.com/llvm/llvm-project.git
wget https://reviews.llvm.org/file/download/tiyftt33uo7cki54v443/PHID-FILE-yq35g4b6fbvssmn5il2f/D74777.diff
patch -d llvm-project -p0 < D74777.diff
mkdir build
cd build
cmake ../llvm-project/llvm/
make SupportTests
./unittests/Support/SupportTests --gtest_filter=VFSFromYAMLTest.MappedFiles

llvm/lib/Support/VirtualFileSystem.cpp

 } // namespace llvm
 
 //===-----------------------------------------------------------------------===/
 // RedirectingFileSystem implementation
 //===-----------------------------------------------------------------------===/
 
 namespace {
 
-/// Removes leading "./" as well as path components like ".." and ".".
+/// Returns the components of a possibly hybrid Path.  In VFS, paths can be
+/// hybrids of Windows and Posix styles, so we cannot rely on the sys::path
+/// methods which make assumptions.
+///
+/// Examples:
+///   "C:/foo\\bar"
+///      -> { "C:", "/", "foo\\", "bar" }
+///   "C:./.././//foo/bar/../bar"
+///      -> {"C:", "./", "../", "./", "/", "/", "foo/", "bar/", "../", "bar" }
+static llvm::SmallVector<llvm::StringRef, 10> splitHybridPath(llvm::StringRef Path) {
+  llvm::SmallVector<llvm::StringRef, 10> components;
+  auto head = Path.begin();
+  auto it = head;
+  auto end = Path.end();
+  while (it != end) {
+    if (*it == '/' || *it == '\\') {
+      ++it;
+      components.emplace_back(head, std::distance(head, it));
+      head = it;
+      continue;
+    }
+    
+    if (*it == ':' && std::distance(Path.begin(), it) == 1) {
+      ++it;
+      components.emplace_back(head, std::distance(head, it));
+      head = it;
+      continue;
+    }
+
+    ++it;
+  }
+  if (head != end) {
+    components.emplace_back(head, std::distance(head, it));
+  }
+  return components;
+}
+
+/// Removes traversal components (".." and ".") as well as leading "./" and
+/// redundant slashes.  This accepts (and preserves) both slash directions.
+/// For use only on VFS paths, which may be in a hybrid of Windows and Posix
+/// styles.
 static llvm::SmallString<256> canonicalize(llvm::StringRef Path) {
-  // First detect the path style in use by checking the first separator.
-  llvm::sys::path::Style style = llvm::sys::path::Style::native;
-  const size_t n = Path.find_first_of("/\\");
-  if (n != static_cast<size_t>(-1))
-    style = (Path[n] == '/') ? llvm::sys::path::Style::posix
-                             : llvm::sys::path::Style::windows;
-
-  // Now remove the dots.  Explicitly specifying the path style prevents the
-  // direction of the slashes from changing.
-  llvm::SmallString<256> result =
-      llvm::sys::path::remove_leading_dotslash(Path, style);
-  llvm::sys::path::remove_dots(result, /*remove_dot_dot=*/true, style);
+  llvm::SmallString<256> result;
+  auto components = splitHybridPath(Path);
+
+  if (components.empty()) return result;
+
+  // Walk through the components, dropping the traversals.
+  auto source = components.begin();
+  auto target = components.begin();
+  const auto end = components.end();
+
+  if (source->size() == 2 && (*source)[1] == ':') {
+    // Starts with a drive letter, so keep it.
+    *target++ = *source++;
+  }
+
+  if (source != end && (*source == "/" || *source == "\\")) {
+    // This is an absolute path, so keep the root.
+    *target++ = *source++;
+  }
+
+  // A double dot cannot ascend above this point.
+  const auto limit = target;
+
+  while (source != end) {
+    if (*source == "/" || *source == "\\") {
+      // Redundant slashes should be dropped.
+      ++source;
+      continue;
+    }
+    if (*source == "./" || *source == ".\\" || *source == ".") {
+      // A dot goes nowhere, so just drop it.
+      ++source;
+      continue;
+    }
+    if (*source == "../" || *source == "..\\\\" || *source == "..") {
+      // Back up if we can.
+      if (target == limit) {
+        // We cannot ascend, so keep the dot-dot.
+        *target++ = *source++;
+        continue;
+      }
+
+      auto prev = target - 1;
+      if (*prev == "../" || *prev == "..\\\\") {
+        // We cannot ascend in this case, either.
+        *target++ = *source++;
+        continue;
+      }
+
+      // Ascend!
+      target = prev;
+      ++source;
+      continue;
+    }
+    // Everything else is a plain old path component.
+    *target++ = *source++;
+  }
+  components.erase(target, end);
+
+  // The canonical path is just the concatenation of the remaining components.
+  for (StringRef C : components) {
+    result.append(C.begin(), C.end());
+  }
+
+  // ... except that a trailing slash is redundant.
+  if (!result.empty() && (result.back() == '/' || result.back() == '\\')) {
+    result.pop_back();
+  }
+
   return result;
 }
 
 } // anonymous namespace
 
 
 RedirectingFileSystem::RedirectingFileSystem(IntrusiveRefCntPtr<FileSystem> FS)
     : ExternalFS(std::move(FS)) {