Repository: docker/docker-py

Issue:
dockerignore implementation is relatively slow compared to Docker's implementation
I ran into an issue in a project where my builds - run through `docker-compose` - seemed to be taking an awfully long time (around ~60 seconds) during the context build/upload stage. `strace` showed a ton of time was being spent `stat()`ing files that were included in my `.dockerignore` rules, which I found curious.

Oddly, when I simply used `docker build` to build the container, I didn't have this issue, and context build/upload took about ~3-5 seconds. I couldn't figure out what was going wrong, so I investigated `docker-py`, and found that almost all of my execution time was spent in [this `get_paths` call](https://github.com/docker/docker-py/blob/master/docker/utils/utils.py#L110).

It appears that the difference in execution time is because docker-py's implementation of dockerignore/tar exclusion is far slower than Docker's:

Docker's implementation of the dockerignore exclusion algorithm, (seen [here](https://github.com/docker/docker/blob/master/pkg/archive/archive.go#L518)), walks through each folder, but [does not descend into a directory if it matched an exclusion pattern](https://github.com/docker/docker/blob/master/pkg/archive/archive.go#L556). Meanwhile, docker-py first gets an array of *every single file in the context folder*, and then applies a filter to the array. This seems to be what is causing the massive difference in execution time when I build my project - docker-py is iterating over thousands of files that Docker correctly ignores.

I started on a fix, using what I believe are the same rules as Docker's algorithm: https://github.com/thomasboyt/docker-py/commit/9f302f6721bb8492140cf5b218a80d62a2b62e19

This runs just as fast as Docker's implementation, but doesn't fully implement exception rules (e.g. `!foo`), leading it to fail a few tests. Before I go through and add this feature, I wanted to confirm that I'm on the right path (and that no one else has a better solution/algorithm to apply).

Discussion:
aanand: Nice. I agree with @kanzure's comments, plus it'd be good to document the logic of `should_include`.
thomasboyt: @aanand cool, added some docs/comments!
aanand: Thanks! I think this can be squashed to one commit.

Patch:
diff --git a/docker/utils/utils.py b/docker/utils/utils.py
index 9c4bb477..762b39a4 100644
--- a/docker/utils/utils.py
+++ b/docker/utils/utils.py
@@ -107,38 +107,68 @@ def exclude_paths(root, patterns, dockerfile=None):
 
     exclude_patterns = list(set(patterns) - set(exceptions))
 
-    all_paths = get_paths(root)
-
-    # Remove all paths that are matched by any exclusion pattern
-    paths = [
-        p for p in all_paths
-        if not any(match_path(p, pattern) for pattern in exclude_patterns)
-    ]
-
-    # Add back the set of paths that are matched by any inclusion pattern.
-    # Include parent dirs - if we add back 'foo/bar', add 'foo' as well
-    for p in all_paths:
-        if any(match_path(p, pattern) for pattern in include_patterns):
-            components = p.split('/')
-            paths += [
-                '/'.join(components[:end])
-                for end in range(1, len(components) + 1)
-            ]
+    paths = get_paths(root, exclude_patterns, include_patterns,
+                      has_exceptions=len(exceptions) > 0)
 
     return set(paths)
 
 
-def get_paths(root):
+def should_include(path, exclude_patterns, include_patterns):
+    """
+    Given a path, a list of exclude patterns, and a list of inclusion patterns:
+
+    1. Returns True if the path doesn't match any exclusion pattern
+    2. Returns False if the path matches an exclusion pattern and doesn't match
+       an inclusion pattern
+    3. Returns true if the path matches an exclusion pattern and matches an
+       inclusion pattern
+    """
+    for pattern in exclude_patterns:
+        if match_path(path, pattern):
+            for pattern in include_patterns:
+                if match_path(path, pattern):
+                    return True
+            return False
+    return True
+
+
+def get_paths(root, exclude_patterns, include_patterns, has_exceptions=False):
     paths = []
 
-    for parent, dirs, files in os.walk(root, followlinks=False):
+    for parent, dirs, files in os.walk(root, topdown=True, followlinks=False):
         parent = os.path.relpath(parent, root)
         if parent == '.':
             parent = ''
+
+        # If exception rules exist, we can't skip recursing into ignored
+        # directories, as we need to look for exceptions in them.
+        #
+        # It may be possible to optimize this further for exception patterns
+        # that *couldn't* match within ignored directores.
+        #
+        # This matches the current docker logic (as of 2015-11-24):
+        # https://github.com/docker/docker/blob/37ba67bf636b34dc5c0c0265d62a089d0492088f/pkg/archive/archive.go#L555-L557
+
+        if not has_exceptions:
+
+            # Remove excluded patterns from the list of directories to traverse
+            # by mutating the dirs we're iterating over.
+            # This looks strange, but is considered the correct way to skip
+            # traversal. See https://docs.python.org/2/library/os.html#os.walk
+
+            dirs[:] = [d for d in dirs if
+                       should_include(os.path.join(parent, d),
+                                      exclude_patterns, include_patterns)]
+
         for path in dirs:
-            paths.append(os.path.join(parent, path))
+            if should_include(os.path.join(parent, path),
+                              exclude_patterns, include_patterns):
+                paths.append(os.path.join(parent, path))
+
         for path in files:
-            paths.append(os.path.join(parent, path))
+            if should_include(os.path.join(parent, path),
+                              exclude_patterns, include_patterns):
+                paths.append(os.path.join(parent, path))
 
     return paths
 


Test patch:
diff --git a/tests/integration/build_test.py b/tests/integration/build_test.py
index 011ddc3e..26164ae0 100644
--- a/tests/integration/build_test.py
+++ b/tests/integration/build_test.py
@@ -65,6 +65,7 @@ class BuildTest(helpers.BaseTestCase):
                 'ignored',
                 'Dockerfile',
                 '.dockerignore',
+                '!ignored/subdir/excepted-file',
                 '',  # empty line
             ]))
 
