← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: John Arbash Meinel
  • Date: 2008-09-05 02:29:34 UTC
  • mto: (3697.7.4 1.7)
  • mto: This revision was merged to the branch mainline in revision 3748.
  • Revision ID: john@arbash-meinel.com-20080905022934-s8692mbwpkdwi106
Cleanups to the algorithm documentation.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
1
 
# Copyright (C) 2009 Canonical Ltd
2
 
#
3
 
# This program is free software; you can redistribute it and/or modify
4
 
# it under the terms of the GNU General Public License as published by
5
 
# the Free Software Foundation; either version 2 of the License, or
6
 
# (at your option) any later version.
7
 
#
8
 
# This program is distributed in the hope that it will be useful,
9
 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
 
# GNU General Public License for more details.
12
 
#
13
 
# You should have received a copy of the GNU General Public License
14
 
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
"""Implementation of Graph algorithms when we have already loaded everything.
18
 
"""
19
 
 
20
 
from bzrlib import (
21
 
    revision,
22
 
    )
23
 
 
24
 
 
25
 
class _KnownGraphNode(object):
26
 
    """Represents a single object in the known graph."""
27
 
 
28
 
    __slots__ = ('key', 'parent_keys', 'child_keys', 'gdfo')
29
 
 
30
 
    def __init__(self, key, parent_keys):
31
 
        self.key = key
32
 
        self.parent_keys = parent_keys
33
 
        self.child_keys = []
34
 
        # Greatest distance from origin
35
 
        self.gdfo = None
36
 
 
37
 
    def __repr__(self):
38
 
        return '%s(%s  gdfo:%s par:%s child:%s)' % (
39
 
            self.__class__.__name__, self.key, self.gdfo,
40
 
            self.parent_keys, self.child_keys)
41
 
 
42
 
 
43
 
class KnownGraph(object):
44
 
    """This is a class which assumes we already know the full graph."""
45
 
 
46
 
    def __init__(self, parent_map, do_cache=True):
47
 
        """Create a new KnownGraph instance.
48
 
 
49
 
        :param parent_map: A dictionary mapping key => parent_keys
50
 
        """
51
 
        self._nodes = {}
52
 
        # Maps {sorted(revision_id, revision_id): heads}
53
 
        self._known_heads = {}
54
 
        self.do_cache = do_cache
55
 
        self._initialize_nodes(parent_map)
56
 
        self._find_gdfo()
57
 
 
58
 
    def _initialize_nodes(self, parent_map):
59
 
        """Populate self._nodes.
60
 
 
61
 
        After this has finished:
62
 
        - self._nodes will have an entry for every entry in parent_map.
63
 
        - ghosts will have a parent_keys = None,
64
 
        - all nodes found will also have .child_keys populated with all known
65
 
          child_keys,
66
 
        """
67
 
        nodes = self._nodes
68
 
        for key, parent_keys in parent_map.iteritems():
69
 
            if key in nodes:
70
 
                node = nodes[key]
71
 
                node.parent_keys = parent_keys
72
 
            else:
73
 
                node = _KnownGraphNode(key, parent_keys)
74
 
                nodes[key] = node
75
 
            for parent_key in parent_keys:
76
 
                try:
77
 
                    parent_node = nodes[parent_key]
78
 
                except KeyError:
79
 
                    parent_node = _KnownGraphNode(parent_key, None)
80
 
                    nodes[parent_key] = parent_node
81
 
                parent_node.child_keys.append(key)
82
 
 
83
 
    def _find_tails(self):
84
 
        return [node for node in self._nodes.itervalues()
85
 
                if not node.parent_keys]
86
 
 
87
 
    def _find_gdfo(self):
88
 
        nodes = self._nodes
89
 
        known_parent_gdfos = {}
90
 
        pending = []
91
 
 
92
 
        for node in self._find_tails():
93
 
            node.gdfo = 1
94
 
            pending.append(node)
95
 
 
96
 
        while pending:
97
 
            node = pending.pop()
98
 
            for child_key in node.child_keys:
99
 
                child = nodes[child_key]
100
 
                if child_key in known_parent_gdfos:
101
 
                    known_gdfo = known_parent_gdfos[child_key] + 1
102
 
                    present = True
103
 
                else:
104
 
                    known_gdfo = 1
105
 
                    present = False
106
 
                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
107
 
                    child.gdfo = node.gdfo + 1
108
 
                if known_gdfo == len(child.parent_keys):
109
 
                    # We are the last parent updating that node, we can
110
 
                    # continue from there
111
 
                    pending.append(child)
112
 
                    if present:
113
 
                        del known_parent_gdfos[child_key]
114
 
                else:
115
 
                    # Update known_parent_gdfos for a key we couldn't process
116
 
                    known_parent_gdfos[child_key] = known_gdfo
117
 
 
118
 
    def heads(self, keys):
119
 
        """Return the heads from amongst keys.
120
 
 
121
 
        This is done by searching the ancestries of each key.  Any key that is
122
 
        reachable from another key is not returned; all the others are.
123
 
 
124
 
        This operation scales with the relative depth between any two keys. It
125
 
        uses gdfo to avoid walking all ancestry.
126
 
 
127
 
        :param keys: An iterable of keys.
128
 
        :return: A set of the heads. Note that as a set there is no ordering
129
 
            information. Callers will need to filter their input to create
130
 
            order if they need it.
131
 
        """
132
 
        candidate_nodes = dict((key, self._nodes[key]) for key in keys)
133
 
        if revision.NULL_REVISION in candidate_nodes:
134
 
            # NULL_REVISION is only a head if it is the only entry
135
 
            candidate_nodes.pop(revision.NULL_REVISION)
136
 
            if not candidate_nodes:
137
 
                return frozenset([revision.NULL_REVISION])
138
 
        if len(candidate_nodes) < 2:
139
 
            # No or only one candidate
140
 
            return frozenset(candidate_nodes)
141
 
        heads_key = frozenset(candidate_nodes)
142
 
        # Do we have a cached result ?
143
 
        try:
144
 
            heads = self._known_heads[heads_key]
145
 
            return heads
146
 
        except KeyError:
147
 
            pass
148
 
        # Let's compute the heads
149
 
        seen = set()
150
 
        pending = []
151
 
        min_gdfo = None
152
 
        for node in candidate_nodes.values():
153
 
            if node.parent_keys:
154
 
                pending.extend(node.parent_keys)
155
 
            if min_gdfo is None or node.gdfo < min_gdfo:
156
 
                min_gdfo = node.gdfo
157
 
        nodes = self._nodes
158
 
        while pending:
159
 
            node_key = pending.pop()
160
 
            if node_key in seen:
161
 
                # node already appears in some ancestry
162
 
                continue
163
 
            seen.add(node_key)
164
 
            node = nodes[node_key]
165
 
            if node.gdfo <= min_gdfo:
166
 
                continue
167
 
            if node.parent_keys:
168
 
                pending.extend(node.parent_keys)
169
 
        heads = heads_key.difference(seen)
170
 
        if self.do_cache:
171
 
            self._known_heads[heads_key] = heads
172
 
        return heads
173