← 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: 2006-03-09 08:50:48 UTC
  • mfrom: (1553.5.83 bzr.mbp.locks)
  • Revision ID: pqm@pqm.ubuntu.com-20060309085048-37f21fd146dabe93
[merge] LockDir integration into new formats

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
1
 
# Copyright (C) 2005-2011 Canonical Ltd
2
 
#
 
1
# (C) 2005 Canonical
 
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
5
5
# the Free Software Foundation; either version 2 of the License, or
6
6
# (at your option) any later version.
7
 
#
 
7
 
8
8
# This program is distributed in the hope that it will be useful,
9
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
# GNU General Public License for more details.
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
 
from bzrlib import (
28
 
    errors,
29
 
    symbol_versioning,
30
 
    )
 
21
import bzrlib.errors
 
22
import bzrlib.errors as errors
 
23
from bzrlib.graph import node_distances, select_farthest, all_descendants, Graph
31
24
from bzrlib.osutils import contains_whitespace
 
25
from bzrlib.progress import DummyProgress
32
26
 
33
27
NULL_REVISION="null:"
34
 
CURRENT_REVISION="current:"
35
 
 
36
28
 
37
29
class Revision(object):
38
30
    """Single revision on a branch.
48
40
 
49
41
    properties
50
42
        Dictionary of revision properties.  These are attached to the
51
 
        revision as extra metadata.  The name must be a single
 
43
        revision as extra metadata.  The name must be a single 
52
44
        word; the value can be an arbitrary string.
53
45
    """
54
 
 
 
46
    
55
47
    def __init__(self, revision_id, properties=None, **args):
56
48
        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
 
49
        self.properties = properties or {}
 
50
        self._check_properties()
63
51
        self.parent_ids = []
64
52
        self.parent_sha1s = []
65
 
        """Not used anymore - legacy from for 4."""
66
53
        self.__dict__.update(args)
67
54
 
68
55
    def __repr__(self):
71
58
    def __eq__(self, other):
72
59
        if not isinstance(other, Revision):
73
60
            return False
 
61
        # FIXME: rbc 20050930 parent_ids are not being compared
74
62
        return (
75
63
                self.inventory_sha1 == other.inventory_sha1
76
64
                and self.revision_id == other.revision_id
78
66
                and self.message == other.message
79
67
                and self.timezone == other.timezone
80
68
                and self.committer == other.committer
81
 
                and self.properties == other.properties
82
 
                and self.parent_ids == other.parent_ids)
 
69
                and self.properties == other.properties)
83
70
 
84
71
    def __ne__(self, other):
85
72
        return not self.__eq__(other)
86
73
 
87
74
    def _check_properties(self):
88
 
        """Verify that all revision properties are OK."""
 
75
        """Verify that all revision properties are OK.
 
76
        """
89
77
        for name, value in self.properties.iteritems():
90
78
            if not isinstance(name, basestring) or contains_whitespace(name):
91
79
                raise ValueError("invalid property name %r" % name)
92
80
            if not isinstance(value, basestring):
93
 
                raise ValueError("invalid property value %r for %r" %
94
 
                                 (value, name))
 
81
                raise ValueError("invalid property value %r for %r" % 
 
82
                                 (name, value))
95
83
 
96
84
    def get_history(self, repository):
97
85
        """Return the canonical line-of-history for this revision.
112
100
        reversed_result.reverse()
113
101
        return reversed_result
114
102
 
115
 
    def get_summary(self):
116
 
        """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
 
103
 
 
104
def is_ancestor(revision_id, candidate_id, branch):
 
105
    """Return true if candidate_id is an ancestor of revision_id.
 
106
 
 
107
    A false negative will be returned if any intermediate descendent of
 
108
    candidate_id is not present in any of the revision_sources.
 
109
    
 
110
    revisions_source is an object supporting a get_revision operation that
 
111
    behaves like Branch's.
 
112
    """
 
113
    return candidate_id in branch.repository.get_ancestry(revision_id)
155
114
 
156
115
 
157
116
def iter_ancestors(revision_id, revision_source, only_present=False):
164
123
                yield ancestor, distance
165
124
            try:
166
125
                revision = revision_source.get_revision(ancestor)
167
 
            except errors.NoSuchRevision, e:
 
126
            except bzrlib.errors.NoSuchRevision, e:
168
127
                if e.revision == revision_id:
169
 
                    raise
 
128
                    raise 
170
129
                else:
171
130
                    continue
172
131
            if only_present:
180
139
    """Return the ancestors of a revision present in a branch.
181
140
 
182
141
    It's possible that a branch won't have the complete ancestry of
183
 
    one of its revisions.
 
142
    one of its revisions.  
184
143
 
185
144
    """
186
145
    found_ancestors = {}
187
146
    anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
188
147
                         only_present=True))
189
148
    for anc_order, (anc_id, anc_distance) in anc_iter:
190
 
        if anc_id not in found_ancestors:
 
149
        if not found_ancestors.has_key(anc_id):
191
150
            found_ancestors[anc_id] = (anc_order, anc_distance)
192
151
    return found_ancestors
193
 
 
 
152
    
194
153
 
195
154
def __get_closest(intersection):
196
155
    intersection.sort()
197
 
    matches = []
 
156
    matches = [] 
198
157
    for entry in intersection:
199
158
        if entry[0] == intersection[0][0]:
200
159
            matches.append(entry[2])
201
160
    return matches
202
161
 
203
162
 
204
 
def is_reserved_id(revision_id):
205
 
    """Determine whether a revision id is reserved
206
 
 
207
 
    :return: True if the revision is reserved, False otherwise
208
 
    """
209
 
    return isinstance(revision_id, basestring) and revision_id.endswith(':')
210
 
 
211
 
 
212
 
def check_not_reserved_id(revision_id):
213
 
    """Raise ReservedId if the supplied revision_id is reserved"""
214
 
    if is_reserved_id(revision_id):
215
 
        raise errors.ReservedId(revision_id)
216
 
 
217
 
 
218
 
def ensure_null(revision_id):
219
 
    """Ensure only NULL_REVISION is used to represent the null revision"""
220
 
    if revision_id is None:
221
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
222
 
            ' revision instead of None, as of bzr 0.91.',
223
 
            DeprecationWarning, stacklevel=2)
224
 
        return NULL_REVISION
225
 
    else:
226
 
        return revision_id
227
 
 
228
 
 
229
 
def is_null(revision_id):
230
 
    if revision_id is None:
231
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
232
 
            ' revision instead of None, as of bzr 0.90.',
233
 
            DeprecationWarning, stacklevel=2)
234
 
    return revision_id in (None, NULL_REVISION)
 
163
def revision_graph(revision, revision_source):
 
164
    """Produce a graph of the ancestry of the specified revision.
 
165
    
 
166
    :return: root, ancestors map, descendants map
 
167
    """
 
168
    revision_source.lock_read()
 
169
    try:
 
170
        return _revision_graph(revision, revision_source)
 
171
    finally:
 
172
        revision_source.unlock()
 
173
 
 
174
 
 
175
def _revision_graph(revision, revision_source):
 
176
    """See revision_graph."""
 
177
    from bzrlib.tsort import topo_sort
 
178
    graph = revision_source.get_revision_graph(revision)
 
179
    # mark all no-parent revisions as being NULL_REVISION parentage.
 
180
    for node, parents in graph.items():
 
181
        if len(parents) == 0:
 
182
            graph[node] = [NULL_REVISION]
 
183
    # add NULL_REVISION to the graph
 
184
    graph[NULL_REVISION] = []
 
185
 
 
186
    # pick a root. If there are multiple roots
 
187
    # this could pick a random one.
 
188
    topo_order = topo_sort(graph.items())
 
189
    root = topo_order[0]
 
190
 
 
191
    ancestors = {}
 
192
    descendants = {}
 
193
 
 
194
    # map the descendants of the graph.
 
195
    # and setup our set based return graph.
 
196
    for node in graph.keys():
 
197
        descendants[node] = {}
 
198
    for node, parents in graph.items():
 
199
        for parent in parents:
 
200
            descendants[parent][node] = 1
 
201
        ancestors[node] = set(parents)
 
202
 
 
203
    assert root not in descendants[root]
 
204
    assert root not in ancestors[root]
 
205
    return root, ancestors, descendants
 
206
 
 
207
 
 
208
def combined_graph(revision_a, revision_b, revision_source):
 
209
    """Produce a combined ancestry graph.
 
210
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
211
    root, ancestors, descendants = revision_graph(
 
212
        revision_a, revision_source)
 
213
    root_b, ancestors_b, descendants_b = revision_graph(
 
214
        revision_b, revision_source)
 
215
    if root != root_b:
 
216
        raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
 
217
    common = set()
 
218
    for node, node_anc in ancestors_b.iteritems():
 
219
        if node in ancestors:
 
220
            common.add(node)
 
221
        else:
 
222
            ancestors[node] = set()
 
223
        ancestors[node].update(node_anc)
 
224
    for node, node_dec in descendants_b.iteritems():
 
225
        if node not in descendants:
 
226
            descendants[node] = {}
 
227
        descendants[node].update(node_dec)
 
228
    return root, ancestors, descendants, common
 
229
 
 
230
 
 
231
def common_ancestor(revision_a, revision_b, revision_source, 
 
232
                    pb=DummyProgress()):
 
233
    if None in (revision_a, revision_b):
 
234
        return None
 
235
    # trivial optimisation
 
236
    if revision_a == revision_b:
 
237
        return revision_a
 
238
    try:
 
239
        try:
 
240
            pb.update('Picking ancestor', 1, 3)
 
241
            graph = revision_source.get_revision_graph_with_ghosts(
 
242
                [revision_a, revision_b])
 
243
            # convert to a NULL_REVISION based graph.
 
244
            ancestors = graph.get_ancestors()
 
245
            descendants = graph.get_descendants()
 
246
            common = set(graph.get_ancestry(revision_a)).intersection(
 
247
                     set(graph.get_ancestry(revision_b)))
 
248
            descendants[NULL_REVISION] = {}
 
249
            ancestors[NULL_REVISION] = []
 
250
            for root in graph.roots:
 
251
                descendants[NULL_REVISION][root] = 1
 
252
                ancestors[root].append(NULL_REVISION)
 
253
            if len(graph.roots) == 0:
 
254
                # no reachable roots - not handled yet.
 
255
                raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
256
            root = NULL_REVISION
 
257
            common.add(NULL_REVISION)
 
258
        except bzrlib.errors.NoCommonRoot:
 
259
            raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
260
            
 
261
        pb.update('Picking ancestor', 2, 3)
 
262
        distances = node_distances (descendants, ancestors, root)
 
263
        pb.update('Picking ancestor', 3, 2)
 
264
        farthest = select_farthest(distances, common)
 
265
        if farthest is None or farthest == NULL_REVISION:
 
266
            raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
267
    finally:
 
268
        pb.clear()
 
269
    return farthest
 
270
 
 
271
 
 
272
class MultipleRevisionSources(object):
 
273
    """Proxy that looks in multiple branches for revisions."""
 
274
    def __init__(self, *args):
 
275
        object.__init__(self)
 
276
        assert len(args) != 0
 
277
        self._revision_sources = args
 
278
 
 
279
    def revision_parents(self, revision_id):
 
280
        for source in self._revision_sources:
 
281
            try:
 
282
                return source.revision_parents(revision_id)
 
283
            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
 
284
                pass
 
285
        raise e
 
286
 
 
287
    def get_revision(self, revision_id):
 
288
        for source in self._revision_sources:
 
289
            try:
 
290
                return source.get_revision(revision_id)
 
291
            except bzrlib.errors.NoSuchRevision, e:
 
292
                pass
 
293
        raise e
 
294
 
 
295
    def get_revision_graph(self, revision_id):
 
296
        # we could probe incrementally until the pending
 
297
        # ghosts list stop growing, but its cheaper for now
 
298
        # to just ask for the complete graph for each repository.
 
299
        graphs = []
 
300
        for source in self._revision_sources:
 
301
            ghost_graph = source.get_revision_graph_with_ghosts()
 
302
            graphs.append(ghost_graph)
 
303
        absent = 0
 
304
        for graph in graphs:
 
305
            if not revision_id in graph.get_ancestors():
 
306
                absent += 1
 
307
        if absent == len(graphs):
 
308
            raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
 
309
 
 
310
        # combine the graphs
 
311
        result = {}
 
312
        pending = set([revision_id])
 
313
        def find_parents(node_id):
 
314
            """find the parents for node_id."""
 
315
            for graph in graphs:
 
316
                ancestors = graph.get_ancestors()
 
317
                try:
 
318
                    return ancestors[node_id]
 
319
                except KeyError:
 
320
                    pass
 
321
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
322
        while len(pending):
 
323
            # all the graphs should have identical parent lists
 
324
            node_id = pending.pop()
 
325
            try:
 
326
                result[node_id] = find_parents(node_id)
 
327
                for parent_node in result[node_id]:
 
328
                    if not parent_node in result:
 
329
                        pending.add(parent_node)
 
330
            except errors.NoSuchRevision:
 
331
                # ghost, ignore it.
 
332
                pass
 
333
        return result
 
334
 
 
335
    def get_revision_graph_with_ghosts(self, revision_ids):
 
336
        # query all the sources for their entire graphs 
 
337
        # and then build a combined graph for just
 
338
        # revision_ids.
 
339
        graphs = []
 
340
        for source in self._revision_sources:
 
341
            ghost_graph = source.get_revision_graph_with_ghosts()
 
342
            graphs.append(ghost_graph.get_ancestors())
 
343
        for revision_id in revision_ids:
 
344
            absent = 0
 
345
            for graph in graphs:
 
346
                    if not revision_id in graph:
 
347
                        absent += 1
 
348
            if absent == len(graphs):
 
349
                raise errors.NoSuchRevision(self._revision_sources[0],
 
350
                                            revision_id)
 
351
 
 
352
        # combine the graphs
 
353
        result = Graph()
 
354
        pending = set(revision_ids)
 
355
        done = set()
 
356
        def find_parents(node_id):
 
357
            """find the parents for node_id."""
 
358
            for graph in graphs:
 
359
                try:
 
360
                    return graph[node_id]
 
361
                except KeyError:
 
362
                    pass
 
363
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
364
        while len(pending):
 
365
            # all the graphs should have identical parent lists
 
366
            node_id = pending.pop()
 
367
            try:
 
368
                parents = find_parents(node_id)
 
369
                for parent_node in parents:
 
370
                    # queued or done? 
 
371
                    if (parent_node not in pending and
 
372
                        parent_node not in done):
 
373
                        # no, queue
 
374
                        pending.add(parent_node)
 
375
                result.add_node(node_id, parents)
 
376
                done.add(node_id)
 
377
            except errors.NoSuchRevision:
 
378
                # ghost
 
379
                result.add_ghost(node_id)
 
380
                continue
 
381
        return result
 
382
 
 
383
    def lock_read(self):
 
384
        for source in self._revision_sources:
 
385
            source.lock_read()
 
386
 
 
387
    def unlock(self):
 
388
        for source in self._revision_sources:
 
389
            source.unlock()
 
390
 
 
391
 
 
392
def get_intervening_revisions(ancestor_id, rev_id, rev_source, 
 
393
                              revision_history=None):
 
394
    """Find the longest line of descent from maybe_ancestor to revision.
 
395
    Revision history is followed where possible.
 
396
 
 
397
    If ancestor_id == rev_id, list will be empty.
 
398
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
399
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
400
    """
 
401
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
402
    if len(descendants) == 0:
 
403
        raise NoSuchRevision(rev_source, rev_id)
 
404
    if ancestor_id not in descendants:
 
405
        rev_source.get_revision(ancestor_id)
 
406
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
407
    root_descendants = all_descendants(descendants, ancestor_id)
 
408
    root_descendants.add(ancestor_id)
 
409
    if rev_id not in root_descendants:
 
410
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
411
    distances = node_distances(descendants, ancestors, ancestor_id,
 
412
                               root_descendants=root_descendants)
 
413
 
 
414
    def best_ancestor(rev_id):
 
415
        best = None
 
416
        for anc_id in ancestors[rev_id]:
 
417
            try:
 
418
                distance = distances[anc_id]
 
419
            except KeyError:
 
420
                continue
 
421
            if revision_history is not None and anc_id in revision_history:
 
422
                return anc_id
 
423
            elif best is None or distance > best[1]:
 
424
                best = (anc_id, distance)
 
425
        return best[0]
 
426
 
 
427
    next = rev_id
 
428
    path = []
 
429
    while next != ancestor_id:
 
430
        path.append(next)
 
431
        next = best_ancestor(next)
 
432
    path.reverse()
 
433
    return path