MediaWiki master
IcuCollation.php
Go to the documentation of this file.
1<?php
22
26class IcuCollation extends Collation {
27 private const FIRST_LETTER_VERSION = 4;
28
30 private $primaryCollator;
31
33 private $mainCollator;
34
36 private $locale;
37
40
42 private $useNumericCollation = false;
43
45 private $firstLetterData;
46
56 private const CJK_BLOCKS = [
57 [ 0x2E80, 0x2EFF ], // CJK Radicals Supplement
58 [ 0x2F00, 0x2FDF ], // Kangxi Radicals
59 [ 0x2FF0, 0x2FFF ], // Ideographic Description Characters
60 [ 0x3000, 0x303F ], // CJK Symbols and Punctuation
61 [ 0x31C0, 0x31EF ], // CJK Strokes
62 [ 0x3200, 0x32FF ], // Enclosed CJK Letters and Months
63 [ 0x3300, 0x33FF ], // CJK Compatibility
64 [ 0x3400, 0x4DBF ], // CJK Unified Ideographs Extension A
65 [ 0x4E00, 0x9FFF ], // CJK Unified Ideographs
66 [ 0xF900, 0xFAFF ], // CJK Compatibility Ideographs
67 [ 0xFE30, 0xFE4F ], // CJK Compatibility Forms
68 [ 0x20000, 0x2A6DF ], // CJK Unified Ideographs Extension B
69 [ 0x2A700, 0x2B73F ], // CJK Unified Ideographs Extension C
70 [ 0x2B740, 0x2B81F ], // CJK Unified Ideographs Extension D
71 [ 0x2F800, 0x2FA1F ], // CJK Compatibility Ideographs Supplement
72 ];
73
95 private const TAILORING_FIRST_LETTERS = [
96 'af' => [],
97 'am' => [],
98 'ar' => [],
99 'as' => [ "\u{0982}", "\u{0981}", "\u{0983}", "\u{09CE}", "ক্ষ " ],
100 'ast' => [ "Ch", "Ll", "Ñ" ], // not in libicu
101 'az' => [ "Ç", "Ə", "Ğ", "İ", "Ö", "Ş", "Ü" ],
102 'be' => [ "Ё" ],
103 'be-tarask' => [ "Ё" ],
104 'bg' => [],
105 'bn' => [ 'ং', 'ঃ', 'ঁ' ],
106 'bn@collation=traditional' => [
107 'ং', 'ঃ', 'ঁ', 'ক্', 'খ্', 'গ্', 'ঘ্', 'ঙ্', 'চ্', 'ছ্', 'জ্', 'ঝ্',
108 'ঞ্', 'ট্', 'ঠ্', 'ড্', 'ঢ্', 'ণ্', 'ৎ', 'থ্', 'দ্', 'ধ্', 'ন্', 'প্',
109 'ফ্', 'ব্', 'ভ্', 'ম্', 'য্', 'র্', 'ৰ্', 'ল্', 'ৱ্', 'শ্', 'ষ্', 'স্', 'হ্'
110 ],
111 'bo' => [],
112 'br' => [ "Ch", "C'h" ],
113 'bs' => [ "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ],
114 'bs-Cyrl' => [],
115 'ca' => [],
116 'chr' => [],
117 'co' => [], // not in libicu
118 'cs' => [ "Č", "Ch", "Ř", "Š", "Ž" ],
119 'cy' => [ "Ch", "Dd", "Ff", "Ng", "Ll", "Ph", "Rh", "Th" ],
120 'da' => [ "Æ", "Ø", "Å" ],
121 'de' => [],
122 'de-AT@collation=phonebook' => [ 'ä', 'ö', 'ü', 'ß' ],
123 'dsb' => [ "Č", "Ć", "Dź", "Ě", "Ch", "Ł", "Ń", "Ŕ", "Š", "Ś", "Ž", "Ź" ],
124 'ee' => [ "Dz", "Ɖ", "Ɛ", "Ƒ", "Gb", "Ɣ", "Kp", "Ny", "Ŋ", "Ɔ", "Ts", "Ʋ" ],
125 'el' => [],
126 'en' => [],
127 'eo' => [ "Ĉ", "Ĝ", "Ĥ", "Ĵ", "Ŝ", "Ŭ" ],
128 'es' => [ "Ñ" ],
129 'et' => [ "Š", "Ž", "Õ", "Ä", "Ö", "Ü" ],
130 'eu' => [ "Ñ" ], // not in libicu
131 'fa' => [
132 // RTL, let's put each letter on a new line
133 "آ",
134 "ء",
135 "ه",
136 "ا",
137 "و"
138 ],
139 'fi' => [ "Å", "Ä", "Ö" ],
140 'fil' => [ "Ñ", "Ng" ],
141 'fo' => [ "Á", "Ð", "Í", "Ó", "Ú", "Ý", "Æ", "Ø", "Å" ],
142 'fr' => [],
143 'fr-CA' => [], // fr-CA sorts accents slightly different from fr.
144 'fur' => [ "À", "Á", "Â", "È", "Ì", "Ò", "Ù" ], // not in libicu
145 'fy' => [], // not in libicu
146 'ga' => [],
147 'gd' => [], // not in libicu
148 'gl' => [ "Ch", "Ll", "Ñ" ],
149 'gu' => [ "\u{0A82}", "\u{0A83}", "\u{0A81}", "\u{0AB3}" ],
150 'ha' => [ 'Ɓ', 'Ɗ', 'Ƙ', 'Sh', 'Ts', 'Ƴ' ],
151 'haw' => [ 'ʻ' ],
152 'he' => [],
153 'hi' => [ "\u{0902}", "\u{0903}" ],
154 'hr' => [ "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ],
155 'hsb' => [ "Č", "Dź", "Ě", "Ch", "Ł", "Ń", "Ř", "Š", "Ć", "Ž" ],
156 'hu' => [ "Cs", "Dz", "Dzs", "Gy", "Ly", "Ny", "Ö", "Sz", "Ty", "Ü", "Zs" ],
157 'hy' => [ "և" ],
158 'id' => [],
159 'ig' => [ "Ch", "Gb", "Gh", "Gw", "Ị", "Kp", "Kw", "Ṅ", "Nw", "Ny", "Ọ", "Sh", "Ụ" ],
160 'is' => [ "Á", "Ð", "É", "Í", "Ó", "Ú", "Ý", "Þ", "Æ", "Ö", "Å" ],
161 'it' => [],
162 'ka' => [],
163 'kk' => [ "Ү", "І" ],
164 'kl' => [ "Æ", "Ø", "Å" ],
165 'km' => [
166 "រ", "ឫ", "ឬ", "ល", "ឭ", "ឮ", "\u{17BB}\u{17C6}",
167 "\u{17C6}", "\u{17B6}\u{17C6}", "\u{17C7}",
168 "\u{17B7}\u{17C7}", "\u{17BB}\u{17C7}",
169 "\u{17C1}\u{17C7}", "\u{17C4}\u{17C7}",
170 ],
171 'kn' => [ "\u{0C81}", "\u{0C83}", "\u{0CF1}", "\u{0CF2}" ],
172 'kok' => [ "\u{0902}", "\u{0903}", "ळ", "क्ष" ],
173 'ku' => [ "Ç", "Ê", "Î", "Ş", "Û" ], // not in libicu
174 'ky' => [ "Ё" ],
175 'la' => [], // not in libicu
176 'lb' => [],
177 'lkt' => [ 'Č', 'Ǧ', 'Ȟ', 'Š', 'Ž' ],
178 'ln' => [ 'Ɛ' ],
179 'lo' => [],
180 'lt' => [ "Č", "Š", "Ž" ],
181 'lv' => [ "Č", "Ģ", "Ķ", "Ļ", "Ņ", "Š", "Ž" ],
182 'mk' => [ "Ѓ", "Ќ" ],
183 'ml' => [],
184 'mn' => [],
185 'mo' => [ "Ă", "Â", "Î", "Ș", "Ț" ], // not in libicu
186 'mr' => [ "\u{0902}", "\u{0903}", "ळ", "क्ष", "ज्ञ" ],
187 'ms' => [],
188 'mt' => [ "Ċ", "Ġ", "Għ", "Ħ", "Ż" ],
189 'nb' => [ "Æ", "Ø", "Å" ],
190 'ne' => [],
191 'nl' => [],
192 'nn' => [ "Æ", "Ø", "Å" ],
193 'no' => [ "Æ", "Ø", "Å" ], // not in libicu. You should probably use nb or nn instead.
194 'oc' => [], // not in libicu
195 'om' => [ 'Ch', 'Dh', 'Kh', 'Ny', 'Ph', 'Sh' ],
196 'or' => [ "\u{0B01}", "\u{0B02}", "\u{0B03}", "କ୍ଷ" ],
197 'pa' => [ "\u{0A4D}" ],
198 'pl' => [ "Ą", "Ć", "Ę", "Ł", "Ń", "Ó", "Ś", "Ź", "Ż" ],
199 'pt' => [],
200 'rm' => [], // not in libicu
201 'ro' => [ "Ă", "Â", "Î", "Ș", "Ț" ],
202 'ru' => [],
203 'rup' => [ "Ă", "Â", "Î", "Ľ", "Ń", "Ș", "Ț" ], // not in libicu
204 'sco' => [],
205 'se' => [
206 'Á', 'Č', 'Ʒ', 'Ǯ', 'Đ', 'Ǧ', 'Ǥ', 'Ǩ', 'Ŋ',
207 'Š', 'Ŧ', 'Ž', 'Ø', 'Æ', 'Ȧ', 'Ä', 'Ö'
208 ],
209 'si' => [ "\u{0D82}", "\u{0D83}", "\u{0DA4}" ],
210 'sk' => [ "Ä", "Č", "Ch", "Ô", "Š", "Ž" ],
211 'sl' => [ "Č", "Š", "Ž" ],
212 'smn' => [ "Á", "Č", "Đ", "Ŋ", "Š", "Ŧ", "Ž", "Æ", "Ø", "Å", "Ä", "Ö" ],
213 'sq' => [ "Ç", "Dh", "Ë", "Gj", "Ll", "Nj", "Rr", "Sh", "Th", "Xh", "Zh" ],
214 'sr' => [],
215 'sr-Latn' => [ "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ],
216 'sv' => [ "Å", "Ä", "Ö" ],
217 'sv@collation=standard' => [ "Å", "Ä", "Ö" ],
218 'sw' => [],
219 'ta' => [
220 "\u{0B82}", "ஃ", "க்ஷ", "க்", "ங்", "ச்", "ஞ்", "ட்", "ண்", "த்", "ந்",
221 "ப்", "ம்", "ய்", "ர்", "ல்", "வ்", "ழ்", "ள்", "ற்", "ன்", "ஜ்", "ஶ்", "ஷ்",
222 "ஸ்", "ஹ்", "க்ஷ்"
223 ],
224 'te' => [ "\u{0C01}", "\u{0C02}", "\u{0C03}" ],
225 'th' => [ "ฯ", "\u{0E46}", "\u{0E4D}", "\u{0E3A}" ],
226 'tk' => [ "Ç", "Ä", "Ž", "Ň", "Ö", "Ş", "Ü", "Ý" ],
227 'tl' => [ "Ñ", "Ng" ], // not in libicu
228 'to' => [ "Ng", "ʻ" ],
229 'tr' => [ "Ç", "Ğ", "İ", "Ö", "Ş", "Ü" ],
230 '-tr' => [ "ı" ],
231 'tt' => [ "Ә", "Ө", "Ү", "Җ", "Ң", "Һ" ], // not in libicu
232 'uk' => [ "Ґ", "Ь" ],
233 'uz' => [ "Ch", "G'", "Ng", "O'", "Sh" ], // not in libicu
234 'vi' => [ "Ă", "Â", "Đ", "Ê", "Ô", "Ơ", "Ư" ],
235 'vo' => [ "Ä", "Ö", "Ü" ],
236 'yi' => [
237 "\u{05D1}\u{05BF}", "\u{05DB}\u{05BC}", "\u{05E4}\u{05BC}",
238 "\u{05E9}\u{05C2}", "\u{05EA}\u{05BC}"
239 ],
240 'yo' => [ "Ẹ", "Gb", "Ọ", "Ṣ" ],
241 'zu' => [],
242 ];
243
248 public function __construct(
249 LanguageFactory $languageFactory,
250 $locale
251 ) {
252 $this->locale = $locale;
253 // Drop everything after the '@' in locale's name
254 $localeParts = explode( '@', $locale );
255 $this->digitTransformLanguage = $languageFactory->getLanguage( $locale === 'root' ? 'en' : $localeParts[0] );
256
257 $mainCollator = Collator::create( $locale );
258 if ( !$mainCollator ) {
259 throw new InvalidArgumentException( "Invalid ICU locale specified for collation: $locale" );
260 }
261 $this->mainCollator = $mainCollator;
262
263 // @phan-suppress-next-line PhanPossiblyNullTypeMismatchProperty successed before, no null check needed
264 $this->primaryCollator = Collator::create( $locale );
265 $this->primaryCollator->setStrength( Collator::PRIMARY );
266
267 // If the special suffix for numeric collation is present, turn on numeric collation.
268 if ( str_ends_with( $locale, '-u-kn' ) ) {
269 $this->useNumericCollation = true;
270 // Strip off the special suffix so it doesn't trip up fetchFirstLetterData().
271 $this->locale = substr( $this->locale, 0, -5 );
272 $this->mainCollator->setAttribute( Collator::NUMERIC_COLLATION, Collator::ON );
273 $this->primaryCollator->setAttribute( Collator::NUMERIC_COLLATION, Collator::ON );
274 }
275 }
276
277 public function getSortKey( $string ) {
278 return $this->mainCollator->getSortKey( $string );
279 }
280
281 public function getFirstLetter( $string ) {
282 $string = strval( $string );
283 if ( $string === '' ) {
284 return '';
285 }
286
287 $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
288
289 // If the first character is a CJK character, just return that character.
290 if ( ord( $firstChar ) > 0x7f && self::isCjk( mb_ord( $firstChar ) ) ) {
291 return $firstChar;
292 }
293
294 $sortKey = $this->getPrimarySortKey( $string );
295 $data = $this->getFirstLetterData();
296 $keys = $data['keys'];
297 $letters = $data['chars'];
298
299 // Do a binary search to find the correct letter to sort under
300 $min = ArrayUtils::findLowerBound(
301 static function ( $index ) use ( $keys ) {
302 return $keys[$index];
303 },
304 count( $keys ),
305 'strcmp',
306 $sortKey );
307
308 if ( $min === false ) {
309 // Before the first letter
310 return '';
311 }
312
313 $sortLetter = $letters[$min];
314
315 if ( $this->useNumericCollation ) {
316 // If the sort letter is a number, return '0–9' (or localized equivalent).
317 // ASCII value of 0 is 48. ASCII value of 9 is 57.
318 // Note that this also applies to non-Arabic numerals since they are
319 // mapped to Arabic numeral sort letters. For example, ২ sorts as 2.
320 if ( ord( $sortLetter ) >= 48 && ord( $sortLetter ) <= 57 ) {
321 $sortLetter = wfMessage( 'category-header-numerals' )->numParams( 0, 9 )->text();
322 }
323 }
324 return $sortLetter;
325 }
326
327 private function getPrimarySortKey( $string ) {
328 return $this->primaryCollator->getSortKey( $string );
329 }
330
335 private function getFirstLetterData() {
336 if ( $this->firstLetterData === null ) {
338 $cacheKey = $cache->makeKey(
339 'first-letters',
340 static::class,
341 $this->locale,
342 $this->digitTransformLanguage->getCode(),
343 INTL_ICU_VERSION,
344 self::FIRST_LETTER_VERSION
345 );
346 $this->firstLetterData = $cache->getWithSetCallback( $cacheKey, $cache::TTL_WEEK, function () {
347 return $this->fetchFirstLetterData();
348 } );
349 }
350 return $this->firstLetterData;
351 }
352
356 private function fetchFirstLetterData() {
357 // Generate data from serialized data file
358 if ( isset( self::TAILORING_FIRST_LETTERS[$this->locale] ) ) {
359 $letters = require __DIR__ . "/data/first-letters-root.php";
360 // Append additional characters
361 $letters = array_merge( $letters, self::TAILORING_FIRST_LETTERS[$this->locale] );
362 // Remove unnecessary ones, if any
363 if ( isset( self::TAILORING_FIRST_LETTERS['-' . $this->locale] ) ) {
364 $letters = array_diff( $letters, self::TAILORING_FIRST_LETTERS['-' . $this->locale] );
365 }
366 // Apply digit transforms
367 $digits = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' ];
368 $letters = array_diff( $letters, $digits );
369 foreach ( $digits as $digit ) {
370 $letters[] = $this->digitTransformLanguage->formatNumNoSeparators( $digit );
371 }
372 } elseif ( $this->locale === 'root' ) {
373 $letters = require __DIR__ . "/data/first-letters-root.php";
374 } else {
375 throw new RuntimeException( "MediaWiki does not support ICU locale " .
376 "\"{$this->locale}\"" );
377 }
378
379 /* Sort the letters.
380 *
381 * It's impossible to have the precompiled data file properly sorted,
382 * because the sort order changes depending on ICU version. If the
383 * array is not properly sorted, the binary search will return random
384 * results.
385 *
386 * We also take this opportunity to remove primary collisions.
387 */
388 $letterMap = [];
389 foreach ( $letters as $letter ) {
390 $key = $this->getPrimarySortKey( $letter );
391 if ( isset( $letterMap[$key] ) ) {
392 // Primary collision (two characters with the same sort position).
393 // Keep whichever one sorts first in the main collator.
394 $comp = $this->mainCollator->compare( $letter, $letterMap[$key] );
395 wfDebug( "Primary collision '$letter' '{$letterMap[$key]}' (comparison: $comp)" );
396 // If that also has a collision, use codepoint as a tiebreaker.
397 if ( $comp === 0 ) {
398 $comp = mb_ord( $letter ) <=> mb_ord( $letterMap[$key] );
399 }
400 if ( $comp < 0 ) {
401 $letterMap[$key] = $letter;
402 }
403 } else {
404 $letterMap[$key] = $letter;
405 }
406 }
407 ksort( $letterMap, SORT_STRING );
408
409 /* Remove duplicate prefixes. Basically, if something has a sortkey
410 * which is a prefix of some other sortkey, then it is an
411 * expansion and probably should not be considered a section
412 * header.
413 *
414 * For example, 'þ' is sometimes sorted as if it is the letters
415 * 'th'. Other times it is its own primary element. Another
416 * example is '₨'. Sometimes it's a currency symbol. Sometimes it
417 * is an 'R' followed by an 's'.
418 *
419 * Additionally, an expanded element should always sort directly
420 * after its first element due to the way sortkeys work.
421 *
422 * UCA sortkey elements are of variable length, but no collation
423 * element should be a prefix of some other element, so I think
424 * this is safe. See:
425 * - https://unicode-org.github.io/icu-docs/design/collation/ICU_collation_design.htm
426 * - https://icu.unicode.org/design/collation/uca-weight-allocation
427 *
428 * Additionally, there is something called primary compression to
429 * worry about. Basically, if you have two primary elements that
430 * are more than one byte and both start with the same byte, then
431 * the first byte is dropped on the second primary. Additionally,
432 * either \x03 or \xFF may be added to mean that the next primary
433 * does not start with the first byte of the first primary.
434 *
435 * This shouldn't matter much, as the first primary is not
436 * changed, and that is what we are comparing against.
437 *
438 * tl;dr: This makes some assumptions about how ICU implements
439 * collations. It seems incredibly unlikely these assumptions
440 * will change, but nonetheless they are assumptions.
441 */
442
443 $prev = '';
444 $duplicatePrefixes = [];
445 foreach ( $letterMap as $key => $value ) {
446 // Due to the fact the array is sorted, we only have
447 // to compare with the element directly previous
448 // to the current element (skipping expansions).
449 // An element "X" will always sort directly
450 // before "XZ" (Unless we have "XY", but we
451 // do not update $prev in that case).
452 if ( $prev !== '' && str_starts_with( $key, $prev ) ) {
453 $duplicatePrefixes[] = $key;
454 // If this is an expansion, we don't want to
455 // compare the next element to this element,
456 // but to what is currently $prev
457 continue;
458 }
459 $prev = $key;
460 }
461 foreach ( $duplicatePrefixes as $badKey ) {
462 wfDebug( "Removing '{$letterMap[$badKey]}' from first letters." );
463 unset( $letterMap[$badKey] );
464 // This code assumes that unsetting does not change sort order.
465 }
466 return [
467 'chars' => array_values( $letterMap ),
468 'keys' => array_keys( $letterMap ),
469 ];
470 }
471
478 public static function isCjk( $codepoint ) {
479 foreach ( self::CJK_BLOCKS as $block ) {
480 if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
481 return true;
482 }
483 }
484 return false;
485 }
486}
const CACHE_ANYTHING
Definition Defines.php:85
wfDebug( $text, $dest='all', array $context=[])
Sends a line to the debug log if enabled or, optionally, to a comment in output.
wfMessage( $key,... $params)
This is the function for getting translated interface messages.
getFirstLetter( $string)
Given a string, return the logical "first letter" to be used for grouping on category pages and so on...
static isCjk( $codepoint)
Test if a code point is a CJK (Chinese, Japanese, Korean) character.
__construct(LanguageFactory $languageFactory, $locale)
Language $digitTransformLanguage
getSortKey( $string)
Given a string, convert it to a (hopefully short) key that can be used for efficient sorting.
Base class for language-specific code.
Definition Language.php:63
Internationalisation code See https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation for more...
getLanguage( $code)
Get a cached or new language object for a given language code with normalization of the language code...
static getLocalServerInstance( $fallback=CACHE_NONE)