¿De dónde salió '\n'?

 (rodarmor.com)
1 puntos por GN⁺ 2024-10-07 | 1 comentarios | Compartir por WhatsApp
  • just foo procesa el "\n" del justfile y escribe un único byte 0x0A en el archivo bar; el artículo rastrea paso a paso de dónde salió ese valor
  • El parser de Rust de just está implementado de modo que, cuando encuentra el escape \n, inserta en la cadena el valor del escape de carácter de Rust '\n'
  • El rustc actual también está escrito en Rust, así que el rastro vuelve al lexer de rustc, pero se puede encontrar una pista más directa en la implementación en OCaml anterior a la etapa self-hosted
  • Las primeras versiones de rustc en OCaml procesaban el escape de carácter n como Char.code '\n', y el lexer de OCaml lo define como '\010'
  • Como 0x0A es 10, el \n del justfile es un valor transmitido a través de generaciones del compilador de Rust, y su punto de partida lleva al byte que el compilador de OCaml insertó en el binario inicial de rustc al evaluar '\010'

Cómo el \n de un justfile llega a convertirse en 0x0A

  • Al ejecutar just foo, el siguiente justfile escribe un único byte 0x0A en el archivo bar
x := "\n"
foo:
printf '{{x}}' > bar
  • just está escrito en Rust, y la función cook_string del parser convierte los tokens de cadena de just, incluidos los que tienen secuencias de escape, en cadenas UTF-8
  • Si después de una barra invertida viene n, esta función ejecuta cooked.push('\n')
State::Backslash => {
    match c {
        'n' => cooked.push('\n'),
        …
    }
}
  • En esta etapa, just le delega a rustc insertar en la cadena el resultado de evaluar el escape de carácter de Rust '\n'

El camino de regreso hasta rustc y OCaml

  • El manejo de escapes en rustc está en la función scan_escape del lexer y, cuando encuentra n, vuelve a procesarlo como el escape de carácter de Rust '\n'
let res: char = match chars.next().ok_or(EscapeError::LoneSlash)? {
    …
    'n' => '\n',
    …
};
  • El rustc actual está escrito en Rust y se compila a sí mismo, por lo que la búsqueda del significado de '\n' lleva de rustc de vuelta a rustc
  • Sin embargo, rustc no estuvo escrito en Rust desde el principio; las primeras versiones, antes de ser self-hosted, estaban escritas en OCaml
  • El lexer de la versión de rustc en OCaml procesaba el escape de carácter n así
| 'n' { end_char (Char.code '\n') lexbuf }
  • Aquí también se usa el escape de carácter de OCaml '\n', pero el lexer de OCaml tiene una definición más directa
