[clangd] Include macro expansions in documentSymbol hierarchy

[sammccall]

Summary

Browsing macro-generated symbols is confusing.
On the one hand, it seems very *useful* to be able to see the summary of
symbols that were generated.
On the other hand, some macros spew a lot of confusing symbols into the
namespace and when used repeatedly (ABSL_FLAG) can create a lot of spam
that's hard to navigate.

Design constraints:

• the macro expansion tree need not align with the AST, though it often does in practice. We address this by defining the nesting based on the *primary* location of decls, rather than their ranges.
• DocumentSymbol.children[*].range should nest within DocumentSymbol.range (This constraint is not in LSP "breadcrumbs" breaks without it) We adjust macro ranges so they cover their "children", rather than just the macro expansion
• LSP does not have a "macro expansion" symbolkind, nor does it allow a symbol to have no kind. I've arbitrarily picked "null" as this is unlikely to conflict with anything useful.

This patch makes all macros and children visible for simplicity+consistency,
though in some cases it may be better to elide the macro node.
We may consider adding heuristics for this in future (e.g. when it expands
to one decl only?) but it doesn't seem clear-cut to me.

[sammccall]

Before:

After:

[kadircet]

thanks, LGTM. with a couple nits and asking for some extra clarifications :)

clang-tools-extra/clangd/FindSymbols.cpp

303

nit: drop this one?

310

this comment feels a little out-of-place, maybe move it next to possibleMacroContainer call?

347

nit:

Sym.range = Sym.selectionRange = halfOpenToRange(SM, Tok.range(SM).toCharRange(SM));
if (Exp) {
  Sym.range = .... // cover Exp;
  // Populate Sym.detail.
}

420

also mention that there's at most one node for each macro invocation in the document symbol hierarchy, even if it yields multiple decls

442

nit:

SourceLocation ExpansionLoc = Loc;
// If ExpansionLoc is inside a macro argument, use the outer macro invocation instead. e.g:
//    #define ID(X) X
//    ID(int y); // chose location of ID, not X
if(SM.isMacroArgExpansion(ExpansionLoc))
  ExpansionLoc = SM.getImmediateExpansionRange(Loc).getBegin();
FileID MacroBody = SM.getFileID(ExpansionLoc);

