A Polish user sorts a list alphabetically and every word beginning with ć, ł, ś, ź or ż appears in a block at the bottom, after zebra. Nothing is broken in the way a crash is broken. The list is sorted, correctly, by the wrong key.
The symptom
Take twelve Polish words and sort them with a default comparator — Array.prototype.sort() in JavaScript, sorted() in Python, ORDER BY in a database with a C or byte collation. Here is what you get, next to what a Polish reader expects.
code-point order Polish collation order
------------------ ----------------------
adres adres
cena cena
lupa ćma ← moves up 6 places
osiem lupa
sad łąka
zebra osiem
ósmy ← U+00F3 ósmy
ćma ← U+0107 sad
łąka ← U+0142 ślad
ślad ← U+015B zebra
źle ← U+017A źle
żaba ← U+017C żaba
Five of the twelve are in the wrong place, and ćma is eight positions out. Notice also that the accented words are not shuffled randomly among themselves: ósmy comes first of them, then ćma, then łąka, then ślad, then źle, then żaba. That ordering is the tell.
Why code-point order does this
A default comparator compares code points. Polish uses nine letters outside ASCII, and Unicode did not allocate them anywhere near their alphabetical neighbours, because Unicode block layout follows the legacy character sets it had to absorb rather than any language’s alphabet.
letter code point block
ó U+00F3 Latin-1 Supplement
ą U+0105 Latin Extended-A
ć U+0107 Latin Extended-A
ę U+0119 Latin Extended-A
ł U+0142 Latin Extended-A
ń U+0144 Latin Extended-A
ś U+015B Latin Extended-A
ź U+017A Latin Extended-A
ż U+017C Latin Extended-A
ASCII a–z occupy U+0061–U+007A, so every one of these
sorts after every unaccented letter. And ó, being in the
older Latin-1 block, sorts before all the others.
That explains the observed order exactly. ósmy leads the accented block because U+00F3 is the lowest of the nine; the rest follow in Latin Extended-A order, which happens to coincide with alphabetical order for those five words by accident rather than by design. The Polish alphabet is a ą b c ć d e ę f g h i j k l ł m n ń o ó p r s ś t u w y z ź ż, and no arrangement of code points produces it.
Primary, secondary, tertiary
The reason a generic “accent-aware” setting does not fix this is that Polish disagrees with French about what an accent is.
The Unicode Collation Algorithm compares at several levels. A primary difference is a difference of letter. A secondary difference is a difference of accent on the same letter. A tertiary difference is case. Under the default table, e and é differ at the secondary level: they sort adjacently and the accent only breaks a tie. That is right for French, where coté and côte belong together in a dictionary.
Polish tailors the table so that ą, ć, ę, ł, ń, ó, ś, ź and ż are primary differences: separate letters, each with its own position immediately after its base letter. ćma sorts after every word beginning c and before every word beginning d, not interleaved among the c words. Locale-specific tailorings like this are exactly what CLDR publishes; the collation data itself is documented in Unicode Technical Standard #10, the Unicode Collation Algorithm.
The practical consequence: an accent-insensitive comparison is not a Polish comparison. Setting a comparator to ignore accents makes ćma sort among the c words, which is wrong in a different way from putting it after zebra. You need the Polish tailoring specifically.
Case is the third level, and it is the level that decides whether Zebra comes before or after zebra rather than whether either comes before żaba. This ordering of levels is why a case-insensitive comparison is a safe thing to ask for and an accent-insensitive one is not: dropping the tertiary level loses information Polish does not use lexically, while dropping the primary distinction between z and ż loses information it does. The uppercase forms sit at the same code points relative to each other — Ł is U+0141 and Ż is U+017B — so a naive sort of mixed-case Polish is wrong twice over, once for the accents and once for putting every capital ahead of every lowercase letter.
The letters Polish does not have
The mirror-image mistake is to assume that because Polish adds letters, it also treats its digraphs as letters. It does not, and hand-written collation code frequently gets this backwards.
Polish writes several sounds with two characters: cz, sz, rz, ch, dz, dź and dż. None of them is a letter of the alphabet. They sort as the two characters they are, so czapka falls among the c words, between cyrk and ćma, exactly where a character-by-character comparison puts it. Nothing special is required and nothing special should be added.
This is worth stating because neighbouring languages do the opposite. Czech treats ch as a single letter sorted after h, so chlap comes after hodina in a Czech dictionary and before it in a Polish-style comparison. Slovak, Hungarian and historically Spanish make similar contractions. Each of those is a separate CLDR tailoring, and none of them can be derived from the other — which is the practical argument for taking the collation from a locale identifier rather than assembling one from rules you have read about. A comparator built by hand for Polish will be wrong for Czech in a way that is invisible until a Czech user sorts a list.
Fixing it in three places
Sorting happens in more places than people expect, and fixing one of them produces a list that changes order depending on how it was fetched.
// 1. Application code — use a collator, not the default sort.
const pl = new Intl.Collator("pl", { sensitivity: "variant" });
words.sort(pl.compare);
// Intl.Collator caches its tailoring; constructing one per
// comparison inside sort() is the usual reason this "fixed"
// version is slower than the broken one.
// 2. PostgreSQL — an ICU collation on the column or the clause.
SELECT name FROM cities ORDER BY name COLLATE "pl-PL-x-icu";
ALTER TABLE cities
ALTER COLUMN name TYPE text COLLATE "pl-PL-x-icu";
// 3. The search engine — a collation-aware sort field, because a
// text field is sorted by its indexed terms, which are folded.
// In Elasticsearch this is the icu_collation_keyword field type
// with "language": "pl".
Python’s standard library is the odd one out. locale.strxfrm works but depends on a process-global locale being set and on that locale existing on the host, which fails in a minimal container. PyICU gives a real collator without the global state. Java and .NET both expose ICU collators directly, and both default to culture-sensitive comparison in ways that surprise people going the other direction.
One order, or none
The failure that outlasts the original bug is a list sorted in two places with two comparators. If the database returns a page ordered by its collation and the client re-sorts the visible rows with Intl.Collator, the two orders differ, and the difference shows up as rows that appear on two pages or on none. Keyset pagination makes it worse: the cursor is a value compared under the database’s ordering, so a client-side re-sort silently breaks the cursor’s meaning.
- Sort in exactly one layer. Usually the database, because that is where pagination happens.
- Pin the locale in the query, not in the session. A session-level
lc_collatemakes the order depend on which connection served the request. - Reindex after a collation change. A B-tree built under one collation is not valid under another; PostgreSQL will warn about collation version mismatches, and an index that is quietly out of order returns wrong results rather than slow ones.
- Decide what the locale of the list is. A Polish name in an English-language list is sorted by the list’s locale, not the name’s. Sorting each row by the language it appears to be in produces no total order at all.
Top comments (0)