Reland "[llvm-readobj][MachO] Add option to sort the symbol table before dumping (MachO only, for now)."

    https://reviews.llvm.org/D116787

This reverts commit 33b3c86afab06ad61d46456c85c0b565cfff8287.

New change: fixed build failures:
 - in stabs-sorted:restore the the ERR-KEY statements, which were accidentally deleted during refactoring
 - in ObjDumper.h/MachODumper.cpp: refactor so that current dumpers which didn't provide an impl that accept a SymCom still works

5 files changed, 158 insertions, 9 deletions

diff --git a/llvm/tools/llvm-readobj/MachODumper.cpp b/llvm/tools/llvm-readobj/MachODumper.cpp
index 599b035..d875e3b 100644
--- a/llvm/tools/llvm-readobj/MachODumper.cpp
+++ b/llvm/tools/llvm-readobj/MachODumper.cpp
@@ -13,6 +13,7 @@
 #include "ObjDumper.h"
 #include "StackMapPrinter.h"
 #include "llvm-readobj.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Object/MachO.h"
@@ -39,6 +40,11 @@ public:
 
   void printNeededLibraries() override;
 
+  bool canCompareSymbols() const override { return true; }
+  bool compareSymbolsByName(object::SymbolRef LHS,
+                            object::SymbolRef RHS) const override;
+  bool compareSymbolsByType(object::SymbolRef LHS,
+                            object::SymbolRef RHS) const override;
   // MachO-specific.
   void printMachODataInCode() override;
   void printMachOVersionMin() override;
@@ -51,10 +57,14 @@ private:
   template<class MachHeader>
   void printFileHeaders(const MachHeader &Header);
 
-  StringRef getSymbolName(const SymbolRef &Symbol);
+  StringRef getSymbolName(const SymbolRef &Symbol) const;
+  uint8_t getSymbolType(const SymbolRef &Symbol) const;
 
   void printSymbols() override;
+  void printSymbols(Optional<SymbolComparator> SymComp) override;
   void printDynamicSymbols() override;
+  void printDynamicSymbols(Optional<SymbolComparator> SymComp) override;
+  void printSymbol(const SymbolRef &Symbol, ScopedPrinter &W);
   void printSymbol(const SymbolRef &Symbol);
 
   void printRelocation(const RelocationRef &Reloc);
@@ -602,7 +612,7 @@ void MachODumper::printRelocation(const MachOObjectFile *Obj,
   }
 }
 
