เปลี่ยนส่วนภายในของเอนจิน regex ให้เป็นไลบรารี

 (blog.burntsushi.net)
1 คะแนน โดย GN⁺ 2023-07-06 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Rust crate regex เปิดเผยส่วนสำคัญของเอนจินภายในเป็น API ของ crate regex-automata ที่แยกเวอร์ชัน หลังจากเขียนใหม่มาหลายปี และการย้ายเสร็จสมบูรณ์ใน regex 1.9
  • การเขียนใหม่นี้เริ่มจากปัญหา ความยากในการผสมผสาน กลยุทธ์การค้นหา ความยากในการทดสอบเอนจินภายในแต่ละตัว ความต้องการ API แบบหลายแพตเทิร์นที่ละเอียดกว่า RegexSet และความจำเป็นต้องแชร์ DFA ที่คอมไพล์สมบูรณ์
  • regex-automata จัดโครงสร้างการประมวลผล regex เป็นโฟลว์ Ast → Hir → การดึง literal/Prefilter → Thompson NFA → PikeVM·BoundedBacktracker·one-pass DFA·DFA·lazy DFA → meta engine
  • ประสิทธิภาพได้มาจากการใช้ การค้นหา literal และเอนจินตระกูล DFA ก่อนเท่าที่ทำได้ แล้วเสริมด้วย PikeVM, bounded backtracker และ one-pass DFA ในกรณีที่มี capture group หรือกรณียกเว้น
  • API สาธารณะและ abstraction ที่นำกลับมาใช้ได้ทำให้การทดสอบและการทดลองง่ายขึ้น แต่ทำให้จำนวนโค้ด ขนาดไบนารี และเวลา compile เพิ่มขึ้น โดย DFA ที่คอมไพล์สมบูรณ์ถูกกำหนดให้เป็น opt-in และมี regex-lite เพิ่มเข้ามาเป็นทางเลือกแบบเบา

การเขียน regex ใหม่และการเปิดเผย regex-automata

  • regex crate ของ Rust ถูกเขียนใหม่เป็นเวลาหลายปี เพื่อปรับปรุงการประกอบภายใน เพิ่ม optimization ได้ง่ายขึ้น และยังคงความถูกต้องไว้
  • ในกระบวนการนี้มีการสร้าง regex-automata ขึ้น และเปิดเผยส่วนสำคัญของ implementation ภายใน regex crate ออกมาเป็น API แยกต่างหาก
  • regex-automata ถูกแนะนำว่าเป็นกรณีแรกที่เปิดเผยส่วนภายในของไลบรารี regex ออกมาเป็นไลบรารีแยกเวอร์ชันในระดับนี้
  • regex 1.9 ออกเมื่อวันที่ 5 กรกฎาคม 2023 และทำให้การเขียนใหม่นี้เสร็จสมบูรณ์
  • เนื้อหานี้มุ่งไปที่โปรแกรมเมอร์ Rust และผู้ที่สนใจ implementation ของเอนจิน regex ที่อิง finite automata โดยถือว่ามีประสบการณ์กับ regex อยู่แล้ว

ปัญหาก่อนการเขียนใหม่

  • regex crate เดิมใช้กลยุทธ์การค้นหาหลายแบบภายในตามแนวทางของ RE2 แต่กลยุทธ์ต่าง ๆ ถูกเพิ่มเข้ามาแบบค่อยเป็นค่อยไป ทำให้ ผสมผสานกันได้ยาก
    • PikeVM ถูกออกแบบเป็นกลยุทธ์แรก จึงขาดการจัดการที่จำเป็นสำหรับการเริ่มและหยุดค้นหาใน partial slice เมื่อใช้ร่วมกับ lazy DFA
    • ยากที่จะอนุมานได้ว่า regex ใดใช้กลยุทธ์ใด
    • expression match หลายจุด implement logic เดียวกันซ้ำ ๆ ทำให้การซิงก์กันคลาดเคลื่อนได้ง่าย
    • แม้แต่ regex ที่ใช้เพียง Aho-Corasick ก็อาจสร้าง Thompson NFA ที่ไม่จำเป็นและไม่ได้ใช้งานขึ้นมา
  • การทดสอบเอนจินภายในก็ยุ่งยากเช่นกัน
    • API สาธารณะดูเหมือนเป็นเอนจิน regex ตัวเดียว แต่ภายในมีกลยุทธ์หลายแบบ และต้องทำงานเหมือนกันสำหรับ input เดียวกัน
    • ก่อน regex 1.9 กลยุทธ์ภายในไม่ใช่ API สาธารณะ จึงยากที่จะทดสอบเอนจินแต่ละตัวอย่างอิสระ
    • การทดสอบเดิมมีโครงสร้างใกล้เคียงกับการ hack โดยพึ่งพาการเปิดเผย API ภายใน, implementation ของ From ที่ไม่ได้ทำเอกสารไว้, macro และ target ทดสอบแยกตามเอนจิน
  • มีคำขอ niche API หลายอย่างที่ใส่ลงในพื้นผิว API เดิมได้ยาก
    • RegexSet บอกได้เพียงว่าแพตเทิร์นใด match ที่ไหนสักแห่งใน haystack แต่ไม่ให้ match offset หรือ capture group offset
    • ต้องการความสามารถในการทำ anchored search โดยไม่ต้องใส่ ^ ลงในแพตเทิร์น
    • มีความต้องการให้ส่ง mutable scratch space เข้าไปโดยตรงระหว่างค้นหา โดยไม่มีการซิงโครไนซ์ภายใน
    • ยังมีคำขอให้รัน regex บน haystack ที่ไม่ต่อเนื่อง เช่น stream หรือ rope
  • หากเปิดเผยส่วนภายในเป็น crate แยกเวอร์ชัน ก็สามารถทดลอง API สำหรับผู้เชี่ยวชาญด้วยรอบ breaking change ที่เร็วกว่าได้ โดยไม่ทำให้ API regex สำหรับการใช้งานทั่วไปซับซ้อนขึ้น

