| 1 |
//===- Tokens.cpp - collect tokens from preprocessing ---------------------===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
#include "clang/Tooling/Syntax/Tokens.h" |
| 9 |
|
| 10 |
#include "clang/Basic/Diagnostic.h" |
| 11 |
#include "clang/Basic/IdentifierTable.h" |
| 12 |
#include "clang/Basic/LLVM.h" |
| 13 |
#include "clang/Basic/LangOptions.h" |
| 14 |
#include "clang/Basic/SourceLocation.h" |
| 15 |
#include "clang/Basic/SourceManager.h" |
| 16 |
#include "clang/Basic/TokenKinds.h" |
| 17 |
#include "clang/Lex/PPCallbacks.h" |
| 18 |
#include "clang/Lex/Preprocessor.h" |
| 19 |
#include "clang/Lex/Token.h" |
| 20 |
#include "llvm/ADT/ArrayRef.h" |
| 21 |
#include "llvm/ADT/STLExtras.h" |
| 22 |
#include "llvm/Support/Debug.h" |
| 23 |
#include "llvm/Support/ErrorHandling.h" |
| 24 |
#include "llvm/Support/FormatVariadic.h" |
| 25 |
#include "llvm/Support/raw_ostream.h" |
| 26 |
#include <algorithm> |
| 27 |
#include <cassert> |
| 28 |
#include <iterator> |
| 29 |
#include <optional> |
| 30 |
#include <string> |
| 31 |
#include <utility> |
| 32 |
#include <vector> |
| 33 |
|
| 34 |
using namespace clang; |
| 35 |
using namespace clang::syntax; |
| 36 |
|
| 37 |
namespace { |
| 38 |
// Finds the smallest consecutive subsuquence of Toks that covers R. |
| 39 |
llvm::ArrayRef<syntax::Token> |
| 40 |
getTokensCovering(llvm::ArrayRef<syntax::Token> Toks, SourceRange R, |
| 41 |
const SourceManager &SM) { |
| 42 |
if (R.isInvalid()) |
| 43 |
return {}; |
| 44 |
const syntax::Token *Begin = |
| 45 |
llvm::partition_point(Toks, [&](const syntax::Token &T) { |
| 46 |
return SM.isBeforeInTranslationUnit(T.location(), R.getBegin()); |
| 47 |
}); |
| 48 |
const syntax::Token *End = |
| 49 |
llvm::partition_point(Toks, [&](const syntax::Token &T) { |
| 50 |
return !SM.isBeforeInTranslationUnit(R.getEnd(), T.location()); |
| 51 |
}); |
| 52 |
if (Begin > End) |
| 53 |
return {}; |
| 54 |
return {Begin, End}; |
| 55 |
} |
| 56 |
|
| 57 |
// Finds the range within FID corresponding to expanded tokens [First, Last]. |
| 58 |
// Prev precedes First and Next follows Last, these must *not* be included. |
| 59 |
// If no range satisfies the criteria, returns an invalid range. |
| 60 |
// |
| 61 |
// #define ID(x) x |
| 62 |
// ID(ID(ID(a1) a2)) |
| 63 |
// ~~ -> a1 |
| 64 |
// ~~ -> a2 |
| 65 |
// ~~~~~~~~~ -> a1 a2 |
| 66 |
SourceRange spelledForExpandedSlow(SourceLocation First, SourceLocation Last, |
| 67 |
SourceLocation Prev, SourceLocation Next, |
| 68 |
FileID TargetFile, |
| 69 |
const SourceManager &SM) { |
| 70 |
// There are two main parts to this algorithm: |
| 71 |
// - identifying which spelled range covers the expanded tokens |
| 72 |
// - validating that this range doesn't cover any extra tokens (First/Last) |
| 73 |
// |
| 74 |
// We do these in order. However as we transform the expanded range into the |
| 75 |
// spelled one, we adjust First/Last so the validation remains simple. |
| 76 |
|
| 77 |
assert(SM.getSLocEntry(TargetFile).isFile()); |
| 78 |
// In most cases, to select First and Last we must return their expansion |
| 79 |
// range, i.e. the whole of any macros they are included in. |
| 80 |
// |
| 81 |
// When First and Last are part of the *same macro arg* of a macro written |
| 82 |
// in TargetFile, we that slice of the arg, i.e. their spelling range. |
| 83 |
// |
| 84 |
// Unwrap such macro calls. If the target file has A(B(C)), the |
| 85 |
// SourceLocation stack of a token inside C shows us the expansion of A first, |
| 86 |
// then B, then any macros inside C's body, then C itself. |
| 87 |
// (This is the reverse of the order the PP applies the expansions in). |
| 88 |
while (First.isMacroID() && Last.isMacroID()) { |
| 89 |
auto DecFirst = SM.getDecomposedLoc(First); |
| 90 |
auto DecLast = SM.getDecomposedLoc(Last); |
| 91 |
auto &ExpFirst = SM.getSLocEntry(DecFirst.first).getExpansion(); |
| 92 |
auto &ExpLast = SM.getSLocEntry(DecLast.first).getExpansion(); |
| 93 |
|
| 94 |
if (!ExpFirst.isMacroArgExpansion() || !ExpLast.isMacroArgExpansion()) |
| 95 |
break; |
| 96 |
// Locations are in the same macro arg if they expand to the same place. |
| 97 |
// (They may still have different FileIDs - an arg can have >1 chunks!) |
| 98 |
if (ExpFirst.getExpansionLocStart() != ExpLast.getExpansionLocStart()) |
| 99 |
break; |
| 100 |
// Careful, given: |
| 101 |
// #define HIDE ID(ID(a)) |
| 102 |
// ID(ID(HIDE)) |
| 103 |
// The token `a` is wrapped in 4 arg-expansions, we only want to unwrap 2. |
| 104 |
// We distinguish them by whether the macro expands into the target file. |
| 105 |
// Fortunately, the target file ones will always appear first. |
| 106 |
auto &ExpMacro = |
| 107 |
SM.getSLocEntry(SM.getFileID(ExpFirst.getExpansionLocStart())) |
| 108 |
.getExpansion(); |
| 109 |
if (ExpMacro.getExpansionLocStart().isMacroID()) |
| 110 |
break; |
| 111 |
// Replace each endpoint with its spelling inside the macro arg. |
| 112 |
// (This is getImmediateSpellingLoc without repeating lookups). |
| 113 |
First = ExpFirst.getSpellingLoc().getLocWithOffset(DecFirst.second); |
| 114 |
Last = ExpLast.getSpellingLoc().getLocWithOffset(DecLast.second); |
| 115 |
|
| 116 |
// Now: how do we adjust the previous/next bounds? Three cases: |
| 117 |
// A) If they are also part of the same macro arg, we translate them too. |
| 118 |
// This will ensure that we don't select any macros nested within the |
| 119 |
// macro arg that cover extra tokens. Critical case: |
| 120 |
// #define ID(X) X |
| 121 |
// ID(prev target) // selecting 'target' succeeds |
| 122 |
// #define LARGE ID(prev target) |
| 123 |
// LARGE // selecting 'target' fails. |
| 124 |
// B) They are not in the macro at all, then their expansion range is a |
| 125 |
// sibling to it, and we can safely substitute that. |
| 126 |
// #define PREV prev |
| 127 |
// #define ID(X) X |
| 128 |
// PREV ID(target) // selecting 'target' succeeds. |
| 129 |
// #define LARGE PREV ID(target) |
| 130 |
// LARGE // selecting 'target' fails. |
| 131 |
// C) They are in a different arg of this macro, or the macro body. |
| 132 |
// Now selecting the whole macro arg is fine, but the whole macro is not. |
| 133 |
// Model this by setting using the edge of the macro call as the bound. |
| 134 |
// #define ID2(X, Y) X Y |
| 135 |
// ID2(prev, target) // selecting 'target' succeeds |
| 136 |
// #define LARGE ID2(prev, target) |
| 137 |
// LARGE // selecting 'target' fails |
| 138 |
auto AdjustBound = [&](SourceLocation &Bound) { |
| 139 |
if (Bound.isInvalid() || !Bound.isMacroID()) // Non-macro must be case B. |
| 140 |
return; |
| 141 |
auto DecBound = SM.getDecomposedLoc(Bound); |
| 142 |
auto &ExpBound = SM.getSLocEntry(DecBound.first).getExpansion(); |
| 143 |
if (ExpBound.isMacroArgExpansion() && |
| 144 |
ExpBound.getExpansionLocStart() == ExpFirst.getExpansionLocStart()) { |
| 145 |
// Case A: translate to (spelling) loc within the macro arg. |
| 146 |
Bound = ExpBound.getSpellingLoc().getLocWithOffset(DecBound.second); |
| 147 |
return; |
| 148 |
} |
| 149 |
while (Bound.isMacroID()) { |
| 150 |
SourceRange Exp = SM.getImmediateExpansionRange(Bound).getAsRange(); |
| 151 |
if (Exp.getBegin() == ExpMacro.getExpansionLocStart()) { |
| 152 |
// Case B: bounds become the macro call itself. |
| 153 |
Bound = (&Bound == &Prev) ? Exp.getBegin() : Exp.getEnd(); |
| 154 |
return; |
| 155 |
} |
| 156 |
// Either case C, or expansion location will later find case B. |
| 157 |
// We choose the upper bound for Prev and the lower one for Next: |
| 158 |
// ID(prev) target ID(next) |
| 159 |
// ^ ^ |
| 160 |
// new-prev new-next |
| 161 |
Bound = (&Bound == &Prev) ? Exp.getEnd() : Exp.getBegin(); |
| 162 |
} |
| 163 |
}; |
| 164 |
AdjustBound(Prev); |
| 165 |
AdjustBound(Next); |
| 166 |
} |
| 167 |
|
| 168 |
// In all remaining cases we need the full containing macros. |
| 169 |
// If this overlaps Prev or Next, then no range is possible. |
| 170 |
SourceRange Candidate = |
| 171 |
SM.getExpansionRange(SourceRange(First, Last)).getAsRange(); |
| 172 |
auto DecFirst = SM.getDecomposedExpansionLoc(Candidate.getBegin()); |
| 173 |
auto DecLast = SM.getDecomposedLoc(Candidate.getEnd()); |
| 174 |
// Can end up in the wrong file due to bad input or token-pasting shenanigans. |
| 175 |
if (Candidate.isInvalid() || DecFirst.first != TargetFile || DecLast.first != TargetFile) |
| 176 |
return SourceRange(); |
| 177 |
// Check bounds, which may still be inside macros. |
| 178 |
if (Prev.isValid()) { |
| 179 |
auto Dec = SM.getDecomposedLoc(SM.getExpansionRange(Prev).getBegin()); |
| 180 |
if (Dec.first != DecFirst.first || Dec.second >= DecFirst.second) |
| 181 |
return SourceRange(); |
| 182 |
} |
| 183 |
if (Next.isValid()) { |
| 184 |
auto Dec = SM.getDecomposedLoc(SM.getExpansionRange(Next).getEnd()); |
| 185 |
if (Dec.first != DecLast.first || Dec.second <= DecLast.second) |
| 186 |
return SourceRange(); |
| 187 |
} |
| 188 |
// Now we know that Candidate is a file range that covers [First, Last] |
| 189 |
// without encroaching on {Prev, Next}. Ship it! |
| 190 |
return Candidate; |
| 191 |
} |
| 192 |
|
| 193 |
} // namespace |
| 194 |
|
| 195 |
syntax::Token::Token(SourceLocation Location, unsigned Length, |
| 196 |
tok::TokenKind Kind) |
| 197 |
: Location(Location), Length(Length), Kind(Kind) { |
| 198 |
assert(Location.isValid()); |
| 199 |
} |
| 200 |
|
| 201 |
syntax::Token::Token(const clang::Token &T) |
| 202 |
: Token(T.getLocation(), T.getLength(), T.getKind()) { |
| 203 |
assert(!T.isAnnotation()); |
| 204 |
} |
| 205 |
|
| 206 |
llvm::StringRef syntax::Token::text(const SourceManager &SM) const { |
| 207 |
bool Invalid = false; |
| 208 |
const char *Start = SM.getCharacterData(location(), &Invalid); |
| 209 |
assert(!Invalid); |
| 210 |
return llvm::StringRef(Start, length()); |
| 211 |
} |
| 212 |
|
| 213 |
FileRange syntax::Token::range(const SourceManager &SM) const { |
| 214 |
assert(location().isFileID() && "must be a spelled token"); |
| 215 |
FileID File; |
| 216 |
unsigned StartOffset; |
| 217 |
std::tie(File, StartOffset) = SM.getDecomposedLoc(location()); |
| 218 |
return FileRange(File, StartOffset, StartOffset + length()); |
| 219 |
} |
| 220 |
|
| 221 |
FileRange syntax::Token::range(const SourceManager &SM, |
| 222 |
const syntax::Token &First, |
| 223 |
const syntax::Token &Last) { |
| 224 |
auto F = First.range(SM); |
| 225 |
auto L = Last.range(SM); |
| 226 |
assert(F.file() == L.file() && "tokens from different files"); |
| 227 |
assert((F == L || F.endOffset() <= L.beginOffset()) && |
| 228 |
"wrong order of tokens"); |
| 229 |
return FileRange(F.file(), F.beginOffset(), L.endOffset()); |
| 230 |
} |
| 231 |
|
| 232 |
llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, const Token &T) { |
| 233 |
return OS << T.str(); |
| 234 |
} |
| 235 |
|
| 236 |
FileRange::FileRange(FileID File, unsigned BeginOffset, unsigned EndOffset) |
| 237 |
: File(File), Begin(BeginOffset), End(EndOffset) { |
| 238 |
assert(File.isValid()); |
| 239 |
assert(BeginOffset <= EndOffset); |
| 240 |
} |
| 241 |
|
| 242 |
FileRange::FileRange(const SourceManager &SM, SourceLocation BeginLoc, |
| 243 |
unsigned Length) { |
| 244 |
assert(BeginLoc.isValid()); |
| 245 |
assert(BeginLoc.isFileID()); |
| 246 |
|
| 247 |
std::tie(File, Begin) = SM.getDecomposedLoc(BeginLoc); |
| 248 |
End = Begin + Length; |
| 249 |
} |
| 250 |
FileRange::FileRange(const SourceManager &SM, SourceLocation BeginLoc, |
| 251 |
SourceLocation EndLoc) { |
| 252 |
assert(BeginLoc.isValid()); |
| 253 |
assert(BeginLoc.isFileID()); |
| 254 |
assert(EndLoc.isValid()); |
| 255 |
assert(EndLoc.isFileID()); |
| 256 |
assert(SM.getFileID(BeginLoc) == SM.getFileID(EndLoc)); |
| 257 |
assert(SM.getFileOffset(BeginLoc) <= SM.getFileOffset(EndLoc)); |
| 258 |
|
| 259 |
std::tie(File, Begin) = SM.getDecomposedLoc(BeginLoc); |
| 260 |
End = SM.getFileOffset(EndLoc); |
| 261 |
} |
| 262 |
|
| 263 |
llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, |
| 264 |
const FileRange &R) { |
| 265 |
return OS << llvm::formatv("FileRange(file = {0}, offsets = {1}-{2})", |
| 266 |
R.file().getHashValue(), R.beginOffset(), |
| 267 |
R.endOffset()); |
| 268 |
} |
| 269 |
|
| 270 |
llvm::StringRef FileRange::text(const SourceManager &SM) const { |
| 271 |
bool Invalid = false; |
| 272 |
StringRef Text = SM.getBufferData(File, &Invalid); |
| 273 |
if (Invalid) |
| 274 |
return ""; |
| 275 |
assert(Begin <= Text.size()); |
| 276 |
assert(End <= Text.size()); |
| 277 |
return Text.substr(Begin, length()); |
| 278 |
} |
| 279 |
|
| 280 |
void TokenBuffer::indexExpandedTokens() { |
| 281 |
// No-op if the index is already created. |
| 282 |
if (!ExpandedTokIndex.empty()) |
| 283 |
return; |
| 284 |
ExpandedTokIndex.reserve(ExpandedTokens.size()); |
| 285 |
// Index ExpandedTokens for faster lookups by SourceLocation. |
| 286 |
for (size_t I = 0, E = ExpandedTokens.size(); I != E; ++I) { |
| 287 |
SourceLocation Loc = ExpandedTokens[I].location(); |
| 288 |
if (Loc.isValid()) |
| 289 |
ExpandedTokIndex[Loc] = I; |
| 290 |
} |
| 291 |
} |
| 292 |
|
| 293 |
llvm::ArrayRef<syntax::Token> TokenBuffer::expandedTokens(SourceRange R) const { |
| 294 |
if (R.isInvalid()) |
| 295 |
return {}; |
| 296 |
if (!ExpandedTokIndex.empty()) { |
| 297 |
// Quick lookup if `R` is a token range. |
| 298 |
// This is a huge win since majority of the users use ranges provided by an |
| 299 |
// AST. Ranges in AST are token ranges from expanded token stream. |
| 300 |
const auto B = ExpandedTokIndex.find(R.getBegin()); |
| 301 |
const auto E = ExpandedTokIndex.find(R.getEnd()); |
| 302 |
if (B != ExpandedTokIndex.end() && E != ExpandedTokIndex.end()) { |
| 303 |
const Token *L = ExpandedTokens.data() + B->getSecond(); |
| 304 |
// Add 1 to End to make a half-open range. |
| 305 |
const Token *R = ExpandedTokens.data() + E->getSecond() + 1; |
| 306 |
if (L > R) |
| 307 |
return {}; |
| 308 |
return {L, R}; |
| 309 |
} |
| 310 |
} |
| 311 |
// Slow case. Use `isBeforeInTranslationUnit` to binary search for the |
| 312 |
// required range. |
| 313 |
return getTokensCovering(expandedTokens(), R, *SourceMgr); |
| 314 |
} |
| 315 |
|
| 316 |
CharSourceRange FileRange::toCharRange(const SourceManager &SM) const { |
| 317 |
return CharSourceRange( |
| 318 |
SourceRange(SM.getComposedLoc(File, Begin), SM.getComposedLoc(File, End)), |
| 319 |
/*IsTokenRange=*/false); |
| 320 |
} |
| 321 |
|
| 322 |
std::pair<const syntax::Token *, const TokenBuffer::Mapping *> |
| 323 |
TokenBuffer::spelledForExpandedToken(const syntax::Token *Expanded) const { |
| 324 |
assert(Expanded); |
| 325 |
assert(ExpandedTokens.data() <= Expanded && |
| 326 |
Expanded < ExpandedTokens.data() + ExpandedTokens.size()); |
| 327 |
|
| 328 |
auto FileIt = Files.find( |
| 329 |
SourceMgr->getFileID(SourceMgr->getExpansionLoc(Expanded->location()))); |
| 330 |
assert(FileIt != Files.end() && "no file for an expanded token"); |
| 331 |
|
| 332 |
const MarkedFile &File = FileIt->second; |
| 333 |
|
| 334 |
unsigned ExpandedIndex = Expanded - ExpandedTokens.data(); |
| 335 |
// Find the first mapping that produced tokens after \p Expanded. |
| 336 |
auto It = llvm::partition_point(File.Mappings, [&](const Mapping &M) { |
| 337 |
return M.BeginExpanded <= ExpandedIndex; |
| 338 |
}); |
| 339 |
// Our token could only be produced by the previous mapping. |
| 340 |
if (It == File.Mappings.begin()) { |
| 341 |
// No previous mapping, no need to modify offsets. |
| 342 |
return {&File.SpelledTokens[ExpandedIndex - File.BeginExpanded], |
| 343 |
/*Mapping=*/nullptr}; |
| 344 |
} |
| 345 |
--It; // 'It' now points to last mapping that started before our token. |
| 346 |
|
| 347 |
// Check if the token is part of the mapping. |
| 348 |
if (ExpandedIndex < It->EndExpanded) |
| 349 |
return {&File.SpelledTokens[It->BeginSpelled], /*Mapping=*/&*It}; |
| 350 |
|
| 351 |
// Not part of the mapping, use the index from previous mapping to compute the |
| 352 |
// corresponding spelled token. |
| 353 |
return { |
| 354 |
&File.SpelledTokens[It->EndSpelled + (ExpandedIndex - It->EndExpanded)], |
| 355 |
/*Mapping=*/nullptr}; |
| 356 |
} |
| 357 |
|
| 358 |
const TokenBuffer::Mapping * |
| 359 |
TokenBuffer::mappingStartingBeforeSpelled(const MarkedFile &F, |
| 360 |
const syntax::Token *Spelled) { |
| 361 |
assert(F.SpelledTokens.data() <= Spelled); |
| 362 |
unsigned SpelledI = Spelled - F.SpelledTokens.data(); |
| 363 |
assert(SpelledI < F.SpelledTokens.size()); |
| 364 |
|
| 365 |
auto It = llvm::partition_point(F.Mappings, [SpelledI](const Mapping &M) { |
| 366 |
return M.BeginSpelled <= SpelledI; |
| 367 |
}); |
| 368 |
if (It == F.Mappings.begin()) |
| 369 |
return nullptr; |
| 370 |
--It; |
| 371 |
return &*It; |
| 372 |
} |
| 373 |
|
| 374 |
llvm::SmallVector<llvm::ArrayRef<syntax::Token>, 1> |
| 375 |
TokenBuffer::expandedForSpelled(llvm::ArrayRef<syntax::Token> Spelled) const { |
| 376 |
if (Spelled.empty()) |
| 377 |
return {}; |
| 378 |
const auto &File = fileForSpelled(Spelled); |
| 379 |
|
| 380 |
auto *FrontMapping = mappingStartingBeforeSpelled(File, &Spelled.front()); |
| 381 |
unsigned SpelledFrontI = &Spelled.front() - File.SpelledTokens.data(); |
| 382 |
assert(SpelledFrontI < File.SpelledTokens.size()); |
| 383 |
unsigned ExpandedBegin; |
| 384 |
if (!FrontMapping) { |
| 385 |
// No mapping that starts before the first token of Spelled, we don't have |
| 386 |
// to modify offsets. |
| 387 |
ExpandedBegin = File.BeginExpanded + SpelledFrontI; |
| 388 |
} else if (SpelledFrontI < FrontMapping->EndSpelled) { |
| 389 |
// This mapping applies to Spelled tokens. |
| 390 |
if (SpelledFrontI != FrontMapping->BeginSpelled) { |
| 391 |
// Spelled tokens don't cover the entire mapping, returning empty result. |
| 392 |
return {}; // FIXME: support macro arguments. |
| 393 |
} |
| 394 |
// Spelled tokens start at the beginning of this mapping. |
| 395 |
ExpandedBegin = FrontMapping->BeginExpanded; |
| 396 |
} else { |
| 397 |
// Spelled tokens start after the mapping ends (they start in the hole |
| 398 |
// between 2 mappings, or between a mapping and end of the file). |
| 399 |
ExpandedBegin = |
| 400 |
FrontMapping->EndExpanded + (SpelledFrontI - FrontMapping->EndSpelled); |
| 401 |
} |
| 402 |
|
| 403 |
auto *BackMapping = mappingStartingBeforeSpelled(File, &Spelled.back()); |
| 404 |
unsigned SpelledBackI = &Spelled.back() - File.SpelledTokens.data(); |
| 405 |
unsigned ExpandedEnd; |
| 406 |
if (!BackMapping) { |
| 407 |
// No mapping that starts before the last token of Spelled, we don't have to |
| 408 |
// modify offsets. |
| 409 |
ExpandedEnd = File.BeginExpanded + SpelledBackI + 1; |
| 410 |
} else if (SpelledBackI < BackMapping->EndSpelled) { |
| 411 |
// This mapping applies to Spelled tokens. |
| 412 |
if (SpelledBackI + 1 != BackMapping->EndSpelled) { |
| 413 |
// Spelled tokens don't cover the entire mapping, returning empty result. |
| 414 |
return {}; // FIXME: support macro arguments. |
| 415 |
} |
| 416 |
ExpandedEnd = BackMapping->EndExpanded; |
| 417 |
} else { |
| 418 |
// Spelled tokens end after the mapping ends. |
| 419 |
ExpandedEnd = |
| 420 |
BackMapping->EndExpanded + (SpelledBackI - BackMapping->EndSpelled) + 1; |
| 421 |
} |
| 422 |
|
| 423 |
assert(ExpandedBegin < ExpandedTokens.size()); |
| 424 |
assert(ExpandedEnd < ExpandedTokens.size()); |
| 425 |
// Avoid returning empty ranges. |
| 426 |
if (ExpandedBegin == ExpandedEnd) |
| 427 |
return {}; |
| 428 |
return {llvm::ArrayRef(ExpandedTokens.data() + ExpandedBegin, |
| 429 |
ExpandedTokens.data() + ExpandedEnd)}; |
| 430 |
} |
| 431 |
|
| 432 |
llvm::ArrayRef<syntax::Token> TokenBuffer::spelledTokens(FileID FID) const { |
| 433 |
auto It = Files.find(FID); |
| 434 |
assert(It != Files.end()); |
| 435 |
return It->second.SpelledTokens; |
| 436 |
} |
| 437 |
|
| 438 |
const syntax::Token *TokenBuffer::spelledTokenAt(SourceLocation Loc) const { |
| 439 |
assert(Loc.isFileID()); |
| 440 |
const auto *Tok = llvm::partition_point( |
| 441 |
spelledTokens(SourceMgr->getFileID(Loc)), |
| 442 |
[&](const syntax::Token &Tok) { return Tok.location() < Loc; }); |
| 443 |
if (!Tok || Tok->location() != Loc) |
| 444 |
return nullptr; |
| 445 |
return Tok; |
| 446 |
} |
| 447 |
|
| 448 |
std::string TokenBuffer::Mapping::str() const { |
| 449 |
return std::string( |
| 450 |
llvm::formatv("spelled tokens: [{0},{1}), expanded tokens: [{2},{3})", |
| 451 |
BeginSpelled, EndSpelled, BeginExpanded, EndExpanded)); |
| 452 |
} |
| 453 |
|
| 454 |
std::optional<llvm::ArrayRef<syntax::Token>> |
| 455 |
TokenBuffer::spelledForExpanded(llvm::ArrayRef<syntax::Token> Expanded) const { |
| 456 |
// Mapping an empty range is ambiguous in case of empty mappings at either end |
| 457 |
// of the range, bail out in that case. |
| 458 |
if (Expanded.empty()) |
| 459 |
return std::nullopt; |
| 460 |
const syntax::Token *First = &Expanded.front(); |
| 461 |
const syntax::Token *Last = &Expanded.back(); |
| 462 |
auto [FirstSpelled, FirstMapping] = spelledForExpandedToken(First); |
| 463 |
auto [LastSpelled, LastMapping] = spelledForExpandedToken(Last); |
| 464 |
|
| 465 |
FileID FID = SourceMgr->getFileID(FirstSpelled->location()); |
| 466 |
// FIXME: Handle multi-file changes by trying to map onto a common root. |
| 467 |
if (FID != SourceMgr->getFileID(LastSpelled->location())) |
| 468 |
return std::nullopt; |
| 469 |
|
| 470 |
const MarkedFile &File = Files.find(FID)->second; |
| 471 |
|
| 472 |
// If the range is within one macro argument, the result may be only part of a |
| 473 |
// Mapping. We must use the general (SourceManager-based) algorithm. |
| 474 |
if (FirstMapping && FirstMapping == LastMapping && |
| 475 |
SourceMgr->isMacroArgExpansion(First->location()) && |
| 476 |
SourceMgr->isMacroArgExpansion(Last->location())) { |
| 477 |
// We use excluded Prev/Next token for bounds checking. |
| 478 |
SourceLocation Prev = (First == &ExpandedTokens.front()) |
| 479 |
? SourceLocation() |
| 480 |
: (First - 1)->location(); |
| 481 |
SourceLocation Next = (Last == &ExpandedTokens.back()) |
| 482 |
? SourceLocation() |
| 483 |
: (Last + 1)->location(); |
| 484 |
SourceRange Range = spelledForExpandedSlow( |
| 485 |
First->location(), Last->location(), Prev, Next, FID, *SourceMgr); |
| 486 |
if (Range.isInvalid()) |
| 487 |
return std::nullopt; |
| 488 |
return getTokensCovering(File.SpelledTokens, Range, *SourceMgr); |
| 489 |
} |
| 490 |
|
| 491 |
// Otherwise, use the fast version based on Mappings. |
| 492 |
// Do not allow changes that doesn't cover full expansion. |
| 493 |
unsigned FirstExpanded = Expanded.begin() - ExpandedTokens.data(); |
| 494 |
unsigned LastExpanded = Expanded.end() - ExpandedTokens.data(); |
| 495 |
if (FirstMapping && FirstExpanded != FirstMapping->BeginExpanded) |
| 496 |
return std::nullopt; |
| 497 |
if (LastMapping && LastMapping->EndExpanded != LastExpanded) |
| 498 |
return std::nullopt; |
| 499 |
return llvm::ArrayRef( |
| 500 |
FirstMapping ? File.SpelledTokens.data() + FirstMapping->BeginSpelled |
| 501 |
: FirstSpelled, |
| 502 |
LastMapping ? File.SpelledTokens.data() + LastMapping->EndSpelled |
| 503 |
: LastSpelled + 1); |
| 504 |
} |
| 505 |
|
| 506 |
TokenBuffer::Expansion TokenBuffer::makeExpansion(const MarkedFile &F, |
| 507 |
const Mapping &M) const { |
| 508 |
Expansion E; |
| 509 |
E.Spelled = llvm::ArrayRef(F.SpelledTokens.data() + M.BeginSpelled, |
| 510 |
F.SpelledTokens.data() + M.EndSpelled); |
| 511 |
E.Expanded = llvm::ArrayRef(ExpandedTokens.data() + M.BeginExpanded, |
| 512 |
ExpandedTokens.data() + M.EndExpanded); |
| 513 |
return E; |
| 514 |
} |
| 515 |
|
| 516 |
const TokenBuffer::MarkedFile & |
| 517 |
TokenBuffer::fileForSpelled(llvm::ArrayRef<syntax::Token> Spelled) const { |
| 518 |
assert(!Spelled.empty()); |
| 519 |
assert(Spelled.front().location().isFileID() && "not a spelled token"); |
| 520 |
auto FileIt = Files.find(SourceMgr->getFileID(Spelled.front().location())); |
| 521 |
assert(FileIt != Files.end() && "file not tracked by token buffer"); |
| 522 |
const auto &File = FileIt->second; |
| 523 |
assert(File.SpelledTokens.data() <= Spelled.data() && |
| 524 |
Spelled.end() <= |
| 525 |
(File.SpelledTokens.data() + File.SpelledTokens.size()) && |
| 526 |
"Tokens not in spelled range"); |
| 527 |
#ifndef NDEBUG |
| 528 |
auto T1 = Spelled.back().location(); |
| 529 |
auto T2 = File.SpelledTokens.back().location(); |
| 530 |
assert(T1 == T2 || sourceManager().isBeforeInTranslationUnit(T1, T2)); |
| 531 |
#endif |
| 532 |
return File; |
| 533 |
} |
| 534 |
|
| 535 |
std::optional<TokenBuffer::Expansion> |
| 536 |
TokenBuffer::expansionStartingAt(const syntax::Token *Spelled) const { |
| 537 |
assert(Spelled); |
| 538 |
const auto &File = fileForSpelled(*Spelled); |
| 539 |
|
| 540 |
unsigned SpelledIndex = Spelled - File.SpelledTokens.data(); |
| 541 |
auto M = llvm::partition_point(File.Mappings, [&](const Mapping &M) { |
| 542 |
return M.BeginSpelled < SpelledIndex; |
| 543 |
}); |
| 544 |
if (M == File.Mappings.end() || M->BeginSpelled != SpelledIndex) |
| 545 |
return std::nullopt; |
| 546 |
return makeExpansion(File, *M); |
| 547 |
} |
| 548 |
|
| 549 |
std::vector<TokenBuffer::Expansion> TokenBuffer::expansionsOverlapping( |
| 550 |
llvm::ArrayRef<syntax::Token> Spelled) const { |
| 551 |
if (Spelled.empty()) |
| 552 |
return {}; |
| 553 |
const auto &File = fileForSpelled(Spelled); |
| 554 |
|
| 555 |
// Find the first overlapping range, and then copy until we stop overlapping. |
| 556 |
unsigned SpelledBeginIndex = Spelled.begin() - File.SpelledTokens.data(); |
| 557 |
unsigned SpelledEndIndex = Spelled.end() - File.SpelledTokens.data(); |
| 558 |
auto M = llvm::partition_point(File.Mappings, [&](const Mapping &M) { |
| 559 |
return M.EndSpelled <= SpelledBeginIndex; |
| 560 |
}); |
| 561 |
std::vector<TokenBuffer::Expansion> Expansions; |
| 562 |
for (; M != File.Mappings.end() && M->BeginSpelled < SpelledEndIndex; ++M) |
| 563 |
Expansions.push_back(makeExpansion(File, *M)); |
| 564 |
return Expansions; |
| 565 |
} |
| 566 |
|
| 567 |
llvm::ArrayRef<syntax::Token> |
| 568 |
syntax::spelledTokensTouching(SourceLocation Loc, |
| 569 |
llvm::ArrayRef<syntax::Token> Tokens) { |
| 570 |
assert(Loc.isFileID()); |
| 571 |
|
| 572 |
auto *Right = llvm::partition_point( |
| 573 |
Tokens, [&](const syntax::Token &Tok) { return Tok.location() < Loc; }); |
| 574 |
bool AcceptRight = Right != Tokens.end() && Right->location() <= Loc; |
| 575 |
bool AcceptLeft = |
| 576 |
Right != Tokens.begin() && (Right - 1)->endLocation() >= Loc; |
| 577 |
return llvm::ArrayRef(Right - (AcceptLeft ? 1 : 0), |
| 578 |
Right + (AcceptRight ? 1 : 0)); |
| 579 |
} |
| 580 |
|
| 581 |
llvm::ArrayRef<syntax::Token> |
| 582 |
syntax::spelledTokensTouching(SourceLocation Loc, |
| 583 |
const syntax::TokenBuffer &Tokens) { |
| 584 |
return spelledTokensTouching( |
| 585 |
Loc, Tokens.spelledTokens(Tokens.sourceManager().getFileID(Loc))); |
| 586 |
} |
| 587 |
|
| 588 |
const syntax::Token * |
| 589 |
syntax::spelledIdentifierTouching(SourceLocation Loc, |
| 590 |
llvm::ArrayRef<syntax::Token> Tokens) { |
| 591 |
for (const syntax::Token &Tok : spelledTokensTouching(Loc, Tokens)) { |
| 592 |
if (Tok.kind() == tok::identifier) |
| 593 |
return &Tok; |
| 594 |
} |
| 595 |
return nullptr; |
| 596 |
} |
| 597 |
|
| 598 |
const syntax::Token * |
| 599 |
syntax::spelledIdentifierTouching(SourceLocation Loc, |
| 600 |
const syntax::TokenBuffer &Tokens) { |
| 601 |
return spelledIdentifierTouching( |
| 602 |
Loc, Tokens.spelledTokens(Tokens.sourceManager().getFileID(Loc))); |
| 603 |
} |
| 604 |
|
| 605 |
std::vector<const syntax::Token *> |
| 606 |
TokenBuffer::macroExpansions(FileID FID) const { |
| 607 |
auto FileIt = Files.find(FID); |
| 608 |
assert(FileIt != Files.end() && "file not tracked by token buffer"); |
| 609 |
auto &File = FileIt->second; |
| 610 |
std::vector<const syntax::Token *> Expansions; |
| 611 |
auto &Spelled = File.SpelledTokens; |
| 612 |
for (auto Mapping : File.Mappings) { |
| 613 |
const syntax::Token *Token = &Spelled[Mapping.BeginSpelled]; |
| 614 |
if (Token->kind() == tok::TokenKind::identifier) |
| 615 |
Expansions.push_back(Token); |
| 616 |
} |
| 617 |
return Expansions; |
| 618 |
} |
| 619 |
|
| 620 |
std::vector<syntax::Token> syntax::tokenize(const FileRange &FR, |
| 621 |
const SourceManager &SM, |
| 622 |
const LangOptions &LO) { |
| 623 |
std::vector<syntax::Token> Tokens; |
| 624 |
IdentifierTable Identifiers(LO); |
| 625 |
auto AddToken = [&](clang::Token T) { |
| 626 |
// Fill the proper token kind for keywords, etc. |
| 627 |
if (T.getKind() == tok::raw_identifier && !T.needsCleaning() && |
| 628 |
!T.hasUCN()) { // FIXME: support needsCleaning and hasUCN cases. |
| 629 |
clang::IdentifierInfo &II = Identifiers.get(T.getRawIdentifier()); |
| 630 |
T.setIdentifierInfo(&II); |
| 631 |
T.setKind(II.getTokenID()); |
| 632 |
} |
| 633 |
Tokens.push_back(syntax::Token(T)); |
| 634 |
}; |
| 635 |
|
| 636 |
auto SrcBuffer = SM.getBufferData(FR.file()); |
| 637 |
Lexer L(SM.getLocForStartOfFile(FR.file()), LO, SrcBuffer.data(), |
| 638 |
SrcBuffer.data() + FR.beginOffset(), |
| 639 |
// We can't make BufEnd point to FR.endOffset, as Lexer requires a |
| 640 |
// null terminated buffer. |
| 641 |
SrcBuffer.data() + SrcBuffer.size()); |
| 642 |
|
| 643 |
clang::Token T; |
| 644 |
while (!L.LexFromRawLexer(T) && L.getCurrentBufferOffset() < FR.endOffset()) |
| 645 |
AddToken(T); |
| 646 |
// LexFromRawLexer returns true when it parses the last token of the file, add |
| 647 |
// it iff it starts within the range we are interested in. |
| 648 |
if (SM.getFileOffset(T.getLocation()) < FR.endOffset()) |
| 649 |
AddToken(T); |
| 650 |
return Tokens; |
| 651 |
} |
| 652 |
|
| 653 |
std::vector<syntax::Token> syntax::tokenize(FileID FID, const SourceManager &SM, |
| 654 |
const LangOptions &LO) { |
| 655 |
return tokenize(syntax::FileRange(FID, 0, SM.getFileIDSize(FID)), SM, LO); |
| 656 |
} |
| 657 |
|
| 658 |
/// Records information reqired to construct mappings for the token buffer that |
| 659 |
/// we are collecting. |
| 660 |
class TokenCollector::CollectPPExpansions : public PPCallbacks { |
| 661 |
public: |
| 662 |
CollectPPExpansions(TokenCollector &C) : Collector(&C) {} |
| 663 |
|
| 664 |
/// Disabled instance will stop reporting anything to TokenCollector. |
| 665 |
/// This ensures that uses of the preprocessor after TokenCollector::consume() |
| 666 |
/// is called do not access the (possibly invalid) collector instance. |
| 667 |
void disable() { Collector = nullptr; } |
| 668 |
|
| 669 |
void MacroExpands(const clang::Token &MacroNameTok, const MacroDefinition &MD, |
| 670 |
SourceRange Range, const MacroArgs *Args) override { |
| 671 |
if (!Collector) |
| 672 |
return; |
| 673 |
const auto &SM = Collector->PP.getSourceManager(); |
| 674 |
// Only record top-level expansions that directly produce expanded tokens. |
| 675 |
// This excludes those where: |
| 676 |
// - the macro use is inside a macro body, |
| 677 |
// - the macro appears in an argument to another macro. |
| 678 |
// However macro expansion isn't really a tree, it's token rewrite rules, |
| 679 |
// so there are other cases, e.g. |
| 680 |
// #define B(X) X |
| 681 |
// #define A 1 + B |
| 682 |
// A(2) |
| 683 |
// Both A and B produce expanded tokens, though the macro name 'B' comes |
| 684 |
// from an expansion. The best we can do is merge the mappings for both. |
| 685 |
|
| 686 |
// The *last* token of any top-level macro expansion must be in a file. |
| 687 |
// (In the example above, see the closing paren of the expansion of B). |
| 688 |
if (!Range.getEnd().isFileID()) |
| 689 |
return; |
| 690 |
// If there's a current expansion that encloses this one, this one can't be |
| 691 |
// top-level. |
| 692 |
if (LastExpansionEnd.isValid() && |
| 693 |
!SM.isBeforeInTranslationUnit(LastExpansionEnd, Range.getEnd())) |
| 694 |
return; |
| 695 |
|
| 696 |
// If the macro invocation (B) starts in a macro (A) but ends in a file, |
| 697 |
// we'll create a merged mapping for A + B by overwriting the endpoint for |
| 698 |
// A's startpoint. |
| 699 |
if (!Range.getBegin().isFileID()) { |
| 700 |
Range.setBegin(SM.getExpansionLoc(Range.getBegin())); |
| 701 |
assert(Collector->Expansions.count(Range.getBegin()) && |
| 702 |
"Overlapping macros should have same expansion location"); |
| 703 |
} |
| 704 |
|
| 705 |
Collector->Expansions[Range.getBegin()] = Range.getEnd(); |
| 706 |
LastExpansionEnd = Range.getEnd(); |
| 707 |
} |
| 708 |
// FIXME: handle directives like #pragma, #include, etc. |
| 709 |
private: |
| 710 |
TokenCollector *Collector; |
| 711 |
/// Used to detect recursive macro expansions. |
| 712 |
SourceLocation LastExpansionEnd; |
| 713 |
}; |
| 714 |
|
| 715 |
/// Fills in the TokenBuffer by tracing the run of a preprocessor. The |
| 716 |
/// implementation tracks the tokens, macro expansions and directives coming |
| 717 |
/// from the preprocessor and: |
| 718 |
/// - for each token, figures out if it is a part of an expanded token stream, |
| 719 |
/// spelled token stream or both. Stores the tokens appropriately. |
| 720 |
/// - records mappings from the spelled to expanded token ranges, e.g. for macro |
| 721 |
/// expansions. |
| 722 |
/// FIXME: also properly record: |
| 723 |
/// - #include directives, |
| 724 |
/// - #pragma, #line and other PP directives, |
| 725 |
/// - skipped pp regions, |
| 726 |
/// - ... |
| 727 |
|
| 728 |
TokenCollector::TokenCollector(Preprocessor &PP) : PP(PP) { |
| 729 |
// Collect the expanded token stream during preprocessing. |
| 730 |
PP.setTokenWatcher([this](const clang::Token &T) { |
| 731 |
if (T.isAnnotation()) |
| 732 |
return; |
| 733 |
DEBUG_WITH_TYPE("collect-tokens", llvm::dbgs() |
| 734 |
<< "Token: " |
| 735 |
<< syntax::Token(T).dumpForTests( |
| 736 |
this->PP.getSourceManager()) |
| 737 |
<< "\n" |
| 738 |
|
| 739 |
); |
| 740 |
Expanded.push_back(syntax::Token(T)); |
| 741 |
}); |
| 742 |
// And locations of macro calls, to properly recover boundaries of those in |
| 743 |
// case of empty expansions. |
| 744 |
auto CB = std::make_unique<CollectPPExpansions>(*this); |
| 745 |
this->Collector = CB.get(); |
| 746 |
PP.addPPCallbacks(std::move(CB)); |
| 747 |
} |
| 748 |
|
| 749 |
/// Builds mappings and spelled tokens in the TokenBuffer based on the expanded |
| 750 |
/// token stream. |
| 751 |
class TokenCollector::Builder { |
| 752 |
public: |
| 753 |
Builder(std::vector<syntax::Token> Expanded, PPExpansions CollectedExpansions, |
| 754 |
const SourceManager &SM, const LangOptions &LangOpts) |
| 755 |
: Result(SM), CollectedExpansions(std::move(CollectedExpansions)), SM(SM), |
| 756 |
LangOpts(LangOpts) { |
| 757 |
Result.ExpandedTokens = std::move(Expanded); |
| 758 |
} |
| 759 |
|
| 760 |
TokenBuffer build() && { |
| 761 |
assert(!Result.ExpandedTokens.empty()); |
| 762 |
assert(Result.ExpandedTokens.back().kind() == tok::eof); |
| 763 |
|
| 764 |
// Tokenize every file that contributed tokens to the expanded stream. |
| 765 |
buildSpelledTokens(); |
| 766 |
|
| 767 |
// The expanded token stream consists of runs of tokens that came from |
| 768 |
// the same source (a macro expansion, part of a file etc). |
| 769 |
// Between these runs are the logical positions of spelled tokens that |
| 770 |
// didn't expand to anything. |
| 771 |
while (NextExpanded < Result.ExpandedTokens.size() - 1 /* eof */) { |
| 772 |
// Create empty mappings for spelled tokens that expanded to nothing here. |
| 773 |
// May advance NextSpelled, but NextExpanded is unchanged. |
| 774 |
discard(); |
| 775 |
// Create mapping for a contiguous run of expanded tokens. |
| 776 |
// Advances NextExpanded past the run, and NextSpelled accordingly. |
| 777 |
unsigned OldPosition = NextExpanded; |
| 778 |
advance(); |
| 779 |
if (NextExpanded == OldPosition) |
| 780 |
diagnoseAdvanceFailure(); |
| 781 |
} |
| 782 |
// If any tokens remain in any of the files, they didn't expand to anything. |
| 783 |
// Create empty mappings up until the end of the file. |
| 784 |
for (const auto &File : Result.Files) |
| 785 |
discard(File.first); |
| 786 |
|
| 787 |
#ifndef NDEBUG |
| 788 |
for (auto &pair : Result.Files) { |
| 789 |
auto &mappings = pair.second.Mappings; |
| 790 |
assert(llvm::is_sorted(mappings, [](const TokenBuffer::Mapping &M1, |
| 791 |
const TokenBuffer::Mapping &M2) { |
| 792 |
return M1.BeginSpelled < M2.BeginSpelled && |
| 793 |
M1.EndSpelled < M2.EndSpelled && |
| 794 |
M1.BeginExpanded < M2.BeginExpanded && |
| 795 |
M1.EndExpanded < M2.EndExpanded; |
| 796 |
})); |
| 797 |
} |
| 798 |
#endif |
| 799 |
|
| 800 |
return std::move(Result); |
| 801 |
} |
| 802 |
|
| 803 |
private: |
| 804 |
// Consume a sequence of spelled tokens that didn't expand to anything. |
| 805 |
// In the simplest case, skips spelled tokens until finding one that produced |
| 806 |
// the NextExpanded token, and creates an empty mapping for them. |
| 807 |
// If Drain is provided, skips remaining tokens from that file instead. |
| 808 |
void discard(std::optional<FileID> Drain = std::nullopt) { |
| 809 |
SourceLocation Target = |
| 810 |
Drain ? SM.getLocForEndOfFile(*Drain) |
| 811 |
: SM.getExpansionLoc( |
| 812 |
Result.ExpandedTokens[NextExpanded].location()); |
| 813 |
FileID File = SM.getFileID(Target); |
| 814 |
const auto &SpelledTokens = Result.Files[File].SpelledTokens; |
| 815 |
auto &NextSpelled = this->NextSpelled[File]; |
| 816 |
|
| 817 |
TokenBuffer::Mapping Mapping; |
| 818 |
Mapping.BeginSpelled = NextSpelled; |
| 819 |
// When dropping trailing tokens from a file, the empty mapping should |
| 820 |
// be positioned within the file's expanded-token range (at the end). |
| 821 |
Mapping.BeginExpanded = Mapping.EndExpanded = |
| 822 |
Drain ? Result.Files[*Drain].EndExpanded : NextExpanded; |
| 823 |
// We may want to split into several adjacent empty mappings. |
| 824 |
// FlushMapping() emits the current mapping and starts a new one. |
| 825 |
auto FlushMapping = [&, this] { |
| 826 |
Mapping.EndSpelled = NextSpelled; |
| 827 |
if (Mapping.BeginSpelled != Mapping.EndSpelled) |
| 828 |
Result.Files[File].Mappings.push_back(Mapping); |
| 829 |
Mapping.BeginSpelled = NextSpelled; |
| 830 |
}; |
| 831 |
|
| 832 |
while (NextSpelled < SpelledTokens.size() && |
| 833 |
SpelledTokens[NextSpelled].location() < Target) { |
| 834 |
// If we know mapping bounds at [NextSpelled, KnownEnd] (macro expansion) |
| 835 |
// then we want to partition our (empty) mapping. |
| 836 |
// [Start, NextSpelled) [NextSpelled, KnownEnd] (KnownEnd, Target) |
| 837 |
SourceLocation KnownEnd = |
| 838 |
CollectedExpansions.lookup(SpelledTokens[NextSpelled].location()); |
| 839 |
if (KnownEnd.isValid()) { |
| 840 |
FlushMapping(); // Emits [Start, NextSpelled) |
| 841 |
while (NextSpelled < SpelledTokens.size() && |
| 842 |
SpelledTokens[NextSpelled].location() <= KnownEnd) |
| 843 |
++NextSpelled; |
| 844 |
FlushMapping(); // Emits [NextSpelled, KnownEnd] |
| 845 |
// Now the loop continues and will emit (KnownEnd, Target). |
| 846 |
} else { |
| 847 |
++NextSpelled; |
| 848 |
} |
| 849 |
} |
| 850 |
FlushMapping(); |
| 851 |
} |
| 852 |
|
| 853 |
// Consumes the NextExpanded token and others that are part of the same run. |
| 854 |
// Increases NextExpanded and NextSpelled by at least one, and adds a mapping |
| 855 |
// (unless this is a run of file tokens, which we represent with no mapping). |
| 856 |
void advance() { |
| 857 |
const syntax::Token &Tok = Result.ExpandedTokens[NextExpanded]; |
| 858 |
SourceLocation Expansion = SM.getExpansionLoc(Tok.location()); |
| 859 |
FileID File = SM.getFileID(Expansion); |
| 860 |
const auto &SpelledTokens = Result.Files[File].SpelledTokens; |
| 861 |
auto &NextSpelled = this->NextSpelled[File]; |
| 862 |
|
| 863 |
if (Tok.location().isFileID()) { |
| 864 |
// A run of file tokens continues while the expanded/spelled tokens match. |
| 865 |
while (NextSpelled < SpelledTokens.size() && |
| 866 |
NextExpanded < Result.ExpandedTokens.size() && |
| 867 |
SpelledTokens[NextSpelled].location() == |
| 868 |
Result.ExpandedTokens[NextExpanded].location()) { |
| 869 |
++NextSpelled; |
| 870 |
++NextExpanded; |
| 871 |
} |
| 872 |
// We need no mapping for file tokens copied to the expanded stream. |
| 873 |
} else { |
| 874 |
// We found a new macro expansion. We should have its spelling bounds. |
| 875 |
auto End = CollectedExpansions.lookup(Expansion); |
| 876 |
assert(End.isValid() && "Macro expansion wasn't captured?"); |
| 877 |
|
| 878 |
// Mapping starts here... |
| 879 |
TokenBuffer::Mapping Mapping; |
| 880 |
Mapping.BeginExpanded = NextExpanded; |
| 881 |
Mapping.BeginSpelled = NextSpelled; |
| 882 |
// ... consumes spelled tokens within bounds we captured ... |
| 883 |
while (NextSpelled < SpelledTokens.size() && |
| 884 |
SpelledTokens[NextSpelled].location() <= End) |
| 885 |
++NextSpelled; |
| 886 |
// ... consumes expanded tokens rooted at the same expansion ... |
| 887 |
while (NextExpanded < Result.ExpandedTokens.size() && |
| 888 |
SM.getExpansionLoc( |
| 889 |
Result.ExpandedTokens[NextExpanded].location()) == Expansion) |
| 890 |
++NextExpanded; |
| 891 |
// ... and ends here. |
| 892 |
Mapping.EndExpanded = NextExpanded; |
| 893 |
Mapping.EndSpelled = NextSpelled; |
| 894 |
Result.Files[File].Mappings.push_back(Mapping); |
| 895 |
} |
| 896 |
} |
| 897 |
|
| 898 |
// advance() is supposed to consume at least one token - if not, we crash. |
| 899 |
void diagnoseAdvanceFailure() { |
| 900 |
#ifndef NDEBUG |
| 901 |
// Show the failed-to-map token in context. |
| 902 |
for (unsigned I = (NextExpanded < 10) ? 0 : NextExpanded - 10; |
| 903 |
I < NextExpanded + 5 && I < Result.ExpandedTokens.size(); ++I) { |
| 904 |
const char *L = |
| 905 |
(I == NextExpanded) ? "!! " : (I < NextExpanded) ? "ok " : " "; |
| 906 |
llvm::errs() << L << Result.ExpandedTokens[I].dumpForTests(SM) << "\n"; |
| 907 |
} |
| 908 |
#endif |
| 909 |
llvm_unreachable("Couldn't map expanded token to spelled tokens!"); |
| 910 |
} |
| 911 |
|
| 912 |
/// Initializes TokenBuffer::Files and fills spelled tokens and expanded |
| 913 |
/// ranges for each of the files. |
| 914 |
void buildSpelledTokens() { |
| 915 |
for (unsigned I = 0; I < Result.ExpandedTokens.size(); ++I) { |
| 916 |
const auto &Tok = Result.ExpandedTokens[I]; |
| 917 |
auto FID = SM.getFileID(SM.getExpansionLoc(Tok.location())); |
| 918 |
auto It = Result.Files.try_emplace(FID); |
| 919 |
TokenBuffer::MarkedFile &File = It.first->second; |
| 920 |
|
| 921 |
// The eof token should not be considered part of the main-file's range. |
| 922 |
File.EndExpanded = Tok.kind() == tok::eof ? I : I + 1; |
| 923 |
|
| 924 |
if (!It.second) |
| 925 |
continue; // we have seen this file before. |
| 926 |
// This is the first time we see this file. |
| 927 |
File.BeginExpanded = I; |
| 928 |
File.SpelledTokens = tokenize(FID, SM, LangOpts); |
| 929 |
} |
| 930 |
} |
| 931 |
|
| 932 |
TokenBuffer Result; |
| 933 |
unsigned NextExpanded = 0; // cursor in ExpandedTokens |
| 934 |
llvm::DenseMap<FileID, unsigned> NextSpelled; // cursor in SpelledTokens |
| 935 |
PPExpansions CollectedExpansions; |
| 936 |
const SourceManager &SM; |
| 937 |
const LangOptions &LangOpts; |
| 938 |
}; |
| 939 |
|
| 940 |
TokenBuffer TokenCollector::consume() && { |
| 941 |
PP.setTokenWatcher(nullptr); |
| 942 |
Collector->disable(); |
| 943 |
return Builder(std::move(Expanded), std::move(Expansions), |
| 944 |
PP.getSourceManager(), PP.getLangOpts()) |
| 945 |
.build(); |
| 946 |
} |
| 947 |
|
| 948 |
std::string syntax::Token::str() const { |
| 949 |
return std::string(llvm::formatv("Token({0}, length = {1})", |
| 950 |
tok::getTokenName(kind()), length())); |
| 951 |
} |
| 952 |
|
| 953 |
std::string syntax::Token::dumpForTests(const SourceManager &SM) const { |
| 954 |
return std::string(llvm::formatv("Token(`{0}`, {1}, length = {2})", text(SM), |
| 955 |
tok::getTokenName(kind()), length())); |
| 956 |
} |
| 957 |
|
| 958 |
std::string TokenBuffer::dumpForTests() const { |
| 959 |
auto PrintToken = [this](const syntax::Token &T) -> std::string { |
| 960 |
if (T.kind() == tok::eof) |
| 961 |
return "<eof>"; |
| 962 |
return std::string(T.text(*SourceMgr)); |
| 963 |
}; |
| 964 |
|
| 965 |
auto DumpTokens = [this, &PrintToken](llvm::raw_ostream &OS, |
| 966 |
llvm::ArrayRef<syntax::Token> Tokens) { |
| 967 |
if (Tokens.empty()) { |
| 968 |
OS << "<empty>"; |
| 969 |
return; |
| 970 |
} |
| 971 |
OS << Tokens[0].text(*SourceMgr); |
| 972 |
for (unsigned I = 1; I < Tokens.size(); ++I) { |
| 973 |
if (Tokens[I].kind() == tok::eof) |
| 974 |
continue; |
| 975 |
OS << " " << PrintToken(Tokens[I]); |
| 976 |
} |
| 977 |
}; |
| 978 |
|
| 979 |
std::string Dump; |
| 980 |
llvm::raw_string_ostream OS(Dump); |
| 981 |
|
| 982 |
OS << "expanded tokens:\n" |
| 983 |
<< " "; |
| 984 |
// (!) we do not show '<eof>'. |
| 985 |
DumpTokens(OS, llvm::ArrayRef(ExpandedTokens).drop_back()); |
| 986 |
OS << "\n"; |
| 987 |
|
| 988 |
std::vector<FileID> Keys; |
| 989 |
for (auto F : Files) |
| 990 |
Keys.push_back(F.first); |
| 991 |
llvm::sort(Keys); |
| 992 |
|
| 993 |
for (FileID ID : Keys) { |
| 994 |
const MarkedFile &File = Files.find(ID)->second; |
| 995 |
auto *Entry = SourceMgr->getFileEntryForID(ID); |
| 996 |
if (!Entry) |
| 997 |
continue; // Skip builtin files. |
| 998 |
OS << llvm::formatv("file '{0}'\n", Entry->getName()) |
| 999 |
<< " spelled tokens:\n" |
| 1000 |
<< " "; |
| 1001 |
DumpTokens(OS, File.SpelledTokens); |
| 1002 |
OS << "\n"; |
| 1003 |
|
| 1004 |
if (File.Mappings.empty()) { |
| 1005 |
OS << " no mappings.\n"; |
| 1006 |
continue; |
| 1007 |
} |
| 1008 |
OS << " mappings:\n"; |
| 1009 |
for (auto &M : File.Mappings) { |
| 1010 |
OS << llvm::formatv( |
| 1011 |
" ['{0}'_{1}, '{2}'_{3}) => ['{4}'_{5}, '{6}'_{7})\n", |
| 1012 |
PrintToken(File.SpelledTokens[M.BeginSpelled]), M.BeginSpelled, |
| 1013 |
M.EndSpelled == File.SpelledTokens.size() |
| 1014 |
? "<eof>" |
| 1015 |
: PrintToken(File.SpelledTokens[M.EndSpelled]), |
| 1016 |
M.EndSpelled, PrintToken(ExpandedTokens[M.BeginExpanded]), |
| 1017 |
M.BeginExpanded, PrintToken(ExpandedTokens[M.EndExpanded]), |
| 1018 |
M.EndExpanded); |
| 1019 |
} |
| 1020 |
} |
| 1021 |
return Dump; |
| 1022 |
} |