De onde veio o `'\n'`?

 (rodarmor.com)
1 pontos por GN⁺ 2024-10-07 | 1 comentários | Compartilhar no WhatsApp
  • just foo processa "\n" no justfile e escreve no arquivo bar um único byte 0x0A; o texto rastreia passo a passo de onde veio esse valor
  • O parser em Rust do just foi implementado para, ao encontrar o escape \n, inserir na string o valor do escape de caractere em Rust '\n'
  • Como o rustc atual também é escrito em Rust, o rastreamento continua até o lexer do rustc, mas é possível encontrar uma pista mais direta na implementação em OCaml anterior ao self-hosting
  • As versões iniciais do rustc em OCaml tratavam o escape de caractere n como Char.code '\n', e o lexer de OCaml o define como '\010'
  • Como 0x0A é 10, o \n do justfile é um valor transmitido através de gerações do compilador Rust, e seu ponto de partida leva ao byte colocado no binário inicial do rustc quando o compilador OCaml avaliou '\010'

Como o \n no justfile vira 0x0A

  • Ao executar just foo, o justfile abaixo escreve no arquivo bar um único byte 0x0A
x := "\n"
foo:
printf '{{x}}' > bar
  • O just é escrito em Rust, e a função cook_string do parser converte tokens de string do just com sequências de escape em strings UTF-8
  • Quando há um n depois da barra invertida, essa função executa cooked.push('\n')
State::Backslash => {
    match c {
        'n' => cooked.push('\n'),
        …
    }
}
  • Nessa etapa, o just deixa para o rustc a tarefa de inserir na string o resultado da avaliação do escape de caractere em Rust '\n'

O caminho de volta até rustc e OCaml

  • O tratamento de escapes no rustc fica na função scan_escape do lexer, e ao encontrar n ele novamente o trata como o escape de caractere em Rust '\n'
let res: char = match chars.next().ok_or(EscapeError::LoneSlash)? {
    …
    'n' => '\n',
    …
};
  • Como o rustc atual é escrito em Rust e compila a si mesmo, o processo de descobrir o significado de '\n' continua de rustc para rustc novamente
  • Porém, o rustc nem sempre foi escrito em Rust; as versões iniciais anteriores ao self-hosting eram escritas em OCaml
  • No rustc em OCaml, o lexer tratava o escape de caractere n assim:
| 'n' { end_char (Char.code '\n') lexbuf }
  • Aqui também aparece o escape de caractere em OCaml '\n', mas o lexer de OCaml tem uma definição mais direta
let char_for_backslash = function
  'n' -> '\010'
  • Quando o compilador OCaml encontra \n, ele insere o resultado da avaliação do escape decimal de caractere '\010'; como 0x0A é 10, isso coincide com o valor do byte procurado
  • Portanto, o \n do justfile leva a alguma forma do byte 0x0A dentro do binário do just; esse byte foi colocado pelo rustc, e os rustc anteriores transmitiram o mesmo valor ao longo das gerações
  • O rustc atual é a versão 1.81.0 e, considerando apenas a partir do rustc 1.0, esse processo ocorreu pelo menos 81 vezes; incluindo antes da 1.0, é possível que tenha acontecido ainda mais
  • O ponto de partida do rastreamento é o momento em que o compilador OCaml avaliou o escape decimal de caractere '\010' e colocou o byte 0x0A no binário inicial do rustc

Leituras relacionadas

