Byte by byte directory comparison ignoring folder structures and file name differences

Question

I haven't been able to find an existing tool that does this, so I'm attempting to create one. If anyone knows of one that already exists, I'd appreciate a pointer to it. I plan on using this primarily for cleaning up old backup copies and was hoping for a review of its correctness or suggestions for improvement. Part of my concern is whether or not filecmp.cmp(), as I've used it here with the third argument set to False, does a full byte by byte comparison. I'm also providing it here in the hope that someone else might find it useful. I have run it on Ubuntu 12.04 LTS with Python 2.7.3.

# Prints a list of paths to files that exist in dir_l but not dir_r. File name 
# differences are ignored. Recursively scans subdirectories. Skips hidden files 
# and folders by default. Files of the same size are compared byte by byte (?).
# Differences in folder structures are ignored. For example, if 
# dir_l/subdir1/file1 and dir_r/subdir2/subdir3/file2 match byte for byte, 
# then dir_l/subdir1/file1 exists in dir_r.

# Two primary data structures are used:
# (1) A list of all the paths to files in dir_l (recursively including 
# subdirectories of dir_l and excluding hidden files and folders by default).
# (2) A hash mapping each unique file size in dir_r to a list of all the paths 
# to files in dir_r of that size (recursively including subdirectories of dir_r 
# and excluding hidden files and folders by default).

# For each file pointed to in (1), its size is checked for existence in (2). 
# If its size does not exist in (2), the file path to it is stored as 
# unmatched. If its size does exist in (2), a byte by byte comparison (?) is 
# done between it and each file matching its size in (2) until a match is 
# found, if any. If a match is not found, the file path to it is stored as 
# unmatched. The stored list of unmatched file paths, if any, is then printed.

# Requires the progress bar library (2.2)
# https://pypi.python.org/pypi/progressbar/2.2
# http://code.google.com/p/python-progressbar/


import sys
import os
import filecmp
import argparse

from progressbar import *


def main():
    help_description = \
    'Prints a list of paths to files that exist in dir_l but not dir_r. File \
name differences are ignored. Recursively scans subdirectories. Skips hidden \
files and folders by default. Files of the same size are compared \
byte by byte (?). Differences in folder structures are ignored. For example, \
if dir_l/subdir1/file1 and dir_r/subdir2/subdir3/file2 match byte for byte, \
then dir_l/subdir1/file1 exists in dir_r.'

    parser = argparse.ArgumentParser(description = help_description)

    parser.add_argument('-a', '--all', action='store_true', help='do not skip \
    hidden files and folders')
    parser.add_argument('dir_l')
    parser.add_argument('dir_r')

    args = vars(parser.parse_args())

    include_hidden = args['all']

    dir_l = args['dir_l']
    dir_r = args['dir_r']

    if not os.path.isdir(dir_l):
        print "Invalid directory path: " + dir_l
        sys.exit(2)

    if not os.path.isdir(dir_r):
        print "Invalid directory path: " + dir_r
        sys.exit(2)


    print "Preprocessing..."

    # creates (1)

    # (1)
    filepaths_l = get_dir_file_paths(dir_l, include_hidden);


    # creates (2)

    filepaths_r = get_dir_file_paths(dir_r, include_hidden);

    # (2)
    size_to_filepaths_r = dict()

    for filepath in filepaths_r:
        size = os.path.getsize(filepath)

        if size in size_to_filepaths_r:
            # adds this path to the existing list of paths to files in dir_r of this 
            # size
            size_to_filepaths_r[size].append(filepath)
        else:
            # starts a new list of paths to files in dir_r of this size
            size_to_filepaths_r[size] = [filepath]

    del filepaths_r


    # compares the files

    print "Comparing files..."

    # will hold a list of all the paths to files in dir_l that do not exist in 
    # dir_r
    unmatched = []

    # creates a progress bar
    pbar = ProgressBar(widgets=[Percentage(), Bar()], maxval=len(filepaths_l))
    pbar.start()
    # counter for the progress bar
    i = 0
    for filepath_l in filepaths_l:
        match = False
        # gets the size of the file pointed to by filepath_l
        size = os.path.getsize(filepath_l)
        if size in size_to_filepaths_r:
            # each of the files pointed to in the list of file paths stored in 
            # size_to_filepaths_r[size] is the same size as the file pointed to by 
            # filepath_l
            for filepath_r in size_to_filepaths_r[size]: 
                # compares the files byte by byte (?)
                if filecmp.cmp(filepath_l, filepath_r, False): 
                    match = True
                    # found a match, no need to check the rest of the files in the list,
                    # if any
                    break
        if match == False:
            # either no files in dir_r exist that are the same size as the file 
            # pointed to by filepath_l, or none of those that do are a 
            # byte by byte (?) match
            unmatched.append(filepath_l)
        i = i + 1
        pbar.update(i)
    pbar.finish()


    # prints the paths to any unmatched files
    if not unmatched:
        print "No unmatched files"
    else:
        print "Unmatched files:"
        for filepath in unmatched:
            print filepath


