Handle ":" as a regular token character in linker scripts.

[ruiu]

Summary

This is alternative to https://reviews.llvm.org/D30500 to simplify the
version definition parser and allow ":" in symbol names.

[ruiu]

• Remove the parameter from peek().

[ruiu]

• Remove a use of Twine. We don't need that.

[grimar]

This approach sure has simpler implementation,
(when I wrote my patch, I sure thought about doing the same),
but it may open Pandora's box.

For example it is easy to copypaste "global" instead of "local" and it be accepted:

{ 
global: 
  aaa;
global: *; 
};

At fact any combinations of local and global labels are possible with it:

{
 global:
  aa;
 local:
  bb;
 global:
  cc;
 local:
  dd;
}

That opens road to writing overcomplicated and what is probably
more important - a road to write scripts that are incompatible with both BFD and gold !
I think compatibility and simplicity is what we want to deliver and if gnu linkers do not
accept that, I see that is a reason also not to accept it.
At fact you want to accept such syntax because its simplifies implementation and
that is understandable position, though I think we probably should not do that here.

[ruiu]

In D30722#696406, @grimar wrote:

This approach sure has simpler implementation,
(when I wrote my patch, I sure thought about doing the same),
but it may open Pandora's box.

For example it is easy to copypaste "global" instead of "local" and it be accepted:

{ 
global: 
  aaa;
global: *; 
};

At fact any combinations of local and global labels are possible with it:

{
 global:
  aa;
 local:
  bb;
 global:
  cc;
 local:
  dd;
}

That opens road to writing overcomplicated and what is probably
more important - a road to write scripts that are incompatible with both BFD and gold !
I think compatibility and simplicity is what we want to deliver and if gnu linkers do not
accept that, I see that is a reason also not to accept it.
At fact you want to accept such syntax because its simplifies implementation and
that is understandable position, though I think we probably should not do that here.

I disagree. If you intentionally try to break a thing, it will break, but that's not realistic. Your examples are clearly wrong and easy to fix for programmers. If you know the internal implementation of LLD and other linkers, you can always write a linker script that is broken in a subtle way in some linker but works perfectly fine with different one. For example, our lexer behaves different in corner cases from the GNU linker's because we aimed simplicity, and if you know about that, you can come up with many examples that doesn't work with our linker or their linkers. I think you are overthinking.

[ruiu]

Note that we can easily reject linker scripts that you gave me as bad examples just by counting the number of occurrences of each label in the function and doesn't allow more than one label for each label name. That's worth to do though.

[ruiu]

That's worth to do though.

That's _not_

[grimar]

Implementation is LGTM. My concern stands, but we can change it to stricter behavior separatelly.

[ruiu]

Yes, if that would raise a real issue, I can add counters to the function.

lld/ELF/Config.h

