clang-tools-extra/clangd/SourceCode.cpp

   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
  48 namespace clang {
  49 namespace 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.
  62 template <typename Callback>
  63 static 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(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("File has invalid UTF-8 near offset {0}: {1}", I, llvm::toHex(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.
 105 static 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, [&](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, [&](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
 142 Key<OffsetEncoding> kCurrentOffsetEncoding;
 143 static OffsetEncoding lspEncoding() {
 144   auto *Enc = Context::current().get(kCurrentOffsetEncoding);
 145   return Enc ? *Enc : OffsetEncoding::UTF16;
 146 }
 147
 148 // Like most strings in clangd, the input is UTF-8 encoded.
 149 size_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(Code, [&](int U8Len, int U16Len) {
 157       Count += U16Len;
 158       return false;
 159     });
 160     break;
 161   case OffsetEncoding::UTF32:
 162     iterateCodepoints(Code, [&](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
 173 llvm::Expected<size_t> positionToOffset(llvm::StringRef Code, Position P,
 174                                         bool AllowColumnsBeyondLineLength) {
 175   if (P.line < 0)
 176     return error(llvm::errc::invalid_argument,
 177                  "Line value can't be negative ({0})", P.line);
 178   if (P.character < 0)
 179     return error(llvm::errc::invalid_argument,
 180                  "Character value can't be negative ({0})", P.character);
 181   size_t StartOfLine = 0;
 182   for (int I = 0; I != P.line; ++I) {
 183     size_t NextNL = Code.find('\n', StartOfLine);
 184     if (NextNL == llvm::StringRef::npos)
 185       return error(llvm::errc::invalid_argument,
 186                    "Line value is out of range ({0})", P.line);
 187     StartOfLine = NextNL + 1;
 188   }
 189   StringRef Line =
 190       Code.substr(StartOfLine).take_until([](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(Line, P.character, lspEncoding(), Valid);
 195   if (!Valid && !AllowColumnsBeyondLineLength)
 196     return error(llvm::errc::invalid_argument,
 197                  "{0} offset {1} is invalid for line {2}", lspEncoding(),
 198                  P.character, P.line);
 199   return StartOfLine + ByteInLine;
 200 }
 201
 202 Position offsetToPosition(llvm::StringRef Code, size_t Offset) {
 203   Offset = std::min(Code.size(), Offset);
 204   llvm::StringRef Before = Code.substr(0, Offset);
 205   int Lines = Before.count('\n');
 206   size_t PrevNL = Before.rfind('\n');
 207   size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
 208   Position Pos;
 209   Pos.line = Lines;
 210   Pos.character = lspLength(Before.substr(StartOfLine));
 211   return Pos;
 212 }
 213
 214 Position 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(FID, Offset) = SM.getDecomposedSpellingLoc(Loc);
 219   Position P;
 220   P.line = static_cast<int>(SM.getLineNumber(FID, Offset)) - 1;
 221   bool Invalid = false;
 222   llvm::StringRef Code = SM.getBufferData(FID, &Invalid);
 223   if (!Invalid) {
 224     auto ColumnInBytes = SM.getColumnNumber(FID, Offset) - 1;
 225     auto LineSoFar = Code.substr(Offset - ColumnInBytes, ColumnInBytes);
 226     P.character = lspLength(LineSoFar);
 227   }
 228   return P;
 229 }
 230
 231 bool 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(Spelling.first, &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         SM.getComposedLoc(Spelling.first, Spelling.second));
 246   return true;
 247 }
 248
 249 bool 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(BeginFID, BeginOffset) = Mgr.getDecomposedLoc(R.getBegin());
 256
 257   FileID EndFID;
 258   size_t EndOffset = 0;
 259   std::tie(EndFID, EndOffset) = Mgr.getDecomposedLoc(R.getEnd());
 260
 261   return BeginFID.isValid() && BeginFID == EndFID && BeginOffset <= EndOffset;
 262 }
 263
 264 SourceLocation includeHashLoc(FileID IncludedFile, const SourceManager &SM) {
 265   assert(SM.getLocForEndOfFile(IncludedFile).isFileID());
 266   FileID IncludingFile;
 267   unsigned Offset;
 268   std::tie(IncludingFile, Offset) =
 269       SM.getDecomposedExpansionLoc(SM.getIncludeLoc(IncludedFile));
 270   bool Invalid = false;
 271   llvm::StringRef Buf = SM.getBufferData(IncludingFile, &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(IncludingFile, Offset);
 281     if (Buf[Offset] == '\n' || Offset == 0) // no hash, what's going on?
 282       return SourceLocation();
 283   }
 284 }
 285
 286 static unsigned getTokenLengthAtLoc(SourceLocation Loc, const SourceManager &SM,
 287                                     const LangOptions &LangOpts) {
 288   Token TheTok;
 289   if (Lexer::getRawToken(Loc, 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(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
 302 static SourceLocation getLocForTokenEnd(SourceLocation BeginLoc,
 303                                         const SourceManager &SM,
 304                                         const LangOptions &LangOpts) {
 305   unsigned Len = getTokenLengthAtLoc(BeginLoc, SM, LangOpts);
 306   return BeginLoc.getLocWithOffset(Len ? Len - 1 : 0);
 307 }
 308
 309 // Returns location of the starting of the token at a given EndLoc
 310 static SourceLocation getLocForTokenBegin(SourceLocation EndLoc,
 311                                           const SourceManager &SM,
 312                                           const LangOptions &LangOpts) {
 313   return EndLoc.getLocWithOffset(
 314       -(signed)getTokenLengthAtLoc(EndLoc, SM, LangOpts));
 315 }
 316
 317 // Converts a char source range to a token range.
 318 static SourceRange toTokenRange(CharSourceRange Range, const SourceManager &SM,
 319                                 const LangOptions &LangOpts) {
 320   if (!Range.isTokenRange())
 321     Range.setEnd(getLocForTokenBegin(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.
 327 static SourceRange unionTokenRange(SourceRange R1, SourceRange R2,
 328                                    const SourceManager &SM,
 329                                    const LangOptions &LangOpts) {
 330   SourceLocation Begin =
 331       SM.isBeforeInTranslationUnit(R1.getBegin(), R2.getBegin())
 332           ? R1.getBegin()
 333           : R2.getBegin();
 334   SourceLocation End =
 335       SM.isBeforeInTranslationUnit(getLocForTokenEnd(R1.getEnd(), SM, LangOpts),
 336                                    getLocForTokenEnd(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.
 345 static SourceRange rangeInCommonFile(SourceRange R, const SourceManager &SM,
 346                                      const LangOptions &LangOpts) {
 347   // Fast path for most common cases.
 348   if (SM.isWrittenInSameFile(R.getBegin(), 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(SM.getFileID(Begin), SM)
 355                    : SM.getImmediateExpansionRange(Begin).getBegin()) {
 356     BeginExpansions[SM.getFileID(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(SM.getFileID(End), SM)
 362                             : toTokenRange(SM.getImmediateExpansionRange(End),
 363                                            SM, LangOpts)
 364                                   .getEnd()) {
 365     auto It = BeginExpansions.find(SM.getFileID(End));
 366     if (It != BeginExpansions.end()) {
 367       if (SM.getFileOffset(It->second) > SM.getFileOffset(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.
 377 static SourceRange
 378 getExpansionTokenRangeInSameFile(SourceLocation Loc, const SourceManager &SM,
 379                                  const LangOptions &LangOpts) {
 380   return rangeInCommonFile(
 381       toTokenRange(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.
 395 static 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(FileRange.getBegin())) {
 401       FileRange = unionTokenRange(
 402           SM.getImmediateSpellingLoc(FileRange.getBegin()),
 403           SM.getImmediateSpellingLoc(FileRange.getEnd()), SM, LangOpts);
 404       assert(SM.isWrittenInSameFile(FileRange.getBegin(), FileRange.getEnd()));
 405     } else {
 406       SourceRange ExpansionRangeForBegin =
 407           getExpansionTokenRangeInSameFile(FileRange.getBegin(), SM, LangOpts);
 408       SourceRange ExpansionRangeForEnd =
 409           getExpansionTokenRangeInSameFile(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(ExpansionRangeForBegin, ExpansionRangeForEnd,
 417                                   SM, LangOpts);
 418     }
 419   }
 420   return FileRange;
 421 }
 422
 423 bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM) {
 424   if (!Loc.isValid())
 425     return false;
 426   FileID FID = SM.getFileID(SM.getExpansionLoc(Loc));
 427   return FID == SM.getMainFileID() || FID == SM.getPreambleFileID();
 428 }
 429
 430 std::optional<SourceRange> toHalfOpenFileRange(const SourceManager &SM,
 431                                                const LangOptions &LangOpts,
 432                                                SourceRange R) {
 433   SourceRange R1 = getTokenFileRange(R.getBegin(), SM, LangOpts);
 434   if (!isValidFileRange(SM, R1))
 435     return std::nullopt;
 436
 437   SourceRange R2 = getTokenFileRange(R.getEnd(), SM, LangOpts);
 438   if (!isValidFileRange(SM, R2))
 439     return std::nullopt;
 440
 441   SourceRange Result =
 442       rangeInCommonFile(unionTokenRange(R1, R2, SM, LangOpts), SM, LangOpts);
 443   unsigned TokLen = getTokenLengthAtLoc(Result.getEnd(), SM, LangOpts);
 444   // Convert from closed token range to half-open (char) range
 445   Result.setEnd(Result.getEnd().getLocWithOffset(TokLen));
 446   if (!isValidFileRange(SM, Result))
 447     return std::nullopt;
 448
 449   return Result;
 450 }
 451
 452 llvm::StringRef toSourceCode(const SourceManager &SM, SourceRange R) {
 453   assert(isValidFileRange(SM, R));
 454   auto Buf = SM.getBufferOrNone(SM.getFileID(R.getBegin()));
 455   assert(Buf);
 456
 457   size_t BeginOffset = SM.getFileOffset(R.getBegin());
 458   size_t EndOffset = SM.getFileOffset(R.getEnd());
 459   return Buf->getBuffer().substr(BeginOffset, EndOffset - BeginOffset);
 460 }
 461
 462 llvm::Expected<SourceLocation> sourceLocationInMainFile(const SourceManager &SM,
 463                                                         Position P) {
 464   llvm::StringRef Code = SM.getBufferOrFake(SM.getMainFileID()).getBuffer();
 465   auto Offset =
 466       positionToOffset(Code, P, /*AllowColumnsBeyondLineLength=*/false);
 467   if (!Offset)
 468     return Offset.takeError();
 469   return SM.getLocForStartOfFile(SM.getMainFileID()).getLocWithOffset(*Offset);
 470 }
 471
 472 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
 473   // Clang is 1-based, LSP uses 0-based indexes.
 474   Position Begin = sourceLocToPosition(SM, R.getBegin());
 475   Position End = sourceLocToPosition(SM, R.getEnd());
 476
 477   return {Begin, End};
 478 }
 479
 480 void 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
 487 std::pair<size_t, size_t> offsetToClangLineColumn(llvm::StringRef Code,
 488                                                   size_t Offset) {
 489   Offset = std::min(Code.size(), Offset);
 490   llvm::StringRef Before = Code.substr(0, Offset);
 491   int Lines = Before.count('\n');
 492   size_t PrevNL = Before.rfind('\n');
 493   size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
 494   return {Lines + 1, Offset - StartOfLine + 1};
 495 }
 496
 497 std::pair<StringRef, StringRef> splitQualifiedName(StringRef QName) {
 498   size_t Pos = QName.rfind("::");
 499   if (Pos == llvm::StringRef::npos)
 500     return {llvm::StringRef(), QName};
 501   return {QName.substr(0, Pos + 2), QName.substr(Pos + 2)};
 502 }
 503
 504 TextEdit replacementToEdit(llvm::StringRef Code,
 505                            const tooling::Replacement &R) {
 506   Range ReplacementRange = {
 507       offsetToPosition(Code, R.getOffset()),
 508       offsetToPosition(Code, R.getOffset() + R.getLength())};
 509   return {ReplacementRange, std::string(R.getReplacementText())};
 510 }
 511
 512 std::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(replacementToEdit(Code, R));
 517   return Edits;
 518 }
 519
 520 std::optional<std::string> getCanonicalPath(const FileEntryRef F,
 521                                             FileManager &FileMgr) {
 522   llvm::SmallString<128> FilePath = F.getName();
 523   if (!llvm::sys::path::is_absolute(FilePath)) {
 524     if (auto EC =
 525             FileMgr.getVirtualFileSystem().makeAbsolute(
 526                 FilePath)) {
 527       elog("Could not turn relative path '{0}' to absolute: {1}", FilePath,
 528            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           llvm::sys::path::parent_path(FilePath))) {
 546     llvm::SmallString<128> RealPath;
 547     llvm::StringRef DirName = FileMgr.getCanonicalName(*Dir);
 548     llvm::sys::path::append(RealPath, DirName,
 549                             llvm::sys::path::filename(FilePath));
 550     return RealPath.str().str();
 551   }
 552
 553   return FilePath.str().str();
 554 }
 555
 556 TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M,
 557                     const LangOptions &L) {
 558   TextEdit Result;
 559   Result.range =
 560       halfOpenToRange(M, Lexer::makeFileCharRange(FixIt.RemoveRange, M, L));
 561   Result.newText = FixIt.CodeToInsert;
 562   return Result;
 563 }
 564
 565 FileDigest digest(llvm::StringRef Content) {
 566   uint64_t Hash{llvm::xxh3_64bits(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
 575 std::optional<FileDigest> digestFile(const SourceManager &SM, FileID FID) {
 576   bool Invalid = false;
 577   llvm::StringRef Content = SM.getBufferData(FID, &Invalid);
 578   if (Invalid)
 579     return std::nullopt;
 580   return digest(Content);
 581 }
 582
 583 format::FormatStyle getFormatStyleForFile(llvm::StringRef File,
 584                                           llvm::StringRef Content,
 585                                           const ThreadsafeFS &TFS,
 586                                           bool FormatFile) {
 587   // Unless we're formatting a substantial amount of code (the entire file
 588   // or an arbitrarily large range), skip libFormat's heuristic check for
 589   // .h files that tries to determine whether the file contains objective-c
 590   // code. (This is accomplished by passing empty code contents to getStyle().
 591   // The heuristic is the only thing that looks at the contents.)
 592   // This is a workaround for PR60151, a known issue in libFormat where this
 593   // heuristic can OOM on large files. If we *are* formatting the entire file,
 594   // there's no point in doing this because the actual format::reformat() call
 595   // will run into the same OOM; we'd just be risking inconsistencies between
 596   // clangd and clang-format on smaller .h files where they disagree on what
 597   // language is detected.
 598   if (!FormatFile)
 599     Content = {};
 600   auto Style = format::getStyle(format::DefaultFormatStyle, File,
 601                                 format::DefaultFallbackStyle, Content,
 602                                 TFS.view(/*CWD=*/std::nullopt).get());
 603   if (!Style) {
 604     log("getStyle() failed for file {0}: {1}. Fallback is LLVM style.", File,
 605         Style.takeError());
 606     return format::getLLVMStyle();
 607   }
 608   return *Style;
 609 }
 610
 611 llvm::Expected<tooling::Replacements>
 612 cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
 613                  const format::FormatStyle &Style) {
 614   auto CleanReplaces = cleanupAroundReplacements(Code, Replaces, Style);
 615   if (!CleanReplaces)
 616     return CleanReplaces;
 617   return formatReplacements(Code, std::move(*CleanReplaces), Style);
 618 }
 619
 620 static void
 621 lex(llvm::StringRef Code, const LangOptions &LangOpts,
 622     llvm::function_ref<void(const syntax::Token &, const SourceManager &SM)>
 623         Action) {
 624   // FIXME: InMemoryFileAdapter crashes unless the buffer is null terminated!
 625   std::string NullTerminatedCode = Code.str();
 626   SourceManagerForFile FileSM("mock_file_name.cpp", NullTerminatedCode);
 627   auto &SM = FileSM.get();
 628   for (const auto &Tok : syntax::tokenize(SM.getMainFileID(), SM, LangOpts))
 629     Action(Tok, SM);
 630 }
 631
 632 llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
 633                                              const format::FormatStyle &Style) {
 634   llvm::StringMap<unsigned> Identifiers;
 635   auto LangOpt = format::getFormattingLangOpts(Style);
 636   lex(Content, LangOpt, [&](const syntax::Token &Tok, const SourceManager &SM) {
 637     if (Tok.kind() == tok::identifier)
 638       ++Identifiers[Tok.text(SM)];
 639     // FIXME: Should this function really return keywords too ?
 640     else if (const auto *Keyword = tok::getKeywordSpelling(Tok.kind()))
 641       ++Identifiers[Keyword];
 642   });
 643   return Identifiers;
 644 }
 645
 646 std::vector<Range> collectIdentifierRanges(llvm::StringRef Identifier,
 647                                            llvm::StringRef Content,
 648                                            const LangOptions &LangOpts) {
 649   std::vector<Range> Ranges;
 650   lex(Content, LangOpts,
 651       [&](const syntax::Token &Tok, const SourceManager &SM) {
 652         if (Tok.kind() != tok::identifier || Tok.text(SM) != Identifier)
 653           return;
 654         Ranges.push_back(halfOpenToRange(SM, Tok.range(SM).toCharRange(SM)));
 655       });
 656   return Ranges;
 657 }
 658
 659 bool isKeyword(llvm::StringRef NewName, const LangOptions &LangOpts) {
 660   // Keywords are initialized in constructor.
 661   clang::IdentifierTable KeywordsTable(LangOpts);
 662   return KeywordsTable.find(NewName) != KeywordsTable.end();
 663 }
 664
 665 namespace {
 666 struct NamespaceEvent {
 667   enum {
 668     BeginNamespace, // namespace <ns> {.     Payload is resolved <ns>.
 669     EndNamespace,   // } // namespace <ns>.  Payload is resolved *outer*
 670                     // namespace.
 671     UsingDirective  // using namespace <ns>. Payload is unresolved <ns>.
 672   } Trigger;
 673   std::string Payload;
 674   Position Pos;
 675 };
 676 // Scans C++ source code for constructs that change the visible namespaces.
 677 void parseNamespaceEvents(llvm::StringRef Code, const LangOptions &LangOpts,
 678                           llvm::function_ref<void(NamespaceEvent)> Callback) {
 679
 680   // Stack of enclosing namespaces, e.g. {"clang", "clangd"}
 681   std::vector<std::string> Enclosing; // Contains e.g. "clang", "clangd"
 682   // Stack counts open braces. true if the brace opened a namespace.
 683   llvm::BitVector BraceStack;
 684
 685   enum {
 686     Default,
 687     Namespace,          // just saw 'namespace'
 688     NamespaceName,      // just saw 'namespace' NSName
 689     Using,              // just saw 'using'
 690     UsingNamespace,     // just saw 'using namespace'
 691     UsingNamespaceName, // just saw 'using namespace' NSName
 692   } State = Default;
 693   std::string NSName;
 694
 695   NamespaceEvent Event;
 696   lex(Code, LangOpts, [&](const syntax::Token &Tok, const SourceManager &SM) {
 697     Event.Pos = sourceLocToPosition(SM, Tok.location());
 698     switch (Tok.kind()) {
 699     case tok::kw_using:
 700       State = State == Default ? Using : Default;
 701       break;
 702     case tok::kw_namespace:
 703       switch (State) {
 704       case Using:
 705         State = UsingNamespace;
 706         break;
 707       case Default:
 708         State = Namespace;
 709         break;
 710       default:
 711         State = Default;
 712         break;
 713       }
 714       break;
 715     case tok::identifier:
 716       switch (State) {
 717       case UsingNamespace:
 718         NSName.clear();
 719         [[fallthrough]];
 720       case UsingNamespaceName:
 721         NSName.append(Tok.text(SM).str());
 722         State = UsingNamespaceName;
 723         break;
 724       case Namespace:
 725         NSName.clear();
 726         [[fallthrough]];
 727       case NamespaceName:
 728         NSName.append(Tok.text(SM).str());
 729         State = NamespaceName;
 730         break;
 731       case Using:
 732       case Default:
 733         State = Default;
 734         break;
 735       }
 736       break;
 737     case tok::coloncolon:
 738       // This can come at the beginning or in the middle of a namespace
 739       // name.
 740       switch (State) {
 741       case UsingNamespace:
 742         NSName.clear();
 743         [[fallthrough]];
 744       case UsingNamespaceName:
 745         NSName.append("::");
 746         State = UsingNamespaceName;
 747         break;
 748       case NamespaceName:
 749         NSName.append("::");
 750         State = NamespaceName;
 751         break;
 752       case Namespace: // Not legal here.
 753       case Using:
 754       case Default:
 755         State = Default;
 756         break;
 757       }
 758       break;
 759     case tok::l_brace:
 760       // Record which { started a namespace, so we know when } ends one.
 761       if (State == NamespaceName) {
 762         // Parsed: namespace <name> {
 763         BraceStack.push_back(true);
 764         Enclosing.push_back(NSName);
 765         Event.Trigger = NamespaceEvent::BeginNamespace;
 766         Event.Payload = llvm::join(Enclosing, "::");
 767         Callback(Event);
 768       } else {
 769         // This case includes anonymous namespaces (State = Namespace).
 770         // For our purposes, they're not namespaces and we ignore them.
 771         BraceStack.push_back(false);
 772       }
 773       State = Default;
 774       break;
 775     case tok::r_brace:
 776       // If braces are unmatched, we're going to be confused, but don't
 777       // crash.
 778       if (!BraceStack.empty()) {
 779         if (BraceStack.back()) {
 780           // Parsed: } // namespace
 781           Enclosing.pop_back();
 782           Event.Trigger = NamespaceEvent::EndNamespace;
 783           Event.Payload = llvm::join(Enclosing, "::");
 784           Callback(Event);
 785         }
 786         BraceStack.pop_back();
 787       }
 788       break;
 789     case tok::semi:
 790       if (State == UsingNamespaceName) {
 791         // Parsed: using namespace <name> ;
 792         Event.Trigger = NamespaceEvent::UsingDirective;
 793         Event.Payload = std::move(NSName);
 794         Callback(Event);
 795       }
 796       State = Default;
 797       break;
 798     default:
 799       State = Default;
 800       break;
 801     }
 802   });
 803 }
 804
 805 // Returns the prefix namespaces of NS: {"" ... NS}.
 806 llvm::SmallVector<llvm::StringRef> ancestorNamespaces(llvm::StringRef NS) {
 807   llvm::SmallVector<llvm::StringRef> Results;
 808   Results.push_back(NS.take_front(0));
 809   NS.split(Results, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
 810   for (llvm::StringRef &R : Results)
 811     R = NS.take_front(R.end() - NS.begin());
 812   return Results;
 813 }
 814
 815 // Checks whether \p FileName is a valid spelling of main file.
 816 bool isMainFile(llvm::StringRef FileName, const SourceManager &SM) {
 817   auto FE = SM.getFileManager().getFile(FileName);
 818   return FE && *FE == SM.getFileEntryForID(SM.getMainFileID());
 819 }
 820
 821 } // namespace
 822
 823 std::vector<std::string> visibleNamespaces(llvm::StringRef Code,
 824                                            const LangOptions &LangOpts) {
 825   std::string Current;
 826   // Map from namespace to (resolved) namespaces introduced via using directive.
 827   llvm::StringMap<llvm::StringSet<>> UsingDirectives;
 828
 829   parseNamespaceEvents(Code, LangOpts, [&](NamespaceEvent Event) {
 830     llvm::StringRef NS = Event.Payload;
 831     switch (Event.Trigger) {
 832     case NamespaceEvent::BeginNamespace:
 833     case NamespaceEvent::EndNamespace:
 834       Current = std::move(Event.Payload);
 835       break;
 836     case NamespaceEvent::UsingDirective:
 837       if (NS.consume_front("::"))
 838         UsingDirectives[Current].insert(NS);
 839       else {
 840         for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
 841           if (Enclosing.empty())
 842             UsingDirectives[Current].insert(NS);
 843           else
 844             UsingDirectives[Current].insert((Enclosing + "::" + NS).str());
 845         }
 846       }
 847       break;
 848     }
 849   });
 850
 851   std::vector<std::string> Found;
 852   for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
 853     Found.push_back(std::string(Enclosing));
 854     auto It = UsingDirectives.find(Enclosing);
 855     if (It != UsingDirectives.end())
 856       for (const auto &Used : It->second)
 857         Found.push_back(std::string(Used.getKey()));
 858   }
 859
 860   llvm::sort(Found, [&](const std::string &LHS, const std::string &RHS) {
 861     if (Current == RHS)
 862       return false;
 863     if (Current == LHS)
 864       return true;
 865     return LHS < RHS;
 866   });
 867   Found.erase(std::unique(Found.begin(), Found.end()), Found.end());
 868   return Found;
 869 }
 870
 871 llvm::StringSet<> collectWords(llvm::StringRef Content) {
 872   // We assume short words are not significant.
 873   // We may want to consider other stopwords, e.g. language keywords.
 874   // (A very naive implementation showed no benefit, but lexing might do better)
 875   static constexpr int MinWordLength = 4;
 876
 877   std::vector<CharRole> Roles(Content.size());
 878   calculateRoles(Content, Roles);
 879
 880   llvm::StringSet<> Result;
 881   llvm::SmallString<256> Word;
 882   auto Flush = [&] {
 883     if (Word.size() >= MinWordLength) {
 884       for (char &C : Word)
 885         C = llvm::toLower(C);
 886       Result.insert(Word);
 887     }
 888     Word.clear();
 889   };
 890   for (unsigned I = 0; I < Content.size(); ++I) {
 891     switch (Roles[I]) {
 892     case Head:
 893       Flush();
 894       [[fallthrough]];
 895     case Tail:
 896       Word.push_back(Content[I]);
 897       break;
 898     case Unknown:
 899     case Separator:
 900       Flush();
 901       break;
 902     }
 903   }
 904   Flush();
 905
 906   return Result;
 907 }
 908
 909 static bool isLikelyIdentifier(llvm::StringRef Word, llvm::StringRef Before,
 910                                llvm::StringRef After) {
 911   // `foo` is an identifier.
 912   if (Before.ends_with("`") && After.starts_with("`"))
 913     return true;
 914   // In foo::bar, both foo and bar are identifiers.
 915   if (Before.ends_with("::") || After.starts_with("::"))
 916     return true;
 917   // Doxygen tags like \c foo indicate identifiers.
 918   // Don't search too far back.
 919   // This duplicates clang's doxygen parser, revisit if it gets complicated.
 920   Before = Before.take_back(100); // Don't search too far back.
 921   auto Pos = Before.find_last_of("\\@");
 922   if (Pos != llvm::StringRef::npos) {
 923     llvm::StringRef Tag = Before.substr(Pos + 1).rtrim(' ');
 924     if (Tag == "p" || Tag == "c" || Tag == "class" || Tag == "tparam" ||
 925         Tag == "param" || Tag == "param[in]" || Tag == "param[out]" ||
 926         Tag == "param[in,out]" || Tag == "retval" || Tag == "throw" ||
 927         Tag == "throws" || Tag == "link")
 928       return true;
 929   }
 930
 931   // Word contains underscore.
 932   // This handles things like snake_case and MACRO_CASE.
 933   if (Word.contains('_')) {
 934     return true;
 935   }
 936   // Word contains capital letter other than at beginning.
 937   // This handles things like lowerCamel and UpperCamel.
 938   // The check for also containing a lowercase letter is to rule out
 939   // initialisms like "HTTP".
 940   bool HasLower = Word.find_if(clang::isLowercase) != StringRef::npos;
 941   bool HasUpper = Word.substr(1).find_if(clang::isUppercase) != StringRef::npos;
 942   if (HasLower && HasUpper) {
 943     return true;
 944   }
 945   // FIXME: consider mid-sentence Capitalization?
 946   return false;
 947 }
 948
 949 std::optional<SpelledWord> SpelledWord::touching(SourceLocation SpelledLoc,
 950                                                  const syntax::TokenBuffer &TB,
 951                                                  const LangOptions &LangOpts) {
 952   const auto &SM = TB.sourceManager();
 953   auto Touching = syntax::spelledTokensTouching(SpelledLoc, TB);
 954   for (const auto &T : Touching) {
 955     // If the token is an identifier or a keyword, don't use any heuristics.
 956     if (tok::isAnyIdentifier(T.kind()) || tok::getKeywordSpelling(T.kind())) {
 957       SpelledWord Result;
 958       Result.Location = T.location();
 959       Result.Text = T.text(SM);
 960       Result.LikelyIdentifier = tok::isAnyIdentifier(T.kind());
 961       Result.PartOfSpelledToken = &T;
 962       Result.SpelledToken = &T;
 963       auto Expanded =
 964           TB.expandedTokens(SM.getMacroArgExpandedLocation(T.location()));
 965       if (Expanded.size() == 1 && Expanded.front().text(SM) == Result.Text)
 966         Result.ExpandedToken = &Expanded.front();
 967       return Result;
 968     }
 969   }
 970   FileID File;
 971   unsigned Offset;
 972   std::tie(File, Offset) = SM.getDecomposedLoc(SpelledLoc);
 973   bool Invalid = false;
 974   llvm::StringRef Code = SM.getBufferData(File, &Invalid);
 975   if (Invalid)
 976     return std::nullopt;
 977   unsigned B = Offset, E = Offset;
 978   while (B > 0 && isAsciiIdentifierContinue(Code[B - 1]))
 979     --B;
 980   while (E < Code.size() && isAsciiIdentifierContinue(Code[E]))
 981     ++E;
 982   if (B == E)
 983     return std::nullopt;
 984
 985   SpelledWord Result;
 986   Result.Location = SM.getComposedLoc(File, B);
 987   Result.Text = Code.slice(B, E);
 988   Result.LikelyIdentifier =
 989       isLikelyIdentifier(Result.Text, Code.substr(0, B), Code.substr(E)) &&
 990       // should not be a keyword
 991       tok::isAnyIdentifier(
 992           IdentifierTable(LangOpts).get(Result.Text).getTokenID());
 993   for (const auto &T : Touching)
 994     if (T.location() <= Result.Location)
 995       Result.PartOfSpelledToken = &T;
 996   return Result;
 997 }
 998
 999 std::optional<DefinedMacro> locateMacroAt(const syntax::Token &SpelledTok,
1000                                           Preprocessor &PP) {
1001   if (SpelledTok.kind() != tok::identifier)
1002     return std::nullopt;
1003   SourceLocation Loc = SpelledTok.location();
1004   assert(Loc.isFileID());
1005   const auto &SM = PP.getSourceManager();
1006   IdentifierInfo *IdentifierInfo = PP.getIdentifierInfo(SpelledTok.text(SM));
1007   if (!IdentifierInfo || !IdentifierInfo->hadMacroDefinition())
1008     return std::nullopt;
1009
1010   // We need to take special case to handle #define and #undef.
1011   // Preprocessor::getMacroDefinitionAtLoc() only considers a macro
1012   // definition to be in scope *after* the location of the macro name in a
1013   // #define that introduces it, and *before* the location of the macro name
1014   // in an #undef that undefines it. To handle these cases, we check for
1015   // the macro being in scope either just after or just before the location
1016   // of the token. In getting the location before, we also take care to check
1017   // for start-of-file.
1018   FileID FID = SM.getFileID(Loc);
1019   assert(Loc != SM.getLocForEndOfFile(FID));
1020   SourceLocation JustAfterToken = Loc.getLocWithOffset(1);
1021   auto *MacroInfo =
1022       PP.getMacroDefinitionAtLoc(IdentifierInfo, JustAfterToken).getMacroInfo();
1023   if (!MacroInfo && SM.getLocForStartOfFile(FID) != Loc) {
1024     SourceLocation JustBeforeToken = Loc.getLocWithOffset(-1);
1025     MacroInfo = PP.getMacroDefinitionAtLoc(IdentifierInfo, JustBeforeToken)
1026                     .getMacroInfo();
1027   }
1028   if (!MacroInfo) {
1029     return std::nullopt;
1030   }
1031   return DefinedMacro{
1032       IdentifierInfo->getName(), MacroInfo,
1033       translatePreamblePatchLocation(MacroInfo->getDefinitionLoc(), SM)};
1034 }
1035
1036 llvm::Expected<std::string> Edit::apply() const {
1037   return tooling::applyAllReplacements(InitialCode, Replacements);
1038 }
1039
1040 std::vector<TextEdit> Edit::asTextEdits() const {
1041   return replacementsToEdits(InitialCode, Replacements);
1042 }
1043
1044 bool Edit::canApplyTo(llvm::StringRef Code) const {
1045   // Create line iterators, since line numbers are important while applying our
1046   // edit we cannot skip blank lines.
1047   auto LHS = llvm::MemoryBuffer::getMemBuffer(Code);
1048   llvm::line_iterator LHSIt(*LHS, /*SkipBlanks=*/false);
1049
1050   auto RHS = llvm::MemoryBuffer::getMemBuffer(InitialCode);
1051   llvm::line_iterator RHSIt(*RHS, /*SkipBlanks=*/false);
1052
1053   // Compare the InitialCode we prepared the edit for with the Code we received
1054   // line by line to make sure there are no differences.
1055   // FIXME: This check is too conservative now, it should be enough to only
1056   // check lines around the replacements contained inside the Edit.
1057   while (!LHSIt.is_at_eof() && !RHSIt.is_at_eof()) {
1058     if (*LHSIt != *RHSIt)
1059       return false;
1060     ++LHSIt;
1061     ++RHSIt;
1062   }
1063
1064   // After we reach EOF for any of the files we make sure the other one doesn't
1065   // contain any additional content except empty lines, they should not
1066   // interfere with the edit we produced.
1067   while (!LHSIt.is_at_eof()) {
1068     if (!LHSIt->empty())
1069       return false;
1070     ++LHSIt;
1071   }
1072   while (!RHSIt.is_at_eof()) {
1073     if (!RHSIt->empty())
1074       return false;
1075     ++RHSIt;
1076   }
1077   return true;
1078 }
1079
1080 llvm::Error reformatEdit(Edit &E, const format::FormatStyle &Style) {
1081   if (auto NewEdits = cleanupAndFormat(E.InitialCode, E.Replacements, Style))
1082     E.Replacements = std::move(*NewEdits);
1083   else
1084     return NewEdits.takeError();
1085   return llvm::Error::success();
1086 }
1087
1088 // Workaround for editors that have buggy handling of newlines at end of file.
1089 //
1090 // The editor is supposed to expose document contents over LSP as an exact
1091 // string, with whitespace and newlines well-defined. But internally many
1092 // editors treat text as an array of lines, and there can be ambiguity over
1093 // whether the last line ends with a newline or not.
1094 //
1095 // This confusion can lead to incorrect edits being sent. Failing to apply them
1096 // is catastrophic: we're desynced, LSP has no mechanism to get back in sync.
1097 // We apply a heuristic to avoid this state.
1098 //
1099 // If our current view of an N-line file does *not* end in a newline, but the
1100 // editor refers to the start of the next line (an impossible location), then
1101 // we silently add a newline to make this valid.
1102 // We will still validate that the rangeLength is correct, *including* the
1103 // inferred newline.
1104 //
1105 // See https://github.com/neovim/neovim/issues/17085
1106 static void inferFinalNewline(llvm::Expected<size_t> &Err,
1107                               std::string &Contents, const Position &Pos) {
1108   if (Err)
1109     return;
1110   if (!Contents.empty() && Contents.back() == '\n')
1111     return;
1112   if (Pos.character != 0)
1113     return;
1114   if (Pos.line != llvm::count(Contents, '\n') + 1)
1115     return;
1116   log("Editor sent invalid change coordinates, inferring newline at EOF");
1117   Contents.push_back('\n');
1118   consumeError(Err.takeError());
1119   Err = Contents.size();
1120 }
1121
1122 llvm::Error applyChange(std::string &Contents,
1123                         const TextDocumentContentChangeEvent &Change) {
1124   if (!Change.range) {
1125     Contents = Change.text;
1126     return llvm::Error::success();
1127   }
1128
1129   const Position &Start = Change.range->start;
1130   llvm::Expected<size_t> StartIndex = positionToOffset(Contents, Start, false);
1131   inferFinalNewline(StartIndex, Contents, Start);
1132   if (!StartIndex)
1133     return StartIndex.takeError();
1134
1135   const Position &End = Change.range->end;
1136   llvm::Expected<size_t> EndIndex = positionToOffset(Contents, End, false);
1137   inferFinalNewline(EndIndex, Contents, End);
1138   if (!EndIndex)
1139     return EndIndex.takeError();
1140
1141   if (*EndIndex < *StartIndex)
1142     return error(llvm::errc::invalid_argument,
1143                  "Range's end position ({0}) is before start position ({1})",
1144                  End, Start);
1145
1146   // Since the range length between two LSP positions is dependent on the
1147   // contents of the buffer we compute the range length between the start and
1148   // end position ourselves and compare it to the range length of the LSP
1149   // message to verify the buffers of the client and server are in sync.
1150
1151   // EndIndex and StartIndex are in bytes, but Change.rangeLength is in UTF-16
1152   // code units.
1153   ssize_t ComputedRangeLength =
1154       lspLength(Contents.substr(*StartIndex, *EndIndex - *StartIndex));
1155
1156   if (Change.rangeLength && ComputedRangeLength != *Change.rangeLength)
1157     return error(llvm::errc::invalid_argument,
1158                  "Change's rangeLength ({0}) doesn't match the "
1159                  "computed range length ({1}).",
1160                  *Change.rangeLength, ComputedRangeLength);
1161
1162   Contents.replace(*StartIndex, *EndIndex - *StartIndex, Change.text);
1163
1164   return llvm::Error::success();
1165 }
1166
1167 EligibleRegion getEligiblePoints(llvm::StringRef Code,
1168                                  llvm::StringRef FullyQualifiedName,
1169                                  const LangOptions &LangOpts) {
1170   EligibleRegion ER;
1171   // Start with global namespace.
1172   std::vector<std::string> Enclosing = {""};
1173   // FIXME: In addition to namespaces try to generate events for function
1174   // definitions as well. One might use a closing parantheses(")" followed by an
1175   // opening brace "{" to trigger the start.
1176   parseNamespaceEvents(Code, LangOpts, [&](NamespaceEvent Event) {
1177     // Using Directives only introduces declarations to current scope, they do
1178     // not change the current namespace, so skip them.
1179     if (Event.Trigger == NamespaceEvent::UsingDirective)
1180       return;
1181     // Do not qualify the global namespace.
1182     if (!Event.Payload.empty())
1183       Event.Payload.append("::");
1184
1185     std::string CurrentNamespace;
1186     if (Event.Trigger == NamespaceEvent::BeginNamespace) {
1187       Enclosing.emplace_back(std::move(Event.Payload));
1188       CurrentNamespace = Enclosing.back();
1189       // parseNameSpaceEvents reports the beginning position of a token; we want
1190       // to insert after '{', so increment by one.
1191       ++Event.Pos.character;
1192     } else {
1193       // Event.Payload points to outer namespace when exiting a scope, so use
1194       // the namespace we've last entered instead.
1195       CurrentNamespace = std::move(Enclosing.back());
1196       Enclosing.pop_back();
1197       assert(Enclosing.back() == Event.Payload);
1198     }
1199
1200     // Ignore namespaces that are not a prefix of the target.
1201     if (!FullyQualifiedName.starts_with(CurrentNamespace))
1202       return;
1203
1204     // Prefer the namespace that shares the longest prefix with target.
1205     if (CurrentNamespace.size() > ER.EnclosingNamespace.size()) {
1206       ER.EligiblePoints.clear();
1207       ER.EnclosingNamespace = CurrentNamespace;
1208     }
1209     if (CurrentNamespace.size() == ER.EnclosingNamespace.size())
1210       ER.EligiblePoints.emplace_back(std::move(Event.Pos));
1211   });
1212   // If there were no shared namespaces just return EOF.
1213   if (ER.EligiblePoints.empty()) {
1214     assert(ER.EnclosingNamespace.empty());
1215     ER.EligiblePoints.emplace_back(offsetToPosition(Code, Code.size()));
1216   }
1217   return ER;
1218 }
1219
1220 bool isHeaderFile(llvm::StringRef FileName,
1221                   std::optional<LangOptions> LangOpts) {
1222   // Respect the langOpts, for non-file-extension cases, e.g. standard library
1223   // files.
1224   if (LangOpts && LangOpts->IsHeaderFile)
1225     return true;
1226   namespace types = clang::driver::types;
1227   auto Lang = types::lookupTypeForExtension(
1228       llvm::sys::path::extension(FileName).substr(1));
1229   return Lang != types::TY_INVALID && types::onlyPrecompileType(Lang);
1230 }
1231
1232 bool isProtoFile(SourceLocation Loc, const SourceManager &SM) {
1233   auto FileName = SM.getFilename(Loc);
1234   if (!FileName.ends_with(".proto.h") && !FileName.ends_with(".pb.h"))
1235     return false;
1236   auto FID = SM.getFileID(Loc);
1237   // All proto generated headers should start with this line.
1238   static const char *ProtoHeaderComment =
1239       "// Generated by the protocol buffer compiler.  DO NOT EDIT!";
1240   // Double check that this is an actual protobuf header.
1241   return SM.getBufferData(FID).starts_with(ProtoHeaderComment);
1242 }
1243
1244 SourceLocation translatePreamblePatchLocation(SourceLocation Loc,
1245                                               const SourceManager &SM) {
1246   auto DefFile = SM.getFileID(Loc);
1247   if (auto FE = SM.getFileEntryRefForID(DefFile)) {
1248     auto IncludeLoc = SM.getIncludeLoc(DefFile);
1249     // Preamble patch is included inside the builtin file.
1250     if (IncludeLoc.isValid() && SM.isWrittenInBuiltinFile(IncludeLoc) &&
1251         FE->getName().ends_with(PreamblePatch::HeaderName)) {
1252       auto Presumed = SM.getPresumedLoc(Loc);
1253       // Check that line directive is pointing at main file.
1254       if (Presumed.isValid() && Presumed.getFileID().isInvalid() &&
1255           isMainFile(Presumed.getFilename(), SM)) {
1256         Loc = SM.translateLineCol(SM.getMainFileID(), Presumed.getLine(),
1257                                   Presumed.getColumn());
1258       }
1259     }
1260   }
1261   return Loc;
1262 }
1263
1264 clangd::Range rangeTillEOL(llvm::StringRef Code, unsigned HashOffset) {
1265   clangd::Range Result;
1266   Result.end = Result.start = offsetToPosition(Code, HashOffset);
1267
1268   // Span the warning until the EOL or EOF.
1269   Result.end.character +=
1270       lspLength(Code.drop_front(HashOffset).take_until([](char C) {
1271         return C == '\n' || C == '\r';
1272       }));
1273   return Result;
1274 }
1275 } // namespace clangd
1276 } // namespace clang