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