← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Robert Collins
  • Date: 2006-02-25 00:54:16 UTC
  • mto: (1587.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 1588.
  • Revision ID: robertc@robertcollins.net-20060225005416-e74996bec38de816
UI tweaks to reconcile - show progress for inventory backup.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
1
 
# Copyright (C) 2005, 2006 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
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
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
 
 
21
 
from bzrlib.lazy_import import lazy_import
22
 
lazy_import(globals(), """
23
 
from bzrlib import deprecated_graph
24
 
""")
25
 
from bzrlib import (
26
 
    errors,
27
 
    symbol_versioning,
28
 
    )
 
20
import bzrlib.errors
 
21
from bzrlib.graph import node_distances, select_farthest, all_descendants
29
22
from bzrlib.osutils import contains_whitespace
30
23
from bzrlib.progress import DummyProgress
31
24
 
32
25
NULL_REVISION="null:"
33
 
CURRENT_REVISION="current:"
34
 
 
35
26
 
36
27
class Revision(object):
37
28
    """Single revision on a branch.
57
48
        self._check_properties()
58
49
        self.parent_ids = []
59
50
        self.parent_sha1s = []
60
 
        """Not used anymore - legacy from for 4."""
61
51
        self.__dict__.update(args)
62
52
 
63
53
    def __repr__(self):
80
70
        return not self.__eq__(other)
81
71
 
82
72
    def _check_properties(self):
83
 
        """Verify that all revision properties are OK."""
 
73
        """Verify that all revision properties are OK.
 
74
        """
84
75
        for name, value in self.properties.iteritems():
85
76
            if not isinstance(name, basestring) or contains_whitespace(name):
86
77
                raise ValueError("invalid property name %r" % name)
107
98
        reversed_result.reverse()
108
99
        return reversed_result
109
100
 
110
 
    def get_summary(self):
111
 
        """Get the first line of the log message for this revision.
112
 
        """
113
 
        return self.message.lstrip().split('\n', 1)[0]
114
 
 
115
 
    def get_apparent_author(self):
116
 
        """Return the apparent author of this revision.
117
 
 
118
 
        If the revision properties contain the author name,
119
 
        return it. Otherwise return the committer name.
120
 
        """
121
 
        return self.properties.get('author', self.committer)
 
101
 
 
102
def is_ancestor(revision_id, candidate_id, branch):
 
103
    """Return true if candidate_id is an ancestor of revision_id.
 
104
 
 
105
    A false negative will be returned if any intermediate descendent of
 
106
    candidate_id is not present in any of the revision_sources.
 
107
    
 
108
    revisions_source is an object supporting a get_revision operation that
 
109
    behaves like Branch's.
 
110
    """
 
111
    return candidate_id in branch.repository.get_ancestry(revision_id)
122
112
 
123
113
 
124
114
def iter_ancestors(revision_id, revision_source, only_present=False):
131
121
                yield ancestor, distance
132
122
            try:
133
123
                revision = revision_source.get_revision(ancestor)
134
 
            except errors.NoSuchRevision, e:
 
124
            except bzrlib.errors.NoSuchRevision, e:
135
125
                if e.revision == revision_id:
136
126
                    raise 
137
127
                else:
154
144
    anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
155
145
                         only_present=True))
156
146
    for anc_order, (anc_id, anc_distance) in anc_iter:
157
 
        if anc_id not in found_ancestors:
 
147
        if not found_ancestors.has_key(anc_id):
158
148
            found_ancestors[anc_id] = (anc_order, anc_distance)
159
149
    return found_ancestors
160
150
    
168
158
    return matches
169
159
 
170
160
 
171
 
def is_reserved_id(revision_id):
172
 
    """Determine whether a revision id is reserved
173
 
 
174
 
    :return: True if the revision is is reserved, False otherwise
 
161
def old_common_ancestor(revision_a, revision_b, revision_source):
 
162
    """Find the ancestor common to both revisions that is closest to both.
175
163
    """
176
 
    return isinstance(revision_id, basestring) and revision_id.endswith(':')
177
 
 
178
 
 
179
 
def check_not_reserved_id(revision_id):
180
 
    """Raise ReservedId if the supplied revision_id is reserved"""
181
 
    if is_reserved_id(revision_id):
182
 
        raise errors.ReservedId(revision_id)
183
 
 
184
 
 
185
 
def ensure_null(revision_id):
186
 
    """Ensure only NULL_REVISION is used to represent the null revision"""
187
 
    if revision_id is None:
188
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
189
 
            ' revision instead of None, as of bzr 0.91.',
190
 
            DeprecationWarning, stacklevel=2)
