[RFC][clangd] Check if SelectionTree is complete

[kuganv]

Summary

clangd in the presence of compilation error can navigate to completely irrelevant destinations. This is often a problem for headers that cannot be compiled standalone. For example, go-to-def often jumps to containing namespace because the selection tree just consists of namespace (when relevant AST nodes were missing due to compilation error). This is known issue that is hard to solve without using some heuristic. One such heuristic is to check the nodes in the selection tree for the exact line match. In the absence of such match, we do not provide navigation. IMO, this is better than jumping to wrong position.

TODO:

• This currently does not have test cases but I will add test cases based on the feedback for the heuristic.
• Enable only when there is compilation error.

[kuganv]

Rebased

[kuganv]

ping? Any thoughts. Thanks.

[ArcsinX]

One such heuristic is to check the nodes in the selection tree for the exact line match

It looks like this heuristic doesn't work well in multiline cases.
E.g.

int
f^unc() {
  return 0;
}

will give empty result with this patch applied.

clang-tools-extra/clangd/Selection.h

struct Node {
     const Node &outerImplicit() const;
   };
   // The most specific common ancestor of all the selected nodes.
   // Returns nullptr if the common ancestor is the root.
   // (This is to avoid accidentally traversing the TUDecl and thus preamble).
   const Node *commonAncestor() const;
   // The selection node corresponding to TranslationUnitDecl.
   const Node &root() const { return *Root; }
+  bool TochesSourceLoc(SourceLocation Pos, const SourceManager &SM);
 
 private:
   // Creates a selection tree for the given range in the main file.
   // The range includes bytes [Start, End).
   SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens,
                 unsigned Start, unsigned End);
 
   std::deque<Node> Nodes; // Stable-pointer storage.

clang-tools-extra/clangd/Selection.cpp

const Node *SelectionTree::commonAncestor() const {
   while (Ancestor->Children.size() == 1 && !Ancestor->Selected)
     Ancestor = Ancestor->Children.front();
   // Returning nullptr here is a bit unprincipled, but it makes the API safer:
   // the TranslationUnitDecl contains all of the preamble, so traversing it is a
   // performance cliff. Callers can check for null and use root() if they want.
   return Ancestor != Root ? Ancestor : nullptr;
 }
 
+// Check if source line at Pos touches any node in SelectionTree. In the
+// presence of compilation error, we will have only root nodes without the
+// nodes that coresponds to tokens from Pos. In these cases, clangd cannot
+// provide meaningful navigation and often jumps to the conataining scope
+// identifier such as napespace.
+bool SelectionTree::TochesSourceLoc(SourceLocation Pos,
+                                    const SourceManager &SM) {
+  const auto DecomposedPos = SM.getDecomposedSpellingLoc(Pos);
+  int Line = SM.getLineNumber(DecomposedPos.first, DecomposedPos.second);
+  for (const auto &Node : Nodes) {
+    const auto Begin =
+        SM.getDecomposedSpellingLoc(getSourceRange(Node.ASTNode).getBegin());
+    const auto End =
+        SM.getDecomposedSpellingLoc(getSourceRange(Node.ASTNode).getEnd());
+    int startLine = SM.getLineNumber(Begin.first, Begin.second);
+    int endLine = SM.getLineNumber(End.first, End.second);
+    if (startLine == Line || endLine == Line) {
+      return true;
+    }
+  }
+  return false;
+}
+
 const DeclContext &SelectionTree::Node::getDeclContext() const {
   for (const Node *CurrentNode = this; CurrentNode != nullptr;
        CurrentNode = CurrentNode->Parent) {
     if (const Decl *Current = CurrentNode->ASTNode.get<Decl>()) {
       if (CurrentNode != this)
         if (auto *DC = dyn_cast<DeclContext>(Current))
           return *DC;
       return *Current->getLexicalDeclContext();

clang-tools-extra/clangd/XRefs.cpp

 
 std::vector<std::pair<const NamedDecl *, DeclRelationSet>>
 getDeclAtPositionWithRelations(ParsedAST &AST, SourceLocation Pos,
                                DeclRelationSet Relations,
                                ASTNodeKind *NodeKind = nullptr) {
   unsigned Offset = AST.getSourceManager().getDecomposedSpellingLoc(Pos).second;
   std::vector<std::pair<const NamedDecl *, DeclRelationSet>> Result;
   auto ResultFromTree = [&](SelectionTree ST) {
+    // If the SelectionTree does not have nodes from Pos, we will navigate to
+    // wrong locations. In these cases, it is better to return empty results
+    // rather than jumping to irrelevant location.
+    if (!ST.TochesSourceLoc(Pos, AST.getSourceManager())) {
+      return false;
+    }
     if (const SelectionTree::Node *N = ST.commonAncestor()) {
       if (NodeKind)
         *NodeKind = N->ASTNode.getNodeKind();
       // Attributes don't target decls, look at the
       // thing it's attached to.
       // We still report the original NodeKind!
       // This makes the `override` hack work.
       if (N->ASTNode.get<Attr>() && N->Parent)