[SyntaxTree] Use PointerUnion instead of inheritance for alternative clauses in NNS

[eduucaldas]

Summary

We also fix a crasch on name specifier.

The generation of syntax tree for name specifiers with longer than 1 character identifier crashed. Root cause is that getLocalSourceRange returns a SourceRange that had its end SourceLocation just before the :: in the nested-name-specifier, but we actually expect SourceLocation to be at the start of tokens.

[eduucaldas]

• [SyntaxTree] Fix crash on name specifier.

This diff revision is based on https://reviews.llvm.org/D84348

[eduucaldas]

clang/lib/Tooling/Syntax/BuildTree.cpp

781–782

Newbie mistake causing the crash

839

I mark NodeRole as Unknown here, this would need fixing in the future. But should we make roles that mimic the NodeKind of the alternative?

clang/unittests/Tooling/Syntax/TreeTest.cpp

1003–1008

Here notice the additional level of nesting

[eduucaldas]

Remove Fix crash on name specifier commit from patch

[gribozavr2]

Seeing the API, I like the inheritance-based approach better. It seems more uniform.

clang/lib/Tooling/Syntax/Nodes.cpp

219

getFromOpaqueValue will not select the right alternative in the PointerUnion. You need to do case analysis through if-else-if based on the type of node returned by firstChild.

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

 namespace clang {
 namespace syntax {
 
 /// A kind of a syntax node, used for implementing casts. The ordering and
 /// blocks of enumerator constants must correspond to the inheritance hierarchy
 /// of syntax::Node.
 enum class NodeKind : uint16_t {
   Leaf,
+  EmptyNode,
   TranslationUnit,
 
   // Expressions.
   UnknownExpression,
   PrefixUnaryOperatorExpression,
   PostfixUnaryOperatorExpression,
   BinaryOperatorExpression,
   ParenExpression,
enum class NodeKind : uint16_t {
   SimpleDeclarator,
   ParenDeclarator,
 
   ArraySubscript,
   TrailingReturnType,
   ParametersAndQualifiers,
   MemberPointer,
   UnqualifiedId,
+
   // Nested Name Specifiers.
   NestedNameSpecifier,
-  GlobalNameSpecifier,
-  DecltypeNameSpecifier,
-  IdentifierNameSpecifier,
-  SimpleTemplateNameSpecifier
+  NameSpecifier,
+  DecltypeSpecifier,
+  SimpleTemplateSpecifier
 };
 /// For debugging purposes.
 raw_ostream &operator<<(raw_ostream &OS, NodeKind K);
 
 /// A relation between a parent and child node, e.g. 'left-hand-side of
 /// a binary expression'. Used for implementing accessors.
 ///
 /// Some roles describe parent/child relations that occur multiple times in

 public:
   Expression(NodeKind K) : Tree(K) {}
   static bool classof(const Node *N) {
     return NodeKind::UnknownExpression <= N->kind() &&
            N->kind() <= NodeKind::UnknownExpression;
   }
 };
 
-/// A sequence of these specifiers make a `nested-name-specifier`.
-/// e.g. the `std` or `vector<int>` in `std::vector<int>::size`.
-class NameSpecifier : public Tree {
-public:
-  NameSpecifier(NodeKind K) : Tree(K) {}
-  static bool classof(const Node *N) {
-    return N->kind() == NodeKind::GlobalNameSpecifier ||
-           N->kind() == NodeKind::DecltypeNameSpecifier ||
-           N->kind() == NodeKind::IdentifierNameSpecifier ||
-           N->kind() == NodeKind::SimpleTemplateNameSpecifier;
-  }
-};
-
-/// The global namespace name specifier, this specifier doesn't correspond to a
-/// token instead an absence of tokens before a `::` characterizes it, in
-/// `::std::vector<int>` it would be characterized by the absence of a token
-/// before the first `::`
-class GlobalNameSpecifier final : public NameSpecifier {
+class DecltypeSpecifier final : public Tree {
 public:
-  GlobalNameSpecifier() : NameSpecifier(NodeKind::GlobalNameSpecifier) {}
+  DecltypeSpecifier() : Tree(NodeKind::DecltypeSpecifier) {}
   static bool classof(const Node *N) {
-    return N->kind() == NodeKind::GlobalNameSpecifier;
+    return N->kind() == NodeKind::DecltypeSpecifier;
   }
 };
 
-/// A name specifier holding a decltype, of the form: `decltype ( expression ) `
-/// e.g. the `decltype(s)` in `decltype(s)::size`.
-class DecltypeNameSpecifier final : public NameSpecifier {
+class SimpleTemplateSpecifier : public Tree {
 public:
-  DecltypeNameSpecifier() : NameSpecifier(NodeKind::DecltypeNameSpecifier) {}
+  SimpleTemplateSpecifier() : Tree(NodeKind::SimpleTemplateSpecifier) {}
   static bool classof(const Node *N) {
-    return N->kind() == NodeKind::DecltypeNameSpecifier;
+    return N->kind() == NodeKind::SimpleTemplateSpecifier;
   }
 };
 
-/// A identifier name specifier, of the form `identifier`
-/// e.g. the `std` in `std::vector<int>::size`.
-class IdentifierNameSpecifier final : public NameSpecifier {
-public:
-  IdentifierNameSpecifier()
-      : NameSpecifier(NodeKind::IdentifierNameSpecifier) {}
-  static bool classof(const Node *N) {
-    return N->kind() == NodeKind::IdentifierNameSpecifier;
-  }
-};
-
-/// A name specifier with a simple-template-id, of the form `template_opt
-/// identifier < template-args >` e.g. the `vector<int>` in
-/// `std::vector<int>::size`.
-class SimpleTemplateNameSpecifier final : public NameSpecifier {
+/// A sequence of these specifiers make a `nested-name-specifier`.
+/// e.g. the `std` or `vector<int>` in `std::vector<int>::size`.
+class NameSpecifier final : public Tree {
 public:
-  SimpleTemplateNameSpecifier()
-      : NameSpecifier(NodeKind::SimpleTemplateNameSpecifier) {}
+  NameSpecifier() : Tree(NodeKind::NameSpecifier) {}
   static bool classof(const Node *N) {
-    return N->kind() == NodeKind::SimpleTemplateNameSpecifier;
+    return N->kind() == NodeKind::NameSpecifier;
   }
+  llvm::PointerUnion<syntax::EmptyNode *, syntax::Leaf *,
+                     syntax::DecltypeSpecifier *,
+                     syntax::SimpleTemplateSpecifier *>
+  child();
 };
 
 /// Models a `nested-name-specifier`. C++ [expr.prim.id.qual]
 /// e.g. the `std::vector<int>::` in `std::vector<int>::size`.
 class NestedNameSpecifier final : public Tree {
 public:
   NestedNameSpecifier() : Tree(NodeKind::NestedNameSpecifier) {}
   static bool classof(const Node *N) {

clang/include/clang/Tooling/Syntax/Tree.h

public:
   static bool classof(const Node *N);
 
   const Token *token() const { return Tok; }
 
 private:
   const Token *Tok;
 };
 
+class EmptyNode final : public Node {
+public:
+  EmptyNode();
+  static bool classof(const Node *N);
+};
+
 /// A node that has children and represents a syntactic language construct.
 class Tree : public Node {
 public:
   using Node::Node;
   static bool classof(const Node *N);
 
   Node *firstChild() { return FirstChild; }
   const Node *firstChild() const { return FirstChild; }

clang/lib/Tooling/Syntax/BuildTree.cpp

public:
   }
 
   bool WalkUpFromUserDefinedLiteral(UserDefinedLiteral *S) {
     Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);
     Builder.foldNode(Builder.getExprRange(S), buildUserDefinedLiteral(S), S);
     return true;
   }
 
-  syntax::NameSpecifier *BuildNameSpecifier(const NestedNameSpecifier &NNS) {
+  syntax::NodeKind getNameSpecifierChildKind(const NestedNameSpecifier &NNS) {
     switch (NNS.getKind()) {
     case clang::NestedNameSpecifier::Global:
-      return new (allocator()) syntax::GlobalNameSpecifier;
+      return syntax::NodeKind::EmptyNode;
     case clang::NestedNameSpecifier::Namespace:
     case clang::NestedNameSpecifier::NamespaceAlias:
     case clang::NestedNameSpecifier::Identifier:
-      return new (allocator()) syntax::IdentifierNameSpecifier;
+      return syntax::NodeKind::Leaf;
     case clang::NestedNameSpecifier::TypeSpecWithTemplate:
-      return new (allocator()) syntax::SimpleTemplateNameSpecifier;
+      return syntax::NodeKind::SimpleTemplateSpecifier;
     case clang::NestedNameSpecifier::TypeSpec: {
       const auto *NNSType = NNS.getAsType();
       assert(NNSType);
       if (isa<DecltypeType>(NNSType))
-        return new (allocator()) syntax::DecltypeNameSpecifier;
+        return syntax::NodeKind::DecltypeSpecifier;
       if (isa<TemplateSpecializationType, DependentTemplateSpecializationType>(
               NNSType))
-        return new (allocator()) syntax::SimpleTemplateNameSpecifier;
-      return new (allocator()) syntax::IdentifierNameSpecifier;
+        return syntax::NodeKind::SimpleTemplateSpecifier;
+      return syntax::NodeKind::Leaf;
     }
     case clang::NestedNameSpecifier::Super:
       // FIXME: Support Microsoft's __super
       llvm::report_fatal_error("We don't yet support the __super specifier",
                                true);
     }
   }
 
+  syntax::NameSpecifier *
+  BuildNameSpecifier(const NestedNameSpecifierLoc &NNSLoc) {
+    auto NameSpecifierTokens =
+        Builder.getRange(getLocalSourceRange(NNSLoc)).drop_back(1);
+
+    auto *NNS = NNSLoc.getNestedNameSpecifier();
+    assert(NNS);
+    switch (getNameSpecifierChildKind(*NNS)) {
+    case syntax::NodeKind::EmptyNode: {
+      Builder.markChild(new (allocator()) syntax::EmptyNode,
+                        syntax::NodeRole::Unknown);
+      return new (allocator()) syntax::NameSpecifier;
+    }
+    case syntax::NodeKind::Leaf: {
+      assert(NameSpecifierTokens.size() == 1);
+      Builder.markChildToken(NameSpecifierTokens.begin(),
+                             syntax::NodeRole::Unknown);
+      break;
+    }
+    case syntax::NodeKind::SimpleTemplateSpecifier: {
+      auto *child = new (allocator()) syntax::SimpleTemplateSpecifier;
+      Builder.foldNode(NameSpecifierTokens, child, nullptr);
+      Builder.markChild(child, syntax::NodeRole::Unknown);
+      break;
+    }
+    case syntax::NodeKind::DecltypeSpecifier: {
+      auto *child = new (allocator()) syntax::DecltypeSpecifier;
+      Builder.foldNode(NameSpecifierTokens, child, nullptr);
+      Builder.markChild(child, syntax::NodeRole::Unknown);
+      break;
+    }
+    default:
+      llvm_unreachable("getChildKind() does not return this value");
+    }
+
+    auto *NS = new (allocator()) syntax::NameSpecifier;
+    Builder.foldNode(NameSpecifierTokens, NS, nullptr);
+    return NS;
+  }
+
   // FIXME: Fix `NestedNameSpecifierLoc::getLocalSourceRange` for the
   // `DependentTemplateSpecializationType` case.
   /// Given a nested-name-specifier return the range for the last name specifier
   ///
   /// e.g. `std::T::template X<U>::` => `template X<U>::`
   SourceRange getLocalSourceRange(const NestedNameSpecifierLoc &NNSLoc) {
     auto SR = NNSLoc.getLocalSourceRange();
 
     // The method `NestedNameSpecifierLoc::getLocalSourceRange` *should* return
     // the desired `SourceRange`, but there is a corner
     // case. For a `DependentTemplateSpecializationType` this method returns its
     // qualifiers as well, in other words in the example above this method
     // returns `T::template X<U>::` instead of only `template X<U>::`
     if (auto TL = NNSLoc.getTypeLoc()) {
       if (auto DependentTL =
               TL.getAs<DependentTemplateSpecializationTypeLoc>()) {
         // The 'template' keyword is always present in dependent template
         // specializations. Except in the case of incorrect code
         // TODO: Treat the case of incorrect code.
         SR.setBegin(DependentTL.getTemplateKeywordLoc());
       }
     }
 
     return SR;
   }
 
   syntax::NestedNameSpecifier *
   BuildNestedNameSpecifier(const NestedNameSpecifierLoc &QualifierLoc) {
     if (!QualifierLoc)
       return nullptr;
     for (auto it = QualifierLoc; it; it = it.getPrefix()) {
-      assert(it.hasQualifier());
-      auto *NS = BuildNameSpecifier(*it.getNestedNameSpecifier());
+      auto *NS = BuildNameSpecifier(it);
       assert(NS);
-      if (!isa<syntax::GlobalNameSpecifier>(NS))
-        Builder.foldNode(Builder.getRange(getLocalSourceRange(it)).drop_back(),
-                         NS, it);
       Builder.markChild(NS, syntax::NodeRole::NestedNameSpecifier_specifier);
       Builder.markChildToken(it.getEndLoc(),
                              syntax::NodeRole::NestedNameSpecifier_delimiter);
     }
     auto *NNS = new (allocator()) syntax::NestedNameSpecifier;
     Builder.foldNode(Builder.getRange(QualifierLoc.getSourceRange()), NNS,
                      QualifierLoc);
     return NNS;

clang/lib/Tooling/Syntax/Nodes.cpp

 //===- Nodes.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/Nodes.h"
 #include "clang/Basic/TokenKinds.h"
 
 using namespace clang;
 
 raw_ostream &syntax::operator<<(raw_ostream &OS, NodeKind K) {
   switch (K) {
+  case NodeKind::EmptyNode:
+    return OS << "EmptyNode";
   case NodeKind::Leaf:
     return OS << "Leaf";
   case NodeKind::TranslationUnit:
     return OS << "TranslationUnit";
   case NodeKind::UnknownExpression:
     return OS << "UnknownExpression";
   case NodeKind::ParenExpression:
     return OS << "ParenExpression";
raw_ostream &syntax::operator<<(raw_ostream &OS, NodeKind K) {
   case NodeKind::ArraySubscript:
     return OS << "ArraySubscript";
   case NodeKind::TrailingReturnType:
     return OS << "TrailingReturnType";
   case NodeKind::ParametersAndQualifiers:
     return OS << "ParametersAndQualifiers";
   case NodeKind::MemberPointer:
     return OS << "MemberPointer";
-  case NodeKind::GlobalNameSpecifier:
-    return OS << "GlobalNameSpecifier";
-  case NodeKind::DecltypeNameSpecifier:
-    return OS << "DecltypeNameSpecifier";
-  case NodeKind::IdentifierNameSpecifier:
-    return OS << "IdentifierNameSpecifier";
-  case NodeKind::SimpleTemplateNameSpecifier:
-    return OS << "SimpleTemplateNameSpecifier";
+  case NodeKind::NameSpecifier:
+    return OS << "NameSpecifier";
+  case NodeKind::DecltypeSpecifier:
+    return OS << "DecltypeSpecifier";
+  case NodeKind::SimpleTemplateSpecifier:
+    return OS << "SimpleTemplateSpecifier";
   case NodeKind::NestedNameSpecifier:
     return OS << "NestedNameSpecifier";
   }
   llvm_unreachable("unknown node kind");
 }
 
 raw_ostream &syntax::operator<<(raw_ostream &OS, NodeRole R) {
   switch (R) {
raw_ostream &syntax::operator<<(raw_ostream &OS, NodeRole R) {
   case syntax::NodeRole::NestedNameSpecifier_delimiter:
     return OS << "NestedNameSpecifier_delimiter";
   case syntax::NodeRole::ParenExpression_subExpression:
     return OS << "ParenExpression_subExpression";
   }
   llvm_unreachable("invalid role");
 }
 
+llvm::PointerUnion<syntax::EmptyNode *, syntax::Leaf *,
+                   syntax::DecltypeSpecifier *,
+                   syntax::SimpleTemplateSpecifier *>
+syntax::NameSpecifier::child() {
+  return llvm::PointerUnion<
+      syntax::EmptyNode *, syntax::Leaf *, syntax::DecltypeSpecifier *,
+      syntax::SimpleTemplateSpecifier *>::getFromOpaqueValue(firstChild());
+}
+
 std::vector<syntax::Leaf *> syntax::NestedNameSpecifier::delimiters() {
   std::vector<syntax::Leaf *> Children;
   for (auto *C = firstChild(); C; C = C->nextSibling()) {
     assert(C->role() == syntax::NodeRole::NestedNameSpecifier_delimiter);
     Children.push_back(llvm::cast<syntax::Leaf>(C));
   }
   return Children;
 }

clang/lib/Tooling/Syntax/Tree.cpp

 syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
   assert(Tok != nullptr);
 }
 
 bool syntax::Leaf::classof(const Node *N) {
   return N->kind() == NodeKind::Leaf;
 }
 
+syntax::EmptyNode::EmptyNode() : Node(NodeKind::EmptyNode) {}
+
+bool syntax::EmptyNode::classof(const Node *N) {
+  return N->kind() == NodeKind::EmptyNode;
+}
+
 syntax::Node::Node(NodeKind Kind)
     : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
       Role(0), Original(false), CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
 bool syntax::Node::isDetached() const { return role() == NodeRole::Detached; }
 

clang/unittests/Tooling/Syntax/TreeTest.cpp

`-SimpleDeclaration
   |   `-)
   `-CompoundStatement
     |-{
     |-ExpressionStatement
     | |-UnknownExpression
     | | |-IdExpression
     | | | |-NestedNameSpecifier
     | | | | |-::
-    | | | | |-IdentifierNameSpecifier
+    | | | | |-NameSpecifier
     | | | | | `-n
     | | | | |-::
-    | | | | |-IdentifierNameSpecifier
+    | | | | |-NameSpecifier
     | | | | | `-S
     | | | | |-::
-    | | | | |-SimpleTemplateNameSpecifier
-    | | | | | |-template
-    | | | | | |-ST
-    | | | | | |-<
-    | | | | | |-int
-    | | | | | `->
+    | | | | |-NameSpecifier
+    | | | | | `-SimpleTemplateSpecifier
+    | | | | |   |-template
+    | | | | |   |-ST
+    | | | | |   |-<
+    | | | | |   |-int
+    | | | | |   `->
     | | | | `-::
     | | | `-UnqualifiedId
     | | |   `-f
     | | |-(
     | | `-)
     | `-;
     |-ExpressionStatement
     | |-UnknownExpression
     | | |-IdExpression
     | | | |-NestedNameSpecifier
-    | | | | |-IdentifierNameSpecifier
+    | | | | |-NameSpecifier
     | | | | | `-n
     | | | | |-::
-    | | | | |-IdentifierNameSpecifier
+    | | | | |-NameSpecifier
     | | | | | `-S
     | | | | |-::
-    | | | | |-SimpleTemplateNameSpecifier
-    | | | | | |-ST
-    | | | | | |-<
-    | | | | | |-int
-    | | | | | `->
+    | | | | |-NameSpecifier
+    | | | | | `-SimpleTemplateSpecifier
+    | | | | |   |-ST
+    | | | | |   |-<
+    | | | | |   |-int
+    | | | | |   `->
     | | | | `-::
     | | | `-UnqualifiedId
     | | |   `-f
     | | |-(
     | | `-)
     | `-;
     |-ExpressionStatement
     | |-UnknownExpression
     | | |-IdExpression
     | | | |-NestedNameSpecifier
-    | | | | |-SimpleTemplateNameSpecifier
-    | | | | | |-ST
-    | | | | | |-<
-    | | | | | |-int
-    | | | | | `->
+    | | | | |-NameSpecifier
+    | | | | | `-SimpleTemplateSpecifier
+    | | | | |   |-ST
+    | | | | |   |-<
+    | | | | |   |-int
+    | | | | |   `->
     | | | | |-::
-    | | | | |-IdentifierNameSpecifier
+    | | | | |-NameSpecifier
     | | | | | `-S
     | | | | `-::
     | | | `-UnqualifiedId
     | | |   |-f
     | | |   |-<
     | | |   |-int
     | | |   `->
     | | |-(
     | | `-)
     | `-;
     |-ExpressionStatement
     | |-UnknownExpression
     | | |-IdExpression
     | | | |-NestedNameSpecifier
-    | | | | |-SimpleTemplateNameSpecifier
-    | | | | | |-ST
-    | | | | | |-<
-    | | | | | |-int
-    | | | | | `->
+    | | | | |-NameSpecifier
+    | | | | | `-SimpleTemplateSpecifier
+    | | | | |   |-ST
+    | | | | |   |-<
+    | | | | |   |-int
+    | | | | |   `->
     | | | | |-::
-    | | | | |-IdentifierNameSpecifier
+    | | | | |-NameSpecifier
     | | | | | `-S
     | | | | `-::
     | | | |-template
     | | | `-UnqualifiedId
     | | |   |-f
     | | |   |-<
     | | |   |-int
     | | |   `->
`-SimpleDeclaration
     |   |-(
     |   `-)
     `-CompoundStatement
       |-{
       |-ExpressionStatement
       | |-UnknownExpression
       | | |-IdExpression
       | | | |-NestedNameSpecifier
-      | | | | |-IdentifierNameSpecifier
+      | | | | |-NameSpecifier
       | | | | | `-T
       | | | | |-::
-      | | | | |-SimpleTemplateNameSpecifier
-      | | | | | |-template
-      | | | | | |-U
-      | | | | | |-<
-      | | | | | |-int
-      | | | | | `->
+      | | | | |-NameSpecifier
+      | | | | | `-SimpleTemplateSpecifier
+      | | | | |   |-template
+      | | | | |   |-U
+      | | | | |   |-<
+      | | | | |   |-int
+      | | | | |   `->
       | | | | `-::
       | | | `-UnqualifiedId
       | | |   `-f
       | | |-(
       | | `-)
       | `-;
       |-ExpressionStatement
       | |-UnknownExpression
       | | |-IdExpression
       | | | |-NestedNameSpecifier
-      | | | | |-IdentifierNameSpecifier
+      | | | | |-NameSpecifier
       | | | | | `-T
       | | | | |-::
-      | | | | |-IdentifierNameSpecifier
+      | | | | |-NameSpecifier
       | | | | | `-U
       | | | | `-::
       | | | `-UnqualifiedId
       | | |   `-f
       | | |-(
       | | `-)
       | `-;
       |-ExpressionStatement
       | |-UnknownExpression
       | | |-IdExpression
       | | | |-NestedNameSpecifier
-      | | | | |-IdentifierNameSpecifier
+      | | | | |-NameSpecifier
       | | | | | `-T
       | | | | `-::
       | | | |-template
       | | | `-UnqualifiedId
       | | |   |-f
       | | |   |-<
       | | |   |-IntegerLiteralExpression
       | | |   | `-0
`-SimpleDeclaration
   |   |   `-s
   |   `-)
   `-CompoundStatement
     |-{
     |-ExpressionStatement
     | |-UnknownExpression
     | | |-IdExpression
     | | | |-NestedNameSpecifier
-    | | | | |-DecltypeNameSpecifier
-    | | | | | |-decltype
-    | | | | | |-(
-    | | | | | |-IdExpression
-    | | | | | | `-UnqualifiedId
-    | | | | | |   `-s
-    | | | | | `-)
+    | | | | |-NameSpecifier
+    | | | | | `-DecltypeSpecifier
+    | | | | |   |-decltype
+    | | | | |   |-(
+    | | | | |   |-IdExpression
+    | | | | |   | `-UnqualifiedId
+    | | | | |   |   `-s
+    | | | | |   `-)
     | | | | `-::
     | | | `-UnqualifiedId
     | | |   `-f
     | | |-(
     | | `-)
     | `-;
     `-}
 )txt"));