[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

1224–1225

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.

794–868

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

849–850

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

clang/unittests/Tooling/Syntax/TreeTest.cpp

1224–1225

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

[gribozavr2]

clang/include/clang/AST/NestedNameSpecifier.h

20

534

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

539

Inline is implied here.

544

Inline is implied here.

550

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

clang/lib/Tooling/Syntax/BuildTree.cpp

770

[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

838–842

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.

849–850

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/include/clang/AST/NestedNameSpecifier.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_NESTEDNAMESPECIFIER_H
 #define LLVM_CLANG_AST_NESTEDNAMESPECIFIER_H
 
 #include "clang/AST/DependenceFlags.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/Support/Compiler.h"
 #include <cstdint>
 #include <cstdlib>
 #include <utility>
 
 namespace clang {
inline const DiagnosticBuilder &operator<<(const DiagnosticBuilder &DB,
                                            NestedNameSpecifier *NNS) {
   DB.AddTaggedVal(reinterpret_cast<intptr_t>(NNS),
                   DiagnosticsEngine::ak_nestednamespec);
   return DB;
 }
 
 } // namespace clang
 
+namespace llvm {
+
+template <> struct DenseMapInfo<clang::NestedNameSpecifierLoc> {
+  using FirstInfo = DenseMapInfo<clang::NestedNameSpecifier *>;
+  using SecondInfo = DenseMapInfo<void *>;
+
+  static clang::NestedNameSpecifierLoc getEmptyKey() {
+    return clang::NestedNameSpecifierLoc(FirstInfo::getEmptyKey(),
+                                         SecondInfo::getEmptyKey());
+  }
+
+  static clang::NestedNameSpecifierLoc getTombstoneKey() {
+    return clang::NestedNameSpecifierLoc(FirstInfo::getTombstoneKey(),
+                                         SecondInfo::getTombstoneKey());
+  }
+
+  static unsigned getHashValue(const clang::NestedNameSpecifierLoc &PairVal) {
+    return hash_combine(
+        FirstInfo::getHashValue(PairVal.getNestedNameSpecifier()),
+        SecondInfo::getHashValue(PairVal.getOpaqueData()));
+  }
+
+  static bool isEqual(const clang::NestedNameSpecifierLoc &LHS,
+                      const clang::NestedNameSpecifierLoc &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
 #endif // LLVM_CLANG_AST_NESTEDNAMESPECIFIER_H

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 {
 /// 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");
   }
 
+  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(ASTPtr P) const { return Nodes.lookup(P); }
 
+  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:
   /// Populate children for \p New node, assuming it covers tokens from \p
   /// Range.
   void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New, ASTPtr From) {
     assert(New);
     Pending.foldChildren(Arena, Range, New);
     if (From)
       Mapping.add(From, New);
   }
+
   void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New, TypeLoc L) {
     // FIXME: add mapping for TypeLocs
     foldNode(Range, New, nullptr);
   }
 
-  void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New,
-                NestedNameSpecifierLoc L) {
-    // FIXME: add mapping for NestedNameSpecifierLoc
-    foldNode(Range, New, nullptr);
+  void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
+                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.
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) {
+  // 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::NodeKind getNameSpecifierKind(const NestedNameSpecifier &NNS) {
     switch (NNS.getKind()) {
     case NestedNameSpecifier::Global:
-      return new (allocator()) syntax::GlobalNameSpecifier;
+      return syntax::NodeKind::GlobalNameSpecifier;
     case NestedNameSpecifier::Namespace:
     case NestedNameSpecifier::NamespaceAlias:
     case NestedNameSpecifier::Identifier:
-      return new (allocator()) syntax::IdentifierNameSpecifier;
+      return syntax::NodeKind::IdentifierNameSpecifier;
     case NestedNameSpecifier::TypeSpecWithTemplate:
-      return new (allocator()) syntax::SimpleTemplateNameSpecifier;
+      return syntax::NodeKind::SimpleTemplateNameSpecifier;
     case NestedNameSpecifier::TypeSpec: {
       const auto *NNSType = NNS.getAsType();
       assert(NNSType);
       if (isa<DecltypeType>(NNSType))
-        return new (allocator()) syntax::DecltypeNameSpecifier;
+        return syntax::NodeKind::DecltypeNameSpecifier;
       if (isa<TemplateSpecializationType, DependentTemplateSpecializationType>(
               NNSType))
-        return new (allocator()) syntax::SimpleTemplateNameSpecifier;
-      return new (allocator()) syntax::IdentifierNameSpecifier;
+        return syntax::NodeKind::SimpleTemplateNameSpecifier;
+      return syntax::NodeKind::IdentifierNameSpecifier;
     }
-    case NestedNameSpecifier::Super:
+    default:
       // FIXME: Support Microsoft's __super
       llvm::report_fatal_error("We don't yet support the __super specifier",
                                true);
     }
-    llvm_unreachable("Unhandled NestedNameSpecifier::SpecifierKind enum");
   }
 
-  // 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());
-      }
+  syntax::NameSpecifier *
+  BuildNameSpecifier(const NestedNameSpecifierLoc &NNSLoc) {
+    assert(NNSLoc.hasQualifier());
+    auto NameSpecifierTokens =
+        Builder.getRange(getLocalSourceRange(NNSLoc)).drop_back();
+    switch (getNameSpecifierKind(*NNSLoc.getNestedNameSpecifier())) {
+    case syntax::NodeKind::GlobalNameSpecifier:
+      return new (allocator()) syntax::GlobalNameSpecifier;
+    case syntax::NodeKind::IdentifierNameSpecifier: {
+      assert(NameSpecifierTokens.size() == 1);
+      Builder.markChildToken(NameSpecifierTokens.begin(),
+                             syntax::NodeRole::Unknown);
+      auto *NS = new (allocator()) syntax::IdentifierNameSpecifier;
+      Builder.foldNode(NameSpecifierTokens, NS, nullptr);
+      return NS;
+    }
+    case syntax::NodeKind::SimpleTemplateNameSpecifier: {
+      // TODO: Build `SimpleTemplateNameSpecifier` children and implement
+      // accessors to them.
+      // Be aware, we cannot do that simply by calling `TraverseTypeLoc`,
+      // some `TypeLoc`s have inside them the previous name specifier and
+      // we want to treat them independently.
+      auto *NS = new (allocator()) syntax::SimpleTemplateNameSpecifier;
+      Builder.foldNode(NameSpecifierTokens, NS, nullptr);
+      return NS;
+    }
+    case syntax::NodeKind::DecltypeNameSpecifier: {
+      const auto TL = NNSLoc.getTypeLoc().castAs<DecltypeTypeLoc>();
+      if (!RecursiveASTVisitor::TraverseDecltypeTypeLoc(TL))
+        return nullptr;
+      auto *NS = new (allocator()) syntax::DecltypeNameSpecifier;
+      // TODO: Implement accessor to `DecltypeNameSpecifier` inner
+      // `DecltypeTypeLoc`.
+      // For that add mapping from `TypeLoc` to `syntax::Node*` then:
+      // Builder.markChild(TypeLoc, syntax::NodeRole);
+      Builder.foldNode(NameSpecifierTokens, NS, nullptr);
+      return NS;
+    default:
+      llvm_unreachable("getChildKind() does not return this value");
     }
-
-    return SR;
   }
 
-  syntax::NestedNameSpecifier *
-  BuildNestedNameSpecifier(const NestedNameSpecifierLoc &QualifierLoc) {
+  // 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.
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc QualifierLoc) {
     if (!QualifierLoc)
-      return nullptr;
+      return true;
     for (auto it = QualifierLoc; it; it = it.getPrefix()) {
-      assert(it.hasQualifier());
-      auto *NS = BuildNameSpecifier(*it.getNestedNameSpecifier());
-      assert(NS);
-      if (!isa<syntax::GlobalNameSpecifier>(NS))
-        Builder.foldNode(Builder.getRange(getLocalSourceRange(it)).drop_back(),
-                         NS, it);
+      auto *NS = BuildNameSpecifier(it);
+      if (!NS)
+        return false;
       Builder.markChild(NS, syntax::NodeRole::List_element);
       Builder.markChildToken(it.getEndLoc(), syntax::NodeRole::List_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;
   }
 
   // Same logic as DeclRefExpr.
   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;
 
void syntax::TreeBuilder::markChild(syntax::Node *N, NodeRole R) {
   setRole(N, R);
 }
 
 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

clang/unittests/Tooling/Syntax/TreeTest.cpp

`-SimpleDeclaration
   |   | `-SimpleDeclarator
   |   |   `-s
   |   `-)
   `-CompoundStatement
     |-{
     |-ExpressionStatement
     | |-UnknownExpression
     | | |-IdExpression
     | | | |-NestedNameSpecifier
     | | | | |-DecltypeNameSpecifier
     | | | | | |-decltype
     | | | | | |-(
     | | | | | |-IdExpression
     | | | | | | `-UnqualifiedId
     | | | | | |   `-s
     | | | | | `-)
     | | | | `-::
     | | | `-UnqualifiedId

 |-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
+  | |-IdentifierNameSpecifier
+  | | `-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
+    | |-SimpleTemplateNameSpecifier
+    | | |-X
+    | | |-<
+    | | |-T
+    | | `->
+    | `-::
     |-Y
     |-{
     |-}
     `-;
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, TemplatesUsingUsing) {
`-TemplateDeclaration
   | `-T
   |->
   `-SimpleDeclaration
     |-struct
     |-X
     |-{
     |-UsingDeclaration
     | |-using
-    | |-T
-    | |-::
+    | |-NestedNameSpecifier
+    | | |-IdentifierNameSpecifier
+    | | | `-T
+    | | `-::
     | |-foo
     | `-;
     |-UsingDeclaration
     | |-using
     | |-typename
-    | |-T
-    | |-::
+    | |-NestedNameSpecifier
+    | | |-IdentifierNameSpecifier
+    | | | `-T
+    | | `-::
     | |-bar
     | `-;
     |-}
     `-;
 )txt"));
 }
 
 TEST_P(SyntaxTreeTest, ExplicitTemplateInstantations) {