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