/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: David Allouche
  • Date: 2006-05-08 12:36:08 UTC
  • mfrom: (37.1.3 trunk)
  • Revision ID: david.allouche@canonical.com-20060508123608-43014b1fbcc6ba23
[merge] lifeless graphing and performance improvements

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):
30
31
        self.message = self.revision_id
31
32
 
32
33
 
 
34
class RevisionProxy(object):
 
35
    """A revision proxy object.
 
36
 
 
37
    This will demand load the revision it represents when the committer or
 
38
    message attributes are accessed in order to populate them. It is 
 
39
    constructed with the revision id and parent_ids list and a repository
 
40
    object to request the revision from when needed.
 
41
    """
 
42
 
 
43
    def __init__(self, revid, parent_ids, repository):
 
44
        self.revision_id = revid
 
45
        self.parent_ids = parent_ids
 
46
        self._repository = repository
 
47
        self._revision = None
 
48
 
 
49
    def _get_attribute_getter(attr):
 
50
        def get_attribute(self):
 
51
            if self._revision is None:
 
52
                self._load()
 
53
            return getattr(self._revision, attr)
 
54
        return get_attribute
 
55
    committer = property(_get_attribute_getter('committer'))
 
56
    message = property(_get_attribute_getter('message'))
 
57
    properties = property(_get_attribute_getter('properties'))
 
58
    timestamp = property(_get_attribute_getter('timestamp'))
 
59
    timezone = property(_get_attribute_getter('timezone'))
 
60
 
 
61
    def _load(self):
 
62
        """Load the revision object."""
 
63
        self._revision = self._repository.get_revision(self.revision_id)
 
64
 
 
65
 
33
66
class DistanceMethod(object):
34
67
 
35
68
    def __init__(self, branch, start):
42
75
        self.colours = { start: 0 }
43
76
        self.last_colour = 0
44
77
        self.direct_parent_of = {}
 
78
        self.graph = {}
45
79
 
46
80
    def fill_caches(self):
47
 
        branch = self.branch
48
 
        revisions = self.revisions
49
 
        todo = set([self.start])
50
 
        while todo:
51
 
            revid = todo.pop()
52
 
            try:
53
 
                revision = branch.repository.get_revision(revid)
54
 
            except NoSuchRevision:
55
 
                revision = DummyRevision(revid)
56
 
            self.cache_revision(revid, revision)
57
 
            for parent_id in revision.parent_ids:
58
 
                if parent_id not in revisions:
59
 
                    todo.add(parent_id)
 
81
        # FIXME: look at using repository.get_revision_graph_with_ghosts - RBC.
 
82
        graph = self.branch.repository.get_revision_graph_with_ghosts([self.start])
 
83
        for revid in graph.ghosts:
 
84
            self.cache_revision(DummyRevision(revid))
 
85
        for revid, parents in graph.get_ancestors().items():
 
86
            self.cache_revision(RevisionProxy(revid, parents, self.branch.repository))
60
87
 
61
 
    def cache_revision(self, revid, revision):
 
88
    def cache_revision(self, revision):
62
89
        "Set the caches for a newly retrieved revision."""
 
90
        revid = revision.revision_id
63
91
        # Build a revision cache
64
92
        self.revisions[revid] = revision
65
 
        # Build a children dictionnary
 
93
        # Build a children dictionary
66
94
        for parent_id in revision.parent_ids:
67
95
            self.children_of_id.setdefault(parent_id, set()).add(revision)
68
96
        # Build a parents dictionnary, where redundant parents will be removed,
69
97
        # and that will be passed along tothe rest of program.
70
 
        if len(revision.parent_ids) == len(set(revision.parent_ids)):
71
 
            self.parent_ids_of[revision] = list(revision.parent_ids)
72
 
        else:
73
 
            # Remove duplicate parents
 
98
        if len(revision.parent_ids) != len(set(revision.parent_ids)):
 
99
            # fix the parent_ids list.
74
100
            parent_ids = []
75
101
            parent_ids_set = set()
76
102
            for parent_id in revision.parent_ids:
78
104
                    continue
79
105
                parent_ids.append(parent_id)
80
106
                parent_ids_set.add(parent_id)
