From mboxrd@z Thu Jan 1 00:00:00 1970 From: Mike Hommey Subject: Re: Is there interest in a n-sect tool? Date: Mon, 18 Jan 2016 18:01:22 +0900 Message-ID: <20160118090122.GB15642@glandium.org> References: <20160118075653.GA13911@glandium.org> <20160118085835.GA15642@glandium.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: git@vger.kernel.org To: Junio C Hamano X-From: git-owner@vger.kernel.org Mon Jan 18 10:01:32 2016 Return-path: Envelope-to: gcvg-git-2@plane.gmane.org Received: from vger.kernel.org ([209.132.180.67]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1aL5gp-0007sa-4s for gcvg-git-2@plane.gmane.org; Mon, 18 Jan 2016 10:01:31 +0100 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753808AbcARJB2 (ORCPT ); Mon, 18 Jan 2016 04:01:28 -0500 Received: from ns332406.ip-37-187-123.eu ([37.187.123.207]:36526 "EHLO glandium.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752001AbcARJB1 (ORCPT ); Mon, 18 Jan 2016 04:01:27 -0500 Received: from glandium by zenigata with local (Exim 4.86) (envelope-from ) id 1aL5gg-00048V-5D; Mon, 18 Jan 2016 18:01:22 +0900 Content-Disposition: inline In-Reply-To: <20160118085835.GA15642@glandium.org> X-GPG-Fingerprint: 182E 161D 1130 B9FC CD7D B167 E42A A04F A6AA 8C72 User-Agent: Mutt/1.5.24 (2015-08-30) Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Archived-At: On Mon, Jan 18, 2016 at 05:58:35PM +0900, Mike Hommey wrote: > On Mon, Jan 18, 2016 at 12:43:35AM -0800, Junio C Hamano wrote: > > Mike Hommey writes: > > > > > - I have a script that, for a given git-cinnabar commit, clones > > > those four mercurial repositories, and determines a global state > > > for the resulting repositories. (for example, the sha1sum of all > > > the sha1s of the remote refs for all repositories) > > > - The script is run for the earliest commit and gives a sha1. > > > - Then I bisect run with a script wrapping the other, returning 0 > > > when the state is the same as the one for the earliest commit, > > > or 1 otherwise. > > > - The result of that first bisection is the first state change. > > > - Then I bisect run again, using the state of the result of that first > > > bisect instead of the earliest commit. > > > - The result of that second bisection is the second state change. > > > - And so on... > > > > > > I do, in fact, cache the states for each iteration of each bisect, > > > so that I can do some smarter decisions than just start from the last > > > bisection for the next one. > > > > > > I don't have that many state changes to track, but I do have different > > > kind of states that I want to track down, so I will be running this > > > a couple more times. > > > > > > The question is, is there sufficient interest in a generic n-sect tool > > > for me to justify spending the time to do it properly, vs. just doing > > > the minimalist thing I did to make it work for my use case. > > > > After reading the above a few times, I still am not sure what you > > mean by n-sect (as opposed to bi-sect), especially given that you > > sounded as if you consider the straight "bisect" is about having > > only two states, bad/good, new/old, or black/white. "Bi" in the > > word "bisect" refers to the search going by dividing the space into > > two to find state transition, and does not necessarily mean there > > are two states (hence implying a single state transition between the > > two). If you have three states, black/gray/white, that linearly > > transitions states twice (i.e. one part of the history is > > continuously black, and at one boundary it turns gray and continues > > to be gray, until at another boundary it turns white and continues > > to be white to the other end), you would still "bi"-sect to find > > these two transition points. You start from a black A and a white > > Z, pick a midpoint M that tests to be gray and know the transition > > point from black to gray exists somewhere between A and M, while the > > other transision point from gray to white exists somewhere between M > > and Z. Is that the kind of search you are talking about? > > Yes, it is. Somehow, I was thinking of the result once you're done > bisecting, not the process itself of cutting history in two parts. Let me add that in my use case, I don't know how many states there are when I start. I only know there are at least two. Mike