/b-gtk/fix-viz

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/b-gtk/fix-viz

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Robert Collins
  • Date: 2006-03-29 17:40:50 UTC
  • mto: (36.1.1 bzrk.jaq)
  • mto: This revision was merged to the branch mainline in revision 38.
  • Revision ID: robertc@robertcollins.net-20060329174050-46d95d48c9f61743
Make revision sorting and linking use merge_sorted from latest bzr.dev. This
gives a much nicer layout with features such as 'fully merged branches' not
being inappropriately shown as active - rather then point the branch is 
resurrected has its merge from mainline linked. This leads to a narrow,
more understandable view, and much less cross-hatch cases - perhaps none in 
fact.

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
12
12
 
13
13
 
14
14
from bzrlib.errors import NoSuchRevision
 
15
from bzrlib.tsort import merge_sort
15
16
 
16
17
 
17
18
class DummyRevision(object):
44
45
        self.direct_parent_of = {}
45
46
 
46
47
    def fill_caches(self):
 
48
        # FIXME: look at using repository.get_revision_graph_with_ghosts - RBC.
47
49
        branch = self.branch
48
50
        revisions = self.revisions
49
51
        todo = set([self.start])
86
88
                    for (revid, c) in self.children_of_id.iteritems())
87
89
 
88
90
    def first_ancestry_traversal(self):
 
91
        # make a revision graph:
 
92
        self.graph = {}
89
93
        distances = {}
90
94
        todo = [self.start]
91
95
        revisions = self.revisions
92
96
        children_of_id = self.children_of_id
93
97
        while todo:
94
98
            revid = todo.pop(0)
 
99
            self.graph[revid] = self.revisions[revid].parent_ids
95
100
            for child in children_of_id[revid]:
96
101
                if child.revision_id not in distances:
97
102
                    todo.append(revid)
104
109
        # Topologically sorted revids, with the most recent revisions first.
105
110
        # A revision occurs only after all of its children.
106
111
        self.distances = distances
 
112
        self.merge_sorted = merge_sort(self.graph, self.start)
107
113
        return sorted(distances, key=distances.get)
108
114
 
109
115
    def remove_redundant_parents(self, sorted_revids):
269
275
                self.colours[revid] = self.last_colour = self.last_colour + 1
270
276
 
271
277
 
272
 
def distances(branch, start, robust, accurate, maxnum):
 
278
def distances(branch, start, robust, maxnum):
273
279
    """Sort the revisions.
274
280
 
275
281
    Traverses the branch revision tree starting at start and produces an
285
291
        print 'robust filtering'
286
292
        distance.remove_redundant_parents(sorted_revids)
287
293
    children = distance.make_children_map()
288
 
    if accurate:
289
 
        print 'accurate sorting'
290
 
        sorted_revids = distance.sort_revisions(sorted_revids, maxnum)
291
 
    for revid in sorted_revids:
 
294
    sorted_revids = []
 
295
    
 
296
    for seq, revid, merge_depth, end_of_merge in distance.merge_sorted:
 
297
        sorted_revids.append(revid)
292
298
        distance.choose_colour(revid)
293
299
 
294
300
    if maxnum is not None:
295
301
        del sorted_revids[maxnum:]
 
302
        print 'FIXME: maxnum disabled.'
296
303
 
297
304
    revisions = distance.revisions
298
305
    colours = distance.colours
299
306
    parent_ids_of = distance.parent_ids_of
300
 
    return (sorted_revids, revisions, colours, children, parent_ids_of)
 
307
    return (revisions, colours, children, parent_ids_of, distance.merge_sorted)
301
308
 
302
 
def graph(revids, revisions, colours, parent_ids):
 
309
def graph(revisions, colours, parent_ids, merge_sorted):
303
310
    """Produce a directed graph of a bzr branch.
304
311
 
305
312
    For each revision it then yields a tuple of (revision, node, lines).
321
328
    It's up to you how to actually draw the nodes and lines (straight,
322
329
    curved, kinked, etc.) and to pick the actual colours for each index.
