planet

News and discussions

1. This year's Google Summer of Code projects brought a lot of improvements to darcs and its ecosystem!
   
   • BSRK Aditya: Darcsden improvements:
     
     • http://joyful.com/blog/2013-09-26-darcsden-darcs-hub-gsoc-complete.html
     • http://bsrkaditya.blogspot.com.ar/2013/09/darcsden-gsoc-final-blog-post.html
   • José Neder: patience diff, file move detection, token replace detection:
     
     • http://lists.osuosl.org/pipermail/darcs-users/2013-October/026945.html
     • http://blog.jlneder.com.ar/search/label/darcs
2. Gian Piero Carrubba asked why adjacent hunks could not commute:
   
   • http://lists.osuosl.org/pipermail/darcs-users/2013-November/026958.html
3. We listed the changes that occurred between version 2.8.4 and the current development branch into a 2.10 release page:
   
   • http://darcs.net/Releases/2.10?revision=20131028184855-5ef8f-ba33870773ad9ee010a470ac8536b5c7ae331b50

Issues resolved (8)

issue346 Jose Luis Neder

• implement "patience diff" from bzr
• http://bugs.darcs.net/issue346

issue1828 Guillaume Hoffmann

• file listing and working --dry-run for mark-conflicts
• http://bugs.darcs.net/issue1828

issue2181 Guillaume Hoffmann

• put cache in $XDG_CACHE_HOME (~/.cache by default)
• http://bugs.darcs.net/issue2181

issue2309 Owen Stephens

• annotate includes line numbers
• http://bugs.darcs.net/issue2309

issue2313 Jose Luis Neder

• whatsnew -l: Stack space overflow
• http://bugs.darcs.net/issue2313

issue2334 Guillaume Hoffmann

• fix win32 build removing file permission functions
• http://bugs.darcs.net/issue2334

issue2343 Jose Luis Neder

• darcs amend-record does not record my change
• http://bugs.darcs.net/issue2343

issue2347 Guillaume Hoffmann

• fix amend-record --prompt-long-comment
• http://bugs.darcs.net/issue2347

Patches applied (39)

2013-10-28 Guillaume Hoffmann

• record: no longer accept first commented line as patch name
• resolve issue2347: fix amend-record --prompt-long-comment
• refuse incorrect patch names (empty or starting with TAG)

2013-06-15 Jose Luis Neder

• resolve issue2313: whatsnew -l: Stack space overflow
• tests for issue2313: whatsnew -l: Stack space overflow

2013-02-17 Mark Stosberg

• new failing test for issue2303 - illustrates a Patch Index diagnostic that can be improved.
• failing test for issue2272: darcs rebase unsuspend should succeed despite unrecorded changes
• issue2271: New (passing) test which confirms that darcs optimize --disable-patch-index will fail in the face of a permissions problem.

2013-08-20 BSRK Aditya

• Export getChangesInfo from Changes command module

2013-09-22 Jose Luis Neder

• Add better comments to the issue2343 test file
• resolve issue2343: darcs amend-record does not record my change

2013-08-20 Ganesh Sittampalam

• Introduce a local copy of Data.Map.Strict from containers 0.5,
• Weaken hashable dependency

2013-08-13 Guillaume Hoffmann

• put upper bound on hashable dependency

2013-07-30 Jose Luis Neder

• make darcs-test run tests with both diff algorithms
• resolve issue346: implement "patience diff" from bzr
• name change Lcs.hs -> Diff/Myers.hs

2013-08-05 Guillaume Hoffmann

• resolve issue2334 fix win32 build removing file permission functions

2013-08-27 BSRK Aditya

• When using send command, post the patch if using http,
• Update containers minimum version

2013-08-12 Guillaume Hoffmann

• remove import warning
• put newline after darcs diff changelog output
• change format of patch name file when a text editor is invoked
• remove redundant case in Darcs.UI.Command.Record.getLog
• update unrecord and obliterate help, mention -O flag

2013-07-18 Owen Stephens

• Fix a couple of warnings from annotate with line numbers patch
• Resolve issue2309: annotate includes line numbers

2013-07-25 Guillaume Hoffmann

• fix test for issue1290 for when tests are run in parallel
• announce moved files
• make move patch explicit
• announce removed files
• announce added files
• resolve issue2181: put cache in $XDG_CACHE_HOME (~/.cache by default)
• merge Darcs.Util.IO into Darcs.Util.File

2013-07-17 Owen Stephens

• Move chompNewline from Commands to Util/Text and rename to chompTrailingNewline

2013-07-04 Guillaume Hoffmann

• update help of mark-conflicts
• resolve issue1828: file listing and working --dry-run for mark-conflicts

2013-03-18 Ganesh Sittampalam

• fix warnings introduced by issue1105 fix

2013-02-21 Florent Becker

• Fix issue1105 even in the presence of command-line optinos

See darcs wiki entry for details.

darcsum 1.3

