/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: John Arbash Meinel
  • Date: 2008-03-20 17:14:01 UTC
  • mto: (3326.1.1 ianc-integration)
  • mto: This revision was merged to the branch mainline in revision 3327.
  • Revision ID: john@arbash-meinel.com-20080320171401-uwkidro3gqqvy7ek
Only show pending merges when not given a list of specific files.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
 
1
# Copyright (C) 2005, 2006 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
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: 
 
18
# perhaps show them in log -v and allow them as options to the commit command.
 
19
 
 
20
 
 
21
from bzrlib import (
 
22
    errors,
 
23
    symbol_versioning,
 
24
    )
 
25
from bzrlib.deprecated_graph import (
 
26
    all_descendants,
 
27
    Graph,
 
28
    node_distances,
 
29
    select_farthest,
 
30
    )
 
31
from bzrlib.osutils import contains_whitespace
 
32
from bzrlib.progress import DummyProgress
 
33
from bzrlib.symbol_versioning import (deprecated_function,
 
34
        )
 
35
 
 
36
NULL_REVISION="null:"
 
37
CURRENT_REVISION="current:"
 
38
 
 
39
 
 
40
class Revision(object):
 
41
    """Single revision on a branch.
 
42
 
 
43
    Revisions may know their revision_hash, but only once they've been
 
44
    written out.  This is not stored because you cannot write the hash
 
45
    into the file it describes.
 
46
 
 
47
    After bzr 0.0.5 revisions are allowed to have multiple parents.
 
48
 
 
49
    parent_ids
 
50
        List of parent revision_ids
 
51
 
 
52
    properties
 
53
        Dictionary of revision properties.  These are attached to the
 
54
        revision as extra metadata.  The name must be a single 
 
55
        word; the value can be an arbitrary string.
 
56
    """
 
57
    
 
58
    def __init__(self, revision_id, properties=None, **args):
 
59
        self.revision_id = revision_id
 
60
        self.properties = properties or {}
 
61
        self._check_properties()
 
62
        self.parent_ids = []
 
63
        self.parent_sha1s = []
 
64
        """Not used anymore - legacy from for 4."""
 
65
        self.__dict__.update(args)
 
66
 
 
67
    def __repr__(self):
 
68
        return "<Revision id %s>" % self.revision_id
 
69
 
 
70
    def __eq__(self, other):
 
71
        if not isinstance(other, Revision):
 
72
            return False
 
73
        # FIXME: rbc 20050930 parent_ids are not being compared
 
74
        return (
 
75
                self.inventory_sha1 == other.inventory_sha1
 
76
                and self.revision_id == other.revision_id
 
77
                and self.timestamp == other.timestamp
 
78
                and self.message == other.message
 
79
                and self.timezone == other.timezone
 
80
                and self.committer == other.committer
 
81
                and self.properties == other.properties)
 
82
 
 
83
    def __ne__(self, other):
 
84
        return not self.__eq__(other)
 
85
 
 
86
    def _check_properties(self):
 
87
        """Verify that all revision properties are OK."""
 
88
        for name, value in self.properties.iteritems():
 
89
            if not isinstance(name, basestring) or contains_whitespace(name):
 
90
                raise ValueError("invalid property name %r" % name)
 
91
            if not isinstance(value, basestring):
 
92
                raise ValueError("invalid property value %r for %r" % 
 
93
                                 (name, value))
 
94
 
 
95
    def get_history(self, repository):
 
96
        """Return the canonical line-of-history for this revision.
 
97
 
 
98
        If ghosts are present this may differ in result from a ghost-free
 
99
        repository.
 
100
        """
 
101
        current_revision = self
 
102
        reversed_result = []
 
103
        while current_revision is not None:
 
104
            reversed_result.append(current_revision.revision_id)
 
105
            if not len (current_revision.parent_ids):
 
106
                reversed_result.append(None)
 
107
                current_revision = None
 
108
            else:
 
109
                next_revision_id = current_revision.parent_ids[0]
 
110
                current_revision = repository.get_revision(next_revision_id)
 
111
        reversed_result.reverse()
 
112
        return reversed_result
 
113
 
 
114
    def get_summary(self):
 
115
        """Get the first line of the log message for this revision.
 
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)
 
142
 
 
143
 
 
144
def iter_ancestors(revision_id, revision_source, only_present=False):
 
145
    ancestors = (revision_id,)
 
146
    distance = 0
 
147
    while len(ancestors) > 0:
 
148
        new_ancestors = []
 
149
        for ancestor in ancestors:
 
150
            if not only_present:
 
151
                yield ancestor, distance
 
152
            try:
 
153
                revision = revision_source.get_revision(ancestor)
 
154
            except errors.NoSuchRevision, e:
 
155
                if e.revision == revision_id:
 
156
                    raise 
 
157
                else:
 
158
                    continue
 
159
            if only_present:
 
160
                yield ancestor, distance
 
161
            new_ancestors.extend(revision.parent_ids)
 
162
        ancestors = new_ancestors
 
163
        distance += 1
 
164
 
 
165
 
 
166
def find_present_ancestors(revision_id, revision_source):
 
167
    """Return the ancestors of a revision present in a branch.
 
168
 
 
169
    It's possible that a branch won't have the complete ancestry of
 
170
    one of its revisions.  
 
171
 
 
172
    """
 
173
    found_ancestors = {}
 
174
    anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
 
175
                         only_present=True))
 
176
    for anc_order, (anc_id, anc_distance) in anc_iter:
 
177
        if anc_id not in found_ancestors:
 
178
            found_ancestors[anc_id] = (anc_order, anc_distance)
 
179
    return found_ancestors
 
180
    
 
181
 
 
182
def __get_closest(intersection):
 
183
    intersection.sort()
 
184
    matches = [] 
 
185
    for entry in intersection:
 
186
        if entry[0] == intersection[0][0]:
 
187
            matches.append(entry[2])
 
188
    return matches
 
189
 
 
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
 
 
445
def is_reserved_id(revision_id):
 
446
    """Determine whether a revision id is reserved
 
447
 
 
448
    :return: True if the revision is is reserved, False otherwise
 
449
    """
 
450
    return isinstance(revision_id, basestring) and revision_id.endswith(':')
 
451
 
 
452
 
 
453
def check_not_reserved_id(revision_id):
 
454
    """Raise ReservedId if the supplied revision_id is reserved"""
 
455
    if is_reserved_id(revision_id):
 
456
        raise errors.ReservedId(revision_id)
 
457
 
 
458
 
 
459
def ensure_null(revision_id):
 
460
    """Ensure only NULL_REVISION is used to represent the null revision"""
 
461
    if revision_id is None:
 
462
        symbol_versioning.warn('NULL_REVISION should be used for the null'
 
463
            ' revision instead of None, as of bzr 0.91.',
 
464
            DeprecationWarning, stacklevel=2)
 
465
        return NULL_REVISION
 
466
    else:
 
467
        return revision_id
 
468
 
 
469
 
 
470
def is_null(revision_id):
 
471
    if revision_id is None:
 
472
        symbol_versioning.warn('NULL_REVISION should be used for the null'
 
473
            ' revision instead of None, as of bzr 0.90.',
 
474
            DeprecationWarning, stacklevel=2)
 
475
    return revision_id in (None, NULL_REVISION)