[VFS] Reapply #2: Reconstruct the VFS overlay tree for more accurate lookup

Reapply r269100 and r269270, reverted due to
https://llvm.org/bugs/show_bug.cgi?id=27725. Isolate the testcase that
corresponds to the new feature side of this commit and skip it on
windows hosts until we find why it does not work on these platforms.

Original commit message:

The way we currently build the internal VFS overlay representation leads
to inefficient path search and might yield wrong answers when asked for
recursive or regular directory iteration.

Currently, when reading an YAML file, each YAML root entry is placed
inside a new root in the filesystem overlay. In the crash reproducer, a
simple "@import Foundation" currently maps to 43 roots, and when looking
up paths, we traverse a directory tree for each of these different
roots, until we find a match (or don't). This has two consequences:

- It's slow.
- Directory iteration gives incomplete results since it only return
results within one root - since contents of the same directory can be
declared inside different roots, the result isn't accurate.

This is in part fault of the way we currently write out the YAML file
when emitting the crash reproducer - we could generate only one root and
that would make it fast and correct again. However, we should not rely
on how the client writes the YAML, but provide a good internal
representation regardless.

Build a proper virtual directory tree out of the YAML representation,
allowing faster search and proper iteration. Besides the crash
reproducer, this potentially benefits other VFS clients.

llvm-svn: 269327

1 files changed, 56 insertions, 0 deletions

diff --git a/clang/unittests/Basic/VirtualFileSystemTest.cpp b/clang/unittests/Basic/VirtualFileSystemTest.cpp
index 992f0d8..a33f2b1 100644
--- a/clang/unittests/Basic/VirtualFileSystemTest.cpp
+++ b/clang/unittests/Basic/VirtualFileSystemTest.cpp
@@ -8,7 +8,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "clang/Basic/VirtualFileSystem.h"
+#include "llvm/ADT/Triple.h"
 #include "llvm/Support/Errc.h"
+#include "llvm/Support/Host.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/SourceMgr.h"
@@ -680,6 +682,12 @@ public:
     VersionPlusContent += Content.slice(Content.find('{') + 1, StringRef::npos);
     return getFromYAMLRawString(VersionPlusContent, ExternalFS);
   }
+
+  // This is intended as a "XFAIL" for windows hosts.
+  bool supportsSameDirMultipleYAMLEntries() {
+    Triple Host(Triple::normalize(sys::getProcessTriple()));
+    return !Host.isOSWindows();
+  }
 };
 
 TEST_F(VFSFromYAMLTest, BasicVFSFromYAML) {
@@ -1066,3 +1074,51 @@ TEST_F(VFSFromYAMLTest, DirectoryIteration) {
   checkContents(O->dir_begin("//root/foo/bar", EC),
                 {"//root/foo/bar/a", "//root/foo/bar/b"});
 }
+
+TEST_F(VFSFromYAMLTest, DirectoryIterationSameDirMultipleEntries) {
+  // https://llvm.org/bugs/show_bug.cgi?id=27725
+  if (!supportsSameDirMultipleYAMLEntries())
+    return;
+
+  IntrusiveRefCntPtr<DummyFileSystem> Lower(new DummyFileSystem());
+  Lower->addDirectory("//root/zab");
+  Lower->addDirectory("//root/baz");
+  Lower->addRegularFile("//root/zab/a");
+  Lower->addRegularFile("//root/zab/b");
+  IntrusiveRefCntPtr<vfs::FileSystem> FS = getFromYAMLString(
+      "{ 'use-external-names': false,\n"
+      "  'roots': [\n"
+      "{\n"
+      "  'type': 'directory',\n"
+      "  'name': '//root/baz/',\n"
+      "  'contents': [ {\n"
+      "                  'type': 'file',\n"
+      "                  'name': 'x',\n"
+      "                  'external-contents': '//root/zab/a'\n"
+      "                }\n"
+      "              ]\n"
+      "},\n"
+      "{\n"
+      "  'type': 'directory',\n"
+      "  'name': '//root/baz/',\n"
+      "  'contents': [ {\n"
+      "                  'type': 'file',\n"
+      "                  'name': 'y',\n"
+      "                  'external-contents': '//root/zab/b'\n"
+      "                }\n"
+      "              ]\n"
+      "}\n"
+      "]\n"
+      "}",
+      Lower);
+  ASSERT_TRUE(FS.get() != nullptr);
+
+  IntrusiveRefCntPtr<vfs::OverlayFileSystem> O(
+      new vfs::OverlayFileSystem(Lower));
+  O->pushOverlay(FS);
+
+  std::error_code EC;
+
+  checkContents(O->dir_begin("//root/baz/", EC),
+                {"//root/baz/x", "//root/baz/y"});
+}