# obsolete.py - obsolete markers handling

#

# Copyright 2012 Pierre-Yves David <pierre-yves.david@ens-lyon.org>

#                Logilab SA        <contact@logilab.fr>

#

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

# GNU General Public License version 2 or any later version.

"""Obsolete marker handling

An obsolete marker maps an old changeset to a list of new

changesets. If the list of new changesets is empty, the old changeset

is said to be "killed". Otherwise, the old changeset is being

"replaced" by the new changesets.

Obsolete markers can be used to record and distribute changeset graph

transformations performed by history rewrite operations, and help

building new tools to reconcile conflicting rewrite actions. To

facilitate conflict resolution, markers include various annotations

besides old and news changeset identifiers, such as creation date or

author name.

The old obsoleted changeset is called a "precursor" and possible

replacements are called "successors". Markers that used changeset X as

a precursor are called "successor markers of X" because they hold

information about the successors of X. Markers that use changeset Y as

a successors are call "precursor markers of Y" because they hold

information about the precursors of Y.

Examples:

- When changeset A is replaced by changeset A', one marker is stored:

    (A, (A',))

- When changesets A and B are folded into a new changeset C, two markers are

  stored:

    (A, (C,)) and (B, (C,))

- When changeset A is simply "pruned" from the graph, a marker is created:

    (A, ())

- When changeset A is split into B and C, a single marker are used:

    (A, (C, C))

  We use a single marker to distinguish the "split" case from the "divergence"

  case. If two independent operations rewrite the same changeset A in to A' and

  A'', we have an error case: divergent rewriting. We can detect it because

  two markers will be created independently:

  (A, (B,)) and (A, (C,))

Format

------

Markers are stored in an append-only file stored in

'.hg/store/obsstore'.

The file starts with a version header:

- 1 unsigned byte: version number, starting at zero.

The header is followed by the markers. Marker format depend of the version. See

comment associated with each format for details.

"""

import struct

import util, base85, node

import phases

from i18n import _

_pack = struct.pack

_unpack = struct.unpack

_SEEK_END = 2 # os.SEEK_END was introduced in Python 2.5

# the obsolete feature is not mature enough to be enabled by default.

# you have to rely on third party extension extension to enable this.

_enabled = False

# Options for obsolescence

createmarkersopt = 'createmarkers'

allowunstableopt = 'allowunstable'

### obsolescence marker flag

## bumpedfix flag

#

# When a changeset A' succeed to a changeset A which became public, we call A'

# "bumped" because it's a successors of a public changesets

#

# o    A' (bumped)

# |`:

# | o  A

# |/

# o    Z

#

# The way to solve this situation is to create a new changeset Ad as children

# of A. This changeset have the same content than A'. So the diff from A to A'

# is the same than the diff from A to Ad. Ad is marked as a successors of A'

#

# o   Ad

# |`:

# | x A'

# |'|

# o | A

# |/

# o Z

#

# But by transitivity Ad is also a successors of A. To avoid having Ad marked

# as bumped too, we add the `bumpedfix` flag to the marker. <A', (Ad,)>.

# This flag mean that the successors express the changes between the public and

# bumped version and fix the situation, breaking the transitivity of

# "bumped" here.

bumpedfix = 1

usingsha256 = 2

## Parsing and writing of version "0"

#

# The header is followed by the markers. Each marker is made of:

#

# - 1 uint8 : number of new changesets "N", can be zero.

#

# - 1 uint32: metadata size "M" in bytes.

#

# - 1 byte: a bit field. It is reserved for flags used in common

#   obsolete marker operations, to avoid repeated decoding of metadata

#   entries.

#

# - 20 bytes: obsoleted changeset identifier.

#

# - N*20 bytes: new changesets identifiers.

#

# - M bytes: metadata as a sequence of nul-terminated strings. Each

#   string contains a key and a value, separated by a colon ':', without

#   additional encoding. Keys cannot contain '\0' or ':' and values

#   cannot contain '\0'.

_fm0version = 0

_fm0fixed   = '>BIB20s'

_fm0node = '20s'

_fm0fsize = struct.calcsize(_fm0fixed)

_fm0fnodesize = struct.calcsize(_fm0node)

