~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2009, 2010 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

    int PyString_CheckExact(object)

    int PyObject_RichCompareBool(object, object, int)

    int Py_LT

    int PyTuple_CheckExact(object)

    object PyTuple_New(Py_ssize_t n)

    Py_ssize_t PyTuple_GET_SIZE(object t)

    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)

    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)

    int PyList_CheckExact(object)

    Py_ssize_t PyList_GET_SIZE(object l)

    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)

    int PyList_SetItem(object l, Py_ssize_t o, object l) except -1

    int PyList_Append(object l, object v) except -1

    int PyDict_CheckExact(object d)

    Py_ssize_t PyDict_Size(object d) except -1

    PyObject * PyDict_GetItem(object d, object k)

    int PyDict_SetItem(object d, object k, object v) except -1

    int PyDict_DelItem(object d, object k) except -1

    int PyDict_Next(object d, Py_ssize_t *pos, PyObject **k, PyObject **v)

    void Py_INCREF(object)

from collections import deque

import gc

from bzrlib import errors, revision

cdef object NULL_REVISION

NULL_REVISION = revision.NULL_REVISION

cdef class _KnownGraphNode:

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

    cdef object key

    cdef object parents

    cdef object children

    cdef public long gdfo

    cdef int seen

    cdef object extra

    def __init__(self, key):

        self.key = key

        self.parents = None

        self.children = []

        # Greatest distance from origin

        self.gdfo = -1

        self.seen = 0

        self.extra = None

    property child_keys:

        def __get__(self):

            cdef _KnownGraphNode child

            keys = []

            for child in self.children:

                PyList_Append(keys, child.key)

            return keys

    property parent_keys:

        def __get__(self):

            if self.parents is None:

                return None

            cdef _KnownGraphNode parent

            keys = []

            for parent in self.parents:

                PyList_Append(keys, parent.key)

            return keys

    cdef clear_references(self):

        self.parents = None

        self.children = 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)' % (

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

            parent_keys, child_keys)

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_tuple_node(tpl, Py_ssize_t pos):

    cdef PyObject *temp_node

    temp_node = PyTuple_GET_ITEM(tpl, pos)

    return <_KnownGraphNode>temp_node

def get_key(node):

    cdef _KnownGraphNode real_node

    real_node = node

    return real_node.key

cdef object _sort_list_nodes(object lst_or_tpl, int reverse):

    """Sort a list of _KnownGraphNode objects.

    If lst_or_tpl is a list, it is allowed to mutate in place. It may also

    just return the input list if everything is already sorted.

    """

    cdef _KnownGraphNode node1, node2

    cdef int do_swap, is_tuple

    cdef Py_ssize_t length

    is_tuple = PyTuple_CheckExact(lst_or_tpl)

    if not (is_tuple or PyList_CheckExact(lst_or_tpl)):

        raise TypeError('lst_or_tpl must be a list or tuple.')

    length = len(lst_or_tpl)

    if length == 0 or length == 1:

        return lst_or_tpl

    if length == 2:

        if is_tuple:

            node1 = _get_tuple_node(lst_or_tpl, 0)

            node2 = _get_tuple_node(lst_or_tpl, 1)

        else:

            node1 = _get_list_node(lst_or_tpl, 0)

            node2 = _get_list_node(lst_or_tpl, 1)

        if reverse:

            do_swap = PyObject_RichCompareBool(node1.key, node2.key, Py_LT)

        else:

            do_swap = PyObject_RichCompareBool(node2.key, node1.key, Py_LT)

        if not do_swap:

            return lst_or_tpl

        if is_tuple:

            return (node2, node1)

        else:

            # Swap 'in-place', since lists are mutable

            Py_INCREF(node1)

            PyList_SetItem(lst_or_tpl, 1, node1)

            Py_INCREF(node2)

            PyList_SetItem(lst_or_tpl, 0, node2)

            return lst_or_tpl

    # For all other sizes, we just use 'sorted()'

    if is_tuple:

        # Note that sorted() is just list(iterable).sort()

        lst_or_tpl = list(lst_or_tpl)

    lst_or_tpl.sort(key=get_key, reverse=reverse)

    return lst_or_tpl

cdef class _MergeSorter

