From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Eric S. Raymond" Newsgroups: gmane.emacs.devel Subject: Re: resolving ambiguity in action stamps (was: Everyone, please stop making my life more difficult) Date: Sat, 13 Sep 2014 01:35:26 -0400 Organization: Eric Conspiracy Secret Labs Message-ID: <20140913053525.GA15582@thyrsus.com> References: <20140912043652.4D6D8380604@snark.thyrsus.com> <83zje56ymd.fsf@gnu.org> <20140912083430.GA32586@thyrsus.com> <87mwa59i1r.fsf@igel.home> <20140912115739.GA3403@thyrsus.com> <87d2b19cbr.fsf@igel.home> <20140912155410.GA5086@thyrsus.com> <877g188uc3.fsf_-_@slice.rozzin.com> <20140912204111.GA12328@thyrsus.com> <87wq9841zx.fsf@uwakimon.sk.tsukuba.ac.jp> Reply-To: esr@thyrsus.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1410586551 1557 80.91.229.3 (13 Sep 2014 05:35:51 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 13 Sep 2014 05:35:51 +0000 (UTC) Cc: emacs-devel@gnu.org To: "Stephen J. Turnbull" Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Sep 13 07:35:46 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XSfzt-0002MO-MF for ged-emacs-devel@m.gmane.org; Sat, 13 Sep 2014 07:35:45 +0200 Original-Received: from localhost ([::1]:48564 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XSfzt-0002vo-81 for ged-emacs-devel@m.gmane.org; Sat, 13 Sep 2014 01:35:45 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45254) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XSfzj-0002vM-RR for emacs-devel@gnu.org; Sat, 13 Sep 2014 01:35:40 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XSfzb-0006BE-Aw for emacs-devel@gnu.org; Sat, 13 Sep 2014 01:35:35 -0400 Original-Received: from static-71-162-243-5.phlapa.fios.verizon.net ([71.162.243.5]:39684 helo=snark.thyrsus.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XSfzb-0006Ao-6c for emacs-devel@gnu.org; Sat, 13 Sep 2014 01:35:27 -0400 Original-Received: by snark.thyrsus.com (Postfix, from userid 1000) id 33F043805FC; Sat, 13 Sep 2014 01:35:26 -0400 (EDT) Content-Disposition: inline In-Reply-To: <87wq9841zx.fsf@uwakimon.sk.tsukuba.ac.jp> X-Eric-Conspiracy: There is no conspiracy User-Agent: Mutt/1.5.21 (2010-09-15) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 71.162.243.5 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:174263 Archived-At: Stephen J. Turnbull : > Eric S. Raymond writes: > > > I couldn't invent one. I believe this is mathematically equivalent > > to total-ordering the DAG. Which you can't do. > > You must have other conditions in mind for your allowable total > orders, since any finite partial order can be extended to a total > order (topological sort), usually in several ways. Not even the Emacs > repo has an uncountable number of revisions (although working with bzr > sometimes makes me feel like it does). Sorry, you're right. I should have said equivalent to the existence of a *unique* total ordering. The multiplicity of possible extended orders is the problem, not the solution. Look at it this way. For a suffix-numbering scheme to be useful, a browsing tool or anything else chasing references needs to converge on *the same ordering that you generated* using only the DAG topology - because it's not going to know, in particular, what order you encountered the commits in. /me puts on his "I used to be a mathematician..." hat... The problem admits of a unique solution if every clique of commits has the property that the minimal subgraph required to connect it is totally ordered. Think of the dates as node colors. Then, in this graph: A <-- B <-- C <-- B <-- D we can number uniquely as A <-- B1 <-- C <-- B2 <-- D based on the parent-of ordering. Then there's this case: A <-- B1 <-- C <-- B2 <-- D \ +--- E <-- F We can still uniquely order B1 and B2 because the minimal subgraph that joins them is totally ordered. The problem case is this: A <-- B <-- C <-- B <-- D \ +--- B <-- E <- F In this the minimal subgraph joining the clique is not totally ordered, so we don't know how to uniquely order the Bs on the branches. To solve this problem we need a unique order relation on the branch heads. If branches had immutable names that would imply one, but we can't assume that. Possibly there's a solution here using a constraint particular to VCSes that I haven't taken into account, and someone cleverer than me will notice. That would be nice. -- Eric S. Raymond