`'\n'` đến từ đâu?

(rodarmor.com)

1 điểm bởi GN⁺ 2024-10-07 | 1 bình luận | Chia sẻ qua WhatsApp

just foo xử lý "\n" trong justfile và ghi một byte duy nhất 0x0A vào tệp bar; bài viết lần theo từng bước xem giá trị này đến từ đâu
Trình phân tích cú pháp Rust của just được triển khai để khi gặp escape \n, nó đưa giá trị escape ký tự Rust '\n' vào chuỗi
rustc hiện cũng được viết bằng Rust, nên việc truy vết lại dẫn tiếp đến lexer của rustc; tuy vậy, có thể tìm được manh mối trực tiếp hơn trong bản triển khai bằng OCaml trước thời self-hosted
Phiên bản rustc OCaml ban đầu xử lý escape ký tự n bằng Char.code '\n', còn lexer của OCaml định nghĩa nó là '\010'
Vì 0x0A là 10, \n trong justfile là một giá trị được truyền qua nhiều thế hệ trình biên dịch Rust, và điểm xuất phát dẫn tới byte mà trình biên dịch OCaml đã đánh giá từ '\010' rồi đưa vào binary rustc ban đầu

Từ `\n` trong `justfile` đến `0x0A`

Khi chạy just foo, justfile sau sẽ ghi một byte duy nhất 0x0A vào tệp bar

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

just được viết bằng Rust, và hàm cook_string của parser chuyển đổi token chuỗi just có chứa các chuỗi escape thành chuỗi UTF-8
Khi sau dấu gạch chéo ngược là n, hàm này thực thi cooked.push('\n')

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

Ở bước này, just giao cho rustc việc đưa kết quả đánh giá escape ký tự Rust '\n' vào chuỗi

Lần ngược đường đi tới `rustc` và OCaml

Việc xử lý escape của rustc nằm trong hàm scan_escape của lexer; khi gặp n, nó lại xử lý thành escape ký tự Rust '\n'

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

rustc hiện được viết bằng Rust và tự biên dịch chính nó, nên quá trình tìm ý nghĩa của '\n' dẫn từ rustc quay lại rustc
Tuy nhiên, rustc không phải ngay từ đầu đã được viết bằng Rust; các phiên bản ban đầu trước khi self-hosted được viết bằng OCaml
Lexer của rustc phiên bản OCaml xử lý escape ký tự n như sau

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

Ở đây cũng dùng escape ký tự OCaml '\n', nhưng trong lexer của OCaml có một định nghĩa trực tiếp hơn

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

Khi trình biên dịch OCaml thấy \n, nó đưa vào kết quả đánh giá của escape ký tự thập phân '\010'; vì 0x0A là 10, giá trị này khớp với byte đang được tìm kiếm
Do đó, có thể xem \n trong justfile dẫn tới một dạng byte 0x0A nào đó bên trong binary just; byte đó do rustc đưa vào, và các đời rustc trước đó đã truyền cùng một giá trị qua nhiều thế hệ
rustc hiện là 1.81.0; chỉ tính từ sau rustc 1.0 thì quá trình này đã diễn ra ít nhất 81 lần, và nếu tính cả trước 1.0 thì có thể còn nhiều hơn
Điểm xuất phát của truy vết là lúc trình biên dịch OCaml đánh giá escape ký tự thập phân '\010' và đưa byte 0x0A vào binary rustc ban đầu

1 bình luận

GN⁺ 2024-10-07

Các ý kiến trên Hacker News

Nơi tôi đọc ý tưởng này lần đầu không phải là dạng trusting trust thông thường, mà là nội dung về ký tự xuống dòng; đó là ngày thứ 42 trong https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile...
Điều thú vị là để diễn giải "\n" trong string literal thành ký tự xuống dòng thật, mã nguồn không có thông tin mã ASCII đó; nó được truyền lại từ trình biên dịch trước đó đã dùng để biên dịch trình biên dịch này
Rốt cuộc, ký tự xuống dòng của trình biên dịch đó có thể truy ngược về tận GCC đã biên dịch ra nó
- Tôi đã kỳ vọng GCC cũng giao giá trị của '\n' cho chính trình biên dịch của nó theo kiểu như vậy, nhưng thực tế nó hard-code giá trị số của escape[1], và dường như chỉ có các lựa chọn cho hệ thống ASCII và EBCDIC
  [1] https://github.com/gcc-mirror/gcc/blob/8a4a967a77cb937a2df45...
