[Preprocessor] Fix assertion in AnnotatePreviousCachedTokens

[bruno]

Summary

Consider the following ObjC++ snippet:

@protocol PA;
@protocol PB;

@class NSArray<ObjectType>;
typedef int some_t;

id<PA> FA(NSArray<id<PB>> *h, some_t group);

This would hit an assertion in the parser after generating an annotation token while
trying to update the token cache:

Assertion failed: (CachedTokens[CachedLexPos-1].getLastLoc() == Tok.getAnnotationEndLoc() && "The annotation should be until the most recent cached token")
...
7 clang::Preprocessor::AnnotatePreviousCachedTokens(clang::Token const&) + 494
8 clang::Parser::TryAnnotateTypeOrScopeTokenAfterScopeSpec(bool, bool, clang::CXXScopeSpec&, bool) + 1163
9 clang::Parser::TryAnnotateTypeOrScopeToken(bool, bool) + 361
10 clang::Parser::isCXXDeclarationSpecifier(clang::Parser::TPResult, bool*) + 598
...

The cached preprocessor token in this case is:

greatergreater '>>' Loc=<testcase.mm:7:24>

while the annotation ("NSArray<id<PB>>") ends at "testcase.mm:7:25", hence the assertion.
The mismatch only happens because of the cached token length and the assertion should account for that.

[bruno]

Ping!

[akyrtzi]

Hi Bruno,

[bruno]

Hi Argyrios,

Thanks for the suggestions, will apply them.
The assertion seems important to catch subtle bugs, are you sure it should be placed inside a "#ifndef NDEBUG”?

[bruno]

Thanks Duncan and Argyrios, updated a patch with the suggestions!

[bruno]

Ping!

[akyrtzi]

LGTM.

[rsmith]

I think that this will leave us with a broken token stream. In your example, the cached token stream starts as

NSArray < id < PB >> * [...]

... and we try to annotate the id<PB> with our CachedLexPos pointing at the * token. That leaves CachedTokens containing:

NSArray < (type annotation) * [...]

... which is wrong. We need to actually convert the tok::greatergreater in CachedTokens into a tok::greater and update its location and length in order for the cached token stream to be correctly updated. Otherwise if the parser backtracks it will see the wrong token stream.

lib/Lex/PPCaching.cpp

103–105

Please add braces inside this #ifndef block so these variables don't accidentally leak into the rest of the function.

109

that cases -> that case

110

Please only do this extra work if CachedLastTokLoc != TokAnnEndLoc.

[bruno]

Hi Richard,

Thanks for the comments. Updated the patch!

In D15173#313235, @rsmith wrote:

I think that this will leave us with a broken token stream. In your example, the cached token stream starts as

NSArray < id < PB >> * [...]

... and we try to annotate the id<PB> with our CachedLexPos pointing at the * token. That leaves CachedTokens containing:

NSArray < (type annotation) * [...]

... which is wrong. We need to actually convert the tok::greatergreater in CachedTokens into a tok::greater and update its location and length in order for the cached token stream to be correctly updated. Otherwise if the parser backtracks it will see the wrong token stream.

I don't think this happens, the type annotation starts at 7:11 and ends at 7:24:
identifier 'NSArray' Loc=<testcase.mm:7:11>
greatergreater '>>' Loc=<testcase.mm:7:24>

The code that follows the assert then patches the CachedTokens the correct way, see the CachedTokens before and after:

• Before:

