/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: Martin Pool
  • Date: 2005-09-05 09:27:11 UTC
  • Revision ID: mbp@sourcefrog.net-20050905092711-f9f5bded3fd82605
- more disentangling of xml storage format from objects

- remove pack_xml and unpack_xml function in favor of 
  serializer object

- test unpacking canned revision xml

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
 
 
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
        
 
74
 
 
75
REVISION_ID_RE = None
 
76
 
 
77
def validate_revision_id(rid):
 
78
    """Check rid is syntactically valid for a revision id."""
 
79
    global REVISION_ID_RE
 
80
    if not REVISION_ID_RE:
 
81
        import re
 
82
        REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
 
83
 
 
84
    if not REVISION_ID_RE.match(rid):
 
85
        raise ValueError("malformed revision-id %r" % rid)
 
86
 
 
87
def is_ancestor(revision_id, candidate_id, revision_source):
 
88
    """Return true if candidate_id is an ancestor of revision_id.
 
89
    A false negative will be returned if any intermediate descendent of
 
90
    candidate_id is not present in any of the revision_sources.
 
91
    
 
92
    revisions_source is an object supporting a get_revision operation that
 
93
    behaves like Branch's.
 
94
    """
 
95
 
 
96
    for ancestor_id, distance in iter_ancestors(revision_id, revision_source):
 
97
        if ancestor_id == candidate_id:
 
98
            return True
 
99
    return False
 
100
 
 
101
def iter_ancestors(revision_id, revision_source, only_present=False):
 
102
    ancestors = (revision_id,)
 
103
    distance = 0
 
104
    while len(ancestors) > 0:
 
105
        new_ancestors = []
 
106
        for ancestor in ancestors:
 
107
            if not only_present:
 
108
                yield ancestor, distance
 
109
            try:
 
110
                revision = revision_source.get_revision(ancestor)
 
111
            except bzrlib.errors.NoSuchRevision, e:
 
112
                if e.revision == revision_id:
 
113
                    raise 
 
114
                else:
 
115
                    continue
 
116
            if only_present:
 
117
                yield ancestor, distance
 
118
            new_ancestors.extend([p.revision_id for p in revision.parents])
 
119
        ancestors = new_ancestors
 
120
        distance += 1
 
121
 
 
122
 
 
123
def find_present_ancestors(revision_id, revision_source):
 
124
    """Return the ancestors of a revision present in a branch.
 
125
 
 
126
    It's possible that a branch won't have the complete ancestry of
 
127
    one of its revisions.  
 
128
 
 
129
    """
 
130
    found_ancestors = {}
 
131
    anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
 
132
                         only_present=True))
 
133
    for anc_order, (anc_id, anc_distance) in anc_iter:
 
134
        if not found_ancestors.has_key(anc_id):
 
135
            found_ancestors[anc_id] = (anc_order, anc_distance)
 
136
    return found_ancestors
 
137
    
 
138
 
 
139
def __get_closest(intersection):
 
140
    intersection.sort()
 
141
    matches = [] 
 
142
    for entry in intersection:
 
143
        if entry[0] == intersection[0][0]:
 
144
            matches.append(entry[2])
 
145
    return matches
 
146
 
 
147
 
 
148
def common_ancestor(revision_a, revision_b, revision_source):
 
149
    """Find the ancestor common to both revisions that is closest to both.
 
150
    """
 
151
    from bzrlib.trace import mutter
 
152
    a_ancestors = find_present_ancestors(revision_a, revision_source)
 
153
    b_ancestors = find_present_ancestors(revision_b, revision_source)
 
154
    a_intersection = []
 
155
    b_intersection = []
 
156
    # a_order is used as a tie-breaker when two equally-good bases are found
 
157
    for revision, (a_order, a_distance) in a_ancestors.iteritems():
 
158
        if b_ancestors.has_key(revision):
 
159
            a_intersection.append((a_distance, a_order, revision))
 
160
            b_intersection.append((b_ancestors[revision][1], a_order, revision))
 
161
    mutter("a intersection: %r" % a_intersection)
 
162
    mutter("b intersection: %r" % b_intersection)
 
163
 
 
164
    a_closest = __get_closest(a_intersection)
 
165
    if len(a_closest) == 0:
 
166
        return None
 
167
    b_closest = __get_closest(b_intersection)
 
168
    assert len(b_closest) != 0
 
169
    mutter ("a_closest %r" % a_closest)
 
170
    mutter ("b_closest %r" % b_closest)
 
171
    if a_closest[0] in b_closest:
 
172
        return a_closest[0]
 
173
    elif b_closest[0] in a_closest:
 
174
        return b_closest[0]
 
175
    else:
 
176
        raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
 
177
    return a_closest[0]
 
178
 
 
179
class MultipleRevisionSources(object):
 
180
    """Proxy that looks in multiple branches for revisions."""
 
181
    def __init__(self, *args):
 
182
        object.__init__(self)
 
183
        assert len(args) != 0
 
184
        self._revision_sources = args
 
185
 
 
186
    def get_revision(self, revision_id):
 
187
        for source in self._revision_sources:
 
188
            try:
 
189
                return source.get_revision(revision_id)
 
190
            except bzrlib.errors.NoSuchRevision, e:
 
191
                pass
 
192
        raise e
 
193
 
 
194
def get_intervening_revisions(ancestor_id, rev_id, rev_source, 
 
195
                              revision_history=None):
 
196
    """Find the longest line of descent from maybe_ancestor to revision.
 
197
    Revision history is followed where possible.
 
198
 
 
199
    If ancestor_id == rev_id, list will be empty.
 
200
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
201
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
202
    """
 
203
    [rev_source.get_revision(r) for r in (ancestor_id, rev_id)]
 
204
    if ancestor_id == rev_id:
 
205
        return []
 
206
    def historical_lines(line):
 
207
        """Return a tuple of historical/non_historical lines, for sorting.
 
208
        The non_historical count is negative, since non_historical lines are
 
209
        a bad thing.
 
210
        """
 
211
        good_count = 0
 
212
        bad_count = 0
 
213
        for revision in line:
 
214
            if revision in revision_history:
 
215
                good_count += 1
 
216
            else:
 
217
                bad_count -= 1
 
218
        return good_count, bad_count
 
219
    active = [[rev_id]]
 
220
    successful_lines = []
 
221
    while len(active) > 0:
 
222
        new_active = []
 
223
        for line in active:
 
224
            parent_ids = [p.revision_id for p in 
 
225
                          rev_source.get_revision(line[-1]).parents]
 
226
            for parent in parent_ids:
 
227
                line_copy = line[:]
 
228
                if parent == ancestor_id:
 
229
                    successful_lines.append(line_copy)
 
230
                else:
 
231
                    line_copy.append(parent)
 
232
                    new_active.append(line_copy)
 
233
        active = new_active
 
234
    if len(successful_lines) == 0:
 
235
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
236
    for line in successful_lines:
 
237
        line.reverse()
 
238
    if revision_history is not None:
 
239
        by_historical_lines = []
 
240
        for line in successful_lines:
 
241
            count = historical_lines(line)
 
242
            by_historical_lines.append((count, line))
 
243
        by_historical_lines.sort()
 
244
        if by_historical_lines[-1][0][0] > 0:
 
245
            return by_historical_lines[-1][1]
 
246
    assert len(successful_lines)
 
247
    successful_lines.sort(cmp, len)
 
248
    return successful_lines[-1]