[clangd] Add dlog()s for SelectionTree, enabling -debug-only=SelectionTree.cpp

[sammccall]

Summary

SelectionTree is a RecursiveASTVisitor which processes getSourceRange() for
every node. This is a lot of surface area with the AST, as getSourceRange()
is specialized for *many* node types.
And the resulting SelectionTree depends on the source ranges of many
visited nodes, and the order of traversal.

Put together, this means we really need a traversal log to debug when we
get an unexpected SelectionTree. I've built this ad-hoc a few times, now
it's time to check it in.

Example output:

D[14:07:44.184] Computing selection for </usr/local/google/home/sammccall/test.cc:1:7, col:8>
D[14:07:44.184]  push: VarDecl const auto x = 42
D[14:07:44.184]   claimRange: </usr/local/google/home/sammccall/test.cc:1:12, col:13>
D[14:07:44.184]   push: NestedNameSpecifierLoc (empty NestedNameSpecifierLoc)
D[14:07:44.184]   pop: NestedNameSpecifierLoc (empty NestedNameSpecifierLoc)
D[14:07:44.184]   push: QualifiedTypeLoc const auto
D[14:07:44.184]   pop: QualifiedTypeLoc const auto
D[14:07:44.184]    claimRange: </usr/local/google/home/sammccall/test.cc:1:7, col:11>
D[14:07:44.184]    hit selection: </usr/local/google/home/sammccall/test.cc:1:7, col:8>
D[14:07:44.184]   skip: IntegerLiteral 42
D[14:07:44.184]    skipped range = </usr/local/google/home/sammccall/test.cc:1:16>
D[14:07:44.184]  pop: VarDecl const auto x = 42
D[14:07:44.184]   claimRange: </usr/local/google/home/sammccall/test.cc:1:1, col:18>
D[14:07:44.184]  skip: VarDecl int y = 43
D[14:07:44.184]   skipped range = </usr/local/google/home/sammccall/test.cc:2:1, col:9>
D[14:07:44.184] Built selection tree
TranslationUnitDecl
  VarDecl const auto x = 42
     .QualifiedTypeLoc const auto

[hokein]

looks good.

[bjope]

Since this patch we get

