Character classes for Unicode-aware lexers and regex engines: a faster, smaller Set.Make (Uchar).

Elements are Unicode scalar values in the sense of Uchar.t: codepoints 0 .. max_codepoint excluding the surrogate block 0xD800 .. 0xDFFF, which exists only as a UTF-16 encoding mechanism and cannot occur in well-formed text. Noncharacters such as U+FFFE are ordinary scalar values and are included.

Every function taking a raw int codepoint to build or update a set validates it, raising Invalid_argument on a surrogate or on a value outside 0 .. max_codepoint. add, remove, add_range and remove_range validate before the membership test, so remove t 0xD800 raises rather than returning t unchanged. The _char and _uchar families cannot raise, their arguments being scalar values already.

Queries go the other way: mem, next_elt_opt, prev_elt_opt, Lookup.mem and Partition.block_of_opt take any int and answer, reading a surrogate or an out-of-range value as one the set does not contain.

Largest valid codepoint, 0x10FFFF.

The empty set.

The set of all Unicode scalar values: 0 .. 0xD7FF and 0xE000 .. max_codepoint.

singleton cp is the set containing exactly cp.

singleton_char c is singleton (Char.code c).

singleton_uchar u is singleton (Uchar.to_int u). A Uchar.t is a scalar value by construction, so none of the _uchar functions can raise.

range ~lo ~hi is the set of scalar values from lo to hi inclusive; empty if lo > hi. Both bounds are validated (and must not be surrogates) even when the result is empty. A range straddling the surrogate block is split around it, so range ~lo:0xD000 ~hi:0xF000 contains 0xD000 .. 0xD7FF and 0xE000 .. 0xF000. An endpoint landing inside the block raises, so range ~lo:0xD000 ~hi:0xD900 is an error and a caller slicing arbitrary spans has to snap its own bounds clear.

range_char ~lo ~hi is range ~lo:(Char.code lo) ~hi:(Char.code hi).

of_list cps is the set of the given codepoints. Duplicates are allowed; order is irrelevant. O(n log n).

range_uchar ~lo ~hi is range on the two scalar values.

of_char_list cs is of_list (List.map Char.code cs).

of_uchar_list us is of_list (List.map Uchar.to_int us). O(n log n).

of_seq s is the set of the codepoints of s. O(n log n).

of_utf_8_string s is the set of scalar values occurring in s. Malformed bytes decode to U+FFFD following String.get_utf_8_uchar, and so contribute U+FFFD to the result rather than raising.

of_intervals pairs is the union of the inclusive ranges (lo, hi) in pairs. Pairs may be unsorted, overlapping, or adjacent; pairs with lo > hi are ignored; bounds are validated and split around the surrogate block like range. O(n log n). Intended for tables of literals such as generated Unicode property data.

Compile t into a Lookup.t. Costs a pass over the pages up to the largest member, so compile once and reuse; pages that come out identical share one leaf, which is what keeps the pool proportional to the set.

ascii_table s is a 256-byte table for the ASCII fast path of a UTF-8 inner loop: tbl.[b] <> '\000' tests membership of byte b directly. Bytes 0x80..0xFF (UTF-8 lead/continuation bytes, not characters) map to false, so the raw input byte indexes the table with no masking; route multi-byte sequences through Lookup.mem_uchar on the decoded scalar instead.

of_packed_string s decodes a string produced by to_packed_string, and accepts exactly what that function emits: a length that is a multiple of six, and intervals with lo <= hi, in range, clear of the surrogate block, in increasing order and separated by at least one codepoint. Anything else raises Invalid_argument, adjacent intervals such as 1..10 and 11..20 included, canonical form having written them as one.

of_packed_string returning None instead of raising, for decoding data from an untrusted source.

to_packed_string t encodes the canonical intervals of t, lowest first, each endpoint as three big-endian bytes and lo before hi, so the result is 6 * num_intervals t bytes. Inverse of of_packed_string.

union t1 t2 is the set of scalar values in either.

inter t1 t2 is the set of scalar values in both.

diff t ~remove is the set of scalar values in t but not in remove.

comp t is diff all ~remove:t.

Symmetric difference: the values in exactly one of the two. One merge over the endpoints of both, like union and inter.

union_list ts is the union of all of ts, and empty for the empty list. Accumulates into one builder and canonicalizes once, O(N log N) in the total interval count.

inter_list ts is the intersection of all of ts, and all for the empty list (the identity for intersection). One k-way sweep, so no intermediate set is built.