@@ -76,6 +77,9 @@ class BuildTest(helpers.BaseTestCase):
         with open(os.path.join(subdir, 'file'), 'w') as f:
             f.write("this file should be ignored")
 
+        with open(os.path.join(subdir, 'excepted-file'), 'w') as f:
+            f.write("this file should not be ignored")
+
         tag = 'docker-py-test-build-with-dockerignore'
         stream = self.client.build(
             path=base_dir,
@@ -84,7 +88,7 @@ class BuildTest(helpers.BaseTestCase):
         for chunk in stream:
             pass
 
-        c = self.client.create_container(tag, ['ls', '-1A', '/test'])
+        c = self.client.create_container(tag, ['find', '/test', '-type', 'f'])
         self.client.start(c)
         self.client.wait(c)
         logs = self.client.logs(c)
@@ -93,8 +97,9 @@ class BuildTest(helpers.BaseTestCase):
             logs = logs.decode('utf-8')
 
         self.assertEqual(
-            list(filter(None, logs.split('\n'))),
-            ['not-ignored'],
+            sorted(list(filter(None, logs.split('\n')))),
+            sorted(['/test/ignored/subdir/excepted-file',
+                    '/test/not-ignored']),
         )
 
     @requires_api_version('1.21')
diff --git a/tests/unit/utils_test.py b/tests/unit/utils_test.py
index 57ad4435..a68e1e78 100644
--- a/tests/unit/utils_test.py
+++ b/tests/unit/utils_test.py
@@ -671,17 +671,17 @@ class ExcludePathsTest(base.BaseTestCase):
 
     def test_directory_with_single_exception(self):
         assert self.exclude(['foo', '!foo/bar/a.py']) == self.all_paths - set([
-            'foo/a.py', 'foo/b.py',
+            'foo/a.py', 'foo/b.py', 'foo', 'foo/bar'
         ])
 
     def test_directory_with_subdir_exception(self):
         assert self.exclude(['foo', '!foo/bar']) == self.all_paths - set([
-            'foo/a.py', 'foo/b.py',
+            'foo/a.py', 'foo/b.py', 'foo'
         ])
 
     def test_directory_with_wildcard_exception(self):
         assert self.exclude(['foo', '!foo/*.py']) == self.all_paths - set([
-            'foo/bar', 'foo/bar/a.py',
+            'foo/bar', 'foo/bar/a.py', 'foo'
         ])
 
     def test_subdirectory(self):