← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Andrew Bennetts
  • Date: 2007-03-26 06:24:01 UTC
  • mto: This revision was merged to the branch mainline in revision 2376.
  • Revision ID: andrew.bennetts@canonical.com-20070326062401-k3nbefzje5332jaf
Deal with review comments from Robert:

  * Add my name to the NEWS file
  * Move the test case to a new module in branch_implementations
  * Remove revision_history cruft from identitymap and test_identitymap
  * Improve some docstrings

Also, this fixes a bug where revision_history was not returning a copy of the
cached data, allowing the cache to be corrupted.

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
            # convert to a NULL_REVISION based graph.
 
255
            ancestors = graph.get_ancestors()
 
256
            descendants = graph.get_descendants()
 
257
            common = set(graph.get_ancestry(revision_a)).intersection(
 
258
                     set(graph.get_ancestry(revision_b)))
 
259
            descendants[NULL_REVISION] = {}
 
260
            ancestors[NULL_REVISION] = []
 
261
            for root in graph.roots:
 
262
                descendants[NULL_REVISION][root] = 1
 
263
                ancestors[root].append(NULL_REVISION)
 
264
            for ghost in graph.ghosts:
 
265
                # ghosts act as roots for the purpose of finding 
 
266
                # the longest paths from the root: any ghost *might*
 
267
                # be directly attached to the root, so we treat them
 
268
                # as being such.
 
269
                # ghost now descends from NULL
 
270
                descendants[NULL_REVISION][ghost] = 1
 
271
                # that is it has an ancestor of NULL
 
272
                ancestors[ghost] = [NULL_REVISION]
 
273
                # ghost is common if any of ghosts descendants are common:
 
274
                for ghost_descendant in descendants[ghost]:
 
275
                    if ghost_descendant in common:
 
276
                        common.add(ghost)
 
277
                
 
278
            root = NULL_REVISION
 
279
            common.add(NULL_REVISION)
 
280
        except errors.NoCommonRoot:
 
281
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
282
            
 
283
        pb.update('Picking ancestor', 2, 3)
 
284
        distances = node_distances (descendants, ancestors, root)
 
285
        pb.update('Picking ancestor', 3, 2)
 
286
        farthest = select_farthest(distances, common)
 
287
        if farthest is None or farthest == NULL_REVISION:
 
288
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
289
    finally:
 
290
        pb.clear()
 
291
    return farthest
 
292
 
 
293
 
 
294
class MultipleRevisionSources(object):
 
295
    """Proxy that looks in multiple branches for revisions."""
 
296
    def __init__(self, *args):
 
297
        object.__init__(self)
 
298
        assert len(args) != 0
 
299
        self._revision_sources = args
 
300
 
 
301
    def revision_parents(self, revision_id):
 
302
        for source in self._revision_sources:
 
303
            try:
 
304
                return source.revision_parents(revision_id)
 
305
            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
 
306
                pass
 
307
        raise e
 
308
 
 
309
    def get_revision(self, revision_id):
 
310
        for source in self._revision_sources:
 
311
            try:
 
312
                return source.get_revision(revision_id)
 
313
            except errors.NoSuchRevision, e:
 
314
                pass
 
315
        raise e
 
316
 
 
317
    def get_revision_graph(self, revision_id):
 
318
        # we could probe incrementally until the pending
 
319
        # ghosts list stop growing, but its cheaper for now
 
320
        # to just ask for the complete graph for each repository.
 
321
        graphs = []
 
322
        for source in self._revision_sources:
 
323
            ghost_graph = source.get_revision_graph_with_ghosts()
 
324
            graphs.append(ghost_graph)
 
325
        absent = 0
 
326
        for graph in graphs:
 
327
            if not revision_id in graph.get_ancestors():
 
328
                absent += 1
 
329
        if absent == len(graphs):
 
330
            raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
 
331
 
 
332
        # combine the graphs
 
333
        result = {}
 
334
        pending = set([revision_id])
 
335
        def find_parents(node_id):
 
336
            """find the parents for node_id."""
 
337
            for graph in graphs:
 
338
                ancestors = graph.get_ancestors()
 
339
                try:
 
340
                    return ancestors[node_id]
 
341
                except KeyError:
 
342
                    pass
 
343
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
344
        while len(pending):
 
345
            # all the graphs should have identical parent lists
 
346
            node_id = pending.pop()
 
347
            try:
 
