← 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: 2009-06-16 15:35:14 UTC
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090616153514-2croj2d8ych1sk71
Clean out some asserts, get rid of the 'dominator_distance' field which isn't used anyway.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
28
28
    """Represents a single object in the known graph."""
29
29
 
30
30
    __slots__ = ('key', 'parent_keys', 'child_keys', 'linear_dominator',
31
 
                 'dominator_distance', 'gdfo', 'ancestor_of')
 
31
                 'gdfo', 'ancestor_of')
32
32
 
33
33
    def __init__(self, key, parent_keys):
34
34
        self.key = key
37
37
        # oldest ancestor, such that no parents between here and there have >1
38
38
        # child or >1 parent.
39
39
        self.linear_dominator = None
40
 
        self.dominator_distance = 0
41
40
        # Greatest distance from origin
42
41
        self.gdfo = None
43
42
        # This will become a tuple of known heads that have this node as an
45
44
        self.ancestor_of = None
46
45
 
47
46
    def __repr__(self):
48
 
        return '%s(%s  gdfo:%s par:%s child:%s dom:%s %s)' % (
 
47
        return '%s(%s  gdfo:%s par:%s child:%s %s)' % (
49
48
            self.__class__.__name__, self.key, self.gdfo,
50
49
            self.parent_keys, self.child_keys,
51
 
            self.linear_dominator, self.dominator_distance)
 
50
            self.linear_dominator)
52
51
 
53
52
 
54
53
class KnownGraph(object):
78
77
        for key, parent_keys in parent_map.iteritems():
79
78
            if key in nodes:
80
79
                node = nodes[key]
81
 
                assert node.parent_keys is None
82
80
                node.parent_keys = parent_keys
83
81
            else:
84
82
                node = _KnownGraphNode(key, parent_keys)
112
110
                # This node is either a ghost, a tail, or has multiple parents
113
111
                # It its own dominator
114
112
                node.linear_dominator = node.key
115
 
                node.dominator_distance = 0
116
113
                return None
117
114
            parent_node = self._nodes[node.parent_keys[0]]
118
115
            if len(parent_node.child_keys) > 1:
119
116
                # The parent has multiple children, so *this* node is the
120
117
                # dominator
121
118
                node.linear_dominator = node.key
122
 
                node.dominator_distance = 0
123
119
                return None
124
120
            # The parent is already filled in, so add and continue
125
121
            if parent_node.linear_dominator is not None:
126
122
                node.linear_dominator = parent_node.linear_dominator
127
 
                node.dominator_distance = parent_node.dominator_distance + 1
128
123
                return None
129
124
            # We don't know this node, or its parent node, so start walking to
130
125
            # next
145
140
                next_node = check_node(node)
146
141
            # The stack now contains the linear chain, and 'node' should have
147
142
            # been labeled
148
 
            assert node.linear_dominator is not None
149
143
            dominator = node.linear_dominator
150
144
            while stack:
151
145
                next_node = stack.pop()
152
146
                next_node.linear_dominator = dominator
153
 
                next_node.dominator_distance = node.dominator_distance + 1
154
147
                node = next_node
155
148
 
156
149
    def _find_gdfo(self):
166
159
            node.gdfo = 1
167
160
            heappush(todo, (1, node))
168
161
        processed = 0
169
 
        max_gdfo = len(self._nodes) + 1
170
162
        while todo:
171
163
            gdfo, next = heappop(todo)
172
164
            processed += 1
174
166
                # This node was reached from a longer path, we assume it was
175
167
                # enqued correctly with the longer gdfo, so don't continue
176
168
                # processing now
177
 
                assert gdfo < next.gdfo
178
169
                continue
179
170
            next_gdfo = gdfo + 1
180
 
            assert next_gdfo <= max_gdfo
181
171
            for child_key in next.child_keys:
182
172
                child_node = nodes[child_key]
183
173
                if child_node.gdfo is None or child_node.gdfo < next_gdfo:
208
198
                other_node = dom_to_node[node.linear_dominator]
209
199
                # There should be no way that nodes sharing a dominator could
210
200
                # 'tie' for gdfo
211
 
                assert other_node.gdfo != node.gdfo
212
201
                if other_node.gdfo > node.gdfo:
213
202
                    # The other node has this node as an ancestor
214
203
                    keys_to_remove.append(node.key)
282
271
        to_cleanup = []
283
272
        to_cleanup_append = to_cleanup.append
284
273
        for node in candidate_nodes.itervalues():
285
 
            assert node.ancestor_of is None
286
274
            node.ancestor_of = (node.key,)
287
275
            queue.append((-node.gdfo, node))
288
276
            to_cleanup_append(node)
296
284
        heappush = heapq.heappush
297
285
        while queue and len(candidate_nodes) > 1:
298
286
            _, node = heappop(queue)
299
 
            # assert node.ancestor_of is not None
300
287
            next_ancestor_of = node.ancestor_of
301
288
            if len(next_ancestor_of) == num_candidates:
302
289
                # This node is now considered 'common'