DM 1: find

Compilé le 4 janvier 2006

DM 1: find

Si vous redéposez: avant le jeudi 5 février, 18h00.

(Voir la section correction)

Cette page sera mise à jour. Il convient d'en vérifier les informations de temps en temps, notamment avant la remise du DM. 50(Dernière mise à jour le4 janvier 2006)

Sujet

Il s'agit d'écrire en OCaml la commande find présente sur la plupart des système Unix. Toutefois, on va généraliser ce travail en ne se fixant pas uniquement comme objectif l'écriture d'une commande find mais également l'écriture d'une bibliothèque OCaml fournissant les fonctionnalités de find aux programmes OCaml.

1 Exercice

Pour se mettre en jambe, on pourra commencer par résoudre l'exercice 4 du TD 1 que l'on rappelle ici. Cet exercice n'est pas strictement demandé, et n'est pas à remettre, mais il permet d'avancer progressivement et la plupart des parties serviront soit à la réalisation de la bibliothèque soit à la réalisation de la commande finale find demandée.

1) Donner des exemples de requêtes avec la la commande find d'Unix (man find) permettant d'exécuter les opérations suivantes:

afficher tous les chemins accessibles depuis le répertoire courant,
afficher tous les chemins accessibles depuis le répertoire courant qui correspondent à des répertoires,
afficher tous les chemins accessibles depuis le répertoire courant qui correspondent à des répertoires et qui ont une profondeur inférieure à 2 dans l'arborescence,
afficher tous les chemins accessibles depuis le répertoire home qui correspondent à des fichiers réguliers qui ont été accédés il y a 2 jours.

2) Écrire une première commande mon_find0 équivalente à find . -maxdepth 1.

3) Écrire une seconde version mon_find1 qui prend en argument une profondeur p et affiche la liste des chemins accessibles depuis le répertoire courant avec une profondeur inférieure à p.

4) Implanter les comportements équivalents aux options :

-maxdepth,
-type,
-atime,
-follow,
-regexp.

Pour réaliser cette commande, on pourra utiliser le module Arg pour récupérer les arguments de la ligne de commande et le module Str (à charger explicitement) pour manipuler les expressions régulières.

Pour l'option -atime, le

Une fonction bibliothèque

La commande Unix find prend ses arguments sur la ligne de commande. Tous ses arguments sont des chaînes de caractères qu'il faut interpréter. En fait, elle prend deux types d'arguments : des options et un ensemble de chemins qui sont les racines à partir desquels mener la recherche.

En bibliothèque, nous pouvons regrouper les arguments dans des listes, en fait les deux groupes d'arguments dans deux listes différentes : une liste de filtres et une liste de chemins racines. Le type à utiliser pour représenter les filtres est le suivant :

Le sens de chaque filtre est le même que dans l'exercice précédent.

L'argument follow demande de suivre les liens symboliques, ce qui n'est pas le cas par défaut. En présence de l'option -follow on gardera trace (de l'identité) des répertoires déjà visités de façon à ne pas les visiter plusieurs fois: lorsqu'un lien symbolique mène à un répertoire déjà visité, on affichera le lien mais on ne le suivra pas.

