[ELF] - Do not treat colon(":") as separate token in script parser.

[grimar]

Summary

This is PR32091,

it has next script which we failed to parse.

GLIBCXX_3.4 {
    extern "C++" {
...
        std::set_new_handler*;
        std::set_terminate*;
        std::set_unexpected*;
        std::type_info::__*;
    }
}

Patch changes logic to not treat ":" as separate token to fix issue.

[ruiu]

Are you sure this is correct? I was thinking that this is about quoted strings. This allows something like extern "C++" { std::foo; } (as opposed to extern "C++" { "std::foo"; }) which seems odd.

[grimar]

In D30500#689702, @ruiu wrote:

Are you sure this is correct? I was thinking that this is about quoted strings. This allows something like extern "C++" { std::foo; } (as opposed to extern "C++" { "std::foo"; }) which seems odd.

I believe its fine.
If I have symbol _ZSt3qux which is std::qux. Lets see what BFD do.

Next script:

{ global: extern "C++" { "std::q*"; };  local: *; };

Will leave it local,
11: 000000000000014e 0 NOTYPE LOCAL DEFAULT 4 _ZSt3qux

because wildcard in quotes means exact match. And removing quotes makes symbol global as expected:

{ global: extern "C++" { std::q*; };  local: *; };

17: 0000000000000176 0 NOTYPE GLOBAL DEFAULT 4 _ZSt3qux

Your sample was about

{ global: extern "C++" { "std::qux"; };  local: *; };

vs

{ global: extern "C++" { std::qux; };  local: *; };

Both are accepted by BFD/gold and symbol is GLOBAL. That is expected behavior I believe,
see nothing odd here.

[ruiu]

ELF/LinkerScript.cpp

1965–1967

Handling only "local:" is not good. You have the same issue with "global:". You want to change this to bool consumeLabel(StringRef) and use it as consumeLabel("local") or consumeLabel("global"). It also needs comment that this is the only part that makes the grammar LL(2).

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

1965–1967

Ok. I think it I need peakLabel too, to be able handle code like:
(line 2015).

if (peek() == "}" || Error || isNextLocal())
 break;

[emaste]

extern "C++" { std::foo; } (as opposed to extern "C++" { "std::foo"; })

Oops, my fault. I added quotes while investigating the issue and accidentally pasted the quoted version in the bug report. The script actually has:

GLIBCXX_3.4 {
    extern "C++" {
...
        std::set_new_handler*;
        std::set_terminate*;
        std::set_unexpected*;
        std::type_info::__*;
    }
}

[emaste]

With this change, linking libcxxrt in FreeBSD succeeds.

(I have not yet been able to test the result because lld is now segfaulting while linking a different component later in the build; I will submit a reproducer .tar in due course.)

[ruiu]

ELF/LinkerScript.cpp

1940–1946

I think you can do that without defining peekLabel. You should remove the first two lines from readLocals().

[grimar]

ELF/LinkerScript.cpp

1940–1946

This place is not a problem to avoid use of peekLabel. But
ScriptParser::readSymbols() need it anyways I believe:

if (peek() == "}" || Error || peekLabel("local:"))
  break;

We have to know when to get out from readSymbols, one of conditions is when we meet "local"

[ruiu]

ELF/LinkerScript.cpp

1940–1946

Do you mean it is impossible? If not, please try to edit other functions.

[grimar]

ELF/LinkerScript.cpp

1940–1946

Almost nothing is impossible usually.
I'll try tomorrow though don`t think I understand why it is ok to have peek()/consume() and not ok to have peekLable + consumeLable. Isn't that consistent ?

[ruiu]

ELF/LinkerScript.cpp

1940–1946

Because I don't like the LL(2) part of the grammar.

[grimar]

• Addressed review comments.

[ruiu]

Overall this seems much more complicated than the original code. Can you simplify?

[grimar]

• Addressed review comment.

[ruiu]

ELF/LinkerScript.cpp

1945

: is not a part of a label. It's a punctuation after a label. So please remove it.

2004–2009

Do you need this error check?

ELF/ScriptLexer.cpp

261

This seems complicated. You want to skip either Tok or Tok:. In code, it's something like this.

if (consume(Tok))
  expect(":");
else
  expect(Tok + ":");

269–272

Please do not introduce a new utility function. If you want to skip two tokens, call next() twice.

[grimar]

• Addressed review comment.

ELF/LinkerScript.cpp

1945

Done.

2004–2009

Otherwise we would accept scripts like:

{
global:
...
local:
...
local:
...
local:
...
}

Both bfd and gold does not accept this, I think we also should not.

Code would be really simpler if we had peekLabel() I believe. Still not understand why we can't have one. consumeLabel can me implemented via peekLabel() + next(), so at fact we would have single method relying on LL(2) in final anyways.

ELF/ScriptLexer.cpp

261

No, that is not like this. I can't consume Tok and expect(":") for example because Tok may be a "local" symbol name, and not a label. I can't expect anything in this method actually.

expect(Tok + ":"); sure simplifies things, but requires using Twine argument (what involves std::string creation for each consume call, hope that is fine).

269–272

OK.

[ruiu]

ELF/LinkerScript.cpp

2004–2009

