[syntax] Introduce a TokenManager interface.

[hokein]

Summary

The TokenManager defines Token interfaces for the clang syntax-tree. This is level of
abstraction that the syntax-tree should use to operate on Tokens.

It decouples the syntax-tree from a particular token implementation (TokenBuffer
previously). This enables us to use a different underlying token implementation
for the syntax Leaf node -- in clang pseudoparser, we want to produce a
syntax-tree with its own pseudo::Token rather than syntax::Token.

[sammccall]

As discussed offline this has some problems:

• putting virtual methods on BaseToken gives it a vtable, which makes it (and syntax::Token) large
• being able to use ArrayRef<syntax::Token> but not ArrayRef<BaseToken> is a bit weird
• unusual uses of inheritance can be hard to reason about

We suggested rather having Leaf store an opaque ID.
Callers who know what kind of tokens are in use can use this to associate with the original token.
For generic use (e.g dump()), we can have a TokenManager interface which provides the common operations (like getText()). This generalizes where SourceManager is needed today.

[hokein]

Revised to the TokenManager approach:

• Inroduce a Base Token class (TokenManager) for syntax-tree, the motivation is to allow using different underlying token implementation in syntax-tree
• Decouple the syntax-tree from the TokenBuffer:
  • syntax-tree structure (Tree.h) doesn't depend on the TokenBuffer, SourceManager Source location etc, it communicates with TokenManager interfaces;
  • syntax-tree Arena is simpler, the token-managing responsiblity is transferred to TokenManager;
  • in SyntaxTree directory, we implement a TokenBuffer-based SyntaxTokenManager, which mangues all token-related stuff
  • For the mutation/replacement computation APIs, currently they only work on a TokenBuffer-based token manager. Asssertion will be raised if it is not satisfied. It is an NFC change

[hokein]

I'm quite happy about the interfaces now, it should be in a good shape for the API review (would be nice to get some initial feedback before I do further cleanup).

[ilya-biryukov]

clang/include/clang/Tooling/Syntax/TokenManager.h

23 ↗