81
 
            self.parent_ids_of[revision] = parent_ids
 
107
            revision.parent_ids = parent_ids
 
108
        self.parent_ids_of[revision] = list(revision.parent_ids)
 
109
        self.graph[revid] = revision.parent_ids
82
110
 
83
111
    def make_children_map(self):
84
112
        revisions = self.revisions
85
113
        return dict((revisions[revid], c)
86
114
                    for (revid, c) in self.children_of_id.iteritems())
87
115
 
88
 
    def first_ancestry_traversal(self):
89
 
        distances = {}
90
 
        todo = [self.start]
91
 
        revisions = self.revisions
92
 
        children_of_id = self.children_of_id
93
 
        while todo:
94
 
            revid = todo.pop(0)
95
 
            for child in children_of_id[revid]:
96
 
                if child.revision_id not in distances:
97
 
                    todo.append(revid)
98
 
                    break
99
 
            else:
100
 
                distances[revid] = len(distances)
101
 
                for parent_id in revisions[revid].parent_ids:
102
 
                    if parent_id not in todo:
103
 
                        todo.insert(0, parent_id)
104
 
        # Topologically sorted revids, with the most recent revisions first.
105
 
        # A revision occurs only after all of its children.
106
 
        self.distances = distances
107
 
        return sorted(distances, key=distances.get)
108
 
 
109
116
    def remove_redundant_parents(self, sorted_revids):
110
117
        children_of_id = self.children_of_id
111
118
        revisions = self.revisions
241
248
            self.colours[revid] = self.last_colour = self.last_colour + 1
242
249
 
243
250
    def choose_colour_many_children(self, revision, the_children):
244
 
        distances = self.distances
 
251
        """Colour revision revision."""
245
252
        revid = revision.revision_id
246
253
        direct_parent_of = self.direct_parent_of
247
254
        # multiple children, get the colour of the last displayed child
255
262
            if direct_parent == revision:
256
263
                self.colours[revid] = self.colours[child.revision_id]
257
264
                break
258
 
            if direct_parent is None:
259
 
                available[child] = distances[child.revision_id]
 
265
            # FIXME: Colouring based on whats been displayed MUST be done with 
 
266
            # knowledge of the revisions being output.
 
267
            # until the refactoring to fold graph() into this more compactly is
 
268
            # done, I've disabled this reuse. RBC 20060403
 
269
            # if direct_parent is None:
 
270
            #     available[child] = distances[child.revision_id] 
 
271
            #   .. it will be something like available[child] =  \
 
272
            #  revs[child.revision_id][0] - which is the sequence number
260
273
        else:
261
274
            if available:
262
275
                sorted_children = sorted(available, key=available.get)
269
282
                self.colours[revid] = self.last_colour = self.last_colour + 1
270
283
 
271
284
 
272
 
def distances(branch, start, robust, accurate, maxnum):
 
285
def distances(branch, start, robust, maxnum):
273
286
    """Sort the revisions.
274
287
 
275
288
    Traverses the branch revision tree starting at start and produces an
280
293
    """
281
294
    distance = DistanceMethod(branch, start)
282
295
    distance.fill_caches()
283
 
    sorted_revids = distance.first_ancestry_traversal()
284
296
    if robust:
285
297
        print 'robust filtering'
286
 
        distance.remove_redundant_parents(sorted_revids)
 
298
        distance.remove_redundant_parents(self.graph.keys())
 
299
    distance.merge_sorted = merge_sort(distance.graph, distance.start)
287
300
    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:
 
301
    
 
302
    for seq, revid, merge_depth, end_of_merge in distance.merge_sorted:
292
303
        distance.choose_colour(revid)
293
304
 
294
305
    if maxnum is not None:
295
 
        del sorted_revids[maxnum:]
 
306
        print 'FIXME: maxnum disabled.'
296
307
 
297
308
    revisions = distance.revisions
298
309
    colours = distance.colours
299
310
    parent_ids_of = distance.parent_ids_of
300
 
    return (sorted_revids, revisions, colours, children, parent_ids_of)
 
311
    return (revisions, colours, children, parent_ids_of, distance.merge_sorted)
301
312
 
302
 
def graph(revids, revisions, colours, parent_ids):
 
