[clangd] Rainbow Semantic Highlighting

[alexzielenski]

Summary

This patch adds support for rainbow semantic highlighting seem in ccls and cquery into clangd's implementation of SemanticTokensProvider. The method of implementation is to create new modifiers "0, 1, 2, 4", which are pinned to the hash of a SymbolID, to be used by the user in the creation of their theme for rainbow highlighting.

This patch has a few flaws as well as minor improvements to clangd's classification of symbols and takes you 80% of the way. I mainly created it for my own purposes since I cannot read code without this feature. Hopefully you can merge something like this upstream so I don't have to keep maintaining my local checkout.

I attached an example of what this looks like, and below is the configuration I used in my VSCode settings so you can try for yourself:

json
    "editor.semanticTokenColorCustomizations": {
        "enabled": true,
        "rules": {
            "variable:cpp": "#92d7f2",
            "variable.1:cpp": "#78a8d5",
            "variable.2:cpp": "#9be0e6",
            "variable.3:cpp": "#9cc2f7",
            "variable.4:cpp": "#5ba9b8",
            "variable.local:cpp": "#99bfcb",
            "variable.local.1:cpp": "#c2e9f5",
            "variable.local.2:cpp": "#add4e0",
            "variable.local.3:cpp": "#99bfcb",
            "variable.local.4:cpp": "#81afc5",
            "variable.member:cpp": "#4fbbbc",
            "variable.member.1:cpp": "#3ba7e5",
            "variable.member.2:cpp": "#33d4d1",
            "variable.member.3:cpp": "#4eb4f3",
            "variable.member.4:cpp": "#6ed7d8",
            "variable.static.member:cpp": "#66d4f6",
            "variable.static.member.1:cpp": "#2f8fa5",
            "variable.static.member.2:cpp": "#4ee2f4",
            "variable.static.member.3:cpp": "#88aee1",
            "variable.static.member.4:cpp": "#4ab9ce",
            "parameter:cpp": "#a4beb8",
            "parameter.1:cpp": "#7fd6c5",
            "parameter.2:cpp": "#b8d3cd",
            "parameter.3:cpp": "#9fcaac",
            "parameter.4:cpp": "#a8dfd4",
            "function:cpp": "#61cca5",
            "function.1:cpp": "#1fe1fb",
            "function.2:cpp": "#43c88b",
            "function.3:cpp": "#3edbd8",
            "function.4:cpp": "#63e5a6",
            "function.member:cpp": "#4bd6fd",
            "function.member.1:cpp": "#28e6cc",
            "function.member.2:cpp": "#4eb4f3",
            "function.member.3:cpp": "#4cccb7",
            "function.member.4:cpp": "#4abfe8",
            "function.static:cpp": "#9fa8e1",
            "function.static.1:cpp": "#20d8fd",
            "function.static.2:cpp": "#9ca6f4",
            "function.static.3:cpp": "#5bcdf6",
            "function.static.4:cpp": "#b4bcf7",
            "type:cpp": "#edc158",
            "type.1:cpp": "#f67b3e",
            "type.2:cpp": "#ecc02b",
            "type.3:cpp": "#e59668",
            "type.4:cpp": "#e6a01e",
            "enum:cpp": "#d55bc0",
            "enum.1:cpp": "#ee4d69",
            "enum.2:cpp": "#f570d9",
            "enum.3:cpp": "#f7457c",
            "enum.4:cpp": "#e44cc0",
            "enumConstant:cpp": "#f53d8b",
            "enumConstant.1:cpp": "#f53d8b",
            "enumConstant.2:cpp": "#ef489e",
            "enumConstant.3:cpp": "#d452a8",
            "enumConstant.4:cpp": "#d452a8",
            "macro:cpp": "#a85e16",
            "macro.1:cpp": "#d29e3b",
            "macro.2:cpp": "#8d630a",
            "macro.3:cpp": "#dc803d",
            "macro.4:cpp": "#dd9549",
            "namespace:cpp": "#c6a94d",
            "namespace.1:cpp": "#8c6a25",
            "namespace.2:cpp": "#daca74",
            "namespace.3:cpp": "#ab722f",
            "namespace.4:cpp": "#a19435"
        }
    }

[sammccall]

This is cool! We've had a couple of looks at attributes, but haven't really gotten around to polishing it.
(For a submittable version, I think we should avoid introducing more modifiers at the same time, just to avoid getting bogged down in exactly which ones)

I like the idea of using modifiers to encode the rainbow variants - this avoids the need for a protocol extension. On the other hand, it's ugly to have the server rather than themes decide how many variants there should be. What do you think of having modifiers for each bit of the hash, rather than specific hash values?