1 comentários

 
GN⁺ 2024-10-07
Opiniões no Hacker News

  • O primeiro lugar onde li essa ideia não foi no contexto geral de trusting trust, mas sobre caracteres de nova linha: foi no dia 42 de https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile...
    É interessante que, para interpretar "\n" dentro de um literal de string como um caractere real de nova linha, o código-fonte não contém a informação daquele código ASCII; ela é transmitida pelo compilador anterior que compilou o compilador
    No fim, o caractere de nova linha desse compilador pode ser rastreado até o GCC que o compilou

  • Parece possível que o texto original em que o autor estava pensando seja a palestra do prêmio Turing de Ken Thompson, Reflections on Trusting Trust

    • Essa apresentação também observa que essa técnica é usada de forma mais geral em quines
      Há bastante pesquisa, artigos e explicações sobre quines, então o autor pode ter lido algum texto nessa linha
      https://en.wikipedia.org/wiki/Quine_(computing)
    • Também vale a pena ler este texto curto e excelente de 2009 na web
      https://www.teamten.com/lawrence/writings/coding-machines/
    • Acho que não é isso
      Eu também me lembro de ter visto, alguns anos atrás, um texto exatamente com a mesma curiosidade sobre '\n' em Rust, mas agora não consigo encontrar a fonte

  • É interessante que, depois de 10 horas, ainda não haja nenhuma thread mencionando EBCDIC
    Compiladores C iniciais também existiam em sistemas não ASCII que não mapeavam o “line feed” de \n para o decimal 10, então todas as teorias discutidas aqui precisam explicar esse fato
    https://en.wikipedia.org/wiki/EBCDIC
    Além disso, o EBCDIC tinha tanto um caractere explícito NextLine quanto um caractere LineFeed
    Em ASCII, for (c = 'A'; c <= 'Z'; ++c) putchar(c); imprime de A a Z, mas em EBCDIC há lacunas entre as letras, então ele acaba imprimindo 41 caracteres, incluindo caracteres não atribuídos
    A ordenação do EBCDIC colocava minúsculas antes de maiúsculas, e letras antes de números, o oposto do ASCII
    A única garantia que o padrão C dava sobre codificação de caracteres era que os dígitos de '0' a '9' seriam mapeados em ordem crescente e consecutiva
    Em teoria, um programa C simples deveria ser compilado a partir do mesmo código-fonte e produzir a mesma saída tanto em ASCII quanto em EBCDIC, mas na prática havia muitas armadilhas

    • Embora exista em EBCDIC o caractere de nova linha/próxima linha NEL, ele não é encontrado com frequência em muitos sistemas EBCDIC
      Sistemas EBCDIC iniciais (MVS, VM/CMS, OS/400, DOS/VSE etc.) armazenavam texto como arquivos orientados a registros, em vez de arquivos de fluxo de bytes, e cada linha era um registro de comprimento fixo ou variável
      Em registros de comprimento fixo, ao criar o arquivo se declarava um tamanho de registro, como 80 ou 132; linhas curtas normalmente eram preenchidas com o caractere de espaço EBCDIC 0x40, enquanto linhas longas eram truncadas ou usavam um caractere de continuação
      Registros de comprimento variável traziam antes um Record Descriptor Word (RDW) contendo o tamanho, mas eram raros em arquivos de texto e código-fonte; registros de comprimento fixo eram o comum
      Por isso, mesmo existindo, o NEL normalmente não era usado em arquivos em disco
      Caracteres de nova linha como NEL são um sinal in-band que indica limites de linha/registro, enquanto sistemas de arquivos orientados a registros expressavam esses limites fora da banda
      Não sei exatamente como o stdio era implementado na biblioteca de runtime dos compiladores C para EBCDIC, mas imagino que internamente \n fosse mapeado para NEL e que a camada stdio o tratasse como separador de registros, escrevendo cada registro por uma chamada de sistema separada e aplicando padding quando necessário
      Mais tarde, a maioria desses sistemas operacionais ganhou subsistemas compatíveis com POSIX e passou a ter também arquivos de fluxo de bytes como os sistemas mainstream
      Sistemas IBM em geral oferecem suporte a tags de página de código nos arquivos, de modo que um arquivo pode misturar EBCDIC e ASCII, com o sistema operacional fazendo a conversão na camada de entrada/saída
      Graças a isso, mesmo aplicações que usam EBCDIC em runtime conseguem ler arquivos ASCII como se fossem EBCDIC, sem chamadas separadas a APIs de conversão nem especificação explícita
      Aplicações novas usam cada vez mais sistemas de arquivos baseados em POSIX, mas aplicações antigas muitas vezes ainda armazenam dados, arquivos de texto e até código-fonte nos sistemas de arquivos clássicos orientados a registros
      Pelo que entendo, o lugar onde era mais comum ver EBCDIC NEL em ambientes reais eram conexões de terminais em modo linha de terminais hardcopy como o IBM 2741 e o IBM 3767

  • É um texto realmente fascinante
    Para mim, ele soa como uma mistura de programação literária e poesia
    O texto tenta explicar a ideia de que aquele byte 0x0A que aparece ao executar just foo talvez tenha passado por centenas de ciclos de geração de código
    Há muito tempo, alguém codificou essa informação de alguma forma no compilador OCaml e, anos depois, a informação do 0x0A no meu computador está armazenada por causa dessa história
    Mas esse fenômeno é explicado por código real
    Claro que o código em si não é o ponto central, e provavelmente ninguém vai executar ou compilar esse código específico, mas ele está ali para que as pessoas consigam acompanhar a discussão

  • Fiquei curioso para saber se o clang também tem a mesma característica, e em lib/Lex/LiteralSupport.cpp isso está explicitamente hardcoded como 10
    ProcessCharEscape analisa as sequências de escape padrão de C e trata algo como case 'n': ResultChar = 10; break;

    • O GCC também faz algo parecido em gcc/libcpp/charset.cc, onde isso fica hardcoded e escolhe entre ASCII ou EBCDIC
      Ele coloca os valores de \a \b \e \f \n \r \t \v no array charconsts; se for ASCII, usa { 7, 8, 27, 12, 10, 13, 9, 11 }, e se for EBCDIC, usa { 47, 22, 39, 12, 21, 13, 5, 11 }, depois trata com case 'n': c = charconsts[4]; break;

  • Lembro de um texto parecido sobre algum compilador C
    No fim, descobriu-se que o único lugar onde o valor 0x10 aparecia era no binário do compilador; no código-fonte, ele só aparecia em formas como "\\n" -> "\n"

  • Isso está acima do meu nível
    Não entendo por que é preciso uma jornada tão longa para descobrir por que \n é codificado como um byte de valor 10
    Parece algo óbvio, e como nem o autor nem os comentários explicam, acabo me sentindo burro

    • O ponto central é perguntar “quem” codificou aquele byte como o valor 10
      Se, ao escrever um parser, você analisa uma quebra de linha como a sequência de escape \n, de onde veio o valor 10?
      Se você analisa a quebra de linha como o literal inteiro 10, de onde veio o valor binário real 1010?
      O objetivo final desse experimento mental é mudar a percepção sobre compiladores, como na famosa apresentação Reflections On Trusting Trust
      Ou seja, um compilador não é simplesmente algo que gera programas; ele também é uma entrada do programa
      Como o próprio compilador é um programa, o compilador que criou esse compilador foi uma entrada do compilador atual e, transitivamente, torna-se entrada do meu programa
      E isso continua para o compilador do compilador do compilador, e para os compiladores acima dele
    • O interessante é que o valor 10 não está definido dentro do código-fonte do Rust, mas é transmitido de compilador para compilador como tradição oral
    • Se você precisar reconstruir o compilador Rust do zero e tiver apenas o código-fonte do rustc, não há em lugar nenhum do código-fonte uma informação dizendo a que '\n' realmente é mapeado
      É um exemplo real interessante do hack de Ken Thompson
    • O ponto central é: por que exatamente 10?
      Por que não 9 ou 11?
      O código diz: “ao ver a string do caractere de nova linha, emita o caractere de nova linha”
      Mas como o compilador sabe o que é o caractere de nova linha?
      O código desse compilador, por sua vez, também só diz: “ao ver a string do caractere de nova linha, trate como o caractere de nova linha”
      Uma pessoa pode pesquisar “códigos de escape de strings em C”, mas essa tabela não está em lugar nenhum dentro do compilador
      Se o C 2025 definir Start of Heading como \h, será que 'h' => cooked.push('\h') vai começar a funcionar magicamente?
      Como, afinal, alguém poderia saber?
      Em algum momento, certamente alguém programou manualmente o mapeamento 'n' => 10; a pergunta é onde fica esse lugar

  • Talvez por causa do C, sempre pensei que \0??? fosse um escape octal
    Então, na minha cabeça, \012 é \x0a ou 0x0a, e \010 é 0x08
    Por isso este texto me deixou bastante confuso
    Talvez OCaml não tenha escapes octais, mas sim escapes decimais, e \09 talvez seja o caractere de tabulação
    Não verifiquei

    • Há algo de certo nessa direção, mas isso não tem relação com escapes de barra invertida
      Escapes de barra invertida são simbólicos/mnemônicos: \n é “[Ne]wline”, \r é “carriage [R]eturn”, \t é “[T]ab”, e assim por diante
      Em vez disso, vale olhar para a convenção de caracteres de controle como ^C (interrupção), ^G (bell), ^M (carriage return)
      Eles ficam no conjunto de caracteres de controle C0, e ^C é \0x3, ^G é \0x7, ^M é \0xD
      De uma forma engenhosa que remonta a antes do Unix, os terminais representavam os caracteres C0 invisíveis do ASCII prefixando-os com o caractere ^ e aplicando AND-0x40 ao caractere correspondente para movê-lo para uma faixa visível antes de imprimi-lo
      Para acompanhar, é bom abrir uma tabela ASCII como https://www.asciitable.com
      Cada caractere de controle é mapeado para o ^caractere duas casas ao lado nessa tabela
      Por isso surgem equivalências difíceis de memorizar, como \0 sendo estranhamente representado por ^@, e a tecla Esc virando ^[
      Isso não foi uma escolha dos autores do Unix, mas um produto do sistema de numeração do ASCII
    • De fato, OCaml usa escapes decimais: https://ocaml.org/manual/5.2/lex.html#char-literal
    • Escapes de caracteres com barra invertida e decimal são realmente raros
      Entre as sintaxes de string que conheço, acho que só OCaml, Lua e DNS têm isso

  • Por causa da capitalização errada, achei que talvez existisse uma sequência de escape quase desconhecida \N, diferente de \n
    Pensei que fosse algo que combinasse com qualquer caractere exceto quebra de linha, mas não; era por causa das letras maiúsculas pequenas no texto original

    • Ao ver o código-fonte da página, é de fato \n, mas não aparece assim por causa desta regra CSS
      .title { font-variant: small-caps; }
    • Existem, de fato, lugares que usam \N
      Muitos sistemas usam \N como NULL em CSV ou formatos parecidos, para diferenciá-lo de uma string vazia
      Por isso achei que este texto fosse sobre isso
    • Python tem uma sequência de escape \N
      Ela insere um caractere Unicode pelo nome
      Por exemplo, '\N{PILE OF POO}' é uma string Unicode com um único emoji de cocô
      É muito mais autoexplicativo do que usar uma sequência hexadecimal com \u ou \U
    • Também foi por isso que cliquei neste texto
      Ainda assim, foi uma leitura divertida

  • O “outro texto” que inspirou este artigo provavelmente é este
    https://research.swtch.com/nih