Le type intervalle permet de représenter des valeurs respectivement «inférieure ou égale» (Le), égale (Eq), et supérieure ou égale (Ge) à l'entier donné en argument. L'unité de temps est 24 heures. La commande Unix find utilise −n, n et +n pour spécifier respectivement les valeurs (Le n), n et (Ge n). En fait, find utilise des inégalités strictes, mais nous utiliserons des égalités larges (incluant l'égalité) ici, afin de rester compatible avec les versions précédentes du sujet.

Le nouveau filtre Predicate prend en argument une fonction qui est appliquée au chemin et qui indique s'il faut garder ce chemin (à la manière de Regexp). Par exemple,

Predicate (fun d -> Sys.file_exists (Filename.concat d "CVS"))

permet de filtrer les répertoires CVS (i.e. les répertoires qui contiennent un sous-répertoire CVS)¹.

La recherche peut produire des erreurs. Pour contrôler le comportement en cas d'erreur, on utilise le type mode suivant:

type mode = | Ignore | Stderr | Failure | Custom of (Unix.error * string * string -> unit)

Dans le mode Ignore, les erreurs sont simplement ignorées et le calcul de find sur le reste de la hiérarchie est poursuivi. Le mode Stderr fonctionne comme le mode Ignore à part qu'il imprime un message d'erreur sur la sortie d'erreur. Dans le mode Failure, le calcul est abandonné dès la première erreur et elle est reportée immédiatement à l'utilisateur. Le mode Custom utilise la fonction fournie au constructeur pour traiter l'erreur.

Bien sûr, quel que soit le mode, il faudra s'assurer que les structures ouvertes auront bien été refermées afin de laisser le processus dans un état similaire à ce qu'il était avant l'appel (les répertoires ouverts devront être fermés, ...).

Lorsque find n'est plus une commande Unix, mais une fonction de bibliothèque, il n'est plus nécessaire de retourner les résultats dans la sortie standard (typiquement le terminal), et il est préférable de les retourner en mémoire, par exemple dans une liste. Mieux, on peut abstraire la fonction par rapport à ce que l'on veut faire sur les résultats, par exemple comme le fait la fonction List.iter dans un parcours de liste.

Finalement, la fonction find aura le type suivant:

val find : mode -> string list -> filter list -> (string -> unit) -> unit

où find m r p f recherche récursivement les chemins issus d'une des racines r satisfaisant les filtres p et applique f au fur et à mesure que les chemins sont trouvés.

Pas exemple, l'appel:

find Stderr [ "." ] [] print_endline

imprime l'ensemble des résultats comme le ferait la commande «find .».

Enfin, on pourra utiliser l'option Custom pour collecter l'ensemble des messages d'erreurs par exemple en les cumulant dans une référence.

1) Implémenter la bibliothèque find.ml satisfaisant l'interface find.mli et la sémantique décrites ci-dessus.

2) Écrire le programme mon_find de la question 4) de l'exercice ci-dessus en utilisant la bibliothèque find.ml. Le programme mon_find ne reconnaît donc que les options de la question 4) de l'exercice. En particulier n'a pas d'option équivalente à l'option Predicate de la librairie. De même, le mode de fonctionnement de la commande mon_find n'est pas passé en argument et correspond au mode Stderr.

À rendre

Une archive contenant deux fichiers find.ml et un fichier mon_find.ml dans un répertoire ayant comme nom votre login.

Le fichier find.ml devra respecter l'interface find.mli.

Le fichier mon_find.ml devra permettre de fabriquer le programme mon_find par la ligne de commande:

ocamlc -o mon_find unix.cma str.cma find.mli find.ml mon_find.ml

Procédure de dépôt

Se placer dans le répertoire de dépôt:

cd /users/profs/info/INF552
Invoquer la commande de dépôt:

./deposer-DM1 <chemin>/find.ml <chemin>/mon_find.ml

où <chemin> est un chemin absolu qui mène à vos fichiers.
Vous pouvez vérifier le dépôt:

./deposer-DM1

Vous pouvez redéposer plusieurs fois, chaque dépôt effaçant le précédent.

2 Faites vos propres tests

Les tests font partie entière de l'écriture d'un programme. Il faut prévoir du temps pour les tests!

2.1 Compilation

C'est le premier test.

2.2 Respect de l'interface

C'est le deuxième test. Si votre programme ne compile pas avec l'interface demandée, il ne fera surement pas ce qui est demandé.

Mise à jour nécessaire (pour 2 ou 3 élèves):