# Returns a list of all the paths to files in the directory pointed to by 'top', 
# recursively including subdirectories. Hidden files and folders are ignored 
# unless 'include_hidden' is set to True.
def get_dir_file_paths(top, include_hidden):
    filepaths = []

    for dirpath, dirnames, filenames in os.walk(top):
        if not include_hidden:
            # ignore hidden files and folders
            # http://stackoverflow.com/questions/13454164/os-walk-without-hidden-folders
            # Answer by Martijn Pieters
            filenames = [f for f in filenames if not f[0] == '.']
            dirnames[:] = [d for d in dirnames if not d[0] == '.']

        for filename in filenames:
            filepath = os.path.join(dirpath, filename)
            filepaths.append(filepath)

    return filepaths


main()

Code updated to use suggestions by Janne Karila:

# Two primary data structures are created:

# (1) A list of tuples. Each tuple contains a pair of items: a file size and a 
# file path. The file size is the size of the file pointed to by the file path. 
# The list is sorted on the file sizes. The set of file paths consists of all 
# the paths to the files in directory_l (recursively including subdirectories 
# of directory_l and excluding hidden files and folders by default).

# For example:
# [(file_size_1, file_path_1), (file_size_2, file_path_2), ..., 
# (file_size_n, file_path_n)]

# file_size_1 = size of the file pointed to by file_path_1, 
# file_size_2 = size of the file pointed to by file_path_2, ..., 
# file_size_n = size of the file pointed to by file_path_n

# file_size_1 <= file_size_2 <= ... <= file_size_n

# file_path_1, file_path_2, ..., file_path_n = all the paths to the files in 
# directory_l (recursively including subdirectories of directory_l and 
# excluding hidden files and folders by default)

# (2) A dictionary mapping each unique file size in directory_r to a list of 
# all the paths to files of that size in directory_r (recursively including 
# subdirectories of directory_r and excluding hidden files and folders by 
# default).


# For each file pointed to in (1), its size is checked for existence in (2). 
# If its size does not exist in (2), the file path to it is stored as 
# unmatched. If its size does exist in (2), a byte by byte comparison is done 
# between it and each file matching its size in (2) until a match is found, if 
# any. If a match is not found, the file path to it is stored as unmatched. The 
# stored list of unmatched file paths, if any, is then printed.


# Uses suggestions by msvalkon and Janne Karila in Stack Exchange Code Review:
# http://codereview.stackexchange.com/questions/41853/byte-by-byte-directory-comparison-ignoring-folder-structures-and-file-name-diffe


# Requires the progress bar library (2.2)
# https://pypi.python.org/pypi/progressbar/2.2
# http://code.google.com/p/python-progressbar/


import argparse
import collections
import filecmp
import os
import sys

from operator import itemgetter
from progressbar import Bar, Percentage, ProgressBar


