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