More on this: This new idea is O(2N) in space. The previous idea was
O(N^2) in time. It seems to me that O(2N) is better.
But it gets better: An individual user can choose a different space-time
trade-off by keeping fewer of his own version of patches. For example,
you could keep the two versions of each patch only up to the most recent
tag, and for anything older only keep the original patches. And this is
a decision that can be left to the user.
Cheers,
Daniel.
Daniel Carrera wrote:
Here is another idea:
Darcs could store two copies of each patch: One in the form that the
initial author wrote it, and one adapted to the current context. The one
that is signed is the original. This is a space-time trade-off. We make
the repository twice as large, but signing and checking patches is O(1)
because we don't need to commute anything.
Here is an example:
1. Joel has repository ABCDE and creates patch F.
2. The patch F is hashed and signed, just the way Joel wrote it.
3. Jane has repository ABXY and pulls F from Joel.
4. Darcs verifies F without having to commute anything.
5. Darcs turns F into F' to apply it to Jane's context.
6. Darcs keeps both F and F' in the repository.
Later on, if Mike pulls that patch from Jane, he'll get F with its
signature. Notice that in general this system does not require more
bandwidth or more time to merge. In general, there is no reason to think
that F will be harder to apply than F'.
It might still be nice for the original author to compute the minimal
context of his patch, but I'm not sure what we would use this for.
What do you think?
Cheers,
Daniel.
_______________________________________________
darcs-users mailing list
[email protected]
http://lists.osuosl.org/mailman/listinfo/darcs-users
_______________________________________________
darcs-users mailing list
[email protected]
http://lists.osuosl.org/mailman/listinfo/darcs-users