def _fm0readmarkers(data, off=0):

    # Loop on markers

    l = len(data)

    while off + _fm0fsize <= l:

        # read fixed part

        cur = data[off:off + _fm0fsize]

        off += _fm0fsize

        numsuc, mdsize, flags, pre = _unpack(_fm0fixed, cur)

        # read replacement

        sucs = ()

        if numsuc:

            s = (_fm0fnodesize * numsuc)

            cur = data[off:off + s]

            sucs = _unpack(_fm0node * numsuc, cur)

            off += s

        # read metadata

        # (metadata will be decoded on demand)

        metadata = data[off:off + mdsize]

        if len(metadata) != mdsize:

            raise util.Abort(_('parsing obsolete marker: metadata is too '

                               'short, %d bytes expected, got %d')

                             % (mdsize, len(metadata)))

        off += mdsize

        metadata = _fm0decodemeta(metadata)

        try:

            when, offset = metadata.pop('date', '0 0').split(' ')

            date = float(when), int(offset)

        except ValueError:

            date = (0., 0)

        parents = None

        if 'p2' in metadata:

            parents = (metadata.pop('p1', None), metadata.pop('p2', None))

        elif 'p1' in metadata:

            parents = (metadata.pop('p1', None),)

        elif 'p0' in metadata:

            parents = ()

        if parents is not None:

            try:

                parents = tuple(node.bin(p) for p in parents)

                # if parent content is not a nodeid, drop the data

                for p in parents:

                    if len(p) != 20:

                        parents = None

                        break

            except TypeError:

                # if content cannot be translated to nodeid drop the data.

                parents = None

        metadata = tuple(sorted(metadata.iteritems()))

        yield (pre, sucs, flags, metadata, date, parents)

def _fm0encodeonemarker(marker):

    pre, sucs, flags, metadata, date, parents = marker

    if flags & usingsha256:

        raise util.Abort(_('cannot handle sha256 with old obsstore format'))

    metadata = dict(metadata)

    metadata['date'] = '%d %i' % date

    if parents is not None:

        if not parents:

            # mark that we explicitly recorded no parents

            metadata['p0'] = ''

        for i, p in enumerate(parents):

            metadata['p%i' % (i + 1)] = node.hex(p)

    metadata = _fm0encodemeta(metadata)

    numsuc = len(sucs)

    format = _fm0fixed + (_fm0node * numsuc)

    data = [numsuc, len(metadata), flags, pre]

    data.extend(sucs)

    return _pack(format, *data) + metadata

def _fm0encodemeta(meta):

    """Return encoded metadata string to string mapping.

    Assume no ':' in key and no '\0' in both key and value."""

    for key, value in meta.iteritems():

        if ':' in key or '\0' in key:

            raise ValueError("':' and '\0' are forbidden in metadata key'")

        if '\0' in value:

            raise ValueError("':' is forbidden in metadata value'")

    return '\0'.join(['%s:%s' % (k, meta[k]) for k in sorted(meta)])

def _fm0decodemeta(data):

    """Return string to string dictionary from encoded version."""

    d = {}

    for l in data.split('\0'):

        if l:

            key, value = l.split(':')

            d[key] = value

    return d

## Parsing and writing of version "1"

#

# The header is followed by the markers. Each marker is made of:

#

# - uint32: total size of the marker (including this field)

#

# - float64: date in seconds since epoch

#

# - int16: timezone offset in minutes

#

# - uint16: a bit field. It is reserved for flags used in common

#   obsolete marker operations, to avoid repeated decoding of metadata

#   entries.

#

# - uint8: number of successors "N", can be zero.

#

# - uint8: number of parents "P", can be zero.

#

#     0: parents data stored but no parent,

#     1: one parent stored,

#     2: two parents stored,

#     3: no parent data stored

#

# - uint8: number of metadata entries M

#

# - 20 or 32 bytes: precursor changeset identifier.

#

# - N*(20 or 32) bytes: successors changesets identifiers.

#

# - P*(20 or 32) bytes: parents of the precursors changesets.

#

# - M*(uint8, uint8): size of all metadata entries (key and value)

#

# - remaining bytes: the metadata, each (key, value) pair after the other.

_fm1version = 1

_fm1fixed = '>IdhHBBB20s'

_fm1nodesha1 = '20s'

_fm1nodesha256 = '32s'

