1 files changed, 285 insertions, 0 deletions
diff --git a/ELF/ScriptLexer.cpp b/ELF/ScriptLexer.cpp
new file mode 100644
index 0000000000000..86720de3527cb
--- /dev/null
+++ b/ELF/ScriptLexer.cpp
@@ -0,0 +1,285 @@
+//===- ScriptLexer.cpp ----------------------------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a lexer for the linker script.
+//
+// The linker script's grammar is not complex but ambiguous due to the
+// lack of the formal specification of the language. What we are trying to
+// do in this and other files in LLD is to make a "reasonable" linker
+// script processor.
+//
+// Among simplicity, compatibility and efficiency, we put the most
+// emphasis on simplicity when we wrote this lexer. Compatibility with the
+// GNU linkers is important, but we did not try to clone every tiny corner
+// case of their lexers, as even ld.bfd and ld.gold are subtly different
+// in various corner cases. We do not care much about efficiency because
+// the time spent in parsing linker scripts is usually negligible.
+//
+// Our grammar of the linker script is LL(2), meaning that it needs at
+// most two-token lookahead to parse. The only place we need two-token
+// lookahead is labels in version scripts, where we need to parse "local :"
+// as if "local:".
+//
+// Overall, this lexer works fine for most linker scripts. There might
+// be room for improving compatibility, but that's probably not at the
+// top of our todo list.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ScriptLexer.h"
+#include "Error.h"
+#include "llvm/ADT/Twine.h"
+
+using namespace llvm;
+using namespace lld;
+using namespace lld::elf;
+
+// Returns a whole line containing the current token.
+StringRef ScriptLexer::getLine() {
+  StringRef S = getCurrentMB().getBuffer();
+  StringRef Tok = Tokens[Pos - 1];
+
+  size_t Pos = S.rfind('\n', Tok.data() - S.data());
+  if (Pos != StringRef::npos)
+    S = S.substr(Pos + 1);
+  return S.substr(0, S.find_first_of("\r\n"));
+}
+
+// Returns 1-based line number of the current token.
+size_t ScriptLexer::getLineNumber() {
+  StringRef S = getCurrentMB().getBuffer();
+  StringRef Tok = Tokens[Pos - 1];
+  return S.substr(0, Tok.data() - S.data()).count('\n') + 1;
+}
+
+// Returns 0-based column number of the current token.
+size_t ScriptLexer::getColumnNumber() {
+  StringRef Tok = Tokens[Pos - 1];
+  return Tok.data() - getLine().data();
+}
+
+std::string ScriptLexer::getCurrentLocation() {
+  std::string Filename = getCurrentMB().getBufferIdentifier();
+  if (!Pos)
+    return Filename;
+  return (Filename + ":" + Twine(getLineNumber())).str();
+}
+
+ScriptLexer::ScriptLexer(MemoryBufferRef MB) { tokenize(MB); }
+
+// We don't want to record cascading errors. Keep only the first one.
+void ScriptLexer::setError(const Twine &Msg) {
+  if (Error)
+    return;
+  Error = true;
+
+  if (!Pos) {
+    error(getCurrentLocation() + ": " + Msg);
+    return;
+  }
+
+  std::string S = getCurrentLocation() + ": ";
+  error(S + Msg);
+  error(S + getLine());
+  error(S + std::string(getColumnNumber(), ' ') + "^");
+}
+
+// Split S into linker script tokens.
+void ScriptLexer::tokenize(MemoryBufferRef MB) {
+  std::vector<StringRef> Vec;
+  MBs.push_back(MB);
+  StringRef S = MB.getBuffer();
+  StringRef Begin = S;
+
+  for (;;) {
+    S = skipSpace(S);
+    if (S.empty())
+      break;
+
+    // Quoted token. Note that double-quote characters are parts of a token
+    // because, in a glob match context, only unquoted tokens are interpreted
+    // as glob patterns. Double-quoted tokens are literal patterns in that
+    // context.
+    if (S.startswith("\"")) {
+      size_t E = S.find("\"", 1);
+      if (E == StringRef::npos) {
+        StringRef Filename = MB.getBufferIdentifier();
+        size_t Lineno = Begin.substr(0, S.data() - Begin.data()).count('\n');
+        error(Filename + ":" + Twine(Lineno + 1) + ": unclosed quote");
+        return;
+      }
+
+      Vec.push_back(S.take_front(E + 1));
+      S = S.substr(E + 1);
+      continue;
+    }
+
+    // Unquoted token. This is more relaxed than tokens in C-like language,
+    // so that you can write "file-name.cpp" as one bare token, for example.
+    size_t Pos = S.find_first_not_of(
+        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
+        "0123456789_.$/\\~=+[]*?-!<>^:");
+
+    // A character that cannot start a word (which is usually a
+    // punctuation) forms a single character token.
+    if (Pos == 0)
+      Pos = 1;
+    Vec.push_back(S.substr(0, Pos));
+    S = S.substr(Pos);
+  }
+
+  Tokens.insert(Tokens.begin() + Pos, Vec.begin(), Vec.end());
+}
+
+// Skip leading whitespace characters or comments.
+StringRef ScriptLexer::skipSpace(StringRef S) {
+  for (;;) {
+    if (S.startswith("/*")) {
+      size_t E = S.find("*/", 2);
+      if (E == StringRef::npos) {
+        error("unclosed comment in a linker script");
+        return "";
+      }
+      S = S.substr(E + 2);
+      continue;
+    }
+    if (S.startswith("#")) {
+      size_t E = S.find('\n', 1);
+      if (E == StringRef::npos)
+        E = S.size() - 1;
+      S = S.substr(E + 1);
+      continue;
+    }
+    size_t Size = S.size();
+    S = S.ltrim();
+    if (S.size() == Size)
+      return S;
+  }
+}
+
+// An erroneous token is handled as if it were the last token before EOF.
+bool ScriptLexer::atEOF() { return Error || Tokens.size() == Pos; }
+
+// Split a given string as an expression.
+// This function returns "3", "*" and "5" for "3*5" for example.
+static std::vector<StringRef> tokenizeExpr(StringRef S) {
+  StringRef Ops = "+-*/:"; // List of operators
+
+  // Quoted strings are literal strings, so we don't want to split it.
+  if (S.startswith("\""))
+    return {S};
+
+  // Split S with +-*/ as separators.
+  std::vector<StringRef> Ret;
+  while (!S.empty()) {
+    size_t E = S.find_first_of(Ops);
+
+    // No need to split if there is no operator.
+    if (E == StringRef::npos) {
+      Ret.push_back(S);
+      break;
+    }
+
+    // Get a token before the opreator.
+    if (E != 0)
+      Ret.push_back(S.substr(0, E));
+
+    // Get the operator as a token.
+    Ret.push_back(S.substr(E, 1));
+    S = S.substr(E + 1);
+  }
+  return Ret;
+}
+
+// In contexts where expressions are expected, the lexer should apply
+// different tokenization rules than the default one. By default,
+// arithmetic operator characters are regular characters, but in the
+// expression context, they should be independent tokens.
+//
+// For example, "foo*3" should be tokenized to "foo", "*" and "3" only
+// in the expression context.
+//
+// This function may split the current token into multiple tokens.
+void ScriptLexer::maybeSplitExpr() {
+  if (!InExpr || Error || atEOF())
+    return;
+
+  std::vector<StringRef> V = tokenizeExpr(Tokens[Pos]);
+  if (V.size() == 1)
+    return;
+  Tokens.erase(Tokens.begin() + Pos);
+  Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
+}
+
+StringRef ScriptLexer::next() {
+  maybeSplitExpr();
+
+  if (Error)
+    return "";
+  if (atEOF()) {
+    setError("unexpected EOF");
+    return "";
+  }
+  return Tokens[Pos++];
+}
+
+StringRef ScriptLexer::peek() {
+  StringRef Tok = next();
+  if (Error)
+    return "";
+  Pos = Pos - 1;
+  return Tok;
+}
+
+bool ScriptLexer::consume(StringRef Tok) {
+  if (peek() == Tok) {
+    skip();
+    return true;
+  }
+  return false;
+}
+
+// Consumes Tok followed by ":". Space is allowed between Tok and ":".
+bool ScriptLexer::consumeLabel(StringRef Tok) {
+  if (consume((Tok + ":").str()))
+    return true;
+  if (Tokens.size() >= Pos + 2 && Tokens[Pos] == Tok &&
+      Tokens[Pos + 1] == ":") {
+    Pos += 2;
+    return true;
+  }
+  return false;
+}
+
+void ScriptLexer::skip() { (void)next(); }
+
+void ScriptLexer::expect(StringRef Expect) {
+  if (Error)
+    return;
+  StringRef Tok = next();
+  if (Tok != Expect)
+    setError(Expect + " expected, but got " + Tok);
+}
+
+// Returns true if S encloses T.
+static bool encloses(StringRef S, StringRef T) {
+  return S.bytes_begin() <= T.bytes_begin() && T.bytes_end() <= S.bytes_end();
+}
+
+MemoryBufferRef ScriptLexer::getCurrentMB() {
+  // Find input buffer containing the current token.
+  assert(!MBs.empty());
+  if (!Pos)
+    return MBs[0];
+
+  for (MemoryBufferRef MB : MBs)
+    if (encloses(MB.getBuffer(), Tokens[Pos - 1]))
+      return MB;
+  llvm_unreachable("getCurrentMB: failed to find a token");
+}