darcsum was hanging again, so I made some updates:

• Fix a hang when reverting, when darcs responds with “Will not ask whether to revert this already decided patch…”.

• Fixed an error in at least my local darcsum, which caused it to break when darcsum-debug was enabled.

• Fixed the four warnings my emacs gave when byte-compiling it. These fixes could use some testing.

• Reviewed the status and backlog. Last release was 2010, the ELPA package dates from 2012, there’s a bunch of unreleased fixes, the site script needs updating for hakyll 4, the project still needs a maintainer.

And since I came this far, I’ll tag and announce darcsum 1.3. Hurrah!

This release includes many fixes from Dave Love and one from Simon Marlow. Here are the release notes.

Site and ELPA package updates will follow asap. All help is welcome.

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

darcsden/darcs hub GSOC complete

Aditya BSRK’s darcsden-improvement GSOC has concluded, and I’ve recently merged almost all of the pending work and deployed it on darcs hub.

You can always see the recently landed changes here, but let me describe the latest features a little more:

File history - when you browse a file, there’s a new “file changes” button which shows just the changes affecting that file.

File annotate - there’s also a new “annotate” button, providing the standard view showing which commit last touched each line of the file. (also known as the blame/praise feature). It needs some CSS polish but I’m glad that the basic side-by-side layout is there.

More reliable highlighting while editing - the file editor was failing to highlight many common programming languages - this should be working better now. (Note highlighting while viewing and highlighting while editing are independent and probably use different colour schemes, this is a known open wishlist item.)

Repository compare - when viewing a repo’s branches, there’s a new “compare” button which lets you compare (and merge from) any two public repos on darcs hub, showing the unique patches on each side.

Cosmetic fixes - various minor layout and rendering issues were fixed. One point of discussion was whether to use the two-sided layout on the repo branches page as well. Since there wasn’t time to make that really usable I vetoed it in favour of the less confusing one-sided layout. I think showing both sides works well on the compare page though.

Patch bundle support - the last big feature of the GSOC was patch bundles. This is an alternative to the fork repo/request merge workflow, intended to be more lightweight and easy for casual contributors. There are two parts. First, darcs hub issue trackers can now store darcs patch bundle files (one per issue I think). This means patches can be uploaded to an issue, much like the current Darcs issue/patch tracker. But you can also browse and merge patches directly from a bundle, just as you can from another repo.

The second part (not yet deployed) is support for a previously unused feature built in to the darcs send command, which can post patches directly to a url instead of emailing them. The idea (championed by Aditya and Ganesh) is to make it very easy for someone to darcs send patches upstream to the project’s issue tracker, without having to fork a repo, or even create an account on darcs hub. As you can imagine, some safeguards are important to avoid becoming a spam vector or long-term maintenance headache, but the required change(s) are small and I hope we’ll have this piece working soon. It should be interesting to have both workflows available and see which works where.

I won’t recap the older new features, except to say that pack support is in need of more testing. If you ever find darcs get to be slow, perhaps you’d like to help test and troubleshoot packs, since they can potentially make this much faster. Also there are a number of low-hanging UI improvements we can make, and more (relatively easy) bugs keep landing in the darcs hub/darcsden issue tracker. It’s a great time to hack on darcs hub/darcsden and every day make it a little more fun and efficient to work with.

I really appreciate Aditya’s work, and that of his mentor, Ganesh Sittampalam. We did a lot of code review which was not always easy across a large time zone gap, but I think the results were good. Congratulations Aditya on completing the GSOC and delivering many useful features, which we can put to good use immediately. Thanks!

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

In the last post i show some examples and use cases of the "--look-for-replaces" flag for whatsnew, record, and amend-record commands in Darcs. When used, this flag provides automatic detection of replaces(possible ones), even when the modified files shows more differences than only the replaces, and even shows possible "forced" replaces.
The simplest case is when you made a replace in you editor in of choice and don't do any other change to the file and then, after check all is ok, remember that you could have used a replace patch.

Then, instead of:

> darcs revert -a file
Reverting changes in "file":

Finished reverting.
> darcs replace foo bar file
> darcs record -m "replace foo bar"
replace ./file [A-Za-z_0-9] foo bar
Shall I record this change? (1/1) [ynW...], or ? for more options: y
Do you want to record these changes? [Yglqk...], or ? for more options: y
Finished recording patch 'replace foo bar'

You could do:

> darcs record --look-for-replaces -m "replace foo bar"
replace ./file [A-Za-z_0-9] foo bar
Shall I record this change? (1/1) [ynW...], or ? for more options: y
Do you want to record these changes? [Yglqk...], or ? for more options: y
Finished recording patch 'replace foo bar'

But it doesn't have to be a full replace. For instance, if you don't want to change a pair replaces, when you try to detect the changes instead of:
Then, instead of:

> darcs whatsnew
hunk ./file 1
-line1 foo
-line2 foo
-line3 foo
+line1 bar
+line2 bar
+line3 bar

