/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: Robert Collins
  • Date: 2006-03-05 11:48:54 UTC
  • mto: This revision was merged to the branch mainline in revision 1590.
  • Revision ID: robertc@robertcollins.net-20060305114854-d95dbe4adfee32e9
Make bound branch creation happen via 'checkout'

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
 
1
# (C) 2005 Canonical
 
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
import bzrlib.errors
 
21
from bzrlib.graph import node_distances, select_farthest, all_descendants
 
22
from bzrlib.osutils import contains_whitespace
 
23
from bzrlib.progress import DummyProgress
 
24
 
 
25
NULL_REVISION="null:"
 
26
 
 
27
class Revision(object):
 
28
    """Single revision on a branch.
 
29
 
 
30
    Revisions may know their revision_hash, but only once they've been
 
31
    written out.  This is not stored because you cannot write the hash
 
32
    into the file it describes.
 
33
 
 
34
    After bzr 0.0.5 revisions are allowed to have multiple parents.
 
35
 
 
36
    parent_ids
 
37
        List of parent revision_ids
 
38
 
 
39
    properties
 
40
        Dictionary of revision properties.  These are attached to the
 
41
        revision as extra metadata.  The name must be a single 
 
42
        word; the value can be an arbitrary string.
 
43
    """
 
44
    
 
45
    def __init__(self, revision_id, properties=None, **args):
 
46
        self.revision_id = revision_id
 
47
        self.properties = properties or {}
 
48
        self._check_properties()
 
49
        self.parent_ids = []
 
50
        self.parent_sha1s = []
 
51
        self.__dict__.update(args)
 
52
 
 
53
    def __repr__(self):
 
54
        return "<Revision id %s>" % self.revision_id
 
55
 
 
56
    def __eq__(self, other):
 
57
        if not isinstance(other, Revision):
 
58
            return False
 
59
        # FIXME: rbc 20050930 parent_ids are not being compared
 
60
        return (
 
61
                self.inventory_sha1 == other.inventory_sha1
 
62
                and self.revision_id == other.revision_id
 
63
                and self.timestamp == other.timestamp
 
64
                and self.message == other.message
 
65
                and self.timezone == other.timezone
 
66
                and self.committer == other.committer
 
67
                and self.properties == other.properties)
 
68
 
 
69
    def __ne__(self, other):
 
70
        return not self.__eq__(other)
 
71
 
 
72
    def _check_properties(self):
 
73
        """Verify that all revision properties are OK.
 
74
        """
 
75
        for name, value in self.properties.iteritems():
 
76
            if not isinstance(name, basestring) or contains_whitespace(name):
 
77
                raise ValueError("invalid property name %r" % name)
 
78
            if not isinstance(value, basestring):
 
79
                raise ValueError("invalid property value %r for %r" % 
 
80
                                 (name, value))
 
81
 
 
82
    def get_history(self, repository):
 
83
        """Return the canonical line-of-history for this revision.
 
84
 
 
85
        If ghosts are present this may differ in result from a ghost-free
 
86
        repository.
 
87
        """
 
88
        current_revision = self
 
89
        reversed_result = []
 
90
        while current_revision is not None:
 
91
            reversed_result.append(current_revision.revision_id)
 
92
            if not len (current_revision.parent_ids):
 
93
                reversed_result.append(None)
 
94
                current_revision = None
 
95
            else:
 
96
                next_revision_id = current_revision.parent_ids[0]
 
97
                current_revision = repository.get_revision(next_revision_id)
 
98
        reversed_result.reverse()
 
99
        return reversed_result
 
100
 
 
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)
 
112
 
 
113
 
 
114
def iter_ancestors(revision_id, revision_source, only_present=False):
 
115
    ancestors = (revision_id,)
 
116
    distance = 0
 
117
    while len(ancestors) > 0:
 
118
        new_ancestors = []
 
119
        for ancestor in ancestors:
 
120
            if not only_present:
 
121
                yield ancestor, distance
 
122
            try:
 
123
                revision = revision_source.get_revision(ancestor)
 