191
 
        return NULL_REVISION
 
164
    from bzrlib.trace import mutter
 
165
    a_ancestors = find_present_ancestors(revision_a, revision_source)
 
166
    b_ancestors = find_present_ancestors(revision_b, revision_source)
 
167
    a_intersection = []
 
168
    b_intersection = []
 
169
    # a_order is used as a tie-breaker when two equally-good bases are found
 
170
    for revision, (a_order, a_distance) in a_ancestors.iteritems():
 
171
        if b_ancestors.has_key(revision):
 
172
            a_intersection.append((a_distance, a_order, revision))
 
173
            b_intersection.append((b_ancestors[revision][1], a_order, revision))
 
174
    mutter("a intersection: %r", a_intersection)
 
175
    mutter("b intersection: %r", b_intersection)
 
176
 
 
177
    a_closest = __get_closest(a_intersection)
 
178
    if len(a_closest) == 0:
 
179
        return None
 
180
    b_closest = __get_closest(b_intersection)
 
181
    assert len(b_closest) != 0
 
182
    mutter ("a_closest %r", a_closest)
 
183
    mutter ("b_closest %r", b_closest)
 
184
    if a_closest[0] in b_closest:
 
185
        return a_closest[0]
 
186
    elif b_closest[0] in a_closest:
 
187
        return b_closest[0]
192
188
    else:
193
 
        return revision_id
194
 
 
195
 
 
196
 
def is_null(revision_id):
197
 
    if revision_id is None:
198
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
199
 
            ' revision instead of None, as of bzr 0.90.',
200
 
            DeprecationWarning, stacklevel=2)
201
 
    return revision_id in (None, NULL_REVISION)
 
189
        raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
 
190
    return a_closest[0]
 
191
 
 
192
def revision_graph(revision, revision_source):
 
193
    """Produce a graph of the ancestry of the specified revision.
 
194
    Return root, ancestors map, descendants map
 
195
 
 
196
    TODO: Produce graphs with the NULL revision as root, so that we can find
 
197
    a common even when trees are not branches don't represent a single line
 
198
    of descent.
 
199
    RBC: 20051024: note that when we have two partial histories, this may not
 
200
         be possible. But if we are willing to pretend :)... sure.
 
201
    """
 
202
    ancestors = {}
 
203
    descendants = {}
 
204
    lines = [revision]
 
205
    root = None
 
206
    descendants[revision] = {}
 
207
    while len(lines) > 0:
 
208
        new_lines = set()
 
209
        for line in lines:
 
210
            if line == NULL_REVISION:
 
211
                parents = []
 
212
                root = NULL_REVISION
 
213
            else:
 
214
                try:
 
215
                    rev = revision_source.get_revision(line)
 
216
                    parents = list(rev.parent_ids)
 
217
                    if len(parents) == 0:
 
218
                        parents = [NULL_REVISION]
 
219
                except bzrlib.errors.NoSuchRevision:
 
220
                    if line == revision:
 
221
                        raise
 
222
                    parents = None
 
223
            if parents is not None:
 
224
                for parent in parents:
 
225
                    if parent not in ancestors:
 
226
                        new_lines.add(parent)
 
227
                    if parent not in descendants:
 
228
                        descendants[parent] = {}
 
229
                    descendants[parent][line] = 1
 
230
            if parents is not None:
 
231
                ancestors[line] = set(parents)
 
232
        lines = new_lines
 
233
    if root is None:
 
234
        # The history for revision becomes inaccessible without
 
235
        # actually hitting a no-parents revision. This then
 
236
        # makes these asserts below trigger. So, if root is None
 
237
        # determine the actual root by walking the accessible tree
 
238
        # and then stash NULL_REVISION at the end.
 
239
        root = NULL_REVISION
 
240
        descendants[root] = {}
 
241
        # for every revision, check we can access at least
 
242
        # one parent, if we cant, add NULL_REVISION and
 
243
        # a link
 
244
        for rev in ancestors:
 
245
            if len(ancestors[rev]) == 0:
 
246
                raise RuntimeError('unreachable code ?!')
 
247
            ok = False
 
