← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: John Arbash Meinel
  • Date: 2006-06-30 21:38:52 UTC
  • mto: (1711.4.39 win32-accepted)
  • mto: This revision was merged to the branch mainline in revision 1836.
  • Revision ID: john@arbash-meinel.com-20060630213852-8a2dd85d080541a1
check_text_file was leaving the file handle open, now it closes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
1
 
# Copyright (C) 2005-2010 Canonical Ltd
2
 
#
 
1
# Copyright (C) 2005, 2006 Canonical
 
2
 
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
5
5
# the Free Software Foundation; either version 2 of the License, or
6
6
# (at your option) any later version.
7
 
#
 
7
 
8
8
# This program is distributed in the hope that it will be useful,
9
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
# GNU General Public License for more details.
12
 
#
 
12
 
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
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:
 
17
# TODO: Some kind of command-line display of revision properties: 
18
18
# perhaps show them in log -v and allow them as options to the commit command.
19
19
 
20
20
 
21
 
from bzrlib.lazy_import import lazy_import
22
 
lazy_import(globals(), """
23
 
from bzrlib import deprecated_graph
24
 
from bzrlib import bugtracker
25
 
""")
26
 
from bzrlib import (
27
 
    errors,
28
 
    symbol_versioning,
29
 
    )
 
21
import bzrlib.errors as errors
 
22
from bzrlib.graph import node_distances, select_farthest, all_descendants, Graph
30
23
from bzrlib.osutils import contains_whitespace
 
24
from bzrlib.progress import DummyProgress
 
25
from bzrlib.symbol_versioning import (deprecated_function,
 
26
        zero_eight,
 
27
        )
31
28
 
32
29
NULL_REVISION="null:"
33
 
CURRENT_REVISION="current:"
34
 
 
35
30
 
36
31
class Revision(object):
37
32
    """Single revision on a branch.
47
42
 
48
43
    properties
49
44
        Dictionary of revision properties.  These are attached to the
50
 
        revision as extra metadata.  The name must be a single
 
45
        revision as extra metadata.  The name must be a single 
51
46
        word; the value can be an arbitrary string.
52
47
    """
53
 
 
 
48
    
54
49
    def __init__(self, revision_id, properties=None, **args):
55
50
        self.revision_id = revision_id
56
 
        if properties is None:
57
 
            self.properties = {}
58
 
        else:
59
 
            self.properties = properties
60
 
            self._check_properties()
61
 
        self.committer = None
 
51
        self.properties = properties or {}
 
52
        self._check_properties()
62
53
        self.parent_ids = []
63
54
        self.parent_sha1s = []
64
55
        """Not used anymore - legacy from for 4."""
70
61
    def __eq__(self, other):
71
62
        if not isinstance(other, Revision):
72
63
            return False
 
64
        # FIXME: rbc 20050930 parent_ids are not being compared
73
65
        return (
74
66
                self.inventory_sha1 == other.inventory_sha1
75
67
                and self.revision_id == other.revision_id
77
69
                and self.message == other.message
78
70
                and self.timezone == other.timezone
79
71
                and self.committer == other.committer
80
 
                and self.properties == other.properties
81
 
                and self.parent_ids == other.parent_ids)
 
72
                and self.properties == other.properties)
82
73
 
83
74
    def __ne__(self, other):
84
75
        return not self.__eq__(other)
85
76
 
86
77
    def _check_properties(self):
87
 
        """Verify that all revision properties are OK."""
 
78
        """Verify that all revision properties are OK.
 
79
        """
88
80
        for name, value in self.properties.iteritems():
89
81
            if not isinstance(name, basestring) or contains_whitespace(name):
90
82
                raise ValueError("invalid property name %r" % name)
91
83
            if not isinstance(value, basestring):
92
 
                raise ValueError("invalid property value %r for %r" %
93
 
                                 (value, name))
 
84
                raise ValueError("invalid property value %r for %r" % 
 
85
                                 (name, value))
94
86
 
95
87
    def get_history(self, repository):