Suite à un changement malencontreux de find.mli, vous devrez changer intervalle en interval si vous avez encore une ancienne version de find.mli (récupérez la version ci-dessus).
Pour compiler en version 3.07 (maintenant installée sur les machines de l'écoles), ouvrez le module Sys avant le module Unix ou écrivez Unix.readdir au lieu readdir en raison de l'ajout d'une fonction readdir dans le module Sys.

2.3 Test de la librairie

Vous pouvez effectuer les tests sur la petite hierarchie ~remy/DM1/arch/ que vous pouvez aussi récuperer ici et décompresser avec la commande tar -z -xvf arch.tar.gz.

Voici un ensemble de tests simples que vous pourrez comparer à la sortie produite par le programme find de Unix. Il n'y a pas de raison, a priori, pour que la sortie diffère de celle de find pour les tests du groupe 1 ci-dessous. Pour les tests du groupe 2, vous pouvez éventuellement, pour certains tests, trouver moins de chemin que la commande find. Pour les tests du groupe 3, vous pouvez éventuellement reporter les erreurs différement, mais pas réussir sans repport d'erreur lorsque l'autre échoue ou inversement (sur les tests donnés) et vous devez a priori trouver au moins trouver les fichiers trouvés par la commande Unix. Pour les tests du groupe 4, vous devez repporter proprement les erreurs d'analyse de la ligne de commande et ne pas laisser une exception non rattrappée.

N'imprimez pas de commentaires ou autres informations de debugging dans stdout! N'imprimez dans stderr que les messages d'erreurs, par d'information de mise au point, pas de commentaires inutile, de façon concise, (si possible comme le fait find).

Faites des tests des fonctions de librairie d'abord (en particulier en utilisant les options Predicate, Custom et en changeant la fonction de traitement). Les test 1 à 3 ci-dessous peuvent se faire avec find.ml sans utiliser mon_find.ml en faissant simplement des appels directs à la fonction find.

La librairie find.ml doit reporter des erreurs en levant des exceptions, surtout pas appeler directement exit (sauf pour une assertion invalide, i.e. repporter un bug du programme, qui ne devrait donc jamais être levée).

Test	Command
1. Tests simples (sans -follow)
Order on single entry	`find B`
Order on multiple entries	`find B/a B/b`
Default on whole directory	`find A B`
Type regular	`find A -type f`
Maxdepth 1	`find A -maxdepth 1`
Combine options	`find A -maxdepth 2 -type f`
Regex left	`find B -regexp '@@A'`
Regex right	`find B -regexp 'B/@'`
Type regular and regexp	`find B -type f -regexp 'B/[ab]'`
2. Tests avec -follow
Follow (simple)	`find D -follow`
Follow with multiple entries	`find C D -follow`
Follow (self recursion)	`find A -follow`
Follow and links	`find A -follow -type l`
Not follow and links	`find A -type l`
3. Tests avec erreurs
Innaccessible link (ok)	`find 'E/@?'`
Innaccessible link (fail)	`find 'E/@?' -follow`
Unreadable directory (fail)	`find E/R`
Directory execution missing (fail)	`find E/X`
4. Analyse de la ligne de commande
Comparaison avec la librairie	`find A`
Inversion des entrées?	`find B/a B/b`
Appel sans arguments	`find`
Option non reconnue	`find B/a -foo`
Argument incorrect	`find B/a -type a`
Argument vide	`find B/a -maxdepth ''`
Argument vide	`find B/a -atime ''`

Les tests des groupes 1 à 3 peuvent être effectués sur find.ml en appelant directement la librairie depuis un programme OCaml. Les tests du groupe 4 testent essentiellement le programme mon_find.ml.

Nouveau dépôt

Si vous voulez un correction de votre DM1, refaites un dépôt, après avoir fait les test ci-dessus.

Ne déposer pas votre programme s'il ne passe les tests! Débugger le d'abord. Demandez de l'aide en TD.

Faites le dépôt avant: Jeudi 5 février, 18h.

3 Correction

Les corrections de vous DM1 sont adressés par email à <login>@poly.polytechnique.fr.

3.1 Informations pour lire les corrections

Champ group

Le champ group est une lettre en A et E qui résume la catégorie dans laquelle se situe votre programme en «l'état» et ne dépend que de l'ensemble des tests effectués:

`A:`	C'est très bien.
`B:`	Il y a un petit problème, sûrement facile à corriger
`C:`	Il y a, a priori, des problèmes avec le traitement des liens
`D:`	Il y a des problèmes sérieux ou sur de nombreux types de chemins
`E:`	Le programme ne compile

ATTENTION! Ce champ n'est pas une note et ne représente pas la valeur de votre travail mais l'état de votre programme. Parfois, cinq minutes peuvent suffire pour replacer un programme de la catégorie C ou D dans la catégorie A ou B, en corrigeant une erreur stupide ou le non respect de l'interface. De même, un E ne veut pas dire que le travail est nul, simplement qu'il ne compile pas, donc est inutilisable et difficilement évaluable en l'état. D'autre part, les tests ne couvrent que certains aspects du programme. En particulier, le «style» de programmation n'a pas été du tout pris en compte.

Champ mask

Le «mask» comporte deux parties séparées par une virgule. Il résume l'ensemble des test effectués de façon automatique.

La première partie est résume les tests qui portent uniquement sur le fichier find.ml en appelant directement la librairie (donc sans utiliser votre fichier mon_find.ml). En ce sens les tests effectués sont plus fins et peuvent différés des tests que vous auriez effectués avec mon_find.ml en regardant la sortie standard ou d'erreur. En particulier, les derniers tests, provoquent une exception pendant le traitement de action appliquée à un chemin filtré.

Les lettres résumant le test dans le champ «mask» représente, par importance décroissante, les erreurs suivantes (par différence avec la version attendue de la librairie).

`X:`	Appel à `exit` pendant l'exécution du test
`L:`	Boucle ou Blocage du programme
`R:`	Retour de l'appel (exception levée)
`S:`	Statut du retour (erreurs reportés ou non)
`E:`	Ensemble des erreurs reportées
`I:`	Ensemble des inodes (au bout des chemins) trouvés incorrects
`-:`	Chemin manquant
`+:`	Chemin trouvé en trop
`a:`	Aucune erreur

La deuxième partie du masque porte sur mon_find.ml, mais sans utiliser votre find.ml: vous pouvez donc passer les seconds tests même avec des erreurs dans find.ml.

Report des tests

Le reste de ce fichier contient une évaluation automatique commentée puis éventuelle de commentaires manuels (optionnels).

Pour la partie automatique, en cas d'erreurs on indique d'abord les résultats du test, puis on explique ce que le test cherche à détecter a priori et une source possible d'erreur.

L'affichage des différences se fait en les préfixant par + ou - pour signifier en trop ou en moins. Le signe $ devant un chemin signifie l'inode à ce chemin là. Notez que certaines différences sont ignorées (par exemple on pouvait ou non reporter une erreur sur un répertoire interdit en exécution et lister ou non un chemin dont la cible n'est pas lisible). D'autres erreurs sont reportées à titre indicatif, mais n'invalide pas le test.

3.2 Profil des résultats

Groupe	A	B	C	D	E	total
Nombre	9	7	10	16	2	44

3.3 Quelques erreurs fréquentes

Il y a encore trop des erreurs que vous pouviez facilement déceler (voir la section 2).
Le code de retour de la commande mon_find devait être non nul lorsqu'il y a eu des erreurs pendant le parcours.
L'option -regexp r demande de filtrer exactement le chemin: il faut donc que le filtre r puisse s'applique au tout début du chemin et se terminer à la fin.
Il ne doit pas y avoir d'appel à exit dans la librairie! ni directement, ni via un appel à handler_unix_error, y compris dans le mode Failure.
Il faut utliser Filename (et pas . et ..) directement pour être portable. Seulement 1/4 d'entre vous l'on bien fait!
Mauvais style: utilisation trop fréquentes de boucles while + références plutôt que de petites fonctions récursives. C'est plus long et cela augmente le risque d'erreurs.
Fermeture multiple des répertoires ouverts: une ressource doit être (si possible) allouée et désallouée dans le même appel récursif et surtout pas allouée en dehors et désallouée à l'interieure de la façon suivante:

let body() = let resource = alloue ... let rec treat f x = try ... treat g y ... with x -> libère resource; raise x in treat f x

3.4 Quelques erreurs ou points plus subtiles

Émission des chemins

Il était préférable «d'exécuter» les chemins au fur et à mesure en leur appliquant «l'action» plutôt que de stocker dans un premier temps tous les chemins dans une liste puis de leur appliquer l'action seulement à la fin du parcours. En plus de l'encombrement mémoire, le premier cas limite fortement l'intérêt dans le cas où la commande est «tuyautée» avec une autre.

Protection des erreurs

Par contre, dans ce cas, le rattrapage des erreurs est plus délicats: une erreur pendant l'exécution de l'action doit être considérer comme une erreur de l'utlisateur et non une erreur de parcours de la hiérarchie. En particulier, si l'utilisateur en opérant sur le chemin lève une exception Unix_error, celle-ci doit arrêter l'appel sans passer par le traitement des chemins erronés.

Une façon élégante de s'en sortir consiste à encapsuler les exceptions qui ont lieu pendant l'action, par exemple de la façon suivante:

exception Hide_exn of exn;;let hide_exn f x = try f x with exn -> Hide exn;;let reveal_exn f x = try f x with Hide exn -> raise exn;;let unprotected_find args... action = ...let find args... action = reveal_exn (unprotected_find args...) (hide_exn action)

On encapsulera de même les exceptions qui apparaissent pendant l'exécution du «handler» personnalisé défini par l'option Custom. Cela peut également être utiliser pour traiter l'option Failure. L'exception encapsulée sera vue comme une exception ordinaire, provoquant au retour des appels récursifs le code de finalisation (fermeture des répertoires ouverts) et non son traitement comme une erreur de parcours Unix_error sur le répertoire courant.

4 Annexe: ensemble des test effectués mécaniquement

Les tests principaux sont effectués sur la librairie en appelant directement la fonction find en tête du le répertoire arch. Par défaut, le mode de parcours est avec l'option Custom qui prend une fonction qui accumule les erreurs dans une liste. De façon similaire, par défaut l'action de tous les tests est une fonction qui accumule les résultats dans une liste. On donne, pour chaque teste les entreés et le cas échéant les options de filtrage.

Sur [ "C" ] avec []

Si ça ne réussit pas ici, c'est bien difficile de deviner pourquoi. C'est peut-être un nom respect tout bête de l'interface de sortie. Mais il y a de grandes chances pour que peu de tests passent.
Sur [ "D" ] avec []

Ce test est similaire au précédent, mais dans le cas d'un lien. Si cela ne réussit pas il y a un problème avec le traitement des liens. Notez bien qu'il n'y a pas l'option -follow donc on ne doit pas suivre les liens ici.
Sur [ "B" ] avec []

Teste maintenant tous les types de fichiers: liens symboliques et liens durs, mais sans descendre récursivement dans les sous-répertoires ("B" n'a pas de sous-répertoires). Si on boucle ici, peut-être suit-on les liens symboliques par erreur. S'il manque des inodes (indiqué par une ligne commençant pas - $), ce n'est vraiment pas bien. S'il manque seulemet des chemin (la commence par -, non suivi du sign $), c'est déjà moins grave. C'est encore moins grave s'il y a quelques chemins en trop. Mais dans tous les cas, il y a un problème et il faut en chercher la cause...
Sur [ "A" ] avec []

Teste la descente récursive dans les sous-répertoires.
Sur [ "B/a" "B/b" ] avec []

Teste la prise en compte de deux racines pour la recherche.
Sur [ "A" "B" ] avec []

Teste les liens croisés vers des répertoires, mais sans suivre les liens. Ne devrait donc pas poser de problèmes.
Sur [ "A" ] avec [ Type S_REG ]

Teste le filtrage des fichiers réguliers. Ne devrait pas posé de problème.
Sur [ "A" ] avec [ Type S_LNK ]

Teste le filtrage des liens symboliques. Ne devrait normalement pas poser de problème, à moins qu'il y ait déjà des erreurs ci-dessus. ou que le teste lui-même soit incorect.
Sur [ "A" ] avec [ Maxdepth 1 ]

Teste l'option -maxdepth à la profondeur 1. Peut réussir même si le test précédent de descente récursive dans les répertoires échoue.
Sur [ "A" ] avec [ Maxdepth 2 ]

Si le test précédent est correct et pas celui ci, il y a un problème avec la descente récursive dans les répertoires.
Sur [ "A" ] avec [ Maxdepth 2; Type S_REG ]

Teste la combinaison d'options, des fois qu'on ne traite que la première!
Sur [ "B" ] avec [ Regexp (Str.regexp "@@A") ]

Teste les expressions régulières. En particulier, vérifie que la motif de l'expression est reconnu au début du chemin (le filtre doit matcher exatement le chemin et non un indix du chemin).
Sur [ "B" ] avec [ Regexp (Str.regexp "B/@") ]

Similaire au test précédent, on vérifie ici que le motif reconnaît le chemin tout entier.
Sur [ "B" ] avec [ Type S_REG; Regexp (Str.regexp "B/[ab]") ]

Test récapitulatif. Si tous les tests précédent passent et pas celui-ci, difficile de deviner pourquoi a priori.
Sur [ "D" ] avec [ Follow ]

C'est le premier test qui suit les liens. Ici, on ne risque pas de boucler, car il n'y a pas de liens récursifs. Si ça ne marche pas, il y a vraiment un problème de base avec le traitement des liens, indépendant de l'existence de liens récursifs.
Sur [ "C" "D" ] avec [ Follow ]

Comme le test précéde on teste les liens symboliques en les suivant. On ne risque toujours pas de boucler, mais on visite C deux fois: une fois directement puis une fois à partir d'un lien dans D. On déroule la visite une deuxième fois, car on est sur un chemin différent mais on pourrait ne pas le faire (ce n'est pas bien grave).
Sur [ "A" ] avec [ Follow ]

C'est le premier test sur les liens symbolique qui risque de boucler. Ici, il y a une récursion directe le long de la hiérachie. Si les tests précédents passent et celui-ci ne passe pas il y a un problème dans ce traitement. Si on boucle (L) c'est très mauvais...
Sur [ "A" ] avec [ Follow; Type S_LNK ]

On teste à nouveau l'option -type l, mais en présence de -follow: dans ce cas, on ne doit rien trouver puisqu'on suit systématiquement les liens, donc ce qui est au bout du chemin n'est pas un lien.
Sur [ "E/@?" ] avec []

Si les tests du groupe précédent sont corrects, ce test devrait réussir même si le lien est inaccessible, car on ne doit pas suivre pas les liens ici.
Sur [ "E/@?" ] avec [ Follow ]

Contrairement au test précédent, ici on doit suivre le lien qui est inaccessible. On doit donc échouer (typiquement en faisant 'stat') sur le lien. On ne devrait pas imprimer le lien (mais ce n'est pas grave de le faire).
Sur [ "E/R" ] avec []

Ce test doit échouer en essayant de lire E/R, typiquement (mais pas forcément) en faisant [l]stat sur E/R,
Sur [ "E/X" ] avec []

Ici, on peut lire E/X, donc trouver E/X/A et E/X/a, mais on va échouer sur ces deux entrées typiquement en faisant 'lstat' sur celles-ci. En fait on sait pas avance qu'on va échoué sur tous les chemins de E/X. Donc on pourrait aussi bien échouer sur E/X.

En résumé:
- E/X doit être afficher.
- E/X/A et E/X/a peuvent ou non être affiché.
Et on reporte au moins une erreur d'accès:
- soit sur E/X et on ne fait pas la descente récursive.
- soit sur E/X/A et E/X/a
Sur [ "E" ] avec []

Ce test résume l'ensemble des tests d'erreur. Malgré les erreurs, on doit au moins trouver les chemins: E, E/R, E/@?, E/X. Si ce n'est pas le cas, vous avez peut-être tout arrêté à la première erreur au lieu de continuer.
Sur [ "A" ] avec []

On test le rattrapage des exceptions lancées pendant l'action appliquée au traitement d'un chemin (on a donc changé l'action par défaut pour lever une exception après le second chemin) - Si cela échoue avec R, les exceptions sont mals protégées. - Si cela échoue avec L, il y a de grandes chances qu'un même répertoire soit refermé plusieurs fois.
Sur [ "A" ] avec []

Comme précédemmment, on test le rattrapage des exceptions lancées pendant le traitement d'un chemin, mais avec l'exception Unix_error. Celle-ci ne doit pas être prise pour une erreur de parcours, donc elle ne doit pas être traitée mais doit remonter immédiatement à l'utilisateur comme dans le cas précédent.
Sur [ "C E" ] avec []

Ici, on utilise le mode Ignore. On devrait toujours retourner normalement et retourner tous les chemins corrects
Sur [ "C E" ] avec []

Ici, on utilise le mode Failure. On devrait traiter les chemins de C corrects, puis lever l'exception Unix_error à la première erreur rencontrée. (Les actions précédents l'erreur devraient être visibles).

Ce document a été traduit de L^AT_EX par H^EV^EA