> (1) There are 5.125 bytes in Unicode, not four.
> (2) I think the above would suffer from the same problem as one common
> suggestion, two-level bitmaps (though I think the above would suffer
> less, being of finer granularity): the problem is that a lot of
> space is wasted, since the "usage patterns" of Unicode character
> classes tend to be rather scattered and irregular. Yes, I see
> that you said: "only the arrays that we actually used would be
> allocated to save space"-- which reads to me: much complicated
> logic both in creation and access to make the data
> structure *look*
> simple. I'm a firm believer in getting the data structures right,
> after which the code to access them almost writes itself.
>
> I would suggest the inversion lists for the first try. As long as
> character classes are not very dynamic once they have been created
> (and at least traditionally that has been the case), inversion lists
> should work reasonably well.
My proposal is we should use mix method. The Unicode standard class,
such as \p{IsLu}, can be handled by a standard splitbin table. Please
see Java java.lang.Character or Python unicodedata_db.h. I did
measurement on it, to handle all unicode category, simple casing,
and decimal digit value, I need about 23KB table for Unicode 3.1
(0x0 to 0x10FFFF), about 15KB for (0x0 to 0xFFFF).
For simple character class, such as [\p{IsLu}\p{InGreak}], the regex
does not need to emit optimized bitmap. Instead, the regex just generate
an union, the first one will use standard unicode category lookup, the
second one is a simple range.
If user mandate to use fast bitmap, and the character class is not
extremely complicated, we will only probably need about several K for
each char class.
> > As for character encodings, we're forcing everything to UTF-32 in
> > regular expressions. No exceptions. If you use a string in a regex,
> > it'll be transcoded. I honestly can't think of a better way to
> > guarantee efficient string indexing.
I don't think UTF-32 will save you much. The unicode case map is variable
length, combining character, canonical equivalence, and many other thing
will require variable length mapping. For example, if I only want to
parse /[0-9]+/, why you want to convert everything to UTF-32. Most of
time, the regcomp() can find out whether this regexp will need complicated
preprocessing. Another example, if I want to search for /resume/e,
(equivalent matching), the regex engine can normalize the case, fully
decompose input string, strip off any combining character, and do 8-bit
Boyer-Moore search. I bet it will be simpler and faster than using UTF-32.
(BTW, the equivalent matching means match English spelling against French
spell, disregarding diacritics.)
I think we should explore more choices and do some experiments.
Hong
