3
\$\begingroup\$

Dilemma

The code below is in its infancy, but for now is an effort to crawl my entire file system and find duplicates whilst adhering to a variety of exclusion criteria. My current strategy for determining if two files are identical—comparing their checksums—seems unfeasible because it takes far too long to run (days, in fact).

Context (Optional Reading)

I have 6 drives in my machine from as early as 2008 to three months ago; collectively it's 7TB of storage that is littered in "Recovery" and "Stuff" directories; my computer-savvy has been steadily increasing since I was a kid, and now I'm a pro-am web-developer dabbling in real programming. Professionally I manage a cognitive psych laboratory that's has never thrown anything away, ever. Here I have still more TBs of data that is multiply redundant, and so I'm tentatively developing this to be worthy as an open source project.

Eventually, I want to:

  • find & remove redundant file/directory
  • programmatically 'tag' files (ie. the feature by the same name new to OS X as of 10.9)
  • develop an API for manipulating and organizing my files as per my whims, essentially

Probably some software has already been written that will do lots of what I want to do; this is much an exercise in writing software with a larger scope than the practical matter of achieving my ends.

Ideas & Progress

It occurs to me that their might be heuristical approaches that could cut down the workload—possibly I could only create checksums for files that have been inferred to be identical. The two criterion I can think of:

  • comparing filenames: Since many files are identical but for the filenames, this is only helpful if fallbacks exist to catch other cases

  • comparing filesize: It occurs to me that this might always work, ie. if two files have the same size only create & compare checksums between them

Also, often entire directories are identical, say two copies of CakePHP that each have a few thousand library files. Is there a way to establish if two directories are identical without comparing every file they contain? Sometimes I can imagine compressing a directory and then getting it's checksum would be useful, but how to establish which directories (ie. compressing whole volumes is obviously bonkers)?

Code

Most of this can be ignored; I've included my entire code here as a contextual courtesy but my question for the community primarily concerns the matter of identifying identical files or directories. Primarily one can pay attention to Manifest.fi_list_from_mfl() and the FileInspection class to see what I'm doing re: 'dilemma'.

import shutil
import time
import datetime
import pickle
import hashlib
import os, sys


def now(include_time=True):
    if include_time:
        return datetime.datetime.fromtimestamp(time.time()).strftime('%Y-%m-%d %H:%M:%S')
    else:
        return datetime.datetime.fromtimestamp(time.time()).strftime('%Y-%m-%d')

def path_dir_list(path):
    folders = []
    while True:
        path, folder = os.path.split(path)
        if folder != "":
            folders.insert(0, folder)
        else:
            if path != "": folders.insert(0, path)
            break
    return folders


def make_missing_dirs(path):
        try:
            try:
                os.makedirs(path)
            except AttributeError:
                os.makedirs(os.path.join(*path))
        except OSError:
            if type(path) is str: path = path_dir_list(path)
            for i in range(len(path)):
                try:
                    partial_path = os.path.join(*path[0:i] if i > 0 else path)
                    os.mkdir(partial_path, 0777)
                except OSError:
                    pass

def is_subpath(path, of_paths):
        if isinstance(of_paths, basestring): of_paths = [of_paths]
        abs_of_paths = [os.path.abspath(of_path) for of_path in of_paths]
        return any(os.path.abspath(path).startswith(subpath) for subpath in abs_of_paths)

DIR = "d"
FILE = "f"
LIST_MODE = 0
SAFE_BUILD_MODE = 1
OS_FILES = [".DS_Store", ".", "..", ".localized"]
FI_JAR_NAME = "file_jar.pkl"
MFL_NAME = "master_file_list.txt"
ORIGINAL_NAME = "original.txt"
LOG_NAME_STRING = "log_{0}.txt"


class FileInspection(object):
    json_template = '"{0}":{{"path":"{1}","hash":"{0}","filesize":"{2}","created": {3},"last_mod":"{4}", "has_duplicates":{5},"duplicates_moved":{6},"checked":{7}}}'
    is_original = False
    checked = False
    fetched = False
    hash = ''
    size = 0
    created = ''
    modified = ''

    def __init__(self, path):
        stats = os.stat(path)
        self.__path = path
        self.hash = self.hash_file()
        self.size = stats.st_size
        self.modified = stats.st_mtime
        self.created = stats.st_ctime

    def hash_file(self):
        read_size = 1048576 # I chose a 1MB, is this a good balance between performance and stability?
        checksum = hashlib.md5()
        with open(self.__path) as f:
            data = f.read(read_size)
            while data:
                checksum.update(data)
                data = f.read(read_size)
        return checksum.hexdigest()

    def log(self):
        json = self.json_template.format(self.__hash, self.__path, self.__size, self.__created, self.__last_mod, self.__has_duplicates,
            self.__fetched, self.__checked)
        return json.replace(":False", ":false").replace(":True",":true")