i.e.
1 = bool(symbolid & 1)
2 = bool(symbolid & 2)
4 = bool(symbolid & 4)
etc.

Then the client can decide how many variants to style, as long as it's a power of 2: e.g. providing styles for variable, variable.1, variable.2, variable.1.2 should yield 4 uniform colors. With 8 attributes we can support 256 colors, which ought to be enough for anyone :-)

One catch here is that some tokens may not have a symbol id and can't be distinguished from all-bits-zero, we could provide a marker modifier like "0" so you can style variable.0, variable.1, variable.2, variable.1.2.

(Not sure whether it's more intuitive to name the attributes 0, 1, 2, 3... or 1, 2, 4, 8...)

From your description I'm not sure whether you're interested in upstreaming this yourself (revising through code review, writing tests, etc) or looking to hand the patch over to someone else - let me know!

[alexzielenski]

Hey Sam, Thanks for checking this out!

I really like your idea about encoding the variants with binary - as you say it removes the need for any assumption on the server's part for the limit of colors. However, I'd be wary of the fact that most users and theme creators don't know or understand binary and probably also don't want to learn binary. Indeed - I dont think users would easily accept (or obey) being limited to a power of 2 for their rainbow variants - and be subject to ambiguous behavior that arises when variable.1.2 is requested to be highlighted by a theme with only variable.1 and variable.2 entries.

Additionally, having creating a theme myself, I've come to understand that anyone would be hard pressed to find 256 visually distinct colors that are still similar enough to recognize as the same semantic type. I had a hard enough time finding 5 good ones even with the help of automated tools.

So I think for the server to have a small imposed limit would be okay (8 seems OK) - the only practical drawback I can think of with my current solution is you are forced to have 5 colors: If variable.4 is requested to be highlighted and you only have variable.1;variable.2;variable.3 defined by a theme, my current system with just highlight this with the unmodified variable. The binary-encoded system you propose would not have this issue and would properly "modulo" for the defined bits. Of course this could be a configuration option, but I don't like that either.

My intent for this patch is to get the ball rolling - I'm not really interesting in bringing it through the review process since I get enough of that at my day job 😅 (I also adjusted the visibility to users only to try to stay discreet) but I am happy to help influence discussion for this patch. I've been following clangd for a few years and have been happy that since around clangd-10/11 it seems to have gotten usable for my day-to-day use. Tools like these 10x developer productivity so good work!

clang-tools-extra/clangd/SemanticHighlighting.cpp

606

This method of managing the modifiers is pretty obviously bad.

clang-tools-extra/clangd/ClangdLSPServer.cpp

 }
 
 void ClangdLSPServer::notify(llvm::StringRef Method, llvm::json::Value Params) {
   log("--> {0}", Method);
   std::lock_guard<std::mutex> Lock(TranspWriter);
   Transp.notify(Method, std::move(Params));
 }
 
+static std::vector<llvm::StringRef> semanticTokenModifiers() {
+  std::vector<llvm::StringRef> Result;
+  Result.push_back("0");
+  Result.push_back("1");
+  Result.push_back("2");
+  Result.push_back("3");
+  Result.push_back("4");
+  Result.push_back("local");
+  Result.push_back("static");
+  Result.push_back("member");
+  // Result.push_back("const");
+  return Result;
+}
+
 static std::vector<llvm::StringRef> semanticTokenTypes() {
   std::vector<llvm::StringRef> Types;
   for (unsigned I = 0; I <= static_cast<unsigned>(HighlightingKind::LastKind);
        ++I)
     Types.push_back(toSemanticTokenType(static_cast<HighlightingKind>(I)));
   return Types;
 }
 
llvm::json::Object Result{
                  // We do extra checks, e.g. that > is part of ->.
                  {"triggerCharacters", {".", "<", ">", ":", "\"", "/"}},
              }},
             {"semanticTokensProvider",
              llvm::json::Object{
                  {"full", llvm::json::Object{{"delta", true}}},
                  {"range", false},
                  {"legend",
-                  llvm::json::Object{{"tokenTypes", semanticTokenTypes()},
-                                     {"tokenModifiers", llvm::json::Array()}}},
+                  llvm::json::Object{
+                      {"tokenTypes", semanticTokenTypes()},
+                      {"tokenModifiers", semanticTokenModifiers()}}},
              }},
             {"signatureHelpProvider",
              llvm::json::Object{
                  {"triggerCharacters", {"(", ","}},
              }},
             {"declarationProvider", true},
             {"definitionProvider", true},
             {"documentHighlightProvider", true},

clang-tools-extra/clangd/SemanticHighlighting.h

