[clangd] Highlight typedefs to template parameters as template parameters

[ilya-biryukov]

Summary

Template parameters were handled outside addType, this led to lack of highlightings for typedefs
to template types.

This was never desirable, we want to highlight our typedefs as their underlying type.
Note that typedefs to more complicated types, like pointers and references are still not highlighted.

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

RecursiveASTVisitor also traverses the pointer and reference types, why does it not reach the inner TemplateTypeParmType in the cases you describe?

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

The D in using D = ... typedef ... D does not have a TypeLoc (at least not one that is visited). Therefore we use the VisitTypedefNameDecl (line 121) to get the location of D to be able to highlight it. And we just send the typeLocs typeptr to addType (which is a Pointer for using D = T*;)...

But maybe we should get the underlying type before we call addType with TypePtr? Just a while loop on line 123 basically (can we have multiple PointerTypes nested in each other actually?)

Even if we keep it in addType the comment is actually wrong, because it obviously works when for the actual "type occurrences" for D (so will fix that no matter what). This recursion will just make us add more duplicate tokens...

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

Could we investigate why RecursiveASTVisitor does not visit the TypeLoc of a corresponding decl?
Here's the code from RecursiveASTVisitor.h that should do the trick:

DEF_TRAVERSE_DECL(TypeAliasDecl, {
  TRY_TO(TraverseTypeLoc(D->getTypeSourceInfo()->getTypeLoc()));
  // We shouldn't traverse D->getTypeForDecl(); it's a result of
  // declaring the type alias, not something that was written in the
  // source.
})

If it doesn't, we are probably holding it wrong.

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

There just doesn't seem to be a TypeLoc for the typedef'ed Decl. We can get the T* TypeLoc (with D->getTypeSourceInfo()->getTypeLoc()). But there isn't one for D. Even the D->getTypeForDecl returns null.

And I have no idea where I'd even start debugging that. Or if it's even a bug

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

I may have misinterpreted the patch. Are we trying to add highlightings for the names of using aliases here? E.g. for the following range:

template <class T>
struct Foo {
  using [[D]] = T**;
};

Why isn't this handled in VisitNamedDecl?
We don't seem to call this function for TypedefNameDecl at all and it actually weird. Is this because we attempt to highlight typedefs as their underlying types?

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

So currently using aliases and typedefs are highlighted the same as the underlying type (in most cases). One case where they aren't is when the underlying type is a template parameter (which is what this patch is trying to solve).

Why isn't this handled in VisitNamedDecl?

The Decl is actually visited in VisitNamedDecl, however as it is a TypeAliasDecl which we do not have a check for in the addToken function it will not get highlighted in that visit.

Actually, could add a check for TypeAliasDecl in addToken (should probably be a check for TypedefNameDecl to cover both using ... and typedef ...) and move the code from the VisitTypedefNameDecl to the addToken function inside that check instead.

We don't seem to call this function for TypedefNameDecl at all and it actually weird. Is this because we attempt to highlight typedefs as their underlying types?

Don't understand what you mean. What function?

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

So currently using aliases and typedefs are highlighted the same as the underlying type (in most cases).

