Đưa nội bộ của regex engine thành một thư viện

 (blog.burntsushi.net)
1 điểm bởi GN⁺ 2023-07-06 | 1 bình luận | Chia sẻ qua WhatsApp
  • Crate Rust regex sau nhiều năm được viết lại đã công khai phần lớn engine nội bộ dưới dạng API của crate regex-automata có phiên bản tách riêng, và quá trình chuyển đổi hoàn tất trong regex 1.9
  • Việc viết lại bắt đầu từ các vấn đề khó kết hợp giữa các chiến lược tìm kiếm, độ khó khi kiểm thử từng engine nội bộ, nhu cầu về API đa mẫu chi tiết hơn RegexSet, và nhu cầu chia sẻ DFA biên dịch đầy đủ
  • regex-automata tổ chức xử lý regex theo luồng Ast → Hir → trích xuất literal/Prefilter → Thompson NFA → PikeVM·BoundedBacktracker·one-pass DFA·DFA·lazy DFA → meta engine
  • Hiệu năng được đảm bảo bằng cách ưu tiên tìm kiếm literal và các engine họ DFA khi có thể, rồi bổ sung bằng PikeVM, bounded backtracker và one-pass DFA trong các trường hợp có capture group hoặc tình huống ngoại lệ
  • API công khai và các trừu tượng có thể tái sử dụng giúp việc kiểm thử và thử nghiệm dễ hơn, nhưng làm tăng lượng mã, kích thước nhị phân và thời gian biên dịch; DFA biên dịch đầy đủ được để ở chế độ opt-in và regex-lite được thêm vào như một lựa chọn gọn nhẹ

Viết lại regex và công khai regex-automata

  • regex crate của Rust đã được viết lại trong nhiều năm để cải thiện cách kết hợp nội bộ, giúp bổ sung tối ưu hóa dễ hơn mà vẫn giữ được tính chính xác
  • Trong quá trình đó, regex-automata được tạo ra và phơi bày phần lớn triển khai nội bộ của regex crate thành một API riêng
  • regex-automata được giới thiệu là trường hợp đầu tiên công khai nội bộ của một thư viện regex thành một thư viện có phiên bản riêng ở mức độ như vậy
  • regex 1.9 được phát hành ngày 5 tháng 7 năm 2023 và hoàn tất việc viết lại này
  • Đối tượng nhắm tới là các lập trình viên Rust và những người quan tâm đến việc triển khai regex engine dựa trên finite automata, với giả định đã có kinh nghiệm về regex

Các vấn đề trước khi viết lại

  • regex crate cũ đi theo truyền thống RE2 và dùng nhiều chiến lược tìm kiếm ở bên trong, nhưng khi các chiến lược được bổ sung dần theo kiểu hữu cơ thì việc kết hợp trở nên khó khăn
    • PikeVM được thiết kế như chiến lược đầu tiên nên thiếu cơ chế xử lý bắt đầu/dừng tìm kiếm trên các lát cắt con cần thiết khi kết hợp với lazy DFA
    • Khó suy luận regex nào sẽ dùng chiến lược nào
    • Nhiều biểu thức match lặp lại cùng một logic nên dễ bị lệch đồng bộ
    • Ngay cả với regex chỉ cần Aho-Corasick, Thompson NFA không dùng đến vẫn có thể bị tạo ra một cách không cần thiết
  • Việc kiểm thử các engine nội bộ cũng phức tạp
    • API công khai trông như một regex engine duy nhất, nhưng bên trong có nhiều chiến lược và tất cả phải hoạt động giống nhau trên cùng một đầu vào
    • Trước regex 1.9, các chiến lược nội bộ không phải API công khai nên khó kiểm thử từng engine một cách độc lập
    • Các bài kiểm thử cũ có cấu trúc gần như hack, phụ thuộc vào việc lộ API nội bộ, các triển khai From không được tài liệu hóa, macro và mục tiêu kiểm thử riêng cho từng engine
  • Nhiều yêu cầu về API ngách cũng khó đưa vào bề mặt API hiện có
    • RegexSet chỉ cho biết mẫu nào khớp ở đâu đó trong haystack, chứ không cung cấp offset của match hay offset của capture group
    • Có nhu cầu thực hiện tìm kiếm anchored mà không cần chèn ^ vào mẫu
    • Có nhu cầu tự truyền mutable scratch space trực tiếp mà không có đồng bộ hóa nội bộ trong lúc tìm kiếm
    • Cũng có yêu cầu chạy regex trên haystack không liên tục như stream hoặc rope
  • Việc công khai phần nội bộ dưới dạng crate có phiên bản riêng cho phép thử nghiệm API dành cho người dùng chuyên sâu với nhịp breaking change nhanh hơn, mà không làm API regex phổ dụng trở nên phức tạp

