~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Aaron Bentley
  • Date: 2005-09-21 15:33:23 UTC
  • mto: (1185.1.37)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: abentley@panoramicfeedback.com-20050921153323-5db674d572d7649d
Fixed bug in distance-from-root graph operation

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
19
from bzrlib.graph import node_distances, select_farthest, all_descendants
22
 
from bzrlib.osutils import contains_whitespace
23
20
 
24
21
NULL_REVISION="null:"
25
22
 
 
23
class RevisionReference(object):
 
24
    """
 
25
    Reference to a stored revision.
 
26
 
 
27
    Includes the revision_id and revision_sha1.
 
28
    """
 
29
    revision_id = None
 
30
    revision_sha1 = None
 
31
    def __init__(self, revision_id, revision_sha1=None):
 
32
        if revision_id == None \
 
33
           or isinstance(revision_id, basestring):
 
34
            self.revision_id = revision_id
 
35
        else:
 
36
            raise ValueError('bad revision_id %r' % revision_id)
 
37
 
 
38
        if revision_sha1 != None:
 
39
            if isinstance(revision_sha1, basestring) \
 
40
               and len(revision_sha1) == 40:
 
41
                self.revision_sha1 = revision_sha1
 
42
            else:
 
43
                raise ValueError('bad revision_sha1 %r' % revision_sha1)
 
44
                
 
45
 
 
46
 
26
47
class Revision(object):
27
48
    """Single revision on a branch.
28
49
 
32
53
 
33
54
    After bzr 0.0.5 revisions are allowed to have multiple parents.
34
55
 
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.
 
56
    parents
 
57
        List of parent revisions, each is a RevisionReference.
42
58
    """
 
59
    inventory_id = None
 
60
    inventory_sha1 = None
 
61
    revision_id = None
 
62
    timestamp = None
 
63
    message = None
 
64
    timezone = None
 
65
    committer = None
43
66
    
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 = []
 
67
    def __init__(self, **args):
50
68
        self.__dict__.update(args)
 
69
        self.parents = []
 
70
 
51
71
 
52
72
    def __repr__(self):
53
73
        return "<Revision id %s>" % self.revision_id
55
75
    def __eq__(self, other):
56
76
        if not isinstance(other, Revision):
57
77
            return False
58
 
        # FIXME: rbc 20050930 parent_ids are not being compared
59
 
        return (
60
 
                self.inventory_sha1 == other.inventory_sha1
 
78
        return (self.inventory_id == other.inventory_id
 
79
                and self.inventory_sha1 == other.inventory_sha1
61
80
                and self.revision_id == other.revision_id
62
81
                and self.timestamp == other.timestamp
63
82
                and self.message == other.message
64
83
                and self.timezone == other.timezone
65
 
                and self.committer == other.committer
66
 
                and self.properties == other.properties)
 
84
                and self.committer == other.committer)
67
85
 
68
86
    def __ne__(self, other):
69
87
        return not self.__eq__(other)
70
88
 
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):
 
89
        
 
90
 
 
91
REVISION_ID_RE = None
 
92
 
 
93
def validate_revision_id(rid):
 
94
    """Check rid is syntactically valid for a revision id."""
 
95
    global REVISION_ID_RE
 
96
    if not REVISION_ID_RE:
 
97
        import re
 
98
        REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
 
99
 
 
100
    if not REVISION_ID_RE.match(rid):
 
101
        raise ValueError("malformed revision-id %r" % rid)
 
102
 
 
103
def is_ancestor(revision_id, candidate_id, revision_source):
83
104
    """Return true if candidate_id is an ancestor of revision_id.
84
 
 
85
105
    A false negative will be returned if any intermediate descendent of
86
106
    candidate_id is not present in any of the revision_sources.
87
107
    
88
108
    revisions_source is an object supporting a get_revision operation that
89
109
    behaves like Branch's.
90
110
    """
91
 
    return candidate_id in branch.repository.get_ancestry(revision_id)
92
 
 
 
111
    if candidate_id is None:
 
112
        return True
 
113
    for ancestor_id, distance in iter_ancestors(revision_id, revision_source):
 
114
        if ancestor_id == candidate_id:
 
115
            return True
 
116
    return False
93
117
 
94
118
def iter_ancestors(revision_id, revision_source, only_present=False):
95
119
    ancestors = (revision_id,)
108
132
                    continue
109
133
            if only_present:
110
134
                yield ancestor, distance
111
 
            new_ancestors.extend(revision.parent_ids)
 
135
            new_ancestors.extend([p.revision_id for p in revision.parents])
112
136
        ancestors = new_ancestors
113
137
        distance += 1
114
138
 
151
175
        if b_ancestors.has_key(revision):
152
176
            a_intersection.append((a_distance, a_order, revision))
153
177
            b_intersection.append((b_ancestors[revision][1], a_order, revision))
154
 
    mutter("a intersection: %r", a_intersection)
155
 
    mutter("b intersection: %r", b_intersection)
 
178
    mutter("a intersection: %r" % a_intersection)
 
179
    mutter("b intersection: %r" % b_intersection)
156
180
 
157
181
    a_closest = __get_closest(a_intersection)
158
182
    if len(a_closest) == 0:
159
183
        return None
160
184
    b_closest = __get_closest(b_intersection)
161
185
    assert len(b_closest) != 0
162
 
    mutter ("a_closest %r", a_closest)
163
 
    mutter ("b_closest %r", b_closest)
 
186
    mutter ("a_closest %r" % a_closest)
 
187
    mutter ("b_closest %r" % b_closest)
164
188
    if a_closest[0] in b_closest:
165
189
        return a_closest[0]
166
190
    elif b_closest[0] in a_closest:
176
200
    TODO: Produce graphs with the NULL revision as root, so that we can find
177
201
    a common even when trees are not branches don't represent a single line
178
202
    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
203
    """
182
204
    ancestors = {}
183
205
    descendants = {}
193
215
            else:
194
216
                try:
195
217
                    rev = revision_source.get_revision(line)
196
 
                    parents = list(rev.parent_ids)
 
218
                    parents = [p.revision_id for p in rev.parents]
197
219
                    if len(parents) == 0:
198
220
                        parents = [NULL_REVISION]
199
221
                except bzrlib.errors.NoSuchRevision:
210
232
            if parents is not None:
211
233
                ancestors[line] = set(parents)
212
234
        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
235
    assert root not in descendants[root]
237
236
    assert root not in ancestors[root]
238
237
    return root, ancestors, descendants
239
238
 
240
 
 
241
239
def combined_graph(revision_a, revision_b, revision_source):
242
240
    """Produce a combined ancestry graph.
243
241
    Return graph root, ancestors map, descendants map, set of common nodes"""
259
257
        descendants[node].update(node_dec)
260
258
    return root, ancestors, descendants, common
261
259
 
262
 
 
263
260
def common_ancestor(revision_a, revision_b, revision_source):
264
261
    try:
265
262
        root, ancestors, descendants, common = \
273
270
        raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
274
271
    return farthest
275
272
 
276
 
 
277
273
class MultipleRevisionSources(object):
278
274
    """Proxy that looks in multiple branches for revisions."""
279
275
    def __init__(self, *args):