~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2009 Canonical Ltd

#

# This program is free software; you can redistribute it and/or modify

# it under the terms of the GNU General Public License as published by

# the Free Software Foundation; either version 2 of the License, or

# (at your option) any later version.

#

# This program is distributed in the hope that it will be useful,

# but WITHOUT ANY WARRANTY; without even the implied warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

# GNU General Public License for more details.

#

# You should have received a copy of the GNU General Public License

# along with this program; if not, write to the Free Software

# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

"""Implementation of Graph algorithms when we have already loaded everything.

"""

from bzrlib import (

    errors,

    revision,

    )

class _KnownGraphNode(object):

    """Represents a single object in the known graph."""

    __slots__ = ('key', 'parent_keys', 'child_keys', 'gdfo')

    def __init__(self, key, parent_keys):

        self.key = key

        self.parent_keys = parent_keys

        self.child_keys = []

        # Greatest distance from origin

        self.gdfo = None

    def __repr__(self):

        return '%s(%s  gdfo:%s par:%s child:%s)' % (

            self.__class__.__name__, self.key, self.gdfo,

            self.parent_keys, self.child_keys)

class _MergeSortNode(object):

    """Information about a specific node in the merge graph."""

    __slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge')

    def __init__(self, key, merge_depth, revno, end_of_merge):

        self.key = key

        self.merge_depth = merge_depth

        self.revno = revno

        self.end_of_merge = end_of_merge

class KnownGraph(object):

    """This is a class which assumes we already know the full graph."""

    def __init__(self, parent_map, do_cache=True):

        """Create a new KnownGraph instance.

        :param parent_map: A dictionary mapping key => parent_keys

        """

        self._nodes = {}

        # Maps {sorted(revision_id, revision_id): heads}

        self._known_heads = {}

        self.do_cache = do_cache

        self._initialize_nodes(parent_map)

        self._find_gdfo()

    def _initialize_nodes(self, parent_map):

        """Populate self._nodes.

        After this has finished:

        - self._nodes will have an entry for every entry in parent_map.

        - ghosts will have a parent_keys = None,

        - all nodes found will also have .child_keys populated with all known

          child_keys,

        """

        nodes = self._nodes

        for key, parent_keys in parent_map.iteritems():

            if key in nodes:

                node = nodes[key]

                node.parent_keys = parent_keys

            else:

                node = _KnownGraphNode(key, parent_keys)

                nodes[key] = node

            for parent_key in parent_keys:

                try:

                    parent_node = nodes[parent_key]

                except KeyError:

                    parent_node = _KnownGraphNode(parent_key, None)

                    nodes[parent_key] = parent_node

                parent_node.child_keys.append(key)

    def _find_tails(self):

        return [node for node in self._nodes.itervalues()

                if not node.parent_keys]

    def _find_gdfo(self):

        nodes = self._nodes

        known_parent_gdfos = {}

        pending = []

        for node in self._find_tails():

            node.gdfo = 1

            pending.append(node)

        while pending:

            node = pending.pop()

            for child_key in node.child_keys:

                child = nodes[child_key]

                if child_key in known_parent_gdfos:

                    known_gdfo = known_parent_gdfos[child_key] + 1

                    present = True

                else:

                    known_gdfo = 1

                    present = False

                if child.gdfo is None or node.gdfo + 1 > child.gdfo:

                    child.gdfo = node.gdfo + 1

                if known_gdfo == len(child.parent_keys):

                    # We are the last parent updating that node, we can

                    # continue from there

                    pending.append(child)

                    if present:

                        del known_parent_gdfos[child_key]

                else:

                    # Update known_parent_gdfos for a key we couldn't process

                    known_parent_gdfos[child_key] = known_gdfo

    def heads(self, keys):

        """Return the heads from amongst keys.

        This is done by searching the ancestries of each key.  Any key that is

        reachable from another key is not returned; all the others are.

        This operation scales with the relative depth between any two keys. It

        uses gdfo to avoid walking all ancestry.

        :param keys: An iterable of keys.

        :return: A set of the heads. Note that as a set there is no ordering

            information. Callers will need to filter their input to create

            order if they need it.

        """

        candidate_nodes = dict((key, self._nodes[key]) for key in keys)

        if revision.NULL_REVISION in candidate_nodes:

            # NULL_REVISION is only a head if it is the only entry

            candidate_nodes.pop(revision.NULL_REVISION)

            if not candidate_nodes:

                return frozenset([revision.NULL_REVISION])

        if len(candidate_nodes) < 2:

            # No or only one candidate

            return frozenset(candidate_nodes)

        heads_key = frozenset(candidate_nodes)

        # Do we have a cached result ?

        try:

            heads = self._known_heads[heads_key]

            return heads

        except KeyError:

            pass

        # Let's compute the heads

        seen = set()

        pending = []

        min_gdfo = None

        for node in candidate_nodes.values():

            if node.parent_keys:

                pending.extend(node.parent_keys)

            if min_gdfo is None or node.gdfo < min_gdfo:

                min_gdfo = node.gdfo

        nodes = self._nodes

        while pending:

            node_key = pending.pop()

            if node_key in seen:

                # node already appears in some ancestry

                continue

            seen.add(node_key)

            node = nodes[node_key]

            if node.gdfo <= min_gdfo:

                continue

            if node.parent_keys:

                pending.extend(node.parent_keys)

        heads = heads_key.difference(seen)

        if self.do_cache:

            self._known_heads[heads_key] = heads

        return heads

    def topo_sort(self):

        """Return the nodes in topological order.

        All parents must occur before all children.

        """

        for node in self._nodes.itervalues():

            if node.gdfo is None:

                raise errors.GraphCycleError(self._nodes)

        pending = self._find_tails()

        pending_pop = pending.pop

        pending_append = pending.append

        topo_order = []

        topo_order_append = topo_order.append

        num_seen_parents = dict.fromkeys(self._nodes, 0)

        while pending:

            node = pending_pop()

            if node.parent_keys is not None:

                # We don't include ghost parents

                topo_order_append(node.key)

            for child_key in node.child_keys:

                child_node = self._nodes[child_key]

                seen_parents = num_seen_parents[child_key] + 1

                if seen_parents == len(child_node.parent_keys):

                    # All parents have been processed, enqueue this child

                    pending_append(child_node)

                    # This has been queued up, stop tracking it

                    del num_seen_parents[child_key]

                else:

                    num_seen_parents[child_key] = seen_parents

        # We started from the parents, so we don't need to do anymore work

        return topo_order

    def merge_sort(self, tip_key):

        """Compute the merge sorted graph output."""

        from bzrlib import tsort

        as_parent_map = dict((node.key, node.parent_keys)

                             for node in self._nodes.itervalues()

                              if node.parent_keys is not None)

        # We intentionally always generate revnos and never force the

        # mainline_revisions

        # Strip the sequence_number that merge_sort generates

        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)

                for _, key, merge_depth, revno, end_of_merge

                 in tsort.merge_sort(as_parent_map, tip_key,

                                     mainline_revisions=None,

                                     generate_revno=True)]