← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: aaron.bentley at utoronto
  • Date: 2005-09-04 02:59:56 UTC
  • mfrom: (1172)
  • mto: (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1178.
  • Revision ID: aaron.bentley@utoronto.ca-20050904025956-776ba4f07de97700
Merged mpool's latest changes (~0.0.7)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
 
18
 
 
19
 
 
20
 
from xml import XMLMixin
21
 
 
22
 
try:
23
 
    from cElementTree import Element, ElementTree, SubElement
24
 
except ImportError:
25
 
    from elementtree.ElementTree import Element, ElementTree, SubElement
26
 
 
27
 
from errors import BzrError
28
 
 
29
 
 
30
 
class RevisionReference:
 
18
import bzrlib.errors
 
19
 
 
20
 
 
21
class RevisionReference(object):
31
22
    """
32
23
    Reference to a stored revision.
33
24
 
35
26
    """
36
27
    revision_id = None
37
28
    revision_sha1 = None
38
 
    def __init__(self, revision_id, revision_sha1):
 
29
    def __init__(self, revision_id, revision_sha1=None):
39
30
        if revision_id == None \
40
31
           or isinstance(revision_id, basestring):
41
32
            self.revision_id = revision_id
51
42
                
52
43
 
53
44
 
54
 
class Revision(XMLMixin):
 
45
class Revision(object):
55
46
    """Single revision on a branch.
56
47
 
57
48
    Revisions may know their revision_hash, but only once they've been
59
50
    into the file it describes.
60
51
 
61
52
    After bzr 0.0.5 revisions are allowed to have multiple parents.
62
 
    To support old clients this is written out in a slightly redundant
63
 
    form: the first parent as the predecessor.  This will eventually
64
 
    be dropped.
65
53
 
66
54
    parents
67
55
        List of parent revisions, each is a RevisionReference.
78
66
        self.__dict__.update(args)
79
67
        self.parents = []
80
68
 
81
 
    def _get_precursor(self):
82
 
        from warnings import warn
83
 
        warn("Revision.precursor is deprecated", stacklevel=2)
84
 
        if self.parents:
85
 
            return self.parents[0].revision_id
86
 
        else:
87
 
            return None
88
 
 
89
 
 
90
 
    def _get_precursor_sha1(self):
91
 
        from warnings import warn
92
 
        warn("Revision.precursor_sha1 is deprecated", stacklevel=2)
93
 
        if self.parents:
94
 
            return self.parents[0].revision_sha1
95
 
        else:
96
 
            return None    
97
 
 
98
 
 
99
 
    def _fail(self):
100
 
        raise Exception("can't assign to precursor anymore")
101
 
 
102
 
 
103
 
    precursor = property(_get_precursor, _fail, _fail)
104
 
    precursor_sha1 = property(_get_precursor_sha1, _fail, _fail)
105
 
 
106
 
 
107
69
 
108
70
    def __repr__(self):
109
71
        return "<Revision id %s>" % self.revision_id
110
72
 
111
73
        
112
74
    def to_element(self):
 
75
        from bzrlib.xml import Element, SubElement
 
76
        
113
77
        root = Element('revision',
114
78
                       committer = self.committer,
115
79
                       timestamp = '%.9f' % self.timestamp,
126
90
        msg.tail = '\n'
127
91
 
128
92
        if self.parents:
129
 
            # first parent stored as precursor for compatability with 0.0.5 and
130
 
            # earlier
131
 
            pr = self.parents[0]
132
 
            assert pr.revision_id
133
 
            root.set('precursor', pr.revision_id)
134
 
            if pr.revision_sha1:
135
 
                root.set('precursor_sha1', pr.revision_sha1)
136
 
                
137
 
        if self.parents:
138
93
            pelts = SubElement(root, 'parents')
139
94
            pelts.tail = pelts.text = '\n'
140
95
            for rr in self.parents:
160
115
    """Convert XML element into Revision object."""
161
116
    # <changeset> is deprecated...
162
117
    if elt.tag not in ('revision', 'changeset'):
163
 
        raise BzrError("unexpected tag in revision file: %r" % elt)
 
118
        raise bzrlib.errors.BzrError("unexpected tag in revision file: %r" % elt)
164
119
 
165
120
    rev = Revision(committer = elt.get('committer'),
166
121
                   timestamp = float(elt.get('timestamp')),
174
129
 
175
130
    pelts = elt.find('parents')
176
131
 
177
 
    if precursor:
178
 
        # revisions written prior to 0.0.5 have a single precursor
179
 
        # give as an attribute
180
 
        rev_ref = RevisionReference(precursor, precursor_sha1)
181
 
        rev.parents.append(rev_ref)
182
 
    elif pelts:
 
132
    if pelts:
183
133
        for p in pelts:
184
134
            assert p.tag == 'revision_ref', \
185
135
                   "bad parent node tag %r" % p.tag
187
137
                                        p.get('revision_sha1'))
188
138
            rev.parents.append(rev_ref)
189
139
 
 
140
        if precursor:
 
141
            # must be consistent
 
142
            prec_parent = rev.parents[0].revision_id
 
143
            assert prec_parent == precursor
 
144
    elif precursor:
 
145
        # revisions written prior to 0.0.5 have a single precursor
 
146
        # give as an attribute
 
147
        rev_ref = RevisionReference(precursor, precursor_sha1)
 
148
        rev.parents.append(rev_ref)
 
149
 
190
150
    v = elt.get('timezone')
191
151
    rev.timezone = v and int(v)
192
152
 
193
153
    rev.message = elt.findtext('message') # text of <message>
194
154
    return rev
 
155
 
 
156
 
 
157
 
 
158
REVISION_ID_RE = None
 
159
 
 
160
def validate_revision_id(rid):
 
161
    """Check rid is syntactically valid for a revision id."""
 
162
    global REVISION_ID_RE
 
163
    if not REVISION_ID_RE:
 
164
        import re
 
165
        REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
 
166
 
 
167
    if not REVISION_ID_RE.match(rid):
 
168
        raise ValueError("malformed revision-id %r" % rid)
 
169
 
 
170
def is_ancestor(revision_id, candidate_id, revision_source):
 
171
    """Return true if candidate_id is an ancestor of revision_id.
 
172
    A false negative will be returned if any intermediate descendent of
 
173
    candidate_id is not present in any of the revision_sources.
 
174
    
 
175
    revisions_source is an object supporting a get_revision operation that
 
176
    behaves like Branch's.
 
177
    """
 
178
 
 
179
    for ancestor_id, distance in iter_ancestors(revision_id, revision_source):
 
180
        if ancestor_id == candidate_id:
 
181
            return True
 
182
    return False
 
183
 
 
184
def iter_ancestors(revision_id, revision_source, only_present=False):
 
185
    ancestors = (revision_id,)
 
186
    distance = 0
 
187
    while len(ancestors) > 0:
 
188
        new_ancestors = []
 
189
        for ancestor in ancestors:
 
190
            if not only_present:
 
191
                yield ancestor, distance
 
192
            try:
 
193
                revision = revision_source.get_revision(ancestor)
 
194
            except bzrlib.errors.NoSuchRevision, e:
 
195
                if e.revision == revision_id:
 
196
                    raise 
 
197
                else:
 
198
                    continue
 
199
            if only_present:
 
200
                yield ancestor, distance
 
201
            new_ancestors.extend([p.revision_id for p in revision.parents])
 
202
        ancestors = new_ancestors
 
203
        distance += 1
 
204
 
 
205
 
 
206
def find_present_ancestors(revision_id, revision_source):
 
207
    """Return the ancestors of a revision present in a branch.
 
208
 
 
209
    It's possible that a branch won't have the complete ancestry of
 
210
    one of its revisions.  
 
211
 
 
212
    """
 
213
    found_ancestors = {}
 
214
    anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
 
215
                         only_present=True))
 
216
    for anc_order, (anc_id, anc_distance) in anc_iter:
 
217
        if not found_ancestors.has_key(anc_id):
 
218
            found_ancestors[anc_id] = (anc_order, anc_distance)
 
219
    return found_ancestors
 
220
    
 
221
 
 
222
def __get_closest(intersection):
 
223
    intersection.sort()
 
224
    matches = [] 
 
225
    for entry in intersection:
 
226
        if entry[0] == intersection[0][0]:
 
227
            matches.append(entry[2])
 
228
    return matches
 
229
 
 
230
 
 
231
def common_ancestor(revision_a, revision_b, revision_source):
 
232
    """Find the ancestor common to both revisions that is closest to both.
 
233
    """
 
234
    from bzrlib.trace import mutter
 
235
    a_ancestors = find_present_ancestors(revision_a, revision_source)
 
236
    b_ancestors = find_present_ancestors(revision_b, revision_source)
 
237
    a_intersection = []
 
238
    b_intersection = []
 
239
    # a_order is used as a tie-breaker when two equally-good bases are found
 
240
    for revision, (a_order, a_distance) in a_ancestors.iteritems():
 
241
        if b_ancestors.has_key(revision):
 
242
            a_intersection.append((a_distance, a_order, revision))
 
243
            b_intersection.append((b_ancestors[revision][1], a_order, revision))
 
244
    mutter("a intersection: %r" % a_intersection)
 
245
    mutter("b intersection: %r" % b_intersection)
 
246
 
 
247
    a_closest = __get_closest(a_intersection)
 
248
    if len(a_closest) == 0:
 
249
        return None
 
250
    b_closest = __get_closest(b_intersection)
 
251
    assert len(b_closest) != 0
 
252
    mutter ("a_closest %r" % a_closest)
 
253
    mutter ("b_closest %r" % b_closest)
 
254
    if a_closest[0] in b_closest:
 
255
        return a_closest[0]
 
256
    elif b_closest[0] in a_closest:
 
257
        return b_closest[0]
 
258
    else:
 
259
        raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
 
260
    return a_closest[0]
 
261
 
 
262
class MultipleRevisionSources(object):
 
263
    """Proxy that looks in multiple branches for revisions."""
 
264
    def __init__(self, *args):
 
265
        object.__init__(self)
 
266
        assert len(args) != 0
 
267
        self._revision_sources = args
 
268
 
 
269
    def get_revision(self, revision_id):
 
270
        for source in self._revision_sources:
 
271
            try:
 
272
                return source.get_revision(revision_id)
 
273
            except bzrlib.errors.NoSuchRevision, e:
 
274
                pass
 
275
        raise e
 
276
 
 
277
def get_intervening_revisions(ancestor_id, rev_id, rev_source, 
 
278
                              revision_history=None):
 
279
    """Find the longest line of descent from maybe_ancestor to revision.
 
280
    Revision history is followed where possible.
 
281
 
 
282
    If ancestor_id == rev_id, list will be empty.
 
283
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
284
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
285
    """
 
286
    [rev_source.get_revision(r) for r in (ancestor_id, rev_id)]
 
287
    if ancestor_id == rev_id:
 
288
        return []
 
289
    def historical_lines(line):
 
290
        """Return a tuple of historical/non_historical lines, for sorting.
 
291
        The non_historical count is negative, since non_historical lines are
 
292
        a bad thing.
 
293
        """
 
294
        good_count = 0
 
295
        bad_count = 0
 
296
        for revision in line:
 
297
            if revision in revision_history:
 
298
                good_count += 1
 
299
            else:
 
300
                bad_count -= 1
 
301
        return good_count, bad_count
 
302
    active = [[rev_id]]
 
303
    successful_lines = []
 
304
    while len(active) > 0:
 
305
        new_active = []
 
306
        for line in active:
 
307
            parent_ids = [p.revision_id for p in 
 
308
                          rev_source.get_revision(line[-1]).parents]
 
309
            for parent in parent_ids:
 
310
                line_copy = line[:]
 
311
                if parent == ancestor_id:
 
312
                    successful_lines.append(line_copy)
 
313
                else:
 
314
                    line_copy.append(parent)
 
315
                    new_active.append(line_copy)
 
316
        active = new_active
 
317
    if len(successful_lines) == 0:
 
318
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
319
    for line in successful_lines:
 
320
        line.reverse()
 
321
    if revision_history is not None:
 
322
        by_historical_lines = []
 
323
        for line in successful_lines:
 
324
            count = historical_lines(line)
 
325
            by_historical_lines.append((count, line))
 
326
        by_historical_lines.sort()
 
327
        if by_historical_lines[-1][0][0] > 0:
 
328
            return by_historical_lines[-1][1]
 
329
    assert len(successful_lines)
 
330
    successful_lines.sort(cmp, len)
 
331
    return successful_lines[-1]