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// Overall, this lexer works fine for most linker scripts. There might
24// be room for improving compatibility, but that's probably not at the
25// top of our todo list.
26//
27//===----------------------------------------------------------------------===//
28
29#include "ScriptLexer.h"
30#include "Config.h"
31#include "llvm/ADT/Twine.h"
32#include "llvm/Support/ErrorHandling.h"
33#include "llvm/Support/FileSystem.h"
34#include "llvm/Support/Path.h"
35
36using namespace llvm;
37using namespace lld;
38using namespace lld::elf;
39
40ScriptLexer::Buffer::Buffer(Ctx &ctx, MemoryBufferRef mb)
41 : s(mb.getBuffer()), filename(mb.getBufferIdentifier()),
42 begin(mb.getBufferStart()) {
43 if (ctx.arg.sysroot == "")
44 return;
45 StringRef path = filename;
46 for (; !path.empty(); path = sys::path::parent_path(path)) {
47 if (!sys::fs::equivalent(A: ctx.arg.sysroot, B: path))
48 continue;
49 isUnderSysroot = true;
50 return;
51 }
52}
53
54ScriptLexer::ScriptLexer(Ctx &ctx, MemoryBufferRef mb)
55 : ctx(ctx), curBuf(ctx, mb) {
56 activeFilenames.insert(V: mb.getBufferIdentifier());
57}
58
59// Returns a whole line containing the current token.
60StringRef ScriptLexer::getLine() {
61 StringRef s(curBuf.begin, curBuf.s.end() - curBuf.begin);
62 size_t pos = s.rfind(C: '\n', From: prevTok.data() - s.data());
63 if (pos != StringRef::npos)
64 s = s.substr(Start: pos + 1);
65 return s.substr(Start: 0, N: s.find_first_of(Chars: "\r\n"));
66}
67
68// Returns 0-based column number of the current token.
69size_t ScriptLexer::getColumnNumber() {
70 return prevTok.data() - getLine().data();
71}
72
73std::string ScriptLexer::getCurrentLocation() {
74 return (curBuf.filename + ":" + Twine(prevTokLine)).str();
75}
76
77// We don't want to record cascading errors. Keep only the first one.
78void ScriptLexer::setError(const Twine &msg) {
79 if (errCount(ctx))
80 return;
81
82 std::string s = (getCurrentLocation() + ": " + msg).str();
83 if (prevTok.size())
84 s += "\n>>> " + getLine().str() + "\n>>> " +
85 std::string(getColumnNumber(), ' ') + "^";
86 ErrAlways(ctx) << s;
87}
88
89void ScriptLexer::lex() {
90 for (;;) {
91 StringRef &s = curBuf.s;
92 s = skipSpace(s);
93 if (s.empty()) {
94 // If this buffer is from an INCLUDE, the caller is responsible for
95 // popping to the parent buffer.
96 eof = true;
97 return;
98 }
99 curTokState = lexState;
100
101 // Quoted token. Note that double-quote characters are parts of a token
102 // because, in a glob match context, only unquoted tokens are interpreted
103 // as glob patterns. Double-quoted tokens are literal patterns in that
104 // context.
105 if (s.starts_with(Prefix: "\"")) {
106 size_t e = s.find(Str: "\"", From: 1);
107 if (e == StringRef::npos) {
108 size_t lineno =
109 StringRef(curBuf.begin, s.data() - curBuf.begin).count(C: '\n');
110 ErrAlways(ctx) << curBuf.filename << ":" << (lineno + 1)
111 << ": unclosed quote";
112 return;
113 }
114
115 curTok = s.take_front(N: e + 1);
116 s = s.substr(Start: e + 1);
117 return;
118 }
119
120 // In Script and Expr states, recognize compound assignment operators.
121 auto recognizeAssign = [&]() -> bool {
122 if (s.starts_with(Prefix: "<<=") || s.starts_with(Prefix: ">>=")) {
123 curTok = s.substr(Start: 0, N: 3);
124 s = s.substr(Start: 3);
125 return true;
126 }
127 if (s.size() > 1 && (s[1] == '=' && strchr(s: "+-*/!&^|", c: s[0]))) {
128 curTok = s.substr(Start: 0, N: 2);
129 s = s.substr(Start: 2);
130 return true;
131 }
132 return false;
133 };
134
135 // Unquoted token. The non-expression token is more relaxed than tokens in
136 // C-like languages, so that you can write "file-name.cpp" as one bare
137 // token.
138 size_t pos;
139 constexpr StringRef scriptAndVersionChars =
140 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
141 "0123456789_.$/\\~=+[]*?-!^:";
142 constexpr StringRef exprChars =
143 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
144 "0123456789_.$";
145 switch (lexState) {
146 case State::Script:
147 if (recognizeAssign())
148 return;
149 pos = s.find_first_not_of(Chars: scriptAndVersionChars);
150 break;
151 case State::Expr:
152 if (recognizeAssign())
153 return;
154 pos = s.find_first_not_of(Chars: exprChars);
155 if (pos == 0 && s.size() >= 2 &&
156 ((s[0] == s[1] && strchr(s: "<>&|", c: s[0])) ||
157 is_contained(Set: {"==", "!=", "<=", ">=", "<<", ">>"}, Element: s.substr(Start: 0, N: 2))))
158 pos = 2;
159 break;
160 case State::VersionNode:
161 // Treat `:` as a token boundary unless it's part of a scope operator `::`
162 // (for extern "C++"). This behavior resembles GNU ld and allows proper
163 // tokenization of patterns like `local:*`.
164 pos = 0;
165 for (; pos != s.size(); ++pos) {
166 if (s[pos] == ':') {
167 if (pos + 1 != s.size() && s[pos + 1] == ':') {
168 ++pos;
169 continue;
170 }
171 } else if (scriptAndVersionChars.contains(C: s[pos]))
172 continue;
173 break;
174 }
175 break;
176 }
177
178 if (pos == 0)
179 pos = 1;
180 curTok = s.substr(Start: 0, N: pos);
181 s = s.substr(Start: pos);
182 break;
183 }
184}
185
186// Skip leading whitespace characters or comments.
187StringRef ScriptLexer::skipSpace(StringRef s) {
188 for (;;) {
189 if (s.starts_with(Prefix: "/*")) {
190 size_t e = s.find(Str: "*/", From: 2);
191 if (e == StringRef::npos) {
192 setError("unclosed comment in a linker script");
193 return "";
194 }
195 curBuf.lineNumber += s.substr(Start: 0, N: e).count(C: '\n');
196 s = s.substr(Start: e + 2);
197 continue;
198 }
199 if (s.starts_with(Prefix: "#")) {
200 size_t e = s.find(C: '\n', From: 1);
201 if (e == StringRef::npos)
202 e = s.size() - 1;
203 else
204 ++curBuf.lineNumber;
205 s = s.substr(Start: e + 1);
206 continue;
207 }
208 StringRef saved = s;
209 s = s.ltrim();
210 auto len = saved.size() - s.size();
211 if (len == 0)
212 return s;
213 curBuf.lineNumber += saved.substr(Start: 0, N: len).count(C: '\n');
214 }
215}
216
217// Used to determine whether to stop parsing. Treat errors like EOF.
218bool ScriptLexer::atEOF() { return eof || errCount(ctx); }
219
220StringRef ScriptLexer::next() {
221 prevTok = peek();
222 // `prevTokLine` is not updated for EOF so that the line number in `setError`
223 // will be more useful.
224 if (prevTok.size())
225 prevTokLine = curBuf.lineNumber;
226 return std::exchange(obj&: curTok, new_val: StringRef(curBuf.s.data(), 0));
227}
228
229StringRef ScriptLexer::peek() {
230 // curTok is invalid if curTokState and lexState mismatch.
231 if (curTok.size() && curTokState != lexState) {
232 curBuf.s = StringRef(curTok.data(), curBuf.s.end() - curTok.data());
233 curTok = {};
234 }
235 if (curTok.empty())
236 lex();
237 return curTok;
238}
239
240bool ScriptLexer::consume(StringRef tok) {
241 if (peek() != tok)
242 return false;
243 next();
244 return true;
245}
246
247void ScriptLexer::skip() { (void)next(); }
248
249void ScriptLexer::expect(StringRef expect) {
250 if (errCount(ctx))
251 return;
252 StringRef tok = next();
253 if (tok != expect) {
254 if (atEOF())
255 setError("unexpected EOF");
256 else
257 setError(expect + " expected, but got " + tok);
258 }
259}
260
261ScriptLexer::Token ScriptLexer::till(StringRef tok) {
262 StringRef str = next();
263 if (str == tok)
264 return {};
265 if (!atEOF())
266 return {.str: str};
267 prevTok = {};
268 setError("unexpected EOF");
269 return {};
270}
271