[ELF] Support multiple SORT in an input section description

[MaskRay]

Summary

The second SORT in *(SORT(...) SORT(...)) is incorrectly parsed as a file pattern.
Fix the bug by stopping at SORT* in readInputSectionsList.

[psmith]

Looks OK to me. Will be best to see if George has any comments about how to do the parsing.

lld/ELF/ScriptParser.cpp

651

May be worth adding a SORT example here, as peek2() may look a bit strange without one.

[MaskRay]

Add a comment and simplify

[grimar]

lld/ELF/ScriptParser.cpp

663

I'd reformat the comment to have the sample on a single line, it is hard to read currently.

// peek2() is used to detect "EXCLUDE_FILE(" or "SORT("
// (e.g. *(.foo SORT(.bar)) ) where we should break the loop.

Also, our current grammar is LL(2), but we tried to use LL(1) where was possible.
See (a bit outdated) comment in ScriptLexer.cpp.

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:".

Given above I'd go with explicit version:

while (!errorCount() && peek() != ")" && peek() != "SORT" &&
       peek() != "EXCLUDE_FILE")

Note:

1. That "(" is a valid file name. Your version goes into infinite loop with the following input (added the FOO ( to script from test case):

# RUN: echo "SECTIONS { .abc : { *(SORT(.foo.*) .a* .a* SORT(.bar.*) FOO ( .b*) } }" > %t1.script

2. Perhaps, the comment for readInputSectionsList should be updated.

lld/test/ELF/linkerscript/sort2.s

8–10

This is what is fixed by D91127, right?

[MaskRay]

Fix infinite loop

lld/ELF/ScriptParser.cpp

663

Thanks for spotting the infinite loop problem! I added peekSortKind and changed back to LL(1).

lld/test/ELF/linkerscript/sort2.s

8–10

Yes.

[grimar]

LGTM!

lld/ELF/ScriptParser.cpp

private:
   std::pair<uint64_t, uint64_t> readInputSectionFlags();
   InputSectionDescription *readInputSectionDescription(StringRef tok);
   StringMatcher readFilePatterns();
   std::vector<SectionPattern> readInputSectionsList();
   InputSectionDescription *readInputSectionRules(StringRef filePattern,
                                                  uint64_t withFlags,
                                                  uint64_t withoutFlags);
   unsigned readPhdrType();
+  SortSectionPolicy peekSortKind();
   SortSectionPolicy readSortKind();
   SymbolAssignment *readProvideHidden(bool provide, bool hidden);
   SymbolAssignment *readAssignment(StringRef tok);
   void readSort();
   Expr readAssert();
   Expr readConstant();
   Expr getPageSize();
 

 StringMatcher ScriptParser::readFilePatterns() {
   StringMatcher Matcher;
 
   while (!errorCount() && !consume(")"))
     Matcher.addPattern(SingleStringMatcher(next()));
   return Matcher;
 }
 
+SortSectionPolicy ScriptParser::peekSortKind() {
+  return StringSwitch<SortSectionPolicy>(peek())
+      .Cases("SORT", "SORT_BY_NAME", SortSectionPolicy::Name)
+      .Case("SORT_BY_ALIGNMENT", SortSectionPolicy::Alignment)
+      .Case("SORT_BY_INIT_PRIORITY", SortSectionPolicy::Priority)
+      .Case("SORT_NONE", SortSectionPolicy::None)
+      .Default(SortSectionPolicy::Default);
+}
+
 SortSectionPolicy ScriptParser::readSortKind() {
-  if (consume("SORT") || consume("SORT_BY_NAME"))
-    return SortSectionPolicy::Name;
-  if (consume("SORT_BY_ALIGNMENT"))
-    return SortSectionPolicy::Alignment;
-  if (consume("SORT_BY_INIT_PRIORITY"))
-    return SortSectionPolicy::Priority;
-  if (consume("SORT_NONE"))
-    return SortSectionPolicy::None;
-  return SortSectionPolicy::Default;
+  SortSectionPolicy ret = peekSortKind();
+  if (ret != SortSectionPolicy::Default)
+    skip();
+  return ret;
 }
 
 // Reads SECTIONS command contents in the following form:
 //
 // <contents> ::= <elem>*
 // <elem>     ::= <exclude>? <glob-pattern>
 // <exclude>  ::= "EXCLUDE_FILE" "(" <glob-pattern>+ ")"
 //
 // For example,
 //
 // *(.foo EXCLUDE_FILE (a.o) .bar EXCLUDE_FILE (b.o) .baz)
 //
 // is parsed as ".foo", ".bar" with "a.o", and ".baz" with "b.o".
 // The semantics of that is section .foo in any file, section .bar in
 // any file but a.o, and section .baz in any file but b.o.
 std::vector<SectionPattern> ScriptParser::readInputSectionsList() {
   std::vector<SectionPattern> ret;
   while (!errorCount() && peek() != ")") {
     StringMatcher excludeFilePat;
     if (consume("EXCLUDE_FILE")) {
       expect("(");
       excludeFilePat = readFilePatterns();
     }
 
     StringMatcher SectionMatcher;
-    while (!errorCount() && peek() != ")" && peek() != "EXCLUDE_FILE")
+    // Break if the next token is ), EXCLUDE_FILE, or SORT*.
+    while (!errorCount() && peek() != ")" && peek() != "EXCLUDE_FILE" &&
+           peekSortKind() == SortSectionPolicy::Default)
       SectionMatcher.addPattern(unquote(next()));
 
     if (!SectionMatcher.empty())
       ret.push_back({std::move(excludeFilePat), std::move(SectionMatcher)});
+    else if (excludeFilePat.empty())
+      break;
     else
       setError("section pattern is expected");
   }
   return ret;
 }
 
 // Reads contents of "SECTIONS" directive. That directive contains a
 // list of glob patterns for input sections. The grammar is as follows.

lld/test/ELF/linkerscript/sort2.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %tfile1.o
 
-# RUN: echo "SECTIONS { .abc : { *(SORT(.foo.*) .bar.*) } }" > %t1.script
+# RUN: echo "SECTIONS { .abc : { *(SORT(.foo.*) .a* .a* SORT(.bar.*) .b*) } }" > %t1.script
 # RUN: ld.lld -o %t1 --script %t1.script %tfile1.o
-# RUN: llvm-objdump -s %t1 | FileCheck %s
+# RUN: llvm-readelf -x .abc %t1 | FileCheck %s
 
-# CHECK:  Contents of section .abc:
-# CHECK:   01000000 00000000 02000000 00000000
-# CHECK:   03000000 00000000 04000000 00000000
-# CHECK:   06000000 00000000 05000000 00000000
+## FIXME Some input sections are duplicated in .abc and their second occurrences are zeros.
+# CHECK:      Hex dump of section '.abc'
+# CHECK-NEXT: 0x00000000 01020306 05040000 00070908 0b0c0a
 
 # RUN: echo "SECTIONS { \
-# RUN:   .abc : { *(SORT(.foo.* EXCLUDE_FILE (*file1.o) .bar.*) .bar.*) } \
+# RUN:   .abc : { *(SORT(.foo.* EXCLUDE_FILE (*file1.o) .bar.*) .a* SORT(.bar.*) .b*) } \
 # RUN:  }" > %t2.script
 # RUN: ld.lld -o %t2 --script %t2.script %tfile1.o
-# RUN: llvm-objdump -s %t2 | FileCheck %s
+# RUN: llvm-readelf -x .abc %t2 | FileCheck %s
 
 .text
 .globl _start
 _start:
 
-.section .foo.2,"a"
- .quad 2
-
-.section .foo.3,"a"
- .quad 3
-
-.section .foo.1,"a"
- .quad 1
-
-.section .bar.4,"a"
- .quad 4
-
-.section .bar.6,"a"
- .quad 6
-
-.section .bar.5,"a"
- .quad 5
+.section .foo.2,"a"; .byte 2
+.section .foo.3,"a"; .byte 3
+.section .foo.1,"a"; .byte 1
+
+.section .a6,"a"; .byte 6
+.section .a5,"a"; .byte 5
+.section .a4,"a"; .byte 4
+
+.section .bar.7,"a"; .byte 7
+.section .bar.9,"a"; .byte 9
+.section .bar.8,"a"; .byte 8
+
+.section .b11,"a"; .byte 11
+.section .b12,"a"; .byte 12
+.section .b10,"a"; .byte 10

lld/test/ELF/linkerscript/wildcards.s

 # REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %t/asm -o %t.o
 
 ## Default case: abc and abx included in text.
 # RUN: echo "SECTIONS { \
 # RUN:      .text : { *(.abc .abx) } }" > %t.script
-# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: ld.lld -o %t.out --script %t.script %t.o
 # RUN: llvm-objdump --section-headers %t.out | \
 # RUN:   FileCheck -check-prefix=SEC-DEFAULT %s
 # SEC-DEFAULT:      Sections:
 # SEC-DEFAULT-NEXT: Idx Name          Size
 # SEC-DEFAULT-NEXT:   0               00000000
 # SEC-DEFAULT-NEXT:   1 .text         00000008
 # SEC-DEFAULT-NEXT:   2 .abcd         00000004
 # SEC-DEFAULT-NEXT:   3 .ad           00000004
 # SEC-DEFAULT-NEXT:   4 .ag           00000004
 # SEC-DEFAULT-NEXT:   5 .comment      00000008 {{[0-9a-f]*}}
 # SEC-DEFAULT-NEXT:   6 .symtab       00000030
 # SEC-DEFAULT-NEXT:   7 .shstrtab     00000038
 # SEC-DEFAULT-NEXT:   8 .strtab       00000008
 
 ## Now replace the symbol with '?' and check that results are the same.
 # RUN: echo "SECTIONS { \
 # RUN:      .text : { *(.abc .ab?) } }" > %t.script
-# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: ld.lld -o %t.out --script %t.script %t.o
 # RUN: llvm-objdump --section-headers %t.out | \
 # RUN:   FileCheck -check-prefix=SEC-DEFAULT %s
 
 ## Now see how replacing '?' with '*' will consume whole abcd.
 # RUN: echo "SECTIONS { \
 # RUN:      .text : { *(.abc .ab*) } }" > %t.script
-# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: ld.lld -o %t.out --script %t.script %t.o
 # RUN: llvm-objdump --section-headers %t.out | \
 # RUN:   FileCheck -check-prefix=SEC-ALL %s
 # SEC-ALL:      Sections:
 # SEC-ALL-NEXT: Idx Name          Size
 # SEC-ALL-NEXT:   0               00000000
 # SEC-ALL-NEXT:   1 .text         0000000c
 # SEC-ALL-NEXT:   2 .ad           00000004
 # SEC-ALL-NEXT:   3 .ag           00000004
 # SEC-ALL-NEXT:   4 .comment      00000008
 # SEC-ALL-NEXT:   5 .symtab       00000030
 # SEC-ALL-NEXT:   6 .shstrtab     00000032
 # SEC-ALL-NEXT:   7 .strtab       00000008
 
 ## All sections started with .a are merged.
 # RUN: echo "SECTIONS { \
 # RUN:      .text : { *(.a*) } }" > %t.script
-# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: ld.lld -o %t.out --script %t.script %t.o
 # RUN: llvm-objdump --section-headers %t.out | \
 # RUN:   FileCheck -check-prefix=SEC-NO %s
 # SEC-NO: Sections:
 # SEC-NO-NEXT: Idx Name          Size
 # SEC-NO-NEXT:   0               00000000
 # SEC-NO-NEXT:   1 .text         00000014
 # SEC-NO-NEXT:   2 .comment      00000008
 # SEC-NO-NEXT:   3 .symtab       00000030
 # SEC-NO-NEXT:   4 .shstrtab     0000002a
 # SEC-NO-NEXT:   5 .strtab       00000008
 
+#--- asm
 .text
 .section .abc,"ax",@progbits
 .long 0
 
 .text
 .section .abx,"ax",@progbits
 .long 0
 
 .text
 .section .abcd,"ax",@progbits
 .long 0
 
 .text
 .section .ad,"ax",@progbits
 .long 0
 
 .text
 .section .ag,"ax",@progbits
 .long 0
 
 
 .globl _start
 _start:
+
+#--- lparen.lds
+## ( is recognized as a section name pattern. Note, ( is rejected by GNU ld.
+# RUN: ld.lld -T %t/lparen.lds %t.o -o %t.out
+# RUN: llvm-objdump --section-headers %t.out | FileCheck --check-prefix=SEC-NO %s
+SECTIONS {
+ .text : { *(.a* ( ) }
+}