llvm-project

1
//===--- SemanticHighlighting.cpp - ------------------------- ---*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8

9
#include "SemanticHighlighting.h"
10
#include "Config.h"
11
#include "FindTarget.h"
12
#include "HeuristicResolver.h"
13
#include "ParsedAST.h"
14
#include "Protocol.h"
15
#include "SourceCode.h"
16
#include "support/Logger.h"
17
#include "clang/AST/ASTContext.h"
18
#include "clang/AST/Decl.h"
19
#include "clang/AST/DeclCXX.h"
20
#include "clang/AST/DeclObjC.h"
21
#include "clang/AST/DeclTemplate.h"
22
#include "clang/AST/DeclarationName.h"
23
#include "clang/AST/ExprCXX.h"
24
#include "clang/AST/RecursiveASTVisitor.h"
25
#include "clang/AST/Type.h"
26
#include "clang/AST/TypeLoc.h"
27
#include "clang/Basic/LangOptions.h"
28
#include "clang/Basic/SourceLocation.h"
29
#include "clang/Basic/SourceManager.h"
30
#include "clang/Tooling/Syntax/Tokens.h"
31
#include "llvm/ADT/STLExtras.h"
32
#include "llvm/ADT/StringRef.h"
33
#include "llvm/Support/Casting.h"
34
#include "llvm/Support/Error.h"
35
#include <algorithm>
36
#include <optional>
37

38
namespace clang {
39
namespace clangd {
40
namespace {
41

42
/// Get the last Position on a given line.
43
llvm::Expected<Position> endOfLine(llvm::StringRef Code, int Line) {
44
  auto StartOfLine = positionToOffset(Code, Position{Line, 0});
45
  if (!StartOfLine)
46
    return StartOfLine.takeError();
47
  StringRef LineText = Code.drop_front(*StartOfLine).take_until([](char C) {
48
    return C == '\n';
49
  });
50
  return Position{Line, static_cast<int>(lspLength(LineText))};
51
}
52

53
/// Some names are not written in the source code and cannot be highlighted,
54
/// e.g. anonymous classes. This function detects those cases.
55
bool canHighlightName(DeclarationName Name) {
56
  switch (Name.getNameKind()) {
57
  case DeclarationName::Identifier: {
58
    auto *II = Name.getAsIdentifierInfo();
59
    return II && !II->getName().empty();
60
  }
61
  case DeclarationName::CXXConstructorName:
62
  case DeclarationName::CXXDestructorName:
63
    return true;
64
  case DeclarationName::ObjCZeroArgSelector:
65
  case DeclarationName::ObjCOneArgSelector:
66
  case DeclarationName::ObjCMultiArgSelector:
67
    // Multi-arg selectors need special handling, and we handle 0/1 arg
68
    // selectors there too.
69
    return false;
70
  case DeclarationName::CXXConversionFunctionName:
71
  case DeclarationName::CXXOperatorName:
72
  case DeclarationName::CXXDeductionGuideName:
73
  case DeclarationName::CXXLiteralOperatorName:
74
  case DeclarationName::CXXUsingDirective:
75
    return false;
76
  }
77
  llvm_unreachable("invalid name kind");
78
}
79

80
bool isUniqueDefinition(const NamedDecl *Decl) {
81
  if (auto *Func = dyn_cast<FunctionDecl>(Decl))
82
    return Func->isThisDeclarationADefinition();
83
  if (auto *Klass = dyn_cast<CXXRecordDecl>(Decl))
84
    return Klass->isThisDeclarationADefinition();
85
  if (auto *Iface = dyn_cast<ObjCInterfaceDecl>(Decl))
86
    return Iface->isThisDeclarationADefinition();
87
  if (auto *Proto = dyn_cast<ObjCProtocolDecl>(Decl))
88
    return Proto->isThisDeclarationADefinition();
89
  if (auto *Var = dyn_cast<VarDecl>(Decl))
90
    return Var->isThisDeclarationADefinition();
91
  return isa<TemplateTypeParmDecl>(Decl) ||
92
         isa<NonTypeTemplateParmDecl>(Decl) ||
93
         isa<TemplateTemplateParmDecl>(Decl) || isa<ObjCCategoryDecl>(Decl) ||
94
         isa<ObjCImplDecl>(Decl);
95
}
96

97
std::optional<HighlightingKind> kindForType(const Type *TP,
98
                                            const HeuristicResolver *Resolver);
99
std::optional<HighlightingKind> kindForDecl(const NamedDecl *D,
100
                                            const HeuristicResolver *Resolver) {
101
  if (auto *USD = dyn_cast<UsingShadowDecl>(D)) {
102
    if (auto *Target = USD->getTargetDecl())
103
      D = Target;
104
  }
105
  if (auto *TD = dyn_cast<TemplateDecl>(D)) {
106
    if (auto *Templated = TD->getTemplatedDecl())
107
      D = Templated;
108
  }
109
  if (auto *TD = dyn_cast<TypedefNameDecl>(D)) {
110
    // We try to highlight typedefs as their underlying type.
111
    if (auto K =
112
            kindForType(TD->getUnderlyingType().getTypePtrOrNull(), Resolver))
113
      return K;
114
    // And fallback to a generic kind if this fails.
115
    return HighlightingKind::Typedef;
116
  }
117
  // We highlight class decls, constructor decls and destructor decls as
118
  // `Class` type. The destructor decls are handled in `VisitTagTypeLoc` (we
119
  // will visit a TypeLoc where the underlying Type is a CXXRecordDecl).
120
  if (auto *RD = llvm::dyn_cast<RecordDecl>(D)) {
121
    // We don't want to highlight lambdas like classes.
122
    if (RD->isLambda())
123
      return std::nullopt;
124
    return HighlightingKind::Class;
125
  }
126
  if (isa<ClassTemplateDecl, RecordDecl, CXXConstructorDecl, ObjCInterfaceDecl,
127
          ObjCImplementationDecl>(D))
128
    return HighlightingKind::Class;
129
  if (isa<ObjCProtocolDecl>(D))
130
    return HighlightingKind::Interface;
131
  if (isa<ObjCCategoryDecl, ObjCCategoryImplDecl>(D))
132
    return HighlightingKind::Namespace;
133
  if (auto *MD = dyn_cast<CXXMethodDecl>(D))
134
    return MD->isStatic() ? HighlightingKind::StaticMethod
135
                          : HighlightingKind::Method;
136
  if (auto *OMD = dyn_cast<ObjCMethodDecl>(D))
137
    return OMD->isClassMethod() ? HighlightingKind::StaticMethod
138
                                : HighlightingKind::Method;
139
  if (isa<FieldDecl, IndirectFieldDecl, ObjCPropertyDecl>(D))
140
    return HighlightingKind::Field;
141
  if (isa<EnumDecl>(D))
142
    return HighlightingKind::Enum;
143
  if (isa<EnumConstantDecl>(D))
144
    return HighlightingKind::EnumConstant;
145
  if (isa<ParmVarDecl>(D))
146
    return HighlightingKind::Parameter;
147
  if (auto *VD = dyn_cast<VarDecl>(D)) {
148
    if (isa<ImplicitParamDecl>(VD)) // e.g. ObjC Self
149
      return std::nullopt;
150
    return VD->isStaticDataMember()
151
               ? HighlightingKind::StaticField
152
               : VD->isLocalVarDecl() ? HighlightingKind::LocalVariable
153
                                      : HighlightingKind::Variable;
154
  }
155
  if (const auto *BD = dyn_cast<BindingDecl>(D))
156
    return BD->getDeclContext()->isFunctionOrMethod()
157
               ? HighlightingKind::LocalVariable
158
               : HighlightingKind::Variable;
159
  if (isa<FunctionDecl>(D))
160
    return HighlightingKind::Function;
161
  if (isa<NamespaceDecl>(D) || isa<NamespaceAliasDecl>(D) ||
162
      isa<UsingDirectiveDecl>(D))
163
    return HighlightingKind::Namespace;
164
  if (isa<TemplateTemplateParmDecl>(D) || isa<TemplateTypeParmDecl>(D) ||
165
      isa<NonTypeTemplateParmDecl>(D))
166
    return HighlightingKind::TemplateParameter;
167
  if (isa<ConceptDecl>(D))
168
    return HighlightingKind::Concept;
169
  if (isa<LabelDecl>(D))
170
    return HighlightingKind::Label;
171
  if (const auto *UUVD = dyn_cast<UnresolvedUsingValueDecl>(D)) {
172
    auto Targets = Resolver->resolveUsingValueDecl(UUVD);
173
    if (!Targets.empty() && Targets[0] != UUVD) {
174
      return kindForDecl(Targets[0], Resolver);
175
    }
176
    return HighlightingKind::Unknown;
177
  }
178
  return std::nullopt;
179
}
180
std::optional<HighlightingKind> kindForType(const Type *TP,
181
                                            const HeuristicResolver *Resolver) {
182
  if (!TP)
183
    return std::nullopt;
184
  if (TP->isBuiltinType()) // Builtins are special, they do not have decls.
185
    return HighlightingKind::Primitive;
186
  if (auto *TD = dyn_cast<TemplateTypeParmType>(TP))
187
    return kindForDecl(TD->getDecl(), Resolver);
188
  if (isa<ObjCObjectPointerType>(TP))
189
    return HighlightingKind::Class;
190
  if (auto *TD = TP->getAsTagDecl())
191
    return kindForDecl(TD, Resolver);
192
  return std::nullopt;
193
}
194

195
// Whether T is const in a loose sense - is a variable with this type readonly?
196
bool isConst(QualType T) {
197
  if (T.isNull())
198
    return false;
199
  T = T.getNonReferenceType();
200
  if (T.isConstQualified())
201
    return true;
202
  if (const auto *AT = T->getAsArrayTypeUnsafe())
203
    return isConst(AT->getElementType());
204
  if (isConst(T->getPointeeType()))
205
    return true;
206
  return false;
207
}
208

209
// Whether D is const in a loose sense (should it be highlighted as such?)
210
// FIXME: This is separate from whether *a particular usage* can mutate D.
211
//        We may want V in V.size() to be readonly even if V is mutable.
212
bool isConst(const Decl *D) {
213
  if (llvm::isa<EnumConstantDecl>(D) || llvm::isa<NonTypeTemplateParmDecl>(D))
214
    return true;
215
  if (llvm::isa<FieldDecl>(D) || llvm::isa<VarDecl>(D) ||
216
      llvm::isa<MSPropertyDecl>(D) || llvm::isa<BindingDecl>(D)) {
217
    if (isConst(llvm::cast<ValueDecl>(D)->getType()))
218
      return true;
219
  }
220
  if (const auto *OCPD = llvm::dyn_cast<ObjCPropertyDecl>(D)) {
221
    if (OCPD->isReadOnly())
222
      return true;
223
  }
224
  if (const auto *MPD = llvm::dyn_cast<MSPropertyDecl>(D)) {
225
    if (!MPD->hasSetter())
226
      return true;
227
  }
228
  if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D)) {
229
    if (CMD->isConst())
230
      return true;
231
  }
232
  return false;
233
}
234

235
// "Static" means many things in C++, only some get the "static" modifier.
236
//
237
// Meanings that do:
238
// - Members associated with the class rather than the instance.
239
//   This is what 'static' most often means across languages.
240
// - static local variables
241
//   These are similarly "detached from their context" by the static keyword.
242
//   In practice, these are rarely used inside classes, reducing confusion.
243
//
244
// Meanings that don't:
245
// - Namespace-scoped variables, which have static storage class.
246
//   This is implicit, so the keyword "static" isn't so strongly associated.
247
//   If we want a modifier for these, "global scope" is probably the concept.
248
// - Namespace-scoped variables/functions explicitly marked "static".
249
//   There the keyword changes *linkage* , which is a totally different concept.
250
//   If we want to model this, "file scope" would be a nice modifier.
251
//
252
// This is confusing, and maybe we should use another name, but because "static"
253
// is a standard LSP modifier, having one with that name has advantages.
254
bool isStatic(const Decl *D) {
255
  if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D))
256
    return CMD->isStatic();
257
  if (const VarDecl *VD = llvm::dyn_cast<VarDecl>(D))
258
    return VD->isStaticDataMember() || VD->isStaticLocal();
259
  if (const auto *OPD = llvm::dyn_cast<ObjCPropertyDecl>(D))
260
    return OPD->isClassProperty();
261
  if (const auto *OMD = llvm::dyn_cast<ObjCMethodDecl>(D))
262
    return OMD->isClassMethod();
263
  return false;
264
}
265

266
bool isAbstract(const Decl *D) {
267
  if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D))
268
    return CMD->isPureVirtual();
269
  if (const auto *CRD = llvm::dyn_cast<CXXRecordDecl>(D))
270
    return CRD->hasDefinition() && CRD->isAbstract();
271
  return false;
272
}
273

274
bool isVirtual(const Decl *D) {
275
  if (const auto *CMD = llvm::dyn_cast<CXXMethodDecl>(D))
276
    return CMD->isVirtual();
277
  return false;
278
}
279

280
bool isDependent(const Decl *D) {
281
  if (isa<UnresolvedUsingValueDecl>(D))
282
    return true;
283
  return false;
284
}
285

286
/// Returns true if `Decl` is considered to be from a default/system library.
287
/// This currently checks the systemness of the file by include type, although
288
/// different heuristics may be used in the future (e.g. sysroot paths).
289
bool isDefaultLibrary(const Decl *D) {
290
  SourceLocation Loc = D->getLocation();
291
  if (!Loc.isValid())
292
    return false;
293
  return D->getASTContext().getSourceManager().isInSystemHeader(Loc);
294
}
295

296
bool isDefaultLibrary(const Type *T) {
297
  if (!T)
298
    return false;
299
  const Type *Underlying = T->getPointeeOrArrayElementType();
300
  if (Underlying->isBuiltinType())
301
    return true;
302
  if (auto *TD = dyn_cast<TemplateTypeParmType>(Underlying))
303
    return isDefaultLibrary(TD->getDecl());
304
  if (auto *TD = Underlying->getAsTagDecl())
305
    return isDefaultLibrary(TD);
306
  return false;
307
}
308

309
// For a macro usage `DUMP(foo)`, we want:
310
//  - DUMP --> "macro"
311
//  - foo --> "variable".
312
SourceLocation getHighlightableSpellingToken(SourceLocation L,
313
                                             const SourceManager &SM) {
314
  if (L.isFileID())
315
    return SM.isWrittenInMainFile(L) ? L : SourceLocation{};
316
  // Tokens expanded from the macro body contribute no highlightings.
317
  if (!SM.isMacroArgExpansion(L))
318
    return {};
319
  // Tokens expanded from macro args are potentially highlightable.
320
  return getHighlightableSpellingToken(SM.getImmediateSpellingLoc(L), SM);
321
}
322

323
unsigned evaluateHighlightPriority(const HighlightingToken &Tok) {
324
  enum HighlightPriority { Dependent = 0, Resolved = 1 };
325
  return (Tok.Modifiers & (1 << uint32_t(HighlightingModifier::DependentName)))
326
             ? Dependent
327
             : Resolved;
328
}
329

330
// Sometimes we get multiple tokens at the same location:
331
//
332
// - findExplicitReferences() returns a heuristic result for a dependent name
333
//   (e.g. Method) and CollectExtraHighlighting returning a fallback dependent
334
//   highlighting (e.g. Unknown+Dependent).
335
// - macro arguments are expanded multiple times and have different roles
336
// - broken code recovery produces several AST nodes at the same location
337
//
338
// We should either resolve these to a single token, or drop them all.
339
// Our heuristics are:
340
//
341
// - token kinds that come with "dependent-name" modifiers are less reliable
342
//   (these tend to be vague, like Type or Unknown)
343
// - if we have multiple equally reliable kinds, drop token rather than guess
344
// - take the union of modifiers from all tokens
345
//
346
// In particular, heuristically resolved dependent names get their heuristic
347
// kind, plus the dependent modifier.
348
std::optional<HighlightingToken> resolveConflict(const HighlightingToken &A,
349
                                                 const HighlightingToken &B) {
350
  unsigned Priority1 = evaluateHighlightPriority(A);
351
  unsigned Priority2 = evaluateHighlightPriority(B);
352
  if (Priority1 == Priority2 && A.Kind != B.Kind)
353
    return std::nullopt;
354
  auto Result = Priority1 > Priority2 ? A : B;
355
  Result.Modifiers = A.Modifiers | B.Modifiers;
356
  return Result;
357
}
358
std::optional<HighlightingToken>
359
resolveConflict(ArrayRef<HighlightingToken> Tokens) {
360
  if (Tokens.size() == 1)
361
    return Tokens[0];
362

363
  assert(Tokens.size() >= 2);
364
  std::optional<HighlightingToken> Winner =
365
      resolveConflict(Tokens[0], Tokens[1]);
366
  for (size_t I = 2; Winner && I < Tokens.size(); ++I)
367
    Winner = resolveConflict(*Winner, Tokens[I]);
368
  return Winner;
369
}
370

371
/// Filter to remove particular kinds of highlighting tokens and modifiers from
372
/// the output.
373
class HighlightingFilter {
374
public:
375
  HighlightingFilter() {
376
    for (auto &Active : ActiveKindLookup)
377
      Active = true;
378

379
    ActiveModifiersMask = ~0;
380
  }
381

382
  void disableKind(HighlightingKind Kind) {
383
    ActiveKindLookup[static_cast<size_t>(Kind)] = false;
384
  }
385

386
  void disableModifier(HighlightingModifier Modifier) {
387
    ActiveModifiersMask &= ~(1 << static_cast<uint32_t>(Modifier));
388
  }
389

390
  bool isHighlightKindActive(HighlightingKind Kind) const {
391
    return ActiveKindLookup[static_cast<size_t>(Kind)];
392
  }
393

394
  uint32_t maskModifiers(uint32_t Modifiers) const {
395
    return Modifiers & ActiveModifiersMask;
396
  }
397

398
  static HighlightingFilter fromCurrentConfig() {
399
    const Config &C = Config::current();
400
    HighlightingFilter Filter;
401
    for (const auto &Kind : C.SemanticTokens.DisabledKinds)
402
      if (auto K = highlightingKindFromString(Kind))
403
        Filter.disableKind(*K);
404
    for (const auto &Modifier : C.SemanticTokens.DisabledModifiers)
405
      if (auto M = highlightingModifierFromString(Modifier))
406
        Filter.disableModifier(*M);
407

408
    return Filter;
409
  }
410

411
private:
412
  bool ActiveKindLookup[static_cast<size_t>(HighlightingKind::LastKind) + 1];
413
  uint32_t ActiveModifiersMask;
414
};
415

416
/// Consumes source locations and maps them to text ranges for highlightings.
417
class HighlightingsBuilder {
418
public:
419
  HighlightingsBuilder(const ParsedAST &AST, const HighlightingFilter &Filter)
420
      : TB(AST.getTokens()), SourceMgr(AST.getSourceManager()),
421
        LangOpts(AST.getLangOpts()), Filter(Filter),
422
        Resolver(AST.getHeuristicResolver()) {}
423

424
  HighlightingToken &addToken(SourceLocation Loc, HighlightingKind Kind) {
425
    auto Range = getRangeForSourceLocation(Loc);
426
    if (!Range)
427
      return InvalidHighlightingToken;
428

429
    return addToken(*Range, Kind);
430
  }
431

432
  // Most of this function works around
433
  // https://github.com/clangd/clangd/issues/871.
434
  void addAngleBracketTokens(SourceLocation LLoc, SourceLocation RLoc) {
435
    if (!LLoc.isValid() || !RLoc.isValid())
436
      return;
437

438
    auto LRange = getRangeForSourceLocation(LLoc);
439
    if (!LRange)
440
      return;
441

442
    // RLoc might be pointing at a virtual buffer when it's part of a `>>`
443
    // token.
444
    RLoc = SourceMgr.getFileLoc(RLoc);
445
    // Make sure token is part of the main file.
446
    RLoc = getHighlightableSpellingToken(RLoc, SourceMgr);
447
    if (!RLoc.isValid())
448
      return;
449

450
    const auto *RTok = TB.spelledTokenContaining(RLoc);
451
    // Handle `>>`. RLoc is either part of `>>` or a spelled token on its own
452
    // `>`. If it's the former, slice to have length of 1, if latter use the
453
    // token as-is.
454
    if (!RTok || RTok->kind() == tok::greatergreater) {
455
      Position Begin = sourceLocToPosition(SourceMgr, RLoc);
456
      Position End = sourceLocToPosition(SourceMgr, RLoc.getLocWithOffset(1));
457
      addToken(*LRange, HighlightingKind::Bracket);
458
      addToken({Begin, End}, HighlightingKind::Bracket);
459
      return;
460
    }
461

462
    // Easy case, we have the `>` token directly available.
463
    if (RTok->kind() == tok::greater) {
464
      if (auto RRange = getRangeForSourceLocation(RLoc)) {
465
        addToken(*LRange, HighlightingKind::Bracket);
466
        addToken(*RRange, HighlightingKind::Bracket);
467
      }
468
      return;
469
    }
470
  }
471

472
  HighlightingToken &addToken(Range R, HighlightingKind Kind) {
473
    if (!Filter.isHighlightKindActive(Kind))
474
      return InvalidHighlightingToken;
475

476
    HighlightingToken HT;
477
    HT.R = std::move(R);
478
    HT.Kind = Kind;
479
    Tokens.push_back(std::move(HT));
480
    return Tokens.back();
481
  }
482

483
  void addExtraModifier(SourceLocation Loc, HighlightingModifier Modifier) {
484
    if (auto Range = getRangeForSourceLocation(Loc))
485
      ExtraModifiers[*Range].push_back(Modifier);
486
  }
487

488
  std::vector<HighlightingToken> collect(ParsedAST &AST) && {
489
    // Initializer lists can give duplicates of tokens, therefore all tokens
490
    // must be deduplicated.
491
    llvm::sort(Tokens);
492
    auto Last = std::unique(Tokens.begin(), Tokens.end());
493
    Tokens.erase(Last, Tokens.end());
494

495
    // Macros can give tokens that have the same source range but conflicting
496
    // kinds. In this case all tokens sharing this source range should be
497
    // removed.
498
    std::vector<HighlightingToken> NonConflicting;
499
    NonConflicting.reserve(Tokens.size());
500
    for (ArrayRef<HighlightingToken> TokRef = Tokens; !TokRef.empty();) {
501
      ArrayRef<HighlightingToken> Conflicting =
502
          TokRef.take_while([&](const HighlightingToken &T) {
503
            // TokRef is guaranteed at least one element here because otherwise
504
            // this predicate would never fire.
505
            return T.R == TokRef.front().R;
506
          });
507
      if (auto Resolved = resolveConflict(Conflicting)) {
508
        // Apply extra collected highlighting modifiers
509
        auto Modifiers = ExtraModifiers.find(Resolved->R);
510
        if (Modifiers != ExtraModifiers.end()) {
511
          for (HighlightingModifier Mod : Modifiers->second) {
512
            Resolved->addModifier(Mod);
513
          }
514
        }
515

516
        Resolved->Modifiers = Filter.maskModifiers(Resolved->Modifiers);
517
        NonConflicting.push_back(*Resolved);
518
      }
519
      // TokRef[Conflicting.size()] is the next token with a different range (or
520
      // the end of the Tokens).
521
      TokRef = TokRef.drop_front(Conflicting.size());
522
    }
523

524
    if (!Filter.isHighlightKindActive(HighlightingKind::InactiveCode))
525
      return NonConflicting;
526

527
    const auto &SM = AST.getSourceManager();
528
    StringRef MainCode = SM.getBufferOrFake(SM.getMainFileID()).getBuffer();
529

530
    // Merge token stream with "inactive line" markers.
531
    std::vector<HighlightingToken> WithInactiveLines;
532
    auto SortedInactiveRegions = getInactiveRegions(AST);
533
    llvm::sort(SortedInactiveRegions);
534
    auto It = NonConflicting.begin();
535
    for (const Range &R : SortedInactiveRegions) {
536
      // Create one token for each line in the inactive range, so it works
537
      // with line-based diffing.
538
      assert(R.start.line <= R.end.line);
539
      for (int Line = R.start.line; Line <= R.end.line; ++Line) {
540
        // Copy tokens before the inactive line
541
        for (; It != NonConflicting.end() && It->R.start.line < Line; ++It)
542
          WithInactiveLines.push_back(std::move(*It));
543
        // Add a token for the inactive line itself.
544
        auto EndOfLine = endOfLine(MainCode, Line);
545
        if (EndOfLine) {
546
          HighlightingToken HT;
547
          WithInactiveLines.emplace_back();
548
          WithInactiveLines.back().Kind = HighlightingKind::InactiveCode;
549
          WithInactiveLines.back().R.start.line = Line;
550
          WithInactiveLines.back().R.end = *EndOfLine;
551
        } else {
552
          elog("Failed to determine end of line: {0}", EndOfLine.takeError());
553
        }
554

555
        // Skip any other tokens on the inactive line. e.g.
556
        // `#ifndef Foo` is considered as part of an inactive region when Foo is
557
        // defined, and there is a Foo macro token.
558
        // FIXME: we should reduce the scope of the inactive region to not
559
        // include the directive itself.
560
        while (It != NonConflicting.end() && It->R.start.line == Line)
561
          ++It;
562
      }
563
    }
564
    // Copy tokens after the last inactive line
565
    for (; It != NonConflicting.end(); ++It)
566
      WithInactiveLines.push_back(std::move(*It));
567
    return WithInactiveLines;
568
  }
569

570
  const HeuristicResolver *getResolver() const { return Resolver; }
571

572
private:
573
  std::optional<Range> getRangeForSourceLocation(SourceLocation Loc) {
574
    Loc = getHighlightableSpellingToken(Loc, SourceMgr);
575
    if (Loc.isInvalid())
576
      return std::nullopt;
577
    // We might have offsets in the main file that don't correspond to any
578
    // spelled tokens.
579
    const auto *Tok = TB.spelledTokenContaining(Loc);
580
    if (!Tok)
581
      return std::nullopt;
582
    return halfOpenToRange(SourceMgr,
583
                           Tok->range(SourceMgr).toCharRange(SourceMgr));
584
  }
585

586
  const syntax::TokenBuffer &TB;
587
  const SourceManager &SourceMgr;
588
  const LangOptions &LangOpts;
589
  HighlightingFilter Filter;
590
  std::vector<HighlightingToken> Tokens;
591
  std::map<Range, llvm::SmallVector<HighlightingModifier, 1>> ExtraModifiers;
592
  const HeuristicResolver *Resolver;
593
  // returned from addToken(InvalidLoc)
594
  HighlightingToken InvalidHighlightingToken;
595
};
596

