# manifest.py - manifest revision class 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.

from __future__ import absolute_import

import heapq

import itertools

import os

import struct

from .i18n import _

from .node import (

    bin,

    hex,

)

from . import (

    error,

    mdiff,

    policy,

    revlog,

    util,

)

parsers = policy.importmod(r'parsers')

propertycache = util.propertycache

def _parsev1(data):

    # This method does a little bit of excessive-looking

    # precondition checking. This is so that the behavior of this

    # class exactly matches its C counterpart to try and help

    # prevent surprise breakage for anyone that develops against

    # the pure version.

    if data and data[-1:] != '\n':

        raise ValueError('Manifest did not end in a newline.')

    prev = None

    for l in data.splitlines():

        if prev is not None and prev > l:

            raise ValueError('Manifest lines not in sorted order.')

        prev = l

        f, n = l.split('\0')

        if len(n) > 40:

            yield f, bin(n[:40]), n[40:]

        else:

            yield f, bin(n), ''

def _parsev2(data):

    metadataend = data.find('\n')

    # Just ignore metadata for now

    pos = metadataend + 1

    prevf = ''

    while pos < len(data):

        end = data.find('\n', pos + 1) # +1 to skip stem length byte

        if end == -1:

            raise ValueError('Manifest ended with incomplete file entry.')

        stemlen = ord(data[pos:pos + 1])

        items = data[pos + 1:end].split('\0')

        f = prevf[:stemlen] + items[0]

        if prevf > f:

            raise ValueError('Manifest entries not in sorted order.')

        fl = items[1]

        # Just ignore metadata (items[2:] for now)

        n = data[end + 1:end + 21]

        yield f, n, fl

        pos = end + 22

        prevf = f

def _parse(data):

    """Generates (path, node, flags) tuples from a manifest text"""

    if data.startswith('\0'):

        return iter(_parsev2(data))

    else:

        return iter(_parsev1(data))

def _text(it, usemanifestv2):

    """Given an iterator over (path, node, flags) tuples, returns a manifest

    text"""

    if usemanifestv2:

        return _textv2(it)

    else:

        return _textv1(it)

def _textv1(it):

    files = []

    lines = []

    _hex = revlog.hex

    for f, n, fl in it:

        files.append(f)

        # if this is changed to support newlines in filenames,

        # be sure to check the templates/ dir again (especially *-raw.tmpl)

        lines.append("%s\0%s%s\n" % (f, _hex(n), fl))

    _checkforbidden(files)

    return ''.join(lines)

def _textv2(it):

    files = []

    lines = ['\0\n']

    prevf = ''

    for f, n, fl in it:

        files.append(f)

        stem = os.path.commonprefix([prevf, f])

        stemlen = min(len(stem), 255)

        lines.append("%c%s\0%s\n%s\n" % (stemlen, f[stemlen:], fl, n))

        prevf = f

    _checkforbidden(files)

    return ''.join(lines)

class lazymanifestiter(object):

    def __init__(self, lm):

        self.pos = 0

        self.lm = lm

    def __iter__(self):

        return self

    def next(self):

        try:

            data, pos = self.lm._get(self.pos)

        except IndexError:

            raise StopIteration

        if pos == -1:

            self.pos += 1

            return data[0]

        self.pos += 1

        zeropos = data.find('\x00', pos)

        return data[pos:zeropos]

    __next__ = next

class lazymanifestiterentries(object):

    def __init__(self, lm):

        self.lm = lm

        self.pos = 0

    def __iter__(self):

        return self

    def next(self):

        try:

            data, pos = self.lm._get(self.pos)

        except IndexError:

            raise StopIteration

        if pos == -1:

            self.pos += 1

            return data

        zeropos = data.find('\x00', pos)

        hashval = unhexlify(data, self.lm.extrainfo[self.pos],

                            zeropos + 1, 40)

        flags = self.lm._getflags(data, self.pos, zeropos)

        self.pos += 1

        return (data[pos:zeropos], hashval, flags)

    __next__ = next

def unhexlify(data, extra, pos, length):

    s = bin(data[pos:pos + length])

    if extra:

        s += chr(extra & 0xff)

    return s

def _cmp(a, b):

    return (a > b) - (a < b)

