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