[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20260904164533.GZ23438@brightrain.aerifal.cx>
Date: Fri, 4 Sep 2026 12:45:33 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: Collation implementation is functional
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.
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.