Thanks for clarifying this. This is where my confusion is coming from.
A few question to try understanding the approach taken (sorry if that's too detailed, I am probably missing the context here)

• What do we fallback to? From my reading of the code, we do not highlight them at all if the underlying type is not one of the predefined cases.
• Why are pointers and l-value references special? What about arrays, r-value references, function types, pack expansions, etc.?

Don't understand what you mean. What function?

We don't call VisitNamedDecl from VisitTypedefNameDecl. I guess that's intentional if we try to highlight them as underlying types.

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

Summarizing the offline discussion:

• we chose to highlight typedefs same as their underlying type (e.g. if it's a class we highlight the typedef as class too)
• we need to ensure all typdefs are highlighted in some color. That means we need to handle all composite types in this function and recurse into those. That involves handling at least functions, arrays, all reference types (not just l-value references).
• we should add tests for this.

@jvikstrom, please let me know if I missed something.

[jvikstrom]

Added a RecursiveASTVisitor for finding 'underlying' types.

[jvikstrom]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

we chose to highlight typedefs same as their underlying type (e.g. if it's a class we highlight the typedef as class too)

So this version should do that. For the typedef part.

When there are references with typedefs SomeTypedefTypeThatIsNotBuiltinAndHasNoTagDecl R = ... this will not highlight the SomeTypedefTypeThatIsNotBuiltinAndHasNoTagDecl because RecursiveASTVisitor does not traverse into typedeftypelocs, so we'd need to add the getUnderlyingType thing in VisitTypeLoc as well.
Also need to do this for auto.

And, does it make sense to highlight function typedefs as their return type?

But I'm a bit worried this current approach might not be really sensible.
The 'short circuit' when we find a TagDecl is because otherwise we get weird results at times. (for example TemplateInstantiations, if instantiated with a builtin we'd highlight that as a Primitive while it should be a class because of traversal order)

I guess it would be possible to create a TypeVisitor kind of like how you get deduced types from a typeptr, but that would be a lot of boilerplate.

Maybe what we could do instead of stopping the traversal early when finding a TagDecl is add one field for each Leaf type in UnderlyingTypeVisitor. When returning we'd then return the Record if there is one or Enum if there is one, ... , or a Builtin if none of the others exist.

Is there maybe some other way of finding the "correct" type for a type hierarchy or maybe doing the very basic ranking would be enough? (Record > Enum > TemplateTypeParm > ObjC stuff > Builtin)

[jvikstrom]

Pinging about this @ilya-biryukov

[ilya-biryukov]

clang-tools-extra/clangd/SemanticHighlighting.cpp

24

The comment is a bit complicated, would it be fair to say this is trying to
find the type that should be used to highlight a typedef?

30

We need to initialize Underlying to nullptr

37

Could you make this function static or define it out of class?
That would allow the clients to avoid writing the boilerplate of creating the visitor

38

NIT: maybe simplify to T.getTypePtr()?

57

NIT: no need to specify template arguments to the base class, just use RecursiveASTVisitor::TraverseType()

63

Despite our best efforts, RecursiveASTVisitor still traverses extra stuff, e.g. array sizes

template <class T>
struct X{ 
  using foo = int a[sizeof(T)]; // will probably get 'T' now.
}

Using the recursive ast visitor will lead to hard-to-detect bugs because it visits too much. It's much simpler to write a function that will possibly visit too little, but won't visit the things we don't want to visit:

const Type* getTypeForHighlighting(QualType T) {
  while (true) {
     if (T.isAnyPointerType())
        T = T.getPointeeType();
     else if (T.isReferenceType())
        T = T.getReferencedType();
     else if (T.isArrayType()) 
        T = T.getArrayElementType();
     else if (T.isFunctionType())
        T = T.getReturnType();
     else if (T.isTypedefType())
        T = T.getUnderlyingTypedefType();
     else if (T.isDecltypeType())
        T = T.getAs<DecltypeType>().getExpression().getType(); // have to careful here, can it loop forever?
     else
        break;
  } 
}

126–127

Could we signal when addType cannot produce a highlighting?
E.g. with a vlog()? So that it's easy to detect if we missed something in practice.

177

And, does it make sense to highlight function typedefs as their return type?

I also think it's confusing. But we need to fallback to something if we see a function type (or some other unhandled type) and I believe we
currently just don't highlight those typedefs at all, which seems bad.

I would just have a separate highlighting kind for typedefs (regardless of what the underlying type is).
This would allow to avoid both technical problems (simplifying the implementation) and logical questions (e.g. 'should we highlight typedefs to functions as their return type?)

186

Why do we consider all non-tag-decl types as corner-cases?
The non-tag-decl cases are actually much more common: only classes, structs unions and enums are tag decls, all other non-composite types are not (including builtins, template types, many dependent types, etc)

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

19

Just define a stream output operator for HighlightingToken.
And we should do this inside the file where HighlightingToken is declared to avoid potential ODR violations (e.g. if two tests define the same function, we are in trouble)

442

Could you also add checks that usages of these typedefs are highlighted in the same way as their declarations?

Given that we do not call getUnderlyingType() for those, I suspect they won't be. Perhaps I'm missing something

[nridge]

clang-tools-extra/clangd/SemanticHighlighting.cpp

177

I would just have a separate highlighting kind for typedefs (regardless of what the underlying type is).

FWIW, this is what Eclipse CDT does.

(Although clangd's current choice to highlight typedefs based on their target type is certainly an interesting one. From a user's point of view I can see arguments in either direction. On the one hand, revealing information about the target type is useful. On the other hand, knowing that a type is an alias for something else can also be useful.)

[ilya-biryukov]

• Replace UnderlyingTypeVisitor with a function
• Remove PrintTo()
• Also highlight references to typedefs
• reformat

[ilya-biryukov]

Now that I think about it more, maybe the simplest option is to not recurse into composite types at all....
E.g. a typedef to a template parameter will be highlighted as a template parameter. A typedef to a pointer can be highligthed with a separate kind (other typedefs...)
I'll do these changes, this should simplify both our model and the implementation.

[ilya-biryukov]

• Only highlight typedefs to non-composite types, simplifies everything

[ilya-biryukov]

I'll send a separate change to fallback to a new highlighting type if the underlying type of a typedef is complicated.

[hokein]

thanks for taking care of it.

clang-tools-extra/clangd/SemanticHighlighting.cpp

123

nit: I think the previous TSI->getTypeLoc().getTypePtr() should work?

185

nit: use auto, since the type is obvious from RHS.

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

225

Is this change relevant to this patch?

[ilya-biryukov]

• Address comments

clang-tools-extra/clangd/SemanticHighlighting.cpp

123

Ah, good point, thanks! Fixed.
I've changed this code multiple types and didn't notice that the final result is just a no-op change.

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

225

A leftover from an older version of the patch. Removed, thanks!

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
 //
 //===----------------------------------------------------------------------===//
 
 #include "SemanticHighlighting.h"
 #include "Logger.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Type.h"
 #include <algorithm>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 // Collects all semantic tokens in an ASTContext.
 class HighlightingTokenCollector
     : public RecursiveASTVisitor<HighlightingTokenCollector> {
   std::vector<HighlightingToken> Tokens;
   ASTContext &Ctx;
   const SourceManager &SM;
 
 public:
   HighlightingTokenCollector(ParsedAST &AST)
       : Ctx(AST.getASTContext()), SM(AST.getSourceManager()) {}
 
   std::vector<HighlightingToken> collectTokens() {
     Tokens.clear();
     TraverseAST(Ctx);
     // Initializer lists can give duplicates of tokens, therefore all tokens
     // must be deduplicated.
     llvm::sort(Tokens);
     auto Last = std::unique(Tokens.begin(), Tokens.end());
     Tokens.erase(Last, Tokens.end());
     // Macros can give tokens that have the same source range but conflicting
     // kinds. In this case all tokens sharing this source range should be
     // removed.
     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());
       // TokRef[Conflicting.size()] is the next token with a different range (or
       // the end of the Tokens).
       TokRef = TokRef.drop_front(Conflicting.size());
     }
     return NonConflicting;
   }
 
   bool VisitNamespaceAliasDecl(NamespaceAliasDecl *NAD) {
     // The target namespace of an alias can not be found in any other way.
     addToken(NAD->getTargetNameLoc(), HighlightingKind::Namespace);
     return true;
   }
 
if (Ref->getNameInfo().getName().getNameKind() !=
       return true;
 
     addToken(Ref->getLocation(), Ref->getDecl());
     return true;
   }
 
   bool VisitTypedefNameDecl(TypedefNameDecl *TD) {
     if (const auto *TSI = TD->getTypeSourceInfo())
       addType(TD->getLocation(), TSI->getTypeLoc().getTypePtr());
     return true;
   }
 
-  bool VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc &TL) {
-    // TemplateTypeParmTypeLoc does not have a TagDecl in its type ptr.
-    addToken(TL.getBeginLoc(), TL.getDecl());
-    return true;
-  }
-
   bool VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc &TL) {
     if (const TemplateDecl *TD =
             TL.getTypePtr()->getTemplateName().getAsTemplateDecl())
       addToken(TL.getBeginLoc(), TD);
     return true;
   }
 
   bool VisitTypeLoc(TypeLoc &TL) {
     // This check is for not getting two entries when there are anonymous
bool VisitDeclaratorDecl(DeclaratorDecl *D) {
     }
     return true;
   }
 
 private:
   void addType(SourceLocation Loc, const Type *TP) {
     if (!TP)
       return;
+    if (TP->isPointerType() || TP->isLValueReferenceType())
+      // When highlighting dependant template types the type can be a pointer or
+      // reference of a template type. To highlight that type we need to get to
+      // the underlying type.
+      addType(Loc, TP->getPointeeType().getTypePtr());
     if (TP->isBuiltinType())
       // Builtins must be special cased as they do not have a TagDecl.
       addToken(Loc, HighlightingKind::Primitive);
+    if (const TemplateTypeParmType *TD = dyn_cast<TemplateTypeParmType>(TP))
+      // TemplateTypeParmType does not have a TagDecl.
+      addToken(Loc, TD->getDecl());
     if (const TagDecl *TD = TP->getAsTagDecl())
       addToken(Loc, TD);
   }
 
   void addToken(SourceLocation Loc, const NamedDecl *D) {
     if (D->getDeclName().isIdentifier() && D->getName().empty())
       // Don't add symbols that don't have any length.
       return;

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

 #include "Protocol.h"
 #include "SemanticHighlighting.h"
 #include "TestFS.h"
 #include "TestTU.h"
 #include "gmock/gmock.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 std::vector<HighlightingToken>
 makeHighlightingTokens(llvm::ArrayRef<Range> Ranges, HighlightingKind Kind) {
   std::vector<HighlightingToken> Tokens(Ranges.size());
   for (int I = 0, End = Ranges.size(); I < End; ++I) {
     Tokens[I].R = Ranges[I];
     Tokens[I].Kind = Kind;
   }
R"cpp(
         $Primitive[[int]] $Field[[A]];
       }
       $Primitive[[int]] $Variable[[B]];
       $Class[[AA]] $Variable[[A]]{$Variable[[B]]};
     )cpp",
     R"cpp(
       namespace $Namespace[[a]] {
         struct $Class[[A]] {};
         typedef $Primitive[[char]] $Primitive[[C]];
       }
       typedef $Namespace[[a]]::$Class[[A]] $Class[[B]];
       using $Class[[BB]] = $Namespace[[a]]::$Class[[A]];
       enum class $Enum[[E]] {};
       typedef $Enum[[E]] $Enum[[C]];
       typedef $Enum[[C]] $Enum[[CC]];
       using $Enum[[CD]] = $Enum[[CC]];
       $Enum[[CC]] $Function[[f]]($Class[[B]]);
R"cpp(
       #define assert(COND) if (!(COND)) { fail("assertion failed" #COND); }
       $Primitive[[int]] $Variable[[x]];
       $Primitive[[int]] $Variable[[y]];
       $Primitive[[int]] $Function[[f]]();
       $Primitive[[void]] $Function[[foo]]() {
         assert($Variable[[x]] != $Variable[[y]]);
         assert($Variable[[x]] != $Function[[f]]());
       }
+    )cpp",
+    R"cpp(
+      template<class $TemplateParameter[[T]]>
+      class $Class[[A]] {
+        using $TemplateParameter[[D]] = $TemplateParameter[[T]];
+        using $TemplateParameter[[DD]] = $TemplateParameter[[T]] *;
+        using $TemplateParameter[[DDD]] = $TemplateParameter[[T]] &;
+      };
     )cpp"};
   for (const auto &TestCase : TestCases) {
     checkHighlightings(TestCase);
   }
 
   checkHighlightings(R"cpp(
     class $Class[[A]] {
       #include "imp.h"
     };
     #endif
   )cpp",
                      {{"imp.h", R"cpp(
     int someMethod();