Add support for binary operators in Syntax Trees

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

 /// blocks of enumerator constants must correspond to the inheritance hierarchy
 /// of syntax::Node.
 enum class NodeKind : uint16_t {
   Leaf,
   TranslationUnit,
 
   // Expressions.
   UnknownExpression,
+  BinaryOperatorExpression,
 
   // Statements.
   UnknownStatement,
   DeclarationStatement,
   EmptyStatement,
   SwitchStatement,
   CaseStatement,
   DefaultStatement,
enum class NodeRole : uint8_t {
   /// A keywords that introduces some grammar construct, e.g. 'if', 'try', etc.
   IntroducerKeyword,
   /// An inner statement for those that have only a single child of kind
   /// statement, e.g. loop body for while, for, etc; inner statement for case,
   /// default, etc.
   BodyStatement,
 
   // Roles specific to particular node kinds.
+  BinaryOperatorExpression_leftHandSide,
+  BinaryOperatorExpression_operatorToken,
+  BinaryOperatorExpression_rightHandSide,
   CaseStatement_value,
   IfStatement_thenStatement,
   IfStatement_elseKeyword,
   IfStatement_elseStatement,
   ReturnStatement_value,
   ExpressionStatement_expression,
   CompoundStatement_statement,
   StaticAssertDeclaration_condition,

 class UnknownExpression final : public Expression {
 public:
   UnknownExpression() : Expression(NodeKind::UnknownExpression) {}
   static bool classof(const Node *N) {
     return N->kind() == NodeKind::UnknownExpression;
   }
 };
 
+/// <lhs> <operator> <rhs>
+///
+/// For example:
+///   a + b
+///   a bitor 1
+///   a |= b
+///   a and_eq b
+class BinaryOperatorExpression final : public Expression {
+public:
+  BinaryOperatorExpression() : Expression(NodeKind::BinaryOperatorExpression) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::BinaryOperatorExpression;
+  }
+  syntax::Expression *lhs();
+  syntax::Leaf *operatorToken();
+  syntax::Expression *rhs();
+};
+
 /// An abstract node for C++ statements, e.g. 'while', 'if', etc.
 /// FIXME: add accessors for semicolon of statements that have it.
 class Statement : public Tree {
 public:
   Statement(NodeKind K) : Tree(K) {}
   static bool classof(const Node *N) {
     return NodeKind::UnknownStatement <= N->kind() &&
            N->kind() <= NodeKind::CompoundStatement;

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/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"
public:
   }
 
   bool TraverseStmt(Stmt *S) {
     if (auto *DS = llvm::dyn_cast_or_null<DeclStmt>(S)) {
       // We want to consume the semicolon, make sure SimpleDeclaration does not.
       for (auto *D : DS->decls())
         Builder.noticeDeclWithoutSemicolon(D);
     } else if (auto *E = llvm::dyn_cast_or_null<Expr>(S)) {
-      // Do not recurse into subexpressions.
-      // We do not have syntax trees for expressions yet, so we only want to see
-      // the first top-level expression.
-      return WalkUpFromExpr(E->IgnoreImplicit());
+      return RecursiveASTVisitor::TraverseStmt(E->IgnoreImplicit());
     }
     return RecursiveASTVisitor::TraverseStmt(S);
   }
 
   // Some expressions are not yet handled by syntax trees.
   bool WalkUpFromExpr(Expr *E) {
     assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");
     Builder.foldNode(Builder.getExprRange(E),
                      new (allocator()) syntax::UnknownExpression, E);
     return true;
   }
 
+  bool WalkUpFromBinaryOperator(BinaryOperator *S) {
+    Builder.markExprChild(
+        S->getLHS(), syntax::NodeRole::BinaryOperatorExpression_leftHandSide);
+    Builder.markChildToken(
+        S->getOperatorLoc(),
+        syntax::NodeRole::BinaryOperatorExpression_operatorToken);
+    Builder.markExprChild(
+        S->getRHS(), syntax::NodeRole::BinaryOperatorExpression_rightHandSide);
+    Builder.foldNode(Builder.getExprRange(S),
+                     new (allocator()) syntax::BinaryOperatorExpression, S);
+    return true;
+  }
+
   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.
       return true;
     }

clang/lib/Tooling/Syntax/Nodes.cpp

 llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeKind K) {
   switch (K) {
   case NodeKind::Leaf:
     return OS << "Leaf";
   case NodeKind::TranslationUnit:
     return OS << "TranslationUnit";
   case NodeKind::UnknownExpression:
     return OS << "UnknownExpression";
+  case NodeKind::BinaryOperatorExpression:
+    return OS << "BinaryOperatorExpression";
   case NodeKind::UnknownStatement:
     return OS << "UnknownStatement";
   case NodeKind::DeclarationStatement:
     return OS << "DeclarationStatement";
   case NodeKind::EmptyStatement:
     return OS << "EmptyStatement";
   case NodeKind::SwitchStatement:
     return OS << "SwitchStatement";
llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeRole R) {
   case syntax::NodeRole::CaseStatement_value:
     return OS << "CaseStatement_value";
   case syntax::NodeRole::IfStatement_thenStatement:
     return OS << "IfStatement_thenStatement";
   case syntax::NodeRole::IfStatement_elseKeyword:
     return OS << "IfStatement_elseKeyword";
   case syntax::NodeRole::IfStatement_elseStatement:
     return OS << "IfStatement_elseStatement";
+  case syntax::NodeRole::BinaryOperatorExpression_leftHandSide:
+    return OS << "BinaryOperatorExpression_leftHandSide";
+  case syntax::NodeRole::BinaryOperatorExpression_operatorToken:
+    return OS << "BinaryOperatorExpression_operatorToken";
+  case syntax::NodeRole::BinaryOperatorExpression_rightHandSide:
+    return OS << "BinaryOperatorExpression_rightHandSide";
   case syntax::NodeRole::ReturnStatement_value:
     return OS << "ReturnStatement_value";
   case syntax::NodeRole::ExpressionStatement_expression:
     return OS << "ExpressionStatement_expression";
   case syntax::NodeRole::CompoundStatement_statement:
     return OS << "CompoundStatement_statement";
   case syntax::NodeRole::StaticAssertDeclaration_condition:
     return OS << "StaticAssertDeclaration_condition";
llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeRole R) {
   case syntax::NodeRole::ParametersAndQualifiers_parameter:
     return OS << "ParametersAndQualifiers_parameter";
   case syntax::NodeRole::ParametersAndQualifiers_trailingReturn:
     return OS << "ParametersAndQualifiers_trailingReturn";
   }
   llvm_unreachable("invalid role");
 }
 