let char_for_backslash = function
  'n' -> '\010'
  • Cuando el compilador de OCaml ve \n, inserta el resultado de evaluar el escape de carácter decimal '\010', y como 0x0A es 10, coincide con el valor de byte que se buscaba
  • Por lo tanto, el \n del justfile conduce a algún tipo de byte 0x0A dentro del binario de just; ese byte fue insertado por rustc, y puede verse como un flujo en el que las versiones anteriores de rustc transmitieron el mismo valor a lo largo de generaciones
  • El rustc actual es 1.81.0 y, si contamos solo desde rustc 1.0, este proceso ocurrió al menos 81 veces; si se incluyen las versiones anteriores a 1.0, probablemente ocurrió más veces
  • El punto de inicio del rastro es el momento en que el compilador de OCaml evaluó el escape de carácter decimal '\010' e insertó el byte 0x0A en el binario inicial de rustc

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-10-07
Opiniones de Hacker News

  • La primera vez que leí esta idea no fue en el contexto general de trusting trust, sino sobre el carácter de nueva línea, en el día 42 de https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile...
    Es interesante que, para interpretar "\n" dentro de un literal de cadena como un carácter de nueva línea real, el código fuente no contiene esa información de código ASCII, sino que esta se transmite desde el compilador anterior que compiló al compilador
    Al final, el carácter de nueva línea de ese compilador puede rastrearse hasta el GCC que lo compiló

  • Parece probable que el texto original que el autor tenía en mente fuera la conferencia del Premio Turing de Ken Thompson, Reflections on Trusting Trust

    • Esa charla también señala que esta técnica se usa de forma más general en los quines
      Hay bastantes estudios, artículos y explicaciones sobre quines, así que quizá el autor leyó algún texto de ese ámbito
      https://en.wikipedia.org/wiki/Quine_(computing)
    • También vale la pena leer este breve y excelente texto web de 2009
      https://www.teamten.com/lawrence/writings/coding-machines/
    • No creo que haya sido eso
      Yo también recuerdo haber visto hace unos años un texto de curiosidades exactamente igual sobre '\n' en Rust, pero ya no logro encontrar la fuente

  • Es interesante que hayan pasado 10 horas y todavía no haya ningún hilo que mencione EBCDIC
    Los primeros compiladores de C también existían en sistemas no ASCII que no mapeaban el “line feed” de \n al decimal 10, así que cualquier teoría que se maneje aquí tiene que explicar ese hecho
    https://en.wikipedia.org/wiki/EBCDIC
    Además, EBCDIC tenía tanto un carácter explícito NextLine como un carácter LineFeed
    En ASCII, for (c = 'A'; c <= 'Z'; ++c) putchar(c); imprime de la A a la Z, pero en EBCDIC hay huecos entre las letras, por lo que termina imprimiendo 41 caracteres, incluidos caracteres no asignados
    El ordenamiento de EBCDIC ponía las minúsculas antes que las mayúsculas, y las letras antes que los números, justo al revés que ASCII
    Lo único que el estándar C garantizaba sobre la codificación de caracteres era que los dígitos '0' a '9' se mapearan en orden ascendente y de forma consecutiva
    En teoría, un programa simple en C debía compilarse desde el mismo fuente y producir la misma salida tanto en ASCII como en EBCDIC, pero en la práctica había muchas trampas

    • Aunque en EBCDIC existe el carácter de nueva línea/siguiente línea NEL, en muchos sistemas EBCDIC no era algo que se encontrara con frecuencia
      Los primeros sistemas EBCDIC (MVS, VM/CMS, OS/400, DOS/VSE, etc.) almacenaban texto como archivos orientados a registros, en vez de como archivos de flujo de bytes, y cada línea era un registro de longitud fija o variable
      En los registros de longitud fija, al crear el archivo se declaraba una longitud de registro como 80 o 132; las líneas cortas normalmente se rellenaban con el carácter de espacio EBCDIC 0x40, y las líneas largas se truncaban o usaban un carácter de continuación
      Los registros de longitud variable llevaban al principio una palabra descriptora de registro (RDW) con la longitud, pero eran raros en archivos de texto y código fuente; lo común eran los registros de longitud fija
      Por eso, aunque NEL existiera, normalmente no se usaba en archivos en disco
      Un carácter de nueva línea como NEL es una señal dentro de banda que indica límites de línea/registro, mientras que un sistema de archivos orientado a registros expresa esos límites fuera de banda
      No sé exactamente cómo estaba implementado stdio en la biblioteca de runtime de un compilador C para EBCDIC, pero imagino que internamente mapeaba \n a NEL y luego la capa stdio lo trataba como separador de registros, escribiendo cada registro con una llamada al sistema aparte y aplicando padding si hacía falta
      Más adelante, la mayoría de estos sistemas operativos obtuvo subsistemas compatibles con POSIX y, con ellos, archivos de flujo de bytes como en los sistemas más comunes
      Los sistemas IBM suelen soportar la capacidad de etiquetar archivos con páginas de códigos, de modo que un archivo puede mezclar EBCDIC y ASCII y el sistema operativo realiza la conversión en la capa de entrada/salida
      Gracias a eso, incluso una aplicación que usa EBCDIC en runtime puede leer archivos ASCII como si fueran EBCDIC, sin llamadas aparte a una API de conversión ni especificaciones explícitas
      Las aplicaciones nuevas usan cada vez más sistemas de archivos basados en POSIX, pero muchas aplicaciones antiguas todavía guardan datos, archivos de texto e incluso código fuente en los sistemas de archivos clásicos orientados a registros
      Según entiendo, en entornos reales donde más se veía EBCDIC NEL era en conexiones de terminal en modo línea de terminales de copia impresa como IBM 2741 o IBM 3767

  • Es un texto realmente interesante
    A mí me suena como una mezcla de programación literaria y poesía
    Intenta explicar la idea de que ese mismo byte 0x0A que aparece al ejecutar just foo quizá haya pasado por cientos de ciclos de generación de código
    Hace mucho tiempo alguien codificó esta información de alguna manera en el compilador de OCaml, y años después la información de 0x0A en mi computadora está almacenada por esa historia
    Pero este fenómeno se explica con código real
    Claro que el código en sí no es lo central, y tampoco parece que alguien vaya a ejecutar o compilar este código específico, sino que es código puesto ahí para que una persona pueda seguir la discusión

  • Tenía curiosidad por saber si clang tiene la misma propiedad, y en lib/Lex/LiteralSupport.cpp está explícitamente hardcodeado como 10
    ProcessCharEscape parsea las secuencias de escape estándar de C y las maneja como case 'n': ResultChar = 10; break;

    • GCC también lo tiene hardcodeado de forma similar en gcc/libcpp/charset.cc, y elige entre ASCII o EBCDIC
      Coloca los valores de \a \b \e \f \n \r \t \v en el arreglo charconsts; si es ASCII usa { 7, 8, 27, 12, 10, 13, 9, 11 }, y si es EBCDIC usa { 47, 22, 39, 12, 21, 13, 5, 11 }, y luego lo procesa con case 'n': c = charconsts[4]; break;

  • Recuerdo un artículo similar sobre algún compilador de C
    Al final, el único lugar donde aparecía el valor 0x10 era en el binario del compilador, y se descubrió que en el código fuente solo estaba en formas como "\\n" -> "\n"

  • Esto supera mi nivel
    No entiendo por qué habría que hacer un viaje tan largo para averiguar por qué \n se codifica como un byte con valor 10
    Me parece algo obvio, y como ni el autor ni los comentarios lo explican, me siento como un tonto

    • El punto clave es preguntar “quién” codificó ese byte con el valor 10
      Si al escribir un parser parseas un salto de línea como la secuencia de escape \n, ¿de dónde salió el valor 10?
      Si parseas el salto de línea como el literal entero 10, ¿de dónde salió el valor binario real 1010?
      El objetivo último de este experimento mental es cambiar la percepción sobre los compiladores, como en la famosa presentación Reflections On Trusting Trust
      Es decir, un compilador no es simplemente algo que produce programas; también es entrada de programas
      Como el compilador en sí también es un programa, el compilador que creó a ese compilador fue entrada del compilador actual y, transitivamente, se vuelve entrada de mi programa
      Y eso continúa con el compilador del compilador del compilador, y con los compiladores por encima de él
    • Lo interesante es que el valor 10 no está definido dentro del código fuente de Rust, sino que se transmite como tradición oral de compilador en compilador
    • Si tuvieras que reconstruir el compilador de Rust desde cero y solo tuvieras el código fuente de rustc, no habría ninguna información en el código fuente que indique a qué se mapea realmente '\n'
      Es un caso real interesante del hack de Ken Thompson
    • El punto clave es por qué precisamente 10
      ¿Por qué no 9 u 11?
      El código dice: “si ves la cadena de carácter de salto de línea, emite el carácter de salto de línea”
      Pero ¿cómo sabe el compilador qué es un carácter de salto de línea?
      El código de ese compilador, de nuevo, solo dice: “si ves la cadena de carácter de salto de línea, trátala como un carácter de salto de línea”
      Una persona puede buscar “códigos de escape de cadenas de C”, pero esa tabla no está en ninguna parte dentro del compilador
      Si C 2025 definiera Start of Heading como \h, ¿'h' => cooked.push('\h') empezaría a funcionar mágicamente?
      ¿Cómo podría saberlo?
      Claramente, en algún momento alguien tuvo que programar manualmente el mapeo 'n' => 10; la pregunta es dónde está ese lugar

  • Por culpa de C, siempre pensé que \0??? era un escape octal
    Así que en mi cabeza \012 es \x0a o 0x0a, y \010 es 0x08
    Por eso este artículo me resulta bastante confuso
    Tal vez OCaml no tenga escapes octales sino escapes decimales, y quizá \09 sea el carácter de tabulación
    No lo comprobé

    • En esa dirección hay algo de razón, pero no tiene que ver con los escapes con barra invertida
      Los escapes con barra invertida son simbólicos/mnemotécnicos, así que \n es “[Ne]wline”, \r es “carriage [R]eturn”, \t es “[T]ab”, y así
      En cambio, conviene mirar la convención de caracteres de control como ^C (interrupción), ^G (campana), ^M (retorno de carro)
      Estos están en el conjunto de caracteres de control C0, y ^C es \0x3, ^G es \0x7, ^M es \0xD
      Es un método ingenioso que se remonta a antes de Unix: para representar los caracteres C0 invisibles de ASCII, las terminales anteponían el carácter ^ y aplicaban AND-0x40 al carácter correspondiente para moverlo al rango visible antes de imprimirlo
      Para seguirlo, conviene abrir una tabla ASCII como https://www.asciitable.com
      Cada carácter de control se mapea al ^carácter ubicado dos columnas a la derecha en esa tabla
      Por eso aparecen equivalencias difíciles de memorizar, como que \0 se represente extrañamente como ^@, o que la tecla Esc sea ^[
      Esto no fue una elección de los autores de Unix, sino producto de la numeración de ASCII
    • De hecho, OCaml usa escapes decimales: https://ocaml.org/manual/5.2/lex.html#char-literal
    • Los escapes de caracteres con barra invertida y decimal son realmente raros
      Entre las sintaxis de cadenas que conozco, solo se me ocurren OCaml, Lua y DNS

  • Por la capitalización incorrecta, pensé que quizá existía otra secuencia de escape casi desconocida, \N, distinta de \n
    Pensé que tal vez coincidía con cualquier carácter que no fuera un salto de línea, pero no: era por las versalitas del artículo original

    • Si ves el código fuente, en realidad es \n, pero no se muestra así por esta regla de CSS
      .title { font-variant: small-caps; }
    • De hecho, hay lugares donde se usa \N
      Muchos sistemas usan \N como NULL en CSV o formatos similares para distinguirlo de una cadena vacía
      Por eso pensé que este artículo trataba de eso
    • Python tiene una secuencia de escape \N
      Inserta un carácter Unicode por nombre
      Por ejemplo, '\N{PILE OF POO}' es una cadena Unicode con un solo emoji de popó
      Es mucho más autoexplicativo que usar una secuencia hexadecimal con \u o \U
    • Yo también hice clic en el artículo por eso
      Aun así, me pareció una lectura entretenida

  • El “otro artículo” que inspiró este texto probablemente sea este
    https://research.swtch.com/nih