[Syntax] Do not glue multiple empty PP expansions to a single mapping

[ilya-biryukov]

Summary

This change makes sure we have a single mapping for each macro expansion,
even if the result of expansion was empty.

To achieve that, we take information from PPCallbacks::MacroExpands into
account. Previously we relied only on source locations of expanded tokens.

[sammccall]

Can you explain why this is important?
(in the code)

[ilya-biryukov]

• Added comments.

[ilya-biryukov]

In D62953#1547799, @sammccall wrote:

Can you explain why this is important?
(in the code)

I've added a few comments into the code that builds token buffers, but I couldn't figure out a good place to mention this in the API docs.
It would be a natural expectation from the API from my POV, the fact that we glued empty expansions together is an implementation artifact rather than a sensible contract...

[sammccall]

Sorry, I'm having trouble understanding this patch. Can you try to find some clearer names for the new concepts, or describe how they differ?

clang/include/clang/Tooling/Syntax/Tokens.h

318 ↗

(On Diff #205377)

There are now 4 things called mappings, and I can't understand how they relate to each other. I think this needs new names and/or concepts.

326 ↗

(On Diff #205377)

Give the class and member more descriptive names?

clang/lib/Tooling/Syntax/Tokens.cpp

256 ↗

(On Diff #205377)

what is this class for, what does it do?

278 ↗

(On Diff #205377)

members should have real names

[ilya-biryukov]

clang/include/clang/Tooling/Syntax/Tokens.h

318 ↗

(On Diff #205377)

Renamed to PPExpansions.

326 ↗

(On Diff #205377)

Renamed to Expansions

clang/lib/Tooling/Syntax/Tokens.cpp

256 ↗

(On Diff #205377)

Added a comment.

[ilya-biryukov]

• Address comments

[ilya-biryukov]

To clarify, I don't think there are new concepts in this patch.
Previously, we only took information from source locations into account when building token buffers. That works fine in most cases, but not enough to find the boundaries of empty macro expansions.
In order to find those, we now also watch the callbacks from the preprocessor to get all macro expansions (including the empty ones) and reconstruct the mappings of token buffers from there.

[sammccall]

clang/include/clang/Tooling/Syntax/Tokens.h

315 ↗

(On Diff #205537)

*spelled* locations!

319 ↗

(On Diff #205537)

do I understand right that this is logically a stack, but it's hard to know when to pop or just less hassle to do this way?
if so, maybe worth mentioning

clang/lib/Tooling/Syntax/Tokens.cpp

262 ↗

(On Diff #205537)

add a comment for *why* this is needed?

269 ↗

(On Diff #205537)

This doesn't seem like a particularly standard use of the word "recursive", and the code isn't totally obvious either.

Could this be "only record top-level expansions, not those where:

• the macro use is inside a macro body
• the macro appears in an argument to another macro

Because the top level macros are treated as opaque atoms. (We probably need a FIXME for tracking arg locations somewhere)

522 ↗

(On Diff #205537)

maybe RecordedExpansions? to make the link with the recorder

clang/unittests/Tooling/Syntax/TokensTest.cpp

431 ↗

(On Diff #205537)

the two #define statements are still merged into a single mapping.
Do we have a FIXME somewhere to cover this?

[ilya-biryukov]

• Address comments, document code.
• s/Expansion/CollectedExpansions.
• Added FIXMEs for macro arguments.

clang/include/clang/Tooling/Syntax/Tokens.h

319 ↗

(On Diff #205537)

That's exactly the case, but preprocessor only exposes the point at which we push macros to the stack (PPCallbacks::MacroExpands, etc) and not points when we pop from the stack. This map is an attempt to recover the pop positions (e.g. to detect intermediate expansions in the macro arguments).

Added a comment

clang/lib/Tooling/Syntax/Tokens.cpp

269 ↗

(On Diff #205537)

Added a comment and a FIXME at the declaration site of TokenBuffer

522 ↗

(On Diff #205537)

SG, I've renamed to CollectedExpansions. (Assuming 'recorder' stands for 'collector', happy to update if I misinterpreted your comment)

[chrish_ericsson_atx]

clang/lib/Tooling/Syntax/Tokens.cpp

447 ↗

(On Diff #205537)

What is intended by this line?

[ilya-biryukov]

clang/lib/Tooling/Syntax/Tokens.cpp

447 ↗

(On Diff #205537)

Suppressing compiler warning for unused local variable.

cfe/trunk/include/clang/Tooling/Syntax/Tokens.h

 /// tokens for each of the files can be obtained via spelledTokens(FileID).
 ///
 /// To map between the expanded and spelled tokens use findSpelledByExpanded().
 ///
 /// To build a token buffer use the TokenCollector class. You can also compute
 /// the spelled tokens of a file using the tokenize() helper.
 ///
 /// FIXME: allow to map from spelled to expanded tokens when use-case shows up.
+/// FIXME: allow mappings into macro arguments.
 class TokenBuffer {
 public:
   TokenBuffer(const SourceManager &SourceMgr) : SourceMgr(&SourceMgr) {}
   /// All tokens produced by the preprocessor after all macro replacements,
   /// directives, etc. Source locations found in the clang AST will always
   /// point to one of these tokens.
   /// FIXME: figure out how to handle token splitting, e.g. '>>' can be split
   ///        into two '>' tokens by the parser. However, TokenBuffer currently
public:
   /// Lexed tokens of a file before preprocessing. E.g. for the following input
   ///     #define DECL(name) int name = 10
   ///     DECL(a);
   /// spelledTokens() returns {"#", "define", "DECL", "(", "name", ")", "eof"}.
   /// FIXME: we do not yet store tokens of directives, like #include, #define,
   ///        #pragma, etc.
   llvm::ArrayRef<syntax::Token> spelledTokens(FileID FID) const;
 
+  const SourceManager &sourceManager() const { return *SourceMgr; }
+
   std::string dumpForTests() const;
 
 private:
   /// Describes a mapping between a continuous subrange of spelled tokens and
   /// expanded tokens. Represents macro expansions, preprocessor directives,
   /// conditionally disabled pp regions, etc.
   ///   #define FOO 1+2
   ///   #define BAR(a) a + 1
public:
   /// CreateASTConsumer().
   TokenCollector(Preprocessor &P);
 
   /// Finalizes token collection. Should be called after preprocessing is
   /// finished, i.e. after running Execute().
   LLVM_NODISCARD TokenBuffer consume() &&;
 
 private:
+  /// Maps from a start to an end spelling location of transformations
+  /// performed by the preprocessor. These include:
+  ///   1. range from '#' to the last token in the line for PP directives,
+  ///   2. macro name and arguments for macro expansions.
+  /// Note that we record only top-level macro expansions, intermediate
+  /// expansions (e.g. inside macro arguments) are ignored.
+  ///
+  /// Used to find correct boundaries of macro calls and directives when
+  /// building mappings from spelled to expanded tokens.
+  ///
+  /// Logically, at each point of the preprocessor execution there is a stack of
+  /// macro expansions being processed and we could use it to recover the
+  /// location information we need. However, the public preprocessor API only
+  /// exposes the points when macro expansions start (when we push a macro onto
+  /// the stack) and not when they end (when we pop a macro from the stack).
+  /// To workaround this limitation, we rely on source location information
+  /// stored in this map.
+  using PPExpansions = llvm::DenseMap</*SourceLocation*/ int, SourceLocation>;
   class Builder;
+  class CollectPPExpansions;
+
   std::vector<syntax::Token> Expanded;
+  // FIXME: we only store macro expansions, also add directives(#pragma, etc.)
+  PPExpansions Expansions;
   Preprocessor &PP;
+  CollectPPExpansions *Collector;
 };
 
 } // namespace syntax
 } // namespace clang
 
 #endif

cfe/trunk/lib/Tooling/Syntax/Tokens.cpp

 //===- Tokens.cpp - collect tokens from preprocessing ---------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "clang/Tooling/Syntax/Tokens.h"
 
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
+#include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/Token.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"

 }
 
 llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, const Token &T) {
   return OS << T.str();
 }
 
 FileRange::FileRange(FileID File, unsigned BeginOffset, unsigned EndOffset)
     : File(File), Begin(BeginOffset), End(EndOffset) {
-      assert(File.isValid());
-      assert(BeginOffset <= EndOffset);
 }
 
 FileRange::FileRange(const SourceManager &SM, SourceLocation BeginLoc,
                      unsigned Length) {
   assert(BeginLoc.isValid());
   assert(BeginLoc.isFileID());
 
   std::tie(File, Begin) = SM.getDecomposedLoc(BeginLoc);
while (!L.LexFromRawLexer(T))
     AddToken(T);
   // 'eof' is only the last token if the input is null-terminated. Never store
   // it, for consistency.
   if (T.getKind() != tok::eof)
     AddToken(T);
   return Tokens;
 }
 
+/// Records information reqired to construct mappings for the token buffer that
+/// we are collecting.
+class TokenCollector::CollectPPExpansions : public PPCallbacks {
+public:
+  CollectPPExpansions(TokenCollector &C) : Collector(&C) {}
+
+  /// Disabled instance will stop reporting anything to TokenCollector.
+  /// This ensures that uses of the preprocessor after TokenCollector::consume()
+  /// is called do not access the (possibly invalid) collector instance.
+  void disable() { Collector = nullptr; }
+
+  void MacroExpands(const clang::Token &MacroNameTok, const MacroDefinition &MD,
+                    SourceRange Range, const MacroArgs *Args) override {
+    if (!Collector)
+      return;
+    // Only record top-level expansions, not those where:
+    //   - the macro use is inside a macro body,
+    //   - the macro appears in an argument to another macro.
+    if (!MacroNameTok.getLocation().isFileID() ||
+        (LastExpansionEnd.isValid() &&
+         Collector->PP.getSourceManager().isBeforeInTranslationUnit(
+             Range.getBegin(), LastExpansionEnd)))
+      return;
+    Collector->Expansions[Range.getBegin().getRawEncoding()] = Range.getEnd();
+    LastExpansionEnd = Range.getEnd();
+  }
+  // FIXME: handle directives like #pragma, #include, etc.
+private:
+  TokenCollector *Collector;
+  /// Used to detect recursive macro expansions.
+  SourceLocation LastExpansionEnd;
+};
+
 /// Fills in the TokenBuffer by tracing the run of a preprocessor. The
 /// implementation tracks the tokens, macro expansions and directives coming
 /// from the preprocessor and:
 /// - for each token, figures out if it is a part of an expanded token stream,
 ///   spelled token stream or both. Stores the tokens appropriately.
 /// - records mappings from the spelled to expanded token ranges, e.g. for macro
 ///   expansions.
 /// FIXME: also properly record:
DEBUG_WITH_TYPE("collect-tokens", llvm::dbgs()
                                           << "Token: "
                                           << syntax::Token(T).dumpForTests(
                                                  this->PP.getSourceManager())
                                           << "\n"
 
     );
     Expanded.push_back(syntax::Token(T));
   });
+  // And locations of macro calls, to properly recover boundaries of those in
+  // case of empty expansions.
+  auto CB = llvm::make_unique<CollectPPExpansions>(*this);
+  this->Collector = CB.get();
+  PP.addPPCallbacks(std::move(CB));
 }
 
 /// Builds mappings and spelled tokens in the TokenBuffer based on the expanded
 /// token stream.
 class TokenCollector::Builder {
 public:
-  Builder(std::vector<syntax::Token> Expanded, const SourceManager &SM,
-          const LangOptions &LangOpts)
-      : Result(SM), SM(SM), LangOpts(LangOpts) {
+  Builder(std::vector<syntax::Token> Expanded, PPExpansions CollectedExpansions,
+          const SourceManager &SM, const LangOptions &LangOpts)
+      : Result(SM), CollectedExpansions(std::move(CollectedExpansions)), SM(SM),
+        LangOpts(LangOpts) {
     Result.ExpandedTokens = std::move(Expanded);
   }
 
   TokenBuffer build() && {
     buildSpelledTokens();
 
     // Walk over expanded tokens and spelled tokens in parallel, building the
     // mappings between those using source locations.
+    // To correctly recover empty macro expansions, we also take locations
+    // reported to PPCallbacks::MacroExpands into account as we do not have any
+    // expanded tokens with source locations to guide us.
 
     // The 'eof' token is special, it is not part of spelled token stream. We
     // handle it separately at the end.
     assert(!Result.ExpandedTokens.empty());
     assert(Result.ExpandedTokens.back().kind() == tok::eof);
     for (unsigned I = 0; I < Result.ExpandedTokens.size() - 1; ++I) {
       // (!) I might be updated by the following call.
       processExpandedToken(I);
private:
   /// function returns.
   void processMacroExpansion(CharSourceRange SpelledRange, unsigned &I) {
     auto FID = SM.getFileID(SpelledRange.getBegin());
     assert(FID == SM.getFileID(SpelledRange.getEnd()));
     TokenBuffer::MarkedFile &File = Result.Files[FID];
 
     fillGapUntil(File, SpelledRange.getBegin(), I);
 
-    TokenBuffer::Mapping M;
-    // Skip the spelled macro tokens.
-    std::tie(M.BeginSpelled, M.EndSpelled) =
-        consumeSpelledUntil(File, SpelledRange.getEnd().getLocWithOffset(1));
     // Skip all expanded tokens from the same macro expansion.
-    M.BeginExpanded = I;
+    unsigned BeginExpanded = I;
     for (; I + 1 < Result.ExpandedTokens.size(); ++I) {
       auto NextL = Result.ExpandedTokens[I + 1].location();
       if (!NextL.isMacroID() ||
           SM.getExpansionLoc(NextL) != SpelledRange.getBegin())
         break;
     }
-    M.EndExpanded = I + 1;
-
-    // Add a resulting mapping.
-    File.Mappings.push_back(M);
+    unsigned EndExpanded = I + 1;
+    consumeMapping(File, SM.getFileOffset(SpelledRange.getEnd()), BeginExpanded,
+                   EndExpanded, NextSpelled[FID]);
   }
 
   /// Initializes TokenBuffer::Files and fills spelled tokens and expanded
   /// ranges for each of the files.
   void buildSpelledTokens() {
     for (unsigned I = 0; I < Result.ExpandedTokens.size(); ++I) {
       auto FID =
           SM.getFileID(SM.getExpansionLoc(Result.ExpandedTokens[I].location()));
       auto It = Result.Files.try_emplace(FID);
       TokenBuffer::MarkedFile &File = It.first->second;
 
       File.EndExpanded = I + 1;
       if (!It.second)
         continue; // we have seen this file before.
 
       // This is the first time we see this file.
       File.BeginExpanded = I;
       File.SpelledTokens = tokenize(FID, SM, LangOpts);
     }
   }
 
-  /// Consumed spelled tokens until location L is reached (token starting at L
-  /// is not included). Returns the indicies of the consumed range.
-  std::pair</*Begin*/ unsigned, /*End*/ unsigned>
-  consumeSpelledUntil(TokenBuffer::MarkedFile &File, SourceLocation L) {
-    assert(L.isFileID());
-    FileID FID;
-    unsigned Offset;
-    std::tie(FID, Offset) = SM.getDecomposedLoc(L);
+  void consumeEmptyMapping(TokenBuffer::MarkedFile &File, unsigned EndOffset,
+                           unsigned ExpandedIndex, unsigned &SpelledIndex) {
+    consumeMapping(File, EndOffset, ExpandedIndex, ExpandedIndex, SpelledIndex);
+  }
+
+  /// Consumes spelled tokens that form a macro expansion and adds a entry to
+  /// the resulting token buffer.
+  /// (!) SpelledIndex is updated in-place.
+  void consumeMapping(TokenBuffer::MarkedFile &File, unsigned EndOffset,
+                      unsigned BeginExpanded, unsigned EndExpanded,
+                      unsigned &SpelledIndex) {
+    // We need to record this mapping before continuing.
+    unsigned MappingBegin = SpelledIndex;
+    ++SpelledIndex;
+
+    bool HitMapping =
+        tryConsumeSpelledUntil(File, EndOffset + 1, SpelledIndex).hasValue();
+    (void)HitMapping;
+    assert(!HitMapping && "recursive macro expansion?");
+
+    TokenBuffer::Mapping M;
+    M.BeginExpanded = BeginExpanded;
+    M.EndExpanded = EndExpanded;
+    M.BeginSpelled = MappingBegin;
+    M.EndSpelled = SpelledIndex;
 
-    // (!) we update the index in-place.
-    unsigned &SpelledI = NextSpelled[FID];
-    unsigned Before = SpelledI;
-    for (; SpelledI < File.SpelledTokens.size() &&
-           SM.getFileOffset(File.SpelledTokens[SpelledI].location()) < Offset;
-         ++SpelledI) {
-    }
-    return std::make_pair(Before, /*After*/ SpelledI);
-  };
+    File.Mappings.push_back(M);
 
   /// Consumes spelled tokens until location \p L is reached and adds a mapping
   /// covering the consumed tokens. The mapping will point to an empty expanded
   /// range at position \p ExpandedIndex.
   void fillGapUntil(TokenBuffer::MarkedFile &File, SourceLocation L,
                     unsigned ExpandedIndex) {
-    unsigned BeginSpelledGap, EndSpelledGap;
-    std::tie(BeginSpelledGap, EndSpelledGap) = consumeSpelledUntil(File, L);
-    if (BeginSpelledGap == EndSpelledGap)
-      return; // No gap.
+    assert(L.isFileID());
+    FileID FID;
+    unsigned Offset;
+    std::tie(FID, Offset) = SM.getDecomposedLoc(L);
+
+    unsigned &SpelledIndex = NextSpelled[FID];
+    unsigned MappingBegin = SpelledIndex;
+    while (true) {
+      auto EndLoc = tryConsumeSpelledUntil(File, Offset, SpelledIndex);
+      if (SpelledIndex != MappingBegin) {
         TokenBuffer::Mapping M;
-    M.BeginSpelled = BeginSpelledGap;
-    M.EndSpelled = EndSpelledGap;
+        M.BeginSpelled = MappingBegin;
+        M.EndSpelled = SpelledIndex;
         M.BeginExpanded = M.EndExpanded = ExpandedIndex;
         File.Mappings.push_back(M);
+      }
+      if (!EndLoc)
+        break;
+      consumeEmptyMapping(File, SM.getFileOffset(*EndLoc), ExpandedIndex,
+                          SpelledIndex);
+
+      MappingBegin = SpelledIndex;
+    }
   };
 
+  /// Consumes spelled tokens until it reaches Offset or a mapping boundary,
+  /// i.e. a name of a macro expansion or the start '#' token of a PP directive.
+  /// (!) NextSpelled is updated in place.
+  ///
+  /// returns None if \p Offset was reached, otherwise returns the end location
+  /// of a mapping that starts at \p NextSpelled.
+  llvm::Optional<SourceLocation>
+  tryConsumeSpelledUntil(TokenBuffer::MarkedFile &File, unsigned Offset,
+                         unsigned &NextSpelled) {
+    for (; NextSpelled < File.SpelledTokens.size(); ++NextSpelled) {
+      auto L = File.SpelledTokens[NextSpelled].location();
+      if (Offset <= SM.getFileOffset(L))
+        return llvm::None; // reached the offset we are looking for.
+      auto Mapping = CollectedExpansions.find(L.getRawEncoding());
+      if (Mapping != CollectedExpansions.end())
+        return Mapping->second; // found a mapping before the offset.
+    }
+    return llvm::None; // no more tokens, we "reached" the offset.
+  }
+
   /// Adds empty mappings for unconsumed spelled tokens at the end of each file.
   void fillGapsAtEndOfFiles() {
     for (auto &F : Result.Files) {
-      unsigned Next = NextSpelled[F.first];
-      if (F.second.SpelledTokens.size() == Next)
-        continue; // All spelled tokens are accounted for.
-
-      // Record a mapping for the gap at the end of the spelled tokens.
-      TokenBuffer::Mapping M;
-      M.BeginSpelled = Next;
-      M.EndSpelled = F.second.SpelledTokens.size();
-      M.BeginExpanded = F.second.EndExpanded;
-      M.EndExpanded = F.second.EndExpanded;
-
-      F.second.Mappings.push_back(M);
+      if (F.second.SpelledTokens.empty())
+        continue;
+      fillGapUntil(F.second, F.second.SpelledTokens.back().endLocation(),
+                   F.second.EndExpanded);
     }
   }
 
   TokenBuffer Result;
   /// For each file, a position of the next spelled token we will consume.
   llvm::DenseMap<FileID, unsigned> NextSpelled;
+  PPExpansions CollectedExpansions;
   const SourceManager &SM;
   const LangOptions &LangOpts;
 };
 
 TokenBuffer TokenCollector::consume() && {
   PP.setTokenWatcher(nullptr);
-  return Builder(std::move(Expanded), PP.getSourceManager(), PP.getLangOpts())
+  Collector->disable();
+  return Builder(std::move(Expanded), std::move(Expansions),
+                 PP.getSourceManager(), PP.getLangOpts())
       .build();
 }
 
 std::string syntax::Token::str() const {
   return llvm::formatv("Token({0}, length = {1})", tok::getTokenName(kind()),
                        length());
 }
 

cfe/trunk/unittests/Tooling/Syntax/TokensTest.cpp

)cpp",
        "file './input.cpp'\n"
        "  spelled tokens:\n"
        "    # define ADD ( X , Y ) X + Y # define MULT ( X , Y ) X * Y int "
        "a = ADD ( MULT ( 1 , 2 ) , MULT ( 3 , ADD ( 4 , 5 ) ) ) ;\n"
        "  mappings:\n"
        "    ['#'_0, 'int'_22) => ['int'_0, 'int'_0)\n"
        "    ['ADD'_25, ';'_46) => ['1'_3, ';'_12)\n"},
       // Empty macro replacement.
+      // FIXME: the #define directives should not be glued together.
       {R"cpp(
     #define EMPTY
     #define EMPTY_FUNC(X)
     EMPTY
     EMPTY_FUNC(1+2+3)
     )cpp",
        R"(expanded tokens:
   <empty>
 file './input.cpp'
   spelled tokens:
     # define EMPTY # define EMPTY_FUNC ( X ) EMPTY EMPTY_FUNC ( 1 + 2 + 3 )
   mappings:
-    ['#'_0, '<eof>'_18) => ['<eof>'_0, '<eof>'_0)
+    ['#'_0, 'EMPTY'_9) => ['<eof>'_0, '<eof>'_0)
+    ['EMPTY'_9, 'EMPTY_FUNC'_10) => ['<eof>'_0, '<eof>'_0)
+    ['EMPTY_FUNC'_10, '<eof>'_18) => ['<eof>'_0, '<eof>'_0)
 )"},
       // File ends with a macro replacement.
       {R"cpp(
     #define FOO 10+10;
     int a = FOO
     )cpp",
        R"(expanded tokens:
   int a = 10 + 10 ;