On Sat, 1 Jul 2006, Linus Torvalds wrote: > On Sat, 1 Jul 2006, Daniel Barkalow wrote: > > > > I think a...b can be computed by (in pseudocode, obviously): > > Nope. > > > It's basically the original merge-bases code, from way back; > > And it has basically the same bug. > > It is possible to have > > a > / \ > b c > |\ /| > d e f > \|/ > g > > and clearly "e" is the only valid merge-base of b and c. > > HOWEVER. It's actually possible that we traverse d, f and g before we even > look at 'e' (because somebody had a bogus date, and 'e' _looks_ old). But that wouldn't actually affect b...c, because we don't actually care that 'e' is the correct merge-base and 'g' is not, because "b c ^e ^g" is the same as "b c ^e". Your point is correct, though; if we look at e before c, we could think that it's interesting when it isn't, so we have to wait until we've drained the list to output anything. > So that's why git-merge-base has all that extra "unnecessary" complexity. > You cannot output anything at all until you've guaranteed that all pending > objects are uninteresting. That's not all the complexity in git-merge-base, though. There's a ton more that's about why e is right and g is wrong in your example, and we don't care about *that* part in b...c. Actually, I think that it would work to have object flags "LEFT" and "RIGHT", mark b with left, mark c with right, and mark anything with both LEFT and RIGHT as UNINTERESTING as we go through the revisions. The time-ordering problem with symmetric difference isn't absent with regular difference, and, assuming that b..c works in the tricky cases, the same logic should handle symmetric difference. -Daniel *This .sig left intentionally blank* - : 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