[analyzer] Introduce MacroExpansionContext to libAnalysis

[steakhal]

Summary

Introduce MacroExpansionContext to track what and how macros in a translation
unit expand. This is the first element of the patch-stack in this direction.

The main goal is to substitute the current macro expansion generator in the
PlistsDiagnostics, but all the other DiagnosticsConsumer could benefit from
this.

getExpandedText and getOriginalText are the primary functions of this class.
The former can provide you the text that was the result of the macro expansion
chain starting from a SourceLocation.
While the latter will tell you what text was in the original source code
replaced by the macro expansion chain from that location.

Here is an example:

void bar();
#define retArg(x) x
#define retArgUnclosed retArg(bar()
#define BB CC
#define applyInt BB(int)
#define CC(x) retArgUnclosed

void unbalancedMacros() {
  applyInt  );
//^~~~~~~~~~^ is the substituted range
// Original text is "applyInt  )"
// Expanded text is "bar()"
}

#define expandArgUnclosedCommaExpr(x) (x, bar(), 1
#define f expandArgUnclosedCommaExpr

void unbalancedMacros2() {
  int x =  f(f(1))  ));  // Look at the parenthesis!
//         ^~~~~~^ is the substituted range
// Original text is "f(f(1))"
// Expanded text is "((1,bar(),1,bar(),1"
}

Might worth investigating how to provide a reusable component, which could be
used for example by a standalone tool eg. expanding all macros to their
definitions.

I borrowed the main idea from the PrintPreprocessedOutput.cpp Frontend
component, providing a PPCallbacks instance hooking the preprocessor events.
I'm using that for calculating the source range where tokens will be expanded
to. I'm also using the Preprocessor's OnToken callback, via the
Preprocessor::setTokenWatcher to reconstruct the expanded text.

Unfortunately, I concatenate the token's string representation without any
whitespaces except if the token is an identifier when I emit an extra space
to produce valid code for int var token sequences.
This could be improved later if needed.

Patch-stack:

1. D93222 (this one) Introduces the MacroExpansionContext class and unittests
2. D93223 Create MacroExpansionContext member in AnalysisConsumer and pass down to the diagnostics consumers
3. D93224 Use the MacroExpansionContext for macro expansions in plists It replaces the 'old' macro expansion mechanism.
4. D94673 API for CTU macro expansions You should be able to get a MacroExpansionContext for each imported TU. Right now it will just return llvm::None as this is not implemented yet.
5. FIXME: Implement macro expansion tracking for imported TUs as well.

It would also relieve us from bugs like:

• [fixed] D86135
• [confirmed] The __VA_ARGS__ and other macro nitty-gritty, such as how to stringify macro parameters, where to put or swallow commas, etc. are not handled correctly.
• [confirmed] Unbalanced parenthesis are not well handled - resulting in incorrect expansions or even crashes.
• [confirmed][crashing] https://bugs.llvm.org/show_bug.cgi?id=48358

[martong]

Nice and precise work! And special thanks for the unit tests. I've found some minor nits.

clang/include/clang/Analysis/MacroExpansionContext.h

78

?

80–81

I think we should have an Optional<String> as a return type, so we'd be able to detect if no macro expansion happened. (?)

82

Could this be StringRef also?

88–89

We should be able to distinguish between no macro expansion (1) and expansion to an empty string (2). So, I think we should have an Optional<StringRef> as a return type.

clang/lib/Analysis/MacroExpansionContext.cpp

40

?

[martong]

clang/include/clang/Analysis/MacroExpansionContext.h

83

getExpandedText ? Since what you get back is not a macro anymore.

91

Substituted is a bit ambiguous to me. What about getOriginalText ?

[xazax.hun]

Overall looks good to me, I have some minor nits and questions inline.

clang/lib/Analysis/MacroExpansionContext.cpp

23

It may be more idiomatic to put classes in an anonymous namespace rather than expanding them in a method.

34

Will we end up recording ranges for intermediate macro expansions? If yes, we might end up recording excessive amount of ranges. Is there any way to only record final expansion ranges in that case?

40

Why do you need the assignment in &SM = SM?

95

I am a bit uneasy about this. As far as I understand a macro could be expanded to an empty string. How could the user differentiate between a valid empty expansion and a lookup failure. Also, can this lookup ever fail in a well behaving code? Do we need to add llvm_unreachable() or something?

106

Similar concerns to above. Do we want an assert? When can this happen?

[steakhal]

I want to highlight, that the 4th part of the stack is not yet done.
Partially because I'm not quite familiar with CTU.
AFAIK, CTU creates compiler invocations, which are going to call Parse at some point.
I'm not sure how to configure, apply the callbacks, etc. on the Preprocessor in the middle of that process.
I'm also reluctant to pass this domain-specific MacroExpansionContext as the 23rd parameter to that generic function (ASTUnit::LoadFromCommandLine).

I'm not even sure if there will be a Preprocessor, which would generate the 'OnToken' or PPCallbacks calls if we are parsing a PCH or some other serialized source.
That would be crucial for this MacroExpansion machinery. I hope you can ensure that I'm on the right path.

clang/include/clang/Analysis/MacroExpansionContext.h

80–81

Yes, it depends on what interface we want to provide.
If we expect it to be called on source locations that participate in a macro expansion, then it would be somewhat redundant.
I don't mind if it returns an Optional<>.

82

We could return a StringRef, but that would point to an entry of a DenseMap. That could be invalidated later if the preprocessor still generates tokens.

If we say that these calls should be called after the preprocessing is completely done, it could just return a StringRef.

83

You are right! I like it.

88–89

I'm not sure about this.
If a SourceLocation is not a macro expansion, then the isFileID() would return false AFAIK.
Otherwise, if the result is an empty string, that means that the macro indeed expanded to no tokens.

91

I agree.

clang/lib/Analysis/MacroExpansionContext.cpp

23

I tried, but I could not hide the MacroExpansionRangeRecorder class as a detail.
https://godbolt.org/z/bcYK7x
Let me know if there is a better way to hide details.

40

SM is an object member.
The lambda should either capture the this pointer or a pointer/reference to the referred member (SM).
I preferred the latter as the lambda doesn't want to access all of the members except this one.

95

Yes, I should have put an unreachable there as you suggested.

106

Yes, I should put an assert there.

[xazax.hun]

clang/lib/Analysis/MacroExpansionContext.cpp

23

I don't see any problems with the code you linked. What do you mean by could not hide it better? I think, it is very common to have utility functions with the current file as the visibility.

[whisperity]

clang/lib/Analysis/MacroExpansionContext.cpp

23

@steakhal You need to forward declare the class in the detail namespace first within the header (so both the namespace and the qualified name detail::Class is introduced), and then the friend class declaration works as intended, see: https://godbolt.org/z/hs45ze

[xazax.hun]

clang/lib/Analysis/MacroExpansionContext.cpp

23

Oh, I see the problem now. Somehow I did not see the error message. I would also not mind not hiding the using ExpansionRangeMap ... part,

[steakhal]

• move MacroExpansionRangeRecorder to clang::detail and mark it as a friend class
• fix comment typo in getExpandedMacroForLocation
• rename getExpandedMacroForLocation -> getExpandedText
• rename getSubstitutedTextForLocation -> getOriginalText
• introduce llvm_unreachable where applicable.

No tests were changed.

[martong]

Nice work! Thanks!

clang/lib/Analysis/MacroExpansionContext.cpp

40

[Range, &SM, &MacroName] would not work? (why?)

231

Missing newline?

[steakhal]

clang/lib/Analysis/MacroExpansionContext.cpp

34

All top-level macro expansions will insert a new entry to the map. All intermediate macro expansions right after that will have the very same expansion location, so it will just update the 'end' for that expansion chain.
For tracking the final tokens I'm just aggregating them for every expansion location in a similar fashion.

40

MacroExpansionContext.cpp:35:50: error: capture of non-variable 'clang::detail::MacroExpansionRangeRecorder::SM'
MacroExpansionContext.cpp:38:16: error: 'this' was not captured for this lambda function

231

I honestly don't know why was that not addressed by clang-format.
Even here, the prebuild bot should have complained about this - if this is an issue.

If you still think I should add that newline, we should also take a look at the .clang-format.

[steakhal]

No changes made besides backporting API changes from the immediate child revision, D93223.
This way the API of MacroExpansionContext won't be changed in later parts of this stack.

[steakhal]

Ignore _Pragma macro expansions, also ignore those during lexing.
Added a unit-test to demonstrate that we don't crash and these expansions are not recorded.

Fix typo in MacroExpansionContext.cpp header comment.

[martong]

Still looks good to me! Thanks for handling the pragma cases!

[Szelethus]

This is amazing. We longed for a sensible implementation for this for a long time. Really liking the unit tests as well!

There are a number of inlines you didn't mark as done but seem to have addressed.

The main goal is to substitute the current macro expansion generator in the PlistsDiagnostics, but all the other DiagnosticsConsumer could benefit from this.

Good! Burn it, bury it, lets forget that it ever existed. It was a stupid idea from the get-go and got so much worse over time.

clang/include/clang/Analysis/MacroExpansionContext.h

65–67

That might be very tricky. I recall stumbling across the same issue when using the Preprocessor. I think I used this or something similar:

https://clang.llvm.org/doxygen/classclang_1_1Preprocessor.html#adb53a8b33c6ea7a5e0953126da5fb121

92

Consider mentioning getExpansionLoc, since that is almost always the source of the expansion loc (no other comes to my mind).

clang/lib/Analysis/MacroExpansionContext.cpp

42–44

Well that is interesting, so the Range parameter is not (always?) the range of the expansion. Doxygen says that

Called by Preprocessor::HandleMacroExpandedIdentifier when a macro invocation is found.

in which there is a TODO:

// FIXME: We lose macro args info with delayed callback.
Callbacks->MacroExpands(Info.Tok, Info.MD, Info.Range,
                        /*Args=*/nullptr);

I suppose you're handling this corner case?

184–187

In the TokenPrinter in the plist implementation, I used Preprocessor::getSpelling().

[Szelethus]

clang/include/clang/Analysis/MacroExpansionContext.h

106

Hmm, I'm by no means an expert, but isn't a string-like structure a bit big for a DenseMap?

[steakhal]

Thank you @Szelethus for taking the time to review this.
This time I marked the inline comments done where it was applicable :)

I'm gonna investigate some of your comments and if everything goes well I'm planning to commit this in the next week.

clang/include/clang/Analysis/MacroExpansionContext.h

65–67

Since I'm listening to every new token that was parsed (via the token watcher), the tokens will be absolutely correct. But I'm sacrificing the precise location to acquire it.
However, we should be able to reconstruct the precise position too with some additional bookkeeping. But I'm more interested in correct expansions than whitespace preserving (and also correct) expansions.
That's why I'm not interested in re-lexing anything via clang::Preprocessor::getRawToken.

92

Ok, I will.

106

I'm not sure. When I grepped for an associative container having SourceLocation as a key, the only one I found was the DenseMap.
Besides that, the Value should fit into a single cacheline (at least on my X86_64 linux machine).
What data structure you think is a better fit?

clang/lib/Analysis/MacroExpansionContext.cpp

42–44

It could be, but I'm not sure.
According to the code snippet you mention, the range does not look suspicious. The nullptr is passed as the Args parameter.
So, I think it's a different thing.

Either way, my tests will break if anything changes, so we will be notified for sure.

184–187

Oh, I'm gonna investigate!
This code looks really ugly xD.

