[clang][modules] Track included files per submodule

[jansvoboda11]

Summary

When building a module consisting of submodules, the preprocessor maintains a global set of included headers. This information gets serialized into the PCM file (specifically into the HeaderFileInfo table). After loading such PCM file, this information is deserialized into the state of the importing preprocessor. This happens even if the headers were included by (sub)modules that are not visible. This can incorrectly prevent imports of textual headers in the importing instance (see attached tests).

This patch fixes this bug splitting the set of included files per submodule. This is an alternative to D112915 and D104344.

[jansvoboda11]

Note to self: lost the change that bumps PCM format version during a rebase. Make sure to increment the major version before committing.

clang/include/clang/Lex/Preprocessor.h

private:
 
   /// The preprocessor state for preprocessing outside of any submodule.
   SubmoduleState NullSubmoduleState;
 
   /// The current submodule state. Will be \p NullSubmoduleState if we're not
   /// in a submodule.
   SubmoduleState *CurSubmoduleState;
 
+  /// The set of files that have been included in each submodule.
+  /// Files included outside of any module (e.g. in PCH) have nullptr key.
+  llvm::DenseMap<Module *, IncludedFilesSet> IncludedFilesPerSubmodule;
+
   /// The files that have been included.
   IncludedFilesSet IncludedFiles;
 
   /// The set of top-level modules that affected preprocessing, but were not
   /// imported.
   llvm::SmallSetVector<Module *, 2> AffectingClangModules;
 
   /// The set of known macros exported from modules.
public:
   }
 
   /// Get the set of top-level clang modules that affected preprocessing, but were not
   /// imported.
   const llvm::SmallSetVector<Module *, 2> &getAffectingClangModules() const {
     return AffectingClangModules;
   }
 
-  /// Mark the file as included.
+  /// Mark the file as included in the current state.
+  /// Do not attribute it to the current module - this file was included by one
+  /// of its dependencies (transitively).
+  void markTransitivelyIncluded(const FileEntry *File) {
+    HeaderInfo.getFileInfo(File);
+    IncludedFiles.insert(File);
+  }
+
+  /// Mark the file as included in the current state and attribute it to the
+  /// current module.
   /// Returns true if this is the first time the file was included.