clang-tools-extra/clangd/FindSymbols.cpp

 /// directly instead of using RecursiveASTVisitor (RAV) for three main reasons:
 ///    - there is no way to keep RAV from traversing subtrees we are not
 ///      interested in. E.g. not traversing function locals or implicit template
 ///      instantiations.
 ///    - it's easier to combine results of recursive passes,
 ///    - visiting decls is actually simple, so we don't hit the complicated
 ///      cases that RAV mostly helps with (types, expressions, etc.)
 class DocumentOutline {
+  // A DocumentSymbol we're constructing.
+  // We use this instead of DocumentSymbol directly so that we can keep track
+  // of the nodes we insert for macros.
+  class SymBuilder {
+    std::vector<SymBuilder> Children;
+    DocumentSymbol Symbol; // Symbol.children is empty, use Children instead.
+    // Macro expansions that this node or its parents are associated with.
+    // (Thus we will never create further children for these expansions).
+    llvm::SmallVector<SourceLocation> EnclosingMacroLoc;
+
+  public:
+    DocumentSymbol build() && {
+      for (SymBuilder &C : Children) {
+        Symbol.children.push_back(std::move(C).build());
+        // Expand range to ensure children nest properly, which editors expect.
+        // This can fix some edge-cases in the AST, but is vital for macros.
+        // A macro expansion "contains" AST node if it covers the node's primary
+        // location, but it may not span the node's whole range.
+        Symbol.range.start =
+            std::min(Symbol.range.start, Symbol.children.back().range.start);
+        Symbol.range.end =
+            std::max(Symbol.range.end, Symbol.children.back().range.end);
+      }
+      return std::move(Symbol);
+    }
+
+    // Add a symbol as a child of the current one.
+    SymBuilder &addChild(DocumentSymbol S) {
+      Children.emplace_back();
+      Children.back().EnclosingMacroLoc = EnclosingMacroLoc;
+      Children.back().Symbol = std::move(S);
+      return Children.back();
+    }
+
+    // Get an appropriate container for children of this symbol that were
+    // expanded from a macro (whose spelled name is Tok).
+    //
+    // This may return:
+    //  - a macro symbol child of this (either new or previously created)
+    //  - this scope itself, if it *is* the macro symbol or is nested within it
+    SymBuilder &inMacro(const syntax::Token &Tok, const SourceManager &SM,
+                        llvm::Optional<syntax::TokenBuffer::Expansion> Exp) {
+      if (llvm::is_contained(EnclosingMacroLoc, Tok.location()))
+        return *this;
+      // If there's an existing child for this macro, we expect it to be last.
+      if (!Children.empty() && !Children.back().EnclosingMacroLoc.empty() &&
+          Children.back().EnclosingMacroLoc.back() == Tok.location())
+        return Children.back();
+
+      DocumentSymbol Sym;
+      Sym.name = Tok.text(SM).str();
+      Sym.kind = SymbolKind::Null; // There's no suitable kind!
+      Sym.range = Sym.selectionRange =
+          halfOpenToRange(SM, Tok.range(SM).toCharRange(SM));
+
+      // FIXME: Exp is currently unavailable for nested expansions.
+      if (Exp) {
+        // Full range covers the macro args.
+        Sym.range = halfOpenToRange(SM, CharSourceRange::getCharRange(
+                                            Exp->Spelled.front().location(),
+                                            Exp->Spelled.back().endLocation()));
+        // Show macro args as detail.
+        llvm::raw_string_ostream OS(Sym.detail);
+        const syntax::Token *Prev = nullptr;
+        for (const auto &Tok : Exp->Spelled.drop_front()) {
+          // Don't dump arbitrarily long macro args.
+          if (OS.tell() > 80) {
+            OS << " ...)";
+            break;
+          }
+          if (Prev && Prev->endLocation() != Tok.location())
+            OS << ' ';
+          OS << Tok.text(SM);
+          Prev = &Tok;
+        }
+      }
+      SymBuilder &Child = addChild(std::move(Sym));
+      Child.EnclosingMacroLoc.push_back(Tok.location());
+      return Child;
+    }
+  };
+
 public:
   DocumentOutline(ParsedAST &AST) : AST(AST) {}
 
   /// Builds the document outline for the generated AST.
   std::vector<DocumentSymbol> build() {
-    std::vector<DocumentSymbol> Results;
+    SymBuilder DummyRoot;
     for (auto &TopLevel : AST.getLocalTopLevelDecls())
-      traverseDecl(TopLevel, Results);
-    return Results;
+      traverseDecl(TopLevel, DummyRoot);
+    return std::move(std::move(DummyRoot).build().children);
   }
 
 private:
   enum class VisitKind { No, OnlyDecl, OnlyChildren, DeclAndChildren };
 
-  void traverseDecl(Decl *D, std::vector<DocumentSymbol> &Results) {
+  void traverseDecl(Decl *D, SymBuilder &Parent) {
     // Skip symbols which do not originate from the main file.
     if (!isInsideMainFile(D->getLocation(), AST.getSourceManager()))
       return;
 
     if (auto *Templ = llvm::dyn_cast<TemplateDecl>(D)) {
       // TemplatedDecl might be null, e.g. concepts.
       if (auto *TD = Templ->getTemplatedDecl())
         D = TD;
     }
 
     VisitKind Visit = shouldVisit(D);
     if (Visit == VisitKind::No)
       return;
 
     if (Visit == VisitKind::OnlyChildren)
-      return traverseChildren(D, Results);
+      return traverseChildren(D, Parent);
 
     auto *ND = llvm::cast<NamedDecl>(D);
     auto Sym = declToSym(AST.getASTContext(), *ND);
     if (!Sym)
       return;
-    Results.push_back(std::move(*Sym));
+    SymBuilder &MacroParent = possibleMacroContainer(D->getLocation(), Parent);
+    SymBuilder &Child = MacroParent.addChild(std::move(*Sym));
 
     if (Visit == VisitKind::OnlyDecl)
       return;
 
     assert(Visit == VisitKind::DeclAndChildren && "Unexpected VisitKind");
-    traverseChildren(ND, Results.back().children);
+    traverseChildren(ND, Child);
+  }
+
+  // Determines where a decl should appear in the DocumentSymbol hierarchy.
+  //
+  // This is usually a direct child of the relevant AST parent.
+  // But we may also insert nodes for macros. Given:
+  //   #define DECLARE_INT(V) int v;
+  //   namespace a { DECLARE_INT(x) }
+  // We produce:
+  //   Namespace a
+  //     Macro DECLARE_INT(x)
+  //       Variable x
+  //
+  // In the absence of macros, this method simply returns Parent.
+  // Otherwise it may return a macro expansion node instead.
+  // Each macro only has at most one node in the hierarchy, even if it expands
+  // to multiple decls.
+  SymBuilder &possibleMacroContainer(SourceLocation TargetLoc,
+                                     SymBuilder &Parent) {
+    const auto &SM = AST.getSourceManager();
+    // Look at the path of macro-callers from the token to the main file.
+    // Note that along these paths we see the "outer" macro calls first.
+    SymBuilder *CurParent = &Parent;
+    for (SourceLocation Loc = TargetLoc; Loc.isMacroID();
+         Loc = SM.getImmediateMacroCallerLoc(Loc)) {
+      // Find the virtual macro body that our token is being substituted into.
+      FileID MacroBody;
+      if (SM.isMacroArgExpansion(Loc)) {
+        // Loc is part of a macro arg being substituted into a macro body.
+        MacroBody = SM.getFileID(SM.getImmediateExpansionRange(Loc).getBegin());
+      } else {
+        // Loc is already in the macro body.
+        MacroBody = SM.getFileID(Loc);
+      }
+      // The macro body is being substituted for a macro expansion, whose
+      // first token is the name of the macro.
+      SourceLocation MacroName =
+          SM.getSLocEntry(MacroBody).getExpansion().getExpansionLocStart();
+      // Only include the macro expansion in the outline if it was written
+      // directly in the main file, rather than expanded from another macro.
+      if (!MacroName.isValid() || !MacroName.isFileID())
+        continue;
+      // All conditions satisfied, add the macro.
+      if (auto *Tok = AST.getTokens().spelledTokenAt(MacroName))
+        CurParent = &CurParent->inMacro(
+            *Tok, SM, AST.getTokens().expansionStartingAt(Tok));
+    }
+    return *CurParent;
   }
 
-  void traverseChildren(Decl *D, std::vector<DocumentSymbol> &Results) {
+  void traverseChildren(Decl *D, SymBuilder &Builder) {
     auto *Scope = llvm::dyn_cast<DeclContext>(D);
     if (!Scope)
       return;
     for (auto *C : Scope->decls())
-      traverseDecl(C, Results);
+      traverseDecl(C, Builder);
   }
 
   VisitKind shouldVisit(Decl *D) {
     if (D->isImplicit())
       return VisitKind::No;
 
     if (llvm::isa<LinkageSpecDecl>(D) || llvm::isa<ExportDecl>(D))
       return VisitKind::OnlyChildren;

clang-tools-extra/clangd/unittests/FindSymbolsTests.cpp

EXPECT_THAT(
           AllOf(WithName("Color2"), WithDetail("enum"),
                 Children(AllOf(WithName("Yellow"), WithDetail("Color2")))),
           AllOf(WithName("ns"),
                 Children(AllOf(WithName("(anonymous enum)"), WithDetail("enum"),
                                Children(AllOf(WithName("Black"),
                                               WithDetail("(unnamed)"))))))));
 }
 
-TEST(DocumentSymbols, FromMacro) {
+TEST(DocumentSymbols, Macro) {
+  struct Test {
+    const char *Code;
+    testing::Matcher<DocumentSymbol> Matcher;
+  } Tests[] = {
+      {
+          R"cpp(
+            // Basic macro that generates symbols.
+            #define DEFINE_FLAG(X) bool FLAGS_##X; bool FLAGS_no##X
+            DEFINE_FLAG(pretty);
+          )cpp",
+          AllOf(WithName("DEFINE_FLAG"), WithDetail("(pretty)"),
+                Children(WithName("FLAGS_pretty"), WithName("FLAGS_nopretty"))),
+      },
+      {
+          R"cpp(
+            // Hierarchy is determined by primary (name) location.
+            #define ID(X) X
+            namespace ID(ns) { int ID(y); }
+          )cpp",
+          AllOf(WithName("ID"), WithDetail("(ns)"),
+                Children(AllOf(WithName("ns"),
+                               Children(AllOf(WithName("ID"), WithDetail("(y)"),
+                                              Children(WithName("y"))))))),
+      },
+      {
+          R"cpp(
+            // More typical example where macro only generates part of a decl.
+            #define TEST(A, B) class A##_##B { void go(); }; void A##_##B::go()
+            TEST(DocumentSymbols, Macro) { }
+          )cpp",
+          AllOf(WithName("TEST"), WithDetail("(DocumentSymbols, Macro)"),
+                Children(AllOf(WithName("DocumentSymbols_Macro"),
+                               Children(WithName("go"))),
+                         WithName("DocumentSymbols_Macro::go"))),
+      },
+      {
+          R"cpp(
+            // Nested macros.
+            #define NAMESPACE(NS, BODY) namespace NS { BODY }
+            NAMESPACE(a, NAMESPACE(b, int x;))
+          )cpp",
+          AllOf(
+              WithName("NAMESPACE"), WithDetail("(a, NAMESPACE(b, int x;))"),
+              Children(AllOf(
+                  WithName("a"),
+                  Children(AllOf(WithName("NAMESPACE"),
+                                 // FIXME: nested expansions not in TokenBuffer
+                                 WithDetail(""),
+                                 Children(AllOf(WithName("b"),
+                                                Children(WithName("x"))))))))),
+      },
+      {
+          R"cpp(
+            // Macro invoked from body is not exposed.
+            #define INNER(X) int X
+            #define OUTER(X) INNER(X)
+            OUTER(foo);
+          )cpp",
+          AllOf(WithName("OUTER"), WithDetail("(foo)"),
+                Children(WithName("foo"))),
+      },
+  };
+  for (const Test &T : Tests) {
+    auto TU = TestTU::withCode(T.Code);
+    EXPECT_THAT(getSymbols(TU.build()), ElementsAre(T.Matcher)) << T.Code;
+  }
+}
+
+TEST(DocumentSymbols, RangeFromMacro) {
   TestTU TU;
   Annotations Main(R"(
     #define FF(name) \
       class name##_Test {};
 
     $expansion1[[FF]](abc);
 
     #define FF2() \
-      class Test {};
+      class Test {}
 
-    $expansion2[[FF2]]();
+    $expansion2parens[[$expansion2[[FF2]]()]];
 
     #define FF3() \
       void waldo()
 
     $fullDef[[FF3() {
       int var = 42;
     }]]
   )");
   TU.Code = Main.code().str();
-  EXPECT_THAT(getSymbols(TU.build()),
-              ElementsAre(AllOf(WithName("abc_Test"), WithDetail("class"),
-                                SymNameRange(Main.range("expansion1"))),
-                          AllOf(WithName("Test"), WithDetail("class"),
-                                SymNameRange(Main.range("expansion2"))),
-                          AllOf(WithName("waldo"), WithDetail("void ()"),
-                                SymRange(Main.range("fullDef")))));
+  EXPECT_THAT(
+      getSymbols(TU.build()),
+      ElementsAre(
+          AllOf(WithName("FF"), WithDetail("(abc)"),
+                Children(AllOf(WithName("abc_Test"), WithDetail("class"),
+                               SymNameRange(Main.range("expansion1"))))),
+          AllOf(WithName("FF2"), WithDetail("()"),
+                SymNameRange(Main.range("expansion2")),
+                SymRange(Main.range("expansion2parens")),
+                Children(AllOf(WithName("Test"), WithDetail("class"),
+                               SymNameRange(Main.range("expansion2"))))),
+          AllOf(WithName("FF3"), WithDetail("()"),
+                SymRange(Main.range("fullDef")),
+                Children(AllOf(WithName("waldo"), WithDetail("void ()"),
+                               SymRange(Main.range("fullDef")))))));
 }
 
 TEST(DocumentSymbols, FuncTemplates) {
   TestTU TU;
   Annotations Source(R"cpp(
     template <class T>
     T foo() {}