-StringRef MachODumper::getSymbolName(const SymbolRef &Symbol) {
+StringRef MachODumper::getSymbolName(const SymbolRef &Symbol) const {
   Expected<StringRef> SymbolNameOrErr = Symbol.getName();
   if (!SymbolNameOrErr) {
     reportError(SymbolNameOrErr.takeError(), Obj->getFileName());
@@ -610,19 +620,48 @@ StringRef MachODumper::getSymbolName(const SymbolRef &Symbol) {
   return *SymbolNameOrErr;
 }
 
-void MachODumper::printSymbols() {
-  ListScope Group(W, "Symbols");
+uint8_t MachODumper::getSymbolType(const SymbolRef &Symbol) const {
+  return Obj->getSymbol64TableEntry(Symbol.getRawDataRefImpl()).n_type;
+}
+
+bool MachODumper::compareSymbolsByName(SymbolRef LHS, SymbolRef RHS) const {
+  return getSymbolName(LHS).str().compare(getSymbolName(RHS).str()) < 0;
+}
+
+bool MachODumper::compareSymbolsByType(SymbolRef LHS, SymbolRef RHS) const {
+  return getSymbolType(LHS) < getSymbolType(RHS);
+}
+
+void MachODumper::printSymbols() { printSymbols(None); }
 
-  for (const SymbolRef &Symbol : Obj->symbols()) {
-    printSymbol(Symbol);
+void MachODumper::printSymbols(Optional<SymbolComparator> SymComp) {
+  ListScope Group(W, "Symbols");
+  if (SymComp) {
+    auto SymbolRange = Obj->symbols();
+    std::vector<SymbolRef> SortedSymbols(SymbolRange.begin(),
+                                         SymbolRange.end());
+    llvm::stable_sort(SortedSymbols, *SymComp);
+    for (SymbolRef Symbol : SortedSymbols)
+      printSymbol(Symbol);
+  } else {
+    for (const SymbolRef &Symbol : Obj->symbols()) {
+      printSymbol(Symbol);
+    }
   }
 }
 
 void MachODumper::printDynamicSymbols() {
   ListScope Group(W, "DynamicSymbols");
 }
+void MachODumper::printDynamicSymbols(Optional<SymbolComparator> SymComp) {
+  ListScope Group(W, "DynamicSymbols");
+}
 
 void MachODumper::printSymbol(const SymbolRef &Symbol) {
+  printSymbol(Symbol, W);
+}
+
+void MachODumper::printSymbol(const SymbolRef &Symbol, ScopedPrinter &W) {
   StringRef SymbolName = getSymbolName(Symbol);
 
   MachOSymbol MOSymbol;
diff --git a/llvm/tools/llvm-readobj/ObjDumper.h b/llvm/tools/llvm-readobj/ObjDumper.h
index a09a243..c1edf98 100644
--- a/llvm/tools/llvm-readobj/ObjDumper.h
+++ b/llvm/tools/llvm-readobj/ObjDumper.h
@@ -12,6 +12,10 @@
 #include <memory>
 #include <system_error>
 
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Support/CommandLine.h"
@@ -25,7 +29,7 @@ class COFFImportFile;
 class ObjectFile;
 class XCOFFObjectFile;
 class ELFObjectFileBase;
-}
+} // namespace object
 namespace codeview {
 class GlobalTypeTableBuilder;
 class MergingTypeTableBuilder;
@@ -33,6 +37,33 @@ class MergingTypeTableBuilder;
 
 class ScopedPrinter;
 
+// Comparator to compare symbols.
+// Usage: the caller registers predicates (i.e., how to compare the symbols) by
+// calling addPredicate(). The order in which predicates are registered is also
+// their priority.
+class SymbolComparator {
+public:
+  using CompPredicate =
+      function_ref<bool(object::SymbolRef, object::SymbolRef)>;
+
+  // Each Obj format has a slightly different way of retrieving a symbol's info
+  // So we defer the predicate's impl to each format.
+  void addPredicate(CompPredicate Pred) { Predicates.push_back(Pred); }
+
+  bool operator()(object::SymbolRef LHS, object::SymbolRef RHS) {
+    for (CompPredicate Pred : Predicates) {
+      if (Pred(LHS, RHS))
+        return true;
+      if (Pred(RHS, LHS))
+        return false;
+    }
+    return false;
+  }
+
+private:
+  SmallVector<CompPredicate, 2> Predicates;
+};
+
 class ObjDumper {
 public:
   ObjDumper(ScopedPrinter &Writer, StringRef ObjName);
@@ -52,6 +83,17 @@ public:
     if (PrintDynamicSymbols)
       printDynamicSymbols();
   }
+  virtual void printSymbols(bool PrintSymbols, bool PrintDynamicSymbols,
+                            llvm::Optional<SymbolComparator> SymComp) {
+    if (SymComp) {
+      if (PrintSymbols)
+        printSymbols(SymComp);
+      if (PrintDynamicSymbols)
+        printDynamicSymbols(SymComp);
+    } else {
+      printSymbols(PrintSymbols, PrintDynamicSymbols);
+    }
+  }
   virtual void printProgramHeaders(bool PrintProgramHeaders,
                                    cl::boolOrDefault PrintSectionMapping) {
     if (PrintProgramHeaders)
@@ -62,6 +104,17 @@ public:
 
   virtual void printUnwindInfo() = 0;
 
+  // Symbol comparison functions.
+  virtual bool canCompareSymbols() const { return false; }
+  virtual bool compareSymbolsByName(object::SymbolRef LHS,
+                                    object::SymbolRef RHS) const {
+    return true;
+  }
+  virtual bool compareSymbolsByType(object::SymbolRef LHS,
+                                    object::SymbolRef RHS) const {
+    return true;
+  }
+
   // Only implemented for ELF at this time.
   virtual void printDependentLibs() {}
   virtual void printDynamicRelocations() { }
@@ -133,7 +186,9 @@ protected:
 
 private:
   virtual void printSymbols() {}
+  virtual void printSymbols(llvm::Optional<SymbolComparator> Comp) {}
   virtual void printDynamicSymbols() {}
+  virtual void printDynamicSymbols(llvm::Optional<SymbolComparator> Comp) {}
   virtual void printProgramHeaders() {}
   virtual void printSectionMapping() {}
 
diff --git a/llvm/tools/llvm-readobj/Opts.td b/llvm/tools/llvm-readobj/Opts.td
index 528c7f6..4687fc7 100644
--- a/llvm/tools/llvm-readobj/Opts.td
+++ b/llvm/tools/llvm-readobj/Opts.td
@@ -37,6 +37,7 @@ def section_mapping : FF<"section-mapping", "Display the section to segment mapp
 def section_mapping_EQ_false : FF<"section-mapping=false", "Don't display the section to segment mapping">, Flags<[HelpHidden]>;
 def section_relocations : FF<"section-relocations", "Display relocations for each section shown. This option has no effect for GNU style output">;
 def section_symbols : FF<"section-symbols", "Display symbols for each section shown. This option has no effect for GNU style output">;
+defm sort_symbols : Eq<"sort-symbols", "Specify the keys to sort the symbols before displaying symtab">;
 def stack_sizes : FF<"stack-sizes", "Display contents of all stack sizes sections. This option has no effect for GNU style output">;
 def stackmap : FF<"stackmap", "Display contents of stackmap section">;
 defm string_dump : Eq<"string-dump", "Display the specified section(s) as a list of strings">, MetaVarName<"<name or index>">;
diff --git a/llvm/tools/llvm-readobj/llvm-readobj.cpp b/llvm/tools/llvm-readobj/llvm-readobj.cpp
index 543b0de..e1ebbeb 100644
--- a/llvm/tools/llvm-readobj/llvm-readobj.cpp
+++ b/llvm/tools/llvm-readobj/llvm-readobj.cpp
@@ -21,6 +21,7 @@
 #include "llvm-readobj.h"
 #include "ObjDumper.h"
 #include "WindowsResourceDumper.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
 #include "llvm/MC/TargetRegistry.h"
@@ -83,6 +84,14 @@ public:
 };
 
 enum OutputFormatTy { bsd, sysv, posix, darwin, just_symbols };
+
+enum SortSymbolKeyTy {
+  NAME = 0,
+  TYPE = 1,
+  UNKNOWN = 100,
+  // TODO: add ADDRESS, SIZE as needed.
+};
+
 } // namespace
 
 namespace opts {
@@ -113,6 +122,7 @@ static bool StringTable;
 static bool Symbols;
 static bool UnwindInfo;
 static cl::boolOrDefault SectionMapping;
+static SmallVector<SortSymbolKeyTy> SortKeys;
 
 // ELF specific options.
 static bool DynamicTable;
@@ -253,6 +263,19 @@ static void parseOptions(const opt::InputArgList &Args) {
   opts::ProgramHeaders = Args.hasArg(OPT_program_headers);
   opts::RawRelr = Args.hasArg(OPT_raw_relr);
   opts::SectionGroups = Args.hasArg(OPT_section_groups);
+  if (Arg *A = Args.getLastArg(OPT_sort_symbols_EQ)) {
+    std::string SortKeysString = A->getValue();
+    for (StringRef KeyStr : llvm::split(A->getValue(), ",")) {
+      SortSymbolKeyTy KeyType = StringSwitch<SortSymbolKeyTy>(KeyStr)
+                                    .Case("name", SortSymbolKeyTy::NAME)
+                                    .Case("type", SortSymbolKeyTy::TYPE)
+                                    .Default(SortSymbolKeyTy::UNKNOWN);
+      if (KeyType == SortSymbolKeyTy::UNKNOWN)
+        error("--sort-symbols value should be 'name' or 'type', but was '" +
+              Twine(KeyStr) + "'");
+      opts::SortKeys.push_back(KeyType);
+    }
+  }
   opts::VersionInfo = Args.hasArg(OPT_version_info);
 
   // Mach-O specific options.
@@ -334,11 +357,39 @@ static void dumpObject(ObjectFile &Obj, ScopedPrinter &Writer,
                        toString(std::move(ContentErr));
 
   ObjDumper *Dumper;
+  Optional<SymbolComparator> SymComp;
   Expected<std::unique_ptr<ObjDumper>> DumperOrErr = createDumper(Obj, Writer);
   if (!DumperOrErr)
     reportError(DumperOrErr.takeError(), FileStr);
   Dumper = (*DumperOrErr).get();
 
+  if (!opts::SortKeys.empty()) {
+    if (Dumper->canCompareSymbols()) {
+      SymComp = SymbolComparator();
+      for (SortSymbolKeyTy Key : opts::SortKeys) {
+        switch (Key) {
+        case NAME:
+          SymComp->addPredicate([Dumper](SymbolRef LHS, SymbolRef RHS) {
+            return Dumper->compareSymbolsByName(LHS, RHS);
+          });
+          break;
+        case TYPE:
+          SymComp->addPredicate([Dumper](SymbolRef LHS, SymbolRef RHS) {
+            return Dumper->compareSymbolsByType(LHS, RHS);
+          });
+          break;
+        case UNKNOWN:
+          llvm_unreachable("Unsupported sort key");
+        }
+      }
+
+    } else {
+      reportWarning(createStringError(
+                        errc::invalid_argument,
+                        "--sort-symbols is not supported yet for this format"),
+                    FileStr);
+    }
+  }
   Dumper->printFileSummary(FileStr, Obj, opts::InputFilenames, A);
 
   if (opts::FileHeaders)
@@ -374,7 +425,7 @@ static void dumpObject(ObjectFile &Obj, ScopedPrinter &Writer,
   if (opts::UnwindInfo)
     Dumper->printUnwindInfo();
   if (opts::Symbols || opts::DynamicSymbols)
-    Dumper->printSymbols(opts::Symbols, opts::DynamicSymbols);
+    Dumper->printSymbols(opts::Symbols, opts::DynamicSymbols, SymComp);
   if (!opts::StringDump.empty())
     Dumper->printSectionsAsString(Obj, opts::StringDump);
   if (!opts::HexDump.empty())
diff --git a/llvm/tools/llvm-readobj/llvm-readobj.h b/llvm/tools/llvm-readobj/llvm-readobj.h
index 0ea695d..989cd0a 100644
--- a/llvm/tools/llvm-readobj/llvm-readobj.h
+++ b/llvm/tools/llvm-readobj/llvm-readobj.h
@@ -9,10 +9,13 @@
 #ifndef LLVM_TOOLS_LLVM_READOBJ_LLVM_READOBJ_H
 #define LLVM_TOOLS_LLVM_READOBJ_LLVM_READOBJ_H
 
+#include "ObjDumper.h"
+
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
-#include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/ErrorOr.h"
 #include <string>
 
 namespace llvm {