filesystem.py: fixed bug introduced in #3367 (scrambled order in output) (#4156)

PR #3367 inadvertently changed the semantics of _find_recursive and
_find_non_recursive so that the returned list are not ordered as the
input search list. This commit restores the original semantic, and adds
tests to verify it.

19 files changed, 95 insertions, 7 deletions

diff --git a/lib/spack/llnl/util/filesystem.py b/lib/spack/llnl/util/filesystem.py
index 25dc747499..f7fae7eb44 100644
--- a/lib/spack/llnl/util/filesystem.py
+++ b/lib/spack/llnl/util/filesystem.py
@@ -551,26 +551,41 @@ def find(root, files, recurse=True):
 
 
 def _find_recursive(root, search_files):
-    found_files = []
+
+    # The variable here is **on purpose** a defaultdict. The idea is that
+    # we want to poke the filesystem as little as possible, but still maintain
+    # stability in the order of the answer. Thus we are recording each library
+    # found in a key, and reconstructing the stable order later.
+    found_files = collections.defaultdict(list)
 
     for path, _, list_files in os.walk(root):
         for search_file in search_files:
             for list_file in list_files:
                 if fnmatch.fnmatch(list_file, search_file):
-                    found_files.append(join_path(path, list_file))
+                    found_files[search_file].append(join_path(path, list_file))
+
+    answer = []
+    for search_file in search_files:
+        answer.extend(found_files[search_file])
 
-    return found_files
+    return answer
 
 
 def _find_non_recursive(root, search_files):
-    found_files = []
+    # The variable here is **on purpose** a defaultdict as os.list_dir
+    # can return files in any order (does not preserve stability)
+    found_files = collections.defaultdict(list)
 
     for list_file in os.listdir(root):
         for search_file in search_files:
             if fnmatch.fnmatch(list_file, search_file):
-                found_files.append(join_path(root, list_file))
+                found_files[search_file].append(join_path(root, list_file))
+
+    answer = []
+    for search_file in search_files:
+        answer.extend(found_files[search_file])
 
-    return found_files
+    return answer
 
 
 # Utilities for libraries and headers
diff --git a/lib/spack/spack/test/data/directory_search/README.txt b/lib/spack/spack/test/data/directory_search/README.txt
new file mode 100644
index 0000000000..9c43a4224d
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/README.txt
@@ -0,0 +1 @@
+This directory tree is made up to test that search functions wil return a stable ordered sequence.
\ No newline at end of file
diff --git a/lib/spack/spack/test/data/directory_search/a/c.h b/lib/spack/spack/test/data/directory_search/a/c.h
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/a/c.h
diff --git a/lib/spack/spack/test/data/directory_search/a/libc.a b/lib/spack/spack/test/data/directory_search/a/libc.a
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/a/libc.a
diff --git a/lib/spack/spack/test/data/directory_search/a/libc.dylib b/lib/spack/spack/test/data/directory_search/a/libc.dylib
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/a/libc.dylib
diff --git a/lib/spack/spack/test/data/directory_search/a/libc.so b/lib/spack/spack/test/data/directory_search/a/libc.so
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/a/libc.so
diff --git a/lib/spack/spack/test/data/directory_search/b/b.h b/lib/spack/spack/test/data/directory_search/b/b.h
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/b/b.h
diff --git a/lib/spack/spack/test/data/directory_search/b/d.h b/lib/spack/spack/test/data/directory_search/b/d.h
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/b/d.h
diff --git a/lib/spack/spack/test/data/directory_search/b/liba.a b/lib/spack/spack/test/data/directory_search/b/liba.a
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/b/liba.a
diff --git a/lib/spack/spack/test/data/directory_search/b/liba.dylib b/lib/spack/spack/test/data/directory_search/b/liba.dylib
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/b/liba.dylib
diff --git a/lib/spack/spack/test/data/directory_search/b/liba.so b/lib/spack/spack/test/data/directory_search/b/liba.so
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/b/liba.so
diff --git a/lib/spack/spack/test/data/directory_search/b/libd.a b/lib/spack/spack/test/data/directory_search/b/libd.a
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/b/libd.a
diff --git a/lib/spack/spack/test/data/directory_search/b/libd.dylib b/lib/spack/spack/test/data/directory_search/b/libd.dylib
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/b/libd.dylib
diff --git a/lib/spack/spack/test/data/directory_search/b/libd.so b/lib/spack/spack/test/data/directory_search/b/libd.so
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/b/libd.so
diff --git a/lib/spack/spack/test/data/directory_search/c/a.h b/lib/spack/spack/test/data/directory_search/c/a.h
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/c/a.h
diff --git a/lib/spack/spack/test/data/directory_search/c/libb.a b/lib/spack/spack/test/data/directory_search/c/libb.a
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/c/libb.a
diff --git a/lib/spack/spack/test/data/directory_search/c/libb.dylib b/lib/spack/spack/test/data/directory_search/c/libb.dylib
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/c/libb.dylib
diff --git a/lib/spack/spack/test/data/directory_search/c/libb.so b/lib/spack/spack/test/data/directory_search/c/libb.so
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/lib/spack/spack/test/data/directory_search/c/libb.so
diff --git a/lib/spack/spack/test/file_list.py b/lib/spack/spack/test/file_list.py
index be4334f055..10c86d0d08 100644
--- a/lib/spack/spack/test/file_list.py
+++ b/lib/spack/spack/test/file_list.py
@@ -23,9 +23,14 @@
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
 
