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 ↗

(On Diff #88436)

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

[grimar]

lld/ELF/ScriptLexer.cpp

187 ↗

(On Diff #88436)

May be just:

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

lld/trunk/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/trunk/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/trunk/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);
+
+    // 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++];
 }

lld/trunk/test/ELF/linkerscript/operators.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: echo "SECTIONS { \
 # RUN:  plus = 1 + 2 + 3; \
 # RUN:  minus = 5 - 1; \
 # RUN:  div = 6 / 2; \
 # RUN:  mul = 1 + 2 * 3; \
+# RUN:  nospace = 1+2*6/3; \
 # RUN:  braces = 1 + (2 + 3) * 4; \
 # RUN:  and = 0xbb & 0xee; \
 # RUN:  ternary1 = 1 ? 1 : 2; \
 # RUN:  ternary2 = 0 ? 1 : 2; \
 # RUN:  less = 1 < 0 ? 1 : 2; \
 # RUN:  lesseq = 1 <= 1 ? 1 : 2; \
 # RUN:  greater = 0 > 1 ? 1 : 2; \
 # RUN:  greatereq = 1 >= 1 ? 1 : 2; \

 # RUN: }" > %t.script
 # RUN: ld.lld %t --script %t.script -o %t2
 # RUN: llvm-objdump -t %t2 | FileCheck %s
 
 # CHECK: 00000000000006 *ABS* 00000000 plus
 # CHECK: 00000000000004 *ABS* 00000000 minus
 # CHECK: 00000000000003 *ABS* 00000000 div
 # CHECK: 00000000000007 *ABS* 00000000 mul
+# CHECK: 00000000000005 *ABS* 00000000 nospace
 # CHECK: 00000000000015 *ABS* 00000000 braces
 # CHECK: 000000000000aa *ABS* 00000000 and
 # CHECK: 00000000000001 *ABS* 00000000 ternary1
 # CHECK: 00000000000002 *ABS* 00000000 ternary2
 # CHECK: 00000000000002 *ABS* 00000000 less
 # CHECK: 00000000000001 *ABS* 00000000 lesseq
 # CHECK: 00000000000002 *ABS* 00000000 greater
 # CHECK: 00000000000001 *ABS* 00000000 greatereq