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 /// \brief 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 /// \brief 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 /// \brief 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 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
 333                                                   MacroDefinitionRecord *Def) {
 334   MacroDefinitions[Macro] = Def;
 335 }
 336
 337 /// \brief Retrieve the preprocessed entity at the given ID.
 338 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
 339   if (PPID.ID < 0) {
 340     unsigned Index = -PPID.ID - 1;
 341     assert(Index < LoadedPreprocessedEntities.size() &&
 342            "Out-of bounds loaded preprocessed entity");
 343     return getLoadedPreprocessedEntity(Index);
 344   }
 345
 346   if (PPID.ID == 0)
 347     return nullptr;
 348   unsigned Index = PPID.ID - 1;
 349   assert(Index < PreprocessedEntities.size() &&
 350          "Out-of bounds local preprocessed entity");
 351   return PreprocessedEntities[Index];
 352 }
 353
 354 /// \brief Retrieve the loaded preprocessed entity at the given index.
 355 PreprocessedEntity *
 356 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
 357   assert(Index < LoadedPreprocessedEntities.size() &&
 358          "Out-of bounds loaded preprocessed entity");
 359   assert(ExternalSource && "No external source to load from");
 360   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
 361   if (!Entity) {
 362     Entity = ExternalSource->ReadPreprocessedEntity(Index);
 363     if (!Entity) // Failed to load.
 364       Entity = new (*this)
 365          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
 366   }
 367   return Entity;
 368 }
 369
 370 MacroDefinitionRecord *
 371 PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
 372   llvm::DenseMap<const MacroInfo *, MacroDefinitionRecord *>::iterator Pos =
 373       MacroDefinitions.find(MI);
 374   if (Pos == MacroDefinitions.end())
 375     return nullptr;
 376
 377   return Pos->second;
 378 }
 379
 380 void PreprocessingRecord::addMacroExpansion(const Token &Id,
 381                                             const MacroInfo *MI,
 382                                             SourceRange Range) {
 383   // We don't record nested macro expansions.
 384   if (Id.getLocation().isMacroID())
 385     return;
 386
 387   if (MI->isBuiltinMacro())
 388     addPreprocessedEntity(new (*this)
 389                               MacroExpansion(Id.getIdentifierInfo(), Range));
 390   else if (MacroDefinitionRecord *Def = findMacroDefinition(MI))
 391     addPreprocessedEntity(new (*this) MacroExpansion(Def, Range));
 392 }
 393
 394 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
 395                                 const MacroDefinition &MD) {
 396   // This is not actually a macro expansion but record it as a macro reference.
 397   if (MD)
 398     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
 399                       MacroNameTok.getLocation());
 400 }
 401
 402 void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
 403                                  const MacroDefinition &MD) {
 404   // This is not actually a macro expansion but record it as a macro reference.
 405   if (MD)
 406     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
 407                       MacroNameTok.getLocation());
 408 }
 409
 410 void PreprocessingRecord::Defined(const Token &MacroNameTok,
 411                                   const MacroDefinition &MD,
 412                                   SourceRange Range) {
 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::SourceRangeSkipped(SourceRange Range,
 420                                              SourceLocation EndifLoc) {
 421   SkippedRanges.emplace_back(Range.getBegin(), EndifLoc);
 422 }
 423
 424 void PreprocessingRecord::MacroExpands(const Token &Id,
 425                                        const MacroDefinition &MD,
 426                                        SourceRange Range,
 427                                        const MacroArgs *Args) {
 428   addMacroExpansion(Id, MD.getMacroInfo(), Range);
 429 }
 430
 431 void PreprocessingRecord::MacroDefined(const Token &Id,
 432                                        const MacroDirective *MD) {
 433   const MacroInfo *MI = MD->getMacroInfo();
 434   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
 435   MacroDefinitionRecord *Def =
 436       new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R);
 437   addPreprocessedEntity(Def);
 438   MacroDefinitions[MI] = Def;
 439 }
 440
 441 void PreprocessingRecord::MacroUndefined(const Token &Id,
 442                                          const MacroDefinition &MD,
 443                                          const MacroDirective *Undef) {
 444   MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });
 445 }
 446
 447 void PreprocessingRecord::InclusionDirective(
 448     SourceLocation HashLoc,
 449     const Token &IncludeTok,
 450     StringRef FileName,
 451     bool IsAngled,
 452     CharSourceRange FilenameRange,
 453     const FileEntry *File,
 454     StringRef SearchPath,
 455     StringRef RelativePath,
 456     const Module *Imported) {
 457   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
 458
 459   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
 460   case tok::pp_include:
 461     Kind = InclusionDirective::Include;
 462     break;
 463
 464   case tok::pp_import:
 465     Kind = InclusionDirective::Import;
 466     break;
 467
 468   case tok::pp_include_next:
 469     Kind = InclusionDirective::IncludeNext;
 470     break;
 471
 472   case tok::pp___include_macros:
 473     Kind = InclusionDirective::IncludeMacros;
 474     break;
 475
 476   default:
 477     llvm_unreachable("Unknown include directive kind");
 478   }
 479
 480   SourceLocation EndLoc;
 481   if (!IsAngled) {
 482     EndLoc = FilenameRange.getBegin();
 483   } else {
 484     EndLoc = FilenameRange.getEnd();
 485     if (FilenameRange.isCharRange())
 486       EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
 487                                             // a token range.
 488   }
 489   clang::InclusionDirective *ID =
 490       new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
 491                                             (bool)Imported, File,
 492                                             SourceRange(HashLoc, EndLoc));
 493   addPreprocessedEntity(ID);
 494 }
 495
 496 size_t PreprocessingRecord::getTotalMemory() const {
 497   return BumpAlloc.getTotalMemory()
 498     + llvm::capacity_in_bytes(MacroDefinitions)
 499     + llvm::capacity_in_bytes(PreprocessedEntities)
 500     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
 501 }