BurntSushi
commented
10 months ago I confess that I am somewhat interested in supporting this. In particular, I've found that the existing support for class set operations (union, complement, intersection, difference) to be enormously useful when it comes to dealing with Unicode character classes. I'm really glad the regex crate has that support (not many regex engines do, notably PCRE and RE2 both lack it), because it makes some things expressible that would otherwise be quite difficult to do. I feel like this might fall into a similar bucket, and folks have filed issues about trying to match emoji with regex and it not working like they'd expect.
I have two general threads of concern here.
Firstly, based on the reading I've done (see the end of this comment for roughly what I read), it seems clear to me that the driving reason behind supporting "properties of strings" is Emoji. That is, I'm sure it's no coincidence that every single string property required by UTS#18 S2.7 is related to emoji. Therefore, I want to make sure that we can hit the Emoji use case. I haven't actually read UTS#51 in full detail yet, but there are aspects I don't yet understand. One is whether matching emoji correctly requires something other than a "simple" regex. For example, UTS#51 specifically provides a regex for matching possible emoji. That regex is already supported today by the regex crate (quite intentionally):
$ cat ~/tmp/emoji.regex
(?x)\p{RI} \p{RI}
| \p{Emoji}
( \p{EMod}
| \x{FE0F} \x{20E3}?
| [\x{E0020}-\x{E007E}]+ \x{E007F}
)?
(\x{200D}
( \p{RI} \p{RI}
| \p{Emoji}
( \p{EMod}
| \x{FE0F} \x{20E3}?
| [\x{E0020}-\x{E007E}]+ \x{E007F}
)?
)
)*
$ regex-cli find match meta -p "$(cat ~/tmp/emoji.regex)" -y 'β½'
parse time: 138.955Β΅s
translate time: 126.662Β΅s
build meta time: 1.446184ms
search time: 145.104Β΅s
total matches: 1
0:0:3:β½
$ regex-cli find match meta -p "$(cat ~/tmp/emoji.regex)" -y 'π¨πΎββοΈ'
parse time: 143.247Β΅s
translate time: 104.561Β΅s
build meta time: 1.455044ms
search time: 304.674Β΅s
total matches: 1
0:0:17:π¨πΎββοΈBut...
$ regex-cli find match meta -p "$(cat ~/tmp/emoji.regex)" -y '5'
parse time: 125.205Β΅s
translate time: 105.963Β΅s
build meta time: 1.433962ms
search time: 123.723Β΅s
total matches: 1
0:0:1:5So clearly the "possible" part here is rather relevant, since the regex matches ASCII digits. Because I haven't read UTS#51 in full yet, I don't know what extra validity checking steps are needed here. And in general, I would want to know this before we start on adding support for this because I want to make sure that matching emoji is actually feasible to do. That is, if we had properties of strings, how would \p{RGI_Emoji} be implemented? Is it literally just a table of strings? If so, isn't that impractically large?
I'd also like to point out how long it takes to build the regex above. It's already at 1.5ms. I'm sure aspects of that could be further optimized, but I don't see it getting much better. In particular, large Unicode classes add a lot of overhead to regex compilation. Will properties of strings be even worse? If so, how much worse? I feel like big Unicode classes are already pushing the limits of what is acceptable and I worry that big Unicode sets of strings might be even worse.
The second general concern I have is implementation. While you astutely point out that the regex crate kind of already supports string classes by virtue of the fact that UTF-8 is a variable width encoding, this doesn't actually help too much. It's true that building the NFA shouldn't be an issue here, but there really is some significant issues with how the implementation would be adapted. I believe the fundamental issue here is that while UTF-8 is a variable width encoding, that isn't made manifest until the NFA is constructed. Before that, particularly the HIR, UTF-8 isn't really a thing. Instead, the HIR is a logical description of a regex matching characters, where a character can either be a single byte or a single codepoint. And the definition of character (among other things) can be changed by toggling Unicode mode via the u flag in the pattern. In particular, notice that character classes are limited only to characters implied by the current mode:
$ regex-cli debug hir '(?-u)β'
parse time: 43.355Β΅s
translate time: 21.032Β΅s
Literal(
"β",
)
$ regex-cli debug hir '(?-u)[β]'
failed to translate pattern 0 to HIR: '(?-u)[β]': failed to translate pattern: regex parse error:
(?-u)[β]
^
error: Unicode not allowed hereThere's a reason why this restriction exists, because mixing up what it means to be a "character" within a single character class is tricky and would require significant surgery to how character classes in the HIR are represented. Evolving character classes to arbitrary finite sets of strings will thus require significant surgery as well.
The place where this really comes up is in the implementation of Unicode character class set operations. You don't need to read it in depth, but the key fact to understand is that it is tightly coupled to the concept of Unicode codepoint ranges. (That is, a Vec<RangeInclusive<u32>>, where the ranges are sorted, not overlapping and not adjacent.)
My supsicion is that all of this would need to be completely gutted and rethought to account for arbitrary sets of finite strings.
The pain doesn't stop there unfortunately. The lowering from an HIR to an NFA (where UTF-8 is made manifest) also exploits the fact that classes are just ranges of characters. This is also where a lot of the time spent compiling large Unicode classes is spent. I'm nearly certain that the existing technique used, Daciuk's algorithm, probably cannot be easily adapted to finite sets of strings? Daciuk's algorithm requires that the elements in the set are sorted lexicographically, but UTS#18 requires that \q{lit1 | lit2 | ... | litN} has its literals sorted such that the longest matches first, which might conflict with the lexicographic ordering requirement. It's unclear to me whether some modification could make it work, but if Daciuk's algorithm doesn't work, then compiling finite sets of strings to an NFA will require a different path. That isn't a huge problem (as those paths already exist), but it will be more expensive both in terms of time, memory and match speed.
It's essentially a fancy wrapper around
HashSet<String>.
Logically, yes. But that won't work as an implementation because it would require explicitly representing every codepoint in a class as a distinct element in a HashSet. Performance wise, that's a non-starter because it is very very common to have sets of codepoints with 100,000 codepoints.
Additional reading:
- https://unicode.org/reports/tr18/#Character_Ranges_with_Strings
- https://unicode.org/reports/tr18/#Resolving_Character_Ranges_with_Strings
- https://unicode.org/reports/tr18/#Notation_for_Properties_of_Strings
- https://v8.dev/features/regexp-v-flag
- https://github.com/tc39/proposal-regexp-v-flag
- https://www.unicode.org/reports/tr51/
Note: I found it interesting that /sam|samwise/gv and /[\q{sam|samwise}]/gv do not have the same match semantics! The former will match sam in samwise, but the latter will match samwise. This is explicitly called out in UTS#18 S2.2.1:
In implementing Character Classes with strings, the expression /[a-m \q{ch|chh|rr|} Ξ²-ΞΎ]/ should behave as the alternation /(chh | ch | rr | [a-mΞ²-ΞΎ] | )/. Note that such an alternation must have the multi-code point strings ordered as longest-first to work correctly in arbitrary regex engines, because some regex engines try the leftmost matching alternative first. Therefore it does not work to have shorter strings first. The exception is where those shorter strings are not initial substrings of longer strings.
CAD97
ECMAScript RegExp supports an interesting feature: v-mode enables
\pto match string properties (e.g.\p{RGI_Emoji_Flag_Sequence}, roughly\p{Regional_Indicator}{2}), allows[]character classes to match finite-length strings, and adds the\q{regexp}escape for writing "string literals" in character classes (a nested regex expression where the only valid syntax is literals, escaped literals, and|disjunction).This support is quite interesting because it allows doing set operations on (finite) sets of (finite) strings (e.g. grapheme clusters / emoji), which can enable matching patterns that might otherwise be achieved with lookahead, e.g.
^[\p{RGI_Emoji_Flag_Sequence}--\q{πΊπΈ|π¨π³|π·πΊ|π¬π§|π«π·}]$versus^(?!πΊπΈ|π¨π³|π·πΊ|π¬π§|π«π·)\p{Regional_Indicator}{2}$(example from MDN). This functionality is required for implementing things such as the UAX#31 Emoji Profile for identifiers, which "requires the use of character sequences, rather than individual code points, in the sets Start and Continue defined by UAX31-D1."I don't think the regex crate particularly needs to be carrying around additional Unicode tables[^icu4x] for extended
\p, but\qseems somewhat reasonably straightforward to support without impacting users who don't use it (modulo some code size / compile time) and makes good chunks of the problem space at least possible to address, if still annoying[^gen]. Because\qis so restricted, it would even be sufficient to not permit alternation within the\qand require writing multiple\qinstead, e.g. making the prior regex^[\p{RGI_Emoji_Flag_Sequence}--[\q{πΊπΈ}\q{π¨π³}\q{π·πΊ}\q{π¬π§}\q{π«π·}]]$, at no loss of expressiveness, just convenience.[^icu4x]: At least not until such a day as icu4x allows it to be plausible for other crates to share the same underlying tables and/or for the binary package to have some control over what tables are built into the executable. Along that line,
\pwould be quite interesting β probably something like afn(&self, &str) -> Option<impl ExactSizeIterator<Item=&str>>callback, to handle v-mode string sets, with a fast path for CodePointInversionLists β but that's drifting far off topic. [^gen]: Listing out each string in the relevant sets in|-delimited lists, oh my.Is it possible that the regex crate could someday support
\qin character classes? I do understand it could be a significant chunk of extra work to allow classes to match longer strings. Although, on the other hand, since sets already need to handle UTF-8's variable 1..=4 byte length codepoint encoding, generalizing that to 1.. bytes might not be completely different. And while that kind of processing could be done, it doesn't need to be for what is, ultimately, a quite niche feature, and is ultimately (after resolving set operations and longest-first ordering) no different from regular top-level alternation.Concrete changes
ast::ClassSetItemvariant for\qa. consisting of anAlternationofConcatofLiteral; or b. which is aLiteralStringstructured likeLiteral, and\q{one|two}is actually two of them, e.g. roughly[LiteralString { span: "\q{one", s: "one" }, LiteralString { span: "|two}", s: "two" }].\q{introduces a string set withmacro_rules!-ish syntax\q{ $( $($lit:Literal)* )|* }. Encountering any meta character except a literal escape is an error.\qinside a negated bracketed class is an error.hir::Classvariant for\q, i.e. aClassStrings. It can't be negated, but it can beunioned,intersected,differenced, andsymmetric_differenced. It's essentially a fancy wrapper aroundHashSet<String>.\qends up beingClassStrings.If the general idea seems sound, I'm willing to try my hand at implementing
\q(to be transparent to HIR, thus invisible to regex-automata).References
RegExp.prototype.unicodeSets\qdocumentation)