StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>OK, so I'm having a similarly hard time reading the entirety of that patch, but let's see if I can piece it together from what I did figure out. </p> <p>To start with, gitk simplifies things by condensing a string of commits into an arc, containing a series of commits that each only have one parent and one child. Aside from anything else, doing this should cut down pretty dramatically on the number of nodes you have to consider for your sort, which will help out any algorithm you use. As a bonus, related commits will end up grouped together.</p> <p>This does introduce some complexity in terms of finding an arc when you read a new commit. There are a few situations:</p> <ul> <li>The new commit has a single parent, or no parents. It extends a (possibly empty) arc. Most of the time, you'll just extend the most recent arc. There are a few interesting subcases: <ul> <li>It may cause an existing arc to be split, if its parent already has a child (i.e. its parent turns out to be a branch point, which I gather you don't know ahead of time). </li> <li>It could be a "missing link" that connects two arcs together.</li> <li>You may already know that this commit has multiple children</li> </ul></li> <li>The new commit has multiple parents (a merge commit). </li> </ul> <p>You may want to include the multi-child or multi-parent commits in arcs, or it may make more sense to keep them separate. Either way, it shouldn't be too difficult to build up this set of arcs incrementally.</p> <p>Once you have these arcs, you're still left with trying to linearize them. In your case, the first algorithm described on the aforementioned <a href="http://en.wikipedia.org/wiki/Topological%5Fsorting" rel="nofollow noreferrer">Wikipedia page</a> sounds useful, as you have a known set of branch points to use as your initial set S.</p> <p>Other notes: </p> <ul> <li>Relocating commits should be manageable. First of all, you only have to care when you connect two arcs, either through a new merge commit, a newly-discovered branch point, or combining two arcs into one. Any given arc can easily maintain its current row number range (assuming you're fine with putting an arc on sequential rows), so traversing up the tree checking that all new ancestors show up later should be pretty quick. </li> <li>I don't know enough to say much about drawing the graph lines, but I imagine it won't be too different from what you do now.</li> </ul> <p>Anyway, I hope that helps. It was interesting to think about, at least.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload