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 "Logger.h"
11 #include "clang/AST/ASTContext.h"
12 #include "clang/Basic/SourceManager.h"
13 #include "clang/Lex/Lexer.h"
14 #include "llvm/ADT/None.h"
15 #include "llvm/ADT/StringRef.h"
16 #include "llvm/Support/Errc.h"
17 #include "llvm/Support/Error.h"
18 #include "llvm/Support/Path.h"
19 
20 namespace clang {
21 namespace clangd {
22 
23 // Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
24 // Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
25 
26 // Iterates over unicode codepoints in the (UTF-8) string. For each,
27 // invokes CB(UTF-8 length, UTF-16 length), and breaks if it returns true.
28 // Returns true if CB returned true, false if we hit the end of string.
29 template <typename Callback>
30 static bool iterateCodepoints(llvm::StringRef U8, const Callback &CB) {
31   for (size_t I = 0; I < U8.size();) {
32     unsigned char C = static_cast<unsigned char>(U8[I]);
33     if (LLVM_LIKELY(!(C & 0x80))) { // ASCII character.
34       if (CB(1, 1))
35         return true;
36       ++I;
37       continue;
38     }
39     // This convenient property of UTF-8 holds for all non-ASCII characters.
40     size_t UTF8Length = llvm::countLeadingOnes(C);
41     // 0xxx is ASCII, handled above. 10xxx is a trailing byte, invalid here.
42     // 11111xxx is not valid UTF-8 at all. Assert because it's probably our bug.
43     assert((UTF8Length >= 2 && UTF8Length <= 4) &&
44            "Invalid UTF-8, or transcoding bug?");
45     I += UTF8Length; // Skip over all trailing bytes.
46     // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
47     // Astral codepoints are encoded as 4 bytes in UTF-8 (11110xxx ...)
48     if (CB(UTF8Length, UTF8Length == 4 ? 2 : 1))
49       return true;
50   }
51   return false;
52 }
53 
54 // Returns the offset into the string that matches \p Units UTF-16 code units.
55 // Conceptually, this converts to UTF-16, truncates to CodeUnits, converts back
56 // to UTF-8, and returns the length in bytes.
57 static size_t measureUTF16(llvm::StringRef U8, int U16Units, bool &Valid) {
58   size_t Result = 0;
59   Valid = U16Units == 0 || iterateCodepoints(U8, [&](int U8Len, int U16Len) {
60             Result += U8Len;
61             U16Units -= U16Len;
62             return U16Units <= 0;
63           });
64   if (U16Units < 0) // Offset was into the middle of a surrogate pair.
65     Valid = false;
66   // Don't return an out-of-range index if we overran.
67   return std::min(Result, U8.size());
68 }
69 
70 // Like most strings in clangd, the input is UTF-8 encoded.
71 size_t lspLength(llvm::StringRef Code) {
72   // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
73   // Astral codepoints are encoded as 4 bytes in UTF-8, starting with 11110xxx.
74   size_t Count = 0;
75   iterateCodepoints(Code, [&](int U8Len, int U16Len) {
76     Count += U16Len;
77     return false;
78   });
79   return Count;
80 }
81 
82 llvm::Expected<size_t> positionToOffset(llvm::StringRef Code, Position P,
83                                         bool AllowColumnsBeyondLineLength) {
84   if (P.line < 0)
85     return llvm::make_error<llvm::StringError>(
86         llvm::formatv("Line value can't be negative ({0})", P.line),
87         llvm::errc::invalid_argument);
88   if (P.character < 0)
89     return llvm::make_error<llvm::StringError>(
90         llvm::formatv("Character value can't be negative ({0})", P.character),
91         llvm::errc::invalid_argument);
92   size_t StartOfLine = 0;
93   for (int I = 0; I != P.line; ++I) {
94     size_t NextNL = Code.find('\n', StartOfLine);
95     if (NextNL == llvm::StringRef::npos)
96       return llvm::make_error<llvm::StringError>(
97           llvm::formatv("Line value is out of range ({0})", P.line),
98           llvm::errc::invalid_argument);
99     StartOfLine = NextNL + 1;
100   }
101 
102   size_t NextNL = Code.find('\n', StartOfLine);
103   if (NextNL == llvm::StringRef::npos)
104     NextNL = Code.size();
105 
106   bool Valid;
107   size_t ByteOffsetInLine = measureUTF16(
108       Code.substr(StartOfLine, NextNL - StartOfLine), P.character, Valid);
109   if (!Valid && !AllowColumnsBeyondLineLength)
110     return llvm::make_error<llvm::StringError>(
111         llvm::formatv("UTF-16 offset {0} is invalid for line {1}", P.character,
112                       P.line),
113         llvm::errc::invalid_argument);
114   return StartOfLine + ByteOffsetInLine;
115 }
116 
117 Position offsetToPosition(llvm::StringRef Code, size_t Offset) {
118   Offset = std::min(Code.size(), Offset);
119   llvm::StringRef Before = Code.substr(0, Offset);
120   int Lines = Before.count('\n');
121   size_t PrevNL = Before.rfind('\n');
122   size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
123   Position Pos;
124   Pos.line = Lines;
125   Pos.character = lspLength(Before.substr(StartOfLine));
126   return Pos;
127 }
128 
129 Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc) {
130   // We use the SourceManager's line tables, but its column number is in bytes.
131   FileID FID;
132   unsigned Offset;
133   std::tie(FID, Offset) = SM.getDecomposedSpellingLoc(Loc);
134   Position P;
135   P.line = static_cast<int>(SM.getLineNumber(FID, Offset)) - 1;
136   bool Invalid = false;
137   llvm::StringRef Code = SM.getBufferData(FID, &Invalid);
138   if (!Invalid) {
139     auto ColumnInBytes = SM.getColumnNumber(FID, Offset) - 1;
140     auto LineSoFar = Code.substr(Offset - ColumnInBytes, ColumnInBytes);
141     P.character = lspLength(LineSoFar);
142   }
143   return P;
144 }
145 
146 bool isValidFileRange(const SourceManager &Mgr, SourceRange R) {
147   if (!R.getBegin().isValid() || !R.getEnd().isValid())
148     return false;
149 
150   FileID BeginFID;
151   size_t BeginOffset = 0;
152   std::tie(BeginFID, BeginOffset) = Mgr.getDecomposedLoc(R.getBegin());
153 
154   FileID EndFID;
155   size_t EndOffset = 0;
156   std::tie(EndFID, EndOffset) = Mgr.getDecomposedLoc(R.getEnd());
157 
158   return BeginFID.isValid() && BeginFID == EndFID && BeginOffset <= EndOffset;
159 }
160 
161 bool halfOpenRangeContains(const SourceManager &Mgr, SourceRange R,
162                            SourceLocation L) {
163   assert(isValidFileRange(Mgr, R));
164 
165   FileID BeginFID;
166   size_t BeginOffset = 0;
167   std::tie(BeginFID, BeginOffset) = Mgr.getDecomposedLoc(R.getBegin());
168   size_t EndOffset = Mgr.getFileOffset(R.getEnd());
169 
170   FileID LFid;
171   size_t LOffset;
172   std::tie(LFid, LOffset) = Mgr.getDecomposedLoc(L);
173   return BeginFID == LFid && BeginOffset <= LOffset && LOffset < EndOffset;
174 }
175 
176 bool halfOpenRangeTouches(const SourceManager &Mgr, SourceRange R,
177                           SourceLocation L) {
178   return L == R.getEnd() || halfOpenRangeContains(Mgr, R, L);
179 }
180 
181 llvm::Optional<SourceRange> toHalfOpenFileRange(const SourceManager &Mgr,
182                                                 const LangOptions &LangOpts,
183                                                 SourceRange R) {
184   auto Begin = Mgr.getFileLoc(R.getBegin());
185   if (Begin.isInvalid())
186     return llvm::None;
187   auto End = Mgr.getFileLoc(R.getEnd());
188   if (End.isInvalid())
189     return llvm::None;
190   End = Lexer::getLocForEndOfToken(End, 0, Mgr, LangOpts);
191 
192   SourceRange Result(Begin, End);
193   if (!isValidFileRange(Mgr, Result))
194     return llvm::None;
195   return Result;
196 }
197 
198 llvm::StringRef toSourceCode(const SourceManager &SM, SourceRange R) {
199   assert(isValidFileRange(SM, R));
200   bool Invalid = false;
201   auto *Buf = SM.getBuffer(SM.getFileID(R.getBegin()), &Invalid);
202   assert(!Invalid);
203 
204   size_t BeginOffset = SM.getFileOffset(R.getBegin());
205   size_t EndOffset = SM.getFileOffset(R.getEnd());
206   return Buf->getBuffer().substr(BeginOffset, EndOffset - BeginOffset);
207 }
208 
209 llvm::Expected<SourceLocation> sourceLocationInMainFile(const SourceManager &SM,
210                                                         Position P) {
211   llvm::StringRef Code = SM.getBuffer(SM.getMainFileID())->getBuffer();
212   auto Offset =
213       positionToOffset(Code, P, /*AllowColumnBeyondLineLength=*/false);
214   if (!Offset)
215     return Offset.takeError();
216   return SM.getLocForStartOfFile(SM.getMainFileID()).getLocWithOffset(*Offset);
217 }
218 
219 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
220   // Clang is 1-based, LSP uses 0-based indexes.
221   Position Begin = sourceLocToPosition(SM, R.getBegin());
222   Position End = sourceLocToPosition(SM, R.getEnd());
223 
224   return {Begin, End};
225 }
226 
227 std::pair<size_t, size_t> offsetToClangLineColumn(llvm::StringRef Code,
228                                                   size_t Offset) {
229   Offset = std::min(Code.size(), Offset);
230   llvm::StringRef Before = Code.substr(0, Offset);
231   int Lines = Before.count('\n');
232   size_t PrevNL = Before.rfind('\n');
233   size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
234   return {Lines + 1, Offset - StartOfLine + 1};
235 }
236 
237 std::pair<StringRef, StringRef> splitQualifiedName(StringRef QName) {
238   size_t Pos = QName.rfind("::");
239   if (Pos == llvm::StringRef::npos)
240     return {llvm::StringRef(), QName};
241   return {QName.substr(0, Pos + 2), QName.substr(Pos + 2)};
242 }
243 
244 TextEdit replacementToEdit(llvm::StringRef Code,
245                            const tooling::Replacement &R) {
246   Range ReplacementRange = {
247       offsetToPosition(Code, R.getOffset()),
248       offsetToPosition(Code, R.getOffset() + R.getLength())};
249   return {ReplacementRange, R.getReplacementText()};
250 }
251 
252 std::vector<TextEdit> replacementsToEdits(llvm::StringRef Code,
253                                           const tooling::Replacements &Repls) {
254   std::vector<TextEdit> Edits;
255   for (const auto &R : Repls)
256     Edits.push_back(replacementToEdit(Code, R));
257   return Edits;
258 }
259 
260 llvm::Optional<std::string> getCanonicalPath(const FileEntry *F,
261                                              const SourceManager &SourceMgr) {
262   if (!F)
263     return None;
264 
265   llvm::SmallString<128> FilePath = F->getName();
266   if (!llvm::sys::path::is_absolute(FilePath)) {
267     if (auto EC =
268             SourceMgr.getFileManager().getVirtualFileSystem()->makeAbsolute(
269                 FilePath)) {
270       elog("Could not turn relative path '{0}' to absolute: {1}", FilePath,
271            EC.message());
272       return None;
273     }
274   }
275 
276   // Handle the symbolic link path case where the current working directory
277   // (getCurrentWorkingDirectory) is a symlink./ We always want to the real
278   // file path (instead of the symlink path) for the  C++ symbols.
279   //
280   // Consider the following example:
281   //
282   //   src dir: /project/src/foo.h
283   //   current working directory (symlink): /tmp/build -> /project/src/
284   //
285   //  The file path of Symbol is "/project/src/foo.h" instead of
286   //  "/tmp/build/foo.h"
287   if (const DirectoryEntry *Dir = SourceMgr.getFileManager().getDirectory(
288           llvm::sys::path::parent_path(FilePath))) {
289     llvm::SmallString<128> RealPath;
290     llvm::StringRef DirName = SourceMgr.getFileManager().getCanonicalName(Dir);
291     llvm::sys::path::append(RealPath, DirName,
292                             llvm::sys::path::filename(FilePath));
293     return RealPath.str().str();
294   }
295 
296   return FilePath.str().str();
297 }
298 
299 TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M,
300                     const LangOptions &L) {
301   TextEdit Result;
302   Result.range =
303       halfOpenToRange(M, Lexer::makeFileCharRange(FixIt.RemoveRange, M, L));
304   Result.newText = FixIt.CodeToInsert;
305   return Result;
306 }
307 
308 bool isRangeConsecutive(const Range &Left, const Range &Right) {
309   return Left.end.line == Right.start.line &&
310          Left.end.character == Right.start.character;
311 }
312 
313 FileDigest digest(llvm::StringRef Content) {
314   return llvm::SHA1::hash({(const uint8_t *)Content.data(), Content.size()});
315 }
316 
317 llvm::Optional<FileDigest> digestFile(const SourceManager &SM, FileID FID) {
318   bool Invalid = false;
319   llvm::StringRef Content = SM.getBufferData(FID, &Invalid);
320   if (Invalid)
321     return None;
322   return digest(Content);
323 }
324 
325 format::FormatStyle getFormatStyleForFile(llvm::StringRef File,
326                                           llvm::StringRef Content,
327                                           llvm::vfs::FileSystem *FS) {
328   auto Style = format::getStyle(format::DefaultFormatStyle, File,
329                                 format::DefaultFallbackStyle, Content, FS);
330   if (!Style) {
331     log("getStyle() failed for file {0}: {1}. Fallback is LLVM style.", File,
332         Style.takeError());
333     Style = format::getLLVMStyle();
334   }
335   return *Style;
336 }
337 
338 llvm::Expected<tooling::Replacements>
339 cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
340                  const format::FormatStyle &Style) {
341   auto CleanReplaces = cleanupAroundReplacements(Code, Replaces, Style);
342   if (!CleanReplaces)
343     return CleanReplaces;
344   return formatReplacements(Code, std::move(*CleanReplaces), Style);
345 }
346 
347 } // namespace clangd
348 } // namespace clang
349