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