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

142

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

752

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

752

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

[ruiu]

• Rebased.

[ruiu]

ELF/LinkerScript.cpp

752

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 PhdrsCommand {
   StringRef Name;
   unsigned Type;
   bool HasFilehdr;

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(
     std::vector<OutputSectionBase<ELFT> *> *Out,
     OutputSectionFactory<ELFT> &Factory) {
   OutputSections = Out;
 
   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, *Out, 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);
   void readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller();
   std::vector<StringRef> readOutputSectionPhdrs();
   std::unique_ptr<InputSectionDescription> readInputSectionDescription();
   void readInputFilePattern(InputSectionDescription *InCmd, bool Keep);
   void readInputSectionRules(InputSectionDescription *InCmd, bool Keep);
   unsigned readPhdrType();
+  SortKind readSortKind();
   void readProvide(bool Hidden);
   void readAlign(OutputSectionCommand *Cmd);
   void readSort();
 
   Expr readExpr();
   Expr readExpr1(Expr Lhs, int MinPrec);
   Expr readPrimary();
   Expr readTernary(Expr Cond);
void ScriptParser::readInputFilePattern(InputSectionDescription *InCmd,
                                         bool Keep) {
   while (!Error && !skip(")")) {
     if (Keep)
       Opt.KeptSections.push_back(peek());
     InCmd->SectionPatterns.push_back(next());
   }
 }
 
+SortKind ScriptParser::readSortKind() {
+  if (skip("SORT") || skip("SORT_BY_NAME"))
+    return SortByName;
+  if (skip("SORT_BY_ALIGNMENT"))
+    return SortByAlignment;
+  return SortNone;
+}
+
 void ScriptParser::readInputSectionRules(InputSectionDescription *InCmd,
                                          bool Keep) {
   InCmd->FilePattern = next();
   expect("(");
 
+  // Read EXCLUDE_FILE().
   if (skip("EXCLUDE_FILE")) {
     expect("(");
     while (!Error && !skip(")"))
       InCmd->ExcludedFiles.push_back(next());
   }
 
-  if (skip("SORT") || skip("SORT_BY_NAME")) {
-    expect("(");
-    if (skip("SORT_BY_ALIGNMENT")) {
-      InCmd->Sort = SortKind::NameAlign;
-      expect("(");
-      readInputFilePattern(InCmd, Keep);
-      expect(")");
-    } else {
-      InCmd->Sort = SortKind::Name;
-      readInputFilePattern(InCmd, Keep);
-    }
-    expect(")");
-    return;
-  }
-
-  if (skip("SORT_BY_ALIGNMENT")) {
+  // Read SORT().
+  if (SortKind K1 = readSortKind()) {
+    InCmd->SortOuter = K1;
     expect("(");
-    if (skip("SORT") || skip("SORT_BY_NAME")) {
-      InCmd->Sort = SortKind::AlignName;
+    if (SortKind K2 = readSortKind()) {
+      InCmd->SortInner = K2;
       expect("(");
       readInputFilePattern(InCmd, Keep);
       expect(")");
     } else {
-      InCmd->Sort = SortKind::Align;
       readInputFilePattern(InCmd, Keep);
     }
     expect(")");
     return;
   }
 
   readInputFilePattern(InCmd, Keep);
 }