With the new flag you could record this:

> darcs whatsnew --look-for-replaces
replace ./file [A-Za-z_0-9] foo bar
hunk ./file 4
-line4 bar
+line4 foo

Say you replace a word for another word that was already in the file. Normally this would mean that you should use "darcs replace --force". The look-for-replaces flag always "forces" the replaces, so if you try this, the changes to make the replace reversible will be shown before the replace patch:
With the new flag you will see the same patches like if you have made a "darcs replace --force foo bar file":

> darcs whatsnew --look-for-replaces
hunk ./file 4
-line4 bar
+line4 foo
replace ./file [A-Za-z_0-9] foo bar

Given certain limitations you could have any number of replaces detected, like this:
All the replaces are shown below:

> darcs whatsnew --look-for-replaces
replace ./file [A-Za-z_0-9] fee bor
replace ./file [A-Za-z_0-9] fee2 bor2
replace ./file [A-Za-z_0-9] fee3 bor3
replace ./file [A-Za-z_0-9] foo bar
replace ./file [A-Za-z_0-9] foo2 bar2
replace ./file [A-Za-z_0-9] foo3 bar3

If you want to know more about the limitations of this functionality, check Automatic detection of replaces for Darcs - Part 2.

The last weeks i was implementing "--look-for-replaces" flag for whatsnew, record, and amend-record commands in Darcs. When used, this flag provides automatic detection of replaces(possible ones) even when the modified files shows more differences than only the replaces, given they meet the following prerequisites:
1. For a given "word" and a given file, there is not need for all the instances to be replaced, but there must be only one replace suggestion posible. i.e.:

2. The replace must happen in lines that have the same amount of words between the recorded and the working state, otherwise it would not be detected.
3. There must be at least one hunk with the same amount of lines in the - and + side that contains the replace.

⮁ ls -1pC
_darcs/  dir/  dir2/  dir3/  foo  foo2  foo3  foo4  foo5
⮁ mv foo dir3
⮁ mv foo2 dir
⮁ mv foo3 dir2
⮁ mv foo4 foo4.tmp
⮁ mv foo5 foo4
⮁ mv foo4.tmp foo5
⮁ mv dir3 dir
⮁ mv dir dir2/dir2
⮁ mv dir2 dir
⮁ darcs whatsnew --look-for-moves
move ./dir ./dir2/dir2
move ./dir2 ./dir
move ./dir3 ./dir/dir2/dir3
move ./foo ./dir/dir2/dir3/foo3
move ./foo2 ./dir/dir2/foo2
move ./foo3 ./dir/foo3
move ./foo4 ./foo4.tmp~
move ./foo5 ./foo4
move ./foo4.tmp~ ./foo5

The moves shown by "darcs whatsnew --look-for-moves" are not exactly the ones made but yield the same final result.

In the last few weeks i was implementing automatic detection of file renames adding "look-for-moves" flag to the amend-record, record, and whatsnew commands.

In darcs are 3 states:

• The recorded state is the one is marked by the last record made.
• The working state is the actual state of the files in the repository with all the last changes.
• The pending state is the one that mark changes like file adds, moves, replaces, etc, before they are recorded. Is a temporal state between recorded and working that let darcs know about what filenames to track, and changes that are not common like replaces.

 If a file rename is not marked in the pending state, darcs lost track of the file and can't know where it is, and then `darcs whatsnew` and `darcs record` will indicate the file as deleted.
To detect this file rename I choose to use the inode info in the filesystem to check for equality between different filenames in the recorded and working state of the repo. for those who don't know, the inode is an index number assigned by the file system to identify a specific file data. The file name is linked to the data by this number, and it's used by directories as well. You can consult this number with "ls -i".

⮁ mkdir testdir
⮁ touch testfile
⮁ ln testfile testfile.hardlink
⮁ ln -s testfile testfile.symboliclink
⮁ ls -i1
10567718 testdir
10485776 testfile
10485776 testfile.hardlink
10485767 testfile.symboliclink 

You can see that the hardlink shares the same number with the test file, this is because a file is essentially a hardlink to the file data and when you make a new hardlink you are sharing the same file data, so the same inode number.
To have an old inode to filename mapping, there must be some record of the files inodes in some place, so I added the inode info to the index of hashed-storage in _darcs/index. The index save the last info about the record plus the pending state, sort of, so is a perfect fit to save this info.
Then comparing the RecordedAndPending Tree(from the index) with the Working Tree i get the file changes in a pair list mapping between the two states. With this list I resolve dependencies between the different moves, making temporal names if it's necessary and generating a FL list of move patches to merge with the changes between pending and working patches.
This patches are shown in with whatsnew or are selected with record/amend-record to be recorded in the repo.
There is a little more to make this happen but that's the core idea of the implementation.
The algorithm doesn't care if the file are modified or not, because it doesn't care of the content of the files, so it's very robust in that sense.
With this implementation you could do any move directly with "mv", and is very lightweight and fast in detecting moves so is likely a good decision make "--look-for-moves" a default flag. You could do things like this:

