#!/usr/bin/env python

# Copyright (c) 2009 Anthony Towns
#
# 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.
class Struct(object):
    __slots__ = ()
    def __init__(self, *args, **kwargs):
        d = dict(zip(self.__slots__, args))
        d.update(kwargs)
        for x in self.__slots__:
            setattr(self, x, d.get(x,None))
class Change(Struct):
    __slots__ = ("offset", "del_cnt", "add_cnt", "add_lines")
class LineNrCache(Struct)
    __slots__ = ("change", "line")
class Modifications(object):
    def __init__(self):
        self.changes = []  # list of Change objects
        self.line_nr_cache = LineNrCache(change=0, line=0)
    def insert(self, i, offset, del_cnt, add_lines):
        self.changes.insert(i,
            Change(offset, del_cnt, len(add_lines), add_lines) )

    def mod_for(self, line):
        assert line >= 0
        i = self.line_nr_cache.change
        pos = self.line_nr_cache.line
        changes = self.changes # abbreviation
        assert (i == len(changes) == 0) or (0 <= i and i < len(changes))

        while True:
            assert 0 <= i and i <= len(changes)
            if i == len(changes):
                self.insert(i, line-pos, 0, [])
                break

            if pos + changes[i].offset + changes[i].add_cnt < line:
                pos += changes[i].offset + change[i].add_cnt
                i += 1
                continue
            elif line < pos:
                assert i > 0
                i -= 1
                pos -= changes[i].offset + changes[i].add_cnt
                continue

            assert i == 0 or pos <= line
            assert line <= pos + changes[i].offset + changes[i].add_cnt
            if line < pos + changes[i].offset:
                changes[i].offset -= (line-pos)
                self.insert(i, line-pos, 0, [])
                break
            elif pos + changes[i].offset < line:
                split = line - pos - changes[i].offset
                self.insert(i+1, 0, 0, changes[i].add_lines[split:])
                changes[i].add_cnt = split 
                changes[i].add_lines = changes[i].add_lines[:split]
                i += 1
                break
            else: 
                assert line == pos + changes[i].offset
                break

        assert 0 <= i and i < len(changes)
        self.line_nr_cache.change = i
        self.line_nr_cache.line = line - changes[i].offset
        return i

    def merge_next(self, i):
        assert i+1 < len(self.changes) and self.changes[i+1].offset == 0

        c_i = self.line_nr_cache.change
        c_p = self.line_nr_cache.line
        if c_i == i+1:
            c_i -= 1
            c_p -= self.change[i].offset + self.change[i].add_cnt
            self.line_nr_cache.change = c_i
            self.line_nr_chace.line = c_p
        self.changes.pop(i+1)  

    def insert_lines(self, line, strs):
        mod = self.mod_for(line)
        self.changes[mod].add_cnt += len(strs)
        self.changes[mod].add_lines = strs + self.add_lines[mod]
        if mod > 0 and self.changes[mod].offset == 0:
            self.merge_next(mod-1)
            assert mod == len(self.changes) or self.changes[mod].offset > 0
        assert mod-1 <= 0 or self.changes[mod-1].offset > 0

    def remove_lines(self, line, cnt):
        mod = self.mod_for(line)
        changes = self.changes # abbreviation
        while cnt > 0:
            k = min(changes[mod].add_cnt, cnt)
            changes[mod].add_lines = self.add_lines[mod][k:]
            changes[mod].add_cnt -= k
            cnt -= k

            if mod+1 < len(changes):
                k = min(changes[mod+1].offset, cnt)
                changes[mod].del_cnt += k
                changes[mod+1].offset -= k
                cnt -= k
                if changes[mod+1].offset == 0:
                    self.merge_next(mod)
            else:
                changes[mod].del_cnt += cnt
                cnt = 0
        if mod > 0 and changes[mod].offset == 0:
            self.merge_next(mod-1)
            assert mod-1 == 0 or changes[mod-1].offset > 0

    def apply_against_file(self, file, out):
        for change in self.changes):
            for _ in xrange(change.offset):
                out.write(file.readline())
            for _ in xrange(change.del_cnt):
                file.readline()
            assert change.add_cnt == len(change.add_lines)
            for line in change.add_lines:
                out.write(line + "\n")
        while True:
            line = file.readline()
            if line == "":
                break
            out.write(line)

def red_components(file):
    cmdwanted = True
    lines = []
    for line in file:
        line = line.rstrip("\n")
        if cmdwanted:
            if line == "":
                continue

            line, cmd = line[:-1], line[-1]
            if "," in line:
                vals = line.split(",", 1)
            else:
                vals = line, line
            vals = [int(x) for x in vals]

            offset = vals[0]-1
            del_cnt = vals[1]-vals[0]+1

            if cmd == "d":
                yield (offset, del_cnt, [])
            elif cmd == "c":
                cmdwanted = False
            elif cmd == "a":
                offset += 1
                del_cnt = 0
                cmdwanted = False
            else:
                raise Exception("Could not parse ed command: \"%s%s\"" % 
                    (line,cmd))
        else:
            if line == ".":
                yield (offset, del_cnt, lines)
                lines = []
                cmdwanted = True
            else:
                lines.append(line)
    if not cmdwanted:
        raise Exception("ed input hit eof within text block")
    return
class EdModifications(Modifications):
    def read_diff(self, file):
        for offset, del_cnt, add_lines in red_components(file):
            if del_cnt > 0:
                self.remove_lines(offset, del_cnt)
            if add_lines != []:
                self.insert_lines(offset, add_lines)
        return

    def write_diff(self, out):
        line = 0
        for change in self.changes:
            line += change.offset + change.del_cnt

        for change in reversed(self.changes):
            line -= change.del_cnt

            if change.del_cnt <= 1:
                lines = "%d" % (line+1)
            else:
                lines = "%d,%d" % (line+1, line+change.del_cnt)
            if change.add_cnt == 0:
                if change.del_cnt == 0:
                    continue
                else:
                    out.write("%sd\n" % (lines))
            else:
                if change.del_cnt == 0:
                    out.write("%da\n" % (line))   # NB: not line+1
                else:
                    out.write("%sc\n" % (lines))
                for added_line in change.add_lines:
                    out.write("%s\n" % (added_line))
                out.write(".\n")
            line -= change.offset

def main():
    import sys, gzip

    if len(sys.argv) == 1 or (len(sys.argv) == 2 and sys.argv[1] == "-f"):
        print "Usage: %s [-f] <diff>..."
        print """
One of more diff files must be specified. Gzip compression is assumed if
.gz extension is used.

If -f is specified, patch will be applied to stdin, with result on stdout.
Otherwise, combined diff is produced on stdout."""
        sys.exit(0)

    if sys.argv[1] == "-f":
        just_dump_ed = False
        files = sys.argv[2:]
    else:
        just_dump_ed = True
        files = sys.argv[1:]

    diffs = EdModifications()
    for filename in files:
        if filename.endswith(".gz"):
            file = gzip.GzipFile(filename, "r")
        else:
            file = open(filename, "r")
        diffs.read_diff(file)

    if just_dump_ed:
        diffs.write_diff(sys.stdout)
    else:
        diffs.apply_against_file(sys.stdin, sys.stdout)

if __name__ == "__main__":
    main()