"""

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-2007 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.

"""

from node import *

from i18n import _

import binascii, changegroup, errno, ancestor, mdiff, os

import sha, struct, util, zlib

# revlog version strings

REVLOGV0 = 0

REVLOGNG = 1

# revlog flags

REVLOGNGINLINEDATA = (1 << 16)

REVLOG_DEFAULT_FLAGS = REVLOGNGINLINEDATA

REVLOG_DEFAULT_FORMAT = REVLOGNG

REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS

def hash(text, p1, p2):

    """generate a hash from the given text and its parent hashes

    This hash combines both the current file contents and its history

    in a manner that makes it easy to distinguish nodes with the same

    content in the revision graph.

    """

    l = [p1, p2]

    l.sort()

    s = sha.new(l[0])

    s.update(l[1])

    s.update(text)

    return s.digest()

def compress(text):

    """ generate a possibly-compressed representation of 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):

    """ decompress the given input """

    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 RevlogError(_("unknown compression type %r") % t)

indexformatv0 = ">4l20s20s20s"

v0shaoffset = 56

# index ng:

# 6 bytes offset

# 2 bytes flags

# 4 bytes compressed length

# 4 bytes uncompressed length

# 4 bytes: base rev

# 4 bytes link rev

# 4 bytes parent 1 rev

# 4 bytes parent 2 rev

# 32 bytes: nodeid

indexformatng = ">Qiiiiii20s12x"

ngshaoffset = 32

versionformat = ">I"

class lazyparser(object):

    """

    this class avoids the need to parse the entirety of large indices

    """

    # lazyparser is not safe to use on windows if win32 extensions not

    # available. it keeps file handle open, which make it not possible

    # to break hardlinks on local cloned repos.

    safe_to_use = os.name != 'nt' or (not util.is_win_9x() and

                                      hasattr(util, 'win32api'))

    def __init__(self, dataf, size):

        self.dataf = dataf

        self.s = struct.calcsize(indexformatng)

        self.datasize = size

        self.l = size/self.s

        self.index = [None] * self.l

        self.map = {nullid: nullrev}

        self.allmap = 0

        self.all = 0

        self.mapfind_count = 0

    def loadmap(self):

        """

        during a commit, we need to make sure the rev being added is

        not a duplicate.  This requires loading the entire index,

        which is fairly slow.  loadmap can load up just the node map,

        which takes much less time.

        """

        if self.allmap:

            return

        end = self.datasize

        self.allmap = 1

        cur = 0

        count = 0

        blocksize = self.s * 256

        self.dataf.seek(0)

        while cur < end:

            data = self.dataf.read(blocksize)

            off = 0

            for x in xrange(256):

                n = data[off + ngshaoffset:off + ngshaoffset + 20]

                self.map[n] = count

                count += 1

                if count >= self.l:

                    break

                off += self.s

            cur += blocksize

    def loadblock(self, blockstart, blocksize, data=None):

        if self.all:

            return

        if data is None:

            self.dataf.seek(blockstart)

            if blockstart + blocksize > self.datasize:

                # the revlog may have grown since we've started running,

                # but we don't have space in self.index for more entries.

                # limit blocksize so that we don't get too much data.

                blocksize = max(self.datasize - blockstart, 0)

            data = self.dataf.read(blocksize)

        lend = len(data) / self.s

        i = blockstart / self.s

        off = 0

        # lazyindex supports __delitem__

        if lend > len(self.index) - i:

            lend = len(self.index) - i

        for x in xrange(lend):

            if self.index[i + x] == None:

                b = data[off : off + self.s]

                self.index[i + x] = b

                n = b[ngshaoffset:ngshaoffset + 20]

                self.map[n] = i + x

            off += self.s

    def findnode(self, node):

        """search backwards through the index file for a specific node"""

        if self.allmap:

            return None

        # hg log will cause many many searches for the manifest

        # nodes.  After we get called a few times, just load the whole

        # thing.

        if self.mapfind_count > 8:

            self.loadmap()

            if node in self.map:

                return node

            return None

        self.mapfind_count += 1

        last = self.l - 1

        while self.index[last] != None:

            if last == 0:

                self.all = 1

                self.allmap = 1

                return None

            last -= 1

        end = (last + 1) * self.s

        blocksize = self.s * 256

        while end >= 0:

            start = max(end - blocksize, 0)

            self.dataf.seek(start)

            data = self.dataf.read(end - start)

            findend = end - start

            while True:

                # we're searching backwards, so weh have to make sure

                # we don't find a changeset where this node is a parent

                off = data.rfind(node, 0, findend)

                findend = off

                if off >= 0:

                    i = off / self.s

                    off = i * self.s

                    n = data[off + ngshaoffset:off + ngshaoffset + 20]

                    if n == node:

                        self.map[n] = i + start / self.s

                        return node

                else:

                    break

            end -= blocksize

        return None

    def loadindex(self, i=None, end=None):

        if self.all:

            return

        all = False

        if i == None:

            blockstart = 0

            blocksize = (512 / self.s) * self.s

            end = self.datasize

            all = True

        else:

            if end:

                blockstart = i * self.s

                end = end * self.s

                blocksize = end - blockstart

            else:

                blockstart = (i & ~63) * self.s

                blocksize = self.s * 64

                end = blockstart + blocksize

        while blockstart < end:

            self.loadblock(blockstart, blocksize)

            blockstart += blocksize

        if all:

            self.all = True

class lazyindex(object):

    """a lazy version of the index array"""

    def __init__(self, parser):

        self.p = parser

    def __len__(self):

        return len(self.p.index)

    def load(self, pos):

        if pos < 0:

            pos += len(self.p.index)

        self.p.loadindex(pos)

        return self.p.index[pos]

    def __getitem__(self, pos):

        ret = self.p.index[pos] or self.load(pos)

        if isinstance(ret, str):

            ret = struct.unpack(indexformatng, ret)

        return ret

    def __setitem__(self, pos, item):

        self.p.index[pos] = item

    def __delitem__(self, pos):

        del self.p.index[pos]

    def insert(self, pos, e):

        self.p.index.insert(pos, e)

    def append(self, e):

        self.p.index.append(e)

class lazymap(object):

    """a lazy version of the node map"""

    def __init__(self, parser):

        self.p = parser

    def load(self, key):

        n = self.p.findnode(key)

        if n == None:

            raise KeyError(key)

    def __contains__(self, key):

        if key in self.p.map:

            return True

        self.p.loadmap()

        return key in self.p.map

    def __iter__(self):

        yield nullid

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

            ret = self.p.index[i]

            if not ret:

                self.p.loadindex(i)

                ret = self.p.index[i]

            if isinstance(ret, str):

                ret = struct.unpack(indexformatng, ret)

            yield ret[7]

    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

    def __delitem__(self, key):

        del self.p.map[key]

class RevlogError(Exception):

    pass

class LookupError(RevlogError):

    pass

def getoffset(q):

    if q & 0xFFFF:

        raise RevlogError(_('incompatible revision flag %x') % q)

    return int(q >> 16)

def gettype(q):

    return int(q & 0xFFFF)

def offset_type(offset, type):

    return long(long(offset) << 16 | type)

class revlogoldio(object):

    def __init__(self):

        self.size = struct.calcsize(indexformatv0)

    def parseindex(self, fp, inline):

        s = self.size

        index = []

        nodemap =  {nullid: nullrev}

        n = off = 0

        data = fp.read()

        l = len(data)

        while off + s <= l:

            cur = data[off:off + s]

            off += s

            e = struct.unpack(indexformatv0, cur)

            # transform to revlogv1 format

            e2 = (offset_type(e[0], 0), e[1], -1, e[2], e[3],

                  nodemap[e[4]], nodemap[e[5]], e[6])

            index.append(e2)

            nodemap[e[6]] = n

            n += 1

        return index, nodemap, None

class revlogio(object):

    def __init__(self):

        self.size = struct.calcsize(indexformatng)

    def parseindex(self, fp, inline):

        try:

            size = util.fstat(fp).st_size

        except AttributeError:

            size = 0

        if lazyparser.safe_to_use and not inline and size > 1000000:

            # big index, let's parse it on demand

            parser = lazyparser(fp, size)

            index = lazyindex(parser)

            nodemap = lazymap(parser)

            e = list(index[0])

            type = gettype(e[0])

            e[0] = offset_type(0, type)

            index[0] = e

            return index, nodemap, None

        s = self.size

        cache = None

        index = []

        nodemap =  {nullid: nullrev}

        n = off = 0

        # if we're not using lazymap, always read the whole index

        data = fp.read()

        l = len(data)

        if inline:

            cache = (0, data)

        while off + s <= l: