Dari mana asal '\n'?

(rodarmor.com)

1 poin oleh GN⁺ 2024-10-07 | 1 komentar | Bagikan ke WhatsApp

just foo memproses "\n" dalam justfile dan menulis satu byte 0x0A ke file bar; tulisan ini melacak langkah demi langkah dari mana nilai tersebut berasal
Parser Rust milik just diimplementasikan agar, ketika menemukan escape \n, ia memasukkan nilai escape karakter Rust '\n' ke dalam string
Karena rustc saat ini juga ditulis dalam Rust, pelacakan berlanjut lagi ke lexer rustc, tetapi petunjuk yang lebih langsung dapat ditemukan pada implementasi OCaml sebelum self-hosted
Versi awal rustc berbasis OCaml menangani escape karakter n sebagai Char.code '\n', dan lexer OCaml mendefinisikannya sebagai '\010'
Karena 0x0A adalah 10, \n dalam justfile adalah nilai yang diteruskan melalui generasi compiler Rust, dan titik awalnya mengarah ke byte yang dimasukkan ke binary rustc awal ketika compiler OCaml mengevaluasi '\010'

Hingga `\n` dalam `justfile` menjadi `0x0A`

Saat menjalankan just foo, justfile berikut menulis satu byte 0x0A ke file bar

x := "\n"
foo:
printf '{{x}}' > bar

just ditulis dalam Rust, dan fungsi cook_string pada parser mengubah token string just yang berisi escape sequence menjadi string UTF-8
Jika setelah backslash muncul n, fungsi ini menjalankan cooked.push('\n')

State::Backslash => {
    match c {
        'n' => cooked.push('\n'),
        …
    }
}

Pada tahap ini, just menyerahkan kepada rustc untuk memasukkan hasil evaluasi escape karakter Rust '\n' ke dalam string

Jalur penelusuran mundur hingga `rustc` dan OCaml

Penanganan escape di rustc berada pada fungsi scan_escape di lexer; ketika menemukan n, ia kembali menanganinya sebagai escape karakter Rust '\n'

let res: char = match chars.next().ok_or(EscapeError::LoneSlash)? {
    …
    'n' => '\n',
    …
};

Saat ini rustc ditulis dalam Rust dan mengompilasi dirinya sendiri, sehingga proses mencari makna '\n' berlanjut dari rustc kembali ke rustc
Namun, rustc tidak sejak awal ditulis dalam Rust; versi-versi awal sebelum self-hosted ditulis dalam OCaml
Lexer rustc versi OCaml menangani escape karakter n seperti berikut

| 'n' { end_char (Char.code '\n') lexbuf }

Di sini pun escape karakter OCaml '\n' digunakan, tetapi lexer OCaml memiliki definisi yang lebih langsung

let char_for_backslash = function
  'n' -> '\010'

Ketika compiler OCaml melihat \n, ia memasukkan hasil evaluasi escape karakter desimal '\010', dan karena 0x0A adalah 10, nilainya cocok dengan byte yang dicari
Jadi \n dalam justfile mengarah ke byte 0x0A dalam suatu bentuk di dalam binary just; byte itu dimasukkan oleh rustc, dan dapat dilihat sebagai alur ketika rustc-rustc sebelumnya meneruskan nilai yang sama dari generasi ke generasi
rustc saat ini adalah 1.81.0, dan jika hanya melihat sejak rustc 1.0 pun, proses ini telah terjadi setidaknya 81 kali; jika mencakup masa sebelum 1.0, kemungkinannya lebih banyak lagi
Titik awal pelacakan adalah saat compiler OCaml mengevaluasi escape karakter desimal '\010' dan memasukkan byte 0x0A ke binary rustc awal

1 komentar

GN⁺ 2024-10-07

Opini Hacker News

Tempat pertama saya membaca ide ini bukan tentang trusting trust yang umum, melainkan tentang karakter newline, yaitu hari ke-42 di https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile...
Menarik bahwa agar "\n" di dalam literal string ditafsirkan sebagai karakter newline sungguhan, kode sumbernya sendiri tidak memuat informasi kode ASCII itu; informasinya diwariskan dari compiler sebelumnya yang mengompilasi compiler tersebut
Pada akhirnya, karakter newline compiler itu bisa ditelusuri mundur sampai ke GCC yang mengompilasinya
- Saya berharap GCC juga menyerahkan nilai '\n' kepada compilernya sendiri, tetapi ternyata GCC melakukan hardcode nilai numerik untuk escape tersebut[1], dan tampaknya hanya menyediakan pilihan untuk sistem ASCII dan EBCDIC
  [1] https://github.com/gcc-mirror/gcc/blob/8a4a967a77cb937a2df45...
