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#include "llvm/Support/ErrorHandling.h"
38#include <algorithm>
39
40using namespace llvm;
41using namespace lld;
42using namespace lld::elf;
43
44// Returns a whole line containing the current token.
45StringRef 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.
56size_t ScriptLexer::getLineNumber() {
57  if (pos == 0)
58    return 1;
59  StringRef s = getCurrentMB().getBuffer();
60  StringRef tok = tokens[pos - 1];
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;
80}
81
82// Returns 0-based column number of the current token.
83size_t ScriptLexer::getColumnNumber() {
84  StringRef tok = tokens[pos - 1];
85  return tok.data() - getLine().data();
86}
87
88std::string ScriptLexer::getCurrentLocation() {
89  std::string filename = std::string(getCurrentMB().getBufferIdentifier());
90  return (filename + ":" + Twine(getLineNumber())).str();
91}
92
93ScriptLexer::ScriptLexer(MemoryBufferRef mb) { tokenize(mb); }
94
95// We don't want to record cascading errors. Keep only the first one.
96void 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.
108void 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.
123    if (s.startswith("\"")) {
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
137    // Some operators form separate tokens.
138    if (s.startswith("<<=") || s.startswith(">>=")) {
139      vec.push_back(s.substr(0, 3));
140      s = s.substr(3);
141      continue;
142    }
143    if (s.size() > 1 && ((s[1] == '=' && strchr("*/+-<>&|", s[0])) ||
144                         (s[0] == s[1] && strchr("<>&|", s[0])))) {
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.
168StringRef ScriptLexer::skipSpace(StringRef s) {
169  for (;;) {
170    if (s.startswith("/*")) {
171      size_t e = s.find("*/", 2);
172      if (e == StringRef::npos) {
173        setError("unclosed comment in a linker script");
174        return "";
175      }
176      s = s.substr(e + 2);
177      continue;
178    }
179    if (s.startswith("#")) {
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.
194bool 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.
198static std::vector<StringRef> tokenizeExpr(StringRef s) {
199  StringRef ops = "!~*/+-<>?:="; // List of operators
200
201  // Quoted strings are literal strings, so we don't want to split it.
202  if (s.startswith("\""))
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
216    // Get a token before the operator.
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.
222    if (s.substr(e).startswith("!=") || s.substr(e).startswith("==") ||
223        s.substr(e).startswith(">=") || s.substr(e).startswith("<=") ||
224        s.substr(e).startswith("<<") || s.substr(e).startswith(">>")) {
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.
244void 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
255StringRef 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
267StringRef ScriptLexer::peek() {
268  StringRef tok = next();
269  if (errorCount())
270    return "";
271  pos = pos - 1;
272  return tok;
273}
274
275StringRef ScriptLexer::peek2() {
276  skip();
277  StringRef tok = next();
278  if (errorCount())
279    return "";
280  pos = pos - 2;
281  return tok;
282}
283
284bool 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 ":".
293bool 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
304void ScriptLexer::skip() { (void)next(); }
305
306void 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.
315static bool encloses(StringRef s, StringRef t) {
316  return s.bytes_begin() <= t.bytes_begin() && t.bytes_end() <= s.bytes_end();
317}
318
319MemoryBufferRef ScriptLexer::getCurrentMB() {
320  // Find input buffer containing the current token.
321  assert(!mbs.empty());
322  if (pos == 0)
323    return mbs.back();
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}
329