planet

Patch-tag is now https safe, so you can access your projects with cryptographic security. Just use https style urls when interacting with patch-tag.

By the way — for you code shops with mission critical, high-value, national security endangering repos hosted at patch-tag — https isn’t completely safe.

You could, for instance, get your password sniffed by a man in the middle attack with arp poisoning, if you are in a public network like an internet cafe, or on a trusted network with a coworker who enjoys hanky panky.

There is a simple thing you can do to foil the terrorists though — just click outside the text fields and type some gibberish when you are entering your password.

Ha! Take that script kiddies!

Please enjoy secure repos at patch tag, and as always…

Happy tagging.

One of the great things about distributed version control is that you can unplug from the internet and keep checking in.

If you recreate your gitit wiki offline, you can unplug from the internet and keep interacting with your repository via your offline gitit wiki.

Here’s a newsgroup discussion that describes how to use your gitit wiki offline

Disclaimer: If you are not technically savvy, and using patch-tag only for the gitit wiki, this option is probably not for you. I have some ideas percolating though that might make this a lot more straightforward if having an offline gitit wiki is something people want.

Patch Tag has a bug tracker, an anonymously editable gitit wiki hosted at patch-tag.

Full details at the mailing list, where I made the announcement.

I've taken, with a tiny bit of prodding, the Token Stream Diffs Using Pygments from toy to a nascent toolchain that may even almost be useful.

I've brought in two new dependencies Google diff-match-patch and, for nice argument parsing, argparse. The diff-match-patch library provides a character-based diff algorithm and patch format (a character-based unidiff-like format with character escaping) in a number of languages, including my friend Python. I can use diff-match-patch to produce useful patch output (and apply said patches with a simple new tokpatch.py file that is but a wrapper around diff-match-patch patching).

tokdiff.py has grown three new output formats. The original "toy" format I've renamed "verbose" and its quite interesting for debugging and getting an idea of why diffs look the way they do. Most useful, and the new default, is the unidiff-like output. There's also diff-match-patch's much more compact tab-delimited "delta" format, which is interesting, but I don't think is all that safe. (It's an undocumented, outside of the code itself, feature...)

The final output format is the "compare" which outputs some pretty HTML visually showing the differences between the tokenized diff approach and diff-match-patch's standard character-based diff, plus some basic benchmarking of the two algorithms.

Both tools and both dependencies can be grabbed from the darcs repository:

darcs get http://repos.worldmaker.net/tokdiff/main tokdiff

I'll consider putting together a deeper code site for it in the near future.

Some brief observations and thoughts for future directions:

• I shouldn't be too surprised by it, but the tokenized diff does generally seem to be an order of magnitude faster than diff-match-patch's more generalized character-based diff algorithm.
• I think there are still some interesting heuristics that can be further applied to make the tokenized diff even smarter. I'm not sure how exactly to start on that (I've been lucky to get as far as I have on the backs of existing diff algorithms).
• I'd like to experiment with darcs-like patch selection UI using the tokenized diffs; particularly using the existing tokenization for syntax highlighting.
• I'd like to know if anyone finds interesting real applications of this quick hack.

I have been doing some python brush-up over the last couple of days, and came across the following bit of code in an irc chat about approaches for fibonacci in python.

def fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return a
print fib(1000)

I think this is pretty typical, reasonable, and efficient python code.

I wondered, how would I express this in haskell? How different this computation looks from the canonical

fibs = 1:1:zipwith (+) fibs (tail fibs)

!

The answer, as is commonly the case for code written in imperative languages, is that this algorithm lives in the state monad. It can be ported to haskell, practically transliterated, as:

import Control.Monad.State
{-
-- haskell translational of python algo
def fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return a
print fib(1000)
-}
fib :: Integer -> Integer
fib n = flip evalState (0,1) $ do
  forM (xrange n) $ \_ -> do
    (a,b) <- get
    put (b,a+b)
  (a,b) <- get
  return a 

xrange n = [0..(n-1)]

