Incorrect topological sorting

[nchaly]

Enountered an issue with Topological log rendering by latest version of ngit sources, built in VS 2010.

Given a simple history of two merged branches:

$ git log --graph --oneline
*   ba81db5 Merge branch 'new'
|\
| * 7f032bd Commit #5
| * fe2dd30 Commit #3
* | efda135 Commit #4
* | 116839d Commit #2
|/
* 089e538 commit #1

I'm trying to render it in the same way using NGit using the following code:

class Program
{
    static void Main(string[] args)
    {
        var r = new FileRepository(@"D:\temp\_git\.git");
        var headId = r.Resolve(Constants.HEAD);
        var rw = new RevWalk(r);
        rw.Sort(RevSort.TOPO);
        rw.MarkStart(rw.LookupCommit(headId));
        RevCommit c;
        while((c = rw.Next()) != null)
        {
            Console.WriteLine("{0}, {2}, {1}", c.Abbreviate(8).Name, c.GetShortMessage(), UnixTimeStampToDateTime(c.CommitTime));
        }
    }
    public static DateTime UnixTimeStampToDateTime(double unixTimeStamp)
    {
        // Unix timestamp is seconds past epoch
        var dtDateTime = new DateTime(1970, 1, 1, 0, 0, 0, 0);
        dtDateTime = dtDateTime.AddSeconds(unixTimeStamp).ToLocalTime();
        return dtDateTime;
    }
}

Which unexpectedly gives me commit-time ordering.

ba81db55, 3/8/2013 1:16:54 PM, Merge branch 'new'
7f032bdc, 3/8/2013 1:16:05 PM, Commit #5
efda135c, 3/8/2013 1:15:29 PM, Commit #4
fe2dd30d, 3/8/2013 1:14:58 PM, Commit #3
116839d4, 3/8/2013 1:13:52 PM, Commit #2
089e5381, 3/8/2013 1:12:54 PM, commit #1

Probably there is a known issue - anyway, please let me know if it would be fixed. (I'm going to use ngit for some automation, but topo-order is critical to me).

[nchaly]

Well - not sure if that's correct, but here is the patch which fixes it for me, but breaks PlotWalk tests:

From 2039d4886e23ab62e01370ce143c364afb6fecf0 Mon Sep 17 00:00:00 2001
From: Mikalai Chaly <mikalai_chaly@epam.com>
Date: Tue, 12 Mar 2013 00:28:03 +0300
Subject: [PATCH] Reimplement Topo sorting using stack

Functionality ported by default seemed not to be working: it actually
shown a list of commits ordered by commit date. Now parents should wait
in stack until all their children have been promoted to output queue.

Also, as topo-sorting can be broken by other sortings or rev-filters, it
seems that that TopoSortGenerator should be applied before any other
queue filters. And this exact patch can't be applied as is: it fixed my
needs with correct topological-sorting but breaks plot walk - probably
because of some functionality inferference, as I suppose, topo bugs had
been masked by additional implementation in PlotWalk classes. Judging by
http://wiki.eclipse.org/Image:Jgit-glog.png, event current jgit
implementation shows plot sorted by commit time.
---
 NGit/NGit.Revwalk/TopoSortGenerator.cs | 57 ++++++++++++++++------------------
 1 file changed, 27 insertions(+), 30 deletions(-)

diff --git a/NGit/NGit.Revwalk/TopoSortGenerator.cs b/NGit/NGit.Revwalk/TopoSortGenerator.cs
index d882fbd..c700264 100755
--- a/NGit/NGit.Revwalk/TopoSortGenerator.cs
+++ b/NGit/NGit.Revwalk/TopoSortGenerator.cs
@@ -54,6 +54,8 @@ namespace NGit.Revwalk

        private readonly FIFORevQueue pending;

+       private readonly LIFORevQueue work;
+       
        private readonly int outputType;

        /// <summary>Create a new sorter and completely spin the generator.</summary>
@@ -73,6 +75,8 @@ namespace NGit.Revwalk
        internal TopoSortGenerator(Generator s)
        {
            pending = new FIFORevQueue();
+           var temp = new FIFORevQueue();
+           work = new LIFORevQueue();
            outputType = s.OutputType() | SORT_TOPO;
            s.ShareFreeList(pending);
            for (; ; )
@@ -86,7 +90,19 @@ namespace NGit.Revwalk
                {
                    p.inDegree++;
                }
-               pending.Add(c);
+               temp.Add(c);
+           }
+           for (;;)
+           {
+               RevCommit c = temp.Next();
+               if (c == null)
+               {
+                   break;
+               }
+               if (c.inDegree == 0)
+               {
+                   work.Add(c);
+               }
            }
        }

@@ -105,38 +121,19 @@ namespace NGit.Revwalk
        /// <exception cref="System.IO.IOException"></exception>
        internal override RevCommit Next()
        {
-           for (; ; )
+           var commit = work.Next();
+           if (commit == null)
+               return null;
+           foreach (var parent in commit.Parents)
            {
-               RevCommit c = pending.Next();
-               if (c == null)
-               {
-                   return null;
-               }
-               if (c.inDegree > 0)
-               {
-                   // At least one of our children is missing. We delay
-                   // production until all of our children are output.
-                   //
-                   c.flags |= TOPO_DELAY;
+               if (parent.inDegree == 0)
                    continue;
-               }
-               // All of our children have already produced,
-               // so it is OK for us to produce now as well.
-               //
-               foreach (RevCommit p in c.parents)
-               {
-                   if (--p.inDegree == 0 && (p.flags & TOPO_DELAY) != 0)
-                   {
-                       // This parent tried to come before us, but we are
-                       // his last child. unpop the parent so it goes right
-                       // behind this child.
-                       //
-                       p.flags &= ~TOPO_DELAY;
-                       pending.Unpop(p);
-                   }
-               }
-               return c;
+               if(--parent.inDegree == 0)
+                   work.Add(parent);
            }
+
+           commit.inDegree = 0;
+           return commit;
        }
    }
 }
-- 
1.8.0