Merged revisions in log

[Gustavo Niemeyer]

> Not for me. I've attached the combined patch I used. 

As we discussed on IRC, the patch was not really incremental, so
it's my fault.

I'm attaching the full patch.

-- 
Gustavo Niemeyer
http://niemeyer.net
-------------- next part --------------
=== modified file 'bzrlib/log.py'
--- bzrlib/log.py
+++ bzrlib/log.py
@@ -154,6 +154,7 @@
     end_revision
         If not None, only show revisions <= end_revision
     """
+    from bzrlib.revision import get_merged_revisions
     from bzrlib.osutils import format_date
     from bzrlib.errors import BzrCheckError
     from bzrlib.textui import show_status
@@ -186,6 +187,11 @@
 
     # list indexes are 0-based; revisions are 1-based
     cut_revs = which_revs[(start_revision-1):(end_revision)]
+
+    if cut_revs:
+        merged_revs = get_merged_revisions(cut_revs[-1][1], branch)
+    else:
+        merged_revs = {}
 
     if direction == 'reverse':
         cut_revs.reverse()
@@ -213,6 +219,10 @@
                 continue
 
         lf.show(revno, rev, delta)
+
+        if rev_id in merged_revs:
+            for merged_rev_id in merged_revs[rev_id]:
+                lf.show_merge(branch.get_revision(merged_rev_id))
 
 
 
@@ -309,6 +319,9 @@
     def show(self, revno, rev, delta):
         raise NotImplementedError('not implemented in abstract base')
 
+    def show_merge(self, rev):
+        pass
+
     
 class LongLogFormatter(LogFormatter):
     def show(self, revno, rev, delta):
@@ -341,6 +354,32 @@
         if delta != None:
             delta.show(to_file, self.show_ids)
 
+    def show_merge(self, rev):
+        from osutils import format_date
+
+        to_file = self.to_file
+
+        indent = '    '
+
+        print >>to_file,  indent+'-' * 60
+        print >>to_file,  indent+'merged:', rev.revision_id
+        if self.show_ids:
+            for parent_id in rev.parent_ids:
+                print >>to_file, indent+'parent:', parent_id
+            
+        print >>to_file,  indent+'committer:', rev.committer
+
+        date_str = format_date(rev.timestamp,
+                               rev.timezone or 0,
+                               self.show_timezone)
+        print >>to_file,  indent+'timestamp: %s' % date_str
+
+        print >>to_file,  indent+'message:'
+        if not rev.message:
+            print >>to_file,  indent+'  (no message)'
+        else:
+            for l in rev.message.split('\n'):
+                print >>to_file,  indent+'  ' + l
 
 
 class ShortLogFormatter(LogFormatter):

=== modified file 'bzrlib/revision.py'
--- bzrlib/revision.py
+++ bzrlib/revision.py
@@ -298,3 +298,85 @@
         next = best_ancestor(next)
     path.reverse()
     return path
+
+
+def get_merged_revisions(revision_id, branch):
+    """
+    revision_id must be in the revision history of the given branch.
+
+    Suppose the following revision graph:
+    
+                F --- G
+              /         \ 
+       A --- B --- C --- D --- E
+        \         /     /
+          H --- I --- J
+           \         /
+            K ---- L
+
+    Considering that A, B, C, D, E are the only revisions present in
+    the revision history for the given branch, when queried on E
+    that function may return:
+
+    { C: [I, H], D: [G, F, J, L, K] }
+      
+    "may" because the order between G, F and J, L, K is not guaranteed.
+    """
+    history = branch.revision_history()
+    del history[history.index(revision_id)+1:]
+
+    skip = dict.fromkeys(history, True)
+
+    merged = {}
+
+    for hist_revision_id in history:
+
+        revision = branch.get_revision(hist_revision_id)
+
+        queue = []
+        for parent_id in revision.parent_ids:
+            if parent_id not in skip:
+                skip[parent_id] = True
+                queue.append((hist_revision_id, parent_id))
+
+        if not queue:
+            continue
+
+        # Reversed topological sorting of merged ids.
+        succ_num = {}
+        pred_ids = {}
+        while queue:
+
+            revision_id, parent_id = queue.pop()
+
+            try:
+                parent = branch.get_revision(parent_id)
+            except bzrlib.errors.NoSuchRevision:
+                continue
+
+            if revision_id in pred_ids:
+                pred_ids[revision_id].append(parent_id)
+            else:
+                pred_ids[revision_id] = [parent_id]
+            if parent_id in succ_num:
+                succ_num[parent_id] += 1
+            else:
+                succ_num[parent_id] = 1
+
+            for parent_parent_id in parent.parent_ids:
+                if parent_parent_id not in skip:
+                    skip[parent_parent_id] = True
+                    queue.append((parent_id, parent_parent_id))
+
+        revision_merged_ids = merged[hist_revision_id] = [hist_revision_id]
+
+        for revision_id in revision_merged_ids:
+            for parent_id in pred_ids.get(revision_id, ()):
+                succ_num[parent_id] -= 1
+                if not succ_num[parent_id]:
+                    revision_merged_ids.append(parent_id)
+
+        del revision_merged_ids[0]
+
+    return merged
+