[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

1966–1968

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

1966–1968

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

1943–1944

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

[grimar]

ELF/LinkerScript.cpp

1943–1944

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

1943–1944

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

[grimar]

ELF/LinkerScript.cpp

1943–1944

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

1943–1944

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

1949

: 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

252

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 + ":");

260–263

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

1949

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

252

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).

260–263

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

unsigned ScriptParser::readPhdrType() {
   }
   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(":");
+  if (!peekLabel("local:")) {
+    consumeLabel("global:");
     for (SymbolVersion V : readSymbols())
       Config->VersionScriptGlobals.push_back(V);
   }
   readLocals();
   expect("}");
   expect(";");
 }
 
 void ScriptParser::readLocals() {
-  if (!consume("local"))
+  if (!consumeLabel("local:"))
     return;
-  expect(":");
   std::vector<SymbolVersion> Locals = readSymbols();
   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(":");
+  if (!peekLabel("local:")) {
+    consumeLabel("global:");
     Config->VersionDefinitions.back().Globals = readSymbols();
   }
   readLocals();
   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
std::vector<SymbolVersion> ScriptParser::readSymbols() {
   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 || peekLabel("local:"))
       break;
     StringRef Tok = next();
     Ret.push_back({unquote(Tok), false, hasWildcard(Tok)});
     expect(";");
   }
   return Ret;
 }
 
 // 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("{");

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);
-  void skip();
+  void skip(unsigned N = 1);
   bool consume(StringRef Tok);
   void expect(StringRef Expect);
   std::string getCurrentLocation();
 
+  // These are the only methods that use LL(2) grammar.
+  // Required to parse labels that may consist of
+  // one or two tokens, ex: "local :" vs "local:".
+  bool peekLabel(StringRef Tok);
+  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()) {

 bool ScriptLexer::consume(StringRef Tok) {
   if (peek() == Tok) {
     skip();
     return true;
   }
   return false;
 }
 
-void ScriptLexer::skip() { (void)next(); }
+bool ScriptLexer::consumeLabel(StringRef Tok) {
+  if (!peekLabel(Tok))
+    return false;
+  skip(peek() == Tok ? 1 : 2);
+  return true;
+}
+
+bool ScriptLexer::peekLabel(StringRef Tok) {
+  if (peek() == Tok)
+    return true;
+  return peek() == Tok.drop_back(1) && peek(1) == Tok.take_back(1);
+}
+
+void ScriptLexer::skip(unsigned N) {
+  while (N--)
+    (void)next();
+}
 
 void ScriptLexer::expect(StringRef Expect) {
   if (Error)
     return;
   StringRef Tok = next();
   if (Tok != Expect)
     setError(Expect + " expected, but got " + Tok);
 }

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: