[clangd] Use all inputs to SystemIncludeExtractor in cache key

[kadircet]

Summary

Instead of passing in a tooling::CompileCommand into system include
extraction, pass a limited set, whose elements are used as keys.

Also fix the issue around accepting -isysroot=/foo which isn't a valid
argument (or the directory should be =/foo not /foo).

Fixes https://github.com/clangd/clangd/issues/1404
Fixes https://github.com/clangd/clangd/issues/1403

This should also unblock https://reviews.llvm.org/D138546

[nridge]

clang-tools-extra/clangd/SystemIncludeExtractor.cpp

83

It looks like the purpose of including Directory in the key is to use it in make_absolute in case where Driver is not an absolute path.

I wonder if it would make sense to perform that make_absolute operation eagerly and store its result in the key instead.

I'm thinking of a scenario where a project has say 10,000 source files in 500 directories, and in the compile_commands.json entries the directory is the directory immediately containing the source file (or a corresponding directory in a build/ directory hierarchy). In such cases, having the directory be in the key would mean executing the driver 500 times instead of just once (assuming no other properties are different) during indexing.

141

The previous behaviour was to abort system include extraction in this case.

Assuming you're not looking to change that behaviour, one way to preserve it could be to have render() check for an empty Lang and return an empty vector in that case, and also have extractSystemIncludesAndTarget() check for render() returning an empty vector and return an empty optional in that case.

clang-tools-extra/clangd/test/system-include-extractor.test

45

