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