D’où vient `\n` ?

 (rodarmor.com)
1 points par GN⁺ 2024-10-07 | 1 commentaires | Partager sur WhatsApp
  • just foo traite "\n" dans un justfile et écrit un seul octet 0x0A dans le fichier bar, et l’article remonte étape par étape l’origine de cette valeur
  • Le parseur Rust de just est implémenté de sorte que, lorsqu’il rencontre l’échappement \n, il insère dans la chaîne la valeur de l’échappement de caractère Rust '\n'
  • Comme rustc est aujourd’hui lui aussi écrit en Rust, la recherche se poursuit jusqu’au lexer de rustc, mais on peut trouver un indice plus direct dans l’implémentation OCaml d’avant le self-hosting
  • La première version OCaml de rustc traitait l’échappement de caractère n comme Char.code '\n', et le lexer OCaml le définissait comme '\010'
  • Comme 0x0A vaut 10, le \n du justfile correspond donc à une valeur transmise à travers des générations de compilateurs Rust, dont le point de départ remonte à l’octet placé dans le binaire initial de rustc lorsque le compilateur OCaml a évalué '\010'

Comment le \n d’un justfile devient 0x0A

  • Quand on exécute just foo, le justfile suivant écrit un seul octet 0x0A dans le fichier bar
x := "\n"
foo:
printf '{{x}}' > bar
  • just est écrit en Rust, et la fonction cook_string du parseur convertit les tokens de chaîne just contenant des séquences d’échappement en chaînes UTF-8
  • Si un n suit l’antislash, cette fonction exécute cooked.push('\n')
State::Backslash => {
    match c {
        'n' => cooked.push('\n'),
        …
    }
}
  • À cette étape, just laisse à rustc le soin d’évaluer l’échappement de caractère Rust '\n' avant d’insérer le résultat dans la chaîne

Le chemin en remontant jusqu’à rustc et OCaml

  • Le traitement des échappements dans rustc se trouve dans la fonction scan_escape du lexer, qui, lorsqu’elle rencontre n, le traite à nouveau comme l’échappement de caractère Rust '\n'
let res: char = match chars.next().ok_or(EscapeError::LoneSlash)? {
    …
    'n' => '\n',
    …
};
  • Comme rustc est aujourd’hui écrit en Rust et se compile lui-même, la recherche du sens de '\n' mène de rustc à nouveau vers rustc
  • Toutefois, rustc n’a pas toujours été écrit en Rust, et les premières versions antérieures au self-hosting étaient écrites en OCaml
  • Dans la version OCaml de rustc, le lexer traitait l’échappement de caractère n comme ceci
| 'n' { end_char (Char.code '\n') lexbuf }
  • Là encore, on utilise l’échappement de caractère OCaml '\n', mais le lexer OCaml en donne une définition plus directe
let char_for_backslash = function
  'n' -> '\010'
  • Quand le compilateur OCaml voit \n, il insère le résultat de l’évaluation de l’échappement de caractère décimal '\010', et comme 0x0A vaut 10, cela correspond exactement à l’octet recherché
  • Le \n du justfile mène donc à une forme d’octet 0x0A dans le binaire de just, octet qui a été inséré par rustc, tandis que les versions précédentes de rustc ont transmis cette même valeur de génération en génération
  • La version actuelle de rustc est la 1.81.0 ; même en ne remontant qu’à partir de rustc 1.0, ce processus s’est donc produit au moins 81 fois, et probablement davantage si l’on inclut les versions antérieures à la 1.0
  • Le point de départ de cette traque se situe au moment où le compilateur OCaml a évalué l’échappement de caractère décimal '\010' pour placer l’octet 0x0A dans le binaire initial de rustc

À lire aussi

