blob: 3feddd1df24becabbc948604f558086596263d4c [file] [log] [blame]
Sam McCallb536a2a2017-12-19 12:23:48 +00001//===--- SourceCode.h - Manipulating source code as strings -----*- C++ -*-===//
2//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Sam McCallb536a2a2017-12-19 12:23:48 +00006//
7//===----------------------------------------------------------------------===//
8#include "SourceCode.h"
9
Sam McCalla69698f2019-03-27 17:47:49 +000010#include "Context.h"
Sam McCall9fb22b22019-05-06 10:25:10 +000011#include "FuzzyMatch.h"
Marc-Andre Laperle1be69702018-07-05 19:35:01 +000012#include "Logger.h"
Sam McCalla69698f2019-03-27 17:47:49 +000013#include "Protocol.h"
Kadir Cetinkaya5b270932019-09-09 12:28:44 +000014#include "refactor/Tweak.h"
Marc-Andre Laperle1be69702018-07-05 19:35:01 +000015#include "clang/AST/ASTContext.h"
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +000016#include "clang/Basic/LangOptions.h"
17#include "clang/Basic/SourceLocation.h"
Marc-Andre Laperle63a10982018-02-21 02:39:08 +000018#include "clang/Basic/SourceManager.h"
Sam McCallc316b222019-04-26 07:45:49 +000019#include "clang/Basic/TokenKinds.h"
Haojian Wu509efe52019-11-13 16:30:07 +010020#include "clang/Driver/Types.h"
Sam McCallc316b222019-04-26 07:45:49 +000021#include "clang/Format/Format.h"
Marc-Andre Laperle1be69702018-07-05 19:35:01 +000022#include "clang/Lex/Lexer.h"
Haojian Wu9d34f452019-07-01 09:26:48 +000023#include "clang/Lex/Preprocessor.h"
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +020024#include "clang/Lex/Token.h"
Kadir Cetinkaya5b270932019-09-09 12:28:44 +000025#include "clang/Tooling/Core/Replacement.h"
Kadir Cetinkaya98bb0942020-02-27 15:10:54 +010026#include "clang/Tooling/Syntax/Tokens.h"
Kadir Cetinkaya5b270932019-09-09 12:28:44 +000027#include "llvm/ADT/ArrayRef.h"
Ilya Biryukov43998782019-01-31 21:30:05 +000028#include "llvm/ADT/None.h"
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +020029#include "llvm/ADT/STLExtras.h"
Sam McCallc316b222019-04-26 07:45:49 +000030#include "llvm/ADT/StringExtras.h"
Kadir Cetinkaya5b270932019-09-09 12:28:44 +000031#include "llvm/ADT/StringMap.h"
Ilya Biryukov43998782019-01-31 21:30:05 +000032#include "llvm/ADT/StringRef.h"
Sam McCall9fb22b22019-05-06 10:25:10 +000033#include "llvm/Support/Compiler.h"
Simon Marchi766338a2018-03-21 14:36:46 +000034#include "llvm/Support/Errc.h"
35#include "llvm/Support/Error.h"
Sam McCall8b25d222019-03-28 14:37:51 +000036#include "llvm/Support/ErrorHandling.h"
Kadir Cetinkaya5b270932019-09-09 12:28:44 +000037#include "llvm/Support/LineIterator.h"
38#include "llvm/Support/MemoryBuffer.h"
Marc-Andre Laperle1be69702018-07-05 19:35:01 +000039#include "llvm/Support/Path.h"
Kadir Cetinkaya5b270932019-09-09 12:28:44 +000040#include "llvm/Support/SHA1.h"
41#include "llvm/Support/VirtualFileSystem.h"
Sam McCall674d8a92019-07-08 11:33:17 +000042#include "llvm/Support/xxhash.h"
Sam McCallc316b222019-04-26 07:45:49 +000043#include <algorithm>
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +020044#include <cstddef>
45#include <string>
46#include <vector>
Marc-Andre Laperle63a10982018-02-21 02:39:08 +000047
Sam McCallb536a2a2017-12-19 12:23:48 +000048namespace clang {
49namespace clangd {
Sam McCallb536a2a2017-12-19 12:23:48 +000050
Sam McCalla4962cc2018-04-27 11:59:28 +000051// 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.
57template <typename Callback>
Ilya Biryukovf2001aa2019-01-07 15:45:19 +000058static bool iterateCodepoints(llvm::StringRef U8, const Callback &CB) {
Sam McCall8b25d222019-03-28 14:37:51 +000059 // 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, starting with 11110xxx.
Sam McCalla4962cc2018-04-27 11:59:28 +000061 for (size_t I = 0; I < U8.size();) {
62 unsigned char C = static_cast<unsigned char>(U8[I]);
63 if (LLVM_LIKELY(!(C & 0x80))) { // ASCII character.
64 if (CB(1, 1))
65 return true;
66 ++I;
67 continue;
68 }
69 // This convenient property of UTF-8 holds for all non-ASCII characters.
Ilya Biryukovf2001aa2019-01-07 15:45:19 +000070 size_t UTF8Length = llvm::countLeadingOnes(C);
Sam McCalla4962cc2018-04-27 11:59:28 +000071 // 0xxx is ASCII, handled above. 10xxx is a trailing byte, invalid here.
72 // 11111xxx is not valid UTF-8 at all. Assert because it's probably our bug.
73 assert((UTF8Length >= 2 && UTF8Length <= 4) &&
74 "Invalid UTF-8, or transcoding bug?");
75 I += UTF8Length; // Skip over all trailing bytes.
76 // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
77 // Astral codepoints are encoded as 4 bytes in UTF-8 (11110xxx ...)
78 if (CB(UTF8Length, UTF8Length == 4 ? 2 : 1))
79 return true;
80 }
81 return false;
82}
83
Sam McCall8b25d222019-03-28 14:37:51 +000084// Returns the byte offset into the string that is an offset of \p Units in
85// the specified encoding.
86// Conceptually, this converts to the encoding, truncates to CodeUnits,
87// converts back to UTF-8, and returns the length in bytes.
88static size_t measureUnits(llvm::StringRef U8, int Units, OffsetEncoding Enc,
89 bool &Valid) {
90 Valid = Units >= 0;
91 if (Units <= 0)
92 return 0;
Sam McCalla4962cc2018-04-27 11:59:28 +000093 size_t Result = 0;
Sam McCall8b25d222019-03-28 14:37:51 +000094 switch (Enc) {
95 case OffsetEncoding::UTF8:
96 Result = Units;
97 break;
98 case OffsetEncoding::UTF16:
99 Valid = iterateCodepoints(U8, [&](int U8Len, int U16Len) {
100 Result += U8Len;
101 Units -= U16Len;
102 return Units <= 0;
103 });
104 if (Units < 0) // Offset in the middle of a surrogate pair.
105 Valid = false;
106 break;
107 case OffsetEncoding::UTF32:
108 Valid = iterateCodepoints(U8, [&](int U8Len, int U16Len) {
109 Result += U8Len;
110 Units--;
111 return Units <= 0;
112 });
113 break;
114 case OffsetEncoding::UnsupportedEncoding:
115 llvm_unreachable("unsupported encoding");
116 }
Sam McCalla4962cc2018-04-27 11:59:28 +0000117 // Don't return an out-of-range index if we overran.
Sam McCall8b25d222019-03-28 14:37:51 +0000118 if (Result > U8.size()) {
119 Valid = false;
120 return U8.size();
121 }
122 return Result;
Sam McCalla4962cc2018-04-27 11:59:28 +0000123}
124
Sam McCalla69698f2019-03-27 17:47:49 +0000125Key<OffsetEncoding> kCurrentOffsetEncoding;
Sam McCall8b25d222019-03-28 14:37:51 +0000126static OffsetEncoding lspEncoding() {
Sam McCalla69698f2019-03-27 17:47:49 +0000127 auto *Enc = Context::current().get(kCurrentOffsetEncoding);
Sam McCall8b25d222019-03-28 14:37:51 +0000128 return Enc ? *Enc : OffsetEncoding::UTF16;
Sam McCalla69698f2019-03-27 17:47:49 +0000129}
130
Sam McCalla4962cc2018-04-27 11:59:28 +0000131// Like most strings in clangd, the input is UTF-8 encoded.
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000132size_t lspLength(llvm::StringRef Code) {
Sam McCalla4962cc2018-04-27 11:59:28 +0000133 size_t Count = 0;
Sam McCall8b25d222019-03-28 14:37:51 +0000134 switch (lspEncoding()) {
135 case OffsetEncoding::UTF8:
136 Count = Code.size();
137 break;
138 case OffsetEncoding::UTF16:
139 iterateCodepoints(Code, [&](int U8Len, int U16Len) {
140 Count += U16Len;
141 return false;
142 });
143 break;
144 case OffsetEncoding::UTF32:
145 iterateCodepoints(Code, [&](int U8Len, int U16Len) {
146 ++Count;
147 return false;
148 });
149 break;
150 case OffsetEncoding::UnsupportedEncoding:
151 llvm_unreachable("unsupported encoding");
152 }
Sam McCalla4962cc2018-04-27 11:59:28 +0000153 return Count;
154}
155
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000156llvm::Expected<size_t> positionToOffset(llvm::StringRef Code, Position P,
157 bool AllowColumnsBeyondLineLength) {
Sam McCallb536a2a2017-12-19 12:23:48 +0000158 if (P.line < 0)
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000159 return llvm::make_error<llvm::StringError>(
160 llvm::formatv("Line value can't be negative ({0})", P.line),
161 llvm::errc::invalid_argument);
Simon Marchi766338a2018-03-21 14:36:46 +0000162 if (P.character < 0)
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000163 return llvm::make_error<llvm::StringError>(
164 llvm::formatv("Character value can't be negative ({0})", P.character),
165 llvm::errc::invalid_argument);
Sam McCallb536a2a2017-12-19 12:23:48 +0000166 size_t StartOfLine = 0;
167 for (int I = 0; I != P.line; ++I) {
168 size_t NextNL = Code.find('\n', StartOfLine);
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000169 if (NextNL == llvm::StringRef::npos)
170 return llvm::make_error<llvm::StringError>(
171 llvm::formatv("Line value is out of range ({0})", P.line),
172 llvm::errc::invalid_argument);
Sam McCallb536a2a2017-12-19 12:23:48 +0000173 StartOfLine = NextNL + 1;
174 }
Sam McCalla69698f2019-03-27 17:47:49 +0000175 StringRef Line =
176 Code.substr(StartOfLine).take_until([](char C) { return C == '\n'; });
Simon Marchi766338a2018-03-21 14:36:46 +0000177
Sam McCall8b25d222019-03-28 14:37:51 +0000178 // P.character may be in UTF-16, transcode if necessary.
Sam McCalla4962cc2018-04-27 11:59:28 +0000179 bool Valid;
Sam McCall8b25d222019-03-28 14:37:51 +0000180 size_t ByteInLine = measureUnits(Line, P.character, lspEncoding(), Valid);
Sam McCalla4962cc2018-04-27 11:59:28 +0000181 if (!Valid && !AllowColumnsBeyondLineLength)
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000182 return llvm::make_error<llvm::StringError>(
Sam McCall8b25d222019-03-28 14:37:51 +0000183 llvm::formatv("{0} offset {1} is invalid for line {2}", lspEncoding(),
184 P.character, P.line),
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000185 llvm::errc::invalid_argument);
Sam McCall8b25d222019-03-28 14:37:51 +0000186 return StartOfLine + ByteInLine;
Sam McCallb536a2a2017-12-19 12:23:48 +0000187}
188
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000189Position offsetToPosition(llvm::StringRef Code, size_t Offset) {
Sam McCallb536a2a2017-12-19 12:23:48 +0000190 Offset = std::min(Code.size(), Offset);
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000191 llvm::StringRef Before = Code.substr(0, Offset);
Sam McCallb536a2a2017-12-19 12:23:48 +0000192 int Lines = Before.count('\n');
193 size_t PrevNL = Before.rfind('\n');
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000194 size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
Ilya Biryukov7beea3a2018-02-14 10:52:04 +0000195 Position Pos;
196 Pos.line = Lines;
Sam McCall71891122018-10-23 11:51:53 +0000197 Pos.character = lspLength(Before.substr(StartOfLine));
Ilya Biryukov7beea3a2018-02-14 10:52:04 +0000198 return Pos;
Sam McCallb536a2a2017-12-19 12:23:48 +0000199}
200
Marc-Andre Laperle63a10982018-02-21 02:39:08 +0000201Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc) {
Sam McCalla4962cc2018-04-27 11:59:28 +0000202 // We use the SourceManager's line tables, but its column number is in bytes.
203 FileID FID;
204 unsigned Offset;
205 std::tie(FID, Offset) = SM.getDecomposedSpellingLoc(Loc);
Marc-Andre Laperle63a10982018-02-21 02:39:08 +0000206 Position P;
Sam McCalla4962cc2018-04-27 11:59:28 +0000207 P.line = static_cast<int>(SM.getLineNumber(FID, Offset)) - 1;
208 bool Invalid = false;
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000209 llvm::StringRef Code = SM.getBufferData(FID, &Invalid);
Sam McCalla4962cc2018-04-27 11:59:28 +0000210 if (!Invalid) {
211 auto ColumnInBytes = SM.getColumnNumber(FID, Offset) - 1;
212 auto LineSoFar = Code.substr(Offset - ColumnInBytes, ColumnInBytes);
Sam McCall71891122018-10-23 11:51:53 +0000213 P.character = lspLength(LineSoFar);
Sam McCalla4962cc2018-04-27 11:59:28 +0000214 }
Marc-Andre Laperle63a10982018-02-21 02:39:08 +0000215 return P;
216}
217
Sam McCall95738072019-08-06 20:25:59 +0000218bool isSpelledInSource(SourceLocation Loc, const SourceManager &SM) {
219 if (Loc.isMacroID()) {
220 std::string PrintLoc = SM.getSpellingLoc(Loc).printToString(SM);
221 if (llvm::StringRef(PrintLoc).startswith("<scratch") ||
222 llvm::StringRef(PrintLoc).startswith("<command line>"))
223 return false;
224 }
225 return true;
226}
227
Haojian Wu92c32572019-06-25 08:01:46 +0000228llvm::Optional<Range> getTokenRange(const SourceManager &SM,
229 const LangOptions &LangOpts,
230 SourceLocation TokLoc) {
231 if (!TokLoc.isValid())
232 return llvm::None;
233 SourceLocation End = Lexer::getLocForEndOfToken(TokLoc, 0, SM, LangOpts);
234 if (!End.isValid())
235 return llvm::None;
236 return halfOpenToRange(SM, CharSourceRange::getCharRange(TokLoc, End));
237}
238
Ilya Biryukov43998782019-01-31 21:30:05 +0000239bool isValidFileRange(const SourceManager &Mgr, SourceRange R) {
240 if (!R.getBegin().isValid() || !R.getEnd().isValid())
241 return false;
242
243 FileID BeginFID;
244 size_t BeginOffset = 0;
245 std::tie(BeginFID, BeginOffset) = Mgr.getDecomposedLoc(R.getBegin());
246
247 FileID EndFID;
248 size_t EndOffset = 0;
249 std::tie(EndFID, EndOffset) = Mgr.getDecomposedLoc(R.getEnd());
250
251 return BeginFID.isValid() && BeginFID == EndFID && BeginOffset <= EndOffset;
252}
253
254bool halfOpenRangeContains(const SourceManager &Mgr, SourceRange R,
255 SourceLocation L) {
256 assert(isValidFileRange(Mgr, R));
257
258 FileID BeginFID;
259 size_t BeginOffset = 0;
260 std::tie(BeginFID, BeginOffset) = Mgr.getDecomposedLoc(R.getBegin());
261 size_t EndOffset = Mgr.getFileOffset(R.getEnd());
262
263 FileID LFid;
264 size_t LOffset;
265 std::tie(LFid, LOffset) = Mgr.getDecomposedLoc(L);
266 return BeginFID == LFid && BeginOffset <= LOffset && LOffset < EndOffset;
267}
268
269bool halfOpenRangeTouches(const SourceManager &Mgr, SourceRange R,
270 SourceLocation L) {
271 return L == R.getEnd() || halfOpenRangeContains(Mgr, R, L);
272}
273
Sam McCallc791d852019-08-27 08:44:06 +0000274SourceLocation includeHashLoc(FileID IncludedFile, const SourceManager &SM) {
275 assert(SM.getLocForEndOfFile(IncludedFile).isFileID());
276 FileID IncludingFile;
277 unsigned Offset;
278 std::tie(IncludingFile, Offset) =
279 SM.getDecomposedExpansionLoc(SM.getIncludeLoc(IncludedFile));
280 bool Invalid = false;
281 llvm::StringRef Buf = SM.getBufferData(IncludingFile, &Invalid);
282 if (Invalid)
283 return SourceLocation();
284 // Now buf is "...\n#include <foo>\n..."
285 // and Offset points here: ^
286 // Rewind to the preceding # on the line.
287 assert(Offset < Buf.size());
288 for (;; --Offset) {
289 if (Buf[Offset] == '#')
290 return SM.getComposedLoc(IncludingFile, Offset);
291 if (Buf[Offset] == '\n' || Offset == 0) // no hash, what's going on?
292 return SourceLocation();
293 }
294}
295
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000296static unsigned getTokenLengthAtLoc(SourceLocation Loc, const SourceManager &SM,
297 const LangOptions &LangOpts) {
298 Token TheTok;
299 if (Lexer::getRawToken(Loc, TheTok, SM, LangOpts))
300 return 0;
301 // FIXME: Here we check whether the token at the location is a greatergreater
302 // (>>) token and consider it as a single greater (>). This is to get it
303 // working for templates but it isn't correct for the right shift operator. We
304 // can avoid this by using half open char ranges in getFileRange() but getting
305 // token ending is not well supported in macroIDs.
306 if (TheTok.is(tok::greatergreater))
307 return 1;
308 return TheTok.getLength();
309}
310
311// Returns location of the last character of the token at a given loc
312static SourceLocation getLocForTokenEnd(SourceLocation BeginLoc,
313 const SourceManager &SM,
314 const LangOptions &LangOpts) {
315 unsigned Len = getTokenLengthAtLoc(BeginLoc, SM, LangOpts);
316 return BeginLoc.getLocWithOffset(Len ? Len - 1 : 0);
317}
318
319// Returns location of the starting of the token at a given EndLoc
320static SourceLocation getLocForTokenBegin(SourceLocation EndLoc,
321 const SourceManager &SM,
322 const LangOptions &LangOpts) {
323 return EndLoc.getLocWithOffset(
324 -(signed)getTokenLengthAtLoc(EndLoc, SM, LangOpts));
325}
326
327// Converts a char source range to a token range.
328static SourceRange toTokenRange(CharSourceRange Range, const SourceManager &SM,
329 const LangOptions &LangOpts) {
330 if (!Range.isTokenRange())
331 Range.setEnd(getLocForTokenBegin(Range.getEnd(), SM, LangOpts));
332 return Range.getAsRange();
333}
334// Returns the union of two token ranges.
335// To find the maximum of the Ends of the ranges, we compare the location of the
336// last character of the token.
337static SourceRange unionTokenRange(SourceRange R1, SourceRange R2,
338 const SourceManager &SM,
339 const LangOptions &LangOpts) {
Sam McCallc791d852019-08-27 08:44:06 +0000340 SourceLocation Begin =
341 SM.isBeforeInTranslationUnit(R1.getBegin(), R2.getBegin())
342 ? R1.getBegin()
343 : R2.getBegin();
344 SourceLocation End =
345 SM.isBeforeInTranslationUnit(getLocForTokenEnd(R1.getEnd(), SM, LangOpts),
346 getLocForTokenEnd(R2.getEnd(), SM, LangOpts))
347 ? R2.getEnd()
348 : R1.getEnd();
349 return SourceRange(Begin, End);
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000350}
351
Sam McCallc791d852019-08-27 08:44:06 +0000352// Given a range whose endpoints may be in different expansions or files,
353// tries to find a range within a common file by following up the expansion and
354// include location in each.
355static SourceRange rangeInCommonFile(SourceRange R, const SourceManager &SM,
356 const LangOptions &LangOpts) {
357 // Fast path for most common cases.
358 if (SM.isWrittenInSameFile(R.getBegin(), R.getEnd()))
359 return R;
360 // Record the stack of expansion locations for the beginning, keyed by FileID.
361 llvm::DenseMap<FileID, SourceLocation> BeginExpansions;
362 for (SourceLocation Begin = R.getBegin(); Begin.isValid();
363 Begin = Begin.isFileID()
364 ? includeHashLoc(SM.getFileID(Begin), SM)
365 : SM.getImmediateExpansionRange(Begin).getBegin()) {
366 BeginExpansions[SM.getFileID(Begin)] = Begin;
367 }
368 // Move up the stack of expansion locations for the end until we find the
369 // location in BeginExpansions with that has the same file id.
370 for (SourceLocation End = R.getEnd(); End.isValid();
371 End = End.isFileID() ? includeHashLoc(SM.getFileID(End), SM)
372 : toTokenRange(SM.getImmediateExpansionRange(End),
373 SM, LangOpts)
374 .getEnd()) {
375 auto It = BeginExpansions.find(SM.getFileID(End));
376 if (It != BeginExpansions.end()) {
377 if (SM.getFileOffset(It->second) > SM.getFileOffset(End))
378 return SourceLocation();
379 return {It->second, End};
380 }
381 }
382 return SourceRange();
Shaurya Gupta8fbb6ce2019-08-06 17:01:12 +0000383}
384
385// Find an expansion range (not necessarily immediate) the ends of which are in
386// the same file id.
387static SourceRange
388getExpansionTokenRangeInSameFile(SourceLocation Loc, const SourceManager &SM,
389 const LangOptions &LangOpts) {
Sam McCallc791d852019-08-27 08:44:06 +0000390 return rangeInCommonFile(
391 toTokenRange(SM.getImmediateExpansionRange(Loc), SM, LangOpts), SM,
392 LangOpts);
Shaurya Gupta8fbb6ce2019-08-06 17:01:12 +0000393}
Sam McCallc791d852019-08-27 08:44:06 +0000394
Shaurya Gupta8fbb6ce2019-08-06 17:01:12 +0000395// Returns the file range for a given Location as a Token Range
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000396// This is quite similar to getFileLoc in SourceManager as both use
397// getImmediateExpansionRange and getImmediateSpellingLoc (for macro IDs).
398// However:
399// - We want to maintain the full range information as we move from one file to
400// the next. getFileLoc only uses the BeginLoc of getImmediateExpansionRange.
Shaurya Gupta8fbb6ce2019-08-06 17:01:12 +0000401// - We want to split '>>' tokens as the lexer parses the '>>' in nested
402// template instantiations as a '>>' instead of two '>'s.
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000403// There is also getExpansionRange but it simply calls
404// getImmediateExpansionRange on the begin and ends separately which is wrong.
405static SourceRange getTokenFileRange(SourceLocation Loc,
406 const SourceManager &SM,
407 const LangOptions &LangOpts) {
408 SourceRange FileRange = Loc;
409 while (!FileRange.getBegin().isFileID()) {
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000410 if (SM.isMacroArgExpansion(FileRange.getBegin())) {
Shaurya Gupta8fbb6ce2019-08-06 17:01:12 +0000411 FileRange = unionTokenRange(
412 SM.getImmediateSpellingLoc(FileRange.getBegin()),
413 SM.getImmediateSpellingLoc(FileRange.getEnd()), SM, LangOpts);
Sam McCallc791d852019-08-27 08:44:06 +0000414 assert(SM.isWrittenInSameFile(FileRange.getBegin(), FileRange.getEnd()));
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000415 } else {
Shaurya Gupta8fbb6ce2019-08-06 17:01:12 +0000416 SourceRange ExpansionRangeForBegin =
417 getExpansionTokenRangeInSameFile(FileRange.getBegin(), SM, LangOpts);
418 SourceRange ExpansionRangeForEnd =
419 getExpansionTokenRangeInSameFile(FileRange.getEnd(), SM, LangOpts);
Sam McCallc791d852019-08-27 08:44:06 +0000420 if (ExpansionRangeForBegin.isInvalid() ||
421 ExpansionRangeForEnd.isInvalid())
422 return SourceRange();
423 assert(SM.isWrittenInSameFile(ExpansionRangeForBegin.getBegin(),
424 ExpansionRangeForEnd.getBegin()) &&
Shaurya Gupta8fbb6ce2019-08-06 17:01:12 +0000425 "Both Expansion ranges should be in same file.");
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000426 FileRange = unionTokenRange(ExpansionRangeForBegin, ExpansionRangeForEnd,
427 SM, LangOpts);
428 }
429 }
430 return FileRange;
431}
432
Haojian Wu6ae86ea2019-07-19 08:33:39 +0000433bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM) {
434 return Loc.isValid() && SM.isWrittenInMainFile(SM.getExpansionLoc(Loc));
435}
436
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000437llvm::Optional<SourceRange> toHalfOpenFileRange(const SourceManager &SM,
Ilya Biryukov43998782019-01-31 21:30:05 +0000438 const LangOptions &LangOpts,
439 SourceRange R) {
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000440 SourceRange R1 = getTokenFileRange(R.getBegin(), SM, LangOpts);
441 if (!isValidFileRange(SM, R1))
Ilya Biryukov43998782019-01-31 21:30:05 +0000442 return llvm::None;
Ilya Biryukov43998782019-01-31 21:30:05 +0000443
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000444 SourceRange R2 = getTokenFileRange(R.getEnd(), SM, LangOpts);
445 if (!isValidFileRange(SM, R2))
Ilya Biryukov43998782019-01-31 21:30:05 +0000446 return llvm::None;
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000447
Sam McCallc791d852019-08-27 08:44:06 +0000448 SourceRange Result =
449 rangeInCommonFile(unionTokenRange(R1, R2, SM, LangOpts), SM, LangOpts);
Shaurya Gupta0d26d6f2019-07-12 11:42:31 +0000450 unsigned TokLen = getTokenLengthAtLoc(Result.getEnd(), SM, LangOpts);
451 // Convert from closed token range to half-open (char) range
452 Result.setEnd(Result.getEnd().getLocWithOffset(TokLen));
453 if (!isValidFileRange(SM, Result))
454 return llvm::None;
455
Ilya Biryukov43998782019-01-31 21:30:05 +0000456 return Result;
457}
458
459llvm::StringRef toSourceCode(const SourceManager &SM, SourceRange R) {
460 assert(isValidFileRange(SM, R));
461 bool Invalid = false;
462 auto *Buf = SM.getBuffer(SM.getFileID(R.getBegin()), &Invalid);
463 assert(!Invalid);
464
465 size_t BeginOffset = SM.getFileOffset(R.getBegin());
466 size_t EndOffset = SM.getFileOffset(R.getEnd());
467 return Buf->getBuffer().substr(BeginOffset, EndOffset - BeginOffset);
468}
469
Ilya Biryukovcce67a32019-01-29 14:17:36 +0000470llvm::Expected<SourceLocation> sourceLocationInMainFile(const SourceManager &SM,
471 Position P) {
472 llvm::StringRef Code = SM.getBuffer(SM.getMainFileID())->getBuffer();
473 auto Offset =
474 positionToOffset(Code, P, /*AllowColumnBeyondLineLength=*/false);
475 if (!Offset)
476 return Offset.takeError();
477 return SM.getLocForStartOfFile(SM.getMainFileID()).getLocWithOffset(*Offset);
478}
479
Ilya Biryukov71028b82018-03-12 15:28:22 +0000480Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
481 // Clang is 1-based, LSP uses 0-based indexes.
482 Position Begin = sourceLocToPosition(SM, R.getBegin());
483 Position End = sourceLocToPosition(SM, R.getEnd());
484
485 return {Begin, End};
486}
487
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000488std::pair<size_t, size_t> offsetToClangLineColumn(llvm::StringRef Code,
Sam McCalla4962cc2018-04-27 11:59:28 +0000489 size_t Offset) {
490 Offset = std::min(Code.size(), Offset);
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000491 llvm::StringRef Before = Code.substr(0, Offset);
Sam McCalla4962cc2018-04-27 11:59:28 +0000492 int Lines = Before.count('\n');
493 size_t PrevNL = Before.rfind('\n');
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000494 size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
Sam McCalla4962cc2018-04-27 11:59:28 +0000495 return {Lines + 1, Offset - StartOfLine + 1};
496}
497
Ilya Biryukov43998782019-01-31 21:30:05 +0000498std::pair<StringRef, StringRef> splitQualifiedName(StringRef QName) {
Marc-Andre Laperleb387b6e2018-04-23 20:00:52 +0000499 size_t Pos = QName.rfind("::");
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000500 if (Pos == llvm::StringRef::npos)
501 return {llvm::StringRef(), QName};
Marc-Andre Laperleb387b6e2018-04-23 20:00:52 +0000502 return {QName.substr(0, Pos + 2), QName.substr(Pos + 2)};
503}
504
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000505TextEdit replacementToEdit(llvm::StringRef Code,
506 const tooling::Replacement &R) {
Eric Liu9133ecd2018-05-11 12:12:08 +0000507 Range ReplacementRange = {
508 offsetToPosition(Code, R.getOffset()),
509 offsetToPosition(Code, R.getOffset() + R.getLength())};
Benjamin Krameradcd0262020-01-28 20:23:46 +0100510 return {ReplacementRange, std::string(R.getReplacementText())};
Eric Liu9133ecd2018-05-11 12:12:08 +0000511}
512
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000513std::vector<TextEdit> replacementsToEdits(llvm::StringRef Code,
Eric Liu9133ecd2018-05-11 12:12:08 +0000514 const tooling::Replacements &Repls) {
515 std::vector<TextEdit> Edits;
516 for (const auto &R : Repls)
517 Edits.push_back(replacementToEdit(Code, R));
518 return Edits;
519}
520
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000521llvm::Optional<std::string> getCanonicalPath(const FileEntry *F,
522 const SourceManager &SourceMgr) {
Kadir Cetinkayadd677932018-12-19 10:46:21 +0000523 if (!F)
524 return None;
Simon Marchi25f1f732018-08-10 22:27:53 +0000525
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000526 llvm::SmallString<128> FilePath = F->getName();
527 if (!llvm::sys::path::is_absolute(FilePath)) {
Kadir Cetinkayadd677932018-12-19 10:46:21 +0000528 if (auto EC =
Duncan P. N. Exon Smithdb8a7422019-03-26 22:32:06 +0000529 SourceMgr.getFileManager().getVirtualFileSystem().makeAbsolute(
Kadir Cetinkayadd677932018-12-19 10:46:21 +0000530 FilePath)) {
531 elog("Could not turn relative path '{0}' to absolute: {1}", FilePath,
532 EC.message());
Sam McCallc008af62018-10-20 15:30:37 +0000533 return None;
Marc-Andre Laperle1be69702018-07-05 19:35:01 +0000534 }
535 }
Simon Marchi25f1f732018-08-10 22:27:53 +0000536
Kadir Cetinkayadd677932018-12-19 10:46:21 +0000537 // Handle the symbolic link path case where the current working directory
Kadir Cetinkaya5b270932019-09-09 12:28:44 +0000538 // (getCurrentWorkingDirectory) is a symlink. We always want to the real
Kadir Cetinkayadd677932018-12-19 10:46:21 +0000539 // file path (instead of the symlink path) for the C++ symbols.
540 //
541 // Consider the following example:
542 //
543 // src dir: /project/src/foo.h
544 // current working directory (symlink): /tmp/build -> /project/src/
545 //
546 // The file path of Symbol is "/project/src/foo.h" instead of
547 // "/tmp/build/foo.h"
Harlan Haskinsa02f8572019-08-01 21:32:01 +0000548 if (auto Dir = SourceMgr.getFileManager().getDirectory(
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000549 llvm::sys::path::parent_path(FilePath))) {
550 llvm::SmallString<128> RealPath;
Harlan Haskinsa02f8572019-08-01 21:32:01 +0000551 llvm::StringRef DirName = SourceMgr.getFileManager().getCanonicalName(*Dir);
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000552 llvm::sys::path::append(RealPath, DirName,
553 llvm::sys::path::filename(FilePath));
Kadir Cetinkayadd677932018-12-19 10:46:21 +0000554 return RealPath.str().str();
Simon Marchi25f1f732018-08-10 22:27:53 +0000555 }
556
Kadir Cetinkayadd677932018-12-19 10:46:21 +0000557 return FilePath.str().str();
Marc-Andre Laperle1be69702018-07-05 19:35:01 +0000558}
559
Kadir Cetinkaya2f84d912018-08-08 08:59:29 +0000560TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M,
561 const LangOptions &L) {
562 TextEdit Result;
563 Result.range =
564 halfOpenToRange(M, Lexer::makeFileCharRange(FixIt.RemoveRange, M, L));
565 Result.newText = FixIt.CodeToInsert;
566 return Result;
567}
568
Haojian Wuaa3ed5a2019-01-25 15:14:03 +0000569bool isRangeConsecutive(const Range &Left, const Range &Right) {
Kadir Cetinkayaa9c9d002018-08-13 08:23:01 +0000570 return Left.end.line == Right.start.line &&
571 Left.end.character == Right.start.character;
572}
573
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000574FileDigest digest(llvm::StringRef Content) {
Sam McCall674d8a92019-07-08 11:33:17 +0000575 uint64_t Hash{llvm::xxHash64(Content)};
576 FileDigest Result;
577 for (unsigned I = 0; I < Result.size(); ++I) {
578 Result[I] = uint8_t(Hash);
579 Hash >>= 8;
580 }
581 return Result;
Kadir Cetinkayad08eab42018-11-27 16:08:53 +0000582}
583
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000584llvm::Optional<FileDigest> digestFile(const SourceManager &SM, FileID FID) {
Kadir Cetinkayad08eab42018-11-27 16:08:53 +0000585 bool Invalid = false;
Ilya Biryukovf2001aa2019-01-07 15:45:19 +0000586 llvm::StringRef Content = SM.getBufferData(FID, &Invalid);
Kadir Cetinkayad08eab42018-11-27 16:08:53 +0000587 if (Invalid)
588 return None;
589 return digest(Content);
590}
591
Eric Liudd662772019-01-28 14:01:55 +0000592format::FormatStyle getFormatStyleForFile(llvm::StringRef File,
593 llvm::StringRef Content,
594 llvm::vfs::FileSystem *FS) {
595 auto Style = format::getStyle(format::DefaultFormatStyle, File,
596 format::DefaultFallbackStyle, Content, FS);
597 if (!Style) {
598 log("getStyle() failed for file {0}: {1}. Fallback is LLVM style.", File,
599 Style.takeError());
600 Style = format::getLLVMStyle();
601 }
602 return *Style;
603}
604
Haojian Wu12e194c2019-02-06 15:24:50 +0000605llvm::Expected<tooling::Replacements>
606cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
607 const format::FormatStyle &Style) {
608 auto CleanReplaces = cleanupAroundReplacements(Code, Replaces, Style);
609 if (!CleanReplaces)
610 return CleanReplaces;
611 return formatReplacements(Code, std::move(*CleanReplaces), Style);
612}
613
Haojian Wuc5e4cf42019-11-07 10:53:19 +0100614static void
615lex(llvm::StringRef Code, const LangOptions &LangOpts,
Kadir Cetinkaya98bb0942020-02-27 15:10:54 +0100616 llvm::function_ref<void(const syntax::Token &, const SourceManager &SM)>
Haojian Wuc5e4cf42019-11-07 10:53:19 +0100617 Action) {
Sam McCallc316b222019-04-26 07:45:49 +0000618 // FIXME: InMemoryFileAdapter crashes unless the buffer is null terminated!
619 std::string NullTerminatedCode = Code.str();
620 SourceManagerForFile FileSM("dummy.cpp", NullTerminatedCode);
Eric Liu00d99bd2019-04-11 09:36:36 +0000621 auto &SM = FileSM.get();
Kadir Cetinkaya98bb0942020-02-27 15:10:54 +0100622 for (const auto &Tok : syntax::tokenize(SM.getMainFileID(), SM, LangOpts))
Haojian Wu7ea4c6f2019-10-30 13:21:47 +0100623 Action(Tok, SM);
Sam McCallc316b222019-04-26 07:45:49 +0000624}
625
626llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
627 const format::FormatStyle &Style) {
Eric Liu00d99bd2019-04-11 09:36:36 +0000628 llvm::StringMap<unsigned> Identifiers;
Haojian Wu7ea4c6f2019-10-30 13:21:47 +0100629 auto LangOpt = format::getFormattingLangOpts(Style);
Kadir Cetinkaya98bb0942020-02-27 15:10:54 +0100630 lex(Content, LangOpt, [&](const syntax::Token &Tok, const SourceManager &SM) {
631 if (Tok.kind() == tok::identifier)
632 ++Identifiers[Tok.text(SM)];
633 // FIXME: Should this function really return keywords too ?
634 else if (const auto *Keyword = tok::getKeywordSpelling(Tok.kind()))
635 ++Identifiers[Keyword];
Sam McCallc316b222019-04-26 07:45:49 +0000636 });
Eric Liu00d99bd2019-04-11 09:36:36 +0000637 return Identifiers;
638}
639
Haojian Wu7ea4c6f2019-10-30 13:21:47 +0100640std::vector<Range> collectIdentifierRanges(llvm::StringRef Identifier,
641 llvm::StringRef Content,
642 const LangOptions &LangOpts) {
643 std::vector<Range> Ranges;
Kadir Cetinkaya98bb0942020-02-27 15:10:54 +0100644 lex(Content, LangOpts,
645 [&](const syntax::Token &Tok, const SourceManager &SM) {
646 if (Tok.kind() != tok::identifier || Tok.text(SM) != Identifier)
647 return;
648 if (auto Range = getTokenRange(SM, LangOpts, Tok.location()))
649 Ranges.push_back(*Range);
650 });
Haojian Wu7ea4c6f2019-10-30 13:21:47 +0100651 return Ranges;
652}
653
Sam McCallc316b222019-04-26 07:45:49 +0000654namespace {
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +0200655struct NamespaceEvent {
656 enum {
657 BeginNamespace, // namespace <ns> {. Payload is resolved <ns>.
658 EndNamespace, // } // namespace <ns>. Payload is resolved *outer*
659 // namespace.
660 UsingDirective // using namespace <ns>. Payload is unresolved <ns>.
661 } Trigger;
662 std::string Payload;
663 Position Pos;
Sam McCallc316b222019-04-26 07:45:49 +0000664};
665// Scans C++ source code for constructs that change the visible namespaces.
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +0200666void parseNamespaceEvents(llvm::StringRef Code,
667 const format::FormatStyle &Style,
668 llvm::function_ref<void(NamespaceEvent)> Callback) {
Sam McCallc316b222019-04-26 07:45:49 +0000669
670 // Stack of enclosing namespaces, e.g. {"clang", "clangd"}
671 std::vector<std::string> Enclosing; // Contains e.g. "clang", "clangd"
672 // Stack counts open braces. true if the brace opened a namespace.
673 std::vector<bool> BraceStack;
674
675 enum {
676 Default,
677 Namespace, // just saw 'namespace'
678 NamespaceName, // just saw 'namespace' NSName
679 Using, // just saw 'using'
680 UsingNamespace, // just saw 'using namespace'
681 UsingNamespaceName, // just saw 'using namespace' NSName
682 } State = Default;
683 std::string NSName;
684
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +0200685 NamespaceEvent Event;
Haojian Wu7ea4c6f2019-10-30 13:21:47 +0100686 lex(Code, format::getFormattingLangOpts(Style),
Kadir Cetinkaya98bb0942020-02-27 15:10:54 +0100687 [&](const syntax::Token &Tok, const SourceManager &SM) {
688 Event.Pos = sourceLocToPosition(SM, Tok.location());
689 switch (Tok.kind()) {
690 case tok::kw_using:
691 State = State == Default ? Using : Default;
692 break;
693 case tok::kw_namespace:
694 switch (State) {
695 case Using:
696 State = UsingNamespace;
697 break;
698 case Default:
699 State = Namespace;
700 break;
701 default:
702 State = Default;
703 break;
704 }
705 break;
706 case tok::identifier:
707 switch (State) {
708 case UsingNamespace:
709 NSName.clear();
710 LLVM_FALLTHROUGH;
711 case UsingNamespaceName:
712 NSName.append(Tok.text(SM).str());
713 State = UsingNamespaceName;
714 break;
715 case Namespace:
716 NSName.clear();
717 LLVM_FALLTHROUGH;
718 case NamespaceName:
719 NSName.append(Tok.text(SM).str());
720 State = NamespaceName;
721 break;
722 case Using:
723 case Default:
724 State = Default;
725 break;
726 }
727 break;
728 case tok::coloncolon:
729 // This can come at the beginning or in the middle of a namespace
730 // name.
731 switch (State) {
732 case UsingNamespace:
733 NSName.clear();
734 LLVM_FALLTHROUGH;
735 case UsingNamespaceName:
736 NSName.append("::");
737 State = UsingNamespaceName;
738 break;
739 case NamespaceName:
740 NSName.append("::");
741 State = NamespaceName;
742 break;
743 case Namespace: // Not legal here.
744 case Using:
745 case Default:
746 State = Default;
747 break;
748 }
749 break;
750 case tok::l_brace:
751 // Record which { started a namespace, so we know when } ends one.
752 if (State == NamespaceName) {
753 // Parsed: namespace <name> {
754 BraceStack.push_back(true);
755 Enclosing.push_back(NSName);
756 Event.Trigger = NamespaceEvent::BeginNamespace;
757 Event.Payload = llvm::join(Enclosing, "::");
758 Callback(Event);
759 } else {
760 // This case includes anonymous namespaces (State = Namespace).
761 // For our purposes, they're not namespaces and we ignore them.
762 BraceStack.push_back(false);
763 }
764 State = Default;
765 break;
766 case tok::r_brace:
767 // If braces are unmatched, we're going to be confused, but don't
768 // crash.
769 if (!BraceStack.empty()) {
770 if (BraceStack.back()) {
771 // Parsed: } // namespace
772 Enclosing.pop_back();
773 Event.Trigger = NamespaceEvent::EndNamespace;
774 Event.Payload = llvm::join(Enclosing, "::");
775 Callback(Event);
776 }
777 BraceStack.pop_back();
778 }
779 break;
780 case tok::semi:
781 if (State == UsingNamespaceName) {
782 // Parsed: using namespace <name> ;
783 Event.Trigger = NamespaceEvent::UsingDirective;
784 Event.Payload = std::move(NSName);
785 Callback(Event);
786 }
787 State = Default;
788 break;
789 default:
790 State = Default;
791 break;
Sam McCallc316b222019-04-26 07:45:49 +0000792 }
Kadir Cetinkaya98bb0942020-02-27 15:10:54 +0100793 });
Sam McCallc316b222019-04-26 07:45:49 +0000794}
795
796// Returns the prefix namespaces of NS: {"" ... NS}.
797llvm::SmallVector<llvm::StringRef, 8> ancestorNamespaces(llvm::StringRef NS) {
798 llvm::SmallVector<llvm::StringRef, 8> Results;
799 Results.push_back(NS.take_front(0));
800 NS.split(Results, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
801 for (llvm::StringRef &R : Results)
802 R = NS.take_front(R.end() - NS.begin());
803 return Results;
804}
805
806} // namespace
807
808std::vector<std::string> visibleNamespaces(llvm::StringRef Code,
809 const format::FormatStyle &Style) {
810 std::string Current;
811 // Map from namespace to (resolved) namespaces introduced via using directive.
812 llvm::StringMap<llvm::StringSet<>> UsingDirectives;
813
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +0200814 parseNamespaceEvents(Code, Style, [&](NamespaceEvent Event) {
815 llvm::StringRef NS = Event.Payload;
816 switch (Event.Trigger) {
817 case NamespaceEvent::BeginNamespace:
818 case NamespaceEvent::EndNamespace:
819 Current = std::move(Event.Payload);
820 break;
821 case NamespaceEvent::UsingDirective:
822 if (NS.consume_front("::"))
823 UsingDirectives[Current].insert(NS);
824 else {
825 for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
826 if (Enclosing.empty())
827 UsingDirectives[Current].insert(NS);
828 else
829 UsingDirectives[Current].insert((Enclosing + "::" + NS).str());
830 }
831 }
832 break;
833 }
834 });
Sam McCallc316b222019-04-26 07:45:49 +0000835
836 std::vector<std::string> Found;
837 for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
Benjamin Krameradcd0262020-01-28 20:23:46 +0100838 Found.push_back(std::string(Enclosing));
Sam McCallc316b222019-04-26 07:45:49 +0000839 auto It = UsingDirectives.find(Enclosing);
840 if (It != UsingDirectives.end())
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +0200841 for (const auto &Used : It->second)
Benjamin Krameradcd0262020-01-28 20:23:46 +0100842 Found.push_back(std::string(Used.getKey()));
Sam McCallc316b222019-04-26 07:45:49 +0000843 }
844
Sam McCallc316b222019-04-26 07:45:49 +0000845 llvm::sort(Found, [&](const std::string &LHS, const std::string &RHS) {
846 if (Current == RHS)
847 return false;
848 if (Current == LHS)
849 return true;
850 return LHS < RHS;
851 });
852 Found.erase(std::unique(Found.begin(), Found.end()), Found.end());
853 return Found;
854}
855
Sam McCall9fb22b22019-05-06 10:25:10 +0000856llvm::StringSet<> collectWords(llvm::StringRef Content) {
857 // We assume short words are not significant.
858 // We may want to consider other stopwords, e.g. language keywords.
859 // (A very naive implementation showed no benefit, but lexing might do better)
860 static constexpr int MinWordLength = 4;
861
862 std::vector<CharRole> Roles(Content.size());
863 calculateRoles(Content, Roles);
864
865 llvm::StringSet<> Result;
866 llvm::SmallString<256> Word;
867 auto Flush = [&] {
868 if (Word.size() >= MinWordLength) {
869 for (char &C : Word)
870 C = llvm::toLower(C);
871 Result.insert(Word);
872 }
873 Word.clear();
874 };
875 for (unsigned I = 0; I < Content.size(); ++I) {
876 switch (Roles[I]) {
877 case Head:
878 Flush();
879 LLVM_FALLTHROUGH;
880 case Tail:
881 Word.push_back(Content[I]);
882 break;
883 case Unknown:
884 case Separator:
885 Flush();
886 break;
887 }
888 }
889 Flush();
890
891 return Result;
892}
893
Haojian Wu9d34f452019-07-01 09:26:48 +0000894llvm::Optional<DefinedMacro> locateMacroAt(SourceLocation Loc,
895 Preprocessor &PP) {
896 const auto &SM = PP.getSourceManager();
897 const auto &LangOpts = PP.getLangOpts();
898 Token Result;
899 if (Lexer::getRawToken(SM.getSpellingLoc(Loc), Result, SM, LangOpts, false))
900 return None;
901 if (Result.is(tok::raw_identifier))
902 PP.LookUpIdentifierInfo(Result);
903 IdentifierInfo *IdentifierInfo = Result.getIdentifierInfo();
904 if (!IdentifierInfo || !IdentifierInfo->hadMacroDefinition())
905 return None;
906
907 std::pair<FileID, unsigned int> DecLoc = SM.getDecomposedExpansionLoc(Loc);
908 // Get the definition just before the searched location so that a macro
909 // referenced in a '#undef MACRO' can still be found.
910 SourceLocation BeforeSearchedLocation =
911 SM.getMacroArgExpandedLocation(SM.getLocForStartOfFile(DecLoc.first)
912 .getLocWithOffset(DecLoc.second - 1));
913 MacroDefinition MacroDef =
914 PP.getMacroDefinitionAtLoc(IdentifierInfo, BeforeSearchedLocation);
915 if (auto *MI = MacroDef.getMacroInfo())
916 return DefinedMacro{IdentifierInfo->getName(), MI};
917 return None;
918}
919
Kadir Cetinkaya5b270932019-09-09 12:28:44 +0000920llvm::Expected<std::string> Edit::apply() const {
921 return tooling::applyAllReplacements(InitialCode, Replacements);
922}
923
924std::vector<TextEdit> Edit::asTextEdits() const {
925 return replacementsToEdits(InitialCode, Replacements);
926}
927
928bool Edit::canApplyTo(llvm::StringRef Code) const {
929 // Create line iterators, since line numbers are important while applying our
930 // edit we cannot skip blank lines.
931 auto LHS = llvm::MemoryBuffer::getMemBuffer(Code);
932 llvm::line_iterator LHSIt(*LHS, /*SkipBlanks=*/false);
933
934 auto RHS = llvm::MemoryBuffer::getMemBuffer(InitialCode);
935 llvm::line_iterator RHSIt(*RHS, /*SkipBlanks=*/false);
936
937 // Compare the InitialCode we prepared the edit for with the Code we received
938 // line by line to make sure there are no differences.
939 // FIXME: This check is too conservative now, it should be enough to only
940 // check lines around the replacements contained inside the Edit.
941 while (!LHSIt.is_at_eof() && !RHSIt.is_at_eof()) {
942 if (*LHSIt != *RHSIt)
943 return false;
944 ++LHSIt;
945 ++RHSIt;
946 }
947
948 // After we reach EOF for any of the files we make sure the other one doesn't
949 // contain any additional content except empty lines, they should not
950 // interfere with the edit we produced.
951 while (!LHSIt.is_at_eof()) {
952 if (!LHSIt->empty())
953 return false;
954 ++LHSIt;
955 }
956 while (!RHSIt.is_at_eof()) {
957 if (!RHSIt->empty())
958 return false;
959 ++RHSIt;
960 }
961 return true;
962}
963
964llvm::Error reformatEdit(Edit &E, const format::FormatStyle &Style) {
965 if (auto NewEdits = cleanupAndFormat(E.InitialCode, E.Replacements, Style))
966 E.Replacements = std::move(*NewEdits);
967 else
968 return NewEdits.takeError();
969 return llvm::Error::success();
970}
971
Kadir Cetinkayad62e3ed2019-09-25 11:35:38 +0200972EligibleRegion getEligiblePoints(llvm::StringRef Code,
973 llvm::StringRef FullyQualifiedName,
974 const format::FormatStyle &Style) {
975 EligibleRegion ER;
976 // Start with global namespace.
977 std::vector<std::string> Enclosing = {""};
978 // FIXME: In addition to namespaces try to generate events for function
979 // definitions as well. One might use a closing parantheses(")" followed by an
980 // opening brace "{" to trigger the start.
981 parseNamespaceEvents(Code, Style, [&](NamespaceEvent Event) {
982 // Using Directives only introduces declarations to current scope, they do
983 // not change the current namespace, so skip them.
984 if (Event.Trigger == NamespaceEvent::UsingDirective)
985 return;
986 // Do not qualify the global namespace.
987 if (!Event.Payload.empty())
988 Event.Payload.append("::");
989
990 std::string CurrentNamespace;
991 if (Event.Trigger == NamespaceEvent::BeginNamespace) {
992 Enclosing.emplace_back(std::move(Event.Payload));
993 CurrentNamespace = Enclosing.back();
994 // parseNameSpaceEvents reports the beginning position of a token; we want
995 // to insert after '{', so increment by one.
996 ++Event.Pos.character;
997 } else {
998 // Event.Payload points to outer namespace when exiting a scope, so use
999 // the namespace we've last entered instead.
1000 CurrentNamespace = std::move(Enclosing.back());
1001 Enclosing.pop_back();
1002 assert(Enclosing.back() == Event.Payload);
1003 }
1004
1005 // Ignore namespaces that are not a prefix of the target.
1006 if (!FullyQualifiedName.startswith(CurrentNamespace))
1007 return;
1008
1009 // Prefer the namespace that shares the longest prefix with target.
1010 if (CurrentNamespace.size() > ER.EnclosingNamespace.size()) {
1011 ER.EligiblePoints.clear();
1012 ER.EnclosingNamespace = CurrentNamespace;
1013 }
1014 if (CurrentNamespace.size() == ER.EnclosingNamespace.size())
1015 ER.EligiblePoints.emplace_back(std::move(Event.Pos));
1016 });
1017 // If there were no shared namespaces just return EOF.
1018 if (ER.EligiblePoints.empty()) {
1019 assert(ER.EnclosingNamespace.empty());
1020 ER.EligiblePoints.emplace_back(offsetToPosition(Code, Code.size()));
1021 }
1022 return ER;
1023}
1024
Haojian Wu509efe52019-11-13 16:30:07 +01001025bool isHeaderFile(llvm::StringRef FileName,
1026 llvm::Optional<LangOptions> LangOpts) {
1027 // Respect the langOpts, for non-file-extension cases, e.g. standard library
1028 // files.
1029 if (LangOpts && LangOpts->IsHeaderFile)
1030 return true;
1031 namespace types = clang::driver::types;
1032 auto Lang = types::lookupTypeForExtension(
1033 llvm::sys::path::extension(FileName).substr(1));
1034 return Lang != types::TY_INVALID && types::onlyPrecompileType(Lang);
1035}
1036
Haojian Wuf8865c02020-02-05 12:03:29 +01001037bool isProtoFile(SourceLocation Loc, const SourceManager &SM) {
1038 auto FileName = SM.getFilename(Loc);
1039 if (!FileName.endswith(".proto.h") && !FileName.endswith(".pb.h"))
1040 return false;
1041 auto FID = SM.getFileID(Loc);
1042 // All proto generated headers should start with this line.
1043 static const char *PROTO_HEADER_COMMENT =
1044 "// Generated by the protocol buffer compiler. DO NOT EDIT!";
1045 // Double check that this is an actual protobuf header.
1046 return SM.getBufferData(FID).startswith(PROTO_HEADER_COMMENT);
1047}
1048
Sam McCallb536a2a2017-12-19 12:23:48 +00001049} // namespace clangd
1050} // namespace clang