(clang::Preprocessor::CachedTokensTy) $32 = {

[0] = (Loc = 89, UintData = 1, PtrData = 0x0000000000000000, Kind = l_paren, Flags = 0)
[1] = (Loc = 90, UintData = 7, PtrData = 0x000000010d82fba0, Kind = identifier, Flags = 0)
[2] = (Loc = 97, UintData = 1, PtrData = 0x0000000000000000, Kind = less, Flags = 0)
[3] = (Loc = 98, UintData = 2, PtrData = 0x000000010d01da58, Kind = identifier, Flags = 0)
[4] = (Loc = 100, UintData = 1, PtrData = 0x0000000000000000, Kind = less, Flags = 0)
[5] = (Loc = 101, UintData = 2, PtrData = 0x000000010d82fb70, Kind = identifier, Flags = 0)
[6] = (Loc = 103, UintData = 2, PtrData = 0x0000000000000000, Kind = greatergreater, Flags = 0)
[7] = (Loc = 106, UintData = 1, PtrData = 0x0000000000000000, Kind = star, Flags = 2)

}

• After:

(clang::Preprocessor::CachedTokensTy) $34 = {

[0] = (Loc = 89, UintData = 1, PtrData = 0x0000000000000000, Kind = l_paren, Flags = 0)
[1] = (Loc = 90, UintData = 104, PtrData = 0x000000010d820660, Kind = annot_typename, Flags = 0)
[2] = (Loc = 106, UintData = 1, PtrData = 0x0000000000000000, Kind = star, Flags = 2)

}

[bruno]

Hi Richard,

Thanks for the detailed explanation, it now makes sense to me. I updated the patch with another approach! Let me know if it's the right direction.

[bruno]

Ping!

[bruno]

Ping :-)

[bruno]

Update patch after Richard comments

[bruno]

Ping!

[bruno]

Update the patch to use ArrayRef and remove a misleading assertion.
Richard, any more comments regarding this approach?

Thanks,

[doug.gregor]

This approach looks great to me.

[bruno]

Thanks,

Committed r259311!

include/clang/Lex/Preprocessor.h

public:
 
   /// Get the location of the last cached token, suitable for setting the end
   /// location of an annotation token.
   SourceLocation getLastCachedTokenLocation() const {
     assert(CachedLexPos != 0);
     return CachedTokens[CachedLexPos-1].getLastLoc();
   }
 
+  /// \brief Whether \p Tok is the most recent token (`CachedLexPos - 1`) in
+  /// CachedTokens.
+  bool IsPreviousCachedToken(const Token &Tok) const;
+
+  /// \brief Replace token in `CachedLexPos - 1` in CachedTokens by the tokens
+  /// in \p NewToks.
+  ///
+  /// Useful when a token needs to be split in smaller ones and CachedTokens
+  /// most recent token must to be updated to reflect that.
+  void ReplacePreviousCachedToken(ArrayRef<Token> NewToks);
+
   /// \brief Replace the last token with an annotation token.
   ///
   /// Like AnnotateCachedTokens(), this routine replaces an
   /// already-parsed (and resolved) token with an annotation
   /// token. However, this routine only replaces the last token with
   /// the annotation token; it does not affect any other cached
   /// tokens. This function has no effect if backtracking is not
   /// enabled.

lib/Lex/PPCaching.cpp

 }
 
 void Preprocessor::AnnotatePreviousCachedTokens(const Token &Tok) {
   assert(Tok.isAnnotation() && "Expected annotation token");
   assert(CachedLexPos != 0 && "Expected to have some cached tokens");
   assert(CachedTokens[CachedLexPos-1].getLastLoc() == Tok.getAnnotationEndLoc()
          && "The annotation should be until the most recent cached token");
 
   // Start from the end of the cached tokens list and look for the token
   // that is the beginning of the annotation token.
   for (CachedTokensTy::size_type i = CachedLexPos; i != 0; --i) {
     CachedTokensTy::iterator AnnotBegin = CachedTokens.begin() + i-1;
     if (AnnotBegin->getLocation() == Tok.getLocation()) {
       assert((BacktrackPositions.empty() || BacktrackPositions.back() < i) &&
              "The backtrack pos points inside the annotated tokens!");
       // Replace the cached tokens with the single annotation token.
       if (i < CachedLexPos)
         CachedTokens.erase(AnnotBegin + 1, CachedTokens.begin() + CachedLexPos);
       *AnnotBegin = Tok;
       CachedLexPos = i;
       return;
     }
   }
 }
