Add support for case-insensitive header lookup

[hans]

Summary

This is useful when dealing with headers that are normally used on case-insensitive filesystems, such as the Windows SDK, when cross-compiling from a file-system that is case-sensitive (such as Linux). A prime example would be compiling "#include <windows.h>" (the file is really called Windows.h).

There has been a patch for this before (http://reviews.llvm.org/D2972), but this one is more general, as it works on the virtual filesystem layer, and also supports case-insensitive lookups of parent directories not just the filename.

I was initially worried about performance here. The most common case is trying to lookup a header file in the wrong include path, and instead of a simple stat, this patch will cause a full directory listing for each such attempt.

I tried a version of this patch that used a small Bloom filter for each directory to avoid unnecessary searches for non-existing files, but that broke a lot of modules tests. It seems those tests would end up writing to a module cache directory, but the vfs wasn't aware of those writes so subsequent attempts to open files in that directory would fail because of the filter (yay, cache invalidation). Maybe that could be fixed, and maybe such filtering would be useful for broadly too, but perhaps we could look at that separately.

I measured compile-time of a file in V8 on Linux with and without case-sensitive includes, and also with the filter:

Case sensitive: (default)   8.60s +- 2.90%
Case insensitive:           8.74s +- 1.18%
Case insensitive w/ filter: 8.46s +- 0.82%

Adding some folks who were on Saleem's patch.

[hans]

Add --show-includes test.

[compnerd]

This looks good to me. Thanks for picking this up! And thanks for the perf numbers!

lib/Basic/VirtualFileSystem.cpp

401

Probably can inline this in the header.

410

Thats slightly difficult to read (the E directory_iterator.

481

These two can probably be inlined into the header.

[hans]

Addressing Saleem's comments, and renaming the flag to -fcase-insensitive-paths, since this doesn't apply just to includes, but anything that goes through vfs, including the main source filename.

[thakis]

For performance: Can you check how build times for some large target in Chromium on Linux targeting Windows compares with this vs having the sdk in a fat mount? That would give us some data.

The discussion in the include case warning thread sounds like MS might update its headers to have #include lines matching actual file case, so hopefully this won't be needed at all eventually.

[hans]

In D21113#452431, @thakis wrote:

For performance: Can you check how build times for some large target in Chromium on Linux targeting Windows compares with this vs having the sdk in a fat mount? That would give us some data.

I measured compile times (perf stat -r5) of the same V8 file as above on Linux, but now targeting Windows:

SDK in vfat-mounted file:                       5.84s +- 1.91%
SDK on normal fs with -fcase-insensitive-paths: 7.18s +- 3.06%
As above, with directory bloom filters:         6.08s +- 0.76%

This makes my patch look slower, but it's a lot more convenient than setting up that file system.

The discussion in the include case warning thread sounds like MS might update its headers to have #include lines matching actual file case, so hopefully this won't be needed at all eventually.

That would be pretty cool!

lib/Basic/VirtualFileSystem.cpp

410

You're right. Moving the declaration of E to its own line further down.

[thakis]

Can you try building a few more files? Say, v8_base?

[hans]

In D21113#452558, @thakis wrote:

Can you try building a few more files? Say, v8_base?

Well, that was depressing:

Putting the sdk on a vfat fs:
real    2m26.077s
user    68m31.476s
sys     1m25.702s

Using the flag:
real    9m5.179s
user    69m3.417s
sys     212m47.136s  <--- !

Using the flag with bloom filters:
real    3m1.046s
user    69m5.328s
sys     19m4.368s

It seems the filesystem wasn't so happy about 32 processes doing a lot of readdir() at the same time.

[thakis]

Not sure if we want a flag that adds 50% overhead, no matter how convenient it might be :-/

[hans]

In D21113#452673, @thakis wrote:

Not sure if we want a flag that adds 50% overhead, no matter how convenient it might be :-/

I now have a version of the patch that caches directory contents that it lists:

real    2m31.461s
user    68m42.090s
sys     1m51.707s

While the sys time is a little bit higher, real time is on par with putting the SDK on FAT, so I think this is still worth pursuing. I need to clean up the patch and figure out how to invalidate the cache after module things are written, though.

[hans]

Adding the version that caches directory contents.

This has the problem the it doesn't play with modules, the rewriter, and possibly others, because they write to the file system without any way for the vfs to find out. I've tried to find a good way to fix that, but didn't come up with anything. One way would be to maintain a global counter like llvm::sys::fileSystemChangeCount which when changed would invalidate the maps, but I don't know if that would be acceptable.

[sheu]

I'd be very interested in seeing this patch happen. What's the current status here?

Also, w.r.t. the cache invalidation problem -- would it be feasible / a good idea to move users of the FileSystem API to VirtualFileSystem, in general? This would have the nice effect of putting filesystem things all in once place. Then invalidation tracking etc. will be easier.

[francisco.lopes]

I'm waiting for this to land as well, it's crucial for coding windows code with libclang assistance on a linux machine.

[pcc]

lib/Basic/VirtualFileSystem.cpp

483

I wonder whether it would help with performance to try the original path here first, then do the case insensitive stuff only if that failed.

[hans]

In D21113#627413, @francisco.lopes wrote:

I'm waiting for this to land as well, it's crucial for coding windows code with libclang assistance on a linux machine.

I'm not actively working on this, so it might take a while.

In the meantime, I recommend mounting a case-insensitive file system on your linux machine.

[Yoav]

Any progress with this? @hans its been stale for a while now and this feature is crucial

[hans]

In D21113#2859165, @Yoav wrote:

Any progress with this? @hans its been stale for a while now and this feature is crucial

No progress, I'm afraid. I'm not working on this, so someone would have to take over the patch to push it forward.

include/clang/Basic/VirtualFileSystem.h

public:
   /// \brief Get an iterator pointing to the most recently added file system.
   iterator overlays_begin() { return FSList.rbegin(); }
 
   /// \brief Get an iterator pointing one-past the least recently added file
   /// system.
   iterator overlays_end() { return FSList.rend(); }
 };
 
+class CaseInsensitiveFileSystem : public FileSystem {
+  IntrusiveRefCntPtr<FileSystem> Base;
+
+  /// Try to find Path by means of case-insensitive lookup. Stores the result in
+  /// FoundPath on success, or returns an error code otherwise.
+  std::error_code findCaseInsensitivePath(StringRef Path,
+                                          SmallVectorImpl<char> &FoundPath);
+
+  /// Attempt to exclude the possibility that File exists in Dir based on
+  /// previous information.
+  bool exclude(StringRef Dir, StringRef File);
+
+  /// Map from directory to map from lowercase to real-case filename.
+  llvm::StringMap<llvm::StringMap<std::string>> Maps;
+
+public:
+  CaseInsensitiveFileSystem(IntrusiveRefCntPtr<FileSystem> Base) : Base(Base) {}
+
+  llvm::ErrorOr<Status> status(const Twine &Path) override;
+  llvm::ErrorOr<std::unique_ptr<File>>
+  openFileForRead(const Twine &Path) override;
+  directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override;
+  llvm::ErrorOr<std::string> getCurrentWorkingDirectory() const override {
+    return Base->getCurrentWorkingDirectory();
+  }
+  std::error_code setCurrentWorkingDirectory(const Twine &Path) override {
+    Maps.clear();
+    return Base->setCurrentWorkingDirectory(Path);
+  }
+};
+
 namespace detail {
 class InMemoryDirectory;
 } // end namespace detail
 
 /// An in-memory file system.
 class InMemoryFileSystem : public FileSystem {
   std::unique_ptr<detail::InMemoryDirectory> Root;
   std::string WorkingDirectory;

include/clang/Driver/Options.td

 def fclasspath_EQ : Joined<["-"], "fclasspath=">, Group<f_Group>;
 def fcolor_diagnostics : Flag<["-"], "fcolor-diagnostics">, Group<f_Group>,
   Flags<[CoreOption, CC1Option]>, HelpText<"Use colors in diagnostics">;
 def fdiagnostics_color : Flag<["-"], "fdiagnostics-color">, Group<f_Group>,
   Flags<[CoreOption, DriverOption]>;
 def fdiagnostics_color_EQ : Joined<["-"], "fdiagnostics-color=">, Group<f_Group>;
 def fansi_escape_codes : Flag<["-"], "fansi-escape-codes">, Group<f_Group>,
   Flags<[CoreOption, CC1Option]>, HelpText<"Use ANSI escape codes for diagnostics">;
+def fcase_insensitive_paths : Flag<["-"], "fcase-insensitive-paths">, Group<f_Group>,
+  Flags<[CC1Option, CoreOption]>, HelpText<"Treat file paths as case-insensitive">;
 def fcomment_block_commands : CommaJoined<["-"], "fcomment-block-commands=">, Group<f_clang_Group>, Flags<[CC1Option]>,
   HelpText<"Treat each comma separated argument in <arg> as a documentation comment block command">,
   MetaVarName<"<arg>">;
 def fparse_all_comments : Flag<["-"], "fparse-all-comments">, Group<f_clang_Group>, Flags<[CC1Option]>;
 def fcommon : Flag<["-"], "fcommon">, Group<f_Group>;
 def fcompile_resource_EQ : Joined<["-"], "fcompile-resource=">, Group<f_Group>;
 def fconstant_cfstrings : Flag<["-"], "fconstant-cfstrings">, Group<f_Group>;
 def fconstant_string_class_EQ : Joined<["-"], "fconstant-string-class=">, Group<f_Group>;

include/clang/Lex/HeaderSearchOptions.h

public:
   unsigned UseStandardCXXIncludes : 1;
 
   /// Use libc++ instead of the default libstdc++.
   unsigned UseLibcxx : 1;
 
   /// Whether header search information should be output as for -v.
   unsigned Verbose : 1;
 
+  /// Whether header search should be case-insensitive.
+  unsigned CaseInsensitive : 1;
+
   /// \brief If true, skip verifying input files used by modules if the
   /// module was already verified during this build session (see
   /// \c BuildSessionTimestamp).
   unsigned ModulesValidateOncePerBuildSession : 1;
 
   /// \brief Whether to validate system input files when a module is loaded.
   unsigned ModulesValidateSystemHeaders : 1;
 

lib/Basic/VirtualFileSystem.cpp

 } // end anonymous namespace
 
 directory_iterator OverlayFileSystem::dir_begin(const Twine &Dir,
                                                 std::error_code &EC) {
   return directory_iterator(
       std::make_shared<OverlayFSDirIterImpl>(Dir, *this, EC));
 }
 
+//===-----------------------------------------------------------------------===/
+// CaseInsensitiveFileSystem implementation
+//===-----------------------------------------------------------------------===/
+
+bool CaseInsensitiveFileSystem::exclude(StringRef Dir, StringRef File) {
+  if (!Maps.count(Dir)) {
+    // We have no map for this Dir, but see if we can exclude the file by
+    // excluding Dir from its parent.
+    StringRef Parent = llvm::sys::path::parent_path(Dir);
+    if (!Parent.empty() &&
+        exclude(Parent, llvm::sys::path::filename(Dir))) {
+      return true;
+    }
+
+    return false;
+  }
+
+  return !Maps[Dir].count(File.lower());
+}
+
+std::error_code CaseInsensitiveFileSystem::findCaseInsensitivePath(
+    StringRef Path, SmallVectorImpl<char> &FoundPath) {
+  StringRef FileName = llvm::sys::path::filename(Path);
+  StringRef Dir = llvm::sys::path::parent_path(Path);
+
+  if (Dir.empty())
+    Dir = ".";
+
+  if (exclude(Dir, FileName))
+    return llvm::errc::no_such_file_or_directory;
+
+  if (Maps.count(Dir)) {
+    // If we have a map for this Dir and File wasn't excluded above, it must
+    // exist.
+    llvm::sys::path::append(FoundPath, Dir, Maps[Dir][FileName.lower()]);
+    return std::error_code();
+  }
+
+  std::error_code EC;
+  directory_iterator I = Base->dir_begin(Dir, EC);
+  if (EC == errc::no_such_file_or_directory) {
+    // If the dir doesn't exist, try to find it and try again.
+    SmallVector<char, 512> NewDir;
+    if (llvm::sys::path::parent_path(Dir).empty() ||
+        (EC = findCaseInsensitivePath(Dir, NewDir))) {
+      // Insert a dummy map value to mark the dir as non-existent.
+      Maps.lookup(Dir);
+      return EC;
+    }
+    llvm::sys::path::append(NewDir, FileName);
+    return findCaseInsensitivePath(StringRef(NewDir.data(), NewDir.size()),
+                                   FoundPath);
+  }
+
+  // These special entries always exist, but won't show up in the listing below.
+  Maps[Dir]["."] = ".";
+  Maps[Dir][".."] = "..";
+
+  directory_iterator E;
+  for (; !EC && I != E; I.increment(EC)) {
+    StringRef DirEntry = llvm::sys::path::filename(I->getName());
+    Maps[Dir][DirEntry.lower()] = DirEntry;
+  }
+  if (EC) {
+    // If there were problems, scrap the whole map as it may not be complete.
+    Maps.erase(Dir);
+    return EC;
+  }
+
+  auto MI = Maps[Dir].find(FileName.lower());
+  if (MI != Maps[Dir].end()) {
+    llvm::sys::path::append(FoundPath, Dir, MI->second);
+    return std::error_code();
+  }
+
+  return llvm::errc::no_such_file_or_directory;
+}
+
+llvm::ErrorOr<Status> CaseInsensitiveFileSystem::status(const Twine &Path) {
+  SmallVector<char, 512> NewPath;
+  if (std::error_code EC = findCaseInsensitivePath(Path.str(), NewPath))
+    return EC;
+
+  return Base->status(NewPath);
+}
+
+llvm::ErrorOr<std::unique_ptr<File>>
+CaseInsensitiveFileSystem::openFileForRead(const Twine &Path) {
+  SmallVector<char, 512> NewPath;
+  if (std::error_code EC = findCaseInsensitivePath(Path.str(), NewPath))
+    return EC;
+
+  return Base->openFileForRead(NewPath);
+}
+
+directory_iterator CaseInsensitiveFileSystem::dir_begin(const Twine &Path,
+                                                        std::error_code &EC) {
+  SmallVector<char, 512> NewPath;
+  if ((EC = findCaseInsensitivePath(Path.str(), NewPath)))
+    return directory_iterator();
+
+  return Base->dir_begin(NewPath, EC);
+}
+
 namespace clang {
 namespace vfs {
 namespace detail {
 
 enum InMemoryNodeKind { IME_File, IME_Directory };
 
 /// The in memory file system is a tree of Nodes. Every node can either be a
 /// file or a directory.

lib/Driver/Tools.cpp

void Clang::AddPreprocessingOptions(Compilation &C, const JobAction &JA,
   // Add system include arguments.
   getToolChain().AddClangSystemIncludeArgs(Args, CmdArgs);
   if (AuxToolChain)
       AuxToolChain->AddClangCXXStdlibIncludeArgs(Args, CmdArgs);
 
   // Add CUDA include arguments, if needed.
   if (types::isCuda(Inputs[0].getType()))
     getToolChain().AddCudaIncludeArgs(Args, CmdArgs);
+
+  if (Args.hasArg(options::OPT_fcase_insensitive_paths))
+    CmdArgs.push_back("-fcase-insensitive-paths");
 }
 
 // FIXME: Move to target hook.
 static bool isSignedCharDefault(const llvm::Triple &Triple) {
   switch (Triple.getArch()) {
   default:
     return true;
 

lib/Frontend/CompilerInvocation.cpp

static void ParseHeaderSearchArgs(HeaderSearchOptions &Opts, ArgList &Args) {
   // Add the path prefixes which are implicitly treated as being system headers.
   for (const Arg *A :
        Args.filtered(OPT_system_header_prefix, OPT_no_system_header_prefix))
     Opts.AddSystemHeaderPrefix(
         A->getValue(), A->getOption().matches(OPT_system_header_prefix));
 
   for (const Arg *A : Args.filtered(OPT_ivfsoverlay))
     Opts.AddVFSOverlayFile(A->getValue());
+
+  Opts.CaseInsensitive = Args.hasArg(OPT_fcase_insensitive_paths);
 }
 
 void CompilerInvocation::setLangDefaults(LangOptions &Opts, InputKind IK,
                                          const llvm::Triple &T,
                                          LangStandard::Kind LangStd) {
   // Set some properties which depend solely on the input kind; it would be nice
   // to move these to the language standard, and have the driver resolve the
   // input kind + language standard.
void BuryPointer(const void *Ptr) {
   LLVM_ATTRIBUTE_UNUSED static const void *GraveYard[kGraveYardMaxSize];
   static std::atomic<unsigned> GraveYardSize;
   unsigned Idx = GraveYardSize++;
   if (Idx >= kGraveYardMaxSize)
     return;
   GraveYard[Idx] = Ptr;
 }
 
-IntrusiveRefCntPtr<vfs::FileSystem>
-createVFSFromCompilerInvocation(const CompilerInvocation &CI,
-                                DiagnosticsEngine &Diags) {
-  if (CI.getHeaderSearchOpts().VFSOverlayFiles.empty())
-    return vfs::getRealFileSystem();
-
+static IntrusiveRefCntPtr<vfs::FileSystem>
+getOverlayFS(const CompilerInvocation &CI, DiagnosticsEngine &Diags) {
   IntrusiveRefCntPtr<vfs::OverlayFileSystem>
     Overlay(new vfs::OverlayFileSystem(vfs::getRealFileSystem()));
   // earlier vfs files are on the bottom
   for (const std::string &File : CI.getHeaderSearchOpts().VFSOverlayFiles) {
     llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Buffer =
         llvm::MemoryBuffer::getFile(File);
     if (!Buffer) {
       Diags.Report(diag::err_missing_vfs_overlay_file) << File;
       return IntrusiveRefCntPtr<vfs::FileSystem>();
     }
 
     IntrusiveRefCntPtr<vfs::FileSystem> FS = vfs::getVFSFromYAML(
         std::move(Buffer.get()), /*DiagHandler*/ nullptr, File);
     if (!FS.get()) {
       Diags.Report(diag::err_invalid_vfs_overlay) << File;
       return IntrusiveRefCntPtr<vfs::FileSystem>();
     }
     Overlay->pushOverlay(FS);
   }
   return Overlay;
 }
+
+IntrusiveRefCntPtr<vfs::FileSystem>
+createVFSFromCompilerInvocation(const CompilerInvocation &CI,
+                                DiagnosticsEngine &Diags) {
+  IntrusiveRefCntPtr<vfs::FileSystem> FS;
+
+  if (CI.getHeaderSearchOpts().VFSOverlayFiles.empty())
+    FS = vfs::getRealFileSystem();
+  else
+    FS = getOverlayFS(CI, Diags);
+
+  if (CI.getHeaderSearchOpts().CaseInsensitive)
+    FS = new vfs::CaseInsensitiveFileSystem(FS);
+
+  return FS;
+}
 } // end namespace clang

test/Driver/cl-options.c

 // RUN:     -fsyntax-only \
 // RUN:     -fms-compatibility \
 // RUN:     -fno-ms-compatibility \
 // RUN:     -fms-extensions \
 // RUN:     -fno-ms-extensions \
 // RUN:     -mllvm -disable-llvm-optzns \
 // RUN:     -Wunused-variable \
 // RUN:     -fmacro-backtrace-limit=0 \
+// RUN:     -fcase-insensitive-paths \
 // RUN:     -Werror /Zs -- %s 2>&1
 
 
 void f() { }

test/Frontend/case-insensitive-paths.c

+// RUN: %clang_cc1 -fsyntax-only -fcase-insensitive-paths -verify %s
+// RUN: %clang_cc1 -fsyntax-only --show-includes -fcase-insensitive-paths %s | FileCheck %s
+
+#include "InpUts/CasE-InsensitivE-Paths.h" // expected-no-diagnostics
+
+// Make sure the real filename is used when printing header dependencies.
+// CHECK: including file: {{.*}}case-insensitive-paths.h

unittests/Basic/VirtualFileSystemTest.cpp

std::error_code increment() override {
       if (I == FilesAndDirs.end())
         CurrentEntry = vfs::Status();
       return std::error_code();
     }
   };
 
   vfs::directory_iterator dir_begin(const Twine &Dir,
                                     std::error_code &EC) override {
-    return vfs::directory_iterator(
+    auto I = vfs::directory_iterator(
         std::make_shared<DirIterImpl>(FilesAndDirs, Dir));
+
+    // Even if there is no entry for /foo, /foo/bar may exist, so only set the
+    // error code if /foo returns an empty iterator.
+    if (I == vfs::directory_iterator())
+      EC = status(Dir).getError();
+
+    return I;
   }
 
   void addEntry(StringRef Path, const vfs::Status &Status) {
     FilesAndDirs[Path] = Status;
   }
 
   void addRegularFile(StringRef Path, sys::fs::perms Perms = sys::fs::all_all) {
     vfs::Status S(Path, UniqueID(FSID, FileID++), sys::TimeValue::now(), 0, 0,
vfs::recursive_directory_iterator I = vfs::recursive_directory_iterator(
                                         *O, "//root", EC), E;
   ASSERT_FALSE(EC);
   for (int l = 0; I != E; I.increment(EC), ++l) {
     ASSERT_FALSE(EC);
     EXPECT_EQ(I.level(), l);
   }
   EXPECT_EQ(I, E);
 }
+
+class CaseInsensitiveFileSystemTest : public ::testing::Test {
+private:
+  IntrusiveRefCntPtr<DummyFileSystem> Base;
+
+protected:
+  IntrusiveRefCntPtr<clang::vfs::FileSystem> FS;
+
+  CaseInsensitiveFileSystemTest()
+      : Base(new DummyFileSystem()),
+        FS(new clang::vfs::CaseInsensitiveFileSystem(Base)) {
+    Base->addRegularFile("/foo");
+    Base->addDirectory("/bar");
+    Base->addRegularFile("/bar/baz");
+  }
+};
+
+TEST_F(CaseInsensitiveFileSystemTest, Basic) {
+  // Not just accepting anything.
+  auto Status = FS->status("/F00");
+  ASSERT_EQ(llvm::errc::no_such_file_or_directory, Status.getError());
+
+  // Case-insensitive file is found.
+  Status = FS->status("/FoO");
+  ASSERT_FALSE(Status.getError());
+
+  // Case-insensitive dir works too.
+  Status = FS->status("/bAr/baZ");
+  ASSERT_FALSE(Status.getError());
+
+  // Test openFileForRead.
+  auto File = FS->openFileForRead("/F00");
+  ASSERT_EQ(llvm::errc::no_such_file_or_directory, File.getError());
+  File = FS->openFileForRead("/Foo");
+  ASSERT_FALSE(File.getError());
+  File = FS->openFileForRead("/Bar/Baz");
+  ASSERT_FALSE(File.getError());
+
+  // Test directory listing.
+  std::error_code EC;
+  auto Dir = FS->dir_begin("/b4r", EC);
+  ASSERT_EQ(llvm::errc::no_such_file_or_directory, EC);
+  Dir = FS->dir_begin("/bAr", EC);
+  ASSERT_FALSE(EC);
+  ASSERT_EQ("/bar/baz", Dir->getName());
+  Dir.increment(EC);
+  ASSERT_FALSE(EC);
+  ASSERT_EQ(vfs::directory_iterator(), Dir);
+}