ขอบเขต abstraction ที่เกิดจาก DFA ที่คอมไพล์สมบูรณ์

  • แรงจูงใจเริ่มต้นของ regex-automata คือการสร้างและ serialize DFA ที่คอมไพล์สมบูรณ์ แล้วให้ runtime ขนาดเล็กที่สุดที่ค้นหาด้วย zero-copy deserialization
  • regex-automata ช่วงแรกถูกใช้เพื่อสร้าง DFA สำหรับ implementation ของอัลกอริทึม Unicode ใน bstr
  • เมื่อสร้าง DFA ก็พบว่าต้องมีโครงสร้างข้อมูล NFA และ compiler ที่คล้ายกับ regex crate และเมื่อโค้ดนี้ซับซ้อนขึ้น ความจำเป็นในการแชร์ก็เพิ่มขึ้น
  • ตอนแรกมีการพิจารณา crate แยกอย่าง regex-nfa แต่มีโค้ดอีกมาก เช่น กระบวนการ determinization ที่สามารถแชร์ระหว่าง regex และ regex-automata ได้
  • ขอบเขต abstraction ใกล้เคียงกับ เอนจิน regex มากกว่า “NFA” และท้ายที่สุด regex-automata จึงถูกนิยามใหม่เป็นชุดของเอนจินหลายตัว
  • แผนระยะยาวคือวางเอนจิน regex ทั้งหมดไว้ใน regex-automata และทำให้ regex crate เป็น wrapper บาง ๆ ที่อยู่ด้านบน

ตรวจสอบโครงสร้างภายในด้วย regex-cli

  • regex-cli เป็นโปรแกรมที่ดูแลอยู่ใน repository ของ regex crate และให้เข้าถึง API ต่าง ๆ ของ regex-syntax, regex-automata และ regex ผ่าน command line
  • ติดตั้งได้ด้วยคำสั่งต่อไปนี้
cargo install regex-cli
  • regex-cli debug สามารถแสดง AST, HIR, literal, Thompson NFA, one-pass DFA, dense DFA, sparse DFA และอื่น ๆ
  • regex . ที่เปิด Unicode จะสร้าง Thompson NFA ที่ซับซ้อนกว่ามากเพื่อจัดการ UTF-8 scalar value ส่วน (?-u:.) ที่ปิด Unicode จะสร้าง NFA ที่เรียบง่ายกว่า
  • regex-cli find สามารถรันการค้นหาแบบชั่วคราวได้ และยังค้นหาแบบหลายแพตเทิร์นกับแสดง capture group ได้ผ่าน meta engine

โฟลว์ข้อมูลของการประมวลผล regex

  • สตริงแพตเทิร์นที่ส่งให้ Regex::new จะถูก parse เป็น Ast ก่อน
  • Ast จะถูกแปลงเป็น Hir
    • Hir มีรายละเอียดน้อยกว่า Ast และ Unicode case folding กับการอ้างอิง Unicode character class จะถูกขยายระหว่างการแปลง
  • จาก Hir จะสร้างสองสิ่ง
    • ลำดับ literal ที่ใช้สำหรับ optimization การค้นหา
    • Thompson NFA
  • NFA เป็นฐานสำหรับสร้างเอนจินหลายแบบ
    • PikeVM: จัดการ regex ทั้งหมดที่ parse ได้ และรายงาน capture group offset
    • BoundedBacktracker: รายงาน capture group offset ด้วย bounded backtracking
    • one-pass DFA: รายงาน capture group offset ได้รวดเร็วใน regex ที่มีข้อจำกัด
    • dense DFA: เร็วมาก แต่รายงานได้เฉพาะจุดเริ่มและจุดจบของ match ทั้งหมด และการสร้างต้องใช้เวลาและพื้นที่ในกรณีแย่สุด O(2^m)
    • lazy DFA: สร้าง DFA จาก NFA ระหว่างการค้นหา โดยปกติเร็วพอ ๆ กับ full DFA และหลีกเลี่ยงต้นทุนการสร้างแบบ exponential ของ full DFA
  • เอนจินเหล่านี้และ Prefilter ถูกประกอบเป็น meta regex engine เดียว และ regex crate เป็น wrapper บาง ๆ ของ meta engine นี้

การปรับแต่งลิเทอรัลให้เหมาะสม

  • การดึงลิเทอรัลเป็นการปรับแต่งสำคัญภายใน regex
    • ตัวอย่างเช่น ทุกแมตช์ของ (foo|bar|quux)(\s+\w+) จะเริ่มด้วยหนึ่งใน foo, bar, quux
  • เหตุผลที่ลิเทอรัลสำคัญคืออัลกอริทึมค้นหาสตริงเดียวหรือจำนวนน้อยนั้นเร็วมาก
    • สามารถใช้คำสั่งเวกเตอร์ประมวลผลหลายไบต์ของ haystack ได้ในครั้งเดียว
    • อัลกอริทึมแมตช์ regex ทั่วไปเร่งความเร็วอย่างสม่ำเสมอด้วยวิธีเดียวกันได้ยาก
  • การค้นหา substring ที่ปรับแต่งมาอย่างดีมักเร็วกว่าเอนจิน regex ทั่วไปอย่างน้อยระดับหนึ่งหลัก
  • การดึงลิเทอรัลเป็น ฮิวริสติก
    • ต้องลดอัตรา false positive ของแมตช์ตัวเลือก
    • ต้องลดผลกระทบของ prefilter ต่อ latency โดยรวมด้วย
    • ทั้งสองเงื่อนไขขึ้นกับ haystack แต่หากวิเคราะห์ haystack ก่อนค้นหา อาจทำให้เวลาค้นหาโดยรวมแย่ลง
  • ลำดับลิเทอรัลไม่ใช่เซต แต่เป็น sequence ที่มีลำดับ
    • regex crate ทำตาม semantics แบบ leftmost-first คล้าย Perl ดังนั้น | จึงไม่เป็นไปตามกฎการสลับที่
    • sam|samwise อาจดึงได้เฉพาะ sam แต่ samwise|sam จะพิจารณาทั้งสองตัว
  • การค้นหาสตริงเดียวใช้โมดูล memmem ของ crate memchr
    • อัลกอริทึมหลักคือ Two-Way ซึ่งมีเวลา worst-case O(n) และใช้พื้นที่คงที่
    • สำหรับ needle และ haystack สั้น ๆ จะใช้ Rabin-Karp
    • บน x86_64 จะใช้ประโยชน์จาก variant แบบ generic SIMD
  • การค้นหาหลายสตริงใช้อัลกอริทึมหลักเป็น Teddy ที่พอร์ตมาจาก Hyperscan และในบางกรณีก็ใช้ Aho-Corasick ด้วย

