रेगेक्स इंजन के अंदरूनी हिस्से अब लाइब्रेरी के रूप में

 (blog.burntsushi.net)
1 पॉइंट द्वारा GN⁺ 2023-07-06 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Rust regex crate ने कई वर्षों के rewrite के बाद अपने internal engine के बड़े हिस्से को अलग version वाले regex-automata crate API के रूप में public किया, और regex 1.9 में यह transition पूरा हुआ
  • rewrite की शुरुआत search strategy के मेल-जोल की कठिनाई, internal engine-वार testing की मुश्किल, RegexSet से अधिक granular multi-pattern API की मांग, और fully compiled DFA को साझा करने की ज़रूरत से हुई
  • regex-automata regex processing को Ast → Hir → literal extraction/Prefilter → Thompson NFA → PikeVM·BoundedBacktracker·one-pass DFA·DFA·lazy DFA → meta engine flow में संगठित करता है
  • performance इस तरह हासिल की जाती है कि जहाँ संभव हो पहले literal search और DFA परिवार के engine इस्तेमाल किए जाते हैं, और capture group या exceptional case में PikeVM·bounded backtracker·one-pass DFA से पूरक किया जाता है
  • public API और reusable abstraction ने testing और experimentation को आसान बनाया, लेकिन code size, binary size और compile time बढ़े; fully compiled DFA को opt-in रखा गया और regex-lite को हल्के विकल्प के रूप में जोड़ा गया

regex rewrite और regex-automata का public release

  • Rust का regex crate internal composition को बेहतर बनाने, optimization को और आसानी से जोड़ने, और correctness बनाए रखने के लिए कई वर्षों तक rewrite किया गया
  • इस प्रक्रिया में regex-automata बना, जो regex crate के internal implementation के बड़े हिस्से को अलग API के रूप में expose करता है
  • regex-automata को इस रूप में पेश किया गया कि regex library के अंदरूनी हिस्सों को इस स्तर तक अलग version वाली library के रूप में public करने का यह पहला उदाहरण है
  • regex 1.9 5 जुलाई 2023 को release हुआ और इसी के साथ यह rewrite पूरा हुआ
  • यह Rust programmers और finite automata आधारित regex engine implementation में रुचि रखने वालों के लिए है, और regex के अनुभव को पूर्वधारणा मानता है

rewrite से पहले की समस्याएँ

  • मौजूदा regex crate ने RE2 परंपरा का पालन करते हुए internal रूप से कई search strategies का उपयोग किया, लेकिन ये strategies समय के साथ organic तरीके से जुड़ती गईं, जिससे इनका संयोजन कठिन हो गया
    • PikeVM को पहली strategy के रूप में डिज़ाइन किया गया था, इसलिए lazy DFA के साथ संयोजन में ज़रूरी partial-slice search start/stop handling की कमी थी
    • यह समझना कठिन था कि किस regex पर कौन-सी strategy इस्तेमाल होगी
    • कई match expressions एक ही logic को बार-बार implement करते थे, जिससे synchronization बिगड़ना आसान था
    • जिन regex में केवल Aho-Corasick ही काफ़ी होता, उनमें भी इस्तेमाल न होने वाला Thompson NFA अनावश्यक रूप से बन सकता था
  • internal engine testing भी कठिन थी
    • public API एक ही regex engine जैसा दिखता है, लेकिन अंदर कई strategies हैं, और उन्हें एक ही input पर समान व्यवहार करना चाहिए
    • regex 1.9 से पहले internal strategies public API नहीं थीं, इसलिए हर engine को स्वतंत्र रूप से test करना मुश्किल था
    • मौजूदा tests का ढाँचा internal API exposure, undocumented From implementations, macros, और engine-specific test targets पर निर्भर लगभग hack जैसा था
  • कई niche API अनुरोध भी मौजूदा API surface में जोड़ना असहज था
    • RegexSet केवल यह बताता है कि कौन-सा pattern haystack में कहीं match हुआ, लेकिन match offset या capture group offset नहीं देता
    • pattern में ^ जोड़े बिना anchored search चलाने की क्षमता की ज़रूरत थी
    • search के दौरान internal synchronization के बिना mutable scratch space को सीधे पास करने की सुविधा माँगी गई
    • stream या rope जैसे non-contiguous haystack पर regex चलाने की क्षमता की भी माँग थी
  • अगर अंदरूनी हिस्सों को अलग version crate के रूप में public किया जाए, तो general-purpose regex API को जटिल बनाए बिना expert API को तेज़ breaking change cycle में प्रयोग किया जा सकता है

fully compiled DFA ने abstraction boundary कैसे तय की

  • regex-automata की शुरुआती प्रेरणा एक fully compiled DFA बनाना, उसे serialize करना, और फिर zero-copy deserialization के साथ search करने वाला minimal runtime देना था
  • शुरुआती regex-automata का उपयोग bstr के Unicode algorithm implementation के लिए DFA बनाने में हुआ
  • DFA बनाते समय regex crate जैसे NFA data structure और compiler की आवश्यकता पड़ी, और यह code जटिल होने पर उसे साझा करने की ज़रूरत बढ़ी
  • शुरुआत में regex-nfa जैसे अलग crate पर विचार हुआ, लेकिन determinization process सहित और भी बहुत-सा code regex और regex-automata के बीच साझा किया जा सकता था
  • abstraction boundary “NFA” से ज़्यादा regex engine के करीब निकली, और अंततः regex-automata को कई engines के संग्रह के रूप में फिर से परिभाषित किया गया
  • long-term plan यह था कि सभी regex engines को regex-automata में रखा जाए और regex crate को उसके ऊपर एक पतला wrapper बनाया जाए

regex-cli से internal structure देखना

  • regex-cli एक program है जिसे regex crate repository में maintain किया जाता है, और यह regex-syntax, regex-automata, regex की विभिन्न APIs तक command-line access देता है
  • इसे निम्न command से install किया जा सकता है
cargo install regex-cli
  • regex-cli debug AST, HIR, literal, Thompson NFA, one-pass DFA, dense DFA, sparse DFA आदि को output कर सकता है
  • Unicode enabled . regex, UTF-8 scalar value को handle करने के लिए कहीं अधिक जटिल Thompson NFA बनाता है, जबकि Unicode disabled (?-u:.) अधिक सरल NFA बनाता है
  • regex-cli find ad-hoc search चला सकता है, और meta engine के साथ multi-pattern search तथा capture group output भी दे सकता है

regex processing data flow

  • Regex::new को दिया गया pattern string पहले Ast में parse होता है
  • Ast को Hir में convert किया जाता है
    • Hir, Ast की तुलना में कम detailed होता है, और conversion के दौरान Unicode case folding तथा Unicode character class references expand होते हैं
  • Hir से दो चीज़ें बनती हैं
    • search optimization में इस्तेमाल होने वाली literal sequence
    • Thompson NFA
  • NFA कई engines बनाने की नींव बनता है
    • PikeVM: parse हो सकने वाले सभी regex को संभालता है और capture group offset report करता है
    • BoundedBacktracker: bounded backtracking के साथ capture group offset report करता है
    • one-pass DFA: सीमित regex में capture group offset तेज़ी से report करता है
    • dense DFA: बहुत तेज़ है, लेकिन केवल full match की शुरुआत/अंत report करता है; इसका construction worst-case O(2^m) time और space ले सकता है
    • lazy DFA: search के दौरान NFA से DFA बनाता है, आम तौर पर full DFA जितना तेज़ होता है और full DFA की exponential construction cost से बचता है
  • इन engines और Prefilter को मिलाकर एक meta regex engine बनाया जाता है, और regex crate इस meta engine का एक पतला wrapper है

लिटरल ऑप्टिमाइज़ेशन

  • लिटरल extraction, regex के अंदर की एक मुख्य optimization है
    • उदाहरण के लिए, (foo|bar|quux)(\s+\w+) के सभी match, foo, bar, quux में से किसी एक से शुरू होते हैं
  • लिटरल महत्वपूर्ण इसलिए हैं क्योंकि एक या कुछ strings के लिए search algorithms बहुत तेज़ होते हैं
    • vector instructions के साथ haystack के कई bytes को एक साथ प्रोसेस किया जा सकता है
    • सामान्य regex matching algorithms को इसी तरह लगातार accelerate करना कठिन है
  • अच्छी तरह optimized substring search, अक्सर सामान्य regex engine से कम-से-कम एक order of magnitude तक तेज़ रही है
  • लिटरल extraction एक heuristic है
    • candidate match की false positive rate को कम करना चाहिए
    • prefilter का पूरे latency पर असर भी कम होना चाहिए
    • दोनों शर्तें haystack पर निर्भर हैं, लेकिन search से पहले haystack का analysis करने पर कुल search time और खराब हो सकता है
  • लिटरल sequence, set नहीं बल्कि ordered sequence है
    • regex crate, Perl-like leftmost-first semantics का पालन करता है, इसलिए | पर commutativity लागू नहीं होती
    • sam|samwise में केवल sam निकाला जा सकता है, लेकिन samwise|sam में दोनों पर विचार किया जाता है
  • single string search के लिए memchr crate का memmem module इस्तेमाल होता है
    • मुख्य algorithm Two-Way है, जिसका worst-case समय O(n) और constant space होता है
    • छोटे needle और haystack के लिए Rabin-Karp इस्तेमाल होता है
    • x86_64 पर generic SIMD variants का उपयोग किया जाता है
  • multiple string search के लिए Hyperscan से port किया गया Teddy मुख्य algorithm के रूप में इस्तेमाल होता है, और कुछ मामलों में Aho-Corasick भी उपयोग होता है

