← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Alexander Belchenko
  • Date: 2007-01-30 12:13:18 UTC
  • mto: This revision was merged to the branch mainline in revision 2259.
  • Revision ID: bialix@ukr.net-20070130121318-a03bj0mol21o1rup
setup.py: fix plain 'python setup.py install' for win98

Show diffs side-by-side

added added

removed removed

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