# revlog.py - storage back-end for mercurial

#

# This provides efficient delta storage with O(1) retrieve and append

# and O(changes) merge between branches

#

# Copyright 2005 Matt Mackall <mpm@selenic.com>

#

# This software may be used and distributed according to the terms

# of the GNU General Public License, incorporated herein by reference.

import zlib, struct, sha, binascii, heapq

from mercurial import mdiff

def hex(node): return binascii.hexlify(node)

def bin(node): return binascii.unhexlify(node)

def short(node): return hex(node[:6])

def compress(text):

    if not text: return text

    if len(text) < 44:

        if text[0] == '\0': return text

        return 'u' + text

    bin = zlib.compress(text)

    if len(bin) > len(text):

        if text[0] == '\0': return text

        return 'u' + text

    return bin

def decompress(bin):

    if not bin: return bin

    t = bin[0]

    if t == '\0': return bin

    if t == 'x': return zlib.decompress(bin)

    if t == 'u': return bin[1:]

    raise "unknown compression type %s" % t

def hash(text, p1, p2):

    l = [p1, p2]

    l.sort()

    s = sha.new(l[0])

    s.update(l[1])

    s.update(text)

    return s.digest()

nullid = "\0" * 20

indexformat = ">4l20s20s20s"

class lazyparser:

    def __init__(self, data, revlog):

        self.data = data

        self.s = struct.calcsize(indexformat)

        self.l = len(data)/self.s

        self.index = [None] * self.l

        self.map = {nullid: -1}

        self.all = 0

        self.revlog = revlog

    def load(self, pos=None):

        if self.all: return

        if pos is not None:

            block = pos / 1000

            i = block * 1000

            end = min(self.l, i + 1000)

        else:

            self.all = 1

            i = 0

            end = self.l

            self.revlog.index = self.index

            self.revlog.nodemap = self.map

        while i < end:

            d = self.data[i * self.s: (i + 1) * self.s]

            e = struct.unpack(indexformat, d)

            self.index[i] = e

            self.map[e[6]] = i

            i += 1

class lazyindex:

    def __init__(self, parser):

        self.p = parser

    def __len__(self):

        return len(self.p.index)

    def load(self, pos):

        self.p.load(pos)

        return self.p.index[pos]

    def __getitem__(self, pos):

        return self.p.index[pos] or self.load(pos)

    def append(self, e):

        self.p.index.append(e)

class lazymap:

    def __init__(self, parser):

        self.p = parser

    def load(self, key):

        if self.p.all: return

        n = self.p.data.find(key)

        if n < 0: raise KeyError("node " + hex(key))

        pos = n / self.p.s

        self.p.load(pos)

    def __contains__(self, key):

        self.p.load()

        return key in self.p.map

    def __iter__(self):

        yield nullid

        for i in xrange(self.p.l):

            try:

                yield self.p.index[i][6]

            except:

                self.p.load(i)

                yield self.p.index[i][6]

    def __getitem__(self, key):

        try:

            return self.p.map[key]

        except KeyError:

            try:

                self.load(key)

                return self.p.map[key]

            except KeyError:

                raise KeyError("node " + hex(key))

    def __setitem__(self, key, val):

        self.p.map[key] = val

