ExportTrie nodes need to be visisted in order.

The export trie was being emitted in the order the nodes were
added to the vector, but instead needs to be visited in the order
that the nodes are traversed.  This matches the behaviour of ld64.

llvm-svn: 277869

2 files changed, 92 insertions, 2 deletions

diff --git a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
index ed58d92a80b..a0609a5e926 100644
--- a/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachONormalizedFileBinaryWriter.cpp
@@ -103,6 +103,9 @@ struct TrieNode {
 
   void addSymbol(const Export &entry, BumpPtrAllocator &allocator,
                  std::vector<TrieNode *> &allNodes);
+
+  void addOrderedNodes(const Export &entry,
+                       std::vector<TrieNode *> &allNodes);
   bool updateOffset(uint32_t &offset);
   void appendToByteBuffer(ByteBuffer &out);
 
@@ -115,6 +118,7 @@ private:
   StringRef                 _importedName;
   uint32_t                  _trieOffset;
   bool                      _hasExportInfo;
+  bool                      _ordered = false;
 };
 
 /// Utility class for writing a mach-o binary file given an in-memory
@@ -1289,6 +1293,24 @@ void TrieNode::addSymbol(const Export& entry,
   allNodes.push_back(newNode);
 }
 
+void TrieNode::addOrderedNodes(const Export& entry,
+                               std::vector<TrieNode*> &orderedNodes) {
+  if (!_ordered) {
+    orderedNodes.push_back(this);
+    _ordered = true;
+  }
+
+  StringRef partialStr = entry.name.drop_front(_cummulativeString.size());
+  for (TrieEdge &edge : _children) {
+    StringRef edgeStr = edge._subString;
+    if (partialStr.startswith(edgeStr)) {
+      // Already have matching edge, go down that path.
+      edge._child->addOrderedNodes(entry, orderedNodes);
+      return;
+    }
+  }
+}
+
 bool TrieNode::updateOffset(uint32_t& offset) {
   uint32_t nodeSize = 1; // Length when no export info
   if (_hasExportInfo) {
@@ -1394,20 +1416,26 @@ void MachOFileLayout::buildExportTrie() {
     rootNode->addSymbol(entry, allocator, allNodes);
   }
 
+  std::vector<TrieNode*> orderedNodes;
+  orderedNodes.reserve(allNodes.size());
+
+  for (const Export& entry : _file.exportInfo)
+    rootNode->addOrderedNodes(entry, orderedNodes);
+
   // Assign each node in the vector an offset in the trie stream, iterating
   // until all uleb128 sizes have stabilized.
   bool more;
   do {
     uint32_t offset = 0;
     more = false;
-    for (TrieNode* node : allNodes) {
+    for (TrieNode* node : orderedNodes) {
       if (node->updateOffset(offset))
         more = true;
     }
   } while (more);
 
   // Serialize trie to ByteBuffer.
-  for (TrieNode* node : allNodes) {
+  for (TrieNode* node : orderedNodes) {
     node->appendToByteBuffer(_exportTrie);
   }
   _exportTrie.align(_is64 ? 8 : 4);
diff --git a/lld/test/mach-o/export-trie-order.yaml b/lld/test/mach-o/export-trie-order.yaml
new file mode 100644
index 00000000000..a11c998bdb0
--- /dev/null
+++ b/lld/test/mach-o/export-trie-order.yaml
@@ -0,0 +1,62 @@
+# RUN: lld -flavor darwin -arch i386 %s %p/Inputs/hello-world-x86.yaml -o %t
+# RUN: llvm-objdump -exports-trie %t | FileCheck %s
+#
+# Test that the export trie is emitted in order.
+#
+
+--- !mach-o
+arch:            x86
+file-type:       MH_OBJECT
+flags:           [ MH_SUBSECTIONS_VIA_SYMBOLS ]
+sections:
+  - segment:         __TEXT
+    section:         __text
+    type:            S_REGULAR
+    attributes:      [ S_ATTR_PURE_INSTRUCTIONS, S_ATTR_SOME_INSTRUCTIONS ]
+    address:         0x0000000000000000
+    content:         [ 0x55, 0x89, 0xE5, 0x83, 0xEC, 0x08, 0xE8, 0x00,
+                       0x00, 0x00, 0x00, 0x58, 0x8D, 0x80, 0x16, 0x00,
+                       0x00, 0x00, 0x89, 0x04, 0x24, 0xE8, 0xE6, 0xFF,
+                       0xFF, 0xFF, 0x31, 0xC0, 0x83, 0xC4, 0x08, 0x5D,
+                       0xC3 ]
+    relocations:
+      - offset:          0x00000016
+        type:            GENERIC_RELOC_VANILLA
+        length:          2
+        pc-rel:          true
+        extern:          true
+        symbol:          1
+      - offset:          0x0000000E
+        scattered:       true
+        type:            GENERIC_RELOC_LOCAL_SECTDIFF
+        length:          2
+        pc-rel:          false
+        value:           0x00000021
+      - offset:          0x00000000
+        scattered:       true
+        type:            GENERIC_RELOC_PAIR
+        length:          2
+        pc-rel:          false
+        value:           0x0000000B
+  - segment:         __TEXT
+    section:         __cstring
+    type:            S_CSTRING_LITERALS
+    attributes:      [  ]
+    address:         0x0000000000000021
+    content:         [ 0x68, 0x65, 0x6C, 0x6C, 0x6F, 0x0A, 0x00 ]
+global-symbols:
+  - name:            _main
+    type:            N_SECT
+    scope:           [ N_EXT ]
+    sect:            1
+    value:           0x0000000000000000
+undefined-symbols:
+  - name:            _printf
+    type:            N_UNDF
+    scope:           [ N_EXT ]
+    value:           0x0000000000000000
+...
+
+# CHECK: Exports trie:
+# CHECK-NEXT: __mh_execute_header
+# CHECK-NEXT: _main