_fm1fsize = struct.calcsize(_fm1fixed)

_fm1parentnone = 3

_fm1parentshift = 14

_fm1parentmask = (_fm1parentnone << _fm1parentshift)

_fm1metapair = 'BB'

_fm1metapairsize = struct.calcsize('BB')

def _fm1readmarkers(data, off=0):

    # Loop on markers

    l = len(data)

    while off + _fm1fsize <= l:

        # read fixed part

        cur = data[off:off + _fm1fsize]

        off += _fm1fsize

        fixeddata = _unpack(_fm1fixed, cur)

        ttsize, seconds, tz, flags, numsuc, numpar, nummeta, prec = fixeddata

        # extract the number of parents information

        if numpar == _fm1parentnone:

            numpar = None

        # build the date tuple (upgrade tz minutes to seconds)

        date = (seconds, tz * 60)

        _fm1node = _fm1nodesha1

        if flags & usingsha256:

            _fm1node = _fm1nodesha256

        fnodesize = struct.calcsize(_fm1node)

        # read replacement

        sucs = ()

        if numsuc:

            s = (fnodesize * numsuc)

            cur = data[off:off + s]

            sucs = _unpack(_fm1node * numsuc, cur)

            off += s

        # read parents

        if numpar is None:

            parents = None

        elif numpar == 0:

            parents = ()

        elif numpar:  # neither None nor zero

            s = (fnodesize * numpar)

            cur = data[off:off + s]

            parents = _unpack(_fm1node * numpar, cur)

            off += s

        # read metadata

        metaformat = '>' + (_fm1metapair * nummeta)

        s = _fm1metapairsize * nummeta

        metapairsize = _unpack(metaformat, data[off:off + s])

        off += s

        metadata = []

        for idx in xrange(0, len(metapairsize), 2):

            sk = metapairsize[idx]

            sv = metapairsize[idx + 1]

            key = data[off:off + sk]

            value = data[off + sk:off + sk + sv]

            assert len(key) == sk

            assert len(value) == sv

            metadata.append((key, value))

            off += sk + sv

        metadata = tuple(metadata)

        yield (prec, sucs, flags, metadata, date, parents)

def _fm1encodeonemarker(marker):

    pre, sucs, flags, metadata, date, parents = marker

    # determine node size

    _fm1node = _fm1nodesha1

    if flags & usingsha256:

        _fm1node = _fm1nodesha256

    numsuc = len(sucs)

    numextranodes = numsuc

    if parents is None:

        numpar = _fm1parentnone

    else:

        numpar = len(parents)

        numextranodes += numpar

    formatnodes = _fm1node * numextranodes

    formatmeta = _fm1metapair * len(metadata)

    format = _fm1fixed + formatnodes + formatmeta

    # tz is stored in minutes so we divide by 60

    tz = date[1]//60

    data = [None, date[0], tz, flags, numsuc, numpar, len(metadata), pre]

    data.extend(sucs)

    if parents is not None:

        data.extend(parents)

    totalsize = struct.calcsize(format)

    for key, value in metadata:

        lk = len(key)

        lv = len(value)

        data.append(lk)

        data.append(lv)

        totalsize += lk + lv

    data[0] = totalsize

    data = [_pack(format, *data)]

    for key, value in metadata:

        data.append(key)

        data.append(value)

    return ''.join(data)

# mapping to read/write various marker formats

# <version> -> (decoder, encoder)

formats = {_fm0version: (_fm0readmarkers, _fm0encodeonemarker),

           _fm1version: (_fm1readmarkers, _fm1encodeonemarker)}

def _readmarkers(data):

    """Read and enumerate markers from raw data"""

    off = 0

    diskversion = _unpack('>B', data[off:off + 1])[0]

    off += 1

    if diskversion not in formats:

        raise util.Abort(_('parsing obsolete marker: unknown version %r')

                         % diskversion)

    return diskversion, formats[diskversion][0](data, off)

def encodemarkers(markers, addheader=False, version=_fm0version):

    # Kept separate from flushmarkers(), it will be reused for

    # markers exchange.

    encodeone = formats[version][1]

    if addheader:

        yield _pack('>B', version)

    for marker in markers:

        yield encodeone(marker)

class marker(object):

    """Wrap obsolete marker raw data"""