← 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: 2005-10-09 23:42:12 UTC
  • Revision ID: robertc@robertcollins.net-20051009234212-7973344d900afb0b
merge in niemeyers prefixed-store patch

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
16
16
 
17
17
 
18
18
import bzrlib.errors
19
 
 
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
 
 
 
19
from bzrlib.graph import node_distances, select_farthest, all_descendants
 
20
 
 
21
NULL_REVISION="null:"
44
22
 
45
23
class Revision(object):
46
24
    """Single revision on a branch.
51
29
 
52
30
    After bzr 0.0.5 revisions are allowed to have multiple parents.
53
31
 
54
 
    parents
55
 
        List of parent revisions, each is a RevisionReference.
 
32
    parent_ids
 
33
        List of parent revision_ids
56
34
    """
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
35
    
65
 
    def __init__(self, **args):
 
36
    def __init__(self, revision_id, **args):
 
37
        self.revision_id = revision_id
66
38
        self.__dict__.update(args)
67
 
        self.parents = []
68
 
 
 
39
        self.parent_ids = []
 
40
        self.parent_sha1s = []
69
41
 
70
42
    def __repr__(self):
71
43
        return "<Revision id %s>" % self.revision_id
73
45
    def __eq__(self, other):
74
46
        if not isinstance(other, Revision):
75
47
            return False
