[clangd] Color dependent names based on their heuristic target if they have one

[nridge]

Summary

Fixes https://github.com/clangd/clangd/issues/297

[nridge]

Adding some reviewers.

[sammccall]

Great! Needs some tests though :-)

clang-tools-extra/clangd/FindTarget.cpp

651

Can you move these into some logical order?
e.g. below the common cases, or paired with the non-dependent equivalents

651

Can you add tests for these changes?
This function is used for various things beyond semantic highlighting (such as rename) so it has its own tests.

clang-tools-extra/clangd/SemanticHighlighting.cpp

146

nit: the quality is of the categorization (the "highlighting"), not the token.
And I don't think "heuristic" is a good name for DependentType etc - when DependentType conflicts with Field, it's *Field* that's heuristic!

I'd suggest something like enum HighlightPriority { Dependent, Resolved } so that < does the obvious thing.

148

nit: move the enum inside this function and return unsigned? No need to worry about names then, and represents that this is only used for prioritization.

157

why a limit of 2, vs a loop?

215–216

can we move this case into resolveConflict?

217

out of curiosity, *why* is the same token being highlighted as dependentname and resolved? Is it being traversed twice?

[nridge]

Address review comments

clang-tools-extra/clangd/SemanticHighlighting.cpp

157

I'm not aware of a scenario where we'd get more than two conflicting highlightings, except when macros are involved in which case we don't have a good way to disambiguate anyways.

217

It's for the reason you described in this comment: the resolved highlighting comes from findExplicitReferences(), and the dependent one form CollectExtraHighlightings.

[sammccall]

clang-tools-extra/clangd/SemanticHighlighting.cpp

217

Oh yeah :-)
Can we add a comment somewhere about this case? e.g. on resolveConflict (this happens when...)

[nridge]

Address final review comment

[nridge]

clang-tools-extra/clangd/SemanticHighlighting.cpp

157

I should've listened to you when you suggested a loop :)

I overlooked the case where findExplicitReferences() contributes more than one candidate token because a dependent name is heuristically resolved to an overload set, in which case we get one target for each overload.

Fixed in D121775.

[sammccall]

clang-tools-extra/clangd/SemanticHighlighting.cpp

157

I think this is a good sign, my tendency is to borrow too many problems from the future anyway :-)

clang-tools-extra/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
 //
 //===----------------------------------------------------------------------===//
 
struct Visitor : ConstStmtVisitor<Visitor> {
     llvm::SmallVector<ReferenceLoc, 2> Refs;
 
     void VisitConceptSpecializationExpr(const ConceptSpecializationExpr *E) {
       Refs.push_back(ReferenceLoc{E->getNestedNameSpecifierLoc(),
                                   E->getConceptNameLoc(),
                                   /*IsDecl=*/false,
                                   {E->getNamedConcept()}});
     }
+
     void VisitDeclRefExpr(const DeclRefExpr *E) {
       Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
                                   E->getNameInfo().getLoc(),
                                   /*IsDecl=*/false,
                                   {E->getFoundDecl()}});
     }
 
+    void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) {
+      Refs.push_back(ReferenceLoc{
+          E->getQualifierLoc(), E->getNameInfo().getLoc(), /*IsDecl=*/false,
+          explicitReferenceTargets(DynTypedNode::create(*E), {})});
+    }
+
     void VisitMemberExpr(const MemberExpr *E) {
       // Skip destructor calls to avoid duplication: TypeLoc within will be
       // visited separately.
       if (llvm::dyn_cast<CXXDestructorDecl>(E->getFoundDecl().getDecl()))
         return;
       Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
                                   E->getMemberNameInfo().getLoc(),
                                   /*IsDecl=*/false,
                                   {E->getFoundDecl()}});
     }
 
+    void
+    VisitCXXDependentScopeMemberExpr(const CXXDependentScopeMemberExpr *E) {
+      Refs.push_back(
+          ReferenceLoc{E->getQualifierLoc(), E->getMemberNameInfo().getLoc(),
+                       /*IsDecl=*/false,
+                       explicitReferenceTargets(DynTypedNode::create(*E), {})});
+    }
+
     void VisitOverloadExpr(const OverloadExpr *E) {
       Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
                                   E->getNameInfo().getLoc(),
                                   /*IsDecl=*/false,
                                   llvm::SmallVector<const NamedDecl *, 1>(
                                       E->decls().begin(), E->decls().end())});
     }
 

clang-tools-extra/clangd/SemanticHighlighting.cpp

 //===--- SemanticHighlighting.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
 //
 //===----------------------------------------------------------------------===//
 
if (L.isFileID())
     return SM.isWrittenInMainFile(L) ? L : SourceLocation{};
   // Tokens expanded from the macro body contribute no highlightings.
   if (!SM.isMacroArgExpansion(L))
     return {};
   // Tokens expanded from macro args are potentially highlightable.
   return getHighlightableSpellingToken(SM.getImmediateSpellingLoc(L), SM);
 }
 
+unsigned evaluateHighlightPriority(HighlightingKind Kind) {
+  enum HighlightPriority { Dependent = 0, Resolved = 1 };
+  return Kind == HighlightingKind::DependentType ||
+                 Kind == HighlightingKind::DependentName
+             ? Dependent
+             : Resolved;
+}
+
+// Sometimes we get conflicts between findExplicitReferences() returning
+// a heuristic result for a dependent name (e.g. Method) and
+// CollectExtraHighlighting returning a fallback dependent highlighting (e.g.
+// DependentName). In such cases, resolve the conflict in favour of the
+// resolved (non-dependent) highlighting.
+// With macros we can get other conflicts (if a spelled token has multiple
+// expansions with different token types) which we can't usefully resolve.
+llvm::Optional<HighlightingToken>
+resolveConflict(ArrayRef<HighlightingToken> Tokens) {
+  if (Tokens.size() == 1)
+    return Tokens[0];
+
+  if (Tokens.size() != 2)
+    return llvm::None;
+
+  unsigned Priority1 = evaluateHighlightPriority(Tokens[0].Kind);
+  unsigned Priority2 = evaluateHighlightPriority(Tokens[1].Kind);
+  if (Priority1 == Priority2)
+    return llvm::None;
+  return Priority1 > Priority2 ? Tokens[0] : Tokens[1];
+}
+
 /// Consumes source locations and maps them to text ranges for highlightings.
 class HighlightingsBuilder {
 public:
   HighlightingsBuilder(const ParsedAST &AST)
       : TB(AST.getTokens()), SourceMgr(AST.getSourceManager()),
         LangOpts(AST.getLangOpts()) {}
 
   void addToken(HighlightingToken T) { Tokens.push_back(T); }
std::vector<HighlightingToken> collect(ParsedAST &AST) && {
     std::vector<HighlightingToken> NonConflicting;
     NonConflicting.reserve(Tokens.size());
     for (ArrayRef<HighlightingToken> TokRef = Tokens; !TokRef.empty();) {
       ArrayRef<HighlightingToken> Conflicting =
           TokRef.take_while([&](const HighlightingToken &T) {
             // TokRef is guaranteed at least one element here because otherwise
             // this predicate would never fire.
             return T.R == TokRef.front().R;
           });
-      // If there is exactly one token with this range it's non conflicting and
-      // should be in the highlightings.
-      if (Conflicting.size() == 1)
-        NonConflicting.push_back(TokRef.front());
+      if (auto Resolved = resolveConflict(Conflicting))
+        NonConflicting.push_back(*Resolved);
       // TokRef[Conflicting.size()] is the next token with a different range (or
       // the end of the Tokens).
       TokRef = TokRef.drop_front(Conflicting.size());
     }
     // Add tokens indicating lines skipped by the preprocessor.
     for (const Range &R : AST.getMacros().SkippedRanges) {
       // Create one token for each line in the skipped range, so it works
       // with line-based diffing.

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

 //===-- FindTargetTests.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"
std::pair</*Code*/ llvm::StringRef, /*References*/ llvm::StringRef> Cases[] =
               for (int $0^x : $1^vector()) {
                 $2^x = 10;
               }
             }
         )cpp",
         "0: targets = {x}, decl\n"
         "1: targets = {vector}\n"
         "2: targets = {x}\n"},
