darcs

Issue 346 implement "patience diff" from bzr

Title implement "patience diff" from bzr
Priority feature Status resolved
Milestone Resolved in 2.10.0 HEAD
Superseder Nosy List darcs-devel, dmitry.kurochkin, jlneder, kowey, marcot, markstos, thorkilnaur, tommy
Assigned To
Topics

Created on 2006-11-13.23:39:13 by beschmi, last changed 2013-10-10.15:08:01 by noreply.

Messages
msg1214 (view) Author: beschmi Date: 2006-11-13.23:39:08
Please attach all examples for this behaviour with a small explanation of the
desired output or the diff produced by other SCMs to this bug.
msg3507 (view) Author: markstos Date: 2008-02-16.19:10:42
I'm closing this bug from 2006 due to lack of activity on it on the part of both
developers and users. 

Any re-opening of this issue should be specific about what's wrong with the
current "diff" output, and how it should be improved. 

Since we already have "--diff-command" and "--diff-opts", it seems like there is
a lot of possibility to improve the diffs using solutions external to darcs.
msg6148 (view) Author: kowey Date: 2008-09-27.22:15:19
On a 2008-05 mailing list entry, David said that implementing the 'patience
diff' algorithm could be useful

http://lists.osuosl.org/pipermail/darcs-users/2008-May/012229.html
msg6149 (view) Author: kowey Date: 2008-09-27.22:35:18
There's also Bram Cohen's algorithm to consider:
http://lists.osuosl.org/pipermail/darcs-devel/2007-May/005664.html

Is that different?
msg6684 (view) Author: marcot Date: 2008-11-17.18:35:13
Small case where I think the generated diff is not the one I would expect:

marcot@quindinho:~/Modelos/darcs$ cat a 
a
b
c
marcot@quindinho:~/Modelos/darcs$ darcs init
marcot@quindinho:~/Modelos/darcs$ darcs add a
marcot@quindinho:~/Modelos/darcs$ darcs record
Darcs needs to know what name (conventionally an email address) to use as the
patch author, e.g. 'Fred Bloggs <fred@bloggs.invalid>'.  If you provide one
now it will be stored in the file '_darcs/prefs/author' and used as a default
in the future.  To change your preferred author address, simply delete or edit
this file.

What is your email address?
addfile ./a
Shall I record this change? (1/2)  [ynWsfvpxdaqjk], or ? for help: y
hunk ./a 1
+a
+b
+c
Shall I record this change? (2/2)  [ynWsfvpxdaqjk], or ? for help: y
What is the patch name?
What is the patch name? a
Do you want to add a long comment? [yn]n
Finished recording patch 'a'
marcot@quindinho:~/Modelos/darcs$ # Edit a
marcot@quindinho:~/Modelos/darcs$ cat a
c
b
a
marcot@quindinho:~/Modelos/darcs$ darcs whatsnew
hunk ./a 1
-a
-b
hunk ./a 2
+b
+a
marcot@quindinho:~/Modelos/darcs$ darcs --version
2.0.2 (release)

I would expect it to generate something as:
hunk ./a 1
-a
+c
hunk ./a 3
-c
+a
msg6685 (view) Author: droundy Date: 2008-11-17.18:46:34
On Mon, Nov 17, 2008 at 06:35:27PM -0000, Marco TĂșlio Gontijo e Silva wrote:
> marcot@quindinho:~/Modelos/darcs$ darcs whatsnew
> hunk ./a 1
> -a
> -b
> hunk ./a 2
> +b
> +a
> marcot@quindinho:~/Modelos/darcs$ darcs --version
> 2.0.2 (release)
> 
> I would expect it to generate something as:
> hunk ./a 1
> -a
> +c
> hunk ./a 3
> -c
> +a

Although I agree that we could improve on our diff, I don't think this
is a good example.  I don't see any reason why darcs should decide
that the 'b' was preserved rather than the 'c' or the 'a'.  I guess
you're thinking that it should take into account the location in the
file, and somehow treat lines that haven't moved specially?

David
msg6686 (view) Author: marcot Date: 2008-11-17.19:01:01
I think it would be good, but maybe it's just the way I'm looking at it.  I'm
convinced this is a subjective point of view, so it's ok not to consider this
example.
msg14674 (view) Author: kowey Date: 2011-08-18.14:30:31
We should take note of http://hackage.haskell.org/package/patience-0.1.1
msg16727 (view) Author: gh Date: 2013-02-27.15:22:44
A GPL licensed Haskell implementation by David Roundy: 
https://github.com/droundy/iolaus-broken/blob/master/Iolaus/Lcs2.hs#L128
msg17049 (view) Author: markstos Date: 2013-09-24.19:00:05
Patience diff has been implemented now. Can this ticket be resolved?
msg17056 (view) Author: noreply Date: 2013-10-10.15:08:00
The following patch sent by Jose Luis Neder <jlneder@gmail.com> updated issue issue346 with
status=resolved;resolvedin=2.10.0 HEAD

* resolve issue346: implement "patience diff" from bzr 
Ignore-this: 67e8a1a8098c98a7ef7dcab816885b6d
Add patience diff algorithm to Darcs/Util/Diff/Patience.hs from David Roundy implementation with some tweaks.
Make some changes required to let the user choose between algorithms with a flag.
History
Date User Action Args
2006-11-13 23:39:13beschmicreate
2008-02-16 19:10:43markstossetstatus: has-patch -> wont-fix
nosy: + markstos
messages: + msg3507
2008-09-27 22:15:21koweysetstatus: wont-fix -> deferred
nosy: + dagit, simon
title: darcs diff algorithm should find nicer diffs -> implement "patience diff" from bzr
messages: + msg6148
assignedto: beschmi ->
2008-09-27 22:35:20koweysetnosy: droundy, tommy, beschmi, kowey, markstos, dagit, simon
messages: + msg6149
2008-11-17 18:35:26marcotsetnosy: + dmitry.kurochkin, marcot, thorkilnaur
messages: + msg6684
2008-11-17 18:46:39droundysetnosy: droundy, tommy, beschmi, kowey, markstos, dagit, simon, marcot, thorkilnaur, dmitry.kurochkin
messages: + msg6685
2008-11-17 19:01:03marcotsetnosy: droundy, tommy, beschmi, kowey, markstos, dagit, simon, marcot, thorkilnaur, dmitry.kurochkin
messages: + msg6686
2009-08-06 17:49:24adminsetnosy: + jast, Serware, darcs-devel, zooko, mornfall, - droundy, marcot
2009-08-06 20:52:49adminsetnosy: - beschmi
2009-08-10 21:58:48adminsetnosy: + marcot, - darcs-devel, zooko, jast, Serware, mornfall
2009-08-10 23:58:05adminsetnosy: - dagit
2009-08-25 17:25:52adminsetnosy: + darcs-devel, - simon
2009-08-26 14:28:11koweysetstatus: deferred -> needs-implementation
nosy: tommy, kowey, markstos, darcs-devel, marcot, thorkilnaur, dmitry.kurochkin
2009-08-27 14:33:22adminsetnosy: tommy, kowey, markstos, darcs-devel, marcot, thorkilnaur, dmitry.kurochkin
2011-08-18 14:30:32koweysetmessages: + msg14674
2013-02-27 15:22:47ghsetmessages: + msg16727
2013-05-29 22:05:51ghsetnosy: + jlneder
2013-09-24 19:00:07markstossetmessages: + msg17049
2013-10-10 15:08:01noreplysetstatus: needs-implementation -> resolved
messages: + msg17056
resolvedin: 2.10.0 HEAD