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