← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-12-20 16:16:34 UTC
  • mfrom: (3123.5.18 hardlinks)
  • Revision ID: pqm@pqm.ubuntu.com-20071220161634-2kcjb650o21ydko4
Accelerate build_tree using similar workingtrees (abentley)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
20
20
 
21
21
from bzrlib import (
22
22
    errors,
23
 
    symbol_versioning,
 
23
    symbol_versioning
 
24
    )
 
25
from bzrlib.deprecated_graph import (
 
26
    all_descendants,
 
27
    Graph,
 
28
    node_distances,
 
29
    select_farthest,
24
30
    )
25
31
from bzrlib.osutils import contains_whitespace
26
32
from bzrlib.progress import DummyProgress
 
33
from bzrlib.symbol_versioning import (deprecated_function,
 
34
        )
27
35
 
28
36
NULL_REVISION="null:"
29
37
CURRENT_REVISION="current:"
117
125
        return self.properties.get('author', self.committer)
118
126
 
119
127
 
 
128
@deprecated_function(symbol_versioning.one_zero)
 
129
def is_ancestor(revision_id, candidate_id, branch):
 
130
    """Return true if candidate_id is an ancestor of revision_id.
 
131
 
 
132
    A false negative will be returned if any intermediate descendent of
 
133
    candidate_id is not present in any of the revision_sources.
 
134
    
 
135
    revisions_source is an object supporting a get_revision operation that
 
136
    behaves like Branch's.
 
137
 
 
138
    This function is deprecated, it is better for callers to directly use
 
139
    Graph.is_ancestor() (just watch out that the parameter order is switched)
 
140
    """
 
141
    return branch.repository.get_graph().is_ancestor(candidate_id, revision_id)
 
142
 
 
143
 
120
144
def iter_ancestors(revision_id, revision_source, only_present=False):
121
145
    ancestors = (revision_id,)
122
146
    distance = 0
164
188
    return matches
165
189
 
166
190
 
 
191
def revision_graph(revision, revision_source):
 
192
    """Produce a graph of the ancestry of the specified revision.
 
193
    
 
194
    :return: root, ancestors map, descendants map
 
195
    """
 
196
    revision_source.lock_read()
 
197
    try:
 
198
        return _revision_graph(revision, revision_source)
 
199
    finally:
 
200
        revision_source.unlock()
 
201
 
 
202
 
 
203
def _revision_graph(revision, revision_source):
 
204
    """See revision_graph."""
 
205
    from bzrlib.tsort import topo_sort
 
206
    graph = revision_source.get_revision_graph(revision)
 
207
    # mark all no-parent revisions as being NULL_REVISION parentage.
 
208
    for node, parents in graph.items():
 
209
        if len(parents) == 0:
 
210
            graph[node] = [NULL_REVISION]
 
211
    # add NULL_REVISION to the graph
 
212
    graph[NULL_REVISION] = []
 
213
 
 
214
    # pick a root. If there are multiple roots
 
215
    # this could pick a random one.
 
216
    topo_order = topo_sort(graph.items())
 
217
    root = topo_order[0]
 
218
 
 
219
    ancestors = {}
 
220
    descendants = {}
 
221
 
 
222
    # map the descendants of the graph.
 
223
    # and setup our set based return graph.
 
224
    for node in graph.keys():
 
225
        descendants[node] = {}
 
226
    for node, parents in graph.items():
 
227
        for parent in parents:
 
228
            descendants[parent][node] = 1
 
229
        ancestors[node] = set(parents)
 
230
 
 
231
    assert root not in descendants[root]
 
232
    assert root not in ancestors[root]
 
233
    return root, ancestors, descendants
 
234
 
 
235
 
 
236
def combined_graph(revision_a, revision_b, revision_source):
 
