Fix crash on `user defined literals`

[eduucaldas]

Summary

Given an UserDefinedLiteral 1.2_w:
Problem: Lexer generates one Token for the literal, but ClangAST
references two source locations
Fix: Ignore the operator and interpret it as the underlying literal.
e.g.: 1.2_w token generates syntax node IntegerLiteral(1.2_w)

[eduucaldas]

Why does this work?

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

718

This comment makes sense, but it is not clear how it is connected to the implementation. Could you clarify? Also, could you re-wrap the comment to 80 columns? Where exactly in the AST do we have the source location that points to _w? What are we doing to avoid using that source location?

[eduucaldas]

Reflect fix on RecursiveASTVisitor

[gribozavr2]

Fix crash on user defined literals

WDYT:

Implement support for user defined literals (which also fixes a crash)

Given an UserDefinedLiteral 1.2_w:
Problem: Lexer generates one Token for the literal, but ClangAST
references two source locations
Fix: Ignore the operator and interpret it as the underlying literal.
e.g.: 1.2_w token generates syntax node IntegerLiteral(1.2_w)

WDYT:

A user defined literal (for example, 1.2_w) is one token. The Clang AST for a user defined literal references two source locations: the beginning of the token (the location of 1 in 1.2_w) and the beginning of the suffix (the location of _). When constructing the syntax tree, we were trying to find a token that starts at the underscore, but couldn't find one, and crashed on an assertion failure. To fix this issue, we ignore the Clang AST nodes for UDLs that have source locations that point in the middle of a token.

clang/lib/Tooling/Syntax/BuildTree.cpp

716

"The semantic AST node for has child nodes that reference two source locations, the location of the beginning of the token (1), and the location of the beginning of the UDL suffix (_). The UDL suffix location does not point to the beginning of a token, so we can't represent the UDL suffix as a separate syntax tree node."

clang/unittests/Tooling/Syntax/TreeTest.cpp

1197–1199

Indent -2.

1200

Could you also add tests for user-defined string literals and user-defined character literals? ("abc"_mystr, u"abc"_mystr, 'c'_mychar)

1265

It looks somewhat weird to me that integer and floating point literals end up with the same syntax tree node type. WDYT about making different nodes for different literals (integer, floating-point, string, character)?

[eduucaldas]

clang/unittests/Tooling/Syntax/TreeTest.cpp

1265

Makes sense. Let's follow the grammar then.

[eduucaldas]

Add support for {Integer,Float,Char,String}UserDefinedLiteral

[eduucaldas]

workaround size_t

[eduucaldas]

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

347–357

This is gonna be removed once we are able to distinguish between integer and float on raw and template UDL

clang/lib/Tooling/Syntax/BuildTree.cpp

219–221

I know it adds noise, but this is the only place where the formatting doesn't obey the llvm clang format.

733

Here we need logic to determine which kind of UDL, if float or integer

clang/unittests/Tooling/Syntax/TreeTest.cpp

1311–1313

For raw and template UDL, we don't know yet how to get the information about integer of float

[eduucaldas]

Polishing patch

clang/lib/Tooling/Syntax/BuildTree.cpp

716

I changed your comment slightly, WDYT

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

716

LGTM!

[eduucaldas]

Document proposed solution for treating raw literal operators and numeric template operators

[eduucaldas]

Add support for integer and floating UDL even for raw literal operator and
numeric literal operator template

[eduucaldas]

nothing

[eduucaldas]

clang/lib/Tooling/Syntax/BuildTree.cpp

713

Not sure if text is the right thing to get a TokenSpelling from a syntax::Token

[eduucaldas]

Nothing

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

736

Please use parentheses to call the constructor. Braces are correct, but not idiomatic in LLVM.

753

Please allocate an instance of the correct derived type. It is undefined behavior to downcast an object allocated as UserDefinedLiteralExpression to any of its subtypes.

clang/unittests/Tooling/Syntax/TreeTest.cpp

1197

No need to explain the language.

1200

No need to explain the language.

1210

call -> calls? (as in, "this expression calls ...")

1336

I don't understand why this test is separate from the previous one -- why not merge them all into one, or split all of them into one call per test?

1339

ditto, "calls"

Also please add a space before "//".

[eduucaldas]

Use right function to get TokSpelling, answer comments

clang/unittests/Tooling/Syntax/TreeTest.cpp

1210

it is a noun here, as kind is.

[eduucaldas]

clang/lib/Tooling/Syntax/BuildTree.cpp

722

b or B? Should I use camelCase or TitleCase?

734–750

I'll write a comment explaining why this crazyness. Promise not to rant about the lexer that doesn't distinguish between float and integer.

737–739

This is exactly the function used by the parser to get the TokSpelling. see: llvm-project/clang/lib/Sema/SemaExpr.cpp:3633

[eduucaldas]

• Add comment explaining complication on LOK_Raw and LOK_Template
• Use FileRange::text instead of Lexer::getSpelling

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

748

... else { assert(Literal.isFloatingLiteral()); return new ... }

[eduucaldas]

Add assert

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

enum class NodeKind : uint16_t {
   BinaryOperatorExpression,
   ParenExpression,
   IntegerLiteralExpression,
   CharacterLiteralExpression,
   FloatingLiteralExpression,
   StringLiteralExpression,
   BoolLiteralExpression,
   CxxNullPtrExpression,
+  UnknownUserDefinedLiteralExpression,
+  IntegerUserDefinedLiteralExpression,
+  FloatUserDefinedLiteralExpression,
+  CharUserDefinedLiteralExpression,
+  StringUserDefinedLiteralExpression,
   IdExpression,
 
   // Statements.
   UnknownStatement,
   DeclarationStatement,
   EmptyStatement,
   SwitchStatement,
   CaseStatement,

 public:
   CxxNullPtrExpression() : Expression(NodeKind::CxxNullPtrExpression) {}
   static bool classof(const Node *N) {
     return N->kind() == NodeKind::CxxNullPtrExpression;
   }
   syntax::Leaf *nullPtrKeyword();
 };
 