597
std::optional<HighlightingModifier> scopeModifier(const NamedDecl *D) {
598
  const DeclContext *DC = D->getDeclContext();
599
  // Injected "Foo" within the class "Foo" has file scope, not class scope.
600
  if (auto *R = dyn_cast_or_null<RecordDecl>(D))
601
    if (R->isInjectedClassName())
602
      DC = DC->getParent();
603
  // Lambda captures are considered function scope, not class scope.
604
  if (llvm::isa<FieldDecl>(D))
605
    if (const auto *RD = llvm::dyn_cast<RecordDecl>(DC))
606
      if (RD->isLambda())
607
        return HighlightingModifier::FunctionScope;
608
  // Walk up the DeclContext hierarchy until we find something interesting.
609
  for (; !DC->isFileContext(); DC = DC->getParent()) {
610
    if (DC->isFunctionOrMethod())
611
      return HighlightingModifier::FunctionScope;
612
    if (DC->isRecord())
613
      return HighlightingModifier::ClassScope;
614
  }
615
  // Some template parameters (e.g. those for variable templates) don't have
616
  // meaningful DeclContexts. That doesn't mean they're global!
617
  if (DC->isTranslationUnit() && D->isTemplateParameter())
618
    return std::nullopt;
619
  // ExternalLinkage threshold could be tweaked, e.g. module-visible as global.
620
  if (llvm::to_underlying(D->getLinkageInternal()) <
621
      llvm::to_underlying(Linkage::External))
622
    return HighlightingModifier::FileScope;
623
  return HighlightingModifier::GlobalScope;
624
}
625

626
std::optional<HighlightingModifier> scopeModifier(const Type *T) {
627
  if (!T)
628
    return std::nullopt;
629
  if (T->isBuiltinType())
630
    return HighlightingModifier::GlobalScope;
631
  if (auto *TD = dyn_cast<TemplateTypeParmType>(T))
632
    return scopeModifier(TD->getDecl());
633
  if (auto *TD = T->getAsTagDecl())
634
    return scopeModifier(TD);
635
  return std::nullopt;
636
}
637

638
/// Produces highlightings, which are not captured by findExplicitReferences,
639
/// e.g. highlights dependent names and 'auto' as the underlying type.
640
class CollectExtraHighlightings
641
    : public RecursiveASTVisitor<CollectExtraHighlightings> {
642
  using Base = RecursiveASTVisitor<CollectExtraHighlightings>;
643

644
public:
645
  CollectExtraHighlightings(HighlightingsBuilder &H) : H(H) {}
646

647
  bool VisitCXXConstructExpr(CXXConstructExpr *E) {
648
    highlightMutableReferenceArguments(E->getConstructor(),
649
                                       {E->getArgs(), E->getNumArgs()});
650

651
    return true;
652
  }
653

654
  bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
655
    if (Init->isMemberInitializer())
656
      if (auto *Member = Init->getMember())
657
        highlightMutableReferenceArgument(Member->getType(), Init->getInit());
658
    return Base::TraverseConstructorInitializer(Init);
659
  }
660

661
  bool TraverseTypeConstraint(const TypeConstraint *C) {
662
    if (auto *Args = C->getTemplateArgsAsWritten())
663
      H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
664
    return Base::TraverseTypeConstraint(C);
665
  }
666

667
  bool VisitPredefinedExpr(PredefinedExpr *E) {
668
    H.addToken(E->getLocation(), HighlightingKind::LocalVariable)
669
        .addModifier(HighlightingModifier::Static)
670
        .addModifier(HighlightingModifier::Readonly)
671
        .addModifier(HighlightingModifier::FunctionScope);
672
    return true;
673
  }
674

675
  bool VisitConceptSpecializationExpr(ConceptSpecializationExpr *E) {
676
    if (auto *Args = E->getTemplateArgsAsWritten())
677
      H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
678
    return true;
679
  }
680

681
  bool VisitTemplateDecl(TemplateDecl *D) {
682
    if (auto *TPL = D->getTemplateParameters())
683
      H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
684
    return true;
685
  }
686

687
  bool VisitTagDecl(TagDecl *D) {
688
    for (unsigned i = 0; i < D->getNumTemplateParameterLists(); ++i) {
689
      if (auto *TPL = D->getTemplateParameterList(i))
690
        H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
691
    }
692
    return true;
693
  }
694

695
  bool
696
  VisitClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *D) {
697
    if (auto *Args = D->getTemplateArgsAsWritten())
698
      H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
699
    return true;
700
  }
701

702
  bool VisitClassTemplatePartialSpecializationDecl(
703
      ClassTemplatePartialSpecializationDecl *D) {
704
    if (auto *TPL = D->getTemplateParameters())
705
      H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
706
    return true;
707
  }
708

709
  bool VisitVarTemplateSpecializationDecl(VarTemplateSpecializationDecl *D) {
710
    if (auto *Args = D->getTemplateArgsAsWritten())
711
      H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
712
    return true;
713
  }
714

715
  bool VisitVarTemplatePartialSpecializationDecl(
716
      VarTemplatePartialSpecializationDecl *D) {
717
    if (auto *TPL = D->getTemplateParameters())
718
      H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
719
    return true;
720
  }
721

722
  bool VisitDeclRefExpr(DeclRefExpr *E) {
723
    H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
724
    return true;
725
  }
726
  bool VisitMemberExpr(MemberExpr *E) {
727
    H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
728
    return true;
729
  }
730

731
  bool VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) {
732
    H.addAngleBracketTokens(L.getLAngleLoc(), L.getRAngleLoc());
733
    return true;
734
  }
735

736
  bool VisitFunctionDecl(FunctionDecl *D) {
737
    if (D->isOverloadedOperator()) {
738
      const auto AddOpDeclToken = [&](SourceLocation Loc) {
739
        auto &Token = H.addToken(Loc, HighlightingKind::Operator)
740
                          .addModifier(HighlightingModifier::Declaration);
741
        if (D->isThisDeclarationADefinition())
742
          Token.addModifier(HighlightingModifier::Definition);
743
      };
744
      const auto Range = D->getNameInfo().getCXXOperatorNameRange();
745
      AddOpDeclToken(Range.getBegin());
746
      const auto Kind = D->getOverloadedOperator();
747
      if (Kind == OO_Call || Kind == OO_Subscript)
748
        AddOpDeclToken(Range.getEnd());
749
    }
750
    if (auto *Args = D->getTemplateSpecializationArgsAsWritten())
751
      H.addAngleBracketTokens(Args->getLAngleLoc(), Args->getRAngleLoc());
752
    return true;
753
  }
754

755
  bool VisitCXXOperatorCallExpr(CXXOperatorCallExpr *E) {
756
    const auto AddOpToken = [&](SourceLocation Loc) {
757
      H.addToken(Loc, HighlightingKind::Operator)
758
          .addModifier(HighlightingModifier::UserDefined);
759
    };
760
    AddOpToken(E->getOperatorLoc());
761
    const auto Kind = E->getOperator();
762
    if (Kind == OO_Call || Kind == OO_Subscript) {
763
      if (auto *Callee = E->getCallee())
764
        AddOpToken(Callee->getBeginLoc());
765
    }
766
    return true;
767
  }
768

769
  bool VisitUnaryOperator(UnaryOperator *Op) {
770
    auto &Token = H.addToken(Op->getOperatorLoc(), HighlightingKind::Operator);
771
    if (Op->getSubExpr()->isTypeDependent())
772
      Token.addModifier(HighlightingModifier::UserDefined);
773
    return true;
774
  }
775

776
  bool VisitBinaryOperator(BinaryOperator *Op) {
777
    auto &Token = H.addToken(Op->getOperatorLoc(), HighlightingKind::Operator);
778
    if (Op->getLHS()->isTypeDependent() || Op->getRHS()->isTypeDependent())
779
      Token.addModifier(HighlightingModifier::UserDefined);
780
    return true;
781
  }
782

783
  bool VisitConditionalOperator(ConditionalOperator *Op) {
784
    H.addToken(Op->getQuestionLoc(), HighlightingKind::Operator);
785
    H.addToken(Op->getColonLoc(), HighlightingKind::Operator);
786
    return true;
787
  }
788

789
  bool VisitCXXNewExpr(CXXNewExpr *E) {
790
    auto &Token = H.addToken(E->getBeginLoc(), HighlightingKind::Operator);
791
    if (isa_and_present<CXXMethodDecl>(E->getOperatorNew()))
792
      Token.addModifier(HighlightingModifier::UserDefined);
793
    return true;
794
  }
795

796
  bool VisitCXXDeleteExpr(CXXDeleteExpr *E) {
797
    auto &Token = H.addToken(E->getBeginLoc(), HighlightingKind::Operator);
798
    if (isa_and_present<CXXMethodDecl>(E->getOperatorDelete()))
799
      Token.addModifier(HighlightingModifier::UserDefined);
800
    return true;
801
  }
802

803
  bool VisitCXXNamedCastExpr(CXXNamedCastExpr *E) {
804
    const auto &B = E->getAngleBrackets();
805
    H.addAngleBracketTokens(B.getBegin(), B.getEnd());
806
    return true;
807
  }
808