96
88
        """Return the canonical line-of-history for this revision.
113
105
 
114
106
    def get_summary(self):
115
107
        """Get the first line of the log message for this revision.
116
 
 
117
 
        Return an empty string if message is None.
118
 
        """
119
 
        if self.message:
120
 
            return self.message.lstrip().split('\n', 1)[0]
121
 
        else:
122
 
            return ''
123
 
 
124
 
    def get_apparent_authors(self):
125
 
        """Return the apparent authors of this revision.
126
 
 
127
 
        If the revision properties contain the names of the authors,
128
 
        return them. Otherwise return the committer name.
129
 
 
130
 
        The return value will be a list containing at least one element.
131
 
        """
132
 
        authors = self.properties.get('authors', None)
133
 
        if authors is None:
134
 
            author = self.properties.get('author', self.committer)
135
 
            if author is None:
136
 
                return []
137
 
            return [author]
138
 
        else:
139
 
            return authors.split("\n")
140
 
 
141
 
    def iter_bugs(self):
142
 
        """Iterate over the bugs associated with this revision."""
143
 
        bug_property = self.properties.get('bugs', None)
144
 
        if bug_property is None:
145
 
            return
146
 
        for line in bug_property.splitlines():
147
 
            try:
148
 
                url, status = line.split(None, 2)
149
 
            except ValueError:
150
 
                raise errors.InvalidLineInBugsProperty(line)
151
 
            if status not in bugtracker.ALLOWED_BUG_STATUSES:
152
 
                raise errors.InvalidBugStatus(status)
153
 
            yield url, status
 
108
        """
 
109
        return self.message.split('\n', 1)[0]
 
110
 
 
111
 
 
112
def is_ancestor(revision_id, candidate_id, branch):
 
113
    """Return true if candidate_id is an ancestor of revision_id.
 
114
 
 
115
    A false negative will be returned if any intermediate descendent of
 
116
    candidate_id is not present in any of the revision_sources.
 
117
    
 
118
    revisions_source is an object supporting a get_revision operation that
 
119
    behaves like Branch's.
 
120
    """
 
121
    return candidate_id in branch.repository.get_ancestry(revision_id)
154
122
 
155
123
 
156
124
def iter_ancestors(revision_id, revision_source, only_present=False):
165
133
                revision = revision_source.get_revision(ancestor)
166
134
            except errors.NoSuchRevision, e:
167
135
                if e.revision == revision_id:
168
 
                    raise
 
136
                    raise 
169
137
                else:
170
138
                    continue
171
139
            if only_present:
179
147
    """Return the ancestors of a revision present in a branch.
180
148
 
181
149
    It's possible that a branch won't have the complete ancestry of
182
 
    one of its revisions.
 
150
    one of its revisions.  
183
151
 
184
152
    """
185
153
    found_ancestors = {}
186
154
    anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
187
155
                         only_present=True))
188
156
    for anc_order, (anc_id, anc_distance) in anc_iter:
189
 
        if anc_id not in found_ancestors:
 
157
        if not found_ancestors.has_key(anc_id):
190
158
            found_ancestors[anc_id] = (anc_order, anc_distance)
191
159
    return found_ancestors
192
 
 
 
160
    
193
161
 
194
162
def __get_closest(intersection):
195
163
    intersection.sort()
196
 
    matches = []
 
164
    matches = [] 
197
165
    for entry in intersection:
198
166
        if entry[0] == intersection[0][0]:
199
167
            matches.append(entry[2])
200
168
    return matches
201
169
 
202
170
 
203
 
def is_reserved_id(revision_id):
204
 
    """Determine whether a revision id is reserved
205
 
 
206
 
    :return: True if the revision is reserved, False otherwise
207
 
    """
208
 
    return isinstance(revision_id, basestring) and revision_id.endswith(':')
209
 
 
210
 
 
211
 
def check_not_reserved_id(revision_id):
212
 
    """Raise ReservedId if the supplied revision_id is reserved"""
213
 
    if is_reserved_id(revision_id):
214
 
        raise errors.ReservedId(revision_id)
