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.
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
 

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).
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):

pip install -e .[dev]
parse_log_pytest
requirements.txt
pytest pytest-cov pytest-xdist pytest-mock pytest-asyncio
apt-get update apt-get install -y gcc
3.9
requirements.txt
pytest --no-header -rA --tb=line --color=no -p no:cacheprovider -W ignore::DeprecationWarning
coverage==7.8.0
-e git+https://github.com/docker/docker-py.git@28864df27b2cf289478d5fa9d5ca27a9f0daa9a8#egg=docker_py
exceptiongroup==1.2.2
execnet==2.1.1
iniconfig==2.1.0
packaging==24.2
pluggy==1.5.0
pytest==8.3.5
pytest-asyncio==0.26.0
pytest-cov==6.0.0
pytest-mock==3.14.0
pytest-xdist==3.6.1
requests==2.5.3
six==1.17.0
tomli==2.2.1
typing_extensions==4.13.0
websocket_client==0.32.0

name: docker-py
channels:
  - defaults
  - https://repo.anaconda.com/pkgs/main
  - https://repo.anaconda.com/pkgs/r
  - conda-forge
dependencies:
  - _libgcc_mutex=0.1=main
  - _openmp_mutex=5.1=1_gnu
  - ca-certificates=2025.2.25=h06a4308_0
  - ld_impl_linux-64=2.40=h12ee557_0
  - libffi=3.4.4=h6a678d5_1
  - libgcc-ng=11.2.0=h1234567_1
  - libgomp=11.2.0=h1234567_1
  - libstdcxx-ng=11.2.0=h1234567_1
  - ncurses=6.4=h6a678d5_0
  - openssl=3.0.16=h5eee18b_0
  - pip=25.0=py39h06a4308_0
  - python=3.9.21=he870216_1
  - readline=8.2=h5eee18b_0
  - setuptools=75.8.0=py39h06a4308_0
  - sqlite=3.45.3=h5eee18b_0
  - tk=8.6.14=h39e8969_0
  - tzdata=2025a=h04d1e81_0
  - wheel=0.45.1=py39h06a4308_0
  - xz=5.6.4=h5eee18b_1
  - zlib=1.2.13=h5eee18b_1
  - pip:
      - coverage==7.8.0
      - exceptiongroup==1.2.2
      - execnet==2.1.1
      - iniconfig==2.1.0
      - packaging==24.2
      - pluggy==1.5.0
      - pytest==8.3.5
      - pytest-asyncio==0.26.0
      - pytest-cov==6.0.0
      - pytest-mock==3.14.0
      - pytest-xdist==3.6.1
      - requests==2.5.3
      - six==1.17.0
      - tomli==2.2.1
      - typing-extensions==4.13.0
      - websocket-client==0.32.0
prefix: /opt/conda/envs/docker-py

