From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Joshua Judson Rosen Newsgroups: gmane.emacs.devel Subject: Re: resolving ambiguity in action stamps Date: Fri, 12 Sep 2014 17:44:27 -0400 Message-ID: <87ioks4ipw.fsf@slice.rozzin.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> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1410558305 17847 80.91.229.3 (12 Sep 2014 21:45:05 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 12 Sep 2014 21:45:05 +0000 (UTC) Cc: Eli Zaretskii , Andreas Schwab , emacs-devel@gnu.org To: esr@thyrsus.com Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Sep 12 23:45:00 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 1XSYeJ-0005SU-Qy for ged-emacs-devel@m.gmane.org; Fri, 12 Sep 2014 23:44:59 +0200 Original-Received: from localhost ([::1]:47453 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XSYeJ-0007uO-GV for ged-emacs-devel@m.gmane.org; Fri, 12 Sep 2014 17:44:59 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47124) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XSYe2-0007l1-Ev for emacs-devel@gnu.org; Fri, 12 Sep 2014 17:44:46 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XSYdy-0001mi-6A for emacs-devel@gnu.org; Fri, 12 Sep 2014 17:44:42 -0400 Original-Received: from 209-20-69-211.slicehost.net ([209.20.69.211]:35167 helo=slice.rozzin.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XSYdp-0001m0-DE; Fri, 12 Sep 2014 17:44:29 -0400 Original-Received: by slice.rozzin.com (Postfix, from userid 1000) id 62947C8331; Fri, 12 Sep 2014 17:44:28 -0400 (EDT) In-Reply-To: <20140912204111.GA12328@thyrsus.com> (Eric S. Raymond's message of "Fri, 12 Sep 2014 16:41:12 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.4.x-2.6.x [generic] X-Received-From: 209.20.69.211 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:174258 Archived-At: "Eric S. Raymond" writes: > > Joshua Judson Rosen : > > Sorry--I mostly just wasn't paying close enough attention six months ago > > to point out all of the angles of this issue...; though I *did* raise > > this "ambiguity of reference by timestamp" issue at that time--and thought > > that you'd given an ACK with a statement you were going to fix it by using > > "#{sequence-number}" suffixes to distingiush between multiple distinct > > items in the same "{ISO-date}!{email-address}" hashbucket: > > > > https://lists.gnu.org/archive/html/emacs-devel/2014-01/msg01117.html > > > > https://lists.gnu.org/archive/html/emacs-devel/2014-01/msg01113.html > > > > (that first link is your response; the second is my message--which > > included an example of why the "same timestamps, different commit- > > objects" situation might exist in a repository) > > I remeber that. I thought I was going to fix it that way too. > > Then I found a showstopper. Possibly it has a solution I haven't found yet. > > The problem is this: suppose you have such a suffix, and several nodes > with the same date on a DAG. What's your rule for mapping suffix > to individual node? Hrm. I'd figured you were just going to assign sequence-numbers according to the order in which you encountered the commits in the git-fast-import stream, or reverse of the order in the git-fast-import stream, or something like that. It wasn't obvious to me how that would actually be usable in the _general_ case, but I guess I assumed you'd found it to be sufficient in practice, and/or that you had something up your sleeve that you hadn't explicitly mentioned (and wasn't really keenly intent on pressing the issue at the time). > I couldn't invent one. I believe this is mathematically equivalent to > total-ordering the DAG. Which you can't do. In the specific case that Andreas put forward (*commit* times in a single series incrementing more rapidly than their timestamp-precision could account for), I'd sort-of expect that to be workable with pretty good usability--the since commits along a single branch (as in a rebase) would seem to already have intrinsic sequencing with respect to each other. What I put forward in my example was the sort of case where I was skeptical of `*authorship* timestamp_bucket + seqno' being usable, but I also noted the possibility of that situation not existing in the emacs repository (if you don't actually encounter the general case, does it matter whether your algorithm handles it?). Have you actually found that sort of collision in the emacs DAG? Actually, I guess the nature (and relevance) of that last question changes if you're using *commit* timestamps rather and not *authorship* timestamps--like, maybe you only have to worry about the "rebase" situation that Andreas described, and _that_ can handled trivially? -- "'tis an ill wind that blows no minds."