215
 
 
216
 
 
217
 
def ensure_null(revision_id):
218
 
    """Ensure only NULL_REVISION is used to represent the null revision"""
219
 
    if revision_id is None:
220
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
221
 
            ' revision instead of None, as of bzr 0.91.',
222
 
            DeprecationWarning, stacklevel=2)
223
 
        return NULL_REVISION
224
 
    else:
225
 
        return revision_id
226
 
 
227
 
 
228
 
def is_null(revision_id):
229
 
    if revision_id is None:
230
 
        symbol_versioning.warn('NULL_REVISION should be used for the null'
231
 
            ' revision instead of None, as of bzr 0.90.',
232
 
            DeprecationWarning, stacklevel=2)
233
 
    return revision_id in (None, NULL_REVISION)
 
171
def revision_graph(revision, revision_source):
 
172
    """Produce a graph of the ancestry of the specified revision.
 
173
    
 
174
    :return: root, ancestors map, descendants map
 
175
    """
 
176
    revision_source.lock_read()
 
177
    try:
 
178
        return _revision_graph(revision, revision_source)
 
179
    finally:
 
180
        revision_source.unlock()
 
181
 
 
182
 
 
183
def _revision_graph(revision, revision_source):
 
184
    """See revision_graph."""
 
185
    from bzrlib.tsort import topo_sort
 
186
    graph = revision_source.get_revision_graph(revision)
 
187
    # mark all no-parent revisions as being NULL_REVISION parentage.
 
188
    for node, parents in graph.items():
 
189
        if len(parents) == 0:
 
190
            graph[node] = [NULL_REVISION]
 
191
    # add NULL_REVISION to the graph
 
192
    graph[NULL_REVISION] = []
 
193
 
 
194
    # pick a root. If there are multiple roots
 
195
    # this could pick a random one.
 
196
    topo_order = topo_sort(graph.items())
 
197
    root = topo_order[0]
 
198
 
 
199
    ancestors = {}
 
200
    descendants = {}
 
201
 
 
202
    # map the descendants of the graph.
 
203
    # and setup our set based return graph.
 
204
    for node in graph.keys():
 
205
        descendants[node] = {}
 
206
    for node, parents in graph.items():
 
207
        for parent in parents:
 
208
            descendants[parent][node] = 1
 
209
        ancestors[node] = set(parents)
 
210
 
 
211
    assert root not in descendants[root]
 
212
    assert root not in ancestors[root]
 
213
    return root, ancestors, descendants
 
214
 
 
215
 
 
216
def combined_graph(revision_a, revision_b, revision_source):
 
217
    """Produce a combined ancestry graph.
 
218
    Return graph root, ancestors map, descendants map, set of common nodes"""
 
219
    root, ancestors, descendants = revision_graph(
 
220
        revision_a, revision_source)
 
221
    root_b, ancestors_b, descendants_b = revision_graph(
 
222
        revision_b, revision_source)
 
223
    if root != root_b:
 
224
        raise errors.NoCommonRoot(revision_a, revision_b)
 
225
    common = set()
 
226
    for node, node_anc in ancestors_b.iteritems():
 
227
        if node in ancestors:
 
228
            common.add(node)
 
229
        else:
 
230
            ancestors[node] = set()
 
231
        ancestors[node].update(node_anc)
 
232
    for node, node_dec in descendants_b.iteritems():
 
233
        if node not in descendants:
 
234
            descendants[node] = {}
 
235
        descendants[node].update(node_dec)
 
236
    return root, ancestors, descendants, common
 
237
 
 
238
 
 
239
def common_ancestor(revision_a, revision_b, revision_source, 
 
240
                    pb=DummyProgress()):
 
241
    if None in (revision_a, revision_b):
 
242
        return None
 
243
    # trivial optimisation
 
244
    if revision_a == revision_b:
 
245
        return revision_a
 
246
    try:
 
247
        try:
 
248
            pb.update('Picking ancestor', 1, 3)
 
249
            graph = revision_source.get_revision_graph_with_ghosts(
 
250
                [revision_a, revision_b])
 