124
            except bzrlib.errors.NoSuchRevision, e:
 
125
                if e.revision == revision_id:
 
126
                    raise 
 
127
                else:
 
128
                    continue
 
129
            if only_present:
 
130
                yield ancestor, distance
 
131
            new_ancestors.extend(revision.parent_ids)
 
132
        ancestors = new_ancestors
 
133
        distance += 1
 
134
 
 
135
 
 
136
def find_present_ancestors(revision_id, revision_source):
 
137
    """Return the ancestors of a revision present in a branch.
 
138
 
 
139
    It's possible that a branch won't have the complete ancestry of
 
140
    one of its revisions.  
 
141
 
 
142
    """
 
143
    found_ancestors = {}
 
144
    anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
 
145
                         only_present=True))
 
146
    for anc_order, (anc_id, anc_distance) in anc_iter:
 
147
        if not found_ancestors.has_key(anc_id):
 
148
            found_ancestors[anc_id] = (anc_order, anc_distance)
 
149
    return found_ancestors
 
150
    
 
151
 
 
152
def __get_closest(intersection):
 
153
    intersection.sort()
 
154
    matches = [] 
 
155
    for entry in intersection:
 
156
        if entry[0] == intersection[0][0]:
 
157
            matches.append(entry[2])
 
158
    return matches
 
159
 
 
160
 
 
161
def revision_graph(revision, revision_source):
 
162
    """Produce a graph of the ancestry of the specified revision.
 
163
    Return root, ancestors map, descendants map
 
164
 
 
165
    TODO: Produce graphs with the NULL revision as root, so that we can find
 
166
    a common even when trees are not branches don't represent a single line
 
167
    of descent.
 
168
    RBC: 20051024: note that when we have two partial histories, this may not
 
169
         be possible. But if we are willing to pretend :)... sure.
 
170
    """
 
171
    revision_source.lock_read()
 
172
    try:
 
173
        return _revision_graph(revision, revision_source)
 
174
    finally:
 
175
        revision_source.unlock()
 
176
 
 
177
def _revision_graph(revision, revision_source):
 
178
    """See revision_graph."""
 
179
    ancestors = {}
 
180
    descendants = {}
 
181
    lines = [revision]
 
182
    root = None
 
183
    descendants[revision] = {}
 
184
    while len(lines) > 0:
 
185
        new_lines = set()
 
186
        for line in lines:
 
187
            if line == NULL_REVISION:
 
188
                parents = []
 
189
                root = NULL_REVISION
 
190
            else:
 
191
                try:
 
192
                    rev = revision_source.get_revision(line)
 
193
                    parents = list(rev.parent_ids)
 
194
                    if len(parents) == 0:
 
195
                        parents = [NULL_REVISION]
 
196
                except bzrlib.errors.NoSuchRevision:
 
197
                    if line == revision:
 
198
                        raise
 
199
                    parents = None
 
200
            if parents is not None:
 
201
                for parent in parents:
 
202
                    if parent not in ancestors:
 
203
                        new_lines.add(parent)
 
204
                    if parent not in descendants:
 
205
                        descendants[parent] = {}
 
206
                    descendants[parent][line] = 1
 
207
            if parents is not None:
 
208
                ancestors[line] = set(parents)
 
209
        lines = new_lines
 
210
    if root is None:
 
211
        # The history for revision becomes inaccessible without
 
212
        # actually hitting a no-parents revision. This then
 
213
        # makes these asserts below trigger. So, if root is None
 
214
        # determine the actual root by walking the accessible tree
 
215
        # and then stash NULL_REVISION at the end.
 
216
        root = NULL_REVISION
 
217
        descendants[root] = {}
 
218
        # for every revision, check we can access at least
 
219
        # one parent, if we cant, add NULL_REVISION and
 
220
        # a link
 
221
        for rev in ancestors:
 
222
            if len(ancestors[rev]) == 0:
 
223
                raise RuntimeError('unreachable code ?!')
 
224
            ok = False
 
225
            for parent in ancestors[rev]:
 
226
                if parent in ancestors:
 
227
                    ok = True
 
228
            if ok:
 
229
                continue
 
230
            descendants[root][rev] = 1
 
231
            ancestors[rev].add(root)
 
232
        ancestors[root] = set()
 
233
    assert root not in descendants[root]
 
234
    assert root not in ancestors[root]
 
235
    return root, ancestors, descendants
 
236
 
 
237
 
 
238
def combined_graph(revision_a, revision_b, revision_source):
 
239
    """Produce a combined ancestry graph.
 
240
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
241
    root, ancestors, descendants = revision_graph(revision_a, revision_source)
 
242
    root_b, ancestors_b, descendants_b = revision_graph(revision_b, 
 
243
                                                        revision_source)
 
244
    if root != root_b:
 
245
        raise bzrlib.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
def common_ancestor(revision_a, revision_b, revision_source, 
 
261
                    pb=DummyProgress()):
 
262
    if None in (revision_a, revision_b):
 
263
        return None
 
264
    try:
 
265
        try:
 
266
            pb.update('Picking ancestor', 1, 3)
 
267
            root, ancestors, descendants, common = \
 
268
                combined_graph(revision_a, revision_b, revision_source)
 
269
        except bzrlib.errors.NoCommonRoot:
 
270
            raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
271
            
 
272
        pb.update('Picking ancestor', 2, 3)
 
273
        distances = node_distances (descendants, ancestors, root)
 
274
        pb.update('Picking ancestor', 3, 2)
 
275
        farthest = select_farthest(distances, common)
 
276
        if farthest is None or farthest == NULL_REVISION:
 
277
            raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
278
    finally:
 
279
        pb.clear()
 
280
    return farthest
 
281
 
 
282
 
 
283
class MultipleRevisionSources(object):
 
284
    """Proxy that looks in multiple branches for revisions."""
 
285
    def __init__(self, *args):
 
286
        object.__init__(self)
 
287
        assert len(args) != 0
 
288
        self._revision_sources = args
 
289
 
 
290
    def get_revision(self, revision_id):
 
291
        for source in self._revision_sources:
 
292
            try:
 
293
                return source.get_revision(revision_id)
 
294
            except bzrlib.errors.NoSuchRevision, e:
 
295
                pass
 
296
        raise e
 
297
 
 
298
    def lock_read(self):
 
299
        for source in self._revision_sources:
 
300
            source.lock_read()
 
301
 
 
302
    def unlock(self):
 
303
        for source in self._revision_sources:
 
304
            source.unlock()
 
305
 
 
306
def get_intervening_revisions(ancestor_id, rev_id, rev_source, 
 
307
                              revision_history=None):
 
308
    """Find the longest line of descent from maybe_ancestor to revision.
 
309
    Revision history is followed where possible.
 
310
 
 
311
    If ancestor_id == rev_id, list will be empty.
 
312
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
313
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
314
    """
 
315
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
316
    if len(descendants) == 0:
 
317
        raise NoSuchRevision(rev_source, rev_id)
 
318
    if ancestor_id not in descendants:
 
319
        rev_source.get_revision(ancestor_id)
 
320
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
321
    root_descendants = all_descendants(descendants, ancestor_id)
 
322
    root_descendants.add(ancestor_id)
 
323
    if rev_id not in root_descendants:
 
324
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
325
    distances = node_distances(descendants, ancestors, ancestor_id,
 
326
                               root_descendants=root_descendants)
 
327
 
 
328
    def best_ancestor(rev_id):
 
329
        best = None
 
330
        for anc_id in ancestors[rev_id]:
 
331
            try:
 
332
                distance = distances[anc_id]
 
333
            except KeyError:
 
334
                continue
 
335
            if revision_history is not None and anc_id in revision_history:
 
336
                return anc_id
 
337
            elif best is None or distance > best[1]:
 
338
                best = (anc_id, distance)
 
339
        return best[0]
 
340
 
 
341
    next = rev_id
 
342
    path = []
 
343
    while next != ancestor_id:
 
344
        path.append(next)
 
345
        next = best_ancestor(next)
 
346
    path.reverse()
 
347
    return path