76
 
        return (self.inventory_id == other.inventory_id
77
 
                and self.inventory_sha1 == other.inventory_sha1
 
48
        # FIXME: rbc 20050930 parent_ids are not being compared
 
49
        return (
 
50
                self.inventory_sha1 == other.inventory_sha1
78
51
                and self.revision_id == other.revision_id
79
52
                and self.timestamp == other.timestamp
80
53
                and self.message == other.message
85
58
        return not self.__eq__(other)
86
59
 
87
60
        
88
 
 
89
61
REVISION_ID_RE = None
90
62
 
91
63
def validate_revision_id(rid):
93
65
    global REVISION_ID_RE
94
66
    if not REVISION_ID_RE:
95
67
        import re
96
 
        REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
 
68
        REVISION_ID_RE = re.compile('[\w:.-]+@[\w%.-]+--?[\w]+--?[0-9a-f]+\Z')
97
69
 
98
70
    if not REVISION_ID_RE.match(rid):
99
71
        raise ValueError("malformed revision-id %r" % rid)
100
72
 
101
 
def is_ancestor(revision_id, candidate_id, revision_source):
 
73
 
 
74
def is_ancestor(revision_id, candidate_id, branch):
102
75
    """Return true if candidate_id is an ancestor of revision_id.
 
76
 
103
77
    A false negative will be returned if any intermediate descendent of
104
78
    candidate_id is not present in any of the revision_sources.
105
79
    
106
80
    revisions_source is an object supporting a get_revision operation that
107
81
    behaves like Branch's.
108
82
    """
 
83
    return candidate_id in branch.get_ancestry(revision_id)
109
84
 
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
85
 
115
86
def iter_ancestors(revision_id, revision_source, only_present=False):
116
87
    ancestors = (revision_id,)
129
100
                    continue
130
101
            if only_present:
131
102
                yield ancestor, distance
132
 
            new_ancestors.extend([p.revision_id for p in revision.parents])
 
103
            new_ancestors.extend(revision.parent_ids)
133
104
        ancestors = new_ancestors
134
105
        distance += 1
135
106
 
159
130
    return matches
160
131
 
161
132
 
162
 
def common_ancestor(revision_a, revision_b, revision_source):
 
133
def old_common_ancestor(revision_a, revision_b, revision_source):
163
134
    """Find the ancestor common to both revisions that is closest to both.
164
135
    """
165
136
    from bzrlib.trace import mutter
190
161
        raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
191
162
    return a_closest[0]
192
163
 
 
164
def revision_graph(revision, revision_source):
 
165
    """Produce a graph of the ancestry of the specified revision.
 
166
    Return root, ancestors map, descendants map
 
167
 
 
168
    TODO: Produce graphs with the NULL revision as root, so that we can find
 
169
    a common even when trees are not branches don't represent a single line
 
170
    of descent.
 
171
    """
 
172
    ancestors = {}
 
173
    descendants = {}
 
174
    lines = [revision]
 
175
    root = None
 
176
    descendants[revision] = {}
 
177
    while len(lines) > 0:
 
178
        new_lines = set()
 
179
        for line in lines:
 
180
            if line == NULL_REVISION:
 
181
                parents = []
 
182
                root = NULL_REVISION
 
183
            else:
 
184
                try:
 
185
                    rev = revision_source.get_revision(line)
 
186
                    parents = list(rev.parent_ids)
 
187
                    if len(parents) == 0:
 
188
                        parents = [NULL_REVISION]
 
189
                except bzrlib.errors.NoSuchRevision:
 
190
                    if line == revision:
 
191
                        raise
 
192
                    parents = None
 
193
            if parents is not None:
 
194
                for parent in parents:
 
195
                    if parent not in ancestors:
 
196
                        new_lines.add(parent)
 
197
                    if parent not in descendants:
 
198
                        descendants[parent] = {}
 
199
                    descendants[parent][line] = 1
 
200
            if parents is not None:
 
201
                ancestors[line] = set(parents)
 
202
        lines = new_lines
 
203
    assert root not in descendants[root]
 
204
    assert root not in ancestors[root]
 
205
    return root, ancestors, descendants
 
206
 
 
207
 
 
208
def combined_graph(revision_a, revision_b, revision_source):
 
209
    """Produce a combined ancestry graph.
 
210
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
211
    root, ancestors, descendants = revision_graph(revision_a, revision_source)
 
212
    root_b, ancestors_b, descendants_b = revision_graph(revision_b, 
 
213
                                                        revision_source)
 
214
    if root != root_b:
 
215
        raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
 
216
    common = set()
 
217
    for node, node_anc in ancestors_b.iteritems():
 
218
        if node in ancestors:
 
219
            common.add(node)
 
220
        else:
 
221
            ancestors[node] = set()
 
222
        ancestors[node].update(node_anc)
 
223
    for node, node_dec in descendants_b.iteritems():
 
224
        if node not in descendants:
 
225
            descendants[node] = {}
 
226
        descendants[node].update(node_dec)
 
227
    return root, ancestors, descendants, common
 
228
 
 
229
 
 
230
def common_ancestor(revision_a, revision_b, revision_source):
 
231
    try:
 
232
        root, ancestors, descendants, common = \
 
233
            combined_graph(revision_a, revision_b, revision_source)
 
234
    except bzrlib.errors.NoCommonRoot:
 
235
        raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
236
        
 
237
    distances = node_distances (descendants, ancestors, root)
 
238
    farthest = select_farthest(distances, common)
 
239
    if farthest is None or farthest == NULL_REVISION:
 
240
        raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
241
    return farthest
 
242
 
 
243
 
193
244
class MultipleRevisionSources(object):
194
245
    """Proxy that looks in multiple branches for revisions."""
195
246
    def __init__(self, *args):
214
265
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
215
266
    If ancestor_id is not an ancestor, NotAncestor will be thrown
216
267
    """
217
 
    [rev_source.get_revision(r) for r in (ancestor_id, rev_id)]
218
 
    if ancestor_id == rev_id:
219
 
        return []
220
 
    def historical_lines(line):
221
 
        """Return a tuple of historical/non_historical lines, for sorting.
222
 
        The non_historical count is negative, since non_historical lines are
223
 
        a bad thing.
224
 
        """
225
 
        good_count = 0
226
 
        bad_count = 0
227
 
        for revision in line:
228
 
            if revision in revision_history:
229
 
                good_count += 1
230
 
            else:
231
 
                bad_count -= 1
232
 
        return good_count, bad_count
233
 
    active = [[rev_id]]
234
 
    successful_lines = []
235
 
    while len(active) > 0:
236
 
        new_active = []
237
 
        for line in active:
238
 
            parent_ids = [p.revision_id for p in 
239
 
                          rev_source.get_revision(line[-1]).parents]
240
 
            for parent in parent_ids:
241
 
                line_copy = line[:]
242
 
                if parent == ancestor_id:
243
 
                    successful_lines.append(line_copy)
244
 
                else:
245
 
                    line_copy.append(parent)
246
 
                    new_active.append(line_copy)
247
 
        active = new_active
248
 
    if len(successful_lines) == 0:
249
 
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
250
 
    for line in successful_lines:
251
 
        line.reverse()
252
 
    if revision_history is not None:
253
 
        by_historical_lines = []
254
 
        for line in successful_lines:
255
 
            count = historical_lines(line)
256
 
            by_historical_lines.append((count, line))
257
 
        by_historical_lines.sort()
258
 
        if by_historical_lines[-1][0][0] > 0:
259
 
            return by_historical_lines[-1][1]
260
 
    assert len(successful_lines)
261
 
    successful_lines.sort(cmp, len)
262
 
    return successful_lines[-1]
 
268
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
269
    if len(descendants) == 0:
 
270
        raise NoSuchRevision(rev_source, rev_id)
 
271
    if ancestor_id not in descendants:
 
272
        rev_source.get_revision(ancestor_id)
 
273
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
274
    root_descendants = all_descendants(descendants, ancestor_id)
 
275
    root_descendants.add(ancestor_id)
 
276
    if rev_id not in root_descendants:
 
277
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
278
    distances = node_distances(descendants, ancestors, ancestor_id,
 
279
                               root_descendants=root_descendants)
 
280
 
 
281
    def best_ancestor(rev_id):
 
282
        best = None
 
283
        for anc_id in ancestors[rev_id]:
 
284
            try:
 
285
                distance = distances[anc_id]
 
286
            except KeyError:
 
287
                continue
 
288
            if revision_history is not None and anc_id in revision_history:
 
289
                return anc_id
 
290
            elif best is None or distance > best[1]:
 
291
                best = (anc_id, distance)
 
292
        return best[0]
 
293
 
 
294
    next = rev_id
 
295
    path = []
 
296
    while next != ancestor_id:
 
297
        path.append(next)
 
298
        next = best_ancestor(next)
 
299
    path.reverse()
 
300
    return path