Thompson NFA และการปรับแต่ง

  • โครงสร้างข้อมูลศูนย์กลางภายใน regex crate คือ Thompson NFA
  • Thompson’s construction สร้าง NFA จาก representation เชิงโครงสร้างของ regex ได้ในเวลา O(m) โดย m แปรผันตามขนาด regex หลังขยาย counted repetition แล้ว
  • NFA สามารถใช้เป็นเอนจิน regex ได้โดยตรง และยังแปลงเป็นชนิดอื่นอย่าง DFA เพื่อใช้เป็นฐานของเอนจินอื่นได้ด้วย
  • การปรับแต่งหลักของคอมไพเลอร์ NFA ใหม่มุ่งลด epsilon transition
    • Thompson NFA มีเวลาสร้างที่ดี แต่ใช้ epsilon transition จำนวนมาก
    • การคำนวณ epsilon closure อาจก่อให้เกิดต้นทุนซ้ำระหว่างการค้นหาหรือการสร้าง DFA
  • การปรับแต่ง state แบบ sparse แสดง transition หลายช่วงไว้ใน state เดียว เพื่อลด instruction Split หลายตัวแบบเดิม
    • กำจัด epsilon transition ที่ไม่จำเป็นใน regex เช่น [A-Za-z0-9]
    • ใน representation ปัจจุบัน อาจมีผลต่อ cache และเพิ่ม heap memory ได้จาก indirection
  • การปรับแต่ง ออโตมาตา UTF-8 ขั้นต่ำ ลดขนาด NFA ใน Unicode class ขนาดใหญ่ได้อย่างมาก
    • ใน NFA แบบ byte-oriented เดิม \w อาจสร้างได้ถึง 3,564 states
    • คอมไพเลอร์ใหม่ใช้อัลกอริทึมของ Daciuk เพื่อสร้างโครงสร้างที่มี state น้อยกว่ามากและไม่มี epsilon transition
    • การ shrink ของ reverse NFA ถูกปิดไว้เป็นค่าเริ่มต้นเพราะมีต้นทุน compile time
  • การปรับแต่ง literal trie คอมไพล์ alternation ของลิเทอรัล เช่น zap|z|zapper, abc|xyz ให้เป็น trie ที่มีโครงสร้างร่วมกัน เพื่อลด epsilon transition
    • เพื่อรักษา semantics แบบ leftmost-first จะแบ่ง transition chunk ทุกจุดที่มี match ปรากฏ
  • งาน NFA ในอนาคตกำลังพิจารณา Glushkov NFA และการจัดเก็บด้วย allocation แบบ contiguous เดียว
    • Glushkov NFA ไม่มี epsilon transition แต่มี compile time complexity แย่กว่า
    • contiguous allocation อาจให้ cache friendliness และความเป็นไปได้ในการ serialize/deserialize แบบ zero-copy แต่มีความซับซ้อนของโค้ดและความเป็นไปได้ที่จะใช้ unsafe

เอนจิน regex รายตัว

  • เอนจินของ regex-automata ใช้ API คล้ายกัน
    • Input: ตั้งค่า haystack, ช่วงค้นหา, ว่าเป็น anchored หรือไม่ และว่าจะ early stop หรือไม่
    • Match: เก็บ byte span ที่แมตช์และ PatternID
    • MatchError: แทนข้อผิดพลาดที่ไม่สามารถตัดสินผลการค้นหาได้

  • PikeVM

    • รองรับฟีเจอร์ทั้งหมดที่ regex-syntax พาร์สได้ และทำงานได้กับ haystack ความยาวใดก็ได้
    • ติดตามตำแหน่ง capture group และคำนวณ active state แบบ lock-step จึงรับประกันเวลา worst-case O(m * n)
    • จุดอ่อนหลักคือประสิทธิภาพ เพราะต้องติดตาม state และตำแหน่ง capture group จำนวนมาก
    • มีคุณสมบัติเฉพาะในบรรดาเอนจิน regex-automata คือไม่คืนข้อผิดพลาดระหว่างการค้นหา

  • BoundedBacktracker

    • ใช้ backtracking บน Thompson NFA แต่ใช้ state เพิ่มเติมเพื่อไม่ย้อนติดตามงานที่ทำไปแล้วซ้ำ
    • รับประกันเวลา worst-case O(m * n) แต่ใช้พื้นที่ O(m * n)
    • จากการทดลองคร่าว ๆ โดยทั่วไปเร็วกว่า PikeVM ประมาณ 2 เท่า
    • อาจล้มเหลวได้หากความยาว haystack และขนาด regex เกิน visited capacity ที่ตั้งไว้

  • one-pass DFA

    • รายงาน offset ของ capture group ได้เร็วมากใน one-pass NFA ที่มีข้อจำกัด
    • ถือเป็นวิธีที่เร็วที่สุดสำหรับการรายงาน capture group
    • รองรับเฉพาะ anchored search และ regex จำนวนมากไม่ใช่ one-pass
    • ในโหมด Unicode regex ที่เดิมไม่เป็น one-pass เพราะ transition overlap ระดับ byte อาจกลายเป็น one-pass ได้เมื่อปิด Unicode

  • fully compiled DFA

    • ประกอบด้วย forward DFA และ reverse DFA สองตัว เพื่อหาจุดจบและจุดเริ่มของแมตช์ทั้งหมด
    • การสร้างมีเวลาและพื้นที่ worst-case O(2^m) และ dense DFA ใช้หน่วยความจำมาก
    • full DFA engine ถูกปิดเป็นค่าเริ่มต้นใน regex crate และต้อง opt-in ด้วย feature perf-dfa-full
    • ทำงานได้โดยไม่มี Cache แบบ mutable และสามารถ serialize เป็น raw bytes เพื่อใช้ runtime การค้นหาในสภาพแวดล้อมที่มีแค่ core ได้

  • hybrid NFA/DFA, lazy DFA

    • คล้าย full DFA แต่สร้าง transition table ระหว่างการค้นหา
    • หากมี transition ที่คำนวณไว้แล้วใน cache ก็จะนำมาใช้ซ้ำ หากไม่มี จะใช้ NFA powerset construction คำนวณเฉพาะ transition นั้น
    • เวลา worst-case ของการค้นหาคือ O(m * n) และพื้นที่ถูกจำกัดด้วย cache capacity ที่กำหนดตอนสร้าง
    • ในกรณีทั่วไป state และ transition ส่วนใหญ่จะถูก cache ไว้ จึงทำงานเหมือนมีค่าเฉลี่ย O(n) และในทางปฏิบัติมีประสิทธิภาพการค้นหาใกล้เคียง full DFA ใน regex จำนวนมาก
    • หาก cache เต็มซ้ำ ๆ จนไม่มีประสิทธิภาพ จะคืนข้อผิดพลาด และใน meta engine โดยทั่วไปจะลองใหม่ด้วยเอนจินอื่น

บทบาทของ meta regex engine

  • meta regex engine พยายามรวมหลายเอนจินเข้าเป็นหนึ่งเดียว และให้ API แบบ infallible แก่ผู้เรียก
  • ผู้เรียกไม่จำเป็นต้องสร้างและส่ง Cache เองในทุกการค้นหา
    • meta engine จัดการ thread-safe cache pool ภายใน
    • หากต้องการหลีกเลี่ยงต้นทุนจากการซิงโครไนซ์ ก็มี lower-level API ที่ให้ส่ง Cache อย่างชัดเจนด้วย
  • regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet ล้วนเป็น wrapper แบบบาง ๆ ของ meta engine
  • กลยุทธ์ภายในของ meta engine โดยคร่าว ๆ เป็นดังนี้
    • หากสามารถจัดการได้ด้วยการค้นหา substring แบบเดี่ยวหรือหลายรายการโดยไม่ต้องใช้เอนจิน regex ก็จะหลีกเลี่ยงการสร้าง NFA ด้วย
    • หากเป็นไปได้ จะดึงลำดับ prefix literal ออกมาใช้เป็น Prefilter
    • หาก prefix ไม่เหมาะสม จะลองทำ optimization แบบ reverse anchored, reverse suffix, reverse inner
    • นอกเหนือจากนั้นจะ fallback ไปยัง core strategy ซึ่งรวมถึง PikeVM, bounded backtracker, one-pass DFA, lazy DFA, full DFA
  • กลยุทธ์ทั้งหมดสรุปได้เป็นสองประโยค
    • ค้นหา literal ให้มากที่สุดเท่าที่ทำได้
    • หลีกเลี่ยงการใช้ PikeVM ให้มากที่สุดเท่าที่ทำได้
  • optimization แบบ reverse suffix และ reverse inner หากทำผิดอาจมีกรณีแย่สุดเป็น O(m * n^2) ตามขนาดของ haystack
    • meta engine จะตรวจจับสถานการณ์ที่ reverse scan กำลังจะข้ามจุดสิ้นสุดของ suffix match ก่อนหน้า และ fallback ไปยัง core strategy เพื่อคงการรับประกันความซับซ้อนเชิงเวลาไว้

ความแตกต่างจาก RE2

  • regex crate และ RE2 มีจุดคล้ายกันมาก
    • RE2 ก็มี NFA ที่เทียบได้กับ PikeVM, bitstate backtracker, one-pass NFA, lazy DFA และโครงสร้างที่ผสานหลายเอนจินเข้าด้วยกัน
    • ในบรรดาเอนจินข้างต้น สิ่งที่ RE2 ไม่มีคือ fully compiled DFA
  • ความแตกต่างหลักมีดังนี้
    • RE2 รองรับ semantics แบบ POSIX leftmost-longest เป็นตัวเลือก นอกเหนือจาก leftmost-first
    • RE2 รองรับ Unicode ได้จำกัดกว่า และไม่มีตัวเลือกให้ใช้ \w, \s, \d, \b ตามนิยาม Unicode
    • RE2 รองรับ character class set operation นอกเหนือจาก union ได้อย่างจำกัด
    • PikeVM ของ RE2 อาจมีประสิทธิภาพด้านหน่วยความจำดีกว่า
    • การ optimization สำหรับ literal ของ RE2 มีข้อจำกัด ขณะที่ regex crate ทำ literal optimization ได้มากกว่า
    • lazy DFA ของ RE2 ต้องมีการซิงโครไนซ์เพราะหลาย thread แชร์ transition cache เดียวกัน แต่ regex crate ต้องใช้ cache แยกตามแต่ละ thread จึงใช้หน่วยความจำมากกว่า
    • regex crate เผยแพร่ regex-syntax และ regex-automata เป็นไลบรารีที่มีเวอร์ชันแยกต่างหาก แต่ RE2 ไม่รองรับสิ่งนี้
    • regex-automata รองรับ first-class multi-pattern regex ในทุกเอนจิน และยังสามารถรายงาน match ของแต่ละแพตเทิร์นที่แมตช์ รวมถึง offset ของ capture group ได้ด้วย

