[C++] Don't sort find/ls results

These should only be sorted if explicitly requested, otherwise
make-built binaries may be different from kati-built binaries.

This resolves some binary-diff issues for Android between libc.a built
with make vs kati/ninja. To be the same across multiple
checkouts/machines, we should probably switch android to sorting these
results, but then the kati ninja support will stop working.

4 files changed, 32 insertions, 26 deletions

diff --git a/find.cc b/find.cc
index 86f5dc2..dfd6838 100644
--- a/find.cc
+++ b/find.cc
@@ -23,7 +23,6 @@
 #include <sys/types.h>
 #include <unistd.h>
 
-#include <map>
 #include <memory>
 #include <vector>
 
@@ -170,13 +169,15 @@ class DirentDirNode : public DirentNode {
       return this;
     size_t index = d.find('/');
     const string& p = d.substr(0, index).as_string();
-    auto found = children_.find(p);
-    if (found == children_.end())
-      return NULL;
-    if (index == string::npos)
-      return found->second;
-    StringPiece nd = d.substr(index + 1);
-    return found->second->FindDir(nd);
+    for (auto& child : children_) {
+      if (p == child.first) {
+        if (index == string::npos)
+          return child.second;
+        StringPiece nd = d.substr(index + 1);
+        return child.second->FindDir(nd);
+      }
+    }
+    return NULL;
   }
 
   virtual bool RunFind(const FindCommand& fc, int d,
@@ -205,12 +206,12 @@ class DirentDirNode : public DirentNode {
   }
 
   void Add(const string& name, DirentNode* c) {
-    auto p = children_.emplace(name, c);
-    CHECK(p.second);
+    auto p = children_.emplace(children_.end(), name, c);
+    CHECK(p->second);
   }
 
  private:
-  map<string, DirentNode*> children_;
+  vector<pair<string, DirentNode*>> children_;
 };
 
 class DirentSymlinkNode : public DirentNode {
diff --git a/func.cc b/func.cc
index e9cdca3..73259c7 100644
--- a/func.cc
+++ b/func.cc
@@ -476,7 +476,6 @@ static bool HasNoIoInShellScript(const string& cmd) {
 }
 
 static void ShellFuncImpl(const string& shell, const string& cmd,
-                          bool is_file_list_command,
                           string* s, FindCommand** fc) {
   LOG("ShellFunc: %s", cmd.c_str());
 
@@ -493,7 +492,6 @@ static void ShellFuncImpl(const string& shell, const string& cmd,
       }
 #else
       if (FindEmulator::Get()->HandleFind(cmd, **fc, s)) {
-        *s = SortWordsInString(*s);
         return;
       }
 #endif
@@ -504,19 +502,13 @@ static void ShellFuncImpl(const string& shell, const string& cmd,
 
   COLLECT_STATS_WITH_SLOW_REPORT("func shell time", cmd.c_str());
   RunCommand(shell, cmd, RedirectStderr::NONE, s);
-  if (is_file_list_command) {
-    *s = SortWordsInString(*s);
-  } else {
-    FormatForCommandSubstitution(s);
-  }
+  FormatForCommandSubstitution(s);
 
 #ifdef TEST_FIND_EMULATOR
   if (need_check) {
-    string sorted = SortWordsInString(*s);
-    out2 = SortWordsInString(out2);
-    if (sorted != out2) {
+    if (*s != out2) {
       ERROR("FindEmulator is broken: %s\n%s\nvs\n%s",
-            cmd.c_str(), sorted.c_str(), out2.c_str());
+            cmd.c_str(), s->c_str(), out2.c_str());
     }
   }
 #endif
@@ -542,7 +534,7 @@ void ShellFunc(const vector<Value*>& args, Evaluator* ev, string* s) {
 
   string out;
   FindCommand* fc = NULL;
-  ShellFuncImpl(*shell, *cmd, is_file_list_command, &out, &fc);
+  ShellFuncImpl(*shell, *cmd, &out, &fc);
   if (is_file_list_command) {
     FileListCommand* flc = new FileListCommand();
     flc->cmd = *cmd;
diff --git a/testcase/find_command.mk b/testcase/find_command.mk
index b7f6f76..e30807a 100644
--- a/testcase/find_command.mk
+++ b/testcase/find_command.mk
@@ -1,6 +1,8 @@
-# TODO(ninja): This test is only for ckati. ninja: fix $(sort $(shell $(1)))
+# TODO(ninja): This test is only for ckati. ninja: multiple problems
 # go: implement generic builtin find
-# ninja: $(sort $(shell "find -name testdir")) becomes "$( -name find testdir)"
+# ninja: find . finds ninja temporary files
+# ninja: escaping ! doesn't seem to be working
+# ninja: stderr gets reordered
 
 ifeq ($(shell uname),Darwin)
 USE_GNU_FIND:=
@@ -10,7 +12,7 @@ endif
 
 define run_find
 @echo $$ '$(strip $(1))'
-@echo $(sort $(shell $(1)))
+@echo $(shell $(1))
 endef
 
 test1:
diff --git a/testcase/find_command_sorted.mk b/testcase/find_command_sorted.mk
new file mode 100644
index 0000000..1721172
--- /dev/null
+++ b/testcase/find_command_sorted.mk
@@ -0,0 +1,11 @@
+# TODO(ninja): This test is only for ckati. ninja: fix $(sort $(shell $(1)))
+# go: implement generic builtin find
+# ninja: $(sort $(shell "find .")) becomes "$( .) find"
+
+define run_find
+@echo $$ '$(strip $(1))'
+@echo $(sort $(shell $(1)))
+endef
+
+test1:
+	$(call run_find, find .)