• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 "FindTarget.h"
11 #include "ParsedAST.h"
12 #include "Protocol.h"
13 #include "SourceCode.h"
14 #include "support/Logger.h"
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/DeclarationName.h"
19 #include "clang/AST/ExprCXX.h"
20 #include "clang/AST/RecursiveASTVisitor.h"
21 #include "clang/AST/Type.h"
22 #include "clang/AST/TypeLoc.h"
23 #include "clang/Basic/LangOptions.h"
24 #include "clang/Basic/SourceLocation.h"
25 #include "clang/Basic/SourceManager.h"
26 #include "clang/Tooling/Syntax/Tokens.h"
27 #include "llvm/ADT/None.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/Support/Base64.h"
31 #include "llvm/Support/Casting.h"
32 #include <algorithm>
33 
34 namespace clang {
35 namespace clangd {
36 namespace {
37 
38 /// Some names are not written in the source code and cannot be highlighted,
39 /// e.g. anonymous classes. This function detects those cases.
canHighlightName(DeclarationName Name)40 bool canHighlightName(DeclarationName Name) {
41   if (Name.getNameKind() == DeclarationName::CXXConstructorName ||
42       Name.getNameKind() == DeclarationName::CXXUsingDirective)
43     return true;
44   auto *II = Name.getAsIdentifierInfo();
45   return II && !II->getName().empty();
46 }
47 
48 llvm::Optional<HighlightingKind> kindForType(const Type *TP);
kindForDecl(const NamedDecl * D)49 llvm::Optional<HighlightingKind> kindForDecl(const NamedDecl *D) {
50   if (auto *USD = dyn_cast<UsingShadowDecl>(D)) {
51     if (auto *Target = USD->getTargetDecl())
52       D = Target;
53   }
54   if (auto *TD = dyn_cast<TemplateDecl>(D)) {
55     if (auto *Templated = TD->getTemplatedDecl())
56       D = Templated;
57   }
58   if (auto *TD = dyn_cast<TypedefNameDecl>(D)) {
59     // We try to highlight typedefs as their underlying type.
60     if (auto K = kindForType(TD->getUnderlyingType().getTypePtrOrNull()))
61       return K;
62     // And fallback to a generic kind if this fails.
63     return HighlightingKind::Typedef;
64   }
65   // We highlight class decls, constructor decls and destructor decls as
66   // `Class` type. The destructor decls are handled in `VisitTagTypeLoc` (we
67   // will visit a TypeLoc where the underlying Type is a CXXRecordDecl).
68   if (auto *RD = llvm::dyn_cast<RecordDecl>(D)) {
69     // We don't want to highlight lambdas like classes.
70     if (RD->isLambda())
71       return llvm::None;
72     return HighlightingKind::Class;
73   }
74   if (isa<ClassTemplateDecl>(D) || isa<RecordDecl>(D) ||
75       isa<CXXConstructorDecl>(D))
76     return HighlightingKind::Class;
77   if (auto *MD = dyn_cast<CXXMethodDecl>(D))
78     return MD->isStatic() ? HighlightingKind::StaticMethod
79                           : HighlightingKind::Method;
80   if (isa<FieldDecl>(D))
81     return HighlightingKind::Field;
82   if (isa<EnumDecl>(D))
83     return HighlightingKind::Enum;
84   if (isa<EnumConstantDecl>(D))
85     return HighlightingKind::EnumConstant;
86   if (isa<ParmVarDecl>(D))
87     return HighlightingKind::Parameter;
88   if (auto *VD = dyn_cast<VarDecl>(D))
89     return VD->isStaticDataMember()
90                ? HighlightingKind::StaticField
91                : VD->isLocalVarDecl() ? HighlightingKind::LocalVariable
92                                       : HighlightingKind::Variable;
93   if (const auto *BD = dyn_cast<BindingDecl>(D))
94     return BD->getDeclContext()->isFunctionOrMethod()
95                ? HighlightingKind::LocalVariable
96                : HighlightingKind::Variable;
97   if (isa<FunctionDecl>(D))
98     return HighlightingKind::Function;
99   if (isa<NamespaceDecl>(D) || isa<NamespaceAliasDecl>(D) ||
100       isa<UsingDirectiveDecl>(D))
101     return HighlightingKind::Namespace;
102   if (isa<TemplateTemplateParmDecl>(D) || isa<TemplateTypeParmDecl>(D) ||
103       isa<NonTypeTemplateParmDecl>(D))
104     return HighlightingKind::TemplateParameter;
105   if (isa<ConceptDecl>(D))
106     return HighlightingKind::Concept;
107   return llvm::None;
108 }
kindForType(const Type * TP)109 llvm::Optional<HighlightingKind> kindForType(const Type *TP) {
110   if (!TP)
111     return llvm::None;
112   if (TP->isBuiltinType()) // Builtins are special, they do not have decls.
113     return HighlightingKind::Primitive;
114   if (auto *TD = dyn_cast<TemplateTypeParmType>(TP))
115     return kindForDecl(TD->getDecl());
116   if (auto *TD = TP->getAsTagDecl())
117     return kindForDecl(TD);
118   return llvm::None;
119 }
120 
kindForReference(const ReferenceLoc & R)121 llvm::Optional<HighlightingKind> kindForReference(const ReferenceLoc &R) {
122   llvm::Optional<HighlightingKind> Result;
123   for (const NamedDecl *Decl : R.Targets) {
124     if (!canHighlightName(Decl->getDeclName()))
125       return llvm::None;
126     auto Kind = kindForDecl(Decl);
127     if (!Kind || (Result && Kind != Result))
128       return llvm::None;
129     Result = Kind;
130   }
131   return Result;
132 }
133 
134 // For a macro usage `DUMP(foo)`, we want:
135 //  - DUMP --> "macro"
136 //  - foo --> "variable".
getHighlightableSpellingToken(SourceLocation L,const SourceManager & SM)137 SourceLocation getHighlightableSpellingToken(SourceLocation L,
138                                              const SourceManager &SM) {
139   if (L.isFileID())
140     return SM.isWrittenInMainFile(L) ? L : SourceLocation{};
141   // Tokens expanded from the macro body contribute no highlightings.
142   if (!SM.isMacroArgExpansion(L))
143     return {};
144   // Tokens expanded from macro args are potentially highlightable.
145   return getHighlightableSpellingToken(SM.getImmediateSpellingLoc(L), SM);
146 }
147 
evaluateHighlightPriority(HighlightingKind Kind)148 unsigned evaluateHighlightPriority(HighlightingKind Kind) {
149   enum HighlightPriority { Dependent = 0, Resolved = 1 };
150   return Kind == HighlightingKind::DependentType ||
151                  Kind == HighlightingKind::DependentName
152              ? Dependent
153              : Resolved;
154 }
155 
156 // Sometimes we get conflicts between findExplicitReferences() returning
157 // a heuristic result for a dependent name (e.g. Method) and
158 // CollectExtraHighlighting returning a fallback dependent highlighting (e.g.
159 // DependentName). In such cases, resolve the conflict in favour of the
160 // resolved (non-dependent) highlighting.
161 // With macros we can get other conflicts (if a spelled token has multiple
162 // expansions with different token types) which we can't usefully resolve.
163 llvm::Optional<HighlightingToken>
resolveConflict(ArrayRef<HighlightingToken> Tokens)164 resolveConflict(ArrayRef<HighlightingToken> Tokens) {
165   if (Tokens.size() == 1)
166     return Tokens[0];
167 
168   if (Tokens.size() != 2)
169     return llvm::None;
170 
171   unsigned Priority1 = evaluateHighlightPriority(Tokens[0].Kind);
172   unsigned Priority2 = evaluateHighlightPriority(Tokens[1].Kind);
173   if (Priority1 == Priority2)
174     return llvm::None;
175   return Priority1 > Priority2 ? Tokens[0] : Tokens[1];
176 }
177 
178 /// Consumes source locations and maps them to text ranges for highlightings.
179 class HighlightingsBuilder {
180 public:
HighlightingsBuilder(const ParsedAST & AST)181   HighlightingsBuilder(const ParsedAST &AST)
182       : TB(AST.getTokens()), SourceMgr(AST.getSourceManager()),
183         LangOpts(AST.getLangOpts()) {}
184 
addToken(HighlightingToken T)185   void addToken(HighlightingToken T) { Tokens.push_back(T); }
186 
addToken(SourceLocation Loc,HighlightingKind Kind)187   void addToken(SourceLocation Loc, HighlightingKind Kind) {
188     Loc = getHighlightableSpellingToken(Loc, SourceMgr);
189     if (Loc.isInvalid())
190       return;
191     const auto *Tok = TB.spelledTokenAt(Loc);
192     assert(Tok);
193 
194     auto Range = halfOpenToRange(SourceMgr,
195                                  Tok->range(SourceMgr).toCharRange(SourceMgr));
196     Tokens.push_back(HighlightingToken{Kind, std::move(Range)});
197   }
198 
collect(ParsedAST & AST)199   std::vector<HighlightingToken> collect(ParsedAST &AST) && {
200     // Initializer lists can give duplicates of tokens, therefore all tokens
201     // must be deduplicated.
202     llvm::sort(Tokens);
203     auto Last = std::unique(Tokens.begin(), Tokens.end());
204     Tokens.erase(Last, Tokens.end());
205 
206     // Macros can give tokens that have the same source range but conflicting
207     // kinds. In this case all tokens sharing this source range should be
208     // removed.
209     std::vector<HighlightingToken> NonConflicting;
210     NonConflicting.reserve(Tokens.size());
211     for (ArrayRef<HighlightingToken> TokRef = Tokens; !TokRef.empty();) {
212       ArrayRef<HighlightingToken> Conflicting =
213           TokRef.take_while([&](const HighlightingToken &T) {
214             // TokRef is guaranteed at least one element here because otherwise
215             // this predicate would never fire.
216             return T.R == TokRef.front().R;
217           });
218       if (auto Resolved = resolveConflict(Conflicting))
219         NonConflicting.push_back(*Resolved);
220       // TokRef[Conflicting.size()] is the next token with a different range (or
221       // the end of the Tokens).
222       TokRef = TokRef.drop_front(Conflicting.size());
223     }
224     const auto &SM = AST.getSourceManager();
225     StringRef MainCode = SM.getBufferOrFake(SM.getMainFileID()).getBuffer();
226 
227     // Merge token stream with "inactive line" markers.
228     std::vector<HighlightingToken> WithInactiveLines;
229     auto SortedSkippedRanges = AST.getMacros().SkippedRanges;
230     llvm::sort(SortedSkippedRanges);
231     auto It = NonConflicting.begin();
232     for (const Range &R : SortedSkippedRanges) {
233       // Create one token for each line in the skipped range, so it works
234       // with line-based diffing.
235       assert(R.start.line <= R.end.line);
236       for (int Line = R.start.line; Line <= R.end.line; ++Line) {
237         // If the end of the inactive range is at the beginning
238         // of a line, that line is not inactive.
239         if (Line == R.end.line && R.end.character == 0)
240           continue;
241         // Copy tokens before the inactive line
242         for (; It != NonConflicting.end() && It->R.start.line < Line; ++It)
243           WithInactiveLines.push_back(std::move(*It));
244         // Add a token for the inactive line itself.
245         auto StartOfLine = positionToOffset(MainCode, Position{Line, 0});
246         if (StartOfLine) {
247           StringRef LineText =
248               MainCode.drop_front(*StartOfLine).take_until([](char C) {
249                 return C == '\n';
250               });
251           WithInactiveLines.push_back(
252               {HighlightingKind::InactiveCode,
253                {Position{Line, 0},
254                 Position{Line, static_cast<int>(lspLength(LineText))}}});
255         } else {
256           elog("Failed to convert position to offset: {0}",
257                StartOfLine.takeError());
258         }
259 
260         // Skip any other tokens on the inactive line. e.g.
261         // `#ifndef Foo` is considered as part of an inactive region when Foo is
262         // defined, and there is a Foo macro token.
263         // FIXME: we should reduce the scope of the inactive region to not
264         // include the directive itself.
265         while (It != NonConflicting.end() && It->R.start.line == Line)
266           ++It;
267       }
268     }
269     // Copy tokens after the last inactive line
270     for (; It != NonConflicting.end(); ++It)
271       WithInactiveLines.push_back(std::move(*It));
272     return WithInactiveLines;
273   }
274 
275 private:
276   const syntax::TokenBuffer &TB;
277   const SourceManager &SourceMgr;
278   const LangOptions &LangOpts;
279   std::vector<HighlightingToken> Tokens;
280 };
281 
282 /// Produces highlightings, which are not captured by findExplicitReferences,
283 /// e.g. highlights dependent names and 'auto' as the underlying type.
284 class CollectExtraHighlightings
285     : public RecursiveASTVisitor<CollectExtraHighlightings> {
286 public:
CollectExtraHighlightings(HighlightingsBuilder & H)287   CollectExtraHighlightings(HighlightingsBuilder &H) : H(H) {}
288 
VisitDecltypeTypeLoc(DecltypeTypeLoc L)289   bool VisitDecltypeTypeLoc(DecltypeTypeLoc L) {
290     if (auto K = kindForType(L.getTypePtr()))
291       H.addToken(L.getBeginLoc(), *K);
292     return true;
293   }
294 
VisitDeclaratorDecl(DeclaratorDecl * D)295   bool VisitDeclaratorDecl(DeclaratorDecl *D) {
296     auto *AT = D->getType()->getContainedAutoType();
297     if (!AT)
298       return true;
299     if (auto K = kindForType(AT->getDeducedType().getTypePtrOrNull()))
300       H.addToken(D->getTypeSpecStartLoc(), *K);
301     return true;
302   }
303 
VisitOverloadExpr(OverloadExpr * E)304   bool VisitOverloadExpr(OverloadExpr *E) {
305     if (!E->decls().empty())
306       return true; // handled by findExplicitReferences.
307     H.addToken(E->getNameLoc(), HighlightingKind::DependentName);
308     return true;
309   }
310 
VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr * E)311   bool VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
312     H.addToken(E->getMemberNameInfo().getLoc(),
313                HighlightingKind::DependentName);
314     return true;
315   }
316 
VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr * E)317   bool VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *E) {
318     H.addToken(E->getNameInfo().getLoc(), HighlightingKind::DependentName);
319     return true;
320   }
321 
VisitDependentNameTypeLoc(DependentNameTypeLoc L)322   bool VisitDependentNameTypeLoc(DependentNameTypeLoc L) {
323     H.addToken(L.getNameLoc(), HighlightingKind::DependentType);
324     return true;
325   }
326 
VisitDependentTemplateSpecializationTypeLoc(DependentTemplateSpecializationTypeLoc L)327   bool VisitDependentTemplateSpecializationTypeLoc(
328       DependentTemplateSpecializationTypeLoc L) {
329     H.addToken(L.getTemplateNameLoc(), HighlightingKind::DependentType);
330     return true;
331   }
332 
TraverseTemplateArgumentLoc(TemplateArgumentLoc L)333   bool TraverseTemplateArgumentLoc(TemplateArgumentLoc L) {
334     switch (L.getArgument().getKind()) {
335     case TemplateArgument::Template:
336     case TemplateArgument::TemplateExpansion:
337       H.addToken(L.getTemplateNameLoc(), HighlightingKind::DependentType);
338       break;
339     default:
340       break;
341     }
342     return RecursiveASTVisitor::TraverseTemplateArgumentLoc(L);
343   }
344 
345   // findExplicitReferences will walk nested-name-specifiers and
346   // find anything that can be resolved to a Decl. However, non-leaf
347   // components of nested-name-specifiers which are dependent names
348   // (kind "Identifier") cannot be resolved to a decl, so we visit
349   // them here.
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc Q)350   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc Q) {
351     if (NestedNameSpecifier *NNS = Q.getNestedNameSpecifier()) {
352       if (NNS->getKind() == NestedNameSpecifier::Identifier)
353         H.addToken(Q.getLocalBeginLoc(), HighlightingKind::DependentType);
354     }
355     return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(Q);
356   }
357 
358 private:
359   HighlightingsBuilder &H;
360 };
361 
write32be(uint32_t I,llvm::raw_ostream & OS)362 void write32be(uint32_t I, llvm::raw_ostream &OS) {
363   std::array<char, 4> Buf;
364   llvm::support::endian::write32be(Buf.data(), I);
365   OS.write(Buf.data(), Buf.size());
366 }
367 
write16be(uint16_t I,llvm::raw_ostream & OS)368 void write16be(uint16_t I, llvm::raw_ostream &OS) {
369   std::array<char, 2> Buf;
370   llvm::support::endian::write16be(Buf.data(), I);
371   OS.write(Buf.data(), Buf.size());
372 }
373 
374 // Get the highlightings on \c Line where the first entry of line is at \c
375 // StartLineIt. If it is not at \c StartLineIt an empty vector is returned.
376 ArrayRef<HighlightingToken>
takeLine(ArrayRef<HighlightingToken> AllTokens,ArrayRef<HighlightingToken>::iterator StartLineIt,int Line)377 takeLine(ArrayRef<HighlightingToken> AllTokens,
378          ArrayRef<HighlightingToken>::iterator StartLineIt, int Line) {
379   return ArrayRef<HighlightingToken>(StartLineIt, AllTokens.end())
380       .take_while([Line](const HighlightingToken &Token) {
381         return Token.R.start.line == Line;
382       });
383 }
384 } // namespace
385 
getSemanticHighlightings(ParsedAST & AST)386 std::vector<HighlightingToken> getSemanticHighlightings(ParsedAST &AST) {
387   auto &C = AST.getASTContext();
388   // Add highlightings for AST nodes.
389   HighlightingsBuilder Builder(AST);
390   // Highlight 'decltype' and 'auto' as their underlying types.
391   CollectExtraHighlightings(Builder).TraverseAST(C);
392   // Highlight all decls and references coming from the AST.
393   findExplicitReferences(C, [&](ReferenceLoc R) {
394     if (auto Kind = kindForReference(R))
395       Builder.addToken(R.NameLoc, *Kind);
396   });
397   // Add highlightings for macro references.
398   for (const auto &SIDToRefs : AST.getMacros().MacroRefs) {
399     for (const auto &M : SIDToRefs.second)
400       Builder.addToken({HighlightingKind::Macro, M});
401   }
402   for (const auto &M : AST.getMacros().UnknownMacros)
403     Builder.addToken({HighlightingKind::Macro, M});
404 
405   return std::move(Builder).collect(AST);
406 }
407 
operator <<(llvm::raw_ostream & OS,HighlightingKind K)408 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K) {
409   switch (K) {
410   case HighlightingKind::Variable:
411     return OS << "Variable";
412   case HighlightingKind::LocalVariable:
413     return OS << "LocalVariable";
414   case HighlightingKind::Parameter:
415     return OS << "Parameter";
416   case HighlightingKind::Function:
417     return OS << "Function";
418   case HighlightingKind::Method:
419     return OS << "Method";
420   case HighlightingKind::StaticMethod:
421     return OS << "StaticMethod";
422   case HighlightingKind::Field:
423     return OS << "Field";
424   case HighlightingKind::StaticField:
425     return OS << "StaticField";
426   case HighlightingKind::Class:
427     return OS << "Class";
428   case HighlightingKind::Enum:
429     return OS << "Enum";
430   case HighlightingKind::EnumConstant:
431     return OS << "EnumConstant";
432   case HighlightingKind::Typedef:
433     return OS << "Typedef";
434   case HighlightingKind::DependentType:
435     return OS << "DependentType";
436   case HighlightingKind::DependentName:
437     return OS << "DependentName";
438   case HighlightingKind::Namespace:
439     return OS << "Namespace";
440   case HighlightingKind::TemplateParameter:
441     return OS << "TemplateParameter";
442   case HighlightingKind::Concept:
443     return OS << "Concept";
444   case HighlightingKind::Primitive:
445     return OS << "Primitive";
446   case HighlightingKind::Macro:
447     return OS << "Macro";
448   case HighlightingKind::InactiveCode:
449     return OS << "InactiveCode";
450   }
451   llvm_unreachable("invalid HighlightingKind");
452 }
453 
454 std::vector<LineHighlightings>
diffHighlightings(ArrayRef<HighlightingToken> New,ArrayRef<HighlightingToken> Old)455 diffHighlightings(ArrayRef<HighlightingToken> New,
456                   ArrayRef<HighlightingToken> Old) {
457   assert(std::is_sorted(New.begin(), New.end()) &&
458          "New must be a sorted vector");
459   assert(std::is_sorted(Old.begin(), Old.end()) &&
460          "Old must be a sorted vector");
461 
462   // FIXME: There's an edge case when tokens span multiple lines. If the first
463   // token on the line started on a line above the current one and the rest of
464   // the line is the equal to the previous one than we will remove all
465   // highlights but the ones for the token spanning multiple lines. This means
466   // that when we get into the LSP layer the only highlights that will be
467   // visible are the ones for the token spanning multiple lines.
468   // Example:
469   // EndOfMultilineToken  Token Token Token
470   // If "Token Token Token" don't differ from previously the line is
471   // incorrectly removed. Suggestion to fix is to separate any multiline tokens
472   // into one token for every line it covers. This requires reading from the
473   // file buffer to figure out the length of each line though.
474   std::vector<LineHighlightings> DiffedLines;
475   // ArrayRefs to the current line in the highlightings.
476   ArrayRef<HighlightingToken> NewLine(New.begin(),
477                                       /*length*/ static_cast<size_t>(0));
478   ArrayRef<HighlightingToken> OldLine(Old.begin(),
479                                       /*length*/ static_cast<size_t>(0));
480   auto NewEnd = New.end();
481   auto OldEnd = Old.end();
482   auto NextLineNumber = [&]() {
483     int NextNew = NewLine.end() != NewEnd ? NewLine.end()->R.start.line
484                                           : std::numeric_limits<int>::max();
485     int NextOld = OldLine.end() != OldEnd ? OldLine.end()->R.start.line
486                                           : std::numeric_limits<int>::max();
487     return std::min(NextNew, NextOld);
488   };
489 
490   for (int LineNumber = 0; NewLine.end() < NewEnd || OldLine.end() < OldEnd;
491        LineNumber = NextLineNumber()) {
492     NewLine = takeLine(New, NewLine.end(), LineNumber);
493     OldLine = takeLine(Old, OldLine.end(), LineNumber);
494     if (NewLine != OldLine) {
495       DiffedLines.push_back({LineNumber, NewLine, /*IsInactive=*/false});
496 
497       // Turn a HighlightingKind::InactiveCode token into the IsInactive flag.
498       auto &AddedLine = DiffedLines.back();
499       llvm::erase_if(AddedLine.Tokens, [&](const HighlightingToken &T) {
500         if (T.Kind == HighlightingKind::InactiveCode) {
501           AddedLine.IsInactive = true;
502           return true;
503         }
504         return false;
505       });
506     }
507   }
508 
509   return DiffedLines;
510 }
511 
operator ==(const HighlightingToken & L,const HighlightingToken & R)512 bool operator==(const HighlightingToken &L, const HighlightingToken &R) {
513   return std::tie(L.R, L.Kind) == std::tie(R.R, R.Kind);
514 }
operator <(const HighlightingToken & L,const HighlightingToken & R)515 bool operator<(const HighlightingToken &L, const HighlightingToken &R) {
516   return std::tie(L.R, L.Kind) < std::tie(R.R, R.Kind);
517 }
operator ==(const LineHighlightings & L,const LineHighlightings & R)518 bool operator==(const LineHighlightings &L, const LineHighlightings &R) {
519   return std::tie(L.Line, L.Tokens) == std::tie(R.Line, R.Tokens);
520 }
521 
522 std::vector<SemanticToken>
toSemanticTokens(llvm::ArrayRef<HighlightingToken> Tokens)523 toSemanticTokens(llvm::ArrayRef<HighlightingToken> Tokens) {
524   assert(std::is_sorted(Tokens.begin(), Tokens.end()));
525   std::vector<SemanticToken> Result;
526   const HighlightingToken *Last = nullptr;
527   for (const HighlightingToken &Tok : Tokens) {
528     Result.emplace_back();
529     SemanticToken &Out = Result.back();
530     // deltaStart/deltaLine are relative if possible.
531     if (Last) {
532       assert(Tok.R.start.line >= Last->R.start.line);
533       Out.deltaLine = Tok.R.start.line - Last->R.start.line;
534       if (Out.deltaLine == 0) {
535         assert(Tok.R.start.character >= Last->R.start.character);
536         Out.deltaStart = Tok.R.start.character - Last->R.start.character;
537       } else {
538         Out.deltaStart = Tok.R.start.character;
539       }
540     } else {
541       Out.deltaLine = Tok.R.start.line;
542       Out.deltaStart = Tok.R.start.character;
543     }
544     assert(Tok.R.end.line == Tok.R.start.line);
545     Out.length = Tok.R.end.character - Tok.R.start.character;
546     Out.tokenType = static_cast<unsigned>(Tok.Kind);
547 
548     Last = &Tok;
549   }
550   return Result;
551 }
toSemanticTokenType(HighlightingKind Kind)552 llvm::StringRef toSemanticTokenType(HighlightingKind Kind) {
553   switch (Kind) {
554   case HighlightingKind::Variable:
555   case HighlightingKind::LocalVariable:
556   case HighlightingKind::StaticField:
557     return "variable";
558   case HighlightingKind::Parameter:
559     return "parameter";
560   case HighlightingKind::Function:
561     return "function";
562   case HighlightingKind::Method:
563     return "method";
564   case HighlightingKind::StaticMethod:
565     // FIXME: better method with static modifier?
566     return "function";
567   case HighlightingKind::Field:
568     return "property";
569   case HighlightingKind::Class:
570     return "class";
571   case HighlightingKind::Enum:
572     return "enum";
573   case HighlightingKind::EnumConstant:
574     return "enumConstant"; // nonstandard
575   case HighlightingKind::Typedef:
576     return "type";
577   case HighlightingKind::DependentType:
578     return "dependent"; // nonstandard
579   case HighlightingKind::DependentName:
580     return "dependent"; // nonstandard
581   case HighlightingKind::Namespace:
582     return "namespace";
583   case HighlightingKind::TemplateParameter:
584     return "typeParameter";
585   case HighlightingKind::Concept:
586     return "concept"; // nonstandard
587   case HighlightingKind::Primitive:
588     return "type";
589   case HighlightingKind::Macro:
590     return "macro";
591   case HighlightingKind::InactiveCode:
592     return "comment";
593   }
594   llvm_unreachable("unhandled HighlightingKind");
595 }
596 
597 std::vector<TheiaSemanticHighlightingInformation>
toTheiaSemanticHighlightingInformation(llvm::ArrayRef<LineHighlightings> Tokens)598 toTheiaSemanticHighlightingInformation(
599     llvm::ArrayRef<LineHighlightings> Tokens) {
600   if (Tokens.size() == 0)
601     return {};
602 
603   // FIXME: Tokens might be multiple lines long (block comments) in this case
604   // this needs to add multiple lines for those tokens.
605   std::vector<TheiaSemanticHighlightingInformation> Lines;
606   Lines.reserve(Tokens.size());
607   for (const auto &Line : Tokens) {
608     llvm::SmallVector<char, 128> LineByteTokens;
609     llvm::raw_svector_ostream OS(LineByteTokens);
610     for (const auto &Token : Line.Tokens) {
611       // Writes the token to LineByteTokens in the byte format specified by the
612       // LSP proposal. Described below.
613       // |<---- 4 bytes ---->|<-- 2 bytes -->|<--- 2 bytes -->|
614       // |    character      |  length       |    index       |
615 
616       write32be(Token.R.start.character, OS);
617       write16be(Token.R.end.character - Token.R.start.character, OS);
618       write16be(static_cast<int>(Token.Kind), OS);
619     }
620 
621     Lines.push_back({Line.Line, encodeBase64(LineByteTokens), Line.IsInactive});
622   }
623 
624   return Lines;
625 }
626 
toTextMateScope(HighlightingKind Kind)627 llvm::StringRef toTextMateScope(HighlightingKind Kind) {
628   // FIXME: Add scopes for C and Objective C.
629   switch (Kind) {
630   case HighlightingKind::Function:
631     return "entity.name.function.cpp";
632   case HighlightingKind::Method:
633     return "entity.name.function.method.cpp";
634   case HighlightingKind::StaticMethod:
635     return "entity.name.function.method.static.cpp";
636   case HighlightingKind::Variable:
637     return "variable.other.cpp";
638   case HighlightingKind::LocalVariable:
639     return "variable.other.local.cpp";
640   case HighlightingKind::Parameter:
641     return "variable.parameter.cpp";
642   case HighlightingKind::Field:
643     return "variable.other.field.cpp";
644   case HighlightingKind::StaticField:
645     return "variable.other.field.static.cpp";
646   case HighlightingKind::Class:
647     return "entity.name.type.class.cpp";
648   case HighlightingKind::Enum:
649     return "entity.name.type.enum.cpp";
650   case HighlightingKind::EnumConstant:
651     return "variable.other.enummember.cpp";
652   case HighlightingKind::Typedef:
653     return "entity.name.type.typedef.cpp";
654   case HighlightingKind::DependentType:
655     return "entity.name.type.dependent.cpp";
656   case HighlightingKind::DependentName:
657     return "entity.name.other.dependent.cpp";
658   case HighlightingKind::Namespace:
659     return "entity.name.namespace.cpp";
660   case HighlightingKind::TemplateParameter:
661     return "entity.name.type.template.cpp";
662   case HighlightingKind::Concept:
663     return "entity.name.type.concept.cpp";
664   case HighlightingKind::Primitive:
665     return "storage.type.primitive.cpp";
666   case HighlightingKind::Macro:
667     return "entity.name.function.preprocessor.cpp";
668   case HighlightingKind::InactiveCode:
669     return "meta.disabled";
670   }
671   llvm_unreachable("unhandled HighlightingKind");
672 }
673 
674 std::vector<SemanticTokensEdit>
diffTokens(llvm::ArrayRef<SemanticToken> Old,llvm::ArrayRef<SemanticToken> New)675 diffTokens(llvm::ArrayRef<SemanticToken> Old,
676            llvm::ArrayRef<SemanticToken> New) {
677   // For now, just replace everything from the first-last modification.
678   // FIXME: use a real diff instead, this is bad with include-insertion.
679 
680   unsigned Offset = 0;
681   while (!Old.empty() && !New.empty() && Old.front() == New.front()) {
682     ++Offset;
683     Old = Old.drop_front();
684     New = New.drop_front();
685   }
686   while (!Old.empty() && !New.empty() && Old.back() == New.back()) {
687     Old = Old.drop_back();
688     New = New.drop_back();
689   }
690 
691   if (Old.empty() && New.empty())
692     return {};
693   SemanticTokensEdit Edit;
694   Edit.startToken = Offset;
695   Edit.deleteTokens = Old.size();
696   Edit.tokens = New;
697   return {std::move(Edit)};
698 }
699 
700 } // namespace clangd
701 } // namespace clang
702