From: A Large Angry SCM Date: Tue, 04 Jul 2006 06:41:50 GMT Subject: Re: [PATCH] Additional merge-base tests Message-ID: <44AA0DAE.1060308@gmail.com> In-Reply-To: <7v3bdhoraa.fsf@assigned-by-dhcp.cox.net> Junio C Hamano wrote: > A Large Angry SCM writes: > >> This demonstrates a problem with git-merge-base. >> >> +# Setup for second test set >> +# >> +# PL PR >> +# / \/ \ >> +# L2 C2 R2 >> +# | | | >> +# L1 C1 R1 >> +# | | | >> +# L0 C0 R0 >> +# \ | / >> +# S > > Cute. > > This is a good demonstration that merge-base may not give you > minimal set for pathological cases. If you want to be through > you could traverse everything to make sure we do not say 'S' is > relevant, but that is quite expensive, so I think there will > always be artifacts of horizon effect like this no matter how > you try to catch it (didn't I keep saying that already?). Not _that_ pathological in practice, given that you can't really depend on the timestamps in a distributed SCM. The problem is in mark_reachable_commits(); it is either superfluous or it needs to parse_commit() those commits that haven't been parsed yet that it needs to traverse. > However, I do not think it is really a "problem". At least what > "merge-base --all" did not miss any, that should be OK. The degree of the problem is, admittedly, situational. > I think the practical way to proceed is to say that the test > condition should really check that we do not _omit_ C2 in the > merge-base --all output. I do not believe that the (current) code will miss any bases but it can certainly return bases that are reachable from other bases.