class _lazymanifest(object):

    def __init__(self, data, positions=None, extrainfo=None, extradata=None):

        if positions is None:

            self.positions = self.findlines(data)

            self.extrainfo = [0] * len(self.positions)

            self.data = data

            self.extradata = []

        else:

            self.positions = positions[:]

            self.extrainfo = extrainfo[:]

            self.extradata = extradata[:]

            self.data = data

    def findlines(self, data):

        if not data:

            return []

        pos = data.find("\n")

        if pos == -1 or data[-1:] != '\n':

            raise ValueError("Manifest did not end in a newline.")

        positions = [0]

        prev = data[:data.find('\x00')]

        while pos < len(data) - 1 and pos != -1:

            positions.append(pos + 1)

            nexts = data[pos + 1:data.find('\x00', pos + 1)]

            if nexts < prev:

                raise ValueError("Manifest lines not in sorted order.")

            prev = nexts

            pos = data.find("\n", pos + 1)

        return positions

    def _get(self, index):

        # get the position encoded in pos:

        #   positive number is an index in 'data'

        #   negative number is in extrapieces

        pos = self.positions[index]

        if pos >= 0:

            return self.data, pos

        return self.extradata[-pos - 1], -1

    def _getkey(self, pos):

        if pos >= 0:

            return self.data[pos:self.data.find('\x00', pos + 1)]

        return self.extradata[-pos - 1][0]

    def bsearch(self, key):

        first = 0

        last = len(self.positions) - 1

        while first <= last:

            midpoint = (first + last)//2

            nextpos = self.positions[midpoint]

            candidate = self._getkey(nextpos)

            r = _cmp(key, candidate)

            if r == 0:

                return midpoint

            else:

                if r < 0:

                    last = midpoint - 1

                else:

                    first = midpoint + 1

        return -1

    def bsearch2(self, key):

        # same as the above, but will always return the position

        # done for performance reasons

        first = 0

        last = len(self.positions) - 1

        while first <= last:

            midpoint = (first + last)//2

            nextpos = self.positions[midpoint]

            candidate = self._getkey(nextpos)

            r = _cmp(key, candidate)

            if r == 0:

                return (midpoint, True)

            else:

                if r < 0:

                    last = midpoint - 1

                else:

                    first = midpoint + 1

        return (first, False)

    def __contains__(self, key):

        return self.bsearch(key) != -1

    def _getflags(self, data, needle, pos):

        start = pos + 41

        end = data.find("\n", start)

        if end == -1:

            end = len(data) - 1

        if start == end:

            return ''

        return self.data[start:end]

    def __getitem__(self, key):

        if not isinstance(key, bytes):

            raise TypeError("getitem: manifest keys must be a bytes.")

        needle = self.bsearch(key)

        if needle == -1:

            raise KeyError

        data, pos = self._get(needle)

        if pos == -1:

            return (data[1], data[2])

        zeropos = data.find('\x00', pos)

        assert 0 <= needle <= len(self.positions)

        assert len(self.extrainfo) == len(self.positions)

        hashval = unhexlify(data, self.extrainfo[needle], zeropos + 1, 40)

        flags = self._getflags(data, needle, zeropos)

        return (hashval, flags)

    def __delitem__(self, key):

        needle, found = self.bsearch2(key)

        if not found:

            raise KeyError

        cur = self.positions[needle]

        self.positions = self.positions[:needle] + self.positions[needle + 1:]

        self.extrainfo = self.extrainfo[:needle] + self.extrainfo[needle + 1:]

        if cur >= 0:

            self.data = self.data[:cur] + '\x00' + self.data[cur + 1:]

    def __setitem__(self, key, value):

        if not isinstance(key, bytes):

            raise TypeError("setitem: manifest keys must be a byte string.")

        if not isinstance(value, tuple) or len(value) != 2:

            raise TypeError("Manifest values must be a tuple of (node, flags).")

        hashval = value[0]

        if not isinstance(hashval, bytes) or not 20 <= len(hashval) <= 22:

            raise TypeError("node must be a 20-byte byte string")

        flags = value[1]

        if len(hashval) == 22:

            hashval = hashval[:-1]

        if not isinstance(flags, bytes) or len(flags) > 1:

            raise TypeError("flags must a 0 or 1 byte string, got %r", flags)

        needle, found = self.bsearch2(key)

        if found:

            # put the item

            pos = self.positions[needle]

            if pos < 0:

                self.extradata[-pos - 1] = (key, hashval, value[1])

            else:

                # just don't bother

                self.extradata.append((key, hashval, value[1]))

                self.positions[needle] = -len(self.extradata)

        else:

            # not found, put it in with extra positions

            self.extradata.append((key, hashval, value[1]))

            self.positions = (self.positions[:needle] + [-len(self.extradata)]

                              + self.positions[needle:])

            self.extrainfo = (self.extrainfo[:needle] + [0] +

                              self.extrainfo[needle:])

    def copy(self):

        # XXX call _compact like in C?

        return _lazymanifest(self.data, self.positions, self.extrainfo,

            self.extradata)

    def _compact(self):

        # hopefully not called TOO often

        if len(self.extradata) == 0:

            return

        l = []

        last_cut = 0

        i = 0

        offset = 0

        self.extrainfo = [0] * len(self.positions)

        while i < len(self.positions):

            if self.positions[i] >= 0:

                cur = self.positions[i]

                last_cut = cur

                while True:

                    self.positions[i] = offset

                    i += 1

                    if i == len(self.positions) or self.positions[i] < 0:

                        break

                    offset += self.positions[i] - cur

                    cur = self.positions[i]

                end_cut = self.data.find('\n', cur)

                if end_cut != -1:

                    end_cut += 1

                offset += end_cut - cur

                l.append(self.data[last_cut:end_cut])

            else:

                while i < len(self.positions) and self.positions[i] < 0:

                    cur = self.positions[i]

                    t = self.extradata[-cur - 1]

                    l.append(self._pack(t))

                    self.positions[i] = offset

                    if len(t[1]) > 20:

                        self.extrainfo[i] = ord(t[1][21])

                    offset += len(l[-1])

                    i += 1