[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <7494ace5-f7d5-4fe8-a242-209c7fa5a1d4@gmail.com>
Date: Fri, 4 Sep 2026 15:45:27 -0400
From: Demi Marie Obenour <demiobenour@...il.com>
To: musl@...ts.openwall.com, Rich Felker <dalias@...c.org>
Subject: Re: Collation implementation is functional
On 9/4/26 12:45, Rich Felker wrote:
> On Thu, Sep 03, 2026 at 12:22:22PM -0400, Rich Felker wrote:
>> Runtime side:
>>
>> Both basic proof of concept (iteration of collation elements from an
>> input string) and a working strxfrm (transformation of string to a
>> null-terminated binary sort key) are working, and have been
>> smoke-tested manually for basic coverage:
>>
>> - Straightforward one-to-one mappings
>> - Matching prefix contexts (middle dot following L)
>> - Non-matching prefix contexts (middle dot not following L)
>> - One-to-many mappings
>> - Two-to-one mappings
>> - Reordering mappings (Thai vowel)
>> - Auto-generated ideographic radical-stroke-order weights
>> - Implicit weights
>> - Reversed-order secondary weights
>>
>> This list will make the basis for an automated smoke test. There are
>> also Unicode-provided test vectors which have not yet been tested, but
>> these do not assert specific behavior generating keys; they just
>> assert the correct ordering of a long list of short string fragments.
>
> Yesterday I started testing against the Unicode test vectors, and
> after fixing a few small bugs and version skew issues between tests
> and data, there's only one real issue.
>
> Apparently I'd overlooked (UTR#35 doesn't mention this; it's only
> covered in the original UTR#10) that UCA has discontiguous contraction
> matches. This is a costly and cursed requirement but necessary because
> of how canonicalization -- specifically, canonical ordering of
> combining marks -- works.
>
> In a sequence A B C, where B and C are combining marks, it's possible
> that, due purely to arbitrary choice that was made in how to number
> the combining classes, the normalization is A C B.
>
> But if A+B collate as a unit, this means the addition of the mark C
> would suddenly break the sorting of A B by reordering between them.
>
>
>
> As such, UCA specifies a discontiguous matching of contractions. When
> A is a prefix of a possible contraction, and the next character C does
> not match but is a "non-starter" (character which participates in
> canonical reordering), the search for a match must look ahead,
> consuming any characters that contribute to a match until a blocker
> is encountered. These consumed characters are then logically removed
> from the input.
>
> Described that way, this is (pardon the pun) a non-starter: there is
> no way to remove characters out of an immutable input stream with no
> place for a copy. However, fortunately that impossibility is an
> artifact of the description, and not fundamental.
>
>
>
> Let's look at the general case, much worse than anything practical,
> where we have a contraction ABCDEFG involving 6 combining marks
> attached to A, and an input which, after normalization, looks like:
>
> A............B...........CD.....E.F..G......
> 01111111111112222222333334444444555556666660
>
> Here the dots could be arbitrary nonmatching characters; the numbers
> below them are their canonical combining classes. It's not important
> that A have ccc=0; it could itself have been a non-starter.
>
> The matching process, when the next character does not match but A is
> a prefix, looks forward to find B, C, D, and E. But F can't be
> included, because there's an intervening character in the same ccc.
> Thus, we match the contraction ABCDE, advancing past the A and
> pre-consuming B, C, D, and E.
>
> So, how do we represent the state after this, to be able to continue
> without storing all the offsets of characters pre-consumed?
>
> We've already advanced past A as if it were a single-character match,
> so no special accounting for it is needed. For the rest, we use the
> fact that there are only a fixed number of ccc's (bounded by 255;
> practically a lot less), and that we can only consume contiguous spans
> at the beginning of each ccc in the normalized order: B, CD, and E. So
> the state after the above ABCDE match is:
>
> ccc=1: 0 preconsumed
> ccc=2: 1 preconsumed
> ccc=3: 0 preconsumed
> ccc=4: 2 preconsumed
> ccc=5: 1 preconsumed
> ccc=6: 0 preconsumed
>
> Now, upon continuing to consume input, we just need to know the ccc of
> each character we read from the input sequence. If there is a nonzero
> preconsumed counter for that ccc, we drop the character and decrement
> the preconsumed counter, repeating this process until we get to a
> character that's not preconsumed. If we reach the next starter
> (ccc=0), it's guaranteed that all of the preconsumed counts have
> dropped back to 0.
>
> This isn't quite the complete story though. because it might occur
> that we have another lookahead while there are already preconsumed
> characters. Let's say XYZ is also a contraction, and the above dots
> are filled in partly as:
>
> A....X.......B...........CDY....EZF..G......
> 01111111111112222222333334444444555556666660
>
> When we reach X and begin lookahead, B is skipped because ccc=2 has 1
> preconsumed, but since this is lookahead, we can't decrement that
> counter. Instead it needs to be left alone while skipping ahead. Upon
> reaching ccc=4, there are 2 preconsumed characters, so C and D are
> skipped. Now Y is the first character of a new ccc, so it can be
> consumed for the contraction, incrementing the preconsumed count for
> ccc=4 to 3. Lookahead continues to ccc=5 where E is skipped (1
> character was already preconsumed) and now Z is the first character of
> a new ccc. It also gets added to the contraction match and the
> preconsumed count gets incremented.
>
> The final state has:
>
> ccc=1: 0 preconsumed
> ccc=2: 1 preconsumed
> ccc=3: 0 preconsumed
> ccc=4: 3 preconsumed
> ccc=5: 2 preconsumed
> ccc=6: 0 preconsumed
>
>
>
> I've written up the following pseudocode for the above process:
>
>
> Non-lookahead input reads:
>
> if nskip[ccc] is nonzero, decremenet nskip[ccc], discard character,
> and start over reading the next character
>
>
> Lookahead process:
>
> if contraction is incomplete
> and next character does not match
> and next character is a non-starter:
>
> place next character pending
>
> make a copy of nfd iterator state, and enter a loop advancing it
> forward:
>
> - end loop if we hit a non-starter
> - if new ccc, skip nskip[ccc]
> - if we hit a match, consume it and increment nskip[ccc]
> - if not a match, skip past all further chars in same ccc
>
> after stopping, the temp iterator copy can be discarded. we only need
> to preserve nskip[] array.
>
>
>
>
> Implementation considerations:
>
> The NFD iterator implementation already has ccc values available to
> it, but drops them from the return value to give clean wchar_t
> codepoint values. Switching to return a combined ccc+codepoint value,
> like what's used internally, is not hard; the caller can extract/strip
> the ccc as needed.
>
> Having a 255-element array of size_t for nskip[] is somewhat costly,
> mainly in terms of overhead to initialize in the common case where it
> will never be touched.
>
> The decomposition table already compresses ccc values to account for
> the fact that most of the space is unused. I recall there being around
> 56 actually used. An array of bytes in .rodata mapping ccc's to an
> index in a much smaller array of size_t would have very low .text and
> .rodata size and drop this runtime cost by 80%.
>
>
>
> Performance considerations:
>
> How bad does this all perform? In principle we can end up iterating
> over the same very long span of characters many times in successive
> lookehead operations. However, the sort of interleaved ABC/XYZ
> situation in the example above can only arise if you have contractions
> beginning with non-starters. You would think that wouldn't happen, but
> there's exactly one place in the root data where it does: contractions
> for 0F71 0F72 and 0F71 0F80. This means you can achieve quadratic(*)
> time with an input consisting of n copies of 0F71 and n copies of
> 0F72, in any order.
>
> Unfortunately, this is essential; it's not a consequence of
> implementation choices. The only ways to avoid it are by not
> attempting to collate monstrously long strings with potentially
> malicious contents, or by only using locales without such bad
> contractions. The fact that they appear at all here is probably due to
> an error encoding the characters in Unicode; 0F71 behaves like a
> subjoined letter not a vowel marker, and likely should have been
> encoded with ccc=0. Since the root data does not even give correct
> dictionary order for Tibetan to begin with, it may be a good idea to
> just drop these contractions for locales that are not tailored for it.
>
> On the bright side, exposure of collation interfaces to low-trust data
> is usually limited to things like file listings, where NAME_MAX sets a
> very low limit on the number of characters that can participate in
> pathological canonical ordering shenanigans. Since the affected
> characters are 3-byte UTF-8, the n going into quadratic(?) time cost
> is at most 85 here.
>
> (*) It may actually be higher-order, because the NFD iteration process
> is complex and quasi-nonlinear. For a given iteration, the number of
> times going over the same character is bounded by the number of ccc's,
> making it technically O(n). But when resetting a clone of the
> iterator, I'm not sure, and it's making my head hurt trying to think
> about it.
Unfortunately, databases use libc collations, and *do* contain untrusted
data, often from the network.
Is it possible to achieve worst-case O(n) runtime if one allocates heap
memory? Or should the collation be incorrect in this case, and a bug
reported against the collation information?
--
Sincerely,
Demi Marie Obenour (she/her/hers)
Download attachment "OpenPGP_signature.asc" of type "application/pgp-signature" (834 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
