Recursively scan a list of directories, looking for duplicate files.

    `exclude_dirs`, if provided, should be a list of glob patterns.
    Subdirectories whose names match these patterns are excluded from the
    scan.

    `exclude_files`, if provided, should be a list of glob patterns. Files
    whose names match these patterns are excluded from the scan.

    ``follow_dirlinks`` controls whether to follow symbolic links to
    subdirectories while crawling.

    Returns a 2-tuple of two values: ``(duplicate_groups, errors)``.

    `duplicate_groups` is a (possibly empty) list of lists: the names of files
    that have at least two copies, grouped together.

    `errors` is a list of error messages that occurred. If empty, there were no
    errors.

    For example, assuming ``./a1`` and ``/dir1/a2`` are identical,
    ``/dir1/c1`` and ``/dir2/c2`` are identical, ``/dir2/b`` is different
    from all others, that any subdirectories called ``tmp`` should not
    be scanned, and that files ending in ``.bak`` should be ignored:

      >>> dups, errs = find_duplicates_in_dirs(['.', '/dir1', '/dir2'], ['tmp'], ['*.bak'])
      >>> dups
      [['./a1', '/dir1/a2'], ['/dir1/c1', '/dir2/c2']]
      >>> errs
      []

def find_duplicates_in_dirs(directories, exclude_dirs=None, exclude_files=None,
        follow_dirlinks=False):
    """Recursively scan a list of directories, looking for duplicate files.

    `exclude_dirs`, if provided, should be a list of glob patterns.
    Subdirectories whose names match these patterns are excluded from the
    scan.

    `exclude_files`, if provided, should be a list of glob patterns. Files
    whose names match these patterns are excluded from the scan.

    ``follow_dirlinks`` controls whether to follow symbolic links to
    subdirectories while crawling.

    Returns a 2-tuple of two values: ``(duplicate_groups, errors)``.

    `duplicate_groups` is a (possibly empty) list of lists: the names of files
    that have at least two copies, grouped together.

    `errors` is a list of error messages that occurred. If empty, there were no
    errors.

    For example, assuming ``./a1`` and ``/dir1/a2`` are identical,
    ``/dir1/c1`` and ``/dir2/c2`` are identical, ``/dir2/b`` is different
    from all others, that any subdirectories called ``tmp`` should not
    be scanned, and that files ending in ``.bak`` should be ignored:

      >>> dups, errs = find_duplicates_in_dirs(['.', '/dir1', '/dir2'], ['tmp'], ['*.bak'])
      >>> dups
      [['./a1', '/dir1/a2'], ['/dir1/c1', '/dir2/c2']]
      >>> errs
      []

    """
    if exclude_dirs is None:
        exclude_dirs = []

    if exclude_files is None:
        exclude_files = []

    errors_in_total = []
    files_by_size = {}

    # First, group all files by size
    for directory in directories:
        sub_errors = index_files_by_size(directory, files_by_size, exclude_dirs,
                                         exclude_files, follow_dirlinks)
        errors_in_total += sub_errors

    all_duplicates = []

    # Now, within each file size, check for duplicates.
    #
    # We use an iterator over the dict (which gives us the keys), instead
    # of explicitly accessing dict.keys(). On Python 2, dict.keys() returns
    # a list copy of the keys, which may be very large.
    for size in iter(files_by_size):
        # for large file sizes, divide them further into groups by matching
        # initial portion; how much of the file is used to match depends on
        # the file size
        if size >= PARTIAL_MD5_THRESHOLD:
            partial_size = min(round_up_to_mult(size // PARTIAL_MD5_READ_RATIO,
                                                PARTIAL_MD5_READ_MULT),
                               PARTIAL_MD5_MAX_READ)

            possible_duplicates_list, sub_errors = find_duplicates(files_by_size[size], partial_size)
            errors_in_total += sub_errors
        else:
            # small file size, group them all together and do full MD5s
            possible_duplicates_list = [files_by_size[size]]


        # Do full MD5 scan on suspected duplicates. calculate_md5 (and
        # therefore find_duplicates) needs to know how many bytes to scan.
        # We're using the file's size, as per stat(); this is a problem if
        # the file is growing. We'll only scan up to the size the file had
        # when we indexed. Would be better to somehow tell calculate_md5 to
        # scan until EOF (e.g. give it a negative size).
        for possible_duplicates in possible_duplicates_list:
            duplicates, sub_errors = find_duplicates(possible_duplicates, size)
            all_duplicates += duplicates
            errors_in_total += sub_errors

    return all_duplicates, errors_in_total