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, IndirectFieldDecl, 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->isPureVirtual();
 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         Resolver(AST.getHeuristicResolver()) {}
 423
 424   HighlightingToken &addToken(SourceLocation Loc, HighlightingKind Kind) {
 425     auto Range = getRangeForSourceLocation(Loc);
 426     if (!Range)
 427       return InvalidHighlightingToken;
 428
 429     return addToken(*Range, Kind);
 430   }
 431
 432   // Most of this function works around
 433   // https://github.com/clangd/clangd/issues/871.
 434   void addAngleBracketTokens(SourceLocation LLoc, SourceLocation RLoc) {
 435     if (!LLoc.isValid() || !RLoc.isValid())
 436       return;
 437
 438     auto LRange = getRangeForSourceLocation(LLoc);
 439     if (!LRange)
 440       return;
 441
 442     // RLoc might be pointing at a virtual buffer when it's part of a `>>`
 443     // token.
 444     RLoc = SourceMgr.getFileLoc(RLoc);
 445     // Make sure token is part of the main file.
 446     RLoc = getHighlightableSpellingToken(RLoc, SourceMgr);
 447     if (!RLoc.isValid())
 448       return;
 449
 450     const auto *RTok = TB.spelledTokenContaining(RLoc);
 451     // Handle `>>`. RLoc is either part of `>>` or a spelled token on its own
 452     // `>`. If it's the former, slice to have length of 1, if latter use the
 453     // token as-is.
 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.spelledTokenContaining(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;
 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 (llvm::to_underlying(D->getLinkageInternal()) <
 621       llvm::to_underlying(Linkage::External))
 622     return HighlightingModifier::FileScope;
 623   return HighlightingModifier::GlobalScope;
 624 }
 625
 626 std::optional<HighlightingModifier> scopeModifier(const Type *T) {
 627   if (!T)
 628     return std::nullopt;
 629   if (T->isBuiltinType())
 630     return HighlightingModifier::GlobalScope;
 631   if (auto *TD = dyn_cast<TemplateTypeParmType>(T))
 632     return scopeModifier(TD->getDecl());
 633   if (auto *TD = T->getAsTagDecl())
 634     return scopeModifier(TD);
 635   return std::nullopt;
 636 }
 637
 638 /// Produces highlightings, which are not captured by findExplicitReferences,
 639 /// e.g. highlights dependent names and 'auto' as the underlying type.
 640 class CollectExtraHighlightings
 641     : public RecursiveASTVisitor<CollectExtraHighlightings> {
 642   using Base = RecursiveASTVisitor<CollectExtraHighlightings>;
 643
 644 public:
 645   CollectExtraHighlightings(HighlightingsBuilder &H) : H(H) {}
 646
 647   bool VisitCXXConstructExpr(CXXConstructExpr *E) {
 648     highlightMutableReferenceArguments(E->getConstructor(),
 649                                        {E->getArgs(), E->getNumArgs()});
 650
 651     return true;
 652   }
 653
 654   bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
 655     if (Init->isMemberInitializer())
 656       if (auto *Member = Init->getMember())
 657         highlightMutableReferenceArgument(Member->getType(), Init->getInit());
 658     return Base::TraverseConstructorInitializer(Init);
 659   }
 660
 661   bool TraverseTypeConstraint(const TypeConstraint *C) {
 662     if (auto *Args = C->getTemplateArgsAsWritten())
 663       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 664     return Base::TraverseTypeConstraint(C);
 665   }
 666
 667   bool VisitPredefinedExpr(PredefinedExpr *E) {
 668     H.addToken(E->getLocation(), HighlightingKind::LocalVariable)
 669         .addModifier(HighlightingModifier::Static)
 670         .addModifier(HighlightingModifier::Readonly)
 671         .addModifier(HighlightingModifier::FunctionScope);
 672     return true;
 673   }
 674
 675   bool VisitConceptSpecializationExpr(ConceptSpecializationExpr *E) {
 676     if (auto *Args = E->getTemplateArgsAsWritten())
 677       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 678     return true;
 679   }
 680
 681   bool VisitTemplateDecl(TemplateDecl *D) {
 682     if (auto *TPL = D->getTemplateParameters())
 683       H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 684     return true;
 685   }
 686
 687   bool VisitTagDecl(TagDecl *D) {
 688     for (unsigned i = 0; i < D->getNumTemplateParameterLists(); ++i) {
 689       if (auto *TPL = D->getTemplateParameterList(i))
 690         H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 691     }
 692     return true;
 693   }
 694
 695   bool
 696   VisitClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *D) {
 697     if (auto *Args = D->getTemplateArgsAsWritten())
 698       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 699     return true;
 700   }
 701
 702   bool VisitClassTemplatePartialSpecializationDecl(
 703       ClassTemplatePartialSpecializationDecl *D) {
 704     if (auto *TPL = D->getTemplateParameters())
 705       H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 706     return true;
 707   }
 708
 709   bool VisitVarTemplateSpecializationDecl(VarTemplateSpecializationDecl *D) {
 710     if (auto *Args = D->getTemplateArgsAsWritten())
 711       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 712     return true;
 713   }
 714
 715   bool VisitVarTemplatePartialSpecializationDecl(
 716       VarTemplatePartialSpecializationDecl *D) {
 717     if (auto *TPL = D->getTemplateParameters())
 718       H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 719     return true;
 720   }
 721
 722   bool VisitDeclRefExpr(DeclRefExpr *E) {
 723     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
 724     return true;
 725   }
 726   bool VisitMemberExpr(MemberExpr *E) {
 727     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
 728     return true;
 729   }
 730
 731   bool VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) {
 732     H.addAngleBracketTokens(L.getLAngleLoc(), L.getRAngleLoc());
 733     return true;
 734   }
 735
 736   bool VisitFunctionDecl(FunctionDecl *D) {
 737     if (D->isOverloadedOperator()) {
 738       const auto AddOpDeclToken = [&](SourceLocation Loc) {
 739         auto &Token = H.addToken(Loc, HighlightingKind::Operator)
 740                           .addModifier(HighlightingModifier::Declaration);
 741         if (D->isThisDeclarationADefinition())
 742           Token.addModifier(HighlightingModifier::Definition);
 743       };
 744       const auto Range = D->getNameInfo().getCXXOperatorNameRange();
 745       AddOpDeclToken(Range.getBegin());
 746       const auto Kind = D->getOverloadedOperator();
 747       if (Kind == OO_Call || Kind == OO_Subscript)
 748         AddOpDeclToken(Range.getEnd());
 749     }
 750     if (auto *Args = D->getTemplateSpecializationArgsAsWritten())
 751       H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
 752     return true;
 753   }
 754
 755   bool VisitCXXOperatorCallExpr(CXXOperatorCallExpr *E) {
 756     const auto AddOpToken = [&](SourceLocation Loc) {
 757       H.addToken(Loc, HighlightingKind::Operator)
 758           .addModifier(HighlightingModifier::UserDefined);
 759     };
 760     AddOpToken(E->getOperatorLoc());
 761     const auto Kind = E->getOperator();
 762     if (Kind == OO_Call || Kind == OO_Subscript) {
 763       if (auto *Callee = E->getCallee())
 764         AddOpToken(Callee->getBeginLoc());
 765     }
 766     return true;
 767   }
 768
 769   bool VisitUnaryOperator(UnaryOperator *Op) {
 770     auto &Token = H.addToken(Op->getOperatorLoc(), HighlightingKind::Operator);
 771     if (Op->getSubExpr()->isTypeDependent())
 772       Token.addModifier(HighlightingModifier::UserDefined);
 773     return true;
 774   }
 775
 776   bool VisitBinaryOperator(BinaryOperator *Op) {
 777     auto &Token = H.addToken(Op->getOperatorLoc(), HighlightingKind::Operator);
 778     if (Op->getLHS()->isTypeDependent() || Op->getRHS()->isTypeDependent())
 779       Token.addModifier(HighlightingModifier::UserDefined);
 780     return true;
 781   }
 782
 783   bool VisitConditionalOperator(ConditionalOperator *Op) {
 784     H.addToken(Op->getQuestionLoc(), HighlightingKind::Operator);
 785     H.addToken(Op->getColonLoc(), HighlightingKind::Operator);
 786     return true;
 787   }
 788
 789   bool VisitCXXNewExpr(CXXNewExpr *E) {
 790     auto &Token = H.addToken(E->getBeginLoc(), HighlightingKind::Operator);
 791     if (isa_and_present<CXXMethodDecl>(E->getOperatorNew()))
 792       Token.addModifier(HighlightingModifier::UserDefined);
 793     return true;
 794   }
 795
 796   bool VisitCXXDeleteExpr(CXXDeleteExpr *E) {
 797     auto &Token = H.addToken(E->getBeginLoc(), HighlightingKind::Operator);
 798     if (isa_and_present<CXXMethodDecl>(E->getOperatorDelete()))
 799       Token.addModifier(HighlightingModifier::UserDefined);
 800     return true;
 801   }
 802
 803   bool VisitCXXNamedCastExpr(CXXNamedCastExpr *E) {
 804     const auto &B = E->getAngleBrackets();
 805     H.addAngleBracketTokens(B.getBegin(), B.getEnd());
 806     return true;
 807   }
 808
 809   bool VisitCallExpr(CallExpr *E) {
 810     // Highlighting parameters passed by non-const reference does not really
 811     // make sense for literals...
 812     if (isa<UserDefinedLiteral>(E))
 813       return true;
 814
 815     // FIXME: consider highlighting parameters of some other overloaded
 816     // operators as well
 817     llvm::ArrayRef<const Expr *> Args = {E->getArgs(), E->getNumArgs()};
 818     if (auto *CallOp = dyn_cast<CXXOperatorCallExpr>(E)) {
 819       switch (CallOp->getOperator()) {
 820       case OO_Call:
 821       case OO_Subscript:
 822         Args = Args.drop_front(); // Drop object parameter
 823         break;
 824       default:
 825         return true;
 826       }
 827     }
 828
 829     highlightMutableReferenceArguments(
 830         dyn_cast_or_null<FunctionDecl>(E->getCalleeDecl()), Args);
 831
 832     return true;
 833   }
 834
 835   void highlightMutableReferenceArgument(QualType T, const Expr *Arg) {
 836     if (!Arg)
 837       return;
 838
 839     // Is this parameter passed by non-const pointer or reference?
 840     // FIXME The condition T->idDependentType() could be relaxed a bit,
 841     // e.g. std::vector<T>& is dependent but we would want to highlight it
 842     bool IsRef = T->isLValueReferenceType();
 843     bool IsPtr = T->isPointerType();
 844     if ((!IsRef && !IsPtr) || T->getPointeeType().isConstQualified() ||
 845         T->isDependentType()) {
 846       return;
 847     }
 848
 849     std::optional<SourceLocation> Location;
 850
 851     // FIXME Add "unwrapping" for ArraySubscriptExpr,
 852     //  e.g. highlight `a` in `a[i]`
 853     // FIXME Handle dependent expression types
 854     if (auto *IC = dyn_cast<ImplicitCastExpr>(Arg))
 855       Arg = IC->getSubExprAsWritten();
 856     if (auto *UO = dyn_cast<UnaryOperator>(Arg)) {
 857       if (UO->getOpcode() == UO_AddrOf)
 858         Arg = UO->getSubExpr();
 859     }
 860     if (auto *DR = dyn_cast<DeclRefExpr>(Arg))
 861       Location = DR->getLocation();
 862     else if (auto *M = dyn_cast<MemberExpr>(Arg))
 863       Location = M->getMemberLoc();
 864
 865     if (Location)
 866       H.addExtraModifier(*Location,
 867                          IsRef ? HighlightingModifier::UsedAsMutableReference
 868                                : HighlightingModifier::UsedAsMutablePointer);
 869   }
 870
 871   void
 872   highlightMutableReferenceArguments(const FunctionDecl *FD,
 873                                      llvm::ArrayRef<const Expr *const> Args) {
 874     if (!FD)
 875       return;
 876
 877     if (auto *ProtoType = FD->getType()->getAs<FunctionProtoType>()) {
 878       // Iterate over the types of the function parameters.
 879       // If any of them are non-const reference paramteres, add it as a
 880       // highlighting modifier to the corresponding expression
 881       for (size_t I = 0;
 882            I < std::min(size_t(ProtoType->getNumParams()), Args.size()); ++I) {
 883         highlightMutableReferenceArgument(ProtoType->getParamType(I), Args[I]);
 884       }
 885     }
 886   }
 887
 888   bool VisitDecltypeTypeLoc(DecltypeTypeLoc L) {
 889     if (auto K = kindForType(L.getTypePtr(), H.getResolver())) {
 890       auto &Tok = H.addToken(L.getBeginLoc(), *K)
 891                       .addModifier(HighlightingModifier::Deduced);
 892       if (auto Mod = scopeModifier(L.getTypePtr()))
 893         Tok.addModifier(*Mod);
 894       if (isDefaultLibrary(L.getTypePtr()))
 895         Tok.addModifier(HighlightingModifier::DefaultLibrary);
 896     }
 897     return true;
 898   }
 899
 900   bool VisitCXXDestructorDecl(CXXDestructorDecl *D) {
 901     if (auto *TI = D->getNameInfo().getNamedTypeInfo()) {
 902       SourceLocation Loc = TI->getTypeLoc().getBeginLoc();
 903       H.addExtraModifier(Loc, HighlightingModifier::ConstructorOrDestructor);
 904       H.addExtraModifier(Loc, HighlightingModifier::Declaration);
 905       if (D->isThisDeclarationADefinition())
 906         H.addExtraModifier(Loc, HighlightingModifier::Definition);
 907     }
 908     return true;
 909   }
 910
 911   bool VisitCXXMemberCallExpr(CXXMemberCallExpr *CE) {
 912     // getMethodDecl can return nullptr with member pointers, e.g.
 913     // `(foo.*pointer_to_member_fun)(arg);`
 914     if (auto *D = CE->getMethodDecl()) {
 915       if (isa<CXXDestructorDecl>(D)) {
 916         if (auto *ME = dyn_cast<MemberExpr>(CE->getCallee())) {
 917           if (auto *TI = ME->getMemberNameInfo().getNamedTypeInfo()) {
 918             H.addExtraModifier(TI->getTypeLoc().getBeginLoc(),
 919                                HighlightingModifier::ConstructorOrDestructor);
 920           }
 921         }
 922       } else if (D->isOverloadedOperator()) {
 923         if (auto *ME = dyn_cast<MemberExpr>(CE->getCallee()))
 924           H.addToken(
 925                ME->getMemberNameInfo().getCXXOperatorNameRange().getBegin(),
 926                HighlightingKind::Operator)
 927               .addModifier(HighlightingModifier::UserDefined);
 928       }
 929     }
 930     return true;
 931   }
 932
 933   bool VisitDeclaratorDecl(DeclaratorDecl *D) {
 934     for (unsigned i = 0; i < D->getNumTemplateParameterLists(); ++i) {
 935       if (auto *TPL = D->getTemplateParameterList(i))
 936         H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
 937     }
 938     auto *AT = D->getType()->getContainedAutoType();
 939     if (!AT)
 940       return true;
 941     auto K =
 942         kindForType(AT->getDeducedType().getTypePtrOrNull(), H.getResolver());
 943     if (!K)
 944       return true;
 945     auto *TSI = D->getTypeSourceInfo();
 946     if (!TSI)
 947       return true;
 948     SourceLocation StartLoc =
 949         TSI->getTypeLoc().getContainedAutoTypeLoc().getNameLoc();
 950     // The AutoType may not have a corresponding token, e.g. in the case of
 951     // init-captures. In this case, StartLoc overlaps with the location
 952     // of the decl itself, and producing a token for the type here would result
 953     // in both it and the token for the decl being dropped due to conflict.
 954     if (StartLoc == D->getLocation())
 955       return true;
 956
 957     auto &Tok =
 958         H.addToken(StartLoc, *K).addModifier(HighlightingModifier::Deduced);
 959     const Type *Deduced = AT->getDeducedType().getTypePtrOrNull();
 960     if (auto Mod = scopeModifier(Deduced))
 961       Tok.addModifier(*Mod);
 962     if (isDefaultLibrary(Deduced))
 963       Tok.addModifier(HighlightingModifier::DefaultLibrary);
 964     return true;
 965   }
 966
 967   // We handle objective-C selectors specially, because one reference can
 968   // cover several non-contiguous tokens.
 969   void highlightObjCSelector(const ArrayRef<SourceLocation> &Locs, bool Decl,
 970                              bool Def, bool Class, bool DefaultLibrary) {
 971     HighlightingKind Kind =
 972         Class ? HighlightingKind::StaticMethod : HighlightingKind::Method;
 973     for (SourceLocation Part : Locs) {
 974       auto &Tok =
 975           H.addToken(Part, Kind).addModifier(HighlightingModifier::ClassScope);
 976       if (Decl)
 977         Tok.addModifier(HighlightingModifier::Declaration);
 978       if (Def)
 979         Tok.addModifier(HighlightingModifier::Definition);
 980       if (Class)
 981         Tok.addModifier(HighlightingModifier::Static);
 982       if (DefaultLibrary)
 983         Tok.addModifier(HighlightingModifier::DefaultLibrary);
 984     }
 985   }
 986
 987   bool VisitObjCMethodDecl(ObjCMethodDecl *OMD) {
 988     llvm::SmallVector<SourceLocation> Locs;
 989     OMD->getSelectorLocs(Locs);
 990     highlightObjCSelector(Locs, /*Decl=*/true,
 991                           OMD->isThisDeclarationADefinition(),
 992                           OMD->isClassMethod(), isDefaultLibrary(OMD));
 993     return true;
 994   }
 995
 996   bool VisitObjCMessageExpr(ObjCMessageExpr *OME) {
 997     llvm::SmallVector<SourceLocation> Locs;
 998     OME->getSelectorLocs(Locs);
 999     bool DefaultLibrary = false;
1000     if (ObjCMethodDecl *OMD = OME->getMethodDecl())
1001       DefaultLibrary = isDefaultLibrary(OMD);
1002     highlightObjCSelector(Locs, /*Decl=*/false, /*Def=*/false,
1003                           OME->isClassMessage(), DefaultLibrary);
1004     return true;
1005   }
1006
1007   // Objective-C allows you to use property syntax `self.prop` as sugar for
1008   // `[self prop]` and `[self setProp:]` when there's no explicit `@property`
1009   // for `prop` as well as for class properties. We treat this like a property
1010   // even though semantically it's equivalent to a method expression.
1011   void highlightObjCImplicitPropertyRef(const ObjCMethodDecl *OMD,
1012                                         SourceLocation Loc) {
1013     auto &Tok = H.addToken(Loc, HighlightingKind::Field)
1014                     .addModifier(HighlightingModifier::ClassScope);
1015     if (OMD->isClassMethod())
1016       Tok.addModifier(HighlightingModifier::Static);
1017     if (isDefaultLibrary(OMD))
1018       Tok.addModifier(HighlightingModifier::DefaultLibrary);
1019   }
1020
1021   bool VisitObjCPropertyRefExpr(ObjCPropertyRefExpr *OPRE) {
1022     // We need to handle implicit properties here since they will appear to
1023     // reference `ObjCMethodDecl` via an implicit `ObjCMessageExpr`, so normal
1024     // highlighting will not work.
1025     if (!OPRE->isImplicitProperty())
1026       return true;
1027     // A single property expr can reference both a getter and setter, but we can
1028     // only provide a single semantic token, so prefer the getter. In most cases
1029     // the end result should be the same, although it's technically possible
1030     // that the user defines a setter for a system SDK.
1031     if (OPRE->isMessagingGetter()) {
1032       highlightObjCImplicitPropertyRef(OPRE->getImplicitPropertyGetter(),
1033                                        OPRE->getLocation());
1034       return true;
1035     }
1036     if (OPRE->isMessagingSetter()) {
1037       highlightObjCImplicitPropertyRef(OPRE->getImplicitPropertySetter(),
1038                                        OPRE->getLocation());
1039     }
1040     return true;
1041   }
1042
1043   bool VisitOverloadExpr(OverloadExpr *E) {
1044     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1045     if (!E->decls().empty())
1046       return true; // handled by findExplicitReferences.
1047     auto &Tok = H.addToken(E->getNameLoc(), HighlightingKind::Unknown)
1048                     .addModifier(HighlightingModifier::DependentName);
1049     if (llvm::isa<UnresolvedMemberExpr>(E))
1050       Tok.addModifier(HighlightingModifier::ClassScope);
1051     // other case is UnresolvedLookupExpr, scope is unknown.
1052     return true;
1053   }
1054
1055   bool VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
1056     H.addToken(E->getMemberNameInfo().getLoc(), HighlightingKind::Unknown)
1057         .addModifier(HighlightingModifier::DependentName)
1058         .addModifier(HighlightingModifier::ClassScope);
1059     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1060     return true;
1061   }
1062
1063   bool VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *E) {
1064     H.addToken(E->getNameInfo().getLoc(), HighlightingKind::Unknown)
1065         .addModifier(HighlightingModifier::DependentName)
1066         .addModifier(HighlightingModifier::ClassScope);
1067     H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1068     return true;
1069   }
1070
1071   bool VisitAttr(Attr *A) {
1072     switch (A->getKind()) {
1073     case attr::Override:
1074     case attr::Final:
1075       H.addToken(A->getLocation(), HighlightingKind::Modifier);
1076       break;
1077     default:
1078       break;
1079     }
1080     return true;
1081   }
1082
1083   bool VisitDependentNameTypeLoc(DependentNameTypeLoc L) {
1084     H.addToken(L.getNameLoc(), HighlightingKind::Type)
1085         .addModifier(HighlightingModifier::DependentName)
1086         .addModifier(HighlightingModifier::ClassScope);
1087     return true;
1088   }
1089
1090   bool VisitDependentTemplateSpecializationTypeLoc(
1091       DependentTemplateSpecializationTypeLoc L) {
1092     H.addToken(L.getTemplateNameLoc(), HighlightingKind::Type)
1093         .addModifier(HighlightingModifier::DependentName)
1094         .addModifier(HighlightingModifier::ClassScope);
1095     H.addAngleBracketTokens(L.getLAngleLoc(), L.getRAngleLoc());
1096     return true;
1097   }
1098
1099   bool TraverseTemplateArgumentLoc(TemplateArgumentLoc L) {
1100     // Handle template template arguments only (other arguments are handled by
1101     // their Expr, TypeLoc etc values).
1102     if (L.getArgument().getKind() != TemplateArgument::Template &&
1103         L.getArgument().getKind() != TemplateArgument::TemplateExpansion)
1104       return RecursiveASTVisitor::TraverseTemplateArgumentLoc(L);
1105
1106     TemplateName N = L.getArgument().getAsTemplateOrTemplatePattern();
1107     switch (N.getKind()) {
1108     case TemplateName::OverloadedTemplate:
1109       // Template template params must always be class templates.
1110       // Don't bother to try to work out the scope here.
1111       H.addToken(L.getTemplateNameLoc(), HighlightingKind::Class);
1112       break;
1113     case TemplateName::DependentTemplate:
1114     case TemplateName::AssumedTemplate:
1115       H.addToken(L.getTemplateNameLoc(), HighlightingKind::Class)
1116           .addModifier(HighlightingModifier::DependentName);
1117       break;
1118     case TemplateName::Template:
1119     case TemplateName::QualifiedTemplate:
1120     case TemplateName::SubstTemplateTemplateParm:
1121     case TemplateName::SubstTemplateTemplateParmPack:
1122     case TemplateName::UsingTemplate:
1123     case TemplateName::DeducedTemplate:
1124       // Names that could be resolved to a TemplateDecl are handled elsewhere.
1125       break;
1126     }
1127     return RecursiveASTVisitor::TraverseTemplateArgumentLoc(L);
1128   }
1129
1130   // findExplicitReferences will walk nested-name-specifiers and
1131   // find anything that can be resolved to a Decl. However, non-leaf
1132   // components of nested-name-specifiers which are dependent names
1133   // (kind "Identifier") cannot be resolved to a decl, so we visit
1134   // them here.
1135   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc Q) {
1136     if (NestedNameSpecifier *NNS = Q.getNestedNameSpecifier()) {
1137       if (NNS->getKind() == NestedNameSpecifier::Identifier)
1138         H.addToken(Q.getLocalBeginLoc(), HighlightingKind::Type)
1139             .addModifier(HighlightingModifier::DependentName)
1140             .addModifier(HighlightingModifier::ClassScope);
1141     }
1142     return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(Q);
1143   }
1144
1145 private:
1146   HighlightingsBuilder &H;
1147 };
1148 } // namespace
1149
1150 std::vector<HighlightingToken>
1151 getSemanticHighlightings(ParsedAST &AST, bool IncludeInactiveRegionTokens) {
1152   auto &C = AST.getASTContext();
1153   HighlightingFilter Filter = HighlightingFilter::fromCurrentConfig();
1154   if (!IncludeInactiveRegionTokens)
1155     Filter.disableKind(HighlightingKind::InactiveCode);
1156   // Add highlightings for AST nodes.
1157   HighlightingsBuilder Builder(AST, Filter);
1158   // Highlight 'decltype' and 'auto' as their underlying types.
1159   CollectExtraHighlightings(Builder).TraverseAST(C);
1160   // Highlight all decls and references coming from the AST.
1161   findExplicitReferences(
1162       C,
1163       [&](ReferenceLoc R) {
1164         for (const NamedDecl *Decl : R.Targets) {
1165           if (!canHighlightName(Decl->getDeclName()))
1166             continue;
1167           auto Kind = kindForDecl(Decl, AST.getHeuristicResolver());
1168           if (!Kind)
1169             continue;
1170           auto &Tok = Builder.addToken(R.NameLoc, *Kind);
1171
1172           // The attribute tests don't want to look at the template.
1173           if (auto *TD = dyn_cast<TemplateDecl>(Decl)) {
1174             if (auto *Templated = TD->getTemplatedDecl())
1175               Decl = Templated;
1176           }
1177           if (auto Mod = scopeModifier(Decl))
1178             Tok.addModifier(*Mod);
1179           if (isConst(Decl))
1180             Tok.addModifier(HighlightingModifier::Readonly);
1181           if (isStatic(Decl))
1182             Tok.addModifier(HighlightingModifier::Static);
1183           if (isAbstract(Decl))
1184             Tok.addModifier(HighlightingModifier::Abstract);
1185           if (isVirtual(Decl))
1186             Tok.addModifier(HighlightingModifier::Virtual);
1187           if (isDependent(Decl))
1188             Tok.addModifier(HighlightingModifier::DependentName);
1189           if (isDefaultLibrary(Decl))
1190             Tok.addModifier(HighlightingModifier::DefaultLibrary);
1191           if (Decl->isDeprecated())
1192             Tok.addModifier(HighlightingModifier::Deprecated);
1193           if (isa<CXXConstructorDecl>(Decl))
1194             Tok.addModifier(HighlightingModifier::ConstructorOrDestructor);
1195           if (R.IsDecl) {
1196             // Do not treat an UnresolvedUsingValueDecl as a declaration.
1197             // It's more common to think of it as a reference to the
1198             // underlying declaration.
1199             if (!isa<UnresolvedUsingValueDecl>(Decl))
1200               Tok.addModifier(HighlightingModifier::Declaration);
1201             if (isUniqueDefinition(Decl))
1202               Tok.addModifier(HighlightingModifier::Definition);
1203           }
1204         }
1205       },
1206       AST.getHeuristicResolver());
1207   // Add highlightings for macro references.
1208   auto AddMacro = [&](const MacroOccurrence &M) {
1209     auto &T = Builder.addToken(M.toRange(C.getSourceManager()),
1210                                HighlightingKind::Macro);
1211     T.addModifier(HighlightingModifier::GlobalScope);
1212     if (M.IsDefinition)
1213       T.addModifier(HighlightingModifier::Declaration);
1214   };
1215   for (const auto &SIDToRefs : AST.getMacros().MacroRefs)
1216     for (const auto &M : SIDToRefs.second)
1217       AddMacro(M);
1218   for (const auto &M : AST.getMacros().UnknownMacros)
1219     AddMacro(M);
1220
1221   return std::move(Builder).collect(AST);
1222 }
1223
1224 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K) {
1225   switch (K) {
1226   case HighlightingKind::Variable:
1227     return OS << "Variable";
1228   case HighlightingKind::LocalVariable:
1229     return OS << "LocalVariable";
1230   case HighlightingKind::Parameter:
1231     return OS << "Parameter";
1232   case HighlightingKind::Function:
1233     return OS << "Function";
1234   case HighlightingKind::Method:
1235     return OS << "Method";
1236   case HighlightingKind::StaticMethod:
1237     return OS << "StaticMethod";
1238   case HighlightingKind::Field:
1239     return OS << "Field";
1240   case HighlightingKind::StaticField:
1241     return OS << "StaticField";
1242   case HighlightingKind::Class:
1243     return OS << "Class";
1244   case HighlightingKind::Interface:
1245     return OS << "Interface";
1246   case HighlightingKind::Enum:
1247     return OS << "Enum";
1248   case HighlightingKind::EnumConstant:
1249     return OS << "EnumConstant";
1250   case HighlightingKind::Typedef:
1251     return OS << "Typedef";
1252   case HighlightingKind::Type:
1253     return OS << "Type";
1254   case HighlightingKind::Unknown:
1255     return OS << "Unknown";
1256   case HighlightingKind::Namespace:
1257     return OS << "Namespace";
1258   case HighlightingKind::TemplateParameter:
1259     return OS << "TemplateParameter";
1260   case HighlightingKind::Concept:
1261     return OS << "Concept";
1262   case HighlightingKind::Primitive:
1263     return OS << "Primitive";
1264   case HighlightingKind::Macro:
1265     return OS << "Macro";
1266   case HighlightingKind::Modifier:
1267     return OS << "Modifier";
1268   case HighlightingKind::Operator:
1269     return OS << "Operator";
1270   case HighlightingKind::Bracket:
1271     return OS << "Bracket";
1272   case HighlightingKind::Label:
1273     return OS << "Label";
1274   case HighlightingKind::InactiveCode:
1275     return OS << "InactiveCode";
1276   }
1277   llvm_unreachable("invalid HighlightingKind");
1278 }
1279 std::optional<HighlightingKind>
1280 highlightingKindFromString(llvm::StringRef Name) {
1281   static llvm::StringMap<HighlightingKind> Lookup = {
1282       {"Variable", HighlightingKind::Variable},
1283       {"LocalVariable", HighlightingKind::LocalVariable},
1284       {"Parameter", HighlightingKind::Parameter},
1285       {"Function", HighlightingKind::Function},
1286       {"Method", HighlightingKind::Method},
1287       {"StaticMethod", HighlightingKind::StaticMethod},
1288       {"Field", HighlightingKind::Field},
1289       {"StaticField", HighlightingKind::StaticField},
1290       {"Class", HighlightingKind::Class},
1291       {"Interface", HighlightingKind::Interface},
1292       {"Enum", HighlightingKind::Enum},
1293       {"EnumConstant", HighlightingKind::EnumConstant},
1294       {"Typedef", HighlightingKind::Typedef},
1295       {"Type", HighlightingKind::Type},
1296       {"Unknown", HighlightingKind::Unknown},
1297       {"Namespace", HighlightingKind::Namespace},
1298       {"TemplateParameter", HighlightingKind::TemplateParameter},
1299       {"Concept", HighlightingKind::Concept},
1300       {"Primitive", HighlightingKind::Primitive},
1301       {"Macro", HighlightingKind::Macro},
1302       {"Modifier", HighlightingKind::Modifier},
1303       {"Operator", HighlightingKind::Operator},
1304       {"Bracket", HighlightingKind::Bracket},
1305       {"InactiveCode", HighlightingKind::InactiveCode},
1306   };
1307
1308   auto It = Lookup.find(Name);
1309   return It != Lookup.end() ? std::make_optional(It->getValue()) : std::nullopt;
1310 }
1311 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingModifier K) {
1312   switch (K) {
1313   case HighlightingModifier::Declaration:
1314     return OS << "decl"; // abbreviation for common case
1315   case HighlightingModifier::Definition:
1316     return OS << "def"; // abbrevation for common case
1317   case HighlightingModifier::ConstructorOrDestructor:
1318     return OS << "constrDestr";
1319   default:
1320     return OS << toSemanticTokenModifier(K);
1321   }
1322 }
1323 std::optional<HighlightingModifier>
1324 highlightingModifierFromString(llvm::StringRef Name) {
1325   static llvm::StringMap<HighlightingModifier> Lookup = {
1326       {"Declaration", HighlightingModifier::Declaration},
1327       {"Definition", HighlightingModifier::Definition},
1328       {"Deprecated", HighlightingModifier::Deprecated},
1329       {"Deduced", HighlightingModifier::Deduced},
1330       {"Readonly", HighlightingModifier::Readonly},
1331       {"Static", HighlightingModifier::Static},
1332       {"Abstract", HighlightingModifier::Abstract},
1333       {"Virtual", HighlightingModifier::Virtual},
1334       {"DependentName", HighlightingModifier::DependentName},
1335       {"DefaultLibrary", HighlightingModifier::DefaultLibrary},
1336       {"UsedAsMutableReference", HighlightingModifier::UsedAsMutableReference},
1337       {"UsedAsMutablePointer", HighlightingModifier::UsedAsMutablePointer},
1338       {"ConstructorOrDestructor",
1339        HighlightingModifier::ConstructorOrDestructor},
1340       {"UserDefined", HighlightingModifier::UserDefined},
1341       {"FunctionScope", HighlightingModifier::FunctionScope},
1342       {"ClassScope", HighlightingModifier::ClassScope},
1343       {"FileScope", HighlightingModifier::FileScope},
1344       {"GlobalScope", HighlightingModifier::GlobalScope},
1345   };
1346
1347   auto It = Lookup.find(Name);
1348   return It != Lookup.end() ? std::make_optional(It->getValue()) : std::nullopt;
1349 }
1350
1351 bool operator==(const HighlightingToken &L, const HighlightingToken &R) {
1352   return std::tie(L.R, L.Kind, L.Modifiers) ==
1353          std::tie(R.R, R.Kind, R.Modifiers);
1354 }
1355 bool operator<(const HighlightingToken &L, const HighlightingToken &R) {
1356   return std::tie(L.R, L.Kind, L.Modifiers) <
1357          std::tie(R.R, R.Kind, R.Modifiers);
1358 }
1359
1360 std::vector<SemanticToken>
1361 toSemanticTokens(llvm::ArrayRef<HighlightingToken> Tokens,
1362                  llvm::StringRef Code) {
1363   assert(llvm::is_sorted(Tokens));
1364   std::vector<SemanticToken> Result;
1365   // In case we split a HighlightingToken into multiple tokens (e.g. because it
1366   // was spanning multiple lines), this tracks the last one. This prevents
1367   // having a copy all the time.
1368   HighlightingToken Scratch;
1369   const HighlightingToken *Last = nullptr;
1370   for (const HighlightingToken &Tok : Tokens) {
1371     Result.emplace_back();
1372     SemanticToken *Out = &Result.back();
1373     // deltaStart/deltaLine are relative if possible.
1374     if (Last) {
1375       assert(Tok.R.start.line >= Last->R.end.line);
1376       Out->deltaLine = Tok.R.start.line - Last->R.end.line;
1377       if (Out->deltaLine == 0) {
1378         assert(Tok.R.start.character >= Last->R.start.character);
1379         Out->deltaStart = Tok.R.start.character - Last->R.start.character;
1380       } else {
1381         Out->deltaStart = Tok.R.start.character;
1382       }
1383     } else {
1384       Out->deltaLine = Tok.R.start.line;
1385       Out->deltaStart = Tok.R.start.character;
1386     }
1387     Out->tokenType = static_cast<unsigned>(Tok.Kind);
1388     Out->tokenModifiers = Tok.Modifiers;
1389     Last = &Tok;
1390
1391     if (Tok.R.end.line == Tok.R.start.line) {
1392       Out->length = Tok.R.end.character - Tok.R.start.character;
1393     } else {
1394       // If the token spans a line break, split it into multiple pieces for each
1395       // line.
1396       // This is slow, but multiline tokens are rare.
1397       // FIXME: There's a client capability for supporting multiline tokens,
1398       // respect that.
1399       auto TokStartOffset = llvm::cantFail(positionToOffset(Code, Tok.R.start));
1400       // Note that the loop doesn't cover the last line, which has a special
1401       // length.
1402       for (int I = Tok.R.start.line; I < Tok.R.end.line; ++I) {
1403         auto LineEnd = Code.find('\n', TokStartOffset);
1404         assert(LineEnd != Code.npos);
1405         Out->length = LineEnd - TokStartOffset;
1406         // Token continues on next line, right after the line break.
1407         TokStartOffset = LineEnd + 1;
1408         Result.emplace_back();
1409         Out = &Result.back();
1410         *Out = Result[Result.size() - 2];
1411         // New token starts at the first column of the next line.
1412         Out->deltaLine = 1;
1413         Out->deltaStart = 0;
1414       }
1415       // This is the token on last line.
1416       Out->length = Tok.R.end.character;
1417       // Update the start location for last token, as that's used in the
1418       // relative delta calculation for following tokens.
1419       Scratch = *Last;
1420       Scratch.R.start.line = Tok.R.end.line;
1421       Scratch.R.start.character = 0;
1422       Last = &Scratch;
1423     }
1424   }
1425   return Result;
1426 }
1427 llvm::StringRef toSemanticTokenType(HighlightingKind Kind) {
1428   switch (Kind) {
1429   case HighlightingKind::Variable:
1430   case HighlightingKind::LocalVariable:
1431   case HighlightingKind::StaticField:
1432     return "variable";
1433   case HighlightingKind::Parameter:
1434     return "parameter";
1435   case HighlightingKind::Function:
1436     return "function";
1437   case HighlightingKind::Method:
1438     return "method";
1439   case HighlightingKind::StaticMethod:
1440     // FIXME: better method with static modifier?
1441     return "function";
1442   case HighlightingKind::Field:
1443     return "property";
1444   case HighlightingKind::Class:
1445     return "class";
1446   case HighlightingKind::Interface:
1447     return "interface";
1448   case HighlightingKind::Enum:
1449     return "enum";
1450   case HighlightingKind::EnumConstant:
1451     return "enumMember";
1452   case HighlightingKind::Typedef:
1453   case HighlightingKind::Type:
1454     return "type";
1455   case HighlightingKind::Unknown:
1456     return "unknown"; // nonstandard
1457   case HighlightingKind::Namespace:
1458     return "namespace";
1459   case HighlightingKind::TemplateParameter:
1460     return "typeParameter";
1461   case HighlightingKind::Concept:
1462     return "concept"; // nonstandard
1463   case HighlightingKind::Primitive:
1464     return "type";
1465   case HighlightingKind::Macro:
1466     return "macro";
1467   case HighlightingKind::Modifier:
1468     return "modifier";
1469   case HighlightingKind::Operator:
1470     return "operator";
1471   case HighlightingKind::Bracket:
1472     return "bracket";
1473   case HighlightingKind::Label:
1474     return "label";
1475   case HighlightingKind::InactiveCode:
1476     return "comment";
1477   }
1478   llvm_unreachable("unhandled HighlightingKind");
1479 }
1480
1481 llvm::StringRef toSemanticTokenModifier(HighlightingModifier Modifier) {
1482   switch (Modifier) {
1483   case HighlightingModifier::Declaration:
1484     return "declaration";
1485   case HighlightingModifier::Definition:
1486     return "definition";
1487   case HighlightingModifier::Deprecated:
1488     return "deprecated";
1489   case HighlightingModifier::Readonly:
1490     return "readonly";
1491   case HighlightingModifier::Static:
1492     return "static";
1493   case HighlightingModifier::Deduced:
1494     return "deduced"; // nonstandard
1495   case HighlightingModifier::Abstract:
1496     return "abstract";
1497   case HighlightingModifier::Virtual:
1498     return "virtual";
1499   case HighlightingModifier::DependentName:
1500     return "dependentName"; // nonstandard
1501   case HighlightingModifier::DefaultLibrary:
1502     return "defaultLibrary";
1503   case HighlightingModifier::UsedAsMutableReference:
1504     return "usedAsMutableReference"; // nonstandard
1505   case HighlightingModifier::UsedAsMutablePointer:
1506     return "usedAsMutablePointer"; // nonstandard
1507   case HighlightingModifier::ConstructorOrDestructor:
1508     return "constructorOrDestructor"; // nonstandard
1509   case HighlightingModifier::UserDefined:
1510     return "userDefined"; // nonstandard
1511   case HighlightingModifier::FunctionScope:
1512     return "functionScope"; // nonstandard
1513   case HighlightingModifier::ClassScope:
1514     return "classScope"; // nonstandard
1515   case HighlightingModifier::FileScope:
1516     return "fileScope"; // nonstandard
1517   case HighlightingModifier::GlobalScope:
1518     return "globalScope"; // nonstandard
1519   }
1520   llvm_unreachable("unhandled HighlightingModifier");
1521 }
1522
1523 std::vector<SemanticTokensEdit>
1524 diffTokens(llvm::ArrayRef<SemanticToken> Old,
1525            llvm::ArrayRef<SemanticToken> New) {
1526   // For now, just replace everything from the first-last modification.
1527   // FIXME: use a real diff instead, this is bad with include-insertion.
1528
1529   unsigned Offset = 0;
1530   while (!Old.empty() && !New.empty() && Old.front() == New.front()) {
1531     ++Offset;
1532     Old = Old.drop_front();
1533     New = New.drop_front();
1534   }
1535   while (!Old.empty() && !New.empty() && Old.back() == New.back()) {
1536     Old = Old.drop_back();
1537     New = New.drop_back();
1538   }
1539
1540   if (Old.empty() && New.empty())
1541     return {};
1542   SemanticTokensEdit Edit;
1543   Edit.startToken = Offset;
1544   Edit.deleteTokens = Old.size();
1545   Edit.tokens = New;
1546   return {std::move(Edit)};
1547 }
1548
1549 std::vector<Range> getInactiveRegions(ParsedAST &AST) {
1550   std::vector<Range> SkippedRanges(std::move(AST.getMacros().SkippedRanges));
1551   const auto &SM = AST.getSourceManager();
1552   StringRef MainCode = SM.getBufferOrFake(SM.getMainFileID()).getBuffer();
1553   std::vector<Range> InactiveRegions;
1554   for (const Range &Skipped : SkippedRanges) {
1555     Range Inactive = Skipped;
1556     // Sometimes, SkippedRanges contains a range ending at position 0
1557     // of a line. Clients that apply whole-line styles will treat that
1558     // line as inactive which is not desirable, so adjust the ending
1559     // position to be the end of the previous line.
1560     if (Inactive.end.character == 0 && Inactive.end.line > 0) {
1561       --Inactive.end.line;
1562     }
1563     // Exclude the directive lines themselves from the range.
1564     if (Inactive.end.line >= Inactive.start.line + 2) {
1565       ++Inactive.start.line;
1566       --Inactive.end.line;
1567     } else {
1568       // range would be empty, e.g. #endif on next line after #ifdef
1569       continue;
1570     }
1571     // Since we've adjusted the ending line, we need to recompute the
1572     // column to reflect the end of that line.
1573     if (auto EndOfLine = endOfLine(MainCode, Inactive.end.line)) {
1574       Inactive.end = *EndOfLine;
1575     } else {
1576       elog("Failed to determine end of line: {0}", EndOfLine.takeError());
1577       continue;
1578     }
1579     InactiveRegions.push_back(Inactive);
1580   }
1581   return InactiveRegions;
1582 }
1583
1584 } // namespace clangd
1585 } // namespace clang