util: add find_leaves() supplimenting find_leaf()

The workspace needs to be able to list all its system branches, and the
system branches need to be able to list all their git repositories.

This is broadly the same thing, just with a different directory to look
out for, so provide that utility in morphlib.util.

find_leaf() is rewritten to use find_leaves(), this is less efficient
since it waits until every leaf is found.
I felt it was better to reduce the code than maintain a slightly more
optimal algorithm.
The find_leaf() algorithm could become more optimal if it could lazily
check for at least one result in a generator.

3 files changed, 26 insertions, 21 deletions

diff --git a/morphlib/sysbranchdir.py b/morphlib/sysbranchdir.py
index 0b3c859a..a05ca52e 100644
--- a/morphlib/sysbranchdir.py
+++ b/morphlib/sysbranchdir.py
@@ -156,13 +156,9 @@ class SystemBranchDirectory(object):
 
         '''
 
-        gitdirs = []
-        for dirname, subdirs, filenames in os.walk(self.root_directory):
-            if os.path.isdir(os.path.join(dirname, '.git')):
-                del subdirs[:]
-                gitdirs.append(morphlib.gitdir.GitDirectory(dirname))
-
-        return gitdirs
+        return (morphlib.gitdir.GitDirectory(dirname)
+                for dirname in
+                morphlib.util.find_leaves(self.root_directory, '.git'))
 
 
 def create(root_directory, root_repository_url, system_branch_name):
diff --git a/morphlib/sysbranchdir_tests.py b/morphlib/sysbranchdir_tests.py
index 7ee04c7d..7ec8ef5c 100644
--- a/morphlib/sysbranchdir_tests.py
+++ b/morphlib/sysbranchdir_tests.py
@@ -213,7 +213,7 @@ class SystemBranchDirectoryTests(unittest.TestCase):
         cached_repo = self.create_fake_cached_repo()
         sb.clone_cached_repo(cached_repo, 'master')
 
-        gd_list = sb.list_git_directories()
+        gd_list = list(sb.list_git_directories())
         self.assertEqual(len(gd_list), 1)
         self.assertEqual(
             gd_list[0].dirname,
diff --git a/morphlib/util.py b/morphlib/util.py
index 22288cac..19c0046f 100644
--- a/morphlib/util.py
+++ b/morphlib/util.py
@@ -306,26 +306,35 @@ def find_root(dirname, subdir_name):
     return dirname
 
 
+def find_leaves(search_dir, subdir_name):
+    '''This is like find_root, except it looks towards leaves.
+
+    The directory tree, starting at search_dir is traversed.
+
+    If a directory has a subdirectory called subdir_name, then
+    the directory is returned.
+
+    It does not recurse into a leaf's subdirectories.
+
+    '''
+
+    for dirname, subdirs, filenames in os.walk(search_dir):
+        if subdir_name in subdirs:
+            del subdirs[:]
+            yield dirname
+
+
 def find_leaf(dirname, subdir_name):
     '''This is like find_root, except it looks towards leaves.
 
-    It only looks in a subdirectory if it is the only subdirectory.
     If there are no subdirectories, or more than one, fail.
-    (Subdirectories whose name starts with a dot are ignored for this.)
 
     '''
 
-    while True:
-        if os.path.exists(os.path.join(dirname, subdir_name)):
-            return dirname
-        pathnames = [
-            os.path.join(dirname, x)
-            for x in os.listdir(dirname)
-            if not x.startswith('.')]
-        subdirs = [x for x in pathnames if os.path.isdir(x)]
-        if len(subdirs) != 1:
-            return None
-        dirname = subdirs[0]
+    leaves = list(find_leaves(dirname, subdir_name))
+    if len(leaves) == 1:
+        return leaves[0]
+    return None
 
 
 class EnvironmentAlreadySetError(morphlib.Error):