809
  bool VisitCallExpr(CallExpr *E) {
810
    // Highlighting parameters passed by non-const reference does not really
811
    // make sense for literals...
812
    if (isa<UserDefinedLiteral>(E))
813
      return true;
814

815
    // FIXME: consider highlighting parameters of some other overloaded
816
    // operators as well
817
    llvm::ArrayRef<const Expr *> Args = {E->getArgs(), E->getNumArgs()};
818
    if (auto *CallOp = dyn_cast<CXXOperatorCallExpr>(E)) {
819
      switch (CallOp->getOperator()) {
820
      case OO_Call:
821
      case OO_Subscript:
822
        Args = Args.drop_front(); // Drop object parameter
823
        break;
824
      default:
825
        return true;
826
      }
827
    }
828

829
    highlightMutableReferenceArguments(
830
        dyn_cast_or_null<FunctionDecl>(E->getCalleeDecl()), Args);
831

832
    return true;
833
  }
834

835
  void highlightMutableReferenceArgument(QualType T, const Expr *Arg) {
836
    if (!Arg)
837
      return;
838

839
    // Is this parameter passed by non-const pointer or reference?
840
    // FIXME The condition T->idDependentType() could be relaxed a bit,
841
    // e.g. std::vector<T>& is dependent but we would want to highlight it
842
    bool IsRef = T->isLValueReferenceType();
843
    bool IsPtr = T->isPointerType();
844
    if ((!IsRef && !IsPtr) || T->getPointeeType().isConstQualified() ||
845
        T->isDependentType()) {
846
      return;
847
    }
848

849
    std::optional<SourceLocation> Location;
850

851
    // FIXME Add "unwrapping" for ArraySubscriptExpr,
852
    //  e.g. highlight `a` in `a[i]`
853
    // FIXME Handle dependent expression types
854
    if (auto *IC = dyn_cast<ImplicitCastExpr>(Arg))
855
      Arg = IC->getSubExprAsWritten();
856
    if (auto *UO = dyn_cast<UnaryOperator>(Arg)) {
857
      if (UO->getOpcode() == UO_AddrOf)
858
        Arg = UO->getSubExpr();
859
    }
860
    if (auto *DR = dyn_cast<DeclRefExpr>(Arg))
861
      Location = DR->getLocation();
862
    else if (auto *M = dyn_cast<MemberExpr>(Arg))
863
      Location = M->getMemberLoc();
864

865
    if (Location)
866
      H.addExtraModifier(*Location,
867
                         IsRef ? HighlightingModifier::UsedAsMutableReference
868
                               : HighlightingModifier::UsedAsMutablePointer);
869
  }
870

871
  void
872
  highlightMutableReferenceArguments(const FunctionDecl *FD,
873
                                     llvm::ArrayRef<const Expr *const> Args) {
874
    if (!FD)
875
      return;
876

877
    if (auto *ProtoType = FD->getType()->getAs<FunctionProtoType>()) {
878
      // Iterate over the types of the function parameters.
879
      // If any of them are non-const reference paramteres, add it as a
880
      // highlighting modifier to the corresponding expression
881
      for (size_t I = 0;
882
           I < std::min(size_t(ProtoType->getNumParams()), Args.size()); ++I) {
883
        highlightMutableReferenceArgument(ProtoType->getParamType(I), Args[I]);
884
      }
885
    }
886
  }
887

888
  bool VisitDecltypeTypeLoc(DecltypeTypeLoc L) {
889
    if (auto K = kindForType(L.getTypePtr(), H.getResolver())) {
890
      auto &Tok = H.addToken(L.getBeginLoc(), *K)
891
                      .addModifier(HighlightingModifier::Deduced);
892
      if (auto Mod = scopeModifier(L.getTypePtr()))
893
        Tok.addModifier(*Mod);
894
      if (isDefaultLibrary(L.getTypePtr()))
895
        Tok.addModifier(HighlightingModifier::DefaultLibrary);
896
    }
897
    return true;
898
  }
899

900
  bool VisitCXXDestructorDecl(CXXDestructorDecl *D) {
901
    if (auto *TI = D->getNameInfo().getNamedTypeInfo()) {
902
      SourceLocation Loc = TI->getTypeLoc().getBeginLoc();
903
      H.addExtraModifier(Loc, HighlightingModifier::ConstructorOrDestructor);
904
      H.addExtraModifier(Loc, HighlightingModifier::Declaration);
905
      if (D->isThisDeclarationADefinition())
906
        H.addExtraModifier(Loc, HighlightingModifier::Definition);
907
    }
908
    return true;
909
  }
910

911
  bool VisitCXXMemberCallExpr(CXXMemberCallExpr *CE) {
912
    // getMethodDecl can return nullptr with member pointers, e.g.
913
    // `(foo.*pointer_to_member_fun)(arg);`
914
    if (auto *D = CE->getMethodDecl()) {
915
      if (isa<CXXDestructorDecl>(D)) {
916
        if (auto *ME = dyn_cast<MemberExpr>(CE->getCallee())) {
917
          if (auto *TI = ME->getMemberNameInfo().getNamedTypeInfo()) {
918
            H.addExtraModifier(TI->getTypeLoc().getBeginLoc(),
919
                               HighlightingModifier::ConstructorOrDestructor);
920
          }
921
        }
922
      } else if (D->isOverloadedOperator()) {
923
        if (auto *ME = dyn_cast<MemberExpr>(CE->getCallee()))
924
          H.addToken(
925
               ME->getMemberNameInfo().getCXXOperatorNameRange().getBegin(),
926
               HighlightingKind::Operator)
927
              .addModifier(HighlightingModifier::UserDefined);
928
      }
929
    }
930
    return true;
931
  }
932

933
  bool VisitDeclaratorDecl(DeclaratorDecl *D) {
934
    for (unsigned i = 0; i < D->getNumTemplateParameterLists(); ++i) {
935
      if (auto *TPL = D->getTemplateParameterList(i))
936
        H.addAngleBracketTokens(TPL->getLAngleLoc(), TPL->getRAngleLoc());
937
    }
938
    auto *AT = D->getType()->getContainedAutoType();
939
    if (!AT)
940
      return true;
941
    auto K =
942
        kindForType(AT->getDeducedType().getTypePtrOrNull(), H.getResolver());
943
    if (!K)
944
      return true;
945
    auto *TSI = D->getTypeSourceInfo();
946
    if (!TSI)
947
      return true;
948
    SourceLocation StartLoc =
949
        TSI->getTypeLoc().getContainedAutoTypeLoc().getNameLoc();
950
    // The AutoType may not have a corresponding token, e.g. in the case of
951
    // init-captures. In this case, StartLoc overlaps with the location
952
    // of the decl itself, and producing a token for the type here would result
953
    // in both it and the token for the decl being dropped due to conflict.
954
    if (StartLoc == D->getLocation())
955
      return true;
956

957
    auto &Tok =
958
        H.addToken(StartLoc, *K).addModifier(HighlightingModifier::Deduced);
959
    const Type *Deduced = AT->getDeducedType().getTypePtrOrNull();
960
    if (auto Mod = scopeModifier(Deduced))
961
      Tok.addModifier(*Mod);
962
    if (isDefaultLibrary(Deduced))
963
      Tok.addModifier(HighlightingModifier::DefaultLibrary);
964
    return true;
965
  }
966

967
  // We handle objective-C selectors specially, because one reference can
968
  // cover several non-contiguous tokens.
969
  void highlightObjCSelector(const ArrayRef<SourceLocation> &Locs, bool Decl,
970
                             bool Def, bool Class, bool DefaultLibrary) {
971
    HighlightingKind Kind =
972
        Class ? HighlightingKind::StaticMethod : HighlightingKind::Method;
973
    for (SourceLocation Part : Locs) {
974
      auto &Tok =
975
          H.addToken(Part, Kind).addModifier(HighlightingModifier::ClassScope);
976
      if (Decl)
977
        Tok.addModifier(HighlightingModifier::Declaration);
978
      if (Def)
979
        Tok.addModifier(HighlightingModifier::Definition);
980
      if (Class)
981
        Tok.addModifier(HighlightingModifier::Static);
982
      if (DefaultLibrary)
983
        Tok.addModifier(HighlightingModifier::DefaultLibrary);
984
    }
985
  }
986

987
  bool VisitObjCMethodDecl(ObjCMethodDecl *OMD) {
988
    llvm::SmallVector<SourceLocation> Locs;
989
    OMD->getSelectorLocs(Locs);
990
    highlightObjCSelector(Locs, /*Decl=*/true,
991
                          OMD->isThisDeclarationADefinition(),
992
                          OMD->isClassMethod(), isDefaultLibrary(OMD));
993
    return true;
994
  }
995

996
  bool VisitObjCMessageExpr(ObjCMessageExpr *OME) {
997
    llvm::SmallVector<SourceLocation> Locs;
998
    OME->getSelectorLocs(Locs);
999
    bool DefaultLibrary = false;
1000
    if (ObjCMethodDecl *OMD = OME->getMethodDecl())
1001
      DefaultLibrary = isDefaultLibrary(OMD);
1002
    highlightObjCSelector(Locs, /*Decl=*/false, /*Def=*/false,
1003
                          OME->isClassMessage(), DefaultLibrary);
1004
    return true;
1005
  }
1006