class Manifest(object):
    duplicates_path = ''    # where to put found duplicate files
    duplicates = {}         # references to FileInspections that were duplicates
    search_dir = ''         # the directory to crawl, eventually my whole file-system
    no_crawl_list = []      # directories not to crawl within the scope of search_dir 
    no_inspect_list = []    # file extensions to ignore when building FileInspections
    log_path = ''           # where the log file should go
    default_mfl_name = "master_file_list_{0}.txt"
    mfl_dir = ''            # path of the actual master file list
    mfl_path = None         # where the master file list should go
    fi_jar_path = None      # where the pickled FileInspections should go
    fi_jar = ''             # where pickling of FileInspections continues during runtime
    fi_store = []           # the set of FileInspection objects created by fi_list_from_mfl()
    mfl = None              # a reference to the master file list when it's open
    duplicate_size = 0      # cumulative size of files relocated because they were duplicates
    max_duplicate_space = 0 # moving files to a "Duplicates" directory until code is smart enough to trust with deletion
    count = 0
    dirs = 0
    files = 0
    os_files = 0
    mode = None             # not really implemented yet; you'll see it show up in a few places below but it's haphazard

    def __init__(self, search_dir="/", duplicates=None, mfl_dir=None, log_dir=None, autobuild=False, mode=LIST_MODE):
        self.search_dir = search_dir
        self.max_duplicate_space = 1073741824 * 50  # later will make this settable, for just hard-coded to the size of a partition I have set up

        #set the crawl mode
        self.mode = mode if mode in [LIST_MODE, FAST_BUILD_MODE, SAFE_BUILD_MODE, COPY_MODE] else self.SAFE_BUILD_MODE

        # ensure search path is a directory and set it
        if not os.path.isdir(search_dir): os.mkdir(search_dir)

        # ensure duplicates_dir is a directory and writeable
        self.duplicates_path = duplicates if duplicates else os.path.dirname(os.path.abspath(__file__))
        if not os.path.isdir(self.duplicates_path ): make_missing_dirs(self.duplicates_path )

        # ensure log_path is a directory or create it if needed
        if not os.path.isdir(log_dir): log_dir = self.duplicates_path
        self.log_path = os.path.join(log_dir, LOG_NAME_STRING.format(now(False)))
        self.log = open(self.log_path, "a") if self.mode == SAFE_BUILD_MODE  else open(self.log_path, "w+")

        # ensure master file list path is a directory or create it if needed
        self.mfl_dir = mfl_dir if mfl_dir else  os.path.dirname(os.path.abspath(__file__))
        self.mfl_path = os.path.join(mfl_dir, MFL_NAME)
        if not os.path.isdir(self.mfl_dir): make_missing_dirs(self.mfl_path)
        if os.path.isfile(self.mfl_path):
            self.mfl = open(self.mfl_path, "a") if self.mode == SAFE_BUILD_MODE else open(self.mfl_path, "w+")
        else:
            self.mfl = open(self.mfl_path, "w+")
            self.mfl.write('Master File List for DuplicatesFinder.py, created {0}\n'.format(now(True)))

        self.fi_jar_path = os.path.join(self.mfl_dir, FI_JAR_NAME)
        if os.path.isfile(self.fi_jar_path): self.load()

        #if autobuild is set, build the master file list
        if autobuild is True:
            self.__output("***Commencing autobuild....", False)
            self.build_master_file_list()
            self.fi_list_from_mfl()

    def __output(self, content, to_console=True, to_log=True):
            if to_console: print content
            if to_log: self.log.write(content + "\n")

    def build_master_file_list(self):
        self.__output("***Building master file list...")
        last_flush = 1
        for root, directories, files in os.walk(self.search_dir):
            files = [f for f in files if not f[0] == '.']
            directories[:] = [d for d in directories if not d[0] == '.']
            if self.files > last_flush * 1000:
                self.log.close()
                self.mfl.close()
                self.log = open(self.log_path, "a")
                self.mfl = open(self.mfl_path, "a")
                time.sleep(0.1)
                last_flush += 1
            for filename in files:
                filepath = os.path.join(root, filename)
                if not is_subpath(filepath, self.no_crawl_list):
                    self.files += 1
                    self.mfl.write(filepath + "\n")
                    self.__output("Added '{0}' to master_file_list.".format(filename))
        self.mfl.close()
        time.sleep(0.5)

    def do_not_inspect(self, no_inspect_list):
        self.no_inspect_list = [no_inspect_list] if type(no_inspect_list) is str else no_inspect_list

    def do_not_crawl(self, no_crawl_list):
        self.no_crawl_list = [no_crawl_list] if type(no_crawl_list) is str else no_crawl_list

    def save(self):
        self.fi_jar = open(self.fi_jar_path, "wb")
        pickle.dump(self.fi_store, self.fi_jar, 0)
        self.fi_jar.close()


    def load(self, path=False):
        self.fi_store = pickle.load(open(path if path is not False else self.fi_jar_path, "rb"))

    def fi_list_from_mfl(self):
        self.__output("\n\n***inspect_mfl() ({0})\n".format(now()), to_console=False)
        self.mfl = open(self.mfl_path, "r+") if self.mode == SAFE_BUILD_MODE else open(self.mfl_path, "r")
        files = self.mfl.readlines()[1:]  # first line is a header
        fi_list = []
        for f in files:
            f = f.rstrip('\n')
            if self.black_listed(f): continue  # ie. is has do_not_inspect file extension or resides in a do_not_crawl directory
            self.__output('Building FileInspection for: "{0}"'.format(f))
            try:
                self.fi_store.append(FileInspection(f))
                self.count += 1
                self.files += 1
                self.save()
            except IOError as e:
                self.__output(e.message)
        self.__output("Total Files: {0}".format(self.files), to_console=False)
        self.log.close()

    def black_listed(self, path):
        file_name, file_ext = os.path.splitext(path)
        return file_ext.lower() in self.no_inspect_list

    def locate_duplicates(self, exclude=[]):
        self.log = open(self.log_path, "a")
        self.__output("\n\n***locate_duplicates()\n", to_console=False)

        for fi in self.fi_store:
            if self.black_listed(fi.path): continue
            if not fi.hash in self.duplicates:
                self.duplicates[fi.hash] = {"original": fi, "copies": []}
            else:
                if self.duplicates[fi.hash]["original"].created > fi.created:
                    self.duplicates[fi.hash]['copies'].append(self.duplicates[fi.hash]["original"])
                    self.duplicates[fi.hash]["original"] = fi
                else:
                    self.duplicates[fi.hash]['copies'].append(fi)

    def fetch_duplicates(self, copy=False):
        # walk each file's list of inspected duplicates
        for hash_key in self.duplicates:
            # walk each FileInspection in the list
            for f_ins in self.duplicates[hash_key]['copies']:
                if f_ins.fetched: continue  # this is kind of broken logic, just ignore this
                if self.duplicate_size + f_ins.size > self.max_duplicate_space:
                    self.save()
                    self.__output("*** REACHED MAX SPACE LIMIT FOR COPIED FILES; SAVING & EXITING ***")
                    self.duplicate_size = 0
                    return
                # create the parent folder (ie. duplicates/hash_key
                top_dir = os.path.join(self.duplicates_path, hash_key)
                if not os.path.isdir(top_dir): os.mkdir(top_dir)

                # write the json output of the FileInspection
                if not os.path.isfile(os.path.join(top_dir, ORIGINAL_NAME)):
                    open(os.path.join(top_dir, ORIGINAL_NAME), "w+").write(f_ins.log())
                fi_base, fi_name = os.path.split(f_ins.path)
                fi_base = os.path.join(top_dir, *path_dir_list(fi_base)[1:])
                make_missing_dirs(fi_base)
                relocated_file = os.path.join(fi_base, fi_name)
                try:
                    shutil.copyfile(f_ins.path, relocated_file)  # copy for now; next step will be move, and then finally delete
                    f_ins.fetched = True
                    self.save()
                    self.duplicate_size += f_ins.size
                    self.__output("Duplicate Found: Successfully relocated to {0}".format(relocated_file))
               except OSError as e:
                    self.___output('Duplicate relocation \"{0}\" to \"{1}\" failed: {2}'.format(f_ins.path, relocated_file, e.message))