313
def graph(revisions, colours, merge_sorted):
303
314
    """Produce a directed graph of a bzr branch.
304
315
 
305
316
    For each revision it then yields a tuple of (revision, node, lines).
321
332
    It's up to you how to actually draw the nodes and lines (straight,
322
333
    curved, kinked, etc.) and to pick the actual colours for each index.
323
334
    """
324
 
    hanging = revids[:1]
325
 
    for revid in revids:
 
335
    if not len(merge_sorted):
 
336
        return
 
337
    # split merge_sorted into a map:
 
338
    revs = {}
 
339
    # FIXME: get a hint on this from the merge_sorted data rather than
 
340
    # calculating it ourselves
 
341
    # mapping from rev_id to the sequence number of the next lowest rev
 
342
    next_lower_rev = {}
 
343
    # mapping from rev_id to next-in-branch-revid - may be None for end
 
344
    # of branch
 
345
    next_branch_revid = {}
 
346
    # the stack we are in in the sorted data for determining which 
 
347
    # next_lower_rev to set. It is a stack which has one list at each
 
348
    # depth - the ids at that depth that need the same id allocated.
 
349
    current_stack = [[]]
 
350
    for seq, revid, indent, end_merge in merge_sorted:
 
351
        revs[revid] = (seq, indent, end_merge)
 
352
        if indent == len(current_stack):
 
353
            # new merge group starts
 
354
            current_stack.append([revid])
 
355
        elif indent == len(current_stack) - 1:
 
356
            # part of the current merge group
 
357
            current_stack[-1].append(revid)
 
358
        else:
 
359
            # end of a merge group
 
360
            while current_stack[-1]:
 
361
                stack_rev_id = current_stack[-1].pop()
 
362
                # record the next lower rev for this rev:
 
363
                next_lower_rev[stack_rev_id] = seq
 
364
                # if this followed a non-end-merge rev in this group note that
 
365
                if len(current_stack[-1]):
 
366
                    if not revs[current_stack[-1][-1]][2]:
 
367
                        next_branch_revid[current_stack[-1][-1]] = stack_rev_id
 
368
            current_stack.pop()
 
369
            # append to the now-current merge group
 
370
            current_stack[-1].append(revid)
 
371
    # assign a value to all the depth 0 revisions
 
372
    while current_stack[-1]:
 
373
        stack_rev_id = current_stack[-1].pop()
 
374
        # record the next lower rev for this rev:
 
375
        next_lower_rev[stack_rev_id] = len(merge_sorted)
 
376
        # if this followed a non-end-merge rev in this group note that
 
377
        if len(current_stack[-1]):
 
378
            if not revs[current_stack[-1][-1]][2]:
 
379
                next_branch_revid[current_stack[-1][-1]] = stack_rev_id
 
380
 
 
381
    # a list of the current revisions we are drawing lines TO indicating
 
382
    # the sequence of their lines on the screen.
 
383
    # i.e. [A, B, C] means that the line to A, to B, and to C are in
 
384
    # (respectively), 0, 1, 2 on the screen.
 
385
    hanging = [merge_sorted[0][1]]
 
386
    for seq, revid, indent, end_merge in merge_sorted:
 
387
        # a list of the lines to draw: their position in the
 
388
        # previous row, their position in this row, and the colour
 
389
        # (which is the colour they are routing to).
326
390
        lines = []
327
 
        node = None
328
391
 
329
392
        new_hanging = []
 
393
 
330
394
        for h_idx, hang in enumerate(hanging):
 
395
            # one of these will be the current lines node:
 
396
            # we are drawing a line. h_idx 
331
397
            if hang == revid:
332
 
                # We've matched a hanging revision, so need to output a node
333
 
                # at this point
 
398
                # we have found the current lines node
334
399
                node = (h_idx, colours[revid])
335
400
 
 
401
                # note that we might have done the main parent
 
402
                drawn_parents = set()
 
403
 
 
404
                def draw_line(from_idx, to_idx, revision_id):
 
405
                    try:
 
406
                        n_idx = new_hanging.index(revision_id)
 
407
                    except ValueError:
 
408
                        # force this to be vertical at the place this rev was
 
409
                        # drawn.
 