../../clang-tools-extra/clangd/Selection.cpp:80:13: error: unused function 'printNodeToString' [-Werror,-Wunused-function]
std::string printNodeToString(const DynTypedNode &N, const PrintingPolicy &PP) {
            ^
../../clang-tools-extra/clangd/Selection.cpp:351:25: error: private field 'PrintPolicy' is not used [-Werror,-Wunused-private-field]
  const PrintingPolicy &PrintPolicy;
                        ^
2 errors generated.

When building with -DNDEBUG and -Werror.

I guess we can sprinkle some ifndef NDEBUG in this file, but I'm not sure how these dlog statements normally are handled in clang-tools-extra. Should for example LLVM_ENABLE_DUMP also be used for clang-tools-extra?

[bjope]

In D65073#1603568, @bjope wrote:

Since this patch we get

../../clang-tools-extra/clangd/Selection.cpp:80:13: error: unused function 'printNodeToString' [-Werror,-Wunused-function]
std::string printNodeToString(const DynTypedNode &N, const PrintingPolicy &PP) {
            ^
../../clang-tools-extra/clangd/Selection.cpp:351:25: error: private field 'PrintPolicy' is not used [-Werror,-Wunused-private-field]
  const PrintingPolicy &PrintPolicy;
                        ^
2 errors generated.

When building with -DNDEBUG and -Werror.

I guess we can sprinkle some ifndef NDEBUG in this file, but I'm not sure how these dlog statements normally are handled in clang-tools-extra. Should for example LLVM_ENABLE_DUMP also be used for clang-tools-extra?

Well, I made a fix here: https://reviews.llvm.org/rL367178

cfe/trunk/lib/AST/ASTTypeTraits.cpp

 //  that can be used to store an AST base node at runtime in the same storage in
 //  a type safe way.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclCXX.h"
+#include "clang/AST/NestedNameSpecifier.h"
 
 namespace clang {
 namespace ast_type_traits {
 
 const ASTNodeKind::KindInfo ASTNodeKind::AllKindInfo[] = {
   { NKI_None, "<None>" },
   { NKI_None, "TemplateArgument" },
   { NKI_None, "TemplateName" },

 void DynTypedNode::print(llvm::raw_ostream &OS,
                          const PrintingPolicy &PP) const {
   if (const TemplateArgument *TA = get<TemplateArgument>())
     TA->print(PP, OS);
   else if (const TemplateName *TN = get<TemplateName>())
     TN->print(OS, PP);
   else if (const NestedNameSpecifier *NNS = get<NestedNameSpecifier>())
     NNS->print(OS, PP);
-  else if (const NestedNameSpecifierLoc *NNSL = get<NestedNameSpecifierLoc>())
-    NNSL->getNestedNameSpecifier()->print(OS, PP);
-  else if (const QualType *QT = get<QualType>())
+  else if (const NestedNameSpecifierLoc *NNSL = get<NestedNameSpecifierLoc>()) {
+    if (const NestedNameSpecifier *NNS = NNSL->getNestedNameSpecifier())
+      NNS->print(OS, PP);
+    else
+      OS << "(empty NestedNameSpecifierLoc)";
+  } else if (const QualType *QT = get<QualType>())
     QT->print(OS, PP);
   else if (const TypeLoc *TL = get<TypeLoc>())
     TL->getType().print(OS, PP);
   else if (const Decl *D = get<Decl>())
     D->print(OS, PP);
   else if (const Stmt *S = get<Stmt>())
     S->printPretty(OS, nullptr, PP);
   else if (const Type *T = get<Type>())

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

struct Node {
     // 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;
   };
-
   // 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; }
 
 private:

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

 //===--- Selection.cpp ----------------------------------------------------===//
 //
 // 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 "Selection.h"
 #include "ClangdUnit.h"
+#include "Logger.h"
 #include "SourceCode.h"
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/PrettyPrinter.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/TypeLoc.h"
+#include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/raw_ostream.h"
 #include <algorithm>
+#include <string>
 
 namespace clang {
 namespace clangd {
 namespace {
 using Node = SelectionTree::Node;
 using ast_type_traits::DynTypedNode;
 
 // Stores a collection of (possibly-overlapping) integer ranges.
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) {
+  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);
+  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
 // selected or contain some nodes that are.
 //
 // For simple cases (not inside macros) we prune subtrees that don't intersect.
 class SelectionVisitor : public RecursiveASTVisitor<SelectionVisitor> {
 public:
   // Runs the visitor to gather selected nodes and their ancestors.
   // If there is any selection, the root (TUDecl) is the first node.
-  static std::deque<Node> collect(ASTContext &AST, unsigned Begin,
-                                  unsigned End, FileID File) {
-    SelectionVisitor V(AST, Begin, End, File);
+  static std::deque<Node> collect(ASTContext &AST, const PrintingPolicy &PP,
+                                  unsigned Begin, unsigned End, FileID File) {
+    SelectionVisitor V(AST, PP, Begin, End, File);
     V.TraverseAST(AST);
     assert(V.Stack.size() == 1 && "Unpaired push/pop?");
     assert(V.Stack.top() == &V.Nodes.front());
     if (V.Nodes.size() == 1) // TUDecl, but no nodes under it.
       V.Nodes.clear();
     return std::move(V.Nodes);
   }
 
return traverseNode(
         &X, [&] { return Base::TraverseNestedNameSpecifierLoc(X); });
   }
   bool TraverseConstructorInitializer(CXXCtorInitializer *X) {
     return traverseNode(
         X, [&] { return Base::TraverseConstructorInitializer(X); });
   }
   // Stmt is the same, but this form allows the data recursion optimization.
   bool dataTraverseStmtPre(Stmt *X) {
-    if (!X || canSafelySkipNode(X->getSourceRange()))
+    if (!X)
+      return false;
+    auto N = DynTypedNode::create(*X);
+    if (canSafelySkipNode(N))
       return false;
-    push(DynTypedNode::create(*X));
+    push(std::move(N));
     return true;
   }
   bool dataTraverseStmtPost(Stmt *X) {
     pop();
     return true;
   }
   // 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, unsigned SelBegin, unsigned SelEnd,
-                   FileID SelFile)
+  SelectionVisitor(ASTContext &AST, const PrintingPolicy &PP, unsigned SelBegin,
+                   unsigned SelEnd, FileID SelFile)
       : SM(AST.getSourceManager()), LangOpts(AST.getLangOpts()),
-        SelBegin(SelBegin), SelEnd(SelEnd), SelFile(SelFile),
+        PrintPolicy(PP), SelBegin(SelBegin), SelEnd(SelEnd), SelFile(SelFile),
         SelBeginTokenStart(SM.getFileOffset(Lexer::GetBeginningOfToken(
             SM.getComposedLoc(SelFile, SelBegin), SM, LangOpts))) {
     // Ensure we have a node for the TU decl, regardless of traversal scope.
     Nodes.emplace_back();
     Nodes.back().ASTNode = DynTypedNode::create(*AST.getTranslationUnitDecl());
     Nodes.back().Parent = nullptr;
     Nodes.back().Selected = SelectionTree::Unselected;
     Stack.push(&Nodes.back());
   }
 
   // Generic case of TraverseFoo. Func should be the call to Base::TraverseFoo.
   // Node is always a pointer so the generic code can handle any null checks.
   template <typename T, typename Func>
   bool traverseNode(T *Node, const Func &Body) {
-    if (Node == nullptr || canSafelySkipNode(Node->getSourceRange()))
+    if (Node == nullptr)
+      return true;
+    auto N = DynTypedNode::create(*Node);
+    if (canSafelySkipNode(N))
       return true;
     push(DynTypedNode::create(*Node));
     bool Ret = Body();
     pop();
     return Ret;
   }
 
   // HIT TESTING
private:
   //                    ~~~~~ x
   //                    ~~~~~~~~ y
   // Here the first ("leftmost") sibling claims the tokens it wants, and the
   // other sibling gets what's left. So selecting "int" only includes the left
   // VarDecl in the selection tree.
 
   // An optimization for a common case: nodes outside macro expansions that
   // don't intersect the selection may be recursively skipped.
-  bool canSafelySkipNode(SourceRange S) {
+  bool canSafelySkipNode(const DynTypedNode &N) {
+    SourceRange S = N.getSourceRange();
     auto B = SM.getDecomposedLoc(S.getBegin());
     auto E = SM.getDecomposedLoc(S.getEnd());
+    // Node lies in a macro expansion?
     if (B.first != SelFile || E.first != SelFile)
       return false;
-    return B.second >= SelEnd || E.second < SelBeginTokenStart;
+    // Node intersects selection tokens?
+    if (B.second < SelEnd && E.second >= SelBeginTokenStart)
+      return false;
+    // Otherwise, allow skipping over the node.
+    dlog("{1}skip: {0}", printNodeToString(N, PrintPolicy), indent());
+    dlog("{1}skipped range = {0}", S.printToString(SM), indent(1));
+    return true;
   }
 
   // Pushes a node onto the ancestor stack. Pairs with pop().
   // Performs early hit detection for some nodes (on the earlySourceRange).
   void push(DynTypedNode Node) {
-    bool SelectedEarly = claimRange(earlySourceRange(Node));
+    SourceRange Early = earlySourceRange(Node);
+    dlog("{1}push: {0}", printNodeToString(Node, PrintPolicy), indent());
     Nodes.emplace_back();
     Nodes.back().ASTNode = std::move(Node);
     Nodes.back().Parent = Stack.top();
     // Early hit detection never selects the whole node.
-    Nodes.back().Selected =
-        SelectedEarly ? SelectionTree::Partial : SelectionTree::Unselected;
     Stack.push(&Nodes.back());
+    Nodes.back().Selected =
+        claimRange(Early) ? SelectionTree::Partial : SelectionTree::Unselected;
   }
 
   // Pops a node off the ancestor stack, and finalizes it. Pairs with push().
   // Performs primary hit detection.
   void pop() {
     Node &N = *Stack.top();
+    dlog("{1}pop: {0}", printNodeToString(N.ASTNode, PrintPolicy), indent(-1));
     if (auto Sel = claimRange(N.ASTNode.getSourceRange()))
       N.Selected = Sel;
     if (N.Selected || !N.Children.empty()) {
       // Attach to the tree.
       N.Parent->Children.push_back(&N);
     } else {
       // Neither N any children are selected, it doesn't belong in the tree.
       assert(&N == &Nodes.back());
SelectionTree::Selection claimRange(SourceRange S) {
     // toHalfOpenFileRange() allows selection of constructs in macro args. e.g:
     //   #define LOOP_FOREVER(Body) for(;;) { Body }
     //   void IncrementLots(int &x) {
     //     LOOP_FOREVER( ++x; )
     //   }
     // Selecting "++x" or "x" will do the right thing.
     auto Range = toHalfOpenFileRange(SM, LangOpts, S);
     assert(Range && "We should be able to get the File Range");
+    dlog("{1}claimRange: {0}", Range->printToString(SM), indent());
     auto B = SM.getDecomposedLoc(Range->getBegin());
     auto E = SM.getDecomposedLoc(Range->getEnd());
     // Otherwise, nodes in macro expansions can't be selected.
     if (B.first != SelFile || E.first != SelFile)
       return SelectionTree::Unselected;
     // Is there any overlap at all between the selection and range?
     if (B.second >= SelEnd || E.second < SelBegin)
       return SelectionTree::Unselected;
     // We may have hit something.
     auto PreciseBounds = std::make_pair(B.second, E.second);
     // Trim range using the selection, drop it if empty.
     B.second = std::max(B.second, SelBegin);
     E.second = std::min(E.second, SelEnd);
     if (B.second >= E.second)
       return SelectionTree::Unselected;
     // Attempt to claim the remaining range. If there's nothing to claim, only
     // children were selected.
     if (!Claimed.add(B.second, E.second))
       return SelectionTree::Unselected;
+    dlog("{1}hit selection: {0}",
+         SourceRange(SM.getComposedLoc(B.first, B.second),
+                     SM.getComposedLoc(E.first, E.second))
+             .printToString(SM),
+         indent());
     // Some of our own characters are covered, this is a true hit.
     // Determine whether the node was completely covered.
     return (PreciseBounds.first >= SelBegin && PreciseBounds.second <= SelEnd)
                ? SelectionTree::Complete
                : SelectionTree::Partial;
   }
 
+  std::string indent(int Offset = 0) {
+    // Cast for signed arithmetic.
+    int Amount = int(Stack.size()) + Offset;
+    assert(Amount >= 0);
+    return std::string(Amount, ' ');
+  }
+
   SourceManager &SM;
   const LangOptions &LangOpts;
+  const PrintingPolicy &PrintPolicy;
   std::stack<Node *> Stack;
   RangeSet Claimed;
   std::deque<Node> Nodes; // Stable pointers as we add more nodes.
   // Half-open selection range.
   unsigned SelBegin;
   unsigned SelEnd;
   FileID SelFile;
   // If the selection start slices a token in half, the beginning of that token.
   // This is useful for checking whether the end of a token range overlaps
   // the selection: range.end < SelBeginTokenStart is equivalent to
   // range.end + measureToken(range.end) < SelBegin (assuming range.end points
   // to a token), and it saves a lex every time.
   unsigned SelBeginTokenStart;
 };
 
 } // namespace
 
 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);
-  if (const TypeLoc *TL = N.ASTNode.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.ASTNode.getNodeKind().asStringRef();
-  }
-  OS << " ";
-  N.ASTNode.print(OS, PrintPolicy);
+  printNode(OS, N.ASTNode, PrintPolicy);
   OS << "\n";
   for (const Node *Child : N.Children)
     print(OS, *Child, Indent + 2);
 }
 
 // Decide which selection emulates a "point" query in between characters.
 static std::pair<unsigned, unsigned> pointBounds(unsigned Offset, FileID FID,
                                                  ASTContext &AST) {
if (isWhitespace(Buf[Offset]) && !isWhitespace(Buf[Offset - 1]))
     return {Offset - 1, Offset};
   return {Offset, Offset + 1};
 }
 
 SelectionTree::SelectionTree(ASTContext &AST, unsigned Begin, unsigned End)
     : PrintPolicy(AST.getLangOpts()) {
   // No fundamental reason the selection needs to be in the main file,
   // but that's all clangd has needed so far.
-  FileID FID = AST.getSourceManager().getMainFileID();
+  const SourceManager &SM = AST.getSourceManager();
+  FileID FID = SM.getMainFileID();
   if (Begin == End)
     std::tie(Begin, End) = pointBounds(Begin, FID, AST);
   PrintPolicy.TerseOutput = true;
   PrintPolicy.IncludeNewlines = false;
 
-  Nodes = SelectionVisitor::collect(AST, Begin, End, FID);
+  dlog("Computing selection for {0}",
+       SourceRange(SM.getComposedLoc(FID, Begin), SM.getComposedLoc(FID, End))
+           .printToString(SM));
+  Nodes = SelectionVisitor::collect(AST, PrintPolicy, Begin, End, FID);
   Root = Nodes.empty() ? nullptr : &Nodes.front();
+  dlog("Built selection tree\n{0}", *this);
 }
 
 SelectionTree::SelectionTree(ASTContext &AST, unsigned Offset)
     : SelectionTree(AST, Offset, Offset) {}
 
 const Node *SelectionTree::commonAncestor() const {
   if (!Root)
     return nullptr;