Teks asli yang teringat oleh penulis kemungkinan adalah ceramah Turing Award Ken Thompson, Reflections on Trusting Trust
- Presentasi itu juga menyinggung bahwa teknik ini digunakan secara lebih umum dalam quine
  Ada cukup banyak riset, makalah, dan penjelasan tentang quine, jadi bisa saja penulis membaca tulisan dari ranah itu
  https://en.wikipedia.org/wiki/Quine_(computing)
- Tulisan web singkat dan bagus dari 2009 ini juga layak dibaca
  https://www.teamten.com/lawrence/writings/coding-machines/
- Sepertinya bukan itu
  Saya juga ingat pernah melihat tulisan trivia yang persis sama tentang '\n' di Rust beberapa tahun lalu, tetapi sekarang tidak bisa menemukan sumbernya
Menarik bahwa setelah 10 jam belum ada thread yang menyebut EBCDIC
Compiler C awal juga ada di sistem non-ASCII yang tidak memetakan “line feed” \n ke angka desimal 10, jadi semua teori yang dibahas di sini harus menjelaskan fakta itu
https://en.wikipedia.org/wiki/EBCDIC
Selain itu, EBCDIC memiliki karakter NextLine dan LineFeed yang eksplisit
Di ASCII, for (c = 'A'; c <= 'Z'; ++c) putchar(c); mencetak A sampai Z, tetapi di EBCDIC ada celah kosong di antara karakter, sehingga akan mencetak 41 karakter termasuk karakter yang tidak dialokasikan
Urutan kolasi EBCDIC menempatkan huruf kecil sebelum huruf besar, dan huruf sebelum angka, kebalikan dari ASCII
Satu-satunya jaminan standar C tentang encoding karakter adalah bahwa angka '0' sampai '9' dipetakan berurutan naik
Secara teori, program C sederhana seharusnya bisa dikompilasi dari sumber yang sama dan menghasilkan output yang sama, baik di ASCII maupun EBCDIC, tetapi dalam praktiknya ada banyak jebakan
- EBCDIC memang memiliki karakter newline/baris berikutnya NEL, tetapi di banyak sistem EBCDIC karakter itu tidak sering ditemui
  Sistem EBCDIC awal (MVS, VM/CMS, OS/400, DOS/VSE, dan lainnya) menyimpan teks sebagai file berorientasi record, bukan sebagai file byte stream, dan setiap baris adalah record dengan panjang tetap atau panjang variabel
  Pada record panjang tetap, panjang record seperti 80 atau 132 dideklarasikan saat file dibuat; baris pendek biasanya dipenuhi dengan karakter spasi EBCDIC 0x40, sedangkan baris panjang dipotong atau memakai karakter kelanjutan
  Record panjang variabel diawali dengan record descriptor word (RDW) yang memuat panjangnya, tetapi ini jarang dipakai untuk file teks dan kode sumber; record panjang tetaplah yang umum
  Karena itu, meskipun NEL ada, biasanya tidak digunakan di file disk
  Karakter newline seperti NEL adalah sinyal in-band yang menunjukkan batas baris/record, sedangkan sistem file berorientasi record merepresentasikan batas itu secara out-of-band
  Saya tidak tahu persis bagaimana stdio diimplementasikan dalam runtime library compiler C EBCDIC, tetapi sepertinya secara internal \n dipetakan ke NEL, lalu layer stdio memperlakukannya sebagai pemisah record, menulis tiap record sebagai system call terpisah dan melakukan padding bila perlu
  Belakangan, sebagian besar sistem operasi seperti ini memperoleh subsistem yang kompatibel POSIX, sehingga juga memiliki file byte stream seperti sistem arus utama
  Sistem IBM umumnya mendukung fitur pemberian tag code page pada file, sehingga file bisa berisi campuran EBCDIC dan ASCII, dan sistem operasi melakukan konversi di layer input/output
  Dengan begitu, aplikasi yang memakai EBCDIC saat runtime pun dapat membaca file ASCII seolah-olah EBCDIC tanpa panggilan API konversi khusus atau penentuan eksplisit
  Aplikasi baru semakin banyak memakai sistem file berbasis POSIX, tetapi aplikasi lama masih sering menyimpan data, file teks, bahkan kode sumber di sistem file berorientasi record klasik
  Sejauh yang saya pahami, tempat paling sering melihat EBCDIC NEL di lingkungan nyata adalah koneksi terminal mode baris pada terminal hardcopy seperti IBM 2741 dan IBM 3767
