def get_matching_files(dirname, exclude_matchers=()):
    # type: (unicode, Tuple[Callable[[unicode], bool], ...]) -> Iterable[unicode]
    """Get all file names in a directory, recursively.

    Exclude files and dirs matching some matcher in *exclude_matchers*.
    """
    # dirname is a normalized absolute path.
    dirname = path.normpath(path.abspath(dirname))
    dirlen = len(dirname) + 1    # exclude final os.path.sep

    for root, dirs, files in walk(dirname, followlinks=True):
        relativeroot = root[dirlen:]

        qdirs = enumerate(path_stabilize(path.join(relativeroot, dn))
                          for dn in dirs)  # type: Iterable[Tuple[int, unicode]]
        qfiles = enumerate(path_stabilize(path.join(relativeroot, fn))
                           for fn in files)  # type: Iterable[Tuple[int, unicode]]
        for matcher in exclude_matchers:
            qdirs = [entry for entry in qdirs if not matcher(entry[1])]
            qfiles = [entry for entry in qfiles if not matcher(entry[1])]

        dirs[:] = sorted(dirs[i] for (i, _) in qdirs)

        for i, filename in sorted(qfiles):
            yield filename

def get_matching_files(dirname, exclude_matchers=()):
    """
    Get all file names in a directory, recursively.

    Exclude files and dirs matching some matcher in *exclude_matchers*.
    """
    # dirname is a normalized absolute path.
    dirname = path.normpath(path.abspath(dirname))
    dirlen = len(dirname) + 1    # exclude final os.path.sep

    for root, dirs, files in walk(dirname, followlinks=True):
        relativeroot = root[dirlen:]

        qdirs = enumerate(path.join(relativeroot, dn).replace(os.path.sep, SEP)
                          for dn in dirs)
        qfiles = enumerate(path.join(relativeroot, fn).replace(os.path.sep, SEP)
                           for fn in files)
        for matcher in exclude_matchers:
            qdirs = [entry for entry in qdirs if not matcher(entry[1])]
            qfiles = [entry for entry in qfiles if not matcher(entry[1])]

        dirs[:] = sorted(dirs[i] for (i, _) in qdirs)

        for i, filename in sorted(qfiles):
            yield filename

def copy_asset(source, destination, excluded=lambda path: False, context=None, renderer=None):
    """Copy asset files to destination recursively.

    On copying, it expands the template variables if context argument is given and
    the asset is a template file.

    :param source: The path to source file or directory
    :param destination: The path to destination directory
    :param excluded: The matcher to determine the given path should be copied or not
    :param context: The template variables.  If not given, template files are simply copied
    :param renderer: The template engine.  If not given, SphinxRenderer is used by default
    """
    if not os.path.exists(source):
        return

    ensuredir(destination)
    if os.path.isfile(source):
        copy_asset_file(source, destination, context, renderer)
        return

    for root, dirs, files in walk(source):
        reldir = relative_path(source, root)
        for dir in dirs[:]:
            if excluded(posixpath.join(reldir, dir)):
                dirs.remove(dir)
            else:
                ensuredir(posixpath.join(destination, reldir, dir))

        for filename in files:
            if not excluded(posixpath.join(reldir, filename)):
                copy_asset_file(posixpath.join(root, filename),
                                posixpath.join(destination, reldir),
                                context, renderer)

def recurse_tree(rootpath, excludes, followlinks, includeprivate,
                 separatemodules, noheadings, destdir, dryrun, force, suffix):
    """
    Look for every file in the directory tree and create the corresponding
    ReST files.
    """
    # check if the base directory is a package and get its name
    if INITPY in os.listdir(rootpath):
        root_package = rootpath.split(path.sep)[-1]
    else:
        # otherwise, the base is a directory with packages
        root_package = None

    toplevels = []
    for root, subs, files in walk(rootpath, followlinks=followlinks):
        # document only Python module files (that aren't excluded)
        py_files = sorted(f for f in files
                          if path.splitext(f)[1] in PY_SUFFIXES and
                          not is_excluded(path.join(root, f), excludes))
        is_pkg = INITPY in py_files
        if is_pkg:
            py_files.remove(INITPY)
            py_files.insert(0, INITPY)
        elif root != rootpath:
            # only accept non-package at toplevel
            del subs[:]
            continue
        # remove hidden ('.') and private ('_') directories, as well as
        # excluded dirs
        if includeprivate:
            exclude_prefixes = ('.',)
        else:
            exclude_prefixes = ('.', '_')
        subs[:] = sorted(sub for sub in subs if not sub.startswith(
                exclude_prefixes)
                         and not is_excluded(path.join(root, sub), excludes))

        if is_pkg:
            # we are in a package with something to document
            if subs or len(py_files) > 1 or not \
                    shall_skip(path.join(root, INITPY), includeprivate):
                subpackage = root[len(rootpath):].lstrip(path.sep).\
                    replace(path.sep, '.')
                create_package_file(root, root_package, subpackage,
                                    py_files, separatemodules, noheadings,
                                    includeprivate, destdir, dryrun, force,
                                    suffix, subs)
                toplevels.append(makename(root_package, subpackage))
        else:
            # if we are at the root level, we don't require it to be a package
            assert root == rootpath and root_package is None
            for py_file in py_files:
                if not shall_skip(path.join(rootpath, py_file),
                                  includeprivate):
                    module = path.splitext(py_file)[0]
                    create_module_file(root_package, module, noheadings,
                                       destdir, dryrun, force, suffix)
                    toplevels.append(module)

    return toplevels

def pkgname_modules_subpkgs(rootpath, excluded, opts):
    """A generator that filters out the packages and modules as desired and 
    yields tuples of (package name, modules, subpackages).  
    """
    for root, dirs, files in walk(rootpath, followlinks=opts.followlinks):
        if root in excluded:
            del dirs[:] # skip all subdirectories as well
            continue
        if INITPY not in files:
            if root != rootpath:
                del dirs[:]
            continue
        pkg_name = root[len(rootpath):].lstrip(os.sep).replace(os.sep, '.')
        if not opts.includeprivate and pkg_name.startswith('_'):
            del dirs[:]
            continue
        modules = get_modules(files, excluded, opts, root)
        subpkgs = get_subpkgs(dirs,  excluded, opts, root, rootpath)
        dirs[:] = subpkgs # visit only subpackages
        has_sg_to_doc = True 
        if opts.respect_all:
            all_attr, has_docstr = get_all_attr_has_docstr(rootpath, root, opts)
            has_sg_to_doc = has_docstr or bool(all_attr)
            # has_sg_to_doc: e.g. multiprocessing.dummy has nonempty __all__ but 
            # no modules, subpkgs or docstring to document -> still document it!                   
            modules = get_only_modules(all_attr, modules)
        if modules or subpkgs or has_sg_to_doc:
                yield pkg_name, modules, subpkgs

def find_catalog_source_files(locale_dirs, locale, domains=None, gettext_compact=False,
                              charset='utf-8', force_all=False,
                              excluded=Matcher([])):
    # type: (List[unicode], unicode, List[unicode], bool, unicode, bool, Matcher) -> Set[CatalogInfo]  # NOQA
    """
    :param list locale_dirs:
       list of path as `['locale_dir1', 'locale_dir2', ...]` to find
       translation catalogs. Each path contains a structure such as
       `<locale>/LC_MESSAGES/domain.po`.
    :param str locale: a language as `'en'`
    :param list domains: list of domain names to get. If empty list or None
       is specified, get all domain names. default is None.
    :param boolean gettext_compact:
       * False: keep domains directory structure (default).
       * True: domains in the sub directory will be merged into 1 file.
    :param boolean force_all:
       Set True if you want to get all catalogs rather than updated catalogs.
       default is False.
    :return: [CatalogInfo(), ...]
    """
    catalogs = set()  # type: Set[CatalogInfo]

    if not locale:
        return catalogs  # locale is not specified

    for locale_dir in locale_dirs:
        if not locale_dir:
            continue  # skip system locale directory

        base_dir = path.join(locale_dir, locale, 'LC_MESSAGES')

        if not path.exists(base_dir):
            continue  # locale path is not found

        for dirpath, dirnames, filenames in walk(base_dir, followlinks=True):
            filenames = [f for f in filenames if f.endswith('.po')]
            for filename in filenames:
                if excluded(path.join(relpath(dirpath, base_dir), filename)):
                    continue
                base = path.splitext(filename)[0]
                domain = relpath(path.join(dirpath, base), base_dir)
                if gettext_compact and path.sep in domain:
                    domain = path.split(domain)[0]
                domain = domain.replace(path.sep, SEP)
                if domains and domain not in domains:
                    continue
                cat = CatalogInfo(base_dir, domain, charset)
                if force_all or cat.is_outdated():
                    catalogs.add(cat)

    return catalogs

