← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

  • Committer: Robert Collins
  • Date: 2006-03-28 14:29:13 UTC
  • mto: (1626.2.1 integration)
  • mto: This revision was merged to the branch mainline in revision 1628.
  • Revision ID: robertc@robertcollins.net-20060328142913-ac5afb37075719c6
Convert log to use the new tsort.merge_sort routine.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
159
159
        return node_name
160
160
 
161
161
 
162
 
def merge_sort(graph, branch_tip):
 
162
def merge_sort(graph, branch_tip, mainline_revisions=None):
163
163
    """Topological sort a graph which groups merges.
164
164
 
165
165
    :param graph: sequence of pairs of node->parents_list.
166
166
    :param branch_tip: the tip of the branch to graph. Revisions not 
167
167
                       reachable from branch_tip are not included in the
168
168
                       output.
 
169
    :param mainline_revisions: If not None this forces a mainline to be
 
170
                               used rather than synthesised from the graph.
 
171
                               This must be a valid path through some part
 
172
                               of the graph. If the mainline does not cover all
 
173
                               the revisions, output stops at the start of the
 
174
                               old revision listed in the mainline revisions
 
175
                               list.
 
176
                               The order for this parameter is oldest-first.
169
177
 
170
178
    The result is a list of node names, such that all parents come before
171
179
    their children.
172
180
 
173
181
    node identifiers can be any hashable object, and are typically strings.
174
182
    """
175
 
    return MergeSorter(graph, branch_tip).sorted()
 
183
    return MergeSorter(graph, branch_tip, mainline_revisions).sorted()
176
184
 
177
185
 
178
186
class MergeSorter(object):
179
187
 
180
 
    def __init__(self, graph, branch_tip):
 
188
    def __init__(self, graph, branch_tip, mainline_revisions=None):
181
189
        """Merge-aware topological sorting of a graph.
182
190
    
183
191
        :param graph: sequence of pairs of node_name->parent_names_list.
185
193
                      For this input the output from the sort or
186
194
                      iter_topo_order routines will be:
187
195
                      'A', 'B', 'C'
 
196
        :param branch_tip: the tip of the branch to graph. Revisions not 
 
197
                       reachable from branch_tip are not included in the
 
198
                       output.
 
199
        :param mainline_revisions: If not None this forces a mainline to be
 
200
                               used rather than synthesised from the graph.
 
201
                               This must be a valid path through some part
 
202
                               of the graph. If the mainline does not cover all
 
203
                               the revisions, output stops at the start of the
 
204
                               old revision listed in the mainline revisions
 
205
                               list.
 
206
                               The order for this parameter is oldest-first.
 
207
 
188
208
        
189
209
        node identifiers can be any hashable object, and are typically strings.
190
210
 
267
287
        """
268
288
        # a dict of the graph.
269
289
        self._graph = dict(graph)
 
290
        # if there is an explicit mainline, alter the graph to match. This is
 
291
        # easier than checking at every merge whether we are on the mainline and
 
292
        # if so which path to take.
 
293
        if mainline_revisions is None:
 
294
            self._mainline_revisions = []
 
295
            self._stop_revision = None
 
296
        else:
 
297
            self._mainline_revisions = list(mainline_revisions)
 
298
            self._stop_revision = self._mainline_revisions[0]
 
299
        # skip the first revision, its what we reach and its parents are 
 
300
        # therefore irrelevant
 
301
        for index, revision in enumerate(self._mainline_revisions[1:]):
 
302
            # NB: index 0 means self._mainline_revisions[1]
 
303
            # if the mainline matches the graph, nothing to do.
 
304
            parent = self._mainline_revisions[index]
 
305
            if parent is None:
 
306
                # end of mainline_revisions history
 
307
                continue
 
308
            if self._graph[revision][0] == parent:
 
309
                continue
 
310
            # remove it from its prior spot
 
311
            self._graph[revision].remove(parent)
 
312
            # insert it into the start of the mainline
 
313
            self._graph[revision].insert(0, parent)
270
314
        # we need to do a check late in the process to detect end-of-merges
271
315
        # which requires the parents to be accessible: its easier for now
272
316
        # to just keep the original graph around.
273
 
        self._original_graph = dict(graph)
 
317
        self._original_graph = dict(self._graph.items())
274
318
        
275
319
        # this is a stack storing the depth first search into the graph.
276
320
        self._node_name_stack = []
376
420
        sequence_number = 0
377
421
        while self._scheduled_nodes:
378
422
            node_name, merge_depth = self._scheduled_nodes.pop()
 
423
            if node_name == self._stop_revision:
 
424
                return
379
425
            if not len(self._scheduled_nodes):
380
426
                end_of_merge = True
381
427
            elif self._scheduled_nodes[-1][1] < merge_depth: