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"
37
38 using namespace llvm;
39 using namespace lld;
40 using namespace lld::elf;
41
42 // Returns a whole line containing the current token.
getLine()43 StringRef ScriptLexer::getLine() {
44 StringRef s = getCurrentMB().getBuffer();
45 StringRef tok = tokens[pos - 1];
46
47 size_t pos = s.rfind('\n', tok.data() - s.data());
48 if (pos != StringRef::npos)
49 s = s.substr(pos + 1);
50 return s.substr(0, s.find_first_of("\r\n"));
51 }
52
53 // Returns 1-based line number of the current token.
getLineNumber()54 size_t ScriptLexer::getLineNumber() {
55 if (pos == 0)
56 return 1;
57 StringRef s = getCurrentMB().getBuffer();
58 StringRef tok = tokens[pos - 1];
59 return s.substr(0, tok.data() - s.data()).count('\n') + 1;
60 }
61
62 // Returns 0-based column number of the current token.
getColumnNumber()63 size_t ScriptLexer::getColumnNumber() {
64 StringRef tok = tokens[pos - 1];
65 return tok.data() - getLine().data();
66 }
67
getCurrentLocation()68 std::string ScriptLexer::getCurrentLocation() {
69 std::string filename = std::string(getCurrentMB().getBufferIdentifier());
70 return (filename + ":" + Twine(getLineNumber())).str();
71 }
72
ScriptLexer(MemoryBufferRef mb)73 ScriptLexer::ScriptLexer(MemoryBufferRef mb) { tokenize(mb); }
74
75 // We don't want to record cascading errors. Keep only the first one.
setError(const Twine & msg)76 void ScriptLexer::setError(const Twine &msg) {
77 if (errorCount())
78 return;
79
80 std::string s = (getCurrentLocation() + ": " + msg).str();
81 if (pos)
82 s += "\n>>> " + getLine().str() + "\n>>> " +
83 std::string(getColumnNumber(), ' ') + "^";
84 error(s);
85 }
86
87 // Split S into linker script tokens.
tokenize(MemoryBufferRef mb)88 void ScriptLexer::tokenize(MemoryBufferRef mb) {
89 std::vector<StringRef> vec;
90 mbs.push_back(mb);
91 StringRef s = mb.getBuffer();
92 StringRef begin = s;
93
94 for (;;) {
95 s = skipSpace(s);
96 if (s.empty())
97 break;
98
99 // Quoted token. Note that double-quote characters are parts of a token
100 // because, in a glob match context, only unquoted tokens are interpreted
101 // as glob patterns. Double-quoted tokens are literal patterns in that
102 // context.
103 if (s.startswith("\"")) {
104 size_t e = s.find("\"", 1);
105 if (e == StringRef::npos) {
106 StringRef filename = mb.getBufferIdentifier();
107 size_t lineno = begin.substr(0, s.data() - begin.data()).count('\n');
108 error(filename + ":" + Twine(lineno + 1) + ": unclosed quote");
109 return;
110 }
111
112 vec.push_back(s.take_front(e + 1));
113 s = s.substr(e + 1);
114 continue;
115 }
116
117 // ">foo" is parsed to ">" and "foo", but ">>" is parsed to ">>".
118 // "|", "||", "&" and "&&" are different operators.
119 if (s.startswith("<<") || s.startswith("<=") || s.startswith(">>") ||
120 s.startswith(">=") || s.startswith("||") || s.startswith("&&")) {
121 vec.push_back(s.substr(0, 2));
122 s = s.substr(2);
123 continue;
124 }
125
126 // Unquoted token. This is more relaxed than tokens in C-like language,
127 // so that you can write "file-name.cpp" as one bare token, for example.
128 size_t pos = s.find_first_not_of(
129 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
130 "0123456789_.$/\\~=+[]*?-!^:");
131
132 // A character that cannot start a word (which is usually a
133 // punctuation) forms a single character token.
134 if (pos == 0)
135 pos = 1;
136 vec.push_back(s.substr(0, pos));
137 s = s.substr(pos);
138 }
139
140 tokens.insert(tokens.begin() + pos, vec.begin(), vec.end());
141 }
142
143 // Skip leading whitespace characters or comments.
skipSpace(StringRef s)144 StringRef ScriptLexer::skipSpace(StringRef s) {
145 for (;;) {
146 if (s.startswith("/*")) {
147 size_t e = s.find("*/", 2);
148 if (e == StringRef::npos) {
149 setError("unclosed comment in a linker script");
150 return "";
151 }
152 s = s.substr(e + 2);
153 continue;
154 }
155 if (s.startswith("#")) {
156 size_t e = s.find('\n', 1);
157 if (e == StringRef::npos)
158 e = s.size() - 1;
159 s = s.substr(e + 1);
160 continue;
161 }
162 size_t size = s.size();
163 s = s.ltrim();
164 if (s.size() == size)
165 return s;
166 }
167 }
168
169 // An erroneous token is handled as if it were the last token before EOF.
atEOF()170 bool ScriptLexer::atEOF() { return errorCount() || tokens.size() == pos; }
171
172 // Split a given string as an expression.
173 // This function returns "3", "*" and "5" for "3*5" for example.
tokenizeExpr(StringRef s)174 static std::vector<StringRef> tokenizeExpr(StringRef s) {
175 StringRef ops = "+-*/:!~=<>"; // List of operators
176
177 // Quoted strings are literal strings, so we don't want to split it.
178 if (s.startswith("\""))
179 return {s};
180
181 // Split S with operators as separators.
182 std::vector<StringRef> ret;
183 while (!s.empty()) {
184 size_t e = s.find_first_of(ops);
185
186 // No need to split if there is no operator.
187 if (e == StringRef::npos) {
188 ret.push_back(s);
189 break;
190 }
191
192 // Get a token before the operator.
193 if (e != 0)
194 ret.push_back(s.substr(0, e));
195
196 // Get the operator as a token.
197 // Keep !=, ==, >=, <=, << and >> operators as a single tokens.
198 if (s.substr(e).startswith("!=") || s.substr(e).startswith("==") ||
199 s.substr(e).startswith(">=") || s.substr(e).startswith("<=") ||
200 s.substr(e).startswith("<<") || s.substr(e).startswith(">>")) {
201 ret.push_back(s.substr(e, 2));
202 s = s.substr(e + 2);
203 } else {
204 ret.push_back(s.substr(e, 1));
205 s = s.substr(e + 1);
206 }
207 }
208 return ret;
209 }
210
211 // In contexts where expressions are expected, the lexer should apply
212 // different tokenization rules than the default one. By default,
213 // arithmetic operator characters are regular characters, but in the
214 // expression context, they should be independent tokens.
215 //
216 // For example, "foo*3" should be tokenized to "foo", "*" and "3" only
217 // in the expression context.
218 //
219 // This function may split the current token into multiple tokens.
maybeSplitExpr()220 void ScriptLexer::maybeSplitExpr() {
221 if (!inExpr || errorCount() || atEOF())
222 return;
223
224 std::vector<StringRef> v = tokenizeExpr(tokens[pos]);
225 if (v.size() == 1)
226 return;
227 tokens.erase(tokens.begin() + pos);
228 tokens.insert(tokens.begin() + pos, v.begin(), v.end());
229 }
230
next()231 StringRef ScriptLexer::next() {
232 maybeSplitExpr();
233
234 if (errorCount())
235 return "";
236 if (atEOF()) {
237 setError("unexpected EOF");
238 return "";
239 }
240 return tokens[pos++];
241 }
242
peek()243 StringRef ScriptLexer::peek() {
244 StringRef tok = next();
245 if (errorCount())
246 return "";
247 pos = pos - 1;
248 return tok;
249 }
250
peek2()251 StringRef ScriptLexer::peek2() {
252 skip();
253 StringRef tok = next();
254 if (errorCount())
255 return "";
256 pos = pos - 2;
257 return tok;
258 }
259
consume(StringRef tok)260 bool ScriptLexer::consume(StringRef tok) {
261 if (peek() == tok) {
262 skip();
263 return true;
264 }
265 return false;
266 }
267
268 // Consumes Tok followed by ":". Space is allowed between Tok and ":".
consumeLabel(StringRef tok)269 bool ScriptLexer::consumeLabel(StringRef tok) {
270 if (consume((tok + ":").str()))
271 return true;
272 if (tokens.size() >= pos + 2 && tokens[pos] == tok &&
273 tokens[pos + 1] == ":") {
274 pos += 2;
275 return true;
276 }
277 return false;
278 }
279
skip()280 void ScriptLexer::skip() { (void)next(); }
281
expect(StringRef expect)282 void ScriptLexer::expect(StringRef expect) {
283 if (errorCount())
284 return;
285 StringRef tok = next();
286 if (tok != expect)
287 setError(expect + " expected, but got " + tok);
288 }
289
290 // Returns true if S encloses T.
encloses(StringRef s,StringRef t)291 static bool encloses(StringRef s, StringRef t) {
292 return s.bytes_begin() <= t.bytes_begin() && t.bytes_end() <= s.bytes_end();
293 }
294
getCurrentMB()295 MemoryBufferRef ScriptLexer::getCurrentMB() {
296 // Find input buffer containing the current token.
297 assert(!mbs.empty());
298 if (pos == 0)
299 return mbs.back();
300 for (MemoryBufferRef mb : mbs)
301 if (encloses(mb.getBuffer(), tokens[pos - 1]))
302 return mb;
303 llvm_unreachable("getCurrentMB: failed to find a token");
304 }
305