[modules] Track how headers are included by different submodules.

[vsapsai]

Summary

Currently in a PCM file we are storing HeaderSearch state from
building an entire module. This is too coarse because for a non-modular
header isImport == true means it was imported by *some* header in the
module but doesn't capture if this module header is reachable itself. In
practice it can cause code

#import <Framework/Header.h>
#import <Unmodularized/Unmodularized.h>

to skip "Unmodularized.h" header because another "Framework/Invisible.h"
imported it. As the result declarations from "Unmodularized.h" aren't
accessible despite direct import.

Fix it by tracking isImport and NumIncludes per submodule including
a header. And on reading AST use the values only for visible submodules.

rdar://64773328

[vsapsai]

Split out smaller parts as separate reviews.

[vsapsai]

Test when a non-modular header *is* visible through a module import (mostly for completeness).

[vsapsai]

Add a test to verify MarkFileIncludedFromModule does |= isImport instead of = isImport.

[vsapsai]

Ping. It would be useful to know if this approach makes sense. If so, I can test it on a bigger codebase and see if there are any problems.

[vsapsai]

Ping.

[vsapsai]

Ping.

[vsapsai]

Ping.

[vsapsai]

Ping.

[jansvoboda11]

If my understanding is correct, this patch only changes how we track HeaderFileInfo::{isImport,NumIncludes} and makes sure to store the necessary info into AST files. Right?

Can you explain how values of these members can prevent Clang from importing the header and how this interacts with visibility?

[jansvoboda11]

FYI, a clangd test is failing in CI.

[vsapsai]

In D104344#2969178, @jansvoboda11 wrote:

If my understanding is correct, this patch only changes how we track HeaderFileInfo::{isImport,NumIncludes} and makes sure to store the necessary info into AST files. Right?

Yes, you are correct.

Can you explain how values of these members can prevent Clang from importing the header and how this interacts with visibility?

Currently, in AST we basically store the state of HeaderSearch after building a module. And isImport means "if any of the headers in the module has used #import", NumIncludes means "how many times all of the headers in the module have included the given header". So in the test case import-nonmodular.m after building the module 'Modularized' we have for the header Unmodularized.h isImport = true, NumIncludes = 1. So when we see #import <Unmodularized/Unmodularized.h> we decide not to enter the header because according to PCM data it was already imported once. But when we try to use UnmodularizedStruct, we cannot do that because it is present in Modularized.Invisible but unfortunately not visible.

So my fix is to track HeaderFileInfo::{isImport,NumIncludes} per including submodule. And when we encounter include/import in the source code, try to load ExternalHFI from ExternalSource, we use isImport and NumIncludes only from the modules that are [transitively] visible at this point. This way we don't use isImport and NumIncludes from irrelevant modular headers.

Another option is to treat unmodularized headers as submodules and update their visibility when we see #import <Unmodularized/Unmodularized.h>. But that's pretty complicated and I'm not sure it is possible when we have the same non-modular header included from different modules. Then we have multiple copies of the same fake submodule and it's not clear which one to use, which one to update.

[jansvoboda11]

I see, thanks for the explanation. This LGTM provided the failing clangd test gets fixed.

[vsapsai]

clang/lib/Serialization/ASTWriter.cpp

1671–1674

Note for future readers (including myself). Can save 2 bytes because not writing Data.HFI.NumIncludes but need 4 extra bytes for Data.HFI.ModuleIncludersMap stop value.

[vsapsai]

Clarify some comments; rebase for a fresh pre-commit testing.

[rsmith]

I wonder if perhaps we're tracking this state in the wrong way. The "has been included" information for #pragma once / #import should behave exactly like macro definition visibility: it should be reset whenever we enter a new "clean slate" state and should be saved and restored suitably when switching visibility states. If we track, for each header file, a map from module to include information, then we'll be paying a fairly high cost: each time we see a #include we'll need to look up every currently-visible module in the map to see if the header was included in that module. It might be better to track an up-to-date list of the headers that have been either #imported in the current preprocessor state (including via imported modules) or that have been both #included and contain #pragma once. You could stash that in the Preprocessor::SubmoduleState so that it's suitably swapped out when we switch to a new preprocessing state.

clang/include/clang/Lex/HeaderSearch.h

126

This seems like a very expensive thing to include in HeaderFileInfo, which we may have many thousands of in some compilations. (I have similar concerns about Aliases FWIW.)

clang/include/clang/Serialization/ASTBitCodes.h

44

Do we really need to bump the version number? (Does this affect something we read before we read the Clang version number and reject on a version mismatch?)