def copy_asset(source, destination, excluded=lambda path: False, context=None, renderer=None):
    # type: (unicode, unicode, Union[Callable[[unicode], bool], Matcher], Dict, BaseRenderer) -> None  # NOQA
    """Copy asset files to destination recursively.

    On copying, it expands the template variables if context argument is given and
    the asset is a template file.

    :param source: The path to source file or directory
    :param destination: The path to destination directory
    :param excluded: The matcher to determine the given path should be copied or not
    :param context: The template variables.  If not given, template files are simply copied
    :param renderer: The template engine.  If not given, SphinxRenderer is used by default
    """
    if not os.path.exists(source):
        return

    if renderer is None:
        from sphinx.util.template import SphinxRenderer
        renderer = SphinxRenderer()

    ensuredir(destination)
    if os.path.isfile(source):
        copy_asset_file(source, destination, context, renderer)
        return

    for root, dirs, files in walk(source, followlinks=True):
        reldir = relative_path(source, root)
        for dir in dirs[:]:
            if excluded(posixpath.join(reldir, dir)):
                dirs.remove(dir)
            else:
                ensuredir(posixpath.join(destination, reldir, dir))

        for filename in files:
            if not excluded(posixpath.join(reldir, filename)):
                copy_asset_file(posixpath.join(root, filename),
                                posixpath.join(destination, reldir),
                                context, renderer)

def get_catalogs(locale_dirs, locale, gettext_compact=False, force_all=False):
    """
    :param list locale_dirs:
       list of path as `['locale_dir1', 'locale_dir2', ...]` to find
       translation catalogs. Each path contains a structure such as
       `<locale>/LC_MESSAGES/domain.po`.
    :param str locale: a language as `'en'`
    :param boolean gettext_compact:
       * False: keep domains directory structure (default).
       * True: domains in the sub directory will be merged into 1 file.
    :param boolean force_all:
       Set True if you want to get all catalogs rather than updated catalogs.
       default is False.
    :return: [CatalogInfo(), ...]
    """
    if not locale:
        return []  # locale is not specified

    catalogs = set()
    for locale_dir in locale_dirs:
        base_dir = path.join(locale_dir, locale, 'LC_MESSAGES')

        if not path.exists(base_dir):
            continue  # locale path is not found

        for dirpath, dirnames, filenames in walk(base_dir, followlinks=True):
            filenames = [f for f in filenames if f.endswith('.po')]
            for filename in filenames:
                base = path.splitext(filename)[0]
                domain = path.relpath(path.join(dirpath, base), base_dir)
                if gettext_compact and path.sep in domain:
                    domain = path.split(domain)[0]
                cat = CatalogInfo(base_dir, domain)
                if force_all or cat.is_outdated():
                    catalogs.add(cat)

    return catalogs

def recurse_tree(rootpath, excludes, opts):
    # type: (unicode, List[unicode], Any) -> List[unicode]
    """
    Look for every file in the directory tree and create the corresponding
    ReST files.
    """
    followlinks = getattr(opts, 'followlinks', False)
    includeprivate = getattr(opts, 'includeprivate', False)
    implicit_namespaces = getattr(opts, 'implicit_namespaces', False)

    # check if the base directory is a package and get its name
    if INITPY in os.listdir(rootpath) or implicit_namespaces:
        root_package = rootpath.split(path.sep)[-1]
    else:
        # otherwise, the base is a directory with packages
        root_package = None

    toplevels = []
    for root, subs, files in walk(rootpath, followlinks=followlinks):
        # document only Python module files (that aren't excluded)
        py_files = sorted(f for f in files
                          if path.splitext(f)[1] in PY_SUFFIXES and
                          not is_excluded(path.join(root, f), excludes))
        is_pkg = INITPY in py_files
        is_namespace = INITPY not in py_files and implicit_namespaces
        if is_pkg:
            py_files.remove(INITPY)
            py_files.insert(0, INITPY)
        elif root != rootpath:
            # only accept non-package at toplevel unless using implicit namespaces
            if not implicit_namespaces:
                del subs[:]
                continue
        # remove hidden ('.') and private ('_') directories, as well as
        # excluded dirs
        if includeprivate:
            exclude_prefixes = ('.',)  # type: Tuple[unicode, ...]
        else:
            exclude_prefixes = ('.', '_')
        subs[:] = sorted(sub for sub in subs if not sub.startswith(exclude_prefixes) and
                         not is_excluded(path.join(root, sub), excludes))

        if is_pkg or is_namespace:
            # we are in a package with something to document
            if subs or len(py_files) > 1 or not shall_skip(path.join(root, INITPY), opts):
                subpackage = root[len(rootpath):].lstrip(path.sep).\
                    replace(path.sep, '.')
                # if this is not a namespace or
                # a namespace and there is something there to document
                if not is_namespace or len(py_files) > 0:
                    create_package_file(root, root_package, subpackage,
                                        py_files, opts, subs, is_namespace)
                    toplevels.append(makename(root_package, subpackage))
        else:
            # if we are at the root level, we don't require it to be a package
            assert root == rootpath and root_package is None
            for py_file in py_files:
                if not shall_skip(path.join(rootpath, py_file), opts):
                    module = path.splitext(py_file)[0]
                    create_module_file(root_package, module, opts)
                    toplevels.append(module)

    return toplevels

def recurse_tree(app, env, src, dest, excludes, followlinks, force, dryrun, private, suffix):
    """Look for every file in the directory tree and create the corresponding
    ReST files.

    :param app: the sphinx app
    :type app: :class:`sphinx.application.Sphinx`
    :param env: the jinja environment
    :type env: :class:`jinja2.Environment`
    :param src: the path to the python source files
    :type src: :class:`str`
    :param dest: the output directory
    :type dest: :class:`str`
    :param excludes: the paths to exclude
    :type excludes: :class:`list`
    :param followlinks: follow symbolic links
    :type followlinks: :class:`bool`
    :param force: overwrite existing files
    :type force: :class:`bool`
    :param dryrun: do not generate files
    :type dryrun: :class:`bool`
    :param private: include "_private" modules
    :type private: :class:`bool`
    :param suffix: the file extension
    :type suffix: :class:`str`
    """
    # check if the base directory is a package and get its name
    if INITPY in os.listdir(src):
        root_package = src.split(os.path.sep)[-1]
    else:
        # otherwise, the base is a directory with packages
        root_package = None

    toplevels = []
    for root, subs, files in walk(src, followlinks=followlinks):
        # document only Python module files (that aren't excluded)
        py_files = sorted(f for f in files
                          if os.path.splitext(f)[1] in PY_SUFFIXES and
                          not is_excluded(os.path.join(root, f), excludes))
        is_pkg = INITPY in py_files
        if is_pkg:
            py_files.remove(INITPY)
            py_files.insert(0, INITPY)
        elif root != src:
            # only accept non-package at toplevel
            del subs[:]
            continue
        # remove hidden ('.') and private ('_') directories, as well as
        # excluded dirs
        if private:
            exclude_prefixes = ('.',)
        else:
            exclude_prefixes = ('.', '_')
        subs[:] = sorted(sub for sub in subs if not sub.startswith(exclude_prefixes) and not
                         is_excluded(os.path.join(root, sub), excludes))
        if is_pkg:
            # we are in a package with something to document
            if subs or len(py_files) > 1 or not \
               shall_skip(app, os.path.join(root, INITPY), private):
                subpackage = root[len(src):].lstrip(os.path.sep).\
                    replace(os.path.sep, '.')
                create_package_file(app, env, root_package, subpackage,
                                    private, dest, suffix, dryrun, force)
                toplevels.append(makename(root_package, subpackage))
        else:
            # if we are at the root level, we don't require it to be a package
            assert root == src and root_package is None
            for py_file in py_files:
                if not shall_skip(app, os.path.join(src, py_file), private):
                    module = os.path.splitext(py_file)[0]
                    create_module_file(app, env, root_package, module, dest, suffix, dryrun, force)
                    toplevels.append(module)
    return toplevels