1 //===- ScriptLexer.cpp ----------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a lexer for the linker script.
12 // The linker script's grammar is not complex but ambiguous due to the
13 // lack of the formal specification of the language. What we are trying to
14 // do in this and other files in LLD is to make a "reasonable" linker
17 // Among simplicity, compatibility and efficiency, we put the most
18 // emphasis on simplicity when we wrote this lexer. Compatibility with the
19 // GNU linkers is important, but we did not try to clone every tiny corner
20 // case of their lexers, as even ld.bfd and ld.gold are subtly different
21 // in various corner cases. We do not care much about efficiency because
22 // the time spent in parsing linker scripts is usually negligible.
24 // Our grammar of the linker script is LL(2), meaning that it needs at
25 // most two-token lookahead to parse. The only place we need two-token
26 // lookahead is labels in version scripts, where we need to parse "local :"
29 // Overall, this lexer works fine for most linker scripts. There might
30 // be room for improving compatibility, but that's probably not at the
31 // top of our todo list.
33 //===----------------------------------------------------------------------===//
35 #include "ScriptLexer.h"
36 #include "lld/Common/ErrorHandler.h"
37 #include "llvm/ADT/Twine.h"
41 using namespace lld::elf;
43 // Returns a whole line containing the current token.
44 StringRef ScriptLexer::getLine() {
45 StringRef S = getCurrentMB().getBuffer();
46 StringRef Tok = Tokens[Pos - 1];
48 size_t Pos = S.rfind('\n', Tok.data() - S.data());
49 if (Pos != StringRef::npos)
50 S = S.substr(Pos + 1);
51 return S.substr(0, S.find_first_of("\r\n"));
54 // Returns 1-based line number of the current token.
55 size_t ScriptLexer::getLineNumber() {
56 StringRef S = getCurrentMB().getBuffer();
57 StringRef Tok = Tokens[Pos - 1];
58 return S.substr(0, Tok.data() - S.data()).count('\n') + 1;
61 // Returns 0-based column number of the current token.
62 size_t ScriptLexer::getColumnNumber() {
63 StringRef Tok = Tokens[Pos - 1];
64 return Tok.data() - getLine().data();
67 std::string ScriptLexer::getCurrentLocation() {
68 std::string Filename = getCurrentMB().getBufferIdentifier();
69 return (Filename + ":" + Twine(getLineNumber())).str();
72 ScriptLexer::ScriptLexer(MemoryBufferRef MB) { tokenize(MB); }
74 // We don't want to record cascading errors. Keep only the first one.
75 void ScriptLexer::setError(const Twine &Msg) {
79 std::string S = (getCurrentLocation() + ": " + Msg).str();
81 S += "\n>>> " + getLine().str() + "\n>>> " +
82 std::string(getColumnNumber(), ' ') + "^";
86 // Split S into linker script tokens.
87 void ScriptLexer::tokenize(MemoryBufferRef MB) {
88 std::vector<StringRef> Vec;
90 StringRef S = MB.getBuffer();
98 // Quoted token. Note that double-quote characters are parts of a token
99 // because, in a glob match context, only unquoted tokens are interpreted
100 // as glob patterns. Double-quoted tokens are literal patterns in that
102 if (S.startswith("\"")) {
103 size_t E = S.find("\"", 1);
104 if (E == StringRef::npos) {
105 StringRef Filename = MB.getBufferIdentifier();
106 size_t Lineno = Begin.substr(0, S.data() - Begin.data()).count('\n');
107 error(Filename + ":" + Twine(Lineno + 1) + ": unclosed quote");
111 Vec.push_back(S.take_front(E + 1));
116 // ">foo" is parsed to ">" and "foo", but ">>" is parsed to ">>".
117 // "|", "||", "&" and "&&" are different operators.
118 if (S.startswith("<<") || S.startswith("<=") || S.startswith(">>") ||
119 S.startswith(">=") || S.startswith("||") || S.startswith("&&")) {
120 Vec.push_back(S.substr(0, 2));
125 // Unquoted token. This is more relaxed than tokens in C-like language,
126 // so that you can write "file-name.cpp" as one bare token, for example.
127 size_t Pos = S.find_first_not_of(
128 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
129 "0123456789_.$/\\~=+[]*?-!^:");
131 // A character that cannot start a word (which is usually a
132 // punctuation) forms a single character token.
135 Vec.push_back(S.substr(0, Pos));
139 Tokens.insert(Tokens.begin() + Pos, Vec.begin(), Vec.end());
142 // Skip leading whitespace characters or comments.
143 StringRef ScriptLexer::skipSpace(StringRef S) {
145 if (S.startswith("/*")) {
146 size_t E = S.find("*/", 2);
147 if (E == StringRef::npos) {
148 error("unclosed comment in a linker script");
154 if (S.startswith("#")) {
155 size_t E = S.find('\n', 1);
156 if (E == StringRef::npos)
161 size_t Size = S.size();
163 if (S.size() == Size)
168 // An erroneous token is handled as if it were the last token before EOF.
169 bool ScriptLexer::atEOF() { return errorCount() || Tokens.size() == Pos; }
171 // Split a given string as an expression.
172 // This function returns "3", "*" and "5" for "3*5" for example.
173 static std::vector<StringRef> tokenizeExpr(StringRef S) {
174 StringRef Ops = "+-*/:!~"; // List of operators
176 // Quoted strings are literal strings, so we don't want to split it.
177 if (S.startswith("\""))
180 // Split S with operators as separators.
181 std::vector<StringRef> Ret;
183 size_t E = S.find_first_of(Ops);
185 // No need to split if there is no operator.
186 if (E == StringRef::npos) {
191 // Get a token before the opreator.
193 Ret.push_back(S.substr(0, E));
195 // Get the operator as a token. Keep != as one token.
196 if (S.substr(E).startswith("!=")) {
197 Ret.push_back(S.substr(E, 2));
200 Ret.push_back(S.substr(E, 1));
207 // In contexts where expressions are expected, the lexer should apply
208 // different tokenization rules than the default one. By default,
209 // arithmetic operator characters are regular characters, but in the
210 // expression context, they should be independent tokens.
212 // For example, "foo*3" should be tokenized to "foo", "*" and "3" only
213 // in the expression context.
215 // This function may split the current token into multiple tokens.
216 void ScriptLexer::maybeSplitExpr() {
217 if (!InExpr || errorCount() || atEOF())
220 std::vector<StringRef> V = tokenizeExpr(Tokens[Pos]);
223 Tokens.erase(Tokens.begin() + Pos);
224 Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
227 StringRef ScriptLexer::next() {
233 setError("unexpected EOF");
236 return Tokens[Pos++];
239 StringRef ScriptLexer::peek() {
240 StringRef Tok = next();
247 StringRef ScriptLexer::peek2() {
249 StringRef Tok = next();
256 bool ScriptLexer::consume(StringRef Tok) {
264 // Consumes Tok followed by ":". Space is allowed between Tok and ":".
265 bool ScriptLexer::consumeLabel(StringRef Tok) {
266 if (consume((Tok + ":").str()))
268 if (Tokens.size() >= Pos + 2 && Tokens[Pos] == Tok &&
269 Tokens[Pos + 1] == ":") {
276 void ScriptLexer::skip() { (void)next(); }
278 void ScriptLexer::expect(StringRef Expect) {
281 StringRef Tok = next();
283 setError(Expect + " expected, but got " + Tok);
286 // Returns true if S encloses T.
287 static bool encloses(StringRef S, StringRef T) {
288 return S.bytes_begin() <= T.bytes_begin() && T.bytes_end() <= S.bytes_end();
291 MemoryBufferRef ScriptLexer::getCurrentMB() {
292 // Find input buffer containing the current token.
293 assert(!MBs.empty() && Pos > 0);
294 for (MemoryBufferRef MB : MBs)
295 if (encloses(MB.getBuffer(), Tokens[Pos - 1]))
297 llvm_unreachable("getCurrentMB: failed to find a token");