กลยุทธ์การทดสอบและเบนช์มาร์ก

  • กลยุทธ์การทดสอบใหม่คือการทำให้เอนจินภายในเป็น first-class API อิสระ และทดสอบแต่ละเอนจินโดยตรง
  • การทดสอบ regex ทั้งหมดถูกกำหนดด้วยไฟล์ TOML
  • crate regex-test อ่านการทดสอบ TOML แล้วแปลงเป็น representation แบบมีโครงสร้าง
  • สำหรับการตั้งค่าแต่ละเอนจิน จะมี Rust unit test หนึ่งรายการ และรันการทดสอบ TOML ทั้งหมดที่ใช้กับเอนจินนั้นได้
  • เนื่องจาก Rust unit test framework ขยายความสามารถได้ไม่มาก จึงมีการเพิ่มโครงสร้างพื้นฐาน environment variable ของตัวเองสำหรับการกรองการทดสอบเฉพาะรายการ
  • เฉพาะ regex-automata ก็มี documentation test มากกว่า 450 รายการ
  • ในกระบวนการเตรียม regex 1.9 มีการเพิ่ม fuzz testing target จำนวนมาก และด้วยความช่วยเหลือจาก Addison Crump ก็พบ bug บางรายการ
  • เบนช์มาร์กเผยแพร่เป็น regex barometer ชื่อ rebar
    • rebar เบนช์มาร์กเอนจิน regex หลายตัว ไม่ใช่เฉพาะ regex crate
    • จากเบนช์มาร์ก 242 รายการ regex 1.9 เร็วกว่า regex 1.7.3 โดยเฉลี่ย 1.5 เท่าเมื่อวัดจากเวลาค้นหา
    • เวลาสำหรับ build regex ถดถอยลงเล็กน้อย
    • 1.8 เป็น transition release ที่มีงานเปลี่ยนผ่านบางส่วน จึงใช้ 1.7 เป็นฐานในการเปรียบเทียบ