348
                result[node_id] = find_parents(node_id)
 
349
                for parent_node in result[node_id]:
 
350
                    if not parent_node in result:
 
351
                        pending.add(parent_node)
 
352
            except errors.NoSuchRevision:
 
353
                # ghost, ignore it.
 
354
                pass
 
355
        return result
 
356
 
 
357
    def get_revision_graph_with_ghosts(self, revision_ids):
 
358
        # query all the sources for their entire graphs 
 
359
        # and then build a combined graph for just
 
360
        # revision_ids.
 
361
        graphs = []
 
362
        for source in self._revision_sources:
 
363
            ghost_graph = source.get_revision_graph_with_ghosts()
 
364
            graphs.append(ghost_graph.get_ancestors())
 
365
        for revision_id in revision_ids:
 
366
            absent = 0
 
367
            for graph in graphs:
 
368
                    if not revision_id in graph:
 
369
                        absent += 1
 
370
            if absent == len(graphs):
 
371
                raise errors.NoSuchRevision(self._revision_sources[0],
 
372
                                            revision_id)
 
373
 
 
374
        # combine the graphs
 
375
        result = Graph()
 
376
        pending = set(revision_ids)
 
377
        done = set()
 
378
        def find_parents(node_id):
 
379
            """find the parents for node_id."""
 
380
            for graph in graphs:
 
381
                try:
 
382
                    return graph[node_id]
 
383
                except KeyError:
 
384
                    pass
 
385
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
386
        while len(pending):
 
387
            # all the graphs should have identical parent lists
 
388
            node_id = pending.pop()
 
389
            try:
 
390
                parents = find_parents(node_id)
 
391
                for parent_node in parents:
 
392
                    # queued or done? 
 
393
                    if (parent_node not in pending and
 
394
                        parent_node not in done):
 
395
                        # no, queue
 
396
                        pending.add(parent_node)
 
397
                result.add_node(node_id, parents)
 
398
                done.add(node_id)
 
399
            except errors.NoSuchRevision:
 
400
                # ghost
 
401
                result.add_ghost(node_id)
 
402
                continue
 
403
        return result
 
404
 
 
405
    def lock_read(self):
 
406
        for source in self._revision_sources:
 
407
            source.lock_read()
 
408
 
 
409
    def unlock(self):
 
410
        for source in self._revision_sources:
 
411
            source.unlock()
 
412
 
 
413
 
 
414
@deprecated_function(zero_eight)
 
415
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
 
416
                              revision_history=None):
 
417
    """Find the longest line of descent from maybe_ancestor to revision.
 
418
    Revision history is followed where possible.
 
419
 
 
420
    If ancestor_id == rev_id, list will be empty.
 
421
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
422
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
423
    """
 
424
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
425
    if len(descendants) == 0:
 
426
        raise errors.NoSuchRevision(rev_source, rev_id)
 
427
    if ancestor_id not in descendants:
 
428
        rev_source.get_revision(ancestor_id)
 
429
        raise errors.NotAncestor(rev_id, ancestor_id)
 
430
    root_descendants = all_descendants(descendants, ancestor_id)
 
431
    root_descendants.add(ancestor_id)
 
432
    if rev_id not in root_descendants:
 
433
        raise errors.NotAncestor(rev_id, ancestor_id)
 
434
    distances = node_distances(descendants, ancestors, ancestor_id,
 
435
                               root_descendants=root_descendants)
 
436
 
 
437
    def best_ancestor(rev_id):
 
438
        best = None
 
439
        for anc_id in ancestors[rev_id]:
 
440
            try:
 
441
                distance = distances[anc_id]
 
442
            except KeyError:
 
443
                continue
 
444
            if revision_history is not None and anc_id in revision_history:
 
445
                return anc_id
 
446
            elif best is None or distance > best[1]:
 
447
                best = (anc_id, distance)
 
448
        return best[0]
 
449
 
 
450
    next = rev_id
 
451
    path = []
 
452
    while next != ancestor_id:
 
453
        path.append(next)
 
454
        next = best_ancestor(next)
 
455
    path.reverse()
 
456
    return path
 
457
 
 
458
 
167
459
def is_reserved_id(revision_id):
168
460
    """Determine whether a revision id is reserved
169
461
 
176
468
    """Raise ReservedId if the supplied revision_id is reserved"""
177
469
    if is_reserved_id(revision_id):
178
470
        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)