[clangd] Improve semantic highlighting in dependent contexts (fixes #154)

[hokein]

The heuristic of guessing a concrete type seems fragile, and may not work for all cases. Instead of trying out test to guess the underlying type, I think we could introduce a new highlighting kind (e.g. entity.name.type.dependent) for this.

clang-tools-extra/clangd/SemanticHighlighting.cpp

181

This could be member functions, a case is like

template<class T>
class Foo {
public:
  void foo() {
    this->foo();
  }
};

[nridge]

clang-tools-extra/clangd/SemanticHighlighting.cpp

181

Thanks for the example.

Do you have a suggestion for how to discriminate this case? To me, it would seem logical to do it based on syntax (highlight as a member function if the expression forms the function name of a function call expression). That would require navigating from the expression to its parent node. Is there a way to do that?

[nridge]

Updated to use a new "dependent type" highlighting

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

181

There is no way to do this in C++.
Even if the name is followed by a pair of parenthese, this could either be a field with overloaded operator() (e.g. a std::function<void()> field) or a function with the same name.

It's much better to pick a separate highlighting kind for dependent names, this follows the actual semantics of C++.

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

158

I'm doubting we will encounter other exceptions.

struct X {
template<class T>
static T t;
};

template<typename T>
void f() {
  X::t<T>; // this is a `UnresolvedLookupExpr`.
}

181

+1, I think we should just highlight them as a dependent type.

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

54

thanks for catching this!

[nridge]

clang-tools-extra/clangd/SemanticHighlighting.cpp

181

Of course, any attempt to disambiguate between a member function and a field would be heuristic only. I figured that would be better than nothing. But if you prefer using a separate highlighting for dependent names that resolve to a function or a variable, we could do that.

(Hokein, I assume you don't actually mean using the dependent *type* highlighting. Using a type highlighting for something we know is not a type, but rather a function or variable, would be rather confusing.)

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

181

But if you prefer using a separate highlighting for dependent names that resolve to a function or a variable, we could do that.

I'd suggest we'd better follow this. The heuristic could fail in some cases. For these cases, the wrong highlighting'd confuse users too.

(Hokein, I assume you don't actually mean using the dependent *type* highlighting. Using a type highlighting for something we know is not a type, but rather a function or variable, would be rather confusing.)

sorry for the confusion, I meant for anything that could not resolve to a specific declaration (e.g. CXXDependentScopeMemberExpr, UnresolvedLookupExpr), we use the new dependent highlighting kind.

[nridge]

Address review comments

[nridge]

I do feel strongly that types and non-types should be highlighted differently, so the updated patch adds two new dependent highlightings, one for types and one for variables/functions.

[hokein]

In D67901#1687308, @nridge wrote:

I do feel strongly that types and non-types should be highlighted differently, so the updated patch adds two new dependent highlightings, one for types and one for variables/functions.

I see your point here, no objection.

clang-tools-extra/clangd/SemanticHighlighting.cpp

156

nit: remove the {} and elsewhere, LLVM prefers not adding {} if the body only contains a single statement.

163

I think we should use E->getName() since we are highlighting the NameLoc below.

219

nit: we have kindForType for hanlding all types, so I'd move the logic of detecting the dependent type there.

[nridge]

Address review comments

clang-tools-extra/clangd/SemanticHighlighting.cpp

219

I did try this, but it doesn't quite work, because VisitTypeLoc adds the highlighting to the TypeLoc's getBeginLoc(). For something like typename T::type, that highlights the typename token rather than the type token. By contrast, here I add the highlighting to the DependentNameTypeLoc's getNameLoc() which will correctly highlight the type token.

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

219

You'd want to implement WalkUpFromDependentNameTypeLoc instead of Visit* to avoid adding extra highlightings in VisitTypeLoc.

In fact, I'm surprised we're not seeing them now.

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

509

Maybe have a separate category for all dependent entities instead, i.e. use
entity.name.dependent.type.cpp and entity.name.dependent.other.cpp?

This would allow to specify a single highlighting for both names by stopping at dependent subcategory.
I'm not sure how this plays into the default colors provided in the editors that support semantic highlighting...

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

509

Having a dedicate dependent entity doesn't align with the existing textmate patterns (the dependent type should be under the entity.name.type umbrella) -- most highlighters don't have a specific pattern for dependent, so we'll fallback to the entity.name.type color. If we use entity.name.dependent.type.cpp, we'll fall back to entity.name color.

[nridge]

clang-tools-extra/clangd/SemanticHighlighting.cpp

219

We're not seeing extra highlightings with the current patch, because VisitTypeLoc does not add any highlightings for dependent types (kindForType() returns None for them).

So, I don't think there's a problem with using VisitDependentNameTypeLoc?

509

+1, I think it's more important that dependent types are highlighted as types out-of-the-box in cases where the theme contains a highlighting for types but not one specifically for dependent types.

[hokein]

clang-tools-extra/clangd/SemanticHighlighting.cpp

219

I'm second on Ilya's suggestion. It follows the existing pattern (see WalkupFrom* methods above) and make the code clearer, and we can move the DependentType to kindForType.

[nridge]

Updated to use WalkUpFromDependentNameTypeLoc

[nridge]

Is this what you had in mind?

I'm not seeing where the kindForType part comes in. In particular, it seems like it would be silly to call kindForType in WalkUpFromDependentNameTypeLoc(), because we know the answer will be HighlightingKind::DependentType.

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

157

Could we highlighting based on the kinds of E->decls()? If they're all the same, you could just use the corresponding highlighting kind.
Most of the time ADL at template instantiation time does not affect the resulting highlighting, so we could just assume it's going to stay the same.

If there are no decls() or some of them have different highlighting kinds (e.g. static and non-static member functions), you could fallback to DependentName.

162

Same here. Could we try guessing the highlighting type based on E->decls()?

[nridge]

Updated to use heuristics based on OverloadExpr::decl()

Also folded VisitUnresolvedLookupExpr and VisitUnresolvedMemberExpr together
into a single VisitOverloadExpr

[nridge]

I like how we went from using heuristics, to not using heuristics, to using heuristics again :)

But admittedly, the new heuristics are more accurate because they're based on phase 1 lookup results rather than just syntax, so I'm happy with the outcome!

[ilya-biryukov]

In D67901#1704639, @nridge wrote:

I like how we went from using heuristics, to not using heuristics, to using heuristics again :)

But admittedly, the new heuristics are more accurate because they're based on phase 1 lookup results rather than just syntax, so I'm happy with the outcome!

I also liked the irony of it :-)

Mostly LG, just NITs from my side. Happy to LGTM when they're addressed.

clang-tools-extra/clangd/SemanticHighlighting.cpp

105

Could we do this in kindForDecl instead?
I suspect we want to be consistent in other cases this might potentially called in.

108

Maybe simplify the rest of the loop body to the following code?

auto Kind = ...;
if (!Kind || Result && Result != Kind)
  return llvm::None;
Result = Kind;

If you want to have fewer assignments, we could also do:

if (!Result) Result = Kind;

at the end. But I'd just keep it a tad simpler instead.

[nridge]

Address final comments

[ilya-biryukov]

LGTM from my side, but not marking as accepted yet to make sure @hokein has a chance to take a final look.

[hokein]

thanks, looks great now!

clang-tools-extra/clangd/SemanticHighlighting.cpp

41

nit: remove the enclosing {}.

102

nit: the parameter type seems a bit tangled, may use llvm::iterator_range<UnresolvedSetIterator>, but it is not a big deal, up to you.

[nridge]

Address last review comments

clang-tools-extra/clangd/SemanticHighlighting.h

enum class HighlightingKind {
   Method,
   StaticMethod,
   Field,
   StaticField,
   Class,
   Enum,
   EnumConstant,
   Typedef,
+  DependentType,
+  DependentName,
   Namespace,
   TemplateParameter,
   Primitive,
   Macro,
 
