← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: John Arbash Meinel
  • Date: 2007-04-28 15:04:17 UTC
  • mfrom: (2466 +trunk)
  • mto: This revision was merged to the branch mainline in revision 2566.
  • Revision ID: john@arbash-meinel.com-20070428150417-trp3pi0pzd411pu4
[merge] bzr.dev 2466

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
18
18
# perhaps show them in log -v and allow them as options to the commit command.
19
19
 
20
20
 
21
 
from bzrlib import (
22
 
    errors,
23
 
    symbol_versioning,
24
 
    )
 
21
import bzrlib.errors as errors
 
22
from bzrlib.graph import node_distances, select_farthest, all_descendants, Graph
25
23
from bzrlib.osutils import contains_whitespace
26
24
from bzrlib.progress import DummyProgress
 
25
from bzrlib.symbol_versioning import (deprecated_function,
 
26
        zero_eight,
 
27
        )
27
28
 
28
29
NULL_REVISION="null:"
29
30
CURRENT_REVISION="current:"
106
107
    def get_summary(self):
107
108
        """Get the first line of the log message for this revision.
108
109
        """
109
 
        return self.message.lstrip().split('\n', 1)[0]
110
 
 
111
 
    def get_apparent_author(self):
112
 
        """Return the apparent author of this revision.
113
 
 
114
 
        If the revision properties contain the author name,
115
 
        return it. Otherwise return the committer name.
116
 
        """
117
 
        return self.properties.get('author', self.committer)
 
110
        return self.message.split('\n', 1)[0]
 
111
 
 
112
 
 
113
def is_ancestor(revision_id, candidate_id, branch):
 
114
    """Return true if candidate_id is an ancestor of revision_id.
 
115
 
 
116
    A false negative will be returned if any intermediate descendent of
 
117
    candidate_id is not present in any of the revision_sources.
 
118
    
 
119
    revisions_source is an object supporting a get_revision operation that
 
120
    behaves like Branch's.
 
121
    """
 
122
    return (candidate_id in branch.repository.get_ancestry(revision_id))
118
123
 
119
124
 
120
125
def iter_ancestors(revision_id, revision_source, only_present=False):
164
169
    return matches
165
170
 
166
171
 
 
172
def revision_graph(revision, revision_source):
 
173
    """Produce a graph of the ancestry of the specified revision.
 
174
    
 
175
    :return: root, ancestors map, descendants map
 
176
    """
 
177
    revision_source.lock_read()
 
178
    try:
 
179
        return _revision_graph(revision, revision_source)
 
180
    finally:
 
181
        revision_source.unlock()
 
182
 
 
183
 
 
184
def _revision_graph(revision, revision_source):
 
185
    """See revision_graph."""
 
186
    from bzrlib.tsort import topo_sort
 
187
    graph = revision_source.get_revision_graph(revision)
 
188
    # mark all no-parent revisions as being NULL_REVISION parentage.
 
189
    for node, parents in graph.items():
 
190
        if len(parents) == 0:
 
191
            graph[node] = [NULL_REVISION]
 
192
    # add NULL_REVISION to the graph
 
193
    graph[NULL_REVISION] = []
 
194
 
 
195
    # pick a root. If there are multiple roots
 
196
    # this could pick a random one.
 
197
    topo_order = topo_sort(graph.items())
 
198
    root = topo_order[0]
 
199
 
 
200
    ancestors = {}
 
201
    descendants = {}
 
202
 
 
203
    # map the descendants of the graph.
 
204
    # and setup our set based return graph.
 
205
    for node in graph.keys():
 
206
        descendants[node] = {}
 
207
    for node, parents in graph.items():
 
208
        for parent in parents:
 
209
            descendants[parent][node] = 1
 
210
        ancestors[node] = set(parents)
 
211
 
 
212
    assert root not in descendants[root]
 
213
    assert root not in ancestors[root]
 
214
    return root, ancestors, descendants
 
215
 
 
216
 
 
217
def combined_graph(revision_a, revision_b, revision_source):
 