323
330
    """
324
 
    hanging = revids[:1]
325
 
    for revid in revids:
 
331
    if not len(merge_sorted):
 
332
        return
 
333
    # split merge_sorted into a map:
 
334
    revs = {}
 
335
    # FIXME: get a hint on this from the merge_sorted data rather than
 
336
    # calculating it ourselves
 
337
    # mapping from rev_id to the sequence number of the next lowest rev
 
338
    next_lower_rev = {}
 
339
    # mapping from rev_id to next-in-branch-revid - may be None for end
 
340
    # of branch
 
341
    next_branch_revid = {}
 
342
    # the stack we are in in the sorted data for determining which 
 
343
    # next_lower_rev to set. It is a stack which has one list at each
 
344
    # depth - the ids at that depth that need the same id allocated.
 
345
    current_stack = [[]]
 
346
    for seq, revid, indent, end_merge in merge_sorted:
 
347
        revs[revid] = (seq, indent, end_merge)
 
348
        if indent == len(current_stack):
 
349
            # new merge group starts
 
350
            current_stack.append([revid])
 
351
        elif indent == len(current_stack) - 1:
 
352
            # part of the current merge group
 
353
            current_stack[-1].append(revid)
 
354
        else:
 
355
            # end of a merge group
 
356
            while current_stack[-1]:
 
357
                stack_rev_id = current_stack[-1].pop()
 
358
                # record the next lower rev for this rev:
 
359
                next_lower_rev[stack_rev_id] = seq
 
360
                # if this followed a non-end-merge rev in this group note that
 
361
                if len(current_stack[-1]):
 
362
                    if not revs[current_stack[-1][-1]][2]:
 
363
                        next_branch_revid[current_stack[-1][-1]] = stack_rev_id
 
364
            current_stack.pop()
 
365
            # append to the now-current merge group
 
366
            current_stack[-1].append(revid)
 
367
    # assign a value to all the depth 0 revisions
 
368
    while current_stack[-1]:
 
369
        stack_rev_id = current_stack[-1].pop()
 
370
        # record the next lower rev for this rev:
 
371
        next_lower_rev[stack_rev_id] = len(merge_sorted)
 
372
        # if this followed a non-end-merge rev in this group note that
 
373
        if len(current_stack[-1]):
 
374
            if not revs[current_stack[-1][-1]][2]:
 
375
                next_branch_revid[current_stack[-1][-1]] = stack_rev_id
 
376
 
 
377
    # a list of the current revisions we are drawing lines TO indicating
 
378
    # the sequence of their lines on the screen.
 
379
    # i.e. [A, B, C] means that the line to A, to B, and to C are in
 
380
    # (respectively), 0, 1, 2 on the screen.
 
381
    hanging = [merge_sorted[0][1]]
 
382
    for seq, revid, indent, end_merge in merge_sorted:
 
383
        # a list of the lines to draw: their position in the
 
384
        # previous row, their position in this row, and the colour
 
385
        # (which is the colour they are routing to).
326
386
        lines = []
327
 
        node = None
328
387
 
329
388
        new_hanging = []
 
389
 
330
390
        for h_idx, hang in enumerate(hanging):
 
391
            # one of these will be the current lines node:
 
392
            # we are drawing a line. h_idx 
331
393
            if hang == revid:
332
 
                # We've matched a hanging revision, so need to output a node
333
 
                # at this point
 
394
                # we have found the current lines node
334
395
                node = (h_idx, colours[revid])
335
396
 
 
397
                # note that we might have done the main parent
 
398
                drawn_parents = set()
 
399
 
 
400
                def draw_line(from_idx, to_idx, revision_id):
 
401
                    try:
 
402
                        n_idx = new_hanging.index(revision_id)
 
403
                    except ValueError:
 
404
                        # force this to be vertical at the place this rev was
 
405
                        # drawn.
 
406
                        new_hanging.insert(to_idx, revision_id)
 
407
                        n_idx = to_idx
 
408
                    lines.append((from_idx, n_idx, colours[revision_id]))
 
409
 
 
410
                
 
411
                # we want to draw a line to the next commit on 'this' branch
 
412
                if not end_merge:
 
413
                    # drop this line first.
 
414
                    parent_id = next_branch_revid[revid]
 
415
                    draw_line(h_idx, h_idx, parent_id)
 
416
                    # we have drawn this parent
 
417
                    drawn_parents.add(parent_id)
 
418
                else:
 
419
                    # this is the last revision in a 'merge', show where it came from
 
420
                    if len(parent_ids[revisions[revid]]) > 1:
 
421
                        # having > 1
 
422
                        # parents means this commit was a merge, and being
 
423
                        # the end point of a merge group means that all
 
424
                        # the parent revisions were merged into branches
 
425
                        # to the left of this before this was committed
 
426
                        # - so we want to show this as a new branch from
 
427
                        # those revisions.
 
428
                        # to do this, we show the parent with the lowest
 
429
                        # sequence number, which is the one that this
 
430
                        # branch 'spawned from', and no others.
 
431
                        # If this sounds like a problem, remember that:
 
432
                        # if the parent was not already in our mainline
 
433
                        # it would show up as a merge into this making
 
434
                        # this not the end of a merge-line.
 
435
                        lowest = len(merge_sorted)
 
436
                        for parent_id in parent_ids[revisions[revid]]:
 
437
                            if revs[parent_id][0] < lowest:
 
438
                                lowest = revs[parent_id][0]
 
439
                        assert lowest != len(merge_sorted)
 
440
                        draw_line(h_idx, len(new_hanging), merge_sorted[lowest][1])
 
441
                        drawn_parents.add(merge_sorted[lowest][1])
 
442
                    elif len(parent_ids[revisions[revid]]) == 1:
 
443
                        # only one parent, must show this link to be useful.
 
444
                        parent_id = parent_ids[revisions[revid]][0]
 
445
                        draw_line(h_idx, len(new_hanging), parent_id)
 
446
                        drawn_parents.add(parent_id)
 
447
                
 
448
                # what do we want to draw lines to from here:
 
449
                # each parent IF its relevant.
 
450
                #
336
451
                # Now we need to hang its parents, we put them at the point
337
452
                # the old column was so anything to the right of this has
338
453
                # to move outwards to make room.  We also try and collapse
339
454
                # hangs to keep the graph small.
 
455
                # RBC: we do not draw lines to parents that were already merged
 
456
                # unless its the last revision in a merge group.
340
457
                for parent_id in parent_ids[revisions[revid]]:
341
 
                    try:
342
 
                        n_idx = new_hanging.index(parent_id)
343
 
                    except ValueError:
344
 
                        n_idx = len(new_hanging)
345
 
                        new_hanging.append(parent_id)
346
 
                    lines.append((h_idx, n_idx, colours[parent_id]))
 
458
                    if parent_id in drawn_parents:
 
459
                        continue
 
460
                    parent_seq = revs[parent_id][0]
 
461
                    parent_depth = revs[parent_id][1]
 
462
                    if parent_depth == indent + 1:
 
463
                        # the parent was a merge into this branch
 
464
                        # determine if it was already merged into the mainline
 
465
                        # via a different merge:
 
466
                        # if all revisions between us and parent_seq have a 
 
467
                        # indent greater than there are no revisions with a lower indent than
 
468
                        # us.
 
469
                        # we do not use 'parent_depth < indent' because that would allow
 
470
                        # un-uniqueified merges to show up, and merge_sorted should take
 
471
                        # care of that for us (but does not trim the values)
 
472
                        if parent_seq < next_lower_rev[revid]:
 
473
                            draw_line(h_idx, len(new_hanging), parent_id)
 
474
                    elif parent_depth == indent and parent_seq == seq + 1:
 
475
                        # part of this branch
 
476
                        draw_line(h_idx, len(new_hanging), parent_id)
347
477
            else:
348
 
                # Revision keeps on hanging, adjust for any change in the
349
 
                # graph shape and try to collapse hangs to keep the graph
350
 
                # small.
351
 
                try:
352
 
                    n_idx = new_hanging.index(hang)
353
 
                except ValueError:
354
 
                    n_idx = len(new_hanging)
355
 
                    new_hanging.append(hang)
356
 
                lines.append((h_idx, n_idx, colours[hang]))
 
478
                # draw a line from the previous position of this line to the 
 
479
                # new position.
 
480
                # h_idx is the old position.
 
481
                # new_indent is the new position. 
 
482
                draw_line(h_idx, len(new_hanging), hang)
 
483
        # we've calculated the row, assign new_hanging to hanging to setup for
 
484
        # the next row
357
485
        hanging = new_hanging
358
486
 
359
487
        yield (revisions[revid], node, lines)