struct SymbolVersion {
   llvm::StringRef Name;
   bool IsExternCpp;
   bool HasWildcard;
 };
 
 // This struct contains symbols version definition that
 // can be found in version script if it is used for link.
 struct VersionDefinition {
-  VersionDefinition(llvm::StringRef Name, uint16_t Id) : Name(Name), Id(Id) {}
   llvm::StringRef Name;
-  uint16_t Id;
+  uint16_t Id = 0;
   std::vector<SymbolVersion> Globals;
-  size_t NameOff; // Offset in string table.
+  size_t NameOff = 0; // Offset in the string table
 };
 
 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
 // and such fields have the same name as the corresponding options.
 // Most fields are initialized by the driver.
 struct Configuration {
   InputFile *FirstElf = nullptr;

lld/ELF/LinkerScript.cpp

private:
   Expr readPrimary();
   Expr readTernary(Expr Cond);
   Expr readParenExpr();
 
   // For parsing version script.
   std::vector<SymbolVersion> readVersionExtern();
   void readAnonymousDeclaration();
   void readVersionDeclaration(StringRef VerStr);
-  std::vector<SymbolVersion> readSymbols();
-  void readLocals();
+
+  std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
+  readSymbols();
 
   ScriptConfiguration &Opt = *ScriptConfig;
   bool IsUnderSysroot;
 };
 
 void ScriptParser::readDynamicList() {
   expect("{");
   readAnonymousDeclaration();
unsigned ScriptParser::readPhdrType() {
 
   if (Ret == (unsigned)-1) {
     setError("invalid program header type: " + Tok);
     return PT_NULL;
   }
   return Ret;
 }
 
-// Reads a list of symbols, e.g. "{ global: foo; bar; local: *; };".
+// Reads an anonymous version declaration.
 void ScriptParser::readAnonymousDeclaration() {
-  // Read global symbols first. "global:" is default, so if there's
-  // no label, we assume global symbols.
-  if (peek() != "local") {
-    if (consume("global"))
-      expect(":");
-    for (SymbolVersion V : readSymbols())
-      Config->VersionScriptGlobals.push_back(V);
+  std::vector<SymbolVersion> Globals;
+  std::vector<SymbolVersion> Locals;
+  std::tie(Globals, Locals) = readSymbols();
+
+  for (SymbolVersion V : Globals)
+  for (SymbolVersion V : Locals) {
+    if (V.Name == "*")
+      Config->DefaultSymbolVersion = VER_NDX_LOCAL;
+    else
+      Config->VersionScriptLocals.push_back(V);
   }
-  readLocals();
-  expect("}");
   expect(";");
 }
 
-void ScriptParser::readLocals() {
-  if (!consume("local"))
-    return;
-  expect(":");
-  std::vector<SymbolVersion> Locals = readSymbols();
+// Reads a non-anonymous version definition,
+// e.g. "VerStr { global: foo; bar; local: *; };".
+void ScriptParser::readVersionDeclaration(StringRef VerStr) {
+  // Read a symbol list.
+  std::vector<SymbolVersion> Globals;
+  std::vector<SymbolVersion> Locals;
+  std::tie(Globals, Locals) = readSymbols();
+
   for (SymbolVersion V : Locals) {
-    if (V.Name == "*") {
+    if (V.Name == "*")
       Config->DefaultSymbolVersion = VER_NDX_LOCAL;
-      continue;
-    }
+    else
       Config->VersionScriptLocals.push_back(V);
   }
-}
 
-// Reads a list of symbols, e.g. "VerStr { global: foo; bar; local: *; };".
-void ScriptParser::readVersionDeclaration(StringRef VerStr) {
-  // Identifiers start at 2 because 0 and 1 are reserved
-  // for VER_NDX_LOCAL and VER_NDX_GLOBAL constants.
-  uint16_t VersionId = Config->VersionDefinitions.size() + 2;
-  Config->VersionDefinitions.push_back({VerStr, VersionId});
-
-  // Read global symbols.
-  if (peek() != "local") {
-    if (consume("global"))
-      expect(":");
-    Config->VersionDefinitions.back().Globals = readSymbols();
-  }
-  readLocals();
-  expect("}");
+  // Create a new version definition and add that to the global symbols.
+  VersionDefinition Ver;
+  Ver.Name = VerStr;
+  Ver.Globals = Globals;
+
+  // User-defined version number starts from 2 because 0 and 1 are
+  // reserved for VER_NDX_LOCAL and VER_NDX_GLOBAL, respectively.
+  Ver.Id = Config->VersionDefinitions.size() + 2;
+  Config->VersionDefinitions.push_back(Ver);
 
   // Each version may have a parent version. For example, "Ver2"
   // defined as "Ver2 { global: foo; local: *; } Ver1;" has "Ver1"
   // as a parent. This version hierarchy is, probably against your
   // instinct, purely for hint; the runtime doesn't care about it
   // at all. In LLD, we simply ignore it.
   if (peek() != ";")
     skip();
   expect(";");
 }
 
-// Reads a list of symbols for a versions cript.
-std::vector<SymbolVersion> ScriptParser::readSymbols() {
-  std::vector<SymbolVersion> Ret;
-  for (;;) {
-    if (consume("extern")) {
-      for (SymbolVersion V : readVersionExtern())
-        Ret.push_back(V);
+// Reads a list of symbols, e.g. "{ global: foo; bar; local: *; };".
+std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
+ScriptParser::readSymbols() {
+  std::vector<SymbolVersion> Globals;
+  std::vector<SymbolVersion> Locals;
+  std::vector<SymbolVersion> *V = &Globals;
+
+  while (!Error) {
+    if (consume("}"))
+      break;
+    if (consumeLabel("global")) {
+      V = &Globals;
+      continue;
+    }
+    if (consumeLabel("local")) {
+      V = &Locals;
       continue;
     }
 
-    if (peek() == "}" || (peek() == "local" && peek(1) == ":") || Error)
-      break;
+    if (consume("extern")) {
+      std::vector<SymbolVersion> Ext = readVersionExtern();
+      V->insert(V->end(), Ext.begin(), Ext.end());
+    } else {
       StringRef Tok = next();
-    Ret.push_back({unquote(Tok), false, hasWildcard(Tok)});
+      V->push_back({unquote(Tok), false, hasWildcard(Tok)});
+    }
     expect(";");
   }
-  return Ret;
+  return {Globals, Locals};
 }
 
 // Reads an "extern C++" directive, e.g.,
 // "extern "C++" { ns::*; "f(int, double)"; };"
 std::vector<SymbolVersion> ScriptParser::readVersionExtern() {
   StringRef Tok = next();
   bool IsCXX = Tok == "\"C++\"";
   if (!IsCXX && Tok != "\"C\"")
     setError("Unknown language");
   expect("{");
 
   std::vector<SymbolVersion> Ret;
   while (!Error && peek() != "}") {
     StringRef Tok = next();
     bool HasWildcard = !Tok.startswith("\"") && hasWildcard(Tok);
     Ret.push_back({unquote(Tok), IsCXX, HasWildcard});
     expect(";");
   }
 
   expect("}");
-  expect(";");
   return Ret;
 }
 
 uint64_t ScriptParser::readMemoryAssignment(
     StringRef S1, StringRef S2, StringRef S3) {
   if (!(consume(S1) || consume(S2) || consume(S3))) {
     setError("expected one of: " + S1 + ", " + S2 + ", or " + S3);
     return 0;

lld/ELF/ScriptLexer.h

 public:
   explicit ScriptLexer(MemoryBufferRef MB);
 
   void setError(const Twine &Msg);
   void tokenize(MemoryBufferRef MB);
   static StringRef skipSpace(StringRef S);
   bool atEOF();
   StringRef next();
-  StringRef peek(unsigned N = 0);
+  StringRef peek();
   void skip();
-  bool consume(StringRef Tok);
+  bool consume(const Twine &Tok);
   void expect(StringRef Expect);
+  bool consumeLabel(StringRef Tok);
   std::string getCurrentLocation();
 
   std::vector<MemoryBufferRef> MBs;
   std::vector<StringRef> Tokens;
   bool InExpr = false;
   size_t Pos = 0;
   bool Error = false;
 

lld/ELF/ScriptLexer.cpp

if (S.startswith("\"")) {
       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_.$/\\~=+[]*?-!<>^");
+        "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);
   }

 }
 
 // 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
+  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()) {
if (Error)
     return "";
   if (atEOF()) {
     setError("unexpected EOF");
     return "";
   }
   return Tokens[Pos++];
 }
 
-StringRef ScriptLexer::peek(unsigned N) {
-  StringRef Tok;
-  for (unsigned I = 0; I <= N; ++I) {
-    Tok = next();
-    if (Error)
-      return "";
-  }
-  Pos = Pos - N - 1;
+StringRef ScriptLexer::peek() {
+  StringRef Tok = next();
+  Pos = Pos - 1;
   return Tok;
 }
 
-bool ScriptLexer::consume(StringRef Tok) {
-  if (peek() == Tok) {
+bool ScriptLexer::consume(const Twine &Tok) {
+  if (peek() == Tok.str()) {
     skip();
     return true;
   }
   return false;
 }
 
+// Consumes Tok followed by ":". Space is allowed between Tok and ":".
+bool ScriptLexer::consumeLabel(StringRef Tok) {
+  if (consume(Tok + ":"))
+    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);

lld/test/ELF/version-script-extern-wildcards-anon.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 # RUN: echo '{ \
 # RUN:       global: \
 # RUN:       _Z3bari; \
 # RUN:       extern "C++" { \
 # RUN:         "foo(int)"; \
 # RUN:         z*; \
+# RUN:         std::q*; \
 # RUN:       }; \
 # RUN:       local: *; \
 # RUN:       }; ' > %t.script
 # RUN: ld.lld --version-script %t.script -shared %t.o -o %t.so
 # RUN: llvm-readobj -dyn-symbols %t.so | FileCheck %s
 
 # CHECK:      DynamicSymbols [
 # CHECK-NEXT:   Symbol {

 # CHECK-NEXT:     Name: _Z3zedi
 # CHECK-NEXT:     Value:
 # CHECK-NEXT:     Size:
 # CHECK-NEXT:     Binding: Global
 # CHECK-NEXT:     Type:
 # CHECK-NEXT:     Other:
 # CHECK-NEXT:     Section:
 # CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: _ZSt3qux
+# CHECK-NEXT:     Value:
+# CHECK-NEXT:     Size:
+# CHECK-NEXT:     Binding: Global
+# CHECK-NEXT:     Type:
+# CHECK-NEXT:     Other:
+# CHECK-NEXT:     Section:
+# CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
 .global _Z3fooi
 _Z3fooi:
 .global _Z3bari
 _Z3bari:
 .global _Z3zedi
 _Z3zedi:
 .global _Z3bazi
 _Z3bazi:
+.global _ZSt3qux
+_ZSt3qux: