Au final, on finit toujours par utiliser `git bisect`

• Le concept de recherche binaire (binary search) ne sert pas seulement aux questions d’entretien : il est aussi utilisé dans un outil de développement bien réel, Git
• Dans un environnement de monorepo à grande échelle, quand des tests se mettent soudainement à échouer, il peut devenir difficile de remonter à la cause à partir des seuls logs
• Un collègue a indiqué un bon commit et un mauvais commit, puis lancé une recherche automatique avec git bisect, ce qui a permis d’identifier précisément le commit fautif à l’origine du bug
• À chaque étape, un script est exécuté pour classer automatiquement les commits selon le résultat des tests, afin d’identifier le premier commit qui fait échouer
• En s’appuyant sur le principe de la recherche binaire, git bisect est un outil puissant pour retrouver rapidement l’origine d’un bug dans une base de code volumineuse

---

Algorithme et cas concret

• L’algorithme de recherche binaire (binary search) dépasse largement le cadre des simples questions d’entretien : c’est aussi un principe clé dans de vrais outils de débogage
• git bisect peut être utilisé comme un outil qui emploie la recherche binaire pour trouver « le commit qui a introduit le bug pour la première fois (first bad commit) »
  • Il fonctionne selon un principe similaire au problème « First Bad Version » de Leetcode

Le problème en conditions réelles

• Dans un environnement reposant sur un monorepo de grande taille, des centaines voire des milliers de commits peuvent être produits chaque jour
• Il est difficile de retrouver la cause d’un échec de test à partir des seuls logs
• La cause de l’échec venait d’une modification de chaîne de caractères dans un fichier de configuration servant à obtenir le token nécessaire à un appel distant, ce qui faisait référence à un autre compte et entraînait l’échec du test
• Cette modification avait passé les tests d’intégration, tout en provoquant un problème réel, et il était difficile de savoir à quel moment précis elle était apparue parmi tous ces commits

Résoudre le problème avec git bisect

• Un collègue d’une autre équipe a rapidement identifié le commit problématique à l’aide de la commande git bisect
  • Après avoir défini un bon commit (good) et un mauvais commit (bad), l’outil checkout automatiquement les commits intermédiaires, exécute les tests et réduit progressivement le champ des causes possibles
  • Chaque exécution de test prenait du temps, mais cela a finalement permis de retrouver exactement le commit qui a introduit le problème
  • Une fois ce commit annulé, tous les tests sont revenus à la normale

Déroulement de git bisect

• Exemple d’historique de commits
  • Commit 1 : commit initial (normal)
  • Commit 2 : refactorisation (normal)
  • Commit 3 : introduction du bug (erreur)
  • Commit 4~10 : modifications non fonctionnelles (l’erreur persiste)
• Exemple de commandes

  git bisect start  
  git bisect bad HEAD  
  git bisect good HEAD~9  
  git bisect run ./test_script.sh  
  

• Le script de test (test_script.sh) renvoie 0 en cas de succès, et un code non nul en cas d’échec
• git bisect checkout automatiquement les commits intermédiaires et exécute le script de test, puis identifie le premier mauvais commit à partir du moment où le test commence à échouer
• La sortie montre que le commit b982ed9373fe235fe61c74b15faf264bc7142398 est bien le premier commit ayant introduit le bug

Conclusion

• git bisect est un outil pratique qui applique le principe de la recherche binaire à l’exploration de l’historique du code
• Même dans un grand dépôt ou avec un historique de modifications complexe, il permet de retrouver rapidement le moment où un bug a été introduit
• Combiné à l’automatisation des tests, il rend possible un débogage fiable même dans des bases de code volumineuses

[kandk]

C’est pour ce type de problèmes qu’on utilise le TBD (trunk-based development).

[GN⁺]

Commentaires sur Hacker News

• Quand je travaillais autrefois sur une énorme base de code sans couverture de tests et avec des abstractions désastreuses, git bisect était pratiquement le seul outil vraiment utile
  Le code était tellement complexe qu’il était impossible de remonter logiquement jusqu’au bug, donc il était bien plus simple d’identifier à partir de quel commit le problème était apparu
  En revanche, sur une base de code de haute qualité, je n’avais pas vraiment besoin de bisect. Chaque composant pouvait être testé indépendamment, et l’observabilité était suffisamment bonne pour savoir clairement où regarder

  • Je ne pense pas que git bisect soit jamais inutile. Il ne sert pas seulement à trouver un bug, mais aussi à comprendre pourquoi il est apparu
    Dans un projet avec de bons messages de commit, bisect permet de retrouver le contexte d’anciens commits et de réinjecter ces éléments dans le commit de correction. Ce cercle vertueux renforce la culture du commit elle-même
  • J’ai déjà trouvé un bug dans un programme OSS où une chaîne étrange apparaissait. C’était du code C, et la cause était une variable non initialisée
    Il était impossible de le tracer directement, mais en écrivant un script bisect et en le laissant tourner une trentaine de minutes, j’ai pu identifier précisément le commit fautif
  • git bisect a été introduit à l’origine pour trouver des régressions du noyau Linux
    Même dans des cas impossibles à tester comme les pilotes matériels, les utilisateurs ordinaires ont pu bisecter eux-mêmes le noyau pour identifier le commit en cause
    Autrefois, il fallait demander de l’aide aux développeurs par e-mail, mais désormais les utilisateurs peuvent eux-mêmes réduire le champ du problème
  • Si l’objectif est simplement de corriger un bug, bisect n’est peut-être pas nécessaire. Mais il arrive qu’on ait besoin de savoir depuis quand il existe
    Par exemple pour suivre l’étendue de données mal traitées, ou pour décider si « c’est un bug ou une fonctionnalité »
  • Parfois, il faut aussi savoir quand le bug a été corrigé
    Par exemple, lorsqu’un client rencontre un problème sur une version vieille de 6 ans, on peut vérifier si une mise à niveau vers une version vieille de 4 ans le résout
    Ou, quand le code a été fortement refactoré, on peut déterminer si la correction du bug était intentionnelle ou accidentelle

