clang-tools-extra/clangd/SemanticHighlighting.cpp

   1 //===--- SemanticHighlighting.cpp - ------------------------- ---*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "SemanticHighlighting.h"
  10 #include "Config.h"
  11 #include "FindTarget.h"
  12 #include "HeuristicResolver.h"
  13 #include "ParsedAST.h"
  14 #include "Protocol.h"
  15 #include "SourceCode.h"
  16 #include "support/Logger.h"
  17 #include "clang/AST/ASTContext.h"
  18 #include "clang/AST/Decl.h"
  19 #include "clang/AST/DeclCXX.h"
  20 #include "clang/AST/DeclObjC.h"
  21 #include "clang/AST/DeclTemplate.h"
  22 #include "clang/AST/DeclarationName.h"
  23 #include "clang/AST/ExprCXX.h"
  24 #include "clang/AST/RecursiveASTVisitor.h"
  25 #include "clang/AST/Type.h"
  26 #include "clang/AST/TypeLoc.h"
  27 #include "clang/Basic/LangOptions.h"
  28 #include "clang/Basic/SourceLocation.h"
  29 #include "clang/Basic/SourceManager.h"
  30 #include "clang/Tooling/Syntax/Tokens.h"
  31 #include "llvm/ADT/STLExtras.h"
  32 #include "llvm/ADT/StringRef.h"
  33 #include "llvm/Support/Casting.h"
  34 #include "llvm/Support/Error.h"
  35 #include <algorithm>
  36 #include <optional>
  37
  38 namespace clang {
  39 namespace clangd {
  40 namespace {
  41
  42 /// Get the last Position on a given line.
  43 llvm::Expected<Position> endOfLine(llvm::StringRef Code, int Line) {
  44   auto StartOfLine = positionToOffset(Code, Position{Line, 0});
  45   if (!StartOfLine)
  46     return StartOfLine.takeError();
  47   StringRef LineText = Code.drop_front(*StartOfLine).take_until([](char C) {
  48     return C == '\n';
  49   });
  50   return Position{Line, static_cast<int>(lspLength(LineText))};
  51 }
  52
  53 /// Some names are not written in the source code and cannot be highlighted,
  54 /// e.g. anonymous classes. This function detects those cases.
  55 bool canHighlightName(DeclarationName Name) {
  56   switch (Name.getNameKind()) {
  57   case DeclarationName::Identifier: {
  58     auto *II = Name.getAsIdentifierInfo();
  59     return II && !II->getName().empty();
  60   }
  61   case DeclarationName::CXXConstructorName:
  62   case DeclarationName::CXXDestructorName:
  63     return true;
  64   case DeclarationName::ObjCZeroArgSelector:
  65   case DeclarationName::ObjCOneArgSelector:
  66   case DeclarationName::ObjCMultiArgSelector:
  67     // Multi-arg selectors need special handling, and we handle 0/1 arg
  68     // selectors there too.
  69     return false;
  70   case DeclarationName::CXXConversionFunctionName:
  71   case DeclarationName::CXXOperatorName:
  72   case DeclarationName::CXXDeductionGuideName:
  73   case DeclarationName::CXXLiteralOperatorName:
  74   case DeclarationName::CXXUsingDirective:
  75     return false;
  76   }
  77   llvm_unreachable("invalid name kind");
  78 }
  79
  80 bool isUniqueDefinition(const NamedDecl *Decl) {
  81   if (auto *Func = dyn_cast<FunctionDecl>(Decl))
  82     return Func->isThisDeclarationADefinition();
  83   if (auto *Klass = dyn_cast<CXXRecordDecl>(Decl))
  84     return Klass->isThisDeclarationADefinition();
  85   if (auto *Iface = dyn_cast<ObjCInterfaceDecl>(Decl))
  86     return Iface->isThisDeclarationADefinition();
  87   if (auto *Proto = dyn_cast<ObjCProtocolDecl>(Decl))
  88     return Proto->isThisDeclarationADefinition();
  89   if (auto *Var = dyn_cast<VarDecl>(Decl))
  90     return Var->isThisDeclarationADefinition();
  91   return isa<TemplateTypeParmDecl>(Decl) ||
  92          isa<NonTypeTemplateParmDecl>(Decl) ||
  93          isa<TemplateTemplateParmDecl>(Decl) || isa<ObjCCategoryDecl>(Decl) ||
  94          isa<ObjCImplDecl>(Decl);
  95 }
  96
  97 std::optional<HighlightingKind> kindForType(const Type *TP,
  98                                             const HeuristicResolver *Resolver);
  99 std::optional<HighlightingKind> kindForDecl(const NamedDecl *D,
 100                                             const HeuristicResolver *Resolver) {
 101   if (auto *USD = dyn_cast<UsingShadowDecl>(D)) {
 102     if (auto *Target = USD->getTargetDecl())
 103       D = Target;
 104   }
 105   if (auto *TD = dyn_cast<TemplateDecl>(D)) {
 106     if (auto *Templated = TD->getTemplatedDecl())
 107       D = Templated;
 108   }
 109   if (auto *TD = dyn_cast<TypedefNameDecl>(D)) {
 110     // We try to highlight typedefs as their underlying type.
 111     if (auto K =
 112             kindForType(TD->getUnderlyingType().getTypePtrOrNull(), Resolver))
 113       return K;
 114     // And fallback to a generic kind if this fails.
 115     return HighlightingKind::Typedef;
 116   }
 117   // We highlight class decls, constructor decls and destructor decls as
 118   // `Class` type. The destructor decls are handled in `VisitTagTypeLoc` (we
 119   // will visit a TypeLoc where the underlying Type is a CXXRecordDecl).
 120   if (auto *RD = llvm::dyn_cast<RecordDecl>(D)) {
 121     // We don't want to highlight lambdas like classes.
 122     if (RD->isLambda())
 123       return std::nullopt;
 124     return HighlightingKind::Class;
 125   }
 126   if (isa<ClassTemplateDecl, RecordDecl, CXXConstructorDecl, ObjCInterfaceDecl,
 127           ObjCImplementationDecl>(D))
 128     return HighlightingKind::Class;
 129   if (isa<ObjCProtocolDecl>(D))
 130     return HighlightingKind::Interface;
 131   if (isa<ObjCCategoryDecl, ObjCCategoryImplDecl>(D))
 132     return HighlightingKind::Namespace;
 133   if (auto *MD = dyn_cast<CXXMethodDecl>(D))
 134     return MD->isStatic() ? HighlightingKind::StaticMethod
 135                           : HighlightingKind::Method;
 136   if (auto *OMD = dyn_cast<ObjCMethodDecl>(D))
 137     return OMD->isClassMethod() ? HighlightingKind::StaticMethod
 138                                 : HighlightingKind::Method;
 139   if (isa<FieldDecl, ObjCPropertyDecl>(D))
 140     return HighlightingKind::Field;
 141   if (isa<EnumDecl>(D))
 142     return HighlightingKind::Enum;
 143   if (isa<EnumConstantDecl>(D))
 144     return HighlightingKind::EnumConstant;
 145   if (isa<ParmVarDecl>(D))
 146     return HighlightingKind::Parameter;
 147   if (auto *VD = dyn_cast<VarDecl>(D)) {
 148     if (isa<ImplicitParamDecl>(VD)) // e.g. ObjC Self
 149       return std::nullopt;
 150     return VD->isStaticDataMember()
 151                ? HighlightingKind::StaticField
 152                : VD->isLocalVarDecl() ? HighlightingKind::LocalVariable
 153                                       : HighlightingKind::Variable;
 154   }
 155   if (const auto *BD = dyn_cast<BindingDecl>(D))
 156     return BD->getDeclContext()->isFunctionOrMethod()
 157                ? HighlightingKind::LocalVariable
 158                : HighlightingKind::Variable;
 159   if (isa<FunctionDecl>(D))
 160     return HighlightingKind::Function;
 161   if (isa<NamespaceDecl>(D) || isa<NamespaceAliasDecl>(D) ||
 162       isa<UsingDirectiveDecl>(D))
 163     return HighlightingKind::Namespace;
 164   if (isa<TemplateTemplateParmDecl>(D) || isa<TemplateTypeParmDecl>(D) ||
 165       isa<NonTypeTemplateParmDecl>(D))
 166     return HighlightingKind::TemplateParameter;
 167   if (isa<ConceptDecl>(D))
 168     return HighlightingKind::Concept;
 169   if (isa<LabelDecl>(D))
 170     return HighlightingKind::Label;
 171   if (const auto *UUVD = dyn_cast<UnresolvedUsingValueDecl>(D)) {
 172     auto Targets = Resolver->resolveUsingValueDecl(UUVD);
 173     if (!Targets.empty() && Targets[0] != UUVD) {
 174       return kindForDecl(Targets[0], Resolver);
 175     }
 176     return HighlightingKind::Unknown;
 177   }
 178   return std::nullopt;
 179 }
 180 std::optional<HighlightingKind> kindForType(const Type *TP,
 181                                             const HeuristicResolver *Resolver) {
 182   if (!TP)
 183     return std::nullopt;
 184   if (TP->isBuiltinType()) // Builtins are special, they do not have decls.
 185     return HighlightingKind::Primitive;
 186   if (auto *TD = dyn_cast<TemplateTypeParmType>(TP))
 187     return kindForDecl(TD->getDecl(), Resolver);
 188   if (isa<ObjCObjectPointerType>(TP))
 189     return HighlightingKind::Class;
 190   if (auto *TD = TP->getAsTagDecl())
 191     return kindForDecl(TD, Resolver);
 192   return std::nullopt;
 193 }
 194
 195 // Whether T is const in a loose sense - is a variable with this type readonly?
 196 bool isConst(QualType T) {
 197   if (T.isNull())
 198     return false;
 199   T = T.getNonReferenceType();
 200   if (T.isConstQualified())
 201     return true;
 202   if (const auto *AT = T->getAsArrayTypeUnsafe())
 203     return isConst(AT->getElementType());
 204   if (isConst(T->getPointeeType()))
 205     return true;
 206   return false;
 207 }
 208
 209 // Whether D is const in a loose sense (should it be highlighted as such?)
 210 // FIXME: This is separate from whether *a particular usage* can mutate D.
 211 //        We may want V in V.size() to be readonly even if V is mutable.
 212 bool isConst(const Decl *D) {
 213   if (llvm::isa<EnumConstantDecl>(D) || llvm::isa<NonTypeTemplateParmDecl>(D))
 214     return true;
 215   if (llvm::isa<FieldDecl>(D) || llvm::isa<VarDecl>(D) ||
 216       llvm::isa<MSPropertyDecl>(D) || llvm::isa<BindingDecl>(D)) {
 217     if (isConst(llvm::cast<ValueDecl>(D)->getType()))
 218       return true;
 219   }
 220   if (const auto *OCPD = llvm::dyn_cast<ObjCPropertyDecl>(D)) {
 221     if (OCPD->isReadOnly())
 222       return true;
 223   }
 224   if (const auto *MPD = llvm::dyn_cast<MSPropertyDecl>(D)) {
 225     if (!MPD->hasSetter())
 226       return true;
 227   }
 228   if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D)) {
 229     if (CMD->isConst())
 230       return true;
 231   }
 232   return false;
 233 }
 234
 235 // "Static" means many things in C++, only some get the "static" modifier.
 236 //
 237 // Meanings that do:
 238 // - Members associated with the class rather than the instance.
 239 //   This is what 'static' most often means across languages.
 240 // - static local variables
 241 //   These are similarly "detached from their context" by the static keyword.
 242 //   In practice, these are rarely used inside classes, reducing confusion.
 243 //
 244 // Meanings that don't:
 245 // - Namespace-scoped variables, which have static storage class.
 246 //   This is implicit, so the keyword "static" isn't so strongly associated.
 247 //   If we want a modifier for these, "global scope" is probably the concept.
 248 // - Namespace-scoped variables/functions explicitly marked "static".
 249 //   There the keyword changes *linkage* , which is a totally different concept.
 250 //   If we want to model this, "file scope" would be a nice modifier.
 251 //
 252 // This is confusing, and maybe we should use another name, but because "static"
 253 // is a standard LSP modifier, having one with that name has advantages.
 254 bool isStatic(const Decl *D) {
 255   if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D))
 256     return CMD->isStatic();
 257   if (const VarDecl *VD = llvm::dyn_cast<VarDecl>(D))
 258     return VD->isStaticDataMember() || VD->isStaticLocal();
 259   if (const auto *OPD = llvm::dyn_cast<ObjCPropertyDecl>(D))
 260     return OPD->isClassProperty();
 261   if (const auto *OMD = llvm::dyn_cast<ObjCMethodDecl>(D))
 262     return OMD->isClassMethod();
 263   return false;
 264 }
 265
 266 bool isAbstract(const Decl *D) {
 267   if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D))
 268     return CMD->isPure();
 269   if (const auto *CRD = llvm::dyn_cast<CXXRecordDecl>(D))
 270     return CRD->hasDefinition() && CRD->isAbstract();
 271   return false;
 272 }
 273
 274 bool isVirtual(const Decl *D) {
 275   if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D))
 276     return CMD->isVirtual();
 277   return false;
 278 }
 279
 280 bool isDependent(const Decl *D) {
 281   if (isa<UnresolvedUsingValueDecl>(D))
 282     return true;
 283   return false;
 284 }
 285
 286 /// Returns true if `Decl` is considered to be from a default/system library.
 287 /// This currently checks the systemness of the file by include type, although
 288 /// different heuristics may be used in the future (e.g. sysroot paths).
 289 bool isDefaultLibrary(const Decl *D) {
 290   SourceLocation Loc = D->getLocation();
 291   if (!Loc.isValid())
 292     return false;
 293   return D->getASTContext().getSourceManager().isInSystemHeader(Loc);
 294 }
 295
 296 bool isDefaultLibrary(const Type *T) {
 297   if (!T)
 298     return false;
 299   const Type *Underlying = T->getPointeeOrArrayElementType();
 300   if (Underlying->isBuiltinType())
 301     return true;
 302   if (auto *TD = dyn_cast<TemplateTypeParmType>(Underlying))
 303     return isDefaultLibrary(TD->getDecl());
 304   if (auto *TD = Underlying->getAsTagDecl())
 305     return isDefaultLibrary(TD);
 306   return false;
 307 }
 308
 309 // For a macro usage `DUMP(foo)`, we want:
 310 //  - DUMP --> "macro"
 311 //  - foo --> "variable".
 312 SourceLocation getHighlightableSpellingToken(SourceLocation L,
 313                                              const SourceManager &SM) {
 314   if (L.isFileID())
 315     return SM.isWrittenInMainFile(L) ? L : SourceLocation{};
 316   // Tokens expanded from the macro body contribute no highlightings.
 317   if (!SM.isMacroArgExpansion(L))
 318     return {};
 319   // Tokens expanded from macro args are potentially highlightable.
 320   return getHighlightableSpellingToken(SM.getImmediateSpellingLoc(L), SM);
 321 }
 322
 323 unsigned evaluateHighlightPriority(const HighlightingToken &Tok) {
 324   enum HighlightPriority { Dependent = 0, Resolved = 1 };
 325   return (Tok.Modifiers & (1 << uint32_t(HighlightingModifier::DependentName)))
 326              ? Dependent
 327              : Resolved;
 328 }
 329
 330 // Sometimes we get multiple tokens at the same location:
 331 //
 332 // - findExplicitReferences() returns a heuristic result for a dependent name
 333 //   (e.g. Method) and CollectExtraHighlighting returning a fallback dependent
 334 //   highlighting (e.g. Unknown+Dependent).
 335 // - macro arguments are expanded multiple times and have different roles
 336 // - broken code recovery produces several AST nodes at the same location
 337 //
 338 // We should either resolve these to a single token, or drop them all.
 339 // Our heuristics are:
 340 //
 341 // - token kinds that come with "dependent-name" modifiers are less reliable
 342 //   (these tend to be vague, like Type or Unknown)
 343 // - if we have multiple equally reliable kinds, drop token rather than guess
 344 // - take the union of modifiers from all tokens
 345 //
 346 // In particular, heuristically resolved dependent names get their heuristic
 347 // kind, plus the dependent modifier.
 348 std::optional<HighlightingToken> resolveConflict(const HighlightingToken &A,
 349                                                  const HighlightingToken &B) {
 350   unsigned Priority1 = evaluateHighlightPriority(A);
 351   unsigned Priority2 = evaluateHighlightPriority(B);
 352   if (Priority1 == Priority2 && A.Kind != B.Kind)
 353     return std::nullopt;
 354   auto Result = Priority1 > Priority2 ? A : B;
 355   Result.Modifiers = A.Modifiers | B.Modifiers;
 356   return Result;
 357 }
 358 std::optional<HighlightingToken>
 359 resolveConflict(ArrayRef<HighlightingToken> Tokens) {
 360   if (Tokens.size() == 1)
 361     return Tokens[0];
 362
 363   assert(Tokens.size() >= 2);
 364   std::optional<HighlightingToken> Winner =
 365       resolveConflict(Tokens[0], Tokens[1]);
 366   for (size_t I = 2; Winner && I < Tokens.size(); ++I)
 367     Winner = resolveConflict(*Winner, Tokens[I]);
 368   return Winner;
 369 }
 370
 371 /// Filter to remove particular kinds of highlighting tokens and modifiers from
 372 /// the output.
 373 class HighlightingFilter {
 374 public:
 375   HighlightingFilter() {
 376     for (auto &Active : ActiveKindLookup)
 377       Active = true;
 378
 379     ActiveModifiersMask = ~0;
 380   }
 381
 382   void disableKind(HighlightingKind Kind) {
 383     ActiveKindLookup[static_cast<size_t>(Kind)] = false;
 384   }
 385
 386   void disableModifier(HighlightingModifier Modifier) {
 387     ActiveModifiersMask &= ~(1 << static_cast<uint32_t>(Modifier));
 388   }
 389
 390   bool isHighlightKindActive(HighlightingKind Kind) const {
 391     return ActiveKindLookup[static_cast<size_t>(Kind)];
 392   }
 393
 394   uint32_t maskModifiers(uint32_t Modifiers) const {
 395     return Modifiers & ActiveModifiersMask;
 396   }
 397
 398   static HighlightingFilter fromCurrentConfig() {
 399     const Config &C = Config::current();
 400     HighlightingFilter Filter;
 401     for (const auto &Kind : C.SemanticTokens.DisabledKinds)
 402       if (auto K = highlightingKindFromString(Kind))
 403         Filter.disableKind(*K);
 404     for (const auto &Modifier : C.SemanticTokens.DisabledModifiers)
 405       if (auto M = highlightingModifierFromString(Modifier))
 406         Filter.disableModifier(*M);
 407
 408     return Filter;
 409   }
 410
 411 private:
 412   bool ActiveKindLookup[static_cast<size_t>(HighlightingKind::LastKind) + 1];
 413   uint32_t ActiveModifiersMask;
 414 };
 415
 416 /// Consumes source locations and maps them to text ranges for highlightings.
 417 class HighlightingsBuilder {
 418 public:
 419   HighlightingsBuilder(const ParsedAST &AST, const HighlightingFilter &Filter)
 420       : TB(AST.getTokens()), SourceMgr(AST.getSourceManager()),
 421         LangOpts(AST.getLangOpts()), Filter(Filter) {}
 422
 423   HighlightingToken &addToken(SourceLocation Loc, HighlightingKind Kind) {
 424     auto Range = getRangeForSourceLocation(Loc);
 425     if (!Range)
 426       return InvalidHighlightingToken;
 427
 428     return addToken(*Range, Kind);
 429   }
 430
 431   // Most of this function works around
 432   // https://github.com/clangd/clangd/issues/871.
 433   void addAngleBracketTokens(SourceLocation LLoc, SourceLocation RLoc) {
 434     if (!LLoc.isValid() || !RLoc.isValid())
 435       return;
 436
 437     auto LRange = getRangeForSourceLocation(LLoc);
 438     if (!LRange)
 439       return;
 440
 441     // RLoc might be pointing at a virtual buffer when it's part of a `>>`
 442     // token.
 443     RLoc = SourceMgr.getFileLoc(RLoc);
 444     // Make sure token is part of the main file.
 445     RLoc = getHighlightableSpellingToken(RLoc, SourceMgr);
 446     if (!RLoc.isValid())
 447       return;
 448
 449     const auto *RTok = TB.spelledTokenAt(RLoc);
 450     // Handle `>>`. RLoc is always pointing at the right location, just change
 451     // the end to be offset by 1.
 452     // We'll either point at the beginning of `>>`, hence get a proper spelled
 453     // or point in the middle of `>>` hence get no spelled tok.
 454     if (!RTok || RTok->kind() == tok::greatergreater) {
 455       Position Begin = sourceLocToPosition(SourceMgr, RLoc);
 456       Position End = sourceLocToPosition(SourceMgr, RLoc.getLocWithOffset(1));
 457       addToken(*LRange, HighlightingKind::Bracket);
 458       addToken({Begin, End}, HighlightingKind::Bracket);
 459       return;
 460     }
 461
 462     // Easy case, we have the `>` token directly available.
 463     if (RTok->kind() == tok::greater) {
 464       if (auto RRange = getRangeForSourceLocation(RLoc)) {
 465         addToken(*LRange, HighlightingKind::Bracket);
 466         addToken(*RRange, HighlightingKind::Bracket);
 467       }
 468       return;
 469     }
 470   }
 471
 472   HighlightingToken &addToken(Range R, HighlightingKind Kind) {
 473     if (!Filter.isHighlightKindActive(Kind))
 474       return InvalidHighlightingToken;
 475
 476     HighlightingToken HT;
 477     HT.R = std::move(R);
 478     HT.Kind = Kind;
 479     Tokens.push_back(std::move(HT));
 480     return Tokens.back();
 481   }
 482
 483   void addExtraModifier(SourceLocation Loc, HighlightingModifier Modifier) {
 484     if (auto Range = getRangeForSourceLocation(Loc))
 485       ExtraModifiers[*Range].push_back(Modifier);
 486   }
 487
 488   std::vector<HighlightingToken> collect(ParsedAST &AST) && {
 489     // Initializer lists can give duplicates of tokens, therefore all tokens
 490     // must be deduplicated.
 491     llvm::sort(Tokens);
 492     auto Last = std::unique(Tokens.begin(), Tokens.end());
 493     Tokens.erase(Last, Tokens.end());
 494
 495     // Macros can give tokens that have the same source range but conflicting
 496     // kinds. In this case all tokens sharing this source range should be
 497     // removed.
 498     std::vector<HighlightingToken> NonConflicting;
 499     NonConflicting.reserve(Tokens.size());
 500     for (ArrayRef<HighlightingToken> TokRef = Tokens; !TokRef.empty();) {
 501       ArrayRef<HighlightingToken> Conflicting =
 502           TokRef.take_while([&](const HighlightingToken &T) {
 503             // TokRef is guaranteed at least one element here because otherwise
 504             // this predicate would never fire.
 505             return T.R == TokRef.front().R;
 506           });
 507       if (auto Resolved = resolveConflict(Conflicting)) {
 508         // Apply extra collected highlighting modifiers
 509         auto Modifiers = ExtraModifiers.find(Resolved->R);
 510         if (Modifiers != ExtraModifiers.end()) {
 511           for (HighlightingModifier Mod : Modifiers->second) {
 512             Resolved->addModifier(Mod);
 513           }
 514         }
 515
 516         Resolved->Modifiers = Filter.maskModifiers(Resolved->Modifiers);
 517         NonConflicting.push_back(*Resolved);
 518       }
 519       // TokRef[Conflicting.size()] is the next token with a different range (or
 520       // the end of the Tokens).
 521       TokRef = TokRef.drop_front(Conflicting.size());
 522     }
 523
 524     if (!Filter.isHighlightKindActive(HighlightingKind::InactiveCode))
 525       return NonConflicting;
 526
 527     const auto &SM = AST.getSourceManager();
 528     StringRef MainCode = SM.getBufferOrFake(SM.getMainFileID()).getBuffer();
 529
 530     // Merge token stream with "inactive line" markers.
 531     std::vector<HighlightingToken> WithInactiveLines;
 532     auto SortedInactiveRegions = getInactiveRegions(AST);
 533     llvm::sort(SortedInactiveRegions);
 534     auto It = NonConflicting.begin();
 535     for (const Range &R : SortedInactiveRegions) {
 536       // Create one token for each line in the inactive range, so it works
 537       // with line-based diffing.
 538       assert(R.start.line <= R.end.line);
 539       for (int Line = R.start.line; Line <= R.end.line; ++Line) {
 540         // Copy tokens before the inactive line
 541         for (; It != NonConflicting.end() && It->R.start.line < Line; ++It)
 542           WithInactiveLines.push_back(std::move(*It));
 543         // Add a token for the inactive line itself.
 544         auto EndOfLine = endOfLine(MainCode, Line);
 545         if (EndOfLine) {
 546           HighlightingToken HT;
 547           WithInactiveLines.emplace_back();
 548           WithInactiveLines.back().Kind = HighlightingKind::InactiveCode;
 549           WithInactiveLines.back().R.start.line = Line;
 550           WithInactiveLines.back().R.end = *EndOfLine;
 551         } else {
 552           elog("Failed to determine end of line: {0}", EndOfLine.takeError());
 553         }
 554
 555         // Skip any other tokens on the inactive line. e.g.
 556         // `#ifndef Foo` is considered as part of an inactive region when Foo is
 557         // defined, and there is a Foo macro token.
 558         // FIXME: we should reduce the scope of the inactive region to not
 559         // include the directive itself.
 560         while (It != NonConflicting.end() && It->R.start.line == Line)
 561           ++It;
 562       }
 563     }
 564     // Copy tokens after the last inactive line
 565     for (; It != NonConflicting.end(); ++It)
 566       WithInactiveLines.push_back(std::move(*It));
 567     return WithInactiveLines;
 568   }
 569
 570   const HeuristicResolver *getResolver() const { return Resolver; }
 571
 572 private:
 573   std::optional<Range> getRangeForSourceLocation(SourceLocation Loc) {
 574     Loc = getHighlightableSpellingToken(Loc, SourceMgr);
 575     if (Loc.isInvalid())
 576       return std::nullopt;
 577     // We might have offsets in the main file that don't correspond to any
 578     // spelled tokens.
 579     const auto *Tok = TB.spelledTokenAt(Loc);
 580     if (!Tok)
 581       return std::nullopt;
 582     return halfOpenToRange(SourceMgr,
 583                            Tok->range(SourceMgr).toCharRange(SourceMgr));
 584   }
 585
 586   const syntax::TokenBuffer &TB;
 587   const SourceManager &SourceMgr;
 588   const LangOptions &LangOpts;
 589   HighlightingFilter Filter;
 590   std::vector<HighlightingToken> Tokens;
 591   std::map<Range, llvm::SmallVector<HighlightingModifier, 1>> ExtraModifiers;
 592   const HeuristicResolver *Resolver = nullptr;
 593   // returned from addToken(InvalidLoc)
 594   HighlightingToken InvalidHighlightingToken;
 595 };
 596
 597 std::optional<HighlightingModifier> scopeModifier(const NamedDecl *D) {
 598   const DeclContext *DC = D->getDeclContext();
 599   // Injected "Foo" within the class "Foo" has file scope, not class scope.
 600   if (auto *R = dyn_cast_or_null<RecordDecl>(D))
 601     if (R->isInjectedClassName())
 602       DC = DC->getParent();
 603   // Lambda captures are considered function scope, not class scope.
 604   if (llvm::isa<FieldDecl>(D))
 605     if (const auto *RD = llvm::dyn_cast<RecordDecl>(DC))
 606       if (RD->isLambda())
 607         return HighlightingModifier::FunctionScope;
 608   // Walk up the DeclContext hierarchy until we find something interesting.
 609   for (; !DC->isFileContext(); DC = DC->getParent()) {
 610     if (DC->isFunctionOrMethod())
 611       return HighlightingModifier::FunctionScope;
 612     if (DC->isRecord())
 613       return HighlightingModifier::ClassScope;
 614   }
 615   // Some template parameters (e.g. those for variable templates) don't have
 616   // meaningful DeclContexts. That doesn't mean they're global!
 617   if (DC->isTranslationUnit() && D->isTemplateParameter())
 618     return std::nullopt;
 619   // ExternalLinkage threshold could be tweaked, e.g. module-visible as global.
 620   if (D->getLinkageInternal() < ExternalLinkage)
 621     return HighlightingModifier::FileScope;
 622   return HighlightingModifier::GlobalScope;
 623 }
 624
 625 std::optional<HighlightingModifier> scopeModifier(const Type *T) {
 626   if (!T)
 627     return std::nullopt;
 628   if (T->isBuiltinType())
 629     return HighlightingModifier::GlobalScope;
 630   if (auto *TD = dyn_cast<TemplateTypeParmType>(T))
 631     return scopeModifier(TD->getDecl());
 632   if (auto *TD = T->getAsTagDecl())
 633     return scopeModifier(TD);
 634   return std::nullopt;
 635 }
 636
 637 /// Produces highlightings, which are not captured by findExplicitReferences,
 638 /// e.g. highlights dependent names and 'auto' as the underlying type.
 639 class CollectExtraHighlightings
 640     : public RecursiveASTVisitor<CollectExtraHighlightings> {
 641   using Base = RecursiveASTVisitor<CollectExtraHighlightings>;
 642
 643 public:
 644   CollectExtraHighlightings(HighlightingsBuilder &H) : H(H) {}
 645
 646   bool VisitCXXConstructExpr(CXXConstructExpr *E) {
 647     highlightMutableReferenceArguments(E->getConstructor(),
 648                                        {E->getArgs(), E->getNumArgs()});
 649
 650     return true;
 651   }
 652
 653   bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
 654     if (Init->isMemberInitializer())
 655       if (auto *Member = Init->getMember())
 656         highlightMutableReferenceArgument(Member->getType(), Init->getInit());
 657     return Base::TraverseConstructorInitializer(Init);
 658   }
 659
 660   bool TraverseTypeConstraint(const TypeConstraint *C) {
 661     if (auto *Args = C->getTemplateArgsAsWritten())
 662       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 663     return Base::TraverseTypeConstraint(C);
 664   }
 665
 666   bool VisitPredefinedExpr(PredefinedExpr *E) {
 667     H.addToken(E->getLocation(), HighlightingKind::LocalVariable)
 668         .addModifier(HighlightingModifier::Static)
 669         .addModifier(HighlightingModifier::Readonly)
 670         .addModifier(HighlightingModifier::FunctionScope);
 671     return true;
 672   }
 673
 674   bool VisitConceptSpecializationExpr(ConceptSpecializationExpr *E) {
 675     if (auto *Args = E->getTemplateArgsAsWritten())
 676       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 677     return true;
 678   }
 679
 680   bool VisitTemplateDecl(TemplateDecl *D) {
 681     if (auto *TPL = D->getTemplateParameters())
 682       H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 683     return true;
 684   }
 685
 686   bool VisitTagDecl(TagDecl *D) {
 687     for (unsigned i = 0; i < D->getNumTemplateParameterLists(); ++i) {
 688       if (auto *TPL = D->getTemplateParameterList(i))
 689         H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 690     }
 691     return true;
 692   }
 693
 694   bool VisitClassTemplatePartialSpecializationDecl(
 695       ClassTemplatePartialSpecializationDecl *D) {
 696     if (auto *TPL = D->getTemplateParameters())
 697       H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 698     if (auto *Args = D->getTemplateArgsAsWritten())
 699       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 700     return true;
 701   }
 702
 703   bool VisitVarTemplateSpecializationDecl(VarTemplateSpecializationDecl *D) {
 704     if (auto *Args = D->getTemplateArgsInfo())
 705       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 706     return true;
 707   }
 708
 709   bool VisitVarTemplatePartialSpecializationDecl(
 710       VarTemplatePartialSpecializationDecl *D) {
 711     if (auto *TPL = D->getTemplateParameters())
 712       H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 713     if (auto *Args = D->getTemplateArgsAsWritten())
 714       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 715     return true;
 716   }
 717
 718   bool VisitDeclRefExpr(DeclRefExpr *E) {
 719     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
 720     return true;
 721   }
 722   bool VisitMemberExpr(MemberExpr *E) {
 723     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
 724     return true;
 725   }
 726
 727   bool VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) {
 728     H.addAngleBracketTokens(L.getLAngleLoc(), L.getRAngleLoc());
 729     return true;
 730   }
 731
 732   bool VisitFunctionDecl(FunctionDecl *D) {
 733     if (D->isOverloadedOperator()) {
 734       const auto AddOpDeclToken = [&](SourceLocation Loc) {
 735         auto &Token = H.addToken(Loc, HighlightingKind::Operator)
 736                           .addModifier(HighlightingModifier::Declaration);
 737         if (D->isThisDeclarationADefinition())
 738           Token.addModifier(HighlightingModifier::Definition);
 739       };
 740       const auto Range = D->getNameInfo().getCXXOperatorNameRange();
 741       AddOpDeclToken(Range.getBegin());
 742       const auto Kind = D->getOverloadedOperator();
 743       if (Kind == OO_Call || Kind == OO_Subscript)
 744         AddOpDeclToken(Range.getEnd());
 745     }
 746     if (auto *Args = D->getTemplateSpecializationArgsAsWritten())
 747       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 748     return true;
 749   }
 750
 751   bool VisitCXXOperatorCallExpr(CXXOperatorCallExpr *E) {
 752     const auto AddOpToken = [&](SourceLocation Loc) {
 753       H.addToken(Loc, HighlightingKind::Operator)
 754           .addModifier(HighlightingModifier::UserDefined);
 755     };
 756     AddOpToken(E->getOperatorLoc());
 757     const auto Kind = E->getOperator();
 758     if (Kind == OO_Call || Kind == OO_Subscript) {
 759       if (auto *Callee = E->getCallee())
 760         AddOpToken(Callee->getBeginLoc());
 761     }
 762     return true;
 763   }
 764
 765   bool VisitUnaryOperator(UnaryOperator *Op) {
 766     auto &Token = H.addToken(Op->getOperatorLoc(), HighlightingKind::Operator);
 767     if (Op->getSubExpr()->isTypeDependent())
 768       Token.addModifier(HighlightingModifier::UserDefined);
 769     return true;
 770   }
 771
 772   bool VisitBinaryOperator(BinaryOperator *Op) {
 773     auto &Token = H.addToken(Op->getOperatorLoc(), HighlightingKind::Operator);
 774     if (Op->getLHS()->isTypeDependent() || Op->getRHS()->isTypeDependent())
 775       Token.addModifier(HighlightingModifier::UserDefined);
 776     return true;
 777   }
 778
 779   bool VisitConditionalOperator(ConditionalOperator *Op) {
 780     H.addToken(Op->getQuestionLoc(), HighlightingKind::Operator);
 781     H.addToken(Op->getColonLoc(), HighlightingKind::Operator);
 782     return true;
 783   }
 784
 785   bool VisitCXXNewExpr(CXXNewExpr *E) {
 786     auto &Token = H.addToken(E->getBeginLoc(), HighlightingKind::Operator);
 787     if (isa_and_present<CXXMethodDecl>(E->getOperatorNew()))
 788       Token.addModifier(HighlightingModifier::UserDefined);
 789     return true;
 790   }
 791
 792   bool VisitCXXDeleteExpr(CXXDeleteExpr *E) {
 793     auto &Token = H.addToken(E->getBeginLoc(), HighlightingKind::Operator);
 794     if (isa_and_present<CXXMethodDecl>(E->getOperatorDelete()))
 795       Token.addModifier(HighlightingModifier::UserDefined);
 796     return true;
 797   }
 798
 799   bool VisitCXXNamedCastExpr(CXXNamedCastExpr *E) {
 800     const auto &B = E->getAngleBrackets();
 801     H.addAngleBracketTokens(B.getBegin(), B.getEnd());
 802     return true;
 803   }
 804
 805   bool VisitCallExpr(CallExpr *E) {
 806     // Highlighting parameters passed by non-const reference does not really
 807     // make sense for literals...
 808     if (isa<UserDefinedLiteral>(E))
 809       return true;
 810
 811     // FIXME: consider highlighting parameters of some other overloaded
 812     // operators as well
 813     llvm::ArrayRef<const Expr *> Args = {E->getArgs(), E->getNumArgs()};
 814     if (auto *CallOp = dyn_cast<CXXOperatorCallExpr>(E)) {
 815       switch (CallOp->getOperator()) {
 816       case OO_Call:
 817       case OO_Subscript:
 818         Args = Args.drop_front(); // Drop object parameter
 819         break;
 820       default:
 821         return true;
 822       }
 823     }
 824
 825     highlightMutableReferenceArguments(
 826         dyn_cast_or_null<FunctionDecl>(E->getCalleeDecl()), Args);
 827
 828     return true;
 829   }
 830
 831   void highlightMutableReferenceArgument(QualType T, const Expr *Arg) {
 832     if (!Arg)
 833       return;
 834
 835     // Is this parameter passed by non-const pointer or reference?
 836     // FIXME The condition T->idDependentType() could be relaxed a bit,
 837     // e.g. std::vector<T>& is dependent but we would want to highlight it
 838     bool IsRef = T->isLValueReferenceType();
 839     bool IsPtr = T->isPointerType();
 840     if ((!IsRef && !IsPtr) || T->getPointeeType().isConstQualified() ||
 841         T->isDependentType()) {
 842       return;
 843     }
 844
 845     std::optional<SourceLocation> Location;
 846
 847     // FIXME Add "unwrapping" for ArraySubscriptExpr,
 848     //  e.g. highlight `a` in `a[i]`
 849     // FIXME Handle dependent expression types
 850     if (auto *IC = dyn_cast<ImplicitCastExpr>(Arg))
 851       Arg = IC->getSubExprAsWritten();
 852     if (auto *UO = dyn_cast<UnaryOperator>(Arg)) {
 853       if (UO->getOpcode() == UO_AddrOf)
 854         Arg = UO->getSubExpr();
 855     }
 856     if (auto *DR = dyn_cast<DeclRefExpr>(Arg))
 857       Location = DR->getLocation();
 858     else if (auto *M = dyn_cast<MemberExpr>(Arg))
 859       Location = M->getMemberLoc();
 860
 861     if (Location)
 862       H.addExtraModifier(*Location,
 863                          IsRef ? HighlightingModifier::UsedAsMutableReference
 864                                : HighlightingModifier::UsedAsMutablePointer);
 865   }
 866
 867   void
 868   highlightMutableReferenceArguments(const FunctionDecl *FD,
 869                                      llvm::ArrayRef<const Expr *const> Args) {
 870     if (!FD)
 871       return;
 872
 873     if (auto *ProtoType = FD->getType()->getAs<FunctionProtoType>()) {
 874       // Iterate over the types of the function parameters.
 875       // If any of them are non-const reference paramteres, add it as a
 876       // highlighting modifier to the corresponding expression
 877       for (size_t I = 0;
 878            I < std::min(size_t(ProtoType->getNumParams()), Args.size()); ++I) {
 879         highlightMutableReferenceArgument(ProtoType->getParamType(I), Args[I]);
 880       }
 881     }
 882   }
 883
 884   bool VisitDecltypeTypeLoc(DecltypeTypeLoc L) {
 885     if (auto K = kindForType(L.getTypePtr(), H.getResolver())) {
 886       auto &Tok = H.addToken(L.getBeginLoc(), *K)
 887                       .addModifier(HighlightingModifier::Deduced);
 888       if (auto Mod = scopeModifier(L.getTypePtr()))
 889         Tok.addModifier(*Mod);
 890       if (isDefaultLibrary(L.getTypePtr()))
 891         Tok.addModifier(HighlightingModifier::DefaultLibrary);
 892     }
 893     return true;
 894   }
 895
 896   bool VisitCXXDestructorDecl(CXXDestructorDecl *D) {
 897     if (auto *TI = D->getNameInfo().getNamedTypeInfo()) {
 898       SourceLocation Loc = TI->getTypeLoc().getBeginLoc();
 899       H.addExtraModifier(Loc, HighlightingModifier::ConstructorOrDestructor);
 900       H.addExtraModifier(Loc, HighlightingModifier::Declaration);
 901       if (D->isThisDeclarationADefinition())
 902         H.addExtraModifier(Loc, HighlightingModifier::Definition);
 903     }
 904     return true;
 905   }
 906
 907   bool VisitCXXMemberCallExpr(CXXMemberCallExpr *CE) {
 908     // getMethodDecl can return nullptr with member pointers, e.g.
 909     // `(foo.*pointer_to_member_fun)(arg);`
 910     if (auto *D = CE->getMethodDecl()) {
 911       if (isa<CXXDestructorDecl>(D)) {
 912         if (auto *ME = dyn_cast<MemberExpr>(CE->getCallee())) {
 913           if (auto *TI = ME->getMemberNameInfo().getNamedTypeInfo()) {
 914             H.addExtraModifier(TI->getTypeLoc().getBeginLoc(),
 915                                HighlightingModifier::ConstructorOrDestructor);
 916           }
 917         }
 918       } else if (D->isOverloadedOperator()) {
 919         if (auto *ME = dyn_cast<MemberExpr>(CE->getCallee()))
 920           H.addToken(
 921                ME->getMemberNameInfo().getCXXOperatorNameRange().getBegin(),
 922                HighlightingKind::Operator)
 923               .addModifier(HighlightingModifier::UserDefined);
 924       }
 925     }
 926     return true;
 927   }
 928
 929   bool VisitDeclaratorDecl(DeclaratorDecl *D) {
 930     for (unsigned i = 0; i < D->getNumTemplateParameterLists(); ++i) {
 931       if (auto *TPL = D->getTemplateParameterList(i))
 932         H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 933     }
 934     auto *AT = D->getType()->getContainedAutoType();
 935     if (!AT)
 936       return true;
 937     auto K =
 938         kindForType(AT->getDeducedType().getTypePtrOrNull(), H.getResolver());
 939     if (!K)
 940       return true;
 941     auto *TSI = D->getTypeSourceInfo();
 942     if (!TSI)
 943       return true;
 944     SourceLocation StartLoc =
 945         TSI->getTypeLoc().getContainedAutoTypeLoc().getNameLoc();
 946     // The AutoType may not have a corresponding token, e.g. in the case of
 947     // init-captures. In this case, StartLoc overlaps with the location
 948     // of the decl itself, and producing a token for the type here would result
 949     // in both it and the token for the decl being dropped due to conflict.
 950     if (StartLoc == D->getLocation())
 951       return true;
 952
 953     auto &Tok =
 954         H.addToken(StartLoc, *K).addModifier(HighlightingModifier::Deduced);
 955     const Type *Deduced = AT->getDeducedType().getTypePtrOrNull();
 956     if (auto Mod = scopeModifier(Deduced))
 957       Tok.addModifier(*Mod);
 958     if (isDefaultLibrary(Deduced))
 959       Tok.addModifier(HighlightingModifier::DefaultLibrary);
 960     return true;
 961   }
 962
 963   // We handle objective-C selectors specially, because one reference can
 964   // cover several non-contiguous tokens.
 965   void highlightObjCSelector(const ArrayRef<SourceLocation> &Locs, bool Decl,
 966                              bool Def, bool Class, bool DefaultLibrary) {
 967     HighlightingKind Kind =
 968         Class ? HighlightingKind::StaticMethod : HighlightingKind::Method;
 969     for (SourceLocation Part : Locs) {
 970       auto &Tok =
 971           H.addToken(Part, Kind).addModifier(HighlightingModifier::ClassScope);
 972       if (Decl)
 973         Tok.addModifier(HighlightingModifier::Declaration);
 974       if (Def)
 975         Tok.addModifier(HighlightingModifier::Definition);
 976       if (Class)
 977         Tok.addModifier(HighlightingModifier::Static);
 978       if (DefaultLibrary)
 979         Tok.addModifier(HighlightingModifier::DefaultLibrary);
 980     }
 981   }
 982
 983   bool VisitObjCMethodDecl(ObjCMethodDecl *OMD) {
 984     llvm::SmallVector<SourceLocation> Locs;
 985     OMD->getSelectorLocs(Locs);
 986     highlightObjCSelector(Locs, /*Decl=*/true,
 987                           OMD->isThisDeclarationADefinition(),
 988                           OMD->isClassMethod(), isDefaultLibrary(OMD));
 989     return true;
 990   }
 991
 992   bool VisitObjCMessageExpr(ObjCMessageExpr *OME) {
 993     llvm::SmallVector<SourceLocation> Locs;
 994     OME->getSelectorLocs(Locs);
 995     bool DefaultLibrary = false;
 996     if (ObjCMethodDecl *OMD = OME->getMethodDecl())
 997       DefaultLibrary = isDefaultLibrary(OMD);
 998     highlightObjCSelector(Locs, /*Decl=*/false, /*Def=*/false,
 999                           OME->isClassMessage(), DefaultLibrary);
1000     return true;
1001   }
1002
1003   // Objective-C allows you to use property syntax `self.prop` as sugar for
1004   // `[self prop]` and `[self setProp:]` when there's no explicit `@property`
1005   // for `prop` as well as for class properties. We treat this like a property
1006   // even though semantically it's equivalent to a method expression.
1007   void highlightObjCImplicitPropertyRef(const ObjCMethodDecl *OMD,
1008                                         SourceLocation Loc) {
1009     auto &Tok = H.addToken(Loc, HighlightingKind::Field)
1010                     .addModifier(HighlightingModifier::ClassScope);
1011     if (OMD->isClassMethod())
1012       Tok.addModifier(HighlightingModifier::Static);
1013     if (isDefaultLibrary(OMD))
1014       Tok.addModifier(HighlightingModifier::DefaultLibrary);
1015   }
1016
1017   bool VisitObjCPropertyRefExpr(ObjCPropertyRefExpr *OPRE) {
1018     // We need to handle implicit properties here since they will appear to
1019     // reference `ObjCMethodDecl` via an implicit `ObjCMessageExpr`, so normal
1020     // highlighting will not work.
1021     if (!OPRE->isImplicitProperty())
1022       return true;
1023     // A single property expr can reference both a getter and setter, but we can
1024     // only provide a single semantic token, so prefer the getter. In most cases
1025     // the end result should be the same, although it's technically possible
1026     // that the user defines a setter for a system SDK.
1027     if (OPRE->isMessagingGetter()) {
1028       highlightObjCImplicitPropertyRef(OPRE->getImplicitPropertyGetter(),
1029                                        OPRE->getLocation());
1030       return true;
1031     }
1032     if (OPRE->isMessagingSetter()) {
1033       highlightObjCImplicitPropertyRef(OPRE->getImplicitPropertySetter(),
1034                                        OPRE->getLocation());
1035     }
1036     return true;
1037   }
1038
1039   bool VisitOverloadExpr(OverloadExpr *E) {
1040     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1041     if (!E->decls().empty())
1042       return true; // handled by findExplicitReferences.
1043     auto &Tok = H.addToken(E->getNameLoc(), HighlightingKind::Unknown)
1044                     .addModifier(HighlightingModifier::DependentName);
1045     if (llvm::isa<UnresolvedMemberExpr>(E))
1046       Tok.addModifier(HighlightingModifier::ClassScope);
1047     // other case is UnresolvedLookupExpr, scope is unknown.
1048     return true;
1049   }
1050
1051   bool VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
1052     H.addToken(E->getMemberNameInfo().getLoc(), HighlightingKind::Unknown)
1053         .addModifier(HighlightingModifier::DependentName)
1054         .addModifier(HighlightingModifier::ClassScope);
1055     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1056     return true;
1057   }
1058
1059   bool VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *E) {
1060     H.addToken(E->getNameInfo().getLoc(), HighlightingKind::Unknown)
1061         .addModifier(HighlightingModifier::DependentName)
1062         .addModifier(HighlightingModifier::ClassScope);
1063     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1064     return true;
1065   }
1066
1067   bool VisitAttr(Attr *A) {
1068     switch (A->getKind()) {
1069     case attr::Override:
1070     case attr::Final:
1071       H.addToken(A->getLocation(), HighlightingKind::Modifier);
1072       break;
1073     default:
1074       break;
1075     }
1076     return true;
1077   }
1078
1079   bool VisitDependentNameTypeLoc(DependentNameTypeLoc L) {
1080     H.addToken(L.getNameLoc(), HighlightingKind::Type)
1081         .addModifier(HighlightingModifier::DependentName)
1082         .addModifier(HighlightingModifier::ClassScope);
1083     return true;
1084   }
1085
1086   bool VisitDependentTemplateSpecializationTypeLoc(
1087       DependentTemplateSpecializationTypeLoc L) {
1088     H.addToken(L.getTemplateNameLoc(), HighlightingKind::Type)
1089         .addModifier(HighlightingModifier::DependentName)
1090         .addModifier(HighlightingModifier::ClassScope);
1091     H.addAngleBracketTokens(L.getLAngleLoc(), L.getRAngleLoc());
1092     return true;
1093   }
1094
1095   bool TraverseTemplateArgumentLoc(TemplateArgumentLoc L) {
1096     // Handle template template arguments only (other arguments are handled by
1097     // their Expr, TypeLoc etc values).
1098     if (L.getArgument().getKind() != TemplateArgument::Template &&
1099         L.getArgument().getKind() != TemplateArgument::TemplateExpansion)
1100       return RecursiveASTVisitor::TraverseTemplateArgumentLoc(L);
1101
1102     TemplateName N = L.getArgument().getAsTemplateOrTemplatePattern();
1103     switch (N.getKind()) {
1104     case TemplateName::OverloadedTemplate:
1105       // Template template params must always be class templates.
1106       // Don't bother to try to work out the scope here.
1107       H.addToken(L.getTemplateNameLoc(), HighlightingKind::Class);
1108       break;
1109     case TemplateName::DependentTemplate:
1110     case TemplateName::AssumedTemplate:
1111       H.addToken(L.getTemplateNameLoc(), HighlightingKind::Class)
1112           .addModifier(HighlightingModifier::DependentName);
1113       break;
1114     case TemplateName::Template:
1115     case TemplateName::QualifiedTemplate:
1116     case TemplateName::SubstTemplateTemplateParm:
1117     case TemplateName::SubstTemplateTemplateParmPack:
1118     case TemplateName::UsingTemplate:
1119       // Names that could be resolved to a TemplateDecl are handled elsewhere.
1120       break;
1121     }
1122     return RecursiveASTVisitor::TraverseTemplateArgumentLoc(L);
1123   }
1124
1125   // findExplicitReferences will walk nested-name-specifiers and
1126   // find anything that can be resolved to a Decl. However, non-leaf
1127   // components of nested-name-specifiers which are dependent names
1128   // (kind "Identifier") cannot be resolved to a decl, so we visit
1129   // them here.
1130   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc Q) {
1131     if (NestedNameSpecifier *NNS = Q.getNestedNameSpecifier()) {
1132       if (NNS->getKind() == NestedNameSpecifier::Identifier)
1133         H.addToken(Q.getLocalBeginLoc(), HighlightingKind::Type)
1134             .addModifier(HighlightingModifier::DependentName)
1135             .addModifier(HighlightingModifier::ClassScope);
1136     }
1137     return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(Q);
1138   }
1139
1140 private:
1141   HighlightingsBuilder &H;
1142 };
1143 } // namespace
1144
1145 std::vector<HighlightingToken>
1146 getSemanticHighlightings(ParsedAST &AST, bool IncludeInactiveRegionTokens) {
1147   auto &C = AST.getASTContext();
1148   HighlightingFilter Filter = HighlightingFilter::fromCurrentConfig();
1149   if (!IncludeInactiveRegionTokens)
1150     Filter.disableKind(HighlightingKind::InactiveCode);
1151   // Add highlightings for AST nodes.
1152   HighlightingsBuilder Builder(AST, Filter);
1153   // Highlight 'decltype' and 'auto' as their underlying types.
1154   CollectExtraHighlightings(Builder).TraverseAST(C);
1155   // Highlight all decls and references coming from the AST.
1156   findExplicitReferences(
1157       C,
1158       [&](ReferenceLoc R) {
1159         for (const NamedDecl *Decl : R.Targets) {
1160           if (!canHighlightName(Decl->getDeclName()))
1161             continue;
1162           auto Kind = kindForDecl(Decl, AST.getHeuristicResolver());
1163           if (!Kind)
1164             continue;
1165           auto &Tok = Builder.addToken(R.NameLoc, *Kind);
1166
1167           // The attribute tests don't want to look at the template.
1168           if (auto *TD = dyn_cast<TemplateDecl>(Decl)) {
1169             if (auto *Templated = TD->getTemplatedDecl())
1170               Decl = Templated;
1171           }
1172           if (auto Mod = scopeModifier(Decl))
1173             Tok.addModifier(*Mod);
1174           if (isConst(Decl))
1175             Tok.addModifier(HighlightingModifier::Readonly);
1176           if (isStatic(Decl))
1177             Tok.addModifier(HighlightingModifier::Static);
1178           if (isAbstract(Decl))
1179             Tok.addModifier(HighlightingModifier::Abstract);
1180           if (isVirtual(Decl))
1181             Tok.addModifier(HighlightingModifier::Virtual);
1182           if (isDependent(Decl))
1183             Tok.addModifier(HighlightingModifier::DependentName);
1184           if (isDefaultLibrary(Decl))
1185             Tok.addModifier(HighlightingModifier::DefaultLibrary);
1186           if (Decl->isDeprecated())
1187             Tok.addModifier(HighlightingModifier::Deprecated);
1188           if (isa<CXXConstructorDecl>(Decl))
1189             Tok.addModifier(HighlightingModifier::ConstructorOrDestructor);
1190           if (R.IsDecl) {
1191             // Do not treat an UnresolvedUsingValueDecl as a declaration.
1192             // It's more common to think of it as a reference to the
1193             // underlying declaration.
1194             if (!isa<UnresolvedUsingValueDecl>(Decl))
1195               Tok.addModifier(HighlightingModifier::Declaration);
1196             if (isUniqueDefinition(Decl))
1197               Tok.addModifier(HighlightingModifier::Definition);
1198           }
1199         }
1200       },
1201       AST.getHeuristicResolver());
1202   // Add highlightings for macro references.
1203   auto AddMacro = [&](const MacroOccurrence &M) {
1204     auto &T = Builder.addToken(M.toRange(C.getSourceManager()),
1205                                HighlightingKind::Macro);
1206     T.addModifier(HighlightingModifier::GlobalScope);
1207     if (M.IsDefinition)
1208       T.addModifier(HighlightingModifier::Declaration);
1209   };
1210   for (const auto &SIDToRefs : AST.getMacros().MacroRefs)
1211     for (const auto &M : SIDToRefs.second)
1212       AddMacro(M);
1213   for (const auto &M : AST.getMacros().UnknownMacros)
1214     AddMacro(M);
1215
1216   return std::move(Builder).collect(AST);
1217 }
1218
1219 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K) {
1220   switch (K) {
1221   case HighlightingKind::Variable:
1222     return OS << "Variable";
1223   case HighlightingKind::LocalVariable:
1224     return OS << "LocalVariable";
1225   case HighlightingKind::Parameter:
1226     return OS << "Parameter";
1227   case HighlightingKind::Function:
1228     return OS << "Function";
1229   case HighlightingKind::Method:
1230     return OS << "Method";
1231   case HighlightingKind::StaticMethod:
1232     return OS << "StaticMethod";
1233   case HighlightingKind::Field:
1234     return OS << "Field";
1235   case HighlightingKind::StaticField:
1236     return OS << "StaticField";
1237   case HighlightingKind::Class:
1238     return OS << "Class";
1239   case HighlightingKind::Interface:
1240     return OS << "Interface";
1241   case HighlightingKind::Enum:
1242     return OS << "Enum";
1243   case HighlightingKind::EnumConstant:
1244     return OS << "EnumConstant";
1245   case HighlightingKind::Typedef:
1246     return OS << "Typedef";
1247   case HighlightingKind::Type:
1248     return OS << "Type";
1249   case HighlightingKind::Unknown:
1250     return OS << "Unknown";
1251   case HighlightingKind::Namespace:
1252     return OS << "Namespace";
1253   case HighlightingKind::TemplateParameter:
1254     return OS << "TemplateParameter";
1255   case HighlightingKind::Concept:
1256     return OS << "Concept";
1257   case HighlightingKind::Primitive:
1258     return OS << "Primitive";
1259   case HighlightingKind::Macro:
1260     return OS << "Macro";
1261   case HighlightingKind::Modifier:
1262     return OS << "Modifier";
1263   case HighlightingKind::Operator:
1264     return OS << "Operator";
1265   case HighlightingKind::Bracket:
1266     return OS << "Bracket";
1267   case HighlightingKind::Label:
1268     return OS << "Label";
1269   case HighlightingKind::InactiveCode:
1270     return OS << "InactiveCode";
1271   }
1272   llvm_unreachable("invalid HighlightingKind");
1273 }
1274 std::optional<HighlightingKind>
1275 highlightingKindFromString(llvm::StringRef Name) {
1276   static llvm::StringMap<HighlightingKind> Lookup = {
1277       {"Variable", HighlightingKind::Variable},
1278       {"LocalVariable", HighlightingKind::LocalVariable},
1279       {"Parameter", HighlightingKind::Parameter},
1280       {"Function", HighlightingKind::Function},
1281       {"Method", HighlightingKind::Method},
1282       {"StaticMethod", HighlightingKind::StaticMethod},
1283       {"Field", HighlightingKind::Field},
1284       {"StaticField", HighlightingKind::StaticField},
1285       {"Class", HighlightingKind::Class},
1286       {"Interface", HighlightingKind::Interface},
1287       {"Enum", HighlightingKind::Enum},
1288       {"EnumConstant", HighlightingKind::EnumConstant},
1289       {"Typedef", HighlightingKind::Typedef},
1290       {"Type", HighlightingKind::Type},
1291       {"Unknown", HighlightingKind::Unknown},
1292       {"Namespace", HighlightingKind::Namespace},
1293       {"TemplateParameter", HighlightingKind::TemplateParameter},
1294       {"Concept", HighlightingKind::Concept},
1295       {"Primitive", HighlightingKind::Primitive},
1296       {"Macro", HighlightingKind::Macro},
1297       {"Modifier", HighlightingKind::Modifier},
1298       {"Operator", HighlightingKind::Operator},
1299       {"Bracket", HighlightingKind::Bracket},
1300       {"InactiveCode", HighlightingKind::InactiveCode},
1301   };
1302
1303   auto It = Lookup.find(Name);
1304   return It != Lookup.end() ? std::make_optional(It->getValue()) : std::nullopt;
1305 }
1306 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingModifier K) {
1307   switch (K) {
1308   case HighlightingModifier::Declaration:
1309     return OS << "decl"; // abbreviation for common case
1310   case HighlightingModifier::Definition:
1311     return OS << "def"; // abbrevation for common case
1312   case HighlightingModifier::ConstructorOrDestructor:
1313     return OS << "constrDestr";
1314   default:
1315     return OS << toSemanticTokenModifier(K);
1316   }
1317 }
1318 std::optional<HighlightingModifier>
1319 highlightingModifierFromString(llvm::StringRef Name) {
1320   static llvm::StringMap<HighlightingModifier> Lookup = {
1321       {"Declaration", HighlightingModifier::Declaration},
1322       {"Definition", HighlightingModifier::Definition},
1323       {"Deprecated", HighlightingModifier::Deprecated},
1324       {"Deduced", HighlightingModifier::Deduced},
1325       {"Readonly", HighlightingModifier::Readonly},
1326       {"Static", HighlightingModifier::Static},
1327       {"Abstract", HighlightingModifier::Abstract},
1328       {"Virtual", HighlightingModifier::Virtual},
1329       {"DependentName", HighlightingModifier::DependentName},
1330       {"DefaultLibrary", HighlightingModifier::DefaultLibrary},
1331       {"UsedAsMutableReference", HighlightingModifier::UsedAsMutableReference},
1332       {"UsedAsMutablePointer", HighlightingModifier::UsedAsMutablePointer},
1333       {"ConstructorOrDestructor",
1334        HighlightingModifier::ConstructorOrDestructor},
1335       {"UserDefined", HighlightingModifier::UserDefined},
1336       {"FunctionScope", HighlightingModifier::FunctionScope},
1337       {"ClassScope", HighlightingModifier::ClassScope},
1338       {"FileScope", HighlightingModifier::FileScope},
1339       {"GlobalScope", HighlightingModifier::GlobalScope},
1340   };
1341
1342   auto It = Lookup.find(Name);
1343   return It != Lookup.end() ? std::make_optional(It->getValue()) : std::nullopt;
1344 }
1345
1346 bool operator==(const HighlightingToken &L, const HighlightingToken &R) {
1347   return std::tie(L.R, L.Kind, L.Modifiers) ==
1348          std::tie(R.R, R.Kind, R.Modifiers);
1349 }
1350 bool operator<(const HighlightingToken &L, const HighlightingToken &R) {
1351   return std::tie(L.R, L.Kind, L.Modifiers) <
1352          std::tie(R.R, R.Kind, R.Modifiers);
1353 }
1354
1355 std::vector<SemanticToken>
1356 toSemanticTokens(llvm::ArrayRef<HighlightingToken> Tokens,
1357                  llvm::StringRef Code) {
1358   assert(llvm::is_sorted(Tokens));
1359   std::vector<SemanticToken> Result;
1360   // In case we split a HighlightingToken into multiple tokens (e.g. because it
1361   // was spanning multiple lines), this tracks the last one. This prevents
1362   // having a copy all the time.
1363   HighlightingToken Scratch;
1364   const HighlightingToken *Last = nullptr;
1365   for (const HighlightingToken &Tok : Tokens) {
1366     Result.emplace_back();
1367     SemanticToken *Out = &Result.back();
1368     // deltaStart/deltaLine are relative if possible.
1369     if (Last) {
1370       assert(Tok.R.start.line >= Last->R.end.line);
1371       Out->deltaLine = Tok.R.start.line - Last->R.end.line;
1372       if (Out->deltaLine == 0) {
1373         assert(Tok.R.start.character >= Last->R.start.character);
1374         Out->deltaStart = Tok.R.start.character - Last->R.start.character;
1375       } else {
1376         Out->deltaStart = Tok.R.start.character;
1377       }
1378     } else {
1379       Out->deltaLine = Tok.R.start.line;
1380       Out->deltaStart = Tok.R.start.character;
1381     }
1382     Out->tokenType = static_cast<unsigned>(Tok.Kind);
1383     Out->tokenModifiers = Tok.Modifiers;
1384     Last = &Tok;
1385
1386     if (Tok.R.end.line == Tok.R.start.line) {
1387       Out->length = Tok.R.end.character - Tok.R.start.character;
1388     } else {
1389       // If the token spans a line break, split it into multiple pieces for each
1390       // line.
1391       // This is slow, but multiline tokens are rare.
1392       // FIXME: There's a client capability for supporting multiline tokens,
1393       // respect that.
1394       auto TokStartOffset = llvm::cantFail(positionToOffset(Code, Tok.R.start));
1395       // Note that the loop doesn't cover the last line, which has a special
1396       // length.
1397       for (int I = Tok.R.start.line; I < Tok.R.end.line; ++I) {
1398         auto LineEnd = Code.find('\n', TokStartOffset);
1399         assert(LineEnd != Code.npos);
1400         Out->length = LineEnd - TokStartOffset;
1401         // Token continues on next line, right after the line break.
1402         TokStartOffset = LineEnd + 1;
1403         Result.emplace_back();
1404         Out = &Result.back();
1405         *Out = Result[Result.size() - 2];
1406         // New token starts at the first column of the next line.
1407         Out->deltaLine = 1;
1408         Out->deltaStart = 0;
1409       }
1410       // This is the token on last line.
1411       Out->length = Tok.R.end.character;
1412       // Update the start location for last token, as that's used in the
1413       // relative delta calculation for following tokens.
1414       Scratch = *Last;
1415       Scratch.R.start.line = Tok.R.end.line;
1416       Scratch.R.start.character = 0;
1417       Last = &Scratch;
1418     }
1419   }
1420   return Result;
1421 }
1422 llvm::StringRef toSemanticTokenType(HighlightingKind Kind) {
1423   switch (Kind) {
1424   case HighlightingKind::Variable:
1425   case HighlightingKind::LocalVariable:
1426   case HighlightingKind::StaticField:
1427     return "variable";
1428   case HighlightingKind::Parameter:
1429     return "parameter";
1430   case HighlightingKind::Function:
1431     return "function";
1432   case HighlightingKind::Method:
1433     return "method";
1434   case HighlightingKind::StaticMethod:
1435     // FIXME: better method with static modifier?
1436     return "function";
1437   case HighlightingKind::Field:
1438     return "property";
1439   case HighlightingKind::Class:
1440     return "class";
1441   case HighlightingKind::Interface:
1442     return "interface";
1443   case HighlightingKind::Enum:
1444     return "enum";
1445   case HighlightingKind::EnumConstant:
1446     return "enumMember";
1447   case HighlightingKind::Typedef:
1448   case HighlightingKind::Type:
1449     return "type";
1450   case HighlightingKind::Unknown:
1451     return "unknown"; // nonstandard
1452   case HighlightingKind::Namespace:
1453     return "namespace";
1454   case HighlightingKind::TemplateParameter:
1455     return "typeParameter";
1456   case HighlightingKind::Concept:
1457     return "concept"; // nonstandard
1458   case HighlightingKind::Primitive:
1459     return "type";
1460   case HighlightingKind::Macro:
1461     return "macro";
1462   case HighlightingKind::Modifier:
1463     return "modifier";
1464   case HighlightingKind::Operator:
1465     return "operator";
1466   case HighlightingKind::Bracket:
1467     return "bracket";
1468   case HighlightingKind::Label:
1469     return "label";
1470   case HighlightingKind::InactiveCode:
1471     return "comment";
1472   }
1473   llvm_unreachable("unhandled HighlightingKind");
1474 }
1475
1476 llvm::StringRef toSemanticTokenModifier(HighlightingModifier Modifier) {
1477   switch (Modifier) {
1478   case HighlightingModifier::Declaration:
1479     return "declaration";
1480   case HighlightingModifier::Definition:
1481     return "definition";
1482   case HighlightingModifier::Deprecated:
1483     return "deprecated";
1484   case HighlightingModifier::Readonly:
1485     return "readonly";
1486   case HighlightingModifier::Static:
1487     return "static";
1488   case HighlightingModifier::Deduced:
1489     return "deduced"; // nonstandard
1490   case HighlightingModifier::Abstract:
1491     return "abstract";
1492   case HighlightingModifier::Virtual:
1493     return "virtual";
1494   case HighlightingModifier::DependentName:
1495     return "dependentName"; // nonstandard
1496   case HighlightingModifier::DefaultLibrary:
1497     return "defaultLibrary";
1498   case HighlightingModifier::UsedAsMutableReference:
1499     return "usedAsMutableReference"; // nonstandard
1500   case HighlightingModifier::UsedAsMutablePointer:
1501     return "usedAsMutablePointer"; // nonstandard
1502   case HighlightingModifier::ConstructorOrDestructor:
1503     return "constructorOrDestructor"; // nonstandard
1504   case HighlightingModifier::UserDefined:
1505     return "userDefined"; // nonstandard
1506   case HighlightingModifier::FunctionScope:
1507     return "functionScope"; // nonstandard
1508   case HighlightingModifier::ClassScope:
1509     return "classScope"; // nonstandard
1510   case HighlightingModifier::FileScope:
1511     return "fileScope"; // nonstandard
1512   case HighlightingModifier::GlobalScope:
1513     return "globalScope"; // nonstandard
1514   }
1515   llvm_unreachable("unhandled HighlightingModifier");
1516 }
1517
1518 std::vector<SemanticTokensEdit>
1519 diffTokens(llvm::ArrayRef<SemanticToken> Old,
1520            llvm::ArrayRef<SemanticToken> New) {
1521   // For now, just replace everything from the first-last modification.
1522   // FIXME: use a real diff instead, this is bad with include-insertion.
1523
1524   unsigned Offset = 0;
1525   while (!Old.empty() && !New.empty() && Old.front() == New.front()) {
1526     ++Offset;
1527     Old = Old.drop_front();
1528     New = New.drop_front();
1529   }
1530   while (!Old.empty() && !New.empty() && Old.back() == New.back()) {
1531     Old = Old.drop_back();
1532     New = New.drop_back();
1533   }
1534
1535   if (Old.empty() && New.empty())
1536     return {};
1537   SemanticTokensEdit Edit;
1538   Edit.startToken = Offset;
1539   Edit.deleteTokens = Old.size();
1540   Edit.tokens = New;
1541   return {std::move(Edit)};
1542 }
1543
1544 std::vector<Range> getInactiveRegions(ParsedAST &AST) {
1545   std::vector<Range> SkippedRanges(std::move(AST.getMacros().SkippedRanges));
1546   const auto &SM = AST.getSourceManager();
1547   StringRef MainCode = SM.getBufferOrFake(SM.getMainFileID()).getBuffer();
1548   std::vector<Range> InactiveRegions;
1549   for (const Range &Skipped : SkippedRanges) {
1550     Range Inactive = Skipped;
1551     // Sometimes, SkippedRanges contains a range ending at position 0
1552     // of a line. Clients that apply whole-line styles will treat that
1553     // line as inactive which is not desirable, so adjust the ending
1554     // position to be the end of the previous line.
1555     if (Inactive.end.character == 0 && Inactive.end.line > 0) {
1556       --Inactive.end.line;
1557     }
1558     // Exclude the directive lines themselves from the range.
1559     if (Inactive.end.line >= Inactive.start.line + 2) {
1560       ++Inactive.start.line;
1561       --Inactive.end.line;
1562     } else {
1563       // range would be empty, e.g. #endif on next line after #ifdef
1564       continue;
1565     }
1566     // Since we've adjusted the ending line, we need to recompute the
1567     // column to reflect the end of that line.
1568     if (auto EndOfLine = endOfLine(MainCode, Inactive.end.line)) {
1569       Inactive.end = *EndOfLine;
1570     } else {
1571       elog("Failed to determine end of line: {0}", EndOfLine.takeError());
1572       continue;
1573     }
1574     InactiveRegions.push_back(Inactive);
1575   }
1576   return InactiveRegions;
1577 }
1578
1579 } // namespace clangd
1580 } // namespace clang