← 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: 2006-03-09 06:39:13 UTC
  • mfrom: (1596.2.6 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20060309063913-6d8ce700706d0802
Merge knit performance stage 1.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
20
20
 
21
21
import bzrlib.errors
22
22
import bzrlib.errors as errors
23
 
from bzrlib.graph import node_distances, select_farthest, all_descendants
 
23
from bzrlib.graph import node_distances, select_farthest, all_descendants, Graph
24
24
from bzrlib.osutils import contains_whitespace
25
25
from bzrlib.progress import DummyProgress
26
26
 
232
232
                    pb=DummyProgress()):
233
233
    if None in (revision_a, revision_b):
234
234
        return None
 
235
    # trivial optimisation
 
236
    if revision_a == revision_b:
 
237
        return revision_a
235
238
    try:
236
239
        try:
237
240
            pb.update('Picking ancestor', 1, 3)
238
 
            root, ancestors, descendants, common = \
239
 
                combined_graph(revision_a,
240
 
                               revision_b,
241
 
                               revision_source)
 
241
            graph = revision_source.get_revision_graph_with_ghosts(
 
242
                [revision_a, revision_b])
 
243
            # convert to a NULL_REVISION based graph.
 
244
            ancestors = graph.get_ancestors()
 
245
            descendants = graph.get_descendants()
 
246
            common = set(graph.get_ancestry(revision_a)).intersection(
 
247
                     set(graph.get_ancestry(revision_b)))
 
248
            descendants[NULL_REVISION] = {}
 
249
            ancestors[NULL_REVISION] = []
 
250
            for root in graph.roots:
 
251
                descendants[NULL_REVISION][root] = 1
 
252
                ancestors[root].append(NULL_REVISION)
 
253
            if len(graph.roots) == 0:
 
254
                # no reachable roots - not handled yet.
 
255
                raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
256
            root = NULL_REVISION
 
257
            common.add(NULL_REVISION)
242
258
        except bzrlib.errors.NoCommonRoot:
243
259
            raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
244
260
            
316
332
                pass
317
333
        return result
318
334
 
 
335
    def get_revision_graph_with_ghosts(self, revision_ids):
 
336
        # query all the sources for their entire graphs 
 
337
        # and then build a combined graph for just
 
338
        # revision_ids.
 
339
        graphs = []
 
340
        for source in self._revision_sources:
 
341
            ghost_graph = source.get_revision_graph_with_ghosts()
 
342
            graphs.append(ghost_graph.get_ancestors())
 
343
        for revision_id in revision_ids:
 
344
            absent = 0
 
345
            for graph in graphs:
 
346
                    if not revision_id in graph:
 
347
                        absent += 1
 
348
            if absent == len(graphs):
 
349
                raise errors.NoSuchRevision(self._revision_sources[0],
 
350
                                            revision_id)
 
351
 
 
352
        # combine the graphs
 
353
        result = Graph()
 
354
        pending = set(revision_ids)
 
355
        done = set()
 
356
        def find_parents(node_id):
 
357
            """find the parents for node_id."""
 
358
            for graph in graphs:
 
359
                try:
 
360
                    return graph[node_id]
 
361
                except KeyError:
 
362
                    pass
 
363
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
364
        while len(pending):
 
365
            # all the graphs should have identical parent lists
 
366
            node_id = pending.pop()
 
367
            try:
 
368
                parents = find_parents(node_id)
 
369
                for parent_node in parents:
 
370
                    # queued or done? 
 
371
                    if (parent_node not in pending and
 
372
                        parent_node not in done):
 
373
                        # no, queue
 
374
                        pending.add(parent_node)
 
375
                result.add_node(node_id, parents)
 
376
                done.add(node_id)
 
377
            except errors.NoSuchRevision:
 
378
                # ghost
 
379
                result.add_ghost(node_id)
 
380
                continue
 
381
        return result
 
382
 
319
383
    def lock_read(self):
320
384
        for source in self._revision_sources:
321
385
            source.lock_read()