Re: [darcs-devel] [Revctrl] DARCS correctness question
On Thu, Jan 17, 2008 at 01:57:23PM +1100, William Uther wrote: > > If I have two Darcs workspaces, each of which have the same set of > patches, but in different orders, should these workspaces be > identical (even in the presence of conflicts)? The pristine trees should be, but the way the conflicts are marked in the working directory need not be. > # Now we'll check for differences in the result > cd .. > diff site2/myfile site3/myfile $ diff -q site2/myfile site3/myfile && echo OK Files site2/myfile and site3/myfile differ $ diff -q site2/_darcs/pristine/myfile site3/_darcs/pristine/myfile && echo OK OK Thanks Ian ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
Re: [darcs-devel] [Revctrl] DARCS correctness question
On 17/01/2008, at 11:45 PM, Ian Lynagh wrote: > On Thu, Jan 17, 2008 at 01:57:23PM +1100, William Uther wrote: >> >> If I have two Darcs workspaces, each of which have the same set of >> patches, but in different orders, should these workspaces be >> identical (even in the presence of conflicts)? > > The pristine trees should be, but the way the conflicts are marked in > the working directory need not be. In OT theory, a set of patches that are all transformed to apply should result in _identical_ output, regardless of order. If the output really is identical, then shouldn't the conflicts be marked up in the same way? My understanding from this that the merger patches are NOT identical. You claim that this isn't a problem - i.e. you seem to be claiming that merger patches do not need to obey the same correctness requirements as normal patches. Can you point me to a formal justification for this? Thanks, Will:-} ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
Re: [darcs-devel] [Revctrl] DARCS correctness question
On Fri, Jan 18, 2008 at 08:39:43AM +1100, William Uther wrote: > On 17/01/2008, at 11:45 PM, Ian Lynagh wrote: > > On Thu, Jan 17, 2008 at 01:57:23PM +1100, William Uther wrote: > >> If I have two Darcs workspaces, each of which have the same set of > >> patches, but in different orders, should these workspaces be > >> identical (even in the presence of conflicts)? > > > > The pristine trees should be, but the way the conflicts are marked in > > the working directory need not be. > > In OT theory, a set of patches that are all transformed to apply should > result in _identical_ output, regardless of order. If the output really > is identical, then shouldn't the conflicts be marked up in the same way? > My understanding from this that the merger patches are NOT identical. > > You claim that this isn't a problem - i.e. you seem to be claiming that > merger patches do not need to obey the same correctness requirements > as normal patches. Can you point me to a formal justification for this? The patches aren't identical because they're in a different order. It's perfectly normal in darcs that changes in different order are described by different patches--in fact it's the basis of the whole system. If you reorder the changes into the same order, then the patches are the same. Merger patches do obey precisely the same correctness requirements as any normal patches. The conflict marking does depend on the order of changes in the repository, but this doesn't really matter, since conflict-marking is not fundamental to how darcs works. It's something that's done to the working directory for the convenience of the user. We could remove this feature and darcs would be just as correct (although rather more awkward to use). -- David Roundy Department of Physics Oregon State University ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
Re: [darcs-devel] [Revctrl] DARCS correctness question
William Uther writes: > In OT theory, a set of patches that are all transformed to apply should > result in _identical_ output, regardless of order. If the output really > is identical, then shouldn't the conflicts be marked up in the same way? Why would you expect that? Merger markup expresses a superposition (hello, physicists!) of two texts; there's always a choice of order when serializing. > My understanding from this that the merger patches are NOT identical. The patches are the same, the notation is changed. That is, like most systems, darcs marks the conflicts like this: <<< status quo post patch applied first temporally atext atext === btext btext btext >> conflicting change due to patch applied second temporally not << changes proposed by patch earlier in some arbitrary but global order atext atext === btext btext btext >> changes proposed by patch later in some arbitrary but global order The latter will give consistent results, I think, but the former definitely will be nondeterministic. Doing this the way you expect *and* in a way that is easy for users to understand is hard, I suspect. For example, in git, Mercurial, or Darcs, you could just sort on some handy SHA1, but this would probably be confusing in the best of all possible world for the case of cherry- picking exactly one patch, because sometimes "mine" would appear on top and sometimes "yours" would appear on top, and the SHA1s are not human-meaningful. In the world we live in where most systems give status quo status to the patch applied to the repo earlier in temporal order, I'm sure it would disconcert most users. ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
Re: [darcs-devel] [Revctrl] DARCS correctness question
On 18/01/2008, at 10:09 AM, Stephen J. Turnbull wrote: > > William Uther writes: > >> In OT theory, a set of patches that are all transformed to apply >> should >> result in _identical_ output, regardless of order. If the output >> really >> is identical, then shouldn't the conflicts be marked up in the >> same way? > > Why would you expect that? Merger markup expresses a superposition > (hello, physicists!) of two texts; there's always a choice of order > when serializing. Well, in OT theory a large effort is made to make sure that the same serialization is made in all cases. It is a bug if different orders appear. >> My understanding from this that the merger patches are NOT identical. > > The patches are the same, the notation is changed. Ahh. I think that might have cleared up my confusion. Would it be correct to say that DARCS is versioning partially ordered text, and it is just choosing which total order to display to the user differently? > Doing this the way you expect *and* in a way that is easy for users to > understand is hard, I suspect. Good point. Cheers, Will :-} ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
Re: [darcs-devel] [Revctrl] DARCS correctness question
On 18/01/2008, at 8:57 AM, David Roundy wrote: > > On Fri, Jan 18, 2008 at 08:39:43AM +1100, William Uther wrote: >> On 17/01/2008, at 11:45 PM, Ian Lynagh wrote: >>> On Thu, Jan 17, 2008 at 01:57:23PM +1100, William Uther wrote: If I have two Darcs workspaces, each of which have the same set of patches, but in different orders, should these workspaces be identical (even in the presence of conflicts)? >>> >>> The pristine trees should be, but the way the conflicts are >>> marked in >>> the working directory need not be. >> >> In OT theory, a set of patches that are all transformed to apply >> should >> result in _identical_ output, regardless of order. If the output >> really >> is identical, then shouldn't the conflicts be marked up in the >> same way? >> My understanding from this that the merger patches are NOT identical. >> >> You claim that this isn't a problem - i.e. you seem to be claiming >> that >> merger patches do not need to obey the same correctness requirements >> as normal patches. Can you point me to a formal justification for >> this? > > The patches aren't identical because they're in a different order. > It's > perfectly normal in darcs that changes in different order are > described by > different patches--in fact it's the basis of the whole system. If you > reorder the changes into the same order, then the patches are the > same. Yes. But the resulting state after applying a series of patches should be the same, regardless of the order in which you've commuted the patches. > Merger patches do obey precisely the same correctness requirements > as any > normal patches. Ok. > The conflict marking does depend on the order of changes in the > repository, > but this doesn't really matter, since conflict-marking is not > fundamental > to how darcs works. It's something that's done to the working > directory > for the convenience of the user. We could remove this feature and > darcs > would be just as correct (although rather more awkward to use). Okie. I think I understand this better now after Stephen's response. Darcs' state is a partial order (represented using 'merger patches') and the particular way you serialise that for display is irrelevant. Thanks for the help, Will:-} ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
Re: [darcs-devel] [Revctrl] DARCS correctness question
William Uther writes: > > Why would you expect that? Merger markup expresses a superposition > > (hello, physicists!) of two texts; there's always a choice of order > > when serializing. > > Well, in OT theory a large effort is made to make sure that the same > serialization is made in all cases. It is a bug if different orders > appear. That's one way of proving that the result is correct (you'll get an empty diff). But there are other ways of doing it, and if you choose a particular serialization, you have to show that which serialization is chosen doesn't matter. > Ahh. I think that might have cleared up my confusion. Would it be > correct to say that DARCS is versioning partially ordered text, and it > is just choosing which total order to display to the user differently? I don't have a good feeling for that. It's a reasonable analogy, I suppose. ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
Re: [darcs-devel] [Revctrl] DARCS correctness question
David Roundy wrote: > The conflict marking does depend on the order of changes in the repository, > but this doesn't really matter, since conflict-marking is not fundamental > to how darcs works. It's something that's done to the working directory > for the convenience of the user. We could remove this feature and darcs > would be just as correct (although rather more awkward to use). Which reminds me - conflict markers are rather hard to use, because it's not clear which change comes from which patch, and unless I'm mistaken the order can vary from one file to another (perhaps even between hunks?). Also, you don't get to see the original version of the file before either patch. I'd like to see something like v v v v v v (original) foo === (patch A) bar === (patch B) baz === (patch C) wibble ^ ^ ^ ^ ^ ^ Cheers, Simon ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
Re: [darcs-devel] [Revctrl] DARCS correctness question
On Fri, Jan 18, 2008 at 01:43:11PM +, Simon Marlow wrote: > David Roundy wrote: > > The conflict marking does depend on the order of changes in the repository, > > but this doesn't really matter, since conflict-marking is not fundamental > > to how darcs works. It's something that's done to the working directory > > for the convenience of the user. We could remove this feature and darcs > > would be just as correct (although rather more awkward to use). > > Which reminds me - conflict markers are rather hard to use, because it's > not clear which change comes from which patch, and unless I'm mistaken the > order can vary from one file to another (perhaps even between hunks?). > Also, you don't get to see the original version of the file before either > patch. I'd like to see something like > > v v v v v v (original) > foo > === (patch A) > bar > === (patch B) > baz > === (patch C) > wibble > ^ ^ ^ ^ ^ ^ This would definitely be a very good improvement, but it's a bit of a pain to implement. :( We'd either have to rewrite the core patch types to track the names of primitive patches (a pain) or we'd have to go back searching even further through the history when marking up patches. I think the latter is the way to go, but the code involved is pretty ugly. -- David Roundy Department of Physics Oregon State University ___ darcs-devel mailing list darcs-devel@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-devel
