DOOM exécuté avec des types TypeScript [vidéo]

• Une expérience qui démarre le jeu DOOM de 1993 non pas avec du code runtime, mais uniquement avec le système de types de TypeScript, jusqu’à produire la première frame
• Pour atteindre cette première frame, le vérificateur de types TypeScript a traité 3,5 billions de lignes, soit 177 To au total, pendant 12 jours ; l’estimation initiale était de 1,25 Po et de plus de 3 mois
• Le cœur de l’implémentation est une machine virtuelle WebAssembly construite avec des types : les 116 instructions nécessaires à DOOM ont été implémentées en logique au niveau des types, avec l’évaluation de 18 millions d’instructions
• Pendant le développement, les limites du compilateur liées à la récursion, aux unions, aux tuples et à l’instanciation de types profonds ont été supprimées, mais le résultat final reste du TypeScript vanilla exécutable par l’utilisateur
• L’échelle dépasse de très loin le type checking d’une application classique, au point de rendre presque inutilisables les outils de développement existants ; il a fallu créer 12 364 tests et des outils custom

---

Un ordinateur créé dans le système de types de TypeScript

• DOOM ne s’exécute pas en JavaScript classique, mais uniquement dans le système de types de TypeScript
• L’objectif était de créer une machine virtuelle WebAssembly capable d’exécuter d’autres programmes uniquement avec des types, sans tricher ni recourir à un autre langage d’exécution
• Cet ordinateur au niveau des types possède, sous forme de types, les composants de base nécessaires à l’exécution
  • RAM
  • Espace disque
  • Pile d’appels
  • Sous-routines
  • Pointeurs mémoire
  • Contextes d’exécution
  • Outils de développement custom
• Les 116 instructions WebAssembly nécessaires à l’exécution de DOOM ont été implémentées en logique avec des types TypeScript
• À elle seule, cette logique a produit 18 millions d’instructions que le vérificateur de types devait évaluer une par une, chaque instruction représentant un état machine unique du système

L’échelle nécessaire pour atteindre la première frame

• Obtenir la première frame de DOOM a nécessité 3,5 billions de lignes de types, pour une taille totale de 177 To
• Le compilateur TypeScript TSC a tourné en continu pendant 12 jours pour démarrer le jeu et obtenir la première frame
• Les premiers calculs estimaient que l’ordinateur devrait traiter 1,25 Po de types TypeScript, avec un temps d’exécution attendu de plus de 3 mois
• Après des optimisations extrêmes, la charge a été réduite à 177 To et 12 jours
• Dans une application classique, le type checking par TSC tourne généralement autour de 200 000 à 500 000 instanciations de types, alors que ce projet a maintenu 20 millions d’instanciations par seconde pendant 12 jours
• La sortie finale est un objet TypeScript, dont chaque valeur représente une ligne de pixels
  • La frame de sortie fait 320×200
  • Il s’agit d’une frame ASCII de 128 000 pixels au total
• Il existe aussi une méthode pour contrôler le jeu au clavier

Protections TypeScript supprimées pendant le développement

• Le résultat final est du TypeScript vanilla que l’utilisateur peut exécuter lui-même
• Pour rendre l’expérience possible, le compilateur TypeScript a été modifié afin de supprimer plusieurs limites
  • Suppression de la limite de profondeur de pile excessive lors de la comparaison de types
  • Suppression de la limite sur les instanciations de types trop profondes ou potentiellement infinies
  • Définition de la taille maximale des unions et des tuples à Infinity
  • Suppression de la limite de troncature de la sortie
  • Suppression de la célèbre limite de récursion de TypeScript
• La limite de pile de la machine elle-même a également été relevée
• Une fois ces protections supprimées, le vérificateur de types pouvait facilement utiliser 100 Go de mémoire
• Le coût de cette suppression était élevé
  • Même un problème mineur, comme une faute de frappe dans un import, pouvait créer une boucle infinie
  • Les allocations sur le tas pouvaient consommer toute la mémoire et faire crasher l’ensemble
  • Les stack traces étaient énormes et, la plupart du temps, les échecs se manifestaient simplement par un blocage

Ce qu’il a fallu créer en plus pour exécuter DOOM

• Après 6 mois de travail, il était possible d’exécuter de petits programmes en C, mais faire tourner DOOM nécessitait bien davantage d’implémentation
• Tous les composants de DOOM ont dû être encodés sous forme de types
  • Cartes du jeu
  • Textures
  • Sprites
  • Sons
  • IA des ennemis
  • Armes
  • Objets
  • Moteur physique
  • Sous-système audio
  • Textes en jeu
• Des fonctionnalités proches du runtime ont également été implémentées au niveau des types
  • Garbage collector
  • Cache CPU L1
  • Dead code elimination au runtime
  • Compacteur mémoire en temps réel
  • Pile globale de valeurs avec comptage de profondeur pour protéger contre les stack underflows
  • Table de dispatch dynamique
  • Variables globales au niveau module
  • goto labellisé
  • Gestion d’exceptions au niveau des types
  • Stack tracing au runtime
  • Core dump complet
• La RAM linéaire est représentée par un énorme objet non triable, avec des clés d’adresse 32 bits et des valeurs d’octets
• Une méthode pour suspendre l’évaluation des types dans l’espace utilisateur des types a été trouvée, rendant possibles les core dumps, la gestion d’exceptions et le stack tracing

Limites des outils et contraintes d’implémentation

• Des fichiers allant jusqu’à 1 Go ont été nécessaires, au-delà de ce que Prettier peut traiter
• L’intégration au serveur de langage et les linters plantaient immédiatement ; en pratique, seule la coloration syntaxique fonctionnait à peine
• L’intérieur du moteur est implémenté avec du binaire en complément à deux stocké dans des littéraux de chaîne
• TypeScript ne pouvant parcourir les chaînes que de gauche à droite, tous les algorithmes binaires ont dû être implémentés à l’envers
• À l’intérieur du moteur, il n’y a ni tableaux, ni objets, ni chaînes, ni booléens : uniquement du binaire
• DOOM n’utilise que des entiers 64 bits et 32 bits, et ces entiers ne sont ni signed ni unsigned, ce qui a pris une journée à comprendre
• Au départ, le créateur ne connaissait même pas 10 % des savoirs nécessaires ; il a créé ses propres outils, écrit à la main 12 364 tests et appris plusieurs langages de programmation au passage