231

Fixed.

clang/include/clang/Analysis/MacroExpansionContext.h

+//===- MacroExpansionContext.h - Macro expansion information ----*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_MACROEXPANSIONCONTEXT_H
+#define LLVM_CLANG_ANALYSIS_MACROEXPANSIONCONTEXT_H
+
+#include "clang/Basic/LangOptions.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Lex/Preprocessor.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace clang {
+
+namespace detail {
+class MacroExpansionRangeRecorder;
+} // namespace detail
+
+/// MacroExpansionContext tracks the macro expansions processed by the
+/// Preprocessor. It means that it can track source locations from a single
+/// translation unit. For every macro expansion it can tell you what text will
+/// be substituted.
+///
+/// It was designed to deal with:
+///  - regular macros
+///  - macro functions
+///  - variadic macros
+///  - transitive macro expansions
+///  - macro redefinition
+///  - unbalanced parenthesis
+///
+/// \code{.c}
+///   void bar();
+///   #define retArg(x) x
+///   #define retArgUnclosed retArg(bar()
+///   #define BB CC
+///   #define applyInt BB(int)
+///   #define CC(x) retArgUnclosed
+///
+///   void unbalancedMacros() {
+///     applyInt  );
+///   //^~~~~~~~~~^ is the substituted range
+///   // Substituted text is "applyInt  )"
+///   // Expanded text is "bar()"
+///   }
+///
+///   #define expandArgUnclosedCommaExpr(x) (x, bar(), 1
+///   #define f expandArgUnclosedCommaExpr
+///
+///   void unbalancedMacros2() {
+///     int x =  f(f(1))  ));  // Look at the parenthesis!
+///   //         ^~~~~~^ is the substituted range
+///   // Substituted text is "f(f(1))"
+///   // Expanded text is "((1,bar(),1,bar(),1"
+///   }
+/// \endcode
+/// \remark Currently we don't respect the whitespaces between expanded tokens,
+///         so the output for this example might differ from the -E compiler
+///         invocation.
+/// \remark All whitespaces are consumed while constructing the expansion.
+///         After all identifier a single space inserted to produce a valid C
+///         code even if identifier follows an other identifiers such as
+///         variable declarations.
+/// \remark MacroExpansionContext object must outlive the Preprocessor
+///         parameter.
+class MacroExpansionContext {
+public:
+  /// Creates a MacroExpansionContext.
+  /// \remark You must call registerForPreprocessor to set the required
+  ///         onTokenLexed callback and the PPCallbacks.
+  explicit MacroExpansionContext(const LangOptions &LangOpts);
+
+  /// Register the necessary callbacks to the Preprocessor to record the
+  /// expansion events and the generated tokens. Must ensure that this object
+  /// outlives the given Preprocessor.
+  void registerForPreprocessor(Preprocessor &PP);
+
+  /// \param MacroExpansionLoc Must be the expansion location of a macro.
+  /// \return The textual representation of the token sequence which was
+  ///         substituted in place of the macro after the preprocessing.
+  ///         If no macro was expanded at that location, returns llvm::None.
+  Optional<StringRef> getExpandedText(SourceLocation MacroExpansionLoc) const;
+
+  /// \param MacroExpansionLoc Must be the expansion location of a macro.
+  /// \return The text from the original source code which were substituted by
+  ///         the macro expansion chain from the given location.
+  ///         If no macro was expanded at that location, returns llvm::None.
+  Optional<StringRef> getOriginalText(SourceLocation MacroExpansionLoc) const;
+
+  LLVM_DUMP_METHOD void dumpExpansionRangesToStream(raw_ostream &OS) const;
+  LLVM_DUMP_METHOD void dumpExpandedTextsToStream(raw_ostream &OS) const;
+  LLVM_DUMP_METHOD void dumpExpansionRanges() const;
+  LLVM_DUMP_METHOD void dumpExpandedTexts() const;
+
+private:
+  friend class detail::MacroExpansionRangeRecorder;
+  using MacroExpansionText = SmallString<40>;
+  using ExpansionMap = llvm::DenseMap<SourceLocation, MacroExpansionText>;
+  using ExpansionRangeMap = llvm::DenseMap<SourceLocation, SourceLocation>;
+
+  /// Associates the textual representation of the expanded tokens at the given
+  /// macro expansion location.
+  ExpansionMap ExpandedTokens;
+
+  /// Tracks which source location was the last affected by any macro
+  /// substitution starting from a given macro expansion location.
+  ExpansionRangeMap ExpansionRanges;
+
+  Preprocessor *PP = nullptr;
+  SourceManager *SM = nullptr;
+  const LangOptions &LangOpts;
+
+  /// This callback is called by the preprocessor.
+  /// It stores the textual representation of the expanded token sequence for a
+  /// macro expansion location.
+  void onTokenLexed(const Token &Tok);
+};
+} // end namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_MACROEXPANSIONCONTEXT_H

clang/lib/Analysis/CMakeLists.txt

add_clang_library(clangAnalysis
   CocoaConventions.cpp
   ConstructionContext.cpp
   Consumed.cpp
   CodeInjector.cpp
   Dominators.cpp
   ExprMutationAnalyzer.cpp
   IssueHash.cpp
   LiveVariables.cpp
+  MacroExpansionContext.cpp
   ObjCNoReturn.cpp
   PathDiagnostic.cpp
   PostOrderCFGView.cpp
   ProgramPoint.cpp
   ReachableCode.cpp
   RetainSummaryManager.cpp
   ThreadSafety.cpp
   ThreadSafetyCommon.cpp

clang/lib/Analysis/MacroExpansionContext.cpp

+//===- MacroExpansionContext.cpp - Macro expansion information --*- C++ -*-===//
+//
+// 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/Analysis/MacroExpansionContext.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "macro-expansion-context"
+
+static void dumpTokenInto(const clang::Preprocessor &PP, clang::raw_ostream &OS,
+                          clang::Token Tok);
+
+namespace clang {
+namespace detail {
+class MacroExpansionRangeRecorder : public PPCallbacks {
+  const Preprocessor &PP;
+  SourceManager &SM;
+  MacroExpansionContext::ExpansionRangeMap &ExpansionRanges;
+
+public:
+  explicit MacroExpansionRangeRecorder(
+      const Preprocessor &PP, SourceManager &SM,
+      MacroExpansionContext::ExpansionRangeMap &ExpansionRanges)
+      : PP(PP), SM(SM), ExpansionRanges(ExpansionRanges) {}
+
+  void MacroExpands(const Token &MacroName, const MacroDefinition &MD,
+                    SourceRange Range, const MacroArgs *Args) override {
+    // Ignore annotation tokens like: _Pragma("pack(push, 1)")
+    if (MacroName.getIdentifierInfo()->getName() == "_Pragma")
+      return;
+
+    SourceLocation MacroNameBegin = SM.getExpansionLoc(MacroName.getLocation());
+    assert(MacroNameBegin == SM.getExpansionLoc(Range.getBegin()));
+
+    const SourceLocation ExpansionEnd = [Range, &SM = SM, &MacroName] {
+      // If the range is empty, use the length of the macro.
+      if (Range.getBegin() == Range.getEnd())
+        return SM.getExpansionLoc(
+            MacroName.getLocation().getLocWithOffset(MacroName.getLength()));
+
+      // Include the last character.
+      return SM.getExpansionLoc(Range.getEnd()).getLocWithOffset(1);
+    }();
+
+    LLVM_DEBUG(llvm::dbgs() << "MacroExpands event: '";
+               dumpTokenInto(PP, llvm::dbgs(), MacroName);
+               llvm::dbgs()
+               << "' with length " << MacroName.getLength() << " at ";
+               MacroNameBegin.print(llvm::dbgs(), SM);
+               llvm::dbgs() << ", expansion end at ";
+               ExpansionEnd.print(llvm::dbgs(), SM); llvm::dbgs() << '\n';);
+
+    // If the expansion range is empty, use the identifier of the macro as a
+    // range.
+    MacroExpansionContext::ExpansionRangeMap::iterator It;
+    bool Inserted;
+    std::tie(It, Inserted) =
+        ExpansionRanges.try_emplace(MacroNameBegin, ExpansionEnd);
+    if (Inserted) {
+      LLVM_DEBUG(llvm::dbgs() << "maps ";
+                 It->getFirst().print(llvm::dbgs(), SM); llvm::dbgs() << " to ";
+                 It->getSecond().print(llvm::dbgs(), SM);
+                 llvm::dbgs() << '\n';);
+    } else {
+      if (SM.isBeforeInTranslationUnit(It->getSecond(), ExpansionEnd)) {
+        It->getSecond() = ExpansionEnd;
+        LLVM_DEBUG(
+            llvm::dbgs() << "remaps "; It->getFirst().print(llvm::dbgs(), SM);
+            llvm::dbgs() << " to "; It->getSecond().print(llvm::dbgs(), SM);
+            llvm::dbgs() << '\n';);
+      }
+    }
+  }
+};
+} // namespace detail
+} // namespace clang
+
+using namespace clang;
+
+MacroExpansionContext::MacroExpansionContext(const LangOptions &LangOpts)
+    : LangOpts(LangOpts) {}
+
+void MacroExpansionContext::registerForPreprocessor(Preprocessor &NewPP) {
+  PP = &NewPP;
+  SM = &NewPP.getSourceManager();
+
+  // Make sure that the Preprocessor does not outlive the MacroExpansionContext.
+  PP->addPPCallbacks(std::make_unique<detail::MacroExpansionRangeRecorder>(
+      *PP, *SM, ExpansionRanges));
+  // Same applies here.
+  PP->setTokenWatcher([this](const Token &Tok) { onTokenLexed(Tok); });
+}
+
+Optional<StringRef>
+MacroExpansionContext::getExpandedText(SourceLocation MacroExpansionLoc) const {
+  if (MacroExpansionLoc.isMacroID())
+    return llvm::None;
+
+  // If there was no macro expansion at that location, return None.
+  if (ExpansionRanges.find_as(MacroExpansionLoc) == ExpansionRanges.end())
+    return llvm::None;
+
+  // There was macro expansion, but resulted in no tokens, return empty string.
+  const auto It = ExpandedTokens.find_as(MacroExpansionLoc);
+  if (It == ExpandedTokens.end())
+    return StringRef{""};
+
+  // Otherwise we have the actual token sequence as string.
+  return StringRef{It->getSecond()};
+}
+
+Optional<StringRef>
+MacroExpansionContext::getOriginalText(SourceLocation MacroExpansionLoc) const {
+  if (MacroExpansionLoc.isMacroID())
+    return llvm::None;
+
+  const auto It = ExpansionRanges.find_as(MacroExpansionLoc);
+  if (It == ExpansionRanges.end())
+    return llvm::None;
+
+  assert(It->getFirst() != It->getSecond() &&
+         "Every macro expansion must cover a non-empty range.");
+
+  return Lexer::getSourceText(
+      CharSourceRange::getCharRange(It->getFirst(), It->getSecond()), *SM,
+      LangOpts);
+}
+
+void MacroExpansionContext::dumpExpansionRanges() const {
+  dumpExpansionRangesToStream(llvm::dbgs());
+}
+void MacroExpansionContext::dumpExpandedTexts() const {
+  dumpExpandedTextsToStream(llvm::dbgs());
+}
+
+void MacroExpansionContext::dumpExpansionRangesToStream(raw_ostream &OS) const {
+  std::vector<std::pair<SourceLocation, SourceLocation>> LocalExpansionRanges;
+  LocalExpansionRanges.reserve(ExpansionRanges.size());
+  for (const auto &Record : ExpansionRanges)
+    LocalExpansionRanges.emplace_back(
+        std::make_pair(Record.getFirst(), Record.getSecond()));
+  llvm::sort(LocalExpansionRanges);
+
+  OS << "\n=============== ExpansionRanges ===============\n";
+  for (const auto &Record : LocalExpansionRanges) {
+    OS << "> ";
+    Record.first.print(OS, *SM);
+    OS << ", ";
+    Record.second.print(OS, *SM);
+    OS << '\n';
+  }
+}
+
+void MacroExpansionContext::dumpExpandedTextsToStream(raw_ostream &OS) const {
+  std::vector<std::pair<SourceLocation, MacroExpansionText>>
+      LocalExpandedTokens;
+  LocalExpandedTokens.reserve(ExpandedTokens.size());
+  for (const auto &Record : ExpandedTokens)
+    LocalExpandedTokens.emplace_back(
+        std::make_pair(Record.getFirst(), Record.getSecond()));
+  llvm::sort(LocalExpandedTokens);
+
+  OS << "\n=============== ExpandedTokens ===============\n";
+  for (const auto &Record : LocalExpandedTokens) {
+    OS << "> ";
+    Record.first.print(OS, *SM);
+    OS << " -> '" << Record.second << "'\n";
+  }
+}
+
+static void dumpTokenInto(const Preprocessor &PP, raw_ostream &OS, Token Tok) {
+  assert(Tok.isNot(tok::raw_identifier));
+
+  // Ignore annotation tokens like: _Pragma("pack(push, 1)")
+  if (Tok.isAnnotation())
+    return;
+
+  if (IdentifierInfo *II = Tok.getIdentifierInfo()) {
+    // FIXME: For now, we don't respect whitespaces between macro expanded
+    // tokens. We just emit a space after every identifier to produce a valid
+    // code for `int a ;` like expansions.
+    //              ^-^-- Space after the 'int' and 'a' identifiers.
+    OS << II->getName() << ' ';
+  } else if (Tok.isLiteral() && !Tok.needsCleaning() && Tok.getLiteralData()) {
+    OS << StringRef(Tok.getLiteralData(), Tok.getLength());
+  } else {
+    char Tmp[256];
+    if (Tok.getLength() < sizeof(Tmp)) {
+      const char *TokPtr = Tmp;
+      // FIXME: Might use a different overload for cleaner callsite.
+      unsigned Len = PP.getSpelling(Tok, TokPtr);
+      OS.write(TokPtr, Len);
+    } else {
+      OS << "<too long token>";
+    }
+  }
+}
+
+void MacroExpansionContext::onTokenLexed(const Token &Tok) {
+  SourceLocation SLoc = Tok.getLocation();
+  if (SLoc.isFileID())
+    return;
+
+  LLVM_DEBUG(llvm::dbgs() << "lexed macro expansion token '";
+             dumpTokenInto(*PP, llvm::dbgs(), Tok); llvm::dbgs() << "' at ";
+             SLoc.print(llvm::dbgs(), *SM); llvm::dbgs() << '\n';);
+
+  // Remove spelling location.
+  SourceLocation CurrExpansionLoc = SM->getExpansionLoc(SLoc);
+
+  MacroExpansionText TokenAsString;
+  llvm::raw_svector_ostream OS(TokenAsString);
+
+  // FIXME: Prepend newlines and space to produce the exact same output as the
+  // preprocessor would for this token.
+
+  dumpTokenInto(*PP, OS, Tok);
+
+  ExpansionMap::iterator It;
+  bool Inserted;
+  std::tie(It, Inserted) =
+      ExpandedTokens.try_emplace(CurrExpansionLoc, std::move(TokenAsString));
+  if (!Inserted)
+    It->getSecond().append(TokenAsString);
+}
+

clang/unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisTests
   CFGDominatorTree.cpp
   CFGTest.cpp
   CloneDetectionTest.cpp
   ExprMutationAnalyzerTest.cpp
+  MacroExpansionContextTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisTests
   PRIVATE
   clangAnalysis
   clangAST
   clangASTMatchers
   clangBasic
   clangFrontend
+  clangLex
   clangSerialization
+  clangTesting
   clangTooling
   )
+
+target_link_libraries(ClangAnalysisTests
+  PRIVATE
+  LLVMTestingSupport
+  )

clang/unittests/Analysis/MacroExpansionContextTest.cpp

+//===- unittests/Analysis/MacroExpansionContextTest.cpp - -----------------===//
+//
+// 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/Analysis/MacroExpansionContext.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/DiagnosticOptions.h"
+#include "clang/Basic/FileManager.h"
+#include "clang/Basic/LangOptions.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Basic/TargetInfo.h"
+#include "clang/Basic/TargetOptions.h"
+#include "clang/Lex/HeaderSearch.h"
+#include "clang/Lex/HeaderSearchOptions.h"
+#include "clang/Lex/Preprocessor.h"
+#include "clang/Lex/PreprocessorOptions.h"
+#include "clang/Parse/Parser.h"
+#include "llvm/ADT/SmallString.h"
+#include "gtest/gtest.h"
+
+// static bool HACK_EnableDebugInUnitTest = (::llvm::DebugFlag = true);
+
+namespace clang {
+namespace analysis {
+namespace {
+
+class MacroExpansionContextTest : public ::testing::Test {
+protected:
+  MacroExpansionContextTest()
+      : InMemoryFileSystem(new llvm::vfs::InMemoryFileSystem),
+        FileMgr(FileSystemOptions(), InMemoryFileSystem),
+        DiagID(new DiagnosticIDs()), DiagOpts(new DiagnosticOptions()),
+        Diags(DiagID, DiagOpts.get(), new IgnoringDiagConsumer()),
+        SourceMgr(Diags, FileMgr), TargetOpts(new TargetOptions()) {
+    TargetOpts->Triple = "x86_64-pc-linux-unknown";
+    Target = TargetInfo::CreateTargetInfo(Diags, TargetOpts);
+    LangOpts.CPlusPlus20 = 1; // For __VA_OPT__
+  }
+
+  IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem;
+  FileManager FileMgr;
+  IntrusiveRefCntPtr<DiagnosticIDs> DiagID;
+  IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts;
+  DiagnosticsEngine Diags;
+  SourceManager SourceMgr;
+  LangOptions LangOpts;
+  std::shared_ptr<TargetOptions> TargetOpts;
+  IntrusiveRefCntPtr<TargetInfo> Target;
+
+  std::unique_ptr<MacroExpansionContext>
+  getMacroExpansionContextFor(StringRef SourceText) {
+    std::unique_ptr<llvm::MemoryBuffer> Buf =
+        llvm::MemoryBuffer::getMemBuffer(SourceText);
+    SourceMgr.setMainFileID(SourceMgr.createFileID(std::move(Buf)));
+    TrivialModuleLoader ModLoader;
+    HeaderSearch HeaderInfo(std::make_shared<HeaderSearchOptions>(), SourceMgr,
+                            Diags, LangOpts, Target.get());
+    Preprocessor PP(std::make_shared<PreprocessorOptions>(), Diags, LangOpts,
+                    SourceMgr, HeaderInfo, ModLoader,
+                    /*IILookup =*/nullptr,
+                    /*OwnsHeaderSearch =*/false);
+
+    PP.Initialize(*Target);
+    auto Ctx = std::make_unique<MacroExpansionContext>(LangOpts);
+    Ctx->registerForPreprocessor(PP);
+
+    // Lex source text.
+    PP.EnterMainSourceFile();
+
+    while (true) {
+      Token Tok;
+      PP.Lex(Tok);
+      if (Tok.is(tok::eof))
+        break;
+    }
+
+    // Callbacks have been executed at this point.
+    return Ctx;
+  }
+
+  /// Returns the expansion location to main file at the given row and column.
+  SourceLocation at(unsigned row, unsigned col) const {
+    SourceLocation Loc =
+        SourceMgr.translateLineCol(SourceMgr.getMainFileID(), row, col);
+    return SourceMgr.getExpansionLoc(Loc);
+  }
+
+  static std::string dumpExpandedTexts(const MacroExpansionContext &Ctx) {
+    std::string Buf;
+    llvm::raw_string_ostream OS{Buf};
+    Ctx.dumpExpandedTextsToStream(OS);
+    return OS.str();
+  }
+
+  static std::string dumpExpansionRanges(const MacroExpansionContext &Ctx) {
+    std::string Buf;
+    llvm::raw_string_ostream OS{Buf};
+    Ctx.dumpExpansionRangesToStream(OS);
+    return OS.str();
+  }
+};
+
+TEST_F(MacroExpansionContextTest, IgnoresPragmas) {
+  // No-crash during lexing.
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  _Pragma("pack(push, 1)")
+  _Pragma("pack(pop, 1)")
+      )code");
+  // After preprocessing:
+  // #pragma pack(push, 1)
+  // #pragma pack(pop, 1)
+
+  EXPECT_EQ("\n=============== ExpandedTokens ===============\n",
+            dumpExpandedTexts(*Ctx));
+  EXPECT_EQ("\n=============== ExpansionRanges ===============\n",
+            dumpExpansionRanges(*Ctx));
+
+  EXPECT_FALSE(Ctx->getExpandedText(at(2, 1)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(2, 1)).hasValue());
+
+  EXPECT_FALSE(Ctx->getExpandedText(at(2, 3)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(2, 3)).hasValue());
+
+  EXPECT_FALSE(Ctx->getExpandedText(at(3, 3)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(3, 3)).hasValue());
+}
+
+TEST_F(MacroExpansionContextTest, NoneForNonExpansionLocations) {
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define EMPTY
+  A b cd EMPTY ef EMPTY gh
+EMPTY zz
+      )code");
+  // After preprocessing:
+  //  A b cd ef gh
+  //      zz
+
+  // That's the beginning of the definition of EMPTY.
+  EXPECT_FALSE(Ctx->getExpandedText(at(2, 11)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(2, 11)).hasValue());
+
+  // The space before the first expansion of EMPTY.
+  EXPECT_FALSE(Ctx->getExpandedText(at(3, 9)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(3, 9)).hasValue());
+
+  // The beginning of the first expansion of EMPTY.
+  EXPECT_TRUE(Ctx->getExpandedText(at(3, 10)).hasValue());
+  EXPECT_TRUE(Ctx->getOriginalText(at(3, 10)).hasValue());
+
+  // Pointing inside of the token EMPTY, but not at the beginning.
+  // FIXME: We only deal with begin locations.
+  EXPECT_FALSE(Ctx->getExpandedText(at(3, 11)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(3, 11)).hasValue());
+
+  // Same here.
+  EXPECT_FALSE(Ctx->getExpandedText(at(3, 12)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(3, 12)).hasValue());
+
+  // The beginning of the last expansion of EMPTY.
+  EXPECT_TRUE(Ctx->getExpandedText(at(4, 1)).hasValue());
+  EXPECT_TRUE(Ctx->getOriginalText(at(4, 1)).hasValue());
+
+  // Same as for the 3:11 case.
+  EXPECT_FALSE(Ctx->getExpandedText(at(4, 2)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(4, 2)).hasValue());
+}
+
+TEST_F(MacroExpansionContextTest, EmptyExpansions) {
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define EMPTY
+  A b cd EMPTY ef EMPTY gh
+EMPTY zz
+      )code");
+  // After preprocessing:
+  //  A b cd ef gh
+  //      zz
+
+  EXPECT_EQ("", Ctx->getExpandedText(at(3, 10)).getValue());
+  EXPECT_EQ("EMPTY", Ctx->getOriginalText(at(3, 10)).getValue());
+
+  EXPECT_EQ("", Ctx->getExpandedText(at(3, 19)).getValue());
+  EXPECT_EQ("EMPTY", Ctx->getOriginalText(at(3, 19)).getValue());
+
+  EXPECT_EQ("", Ctx->getExpandedText(at(4, 1)).getValue());
+  EXPECT_EQ("EMPTY", Ctx->getOriginalText(at(4, 1)).getValue());
+}
+
+TEST_F(MacroExpansionContextTest, TransitiveExpansions) {
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define EMPTY
+  #define WOOF EMPTY ) EMPTY   1
+  A b cd WOOF ef EMPTY gh
+      )code");
+  // After preprocessing:
+  //  A b cd ) 1 ef gh
+
+  EXPECT_EQ("WOOF", Ctx->getOriginalText(at(4, 10)).getValue());
+
+  EXPECT_EQ("", Ctx->getExpandedText(at(4, 18)).getValue());
+  EXPECT_EQ("EMPTY", Ctx->getOriginalText(at(4, 18)).getValue());
+}
+
+TEST_F(MacroExpansionContextTest, MacroFunctions) {
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define EMPTY
+  #define WOOF(x) x(EMPTY ) )  ) EMPTY   1
+  A b cd WOOF($$ ef) EMPTY gh
+  WOOF(WOOF)
+  WOOF(WOOF(bar barr))),,),')
+      )code");
+  // After preprocessing:
+  //  A b cd $$ ef( ) ) ) 1 gh
+  //  WOOF( ) ) ) 1
+  //  bar barr( ) ) ) 1( ) ) ) 1),,),')
+
+  EXPECT_EQ("$$ ef ()))1", Ctx->getExpandedText(at(4, 10)).getValue());
+  EXPECT_EQ("WOOF($$ ef)", Ctx->getOriginalText(at(4, 10)).getValue());
+
+  EXPECT_EQ("", Ctx->getExpandedText(at(4, 22)).getValue());
+  EXPECT_EQ("EMPTY", Ctx->getOriginalText(at(4, 22)).getValue());
+
+  EXPECT_EQ("WOOF ()))1", Ctx->getExpandedText(at(5, 3)).getValue());
+  EXPECT_EQ("WOOF(WOOF)", Ctx->getOriginalText(at(5, 3)).getValue());
+
+  EXPECT_EQ("bar barr ()))1()))1", Ctx->getExpandedText(at(6, 3)).getValue());
+  EXPECT_EQ("WOOF(WOOF(bar barr))", Ctx->getOriginalText(at(6, 3)).getValue());
+}
+
+TEST_F(MacroExpansionContextTest, VariadicMacros) {
+  // From the GCC website.
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define eprintf(format, ...) fprintf (stderr, format, __VA_ARGS__)
+  eprintf("success!\n", );
+  eprintf("success!\n");
+
+  #define eprintf2(format, ...) \
+    fprintf (stderr, format __VA_OPT__(,) __VA_ARGS__)
+  eprintf2("success!\n", );
+  eprintf2("success!\n");
+      )code");
+  // After preprocessing:
+  //  fprintf (stderr, "success!\n", );
+  //  fprintf (stderr, "success!\n", );
+  //  fprintf (stderr, "success!\n" );
+  //  fprintf (stderr, "success!\n" );
+
+  EXPECT_EQ(R"(fprintf (stderr ,"success!\n",))",
+            Ctx->getExpandedText(at(3, 3)).getValue());
+  EXPECT_EQ(R"(eprintf("success!\n", ))",
+            Ctx->getOriginalText(at(3, 3)).getValue());
+
+  EXPECT_EQ(R"(fprintf (stderr ,"success!\n",))",
+            Ctx->getExpandedText(at(4, 3)).getValue());
+  EXPECT_EQ(R"(eprintf("success!\n"))",
+            Ctx->getOriginalText(at(4, 3)).getValue());
+
+  EXPECT_EQ(R"(fprintf (stderr ,"success!\n"))",
+            Ctx->getExpandedText(at(8, 3)).getValue());
+  EXPECT_EQ(R"(eprintf2("success!\n", ))",
+            Ctx->getOriginalText(at(8, 3)).getValue());
+
+  EXPECT_EQ(R"(fprintf (stderr ,"success!\n"))",
+            Ctx->getExpandedText(at(9, 3)).getValue());
+  EXPECT_EQ(R"(eprintf2("success!\n"))",
+            Ctx->getOriginalText(at(9, 3)).getValue());
+}
+
+TEST_F(MacroExpansionContextTest, ConcatenationMacros) {
+  // From the GCC website.
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define COMMAND(NAME)  { #NAME, NAME ## _command }
+  struct command commands[] = {
+    COMMAND(quit),
+    COMMAND(help),
+  };)code");
+  // After preprocessing:
+  //  struct command commands[] = {
+  //    { "quit", quit_command },
+  //    { "help", help_command },
+  //  };
+
+  EXPECT_EQ(R"({"quit",quit_command })",
+            Ctx->getExpandedText(at(4, 5)).getValue());
+  EXPECT_EQ("COMMAND(quit)", Ctx->getOriginalText(at(4, 5)).getValue());
+
+  EXPECT_EQ(R"({"help",help_command })",
+            Ctx->getExpandedText(at(5, 5)).getValue());
+  EXPECT_EQ("COMMAND(help)", Ctx->getOriginalText(at(5, 5)).getValue());
+}
+
+TEST_F(MacroExpansionContextTest, StringizingMacros) {
+  // From the GCC website.
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define WARN_IF(EXP) \
+  do { if (EXP) \
+          fprintf (stderr, "Warning: " #EXP "\n"); } \
+  while (0)
+  WARN_IF (x == 0);
+
+  #define xstr(s) str(s)
+  #define str(s) #s
+  #define foo 4
+  str (foo)
+  xstr (foo)
+      )code");
+  // After preprocessing:
+  //  do { if (x == 0) fprintf (stderr, "Warning: " "x == 0" "\n"); } while (0);
+  //  "foo"
+  //  "4"
+
+  EXPECT_EQ(
+      R"(do {if (x ==0)fprintf (stderr ,"Warning: ""x == 0""\n");}while (0))",
+      Ctx->getExpandedText(at(6, 3)).getValue());
+  EXPECT_EQ("WARN_IF (x == 0)", Ctx->getOriginalText(at(6, 3)).getValue());
+
+  EXPECT_EQ(R"("foo")", Ctx->getExpandedText(at(11, 3)).getValue());
+  EXPECT_EQ("str (foo)", Ctx->getOriginalText(at(11, 3)).getValue());
+
+  EXPECT_EQ(R"("4")", Ctx->getExpandedText(at(12, 3)).getValue());
+  EXPECT_EQ("xstr (foo)", Ctx->getOriginalText(at(12, 3)).getValue());
+}
+
+TEST_F(MacroExpansionContextTest, StringizingVariadicMacros) {
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define xstr(...) str(__VA_ARGS__)
+  #define str(...) #__VA_ARGS__
+  #define RParen2x ) )
+  #define EMPTY
+  #define f(x, ...) __VA_ARGS__ ! x * x
+  #define g(...) zz EMPTY f(__VA_ARGS__ ! x) f() * y
+  #define h(x, G) G(x) G(x ## x RParen2x
+  #define q(G) h(apple, G(apple)) RParen2x
+
+  q(g)
+  q(xstr)
+  g(RParen2x)
+  f( RParen2x )s
+      )code");
+  // clang-format off
+  // After preprocessing:
+  //  zz ! apple ! x * apple ! x ! * * y(apple) zz ! apple ! x * apple ! x ! * * y(appleapple ) ) ) )
+  //  "apple"(apple) "apple"(appleapple ) ) ) )
+  //  zz ! * ) ! x) ! * * y
+  //  ! ) ) * ) )
+  // clang-format on
+
+  EXPECT_EQ("zz !apple !x *apple !x !**y (apple )zz !apple !x *apple !x !**y "
+            "(appleapple ))))",
+            Ctx->getExpandedText(at(11, 3)).getValue());
+  EXPECT_EQ("q(g)", Ctx->getOriginalText(at(11, 3)).getValue());
+
+  EXPECT_EQ(R"res("apple"(apple )"apple"(appleapple )))))res",
+            Ctx->getExpandedText(at(12, 3)).getValue());
+  EXPECT_EQ("q(xstr)", Ctx->getOriginalText(at(12, 3)).getValue());
+
+  EXPECT_EQ("zz !*)!x )!**y ", Ctx->getExpandedText(at(13, 3)).getValue());
+  EXPECT_EQ("g(RParen2x)", Ctx->getOriginalText(at(13, 3)).getValue());
+
+  EXPECT_EQ("!))*))", Ctx->getExpandedText(at(14, 3)).getValue());
+  EXPECT_EQ("f( RParen2x )", Ctx->getOriginalText(at(14, 3)).getValue());
+}
+
+TEST_F(MacroExpansionContextTest, RedefUndef) {
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define Hi(x) Welcome x
+  Hi(Adam)
+  #define Hi Willkommen
+  Hi Hans
+  #undef Hi
+  Hi(Hi)
+      )code");
+  // After preprocessing:
+  //  Welcome Adam
+  //  Willkommen Hans
+  //  Hi(Hi)
+
+  // FIXME: Extra space follows every identifier.
+  EXPECT_EQ("Welcome Adam ", Ctx->getExpandedText(at(3, 3)).getValue());
+  EXPECT_EQ("Hi(Adam)", Ctx->getOriginalText(at(3, 3)).getValue());
+
+  EXPECT_EQ("Willkommen ", Ctx->getExpandedText(at(5, 3)).getValue());
+  EXPECT_EQ("Hi", Ctx->getOriginalText(at(5, 3)).getValue());
+
+  // There was no macro expansion at 7:3, we should expect None.
+  EXPECT_FALSE(Ctx->getExpandedText(at(7, 3)).hasValue());
+  EXPECT_FALSE(Ctx->getOriginalText(at(7, 3)).hasValue());
+}
+
+TEST_F(MacroExpansionContextTest, UnbalacedParenthesis) {
+  const auto Ctx = getMacroExpansionContextFor(R"code(
+  #define retArg(x) x
+  #define retArgUnclosed retArg(fun()
+  #define BB CC
+  #define applyInt BB(int)
+  #define CC(x) retArgUnclosed
+
+  applyInt );
+
+  #define expandArgUnclosedCommaExpr(x) (x, fun(), 1
+  #define f expandArgUnclosedCommaExpr
+
+  int x =  f(f(1))  ));
+      )code");
+  // After preprocessing:
+  //  fun();
+  //  int x = ((1, fun(), 1, fun(), 1 ));
+
+  EXPECT_EQ("fun ()", Ctx->getExpandedText(at(8, 3)).getValue());
+  EXPECT_EQ("applyInt )", Ctx->getOriginalText(at(8, 3)).getValue());
+
+  EXPECT_EQ("((1,fun (),1,fun (),1",
+            Ctx->getExpandedText(at(13, 12)).getValue());
+  EXPECT_EQ("f(f(1))", Ctx->getOriginalText(at(13, 12)).getValue());
+}
+
+} // namespace
+} // namespace analysis
+} // namespace clang