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