1 //===--- SourceCode.h - Manipulating source code as strings -----*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 #include "SourceCode.h"
10 
11 #include "clang/Basic/SourceManager.h"
12 #include "llvm/Support/Errc.h"
13 #include "llvm/Support/Error.h"
14 
15 namespace clang {
16 namespace clangd {
17 using namespace llvm;
18 
19 // Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
20 // Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
21 
22 // Iterates over unicode codepoints in the (UTF-8) string. For each,
23 // invokes CB(UTF-8 length, UTF-16 length), and breaks if it returns true.
24 // Returns true if CB returned true, false if we hit the end of string.
25 template <typename Callback>
26 static bool iterateCodepoints(StringRef U8, const Callback &CB) {
27   for (size_t I = 0; I < U8.size();) {
28     unsigned char C = static_cast<unsigned char>(U8[I]);
29     if (LLVM_LIKELY(!(C & 0x80))) { // ASCII character.
30       if (CB(1, 1))
31         return true;
32       ++I;
33       continue;
34     }
35     // This convenient property of UTF-8 holds for all non-ASCII characters.
36     size_t UTF8Length = countLeadingOnes(C);
37     // 0xxx is ASCII, handled above. 10xxx is a trailing byte, invalid here.
38     // 11111xxx is not valid UTF-8 at all. Assert because it's probably our bug.
39     assert((UTF8Length >= 2 && UTF8Length <= 4) &&
40            "Invalid UTF-8, or transcoding bug?");
41     I += UTF8Length; // Skip over all trailing bytes.
42     // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
43     // Astral codepoints are encoded as 4 bytes in UTF-8 (11110xxx ...)
44     if (CB(UTF8Length, UTF8Length == 4 ? 2 : 1))
45       return true;
46   }
47   return false;
48 }
49 
50 // Returns the offset into the string that matches \p Units UTF-16 code units.
51 // Conceptually, this converts to UTF-16, truncates to CodeUnits, converts back
52 // to UTF-8, and returns the length in bytes.
53 static size_t measureUTF16(StringRef U8, int U16Units, bool &Valid) {
54   size_t Result = 0;
55   Valid = U16Units == 0 || iterateCodepoints(U8, [&](int U8Len, int U16Len) {
56             Result += U8Len;
57             U16Units -= U16Len;
58             return U16Units <= 0;
59           });
60   if (U16Units < 0) // Offset was into the middle of a surrogate pair.
61     Valid = false;
62   // Don't return an out-of-range index if we overran.
63   return std::min(Result, U8.size());
64 }
65 
66 // Counts the number of UTF-16 code units needed to represent a string.
67 // Like most strings in clangd, the input is UTF-8 encoded.
68 static size_t utf16Len(StringRef U8) {
69   // A codepoint takes two UTF-16 code unit if it's astral (outside BMP).
70   // Astral codepoints are encoded as 4 bytes in UTF-8, starting with 11110xxx.
71   size_t Count = 0;
72   iterateCodepoints(U8, [&](int U8Len, int U16Len) {
73     Count += U16Len;
74     return false;
75   });
76   return Count;
77 }
78 
79 llvm::Expected<size_t> positionToOffset(StringRef Code, Position P,
80                                         bool AllowColumnsBeyondLineLength) {
81   if (P.line < 0)
82     return llvm::make_error<llvm::StringError>(
83         llvm::formatv("Line value can't be negative ({0})", P.line),
84         llvm::errc::invalid_argument);
85   if (P.character < 0)
86     return llvm::make_error<llvm::StringError>(
87         llvm::formatv("Character value can't be negative ({0})", P.character),
88         llvm::errc::invalid_argument);
89   size_t StartOfLine = 0;
90   for (int I = 0; I != P.line; ++I) {
91     size_t NextNL = Code.find('\n', StartOfLine);
92     if (NextNL == StringRef::npos)
93       return llvm::make_error<llvm::StringError>(
94           llvm::formatv("Line value is out of range ({0})", P.line),
95           llvm::errc::invalid_argument);
96     StartOfLine = NextNL + 1;
97   }
98 
99   size_t NextNL = Code.find('\n', StartOfLine);
100   if (NextNL == StringRef::npos)
101     NextNL = Code.size();
102 
103   bool Valid;
104   size_t ByteOffsetInLine = measureUTF16(
105       Code.substr(StartOfLine, NextNL - StartOfLine), P.character, Valid);
106   if (!Valid && !AllowColumnsBeyondLineLength)
107     return llvm::make_error<llvm::StringError>(
108         llvm::formatv("UTF-16 offset {0} is invalid for line {1}", P.character,
109                       P.line),
110         llvm::errc::invalid_argument);
111   return StartOfLine + ByteOffsetInLine;
112 }
113 
114 Position offsetToPosition(StringRef Code, size_t Offset) {
115   Offset = std::min(Code.size(), Offset);
116   StringRef Before = Code.substr(0, Offset);
117   int Lines = Before.count('\n');
118   size_t PrevNL = Before.rfind('\n');
119   size_t StartOfLine = (PrevNL == StringRef::npos) ? 0 : (PrevNL + 1);
120   Position Pos;
121   Pos.line = Lines;
122   Pos.character = utf16Len(Before.substr(StartOfLine));
123   return Pos;
124 }
125 
126 Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc) {
127   // We use the SourceManager's line tables, but its column number is in bytes.
128   FileID FID;
129   unsigned Offset;
130   std::tie(FID, Offset) = SM.getDecomposedSpellingLoc(Loc);
131   Position P;
132   P.line = static_cast<int>(SM.getLineNumber(FID, Offset)) - 1;
133   bool Invalid = false;
134   StringRef Code = SM.getBufferData(FID, &Invalid);
135   if (!Invalid) {
136     auto ColumnInBytes = SM.getColumnNumber(FID, Offset) - 1;
137     auto LineSoFar = Code.substr(Offset - ColumnInBytes, ColumnInBytes);
138     P.character = utf16Len(LineSoFar);
139   }
140   return P;
141 }
142 
143 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
144   // Clang is 1-based, LSP uses 0-based indexes.
145   Position Begin = sourceLocToPosition(SM, R.getBegin());
146   Position End = sourceLocToPosition(SM, R.getEnd());
147 
148   return {Begin, End};
149 }
150 
151 std::pair<size_t, size_t> offsetToClangLineColumn(StringRef Code,
152                                                   size_t Offset) {
153   Offset = std::min(Code.size(), Offset);
154   StringRef Before = Code.substr(0, Offset);
155   int Lines = Before.count('\n');
156   size_t PrevNL = Before.rfind('\n');
157   size_t StartOfLine = (PrevNL == StringRef::npos) ? 0 : (PrevNL + 1);
158   return {Lines + 1, Offset - StartOfLine + 1};
159 }
160 
161 std::pair<llvm::StringRef, llvm::StringRef>
162 splitQualifiedName(llvm::StringRef QName) {
163   size_t Pos = QName.rfind("::");
164   if (Pos == llvm::StringRef::npos)
165     return {StringRef(), QName};
166   return {QName.substr(0, Pos + 2), QName.substr(Pos + 2)};
167 }
168 
169 TextEdit replacementToEdit(StringRef Code, const tooling::Replacement &R) {
170   Range ReplacementRange = {
171       offsetToPosition(Code, R.getOffset()),
172       offsetToPosition(Code, R.getOffset() + R.getLength())};
173   return {ReplacementRange, R.getReplacementText()};
174 }
175 
176 std::vector<TextEdit> replacementsToEdits(StringRef Code,
177                                           const tooling::Replacements &Repls) {
178   std::vector<TextEdit> Edits;
179   for (const auto &R : Repls)
180     Edits.push_back(replacementToEdit(Code, R));
181   return Edits;
182 }
183 
184 } // namespace clangd
185 } // namespace clang
186