⮁ darcs init
Repository initialized.
⮁ touch foo
⮁ darcs record -a -m add_file_foo -A x --look-for-adds
Finished recording patch 'add_file_foo'
⮁ mv foo foo2
⮁ darcs whatsnew --look-for-moves
move ./foo ./foo2

This doesn't work on Windows yet, because fileID(the function on unix-compat that get the inode number) is lacking an implementation on windows. I know the windows API have GetFileInformationByHandle (it returns a BY_HANDLE_FILE_INFORMATION structure that contains the file index number[1]), so there doesn't have to be too hard to add an implementation of it with some boilerplate code to make the interface.
More complicated moves should work and some does but I was having problems with the dependency resolving algorithm implementation. I made some mistakes in the first implementation and I'm dragging them since then. I'm confident to know what is the error so I will fix it soon.
UPDATE: i'm testing a windows implementation with the Win32 haskell library on a virtual machine.

darcs hub, hledger, game dev

Hello blog. Since last time I’ve been doing plenty of stuff, but not telling you about it. Let’s do a bullet list and move on..

darcsden/darcs hub

• fixed some bugs
• committed the hub.darcs.net front page, for easy hacking
• added repo counts to the front page
• GSOC testing/support

hledger

• expanded the docs for conditional blocks (if statement) in CSV rules
• added an include directive to allow sharing of common CSV rules

FunGEn & game dev

A sudden burst of activity here.

• schmoozed in #haskell-game, got caught up on haskell game development, updated the Games wiki page a bit
• updated and published my template for SDL projects on OSX: hssdl-osx-template
• continued some FunGEn updates I’ve been sitting for a year and did a release - see next post.

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

darcs hub repo stats, hledger balance sheet

Recent activity:

I fixed another clumsy query on darcs hub, making the all repos page faster. Experimented with user and repo counts on the front page. I like it, but haven’t deployed to production yet. It costs about a quarter of a second in page load time (one 50ms couch query to fetch all repos, plus my probably-suboptimal filtering and sorting).

I’ve finally learned how many of those names on the front page have (public) repos behind them (144 out of 319), and how many private repos there are (125, higher than expected!).

Thinking about what is really most useful to have on the front page. Keep listing everything ? Just top 5 in various categories ? Ideas welcome.

Did a bunch of bookkeeping today, which inspired my first hledger commit in a while. I found the balancesheet command (abbreviation: bs) highly useful for a quick snapshot of assets and liabilities to various depths (add –depth N). The Equity section was just a distraction though, and I think it will be to most hledger users for the time being, so I removed it.

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

hub hacking

More darcs hub activity, including some actual app development (yay):

Added news links to the front page.

Cleaned up hub’s docs repo and updated the list of blockers on the roadmap.

Updated/closed a number of issues, including the app-restarting #58, thanks to a fast highlighting-kate fix by John McFarlane.

