/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

merge merge tweaks from aaron, which includes latest .dev

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