← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-03-16 14:01:20 UTC
  • mfrom: (3280.2.5 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20080316140120-i3yq8yr1l66m11h7
Start 1.4 development

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