Thompson NFA और optimization

  • regex crate के अंदर का केंद्रीय data structure Thompson NFA है
  • Thompson’s construction, regex की structured representation से O(m) समय में NFA बनाता है, जहाँ m, counted repetition expansion के बाद regex के आकार के अनुपात में होता है
  • NFA को सीधे regex engine के रूप में इस्तेमाल किया जा सकता है, और DFA जैसे दूसरे types में बदलकर अन्य engines की नींव के रूप में भी उपयोग किया जा सकता है
  • नए NFA compiler की मुख्य optimization, epsilon transition को कम करने पर केंद्रित है
    • Thompson NFA का construction time अच्छा होता है, लेकिन यह epsilon transition का बहुत उपयोग करता है
    • epsilon closure की गणना, search या DFA construction के दौरान बार-बार लागत पैदा कर सकती है
  • sparse state optimization, कई range transitions को एक state में व्यक्त करके पहले के कई Split instructions को कम करती है
    • [A-Za-z0-9] जैसी regex में अनावश्यक epsilon transition हटाती है
    • मौजूदा representation में indirection की वजह से cache impact और heap memory बढ़ने की संभावना है
  • minimal UTF-8 automata optimization, बड़े Unicode class में NFA के आकार को काफी कम करती है
    • पुराने byte-oriented NFA में \w, 3,564 states बना सकता था
    • नया compiler, Daciuk’s algorithm का उपयोग करके बहुत कम states और zero epsilon transition वाली संरचना बनाता है
    • compile time cost के कारण reverse NFA का shrink, डिफ़ॉल्ट रूप से disabled है
  • literal trie optimization, zap|z|zapper, abc|xyz जैसी literal alternation में common structure को trie के रूप में compile करके epsilon transition कम करती है
    • leftmost-first semantics को बनाए रखने के लिए match दिखने वाले हर बिंदु पर transition chunks को विभाजित किया जाता है
  • भविष्य के NFA कार्य के रूप में Glushkov NFA और single contiguous allocation storage पर विचार किया जा रहा है
    • Glushkov NFA में epsilon transition नहीं होते, लेकिन compile time complexity अधिक खराब है
    • contiguous allocation, cache friendliness और zero-copy serialization·deserialization की संभावना दे सकता है, लेकिन code complexity और unsafe के उपयोग की संभावना भी है

अलग-अलग regex engines

  • regex-automata के engines, मिलती-जुलती API साझा करते हैं
    • Input: haystack, search range, anchored है या नहीं, early stop है या नहीं को सेट करता है
    • Match: matched byte span और PatternID रखता है
    • MatchError: ऐसी error को दिखाता है जिसमें search result निर्धारित नहीं किया जा सकता

  • PikeVM

    • regex-syntax जो पूरी functionality parse कर सकता है, उसे support करता है, और किसी भी लंबाई के haystack पर काम करता है
    • capture group positions को track करता है, और active states को lock-step में calculate करके worst-case O(m * n) समय की guarantee देता है
    • कई states और capture group positions को track करना पड़ता है, इसलिए performance इसकी मुख्य कमजोरी है
    • regex-automata engines में इसकी एक खास विशेषता है कि यह search के दौरान error return नहीं करता

  • BoundedBacktracker

    • Thompson NFA पर backtracking का उपयोग करता है, लेकिन पहले किए गए काम को दोबारा trace न करना पड़े इसके लिए अतिरिक्त state का उपयोग करता है
    • worst-case O(m * n) समय की guarantee देता है, लेकिन O(m * n) space इस्तेमाल करता है
    • मोटे प्रयोगों में यह आम तौर पर PikeVM से लगभग 2 गुना तेज़ है
    • अगर haystack की लंबाई और regex का आकार configured visited capacity से आगे निकल जाए तो यह fail हो सकता है

  • one-pass DFA

    • सीमित one-pass NFA में capture group offsets को बहुत तेज़ी से report करता है
    • इसे capture group report करने का सबसे तेज़ तरीका माना जाता है
    • केवल anchored search support करता है, और कई regex one-pass नहीं होते
    • Unicode mode में byte level transition overlap की वजह से जो regex one-pass नहीं थे, वे Unicode बंद करने पर one-pass बन सकते हैं

  • fully compiled DFA

    • पूरे match के अंत और शुरुआत को खोजने के लिए forward DFA और reverse DFA, इन दो से मिलकर बना होता है
    • construction worst-case O(2^m) समय और space लेता है, और dense DFA बहुत memory इस्तेमाल करता है
    • full DFA engine, regex crate में डिफ़ॉल्ट रूप से disabled है और perf-dfa-full feature से opt-in करना पड़ता है
    • mutable Cache के बिना काम करता है, और raw bytes के रूप में serialize किया जा सकता है ताकि केवल core वाले environment में भी search runtime इस्तेमाल हो सके

  • hybrid NFA/DFA, lazy DFA

    • full DFA के समान है, लेकिन transition table को search के दौरान बनाता है
    • अगर cache में पहले से calculated transition हो तो उसे reuse करता है, और नहीं होने पर NFA powerset construction से केवल वही transition calculate करता है
    • worst-case search time O(m * n) है, और space construction के समय तय की गई cache capacity से सीमित रहता है
    • सामान्य मामलों में ज़्यादातर states और transitions cache हो जाते हैं, इसलिए औसतन यह O(n) जैसा काम करता है, और वास्तव में कई regex पर full DFA जैसी search performance दिखाता है
    • अगर cache बार-बार भरकर अक्षम हो जाए तो यह error return करता है, और meta engine में आम तौर पर किसी दूसरे engine से retry किया जाता है

meta regex engine की भूमिका

  • meta regex engine कई इंजनों को एक में जोड़ता है और caller को infallible API देने की कोशिश करता है
  • caller को हर search के लिए Cache खुद बनाकर पास करने की ज़रूरत नहीं होती
    • meta engine अंदरूनी thread-safe cache pool को मैनेज करता है
    • synchronization cost से बचना हो तो explicit Cache पास करने वाला lower-level API भी दिया जाता है
  • regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet सभी meta engine के thin wrapper हैं
  • meta engine की आंतरिक strategy मोटे तौर पर इस तरह है
    • अगर regular expression engine के बिना सिर्फ single या multiple substring search से काम हो सकता है, तो NFA बनाना भी टाल दिया जाता है
    • जहाँ संभव हो, prefix literal sequence निकालकर उसे Prefilter की तरह इस्तेमाल किया जाता है
    • अगर prefix उपयुक्त न हो, तो reverse anchored, reverse suffix, reverse inner optimization आज़माए जाते हैं
    • बाकी मामलों में PikeVM, bounded backtracker, one-pass DFA, lazy DFA, full DFA शामिल करने वाली core strategy पर fallback किया जाता है
  • पूरी strategy को दो वाक्यों में समेटा जा सकता है
    • जहाँ तक संभव हो literal search करो
    • जहाँ तक संभव हो PikeVM के उपयोग से बचो
  • reverse suffix और reverse inner optimization गलत तरीके से इस्तेमाल होने पर haystack के आकार के सापेक्ष worst-case O(m * n^2) बन सकते हैं
    • meta engine यह पहचान लेता है कि reverse scan पिछली suffix match के अंत से आगे निकलने वाला है, और समय जटिलता की गारंटी बनाए रखने के लिए core strategy पर fallback कर जाता है

RE2 से अंतर

  • regex crate और RE2 में कई समानताएँ हैं
    • RE2 में भी PikeVM के समकक्ष NFA, bitstate backtracker, one-pass NFA, lazy DFA, और कई इंजनों को मिलाकर चलने वाली संरचना है
    • ऊपर के इंजनों में RE2 में जो नहीं है, वह fully compiled DFA है
  • मुख्य अंतर इस प्रकार हैं
    • RE2 leftmost-first के अलावा POSIX शैली के leftmost-longest semantics को भी option के रूप में support करता है
    • RE2 का Unicode support अधिक सीमित है, और \w, \s, \d, \b को Unicode definitions के अनुसार इस्तेमाल करने का option नहीं है
    • RE2 में character class set operation में union के अलावा बाकी support सीमित है
    • संभव है कि RE2 का PikeVM memory के लिहाज़ से अधिक efficient हो
    • RE2 की literal optimization सीमित है, जबकि regex crate अधिक literal optimization करता है
    • RE2 का lazy DFA कई threads के बीच वही transition cache साझा करता है, इसलिए synchronization चाहिए; जबकि regex crate thread-वार अलग cache मांगता है, इसलिए अधिक memory इस्तेमाल करता है
    • regex crate regex-syntax और regex-automata को अलग versioned library के रूप में प्रकाशित करता है, लेकिन RE2 ऐसा support नहीं करता
    • regex-automata सभी इंजनों में first-class multi-pattern regex support देता है, और हर matched pattern के match व capture group offset भी report कर सकता है