218
    """Produce a combined ancestry graph.
 
219
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
220
    root, ancestors, descendants = revision_graph(
 
221
        revision_a, revision_source)
 
222
    root_b, ancestors_b, descendants_b = revision_graph(
 
223
        revision_b, revision_source)
 
224
    if root != root_b:
 
225
        raise errors.NoCommonRoot(revision_a, revision_b)
 
226
    common = set()
 
227
    for node, node_anc in ancestors_b.iteritems():
 
228
        if node in ancestors:
 
229
            common.add(node)
 
230
        else:
 
231
            ancestors[node] = set()
 
232
        ancestors[node].update(node_anc)
 
233
    for node, node_dec in descendants_b.iteritems():
 
234
        if node not in descendants:
 
235
            descendants[node] = {}
 
236
        descendants[node].update(node_dec)
 
237
    return root, ancestors, descendants, common
 
238
 
 
239
 
 
240
def common_ancestor(revision_a, revision_b, revision_source, 
 
241
                    pb=DummyProgress()):
 
242
    if None in (revision_a, revision_b):
 
243
        return None
 
244
    if NULL_REVISION in (revision_a, revision_b):
 
245
        return NULL_REVISION
 
246
    # trivial optimisation
 
247
    if revision_a == revision_b:
 
248
        return revision_a
 
249
    try:
 
250
        try:
 
251
            pb.update('Picking ancestor', 1, 3)
 
252
            graph = revision_source.get_revision_graph_with_ghosts(
 
253
                [revision_a, revision_b])
 
254
            # Shortcut the case where one of the tips is already included in
 
255
            # the other graphs ancestry.
 
256
            ancestry_a = graph.get_ancestry(revision_a)
 
257
            if revision_b in ancestry_a:
 
258
                return revision_b
 
259
            ancestry_b = graph.get_ancestry(revision_b)
 
260
            if revision_a in ancestry_b:
 
261
                return revision_a
 
262
            # convert to a NULL_REVISION based graph.
 
263
            ancestors = graph.get_ancestors()
 
264
            descendants = graph.get_descendants()
 
265
            common = set(ancestry_a)
 
266
            common.intersection_update(ancestry_b)
 
267
            descendants[NULL_REVISION] = {}
 
268
            ancestors[NULL_REVISION] = []
 
269
            for root in graph.roots:
 
270
                descendants[NULL_REVISION][root] = 1
 
271
                ancestors[root].append(NULL_REVISION)
 
272
            for ghost in graph.ghosts:
 
273
                # ghosts act as roots for the purpose of finding 
 
274
                # the longest paths from the root: any ghost *might*
 
275
                # be directly attached to the root, so we treat them
 
276
                # as being such.
 
277
                # ghost now descends from NULL
 
278
                descendants[NULL_REVISION][ghost] = 1
 
279
                # that is it has an ancestor of NULL
 
280
                ancestors[ghost] = [NULL_REVISION]
 
281
                # ghost is common if any of ghosts descendants are common:
 
282
                for ghost_descendant in descendants[ghost]:
 
283
                    if ghost_descendant in common:
 
284
                        common.add(ghost)
 
285
                
 
286
            root = NULL_REVISION
 
287
            common.add(NULL_REVISION)
 
288
        except errors.NoCommonRoot:
 
289
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
290
            
 
291
        pb.update('Picking ancestor', 2, 3)
 
292
        distances = node_distances (descendants, ancestors, root)
 
293
        pb.update('Picking ancestor', 3, 2)
 
294
        farthest = select_farthest(distances, common)
 
295
        if farthest is None or farthest == NULL_REVISION:
 
296
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
297
    finally:
 
298
        pb.clear()
 
299
    return farthest
 
300
 
 
301
 
 
302
class MultipleRevisionSources(object):
 
303
    """Proxy that looks in multiple branches for revisions."""
 
304
    def __init__(self, *args):
 
305
        object.__init__(self)
 
306
        assert len(args) != 0
 
307
        self._revision_sources = args
 
308
 
 
309
    def revision_parents(self, revision_id):
 
310
        for source in self._revision_sources:
 
311
            try:
 
312
                return source.revision_parents(revision_id)
 
313
            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
 
314
                pass
 
315
        raise e
 
316
 
 
317
    def get_revision(self, revision_id):
 
318
        for source in self._revision_sources:
 
319
            try:
 
320
                return source.get_revision(revision_id)
 
321
            except errors.NoSuchRevision, e:
 
322
                pass
 
323
        raise e
 
324
 
 
325
    def get_revision_graph(self, revision_id):
 
326
        # we could probe incrementally until the pending
 
327
        # ghosts list stop growing, but its cheaper for now
 
328
        # to just ask for the complete graph for each repository.
 
329
        graphs = []
 
330
        for source in self._revision_sources:
 
331
            ghost_graph = source.get_revision_graph_with_ghosts()
 
332
            graphs.append(ghost_graph)
 
333
        absent = 0
 
334
        for graph in graphs:
 
335
            if not revision_id in graph.get_ancestors():
 
336
                absent += 1
 
337
        if absent == len(graphs):
 
338
            raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
 
339
 
 
340
        # combine the graphs
 
341
        result = {}
 
342
        pending = set([revision_id])
 
343
        def find_parents(node_id):
 
344
            """find the parents for node_id."""
 
345
            for graph in graphs:
 
346
                ancestors = graph.get_ancestors()
 
347
                try:
 
348
                    return ancestors[node_id]
 
349
                except KeyError:
 
350
                    pass
 
351
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
352
        while len(pending):
 
353
            # all the graphs should have identical parent lists
 
354
            node_id = pending.pop()
 
355
            try:
 
356
                result[node_id] = find_parents(node_id)
 
357
                for parent_node in result[node_id]:
 
358
                    if not parent_node in result:
 
359
                        pending.add(parent_node)
 
360
            except errors.NoSuchRevision:
 
361
                # ghost, ignore it.
 
362
                pass
 
363
        return result
 
364
 
 
365
    def get_revision_graph_with_ghosts(self, revision_ids):
 
366
        # query all the sources for their entire graphs 
 
367
        # and then build a combined graph for just
 
368
        # revision_ids.
 
369
        graphs = []
 
370
        for source in self._revision_sources:
 
371
            ghost_graph = source.get_revision_graph_with_ghosts()
 
372
            graphs.append(ghost_graph.get_ancestors())
 
373
        for revision_id in revision_ids:
 
374
            absent = 0
 
375
            for graph in graphs:
 
376
                    if not revision_id in graph:
 
377
                        absent += 1
 
378
            if absent == len(graphs):
 
379
                raise errors.NoSuchRevision(self._revision_sources[0],
 
380
                                            revision_id)
 
381
 
 
382
        # combine the graphs
 
383
        result = Graph()
 
384
        pending = set(revision_ids)
 
385
        done = set()
 
386
        def find_parents(node_id):
 
387
            """find the parents for node_id."""
 
388
            for graph in graphs:
 
389
                try:
 
390
                    return graph[node_id]
 
391
                except KeyError:
 
392
                    pass
 
393
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
394
        while len(pending):
 
395
            # all the graphs should have identical parent lists
 
396
            node_id = pending.pop()
 
397
            try:
 
398
                parents = find_parents(node_id)
 
399
                for parent_node in parents:
 
400
                    # queued or done? 
 
401
                    if (parent_node not in pending and
 
402
                        parent_node not in done):
 
403
                        # no, queue
 
404
                        pending.add(parent_node)
 
405
                result.add_node(node_id, parents)
 
406
                done.add(node_id)
 
407
            except errors.NoSuchRevision:
 
408
                # ghost
 
409
                result.add_ghost(node_id)
 
410
                continue
 
411
        return result
 
412
 
 
413
    def lock_read(self):
 
414
        for source in self._revision_sources:
 
415
            source.lock_read()
 
416
 
 
417
    def unlock(self):
 
418
        for source in self._revision_sources:
 
419
            source.unlock()
 
420
 
 
421
 
 
422
@deprecated_function(zero_eight)
 
423
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
 
424
                              revision_history=None):
 
425
    """Find the longest line of descent from maybe_ancestor to revision.
 
