1//===--- SourceCode.h - Manipulating source code as strings -----*- 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#include "SourceCode.h"
9
10#include "FuzzyMatch.h"
11#include "Preamble.h"
12#include "Protocol.h"
13#include "support/Context.h"
14#include "support/Logger.h"
15#include "clang/Basic/FileEntry.h"
16#include "clang/Basic/LangOptions.h"
17#include "clang/Basic/SourceLocation.h"
18#include "clang/Basic/SourceManager.h"
19#include "clang/Basic/TokenKinds.h"
20#include "clang/Driver/Types.h"
21#include "clang/Format/Format.h"
22#include "clang/Lex/Lexer.h"
23#include "clang/Lex/Preprocessor.h"
24#include "clang/Lex/Token.h"
25#include "clang/Tooling/Core/Replacement.h"
26#include "clang/Tooling/Syntax/Tokens.h"
27#include "llvm/ADT/ArrayRef.h"
28#include "llvm/ADT/BitVector.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/ADT/StringExtras.h"
31#include "llvm/ADT/StringMap.h"
32#include "llvm/ADT/StringRef.h"
33#include "llvm/Support/Compiler.h"
34#include "llvm/Support/Errc.h"
35#include "llvm/Support/Error.h"
36#include "llvm/Support/ErrorHandling.h"
37#include "llvm/Support/LineIterator.h"
38#include "llvm/Support/MemoryBuffer.h"
39#include "llvm/Support/Path.h"
40#include "llvm/Support/VirtualFileSystem.h"
41#include "llvm/Support/xxhash.h"
42#include <algorithm>
43#include <cstddef>
44#include <optional>
45#include <string>
46#include <vector>
47
48namespace clang {
49namespace clangd {
50
51// Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
52// Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
53
54// Iterates over unicode codepoints in the (UTF-8) string. For each,
55// invokes CB(UTF-8 length, UTF-16 length), and breaks if it returns true.
56// Returns true if CB returned true, false if we hit the end of string.
57//
58// If the string is not valid UTF-8, we log this error and "decode" the
59// text in some arbitrary way. This is pretty sad, but this tends to happen deep
60// within indexing of headers where clang misdetected the encoding, and
61// propagating the error all the way back up is (probably?) not be worth it.
62template <typename Callback>
63static bool iterateCodepoints(llvm::StringRef U8, const Callback &CB) {
64 bool LoggedInvalid = false;
65 // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
66 // Astral codepoints are encoded as 4 bytes in UTF-8, starting with 11110xxx.
67 for (size_t I = 0; I < U8.size();) {
68 unsigned char C = static_cast<unsigned char>(U8[I]);
69 if (LLVM_LIKELY(!(C & 0x80))) { // ASCII character.
70 if (CB(1, 1))
71 return true;
72 ++I;
73 continue;
74 }
75 // This convenient property of UTF-8 holds for all non-ASCII characters.
76 size_t UTF8Length = llvm::countl_one(Value: C);
77 // 0xxx is ASCII, handled above. 10xxx is a trailing byte, invalid here.
78 // 11111xxx is not valid UTF-8 at all, maybe some ISO-8859-*.
79 if (LLVM_UNLIKELY(UTF8Length < 2 || UTF8Length > 4)) {
80 if (!LoggedInvalid) {
81 elog(Fmt: "File has invalid UTF-8 near offset {0}: {1}", Vals&: I, Vals: llvm::toHex(Input: U8));
82 LoggedInvalid = true;
83 }
84 // We can't give a correct result, but avoid returning something wild.
85 // Pretend this is a valid ASCII byte, for lack of better options.
86 // (Too late to get ISO-8859-* right, we've skipped some bytes already).
87 if (CB(1, 1))
88 return true;
89 ++I;
90 continue;
91 }
92 I += UTF8Length; // Skip over all trailing bytes.
93 // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
94 // Astral codepoints are encoded as 4 bytes in UTF-8 (11110xxx ...)
95 if (CB(UTF8Length, UTF8Length == 4 ? 2 : 1))
96 return true;
97 }
98 return false;
99}
100
101// Returns the byte offset into the string that is an offset of \p Units in
102// the specified encoding.
103// Conceptually, this converts to the encoding, truncates to CodeUnits,
104// converts back to UTF-8, and returns the length in bytes.
105static size_t measureUnits(llvm::StringRef U8, int Units, OffsetEncoding Enc,
106 bool &Valid) {
107 Valid = Units >= 0;
108 if (Units <= 0)
109 return 0;
110 size_t Result = 0;
111 switch (Enc) {
112 case OffsetEncoding::UTF8:
113 Result = Units;
114 break;
115 case OffsetEncoding::UTF16:
116 Valid = iterateCodepoints(U8, CB: [&](int U8Len, int U16Len) {
117 Result += U8Len;
118 Units -= U16Len;
119 return Units <= 0;
120 });
121 if (Units < 0) // Offset in the middle of a surrogate pair.
122 Valid = false;
123 break;
124 case OffsetEncoding::UTF32:
125 Valid = iterateCodepoints(U8, CB: [&](int U8Len, int U16Len) {
126 Result += U8Len;
127 Units--;
128 return Units <= 0;
129 });
130 break;
131 case OffsetEncoding::UnsupportedEncoding:
132 llvm_unreachable("unsupported encoding");
133 }
134 // Don't return an out-of-range index if we overran.
135 if (Result > U8.size()) {
136 Valid = false;
137 return U8.size();
138 }
139 return Result;
140}
141
142Key<OffsetEncoding> kCurrentOffsetEncoding;
143static OffsetEncoding lspEncoding() {
144 auto *Enc = Context::current().get(Key: kCurrentOffsetEncoding);
145 return Enc ? *Enc : OffsetEncoding::UTF16;
146}
147
148// Like most strings in clangd, the input is UTF-8 encoded.
149size_t lspLength(llvm::StringRef Code) {
150 size_t Count = 0;
151 switch (lspEncoding()) {
152 case OffsetEncoding::UTF8:
153 Count = Code.size();
154 break;
155 case OffsetEncoding::UTF16:
156 iterateCodepoints(U8: Code, CB: [&](int U8Len, int U16Len) {
157 Count += U16Len;
158 return false;
159 });
160 break;
161 case OffsetEncoding::UTF32:
162 iterateCodepoints(U8: Code, CB: [&](int U8Len, int U16Len) {
163 ++Count;
164 return false;
165 });
166 break;
167 case OffsetEncoding::UnsupportedEncoding:
168 llvm_unreachable("unsupported encoding");
169 }
170 return Count;
171}
172
173llvm::Expected<size_t> positionToOffset(llvm::StringRef Code, Position P,
174 bool AllowColumnsBeyondLineLength) {
175 if (P.line < 0)
176 return error(EC: llvm::errc::invalid_argument,
177 Fmt: "Line value can't be negative ({0})", Vals&: P.line);
178 if (P.character < 0)
179 return error(EC: llvm::errc::invalid_argument,
180 Fmt: "Character value can't be negative ({0})", Vals&: P.character);
181 size_t StartOfLine = 0;
182 for (int I = 0; I != P.line; ++I) {
183 size_t NextNL = Code.find(C: '\n', From: StartOfLine);
184 if (NextNL == llvm::StringRef::npos)
185 return error(EC: llvm::errc::invalid_argument,
186 Fmt: "Line value is out of range ({0})", Vals&: P.line);
187 StartOfLine = NextNL + 1;
188 }
189 StringRef Line =
190 Code.substr(Start: StartOfLine).take_until(F: [](char C) { return C == '\n'; });
191
192 // P.character may be in UTF-16, transcode if necessary.
193 bool Valid;
194 size_t ByteInLine = measureUnits(U8: Line, Units: P.character, Enc: lspEncoding(), Valid);
195 if (!Valid && !AllowColumnsBeyondLineLength)
196 return error(EC: llvm::errc::invalid_argument,
197 Fmt: "{0} offset {1} is invalid for line {2}", Vals: lspEncoding(),
198 Vals&: P.character, Vals&: P.line);
199 return StartOfLine + ByteInLine;
200}
201
202Position offsetToPosition(llvm::StringRef Code, size_t Offset) {
203 Offset = std::min(a: Code.size(), b: Offset);
204 llvm::StringRef Before = Code.substr(Start: 0, N: Offset);
205 int Lines = Before.count(C: '\n');
206 size_t PrevNL = Before.rfind(C: '\n');
207 size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
208 Position Pos;
209 Pos.line = Lines;
210 Pos.character = lspLength(Code: Before.substr(Start: StartOfLine));
211 return Pos;
212}
213
214Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc) {
215 // We use the SourceManager's line tables, but its column number is in bytes.
216 FileID FID;
217 unsigned Offset;
218 std::tie(args&: FID, args&: Offset) = SM.getDecomposedSpellingLoc(Loc);
219 Position P;
220 P.line = static_cast<int>(SM.getLineNumber(FID, FilePos: Offset)) - 1;
221 bool Invalid = false;
222 llvm::StringRef Code = SM.getBufferData(FID, Invalid: &Invalid);
223 if (!Invalid) {
224 auto ColumnInBytes = SM.getColumnNumber(FID, FilePos: Offset) - 1;
225 auto LineSoFar = Code.substr(Start: Offset - ColumnInBytes, N: ColumnInBytes);
226 P.character = lspLength(Code: LineSoFar);
227 }
228 return P;
229}
230
231bool isSpelledInSource(SourceLocation Loc, const SourceManager &SM) {
232 if (Loc.isFileID())
233 return true;
234 auto Spelling = SM.getDecomposedSpellingLoc(Loc);
235 bool InvalidSLocEntry = false;
236 const auto SLocEntry = SM.getSLocEntry(FID: Spelling.first, Invalid: &InvalidSLocEntry);
237 if (InvalidSLocEntry)
238 return false;
239 StringRef SpellingFile = SLocEntry.getFile().getName();
240 if (SpellingFile == "<scratch space>")
241 return false;
242 if (SpellingFile == "<built-in>")
243 // __STDC__ etc are considered spelled, but BAR in arg -DFOO=BAR is not.
244 return !SM.isWrittenInCommandLineFile(
245 Loc: SM.getComposedLoc(FID: Spelling.first, Offset: Spelling.second));
246 return true;
247}
248
249bool isValidFileRange(const SourceManager &Mgr, SourceRange R) {
250 if (!R.getBegin().isValid() || !R.getEnd().isValid())
251 return false;
252
253 FileID BeginFID;
254 size_t BeginOffset = 0;
255 std::tie(args&: BeginFID, args&: BeginOffset) = Mgr.getDecomposedLoc(Loc: R.getBegin());
256
257 FileID EndFID;
258 size_t EndOffset = 0;
259 std::tie(args&: EndFID, args&: EndOffset) = Mgr.getDecomposedLoc(Loc: R.getEnd());
260
261 return BeginFID.isValid() && BeginFID == EndFID && BeginOffset <= EndOffset;
262}
263
264SourceLocation includeHashLoc(FileID IncludedFile, const SourceManager &SM) {
265 assert(SM.getLocForEndOfFile(IncludedFile).isFileID());
266 FileID IncludingFile;
267 unsigned Offset;
268 std::tie(args&: IncludingFile, args&: Offset) =
269 SM.getDecomposedExpansionLoc(Loc: SM.getIncludeLoc(FID: IncludedFile));
270 bool Invalid = false;
271 llvm::StringRef Buf = SM.getBufferData(FID: IncludingFile, Invalid: &Invalid);
272 if (Invalid)
273 return SourceLocation();
274 // Now buf is "...\n#include <foo>\n..."
275 // and Offset points here: ^
276 // Rewind to the preceding # on the line.
277 assert(Offset < Buf.size());
278 for (;; --Offset) {
279 if (Buf[Offset] == '#')
280 return SM.getComposedLoc(FID: IncludingFile, Offset);
281 if (Buf[Offset] == '\n' || Offset == 0) // no hash, what's going on?
282 return SourceLocation();
283 }
284}
285
286static unsigned getTokenLengthAtLoc(SourceLocation Loc, const SourceManager &SM,
287 const LangOptions &LangOpts) {
288 Token TheTok;
289 if (Lexer::getRawToken(Loc, Result&: TheTok, SM, LangOpts))
290 return 0;
291 // FIXME: Here we check whether the token at the location is a greatergreater
292 // (>>) token and consider it as a single greater (>). This is to get it
293 // working for templates but it isn't correct for the right shift operator. We
294 // can avoid this by using half open char ranges in getFileRange() but getting
295 // token ending is not well supported in macroIDs.
296 if (TheTok.is(K: tok::greatergreater))
297 return 1;
298 return TheTok.getLength();
299}
300
301// Returns location of the last character of the token at a given loc
302static SourceLocation getLocForTokenEnd(SourceLocation BeginLoc,
303 const SourceManager &SM,
304 const LangOptions &LangOpts) {
305 unsigned Len = getTokenLengthAtLoc(Loc: BeginLoc, SM, LangOpts);
306 return BeginLoc.getLocWithOffset(Offset: Len ? Len - 1 : 0);
307}
308
309// Returns location of the starting of the token at a given EndLoc
310static SourceLocation getLocForTokenBegin(SourceLocation EndLoc,
311 const SourceManager &SM,
312 const LangOptions &LangOpts) {
313 return EndLoc.getLocWithOffset(
314 Offset: -(signed)getTokenLengthAtLoc(Loc: EndLoc, SM, LangOpts));
315}
316
317// Converts a char source range to a token range.
318static SourceRange toTokenRange(CharSourceRange Range, const SourceManager &SM,
319 const LangOptions &LangOpts) {
320 if (!Range.isTokenRange())
321 Range.setEnd(getLocForTokenBegin(EndLoc: Range.getEnd(), SM, LangOpts));
322 return Range.getAsRange();
323}
324// Returns the union of two token ranges.
325// To find the maximum of the Ends of the ranges, we compare the location of the
326// last character of the token.
327static SourceRange unionTokenRange(SourceRange R1, SourceRange R2,
328 const SourceManager &SM,
329 const LangOptions &LangOpts) {
330 SourceLocation Begin =
331 SM.isBeforeInTranslationUnit(LHS: R1.getBegin(), RHS: R2.getBegin())
332 ? R1.getBegin()
333 : R2.getBegin();
334 SourceLocation End =
335 SM.isBeforeInTranslationUnit(LHS: getLocForTokenEnd(BeginLoc: R1.getEnd(), SM, LangOpts),
336 RHS: getLocForTokenEnd(BeginLoc: R2.getEnd(), SM, LangOpts))
337 ? R2.getEnd()
338 : R1.getEnd();
339 return SourceRange(Begin, End);
340}
341
342// Given a range whose endpoints may be in different expansions or files,
343// tries to find a range within a common file by following up the expansion and
344// include location in each.
345static SourceRange rangeInCommonFile(SourceRange R, const SourceManager &SM,
346 const LangOptions &LangOpts) {
347 // Fast path for most common cases.
348 if (SM.isWrittenInSameFile(Loc1: R.getBegin(), Loc2: R.getEnd()))
349 return R;
350 // Record the stack of expansion locations for the beginning, keyed by FileID.
351 llvm::DenseMap<FileID, SourceLocation> BeginExpansions;
352 for (SourceLocation Begin = R.getBegin(); Begin.isValid();
353 Begin = Begin.isFileID()
354 ? includeHashLoc(IncludedFile: SM.getFileID(SpellingLoc: Begin), SM)
355 : SM.getImmediateExpansionRange(Loc: Begin).getBegin()) {
356 BeginExpansions[SM.getFileID(SpellingLoc: Begin)] = Begin;
357 }
358 // Move up the stack of expansion locations for the end until we find the
359 // location in BeginExpansions with that has the same file id.
360 for (SourceLocation End = R.getEnd(); End.isValid();
361 End = End.isFileID() ? includeHashLoc(IncludedFile: SM.getFileID(SpellingLoc: End), SM)
362 : toTokenRange(Range: SM.getImmediateExpansionRange(Loc: End),
363 SM, LangOpts)
364 .getEnd()) {
365 auto It = BeginExpansions.find(Val: SM.getFileID(SpellingLoc: End));
366 if (It != BeginExpansions.end()) {
367 if (SM.getFileOffset(SpellingLoc: It->second) > SM.getFileOffset(SpellingLoc: End))
368 return SourceLocation();
369 return {It->second, End};
370 }
371 }
372 return SourceRange();
373}
374
375// Find an expansion range (not necessarily immediate) the ends of which are in
376// the same file id.
377static SourceRange
378getExpansionTokenRangeInSameFile(SourceLocation Loc, const SourceManager &SM,
379 const LangOptions &LangOpts) {
380 return rangeInCommonFile(
381 R: toTokenRange(Range: SM.getImmediateExpansionRange(Loc), SM, LangOpts), SM,
382 LangOpts);
383}
384
385// Returns the file range for a given Location as a Token Range
386// This is quite similar to getFileLoc in SourceManager as both use
387// getImmediateExpansionRange and getImmediateSpellingLoc (for macro IDs).
388// However:
389// - We want to maintain the full range information as we move from one file to
390// the next. getFileLoc only uses the BeginLoc of getImmediateExpansionRange.
391// - We want to split '>>' tokens as the lexer parses the '>>' in nested
392// template instantiations as a '>>' instead of two '>'s.
393// There is also getExpansionRange but it simply calls
394// getImmediateExpansionRange on the begin and ends separately which is wrong.
395static SourceRange getTokenFileRange(SourceLocation Loc,
396 const SourceManager &SM,
397 const LangOptions &LangOpts) {
398 SourceRange FileRange = Loc;
399 while (!FileRange.getBegin().isFileID()) {
400 if (SM.isMacroArgExpansion(Loc: FileRange.getBegin())) {
401 FileRange = unionTokenRange(
402 R1: SM.getImmediateSpellingLoc(Loc: FileRange.getBegin()),
403 R2: SM.getImmediateSpellingLoc(Loc: FileRange.getEnd()), SM, LangOpts);
404 assert(SM.isWrittenInSameFile(FileRange.getBegin(), FileRange.getEnd()));
405 } else {
406 SourceRange ExpansionRangeForBegin =
407 getExpansionTokenRangeInSameFile(Loc: FileRange.getBegin(), SM, LangOpts);
408 SourceRange ExpansionRangeForEnd =
409 getExpansionTokenRangeInSameFile(Loc: FileRange.getEnd(), SM, LangOpts);
410 if (ExpansionRangeForBegin.isInvalid() ||
411 ExpansionRangeForEnd.isInvalid())
412 return SourceRange();
413 assert(SM.isWrittenInSameFile(ExpansionRangeForBegin.getBegin(),
414 ExpansionRangeForEnd.getBegin()) &&
415 "Both Expansion ranges should be in same file.");
416 FileRange = unionTokenRange(R1: ExpansionRangeForBegin, R2: ExpansionRangeForEnd,
417 SM, LangOpts);
418 }
419 }
420 return FileRange;
421}
422
423bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM) {
424 if (!Loc.isValid())
425 return false;
426 FileID FID = SM.getFileID(SpellingLoc: SM.getExpansionLoc(Loc));
427 return FID == SM.getMainFileID() || FID == SM.getPreambleFileID();
428}
429
430std::optional<SourceRange> toHalfOpenFileRange(const SourceManager &SM,
431 const LangOptions &LangOpts,
432 SourceRange R) {
433 SourceRange R1 = getTokenFileRange(Loc: R.getBegin(), SM, LangOpts);
434 if (!isValidFileRange(Mgr: SM, R: R1))
435 return std::nullopt;
436
437 SourceRange R2 = getTokenFileRange(Loc: R.getEnd(), SM, LangOpts);
438 if (!isValidFileRange(Mgr: SM, R: R2))
439 return std::nullopt;
440
441 SourceRange Result =
442 rangeInCommonFile(R: unionTokenRange(R1, R2, SM, LangOpts), SM, LangOpts);
443 unsigned TokLen = getTokenLengthAtLoc(Loc: Result.getEnd(), SM, LangOpts);
444 // Convert from closed token range to half-open (char) range
445 Result.setEnd(Result.getEnd().getLocWithOffset(Offset: TokLen));
446 if (!isValidFileRange(Mgr: SM, R: Result))
447 return std::nullopt;
448
449 return Result;
450}
451
452llvm::StringRef toSourceCode(const SourceManager &SM, SourceRange R) {
453 assert(isValidFileRange(SM, R));
454 auto Buf = SM.getBufferOrNone(FID: SM.getFileID(SpellingLoc: R.getBegin()));
455 assert(Buf);
456
457 size_t BeginOffset = SM.getFileOffset(SpellingLoc: R.getBegin());
458 size_t EndOffset = SM.getFileOffset(SpellingLoc: R.getEnd());
459 return Buf->getBuffer().substr(Start: BeginOffset, N: EndOffset - BeginOffset);
460}
461
462llvm::Expected<SourceLocation> sourceLocationInMainFile(const SourceManager &SM,
463 Position P) {
464 llvm::StringRef Code = SM.getBufferOrFake(FID: SM.getMainFileID()).getBuffer();
465 auto Offset =
466 positionToOffset(Code, P, /*AllowColumnsBeyondLineLength=*/false);
467 if (!Offset)
468 return Offset.takeError();
469 return SM.getLocForStartOfFile(FID: SM.getMainFileID()).getLocWithOffset(Offset: *Offset);
470}
471
472Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
473 // Clang is 1-based, LSP uses 0-based indexes.
474 Position Begin = sourceLocToPosition(SM, Loc: R.getBegin());
475 Position End = sourceLocToPosition(SM, Loc: R.getEnd());
476
477 return {.start: Begin, .end: End};
478}
479
480void unionRanges(Range &A, Range B) {
481 if (B.start < A.start)
482 A.start = B.start;
483 if (A.end < B.end)
484 A.end = B.end;
485}
486
487std::pair<size_t, size_t> offsetToClangLineColumn(llvm::StringRef Code,
488 size_t Offset) {
489 Offset = std::min(a: Code.size(), b: Offset);
490 llvm::StringRef Before = Code.substr(Start: 0, N: Offset);
491 int Lines = Before.count(C: '\n');
492 size_t PrevNL = Before.rfind(C: '\n');
493 size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
494 return {Lines + 1, Offset - StartOfLine + 1};
495}
496
497std::pair<StringRef, StringRef> splitQualifiedName(StringRef QName) {
498 size_t Pos = QName.rfind(Str: "::");
499 if (Pos == llvm::StringRef::npos)
500 return {llvm::StringRef(), QName};
501 return {QName.substr(Start: 0, N: Pos + 2), QName.substr(Start: Pos + 2)};
502}
503
504TextEdit replacementToEdit(llvm::StringRef Code,
505 const tooling::Replacement &R) {
506 Range ReplacementRange = {
507 .start: offsetToPosition(Code, Offset: R.getOffset()),
508 .end: offsetToPosition(Code, Offset: R.getOffset() + R.getLength())};
509 return {.range: ReplacementRange, .newText: std::string(R.getReplacementText())};
510}
511
512std::vector<TextEdit> replacementsToEdits(llvm::StringRef Code,
513 const tooling::Replacements &Repls) {
514 std::vector<TextEdit> Edits;
515 for (const auto &R : Repls)
516 Edits.push_back(x: replacementToEdit(Code, R));
517 return Edits;
518}
519
520std::optional<std::string> getCanonicalPath(const FileEntryRef F,
521 FileManager &FileMgr) {
522 llvm::SmallString<128> FilePath = F.getName();
523 if (!llvm::sys::path::is_absolute(path: FilePath)) {
524 if (auto EC =
525 FileMgr.getVirtualFileSystem().makeAbsolute(
526 Path&: FilePath)) {
527 elog(Fmt: "Could not turn relative path '{0}' to absolute: {1}", Vals&: FilePath,
528 Vals: EC.message());
529 return std::nullopt;
530 }
531 }
532
533 // Handle the symbolic link path case where the current working directory
534 // (getCurrentWorkingDirectory) is a symlink. We always want to the real
535 // file path (instead of the symlink path) for the C++ symbols.
536 //
537 // Consider the following example:
538 //
539 // src dir: /project/src/foo.h
540 // current working directory (symlink): /tmp/build -> /project/src/
541 //
542 // The file path of Symbol is "/project/src/foo.h" instead of
543 // "/tmp/build/foo.h"
544 if (auto Dir = FileMgr.getOptionalDirectoryRef(
545 DirName: llvm::sys::path::parent_path(path: FilePath))) {
546 llvm::SmallString<128> RealPath;
547 llvm::StringRef DirName = FileMgr.getCanonicalName(Dir: *Dir);
548 llvm::sys::path::append(path&: RealPath, a: DirName,
549 b: llvm::sys::path::filename(path: FilePath));
550 return RealPath.str().str();
551 }
552
553 return FilePath.str().str();
554}
555
556TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M,
557 const LangOptions &L) {
558 TextEdit Result;
559 Result.range =
560 halfOpenToRange(SM: M, R: Lexer::makeFileCharRange(Range: FixIt.RemoveRange, SM: M, LangOpts: L));
561 Result.newText = FixIt.CodeToInsert;
562 return Result;
563}
564
565FileDigest digest(llvm::StringRef Content) {
566 uint64_t Hash{llvm::xxh3_64bits(data: Content)};
567 FileDigest Result;
568 for (unsigned I = 0; I < Result.size(); ++I) {
569 Result[I] = uint8_t(Hash);
570 Hash >>= 8;
571 }
572 return Result;
573}
574
575std::optional<FileDigest> digestFile(const SourceManager &SM, FileID FID) {
576 bool Invalid = false;
577 llvm::StringRef Content = SM.getBufferData(FID, Invalid: &Invalid);
578 if (Invalid)
579 return std::nullopt;
580 return digest(Content);
581}
582
583format::FormatStyle getFormatStyleForFile(llvm::StringRef File,
584 llvm::StringRef Content,
585 const ThreadsafeFS &TFS) {
586 auto Style = format::getStyle(StyleName: format::DefaultFormatStyle, FileName: File,
587 FallbackStyle: format::DefaultFallbackStyle, Code: Content,
588 FS: TFS.view(/*CWD=*/std::nullopt).get());
589 if (!Style) {
590 log(Fmt: "getStyle() failed for file {0}: {1}. Fallback is LLVM style.", Vals&: File,
591 Vals: Style.takeError());
592 return format::getLLVMStyle();
593 }
594 return *Style;
595}
596
597llvm::Expected<tooling::Replacements>
598cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
599 const format::FormatStyle &Style) {
600 auto CleanReplaces = cleanupAroundReplacements(Code, Replaces, Style);
601 if (!CleanReplaces)
602 return CleanReplaces;
603 return formatReplacements(Code, Replaces: std::move(*CleanReplaces), Style);
604}
605
606static void
607lex(llvm::StringRef Code, const LangOptions &LangOpts,
608 llvm::function_ref<void(const syntax::Token &, const SourceManager &SM)>
609 Action) {
610 // FIXME: InMemoryFileAdapter crashes unless the buffer is null terminated!
611 std::string NullTerminatedCode = Code.str();
612 SourceManagerForFile FileSM("mock_file_name.cpp", NullTerminatedCode);
613 auto &SM = FileSM.get();
614 for (const auto &Tok : syntax::tokenize(FID: SM.getMainFileID(), SM, LO: LangOpts))
615 Action(Tok, SM);
616}
617
618llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
619 const format::FormatStyle &Style) {
620 llvm::StringMap<unsigned> Identifiers;
621 auto LangOpt = format::getFormattingLangOpts(Style);
622 lex(Code: Content, LangOpts: LangOpt, Action: [&](const syntax::Token &Tok, const SourceManager &SM) {
623 if (Tok.kind() == tok::identifier)
624 ++Identifiers[Tok.text(SM)];
625 // FIXME: Should this function really return keywords too ?
626 else if (const auto *Keyword = tok::getKeywordSpelling(Kind: Tok.kind()))
627 ++Identifiers[Keyword];
628 });
629 return Identifiers;
630}
631
632std::vector<Range> collectIdentifierRanges(llvm::StringRef Identifier,
633 llvm::StringRef Content,
634 const LangOptions &LangOpts) {
635 std::vector<Range> Ranges;
636 lex(Code: Content, LangOpts,
637 Action: [&](const syntax::Token &Tok, const SourceManager &SM) {
638 if (Tok.kind() != tok::identifier || Tok.text(SM) != Identifier)
639 return;
640 Ranges.push_back(x: halfOpenToRange(SM, R: Tok.range(SM).toCharRange(SM)));
641 });
642 return Ranges;
643}
644
645bool isKeyword(llvm::StringRef NewName, const LangOptions &LangOpts) {
646 // Keywords are initialized in constructor.
647 clang::IdentifierTable KeywordsTable(LangOpts);
648 return KeywordsTable.find(NewName) != KeywordsTable.end();
649}
650
651namespace {
652struct NamespaceEvent {
653 enum {
654 BeginNamespace, // namespace <ns> {. Payload is resolved <ns>.
655 EndNamespace, // } // namespace <ns>. Payload is resolved *outer*
656 // namespace.
657 UsingDirective // using namespace <ns>. Payload is unresolved <ns>.
658 } Trigger;
659 std::string Payload;
660 Position Pos;
661};
662// Scans C++ source code for constructs that change the visible namespaces.
663void parseNamespaceEvents(llvm::StringRef Code, const LangOptions &LangOpts,
664 llvm::function_ref<void(NamespaceEvent)> Callback) {
665
666 // Stack of enclosing namespaces, e.g. {"clang", "clangd"}
667 std::vector<std::string> Enclosing; // Contains e.g. "clang", "clangd"
668 // Stack counts open braces. true if the brace opened a namespace.
669 llvm::BitVector BraceStack;
670
671 enum {
672 Default,
673 Namespace, // just saw 'namespace'
674 NamespaceName, // just saw 'namespace' NSName
675 Using, // just saw 'using'
676 UsingNamespace, // just saw 'using namespace'
677 UsingNamespaceName, // just saw 'using namespace' NSName
678 } State = Default;
679 std::string NSName;
680
681 NamespaceEvent Event;
682 lex(Code, LangOpts, Action: [&](const syntax::Token &Tok, const SourceManager &SM) {
683 Event.Pos = sourceLocToPosition(SM, Loc: Tok.location());
684 switch (Tok.kind()) {
685 case tok::kw_using:
686 State = State == Default ? Using : Default;
687 break;
688 case tok::kw_namespace:
689 switch (State) {
690 case Using:
691 State = UsingNamespace;
692 break;
693 case Default:
694 State = Namespace;
695 break;
696 default:
697 State = Default;
698 break;
699 }
700 break;
701 case tok::identifier:
702 switch (State) {
703 case UsingNamespace:
704 NSName.clear();
705 [[fallthrough]];
706 case UsingNamespaceName:
707 NSName.append(str: Tok.text(SM).str());
708 State = UsingNamespaceName;
709 break;
710 case Namespace:
711 NSName.clear();
712 [[fallthrough]];
713 case NamespaceName:
714 NSName.append(str: Tok.text(SM).str());
715 State = NamespaceName;
716 break;
717 case Using:
718 case Default:
719 State = Default;
720 break;
721 }
722 break;
723 case tok::coloncolon:
724 // This can come at the beginning or in the middle of a namespace
725 // name.
726 switch (State) {
727 case UsingNamespace:
728 NSName.clear();
729 [[fallthrough]];
730 case UsingNamespaceName:
731 NSName.append(s: "::");
732 State = UsingNamespaceName;
733 break;
734 case NamespaceName:
735 NSName.append(s: "::");
736 State = NamespaceName;
737 break;
738 case Namespace: // Not legal here.
739 case Using:
740 case Default:
741 State = Default;
742 break;
743 }
744 break;
745 case tok::l_brace:
746 // Record which { started a namespace, so we know when } ends one.
747 if (State == NamespaceName) {
748 // Parsed: namespace <name> {
749 BraceStack.push_back(Val: true);
750 Enclosing.push_back(x: NSName);
751 Event.Trigger = NamespaceEvent::BeginNamespace;
752 Event.Payload = llvm::join(R&: Enclosing, Separator: "::");
753 Callback(Event);
754 } else {
755 // This case includes anonymous namespaces (State = Namespace).
756 // For our purposes, they're not namespaces and we ignore them.
757 BraceStack.push_back(Val: false);
758 }
759 State = Default;
760 break;
761 case tok::r_brace:
762 // If braces are unmatched, we're going to be confused, but don't
763 // crash.
764 if (!BraceStack.empty()) {
765 if (BraceStack.back()) {
766 // Parsed: } // namespace
767 Enclosing.pop_back();
768 Event.Trigger = NamespaceEvent::EndNamespace;
769 Event.Payload = llvm::join(R&: Enclosing, Separator: "::");
770 Callback(Event);
771 }
772 BraceStack.pop_back();
773 }
774 break;
775 case tok::semi:
776 if (State == UsingNamespaceName) {
777 // Parsed: using namespace <name> ;
778 Event.Trigger = NamespaceEvent::UsingDirective;
779 Event.Payload = std::move(NSName);
780 Callback(Event);
781 }
782 State = Default;
783 break;
784 default:
785 State = Default;
786 break;
787 }
788 });
789}
790
791// Returns the prefix namespaces of NS: {"" ... NS}.
792llvm::SmallVector<llvm::StringRef> ancestorNamespaces(llvm::StringRef NS) {
793 llvm::SmallVector<llvm::StringRef> Results;
794 Results.push_back(Elt: NS.take_front(N: 0));
795 NS.split(A&: Results, Separator: "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
796 for (llvm::StringRef &R : Results)
797 R = NS.take_front(N: R.end() - NS.begin());
798 return Results;
799}
800
801// Checks whether \p FileName is a valid spelling of main file.
802bool isMainFile(llvm::StringRef FileName, const SourceManager &SM) {
803 auto FE = SM.getFileManager().getFile(Filename: FileName);
804 return FE && *FE == SM.getFileEntryForID(FID: SM.getMainFileID());
805}
806
807} // namespace
808
809std::vector<std::string> visibleNamespaces(llvm::StringRef Code,
810 const LangOptions &LangOpts) {
811 std::string Current;
812 // Map from namespace to (resolved) namespaces introduced via using directive.
813 llvm::StringMap<llvm::StringSet<>> UsingDirectives;
814
815 parseNamespaceEvents(Code, LangOpts, Callback: [&](NamespaceEvent Event) {
816 llvm::StringRef NS = Event.Payload;
817 switch (Event.Trigger) {
818 case NamespaceEvent::BeginNamespace:
819 case NamespaceEvent::EndNamespace:
820 Current = std::move(Event.Payload);
821 break;
822 case NamespaceEvent::UsingDirective:
823 if (NS.consume_front(Prefix: "::"))
824 UsingDirectives[Current].insert(key: NS);
825 else {
826 for (llvm::StringRef Enclosing : ancestorNamespaces(NS: Current)) {
827 if (Enclosing.empty())
828 UsingDirectives[Current].insert(key: NS);
829 else
830 UsingDirectives[Current].insert(key: (Enclosing + "::" + NS).str());
831 }
832 }
833 break;
834 }
835 });
836
837 std::vector<std::string> Found;
838 for (llvm::StringRef Enclosing : ancestorNamespaces(NS: Current)) {
839 Found.push_back(x: std::string(Enclosing));
840 auto It = UsingDirectives.find(Key: Enclosing);
841 if (It != UsingDirectives.end())
842 for (const auto &Used : It->second)
843 Found.push_back(x: std::string(Used.getKey()));
844 }
845
846 llvm::sort(C&: Found, Comp: [&](const std::string &LHS, const std::string &RHS) {
847 if (Current == RHS)
848 return false;
849 if (Current == LHS)
850 return true;
851 return LHS < RHS;
852 });
853 Found.erase(first: std::unique(first: Found.begin(), last: Found.end()), last: Found.end());
854 return Found;
855}
856
857llvm::StringSet<> collectWords(llvm::StringRef Content) {
858 // We assume short words are not significant.
859 // We may want to consider other stopwords, e.g. language keywords.
860 // (A very naive implementation showed no benefit, but lexing might do better)
861 static constexpr int MinWordLength = 4;
862
863 std::vector<CharRole> Roles(Content.size());
864 calculateRoles(Text: Content, Roles);
865
866 llvm::StringSet<> Result;
867 llvm::SmallString<256> Word;
868 auto Flush = [&] {
869 if (Word.size() >= MinWordLength) {
870 for (char &C : Word)
871 C = llvm::toLower(x: C);
872 Result.insert(key: Word);
873 }
874 Word.clear();
875 };
876 for (unsigned I = 0; I < Content.size(); ++I) {
877 switch (Roles[I]) {
878 case Head:
879 Flush();
880 [[fallthrough]];
881 case Tail:
882 Word.push_back(Elt: Content[I]);
883 break;
884 case Unknown:
885 case Separator:
886 Flush();
887 break;
888 }
889 }
890 Flush();
891
892 return Result;
893}
894
895static bool isLikelyIdentifier(llvm::StringRef Word, llvm::StringRef Before,
896 llvm::StringRef After) {
897 // `foo` is an identifier.
898 if (Before.ends_with(Suffix: "`") && After.starts_with(Prefix: "`"))
899 return true;
900 // In foo::bar, both foo and bar are identifiers.
901 if (Before.ends_with(Suffix: "::") || After.starts_with(Prefix: "::"))
902 return true;
903 // Doxygen tags like \c foo indicate identifiers.
904 // Don't search too far back.
905 // This duplicates clang's doxygen parser, revisit if it gets complicated.
906 Before = Before.take_back(N: 100); // Don't search too far back.
907 auto Pos = Before.find_last_of(Chars: "\\@");
908 if (Pos != llvm::StringRef::npos) {
909 llvm::StringRef Tag = Before.substr(Start: Pos + 1).rtrim(Char: ' ');
910 if (Tag == "p" || Tag == "c" || Tag == "class" || Tag == "tparam" ||
911 Tag == "param" || Tag == "param[in]" || Tag == "param[out]" ||
912 Tag == "param[in,out]" || Tag == "retval" || Tag == "throw" ||
913 Tag == "throws" || Tag == "link")
914 return true;
915 }
916
917 // Word contains underscore.
918 // This handles things like snake_case and MACRO_CASE.
919 if (Word.contains(C: '_')) {
920 return true;
921 }
922 // Word contains capital letter other than at beginning.
923 // This handles things like lowerCamel and UpperCamel.
924 // The check for also containing a lowercase letter is to rule out
925 // initialisms like "HTTP".
926 bool HasLower = Word.find_if(F: clang::isLowercase) != StringRef::npos;
927 bool HasUpper = Word.substr(Start: 1).find_if(F: clang::isUppercase) != StringRef::npos;
928 if (HasLower && HasUpper) {
929 return true;
930 }
931 // FIXME: consider mid-sentence Capitalization?
932 return false;
933}
934
935std::optional<SpelledWord> SpelledWord::touching(SourceLocation SpelledLoc,
936 const syntax::TokenBuffer &TB,
937 const LangOptions &LangOpts) {
938 const auto &SM = TB.sourceManager();
939 auto Touching = syntax::spelledTokensTouching(Loc: SpelledLoc, Tokens: TB);
940 for (const auto &T : Touching) {
941 // If the token is an identifier or a keyword, don't use any heuristics.
942 if (tok::isAnyIdentifier(K: T.kind()) || tok::getKeywordSpelling(Kind: T.kind())) {
943 SpelledWord Result;
944 Result.Location = T.location();
945 Result.Text = T.text(SM);
946 Result.LikelyIdentifier = tok::isAnyIdentifier(K: T.kind());
947 Result.PartOfSpelledToken = &T;
948 Result.SpelledToken = &T;
949 auto Expanded =
950 TB.expandedTokens(R: SM.getMacroArgExpandedLocation(Loc: T.location()));
951 if (Expanded.size() == 1 && Expanded.front().text(SM) == Result.Text)
952 Result.ExpandedToken = &Expanded.front();
953 return Result;
954 }
955 }
956 FileID File;
957 unsigned Offset;
958 std::tie(args&: File, args&: Offset) = SM.getDecomposedLoc(Loc: SpelledLoc);
959 bool Invalid = false;
960 llvm::StringRef Code = SM.getBufferData(FID: File, Invalid: &Invalid);
961 if (Invalid)
962 return std::nullopt;
963 unsigned B = Offset, E = Offset;
964 while (B > 0 && isAsciiIdentifierContinue(c: Code[B - 1]))
965 --B;
966 while (E < Code.size() && isAsciiIdentifierContinue(c: Code[E]))
967 ++E;
968 if (B == E)
969 return std::nullopt;
970
971 SpelledWord Result;
972 Result.Location = SM.getComposedLoc(FID: File, Offset: B);
973 Result.Text = Code.slice(Start: B, End: E);
974 Result.LikelyIdentifier =
975 isLikelyIdentifier(Word: Result.Text, Before: Code.substr(Start: 0, N: B), After: Code.substr(Start: E)) &&
976 // should not be a keyword
977 tok::isAnyIdentifier(
978 K: IdentifierTable(LangOpts).get(Name: Result.Text).getTokenID());
979 for (const auto &T : Touching)
980 if (T.location() <= Result.Location)
981 Result.PartOfSpelledToken = &T;
982 return Result;
983}
984
985std::optional<DefinedMacro> locateMacroAt(const syntax::Token &SpelledTok,
986 Preprocessor &PP) {
987 if (SpelledTok.kind() != tok::identifier)
988 return std::nullopt;
989 SourceLocation Loc = SpelledTok.location();
990 assert(Loc.isFileID());
991 const auto &SM = PP.getSourceManager();
992 IdentifierInfo *IdentifierInfo = PP.getIdentifierInfo(Name: SpelledTok.text(SM));
993 if (!IdentifierInfo || !IdentifierInfo->hadMacroDefinition())
994 return std::nullopt;
995
996 // We need to take special case to handle #define and #undef.
997 // Preprocessor::getMacroDefinitionAtLoc() only considers a macro
998 // definition to be in scope *after* the location of the macro name in a
999 // #define that introduces it, and *before* the location of the macro name
1000 // in an #undef that undefines it. To handle these cases, we check for
1001 // the macro being in scope either just after or just before the location
1002 // of the token. In getting the location before, we also take care to check
1003 // for start-of-file.
1004 FileID FID = SM.getFileID(SpellingLoc: Loc);
1005 assert(Loc != SM.getLocForEndOfFile(FID));
1006 SourceLocation JustAfterToken = Loc.getLocWithOffset(Offset: 1);
1007 auto *MacroInfo =
1008 PP.getMacroDefinitionAtLoc(II: IdentifierInfo, Loc: JustAfterToken).getMacroInfo();
1009 if (!MacroInfo && SM.getLocForStartOfFile(FID) != Loc) {
1010 SourceLocation JustBeforeToken = Loc.getLocWithOffset(Offset: -1);
1011 MacroInfo = PP.getMacroDefinitionAtLoc(II: IdentifierInfo, Loc: JustBeforeToken)
1012 .getMacroInfo();
1013 }
1014 if (!MacroInfo) {
1015 return std::nullopt;
1016 }
1017 return DefinedMacro{
1018 .Name: IdentifierInfo->getName(), .Info: MacroInfo,
1019 .NameLoc: translatePreamblePatchLocation(Loc: MacroInfo->getDefinitionLoc(), SM)};
1020}
1021
1022llvm::Expected<std::string> Edit::apply() const {
1023 return tooling::applyAllReplacements(Code: InitialCode, Replaces: Replacements);
1024}
1025
1026std::vector<TextEdit> Edit::asTextEdits() const {
1027 return replacementsToEdits(Code: InitialCode, Repls: Replacements);
1028}
1029
1030bool Edit::canApplyTo(llvm::StringRef Code) const {
1031 // Create line iterators, since line numbers are important while applying our
1032 // edit we cannot skip blank lines.
1033 auto LHS = llvm::MemoryBuffer::getMemBuffer(InputData: Code);
1034 llvm::line_iterator LHSIt(*LHS, /*SkipBlanks=*/false);
1035
1036 auto RHS = llvm::MemoryBuffer::getMemBuffer(InputData: InitialCode);
1037 llvm::line_iterator RHSIt(*RHS, /*SkipBlanks=*/false);
1038
1039 // Compare the InitialCode we prepared the edit for with the Code we received
1040 // line by line to make sure there are no differences.
1041 // FIXME: This check is too conservative now, it should be enough to only
1042 // check lines around the replacements contained inside the Edit.
1043 while (!LHSIt.is_at_eof() && !RHSIt.is_at_eof()) {
1044 if (*LHSIt != *RHSIt)
1045 return false;
1046 ++LHSIt;
1047 ++RHSIt;
1048 }
1049
1050 // After we reach EOF for any of the files we make sure the other one doesn't
1051 // contain any additional content except empty lines, they should not
1052 // interfere with the edit we produced.
1053 while (!LHSIt.is_at_eof()) {
1054 if (!LHSIt->empty())
1055 return false;
1056 ++LHSIt;
1057 }
1058 while (!RHSIt.is_at_eof()) {
1059 if (!RHSIt->empty())
1060 return false;
1061 ++RHSIt;
1062 }
1063 return true;
1064}
1065
1066llvm::Error reformatEdit(Edit &E, const format::FormatStyle &Style) {
1067 if (auto NewEdits = cleanupAndFormat(Code: E.InitialCode, Replaces: E.Replacements, Style))
1068 E.Replacements = std::move(*NewEdits);
1069 else
1070 return NewEdits.takeError();
1071 return llvm::Error::success();
1072}
1073
1074// Workaround for editors that have buggy handling of newlines at end of file.
1075//
1076// The editor is supposed to expose document contents over LSP as an exact
1077// string, with whitespace and newlines well-defined. But internally many
1078// editors treat text as an array of lines, and there can be ambiguity over
1079// whether the last line ends with a newline or not.
1080//
1081// This confusion can lead to incorrect edits being sent. Failing to apply them
1082// is catastrophic: we're desynced, LSP has no mechanism to get back in sync.
1083// We apply a heuristic to avoid this state.
1084//
1085// If our current view of an N-line file does *not* end in a newline, but the
1086// editor refers to the start of the next line (an impossible location), then
1087// we silently add a newline to make this valid.
1088// We will still validate that the rangeLength is correct, *including* the
1089// inferred newline.
1090//
1091// See https://github.com/neovim/neovim/issues/17085
1092static void inferFinalNewline(llvm::Expected<size_t> &Err,
1093 std::string &Contents, const Position &Pos) {
1094 if (Err)
1095 return;
1096 if (!Contents.empty() && Contents.back() == '\n')
1097 return;
1098 if (Pos.character != 0)
1099 return;
1100 if (Pos.line != llvm::count(Range&: Contents, Element: '\n') + 1)
1101 return;
1102 log(Fmt: "Editor sent invalid change coordinates, inferring newline at EOF");
1103 Contents.push_back(c: '\n');
1104 consumeError(Err: Err.takeError());
1105 Err = Contents.size();
1106}
1107
1108llvm::Error applyChange(std::string &Contents,
1109 const TextDocumentContentChangeEvent &Change) {
1110 if (!Change.range) {
1111 Contents = Change.text;
1112 return llvm::Error::success();
1113 }
1114
1115 const Position &Start = Change.range->start;
1116 llvm::Expected<size_t> StartIndex = positionToOffset(Code: Contents, P: Start, AllowColumnsBeyondLineLength: false);
1117 inferFinalNewline(Err&: StartIndex, Contents, Pos: Start);
1118 if (!StartIndex)
1119 return StartIndex.takeError();
1120
1121 const Position &End = Change.range->end;
1122 llvm::Expected<size_t> EndIndex = positionToOffset(Code: Contents, P: End, AllowColumnsBeyondLineLength: false);
1123 inferFinalNewline(Err&: EndIndex, Contents, Pos: End);
1124 if (!EndIndex)
1125 return EndIndex.takeError();
1126
1127 if (*EndIndex < *StartIndex)
1128 return error(EC: llvm::errc::invalid_argument,
1129 Fmt: "Range's end position ({0}) is before start position ({1})",
1130 Vals: End, Vals: Start);
1131
1132 // Since the range length between two LSP positions is dependent on the
1133 // contents of the buffer we compute the range length between the start and
1134 // end position ourselves and compare it to the range length of the LSP
1135 // message to verify the buffers of the client and server are in sync.
1136
1137 // EndIndex and StartIndex are in bytes, but Change.rangeLength is in UTF-16
1138 // code units.
1139 ssize_t ComputedRangeLength =
1140 lspLength(Code: Contents.substr(pos: *StartIndex, n: *EndIndex - *StartIndex));
1141
1142 if (Change.rangeLength && ComputedRangeLength != *Change.rangeLength)
1143 return error(EC: llvm::errc::invalid_argument,
1144 Fmt: "Change's rangeLength ({0}) doesn't match the "
1145 "computed range length ({1}).",
1146 Vals: *Change.rangeLength, Vals&: ComputedRangeLength);
1147
1148 Contents.replace(pos: *StartIndex, n: *EndIndex - *StartIndex, str: Change.text);
1149
1150 return llvm::Error::success();
1151}
1152
1153EligibleRegion getEligiblePoints(llvm::StringRef Code,
1154 llvm::StringRef FullyQualifiedName,
1155 const LangOptions &LangOpts) {
1156 EligibleRegion ER;
1157 // Start with global namespace.
1158 std::vector<std::string> Enclosing = {""};
1159 // FIXME: In addition to namespaces try to generate events for function
1160 // definitions as well. One might use a closing parantheses(")" followed by an
1161 // opening brace "{" to trigger the start.
1162 parseNamespaceEvents(Code, LangOpts, Callback: [&](NamespaceEvent Event) {
1163 // Using Directives only introduces declarations to current scope, they do
1164 // not change the current namespace, so skip them.
1165 if (Event.Trigger == NamespaceEvent::UsingDirective)
1166 return;
1167 // Do not qualify the global namespace.
1168 if (!Event.Payload.empty())
1169 Event.Payload.append(s: "::");
1170
1171 std::string CurrentNamespace;
1172 if (Event.Trigger == NamespaceEvent::BeginNamespace) {
1173 Enclosing.emplace_back(args: std::move(Event.Payload));
1174 CurrentNamespace = Enclosing.back();
1175 // parseNameSpaceEvents reports the beginning position of a token; we want
1176 // to insert after '{', so increment by one.
1177 ++Event.Pos.character;
1178 } else {
1179 // Event.Payload points to outer namespace when exiting a scope, so use
1180 // the namespace we've last entered instead.
1181 CurrentNamespace = std::move(Enclosing.back());
1182 Enclosing.pop_back();
1183 assert(Enclosing.back() == Event.Payload);
1184 }
1185
1186 // Ignore namespaces that are not a prefix of the target.
1187 if (!FullyQualifiedName.starts_with(Prefix: CurrentNamespace))
1188 return;
1189
1190 // Prefer the namespace that shares the longest prefix with target.
1191 if (CurrentNamespace.size() > ER.EnclosingNamespace.size()) {
1192 ER.EligiblePoints.clear();
1193 ER.EnclosingNamespace = CurrentNamespace;
1194 }
1195 if (CurrentNamespace.size() == ER.EnclosingNamespace.size())
1196 ER.EligiblePoints.emplace_back(args: std::move(Event.Pos));
1197 });
1198 // If there were no shared namespaces just return EOF.
1199 if (ER.EligiblePoints.empty()) {
1200 assert(ER.EnclosingNamespace.empty());
1201 ER.EligiblePoints.emplace_back(args: offsetToPosition(Code, Offset: Code.size()));
1202 }
1203 return ER;
1204}
1205
1206bool isHeaderFile(llvm::StringRef FileName,
1207 std::optional<LangOptions> LangOpts) {
1208 // Respect the langOpts, for non-file-extension cases, e.g. standard library
1209 // files.
1210 if (LangOpts && LangOpts->IsHeaderFile)
1211 return true;
1212 namespace types = clang::driver::types;
1213 auto Lang = types::lookupTypeForExtension(
1214 Ext: llvm::sys::path::extension(path: FileName).substr(Start: 1));
1215 return Lang != types::TY_INVALID && types::onlyPrecompileType(Id: Lang);
1216}
1217
1218bool isProtoFile(SourceLocation Loc, const SourceManager &SM) {
1219 auto FileName = SM.getFilename(SpellingLoc: Loc);
1220 if (!FileName.ends_with(Suffix: ".proto.h") && !FileName.ends_with(Suffix: ".pb.h"))
1221 return false;
1222 auto FID = SM.getFileID(SpellingLoc: Loc);
1223 // All proto generated headers should start with this line.
1224 static const char *ProtoHeaderComment =
1225 "// Generated by the protocol buffer compiler. DO NOT EDIT!";
1226 // Double check that this is an actual protobuf header.
1227 return SM.getBufferData(FID).starts_with(Prefix: ProtoHeaderComment);
1228}
1229
1230SourceLocation translatePreamblePatchLocation(SourceLocation Loc,
1231 const SourceManager &SM) {
1232 auto DefFile = SM.getFileID(SpellingLoc: Loc);
1233 if (auto FE = SM.getFileEntryRefForID(FID: DefFile)) {
1234 auto IncludeLoc = SM.getIncludeLoc(FID: DefFile);
1235 // Preamble patch is included inside the builtin file.
1236 if (IncludeLoc.isValid() && SM.isWrittenInBuiltinFile(Loc: IncludeLoc) &&
1237 FE->getName().ends_with(Suffix: PreamblePatch::HeaderName)) {
1238 auto Presumed = SM.getPresumedLoc(Loc);
1239 // Check that line directive is pointing at main file.
1240 if (Presumed.isValid() && Presumed.getFileID().isInvalid() &&
1241 isMainFile(FileName: Presumed.getFilename(), SM)) {
1242 Loc = SM.translateLineCol(FID: SM.getMainFileID(), Line: Presumed.getLine(),
1243 Col: Presumed.getColumn());
1244 }
1245 }
1246 }
1247 return Loc;
1248}
1249
1250clangd::Range rangeTillEOL(llvm::StringRef Code, unsigned HashOffset) {
1251 clangd::Range Result;
1252 Result.end = Result.start = offsetToPosition(Code, Offset: HashOffset);
1253
1254 // Span the warning until the EOL or EOF.
1255 Result.end.character +=
1256 lspLength(Code: Code.drop_front(N: HashOffset).take_until(F: [](char C) {
1257 return C == '\n' || C == '\r';
1258 }));
1259 return Result;
1260}
1261} // namespace clangd
1262} // namespace clang
1263

source code of clang-tools-extra/clangd/SourceCode.cpp