← 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: 2008-03-16 14:01:20 UTC
  • mfrom: (3280.2.5 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20080316140120-i3yq8yr1l66m11h7
Start 1.4 development

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
16
 
 
17
 
from __future__ import absolute_import
18
 
 
19
 
# TODO: Some kind of command-line display of revision properties:
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
# TODO: Some kind of command-line display of revision properties: 
20
18
# perhaps show them in log -v and allow them as options to the commit command.
21
19
 
22
20
 
23
 
from bzrlib.lazy_import import lazy_import
24
 
lazy_import(globals(), """
25
 
from bzrlib import bugtracker
26
 
""")
27
21
from bzrlib import (
28
22
    errors,
29
23
    symbol_versioning,
30
24
    )
 
25
from bzrlib.deprecated_graph import (
 
26
    all_descendants,
 
27
    Graph,
 
28
    node_distances,
 
29
    select_farthest,
 
30
    )
31
31
from bzrlib.osutils import contains_whitespace
 
32
from bzrlib.progress import DummyProgress
 
33
from bzrlib.symbol_versioning import (deprecated_function,
 
34
        )
32
35
 
33
36
NULL_REVISION="null:"
34
37
CURRENT_REVISION="current:"
48
51
 
49
52
    properties
50
53
        Dictionary of revision properties.  These are attached to the
51
 
        revision as extra metadata.  The name must be a single
 
54
        revision as extra metadata.  The name must be a single 
52
55
        word; the value can be an arbitrary string.
53
56
    """
54
 
 
 
57
    
55
58
    def __init__(self, revision_id, properties=None, **args):
56
59
        self.revision_id = revision_id
57
 
        if properties is None:
58
 
            self.properties = {}
59
 
        else:
60
 
            self.properties = properties
61
 
            self._check_properties()
62
 
        self.committer = None
 
60
        self.properties = properties or {}
 
61
        self._check_properties()
63
62
        self.parent_ids = []
64
63
        self.parent_sha1s = []
65
64
        """Not used anymore - legacy from for 4."""
71
70
    def __eq__(self, other):
72
71
        if not isinstance(other, Revision):
73
72
            return False
 
73
        # FIXME: rbc 20050930 parent_ids are not being compared
74
74
        return (
75
75
                self.inventory_sha1 == other.inventory_sha1
76
76
                and self.revision_id == other.revision_id
78
78
                and self.message == other.message
79
79
                and self.timezone == other.timezone
80
80
                and self.committer == other.committer
81
 
                and self.properties == other.properties
82
 
                and self.parent_ids == other.parent_ids)
 
81
                and self.properties == other.properties)
83
82
 
84
83
    def __ne__(self, other):
85
84
        return not self.__eq__(other)
90
89
            if not isinstance(name, basestring) or contains_whitespace(name):
91
90
                raise ValueError("invalid property name %r" % name)
92
91
            if not isinstance(value, basestring):
93
 
                raise ValueError("invalid property value %r for %r" %
94
 
                                 (value, name))
 
92
                raise ValueError("invalid property value %r for %r" % 
 
93
                                 (name, value))
95
94
 
96
95
    def get_history(self, repository):
97
96
        """Return the canonical line-of-history for this revision.
114
113
 
115
114
    def get_summary(self):
116
115
        """Get the first line of the log message for this revision.
117
 
 
118
 
        Return an empty string if message is None.
119
 
        """
120
 
        if self.message:
121
 
            return self.message.lstrip().split('\n', 1)[0]
122
 
        else:
123
 
            return ''
124
 
 
125
 
    def get_apparent_authors(self):
126
 
        """Return the apparent authors of this revision.
127
 
 
128
 
        If the revision properties contain the names of the authors,
129
 
        return them. Otherwise return the committer name.
130
 
 
131
 
        The return value will be a list containing at least one element.
132
 
        """
133
 
        authors = self.properties.get('authors', None)
134
 
        if authors is None:
135
 
            author = self.properties.get('author', self.committer)
136
 
            if author is None:
137
 
                return []
138
 
            return [author]
139
 
        else:
140
 
            return authors.split("\n")
141
 
 
142
 
    def iter_bugs(self):
143
 
        """Iterate over the bugs associated with this revision."""
144
 
        bug_property = self.properties.get('bugs', None)
145
 
        if bug_property is None:
146
 
            return
147
 
        for line in bug_property.splitlines():
148
 
            try:
149
 
                url, status = line.split(None, 2)
150
 
            except ValueError:
151
 
                raise errors.InvalidLineInBugsProperty(line)
152
 
            if status not in bugtracker.ALLOWED_BUG_STATUSES:
153
 
                raise errors.InvalidBugStatus(status)
154
 
            yield url, status
 
116
        """
 
117
        return self.message.lstrip().split('\n', 1)[0]
 
118
 
 
119
    def get_apparent_author(self):
 
120
        """Return the apparent author of this revision.
 
121
 
 
122
        If the revision properties contain the author name,
 
123
        return it. Otherwise return the committer name.
 
124
        """
 
125
        return self.properties.get('author', self.committer)
 
126
 
 
127
 
 
128
@deprecated_function(symbol_versioning.one_zero)
 
129
def is_ancestor(revision_id, candidate_id, branch):
 
130
    """Return true if candidate_id is an ancestor of revision_id.
 
131
 
 
132
    A false negative will be returned if any intermediate descendent of
 
133
    candidate_id is not present in any of the revision_sources.
 
134
    
 
135
    revisions_source is an object supporting a get_revision operation that
 
136
    behaves like Branch's.
 
137
 
 
138
    This function is deprecated, it is better for callers to directly use
 
139
    Graph.is_ancestor() (just watch out that the parameter order is switched)
 
140
    """
 
141
    return branch.repository.get_graph().is_ancestor(candidate_id, revision_id)
155
142
 
156
143
 
157
144
def iter_ancestors(revision_id, revision_source, only_present=False):
166
153
                revision = revision_source.get_revision(ancestor)
167
154
            except errors.NoSuchRevision, e:
168
155
                if e.revision == revision_id:
169
 
                    raise
 
156
                    raise 
170
157
                else:
171
158
                    continue
172
159
            if only_present:
180
167
    """Return the ancestors of a revision present in a branch.
181
168
 
182
169
    It's possible that a branch won't have the complete ancestry of
183
 
    one of its revisions.
 
170
    one of its revisions.  
184
171
 
185
172
    """
186
173
    found_ancestors = {}
190
177
        if anc_id not in found_ancestors:
191
178
            found_ancestors[anc_id] = (anc_order, anc_distance)
192
179
    return found_ancestors
193
 
 
 
180
    
194
181
 
195
182
def __get_closest(intersection):
196
183
    intersection.sort()
197
 
    matches = []
 
184
    matches = [] 
198
185
    for entry in intersection:
199
186
        if entry[0] == intersection[0][0]:
200
187
            matches.append(entry[2])
201
188
    return matches
202
189
 
203
190
 
 
191
def revision_graph(revision, revision_source):
 
192
    """Produce a graph of the ancestry of the specified revision.
 
193
    
 
194
    :return: root, ancestors map, descendants map
 
195
    """
 
196
    revision_source.lock_read()
 
197
    try:
 
198
        return _revision_graph(revision, revision_source)
 
199
    finally:
 
200
        revision_source.unlock()
 
201
 
 
202
 
 
203
def _revision_graph(revision, revision_source):
 
204
    """See revision_graph."""
 
205
    from bzrlib.tsort import topo_sort
 
206
    graph = revision_source.get_revision_graph(revision)
 
207
    # mark all no-parent revisions as being NULL_REVISION parentage.
 
208
    for node, parents in graph.items():
 
209
        if len(parents) == 0:
 
210
            graph[node] = [NULL_REVISION]
 
211
    # add NULL_REVISION to the graph
 
212
    graph[NULL_REVISION] = []
 
213
 
 
214
    # pick a root. If there are multiple roots
 
215
    # this could pick a random one.
 
216
    topo_order = topo_sort(graph.items())
 
217
    root = topo_order[0]
 
218
 
 
219
    ancestors = {}
 
220
    descendants = {}
 
221
 
 
222
    # map the descendants of the graph.
 
223
    # and setup our set based return graph.
 
224
    for node in graph.keys():
 
225
        descendants[node] = {}
 
226
    for node, parents in graph.items():
 
227
        for parent in parents:
 
228
            descendants[parent][node] = 1
 
229
        ancestors[node] = set(parents)
 
230
 
 
231
    assert root not in descendants[root]
 
232
    assert root not in ancestors[root]
 
233
    return root, ancestors, descendants
 
234
 
 
235
 
 
236
@deprecated_function(symbol_versioning.one_three)
 
237
def combined_graph(revision_a, revision_b, revision_source):
 
238
    """Produce a combined ancestry graph.
 
239
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
240
    root, ancestors, descendants = revision_graph(
 
241
        revision_a, revision_source)
 
242
    root_b, ancestors_b, descendants_b = revision_graph(
 
243
        revision_b, revision_source)
 
244
    if root != root_b:
 
245
        raise errors.NoCommonRoot(revision_a, revision_b)
 
246
    common = set()
 
247
    for node, node_anc in ancestors_b.iteritems():
 
248
        if node in ancestors:
 
249
            common.add(node)
 
250
        else:
 
251
            ancestors[node] = set()
 
252
        ancestors[node].update(node_anc)
 
253
    for node, node_dec in descendants_b.iteritems():
 
254
        if node not in descendants:
 
255
            descendants[node] = {}
 
256
        descendants[node].update(node_dec)
 
257
    return root, ancestors, descendants, common
 
258
 
 
259
 
 
260
@deprecated_function(symbol_versioning.one_three)
 
261
def common_ancestor(revision_a, revision_b, revision_source, 
 
262
                    pb=DummyProgress()):
 
263
    if None in (revision_a, revision_b):
 
264
        return None
 
265
    if NULL_REVISION in (revision_a, revision_b):
 
266
        return NULL_REVISION
 
267
    # trivial optimisation
 
268
    if revision_a == revision_b:
 
269
        return revision_a
 
270
    try:
 
271
        try:
 
272
            pb.update('Picking ancestor', 1, 3)
 
273
            graph = revision_source.get_revision_graph_with_ghosts(
 
274
                [revision_a, revision_b])
 
275
            # Shortcut the case where one of the tips is already included in
 
276
            # the other graphs ancestry.
 
277
            ancestry_a = graph.get_ancestry(revision_a, topo_sorted=False)
 
278
            if revision_b in ancestry_a:
 
279
                return revision_b
 
280
            ancestry_b = graph.get_ancestry(revision_b, topo_sorted=False)
 
281
            if revision_a in ancestry_b:
 
282
                return revision_a
 
283
            # convert to a NULL_REVISION based graph.
 
284
            ancestors = graph.get_ancestors()
 
285
            descendants = graph.get_descendants()
 
286
            common = set(ancestry_a)
 
287
            common.intersection_update(ancestry_b)
 
288
            descendants[NULL_REVISION] = {}
 
289
            ancestors[NULL_REVISION] = []
 
290
            for root in graph.roots:
 
291
                descendants[NULL_REVISION][root] = 1
 
292
                ancestors[root].append(NULL_REVISION)
 
293
            for ghost in graph.ghosts:
 
294
                # ghosts act as roots for the purpose of finding 
 
295
                # the longest paths from the root: any ghost *might*
 
296
                # be directly attached to the root, so we treat them
 
297
                # as being such.
 
298
                # ghost now descends from NULL
 
299
                descendants[NULL_REVISION][ghost] = 1
 
300
                # that is it has an ancestor of NULL
 
301
                ancestors[ghost] = [NULL_REVISION]
 
302
                # ghost is common if any of ghosts descendants are common:
 
303
                for ghost_descendant in descendants[ghost]:
 
304
                    if ghost_descendant in common:
 
305
                        common.add(ghost)
 
306
                
 
307
            root = NULL_REVISION
 
308
            common.add(NULL_REVISION)
 
309
        except errors.NoCommonRoot:
 
310
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
311
            
 
312
        pb.update('Picking ancestor', 2, 3)
 
313
        distances = node_distances (descendants, ancestors, root)
 
314
        pb.update('Picking ancestor', 3, 2)
 
315
        farthest = select_farthest(distances, common)
 
316
        if farthest is None or farthest == NULL_REVISION:
 
317
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
318
    finally:
 
319
        pb.clear()
 
320
    return farthest
 
321
 
 
322
 
 
323
class MultipleRevisionSources(object):
 
324
    """Proxy that looks in multiple branches for revisions."""
 
325
 
 
326
    @symbol_versioning.deprecated_method(symbol_versioning.one_three)
 
327
    def __init__(self, *args):
 
328
        object.__init__(self)
 
329
        assert len(args) != 0
 
330
        self._revision_sources = args
 
331
 
 
332
    def revision_parents(self, revision_id):
 
333
        for source in self._revision_sources:
 
334
            try:
 
335
                return source.revision_parents(revision_id)
 
336
            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
 
337
                pass
 
338
        raise e
 
339
 
 
340
    def get_revision(self, revision_id):
 
341
        for source in self._revision_sources:
 
342
            try:
 
343
                return source.get_revision(revision_id)
 
344
            except errors.NoSuchRevision, e:
 
345
                pass
 
346
        raise e
 
347
 
 
348
    def get_revision_graph(self, revision_id):
 
349
        # we could probe incrementally until the pending
 
350
        # ghosts list stop growing, but its cheaper for now
 
351
        # to just ask for the complete graph for each repository.
 
352
        graphs = []
 
353
        for source in self._revision_sources:
 
354
            ghost_graph = source.get_revision_graph_with_ghosts()
 
355
            graphs.append(ghost_graph)
 
356
        absent = 0
 
357
        for graph in graphs:
 
358
            if not revision_id in graph.get_ancestors():
 
359
                absent += 1
 
360
        if absent == len(graphs):
 
361
            raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
 
362
 
 
363
        # combine the graphs
 
364
        result = {}
 
365
        pending = set([revision_id])
 
366
        def find_parents(node_id):
 
367
            """find the parents for node_id."""
 
368
            for graph in graphs:
 
369
                ancestors = graph.get_ancestors()
 
370
                try:
 
371
                    return ancestors[node_id]
 
372
                except KeyError:
 
373
                    pass
 
374
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
375
        while len(pending):
 
376
            # all the graphs should have identical parent lists
 
377
            node_id = pending.pop()
 
378
            try:
 
379
                result[node_id] = find_parents(node_id)
 
380
                for parent_node in result[node_id]:
 
381
                    if not parent_node in result:
 
382
                        pending.add(parent_node)
 
383
            except errors.NoSuchRevision:
 
384
                # ghost, ignore it.
 
385
                pass
 
386
        return result
 
387
 
 
388
    def get_revision_graph_with_ghosts(self, revision_ids):
 
389
        # query all the sources for their entire graphs 
 
390
        # and then build a combined graph for just
 
391
        # revision_ids.
 
392
        graphs = []
 
393
        for source in self._revision_sources:
 
394
            ghost_graph = source.get_revision_graph_with_ghosts()
 
395
            graphs.append(ghost_graph.get_ancestors())
 
396
        for revision_id in revision_ids:
 
397
            absent = 0
 
398
            for graph in graphs:
 
399
                    if not revision_id in graph:
 
400
                        absent += 1
 
401
            if absent == len(graphs):
 
402
                raise errors.NoSuchRevision(self._revision_sources[0],
 
403
                                            revision_id)
 
404
 
 
405
        # combine the graphs
 
406
        result = Graph()
 
407
        pending = set(revision_ids)
 
408
        done = set()
 
409
        def find_parents(node_id):
 
410
            """find the parents for node_id."""
 
411
            for graph in graphs:
 
412
                try:
 
413
                    return graph[node_id]
 
414
                except KeyError:
 
415
                    pass
 
416
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
417
        while len(pending):
 
418
            # all the graphs should have identical parent lists
 
419
            node_id = pending.pop()
 
420
            try:
 
421
                parents = find_parents(node_id)
 
422
                for parent_node in parents:
 
423
                    # queued or done? 
 
424
                    if (parent_node not in pending and
 
425
                        parent_node not in done):
 
426
                        # no, queue
 
427
                        pending.add(parent_node)
 
428
                result.add_node(node_id, parents)
 
429
                done.add(node_id)
 
430
            except errors.NoSuchRevision:
 
431
                # ghost
 
432
                result.add_ghost(node_id)
 
433
                continue
 
434
        return result
 
435
 
 
436
    def lock_read(self):
 
437
        for source in self._revision_sources:
 
438
            source.lock_read()
 
439
 
 
440
    def unlock(self):
 
441
        for source in self._revision_sources:
 
442
            source.unlock()
 
443
 
 
444
 
204
445
def is_reserved_id(revision_id):
205
446
    """Determine whether a revision id is reserved
206
447
 
207
 
    :return: True if the revision is reserved, False otherwise
 
448
    :return: True if the revision is is reserved, False otherwise
208
449
    """
209
450
    return isinstance(revision_id, basestring) and revision_id.endswith(':')
210
451