jpayne@69: """Automatic discovery of Python modules and packages (for inclusion in the
jpayne@69: distribution) and other config values.
jpayne@69: 
jpayne@69: For the purposes of this module, the following nomenclature is used:
jpayne@69: 
jpayne@69: - "src-layout": a directory representing a Python project that contains a "src"
jpayne@69:   folder. Everything under the "src" folder is meant to be included in the
jpayne@69:   distribution when packaging the project. Example::
jpayne@69: 
jpayne@69:     .
jpayne@69:     ├── tox.ini
jpayne@69:     ├── pyproject.toml
jpayne@69:     └── src/
jpayne@69:         └── mypkg/
jpayne@69:             ├── __init__.py
jpayne@69:             ├── mymodule.py
jpayne@69:             └── my_data_file.txt
jpayne@69: 
jpayne@69: - "flat-layout": a Python project that does not use "src-layout" but instead
jpayne@69:   have a directory under the project root for each package::
jpayne@69: 
jpayne@69:     .
jpayne@69:     ├── tox.ini
jpayne@69:     ├── pyproject.toml
jpayne@69:     └── mypkg/
jpayne@69:         ├── __init__.py
jpayne@69:         ├── mymodule.py
jpayne@69:         └── my_data_file.txt
jpayne@69: 
jpayne@69: - "single-module": a project that contains a single Python script direct under
jpayne@69:   the project root (no directory used)::
jpayne@69: 
jpayne@69:     .
jpayne@69:     ├── tox.ini
jpayne@69:     ├── pyproject.toml
jpayne@69:     └── mymodule.py
jpayne@69: 
jpayne@69: """
jpayne@69: 
jpayne@69: from __future__ import annotations
jpayne@69: 
jpayne@69: import itertools
jpayne@69: import os
jpayne@69: from collections.abc import Iterator
jpayne@69: from fnmatch import fnmatchcase
jpayne@69: from glob import glob
jpayne@69: from pathlib import Path
jpayne@69: from typing import TYPE_CHECKING, Iterable, Mapping
jpayne@69: 
jpayne@69: import _distutils_hack.override  # noqa: F401
jpayne@69: 
jpayne@69: from ._path import StrPath
jpayne@69: 
jpayne@69: from distutils import log
jpayne@69: from distutils.util import convert_path
jpayne@69: 
jpayne@69: if TYPE_CHECKING:
jpayne@69:     from setuptools import Distribution
jpayne@69: 
jpayne@69: chain_iter = itertools.chain.from_iterable
jpayne@69: 
jpayne@69: 
jpayne@69: def _valid_name(path: StrPath) -> bool:
jpayne@69:     # Ignore invalid names that cannot be imported directly
jpayne@69:     return os.path.basename(path).isidentifier()
jpayne@69: 
jpayne@69: 
jpayne@69: class _Filter:
jpayne@69:     """
jpayne@69:     Given a list of patterns, create a callable that will be true only if
jpayne@69:     the input matches at least one of the patterns.
jpayne@69:     """
jpayne@69: 
jpayne@69:     def __init__(self, *patterns: str):
jpayne@69:         self._patterns = dict.fromkeys(patterns)
jpayne@69: 
jpayne@69:     def __call__(self, item: str) -> bool:
jpayne@69:         return any(fnmatchcase(item, pat) for pat in self._patterns)
jpayne@69: 
jpayne@69:     def __contains__(self, item: str) -> bool:
jpayne@69:         return item in self._patterns
jpayne@69: 
jpayne@69: 
jpayne@69: class _Finder:
jpayne@69:     """Base class that exposes functionality for module/package finders"""
jpayne@69: 
jpayne@69:     ALWAYS_EXCLUDE: tuple[str, ...] = ()
jpayne@69:     DEFAULT_EXCLUDE: tuple[str, ...] = ()
jpayne@69: 
jpayne@69:     @classmethod
jpayne@69:     def find(
jpayne@69:         cls,
jpayne@69:         where: StrPath = '.',
jpayne@69:         exclude: Iterable[str] = (),
jpayne@69:         include: Iterable[str] = ('*',),
jpayne@69:     ) -> list[str]:
jpayne@69:         """Return a list of all Python items (packages or modules, depending on
jpayne@69:         the finder implementation) found within directory 'where'.
jpayne@69: 
jpayne@69:         'where' is the root directory which will be searched.
jpayne@69:         It should be supplied as a "cross-platform" (i.e. URL-style) path;
jpayne@69:         it will be converted to the appropriate local path syntax.
jpayne@69: 
jpayne@69:         'exclude' is a sequence of names to exclude; '*' can be used
jpayne@69:         as a wildcard in the names.
jpayne@69:         When finding packages, 'foo.*' will exclude all subpackages of 'foo'
jpayne@69:         (but not 'foo' itself).
jpayne@69: 
jpayne@69:         'include' is a sequence of names to include.
jpayne@69:         If it's specified, only the named items will be included.
jpayne@69:         If it's not specified, all found items will be included.
jpayne@69:         'include' can contain shell style wildcard patterns just like
jpayne@69:         'exclude'.
jpayne@69:         """
jpayne@69: 
jpayne@69:         exclude = exclude or cls.DEFAULT_EXCLUDE
jpayne@69:         return list(
jpayne@69:             cls._find_iter(
jpayne@69:                 convert_path(str(where)),
jpayne@69:                 _Filter(*cls.ALWAYS_EXCLUDE, *exclude),
jpayne@69:                 _Filter(*include),
jpayne@69:             )
jpayne@69:         )
jpayne@69: 
jpayne@69:     @classmethod
jpayne@69:     def _find_iter(
jpayne@69:         cls, where: StrPath, exclude: _Filter, include: _Filter
jpayne@69:     ) -> Iterator[str]:
jpayne@69:         raise NotImplementedError
jpayne@69: 
jpayne@69: 
jpayne@69: class PackageFinder(_Finder):
jpayne@69:     """
jpayne@69:     Generate a list of all Python packages found within a directory
jpayne@69:     """
jpayne@69: 
jpayne@69:     ALWAYS_EXCLUDE = ("ez_setup", "*__pycache__")
jpayne@69: 
jpayne@69:     @classmethod
jpayne@69:     def _find_iter(
jpayne@69:         cls, where: StrPath, exclude: _Filter, include: _Filter
jpayne@69:     ) -> Iterator[str]:
jpayne@69:         """
jpayne@69:         All the packages found in 'where' that pass the 'include' filter, but
jpayne@69:         not the 'exclude' filter.
jpayne@69:         """
jpayne@69:         for root, dirs, files in os.walk(str(where), followlinks=True):
jpayne@69:             # Copy dirs to iterate over it, then empty dirs.
jpayne@69:             all_dirs = dirs[:]
jpayne@69:             dirs[:] = []
jpayne@69: 
jpayne@69:             for dir in all_dirs:
jpayne@69:                 full_path = os.path.join(root, dir)
jpayne@69:                 rel_path = os.path.relpath(full_path, where)
jpayne@69:                 package = rel_path.replace(os.path.sep, '.')
jpayne@69: 
jpayne@69:                 # Skip directory trees that are not valid packages
jpayne@69:                 if '.' in dir or not cls._looks_like_package(full_path, package):
jpayne@69:                     continue
jpayne@69: 
jpayne@69:                 # Should this package be included?
jpayne@69:                 if include(package) and not exclude(package):
jpayne@69:                     yield package
jpayne@69: 
jpayne@69:                 # Early pruning if there is nothing else to be scanned
jpayne@69:                 if f"{package}*" in exclude or f"{package}.*" in exclude:
jpayne@69:                     continue
jpayne@69: 
jpayne@69:                 # Keep searching subdirectories, as there may be more packages
jpayne@69:                 # down there, even if the parent was excluded.
jpayne@69:                 dirs.append(dir)
jpayne@69: 
jpayne@69:     @staticmethod
jpayne@69:     def _looks_like_package(path: StrPath, _package_name: str) -> bool:
jpayne@69:         """Does a directory look like a package?"""
jpayne@69:         return os.path.isfile(os.path.join(path, '__init__.py'))
jpayne@69: 
jpayne@69: 
jpayne@69: class PEP420PackageFinder(PackageFinder):
jpayne@69:     @staticmethod
jpayne@69:     def _looks_like_package(_path: StrPath, _package_name: str) -> bool:
jpayne@69:         return True
jpayne@69: 
jpayne@69: 
jpayne@69: class ModuleFinder(_Finder):
jpayne@69:     """Find isolated Python modules.
jpayne@69:     This function will **not** recurse subdirectories.
jpayne@69:     """
jpayne@69: 
jpayne@69:     @classmethod
jpayne@69:     def _find_iter(
jpayne@69:         cls, where: StrPath, exclude: _Filter, include: _Filter
jpayne@69:     ) -> Iterator[str]:
jpayne@69:         for file in glob(os.path.join(where, "*.py")):
jpayne@69:             module, _ext = os.path.splitext(os.path.basename(file))
jpayne@69: 
jpayne@69:             if not cls._looks_like_module(module):
jpayne@69:                 continue
jpayne@69: 
jpayne@69:             if include(module) and not exclude(module):
jpayne@69:                 yield module
jpayne@69: 
jpayne@69:     _looks_like_module = staticmethod(_valid_name)
jpayne@69: 
jpayne@69: 
jpayne@69: # We have to be extra careful in the case of flat layout to not include files
jpayne@69: # and directories not meant for distribution (e.g. tool-related)
jpayne@69: 
jpayne@69: 
jpayne@69: class FlatLayoutPackageFinder(PEP420PackageFinder):
jpayne@69:     _EXCLUDE = (
jpayne@69:         "ci",
jpayne@69:         "bin",
jpayne@69:         "debian",
jpayne@69:         "doc",
jpayne@69:         "docs",
jpayne@69:         "documentation",
jpayne@69:         "manpages",
jpayne@69:         "news",
jpayne@69:         "newsfragments",
jpayne@69:         "changelog",
jpayne@69:         "test",
jpayne@69:         "tests",
jpayne@69:         "unit_test",
jpayne@69:         "unit_tests",
jpayne@69:         "example",
jpayne@69:         "examples",
jpayne@69:         "scripts",
jpayne@69:         "tools",
jpayne@69:         "util",
jpayne@69:         "utils",
jpayne@69:         "python",
jpayne@69:         "build",
jpayne@69:         "dist",
jpayne@69:         "venv",
jpayne@69:         "env",
jpayne@69:         "requirements",
jpayne@69:         # ---- Task runners / Build tools ----
jpayne@69:         "tasks",  # invoke
jpayne@69:         "fabfile",  # fabric
jpayne@69:         "site_scons",  # SCons
jpayne@69:         # ---- Other tools ----
jpayne@69:         "benchmark",
jpayne@69:         "benchmarks",
jpayne@69:         "exercise",
jpayne@69:         "exercises",
jpayne@69:         "htmlcov",  # Coverage.py
jpayne@69:         # ---- Hidden directories/Private packages ----
jpayne@69:         "[._]*",
jpayne@69:     )
jpayne@69: 
jpayne@69:     DEFAULT_EXCLUDE = tuple(chain_iter((p, f"{p}.*") for p in _EXCLUDE))
jpayne@69:     """Reserved package names"""
jpayne@69: 
jpayne@69:     @staticmethod
jpayne@69:     def _looks_like_package(_path: StrPath, package_name: str) -> bool:
jpayne@69:         names = package_name.split('.')
jpayne@69:         # Consider PEP 561
jpayne@69:         root_pkg_is_valid = names[0].isidentifier() or names[0].endswith("-stubs")
jpayne@69:         return root_pkg_is_valid and all(name.isidentifier() for name in names[1:])
jpayne@69: 
jpayne@69: 
jpayne@69: class FlatLayoutModuleFinder(ModuleFinder):
jpayne@69:     DEFAULT_EXCLUDE = (
jpayne@69:         "setup",
jpayne@69:         "conftest",
jpayne@69:         "test",
jpayne@69:         "tests",
jpayne@69:         "example",
jpayne@69:         "examples",
jpayne@69:         "build",
jpayne@69:         # ---- Task runners ----
jpayne@69:         "toxfile",
jpayne@69:         "noxfile",
jpayne@69:         "pavement",
jpayne@69:         "dodo",
jpayne@69:         "tasks",
jpayne@69:         "fabfile",
jpayne@69:         # ---- Other tools ----
jpayne@69:         "[Ss][Cc]onstruct",  # SCons
jpayne@69:         "conanfile",  # Connan: C/C++ build tool
jpayne@69:         "manage",  # Django
jpayne@69:         "benchmark",
jpayne@69:         "benchmarks",
jpayne@69:         "exercise",
jpayne@69:         "exercises",
jpayne@69:         # ---- Hidden files/Private modules ----
jpayne@69:         "[._]*",
jpayne@69:     )
jpayne@69:     """Reserved top-level module names"""
jpayne@69: 
jpayne@69: 
jpayne@69: def _find_packages_within(root_pkg: str, pkg_dir: StrPath) -> list[str]:
jpayne@69:     nested = PEP420PackageFinder.find(pkg_dir)
jpayne@69:     return [root_pkg] + [".".join((root_pkg, n)) for n in nested]
jpayne@69: 
jpayne@69: 
jpayne@69: class ConfigDiscovery:
jpayne@69:     """Fill-in metadata and options that can be automatically derived
jpayne@69:     (from other metadata/options, the file system or conventions)
jpayne@69:     """
jpayne@69: 
jpayne@69:     def __init__(self, distribution: Distribution):
jpayne@69:         self.dist = distribution
jpayne@69:         self._called = False
jpayne@69:         self._disabled = False
jpayne@69:         self._skip_ext_modules = False
jpayne@69: 
jpayne@69:     def _disable(self):
jpayne@69:         """Internal API to disable automatic discovery"""
jpayne@69:         self._disabled = True
jpayne@69: 
jpayne@69:     def _ignore_ext_modules(self):
jpayne@69:         """Internal API to disregard ext_modules.
jpayne@69: 
jpayne@69:         Normally auto-discovery would not be triggered if ``ext_modules`` are set
jpayne@69:         (this is done for backward compatibility with existing packages relying on
jpayne@69:         ``setup.py`` or ``setup.cfg``). However, ``setuptools`` can call this function
jpayne@69:         to ignore given ``ext_modules`` and proceed with the auto-discovery if
jpayne@69:         ``packages`` and ``py_modules`` are not given (e.g. when using pyproject.toml
jpayne@69:         metadata).
jpayne@69:         """
jpayne@69:         self._skip_ext_modules = True
jpayne@69: 
jpayne@69:     @property
jpayne@69:     def _root_dir(self) -> StrPath:
jpayne@69:         # The best is to wait until `src_root` is set in dist, before using _root_dir.
jpayne@69:         return self.dist.src_root or os.curdir
jpayne@69: 
jpayne@69:     @property
jpayne@69:     def _package_dir(self) -> dict[str, str]:
jpayne@69:         if self.dist.package_dir is None:
jpayne@69:             return {}
jpayne@69:         return self.dist.package_dir
jpayne@69: 
jpayne@69:     def __call__(
jpayne@69:         self, force: bool = False, name: bool = True, ignore_ext_modules: bool = False
jpayne@69:     ):
jpayne@69:         """Automatically discover missing configuration fields
jpayne@69:         and modifies the given ``distribution`` object in-place.
jpayne@69: 
jpayne@69:         Note that by default this will only have an effect the first time the
jpayne@69:         ``ConfigDiscovery`` object is called.
jpayne@69: 
jpayne@69:         To repeatedly invoke automatic discovery (e.g. when the project
jpayne@69:         directory changes), please use ``force=True`` (or create a new
jpayne@69:         ``ConfigDiscovery`` instance).
jpayne@69:         """
jpayne@69:         if force is False and (self._called or self._disabled):
jpayne@69:             # Avoid overhead of multiple calls
jpayne@69:             return
jpayne@69: 
jpayne@69:         self._analyse_package_layout(ignore_ext_modules)
jpayne@69:         if name:
jpayne@69:             self.analyse_name()  # depends on ``packages`` and ``py_modules``
jpayne@69: 
jpayne@69:         self._called = True
jpayne@69: 
jpayne@69:     def _explicitly_specified(self, ignore_ext_modules: bool) -> bool:
jpayne@69:         """``True`` if the user has specified some form of package/module listing"""
jpayne@69:         ignore_ext_modules = ignore_ext_modules or self._skip_ext_modules
jpayne@69:         ext_modules = not (self.dist.ext_modules is None or ignore_ext_modules)
jpayne@69:         return (
jpayne@69:             self.dist.packages is not None
jpayne@69:             or self.dist.py_modules is not None
jpayne@69:             or ext_modules
jpayne@69:             or hasattr(self.dist, "configuration")
jpayne@69:             and self.dist.configuration
jpayne@69:             # ^ Some projects use numpy.distutils.misc_util.Configuration
jpayne@69:         )
jpayne@69: 
jpayne@69:     def _analyse_package_layout(self, ignore_ext_modules: bool) -> bool:
jpayne@69:         if self._explicitly_specified(ignore_ext_modules):
jpayne@69:             # For backward compatibility, just try to find modules/packages
jpayne@69:             # when nothing is given
jpayne@69:             return True
jpayne@69: 
jpayne@69:         log.debug(
jpayne@69:             "No `packages` or `py_modules` configuration, performing "
jpayne@69:             "automatic discovery."
jpayne@69:         )
jpayne@69: 
jpayne@69:         return (
jpayne@69:             self._analyse_explicit_layout()
jpayne@69:             or self._analyse_src_layout()
jpayne@69:             # flat-layout is the trickiest for discovery so it should be last
jpayne@69:             or self._analyse_flat_layout()
jpayne@69:         )
jpayne@69: 
jpayne@69:     def _analyse_explicit_layout(self) -> bool:
jpayne@69:         """The user can explicitly give a package layout via ``package_dir``"""
jpayne@69:         package_dir = self._package_dir.copy()  # don't modify directly
jpayne@69:         package_dir.pop("", None)  # This falls under the "src-layout" umbrella
jpayne@69:         root_dir = self._root_dir
jpayne@69: 
jpayne@69:         if not package_dir:
jpayne@69:             return False
jpayne@69: 
jpayne@69:         log.debug(f"`explicit-layout` detected -- analysing {package_dir}")
jpayne@69:         pkgs = chain_iter(
jpayne@69:             _find_packages_within(pkg, os.path.join(root_dir, parent_dir))
jpayne@69:             for pkg, parent_dir in package_dir.items()
jpayne@69:         )
jpayne@69:         self.dist.packages = list(pkgs)
jpayne@69:         log.debug(f"discovered packages -- {self.dist.packages}")
jpayne@69:         return True
jpayne@69: 
jpayne@69:     def _analyse_src_layout(self) -> bool:
jpayne@69:         """Try to find all packages or modules under the ``src`` directory
jpayne@69:         (or anything pointed by ``package_dir[""]``).
jpayne@69: 
jpayne@69:         The "src-layout" is relatively safe for automatic discovery.
jpayne@69:         We assume that everything within is meant to be included in the
jpayne@69:         distribution.
jpayne@69: 
jpayne@69:         If ``package_dir[""]`` is not given, but the ``src`` directory exists,
jpayne@69:         this function will set ``package_dir[""] = "src"``.
jpayne@69:         """
jpayne@69:         package_dir = self._package_dir
jpayne@69:         src_dir = os.path.join(self._root_dir, package_dir.get("", "src"))
jpayne@69:         if not os.path.isdir(src_dir):
jpayne@69:             return False
jpayne@69: 
jpayne@69:         log.debug(f"`src-layout` detected -- analysing {src_dir}")
jpayne@69:         package_dir.setdefault("", os.path.basename(src_dir))
jpayne@69:         self.dist.package_dir = package_dir  # persist eventual modifications
jpayne@69:         self.dist.packages = PEP420PackageFinder.find(src_dir)
jpayne@69:         self.dist.py_modules = ModuleFinder.find(src_dir)
jpayne@69:         log.debug(f"discovered packages -- {self.dist.packages}")
jpayne@69:         log.debug(f"discovered py_modules -- {self.dist.py_modules}")
jpayne@69:         return True
jpayne@69: 
jpayne@69:     def _analyse_flat_layout(self) -> bool:
jpayne@69:         """Try to find all packages and modules under the project root.
jpayne@69: 
jpayne@69:         Since the ``flat-layout`` is more dangerous in terms of accidentally including
jpayne@69:         extra files/directories, this function is more conservative and will raise an
jpayne@69:         error if multiple packages or modules are found.
jpayne@69: 
jpayne@69:         This assumes that multi-package dists are uncommon and refuse to support that
jpayne@69:         use case in order to be able to prevent unintended errors.
jpayne@69:         """
jpayne@69:         log.debug(f"`flat-layout` detected -- analysing {self._root_dir}")
jpayne@69:         return self._analyse_flat_packages() or self._analyse_flat_modules()
jpayne@69: 
jpayne@69:     def _analyse_flat_packages(self) -> bool:
jpayne@69:         self.dist.packages = FlatLayoutPackageFinder.find(self._root_dir)
jpayne@69:         top_level = remove_nested_packages(remove_stubs(self.dist.packages))
jpayne@69:         log.debug(f"discovered packages -- {self.dist.packages}")
jpayne@69:         self._ensure_no_accidental_inclusion(top_level, "packages")
jpayne@69:         return bool(top_level)
jpayne@69: 
jpayne@69:     def _analyse_flat_modules(self) -> bool:
jpayne@69:         self.dist.py_modules = FlatLayoutModuleFinder.find(self._root_dir)
jpayne@69:         log.debug(f"discovered py_modules -- {self.dist.py_modules}")
jpayne@69:         self._ensure_no_accidental_inclusion(self.dist.py_modules, "modules")
jpayne@69:         return bool(self.dist.py_modules)
jpayne@69: 
jpayne@69:     def _ensure_no_accidental_inclusion(self, detected: list[str], kind: str):
jpayne@69:         if len(detected) > 1:
jpayne@69:             from inspect import cleandoc
jpayne@69: 
jpayne@69:             from setuptools.errors import PackageDiscoveryError
jpayne@69: 
jpayne@69:             msg = f"""Multiple top-level {kind} discovered in a flat-layout: {detected}.
jpayne@69: 
jpayne@69:             To avoid accidental inclusion of unwanted files or directories,
jpayne@69:             setuptools will not proceed with this build.
jpayne@69: 
jpayne@69:             If you are trying to create a single distribution with multiple {kind}
jpayne@69:             on purpose, you should not rely on automatic discovery.
jpayne@69:             Instead, consider the following options:
jpayne@69: 
jpayne@69:             1. set up custom discovery (`find` directive with `include` or `exclude`)
jpayne@69:             2. use a `src-layout`
jpayne@69:             3. explicitly set `py_modules` or `packages` with a list of names
jpayne@69: 
jpayne@69:             To find more information, look for "package discovery" on setuptools docs.
jpayne@69:             """
jpayne@69:             raise PackageDiscoveryError(cleandoc(msg))
jpayne@69: 
jpayne@69:     def analyse_name(self):
jpayne@69:         """The packages/modules are the essential contribution of the author.
jpayne@69:         Therefore the name of the distribution can be derived from them.
jpayne@69:         """
jpayne@69:         if self.dist.metadata.name or self.dist.name:
jpayne@69:             # get_name() is not reliable (can return "UNKNOWN")
jpayne@69:             return
jpayne@69: 
jpayne@69:         log.debug("No `name` configuration, performing automatic discovery")
jpayne@69: 
jpayne@69:         name = (
jpayne@69:             self._find_name_single_package_or_module()
jpayne@69:             or self._find_name_from_packages()
jpayne@69:         )
jpayne@69:         if name:
jpayne@69:             self.dist.metadata.name = name
jpayne@69: 
jpayne@69:     def _find_name_single_package_or_module(self) -> str | None:
jpayne@69:         """Exactly one module or package"""
jpayne@69:         for field in ('packages', 'py_modules'):
jpayne@69:             items = getattr(self.dist, field, None) or []
jpayne@69:             if items and len(items) == 1:
jpayne@69:                 log.debug(f"Single module/package detected, name: {items[0]}")
jpayne@69:                 return items[0]
jpayne@69: 
jpayne@69:         return None
jpayne@69: 
jpayne@69:     def _find_name_from_packages(self) -> str | None:
jpayne@69:         """Try to find the root package that is not a PEP 420 namespace"""
jpayne@69:         if not self.dist.packages:
jpayne@69:             return None
jpayne@69: 
jpayne@69:         packages = remove_stubs(sorted(self.dist.packages, key=len))
jpayne@69:         package_dir = self.dist.package_dir or {}
jpayne@69: 
jpayne@69:         parent_pkg = find_parent_package(packages, package_dir, self._root_dir)
jpayne@69:         if parent_pkg:
jpayne@69:             log.debug(f"Common parent package detected, name: {parent_pkg}")
jpayne@69:             return parent_pkg
jpayne@69: 
jpayne@69:         log.warn("No parent package detected, impossible to derive `name`")
jpayne@69:         return None
jpayne@69: 
jpayne@69: 
jpayne@69: def remove_nested_packages(packages: list[str]) -> list[str]:
jpayne@69:     """Remove nested packages from a list of packages.
jpayne@69: 
jpayne@69:     >>> remove_nested_packages(["a", "a.b1", "a.b2", "a.b1.c1"])
jpayne@69:     ['a']
jpayne@69:     >>> remove_nested_packages(["a", "b", "c.d", "c.d.e.f", "g.h", "a.a1"])
jpayne@69:     ['a', 'b', 'c.d', 'g.h']
jpayne@69:     """
jpayne@69:     pkgs = sorted(packages, key=len)
jpayne@69:     top_level = pkgs[:]
jpayne@69:     size = len(pkgs)
jpayne@69:     for i, name in enumerate(reversed(pkgs)):
jpayne@69:         if any(name.startswith(f"{other}.") for other in top_level):
jpayne@69:             top_level.pop(size - i - 1)
jpayne@69: 
jpayne@69:     return top_level
jpayne@69: 
jpayne@69: 
jpayne@69: def remove_stubs(packages: list[str]) -> list[str]:
jpayne@69:     """Remove type stubs (:pep:`561`) from a list of packages.
jpayne@69: 
jpayne@69:     >>> remove_stubs(["a", "a.b", "a-stubs", "a-stubs.b.c", "b", "c-stubs"])
jpayne@69:     ['a', 'a.b', 'b']
jpayne@69:     """
jpayne@69:     return [pkg for pkg in packages if not pkg.split(".")[0].endswith("-stubs")]
jpayne@69: 
jpayne@69: 
jpayne@69: def find_parent_package(
jpayne@69:     packages: list[str], package_dir: Mapping[str, str], root_dir: StrPath
jpayne@69: ) -> str | None:
jpayne@69:     """Find the parent package that is not a namespace."""
jpayne@69:     packages = sorted(packages, key=len)
jpayne@69:     common_ancestors = []
jpayne@69:     for i, name in enumerate(packages):
jpayne@69:         if not all(n.startswith(f"{name}.") for n in packages[i + 1 :]):
jpayne@69:             # Since packages are sorted by length, this condition is able
jpayne@69:             # to find a list of all common ancestors.
jpayne@69:             # When there is divergence (e.g. multiple root packages)
jpayne@69:             # the list will be empty
jpayne@69:             break
jpayne@69:         common_ancestors.append(name)
jpayne@69: 
jpayne@69:     for name in common_ancestors:
jpayne@69:         pkg_path = find_package_path(name, package_dir, root_dir)
jpayne@69:         init = os.path.join(pkg_path, "__init__.py")
jpayne@69:         if os.path.isfile(init):
jpayne@69:             return name
jpayne@69: 
jpayne@69:     return None
jpayne@69: 
jpayne@69: 
jpayne@69: def find_package_path(
jpayne@69:     name: str, package_dir: Mapping[str, str], root_dir: StrPath
jpayne@69: ) -> str:
jpayne@69:     """Given a package name, return the path where it should be found on
jpayne@69:     disk, considering the ``package_dir`` option.
jpayne@69: 
jpayne@69:     >>> path = find_package_path("my.pkg", {"": "root/is/nested"}, ".")
jpayne@69:     >>> path.replace(os.sep, "/")
jpayne@69:     './root/is/nested/my/pkg'
jpayne@69: 
jpayne@69:     >>> path = find_package_path("my.pkg", {"my": "root/is/nested"}, ".")
jpayne@69:     >>> path.replace(os.sep, "/")
jpayne@69:     './root/is/nested/pkg'
jpayne@69: 
jpayne@69:     >>> path = find_package_path("my.pkg", {"my.pkg": "root/is/nested"}, ".")
jpayne@69:     >>> path.replace(os.sep, "/")
jpayne@69:     './root/is/nested'
jpayne@69: 
jpayne@69:     >>> path = find_package_path("other.pkg", {"my.pkg": "root/is/nested"}, ".")
jpayne@69:     >>> path.replace(os.sep, "/")
jpayne@69:     './other/pkg'
jpayne@69:     """
jpayne@69:     parts = name.split(".")
jpayne@69:     for i in range(len(parts), 0, -1):
jpayne@69:         # Look backwards, the most specific package_dir first
jpayne@69:         partial_name = ".".join(parts[:i])
jpayne@69:         if partial_name in package_dir:
jpayne@69:             parent = package_dir[partial_name]
jpayne@69:             return os.path.join(root_dir, parent, *parts[i:])
jpayne@69: 
jpayne@69:     parent = package_dir.get("") or ""
jpayne@69:     return os.path.join(root_dir, *parent.split("/"), *parts)
jpayne@69: 
jpayne@69: 
jpayne@69: def construct_package_dir(packages: list[str], package_path: StrPath) -> dict[str, str]:
jpayne@69:     parent_pkgs = remove_nested_packages(packages)
jpayne@69:     prefix = Path(package_path).parts
jpayne@69:     return {pkg: "/".join([*prefix, *pkg.split(".")]) for pkg in parent_pkgs}