[clangd] A helper to find explicit references and their names

[ilya-biryukov]

Summary

Allows to simplify pending code tweaks:

• the upcoming DefineInline tweak (D66647)
• remove using declaration (D56612)
• qualify name under cursor (D56610)

Another potential future application is simplifying semantic highlighting.

[kadircet]

Thanks this mostly LG, but I think we need some tests feel free to copy the ones in D66647 as a start point. But I believe coverage for this one is bigger, as this tries to figure-out all references, whereas the define-inline patch only cares about references to non-local decls in contexts that can have a nested name specifier.

clang-tools-extra/clangd/FindTarget.cpp

369 ↗

(On Diff #220999)

could you add some comments on what it does

373 ↗

(On Diff #220999)

what is namedTarget ?

376 ↗

(On Diff #220999)

can we simplify this by populating two vectors, Instantiations and Patterns, and then returning the patterns iff instantiations are empty?

381 ↗

(On Diff #220999)

why do we discard aliases(specifically underlying decls) ? for example if we have vector<int> I believe decl(template<> std::vector<int>) will be marked with both TemplateInst and Underlying right ?

391 ↗

(On Diff #220999)

same here for ignoring underlying decls

399 ↗

(On Diff #220999)

these three(usingdirective,using,namespacealias) decls are the only ones that can have a nestednamespecifier.

Are we sure these are the only ones that can reference a decl? For example what about a ConstructorDecl with initializers referencing FieldDecls, I believe this function should rather return multiple locations in such cases.

409 ↗

(On Diff #220999)

I think getUsingLoc will return the location for using keyword, not the name location. Maybe use getLocation ?

426 ↗

(On Diff #220999)

again I believe this list is non-exhaustive, e.g. designatedinitilaizers. and again this also needs to return a vector instead.

432 ↗

(On Diff #220999)

I believe it is better to return getFoundDecl then getDecl, the former respects using declarations.

506 ↗

(On Diff #220999)

can we move this below ExplicitReferenceCollector to prevent splitting anon namespace?

548 ↗

(On Diff #220999)

why not just traversenestednamespecifier and visitNode(L) instead of calling the base::traverse ?

570 ↗

(On Diff #220999)

why not just visitNode(L) and traverse(prefix(L)) instead of calling base?

581 ↗

(On Diff #220999)

what is nodeReference?

594 ↗

(On Diff #220999)

So this endpoint doesn't seem to have downsides above(not visiting all referenced decls) as it performs traversal through an extra ASTVisitor.

What is the point of exposing the first method? Maybe we can getaway with not exposing it or strictly mentioning it might not return references in the children nodes?

clang-tools-extra/clangd/FindTarget.h

103 ↗

(On Diff #220999)

drop :wa ?

[kadircet]

clang-tools-extra/clangd/FindTarget.h

115 ↗

(On Diff #220999)

It might be better to accept a DynTypedNode in here as well, so that this can be used with other node types as well, or provide overrides for them(for example Decl).

[kadircet]

clang-tools-extra/clangd/FindTarget.h

93 ↗

(On Diff #220999)

do we have any real use-case for this field? apart from "skipping instance members in define inline"? because that one can also be achieved easily through decl (there is a isCXXInstanceMember).

[ilya-biryukov]

• Add simple tests
• Address other comments

[ilya-biryukov]

Added some tests too. More tests for dependent constructs are still missing, but please take a look at what we have for now.

clang-tools-extra/clangd/FindTarget.cpp

373 ↗

(On Diff #220999)

Used to be called this before. Fixed, thanks.

376 ↗

(On Diff #220999)

Did something very similar. PTAL.

381 ↗

(On Diff #220999)

For ^vector<int>, we get vector<int>(TemplateInstantiation) and vector(TemplatePattern).
No Underlying.

Added a relevant test-case.

391 ↗

(On Diff #220999)

As mentioned in the previous comment, we want to discard underlying. Underlying decl was not written in the source code, therefore should not be returned by this function.

399 ↗

(On Diff #220999)

This function is non-recursive and ConstructorInitializer is a separate node under ConsturctorDecl.
Any reference to fields are owned (and reported when ConstructorInitializer is visited)

There might be more decls that I missed here, though, hopefully we'll find and add them later.

It's a bit hard to get all cases on the first try.

409 ↗

(On Diff #220999)

Thanks for spotting this! This was supposed to be a temporary placeholder until I figure out a proper location.
But I forgot about it.

Fixed and added a test.

426 ↗

(On Diff #220999)

Added a FIXME to add more exhaustive handling.
I'll make sure to fix it soon, but would want to first land non-exhaustive version.

I would try avoiding returning more than one element here. For designated initializers we seem to have multiple designators. Since this function is non-recursive, it should not return those.

Instead we would require our clients (i.e. our visitor) to call a separate function for each of the designators.

432 ↗

(On Diff #220999)

Good point. Done. Added a test too.

548 ↗

(On Diff #220999)

To avoid re-implementing the traversal logic. Base::Traverse does exactly that, we shouldn't re-implement traversal ourselves.

570 ↗

(On Diff #220999)

For code reuse. See other comment too

581 ↗

(On Diff #220999)

Now renamed to explicitReference. Thanks.

594 ↗

(On Diff #220999)

I think we'll need it for D56610 (qualify name under cursor).
But happy to remove this from public API for now until we have a use-case for it.

Also updated a comment to explicitly mention it does not recurse into child nodes, hope its intention is clear now.

[kadircet]

clang-tools-extra/clangd/FindTarget.cpp

376 ↗

(On Diff #220999)

LG, thanks!

432 ↗

(On Diff #220999)

I was actually referring to DeclRefExpr, change seems to be on MemberExpr

548 ↗

(On Diff #220999)

I see but that should help get rid of TypeLocsToSkip and some extra traversals. I believe it would be worth getting rid of the additional state management, but up to you.

370 ↗

(On Diff #221345)

nit: s/a declaration/declaration(s)/

519 ↗

(On Diff #221345)

unnecessary closing and opening of anon namespace

577 ↗

(On Diff #221345)

:wa is still around have:wa references :D

609 ↗

(On Diff #221345)

I can see the second check is for getting rid of references coming from macro expansions. But what exactly is the first one for? How can we get an invalid nameloc, could you also add it as a comment?

clang-tools-extra/clangd/FindTarget.h

96 ↗

(On Diff #221345)

Is this for testing purposes? maybe move it into findtargettests.cpp or make it a member helper like Print(SourceManager&) so that it can also print locations etc.?

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

498 ↗

(On Diff #221345)

this sounds more like LastOffset or PrevOffset

504 ↗

(On Diff #221345)

I believe these are already filtered-out by findExplicitReferences ?

600 ↗

(On Diff #221345)

Is it OK for this case to be different than X::a above?

also shouldn't this be a::b::struct S or None ?(my preference would be towards None)

638 ↗

(On Diff #221345)

again qualifiers seems to be inconsistent with the rest of the cases.

[ilya-biryukov]

clang-tools-extra/clangd/FindTarget.cpp

432 ↗

(On Diff #220999)

Good point. Fixed that one too, thanks!

548 ↗

(On Diff #220999)

I like the idea and actually tried to implement it before, but failed. The nested-name-specifier case is simple and we could actually implement it.

However, the ElaboratedTypeLoc case is more complicated: we have to call Base::TraverseTypeLoc to make sure we recursively visit children of ElaboratedTypeLoc::getNamedType (e.g. template arguments inside the typeloc). However, Base::TraverseTypeLoc automatically calls VisitTypeLoc and our qualifier is forgotten again.

Let me know if there's a way to implement this that I missed, though.

577 ↗

(On Diff #221345)

Thanks. This slipped my attention last time :-)

609 ↗

(On Diff #221345)

Ah, thanks for spotting this. I don't think we want to filter out macro references, fixed that and added a test

The first one is a precaution against various implicit nodes getting into the traversal. Normally this shouldn't happen, unless:

• RecursiveASTVisitor has bugs and visits implicit nodes (e.g. generated begin() calls for range-based-for )
• Users start traversal from an implicitly-generated statement.

I couldn't come up with examples of that actually happening, but I'm also scared of adding an assertion as I feel this would inevitably fail at some point.
At the same time, the whole point of this function is to only expose those references that could be meaningfully found in the source code (e.g. for refactoring and syntax highlighting), i.e. they should always have (at least) source location of the name.

Added a comment, let me know if this could be made clearer, though.

clang-tools-extra/clangd/FindTarget.h

96 ↗

(On Diff #221345)

Yes, this is for output in the test. Moving to findTargetTests.cpp, we risk ODR violations in the future.
In any case, it's useful to have debug output and operator<< is common for that purpose: it enables llvm::toString and, consecutively, llvm::formatv("{0}", R).

What are the downsides of having it?

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

498 ↗

(On Diff #221345)

That's the next character in Code we need to process, renamed to NextCodeChar to specifically mention what string we're referring to.

504 ↗

(On Diff #221345)

Not anymore (wasn't supposed to in the first place). Added tests too.
See the other comment for details.

600 ↗

(On Diff #221345)

Qualifier captures exactly what's written in the source code, so it seems correct: S:: is what written down.
struct comes from the printing function in clang and I don't think it's worth changing. I believe this comes from the fact that qualifier is a type in this case.

Why would the qualifier be None? Maybe the purpose of this field is unclear?

638 ↗

(On Diff #221345)

There are no qualifiers written in the source code in any of the two references, therefore both qualifiers are empty.
Again, please let me know if the purpose of Qualifier is unclear. Happy to comment or change to make its purpose clear.

[ilya-biryukov]

• Use DeclRefExpr::getFoundDecl, add a test
• Update a comment
• Remove redundant anon namespace declaration
• Remove :wa
• Do not filter-out macro references
• Document why we drop references with invalid locations, log if that happens
• Rename NextOffset to NextCodeChar

[kadircet]

clang-tools-extra/clangd/FindTarget.h

96 ↗

(On Diff #221345)

I wasn't happy about it because it actually needs a SourceManager to print completely, and I believe that's also necessary for debugging.

But feel free to ignore if you're OK with that.

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

498 ↗

(On Diff #221345)

well, this looked more like "beginning of the last token we processed" to me. but now I see your point of view as well. Feel free to use whichever you want.

600 ↗

(On Diff #221345)

ah sorry, I missed the fact that this was written as S::type in the code, now it makes sense. just ignore this one.

638 ↗

(On Diff #221345)

yeah it totally makes sense now, the problem started with me missing the S:: in the previous example :D, nvm..

[ilya-biryukov]

• Remove ExprMemberBase
• Add an overload for Decl*

[ilya-biryukov]

I believe all comments were addressed. PTAL and let me know if I missed something.

clang-tools-extra/clangd/FindTarget.h

96 ↗

(On Diff #221345)

Having some llvm::toString is great, because it's nicely integrated to all of the infrastructure and very easy to use.
I'll stick with it for now, despite the limitations arising from the absence of source manager.

93 ↗

(On Diff #220999)

Thanks, this is definitely a valid concern. I was overthinking the problem, removed it.

115 ↗

(On Diff #220999)

I would avoid doing DynTypedNode - many of the cases don't quite make sense here, e.g. TypeLoc is arguably ok as it has location information, but Type* or QualType are not ok as they lack location information.

Decl definitely sounds useful, though. Would allow to visit all top-level decls of a file, which is another use-case we probably want. Added that.

[kadircet]

LGTM, thanks!

clang-tools-extra/clangd/FindTarget.h

103 ↗

(On Diff #221556)

nit: s/Decl *S/Decl *D/

[ilya-biryukov]

• s/Decl* S/Decl* D/g

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

 // Historically, we have used libIndex (IndexDataConsumer) to tie source
 // locations to referenced declarations. This file defines a more decoupled
 // approach based around AST nodes (DynTypedNode), and can be combined with
 // SelectionTree or other traversals.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/NestedNameSpecifier.h"
+#include "clang/AST/Stmt.h"
 #include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/raw_ostream.h"
 
 #include <bitset>
 
 namespace clang {
 namespace clangd {
 /// Describes the link between an AST node and a Decl it refers to.
 enum class DeclRelation : unsigned;
 /// A bitfield of DeclRelations.

 ///           [underlying]  [alias]
 ///                  /         \
 ///          RecordDecl S    TypeAliasDecl T
 ///
 /// FIXME: some AST nodes cannot be DynTypedNodes, these cannot be specified.
 llvm::SmallVector<const Decl *, 1>
 targetDecl(const ast_type_traits::DynTypedNode &, DeclRelationSet Mask);
 
+/// Information about a reference written in the source code, independent of the
+/// actual AST node that this reference lives in.
+/// Useful for tools that are source-aware, e.g. refactorings.
+struct ReferenceLoc {
+  /// Contains qualifier written in the code, if any, e.g. 'ns::' for 'ns::foo'.
+  NestedNameSpecifierLoc Qualifier;
+  /// Start location of the last name part, i.e. 'foo' in 'ns::foo<int>'.
+  SourceLocation NameLoc;
+  // FIXME: add info about template arguments.
+  /// A list of targets referenced by this name. Normally this has a single
+  /// element, but multiple is also possible, e.g. in case of using declarations
+  /// or unresolved overloaded functions.
+  /// For dependent and unresolved references, Targets can also be empty.
+  llvm::SmallVector<const NamedDecl *, 1> Targets;
+};
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R);
+
+/// Recursively traverse \p S and report all references explicitly written in
+/// the code. The main use-case is refactorings that need to process all
+/// references in some subrange of the file and apply simple edits, e.g. add
+/// qualifiers.
+/// FIXME: currently this does not report references to overloaded operators.
+/// FIXME: extend to report location information about declaration names too.
+void findExplicitReferences(Stmt *S,
+                            llvm::function_ref<void(ReferenceLoc)> Out);
+void findExplicitReferences(Decl *D,
+                            llvm::function_ref<void(ReferenceLoc)> Out);
+
 /// Similar to targetDecl(), however instead of applying a filter, all possible
 /// decls are returned along with their DeclRelationSets.
 /// This is suitable for indexing, where everything is recorded and filtering
 /// is applied later.
 llvm::SmallVector<std::pair<const Decl *, DeclRelationSet>, 1>
 allTargetDecls(const ast_type_traits::DynTypedNode &);
 
 enum class DeclRelation : unsigned {

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

 //===--- FindTarget.cpp - What does an AST node refer to? -----------------===//
 //
 // 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 "FindTarget.h"
 #include "AST.h"
 #include "Logger.h"
 #include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/DeclVisitor.h"
 #include "clang/AST/DeclarationName.h"
+#include "clang/AST/Expr.h"
 #include "clang/AST/ExprObjC.h"
+#include "clang/AST/NestedNameSpecifier.h"
+#include "clang/AST/PrettyPrinter.h"
+#include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/AST/Type.h"
+#include "clang/AST/TypeLoc.h"
 #include "clang/AST/TypeLocVisitor.h"
+#include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
+#include <utility>
 
 namespace clang {
 namespace clangd {
 namespace {
+using ast_type_traits::DynTypedNode;
 
 LLVM_ATTRIBUTE_UNUSED std::string
 nodeToString(const ast_type_traits::DynTypedNode &N) {
   std::string S = N.getNodeKind().asStringRef();
   {
     llvm::raw_string_ostream OS(S);
     OS << ": ";
     N.print(OS, PrintingPolicy(LangOptions()));
else if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>())
     Finder.add(CCI, Flags);
 
   return {Finder.Decls.begin(), Finder.Decls.end()};
 }
 
 llvm::SmallVector<const Decl *, 1>
 targetDecl(const ast_type_traits::DynTypedNode &N, DeclRelationSet Mask) {
   llvm::SmallVector<const Decl *, 1> Result;
-  for (const auto &Entry : allTargetDecls(N))
+  for (const auto &Entry : allTargetDecls(N)) {
     if (!(Entry.second & ~Mask))
       Result.push_back(Entry.first);
+  }
   return Result;
 }
 
+namespace {
+/// Find declarations explicitly referenced in the source code defined by \p N.
+/// For templates, will prefer to return a template instantiation whenever
+/// possible. However, can also return a template pattern if the specialization
+/// cannot be picked, e.g. in dependent code or when there is no corresponding
+/// Decl for a template instantitation, e.g. for templated using decls:
+///    template <class T> using Ptr = T*;
+///    Ptr<int> x;
+///    ^~~ there is no Decl for 'Ptr<int>', so we return the template pattern.
+llvm::SmallVector<const NamedDecl *, 1>
+explicitReferenceTargets(DynTypedNode N, DeclRelationSet Mask = {}) {
+  assert(!(Mask & (DeclRelation::TemplatePattern |
+                   DeclRelation::TemplateInstantiation)) &&
+         "explicitRefenceTargets handles templates on its own");
+  auto Decls = allTargetDecls(N);
+
+  // We prefer to return template instantiation, but fallback to template
+  // pattern if instantiation is not available.
+  Mask |= DeclRelation::TemplatePattern | DeclRelation::TemplateInstantiation;
+
+  llvm::SmallVector<const NamedDecl *, 1> TemplatePatterns;
+  llvm::SmallVector<const NamedDecl *, 1> Targets;
+  bool SeenTemplateInstantiations = false;
+  for (auto &D : Decls) {
+    if (D.second & ~Mask)
+      continue;
+    if (D.second & DeclRelation::TemplatePattern) {
+      TemplatePatterns.push_back(llvm::cast<NamedDecl>(D.first));
+      continue;
+    }
+    if (D.second & DeclRelation::TemplateInstantiation)
+      SeenTemplateInstantiations = true;
+    Targets.push_back(llvm::cast<NamedDecl>(D.first));
+  }
+  if (!SeenTemplateInstantiations)
+    Targets.insert(Targets.end(), TemplatePatterns.begin(),
+                   TemplatePatterns.end());
+  return Targets;
+}
+
+Optional<ReferenceLoc> refInDecl(const Decl *D) {
+  struct Visitor : ConstDeclVisitor<Visitor> {
+    llvm::Optional<ReferenceLoc> Ref;
+
+    void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) {
+      Ref = ReferenceLoc{D->getQualifierLoc(),
+                         D->getIdentLocation(),
+                         {D->getNominatedNamespaceAsWritten()}};
+    }
+
+    void VisitUsingDecl(const UsingDecl *D) {
+      Ref = ReferenceLoc{D->getQualifierLoc(), D->getLocation(),
+                         explicitReferenceTargets(DynTypedNode::create(*D),
+                                                  DeclRelation::Underlying)};
+    }
+
+    void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) {
+      Ref = ReferenceLoc{D->getQualifierLoc(),
+                         D->getTargetNameLoc(),
+                         {D->getAliasedNamespace()}};
+    }
+  };
+
+  Visitor V;
+  V.Visit(D);
+  return V.Ref;
+}
+
+Optional<ReferenceLoc> refInExpr(const Expr *E) {
+  struct Visitor : ConstStmtVisitor<Visitor> {
+    // FIXME: handle more complicated cases, e.g. ObjC, designated initializers.
+    llvm::Optional<ReferenceLoc> Ref;
+
+    void VisitDeclRefExpr(const DeclRefExpr *E) {
+      Ref = ReferenceLoc{
+          E->getQualifierLoc(), E->getNameInfo().getLoc(), {E->getFoundDecl()}};
+    }
+
+    void VisitMemberExpr(const MemberExpr *E) {
+      Ref = ReferenceLoc{E->getQualifierLoc(),
+                         E->getMemberNameInfo().getLoc(),
+                         {E->getFoundDecl()}};
+    }
+  };
+
+  Visitor V;
+  V.Visit(E);
+  return V.Ref;
+}
+
+Optional<ReferenceLoc> refInTypeLoc(TypeLoc L) {
+  struct Visitor : TypeLocVisitor<Visitor> {
+    llvm::Optional<ReferenceLoc> Ref;
+
+    void VisitElaboratedTypeLoc(ElaboratedTypeLoc L) {
+      // We only know about qualifier, rest if filled by inner locations.
+      Visit(L.getNamedTypeLoc().getUnqualifiedLoc());
+      // Fill in the qualifier.
+      if (!Ref)
+        return;
+      assert(!Ref->Qualifier.hasQualifier() && "qualifier already set");
+      Ref->Qualifier = L.getQualifierLoc();
+    }
+
+    void VisitDeducedTemplateSpecializationTypeLoc(
+        DeducedTemplateSpecializationTypeLoc L) {
+      Ref = ReferenceLoc{
+          NestedNameSpecifierLoc(), L.getNameLoc(),
+          explicitReferenceTargets(DynTypedNode::create(L.getType()))};
+    }
+
+    void VisitTagTypeLoc(TagTypeLoc L) {
+      Ref =
+          ReferenceLoc{NestedNameSpecifierLoc(), L.getNameLoc(), {L.getDecl()}};
+    }
+
+    void VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) {
+      Ref = ReferenceLoc{
+          NestedNameSpecifierLoc(), L.getTemplateNameLoc(),
+          explicitReferenceTargets(DynTypedNode::create(L.getType()))};
+    }
+
+    void VisitDependentTemplateSpecializationTypeLoc(
+        DependentTemplateSpecializationTypeLoc L) {
+      Ref = ReferenceLoc{
+          L.getQualifierLoc(), L.getTemplateNameLoc(),
+          explicitReferenceTargets(DynTypedNode::create(L.getType()))};
+    }
+
+    void VisitDependentNameTypeLoc(DependentNameTypeLoc L) {
+      Ref = ReferenceLoc{
+          L.getQualifierLoc(), L.getNameLoc(),
+          explicitReferenceTargets(DynTypedNode::create(L.getType()))};
+    }
+
+    void VisitTypedefTypeLoc(TypedefTypeLoc L) {
+      Ref = ReferenceLoc{
+          NestedNameSpecifierLoc(), L.getNameLoc(), {L.getTypedefNameDecl()}};
+    }
+  };
+
+  Visitor V;
+  V.Visit(L.getUnqualifiedLoc());
+  return V.Ref;
+}
+
+class ExplicitReferenceColletor
+    : public RecursiveASTVisitor<ExplicitReferenceColletor> {
+public:
+  ExplicitReferenceColletor(llvm::function_ref<void(ReferenceLoc)> Out)
+      : Out(Out) {
+    assert(Out);
+  }
+
+  bool VisitTypeLoc(TypeLoc TTL) {
+    if (TypeLocsToSkip.count(TTL.getBeginLoc().getRawEncoding()))
+      return true;
+    visitNode(DynTypedNode::create(TTL));
+    return true;
+  }
+
+  bool TraverseElaboratedTypeLoc(ElaboratedTypeLoc L) {
+    // ElaboratedTypeLoc will reports information for its inner type loc.
+    // Otherwise we loose information about inner types loc's qualifier.
+    TypeLoc Inner = L.getNamedTypeLoc().getUnqualifiedLoc();
+    TypeLocsToSkip.insert(Inner.getBeginLoc().getRawEncoding());
+    return RecursiveASTVisitor::TraverseElaboratedTypeLoc(L);
+  }
+
+  bool VisitExpr(Expr *E) {
+    visitNode(DynTypedNode::create(*E));
+    return true;
+  }
+
+  bool VisitDecl(Decl *D) {
+    visitNode(DynTypedNode::create(*D));
+    return true;
+  }
+
+  // We have to use Traverse* because there is no corresponding Visit*.
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc L) {
+    if (!L.getNestedNameSpecifier())
+      return true;
+    visitNode(DynTypedNode::create(L));
+    // Inner type is missing information about its qualifier, skip it.
+    if (auto TL = L.getTypeLoc())
+      TypeLocsToSkip.insert(TL.getBeginLoc().getRawEncoding());
+    return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(L);
+  }
+
+private:
+  /// Obtain information about a reference directly defined in \p N. Does not
+  /// recurse into child nodes, e.g. do not expect references for constructor
+  /// initializers
+  ///
+  /// Any of the fields in the returned structure can be empty, but not all of
+  /// them, e.g.
+  ///   - for implicitly generated nodes (e.g. MemberExpr from range-based-for),
+  ///     source location information may be missing,
+  ///   - for dependent code, targets may be empty.
+  ///
+  /// (!) For the purposes of this function declarations are not considered to
+  ///     be references. However, declarations can have references inside them,
+  ///     e.g. 'namespace foo = std' references namespace 'std' and this
+  ///     function will return the corresponding reference.
+  llvm::Optional<ReferenceLoc> explicitReference(DynTypedNode N) {
+    if (auto *D = N.get<Decl>())
+      return refInDecl(D);
+    if (auto *E = N.get<Expr>())
+      return refInExpr(E);
+    if (auto *NNSL = N.get<NestedNameSpecifierLoc>())
+      return ReferenceLoc{NNSL->getPrefix(), NNSL->getLocalBeginLoc(),
+                          explicitReferenceTargets(DynTypedNode::create(
+                              *NNSL->getNestedNameSpecifier()))};
+    if (const TypeLoc *TL = N.get<TypeLoc>())
+      return refInTypeLoc(*TL);
+    if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>()) {
+      if (CCI->isBaseInitializer())
+        return refInTypeLoc(CCI->getBaseClassLoc());
+      assert(CCI->isAnyMemberInitializer());
+      return ReferenceLoc{NestedNameSpecifierLoc(),
+                          CCI->getMemberLocation(),
+                          {CCI->getAnyMember()}};
+    }
+    // We do not have location information for other nodes (QualType, etc)
+    return llvm::None;
+  }
+
+  void visitNode(DynTypedNode N) {
+    auto Ref = explicitReference(N);
+    if (!Ref)
+      return;
+    // Our promise is to return only references from the source code. If we lack
+    // location information, skip these nodes.
+    // Normally this should not happen in practice, unless there are bugs in the
+    // traversals or users started the traversal at an implicit node.
+    if (Ref->NameLoc.isInvalid()) {
+      dlog("invalid location at node {0}", nodeToString(N));
+      return;
+    }
+    Out(*Ref);
+  }
+
+  llvm::function_ref<void(ReferenceLoc)> Out;
+  /// TypeLocs starting at these locations must be skipped, see
+  /// TraverseElaboratedTypeSpecifierLoc for details.
+  llvm::DenseSet</*SourceLocation*/ unsigned> TypeLocsToSkip;
+};
+} // namespace
+
+void findExplicitReferences(Stmt *S,
+                            llvm::function_ref<void(ReferenceLoc)> Out) {
+  assert(S);
+  ExplicitReferenceColletor(Out).TraverseStmt(S);
+}
+void findExplicitReferences(Decl *D,
+                            llvm::function_ref<void(ReferenceLoc)> Out) {
+  assert(D);
+  ExplicitReferenceColletor(Out).TraverseDecl(D);
+}
+
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelation R) {
   switch (R) {
 #define REL_CASE(X)                                                            \
   case DeclRelation::X:                                                        \
     return OS << #X;
     REL_CASE(Alias);
     REL_CASE(Underlying);
     REL_CASE(TemplateInstantiation);
     REL_CASE(TemplatePattern);
 #undef REL_CASE
   }
   llvm_unreachable("Unhandled DeclRelation enum");
 }
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelationSet RS) {
   const char *Sep = "";
   for (unsigned I = 0; I < RS.S.size(); ++I) {
     if (RS.S.test(I)) {
       OS << Sep << static_cast<DeclRelation>(I);
       Sep = "|";
     }
   }
   return OS;
 }
 
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R) {
+  // note we cannot print R.NameLoc without a source manager.
+  OS << "targets = {";
+  bool First = true;
+  for (const NamedDecl *T : R.Targets) {
+    if (!First)
+      OS << ", ";
+    else
+      First = false;
+    OS << printQualifiedName(*T) << printTemplateSpecializationArgs(*T);
+  }
+  OS << "}";
+  if (R.Qualifier) {
+    OS << ", qualifier = '";
+    R.Qualifier.getNestedNameSpecifier()->print(OS,
+                                                PrintingPolicy(LangOptions()));
+    OS << "'";
+  }
+  return OS;
+}
+
 } // namespace clangd
 } // namespace clang

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

 //===-- FindSymbolsTests.cpp -------------------------*- C++ -*------------===//
 //
 // 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 "FindTarget.h"
 
 #include "Selection.h"
 #include "TestTU.h"
+#include "clang/AST/Decl.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Testing/Support/Annotations.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <initializer_list>
 
 namespace clang {
 namespace clangd {
Code = R"cpp(
     @protocol Foo
     @end
     void test(C<[[Foo]]> *p);
   )cpp";
   // FIXME: there's no AST node corresponding to 'Foo', so we're stuck.
   EXPECT_DECLS("ObjCObjectTypeLoc");
 }
 
+class FindExplicitReferencesTest : public ::testing::Test {
+protected:
+  struct AllRefs {
+    std::string AnnotatedCode;
+    std::string DumpedReferences;
+  };
+
+  /// Parses \p Code, finds function '::foo' and annotates its body with results
+  /// of findExplicitReferecnces.
+  /// See actual tests for examples of annotation format.
+  AllRefs annotateReferencesInFoo(llvm::StringRef Code) {
+    TestTU TU;
+    TU.Code = Code;
+
+    auto AST = TU.build();
+    auto &Func = llvm::cast<FunctionDecl>(findDecl(AST, "foo"));
+
+    std::vector<ReferenceLoc> Refs;
+    findExplicitReferences(Func.getBody(), [&Refs](ReferenceLoc R) {
+      Refs.push_back(std::move(R));
+    });
+
+    auto &SM = AST.getSourceManager();
+    llvm::sort(Refs, [&](const ReferenceLoc &L, const ReferenceLoc &R) {
+      return SM.isBeforeInTranslationUnit(L.NameLoc, R.NameLoc);
+    });
+
+    std::string AnnotatedCode;
+    unsigned NextCodeChar = 0;
+    for (unsigned I = 0; I < Refs.size(); ++I) {
+      auto &R = Refs[I];
+
+      SourceLocation Pos = R.NameLoc;
+      assert(Pos.isValid());
+      if (Pos.isMacroID()) // FIXME: figure out how to show macro locations.
+        Pos = SM.getExpansionLoc(Pos);
+      assert(Pos.isFileID());
+
+      FileID File;
+      unsigned Offset;
+      std::tie(File, Offset) = SM.getDecomposedLoc(Pos);
+      if (File == SM.getMainFileID()) {
+        // Print the reference in a source code.
+        assert(NextCodeChar <= Offset);
+        AnnotatedCode += Code.substr(NextCodeChar, Offset - NextCodeChar);
+        AnnotatedCode += "$" + std::to_string(I) + "^";
+
+        NextCodeChar = Offset;
+      }
+    }
+    AnnotatedCode += Code.substr(NextCodeChar);
+
+    std::string DumpedReferences;
+    for (unsigned I = 0; I < Refs.size(); ++I)
+      DumpedReferences += llvm::formatv("{0}: {1}\n", I, Refs[I]);
+
+    return AllRefs{std::move(AnnotatedCode), std::move(DumpedReferences)};
+  }
+};
+
+TEST_F(FindExplicitReferencesTest, All) {
+  std::pair</*Code*/ llvm::StringRef, /*References*/ llvm::StringRef> Cases[] =
+      {
+          // Simple expressions.
+          {R"cpp(
+        int global;
+        int func();
+        void foo(int param) {
+          $0^global = $1^param + $2^func();
+        }
+        )cpp",
+           "0: targets = {global}\n"
+           "1: targets = {param}\n"
+           "2: targets = {func}\n"},
+          {R"cpp(
+        struct X { int a; };
+        void foo(X x) {
+          $0^x.$1^a = 10;
+        }
+        )cpp",
+           "0: targets = {x}\n"
+           "1: targets = {X::a}\n"},
+          // Namespaces and aliases.
+          {R"cpp(
+          namespace ns {}
+          namespace alias = ns;
+          void foo() {
+            using namespace $0^ns;
+            using namespace $1^alias;
+          }
+        )cpp",
+           "0: targets = {ns}\n"
+           "1: targets = {alias}\n"},
+          // Using declarations.
+          {R"cpp(
+          namespace ns { int global; }
+          void foo() {
+            using $0^ns::$1^global;
+          }
+        )cpp",
+           "0: targets = {ns}\n"
+           "1: targets = {ns::global}, qualifier = 'ns::'\n"},
+          // Simple types.
+          {R"cpp(
+         struct Struct { int a; };
+         using Typedef = int;
+         void foo() {
+           $0^Struct x;
+           $1^Typedef y;
+           static_cast<$2^Struct*>(0);
+         }
+       )cpp",
+           "0: targets = {Struct}\n"
+           "1: targets = {Typedef}\n"
+           "2: targets = {Struct}\n"},
+          // Name qualifiers.
+          {R"cpp(
+         namespace a { namespace b { struct S { typedef int type; }; } }
+         void foo() {
+           $0^a::$1^b::$2^S x;
+           using namespace $3^a::$4^b;
+           $5^S::$6^type y;
+         }
+        )cpp",
+           "0: targets = {a}\n"
+           "1: targets = {a::b}, qualifier = 'a::'\n"
+           "2: targets = {a::b::S}, qualifier = 'a::b::'\n"
+           "3: targets = {a}\n"
+           "4: targets = {a::b}, qualifier = 'a::'\n"
+           "5: targets = {a::b::S}\n"
+           "6: targets = {a::b::S::type}, qualifier = 'struct S::'\n"},
+          // Simple templates.
+          {R"cpp(
+          template <class T> struct vector { using value_type = T; };
+          template <> struct vector<bool> { using value_type = bool; };
+          void foo() {
+            $0^vector<int> vi;
+            $1^vector<bool> vb;
+          }
+        )cpp",
+           "0: targets = {vector<int>}\n"
+           "1: targets = {vector<bool>}\n"},
+          // FIXME: Fix 'allTargetDecls' to return alias template and re-enable.
+          // Template type aliases.
+          //   {R"cpp(
+          //   template <class T> struct vector { using value_type = T; };
+          //   template <> struct vector<bool> { using value_type = bool; };
+          //   template <class T> using valias = vector<T>;
+          //   void foo() {
+          //     $0^valias<int> vi;
+          //     $1^valias<bool> vb;
+          //   }
+          // )cpp",
+          //    "0: targets = {valias}\n"
+          //    "1: targets = {valias}\n"},
+
+          // MemberExpr should know their using declaration.
+          {R"cpp(
+            struct X { void func(int); }
+            struct Y : X {
+              using X::func;
+            };
+            void foo(Y y) {
+              $0^y.$1^func(1);
+            }
+        )cpp",
+           "0: targets = {y}\n"
+           "1: targets = {Y::func}\n"},
+          // DeclRefExpr should know their using declaration.
+          {R"cpp(
+            namespace ns { void bar(int); }
+            using ns::bar;
+
+            void foo() {
+              $0^bar(10);
+            }
+        )cpp",
+           "0: targets = {bar}\n"},
+          // References from a macro.
+          {R"cpp(
+            #define FOO a
+            #define BAR b
+
+            void foo(int a, int b) {
+              $0^FOO+$1^BAR;
+            }
+        )cpp",
+           "0: targets = {a}\n"
+           "1: targets = {b}\n"},
+          // No references from implicit nodes.
+          {R"cpp(
+            struct vector {
+              int *begin();
+              int *end();
+            };
+
+            void foo() {
+              for (int x : $0^vector()) {
+                $1^x = 10;
+              }
+            }
+        )cpp",
+           "0: targets = {vector}\n"
+           "1: targets = {x}\n"},
+      };
+
+  for (const auto &C : Cases) {
+    llvm::StringRef ExpectedCode = C.first;
+    llvm::StringRef ExpectedRefs = C.second;
+
+    auto Actual =
+        annotateReferencesInFoo(llvm::Annotations(ExpectedCode).code());
+    EXPECT_EQ(ExpectedCode, Actual.AnnotatedCode);
+    EXPECT_EQ(ExpectedRefs, Actual.DumpedReferences) << ExpectedCode;
+  }
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang