[darcs-users] DRAFT Proposal: Navigating the space of versions using Tree hashes

[Eric Kow]

On Sat, Sep 04, 2010 at 02:11:22 -0700, Jason Dagit wrote:
> My comment about Zooko was based on my memory of this ticket:
> http://bugs.darcs.net/issue992
> 
> Here is a ticket about hashed contexts:
> http://bugs.darcs.net/issue1505

Thanks for posting the links!  Now that you have issue992 as background,
would you mind researching prior discussions to help us avoid covering
old ground?  Perhaps what would be most useful is a summary of proposals so far
(note the one by David) and what how your proposal differs from it.

Resources:

* issue992 itself
* search feature for #darcs logs:
    http://irclog.perlgeek.de/search.pl?channel=darcs&nick=&q=issue992
* maybe searching darcs-users for issue992

> He also pointed out that we need an official Rational Skeptic:
> http://wiki.darcs.net/Ideas#proposal-gauntlet

I don't think I was quite saying that, just pointing out that we do tend
to Grumpy Old Man new features (renamed for less cuteness and also to
make it less off-putting as you suggested).

> On Sat, Sep 4, 2010 at 12:47 AM, Jason Dagit <dagit at codersbase.com> wrote:
> > Hashed-storage provides us with a way to label pristine states.

As David observed in issue992, this mechanism also exists in the current
hashed inventory, and also in the tagged states.  Have a look both at the
inventory file and also one of the tags in _darcs/inventories).

In _darcs/hashed_inventory for darcs:
 pristine:7496cfa0b185a7fea872f92293c281126469c5de22046966ba63225bc1d4e6fc

In _darcs/inventories/0000001130-780dbc51d54cfd4934f16bffcfff38474b5dae0fccc94a4002dae3762df65109
 hash: 0000000189-8f314a7e7756daefaee188d9dce459af7a123f70b40092e14933d2604e49d84c
 
I'm not sure what the second hash corresponds to, if it's pristine or if
it's just the hash of the inventory contents, but in either case they
would both uniquely identify equivalent repository states, unless I
misunderstand.  If anybody finds out what the hash is in tag
subinventory files, maybe updating http://wiki.darcs.net/Hashes could be
a good idea

> And their darcs would do one of two things [3]:                                                                                      
>   1) Ideally recognize how to go from the currently active set and                                                                   
> order of patches to some other ordering and set of patches that                                                                      
> results in pristine state X.                                                                                                         
>   2) Tell me that X is unknown in this branch and that I likely need                                                                 
> patches that this branch has never seen before. 
 
Perhaps adding a bit more motivation to point #1, if I'm reading Zooko
on the ticket correctly, a typical use case for a short secure (fast)
version identifier is where

1. Alice gets an identifier from her repository

    alice $ darcs show state --repo alice-repo
    coffee0123456789abcdef

2. Alice tells Bob to get the version from the Central repo
   (centralness not essential here, just to help imagine).

   Email to Bob: Hey Bob, why don't you grab coffee0123456789abcdef
   from the central repository

3. Bob gets the repo as identified:

    bob $ darcs get http://example.com/central --state coffee0123456789abcdef

4. Now Bob and Alice know they have the same repo even though
   they didn't directly exchange any patches.

The trickiness is that Darcs repositories can often have patches in
different order from each other -- that's the whole point -- but I'm not
sure how important that is in practice.  I think a lot of the previous
discussion goes back into how to deal with this fact, and that minimal
contexts tend to come up.

Sorry, I haven't gotten around to reading the meat of your proposal yet.
Hopefully later :-)

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
For a faster response, try +44 (0)1273 64 2905 or
xmpp:kowey at jabber.fr (Jabber or Google Talk only)