`\n` มาจากไหน?

 (rodarmor.com)
1 คะแนน โดย GN⁺ 2024-10-07 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • just foo จะประมวลผล "\n" ใน justfile และเขียน ไบต์เดียว 0x0A ลงในไฟล์ bar โดยบทความนี้ไล่ตามทีละขั้นว่าค่านี้มาจากไหน
  • parser ของ just ที่เขียนด้วย Rust ถูกทำไว้ให้เมื่อเจอ escape \n จะใส่ค่าของ Rust character escape '\n' ลงในสตริง
  • ปัจจุบัน rustc ก็เขียนด้วย Rust เช่นกัน ทำให้การไล่ตามต้องย้อนต่อไปยัง lexer ของ rustc เอง แต่ใน implementation ภาษา OCaml ก่อนยุค self-hosted มีเบาะแสที่ตรงกว่าซ่อนอยู่
  • rustc เวอร์ชันแรก ๆ ที่เขียนด้วย OCaml จัดการ character escape n ด้วย Char.code '\n' และ OCaml lexer ก็นิยามสิ่งนี้เป็น '\010'
  • เนื่องจาก 0x0A คือ 10 ดังนั้น \n ใน justfile จึงเป็นค่าที่ถูกส่งต่อมาผ่านหลายรุ่นของคอมไพเลอร์ Rust และจุดเริ่มต้นย้อนกลับไปถึงไบต์ที่ OCaml compiler ประเมินจาก '\010' แล้วใส่ไว้ในไบนารี rustc รุ่นแรก

\n ใน justfile กลายเป็น 0x0A ได้อย่างไร

  • เมื่อรัน just foo justfile ต่อไปนี้จะเขียน ไบต์เดียว 0x0A ลงในไฟล์ bar
x := "\n"
foo:
printf '{{x}}' > bar
  • just เขียนด้วย Rust และฟังก์ชัน cook_string ใน parser จะเปลี่ยน string token ของ just ที่มี escape sequence ให้เป็นสตริง UTF-8
  • ถ้าหลัง backslash เป็น n ฟังก์ชันนี้จะรัน cooked.push('\n')
State::Backslash => {
    match c {
        'n' => cooked.push('\n'),
        …
    }
}
  • ในขั้นนี้ just ปล่อยให้ rustc เป็นผู้ประเมินผลของ Rust character escape '\n' แล้วใส่ค่านั้นลงในสตริง

เส้นทางที่ย้อนกลับไปถึง rustc และ OCaml

  • การจัดการ escape ของ rustc อยู่ในฟังก์ชัน scan_escape ของ lexer และเมื่อเจอ n ก็จะจัดการเป็น Rust character escape '\n' อีกครั้ง
let res: char = match chars.next().ok_or(EscapeError::LoneSlash)? {
    …
    'n' => '\n',
    …
};
  • ปัจจุบัน rustc เขียนด้วย Rust และคอมไพล์ตัวเอง ดังนั้นกระบวนการตามหาความหมายของ '\n' จึงวนกลับจาก rustc ไป rustc อีกที
  • อย่างไรก็ตาม rustc ไม่ได้เขียนด้วย Rust มาตั้งแต่แรก และเวอร์ชันเริ่มต้นก่อนยุค self-hosted นั้นเขียนด้วย OCaml
  • lexer ของ rustc เวอร์ชัน OCaml จัดการ character escape n แบบนี้
| 'n' { end_char (Char.code '\n') lexbuf }
  • ตรงนี้ก็ยังใช้ OCaml character escape '\n' แต่ใน OCaml lexer มีคำนิยามที่ตรงกว่าอยู่