Ranh giới trừu tượng do DFA biên dịch đầy đủ tạo ra

  • Động lực ban đầu của regex-automata là cung cấp runtime tối thiểu có thể tạo DFA biên dịch đầy đủ, tuần tự hóa nó, rồi tìm kiếm bằng giải tuần tự hóa zero-copy
  • regex-automata ban đầu được dùng để tạo DFA cho phần triển khai thuật toán Unicode của bstr
  • Trong quá trình tạo DFA, cần đến cấu trúc dữ liệu NFA và trình biên dịch tương tự regex crate, và khi phần mã này trở nên phức tạp hơn thì nhu cầu chia sẻ cũng tăng lên
  • Ban đầu từng cân nhắc một crate riêng như regex-nfa, nhưng còn nhiều mã hơn nữa như quá trình determinization có thể được chia sẻ giữa regex và regex-automata
  • Ranh giới trừu tượng thực tế gần với regex engine hơn là chỉ “NFA”, và cuối cùng regex-automata được định nghĩa lại thành một tập hợp nhiều engine
  • Kế hoạch dài hạn là đặt mọi regex engine vào regex-automata và biến regex crate thành một lớp bọc mỏng phía trên nó

Quan sát cấu trúc nội bộ bằng regex-cli

  • regex-cli là chương trình được quản lý trong kho lưu trữ của regex crate, cung cấp truy cập dòng lệnh tới nhiều API của regex-syntax, regex-automata và regex
  • Có thể cài đặt bằng lệnh sau
cargo install regex-cli
  • regex-cli debug có thể in AST, HIR, literal, Thompson NFA, one-pass DFA, dense DFA, sparse DFA, v.v.
  • Regex . khi bật Unicode sẽ tạo Thompson NFA phức tạp hơn nhiều để xử lý UTF-8 scalar value, còn (?-u:.) khi tắt Unicode sẽ tạo NFA đơn giản hơn
  • regex-cli find có thể chạy các phép tìm kiếm tạm thời, đồng thời với meta engine còn có thể thực hiện tìm kiếm đa mẫu và in capture group

Luồng dữ liệu xử lý regex

  • Chuỗi mẫu được truyền vào Regex::new trước hết được phân tích cú pháp thành Ast
  • Ast được chuyển thành Hir
    • Hir có ít chi tiết hơn Ast, và Unicode case folding cùng tham chiếu Unicode character class được mở rộng trong quá trình chuyển đổi
  • Từ Hir sẽ tạo ra hai thứ
    • Chuỗi literal dùng cho tối ưu hóa tìm kiếm
    • Thompson NFA
  • NFA là nền tảng để tạo nhiều engine
    • PikeVM: xử lý mọi regex có thể phân tích và báo cáo offset của capture group
    • BoundedBacktracker: dùng bounded backtracking để báo cáo offset của capture group
    • one-pass DFA: báo cáo offset của capture group nhanh trên các regex bị giới hạn
    • dense DFA: rất nhanh nhưng chỉ báo cáo điểm bắt đầu/kết thúc của toàn bộ match, và việc xây dựng trong trường hợp xấu nhất cần thời gian và không gian O(2^m)
    • lazy DFA: tạo DFA từ NFA trong lúc tìm kiếm, thường nhanh ngang full DFA nhưng tránh được chi phí xây dựng theo cấp số mũ của full DFA
  • Các engine này cùng với Prefilter được kết hợp thành một meta regex engine, và regex crate là lớp bọc mỏng của meta engine này

Tối ưu hóa literal

  • Trích xuất literal là một tối ưu hóa cốt lõi bên trong regex
    • Ví dụ, mọi kết quả khớp của (foo|bar|quux)(\s+\w+) đều bắt đầu bằng một trong foo, bar, quux
  • Literal quan trọng vì các thuật toán tìm kiếm một hoặc một vài chuỗi cực kỳ nhanh
    • Có thể xử lý nhiều byte của haystack cùng lúc bằng lệnh vector
    • Các thuật toán so khớp regex tổng quát khó được tăng tốc một cách nhất quán theo cùng cách đó
  • Tìm kiếm substring được tối ưu tốt thường nhanh hơn regex engine tổng quát ít nhất một bậc độ lớn trong nhiều trường hợp
  • Trích xuất literal là một heuristic
    • Cần giảm false positive rate của các candidate match
    • Cũng cần giữ tác động của prefilter lên tổng độ trễ ở mức thấp
    • Cả hai điều kiện đều phụ thuộc vào haystack, nhưng nếu phân tích haystack trước khi tìm kiếm thì tổng thời gian tìm kiếm có thể tệ đi
  • Chuỗi literal không phải là một tập hợp mà là một chuỗi có thứ tự
    • regex crate tuân theo ngữ nghĩa leftmost-first kiểu Perl, nên | không có tính giao hoán
    • sam|samwise có thể chỉ trích xuất sam, nhưng samwise|sam thì cả hai đều được xem xét
  • Với tìm kiếm một chuỗi, module memmem của crate memchr được sử dụng
    • Thuật toán chính là Two-Way với thời gian tệ nhất O(n) và không gian hằng số
    • Rabin-Karp được dùng cho needle và haystack ngắn
    • Trên x86_64, một biến thể SIMD generic được tận dụng
  • Với tìm kiếm nhiều chuỗi, Teddy được port từ Hyperscan là thuật toán chính, và trong một số trường hợp Aho-Corasick cũng được dùng