Tulisan yang benar-benar menarik
Bagi saya, ini terbaca seperti perpaduan literate programming dan puisi
Tulisan ini mencoba menjelaskan gagasan bahwa byte 0x0A yang muncul saat menjalankan just foo mungkin telah melewati ratusan siklus pembuatan kode
Dahulu sekali, seseorang mengodekan informasi ini ke compiler OCaml dengan suatu cara, dan bertahun-tahun kemudian informasi 0x0A di komputer saya tersimpan karena sejarah itu
Namun fenomena ini dijelaskan dengan kode sungguhan
Tentu saja kode itu sendiri bukan poin utamanya, dan tampaknya tidak ada orang yang benar-benar akan menjalankan atau mengompilasi kode spesifik ini; kode itu ditempatkan agar manusia bisa mengikuti pembahasannya
Saya penasaran apakah clang juga punya sifat yang sama, dan ternyata di lib/Lex/LiteralSupport.cpp nilainya secara eksplisit di-hard-code sebagai 10
ProcessCharEscape mem-parsing escape sequence C standar, lalu menanganinya seperti case 'n': ResultChar = 10; break;
- GCC juga mirip: di gcc/libcpp/charset.cc nilainya di-hard-code, dan memilih salah satu dari ASCII atau EBCDIC
  Nilai untuk \a \b \e \f \n \r \t \v dimasukkan ke array charconsts; jika ASCII memakai { 7, 8, 27, 12, 10, 13, 9, 11 }, jika EBCDIC memakai { 47, 22, 39, 12, 21, 13, 5, 11 }, lalu ditangani dengan case 'n': c = charconsts[4]; break;
Saya ingat pernah membaca tulisan serupa tentang suatu compiler C
Pada akhirnya terungkap bahwa satu-satunya tempat munculnya nilai 0x10 adalah binary compiler, sedangkan di source code hanya ada dalam bentuk seperti "\\n" -> "\n"
Ini sudah di luar level saya
Saya tidak paham kenapa harus menempuh perjalanan sepanjang ini untuk mencari tahu mengapa \n dienkode menjadi byte bernilai 10
Rasanya itu sudah semestinya, dan karena penulis maupun komentarnya tidak menjelaskan, saya jadi merasa bodoh
- Intinya adalah menanyakan “siapa” yang mengenkode byte itu sebagai nilai 10
  Jika saat menulis parser Anda mem-parsing newline sebagai escape sequence \n, dari mana nilai 10 berasal?
  Jika Anda mem-parsing newline sebagai literal integer 10, dari mana nilai biner sebenarnya 1010 berasal?
  Tujuan akhir eksperimen pikiran ini adalah mengubah cara kita memandang compiler, seperti presentasi terkenal Reflections On Trusting Trust
  Dengan kata lain, compiler bukan sekadar sesuatu yang menghasilkan program, melainkan juga input bagi program
  Karena compiler itu sendiri juga program, compiler yang membuat compiler tersebut adalah input bagi compiler saat ini, dan secara transitif menjadi input bagi program saya
  Dan ini terus berlanjut ke compiler dari compiler dari compiler, dan compiler di atasnya lagi
- Hal yang menarik adalah nilai 10 tidak didefinisikan di dalam source code Rust, melainkan diturunkan secara lisan dari compiler ke compiler
- Jika harus membangun ulang compiler Rust dari nol dan yang Anda punya hanya source code rustc, tidak ada informasi di mana pun dalam source code yang memberi tahu sebenarnya '\n' dipetakan ke apa
  Ini contoh nyata yang menarik dari peretasan Ken Thompson