let char_for_backslash = function
  'n' -> '\010'
  • เมื่อ OCaml compiler เจอ \n มันจะใส่ผลลัพธ์ที่ประเมินได้จาก decimal character escape '\010' และเพราะ 0x0A คือ 10 จึงตรงกับค่าไบต์ที่ตามหา
  • ดังนั้น \n ใน justfile จึงเชื่อมโยงไปถึงไบต์ 0x0A ในรูปแบบใดรูปแบบหนึ่งภายในไบนารี just และไบต์นั้นถูกใส่มาโดย rustc ซึ่ง rustc รุ่นก่อนหน้าก็ส่งต่อค่าเดียวกันนี้ข้ามรุ่นมาเรื่อย ๆ
  • ปัจจุบัน rustc อยู่ที่ 1.81.0 และถ้านับเฉพาะหลัง rustc 1.0 กระบวนการนี้ก็เกิดขึ้นอย่างน้อย 81 ครั้งแล้ว และถ้านับก่อน 1.0 ด้วยก็อาจมากกว่านั้น
  • จุดเริ่มต้นของการไล่ตามนี้คือจุดที่ OCaml compiler ประเมิน decimal character escape '\010' แล้วใส่ไบต์ 0x0A ลงในไบนารี rustc รุ่นแรก

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-10-07
ความคิดเห็นจาก Hacker News

  • ครั้งแรกที่ผมอ่านแนวคิดนี้ ไม่ใช่ในบริบทของ trusting trust แบบทั่วไป แต่เป็นเรื่องของ อักขระขึ้นบรรทัดใหม่ โดยอยู่ในวันที่ 42 ของ https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile...
    มันน่าสนใจตรงที่ หากจะตีความ "\n" ภายใน string literal ให้เป็นอักขระขึ้นบรรทัดใหม่จริง ๆ ในซอร์สโค้ดเองกลับไม่มีข้อมูลรหัส ASCII นั้นอยู่ แต่ถูกส่งต่อมาจากคอมไพเลอร์ก่อนหน้าที่ใช้คอมไพล์คอมไพเลอร์ตัวนั้น
    ท้ายที่สุด อักขระขึ้นบรรทัดใหม่ของคอมไพเลอร์นั้นอาจสาวย้อนกลับไปได้ถึง GCC ที่ใช้คอมไพล์มัน

    • ผมคาดว่า GCC เองก็คงปล่อยให้ค่าของ '\n' ขึ้นกับคอมไพเลอร์ที่ใช้คอมไพล์มันเหมือนกัน แต่ความจริงคือมันฮาร์ดโค้ดค่าตัวเลขของ escape ไว้[1] และดูเหมือนจะมีแค่ตัวเลือกสำหรับระบบ ASCII กับ EBCDIC
      [1] https://github.com/gcc-mirror/gcc/blob/8a4a967a77cb937a2df45...

  • ต้นฉบับที่ผู้เขียนนึกถึงน่าจะเป็นปาฐกถารางวัลทัวริงของ Ken Thompson เรื่อง Reflections on Trusting Trust

    • งานบรรยายชิ้นนั้นก็ชี้เช่นกันว่าเทคนิคนี้ถูกใช้ในบริบทที่ทั่วไปกว่านั้นอย่าง quine
      มีงานศึกษา บทความวิชาการ และคำอธิบายเกี่ยวกับ quine อยู่ค่อนข้างมาก ผู้เขียนอาจเคยอ่านอะไรในสายนี้มาก็ได้
      https://en.wikipedia.org/wiki/Quine_(computing)
    • บทความสั้นบนเว็บจากปี 2009 ชิ้นนี้ก็น่าอ่านมากเช่นกัน
      https://www.teamten.com/lawrence/writings/coding-machines/
    • ไม่น่าใช่อันนั้น
      ผมเองก็จำได้ลาง ๆ ว่าเมื่อหลายปีก่อนเคยเห็นเกร็ดความรู้แนวเดียวกันนี้ที่พูดถึง '\n' ใน Rust โดยตรง แต่ตอนนี้หาแหล่งที่มาไม่เจอแล้ว

  • น่าสนใจที่ผ่านไป 10 ชั่วโมงแล้วยังไม่มีเธรดไหนพูดถึง EBCDIC
    คอมไพเลอร์ C ยุคแรก ๆ ก็มีอยู่บนระบบที่ไม่ใช่ ASCII ซึ่งไม่ได้แมป \n ไปเป็น “line feed” ค่าเลขฐานสิบ 10 ดังนั้นทุกทฤษฎีที่คุยกันอยู่ตรงนี้ควรต้องอธิบายข้อเท็จจริงนั้นได้
    https://en.wikipedia.org/wiki/EBCDIC
    ยิ่งไปกว่านั้น EBCDIC ยังมีทั้งอักขระ NextLine และ LineFeed อย่างชัดเจน
    ใน ASCII, for (c = 'A'; c <= 'Z'; ++c) putchar(c); จะพิมพ์ A ถึง Z แต่ใน EBCDIC มีช่องว่างระหว่างตัวอักษร จึงจะพิมพ์ออกมาทั้งหมด 41 ตัว รวมอักขระที่ไม่ได้กำหนดไว้ด้วย
    ลำดับเรียงของ EBCDIC ก็ตรงข้ามกับ ASCII โดยตัวพิมพ์เล็กมาก่อนตัวพิมพ์ใหญ่ และตัวอักษรมาก่อนตัวเลข
    มาตรฐาน C รับประกันเกี่ยวกับการเข้ารหัสอักขระเพียงอย่างเดียวว่า '0' ถึง '9' จะถูกแมปแบบต่อเนื่องในลำดับเพิ่มขึ้น
    ในทางทฤษฎี โปรแกรม C ง่าย ๆ ควรถูกคอมไพล์จากซอร์สเดียวกันได้ทั้งบน ASCII และ EBCDIC แล้วให้ผลลัพธ์เหมือนกัน แต่ในทางปฏิบัติมีกับดักอยู่มาก

    • EBCDIC มีอักขระขึ้นบรรทัดใหม่/ขึ้นบรรทัดถัดไป NEL ก็จริง แต่ในหลายระบบ EBCDIC มันไม่ใช่สิ่งที่เจอกันบ่อย
      ระบบ EBCDIC ยุคแรก ๆ (MVS, VM/CMS, OS/400, DOS/VSE ฯลฯ) เก็บข้อความเป็น ไฟล์แบบระเบียน มากกว่าจะเป็นไฟล์แบบ byte stream โดยแต่ละบรรทัดคือระเบียนความยาวคงที่หรือแปรผัน
      ในระเบียนความยาวคงที่ จะประกาศความยาวระเบียนอย่าง 80 หรือ 132 ตอนสร้างไฟล์ และบรรทัดที่สั้นกว่าก็มักถูกเติมด้วยอักขระช่องว่าง EBCDIC 0x40 ส่วนบรรทัดที่ยาวเกินจะถูกตัดหรือใช้เครื่องหมายต่อบรรทัด
      ระเบียนความยาวแปรผันจะมี record descriptor word (RDW) นำหน้าเพื่อเก็บความยาว แต่พบไม่บ่อยในไฟล์ข้อความและซอร์สโค้ด โดยทั่วไปมักใช้ระเบียนความยาวคงที่
      เพราะแบบนี้ ต่อให้มี NEL อยู่ ก็มักไม่ถูกใช้ในไฟล์บนดิสก์
      อักขระขึ้นบรรทัดใหม่อย่าง NEL เป็น สัญญาณในแบนด์ สำหรับบอกขอบเขตบรรทัด/ระเบียน แต่ระบบไฟล์แบบระเบียนบอกขอบเขตนั้น นอกแบนด์ อยู่แล้ว
      ผมไม่แน่ใจว่า stdio ถูกอิมพลีเมนต์อย่างไรแน่ในไลบรารีรันไทม์ของคอมไพเลอร์ C บน EBCDIC แต่เดาว่าภายในมันคงแมป \n ไปเป็น NEL แล้วให้ชั้น stdio ปฏิบัติต่อมันเป็นตัวคั่นระเบียน เขียนแต่ละระเบียนด้วย system call แยกกัน และเติม padding หากจำเป็น
      ต่อมาระบบปฏิบัติการเหล่านี้ส่วนใหญ่ก็มีซับซิสเต็มที่เข้ากันได้กับ POSIX ทำให้มีไฟล์แบบ byte stream แบบเดียวกับระบบกระแสหลักด้วย
      ระบบของ IBM โดยทั่วไปยังรองรับการติดแท็ก code page ให้ไฟล์ ทำให้ไฟล์หนึ่งสามารถปะปน EBCDIC และ ASCII ได้ และระบบปฏิบัติการจะช่วยแปลงให้ที่ชั้น I/O
      ด้วยเหตุนี้ แอปพลิเคชันที่รันไทม์ใช้ EBCDIC ก็สามารถอ่านไฟล์ ASCII ได้เหมือนเป็น EBCDIC โดยไม่ต้องเรียก API แปลงแยกต่างหากหรือระบุอะไรอย่างชัดเจน
      แอปพลิเคชันใหม่ ๆ หันไปใช้ระบบไฟล์แบบ POSIX มากขึ้นเรื่อย ๆ แต่แอปพลิเคชันเก่ายังคงเก็บข้อมูล ไฟล์ข้อความ และแม้แต่ซอร์สโค้ดไว้ในระบบไฟล์แบบระเบียนดั้งเดิมอยู่บ่อยครั้ง
      จากที่ผมเข้าใจ สภาพแวดล้อมจริงที่พบ EBCDIC NEL บ่อยที่สุดน่าจะเป็น การเชื่อมต่อเทอร์มินัลแบบ line mode ของฮาร์ดคอปปี้เทอร์มินัลอย่าง IBM 2741 และ IBM 3767

  • เป็นบทความที่น่าสนใจมาก
    สำหรับผม มันเหมือนส่วนผสมระหว่าง literate programming กับบทกวี
    มันคือบทความที่พยายามอธิบายว่าตอนไปรัน just foo แล้วได้ไบต์ 0x0A ออกมานั้น ไบต์ตัวเดียวกันนี้อาจเดินทางผ่านวัฏจักรของการสร้างโค้ดมาหลายร้อยครั้งแล้ว
    เมื่อนานมาแล้ว มีใครบางคนเข้ารหัสข้อมูลนี้ไว้ในคอมไพเลอร์ OCaml ไม่ทางใดก็ทางหนึ่ง และหลายปีต่อมา ข้อมูล 0x0A บนคอมพิวเตอร์ของผมก็ยังถูกเก็บรักษาไว้เพราะประวัติศาสตร์นั้น
    แต่ปรากฏการณ์นี้ถูกอธิบายด้วยโค้ดจริง
    แน่นอนว่าโค้ดนั้นไม่ใช่ประเด็นหลักในตัวมันเอง และก็คงไม่มีใครจะไปรันหรือคอมไพล์โค้ดชิ้นนี้จริง ๆ แต่เป็นโค้ดที่วางไว้เพื่อช่วยให้คนตามการอภิปรายได้

  • สงสัยว่า clang มีคุณสมบัติแบบเดียวกันไหม ปรากฏว่าใน lib/Lex/LiteralSupport.cpp มีการ ฮาร์ดโค้ดเป็น 10 ไว้อย่างชัดเจน
    ProcessCharEscape จะพาร์สลำดับ escape มาตรฐานของ C และจัดการในลักษณะอย่าง case 'n': ResultChar = 10; break;

    • GCC ก็คล้ายกัน โดยฮาร์ดโค้ดไว้ใน gcc/libcpp/charset.cc และเลือกอย่างใดอย่างหนึ่งระหว่าง ASCII หรือ EBCDIC
      ใส่ค่าของ \a \b \e \f \n \r \t \v ลงในอาร์เรย์ charconsts โดยถ้าเป็น ASCII จะใช้ { 7, 8, 27, 12, 10, 13, 9, 11 } และถ้าเป็น EBCDIC จะใช้ { 47, 22, 39, 12, 21, 13, 5, 11 } จากนั้นจัดการด้วย case 'n': c = charconsts[4]; break;

  • จำได้ว่าเคยอ่านบทความคล้ายกันเกี่ยวกับ C compiler ตัวหนึ่ง
    สุดท้ายพบว่าที่เดียวที่ค่า 0x10 ปรากฏขึ้นคือในไบนารีของคอมไพเลอร์ และในซอร์สโค้ดมีเพียงรูปแบบอย่าง "\\n" -> "\n" เท่านั้น

  • เป็นเรื่องที่เกินระดับความเข้าใจของฉัน
    ไม่เข้าใจว่าทำไมการจะหาว่าทำไม \n ถึงถูกเข้ารหัสเป็นไบต์ที่มีค่า 10 ถึงต้องเดินทางยาวขนาดนี้
    มันดูเหมือนเป็นเรื่องที่ควรจะชัดเจนอยู่แล้ว และทั้งผู้เขียนกับคอมเมนต์ก็ไม่ได้อธิบาย เลยทำให้ฉันรู้สึกเหมือนตัวเองโง่

    • ประเด็นสำคัญคือถามว่า “ใคร” เป็นคนเข้ารหัสไบต์นั้นให้มีค่า 10
      ถ้าคุณเขียน parser แล้วพาร์สบรรทัดใหม่เป็นลำดับ escape \n ค่า 10 มาจากไหน
      ถ้าคุณพาร์สบรรทัดใหม่เป็น integer literal 10 ค่าไบนารีจริง 1010 มาจากไหน
      เป้าหมายสูงสุดของ thought experiment นี้คือการเปลี่ยนมุมมองที่มีต่อคอมไพเลอร์ แบบเดียวกับงานบรรยายชื่อดัง Reflections On Trusting Trust
      กล่าวคือ คอมไพเลอร์ไม่ได้เป็นแค่สิ่งที่สร้างโปรแกรมออกมาเท่านั้น แต่ยังเป็นอินพุตของโปรแกรมด้วย
      ตัวคอมไพเลอร์เองก็เป็นโปรแกรม ดังนั้นคอมไพเลอร์ที่ใช้สร้างมันจึงเป็นอินพุตของคอมไพเลอร์ปัจจุบัน และโดยการถ่ายทอดต่อก็กลายเป็นอินพุตของโปรแกรมของฉันด้วย
      และสิ่งนี้ก็ย้อนต่อไปได้เรื่อย ๆ ถึงคอมไพเลอร์ของคอมไพเลอร์ของคอมไพเลอร์ และชั้นที่อยู่เหนือขึ้นไป
    • จุดที่น่าสนใจคือค่า 10 ไม่ได้ถูกนิยามไว้ในซอร์สโค้ดของ Rust แต่ ถูกถ่ายทอดปากต่อปาก จากคอมไพเลอร์ตัวหนึ่งไปยังอีกตัวหนึ่ง
    • ถ้าต้อง build Rust compiler ขึ้นมาใหม่จากศูนย์ และคุณมีแค่ซอร์สโค้ดของ rustc ก็ไม่มีที่ไหนในซอร์สโค้ดที่บอกว่า '\n' ถูกแมปกับอะไรจริง ๆ
      เป็นตัวอย่างในโลกจริงที่น่าสนใจของการแฮ็กแบบ Ken Thompson
    • แก่นของคำถามคือทำไมต้องเป็น 10
      ทำไมไม่ใช่ 9 หรือ 11
      โค้ดพูดเพียงว่า “ถ้าเห็นสตริงอักขระขึ้นบรรทัดใหม่ ก็ให้แสดงอักขระขึ้นบรรทัดใหม่”
      แล้วคอมไพเลอร์รู้ได้อย่างไรว่าอักขระขึ้นบรรทัดใหม่คืออะไร
      โค้ดของคอมไพเลอร์ตัวนั้นเองก็พูดซ้ำแค่ว่า “ถ้าเห็นสตริงอักขระขึ้นบรรทัดใหม่ ก็ให้จัดการเป็นอักขระขึ้นบรรทัดใหม่”
      มนุษย์ค้นหา “C string escape codes” ก็ได้ แต่ตารางนั้นไม่มีอยู่ตรงไหนในคอมไพเลอร์เลย
      ถ้า C 2025 นิยาม Start of Heading เป็น \h แล้ว 'h' => cooked.push('\h') จะเริ่มทำงานได้อย่างอัศจรรย์เองหรือ
      แล้วจะรู้ได้อย่างไร
      ชัดเจนว่าในบางจุดต้องมีใครสักคนเขียนแมปปิง 'n' => 10 ลงไปด้วยมือ แต่คำถามคือมันอยู่ตรงไหน

  • อาจเพราะ C เลยทำให้ฉันคิดมาตลอดว่า \0??? คือ octal escape
    ดังนั้นในหัวฉัน \012 คือ \x0a หรือ 0x0a และ \010 คือ 0x08
    เลยรู้สึกว่าบทความนี้ค่อนข้างทำให้งง
    บางที OCaml อาจไม่ได้ใช้ octal escape แต่ใช้ decimal escape และ \09 อาจเป็นอักขระแท็บก็ได้
    แต่ฉันยังไม่ได้ไปตรวจดู

    • มองในทางนั้นก็พอมีส่วนถูกอยู่บ้าง แต่ไม่เกี่ยวกับ backslash escape
      backslash escape เป็นเชิงสัญลักษณ์/ช่วยจำ ดังนั้น \n คือ "[Ne]wline", \r คือ "carriage [R]eturn", \t คือ "[T]ab" อะไรทำนองนั้น
      สิ่งที่ควรมองแทนคือธรรมเนียมของ control characters อย่าง ^C (interrupt), ^G (bell), ^M (carriage return)
      พวกนี้อยู่ในชุดอักขระควบคุม C0 โดย ^C คือ \0x3, ^G คือ \0x7, ^M คือ \0xD
      เป็นวิธีชาญฉลาดที่ย้อนกลับไปได้ถึงก่อนยุคยูนิกซ์ โดยเทอร์มินัลจะแสดงอักขระ C0 ของ ASCII ที่มองไม่เห็นด้วยการเติม ^ ข้างหน้า แล้วนำตัวอักษรนั้นไป AND กับ 0x40 เพื่อย้ายให้มาอยู่ในช่วงที่มองเห็นได้ก่อนแสดงผล
      ถ้าอยากไล่ดูให้เข้าใจ ลองเปิดตาราง ASCII อย่าง https://www.asciitable.com
      อักขระควบคุมแต่ละตัวจะถูกแมปกับ ^ตัวอักษร ที่อยู่ห่างออกไปสองช่องในตารางนั้น
      จึงเกิดรูปแบบเทียบกันที่จำยาก เช่น \0 ถูกแสดงเป็น ^@ อย่างประหลาด และปุ่ม Esc กลายเป็น ^[
      นี่ไม่ใช่การตัดสินใจของผู้เขียนยูนิกซ์ แต่เป็น ผลลัพธ์ของระบบเลขของ ASCII
    • จริง ๆ แล้ว OCaml ใช้ decimal escape: https://ocaml.org/manual/5.2/lex.html#char-literal
    • escape อักขระแบบ backslash-เลขฐานสิบพบได้น้อยมาก
      ในไวยากรณ์สตริงที่ฉันรู้จักมีประมาณ OCaml, Lua, DNS เท่านั้น

  • เพราะการใช้ตัวพิมพ์ใหญ่ที่ผิด ฉันเลยนึกว่ามีลำดับ escape ที่ไม่ค่อยมีใครรู้จักอีกตัวคือ \N ซึ่งต่างจาก \n
    ตอนแรกคิดว่ามันอาจใช้จับคู่กับอักขระอะไรก็ได้ที่ไม่ใช่ newline แต่ไม่ใช่ ที่เห็นแบบนั้นเป็นเพราะการแสดง small caps ในบทความต้นฉบับ

    • ถ้าดู source จะเห็นว่าเป็น \n จริง ๆ แต่กฎ CSS นี้ทำให้มันแสดงออกมาแบบนั้น
      .title { font-variant: small-caps; }
    • ที่จริงมีบางที่ใช้ \N
      หลายระบบใช้ \N เป็น NULL ใน CSV หรือฟอร์แมตคล้ายกัน เพื่อแยกจากสตริงว่าง
      เพราะอย่างนั้นฉันเลยคิดว่าบทความนี้น่าจะพูดถึงเรื่องนั้น
    • Python มีลำดับ escape \N
      ใช้แทรกอักขระยูนิโค้ดด้วยชื่อ
      ตัวอย่างเช่น '\N{PILE OF POO}' คือสตริงยูนิโค้ดที่เป็นอีโมจิกองอึหนึ่งตัว
      มันอธิบายตัวเองได้มากกว่าการใช้ลำดับเลขฐานสิบหกอย่าง \u หรือ \U
    • ฉันเองก็เลยกดเข้ามาอ่านเพราะคิดแบบนั้น
      ถึงอย่างนั้นก็ยังอ่านสนุกดี

  • “บทความอื่น” ที่เป็นแรงบันดาลใจให้บทความนี้ น่าจะเป็นอันนี้
    https://research.swtch.com/nih

    • เคยมีการพูดคุยกันที่นี่
      Running the "Reflections on Trusting Trust" Compiler - https://news.ycombinator.com/item?id=38020792 - ตุลาคม 2023, ความคิดเห็น 67 รายการ