-- test that it works
traditionalFibs' = 1: 1: (zipWith (+) traditionalFibs' (tail traditionalFibs'))
traditionalFib n = traditionalFibs' !! (n-1)

t = fib 1000 == traditionalFib 1000

Also added this to hawiki at

http://www.haskell.org/haskellwiki/The_Fibonacci_sequence#With_state

Patch-Tag is getting closer to a place where I’d feel comfortable charging for it, but there are a couple of things I need to take care of first.

First, I want to be more confident that I can scale this service out if I start getting a lot more users. It needs to be rock solid. No more downtime, no more crashes. This will definitely involve code tweaks for places that use unjustifiably large amounts lot of memory, and may (or may not — haven’t decided yet) mean infrastructure changes.

Second, Patch Tag already does backups but I am going to revisit this process one more time to convince myself that this is as rock solid as it can get.

Happy belated thanksgiving everyone. There will be some more interesting news soon, I am feeling sure!

The Darcs Hacking sprint was co-located in Vienna, Austria and Portland, Oregon, USA.

The Vienna team had a unique experience as the sprint happened to coincide with a student protest that resulted in an occupied University building. Great fun was had by all as we shared our hacking space with the Occupiers on Saturday.

The Portland team was graciously hosted by Galois. As a special treat, we got a visit from Thomas Hartman, one of the folks behind Patch-tag.

Hacking

Studying darcs

Thomas DuBuisson and Jason Dagit studied some hanging merge cases on the GHC repository to see if we could garner some insights into them. While this did not yield much fruit, it did result a few code cleanups.

Jonathan Daugherty and Josh Hoyt took a tour of the Darcs source. We hope they'll be joining us as Darcs hackers in the future :-)

Jason Dagit produced a concrete and low-level description of the Darcs record command.

Code cleanups

As a warm-up exercise, everybody worked on tidying the Darcs and hashed-storage source, eliminating annoying GHC warnings and implementing suggestions from hlint.

Tomáš Caithaml simplified the darcs show authors authorspellings code by rewriting it in Parsec.

Jason Dagit cleaned up the elegant_merge function and removed commutex in favor of commute.

Jonathan Daugherty submitted some improvements to the user manual.

Performance improvements

Luca Molteni improved Darcs's handling of the global cache, splitting it into buckets for better performance.

User interface improvements

Tomáš Caithaml got darcs convert to abort in case user accidently tries to convert a darcs 2 repository a second time.

Roman Plášil improved the user experience behind Darcs progress reporting replacing misleadingly definitive text with a more accurate description as shown in the following example :

                           OLD TEXT    NEW TEXT
Fetching pristine cache... 4/45        4 done, 41 queued
(sometime later)...        10/166      10 done, 155 queued
(finally)...               297/297     297 done

Christian Berrer extended the darcs optimize --upgrade command to also act as plain old darcs optimize in addition to upgrading the repository format.

David Markvica modified darcs get --complete so that it no longer offers to create a lazy repository.

Benedikt Huber relaxed the assumption that darcs executable would be called "darcs", instead fetching this from the command line.

New features

Matthias Fischmann and Radoslav Dorcik worked on a new trackdown --bisect feature for darcs trackdown which makes trackdown more useful for larger sets sets of patches.

Roman Plášil implemented an oft-requested remove -r feature, making it easier to undo accidental adds of large directories.

Luca Molteni implemented darcs show files with an argument to limit the output to a specific file or directory.

Thomas Hartman implemented matchers support for darcs show files, allowing to get the list of files tracked by Darcs at a given point in the history (eg. darcs show files --tag 2.4).

Petr Ročkai worked on a new more extensible, self-documenting format mechanism as a future alterantive to _darcs/format.

UTF-8 Support

Reinier Lamers continued his work on storing darcs patch metadata in UTF-8. He worked on autodetecting UTF-8 content (in the patch metadata) and found some subtle bugs in the utf8-string library along the way.

SVN integration

The Vienna local team, Christian Berrer, Thomas Danecker and David Markvica, worked on SVN integration and studied the libsvn directory in great detail.

Zero Windows Bugs!

Salvatore Insalaco slayed the 18 Windows bugs that resulted from our recent hashed-storage work. This means that we can can definitely release the new hashed-storage work in Darcs 2.4.

Darcs Team infrastructure

Joachim Breitner made some improvements to the darcswatch core and user interface. He also added hooks to Darcswatch for integration with Darcs Team patch tracker. Joachim Breitner, Eric Kow, Petr Ročkai also added some polish to patch tracker, in particular to its email gateway interface and interaction with the darcs-users mailing list. The result of these efforts is a more efficient Darcs Team with simpler and smoother patch review process.

Kim Wallmark worked on making the 'cabal test' friendlier by outputting the amount of time elapsed after long tests.

Attendees

Vienna

1. Joachim Breitner
2. Benedikt Huber
3. Eric Kow
4. Reinier Lamers
5. David Markvica
6. Petr Rockai
7. Radoslav Dorcik
8. Salvatore Insalaco
9. Matthias Fischmann
10. Thomas Danecker
11. Christian Berrer
12. Luca Molteni
13. Roman Plášil
14. Tomáš Caithaml
15. Pivo

Portland

1. Jason Dagit
2. Josh Hoyt
3. Thomas Hartman
4. Thomas DuBuisson
5. Kim Wallmark
6. Jonathan Daugherty

I’m keeping this one brief… Matt Elder has decided that it’s time to move on from patch-tag, in order to focus on other projects and the new addition to his family.

Thanks for all the good work, Matt. Patch-tag wouldn’t have
gotten this far without you.

I am in the process of migrating patch-tag to the latest version of happstack, and I thought I would post some diffs to aid others who have the same task.

This probably isn’t of much interest unless you are actually faced with a migration — but if you are, could save you some time and starting at compile complaints.

<                       happstack-data == 0.1,
<                       happstack-helpers == 0.11,
<                       happstack-ixset == 0.1,
<                       happstack-server == 0.1,
<                       happstack-state == 0.1,
<                       happstack-util == 0.1,
---
>                       happstack-data == 0.3.3,
>                       happstack-helpers == 0.30,
>                       happstack-ixset == 0.3.2,
>                       happstack-server == 0.3.3,
>                       happstack-state == 0.3.3,
>                       happstack-util == 0.3.2,

notice msum

< controller pubdom privdom ts dynamicTemplateReload realEmail wikitmpl mime useGoogAnalytics =
<    (staticfiles ++)
---
> controller pubdom privdom ts dynamicTemplateReload realEmail wikitmpl mime useGoogAnalytics =
>     msum [ staticfiles

notice ReaderT

< mainController pubdom privdom ts' dynamicTemplateReload realEmail wikitmpl mime ga =
<        [ ServerPartT $ \rq -> do
---
> mainController pubdom privdom ts' dynamicTemplateReload realEmail wikitmpl mime ga =
>        ServerPartT $ ReaderT $ \rq -> do

notice s/unserverPartT/runServerPartT/

<   unServerPartT ( multi $ mainCommon pubdom privdom (RenderGlobals rq ts mbSession ga) mailFx wikitmpl mime) rq
<   ]
---
>   runServerPartT ( msum $ mainCommon pubdom privdom (RenderGlobals rq ts mbSession ga) mailFx wikitmpl mime) rq

 </code></pre>

 

To get the most out of the following blog post, first try writing your partition function, which does the same thing as Data.List.partition.

*Partition> partition even [1..10]
([2,4,6,8,10],[1,3,5,7,9])

Then write a testing function, tpf, which checks your partition function against a variety of input, including large or infinite input. (Which means we don’t just use quickcheck).

Then read the blog post to see what obstacles I hit when I went through this process.

source here if you’re irked by wordpress aggressively cutting off the right side of the page.

{-# LANGUAGE NoMonomorphismRestriction #-}
module Partition where
import Debug.Trace.Helpers
import qualified Data.List as DL
import Debug.Trace

-- first attempt
partition f [] = ([],[])
partition f (x:xs) =
  let (as,bs) = partition f xs
  in  if (f x) then (x:as,bs) else (as,x:bs)
t1 = tpf partition 

-- testing function.
tpf partif =
      let a = last . snd . partif even $ [1..(10^6)]
          b = head . snd . partif even $ [1,2..]
          c = last . snd . partif even $ [1..(10^8)]
       in (a,b,c)

-- sanity checks / benchmarks. our own code should be at least as fast as Data.List versions.
-- a is immediate, b is immediate, c takes about 10 seconds.
tDL = tpf DL.partition

-- a test and b test are fine but that 10^8 list seems to take forever.
-- let's think about this. What algorithm are we using?
-- Actually, I don't know the answer to that.
-- but looking at that let/in, I don't have a clear sense of crunching through a list and building up a result, which is usually the ideal.
-- So let's try this with a fold.

-- Next question, what kind of fold?
-- Easy answer: just try both and see what happens!
-- Once you've written one, you have the other just by flipping the arguments in the helper function 
-- (Note: for the foldl, we try strict foldl' by default, as there is usually no reason to use lazy foldl:
-- http://haskell.org/haskellwiki/Foldr_Foldl_Foldl'
partitionR f xs = foldr g ([],[]) xs
  where g next accum@(as,bs) = if f next then (next:as,bs) else (as,next:bs)
partitionL' f xs = DL.foldl' g ([],[]) $ reverse xs
  where g accum@(as,bs) next = if f next then (next:as,bs) else (as,next:bs)
-- Harder answer, which requires thought: we probably want a foldr here, because the b test uses an infinite list and a strict fold
-- won't return anything if you feed it an infinite list.

-- OK, let's try foldr
t2 = tpf partitionR -- result: immediate stack overflow on the a test, and if you try them separately, it overflows all 3 tests.
                    -- that's kind of sad.

-- for no particular reason, let's try a strict foldl version (warning! be careful running this!)
t3 = tpf partitionL'
  -- at least the a test succeeds after a few seconds, confirming the intuition that strict foldl' crunches through a list
  -- and returns output after it's done.
  -- the b test exhausts computer memory, eventually the fan starts whirring louder than I can think, mouse stops responding and have to reboot
  -- so like I said, careful running this, and hit control c!

--okay, I give up, let's peek at the standard libs (SL) Data.List
-- this isn't word for word what the ghc standard libs Data.List has, so as to be more similar to the functions we wrote so far,
-- but it's the same algo, and same performance.
-- the important difference is the lazy match
partitionSL p xs = foldr g ([],[]) xs
  where g next accum = if (p next) then (next:fst accum,snd accum) else (fst accum, next:snd accum)
        -- which is the same as below, using irrefutable pattern syntax:
        -- g next ~accum@(as,bs) = if (p next) then (next:as,bs) else (as, next:bs)
-- Sure enough, same performance as Data.List.Partition
-- Note: to get the same performance as lazy list, you need to compile the module before loading in ghci, eg
-- ghc --make PartitionM.hs, then ghci PartitionM
-- if you do ghci PartitionM.hs, this doesn't terminate (at least, not in under a minute I'm an impatient guy.)
tSL = tpf partitionSL

-- So, why does partition need an irrefutable pattern in the accum argument?
-- Let's look at the original right folded partition again, rewritten as follows, for a 3 element list

partitionR2 f xs = foldr (select f) ([],[]) xs
select f next accum@(as,bs) = if f next then (next:as,bs) else (as,next:bs)
-- select' g next accum = if (p next) then (next:fst accum,snd accum) else (fst accum, next:snd accum) 

tpr2 :: ([Int],[Int])
tpr2 = partitionR even [1..3]
tpr2a = 1 `g` ( 2 `g` ( 3 `g` ([],[]) ) )
g = select even

-- when the accum argument to select is a strict pattern match, the algorithm can't proceed past the first element
-- without evaluating everything inside the first set of parenthesis.
-- For a million element list, this is going to be a problem.
-- if the accum arg is lazy (just accum without the @ binding), the algorithm can proceed to the if test,
-- calculate the tuple with the list parts as just a thunk to be evaluabed later, and keep chugging along,
-- by calculating the list parts next.

It is said that in haskell, If it Compiles, It Works.

This is true, but what do you do when it won’t compile?

I came across a real world scenario for this just now, when I was in the process of removing the HStringTemplateHelpers dependency from happs tutorial. The reason for this is that HStringTemplateHelpers uses the unix package (indirectly, via FileManip), which means that at the present time happs tut won’t run on windows, which lately has me smacking myself like dobby the masochistic house elf in the harry potter movies.*

The dependency wasn’t in one file, but scattered throughout the code. Some places, the dependency wasn’t that important, I could just comment the function out, but in other cases the function was core to the app and commenting it out caused cascading compile failures. Doing the type/function arithmetic in my head for figuring out what depended on what was giving me a headache and tempting me to veg out on youtube rather than face the problem, always a warning sign for me that I’m doing something wrong.

I needed to make my program compile, just so I could think about it with my head screwed on straight.

So, instead of commenting out the HStringTemplateHelpers-dependent functions, I set them equal to undefined and commented out their type signatures (since the type sig might be using a type that was defined in the dependency.


-- paintProfile :: RenderGlobals -> String -> UserProfile -> String -> String
paintProfile rglobs user cp userimagepath = undefined {-.....-}


A few comment-outs later and cabal install compiles! Of course, if I actually try running the resulting binary, I will hit an undefined error right away, but the point is that I can think again, and start rewriting my offending functions in a methodical way until there are no more undefineds, which is easly checked with

grep -irn undefined src

For what it’s worth, I could have also used

paintProfile rglobs user cp userimagepath = error "paintProfile uses HStringTemplateHelpers... bad dobby! bad dobby! Dobby will have to shut his ears in the oven door for this."

But whatever

* I suppose the righter thing to do would be to fix FileManip, but I am choosing the easy way out just to get it done. Eventually I woud like to move away from HStringTemplate with happs and use mostly Text.XHTML and/or HSP, which is type safe, which HSTringTemplate just thrown in for convenience and newb friendliness.

I wanted to have a look at the latest happstack release, and noticed the documentation still wasn’t available on haddock.

http://hackage.haskell.org/package/happstack

It wasn’t available locally either, when I did cabal install happstack-server. In fact, haddock was not available offline for anything.

To get the haddocks locally, I edited ~/.cabal/config, setting

Documentation: True

(and uncommenting that line by removing the starting –)

After this, cabal install –reinstall built the documentation in

.cabal/share/doc/happstack-server-0.3.3/html/

handy

But shouldn’t this flag be on by default?

UPDATE:

cabal haddock –hyperlink-source

installs documentation with links to source code, which imho should also be on by defualt.

cabal install –haddock-options=–hyperlink sourceblehblehbleh

doesn’t throw an error. without the blehblehbleh it runs, but doesn’t install with source links, which seems like a bug to me.

News and discussions

1. Work on hashed-storage, implemented by Petr and reviewed by Ganesh, was finally merged into the main darcs repository. Eric provided explanations for people who want a faster darcs now:

• http://lists.osuosl.org/pipermail/darcs-users/2009-October/021826.html

• http://lists.osuosl.org/pipermail/darcs-users/2009-September/021642.html

3. Jason investigated on performance of the current implementation of regular expression handling:

• http://lists.osuosl.org/pipermail/darcs-users/2009-October/021721.html

4. Eric talked about Summer of Code 2010 and how to raise our chances to have someone paid to work on darcs again next summer:

• http://lists.osuosl.org/pipermail/darcs-users/2009-October/021761.html

Issues resolved in the last week (5)

issue1447 mf-hcafe-15c311f0c

• different online help for send/apply --cc
• http://bugs.darcs.net/issue1447

issue1488 Petr Rockai

• darcs-hs does not suffer from this.
• http://bugs.darcs.net/issue1488

issue1583 Eric Kow

• on darcs get, suggest upgrading source repo to hashed.
• http://bugs.darcs.net/issue1583

issue1618 Kamil Dworakowski

• 1618: preserve log on amend failure
• http://bugs.darcs.net/issue1618

issue1620 Kamil Dworakowski

• amend lies about living logfile
• http://bugs.darcs.net/issue1620

Patches applied in the last week (108)

The following is a copy of my recent post to the darcs-users mailing list.

Hi everybody,

So you may have noticed me saying this in a couple of recent threads. Petr Ročkai's hashed-storage work from his 2009 Google Summer of Code project has been merged!

I thought I would take a few moments to give everybody an overview of how this work benefits us, and where we'll be going in the future.

darcs get --lazy http://darcs.net
cd darcs.net
cabal install

News and discussions

1. darcs 2.3.1 was released, including bug fixes for windows and documentation improvements:

• http://blog.darcs.net/2009/09/darcs-231-better-docs-less-bugs.html

2. The date and location for the next Darcs Hacking Sprint have been set at 14-15 november, Vienna:

• http://lists.osuosl.org/pipermail/darcs-users/2009-September/021559.html

3. Ganesh's hunk editing patch has been applied in the main branch of darcs. Please help up test and improve this feature!

• http://lists.osuosl.org/pipermail/darcs-users/2009-September/021487.html
• http://lists.osuosl.org/pipermail/darcs-users/2009-September/021590.html

Issues resolved in the last week (3)

issue291 Ganesh Sittampalam

• add (basic) interactive patch splitting
• http://bugs.darcs.net/issue291

issue1478 Trent W. Buck

• document summary mnemonics.
• http://bugs.darcs.net/issue1478

issue1584 Eric Kow

• Provide optimize --upgrade command.
• http://bugs.darcs.net/issue1584

Patches applied in the last week (33)