~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: John Arbash Meinel
  • Date: 2005-09-17 20:29:29 UTC
  • mto: (1393.2.1)
  • mto: This revision was merged to the branch mainline in revision 1396.
  • Revision ID: john@arbash-meinel.com-20050917202929-a9e4a3be80bf4ba4
Working on getting tests to run. TestFetch only works if named runTest

Show diffs side-by-side

added added

removed removed

Lines of Context:
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
 
# TODO: Some kind of command-line display of revision properties: 
18
 
# perhaps show them in log -v and allow them as options to the commit command.
19
17
 
20
18
import bzrlib.errors
21
 
from bzrlib.graph import node_distances, select_farthest, all_descendants
22
 
from bzrlib.osutils import contains_whitespace
23
 
 
24
 
NULL_REVISION="null:"
 
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
 
25
44
 
26
45
class Revision(object):
27
46
    """Single revision on a branch.
32
51
 
33
52
    After bzr 0.0.5 revisions are allowed to have multiple parents.
34
53
 
35
 
    parent_ids
36
 
        List of parent revision_ids
37
 
 
38
 
    properties
39
 
        Dictionary of revision properties.  These are attached to the
40
 
        revision as extra metadata.  The name must be a single 
41
 
        word; the value can be an arbitrary string.
 
54
    parents
 
55
        List of parent revisions, each is a RevisionReference.
42
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
43
64
    
44
 
    def __init__(self, revision_id, properties=None, **args):
45
 
        self.revision_id = revision_id
46
 
        self.properties = properties or {}
47
 
        self._check_properties()
48
 
        self.parent_ids = []
49
 
        self.parent_sha1s = []
 
65
    def __init__(self, **args):
50
66
        self.__dict__.update(args)
 
67
        self.parents = []
 
68
 
51
69
 
52
70
    def __repr__(self):
53
71
        return "<Revision id %s>" % self.revision_id
55
73
    def __eq__(self, other):
56
74
        if not isinstance(other, Revision):
57
75
            return False
58
 
        # FIXME: rbc 20050930 parent_ids are not being compared
59
 
        return (
60
 
                self.inventory_sha1 == other.inventory_sha1
 
76
        return (self.inventory_id == other.inventory_id
 
77
                and self.inventory_sha1 == other.inventory_sha1
61
78
                and self.revision_id == other.revision_id
62
79
                and self.timestamp == other.timestamp
63
80
                and self.message == other.message
64
81
                and self.timezone == other.timezone
65
 
                and self.committer == other.committer
66
 
                and self.properties == other.properties)
 
82
                and self.committer == other.committer)
67
83
 
68
84
    def __ne__(self, other):
69
85
        return not self.__eq__(other)
70
86
 
71
 
    def _check_properties(self):
72
 
        """Verify that all revision properties are OK.
73
 
        """
74
 
        for name, value in self.properties.iteritems():
75
 
            if not isinstance(name, basestring) or contains_whitespace(name):
76
 
                raise ValueError("invalid property name %r" % name)
77
 
            if not isinstance(value, basestring):
78
 
                raise ValueError("invalid property value %r for %r" % 
79
 
                                 (name, value))
80
 
 
81
 
 
82
 
def is_ancestor(revision_id, candidate_id, branch):
 
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):
83
102
    """Return true if candidate_id is an ancestor of revision_id.
84
 
 
85
103
    A false negative will be returned if any intermediate descendent of
86
104
    candidate_id is not present in any of the revision_sources.
87
105
    
88
106
    revisions_source is an object supporting a get_revision operation that
89
107
    behaves like Branch's.
