contrib/llvm/tools/lld/ELF/ScriptLexer.cpp

   1 //===- ScriptLexer.cpp ----------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a lexer for the linker script.
  11 //
  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
  15 // script processor.
  16 //
  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.
  23 //
  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 :"
  27 // as if "local:".
  28 //
  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.
  32 //
  33 //===----------------------------------------------------------------------===//
  34
  35 #include "ScriptLexer.h"
  36 #include "lld/Common/ErrorHandler.h"
  37 #include "llvm/ADT/Twine.h"
  38
  39 using namespace llvm;
  40 using namespace lld;
  41 using namespace lld::elf;
  42
  43 // Returns a whole line containing the current token.
  44 StringRef ScriptLexer::getLine() {
  45   StringRef S = getCurrentMB().getBuffer();
  46   StringRef Tok = Tokens[Pos - 1];
  47
  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"));
  52 }
  53
  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;
  59 }
  60
  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();
  65 }
  66
  67 std::string ScriptLexer::getCurrentLocation() {
  68   std::string Filename = getCurrentMB().getBufferIdentifier();
  69   return (Filename + ":" + Twine(getLineNumber())).str();
  70 }
  71
  72 ScriptLexer::ScriptLexer(MemoryBufferRef MB) { tokenize(MB); }
  73
  74 // We don't want to record cascading errors. Keep only the first one.
  75 void ScriptLexer::setError(const Twine &Msg) {
  76   if (errorCount())
  77     return;
  78
  79   std::string S = (getCurrentLocation() + ": " + Msg).str();
  80   if (Pos)
  81     S += "\n>>> " + getLine().str() + "\n>>> " +
  82          std::string(getColumnNumber(), ' ') + "^";
  83   error(S);
  84 }
  85
  86 // Split S into linker script tokens.
  87 void ScriptLexer::tokenize(MemoryBufferRef MB) {
  88   std::vector<StringRef> Vec;
  89   MBs.push_back(MB);
  90   StringRef S = MB.getBuffer();
  91   StringRef Begin = S;
  92
  93   for (;;) {
  94     S = skipSpace(S);
  95     if (S.empty())
  96       break;
  97
  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
 101     // context.
 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");
 108         return;
 109       }
 110
 111       Vec.push_back(S.take_front(E + 1));
 112       S = S.substr(E + 1);
 113       continue;
 114     }
 115
 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));
 121       S = S.substr(2);
 122       continue;
 123     }
 124
 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_.$/\\~=+[]*?-!^:");
 130
 131     // A character that cannot start a word (which is usually a
 132     // punctuation) forms a single character token.
 133     if (Pos == 0)
 134       Pos = 1;
 135     Vec.push_back(S.substr(0, Pos));
 136     S = S.substr(Pos);
 137   }
 138
 139   Tokens.insert(Tokens.begin() + Pos, Vec.begin(), Vec.end());
 140 }
 141
 142 // Skip leading whitespace characters or comments.
 143 StringRef ScriptLexer::skipSpace(StringRef S) {
 144   for (;;) {
 145     if (S.startswith("/*")) {
 146       size_t E = S.find("*/", 2);
 147       if (E == StringRef::npos) {
 148         error("unclosed comment in a linker script");
 149         return "";
 150       }
 151       S = S.substr(E + 2);
 152       continue;
 153     }
 154     if (S.startswith("#")) {
 155       size_t E = S.find('\n', 1);
 156       if (E == StringRef::npos)
 157         E = S.size() - 1;
 158       S = S.substr(E + 1);
 159       continue;
 160     }
 161     size_t Size = S.size();
 162     S = S.ltrim();
 163     if (S.size() == Size)
 164       return S;
 165   }
 166 }
 167
 168 // An erroneous token is handled as if it were the last token before EOF.
 169 bool ScriptLexer::atEOF() { return errorCount() || Tokens.size() == Pos; }
 170
 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
 175
 176   // Quoted strings are literal strings, so we don't want to split it.
 177   if (S.startswith("\""))
 178     return {S};
 179
 180   // Split S with operators as separators.
 181   std::vector<StringRef> Ret;
 182   while (!S.empty()) {
 183     size_t E = S.find_first_of(Ops);
 184
 185     // No need to split if there is no operator.
 186     if (E == StringRef::npos) {
 187       Ret.push_back(S);
 188       break;
 189     }
 190
 191     // Get a token before the opreator.
 192     if (E != 0)
 193       Ret.push_back(S.substr(0, E));
 194
 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));
 198       S = S.substr(E + 2);
 199     } else {
 200       Ret.push_back(S.substr(E, 1));
 201       S = S.substr(E + 1);
 202     }
 203   }
 204   return Ret;
 205 }
 206
 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.
 211 //
 212 // For example, "foo*3" should be tokenized to "foo", "*" and "3" only
 213 // in the expression context.
 214 //
 215 // This function may split the current token into multiple tokens.
 216 void ScriptLexer::maybeSplitExpr() {
 217   if (!InExpr || errorCount() || atEOF())
 218     return;
 219
 220   std::vector<StringRef> V = tokenizeExpr(Tokens[Pos]);
 221   if (V.size() == 1)
 222     return;
 223   Tokens.erase(Tokens.begin() + Pos);
 224   Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
 225 }
 226
 227 StringRef ScriptLexer::next() {
 228   maybeSplitExpr();
 229
 230   if (errorCount())
 231     return "";
 232   if (atEOF()) {
 233     setError("unexpected EOF");
 234     return "";
 235   }
 236   return Tokens[Pos++];
 237 }
 238
 239 StringRef ScriptLexer::peek() {
 240   StringRef Tok = next();
 241   if (errorCount())
 242     return "";
 243   Pos = Pos - 1;
 244   return Tok;
 245 }
 246
 247 bool ScriptLexer::consume(StringRef Tok) {
 248   if (peek() == Tok) {
 249     skip();
 250     return true;
 251   }
 252   return false;
 253 }
 254
 255 // Consumes Tok followed by ":". Space is allowed between Tok and ":".
 256 bool ScriptLexer::consumeLabel(StringRef Tok) {
 257   if (consume((Tok + ":").str()))
 258     return true;
 259   if (Tokens.size() >= Pos + 2 && Tokens[Pos] == Tok &&
 260       Tokens[Pos + 1] == ":") {
 261     Pos += 2;
 262     return true;
 263   }
 264   return false;
 265 }
 266
 267 void ScriptLexer::skip() { (void)next(); }
 268
 269 void ScriptLexer::expect(StringRef Expect) {
 270   if (errorCount())
 271     return;
 272   StringRef Tok = next();
 273   if (Tok != Expect)
 274     setError(Expect + " expected, but got " + Tok);
 275 }
 276
 277 // Returns true if S encloses T.
 278 static bool encloses(StringRef S, StringRef T) {
 279   return S.bytes_begin() <= T.bytes_begin() && T.bytes_end() <= S.bytes_end();
 280 }
 281
 282 MemoryBufferRef ScriptLexer::getCurrentMB() {
 283   // Find input buffer containing the current token.
 284   assert(!MBs.empty() && Pos > 0);
 285   for (MemoryBufferRef MB : MBs)
 286     if (encloses(MB.getBuffer(), Tokens[Pos - 1]))
 287       return MB;
 288   llvm_unreachable("getCurrentMB: failed to find a token");
 289 }