Tokens.cpp revision 351280 
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
35using namespace clang;
36using namespace clang::syntax;
37
38syntax::Token::Token(SourceLocation Location, unsigned Length,
39                     tok::TokenKind Kind)
40    : Location(Location), Length(Length), Kind(Kind) {
41  assert(Location.isValid());
42}
43
44syntax::Token::Token(const clang::Token &T)
45    : Token(T.getLocation(), T.getLength(), T.getKind()) {
46  assert(!T.isAnnotation());
47}
48
49llvm::StringRef syntax::Token::text(const SourceManager &SM) const {
50  bool Invalid = false;
51  const char *Start = SM.getCharacterData(location(), &Invalid);
52  assert(!Invalid);
53  return llvm::StringRef(Start, length());
54}
55
56FileRange syntax::Token::range(const SourceManager &SM) const {
57  assert(location().isFileID() && "must be a spelled token");
58  FileID File;
59  unsigned StartOffset;
60  std::tie(File, StartOffset) = SM.getDecomposedLoc(location());
61  return FileRange(File, StartOffset, StartOffset + length());
62}
63
64FileRange syntax::Token::range(const SourceManager &SM,
65                               const syntax::Token &First,
66                               const syntax::Token &Last) {
67  auto F = First.range(SM);
68  auto L = Last.range(SM);
69  assert(F.file() == L.file() && "tokens from different files");
70  assert(F.endOffset() <= L.beginOffset() && "wrong order of tokens");
71  return FileRange(F.file(), F.beginOffset(), L.endOffset());
72}
73
74llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, const Token &T) {
75  return OS << T.str();
76}
77
78FileRange::FileRange(FileID File, unsigned BeginOffset, unsigned EndOffset)
79    : File(File), Begin(BeginOffset), End(EndOffset) {
80  assert(File.isValid());
81  assert(BeginOffset <= EndOffset);
82}
83
84FileRange::FileRange(const SourceManager &SM, SourceLocation BeginLoc,
85                     unsigned Length) {
86  assert(BeginLoc.isValid());
87  assert(BeginLoc.isFileID());
88
89  std::tie(File, Begin) = SM.getDecomposedLoc(BeginLoc);
90  End = Begin + Length;
91}
92FileRange::FileRange(const SourceManager &SM, SourceLocation BeginLoc,
93                     SourceLocation EndLoc) {
94  assert(BeginLoc.isValid());
95  assert(BeginLoc.isFileID());
96  assert(EndLoc.isValid());
97  assert(EndLoc.isFileID());
98  assert(SM.getFileID(BeginLoc) == SM.getFileID(EndLoc));
99  assert(SM.getFileOffset(BeginLoc) <= SM.getFileOffset(EndLoc));
100
101  std::tie(File, Begin) = SM.getDecomposedLoc(BeginLoc);
102  End = SM.getFileOffset(EndLoc);
103}
104
105llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS,
106                                      const FileRange &R) {
107  return OS << llvm::formatv("FileRange(file = {0}, offsets = {1}-{2})",
108                             R.file().getHashValue(), R.beginOffset(),
109                             R.endOffset());
110}
111
112llvm::StringRef FileRange::text(const SourceManager &SM) const {
113  bool Invalid = false;
114  StringRef Text = SM.getBufferData(File, &Invalid);
115  if (Invalid)
116    return "";
117  assert(Begin <= Text.size());
118  assert(End <= Text.size());
119  return Text.substr(Begin, length());
120}
121
122std::pair<const syntax::Token *, const TokenBuffer::Mapping *>
123TokenBuffer::spelledForExpandedToken(const syntax::Token *Expanded) const {
124  assert(Expanded);
125  assert(ExpandedTokens.data() <= Expanded &&
126         Expanded < ExpandedTokens.data() + ExpandedTokens.size());
127
128  auto FileIt = Files.find(
129      SourceMgr->getFileID(SourceMgr->getExpansionLoc(Expanded->location())));
130  assert(FileIt != Files.end() && "no file for an expanded token");
131
132  const MarkedFile &File = FileIt->second;
133
134  unsigned ExpandedIndex = Expanded - ExpandedTokens.data();
135  // Find the first mapping that produced tokens after \p Expanded.
136  auto It = llvm::partition_point(File.Mappings, [&](const Mapping &M) {
137    return M.BeginExpanded <= ExpandedIndex;
138  });
139  // Our token could only be produced by the previous mapping.
140  if (It == File.Mappings.begin()) {
141    // No previous mapping, no need to modify offsets.
142    return {&File.SpelledTokens[ExpandedIndex - File.BeginExpanded], nullptr};
143  }
144  --It; // 'It' now points to last mapping that started before our token.
145
146  // Check if the token is part of the mapping.
147  if (ExpandedIndex < It->EndExpanded)
148    return {&File.SpelledTokens[It->BeginSpelled], /*Mapping*/ &*It};
149
150  // Not part of the mapping, use the index from previous mapping to compute the
151  // corresponding spelled token.
152  return {
153      &File.SpelledTokens[It->EndSpelled + (ExpandedIndex - It->EndExpanded)],
154      /*Mapping*/ nullptr};
155}
156
157llvm::ArrayRef<syntax::Token> TokenBuffer::spelledTokens(FileID FID) const {
158  auto It = Files.find(FID);
159  assert(It != Files.end());
160  return It->second.SpelledTokens;
161}
162
163std::string TokenBuffer::Mapping::str() const {
164  return llvm::formatv("spelled tokens: [{0},{1}), expanded tokens: [{2},{3})",
165                       BeginSpelled, EndSpelled, BeginExpanded, EndExpanded);
166}
167
168llvm::Optional<llvm::ArrayRef<syntax::Token>>
169TokenBuffer::spelledForExpanded(llvm::ArrayRef<syntax::Token> Expanded) const {
170  // Mapping an empty range is ambiguous in case of empty mappings at either end
171  // of the range, bail out in that case.
172  if (Expanded.empty())
173    return llvm::None;
174
175  // FIXME: also allow changes uniquely mapping to macro arguments.
176
177  const syntax::Token *BeginSpelled;
178  const Mapping *BeginMapping;
179  std::tie(BeginSpelled, BeginMapping) =
180      spelledForExpandedToken(&Expanded.front());
181
182  const syntax::Token *LastSpelled;
183  const Mapping *LastMapping;
184  std::tie(LastSpelled, LastMapping) =
185      spelledForExpandedToken(&Expanded.back());
186
187  FileID FID = SourceMgr->getFileID(BeginSpelled->location());
188  // FIXME: Handle multi-file changes by trying to map onto a common root.
189  if (FID != SourceMgr->getFileID(LastSpelled->location()))
190    return llvm::None;
191
192  const MarkedFile &File = Files.find(FID)->second;
193
194  // Do not allow changes that cross macro expansion boundaries.
195  unsigned BeginExpanded = Expanded.begin() - ExpandedTokens.data();
196  unsigned EndExpanded = Expanded.end() - ExpandedTokens.data();
197  if (BeginMapping && BeginMapping->BeginExpanded < BeginExpanded)
198    return llvm::None;
199  if (LastMapping && EndExpanded < LastMapping->EndExpanded)
200    return llvm::None;
201  // All is good, return the result.
202  return llvm::makeArrayRef(
203      BeginMapping ? File.SpelledTokens.data() + BeginMapping->BeginSpelled
204                   : BeginSpelled,
205      LastMapping ? File.SpelledTokens.data() + LastMapping->EndSpelled
206                  : LastSpelled + 1);
207}
208
209llvm::Optional<TokenBuffer::Expansion>
210TokenBuffer::expansionStartingAt(const syntax::Token *Spelled) const {
211  assert(Spelled);
212  assert(Spelled->location().isFileID() && "not a spelled token");
213  auto FileIt = Files.find(SourceMgr->getFileID(Spelled->location()));
214  assert(FileIt != Files.end() && "file not tracked by token buffer");
215
216  auto &File = FileIt->second;
217  assert(File.SpelledTokens.data() <= Spelled &&
218         Spelled < (File.SpelledTokens.data() + File.SpelledTokens.size()));
219
220  unsigned SpelledIndex = Spelled - File.SpelledTokens.data();
221  auto M = llvm::partition_point(File.Mappings, [&](const Mapping &M) {
222    return M.BeginSpelled < SpelledIndex;
223  });
224  if (M == File.Mappings.end() || M->BeginSpelled != SpelledIndex)
225    return llvm::None;
226
227  Expansion E;
228  E.Spelled = llvm::makeArrayRef(File.SpelledTokens.data() + M->BeginSpelled,
229                                 File.SpelledTokens.data() + M->EndSpelled);
230  E.Expanded = llvm::makeArrayRef(ExpandedTokens.data() + M->BeginExpanded,
231                                  ExpandedTokens.data() + M->EndExpanded);
232  return E;
233}
234
235std::vector<syntax::Token> syntax::tokenize(FileID FID, const SourceManager &SM,
236                                            const LangOptions &LO) {
237  std::vector<syntax::Token> Tokens;
238  IdentifierTable Identifiers(LO);
239  auto AddToken = [&](clang::Token T) {
240    // Fill the proper token kind for keywords, etc.
241    if (T.getKind() == tok::raw_identifier && !T.needsCleaning() &&
242        !T.hasUCN()) { // FIXME: support needsCleaning and hasUCN cases.
243      clang::IdentifierInfo &II = Identifiers.get(T.getRawIdentifier());
244      T.setIdentifierInfo(&II);
245      T.setKind(II.getTokenID());
246    }
247    Tokens.push_back(syntax::Token(T));
248  };
249
250  Lexer L(FID, SM.getBuffer(FID), SM, LO);
251
252  clang::Token T;
253  while (!L.LexFromRawLexer(T))
254    AddToken(T);
255  // 'eof' is only the last token if the input is null-terminated. Never store
256  // it, for consistency.
257  if (T.getKind() != tok::eof)
258    AddToken(T);
259  return Tokens;
260}
261
262/// Records information reqired to construct mappings for the token buffer that
263/// we are collecting.
264class TokenCollector::CollectPPExpansions : public PPCallbacks {
265public:
266  CollectPPExpansions(TokenCollector &C) : Collector(&C) {}
267
268  /// Disabled instance will stop reporting anything to TokenCollector.
269  /// This ensures that uses of the preprocessor after TokenCollector::consume()
270  /// is called do not access the (possibly invalid) collector instance.
271  void disable() { Collector = nullptr; }
272
273  void MacroExpands(const clang::Token &MacroNameTok, const MacroDefinition &MD,
274                    SourceRange Range, const MacroArgs *Args) override {
275    if (!Collector)
276      return;
277    // Only record top-level expansions, not those where:
278    //   - the macro use is inside a macro body,
279    //   - the macro appears in an argument to another macro.
280    if (!MacroNameTok.getLocation().isFileID() ||
281        (LastExpansionEnd.isValid() &&
282         Collector->PP.getSourceManager().isBeforeInTranslationUnit(
283             Range.getBegin(), LastExpansionEnd)))
284      return;
285    Collector->Expansions[Range.getBegin().getRawEncoding()] = Range.getEnd();
286    LastExpansionEnd = Range.getEnd();
287  }
288  // FIXME: handle directives like #pragma, #include, etc.
289private:
290  TokenCollector *Collector;
291  /// Used to detect recursive macro expansions.
292  SourceLocation LastExpansionEnd;
293};
294
295/// Fills in the TokenBuffer by tracing the run of a preprocessor. The
296/// implementation tracks the tokens, macro expansions and directives coming
297/// from the preprocessor and:
298/// - for each token, figures out if it is a part of an expanded token stream,
299///   spelled token stream or both. Stores the tokens appropriately.
300/// - records mappings from the spelled to expanded token ranges, e.g. for macro
301///   expansions.
302/// FIXME: also properly record:
303///          - #include directives,
304///          - #pragma, #line and other PP directives,
305///          - skipped pp regions,
306///          - ...
307
308TokenCollector::TokenCollector(Preprocessor &PP) : PP(PP) {
309  // Collect the expanded token stream during preprocessing.
310  PP.setTokenWatcher([this](const clang::Token &T) {
311    if (T.isAnnotation())
312      return;
313    DEBUG_WITH_TYPE("collect-tokens", llvm::dbgs()
314                                          << "Token: "
315                                          << syntax::Token(T).dumpForTests(
316                                                 this->PP.getSourceManager())
317                                          << "\n"
318
319    );
320    Expanded.push_back(syntax::Token(T));
321  });
322  // And locations of macro calls, to properly recover boundaries of those in
323  // case of empty expansions.
324  auto CB = llvm::make_unique<CollectPPExpansions>(*this);
325  this->Collector = CB.get();
326  PP.addPPCallbacks(std::move(CB));
327}
328
329/// Builds mappings and spelled tokens in the TokenBuffer based on the expanded
330/// token stream.
331class TokenCollector::Builder {
332public:
333  Builder(std::vector<syntax::Token> Expanded, PPExpansions CollectedExpansions,
334          const SourceManager &SM, const LangOptions &LangOpts)
335      : Result(SM), CollectedExpansions(std::move(CollectedExpansions)), SM(SM),
336        LangOpts(LangOpts) {
337    Result.ExpandedTokens = std::move(Expanded);
338  }
339
340  TokenBuffer build() && {
341    buildSpelledTokens();
342
343    // Walk over expanded tokens and spelled tokens in parallel, building the
344    // mappings between those using source locations.
345    // To correctly recover empty macro expansions, we also take locations
346    // reported to PPCallbacks::MacroExpands into account as we do not have any
347    // expanded tokens with source locations to guide us.
348
349    // The 'eof' token is special, it is not part of spelled token stream. We
350    // handle it separately at the end.
351    assert(!Result.ExpandedTokens.empty());
352    assert(Result.ExpandedTokens.back().kind() == tok::eof);
353    for (unsigned I = 0; I < Result.ExpandedTokens.size() - 1; ++I) {
354      // (!) I might be updated by the following call.
355      processExpandedToken(I);
356    }
357
358    // 'eof' not handled in the loop, do it here.
359    assert(SM.getMainFileID() ==
360           SM.getFileID(Result.ExpandedTokens.back().location()));
361    fillGapUntil(Result.Files[SM.getMainFileID()],
362                 Result.ExpandedTokens.back().location(),
363                 Result.ExpandedTokens.size() - 1);
364    Result.Files[SM.getMainFileID()].EndExpanded = Result.ExpandedTokens.size();
365
366    // Some files might have unaccounted spelled tokens at the end, add an empty
367    // mapping for those as they did not have expanded counterparts.
368    fillGapsAtEndOfFiles();
369
370    return std::move(Result);
371  }
372
373private:
374  /// Process the next token in an expanded stream and move corresponding
375  /// spelled tokens, record any mapping if needed.
376  /// (!) \p I will be updated if this had to skip tokens, e.g. for macros.
377  void processExpandedToken(unsigned &I) {
378    auto L = Result.ExpandedTokens[I].location();
379    if (L.isMacroID()) {
380      processMacroExpansion(SM.getExpansionRange(L), I);
381      return;
382    }
383    if (L.isFileID()) {
384      auto FID = SM.getFileID(L);
385      TokenBuffer::MarkedFile &File = Result.Files[FID];
386
387      fillGapUntil(File, L, I);
388
389      // Skip the token.
390      assert(File.SpelledTokens[NextSpelled[FID]].location() == L &&
391             "no corresponding token in the spelled stream");
392      ++NextSpelled[FID];
393      return;
394    }
395  }
396
397  /// Skipped expanded and spelled tokens of a macro expansion that covers \p
398  /// SpelledRange. Add a corresponding mapping.
399  /// (!) \p I will be the index of the last token in an expansion after this
400  /// function returns.
401  void processMacroExpansion(CharSourceRange SpelledRange, unsigned &I) {
402    auto FID = SM.getFileID(SpelledRange.getBegin());
403    assert(FID == SM.getFileID(SpelledRange.getEnd()));
404    TokenBuffer::MarkedFile &File = Result.Files[FID];
405
406    fillGapUntil(File, SpelledRange.getBegin(), I);
407
408    // Skip all expanded tokens from the same macro expansion.
409    unsigned BeginExpanded = I;
410    for (; I + 1 < Result.ExpandedTokens.size(); ++I) {
411      auto NextL = Result.ExpandedTokens[I + 1].location();
412      if (!NextL.isMacroID() ||
413          SM.getExpansionLoc(NextL) != SpelledRange.getBegin())
414        break;
415    }
416    unsigned EndExpanded = I + 1;
417    consumeMapping(File, SM.getFileOffset(SpelledRange.getEnd()), BeginExpanded,
418                   EndExpanded, NextSpelled[FID]);
419  }
420
421  /// Initializes TokenBuffer::Files and fills spelled tokens and expanded
422  /// ranges for each of the files.
423  void buildSpelledTokens() {
424    for (unsigned I = 0; I < Result.ExpandedTokens.size(); ++I) {
425      auto FID =
426          SM.getFileID(SM.getExpansionLoc(Result.ExpandedTokens[I].location()));
427      auto It = Result.Files.try_emplace(FID);
428      TokenBuffer::MarkedFile &File = It.first->second;
429
430      File.EndExpanded = I + 1;
431      if (!It.second)
432        continue; // we have seen this file before.
433
434      // This is the first time we see this file.
435      File.BeginExpanded = I;
436      File.SpelledTokens = tokenize(FID, SM, LangOpts);
437    }
438  }
439
440  void consumeEmptyMapping(TokenBuffer::MarkedFile &File, unsigned EndOffset,
441                           unsigned ExpandedIndex, unsigned &SpelledIndex) {
442    consumeMapping(File, EndOffset, ExpandedIndex, ExpandedIndex, SpelledIndex);
443  }
444
445  /// Consumes spelled tokens that form a macro expansion and adds a entry to
446  /// the resulting token buffer.
447  /// (!) SpelledIndex is updated in-place.
448  void consumeMapping(TokenBuffer::MarkedFile &File, unsigned EndOffset,
449                      unsigned BeginExpanded, unsigned EndExpanded,
450                      unsigned &SpelledIndex) {
451    // We need to record this mapping before continuing.
452    unsigned MappingBegin = SpelledIndex;
453    ++SpelledIndex;
454
455    bool HitMapping =
456        tryConsumeSpelledUntil(File, EndOffset + 1, SpelledIndex).hasValue();
457    (void)HitMapping;
458    assert(!HitMapping && "recursive macro expansion?");
459
460    TokenBuffer::Mapping M;
461    M.BeginExpanded = BeginExpanded;
462    M.EndExpanded = EndExpanded;
463    M.BeginSpelled = MappingBegin;
464    M.EndSpelled = SpelledIndex;
465
466    File.Mappings.push_back(M);
467  }
468
469  /// Consumes spelled tokens until location \p L is reached and adds a mapping
470  /// covering the consumed tokens. The mapping will point to an empty expanded
471  /// range at position \p ExpandedIndex.
472  void fillGapUntil(TokenBuffer::MarkedFile &File, SourceLocation L,
473                    unsigned ExpandedIndex) {
474    assert(L.isFileID());
475    FileID FID;
476    unsigned Offset;
477    std::tie(FID, Offset) = SM.getDecomposedLoc(L);
478
479    unsigned &SpelledIndex = NextSpelled[FID];
480    unsigned MappingBegin = SpelledIndex;
481    while (true) {
482      auto EndLoc = tryConsumeSpelledUntil(File, Offset, SpelledIndex);
483      if (SpelledIndex != MappingBegin) {
484        TokenBuffer::Mapping M;
485        M.BeginSpelled = MappingBegin;
486        M.EndSpelled = SpelledIndex;
487        M.BeginExpanded = M.EndExpanded = ExpandedIndex;
488        File.Mappings.push_back(M);
489      }
490      if (!EndLoc)
491        break;
492      consumeEmptyMapping(File, SM.getFileOffset(*EndLoc), ExpandedIndex,
493                          SpelledIndex);
494
495      MappingBegin = SpelledIndex;
496    }
497  };
498
499  /// Consumes spelled tokens until it reaches Offset or a mapping boundary,
500  /// i.e. a name of a macro expansion or the start '#' token of a PP directive.
501  /// (!) NextSpelled is updated in place.
502  ///
503  /// returns None if \p Offset was reached, otherwise returns the end location
504  /// of a mapping that starts at \p NextSpelled.
505  llvm::Optional<SourceLocation>
506  tryConsumeSpelledUntil(TokenBuffer::MarkedFile &File, unsigned Offset,
507                         unsigned &NextSpelled) {
508    for (; NextSpelled < File.SpelledTokens.size(); ++NextSpelled) {
509      auto L = File.SpelledTokens[NextSpelled].location();
510      if (Offset <= SM.getFileOffset(L))
511        return llvm::None; // reached the offset we are looking for.
512      auto Mapping = CollectedExpansions.find(L.getRawEncoding());
513      if (Mapping != CollectedExpansions.end())
514        return Mapping->second; // found a mapping before the offset.
515    }
516    return llvm::None; // no more tokens, we "reached" the offset.
517  }
518
519  /// Adds empty mappings for unconsumed spelled tokens at the end of each file.
520  void fillGapsAtEndOfFiles() {
521    for (auto &F : Result.Files) {
522      if (F.second.SpelledTokens.empty())
523        continue;
524      fillGapUntil(F.second, F.second.SpelledTokens.back().endLocation(),
525                   F.second.EndExpanded);
526    }
527  }
528
529  TokenBuffer Result;
530  /// For each file, a position of the next spelled token we will consume.
531  llvm::DenseMap<FileID, unsigned> NextSpelled;
532  PPExpansions CollectedExpansions;
533  const SourceManager &SM;
534  const LangOptions &LangOpts;
535};
536
537TokenBuffer TokenCollector::consume() && {
538  PP.setTokenWatcher(nullptr);
539  Collector->disable();
540  return Builder(std::move(Expanded), std::move(Expansions),
541                 PP.getSourceManager(), PP.getLangOpts())
542      .build();
543}
544
545std::string syntax::Token::str() const {
546  return llvm::formatv("Token({0}, length = {1})", tok::getTokenName(kind()),
547                       length());
548}
549
550std::string syntax::Token::dumpForTests(const SourceManager &SM) const {
551  return llvm::formatv("{0}   {1}", tok::getTokenName(kind()), text(SM));
552}
553
554std::string TokenBuffer::dumpForTests() const {
555  auto PrintToken = [this](const syntax::Token &T) -> std::string {
556    if (T.kind() == tok::eof)
557      return "<eof>";
558    return T.text(*SourceMgr);
559  };
560
561  auto DumpTokens = [this, &PrintToken](llvm::raw_ostream &OS,
562                                        llvm::ArrayRef<syntax::Token> Tokens) {
563    if (Tokens.empty()) {
564      OS << "<empty>";
565      return;
566    }
567    OS << Tokens[0].text(*SourceMgr);
568    for (unsigned I = 1; I < Tokens.size(); ++I) {
569      if (Tokens[I].kind() == tok::eof)
570        continue;
571      OS << " " << PrintToken(Tokens[I]);
572    }
573  };
574
575  std::string Dump;
576  llvm::raw_string_ostream OS(Dump);
577
578  OS << "expanded tokens:\n"
579     << "  ";
580  // (!) we do not show '<eof>'.
581  DumpTokens(OS, llvm::makeArrayRef(ExpandedTokens).drop_back());
582  OS << "\n";
583
584  std::vector<FileID> Keys;
585  for (auto F : Files)
586    Keys.push_back(F.first);
587  llvm::sort(Keys);
588
589  for (FileID ID : Keys) {
590    const MarkedFile &File = Files.find(ID)->second;
591    auto *Entry = SourceMgr->getFileEntryForID(ID);
592    if (!Entry)
593      continue; // Skip builtin files.
594    OS << llvm::formatv("file '{0}'\n", Entry->getName())
595       << "  spelled tokens:\n"
596       << "    ";
597    DumpTokens(OS, File.SpelledTokens);
598    OS << "\n";
599
600    if (File.Mappings.empty()) {
601      OS << "  no mappings.\n";
602      continue;
603    }
604    OS << "  mappings:\n";
605    for (auto &M : File.Mappings) {
606      OS << llvm::formatv(
607          "    ['{0}'_{1}, '{2}'_{3}) => ['{4}'_{5}, '{6}'_{7})\n",
608          PrintToken(File.SpelledTokens[M.BeginSpelled]), M.BeginSpelled,
609          M.EndSpelled == File.SpelledTokens.size()
610              ? "<eof>"
611              : PrintToken(File.SpelledTokens[M.EndSpelled]),
612          M.EndSpelled, PrintToken(ExpandedTokens[M.BeginExpanded]),
613          M.BeginExpanded, PrintToken(ExpandedTokens[M.EndExpanded]),
614          M.EndExpanded);
615    }
616  }
617  return OS.str();
618}
619