This patches implements patience diff algorithm in darcs and integrate it in the command line with a flag.
This is a minor bugfix from the last set of patches i send. I miss a line between the patches. Sorry for any inconvenience.
3 patches for repository /home/jul/Proyectos/GSoC/patience-diff/screened:

Mon Jul 22 23:12:52 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * name change Lcs.hs -> Diff/Myers.hs
  change the name of the file with the myers diff algorithm implementation in preparation for the integration of others implementations.

Tue Jul 23 05:51:22 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * resolve issue346: implement "patience diff" from bzr
  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 in the commands that it could be useful.

Tue Jul 23 05:56:02 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * make darcs-test run tests with both diff algorithms

Attachments

• name-change-lcs_hs-__-diff_myers_hs.dpatch
• patch-preview.txt
• unnamed

Reuploaded because of context issues
3 patches for repository /home/jul/Proyectos/GSoC/patience-diff/screened:

Mon Jul 22 23:12:52 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * name change Lcs.hs -> Diff/Myers.hs
  change the name of the file with the myers diff algorithm implementation in preparation for the integration of others implementations.

Tue Jul 23 05:51:22 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * resolve issue346: implement "patience diff" from bzr
  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 in the commands that it could be useful.

Tue Jul 23 05:56:02 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * make darcs-test run tests with both diff algorithms

Attachments

• name-change-lcs_hs-__-diff_myers_hs.dpatch
• patch-preview.txt
• unnamed

* name change Lcs.hs -> Diff/Myers.hs

Good to go. There's a useless hunk in ./src/Darcs/Util/Diff/Myers.hs ,
try to not add this kind of changes in the future.

* resolve issue346: implement "patience diff" from bzr

I have above all superficial, cleanup comments that you could take into
account
for the next iteration of this patch.

Maybe the long description could do without the " in the commands that
it could be useful".

> hunk ./harness/Darcs/Test/Patch/Properties/V1Set1.hs 100
> -    where p1_ = mapFL_FL fromPrim $ concatFL $ mapFL_FL canonize $
sortCoalesceFL $ effect p1
> +    where p1_ = mapFL_FL fromPrim $ concatFL $ mapFL_FL (canonize
D.MyersDiff) $ sortCoalesceFL $ effect p1

You could add a comment telling that the diff algorithm does not matter
if it's the case, or justifying why Myers is used.


> hunk ./src/Darcs/Patch/Annotate.hs 143
> -        reannotate $ getChanges before after
> +        dac <- gets diffAlgorithm
> +        reannotate $ getChangesWith dac before after

Why not use the name `da`? What is the `c` for in `dac`? Same obseration
for the following hunks.


> hunk ./src/Darcs/Patch/Named.hs 165
> -                let (informAdd, informDel) = fromMaybe (const id,
const id) nameHack
> +                -- TODO: see how to integrate DiffAlgorithm or if it
is necessary at all
> +                let (informAdd, informDel) = fromMaybe (const id,
const id) (nameHack MyersDiff)

This comment does not really make sense to me. Is is a way to tell that
you are not sure about the use of `nameHack MyersDiff` and that it may
change in the future?

> hunk ./src/Darcs/Patch/Prim/V1/Coalesce.hs 243
> -
> +   [_$_]

Please remove this hunk (darcs amend --unrecord).


> hunk ./src/Darcs/Patch/Rebase.hs 211
> -  commuteNoConflicts = commuterRebasing commuteNoConflicts
> +  -- TODO: see how to integrate D.DiffAlgorithm or if it is necessary
at all
> +  commuteNoConflicts = commuterRebasing D.MyersDiff commuteNoConflicts
> hunk ./src/Darcs/Patch/Rebase.hs 218
> -  merge (Normal p :\/: Suspended qs) = unseal Suspended (addFixup
(invert p) qs) :/\: Normal p
> -  merge (Suspended ps :\/: Normal q) = Normal q :/\: unseal Suspended
(addFixup (invert q) ps)
> +  -- TODO: see how to integrate D.DiffAlgorithm or if it is necessary
at all
> +  merge (Normal p :\/: Suspended qs) = unseal Suspended (addFixup
D.MyersDiff (invert p) qs) :/\: Normal p
> +  merge (Suspended ps :\/: Normal q) = Normal q :/\: unseal Suspended
(addFixup D.MyersDiff (invert q) ps)