Bài gốc mà tác giả nghĩ tới có vẻ rất có thể là bài giảng giải Turing của Ken Thompson, Reflections on Trusting Trust
- Bài nói đó cũng chỉ ra rằng kỹ thuật này được dùng rộng hơn trong quine
  Có khá nhiều nghiên cứu, bài báo và bài giải thích về quine, nên có thể tác giả đã đọc một bài theo hướng đó
  https://en.wikipedia.org/wiki/Quine_(computing)
- Bài viết web ngắn và xuất sắc này từ năm 2009 cũng đáng đọc
  https://www.teamten.com/lawrence/writings/coding-machines/
- Tôi nghĩ không phải vậy
  Vài năm trước tôi cũng nhớ đã thấy một bài kiến thức lặt vặt đúng y như thế về '\n' trong Rust, nhưng giờ không tìm được nguồn nữa
Thật thú vị là đã 10 giờ trôi qua mà chưa có nhánh thảo luận nào nhắc đến EBCDIC
Các trình biên dịch C thời kỳ đầu cũng tồn tại trên những hệ thống không phải ASCII, nơi \n không ánh xạ “line feed” thành số thập phân 10, nên mọi lý thuyết được bàn ở đây đều phải giải thích sự thật đó
https://en.wikipedia.org/wiki/EBCDIC
Hơn nữa, EBCDIC có cả ký tự NextLine và LineFeed rõ ràng
Trong ASCII, for (c = 'A'; c <= 'Z'; ++c) putchar(c); in từ A đến Z, nhưng trong EBCDIC có các khoảng trống giữa các chữ cái, nên nó sẽ in 41 ký tự, bao gồm cả các ký tự chưa được gán
Thứ tự sắp xếp của EBCDIC đặt chữ thường trước chữ hoa, và chữ cái trước chữ số, hoàn toàn ngược với ASCII
Điều duy nhất chuẩn C bảo đảm về mã hóa ký tự là các chữ số từ '0' đến '9' được ánh xạ liên tiếp theo thứ tự tăng dần
Về lý thuyết, một chương trình C đơn giản phải có thể được biên dịch từ cùng một mã nguồn và cho cùng đầu ra dù là ASCII hay EBCDIC, nhưng thực tế có rất nhiều bẫy
- Đúng là EBCDIC có ký tự xuống dòng/dòng tiếp theo NEL, nhưng trên nhiều hệ thống EBCDIC thì không thường gặp
  Các hệ thống EBCDIC thời kỳ đầu như MVS, VM/CMS, OS/400, DOS/VSE, v.v. lưu văn bản dưới dạng tệp hướng bản ghi thay vì tệp luồng byte; mỗi dòng là một bản ghi có độ dài cố định hoặc biến đổi
  Với bản ghi độ dài cố định, khi tạo tệp người ta khai báo độ dài bản ghi như 80 hoặc 132; các dòng ngắn thường được đệm bằng ký tự khoảng trắng EBCDIC 0x40, còn dòng dài thì bị cắt hoặc dùng ký tự nối dòng
  Bản ghi độ dài biến đổi có một record descriptor word (RDW) chứa độ dài ở phía trước, nhưng dạng này hiếm dùng cho tệp văn bản và mã nguồn; bản ghi độ dài cố định mới là phổ biến
  Vì vậy, dù NEL tồn tại, nó thường không được dùng trong tệp trên đĩa
  Các ký tự xuống dòng như NEL là tín hiệu trong băng biểu thị ranh giới dòng/bản ghi, còn hệ thống tệp hướng bản ghi lại biểu diễn ranh giới đó ở ngoài băng
  Tôi không biết chính xác stdio được triển khai thế nào trong thư viện runtime của trình biên dịch C trên EBCDIC, nhưng có lẽ nội bộ nó ánh xạ \n sang NEL, rồi tầng stdio xử lý ký tự đó như dấu phân tách bản ghi, ghi từng bản ghi bằng lệnh gọi hệ thống riêng và đệm nếu cần
  Về sau, hầu hết các hệ điều hành này có thêm các phân hệ tương thích POSIX, nên cũng có tệp luồng byte giống các hệ thống phổ biến
  Hệ thống IBM nói chung hỗ trợ gắn thẻ code page cho tệp, nhờ đó một tệp có thể trộn EBCDIC và ASCII, và hệ điều hành sẽ chuyển đổi ở tầng nhập/xuất
  Nhờ vậy, ứng dụng dùng EBCDIC ở runtime vẫn có thể đọc tệp ASCII như EBCDIC mà không cần gọi API chuyển đổi riêng hay chỉ định tường minh
  Các ứng dụng mới ngày càng dùng hệ thống tệp dựa trên POSIX nhiều hơn, nhưng ứng dụng cũ thường vẫn lưu cả dữ liệu, tệp văn bản lẫn mã nguồn trong hệ thống tệp hướng bản ghi cổ điển
  Theo tôi hiểu, nơi dễ gặp EBCDIC NEL nhất trong môi trường thực tế là kết nối terminal chế độ dòng của các terminal hardcopy như IBM 2741, IBM 3767