248
            for parent in ancestors[rev]:
 
249
                if parent in ancestors:
 
250
                    ok = True
 
251
            if ok:
 
252
                continue
 
253
            descendants[root][rev] = 1
 
254
            ancestors[rev].add(root)
 
255
        ancestors[root] = set()
 
256
    assert root not in descendants[root]
 
257
    assert root not in ancestors[root]
 
258
    return root, ancestors, descendants
 
259
 
 
260
 
 
261
def combined_graph(revision_a, revision_b, revision_source):
 
262
    """Produce a combined ancestry graph.
 
263
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
264
    root, ancestors, descendants = revision_graph(revision_a, revision_source)
 
265
    root_b, ancestors_b, descendants_b = revision_graph(revision_b, 
 
266
                                                        revision_source)
 
267
    if root != root_b:
 
268
        raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
 
269
    common = set()
 
270
    for node, node_anc in ancestors_b.iteritems():
 
271
        if node in ancestors:
 
272
            common.add(node)
 
273
        else:
 
274
            ancestors[node] = set()
 
275
        ancestors[node].update(node_anc)
 
276
    for node, node_dec in descendants_b.iteritems():
 
277
        if node not in descendants:
 
278
            descendants[node] = {}
 
279
        descendants[node].update(node_dec)
 
280
    return root, ancestors, descendants, common
 
281
 
 
282
 
 
283
def common_ancestor(revision_a, revision_b, revision_source, 
 
284
                    pb=DummyProgress()):
 
285
    try:
 
286
        try:
 
287
            pb.update('Picking ancestor', 1, 3)
 
288
            root, ancestors, descendants, common = \
 
289
                combined_graph(revision_a, revision_b, revision_source)
 
290
        except bzrlib.errors.NoCommonRoot:
 
291
            raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
292
            
 
293
        pb.update('Picking ancestor', 2, 3)
 
294
        distances = node_distances (descendants, ancestors, root)
 
295
        pb.update('Picking ancestor', 3, 2)
 
296
        farthest = select_farthest(distances, common)
 
297
        if farthest is None or farthest == NULL_REVISION:
 
298
            raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
299
    finally:
 
300
        pb.clear()
 
301
    return farthest
 
302
 
 
303
 
 
304
class MultipleRevisionSources(object):
 
305
    """Proxy that looks in multiple branches for revisions."""
 
306
    def __init__(self, *args):
 
307
        object.__init__(self)
 
308
        assert len(args) != 0
 
309
        self._revision_sources = args
 
310
 
 
311
    def get_revision(self, revision_id):
 
312
        for source in self._revision_sources:
 
313
            try:
 
314
                return source.get_revision(revision_id)
 
315
            except bzrlib.errors.NoSuchRevision, e:
 
316
                pass
 
317
        raise e
 
318
 
 
319
def get_intervening_revisions(ancestor_id, rev_id, rev_source, 
 
320
                              revision_history=None):
 
321
    """Find the longest line of descent from maybe_ancestor to revision.
 
322
    Revision history is followed where possible.
 
323
 
 
324
    If ancestor_id == rev_id, list will be empty.
 
325
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
326
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
327
    """
 
328
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
329
    if len(descendants) == 0:
 
330
        raise NoSuchRevision(rev_source, rev_id)
 
331
    if ancestor_id not in descendants:
 
332
        rev_source.get_revision(ancestor_id)
 
333
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
334
    root_descendants = all_descendants(descendants, ancestor_id)
 
335
    root_descendants.add(ancestor_id)
 
336
    if rev_id not in root_descendants:
 
337
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
338
    distances = node_distances(descendants, ancestors, ancestor_id,
 
339
                               root_descendants=root_descendants)
 
340
 
 
341
    def best_ancestor(rev_id):
 
342
        best = None
 
343
        for anc_id in ancestors[rev_id]:
 
344
            try:
 
345
                distance = distances[anc_id]
 
346
            except KeyError:
 
347
                continue
 
348
            if revision_history is not None and anc_id in revision_history:
 
349
                return anc_id
 
350
            elif best is None or distance > best[1]:
 
351
                best = (anc_id, distance)
 
352
        return best[0]
 
353
 
 
354
    next = rev_id
 
355
    path = []
 
356
    while next != ancestor_id:
 
357
        path.append(next)
 
358
        next = best_ancestor(next)
 
359
    path.reverse()
 
360
    return path