Apply different tokenization rules to linker script expressions.

[ruiu]

Summary

The linker script lexer is context-sensitive. In the regular context,
arithmetic operator characters are regular characters, but in the
expression context, they are independent tokens. This afects how the
lexer tokenizes "3*4", for example. (This kind of expression is real;
the Linux kernel uses it.)

This patch defines function maybeSplitExpr. This function splits the
current token into multiple expression tokens if the lexer is in the
expression context.

[grimar]

:) I think that approach implements exactly what I had in mind when wrote
in "[llvm-dev] Linking Linux kernel with LLD" thread:

"I was thinking about entering some special parser state for
extracting sub tokens from tokens transparently when
we are inside code that evaluates the expression."

Looks good to me.

lld/test/ELF/linkerscript/operators.s

13

I would add another sub-case, which tests all operators you support in patch.

[grimar]

lld/ELF/ScriptLexer.cpp

187

May be just:

  E = std::max(E, 1);
  Ret.push_back(S.substr(0, E));
  S = S.substr(E);
}

lld/ELF/LinkerScript.cpp

static bool isAbsolute(StringRef S) {
   return ScriptBase->isAbsolute(S);
 }
 
 SymbolAssignment *ScriptParser::readAssignment(StringRef Name) {
   StringRef Op = next();
   Expr E;
   assert(Op == "=" || Op == "+=");
   if (consume("ABSOLUTE")) {
-    // The RHS may be something like "ABSOLUTE(.) & 0xff".
-    // Call readExpr1 to read the whole expression.
-    E = readExpr1(readParenExpr(), 0);
+    E = readExpr();
     E.IsAbsolute = [] { return true; };
   } else {
     E = readExpr();
   }
   if (Op == "+=") {
     std::string Loc = getCurrentLocation();
     E = [=](uint64_t Dot) {
       return getSymbolValue(Loc, Name, Dot) + E(Dot);
     };
   }
   return new SymbolAssignment(Name, E);
 }
 
 // This is an operator-precedence parser to parse a linker
 // script expression.
-Expr ScriptParser::readExpr() { return readExpr1(readPrimary(), 0); }
+Expr ScriptParser::readExpr() {
+  // Our lexer is context-aware. Set the in-expression bit so that
+  // they apply different tokenization rules.
+  bool Orig = InExpr;
+  InExpr = true;
+  Expr E = readExpr1(readPrimary(), 0);
+  InExpr = Orig;
+  return E;
+}
 
 static Expr combine(StringRef Op, Expr L, Expr R) {
   auto IsAbs = [=] { return L.IsAbsolute() && R.IsAbsolute(); };
   auto GetOutSec = [=] {
     const OutputSectionBase *S = L.Section();
     return S ? S : R.Section();
   };
 

lld/ELF/ScriptLexer.h

public:
   StringRef peek(unsigned N = 0);
   void skip();
   bool consume(StringRef Tok);
   void expect(StringRef Expect);
   std::string getCurrentLocation();
 
   std::vector<MemoryBufferRef> MBs;
   std::vector<StringRef> Tokens;
+  bool InExpr = false;
   size_t Pos = 0;
   bool Error = false;
 
 private:
+  void maybeSplitExpr();
   StringRef getLine();
   size_t getLineNumber();
   size_t getColumnNumber();
 
   MemoryBufferRef getCurrentMB();
 };
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/ScriptLexer.cpp

 // 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's room
-// for improving compatibility, but that's probably not at the top of our
-// todo list.
-//
-// A caveat: This lexer splits an input string into tokens ahead of time,
-// so the lexer is not context aware. There's one known corner case. Let's
-// say the next string is "val*3" (without quotes). In the context where
-// the parser is expecting an expression, that should be tokenizes to
-// "val", "*" and "3". In other context, it should be just a single
-// token. (If it is in a filename context, it'll be interpeted as a glob
-// pattern, for example.)  We want to fix this, but it probably needs a
-// redesign of this lexer.
+// 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;
for (;;) {
     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);
+    if (E == StringRef::npos) {
+      Ret.push_back(S);
+      break;
+    }
+
+    if (E != 0) {
+      Ret.push_back(S.substr(0, E));
+      S = S.substr(E);
+      continue;
+    }
+
+    Ret.push_back(S.substr(0, 1));
+    S = S.substr(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(unsigned N) {
+  maybeSplitExpr();
+
   StringRef Tok;
   for (unsigned I = 0; I <= N; ++I) {
     Tok = next();
     if (Error)
       return "";
   }
   Pos = Pos - N - 1;
   return Tok;

lld/test/ELF/linkerscript/operators.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: echo "SECTIONS { \
 # RUN:  . = 0xFFF0; \
 # RUN:  . = . + 0x10; \
 # RUN:  .plus : { *(.plus) } \
 # RUN:  . = 0x11010 - 0x10; \
 # RUN:  .minus : { *(.minus) } \
 # RUN:  . = 0x24000 / 0x2; \
 # RUN:  .div : { *(.div) } \
 # RUN:  . = 0x11000 + 0x1000 * 0x2; \
 # RUN:  .mul : { *(.mul) } \
-# RUN:  . = 0x10000 + (0x1000 + 0x1000) * 0x2; \
+# RUN:  . = 0x10000+(0x1000+0x1000)*0x2; \
 # RUN:  .bracket : { *(.bracket) } \
 # RUN:  . = 0x17000 & 0x15000; \
 # RUN:  .and : { *(.and) } \
 # RUN:  . = 0x1 ? 0x16000 : 0x999999; \
 # RUN:  .ternary1 : { *(.ternary1) } \
 # RUN:  . = 0x0 ? 0x999999 : 0x17000; \
 # RUN:  .ternary2 : { *(.ternary2) } \
 # RUN:  . = 0x0 < 0x1 ? 0x18000 : 0x999999; \