[clangd] Fix SelectionTree traversal of qualified types

[sammccall]

Summary

QualifiedTypeLoc isn't treated like a regular citizen by RecursiveASTVisitor.
This meant we weren't intercepting the traversal of its inner TypeLoc.

Most of the changes here are about exposing kind() so we can improve the
precision of our tests.

This should fix the issue raised in D65067.

clang-tools-extra/trunk/clangd/Selection.h

struct Node {
     llvm::SmallVector<const Node *, 8> Children;
     // The corresponding node from the full AST.
     ast_type_traits::DynTypedNode ASTNode;
     // The extent to which this node is covered by the selection.
     Selection Selected;
     // Walk up the AST to get the DeclContext of this Node,
     // which is not the node itself.
     const DeclContext& getDeclContext() const;
+    // Printable node kind, like "CXXRecordDecl" or "AutoTypeLoc".
+    std::string kind() const;
   };
   // The most specific common ancestor of all the selected nodes.
   // If there is no selection, this is nullptr.
   const Node *commonAncestor() const;
   // The selection node corresponding to TranslationUnitDecl.
   // If there is no selection, this is nullptr.
   const Node *root() const { return Root; }
 

clang-tools-extra/trunk/clangd/Selection.cpp

for (const auto &R : Ranges) {
       }
     }
     return false;
   }
 
   std::vector<std::pair<unsigned, unsigned>> Ranges; // Always sorted.
 };
 
-// Dump a node for debugging.
-// DynTypedNode::print() doesn't include the kind of node, which is useful.
-void printNode(llvm::raw_ostream &OS, const DynTypedNode &N,
-               const PrintingPolicy &PP) {
+// Show the type of a node for debugging.
+void printNodeKind(llvm::raw_ostream &OS, const DynTypedNode &N) {
   if (const TypeLoc *TL = N.get<TypeLoc>()) {
     // TypeLoc is a hierarchy, but has only a single ASTNodeKind.
     // Synthesize the name from the Type subclass (except for QualifiedTypeLoc).
     if (TL->getTypeLocClass() == TypeLoc::Qualified)
       OS << "QualifiedTypeLoc";
     else
       OS << TL->getType()->getTypeClassName() << "TypeLoc";
   } else {
     OS << N.getNodeKind().asStringRef();
   }
-  OS << " ";
-  N.print(OS, PP);
 }
 
 std::string printNodeToString(const DynTypedNode &N, const PrintingPolicy &PP) {
   std::string S;
   llvm::raw_string_ostream OS(S);
-  printNode(OS, N, PP);
+  printNodeKind(OS, N);
+  OS << " ";
   return std::move(OS.str());
 }
 
 // We find the selection by visiting written nodes in the AST, looking for nodes
 // that intersect with the selected character range.
 //
 // While traversing, we maintain a parent stack. As nodes pop off the stack,
 // we decide whether to keep them or not. To be kept, they must either be
if (canSafelySkipNode(N))
       return false;
     push(std::move(N));
     return true;
   }
   bool dataTraverseStmtPost(Stmt *X) {
     pop();
     return true;
   }
+  // QualifiedTypeLoc is handled strangely in RecursiveASTVisitor: the derived
+  // TraverseTypeLoc is not called for the inner UnqualTypeLoc.
+  // This means we'd never see 'int' in 'const int'! Work around that here.
+  // (The reason for the behavior is to avoid traversing the nested Type twice,
+  // but we ignore TraverseType anyway).
+  bool TraverseQualifiedTypeLoc(QualifiedTypeLoc QX) {
+    return traverseNode<TypeLoc>(
+        &QX, [&] { return TraverseTypeLoc(QX.getUnqualifiedLoc()); });
+  }
   // Uninteresting parts of the AST that don't have locations within them.
   bool TraverseNestedNameSpecifier(NestedNameSpecifier *) { return true; }
   bool TraverseType(QualType) { return true; }
 
 private:
   using Base = RecursiveASTVisitor<SelectionVisitor>;
 
   SelectionVisitor(ASTContext &AST, const PrintingPolicy &PP, unsigned SelBegin,

 
 void SelectionTree::print(llvm::raw_ostream &OS, const SelectionTree::Node &N,
                           int Indent) const {
   if (N.Selected)
     OS.indent(Indent - 1) << (N.Selected == SelectionTree::Complete ? '*'
                                                                     : '.');
   else
     OS.indent(Indent);
-  printNode(OS, N.ASTNode, PrintPolicy);
+  printNodeKind(OS, N.ASTNode);
+  OS << ' ';
+  N.ASTNode.print(OS, PrintPolicy);
   OS << "\n";
   for (const Node *Child : N.Children)
     print(OS, *Child, Indent + 2);
 }
 
+std::string SelectionTree::Node::kind() const {
+  std::string S;
+  llvm::raw_string_ostream OS(S);
+  printNodeKind(OS, ASTNode);
+  return std::move(OS.str());
+}
+
 // Decide which selection emulates a "point" query in between characters.
 static std::pair<unsigned, unsigned> pointBounds(unsigned Offset, FileID FID,
                                                  ASTContext &AST) {
   StringRef Buf = AST.getSourceManager().getBufferData(FID);
   // Edge-cases where the choice is forced.
   if (Buf.size() == 0)
     return {0, 0};
   if (Offset == 0)

clang-tools-extra/trunk/clangd/unittests/SelectionTests.cpp

auto FileRange =
       toHalfOpenFileRange(SM, LangOpts, N->ASTNode.getSourceRange());
   assert(FileRange && "We should be able to get the File Range");
   return Range{
       offsetToPosition(Buffer, SM.getFileOffset(FileRange->getBegin())),
       offsetToPosition(Buffer, SM.getFileOffset(FileRange->getEnd()))};
 }
 
 std::string nodeKind(const SelectionTree::Node *N) {
-  if (!N)
-    return "<null>";
-  return N->ASTNode.getNodeKind().asStringRef().str();
+  return N ? N->kind() : "<null>";
 }
 
 std::vector<const SelectionTree::Node *> allNodes(const SelectionTree &T) {
   std::vector<const SelectionTree::Node *> Result = {T.root()};
   for (unsigned I = 0; I < Result.size(); ++I) {
     const SelectionTree::Node *N = Result[I];
     Result.insert(Result.end(), N->Children.begin(), N->Children.end());
   }
Case Cases[] = {
           )cpp",
           "NestedNameSpecifierLoc",
       },
       {
           R"cpp(
             struct AAA { struct BBB { static int ccc(); };};
             int x = AAA::[[B^B^B]]::ccc();
           )cpp",
-          "TypeLoc",
+          "RecordTypeLoc",
       },
       {
           R"cpp(
             struct AAA { struct BBB { static int ccc(); };};
             int x = AAA::[[B^BB^]]::ccc();
           )cpp",