426
    Revision history is followed where possible.
 
427
 
 
428
    If ancestor_id == rev_id, list will be empty.
 
429
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
430
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
431
    """
 
432
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
433
    if len(descendants) == 0:
 
434
        raise errors.NoSuchRevision(rev_source, rev_id)
 
435
    if ancestor_id not in descendants:
 
436
        rev_source.get_revision(ancestor_id)
 
437
        raise errors.NotAncestor(rev_id, ancestor_id)
 
438
    root_descendants = all_descendants(descendants, ancestor_id)
 
439
    root_descendants.add(ancestor_id)
 
440
    if rev_id not in root_descendants:
 
441
        raise errors.NotAncestor(rev_id, ancestor_id)
 
442
    distances = node_distances(descendants, ancestors, ancestor_id,
 
443
                               root_descendants=root_descendants)
 
444
 
 
445
    def best_ancestor(rev_id):
 
446
        best = None
 
447
        for anc_id in ancestors[rev_id]:
 
448
            try:
 
449
                distance = distances[anc_id]
 
450
            except KeyError:
 
451
                continue
 
452
            if revision_history is not None and anc_id in revision_history:
 
453
                return anc_id
 
454
            elif best is None or distance > best[1]:
 
455
                best = (anc_id, distance)
 
456
        return best[0]
 
457
 
 
458
    next = rev_id
 
459
    path = []
 
460
    while next != ancestor_id:
 
461
        path.append(next)
 
462
        next = best_ancestor(next)
 
463
    path.reverse()
 
464
    return path
 
465
 
 
466
 
167
467
def is_reserved_id(revision_id):
168
468
    """Determine whether a revision id is reserved
169
469
 
176
476
    """Raise ReservedId if the supplied revision_id is reserved"""
177
477
    if is_reserved_id(revision_id):
178
478
        raise errors.ReservedId(revision_id)
179
 
 
180
 
 
181
 
def ensure_null(revision_id):
182
 
    """Ensure only NULL_REVISION is used to represent the null revision"""
183
 
    if revision_id is None:
184
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
185
 
            ' revision instead of None, as of bzr 0.91.',
186
 
            DeprecationWarning, stacklevel=2)
187
 
        return NULL_REVISION
188
 
    else:
189
 
        return revision_id
190
 
 
191
 
 
192
 
def is_null(revision_id):
193
 
    if revision_id is None:
194
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
195
 
            ' revision instead of None, as of bzr 0.90.',
196
 
            DeprecationWarning, stacklevel=2)
197
 
    return revision_id in (None, NULL_REVISION)