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