-       // Handle UnresolvedLookupExpr.
-       // FIXME
-       // This case fails when expensive checks are enabled.
-       // Seems like the order of ns1::func and ns2::func isn't defined.
-       #ifndef EXPENSIVE_CHECKS
        {R"cpp(
             namespace ns1 { void func(char*); }
             namespace ns2 { void func(int*); }
             using namespace ns1;
             using namespace ns2;
 
             template <class T>
             void foo(T t) {
               $0^func($1^t);
             }
         )cpp",
         "0: targets = {ns1::func, ns2::func}\n"
         "1: targets = {t}\n"},
-        #endif
        // Handle UnresolvedMemberExpr.
        {R"cpp(
             struct X {
               void func(char*);
               void func(int*);
             };
 
             template <class T>
             void foo(X x, T t) {
               $0^x.$1^func($2^t);
             }
         )cpp",
         "0: targets = {x}\n"
         "1: targets = {X::func, X::func}\n"
         "2: targets = {t}\n"},
+       // Handle DependentScopeDeclRefExpr.
+       {R"cpp(
+            template <class T>
+            struct S {
+              static int value;
+            };
+
+            template <class T>
+            void foo() {
+              $0^S<$1^T>::$2^value;
+            }
+       )cpp",
+        "0: targets = {S}\n"
+        "1: targets = {T}\n"
+        "2: targets = {S::value}, qualifier = 'S<T>::'\n"},
+       // Handle CXXDependentScopeMemberExpr.
+       {R"cpp(
+            template <class T>
+            struct S {
+              int value;
+            };
+
+            template <class T>
+            void foo(S<T> t) {
+              $0^t.$1^value;
+            }
+       )cpp",
+        "0: targets = {t}\n"
+        "1: targets = {S::value}\n"},
        // Type template parameters.
        {R"cpp(
             template <class T>
             void foo() {
               static_cast<$0^T>(0);
               $1^T();
               $2^T $3^t;
             }
#endif
        {
            R"cpp(
               template <typename T>
               concept Drawable = requires (T t) { t.draw(); };
 
               namespace foo {
                 template <typename $0^T> requires $1^Drawable<$2^T>
                 void $3^bar($4^T $5^t) {
-                  $6^t.draw();
+                  $6^t.$7^draw();
                 }
               }
           )cpp",
            "0: targets = {T}, decl\n"
            "1: targets = {Drawable}\n"
            "2: targets = {T}\n"
            "3: targets = {foo::bar}, decl\n"
            "4: targets = {T}\n"
            "5: targets = {t}, decl\n"
-           "6: targets = {t}\n"},
+           "6: targets = {t}\n"
+           "7: targets = {}\n"},
        // Objective-C: properties
        {
            R"cpp(
             @interface I {}
             @property(retain) I* x;
             @property(retain) I* y;
             @end
             I *f;

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

 //==- SemanticHighlightingTests.cpp - SemanticHighlighting tests-*- 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
 //
 //===----------------------------------------------------------------------===//
 
)cpp",
             ::$DependentType[[Location]];
         using $Typedef[[Location3]] = typename $TemplateParameter[[T]]
             ::$DependentType[[Resolver]]
             ::template $DependentType[[Location]]<$TemplateParameter[[T]]>;
         static const int $StaticField[[Value]] = $TemplateParameter[[T]]
             ::$DependentType[[Resolver]]::$DependentName[[Value]];
       };
     )cpp",
+      // Dependent name with heuristic target
+      R"cpp(
+      template <typename>
+      struct $Class[[Foo]] {
+        int $Field[[Waldo]];
+        void $Method[[bar]]() {
+          $Class[[Foo]]().$Field[[Waldo]];
+        }
+        template <typename $TemplateParameter[[U]]>
+        void $Method[[bar1]]() {
+          $Class[[Foo]]<$TemplateParameter[[U]]>().$Field[[Waldo]];
+        }
+      };
+    )cpp",
       // Concepts
       R"cpp(
       template <typename $TemplateParameter[[T]]>
       concept $Concept[[Fooable]] = 
           requires($TemplateParameter[[T]] $Parameter[[F]]) {
             $Parameter[[F]].$DependentName[[foo]]();
           };
       template <typename $TemplateParameter[[T]]>