[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

248

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

248

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

248

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

248

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

248

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

248

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

248

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

248

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

248

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

25

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?

31

We need to initialize Underlying to nullptr

38

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

39

NIT: maybe simplify to T.getTypePtr()?

58

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

64

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;
  } 
}

193

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.

248

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?)

252

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)

458

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

248

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

192–193

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

251

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

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

233

Is this change relevant to this patch?

[ilya-biryukov]

• Address comments

clang-tools-extra/clangd/SemanticHighlighting.cpp

192–193

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

233

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 "clang/AST/TypeLoc.h"
 #include <algorithm>
 
 namespace clang {
 namespace clangd {
 namespace {
 
+/// Gets an underlying type in a type hierarchy. Should be used to find the type
+/// in a hieracrchy when the HighlightingTokenCollector's RecursiveASTVisitor
+/// can not recurse to it by default and the addType function is used outside a
+/// Visit*TypeLoc.
+class UnderlyingTypeVisitor
+    : public RecursiveASTVisitor<UnderlyingTypeVisitor> {
+  const Type *Underlying;
+
+public:
+  /// Gets an underlying type in the \p T type hierarchy.
+  /// Gets the first type ptr with a Tag decl if one exists.
+  /// Else gets the first Leaf type ptr.
+  /// If neither are found returns the type ptr.
+  const Type *getUnderlyingType(QualType T) {
+    Underlying = &(*T);
+    TraverseType(T);
+    return Underlying;
+  }
+
+  // Check if T has a tag decl and if so stop traversing the type hierachy as we
+  // want to return this.
+  bool VisitType(Type *T) {
+    if (T->getAsTagDecl()) {
+      Underlying = T;
+      return false;
+    }
+    return true;
+  }
+
+  // The default behaviour for RecursiveASTVisitor is to traverse the class type
+  // as well. This makes member pointers become highlighted as classes which is
+  // incorrect.
+  bool TraverseMemberPointerType(MemberPointerType *T) {
+    return RecursiveASTVisitor<UnderlyingTypeVisitor>::TraverseType(
+        T->getPointeeType());
+  }
+
+  // RecursiveASTVisitor does not traverse the underlying type of a decltype.
+  bool TraverseDecltypeType(DecltypeType *T) {
+    return RecursiveASTVisitor<UnderlyingTypeVisitor>::TraverseType(
+        T->getUnderlyingType());
+  }
+
+  // RecursiveASTVisitor also traverses parameter and exception types. Only want
+  // return type for this.
+  bool TraverseFunctionProtoType(FunctionProtoType *T) {
+    return RecursiveASTVisitor<UnderlyingTypeVisitor>::TraverseType(
+        T->getReturnType());
+  }
+
+  // RecursiveASTVisitor does not traverse a typedef's underlying type.
+  bool TraverseTypedefType(TypedefType *T) {
+    return RecursiveASTVisitor<UnderlyingTypeVisitor>::TraverseType(
+        T->getDecl()->getUnderlyingType());
+  }
+
+// Create Visit functions for all leaf types that set the Leaf type. Don't want
+// to create any functions for non leaf Types.
+#define TYPE(X, Y)
+#define LEAF_TYPE(CLASS)                                                       \
+  bool Visit##CLASS##Type(CLASS##Type *T) {                                    \
+    Underlying = T;                                                            \
+    return true;                                                               \
+  }
+#include "clang/AST/TypeNodes.def"
+#undef TYPE
+#undef LEAF_TYPE
+};
+
 // Collects all semantic tokens in an ASTContext.
 class HighlightingTokenCollector
     : public RecursiveASTVisitor<HighlightingTokenCollector> {
   std::vector<HighlightingToken> Tokens;
   ASTContext &Ctx;
   const SourceManager &SM;
 
 public:
if (Ref->getNameInfo().getName().getNameKind() !=
       // Only want to highlight identifiers.
       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());
+      addType(TD->getLocation(), UnderlyingTypeVisitor().getUnderlyingType(
+                                     TSI->getTypeLoc().getType()));
     return true;
   }
 
   bool VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc &TL) {
     if (const TemplateDecl *TD =
             TL.getTypePtr()->getTemplateName().getAsTemplateDecl())
       addToken(TL.getBeginLoc(), TD);
     return true;
bool VisitDeclaratorDecl(DeclaratorDecl *D) {
     }
     return true;
   }
 
 private:
   void addType(SourceLocation Loc, const Type *TP) {
     if (!TP)
       return;
     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 also do 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 {
+void PrintTo(const HighlightingToken &T, ::std::ostream *OS) {
+  *OS << "(" << T.R.start.line << ", " << T.R.start.character << ") -> (" << T.R.end.line << ", " << T.R.end.character << "): " << (int)T.Kind;
+}
+
 namespace {
 
 MATCHER_P(LineNumber, L, "") { return arg.Line == L; }
 MATCHER(EmptyHighlightings, "") { return arg.Tokens.empty(); }
 
 std::vector<HighlightingToken>
 makeHighlightingTokens(llvm::ArrayRef<Range> Ranges, HighlightingKind Kind) {
   std::vector<HighlightingToken> Tokens(Ranges.size());
R"cpp(
       struct $Class[[AA]] {
         $Primitive[[int]] $Field[[A]];
       }
       $Primitive[[int]] $Variable[[B]];
       $Class[[AA]] $Variable[[A]]{$Variable[[B]]};
     )cpp",
     R"cpp(
       namespace $Namespace[[a]] {
-        struct $Class[[A]] {};
+        struct $Class[[A]] {
+          $Primitive[[void]] $Method[[foo]]($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]]);
       $Enum[[CD]] $Function[[f]]($Class[[BB]]);
       typedef $Namespace[[a]]::$Primitive[[C]] $Primitive[[PC]];
       typedef $Primitive[[float]] $Primitive[[F]];
+      using $Primitive[[Member]] =
+        $Primitive[[void]] (B::*)($Namespace[[a]]::$Class[[A]]*);
+      $Primitive[[void]] $Function[[foo]]($Primitive[[int]], $Class[[B]]);
+      typedef decltype($Function[[foo]]) $Primitive[[fooo]];
+      typedef $Class[[B]] (*$Class[[func]])();
+      typedef $Primitive[[int]] (*$Primitive[[func]])();
     )cpp",
     R"cpp(
       template<typename $TemplateParameter[[T]], typename = $Primitive[[void]]>
       class $Class[[A]] {
         $TemplateParameter[[T]] $Field[[AA]];
         $TemplateParameter[[T]] $Method[[foo]]();
       };
       template<class $TemplateParameter[[TT]]>
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]] &;
+        using $TemplateParameter[[B]] = $TemplateParameter[[T]]*[3];
+        using $TemplateParameter[[BB]] = $TemplateParameter[[T]]&&;
+        using $TemplateParameter[[Member]] =
+          BB (T::*)($Primitive[[int]]);
+        using $TemplateParameter[[MemberT]] =
+          $TemplateParameter[[T]]*& (T::*)($Class[[A]]);
+      };
     )cpp"};
   for (const auto &TestCase : TestCases) {
     checkHighlightings(TestCase);
   }
 
   checkHighlightings(R"cpp(
     class $Class[[A]] {
       #include "imp.h"