/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

and the tutorial patch came back, the very next day

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
 
 
18
import bzrlib.errors
 
19
from bzrlib.graph import farthest_nodes, node_distances, all_descendants
 
20
 
 
21
class RevisionReference(object):
 
22
    """
 
23
    Reference to a stored revision.
 
24
 
 
25
    Includes the revision_id and revision_sha1.
 
26
    """
 
27
    revision_id = None
 
28
    revision_sha1 = None
 
29
    def __init__(self, revision_id, revision_sha1=None):
 
30
        if revision_id == None \
 
31
           or isinstance(revision_id, basestring):
 
32
            self.revision_id = revision_id
 
33
        else:
 
34
            raise ValueError('bad revision_id %r' % revision_id)
 
35
 
 
36
        if revision_sha1 != None:
 
37
            if isinstance(revision_sha1, basestring) \
 
38
               and len(revision_sha1) == 40:
 
39
                self.revision_sha1 = revision_sha1
 
40
            else:
 
41
                raise ValueError('bad revision_sha1 %r' % revision_sha1)
 
42
                
 
43
 
 
44
 
 
45
class Revision(object):
 
46
    """Single revision on a branch.
 
47
 
 
48
    Revisions may know their revision_hash, but only once they've been
 
49
    written out.  This is not stored because you cannot write the hash
 
50
    into the file it describes.
 
51
 
 
52
    After bzr 0.0.5 revisions are allowed to have multiple parents.
 
53
 
 
54
    parents
 
55
        List of parent revisions, each is a RevisionReference.
 
56
    """
 
57
    inventory_id = None
 
58
    inventory_sha1 = None
 
59
    revision_id = None
 
60
    timestamp = None
 
61
    message = None
 
62
    timezone = None
 
63
    committer = None
 
64
    
 
65
    def __init__(self, **args):
 
66
        self.__dict__.update(args)
 
67
        self.parents = []
 
68
 
 
69
 
 
70
    def __repr__(self):
 
71
        return "<Revision id %s>" % self.revision_id
 
72
 
 
73
    def __eq__(self, other):
 
74
        if not isinstance(other, Revision):
 
75
            return False
 
76
        return (self.inventory_id == other.inventory_id
 
77
                and self.inventory_sha1 == other.inventory_sha1
 
78
                and self.revision_id == other.revision_id
 
79
                and self.timestamp == other.timestamp
 
80
                and self.message == other.message
 
81
                and self.timezone == other.timezone
 
82
                and self.committer == other.committer)
 
83
 
 
84
    def __ne__(self, other):
 
85
        return not self.__eq__(other)
 
86
 
 
87
        
 
88
 
 
89
REVISION_ID_RE = None
 
90
 
 
91
def validate_revision_id(rid):
 
92
    """Check rid is syntactically valid for a revision id."""
 
93
    global REVISION_ID_RE
 
94
    if not REVISION_ID_RE:
 
95
        import re
 
96
        REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
 
97
 
 
98
    if not REVISION_ID_RE.match(rid):
 
99
        raise ValueError("malformed revision-id %r" % rid)
 
100
 
 
101
def is_ancestor(revision_id, candidate_id, revision_source):
 
102
    """Return true if candidate_id is an ancestor of revision_id.
 
103
    A false negative will be returned if any intermediate descendent of
 
104
    candidate_id is not present in any of the revision_sources.
 
105
    
 
106
    revisions_source is an object supporting a get_revision operation that
 
107
    behaves like Branch's.
 
108
    """
 
109
 
 
110
    for ancestor_id, distance in iter_ancestors(revision_id, revision_source):
 
111
        if ancestor_id == candidate_id:
 
112
            return True
 
113
    return False
 
114
 
 
115
def iter_ancestors(revision_id, revision_source, only_present=False):
 
116
    ancestors = (revision_id,)
 
117
    distance = 0
 
118
    while len(ancestors) > 0:
 
119
        new_ancestors = []
 
120
        for ancestor in ancestors:
 
121
            if not only_present:
 
122
                yield ancestor, distance
 
123
            try:
 
124
                revision = revision_source.get_revision(ancestor)
 
125
            except bzrlib.errors.NoSuchRevision, e:
 
126
                if e.revision == revision_id:
 
127
                    raise 
 
128
                else:
 
129
                    continue
 
130
            if only_present:
 
131
                yield ancestor, distance
 
132
            new_ancestors.extend([p.revision_id for p in revision.parents])
 
133
        ancestors = new_ancestors
 
134
        distance += 1
 
135
 
 
136
 
 
137
def find_present_ancestors(revision_id, revision_source):
 
138
    """Return the ancestors of a revision present in a branch.
 
139
 
 
140
    It's possible that a branch won't have the complete ancestry of
 
141
    one of its revisions.  
 
142
 
 
143
    """
 
144
    found_ancestors = {}
 
145
    anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
 
146
                         only_present=True))
 
147
    for anc_order, (anc_id, anc_distance) in anc_iter:
 
148
        if not found_ancestors.has_key(anc_id):
 
149
            found_ancestors[anc_id] = (anc_order, anc_distance)
 
150
    return found_ancestors
 
151
    
 
152
 
 
153
def __get_closest(intersection):
 
154
    intersection.sort()
 
155
    matches = [] 
 
156
    for entry in intersection:
 
157
        if entry[0] == intersection[0][0]:
 
158
            matches.append(entry[2])
 
159
    return matches
 
160
 
 
161
 
 
162
def old_common_ancestor(revision_a, revision_b, revision_source):
 
163
    """Find the ancestor common to both revisions that is closest to both.
 
164
    """
 
165
    from bzrlib.trace import mutter
 
166
    a_ancestors = find_present_ancestors(revision_a, revision_source)
 
167
    b_ancestors = find_present_ancestors(revision_b, revision_source)
 
168
    a_intersection = []
 
169
    b_intersection = []
 
170
    # a_order is used as a tie-breaker when two equally-good bases are found
 
171
    for revision, (a_order, a_distance) in a_ancestors.iteritems():
 
172
        if b_ancestors.has_key(revision):
 
173
            a_intersection.append((a_distance, a_order, revision))
 
174
            b_intersection.append((b_ancestors[revision][1], a_order, revision))
 
175
    mutter("a intersection: %r" % a_intersection)
 
176
    mutter("b intersection: %r" % b_intersection)
 
177
 
 
178
    a_closest = __get_closest(a_intersection)
 
179
    if len(a_closest) == 0:
 
180
        return None
 
181
    b_closest = __get_closest(b_intersection)
 
182
    assert len(b_closest) != 0
 
183
    mutter ("a_closest %r" % a_closest)
 
184
    mutter ("b_closest %r" % b_closest)
 
185
    if a_closest[0] in b_closest:
 
186
        return a_closest[0]
 
187
    elif b_closest[0] in a_closest:
 
188
        return b_closest[0]
 
189
    else:
 
190
        raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
 
191
    return a_closest[0]
 
192
 
 
193
def revision_graph(revision, revision_source):
 
194
    """Produce a graph of the ancestry of the specified revision.
 
195
    Return root, ancestors map, descendants map
 
196
 
 
197
    TODO: Produce graphs with the NULL revision as root, so that we can find
 
198
    a common even when trees are not branches don't represent a single line
 
199
    of descent.
 
200
    """
 
201
    ancestors = {}
 
202
    descendants = {}
 
203
    lines = [revision]
 
204
    root = None
 
205
    descendants[revision] = {}
 
206
    while len(lines) > 0:
 
207
        new_lines = set()
 
208
        for line in lines:
 
209
            try:
 
210
                rev = revision_source.get_revision(line)
 
211
                parents = [p.revision_id for p in rev.parents]
 
212
                if len(parents) == 0:
 
213
                    root = line
 
214
            except bzrlib.errors.NoSuchRevision:
 
215
                if line == revision:
 
