[clang-format] Enable FormatTokenSource to insert tokens.

[klimek]

Summary

In preparation for configured macro replacements in formatting,
add the ability to insert tokens to FormatTokenSource, and implement
token insertion in IndexedTokenSource.

[sammccall]

Only serious concern is getPreviousToken().

clang/lib/Format/FormatTokenSource.h

81

As I understand it, this parameter is used:

• to provide the initial set of input tokens the source will iterate over
• as a common address space for input + synthesized tokens, to allow the jump mechanism to work
• to make the caller responsible for ownership/lifetime of the synthesized tokens too

This simplifies the implementation, my only problem with this is it seems unusual and confusing.
A comment explaining the roles of this Tokens param would help a bit.

Alternatively you could consider slightly different data structures just for the purpose of making interfaces more obvious: e.g. pass in a BumpPtrAllocator&, allocate scratch tokens there, and use pointers instead of indices (jumps become a ptr->ptr map etc)

102

this no longer seems valid, immediately after calling insertTokens(), Position is at the start of a jump range, and Tokens[Position - 1] will be the EOF at the end of the main stream or previous jump range.

if this is never going to happen, you can detect it (I don't think Tokens[Position - 1] can be EOF in any other way)

123

maybe add a comment that positions don't have meaningful order and this is only useful to restore the position?

(All the callsites look good, it just feels like a trap)

138

nit: move into the LLVM_DEBUG block below? or are you worried about a crash?

159

nit: const

I wasn't sure if this method advanced or not. "successor" might be clearer in this respect

181

DenseMap?

[klimek]

Address reviewer comments.

clang/lib/Format/FormatTokenSource.h

81

Noticing none of this makes sense. We should really just copy the tokens, given that we modify the vector.

102

Added comment in the interface and assert.

123

Added a comment.

[klimek]

Undo changes to ownership of initial set of FormatTokens.

[sammccall]

clang/lib/Format/FormatTokenSource.h

81

Oops, somehow I missed that this was an array of *pointers* and assumed that copying it was no good. This is much better.

clang/lib/Format/UnwrappedLineParser.h

283

I'm not really sure how to read the combination of these two FIXMEs... does it mean "we wanted to do this differently one day, but now we never can"?

Maybe either delete both, or if you think it's still potentially actionable, something like FIXME: it would be better to have tokens created and owned outside because XYZ, but it's hard because macro expansion mutates the stream

(I don't really understand what the prev comment is about: the tokens *are* handed into the UnwrappedLineParser constructor. So I may be off base here)

clang/unittests/Format/FormatTokenSourceTest.cpp

42

nit: parens on (Tok) are redundant given Tok is a local rather than the macro arg

[klimek]

Address review comments.

clang/lib/Format/UnwrappedLineParser.h

283

Yeah, I think I don't fully understand what I wanted to fix, so deleted both.

clang/lib/Format/FormatTokenSource.h

-
 //===--- FormatTokenSource.h - Format C++ code ------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
-/// This file defines the \c TokenSource interface, which provides a token
+/// This file defines the \c FormatTokenSource interface, which provides a token
 /// stream as well as the ability to manipulate the token stream.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_LIB_FORMAT_FORMATTOKENSOURCE_H
 #define LLVM_CLANG_LIB_FORMAT_FORMATTOKENSOURCE_H
 
 #include "FormatToken.h"
 #include "UnwrappedLineParser.h"
+#include "llvm/ADT/DenseMap.h"
 
 #define DEBUG_TYPE "format-token-source"
 
 namespace clang {
 namespace format {
 
+// Navigate a token stream.
+//
+// Enables traversal of a token stream, resetting the position in a token
+// stream, as well as inserting new tokens.
 class FormatTokenSource {
 public:
   virtual ~FormatTokenSource() {}
 
   // Returns the next token in the token stream.
   virtual FormatToken *getNextToken() = 0;
 
   // Returns the token preceding the token returned by the last call to
   // getNextToken() in the token stream, or nullptr if no such token exists.
+  //
+  // Must not be called directly at the position directly after insertTokens()
+  // is called.
   virtual FormatToken *getPreviousToken() = 0;
 
   // Returns the token that would be returned by the next call to
   // getNextToken().
   virtual FormatToken *peekNextToken(bool SkipComment = false) = 0;
 
   // Returns whether we are at the end of the file.
   // This can be different from whether getNextToken() returned an eof token
   // when the FormatTokenSource is a view on a part of the token stream.
   virtual bool isEOF() = 0;
 
   // Gets the current position in the token stream, to be used by setPosition().
+  //
+  // Note that the value of the position is not meaningful, and specifically
+  // should not be used to get relative token positions.
   virtual unsigned getPosition() = 0;
 
   // Resets the token stream to the state it was in when getPosition() returned
   // Position, and return the token at that position in the stream.
   virtual FormatToken *setPosition(unsigned Position) = 0;
+
+  // Insert the given tokens before the current position.
+  // Returns the first token in \c Tokens.
+  // The next returned token will be the second token in \c Tokens.
+  // Requires the last token in Tokens to be EOF; once the EOF token is reached,
+  // the next token will be the last token returned by getNextToken();
+  //
+  // For example, given the token sequence 'a1 a2':
+  // getNextToken() -> a1
+  // insertTokens('b1 b2') -> b1
+  // getNextToken() -> b2
+  // getNextToken() -> a1
+  // getNextToken() -> a2
+  virtual FormatToken *insertTokens(ArrayRef<FormatToken *> Tokens) = 0;
 };
 
-class LLVM_GSL_POINTER IndexedTokenSource : public FormatTokenSource {
+class IndexedTokenSource : public FormatTokenSource {
 public:
   IndexedTokenSource(ArrayRef<FormatToken *> Tokens)
       : Tokens(Tokens), Position(-1) {}
 
   FormatToken *getNextToken() override {
     if (Position >= 0 && isEOF()) {
       LLVM_DEBUG({
         llvm::dbgs() << "Next ";
         dbgToken(Position);
       });
       return Tokens[Position];
     }
-    ++Position;
+    Position = successor(Position);
     LLVM_DEBUG({
       llvm::dbgs() << "Next ";
       dbgToken(Position);
     });
     return Tokens[Position];
   }
 
   FormatToken *getPreviousToken() override {
+    assert(Position <= 0 || !Tokens[Position - 1]->is(tok::eof));
     return Position > 0 ? Tokens[Position - 1] : nullptr;
   }
 
   FormatToken *peekNextToken(bool SkipComment = false) override {
     if (isEOF())
       return Tokens[Position];
-    int Next = Position + 1;
+    int Next = successor(Position);
     if (SkipComment)
       while (Tokens[Next]->is(tok::comment))
-        ++Next;
+        Next = successor(Next);
     LLVM_DEBUG({
       llvm::dbgs() << "Peeking ";
       dbgToken(Next);
     });
     return Tokens[Next];
   }
 
   bool isEOF() override {
     return Position == -1 ? false : Tokens[Position]->is(tok::eof);
   }
 
   unsigned getPosition() override {
     LLVM_DEBUG(llvm::dbgs() << "Getting Position: " << Position << "\n");
     assert(Position >= 0);
     return Position;
   }
 
   FormatToken *setPosition(unsigned P) override {
     LLVM_DEBUG(llvm::dbgs() << "Setting Position: " << P << "\n");
     Position = P;
     return Tokens[Position];
   }
 
+  FormatToken *insertTokens(ArrayRef<FormatToken *> New) override {
+    assert(Position != -1);
+    assert((*New.rbegin())->Tok.is(tok::eof));
+    int Next = Tokens.size();
+    Tokens.append(New.begin(), New.end());
+    LLVM_DEBUG({
+      llvm::dbgs() << "Inserting:\n";
+      for (int I = Next, E = Tokens.size(); I != E; ++I)
+        dbgToken(I, "  ");
+      llvm::dbgs() << "  Jump from: " << (Tokens.size() - 1) << " -> "
+                   << Position << "\n";
+    });
+    Jumps[Tokens.size() - 1] = Position;
+    Position = Next;
+    LLVM_DEBUG({
+      llvm::dbgs() << "At inserted token ";
+      dbgToken(Position);
+    });
+    return Tokens[Position];
+  }
+
   void reset() { Position = -1; }
 
 private:
+  int successor(int Current) const {
+    int Next = Current + 1;
+    auto it = Jumps.find(Next);
+    if (it != Jumps.end()) {
+      Next = it->second;
+      assert(Jumps.find(Next) == Jumps.end());
+    }
+    return Next;
+  }
+
   void dbgToken(int Position, llvm::StringRef Indent = "") {
     FormatToken *Tok = Tokens[Position];
     llvm::dbgs() << Indent << "[" << Position
                  << "] Token: " << Tok->Tok.getName() << " / " << Tok->TokenText
                  << ", Macro: " << !!Tok->MacroCtx << "\n";
   }
 
-  ArrayRef<FormatToken *> Tokens;
+  SmallVector<FormatToken *> Tokens;
   int Position;
+
+  // Maps from position a to position b, so that when we reach a, the token
+  // stream continues at position b instead.
+  llvm::DenseMap<int, int> Jumps;
 };
 
 class ScopedMacroState : public FormatTokenSource {
 public:
   ScopedMacroState(UnwrappedLine &Line, FormatTokenSource *&TokenSource,
                    FormatToken *&ResetToken)
       : Line(Line), TokenSource(TokenSource), ResetToken(ResetToken),
         PreviousLineLevel(Line.Level), PreviousTokenSource(TokenSource),
public:
   unsigned getPosition() override { return PreviousTokenSource->getPosition(); }
 
   FormatToken *setPosition(unsigned Position) override {
     PreviousToken = nullptr;
     Token = PreviousTokenSource->setPosition(Position);
     return Token;
   }
 
+  FormatToken *insertTokens(ArrayRef<FormatToken *> Tokens) override {
+    assert(false && "Cannot insert tokens while parsing a macro.");
+  }
+
 private:
   bool eof() {
     return Token && Token->HasUnescapedNewline &&
            !continuesLineComment(*Token, PreviousToken,
                                  /*MinColumnToken=*/PreviousToken);
   }
 
   FormatToken FakeEOF;

clang/lib/Format/UnwrappedLineParser.h

private:
   const FormatStyle &Style;
   const AdditionalKeywords &Keywords;
 
   llvm::Regex CommentPragmasRegex;
 
   FormatTokenSource *Tokens;
   UnwrappedLineConsumer &Callback;
 
-  // FIXME: This is a temporary measure until we have reworked the ownership
-  // of the format tokens. The goal is to have the actual tokens created and
-  // owned outside of and handed into the UnwrappedLineParser.
   ArrayRef<FormatToken *> AllTokens;
 
   // Keeps a stack of the states of nested control statements (true if the
   // statement contains more than some predefined number of nested statements).
   SmallVector<bool, 8> NestedTooDeep;
 
   // Represents preprocessor branch type, so we can find matching
   // #if/#else/#endif directives.
   enum PPBranchKind {

clang/unittests/Format/FormatTokenSourceTest.cpp

protected:
   }
   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
   std::vector<std::unique_ptr<llvm::MemoryBuffer>> Buffers;
 };
 
 #define EXPECT_TOKEN_KIND(FormatTok, Kind)                                     \
   do {                                                                         \
     FormatToken *Tok = FormatTok;                                              \
-    EXPECT_EQ((Tok)->Tok.getKind(), Kind) << *(Tok);                           \
+    EXPECT_EQ(Tok->Tok.getKind(), Kind) << *Tok;                               \
+  } while (false);
+#define EXPECT_TOKEN_ID(FormatTok, Name)                                       \
+  do {                                                                         \
+    FormatToken *Tok = FormatTok;                                              \
+    EXPECT_EQ(Tok->Tok.getKind(), tok::identifier) << *Tok;                    \
+    EXPECT_EQ(Tok->TokenText, Name) << *Tok;                                   \
   } while (false);
 
 TEST_F(IndexedTokenSourceTest, EmptyInput) {
-  TokenList Tokens = lex("");
-  IndexedTokenSource Source(Tokens);
+  IndexedTokenSource Source(lex(""));
   EXPECT_FALSE(Source.isEOF());
   EXPECT_TOKEN_KIND(Source.getNextToken(), tok::eof);
   EXPECT_TRUE(Source.isEOF());
   EXPECT_TOKEN_KIND(Source.getNextToken(), tok::eof);
   EXPECT_TRUE(Source.isEOF());
   EXPECT_TOKEN_KIND(Source.peekNextToken(/*SkipComment=*/false), tok::eof);
   EXPECT_TOKEN_KIND(Source.peekNextToken(/*SkipComment=*/true), tok::eof);
   EXPECT_EQ(Source.getPreviousToken(), nullptr);
   EXPECT_TRUE(Source.isEOF());
 }
 
 TEST_F(IndexedTokenSourceTest, NavigateTokenStream) {
-  TokenList Tokens = lex("int a;");
-  IndexedTokenSource Source(Tokens);
+  IndexedTokenSource Source(lex("int a;"));
   EXPECT_TOKEN_KIND(Source.peekNextToken(), tok::kw_int);
   EXPECT_TOKEN_KIND(Source.getNextToken(), tok::kw_int);
   EXPECT_EQ(Source.getPreviousToken(), nullptr);
   EXPECT_TOKEN_KIND(Source.peekNextToken(), tok::identifier);
   EXPECT_TOKEN_KIND(Source.getNextToken(), tok::identifier);
   EXPECT_TOKEN_KIND(Source.getPreviousToken(), tok::kw_int);
   EXPECT_TOKEN_KIND(Source.peekNextToken(), tok::semi);
   EXPECT_TOKEN_KIND(Source.getNextToken(), tok::semi);
   EXPECT_TOKEN_KIND(Source.getPreviousToken(), tok::identifier);
   EXPECT_TOKEN_KIND(Source.peekNextToken(), tok::eof);
   EXPECT_TOKEN_KIND(Source.getNextToken(), tok::eof);
   EXPECT_TOKEN_KIND(Source.getPreviousToken(), tok::semi);
+  EXPECT_TOKEN_KIND(Source.getNextToken(), tok::eof);
+  EXPECT_TOKEN_KIND(Source.getPreviousToken(), tok::semi);
 }
 
 TEST_F(IndexedTokenSourceTest, ResetPosition) {
-  TokenList Tokens = lex("int a;");
-  IndexedTokenSource Source(Tokens);
+  IndexedTokenSource Source(lex("int a;"));
   Source.getNextToken();
   unsigned Position = Source.getPosition();
   Source.getNextToken();
   Source.getNextToken();
   EXPECT_TOKEN_KIND(Source.getNextToken(), tok::eof);
   EXPECT_TOKEN_KIND(Source.setPosition(Position), tok::kw_int);
 }
 
+TEST_F(IndexedTokenSourceTest, InsertTokens) {
+  IndexedTokenSource Source(lex("A1 A2"));
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+  EXPECT_TOKEN_ID(Source.insertTokens(lex("B1 B2")), "B1");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "B2");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A2");
+}
+
+TEST_F(IndexedTokenSourceTest, InsertTokensAtEOF) {
+  IndexedTokenSource Source(lex("A1"));
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+  EXPECT_TOKEN_KIND(Source.getNextToken(), tok::eof);
+  EXPECT_TOKEN_ID(Source.insertTokens(lex("B1 B2")), "B1");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "B2");
+  EXPECT_TOKEN_KIND(Source.getNextToken(), tok::eof);
+}
+
+TEST_F(IndexedTokenSourceTest, InsertTokensRecursive) {
+  IndexedTokenSource Source(lex("A1"));
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+  // A1
+  EXPECT_TOKEN_ID(Source.insertTokens(lex("B1")), "B1");
+  // B1 A1
+  EXPECT_TOKEN_ID(Source.insertTokens(lex("C1")), "C1");
+  // C1 B1 A1
+  EXPECT_TOKEN_ID(Source.insertTokens(lex("D1")), "D1");
+  // D1 C1 B1 A1
+  EXPECT_TOKEN_ID(Source.getNextToken(), "C1");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "B1");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+}
+
+TEST_F(IndexedTokenSourceTest, InsertTokensRecursiveAtEndOfSequence) {
+  IndexedTokenSource Source(lex("A1"));
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+  EXPECT_TOKEN_ID(Source.insertTokens(lex("B1")), "B1");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+  EXPECT_TOKEN_ID(Source.insertTokens(lex("C1")), "C1");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+  EXPECT_TOKEN_ID(Source.insertTokens(lex("D1")), "D1");
+  EXPECT_TOKEN_ID(Source.getNextToken(), "A1");
+}
+
 } // namespace
 } // namespace format
 } // namespace clang