PR24667: fix quadratic runtime if textually-included modular headers define large numbers of macros.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@261705 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/clang/Lex/Preprocessor.h b/include/clang/Lex/Preprocessor.h
index f6154b6..da347914 100644
--- a/include/clang/Lex/Preprocessor.h
+++ b/include/clang/Lex/Preprocessor.h
@@ -507,9 +507,10 @@
/// \brief Information about a submodule that we're currently building.
struct BuildingSubmoduleInfo {
BuildingSubmoduleInfo(Module *M, SourceLocation ImportLoc,
- SubmoduleState *OuterSubmoduleState)
- : M(M), ImportLoc(ImportLoc), OuterSubmoduleState(OuterSubmoduleState) {
- }
+ SubmoduleState *OuterSubmoduleState,
+ unsigned OuterPendingModuleMacroNames)
+ : M(M), ImportLoc(ImportLoc), OuterSubmoduleState(OuterSubmoduleState),
+ OuterPendingModuleMacroNames(OuterPendingModuleMacroNames) {}
/// The module that we are building.
Module *M;
@@ -517,6 +518,8 @@
SourceLocation ImportLoc;
/// The previous SubmoduleState.
SubmoduleState *OuterSubmoduleState;
+ /// The number of pending module macro names when we started building this.
+ unsigned OuterPendingModuleMacroNames;
};
SmallVector<BuildingSubmoduleInfo, 8> BuildingSubmoduleStack;
@@ -541,6 +544,9 @@
/// The set of known macros exported from modules.
llvm::FoldingSet<ModuleMacro> ModuleMacros;
+ /// The names of potential module macros that we've not yet processed.
+ llvm::SmallVector<const IdentifierInfo*, 32> PendingModuleMacroNames;
+
/// The list of module macros, for each identifier, that are not overridden by
/// any other module macro.
llvm::DenseMap<const IdentifierInfo *, llvm::TinyPtrVector<ModuleMacro*>>
@@ -1683,6 +1689,10 @@
void EnterSubmodule(Module *M, SourceLocation ImportLoc);
void LeaveSubmodule();
+ /// Determine whether we need to create module macros for #defines in the
+ /// current context.
+ bool needModuleMacros() const;
+
/// Update the set of active module macros and ambiguity flag for a module
/// macro name.
void updateModuleMacroInfo(const IdentifierInfo *II, ModuleMacroInfo &Info);
diff --git a/lib/Lex/PPLexerChange.cpp b/lib/Lex/PPLexerChange.cpp
index bbfa84f..4900662 100644
--- a/lib/Lex/PPLexerChange.cpp
+++ b/lib/Lex/PPLexerChange.cpp
@@ -624,8 +624,8 @@
void Preprocessor::EnterSubmodule(Module *M, SourceLocation ImportLoc) {
if (!getLangOpts().ModulesLocalVisibility) {
// Just track that we entered this submodule.
- BuildingSubmoduleStack.push_back(
- BuildingSubmoduleInfo(M, ImportLoc, CurSubmoduleState));
+ BuildingSubmoduleStack.push_back(BuildingSubmoduleInfo(
+ M, ImportLoc, CurSubmoduleState, PendingModuleMacroNames.size()));
return;
}
@@ -666,8 +666,8 @@
}
// Track that we entered this module.
- BuildingSubmoduleStack.push_back(
- BuildingSubmoduleInfo(M, ImportLoc, CurSubmoduleState));
+ BuildingSubmoduleStack.push_back(BuildingSubmoduleInfo(
+ M, ImportLoc, CurSubmoduleState, PendingModuleMacroNames.size()));
// Switch to this submodule as the current submodule.
CurSubmoduleState = &State;
@@ -677,27 +677,48 @@
makeModuleVisible(M, ImportLoc);
}
+bool Preprocessor::needModuleMacros() const {
+ // If we're not within a submodule, we never need to create ModuleMacros.
+ if (BuildingSubmoduleStack.empty())
+ return false;
+ // If we are tracking module macro visibility even for textually-included
+ // headers, we need ModuleMacros.
+ if (getLangOpts().ModulesLocalVisibility)
+ return true;
+ // Otherwise, we only need module macros if we're actually compiling a module
+ // interface.
+ return !getLangOpts().CurrentModule.empty();
+}
+
void Preprocessor::LeaveSubmodule() {
auto &Info = BuildingSubmoduleStack.back();
Module *LeavingMod = Info.M;
SourceLocation ImportLoc = Info.ImportLoc;
- if ((!getLangOpts().CompilingModule ||
- LeavingMod->getTopLevelModuleName() != getLangOpts().CurrentModule) &&
- !getLangOpts().ModulesLocalVisibility) {
- // Fast path: if we're leaving a modular header that we included textually,
- // and we're not building the interface for that module, and we're not
- // providing submodule visibility semantics regardless, then we don't need
- // to create ModuleMacros. (We'd never use them.)
+ if (!needModuleMacros() ||
+ (!getLangOpts().ModulesLocalVisibility &&
+ LeavingMod->getTopLevelModuleName() != getLangOpts().CurrentModule)) {
+ // If we don't need module macros, or this is not a module for which we
+ // are tracking macro visibility, don't build any, and preserve the list
+ // of pending names for the surrounding submodule.
BuildingSubmoduleStack.pop_back();
makeModuleVisible(LeavingMod, ImportLoc);
return;
}
// Create ModuleMacros for any macros defined in this submodule.
- for (auto &Macro : CurSubmoduleState->Macros) {
- auto *II = const_cast<IdentifierInfo*>(Macro.first);
+ llvm::SmallPtrSet<const IdentifierInfo*, 8> VisitedMacros;
+ for (unsigned I = Info.OuterPendingModuleMacroNames;
+ I != PendingModuleMacroNames.size(); ++I) {
+ auto *II = const_cast<IdentifierInfo*>(PendingModuleMacroNames[I]);
+ if (!VisitedMacros.insert(II).second)
+ continue;
+
+ auto MacroIt = CurSubmoduleState->Macros.find(II);
+ if (MacroIt == CurSubmoduleState->Macros.end())
+ continue;
+ auto &Macro = MacroIt->second;
// Find the starting point for the MacroDirective chain in this submodule.
MacroDirective *OldMD = nullptr;
@@ -708,7 +729,7 @@
// FIXME: It'd be better to start at the state from when we most recently
// entered this submodule, but it doesn't really matter.
auto &OldMacros = OldState->Macros;
- auto OldMacroIt = OldMacros.find(Macro.first);
+ auto OldMacroIt = OldMacros.find(II);
if (OldMacroIt == OldMacros.end())
OldMD = nullptr;
else
@@ -718,16 +739,17 @@
// This module may have exported a new macro. If so, create a ModuleMacro
// representing that fact.
bool ExplicitlyPublic = false;
- for (auto *MD = Macro.second.getLatest(); MD != OldMD;
- MD = MD->getPrevious()) {
+ for (auto *MD = Macro.getLatest(); MD != OldMD; MD = MD->getPrevious()) {
assert(MD && "broken macro directive chain");
- // Stop on macros defined in other submodules we #included along the way.
- // There's no point doing this if we're tracking local submodule
- // visibility, since there can be no such directives in our list.
+ // Stop on macros defined in other submodules of this module that we
+ // #included along the way. There's no point doing this if we're
+ // tracking local submodule visibility, since there can be no such
+ // directives in our list.
if (!getLangOpts().ModulesLocalVisibility) {
Module *Mod = getModuleContainingLocation(MD->getLocation());
- if (Mod != LeavingMod)
+ if (Mod != LeavingMod &&
+ Mod->getTopLevelModule() == LeavingMod->getTopLevelModule())
break;
}
@@ -749,13 +771,14 @@
bool IsNew;
// Don't bother creating a module macro if it would represent a #undef
// that doesn't override anything.
- if (Def || !Macro.second.getOverriddenMacros().empty())
+ if (Def || !Macro.getOverriddenMacros().empty())
addModuleMacro(LeavingMod, II, Def,
- Macro.second.getOverriddenMacros(), IsNew);
+ Macro.getOverriddenMacros(), IsNew);
break;
}
}
}
+ PendingModuleMacroNames.resize(Info.OuterPendingModuleMacroNames);
// FIXME: Before we leave this submodule, we should parse all the other
// headers within it. Otherwise, we're left with an inconsistent state
diff --git a/lib/Lex/PPMacroExpansion.cpp b/lib/Lex/PPMacroExpansion.cpp
index e168d0d..3d4423b 100644
--- a/lib/Lex/PPMacroExpansion.cpp
+++ b/lib/Lex/PPMacroExpansion.cpp
@@ -52,6 +52,13 @@
StoredMD.setLatest(MD);
StoredMD.overrideActiveModuleMacros(*this, II);
+ if (needModuleMacros()) {
+ // Track that we created a new macro directive, so we know we should
+ // consider building a ModuleMacro for it when we get to the end of
+ // the module.
+ PendingModuleMacroNames.push_back(II);
+ }
+
// Set up the identifier as having associated macro history.
II->setHasMacroDefinition(true);
if (!MD->isDefined() && LeafModuleMacros.find(II) == LeafModuleMacros.end())