251
            # convert to a NULL_REVISION based graph.
 
252
            ancestors = graph.get_ancestors()
 
253
            descendants = graph.get_descendants()
 
254
            common = set(graph.get_ancestry(revision_a)).intersection(
 
255
                     set(graph.get_ancestry(revision_b)))
 
256
            descendants[NULL_REVISION] = {}
 
257
            ancestors[NULL_REVISION] = []
 
258
            for root in graph.roots:
 
259
                descendants[NULL_REVISION][root] = 1
 
260
                ancestors[root].append(NULL_REVISION)
 
261
            for ghost in graph.ghosts:
 
262
                # ghosts act as roots for the purpose of finding 
 
263
                # the longest paths from the root: any ghost *might*
 
264
                # be directly attached to the root, so we treat them
 
265
                # as being such.
 
266
                # ghost now descends from NULL
 
267
                descendants[NULL_REVISION][ghost] = 1
 
268
                # that is it has an ancestor of NULL
 
269
                ancestors[ghost] = [NULL_REVISION]
 
270
                # ghost is common if any of ghosts descendants are common:
 
271
                for ghost_descendant in descendants[ghost]:
 
272
                    if ghost_descendant in common:
 
273
                        common.add(ghost)
 
274
                
 
275
            root = NULL_REVISION
 
276
            common.add(NULL_REVISION)
 
277
        except errors.NoCommonRoot:
 
278
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
279
            
 
280
        pb.update('Picking ancestor', 2, 3)
 
281
        distances = node_distances (descendants, ancestors, root)
 
282
        pb.update('Picking ancestor', 3, 2)
 
283
        farthest = select_farthest(distances, common)
 
284
        if farthest is None or farthest == NULL_REVISION:
 
285
            raise errors.NoCommonAncestor(revision_a, revision_b)
 
286
    finally:
 
287
        pb.clear()
 
288
    return farthest
 
289
 
 
290
 
 
291
class MultipleRevisionSources(object):
 
292
    """Proxy that looks in multiple branches for revisions."""
 
293
    def __init__(self, *args):
 
294
        object.__init__(self)
 
295
        assert len(args) != 0
 
296
        self._revision_sources = args
 
297
 
 
298
    def revision_parents(self, revision_id):
 
299
        for source in self._revision_sources:
 
300
            try:
 
301
                return source.revision_parents(revision_id)
 
302
            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
 
303
                pass
 
304
        raise e
 
305
 
 
306
    def get_revision(self, revision_id):
 
307
        for source in self._revision_sources:
 
308
            try:
 
309
                return source.get_revision(revision_id)
 
310
            except errors.NoSuchRevision, e:
 
311
                pass
 
312
        raise e
 
313
 
 
314
    def get_revision_graph(self, revision_id):
 
315
        # we could probe incrementally until the pending
 
316
        # ghosts list stop growing, but its cheaper for now
 
317
        # to just ask for the complete graph for each repository.
 
318
        graphs = []
 
319
        for source in self._revision_sources:
 
320
            ghost_graph = source.get_revision_graph_with_ghosts()
 
321
            graphs.append(ghost_graph)
 
322
        absent = 0
 
323
        for graph in graphs:
 
324
            if not revision_id in graph.get_ancestors():
 
325
                absent += 1
 
326
        if absent == len(graphs):
 
327
            raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
 
328
 
 
329
        # combine the graphs
 
330
        result = {}
 
331
        pending = set([revision_id])
 
332
        def find_parents(node_id):
 
333
            """find the parents for node_id."""
 
334
            for graph in graphs:
 
335
                ancestors = graph.get_ancestors()
 
336
                try:
 
337
                    return ancestors[node_id]
 
338
                except KeyError:
 
339
                    pass
 
340
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
341
        while len(pending):
 
342
            # all the graphs should have identical parent lists
 
343
            node_id = pending.pop()
 
344
            try:
 
345
                result[node_id] = find_parents(node_id)
 
346
                for parent_node in result[node_id]:
 
347
                    if not parent_node in result:
 
