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