Thompson NFA và tối ưu hóa

  • Cấu trúc dữ liệu trung tâm bên trong regex crate là Thompson NFA
  • Thompson’s construction tạo NFA từ biểu diễn có cấu trúc của regex trong thời gian O(m), trong đó m tỉ lệ với kích thước regex sau khi mở rộng counted repetition
  • NFA có thể được dùng trực tiếp làm regex engine, đồng thời cũng có thể được chuyển đổi sang các kiểu khác như DFA để làm nền tảng cho engine khác
  • Tối ưu hóa chính của trình biên dịch NFA mới tập trung vào việc giảm epsilon transition
    • Thompson NFA có thời gian xây dựng tốt nhưng dùng rất nhiều epsilon transition
    • Việc tính epsilon closure có thể tạo ra chi phí lặp lại trong lúc tìm kiếm hoặc khi xây dựng DFA
  • Tối ưu hóa state sparse biểu diễn nhiều chuyển tiếp theo dải bằng một state duy nhất để giảm nhiều instruction Split trước đây
    • Loại bỏ epsilon transition không cần thiết trong các regex như [A-Za-z0-9]
    • Ở biểu diễn hiện tại, indirection có thể ảnh hưởng đến cache và có thể làm tăng heap memory
  • Tối ưu hóa minimal UTF-8 automata giảm mạnh kích thước NFA ở các Unicode class lớn
    • Trong NFA hướng byte trước đây, \w có thể tạo ra 3.564 state
    • Trình biên dịch mới dùng Daciuk’s algorithm để tạo ra cấu trúc với ít state hơn nhiều và zero epsilon transition
    • Việc thu nhỏ reverse NFA hiện bị tắt mặc định do chi phí compile time
  • Tối ưu hóa literal trie biên dịch các literal alternation như zap|z|zapper, abc|xyz thành trie để giảm epsilon transition
    • Để giữ nguyên ngữ nghĩa leftmost-first, transition chunk được chia tại mọi điểm có thể xuất hiện match
  • Các hướng phát triển NFA trong tương lai gồm Glushkov NFA và lưu trữ bằng một contiguous allocation duy nhất
    • Glushkov NFA không có epsilon transition nhưng độ phức tạp compile time kém hơn
    • Contiguous allocation có thể cải thiện cache friendliness và mở ra khả năng tuần tự hóa/giải tuần tự hóa zero-copy, nhưng có thể làm mã phức tạp hơn và có khả năng phải dùng unsafe

Các regex engine riêng lẻ

  • Các engine của regex-automata chia sẻ API khá giống nhau
    • Input: thiết lập haystack, phạm vi tìm kiếm, có anchored hay không, và có early stop hay không
    • Match: chứa byte span đã khớp và PatternID
    • MatchError: biểu thị lỗi không thể xác định kết quả tìm kiếm

  • PikeVM

    • Hỗ trợ toàn bộ tính năng mà regex-syntax có thể parse, và hoạt động với haystack ở mọi độ dài
    • Theo dõi vị trí capture group và tính các active state theo kiểu lock-step để bảo đảm thời gian tệ nhất O(m * n)
    • Điểm yếu chính là hiệu năng do phải theo dõi nhiều state và vị trí capture group
    • Có đặc tính riêng là không trả về lỗi trong lúc tìm kiếm trong số các engine của regex-automata

  • BoundedBacktracker

    • Dùng backtracking trên Thompson NFA nhưng có thêm state để không dò lại phần công việc đã thực hiện
    • Bảo đảm thời gian tệ nhất O(m * n) nhưng dùng không gian O(m * n)
    • Trong các thử nghiệm sơ bộ, thường nhanh hơn PikeVM khoảng 2 lần
    • Có thể thất bại nếu độ dài haystack và kích thước regex vượt quá visited capacity đã cấu hình

  • one-pass DFA

    • Báo cáo offset của capture group rất nhanh trên one-pass NFA bị giới hạn
    • Được xem là cách nhanh nhất để báo cáo capture group
    • Chỉ hỗ trợ anchored search, và nhiều regex không phải one-pass
    • Trong chế độ Unicode, một regex vốn không phải one-pass do chồng lấn transition ở mức byte có thể trở thành one-pass nếu tắt Unicode

  • fully compiled DFA

    • Gồm hai DFA, forward DFA và reverse DFA, để tìm điểm kết thúc và bắt đầu của toàn bộ match
    • Quá trình xây dựng có thời gian và không gian tệ nhất O(2^m), và dense DFA dùng rất nhiều bộ nhớ
    • Full DFA engine bị tắt mặc định trong regex crate và phải opt-in bằng feature perf-dfa-full
    • Hoạt động không cần Cache mutable, và có thể tuần tự hóa thành raw bytes để dùng runtime tìm kiếm cả trong môi trường chỉ có core

  • hybrid NFA/DFA, lazy DFA

    • Tương tự full DFA nhưng xây dựng transition table trong lúc tìm kiếm
    • Nếu transition đã được tính sẵn trong cache thì tái sử dụng, nếu chưa có thì chỉ tính transition đó bằng NFA powerset construction
    • Thời gian tìm kiếm tệ nhất là O(m * n), còn không gian bị giới hạn bởi cache capacity được đặt khi khởi tạo
    • Trong trường hợp phổ biến, phần lớn state và transition được cache nên hoạt động gần như O(n) trung bình, và thực tế cho hiệu năng tìm kiếm tương đương full DFA với nhiều regex
    • Nếu cache liên tục đầy và trở nên kém hiệu quả, engine sẽ trả về lỗi; trong meta engine, khi đó thường sẽ thử lại bằng engine khác

Vai trò của meta regex engine

  • meta regex engine nhằm gộp nhiều engine thành một và cung cấp cho bên gọi một API không thể thất bại
  • Bên gọi không cần tự tạo và truyền Cache cho mỗi lần tìm kiếm
    • meta engine quản lý một cache pool thread-safe ở bên trong
    • nếu muốn tránh chi phí đồng bộ hóa, nó cũng cung cấp API cấp thấp hơn để truyền Cache một cách tường minh
  • regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet đều là wrapper mỏng của meta engine
  • Chiến lược nội bộ của meta engine đại khái như sau
    • nếu có thể xử lý chỉ bằng tìm kiếm substring đơn hoặc nhiều mẫu mà không cần regex engine, thì nó tránh cả việc dựng NFA
    • nếu có thể, nó trích xuất chuỗi literal tiền tố để dùng làm Prefilter
    • nếu tiền tố không phù hợp, nó thử các tối ưu hóa reverse anchored, reverse suffix, reverse inner
    • ngoài ra, nó fallback về chiến lược lõi gồm PikeVM, bounded backtracker, one-pass DFA, lazy DFA, full DFA
  • Toàn bộ chiến lược có thể rút gọn thành hai câu
    • càng nhiều càng tốt, hãy tìm kiếm literal
    • càng nhiều càng tốt, hãy tránh dùng PikeVM
  • Tối ưu hóa reverse suffix và reverse inner nếu làm không đúng có thể dẫn tới trường hợp xấu nhất O(m * n^2) theo kích thước haystack
    • meta engine phát hiện tình huống reverse scan sắp vượt quá điểm kết thúc của suffix match trước đó và fallback về chiến lược lõi để giữ bảo đảm về độ phức tạp thời gian

Khác biệt với RE2

  • regex crate và RE2 có nhiều điểm giống nhau
    • RE2 cũng có NFA tương ứng với PikeVM, bitstate backtracker, one-pass NFA, lazy DFA và cấu trúc kết hợp nhiều engine
    • trong các engine trên, thứ RE2 không có là fully compiled DFA
  • Các khác biệt chính như sau
    • ngoài leftmost-first, RE2 còn hỗ trợ tùy chọn ngữ nghĩa leftmost-longest kiểu POSIX
    • RE2 có hỗ trợ Unicode hạn chế hơn và không có tùy chọn dùng \w, \s, \d, \b theo định nghĩa Unicode
    • RE2 hỗ trợ hạn chế đối với các phép toán trên tập character class ngoài union
    • PikeVM của RE2 có thể hiệu quả bộ nhớ hơn
    • tối ưu hóa literal của RE2 bị giới hạn hơn, còn regex crate thực hiện nhiều tối ưu hóa literal hơn
    • lazy DFA của RE2 cho phép nhiều thread chia sẻ cùng một transition cache nên cần đồng bộ hóa, trong khi regex crate yêu cầu cache riêng cho từng thread nên dùng nhiều bộ nhớ hơn
    • regex crate công bố regex-syntax và regex-automata như các thư viện tách biệt có phiên bản riêng, còn RE2 thì không hỗ trợ điều này
    • regex-automata hỗ trợ multi-pattern regex như tính năng first-class trên mọi engine và cũng có thể báo cáo match cùng offset của capture group cho từng pattern khớp

Chiến lược kiểm thử và benchmark

  • Chiến lược kiểm thử mới là biến các engine nội bộ thành API first-class độc lập và kiểm thử trực tiếp từng engine
  • Tất cả bài kiểm thử regex đều được mô tả bằng file TOML
  • crate regex-test đọc các bài kiểm thử TOML và chuyển chúng thành biểu diễn có cấu trúc
  • Mỗi cấu hình engine có một Rust unit test, và test đó chạy toàn bộ các bài kiểm thử TOML áp dụng được cho engine tương ứng
  • Vì framework Rust unit test không có khả năng mở rộng, hạ tầng environment variable riêng đã được thêm vào để lọc các bài kiểm thử cụ thể
  • Chỉ riêng regex-automata đã có hơn 450 documentation test
  • Trong quá trình chuẩn bị regex 1.9, cũng có thêm nhiều fuzz testing target, và với sự giúp đỡ của Addison Crump đã tìm ra một số lỗi
  • Benchmark được công khai qua regex barometer tên là rebar
    • rebar benchmark không chỉ regex crate mà còn nhiều regex engine khác
    • trên 242 benchmark, regex 1.9 nhanh hơn regex 1.7.3 trung bình 1,5 lần xét theo thời gian tìm kiếm
    • thời gian build regex có phần bị thụt lùi
    • 1.8 là bản phát hành chuyển tiếp có bao gồm một phần công việc chuyển đổi, nên 1.7 được dùng làm mốc so sánh