What's wrong with that? I think we should accept that because that makes sense. Overall this part of code should be simpler than this. Let me try.

[grimar]

D30722 landed instead.

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();
+  std::vector<SymbolVersion> readSymbols(bool Locals);
   void readLocals();
 
   ScriptConfiguration &Opt = *ScriptConfig;
   bool IsUnderSysroot;
 };
 
 void ScriptParser::readDynamicList() {
   expect("{");
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: *; };".
 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())
+  if (consumeLabel("local")) {
+    readLocals();
+  } else {
+    // "global:" is default, so if there's no label, we assume global symbols.
+    consumeLabel("global");
+    for (SymbolVersion V : readSymbols(false))
       Config->VersionScriptGlobals.push_back(V);
   }
-  readLocals();
+
   expect("}");
   expect(";");
 }
 
 void ScriptParser::readLocals() {
-  if (!consume("local"))
-    return;
-  expect(":");
-  std::vector<SymbolVersion> Locals = readSymbols();
+  std::vector<SymbolVersion> Locals = readSymbols(true);
   for (SymbolVersion V : Locals) {
     if (V.Name == "*") {
       Config->DefaultSymbolVersion = VER_NDX_LOCAL;
       continue;
     }
     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();
-  }
+  if (consumeLabel("local")) {
     readLocals();
+  } else {
+    // "global:" is default, so if there's no label, we assume global symbols.
+    consumeLabel("global");
+    Config->VersionDefinitions.back().Globals = readSymbols(false);
+  }
   expect("}");
 
   // 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() {
+// Reads a list of symbols for a versions script.
+std::vector<SymbolVersion> ScriptParser::readSymbols(bool Locals) {
   std::vector<SymbolVersion> Ret;
   for (;;) {
     if (consume("extern")) {
       for (SymbolVersion V : readVersionExtern())
         Ret.push_back(V);
       continue;
     }
 
-    if (peek() == "}" || (peek() == "local" && peek(1) == ":") || Error)
+    if (peek() == "}" || Error)
       break;
+
+    if (consumeLabel("local")) {
+      if (Locals)
+        setError("nested local label");
+      readLocals();
+      return Ret;
+    }
+
     StringRef Tok = next();
     Ret.push_back({unquote(Tok), false, hasWildcard(Tok)});
     expect(";");
   }
   return Ret;
 }
 
 // Reads an "extern C++" directive, e.g.,

ELF/ScriptLexer.h

public:
 
   void setError(const Twine &Msg);
   void tokenize(MemoryBufferRef MB);
   static StringRef skipSpace(StringRef S);
   bool atEOF();
   StringRef next();
   StringRef peek(unsigned N = 0);
   void skip();
-  bool consume(StringRef Tok);
+  bool consume(const Twine& Tok);
   void expect(StringRef Expect);
   std::string getCurrentLocation();
 
+  // This is the only method that use LL(2) grammar.
+  // Required to parse labels that may consist of
+  // one or two tokens, ex: "local :" vs "local:".
+  bool consumeLabel(StringRef Tok);
+
   std::vector<MemoryBufferRef> MBs;
   std::vector<StringRef> Tokens;
   bool InExpr = false;
   size_t Pos = 0;
   bool Error = false;
 
 private:
   void maybeSplitExpr();

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()) {
for (unsigned I = 0; I <= N; ++I) {
     Tok = next();
     if (Error)
       return "";
   }
   Pos = Pos - N - 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;
 }
 
+bool ScriptLexer::consumeLabel(StringRef Tok) {
+  if (peek() == Tok && peek(1) == ":") {
+    skip();
+    skip();
+    return true;
+  }
+  return consume(Twine(Tok) + ":");
+}
+
 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");
 }

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:

test/ELF/version-script.s

 # ERR1: anonymous version definition is used in combination with other version definitions
 
 # RUN: echo "{ global: foo1; local: *; };" > %t5.script
 # RUN: echo "VERSION_2.0 { global: foo3; local: *; };" >> %t5.script
 # RUN: not ld.lld --version-script %t5.script -shared %t.o %t2.so -o %t5.so 2>&1 | \
 # RUN:   FileCheck -check-prefix=ERR2 %s
 # ERR2: EOF expected, but got VERSION_2.0
 
+# RUN: echo "VERSION_1.0 { global: foo1; local: local: *; *; };" > %t7.script
+# RUN: not ld.lld --version-script %t7.script -shared %t.o %t2.so -o %t6.so 2>&1 | \
+# RUN:   FileCheck -check-prefix=ERR3 %s
+# ERR3: nested local label
+
 # RUN: echo "VERSION_1.0 { global: foo1; local: *; };" > %t6.script
 # RUN: echo "VERSION_2.0 { global: foo1; local: *; };" >> %t6.script
 # RUN: ld.lld --version-script %t6.script -shared %t.o %t2.so -o %t6.so 2>&1 | \
 # RUN:   FileCheck -check-prefix=WARN2 %s
 # WARN2: duplicate symbol 'foo1' in version script
 
 # RUN: echo "{ foo1; foo2; };" > %t.list
 # RUN: ld.lld --version-script %t.script --dynamic-list %t.list %t.o %t2.so -o %t2