[SyntaxTree] Expand support for `NestedNameSpecifier`

[eduucaldas]

Summary

We want NestedNameSpecifier syntax nodes to be generally supported, not
only for DeclRefExpr and DependentScopedDeclRefExpr.

To achieve this we:

• Use the RecursiveASTVisitor's API to traverse NestedNameSpecifierLocs and automatically create its syntax nodes
• Add links from the NestedNameSpecifierLocs to their syntax nodes.

In this way, from any semantic construct that has a NestedNameSpecifier,
we implicitly generate its syntax node via RAV and we can easily access
this syntax node via the links we added.

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

Closed by https://reviews.llvm.org/rGf9500cc487573c55ea37b4ee6e9162d115753a48

[eduucaldas]

clang/lib/Tooling/Syntax/BuildTree.cpp

227–254

Inpired on the definition of:

• template<typename T> struct DenseMapInfo<T*>
• template<typename T, typename U> struct DenseMapInfo<std::pair<T,U>>

Please tell me if this is all silly.

clang/unittests/Tooling/Syntax/TreeTest.cpp

1235

standard TraverseNestedNameSpecifierLoc fired TraverseTypeLoc, once we override it we lost this. This will be fixed when refining the Node for DecltypeSpecifier

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

227–254

This is the right way to use DenseMapInfo, just move the specialization into the file that defines NNSLoc.

892

Please add a comment that explains why we override Traverse for NNSLoc instead of WalkUpFrom.

Something like:

To build syntax tree nodes for NestedNameSpecifierLoc we override Traverse instead of WalkUpFrom because we want to traverse the children ourselves and build a list instead of a nested tree of name specifier prefixes.

[eduucaldas]

Move to using inheritance

[eduucaldas]

.

[eduucaldas]

Now NNS are based on inheritance!

clang/lib/Tooling/Syntax/BuildTree.cpp

947–948

Since we are overriding the TraverseNestedNameSpecifierLoc that previously fired TraverseTypeLoc we fire it when building a NameSpecifier.

clang/unittests/Tooling/Syntax/TreeTest.cpp

1235

This is no longer an issue, because we now fire TraverseTypeLoc in the case of DecltypeNameSpecifier

[gribozavr2]

clang/include/clang/AST/NestedNameSpecifier.h

20 ↗

(On Diff #284285)

534 ↗

(On Diff #284285)

I'd suggest to remove the comment because it repeats the API (this is the only reason to define a DenseMapInfo specialization).

539 ↗

(On Diff #284285)

Inline is implied here.

544 ↗

(On Diff #284285)

Inline is implied here.

550 ↗

(On Diff #284285)

Please use hash_combine instead of this internal API (see an example in include/clang/Sema/Sema.h).

clang/lib/Tooling/Syntax/BuildTree.cpp

802

[eduucaldas]

There are some refinements to do, to generate a complete syntax tree. Namely tag decltype-name-specifier and simple-template-specifier children with roles, to allow for accessors.

clang/lib/Tooling/Syntax/BuildTree.cpp

936–940

Let's generate the syntax tree for the nested-name-specifier:

T::template U<int>::X::

T and X are just identifier-name-specifiers. They are easy.

template U<int> however is a simple-template-name-specifier.

simple-template-name-specifier :
  template_opt simple-template-id

We could generate it by traversing the corresponding semantic node. But this node is a DependentTemplateSpecializationTypeLoc and it covers T::template U<int>. The traversal would then cover T:: and thus generate a crash.

As such, we should treat simple-template-name-specifier in a less generic way.

947–948

As opposed to simple-template-name-specifier, we can here use a normal traversal to build the decltype-name-specifier because this specifier doesn't cross boundaries of name specifiers

[eduucaldas]

Answer comments

clang/lib/Tooling/Syntax/BuildTree.cpp

if (Initializer.isValid()) {
     auto InitializerEnd = Initializer.getEnd();
     assert(SM.isBeforeInTranslationUnit(End, InitializerEnd) ||
            End == InitializerEnd);
     End = InitializerEnd;
   }
   return SourceRange(Start, End);
 }
 
+namespace llvm {
+template <> struct DenseMapInfo<clang::NestedNameSpecifierLoc> {
+  using FirstInfo = DenseMapInfo<clang::NestedNameSpecifier *>;
+  using SecondInfo = DenseMapInfo<void *>;
+
+  static inline NestedNameSpecifierLoc getEmptyKey() {
+    return NestedNameSpecifierLoc(FirstInfo::getEmptyKey(),
+                                  SecondInfo::getEmptyKey());
+  }
+
+  static inline NestedNameSpecifierLoc getTombstoneKey() {
+    return NestedNameSpecifierLoc(FirstInfo::getTombstoneKey(),
+                                  SecondInfo::getTombstoneKey());
+  }
+
+  static unsigned getHashValue(const clang::NestedNameSpecifierLoc &PairVal) {
+    return detail::combineHashValue(
+        FirstInfo::getHashValue(PairVal.getNestedNameSpecifier()),
+        SecondInfo::getHashValue(PairVal.getOpaqueData()));
+  }
+
+  static bool isEqual(const NestedNameSpecifierLoc &LHS,
+                      const NestedNameSpecifierLoc &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
 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
 /// complicated as we support more kinds of AST nodes, e.g. TypeLocs.
 /// FIXME: expose this as public API.
 class ASTToSyntaxMapping {
 public:
   void add(ASTPtr From, syntax::Tree *To) {
     assert(To != nullptr);
     assert(!From.isNull());
 
     bool Added = Nodes.insert({From, To}).second;
     (void)Added;
     assert(Added && "mapping added twice");
   }
 
   syntax::Tree *find(ASTPtr P) const { return Nodes.lookup(P); }
 
+  void add(NestedNameSpecifierLoc From, syntax::Tree *To) {
+    assert(To != nullptr);
+    assert(From.hasQualifier());
+
+    bool Added = NNSNodes.insert({From, To}).second;
+    (void)Added;
+    assert(Added && "mapping added twice");
+  }
+
+  syntax::Tree *find(NestedNameSpecifierLoc P) const {
+    return NNSNodes.lookup(P);
+  }
+
 private:
   llvm::DenseMap<ASTPtr, syntax::Tree *> Nodes;
+  llvm::DenseMap<NestedNameSpecifierLoc, syntax::Tree *> NNSNodes;
 };
 } // namespace
 
 /// A helper class for constructing the syntax tree while traversing a clang
 /// AST.
 ///
 /// At each point of the traversal we maintain a list of pending nodes.
 /// Initially all tokens are added as pending nodes. When processing a clang AST
public:
   }
   void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
                 TypeLoc L) {
     // FIXME: add mapping for TypeLocs
     foldNode(Range, New, nullptr);
   }
 
   void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
-                NestedNameSpecifierLoc L) {
-    // FIXME: add mapping for NestedNameSpecifierLoc
-    foldNode(Range, New, nullptr);
+                NestedNameSpecifierLoc From) {
+    assert(New);
+    Pending.foldChildren(Arena, Range, New);
+    if (From)
+      Mapping.add(From, New);
   }
   /// Notifies that we should not consume trailing semicolon when computing
   /// token range of \p D.
   void noticeDeclWithoutSemicolon(Decl *D);
 
   /// Mark the \p Child node with a corresponding \p Role. All marked children
   /// should be consumed by foldNode.
   /// When called on expressions (clang::Expr is derived from clang::Stmt),
   /// wraps expressions into expression statement.
   void markStmtChild(Stmt *Child, NodeRole Role);
   /// Should be called for expressions in non-statement position to avoid
   /// wrapping into expression statement.
   void markExprChild(Expr *Child, NodeRole Role);
   /// Set role for a token starting at \p Loc.
   void markChildToken(SourceLocation Loc, NodeRole R);
   /// Set role for \p T.
   void markChildToken(const syntax::Token *T, NodeRole R);
 
   /// Set role for \p N.
   void markChild(syntax::Node *N, NodeRole R);
   /// Set role for the syntax node matching \p N.
   void markChild(ASTPtr N, NodeRole R);
 
+  /// Set role for the syntax node matching \p N.
+  void markChild(NestedNameSpecifierLoc N, NodeRole R);
+
   /// Finish building the tree and consume the root node.
   syntax::TranslationUnit *finalize() && {
     auto Tokens = Arena.tokenBuffer().expandedTokens();
     assert(!Tokens.empty());
     assert(Tokens.back().kind() == tok::eof);
 
     // Build the root of the tree, consuming all the children.
     Pending.foldChildren(Arena, Tokens.drop_back(),
bool WalkUpFromUserDefinedLiteral(UserDefinedLiteral *S) {
     Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);
     Builder.foldNode(Builder.getExprRange(S), buildUserDefinedLiteral(S), S);
     return true;
   }
 
   // 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
default:
       llvm_unreachable("getChildKind() does not return this value");
     }
 
     auto *NS = new (allocator()) syntax::NameSpecifier;
     Builder.foldNode(NameSpecifierTokens, NS, nullptr);
     return NS;
   }
 
-  syntax::NestedNameSpecifier *
-  BuildNestedNameSpecifier(const NestedNameSpecifierLoc &QualifierLoc) {
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc QualifierLoc) {
     if (!QualifierLoc)
-      return nullptr;
+      return true;
     for (auto it = QualifierLoc; it; it = it.getPrefix()) {
       auto *NS = BuildNameSpecifier(it);
       assert(NS);
       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,
+    Builder.foldNode(Builder.getRange(QualifierLoc.getSourceRange()),
+                     new (allocator()) syntax::NestedNameSpecifier,
                      QualifierLoc);
-    return NNS;
+    return true;
   }
 
   bool WalkUpFromDeclRefExpr(DeclRefExpr *S) {
-    auto *Qualifier = BuildNestedNameSpecifier(S->getQualifierLoc());
-    if (Qualifier)
-      Builder.markChild(Qualifier, syntax::NodeRole::IdExpression_qualifier);
-
+    if (auto QualifierLoc = S->getQualifierLoc()) {
+      Builder.markChild(QualifierLoc, syntax::NodeRole::IdExpression_qualifier);
+    }
     auto TemplateKeywordLoc = S->getTemplateKeywordLoc();
     if (TemplateKeywordLoc.isValid())
       Builder.markChildToken(TemplateKeywordLoc,
                              syntax::NodeRole::TemplateKeyword);
 
     auto *unqualifiedId = new (allocator()) syntax::UnqualifiedId;
 
     Builder.foldNode(Builder.getRange(S->getLocation(), S->getEndLoc()),
                      unqualifiedId, nullptr);
 
     Builder.markChild(unqualifiedId, syntax::NodeRole::IdExpression_id);
 
     Builder.foldNode(Builder.getExprRange(S),
                      new (allocator()) syntax::IdExpression, S);
     return true;
   }
 
   // FIXME: Same logic as DeclRefExpr. How to DRY
   bool WalkUpFromDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *S) {
-    auto *Qualifier = BuildNestedNameSpecifier(S->getQualifierLoc());
-    if (Qualifier)
-      Builder.markChild(Qualifier, syntax::NodeRole::IdExpression_qualifier);
-
+    if (auto QualifierLoc = S->getQualifierLoc()) {
+      Builder.markChild(QualifierLoc, syntax::NodeRole::IdExpression_qualifier);
+    }
     auto TemplateKeywordLoc = S->getTemplateKeywordLoc();
     if (TemplateKeywordLoc.isValid())
       Builder.markChildToken(TemplateKeywordLoc,
                              syntax::NodeRole::TemplateKeyword);
 
     auto *unqualifiedId = new (allocator()) syntax::UnqualifiedId;
 
     Builder.foldNode(Builder.getRange(S->getLocation(), S->getEndLoc()),
                      unqualifiedId, nullptr);
 
     Builder.markChild(unqualifiedId, syntax::NodeRole::IdExpression_id);
 
     Builder.foldNode(Builder.getExprRange(S),
                      new (allocator()) syntax::IdExpression, S);
     return true;
   }
 
   bool WalkUpFromParenExpr(ParenExpr *S) {
     Builder.markChildToken(S->getLParen(), syntax::NodeRole::OpenParen);
     Builder.markExprChild(S->getSubExpr(),
                           syntax::NodeRole::ParenExpression_subExpression);
     Builder.markChildToken(S->getRParen(), syntax::NodeRole::CloseParen);
     Builder.foldNode(Builder.getExprRange(S),

 }
 
 void syntax::TreeBuilder::markChild(ASTPtr N, NodeRole R) {
   auto *SN = Mapping.find(N);
   assert(SN != nullptr);
   setRole(SN, R);
 }
 
+void syntax::TreeBuilder::markChild(NestedNameSpecifierLoc NNSLoc, NodeRole R) {
+  auto *SN = Mapping.find(NNSLoc);
+  assert(SN != nullptr);
+  setRole(SN, R);
+}
+
 void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
   if (!Child)
     return;
 
   syntax::Tree *ChildNode;
   if (Expr *ChildExpr = dyn_cast<Expr>(Child)) {
     // This is an expression in a statement position, consume the trailing
     // semicolon and form an 'ExpressionStatement' node.

clang/unittests/Tooling/Syntax/TreeTest.cpp

`-CompoundStatement
     |-ExpressionStatement
     | |-UnknownExpression
     | | |-IdExpression
     | | | |-NestedNameSpecifier
     | | | | |-NameSpecifier
     | | | | | `-DecltypeSpecifier
     | | | | |   |-decltype
     | | | | |   |-(
-    | | | | |   |-IdExpression
-    | | | | |   | `-UnqualifiedId
-    | | | | |   |   `-s
+    | | | | |   |-s
     | | | | |   `-)
     | | | | `-::
     | | | `-UnqualifiedId
     | | |   `-f
     | | |-(
     | | `-)
     | `-;
     `-}

 |-NamespaceDefinition
 | |-namespace
 | |-ns
 | |-{
 | `-}
 `-UsingNamespaceDirective
   |-using
   |-namespace
-  |-::
+  |-NestedNameSpecifier
+  | `-::
   |-ns
   `-;
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, UsingDeclaration) {
   if (!GetParam().isCXX()) {
     return;

 | |-SimpleDeclaration
 | | |-int
 | | |-SimpleDeclarator
 | | | `-a
 | | `-;
 | `-}
 `-UsingDeclaration
   |-using
-  |-ns
-  |-::
+  |-NestedNameSpecifier
+  | |-NameSpecifier
+  | | `-ns
+  | `-::
   |-a
   `-;
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, FreeStandingClasses) {
   // Free-standing classes, must live inside a SimpleDeclaration.
   EXPECT_TRUE(treeDumpEqual(
`-TemplateDeclaration
   |-template
   |-<
   |-UnknownDeclaration
   | |-class
   | `-T
   |->
   `-SimpleDeclaration
     |-struct
-    |-X
-    |-<
-    |-T
-    |->
-    |-::
+    |-NestedNameSpecifier
+    | |-NameSpecifier
+    | | `-SimpleTemplateSpecifier
+    | |   |-X
+    | |   |-<
+    | |   |-T
+    | |   `->
+    | `-::
     |-Y
     |-{
     |-}
     `-;
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, TemplatesUsingUsing) {
`-TemplateDeclaration
   | `-T
   |->
   `-SimpleDeclaration
     |-struct
     |-X
     |-{
     |-UsingDeclaration
     | |-using
-    | |-T
-    | |-::
+    | |-NestedNameSpecifier
+    | | |-NameSpecifier
+    | | | `-T
+    | | `-::
     | |-foo
     | `-;
     |-UsingDeclaration
     | |-using
     | |-typename
-    | |-T
-    | |-::
+    | |-NestedNameSpecifier
+    | | |-NameSpecifier
+    | | | `-T
+    | | `-::
     | |-bar
     | `-;
     |-}
     `-;
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, ExplicitTemplateInstantations) {