← 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-11-04 18:51:39 UTC
  • mfrom: (2961.1.1 trunk)
  • Revision ID: pqm@pqm.ubuntu.com-20071104185139-kaio3sneodg2kp71
Authentication ring implementation (read-only)

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