/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: Robert Collins
  • Date: 2005-10-14 02:17:36 UTC
  • mfrom: (1185.16.34)
  • Revision ID: robertc@lifelesslap.robertcollins.net-20051014021736-7230e59066856096
Merge from Martin.

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