clang/lib/Serialization/ASTReader.cpp

1912–1916

This doesn't do the right thing in local submodule visibility mode. We need to compute visibility locally from within HeaderSearch based on the currently visible modules at the point of the query instead.

[vsapsai]

That's a good point. Let me check how we track macros, I haven't thought about that approach. And I haven't considered using Preprocessor::SubmoduleState, was too excited HeaderSearch::ShouldEnterIncludeFile works correctly with the updated data.

clang/include/clang/Lex/HeaderSearch.h

126

My fault. The fact that the struct is tightly packed, should have been a hint.

clang/include/clang/Serialization/ASTBitCodes.h

44

Nope, there is no logic for VERSION_MAJOR. Just wanted to avoid old clang writing HeaderFileInfoTrait in one format and new clang reading it in the new format. But if that is resolved by Clang version number, no need for VERSION_MAJOR bump.

clang/lib/Serialization/ASTReader.cpp

1912–1916

Is it wrong from general local submodule visibility approach or do you have a test case in mind? Don't need a specific case, general direction can help to come up with a test case.

In practice it was working because we were reading this part of PCM file only when HeaderFileInfo was requested and that was at the point when modules had correct visibility. Let me try with multiple unmodularized headers, that can be broken and it can be a good test case on its own.

[vsapsai]

Investigate less heavy-weight approaches similar to those used for tracking macros from different submodules.

clang/include/clang/Lex/HeaderSearch.h

struct HeaderFileInfo {
   /// List of aliases that this header is known as.
   /// Most headers should only have at most one alias, but a handful
   /// have two.
   llvm::SetVector<llvm::SmallString<32>,
                   llvm::SmallVector<llvm::SmallString<32>, 2>,
                   llvm::SmallSet<llvm::SmallString<32>, 2>>
       Aliases;
 
+  /// Stores modules including this header.
+  /// Bool represents if the header was included (false) or imported (true).
+  llvm::DenseMap<const Module *, bool> ModuleIncludersMap;
+
   HeaderFileInfo()
       : isImport(false), isPragmaOnce(false), DirInfo(SrcMgr::C_User),
         External(false), isModuleHeader(false), isCompilingModuleHeader(false),
         Resolved(false), IndexHeaderMapHeader(false), IsValid(false)  {}
 
   /// Retrieve the controlling macro for this header file, if
   /// any.
   const IdentifierInfo *
void AddFileAlias(const FileEntry *File, StringRef Alias) {
     getFileInfo(File).Aliases.insert(Alias);
   }
 
   /// Mark the specified file as part of a module.
   void MarkFileModuleHeader(const FileEntry *FE,
                             ModuleMap::ModuleHeaderRole Role,
                             bool isCompilingModuleHeader);
 
+  void MarkFileIncludedFromModule(const FileEntry *File, const Module *M,
+                                  bool isImport) {
+    getFileInfo(File).ModuleIncludersMap[M] |= isImport;
+  }
+
   /// Increment the count for the number of times the specified
   /// FileEntry has been entered.
   void IncrementIncludeCount(const FileEntry *File) {
     ++getFileInfo(File).NumIncludes;
   }
 
   /// Mark the specified file as having a controlling macro.
   ///

clang/include/clang/Serialization/ASTBitCodes.h

 /// Whenever the AST file format changes in a way that makes it
 /// incompatible with previous versions (such that a reader
 /// designed for the previous version could not support reading
 /// the new version), this number should be increased.
 ///
 /// Version 4 of AST files also requires that the version control branch and
 /// revision match exactly, since there is no backward compatibility of
 /// AST files at this time.
-const unsigned VERSION_MAJOR = 15;
+const unsigned VERSION_MAJOR = 16;
 