ต้นทุนและทางเลือกแบบเบา

  • การเขียนใหม่ใช้เวลาว่างส่วนใหญ่ของผู้เขียนตลอดหลายปีที่ผ่านมา และโปรเจกต์อย่าง ripgrep ก็ไม่สามารถออก release ได้ระยะหนึ่ง
  • abstraction สาธารณะที่นำกลับมาใช้ซ้ำได้มักมีโค้ดมากกว่า abstraction สำหรับใช้ภายในเท่านั้น
    • ผลที่ตามมาคือขนาดไบนารีและเวลา compile เพิ่มขึ้น
  • เมื่อ API ของเอนจินภายในถูกเผยแพร่แบบมีเวอร์ชันแยก หากต้องการทำลาย API ก็จำเป็นต้องออก breaking change release ที่เหมาะสมของ regex-automata
  • เพื่อลดต้นทุน มีการใช้มาตรการสองอย่าง
    • ปิดใช้งาน fully compiled DFA engine โดยค่าเริ่มต้น และให้เป็น feature แบบ opt-in
    • เผยแพร่ regex-lite เป็น crate ใหม่
  • regex-lite ตั้งเป้าให้เป็น drop-in replacement ของ regex crate เกือบทั้งหมด แต่เน้น optimization ด้านขนาดไบนารีและเวลา compile
    • ยอมละทิ้งฟีเจอร์ด้าน Unicode และประสิทธิภาพบางอย่าง
    • ยังคงรับประกันความซับซ้อนเชิงเวลา O(m * n)
    • ไม่มี dependency เลย และมี parser regex ของตัวเอง รวมถึงไม่แชร์โค้ดกับ regex crate
  • regex-lite ยังเป็นมาตรการบรรเทาเชิงทดลอง แต่แสดงให้เห็นว่า แม้จะปิด optimization และฟีเจอร์ Unicode ผ่าน feature ของ regex crate ก็ยังยากที่จะเข้าใกล้ขนาดไบนารีและเวลา compile ของ regex-lite

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

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

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

  • แค่อ่านผ่านๆ ก็ยังรู้สึกว่า crate regex ของ Rust น่าประทับใจมาก
    BurntSushi สร้างของดีไว้หลายอย่าง แต่ crate regex ของ Rust นั้นระดับตำนาน และการที่ ecosystem ของ Rust มีไลบรารี regular expression ที่ทั้งเร็วและใช้ง่ายมาตั้งนานแล้วถือเป็นพรอย่างยิ่งต่อชุมชน
    ชุดบทความเรื่อง regular expression ของ Russ Cox ก็ดีมากเช่นกัน ตอนช่วงหน้าร้อนที่เริ่มรู้สึกว่า regular expression เป็นจุดตัดที่สมบูรณ์แบบระหว่างทฤษฎีกับงานปฏิบัติ ก็อาศัยบทความเหล่านั้นเป็นแนวทางในการสร้าง regex engine
    การเปลี่ยนแปลงด้านการทดสอบเชิงลึกในบทความนี้ก็น่าสนใจ และในฐานะที่มันเป็น crate สำคัญของ ecosystem แบบนี้ ก็รู้สึกขอบคุณที่มีคำอธิบายหัวข้อเชิงลึกเช่นนี้
    แม้บางครั้ง regular expression จะอ่านยากและถูกนำไปใช้เกินเลยในงานอย่างการตรวจสอบอีเมล แต่ก็ยังเป็นหนึ่งใน เครื่องมือที่มีความหนาแน่นสูง ที่สุดในแทบทุกภาษา
    หนังสือเชิงปฏิบัติที่รู้จักดีจริงๆ มีแค่ Mastering Regular Expressions ของ Jeffrey Friedl ส่วนฝั่งทฤษฎีก็มักอยู่ในหนังสือคอมไพเลอร์ และ Dragon Book ก็โอเคในมุมของการ implementation อยากรู้ว่ามีใครแนะนำหนังสือ regular expression เล่มอื่นอีกไหม

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... และ https://kean.blog/post/lets-build-regex ยอดเยี่ยมมากสำหรับการเริ่มต้นทำความเข้าใจ implementation ของ regex engine แบบที่ลดรูปลง
      แนวทางคือสร้าง nondeterministic finite automaton จาก regular expression แล้วค้นหาในกราฟมีทิศทางที่ได้ โดยถ้าสามารถไปถึงจุดยอดที่สอดคล้องกับสถานะสิ้นสุดได้ ก็ถือว่า match
      สำหรับคนที่ใช้ regular expression อยู่แล้ว แบบฝึกหัดนี้ช่วยให้เข้าใจว่ามันมีความเป็นเวทมนตร์น้อยกว่าที่คิด และถ้าจินตนาการถึงลูกบอลที่เด้งไปมาบน NFA ปัญหา catastrophic backtracking ที่สุดท้ายต้องเจอใน production ก็จะเริ่มมีความหมายในเชิงกายภาพขึ้นมา
      ส่วนที่เกี่ยวกับบทความต้นฉบับ ความเห็นสุดท้ายของ BurntSushi ใน https://github.com/rust-lang/regex/issues/822 ช่วยเพิ่มบริบทที่มีประโยชน์ให้กับย่อหน้าเรื่อง API เฉพาะทาง https://blog.burntsushi.net/regex-internals/#problem-request... การค้นหา regular expression หลายตัวในข้อความเดียวกันพร้อมกันนั้นซับซ้อนมากแต่ก็มีประโยชน์มากเช่นกัน เลยตื่นเต้นว่าจะมีอะไรที่ชุมชนสร้างขึ้นจากแพตเทิร์นนี้บ้าง
    • กรณีตัวอย่างคลาสสิกที่ regular expression โดดเด่นในงานคล้ายการ parsing คือเวลาต้องจัดการกับ รูปแบบที่มีตัวคั่นหลากหลาย
      ตัวอย่างเช่นรูปแบบที่มีจำนวนฟิลด์คงที่อย่าง header:field1,field2,field3\"data\"hash หรือรูปแบบที่องค์ประกอบส่วนใหญ่เป็นตัวเลือกอย่าง suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2 เครื่องมือพื้นฐานอย่าง split มักไม่พอ และ regular expression จะเหมาะกว่า
      นี่ก็เป็นสาเหตุที่ regular expression อ่านยากอย่างรวดเร็ว เพราะใน regex เดียวจะปนทั้งตัวคั่นระหว่างฟิลด์ ความถูกต้องของแต่ละฟิลด์ และการกำหนดว่าฟิลด์ไหนเป็นตัวเลือก
      ทั้งที่จริงแล้วนี่เป็นประเด็นคนละสามส่วน แต่ API ของ regex ส่วนใหญ่ไม่เปิดให้แยกสิ่งเหล่านี้ออกเป็นขั้นตอน และมักรับได้แค่สตริงเดียวที่รวมทุกอย่างเข้าด้วยกัน
    • สงสัยว่าไลบรารี RegEx นี้ใช้ JIT แบบ implementation ส่วนใหญ่ของ JavaScript หรือไม่ ถ้าไม่ใช่ นี่อาจเป็นกรณีที่ JavaScript ชนะ Rust ก็ได้
    • ช่วงหลังได้ทำงานเกี่ยวกับ RegEx เล็กน้อยและเลยอ่านบทความนี้ผ่านๆ จากภาษาที่ใช้ ดูเหมือนว่าจะใช้ PikeVM เพราะต่างจาก engine อื่นๆ ตรงที่มันไม่คืนค่า error
      เพราะข้อจำกัดของภาษาและสถานะการคุ้มครองลิขสิทธิ์ จึงต้องสร้างความสามารถด้าน RegEx ขึ้นมาใหม่เอง และบางครั้ง regular expression ก็ให้ความรู้สึกเหมือนวิชาไสยศาสตร์จริงๆ
      ไม่รู้ว่า engine อื่นถูกใช้บ่อยแค่ไหน แต่ถ้าหลายภาษาโปรแกรมใช้ PikeVM ก็พอจะเข้าใจได้ว่าทำไม Google ถึงทำ OS สำหรับเซิร์ฟเวอร์ของตัวเอง และพยายามดึง engine ที่เร็วกว่าเข้ามาใช้ในบางสถานการณ์เพื่อประหยัด clock cycle แม้เพียงไม่กี่รอบ
      รู้ดีว่าการเพิ่มตัวอักษรไม่กี่ตัวในสตริงค้นหาอาจทำให้ pattern matching ช้าลงอย่างมาก สุภาษิตที่ว่า “เก็บเล็กผสมน้อย เดี๋ยวของใหญ่ก็ตามมาเอง” ใช้ได้ดีกับ RegEx และ clock cycle เช่นกัน และถ้าย้อนนึกถึงบทสนทนาในยุค 90 ที่พูดถึงการประมวลผลข้อมูลหลายล้านเรคคอร์ดต่อวินาที ก็นึกได้ว่านี่คงทำให้โปรแกรมเมอร์บางคนร่ำรวยมาก
    • สิ่งที่ไม่ชอบที่สุดคือความแตกต่างเล็กๆ น้อยๆ ของ สำเนียง regex
      โดยเฉพาะวิธีจัดการเครื่องหมายคำพูดหรือวิธีจบ expression ที่ต่างกันมากเกินไประหว่างแต่ละสำเนียงและแต่ละบริบท จนเลิกพยายามจำและต้องค้นหาตัวอย่างใหม่ทุกครั้งที่จำเป็น

  • ตอนทำงานที่ ActiveState เคยได้รับมอบหมายให้ทำ ดีบักเกอร์ regex สำหรับ Komodo editor ร่วมกับเพื่อนร่วมงานที่เพิ่งเรียนจบใหม่ๆ
    พวกเราไปจ้าง Mark Jason Dominus ผู้เชี่ยวชาญ Perl ระดับตำนาน ให้เพิ่ม hook เข้าไปใน regex engine ของ Perl แล้วนำ hook เหล่านั้นมาแสดงใน UI เพื่อให้ผู้ใช้ดูการทำงานของ regex แบบทีละขั้นได้
    ทุกวันนี้เครื่องมือบนเว็บอาจดีกว่าแล้ว แต่ในปี 2001 Rx Debugger ของ Komodo ถือว่าล้ำสมัยมาก และก็สนุกมากที่ได้ทำงานนั้น

    • เคยมีช่วงหนึ่งที่ต้องการ ดีบักเกอร์ regex แบบออฟไลน์
      ตอนนั้นต้องทำงานกับเครือข่ายแบบ air-gapped คนที่ต้องใช้เครื่องมือจึงเข้าเว็บออนไลน์ไม่ได้ และไม่ว่าจะออกแบบอย่างไร ก็ไม่มีทางยอมให้นำข้อมูลงานไปใส่ในเครื่องมือออนไลน์ได้เลย
      แต่ความพยายามส่วนใหญ่มุ่งไปที่เครื่องมือออนไลน์ และเครื่องมือออฟไลน์นั้นมีน้อยและด้อยกว่ามากเมื่อเทียบกับ https://regex101.com/
    • อยากได้คำแนะนำเครื่องมือ บนเว็บ ที่เหมาะกับการใช้งานลักษณะนี้โดยเฉพาะ

  • สงสัยว่าสิ่งนี้จะใช้กับลิสต์ที่ไม่ใช่สตริงได้ไหม
    มันมีเครื่องมือทรงพลังสำหรับค้นหาและแก้ไขลิสต์ของตัวอักษรอยู่แล้ว แต่พอเป็นลิสต์ของตัวเลขหรือวันที่ขึ้นมา ทุกอย่างกลับหายไปหมด ซึ่งน่าหงุดหงิดเสมอ
    ตัวอย่างเช่น ถ้าอยากหา sequence ทั้งหมดในลิสต์วันที่พยายามล็อกอินที่มีการล้มเหลวอย่างน้อย 5 ครั้งแล้วตามด้วยความสำเร็จ ถ้าเป็น regex ก็เขียนได้ง่าย แต่ในความเป็นจริงกลับต้องมานั่งเขียนลูปเอง ใช้แฟลก และทำลิสต์ชั่วคราว
    จะเอาลิสต์ไปแปลงเป็นสตริงเพื่อประมวลผลแล้วค่อยแปลงกลับมาก็ได้ แต่ข้อเสียก็ค่อนข้างชัด ถึงจะไม่เร็วเท่า regex ที่ทำงานบนสตริง แต่ก็ไม่เข้าใจว่าทำไมถึงไม่มี regex สำหรับลิสต์ชนิดใดก็ได้
    ยังไปเจอ Python prototype ที่เคยทำไว้ด้วย: https://github.com/boppreh/listregex
    มันช้ามาก แต่ในแง่การทดลอง API ก็ถือว่าน่าพอใจ และยังมีเครื่องมือที่ไม่มีใน regex อย่างการกลับแพตเทิร์น, intersection, และการจับคู่แบบเป็นคู่

    • ทำไม่ได้ ไลบรารี regex นี้ผูกแน่นกับการค้นหาสตริง และนั่นเป็นการตัดสินใจด้านการออกแบบโดยตั้งใจ
      การจะทำให้เอนจิน regex แบบนี้มี alphabet แบบ generic นั้นแทบเป็นไปไม่ได้ตั้งแต่แรก โดยเฉพาะถ้าต้องทำให้เป็นจริงโดยไม่ทำลายทั้งการออกแบบ API และประสิทธิภาพของกรณีใช้งานหลัก
      ถ้าไม่สนประสิทธิภาพ การสร้างเอนจิน regex แบบนั้นไม่ใช่เรื่องยาก เช่น เอา crate regex-lite ที่ผมเผยแพร่มาแก้ให้ generic ได้เท่าที่ต้องการ และระหว่างทางก็น่าจะเจออุปสรรคที่น่าสนใจหลายอย่าง
      ของแบบนี้ก็ไม่ได้ว่าไม่มีเลย มีคนพยายามทำอยู่[1] เพียงแต่ดูจะประเมินประโยชน์ใช้สอยทั่วไปสูงเกินไปอยู่บ้าง เลยมักไม่ค่อยได้ traction มากนัก :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • std::basic_regex ในไลบรารีมาตรฐานของ C++ ก็ลองแนวทางนี้โดยเปิดคลาสเทมเพลตสำหรับชนิดตัวอักษรที่ผู้ใช้กำหนดเอง: https://en.cppreference.com/w/cpp/regex/basic_regex
      สามารถให้ trait class ที่นิยามพฤติกรรมที่ต้องการสำหรับ “ตัวอักษร” แบบกำหนดเองได้
      แต่ประสิทธิภาพตกลงมาก และมีแนวโน้มว่าจะทำงานได้พอๆ กับการใส่อ็อบเจ็กต์ที่ไม่ใช่ตัวอักษรแบบใดก็ได้ลงใน std::basic_string ที่ผู้ใช้กำหนดเอง
    • คงต้องนิยาม API สำหรับการจับคู่บน sliding window ของค่าต่างๆ ให้ได้ไม่ทางใดก็ทางหนึ่ง
      ไม่ใช่ว่าทำไม่ได้ แต่ภาษาส่วนใหญ่ก็ไม่ได้มีอินเทอร์เฟซที่ดีสำหรับเรื่องนี้

  • ผมใช้ Ripgrep ทุกวันเวลาอยากหาอะไรบางอย่างในโค้ดหรือไฟล์ข้อความ และไม่ว่าจะใช้บน Windows, Linux, Mac, VSCode หรือ Vim ก็รู้สึกขอบคุณทุกครั้ง
    มันเป็นหนึ่งในซอฟต์แวร์ที่เปลี่ยนชีวิตและวิธีทำงานของผม
    เวลาต้องฝืนใช้ grep จะรู้สึกเหมือนย้อนกลับไปยุคที่ทุกอย่างรันบน CPU คอร์เดียว และข้อมูลอยู่บนฮาร์ดดิสก์จานหมุน PATA/IDE ที่ช้ามาก
    BurntSushi สมควรได้รับการยกย่องอย่างเพียงพอท่ามกลางโปรแกรมเมอร์ชั้นยอด

    • ripgrep มีสายสืบทอดมาก่อน หน้านั้นมี ag และก่อนหน้านั้นมี ack ซึ่งทั้งหมดพยายามมอบอินเทอร์เฟซที่ดีกว่า grep แบบเรียบง่ายอย่างมาก

  • เคยต้องสร้าง RegexSet ด้วย regex ที่ยาวมากกว่า 10 ล้านรายการ เพราะปัญหาในงาน
    ไม่มีเอนจินไหนรับมือได้ในสภาพตั้งต้น และแม้แต่ RegexSet ของ Rust เองก็ไม่พอเมื่อใช้ค่าปริยาย
    ถึงอย่างนั้น การได้ใช้ regex-automata กับ regex-syntax และอ่านโค้ดของมันก็เป็นสื่อการเรียนรู้ที่มีประโยชน์มากในปี 2018
    สุดท้ายโปรเจกต์ในงานไปลงเอยด้วยการอิงโมเดลจาก Lucene API แต่ก็ทำได้เพราะได้เรียนพื้นฐานมาจาก regex crates ก่อน

    • regex 10 ล้านรายการนี่ขนาดมหาศาลมาก Aho-Corasick เองก็แทบจะรับมือ literal 10 ล้านรายการได้แบบเฉียดๆ เท่านั้น
      งานต่อจากนี้คือทำให้เอนจิน regex ขยายตัวรองรับแพตเทิร์นจำนวนมากขึ้นได้ดีขึ้น ตอนนี้มันคงพังก่อนถึง 10 ล้าน regex ไปไกล และก็ยากจะมั่นใจด้วยว่าเป้าหมายนั้นเป็นไปได้จริงไหม
      แต่ถึงอย่างไรก็ดี มันน่าจะดีขึ้นจากตอนนี้ได้แน่นอน
      แน่นอนว่าในโลกของการค้นหาแบบหลายแพตเทิร์น Hyperscan ถือเป็นเหมือนมาตรฐานทองคำอยู่แล้ว เพียงแต่ผมไม่แน่ใจว่ามันจะจัดการกับแพตเทิร์น 10 ล้านรายการได้ดีแค่ไหน
    • จากที่คุณไม่ได้ลงรายละเอียดไว้ตั้งแต่แรก คำตอบก็น่าจะเป็น “ไม่” แต่ถ้าพอจะเล่าได้ ก็อยากรู้เพิ่มเติมว่าปัญหาหรือโปรเจกต์นั้นคืออะไร

  • เคยลองเล่นกับ crate regex-automata มาก่อน และมันเป็นไลบรารีเดียวที่ใช้กับ text editor ได้ เพราะเปิดให้เข้าถึง DFA ภายในได้โดยตรง
    API ของไลบรารี regex ทั่วไปมักคาดว่าอินพุตเป็นสตริงต่อเนื่องก้อนเดียว แต่วิธีนี้เข้ากันได้กับโครงสร้างข้อมูลข้อความแบบใดก็ได้

  • โพสต์นี้ออกมาพอดีตอนที่กำลังเขียนโค้ดโดยใช้ crate regex-automata แถมยังเป็นรีลีสแรกๆ อย่าง 0.2.0 ด้วย
    ดูเหมือนถึงเวลาที่ต้องลงไปทำความเข้าใจโครงสร้างภายในแบบใหม่อีกครั้งแล้ว
    ยังไม่ได้อ่านบทความ แต่ดูน่าสนใจมากและจังหวะก็ดีมากด้วย
    พอกลับมาดูอีกทีไม่กี่นาทีต่อมา คำตอบก็ใกล้เคียงกับ “อาจจะใช่” แต่เพราะเป็นรีลีสทางการ เลยน่าจะช่วยให้โค้ดเรียบง่ายขึ้นได้มาก
    ผ่านไปอีกราว 10 นาที มันก็แทบ painless และเมธอด Builder::patch ใหม่ถือเป็นการอัปเกรดเต็มรูปแบบ
    ป.ล. ผมยังถูกบล็อกอยู่ใน GitHub repo ทั้งหมดของคุณ และเมื่อคิดว่าหลาย crate ถูกใช้อย่างแพร่หลาย ผมว่ามันไม่ค่อยยุติธรรมเท่าไร ผมจำเหตุการณ์ต้นเรื่องไม่ได้แล้ว ดูเหมือนว่า regex crates เองตอนนี้จะอยู่ใต้ org rust-lang แล้ว แต่ก็ยังมีหลายอย่างที่โต้ตอบไม่ได้

    • ในเอกสาร regex-automata 0.2.0 มีคำเตือนใหญ่เกี่ยวกับเรื่องนี้อยู่ และแนะนำอย่างหนักแน่นให้ใช้ 0.1: https://docs.rs/regex-automata/0.2.0/regex_automata/
      ผมเองก็จำเหตุการณ์ต้นเรื่องไม่ได้เหมือนกัน ผมบล็อกคนไว้เยอะด้วยหลายเหตุผล แต่ตอนนี้ปลดบล็อกให้แล้ว

  • BioJulia ได้เผยแพร่ Automa.jl ซึ่งเป็นเอนจิน regular expression แบบ pure Julia ที่สามารถแทรกโค้ด Julia ตามอำเภอใจได้ในช่วงคอมไพล์
    ไม่ได้ตั้งใจจะลดทอนความจริงที่ว่า regex ของ Rust ก้าวหน้ากว่า Automa มาก แต่ก็ยากที่จะเห็นด้วยกับคำกล่าวที่ว่านี่เป็นกรณีแรกที่เปิดเผยภายในของ regular expression ออกมาเป็นไลบรารี

    • ฟังดูเหมือนเป็นคนละสองเรื่อง
      ตัวอย่างเช่น PCRE2 มีการรองรับ “callout” ที่ฟังดูคล้ายกับสิ่งที่พูดถึง: https://www.pcre.org/current/doc/html/pcre2callout.html
      อย่าง ragel หรือ re2c เองก็ทำสิ่งคล้ายกันมานานแล้ว
      สิ่งที่บล็อกนี้พูดถึงคือการดึงเอาภายในของไลบรารี regular expression ออกมา ทำเป็นไลบรารีแยกที่มีการจัดการเวอร์ชันต่างหาก และเปิดให้ผู้อื่นนำไปประกอบใช้งานได้
      สำหรับ backtracker วิธีนี้มักจะไม่เป็นธรรมชาติเท่าไร เพราะเอนจินมักมี backtracker อยู่เพียงตัวเดียว แต่ไลบรารีที่อิงกับ automaton มักจะมีการนำหลายเอนจินมาประกอบกันได้หลากหลายรูปแบบ
      ถึงอย่างนั้น ฝั่ง backtracker ก็ยังสามารถเปิดเผยสิ่งอย่าง parser หรือ AST ของ regular expression ได้เช่นกัน ซึ่งโดยปกติแล้วมักไม่ได้เปิดเผยออกมา