Haskell - Lazy IO

Ces derniers jours, j’écrivais un script haskell qui repĂšre les fichiers prĂ©sent en double, et propose de ne conserver qu’un exemplaire. TrĂšs pratique pour faire un peu de rangement, par exemple parmi une centaine de PDF que je ne lirais jamais.

Je vais ici vous parler de la phase de hachage des fichiers pour les trier et déterminer les doublons. Et oui, on ne vas pas comparer le contenu de tous les fichiers entre eux, ça serait en n^2 par rapport au nombre de fichiers. On ne veux pas non plus attendre une journée.

Je parlerais donc de la lecture du contenu des fichiers pour produire leur hash. Le trie des paires (Nom du fichier, hash) et l’affichage Ă©tant trivial et sans intĂ©rĂȘt.

Strict IO ?

La premiùre approche est souvent la plus simple. Nous voulons le hash d’un fichier? Et bien il suffit d’utiliser la fonction hash :: String -> ByteString du package Crypto.Hash.SHA1 (SHA1, MD5, MD4, SHA256 
 celons vos gouts). Pour obtenir le contenue du fichier, on peux utiliser readFile :: FilePath -> IO String.

Cela nous donne :

getHash :: String -> (String, ByteString)
getHash filename = do
    hashed <- fmap hash $ readFile filename
    return (filename, hashed)

Il suffit alors d’appliquer mapM getHash sur une liste de nom de fichier pour obtenir une liste de couple Nomdufichier/Hashdufichier.

Si l’on test, cela fonctionne trĂšs bien
 jusqu’au moment oĂč vous tombez sur un fichier de plus d’1GO. LĂ , readFile veux charger l’intĂ©gralitĂ© du fichier en mĂ©moire. Et bien-sur, sur ma machine, c’est impossible.

La paresse a la rescousse!

On vous Ă  toujours dis qu’ĂȘtre paresseux, c’était mal, improductif, et vous mĂšnerais Ă  votre perte? Et bien, ils avaient tort.

On voudrais lire le fichier par morceau, et construire le hash avec ces morceaux (ce que toute bonne fonction de hachage permet).

Pour ce qui est du hachage, on trouve dans Crypto.Hash.Whatever les trois fonctions :

init :: Ctx
update :: Ctx -> S.ByteString -> Ctx
finalize :: Ctx -> S.ByteString

Il nous faut donc un flux de ByteString. Pour ce faire, on dispose d’une version paresseuse de ByteString, qui se trouve dans le package Data.ByteString.Lazy. Histoire de fixer les notations et de ne pas se perdre entre les ByteString strict et les ByteString lazy, on parlera respectivement de S.ByteString et de L.ByteString (Strict/Lazy).

Cela revient a importer les deux types de la façon suivante :

import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L

Le type L.ByteString est en fait une liste de S.ByteString, et chaque bloc ne sera lu depuis le fichier qu’au moment oĂč il sera utilisĂ©. Le module L nous offre donc gentiment les fonctions

L.readFile :: FilePath -> IO L.ByteString
L.foldlChunks :: (a -> S.ByteString -> a) -> a -> L.ByteString -> a

La premiĂšre nous donne le contenue de notre fichier. La seconde, nous offre exactement la mĂ©thode qui “prend une fonction ajoutant un morceau de fichier au hash”, puis “un hash vide”, et enfin “une ByteString paresseuse”. Cela parais plus Ă©vident si l’on spĂ©cialise les “a” en “Ctx”.

On peux donc utiliser :

hashed <- fmap (finalize . foldlChunks update init) $ readFile filename

Bon, en fait, il y avais plus simple. Il y a aussi la fonction :

hashlazy :: L.ByteString -> S.ByteString

qui produit le mĂȘme rĂ©sultat que notre pli.

Et lĂ  tout fonctionne bien, nos fichier d’1Go sont hachĂ©.

Mais 
 si vous travaillez sur beaucoup de fichiers, vous risquez d’avoir un soucis. Par exemple, si vous testez sur /usr/lib, vous obtiendrez peut-ĂȘtre une jolie exception vous indiquant qu’il y a trop de filedescriptors utilisĂ©s, et que donc le fichier ne peux ĂȘtre ouvert. Il se trouve que les fichier ne sont pas fermĂ© immĂ©diatement aprĂšs le hachage, et c’est un vrai problĂšme. ProblĂšme que nous allons rĂ©soudre.

