Merged revisions in log

[Gustavo Niemeyer]

The attached patch adds support for showing merged revisions
in the log, and was built against the current newformat branch.

Here is an example of how it looks.

------------------------------------------------------------
revno: 2
committer: Gustavo Niemeyer <gustavo at niemeyer.net>
timestamp: Thu 2005-09-29 13:41:13 -0300
message:
  Merging file2 and file3, from repos2, into repos1.
  
    ------------------------------------------------------------
    merged: gustavo at niemeyer.net-20050929164020-03a1d6aafde5c9b7
    committer: Gustavo Niemeyer <gustavo at niemeyer.net>
    timestamp: Thu 2005-09-29 13:40:20 -0300
    message:
      Merging file3, from repos3, into repos2.
      
    ------------------------------------------------------------
    merged: gustavo at niemeyer.net-20050929163936-b5eb0a989f29a33d
    committer: Gustavo Niemeyer <gustavo at niemeyer.net>
    timestamp: Thu 2005-09-29 13:39:36 -0300
    message:
      Adding file3, on repos3.
      
    ------------------------------------------------------------
    merged: gustavo at niemeyer.net-20050929163846-4b1c341a976143cf
    committer: Gustavo Niemeyer <gustavo at niemeyer.net>
    timestamp: Thu 2005-09-29 13:38:46 -0300
    message:
      Added file2, on repos2.
      
------------------------------------------------------------
revno: 1
committer: Gustavo Niemeyer <gustavo at niemeyer.net>
timestamp: Thu 2005-09-29 13:37:58 -0300
message:
  Added file1, on repos1.
  

Enjoy!

-- 
Gustavo Niemeyer
http://niemeyer.net
-------------- next part --------------
=== modified file 'bzrlib/log.py'
--- bzrlib/log.py
+++ bzrlib/log.py
@@ -139,6 +139,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
@@ -172,6 +173,8 @@
     # list indexes are 0-based; revisions are 1-based
     cut_revs = which_revs[(start_revision-1):(end_revision)]
 
+    merged_revs = get_merged_revisions(cut_revs[-1][1], branch)
+
     if direction == 'reverse':
         cut_revs.reverse()
     elif direction == 'forward':
@@ -198,6 +201,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))
 
 
 
@@ -294,6 +301,8 @@
     def show(self, revno, rev, delta):
         raise NotImplementedError('not implemented in abstract base')
         
+    def show_merge(self, rev):
+        pass
 
 
 
@@ -330,6 +339,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
@@ -302,3 +302,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
+