90
108
    """
91
 
    return candidate_id in branch.get_ancestry(revision_id)
92
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
93
114
 
94
115
def iter_ancestors(revision_id, revision_source, only_present=False):
95
116
    ancestors = (revision_id,)
108
129
                    continue
109
130
            if only_present:
110
131
                yield ancestor, distance
111
 
            new_ancestors.extend(revision.parent_ids)
 
132
            new_ancestors.extend([p.revision_id for p in revision.parents])
112
133
        ancestors = new_ancestors
113
134
        distance += 1
114
135
 
151
172
        if b_ancestors.has_key(revision):
152
173
            a_intersection.append((a_distance, a_order, revision))
153
174
            b_intersection.append((b_ancestors[revision][1], a_order, revision))
154
 
    mutter("a intersection: %r", a_intersection)
155
 
    mutter("b intersection: %r", b_intersection)
 
175
    mutter("a intersection: %r" % a_intersection)
 
176
    mutter("b intersection: %r" % b_intersection)
156
177
 
157
178
    a_closest = __get_closest(a_intersection)
158
179
    if len(a_closest) == 0:
159
180
        return None
160
181
    b_closest = __get_closest(b_intersection)
161
182
    assert len(b_closest) != 0
162
 
    mutter ("a_closest %r", a_closest)
163
 
    mutter ("b_closest %r", b_closest)
 
183
    mutter ("a_closest %r" % a_closest)
 
184
    mutter ("b_closest %r" % b_closest)
164
185
    if a_closest[0] in b_closest:
165
186
        return a_closest[0]
166
187
    elif b_closest[0] in a_closest:
176
197
    TODO: Produce graphs with the NULL revision as root, so that we can find
177
198
    a common even when trees are not branches don't represent a single line
178
199
    of descent.
179
 
    RBC: 20051024: note that when we have two partial histories, this may not
180
 
         be possible. But if we are willing to pretend :)... sure.
181
200
    """
182
201
    ancestors = {}
183
202
    descendants = {}
187
206
    while len(lines) > 0:
188
207
        new_lines = set()
189
208
        for line in lines:
190
 
            if line == NULL_REVISION:
191
 
                parents = []
192
 
                root = NULL_REVISION
193
 
            else:
194
 
                try:
195
 
                    rev = revision_source.get_revision(line)
196
 
                    parents = list(rev.parent_ids)
197
 
                    if len(parents) == 0:
198
 
                        parents = [NULL_REVISION]
199
 
                except bzrlib.errors.NoSuchRevision:
200
 
                    if line == revision:
201
 
                        raise
202
 
                    parents = None
 
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
203
218
            if parents is not None:
204
219
                for parent in parents:
205
220
                    if parent not in ancestors:
210
225
            if parents is not None:
211
226
                ancestors[line] = set(parents)
212
227
        lines = new_lines
213
 
    if root is None:
214
 
        # The history for revision becomes inaccessible without
215
 
        # actually hitting a no-parents revision. This then
216
 
        # makes these asserts below trigger. So, if root is None
217
 
        # determine the actual root by walking the accessible tree
218
 
        # and then stash NULL_REVISION at the end.
219
 
        root = NULL_REVISION
220
 
        descendants[root] = {}
221
 
        # for every revision, check we can access at least
222
 
        # one parent, if we cant, add NULL_REVISION and
223
 
        # a link
224
 
        for rev in ancestors:
225
 
            if len(ancestors[rev]) == 0:
226
 
                raise RuntimeError('unreachable code ?!')
227
 
            ok = False
228
 
            for parent in ancestors[rev]:
229
 
                if parent in ancestors:
230
 
                    ok = True
231
 
            if ok:
232
 
                continue
233
 
            descendants[root][rev] = 1
234
 
            ancestors[rev].add(root)
235
 
        ancestors[root] = set()
236
228
    assert root not in descendants[root]
237
229
    assert root not in ancestors[root]
238
230
    return root, ancestors, descendants
239
231
 
240
 
 
241
232
def combined_graph(revision_a, revision_b, revision_source):
242
233
    """Produce a combined ancestry graph.
243
234
    Return graph root, ancestors map, descendants map, set of common nodes"""
255
246
        ancestors[node].update(node_anc)
256
247
    for node, node_dec in descendants_b.iteritems():
257
248
        if node not in descendants:
258
 
            descendants[node] = {}
 
249
            descendants[node] = set()
259
250
        descendants[node].update(node_dec)
260
251
    return root, ancestors, descendants, common
261
252
 
262
 
 
263
253
def common_ancestor(revision_a, revision_b, revision_source):
264
254
    try:
265
255
        root, ancestors, descendants, common = \
267
257
    except bzrlib.errors.NoCommonRoot:
268
258
        raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
269
259
        
270
 
    distances = node_distances (descendants, ancestors, root)
271
 
    farthest = select_farthest(distances, common)
272
 
    if farthest is None or farthest == NULL_REVISION:
273
 
        raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
274
 
    return farthest
275
 
 
 
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)
276
265
 
277
266
class MultipleRevisionSources(object):
278
267
    """Proxy that looks in multiple branches for revisions."""