348
                        pending.add(parent_node)
 
349
            except errors.NoSuchRevision:
 
350
                # ghost, ignore it.
 
351
                pass
 
352
        return result
 
353
 
 
354
    def get_revision_graph_with_ghosts(self, revision_ids):
 
355
        # query all the sources for their entire graphs 
 
356
        # and then build a combined graph for just
 
357
        # revision_ids.
 
358
        graphs = []
 
359
        for source in self._revision_sources:
 
360
            ghost_graph = source.get_revision_graph_with_ghosts()
 
361
            graphs.append(ghost_graph.get_ancestors())
 
362
        for revision_id in revision_ids:
 
363
            absent = 0
 
364
            for graph in graphs:
 
365
                    if not revision_id in graph:
 
366
                        absent += 1
 
367
            if absent == len(graphs):
 
368
                raise errors.NoSuchRevision(self._revision_sources[0],
 
369
                                            revision_id)
 
370
 
 
371
        # combine the graphs
 
372
        result = Graph()
 
373
        pending = set(revision_ids)
 
374
        done = set()
 
375
        def find_parents(node_id):
 
376
            """find the parents for node_id."""
 
377
            for graph in graphs:
 
378
                try:
 
379
                    return graph[node_id]
 
380
                except KeyError:
 
381
                    pass
 
382
            raise errors.NoSuchRevision(self._revision_sources[0], node_id)
 
383
        while len(pending):
 
384
            # all the graphs should have identical parent lists
 
385
            node_id = pending.pop()
 
386
            try:
 
387
                parents = find_parents(node_id)
 
388
                for parent_node in parents:
 
389
                    # queued or done? 
 
390
                    if (parent_node not in pending and
 
391
                        parent_node not in done):
 
392
                        # no, queue
 
393
                        pending.add(parent_node)
 
394
                result.add_node(node_id, parents)
 
395
                done.add(node_id)
 
396
            except errors.NoSuchRevision:
 
397
                # ghost
 
398
                result.add_ghost(node_id)
 
399
                continue
 
400
        return result
 
401
 
 
402
    def lock_read(self):
 
403
        for source in self._revision_sources:
 
404
            source.lock_read()
 
405
 
 
406
    def unlock(self):
 
407
        for source in self._revision_sources:
 
408
            source.unlock()
 
409
 
 
410
 
 
411
@deprecated_function(zero_eight)
 
412
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
 
413
                              revision_history=None):
 
414
    """Find the longest line of descent from maybe_ancestor to revision.
 
415
    Revision history is followed where possible.
 
416
 
 
417
    If ancestor_id == rev_id, list will be empty.
 
418
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
419
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
420
    """
 
421
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
422
    if len(descendants) == 0:
 
423
        raise errors.NoSuchRevision(rev_source, rev_id)
 
424
    if ancestor_id not in descendants:
 
425
        rev_source.get_revision(ancestor_id)
 
426
        raise errors.NotAncestor(rev_id, ancestor_id)
 
427
    root_descendants = all_descendants(descendants, ancestor_id)
 
428
    root_descendants.add(ancestor_id)
 
429
    if rev_id not in root_descendants:
 
430
        raise errors.NotAncestor(rev_id, ancestor_id)
 
431
    distances = node_distances(descendants, ancestors, ancestor_id,
 
432
                               root_descendants=root_descendants)
 
433
 
 
434
    def best_ancestor(rev_id):
 
435
        best = None
 
436
        for anc_id in ancestors[rev_id]:
 
437
            try:
 
438
                distance = distances[anc_id]
 
439
            except KeyError:
 
440
                continue
 
441
            if revision_history is not None and anc_id in revision_history:
 
442
                return anc_id
 
443
            elif best is None or distance > best[1]:
 
444
                best = (anc_id, distance)
 
445
        return best[0]
 
446
 
 
447
    next = rev_id
 
448
    path = []
 
449
    while next != ancestor_id:
 
450
        path.append(next)
 
451
        next = best_ancestor(next)
 
452
    path.reverse()
 
453
    return path