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 "Context.h"
11 #include "FuzzyMatch.h"
12 #include "Logger.h"
13 #include "Protocol.h"
14 #include "clang/AST/ASTContext.h"
15 #include "clang/Basic/LangOptions.h"
16 #include "clang/Basic/SourceLocation.h"
17 #include "clang/Basic/SourceManager.h"
18 #include "clang/Basic/TokenKinds.h"
19 #include "clang/Format/Format.h"
20 #include "clang/Lex/Lexer.h"
21 #include "clang/Lex/Preprocessor.h"
22 #include "llvm/ADT/None.h"
23 #include "llvm/ADT/StringExtras.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/Support/Compiler.h"
26 #include "llvm/Support/Errc.h"
27 #include "llvm/Support/Error.h"
28 #include "llvm/Support/ErrorHandling.h"
29 #include "llvm/Support/Path.h"
30 #include "llvm/Support/xxhash.h"
31 #include <algorithm>
32
33 namespace clang {
34 namespace clangd {
35
36 // Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
37 // Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
38
39 // Iterates over unicode codepoints in the (UTF-8) string. For each,
40 // invokes CB(UTF-8 length, UTF-16 length), and breaks if it returns true.
41 // Returns true if CB returned true, false if we hit the end of string.
42 template <typename Callback>
iterateCodepoints(llvm::StringRef U8,const Callback & CB)43 static bool iterateCodepoints(llvm::StringRef U8, const Callback &CB) {
44 // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
45 // Astral codepoints are encoded as 4 bytes in UTF-8, starting with 11110xxx.
46 for (size_t I = 0; I < U8.size();) {
47 unsigned char C = static_cast<unsigned char>(U8[I]);
48 if (LLVM_LIKELY(!(C & 0x80))) { // ASCII character.
49 if (CB(1, 1))
50 return true;
51 ++I;
52 continue;
53 }
54 // This convenient property of UTF-8 holds for all non-ASCII characters.
55 size_t UTF8Length = llvm::countLeadingOnes(C);
56 // 0xxx is ASCII, handled above. 10xxx is a trailing byte, invalid here.
57 // 11111xxx is not valid UTF-8 at all. Assert because it's probably our bug.
58 assert((UTF8Length >= 2 && UTF8Length <= 4) &&
59 "Invalid UTF-8, or transcoding bug?");
60 I += UTF8Length; // Skip over all trailing bytes.
61 // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
62 // Astral codepoints are encoded as 4 bytes in UTF-8 (11110xxx ...)
63 if (CB(UTF8Length, UTF8Length == 4 ? 2 : 1))
64 return true;
65 }
66 return false;
67 }
68
69 // Returns the byte offset into the string that is an offset of \p Units in
70 // the specified encoding.
71 // Conceptually, this converts to the encoding, truncates to CodeUnits,
72 // converts back to UTF-8, and returns the length in bytes.
measureUnits(llvm::StringRef U8,int Units,OffsetEncoding Enc,bool & Valid)73 static size_t measureUnits(llvm::StringRef U8, int Units, OffsetEncoding Enc,
74 bool &Valid) {
75 Valid = Units >= 0;
76 if (Units <= 0)
77 return 0;
78 size_t Result = 0;
79 switch (Enc) {
80 case OffsetEncoding::UTF8:
81 Result = Units;
82 break;
83 case OffsetEncoding::UTF16:
84 Valid = iterateCodepoints(U8, [&](int U8Len, int U16Len) {
85 Result += U8Len;
86 Units -= U16Len;
87 return Units <= 0;
88 });
89 if (Units < 0) // Offset in the middle of a surrogate pair.
90 Valid = false;
91 break;
92 case OffsetEncoding::UTF32:
93 Valid = iterateCodepoints(U8, [&](int U8Len, int U16Len) {
94 Result += U8Len;
95 Units--;
96 return Units <= 0;
97 });
98 break;
99 case OffsetEncoding::UnsupportedEncoding:
100 llvm_unreachable("unsupported encoding");
101 }
102 // Don't return an out-of-range index if we overran.
103 if (Result > U8.size()) {
104 Valid = false;
105 return U8.size();
106 }
107 return Result;
108 }
109
110 Key<OffsetEncoding> kCurrentOffsetEncoding;
lspEncoding()111 static OffsetEncoding lspEncoding() {
112 auto *Enc = Context::current().get(kCurrentOffsetEncoding);
113 return Enc ? *Enc : OffsetEncoding::UTF16;
114 }
115
116 // Like most strings in clangd, the input is UTF-8 encoded.
lspLength(llvm::StringRef Code)117 size_t lspLength(llvm::StringRef Code) {
118 size_t Count = 0;
119 switch (lspEncoding()) {
120 case OffsetEncoding::UTF8:
121 Count = Code.size();
122 break;
123 case OffsetEncoding::UTF16:
124 iterateCodepoints(Code, [&](int U8Len, int U16Len) {
125 Count += U16Len;
126 return false;
127 });
128 break;
129 case OffsetEncoding::UTF32:
130 iterateCodepoints(Code, [&](int U8Len, int U16Len) {
131 ++Count;
132 return false;
133 });
134 break;
135 case OffsetEncoding::UnsupportedEncoding:
136 llvm_unreachable("unsupported encoding");
137 }
138 return Count;
139 }
140
positionToOffset(llvm::StringRef Code,Position P,bool AllowColumnsBeyondLineLength)141 llvm::Expected<size_t> positionToOffset(llvm::StringRef Code, Position P,
142 bool AllowColumnsBeyondLineLength) {
143 if (P.line < 0)
144 return llvm::make_error<llvm::StringError>(
145 llvm::formatv("Line value can't be negative ({0})", P.line),
146 llvm::errc::invalid_argument);
147 if (P.character < 0)
148 return llvm::make_error<llvm::StringError>(
149 llvm::formatv("Character value can't be negative ({0})", P.character),
150 llvm::errc::invalid_argument);
151 size_t StartOfLine = 0;
152 for (int I = 0; I != P.line; ++I) {
153 size_t NextNL = Code.find('\n', StartOfLine);
154 if (NextNL == llvm::StringRef::npos)
155 return llvm::make_error<llvm::StringError>(
156 llvm::formatv("Line value is out of range ({0})", P.line),
157 llvm::errc::invalid_argument);
158 StartOfLine = NextNL + 1;
159 }
160 StringRef Line =
161 Code.substr(StartOfLine).take_until([](char C) { return C == '\n'; });
162
163 // P.character may be in UTF-16, transcode if necessary.
164 bool Valid;
165 size_t ByteInLine = measureUnits(Line, P.character, lspEncoding(), Valid);
166 if (!Valid && !AllowColumnsBeyondLineLength)
167 return llvm::make_error<llvm::StringError>(
168 llvm::formatv("{0} offset {1} is invalid for line {2}", lspEncoding(),
169 P.character, P.line),
170 llvm::errc::invalid_argument);
171 return StartOfLine + ByteInLine;
172 }
173
offsetToPosition(llvm::StringRef Code,size_t Offset)174 Position offsetToPosition(llvm::StringRef Code, size_t Offset) {
175 Offset = std::min(Code.size(), Offset);
176 llvm::StringRef Before = Code.substr(0, Offset);
177 int Lines = Before.count('\n');
178 size_t PrevNL = Before.rfind('\n');
179 size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
180 Position Pos;
181 Pos.line = Lines;
182 Pos.character = lspLength(Before.substr(StartOfLine));
183 return Pos;
184 }
185
sourceLocToPosition(const SourceManager & SM,SourceLocation Loc)186 Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc) {
187 // We use the SourceManager's line tables, but its column number is in bytes.
188 FileID FID;
189 unsigned Offset;
190 std::tie(FID, Offset) = SM.getDecomposedSpellingLoc(Loc);
191 Position P;
192 P.line = static_cast<int>(SM.getLineNumber(FID, Offset)) - 1;
193 bool Invalid = false;
194 llvm::StringRef Code = SM.getBufferData(FID, &Invalid);
195 if (!Invalid) {
196 auto ColumnInBytes = SM.getColumnNumber(FID, Offset) - 1;
197 auto LineSoFar = Code.substr(Offset - ColumnInBytes, ColumnInBytes);
198 P.character = lspLength(LineSoFar);
199 }
200 return P;
201 }
202
getTokenRange(const SourceManager & SM,const LangOptions & LangOpts,SourceLocation TokLoc)203 llvm::Optional<Range> getTokenRange(const SourceManager &SM,
204 const LangOptions &LangOpts,
205 SourceLocation TokLoc) {
206 if (!TokLoc.isValid())
207 return llvm::None;
208 SourceLocation End = Lexer::getLocForEndOfToken(TokLoc, 0, SM, LangOpts);
209 if (!End.isValid())
210 return llvm::None;
211 return halfOpenToRange(SM, CharSourceRange::getCharRange(TokLoc, End));
212 }
213
isValidFileRange(const SourceManager & Mgr,SourceRange R)214 bool isValidFileRange(const SourceManager &Mgr, SourceRange R) {
215 if (!R.getBegin().isValid() || !R.getEnd().isValid())
216 return false;
217
218 FileID BeginFID;
219 size_t BeginOffset = 0;
220 std::tie(BeginFID, BeginOffset) = Mgr.getDecomposedLoc(R.getBegin());
221
222 FileID EndFID;
223 size_t EndOffset = 0;
224 std::tie(EndFID, EndOffset) = Mgr.getDecomposedLoc(R.getEnd());
225
226 return BeginFID.isValid() && BeginFID == EndFID && BeginOffset <= EndOffset;
227 }
228
halfOpenRangeContains(const SourceManager & Mgr,SourceRange R,SourceLocation L)229 bool halfOpenRangeContains(const SourceManager &Mgr, SourceRange R,
230 SourceLocation L) {
231 assert(isValidFileRange(Mgr, R));
232
233 FileID BeginFID;
234 size_t BeginOffset = 0;
235 std::tie(BeginFID, BeginOffset) = Mgr.getDecomposedLoc(R.getBegin());
236 size_t EndOffset = Mgr.getFileOffset(R.getEnd());
237
238 FileID LFid;
239 size_t LOffset;
240 std::tie(LFid, LOffset) = Mgr.getDecomposedLoc(L);
241 return BeginFID == LFid && BeginOffset <= LOffset && LOffset < EndOffset;
242 }
243
halfOpenRangeTouches(const SourceManager & Mgr,SourceRange R,SourceLocation L)244 bool halfOpenRangeTouches(const SourceManager &Mgr, SourceRange R,
245 SourceLocation L) {
246 return L == R.getEnd() || halfOpenRangeContains(Mgr, R, L);
247 }
248
getTokenLengthAtLoc(SourceLocation Loc,const SourceManager & SM,const LangOptions & LangOpts)249 static unsigned getTokenLengthAtLoc(SourceLocation Loc, const SourceManager &SM,
250 const LangOptions &LangOpts) {
251 Token TheTok;
252 if (Lexer::getRawToken(Loc, TheTok, SM, LangOpts))
253 return 0;
254 // FIXME: Here we check whether the token at the location is a greatergreater
255 // (>>) token and consider it as a single greater (>). This is to get it
256 // working for templates but it isn't correct for the right shift operator. We
257 // can avoid this by using half open char ranges in getFileRange() but getting
258 // token ending is not well supported in macroIDs.
259 if (TheTok.is(tok::greatergreater))
260 return 1;
261 return TheTok.getLength();
262 }
263
264 // Returns location of the last character of the token at a given loc
getLocForTokenEnd(SourceLocation BeginLoc,const SourceManager & SM,const LangOptions & LangOpts)265 static SourceLocation getLocForTokenEnd(SourceLocation BeginLoc,
266 const SourceManager &SM,
267 const LangOptions &LangOpts) {
268 unsigned Len = getTokenLengthAtLoc(BeginLoc, SM, LangOpts);
269 return BeginLoc.getLocWithOffset(Len ? Len - 1 : 0);
270 }
271
272 // Returns location of the starting of the token at a given EndLoc
getLocForTokenBegin(SourceLocation EndLoc,const SourceManager & SM,const LangOptions & LangOpts)273 static SourceLocation getLocForTokenBegin(SourceLocation EndLoc,
274 const SourceManager &SM,
275 const LangOptions &LangOpts) {
276 return EndLoc.getLocWithOffset(
277 -(signed)getTokenLengthAtLoc(EndLoc, SM, LangOpts));
278 }
279
280 // Converts a char source range to a token range.
toTokenRange(CharSourceRange Range,const SourceManager & SM,const LangOptions & LangOpts)281 static SourceRange toTokenRange(CharSourceRange Range, const SourceManager &SM,
282 const LangOptions &LangOpts) {
283 if (!Range.isTokenRange())
284 Range.setEnd(getLocForTokenBegin(Range.getEnd(), SM, LangOpts));
285 return Range.getAsRange();
286 }
287 // Returns the union of two token ranges.
288 // To find the maximum of the Ends of the ranges, we compare the location of the
289 // last character of the token.
unionTokenRange(SourceRange R1,SourceRange R2,const SourceManager & SM,const LangOptions & LangOpts)290 static SourceRange unionTokenRange(SourceRange R1, SourceRange R2,
291 const SourceManager &SM,
292 const LangOptions &LangOpts) {
293 SourceLocation E1 = getLocForTokenEnd(R1.getEnd(), SM, LangOpts);
294 SourceLocation E2 = getLocForTokenEnd(R2.getEnd(), SM, LangOpts);
295 return SourceRange(std::min(R1.getBegin(), R2.getBegin()),
296 E1 < E2 ? R2.getEnd() : R1.getEnd());
297 }
298
299 // Check if two locations have the same file id.
inSameFile(SourceLocation Loc1,SourceLocation Loc2,const SourceManager & SM)300 static bool inSameFile(SourceLocation Loc1, SourceLocation Loc2,
301 const SourceManager &SM) {
302 return SM.getFileID(Loc1) == SM.getFileID(Loc2);
303 }
304
305 // Find an expansion range (not necessarily immediate) the ends of which are in
306 // the same file id.
307 static SourceRange
getExpansionTokenRangeInSameFile(SourceLocation Loc,const SourceManager & SM,const LangOptions & LangOpts)308 getExpansionTokenRangeInSameFile(SourceLocation Loc, const SourceManager &SM,
309 const LangOptions &LangOpts) {
310 SourceRange ExpansionRange =
311 toTokenRange(SM.getImmediateExpansionRange(Loc), SM, LangOpts);
312 // Fast path for most common cases.
313 if (inSameFile(ExpansionRange.getBegin(), ExpansionRange.getEnd(), SM))
314 return ExpansionRange;
315 // Record the stack of expansion locations for the beginning, keyed by FileID.
316 llvm::DenseMap<FileID, SourceLocation> BeginExpansions;
317 for (SourceLocation Begin = ExpansionRange.getBegin(); Begin.isValid();
318 Begin = Begin.isFileID()
319 ? SourceLocation()
320 : SM.getImmediateExpansionRange(Begin).getBegin()) {
321 BeginExpansions[SM.getFileID(Begin)] = Begin;
322 }
323 // Move up the stack of expansion locations for the end until we find the
324 // location in BeginExpansions with that has the same file id.
325 for (SourceLocation End = ExpansionRange.getEnd(); End.isValid();
326 End = End.isFileID() ? SourceLocation()
327 : toTokenRange(SM.getImmediateExpansionRange(End),
328 SM, LangOpts)
329 .getEnd()) {
330 auto It = BeginExpansions.find(SM.getFileID(End));
331 if (It != BeginExpansions.end())
332 return {It->second, End};
333 }
334 llvm_unreachable(
335 "We should able to find a common ancestor in the expansion tree.");
336 }
337 // Returns the file range for a given Location as a Token Range
338 // This is quite similar to getFileLoc in SourceManager as both use
339 // getImmediateExpansionRange and getImmediateSpellingLoc (for macro IDs).
340 // However:
341 // - We want to maintain the full range information as we move from one file to
342 // the next. getFileLoc only uses the BeginLoc of getImmediateExpansionRange.
343 // - We want to split '>>' tokens as the lexer parses the '>>' in nested
344 // template instantiations as a '>>' instead of two '>'s.
345 // There is also getExpansionRange but it simply calls
346 // getImmediateExpansionRange on the begin and ends separately which is wrong.
getTokenFileRange(SourceLocation Loc,const SourceManager & SM,const LangOptions & LangOpts)347 static SourceRange getTokenFileRange(SourceLocation Loc,
348 const SourceManager &SM,
349 const LangOptions &LangOpts) {
350 SourceRange FileRange = Loc;
351 while (!FileRange.getBegin().isFileID()) {
352 if (SM.isMacroArgExpansion(FileRange.getBegin())) {
353 FileRange = unionTokenRange(
354 SM.getImmediateSpellingLoc(FileRange.getBegin()),
355 SM.getImmediateSpellingLoc(FileRange.getEnd()), SM, LangOpts);
356 assert(inSameFile(FileRange.getBegin(), FileRange.getEnd(), SM));
357 } else {
358 SourceRange ExpansionRangeForBegin =
359 getExpansionTokenRangeInSameFile(FileRange.getBegin(), SM, LangOpts);
360 SourceRange ExpansionRangeForEnd =
361 getExpansionTokenRangeInSameFile(FileRange.getEnd(), SM, LangOpts);
362 assert(inSameFile(ExpansionRangeForBegin.getBegin(),
363 ExpansionRangeForEnd.getBegin(), SM) &&
364 "Both Expansion ranges should be in same file.");
365 FileRange = unionTokenRange(ExpansionRangeForBegin, ExpansionRangeForEnd,
366 SM, LangOpts);
367 }
368 }
369 return FileRange;
370 }
371
isInsideMainFile(SourceLocation Loc,const SourceManager & SM)372 bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM) {
373 return Loc.isValid() && SM.isWrittenInMainFile(SM.getExpansionLoc(Loc));
374 }
375
toHalfOpenFileRange(const SourceManager & SM,const LangOptions & LangOpts,SourceRange R)376 llvm::Optional<SourceRange> toHalfOpenFileRange(const SourceManager &SM,
377 const LangOptions &LangOpts,
378 SourceRange R) {
379 SourceRange R1 = getTokenFileRange(R.getBegin(), SM, LangOpts);
380 if (!isValidFileRange(SM, R1))
381 return llvm::None;
382
383 SourceRange R2 = getTokenFileRange(R.getEnd(), SM, LangOpts);
384 if (!isValidFileRange(SM, R2))
385 return llvm::None;
386
387 SourceRange Result = unionTokenRange(R1, R2, SM, LangOpts);
388 unsigned TokLen = getTokenLengthAtLoc(Result.getEnd(), SM, LangOpts);
389 // Convert from closed token range to half-open (char) range
390 Result.setEnd(Result.getEnd().getLocWithOffset(TokLen));
391 if (!isValidFileRange(SM, Result))
392 return llvm::None;
393
394 return Result;
395 }
396
toSourceCode(const SourceManager & SM,SourceRange R)397 llvm::StringRef toSourceCode(const SourceManager &SM, SourceRange R) {
398 assert(isValidFileRange(SM, R));
399 bool Invalid = false;
400 auto *Buf = SM.getBuffer(SM.getFileID(R.getBegin()), &Invalid);
401 assert(!Invalid);
402
403 size_t BeginOffset = SM.getFileOffset(R.getBegin());
404 size_t EndOffset = SM.getFileOffset(R.getEnd());
405 return Buf->getBuffer().substr(BeginOffset, EndOffset - BeginOffset);
406 }
407
sourceLocationInMainFile(const SourceManager & SM,Position P)408 llvm::Expected<SourceLocation> sourceLocationInMainFile(const SourceManager &SM,
409 Position P) {
410 llvm::StringRef Code = SM.getBuffer(SM.getMainFileID())->getBuffer();
411 auto Offset =
412 positionToOffset(Code, P, /*AllowColumnBeyondLineLength=*/false);
413 if (!Offset)
414 return Offset.takeError();
415 return SM.getLocForStartOfFile(SM.getMainFileID()).getLocWithOffset(*Offset);
416 }
417
halfOpenToRange(const SourceManager & SM,CharSourceRange R)418 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
419 // Clang is 1-based, LSP uses 0-based indexes.
420 Position Begin = sourceLocToPosition(SM, R.getBegin());
421 Position End = sourceLocToPosition(SM, R.getEnd());
422
423 return {Begin, End};
424 }
425
offsetToClangLineColumn(llvm::StringRef Code,size_t Offset)426 std::pair<size_t, size_t> offsetToClangLineColumn(llvm::StringRef Code,
427 size_t Offset) {
428 Offset = std::min(Code.size(), Offset);
429 llvm::StringRef Before = Code.substr(0, Offset);
430 int Lines = Before.count('\n');
431 size_t PrevNL = Before.rfind('\n');
432 size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
433 return {Lines + 1, Offset - StartOfLine + 1};
434 }
435
splitQualifiedName(StringRef QName)436 std::pair<StringRef, StringRef> splitQualifiedName(StringRef QName) {
437 size_t Pos = QName.rfind("::");
438 if (Pos == llvm::StringRef::npos)
439 return {llvm::StringRef(), QName};
440 return {QName.substr(0, Pos + 2), QName.substr(Pos + 2)};
441 }
442
replacementToEdit(llvm::StringRef Code,const tooling::Replacement & R)443 TextEdit replacementToEdit(llvm::StringRef Code,
444 const tooling::Replacement &R) {
445 Range ReplacementRange = {
446 offsetToPosition(Code, R.getOffset()),
447 offsetToPosition(Code, R.getOffset() + R.getLength())};
448 return {ReplacementRange, R.getReplacementText()};
449 }
450
replacementsToEdits(llvm::StringRef Code,const tooling::Replacements & Repls)451 std::vector<TextEdit> replacementsToEdits(llvm::StringRef Code,
452 const tooling::Replacements &Repls) {
453 std::vector<TextEdit> Edits;
454 for (const auto &R : Repls)
455 Edits.push_back(replacementToEdit(Code, R));
456 return Edits;
457 }
458
getCanonicalPath(const FileEntry * F,const SourceManager & SourceMgr)459 llvm::Optional<std::string> getCanonicalPath(const FileEntry *F,
460 const SourceManager &SourceMgr) {
461 if (!F)
462 return None;
463
464 llvm::SmallString<128> FilePath = F->getName();
465 if (!llvm::sys::path::is_absolute(FilePath)) {
466 if (auto EC =
467 SourceMgr.getFileManager().getVirtualFileSystem().makeAbsolute(
468 FilePath)) {
469 elog("Could not turn relative path '{0}' to absolute: {1}", FilePath,
470 EC.message());
471 return None;
472 }
473 }
474
475 // Handle the symbolic link path case where the current working directory
476 // (getCurrentWorkingDirectory) is a symlink./ We always want to the real
477 // file path (instead of the symlink path) for the C++ symbols.
478 //
479 // Consider the following example:
480 //
481 // src dir: /project/src/foo.h
482 // current working directory (symlink): /tmp/build -> /project/src/
483 //
484 // The file path of Symbol is "/project/src/foo.h" instead of
485 // "/tmp/build/foo.h"
486 if (const DirectoryEntry *Dir = SourceMgr.getFileManager().getDirectory(
487 llvm::sys::path::parent_path(FilePath))) {
488 llvm::SmallString<128> RealPath;
489 llvm::StringRef DirName = SourceMgr.getFileManager().getCanonicalName(Dir);
490 llvm::sys::path::append(RealPath, DirName,
491 llvm::sys::path::filename(FilePath));
492 return RealPath.str().str();
493 }
494
495 return FilePath.str().str();
496 }
497
toTextEdit(const FixItHint & FixIt,const SourceManager & M,const LangOptions & L)498 TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M,
499 const LangOptions &L) {
500 TextEdit Result;
501 Result.range =
502 halfOpenToRange(M, Lexer::makeFileCharRange(FixIt.RemoveRange, M, L));
503 Result.newText = FixIt.CodeToInsert;
504 return Result;
505 }
506
isRangeConsecutive(const Range & Left,const Range & Right)507 bool isRangeConsecutive(const Range &Left, const Range &Right) {
508 return Left.end.line == Right.start.line &&
509 Left.end.character == Right.start.character;
510 }
511
digest(llvm::StringRef Content)512 FileDigest digest(llvm::StringRef Content) {
513 uint64_t Hash{llvm::xxHash64(Content)};
514 FileDigest Result;
515 for (unsigned I = 0; I < Result.size(); ++I) {
516 Result[I] = uint8_t(Hash);
517 Hash >>= 8;
518 }
519 return Result;
520 }
521
digestFile(const SourceManager & SM,FileID FID)522 llvm::Optional<FileDigest> digestFile(const SourceManager &SM, FileID FID) {
523 bool Invalid = false;
524 llvm::StringRef Content = SM.getBufferData(FID, &Invalid);
525 if (Invalid)
526 return None;
527 return digest(Content);
528 }
529
getFormatStyleForFile(llvm::StringRef File,llvm::StringRef Content,llvm::vfs::FileSystem * FS)530 format::FormatStyle getFormatStyleForFile(llvm::StringRef File,
531 llvm::StringRef Content,
532 llvm::vfs::FileSystem *FS) {
533 auto Style = format::getStyle(format::DefaultFormatStyle, File,
534 format::DefaultFallbackStyle, Content, FS);
535 if (!Style) {
536 log("getStyle() failed for file {0}: {1}. Fallback is LLVM style.", File,
537 Style.takeError());
538 Style = format::getLLVMStyle();
539 }
540 return *Style;
541 }
542
543 llvm::Expected<tooling::Replacements>
cleanupAndFormat(StringRef Code,const tooling::Replacements & Replaces,const format::FormatStyle & Style)544 cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
545 const format::FormatStyle &Style) {
546 auto CleanReplaces = cleanupAroundReplacements(Code, Replaces, Style);
547 if (!CleanReplaces)
548 return CleanReplaces;
549 return formatReplacements(Code, std::move(*CleanReplaces), Style);
550 }
551
552 template <typename Action>
lex(llvm::StringRef Code,const format::FormatStyle & Style,Action A)553 static void lex(llvm::StringRef Code, const format::FormatStyle &Style,
554 Action A) {
555 // FIXME: InMemoryFileAdapter crashes unless the buffer is null terminated!
556 std::string NullTerminatedCode = Code.str();
557 SourceManagerForFile FileSM("dummy.cpp", NullTerminatedCode);
558 auto &SM = FileSM.get();
559 auto FID = SM.getMainFileID();
560 Lexer Lex(FID, SM.getBuffer(FID), SM, format::getFormattingLangOpts(Style));
561 Token Tok;
562
563 while (!Lex.LexFromRawLexer(Tok))
564 A(Tok);
565 }
566
collectIdentifiers(llvm::StringRef Content,const format::FormatStyle & Style)567 llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
568 const format::FormatStyle &Style) {
569 llvm::StringMap<unsigned> Identifiers;
570 lex(Content, Style, [&](const clang::Token &Tok) {
571 switch (Tok.getKind()) {
572 case tok::identifier:
573 ++Identifiers[Tok.getIdentifierInfo()->getName()];
574 break;
575 case tok::raw_identifier:
576 ++Identifiers[Tok.getRawIdentifier()];
577 break;
578 default:
579 break;
580 }
581 });
582 return Identifiers;
583 }
584
585 namespace {
586 enum NamespaceEvent {
587 BeginNamespace, // namespace <ns> {. Payload is resolved <ns>.
588 EndNamespace, // } // namespace <ns>. Payload is resolved *outer* namespace.
589 UsingDirective // using namespace <ns>. Payload is unresolved <ns>.
590 };
591 // Scans C++ source code for constructs that change the visible namespaces.
parseNamespaceEvents(llvm::StringRef Code,const format::FormatStyle & Style,llvm::function_ref<void (NamespaceEvent,llvm::StringRef)> Callback)592 void parseNamespaceEvents(
593 llvm::StringRef Code, const format::FormatStyle &Style,
594 llvm::function_ref<void(NamespaceEvent, llvm::StringRef)> Callback) {
595
596 // Stack of enclosing namespaces, e.g. {"clang", "clangd"}
597 std::vector<std::string> Enclosing; // Contains e.g. "clang", "clangd"
598 // Stack counts open braces. true if the brace opened a namespace.
599 std::vector<bool> BraceStack;
600
601 enum {
602 Default,
603 Namespace, // just saw 'namespace'
604 NamespaceName, // just saw 'namespace' NSName
605 Using, // just saw 'using'
606 UsingNamespace, // just saw 'using namespace'
607 UsingNamespaceName, // just saw 'using namespace' NSName
608 } State = Default;
609 std::string NSName;
610
611 lex(Code, Style, [&](const clang::Token &Tok) {
612 switch(Tok.getKind()) {
613 case tok::raw_identifier:
614 // In raw mode, this could be a keyword or a name.
615 switch (State) {
616 case UsingNamespace:
617 case UsingNamespaceName:
618 NSName.append(Tok.getRawIdentifier());
619 State = UsingNamespaceName;
620 break;
621 case Namespace:
622 case NamespaceName:
623 NSName.append(Tok.getRawIdentifier());
624 State = NamespaceName;
625 break;
626 case Using:
627 State =
628 (Tok.getRawIdentifier() == "namespace") ? UsingNamespace : Default;
629 break;
630 case Default:
631 NSName.clear();
632 if (Tok.getRawIdentifier() == "namespace")
633 State = Namespace;
634 else if (Tok.getRawIdentifier() == "using")
635 State = Using;
636 break;
637 }
638 break;
639 case tok::coloncolon:
640 // This can come at the beginning or in the middle of a namespace name.
641 switch (State) {
642 case UsingNamespace:
643 case UsingNamespaceName:
644 NSName.append("::");
645 State = UsingNamespaceName;
646 break;
647 case NamespaceName:
648 NSName.append("::");
649 State = NamespaceName;
650 break;
651 case Namespace: // Not legal here.
652 case Using:
653 case Default:
654 State = Default;
655 break;
656 }
657 break;
658 case tok::l_brace:
659 // Record which { started a namespace, so we know when } ends one.
660 if (State == NamespaceName) {
661 // Parsed: namespace <name> {
662 BraceStack.push_back(true);
663 Enclosing.push_back(NSName);
664 Callback(BeginNamespace, llvm::join(Enclosing, "::"));
665 } else {
666 // This case includes anonymous namespaces (State = Namespace).
667 // For our purposes, they're not namespaces and we ignore them.
668 BraceStack.push_back(false);
669 }
670 State = Default;
671 break;
672 case tok::r_brace:
673 // If braces are unmatched, we're going to be confused, but don't crash.
674 if (!BraceStack.empty()) {
675 if (BraceStack.back()) {
676 // Parsed: } // namespace
677 Enclosing.pop_back();
678 Callback(EndNamespace, llvm::join(Enclosing, "::"));
679 }
680 BraceStack.pop_back();
681 }
682 break;
683 case tok::semi:
684 if (State == UsingNamespaceName)
685 // Parsed: using namespace <name> ;
686 Callback(UsingDirective, llvm::StringRef(NSName));
687 State = Default;
688 break;
689 default:
690 State = Default;
691 break;
692 }
693 });
694 }
695
696 // Returns the prefix namespaces of NS: {"" ... NS}.
ancestorNamespaces(llvm::StringRef NS)697 llvm::SmallVector<llvm::StringRef, 8> ancestorNamespaces(llvm::StringRef NS) {
698 llvm::SmallVector<llvm::StringRef, 8> Results;
699 Results.push_back(NS.take_front(0));
700 NS.split(Results, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
701 for (llvm::StringRef &R : Results)
702 R = NS.take_front(R.end() - NS.begin());
703 return Results;
704 }
705
706 } // namespace
707
visibleNamespaces(llvm::StringRef Code,const format::FormatStyle & Style)708 std::vector<std::string> visibleNamespaces(llvm::StringRef Code,
709 const format::FormatStyle &Style) {
710 std::string Current;
711 // Map from namespace to (resolved) namespaces introduced via using directive.
712 llvm::StringMap<llvm::StringSet<>> UsingDirectives;
713
714 parseNamespaceEvents(Code, Style,
715 [&](NamespaceEvent Event, llvm::StringRef NS) {
716 switch (Event) {
717 case BeginNamespace:
718 case EndNamespace:
719 Current = NS;
720 break;
721 case UsingDirective:
722 if (NS.consume_front("::"))
723 UsingDirectives[Current].insert(NS);
724 else {
725 for (llvm::StringRef Enclosing :
726 ancestorNamespaces(Current)) {
727 if (Enclosing.empty())
728 UsingDirectives[Current].insert(NS);
729 else
730 UsingDirectives[Current].insert(
731 (Enclosing + "::" + NS).str());
732 }
733 }
734 break;
735 }
736 });
737
738 std::vector<std::string> Found;
739 for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
740 Found.push_back(Enclosing);
741 auto It = UsingDirectives.find(Enclosing);
742 if (It != UsingDirectives.end())
743 for (const auto& Used : It->second)
744 Found.push_back(Used.getKey());
745 }
746
747 llvm::sort(Found, [&](const std::string &LHS, const std::string &RHS) {
748 if (Current == RHS)
749 return false;
750 if (Current == LHS)
751 return true;
752 return LHS < RHS;
753 });
754 Found.erase(std::unique(Found.begin(), Found.end()), Found.end());
755 return Found;
756 }
757
collectWords(llvm::StringRef Content)758 llvm::StringSet<> collectWords(llvm::StringRef Content) {
759 // We assume short words are not significant.
760 // We may want to consider other stopwords, e.g. language keywords.
761 // (A very naive implementation showed no benefit, but lexing might do better)
762 static constexpr int MinWordLength = 4;
763
764 std::vector<CharRole> Roles(Content.size());
765 calculateRoles(Content, Roles);
766
767 llvm::StringSet<> Result;
768 llvm::SmallString<256> Word;
769 auto Flush = [&] {
770 if (Word.size() >= MinWordLength) {
771 for (char &C : Word)
772 C = llvm::toLower(C);
773 Result.insert(Word);
774 }
775 Word.clear();
776 };
777 for (unsigned I = 0; I < Content.size(); ++I) {
778 switch (Roles[I]) {
779 case Head:
780 Flush();
781 LLVM_FALLTHROUGH;
782 case Tail:
783 Word.push_back(Content[I]);
784 break;
785 case Unknown:
786 case Separator:
787 Flush();
788 break;
789 }
790 }
791 Flush();
792
793 return Result;
794 }
795
locateMacroAt(SourceLocation Loc,Preprocessor & PP)796 llvm::Optional<DefinedMacro> locateMacroAt(SourceLocation Loc,
797 Preprocessor &PP) {
798 const auto &SM = PP.getSourceManager();
799 const auto &LangOpts = PP.getLangOpts();
800 Token Result;
801 if (Lexer::getRawToken(SM.getSpellingLoc(Loc), Result, SM, LangOpts, false))
802 return None;
803 if (Result.is(tok::raw_identifier))
804 PP.LookUpIdentifierInfo(Result);
805 IdentifierInfo *IdentifierInfo = Result.getIdentifierInfo();
806 if (!IdentifierInfo || !IdentifierInfo->hadMacroDefinition())
807 return None;
808
809 std::pair<FileID, unsigned int> DecLoc = SM.getDecomposedExpansionLoc(Loc);
810 // Get the definition just before the searched location so that a macro
811 // referenced in a '#undef MACRO' can still be found.
812 SourceLocation BeforeSearchedLocation =
813 SM.getMacroArgExpandedLocation(SM.getLocForStartOfFile(DecLoc.first)
814 .getLocWithOffset(DecLoc.second - 1));
815 MacroDefinition MacroDef =
816 PP.getMacroDefinitionAtLoc(IdentifierInfo, BeforeSearchedLocation);
817 if (auto *MI = MacroDef.getMacroInfo())
818 return DefinedMacro{IdentifierInfo->getName(), MI};
819 return None;
820 }
821
822 } // namespace clangd
823 } // namespace clang
824