cdef class KnownGraph:

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

    cdef public object _nodes

    cdef public object _known_heads

    cdef public int do_cache

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

        """Create a new KnownGraph instance.

        :param parent_map: A dictionary mapping key => parent_keys

        """

        # tests at pre-allocating the node dict actually slowed things down

        self._nodes = {}

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

        self._known_heads = {}

        self.do_cache = int(do_cache)

        # TODO: consider disabling gc since we are allocating a lot of nodes

        #       that won't be collectable anyway. real world testing has not

        #       shown a specific impact, yet.

        self._initialize_nodes(parent_map)

        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

    cdef _populate_parents(self, _KnownGraphNode node, parent_keys):

        cdef Py_ssize_t num_parent_keys, pos

        cdef _KnownGraphNode parent_node

        num_parent_keys = len(parent_keys)

        # We know how many parents, so we pre allocate the tuple

        parent_nodes = PyTuple_New(num_parent_keys)

        for pos from 0 <= pos < num_parent_keys:

            # Note: it costs us 10ms out of 40ms to lookup all of these

            #       parents, it doesn't seem to be an allocation overhead,

            #       but rather a lookup overhead. There doesn't seem to be

            #       a way around it, and that is one reason why

            #       KnownGraphNode maintains a direct pointer to the parent

            #       node.

            # We use [] because parent_keys may be a tuple or list

            parent_node = self._get_or_create_node(parent_keys[pos])

            # PyTuple_SET_ITEM will steal a reference, so INCREF first

            Py_INCREF(parent_node)

            PyTuple_SET_ITEM(parent_nodes, pos, parent_node)

            PyList_Append(parent_node.children, node)

        node.parents = parent_nodes

    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

        cdef _KnownGraphNode node

        cdef _KnownGraphNode parent_node

        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)

            self._populate_parents(node, parent_keys)

    def _find_tails(self):

        cdef PyObject *temp_node

        cdef _KnownGraphNode node

        cdef Py_ssize_t pos

        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:

                node.gdfo = 1

                PyList_Append(tails, node)

        return tails

    def _find_tips(self):

        cdef PyObject *temp_node

        cdef _KnownGraphNode node

        cdef Py_ssize_t pos

        tips = []

        pos = 0

        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):

            node = <_KnownGraphNode>temp_node

            if PyList_GET_SIZE(node.children) == 0:

                PyList_Append(tips, node)

        return tips

    def _find_gdfo(self):

        cdef _KnownGraphNode node

        cdef _KnownGraphNode child

        cdef PyObject *temp

        cdef Py_ssize_t pos

        cdef int replace

        cdef Py_ssize_t last_item

        cdef long next_gdfo

        pending = self._find_tails()

        last_item = PyList_GET_SIZE(pending) - 1

        while last_item >= 0:

            # Avoid pop followed by push, instead, peek, and replace

            # timing shows this is 930ms => 770ms for OOo

            node = _get_list_node(pending, last_item)

            last_item = last_item - 1

            next_gdfo = node.gdfo + 1

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

                child = _get_list_node(node.children, pos)

                if next_gdfo > child.gdfo:

                    child.gdfo = next_gdfo

                child.seen = child.seen + 1

                if child.seen == PyTuple_GET_SIZE(child.parents):

                    # This child is populated, queue it to be walked

                    last_item = last_item + 1

                    if last_item < PyList_GET_SIZE(pending):

                        Py_INCREF(child) # SetItem steals a ref

                        PyList_SetItem(pending, last_item, child)

                    else:

                        PyList_Append(pending, child)

                    # We have queued this node, we don't need to track it

                    # anymore

                    child.seen = 0

    def add_node(self, key, parent_keys):

        """Add a new node to the graph.

        If this fills in a ghost, then the gdfos of all children will be

        updated accordingly.

        :param key: The node being added. If this is a duplicate, this is a

            no-op.

        :param parent_keys: The parents of the given node.

        :return: None (should we return if this was a ghost, etc?)

        """

        cdef PyObject *maybe_node

        cdef _KnownGraphNode node, parent_node, child_node

        cdef long parent_gdfo, next_gdfo

        maybe_node = PyDict_GetItem(self._nodes, key)

        if maybe_node != NULL:

            node = <_KnownGraphNode>maybe_node

            if node.parents is None:

                # We are filling in a ghost

                self._populate_parents(node, parent_keys)

                # We can't trust cached heads anymore

                self._known_heads.clear()

            else: # Ensure that the parent_key list matches

                existing_parent_keys = []

                for parent_node in node.parents:

                    existing_parent_keys.append(parent_node.key)

                # Make sure we use a list for the comparison, in case it was a

                # tuple, etc

                parent_keys = list(parent_keys)

                if existing_parent_keys == parent_keys:

                    # Exact match, nothing more to do

                    return

                else:

                    raise ValueError('Parent key mismatch, existing node %s'

                        ' has parents of %s not %s'

                        % (key, existing_parent_keys, parent_keys))

        else:

            node = _KnownGraphNode(key)

            PyDict_SetItem(self._nodes, key, node)

            self._populate_parents(node, parent_keys)

        parent_gdfo = 0

        for parent_node in node.parents:

            if parent_node.gdfo == -1:

                # This is a newly introduced ghost, so it gets gdfo of 1

                parent_node.gdfo = 1

            if parent_gdfo < parent_node.gdfo:

                parent_gdfo = parent_node.gdfo

        node.gdfo = parent_gdfo + 1

        # Now fill the gdfo to all children

        # Note that this loop is slightly inefficient, in that we may visit the

        # same child (and its decendents) more than once, however, it is

        # 'efficient' in that we only walk to nodes that would be updated,

        # rather than all nodes

        # We use a deque rather than a simple list stack, to go for BFD rather

        # than DFD. So that if a longer path is possible, we walk it before we

        # get to the final child

        pending = deque([node])

        pending_popleft = pending.popleft

        pending_append = pending.append

        while pending:

            node = pending_popleft()

            next_gdfo = node.gdfo + 1

            for child_node in node.children:

                if child_node.gdfo < next_gdfo:

                    # This child is being updated, we need to check its

                    # children

                    child_node.gdfo = next_gdfo

                    pending_append(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. 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.

        """

        cdef PyObject *maybe_node

        cdef PyObject *maybe_heads

        cdef PyObject *temp_node

        cdef _KnownGraphNode node

        cdef Py_ssize_t pos, last_item

        cdef long min_gdfo

        heads_key = frozenset(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 = {}

        for key in keys:

            maybe_node = PyDict_GetItem(self._nodes, key)

            if maybe_node == NULL:

                raise KeyError('key %s not in nodes' % (key,))

            PyDict_SetItem(candidate_nodes, key, <object>maybe_node)

        maybe_node = PyDict_GetItem(candidate_nodes, NULL_REVISION)

        if maybe_node != NULL:

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

            candidate_nodes.pop(NULL_REVISION)

            if not candidate_nodes:

                return frozenset([NULL_REVISION])

            # The keys changed, so recalculate heads_key

            heads_key = frozenset(candidate_nodes)

        if PyDict_Size(candidate_nodes) < 2:

            return heads_key

        cleanup = []

        pending = []

        # we know a gdfo cannot be longer than a linear chain of all nodes

        min_gdfo = PyDict_Size(self._nodes) + 1

        # Build up nodes that need to be walked, note that starting nodes are

        # not added to seen()

        pos = 0

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

            node = <_KnownGraphNode>temp_node

            if node.parents is not None:

                pending.extend(node.parents)

            if node.gdfo < min_gdfo:

                min_gdfo = node.gdfo

        # Now do all the real work

        last_item = PyList_GET_SIZE(pending) - 1

        while last_item >= 0:

            node = _get_list_node(pending, last_item)

            last_item = last_item - 1

            if node.seen:

                # node already appears in some ancestry

                continue

            PyList_Append(cleanup, node)

            node.seen = 1

            if node.gdfo <= min_gdfo:

                continue

            if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:

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

                    parent_node = _get_tuple_node(node.parents, pos)

                    last_item = last_item + 1

                    if last_item < PyList_GET_SIZE(pending):

                        Py_INCREF(parent_node) # SetItem steals a ref

                        PyList_SetItem(pending, last_item, parent_node)

                    else:

                        PyList_Append(pending, parent_node)

        heads = []

        pos = 0

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

            node = <_KnownGraphNode>temp_node

            if not node.seen:

                PyList_Append(heads, node.key)

        heads = frozenset(heads)

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

            node = _get_list_node(cleanup, pos)

            node.seen = 0

        if self.do_cache:

            PyDict_SetItem(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.

        """

        # This is, for the most part, the same iteration order that we used for

        # _find_gdfo, consider finding a way to remove the duplication

        # In general, we find the 'tails' (nodes with no parents), and then

        # walk to the children. For children that have all of their parents

        # yielded, we queue up the child to be yielded as well.

        cdef _KnownGraphNode node

        cdef _KnownGraphNode child

        cdef PyObject *temp

        cdef Py_ssize_t pos

        cdef int replace

        cdef Py_ssize_t last_item

        pending = self._find_tails()

        if PyList_GET_SIZE(pending) == 0 and len(self._nodes) > 0:

            raise errors.GraphCycleError(self._nodes)

        topo_order = []

        last_item = PyList_GET_SIZE(pending) - 1

        while last_item >= 0:

            # Avoid pop followed by push, instead, peek, and replace

            # timing shows this is 930ms => 770ms for OOo

            node = _get_list_node(pending, last_item)

            last_item = last_item - 1

            if node.parents is not None:

                # We don't include ghost parents

                PyList_Append(topo_order, node.key)

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

                child = _get_list_node(node.children, pos)

                if child.gdfo == -1:

                    # We know we have a graph cycle because a node has a parent

                    # which we couldn't find

                    raise errors.GraphCycleError(self._nodes)

                child.seen = child.seen + 1

                if child.seen == PyTuple_GET_SIZE(child.parents):

                    # All parents of this child have been yielded, queue this

                    # one to be yielded as well

                    last_item = last_item + 1

                    if last_item < PyList_GET_SIZE(pending):

                        Py_INCREF(child) # SetItem steals a ref

                        PyList_SetItem(pending, last_item, child)

                    else:

                        PyList_Append(pending, child)

                    # We have queued this node, we don't need to track it

                    # anymore

                    child.seen = 0

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

        return topo_order

    def gc_sort(self):

        """Return a reverse topological ordering which is 'stable'.

        There are a few constraints:

          1) Reverse topological (all children before all parents)

          2) Grouped by prefix

          3) 'stable' sorting, so that we get the same result, independent of

             machine, or extra data.

        To do this, we use the same basic algorithm as topo_sort, but when we

        aren't sure what node to access next, we sort them lexicographically.

        """

        cdef PyObject *temp

        cdef Py_ssize_t pos, last_item

        cdef _KnownGraphNode node, node2, parent_node

        tips = self._find_tips()

        # Split the tips based on prefix

        prefix_tips = {}

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

            node = _get_list_node(tips, pos)

            if PyString_CheckExact(node.key) or len(node.key) == 1:

                prefix = ''

            else:

                prefix = node.key[0]

            temp = PyDict_GetItem(prefix_tips, prefix)

            if temp == NULL:

                prefix_tips[prefix] = [node]

            else:

                tip_nodes = <object>temp

                PyList_Append(tip_nodes, node)

        result = []

        for prefix in sorted(prefix_tips):

            temp = PyDict_GetItem(prefix_tips, prefix)

            assert temp != NULL

            tip_nodes = <object>temp

            pending = _sort_list_nodes(tip_nodes, 1)

            last_item = PyList_GET_SIZE(pending) - 1

            while last_item >= 0:

                node = _get_list_node(pending, last_item)

                last_item = last_item - 1

                if node.parents is None:

                    # Ghost

                    continue

                PyList_Append(result, node.key)

                # Sorting the parent keys isn't strictly necessary for stable

                # sorting of a given graph. But it does help minimize the

                # differences between graphs

                # For bzr.dev ancestry:

                #   4.73ms  no sort

                #   7.73ms  RichCompareBool sort

                parents = _sort_list_nodes(node.parents, 1)

                for pos from 0 <= pos < len(parents):

                    if PyTuple_CheckExact(parents):

                        parent_node = _get_tuple_node(parents, pos)

                    else:

                        parent_node = _get_list_node(parents, pos)

                    # TODO: GraphCycle detection

                    parent_node.seen = parent_node.seen + 1

                    if (parent_node.seen

                        == PyList_GET_SIZE(parent_node.children)):

                        # All children have been processed, queue up this

                        # parent

                        last_item = last_item + 1

                        if last_item < PyList_GET_SIZE(pending):

                            Py_INCREF(parent_node) # SetItem steals a ref

                            PyList_SetItem(pending, last_item, parent_node)

                        else:

                            PyList_Append(pending, parent_node)

                        parent_node.seen = 0

        return result

    def merge_sort(self, tip_key):

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

        cdef _MergeSorter sorter

        # TODO: consider disabling gc since we are allocating a lot of nodes

        #       that won't be collectable anyway. real world testing has not

        #       shown a specific impact, yet.

        sorter = _MergeSorter(self, tip_key)

        return sorter.topo_order()

    def get_parent_keys(self, key):

        """Get the parents for a key

        Returns a list containg the parents keys. If the key is a ghost,

        None is returned. A KeyError will be raised if the key is not in

        the graph.

        :param keys: Key to check (eg revision_id)

        :return: A list of parents

        """

        return self._nodes[key].parent_keys 

    def get_child_keys(self, key):

        """Get the children for a key

        Returns a list containg the children keys. A KeyError will be raised

        if the key is not in the graph.

        :param keys: Key to check (eg revision_id)

        :return: A list of children

        """

        return self._nodes[key].child_keys    

cdef class _MergeSortNode:

    """Tracks information about a node during the merge_sort operation."""

    # Public api

    cdef public object key

    cdef public long merge_depth

    cdef public object end_of_merge # True/False Is this the end of the current merge

    # Private api, used while computing the information

    cdef _KnownGraphNode left_parent

    cdef _KnownGraphNode left_pending_parent

    cdef object pending_parents # list of _KnownGraphNode for non-left parents

    cdef long _revno_first

    cdef long _revno_second

    cdef long _revno_last

    # TODO: turn these into flag/bit fields rather than individual members

    cdef int is_first_child # Is this the first child?

    cdef int seen_by_child # A child node has seen this parent

    cdef int completed # Fully Processed

    def __init__(self, key):

        self.key = key