[clang][deps] Fix traversal of precompiled dependencies

[jansvoboda11]

Summary

The code for traversing precompiled dependencies is somewhat complicated and contains a dangling iterator bug.

This patch simplifies the code and fixes the bug.

[dexonsmith]

I'm not a big fan of moving to the recursive call. Creating a separate StringMap for each iteration seems awfully wasteful.

I'd prefer fixing the iterative algorithm so that it's correct and easy to verify. This can be done with a stack that points at the stable pointers into the StringMap:

StringMap<std::string> Imports;
SmallVector<StringMapEntry<std::string> *> Worklist;
PrebuiltModuleListener Listener(Imports, Worklist, InputFiles, VisitInputFiles);

while (!Worklist.empty()) {
  StringMapEntry<std::string> *Import = Worklist.pop_back_val();
  // Deal with "Import".
}

and in PrebuiltModuleListener only push to the worklist for newly-discovered imports:

void visitImport(StringRef ModuleName, StringRef Filename) override {
  auto I = PrebuiltModuleFiles.insert({ModuleName, Filename.str()});
  if (I.second)
    Worklist.push_back(&*I.first);
}

Also, is it possible to add a test to exercise the (fixed) the dangling iterator bug?

[jansvoboda11]

Throw away recursive implementation, add reproducer

[jansvoboda11]

Fair enough, iterative implementation will be better.

I simplified it a bit by using the in-out parameter ModuleFiles to keep track of visited files. I also switched to using SmallVector for the newly discovered (not-yet-visited) imports, which allows using the suggested pop_back_val and avoids using (potentially dangling) iterator.

The test case is a bit unwieldy, since the old implementation only failed when the StringMap got rehashed (with 16 entries).

[dexonsmith]

LGTM, with another comment inline (up to you whether to do something with it).

clang/lib/Tooling/DependencyScanning/DependencyScanningWorker.cpp

87

These filenames will usually be longer than std::string's small storage, requiring separate heap allocations for each filename. Can the worklist just point at the stable pointer StringMapEntry<std::string>*, where a filename copy and heap allocation has already been made? (This has also has a nice side effect of handling 3x as many worklist items before needing to allocate, since the element size goes from 24B to 8B.)

clang/test/ClangScanDeps/modules-pch-dangling.c

11 ↗

(On Diff #415380)

split-file makes this so-called "unwieldy" testcase amazingly easy to read!

clang/lib/Tooling/DependencyScanning/DependencyScanningWorker.cpp

 
 /// Visit the given prebuilt module and collect all of the modules it
 /// transitively imports and contributing input files.
 static void visitPrebuiltModule(StringRef PrebuiltModuleFilename,
                                 CompilerInstance &CI,
                                 PrebuiltModuleFilesT &ModuleFiles,
                                 llvm::StringSet<> &InputFiles,
                                 bool VisitInputFiles) {
-  // Maps the names of modules that weren't yet visited to their PCM path.
-  llvm::StringMap<std::string> ModuleFilesWorklist;
-  // Contains PCM paths of all visited modules.
-  llvm::StringSet<> VisitedModuleFiles;
-
-  PrebuiltModuleListener Listener(ModuleFilesWorklist, InputFiles,
-                                  VisitInputFiles);
-
-  auto GatherModuleFileInfo = [&](StringRef ASTFile) {
-    ASTReader::readASTFileControlBlock(
-        ASTFile, CI.getFileManager(), CI.getPCHContainerReader(),
-        /*FindModuleFileExtensions=*/false, Listener,
-        /*ValidateDiagnosticOptions=*/false);
-  };
-
-  GatherModuleFileInfo(PrebuiltModuleFilename);
-  while (!ModuleFilesWorklist.empty()) {
-    auto WorklistItemIt = ModuleFilesWorklist.begin();
+  // Maps the names of imported modules to their PCM paths.
+  llvm::StringMap<std::string> Imports;
+  PrebuiltModuleListener Listener(Imports, InputFiles, VisitInputFiles);
+      PrebuiltModuleFilename, CI.getFileManager(), CI.getPCHContainerReader(),
 
-    if (!VisitedModuleFiles.contains(WorklistItemIt->getValue())) {
-      VisitedModuleFiles.insert(WorklistItemIt->getValue());
-      GatherModuleFileInfo(WorklistItemIt->getValue());
-      ModuleFiles[WorklistItemIt->getKey().str()] = WorklistItemIt->getValue();
-    }
-
-    ModuleFilesWorklist.erase(WorklistItemIt);
-  }
+  for (const auto &Import : Imports)
+    if (ModuleFiles.insert({Import.getKey().str(), Import.getValue()}).second)
+      visitPrebuiltModule(Import.getValue(), CI, ModuleFiles, InputFiles,
+                          VisitInputFiles);
 }
 
 /// Transform arbitrary file name into an object-like file name.
 static std::string makeObjFileName(StringRef FileName) {
   SmallString<128> ObjFileName(FileName);
   llvm::sys::path::replace_extension(ObjFileName, "o");
   return std::string(ObjFileName.str());
 }