% FILE. . . . . /users/formel2/dicosmo/ACADEMIC/CORSI-DIDATTICA/Algo199899/TP98_6.tex
% EDIT BY . . . Roberto Di Cosmo
% ON MACHINE. . Menthe.Ens.Fr
% STARTED ON. . Thu Nov 26 10:02:25 1998

\documentclass{article}
\usepackage{a4}
\usepackage{graphicx}
% *****FULLNAME: /users/formel/dicosmo/Paperi/Miei/Definitions/tdenv.tex
% *****EXPORTBEGS: \input{tdenv}
%
% General \ignore{ . . . } macro.
%
\long\def\ignore#1{\relax}
%
% definition rules environment
%
\newenvironment{rules}{\begin{list}{}{\itemindent.3in\labelwidth0in\labelsep10pt\parskip0pt\partopsep0pt\itemsep0pt\topsep0pt\leftmargin0pt}}{\end{list}}
%
% definition of standard Article environment
%
\def\piripi{\par} % cambiare con \endgraf
\newenvironment{bodydouble}[1]{\endgraf\noindent {\bf #1}\em}{\endgraf}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{rem}[theorem]{}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{exercise}{Exercice}[section]
\newtheorem{remark}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exmpl}[theorem]{Example}
\newenvironment{example}{\begin{exmpl}\em}{$\qed$\end{exmpl}}
\newenvironment{tinyexample}{\begin{exmpl}\em\twocolscond{\footnotesize\endgraf\smallskip}{\endgraf}}{$\qed$\end{exmpl}}
\newtheorem{defn}[theorem]{Definition}
\newenvironment{definition}{\begin{dfntn}\em}{$\qed$\end{dfntn}}
\newtheorem{lgrthm}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{lgrthm}\em}{\end{lgrthm}}
\newtheorem{xms}[theorem]{Axioms}
\newenvironment{abstract2}[1]{\small\centerline{#1}\begin{list}{}{\rightmargin=\leftmargin} \item}{ \end{list} \normalsize }
\newenvironment{axioms}{\begin{xms}\em}{\end{xms}}
\newenvironment{proof}{\begin{trivlist}\item[]\hspace{\parindent}{\em Proof.}}{$\qed$\end{trivlist}}
%
%\newenvironment{remark}{\begin{trivlist}\item[]{\bf Remark\ \ }}{\end{trivlist}}
%
\def\qed{\proofbox}
\def\proofbox{\begin{picture}(7,7)%
  \put(0,0){\framebox(7,7){}}\end{picture}}
\def\iff{\mbox{$\leftrightarrow$}}
\def\Iff{\mbox{$\Longleftrightarrow$}}
\def\imp{\mbox{$\rightarrow$}}
\def\revimp{\mbox{$\leftarrow$}}
\def\Imp{\mbox{$\Rightarrow$}}
\def\RevImp{\mbox{$\Leftarrow$}}

\begin{document}
% tp1-enonce.tex
\parindent=0pt
MMFAI\par
Cours de programmation
\bigskip

\centerline {TP num\'ero 5}
\centerline {semaine du 30 novembre 1998}
\bigskip
\centerline{\bf Manipulation de Graphes: le programme {\tt make}}

\subsection*{Gestion de gros projets}

Si vous avez \`a  g\'erer un  projet  assez important, c'est n\'ecessaire  de disposer
d'outils  ad\'equats. Par exemple, il serait   bien de disposer  de la compilation
s\'epar\'ee des modules qui composent votre projet. On a d\'ej\`a vu, dans le corrig\'e du
TP2 que si vous avez un fichier \verb|essai.c| qui utilise les fonctions d\'efinies
dans le fichier \verb|matrops.c|, plut\^ot que de le compiler avec la commande
\begin{verbatim}
gcc -o essai matrops.c essai.c
\end{verbatim}
qui compile les deux fichiers ensemble, on peut proc\'eder en deux phases: d'abord
\begin{verbatim}
gcc -c matrops.c
\end{verbatim}
qui compile \verb|matrops.c| et produit le fichier ``objet'' \verb|matrops.o| mais
pas d'executable, ensuite la commande
\begin{verbatim}
gcc -o  essai matrops.o essai.c \end{verbatim}\  qui compile  \verb|essai.c|, et
ensuite  le compose    avec    \verb|matrops.o| pour  produire      l'executable
\verb|essai|.  On gagne du temps si \verb|matrops.c|  est un programme stable et
\verb|essai.c| est  en d\'eveloppement, parce que  la compilation  prends beaucoup
plus de    temps que la  ``composition''  (techniquement   appel\'ee ``\'edition  de
liens'').

Et on  peut  gagner beaucoup  de temps,  dans le cas   de projets  complexes qui
comportent plusieurs dizaines de modules s\'epar\'es, si  on arrive a ne recompiler,
apr\`es une modification de quelques fichiers sources, que ces  modules qui en ont
besoin.

Pour faire \c{c}a, on dispose (sous Unix, mais aussi dans le monde Windows et MacOS)
d'un outil  essentiel    nomm\'e \verb|make|   qui  prend  en   entr\'ee un  fichier
(normalement nomm\'e \verb|makefile|) qui d\'ecrit les d\'ependances entre les modules
de votre  projet, et les actions  \`a effectuer pour mettre  \`a jour ces modules en
cas de  modifications.  Par exemple, pour notre  vieux  projet du  TP2, on  peut
\'ecrire le \verb|makefile| suivant:

\begin{verbatim}
essai:	essai.c matrops.o
        gcc -o essai matrops.o essai.c

matrops.o:	matrops.c matrops.h
        gcc -c matrops.c
\end{verbatim}

Ici les d\'ependances sont not\'es {\it modulequidepende}: {\it moduledontondepend1}
\ldots{} {\it moduledontondependn}, et  les actions \`a  faire sont des lignes qui
commencent par une tabulation  apr\`es la ligne qui  d\'ecrit la d\'ependance.  Ici on
dit par  exemple  que pour  obtenir  l'executable   \verb|essai|  il faut  avoir
\verb|essai.c| et \verb|matrops.o| et  ex\'ecuter  la commande 
\verb|gcc -o  essai matrops.o essai.c|.  Ces d\'ependances,  qui  ne   doivent pas \^etre   circulaires,
d\'ecrivent en effet un graphe acyclique dirig\'e.

Si on tape \verb|make -f makefile essai|, le programme \verb|make| va essayer de
``construire'' essai. Pour cela, il doit explorer le graphe des d\'ependances pour
identifier  tous  les modules  dont  \verb|essai|  d\'epend, ensuite ex\'ecuter  les
actions n\'ecessaires a les construire \emph{dans le bon  ordre}, (par exemple, on
ne peut  pas ex\'ecuter    \verb|gcc -o  essai matrops.o  essai.c|   avant d'avoir
construit \verb|matrops.o|!), et sans  rep\'etitions (si $a$ d\'epend  de $b$ et $c$
qui tous les deux d\'ependent de $d$, on veut quand m\^eme  construire $d$ une seule
fois). De plus, \verb|make| v\'erifie, avant de construire un module, si ``\c{c}a vaut
la peine'' de  le reconstruire:   pour cela, il   utilise la  date de   derni\`ere
modification du module, et si ell'est plus r\'ecente que celle des modules dont il
d\'epend, il ne fait  rien (parce-que on assume  que l'op\'eration de construction a
d\'ej\`a    \'et\'e faite,    par     exemple  par    une  ex\'ecution   ant\'erieure     de
\verb|make|)\footnote{Attention:  il faut  utiliser  cette  information  sur les
dates dans le bon ordre aussi!}.

\subsection*{Un petit {\tt make} maison}
Aujourd'hui,  nous   allons  nous  int\'eresser   \`a \'ecrire  notre   propre version
exp\'erimentale de  \verb|make|,  dans  laquelle nous  nous   int\'eressons dans  un
premier temps seulement \`a   l'analyse des d\'ependences,   et non pas \`a   comment
utiliser les dates pour ne pas  recompiler ce qui  aurait d\'ej\`a \'et\'e compil\'e. Nous
allons aussi ignorer pour l'instant les ``actions''. Donc, nous travaillerons
sur des fichiers \verb|makefile| sans actions, comme par exemple

\begin{verbatim}
a: b c d
b:
c: d e
d: e
e:
\end{verbatim}

qui d\'ecrive le GAD suivant
%
\begin{center}
\includegraphics[height=70pt]{deps.eps}
\end{center}
%
\begin{exercise}
Choisissez   une repr\'esentation   de  graphes  qui   vous  semble  ad\'equate pour
\verb|make|, et  d\'efinissez  le correspondant  type C,  de  nom \verb|GAD| (pour
Graphe Acyclique Dirig\'e).  Reflechissez  bien aux  informations que  vous  allez
garder pour chaque noeud (il  y aura s\^urement  une cha\^{\i}ne de caract\`eres pour le
nom du noeud, mais quoi d'autre?).
\end{exercise}

\begin{exercise}
En utilisant la fonction \verb|int readline(FILE *fp, char **res)| du TP4,
\'ecrivez une fonction \verb|int readmakefile(char *nomdufichier, GAD **graphe)| qui lit
un fichier de d\'ependances et produit le GAD associ\'e, en retournant un code
d'erreur s'il y a des probl\`emes pour lire le fichier.

Tout \c{c}a est fait de fa\c{c}on \`a pouvoir appeler la fonction comme suit
\begin{verbatim}
GAD *mongraphe;

if (readmakefile("makefile",&mongraphe)!=0) 
   {printf("Erreur en lisant makefile. J'abandonne.\n"; exit(1);};
\end{verbatim}
\end{exercise}

\begin{exercise}[exploration]
\'Ecrivez maintenant une fonction qui prends un GAD et le nom d'un noeud $n$ dans ce GAD
et retourne la liste des noeuds dont $n$ d\'epend, dans le bon ordre pour pouvoir l'utiliser
pour construire $n$. Par exemple, pour le fichier d'en haut on pourrait rendre 
$e , b , d , c , a$. Si vous n'avez pas garde le code pour les listes que l'on a vu en TP3,
il suffira d'imprimer les noms des noeuds dans le bon ordre, plut\^ot que retourner la liste.
\end{exercise}

\begin{exercise}[optionnel]  Modifiez votre code  pour  prendre en  compte aussi
l'information sur la date: maintenant, les noms  dans \verb|makefile| seront des
vrais noms de fichier, et on vous demande de retourner la liste des seuls noeuds
qu'il vaut  la   peine de reconstruire.   Pour cela  vous pourriez   avoir envie
d'utiliser la fonction de librairie \verb|stat| (faire \verb|man stat|).
\end{exercise}

{\bf N'oubliez pas de vous d\'econnecter avant d'abandonner le clavier (voir notes du stage Unix).}
%\clearpage
%\mbox{}
\end{document}
