|
150
|
1 //===- ScriptLexer.cpp ----------------------------------------------------===//
|
|
|
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 //
|
|
|
9 // This file defines a lexer for the linker script.
|
|
|
10 //
|
|
|
11 // The linker script's grammar is not complex but ambiguous due to the
|
|
|
12 // lack of the formal specification of the language. What we are trying to
|
|
|
13 // do in this and other files in LLD is to make a "reasonable" linker
|
|
|
14 // script processor.
|
|
|
15 //
|
|
|
16 // Among simplicity, compatibility and efficiency, we put the most
|
|
|
17 // emphasis on simplicity when we wrote this lexer. Compatibility with the
|
|
|
18 // GNU linkers is important, but we did not try to clone every tiny corner
|
|
|
19 // case of their lexers, as even ld.bfd and ld.gold are subtly different
|
|
|
20 // in various corner cases. We do not care much about efficiency because
|
|
|
21 // the time spent in parsing linker scripts is usually negligible.
|
|
|
22 //
|
|
|
23 // Our grammar of the linker script is LL(2), meaning that it needs at
|
|
|
24 // most two-token lookahead to parse. The only place we need two-token
|
|
|
25 // lookahead is labels in version scripts, where we need to parse "local :"
|
|
|
26 // as if "local:".
|
|
|
27 //
|
|
|
28 // Overall, this lexer works fine for most linker scripts. There might
|
|
|
29 // be room for improving compatibility, but that's probably not at the
|
|
|
30 // top of our todo list.
|
|
|
31 //
|
|
|
32 //===----------------------------------------------------------------------===//
|
|
|
33
|
|
|
34 #include "ScriptLexer.h"
|
|
|
35 #include "lld/Common/ErrorHandler.h"
|
|
|
36 #include "llvm/ADT/Twine.h"
|
|
236
|
37 #include "llvm/Support/ErrorHandling.h"
|
|
|
38 #include <algorithm>
|
|
150
|
39
|
|
|
40 using namespace llvm;
|
|
173
|
41 using namespace lld;
|
|
|
42 using namespace lld::elf;
|
|
150
|
43
|
|
|
44 // Returns a whole line containing the current token.
|
|
|
45 StringRef ScriptLexer::getLine() {
|
|
|
46 StringRef s = getCurrentMB().getBuffer();
|
|
|
47 StringRef tok = tokens[pos - 1];
|
|
|
48
|
|
|
49 size_t pos = s.rfind('\n', tok.data() - s.data());
|
|
|
50 if (pos != StringRef::npos)
|
|
|
51 s = s.substr(pos + 1);
|
|
|
52 return s.substr(0, s.find_first_of("\r\n"));
|
|
|
53 }
|
|
|
54
|
|
|
55 // Returns 1-based line number of the current token.
|
|
|
56 size_t ScriptLexer::getLineNumber() {
|
|
221
|
57 if (pos == 0)
|
|
|
58 return 1;
|
|
150
|
59 StringRef s = getCurrentMB().getBuffer();
|
|
|
60 StringRef tok = tokens[pos - 1];
|
|
223
|
61 const size_t tokOffset = tok.data() - s.data();
|
|
|
62
|
|
|
63 // For the first token, or when going backwards, start from the beginning of
|
|
|
64 // the buffer. If this token is after the previous token, start from the
|
|
|
65 // previous token.
|
|
|
66 size_t line = 1;
|
|
|
67 size_t start = 0;
|
|
|
68 if (lastLineNumberOffset > 0 && tokOffset >= lastLineNumberOffset) {
|
|
|
69 start = lastLineNumberOffset;
|
|
|
70 line = lastLineNumber;
|
|
|
71 }
|
|
|
72
|
|
|
73 line += s.substr(start, tokOffset - start).count('\n');
|
|
|
74
|
|
|
75 // Store the line number of this token for reuse.
|
|
|
76 lastLineNumberOffset = tokOffset;
|
|
|
77 lastLineNumber = line;
|
|
|
78
|
|
|
79 return line;
|
|
150
|
80 }
|
|
|
81
|
|
|
82 // Returns 0-based column number of the current token.
|
|
|
83 size_t ScriptLexer::getColumnNumber() {
|
|
|
84 StringRef tok = tokens[pos - 1];
|
|
|
85 return tok.data() - getLine().data();
|
|
|
86 }
|
|
|
87
|
|
|
88 std::string ScriptLexer::getCurrentLocation() {
|
|
|
89 std::string filename = std::string(getCurrentMB().getBufferIdentifier());
|
|
|
90 return (filename + ":" + Twine(getLineNumber())).str();
|
|
|
91 }
|
|
|
92
|
|
|
93 ScriptLexer::ScriptLexer(MemoryBufferRef mb) { tokenize(mb); }
|
|
|
94
|
|
|
95 // We don't want to record cascading errors. Keep only the first one.
|
|
|
96 void ScriptLexer::setError(const Twine &msg) {
|
|
|
97 if (errorCount())
|
|
|
98 return;
|
|
|
99
|
|
|
100 std::string s = (getCurrentLocation() + ": " + msg).str();
|
|
|
101 if (pos)
|
|
|
102 s += "\n>>> " + getLine().str() + "\n>>> " +
|
|
|
103 std::string(getColumnNumber(), ' ') + "^";
|
|
|
104 error(s);
|
|
|
105 }
|
|
|
106
|
|
|
107 // Split S into linker script tokens.
|
|
|
108 void ScriptLexer::tokenize(MemoryBufferRef mb) {
|
|
|
109 std::vector<StringRef> vec;
|
|
|
110 mbs.push_back(mb);
|
|
|
111 StringRef s = mb.getBuffer();
|
|
|
112 StringRef begin = s;
|
|
|
113
|
|
|
114 for (;;) {
|
|
|
115 s = skipSpace(s);
|
|
|
116 if (s.empty())
|
|
|
117 break;
|
|
|
118
|
|
|
119 // Quoted token. Note that double-quote characters are parts of a token
|
|
|
120 // because, in a glob match context, only unquoted tokens are interpreted
|
|
|
121 // as glob patterns. Double-quoted tokens are literal patterns in that
|
|
|
122 // context.
|
|
252
|
123 if (s.starts_with("\"")) {
|
|
150
|
124 size_t e = s.find("\"", 1);
|
|
|
125 if (e == StringRef::npos) {
|
|
|
126 StringRef filename = mb.getBufferIdentifier();
|
|
|
127 size_t lineno = begin.substr(0, s.data() - begin.data()).count('\n');
|
|
|
128 error(filename + ":" + Twine(lineno + 1) + ": unclosed quote");
|
|
|
129 return;
|
|
|
130 }
|
|
|
131
|
|
|
132 vec.push_back(s.take_front(e + 1));
|
|
|
133 s = s.substr(e + 1);
|
|
|
134 continue;
|
|
|
135 }
|
|
|
136
|
|
236
|
137 // Some operators form separate tokens.
|
|
252
|
138 if (s.starts_with("<<=") || s.starts_with(">>=")) {
|
|
236
|
139 vec.push_back(s.substr(0, 3));
|
|
|
140 s = s.substr(3);
|
|
|
141 continue;
|
|
|
142 }
|
|
252
|
143 if (s.size() > 1 && ((s[1] == '=' && strchr("*/+-<>&^|", s[0])) ||
|
|
236
|
144 (s[0] == s[1] && strchr("<>&|", s[0])))) {
|
|
150
|
145 vec.push_back(s.substr(0, 2));
|
|
|
146 s = s.substr(2);
|
|
|
147 continue;
|
|
|
148 }
|
|
|
149
|
|
|
150 // Unquoted token. This is more relaxed than tokens in C-like language,
|
|
|
151 // so that you can write "file-name.cpp" as one bare token, for example.
|
|
|
152 size_t pos = s.find_first_not_of(
|
|
|
153 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
|
|
|
154 "0123456789_.$/\\~=+[]*?-!^:");
|
|
|
155
|
|
|
156 // A character that cannot start a word (which is usually a
|
|
|
157 // punctuation) forms a single character token.
|
|
|
158 if (pos == 0)
|
|
|
159 pos = 1;
|
|
|
160 vec.push_back(s.substr(0, pos));
|
|
|
161 s = s.substr(pos);
|
|
|
162 }
|
|
|
163
|
|
|
164 tokens.insert(tokens.begin() + pos, vec.begin(), vec.end());
|
|
|
165 }
|
|
|
166
|
|
|
167 // Skip leading whitespace characters or comments.
|
|
|
168 StringRef ScriptLexer::skipSpace(StringRef s) {
|
|
|
169 for (;;) {
|
|
252
|
170 if (s.starts_with("/*")) {
|
|
150
|
171 size_t e = s.find("*/", 2);
|
|
|
172 if (e == StringRef::npos) {
|
|
221
|
173 setError("unclosed comment in a linker script");
|
|
150
|
174 return "";
|
|
|
175 }
|
|
|
176 s = s.substr(e + 2);
|
|
|
177 continue;
|
|
|
178 }
|
|
252
|
179 if (s.starts_with("#")) {
|
|
150
|
180 size_t e = s.find('\n', 1);
|
|
|
181 if (e == StringRef::npos)
|
|
|
182 e = s.size() - 1;
|
|
|
183 s = s.substr(e + 1);
|
|
|
184 continue;
|
|
|
185 }
|
|
|
186 size_t size = s.size();
|
|
|
187 s = s.ltrim();
|
|
|
188 if (s.size() == size)
|
|
|
189 return s;
|
|
|
190 }
|
|
|
191 }
|
|
|
192
|
|
|
193 // An erroneous token is handled as if it were the last token before EOF.
|
|
|
194 bool ScriptLexer::atEOF() { return errorCount() || tokens.size() == pos; }
|
|
|
195
|
|
|
196 // Split a given string as an expression.
|
|
|
197 // This function returns "3", "*" and "5" for "3*5" for example.
|
|
|
198 static std::vector<StringRef> tokenizeExpr(StringRef s) {
|
|
252
|
199 StringRef ops = "!~*/+-<>?^:="; // List of operators
|
|
150
|
200
|
|
|
201 // Quoted strings are literal strings, so we don't want to split it.
|
|
252
|
202 if (s.starts_with("\""))
|
|
150
|
203 return {s};
|
|
|
204
|
|
|
205 // Split S with operators as separators.
|
|
|
206 std::vector<StringRef> ret;
|
|
|
207 while (!s.empty()) {
|
|
|
208 size_t e = s.find_first_of(ops);
|
|
|
209
|
|
|
210 // No need to split if there is no operator.
|
|
|
211 if (e == StringRef::npos) {
|
|
|
212 ret.push_back(s);
|
|
|
213 break;
|
|
|
214 }
|
|
|
215
|
|
173
|
216 // Get a token before the operator.
|
|
150
|
217 if (e != 0)
|
|
|
218 ret.push_back(s.substr(0, e));
|
|
|
219
|
|
|
220 // Get the operator as a token.
|
|
|
221 // Keep !=, ==, >=, <=, << and >> operators as a single tokens.
|
|
252
|
222 if (s.substr(e).starts_with("!=") || s.substr(e).starts_with("==") ||
|
|
|
223 s.substr(e).starts_with(">=") || s.substr(e).starts_with("<=") ||
|
|
|
224 s.substr(e).starts_with("<<") || s.substr(e).starts_with(">>")) {
|
|
150
|
225 ret.push_back(s.substr(e, 2));
|
|
|
226 s = s.substr(e + 2);
|
|
|
227 } else {
|
|
|
228 ret.push_back(s.substr(e, 1));
|
|
|
229 s = s.substr(e + 1);
|
|
|
230 }
|
|
|
231 }
|
|
|
232 return ret;
|
|
|
233 }
|
|
|
234
|
|
|
235 // In contexts where expressions are expected, the lexer should apply
|
|
|
236 // different tokenization rules than the default one. By default,
|
|
|
237 // arithmetic operator characters are regular characters, but in the
|
|
|
238 // expression context, they should be independent tokens.
|
|
|
239 //
|
|
|
240 // For example, "foo*3" should be tokenized to "foo", "*" and "3" only
|
|
|
241 // in the expression context.
|
|
|
242 //
|
|
|
243 // This function may split the current token into multiple tokens.
|
|
|
244 void ScriptLexer::maybeSplitExpr() {
|
|
|
245 if (!inExpr || errorCount() || atEOF())
|
|
|
246 return;
|
|
|
247
|
|
|
248 std::vector<StringRef> v = tokenizeExpr(tokens[pos]);
|
|
|
249 if (v.size() == 1)
|
|
|
250 return;
|
|
|
251 tokens.erase(tokens.begin() + pos);
|
|
|
252 tokens.insert(tokens.begin() + pos, v.begin(), v.end());
|
|
|
253 }
|
|
|
254
|
|
|
255 StringRef ScriptLexer::next() {
|
|
|
256 maybeSplitExpr();
|
|
|
257
|
|
|
258 if (errorCount())
|
|
|
259 return "";
|
|
|
260 if (atEOF()) {
|
|
|
261 setError("unexpected EOF");
|
|
|
262 return "";
|
|
|
263 }
|
|
|
264 return tokens[pos++];
|
|
|
265 }
|
|
|
266
|
|
|
267 StringRef ScriptLexer::peek() {
|
|
|
268 StringRef tok = next();
|
|
|
269 if (errorCount())
|
|
|
270 return "";
|
|
|
271 pos = pos - 1;
|
|
|
272 return tok;
|
|
|
273 }
|
|
|
274
|
|
|
275 StringRef ScriptLexer::peek2() {
|
|
|
276 skip();
|
|
|
277 StringRef tok = next();
|
|
|
278 if (errorCount())
|
|
|
279 return "";
|
|
|
280 pos = pos - 2;
|
|
|
281 return tok;
|
|
|
282 }
|
|
|
283
|
|
|
284 bool ScriptLexer::consume(StringRef tok) {
|
|
|
285 if (peek() == tok) {
|
|
|
286 skip();
|
|
|
287 return true;
|
|
|
288 }
|
|
|
289 return false;
|
|
|
290 }
|
|
|
291
|
|
|
292 // Consumes Tok followed by ":". Space is allowed between Tok and ":".
|
|
|
293 bool ScriptLexer::consumeLabel(StringRef tok) {
|
|
|
294 if (consume((tok + ":").str()))
|
|
|
295 return true;
|
|
|
296 if (tokens.size() >= pos + 2 && tokens[pos] == tok &&
|
|
|
297 tokens[pos + 1] == ":") {
|
|
|
298 pos += 2;
|
|
|
299 return true;
|
|
|
300 }
|
|
|
301 return false;
|
|
|
302 }
|
|
|
303
|
|
|
304 void ScriptLexer::skip() { (void)next(); }
|
|
|
305
|
|
|
306 void ScriptLexer::expect(StringRef expect) {
|
|
|
307 if (errorCount())
|
|
|
308 return;
|
|
|
309 StringRef tok = next();
|
|
|
310 if (tok != expect)
|
|
|
311 setError(expect + " expected, but got " + tok);
|
|
|
312 }
|
|
|
313
|
|
|
314 // Returns true if S encloses T.
|
|
|
315 static bool encloses(StringRef s, StringRef t) {
|
|
|
316 return s.bytes_begin() <= t.bytes_begin() && t.bytes_end() <= s.bytes_end();
|
|
|
317 }
|
|
|
318
|
|
|
319 MemoryBufferRef ScriptLexer::getCurrentMB() {
|
|
|
320 // Find input buffer containing the current token.
|
|
221
|
321 assert(!mbs.empty());
|
|
|
322 if (pos == 0)
|
|
|
323 return mbs.back();
|
|
150
|
324 for (MemoryBufferRef mb : mbs)
|
|
|
325 if (encloses(mb.getBuffer(), tokens[pos - 1]))
|
|
|
326 return mb;
|
|
|
327 llvm_unreachable("getCurrentMB: failed to find a token");
|
|
|
328 }
|