Tested and configured the issue-closing commit posthook in the darcsden trunk repo. Commits pushed/merged there whose message contains the regex (closes #([0-9]+)|resolves #([0-9]+)|fixes #([0-9]+)) will now close the specified issue, with luck.

Consolidated a number of modules to help with code navigation, to be pushed soon.

Improved the redirect destination when deleting or forking repos or creating/commenting/closing issues.

Fixed a silly whitespace issue when viewing a patch, where the author name and date run together. I’m still confused about the specific code that generates this - the code I expect uses tables but firebug shows divs. A mystery for another day..

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

hub speedups

More darcs hub hacking today.

• Cleaned up some button text & styles

• Started playing around with the front page layout to add a news box. Accidentally deployed it to production briefly. Used make undeploy-web for the first time.

• Extracted more of darcs hub’s front page into a separate (local) module, DarcsDen.Hub, for easier customisation.

• Worked on optimising page load speed, especially the front page:

  • instead of rendering the front page content from markdown on each request, do it only when changed. This saved, oh a good 50ms! But I now have the beginnings of a timing utility.

  • load the large codemirror js/css files only on the add/edit file pages

  • set a 7-day Expires header on static images. This took about an hour. Here’s the code (based on Yesod’s), it might fit well in Snap.

  • combine the remaining js/css into one js and one css. This is not committed, I just did it by hand. Try less later (only if it’s really simple).

  YSlow now gives us an A grade (score 95), and it feels pretty quick.

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

darcsden 1.1, darcs hub news

I’ve been hacking (mostly on darcsden/hub) but not blogging recently. Must get back to the old 45-15 minute routine.

• banged on hakyll for a while and set up tag feeds on this blog; joined Planet Darcs

• did code review, testing, deployment of BSRK Aditya’s GSOC enhancements

• spent about 8 hours clarifying darcsden history and writing release notes/announcement. Seriously ? Apparently yes.

• moved the darcs hub FAQ back to the front page, cleaned it up and added some javascript magic.

• fixed the slow user list on the front page - it was doing a query for each user. My effective page load time went from ~2 to 1s. Reducing the number of scripts will be a good next step.

• released darcsden 1.1 and the first darcs hub news update. Yay!

  This packages up what we have been using at hub.darcs.net so that you can run it locally. It’s the first darcsden release installable from hackage, and the first with the UI updates from darcs hub. For now, it still requires CouchDB and Redis to run.

  More importantly, this is about communicating the changes and current status of darcs hub, and doing a bit of marketing. Darcs hub hacking is fun, come and help! I include the announcement below.

---

darcsden 1.1 released

darcsden 1.1 is now available on hackage! This is the updated version of darcsden which runs hub.darcs.net, so these changes are also relevant to that site’s users. (More darcs hub news below.)

darcsden is a web application for browsing and managing darcs repositories, issues, and users, plus a basic SSH server which lets users push changes without a system login. It is released under the BSD license. You can use it:

• to browse and manage your local darcs repos with a more comfortable UI
• to make your repos browsable online, optionally with issue tracking
• to run a multi-user darcs hosting site, like hub.darcs.net

http://hackage.haskell.org/package/darcsden - cabal package
http://hub.darcs.net/simon/darcsden - source
http://hub.darcs.net/simon/darcsden/issues - bug tracker

Release notes for 1.1

Fixed:

• 16: Layout of links and navigation places them offscreen
• 21: anchors on line numbers exist but line numbers not clickable
• 28: forking then deleting a private repo makes repos unviewable
• 29: darcs get to an invalid ssh repo url hangs
• 46: if user kills a push, the lock file is not removed, preventing subsequent pushes

New:

• the signup page security question is case-insensitive (“darcs”)
• login redirects to the “my repos” page
• a more responsive layout, with content first, buttons at top/right
• many other UI updates; font, headings, borders, whitespace, robustness
• more context sensitivity in buttons & links
• better next/previous page controls
• better support for microsoft windows, runs as a service
• builds with GHC 7.6 and latest libraries
• easier developer builds

Brand new, from the Enhancing Darcsden GSOC (some WIP):

• you can sign up, log in, and link existing accounts with your Google or Github id
• you can reset your password
• you can edit files through the web
• you can “pack” your repositories, allowing faster darcs get

Detailed change log: http://hub.darcs.net/simon/darcsden/CHANGES.md

How to help

darcsden is a small, clean codebase that is fun to hack on. Discussion takes place on the #darcs IRC channel, and useful changes will quickly be deployed at hub.darcs.net, providing a tight dogfooding/feedback loop. Here’s how to contribute a patch there:

1. register at hub.darcs.net
2. add your ssh key in settings so you can push
3. fork your own branch: http://hub.darcs.net/simon/darcsden , fork
4. copy to your machine: darcs get http://hub.darcs.net/yourname/darcsden
5. make changes, darcs record
6. push to hub: darcs push yourname@hub.darcs.net:darcsden --set-default
7. your change will appear at http://hub.darcs.net/simon/darcsden/patches
8. discuss on #darcs, or ping me (sm, simon@joyful.com) to merge it

Credits

Alex Suraci created darcsden. Simon Michael led this release, which includes contributions from Alp Mestanogullari, Jeffrey Chu, Ganesh Sittampalam, and BSRK Aditya (sponsored by Google’s Summer of Code). And last time I forgot to mention two 1.0 contributors: Bertram Felgenhauer and Alex Suraci.

darcsden depends on Darcs, Snap, GHC, and other fine projects from the Haskell ecosystem, as well as Twitter Bootstrap, JQuery, and many more.

---

darcs hub news 2013/07

http://hub.darcs.net , aka darcs hub, is the darcs repository hosting site I operate. It’s like a mini github, but using darcs. You can:

• browse users, repos, files and changes
• publish darcs repos publicly or privately
• get, push and pull repos over ssh
• grant push access to other members
• fork repos, then view and merge upstream and downstream changes
• track issues

The site was announced on 2012/9/15 (http://thread.gmane.org/gmane.comp.version-control.darcs.user/26556). Since then:

• The site has been deploying new darcsden work promptly; it includes all the 1.1 release improvements described above.

• The server’s ram has doubled from 1G to 2G (thanks Linode). This means app restarts due to excessive memory use are less frequent.

• The front page’s user list had become slow and has been optimised, halving the page load time.

• BSRK Aditya is doing his Google Summer of Code project on enhancing darcsden and darcs hub (mentored by darcs developer Ganesh Sittampalam). Find out more at http://darcs.net/GSoC/2013-Darcsden .

• The site is being used, with many small projects and a few well-known larger ones. Quick stats as of 2013/07/19:

  user accounts                       317
  repos                               579
  disk usage                            2.5G
  uptime last 30 days                  99.48%
  average response time last 30 days    1.6s

• The site remains free to use, including private repos. Eventually, some kind of funding will be needed to keep it self-sustaining, and could also enable faster development. Donate button ? Gittip ? Charge for private repos ? Let’s discuss.

Please try it out, report problems, and contribute patches to make it better.

---

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

In this post i am going to explain the benefits of Bram Cohen's patience diff algorithm for darcs but first we have to understand how this algorithm works. There are great posts on the web that explain it really well so instead of trying to explain it again i'm going to quote the important things i need to remark the benefits it have for darcs and haskell-like non-curly languages by examples.

A brief summary of what the patience diff algorithm does from Bram Cohen's Blog:

1. Match the first lines of both if they're identical, then match the second, third, etc. until a pair doesn't match.
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.
3. Find all lines which occur exactly once on both sides, then do longest common subsequence on those lines, matching them up.
4. Do steps 1-2 on each section between matched lines

From Alfedenzo's Blog:

The common diff algorithm is based on the longest common subsequence problem. Given (in this case) two documents, finding all lines that occur in both, in the same order. That is, making a third document such that every line in the document appears in both of the original documents, and in the same order. Once you have the longest common subsequence, all that remains is to describe the differences between each document and the common document, a much easier problem since the common document is a subset of the other documents.
While the diffs generated by this method are efficient, they tend not to be as human readable.
Patience Diff also relies on the longest common subsequence problem, but takes a different approach. First, it only considers lines that are (a) common to both files, and (b) appear only once in each file. This means that most lines containing a single brace or a new line are ignored, but distinctive lines like a function declaration are retained. Computing the longest common subsequence of the unique elements of both documents leads to a skeleton of common points that almost definitely correspond to each other. The algorithm then sweeps up all contiguous blocks of common lines found in this way, and recurses on those parts that were left out, in the hopes that in this smaller context, some of the lines that were ignored earlier for being non-unique are found to be unique. Once this process is finished, we are left with a common subsequence that more closely corresponds to what humans would identify.

Then when you modify something that is between unique lines like this:

darcsden cleanup

Back to the dev diary. Last post was 11 days ago, after a two-week opening streak of daily posts. I got blocked on one, then got busy. Press on.

Yesterday I started looking at BSRK Aditya’s GSOC darcsden enhancements, to review and hopefully deploy on darcs hub. So far he has worked on alternate login methods (github/google), password reminder, and darcs pack support (for faster gets).

This is forcing some darcsden cleanup, my first darcsden work in a while aside from routine ops and support tasks. I’m going to release what’s in trunk as 1.1, and then start assimilating the new work by BSRK, Ganesh Sittampalam and anyone else who feels like chipping in. Started putting together release notes and a hub status update.

The support requests seem to be on the rise - more usage ? I also found a good bug today: viewing a certain 1K troff file causes darcs hub’s memory footprint to blow up to 1.5G :)

It would be great to have more functionality (like highlighting) broken out into separate, expendable worker processes, erlang style.

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

The past two weeks i was integrating the patience diff algorithm adding an option flag so it can be selected from the command line. This was not as easy as it seems because the diff algorithm was deeply integrated in the codebase and adding a way to select between the two implementation would mean changing more than changing little bits of code here and there. But its done. There are a few rough edges here and there but is ready to be used.
Now you can use "--patience" to use the alternative patience diff algorithm. There should be relatively easy to add more algorithms now.

Regarding the performance, after running a variety of benchmarks with both algorithms in the end I really couldn't get conclusive results. Depending of the input one algorithm could perform better that the other, but only by a shallow margin. This are some of the runs i got(ShellTestsBenchmark, PureCriterionBenchmark).

You can see the code in darcs-patience and darcs-patience-benchmarks
 repositories.

This week I also was researching the best way to implement --look-for-moves flag. I came to the conclusion that the best trade-off is to extend the functionality in hashed-storage adding the inode of the files and then making a changes in some of the darcs commands to maintain and support this new info. I will be using unix-compat package. The functionality is not yet fully implemented for Windows but it may be a solution to that with this. Unfortunately I will have to move to a windows machine to see how this could be implemented. There are some corner cases to consider as well.

You are going to be able to see my progress in darcs-look-for-moves and hashed-storage-look-for-moves repositories in the next weeks.

darcsden db thoughts

Spent about half of yesterday setting up Aditya’s darcsden patches on the dev instance of hub.darcs.net, testing them, and exploring db migration issues.

Following BSRK’s instructions, I got the dev instance authenticating via Google’s OAuth servers. Good progress. The UI flow I saw needs a bit more work - eg logging in with google seemed to want me to register a new account. Or, there may be a problem with my setup at Google (wrong callback urls ?) - will have to review it with BSRK.

Schema, migrations

My dev instance has so far been using the same database as the live production instance. This is partly because I don’t yet know how to run a second CouchDB instance, partly to reduce complexity, partly to be able to compare old and new code with the same realistic data set.

This of course can lead to trouble, if old and new code require different schemas. darcsden uses CouchDB, a “schemaless” database, but of course there is an implicit schema required by the application code, even if couch doesn’t enforce one. I got more clarity on this when I noticed my dev instance experiments causing errors on the production app.

New darcsden code may include changes to the (implicit) db schema. In this case, there’s a change to the user’s password field. I need to notice such schema changes, and if I want to exercise them on the dev instance, I should first also install them on the production instance. Or, use a separate couchdb instance. Or, use separate databases in the couchdb instance. Or possibly, use separate views in the couchdb databases ?

Eg, here BSRK made the code nicely read user documents (db records) with the old or new schema. Before testing it on the shared db I should have deployed that patch to production as well as dev.

Looking ahead, is this approach (including code to deal with all old schemas) the best way to handle this ? Maybe. It makes things work and seems convenient, at least for now. But it also reminds me of years working with Zope’s ZODB (a schemaless python object database) and the layers of on-the-fly schema updating that built up, and the uncounted number of runtime bugs hunted down due to schema variations in individual objects.

Schema-less or schema-ful ?

While recovering from this, I learned some more about managing couchdb, schema migration, and current couchdb alternatives.

Couch has some really good and unusual qualities, and I feel I’m only scratching the surface of it’s power. Even so, I’m starting to feel a schema-ful, relational database is a better fit for darcsden/darcs hub. Replacing couch has been a topic of discussion on #darcs for some time, for other reasons. Here are some reasons to replace it:

• darcsden (more particularly, the instance running darcs hub, which has a lot of long-lived data) works best when all records have the same shape. It gains nothing from the flexibility of a loose schema, in fact will break, at runtime and unpredictably, unless you have extra code that handles all variations perfectly (a hard thing to test).

• couchdb makes darcsden harder to set up, eg on windows. This makes it less successful in its goal to be an easy single-user ui for local darcs repos. It also reduces the number of darcsden hackers.

• it adds complexity by embedding application code in the db. Instead of all logic being in haskell, the darcsden developer has to also deal with design documents and javascript map/reduce functions, and manage the state of those within the db.

• it adds complexity by being less familiar to most people than rdbms system, and by having less mature tools.

• persistent, the likely alternative, would more easily support both large installations (eg postgres for darcs hub) and single-user ones (sqlite) with less code.

Some reasons not to:

• Don’t replace working code!

• Replacing it could be wasted effort, better spent fixing end-user bugs on darcs hub.

• The migration issue can easily be worked around. It’s not that big a deal for this instance.

• Don’t disrupt the GSOC in progress!

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

June review

The beginning of a new month. Here’s a quick update.

No hledger release today as there isn’t much new to ship, following a month with several bugfix releases and otherwise mostly infrastructural work (build and dev tool fixes, wiki styling, site update hook). 8/1 is the likely next release date. Oh, John and I also had a nice voice chat - nice to escape the IRC window isn’t it - reviewing our glorious *ledger plans, and I happily accepted his first hledger patch - thanks John! :)

