Split InputSectionDescription::Sort into SortInner and SortOuter.

[ruiu]

Summary

The comparator function to compare input sections as instructed by
SORT command was a bit too complicated because it needed to handle
four different cases. This patch split it into two function calls.

This patch also simplifies the parser.

[ruiu]

• Rebased.

[grimar]

I like it, LGTM. Comments below.

ELF/LinkerScript.cpp

146

I found a bug, SORT_BY_ALIGNMENT should sort sections into descending order.
Committed fix as r277706.
So condition should be ">" here.

760

May be something like:

if (K1 != K2)
Cmd->SortInner = K2;

to avoid double sorting when the same rule is specified twice:
SORT_BY_NAME (SORT_BY_NAME(...))

[grimar]

ELF/LinkerScript.cpp

760

Though it seems to be useless cornercase and we probably should not really care, preferring shorter code.

[ruiu]

• Rebased.

[ruiu]

ELF/LinkerScript.cpp

760

Yup. Double-sorting is wasteful, but it's probably doesn't have to be handled as an error

[grimar]

lld/trunk/ELF/LinkerScript.cpp

149 ↗

(On Diff #66866)

btw interesting that gold has an issue here. lld and ld are compatible, but gold sorts by alignment in assending order what
is different from spec and looks like a bug.

ELF/LinkerScript.h

struct OutputSectionCommand : BaseCommand {
   Expr AddrExpr;
   Expr AlignExpr;
   std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
-enum class SortKind { None, Name, Align, NameAlign, AlignName };
+enum SortKind { SortNone, SortByName, SortByAlignment };
 
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription() : BaseCommand(InputSectionKind) {}
   static bool classof(const BaseCommand *C);
   StringRef FilePattern;
-  SortKind Sort = SortKind::None;
+  SortKind SortOuter = SortNone;
+  SortKind SortInner = SortNone;
   std::vector<StringRef> ExcludedFiles;
   std::vector<StringRef> SectionPatterns;
 };
 
 struct AssertCommand : BaseCommand {
   AssertCommand(Expr E) : BaseCommand(AssertKind), Expression(E) {}
   static bool classof(const BaseCommand *C);
   Expr Expression;

ELF/LinkerScript.cpp

static void addSection(OutputSectionFactory<ELFT> &Factory,
   OutputSectionBase<ELFT> *Sec;
   bool IsNew;
   std::tie(Sec, IsNew) = Factory.create(C, Name);
   if (IsNew)
     Out.push_back(Sec);
   Sec->addSection(C);
 }
 
-template <class ELFT> struct SectionsSorter {
-  SectionsSorter(SortKind Kind) : Kind(Kind) {}
-  bool operator()(InputSectionBase<ELFT> *A, InputSectionBase<ELFT> *B) {
-    int AlignmentCmp = A->Alignment - B->Alignment;
-    if (Kind == SortKind::Align || (Kind == SortKind::AlignName && AlignmentCmp != 0))
-      return AlignmentCmp > 0;
-
-    int NameCmp = A->getSectionName().compare(B->getSectionName());
-    if (Kind == SortKind::Name || (Kind == SortKind::NameAlign && NameCmp != 0))
-      return NameCmp < 0;
-
-    if (Kind == SortKind::NameAlign)
-      return AlignmentCmp > 0;
-    if (Kind == SortKind::AlignName)
-      return NameCmp < 0;
+template <class ELFT>
+static bool compareName(InputSectionBase<ELFT> *A, InputSectionBase<ELFT> *B) {
+  return A->getSectionName() < B->getSectionName();
+}
 
-    llvm_unreachable("unknown section sort kind in predicate");
-    return false;
-  }
-  SortKind Kind;
-};
+template <class ELFT>
+static bool compareAlignment(InputSectionBase<ELFT> *A,
+                             InputSectionBase<ELFT> *B) {
+  return A->Alignment > B->Alignment;
+}
+
+template <class ELFT>
+static std::function<bool(InputSectionBase<ELFT> *, InputSectionBase<ELFT> *)>
+getComparator(SortKind K) {
+  if (K == SortByName)
+    return compareName<ELFT>;
+  return compareAlignment<ELFT>;
 
 template <class ELFT>
 void LinkerScript<ELFT>::createSections(
     OutputSectionFactory<ELFT> &Factory) {
   for (auto &P : getSectionMap()) {
     StringRef OutputName = P.first;
     const InputSectionDescription *Cmd = P.second;
     std::vector<InputSectionBase<ELFT> *> Sections = getInputSections(Cmd);
 
     if (OutputName == "/DISCARD/") {
       for (InputSectionBase<ELFT> *S : Sections) {
         S->Live = false;
         reportDiscarded(S);
       }
       continue;
     }
 
-    if (Cmd->Sort != SortKind::None)
+    if (Cmd->SortInner)
+      std::stable_sort(Sections.begin(), Sections.end(),
+                       getComparator<ELFT>(Cmd->SortInner));
+    if (Cmd->SortOuter)
       std::stable_sort(Sections.begin(), Sections.end(),
-                       SectionsSorter<ELFT>(Cmd->Sort));
+                       getComparator<ELFT>(Cmd->SortOuter));
 
     for (InputSectionBase<ELFT> *S : Sections)
       addSection(Factory, *OutputSections, S, OutputName);
   }
 
   // Add all other input sections, which are not listed in script.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
        Symtab<ELFT>::X->getObjectFiles())
private:
   SymbolAssignment *readAssignment(StringRef Name);
   OutputSectionCommand *readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller();
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription();
   std::vector<StringRef> readInputFilePatterns();
   InputSectionDescription *readInputSectionRules();
   unsigned readPhdrType();
+  SortKind readSortKind();
   SymbolAssignment *readProvide(bool Hidden);
   Expr readAlign();
   void readSort();
   Expr readAssert();
 
   Expr readExpr();
   Expr readExpr1(Expr Lhs, int MinPrec);
   Expr readPrimary();

 
 std::vector<StringRef> ScriptParser::readInputFilePatterns() {
   std::vector<StringRef> V;
   while (!Error && !skip(")"))
     V.push_back(next());
   return V;
 }
 
+SortKind ScriptParser::readSortKind() {
+  if (skip("SORT") || skip("SORT_BY_NAME"))
+    return SortByName;
+  if (skip("SORT_BY_ALIGNMENT"))
+    return SortByAlignment;
+  return SortNone;
+}
+
 InputSectionDescription *ScriptParser::readInputSectionRules() {
   auto *Cmd = new InputSectionDescription;
   Cmd->FilePattern = next();
   expect("(");
 
+  // Read EXCLUDE_FILE().
   if (skip("EXCLUDE_FILE")) {
     expect("(");
     while (!Error && !skip(")"))
       Cmd->ExcludedFiles.push_back(next());
   }
 
-  if (skip("SORT") || skip("SORT_BY_NAME")) {
-    expect("(");
-    if (skip("SORT_BY_ALIGNMENT")) {
-      Cmd->Sort = SortKind::NameAlign;
-      expect("(");
-      Cmd->SectionPatterns = readInputFilePatterns();
-      expect(")");
-    } else {
-      Cmd->Sort = SortKind::Name;
-      Cmd->SectionPatterns = readInputFilePatterns();
-    }
-    expect(")");
-    return Cmd;
-  }
-
-  if (skip("SORT_BY_ALIGNMENT")) {
+  // Read SORT().
+  if (SortKind K1 = readSortKind()) {
+    Cmd->SortOuter = K1;
     expect("(");
-    if (skip("SORT") || skip("SORT_BY_NAME")) {
-      Cmd->Sort = SortKind::AlignName;
+    if (SortKind K2 = readSortKind()) {
+      Cmd->SortInner = K2;
       expect("(");
       Cmd->SectionPatterns = readInputFilePatterns();
       expect(")");
     } else {
-      Cmd->Sort = SortKind::Align;
       Cmd->SectionPatterns = readInputFilePatterns();
     }
     expect(")");
     return Cmd;
   }
 
   Cmd->SectionPatterns = readInputFilePatterns();
   return Cmd;