Same observation about the TODO comment.

> hunk ./src/Darcs/Patch/Rebase.hs 369
> -   recontextRebase = Just (RecontextRebase1 recontext)
> +   recontextRebase = Just $ RecontextRebase1 $ recontext

You may remove this hunk if it does not bother you.

> hunk ./src/Darcs/Patch/Rebase.hs 374
> -              = (IsEq, RecontextRebase2 (\fixups -> unseal
mkSuspended (simplifyPushes (mapFL_FL translateFixup fixups) ps)))
> +              -- TODO: see how to integrate D.DiffAlgorithm or if it
is necessary at all
> +              = (IsEq, RecontextRebase2 (\fixups -> unseal
mkSuspended(simplifyPushes D.MyersDiff (mapFL_FL translateFixup fixups)
ps)))

TODO comment.

> hunk ./src/Darcs/Patch/Split.hs 107
> --- |Never splits. In other code we normally pass around Maybe
Splitter instead of using this
> +-- |Never splits. In other `de we normally pass around Maybe Splitter
instead of using this

Please remove.

> hunk ./src/Darcs/UI/Commands/AmendRecord.hs 81
> -                   , diffingOpts, compression, verbosity,
removeFromAmended, useCache, umask )
> -import Darcs.Repository.Flags ( UpdateWorking(..), DryRun(NoDryRun) )
> +                   , diffingOpts, compression, verbosity,
removeFromAmended, useCache, umask, diffAlgorithmOptsChoice )
> +import Darcs.Repository.Flags ( UpdateWorking(..), DryRun(NoDryRun))

Please remove the second line of this hunk.

> hunk ./src/Darcs/UI/Commands/Move.hs 37
> -import Darcs.UI.Flags ( doAllowCaseOnly, doAllowWindowsReserved,
useCache, dryRun, umask)
> +import Darcs.UI.Flags ( doAllowCaseOnly, doAllowWindowsReserved,
useCache, dryRun, umask )


Please remove.

> hunk ./src/Darcs/UI/Commands/Remove.hs 43
> +
> hunk ./src/Darcs/UI/Commands/Remove.hs 49
> +

Please remove.

> hunk ./src/Darcs/UI/Commands/SetPref.hs 28
> -import Darcs.UI.Flags ( useCache, dryRun, umask)
> +import Darcs.UI.Flags ( useCache, dryRun, umask )

Please remove.

hunk ./src/Darcs/UI/Flags.hs 212
-

> hunk ./src/Darcs/UI/SelectChanges.hs 228
> -                WhichChanges -> FL p wX wY
> -                             -> PatchSelection p wX wY
> +                 WhichChanges -> FL p wX wY
> +                              -> PatchSelection p wX wY
> hunk ./src/Darcs/UI/SelectChanges.hs 241
> -                WhichChanges -> FL p wX wY
> -                             -> PatchSelection p wX wY
> +       WhichChanges -> FL p wX wY
> +                    -> PatchSelection p wX wY

Please remove.

hunk ./src/Darcs/Util/Diff.hs 6
+import Darcs.Util.Diff.Myers ( getChanges )
+import qualified Darcs.Util.Diff.Patience as P ( getChanges )
+import qualified Data.ByteString as B ( ByteString )
+
+
+data DiffAlgorithm = PatienceDiff | MyersDiff
+    deriving ( Eq, Show )
+
+getChangesWith :: DiffAlgorithm -> [B.ByteString] -> [B.ByteString]
+               -> [(Int,[B.ByteString],[B.ByteString])]
+getChangesWith dac = case dac of
+                       PatienceDiff -> P.getChanges
+                       MyersDiff -> getChanges

I think you could simply call this function getChanges.



Now, I'd rather have the following change not part of this patch:

> hunk ./src/Darcs/Patch/Prim/V1/Coalesce.hs 241
> -   canonizeFL = concatFL . mapFL_FL canonize . sortCoalesceFL .
> -                concatFL . mapFL_FL canonize
> +   canonizeFL diffa = concatFL . mapFL_FL (canonize diffa) .
sortCoalesceFL

You seem to be fixing the double use of canonize. I'd rather see it
happen in a separate
patch, that also modificates the comment right above this piece of code.
And with explanations
to justify the change.



Also, you enable functions of Darcs.Repository.Repair to receive a flag
enabling to choose the diff algorithm, however the command repair does
not receive this flag. Should it? Or should functions of
Darcs.Repository.Repair use a default diff algorithm?

i made the corrections suggested. Deleted the todos because i don't find them relevant anymore. The repair command have the diff flag. The double canonize fix is out this patch.
3 patches for repository /home/jul/Proyectos/GSoC/patience-diff/screened:

Mon Jul 22 23:12:52 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * name change Lcs.hs -> Diff/Myers.hs
  change the name of the file with the myers diff algorithm implementation in preparation for the integration of others implementations.

Wed Jul 24 11:30:59 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * resolve issue346: implement "patience diff" from bzr
  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 in the commands that it could be useful.

Wed Jul 24 11:38:00 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * make darcs-test run tests with both diff algorithms

Attachments

• name-change-lcs_hs-__-diff_myers_hs.dpatch
• patch-preview.txt
• unnamed

i miss something in the last one.

3 patches for repository /home/jul/Proyectos/GSoC/patience-diff/screened:

Mon Jul 22 23:12:52 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * name change Lcs.hs -> Diff/Myers.hs
  change the name of the file with the myers diff algorithm implementation in preparation for the integration of others implementations.

Wed Jul 24 12:37:45 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * resolve issue346: implement "patience diff" from bzr
  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 in the commands that it could be useful.

Wed Jul 24 11:38:00 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * make darcs-test run tests with both diff algorithms

Attachments

• name-change-lcs_hs-__-diff_myers_hs.dpatch
• patch-preview.txt
• unnamed

The bundle looks much better, thanks!

Before screening or accepting it I will use darcs with patience diff
and see if I run into something weird.

Running the same diff-related tests in parallel with Myers and Patience
diff provoked a failure, so I'm sending the following patch:

1 patch for repository http://darcs.net:

Thu Jul 25 11:29:57 CEST 2013  Guillaume Hoffmann <guillaumh@gmail.com>
  * fix test for issue1290 for when tests are run in parallel

Attachments

• fix-test-for-issue1290-for-when-tests-are-run-in-parallel.dpatch
• patch-preview.txt
• unnamed

I must have run the tests hundreds of times and i never seen any issues
except for issue121. Weird. I guess my machine is to slow to bother for
synchronization issues...


2013/7/25 Guillaume Hoffmann <bugs@darcs.net>

>
> Guillaume Hoffmann <guillaumh@gmail.com> added the comment:
>
> The bundle looks much better, thanks!
>
> Before screening or accepting it I will use darcs with patience diff
> and see if I run into something weird.
>
> Running the same diff-related tests in parallel with Myers and Patience
> diff provoked a failure, so I'm sending the following patch:
>
> 1 patch for repository http://darcs.net:
>
> Thu Jul 25 11:29:57 CEST 2013  Guillaume Hoffmann <guillaumh@gmail.com>
>   * fix test for issue1290 for when tests are run in parallel
>
> __________________________________
> Darcs bug tracker <bugs@darcs.net>
> <http://bugs.darcs.net/patch1083>
> __________________________________
>

Attachments

• unnamed

Do you run them in parallel ? Ie, with flag -j 4 for instance ? It
seems to only happen in parallel.

i run them with -j 2.


2013/7/25 Guillaume Hoffmann <guillaumh@gmail.com>

> Do you run them in parallel ? Ie, with flag -j 4 for instance ? It
> seems to only happen in parallel.
>

Attachments

• unnamed

Then probably it's a matter of computing speed. In fact I had this
problem most of the time I ran that particular test, but not always.

One more change to your bundle:

In the case of the `darcs diff` command, it is useless to accept a diff
algorithm flag since the call to `unrecordedChanges` in
`Darcs.UI.Commands.Diff` is only part of a step to construct one of the
trees that is passed to the external diff program (being the commandline
`diff` by default). Hence you can just pass Myers by default for instance.

done.
3 patches for repository /home/jul/Proyectos/GSoC/patience-diff/screened:

Mon Jul 22 23:12:52 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * name change Lcs.hs -> Diff/Myers.hs
  change the name of the file with the myers diff algorithm implementation in preparation for the integration of others implementations.

Thu Jul 25 07:56:47 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * resolve issue346: implement "patience diff" from bzr
  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.

Thu Jul 25 07:57:19 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * make darcs-test run tests with both diff algorithms

Attachments

• name-change-lcs_hs-__-diff_myers_hs.dpatch
• patch-preview.txt
• unnamed

José, you wrote about the performance of Patience vs Myers diff in your
blog post here:
http://blog.jlneder.com.ar/2013/07/integrating-patience-diff-and-some.html

You conclude that their performance are close one to another.

However, on some tests I ran, it is possible to see a quite big
difference in a realistic case: a relatively big file (6000 lines) with
a small hunk deletion and another small hunk insertion: we get a 4 times
slowdown (from ~1 to ~4 miliseconds).

I generated random files using this script:
    http://hub.darcs.net/gh/bench/browse/genDiff.sh

And the criterion report I got was:
    http://hub.darcs.net/gh/bench/raw/crit.html

Do you get similar results on your machine with this benchmark?

I think the performance is still acceptable but would it be possible to
enhance it? Or is it by design a more complex algorithm?

I looked at the benchmark results and managed to optimize the
implementation a lot using hashes and assigning an Int to each
different line for the comparison. Please test the new implementation
from http://hub.darcs.net/jlneder/darcs-patience-benchmarks.
This is my criterion report:
http://hub.darcs.net/jlneder/darcs-patience-benchmarks/raw/CriterionBenchmarks.html.
I saw a 7 times slowdown my machine in the test case you mention with
the old implementation and i managed to make it a 2x slowdown but i
would like to see how it runs in your machine given it runs the old
implementation a lot faster.
There is a little more room for optimization using arrays instead of
list like the myers implementation do, but it is almost a total
rewrite. I think a patience diff implementation using arrays would be
equal, if not faster than myers implementation because the algorithm
is less complex than the myers implementation with Darcs tweaks.
I test the hash from Data.Hashable and i found it's better than the
hashPS implementation of Darcs(performance wise). I don't know if it's
worth to add a dependency to make this change but is a small
dependency anyway.

2013/7/26 Guillaume Hoffmann <bugs@darcs.net>:
>
> Guillaume Hoffmann <guillaumh@gmail.com> added the comment:
>
> José, you wrote about the performance of Patience vs Myers diff in your
> blog post here:
> http://blog.jlneder.com.ar/2013/07/integrating-patience-diff-and-some.html
>
> You conclude that their performance are close one to another.
>
> However, on some tests I ran, it is possible to see a quite big
> difference in a realistic case: a relatively big file (6000 lines) with
> a small hunk deletion and another small hunk insertion: we get a 4 times
> slowdown (from ~1 to ~4 miliseconds).
>
> I generated random files using this script:
>     http://hub.darcs.net/gh/bench/browse/genDiff.sh
>
> And the criterion report I got was:
>     http://hub.darcs.net/gh/bench/raw/crit.html
>
> Do you get similar results on your machine with this benchmark?
>
> I think the performance is still acceptable but would it be possible to
> enhance it? Or is it by design a more complex algorithm?
>
> __________________________________
> Darcs bug tracker <bugs@darcs.net>
> <http://bugs.darcs.net/patch1083>
> __________________________________

Here is the report:

http://hub.darcs.net/gh/bench/raw/crit2.html

The same without the "totally different" benchmarks:

http://hub.darcs.net/gh/bench/raw/crit2b.html

So now on this example Patience is on par with Myers. I compiled the
benchmark program with only the flag -Wall (no -O2 for instance).

Can you submit the patch bundle with this new implementation?

Can you add comments to Darcs.Diff.Patience? The functions dropStart,
dropEnd, genNestedChanges, for instance.

The functions dropStart and dropEnd run the first part of the
algorithm that is the same that in myers algorithm (ie step 1 and 2).
genNestedChanges do the 3 and 4 step. It first try to do it
byparagraph, then bylines and at last it make the remaining hunks with
mkdiff and patienceLcs.

1. Match the first lines of both if they're identical, then match the
second, third, etc. until a pair doesn't match. (dropStart)
2. Match the last lines of both if they're identical, then match the
next to last, second to last, etc. until a pair doesn't match.
(dropEnd)
3. Find all lines which occur exactly once on both sides, then do
longest common subsequence on those lines, matching them up.
(genNestedChanges ~ lcus)
4. Do steps 1-2 on each section between matched lines.
(genNestedChanges with break calls)

I'm running the tests now in case i miss something.

2013/7/30 Guillaume Hoffmann <bugs@darcs.net>:
>
> Guillaume Hoffmann <guillaumh@gmail.com> added the comment:
>
> Here is the report:
>
> http://hub.darcs.net/gh/bench/raw/crit2.html
>
> The same without the "totally different" benchmarks:
>
> http://hub.darcs.net/gh/bench/raw/crit2b.html
>
> So now on this example Patience is on par with Myers. I compiled the
> benchmark program with only the flag -Wall (no -O2 for instance).
>
> Can you submit the patch bundle with this new implementation?
>
> Can you add comments to Darcs.Diff.Patience? The functions dropStart,
> dropEnd, genNestedChanges, for instance.
>
> __________________________________
> Darcs bug tracker <bugs@darcs.net>
> <http://bugs.darcs.net/patch1083>
> __________________________________

Sending again Jose's bundle to the right patch page. His bundle comment:

"This are the patches with the new implementation."

3 patches for repository http://darcs.net:

Mon Jul 22 23:12:52 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * name change Lcs.hs -> Diff/Myers.hs
  change the name of the file with the myers diff algorithm implementation in preparation for the integration of others implementations.

Tue Jul 30 17:22:23 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * resolve issue346: implement "patience diff" from bzr
  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.

Tue Jul 30 17:22:40 ART 2013  Jose Luis Neder <jlneder@gmail.com>
  * make darcs-test run tests with both diff algorithms

Attachments

• name-change-lcs_hs-__-diff_myers_hs.dpatch
• patch-preview.txt
• unnamed

I'm screening the bundle.

Shall we put an upper bound on the new dependency on the hashable package?

I think we should aim to follow the PVP for new dependencies, so yes.

1 patch for repository http://darcs.net:

Tue Aug 13 12:05:52 ART 2013  Guillaume Hoffmann <guillaumh@gmail.com>
  * put upper bound on hashable dependency

Attachments

• patch-preview.txt
• put-upper-bound-on-hashable-dependency.dpatch
• unnamed

I'm going to accept it along with http://bugs.darcs.net/patch1103 which
fixes a bug that has been discovered by a few users and
http://bugs.darcs.net/patch1098.

As far as I can tell patience diff works well with an acceptable
performance slowdown (see http://bugs.darcs.net/issue2338 , in some
cases there is a 2x slowdown of diffing 6000 lines big files in Ganesh's
benchmarks, from 30 to 60 ms).

Testing could be better. We do have one unit test that checks coalescing
with patience diff, and a shell test introduced by
http://bugs.darcs.net/patch1103. Moreover all shell tests are run with
both diff algorithms.

A few things to think about:

* it would be still nice to have a systematic way of testing correctness
of diff algorithms.
* ...and a systematic way of testing performance of diff algorithms
*within* the repository of darcs (cabal bench maybe)
* Darcs.Diff should probably eventually be spun off as a separate library
* whether patience diff should be default is still open (with this
bundle, it is the current default). I like the examples of
http://blog.jlneder.com.ar/2013/07/patience-diff-algorithm-benefits-for.html
, but I can imagine that some people may argue that proposing less hunks
is not always desirable.

So, I'm pushing the whole thing to reviewed.