MediaWiki  master
IcuCollation.php
Go to the documentation of this file.
1 <?php
22 
26 class 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 MWException( "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 ( substr( $locale, -5, 5 ) === '-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
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 
357  private function fetchFirstLetterData() {
358  // Generate data from serialized data file
359  if ( isset( self::TAILORING_FIRST_LETTERS[$this->locale] ) ) {
360  $letters = require __DIR__ . "/data/first-letters-root.php";
361  // Append additional characters
362  $letters = array_merge( $letters, self::TAILORING_FIRST_LETTERS[$this->locale] );
363  // Remove unnecessary ones, if any
364  if ( isset( self::TAILORING_FIRST_LETTERS['-' . $this->locale] ) ) {
365  $letters = array_diff( $letters, self::TAILORING_FIRST_LETTERS['-' . $this->locale] );
366  }
367  // Apply digit transforms
368  $digits = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' ];
369  $letters = array_diff( $letters, $digits );
370  foreach ( $digits as $digit ) {
371  $letters[] = $this->digitTransformLanguage->formatNumNoSeparators( $digit );
372  }
373  } elseif ( $this->locale === 'root' ) {
374  $letters = require __DIR__ . "/data/first-letters-root.php";
375  } else {
376  throw new MWException( "MediaWiki does not support ICU locale " .
377  "\"{$this->locale}\"" );
378  }
379 
380  /* Sort the letters.
381  *
382  * It's impossible to have the precompiled data file properly sorted,
383  * because the sort order changes depending on ICU version. If the
384  * array is not properly sorted, the binary search will return random
385  * results.
386  *
387  * We also take this opportunity to remove primary collisions.
388  */
389  $letterMap = [];
390  foreach ( $letters as $letter ) {
391  $key = $this->getPrimarySortKey( $letter );
392  if ( isset( $letterMap[$key] ) ) {
393  // Primary collision (two characters with the same sort position).
394  // Keep whichever one sorts first in the main collator.
395  $comp = $this->mainCollator->compare( $letter, $letterMap[$key] );
396  wfDebug( "Primary collision '$letter' '{$letterMap[$key]}' (comparison: $comp)" );
397  // If that also has a collision, use codepoint as a tiebreaker.
398  if ( $comp === 0 ) {
399  $comp = mb_ord( $letter ) <=> mb_ord( $letterMap[$key] );
400  }
401  if ( $comp < 0 ) {
402  $letterMap[$key] = $letter;
403  }
404  } else {
405  $letterMap[$key] = $letter;
406  }
407  }
408  ksort( $letterMap, SORT_STRING );
409 
410  /* Remove duplicate prefixes. Basically, if something has a sortkey
411  * which is a prefix of some other sortkey, then it is an
412  * expansion and probably should not be considered a section
413  * header.
414  *
415  * For example, 'þ' is sometimes sorted as if it is the letters
416  * 'th'. Other times it is its own primary element. Another
417  * example is '₨'. Sometimes it's a currency symbol. Sometimes it
418  * is an 'R' followed by an 's'.
419  *
420  * Additionally, an expanded element should always sort directly
421  * after its first element due to the way sortkeys work.
422  *
423  * UCA sortkey elements are of variable length, but no collation
424  * element should be a prefix of some other element, so I think
425  * this is safe. See:
426  * - https://unicode-org.github.io/icu-docs/design/collation/ICU_collation_design.htm
427  * - https://icu.unicode.org/design/collation/uca-weight-allocation
428  *
429  * Additionally, there is something called primary compression to
430  * worry about. Basically, if you have two primary elements that
431  * are more than one byte and both start with the same byte, then
432  * the first byte is dropped on the second primary. Additionally,
433  * either \x03 or \xFF may be added to mean that the next primary
434  * does not start with the first byte of the first primary.
435  *
436  * This shouldn't matter much, as the first primary is not
437  * changed, and that is what we are comparing against.
438  *
439  * tl;dr: This makes some assumptions about how ICU implements
440  * collations. It seems incredibly unlikely these assumptions
441  * will change, but nonetheless they are assumptions.
442  */
443 
444  $prev = '';
445  $duplicatePrefixes = [];
446  foreach ( $letterMap as $key => $value ) {
447  // Due to the fact the array is sorted, we only have
448  // to compare with the element directly previous
449  // to the current element (skipping expansions).
450  // An element "X" will always sort directly
451  // before "XZ" (Unless we have "XY", but we
452  // do not update $prev in that case).
453  if ( $prev !== '' && str_starts_with( $key, $prev ) ) {
454  $duplicatePrefixes[] = $key;
455  // If this is an expansion, we don't want to
456  // compare the next element to this element,
457  // but to what is currently $prev
458  continue;
459  }
460  $prev = $key;
461  }
462  foreach ( $duplicatePrefixes as $badKey ) {
463  wfDebug( "Removing '{$letterMap[$badKey]}' from first letters." );
464  unset( $letterMap[$badKey] );
465  // This code assumes that unsetting does not change sort order.
466  }
467  return [
468  'chars' => array_values( $letterMap ),
469  'keys' => array_keys( $letterMap ),
470  ];
471  }
472 
479  public static function isCjk( $codepoint ) {
480  foreach ( self::CJK_BLOCKS as $block ) {
481  if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
482  return true;
483  }
484  }
485  return false;
486  }
487 
495  public static function getUnicodeVersionForICU() {
496  $icuVersion = INTL_ICU_VERSION;
497  if ( !$icuVersion ) {
498  return false;
499  }
500 
501  $versionPrefix = substr( $icuVersion, 0, 3 );
502  // Source: https://icu.unicode.org/download
503  $map = [
504  '69.' => '13.0',
505  '68.' => '13.0',
506  '67.' => '13.0',
507  '66.' => '13.0',
508  '65.' => '12.0',
509  '64.' => '12.0',
510  '63.' => '11.0',
511  '62.' => '11.0',
512  '61.' => '10.0',
513  '60.' => '10.0',
514  '59.' => '9.0',
515  '58.' => '9.0',
516  '57.' => '8.0',
517  '56.' => '8.0',
518  '55.' => '7.0',
519  '54.' => '7.0',
520  '53.' => '6.3',
521  '52.' => '6.3',
522  '51.' => '6.2',
523  '50.' => '6.2',
524  '49.' => '6.1',
525  '4.8' => '6.0',
526  '4.6' => '6.0',
527  '4.4' => '5.2',
528  '4.2' => '5.1',
529  '4.0' => '5.1',
530  '3.8' => '5.0',
531  '3.6' => '5.0',
532  '3.4' => '4.1',
533  ];
534 
535  return $map[$versionPrefix] ?? false;
536  }
537 }
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.
static findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target)
Do a binary search, and return the index of the largest item that sorts less than or equal to the tar...
Definition: ArrayUtils.php:113
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.
static getUnicodeVersionForICU()
Return the version of Unicode appropriate for the version of ICU library currently in use,...
MediaWiki exception.
Definition: MWException.php:29
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.
static getLocalServerInstance( $fallback=CACHE_NONE)
Factory function for CACHE_ACCEL (referenced from configuration)
$cache
Definition: mcc.php:33