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