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

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