La solution : withFile

La fonction withFile :: FilePath -> IOMode -> (Handle -> IO r) -> IO r est la clef. Cette fonction prend un nom de fichier, le mode d’ouverture (on utilisera ReadMode), une fonction qui travaille sur le fichier, et nous fait suivre le rĂ©sultat de l’application de cette fonction. Un peu stupide, me direz vous? Et bien, ça le serait, si cette fonction se contenter de ça. En fait, elle vous assure aussi qu’une fois Ă©valuĂ©e, le fichier est fermĂ©. En l’utilisant, on est donc certain que le fichier est immĂ©diatement fermĂ© lorsque withFile est Ă©valuĂ© en un “IO r”.

getHash filename = do
    hashed <- withFile filename ReadMode $ \h -> do
        fmap hashLazy $ L.hGetContents h
return (filename, hashed)

Le unefonction $ \h -> do est une pratique courante pour ces fonctions qui Ă©value un morceau de code dans un certains contexte. C’est trĂšs pratique, et on reconnaĂźt trĂšs vite cette idiome avec un peu d’entraĂźnement.

On compile pour vĂ©rifier le typage, tout vas bien, et l’on lance donc notre application que l’on s’attend a voir fonctionner. Et lĂ , c’est le drame : “Illegal operation : handle is closed”.

Wohw, quel est ce mystĂ©rieux message? Et bien, comme je vous l’ai dit, withFile ferme immĂ©diatement le fichier aprĂšs l’évaluation de son expression. Et que fait son Ă©valuation? Elle retourne le hash du fichier me dite vous? Faut.

La fonction construit un thunk (je parlerais de promesse de calcul, ou plus simplement de promesse) a l’aide de “fmap 
”. L’évaluation de withFile retourne alors cette promesse, plutĂŽt que la valeur du hash. Et cette promesse, elle, ne sera Ă©valuĂ©e que plus tard, au moment ou vous en aurez vraiment besoin, et seulement si vous en avez besoin.

Il nous faut donc forcer haskell a ĂȘtre strict, et Ă©valuer le hash avant de sortir de la fonction. Il y a diffĂ©rentes façons de le faire. La plus simple, c’est d’utiliser l’opĂ©rateur `seq` qui force l’évaluation de l’expression a sa gauche, puis retourne l’expression a sa droite. On a aussi l’opĂ©rateur a ($!) b = b `seq` (a b) qui est une “application stricte”. C’est a dire que ce qui sera a droite de $! sera Ă©valuĂ©.

Nb : Il faut faire attention. Quand je dis Ă©valuĂ©, je parle bien de dĂ©-construire le premier niveau de l’expression. C’est a dire que si compute 1 42 est un calcul, ceci sera remplacer par la promesse ou le rĂ©sultat retournĂ©e par compute. Si compute produit une promesse plutĂŽt qu’un rĂ©sultat, l’opĂ©rateur `seq` n’évaluera pas la promesse. Il existe un opĂ©rateur `deepSeq`, qui lui vas tout rĂ©duire en profondeur. Comme vous vous en doutez, c’est trĂšs coĂ»teux et Ă©value des choses dont on n’auras peut-ĂȘtre pas besoin. Le plus souvent, on peux se contenter de `seq` appliquĂ© au bonne endroit pour obtenir le rĂ©sultat souhaitĂ©.

Dans notre cas, il faudrait forcer la promesse faire par fmap a ĂȘtre Ă©valuĂ©e, puis la promesse faite par hashlazy. Vous allez voir que la solution n’est pas plus compliquĂ©e que ce que nous avions dĂ©jĂ  Ă©crit :

-- getHash ...
    withFile filename ReadMode $ \h -> do
        -- On obtient la promesse faite par hashlazy
        data <- fmap hashlazy $ hGetContents h
        -- On force l'évaluation de hashlazy, qui donc sera forcé d'ouvrir le fichier et de le lire, puisque la valeur retournée est un S.ByteString, une valeur Stricte.
        return $! data

Voila, c’est tout, c’est $! qui fait tout le travail en demandant Ă  hashlazy de gentiment s’évaluer.

Et la c’est le bonheur, tout refonctionne et l’on peux gĂ©rer des fichiers arbitrairement grand en nombre arbitrairement grand, le tout en 4 lignes.