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