"Marco Costalba" <mcostalba@xxxxxxxxx> writes: > >> > >> A <--- tip of branch > >> / \ > >> B E > >> | | > >> | F > >> | / > >> C > >> | > >> D > >> ... > >> > > Ok. What about something like this? > A, B, C, D, E, (-3, 1)F > > where -3 is the correct position in sequence and 1 is the number of > revisions before F to whom apply the -3 rule. That means F knows who its descendants are, and commit objects do not have that information, so while traversing you need to keep track of all the descendants yourself, doesn't it? And how does that fix-up information help the user of the stream anyway? If I understand your model correctly, the model does not synchronously draw nodes as they are received, so it keeps track of what it has seen so far. When it sees F it can notice that its parent, C, is something it has seen, so it can tell F is wrong. It also knows that it has seen E and E's parent is F (which turned out to be at a wrong spot), so it can suspect E is also in the wrong spot (now, it is fuzzy to me how that chain of suspicion ends at E and does not propagate up to A, but let's think about that later). There is one thing that the user knows a lot better than the generic rev-list output part. It is the size of the output window (how tall the window is). I wonder if there is a way to exploit it, either in the user, or telling the size of the window (and perhaps where the display region at the top begins at) to rev-list... If we are dealing in a 3-item-tall window, we will traverse A B C D, notice they form a single strand of pearls, and can make a mental note that we do not have to worry about ancestors of D for now, because D's ancestors will be drawn below C, which is already the putative bottom edge of the window (when oddballs like E and F comes later, they can only push things down at the bottom edge of the window). Then rev-list can postpone traversing D and go on to traverse other nodes that are in the "active" list (in this case, E). I am starting to suspect that introducing "generation" header to the commit objects might actually be a very good thing. For one thing, rev-list will automatically get the topology always right if we did so. We obviously need to update 'convert-objects' and tell everybody that they need to rewrite their history if we take this route. That kind of flag-day conversion used to be an Ok thing to do, but it is getting harder and harder these days for obvious reasons, though. - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html