← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Alexander Belchenko
  • Date: 2006-07-30 16:43:12 UTC
  • mto: (1711.2.111 jam-integration)
  • mto: This revision was merged to the branch mainline in revision 1906.
  • Revision ID: bialix@ukr.net-20060730164312-b025fd3ff0cee59e
rename  gpl.txt => COPYING.txt

Show diffs side-by-side

added added

removed removed

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