+syntax::Leaf *syntax::BinaryOperatorExpression::operatorToken() {
+  return llvm::cast_or_null<syntax::Leaf>(
+      findChild(syntax::NodeRole::BinaryOperatorExpression_operatorToken));
+}
+
+syntax::Expression *syntax::BinaryOperatorExpression::lhs() {
+  return llvm::cast_or_null<syntax::Expression>(
+      findChild(syntax::NodeRole::BinaryOperatorExpression_leftHandSide));
+}
+
+syntax::Expression *syntax::BinaryOperatorExpression::rhs() {
+  return llvm::cast_or_null<syntax::Expression>(
+      findChild(syntax::NodeRole::BinaryOperatorExpression_rightHandSide));
+}
+
 syntax::Leaf *syntax::SwitchStatement::switchKeyword() {
   return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::IntroducerKeyword));
 }
 
 syntax::Statement *syntax::SwitchStatement::body() {
   return llvm::cast_or_null<syntax::Statement>(
       findChild(syntax::NodeRole::BodyStatement));

clang/unittests/Tooling/Syntax/TreeTest.cpp

`-SimpleDeclaration
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
     |-ExpressionStatement
     | |-UnknownExpression
-    | | |-test
+    | | |-UnknownExpression
+    | | | `-test
     | | |-(
     | | `-)
     | `-;
     |-IfStatement
     | |-if
     | |-(
     | |-UnknownExpression
     | | `-true
     | |-)
     | |-ExpressionStatement
     | | |-UnknownExpression
-    | | | |-test
+    | | | |-UnknownExpression
+    | | | | `-test
     | | | |-(
     | | | `-)
     | | `-;
     | |-else
     | `-ExpressionStatement
     |   |-UnknownExpression
-    |   | |-test
-    |   | |-(
-    |   | `-)
-    |   `-;
+    |   | |-UnknownExpression
+    |   | | `-test
+    |   | |-(
+    |   | `-)
+    |   `-;
+    `-}
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, BinaryOperator) {
+  expectTreeDumpEqual(
+      R"cpp(
+void test(int a) {
+  1 - 2;
+  1 == 2;
+  a = 1;
+  a <<= 1;
+
+  true || false;
+  true or false;
+
+  1 & 2;
+  1 bitand 2;
+
+  a ^= 3;
+  a xor_eq 3;
+}
+    )cpp",
+      R"txt(
+*: TranslationUnit
+`-SimpleDeclaration
+  |-void
+  |-SimpleDeclarator
+  | |-test
+  | `-ParametersAndQualifiers
+  |   |-(
+  |   |-SimpleDeclaration
+  |   | |-int
+  |   | `-SimpleDeclarator
+  |   |   `-a
+  |   `-)
+  `-CompoundStatement
+    |-{
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-1
+    | | |--
+    | | `-UnknownExpression
+    | |   `-2
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-1
+    | | |-==
+    | | `-UnknownExpression
+    | |   `-2
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-a
+    | | |-=
+    | | `-UnknownExpression
+    | |   `-1
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-a
+    | | |-<<=
+    | | `-UnknownExpression
+    | |   `-1
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-true
+    | | |-||
+    | | `-UnknownExpression
+    | |   `-false
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-true
+    | | |-or
+    | | `-UnknownExpression
+    | |   `-false
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-1
+    | | |-&
+    | | `-UnknownExpression
+    | |   `-2
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-1
+    | | |-bitand
+    | | `-UnknownExpression
+    | |   `-2
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-a
+    | | |-^=
+    | | `-UnknownExpression
+    | |   `-3
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-a
+    | | |-xor_eq
+    | | `-UnknownExpression
+    | |   `-3
+    | `-;
+    `-}
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, NestedBinaryOperator) {
+  expectTreeDumpEqual(
+      R"cpp(
+void test(int a, int b) {
+  (1 + 2) * (4 / 2);
+  a + b + 42;
+  a = b = 42;
+  a + b * 4 + 2;
+  a % 2 + b * 42;
+}
+    )cpp",
+      R"txt(
+*: TranslationUnit
+`-SimpleDeclaration
+  |-void
+  |-SimpleDeclarator
+  | |-test
+  | `-ParametersAndQualifiers
+  |   |-(
+  |   |-SimpleDeclaration
+  |   | |-int
+  |   | `-SimpleDeclarator
+  |   |   `-a
+  |   |-,
+  |   |-SimpleDeclaration
+  |   | |-int
+  |   | `-SimpleDeclarator
+  |   |   `-b
+  |   `-)
+  `-CompoundStatement
+    |-{
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | |-(
+    | | | |-BinaryOperatorExpression
+    | | | | |-UnknownExpression
+    | | | | | `-1
+    | | | | |-+
+    | | | | `-UnknownExpression
+    | | | |   `-2
+    | | | `-)
+    | | |-*
+    | | `-UnknownExpression
+    | |   |-(
+    | |   |-BinaryOperatorExpression
+    | |   | |-UnknownExpression
+    | |   | | `-4
+    | |   | |-/
+    | |   | `-UnknownExpression
+    | |   |   `-2
+    | |   `-)
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-BinaryOperatorExpression
+    | | | |-UnknownExpression
+    | | | | `-a
+    | | | |-+
+    | | | `-UnknownExpression
+    | | |   `-b
+    | | |-+
+    | | `-UnknownExpression
+    | |   `-42
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-UnknownExpression
+    | | | `-a
+    | | |-=
+    | | `-BinaryOperatorExpression
+    | |   |-UnknownExpression
+    | |   | `-b
+    | |   |-=
+    | |   `-UnknownExpression
+    | |     `-42
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-BinaryOperatorExpression
+    | | | |-UnknownExpression
+    | | | | `-a
+    | | | |-+
+    | | | `-BinaryOperatorExpression
+    | | |   |-UnknownExpression
+    | | |   | `-b
+    | | |   |-*
+    | | |   `-UnknownExpression
+    | | |     `-4
+    | | |-+
+    | | `-UnknownExpression
+    | |   `-2
+    | `-;
+    |-ExpressionStatement
+    | |-BinaryOperatorExpression
+    | | |-BinaryOperatorExpression
+    | | | |-UnknownExpression
+    | | | | `-a
+    | | | |-%
+    | | | `-UnknownExpression
+    | | |   `-2
+    | | |-+
+    | | `-BinaryOperatorExpression
+    | |   |-UnknownExpression
+    | |   | `-b
+    | |   |-*
+    | |   `-UnknownExpression
+    | |     `-42
+    | `-;
     `-}
 )txt");
 }
 
 TEST_F(SyntaxTreeTest, MultipleDeclaratorsGrouping) {
   expectTreeDumpEqual(
       R"cpp(
       int *a, b; int *c, d;
`-SimpleDeclaration
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
     |-IfStatement
     | |-I: if
     | |-I: (
-    | |-I: UnknownExpression
-    | | |-I: 1
+    | |-I: BinaryOperatorExpression
+    | | |-I: UnknownExpression
+    | | | `-I: 1
     | | |-I: +
-    | | `-I: 1
+    | | `-I: UnknownExpression
+    | |   `-I: 1
     | |-I: )
     | |-I: CompoundStatement
     | | |-I: {
     | | `-I: }
     | |-else
     | `-CompoundStatement
     |   |-{
     |   `-}

 | |-int
 | |-SimpleDeclarator
 | | |-c
 | | |-ArraySubscript
 | | | |-[
 | | | `-]
 | | |-=
 | | `-UnknownExpression
-| |   |-{
-| |   |-1
-| |   |-,
-| |   |-2
-| |   |-,
-| |   |-3
-| |   `-}
+| |   `-UnknownExpression
+| |     |-{
+| |     |-UnknownExpression
+| |     | `-1
+| |     |-,
+| |     |-UnknownExpression
+| |     | `-2
+| |     |-,
+| |     |-UnknownExpression
+| |     | `-3
+| |     `-}
 | `-;
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-f
   | `-ParametersAndQualifiers
   |   |-(
   |   |-SimpleDeclaration

 |-SimpleDeclaration
 | |-const
 | |-int
 | |-SimpleDeclarator
 | | |-west
 | | |-=
 | | `-UnknownExpression
 | |   |--
-| |   `-1
+| |   `-UnknownExpression
+| |     `-1
 | `-;
 |-SimpleDeclaration
 | |-int
 | |-const
 | |-SimpleDeclarator
 | | |-east
 | | |-=
 | | `-UnknownExpression