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 \p Range 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