test strategy और benchmark

  • नई test strategy में अंदरूनी इंजनों को स्वतंत्र first-class API बनाया गया है और हर engine को सीधे test किया जाता है
  • सभी regular expression tests TOML files में निर्दिष्ट होते हैं
  • regex-test crate TOML tests को पढ़कर structured representation में बदलता है
  • हर engine configuration के लिए एक Rust unit test रखा जाता है, और उस engine पर लागू होने वाले सभी TOML tests चलाए जाते हैं
  • क्योंकि Rust unit test framework extensible नहीं है, इसलिए specific test filtering के लिए अपना environment variable infrastructure जोड़ा गया
  • सिर्फ regex-automata में ही 450 से अधिक documentation tests हैं
  • regex 1.9 की तैयारी के दौरान कई fuzz testing target भी जोड़े गए, और Addison Crump की मदद से कुछ bugs मिले
  • benchmark rebar नाम के regex barometer के रूप में प्रकाशित हैं
    • rebar सिर्फ regex crate ही नहीं, कई regular expression engines का benchmark करता है
    • 242 benchmarks में search time के आधार पर regex 1.9, regex 1.7.3 से औसतन 1.5 गुना तेज़ है
    • regular expression build करने का समय कुछ हद तक regress हुआ है
    • 1.8 एक transition release था जिसमें कुछ migration work शामिल था, इसलिए comparison baseline के रूप में 1.7 का इस्तेमाल किया गया

लागत और हल्के विकल्प

  • इस rewrite में पिछले कुछ वर्षों के दौरान लेखक का अधिकांश free time लगा, और ripgrep जैसे projects कुछ समय तक release नहीं हो पाए
  • पुन: उपयोग योग्य public abstraction, internal-only abstraction की तुलना में आमतौर पर अधिक code माँगते हैं
    • नतीजतन binary size और compile time बढ़ते हैं
  • जब internal engine API को अलग version के रूप में public किया गया, तब API तोड़ने के लिए regex-automata की उपयुक्त breaking change release की ज़रूरत पड़ती है
  • लागत कम करने के लिए दो कदम लागू किए गए
    • fully compiled DFA engine को default रूप से disabled रखा गया और opt-in feature बनाया गया
    • regex-lite को नए crate के रूप में जारी किया गया
  • regex-lite का लक्ष्य regex crate का लगभग drop-in replacement बनना है, लेकिन इसका फोकस binary size और compile time optimization पर है
    • यह Unicode और performance से जुड़ी कुछ सुविधाएँ छोड़ देता है
    • O(m * n) समय जटिलता की गारंटी बरकरार रखता है
    • इसकी dependencies 0 हैं, और इसमें अपना regular expression parser शामिल है, इसलिए यह regex crate के साथ code share नहीं करता
  • regex-lite अभी एक experimental mitigation है, लेकिन यह दिखाता है कि regex crate की feature settings में optimization और Unicode सुविधाएँ बंद करने पर भी binary size और compile time के मामले में regex-lite के करीब पहुँचना मुश्किल है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-07-06
