[preprocessor] Handle correctly inclusion directives that have macro expansions, e.g

"#include MACRO(STUFF)".

-As an inclusion position for the included file, use the file location of the file where it
was included but *after* the macro expansions. We want the macro expansions to be considered
as before-in-translation-unit for everything in the included file.

-In the preprocessing record take into account that only inclusion directives can be encountered
as "out-of-order" (by comparing the start of the range which for inclusions is the hash location)
and use binary search if there is an extreme number of macro expansions in the include directive.

Fixes rdar://11111779

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@153527 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 45 insertions, 18 deletions

diff --git a/lib/Lex/PPDirectives.cpp b/lib/Lex/PPDirectives.cpp
index 3d96e86cb2..aa3d1bf66d 100644
--- a/lib/Lex/PPDirectives.cpp
+++ b/lib/Lex/PPDirectives.cpp
@@ -1453,8 +1453,12 @@ void Preprocessor::HandleIncludeDirective(SourceLocation HashLoc,
   }
 
   // Look up the file, create a File ID for it.
-  FileID FID = SourceMgr.createFileID(File, FilenameTok.getLocation(),
-                                      FileCharacter);
+  SourceLocation IncludePos = End;
+  // If the filename string was the result of macro expansions, set the include
+  // position on the file where it will be included and after the expansions.
+  if (IncludePos.isMacroID())
+    IncludePos = SourceMgr.getExpansionRange(IncludePos).second;
+  FileID FID = SourceMgr.createFileID(File, IncludePos, FileCharacter);
   assert(!FID.isInvalid() && "Expected valid file ID");
 
   // Finally, if all is good, enter the new file!
diff --git a/lib/Lex/PreprocessingRecord.cpp b/lib/Lex/PreprocessingRecord.cpp
index 440e4780ca..89d19fd52a 100644
--- a/lib/Lex/PreprocessingRecord.cpp
+++ b/lib/Lex/PreprocessingRecord.cpp
@@ -244,33 +244,58 @@ unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
   return I - PreprocessedEntities.begin();
 }
 
-void PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
+PreprocessingRecord::PPEntityID
+PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
   assert(Entity);
   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
-  
+
+  if (!isa<class InclusionDirective>(Entity)) {
+    assert((PreprocessedEntities.empty() ||
+            !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
+                   PreprocessedEntities.back()->getSourceRange().getBegin())) &&
+           "a macro directive was encountered out-of-order");
+    PreprocessedEntities.push_back(Entity);
+    return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
+  }
+
   // Check normal case, this entity begin location is after the previous one.
   if (PreprocessedEntities.empty() ||
       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
     PreprocessedEntities.push_back(Entity);
-    return;
+    return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
   }
 
-  // The entity's location is not after the previous one; this can happen rarely
-  // e.g. with "#include MACRO".
-  // Iterate the entities vector in reverse until we find the right place to
-  // insert the new entity.
-  for (std::vector<PreprocessedEntity *>::iterator
-         RI = PreprocessedEntities.end(), Begin = PreprocessedEntities.begin();
-       RI != Begin; --RI) {
-    std::vector<PreprocessedEntity *>::iterator I = RI;
+  // The entity's location is not after the previous one; this can happen with
+  // include directives that form the filename using macros, e.g:
+  // "#include MACRO(STUFF)".
+
+  typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
+
+  // Usually there are few macro expansions when defining the filename, do a
+  // linear search for a few entities.
+  unsigned count = 0;
+  for (pp_iter RI    = PreprocessedEntities.end(),
+               Begin = PreprocessedEntities.begin();
+       RI != Begin && count < 4; --RI, ++count) {
+    pp_iter I = RI;
     --I;
     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
                                            (*I)->getSourceRange().getBegin())) {
-      PreprocessedEntities.insert(RI, Entity);
-      return;
+      pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
+      return getPPEntityID(insertI - PreprocessedEntities.begin(),
+                           /*isLoaded=*/false);
     }
   }
+
+  // Linear search unsuccessful. Do a binary search.
+  pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
+                               PreprocessedEntities.end(),
+                               BeginLoc,
+                               PPEntityComp<&SourceRange::getBegin>(SourceMgr));
+  pp_iter insertI = PreprocessedEntities.insert(I, Entity);
+  return getPPEntityID(insertI - PreprocessedEntities.begin(),
+                       /*isLoaded=*/false);
 }
 
 void PreprocessingRecord::SetExternalSource(
@@ -351,9 +376,7 @@ void PreprocessingRecord::MacroDefined(const Token &Id,
   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
   MacroDefinition *Def
       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
-  addPreprocessedEntity(Def);
-  MacroDefinitions[MI] = getPPEntityID(PreprocessedEntities.size()-1,
-                                       /*isLoaded=*/false);
+  MacroDefinitions[MI] = addPreprocessedEntity(Def);
 }
 
 void PreprocessingRecord::MacroUndefined(const Token &Id,