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"
35 using namespace clang;
69 auto FirstLoc =
First.location(), LastLoc =
Last.location();
72 while (!FirstLoc.isFileID() && !LastLoc.isFileID()) {
73 auto ExpInfoFirst =
SM.getSLocEntry(
SM.getFileID(FirstLoc)).getExpansion();
74 auto ExpInfoLast =
SM.getSLocEntry(
SM.getFileID(LastLoc)).getExpansion();
76 if (ExpInfoFirst.getExpansionLocStart() !=
77 ExpInfoLast.getExpansionLocStart())
80 if (!ExpInfoFirst.isMacroArgExpansion() ||
81 !ExpInfoLast.isMacroArgExpansion())
83 FirstLoc =
SM.getImmediateSpellingLoc(FirstLoc);
84 LastLoc =
SM.getImmediateSpellingLoc(LastLoc);
87 Res = {FirstLoc, LastLoc};
103 : Location(Location), Length(Length),
Kind(
Kind) {
113 bool Invalid =
false;
114 const char *Start =
SM.getCharacterData(location(), &Invalid);
116 return llvm::StringRef(Start,
length());
120 assert(location().isFileID() &&
"must be a spelled token");
122 unsigned StartOffset;
123 std::tie(
File, StartOffset) =
SM.getDecomposedLoc(location());
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());
139 return OS << T.
str();
144 assert(
File.isValid());
145 assert(BeginOffset <= EndOffset);
153 std::tie(File,
Begin) =
SM.getDecomposedLoc(BeginLoc);
154 End =
Begin + Length;
162 assert(
SM.getFileID(BeginLoc) ==
SM.getFileID(EndLoc));
163 assert(
SM.getFileOffset(BeginLoc) <=
SM.getFileOffset(EndLoc));
165 std::tie(File,
Begin) =
SM.getDecomposedLoc(BeginLoc);
166 End =
SM.getFileOffset(EndLoc);
171 return OS << llvm::formatv(
"FileRange(file = {0}, offsets = {1}-{2})",
177 bool Invalid =
false;
178 StringRef
Text =
SM.getBufferData(File, &Invalid);
182 assert(End <=
Text.size());
188 if (!ExpandedTokIndex.empty())
190 ExpandedTokIndex.reserve(ExpandedTokens.size());
192 for (
size_t I = 0, E = ExpandedTokens.size(); I != E; ++I) {
195 ExpandedTokIndex[Loc] = I;
202 if (!ExpandedTokIndex.empty()) {
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();
211 const Token *R = ExpandedTokens.data() + E->getSecond() + 1;
228 std::pair<const syntax::Token *, const TokenBuffer::Mapping *>
229 TokenBuffer::spelledForExpandedToken(
const syntax::Token *Expanded)
const {
231 assert(ExpandedTokens.data() <= Expanded &&
232 Expanded < ExpandedTokens.data() + ExpandedTokens.size());
234 auto FileIt = Files.find(
236 assert(FileIt != Files.end() &&
"no file for an expanded token");
238 const MarkedFile &
File = FileIt->second;
240 unsigned ExpandedIndex = Expanded - ExpandedTokens.data();
242 auto It = llvm::partition_point(
File.Mappings, [&](
const Mapping &M) {
243 return M.BeginExpanded <= ExpandedIndex;
246 if (It ==
File.Mappings.begin()) {
248 return {&
File.SpelledTokens[ExpandedIndex -
File.BeginExpanded],
254 if (ExpandedIndex < It->EndExpanded)
255 return {&
File.SpelledTokens[It->BeginSpelled], &*It};
260 &
File.SpelledTokens[It->EndSpelled + (ExpandedIndex - It->EndExpanded)],
264 const TokenBuffer::Mapping *
265 TokenBuffer::mappingStartingBeforeSpelled(
const MarkedFile &F,
267 assert(F.SpelledTokens.data() <= Spelled);
268 unsigned SpelledI = Spelled - F.SpelledTokens.data();
269 assert(SpelledI < F.SpelledTokens.size());
271 auto It = llvm::partition_point(F.Mappings, [SpelledI](
const Mapping &M) {
272 return M.BeginSpelled <= SpelledI;
274 if (It == F.Mappings.begin())
284 const auto &
File = fileForSpelled(Spelled);
286 auto *FrontMapping = mappingStartingBeforeSpelled(
File, &Spelled.front());
287 unsigned SpelledFrontI = &Spelled.front() -
File.SpelledTokens.data();
288 assert(SpelledFrontI <
File.SpelledTokens.size());
289 unsigned ExpandedBegin;
293 ExpandedBegin =
File.BeginExpanded + SpelledFrontI;
294 }
else if (SpelledFrontI < FrontMapping->EndSpelled) {
296 if (SpelledFrontI != FrontMapping->BeginSpelled) {
301 ExpandedBegin = FrontMapping->BeginExpanded;
306 FrontMapping->EndExpanded + (SpelledFrontI - FrontMapping->EndSpelled);
309 auto *BackMapping = mappingStartingBeforeSpelled(
File, &Spelled.back());
310 unsigned SpelledBackI = &Spelled.back() -
File.SpelledTokens.data();
311 unsigned ExpandedEnd;
315 ExpandedEnd =
File.BeginExpanded + SpelledBackI + 1;
316 }
else if (SpelledBackI < BackMapping->EndSpelled) {
318 if (SpelledBackI + 1 != BackMapping->EndSpelled) {
322 ExpandedEnd = BackMapping->EndExpanded;
326 BackMapping->EndExpanded + (SpelledBackI - BackMapping->EndSpelled) + 1;
329 assert(ExpandedBegin < ExpandedTokens.size());
330 assert(ExpandedEnd < ExpandedTokens.size());
332 if (ExpandedBegin == ExpandedEnd)
334 return {llvm::makeArrayRef(ExpandedTokens.data() + ExpandedBegin,
335 ExpandedTokens.data() + ExpandedEnd)};
339 auto It = Files.find(FID);
340 assert(It != Files.end());
341 return It->second.SpelledTokens;
346 const auto *Tok = llvm::partition_point(
348 [&](
const syntax::Token &Tok) { return Tok.location() < Loc; });
356 llvm::formatv(
"spelled tokens: [{0},{1}), expanded tokens: [{2},{3})",
357 BeginSpelled, EndSpelled, BeginExpanded, EndExpanded));
364 if (Expanded.empty())
368 const Mapping *BeginMapping;
369 std::tie(BeginSpelled, BeginMapping) =
370 spelledForExpandedToken(&Expanded.front());
373 const Mapping *LastMapping;
374 std::tie(LastSpelled, LastMapping) =
375 spelledForExpandedToken(&Expanded.back());
382 const MarkedFile &
File = Files.find(FID)->second;
388 if (BeginMapping && LastMapping &&
391 auto CommonRange = findCommonRangeForMacroArgs(Expanded.front(),
392 Expanded.back(), *SourceMgr);
396 if (CommonRange.isValid())
397 return getTokensCovering(
File.SpelledTokens, CommonRange, *SourceMgr);
401 unsigned BeginExpanded = Expanded.begin() - ExpandedTokens.data();
402 unsigned EndExpanded = Expanded.end() - ExpandedTokens.data();
403 if (BeginMapping && BeginExpanded != BeginMapping->BeginExpanded)
405 if (LastMapping && LastMapping->EndExpanded != EndExpanded)
408 return llvm::makeArrayRef(
409 BeginMapping ?
File.SpelledTokens.data() + BeginMapping->BeginSpelled
411 LastMapping ?
File.SpelledTokens.data() + LastMapping->EndSpelled
416 const Mapping &M)
const {
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);
425 const TokenBuffer::MarkedFile &
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() &&
434 (
File.SpelledTokens.data() +
File.SpelledTokens.size()) &&
435 "Tokens not in spelled range");
437 auto T1 = Spelled.back().location();
438 auto T2 =
File.SpelledTokens.back().location();
439 assert(T1 == T2 ||
sourceManager().isBeforeInTranslationUnit(T1, T2));
447 const auto &
File = fileForSpelled(*Spelled);
449 unsigned SpelledIndex = Spelled -
File.SpelledTokens.data();
450 auto M = llvm::partition_point(
File.Mappings, [&](
const Mapping &M) {
451 return M.BeginSpelled < SpelledIndex;
453 if (M ==
File.Mappings.end() || M->BeginSpelled != SpelledIndex)
455 return makeExpansion(
File, *M);
462 const auto &
File = fileForSpelled(Spelled);
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;
470 std::vector<TokenBuffer::Expansion> Expansions;
471 for (; M !=
File.Mappings.end() && M->BeginSpelled < SpelledEndIndex; ++M)
472 Expansions.push_back(makeExpansion(
File, *M));
481 auto *Right = llvm::partition_point(
483 bool AcceptRight = Right != Tokens.end() && Right->location() <= Loc;
485 Right != Tokens.begin() && (Right - 1)->endLocation() >= Loc;
486 return llvm::makeArrayRef(Right - (AcceptLeft ? 1 : 0),
487 Right + (AcceptRight ? 1 : 0));
494 Loc, Tokens.spelledTokens(Tokens.sourceManager().getFileID(Loc)));
501 if (Tok.kind() == tok::identifier)
511 Loc, Tokens.spelledTokens(Tokens.sourceManager().getFileID(Loc)));
514 std::vector<const syntax::Token *>
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) {
523 if (
Token->
kind() == tok::TokenKind::identifier)
524 Expansions.push_back(
Token);
532 std::vector<syntax::Token> Tokens;
536 if (T.getKind() == tok::raw_identifier && !T.needsCleaning() &&
539 T.setIdentifierInfo(&II);
545 auto SrcBuffer =
SM.getBufferData(FR.
file());
546 Lexer L(
SM.getLocForStartOfFile(FR.
file()), LO, SrcBuffer.data(),
550 SrcBuffer.data() + SrcBuffer.size());
582 const auto &
SM = Collector->PP.getSourceManager();
597 if (!Range.getEnd().isFileID())
601 if (LastExpansionEnd.isValid() &&
602 !
SM.isBeforeInTranslationUnit(LastExpansionEnd, Range.getEnd()))
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");
614 Collector->Expansions[Range.getBegin()] = Range.getEnd();
615 LastExpansionEnd = Range.getEnd();
642 DEBUG_WITH_TYPE(
"collect-tokens", llvm::dbgs()
653 auto CB = std::make_unique<CollectPPExpansions>(*
this);
654 this->Collector = CB.get();
662 Builder(std::vector<syntax::Token> Expanded, PPExpansions CollectedExpansions,
664 : Result(
SM), CollectedExpansions(
std::move(CollectedExpansions)),
SM(
SM),
666 Result.ExpandedTokens = std::move(Expanded);
670 assert(!Result.ExpandedTokens.empty());
671 assert(Result.ExpandedTokens.back().kind() ==
tok::eof);
674 buildSpelledTokens();
680 while (NextExpanded < Result.ExpandedTokens.size() - 1 ) {
686 unsigned OldPosition = NextExpanded;
688 if (NextExpanded == OldPosition)
689 diagnoseAdvanceFailure();
693 for (
const auto &
File : Result.Files)
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;
709 return std::move(Result);
719 Drain ?
SM.getLocForEndOfFile(*Drain)
720 :
SM.getExpansionLoc(
721 Result.ExpandedTokens[NextExpanded].location());
723 const auto &SpelledTokens = Result.Files[
File].SpelledTokens;
724 auto &NextSpelled = this->NextSpelled[
File];
726 TokenBuffer::Mapping Mapping;
727 Mapping.BeginSpelled = NextSpelled;
730 Mapping.BeginExpanded = Mapping.EndExpanded =
731 Drain ? Result.Files[*Drain].EndExpanded : NextExpanded;
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;
741 while (NextSpelled < SpelledTokens.size() &&
742 SpelledTokens[NextSpelled].location() < Target) {
747 CollectedExpansions.lookup(SpelledTokens[NextSpelled].location());
750 while (NextSpelled < SpelledTokens.size() &&
751 SpelledTokens[NextSpelled].location() <= KnownEnd)
766 const syntax::Token &Tok = Result.ExpandedTokens[NextExpanded];
769 const auto &SpelledTokens = Result.Files[
File].SpelledTokens;
770 auto &NextSpelled = this->NextSpelled[
File];
774 while (NextSpelled < SpelledTokens.size() &&
775 NextExpanded < Result.ExpandedTokens.size() &&
776 SpelledTokens[NextSpelled].location() ==
777 Result.ExpandedTokens[NextExpanded].location()) {
784 auto End = CollectedExpansions.lookup(Expansion);
785 assert(
End.
isValid() &&
"Macro expansion wasn't captured?");
788 TokenBuffer::Mapping Mapping;
789 Mapping.BeginExpanded = NextExpanded;
790 Mapping.BeginSpelled = NextSpelled;
792 while (NextSpelled < SpelledTokens.size() &&
793 SpelledTokens[NextSpelled].location() <=
End)
796 while (NextExpanded < Result.ExpandedTokens.size() &&
798 Result.ExpandedTokens[NextExpanded].location()) == Expansion)
801 Mapping.EndExpanded = NextExpanded;
802 Mapping.EndSpelled = NextSpelled;
803 Result.Files[
File].Mappings.push_back(Mapping);
808 void diagnoseAdvanceFailure() {
811 for (
unsigned I = (NextExpanded < 10) ? 0 : NextExpanded - 10;
812 I < NextExpanded + 5 && I < Result.ExpandedTokens.size(); ++I) {
814 (I == NextExpanded) ?
"!! " : (I < NextExpanded) ?
"ok " :
" ";
815 llvm::errs() << L << Result.ExpandedTokens[I].dumpForTests(
SM) <<
"\n";
818 llvm_unreachable(
"Couldn't map expanded token to spelled tokens!");
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;
836 File.BeginExpanded = I;
842 unsigned NextExpanded = 0;
843 llvm::DenseMap<FileID, unsigned> NextSpelled;
844 PPExpansions CollectedExpansions;
850 PP.setTokenWatcher(
nullptr);
851 Collector->disable();
852 return Builder(std::move(Expanded), std::move(Expansions),
853 PP.getSourceManager(), PP.getLangOpts())
858 return std::string(llvm::formatv(
"Token({0}, length = {1})",
874 auto DumpTokens = [
this, &PrintToken](llvm::raw_ostream &OS,
876 if (Tokens.empty()) {
880 OS << Tokens[0].text(*SourceMgr);
881 for (
unsigned I = 1; I < Tokens.size(); ++I) {
884 OS <<
" " << PrintToken(Tokens[I]);
889 llvm::raw_string_ostream OS(Dump);
891 OS <<
"expanded tokens:\n"
894 DumpTokens(OS, llvm::makeArrayRef(ExpandedTokens).drop_back());
897 std::vector<FileID> Keys;
899 Keys.push_back(F.first);
903 const MarkedFile &
File = Files.find(
ID)->second;
907 OS << llvm::formatv(
"file '{0}'\n", Entry->getName())
908 <<
" spelled tokens:\n"
913 if (
File.Mappings.empty()) {
914 OS <<
" no mappings.\n";
917 OS <<
" mappings:\n";
918 for (
auto &M :
File.Mappings) {
920 " ['{0}'_{1}, '{2}'_{3}) => ['{4}'_{5}, '{6}'_{7})\n",
921 PrintToken(
File.SpelledTokens[M.BeginSpelled]), M.BeginSpelled,
922 M.EndSpelled ==
File.SpelledTokens.size()
924 : PrintToken(
File.SpelledTokens[M.EndSpelled]),
925 M.EndSpelled, PrintToken(ExpandedTokens[M.BeginExpanded]),
926 M.BeginExpanded, PrintToken(ExpandedTokens[M.EndExpanded]),