[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20260904210759.GA23438@brightrain.aerifal.cx>
Date: Fri, 4 Sep 2026 17:07:59 -0400
From: Rich Felker <dalias@...c.org>
To: Demi Marie Obenour <demiobenour@...il.com>
Cc: musl@...ts.openwall.com
Subject: Re: Collation implementation is functional
On Fri, Sep 04, 2026 at 03:45:27PM -0400, Demi Marie Obenour wrote:
> On 9/4/26 12:45, Rich Felker wrote:
> > 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.
Unless they allow fields of very-long/unbounded length and collate
based on those, I think this is a non-issue. Normally you don't
collate based on large freeform text fields but things like names or
titles. Are you aware of specific things that would still be affected?
> Is it possible to achieve worst-case O(n) runtime if one allocates heap
> memory?
It's possible, but it's a strategy that's only a winning move if the
data is crafted intentionally to be slow, and it's very large. Doing
actual reordering or characters in a buffer looks like it requires
either expensive memmoves of potentially large spans or data
structures a lot heavier than array-of-characters. In any case it
can't meet the interface requirements; if it used heap allocation with
fallback on OOM, the astronomical-size inputs would just make it
fallback anyway, defeating the purpose.
> Or should the collation be incorrect in this case, and a bug
> reported against the collation information?
I'm not sure what you mean. Are you characterizing "correct" as
matching the UCA root data? That's what it means with respect to test
vectors, but my expectation is that in practice you use a tailoring
matching whatever cultural customs you want to reflect.
BTW I noticed earlier that, if you just want to avoid the
all-nonstarters contractions that can interleave (0F71 0F72 etc) but
still keep the sequence sorting in the right order for Tibetan (where
you would normally also have a lot of other tailorings that serve to
identify root letters of each syllable), you could replace each
offending contraction with 90 contextual contractions that only apply
following a Tibetan letter character. This would give the same result
for semantically-valid sequences but would prevent unbounded
interleaving of multiple contractions. Something like this might be
worth raising with the UCA folks, but probably needs a much deeper
analysis to determine the real costs and whether this fully mitigates
them.
Rich
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.