Đây là một bài viết thật sự thú vị
Với tôi, nó đọc như sự pha trộn giữa lập trình văn học và thơ
Bài viết muốn giải thích ý nghĩ rằng chính byte 0x0A xuất hiện khi chạy just foo có lẽ đã đi qua hàng trăm vòng sinh mã
Từ rất lâu trước đây, ai đó đã mã hóa thông tin này vào trình biên dịch OCaml bằng cách nào đó, và nhiều năm sau thông tin 0x0A trên máy tính của tôi được lưu giữ nhờ lịch sử ấy
Nhưng hiện tượng này lại được giải thích bằng mã thật
Tất nhiên bản thân đoạn mã đó không phải là điểm cốt lõi, và có lẽ cũng chẳng ai sẽ chạy hay biên dịch đoạn mã cụ thể này, nhưng đó là đoạn mã được đặt ra để con người có thể theo dõi lập luận
Tôi tò mò không biết clang có cùng đặc tính này không, và thấy trong lib/Lex/LiteralSupport.cpp nó được hard-code rõ ràng thành 10
ProcessCharEscape phân tích cú pháp các chuỗi escape chuẩn của C, rồi xử lý kiểu case 'n': ResultChar = 10; break;
- GCC cũng tương tự, được hard-code trong gcc/libcpp/charset.cc, và chọn một trong hai: ASCII hoặc EBCDIC
  Nó đưa các giá trị của \a \b \e \f \n \r \t \v vào mảng charconsts; nếu là ASCII thì dùng { 7, 8, 27, 12, 10, 13, 9, 11 }, nếu là EBCDIC thì dùng { 47, 22, 39, 12, 21, 13, 5, 11 }, rồi xử lý bằng case 'n': c = charconsts[4]; break;
Tôi nhớ một bài tương tự về một trình biên dịch C nào đó
Cuối cùng, nơi duy nhất xuất hiện giá trị 0x10 là trong binary của trình biên dịch; còn trong mã nguồn thì chỉ có dạng như "\\n" -> "\n"
Câu chuyện này vượt quá trình độ của tôi
Tôi không hiểu vì sao phải đi một hành trình dài như vậy chỉ để tìm ra tại sao \n được mã hóa thành byte có giá trị 10
Tôi thấy chuyện đó chẳng phải hiển nhiên sao, mà tác giả lẫn bình luận cũng không giải thích, nên tôi cảm thấy mình như kẻ ngốc
- Điểm cốt lõi là hỏi “ai” đã mã hóa byte đó thành giá trị 10
  Nếu khi viết parser, bạn phân tích newline thành chuỗi escape \n, thì giá trị 10 đến từ đâu?
  Nếu phân tích newline thành integer literal 10, thì giá trị nhị phân thực tế 1010 đến từ đâu?
  Mục đích sau cùng của thí nghiệm tư duy này là thay đổi cách ta nhìn về trình biên dịch, giống bài thuyết trình nổi tiếng Reflections On Trusting Trust
  Nghĩa là trình biên dịch không chỉ là thứ xuất ra chương trình, mà còn là đầu vào của chương trình
  Bản thân trình biên dịch cũng là một chương trình, nên trình biên dịch đã tạo ra trình biên dịch đó chính là đầu vào của trình biên dịch hiện tại, và theo tính bắc cầu, trở thành đầu vào của chương trình của tôi
  Và điều này tiếp tục kéo dài lên trình biên dịch của trình biên dịch của trình biên dịch, rồi các trình biên dịch phía trên nữa
- Điều thú vị là giá trị 10 không được định nghĩa trong mã nguồn Rust, mà được truyền miệng từ trình biên dịch này sang trình biên dịch khác
- Nếu phải build lại trình biên dịch Rust từ con số không mà chỉ có mã nguồn rustc, thì trong mã nguồn không có thông tin nào cho biết '\n' thực sự được ánh xạ tới cái gì
  Đây là một ví dụ thực tế thú vị của vụ hack Ken Thompson