+/// Expression for user-defined literal. C++ [lex.ext]
+/// user-defined-literal:
+///   user-defined-integer-literal
+///   user-defined-floating-point-literal
+///   user-defined-string-literal
+///   user-defined-character-literal
+class UserDefinedLiteralExpression : public Expression {
+public:
+  UserDefinedLiteralExpression(NodeKind K) : Expression(K) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::UnknownUserDefinedLiteralExpression ||
+           N->kind() == NodeKind::IntegerUserDefinedLiteralExpression ||
+           N->kind() == NodeKind::FloatUserDefinedLiteralExpression ||
+           N->kind() == NodeKind::CharUserDefinedLiteralExpression ||
+           N->kind() == NodeKind::StringUserDefinedLiteralExpression;
+  }
+  syntax::Leaf *literalToken();
+};
+
+// We cannot yet distinguish between user-defined-integer-literal and
+// user-defined-floating-point-literal, when using raw literal operator or
+// numeric literal operator. C++ [lex.ext]p3, p4
+/// Expression for an unknown user-defined-literal.
+class UnknownUserDefinedLiteralExpression final
+    : public UserDefinedLiteralExpression {
+public:
+  UnknownUserDefinedLiteralExpression()
+      : UserDefinedLiteralExpression(
+            NodeKind::UnknownUserDefinedLiteralExpression) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::UnknownUserDefinedLiteralExpression;
+  }
+};
+
+/// Expression for user-defined-integer-literal. C++ [lex.ext]
+class IntegerUserDefinedLiteralExpression final
+    : public UserDefinedLiteralExpression {
+public:
+  IntegerUserDefinedLiteralExpression()
+      : UserDefinedLiteralExpression(
+            NodeKind::IntegerUserDefinedLiteralExpression) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::IntegerUserDefinedLiteralExpression;
+  }
+};
+
+/// Expression for user-defined-floating-point-literal. C++ [lex.ext]
+class FloatUserDefinedLiteralExpression final
+    : public UserDefinedLiteralExpression {
+public:
+  FloatUserDefinedLiteralExpression()
+      : UserDefinedLiteralExpression(
+            NodeKind::FloatUserDefinedLiteralExpression) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::FloatUserDefinedLiteralExpression;
+  }
+};
+
+/// Expression for user-defined-character-literal. C++ [lex.ext]
+class CharUserDefinedLiteralExpression final
+    : public UserDefinedLiteralExpression {
+public:
+  CharUserDefinedLiteralExpression()
+      : UserDefinedLiteralExpression(
+            NodeKind::CharUserDefinedLiteralExpression) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::CharUserDefinedLiteralExpression;
+  }
+};
+
+/// Expression for user-defined-string-literal. C++ [lex.ext]
+class StringUserDefinedLiteralExpression final
+    : public UserDefinedLiteralExpression {
+public:
+  StringUserDefinedLiteralExpression()
+      : UserDefinedLiteralExpression(
+            NodeKind::StringUserDefinedLiteralExpression) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::StringUserDefinedLiteralExpression;
+  }
+};
+
 /// An abstract class for prefix and postfix unary operators.
 class UnaryOperatorExpression : public Expression {
 public:
   UnaryOperatorExpression(NodeKind K) : Expression(K) {}
   static bool classof(const Node *N) {
     return N->kind() == NodeKind::PrefixUnaryOperatorExpression ||
            N->kind() == NodeKind::PostfixUnaryOperatorExpression;
   }

clang/lib/Tooling/Syntax/BuildTree.cpp

static SourceRange getDeclaratorRange(const SourceManager &SM, TypeLoc T,
   if (Name.isValid()) {
     if (Start.isInvalid())
       Start = Name;
     if (SM.isBeforeInTranslationUnit(End, Name))
       End = Name;
   }
   if (Initializer.isValid()) {
     auto InitializerEnd = Initializer.getEnd();
-    assert(SM.isBeforeInTranslationUnit(End, InitializerEnd) || End == InitializerEnd);
+    assert(SM.isBeforeInTranslationUnit(End, InitializerEnd) ||
+           End == InitializerEnd);
     End = InitializerEnd;
   }
   return SourceRange(Start, End);
 }
 
 namespace {
 /// All AST hierarchy roots that can be represented as pointers.
 using ASTPtr = llvm::PointerUnion<Stmt *, Decl *>;
 /// Maintains a mapping from AST to syntax tree nodes. This class will get more
for (auto it = QualifierLoc; it; it = it.getPrefix()) {
       Builder.markChild(NS, syntax::NodeRole::NestedNameSpecifier_specifier);
     }
     auto *NNS = new (allocator()) syntax::NestedNameSpecifier;
     Builder.foldNode(Builder.getRange(QualifierLoc.getSourceRange()), NNS,
                      nullptr);
     return NNS;
   }
 
+  bool TraverseUserDefinedLiteral(UserDefinedLiteral *S) {
+    // The semantic AST node `UserDefinedLiteral` (UDL) may have one child node
+    // referencing the location of the UDL suffix (`_w` in `1.2_w`). The
+    // UDL suffix location does not point to the beginning of a token, so we
+    // can't represent the UDL suffix as a separate syntax tree node.
+
+    return WalkUpFromUserDefinedLiteral(S);
+  }
+
+  syntax::NodeKind getUserDefinedLiteralKind(UserDefinedLiteral *S) {
+    switch (S->getLiteralOperatorKind()) {
+    case clang::UserDefinedLiteral::LOK_Integer:
+      return syntax::NodeKind::IntegerUserDefinedLiteralExpression;
+    case clang::UserDefinedLiteral::LOK_Floating:
+      return syntax::NodeKind::FloatUserDefinedLiteralExpression;
+    case clang::UserDefinedLiteral::LOK_Character:
+      return syntax::NodeKind::CharUserDefinedLiteralExpression;
+    case clang::UserDefinedLiteral::LOK_String:
+      return syntax::NodeKind::StringUserDefinedLiteralExpression;
+    case clang::UserDefinedLiteral::LOK_Raw:
+    case clang::UserDefinedLiteral::LOK_Template:
+      // FIXME: Apply `NumericLiteralParser` to the underlying token to deduce
+      // the right UDL kind. That would require a `Preprocessor` though.
+      return syntax::NodeKind::UnknownUserDefinedLiteralExpression;
+    }
+  }
+
+  bool WalkUpFromUserDefinedLiteral(UserDefinedLiteral *S) {
+    Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);
+    Builder.foldNode(Builder.getExprRange(S),
+                     new (allocator()) syntax::UserDefinedLiteralExpression(
+                         getUserDefinedLiteralKind(S)),
+                     S);
+    return true;
+  }
+
   bool WalkUpFromDeclRefExpr(DeclRefExpr *S) {
     if (auto *NNS = BuildNestedNameSpecifier(S->getQualifierLoc()))
       Builder.markChild(NNS, syntax::NodeRole::IdExpression_qualifier);
 
     auto *unqualifiedId = new (allocator()) syntax::UnqualifiedId;
     // Get `UnqualifiedId` from `DeclRefExpr`.
     // FIXME: Extract this logic so that it can be used by `MemberExpr`,
     // and other semantic constructs, now it is tied to `DeclRefExpr`.
     if (!S->hasExplicitTemplateArgs()) {
       Builder.foldNode(Builder.getRange(S->getNameInfo().getSourceRange()),
                        unqualifiedId, nullptr);
     } else {
       auto templateIdSourceRange =
           SourceRange(S->getNameInfo().getBeginLoc(), S->getRAngleLoc());
bool WalkUpFromBinaryOperator(BinaryOperator *S) {
     Builder.foldNode(Builder.getExprRange(S),
                      new (allocator()) syntax::BinaryOperatorExpression, S);
     return true;
   }
 
   bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *S) {
     if (getOperatorNodeKind(*S) ==
         syntax::NodeKind::PostfixUnaryOperatorExpression) {
-      // A postfix unary operator is declared as taking two operands. The second
-      // operand is used to distinguish from its prefix counterpart. In the
-      // semantic AST this "phantom" operand is represented as a
+      // A postfix unary operator is declared as taking two operands. The
+      // second operand is used to distinguish from its prefix counterpart. In
+      // the semantic AST this "phantom" operand is represented as a
       // `IntegerLiteral` with invalid `SourceLocation`. We skip visiting this
       // operand because it does not correspond to anything written in source
       // code
       for (auto *child : S->children()) {
         if (child->getSourceRange().isInvalid())
           continue;
         if (!TraverseStmt(child))
           return false;

clang/lib/Tooling/Syntax/Nodes.cpp

llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeKind K) {
   case NodeKind::FloatingLiteralExpression:
     return OS << "FloatingLiteralExpression";
   case NodeKind::StringLiteralExpression:
     return OS << "StringLiteralExpression";
   case NodeKind::BoolLiteralExpression:
     return OS << "BoolLiteralExpression";
   case NodeKind::CxxNullPtrExpression:
     return OS << "CxxNullPtrExpression";
+  case NodeKind::UnknownUserDefinedLiteralExpression:
+    return OS << "UnknownUserDefinedLiteralExpression";
+  case NodeKind::IntegerUserDefinedLiteralExpression:
+    return OS << "IntegerUserDefinedLiteralExpression";
+  case NodeKind::FloatUserDefinedLiteralExpression:
+    return OS << "FloatUserDefinedLiteralExpression";
+  case NodeKind::CharUserDefinedLiteralExpression:
+    return OS << "CharUserDefinedLiteralExpression";
+  case NodeKind::StringUserDefinedLiteralExpression:
+    return OS << "StringUserDefinedLiteralExpression";
   case NodeKind::PrefixUnaryOperatorExpression:
     return OS << "PrefixUnaryOperatorExpression";
   case NodeKind::PostfixUnaryOperatorExpression:
     return OS << "PostfixUnaryOperatorExpression";
   case NodeKind::BinaryOperatorExpression:
     return OS << "BinaryOperatorExpression";
   case NodeKind::UnqualifiedId:
     return OS << "UnqualifiedId";
return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::LiteralToken));
 }
 
 syntax::Leaf *syntax::CxxNullPtrExpression::nullPtrKeyword() {
   return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::LiteralToken));
 }
 
