[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20260823211541.GA26482@brightrain.aerifal.cx>
Date: Sun, 23 Aug 2026 17:15:42 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Collation code in-progress
Finally on to actually implementing collation! Some notes on this for
the record/for feedback if anyone is following and so desires:
The process is built on 4 layers of chained iterators:
1. Canonical decomposition - breaks characters down into base and
combining characters.
2. NFD normalization - applies canonical reordering to decomposed
character sequences.
3. Collation rules - contextually (prefix sensitive) maps sequences of
characters in NFD to sequences of collation elements
4. Collation elements - peels off the collation elements that come out
of the collation rules one-by-one
Iterators 1 and 2 were implemented back at the start of the project.
The 4th one is mostly an identity mapping except in relatively
uncommon case of characters mapping to more than one collation
element, and could possibly be collapsed with 3. I think it'd be a
tradeoff in clarity and code size/performance, but maybe not a bad
one.
As it is, I have drafts for 3 and 4 as separate. There is one
alteration I needed to make to the data model: at some point I had
dropped the requirement of being able to know where to stop reading a
multi-collation-element. I tentatively reserved a continuation bit in
the header byte, but I think this is a bad choice; it saves space in a
rare situation (multiple CEs) by sacrificing savings on very common
case (large number of characters with 3-byte primary weights). A
better option would probably be to reserve only a single header byte
value for flagging multi-CE mappings, then either store a separate CE
count or just null-terminate the sequence.
The overall process for strxfrm is to iterate the collation elements
(output of the final iterator above) in multiple passes, one per
weight level.
On the first pass, total length of the output is computed alongside
writing out the first-level weights. There are two exceptional
conditions for total length:
- If total length would exceed the output limit argument n, further
output is suppressed, but the first pass must be allowed to finish
to compute the return value. At that point, it is returned. This
matches the specification that the contents of the output buffer are
unspecified when the return value is >=n.
- If not bounded, it's possible that the computed total length could
exceed SIZE_MAX and overflow to 0. This is possible with an input
string below size PTRDIFF_MAX, since in general collation mappings
expand the string size quite a bit -- by a factor of 3 for ASCII
letters even. But if the accumulated length ever exceeds
PTRDIFF_MAX, that means it's impossible to store the transformed
string. So at this point, we can make up a required size that can
never be allocated, e.g. SIZE_MAX, and just return that with no
further processing. This avoids a need to try to return an error
from an interface with no good contract for returning errors, and
defers the error to subsequent attempt at allocation.
On each pass (only needed on the first for normal usage) we also
accumulate the output length for the next pass by itself. This is to
handle a possible flag for reversed order ("little endian collation")
where the direction of the last difference, rather than the first
difference, determines ordering.
On reversed passes, we start by jumping forward by the total length of
the pass, then emit collation elements in reverse into the output
buffer, working back to where we started, and finally jumping back to
the end in preparation for the next pass.
For strcoll, the process is somewhat different. We no longer need the
total length, but when the next pass is reverse-order, we need to know
the length of the next pass in [non-ignoreable at the next pass]
collation elements (not bytes). This enables starting the reversed
pass by skipping past enough collation elements of the "longer" string
that we start an equal number of CEs away from the end of both. Then,
we can proceed forward comparing one CE at a time, tracking the
last-seen direction of difference and, at the end of the pass,
returning that if it's nonzero.
Forward-order passes are easy: just compare successive non-ignoreable
CEs pairwise, skipping any that are ignoreable at the current pass.
The first difference is the return value.
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.