237
    """Produce a combined ancestry graph.
 
238
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
239
    root, ancestors, descendants = revision_graph(
 
240
        revision_a, revision_source)
 
241
    root_b, ancestors_b, descendants_b = revision_graph(
 
242
        revision_b, revision_source)
 
243
    if root != root_b:
 
244
        raise errors.NoCommonRoot(revision_a, revision_b)
 
245
    common = set()
 
246
    for node, node_anc in ancestors_b.iteritems():
 
247
        if node in ancestors:
 
248
            common.add(node)
 
249
        else:
 
250
            ancestors[node] = set()
 
251
        ancestors[node].update(node_anc)
 
252
    for node, node_dec in descendants_b.iteritems():
 
253
        if node not in descendants:
 
254
            descendants[node] = {}
 
255
        descendants[node].update(node_dec)
 
256
    return root, ancestors, descendants, common
 
257
 
 
258
 
 
259
def common_ancestor(revision_a, revision_b, revision_source, 
 
260
                    pb=DummyProgress()):
 
261
    if None in (revision_a, revision_b):
 
262
        return None
 
263
    if NULL_REVISION in (revision_a, revision_b):
 
264
        return NULL_REVISION
 
265
    # trivial optimisation
 
266
    if revision_a == revision_b:
 
267
        return revision_a
 
268
    try:
 
269
        try:
 
270
            pb.update('Picking ancestor', 1, 3)
 
271
            graph = revision_source.get_revision_graph_with_ghosts(
 
272
                [revision_a, revision_b])
 
273
            # Shortcut the case where one of the tips is already included in
 
274
            # the other graphs ancestry.
 
275
            ancestry_a = graph.get_ancestry(revision_a, topo_sorted=False)
 
276
            if revision_b in ancestry_a:
 
277
                return revision_b
 
278
            ancestry_b = graph.get_ancestry(revision_b, topo_sorted=False)
 
279
            if revision_a in ancestry_b:
 
280
                return revision_a
 
281
            # convert to a NULL_REVISION based graph.
 
282
            ancestors = graph.get_ancestors()
 
283
            descendants = graph.get_descendants()
 
284
            common = set(ancestry_a)
 
285
            common.intersection_update(ancestry_b)
 
286
            descendants[NULL_REVISION] = {}
 
287
            ancestors[NULL_REVISION] = []
 
288
            for root in graph.roots:
 
289
                descendants[NULL_REVISION][root] = 1
 
290
                ancestors[root].append(NULL_REVISION)
 
291
            for ghost in graph.ghosts:
 
292
                # ghosts act as roots for the purpose of finding 
 
293
                # the longest paths from the root: any ghost *might*
 
294
                # be directly attached to the root, so we treat them
 
295
                # as being such.
 
296
                # ghost now descends from NULL
 
297
                descendants[NULL_REVISION][ghost] = 1
 
298
                # that is it has an ancestor of NULL
 
299
                ancestors[ghost] = [NULL_REVISION]
 
300
                # ghost is common if any of ghosts descendants are common:
 
301
                for ghost_descendant in descendants[ghost]:
 
302
                    if ghost_descendant in common:
 
303
                        common.add(ghost)
 
304
                
 
305
            root = NULL_REVISION
 
306
            common.add(NULL_REVISION)
 
307
        except errors.NoCommonRoot:
 
308
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
309
            
 
310
        pb.update('Picking ancestor', 2, 3)
 
311
        distances = node_distances (descendants, ancestors, root)
 
312
        pb.update('Picking ancestor', 3, 2)
 
313
        farthest = select_farthest(distances, common)
 
314
        if farthest is None or farthest == NULL_REVISION:
 
315
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
316
    finally:
 
317
        pb.clear()
 
318
    return farthest
 
319
 
 
320
 
 
321
class MultipleRevisionSources(object):
 
322
    """Proxy that looks in multiple branches for revisions."""
 
323
    def __init__(self, *args):
 
324
        object.__init__(self)
 
325
        assert len(args) != 0
 
326
        self._revision_sources = args
 
327
 
 
328
    def revision_parents(self, revision_id):
 
329
        for source in self._revision_sources:
 
330
            try:
 
331
                return source.revision_parents(revision_id)
 
332
            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
 
333
                pass
 
334
        raise e
 
335
 
 
336
    def get_revision(self, revision_id):
 
337
        for source in self._revision_sources:
 
338
            try:
 
339
                return source.get_revision(revision_id)
 
340
            except errors.NoSuchRevision, e:
 
341
                pass
 
342
        raise e
 
343
 
 
344
    def get_revision_graph(self, revision_id):
 
345
        # we could probe incrementally until the pending
 
346
        # ghosts list stop growing, but its cheaper for now
 
347
        # to just ask for the complete graph for each repository.
 
348
        graphs = []
 
349
        for source in self._revision_sources:
 
350
            ghost_graph = source.get_revision_graph_with_ghosts()
 
351
            graphs.append(ghost_graph)
 
352
        absent = 0
 
353
        for graph in graphs:
 
354
            if not revision_id in graph.get_ancestors():
 
355
                absent += 1
 
356
        if absent == len(graphs):
 
357
            raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
 
358
 
 
359
        # combine the graphs
 
360
        result = {}
 
361
        pending = set([revision_id])
 
362
        def find_parents(node_id):
 
363
            """find the parents for node_id."""
 
364
            for graph in graphs:
 
365
                ancestors = graph.get_ancestors()
 
366
                try:
 
367
                    return ancestors[node_id]
 
368
                except KeyError:
 
369
                    pass
 
370
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
371
        while len(pending):
 
372
            # all the graphs should have identical parent lists
 
373
            node_id = pending.pop()
 
374
            try:
 
375
                result[node_id] = find_parents(node_id)
 
376
                for parent_node in result[node_id]:
 
377
                    if not parent_node in result:
 
378
                        pending.add(parent_node)
 
379
            except errors.NoSuchRevision:
 
380
                # ghost, ignore it.
 
381
                pass
 
382
        return result
 
383
 
 
384
    def get_revision_graph_with_ghosts(self, revision_ids):
 
385
        # query all the sources for their entire graphs 
 
386
        # and then build a combined graph for just
 
387
        # revision_ids.
 
388
        graphs = []
 
389
        for source in self._revision_sources:
 
390
            ghost_graph = source.get_revision_graph_with_ghosts()
 
391
            graphs.append(ghost_graph.get_ancestors())
 
392
        for revision_id in revision_ids:
 
393
            absent = 0
 
394
            for graph in graphs:
 
395
                    if not revision_id in graph:
 
396
                        absent += 1
 
397
            if absent == len(graphs):
 
398
                raise errors.NoSuchRevision(self._revision_sources[0],
 
399
                                            revision_id)
 
400
 
 
401
        # combine the graphs
 
402
        result = Graph()
 
403
        pending = set(revision_ids)
 
404
        done = set()
 
405
        def find_parents(node_id):
 
406
            """find the parents for node_id."""
 
407
            for graph in graphs:
 
408
                try:
 
409
                    return graph[node_id]
 
410
                except KeyError:
 
411
                    pass
 
412
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
413
        while len(pending):
 
414
            # all the graphs should have identical parent lists
 
415
            node_id = pending.pop()
 
416
            try:
 
417
                parents = find_parents(node_id)
 
418
                for parent_node in parents:
 
419
                    # queued or done? 
 
420
                    if (parent_node not in pending and
 
421
                        parent_node not in done):
 
422
                        # no, queue
 
423
                        pending.add(parent_node)
 
424
                result.add_node(node_id, parents)
 
425
                done.add(node_id)
 
426
            except errors.NoSuchRevision:
 
427
                # ghost
 
428
                result.add_ghost(node_id)
 
429
                continue
 
430
        return result
 
431
 
 
432
    def lock_read(self):
 
433
        for source in self._revision_sources:
 
434
            source.lock_read()
 
435
 
 
436
    def unlock(self):
 
437
        for source in self._revision_sources:
 
438
            source.unlock()
 
439
 
 
440
 
167
441
def is_reserved_id(revision_id):
168
442
    """Determine whether a revision id is reserved
169
443