• git bisect est excellent quand il fonctionne bien, mais il ne permet pas de trouver tous les bugs
  Certains bugs n’ont aucun symptôme au moment de leur introduction et ne se révèlent qu’ensuite, à cause d’un autre changement
  Dans ce cas, l’hypothèse de bisect — le fait que le bug n’apparaisse qu’une seule fois entre un bon commit et un mauvais commit — s’effondre
  On peut skip les commits impossibles à tester, mais si c’est justement le commit fautif, le résultat devient ambigu

• J’ai récemment utilisé git bisect sérieusement pour la première fois, et c’était presque magique
  Il y avait deux fonctions portant le même nom, et le problème est apparu pendant un travail de formatage du code, quand l’import de la bonne fonction a été supprimé
  J’ai relu le code plusieurs fois, mais je n’ai absolument pas compris la cause avant que bisect n’identifie le commit fautif

• En général, je connais déjà le fichier ou la fonction où se situe le bug, donc je n’utilise pas souvent bisect
  À la place, j’utilise la commande git log -L :func_name:path/to/file.c pour suivre l’historique des modifications d’une fonction précise
  Une configuration .gitattributes est nécessaire

  • Quelqu’un a demandé des précisions sur la configuration .gitattributes, en disant vouloir en savoir plus sur ce qu’il fallait y mettre
  • Certains disaient utiliser bisect tous les jours. Le workflow est complètement différent
  • Dans des cas comme le C++ avec des fonctions polymorphes, git log -L est moins efficace, car il est difficile de suivre une version précise parmi plusieurs surcharges portant le même nom
  • Sans .gitattributes, une autre option consiste à utiliser git log -S pour trouver les commits contenant une chaîne donnée

• Dans un script de test, il est utile de connaître le code de sortie 125
  Quand il est impossible de déterminer le résultat du test, par exemple à cause d’un échec de compilation, retourner 125 fait que bisect saute ce commit
  J’ai résumé le sujet dans un billet de blog

  • Dans les dépôts où les commits de fusion représentent les points ayant passé la CI, git bisect --first-parent peut être très utile
    Cela permet de trouver rapidement « quelle PR a introduit le bug », puis d’effectuer ensuite un bisect plus fin sur cette branche

• Quand on a affaire à un test flaky, bisect montre toute sa valeur
  Si, à cause d’une race condition, il faut exécuter le test des centaines de milliers de fois pour être certain, laisser tourner un script bisect en arrière-plan permet de résoudre le problème de façon réaliste

  • Dans ce cas, on pourrait probablement appliquer une recherche binaire bayésienne pour réduire fortement le nombre d’exécutions de test

• J’ai récemment trouvé la cause d’un bug par bisect dans un projet de lecteur de musique en Svelte (lets-make-sweet-music.com)
  Il n’y avait ni tests ni logs d’erreur, et les mises à jour de dependabot avaient multiplié les commits, ce qui rendait le suivi difficile
  Grâce à bisect, j’ai trouvé le commit fautif, et la cause était que le fichier que j’avais remplacé n’implémentait pas la fonction de liaison multiple d’événements
  Garder des commits petits permet de resserrer rapidement la cause du problème trouvé avec bisect

• Quelqu’un disait que l’idée d’apprendre la recherche binaire pour les entretiens d’embauche était artificielle, mais git bisect est un bon exemple concret de ce concept
  En revanche, il n’est pas nécessaire de l’implémenter soi-même. La plupart des langages la fournissent déjà dans leur bibliothèque standard

  • Fait intéressant, on raconte que la recherche binaire a été proposée pour la première fois dans les années 1940, mais qu’une implémentation sans bug n’est apparue que dans les années 1960
    Si on calcule l’indice médian avec (low + high) / 2, il peut y avoir un débordement
  • Personnellement, je pense que tous les développeurs devraient implémenter une fois la recherche binaire eux-mêmes dans un langage à entiers de précision arbitraire (par exemple Python)
    C’est le meilleur exercice pour s’entraîner à raisonner à partir d’invariants

• En plus de bisect, Git propose aussi d’excellents outils d’exploration du code comme log -L, log -S et blame
  J’ai déjà écrit un billet de blog sur ce sujet