← 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: Vincent Ladeuil
  • Date: 2009-07-02 13:07:14 UTC
  • mto: (4524.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4525.
  • Revision ID: v.ladeuil+lp@free.fr-20090702130714-hsyqfusi8vn3a11m
Use tree.has_changes() where appropriate (the test suite caught a
bug in has_changes() (not filtering out the root) in an impressive
number of tests)

* bzrlib/send.py:
(send): Use tree.has_changes() instead of tree.changes_from().

* bzrlib/reconfigure.py:
(Reconfigure._check): Use tree.has_changes() instead of
tree.changes_from().

* bzrlib/merge.py:
(Merger.ensure_revision_trees, Merger.compare_basis): Use
tree.has_changes() instead of tree.changes_from().

* bzrlib/builtins.py:
(cmd_remove_tree.run, cmd_push.run, cmd_merge.run): Use
tree.has_changes() instead of tree.changes_from().

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
        - self._tails will list all the nodes without parents.
 
67
        """
 
68
        tails = self._tails = set()
 
69
        nodes = self._nodes
 
70
        for key, parent_keys in parent_map.iteritems():
 
71
            if key in nodes:
 
72
                node = nodes[key]
 
73
                node.parent_keys = parent_keys
 
74
                if parent_keys:
 
75
                    # This node has been added before being seen in parent_map
 
76
                    # (see below)
 
77
                    tails.remove(node)
 
78
            else:
 
79
                node = _KnownGraphNode(key, parent_keys)
 
80
                nodes[key] = node
 
81
            for parent_key in parent_keys:
 
82
                try:
 
83
                    parent_node = nodes[parent_key]
 
84
                except KeyError:
 
85
                    parent_node = _KnownGraphNode(parent_key, None)
 
86
                    nodes[parent_key] = parent_node
 
87
                    # Potentially a tail, if we're wrong we'll remove it later
 
88
                    # (see above)
 
89
                    tails.add(parent_node)
 
90
                parent_node.child_keys.append(key)
 
91
 
 
92
    def _find_gdfo(self):
 
93
        nodes = self._nodes
 
94
        known_parent_gdfos = {}
 
95
        pending = []
 
96
 
 
97
        for node in self._tails:
 
98
            node.gdfo = 1
 
99
            pending.append(node)
 
100
 
 
101
        while pending:
 
102
            node = pending.pop()
 
103
            for child_key in node.child_keys:
 
104
                child = nodes[child_key]
 
105
                if child_key in known_parent_gdfos:
 
106
                    known_gdfo = known_parent_gdfos[child_key] + 1
 
107
                    present = True
 
108
                else:
 
109
                    known_gdfo = 1
 
110
                    present = False
 
111
                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
 
112
                    child.gdfo = node.gdfo + 1
 
113
                if known_gdfo == len(child.parent_keys):
 
114
                    # We are the last parent updating that node, we can
 
115
                    # continue from there
 
116
                    pending.append(child)
 
117
                    if present:
 
118
                        del known_parent_gdfos[child_key]
 
119
                else:
 
120
                    # Update known_parent_gdfos for a key we couldn't process
 
121
                    known_parent_gdfos[child_key] = known_gdfo
 
122
 
 
123
    def heads(self, keys):
 
124
        """Return the heads from amongst keys.
 
125
 
 
126
        This is done by searching the ancestries of each key.  Any key that is
 
127
        reachable from another key is not returned; all the others are.
 
128
 
 
129
        This operation scales with the relative depth between any two keys. It
 
130
        uses gdfo to avoid walking all ancestry.
 
131
 
 
132
        :param keys: An iterable of keys.
 
133
        :return: A set of the heads. Note that as a set there is no ordering
 
134
            information. Callers will need to filter their input to create
 
135
            order if they need it.
 
136
        """
 
137
        candidate_nodes = dict((key, self._nodes[key]) for key in keys)
 
138
        if revision.NULL_REVISION in candidate_nodes:
 
139
            # NULL_REVISION is only a head if it is the only entry
 
140
            candidate_nodes.pop(revision.NULL_REVISION)
 
141
            if not candidate_nodes:
 
142
                return frozenset([revision.NULL_REVISION])
 
143
        if len(candidate_nodes) < 2:
 
144
            # No or only one candidate
 
145
            return frozenset(candidate_nodes)
 
146
        heads_key = frozenset(candidate_nodes)
 
147
        if heads_key != frozenset(keys):
 
148
            # Mention duplicates
 
149
            note('%s != %s', heads_key, frozenset(keys))
 
150
        # Do we have a cached result ?
 
151
        try:
 
152
            heads = self._known_heads[heads_key]
 
153
            return heads
 
154
        except KeyError:
 
155
            pass
 
156
        # Let's compute the heads
 
157
        seen = set()
 
158
        pending = []
 
159
        min_gdfo = None
 
160
        for node in candidate_nodes.values():
 
161
            if node.parent_keys:
 
162
                pending.extend(node.parent_keys)
 
163
            if min_gdfo is None or node.gdfo < min_gdfo:
 
164
                min_gdfo = node.gdfo
 
165
        nodes = self._nodes
 
166
        while pending:
 
167
            node_key = pending.pop()
 
168
            if node_key in seen:
 
169
                # node already appears in some ancestry
 
170
                continue
 
171
            seen.add(node_key)
 
172
            node = nodes[node_key]
 
173
            if node.gdfo <= min_gdfo:
 
174
                continue
 
175
            if node.parent_keys:
 
176
                pending.extend(node.parent_keys)
 
177
        heads = heads_key.difference(seen)
 
178
        if self.do_cache:
 
179
            self._known_heads[heads_key] = heads
 
180
        return heads
 
181