My free hacking time in recent weeks went more towards darcs:

• Unix shell helpers to get one-line-per-patch output from darcs (awesome!)

  # show darcs changes, push, pull etc. output with one patch per line
  # Eg:
  # dch --last 3
  # darcs pull --dry | d1
  alias darcsoneline="egrep '^\w' -A1 | egrep -v '^(--|The remote repository has|Would pu)' | sed '$!N;s/\n/ /'"
  alias d1=darcsoneline
  function dch() {
      darcs changes $* | darcsoneline
  }

• Support for BSRK Aditya’s GSOC work. Together with Ganesh Sittampalam we did several rounds of code review and BSRK’s nice enhancements should be appearing on darcs hub soon.

• Also driven by the above, updated darcsden and HSP for current GHC and libraries, and made it easy for me to build and deploy again. Also merged Ganesh’s improvements for MS Windows compatibility. This will be released as darcsden 1.1 shortly.

• Ongoing darcs hub ops/maintenance, including a fix for this interesting segfault, and a server upgrade from ubuntu 12.04 to 13.04. This last caused about 45m1h20m of downtime >:( late last night as I wrestled with the unfamiliar couchdb migration process and erlang stack traces. (For reference: just copy /var/lib/couchdb/1.0.1/* to 1.2.0/, but don’t forget to preserve file ownership.) At least it got resolved it before month-end at pingdom, so there’s a chance to get uptime back up where it should be - 3 or 4 nines - in July!

<noscript>JavaScript not enabled, comments will not be shown.</noscript>

As you know, my GSoC project consist in enhancing record command for Darcs.

As part of this, the last two weeks I was implementing the patience diff algorithm for patches and testing it for correctness, performance and usefulness.

First, after identifying where I had to add the code, I proceeded to see if there was any implementation that could use (reuse code, don't reinvent the wheel). To my joy, David Roundy implemented it in his RCS Iolaus and it was almost a direct replacement.
Before doing this I was working in a stack overflow issue (issue2313, patch1076) and i found that big files and diffs cause a stack overflow in this implementation too. After profiling i reduce the problem to the function "byparagraph". It wasn't tail-recursive so after convert it the problem was away and i happy to say it outperform the old diff implementation in this use cases.
For testing the performance i used two tools: criterion and GHC time and space profiling system. The result shows that there isn't any difference in day to day use, performance wise. It particularly perform really bad with files that have many lines equal. I don't think this is really a problem because is very rare(but i'm looking into it) . The old algorithm use more memory but i couldn't make use of all my 4gb of ram as much as i try it, so i can say this is not an issue.
For testing usefulness i make some examples(based on this posts [1][2][3]). It seems to happen that the two different algorithms return actually quite similar patches(if not exactly the same patch) in non-curly braced languages like haskell. On the other hand, in curly-braced languages patience diff is much better.

All in all, i could say that there is several advantages to make the switch. I will be updating my findings about the performance and usefulness in next posts.
You can review the code in http://hub.darcs.net/jlneder/darcs-patience.
In http://hub.darcs.net/jlneder/darcs-patience-tests there is code to compare the two algorithm implementations.

Hello everyone!
I’ve got accepted to this year’s Google Summer of Code and from today I will be blogging about my progress, problems and performance analysis of darcs.
My project is about enhancing record command in different aspects. I have my mentor Guillaume Hoffmann that is going to help me and I hope to get things done right and make a good use of the time given to me for the project.
In the first weeks i will be implementing, testing, and profiling the patience diff algorithm in Darcs.

Stay tuned!!

News and discussions

1. Google Summer of Code 2013 has begun! BSRK and José will post updates on their blogs:
   
   • http://bsrkaditya.blogspot.com/search/label/darcs
   • http://blog.jlneder.com.ar/search/label/darcs

Issues resolved (8)

issue2163 Radoslav Dorcik

• new option for amend, select author for patch stealing.
• http://bugs.darcs.net/issue2163

issue2227 Ganesh Sittampalam

• move the rebase patch to the end before an amend-record
• http://bugs.darcs.net/issue2227

issue2248 Ganesh Sittampalam

• always clean up rebase-in-progress state
• http://bugs.darcs.net/issue2248

issue2250 BSRK Aditya

• tabbing in usageHelper - pad by max length of command name
• http://bugs.darcs.net/issue2250

issue2311 Sebastian Fischer

• posthook for 'get' should run in created repo
• http://bugs.darcs.net/issue2311

issue2312 Sebastian Fischer

• posthooks for 'record' and 'amend-record' should receive DARCS_PATCHES
• http://bugs.darcs.net/issue2312

issue2320 Jose Luis Neder

• save prompted author name in ~/.darcs/author instead of ./_darcs/prefs/author
• http://bugs.darcs.net/issue2320

issue2321 Jose Luis Neder

• when no patch name given, directly invoke text editor
• http://bugs.darcs.net/issue2321

Patches applied (20)

2013-06-09 Guillaume Hoffmann

• make nano the default text editor instead of vi

2013-06-20 BSRK Aditya

• Resolve issue2250: tabbing in usageHelper - pad by max length of command name

2013-06-16 Guillaume Hoffmann

• remove word repetition in fileHelpAuthor string

2013-06-16 Jose Luis Neder

• resolve issue2320: save prompted author name in ~/.darcs/author instead of ./_darcs/prefs/author
• resolve issue2321: when no patch name given, directly invoke text editor

2013-04-30 Guillaume Hoffmann

• remove repository flag DryRun parameter when not used or always NoDryRun

2013-04-05 Ganesh Sittampalam

• fix test for Windows

2013-03-10 Sebastian Fischer

• Follow-up on patch1066 resolving issue2312.
• resolve issue2312: posthooks for 'record' and 'amend-record' should receive DARCS_PATCHES
• Added tests for issue2312: posthooks for 'record' and 'amend-record' should receive DARCS_PATCHES

2013-02-16 Ganesh Sittampalam

• resolve issue2227: move the rebase patch to the end before an amend-record
• tidy command definitions in Darcs.UI.Commands.Rebase
• resolve issue2248: always clean up rebase-in-progress state
• add --ignore-times option to rebase commands that read the working dir

2013-03-08 Sebastian Fischer

• resolve issue2311: posthook for 'get' should run in created repo
• Added tests for Issue 2311.

2013-06-03 Guillaume Hoffmann

• haddocks for functions that look for user e-mail

2013-03-02 Radoslav Dorcik

• Resolve issue2163: new option for amend, select author for patch stealing.

2013-05-29 BSRK Aditya

• Export doOptimizeHTTP from Optimize module
• Increase efficiency of patch index update by more efficient extraction

See darcs wiki entry for details.