216
                    raise
 
217
                parents = None
 
218
            if parents is not None:
 
219
                for parent in parents:
 
220
                    if parent not in ancestors:
 
221
                        new_lines.add(parent)
 
222
                    if parent not in descendants:
 
223
                        descendants[parent] = {}
 
224
                    descendants[parent][line] = 1
 
225
            if parents is not None:
 
226
                ancestors[line] = set(parents)
 
227
        lines = new_lines
 
228
    assert root not in descendants[root]
 
229
    assert root not in ancestors[root]
 
230
    return root, ancestors, descendants
 
231
 
 
232
def combined_graph(revision_a, revision_b, revision_source):
 
233
    """Produce a combined ancestry graph.
 
234
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
235
    root, ancestors, descendants = revision_graph(revision_a, revision_source)
 
236
    root_b, ancestors_b, descendants_b = revision_graph(revision_b, 
 
237
                                                        revision_source)
 
238
    assert root == root_b
 
239
    common = set()
 
240
    for node, node_anc in ancestors_b.iteritems():
 
241
        if node in ancestors:
 
242
            common.add(node)
 
243
        else:
 
244
            ancestors[node] = set()
 
245
        ancestors[node].update(node_anc)
 
246
    for node, node_dec in descendants_b.iteritems():
 
247
        if node not in descendants:
 
248
            descendants[node] = set()
 
249
        descendants[node].update(node_dec)
 
250
    return root, ancestors, descendants, common
 
251
 
 
252
def common_ancestor(revision_a, revision_b, revision_source):
 
253
    root, ancestors, descendants, common = \
 
254
        combined_graph(revision_a, revision_b, revision_source)
 
255
    nodes = farthest_nodes(descendants, ancestors, root)
 
256
    for node in nodes:
 
257
        if node in common:
 
258
            return node
 
259
 
 
260
class MultipleRevisionSources(object):
 
261
    """Proxy that looks in multiple branches for revisions."""
 
262
    def __init__(self, *args):
 
263
        object.__init__(self)
 
264
        assert len(args) != 0
 
265
        self._revision_sources = args
 
266
 
 
267
    def get_revision(self, revision_id):
 
268
        for source in self._revision_sources:
 
269
            try:
 
270
                return source.get_revision(revision_id)
 
271
            except bzrlib.errors.NoSuchRevision, e:
 
272
                pass
 
273
        raise e
 
274
 
 
275
def get_intervening_revisions(ancestor_id, rev_id, rev_source, 
 
276
                              revision_history=None):
 
277
    """Find the longest line of descent from maybe_ancestor to revision.
 
278
    Revision history is followed where possible.
 
279
 
 
280
    If ancestor_id == rev_id, list will be empty.
 
281
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
282
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
283
    """
 
284
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
285
    if len(descendants) == 0:
 
286
        raise NoSuchRevision(rev_source, rev_id)
 
287
    if ancestor_id not in descendants:
 
288
        rev_source.get_revision(ancestor_id)
 
289
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
290
    root_descendants = all_descendants(descendants, ancestor_id)
 
291
    root_descendants.add(ancestor_id)
 
292
    if rev_id not in root_descendants:
 
293
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
294
    distances = node_distances(descendants, ancestors, ancestor_id,
 
295
                               root_descendants=root_descendants)
 
296
 
 
297
    def best_ancestor(rev_id):
 
298
        best = None
 
299
        for anc_id in ancestors[rev_id]:
 
300
            try:
 
301
                distance = distances[anc_id]
 
302
            except KeyError:
 
303
                continue
 
304
            if revision_history is not None and anc_id in revision_history:
 
305
                return anc_id
 
306
            elif best is None or distance > best[1]:
 
307
                best = (anc_id, distance)
 
308
        return best[0]
 
309
 
 
310
    next = rev_id
 
311
    path = []
 
312
    while next != ancestor_id:
 
313
        path.append(next)
 
314
        next = best_ancestor(next)
 
315
    path.reverse()
 
316
    return path