Woher kommt `"\n"`?

 (rodarmor.com)
1 Punkte von GN⁺ 2024-10-07 | 1 Kommentare | Auf WhatsApp teilen
  • just foo verarbeitet "\n" aus dem justfile und schreibt das einzelne Byte 0x0A in die Datei bar; der Artikel verfolgt Schritt für Schritt, woher dieser Wert kommt
  • Der Rust-Parser von just ist so implementiert, dass er beim Escape \n den Rust-Zeichen-Escape-Wert '\n' in den String einfügt
  • Da auch rustc derzeit in Rust geschrieben ist, führt die Verfolgung weiter zum Lexer von rustc, doch in der OCaml-Implementierung vor dem Self-Hosting findet sich ein direkterer Hinweis
  • Das frühe rustc in OCaml behandelte den Zeichen-Escape n als Char.code '\n', und der OCaml-Lexer definiert dies als '\010'
  • Da 0x0A gleich 10 ist, ist \n im justfile also ein über Compiler-Generationen von Rust weitergereichter Wert, dessen Ursprung bei dem Byte liegt, das der OCaml-Compiler durch Auswertung von '\010' in das frühe rustc-Binary geschrieben hat

Wie \n im justfile zu 0x0A wird

  • Führt man just foo aus, schreibt das folgende justfile das einzelne Byte 0x0A in die Datei bar
x := "\n"
foo:
printf '{{x}}' > bar
  • just ist in Rust geschrieben, und die Funktion cook_string des Parsers wandelt just-String-Tokens mit Escape-Sequenzen in UTF-8-Strings um
  • Steht nach dem Backslash ein n, führt diese Funktion cooked.push('\n') aus
State::Backslash => {
    match c {
        'n' => cooked.push('\n'),
        …
    }
}
  • An dieser Stelle überlässt just rustc, das Ergebnis der Auswertung des Rust-Zeichen-Escapes '\n' in den String einzusetzen

Der Pfad zurück über rustc bis zu OCaml

  • Die Escape-Behandlung in rustc befindet sich in der Funktion scan_escape des Lexers; trifft sie auf n, verarbeitet sie es erneut als den Rust-Zeichen-Escape '\n'
let res: char = match chars.next().ok_or(EscapeError::LoneSlash)? {
    …
    'n' => '\n',
    …
};
  • Das heutige rustc ist in Rust geschrieben und kompiliert sich selbst, daher führt die Suche nach der Bedeutung von '\n' von rustc wieder zu rustc
  • rustc war jedoch nicht von Anfang an in Rust geschrieben; die frühen Versionen vor dem Self-Hosting waren in OCaml geschrieben
  • Der Lexer der OCaml-Version von rustc behandelte den Zeichen-Escape n so:
| 'n' { end_char (Char.code '\n') lexbuf }
  • Auch hier wird der OCaml-Zeichen-Escape '\n' verwendet, doch im OCaml-Lexer gibt es eine direktere Definition