- Cốt lõi là vì sao lại là 10
  Vì sao không phải 9 hay 11?
  Mã nói rằng “khi thấy chuỗi ký tự newline thì hãy xuất ký tự newline”
  Nhưng làm sao trình biên dịch biết ký tự newline là gì?
  Mã của trình biên dịch đó cũng chỉ nói lại rằng “khi thấy chuỗi ký tự newline thì hãy xử lý nó như ký tự newline”
  Con người có thể tìm “C string escape codes”, nhưng bảng đó không nằm ở đâu trong trình biên dịch
  Nếu C 2025 định nghĩa Start of Heading là \h, liệu 'h' => cooked.push('\h') có bắt đầu hoạt động một cách kỳ diệu không?
  Làm sao nó biết được?
  Rõ ràng ở một thời điểm nào đó đã có ai đó lập trình thủ công ánh xạ 'n' => 10; câu hỏi là vị trí đó ở đâu
Có lẽ vì C mà tôi luôn nghĩ \0??? là escape bát phân
Vì vậy trong đầu tôi, \012 là \x0a hoặc 0x0a, còn \010 là 0x08
Nên bài này khiến tôi khá bối rối
Có thể OCaml không có escape bát phân mà có escape thập phân, và \09 có khi lại là ký tự tab
Tôi chưa kiểm tra
- Hướng đó cũng có phần đúng, nhưng không liên quan đến backslash escape
  Backslash escape mang tính biểu tượng/gợi nhớ, nên \n là “[Ne]wline”, \r là “carriage [R]eturn”, \t là “[T]ab”, đại loại vậy
  Thay vào đó, hãy nhìn vào quy ước về ký tự điều khiển như ^C (interrupt), ^G (bell), ^M (carriage return)
  Chúng nằm trong tập ký tự điều khiển C0, và ^C là \0x3, ^G là \0x7, ^M là \0xD
  Đây là một cách thông minh có từ trước Unix: để biểu diễn các ký tự C0 vô hình của ASCII, terminal thêm ký tự ^ ở phía trước và áp dụng AND-0x40 lên ký tự tương ứng để chuyển nó sang vùng nhìn thấy được rồi in ra
  Nếu muốn theo dõi, bạn nên mở một bảng ASCII như https://www.asciitable.com
  Mỗi ký tự điều khiển được ánh xạ tới ^ký tự ở cách đó hai ô trong bảng
  Vì vậy mới có những biểu diễn tương đương khó nhớ như \0 được biểu diễn một cách kỳ lạ thành ^@, hay phím Esc thành ^[
  Đây không phải lựa chọn của các tác giả Unix, mà là sản phẩm của hệ thống đánh số ASCII
- Thực ra OCaml dùng escape thập phân: https://ocaml.org/manual/5.2/lex.html#char-literal
- Escape ký tự backslash-thập phân thật sự rất hiếm
  Trong các cú pháp chuỗi mà tôi biết, chỉ khoảng OCaml, Lua, DNS có kiểu này
Vì cách viết hoa sai, tôi đã tưởng có một chuỗi escape \N nào đó gần như không ai biết, khác với \n
Tôi còn tưởng nó dùng để khớp với bất kỳ ký tự nào không phải newline, nhưng hóa ra không phải; chỉ là do kiểu chữ hoa nhỏ trong bài gốc
- Nếu xem mã nguồn trang thì thực ra là \n, nhưng do quy tắc CSS này nên nó hiển thị khác đi
  .title { font-variant: small-caps; }
- Thực sự có nơi dùng \N
  Nhiều hệ thống dùng \N làm NULL trong CSV hoặc các định dạng tương tự để phân biệt với chuỗi rỗng
  Vì vậy tôi cũng tưởng bài này nói về chuyện đó
- Python có chuỗi escape \N
  Nó chèn ký tự Unicode theo tên
  Ví dụ '\N{PILE OF POO}' là một chuỗi Unicode gồm một emoji cục phân
  Nó tự mô tả hơn nhiều so với việc dùng chuỗi hệ 16 bằng \u hoặc \U
- Tôi cũng bấm vào bài này vì thế
  Dù sao đọc cũng thú vị
“Bài viết khác” đã truyền cảm hứng cho bài này có lẽ là bài này
https://research.swtch.com/nih
- Từng được thảo luận ở đây
  Running the "Reflections on Trusting Trust" Compiler - https://news.ycombinator.com/item?id=38020792 - tháng 10 năm 2023, 67 bình luận

`'\n'` đến từ đâu?

Từ \n trong justfile đến 0x0A

Lần ngược đường đi tới rustc và OCaml

Bài viết liên quan

1 bình luận

Các ý kiến trên Hacker News

Từ `\n` trong `justfile` đến `0x0A`

Lần ngược đường đi tới `rustc` và OCaml