# branchmap.py - logic to computes, maintain and stores branchmap for local repo

#

# 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 struct

from .node import (

    bin,

    hex,

    nullid,

    nullrev,

)

from . import (

    encoding,

    error,

    pycompat,

    scmutil,

    util,

)

from .utils import (

    stringutil,

)

calcsize = struct.calcsize

pack_into = struct.pack_into

unpack_from = struct.unpack_from

### Nearest subset relation

# Nearest subset of filter X is a filter Y so that:

# * Y is included in X,

# * X - Y is as small as possible.

# This create and ordering used for branchmap purpose.

# the ordering may be partial

subsettable = {None: 'visible',

               'visible-hidden': 'visible',

               'visible': 'served',

               'served': 'immutable',

               'immutable': 'base'}

class BranchMapCache(object):

    """mapping of filtered views of repo with their branchcache"""

    def __init__(self):

        self._per_filter = {}

    def __getitem__(self, repo):

        self.updatecache(repo)

        return self._per_filter[repo.filtername]

    def updatecache(self, repo):

        """Update the cache for the given filtered view on a repository"""

        # This can trigger updates for the caches for subsets of the filtered

        # view, e.g. when there is no cache for this filtered view or the cache

        # is stale.

        cl = repo.changelog

        filtername = repo.filtername

        bcache = self._per_filter.get(filtername)

        if bcache is None or not bcache.validfor(repo):

            # cache object missing or cache object stale? Read from disk

            bcache = branchcache.fromfile(repo)

        revs = []

        if bcache is None:

            # no (fresh) cache available anymore, perhaps we can re-use

            # the cache for a subset, then extend that to add info on missing

            # revisions.

            subsetname = subsettable.get(filtername)

            if subsetname is not None:

                subset = repo.filtered(subsetname)

                bcache = self[subset].copy()

                extrarevs = subset.changelog.filteredrevs - cl.filteredrevs

                revs.extend(r for r in extrarevs if r <= bcache.tiprev)

            else:

                # nothing to fall back on, start empty.

                bcache = branchcache()

        revs.extend(cl.revs(start=bcache.tiprev + 1))

        if revs:

            bcache.update(repo, revs)

        assert bcache.validfor(repo), filtername

        self._per_filter[repo.filtername] = bcache

    def replace(self, repo, remotebranchmap):

        """Replace the branchmap cache for a repo with a branch mapping.

        This is likely only called during clone with a branch map from a

        remote.

        """

        cl = repo.changelog

        clrev = cl.rev

        clbranchinfo = cl.branchinfo

        rbheads = []

        closed = []

        for bheads in remotebranchmap.itervalues():

            rbheads += bheads

            for h in bheads:

                r = clrev(h)

                b, c = clbranchinfo(r)

                if c:

                    closed.append(h)

        if rbheads:

            rtiprev = max((int(clrev(node)) for node in rbheads))

            cache = branchcache(

                remotebranchmap, repo[rtiprev].node(), rtiprev,

                closednodes=closed)

            # Try to stick it as low as possible

            # filter above served are unlikely to be fetch from a clone

            for candidate in ('base', 'immutable', 'served'):

                rview = repo.filtered(candidate)

                if cache.validfor(rview):

                    self._per_filter[candidate] = cache

                    cache.write(rview)

                    return

    def clear(self):

        self._per_filter.clear()

    """A dict like object that hold branches heads cache.

    This cache is used to avoid costly computations to determine all the

    branch heads of a repo.

    The cache is serialized on disk in the following format:

    <tip hex node> <tip rev number> [optional filtered repo hex hash]

    <branch head hex node> <open/closed state> <branch name>

    <branch head hex node> <open/closed state> <branch name>

    ...

    The first line is used to check if the cache is still valid. If the

    branch cache is for a filtered repo view, an optional third hash is

    included that hashes the hashes of all filtered revisions.

    The open/closed state is represented by a single letter 'o' or 'c'.

    This field can be used to avoid changelog reads when determining if a

    branch head closes a branch or not.

    """

    def __init__(self, entries=(), tipnode=nullid, tiprev=nullrev,

                 filteredhash=None, closednodes=None):

        self.tipnode = tipnode

        self.tiprev = tiprev

        self.filteredhash = filteredhash

        # closednodes is a set of nodes that close their branch. If the branch

        # cache has been updated, it may contain nodes that are no longer

        # heads.

        if closednodes is None:

            self._closednodes = set()

        else:

            self._closednodes = closednodes

    @classmethod

    def fromfile(cls, repo):

        f = None

        try:

            f = repo.cachevfs(cls._filename(repo))

            lineiter = iter(f)

            cachekey = next(lineiter).rstrip('\n').split(" ", 2)

            last, lrev = cachekey[:2]

            last, lrev = bin(last), int(lrev)

            filteredhash = None

            if len(cachekey) > 2:

                filteredhash = bin(cachekey[2])

            bcache = cls(tipnode=last, tiprev=lrev, filteredhash=filteredhash)

            if not bcache.validfor(repo):

                # invalidate the cache

                raise ValueError(r'tip differs')

            bcache.load(repo, lineiter)

        except (IOError, OSError):

            return None

        except Exception as inst:

            if repo.ui.debugflag:

                msg = 'invalid branchheads cache'

                if repo.filtername is not None:

                    msg += ' (%s)' % repo.filtername

                msg += ': %s\n'

                repo.ui.debug(msg % pycompat.bytestr(inst))

            bcache = None

        finally:

            if f:

                f.close()

        return bcache

    def load(self, repo, lineiter):

        """ fully loads the branchcache by reading from the file using the line

        iterator passed"""

        cl = repo.changelog

        for line in lineiter:

            line = line.rstrip('\n')

            if not line:

                continue

            node, state, label = line.split(" ", 2)

            if state not in 'oc':

                raise ValueError(r'invalid branch state')

            label = encoding.tolocal(label.strip())

            node = bin(node)

            if not cl.hasnode(node):

                raise ValueError(

                    r'node %s does not exist' % pycompat.sysstr(hex(node)))

            self.setdefault(label, []).append(node)

            if state == 'c':

                self._closednodes.add(node)

    @staticmethod

    def _filename(repo):

        """name of a branchcache file for a given repo or repoview"""

        filename = "branch2"

        if repo.filtername:

            filename = '%s-%s' % (filename, repo.filtername)

        return filename

    def validfor(self, repo):

        """Is the cache content valid regarding a repo

        - False when cached tipnode is unknown or if we detect a strip.

        - True when cache is up to date or a subset of current repo."""

        try:

            return ((self.tipnode == repo.changelog.node(self.tiprev))

                    and (self.filteredhash ==

                         scmutil.filteredhash(repo, self.tiprev)))

        except IndexError:

            return False

    def _branchtip(self, heads):

        '''Return tuple with last open head in heads and false,

        otherwise return last closed head and true.'''

        tip = heads[-1]

        closed = True

        for h in reversed(heads):

            if h not in self._closednodes:

                tip = h

                closed = False

                break

        return tip, closed

    def branchtip(self, branch):

        '''Return the tipmost open head on branch head, otherwise return the

        tipmost closed head on branch.

        Raise KeyError for unknown branch.'''

        return self._branchtip(self[branch])[0]

    def iteropen(self, nodes):

        return (n for n in nodes if n not in self._closednodes)

    def branchheads(self, branch, closed=False):

        heads = self[branch]

        if not closed:

            heads = list(self.iteropen(heads))

        return heads

    def iterbranches(self):

        for bn, heads in self.iteritems():

            yield (bn, heads) + self._branchtip(heads)

    def copy(self):

        """return an deep copy of the branchcache object"""

            self._closednodes)

    def write(self, repo):

        try:

            f = repo.cachevfs(self._filename(repo), "w", atomictemp=True)

            cachekey = [hex(self.tipnode), '%d' % self.tiprev]

            if self.filteredhash is not None:

                cachekey.append(hex(self.filteredhash))

            f.write(" ".join(cachekey) + '\n')

            nodecount = 0

            for label, nodes in sorted(self.iteritems()):

                label = encoding.fromlocal(label)

                for node in nodes:

                    nodecount += 1

                    if node in self._closednodes:

                        state = 'c'

                    else:

                        state = 'o'

                    f.write("%s %s %s\n" % (hex(node), state, label))

            f.close()

            repo.ui.log('branchcache',

                        'wrote %s branch cache with %d labels and %d nodes\n',

        except (IOError, OSError, error.Abort) as inst:

            # Abort may be raised by read only opener, so log and continue

            repo.ui.debug("couldn't write branch cache: %s\n" %

                          stringutil.forcebytestr(inst))

    def update(self, repo, revgen):

        """Given a branchhead cache, self, that may have extra nodes or be

        missing heads, and a generator of nodes that are strictly a superset of

        heads missing, this function updates self to be correct.

        """

        starttime = util.timer()

        cl = repo.changelog

        # collect new branch entries

        newbranches = {}

        getbranchinfo = repo.revbranchcache().branchinfo

        for r in revgen:

            branch, closesbranch = getbranchinfo(r)

            newbranches.setdefault(branch, []).append(r)

            if closesbranch:

                self._closednodes.add(cl.node(r))

        # fetch current topological heads to speed up filtering

        topoheads = set(cl.headrevs())

        # if older branchheads are reachable from new ones, they aren't

        # really branchheads. Note checking parents is insufficient:

        # 1 (branch a) -> 2 (branch b) -> 3 (branch a)

        for branch, newheadrevs in newbranches.iteritems():

            bheads = self.setdefault(branch, [])

            bheadset = set(cl.rev(node) for node in bheads)

            # This have been tested True on all internal usage of this function.

            # run it again in case of doubt

            # assert not (set(bheadrevs) & set(newheadrevs))

            bheadset.update(newheadrevs)

            # This prunes out two kinds of heads - heads that are superseded by

            # a head in newheadrevs, and newheadrevs that are not heads because

            # an existing head is their descendant.

            uncertain = bheadset - topoheads

            if uncertain:

                floorrev = min(uncertain)

                ancestors = set(cl.ancestors(newheadrevs, floorrev))

                bheadset -= ancestors

            bheadrevs = sorted(bheadset)

            self[branch] = [cl.node(rev) for rev in bheadrevs]

            tiprev = bheadrevs[-1]

            if tiprev > self.tiprev:

                self.tipnode = cl.node(tiprev)

                self.tiprev = tiprev

        if not self.validfor(repo):

            # cache key are not valid anymore

            self.tipnode = nullid

            self.tiprev = nullrev

                tiprev = max(cl.rev(node) for node in heads)

                if tiprev > self.tiprev:

                    self.tipnode = cl.node(tiprev)

                    self.tiprev = tiprev

        self.filteredhash = scmutil.filteredhash(repo, self.tiprev)

        duration = util.timer() - starttime

        repo.ui.log('branchcache', 'updated %s branch cache in %.4f seconds\n',

                    repo.filtername or b'None', duration)

        self.write(repo)

class remotebranchcache(branchcache):

    """Branchmap info for a remote connection, should not write locally"""

    def write(self, repo):

        pass

# Revision branch info cache

_rbcversion = '-v1'

_rbcnames = 'rbc-names' + _rbcversion

_rbcrevs = 'rbc-revs' + _rbcversion

# [4 byte hash prefix][4 byte branch name number with sign bit indicating open]

_rbcrecfmt = '>4sI'

_rbcrecsize = calcsize(_rbcrecfmt)

_rbcnodelen = 4

_rbcbranchidxmask = 0x7fffffff

_rbccloseflag = 0x80000000

class revbranchcache(object):

    """Persistent cache, mapping from revision number to branch name and close.

    This is a low level cache, independent of filtering.

    Branch names are stored in rbc-names in internal encoding separated by 0.

    rbc-names is append-only, and each branch name is only stored once and will

    thus have a unique index.

    The branch info for each revision is stored in rbc-revs as constant size

    records. The whole file is read into memory, but it is only 'parsed' on

    demand. The file is usually append-only but will be truncated if repo

    modification is detected.

    The record for each revision contains the first 4 bytes of the

    corresponding node hash, and the record is only used if it still matches.

    Even a completely trashed rbc-revs fill thus still give the right result

    while converging towards full recovery ... assuming no incorrectly matching

    node hashes.

    The record also contains 4 bytes where 31 bits contains the index of the

    branch and the last bit indicate that it is a branch close commit.

    The usage pattern for rbc-revs is thus somewhat similar to 00changelog.i

    and will grow with it but be 1/8th of its size.

    """

    def __init__(self, repo, readonly=True):

        assert repo.filtername is None

        self._repo = repo

        self._names = [] # branch names in local encoding with static index

        self._rbcrevs = bytearray()

        self._rbcsnameslen = 0 # length of names read at _rbcsnameslen

        try:

            bndata = repo.cachevfs.read(_rbcnames)

            self._rbcsnameslen = len(bndata) # for verification before writing

            if bndata:

                self._names = [encoding.tolocal(bn)

                               for bn in bndata.split('\0')]

        except (IOError, OSError):

            if readonly:

                # don't try to use cache - fall back to the slow path

                self.branchinfo = self._branchinfo

        if self._names:

            try:

                data = repo.cachevfs.read(_rbcrevs)

                self._rbcrevs[:] = data

            except (IOError, OSError) as inst:

                repo.ui.debug("couldn't read revision branch cache: %s\n" %

                              stringutil.forcebytestr(inst))

        # remember number of good records on disk

        self._rbcrevslen = min(len(self._rbcrevs) // _rbcrecsize,

                               len(repo.changelog))

        if self._rbcrevslen == 0:

            self._names = []

        self._rbcnamescount = len(self._names) # number of names read at

                                               # _rbcsnameslen

    def _clear(self):

        self._rbcsnameslen = 0

        del self._names[:]

        self._rbcnamescount = 0

        self._rbcrevslen = len(self._repo.changelog)

        self._rbcrevs = bytearray(self._rbcrevslen * _rbcrecsize)

        util.clearcachedproperty(self, '_namesreverse')

    @util.propertycache

    def _namesreverse(self):

        return dict((b, r) for r, b in enumerate(self._names))

    def branchinfo(self, rev):

        """Return branch name and close flag for rev, using and updating

        persistent cache."""

        changelog = self._repo.changelog

        rbcrevidx = rev * _rbcrecsize

        # avoid negative index, changelog.read(nullrev) is fast without cache

        if rev == nullrev:

            return changelog.branchinfo(rev)

        # if requested rev isn't allocated, grow and cache the rev info

        if len(self._rbcrevs) < rbcrevidx + _rbcrecsize:

            return self._branchinfo(rev)

        # fast path: extract data from cache, use it if node is matching