def main():
    help_description = \
    'Prints a list of the paths to the files that exist in the directory pointed \
to by directory_l, but that do not exist in the directory pointed to by \
directory_r. File name differences are ignored. Recursively scans \
subdirectories of directory_l and directory_r. Skips hidden files and folders \
by default. Files of the same size are compared byte by byte. Differences in \
directory structures are ignored. For example, if \
directory_l/subdirectory_1/file_name_1 and \
directory_r/subdirectory_2/subdirectory_3/file_name_2 match byte for byte, \
then directory_l/subdirectory_1/file_name_1 exists in directory_r.'

    parser = argparse.ArgumentParser(description = help_description)

    parser.add_argument('-a', '--all', action='store_true', help='include hidden \
files and folders')
    parser.add_argument('directory_l', help='path to a directory of files to \
search for')
    parser.add_argument('directory_r', help='path to a directory of files to \
search in')

    args = vars(parser.parse_args())

    include_hidden = args['all']

    directory_l = args['directory_l']
    directory_r = args['directory_r']

    if not os.path.isdir(directory_l):
        print "Invalid directory path: " + directory_l
        sys.exit(2)

    if not os.path.isdir(directory_r):
        print "Invalid directory path: " + directory_r
        sys.exit(2)

    unmatched = find_unmatched(directory_l, directory_r, include_hidden)

    # Prints the paths to any unmatched files.
    if not unmatched:
        print "No unmatched files."
    else:
        print "Unmatched files:"
        for file_path in unmatched:
            print file_path


def find_unmatched(directory_l, directory_r, include_hidden):
    print "Preprocessing..."

    # Creates (1)

    size_file_path_tuple_list_l = sizes_paths(directory_l, include_hidden)
    # Sorts the list by the first item in each tuple pair (size).
    size_file_path_tuple_list_l_sorted = sorted(size_file_path_tuple_list_l, \
key=itemgetter(1)) # (1)


    # Creates (2)

    size_file_path_tuple_list_r = sizes_paths(directory_r, include_hidden)
    size_to_file_path_list_dict_r = \
dict_of_lists(size_file_path_tuple_list_r) # (2)


    # Compares the files

    print "Comparing files..."

    unmatched = []

    # Creates a progress bar
    pbar = ProgressBar(widgets=[Percentage(), Bar()], \
maxval=len(size_file_path_tuple_list_l_sorted))
    pbar.start()

    for i, (size_l, file_path_l) in enumerate(size_file_path_tuple_list_l_sorted):
        # size_to_file_path_list_dict_r[size_l] is a list of the paths to the files
        # in directory_r (recursively including subdirectories of directory_r and 
        # excluding hidden files and folders by default) that are the same size as 
        # the file pointed to by file_path_1.

        # Note that in the statement 'size_to_file_path_list_dict_r[size_l]', if 
        # size_l does not exist as a key in size_to_file_path_list_dict_r, then 
        # size_l is added as a key that maps to an empty list.
        if not file_match(file_path_l, size_to_file_path_list_dict_r[size_l]):
            # Either no files in directory_r (recursively including subdirectories of 
            # directory_r and excluding hidden files and folders by default) exist 
            # that are the same size as the file pointed to by file_path_l, or none 
            # of those that do are a byte by byte match.
            unmatched.append(file_path_l)

        pbar.update(i)

    pbar.finish()

    return unmatched


# Returns as tuple pairs the size of and path to each of the files in the 
# directory pointed to by 'top', recursively including subdirectories of 'top'. 
# Hidden files and folders are not returned unless 'include_hidden' is True.
def sizes_paths(top, include_hidden):
    for file_path in get_directory_file_paths(top, include_hidden):
        size = os.path.getsize(file_path)
        yield size, file_path


# Returns each of the paths to the files in the directory pointed to by 'top', 
# recursively including subdirectories of 'top'. Hidden files and folders are 
# not returned unless 'include_hidden' is True.
def get_directory_file_paths(top, include_hidden):
    for directory_path, folder_name_list, file_name_list in os.walk(top):
        # directory_path is the path to the current directory
        # folder_name_list is the list of all the folder names in the 
        # current directory
        # file_name_list is the list of the file names in the current directory
        if not include_hidden:
            # Ignore hidden files and folders
            # http://stackoverflow.com/questions/13454164/os-walk-without-hidden-folders
            # Answer by Martijn Pieters
            # Removes the file names that begin with '.' from the list of file names 
            # in the current directory.
            file_name_list = [f for f in file_name_list if not f[0] == '.']
            # Removes the folder names that begin with '.' from the list of folder 
            # names in the current directory.
            folder_name_list[:] = [f for f in folder_name_list if not f[0] == '.']

        for file_name in file_name_list:
            yield os.path.join(directory_path, file_name)


# Creates and returns a dictionary of lists from a list of tuple pairs. 
# The keys in the dictionary are the set of the unique first items from the 
# tuple pairs. Each of these keys is mapped to a list of all the second items 
# from the tuple pairs whose first item matches that key.
# Example:
# {'a': [1, 1], 'c': [1], 'b': [2, 3]} = 
# dict_of_lists([('a', 1), ('a', 1), ('b', 2), ('b', 3), ('c', 1)])
def dict_of_lists(item_list):
    # http://docs.python.org/2/library/collections.html#collections.defaultdict
    d = collections.defaultdict(list)
    for key, value in item_list:
        # If d[key] does not exist, an empty list is created and value is attached 
        # to it. Otherwise, if d[key] does exist, value is appended to it.
        d[key].append(value)
    return d


# Returns True if and only if any of the files pointed to by the file paths in 
# file_path_list_r are a byte by byte match for the file pointed to by 
# file_path_l.
# Note that file_path_list_r may be an empty list.
def file_match(file_path_l, file_path_list_r):
    return any(filecmp.cmp(file_path_l, file_path_r, False) \
for file_path_r in file_path_list_r)


main()

Answer 1

• Yes, filecmp.cmp compares the contents of the files with shallow=False
• Breaking main into more functions still gives better structure
• Making get_dir_file_paths a generator reduces memory use when building size_to_filepaths_r, and simplifies the function itself slightly.
• Use collections.defaultdict(list) to avoid if size in size_to_filepaths_r checks.
• Use enumerate to keep a loop counter
• Get the file sizes while walking the directories to benefit from disk caching.
• Compare all files of the same size consecutively for the same reason. (the code below sorts filepaths_l for that)

I propose to rearrange the bulk of the work into these functions:

import collections

def dict_of_lists(items):
    d = collections.defaultdict(list)
    for key, value in items:
        d[key].append(value)
    return d

def get_dir_file_paths(top, include_hidden):
    for dirpath, dirnames, filenames in os.walk(top):
        if not include_hidden:
            # ignore hidden files and folders
            # http://stackoverflow.com/questions/13454164/os-walk-without-hidden-folders
            # Answer by Martijn Pieters
            filenames = [f for f in filenames if not f[0] == '.']
            dirnames[:] = [d for d in dirnames if not d[0] == '.']

        for filename in filenames:
            yield os.path.join(dirpath, filename)

def sizes_paths(top, include_hidden):
    for filepath in get_dir_file_paths(top, include_hidden):
        size = os.path.getsize(filepath)
        yield size, filepath

def file_match(filepath_l, filepaths_r):
    return any(filecmp.cmp(filepath_l, filepath_r, False) 
               for filepath_r in filepaths_r)

def find_unmatched(dir_l, dir_r, include_hidden):

    filepaths_l = sorted(sizes_paths(dir_l, include_hidden))
    size_to_filepaths_r = dict_of_lists(sizes_paths(dir_r, include_hidden))

    # creates a progress bar
    pbar = ProgressBar(widgets=[Percentage(), Bar()], maxval=len(filepaths_l))
    pbar.start()

    unmatched = []

    for i, (size, filepath_l) in enumerate(filepaths_l):
        if not file_match(filepath_l, size_to_filepaths_r[size]):
            # either no files in dir_r exist that are the same size as the file 
            # pointed to by filepath_l, or none of those that do are a 
            # byte by byte match
            unmatched.append(filepath_l)
        pbar.update(i)
    pbar.finish()

    return unmatched