410
                        new_hanging.insert(to_idx, revision_id)
 
411
                        n_idx = to_idx
 
412
                    lines.append((from_idx, n_idx, colours[revision_id]))
 
413
 
 
414
                
 
415
                # we want to draw a line to the next commit on 'this' branch
 
416
                if not end_merge:
 
417
                    # drop this line first.
 
418
                    parent_id = next_branch_revid[revid]
 
419
                    draw_line(h_idx, h_idx, parent_id)
 
420
                    # we have drawn this parent
 
421
                    drawn_parents.add(parent_id)
 
422
                else:
 
423
                    # this is the last revision in a 'merge', show where it came from
 
424
                    if len(revisions[revid].parent_ids) > 1:
 
425
                        # having > 1
 
426
                        # parents means this commit was a merge, and being
 
427
                        # the end point of a merge group means that all
 
428
                        # the parent revisions were merged into branches
 
429
                        # to the left of this before this was committed
 
430
                        # - so we want to show this as a new branch from
 
431
                        # those revisions.
 
432
                        # to do this, we show the parent with the lowest
 
433
                        # sequence number, which is the one that this
 
434
                        # branch 'spawned from', and no others.
 
435
                        # If this sounds like a problem, remember that:
 
436
                        # if the parent was not already in our mainline
 
437
                        # it would show up as a merge into this making
 
438
                        # this not the end of a merge-line.
 
439
                        lowest = len(merge_sorted)
 
440
                        for parent_id in revisions[revid].parent_ids:
 
441
                            if revs[parent_id][0] < lowest:
 
442
                                lowest = revs[parent_id][0]
 
443
                        assert lowest != len(merge_sorted)
 
444
                        draw_line(h_idx, len(new_hanging), merge_sorted[lowest][1])
 
445
                        drawn_parents.add(merge_sorted[lowest][1])
 
446
                    elif len(revisions[revid].parent_ids) == 1:
 
447
                        # only one parent, must show this link to be useful.
 
448
                        parent_id = revisions[revid].parent_ids[0]
 
449
                        draw_line(h_idx, len(new_hanging), parent_id)
 
450
                        drawn_parents.add(parent_id)
 
451
                
 
452
                # what do we want to draw lines to from here:
 
453
                # each parent IF its relevant.
 
454
                #
336
455
                # Now we need to hang its parents, we put them at the point
337
456
                # the old column was so anything to the right of this has
338
457
                # to move outwards to make room.  We also try and collapse
339
458
                # hangs to keep the graph small.
340
 
                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]))
 
459
                # RBC: we do not draw lines to parents that were already merged
 
460
                # unless its the last revision in a merge group.
 
461
                for parent_id in revisions[revid].parent_ids:
 
462
                    if parent_id in drawn_parents:
 
463
                        continue
 
464
                    parent_seq = revs[parent_id][0]
 
465
                    parent_depth = revs[parent_id][1]
 
466
                    if parent_depth == indent + 1:
 
467
                        # the parent was a merge into this branch
 
468
                        # determine if it was already merged into the mainline
 
469
                        # via a different merge:
 
470
                        # if all revisions between us and parent_seq have a 
 
471
                        # indent greater than there are no revisions with a lower indent than
 
472
                        # us.
 
473
                        # we do not use 'parent_depth < indent' because that would allow
 
474
                        # un-uniqueified merges to show up, and merge_sorted should take
 
475
                        # care of that for us (but does not trim the values)
 
476
                        if parent_seq < next_lower_rev[revid]:
 
477
                            draw_line(h_idx, len(new_hanging), parent_id)
 
478
                    elif parent_depth == indent and parent_seq == seq + 1:
 
479
                        # part of this branch
 
480
                        draw_line(h_idx, len(new_hanging), parent_id)
347
481
            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]))
 
482
                # draw a line from the previous position of this line to the 
 
483
                # new position.
 
484
                # h_idx is the old position.
 
485
                # new_indent is the new position. 
 
486
                draw_line(h_idx, len(new_hanging), hang)
 
487
        # we've calculated the row, assign new_hanging to hanging to setup for
 
488
        # the next row
357
489
        hanging = new_hanging
358
490
 
359
491
        yield (revisions[revid], node, lines)