 /// AST file minor version number supported by this version of
 /// Clang.
 ///
 /// Whenever the AST format changes in a way that is still
 /// compatible with previous versions (such that a reader designed
 /// for the previous version could still support reading the new
 /// version by ignoring new kinds of subblocks), this number

clang/lib/Lex/PPDirectives.cpp

if (Action == Enter && File &&
     // modular because we might not have imported it from this submodule before.
     //
     // FIXME: We don't do this when compiling a PCH because the AST
     // serialization layer can't cope with it. This means we get local
     // submodule visibility semantics wrong in that case.
     Action = (SuggestedModule && !getLangOpts().CompilingPCH) ? Import : Skip;
   }
 
+  if (File) {
+    // Store data about includer with submodule granularity.
+    if (Module *RequestingModule = getModuleForLocation(HashLoc)) {
+      HeaderInfo.MarkFileIncludedFromModule(&File->getFileEntry(),
+                                            RequestingModule, EnterOnce);
+    }
+  }
+
   // Check for circular inclusion of the main file.
   // We can't generate a consistent preamble with regard to the conditional
   // stack if the main file is included again as due to the preamble bounds
   // some directives (e.g. #endif of a header guard) will never be seen.
   // Since this will lead to confusing errors, avoid the inclusion.
   if (Action == Enter && File && PreambleConditionalStack.isRecording() &&
       SourceMgr.isMainFile(File->getFileEntry())) {
     Diag(FilenameTok.getLocation(),

clang/lib/Serialization/ASTReader.cpp

 HeaderFileInfoTrait::ReadData(internal_key_ref key, const unsigned char *d,
                               unsigned DataLen) {
   using namespace llvm::support;
 
   const unsigned char *End = d + DataLen;
   HeaderFileInfo HFI;
   unsigned Flags = *d++;
   // 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;
-  // FIXME: Find a better way to handle this. Maybe just store a
-  // "has been included" flag?
-  HFI.NumIncludes = std::max(endian::readNext<uint16_t, little, unaligned>(d),
-                             HFI.NumIncludes);
   HFI.ControllingMacroID = Reader.getGlobalIdentifierID(
       M, endian::readNext<uint32_t, little, unaligned>(d));
   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);
   }
 
+  while (true) {
+    uint32_t LocalSMID = endian::readNext<uint32_t, little, unaligned>(d);
+    if (!LocalSMID)
+      break;
+    bool IsImport = static_cast<bool>(LocalSMID & 1);
+    LocalSMID >>= 1;
+
+    SubmoduleID GlobalSMID = Reader.getGlobalSubmoduleID(M, LocalSMID);
+    Module *Mod = Reader.getSubmodule(GlobalSMID);
+    HFI.ModuleIncludersMap[Mod] = IsImport;
+    // Update isImport and NumIncludes based on including module.
+    if (Mod->NameVisibility == Module::NameVisibilityKind::AllVisible) {
+      HFI.isImport |= IsImport;
+      ++HFI.NumIncludes;
+    }
+  }
+
   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 & 3);
     LocalSMID >>= 2;
 
     // This header is part of a module. Associate it with the module to enable
if (key.Imported)
       Reader.ResolveImportedPath(M, Filename);
     // FIXME: NameAsWritten
     Module::Header H = {std::string(key.Filename), "",
                         *FileMgr.getFile(Filename)};
     ModMap.addHeader(Mod, H, HeaderRole, /*Imported*/true);
     HFI.isModuleHeader |= !(HeaderRole & ModuleMap::TextualHeader);
   }
 
+  serialization::ModuleKind PrimaryModuleKind =
+      Reader.getModuleManager().getPrimaryModule().Kind;
+  if ((PrimaryModuleKind == MK_PCH) || (PrimaryModuleKind == MK_Preamble)) {
+    // Treat preprocessor/preamble header as included at least once.
+    ++HFI.NumIncludes;
+  }
+
   // This HeaderFileInfo was externally loaded.
   HFI.External = true;
   HFI.IsValid = true;
   return HFI;
 }
 
 void ASTReader::addPendingMacro(IdentifierInfo *II, ModuleFile *M,
                                 uint32_t MacroDirectivesOffset) {

clang/lib/Serialization/ASTWriter.cpp

hash_value_type ComputeHash(key_type_ref key) {
       // 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 + 2 + 4 + 4;
+      unsigned DataLen = 1 + 4 + 4 + 4;
+      for (auto ModuleIncluder : Data.HFI.ModuleIncludersMap)
+        if (Writer.getLocalOrImportedSubmoduleID(ModuleIncluder.first))
+          DataLen += 4;
       for (auto ModInfo : Data.KnownHeaders)
         if (Writer.getLocalOrImportedSubmoduleID(ModInfo.getModule()))
           DataLen += 4;
       if (Data.Unresolved.getPointer())
         DataLen += 4;
       return emitULEBKeyDataLength(KeyLen, DataLen, Out);
     }
 
public:
 
     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.HFI.isImport << 5)
-                          | (Data.HFI.isPragmaOnce << 4)
-                          | (Data.HFI.DirInfo << 1)
-                          | Data.HFI.IndexHeaderMapHeader;
+      unsigned char Flags = (Data.HFI.isPragmaOnce << 4) |
+                            (Data.HFI.DirInfo << 1) |
+                            Data.HFI.IndexHeaderMapHeader;
       LE.write<uint8_t>(Flags);
-      LE.write<uint16_t>(Data.HFI.NumIncludes);
 
       if (!Data.HFI.ControllingMacro)
         LE.write<uint32_t>(Data.HFI.ControllingMacroID);
       else
         LE.write<uint32_t>(Writer.getIdentifierRef(Data.HFI.ControllingMacro));
 
       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);
           FrameworkStringData.push_back(0);
 
           FrameworkNameOffset[Data.HFI.Framework] = Offset;
         } else
           Offset = Pos->second;
       }
       LE.write<uint32_t>(Offset);
 
+      for (auto ModuleIncluder : Data.HFI.ModuleIncludersMap) {
+        if (uint32_t ModID =
+                Writer.getLocalOrImportedSubmoduleID(ModuleIncluder.first)) {
+          uint32_t Value = (ModID << 1) | (bool)ModuleIncluder.second;
+          assert((Value >> 1) == ModID && "overflow in header module info");
+          LE.write<uint32_t>(Value);
+        }
+      }
+      // Using a stop value because cannot tell ahead of time how many includers
+      // are local or imported submodules.
+      LE.write<uint32_t>(0);
+
       auto EmitModule = [&](Module *M, ModuleMap::ModuleHeaderRole Role) {
         if (uint32_t ModID = Writer.getLocalOrImportedSubmoduleID(M)) {
           uint32_t Value = (ModID << 2) | (unsigned)Role;
           assert((Value >> 2) == ModID && "overflow in header module info");
           LE.write<uint32_t>(Value);
         }
       };
 

clang/test/Modules/Inputs/import-nonmodular/MixedDirectives.framework/Headers/MixedDirectives.h

+#import <Unmodularized/Unmodularized.h>
+#include <Unmodularized/Unmodularized.h>

clang/test/Modules/Inputs/import-nonmodular/MixedDirectives.framework/Modules/module.modulemap

+framework module MixedDirectives {
+  header "MixedDirectives.h"
+  export *
+}

clang/test/Modules/Inputs/import-nonmodular/Modularized.framework/Headers/Invisible.h

+#import <Unmodularized/Unmodularized.h>

clang/test/Modules/Inputs/import-nonmodular/Modularized.framework/Headers/Visible.h

+// Empty.

clang/test/Modules/Inputs/import-nonmodular/Modularized.framework/Modules/module.modulemap

+framework module Modularized {
+  module Visible {
+    header "Visible.h"
+    export *
+  }
+
+  module Invisible {
+    header "Invisible.h"
+    export *
+  }
+}

clang/test/Modules/Inputs/import-nonmodular/Unmodularized.framework/Headers/Unmodularized.h

+// No header guard on purpose.
+
+typedef struct UnmodularizedStruct {
+} UnmodularizedStruct;

clang/test/Modules/import-nonmodular-directive-tracking.m

+// RUN: rm -rf %t
+// RUN: %clang_cc1 -fsyntax-only -fmodules -fimplicit-module-maps -fmodules-cache-path=%t -F %S/Inputs/import-nonmodular %s -verify
+// expected-no-diagnostics
+
+// Test that #import in a module is "sticky" and isn't overwritten by subsequent #include.
+
+#import <MixedDirectives/MixedDirectives.h>
+// #include instead of #import on purpose.
+#include <Unmodularized/Unmodularized.h>
+void test(UnmodularizedStruct *s) {}

clang/test/Modules/import-nonmodular.m

+// RUN: rm -rf %t
+// RUN: %clang_cc1 -fsyntax-only -fmodules -fimplicit-module-maps -fmodules-cache-path=%t -F %S/Inputs/import-nonmodular %s -verify
+// RUN: %clang_cc1 -fsyntax-only -fmodules -fimplicit-module-maps -fmodules-cache-path=%t -F %S/Inputs/import-nonmodular %s -verify -DTEST_IMPORT_FROM_MODULE
+// expected-no-diagnostics
+
+// Test non-modular headers are not skipped even if they are imported by
+// non-imported submodules of an imported module. Dependency graph is
+//
+//                       Unmodularized.h
+//                           ^       ^
+//                           |       |
+//  Modularized.Visible      |    Modularized.Invisible
+//                  ^        |
+//                   \       |
+//                import-nonmodular.m
+
+#import <Modularized/Visible.h>
+#ifdef TEST_IMPORT_FROM_MODULE
+#import <Modularized/Invisible.h>
+#endif
+#import <Unmodularized/Unmodularized.h>
+void test(UnmodularizedStruct *s) {}