- Intinya adalah kenapa harus 10
  Kenapa bukan 9 atau 11?
  Kode mengatakan “jika melihat string karakter newline, keluarkan karakter newline”
  Tapi bagaimana compiler tahu apa itu karakter newline?
  Kode compiler itu sendiri pun hanya mengatakan lagi “jika melihat string karakter newline, perlakukan sebagai karakter newline”
  Manusia bisa mencari “C string escape code”, tetapi tabel itu tidak ada di mana pun di dalam compiler
  Jika C 2025 mendefinisikan Start of Heading sebagai \h, apakah 'h' => cooked.push('\h') akan mulai bekerja secara ajaib?
  Bagaimana mungkin kita bisa tahu?
  Jelas pada suatu titik seseorang pasti memprogram secara manual pemetaan 'n' => 10; pertanyaannya, di mana lokasi itu?
Mungkin karena C, saya selalu menganggap \0??? sebagai escape oktal
Jadi di kepala saya \012 adalah \x0a atau 0x0a, dan \010 adalah 0x08
Karena itu tulisan ini cukup membingungkan
Mungkin OCaml punya escape desimal, bukan escape oktal, dan \09 mungkin adalah karakter tab
Saya belum mengeceknya
- Arah pemikiran itu ada benarnya juga, tetapi tidak berkaitan dengan backslash escape
  Backslash escape bersifat simbolis/mnemonik, jadi \n adalah “[Ne]wline”, \r adalah “carriage [R]eturn”, \t adalah “[T]ab”, dan seterusnya
  Sebagai gantinya, lihat konvensi karakter kontrol seperti ^C (interrupt), ^G (bell), ^M (carriage return)
  Semuanya ada dalam set karakter kontrol C0, dan ^C adalah \0x3, ^G adalah \0x7, ^M adalah \0xD
  Ini cara cerdik yang berasal dari masa sebelum Unix: untuk merepresentasikan karakter C0 ASCII yang tak terlihat, terminal menambahkan karakter ^ di depannya dan menerapkan AND-0x40 pada karakter terkait untuk memindahkannya ke rentang yang terlihat lalu menampilkannya
  Untuk mengikutinya, sebaiknya buka tabel ASCII seperti https://www.asciitable.com
  Setiap karakter kontrol dipetakan ke ^karakter dua kolom di sebelahnya dalam tabel itu
  Karena itu muncul padanan yang sulit dihafal, seperti \0 yang secara aneh direpresentasikan sebagai ^@, dan tombol Esc menjadi ^[
  Ini bukan pilihan para penulis Unix, melainkan hasil dari sistem penomoran ASCII
- Memang OCaml menggunakan escape desimal: https://ocaml.org/manual/5.2/lex.html#char-literal
- Escape karakter backslash-desimal benar-benar jarang
  Dari sintaks string yang saya tahu, kira-kira hanya OCaml, Lua, DNS yang memilikinya
Karena kapitalisasi yang keliru, saya sempat mengira ada escape sequence \N lain yang hampir tidak dikenal dan berbeda dari \n
Saya kira itu mungkin mencocokkan karakter apa pun selain newline, tetapi ternyata bukan; itu karena tampilan small caps di artikel aslinya
- Jika melihat source-nya, sebenarnya itu \n, tetapi aturan CSS ini membuatnya tidak tampil begitu
  .title { font-variant: small-caps; }
- Memang ada tempat yang menggunakan \N
  Banyak sistem memakai \N sebagai NULL dalam CSV atau format serupa untuk membedakannya dari string kosong
  Jadi saya sempat mengira artikel ini membahas hal itu
- Python punya escape sequence \N
  Itu menyisipkan karakter Unicode berdasarkan nama
  Misalnya '\N{PILE OF POO}' adalah string Unicode berisi satu emoji kotoran
  Ini jauh lebih menjelaskan diri sendiri daripada menulis sequence heksadesimal dengan \u atau \U
- Saya juga mengeklik tulisan ini karena itu
  Tetap saja, bacaan yang menarik
“Tulisan lain” yang menginspirasi artikel ini mungkin adalah yang ini
https://research.swtch.com/nih
- Pernah dibahas di sini
  Running the "Reflections on Trusting Trust" Compiler - https://news.ycombinator.com/item?id=38020792 - Oktober 2023, 67 komentar

Dari mana asal '\n'?

Hingga \n dalam justfile menjadi 0x0A

Jalur penelusuran mundur hingga rustc dan OCaml

Bacaan terkait

1 komentar

Opini Hacker News

Hingga `\n` dalam `justfile` menjadi `0x0A`

Jalur penelusuran mundur hingga `rustc` dan OCaml