1007
  // Objective-C allows you to use property syntax `self.prop` as sugar for
1008
  // `[self prop]` and `[self setProp:]` when there's no explicit `@property`
1009
  // for `prop` as well as for class properties. We treat this like a property
1010
  // even though semantically it's equivalent to a method expression.
1011
  void highlightObjCImplicitPropertyRef(const ObjCMethodDecl *OMD,
1012
                                        SourceLocation Loc) {
1013
    auto &Tok = H.addToken(Loc, HighlightingKind::Field)
1014
                    .addModifier(HighlightingModifier::ClassScope);
1015
    if (OMD->isClassMethod())
1016
      Tok.addModifier(HighlightingModifier::Static);
1017
    if (isDefaultLibrary(OMD))
1018
      Tok.addModifier(HighlightingModifier::DefaultLibrary);
1019
  }
1020

1021
  bool VisitObjCPropertyRefExpr(ObjCPropertyRefExpr *OPRE) {
1022
    // We need to handle implicit properties here since they will appear to
1023
    // reference `ObjCMethodDecl` via an implicit `ObjCMessageExpr`, so normal
1024
    // highlighting will not work.
1025
    if (!OPRE->isImplicitProperty())
1026
      return true;
1027
    // A single property expr can reference both a getter and setter, but we can
1028
    // only provide a single semantic token, so prefer the getter. In most cases
1029
    // the end result should be the same, although it's technically possible
1030
    // that the user defines a setter for a system SDK.
1031
    if (OPRE->isMessagingGetter()) {
1032
      highlightObjCImplicitPropertyRef(OPRE->getImplicitPropertyGetter(),
1033
                                       OPRE->getLocation());
1034
      return true;
1035
    }
1036
    if (OPRE->isMessagingSetter()) {
1037
      highlightObjCImplicitPropertyRef(OPRE->getImplicitPropertySetter(),
1038
                                       OPRE->getLocation());
1039
    }
1040
    return true;
1041
  }
1042

1043
  bool VisitOverloadExpr(OverloadExpr *E) {
1044
    H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1045
    if (!E->decls().empty())
1046
      return true; // handled by findExplicitReferences.
1047
    auto &Tok = H.addToken(E->getNameLoc(), HighlightingKind::Unknown)
1048
                    .addModifier(HighlightingModifier::DependentName);
1049
    if (llvm::isa<UnresolvedMemberExpr>(E))
1050
      Tok.addModifier(HighlightingModifier::ClassScope);
1051
    // other case is UnresolvedLookupExpr, scope is unknown.
1052
    return true;
1053
  }
1054

1055
  bool VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
1056
    H.addToken(E->getMemberNameInfo().getLoc(), HighlightingKind::Unknown)
1057
        .addModifier(HighlightingModifier::DependentName)
1058
        .addModifier(HighlightingModifier::ClassScope);
1059
    H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1060
    return true;
1061
  }
1062

1063
  bool VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *E) {
1064
    H.addToken(E->getNameInfo().getLoc(), HighlightingKind::Unknown)
1065
        .addModifier(HighlightingModifier::DependentName)
1066
        .addModifier(HighlightingModifier::ClassScope);
1067
    H.addAngleBracketTokens(E->getLAngleLoc(), E->getRAngleLoc());
1068
    return true;
1069
  }
1070

1071
  bool VisitAttr(Attr *A) {
1072
    switch (A->getKind()) {
1073
    case attr::Override:
1074
    case attr::Final:
1075
      H.addToken(A->getLocation(), HighlightingKind::Modifier);
1076
      break;
1077
    default:
1078
      break;
1079
    }
1080
    return true;
1081
  }
1082

1083
  bool VisitDependentNameTypeLoc(DependentNameTypeLoc L) {
1084
    H.addToken(L.getNameLoc(), HighlightingKind::Type)
1085
        .addModifier(HighlightingModifier::DependentName)
1086
        .addModifier(HighlightingModifier::ClassScope);
1087
    return true;
1088
  }
1089

1090
  bool VisitDependentTemplateSpecializationTypeLoc(
1091
      DependentTemplateSpecializationTypeLoc L) {
1092
    H.addToken(L.getTemplateNameLoc(), HighlightingKind::Type)
1093
        .addModifier(HighlightingModifier::DependentName)
1094
        .addModifier(HighlightingModifier::ClassScope);
1095
    H.addAngleBracketTokens(L.getLAngleLoc(), L.getRAngleLoc());
1096
    return true;
1097
  }
1098

1099
  bool TraverseTemplateArgumentLoc(TemplateArgumentLoc L) {
1100
    // Handle template template arguments only (other arguments are handled by
1101
    // their Expr, TypeLoc etc values).
1102
    if (L.getArgument().getKind() != TemplateArgument::Template &&
1103
        L.getArgument().getKind() != TemplateArgument::TemplateExpansion)
1104
      return RecursiveASTVisitor::TraverseTemplateArgumentLoc(L);
1105

1106
    TemplateName N = L.getArgument().getAsTemplateOrTemplatePattern();
1107
    switch (N.getKind()) {
1108
    case TemplateName::OverloadedTemplate:
1109
      // Template template params must always be class templates.
1110
      // Don't bother to try to work out the scope here.
1111
      H.addToken(L.getTemplateNameLoc(), HighlightingKind::Class);
1112
      break;
1113
    case TemplateName::DependentTemplate:
1114
    case TemplateName::AssumedTemplate:
1115
      H.addToken(L.getTemplateNameLoc(), HighlightingKind::Class)
1116
          .addModifier(HighlightingModifier::DependentName);
1117
      break;
1118
    case TemplateName::Template:
1119
    case TemplateName::QualifiedTemplate:
1120
    case TemplateName::SubstTemplateTemplateParm:
1121
    case TemplateName::SubstTemplateTemplateParmPack:
1122
    case TemplateName::UsingTemplate:
1123
      // Names that could be resolved to a TemplateDecl are handled elsewhere.
1124
      break;
1125
    }
1126
    return RecursiveASTVisitor::TraverseTemplateArgumentLoc(L);
1127
  }
1128

1129
  // findExplicitReferences will walk nested-name-specifiers and
1130
  // find anything that can be resolved to a Decl. However, non-leaf
1131
  // components of nested-name-specifiers which are dependent names
1132
  // (kind "Identifier") cannot be resolved to a decl, so we visit
1133
  // them here.
1134
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc Q) {
1135
    if (NestedNameSpecifier *NNS = Q.getNestedNameSpecifier()) {
1136
      if (NNS->getKind() == NestedNameSpecifier::Identifier)
1137
        H.addToken(Q.getLocalBeginLoc(), HighlightingKind::Type)
1138
            .addModifier(HighlightingModifier::DependentName)
1139
            .addModifier(HighlightingModifier::ClassScope);
1140
    }
1141
    return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(Q);
1142
  }
1143

1144
private:
1145
  HighlightingsBuilder &H;
1146
};
1147
} // namespace
1148

1149
std::vector<HighlightingToken>
1150
getSemanticHighlightings(ParsedAST &AST, bool IncludeInactiveRegionTokens) {
1151
  auto &C = AST.getASTContext();
1152
  HighlightingFilter Filter = HighlightingFilter::fromCurrentConfig();
1153
  if (!IncludeInactiveRegionTokens)
1154
    Filter.disableKind(HighlightingKind::InactiveCode);
1155
  // Add highlightings for AST nodes.
1156
  HighlightingsBuilder Builder(AST, Filter);
1157
  // Highlight 'decltype' and 'auto' as their underlying types.
1158
  CollectExtraHighlightings(Builder).TraverseAST(C);
1159
  // Highlight all decls and references coming from the AST.
1160
  findExplicitReferences(
1161
      C,
1162
      [&](ReferenceLoc R) {
1163
        for (const NamedDecl *Decl : R.Targets) {
1164
          if (!canHighlightName(Decl->getDeclName()))
1165
            continue;
1166
          auto Kind = kindForDecl(Decl, AST.getHeuristicResolver());
1167
          if (!Kind)
1168
            continue;
1169
          auto &Tok = Builder.addToken(R.NameLoc, *Kind);
1170

1171
          // The attribute tests don't want to look at the template.
1172
          if (auto *TD = dyn_cast<TemplateDecl>(Decl)) {
1173
            if (auto *Templated = TD->getTemplatedDecl())
1174
              Decl = Templated;
1175
          }
1176
          if (auto Mod = scopeModifier(Decl))
1177
            Tok.addModifier(*Mod);
1178
          if (isConst(Decl))
1179
            Tok.addModifier(HighlightingModifier::Readonly);
1180
          if (isStatic(Decl))
1181
            Tok.addModifier(HighlightingModifier::Static);
1182
          if (isAbstract(Decl))
1183
            Tok.addModifier(HighlightingModifier::Abstract);
1184
          if (isVirtual(Decl))
1185
            Tok.addModifier(HighlightingModifier::Virtual);
1186
          if (isDependent(Decl))
1187
            Tok.addModifier(HighlightingModifier::DependentName);
1188
          if (isDefaultLibrary(Decl))
1189
            Tok.addModifier(HighlightingModifier::DefaultLibrary);
1190
          if (Decl->isDeprecated())
1191
            Tok.addModifier(HighlightingModifier::Deprecated);
1192
          if (isa<CXXConstructorDecl>(Decl))
1193
            Tok.addModifier(HighlightingModifier::ConstructorOrDestructor);
1194
          if (R.IsDecl) {
1195
            // Do not treat an UnresolvedUsingValueDecl as a declaration.
1196
            // It's more common to think of it as a reference to the
1197
            // underlying declaration.
1198
            if (!isa<UnresolvedUsingValueDecl>(Decl))
1199
              Tok.addModifier(HighlightingModifier::Declaration);
1200
            if (isUniqueDefinition(Decl))
1201
              Tok.addModifier(HighlightingModifier::Definition);
1202
          }
1203
        }
1204
      },
1205
      AST.getHeuristicResolver());
1206
  // Add highlightings for macro references.
1207
  auto AddMacro = [&](const MacroOccurrence &M) {
1208
    auto &T = Builder.addToken(M.toRange(C.getSourceManager()),
1209
                               HighlightingKind::Macro);
1210
    T.addModifier(HighlightingModifier::GlobalScope);
1211
    if (M.IsDefinition)
1212
      T.addModifier(HighlightingModifier::Declaration);
1213
  };
1214
  for (const auto &SIDToRefs : AST.getMacros().MacroRefs)
1215
    for (const auto &M : SIDToRefs.second)
1216
      AddMacro(M);
1217
  for (const auto &M : AST.getMacros().UnknownMacros)
1218
    AddMacro(M);
1219

1220
  return std::move(Builder).collect(AST);
1221
}
1222

1223
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K) {
1224
  switch (K) {
1225
  case HighlightingKind::Variable:
1226
    return OS << "Variable";
1227
  case HighlightingKind::LocalVariable:
1228
    return OS << "LocalVariable";
1229
  case HighlightingKind::Parameter:
1230
    return OS << "Parameter";
1231
  case HighlightingKind::Function:
1232
    return OS << "Function";
1233
  case HighlightingKind::Method:
1234
    return OS << "Method";
1235
  case HighlightingKind::StaticMethod:
1236
    return OS << "StaticMethod";
1237
  case HighlightingKind::Field:
1238
    return OS << "Field";
1239
  case HighlightingKind::StaticField:
1240
    return OS << "StaticField";
1241
  case HighlightingKind::Class:
1242
    return OS << "Class";
1243
  case HighlightingKind::Interface:
1244
    return OS << "Interface";
1245
  case HighlightingKind::Enum:
1246
    return OS << "Enum";
1247
  case HighlightingKind::EnumConstant:
1248
    return OS << "EnumConstant";
1249
  case HighlightingKind::Typedef:
1250
    return OS << "Typedef";
1251
  case HighlightingKind::Type:
1252
    return OS << "Type";
1253
  case HighlightingKind::Unknown:
1254
    return OS << "Unknown";
1255
  case HighlightingKind::Namespace:
1256
    return OS << "Namespace";
1257
  case HighlightingKind::TemplateParameter:
1258
    return OS << "TemplateParameter";
1259
  case HighlightingKind::Concept:
1260
    return OS << "Concept";
1261
  case HighlightingKind::Primitive:
1262
    return OS << "Primitive";
1263
  case HighlightingKind::Macro:
1264
    return OS << "Macro";
1265
  case HighlightingKind::Modifier:
1266
    return OS << "Modifier";
1267
  case HighlightingKind::Operator:
1268
    return OS << "Operator";
1269
  case HighlightingKind::Bracket:
1270
    return OS << "Bracket";
1271
  case HighlightingKind::Label:
1272
    return OS << "Label";
1273
  case HighlightingKind::InactiveCode:
1274
    return OS << "InactiveCode";
1275
  }
1276
  llvm_unreachable("invalid HighlightingKind");
1277
}
1278
std::optional<HighlightingKind>
1279
highlightingKindFromString(llvm::StringRef Name) {
1280
  static llvm::StringMap<HighlightingKind> Lookup = {
1281
      {"Variable", HighlightingKind::Variable},
1282
      {"LocalVariable", HighlightingKind::LocalVariable},
1283
      {"Parameter", HighlightingKind::Parameter},
1284
      {"Function", HighlightingKind::Function},
1285
      {"Method", HighlightingKind::Method},
1286
      {"StaticMethod", HighlightingKind::StaticMethod},
1287
      {"Field", HighlightingKind::Field},
1288
      {"StaticField", HighlightingKind::StaticField},
1289
      {"Class", HighlightingKind::Class},
1290
      {"Interface", HighlightingKind::Interface},
1291
      {"Enum", HighlightingKind::Enum},
1292
      {"EnumConstant", HighlightingKind::EnumConstant},
1293
      {"Typedef", HighlightingKind::Typedef},
1294
      {"Type", HighlightingKind::Type},
1295
      {"Unknown", HighlightingKind::Unknown},
1296
      {"Namespace", HighlightingKind::Namespace},
1297
      {"TemplateParameter", HighlightingKind::TemplateParameter},
1298
      {"Concept", HighlightingKind::Concept},
1299
      {"Primitive", HighlightingKind::Primitive},
1300
      {"Macro", HighlightingKind::Macro},
1301
      {"Modifier", HighlightingKind::Modifier},
1302
      {"Operator", HighlightingKind::Operator},
1303
      {"Bracket", HighlightingKind::Bracket},
1304
      {"InactiveCode", HighlightingKind::InactiveCode},
1305
  };
1306

1307
  auto It = Lookup.find(Name);
1308
  return It != Lookup.end() ? std::make_optional(It->getValue()) : std::nullopt;
1309
}
1310
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingModifier K) {
1311
  switch (K) {
1312
  case HighlightingModifier::Declaration:
1313
    return OS << "decl"; // abbreviation for common case
1314
  case HighlightingModifier::Definition:
1315
    return OS << "def"; // abbrevation for common case
1316
  case HighlightingModifier::ConstructorOrDestructor:
1317
    return OS << "constrDestr";
1318
  default:
1319
    return OS << toSemanticTokenModifier(K);
1320
  }
1321
}
1322
std::optional<HighlightingModifier>
1323
highlightingModifierFromString(llvm::StringRef Name) {
1324
  static llvm::StringMap<HighlightingModifier> Lookup = {
1325
      {"Declaration", HighlightingModifier::Declaration},
1326
      {"Definition", HighlightingModifier::Definition},
1327
      {"Deprecated", HighlightingModifier::Deprecated},
1328
      {"Deduced", HighlightingModifier::Deduced},
1329
      {"Readonly", HighlightingModifier::Readonly},
1330
      {"Static", HighlightingModifier::Static},
1331
      {"Abstract", HighlightingModifier::Abstract},
1332
      {"Virtual", HighlightingModifier::Virtual},
1333
      {"DependentName", HighlightingModifier::DependentName},
1334
      {"DefaultLibrary", HighlightingModifier::DefaultLibrary},
1335
      {"UsedAsMutableReference", HighlightingModifier::UsedAsMutableReference},
1336
      {"UsedAsMutablePointer", HighlightingModifier::UsedAsMutablePointer},
1337
      {"ConstructorOrDestructor",
1338
       HighlightingModifier::ConstructorOrDestructor},
1339
      {"UserDefined", HighlightingModifier::UserDefined},
1340
      {"FunctionScope", HighlightingModifier::FunctionScope},
1341
      {"ClassScope", HighlightingModifier::ClassScope},
1342
      {"FileScope", HighlightingModifier::FileScope},
1343
      {"GlobalScope", HighlightingModifier::GlobalScope},
1344
  };
1345

1346
  auto It = Lookup.find(Name);
1347
  return It != Lookup.end() ? std::make_optional(It->getValue()) : std::nullopt;
1348
}
1349

1350
bool operator==(const HighlightingToken &L, const HighlightingToken &R) {
1351
  return std::tie(L.R, L.Kind, L.Modifiers) ==
1352
         std::tie(R.R, R.Kind, R.Modifiers);
1353
}
1354
bool operator<(const HighlightingToken &L, const HighlightingToken &R) {
1355
  return std::tie(L.R, L.Kind, L.Modifiers) <
1356
         std::tie(R.R, R.Kind, R.Modifiers);
1357
}
1358

