← 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-12 21:33:07 UTC
  • mfrom: (2413.4.1 api-doc-builders)
  • mto: This revision was merged to the branch mainline in revision 2566.
  • Revision ID: john@arbash-meinel.com-20070412213307-kuh07cnzaud12wx1
[merge] api-doc-builder and remove the pydoctor build code for now.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
1
 
# Copyright (C) 2005-2011 Canonical Ltd
 
1
# Copyright (C) 2005, 2006 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
 
# TODO: Some kind of command-line display of revision properties:
 
17
# TODO: Some kind of command-line display of revision properties: 
18
18
# perhaps show them in log -v and allow them as options to the commit command.
19
19
 
20
20
 
21
 
from bzrlib.lazy_import import lazy_import
22
 
lazy_import(globals(), """
23
 
from bzrlib import bugtracker
24
 
""")
25
 
from bzrlib import (
26
 
    errors,
27
 
    symbol_versioning,
28
 
    )
 
21
import bzrlib.errors as errors
 
22
from bzrlib.graph import node_distances, select_farthest, all_descendants, Graph
29
23
from bzrlib.osutils import contains_whitespace
 
24
from bzrlib.progress import DummyProgress
 
25
from bzrlib.symbol_versioning import (deprecated_function,
 
26
        zero_eight,
 
27
        )
30
28
 
31
29
NULL_REVISION="null:"
32
30
CURRENT_REVISION="current:"
46
44
 
47
45
    properties
48
46
        Dictionary of revision properties.  These are attached to the
49
 
        revision as extra metadata.  The name must be a single
 
47
        revision as extra metadata.  The name must be a single 
50
48
        word; the value can be an arbitrary string.
51
49
    """
52
 
 
 
50
    
53
51
    def __init__(self, revision_id, properties=None, **args):
54
52
        self.revision_id = revision_id
55
 
        if properties is None:
56
 
            self.properties = {}
57
 
        else:
58
 
            self.properties = properties
59
 
            self._check_properties()
60
 
        self.committer = None
 
53
        self.properties = properties or {}
 
54
        self._check_properties()
61
55
        self.parent_ids = []
62
56
        self.parent_sha1s = []
63
57
        """Not used anymore - legacy from for 4."""
69
63
    def __eq__(self, other):
70
64
        if not isinstance(other, Revision):
71
65
            return False
 
66
        # FIXME: rbc 20050930 parent_ids are not being compared
72
67
        return (
73
68
                self.inventory_sha1 == other.inventory_sha1
74
69
                and self.revision_id == other.revision_id
76
71
                and self.message == other.message
77
72
                and self.timezone == other.timezone
78
73
                and self.committer == other.committer
79
 
                and self.properties == other.properties
80
 
                and self.parent_ids == other.parent_ids)
 
74
                and self.properties == other.properties)
81
75
 
82
76
    def __ne__(self, other):
83
77
        return not self.__eq__(other)
88
82
            if not isinstance(name, basestring) or contains_whitespace(name):
89
83
                raise ValueError("invalid property name %r" % name)
90
84
            if not isinstance(value, basestring):
91
 
                raise ValueError("invalid property value %r for %r" %
92
 
                                 (value, name))
 
85
                raise ValueError("invalid property value %r for %r" % 
 
86
                                 (name, value))
93
87
 
94
88
    def get_history(self, repository):
95
89
        """Return the canonical line-of-history for this revision.
112
106
 
113
107
    def get_summary(self):
114
108
        """Get the first line of the log message for this revision.
115
 
 
116
 
        Return an empty string if message is None.
117
 
        """
118
 
        if self.message:
119
 
            return self.message.lstrip().split('\n', 1)[0]
120
 
        else:
121
 
            return ''
122
 
 
123
 
    def get_apparent_authors(self):
124
 
        """Return the apparent authors of this revision.
125
 
 
126
 
        If the revision properties contain the names of the authors,
127
 
        return them. Otherwise return the committer name.
128
 
 
129
 
        The return value will be a list containing at least one element.
130
 
        """
131
 
        authors = self.properties.get('authors', None)
132
 
        if authors is None:
133
 
            author = self.properties.get('author', self.committer)
134
 
            if author is None:
135
 
                return []
136
 
            return [author]
137
 
        else:
138
 
            return authors.split("\n")
139
 
 
140
 
    def iter_bugs(self):
141
 
        """Iterate over the bugs associated with this revision."""
142
 
        bug_property = self.properties.get('bugs', None)
143
 
        if bug_property is None:
144
 
            return
145
 
        for line in bug_property.splitlines():
146
 
            try:
147
 
                url, status = line.split(None, 2)
148
 
            except ValueError:
149
 
                raise errors.InvalidLineInBugsProperty(line)
150
 
            if status not in bugtracker.ALLOWED_BUG_STATUSES:
151
 
                raise errors.InvalidBugStatus(status)
152
 
            yield url, status
 
109
        """
 
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))
153
123
 
154
124
 
155
125
def iter_ancestors(revision_id, revision_source, only_present=False):
164
134
                revision = revision_source.get_revision(ancestor)
165
135
            except errors.NoSuchRevision, e:
166
136
                if e.revision == revision_id:
167
 
                    raise
 
137
                    raise 
168
138
                else:
169
139
                    continue
170
140
            if only_present:
178
148
    """Return the ancestors of a revision present in a branch.
179
149
 
180
150
    It's possible that a branch won't have the complete ancestry of
181
 
    one of its revisions.
 
151
    one of its revisions.  
182
152
 
183
153
    """
184
154
    found_ancestors = {}
188
158
        if anc_id not in found_ancestors:
189
159
            found_ancestors[anc_id] = (anc_order, anc_distance)
190
160
    return found_ancestors
191
 
 
 
161
    
192
162
 
193
163
def __get_closest(intersection):
194
164
    intersection.sort()
195
 
    matches = []
 
165
    matches = [] 
196
166
    for entry in intersection:
197
167
        if entry[0] == intersection[0][0]:
198
168
            matches.append(entry[2])
199
169
    return matches
200
170
 
201
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
 
202
467
def is_reserved_id(revision_id):
203
468
    """Determine whether a revision id is reserved
204
469
 
205
 
    :return: True if the revision is reserved, False otherwise
 
470
    :return: True if the revision is is reserved, False otherwise
206
471
    """
207
472
    return isinstance(revision_id, basestring) and revision_id.endswith(':')
208
473
 
211
476
    """Raise ReservedId if the supplied revision_id is reserved"""
212
477
    if is_reserved_id(revision_id):
213
478
        raise errors.ReservedId(revision_id)
214
 
 
215
 
 
216
 
def ensure_null(revision_id):
217
 
    """Ensure only NULL_REVISION is used to represent the null revision"""
218
 
    if revision_id is None:
219
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
220
 
            ' revision instead of None, as of bzr 0.91.',
221
 
            DeprecationWarning, stacklevel=2)
222
 
        return NULL_REVISION
223
 
    else:
224
 
        return revision_id
225
 
 
226
 
 
227
 
def is_null(revision_id):
228
 
    if revision_id is None:
229
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
230
 
            ' revision instead of None, as of bzr 0.90.',
231
 
            DeprecationWarning, stacklevel=2)
232
 
    return revision_id in (None, NULL_REVISION)