/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: John Arbash Meinel
  • Date: 2005-09-15 21:35:53 UTC
  • mfrom: (907.1.57)
  • mto: (1393.2.1)
  • mto: This revision was merged to the branch mainline in revision 1396.
  • Revision ID: john@arbash-meinel.com-20050915213552-a6c83a5ef1e20897
(broken) Transport work is merged in. Tests do not pass yet.

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
    if root != root_b:
 
239
        raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
 
240
    common = set()
 
241
    for node, node_anc in ancestors_b.iteritems():
 
242
        if node in ancestors:
 
243
            common.add(node)
 
244
        else:
 
245
            ancestors[node] = set()
 
246
        ancestors[node].update(node_anc)
 
247
    for node, node_dec in descendants_b.iteritems():
 
248
        if node not in descendants:
 
249
            descendants[node] = set()
 
250
        descendants[node].update(node_dec)
 
251
    return root, ancestors, descendants, common
 
252
 
 
253
def common_ancestor(revision_a, revision_b, revision_source):
 
254
    try:
 
255
        root, ancestors, descendants, common = \
 
256
            combined_graph(revision_a, revision_b, revision_source)
 
257
    except bzrlib.errors.NoCommonRoot:
 
258
        raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
259
        
 
260
    nodes = farthest_nodes(descendants, ancestors, root)
 
261
    for node in nodes:
 
262
        if node in common:
 
263
            return node
 
264
    raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
265
 
 
266
class MultipleRevisionSources(object):
 
267
    """Proxy that looks in multiple branches for revisions."""
 
268
    def __init__(self, *args):
 
269
        object.__init__(self)
 
270
        assert len(args) != 0
 
271
        self._revision_sources = args
 
272
 
 
273
    def get_revision(self, revision_id):
 
274
        for source in self._revision_sources:
 
275
            try:
 
276
                return source.get_revision(revision_id)
 
277
            except bzrlib.errors.NoSuchRevision, e:
 
278
                pass
 
279
        raise e
 
280
 
 
281
def get_intervening_revisions(ancestor_id, rev_id, rev_source, 
 
282
                              revision_history=None):
 
283
    """Find the longest line of descent from maybe_ancestor to revision.
 
284
    Revision history is followed where possible.
 
285
 
 
286
    If ancestor_id == rev_id, list will be empty.
 
287
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
288
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
289
    """
 
290
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
291
    if len(descendants) == 0:
 
292
        raise NoSuchRevision(rev_source, rev_id)
 
293
    if ancestor_id not in descendants:
 
294
        rev_source.get_revision(ancestor_id)
 
295
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
296
    root_descendants = all_descendants(descendants, ancestor_id)
 
297
    root_descendants.add(ancestor_id)
 
298
    if rev_id not in root_descendants:
 
299
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
300
    distances = node_distances(descendants, ancestors, ancestor_id,
 
301
                               root_descendants=root_descendants)
 
302
 
 
303
    def best_ancestor(rev_id):
 
304
        best = None
 
305
        for anc_id in ancestors[rev_id]:
 
306
            try:
 
307
                distance = distances[anc_id]
 
308
            except KeyError:
 
309
                continue
 
310
            if revision_history is not None and anc_id in revision_history:
 
311
                return anc_id
 
312
            elif best is None or distance > best[1]:
 
313
                best = (anc_id, distance)
 
314
        return best[0]
 
315
 
 
316
    next = rev_id
 
317
    path = []
 
318
    while next != ancestor_id:
 
319
        path.append(next)
 
320
        next = best_ancestor(next)
 
321
    path.reverse()
 
322
    return path