let char_for_backslash = function
  'n' -> '\010'
  • Wenn der OCaml-Compiler \n sieht, setzt er das Ergebnis der Auswertung des dezimalen Zeichen-Escapes '\010' ein; und da 0x0A gleich 10 ist, entspricht dies genau dem gesuchten Bytewert
  • Damit führt \n im justfile zu einer Form des Bytes 0x0A im just-Binary; dieses Byte wurde von rustc eingefügt, wobei frühere rustc-Generationen denselben Wert weitergereicht haben
  • Die aktuelle rustc-Version ist 1.81.0; betrachtet man nur die Versionen seit rustc 1.0, ist dieser Vorgang mindestens 81-mal passiert, und unter Einbeziehung der Zeit vor 1.0 möglicherweise noch öfter
  • Der Ausgangspunkt der Verfolgung liegt dort, wo der OCaml-Compiler den dezimalen Zeichen-Escape '\010' ausgewertet und das Byte 0x0A in das frühe rustc-Binary geschrieben hat

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-10-07
Meinungen auf Hacker News

  • Wo ich diese Idee zum ersten Mal gelesen habe, ging es nicht um das allgemeine „trusting trust“, sondern um das Zeilenumbruchzeichen: Tag 42 von https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile...
    Interessant ist, dass zur Interpretation von "\n" innerhalb eines String-Literals als tatsächliches Zeilenumbruchzeichen diese ASCII-Code-Information nicht im Quellcode steckt, sondern vom vorherigen Compiler weitergegeben wird, mit dem der Compiler kompiliert wurde.
    Letztlich lässt sich das Zeilenumbruchzeichen dieses Compilers bis zu dem GCC zurückverfolgen, der ihn kompiliert hat.

  • Der Originaltext, an den der Autor gedacht hat, dürfte Ken Thompsons Turing-Award-Vortrag Reflections on Trusting Trust gewesen sein.

    • Auch dieser Vortrag weist darauf hin, dass diese Technik allgemeiner bei Quines verwendet wird.
      Es gibt ziemlich viel Forschung, Papers und Erklärungen zu Quines; vielleicht hat der Autor etwas in dieser Richtung gelesen.
      https://en.wikipedia.org/wiki/Quine_(computing)
    • Auch dieser kurze, hervorragende Webtext von 2009 ist lesenswert:
      https://www.teamten.com/lawrence/writings/coding-machines/
    • Das wird es wohl eher nicht gewesen sein.
      Ich erinnere mich auch daran, vor ein paar Jahren genau denselben Trivia-Artikel über Rusts '\n' gesehen zu haben, finde die Quelle aber nicht mehr.

  • Interessant, dass nach 10 Stunden noch kein Thread EBCDIC erwähnt hat.
    Frühe C-Compiler gab es auch auf Nicht-ASCII-Systemen, die \n für „line feed“ nicht auf den Dezimalwert 10 abbildeten; jede hier diskutierte Theorie muss also auch diese Tatsache erklären.
    https://en.wikipedia.org/wiki/EBCDIC
    Außerdem hatte EBCDIC sowohl ein explizites NextLine-Zeichen als auch ein LineFeed-Zeichen.
    In ASCII gibt for (c = 'A'; c <= 'Z'; ++c) putchar(c); die Buchstaben A bis Z aus; in EBCDIC gibt es dagegen Lücken zwischen den Buchstaben, sodass einschließlich nicht zugewiesener Zeichen 41 Zeichen ausgegeben werden.
    In der EBCDIC-Sortierung stehen Kleinbuchstaben vor Großbuchstaben und Buchstaben vor Ziffern, also genau umgekehrt zu ASCII.
    Der C-Standard garantierte für Zeichenkodierungen nur, dass die Ziffern '0' bis '9' fortlaufend und aufsteigend abgebildet sind.
    Theoretisch sollten einfache C-Programme aus demselben Quellcode sowohl unter ASCII als auch unter EBCDIC kompiliert werden und dieselbe Ausgabe erzeugen, praktisch gab es aber viele Fallstricke.

    • In EBCDIC gibt es zwar das Zeilenumbruch-/Next-Line-Zeichen NEL, aber auf vielen EBCDIC-Systemen begegnet man ihm nicht häufig.
      Frühe EBCDIC-Systeme (MVS, VM/CMS, OS/400, DOS/VSE usw.) speicherten Text nicht als Byte-Stream-Dateien, sondern als record-orientierte Dateien; jede Zeile war ein Datensatz fester oder variabler Länge.
      Bei Datensätzen fester Länge wurde beim Erstellen der Datei eine Satzlänge wie 80 oder 132 deklariert; kurze Zeilen wurden gewöhnlich mit dem EBCDIC-Leerzeichen 0x40 aufgefüllt, lange Zeilen abgeschnitten oder mit einem Fortsetzungszeichen versehen.
      Datensätze variabler Länge hatten ein vorangestelltes Record Descriptor Word (RDW) mit der Länge, waren für Textdateien und Quellcode aber selten; feste Satzlängen waren üblich.
      Daher wurde NEL in Dateien auf der Platte normalerweise nicht verwendet, obwohl es existierte.
      Zeilenumbruchzeichen wie NEL sind In-Band-Signale für Zeilen-/Datensatzgrenzen, während record-orientierte Dateisysteme diese Grenzen out-of-band darstellen.
      Ich weiß nicht, wie stdio in der Laufzeitbibliothek von EBCDIC-C-Compilern genau implementiert war, vermute aber, dass \n intern auf NEL gemappt wurde, die stdio-Schicht es dann als Datensatztrenner behandelte und jeden Datensatz bei Bedarf mit Padding als separaten Systemaufruf schrieb.
      Später erhielten die meisten dieser Betriebssysteme POSIX-kompatible Subsysteme und damit auch Byte-Stream-Dateien wie auf Mainstream-Systemen.
      IBM-Systeme unterstützen allgemein das Kennzeichnen von Dateien mit Codepage-Tags, sodass Dateien EBCDIC und ASCII gemischt enthalten können und das Betriebssystem in der Ein-/Ausgabeschicht konvertiert.
      Dadurch können auch Anwendungen, die zur Laufzeit EBCDIC verwenden, ASCII-Dateien ohne separate Konvertierungs-API-Aufrufe oder explizite Angabe wie EBCDIC lesen.
      Neue Anwendungen nutzen zunehmend POSIX-basierte Dateisysteme, aber ältere Anwendungen speichern Daten, Textdateien und sogar Quellcode oft weiterhin in klassischen record-orientierten Dateisystemen.
      Soweit ich es verstehe, konnte man EBCDIC NEL in der Praxis am ehesten bei Line-Mode-Terminal-Verbindungen von Hardcopy-Terminals wie IBM 2741 oder IBM 3767 antreffen.

  • Ein wirklich interessanter Text.
    Für mich liest er sich wie eine Mischung aus literarischem Programmieren und Poesie.
    Er versucht zu vermitteln, dass genau dieses 0x0A-Byte, das beim Ausführen von just foo erscheint, möglicherweise durch Hunderte Zyklen der Codegenerierung gegangen ist.
    Vor langer Zeit hat jemand diese Information auf irgendeine Weise in den OCaml-Compiler kodiert, und Jahre später ist die 0x0A-Information auf meinem Computer aufgrund dieser Geschichte gespeichert.
    Dieses Phänomen wird aber mit echtem Code erklärt.
    Natürlich ist der Code selbst nicht der Kern der Sache, und es ist auch unwahrscheinlich, dass jemand genau diesen Code ausführt oder kompiliert; er ist dafür da, dass Menschen der Diskussion folgen können.

  • Ich fragte mich, ob clang dieselbe Eigenschaft hat; in lib/Lex/LiteralSupport.cpp ist es ausdrücklich hart auf 10 codiert.
    ProcessCharEscape parst die Standard-C-Escape-Sequenzen und behandelt sie etwa mit case 'n': ResultChar = 10; break;.

    • GCC macht es ähnlich: In gcc/libcpp/charset.cc ist es hartcodiert und wählt zwischen ASCII oder EBCDIC.
      Die Werte von \a \b \e \f \n \r \t \v werden in das Array charconsts gelegt; bei ASCII wird { 7, 8, 27, 12, 10, 13, 9, 11 } verwendet, bei EBCDIC { 47, 22, 39, 12, 21, 13, 5, 11 }, und anschließend wird es mit case 'n': c = charconsts[4]; break; behandelt.

  • Ich erinnere mich an einen ähnlichen Artikel über irgendeinen C-Compiler.
    Am Ende stellte sich heraus, dass die einzige Stelle, an der der Wert 0x10 auftauchte, das Compiler-Binary war; im Quellcode stand er nur in Formen wie "\\n" -> "\n".

  • Das geht über mein Niveau hinaus.
    Ich verstehe nicht, warum man so eine lange Reise unternehmen muss, um herauszufinden, warum \n als Byte mit dem Wert 10 codiert wird.
    Es wirkt doch selbstverständlich, und weil weder der Autor noch die Kommentare es erklären, fühle ich mich dumm.

    • Der Kernpunkt ist die Frage, „wer“ dieses Byte als Wert 10 codiert hat.
      Wenn man einen Parser schreibt und einen Zeilenumbruch als Escape-Sequenz \n parst: Woher kommt dann der Wert 10?
      Wenn man den Zeilenumbruch als Integer-Literal 10 parst: Woher kommt dann der tatsächliche Binärwert 1010?
      Das letztliche Ziel dieses Gedankenexperiments ist, ähnlich wie im berühmten Vortrag Reflections On Trusting Trust, die Sicht auf Compiler zu verändern.
      Ein Compiler ist also nicht einfach etwas, das ein Programm ausgibt, sondern auch Eingabe eines Programms.
      Da der Compiler selbst ein Programm ist, war der Compiler, der diesen Compiler erzeugt hat, eine Eingabe des aktuellen Compilers und ist transitiv eine Eingabe meines Programms.
      Und das setzt sich beim Compiler des Compilers des Compilers und bei den darüberliegenden Compilern immer weiter fort.
    • Interessant ist, dass der Wert 10 nicht im Rust-Quellcode definiert ist, sondern von Compiler zu Compiler wie mündliche Überlieferung weitergegeben wird.
    • Wenn man den Rust-Compiler von Grund auf neu bauen müsste und nur den rustc-Quellcode hätte, gäbe es im Quellcode nirgends eine Information darüber, worauf '\n' tatsächlich abgebildet wird.
      Das ist ein interessantes reales Beispiel für den Ken-Thompson-Hack.
    • Der Kernpunkt ist, warum ausgerechnet 10.
      Warum nicht 9 oder 11?
      Der Code sagt: „Wenn du die Zeichenkette für einen Zeilenumbruch siehst, gib einen Zeilenumbruch aus.“
      Aber woher weiß der Compiler, was ein Zeilenumbruch ist?
      Auch der Code dieses Compilers sagt wiederum nur: „Wenn du die Zeichenkette für einen Zeilenumbruch siehst, behandle sie als Zeilenumbruch.“
      Ein Mensch kann nach „C string escape codes“ suchen, aber diese Tabelle steckt nirgends im Compiler.
      Wenn C 2025 Start of Heading als \h definiert, würde dann 'h' => cooked.push('\h') auf magische Weise anfangen zu funktionieren?
      Woher sollte man das überhaupt wissen?
      Irgendwann muss irgendjemand die Abbildung 'n' => 10 manuell programmiert haben; die Frage ist, wo diese Stelle ist.

  • Wegen C habe ich \0??? immer für einen oktalen Escape gehalten.
    In meinem Kopf ist \012 daher \x0a beziehungsweise 0x0a, und \010 ist 0x08.
    Deshalb finde ich diesen Artikel ziemlich verwirrend.
    Vielleicht hat OCaml keine oktalen, sondern dezimale Escapes, und \09 ist womöglich ein Tab-Zeichen.
    Nachgeprüft habe ich es nicht.

    • In diese Richtung stimmt zwar einiges, aber mit Backslash-Escapes hat das nichts zu tun.
      Backslash-Escapes sind symbolisch bzw. als Merkhilfe gedacht: \n steht für „[Ne]wline“, \r für „carriage [R]eturn“, \t für „[T]ab“ und so weiter.
      Stattdessen sollte man sich die Konventionen für Steuerzeichen wie ^C (Interrupt), ^G (Bell) und ^M (Carriage Return) ansehen.
      Diese gehören zum C0-Steuerzeichensatz; ^C ist \0x3, ^G ist \0x7, ^M ist \0xD.
      Das ist ein cleveres Verfahren, das bis vor Unix zurückreicht: Um die unsichtbaren C0-Zeichen von ASCII darzustellen, setzten Terminals ein ^ davor und wendeten auf das betreffende Zeichen AND-0x40 an, um es in den sichtbaren Bereich zu verschieben und auszugeben.
      Zum Nachvollziehen lohnt es sich, eine ASCII-Tabelle wie https://www.asciitable.com zu öffnen.
      Jedes Steuerzeichen wird dort auf das ^Zeichen zwei Felder daneben abgebildet.
      Dadurch entstehen schwer zu merkende Äquivalenzen, etwa dass \0 seltsamerweise als ^@ dargestellt wird und die Esc-Taste zu ^[ wird.
      Das war keine Entscheidung der Unix-Autoren, sondern ein Produkt des ASCII-Nummerierungsschemas.
    • Tatsächlich verwendet OCaml dezimale Escapes: https://ocaml.org/manual/5.2/lex.html#char-literal
    • Backslash-dezimale Zeichen-Escapes sind wirklich selten.
      Unter den String-Syntaxen, die ich kenne, fallen mir nur OCaml, Lua und DNS ein.

  • Wegen der falschen Großschreibung dachte ich kurz, es gäbe eine andere, kaum bekannte Escape-Sequenz \N statt \n.
    Ich dachte, sie könnte auf ein beliebiges Zeichen außer einem Zeilenumbruch passen, aber nein: Es lag nur an der Darstellung in Kapitälchen im Originalartikel.

    • Wenn man den Quelltext ansieht, ist es tatsächlich \n; nur wegen dieser CSS-Regel wird es nicht so angezeigt:
      .title { font-variant: small-caps; }
    • Es gibt tatsächlich Stellen, an denen \N verwendet wird.
      Viele Systeme nutzen \N in CSV oder ähnlichen Formaten als NULL, um es von der leeren Zeichenkette zu unterscheiden.
      Deshalb dachte ich, darum ginge es in diesem Artikel.
    • In Python gibt es eine \N-Escape-Sequenz.
      Sie fügt ein Unicode-Zeichen anhand seines Namens ein.
      Zum Beispiel ist '\N{PILE OF POO}' ein Unicode-String mit einem einzelnen Kackhaufen-Emoji.
      Das ist viel selbsterklärender, als mit \u oder \U hexadezimale Sequenzen zu schreiben.
    • Deshalb habe auch ich auf den Artikel geklickt.
      Interessant zu lesen war er trotzdem.

  • Der „andere Artikel“, der diesen Beitrag inspiriert hat, ist vermutlich dieser hier
    https://research.swtch.com/nih