   LastKind = Macro
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K);

clang-tools-extra/clangd/SemanticHighlighting.cpp

if (Name.getNameKind() == DeclarationName::CXXConstructorName ||
     return true;
   auto *II = Name.getAsIdentifierInfo();
   return II && !II->getName().empty();
 }
 
 llvm::Optional<HighlightingKind> kindForType(const Type *TP);
 llvm::Optional<HighlightingKind> kindForDecl(const NamedDecl *D) {
   if (auto *TD = dyn_cast<TypedefNameDecl>(D)) {
     // We try to highlight typedefs as their underlying type.
     if (auto K = kindForType(TD->getUnderlyingType().getTypePtrOrNull()))
       return K;
     // And fallback to a generic kind if this fails.
     return HighlightingKind::Typedef;
   }
   // We highlight class decls, constructor decls and destructor decls as
   // `Class` type. The destructor decls are handled in `VisitTypeLoc` (we
   // will visit a TypeLoc where the underlying Type is a CXXRecordDecl).
llvm::Optional<HighlightingKind> kindForType(const Type *TP) {
   if (auto *TD = TP->getAsTagDecl())
     return kindForDecl(TD);
   return llvm::None;
 }
 
 // Collects all semantic tokens in an ASTContext.
 class HighlightingTokenCollector
     : public RecursiveASTVisitor<HighlightingTokenCollector> {
   std::vector<HighlightingToken> Tokens;
   ParsedAST &AST;
 
 public:
   HighlightingTokenCollector(ParsedAST &AST) : AST(AST) {}
 
   std::vector<HighlightingToken> collectTokens() {
     Tokens.clear();
     TraverseAST(AST.getASTContext());
     // Add highlightings for macro expansions as they are not traversed by the
     // visitor.
     for (SourceLocation Loc : AST.getMacros())
       addToken(Loc, HighlightingKind::Macro);
     // Initializer lists can give duplicates of tokens, therefore all tokens
     // must be deduplicated.
public:
   }
 
   bool VisitMemberExpr(MemberExpr *ME) {
     if (canHighlightName(ME->getMemberNameInfo().getName()))
       addToken(ME->getMemberLoc(), ME->getMemberDecl());
     return true;
   }
 
+  bool VisitUnresolvedLookupExpr(UnresolvedLookupExpr *E) {
+    if (canHighlightName(E->getName())) {
+      addToken(E->getNameLoc(), HighlightingKind::DependentName);
+    }
+    return true;
+  }
+
+  bool VisitUnresolvedMemberExpr(UnresolvedMemberExpr *E) {
+    if (canHighlightName(E->getMemberName())) {
+      addToken(E->getNameLoc(), HighlightingKind::DependentName);
+    }
+    return true;
+  }
+
+  bool VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *E) {
+    if (canHighlightName(E->getDeclName())) {
+      addToken(E->getLocation(), HighlightingKind::DependentName);
+    }
+    return true;
+  }
+
+  bool VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
+    if (canHighlightName(E->getMember())) {
+      addToken(E->getMemberLoc(), HighlightingKind::DependentName);
+    }
+    return true;
+  }
+
   bool VisitNamedDecl(NamedDecl *ND) {
     if (canHighlightName(ND->getDeclName()))
       addToken(ND->getLocation(), ND);
     return true;
   }
 
   bool VisitDeclRefExpr(DeclRefExpr *Ref) {
     if (canHighlightName(Ref->getNameInfo().getName()))
bool WalkUpFromTagTypeLoc(TagTypeLoc L) {
     return RecursiveASTVisitor::WalkUpFromTagTypeLoc(L);
   }
 
   bool WalkUpFromElaboratedTypeLoc(ElaboratedTypeLoc L) {
     // Avoid highlighting 'struct' or 'enum' keywords.
     return true;
   }
 
+  bool VisitDependentNameTypeLoc(DependentNameTypeLoc L) {
+    addToken(L.getNameLoc(), HighlightingKind::DependentType);
+    return true;
+  }
+
   bool VisitTypeLoc(TypeLoc TL) {
     if (auto K = kindForType(TL.getTypePtr()))
       addToken(TL.getBeginLoc(), *K);
     return true;
   }
 
   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLoc) {
     if (auto *NNS = NNSLoc.getNestedNameSpecifier()) {
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K) {
   case HighlightingKind::Class:
     return OS << "Class";
   case HighlightingKind::Enum:
     return OS << "Enum";
   case HighlightingKind::EnumConstant:
     return OS << "EnumConstant";
   case HighlightingKind::Typedef:
     return OS << "Typedef";
+  case HighlightingKind::DependentType:
+    return OS << "DependentType";
+  case HighlightingKind::DependentName:
+    return OS << "DependentName";
   case HighlightingKind::Namespace:
     return OS << "Namespace";
   case HighlightingKind::TemplateParameter:
     return OS << "TemplateParameter";
   case HighlightingKind::Primitive:
     return OS << "Primitive";
   case HighlightingKind::Macro:
     return OS << "Macro";
llvm::StringRef toTextMateScope(HighlightingKind Kind) {
   case HighlightingKind::Class:
     return "entity.name.type.class.cpp";
   case HighlightingKind::Enum:
     return "entity.name.type.enum.cpp";
   case HighlightingKind::EnumConstant:
     return "variable.other.enummember.cpp";
   case HighlightingKind::Typedef:
     return "entity.name.type.typedef.cpp";
+  case HighlightingKind::DependentType:
+    return "entity.name.type.dependent.cpp";
+  case HighlightingKind::DependentName:
+    return "entity.name.other.dependent.cpp";
   case HighlightingKind::Namespace:
     return "entity.name.namespace.cpp";
   case HighlightingKind::TemplateParameter:
     return "entity.name.type.template.cpp";
   case HighlightingKind::Primitive:
     return "storage.type.primitive.cpp";
   case HighlightingKind::Macro:
     return "entity.name.function.preprocessor.cpp";
   }
   llvm_unreachable("unhandled HighlightingKind");
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/test/semantic-highlighting.test

 # CHECK-NEXT:          ],
 # CHECK-NEXT:          [
 # CHECK-NEXT:            "variable.other.enummember.cpp"
 # CHECK-NEXT:          ],
 # CHECK-NEXT:          [
 # CHECK-NEXT:            "entity.name.type.typedef.cpp"
 # CHECK-NEXT:          ],
 # CHECK-NEXT:          [
+# CHECK-NEXT:            "entity.name.type.dependent.cpp"
+# CHECK-NEXT:          ],
+# CHECK-NEXT:          [
+# CHECK-NEXT:            "entity.name.other.dependent.cpp"
+# CHECK-NEXT:          ],
+# CHECK-NEXT:          [
 # CHECK-NEXT:            "entity.name.namespace.cpp"
 # CHECK-NEXT:          ],
 # CHECK-NEXT:          [
 # CHECK-NEXT:            "entity.name.type.template.cpp"
 # CHECK-NEXT:          ],
 # CHECK-NEXT:          [
 # CHECK-NEXT:            "storage.type.primitive.cpp"
 # CHECK-NEXT:          ],
 # CHECK-NEXT:          [
 # CHECK-NEXT:            "entity.name.function.preprocessor.cpp"
 # CHECK-NEXT:          ]
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 ---
 {"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///foo.cpp","languageId":"cpp","version":1,"text":"int x = 2;"}}}
 #      CHECK:  "method": "textDocument/semanticHighlighting",
 # CHECK-NEXT:  "params": {
 # CHECK-NEXT:    "lines": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "line": 0,
-# CHECK-NEXT:        "tokens": "AAAAAAADAA4AAAAEAAEAAA=="
+# CHECK-NEXT:        "tokens": "AAAAAAADABAAAAAEAAEAAA=="
 # CHECK-NEXT:      }
 # CHECK-NEXT:    ],
 # CHECK-NEXT:    "textDocument": {
 # CHECK-NEXT:      "uri": "file:///clangd-test/foo.cpp"
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 # CHECK-NEXT:}
 ---
 {"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///foo2.cpp","languageId":"cpp","version":1,"text":"int x = 2;\nint y = 2;"}}}
 #      CHECK:  "method": "textDocument/semanticHighlighting",
 # CHECK-NEXT:  "params": {
 # CHECK-NEXT:    "lines": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "line": 0,
-# CHECK-NEXT:        "tokens": "AAAAAAADAA4AAAAEAAEAAA=="
+# CHECK-NEXT:        "tokens": "AAAAAAADABAAAAAEAAEAAA=="
 # CHECK-NEXT:      }
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "line": 1,
-# CHECK-NEXT:        "tokens": "AAAAAAADAA4AAAAEAAEAAA=="
+# CHECK-NEXT:        "tokens": "AAAAAAADABAAAAAEAAEAAA=="
 # CHECK-NEXT:      }
 # CHECK-NEXT:    ],
 # CHECK-NEXT:    "textDocument": {
 # CHECK-NEXT:      "uri": "file:///clangd-test/foo2.cpp"
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 # CHECK-NEXT:}
 ---
 {"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"test:///foo.cpp","version":2},"contentChanges": [{"range":{"start": {"line": 0,"character": 10},"end": {"line": 0,"character": 10}},"rangeLength": 0,"text": "\nint y = 2;"}]}}
 #      CHECK:  "method": "textDocument/semanticHighlighting",
 # CHECK-NEXT:  "params": {
 # CHECK-NEXT:    "lines": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "line": 1,
-# CHECK-NEXT:        "tokens": "AAAAAAADAA4AAAAEAAEAAA=="
+# CHECK-NEXT:        "tokens": "AAAAAAADABAAAAAEAAEAAA=="
 # CHECK-NEXT:      }
 # CHECK-NEXT:   ],
 # CHECK-NEXT:    "textDocument": {
 # CHECK-NEXT:      "uri": "file:///clangd-test/foo.cpp"
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 # CHECK-NEXT:}
 ---

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

static const std::map<HighlightingKind, std::string> KindToString{
       {HighlightingKind::Class, "Class"},
       {HighlightingKind::Enum, "Enum"},
       {HighlightingKind::Namespace, "Namespace"},
       {HighlightingKind::EnumConstant, "EnumConstant"},
       {HighlightingKind::Field, "Field"},
       {HighlightingKind::StaticField, "StaticField"},
       {HighlightingKind::Method, "Method"},
       {HighlightingKind::StaticMethod, "StaticMethod"},
+      {HighlightingKind::Typedef, "Typedef"},
+      {HighlightingKind::DependentType, "DependentType"},
+      {HighlightingKind::DependentName, "DependentName"},
       {HighlightingKind::TemplateParameter, "TemplateParameter"},
       {HighlightingKind::Primitive, "Primitive"},
       {HighlightingKind::Macro, "Macro"}};
   std::vector<HighlightingToken> ExpectedTokens;
   for (const auto &KindString : KindToString) {
     std::vector<HighlightingToken> Toks = makeHighlightingTokens(
         Test.ranges(KindString.second), KindString.first);
     ExpectedTokens.insert(ExpectedTokens.end(), Toks.begin(), Toks.end());
)cpp",
       namespace $Namespace[[abc]] {
         template<typename $TemplateParameter[[T]]>
         struct $Class[[A]] {
           $TemplateParameter[[T]] $Field[[t]];
         };
       }
       template<typename $TemplateParameter[[T]]>
       struct $Class[[C]] : $Namespace[[abc]]::$Class[[A]]<$TemplateParameter[[T]]> {
-        typename $TemplateParameter[[T]]::A* $Field[[D]];
+        typename $TemplateParameter[[T]]::$DependentType[[A]]* $Field[[D]];
       };
       $Namespace[[abc]]::$Class[[A]]<$Primitive[[int]]> $Variable[[AA]];
       typedef $Namespace[[abc]]::$Class[[A]]<$Primitive[[int]]> $Class[[AAA]];
       struct $Class[[B]] {
         $Class[[B]]();
         ~$Class[[B]]();
         $Primitive[[void]] operator<<($Class[[B]]);
         $Class[[AAA]] $Field[[AA]];
)cpp",
         using $Typedef[[Array]] = $TemplateParameter[[T]]*[3];
         using $Typedef[[MemberPointer]] = $Primitive[[int]] (A::*)($Primitive[[int]]);
 
         // Use various previously defined typedefs in a function type.
         $Primitive[[void]] $Method[[func]](
           $Typedef[[Pointer]], $Typedef[[LVReference]], $Typedef[[RVReference]],
           $Typedef[[Array]], $Typedef[[MemberPointer]]);
       };
+    )cpp",
+      R"cpp(
+      template <class $TemplateParameter[[T]]>
+      $Primitive[[void]] $Function[[foo]]($TemplateParameter[[T]] $Parameter[[P]]) {
+        $DependentName[[bar]]($Parameter[[P]]);
+      }
+    )cpp",
+      R"cpp(
+      class $Class[[A]] {
+        template <class $TemplateParameter[[T]]>
+        $Primitive[[void]] $Method[[bar]]($TemplateParameter[[T]]);
+      };
+
+      template <class $TemplateParameter[[U]]>
+      $Primitive[[void]] $Function[[foo]]($TemplateParameter[[U]] $Parameter[[P]]) {
+        $Class[[A]]().$DependentName[[bar]]($Parameter[[P]]);
+      }
+    )cpp",
+      R"cpp(
+      struct $Class[[A]] {
+        template <class $TemplateParameter[[T]]>
+        static $Primitive[[void]] $StaticMethod[[foo]]($TemplateParameter[[T]]);
+      };
+
+      template <class $TemplateParameter[[T]]>
+      struct $Class[[B]] {
+        $Primitive[[void]] $Method[[bar]]() {
+          $Class[[A]]::$DependentName[[foo]]($TemplateParameter[[T]]());
+        }
+      };
+    )cpp",
+      R"cpp(
+      template <class $TemplateParameter[[T]]>
+      $Primitive[[void]] $Function[[foo]](typename $TemplateParameter[[T]]::$DependentType[[Type]]
+                                            = $TemplateParameter[[T]]::$DependentName[[val]]);
+    )cpp",
+      R"cpp(
+      template <class $TemplateParameter[[T]]>
+      $Primitive[[void]] $Function[[foo]]($TemplateParameter[[T]] $Parameter[[P]]) {
+        $Parameter[[P]].$DependentName[[Field]];
+      }
+    )cpp",
+      R"cpp(
+      template <class $TemplateParameter[[T]]>
+      class $Class[[A]] {
+        $Primitive[[int]] $Method[[foo]]() {
+          return $TemplateParameter[[T]]::$DependentName[[Field]];
+        }
+      };
     )cpp"};
   for (const auto &TestCase : TestCases) {
     checkHighlightings(TestCase);
   }
 
   checkHighlightings(R"cpp(
     class $Class[[A]] {
       #include "imp.h"
EXPECT_THAT(ActualDiff,
               testing::UnorderedElementsAre(
                   testing::AllOf(LineNumber(3), EmptyHighlightings()),
                   testing::AllOf(LineNumber(4), EmptyHighlightings())));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang
 No newline at end of file