class revlog:

    def __init__(self, opener, indexfile, datafile):

        self.indexfile = indexfile

        self.datafile = datafile

        self.opener = opener

        self.cache = None

        try:

            i = self.opener(self.indexfile).read()

        except IOError:

            i = ""

        if len(i) > 10000:

            # big index, let's parse it on demand

            parser = lazyparser(i, self)

            self.index = lazyindex(parser)

            self.nodemap = lazymap(parser)

        else:

            s = struct.calcsize(indexformat)

            l = len(i) / s

            self.index = [None] * l

            m = [None] * l

            n = 0

            for f in xrange(0, len(i), s):

                # offset, size, base, linkrev, p1, p2, nodeid

                e = struct.unpack(indexformat, i[f:f + s])

                m[n] = (e[6], n)

                self.index[n] = e

                n += 1

            self.nodemap = dict(m)

            self.nodemap[nullid] = -1

    def tip(self): return self.node(len(self.index) - 1)

    def count(self): return len(self.index)

    def node(self, rev): return (rev < 0) and nullid or self.index[rev][6]

    def rev(self, node): return self.nodemap[node]

    def linkrev(self, node): return self.index[self.nodemap[node]][3]

    def parents(self, node):

        if node == nullid: return (nullid, nullid)

        return self.index[self.nodemap[node]][4:6]

    def start(self, rev): return self.index[rev][0]

    def length(self, rev): return self.index[rev][1]

    def end(self, rev): return self.start(rev) + self.length(rev)

    def base(self, rev): return self.index[rev][2]

    def heads(self):

        p = {}

        h = []

        for r in range(self.count() - 1, -1, -1):

            n = self.node(r)

            if n not in p:

                h.append(n)

            for pn in self.parents(n):

                p[pn] = 1

        return h

    def children(self, node):

        c = []

        p = self.rev(node)

        for r in range(p + 1, self.count()):

            n = self.node(r)

            for pn in self.parents(n):

                if pn == node:

                    c.append(n)

                    continue

                elif pn == nullid:

                    continue

        return c

    def lookup(self, id):

        try:

            rev = int(id)

            if str(rev) != id: raise ValueError

            if rev < 0: rev = self.count() + rev

            if rev < 0 or rev >= self.count(): raise ValueError

            return self.node(rev)

        except (ValueError, OverflowError):

            c = []

            for n in self.nodemap:

                if hex(n).startswith(id):

                    c.append(n)

            if len(c) > 1: raise KeyError("Ambiguous identifier")

            if len(c) < 1: raise KeyError("No match found")

            return c[0]

        return None

    def diff(self, a, b):

        return mdiff.textdiff(a, b)

    def patches(self, t, pl):

        return mdiff.patches(t, pl)

    def delta(self, node):

        r = self.rev(node)

        b = self.base(r)

        if r == b:

            return self.diff(self.revision(self.node(r - 1)),

                             self.revision(node))

        else:

            f = self.opener(self.datafile)

            f.seek(self.start(r))

            data = f.read(self.length(r))

        return decompress(data)

    def revision(self, node):

        if node == nullid: return ""

        if self.cache and self.cache[0] == node: return self.cache[2]

        text = None

        rev = self.rev(node)

        start, length, base, link, p1, p2, node = self.index[rev]

        end = start + length

        if base != rev: start = self.start(base)

        if self.cache and self.cache[1] >= base and self.cache[1] < rev:

            base = self.cache[1]

            start = self.start(base + 1)

            text = self.cache[2]

            last = 0

        f = self.opener(self.datafile)

        f.seek(start)

        data = f.read(end - start)

        if text is None:

            last = self.length(base)

            text = decompress(data[:last])

        bins = []

        for r in xrange(base + 1, rev + 1):

            s = self.length(r)

            bins.append(decompress(data[last:last + s]))

            last = last + s

        text = mdiff.patches(text, bins)

        if node != hash(text, p1, p2):

            raise IOError("integrity check failed on %s:%d"

                          % (self.datafile, rev))

        self.cache = (node, rev, text)

        return text

    def addrevision(self, text, transaction, link, p1=None, p2=None, d=None):

        if text is None: text = ""

        if p1 is None: p1 = self.tip()

        if p2 is None: p2 = nullid

        node = hash(text, p1, p2)

        if node in self.nodemap:

            return node

        n = self.count()

        t = n - 1

        if n:

            base = self.base(t)

            start = self.start(base)

            end = self.end(t)

            if not d:

                prev = self.revision(self.tip())

                d = self.diff(prev, text)

            data = compress(d)

            dist = end - start + len(data)

        # full versions are inserted when the needed deltas

        # become comparable to the uncompressed text

        if not n or dist > len(text) * 2:

            data = compress(text)

            base = n

        else:

            base = self.base(t)

        offset = 0

        if t >= 0:

            offset = self.end(t)

        e = (offset, len(data), base, link, p1, p2, node)

        self.index.append(e)

        self.nodemap[node] = n

        entry = struct.pack(indexformat, *e)

        transaction.add(self.datafile, e[0])

        self.opener(self.datafile, "a").write(data)

        transaction.add(self.indexfile, n * len(entry))

        self.opener(self.indexfile, "a").write(entry)

        self.cache = (node, n, text)

        return node

    def ancestor(self, a, b):

        # calculate the distance of every node from root

        dist = {nullid: 0}

        for i in xrange(self.count()):

            n = self.node(i)

            p1, p2 = self.parents(n)

            dist[n] = max(dist[p1], dist[p2]) + 1

        # traverse ancestors in order of decreasing distance from root

        def ancestors(node):

            # we store negative distances because heap returns smallest member

            h = [(-dist[node], node)]

            seen = {}

            earliest = self.count()

            while h:

                d, n = heapq.heappop(h)

                if n not in seen:

                    seen[n] = 1

                    r = self.rev(n)

                    yield (-d, r, n)

                    for p in self.parents(n):

                        heapq.heappush(h, (-dist[p], p))

        x = ancestors(a)

        y = ancestors(b)

        lx = x.next()

        ly = y.next()

        # increment each ancestor list until it is closer to root than

        # the other, or they match

        while 1:

            if lx == ly: