clang/lib/Lex/PreprocessingRecord.cpp

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