NOTES.org

* Notes en vrac

============================ Competences ======================

1- Trouver le/les bug
    1.1- Comprendre la specification du programme
        1.1.1- Formuler des hypotheses et des contrats sur des bouts de programme et des variables
        1.1.2- Identifier les hypotheses qui ont le plus de chances de causer un bug
    1.2- Savoir verifier une hypothese
        1.2.1- Trouver un input qui pourrait faire planter l'hypothese
        1.2.2- Identifier des variables et des endroits du programme ou il est interessant de tracer.
        1.2.3- Ne pas ajouter de nouveaux bugs pendant le tracing (avec des effets de bord)

2- Correction d'un bug
    2.1- Ne pas ajouter de nouveaux bugs pendant la correction

3- Outils de tracing
    3.0- Lire le code et le simuler dans la tete
    3.1- Print
    3.2- Valgrind
    3.3- GDB

===============================================================

les debuggers plus experimentes font plus de backward reasoning que les novices (de voir la sortie et d'essayer
de deduire ce qui a pu causer ca) plutot que du forward reasoning (on fait du tracing et on espere trouver une erreur)

On peut demander pour chaque exercice, combien de temps l'etudiant pense qu'il va mettre pour resoudre le bug.
On peut aussi demander tout ce qui peut planter dans le programme.

Utilisation de rr dans un module special (Florent a surement raison en fait)

Est ce qu'on a des niveaux sans debugger par ce que ya bcp d'autres methodes de tracing (dans la tete, papier, print) ?

Plusieurs bugs par niveau ?

On peut demander a l'etudiant de nommer les variables et fonctions qu'on va utiliser
pour qu'il s'approprie le code, on donne une description en texte et/ou en pseudocode et on demande un nom

dans la literature de debug, on demande d'abord aux etudiants d'implementer leur propre truc avant de le debugger.
Est ce qu'on ne donne que la spec ou des fonctions de validation ?

* Idees de niveaux / gameplay

Jeu plus à la baba is you que du zelda pur
-> moins de baston et plus de réflexion

Des clés à trouver pour ouvrir des portes.
De la lave, etc.

** Evolution gameplay
1 -> petit a petit on fait un snake (carte 2D, deplacement, generer pommes, attraper des pommes, score, agrandissement, condition de defaite) ya deja plusieurs choses a faire
2 -> on enleve l'agrandissement du serpent et la condition de defaite et on garde juste le deplacement et attraper des choses, on ajoute une collision avec des murs
2' -> etape intermediaire ou on sort juste a pied d'un labyrinthe et IA pour sortir ? Ici on peut mettre les inventaires avec des cles de couleurs pour ouvrir des portes
3 -> mtn on est plutot en sokoban, il faut mettre des caisses sur des emplacements finaux (algorithme pour pousser les caisses, condition de victoire, compteur de tour).
4 -> projet "final" faire une IA qui joue au sokoban ?

* Idées de niveaux / bugs

On demande a des etudiants d'implementer des specs et on regarde les bugs qu'ils font pour les mettre dans agdbentures ?

** niveaux avec "beaucoup" de modifications (mais pas forcement dur)
calcul de denivele ou on ne fait que une somme alors que parfois il faut soustraire (ajout complet du if)

** bugs arithmetique
- mauvais calcul de score quand on mange un truc dans snake

** bugs tableaux
- implementation du passage d'un bord a l'autre (tore), avec le bug le deplacement sort juste de la map
- meme chose mais avec des bornes par ce que cette fois il y a des murs et on peut en faire un parametre d'initialisation de la map dans les niveaux futurs.

** bugs tableaux de taille dynamique
- les elements ne sont pas copies lors de la reallocation

** bugs de listes chainees

- inventaire sous forme LC
  => quand ajout 1er element, on perd le reste

- boucle infinie sur une recherche


** bug random
- module random perso, qui renvoie toujours la meme suite de nombres
  - pb avec seed
  - seed pas utilisée



** bugs memoire

- malloc sur sizeof(*structure) au lieu de sizeof(structure)
  => espace trop petit
  -> intro valgrind ?

- passage par copie sans pointeur et on perd le resultat

- segfaults
  pointeurs déclarés mais non alloués

** algorithmes (derniers niveaux)
- tri de pilier de differentes tailles pour faire un escalier, plusieurs off-by-one dans les tris
- plus court chemin sans tests de cycle.
- backtracking dans un labyrinthe sans le backtrack (cest ptet un peu chaud ?)


** Liste de bugs de réunion du vendredi 25 mars matin

Catégories
- structures
- language
- off by one
- ordre instructions
- boucle infinie
- scope
- memoire
- récursion



*** language C

- if (x=0) au lieu ==
- boucles infinies
  - i-- et i<0 unsigned -> signed
  - i+=2 et test !=  -> test <=
  - stack overflow (recursion)

*** mémoire
- oubli initialisation mémoire à 0
- double free
- free puis utilisation
- malloc(*mastruct) au lieu de mastruct
- malloc sans vérif != null
- fuite (malloc inutiles avant cel = S.tete)


- aliasing
  - 2 listes pointent sur 1 en fait
  - matrice -> toutes les lignes sont une seul en fait

- variables locales modifiées
  - pas d'insertion après appel (LC)
  - cellule locale insérée (sans malloc)

*** tableaux
- off by one
- dépassement -1

- écrasement mémoire : variable d'à côté


*** strings
- oubli du '\0'
- mauvais arguments strcp, strcat etc.
- strcat à répétition (Cpx)


*** passage arguments
- copie ou réf ?


*** invariants / conditions
- utilisation ptr en sortie de boucle != NULL
- manque une étape
- switch avec oubli de break
- dichotomie sans décroissance

*** ordre opérations
- pb d'ordre dans un swap de vars
- pb d'ordre dans insertion cellule (LC)


*** data structure
- mauvaise structure utilisée (ensemble vs sequence)
- #define pourri
- enum

*** algos arbres
- pb modif arbre (notifier le parent)
- pb suppression locale

*** aléatoire
- savoir controler l'aléatoire pour débugger => rendre déterministe


*** lecture de message
- message de warning du compilo non lu
- "recommandation" suivie sans se poser de question (ajout de * ou & par ex.)



=============== DEROULEMENT ==================

Partie 0.5 => Exos sans bugs, il faut formuler des invariants
Il faut trouver des inputs chiants qui peuvent faire planter le programme (cest tres proche du testing)
A partir de maintenant pour chaque exo avant de commencer on demande une liste d'hypotheses a verifier (ce qui peut avoir mal tourne)

==============================

Partie 1 => Tracing only, single step ou full run (pas besoin de controle, juste regarder l'etat du programme)

differentes categories melangees "Off by one" au sens large:
- vrai off by one (indice de boucle, de tableau), erreur de calcul en general
- il faut mettre une ligne dans/dehors une boucle/condition
- il faut ajouter enlever une ligne dans une sequence d'instruction
- bug lie au langage (ici C) :
  * passage par copie/reference
  * bug memoire (voir section bug memoire)
  * juste segfault (on fait run a la segfault et on regarde, la il faut gdb)

/!\ On ne fait pas de reecriture complete de bout de code

bug direct au debut
puis on ajoute l'usage de structures de donnees mais sans bug dedans, juste usage
direct ou indirect ensuite

programmes court, maxi 50-60 lignes y compris definitions de structure

structures possibles :
Liste chainees
Tableaux dynamiques


bug direct cest que la cause est directement ce qu'on print/trace
bug indirect, il faut comprendre comment une valeur est construite et le bug est dans la construction (resultat d'algorithme.
mauvais usage d'une structure)
bug de structure, un invariant de structure est casse ou il y a un bug de langage.

classification partie 1
                         | off by one/arithmetic | control flow | add/remove instruction | language bug
direct                   |                       |              |                        |
direct + struct sans bug |                       |              |                        |
indirect                 |                       |              |                        |

                                              ****************

3eme dimension => Programe long au runtime (et eventuellement en code) qui fait office de transition

- Transition single step mieux que full run par ce que bug observable des le debut et les structures de donnees sont encore petites et lisibles
Exactement comme Partie 1 mais les programmes sont plus longs (au moins en runtime pas forcement en taille de code, mais ca peut)
Contrainte qui reste "le bug doit etre observable tot dans l'execution".



=========================

Partie 2 => Tracing et single step intractable on doit ajouter breakpoint, watchpoint

Dans cette partie les programmes sont plus longs potentiellement avec des fichiers d'input ou des problemes complexes (en terme de calcul pas en terme de difficulte).

On garde la meme classification que partie 1 avec direct/indirect etc mais cette fois les bugs arrivent a des effets de bords.

Il faut qu'on ne puisse pas single stepper ou alors que avec un print il faille filtrer les print (possible de trouver le bug en ne printant pas systematiquement)

Technique:
- break function pour regarder les arguments
  * cas special des fonctions recursives ou on peut faire ca
- break conditionnel pour s'arreter quand on condition est vraie (par exemple invariant viole)
- watchpoint
  * simple tracage pour voir l'evolution d'une variable
  * watchpoint memoire pour detecter des alias


=========================

Partie 3 => "Challenge" parfois il faut completement reecrire des bouts de programme (cette fois on suppose qu'on trouve bien les bugs mais cest dur a corriger maintenant en plus)

**** METRIQUES *****
- Temps
- Nombre de compilation
- Nombre d'execution