contrib/llvm/tools/clang/lib/Lex/PreprocessingRecord.cpp

   1 //===--- PreprocessingRecord.cpp - Record of Preprocessing ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file implements the PreprocessingRecord class, which maintains a record
  11 //  of what occurred during preprocessing, and its helpers.
  12 //
  13 //===----------------------------------------------------------------------===//
  14 #include "clang/Lex/PreprocessingRecord.h"
  15 #include "clang/Lex/MacroInfo.h"
  16 #include "clang/Lex/Token.h"
  17 #include "llvm/Support/ErrorHandling.h"
  18 #include "llvm/Support/Capacity.h"
  19
  20 using namespace clang;
  21
  22 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
  23
  24
  25 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
  26                                        InclusionKind Kind,
  27                                        StringRef FileName,
  28                                        bool InQuotes, bool ImportedModule,
  29                                        const FileEntry *File,
  30                                        SourceRange Range)
  31   : PreprocessingDirective(InclusionDirectiveKind, Range),
  32     InQuotes(InQuotes), Kind(Kind), ImportedModule(ImportedModule), File(File)
  33 {
  34   char *Memory
  35     = (char*)PPRec.Allocate(FileName.size() + 1, llvm::alignOf<char>());
  36   memcpy(Memory, FileName.data(), FileName.size());
  37   Memory[FileName.size()] = 0;
  38   this->FileName = StringRef(Memory, FileName.size());
  39 }
  40
  41 PreprocessingRecord::PreprocessingRecord(SourceManager &SM,
  42                                          bool RecordConditionalDirectives)
  43   : SourceMgr(SM),
  44     RecordCondDirectives(RecordConditionalDirectives), CondDirectiveNextIdx(0),
  45     ExternalSource(0)
  46 {
  47   if (RecordCondDirectives)
  48     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
  49 }
  50
  51 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
  52 /// that source range \p Range encompasses.
  53 std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
  54 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
  55   if (Range.isInvalid())
  56     return std::make_pair(iterator(), iterator());
  57
  58   if (CachedRangeQuery.Range == Range) {
  59     return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
  60                           iterator(this, CachedRangeQuery.Result.second));
  61   }
  62
  63   std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range);
  64
  65   CachedRangeQuery.Range = Range;
  66   CachedRangeQuery.Result = Res;
  67
  68   return std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
  69 }
  70
  71 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
  72                                            SourceManager &SM) {
  73   assert(!FID.isInvalid());
  74   if (!PPE)
  75     return false;
  76
  77   SourceLocation Loc = PPE->getSourceRange().getBegin();
  78   if (Loc.isInvalid())
  79     return false;
  80
  81   if (SM.isInFileID(SM.getFileLoc(Loc), FID))
  82     return true;
  83   else
  84     return false;
  85 }
  86
  87 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
  88 /// points to is coming from the file \arg FID.
  89 ///
  90 /// Can be used to avoid implicit deserializations of preallocated
  91 /// preprocessed entities if we only care about entities of a specific file
  92 /// and not from files \#included in the range given at
  93 /// \see getPreprocessedEntitiesInRange.
  94 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
  95   if (FID.isInvalid())
  96     return false;
  97
  98   int Pos = PPEI.Position;
  99   if (Pos < 0) {
 100     assert(unsigned(-Pos-1) < LoadedPreprocessedEntities.size() &&
 101            "Out-of bounds loaded preprocessed entity");
 102     assert(ExternalSource && "No external source to load from");
 103     unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
 104     if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
 105       return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);
 106
 107     // See if the external source can see if the entity is in the file without
 108     // deserializing it.
 109     llvm::Optional<bool>
 110       IsInFile = ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
 111     if (IsInFile.hasValue())
 112       return IsInFile.getValue();
 113
 114     // The external source did not provide a definite answer, go and deserialize
 115     // the entity to check it.
 116     return isPreprocessedEntityIfInFileID(
 117                                        getLoadedPreprocessedEntity(LoadedIndex),
 118                                           FID, SourceMgr);
 119   }
 120
 121   assert(unsigned(Pos) < PreprocessedEntities.size() &&
 122          "Out-of bounds local preprocessed entity");
 123   return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
 124                                         FID, SourceMgr);
 125 }
 126
 127 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
 128 /// that source range \arg R encompasses.
 129 std::pair<int, int>
 130 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
 131   assert(Range.isValid());
 132   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
 133
 134   std::pair<unsigned, unsigned>
 135     Local = findLocalPreprocessedEntitiesInRange(Range);
 136
 137   // Check if range spans local entities.
 138   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
 139     return std::make_pair(Local.first, Local.second);
 140
 141   std::pair<unsigned, unsigned>
 142     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
 143
 144   // Check if range spans local entities.
 145   if (Loaded.first == Loaded.second)
 146     return std::make_pair(Local.first, Local.second);
 147
 148   unsigned TotalLoaded = LoadedPreprocessedEntities.size();
 149
 150   // Check if range spans loaded entities.
 151   if (Local.first == Local.second)
 152     return std::make_pair(int(Loaded.first)-TotalLoaded,
 153                           int(Loaded.second)-TotalLoaded);
 154
 155   // Range spands loaded and local entities.
 156   return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
 157 }
 158
 159 std::pair<unsigned, unsigned>
 160 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
 161                                                       SourceRange Range) const {
 162   if (Range.isInvalid())
 163     return std::make_pair(0,0);
 164   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
 165
 166   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
 167   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
 168   return std::make_pair(Begin, End);
 169 }
 170
 171 namespace {
 172
 173 template <SourceLocation (SourceRange::*getRangeLoc)() const>
 174 struct PPEntityComp {
 175   const SourceManager &SM;
 176
 177   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
 178
 179   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
 180     SourceLocation LHS = getLoc(L);
 181     SourceLocation RHS = getLoc(R);
 182     return SM.isBeforeInTranslationUnit(LHS, RHS);
 183   }
 184
 185   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
 186     SourceLocation LHS = getLoc(L);
 187     return SM.isBeforeInTranslationUnit(LHS, RHS);
 188   }
 189
 190   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
 191     SourceLocation RHS = getLoc(R);
 192     return SM.isBeforeInTranslationUnit(LHS, RHS);
 193   }
 194
 195   SourceLocation getLoc(PreprocessedEntity *PPE) const {
 196     SourceRange Range = PPE->getSourceRange();
 197     return (Range.*getRangeLoc)();
 198   }
 199 };
 200
 201 }
 202
 203 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
 204                                                      SourceLocation Loc) const {
 205   if (SourceMgr.isLoadedSourceLocation(Loc))
 206     return 0;
 207
 208   size_t Count = PreprocessedEntities.size();
 209   size_t Half;
 210   std::vector<PreprocessedEntity *>::const_iterator
 211     First = PreprocessedEntities.begin();
 212   std::vector<PreprocessedEntity *>::const_iterator I;
 213
 214   // Do a binary search manually instead of using std::lower_bound because
 215   // The end locations of entities may be unordered (when a macro expansion
 216   // is inside another macro argument), but for this case it is not important
 217   // whether we get the first macro expansion or its containing macro.
 218   while (Count > 0) {
 219     Half = Count/2;
 220     I = First;
 221     std::advance(I, Half);
 222     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
 223                                             Loc)){
 224       First = I;
 225       ++First;
 226       Count = Count - Half - 1;
 227     } else
 228       Count = Half;
 229   }
 230
 231   return First - PreprocessedEntities.begin();
 232 }
 233
 234 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
 235                                                      SourceLocation Loc) const {
 236   if (SourceMgr.isLoadedSourceLocation(Loc))
 237     return 0;
 238
 239   std::vector<PreprocessedEntity *>::const_iterator
 240   I = std::upper_bound(PreprocessedEntities.begin(),
 241                        PreprocessedEntities.end(),
 242                        Loc,
 243                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
 244   return I - PreprocessedEntities.begin();
 245 }
 246
 247 PreprocessingRecord::PPEntityID
 248 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
 249   assert(Entity);
 250   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
 251
 252   if (!isa<class InclusionDirective>(Entity)) {
 253     assert((PreprocessedEntities.empty() ||
 254             !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
 255                    PreprocessedEntities.back()->getSourceRange().getBegin())) &&
 256            "a macro directive was encountered out-of-order");
 257     PreprocessedEntities.push_back(Entity);
 258     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
 259   }
 260
 261   // Check normal case, this entity begin location is after the previous one.
 262   if (PreprocessedEntities.empty() ||
 263       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
 264                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
 265     PreprocessedEntities.push_back(Entity);
 266     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
 267   }
 268
 269   // The entity's location is not after the previous one; this can happen with
 270   // include directives that form the filename using macros, e.g:
 271   // "#include MACRO(STUFF)".
 272
 273   typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
 274
 275   // Usually there are few macro expansions when defining the filename, do a
 276   // linear search for a few entities.
 277   unsigned count = 0;
 278   for (pp_iter RI    = PreprocessedEntities.end(),
 279                Begin = PreprocessedEntities.begin();
 280        RI != Begin && count < 4; --RI, ++count) {
 281     pp_iter I = RI;
 282     --I;
 283     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
 284                                            (*I)->getSourceRange().getBegin())) {
 285       pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
 286       return getPPEntityID(insertI - PreprocessedEntities.begin(),
 287                            /*isLoaded=*/false);
 288     }
 289   }
 290
 291   // Linear search unsuccessful. Do a binary search.
 292   pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
 293                                PreprocessedEntities.end(),
 294                                BeginLoc,
 295                                PPEntityComp<&SourceRange::getBegin>(SourceMgr));
 296   pp_iter insertI = PreprocessedEntities.insert(I, Entity);
 297   return getPPEntityID(insertI - PreprocessedEntities.begin(),
 298                        /*isLoaded=*/false);
 299 }
 300
 301 void PreprocessingRecord::SetExternalSource(
 302                                     ExternalPreprocessingRecordSource &Source) {
 303   assert(!ExternalSource &&
 304          "Preprocessing record already has an external source");
 305   ExternalSource = &Source;
 306 }
 307
 308 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
 309   unsigned Result = LoadedPreprocessedEntities.size();
 310   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
 311                                     + NumEntities);
 312   return Result;
 313 }
 314
 315 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
 316                                                   PPEntityID PPID) {
 317   MacroDefinitions[Macro] = PPID;
 318 }
 319
 320 /// \brief Retrieve the preprocessed entity at the given ID.
 321 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
 322   if (PPID.ID < 0) {
 323     unsigned Index = -PPID.ID - 1;
 324     assert(Index < LoadedPreprocessedEntities.size() &&
 325            "Out-of bounds loaded preprocessed entity");
 326     return getLoadedPreprocessedEntity(Index);
 327   }
 328
 329   if (PPID.ID == 0)
 330     return 0;
 331   unsigned Index = PPID.ID - 1;
 332   assert(Index < PreprocessedEntities.size() &&
 333          "Out-of bounds local preprocessed entity");
 334   return PreprocessedEntities[Index];
 335 }
 336
 337 /// \brief Retrieve the loaded preprocessed entity at the given index.
 338 PreprocessedEntity *
 339 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
 340   assert(Index < LoadedPreprocessedEntities.size() &&
 341          "Out-of bounds loaded preprocessed entity");
 342   assert(ExternalSource && "No external source to load from");
 343   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
 344   if (!Entity) {
 345     Entity = ExternalSource->ReadPreprocessedEntity(Index);
 346     if (!Entity) // Failed to load.
 347       Entity = new (*this)
 348          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
 349   }
 350   return Entity;
 351 }
 352
 353 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
 354   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
 355     = MacroDefinitions.find(MI);
 356   if (Pos == MacroDefinitions.end())
 357     return 0;
 358
 359   PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
 360   if (Entity->isInvalid())
 361     return 0;
 362   return cast<MacroDefinition>(Entity);
 363 }
 364
 365 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
 366                                        SourceRange Range) {
 367   // We don't record nested macro expansions.
 368   if (Id.getLocation().isMacroID())
 369     return;
 370
 371   if (MI->isBuiltinMacro())
 372     addPreprocessedEntity(
 373                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
 374   else if (MacroDefinition *Def = findMacroDefinition(MI))
 375     addPreprocessedEntity(
 376                        new (*this) MacroExpansion(Def, Range));
 377 }
 378
 379 void PreprocessingRecord::MacroDefined(const Token &Id,
 380                                        const MacroInfo *MI) {
 381   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
 382   MacroDefinition *Def
 383       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
 384   MacroDefinitions[MI] = addPreprocessedEntity(Def);
 385 }
 386
 387 void PreprocessingRecord::MacroUndefined(const Token &Id,
 388                                          const MacroInfo *MI) {
 389   MacroDefinitions.erase(MI);
 390 }
 391
 392 void PreprocessingRecord::InclusionDirective(
 393     SourceLocation HashLoc,
 394     const clang::Token &IncludeTok,
 395     StringRef FileName,
 396     bool IsAngled,
 397     CharSourceRange FilenameRange,
 398     const FileEntry *File,
 399     StringRef SearchPath,
 400     StringRef RelativePath,
 401     const Module *Imported) {
 402   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
 403
 404   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
 405   case tok::pp_include:
 406     Kind = InclusionDirective::Include;
 407     break;
 408
 409   case tok::pp_import:
 410     Kind = InclusionDirective::Import;
 411     break;
 412
 413   case tok::pp_include_next:
 414     Kind = InclusionDirective::IncludeNext;
 415     break;
 416
 417   case tok::pp___include_macros:
 418     Kind = InclusionDirective::IncludeMacros;
 419     break;
 420
 421   default:
 422     llvm_unreachable("Unknown include directive kind");
 423   }
 424
 425   SourceLocation EndLoc;
 426   if (!IsAngled) {
 427     EndLoc = FilenameRange.getBegin();
 428   } else {
 429     EndLoc = FilenameRange.getEnd();
 430     if (FilenameRange.isCharRange())
 431       EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
 432                                             // a token range.
 433   }
 434   clang::InclusionDirective *ID
 435     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
 436                                             (bool)Imported,
 437                                             File, SourceRange(HashLoc, EndLoc));
 438   addPreprocessedEntity(ID);
 439 }
 440
 441 bool PreprocessingRecord::rangeIntersectsConditionalDirective(
 442                                                       SourceRange Range) const {
 443   if (Range.isInvalid())
 444     return false;
 445
 446   CondDirectiveLocsTy::const_iterator
 447     low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
 448                            Range.getBegin(), CondDirectiveLoc::Comp(SourceMgr));
 449   if (low == CondDirectiveLocs.end())
 450     return false;
 451
 452   if (SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), low->getLoc()))
 453     return false;
 454
 455   CondDirectiveLocsTy::const_iterator
 456     upp = std::upper_bound(low, CondDirectiveLocs.end(),
 457                            Range.getEnd(), CondDirectiveLoc::Comp(SourceMgr));
 458   unsigned uppIdx;
 459   if (upp != CondDirectiveLocs.end())
 460     uppIdx = upp->getIdx();
 461   else
 462     uppIdx = 0;
 463
 464   return low->getIdx() != uppIdx;
 465 }
 466
 467 unsigned PreprocessingRecord::findCondDirectiveIdx(SourceLocation Loc) const {
 468   if (Loc.isInvalid())
 469     return 0;
 470
 471   CondDirectiveLocsTy::const_iterator
 472     low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
 473                            Loc, CondDirectiveLoc::Comp(SourceMgr));
 474   if (low == CondDirectiveLocs.end())
 475     return 0;
 476   return low->getIdx();
 477 }
 478
 479 void PreprocessingRecord::addCondDirectiveLoc(CondDirectiveLoc DirLoc) {
 480   // Ignore directives in system headers.
 481   if (SourceMgr.isInSystemHeader(DirLoc.getLoc()))
 482     return;
 483
 484   assert(CondDirectiveLocs.empty() ||
 485          SourceMgr.isBeforeInTranslationUnit(CondDirectiveLocs.back().getLoc(),
 486                                              DirLoc.getLoc()));
 487   CondDirectiveLocs.push_back(DirLoc);
 488 }
 489
 490 void PreprocessingRecord::If(SourceLocation Loc, SourceRange ConditionRange) {
 491   if (RecordCondDirectives) {
 492     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
 493     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
 494   }
 495 }
 496
 497 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok) {
 498   if (RecordCondDirectives) {
 499     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
 500     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
 501   }
 502 }
 503
 504 void PreprocessingRecord::Ifndef(SourceLocation Loc,const Token &MacroNameTok) {
 505   if (RecordCondDirectives) {
 506     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
 507     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
 508   }
 509 }
 510
 511 void PreprocessingRecord::Elif(SourceLocation Loc, SourceRange ConditionRange,
 512                                SourceLocation IfLoc) {
 513   if (RecordCondDirectives)
 514     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
 515 }
 516
 517 void PreprocessingRecord::Else(SourceLocation Loc, SourceLocation IfLoc) {
 518   if (RecordCondDirectives)
 519     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
 520 }
 521
 522 void PreprocessingRecord::Endif(SourceLocation Loc, SourceLocation IfLoc) {
 523   if (RecordCondDirectives) {
 524     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
 525     assert(!CondDirectiveStack.empty());
 526     CondDirectiveStack.pop_back();
 527   }
 528 }
 529
 530 size_t PreprocessingRecord::getTotalMemory() const {
 531   return BumpAlloc.getTotalMemory()
 532     + llvm::capacity_in_bytes(MacroDefinitions)
 533     + llvm::capacity_in_bytes(PreprocessedEntities)
 534     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
 535 }