add t cp is t with cp added. Returns t itself if cp is already a member; otherwise copies the interval array, so O(n). For repeated additions use Builder, which appends in amortized O(1) and canonicalizes once.

remove t cp is t with cp removed. Returns t itself if cp is not a member; otherwise O(n), as add.

add_range t ~lo ~hi is union t (range ~lo ~hi).

remove_range t ~lo ~hi is diff t ~remove:(range ~lo ~hi).

filter f t keeps the codepoints of t satisfying f. O(cardinal); it visits every codepoint, so over a million calls on all. The number of runs it will emit is not known in advance, so the accumulator starts at t's interval count and grows: a predicate that fragments a large set pays for that growth.

map f t is the image of t under f. O(cardinal), and every result is validated, so f returning a surrogate or an out-of-range value raises Invalid_argument. f need not be injective or monotonic; the results are sorted and merged.

refine p q is the common refinement of two partitions given as lists of disjoint blocks, as Partition.blocks (Partition.meet (of_blocks p) (of_blocks q)). Blocks come back in increasing order of least element. Raises Invalid_argument if either list has overlapping blocks.

refine_all ps refines every partition in ps together, building the block sets once at the end; [all] for the empty list. Prefer this to folding refine, which rebuilds them at every step.

is_empty t is true iff t contains no codepoints. O(1).

is_singleton t is true iff t contains exactly one codepoint. O(1).

is_all t is true iff t is all. O(1); prefer it to is_empty (comp t), which allocates a set to answer the same question.

Membership test. O(log n) in the number of intervals.

mem_char t c is mem t (Char.code c).

mem_uchar t u is mem t (Uchar.to_int u).

next_elt_opt t cp is the smallest member of t strictly greater than cp, if any. cp need not be a member, or even a scalar value, so this doubles as "seek to the next member beyond here". O(log n).

prev_elt_opt t cp is the largest member of t strictly less than cp, if any. O(log n).

exists f t is true iff f holds of some codepoint of t. Visits codepoints, so O(cardinal) in the worst case, though it stops early.

for_all f t is true iff f holds of every codepoint of t. O(cardinal) in the worst case, stopping at the first failure.

Number of codepoints in the set. O(n) in the number of intervals.

Number of maximal contiguous runs in the set. O(1).

subset t ~of_ is true iff every scalar value of t is in of_.

disjoint t1 t2 is true iff t1 and t2 share no scalar value.

Smallest codepoint in the set, if any. O(1).

Largest codepoint in the set, if any. O(1).

An arbitrary element of the set, if any (currently the smallest). O(1).

iter f t applies f to each codepoint of t.

iter_intervals f t applies f lo hi to each maximal run lo..hi of t.

fold f t init folds f over each codepoint of t.

fold_intervals f t init folds f lo hi over each maximal run of t.

The codepoints of t in increasing order. Lazy, so it can be consumed partially without paying for the whole set.

The maximal runs of t as inclusive (lo, hi) pairs, in increasing order.

The maximal runs of the set as inclusive (lo, hi) pairs, in increasing order. Not the inverse of of_list, which takes codepoints; of_intervals is.

equal t1 t2 is true iff the two sets have the same members. The representation is canonical, so this compares the interval arrays: O(1) on physically equal sets and on sets of differing interval count.

A total order on sets. The order is representation-based (lexicographic over interval endpoints), rather than any set-theoretic order.

A non-negative hash consistent with equal, mixing the interval count and every endpoint. The values themselves are an implementation detail and may change between releases, so do not persist them.

Prints the runs of the set, e.g. [97-122; 181; 223-246].

As pp, but into a string on a single line. The printers break at the formatter's margin; the string forms have none, so the result never contains a newline, however wide the set.

As pp, but in U+XXXX notation: [U+0061-U+007A; U+00B5; U+00DF-U+00F6].

As pp_hex, on a single line. See to_string.

A regex-style character class view, reading a set as characters rather than as numbers: {a-g j m-t}, {α-ω}, {é € 😀-😁}.

Members are written as themselves, UTF-8 encoded. The escapes cover the syntax (-, space, { and }), the backslash that introduces them, the C0 and C1 controls, and the rest of Unicode's whitespace (U+00A0, U+1680, U+2000 to U+200A, U+2028, U+2029, U+202F, U+205F, U+3000), which would otherwise be indistinguishable from the separator. They are written \0, \t, \n, \v, \f, \r or \u{XX}. Nothing else is escaped, so unassigned and private-use members reach the terminal as whatever it makes of them.

A view, not regex syntax; an engine would want a single bracketed class with no separators, and its own escaping rules.

As pp_class, on a single line. See to_string.