-import pytest
+import fnmatch
+import os
 
+import pytest
+import six
+import spack
 from llnl.util.filesystem import LibraryList, HeaderList
+from llnl.util.filesystem import find_libraries, find_headers
 
 
 @pytest.fixture()
@@ -201,3 +206,70 @@ class TestHeaderList(object):
         # Always produce an instance of HeaderList
         assert type(header_list + pylist) == type(header_list)
         assert type(pylist + header_list) == type(header_list)
+
+
+#: Directory where the data for the test below is stored
+search_dir = os.path.join(spack.test_path, 'data', 'directory_search')
+
+
+@pytest.mark.parametrize('search_fn,search_list,root,kwargs', [
+    (find_libraries, 'liba', search_dir, {'recurse': True}),
+    (find_libraries, ['liba'], search_dir, {'recurse': True}),
+    (find_libraries, 'libb', search_dir, {'recurse': True}),
+    (find_libraries, ['libc'], search_dir, {'recurse': True}),
+    (find_libraries, ['libc', 'liba'], search_dir, {'recurse': True}),
+    (find_libraries, ['liba', 'libc'], search_dir, {'recurse': True}),
+    (find_libraries, ['libc', 'libb', 'liba'], search_dir, {'recurse': True}),
+    (find_libraries, ['liba', 'libc'], search_dir, {'recurse': True}),
+    (find_libraries,
+     ['libc', 'libb', 'liba'],
+     search_dir,
+     {'recurse': True, 'shared': False}
+     ),
+    (find_headers, 'a', search_dir, {'recurse': True}),
+    (find_headers, ['a'], search_dir, {'recurse': True}),
+    (find_headers, 'b', search_dir, {'recurse': True}),
+    (find_headers, ['c'], search_dir, {'recurse': True}),
+    (find_headers, ['c', 'a'], search_dir, {'recurse': True}),
+    (find_headers, ['a', 'c'], search_dir, {'recurse': True}),
+    (find_headers, ['c', 'b', 'a'], search_dir, {'recurse': True}),
+    (find_headers, ['a', 'c'], search_dir, {'recurse': True}),
+    (find_libraries,
+     ['liba', 'libd'],
+     os.path.join(search_dir, 'b'),
+     {'recurse': False}
+     ),
+    (find_headers,
+     ['b', 'd'],
+     os.path.join(search_dir, 'b'),
+     {'recurse': False}
+     ),
+])
+def test_searching_order(search_fn, search_list, root, kwargs):
+
+    # Test search
+    result = search_fn(search_list, root, **kwargs)
+
+    # The tests are set-up so that something is always found
+    assert len(result) != 0
+
+    # Now reverse the result and start discarding things
+    # as soon as you have matches. In the end the list should
+    # be emptied.
+    l = list(reversed(result))
+
+    # At this point make sure the search list is a sequence
+    if isinstance(search_list, six.string_types):
+        search_list = [search_list]
+
+    # Discard entries in the order they appear in search list
+    for x in search_list:
+        try:
+            while fnmatch.fnmatch(l[-1], x) or x in l[-1]:
+                l.pop()
+        except IndexError:
+            # List is empty
+            pass
+
+    # List should be empty here
+    assert len(l) == 0