#  A sample of how it's currently being used; there's a CLI to come

duplicates = "/Volumes/3TB/DuplicateFiles/duplicates"
log = "/Volumes/3TB/DuplicateFiles/"
mfl = "/Volumes/3TB/DuplicateFiles/"
search_root = "/Volumes/PersonalStorage"

Man = Manifest(search_root, duplicates, mfl, log, False)
Man.do_not_inspect([".mov", ".avi", ".mpg", ".mpeg", ".mkv", ".dmg", ".mp4", ".mp3", ".m4v", ".wmv", ".rar", ".avchd", ".daa", ".part", ".mpq", ".iso", ".vob"]) # ie. really big files! :)

Man.do_not_crawl(["/Volumes/WIN7","/Volumes/Boot/System","/Volumes/Boot/Library", "/Volumes/Boot/Applications"])
Man.build_master_file_list()
Man.fi_list_from_mfl()  # The volume "PersonalStorage" found 194,000 non-blacklisted files; after 10hrs it had inspected 28,000 of them
Man.locate_duplicates()
Man.fetch_duplicates()

Afterthoughts

This is a pet project; I expect this will grow in scale quite a lot before it's done, that's ok—I'm as interested in best practices as results. So I'm also open to high-level advice in the vein of software engineering or structuring a project like this—that's less a request and more a note to anyone reading and thinking that I've got fundamental flaws in this approach!

