# 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 node import bin, hex, nullid, nullrev

import encoding

def read(repo):

    try:

        f = repo.opener("cache/branchheads")

        lines = f.read().split('\n')

        f.close()

    except (IOError, OSError):

        return branchcache()

    try:

        last, lrev = lines.pop(0).split(" ", 1)

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

        partial = branchcache(tipnode=last, tiprev=lrev)

        if not partial.validfor(repo):

            # invalidate the cache

            raise ValueError('tip differs')

        for l in lines:

            if not l:

                continue

            node, label = l.split(" ", 1)

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

            if not node in repo:

                raise ValueError('node %s does not exist' % node)

            partial.setdefault(label, []).append(bin(node))

    except KeyboardInterrupt:

        raise

    except Exception, inst:

        if repo.ui.debugflag:

            repo.ui.warn(('invalid branchheads cache: %s\n') % inst)

        partial = branchcache()

    return partial

def updatecache(repo):

    repo = repo.unfiltered()  # Until we get a smarter cache management

    cl = repo.changelog

    partial = repo._branchcache

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

        partial = read(repo)

    catip = repo._cacheabletip()

    # if partial.tiprev == catip: cache is already up to date

    # if partial.tiprev >  catip: we have uncachable element in `partial` can't

    #                             write on disk

    if partial.tiprev < catip:

        ctxgen = (repo[r] for r in cl.revs(partial.tiprev + 1, catip))

        partial.update(repo, ctxgen)

        partial.write(repo)

    # If cacheable tip were lower than actual tip, we need to update the

    # cache up to tip. This update (from cacheable to actual tip) is not

    # written to disk since it's not cacheable.

    if partial.tiprev < tiprev:

        ctxgen = (repo[r] for r in cl.revs(partial.tiprev + 1, tiprev))

        partial.update(repo, ctxgen)

    repo._branchcache = partial

class branchcache(dict):

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

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

        super(branchcache, self).__init__(entries)

        self.tipnode = tipnode

        self.tiprev = tiprev

    def validfor(self, repo):

        """Is the cache content valide regarding a repo

        - False when cached tipnode are 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)

        except IndexError:

            return False

    def write(self, repo):

        try:

            f = repo.opener("cache/branchheads", "w", atomictemp=True)

            f.write("%s %s\n" % (hex(self.tipnode), self.tiprev))

            for label, nodes in self.iteritems():

                for node in nodes:

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

            f.close()

        except (IOError, OSError):

            pass

    def update(self, repo, ctxgen):

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

        missing heads, and a generator of nodes that are at least a superset of

        heads missing, this function updates self to be correct.

        """

        cl = repo.changelog

        # collect new branch entries

        newbranches = {}

        for c in ctxgen:

            newbranches.setdefault(c.branch(), []).append(c.node())

        # 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, newnodes in newbranches.iteritems():

            bheads = self.setdefault(branch, [])

            # Remove candidate heads that no longer are in the repo (e.g., as

            # the result of a strip that just happened).  Avoid using 'node in

            # self' here because that dives down into branchcache code somewhat

            # recursively.

            bheadrevs = [cl.rev(node) for node in bheads

                         if cl.hasnode(node)]

            newheadrevs = [cl.rev(node) for node in newnodes

                           if cl.hasnode(node)]

            ctxisnew = bheadrevs and min(newheadrevs) > max(bheadrevs)

            # Remove duplicates - nodes that are in newheadrevs and are already

            # in bheadrevs.  This can happen if you strip a node whose parent

            # was already a head (because they're on different branches).

            bheadrevs = sorted(set(bheadrevs).union(newheadrevs))

            # Starting from tip means fewer passes over reachable.  If we know

            # the new candidates are not ancestors of existing heads, we don't

            # have to examine ancestors of existing heads

            if ctxisnew:

                iterrevs = sorted(newheadrevs)

            else:

                iterrevs = list(bheadrevs)

            # This loop 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.

            while iterrevs:

                latest = iterrevs.pop()

                if latest not in bheadrevs:

                    continue

                ancestors = set(cl.ancestors([latest],

                                                         bheadrevs[0]))

                if ancestors:

                    bheadrevs = [b for b in bheadrevs if b not in ancestors]

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

            tiprev = max(bheadrevs)

            if tiprev > self.tiprev:

                self.tipnode = cl.node(tiprev)

                self.tiprev = tiprev

        # There may be branches that cease to exist when the last commit in the

        # branch was stripped.  This code filters them out.  Note that the

        # branch that ceased to exist may not be in newbranches because

        # newbranches is the set of candidate heads, which when you strip the

        # last commit in a branch will be the parent branch.

        droppednodes = []

        for branch in self.keys():

            nodes = [head for head in self[branch]

                     if cl.hasnode(head)]

            if not nodes:

                droppednodes.extend(nodes)

                del self[branch]

        if ((not self.validfor(repo)) or (self.tipnode in droppednodes)):

            # cache key are not valid anymore

            self.tipnode = nullid

            self.tiprev = nullrev

            for heads in self.values():

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

                if tiprev > self.tiprev:

                    self.tipnode = cl.node(tiprev)

                    self.tiprev = tiprev