~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.
"""

cdef extern from "python-compat.h":
    pass

cdef extern from "Python.h":
    ctypedef int Py_ssize_t
    ctypedef struct PyObject:
        pass

    object PyFrozenSet_New(object)
    object PyTuple_New(Py_ssize_t n)
    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
    Py_ssize_t PyTuple_GET_SIZE(object t)
    PyObject * PyDict_GetItem(object d, object k)
    PyObject * PyDict_GetItem(object d, object k)
    Py_ssize_t PyDict_Size(object d) except -1
    int PyDict_CheckExact(object d)
    int PyDict_Next(object d, Py_ssize_t *pos, PyObject **k, PyObject **v)
    int PyList_Append(object l, object v) except -1
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
    Py_ssize_t PyList_GET_SIZE(object l)
    int PyDict_SetItem(object d, object k, object v) except -1
    int PySet_Add(object s, object k) except -1
    void Py_INCREF(object)


import heapq

from bzrlib import revision

# Define these as cdef objects, so we don't have to getattr them later
cdef object heappush, heappop, heapify, heapreplace
heappush = heapq.heappush
heappop = heapq.heappop
heapify = heapq.heapify
heapreplace = heapq.heapreplace


cdef class _KnownGraphNode:
    """Represents a single object in the known graph."""

    cdef object key
    cdef object parents
    cdef object children
    cdef _KnownGraphNode linear_dominator_node
    cdef public long dominator_distance
    cdef public object gdfo # Int
    # This could also be simplified
    cdef object ancestor_of

    def __init__(self, key):
        cdef int i

        self.key = key
        self.parents = None

        self.children = []
        # oldest ancestor, such that no parents between here and there have >1
        # child or >1 parent.
        self.linear_dominator_node = None
        self.dominator_distance = 0
        # Greatest distance from origin
        self.gdfo = -1
        # This will become a tuple of known heads that have this node as an
        # ancestor
        self.ancestor_of = None

    property child_keys:
        def __get__(self):
            cdef _KnownGraphNode child

            keys = []
            for child in self.children:
                PyList_Append(keys, child.key)
            return keys

    property linear_dominator:
        def __get__(self):
            if self.linear_dominator_node is None:
                return None
            else:
                return self.linear_dominator_node.key

    cdef clear_references(self):
        self.parents = None
        self.children = None
        self.linear_dominator_node = None

    def __repr__(self):
        cdef _KnownGraphNode node

        parent_keys = []
        if self.parents is not None:
            for node in self.parents:
                parent_keys.append(node.key)
        child_keys = []
        if self.children is not None:
            for node in self.children:
                child_keys.append(node.key)
        return '%s(%s  gdfo:%s par:%s child:%s dom:%s %s)' % (
            self.__class__.__name__, self.key, self.gdfo,
            parent_keys, child_keys,
            self.linear_dominator, self.dominator_distance)


cdef _KnownGraphNode _get_list_node(lst, Py_ssize_t pos):
    cdef PyObject *temp_node

    temp_node = PyList_GET_ITEM(lst, pos)
    return <_KnownGraphNode>temp_node


cdef _KnownGraphNode _get_parent(parents, Py_ssize_t pos):
    cdef PyObject *temp_node
    cdef _KnownGraphNode node

    temp_node = PyTuple_GET_ITEM(parents, pos)
    return <_KnownGraphNode>temp_node


cdef _KnownGraphNode _peek_node(queue):
    cdef PyObject *temp_node
    cdef _KnownGraphNode node

    temp_node = PyTuple_GET_ITEM(<object>PyList_GET_ITEM(queue, 0), 1)
    node = <_KnownGraphNode>temp_node
    return node

# TODO: slab allocate all _KnownGraphNode objects.
#       We already know how many we are going to need, except for a couple of
#       ghosts that could be allocated on demand.

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

    cdef public object _nodes
    cdef object _known_heads
    cdef public int do_cache
    # Nodes we've touched that we'll need to reset their info when heads() is
    # done
    cdef object _to_cleanup

    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._to_cleanup = []
        self.do_cache = int(do_cache)
        self._initialize_nodes(parent_map)
        self._find_linear_dominators()
        self._find_gdfo()

    def __dealloc__(self):
        cdef _KnownGraphNode child
        cdef Py_ssize_t pos
        cdef PyObject *temp_node

        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
            child = <_KnownGraphNode>temp_node
            child.clear_references()

    cdef _KnownGraphNode _get_or_create_node(self, key):
        cdef PyObject *temp_node
        cdef _KnownGraphNode node

        temp_node = PyDict_GetItem(self._nodes, key)
        if temp_node == NULL:
            node = _KnownGraphNode(key)
            PyDict_SetItem(self._nodes, key, node)
        else:
            node = <_KnownGraphNode>temp_node
        return node

    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.
        """
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
        cdef Py_ssize_t pos, pos2, num_parent_keys
        cdef _KnownGraphNode node
        cdef _KnownGraphNode parent_node

        nodes = self._nodes

        if not PyDict_CheckExact(parent_map):
            raise TypeError('parent_map should be a dict of {key:parent_keys}')
        # for key, parent_keys in parent_map.iteritems():
        pos = 0
        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
            key = <object>temp_key
            parent_keys = <object>temp_parent_keys
            node = self._get_or_create_node(key)
            assert node.parents is None
            # We know how many parents, so we could pre allocate an exact sized
            # tuple here
            num_parent_keys = len(parent_keys)
            parent_nodes = PyTuple_New(num_parent_keys)
            # We use iter here, because parent_keys maybe be a list or tuple
            for pos2 from 0 <= pos2 < num_parent_keys:
                parent_key = parent_keys[pos2]
                parent_node = self._get_or_create_node(parent_keys[pos2])
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
                Py_INCREF(parent_node)
                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
                PyList_Append(parent_node.children, node)
            node.parents = parent_nodes

    cdef _KnownGraphNode _check_is_linear(self, _KnownGraphNode node):
        """Check to see if a given node is part of a linear chain."""
        cdef _KnownGraphNode parent_node
        if node.parents is None or PyTuple_GET_SIZE(node.parents) != 1:
            # This node is either a ghost, a tail, or has multiple parents
            # It its own dominator
            node.linear_dominator_node = node
            node.dominator_distance = 0
            return None
        parent_node = _get_parent(node.parents, 0)
        if PyList_GET_SIZE(parent_node.children) > 1:
            # The parent has multiple children, so *this* node is the
            # dominator
            node.linear_dominator_node = node
            node.dominator_distance = 0
            return None
        # The parent is already filled in, so add and continue
        if parent_node.linear_dominator_node is not None:
            node.linear_dominator_node = parent_node.linear_dominator_node
            node.dominator_distance = parent_node.dominator_distance + 1
            return None
        # We don't know this node, or its parent node, so start walking to
        # next
        return parent_node

    def _find_linear_dominators(self):
        """For each node in the set, find any linear dominators.

        For any given node, the 'linear dominator' is an ancestor, such that
        all parents between this node and that one have a single parent, and a
        single child. So if A->B->C->D then B,C,D all have a linear dominator
        of A. Because there are no interesting siblings, we can quickly skip to
        the nearest dominator when doing comparisons.
        """
        cdef PyObject *temp_node
        cdef Py_ssize_t pos
        cdef _KnownGraphNode node
        cdef _KnownGraphNode next_node
        cdef _KnownGraphNode dominator
        cdef int i, num_elements

        pos = 0
        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
            node = <_KnownGraphNode>temp_node
            # The parent is not filled in, so walk until we get somewhere
            if node.linear_dominator_node is not None: #already done
                continue
            next_node = self._check_is_linear(node)
            if next_node is None:
                # Nothing more needs to be done
                continue
            stack = []
            while next_node is not None:
                PyList_Append(stack, node)
                node = next_node
                next_node = self._check_is_linear(node)
            # The stack now contains the linear chain, and 'node' should have
            # been labeled
            assert node.linear_dominator_node is not None
            dominator = node.linear_dominator_node
            num_elements = len(stack)
            for i from num_elements > i >= 0:
                next_node = _get_list_node(stack, i)
                next_node.linear_dominator_node = dominator
                next_node.dominator_distance = node.dominator_distance + 1
                node = next_node

    cdef object _find_tails(self):
        cdef object tails
        cdef PyObject *temp_node
        cdef Py_ssize_t pos
        cdef _KnownGraphNode node

        tails = []
        pos = 0
        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
            node = <_KnownGraphNode>temp_node
            if node.parents is None or PyTuple_GET_SIZE(node.parents) == 0:
                PyList_Append(tails, node)
        return tails

    def _find_gdfo(self):
        cdef Py_ssize_t pos, pos2
        cdef _KnownGraphNode node
        cdef _KnownGraphNode child_node
        cdef _KnownGraphNode parent_node
        cdef int replace_node, missing_parent

        tails = self._find_tails()
        todo = []
        for pos from 0 <= pos < PyList_GET_SIZE(tails):
            node = _get_list_node(tails, pos)
            node.gdfo = 1
            PyList_Append(todo, (1, node))
        # No need to heapify, because all tails have priority=1
        max_gdfo = len(self._nodes) + 1
        while PyList_GET_SIZE(todo) > 0:
            node = _peek_node(todo)
            next_gdfo = node.gdfo + 1
            assert next_gdfo <= max_gdfo
            replace_node = 1
            for pos from 0 <= pos < PyList_GET_SIZE(node.children):
                child_node = _get_list_node(node.children, pos)
                # We should never have numbered children before we numbered
                # a parent
                if child_node.gdfo != -1:
                    assert child_node.gdfo >= next_gdfo
                    continue
                # Only enque children when all of their parents have been
                # resolved. With a single parent, we can just take 'this' value
                child_gdfo = next_gdfo
                if PyTuple_GET_SIZE(child_node.parents) > 1:
                    missing_parent = 0
                    for pos2 from 0 <= pos2 < PyTuple_GET_SIZE(child_node.parents):
                        parent_node = _get_parent(child_node.parents, pos2)
                        if parent_node.gdfo == -1:
                            missing_parent = 1
                            break
                        if parent_node.gdfo >= child_gdfo:
                            child_gdfo = parent_node.gdfo + 1
                    if missing_parent:
                        # One of the parents is not numbered, so wait until we get
                        # back here
                        continue
                child_node.gdfo = child_gdfo
                if replace_node:
                    heapreplace(todo, (child_gdfo, child_node))
                    replace_node = 0
                else:
                    heappush(todo, (child_gdfo, child_node))
            if replace_node:
                heappop(todo)

    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. If
        any two keys are completely disconnected all ancestry of both sides
        will be retrieved.

        :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.
        """
        cdef PyObject *maybe_node
        cdef PyObject *maybe_heads

        heads_key = PyFrozenSet_New(keys)
        maybe_heads = PyDict_GetItem(self._known_heads, heads_key)
        if maybe_heads != NULL:
            return <object>maybe_heads

        # Not cached, compute it ourselves
        candidate_nodes = {}
        nodes = self._nodes
        for key in keys:
            maybe_node = PyDict_GetItem(nodes, key)
            if maybe_node == NULL:
                raise KeyError('key %s not in nodes' % (key,))
            PyDict_SetItem(candidate_nodes, key, <object>maybe_node)
        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 set([revision.NULL_REVISION])
            # The keys changed, so recalculate heads_key
            heads_key = PyFrozenSet_New(candidate_nodes)
        if len(candidate_nodes) < 2:
            return heads_key
        dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
        if PyDict_Size(candidate_nodes) < 2:
            return frozenset(candidate_nodes)
        dom_lookup_key, heads = self._heads_from_dominators(candidate_nodes,
                                                            dom_to_node)
        if heads is not None:
            if self.do_cache:
                # This heads was not in the cache, or it would have been caught
                # earlier, but the dom head *was*, so do the simple cache
                PyDict_SetItem(self._known_heads, heads_key, heads)
            return heads
        heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_node)
        if self.do_cache:
            self._cache_heads(heads, heads_key, dom_lookup_key, candidate_nodes)
        return heads

    cdef object _cache_heads(self, heads, heads_key, dom_lookup_key,
                             candidate_nodes):
        cdef PyObject *maybe_node
        cdef _KnownGraphNode node

        PyDict_SetItem(self._known_heads, heads_key, heads)
        dom_heads = []
        for key in heads:
            maybe_node = PyDict_GetItem(candidate_nodes, key)
            if maybe_node == NULL:
                raise KeyError
            node = <_KnownGraphNode>maybe_node
            PyList_Append(dom_heads, node.linear_dominator_node.key)
        PyDict_SetItem(self._known_heads, dom_lookup_key,
                       PyFrozenSet_New(dom_heads))

    cdef _get_dominators_to_nodes(self, candidate_nodes):
        """Get the reverse mapping from dominator_key => candidate_nodes.

        As a side effect, this can also remove potential candidate nodes if we
        determine that they share a dominator.
        """
        cdef Py_ssize_t pos
        cdef _KnownGraphNode node, other_node
        cdef PyObject *temp_node
        cdef PyObject *maybe_node

        dom_to_node = {}
        keys_to_remove = []
        pos = 0
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
            node = <_KnownGraphNode>temp_node
            dom_key = node.linear_dominator_node.key
            maybe_node = PyDict_GetItem(dom_to_node, dom_key)
            if maybe_node == NULL:
                PyDict_SetItem(dom_to_node, dom_key, node)
            else:
                other_node = <_KnownGraphNode>maybe_node
                # These nodes share a dominator, one of them obviously
                # supersedes the other, figure out which
                if other_node.gdfo > node.gdfo:
                    PyList_Append(keys_to_remove, node.key)
                else:
                    # This wins, replace the other
                    PyList_Append(keys_to_remove, other_node.key)
                    PyDict_SetItem(dom_to_node, dom_key, node)
        for pos from 0 <= pos < PyList_GET_SIZE(keys_to_remove):
            key = <object>PyList_GET_ITEM(keys_to_remove, pos)
            candidate_nodes.pop(key)
        return dom_to_node

    cdef object _heads_from_dominators(self, candidate_nodes, dom_to_node):
        cdef PyObject *maybe_heads
        cdef PyObject *maybe_node
        cdef _KnownGraphNode node
        cdef Py_ssize_t pos
        cdef PyObject *temp_node

        dom_list_key = []
        pos = 0
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
            node = <_KnownGraphNode>temp_node
            PyList_Append(dom_list_key, node.linear_dominator_node.key)
        dom_lookup_key = PyFrozenSet_New(dom_list_key)
        maybe_heads = PyDict_GetItem(self._known_heads, dom_lookup_key)
        if maybe_heads == NULL:
            return dom_lookup_key, None
        # We need to map back from the dominator head to the original keys
        dom_heads = <object>maybe_heads
        heads = []
        for dom_key in dom_heads:
            maybe_node = PyDict_GetItem(dom_to_node, dom_key)
            if maybe_node == NULL:
                # Should never happen
                raise KeyError
            node = <_KnownGraphNode>maybe_node
            PyList_Append(heads, node.key)
        return dom_lookup_key, PyFrozenSet_New(heads)

    cdef int _process_parent(self, _KnownGraphNode node,
                             _KnownGraphNode parent_node,
                             candidate_nodes, dom_to_node,
                             queue, int *replace_item) except -1:
        """Process the parent of a node, seeing if we need to walk it."""
        cdef PyObject *maybe_candidate
        cdef PyObject *maybe_node
        cdef _KnownGraphNode dom_child_node
        maybe_candidate = PyDict_GetItem(candidate_nodes, parent_node.key)
        if maybe_candidate != NULL:
            candidate_nodes.pop(parent_node.key)
            # We could pass up a flag that tells the caller to stop processing,
            # but it doesn't help much, and makes the code uglier
            return 0
        maybe_node = PyDict_GetItem(dom_to_node, parent_node.key)
        if maybe_node != NULL:
            # This is a dominator of a node
            dom_child_node = <_KnownGraphNode>maybe_node
            if dom_child_node is not node:
                # It isn't a dominator of a node we are searching, so we should
                # remove it from the search
                maybe_candidate = PyDict_GetItem(candidate_nodes, dom_child_node.key)
                if maybe_candidate != NULL:
                    candidate_nodes.pop(dom_child_node.key)
                    return 0
        if parent_node.ancestor_of is None:
            # This node hasn't been walked yet, so just project node's ancestor
            # info directly to parent_node, and enqueue it for later processing
            parent_node.ancestor_of = node.ancestor_of
            if replace_item[0]:
                heapreplace(queue, (-parent_node.gdfo, parent_node))
                replace_item[0] = 0
            else:
                heappush(queue, (-parent_node.gdfo, parent_node))
            PyList_Append(self._to_cleanup, parent_node)
        elif parent_node.ancestor_of != node.ancestor_of:
            # Combine to get the full set of parents
            # Rewrite using PySet_* functions, unfortunately you have to use
            # PySet_Add since there is no PySet_Update... :(
            all_ancestors = set(parent_node.ancestor_of)
            for k in node.ancestor_of:
                PySet_Add(all_ancestors, k)
            parent_node.ancestor_of = tuple(sorted(all_ancestors))
        return 0

    cdef object _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
        cdef _KnownGraphNode node
        cdef _KnownGraphNode parent_node
        cdef Py_ssize_t num_candidates
        cdef int num_parents, replace_item
        cdef Py_ssize_t pos
        cdef PyObject *temp_node

        queue = []
        pos = 0
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
            node = <_KnownGraphNode>temp_node
            assert node.ancestor_of is None
            node.ancestor_of = (node.key,)
            PyList_Append(queue, (-node.gdfo, node))
            PyList_Append(self._to_cleanup, node)
        heapify(queue)
        # These are nodes that we determined are 'common' that we are no longer
        # walking
        # Now we walk nodes until all nodes that are being walked are 'common'
        num_candidates = len(candidate_nodes)
        replace_item = 0
        while PyList_GET_SIZE(queue) > 0 and PyDict_Size(candidate_nodes) > 1:
            if replace_item:
                # We still need to pop the smallest member out of the queue
                # before we peek again
                heappop(queue)
                if PyList_GET_SIZE(queue) == 0:
                    break
            # peek at the smallest item. We don't pop, because we expect we'll
            # need to push more things into the queue anyway
            node = _peek_node(queue)
            replace_item = 1
            if PyTuple_GET_SIZE(node.ancestor_of) == num_candidates:
                # This node is now considered 'common'
                # Make sure all parent nodes are marked as such
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
                    parent_node = _get_parent(node.parents, pos)
                    if parent_node.ancestor_of is not None:
                        parent_node.ancestor_of = node.ancestor_of
                if node.linear_dominator_node is not node:
                    parent_node = node.linear_dominator_node
                    if parent_node.ancestor_of is not None:
                        parent_node.ancestor_of = node.ancestor_of
                continue
            if node.parents is None:
                # This is a ghost
                continue
            # Now project the current nodes ancestor list to the parent nodes,
            # and queue them up to be walked
            if node.linear_dominator_node is not node:
                # We are at the tip of a long linear region
                # We know that there is nothing between here and the tail
                # that is interesting, so skip to the end
                self._process_parent(node, node.linear_dominator_node,
                                     candidate_nodes, dom_to_node, queue, &replace_item)
            else:
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
                    parent_node = _get_parent(node.parents, pos)
                    self._process_parent(node, parent_node, candidate_nodes,
                                         dom_to_node, queue, &replace_item)
        for pos from 0 <= pos < PyList_GET_SIZE(self._to_cleanup):
            node = _get_list_node(self._to_cleanup, pos)
            node.ancestor_of = None
        self._to_cleanup = []
        return PyFrozenSet_New(candidate_nodes)