From: "Eric S. Raymond" <esr@thyrsus.com>
To: "Stephen J. Turnbull" <stephen@xemacs.org>
Cc: emacs-devel@gnu.org
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 [thread overview]
Message-ID: <20140913053525.GA15582@thyrsus.com> (raw)
In-Reply-To: <87wq9841zx.fsf@uwakimon.sk.tsukuba.ac.jp>
Stephen J. Turnbull <stephen@xemacs.org>:
> 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.
--
<a href="http://www.catb.org/~esr/">Eric S. Raymond</a>
next prev parent reply other threads:[~2014-09-13 5:35 UTC|newest]
Thread overview: 83+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-09-12 4:36 Everyone, please stop making my life more difficult Eric S. Raymond
2014-09-12 6:08 ` Eli Zaretskii
2014-09-12 9:55 ` Eric S. Raymond
2014-09-12 10:33 ` Eli Zaretskii
2014-09-12 10:49 ` Gregor Zattler
2014-09-12 13:05 ` Eli Zaretskii
2014-09-12 13:19 ` David Kastrup
2014-09-12 13:29 ` Eli Zaretskii
2014-09-12 13:55 ` Andreas Schwab
2014-09-12 14:12 ` Eli Zaretskii
2014-09-12 15:17 ` Eli Zaretskii
2014-09-12 15:21 ` Andreas Schwab
2014-09-12 17:15 ` Eli Zaretskii
2014-09-12 17:43 ` Andreas Schwab
2014-09-12 15:53 ` David Kastrup
2014-09-12 17:22 ` Eli Zaretskii
2014-09-12 19:28 ` David Kastrup
2014-09-12 19:59 ` Eli Zaretskii
2014-09-12 13:57 ` David Kastrup
2014-09-12 14:26 ` Eli Zaretskii
2014-09-12 11:38 ` Eric S. Raymond
2014-09-12 13:14 ` Eli Zaretskii
2014-09-12 16:27 ` Eric S. Raymond
2014-09-12 11:46 ` Harald Hanche-Olsen
2014-09-12 13:56 ` Paul Eggert
2014-09-12 15:08 ` Barry Warsaw
2014-09-12 16:16 ` Eric S. Raymond
2014-09-12 6:47 ` Thien-Thi Nguyen
2014-09-12 7:25 ` David Kastrup
2014-09-12 9:34 ` Thien-Thi Nguyen
2014-09-12 8:18 ` Eli Zaretskii
2014-09-12 8:34 ` Eric S. Raymond
2014-09-12 8:40 ` Eric S. Raymond
2014-09-12 11:47 ` Andreas Schwab
2014-09-12 11:57 ` Eric S. Raymond
2014-09-12 12:17 ` David Kastrup
2014-09-12 13:51 ` Andreas Schwab
2014-09-12 15:54 ` Eric S. Raymond
2014-09-12 16:04 ` David Kastrup
2014-09-12 16:18 ` Andreas Schwab
2014-09-12 16:28 ` Eric S. Raymond
2014-09-12 16:43 ` David Kastrup
2014-09-12 20:19 ` resolving ambiguity in action stamps (was: Everyone, please stop making my life more difficult) Joshua Judson Rosen
2014-09-12 20:41 ` Eric S. Raymond
2014-09-12 21:44 ` resolving ambiguity in action stamps Joshua Judson Rosen
2014-09-13 3:45 ` resolving ambiguity in action stamps (was: Everyone, please stop making my life more difficult) Stephen J. Turnbull
2014-09-13 5:35 ` Eric S. Raymond [this message]
2014-09-13 6:57 ` Stephen J. Turnbull
2014-09-13 7:26 ` resolving ambiguity in action stamps Harald Hanche-Olsen
2014-09-13 10:50 ` Eric S. Raymond
2014-09-13 12:43 ` Yuri Khan
2014-09-14 7:34 ` Stephen J. Turnbull
2014-09-14 10:55 ` Eric S. Raymond
2014-09-14 11:03 ` David Kastrup
2014-09-14 13:30 ` Stephen J. Turnbull
2014-09-14 14:06 ` David Kastrup
2014-09-14 15:51 ` Stephen J. Turnbull
2014-09-14 14:21 ` Eric S. Raymond
2014-09-14 15:45 ` Stephen J. Turnbull
2014-09-14 15:59 ` David Kastrup
2014-09-14 17:12 ` Eric S. Raymond
2014-09-15 0:09 ` Stephen J. Turnbull
2014-09-13 8:51 ` Andreas Schwab
2014-09-12 14:12 ` Everyone, please stop making my life more difficult Sam Steingold
2014-09-12 14:36 ` David Kastrup
2014-09-12 14:44 ` Yuri Khan
2014-09-12 15:24 ` Sam Steingold
2014-09-12 15:59 ` David Kastrup
2014-09-12 16:12 ` Eric S. Raymond
2014-09-12 17:06 ` Stefan Monnier
2014-09-12 20:35 ` Thien-Thi Nguyen
2014-09-12 15:21 ` Sam Steingold
2014-09-12 15:34 ` Harald Hanche-Olsen
2014-09-12 15:51 ` David Kastrup
2014-09-12 17:44 ` Stephen J. Turnbull
2014-09-12 17:58 ` David Caldwell
2014-09-12 19:19 ` Stephen J. Turnbull
2014-09-12 18:01 ` Harald Hanche-Olsen
2014-09-12 19:36 ` Joshua Judson Rosen
2014-10-28 21:11 ` Randal L. Schwartz
2014-09-12 15:30 ` Phillip Lord
2014-09-12 15:57 ` David Kastrup
2014-09-12 17:10 ` Stefan Monnier
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20140913053525.GA15582@thyrsus.com \
--to=esr@thyrsus.com \
--cc=emacs-devel@gnu.org \
--cc=stephen@xemacs.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.