1 commentaires

 
GN⁺ 2024-10-07
Avis de Hacker News

  • Le premier endroit où j’ai lu cette idée ne portait pas sur le « trusting trust » en général, mais sur le caractère de nouvelle ligne : c’était le jour 42 de https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile...
    Ce qui est intéressant, c’est que pour interpréter "\n" dans un littéral de chaîne comme un véritable caractère de nouvelle ligne, le code source ne contient pas l’information de son code ASCII ; elle est transmise par le compilateur précédent qui a compilé le compilateur
    En fin de compte, le caractère de nouvelle ligne de ce compilateur peut remonter jusqu’à GCC, qui l’a compilé

  • Le texte original auquel l’auteur pense pourrait bien être la conférence de Ken Thompson pour le prix Turing, Reflections on Trusting Trust

    • Cette présentation souligne aussi que cette technique est utilisée plus généralement dans les quines
      Il existe pas mal de recherches, articles et explications sur les quines ; l’auteur a donc pu lire un texte de ce côté-là
      https://en.wikipedia.org/wiki/Quine_(computing)
    • Ce court et excellent article web de 2009 vaut aussi la lecture
      https://www.teamten.com/lawrence/writings/coding-machines/
    • Je ne pense pas que ce soit ça
      Je me souviens moi aussi avoir vu il y a quelques années un billet de trivia exactement similaire à propos de '\n' en Rust, mais je n’arrive plus à en retrouver la source

  • Il est intéressant qu’au bout de 10 heures, aucun fil n’ait mentionné EBCDIC
    Les premiers compilateurs C existaient aussi sur des systèmes non ASCII qui ne faisaient pas correspondre \n, le « saut de ligne » (line feed), au nombre décimal 10 ; toutes les théories évoquées ici doivent donc expliquer ce fait
    https://en.wikipedia.org/wiki/EBCDIC
    En plus, EBCDIC avait à la fois un caractère explicite NextLine et un caractère LineFeed
    En ASCII, for (c = 'A'; c <= 'Z'; ++c) putchar(c); affiche de A à Z, mais en EBCDIC, comme il y a des intervalles vides entre les lettres, cela finit par afficher 41 caractères, y compris des caractères non attribués
    Dans l’ordre EBCDIC, les minuscules précèdent les majuscules, et les lettres précèdent les chiffres, soit l’exact inverse de l’ASCII
    La seule chose que la norme C garantissait à propos de l’encodage des caractères était que les chiffres de '0' à '9' étaient mappés de manière contiguë et croissante
    En théorie, un programme C simple devait pouvoir être compilé depuis le même source et produire la même sortie, que ce soit en ASCII ou en EBCDIC ; en pratique, il y avait beaucoup de pièges

    • EBCDIC possède bien un caractère de nouvelle ligne / ligne suivante, NEL, mais on ne le rencontre pas souvent sur de nombreux systèmes EBCDIC
      Les premiers systèmes EBCDIC (MVS, VM/CMS, OS/400, DOS/VSE, etc.) stockaient le texte sous forme de fichiers orientés enregistrements plutôt que comme des fichiers en flux d’octets, et chaque ligne était un enregistrement de longueur fixe ou variable
      Dans les enregistrements de longueur fixe, on déclarait à la création du fichier une longueur d’enregistrement comme 80 ou 132 ; les lignes courtes étaient généralement complétées avec le caractère espace EBCDIC 0x40, tandis que les lignes longues étaient tronquées ou utilisaient un caractère de continuation
      Les enregistrements de longueur variable étaient précédés d’un Record Descriptor Word (RDW) contenant la longueur, mais ils étaient rares pour les fichiers texte et le code source ; les enregistrements de longueur fixe étaient la norme
      Ainsi, même si NEL existait, il n’était généralement pas utilisé dans les fichiers sur disque
      Les caractères de nouvelle ligne comme NEL sont un signal dans la bande indiquant une frontière de ligne/enregistrement, alors que les systèmes de fichiers orientés enregistrements exprimaient cette frontière hors bande
      Je ne sais pas exactement comment stdio était implémenté dans la bibliothèque runtime des compilateurs C EBCDIC, mais j’imagine qu’en interne, \n était mappé sur NEL, puis que la couche stdio le traitait comme un séparateur d’enregistrements, écrivait chaque enregistrement via un appel système distinct et ajoutait du padding si nécessaire
      Par la suite, la plupart de ces systèmes d’exploitation ont obtenu des sous-systèmes compatibles POSIX et, avec eux, des fichiers en flux d’octets comme sur les systèmes dominants
      Les systèmes IBM prennent généralement en charge l’ajout de balises de page de code aux fichiers, ce qui permet à un fichier de mêler EBCDIC et ASCII, le système d’exploitation effectuant la conversion dans la couche d’entrée/sortie
      Ainsi, une application utilisant EBCDIC au runtime peut lire des fichiers ASCII comme s’ils étaient en EBCDIC, sans appel à une API de conversion distincte ni spécification explicite
      Les nouvelles applications utilisent de plus en plus des systèmes de fichiers basés sur POSIX, mais les anciennes applications stockent encore souvent leurs données, fichiers texte et même leur code source dans des systèmes de fichiers classiques orientés enregistrements
      D’après ce que je comprends, l’endroit où l’on avait le plus de chances de voir EBCDIC NEL en pratique était les connexions de terminaux en mode ligne de terminaux à impression comme l’IBM 2741 et l’IBM 3767

  • C’est un texte vraiment fascinant
    Pour moi, il se lit comme un mélange de programmation littéraire et de poésie
    Il essaie d’expliquer l’idée que l’octet 0x0A précis qui apparaît quand on exécute just foo a peut-être traversé des centaines de cycles de génération de code
    Il y a longtemps, quelqu’un a encodé cette information d’une manière ou d’une autre dans le compilateur OCaml, et quelques années plus tard, l’information 0x0A présente sur mon ordinateur existe à cause de cette histoire
    Et pourtant, ce phénomène est expliqué par du vrai code
    Bien sûr, le code lui-même n’est pas l’essentiel, et il est peu probable que quelqu’un exécute ou compile ce code précis ; il est là pour permettre au lecteur de suivre la discussion

  • Je me demandais si clang avait la même propriété ; dans lib/Lex/LiteralSupport.cpp, c’est explicitement codé en dur à 10
    ProcessCharEscape parse les séquences d’échappement C standard et traite cela comme dans case 'n': ResultChar = 10; break;

    • GCC fait quelque chose de similaire dans gcc/libcpp/charset.cc, où c’est codé en dur, et choisit entre ASCII ou EBCDIC
      Il met les valeurs de \a \b \e \f \n \r \t \v dans le tableau charconsts, utilise { 7, 8, 27, 12, 10, 13, 9, 11 } pour ASCII et { 47, 22, 39, 12, 21, 13, 5, 11 } pour EBCDIC, puis traite le cas avec case 'n': c = charconsts[4]; break;

  • Je me souviens d’un article similaire à propos d’un compilateur C
    Au final, le seul endroit où apparaissait la valeur 0x10 était le binaire du compilateur ; dans le code source, cela n’apparaissait que sous une forme du genre "\\n" -> "\n"

  • C’est au-dessus de mon niveau
    Je ne comprends pas pourquoi il faut un périple aussi long pour découvrir pourquoi \n est encodé comme un octet de valeur 10
    J’ai l’impression que ça devrait être évident, et comme l’auteur et les commentaires ne l’expliquent pas, je me sens idiot

    • Le point central est de demander “qui” a encodé cet octet avec la valeur 10
      Si, en écrivant un parseur, on parse un saut de ligne comme la séquence d’échappement \n, d’où vient la valeur 10 ?
      Si l’on parse un saut de ligne comme le littéral entier 10, d’où vient la valeur binaire réelle 1010 ?
      Le but ultime de cette expérience de pensée est de changer notre perception des compilateurs, comme dans la célèbre conférence Reflections On Trusting Trust
      Autrement dit, un compilateur n’est pas seulement quelque chose qui produit un programme, c’est aussi une entrée du programme
      Comme le compilateur lui-même est un programme, le compilateur qui a construit ce compilateur était une entrée du compilateur actuel et, par transitivité, devient une entrée de mon programme
      Et cela continue avec le compilateur du compilateur du compilateur, puis encore celui d’au-dessus, et ainsi de suite
    • Ce qui est intéressant, c’est que la valeur 10 n’est pas définie dans le code source de Rust, mais se transmet oralement, de compilateur en compilateur
    • Si l’on devait reconstruire le compilateur Rust à partir de zéro en n’ayant que le code source de rustc, il n’y aurait nulle part dans le source d’information indiquant à quoi '\n' correspond réellement
      C’est un exemple réel intéressant du hack de Ken Thompson
    • Le cœur du sujet, c’est pourquoi 10 précisément
      Pourquoi pas 9 ou 11 ?
      Le code dit : “quand vous voyez la chaîne du caractère de nouvelle ligne, affichez le caractère de nouvelle ligne”
      Mais comment le compilateur sait-il ce qu’est un caractère de nouvelle ligne ?
      Le code de ce compilateur, lui aussi, se contente de dire : “quand vous voyez la chaîne du caractère de nouvelle ligne, traitez-la comme un caractère de nouvelle ligne”
      Un humain peut chercher “codes d’échappement des chaînes C”, mais ce tableau n’existe nulle part dans le compilateur
      Si C 2025 définissait Start of Heading comme \h, est-ce que 'h' => cooked.push('\h') commencerait à marcher par magie ?
      Comment pourrait-il le savoir ?
      Il est clair qu’à un moment donné, quelqu’un a programmé manuellement le mapping 'n' => 10 ; la question est de savoir où

  • À cause du C, j’ai toujours pensé que \0??? était un échappement octal
    Donc, dans ma tête, \012 vaut \x0a ou 0x0a, et \010 vaut 0x08
    Du coup, cet article me déroute pas mal
    Peut-être qu’OCaml n’a pas d’échappements octaux mais des échappements décimaux, et que \09 est peut-être le caractère tabulation
    Je n’ai pas vérifié

    • Il y a quelque chose de juste dans cette direction, mais cela n’a rien à voir avec les échappements par backslash
      Les échappements par backslash sont symboliques/mnémotechniques : \n pour “[Ne]wline”, \r pour “carriage [R]eturn”, \t pour “[T]ab”, etc.
      Il faut plutôt regarder la convention des caractères de contrôle comme ^C (interruption), ^G (bell), ^M (carriage return)
      Ils font partie du jeu de caractères de contrôle C0, et ^C vaut \0x3, ^G vaut \0x7, ^M vaut \0xD
      C’est une méthode astucieuse qui remonte à avant Unix : pour représenter les caractères C0 invisibles d’ASCII, les terminaux préfixaient avec le caractère ^ et appliquaient AND-0x40 au caractère concerné afin de le déplacer dans la plage affichable
      Pour suivre, il peut être utile d’ouvrir une table ASCII comme https://www.asciitable.com
      Chaque caractère de contrôle y est associé au ^caractère situé deux colonnes plus loin dans la table
      C’est ainsi que \0 se retrouve bizarrement représenté par ^@, que la touche Esc devient ^[, et que naissent d’autres équivalences difficiles à mémoriser
      Ce n’est pas un choix des auteurs d’Unix, mais un produit de la numérotation ASCII
    • En réalité, OCaml utilise bien des échappements décimaux : https://ocaml.org/manual/5.2/lex.html#char-literal
    • Les échappements de caractères backslash-décimal sont vraiment rares
      Parmi les syntaxes de chaînes que je connais, il n’y a guère que OCaml, Lua et DNS

  • À cause de la capitalisation incorrecte, j’ai cru qu’il existait peut-être une autre séquence d’échappement \N, presque inconnue et différente de \n
    Je me suis demandé si cela correspondait à n’importe quel caractère sauf une nouvelle ligne, mais non : c’était à cause des petites capitales dans l’article d’origine

    • Si l’on affiche le source, c’est bien \n, mais cette règle CSS empêche de l’afficher ainsi
      .title { font-variant: small-caps; }
    • Il existe effectivement des endroits où \N est utilisé
      Beaucoup de systèmes s’en servent comme NULL dans du CSV ou des formats similaires, pour le distinguer d’une chaîne vide
      Je pensais donc que l’article parlait de ça
    • Python a une séquence d’échappement \N
      Elle insère un caractère Unicode par son nom
      Par exemple, '\N{PILE OF POO}' est une chaîne Unicode contenant un seul emoji caca
      C’est bien plus auto-descriptif que d’utiliser une séquence hexadécimale avec \u ou \U
    • C’est aussi pour ça que j’ai cliqué sur cet article
      Mais je l’ai quand même lu avec plaisir

  • L’« autre article » qui a inspiré ce billet est probablement celui-ci
    https://research.swtch.com/nih