includes/collation/IcuCollation.php

   1 <?php
   2 /**
   3  * This program is free software; you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation; either version 2 of the License, or
   6  * (at your option) any later version.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License along
  14  * with this program; if not, write to the Free Software Foundation, Inc.,
  15  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16  * http://www.gnu.org/copyleft/gpl.html
  17  *
  18  * @file
  19  */
  20
  21 /**
  22  * @since 1.16.3
  23  */
  24 class IcuCollation extends Collation {
  25         const FIRST_LETTER_VERSION = 4;
  26
  27         /** @var Collator */
  28         private $primaryCollator;
  29
  30         /** @var Collator */
  31         private $mainCollator;
  32
  33         /** @var string */
  34         private $locale;
  35
  36         /** @var Language */
  37         protected $digitTransformLanguage;
  38
  39         /** @var bool */
  40         private $useNumericCollation = false;
  41
  42         /** @var array */
  43         private $firstLetterData;
  44
  45         /**
  46          * Unified CJK blocks.
  47          *
  48          * The same definition of a CJK block must be used for both Collation and
  49          * generateCollationData.php. These blocks are omitted from the first
  50          * letter data, as an optimisation measure and because the default UCA table
  51          * is pretty useless for sorting Chinese text anyway. Japanese and Korean
  52          * blocks are not included here, because they are smaller and more useful.
  53          */
  54         private static $cjkBlocks = [
  55                 [ 0x2E80, 0x2EFF ], // CJK Radicals Supplement
  56                 [ 0x2F00, 0x2FDF ], // Kangxi Radicals
  57                 [ 0x2FF0, 0x2FFF ], // Ideographic Description Characters
  58                 [ 0x3000, 0x303F ], // CJK Symbols and Punctuation
  59                 [ 0x31C0, 0x31EF ], // CJK Strokes
  60                 [ 0x3200, 0x32FF ], // Enclosed CJK Letters and Months
  61                 [ 0x3300, 0x33FF ], // CJK Compatibility
  62                 [ 0x3400, 0x4DBF ], // CJK Unified Ideographs Extension A
  63                 [ 0x4E00, 0x9FFF ], // CJK Unified Ideographs
  64                 [ 0xF900, 0xFAFF ], // CJK Compatibility Ideographs
  65                 [ 0xFE30, 0xFE4F ], // CJK Compatibility Forms
  66                 [ 0x20000, 0x2A6DF ], // CJK Unified Ideographs Extension B
  67                 [ 0x2A700, 0x2B73F ], // CJK Unified Ideographs Extension C
  68                 [ 0x2B740, 0x2B81F ], // CJK Unified Ideographs Extension D
  69                 [ 0x2F800, 0x2FA1F ], // CJK Compatibility Ideographs Supplement
  70         ];
  71
  72         /**
  73          * Additional characters (or character groups) to be considered separate
  74          * letters for given languages, or to be removed from the list of such
  75          * letters (denoted by keys starting with '-').
  76          *
  77          * These are additions to (or subtractions from) the data stored in the
  78          * first-letters-root.php data file (which among others includes full basic Latin,
  79          * Cyrillic and Greek alphabets).
  80          *
  81          * "Separate letter" is a letter that would have a separate heading/section
  82          * for it in a dictionary or a phone book in this language. This data isn't
  83          * used for sorting (the ICU library handles that), only for deciding which
  84          * characters (or character groups) to use as headings.
  85          *
  86          * Initially generated based on the primary level of Unicode collation
  87          * tailorings available at http://developer.mimer.com/charts/tailorings.htm ,
  88          * later modified.
  89          *
  90          * Empty arrays are intended; this signifies that the data for the language is
  91          * available and that there are, in fact, no additional letters to consider.
  92          */
  93         private static $tailoringFirstLetters = [
  94                 'af' => [],
  95                 'am' => [],
  96                 'ar' => [],
  97                 'as' => [ "\u{0982}", "\u{0981}", "\u{0983}", "\u{09CE}", "ক্ষ " ],
  98                 'ast' => [ "Ch", "Ll", "Ñ" ], // not in libicu
  99                 'az' => [ "Ç", "Ə", "Ğ", "İ", "Ö", "Ş", "Ü" ],
 100                 'be' => [ "Ё" ],
 101                 'be-tarask' => [ "Ё" ],
 102                 'bg' => [],
 103                 'bn' => [ 'ং', 'ঃ', 'ঁ' ],
 104                 'bn@collation=traditional' => [
 105                         'ং', 'ঃ', 'ঁ', 'ক্', 'খ্', 'গ্', 'ঘ্', 'ঙ্', 'চ্', 'ছ্', 'জ্', 'ঝ্',
 106                         'ঞ্', 'ট্', 'ঠ্', 'ড্', 'ঢ্', 'ণ্', 'ৎ', 'থ্', 'দ্', 'ধ্', 'ন্', 'প্',
 107                         'ফ্', 'ব্', 'ভ্', 'ম্', 'য্', 'র্', 'ৰ্', 'ল্', 'ৱ্', 'শ্', 'ষ্', 'স্', 'হ্'
 108                 ],
 109                 'bo' => [],
 110                 'br' => [ "Ch", "C'h" ],
 111                 'bs' => [ "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ],
 112                 'bs-Cyrl' => [],
 113                 'ca' => [],
 114                 'chr' => [],
 115                 'co' => [], // not in libicu
 116                 'cs' => [ "Č", "Ch", "Ř", "Š", "Ž" ],
 117                 'cy' => [ "Ch", "Dd", "Ff", "Ng", "Ll", "Ph", "Rh", "Th" ],
 118                 'da' => [ "Æ", "Ø", "Å" ],
 119                 'de' => [],
 120                 'de-AT@collation=phonebook' => [ 'ä', 'ö', 'ü', 'ß' ],
 121                 'dsb' => [ "Č", "Ć", "Dź", "Ě", "Ch", "Ł", "Ń", "Ŕ", "Š", "Ś", "Ž", "Ź" ],
 122                 'ee' => [ "Dz", "Ɖ", "Ɛ", "Ƒ", "Gb", "Ɣ", "Kp", "Ny", "Ŋ", "Ɔ", "Ts", "Ʋ" ],
 123                 'el' => [],
 124                 'en' => [],
 125                 'eo' => [ "Ĉ", "Ĝ", "Ĥ", "Ĵ", "Ŝ", "Ŭ" ],
 126                 'es' => [ "Ñ" ],
 127                 'et' => [ "Š", "Ž", "Õ", "Ä", "Ö", "Ü" ],
 128                 'eu' => [ "Ñ" ], // not in libicu
 129                 'fa' => [
 130                         // RTL, let's put each letter on a new line
 131                         "آ",
 132                         "ء",
 133                         "ه",
 134                         "ا",
 135                         "و"
 136                 ],
 137                 'fi' => [ "Å", "Ä", "Ö" ],
 138                 'fil' => [ "Ñ", "Ng" ],
 139                 'fo' => [ "Á", "Ð", "Í", "Ó", "Ú", "Ý", "Æ", "Ø", "Å" ],
 140                 'fr' => [],
 141                 'fr-CA' => [], // fr-CA sorts accents slightly different from fr.
 142                 'fur' => [ "À", "Á", "Â", "È", "Ì", "Ò", "Ù" ], // not in libicu
 143                 'fy' => [], // not in libicu
 144                 'ga' => [],
 145                 'gd' => [], // not in libicu
 146                 'gl' => [ "Ch", "Ll", "Ñ" ],
 147                 'gu' => [ "\u{0A82}", "\u{0A83}", "\u{0A81}", "\u{0AB3}" ],
 148                 'ha' => [ 'Ɓ', 'Ɗ', 'Ƙ', 'Sh', 'Ts', 'Ƴ' ],
 149                 'haw' => [ 'ʻ' ],
 150                 'he' => [],
 151                 'hi' => [ "\u{0902}", "\u{0903}" ],
 152                 'hr' => [ "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ],
 153                 'hsb' => [ "Č", "Dź", "Ě", "Ch", "Ł", "Ń", "Ř", "Š", "Ć", "Ž" ],
 154                 'hu' => [ "Cs", "Dz", "Dzs", "Gy", "Ly", "Ny", "Ö", "Sz", "Ty", "Ü", "Zs" ],
 155                 'hy' => [ "և" ],
 156                 'id' => [],
 157                 'ig' => [ "Ch", "Gb", "Gh", "Gw", "Ị", "Kp", "Kw", "Ṅ", "Nw", "Ny", "Ọ", "Sh", "Ụ" ],
 158                 'is' => [ "Á", "Ð", "É", "Í", "Ó", "Ú", "Ý", "Þ", "Æ", "Ö", "Å" ],
 159                 'it' => [],
 160                 'ka' => [],
 161                 'kk' => [ "Ү", "І" ],
 162                 'kl' => [ "Æ", "Ø", "Å" ],
 163                 'km' => [
 164                         "រ", "ឫ", "ឬ", "ល", "ឭ", "ឮ", "\u{17BB}\u{17C6}",
 165                         "\u{17C6}", "\u{17B6}\u{17C6}", "\u{17C7}",
 166                         "\u{17B7}\u{17C7}", "\u{17BB}\u{17C7}",
 167                         "\u{17C1}\u{17C7}", "\u{17C4}\u{17C7}",
 168                 ],
 169                 'kn' => [ "\u{0C81}", "\u{0C83}", "\u{0CF1}", "\u{0CF2}" ],
 170                 'kok' => [ "\u{0902}", "\u{0903}", "ळ", "क्ष" ],
 171                 'ku' => [ "Ç", "Ê", "Î", "Ş", "Û" ], // not in libicu
 172                 'ky' => [ "Ё" ],
 173                 'la' => [], // not in libicu
 174                 'lb' => [],
 175                 'lkt' => [ 'Č', 'Ǧ', 'Ȟ', 'Š', 'Ž' ],
 176                 'ln' => [ 'Ɛ' ],
 177                 'lo' => [],
 178                 'lt' => [ "Č", "Š", "Ž" ],
 179                 'lv' => [ "Č", "Ģ", "Ķ", "Ļ", "Ņ", "Š", "Ž" ],
 180                 'mk' => [ "Ѓ", "Ќ" ],
 181                 'ml' => [],
 182                 'mn' => [],
 183                 'mo' => [ "Ă", "Â", "Î", "Ș", "Ț" ], // not in libicu
 184                 'mr' => [ "\u{0902}", "\u{0903}", "ळ", "क्ष", "ज्ञ" ],
 185                 'ms' => [],
 186                 'mt' => [ "Ċ", "Ġ", "Għ", "Ħ", "Ż" ],
 187                 'nb' => [ "Æ", "Ø", "Å" ],
 188                 'ne' => [],
 189                 'nl' => [],
 190                 'nn' => [ "Æ", "Ø", "Å" ],
 191                 'no' => [ "Æ", "Ø", "Å" ], // not in libicu. You should probably use nb or nn instead.
 192                 'oc' => [], // not in libicu
 193                 'om' => [ 'Ch', 'Dh', 'Kh', 'Ny', 'Ph', 'Sh' ],
 194                 'or' => [ "\u{0B01}", "\u{0B02}", "\u{0B03}", "କ୍ଷ" ],
 195                 'pa' => [ "\u{0A4D}" ],
 196                 'pl' => [ "Ą", "Ć", "Ę", "Ł", "Ń", "Ó", "Ś", "Ź", "Ż" ],
 197                 'pt' => [],
 198                 'rm' => [], // not in libicu
 199                 'ro' => [ "Ă", "Â", "Î", "Ș", "Ț" ],
 200                 'ru' => [],
 201                 'rup' => [ "Ă", "Â", "Î", "Ľ", "Ń", "Ș", "Ț" ], // not in libicu
 202                 'sco' => [],
 203                 'se' => [
 204                         'Á', 'Č', 'Ʒ', 'Ǯ', 'Đ', 'Ǧ', 'Ǥ', 'Ǩ', 'Ŋ',
 205                         'Š', 'Ŧ', 'Ž', 'Ø', 'Æ', 'Ȧ', 'Ä', 'Ö'
 206                 ],
 207                 'si' => [ "\u{0D82}", "\u{0D83}", "\u{0DA4}" ],
 208                 'sk' => [ "Ä", "Č", "Ch", "Ô", "Š", "Ž" ],
 209                 'sl' => [ "Č", "Š", "Ž" ],
 210                 'smn' => [ "Á", "Č", "Đ", "Ŋ", "Š", "Ŧ", "Ž", "Æ", "Ø", "Å", "Ä", "Ö" ],
 211                 'sq' => [ "Ç", "Dh", "Ë", "Gj", "Ll", "Nj", "Rr", "Sh", "Th", "Xh", "Zh" ],
 212                 'sr' => [],
 213                 'sr-Latn' => [ "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ],
 214                 'sv' => [ "Å", "Ä", "Ö" ],
 215                 'sv@collation=standard' => [ "Å", "Ä", "Ö" ],
 216                 'sw' => [],
 217                 'ta' => [
 218                         "\u{0B82}", "ஃ", "க்ஷ", "க்", "ங்", "ச்", "ஞ்", "ட்", "ண்", "த்", "ந்",
 219                         "ப்", "ம்", "ய்", "ர்", "ல்", "வ்", "ழ்", "ள்", "ற்", "ன்", "ஜ்", "ஶ்", "ஷ்",
 220                         "ஸ்", "ஹ்", "க்ஷ்"
 221                 ],
 222                 'te' => [ "\u{0C01}", "\u{0C02}", "\u{0C03}" ],
 223                 'th' => [ "ฯ", "\u{0E46}", "\u{0E4D}", "\u{0E3A}" ],
 224                 'tk' => [ "Ç", "Ä", "Ž", "Ň", "Ö", "Ş", "Ü", "Ý" ],
 225                 'tl' => [ "Ñ", "Ng" ], // not in libicu
 226                 'to' => [ "Ng", "ʻ" ],
 227                 'tr' => [ "Ç", "Ğ", "İ", "Ö", "Ş", "Ü" ],
 228                 '-tr' => [ "ı" ],
 229                 'tt' => [ "Ә", "Ө", "Ү", "Җ", "Ң", "Һ" ], // not in libicu
 230                 'uk' => [ "Ґ", "Ь" ],
 231                 'uz' => [ "Ch", "G'", "Ng", "O'", "Sh" ], // not in libicu
 232                 'vi' => [ "Ă", "Â", "Đ", "Ê", "Ô", "Ơ", "Ư" ],
 233                 'vo' => [ "Ä", "Ö", "Ü" ],
 234                 'yi' => [
 235                         "\u{05D1}\u{05BF}", "\u{05DB}\u{05BC}", "\u{05E4}\u{05BC}",
 236                         "\u{05E9}\u{05C2}", "\u{05EA}\u{05BC}"
 237                 ],
 238                 'yo' => [ "Ẹ", "Gb", "Ọ", "Ṣ" ],
 239                 'zu' => [],
 240         ];
 241
 242         /**
 243          * @since 1.16.3
 244          */
 245         const RECORD_LENGTH = 14;
 246
 247         public function __construct( $locale ) {
 248                 if ( !extension_loaded( 'intl' ) ) {
 249                         throw new MWException( 'An ICU collation was requested, ' .
 250                                 'but the intl extension is not available.' );
 251                 }
 252
 253                 $this->locale = $locale;
 254                 // Drop everything after the '@' in locale's name
 255                 $localeParts = explode( '@', $locale );
 256                 $this->digitTransformLanguage = Language::factory( $locale === 'root' ? 'en' : $localeParts[0] );
 257
 258                 $this->mainCollator = Collator::create( $locale );
 259                 if ( !$this->mainCollator ) {
 260                         throw new MWException( "Invalid ICU locale specified for collation: $locale" );
 261                 }
 262
 263                 $this->primaryCollator = Collator::create( $locale );
 264                 $this->primaryCollator->setStrength( Collator::PRIMARY );
 265
 266                 // If the special suffix for numeric collation is present, turn on numeric collation.
 267                 if ( substr( $locale, -5, 5 ) === '-u-kn' ) {
 268                         $this->useNumericCollation = true;
 269                         // Strip off the special suffix so it doesn't trip up fetchFirstLetterData().
 270                         $this->locale = substr( $this->locale, 0, -5 );
 271                         $this->mainCollator->setAttribute( Collator::NUMERIC_COLLATION, Collator::ON );
 272                         $this->primaryCollator->setAttribute( Collator::NUMERIC_COLLATION, Collator::ON );
 273                 }
 274         }
 275
 276         public function getSortKey( $string ) {
 277                 return $this->mainCollator->getSortKey( $string );
 278         }
 279
 280         public function getPrimarySortKey( $string ) {
 281                 return $this->primaryCollator->getSortKey( $string );
 282         }
 283
 284         public function getFirstLetter( $string ) {
 285                 $string = strval( $string );
 286                 if ( $string === '' ) {
 287                         return '';
 288                 }
 289
 290                 $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
 291
 292                 // If the first character is a CJK character, just return that character.
 293                 if ( ord( $firstChar ) > 0x7f && self::isCjk( UtfNormal\Utils::utf8ToCodepoint( $firstChar ) ) ) {
 294                         return $firstChar;
 295                 }
 296
 297                 $sortKey = $this->getPrimarySortKey( $string );
 298
 299                 // Do a binary search to find the correct letter to sort under
 300                 $min = ArrayUtils::findLowerBound(
 301                         [ $this, 'getSortKeyByLetterIndex' ],
 302                         $this->getFirstLetterCount(),
 303                         'strcmp',
 304                         $sortKey );
 305
 306                 if ( $min === false ) {
 307                         // Before the first letter
 308                         return '';
 309                 }
 310
 311                 $sortLetter = $this->getLetterByIndex( $min );
 312
 313                 if ( $this->useNumericCollation ) {
 314                         // If the sort letter is a number, return '0–9' (or localized equivalent).
 315                         // ASCII value of 0 is 48. ASCII value of 9 is 57.
 316                         // Note that this also applies to non-Arabic numerals since they are
 317                         // mapped to Arabic numeral sort letters. For example, ২ sorts as 2.
 318                         if ( ord( $sortLetter ) >= 48 && ord( $sortLetter ) <= 57 ) {
 319                                 $sortLetter = wfMessage( 'category-header-numerals' )->numParams( 0, 9 )->text();
 320                         }
 321                 }
 322                 return $sortLetter;
 323         }
 324
 325         /**
 326          * @since 1.16.3
 327          * @return array
 328          */
 329         public function getFirstLetterData() {
 330                 if ( $this->firstLetterData === null ) {
 331                         $cache = ObjectCache::getLocalServerInstance( CACHE_ANYTHING );
 332                         $cacheKey = $cache->makeKey(
 333                                 'first-letters',
 334                                 static::class,
 335                                 $this->locale,
 336                                 $this->digitTransformLanguage->getCode(),
 337                                 INTL_ICU_VERSION,
 338                                 self::FIRST_LETTER_VERSION
 339                         );
 340                         $this->firstLetterData = $cache->getWithSetCallback( $cacheKey, $cache::TTL_WEEK, function () {
 341                                 return $this->fetchFirstLetterData();
 342                         } );
 343                 }
 344                 return $this->firstLetterData;
 345         }
 346
 347         /**
 348          * @return array
 349          * @throws MWException
 350          */
 351         private function fetchFirstLetterData() {
 352                 global $IP;
 353                 // Generate data from serialized data file
 354                 if ( isset( self::$tailoringFirstLetters[$this->locale] ) ) {
 355                         $letters = require "$IP/includes/collation/data/first-letters-root.php";
 356                         // Append additional characters
 357                         $letters = array_merge( $letters, self::$tailoringFirstLetters[$this->locale] );
 358                         // Remove unnecessary ones, if any
 359                         if ( isset( self::$tailoringFirstLetters['-' . $this->locale] ) ) {
 360                                 $letters = array_diff( $letters, self::$tailoringFirstLetters['-' . $this->locale] );
 361                         }
 362                         // Apply digit transforms
 363                         $digits = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' ];
 364                         $letters = array_diff( $letters, $digits );
 365                         foreach ( $digits as $digit ) {
 366                                 $letters[] = $this->digitTransformLanguage->formatNum( $digit, true );
 367                         }
 368                 } else {
 369                         if ( $this->locale === 'root' ) {
 370                                 $letters = require "$IP/includes/collation/data/first-letters-root.php";
 371                         } else {
 372                                 // FIXME: Is this still used?
 373                                 $letters = wfGetPrecompiledData( "first-letters-{$this->locale}.ser" );
 374                                 if ( $letters === false ) {
 375                                         throw new MWException( "MediaWiki does not support ICU locale " .
 376                                                 "\"{$this->locale}\"" );
 377                                 }
 378                         }
 379                 }
 380
 381                 /* Sort the letters.
 382                  *
 383                  * It's impossible to have the precompiled data file properly sorted,
 384                  * because the sort order changes depending on ICU version. If the
 385                  * array is not properly sorted, the binary search will return random
 386                  * results.
 387                  *
 388                  * We also take this opportunity to remove primary collisions.
 389                  */
 390                 $letterMap = [];
 391                 foreach ( $letters as $letter ) {
 392                         $key = $this->getPrimarySortKey( $letter );
 393                         if ( isset( $letterMap[$key] ) ) {
 394                                 // Primary collision (two characters with the same sort position).
 395                                 // Keep whichever one sorts first in the main collator.
 396                                 $comp = $this->mainCollator->compare( $letter, $letterMap[$key] );
 397                                 wfDebug( "Primary collision '$letter' '{$letterMap[$key]}' (comparison: $comp)\n" );
 398                                 // If that also has a collision, use codepoint as a tiebreaker.
 399                                 if ( $comp === 0 ) {
 400                                         $comp = UtfNormal\Utils::utf8ToCodepoint( $letter ) <=>
 401                                                 UtfNormal\Utils::utf8ToCodepoint( $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 its 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 they 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://ssl.icu-project.org/repos/icu/icuhtml/trunk/design/collation/ICU_collation_design.htm
 429                  * - http://site.icu-project.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 = false;
 447                 $duplicatePrefixes = [];
 448                 foreach ( $letterMap as $key => $value ) {
 449                         // Remove terminator byte. Otherwise the prefix
 450                         // comparison will get hung up on that.
 451                         $trimmedKey = rtrim( $key, "\0" );
 452                         if ( $prev === false || $prev === '' ) {
 453                                 $prev = $trimmedKey;
 454                                 // We don't yet have a collation element
 455                                 // to compare against, so continue.
 456                                 continue;
 457                         }
 458
 459                         // Due to the fact the array is sorted, we only have
 460                         // to compare with the element directly previous
 461                         // to the current element (skipping expansions).
 462                         // An element "X" will always sort directly
 463                         // before "XZ" (Unless we have "XY", but we
 464                         // do not update $prev in that case).
 465                         if ( substr( $trimmedKey, 0, strlen( $prev ) ) === $prev ) {
 466                                 $duplicatePrefixes[] = $key;
 467                                 // If this is an expansion, we don't want to
 468                                 // compare the next element to this element,
 469                                 // but to what is currently $prev
 470                                 continue;
 471                         }
 472                         $prev = $trimmedKey;
 473                 }
 474                 foreach ( $duplicatePrefixes as $badKey ) {
 475                         wfDebug( "Removing '{$letterMap[$badKey]}' from first letters.\n" );
 476                         unset( $letterMap[$badKey] );
 477                         // This code assumes that unsetting does not change sort order.
 478                 }
 479                 $data = [
 480                         'chars' => array_values( $letterMap ),
 481                         'keys' => array_keys( $letterMap ),
 482                 ];
 483
 484                 // Reduce memory usage before caching
 485                 unset( $letterMap );
 486
 487                 return $data;
 488         }
 489
 490         /**
 491          * @param string $index
 492          * @return string
 493          * @since 1.16.3
 494          */
 495         public function getLetterByIndex( $index ) {
 496                 return $this->getFirstLetterData()['chars'][$index];
 497         }
 498
 499         /**
 500          * @param string $index
 501          * @return string
 502          * @since 1.16.3
 503          */
 504         public function getSortKeyByLetterIndex( $index ) {
 505                 return $this->getFirstLetterData()['keys'][$index];
 506         }
 507
 508         /**
 509          * @return string
 510          * @since 1.16.3
 511          */
 512         public function getFirstLetterCount() {
 513                 return count( $this->getFirstLetterData()['chars'] );
 514         }
 515
 516         /**
 517          * Test if a code point is a CJK (Chinese, Japanese, Korean) character
 518          * @param int $codepoint
 519          * @return bool
 520          * @since 1.16.3
 521          */
 522         public static function isCjk( $codepoint ) {
 523                 foreach ( self::$cjkBlocks as $block ) {
 524                         if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
 525                                 return true;
 526                         }
 527                 }
 528                 return false;
 529         }
 530
 531         /**
 532          * Return the version of ICU library used by PHP's intl extension,
 533          * or false when the extension is not installed of the version
 534          * can't be determined.
 535          *
 536          * The constant INTL_ICU_VERSION this function refers to isn't really
 537          * documented, but see https://bugs.php.net/bug.php?id=54561.
 538          *
 539          * @since 1.21
 540          * @deprecated since 1.32, use INTL_ICU_VERSION directly
 541          * @return string
 542          */
 543         static function getICUVersion() {
 544                 wfDeprecated( __METHOD__, '1.32' );
 545                 return INTL_ICU_VERSION;
 546         }
 547
 548         /**
 549          * Return the version of Unicode appropriate for the version of ICU library
 550          * currently in use, or false when it can't be determined.
 551          *
 552          * @since 1.21
 553          * @return string|bool
 554          */
 555         static function getUnicodeVersionForICU() {
 556                 $icuVersion = INTL_ICU_VERSION;
 557                 if ( !$icuVersion ) {
 558                         return false;
 559                 }
 560
 561                 $versionPrefix = substr( $icuVersion, 0, 3 );
 562                 // Source: http://site.icu-project.org/download
 563                 $map = [
 564                         '63.' => '11.0',
 565                         '62.' => '11.0',
 566                         '61.' => '10.0',
 567                         '60.' => '10.0',
 568                         '59.' => '9.0',
 569                         '58.' => '9.0',
 570                         '57.' => '8.0',
 571                         '56.' => '8.0',
 572                         '55.' => '7.0',
 573                         '54.' => '7.0',
 574                         '53.' => '6.3',
 575                         '52.' => '6.3',
 576                         '51.' => '6.2',
 577                         '50.' => '6.2',
 578                         '49.' => '6.1',
 579                         '4.8' => '6.0',
 580                         '4.6' => '6.0',
 581                         '4.4' => '5.2',
 582                         '4.2' => '5.1',
 583                         '4.0' => '5.1',
 584                         '3.8' => '5.0',
 585                         '3.6' => '5.0',
 586                         '3.4' => '4.1',
 587                 ];
 588
 589                 return $map[$versionPrefix] ?? false;
 590         }
 591 }