Chi phí và các lựa chọn thay thế nhẹ hơn

  • Việc viết lại đã tiêu tốn phần lớn thời gian rảnh của tác giả trong vài năm qua, và các dự án như ripgrep đã không thể phát hành trong một thời gian
  • Các trừu tượng công khai có thể tái sử dụng thường có xu hướng cần nhiều mã hơn các trừu tượng chỉ dùng nội bộ
    • kết quả là kích thước binary và thời gian biên dịch tăng lên
  • Khi API engine nội bộ được công khai như một phiên bản riêng, việc phá vỡ API sẽ đòi hỏi một breaking change release phù hợp của regex-automata
  • Để giảm bớt chi phí, hai biện pháp đã được áp dụng
    • fully compiled DFA engine bị tắt mặc định và được để ở dạng feature opt-in
    • regex-lite được phát hành như một crate mới
  • regex-lite nhắm tới việc gần như là drop-in replacement cho regex crate, nhưng tập trung vào tối ưu kích thước binary và thời gian biên dịch
    • nó đánh đổi các tính năng về Unicode và hiệu năng
    • vẫn giữ bảo đảm độ phức tạp thời gian O(m * n)
    • có 0 dependency, tự bao gồm regex parser riêng và không chia sẻ mã với regex crate
  • regex-lite hiện vẫn là một biện pháp giảm nhẹ mang tính thử nghiệm, nhưng nó cho thấy rằng ngay cả khi tắt các tính năng tối ưu hóa và Unicode của regex crate thì cũng khó có thể tiến gần tới kích thước binary và thời gian biên dịch của regex-lite

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-07-06
Ý kiến trên Hacker News

  • Mới chỉ lướt qua thôi mà crate regex của Rust đã thật sự rất ấn tượng
    BurntSushi đã tạo ra nhiều thứ tuyệt vời, nhưng crate regex của Rust thì mang tầm huyền thoại, và việc hệ sinh thái Rust từ rất lâu đã có một thư viện regex vừa hiệu năng cao vừa dễ dùng là một phước lành lớn cho cộng đồng
    Loạt bài viết về regex của Russ Cox cũng rất xuất sắc, nên khi regex bắt đầu cho cảm giác như giao điểm hoàn hảo giữa lý thuyết và thực hành, tôi đã tham khảo chúng trong suốt mùa hè để tự làm một regex engine
    Những thay đổi kiểm thử sâu hơn trong bài này cũng rất thú vị, và vì đây là một crate cốt lõi của hệ sinh thái nên thật đáng quý khi có lời giải thích về những chủ đề chuyên sâu như vậy
    Regex đôi khi khó đọc và cũng hay bị lạm dụng vào những việc như kiểm tra email, nhưng trong gần như mọi ngôn ngữ nó vẫn là một trong những công cụ cô đọng nhất
    Về sách thực hành thì tôi chỉ biết khá rõ cuốn Mastering Regular Expressions của Jeffrey Friedl, còn phía lý thuyết thì các sách về compiler thường có đề cập, và Dragon Book cũng ổn nếu nhìn từ góc độ triển khai. Tôi muốn biết có ai đề xuất thêm sách nào về regex không

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... và https://kean.blog/post/lets-build-regex là phần nhập môn rất tốt cho việc hiện thực một regex engine đã được đơn giản hóa
      Cách làm là tạo một ôtômát hữu hạn không đơn định cho regex, rồi duyệt trên đồ thị có hướng kết quả, và nếu có thể đi tới đỉnh tương ứng với trạng thái kết thúc thì xem như khớp
      Với người dùng regex, bài tập này giúp hiểu rằng thực ra nó ít phép màu hơn tưởng tượng, và nếu hình dung các quả bóng nảy qua lại trên NFA thì lỗi backtracking thảm họa mà cuối cùng ai cũng gặp trong môi trường production cũng trở nên có ý nghĩa vật lý hơn
      Liên quan tới bài gốc, bình luận cuối cùng của BurntSushi tại https://github.com/rust-lang/regex/issues/822 bổ sung thêm ngữ cảnh hữu ích cho đoạn về API ngách https://blog.burntsushi.net/regex-internals/#problem-request.... Việc tìm đồng thời nhiều regex trong cùng một văn bản là cực kỳ phức tạp nhưng cũng cực kỳ hữu ích, nên tôi rất mong chờ xem cộng đồng sẽ xây được gì từ mẫu hình này
    • Một trường hợp điển hình mà regex tỏa sáng trong các tác vụ gần giống parsing là khi phải xử lý định dạng có nhiều loại dấu phân cách
      Ví dụ như header:field1,field2,field3\"data\"hash với định dạng số trường cố định, hoặc suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2 với định dạng mà hầu hết thành phần là tùy chọn; trong những trường hợp đó các công cụ cơ bản như split là không đủ và regex lại rất phù hợp
      Đây cũng là lý do regex nhanh chóng trở nên khó đọc. Trong một regex duy nhất, dấu phân cách giữa các trường, tính hợp lệ của từng trường, và việc trường nào là tùy chọn đều bị trộn lẫn với nhau
      Đáng ra đây là ba mối quan tâm riêng biệt, nhưng phần lớn API regex lại không cho phép tách chúng thành từng bước mà buộc phải nhận một chuỗi gộp tất cả lại
    • Không rõ thư viện RegEx này có dùng JIT như phần lớn các triển khai JavaScript hay không. Nếu không thì đây có thể là một trường hợp JavaScript đánh bại Rust
    • Gần đây tôi có làm một chút việc với RegEx và đã lướt qua bài này; ngôn ngữ được dùng dường như là PikeVM, vì khác với các engine khác, nó không trả về lỗi
      Do các ràng buộc của ngôn ngữ và tình trạng được bảo hộ bản quyền, tôi phải tự xây lại chức năng RegEx, và có lúc regex thật sự mang cảm giác như tà thuật
      Tôi không biết các engine khác được dùng thường xuyên đến mức nào, nhưng nếu nhiều ngôn ngữ lập trình dùng PikeVM thì tôi có thể hiểu vì sao Google lại làm OS riêng cho máy chủ và trong vài tình huống nhất định còn huy động các engine nhanh hơn để tiết kiệm thêm từng chu kỳ clock
      Ai cũng biết chỉ cần thêm vài ký tự vào chuỗi tìm kiếm là việc khớp mẫu có thể chậm đi đáng kể. Câu “nhặt bạc lẻ thì tiền lớn tự đến” rất đúng với RegEx và cả chu kỳ clock, và nhìn lại những cuộc trò chuyện từ thập niên 90 về việc xử lý hàng triệu bản ghi mỗi giây thì điều này hẳn đã khiến không ít coder trở nên rất giàu
    • Điều khiến tôi khó chịu nhất là những khác biệt nhỏ giữa các phương ngữ regex
      Đặc biệt là cách xử lý dấu nháy và cách kết thúc biểu thức thay đổi quá nhiều giữa từng phương ngữ và từng ngữ cảnh, đến mức tôi đã bỏ ý định học thuộc và cứ khi cần lại đi tìm ví dụ

  • Ở ActiveState, tôi từng được giao cùng một đồng nghiệp vừa mới ra trường làm trình gỡ lỗi regex cho trình soạn thảo Komodo
    Chúng tôi thuê huyền thoại Perl Mark Jason Dominus để gắn hook vào regex engine của Perl, rồi đưa các hook đó lên UI để người dùng có thể xem quá trình thực thi regex theo từng bước
    Ngày nay các công cụ web tốt hơn nhiều, nhưng vào năm 2001, Rx Debugger của Komodo là công nghệ tiên tiến nhất, và làm dự án đó cũng rất vui

    • Trước đây tôi từng cần một trình gỡ lỗi regex chạy ngoại tuyến
      Tôi làm việc với các mạng air-gapped, nên những người phải dùng công cụ không thể truy cập các trang web trực tuyến, và trong bất kỳ thiết kế nào, việc đưa dữ liệu công việc vào công cụ online thậm chí còn không được phép nghĩ tới
      Thế nhưng phần lớn nỗ lực lại dồn vào các công cụ online, còn công cụ offline thì hiếm và kém hơn hẳn những thứ như https://regex101.com/
    • Tôi muốn biết có ai gợi ý cụ thể về công cụ web phù hợp cho mục đích này không

  • Tôi tò mò liệu có thể dùng thứ này cho cả danh sách chứ không chỉ chuỗi hay không
    Luôn có những công cụ mạnh để tìm kiếm và chỉnh sửa danh sách ký tự, nhưng hễ chuyển sang danh sách số hoặc ngày tháng thì mọi thứ gần như biến mất, điều đó lúc nào cũng khiến tôi thấy bức bối
    Ví dụ, nếu muốn tìm mọi chuỗi trong danh sách ngày đăng nhập mà có thành công xuất hiện sau ít nhất 5 lần thất bại, thì với regex việc này rất đơn giản, nhưng ngoài thực tế lại phải tự viết vòng lặp, cờ và danh sách tạm
    Cũng có thể chuyển danh sách thành chuỗi để xử lý rồi đổi lại, nhưng nhược điểm thì quá rõ. Dù có thể không nhanh bằng regex dựa trên chuỗi, tôi vẫn không hiểu vì sao lại không nên có regex cho các kiểu danh sách tùy ý
    Tôi cũng tìm lại được bản prototype Python mình từng làm: https://github.com/boppreh/listregex
    Nó rất chậm, nhưng để thử nghiệm API thì khá ổn, và còn cung cấp những công cụ mà regex không có như đảo mẫu, giao nhau và ghép cặp

    • Không được. Thư viện regex này gắn rất chặt với việc tìm kiếm chuỗi, và đó là quyết định thiết kế có chủ ý
      Việc làm cho một engine regex như vậy có bảng chữ cái tổng quát gần như bất khả thi ngay từ đầu. Đặc biệt là rất khó làm điều đó theo cách không phá hỏng thiết kế API và hiệu năng cho trường hợp sử dụng chính
      Một engine regex kiểu đó mà không quan tâm đến hiệu năng thì không khó làm. Ví dụ, bạn có thể lấy crate regex-lite tôi đã công khai rồi sửa cho nó tổng quát đến mức mong muốn, và trong quá trình đó sẽ gặp vài trở ngại khá thú vị
      Cũng không phải hoàn toàn chưa từng có. Người ta đã thử làm[1]. Chỉ là có vẻ họ hơi phóng đại tính hữu dụng chung của nó nên thường không đạt được traction lớn :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • std::basic_regex của thư viện chuẩn C++ cũng thử theo hướng này bằng cách cung cấp một lớp mẫu cho kiểu ký tự do người dùng định nghĩa: https://en.cppreference.com/w/cpp/regex/basic_regex
      Bạn có thể cung cấp một lớp trait định nghĩa hành vi cần thiết cho “ký tự” tùy chỉnh
      Nhưng hiệu năng giảm rất mạnh, và có lẽ nó chỉ hoạt động tốt ngang mức nhét các đối tượng không phải ký tự tùy ý vào một std::basic_string tùy chỉnh
    • Bạn sẽ phải định nghĩa bằng cách nào đó một API khớp trên cửa sổ trượt của các giá trị
      Không phải là bất khả thi, nhưng phần lớn ngôn ngữ không có giao diện tốt cho việc này

  • Tôi dùng Ripgrep mỗi ngày khi cần tìm thứ gì đó trong mã hoặc tệp văn bản, và lần nào dùng nó trên Windows, Linux, Mac, VSCode hay Vim tôi cũng thấy biết ơn
    Đây là một trong những phần mềm đã thay đổi cuộc sống và cách tôi làm việc
    Mỗi khi bị ép phải dùng grep, tôi có cảm giác như quay lại thời mọi thứ chạy trên CPU đơn nhân và dữ liệu nằm trên ổ cứng quay PATA/IDE chậm chạp
    BurntSushi xứng đáng được kính trọng nhiều hơn trong giới những lập trình viên vĩ đại

    • ripgrep có cả một dòng tiến hóa phía trước. Trước nó là ag, trước nữa là ack, và tất cả đều cố mang lại giao diện tốt hơn rất nhiều so với grep đơn thuần

  • Tôi từng phải tạo một RegexSet với hơn 10 triệu regex cho một bài toán công việc
    Không có engine nào chịu nổi ở cấu hình mặc định, và RegexSet của Rust với thiết lập mặc định cũng không đủ
    Dù vậy, việc dùng regex-automata và regex-syntax rồi đọc mã nguồn của chúng là tài liệu học tập cực kỳ bổ ích đối với tôi ngay cả từ năm 2018
    Cuối cùng, dự án công việc được mô hình hóa theo API của Lucene, nhưng chỉ khả thi sau khi tôi học nền tảng từ các crate regex

    • 10 triệu regex là quy mô khổng lồ. Ngay cả Aho-Corasick cũng chỉ vừa đủ sức xử lý 10 triệu literal
      Công việc sắp tới là làm cho engine regex mở rộng tốt hơn với số lượng mẫu lớn hơn. Hiện tại nó sẽ gục ngã từ rất lâu trước mốc 10 triệu regex, và cũng khó mà chắc mục tiêu đó có thực sự khả thi không
      Nhưng chắc chắn vẫn có thể tốt hơn hiện tại
      Tất nhiên, trong tìm kiếm đa mẫu thì Hyperscan gần như là chuẩn vàng trên thực tế. Dù vậy, tôi không rõ nó xử lý 10 triệu mẫu tốt đến mức nào
    • Việc bạn không viết chi tiết ngay từ đầu làm tôi đoán câu trả lời là “không”, nhưng nếu có thể thì tôi vẫn rất muốn biết thêm bài toán hay dự án đó là gì

  • Tôi từng thử nghiệm crate regex-automata, và đó là thư viện duy nhất tôi có thể dùng cho trình soạn thảo văn bản vì nó cho phép truy cập trực tiếp vào DFA nội bộ
    API của các thư viện regex thông thường giả định đầu vào là một chuỗi liên tục duy nhất, còn cách này thì tương thích với bất kỳ cấu trúc dữ liệu văn bản nào

  • Bài viết này xuất hiện đúng lúc tôi đang viết mã dùng regex-automata, lại còn là bản phát hành 0.2.0 đời đầu
    Có lẽ đã đến lúc xem lại xem có cần đào sâu vào cấu trúc bên trong mới hay không
    Tôi vẫn chưa đọc bài, nhưng trông nó rất thú vị và thời điểm cũng quá chuẩn
    Vài phút sau khi xem thì câu trả lời có vẻ gần với “có thể”, nhưng vì đây là bản phát hành chính thức nên ngược lại tôi có thể đơn giản hóa mã khá nhiều
    Thêm khoảng 10 phút nữa thì việc này khá painless, và phương thức Builder::patch mới đúng là một nâng cấp hoàn hảo
    Tái bút: tôi vẫn đang bị chặn trên tất cả kho GitHub của bạn, và xét đến việc nhiều crate của bạn được dùng rất rộng rãi thì tôi thấy hơi bất công. Tôi cũng không nhớ vụ việc ban đầu là gì. Có vẻ bản thân các crate regex giờ đã nằm dưới tổ chức rust-lang, nhưng vẫn còn những thứ tôi không thể tương tác

    • Tài liệu của regex-automata 0.2.0 có cảnh báo rất lớn về việc này, và khuyến nghị mạnh rằng nên dùng 0.1: https://docs.rs/regex-automata/0.2.0/regex_automata/
      Tôi cũng không nhớ vụ việc ban đầu. Tôi chặn khá nhiều người vì nhiều lý do, nhưng giờ đã bỏ chặn bạn rồi

  • BioJulia đã công bố Automa.jl, một trình máy regex thuần Julia có thể chèn mã Julia tùy ý tại thời điểm biên dịch
    Không phải tôi muốn hạ thấp việc regex của Rust tiên tiến hơn Automa rất nhiều, nhưng tôi khó đồng ý với cách diễn đạt rằng đây là trường hợp đầu tiên phơi bày phần bên trong của regex thành thư viện

    • Nghe như đây là hai việc khác nhau
      Ví dụ, PCRE2 có hỗ trợ “callout” nghe khá giống điều đang nói tới: https://www.pcre.org/current/doc/html/pcre2callout.html
      Những thứ như ragel hay re2c cũng đã làm việc tương tự từ lâu
      Điều bài blog này nói đến là lấy phần nội bộ của chính thư viện regex ra, biến nó thành một thư viện được quản lý phiên bản riêng, để người khác có thể kết hợp sử dụng
      Với backtracker thì cách này thường kém tự nhiên hơn vì thông thường trình máy chỉ có một backtracker, nhưng các thư viện dựa trên automaton thì thường kết hợp nhiều trình máy theo nhiều cách khác nhau
      Dù vậy, ngay cả backtracker trên thực tế cũng có thể phơi bày những thứ như parser regex hay AST, vốn thường không được công khai