(did you mean to add -dump-input=fail here? according to FileCheck docs that's the default)

[kadircet]

clang-tools-extra/clangd/SystemIncludeExtractor.cpp

83

yeah makes sense. i was mostly trying to avoid the extra string operations, with the assumption of "directory" being ~always the same across entries. but we're already paying for those string operations today, so not saving them won't be a regression and being more resilient for such cases in the future wouldn't hurt.

141

thanks! definitely didn't notice that, I am not sure how valid of a concern this is in practice. as we'll only use the cached result for translation units whose language cannot be determined (I'd claim they all belong to same category). but leaving it as-is in this patch with a fixme (happy to drop the fixme if you think that's actually important). made it similar to existing code pattern, i.e. bailing out early if language is empty.

[kadircet]

• Address comments

[nridge]

Thanks!

Do you have any thoughts on merging D147905 first, with a view to backporting D147905 to the 16.x branch?

clang-tools-extra/clangd/SystemIncludeExtractor.cpp

81

nit: typo ("prgoram")

[kadircet]

Fix typo

[nridge]

In D146941#4264146, @nridge wrote:

Do you have any thoughts on merging D147905 first, with a view to backporting D147905 to the 16.x branch?

Since there are ongoing discussions about D147905, I don't want to hold this patch up -- please go ahead and merge it, and I will rebase that one as needed once we agree on an approach there.

clang-tools-extra/clangd/SystemIncludeExtractor.cpp

 // First argument of the command line received from underlying compilation
 // database is used as compiler driver path. Due to this arbitrary binary
 // execution, this mechanism is not used by default and only executes binaries
 // in the paths that are explicitly included by the user.
 
 #include "CompileCommands.h"
 #include "GlobalCompilationDatabase.h"
 #include "support/Logger.h"
-#include "support/Path.h"
+#include "support/Threading.h"
 #include "support/Trace.h"
 #include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/DiagnosticIDs.h"
+#include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Basic/TargetOptions.h"
 #include "clang/Driver/Types.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/ScopedPrinter.h"
-#include <algorithm>
+#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+#include <cstddef>
 #include <iterator>
-#include <map>
+#include <memory>
 #include <optional>
 #include <string>
+#include <tuple>
+#include <utility>
 #include <vector>
 
-namespace clang {
-namespace clangd {
+namespace clang::clangd {
 namespace {
 
 struct DriverInfo {
   std::vector<std::string> SystemIncludes;
   std::string Target;
 };
 
+struct DriverArgs {
+  // Name of the driver program to execute or absolute path to it.
+  std::string Driver;
+  // Whether certain includes should be part of query.
+  bool StandardIncludes = true;
+  bool StandardCXXIncludes = true;
+  bool BuiltinIncludes = true;
+  // Language to use while querying.
+  std::string Lang;
+  std::string Sysroot;
+  std::string ISysroot;
+
+  bool operator==(const DriverArgs &RHS) const {
+    return std::tie(Driver, StandardIncludes, StandardCXXIncludes,
+                    BuiltinIncludes, Lang, Sysroot, ISysroot) ==
+           std::tie(RHS.Driver, RHS.StandardIncludes, RHS.StandardCXXIncludes,
+                    RHS.BuiltinIncludes, RHS.Lang, RHS.Sysroot, ISysroot);
+  }
+
+  DriverArgs(const tooling::CompileCommand &Cmd, llvm::StringRef File) {
+    llvm::SmallString<128> Driver(Cmd.CommandLine.front());
+    // Driver is a not a single executable name but instead a path (either
+    // relative or absolute).
+    if (llvm::any_of(Driver,
+                     [](char C) { return llvm::sys::path::is_separator(C); })) {
+      llvm::sys::fs::make_absolute(Cmd.Directory, Driver);
+    }
+    this->Driver = Driver.str().str();
+    for (size_t I = 0, E = Cmd.CommandLine.size(); I < E; ++I) {
+      llvm::StringRef Arg = Cmd.CommandLine[I];
+
+      // Look for Language related flags.
+      if (Arg.consume_front("-x")) {
+        if (Arg.empty() && I + 1 < E)
+          Lang = Cmd.CommandLine[I + 1];
+        else
+          Lang = Arg.str();
+      }
+      // Look for standard/builtin includes.
+      else if (Arg == "-nostdinc" || Arg == "--no-standard-includes")
+        StandardIncludes = false;
+      else if (Arg == "-nostdinc++")
+        StandardCXXIncludes = false;
+      else if (Arg == "-nobuiltininc")
+        BuiltinIncludes = false;
+      // Figure out sysroot
+      else if (Arg.consume_front("--sysroot")) {
+        if (Arg.consume_front("="))
+          Sysroot = Arg.str();
+        else if (Arg.empty() && I + 1 < E)
+          Sysroot = Cmd.CommandLine[I + 1];
+      } else if (Arg.consume_front("-isysroot")) {
+        if (Arg.empty() && I + 1 < E)
+          ISysroot = Cmd.CommandLine[I + 1];
+        else
+          ISysroot = Arg.str();
+      }
+    }
+
+    // If language is not explicit in the flags, infer from the file.
+    // This is important as we want to cache each language separately.
+    if (Lang.empty()) {
+      llvm::StringRef Ext = llvm::sys::path::extension(File).trim('.');
+      auto Type = driver::types::lookupTypeForExtension(Ext);
+      if (Type == driver::types::TY_INVALID) {
+        elog("System include extraction: invalid file type for {0}", Ext);
+      } else {
+        Lang = driver::types::getTypeName(Type);
+      }
+    }
+  }
+  llvm::SmallVector<llvm::StringRef> render() const {
+    // FIXME: Don't treat lang specially?
+    assert(!Lang.empty());
+    llvm::SmallVector<llvm::StringRef> Args = {"-x", Lang};
+    if (!StandardIncludes)
+      Args.push_back("-nostdinc");
+    if (!StandardCXXIncludes)
+      Args.push_back("-nostdinc++");
+    if (!BuiltinIncludes)
+      Args.push_back("-nobuiltininc++");
+    if (!Sysroot.empty())
+      Args.append({"--sysroot", Sysroot});
+    if (!ISysroot.empty())
+      Args.append({"-isysroot", ISysroot});
+    return Args;
+  }
+
+  static DriverArgs getEmpty() { return {}; }
+
+private:
+  DriverArgs() = default;
+};
+} // namespace
+} // namespace clang::clangd
+namespace llvm {
+using DriverArgs = clang::clangd::DriverArgs;
+template <> struct DenseMapInfo<DriverArgs> {
+  static DriverArgs getEmptyKey() {
+    auto Driver = DriverArgs::getEmpty();
+    Driver.Driver = "EMPTY_KEY";
+    return Driver;
+  }
+  static DriverArgs getTombstoneKey() {
+    auto Driver = DriverArgs::getEmpty();
+    Driver.Driver = "TOMBSTONE_KEY";
+    return Driver;
+  }
+  static unsigned getHashValue(const DriverArgs &Val) {
+    return llvm::hash_value(std::tuple{
+        Val.Driver,
+        Val.StandardIncludes,
+        Val.StandardCXXIncludes,
+        Val.BuiltinIncludes,
+        Val.Lang,
+        Val.Sysroot,
+        Val.ISysroot,
+    });
+  }
+  static bool isEqual(const DriverArgs &LHS, const DriverArgs &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+namespace clang::clangd {
+namespace {
 bool isValidTarget(llvm::StringRef Triple) {
   std::shared_ptr<TargetOptions> TargetOpts(new TargetOptions);
   TargetOpts->Triple = Triple.str();
   DiagnosticsEngine Diags(new DiagnosticIDs, new DiagnosticOptions,
                           new IgnoringDiagConsumer);
-  IntrusiveRefCntPtr<TargetInfo> Target =
+  llvm::IntrusiveRefCntPtr<TargetInfo> Target =
       TargetInfo::CreateTargetInfo(Diags, TargetOpts);
   return bool(Target);
 }
 
 std::optional<DriverInfo> parseDriverOutput(llvm::StringRef Output) {
   DriverInfo Info;
   const char SIS[] = "#include <...> search starts here:";
   const char SIE[] = "End of search list.";
std::optional<DriverInfo> parseDriverOutput(llvm::StringRef Output) {
   if (State == IncludesExtracting) {
     elog("System include extraction: end marker missing: {0}", Output);
     return std::nullopt;
   }
   return std::move(Info);
 }
 
 std::optional<DriverInfo>
-extractSystemIncludesAndTarget(llvm::SmallString<128> Driver,
-                               llvm::StringRef Lang,
-                               llvm::ArrayRef<std::string> CommandLine,
+extractSystemIncludesAndTarget(const DriverArgs &InputArgs,
                                const llvm::Regex &QueryDriverRegex) {
   trace::Span Tracer("Extract system includes and target");
 
+  std::string Driver = InputArgs.Driver;
   if (!llvm::sys::path::is_absolute(Driver)) {
-    assert(llvm::none_of(
-        Driver, [](char C) { return llvm::sys::path::is_separator(C); }));
     auto DriverProgram = llvm::sys::findProgramByName(Driver);
     if (DriverProgram) {
       vlog("System include extraction: driver {0} expanded to {1}", Driver,
            *DriverProgram);
       Driver = *DriverProgram;
     } else {
       elog("System include extraction: driver {0} not found in PATH", Driver);
       return std::nullopt;
     }
   }
 
   SPAN_ATTACH(Tracer, "driver", Driver);
-  SPAN_ATTACH(Tracer, "lang", Lang);
+  SPAN_ATTACH(Tracer, "lang", InputArgs.Lang);
 
   if (!QueryDriverRegex.match(Driver)) {
     vlog("System include extraction: not allowed driver {0}", Driver);
     return std::nullopt;
   }
 
   llvm::SmallString<128> StdErrPath;
   if (auto EC = llvm::sys::fs::createTemporaryFile("system-includes", "clangd",
                                                    StdErrPath)) {
     elog("System include extraction: failed to create temporary file with "
          "error {0}",
          EC.message());
     return std::nullopt;
   }
   auto CleanUp = llvm::make_scope_exit(
       [&StdErrPath]() { llvm::sys::fs::remove(StdErrPath); });
 
   std::optional<llvm::StringRef> Redirects[] = {{""}, {""}, StdErrPath.str()};
 
-  llvm::SmallVector<llvm::StringRef> Args = {Driver, "-E", "-x",
-                                             Lang,   "-",  "-v"};
-
-  // These flags will be preserved
-  const llvm::StringRef FlagsToPreserve[] = {
-      "-nostdinc", "--no-standard-includes", "-nostdinc++", "-nobuiltininc"};
-  // Preserves these flags and their values, either as separate args or with an
-  // equalsbetween them
-  const llvm::StringRef ArgsToPreserve[] = {"--sysroot", "-isysroot"};
-
-  for (size_t I = 0, E = CommandLine.size(); I < E; ++I) {
-    llvm::StringRef Arg = CommandLine[I];
-    if (llvm::is_contained(FlagsToPreserve, Arg)) {
-      Args.push_back(Arg);
-    } else {
-      const auto *Found =
-          llvm::find_if(ArgsToPreserve, [&Arg](llvm::StringRef S) {
-            return Arg.startswith(S);
-          });
-      if (Found == std::end(ArgsToPreserve))
-        continue;
-      Arg = Arg.drop_front(Found->size());
-      if (Arg.empty() && I + 1 < E) {
-        Args.push_back(CommandLine[I]);
-        Args.push_back(CommandLine[++I]);
-      } else if (Arg.startswith("=")) {
-        Args.push_back(CommandLine[I]);
-      }
-    }
-  }
+  llvm::SmallVector<llvm::StringRef> Args = {Driver, "-E", "-v"};
+  Args.append(InputArgs.render());
+  // Input needs to go after Lang flags.
+  Args.push_back("-");
 
   std::string ErrMsg;
   if (int RC = llvm::sys::ExecuteAndWait(Driver, Args, /*Env=*/std::nullopt,
                                          Redirects, /*SecondsToWait=*/0,
                                          /*MemoryLimit=*/0, &ErrMsg)) {
     elog("System include extraction: driver execution failed with return code: "
          "{0} - '{1}'. Args: [{2}]",
          llvm::to_string(RC), ErrMsg, printArgv(Args));

 public:
   SystemIncludeExtractor(llvm::ArrayRef<std::string> QueryDriverGlobs)
       : QueryDriverRegex(convertGlobsToRegex(QueryDriverGlobs)) {}
 
   void operator()(tooling::CompileCommand &Cmd, llvm::StringRef File) const {
     if (Cmd.CommandLine.empty())
       return;
 
-    llvm::StringRef Lang;
-    for (size_t I = 0, E = Cmd.CommandLine.size(); I < E; ++I) {
-      llvm::StringRef Arg = Cmd.CommandLine[I];
-      if (Arg == "-x" && I + 1 < E)
-        Lang = Cmd.CommandLine[I + 1];
-      else if (Arg.startswith("-x"))
-        Lang = Arg.drop_front(2).trim();
-    }
-    if (Lang.empty()) {
-      llvm::StringRef Ext = llvm::sys::path::extension(File).trim('.');
-      auto Type = driver::types::lookupTypeForExtension(Ext);
-      if (Type == driver::types::TY_INVALID) {
-        elog("System include extraction: invalid file type for {0}", Ext);
-        return;
-      }
-      Lang = driver::types::getTypeName(Type);
-    }
-
-    llvm::SmallString<128> Driver(Cmd.CommandLine.front());
-    if (llvm::any_of(Driver,
-                     [](char C) { return llvm::sys::path::is_separator(C); }))
-      // Driver is a not a single executable name but instead a path (either
-      // relative or absolute).
-      llvm::sys::fs::make_absolute(Cmd.Directory, Driver);
-
-    if (auto Info =
-            QueriedDrivers.get(/*Key=*/(Driver + ":" + Lang).str(), [&] {
-              return extractSystemIncludesAndTarget(
-                  Driver, Lang, Cmd.CommandLine, QueryDriverRegex);
-            })) {
+    DriverArgs Args(Cmd, File);
+    if (Args.Lang.empty())
+    if (auto Info = QueriedDrivers.get(Args, [&] {
+          return extractSystemIncludesAndTarget(Args, QueryDriverRegex);
       setTarget(addSystemIncludes(Cmd, Info->SystemIncludes), Info->Target);
     }
   }
 
 private:
   // Caches includes extracted from a driver. Key is driver:lang.
-  Memoize<llvm::StringMap<std::optional<DriverInfo>>> QueriedDrivers;
+  Memoize<llvm::DenseMap<DriverArgs, std::optional<DriverInfo>>> QueriedDrivers;
   llvm::Regex QueryDriverRegex;
 };
 } // namespace
 
 SystemIncludeExtractorFn
 getSystemIncludeExtractor(llvm::ArrayRef<std::string> QueryDriverGlobs) {
   if (QueryDriverGlobs.empty())
     return nullptr;
   return SystemIncludeExtractor(QueryDriverGlobs);
 }
 
-} // namespace clangd
-} // namespace clang
+} // namespace clang::clangd

clang-tools-extra/clangd/test/system-include-extractor.test

 # RUN: rm -rf %t.dir && mkdir -p %t.dir
 
 # The mock driver below is a shell script:
 # REQUIRES: shell
 
 # Create a bin directory to store the mock-driver and add it to the path
 # RUN: mkdir -p %t.dir/bin
 # RUN: export PATH=%t.dir/bin:$PATH
 # Generate a mock-driver that will print %temp_dir%/my/dir and
 # %temp_dir%/my/dir2 as include search paths.
 # RUN: echo '#!/bin/sh' >> %t.dir/bin/my_driver.sh
 # RUN: echo '[ "$0" = "%t.dir/bin/my_driver.sh" ] || exit' >> %t.dir/bin/my_driver.sh
 # RUN: echo 'args="$*"' >> %t.dir/bin/my_driver.sh
 # Check that clangd preserves certain flags like `-nostdinc` from
 # original invocation in compile_commands.json.
 # RUN: echo '[ -z "${args##*"-nostdinc"*}" ] || exit' >> %t.dir/bin/my_driver.sh
-# RUN: echo '[ -z "${args##*"-isysroot=/isysroot"*}" ] || exit' >> %t.dir/bin/my_driver.sh
 # RUN: echo '[ -z "${args##*"--sysroot /my/sysroot/path"*}" ] || exit' >> %t.dir/bin/my_driver.sh
+# RUN: echo '[ -z "${args##*"-isysroot /isysroot"*}" ] || exit' >> %t.dir/bin/my_driver.sh
 # RUN: echo 'echo line to ignore >&2' >> %t.dir/bin/my_driver.sh
 # RUN: echo 'printf "Target: arm-linux-gnueabihf\r\n" >&2' >> %t.dir/bin/my_driver.sh
 # RUN: echo 'printf "#include <...> search starts here:\r\n" >&2' >> %t.dir/bin/my_driver.sh
 # RUN: echo 'echo %t.dir/my/dir/ >&2' >> %t.dir/bin/my_driver.sh
 # RUN: echo 'echo %t.dir/my/dir2/ >&2' >> %t.dir/bin/my_driver.sh
 # RUN: echo 'printf "End of search list.\r\n" >&2' >> %t.dir/bin/my_driver.sh
 # RUN: chmod +x %t.dir/bin/my_driver.sh
 
 # Create header files my/dir/a.h and my/dir2/b.h
 # RUN: mkdir -p %t.dir/my/dir
 # RUN: touch %t.dir/my/dir/a.h
 # RUN: mkdir -p %t.dir/my/dir2
 # RUN: touch %t.dir/my/dir2/b.h
 
 # Generate a compile_commands.json that will query the mock driver we've
 # created. Which should add a.h and b.h into include search path.
-# RUN: echo '[{"directory": "%/t.dir", "command": "my_driver.sh the-file.cpp -nostdinc --sysroot /my/sysroot/path -isysroot=/isysroot", "file": "the-file.cpp"}]' > %t.dir/compile_commands.json
+# RUN: echo '[{"directory": "%/t.dir", "command": "my_driver.sh the-file.cpp -nostdinc --sysroot /my/sysroot/path -isysroot/isysroot", "file": "the-file.cpp"}]' > %t.dir/compile_commands.json
 
 # RUN: sed -e "s|INPUT_DIR|%/t.dir|g" %s > %t.test.1
 # On Windows, we need the URI in didOpen to look like "uri":"file:///C:/..."
 # (with the extra slash in the front), so we add it here.
 # RUN: sed -E -e 's|"file://([A-Z]):/|"file:///\1:/|g' %t.test.1 > %t.test
 
 # Bless the mock driver we've just created so that clangd can execute it.
 # Note: include clangd's stderr in the FileCheck input with "2>&1" so that we
 # can match output lines like "ASTWorker building file"
 # RUN: clangd -lit-test -query-driver="**.test,**.sh" < %t.test 2>&1 | FileCheck -strict-whitespace %t.test
 {"jsonrpc":"2.0","id":0,"method":"initialize","params":{}}
 ---
 {
   "jsonrpc":"2.0",
   "method":"textDocument/didOpen",
   "params": {
     "textDocument": {
       "uri": "file://INPUT_DIR/the-file.cpp",

 # CHECK-NEXT:     "diagnostics": [],
 # CHECK-NEXT:     "uri": "file://{{.*}}/the-file.cpp",
 ---
 {"jsonrpc":"2.0","id":10000,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}
 
 # Generate a different compile_commands.json which does not point to the mock driver
-# RUN: echo '[{"directory": "%/t.dir", "command": "gcc the-file.cpp -nostdinc --sysroot /my/sysroot/path -isysroot=/isysroot", "file": "the-file.cpp"}]' > %t.dir/compile_commands.json
+# RUN: echo '[{"directory": "%/t.dir", "command": "gcc the-file.cpp -nostdinc --sysroot /my/sysroot/path -isysroot/isysroot", "file": "the-file.cpp"}]' > %t.dir/compile_commands.json
 
 # Generate a clangd config file which points to the mock driver instead
 # RUN: echo 'CompileFlags:' > %t.dir/.clangd
 # RUN: echo '  Compiler: my_driver.sh' >> %t.dir/.clangd
 
 # Run clangd a second time, to make sure it picks up the driver name from the config file
 # Note, we need to pass -enable-config because -lit-test otherwise disables it
 # RUN: clangd -lit-test -enable-config -query-driver="**.test,**.sh" < %t.test 2>&1 | FileCheck -strict-whitespace %t.test