Fix crash on overloaded postfix unary operators due to invalid SourceLocation

[eduucaldas]

Code that reproduces the crash
Notice that when using a postfix unary operator ++ one argument is introduced to differ it from its prefix counterpart, but that argument is not used. This phantom argument shows up in the ClangAST in the form of an IntegerLiteral with invalid sloc. This invalid sloc in a valid AST node was causing the SyntaxTree generation to crash.
We can address this problems at two different levels:

1. At the TraverseCXXOperatorCallExpr, by overriding it and replacing the children iteration to not iterate over this phantom argument.
2. At the WalkUpFromIntegerLiteral, by skipping the visitation of the phantom node.

We preferred the latter.

1. Cons: We would have to duplicate the implementation of RecursiveASTVisitor in BuildTree, to handle this subtle change in traversal. That would add code complexity.
2. Cons: We are handling a problem of CXXOperatorCallExpr in IntegerLiteral.

We chose the latter as, anyways, if an AST node has an invalid sloc, it was either a problem with parsing or the node is supposed to be ignored

clang/include/clang/AST/ExprCXX.h

143–148 ↗

(On Diff #274771)

Should new additions to CXXOperatorCallExpr go on a different patch?
I'll also add unit tests for those. I'm waiting for review on https://reviews.llvm.org/D82937, to do that.

[riccibruno]

clang/lib/AST/ExprCXX.cpp

82 ↗

(On Diff #274771)

This will be true for operator->.

[eduucaldas]

clang/lib/AST/ExprCXX.cpp

82 ↗

(On Diff #274771)

Thank you ! I had missed that! I'll propose a more robust solution. I'll probably split this patch. But I'll take care to subscribe you to anything related

[eduucaldas]

• Remove predicates in CXXOperatorCallExpr.
• Implement getOperatorNodeKind to dispatch from CXXOperatorCallExpr to syntax constructs like BinaryOperatorExpression, PrefixUnaryOperatorExpression...

[eduucaldas]

Nits

[eduucaldas]

Revert mistake on last update, used arc diff --update with the wrong diff

[eduucaldas]

clang/lib/Tooling/Syntax/BuildTree.cpp

118

Where to put this logic?

The pro of having this function inside BuildTree.cpp is that it is closer to it's *only* usage. And also for now BuildTree.cpp agglomerates everything that takes a semantic AST as an input, so it would be coherent.

Another option is to put it in Nodes, as it might serve as documentation for *OperatorExpressions.
For example, it would document that the semantic node CXXOperatorCallExpr can also generate the syntax node BinaryOperatorExpression, which was previously only generated by a semantic BinaryOperator

Another option is to add put this function as a lambda inside WalkUpFromCXXOperatorCallExpr as probably it will only be used there.

[eduucaldas]

clang/lib/Tooling/Syntax/BuildTree.cpp

188

Actually arrow star is treated like a normal binary operator in the grammar

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

118

Placing this helper here makes sense to me. However, please mark it static.

178

"Not supported by syntax tree *yet*"

745

WDYT about overriding TraverseCXXOperatorCallExpr, so that we don't even visit the synthetic argument of the postfix unary ++? I would prefer to not introduce blanket "if invalid then ignore" checks in the code.

874

"getOperatorNodeKind() does not return this value"

clang/unittests/Tooling/Syntax/TreeTest.cpp

2553

Could you also add tests for a prefix unary operator?

2596

I'm not sure about this part where ++ is wrapped in IdExpression -- shouldn't the syntax tree look identical to a builtin postfix ++ (see another test in this file)?

[eduucaldas]

->* and , are binary operators.
Unit tests covering most of the operator kinds

[eduucaldas]

Answering comments

[eduucaldas]

clang/lib/Tooling/Syntax/BuildTree.cpp

745

In D82954#2125300, @eduucaldas wrote:

Code that reproduces the crash
Notice that when using a postfix unary operator ++ one argument is introduced to differ it from its prefix counterpart, but that argument is not used. This phantom argument shows up in the ClangAST in the form of an IntegerLiteral with invalid sloc. This invalid sloc in a valid AST node was causing the SyntaxTree generation to crash.
We can address this problems at two different levels:

1. At the TraverseCXXOperatorCallExpr, by overriding it and replacing the children iteration to not iterate over this phantom argument.
2. At the WalkUpFromIntegerLiteral, by skipping the visitation of the phantom node.

We preferred the latter.

1. Cons: We would have to duplicate the implementation of RecursiveASTVisitor in BuildTree, to handle this subtle change in traversal. That would add code complexity.
2. Cons: We are handling a problem of CXXOperatorCallExpr in IntegerLiteral.

We chose the latter as, anyways, if an AST node has an invalid sloc, it was either a problem with parsing or the node is supposed to be ignored

I've explained my reasoning in my first comment for this patch. But as it was a long time ago, I guess it got lost, even by me.

I'll sketch how the Traverse solution would look like, to be able to give more concrete arguments.

clang/unittests/Tooling/Syntax/TreeTest.cpp

2596

This comes back to a discussion we had a month ago about operators ( +, !, etc)
Question: Should we represent operators (built-in or overloaded) in the syntax tree uniformly? If so in which way?
Context: The ClangAST stores built-in operators as mere tokens, whereas overloaded operators are represented as a DeclRefExpr. That makes a lot of sense for the ClangAST, as we might refer back to the declaration of the overloaded operator, but the declaration of built-in operator doesn't exist.
Conclusion: Have the same representation for both types of operators. I have implemented the "unboxed" representation of overloaded operators, i.e. just storing their token in the syntax tree. I have not committed that, but I can do it just after this patch.

[eduucaldas]

Unifying user defined binary operator tests

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

149

Please drop this comment, I don't think it helps understand the code.

clang/unittests/Tooling/Syntax/TreeTest.cpp

2192

I don't think we need a separate class to show the left shift operator. The declaration below can be:

friend X operator<<(X&, const X&);

2198

"TODO: Fix the crash on ->* and add a test for it."

2596

SGTM. Please just leave a FIXME or TODO in this patch that shows that certain parts of tests are not final.

[eduucaldas]

answering minor comments

clang/unittests/Tooling/Syntax/TreeTest.cpp

2192

If we don't bother much about "realistic" operator declarations we could drop all the friend and declare every operator in their most concise form. WDYT

[gribozavr2]

clang/unittests/Tooling/Syntax/TreeTest.cpp

2192

I think we shouldn't try to make tests realistic in terms of function names etc., but we should try to cover as many different AST shapes as possible. In the case of binary operators, we have three cases -- free function, friend function, member function, that all generate slightly different ASTs, so I believe we should try to cover them all.

[eduucaldas]

clang/unittests/Tooling/Syntax/TreeTest.cpp

2192

But those all regard the operators declaration.
Here we test the operator call expression - CXXOperatorCallExpr.

I think we should test friend function declarations when we add support for them in the tree, and then we add tests for declaration of friend operators, friend member functions and whatnot.

[gribozavr2]

clang/unittests/Tooling/Syntax/TreeTest.cpp

2192

The call expression AST node can be meaningfully different between calls to member and non-member functions.

[eduucaldas]

Switch to TraverseCXXOperatorCallExpr

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

820

"is used to distinguish"

823

"... because does not correspond to anything written in the source code"

[eduucaldas]

minor fix comments

clang/lib/Tooling/Syntax/BuildTree.cpp

 //===- BuildTree.cpp ------------------------------------------*- 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/Tooling/Syntax/BuildTree.h"
 #include "clang/AST/ASTFwd.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclarationName.h"
 #include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/AST/TypeLocVisitor.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/Specifiers.h"
template <class PtrLoc> SourceLocation HandlePointer(PtrLoc T) {
     auto L = Visit(T.getPointeeLoc());
     if (L.isValid())
       return L;
     return T.getLocalSourceRange().getBegin();
   }
 };
 } // namespace
 
+static syntax::NodeKind getOperatorNodeKind(const CXXOperatorCallExpr &E) {
+  switch (E.getOperator()) {
+  // Comparison
+  case OO_EqualEqual:
+  case OO_ExclaimEqual:
+  case OO_Greater:
+  case OO_GreaterEqual:
+  case OO_Less:
+  case OO_LessEqual:
+  case OO_Spaceship:
+  // Assignment
+  case OO_Equal:
+  case OO_SlashEqual:
+  case OO_PercentEqual:
+  case OO_CaretEqual:
+  case OO_PipeEqual:
+  case OO_LessLessEqual:
+  case OO_GreaterGreaterEqual:
+  case OO_PlusEqual:
+  case OO_MinusEqual:
+  case OO_StarEqual:
+  case OO_AmpEqual:
+  // Binary computation
+  case OO_Slash:
+  case OO_Percent:
+  case OO_Caret:
+  case OO_Pipe:
+  case OO_LessLess:
+  case OO_GreaterGreater:
+  case OO_AmpAmp:
+  case OO_PipePipe:
+  case OO_ArrowStar:
+  case OO_Comma:
+    return syntax::NodeKind::BinaryOperatorExpression;
+  case OO_Tilde:
+  case OO_Exclaim:
+    return syntax::NodeKind::PrefixUnaryOperatorExpression;
+  // Prefix/Postfix increment/decrement
+  case OO_PlusPlus:
+  case OO_MinusMinus:
+    switch (E.getNumArgs()) {
+    case 1:
+      return syntax::NodeKind::PrefixUnaryOperatorExpression;
+    case 2:
+      return syntax::NodeKind::PostfixUnaryOperatorExpression;
+    default:
+      llvm_unreachable("Invalid number of arguments for operator");
+    }
+  // Operators that can be unary or binary
+  case OO_Plus:
+  case OO_Minus:
+  case OO_Star:
+  case OO_Amp:
+    switch (E.getNumArgs()) {
+    case 1:
+      return syntax::NodeKind::PrefixUnaryOperatorExpression;
+    case 2:
+      return syntax::NodeKind::BinaryOperatorExpression;
+    default:
+      llvm_unreachable("Invalid number of arguments for operator");
+    }
+    return syntax::NodeKind::BinaryOperatorExpression;
+  // Not yet supported by SyntaxTree
+  case OO_New:
+  case OO_Delete:
+  case OO_Array_New:
+  case OO_Array_Delete:
+  case OO_Coawait:
+  case OO_Call:
+  case OO_Subscript:
+  case OO_Arrow:
+    return syntax::NodeKind::UnknownExpression;
+  case OO_Conditional: // not overloadable
+  case NUM_OVERLOADED_OPERATORS:
+  case OO_None:
+    llvm_unreachable("Not an overloadable operator");
+  }
+}
+
 /// Gets the range of declarator as defined by the C++ grammar. E.g.
 ///     `int a;` -> range of `a`,
 ///     `int *a;` -> range of `*a`,
 ///     `int a[10];` -> range of `a[10]`,
 ///     `int a[1][2][3];` -> range of `a[1][2][3]`,
 ///     `int *a = nullptr` -> range of `*a = nullptr`.
 /// FIMXE: \p Name must be a source range, e.g. for `operator+`.
 static SourceRange getDeclaratorRange(const SourceManager &SM, TypeLoc T,
Builder.markExprChild(S->getSubExpr(),
                           syntax::NodeRole::ParenExpression_subExpression);
     Builder.markChildToken(S->getRParen(), syntax::NodeRole::CloseParen);
     Builder.foldNode(Builder.getExprRange(S),
                      new (allocator()) syntax::ParenExpression, S);
     return true;
   }
 
   bool WalkUpFromIntegerLiteral(IntegerLiteral *S) {
     Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
     Builder.foldNode(Builder.getExprRange(S),
                      new (allocator()) syntax::IntegerLiteralExpression, S);
     return true;
   }
 
   bool WalkUpFromCharacterLiteral(CharacterLiteral *S) {
     Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
     Builder.foldNode(Builder.getExprRange(S),
Builder.markChildToken(S->getOperatorLoc(),
                            syntax::NodeRole::OperatorExpression_operatorToken);
     Builder.markExprChild(
         S->getRHS(), syntax::NodeRole::BinaryOperatorExpression_rightHandSide);
     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
+      // `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;
+      }
+      return WalkUpFromCXXOperatorCallExpr(S);
+    } else
+      return RecursiveASTVisitor::TraverseCXXOperatorCallExpr(S);
+  }
+
   bool WalkUpFromCXXOperatorCallExpr(CXXOperatorCallExpr *S) {
-    if (S->isInfixBinaryOp()) {
+    switch (getOperatorNodeKind(*S)) {
+    case syntax::NodeKind::BinaryOperatorExpression:
       Builder.markExprChild(
           S->getArg(0),
           syntax::NodeRole::BinaryOperatorExpression_leftHandSide);
       Builder.markChildToken(
           S->getOperatorLoc(),
           syntax::NodeRole::OperatorExpression_operatorToken);
       Builder.markExprChild(
           S->getArg(1),
           syntax::NodeRole::BinaryOperatorExpression_rightHandSide);
       Builder.foldNode(Builder.getExprRange(S),
                        new (allocator()) syntax::BinaryOperatorExpression, S);
       return true;
-    }
+    case syntax::NodeKind::PrefixUnaryOperatorExpression:
+      Builder.markChildToken(
+          S->getOperatorLoc(),
+          syntax::NodeRole::OperatorExpression_operatorToken);
+      Builder.markExprChild(S->getArg(0),
+                            syntax::NodeRole::UnaryOperatorExpression_operand);
+      Builder.foldNode(Builder.getExprRange(S),
+                       new (allocator()) syntax::PrefixUnaryOperatorExpression,
+                       S);
+      return true;
+    case syntax::NodeKind::PostfixUnaryOperatorExpression:
+      Builder.markChildToken(
+          S->getOperatorLoc(),
+          syntax::NodeRole::OperatorExpression_operatorToken);
+      Builder.markExprChild(S->getArg(0),
+                            syntax::NodeRole::UnaryOperatorExpression_operand);
+      Builder.foldNode(Builder.getExprRange(S),
+                       new (allocator()) syntax::PostfixUnaryOperatorExpression,
+                       S);
+      return true;
+    case syntax::NodeKind::UnknownExpression:
       return RecursiveASTVisitor::WalkUpFromCXXOperatorCallExpr(S);
+    default:
+      llvm_unreachable("getOperatorNodeKind() does not return this value");
+    }
   }
 
   bool WalkUpFromNamespaceDecl(NamespaceDecl *S) {
     auto Tokens = Builder.getDeclarationRange(S);
     if (Tokens.front().kind() == tok::coloncolon) {
       // Handle nested namespace definitions. Those start at '::' token, e.g.
       // namespace a^::b {}
       // FIXME: build corresponding nodes for the name of this namespace.

clang/unittests/Tooling/Syntax/TreeTest.cpp

 }
 
 TEST_P(SyntaxTreeTest, UserDefinedBinaryOperator) {
   if (!GetParam().isCXX()) {
     return;
   }
   EXPECT_TRUE(treeDumpEqual(
       R"cpp(
 struct X {
   X& operator=(const X&);
   friend X operator+(X, const X&);
   friend bool operator<(const X&, const X&);
+  friend X operator<<(X&, const X&);
+  X operator,(X&);
+  // TODO: Fix crash on member function pointer and add a test for `->*`
+  // TODO: Unbox operators in syntax tree. 
+  // Represent operators by `+` instead of `IdExpression-UnqualifiedId-+`
 };
 void test(X x, X y) {
   x = y;
   x + y;
   x < y;
+  x << y;
+  x, y;
 }
 )cpp",
       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-struct
 | |-X
 | |-{

 | |   |   |-,
 | |   |   |-SimpleDeclaration
 | |   |   | |-const
 | |   |   | |-X
 | |   |   | `-SimpleDeclarator
 | |   |   |   `-&
 | |   |   `-)
 | |   `-;
+| |-UnknownDeclaration
+| | `-SimpleDeclaration
+| |   |-friend
+| |   |-X
+| |   |-SimpleDeclarator
+| |   | |-operator
+| |   | |-<<
+| |   | `-ParametersAndQualifiers
+| |   |   |-(
+| |   |   |-SimpleDeclaration
+| |   |   | |-X
+| |   |   | `-SimpleDeclarator
+| |   |   |   `-&
+| |   |   |-,
+| |   |   |-SimpleDeclaration
+| |   |   | |-const
+| |   |   | |-X
+| |   |   | `-SimpleDeclarator
+| |   |   |   `-&
+| |   |   `-)
+| |   `-;
+| |-SimpleDeclaration
+| | |-X
+| | |-SimpleDeclarator
+| | | |-operator
+| | | |-,
+| | | `-ParametersAndQualifiers
+| | |   |-(
+| | |   |-SimpleDeclaration
+| | |   | |-X
+| | |   | `-SimpleDeclarator
+| | |   |   `-&
+| | |   `-)
+| | `-;
 | |-}
 | `-;
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
`-CompoundStatement
     | | |   `-x
     | | |-IdExpression
     | | | `-UnqualifiedId
     | | |   `-<
     | | `-IdExpression
     | |   `-UnqualifiedId
     | |     `-y
     | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-IdExpression
+    | | | `-UnqualifiedId
+    | | |   `-x
+    | | |-IdExpression
+    | | | `-UnqualifiedId
+    | | |   `-<<
+    | | `-IdExpression
+    | |   `-UnqualifiedId
+    | |     `-y
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-IdExpression
+    | | | `-UnqualifiedId
+    | | |   `-x
+    | | |-IdExpression
+    | | | `-UnqualifiedId
+    | | |   `-,
+    | | `-IdExpression
+    | |   `-UnqualifiedId
+    | |     `-y
+    | `-;
+    `-}
+)txt"));
+}
+
+TEST_P(SyntaxTreeTest, UserDefinedUnaryPrefixOperator) {
+  if (!GetParam().isCXX()) {
+    return;
+  }
+  EXPECT_TRUE(treeDumpEqual(
+      R"cpp(
+struct X {
+  X operator++();
+  bool operator!();
+  X* operator&();
+};
+void test(X x) {
+  ++x;
+  !x;
+  &x;
+}
+)cpp",
+      R"txt(
+*: TranslationUnit
+|-SimpleDeclaration
+| |-struct
+| |-X
+| |-{
+| |-SimpleDeclaration
+| | |-X
+| | |-SimpleDeclarator
+| | | |-operator
+| | | |-++
+| | | `-ParametersAndQualifiers
+| | |   |-(
+| | |   `-)
+| | `-;
+| |-SimpleDeclaration
+| | |-bool
+| | |-SimpleDeclarator
+| | | |-operator
+| | | |-!
+| | | `-ParametersAndQualifiers
+| | |   |-(
+| | |   `-)
+| | `-;
+| |-SimpleDeclaration
+| | |-X
+| | |-SimpleDeclarator
+| | | |-*
+| | | |-operator
+| | | |-&
+| | | `-ParametersAndQualifiers
+| | |   |-(
+| | |   `-)
+| | `-;
+| |-}
+| `-;
+`-SimpleDeclaration
+  |-void
+  |-SimpleDeclarator
+  | |-test
+  | `-ParametersAndQualifiers
+  |   |-(
+  |   |-SimpleDeclaration
+  |   | |-X
+  |   | `-SimpleDeclarator
+  |   |   `-x
+  |   `-)
+  `-CompoundStatement
+    |-{
+    |-ExpressionStatement
+    | |-PrefixUnaryOperatorExpression
+    | | |-IdExpression
+    | | | `-UnqualifiedId
+    | | |   `-++
+    | | `-IdExpression
+    | |   `-UnqualifiedId
+    | |     `-x
+    | `-;
+    |-ExpressionStatement
+    | |-PrefixUnaryOperatorExpression
+    | | |-IdExpression
+    | | | `-UnqualifiedId
+    | | |   `-!
+    | | `-IdExpression
+    | |   `-UnqualifiedId
+    | |     `-x
+    | `-;
+    |-ExpressionStatement
+    | |-PrefixUnaryOperatorExpression
+    | | |-IdExpression
+    | | | `-UnqualifiedId
+    | | |   `-&
+    | | `-IdExpression
+    | |   `-UnqualifiedId
+    | |     `-x
+    | `-;
+    `-}
+)txt"));
+}
+
+TEST_P(SyntaxTreeTest, UserDefinedUnaryPostfixOperator) {
+  if (!GetParam().isCXX()) {
+    return;
+  }
+  EXPECT_TRUE(treeDumpEqual(
+      R"cpp(
+struct X {
+  X operator++(int);
+};
+void test(X x) {
+  x++;
+}
+)cpp",
+      R"txt(
+*: TranslationUnit
+|-SimpleDeclaration
+| |-struct
+| |-X
+| |-{
+| |-SimpleDeclaration
+| | |-X
+| | |-SimpleDeclarator
+| | | |-operator
+| | | |-++
+| | | `-ParametersAndQualifiers
+| | |   |-(
+| | |   |-SimpleDeclaration
+| | |   | `-int
+| | |   `-)
+| | `-;
+| |-}
+| `-;
+`-SimpleDeclaration
+  |-void
+  |-SimpleDeclarator
+  | |-test
+  | `-ParametersAndQualifiers
+  |   |-(
+  |   |-SimpleDeclaration
+  |   | |-X
+  |   | `-SimpleDeclarator
+  |   |   `-x
+  |   `-)
+  `-CompoundStatement
+    |-{
+    |-ExpressionStatement
+    | |-PostfixUnaryOperatorExpression
+    | | |-IdExpression
+    | | | `-UnqualifiedId
+    | | |   `-x
+    | | `-IdExpression
+    | |   `-UnqualifiedId
+    | |     `-++
+    | `-;
     `-}
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, MultipleDeclaratorsGrouping) {
   EXPECT_TRUE(treeDumpEqual(
       R"cpp(
 int *a, b;
 int *c, d;
 )cpp",
       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-int
 | |-SimpleDeclarator
 | | |-*
 | | `-a
 | |-,
 | |-SimpleDeclarator
 | | `-b
`-SimpleDeclaration
   |-,
   |-SimpleDeclarator
   | `-b
   `-;
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, MultipleDeclaratorsInsideStatement) {
   EXPECT_TRUE(treeDumpEqual(
       R"cpp(
 void foo() {
   int *a, b;
   typedef int *ta, tb;
 }
 )cpp",
       R"txt(
 *: TranslationUnit