[darcs-devel] Rebase implementation: patch vs. repo level

[Ben Franksen]

[I reorder your replies]

Ganesh Sittampalam wrote:
>> Now to a related question:
>> 
>> Am I right that implementing rebase on the repo level would mean adding
>> yet another phantom type to Repository, something like
>> 
>> data Repository (p :: * -> * -> *)
>>   wRecordedstate wUnrecordedstate wTentativestate wRebasestate
> 
> Hmm. To be honest I'm not sure, but I guess so. Or maybe we don't really
> care about the "end" of the rebase state because most operations happen
> at the beginning of the state where it meets up with the main
> repository, in which case we don't need a new witness at all.

Yes, the thought occurred to me, too.

>> ? Or do we need two new states in order to also represent the "fixup"
>> needed to adapt the rebase patches to new records or pulls (or even just
>> modifications of the working tree, not sure if that is needed). And the
>> list of patches that makes up the rebase state, where would it start? At
>> the wTentativestate or at wUnrecordedstate or even at wRecordedstate?
> 
> I think it would start at wTentativeState. I don't think we would need a
> witness for the fixups specially, that's already handled by them being
> interleaved in a list along with the suspended patches.

Okay. I thought they are lumped together in one place, presumably at the 
front of the rebase list.

>> One thing I do not understand about the Repository witnesses: I may have
>> a wrong understanding of what "tentative" means, but judging from the
>> comment
>> 
>> -- the recorded state of the repository (i.e. what darcs get would
>> retrieve),
>> -- the unrecorded state (what's in the working directory now),
>> -- and the tentative state, which represents work in progress that will
>> -- eventually become the new recorded state unless something goes wrong.
>> 
>> shouldn't wUnrecordedstate and wTentativestate always be equal whenever
>> we start executing a command and be again equal when we finish with it?
>> And if yes, could we perhaps express this more directly in the types of
>> the functions involved?
> 
> Yes, that's right, assuming you meant wRecordedState and wTentativeState.

I didn't mean it, but now that you say it I understand my mistake. So a Repo 
r u t (in simplified Notation), means (ascii art, use a monospaced font to 
view):

         --> u
       /
s --> r
       \
         --> t

instead of

s --> r --> u --> t.

> You can see this in the type of the constructors of
> 'Darcs.Repository.Job.RepoJob', e.g:
> 
>       RepoJob (forall p wR wU . (RepoPatch p, ApplyState p ~ Tree,
> ApplyState (PrimOf p) ~ Tree)
>                => Repository p wR wU wR -> IO a)

Nice. So it's actually done this way.

> I think Darcs.Repository.Internal.finalizeRepositoryChanges and
> D.R.I.revertRepositoryChanges also re-establish this invariant, but
> because they take the starting state as a parameter and the ending state
> isn't explicit, you can't see that in the type.
> 
> The basic point of 'tentative' is to allow for atomic changes to the
> repository - if an operation aborts halfway, the repo isn't left in a
> half-done state.

Understood this now. Thanks for explaining.

> The main technical difficulty is simply tracking whether the patches
> being rebased have been "affected" or not. This is actually quite
> subtle; for example if patch B depends on patch A and patch A changes
> identity, then B has to too [modulo the darcs-2 duplicates hackery that
> means you can sometimes cheat the system, but we're both agreed that's a
> misfeature].
> 
> So concretely, for example if B is suspended and you amend-record A
> that's still in the main repository, you now need to check whether B
> actually depended on A, presumably by doing a test commute. There are
> lots of other cases like this to track, and while I think this could all
> be done in theory, it feels hard to do reliably in practice. Also, users
> might be intending not to change the identity of their patches and be
> surprised by some dependency.

I wonder about this. My initial take would be: whenever we add a patch to 
the main repo, we also add its inverse to the front of the rebase list, then 
try to commute it as far as possible to the right. If we reach the end we 
can drop it and know that nothing needs to be amended. If not, we have a 
conflict and can warn the user that the rebase patch where the commute 
failed (and perhaps some of those which follow it) may have to be amended. 
Wouldn't that work?

Cheers
Ben
-- 
"Make it so they have to reboot after every typo." ― Scott Adams