\$\endgroup\$
6
\$\begingroup\$

Sort your imports

import datetime
import hashlib
import os
import pickle
import shutil
import sys
import time

Your now function should probably use datetime.datetime.now, and can deduplicate its branches:

def now(include_time=True):
    format_as = '%Y-%m-%d %H:%M:%S' if include_time else '%Y-%m-%d'
    datetime.datetime.now().strftime(format_as)

Personally I'd be tempted to use format instead of strftime - format is more general and seems nicer overall:

def now(include_time=True): format_as = '%Y-%m-%d %H:%M:%S' if include_time else '%Y-%m-%d'
    format(datetime.datetime.now(), format_as)

Your path_dir_list function suggests you should use pathlib. It supports Python 2, but it's in Python 3 by default from 3.4 onwards.

def path_dir_list(path):
    return PurePath(path).parts

Having make_missing_dirs do

try:
    os.makedirs(path)
except AttributeError:
    os.makedirs(os.path.join(*path))

is not good. Decide on what type it accepts and stick with it.

Further, with pathlib the whole thing can be just

def make_missing_dirs(path):
    path = Path(path)
    for path in reversed(path.parents):
        try:
            path.mkdir()
        except OSError:
            pass

or the equivalent without - using makedirs (or pathlib.Path(...).mkdir(parents=True)) just duplicates work.

I don't get why parents=True shouldn't be enough, though, so I recommend sticking with

def make_missing_dirs(path):
    Path(path).mkdir(parents=True)

Your is_subpath seems to be broken:

is_subpath("/home", ["/ho"])
#>>> True

The pathlib way to do this would probably be

def is_subpath(path, of):
    try:
        path.relative_to(of)
    except ValueError:
        return False
    else:
        return True

def is_subpath_any(path, of_paths):
    path = Path(path).resolve()
    return any(is_subpath(path, Path(of).resolve()) for of in of_paths)

This looks longer since there is no is_relative_to in pathlib and because I use shorter lines, but at least it should be correct. However, this resolves with OS calls, so will fail for nonexistent paths.

You then have

DIR = "d"
FILE = "f"

which are unused (and look like a terrible idea).

You then have

LIST_MODE = 0
SAFE_BUILD_MODE = 1

I can live with enums, although only with justification. You also probably shouldn't be using integer enums, either. Try = object() or, even better, use an Enum backport.

But you only use this here:

self.mode = mode if mode in [LIST_MODE, FAST_BUILD_MODE, SAFE_BUILD_MODE, COPY_MODE] else self.SAFE_BUILD_MODE

and don't define FAST_BUILD_MODE or COPY_MODE. This obviously can't run then, so remove those.

You also have an absurd default for invalid input. NEVER DO THIS! Bad input should never be silently ignored!

It looks to me like you should have

self.safe_build_mode = safe_build_mode

with safe_build_mode=False in the argument list.

You don't use

OS_FILES = [".DS_Store", ".", "..", ".localized"]

either.

IMPORTANT:

FileInspection has loads of class variables that you don't use. This demonstrates a misunderstanding of how classes work in Python. Python is not Java.

Class variables are like static variables. Do not initialize data on the class. Doing so can only cause sadness. Especially don't initialize variables with incorrect data. That is a surefire way to cause bugs.

In log you have

def log(self):
    json = self.json_template.format(self.__hash, self.__path, self.__size, self.__created, self.__last_mod, self.__has_duplicates,
        self.__fetched, self.__checked)
    return json.replace(":False", ":false").replace(":True",":true")

But none of these variables exist! You don't even use checked or is_original! And even if they did exist, there's no reason to use __mangled names anyway. Never use __mangled names - they're just a silly way to make it easier to do a particularly silly thing that you shouldn't ever want to do.

Wrap your lines. These are way too long.

Also, don't reinvent JSON serialization. Use json.dumps with a sensible dictionary:

def log(self):
    return json.dumps({
        "hash": self.hash,
        "path": self.path,
        "filesize": self.size,
        "created:": self.created,
        "last_mod": self.last_mod,
        "has_duplicates": self.has_duplicates,
        "duplicates_moved": self.fetched,
        "checked": self.checked,
    })

Your hash_file is taking self where self is not fully initialized. I recommend you move it to a plain function and give it a normal argument. You also shouldn't open files in text mode when hashing.

def hash_file(path, read_size=2**20):
    checksum = hashlib.md5()

    with open(path, "rb") as f:
        for chunk in iter(lambda: f.read(read_size), b""):
            checksum.update(data)

    return checksum.hexdigest()

Manifest make the same error with the class variables, but look how many there are!

duplicates_path = ''    # where to put found duplicate files
duplicates = {}         # references to FileInspections that were duplicates
search_dir = ''         # the directory to crawl, eventually my whole file-system
no_crawl_list = []      # directories not to crawl within the scope of search_dir 
no_inspect_list = []    # file extensions to ignore when building FileInspections
log_path = ''           # where the log file should go
default_mfl_name = "master_file_list_{0}.txt"
mfl_dir = ''            # path of the actual master file list
mfl_path = None         # where the master file list should go
fi_jar_path = None      # where the pickled FileInspections should go
fi_jar = ''             # where pickling of FileInspections continues during runtime
fi_store = []           # the set of FileInspection objects created by fi_list_from_mfl()
mfl = None              # a reference to the master file list when it's open
duplicate_size = 0      # cumulative size of files relocated because they were duplicates
max_duplicate_space = 0 # moving files to a "Duplicates" directory until code is smart enough to trust with deletion
count = 0
dirs = 0
files = 0
os_files = 0
mode = None             # not really implemented yet; you'll see it show up in a few places below but it's haphazard

That is not healthy. Split this up somehow in to manageable chunks!

I don't want to spend too much time writing, but for the rest the things to note are

  • Use with for files.
  • Do one thing per function. do_not_crawl should not be overloaded for multiple types.
  • __mangled names are bad. Especially ___output, which I'm sure is a typo.
  • Your functions are too large.
  • There's too much state. Whatever you're doing, do less of it. Split it up into tools that deal with each requirement separately. __init__ should do nearly nothing - yours does nearly everything.

Sorry for the terseness of this review - the code's quite long so a detailed analysis would take quite long.

\$\endgroup\$
  • \$\begingroup\$ While this doesn't address my actual question, which is whether or not there is a faster way to establish if two files have identical content, this does address everything else, thanks for the huge effort. \$\endgroup\$ – Jonline Jun 9 '15 at 18:23
  • 1
    \$\begingroup\$ @Jonline On that note, maybe first try comparing partial checksums. \$\endgroup\$ – Veedrac Jun 9 '15 at 18:41
  • \$\begingroup\$ I'd considered that, but I have no real CS and had no sense of what was a useful chunk size to compare—1MB? It also occurred to me that I could compare file size first, but again, know too little about the fundamentals of CS or UNIX to appreciate if that strategy has holes in it I can't see? \$\endgroup\$ – Jonline Jun 9 '15 at 19:44
  • 2
    \$\begingroup\$ @Jonline A first-pass should aim to be fast and conservative. This means you don't ever want false negatives, but false positives can be checked later. Thus checking file size is fine and checking hashes of the first few kB should be more than enough. You'd then do full passes only on files that match the first two criteria. \$\endgroup\$ – Veedrac Jun 9 '15 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.