-          "TypeLoc",
+          "RecordTypeLoc",
       },
       {
           R"cpp(
             struct AAA { struct BBB { static int ccc(); };};
             int x = [[AAA::BBB::c^c^c]]();
           )cpp",
           "DeclRefExpr",
       },
Case Cases[] = {
             [[S ^s = "foo"]];
           )cpp",
           "VarDecl",
       },
       {
           R"cpp(
             [[^void]] (*S)(int) = nullptr;
           )cpp",
-          "TypeLoc",
+          "BuiltinTypeLoc",
       },
       {
           R"cpp(
             [[void (*S)^(int)]] = nullptr;
           )cpp",
-          "TypeLoc",
+          "FunctionProtoTypeLoc",
       },
       {
           R"cpp(
             [[void (^*S)(int)]] = nullptr;
           )cpp",
-          "TypeLoc",
+          "FunctionProtoTypeLoc",
       },
       {
           R"cpp(
             [[void (*^S)(int) = nullptr]];
           )cpp",
           "VarDecl",
       },
       {
           R"cpp(
             [[void ^(*S)(int)]] = nullptr;
           )cpp",
-          "TypeLoc",
+          "FunctionProtoTypeLoc",
       },
 
       // Point selections.
       {"void foo() { [[^foo]](); }", "DeclRefExpr"},
       {"void foo() { [[f^oo]](); }", "DeclRefExpr"},
       {"void foo() { [[fo^o]](); }", "DeclRefExpr"},
       {"void foo() { [[foo^()]]; }", "CallExpr"},
       {"void foo() { [[foo^]] (); }", "DeclRefExpr"},
       {"int bar; void foo() [[{ foo (); }]]^", "CompoundStmt"},
 
       // Tricky case: FunctionTypeLoc in FunctionDecl has a hole in it.
-      {"[[^void]] foo();", "TypeLoc"},
-      {"[[void foo^()]];", "TypeLoc"},
+      {"[[^void]] foo();", "BuiltinTypeLoc"},
+      {"[[void foo^()]];", "FunctionProtoTypeLoc"},
       {"[[^void foo^()]];", "FunctionDecl"},
       {"[[void ^foo()]];", "FunctionDecl"},
       // Tricky case: two VarDecls share a specifier.
       {"[[int ^a]], b;", "VarDecl"},
       {"[[int a, ^b]];", "VarDecl"},
       // Tricky case: anonymous struct is a sibling of the VarDecl.
       {"[[st^ruct {int x;}]] y;", "CXXRecordDecl"},
       {"[[struct {int x;} ^y]];", "VarDecl"},
       {"struct {[[int ^x]];} y;", "FieldDecl"},
+      // FIXME: the AST has no location info for qualifiers.
+      {"const [[a^uto]] x = 42;", "AutoTypeLoc"},
+      {"[[co^nst auto x = 42]];", "VarDecl"},
 
       {"^", nullptr},
       {"void foo() { [[foo^^]] (); }", "DeclRefExpr"},
 
       // FIXME: Ideally we'd get a declstmt or the VarDecl itself here.
       // This doesn't happen now; the RAV doesn't traverse a node containing ;.
       {"int x = 42;^", nullptr},
       {"int x = 42^;", nullptr},
 
       // Node types that have caused problems in the past.
-      {"template <typename T> void foo() { [[^T]] t; }", "TypeLoc"},
+      {"template <typename T> void foo() { [[^T]] t; }",
+       "TemplateTypeParmTypeLoc"},
 
       // No crash
       {
           R"cpp(
             template <class T> struct Foo {};
             template <[[template<class> class /*cursor here*/^U]]>
              struct Foo<U<int>*> {};
           )cpp",