+syntax::Leaf *syntax::UserDefinedLiteralExpression::literalToken() {
+  return llvm::cast_or_null<syntax::Leaf>(
+      findChild(syntax::NodeRole::LiteralToken));
+}
+
 syntax::Expression *syntax::BinaryOperatorExpression::lhs() {
   return llvm::cast_or_null<syntax::Expression>(
       findChild(syntax::NodeRole::BinaryOperatorExpression_leftHandSide));
 }
 
 syntax::Leaf *syntax::UnaryOperatorExpression::operatorToken() {
   return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::OperatorExpression_operatorToken));

clang/unittests/Tooling/Syntax/TreeTest.cpp

`-CompoundStatement
     | | |   | `-2
     | | |   `-)
     | | `-)
     | `-;
     `-}
 )txt"));
 }
 
-TEST_P(SyntaxTreeTest, IntegerLiteral) {
+TEST_P(SyntaxTreeTest, UserDefinedLiteral) {
+  if (!GetParam().isCXX11OrLater()) {
+    return;
+  }
   EXPECT_TRUE(treeDumpEqual(
       R"cpp(
+unsigned operator "" _i(unsigned long long);
+unsigned operator "" _f(long double);
+unsigned operator "" _c(char);
+
+unsigned operator "" _r(const char*); // raw-literal operator
+
+template <char...>
+unsigned operator "" _t();            // numeric literal operator template
+
 void test() {
-  12;
-  12u;
-  12l;
-  12ul;
-  014;
-  0XC;
+  12_i;  // call: operator "" _i(12uLL)      | kind: integer
+  1.2_f; // call: operator "" _f(1.2L)       | kind: float
+  '2'_c; // call: operator "" _c('2')        | kind: char
+
+  // TODO: Generate `FloatUserDefinedLiteralExpression` and
+  // `IntegerUserDefinedLiteralExpression` instead of
+  // `UnknownUserDefinedLiteralExpression`. See `getUserDefinedLiteralKind`
+  12_r;  // call: operator "" _r("12")       | kind: integer
+  1.2_r; // call: operator "" _i("1.2")      | kind: float
+  12_t;  // call: operator<'1', '2'> "" _x() | kind: integer
+  1.2_t; // call: operator<'1', '2'> "" _x() | kind: float
 }
     )cpp",
       R"txt(
 *: TranslationUnit
+|-SimpleDeclaration
+| |-unsigned
+| |-SimpleDeclarator
+| | |-operator
+| | |-""
+| | |-_i
+| | `-ParametersAndQualifiers
+| |   |-(
+| |   |-SimpleDeclaration
+| |   | |-unsigned
+| |   | |-long
+| |   | `-long
+| |   `-)
+| `-;
+|-SimpleDeclaration
+| |-unsigned
+| |-SimpleDeclarator
+| | |-operator
+| | |-""
+| | |-_f
+| | `-ParametersAndQualifiers
+| |   |-(
+| |   |-SimpleDeclaration
+| |   | |-long
+| |   | `-double
+| |   `-)
+| `-;
+|-SimpleDeclaration
+| |-unsigned
+| |-SimpleDeclarator
+| | |-operator
+| | |-""
+| | |-_c
+| | `-ParametersAndQualifiers
+| |   |-(
+| |   |-SimpleDeclaration
+| |   | `-char
+| |   `-)
+| `-;
+|-SimpleDeclaration
+| |-unsigned
+| |-SimpleDeclarator
+| | |-operator
+| | |-""
+| | |-_r
+| | `-ParametersAndQualifiers
+| |   |-(
+| |   |-SimpleDeclaration
+| |   | |-const
+| |   | |-char
+| |   | `-SimpleDeclarator
+| |   |   `-*
+| |   `-)
+| `-;
+|-TemplateDeclaration
+| |-template
+| |-<
+| |-SimpleDeclaration
+| | `-char
+| |-...
+| |->
+| `-SimpleDeclaration
+|   |-unsigned
+|   |-SimpleDeclarator
+|   | |-operator
+|   | |-""
+|   | |-_t
+|   | `-ParametersAndQualifiers
+|   |   |-(
+|   |   `-)
+|   `-;
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
     |-ExpressionStatement
-    | |-IntegerLiteralExpression
-    | | `-12
+    | |-IntegerUserDefinedLiteralExpression
+    | | `-12_i
     | `-;
     |-ExpressionStatement
-    | |-IntegerLiteralExpression
-    | | `-12u
+    | |-FloatUserDefinedLiteralExpression
+    | | `-1.2_f
     | `-;
     |-ExpressionStatement
-    | |-IntegerLiteralExpression
-    | | `-12l
+    | |-CharUserDefinedLiteralExpression
+    | | `-'2'_c
     | `-;
     |-ExpressionStatement
-    | |-IntegerLiteralExpression
-    | | `-12ul
+    | |-UnknownUserDefinedLiteralExpression
+    | | `-12_r
     | `-;
     |-ExpressionStatement
-    | |-IntegerLiteralExpression
-    | | `-014
+    | |-UnknownUserDefinedLiteralExpression
+    | | `-1.2_r
     | `-;
     |-ExpressionStatement
-    | |-IntegerLiteralExpression
-    | | `-0XC
+    | |-UnknownUserDefinedLiteralExpression
+    | | `-12_t
+    | `-;
+    |-ExpressionStatement
+    | |-UnknownUserDefinedLiteralExpression
+    | | `-1.2_t
+    | `-;
+    `-}
+)txt"));
+}
+
+TEST_P(SyntaxTreeTest, UserDefinedLiteralString) {
+  if (!GetParam().isCXX11OrLater()) {
+    return;
+  }
+  EXPECT_TRUE(treeDumpEqual(
+      R"cpp(
+typedef decltype(sizeof(void *)) size_t;
+unsigned operator "" _s(const char*, size_t);
+void test() {
+  "12"_s;// call: operator "" _s("12")       | kind: string
+}
+    )cpp",
+      R"txt(
+*: TranslationUnit
+|-SimpleDeclaration
+| |-typedef
+| |-decltype
+| |-(
+| |-UnknownExpression
+| | |-sizeof
+| | |-(
+| | |-void
+| | |-*
+| | `-)
+| |-)
+| |-SimpleDeclarator
+| | `-size_t
+| `-;
+|-SimpleDeclaration
+| |-unsigned
+| |-SimpleDeclarator
+| | |-operator
+| | |-""
+| | |-_s
+| | `-ParametersAndQualifiers
+| |   |-(
+| |   |-SimpleDeclaration
+| |   | |-const
+| |   | |-char
+| |   | `-SimpleDeclarator
+| |   |   `-*
+| |   |-,
+| |   |-SimpleDeclaration
+| |   | `-size_t
+| |   `-)
+| `-;
+`-SimpleDeclaration
+  |-void
+  |-SimpleDeclarator
+  | |-test
+  | `-ParametersAndQualifiers
+  |   |-(
+  |   `-)
+  `-CompoundStatement
+    |-{
+    |-ExpressionStatement
+    | |-StringUserDefinedLiteralExpression
+    | | `-"12"_s
     | `-;
     `-}
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, IntegerLiteralLongLong) {
   if (!GetParam().isCXX11OrLater()) {
     return;