tests/unit/utils_test.py::ExcludePathsTest::test_directory_with_single_exception tests/unit/utils_test.py::ExcludePathsTest::test_directory_with_subdir_exception tests/unit/utils_test.py::ExcludePathsTest::test_directory_with_wildcard_exception
tests/unit/utils_test.py::HostConfigTest::test_create_host_config_invalid_cpu_cfs_types tests/unit/utils_test.py::HostConfigTest::test_create_host_config_no_options tests/unit/utils_test.py::HostConfigTest::test_create_host_config_no_options_newer_api_version tests/unit/utils_test.py::HostConfigTest::test_create_host_config_with_cpu_period tests/unit/utils_test.py::HostConfigTest::test_create_host_config_with_cpu_quota tests/unit/utils_test.py::HostConfigTest::test_create_host_config_with_oom_kill_disable tests/unit/utils_test.py::UlimitTest::test_create_host_config_dict_ulimit tests/unit/utils_test.py::UlimitTest::test_create_host_config_dict_ulimit_capitals tests/unit/utils_test.py::UlimitTest::test_create_host_config_obj_ulimit tests/unit/utils_test.py::UlimitTest::test_ulimit_invalid_type tests/unit/utils_test.py::LogConfigTest::test_create_host_config_dict_logconfig tests/unit/utils_test.py::LogConfigTest::test_create_host_config_obj_logconfig tests/unit/utils_test.py::LogConfigTest::test_logconfig_invalid_config_type tests/unit/utils_test.py::KwargsFromEnvTest::test_kwargs_from_env_empty tests/unit/utils_test.py::KwargsFromEnvTest::test_kwargs_from_env_no_cert_path tests/unit/utils_test.py::KwargsFromEnvTest::test_kwargs_from_env_tls tests/unit/utils_test.py::ConverVolumeBindsTest::test_convert_volume_binds_compact tests/unit/utils_test.py::ConverVolumeBindsTest::test_convert_volume_binds_complete tests/unit/utils_test.py::ConverVolumeBindsTest::test_convert_volume_binds_empty tests/unit/utils_test.py::ConverVolumeBindsTest::test_convert_volume_binds_list tests/unit/utils_test.py::ConverVolumeBindsTest::test_convert_volume_binds_no_mode tests/unit/utils_test.py::ConverVolumeBindsTest::test_convert_volume_binds_unicode_bytes_input tests/unit/utils_test.py::ConverVolumeBindsTest::test_convert_volume_binds_unicode_unicode_input tests/unit/utils_test.py::ParseEnvFileTest::test_parse_env_file_commented_line tests/unit/utils_test.py::ParseEnvFileTest::test_parse_env_file_invalid_line tests/unit/utils_test.py::ParseEnvFileTest::test_parse_env_file_proper tests/unit/utils_test.py::ParseHostTest::test_parse_host tests/unit/utils_test.py::ParseHostTest::test_parse_host_empty_value tests/unit/utils_test.py::ParseRepositoryTagTest::test_index_image_no_tag tests/unit/utils_test.py::ParseRepositoryTagTest::test_index_image_sha tests/unit/utils_test.py::ParseRepositoryTagTest::test_index_image_tag tests/unit/utils_test.py::ParseRepositoryTagTest::test_index_user_image_no_tag tests/unit/utils_test.py::ParseRepositoryTagTest::test_index_user_image_tag tests/unit/utils_test.py::ParseRepositoryTagTest::test_private_reg_image_no_tag tests/unit/utils_test.py::ParseRepositoryTagTest::test_private_reg_image_sha tests/unit/utils_test.py::ParseRepositoryTagTest::test_private_reg_image_tag tests/unit/utils_test.py::UtilsTest::test_convert_filters tests/unit/utils_test.py::UtilsTest::test_decode_json_header tests/unit/utils_test.py::UtilsTest::test_parse_bytes tests/unit/utils_test.py::SplitCommandTest::test_split_command_with_unicode tests/unit/utils_test.py::PortsTest::test_build_port_bindings_with_matching_internal_port_ranges tests/unit/utils_test.py::PortsTest::test_build_port_bindings_with_matching_internal_ports tests/unit/utils_test.py::PortsTest::test_build_port_bindings_with_nonmatching_internal_port_ranges tests/unit/utils_test.py::PortsTest::test_build_port_bindings_with_nonmatching_internal_ports tests/unit/utils_test.py::PortsTest::test_build_port_bindings_with_one_port tests/unit/utils_test.py::PortsTest::test_build_port_bindings_with_port_range tests/unit/utils_test.py::PortsTest::test_host_only_with_colon tests/unit/utils_test.py::PortsTest::test_non_matching_length_port_ranges tests/unit/utils_test.py::PortsTest::test_port_and_range_invalid tests/unit/utils_test.py::PortsTest::test_port_only_with_colon tests/unit/utils_test.py::PortsTest::test_split_port_invalid tests/unit/utils_test.py::PortsTest::test_split_port_no_host_port tests/unit/utils_test.py::PortsTest::test_split_port_range_no_host_port tests/unit/utils_test.py::PortsTest::test_split_port_range_with_host_ip_no_port tests/unit/utils_test.py::PortsTest::test_split_port_range_with_host_port tests/unit/utils_test.py::PortsTest::test_split_port_range_with_protocol tests/unit/utils_test.py::PortsTest::test_split_port_with_host_ip tests/unit/utils_test.py::PortsTest::test_split_port_with_host_ip_no_port tests/unit/utils_test.py::PortsTest::test_split_port_with_host_port tests/unit/utils_test.py::PortsTest::test_split_port_with_protocol tests/unit/utils_test.py::ExcludePathsTest::test_directory tests/unit/utils_test.py::ExcludePathsTest::test_directory_with_trailing_slash tests/unit/utils_test.py::ExcludePathsTest::test_exclude_custom_dockerfile tests/unit/utils_test.py::ExcludePathsTest::test_exclude_dockerfile_dockerignore tests/unit/utils_test.py::ExcludePathsTest::test_no_dupes tests/unit/utils_test.py::ExcludePathsTest::test_no_excludes tests/unit/utils_test.py::ExcludePathsTest::test_question_mark tests/unit/utils_test.py::ExcludePathsTest::test_single_filename tests/unit/utils_test.py::ExcludePathsTest::test_single_filename_trailing_slash tests/unit/utils_test.py::ExcludePathsTest::test_single_subdir_single_filename tests/unit/utils_test.py::ExcludePathsTest::test_single_subdir_wildcard_filename tests/unit/utils_test.py::ExcludePathsTest::test_subdirectory tests/unit/utils_test.py::ExcludePathsTest::test_wildcard_exclude tests/unit/utils_test.py::ExcludePathsTest::test_wildcard_filename_end tests/unit/utils_test.py::ExcludePathsTest::test_wildcard_filename_start tests/unit/utils_test.py::ExcludePathsTest::test_wildcard_subdir_single_filename tests/unit/utils_test.py::ExcludePathsTest::test_wildcard_subdir_wildcard_filename tests/unit/utils_test.py::ExcludePathsTest::test_wildcard_with_exception tests/unit/utils_test.py::ExcludePathsTest::test_wildcard_with_wildcard_exception tests/unit/utils_test.py::TarTest::test_tar_with_directory_symlinks tests/unit/utils_test.py::TarTest::test_tar_with_empty_directory tests/unit/utils_test.py::TarTest::test_tar_with_excludes tests/unit/utils_test.py::TarTest::test_tar_with_file_symlinks
docker/utils/utils.py
docker/utils/utils.py