~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

heappush = heapq.heappush

heappop = heapq.heappop

heapify = heapq.heapify

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):

        parent_keys = []

        for parent in self.parents:

            parent_keys.append(parent.key)

        child_keys = []

        for child in self.children:

            child_keys.append(child.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)

# 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 = <_KnownGraphNode>PyTuple_GET_ITEM(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:

                temp_node = PyList_GET_ITEM(stack, i)

                next_node = <_KnownGraphNode>temp_node

                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 PyObject *temp_node

        cdef Py_ssize_t pos, pos2

        cdef _KnownGraphNode node

        cdef _KnownGraphNode child_node

        cdef _KnownGraphNode parent_node

        tails = self._find_tails()

        todo = []

        for pos from 0 <= pos < PyList_GET_SIZE(tails):

            temp_node = PyList_GET_ITEM(tails, pos)

            node = <_KnownGraphNode>temp_node

            node.gdfo = 1

            heappush(todo, (1, node))

        max_gdfo = len(self._nodes) + 1

        while PyList_GET_SIZE(todo) > 0:

            temp_node = PyTuple_GET_ITEM(heappop(todo), 1)

            node = <_KnownGraphNode>temp_node

            next_gdfo = node.gdfo + 1

            assert next_gdfo <= max_gdfo

            for pos from 0 <= pos < PyList_GET_SIZE(node.children):

                temp_node = PyList_GET_ITEM(node.children, pos)

                child_node = <_KnownGraphNode>temp_node

                if child_node.gdfo < next_gdfo:

                    # Only enque children when all of their parents have been

                    # resolved

                    for pos2 from 0 <= pos2 < PyTuple_GET_SIZE(child_node.parents):

                        temp_node = PyTuple_GET_ITEM(child_node.parents, pos2)

                        parent_node = <_KnownGraphNode>temp_node

                        # We know that 'this' parent is counted

                        if parent_node is not node:

                            if parent_node.gdfo == -1:

                                break

                    else:

                        child_node.gdfo = next_gdfo

                        heappush(todo, (next_gdfo, child_node))

    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

        # Check the linear dominators of these keys, to see if we already

        # know the heads answer

        dom_lookup_key, heads = self._heads_from_dominators(candidate_nodes)

        if heads is not None:

            return heads

        heads = self._heads_from_candidate_nodes(candidate_nodes)

        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 object _heads_from_dominators(self, candidate_nodes):

        cdef PyObject *maybe_heads

        cdef PyObject *maybe_key

        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

        dom_to_key = {}

        pos = 0

        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):

            node = <_KnownGraphNode>temp_node

            PyDict_SetItem(dom_to_key, node.linear_dominator_node.key,

                                       node.key)

        heads = []

        for dom_key in dom_heads:

            maybe_key = PyDict_GetItem(dom_to_key, dom_key)

            if maybe_key == NULL:

                # Should never happen

                raise KeyError

            PyList_Append(heads, <object>maybe_key)

        return dom_lookup_key, PyFrozenSet_New(heads)

    cdef int _process_parent(self, _KnownGraphNode node,

                             _KnownGraphNode parent_node,

                             candidate_nodes,

                             queue) except -1:

        """Process the parent of a node, seeing if we need to walk it.

        :return: 0 No extra work needed

                 1 This was a candidate node, and now there is only 1 candidate

                   left, so break out of the loop

        """

        cdef PyObject *maybe_candidate

        maybe_candidate = PyDict_GetItem(candidate_nodes, parent_node.key)

        if maybe_candidate != NULL:

            candidate_nodes.pop(parent_node.key)

            if len(candidate_nodes) <= 1:

                return 1

        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

            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):

        cdef _KnownGraphNode node

        cdef _KnownGraphNode parent_node

        cdef Py_ssize_t num_candidates

        cdef int num_parents

        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)

        while PyList_GET_SIZE(queue) > 0 and PyDict_Size(candidate_nodes) > 1:

            temp_node = PyTuple_GET_ITEM(heappop(queue), 1)

            node = <_KnownGraphNode>temp_node

            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):

                    temp_node = PyTuple_GET_ITEM(node.parents, pos)

                    parent_node = <_KnownGraphNode>temp_node

                    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

                if (self._process_parent(node, node.linear_dominator_node,

                                         candidate_nodes, queue)):

                    break

            else:

               for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):

                   temp_node = PyTuple_GET_ITEM(node.parents, pos)

                   parent_node = <_KnownGraphNode>temp_node

                   if (self._process_parent(node, parent_node,

                                            candidate_nodes, queue)):

                       break

        for pos from 0 <= pos < PyList_GET_SIZE(self._to_cleanup):

            temp_node = PyList_GET_ITEM(self._to_cleanup, pos)

            node = <_KnownGraphNode>temp_node

            node.ancestor_of = None

        self._to_cleanup = []

        return PyFrozenSet_New(candidate_nodes)