(On Diff #439705)

NIT: maybe explain the TokenManager concept here, the comment seems to be a leftover from the previous revision.

clang/lib/Tooling/Syntax/Tree.cpp

301

Maybe add TokenManager::getKind(Key) right away and remove this FIXME.
This should as simple as cast<syntax::Token>(T)->Kind, right? Or am I missing some complications?

[ilya-biryukov]

clang/include/clang/Tooling/Syntax/TokenManager.h

33 ↗

(On Diff #439705)

I have just realized that we were discussing having opaque index as a key, but there may also be tokens in the syntax tree that are not backed by the TokenBuffer.
Those can be synthesized, e.g. imagine someone wants to change !(A && B) to !A || !B. They will need to synthesize at least the || token as it's not in the source code. There is a way to do this now and it prohibits the use of an index to the TokenBuffer.

So having the opaque pointer is probably ok for now, it should enable the pseudo-parser to build syntax trees.
We might want to add an operation to synthesize tokens into the TokenManager at some point, but that's a discussion for another day.

[hokein]

clang/include/clang/Tooling/Syntax/TokenManager.h

33 ↗

(On Diff #439705)

Those can be synthesized, e.g. imagine someone wants to change !(A && B) to !A || !B. They will need to synthesize at least the || token as it's not in the source code. There is a way to do this now and it prohibits the use of an index to the TokenBuffer.

Yes, this is the exact reason why the Key is an opaque pointer, my first attempt was to use an index integer, but failed -- we already have some APIs doing this stuff (see createLeaf in BuildTree.h), the token can be a synthesized token backed up by the SourceManager...

Personally, I don't like the Key to be an opaque pointer as well, but considering the effort, it seems to be the best approach so far -- it enables the pseudoparser to build syntax trees with a different Token implementation while keeping the rest syntax stuff unchanged.

We might want to add an operation to synthesize tokens into the TokenManager at some point, but that's a discussion for another day.

Agree, we will encounter this in the future, but we're still far away from there (the layering mutation/syntax-tree is not perfect at the moment, mutation still depends on the TokenBuffer). And our initial application of syntax-tree in pseudoparser focuses on the read use-case, we should be fine now.

clang/lib/Tooling/Syntax/Tree.cpp

301

Yeah, the main problem is that we don't have the TokenManager object in the syntax::Node, we somehow need to pass it (e.g. a function parameter), which seems a heavy change. I'm not sure it is worth for this small assert.

[ilya-biryukov]

clang/lib/Tooling/Syntax/BuildTree.cpp

569

Could we accept a TokenBuffer here directly?
If TokenManager is needed, we can use it directly in the arena.

623

Same suggestion here: accept TokenBuffer instead of TokenManager

clang/lib/Tooling/Syntax/Tree.cpp

301

That makes sense. WDYT about the alternative fix: to pass ̀TokenManager` to assertInvariants?
Not necessary to do it now, just thinking about changing the FIXME

clang/unittests/Tooling/Syntax/TreeTestBase.cpp

112

NIT: it´s not breaking anything now, but I suggest putting SyntaxTokenManager after TokenBuffer.
The reason is that it´s the right destruction order, TokenManager has references to TokenBuffer, so it could potentially access it in destructor some time in the future (e.g. imagine asserting something on tokens).

Not that it actually breaks today, but seems like a potential surprising bug in the future if we happen to refactor code in a certain way.

[sammccall]

clang/include/clang/Tooling/Syntax/TokenManager.h

9 ↗

(On Diff #439705)

It's important that we have comments explaining what the concept is *now*, rather than how it changes the code structure from the previous state (decouples tokenbuffer, enables pseudoparser).

(I think this comment is actually fine, but be careful when writing the class comment for TokenManager)

33 ↗

(On Diff #439705)

Consider uintptr_t instead, which more naturally supports both approaches. (Stashing an integer in a void* is incredibly weird)

37 ↗

(On Diff #439705)

I wouldn't want to prejudge this: this is a very basic attribute similar to kind/role, and we may want to store it in Leaf and avoid the virtual stuff.

There's certainly enough space, e.g. of the current 16-bit kind use the top bit to denote leaf-or-not and the bottom 15 bits to store kind-or-tokenkind.

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

465

conceptually this is just "TokenBuffer implements TokenManager"

The main reason I can see not to actually write that is to avoid the dependency from TokenBuffer (tokens library) to TokenManager (syntax library). But here you've added that dependency anyway.

So I think we'd be better either with TokenBuffer : TokenManager or moving this class to its own header.

467

no need to take SourceManager, TokenBuffer already includes it.
LangOpts is unused here.

477

Empty string seems like the correct return value here to me.
If you want a special case for dump, I think that belongs in dump().

If this is because we currently provide no way to get the token kind, then this should be a FIXME

489

just tokenBuffer(), consistent with TokenBuffer::sourceManager()

492

manager

506

aren't we trying to store these on the syntax arena?
We never do lookups into this map, maybe lexbuffer just allocates storage on the arena('s allocator) instead of using this map?

clang/include/clang/Tooling/Syntax/Tree.h

156

why is this comment removed?

clang/lib/Tooling/Syntax/Tree.cpp

301

per my comment above: Leaf can store the tok::Kind directly and I think it's appropriate to do so.
But maybe fiddly enough that it's worth deferring for one patch

[ilya-biryukov]

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

465

I would argue they should be separate concepts.

• TokenBuffer is about storing tokens and mapping between expanded and spelled token streams.
• SyntaxTokenManager is about implementing relevant certain operations on syntax::Token and hiding the actual token type.

Conceptually those things are different and decoupling them allows for more flexibility and allows reasoning about them independently. In particular, one could imagine having a SyntaxTokenManager without a TokenBuffer if we do not need to deal with two streams of tokens.

I would suggest keeping SyntaxTokenManager as a separate class.

[hokein]

address review comments.

[hokein]

clang/include/clang/Tooling/Syntax/TokenManager.h

37 ↗

(On Diff #439705)

This sounds good. Adjust the FIXME.

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

465

I would suggest keeping SyntaxTokenManager as a separate class.

+1. Moved to a separate file.

467

no need to take SourceManager, TokenBuffer already includes it.

The SourceMgr can be mutated by the class (it stores the underlying tokens for ExtraTokens), while the SourceManager in TokenBuffer is immutable.

LangOpts is unused here.

It is used in SyntaxTokenManager::lexBuffer.

477

Yeah, this special case is for the Leaf node dump. Added a FIXME.

(I even double whether we need this special case at all, do we really want to build a Leaf node for eof token?)

506

aren't we trying to store these on the syntax arena?

We could do that, but I'd try to avoid that. Now the allocator of syntax::Arena is a storage for syntax-tree nodes only. Allocation for token-related stuff is on the SyntaxTokenManager.

We never do lookups into this map, maybe lexbuffer just allocates storage on the arena('s allocator) instead of using this map?

This map is moved from the syntax::Arena.

You're right, there is no usage of the key at the moment, and the only use-case is to create a syntax leaf node that not backed by the source code (for refactoring usecase), it is unclear whether we will use it in the future. I will keep it as-is (this is not the scope of this patch).

clang/unittests/Tooling/Syntax/TreeTestBase.cpp

112

good point!

[sammccall]

clang/include/clang/Tooling/Syntax/Nodes.h

24 ↗

(On Diff #443173)

I think Token and TokenKinds are also no longer needed?

clang/include/clang/Tooling/Syntax/SyntaxTokenManager.h

20 ↗

(On Diff #443173)

I don't think "syntax" in "syntax token manager" is particularly disambiguating here, both TokenBuffer and TokenManager are part of syntax, so it's not clear what it refers to (and it doens't have any obvious plain-english meaning).

Maybe some combination like TokenBufferTokenManager or BufferTokenManager.
In fact I think best is TokenBuffer::TokenManager, still defined in a separate header, though I'm not sure if you think that's too weird.

clang/include/clang/Tooling/Syntax/TokenManager.h

14 ↗

(On Diff #443173)

unclear: different from what? it's not clear what "enables" means if there's no default. Maybe replace the sentence with:

"For example, a TokenBuffer captured from a clang parse may track macro expansions and associate tokens with clang's SourceManager, while a pseudo-parser would use a flat array of raw-lexed tokens in memory."

38 ↗

(On Diff #443173)

This is not a useful comment, either remove it or add more content to make it useful.

In particular the guarantees (or lack thereof) of exactly what this text is would be helpful. (This is some source code that would produce this token, though it may differ from exactly what was spelled in the file when preprocessing is involved)?

clang/include/clang/Tooling/Syntax/Tree.h

9

this is an implementation detail.
At a high level, leaf nodes correspond to tokens. I'd just delete "expanded" from the original comment

65

this is not a helpful comment, just remove it?

clang/lib/Tooling/Syntax/BuildTree.cpp

370

need changes to the public API to make this cast valid

clang/lib/Tooling/Syntax/ComputeReplacements.cpp

89

Need a change to the public interface to guarantee this cast will succeed.
The cleanest would be just to take the SyntaxTokenManager as a param (moving the cast to the call site - I don't think Arena is otherwise used for anything).

Failing that we at least need to update the contract

[hokein]

address comments.

[hokein]

more update

clang/include/clang/Tooling/Syntax/SyntaxTokenManager.h

20 ↗

(On Diff #443173)

Renamed to TokenBufferTokenManager.

BufferTokenManager name is short, but it has BufferToken prefix, which seems confusing with TokenBuffer. TokenBuffer::TokenManager is weird to me, and doesn't reflect the layering IMO

clang/lib/Tooling/Syntax/BuildTree.cpp

370

Are you suggesting to change all public APIs where there is such a cast usage?

If yes, this seems not a trivial change, I think at least we will change all APIs (buildSyntaxTree, createLeaf, createTree, deepCopyExpandingMacros) in BuildTree.h (by adding a new TokenBufferTokenManager parameter).
And the Arena probably doesn't need to have a TokenManager field (it could be simplified as a single BumpPtrAllocator), as the TokenManager is passed in parallel with the Arena.

I'm happy to do the change, but IMO, the current version doesn't seem too bad for me (if we pass an non-SyntaxTokenManager, it will trigger an assertion in debug mode).

clang/lib/Tooling/Syntax/ComputeReplacements.cpp

89

Done, this is a trivial change.

[sammccall]

clang/lib/Tooling/Syntax/BuildTree.cpp

370

Are you suggesting to change all public APIs where there is such a cast usage?

Yes, at the very least they should document the requirement ("this arena must use a TokenBuffer").
An unchecked downcast with no indication on the public API that a specific subclass is required just looks like a bug.

[hokein]

remove all TokenBufferTokenManager cast usage, make it as a contract in the APIs.

[hokein]

update the API changes in clangd part.

[DavidSpickett]

FYI, after this change I get:

/home/david.spickett/llvm-project/clang/include/clang/Tooling/Syntax/TokenBufferTokenManager.h:20:7: warning: 'clang::syntax::TokenBufferTokenManager' has virtual functions but non-virtual destructor [-Wnon-virtual-dtor]
class TokenBufferTokenManager : public TokenManager {
      ^

[hokein]

In D128411#3654452, @DavidSpickett wrote:

FYI, after this change I get:

/home/david.spickett/llvm-project/clang/include/clang/Tooling/Syntax/TokenBufferTokenManager.h:20:7: warning: 'clang::syntax::TokenBufferTokenManager' has virtual functions but non-virtual destructor [-Wnon-virtual-dtor]
class TokenBufferTokenManager : public TokenManager {
      ^

Sorry, it is fixed in 30c2406e270cc5dab8da813ce5c54e4bb8c40e49.

clang/include/clang/Tooling/Syntax/BaseToken.h

+//===- BaseToken.h - base token class for syntax tree ------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines common interfaces for the Token class. The syntax-tree Leaf node
+// points to a single token, this allows using different underlying token
+// implementations (syntax::Token, pseudo::Token) in the syntax-tree.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_BASE_TOKEN_H
+#define LLVM_CLANG_TOOLING_SYNTAX_BASE_TOKEN_H
+
+#include "clang/Basic/TokenKinds.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+namespace syntax {
+
+/// Base class that represents a token for the C++ source code.
+///
+/// Depending on the subclass implementation, it can be a spelled token from
+/// the original source file or an expanded token.
+class BaseToken {
+public:
+  BaseToken(tok::TokenKind K) : Kind(K) {}
+
+  tok::TokenKind kind() const { return Kind; }
+
+  /// Returns the text of the token.
+  virtual llvm::StringRef text(const void *Ctx = nullptr) const = 0;
+
+private:
+  tok::TokenKind Kind;
+};
+
+} // namespace syntax
+} // namespace clang
+
+#endif //  LLVM_CLANG_TOOLING_SYNTAX_BASE_TOKEN_H

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

 #define LLVM_CLANG_TOOLING_SYNTAX_TOKENS_H
 
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Lex/Token.h"
+#include "clang/Tooling/Syntax/BaseToken.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdint>
 #include <tuple>

 };
 
 /// For debugging purposes.
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const FileRange &R);
 
 /// A token coming directly from a file or from a macro invocation. Has just
 /// enough information to locate the token in the source code.
 /// Can represent both expanded and spelled tokens.
-class Token {
+class Token : public BaseToken {
 public:
   Token(SourceLocation Location, unsigned Length, tok::TokenKind Kind);
   /// EXPECTS: clang::Token is not an annotation token.
   explicit Token(const clang::Token &T);
 
-  tok::TokenKind kind() const { return Kind; }
   /// Location of the first character of a token.
   SourceLocation location() const { return Location; }
   /// Location right after the last character of a token.
   SourceLocation endLocation() const {
     return Location.getLocWithOffset(Length);
   }
   unsigned length() const { return Length; }
 
   /// Get the substring covered by the token. Note that will include all
   /// digraphs, newline continuations, etc. E.g. tokens for 'int' and
   ///    in\
   ///    t
   /// both have the same kind tok::kw_int, but results of text() are different.
-  llvm::StringRef text(const SourceManager &SM) const;
+  llvm::StringRef text(const SourceManager& SM) const;
+  /// A wrapper of the above text().
+  /// EXPECTS: The opauqe parameter must be a `const clang::SourceManager*`.
+  llvm::StringRef text(const void* SM) const override;
 
   /// Gets a range of this token.
   /// EXPECTS: token comes from a file, not from a macro expansion.
   FileRange range(const SourceManager &SM) const;
 
   /// Given two tokens inside the same file, returns a file range that starts at
   /// \p First and ends at \p Last.
   /// EXPECTS: First and Last are file tokens from the same file, Last starts
private:
   // FIXME: we only store macro expansions, also add directives(#pragma, etc.)
   PPExpansions Expansions;
   Preprocessor &PP;
   CollectPPExpansions *Collector;
 };
 
 } // namespace syntax
 } // namespace clang
 
 #endif

clang/include/clang/Tooling/Syntax/Tree.h

 //===- Tree.h - structure of the syntax tree ------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 // Defines the basic structure of the syntax tree. There are two kinds of nodes:
 //   - leaf nodes correspond to a token in the expanded token stream,
 //   - tree nodes correspond to language grammar constructs.
 //
 // The tree is initially built from an AST. Each node of a newly built tree
 // covers a continous subrange of expanded tokens (i.e. tokens after
 // preprocessing), the specific tokens coverered are stored in the leaf nodes of
 // a tree. A post-order traversal of a tree will visit leaf nodes in an order
 // corresponding the original order of expanded tokens.
 //
private:
   lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Buffer);
   friend class FactoryImpl;
 
 private:
   SourceManager &SourceMgr;
   const LangOptions &LangOpts;
   const TokenBuffer &Tokens;
   /// IDs and storage for additional tokenized files.
   llvm::DenseMap<FileID, std::vector<Token>> ExtraTokens;
   /// Keeps all the allocated nodes and their intermediate data structures.
   llvm::BumpPtrAllocator Allocator;
 };
 
 class Tree;
 class TreeBuilder;
 class FactoryImpl;
 class MutationsImpl;
public:
   Tree *getParent() { return Parent; }
 
   const Node *getNextSibling() const { return NextSibling; }
   Node *getNextSibling() { return NextSibling; }
   const Node *getPreviousSibling() const { return PreviousSibling; }
   Node *getPreviousSibling() { return PreviousSibling; }
 
   /// Dumps the structure of a subtree. For debugging and testing purposes.
-  std::string dump(const SourceManager &SM) const;
+  std::string dump(const void *SM) const;
   /// Dumps the tokens forming this subtree.
-  std::string dumpTokens(const SourceManager &SM) const;
+  std::string dumpTokens(const void *SM) const;
 
   /// Asserts invariants on this node of the tree and its immediate children.
   /// Will not recurse into the subtree. No-op if NDEBUG is set.
   void assertInvariants() const;
   /// Runs checkInvariants on all nodes in the subtree. No-op if NDEBUG is set.
   void assertInvariantsRecursive() const;
 
 private:
private:
   Node *NextSibling;
   Node *PreviousSibling;
   unsigned Kind : 16;
   unsigned Role : 8;
   unsigned Original : 1;
   unsigned CanModify : 1;
 };
 
-/// A leaf node points to a single token inside the expanded token stream.
+/// A leaf node points to a single token.
 class Leaf final : public Node {
 public:
-  Leaf(const Token *T);
+  Leaf(const BaseToken *T);
   static bool classof(const Node *N);
 
-  const Token *getToken() const { return Tok; }
+  const BaseToken *getToken() const { return Tok; }
+  template <typename T> const T *getTokenAs() const {
+    return static_cast<const T *>(Tok);
+  }
 
 private:
-  const Token *Tok;
+  const BaseToken *Tok;
 };
 
 /// A node that has children and represents a syntactic language construct.
 class Tree : public Node {
   /// Iterator over children (common base for const/non-const).
   /// Not invalidated by tree mutations (holds a stable node pointer).
   template <typename DerivedT, typename NodeT>
   class ChildIteratorBase

clang/lib/Tooling/Syntax/BuildTree.cpp

 ///
 /// Note that all children are expected to be processed when building a node.
 ///
 /// Call finalize() to finish building the tree and consume the root node.
 class syntax::TreeBuilder {
 public:
   TreeBuilder(syntax::Arena &Arena) : Arena(Arena), Pending(Arena) {
     for (const auto &T : Arena.getTokenBuffer().expandedTokens())
       LocationToToken.insert({T.location(), &T});
   }
 
   llvm::BumpPtrAllocator &allocator() { return Arena.getAllocator(); }
   const SourceManager &sourceManager() const {
     return Arena.getSourceManager();
   }
 
   /// Populate children for \p New node, assuming it covers tokens from \p
private:
   /// When created, each tree corresponds to a single token in the file.
   /// Clients call 'foldChildren' to attach one or more subtrees to a parent
   /// node and update the list of trees accordingly.
   ///
   /// Ensures that added nodes properly nest and cover the whole token stream.
   struct Forest {
     Forest(syntax::Arena &A) {
       assert(!A.getTokenBuffer().expandedTokens().empty());
       assert(A.getTokenBuffer().expandedTokens().back().kind() == tok::eof);
       // Create all leaf nodes.
       // Note that we do not have 'eof' in the tree.
       for (const auto &T : A.getTokenBuffer().expandedTokens().drop_back()) {
         auto *L = new (A.getAllocator()) syntax::Leaf(&T);
         L->Original = true;
         L->CanModify = A.getTokenBuffer().spelledForExpanded(T).has_value();
         Trees.insert(Trees.end(), {&T, L});
       }
ArrayRef<syntax::Token> shrinkToFitList(ArrayRef<syntax::Token> Range) {
       auto EndListChildren =
           std::find_if_not(BeginListChildren, EndChildren, BelongsToList);
 
       return ArrayRef<syntax::Token>(BeginListChildren->first,
                                      EndListChildren->first);
     }
 
     /// Add \p Node to the forest and attach child nodes based on \p Tokens.
     void foldChildren(const syntax::Arena &A, ArrayRef<syntax::Token> Tokens,
                       syntax::Tree *Node) {
       // Attach children to `Node`.
       assert(Node->getFirstChild() == nullptr && "node already has children");
 
       auto *FirstToken = Tokens.begin();
       auto BeginChildren = Trees.lower_bound(FirstToken);
 
       assert((BeginChildren == Trees.end() ||
std::string str(const syntax::Arena &A) const {
         unsigned CoveredTokens =
             It != Trees.end()
                 ? (std::next(It)->first - It->first)
                 : A.getTokenBuffer().expandedTokens().end() - It->first;
 
         R += std::string(
             formatv("- '{0}' covers '{1}'+{2} tokens\n", It->second->getKind(),
                     It->first->text(A.getSourceManager()), CoveredTokens));
-        R += It->second->dump(A.getSourceManager());
+        R += It->second->dump(&A.getSourceManager());
       }
       return R;
     }
 
   private:
     /// Maps from the start token to a subtree starting at that token.
     /// Keys in the map are pointers into the array of expanded tokens, so
     /// pointer order corresponds to the order of preprocessor tokens.
buildUserDefinedLiteral(UserDefinedLiteral *S) {
     case UserDefinedLiteral::LOK_Raw:
     case UserDefinedLiteral::LOK_Template:
       // For raw literal operator and numeric literal operator template we
       // cannot get the type of the operand in the semantic AST. We get this
       // information from the token. As integer and floating point have the same
       // token kind, we run `NumericLiteralParser` again to distinguish them.
       auto TokLoc = S->getBeginLoc();
       auto TokSpelling =
-          Builder.findToken(TokLoc)->text(Context.getSourceManager());
+          Builder.findToken(TokLoc)->text(&Context.getSourceManager());
       auto Literal =
           NumericLiteralParser(TokSpelling, TokLoc, Context.getSourceManager(),
                                Context.getLangOpts(), Context.getTargetInfo(),
                                Context.getDiagnostics());
       if (Literal.isIntegerLiteral())
         return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;
       else {
         assert(Literal.isFloatingLiteral());

clang/lib/Tooling/Syntax/ComputeReplacements.cpp

void process(const syntax::Node *N) {
         // Extend the current span.
         ++SpanEnd;
         return;
       }
       // Report the current span to the user.
       if (SpanBegin)
         Callback(llvm::makeArrayRef(SpanBegin, SpanEnd), SpanIsOriginal);
       // Start recording a new span.
-      SpanBegin = L->getToken();
+      SpanBegin = L->getTokenAs<syntax::Token>();
       SpanEnd = SpanBegin + 1;
       SpanIsOriginal = L->isOriginal();
     }
 
     const syntax::Token *SpanBegin;
     const syntax::Token *SpanEnd;
     bool SpanIsOriginal;
     ProcessTokensFn Callback;
syntax::FileRange rangeOfExpanded(const syntax::Arena &A,
   return syntax::Token::range(SM, Spelled->front(), Spelled->back());
 }
 } // namespace
 
 tooling::Replacements
 syntax::computeReplacements(const syntax::Arena &A,
                             const syntax::TranslationUnit &TU) {
   const auto &Buffer = A.getTokenBuffer();
   const auto &SM = A.getSourceManager();
 
   tooling::Replacements Replacements;
   // Text inserted by the replacement we are building now.
   std::string Replacement;
   auto emitReplacement = [&](llvm::ArrayRef<syntax::Token> ReplacedRange) {
     if (ReplacedRange.empty() && Replacement.empty())
       return;
     llvm::cantFail(Replacements.add(tooling::Replacement(

clang/lib/Tooling/Syntax/Synthesis.cpp

 }
 
 syntax::Node *clang::syntax::deepCopyExpandingMacros(syntax::Arena &A,
                                                      const syntax::Node *N) {
   if (const auto *L = dyn_cast<syntax::Leaf>(N))
     // `L->getToken()` gives us the expanded token, thus we implicitly expand
     // any macros here.
     return createLeaf(A, L->getToken()->kind(),
-                      L->getToken()->text(A.getSourceManager()));
+                      L->getToken()->text(&A.getSourceManager()));
 
   const auto *T = cast<syntax::Tree>(N);
   std::vector<std::pair<syntax::Node *, syntax::NodeRole>> Children;
   for (const auto *Child = T->getFirstChild(); Child;
        Child = Child->getNextSibling())
     Children.push_back({deepCopyExpandingMacros(A, Child), Child->getRole()});
 
   return createTree(A, Children, N->getKind());
 }
 
 syntax::EmptyStatement *clang::syntax::createEmptyStatement(syntax::Arena &A) {
   return cast<EmptyStatement>(
       createTree(A, {{createLeaf(A, tok::semi), NodeRole::Unknown}},
                  NodeKind::EmptyStatement));
 }

clang/lib/Tooling/Syntax/Tokens.cpp

SourceRange findCommonRangeForMacroArgs(const syntax::Token &First,
   // the other if they've got different FileIDs.
   return SM.getExpansionRange(CharSourceRange(Res, true)).getAsRange();
 }
 
 } // namespace
 
 syntax::Token::Token(SourceLocation Location, unsigned Length,
                      tok::TokenKind Kind)
-    : Location(Location), Length(Length), Kind(Kind) {
+    : BaseToken(Kind), Location(Location), Length(Length) {
   assert(Location.isValid());
 }
 
 syntax::Token::Token(const clang::Token &T)
     : Token(T.getLocation(), T.getLength(), T.getKind()) {
   assert(!T.isAnnotation());
 }
 
 llvm::StringRef syntax::Token::text(const SourceManager &SM) const {
   bool Invalid = false;
   const char *Start = SM.getCharacterData(location(), &Invalid);
   assert(!Invalid);
   return llvm::StringRef(Start, length());
 }
+llvm::StringRef syntax::Token::text(const void* Ctx) const {
+  const auto* SM = reinterpret_cast<const SourceManager*>(Ctx);
+  return text(*SM);
+}
 
 FileRange syntax::Token::range(const SourceManager &SM) const {
   assert(location().isFileID() && "must be a spelled token");
   FileID File;
   unsigned StartOffset;
   std::tie(File, StartOffset) = SM.getDecomposedLoc(location());
   return FileRange(File, StartOffset, StartOffset + length());
 }

 }
 
 std::string syntax::Token::str() const {
   return std::string(llvm::formatv("Token({0}, length = {1})",
                                    tok::getTokenName(kind()), length()));
 }
 
 std::string syntax::Token::dumpForTests(const SourceManager &SM) const {
-  return std::string(llvm::formatv("Token(`{0}`, {1}, length = {2})", text(SM),
+  return std::string(llvm::formatv("Token(`{0}`, {1}, length = {2})", text(&SM),
                                    tok::getTokenName(kind()), length()));
 }
 
 std::string TokenBuffer::dumpForTests() const {
   auto PrintToken = [this](const syntax::Token &T) -> std::string {
     if (T.kind() == tok::eof)
       return "<eof>";
-    return std::string(T.text(*SourceMgr));
+    return std::string(T.text(SourceMgr));
   };
 
   auto DumpTokens = [this, &PrintToken](llvm::raw_ostream &OS,
                                         llvm::ArrayRef<syntax::Token> Tokens) {
     if (Tokens.empty()) {
       OS << "<empty>";
       return;
     }
-    OS << Tokens[0].text(*SourceMgr);
+    OS << Tokens[0].text(SourceMgr);
     for (unsigned I = 1; I < Tokens.size(); ++I) {
       if (Tokens[I].kind() == tok::eof)
         continue;
       OS << " " << PrintToken(Tokens[I]);
     }
   };
 
   std::string Dump;

clang/lib/Tooling/Syntax/Tree.cpp

 std::pair<FileID, ArrayRef<syntax::Token>>
 syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
   auto FID = SourceMgr.createFileID(std::move(Input));
   auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
   assert(It.second && "duplicate FileID");
   return {FID, It.first->second};
 }
 
-syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
+syntax::Leaf::Leaf(const syntax::BaseToken *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
   assert(Tok != nullptr);
 }
 
 syntax::Node::Node(NodeKind Kind)
     : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
       Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),
       CanModify(false) {
   this->setRole(NodeRole::Detached);
for (auto *N = New; N != nullptr; N = N->NextSibling) {
     N->Parent = this;
   }
   LastInNew->NextSibling = End;
   NewLast = LastInNew;
 }
 
 namespace {
 static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L,
-                     const SourceManager &SM) {
+                     const void* SM) {
   assert(L);
   const auto *Token = L->getToken();
   assert(Token);
   // Handle 'eof' separately, calling text() on it produces an empty string.
   if (Token->kind() == tok::eof)
     OS << "<eof>";
   else
     OS << Token->text(SM);
 }
 
 static void dumpNode(raw_ostream &OS, const syntax::Node *N,
-                     const SourceManager &SM, llvm::BitVector IndentMask) {
+                     const void* SM, llvm::BitVector IndentMask) {
   auto DumpExtraInfo = [&OS](const syntax::Node *N) {
     if (N->getRole() != syntax::NodeRole::Unknown)
       OS << " " << N->getRole();
     if (!N->isOriginal())
       OS << " synthesized";
     if (!N->canModify())
       OS << " unmodifiable";
   };
if (!It.getNextSibling()) {
       IndentMask.push_back(true);
     }
     dumpNode(OS, &It, SM, IndentMask);
     IndentMask.pop_back();
   }
 }
 } // namespace
 
-std::string syntax::Node::dump(const SourceManager &SM) const {
+std::string syntax::Node::dump(const void* SM) const {
   std::string Str;
   llvm::raw_string_ostream OS(Str);
   dumpNode(OS, this, SM, /*IndentMask=*/{});
   return std::move(OS.str());
 }
 
-std::string syntax::Node::dumpTokens(const SourceManager &SM) const {
+std::string syntax::Node::dumpTokens(const void* SM) const {
   std::string Storage;
   llvm::raw_string_ostream OS(Storage);
   traverse(this, [&](const syntax::Node *N) {
     if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
       dumpLeaf(OS, L, SM);
       OS << " ";
     }
   });
#ifndef NDEBUG
   if (!L)
     return;
   for (const Node &C : T->getChildren()) {
     assert(C.getRole() == NodeRole::ListElement ||
            C.getRole() == NodeRole::ListDelimiter);
     if (C.getRole() == NodeRole::ListDelimiter) {
       assert(isa<Leaf>(C));
       assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind());
     }
   }
 
 #endif
 }
 
 void syntax::Node::assertInvariantsRecursive() const {
 #ifndef NDEBUG
   traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });

clang/tools/clang-check/ClangCheck.cpp

public:
       Consumer(clang::CompilerInstance &CI) : Collector(CI.getPreprocessor()) {}
 
       void HandleTranslationUnit(clang::ASTContext &AST) override {
         clang::syntax::TokenBuffer TB = std::move(Collector).consume();
         if (TokensDump)
           llvm::outs() << TB.dumpForTests();
         clang::syntax::Arena A(AST.getSourceManager(), AST.getLangOpts(), TB);
         llvm::outs() << clang::syntax::buildSyntaxTree(A, AST)->dump(
-            AST.getSourceManager());
+            &AST.getSourceManager());
       }
 
     private:
       clang::syntax::TokenCollector Collector;
     };
     return std::make_unique<Consumer>(CI);
   }
 };

clang/unittests/Tooling/Syntax/BuildTreeTest.cpp

 protected:
   ::testing::AssertionResult treeDumpEqual(StringRef Code, StringRef Tree) {
     SCOPED_TRACE(llvm::join(GetParam().getCommandLineArgs(), " "));
 
     auto *Root = buildTree(Code, GetParam());
     auto ErrorOK = errorOK(Code);
     if (!ErrorOK)
       return ErrorOK;
-    auto Actual = StringRef(Root->dump(Arena->getSourceManager())).trim().str();
+    auto Actual = StringRef(Root->dump(&Arena->getSourceManager())).trim().str();
     // EXPECT_EQ shows the diff between the two strings if they are different.
     EXPECT_EQ(Tree.trim().str(), Actual);
     if (Actual != Tree.trim().str()) {
       return ::testing::AssertionFailure();
     }
     return ::testing::AssertionSuccess();
   }
 
if (AnnotatedRanges.size() != TreeDumps.size()) {
                 "different "
                 "to the number of their corresponding tree dumps.";
     }
     bool Failed = false;
     for (unsigned i = 0; i < AnnotatedRanges.size(); i++) {
       auto *AnnotatedNode = nodeByRange(AnnotatedRanges[i], Root);
       assert(AnnotatedNode);
       auto AnnotatedNodeDump =
-          StringRef(AnnotatedNode->dump(Arena->getSourceManager()))
+          StringRef(AnnotatedNode->dump(&Arena->getSourceManager()))
               .trim()
               .str();
       // EXPECT_EQ shows the diff between the two strings if they are different.
       EXPECT_EQ(TreeDumps[i].trim().str(), AnnotatedNodeDump)
           << "Dumps diverged for the code:\n"
           << AnnotatedCode.code().slice(AnnotatedRanges[i].Begin,
                                         AnnotatedRanges[i].End);
       if (AnnotatedNodeDump != TreeDumps[i].trim().str())

clang/unittests/Tooling/Syntax/SynthesisTest.cpp

 
 class SynthesisTest : public SyntaxTreeTest {
 protected:
   ::testing::AssertionResult treeDumpEqual(syntax::Node *Root, StringRef Dump) {
     if (!Root)
       return ::testing::AssertionFailure()
              << "Root was not built successfully.";
 
-    auto Actual = StringRef(Root->dump(Arena->getSourceManager())).trim().str();
+    auto Actual =
+        StringRef(Root->dump(&Arena->getSourceManager())).trim().str();
     auto Expected = Dump.trim().str();
     // EXPECT_EQ shows the diff between the two strings if they are different.
     EXPECT_EQ(Expected, Actual);
     if (Actual != Expected) {
       return ::testing::AssertionFailure();
     }
     return ::testing::AssertionSuccess();
   }
TEST_P(SynthesisTest, DeepCopy_Synthesized) {
   auto *LeafSemiColon = createLeaf(*Arena, tok::semi);
   auto *StatementContinue = createTree(*Arena,
                                        {{LeafContinue, NodeRole::LiteralToken},
                                         {LeafSemiColon, NodeRole::Unknown}},
                                        NodeKind::ContinueStatement);
 
   auto *Copy = deepCopyExpandingMacros(*Arena, StatementContinue);
   EXPECT_TRUE(
-      treeDumpEqual(Copy, StatementContinue->dump(Arena->getSourceManager())));
+      treeDumpEqual(Copy, StatementContinue->dump(&Arena->getSourceManager())));
   // FIXME: Test that copy is independent of original, once the Mutations API is
   // more developed.
 }
 
 TEST_P(SynthesisTest, DeepCopy_Original) {
   auto *OriginalTree = buildTree("int a;", GetParam());
 
   auto *Copy = deepCopyExpandingMacros(*Arena, OriginalTree);

clang/unittests/Tooling/Syntax/TokensTest.cpp

findTokenRange(llvm::StringRef Query, llvm::ArrayRef<syntax::Token> Tokens) {
     llvm::SmallVector<llvm::StringRef, 8> QueryTokens;
     Query.split(QueryTokens, ' ', /*MaxSplit=*/-1, /*KeepEmpty=*/false);
     if (QueryTokens.empty()) {
       ADD_FAILURE() << "will not look for an empty list of tokens";
       std::abort();
     }
     // An equality test for search.
     auto TextMatches = [this](llvm::StringRef Q, const syntax::Token &T) {
-      return Q == T.text(*SourceMgr);
+      return Q == T.text(&*SourceMgr);
     };
     // Find a match.
     auto Found =
         findSubrange(llvm::makeArrayRef(QueryTokens), Tokens, TextMatches);
     if (Found.begin() == Tokens.end()) {
       ADD_FAILURE() << "could not find the subrange for " << Query;
       std::abort();
     }
auto Touching = [&](int Index) {
     SourceLocation Loc = SourceMgr->getComposedLoc(SourceMgr->getMainFileID(),
                                                    Code.points()[Index]);
     return spelledTokensTouching(Loc, Buffer);
   };
   auto Identifier = [&](int Index) {
     SourceLocation Loc = SourceMgr->getComposedLoc(SourceMgr->getMainFileID(),
                                                    Code.points()[Index]);
     const syntax::Token *Tok = spelledIdentifierTouching(Loc, Buffer);
-    return Tok ? Tok->text(*SourceMgr) : "";
+    return Tok ? Tok->text(&*SourceMgr) : "";
   };
 
   EXPECT_THAT(Touching(0), SameRange(findSpelled("int")));
   EXPECT_EQ(Identifier(0), "");
   EXPECT_THAT(Touching(1), SameRange(findSpelled("int")));
   EXPECT_EQ(Identifier(1), "");
   EXPECT_THAT(Touching(2), SameRange(findSpelled("int")));
   EXPECT_EQ(Identifier(2), "");

clang/unittests/Tooling/Syntax/TreeTest.cpp

TEST_F(TreeTest, Iterators) {
   EXPECT_EQ(nullptr, It.asPointer());
   EXPECT_EQ(nullptr, CIt.asPointer());
 }
 
 class ListTest : public SyntaxTreeTest {
 private:
   std::string dumpQuotedTokensOrNull(const Node *N) {
     return N ? "'" +
-                   StringRef(N->dumpTokens(Arena->getSourceManager()))
+                   StringRef(N->dumpTokens(&Arena->getSourceManager()))
                        .trim()
                        .str() +
                    "'"
              : "null";
   }
 
 protected:
   std::string

clang/unittests/Tooling/Syntax/TreeTestBase.cpp

 
 using namespace clang;
 using namespace clang::syntax;
 
 namespace {
 ArrayRef<syntax::Token> tokens(syntax::Node *N) {
   assert(N->isOriginal() && "tokens of modified nodes are not well-defined");
   if (auto *L = dyn_cast<syntax::Leaf>(N))
-    return llvm::makeArrayRef(L->getToken(), 1);
+    return llvm::makeArrayRef(L->getTokenAs<syntax::Token>(), 1);
   auto *T = cast<syntax::Tree>(N);
-  return llvm::makeArrayRef(T->findFirstLeaf()->getToken(),
-                            T->findLastLeaf()->getToken() + 1);
+  return llvm::makeArrayRef(T->findFirstLeaf()->getTokenAs<syntax::Token>(),
+                            T->findLastLeaf()->getTokenAs<syntax::Token>() + 1);
 }
 } // namespace
 
 std::vector<TestClangConfig> clang::syntax::allTestClangConfigs() {
   std::vector<TestClangConfig> all_configs;
   for (TestLanguage lang : {Lang_C89, Lang_C99, Lang_CXX03, Lang_CXX11,
                             Lang_CXX14, Lang_CXX17, Lang_CXX20}) {
     TestClangConfig config;
std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &CI,
       auto Tokens =
           std::make_unique<syntax::TokenCollector>(CI.getPreprocessor());
       return std::make_unique<BuildSyntaxTree>(Root, TB, Arena,
                                                std::move(Tokens));
     }
 
   private:
     syntax::TranslationUnit *&Root;
     std::unique_ptr<syntax::TokenBuffer> &TB;
     std::unique_ptr<syntax::Arena> &Arena;
   };
 
   constexpr const char *FileName = "./input.cpp";
   FS->addFile(FileName, time_t(), llvm::MemoryBuffer::getMemBufferCopy(""));
 
   if (!Diags->getClient())
     Diags->setClient(new TextDiagnosticPrinter(llvm::errs(), DiagOpts.get()));