enum class HighlightingKind {
   LastKind = InactiveCode
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K);
 
 // Contains all information needed for the highlighting a token.
 struct HighlightingToken {
   HighlightingKind Kind;
   Range R;
+  unsigned char Index = 0;
 };
 
 bool operator==(const HighlightingToken &L, const HighlightingToken &R);
 bool operator<(const HighlightingToken &L, const HighlightingToken &R);
 
 /// Contains all information about highlightings on a single line.
 struct LineHighlightings {
   int Line;

clang-tools-extra/clangd/SemanticHighlighting.cpp

for (const NamedDecl *Decl : R.Targets) {
     auto Kind = kindForDecl(Decl);
     if (!Kind || (Result && Kind != Result))
       return llvm::None;
     Result = Kind;
   }
   return Result;
 }
 
+unsigned char idxForType(const Type *TP);
+unsigned char idxForDecl(const NamedDecl *D) {
+  if (auto *USD = dyn_cast<UsingShadowDecl>(D)) {
+    if (auto *Target = USD->getTargetDecl())
+      D = Target;
+  }
+  if (auto *TD = dyn_cast<TemplateDecl>(D)) {
+    if (auto *Templated = TD->getTemplatedDecl())
+      D = Templated;
+  }
+  if (auto *TD = dyn_cast<TypedefNameDecl>(D)) {
+    // We try to highlight typedefs as their underlying type.
+    if (auto K = idxForType(TD->getUnderlyingType().getTypePtrOrNull()))
+      return K;
+    // And fallback to a generic kind if this fails.
+    return 0;
+  }
+
+  if (auto ID = getSymbolID(D)) {
+    return hash_value(*ID) % 255;
+  }
+
+  return D->getGlobalID() % 255;
+}
+
+unsigned char idxForType(const Type *TP) {
+  if (!TP)
+    return 0;
+  if (TP->isBuiltinType()) // Builtins are special, they do not have decls.
+    return 0;
+  if (auto *TD = dyn_cast<TemplateTypeParmType>(TP))
+    return idxForDecl(TD->getDecl());
+  if (auto *TD = TP->getAsTagDecl())
+    return idxForDecl(TD);
+  return 0;
+}
+
+unsigned char idxForReference(const ReferenceLoc &R) {
+  unsigned char Result = 0;
+  for (const NamedDecl *Decl : R.Targets) {
+    if (!canHighlightName(Decl->getDeclName()))
+      continue;
+    Result = idxForDecl(Decl);
+  }
+  return Result;
+}
+
 // For a macro usage `DUMP(foo)`, we want:
 //  - DUMP --> "macro"
 //  - foo --> "variable".
 SourceLocation getHighlightableSpellingToken(SourceLocation L,
                                              const SourceManager &SM) {
   if (L.isFileID())
     return SM.isWrittenInMainFile(L) ? L : SourceLocation{};
   // Tokens expanded from the macro body contribute no 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); }
 
-  void addToken(SourceLocation Loc, HighlightingKind Kind) {
+  void addToken(SourceLocation Loc, HighlightingKind Kind,
+                unsigned char idx = 0) {
     Loc = getHighlightableSpellingToken(Loc, SourceMgr);
     if (Loc.isInvalid())
       return;
     const auto *Tok = TB.spelledTokenAt(Loc);
     assert(Tok);
 
     auto Range = halfOpenToRange(SourceMgr,
                                  Tok->range(SourceMgr).toCharRange(SourceMgr));
-    Tokens.push_back(HighlightingToken{Kind, std::move(Range)});
+    Tokens.push_back(HighlightingToken{Kind, std::move(Range), idx});
   }
 
   std::vector<HighlightingToken> collect(ParsedAST &AST) && {
     // 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());

 /// e.g. highlights dependent names and 'auto' as the underlying type.
 class CollectExtraHighlightings
     : public RecursiveASTVisitor<CollectExtraHighlightings> {
 public:
   CollectExtraHighlightings(HighlightingsBuilder &H) : H(H) {}
 
   bool VisitDecltypeTypeLoc(DecltypeTypeLoc L) {
     if (auto K = kindForType(L.getTypePtr()))
-      H.addToken(L.getBeginLoc(), *K);
+      H.addToken(L.getBeginLoc(), *K, idxForType(L.getTypePtr()));
     return true;
   }
 
   bool VisitDeclaratorDecl(DeclaratorDecl *D) {
     auto *AT = D->getType()->getContainedAutoType();
     if (!AT)
       return true;
     if (auto K = kindForType(AT->getDeducedType().getTypePtrOrNull()))
-      H.addToken(D->getTypeSpecStartLoc(), *K);
+      H.addToken(D->getTypeSpecStartLoc(), *K,
+                 idxForType(AT->getDeducedType().getTypePtrOrNull()));
     return true;
   }
 
   bool VisitOverloadExpr(OverloadExpr *E) {
     if (!E->decls().empty())
       return true; // handled by findExplicitReferences.
     H.addToken(E->getNameLoc(), HighlightingKind::DependentName);
     return true;
std::vector<HighlightingToken> getSemanticHighlightings(ParsedAST &AST) {
   auto &C = AST.getASTContext();
   // Add highlightings for AST nodes.
   HighlightingsBuilder Builder(AST);
   // Highlight 'decltype' and 'auto' as their underlying types.
   CollectExtraHighlightings(Builder).TraverseAST(C);
   // Highlight all decls and references coming from the AST.
   findExplicitReferences(C, [&](ReferenceLoc R) {
     if (auto Kind = kindForReference(R))
-      Builder.addToken(R.NameLoc, *Kind);
+      Builder.addToken(R.NameLoc, *Kind, idxForReference(R));
   });
   // Add highlightings for macro references.
   for (const auto &SIDToRefs : AST.getMacros().MacroRefs) {
     for (const auto &M : SIDToRefs.second)
-      Builder.addToken({HighlightingKind::Macro, M});
+      Builder.addToken(
+          {HighlightingKind::Macro, M,
+           static_cast<unsigned char>(hash_value(SIDToRefs.first) % 255)});
   }
   for (const auto &M : AST.getMacros().UnknownMacros)
     Builder.addToken({HighlightingKind::Macro, M});
 
   return std::move(Builder).collect(AST);
 }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K) {
if (Last) {
       }
     } else {
       Out.deltaLine = Tok.R.start.line;
       Out.deltaStart = Tok.R.start.character;
     }
     assert(Tok.R.end.line == Tok.R.start.line);
     Out.length = Tok.R.end.character - Tok.R.start.character;
     Out.tokenType = static_cast<unsigned>(Tok.Kind);
+    Out.tokenModifiers = static_cast<unsigned>(1UL << (Tok.Index % 5));
+
+    if (Tok.Kind == HighlightingKind::LocalVariable) {
+      Out.tokenModifiers |= 1 << 5;
+    } else if (Tok.Kind == HighlightingKind::StaticField) {
+      Out.tokenModifiers |= 1 << 6;
+    } else if (Tok.Kind == HighlightingKind::StaticMethod) {
+      Out.tokenModifiers |= 1 << 6;
+    } else if (Tok.Kind == HighlightingKind::Method) {
+      Out.tokenModifiers |= 1 << 7;
+    } else if (Tok.Kind == HighlightingKind::Field) {
+      Out.tokenModifiers |= 1 << 7;
+    }
 
     Last = &Tok;
   }
   return Result;
 }
 llvm::StringRef toSemanticTokenType(HighlightingKind Kind) {
   switch (Kind) {
   case HighlightingKind::Variable:
   case HighlightingKind::LocalVariable:
+  case HighlightingKind::Field:
   case HighlightingKind::StaticField:
     return "variable";
   case HighlightingKind::Parameter:
+    // should this be a modifier on variable?
     return "parameter";
-  case HighlightingKind::Function:
-    return "function";
   case HighlightingKind::Method:
-    return "member";
   case HighlightingKind::StaticMethod:
-    // FIXME: better function/member with static modifier?
+  case HighlightingKind::Function:
     return "function";
-  case HighlightingKind::Field:
-    return "member";
   case HighlightingKind::Class:
     return "class";
   case HighlightingKind::Enum:
     return "enum";
   case HighlightingKind::EnumConstant:
     return "enumConstant"; // nonstandard
   case HighlightingKind::Typedef:
     return "type";
   case HighlightingKind::DependentType:
     return "dependent"; // nonstandard
   case HighlightingKind::DependentName:
     return "dependent"; // nonstandard
   case HighlightingKind::Namespace:
     return "namespace";
   case HighlightingKind::TemplateParameter:
     return "typeParameter";
   case HighlightingKind::Concept:
     return "concept"; // nonstandard
   case HighlightingKind::Primitive:
     return "type";
   case HighlightingKind::Macro:
     return "macro";
+    // would be cool to change this into "function" or "variable"
+    //  with "preprocessor" modifier
   case HighlightingKind::InactiveCode:
     return "comment";
+    // add "preprocessor" modifier
   }
   llvm_unreachable("unhandled HighlightingKind");
 }
 
 std::vector<TheiaSemanticHighlightingInformation>
 toTheiaSemanticHighlightingInformation(
     llvm::ArrayRef<LineHighlightings> Tokens) {
   if (Tokens.size() == 0)