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