← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Martin Pool
  • Date: 2006-03-10 06:29:53 UTC
  • mfrom: (1608 +trunk)
  • mto: This revision was merged to the branch mainline in revision 1611.
  • Revision ID: mbp@sourcefrog.net-20060310062953-bc1c7ade75c89a7a
[merge] bzr.dev; pycurl not updated for readv yet

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
            
277
293
        raise e
278
294
 
279
295
    def get_revision_graph(self, revision_id):
 
296
        # we could probe incrementally until the pending
 
297
        # ghosts list stop growing, but its cheaper for now
 
298
        # to just ask for the complete graph for each repository.
 
299
        graphs = []
 
300
        for source in self._revision_sources:
 
301
            ghost_graph = source.get_revision_graph_with_ghosts()
 
302
            graphs.append(ghost_graph)
 
303
        absent = 0
 
304
        for graph in graphs:
 
305
            if not revision_id in graph.get_ancestors():
 
306
                absent += 1
 
307
        if absent == len(graphs):
 
308
            raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
 
309
 
 
310
        # combine the graphs
280
311
        result = {}
 
312
        pending = set([revision_id])
 
313
        def find_parents(node_id):
 
314
            """find the parents for node_id."""
 
315
            for graph in graphs:
 
316
                ancestors = graph.get_ancestors()
 
317
                try:
 
318
                    return ancestors[node_id]
 
319
                except KeyError:
 
320
                    pass
 
321
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
322
        while len(pending):
 
323
            # all the graphs should have identical parent lists
 
324
            node_id = pending.pop()
 
325
            try:
 
326
                result[node_id] = find_parents(node_id)
 
327
                for parent_node in result[node_id]:
 
328
                    if not parent_node in result:
 
329
                        pending.add(parent_node)
 
330
            except errors.NoSuchRevision:
 
331
                # ghost, ignore it.
 
332
                pass
 
333
        return result
 
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 = []
281
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()
282
367
            try:
283
 
                result.update(source.get_revision_graph(revision_id))
284
 
            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
285
 
                pass
286
 
        if result:
287
 
            return result
288
 
        raise e
 
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
289
382
 
290
383
    def lock_read(self):
291
384
        for source in self._revision_sources: