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