-  bool markIncluded(const FileEntry *File) {
+  bool markDirectlyIncluded(const FileEntry *File) {
     HeaderInfo.getFileInfo(File);
+
+    Module *M = !BuildingSubmoduleStack.empty()
+                    ? BuildingSubmoduleStack.back().M
+                    : getCurrentModule();
+    IncludedFilesPerSubmodule[M].insert(File);
+
     return IncludedFiles.insert(File).second;
   }
 
   /// Return true if this header has already been included.
   bool alreadyIncluded(const FileEntry *File) const {
     HeaderInfo.getFileInfo(File);
     return IncludedFiles.count(File);
   }
 
+  /// Invoke the callback for every module known to include the given file.
+  void forModulesIncluding(const FileEntry *FE,
+                           llvm::function_ref<void(Module *)> Cb) {
+    // TODO: Maintain a data-structure that provides this more efficiently.
+    for (const auto &Entry : IncludedFilesPerSubmodule)
+      if (Entry.second.contains(FE))
+        Cb(Entry.first);
+  }
+
+  /// Get the set of files included in the given module.
+  IncludedFilesSet &getFilesIncludedIn(Module *M) {
+    return IncludedFilesPerSubmodule[M];
+  }
+
   /// Get the set of included files.
   IncludedFilesSet &getIncludedFiles() { return IncludedFiles; }
   const IncludedFilesSet &getIncludedFiles() const { return IncludedFiles; }
 
   /// Return the name of the macro defined before \p Loc that has
   /// spelling \p Tokens.  If there are multiple macros with same spelling,
   /// return the last one defined.
   StringRef getLastMacroWithSpelling(SourceLocation Loc,
public:
   void CollectPpImportSuffix(SmallVectorImpl<Token> &Toks);
 
   void makeModuleVisible(Module *M, SourceLocation Loc);
 
   SourceLocation getModuleImportLoc(Module *M) const {
     return CurSubmoduleState->VisibleModules.getImportLoc(M);
   }
 
+  /// Determine whether the given module is currently visible.
+  bool isModuleCurrentlyVisible(Module *M) const {
+    return CurSubmoduleState->VisibleModules.isVisible(M);
+  }
+
   /// Lex a string literal, which may be the concatenation of multiple
   /// string literals and may even come from macro expansion.
   /// \returns true on success, false if a error diagnostic has been generated.
   bool LexStringLiteral(Token &Result, std::string &String,
                         const char *DiagnosticTag, bool AllowMacroExpansion) {
     if (AllowMacroExpansion)
       Lex(Result);
     else

clang/lib/Lex/HeaderSearch.cpp

if (const IdentifierInfo *ControllingMacro
     // modules.
     if (M ? PP.isMacroDefinedInLocalModule(ControllingMacro, M)
           : PP.isMacroDefined(ControllingMacro)) {
       ++NumMultiIncludeFileOptzn;
       return false;
     }
   }
 
-  IsFirstIncludeOfFile = PP.markIncluded(File);
+  IsFirstIncludeOfFile = PP.markDirectlyIncluded(File);
 
   return true;
 }
 
 size_t HeaderSearch::getTotalMemory() const {
   return SearchDirs.capacity()
     + llvm::capacity_in_bytes(FileInfo)
     + llvm::capacity_in_bytes(HeaderMaps)

clang/lib/Lex/Preprocessor.cpp

if (!SourceMgr.isLoadedFileID(MainFileID)) {
     // precompiled preamble), do so now.
     if (SkipMainFilePreamble.first > 0)
       CurLexer->SetByteOffset(SkipMainFilePreamble.first,
                               SkipMainFilePreamble.second);
 
     // Tell the header info that the main file was entered.  If the file is later
     // #imported, it won't be re-entered.
     if (const FileEntry *FE = SourceMgr.getFileEntryForID(MainFileID))
-      markIncluded(FE);
+      markDirectlyIncluded(FE);
   }
 
   // Preprocess Predefines to populate the initial preprocessor state.
   std::unique_ptr<llvm::MemoryBuffer> SB =
     llvm::MemoryBuffer::getMemBufferCopy(Predefines, "<built-in>");
   assert(SB && "Cannot create predefined source buffer");
   FileID FID = SourceMgr.createFileID(std::move(SB));
   assert(FID.isValid() && "Could not create FileID for predefines?");
if (!Suffix.empty()) {
     EnterTokens(Suffix);
     return false;
   }
   return true;
 }
 
 void Preprocessor::makeModuleVisible(Module *M, SourceLocation Loc) {
   CurSubmoduleState->VisibleModules.setVisible(
-      M, Loc, [](Module *) {},
+      M, Loc,
+      [&](Module *M) {
+        // The set of included files may be incomplete for modules coming from
+        // a PCM, since we're deserializing included files lazily. The rest of
+        // the files will be handled lazily, as we need them.
+        for (const FileEntry *FE : getFilesIncludedIn(M))
+          markTransitivelyIncluded(FE);
+      },
       [&](ArrayRef<Module *> Path, Module *Conflict, StringRef Message) {
         // FIXME: Include the path in the diagnostic.
         // FIXME: Include the import location for the conflicting module.
         Diag(ModuleImportLoc, diag::warn_module_conflict)
             << Path[0]->getFullModuleName()
             << Conflict->getFullModuleName()
             << Message;
       });

clang/lib/Serialization/ASTReader.cpp

ASTReader::getGlobalPreprocessedEntityID(ModuleFile &M,
   ContinuousRangeMap<uint32_t, int, 2>::const_iterator
     I = M.PreprocessedEntityRemap.find(LocalID - NUM_PREDEF_PP_ENTITY_IDS);
   assert(I != M.PreprocessedEntityRemap.end()
          && "Invalid index into preprocessed entity index remap");
 
   return LocalID + I->second;
 }
 
-const FileEntry *HeaderFileInfoTrait::getFile(const internal_key_type &Key) {
+OptionalFileEntryRef
+HeaderFileInfoTrait::getFile(const internal_key_type &Key) {
   FileManager &FileMgr = Reader.getFileManager();
-  if (!Key.Imported) {
-    if (auto File = FileMgr.getFile(Key.Filename))
-      return *File;
-    return nullptr;
-  }
+  if (!Key.Imported)
+    return FileMgr.getOptionalFileRef(Key.Filename);
 
   std::string Resolved = std::string(Key.Filename);
   Reader.ResolveImportedPath(M, Resolved);
-  if (auto File = FileMgr.getFile(Resolved))
-    return *File;
-  return nullptr;
+  return FileMgr.getOptionalFileRef(Resolved);
 }
 
 unsigned HeaderFileInfoTrait::ComputeHash(internal_key_ref ikey) {
   return llvm::hash_combine(ikey.Size, ikey.ModTime);
 }
 
 HeaderFileInfoTrait::internal_key_type
 HeaderFileInfoTrait::GetInternalKey(const FileEntry *FE) {
   internal_key_type ikey = {FE->getSize(),
                             M.HasTimestamps ? FE->getModificationTime() : 0,
                             FE->getName(), /*Imported*/ false};
   return ikey;
 }
 
 bool HeaderFileInfoTrait::EqualKey(internal_key_ref a, internal_key_ref b) {
   if (a.Size != b.Size || (a.ModTime && b.ModTime && a.ModTime != b.ModTime))
     return false;
 
   if (llvm::sys::path::is_absolute(a.Filename) && a.Filename == b.Filename)
     return true;
 
   // Determine whether the actual files are equivalent.
-  const FileEntry *FEA = getFile(a);
-  const FileEntry *FEB = getFile(b);
+  OptionalFileEntryRef FEA = getFile(a);
+  OptionalFileEntryRef FEB = getFile(b);
   return FEA && FEA == FEB;
 }
 
 std::pair<unsigned, unsigned>
 HeaderFileInfoTrait::ReadKeyDataLength(const unsigned char*& d) {
   return readULEBKeyDataLength(d);
 }
 
HeaderFileInfoTrait::ReadKey(const unsigned char *d, unsigned) {
   return ikey;
 }
 
 HeaderFileInfoTrait::data_type
 HeaderFileInfoTrait::ReadData(internal_key_ref key, const unsigned char *d,
                               unsigned DataLen) {
   using namespace llvm::support;
 
+  OptionalFileEntryRef FE = getFile(key);
+  // We can only get here if the key of this entry is an absolute path that
+  // matches the name of an already known FileEntry, or the FileEntry given out
+  // by FileManager for this key compares equal to the alrleady known FileEntry.
+  assert(FE && "Missing FileEntry during HeaderFileInfo deserialization");
+
   const unsigned char *End = d + DataLen;
   HeaderFileInfo HFI;
   unsigned Flags = *d++;
-
-  bool Included = (Flags >> 6) & 0x01;
-  if (Included)
-    if (const FileEntry *FE = getFile(key))
-      // Not using \c Preprocessor::markIncluded(), since that would attempt to
-      // deserialize this header file info again.
-      Reader.getPreprocessor().getIncludedFiles().insert(FE);
-
   // FIXME: Refactor with mergeHeaderFileInfo in HeaderSearch.cpp.
   HFI.isImport |= (Flags >> 5) & 0x01;
   HFI.isPragmaOnce |= (Flags >> 4) & 0x01;
   HFI.DirInfo = (Flags >> 1) & 0x07;
   HFI.IndexHeaderMapHeader = Flags & 0x01;
   HFI.ControllingMacroID = Reader.getGlobalIdentifierID(
       M, endian::readNext<uint32_t, little, unaligned>(d));
+
+  Preprocessor &PP = Reader.getPreprocessor();
+  auto IncludedInCount = endian::readNext<uint32_t, little, unaligned>(d);
+  for (uint32_t I = 0; I < IncludedInCount; ++I) {
+    uint32_t ModID = endian::readNext<uint32_t, little, unaligned>(d);
+    Module *Mod = Reader.getModule(ModID);
+    if (Mod)
+      PP.getFilesIncludedIn(Mod).insert(*FE);
+    if (!Mod || PP.isModuleCurrentlyVisible(Mod))
+      PP.getIncludedFiles().insert(*FE);
+  }
+
   if (unsigned FrameworkOffset =
           endian::readNext<uint32_t, little, unaligned>(d)) {
     // The framework offset is 1 greater than the actual offset,
     // since 0 is used as an indicator for "no framework name".
     StringRef FrameworkName(FrameworkStrings + FrameworkOffset - 1);
     HFI.Framework = HS->getUniqueFrameworkName(FrameworkName);
   }
 
   assert((End - d) % 4 == 0 &&
          "Wrong data length in HeaderFileInfo deserialization");
   while (d != End) {
     uint32_t LocalSMID = endian::readNext<uint32_t, little, unaligned>(d);
     auto HeaderRole = static_cast<ModuleMap::ModuleHeaderRole>(LocalSMID & 7);
     LocalSMID >>= 3;
 
     // This header is part of a module. Associate it with the module to enable
     // implicit module import.
     SubmoduleID GlobalSMID = Reader.getGlobalSubmoduleID(M, LocalSMID);
     Module *Mod = Reader.getSubmodule(GlobalSMID);
-    FileManager &FileMgr = Reader.getFileManager();
-    ModuleMap &ModMap =
-        Reader.getPreprocessor().getHeaderSearchInfo().getModuleMap();
+    ModuleMap &ModMap = PP.getHeaderSearchInfo().getModuleMap();
 
-    std::string Filename = std::string(key.Filename);
-    if (key.Imported)
-      Reader.ResolveImportedPath(M, Filename);
-    if (auto FE = FileMgr.getOptionalFileRef(Filename)) {
-      // FIXME: NameAsWritten
-      Module::Header H = {std::string(key.Filename), "", *FE};
-      ModMap.addHeader(Mod, H, HeaderRole, /*Imported=*/true);
-    }
     HFI.isModuleHeader |= ModuleMap::isModular(HeaderRole);
   }
 
   // This HeaderFileInfo was externally loaded.
   HFI.External = true;
   HFI.IsValid = true;
   return HFI;
 }

clang/lib/Serialization/ASTReaderInternals.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H
 #define LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H
 
 #include "MultiOnDiskHashTable.h"
 #include "clang/AST/DeclarationName.h"
+#include "clang/Basic/FileEntry.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Serialization/ASTBitCodes.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/OnDiskHashTable.h"
 #include <ctime>
 #include <utility>
 
 namespace clang {
 
 class ASTReader;
-class FileEntry;
 struct HeaderFileInfo;
 class HeaderSearch;
 class ObjCMethodDecl;
 
 namespace serialization {
 
 class ModuleFile;
 
public:
   static std::pair<unsigned, unsigned>
   ReadKeyDataLength(const unsigned char*& d);
 
   static internal_key_type ReadKey(const unsigned char *d, unsigned);
 
   data_type ReadData(internal_key_ref,const unsigned char *d, unsigned DataLen);
 
 private:
-  const FileEntry *getFile(const internal_key_type &Key);
+  OptionalFileEntryRef getFile(const internal_key_type &Key);
 };
 
 /// The on-disk hash table used for known header files.
 using HeaderFileInfoLookupTable =
     llvm::OnDiskChainedHashTable<HeaderFileInfoTrait>;
 
 } // namespace reader
 
 } // namespace serialization
 
 } // namespace clang
 
 #endif // LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H

clang/lib/Serialization/ASTWriter.cpp

public:
     };
     using key_type_ref = const key_type &;
 
     using UnresolvedModule =
         llvm::PointerIntPair<Module *, 2, ModuleMap::ModuleHeaderRole>;
 
     struct data_type {
       const HeaderFileInfo &HFI;
-      bool AlreadyIncluded;
+      SmallVector<uint32_t, 4> IncludedIn;
       ArrayRef<ModuleMap::KnownHeader> KnownHeaders;
       UnresolvedModule Unresolved;
     };
     using data_type_ref = const data_type &;
 
     using hash_value_type = unsigned;
     using offset_type = unsigned;
 
     hash_value_type ComputeHash(key_type_ref key) {
       // The hash is based only on size/time of the file, so that the reader can
       // match even when symlinking or excess path elements ("foo/../", "../")
       // change the form of the name. However, complete path is still the key.
       return llvm::hash_combine(key.Size, key.ModTime);
     }
 
     std::pair<unsigned, unsigned>
     EmitKeyDataLength(raw_ostream& Out, key_type_ref key, data_type_ref Data) {
       unsigned KeyLen = key.Filename.size() + 1 + 8 + 8;
       unsigned DataLen = 1 + 4 + 4;
       for (auto ModInfo : Data.KnownHeaders)
         if (Writer.getLocalOrImportedSubmoduleID(ModInfo.getModule()))
           DataLen += 4;
       if (Data.Unresolved.getPointer())
         DataLen += 4;
+      DataLen += 4 + 4 * Data.IncludedIn.size();
       return emitULEBKeyDataLength(KeyLen, DataLen, Out);
     }
 
     void EmitKey(raw_ostream& Out, key_type_ref key, unsigned KeyLen) {
       using namespace llvm::support;
 
       endian::Writer LE(Out, little);
       LE.write<uint64_t>(key.Size);
       KeyLen -= 8;
       LE.write<uint64_t>(key.ModTime);
       KeyLen -= 8;
       Out.write(key.Filename.data(), KeyLen);
     }
 
     void EmitData(raw_ostream &Out, key_type_ref key,
                   data_type_ref Data, unsigned DataLen) {
       using namespace llvm::support;
 
       endian::Writer LE(Out, little);
       uint64_t Start = Out.tell(); (void)Start;
 
-      unsigned char Flags = (Data.AlreadyIncluded << 6)
-                          | (Data.HFI.isImport << 5)
+      unsigned char Flags = (Data.HFI.isImport << 5)
                           | (Data.HFI.isPragmaOnce << 4)
                           | (Data.HFI.DirInfo << 1)
                           | Data.HFI.IndexHeaderMapHeader;
       LE.write<uint8_t>(Flags);
 
       if (!Data.HFI.ControllingMacro)
         LE.write<uint32_t>(Data.HFI.ControllingMacroID);
       else
         LE.write<uint32_t>(Writer.getIdentifierRef(Data.HFI.ControllingMacro));
 
+      LE.write<uint32_t>(Data.IncludedIn.size());
+      for (uint32_t ModID : Data.IncludedIn)
+        LE.write<uint32_t>(ModID);
+
       unsigned Offset = 0;
       if (!Data.HFI.Framework.empty()) {
         // If this header refers into a framework, save the framework name.
         llvm::StringMap<unsigned>::iterator Pos
           = FrameworkNameOffset.find(Data.HFI.Framework);
         if (Pos == FrameworkNameOffset.end()) {
           Offset = FrameworkStringData.size() + 1;
           FrameworkStringData.append(Data.HFI.Framework);
while (!Worklist.empty()) {
         PreparePathForOutput(Filename);
 
         StringRef FilenameDup = strdup(Filename.c_str());
         SavedStrings.push_back(FilenameDup.data());
 
         HeaderFileInfoTrait::key_type Key = {
             FilenameDup, *U.Size, IncludeTimestamps ? *U.ModTime : 0};
         HeaderFileInfoTrait::data_type Data = {
-            Empty, false, {}, {M, ModuleMap::headerKindToRole(U.Kind)}};
+            Empty, {}, {}, {M, ModuleMap::headerKindToRole(U.Kind)}};
         // FIXME: Deal with cases where there are multiple unresolved header
         // directives in different submodules for the same header.
         Generator.insert(Key, Data, GeneratorTrait);
         ++NumHeaderSearchEntries;
       }
       auto SubmodulesRange = M->submodules();
       Worklist.append(SubmodulesRange.begin(), SubmodulesRange.end());
     }
for (unsigned UID = 0, LastUID = FilesByUID.size(); UID != LastUID; ++UID) {
     SmallString<128> FilenameTmp(Filename);
     if (PreparePathForOutput(FilenameTmp)) {
       // If we performed any translation on the file name at all, we need to
       // save this string, since the generator will refer to it later.
       Filename = StringRef(strdup(FilenameTmp.c_str()));
       SavedStrings.push_back(Filename.data());
     }
 
-    bool Included = PP->alreadyIncluded(File);
+    SmallVector<uint32_t, 4> IncludedIn;
+    PP->forModulesIncluding(File, [&](Module *M) {
+      if ((!M && !WritingModule) ||
+          (M && M->getTopLevelModule() == WritingModule))
+        IncludedIn.push_back(getSubmoduleID(M));
+    });
+    llvm::sort(IncludedIn);
 
     HeaderFileInfoTrait::key_type Key = {
       Filename, File->getSize(), getTimestampForOutput(File)
     };
     HeaderFileInfoTrait::data_type Data = {
-      *HFI, Included, HS.getModuleMap().findResolvedModulesForHeader(File), {}
+      *HFI, IncludedIn, HS.getModuleMap().findResolvedModulesForHeader(File), {}
     };
     Generator.insert(Key, Data, GeneratorTrait);
     ++NumHeaderSearchEntries;
   }
 
   // Create the on-disk hash table in a buffer.
   SmallString<4096> TableData;
   uint32_t BucketOffset;

clang/test/Modules/import-submodule-visibility.c

+// This test checks that imports of headers that appeared in a different submodule than
+// what is imported by the current TU don't affect the compilation.
+
+// RUN: rm -rf %t
+// RUN: split-file %s %t
+
+//--- C/C.h
+#include "Textual.h"
+//--- C/module.modulemap
+module C { header "C.h" }
+
+//--- D/D1.h
+#include "Textual.h"
+//--- D/D2.h
+//--- D/module.modulemap
+module D {
+  module D1 { header "D1.h" }
+  module D2 { header "D2.h" }
+}
+
+//--- E/E1.h
+#include "E2.h"
+//--- E/E2.h
+#include "Textual.h"
+//--- E/module.modulemap
+module E {
+  module E1 { header "E1.h" }
+  module E2 { header "E2.h" }
+}
+
+//--- Textual.h
+#define MACRO_TEXTUAL 1
+
+//--- test_top.c
+#import "Textual.h"
+static int x = MACRO_TEXTUAL;
+
+//--- test_sub.c
+#import "D/D2.h"
+#import "Textual.h"
+static int x = MACRO_TEXTUAL;
+
+//--- test_transitive.c
+#import "E/E1.h"
+#import "Textual.h"
+static int x = MACRO_TEXTUAL;
+
+// Simply loading a PCM file containing top-level module including a header does
+// not prevent inclusion of that header in the TU.
+//
+// RUN: %clang_cc1 -fmodules -I %t -emit-module %t/C/module.modulemap -fmodule-name=C -o %t/C.pcm
+// RUN: %clang_cc1 -fmodules -I %t -fsyntax-only %t/test_top.c -fmodule-file=%t/C.pcm
+
+// Loading a PCM file and importing its empty submodule does not prevent
+// inclusion of headers included by invisible sibling submodules.
+//
+// RUN: %clang_cc1 -fmodules -I %t -emit-module %t/D/module.modulemap -fmodule-name=D -o %t/D.pcm
+// RUN: %clang_cc1 -fmodules -I %t -fsyntax-only %t/test_sub.c -fmodule-file=%t/D.pcm
+
+// Loading a PCM file and importing a submodule does not prevent inclusion of
+// headers included by some of its transitive un-exported dependencies.
+//
+// RUN: %clang_cc1 -fmodules -I %t -emit-module %t/E/module.modulemap -fmodule-name=E -o %t/E.pcm
+// RUN: %clang_cc1 -fmodules -I %t -fsyntax-only %t/test_transitive.c -fmodule-file=%t/E.pcm