Hacker News की राय

  • सिर्फ सरसरी तौर पर देखने पर भी Rust regex crate सच में प्रभावशाली है
    BurntSushi ने बहुत-सी शानदार चीजें बनाई हैं, लेकिन Rust का regex crate तो लेजेंडरी है, और Rust ecosystem के लिए यह बड़ा वरदान है कि उसके पास बहुत पहले से ही तेज़ और इस्तेमाल में आसान regular expression library रही है
    Russ Cox की regular expression पर लेख-श्रृंखला भी बेहतरीन है; जब regular expressions मुझे theory और practice के एकदम सही संगम जैसे लगने लगे थे, तब एक गर्मी में regular expression engine बनाने के लिए मैंने उनका सहारा लिया था
    इस लेख में testing में हुए और गहरे बदलाव भी दिलचस्प हैं, और ecosystem के लिए इतने अहम crate पर ऐसे गहरे विषयों की व्याख्या मिलना सराहनीय है
    regular expressions कभी-कभी पढ़ने में मुश्किल होते हैं और email validation जैसी चीजों में उनका दुरुपयोग भी होता है, लेकिन लगभग हर भाषा में वे सबसे घने/कंसाइज़ tools में से एक हैं
    व्यावहारिक किताब के तौर पर मैं Jeffrey Friedl की Mastering Regular Expressions को ही अच्छी तरह जानता हूं, और theory वाली तरफ compiler books इसे कवर करती हैं; Dragon Book भी implementation के नजरिए से ठीक थी। regular expressions पर दूसरी किताबों की सिफारिशें जानना चाहूंगा

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... और https://kean.blog/post/lets-build-regex simplified regular expression engine implementation के introduction के लिए शानदार हैं
      regular expression के लिए non-deterministic finite automaton बनाते हैं, और फिर उस resulting directed graph में search करके अगर final state से संबंधित vertex तक पहुंचना संभव हो तो उसे match माना जाता है
      regular expressions इस्तेमाल करने वाला कोई भी व्यक्ति इस exercise से समझ सकता है कि इसमें अपेक्षा से कम जादू है, और NFA के ऊपर गेंदों को इधर-उधर उछलते सोचें तो production में आखिरकार मिलने वाले catastrophic backtracking bugs का भी भौतिक अर्थ बनने लगता है
      मूल लेख के संदर्भ में, https://github.com/rust-lang/regex/issues/822 में BurntSushi की आखिरी टिप्पणी niche API वाले paragraph https://blog.burntsushi.net/regex-internals/#problem-request... में उपयोगी context जोड़ती है। कई regular expressions को text में एक साथ search करना बहुत जटिल है, लेकिन बहुत उपयोगी भी है, इसलिए इस pattern से community क्या बनाएगी, यह देखने की उत्सुकता है
    • parsing जैसी tasks में regular expressions के चमकने का एक classic मामला अलग-अलग delimiter वाले formats को handle करना है
      उदाहरण के लिए header:field1,field2,field3"data"hash जैसे fixed number of fields वाले format, या suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2 जैसे ऐसे format जिनमें ज्यादातर elements optional हों, उनमें split जैसे basic tools काफी नहीं पड़ते और regular expressions अच्छी तरह fit होते हैं
      regular expressions जल्दी पढ़ने में मुश्किल क्यों हो जाते हैं, वजह भी यही है। एक ही regular expression में fields के बीच delimiters, हर field की validity, और कौन-सा field optional है—सब घुल-मिल जाता है
      ये असल में तीन अलग concerns हैं, लेकिन ज्यादातर regular expression APIs इन्हें step-by-step अलग करने नहीं देतीं और सब कुछ मिलाकर सिर्फ एक string लेती हैं
    • सोच रहा हूं कि क्या यह RegEx library ज्यादातर JavaScript implementations की तरह JIT इस्तेमाल करती है। अगर नहीं, तो यह ऐसा मामला हो सकता है जहां JavaScript Rust को हरा दे
    • हाल ही में थोड़ा RegEx काम करते हुए मैंने यह लेख सरसरी तौर पर देखा, और इस्तेमाल की गई भाषा दूसरे engines के उलट errors return नहीं करती थी, इसलिए लगा कि यह PikeVM इस्तेमाल कर रही होगी
      भाषा की constraints और copyright protection की स्थिति के कारण मुझे RegEx functionality खुद नए सिरे से बनानी पड़ी, और regular expressions सचमुच कभी-कभी voodoo जैसे लगते हैं
      मुझे नहीं पता दूसरे engines कितनी बार इस्तेमाल होते हैं, लेकिन अगर बहुत-सी programming languages PikeVM इस्तेमाल करती हैं, तो समझ आता है कि Google ने servers के लिए अपना OS क्यों बनाया और कुछ situations में कुछ clock cycles भी बचाने के लिए तेज़ engine लगाने की कोशिश क्यों की
      search string में बस कुछ characters जोड़ने से भी pattern matching काफी धीमी हो जाती है, यह मुझे अच्छी तरह पता है। “छोटे पैसे संभालो, बड़े पैसे अपने-आप संभल जाएंगे” वाली कहावत RegEx और clock cycles पर भी अच्छी बैठती है, और 90s में प्रति सेकंड लाखों records process करने वाली बातचीतों को याद करें तो लगता है इसने कुछ coders को बहुत अमीर बना दिया होगा
    • मेरी सबसे बड़ी शिकायत regular expression dialects के छोटे-छोटे फर्क हैं
      खासकर dialect और context के हिसाब से quotes handle करने या expression खत्म करने के तरीके इतने अलग होते हैं कि याद करने की कोशिश छोड़कर जरूरत पड़ने पर हर बार examples search करने लगता हूं

  • ActiveState में, कॉलेज से अभी-अभी निकले एक colleague के साथ मुझे Komodo editor के लिए regular expression debugger बनाने का काम मिला था
    हमने legendary Perl expert Mark Jason Dominus को hire किया ताकि वे Perl regular expression engine में hooks डालें, और उन hooks को UI में expose करके users को regular expression execution step-by-step देखने दें
    आजकल web-based tools ज्यादा बेहतर हैं, लेकिन 2001 में Komodo का Rx Debugger cutting-edge था और उस पर काम करना भी काफी मजेदार था

    • पहले कभी मुझे offline regular expression debugger की जरूरत पड़ी थी
      मैं air-gapped network से deal कर रहा था, इसलिए जिन लोगों को tool इस्तेमाल करना था वे online sites access नहीं कर सकते थे, और किसी भी design में work data को online tool में डालने का विचार तक allowed नहीं था
      लेकिन ज्यादातर effort online tools पर केंद्रित है, और offline tools https://regex101.com/ जैसी चीजों की तुलना में दुर्लभ और कमजोर हैं
    • इस काम के लिए इस्तेमाल करने लायक किसी specific web-based tool की सिफारिश जानना चाहूंगा

  • मुझे जिज्ञासा है कि क्या इसे strings के बजाय lists पर भी इस्तेमाल किया जा सकता है
    characters की list को खोजने और बदलने के लिए तो शक्तिशाली tools हैं, लेकिन जैसे ही वह numbers या dates की list बन जाती है, सब कुछ गायब हो जाता है—यह हमेशा झुंझलाहट भरा रहा है
    उदाहरण के लिए, अगर login attempt dates की list में 5 या उससे ज्यादा failures के बाद success आने वाली सभी sequences ढूंढनी हों, तो regex से यह आसान है, लेकिन असल में आपको खुद loop, flags और temporary lists बनानी पड़ती हैं
    list को string में बदलकर process करने और फिर वापस बदलने का रास्ता हो सकता है, लेकिन उसकी कमियां साफ हैं। भले ही वह string-based regex जितना तेज न हो, मुझे समझ नहीं आता कि arbitrary list types के लिए regex क्यों नहीं होना चाहिए
    पहले बनाया हुआ Python prototype भी मिला: https://github.com/boppreh/listregex
    यह बहुत धीमा है, लेकिन API experiment के तौर पर संतोषजनक है, और pattern inversion, intersection, matching pairs जैसे tools भी देता है जो regex में नहीं होते

    • नहीं हो सकता। यह regex library string search से गहराई से जुड़ी है, और यह जानबूझकर लिया गया design decision है
      ऐसे regex engine में generic alphabet जोड़ना शुरुआत से ही अव्यावहारिक है। खासकर API design और मुख्य use cases की performance को नुकसान न पहुंचाने वाला तरीका व्यावहारिक रूप से बहुत कठिन है
      अगर performance की चिंता न हो तो ऐसा regex engine बनाना मुश्किल नहीं है। उदाहरण के लिए, मैंने जो regex-lite crate प्रकाशित किया है उसे लेकर आप जितना चाहें उतना generic बना सकते हैं, और इस प्रक्रिया में आपको दिलचस्प चुनौतियां मिलेंगी
      ऐसा है कि यह बिल्कुल मौजूद ही नहीं है, ऐसा भी नहीं। लोगों ने बनाने की कोशिश की है[1]। हालांकि वे इसकी सामान्य उपयोगिता को कुछ ज्यादा बढ़ा-चढ़ाकर बताते हैं, इसलिए आम तौर पर इसे बड़ा traction नहीं मिलता लगता :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • C++ standard library का std::basic_regex user-defined character types के लिए template class expose करके ऐसी कोशिश करता है: https://en.cppreference.com/w/cpp/regex/basic_regex
      आप एक trait class दे सकते हैं जो user-defined “character” के लिए जरूरी behavior define करती है
      लेकिन performance काफी गिर जाती है, और इसके arbitrary non-character objects को user-defined std::basic_string में डालने जितना ही अच्छी तरह काम करने की संभावना है
    • values की sliding window पर match करने वाली API किसी न किसी तरह define करनी होगी
      यह असंभव नहीं है, लेकिन ज्यादातर languages के पास इसके लिए अच्छा interface नहीं है

  • code या text files में कुछ ढूंढते समय मैं Ripgrep रोज इस्तेमाल करता हूं, और Windows, Linux, Mac, VSCode, Vim—जहां भी इस्तेमाल करता हूं, हर बार आभारी होता हूं
    यह उन software में से एक है जिसने मेरी जिंदगी और काम करने का तरीका बदल दिया
    जब मजबूरी में grep इस्तेमाल करना पड़ता है, तो ऐसा लगता है जैसे उस दौर में लौट गया हूं जब सब कुछ single-core CPU पर चलता था और data धीमी PATA/IDE spinning hard disk पर होता था
    BurntSushi महान programmers के बीच भरपूर सम्मान के हकदार हैं

    • ripgrep की एक lineage है। उससे पहले ag था, उससे पहले ack था, और इन सभी ने साधारण grep से कहीं बेहतर interface देने की कोशिश की

  • काम की एक समस्या के लिए बहुत लंबे regex के 1 करोड़ से ज्यादा items से RegexSet बनाना पड़ा था
    कोई भी engine default state में इसे संभाल नहीं पाया, और Rust का RegexSet भी default values के साथ पर्याप्त नहीं था
    फिर भी regex-automata और regex-syntax का उपयोग करना और code पढ़ना 2018 में भी बहुत उपयोगी learning material था
    आखिरकार work project ने Lucene API को model बनाया, लेकिन यह basic foundations regex crates से सीखने के बाद ही संभव हुआ

    • 1 करोड़ regex बहुत बड़ा scale है। Aho-Corasick भी 1 करोड़ literals को बस मुश्किल से संभाल पाता है
      आगे का काम regex engine को ज्यादा patterns पर बेहतर scale कराने का है। अभी तो यह 1 करोड़ regex से बहुत पहले ही टूट जाएगा, और यह लक्ष्य सच में संभव है या नहीं, इस पर भी भरोसा करना मुश्किल है
      फिर भी यह मौजूदा स्थिति से निश्चित रूप से बेहतर हो सकता है
      बेशक multi-pattern search में Hyperscan असल में gold standard जैसा है। हालांकि 1 करोड़ patterns को यह कितना अच्छी तरह handle करेगा, पता नहीं
    • आपने शुरुआत में details नहीं लिखीं, तो जवाब शायद “नहीं” होगा, लेकिन अगर संभव हो तो जानना चाहूंगा कि वह समस्या या project क्या था—क्या आप और share कर सकते हैं

  • पहले regex-automata crate के साथ experiment किया था, और यह एकमात्र library थी जिसे text editor में इस्तेमाल किया जा सकता था क्योंकि internal DFA तक सीधे access मिल जाता था
    सामान्य regex library APIs input को एक single contiguous string मानती हैं, लेकिन यह तरीका किसी भी text data structure के साथ compatible है

  • मैं regex-automata crate, वह भी शुरुआती 0.2.0 release इस्तेमाल करने वाला code लिख रहा था, तभी यह लेख आया
    लगता है अब यह देखने का समय है कि क्या नई internal structure को फिर से खंगालना पड़ेगा
    अभी article नहीं पढ़ा है, लेकिन यह बहुत दिलचस्प और timing के लिहाज से बेहद सटीक लगता है
    कुछ मिनट बाद देखा तो जवाब “हो सकता है” के करीब था, लेकिन formal release होने की वजह से शायद code को काफी simplify किया जा सकेगा
    फिर करीब 10 मिनट बाद यह काफी painless निकला और नया Builder::patch method पूरा upgrade था
    P.S. के तौर पर, मैं अभी भी आपके सभी GitHub repositories से blocked हूं, और यह देखते हुए कि कई crates व्यापक रूप से इस्तेमाल होते हैं, मुझे यह थोड़ा unfair लगता है। मूल घटना याद नहीं है। regex crate खुद अब शायद rust-lang organization के नीचे है, लेकिन अब भी कुछ चीजों के साथ interact नहीं कर सकता

    • regex-automata 0.2.0 docs में इस बारे में बड़ी warning थी, और 0.1 इस्तेमाल करने की जोरदार recommendation थी: https://docs.rs/regex-automata/0.2.0/regex_automata/
      मुझे भी मूल घटना याद नहीं है। कई वजहों से मैं बहुत लोगों को block करता हूं, लेकिन अब block हटा दिया है

  • BioJulia ने compile time पर arbitrary Julia code डालने में सक्षम pure Julia regex engine Automa.jl जारी किया था
    मैं यह कमतर नहीं आंकना चाहता कि Rust का regex, Automa से कहीं ज़्यादा advanced है, लेकिन regex internals को library के रूप में expose करने का यह पहला उदाहरण है—इस बात से सहमत होना मुश्किल है

    • यह दो अलग-अलग चीज़ों जैसा लगता है
      उदाहरण के लिए, PCRE2 में “callout” support है, जो कही गई बात से मिलता-जुलता लगता है: https://www.pcre.org/current/doc/html/pcre2callout.html
      ragel या re2c जैसी चीज़ें भी इसी तरह का काम करती रही हैं
      इस ब्लॉग में जिस बात की चर्चा है, वह regex library के अपने internals को निकालकर अलग से versioned library बनाना और दूसरों को उन्हें compose करने देना है
      backtracker के लिए यह तरीका आम तौर पर कम स्वाभाविक है, क्योंकि engine में अक्सर सिर्फ एक backtracker होता है, लेकिन automaton-based libraries में कई engines को अलग-अलग तरीकों से combine करना आम बात है
      फिर भी backtracker भी असल में ऐसी चीज़ें expose कर सकते हैं जिन्हें वे आम तौर पर expose नहीं करते, जैसे regex parser या AST