detect_inode_moves.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

'''Detects renamed and/or moved files by tracking inodes.

Creates a shell script to replay similar changes.  Make sure to use relative
paths if you want to replay changes in a different absolute location. Does not
follow symbolic links. Inode numbers must be identical (do not cross
filesystems)!
'''
__author__    = 'Pavel Krc'
__email__     = 'src@pkrc.net'
__version__   = '1.1'
__copyright__ = 'Copyright (C) 2015 Pavel Krc'
__license__   = 'GPLv2+'

# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 2 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

import sys
import os
import re

generate_python_scripts = True      # instead of shell scripts (more reliable)

if generate_python_scripts:
    script_header = '''#!/usr/bin/env python
# -*- coding: utf-8 -*-
import os
def ren(a, b):
    print(b)
    assert(not os.path.exists(b))
    os.rename(a, b)
def mkd(d):
    print(d)
    os.mkdir(d)

'''
    mv_cmd = 'ren("{0}", "{1}")\n'
    mkdir_cmd = 'mkd("{0}")\n'
    escaped_chars = re.compile(r'(["\\])')
    esc = lambda s: escaped_chars.sub(r'\\\1', s)
else:
    script_header = '#!/bin/sh\nset -e -v\n\n'
    mv_cmd = 'mv -n -T -- "{0}" "{1}"\n'
    mkdir_cmd = 'mkdir -- "{0}"\n'
    # Since single quotes cannot be escaped in sh, I have to use double qoutes
    # and do a little bit more escaping. Fortunately regex does it efficiently.
    escaped_chars = re.compile(r'([`"\$\\])')
    esc = lambda s: escaped_chars.sub(r'\\\1', s)

def dump_inodes(root, log_path):
    # must be top-down for reconstruction
    with open(log_path, 'w') as o:
        o.write('D {0:d} {1}\n'.format(os.lstat(root).st_ino, root))
        for dpath, dnames, fnames in os.walk(root):
            dpath += '/'
            for n in dnames:
                p = dpath + n
                o.write('D {0:d} {1}\n'.format(os.lstat(p).st_ino, p))
            for n in fnames:
                p = dpath + n
                o.write('F {0:d} {1}\n'.format(os.lstat(p).st_ino, p))

class DirEntry(object):
    __slots__ = ['path', 'parent', 'dirs', 'files']
    def __init__(self, path, parent):
        self.path = path
        self.parent = parent
        self.dirs = set()
        self.files = set()

class FileEntry(object):
    __slots__ = ['path', 'parent']
    def __init__(self, path, parent):
        self.path = path
        self.parent = parent

class MovingTree(object):
    def __init__(self, log_path):
        self.dirs = {}
        self.files = {}
        revdirs = {}
        with open(log_path) as i:
            # root entry
            df, ino, path = next(i).rstrip('\n').split(' ', 2)
            ino = int(ino)
            assert df == 'D'
            self.root = path
            self.dirs[ino] = DirEntry(path, None)
            revdirs[path] = ino

            for ln in i:
                df, ino, path = ln.rstrip('\n').split(' ', 2)
                ino = int(ino)
                parent_ino = revdirs[path.rsplit('/', 1)[0]]
                if df == 'D':
                    self.dirs[ino] = DirEntry(path, parent_ino)
                    revdirs[path] = ino
                    self.dirs[parent_ino].dirs.add(ino)
                elif df == 'F':
                    self.files[ino] = FileEntry(path, parent_ino)
                    self.dirs[parent_ino].files.add(ino)
                else:
                    raise RuntimeError()

    def create_script(self, script_path):
        # uses os.open to create executable script - still, read it first!
        cls = lambda: None
        try:
            fd = os.open(script_path, os.O_CREAT|os.O_WRONLY|os.O_TRUNC, 0o777)
            cls = lambda: os.close(fd)
            o = os.fdopen(fd, 'w')
            cls = o.close
            o.write(script_header)
            self.detect_changes(o)
        finally:
            cls()

    def update_children(self, entry, orig_p, new_p):
        l = len(orig_p)
        for i in entry.dirs:
            centry = self.dirs[i]
            assert centry.path[:l] == orig_p
            centry.path = new_p + centry.path[l:]
            self.update_children(centry, orig_p, new_p)
        for i in entry.files:
            centry = self.files[i]
            assert centry.path[:l] == orig_p
            centry.path = new_p + centry.path[l:]

    def detect_changes(self, script):
        # The order of detecting changes is important. The safest order I could
        # think of was to start top-bottom according to destination (i.e.
        # safely constructing new state with guaranteed existing parents),
        # updating source data structures where necessary.

        newfiles = []
        ok_dirs = ok_files = 0
        for dpath, dnames, fnames in os.walk(self.root):
            dpath += '/'
            for n in dnames:
                p = dpath + n
                ino = os.lstat(p).st_ino
                try:
                    orig_entry = self.dirs.pop(ino)
                except KeyError:
                    # new directory
                    script.write(mkdir_cmd.format(esc(p)))
                else:
                    # existing directory
                    if orig_entry.path == p:
                        ok_dirs += 1
                    else:
                        # moved
                        script.write(mv_cmd.format(esc(orig_entry.path), esc(p)))

                        # disparent self
                        try:
                            parent_entry = self.dirs[orig_entry.parent]
                        except KeyError:
                            pass #parent already processed
                        else:
                            parent_entry.dirs.remove(ino)
                        # moving under either freshly created or already
                        # processed dir, so no need to register under new
                        # parent.

                        # update all children in the source tree
                        self.update_children(orig_entry, orig_entry.path+'/', p+'/')

            for n in fnames:
                p = dpath + n
                ino = os.lstat(p).st_ino
                try:
                    orig_entry = self.files.pop(ino)
                except KeyError:
                    # new file - just log
                    newfiles.append(p)
                else:
                    # existing file
                    if orig_entry.path == p:
                        ok_files += 1
                    else:
                        # moved
                        script.write(mv_cmd.format(esc(orig_entry.path), esc(p)))

                        # disparent self
                        try:
                            parent_entry = self.dirs[orig_entry.parent]
                        except KeyError:
                            pass #parent already processed
                        else:
                            parent_entry.files.remove(ino)

        # list remaining unprocessed
        script.write('\n### Deleted directories ###\n')
        for p in sorted(e.path for e in self.dirs.values()
                if e.path != self.root):
            script.write('#{0}\n'.format(p))
        script.write('\n### Deleted files ###\n')
        for p in sorted(e.path for e in self.files.values()):
            script.write('#{0}\n'.format(p))
        script.write('\n### Newly created files ###\n')
        for p in newfiles:
            script.write('#{0}\n'.format(p))
        script.write('\n### {0:d} dirs and {1:d} files have remained in place. ###\n'
                .format(ok_dirs, ok_files))

if __name__ == '__main__':
    action = sys.argv[1:2]
    if action == ['dump']:
        dump_inodes(sys.argv[2], sys.argv[3])
    elif action == ['detect']:
        tr = MovingTree(sys.argv[2])
        tr.create_script(sys.argv[3])
    else:
        sys.exit('''Usage:

    {0} dump {{root_path}} {{inode_list_path}}
            Dumps inode numbers inside {{root_path}} to a new
            file {{inode_list_path}}, thus recording current state.

    {0} detect {{inode_list_path}} {{script_path}}
            Compares recorded state within {{inode_list_path}} with current
            state and creates a script to reconstruct detected changes.
'''.format(sys.argv[0]))