+
+bool Preprocessor::IsPreviousCachedToken(const Token &Tok) const {
+  // There's currently no cached token...
+  if (!CachedLexPos)
+    return false;
+
+  const Token LastCachedTok = CachedTokens[CachedLexPos - 1];
+  if (LastCachedTok.getKind() != Tok.getKind())
+    return false;
+
+  int RelOffset = 0;
+  if ((!getSourceManager().isInSameSLocAddrSpace(
+          Tok.getLocation(), getLastCachedTokenLocation(), &RelOffset)) ||
+      RelOffset)
+    return false;
+
+  return true;
+}
+
+void Preprocessor::ReplacePreviousCachedToken(ArrayRef<Token> NewToks) {
+  assert(CachedLexPos != 0 && "Expected to have some cached tokens");
+  CachedTokens.insert(CachedTokens.begin() + CachedLexPos - 1, NewToks.begin(),
+                      NewToks.end());
+  CachedTokens.erase(CachedTokens.begin() + CachedLexPos - 1 + NewToks.size());
+  CachedLexPos += NewToks.size() - 1;
+}

lib/Parse/ParseTemplate.cpp

if (getLangOpts().CPlusPlus11 &&
         (Tok.is(tok::greatergreater) || Tok.is(tok::greatergreatergreater)))
       DiagId = diag::warn_cxx98_compat_two_right_angle_brackets;
     else if (Tok.is(tok::greaterequal))
       DiagId = diag::err_right_angle_bracket_equal_needs_space;
     Diag(Tok.getLocation(), DiagId) << Hint1 << Hint2;
   }
 
   // Strip the initial '>' from the token.
+  Token PrevTok = Tok;
   if (RemainingToken == tok::equal && Next.is(tok::equal) &&
       areTokensAdjacent(Tok, Next)) {
     // Join two adjacent '=' tokens into one, for cases like:
     //   void (*p)() = f<int>;
     //   return f<int>==p;
     ConsumeToken();
     Tok.setKind(tok::equalequal);
     Tok.setLength(Tok.getLength() + 1);
   } else {
     Tok.setKind(RemainingToken);
     Tok.setLength(Tok.getLength() - 1);
   }
   Tok.setLocation(Lexer::AdvanceToTokenCharacter(RAngleLoc, 1,
                                                  PP.getSourceManager(),
                                                  getLangOpts()));
 
+  // The advance from '>>' to '>' in a ObjectiveC template argument list needs
+  // to be properly reflected in the token cache to allow correct interaction
+  // between annotation and backtracking.
+  if (ObjCGenericList && PrevTok.getKind() == tok::greatergreater &&
+      RemainingToken == tok::greater && PP.IsPreviousCachedToken(PrevTok)) {
+    PrevTok.setKind(RemainingToken);
+    PrevTok.setLength(1);
+    Token NewToks[] = {PrevTok, Tok};
+    PP.ReplacePreviousCachedToken(NewToks);
+  }
+
   if (!ConsumeLastToken) {
     // Since we're not supposed to consume the '>' token, we need to push
     // this token and revert the current token back to the '>'.
     PP.EnterToken(Tok);
     Tok.setKind(tok::greater);
     Tok.setLength(1);
     Tok.setLocation(RAngleLoc);
   }

test/Parser/objcxx11-protocol-in-template.mm

 // RUN: %clang_cc1 -fsyntax-only -verify %s
 // RUN: %clang_cc1 -fsyntax-only -verify -std=c++11 %s
 
 template<class T> class vector {};
 @protocol P @end
 
 // expected-no-diagnostics
 
 vector<id<P>> v;
 vector<vector<id<P>>> v2;
+
+@protocol PA;
+@protocol PB;
+
+@class NSArray<ObjectType>;
+typedef int some_t;
+
+id<PA> FA(NSArray<id<PB>> *h, some_t group);