1359
std::vector<SemanticToken>
1360
toSemanticTokens(llvm::ArrayRef<HighlightingToken> Tokens,
1361
                 llvm::StringRef Code) {
1362
  assert(llvm::is_sorted(Tokens));
1363
  std::vector<SemanticToken> Result;
1364
  // In case we split a HighlightingToken into multiple tokens (e.g. because it
1365
  // was spanning multiple lines), this tracks the last one. This prevents
1366
  // having a copy all the time.
1367
  HighlightingToken Scratch;
1368
  const HighlightingToken *Last = nullptr;
1369
  for (const HighlightingToken &Tok : Tokens) {
1370
    Result.emplace_back();
1371
    SemanticToken *Out = &Result.back();
1372
    // deltaStart/deltaLine are relative if possible.
1373
    if (Last) {
1374
      assert(Tok.R.start.line >= Last->R.end.line);
1375
      Out->deltaLine = Tok.R.start.line - Last->R.end.line;
1376
      if (Out->deltaLine == 0) {
1377
        assert(Tok.R.start.character >= Last->R.start.character);
1378
        Out->deltaStart = Tok.R.start.character - Last->R.start.character;
1379
      } else {
1380
        Out->deltaStart = Tok.R.start.character;
1381
      }
1382
    } else {
1383
      Out->deltaLine = Tok.R.start.line;
1384
      Out->deltaStart = Tok.R.start.character;
1385
    }
1386
    Out->tokenType = static_cast<unsigned>(Tok.Kind);
1387
    Out->tokenModifiers = Tok.Modifiers;
1388
    Last = &Tok;
1389

1390
    if (Tok.R.end.line == Tok.R.start.line) {
1391
      Out->length = Tok.R.end.character - Tok.R.start.character;
1392
    } else {
1393
      // If the token spans a line break, split it into multiple pieces for each
1394
      // line.
1395
      // This is slow, but multiline tokens are rare.
1396
      // FIXME: There's a client capability for supporting multiline tokens,
1397
      // respect that.
1398
      auto TokStartOffset = llvm::cantFail(positionToOffset(Code, Tok.R.start));
1399
      // Note that the loop doesn't cover the last line, which has a special
1400
      // length.
1401
      for (int I = Tok.R.start.line; I < Tok.R.end.line; ++I) {
1402
        auto LineEnd = Code.find('\n', TokStartOffset);
1403
        assert(LineEnd != Code.npos);
1404
        Out->length = LineEnd - TokStartOffset;
1405
        // Token continues on next line, right after the line break.
1406
        TokStartOffset = LineEnd + 1;
1407
        Result.emplace_back();
1408
        Out = &Result.back();
1409
        *Out = Result[Result.size() - 2];
1410
        // New token starts at the first column of the next line.
1411
        Out->deltaLine = 1;
1412
        Out->deltaStart = 0;
1413
      }
1414
      // This is the token on last line.
1415
      Out->length = Tok.R.end.character;
1416
      // Update the start location for last token, as that's used in the
1417
      // relative delta calculation for following tokens.
1418
      Scratch = *Last;
1419
      Scratch.R.start.line = Tok.R.end.line;
1420
      Scratch.R.start.character = 0;
1421
      Last = &Scratch;
1422
    }
1423
  }
1424
  return Result;
1425
}
1426
llvm::StringRef toSemanticTokenType(HighlightingKind Kind) {
1427
  switch (Kind) {
1428
  case HighlightingKind::Variable:
1429
  case HighlightingKind::LocalVariable:
1430
  case HighlightingKind::StaticField:
1431
    return "variable";
1432
  case HighlightingKind::Parameter:
1433
    return "parameter";
1434
  case HighlightingKind::Function:
1435
    return "function";
1436
  case HighlightingKind::Method:
1437
    return "method";
1438
  case HighlightingKind::StaticMethod:
1439
    // FIXME: better method with static modifier?
1440
    return "function";
1441
  case HighlightingKind::Field:
1442
    return "property";
1443
  case HighlightingKind::Class:
1444
    return "class";
1445
  case HighlightingKind::Interface:
1446
    return "interface";
1447
  case HighlightingKind::Enum:
1448
    return "enum";
1449
  case HighlightingKind::EnumConstant:
1450
    return "enumMember";
1451
  case HighlightingKind::Typedef:
1452
  case HighlightingKind::Type:
1453
    return "type";
1454
  case HighlightingKind::Unknown:
1455
    return "unknown"; // nonstandard
1456
  case HighlightingKind::Namespace:
1457
    return "namespace";
1458
  case HighlightingKind::TemplateParameter:
1459
    return "typeParameter";
1460
  case HighlightingKind::Concept:
1461
    return "concept"; // nonstandard
1462
  case HighlightingKind::Primitive:
1463
    return "type";
1464
  case HighlightingKind::Macro:
1465
    return "macro";
1466
  case HighlightingKind::Modifier:
1467
    return "modifier";
1468
  case HighlightingKind::Operator:
1469
    return "operator";
1470
  case HighlightingKind::Bracket:
1471
    return "bracket";
1472
  case HighlightingKind::Label:
1473
    return "label";
1474
  case HighlightingKind::InactiveCode:
1475
    return "comment";
1476
  }
1477
  llvm_unreachable("unhandled HighlightingKind");
1478
}
1479

1480
llvm::StringRef toSemanticTokenModifier(HighlightingModifier Modifier) {
1481
  switch (Modifier) {
1482
  case HighlightingModifier::Declaration:
1483
    return "declaration";
1484
  case HighlightingModifier::Definition:
1485
    return "definition";
1486
  case HighlightingModifier::Deprecated:
1487
    return "deprecated";
1488
  case HighlightingModifier::Readonly:
1489
    return "readonly";
1490
  case HighlightingModifier::Static:
1491
    return "static";
1492
  case HighlightingModifier::Deduced:
1493
    return "deduced"; // nonstandard
1494
  case HighlightingModifier::Abstract:
1495
    return "abstract";
1496
  case HighlightingModifier::Virtual:
1497
    return "virtual";
1498
  case HighlightingModifier::DependentName:
1499
    return "dependentName"; // nonstandard
1500
  case HighlightingModifier::DefaultLibrary:
1501
    return "defaultLibrary";
1502
  case HighlightingModifier::UsedAsMutableReference:
1503
    return "usedAsMutableReference"; // nonstandard
1504
  case HighlightingModifier::UsedAsMutablePointer:
1505
    return "usedAsMutablePointer"; // nonstandard
1506
  case HighlightingModifier::ConstructorOrDestructor:
1507
    return "constructorOrDestructor"; // nonstandard
1508
  case HighlightingModifier::UserDefined:
1509
    return "userDefined"; // nonstandard
1510
  case HighlightingModifier::FunctionScope:
1511
    return "functionScope"; // nonstandard
1512
  case HighlightingModifier::ClassScope:
1513
    return "classScope"; // nonstandard
1514
  case HighlightingModifier::FileScope:
1515
    return "fileScope"; // nonstandard
1516
  case HighlightingModifier::GlobalScope:
1517
    return "globalScope"; // nonstandard
1518
  }
1519
  llvm_unreachable("unhandled HighlightingModifier");
1520
}
1521

1522
std::vector<SemanticTokensEdit>
1523
diffTokens(llvm::ArrayRef<SemanticToken> Old,
1524
           llvm::ArrayRef<SemanticToken> New) {
1525
  // For now, just replace everything from the first-last modification.
1526
  // FIXME: use a real diff instead, this is bad with include-insertion.
1527

1528
  unsigned Offset = 0;
1529
  while (!Old.empty() && !New.empty() && Old.front() == New.front()) {
1530
    ++Offset;
1531
    Old = Old.drop_front();
1532
    New = New.drop_front();
1533
  }
1534
  while (!Old.empty() && !New.empty() && Old.back() == New.back()) {
1535
    Old = Old.drop_back();
1536
    New = New.drop_back();
1537
  }
1538

1539
  if (Old.empty() && New.empty())
1540
    return {};
1541
  SemanticTokensEdit Edit;
1542
  Edit.startToken = Offset;
1543
  Edit.deleteTokens = Old.size();
1544
  Edit.tokens = New;
1545
  return {std::move(Edit)};
1546
}
1547

1548
std::vector<Range> getInactiveRegions(ParsedAST &AST) {
1549
  std::vector<Range> SkippedRanges(std::move(AST.getMacros().SkippedRanges));
1550
  const auto &SM = AST.getSourceManager();
1551
  StringRef MainCode = SM.getBufferOrFake(SM.getMainFileID()).getBuffer();
1552
  std::vector<Range> InactiveRegions;
1553
  for (const Range &Skipped : SkippedRanges) {
1554
    Range Inactive = Skipped;
1555
    // Sometimes, SkippedRanges contains a range ending at position 0
1556
    // of a line. Clients that apply whole-line styles will treat that
1557
    // line as inactive which is not desirable, so adjust the ending
1558
    // position to be the end of the previous line.
1559
    if (Inactive.end.character == 0 && Inactive.end.line > 0) {
1560
      --Inactive.end.line;
1561
    }
1562
    // Exclude the directive lines themselves from the range.
1563
    if (Inactive.end.line >= Inactive.start.line + 2) {
1564
      ++Inactive.start.line;
1565
      --Inactive.end.line;
1566
    } else {
1567
      // range would be empty, e.g. #endif on next line after #ifdef
1568
      continue;
1569
    }
1570
    // Since we've adjusted the ending line, we need to recompute the
1571
    // column to reflect the end of that line.
1572
    if (auto EndOfLine = endOfLine(MainCode, Inactive.end.line)) {
1573
      Inactive.end = *EndOfLine;
1574
    } else {
1575
      elog("Failed to determine end of line: {0}", EndOfLine.takeError());
1576
      continue;
1577
    }
1578
    InactiveRegions.push_back(Inactive);
1579
  }
1580
  return InactiveRegions;
1581
}
1582

1583
} // namespace clangd
1584
} // namespace clang
1585