Ce texte fait partie d’une petite collection de notes mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 2.0 France.20 novembre 2022
Ce texte fait partie d’une petite collection de notes mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 2.0 France.
Première version 20 novembre 2022. Corrections typos 22 nov.
Le langage C n’est pas jeune, a plein de défauts, et est souvent très mal enseigné, surtout au regard des enjeux actuels : produire du code qui n’a pas trop d’erreurs.
Pour cela, il convient de sensibiliser les débutants1 qui découvrent la programmation en C2 (les malheureux). Un point qui est très souvent négligé, c’est l’idée de tester systématiquement le code que l’on écrit.
Mieux :
Pour enseigner ça, il n’est pas utile de montrer un “framework de test” à des débutants. Les bibliothèques industrielles c’est très utile pour les professionnels, mais là on s’adresse à des débutants qui sont déjà largement perdus dans les bases de C. Consacrer du temps à appréhender l’utilisation d’un framework (une mystérieuse usine à gaz qui offre plein de possibilités), c’est autant d’heures en moins consacrées aux bases de la programmation et de l’algorithmique.
En pratique, ils pourront à utiliser un framework le moment venu si jamais ils en ont besoin. Ce qu’ils feront d’autant plus vite qu’ils auront maîtrisé les bases de la programmation, sans être ralentis par l’apprentissage d’une usine à gaz.
Bref, ce document montre
assert ;sur un exemple classique : quelques exercices sur les listes chaînées.
assert()Examinez le code suivant :
// demo-assert.c
#include <stdio.h>
#include <assert.h>
int main()
{
printf("Début\n");
assert(2+2 == 4);
assert(2+3 == 6);
assert(3+3 == 6);
printf("Fin\n");
}Il contient
assert(), avec comme paramètre une condition ;assert.h, où assert() est déclarée.Compilez et exécutez, il se produit
$ gcc demo-assert.c -o demo-assert
./demo-assert
Début
demo-assert: demo-assert.c:8: main: Assertion `2+3 == 6' failed.
AbandonVous remarquez que
2+2 == 4) a réussi, silencieusement ;En résumé : à l’exécution, l’appel assert(condition)
La macro prédéfinie assert fait partie du standard C. Les curieux trouveront dans l’annexe une implémentation simple.
assert(message && condition)Une astuce traditionnelle est d’ajouter une chaîne de caractères qui sert de commentaire dans l’assertion. Exemple
assert("cas de base" && fib(1) == 1);Du point de vue du langage C
&&, ce pointeur non nul correspond à true,fib(1) == 1.La présence de la chaîne ne change donc rien au test qui est effectué. Par contre, pour le programmeur qui teste, la chaîne s’affiche
fib: fib.c:13: tests_fib: Assertion `"cas de base" && fib(1) == 1' failed.
-------------et fournit immédiatement une indication supplémentaire, plutôt que d’avoir à aller consulter le fichier source à la recherche d’un commentaire expliquant la raison du test.
En pratique, la compréhension des erreurs est une activité intellectuelle intense, dans laquelle une petite tâche annexe comme “ouvrir un autre fichier pour aller voir les commentaires” est une distraction qui fait perdre de la concentration. Et ce n’est vraiment pas le moment.
Donc, on recommande de mettre un message dans les assertions.
Ici on se place dans le cadre d’un projet traditionnel, écrire - à titre d’exercices - un certain nombre de fonctions qui agissent sur une liste chaînée de nombres.
Nous allons le faire, en suivant une méthodologie de tests systématiques.
Une liste est une suite de noeuds chaînés entre eux. Nous définissions deux types de données3 :
typedef struct Node {
int value;
struct Node *next;
} Node;
typedef struct List {
struct Node *first;
} List;Il faudra écrire des fonctions pour ajouter, enlever, etc. dans des listes.
Pour homogénéiser les fonctions, on va leur donner des noms
sl (pour simple list),ListCommençons par le début : une fonction sl_init qui initialise une liste. Pour vérifier qu’elle fonctionne, on écrit aussi une fonction sl_is_empty qui regarde si la liste est vide.
Si vous ne voyez pas comment faire, regardez la section “Indications” à la fin du document.
void test_init()
{
List l;
sl_init(&l);
assert("liste vide après initialisation" && sl_is_empty(&l));
}Exercice : écrire la fonction
void sl_init(List * list)
{
...
}Attention : on se permet de nommer le paramètre list alors qu’il ne contient pas une structure List, mais l’adresse d’une telle structure.4
Exercice : en ayant inclus stdbool.h, écrire :
bool sl_is_empty(const List * list)
{
...
}On spécifie const parce que tester si une liste est vide ne doit pas modifier la liste.
Si vous n’y arrivez pas, voir dans l’annexe “Solutions”.
Pour cette fonction, on peut imaginer le test suivant
Le test pourrait s’écrire
void test_add_first()
{
List list;
sl_init(&list);
sl_add_first(&list, 10);
sl_add_first(&list, 30);
sl_add_first(&list, 20);
assert("après 3 ajouts" && sl_size(&list) == 3);
assert("premier de la liste" && sl_value_at(&list, 0) == 20);
assert("second de la liste" && sl_value_at(&list, 1) == 30);
assert("troisième de la liste" && sl_value_at(&list, 2) == 10);
}en suivant la convention - raisonnable en C - d’indicer les éléments de la liste à partir de 0.
Exercice : partir du code suivant
void sl_add_first(List *list, int value)
{
assert("A faire" && false);
}
int sl_size(const List *list)
{
assert("A faire" && false);
}
int sl_value_at(const List *list, int index)
{
assert("A faire" && false);
}Ici assert est utilisée pour faire des “stubs” (bouchons), c’est-à-dire écrire des fonctions syntaxiquement correctes (donc compilables), mais qui font juste acte de présence, sans faire le boulot.
Le travail devient un cycle : compiler le source (qui est correct), exécuter, s’occuper de la première erreur qui apparaît, recommencer.
On peut aussi utiliser une macro TODO (à faire) pour faciliter l’écriture des stubs :
int sl_size(const List *list)
{
TODO("calcul de la taille d'une liste");
}TODO n’est malheureusement pas une macro standard, mais il est facile de définir soi-même en s’inspirant du code d’assert. Voir code en annexe.
On donne inévitablement comme exercice l’ajout d’un élément en fin d’une liste chaînée simple. L’objectif est de faire manipuler les chaînages5.
Voici le test
void test_add_last()
{
List list;
sl_init(& list);
sl_add_last(&list, 11);
assert("après 1 ajout" && sl_size(&list) == 1);
assert("après 1 ajout" &&sl_value_at(&list, 0) == 11);
sl_add_last(&list, 333);
assert("après 2 ajouts" && sl_size(&list) == 2);
assert("après 2 ajouts" &&sl_value_at(&list, 1) == 333);
sl_add_last(&list, 2);
assert("après 3 ajouts" && sl_size(&list) == 3);
assert("après 3 ajouts" && sl_value_at(&list, 2) == 2);
}Exercice : écrire la fonction sl_add_last
void sl_add_last(List *list, int value) {
// A Faire
}Vérifier qu’une liste contient bien les valeurs attendues serait bien plus simple ainsi :
void test_add_last()
{
List list;
sl_init(& list);
sl_add_last(&list, 11);
sl_add_last(&list, 333);
sl_add_last(&list, 2);
int expected[] = { 11, 333, 2}; // ici
assert("après 3 ajouts à la fin"
&& sl_list_contains(&list, expected, 3));
}Exercice : écrire la fonction
bool sl_list_contains(const List *list, int values[], int nb_values)
{
}L’écriture des tests fait souvent apparaître des besoins, au niveau des fonctions sur le type de données.
C’était le cas ci-dessus pour sl_list_contains, qui nous permet de tester facilement qu’une liste contient les valeurs attendues.
Dans les tests, nous avions besoin d’ajouter des éléments, ce qui nous faisions laborieusement à la petite cuiller, un par un.
Pour simplifier, on peut imaginer une fonction qui ajoute un tableau de valeurs à la fin d’une liste.
Exemple de test :
void test_add_values() {
List list;
sl_init(& list);
int v1[] = {11, 22, 33};
sl_add_values(&list, v1, 3);
assert("construction liste" && sl_list_contains(&list, v1, 3));
int v2[] = {44, 55};
sl_add_values(&list, v2, 2);
int expected[] = { 11, 22, 33, 44, 55};
assert("ajout tableau" && sl_list_contains(&list, expected, 5));
}Exercice : écrire la fonction
void sl_add_values(List *list, int values[], int nb_values)
{
// A faire
}Pour l’initialisation, il suffit d’affecter le membre first de la structure dont l’adresse est reçue en paramètre.
list->first = .... ;Tester si la liste est vide se ramène à tester si first contient NULL.
Pour trouver le dernier maillon, vous pouvez faire une boucle avec une variable n
n dans une variable last.Ainsi, à la sortie de la boucle, on a dans last l’adresse du dernier maillon.
À voir : initialisation de last ?
Vous pouvez faire une boucle pour parcourir le tableau case par case.
Dans cette boucle, vous ferez aussi progresser un pointeur le long de la liste, et vous comparerez le contenu d’une case, et d’un élement de la liste.
Attention :
NULL dans la boucle, la liste est trop courte.NULL après la boucle, la liste est trop longue.La solution de facilité consiste à faire une boucle sur le tableau, et appeler sl_add_last pour chaque élément.
Ça ferait l’affaire pour une fonction qu’on n’appellerait que pour des tests. Vous pouvez commencer par faire comme ça.
Mais il y a un problème : pour le premier élément, sl_add_last n’exécute pas sa boucle. Pour le second, elle fait 1 tour. Pour le troisième, deux tours. Etc.
Si on fait le total, pour ajouter 100 éléments, ça fera 0+1+2+….+99 = 4950 tours. Avec de grosses listes, Le temps nécessaire grandit comme le carré de la taille de la liste. Pour de grosses listes, c’est trop.
Pour faire ça bien, dans sl_add_values, il faut se rappeler du dernier élément ajouté.
#include <stdbool.h>
#include <assert.h>
// ... mettre les déclarations ici
void sl_init(List *list)
{
list->first = NULL;
}
bool sl_is_empty(const List *list)
{
return list->first == NULL;
}
void test_init()
{
List l;
sl_init(&l);
assert("liste vide après initialisation" && sl_is_empty(&l));
}
int main()
{
printf("# Tests\n");
test_init();
printf("# OK\n");
}void sl_add_first(List *list, int value)
{
Node *n = malloc(sizeof(Node));
// A traiter : cas où l'allocation échoue
n->value = value;
n->next = list->first;
list->first = n;
}
int sl_size(const List *list)
{
int size = 0;
for (Node *n = list->first; n != NULL; n = n->next) {
size += 1;
}
return size;
}
int sl_value_at(const List *list, int index)
{
Node *n = list->first;
for (int i = 0; i < index; i++) {
n = n->next;
}
return n->value;
}void sl_add_last(List *list, int value)
{
// recherche du dernier maillon
Node *last = NULL;
for (Node *n = list->first; n != NULL; n = n->next) {
last = n;
}
// allocation nouveau maillon
Node *new_node = malloc(sizeof(Node));
new_node->value = value;
new_node->next = NULL;
// accrochage
if (last == NULL) {
// au début (la liste était vide)
list->first = new_node;
} else {
// après le dernier
last->next = new_node;
}
}bool sl_list_contains(const List *list, int values[], int nb_values)
{
Node *node = list->first;
for (int i = 0; i < nb_values; i++) {
if (node == NULL) {
return false;
}
if (node->value != values[i]) {
return false;
}
node = node -> next;
}
return node == NULL;
}Pour ajouter plusieurs éléments à la fin, on commence par localiser le dernier maillon. Les éléments du tableau s’accrocheront
next de ce maillon si il existe ;first de la liste si la liste était vide.Comme ces deux champs sont de même type, on peut uniformiser en notant l’adresse de ce champ.
void sl_add_values(List *list, int values[], int nb_values)
{
// recherche de l'adresse du pointeur auquel on accrochera le
// premier élément supplémentaire
Node **addr_ptr = & list->first;
for (Node *n = list->first; n != NULL; n = n->next) {
addr_ptr = &(n->next);
}
// ajout des éléments du tableau
for (int i = 0; i < nb_values; i++) {
Node *new_node = malloc(sizeof(Node));
new_node->value = values[i];
new_node->next = NULL;
// chainage du maillon
*addr_ptr = new_node;
// c'est à lui qu'on accrochera les suivants
addr_ptr = & new_node->next;
}
}assertVoici une version d’assert
// my-assert.c
#include <stdio.h>
#include <stdlib.h>
#define my_assert(condition) { \
if(!(condition)) { \
fprintf(stderr, "Dans %s ligne %d (fonction %s) l'assertion '%s' est fausse.\n",\
__FILE__, __LINE__, __func__, #condition); \
exit(1); \
}\
}
int main()
{
printf("Début\n");
my_assert(2+2 == 4);
my_assert(2+3 == 6);
my_assert(3+3 == 6);
printf("Fin\n");
}qui produit presque la même chose que le programme du début.
$ gcc my-assert.c -o my-assert
./my-assert
Début
Dans my-assert.c ligne 18 (fonction main) l'assertion '2+3 == 6' est fausse.
Abandon.Explications
my_assert ne peut pas être une fonction. C’est une macro pour afficher le code source de la condition, le nom du fichier et le numéro de ligne où elle est appelée, etc.__FILE__, __LINE__ et __func__ sont des macros standards du langage C.TODOLes mêmes mécanismes peuvent servir à réaliser une macro TODO qui accélère l’écriture des stubs.
Exemple :
// my-todo.c
#include <stdio.h>
#include <stdlib.h>
#define TODO(message) { \
fprintf(stderr, "Dans %s ligne %d (fonction %s) "\
"code manquant : %s.\n", \
__FILE__, __LINE__, __func__, #message ); \
exit(1); \
}
// exemple d'utilisation
int fib(int n)
{
if (n <=1) {
return n;
} else {
TODO("valeurs > à 2");
}
}
int main()
{
printf("fib(0) = %d\n", fib(0));
printf("fib(1) = %d\n", fib(1));
printf("fib(2) = %d\n", fib(2));
}Exécution
./my-todo
fib(0) = 0
fib(1) = 1
Dans my-todo.c ligne 19 (fonction fib) code manquant : "valeurs > à 2".Pour leurs enseignants c’est souvent trop tard.↩︎
L’idée de commencer à apprendre la programmation par un langage aussi rustique que bourré de défauts est clairement une abomination dans la deuxième décennie du troisième millénaire.↩︎
On utilise ici typedef pour simplifier l’écriture des déclarations de structures.↩︎
C’est un abus de langage courant, mais un abus quand même.↩︎
En pratique, si on a besoin souvent d’ajouter des valeurs à la fin d’une liste, c’est qu’une liste chaînée simple n’est pas la structure de données qui convient. Envisagez par exemple une liste avec un pointeur qui donne un accès direct au dernier élément (et peut-être une liste à double chaînage si on a besoin de retirer le dernier).↩︎