← 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-10-14 08:51:07 UTC
  • mto: (2080.1.1 jam-integration)
  • mto: This revision was merged to the branch mainline in revision 2081.
  • Revision ID: bialix@ukr.net-20061014085107-8dff865674eed30a
win32 installer: make short info page instead of full GPL license text

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