# revlog.py - storage back-end for mercurial

#

# 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 version 2 or any later version.

"""Storage back-end for Mercurial.

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

and O(changes) merge between branches.

"""

# import stuff from node for others to import from revlog

from node import bin, hex, nullid, nullrev, short #@UnusedImport

from i18n import _

import changegroup, ancestor, mdiff, parsers, error, util

import struct, zlib, errno

_pack = struct.pack

_unpack = struct.unpack

_compress = zlib.compress

_decompress = zlib.decompress

_sha = util.sha1

# revlog header flags

REVLOGV0 = 0

REVLOGNG = 1

REVLOGNGINLINEDATA = (1 << 16)

REVLOGSHALLOW = (1 << 17)

REVLOG_DEFAULT_FLAGS = REVLOGNGINLINEDATA

REVLOG_DEFAULT_FORMAT = REVLOGNG

REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS

REVLOGNG_FLAGS = REVLOGNGINLINEDATA | REVLOGSHALLOW

# revlog index flags

REVIDX_PARENTDELTA  = 1

REVIDX_PUNCHED_FLAG = 2

REVIDX_KNOWN_FLAGS = REVIDX_PUNCHED_FLAG | REVIDX_PARENTDELTA

# amount of data read unconditionally, should be >= 4

# when not inline: threshold for using lazy index

_prereadsize = 1048576

# max size of revlog with inline data

_maxinline = 131072

RevlogError = error.RevlogError

LookupError = error.LookupError

def getoffset(q):

    return int(q >> 16)

def gettype(q):

    return int(q & 0xFFFF)

def offset_type(offset, type):

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

nullhash = _sha(nullid)

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.

    """

    # As of now, if one of the parent node is null, p2 is null

    if p2 == nullid:

        # deep copy of a hash is faster than creating one

        s = nullhash.copy()

        s.update(p1)

    else:

        # none of the parent nodes are nullid

        l = [p1, p2]

        l.sort()

        s = _sha(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)

    l = len(text)

    bin = None

    if l < 44:

        pass

    elif l > 1000000:

        # zlib makes an internal copy, thus doubling memory usage for

        # large files, so lets do this in pieces

        z = zlib.compressobj()

        p = []

        pos = 0

        while pos < l:

            pos2 = pos + 2**20

            p.append(z.compress(text[pos:pos2]))

            pos = pos2

        p.append(z.flush())

        if sum(map(len, p)) < l:

            bin = "".join(p)

    else:

        bin = _compress(text)

    if bin is None or len(bin) > l:

        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 _decompress(bin)

    if t == 'u':

        return bin[1:]

    raise RevlogError(_("unknown compression type %r") % t)

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.

    def __init__(self, dataf):

        try:

            size = util.fstat(dataf).st_size

        except AttributeError:

            size = 0

        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] is 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 we have to make sure

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

                off = data.find(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 is None:

            blockstart = 0

            blocksize = (65536 / 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 & ~1023) * self.s

                blocksize = self.s * 1024

                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):

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

    def __setitem__(self, pos, item):

        self.p.index[pos] = _pack(indexformatng, *item)

    def __delitem__(self, pos):

        del self.p.index[pos]

    def insert(self, pos, e):

        self.p.index.insert(pos, _pack(indexformatng, *e))

    def append(self, e):

        self.p.index.append(_pack(indexformatng, *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 is 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, ret in enumerate(self.p.index):

            if not ret:

                self.p.loadindex(i)

                ret = self.p.index[i]

            if isinstance(ret, str):

                ret = _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]

indexformatv0 = ">4l20s20s20s"

v0shaoffset = 56

class revlogoldio(object):

    def __init__(self):

        self.size = struct.calcsize(indexformatv0)

    def parseindex(self, fp, data, inline):

        s = self.size

        index = []

        nodemap =  {nullid: nullrev}

        n = off = 0

        if len(data) == _prereadsize:

            data += fp.read() # read the rest

        l = len(data)

        while off + s <= l:

            cur = data[off:off + s]

            off += s

            e = _unpack(indexformatv0, cur)

            # transform to revlogv1 format

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

                  nodemap.get(e[4], nullrev), nodemap.get(e[5], nullrev), e[6])

            index.append(e2)

            nodemap[e[6]] = n

            n += 1

        return index, nodemap, None

    def packentry(self, entry, node, version, rev):

        if gettype(entry[0]):

            raise RevlogError(_("index entry flags need RevlogNG"))

        e2 = (getoffset(entry[0]), entry[1], entry[3], entry[4],

              node(entry[5]), node(entry[6]), entry[7])

        return _pack(indexformatv0, *e2)

# index ng:

#  6 bytes: offset

#  2 bytes: flags

#  4 bytes: compressed length

#  4 bytes: uncompressed length

#  4 bytes: base rev