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 = 3;
  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.ser 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' => [ "\xe0\xa6\x82", "\xe0\xa6\x81", "\xe0\xa6\x83", "\xe0\xa7\x8e", "ক্ষ " ],
  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' => [ "Š", "Ž", "Õ", "Ä", "Ö", "Ü", "W" ], // added W for CollationEt (xx-uca-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' => [ "\xe0\xaa\x82", "\xe0\xaa\x83", "\xe0\xaa\x81", "\xe0\xaa\xb3" ],
 148                 'ha' => [ 'Ɓ', 'Ɗ', 'Ƙ', 'Sh', 'Ts', 'Ƴ' ],
 149                 'haw' => [ 'ʻ' ],
 150                 'he' => [],
 151                 'hi' => [ "\xe0\xa4\x82", "\xe0\xa4\x83" ],
 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                         "រ", "ឫ", "ឬ", "ល", "ឭ", "ឮ", "\xe1\x9e\xbb\xe1\x9f\x86",
 165                         "\xe1\x9f\x86", "\xe1\x9e\xb6\xe1\x9f\x86", "\xe1\x9f\x87",
 166                         "\xe1\x9e\xb7\xe1\x9f\x87", "\xe1\x9e\xbb\xe1\x9f\x87",
 167                         "\xe1\x9f\x81\xe1\x9f\x87", "\xe1\x9f\x84\xe1\x9f\x87",
 168                 ],
 169                 'kn' => [ "\xe0\xb2\x81", "\xe0\xb2\x83", "\xe0\xb3\xb1", "\xe0\xb3\xb2" ],
 170                 'kok' => [ "\xe0\xa4\x82", "\xe0\xa4\x83", "ळ", "क्ष" ],
 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' => [ "\xe0\xa4\x82", "\xe0\xa4\x83", "ळ", "क्ष", "ज्ञ" ],
 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' => [ "\xe0\xac\x81", "\xe0\xac\x82", "\xe0\xac\x83", "କ୍ଷ" ],
 195                 'pa' => [ "\xe0\xa9\x8d" ],
 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' => [ "\xe0\xb6\x82", "\xe0\xb6\x83", "\xe0\xb6\xa4" ],
 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                         "\xE0\xAE\x82", "ஃ", "க்ஷ", "க்", "ங்", "ச்", "ஞ்", "ட்", "ண்", "த்", "ந்",
 219                         "ப்", "ம்", "ய்", "ர்", "ல்", "வ்", "ழ்", "ள்", "ற்", "ன்", "ஜ்", "ஶ்", "ஷ்",
 220                         "ஸ்", "ஹ்", "க்ஷ்"
 221                 ],
 222                 'te' => [ "\xe0\xb0\x81", "\xe0\xb0\x82", "\xe0\xb0\x83" ],
 223                 'th' => [ "ฯ", "\xe0\xb9\x86", "\xe0\xb9\x8d", "\xe0\xb8\xba" ],
 224                 'tk' => [ "Ç", "Ä", "Ž", "Ň", "Ö", "Ş", "Ü", "Ý" ],
 225                 'tl' => [ "Ñ", "Ng" ], // not in libicu
 226                 'to' => [ "Ng", "ʻ" ],
 227                 'tr' => [ "Ç", "Ğ", "İ", "Ö", "Ş", "Ü" ],
 228                 'tt' => [ "Ә", "Ө", "Ү", "Җ", "Ң", "Һ" ], // not in libicu
 229                 'uk' => [ "Ґ", "Ь" ],
 230                 'uz' => [ "Ch", "G'", "Ng", "O'", "Sh" ], // not in libicu
 231                 'vi' => [ "Ă", "Â", "Đ", "Ê", "Ô", "Ơ", "Ư" ],
 232                 'vo' => [ "Ä", "Ö", "Ü" ],
 233                 'yi' => [
 234                         "\xd7\x91\xd6\xbf", "\xd7\x9b\xd6\xbc", "\xd7\xa4\xd6\xbc",
 235                         "\xd7\xa9\xd7\x82", "\xd7\xaa\xd6\xbc"
 236                 ],
 237                 'yo' => [ "Ẹ", "Gb", "Ọ", "Ṣ" ],
 238                 'zu' => [],
 239         ];
 240
 241         /**
 242          * @since 1.16.3
 243          */
 244         const RECORD_LENGTH = 14;
 245
 246         public function __construct( $locale ) {
 247                 if ( !extension_loaded( 'intl' ) ) {
 248                         throw new MWException( 'An ICU collation was requested, ' .
 249                                 'but the intl extension is not available.' );
 250                 }
 251
 252                 $this->locale = $locale;
 253                 // Drop everything after the '@' in locale's name
 254                 $localeParts = explode( '@', $locale );
 255                 $this->digitTransformLanguage = Language::factory( $locale === 'root' ? 'en' : $localeParts[0] );
 256
 257                 $this->mainCollator = Collator::create( $locale );
 258                 if ( !$this->mainCollator ) {
 259                         throw new MWException( "Invalid ICU locale specified for collation: $locale" );
 260                 }
 261
 262                 $this->primaryCollator = Collator::create( $locale );
 263                 $this->primaryCollator->setStrength( Collator::PRIMARY );
 264
 265                 // If the special suffix for numeric collation is present, turn on numeric collation.
 266                 if ( substr( $locale, -5, 5 ) === '-u-kn' ) {
 267                         $this->useNumericCollation = true;
 268                         // Strip off the special suffix so it doesn't trip up fetchFirstLetterData().
 269                         $this->locale = substr( $this->locale, 0, -5 );
 270                         $this->mainCollator->setAttribute( Collator::NUMERIC_COLLATION, Collator::ON );
 271                         $this->primaryCollator->setAttribute( Collator::NUMERIC_COLLATION, Collator::ON );
 272                 }
 273         }
 274
 275         public function getSortKey( $string ) {
 276                 return $this->mainCollator->getSortKey( $string );
 277         }
 278
 279         public function getPrimarySortKey( $string ) {
 280                 return $this->primaryCollator->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( UtfNormal\Utils::utf8ToCodepoint( $firstChar ) ) ) {
 293                         return $firstChar;
 294                 }
 295
 296                 $sortKey = $this->getPrimarySortKey( $string );
 297
 298                 // Do a binary search to find the correct letter to sort under
 299                 $min = ArrayUtils::findLowerBound(
 300                         [ $this, 'getSortKeyByLetterIndex' ],
 301                         $this->getFirstLetterCount(),
 302                         'strcmp',
 303                         $sortKey );
 304
 305                 if ( $min === false ) {
 306                         // Before the first letter
 307                         return '';
 308                 }
 309
 310                 $sortLetter = $this->getLetterByIndex( $min );
 311
 312                 if ( $this->useNumericCollation ) {
 313                         // If the sort letter is a number, return '0–9' (or localized equivalent).
 314                         // ASCII value of 0 is 48. ASCII value of 9 is 57.
 315                         // Note that this also applies to non-Arabic numerals since they are
 316                         // mapped to Arabic numeral sort letters. For example, ২ sorts as 2.
 317                         if ( ord( $sortLetter ) >= 48 && ord( $sortLetter ) <= 57 ) {
 318                                 $sortLetter = wfMessage( 'category-header-numerals' )->numParams( 0, 9 )->text();
 319                         }
 320                 }
 321                 return $sortLetter;
 322         }
 323
 324         /**
 325          * @since 1.16.3
 326          * @return array
 327          */
 328         public function getFirstLetterData() {
 329                 if ( $this->firstLetterData === null ) {
 330                         $cache = ObjectCache::getLocalServerInstance( CACHE_ANYTHING );
 331                         $cacheKey = $cache->makeKey(
 332                                 'first-letters',
 333                                 static::class,
 334                                 $this->locale,
 335                                 $this->digitTransformLanguage->getCode(),
 336                                 self::getICUVersion(),
 337                                 self::FIRST_LETTER_VERSION
 338                         );
 339                         $this->firstLetterData = $cache->getWithSetCallback( $cacheKey, $cache::TTL_WEEK, function () {
 340                                 return $this->fetchFirstLetterData();
 341                         } );
 342                 }
 343                 return $this->firstLetterData;
 344         }
 345
 346         /**
 347          * @return array
 348          * @throws MWException
 349          */
 350         private function fetchFirstLetterData() {
 351                 // Generate data from serialized data file
 352                 if ( isset( self::$tailoringFirstLetters[$this->locale] ) ) {
 353                         $letters = wfGetPrecompiledData( 'first-letters-root.ser' );
 354                         // Append additional characters
 355                         $letters = array_merge( $letters, self::$tailoringFirstLetters[$this->locale] );
 356                         // Remove unnecessary ones, if any
 357                         if ( isset( self::$tailoringFirstLetters['-' . $this->locale] ) ) {
 358                                 $letters = array_diff( $letters, self::$tailoringFirstLetters['-' . $this->locale] );
 359                         }
 360                         // Apply digit transforms
 361                         $digits = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' ];
 362                         $letters = array_diff( $letters, $digits );
 363                         foreach ( $digits as $digit ) {
 364                                 $letters[] = $this->digitTransformLanguage->formatNum( $digit, true );
 365                         }
 366                 } else {
 367                         $letters = wfGetPrecompiledData( "first-letters-{$this->locale}.ser" );
 368                         if ( $letters === false ) {
 369                                 throw new MWException( "MediaWiki does not support ICU locale " .
 370                                         "\"{$this->locale}\"" );
 371                         }
 372                 }
 373
 374                 /* Sort the letters.
 375                  *
 376                  * It's impossible to have the precompiled data file properly sorted,
 377                  * because the sort order changes depending on ICU version. If the
 378                  * array is not properly sorted, the binary search will return random
 379                  * results.
 380                  *
 381                  * We also take this opportunity to remove primary collisions.
 382                  */
 383                 $letterMap = [];
 384                 foreach ( $letters as $letter ) {
 385                         $key = $this->getPrimarySortKey( $letter );
 386                         if ( isset( $letterMap[$key] ) ) {
 387                                 // Primary collision (two characters with the same sort position).
 388                                 // Keep whichever one sorts first in the main collator.
 389                                 $comp = $this->mainCollator->compare( $letter, $letterMap[$key] );
 390                                 wfDebug( "Primary collision '$letter' '{$letterMap[$key]}' (comparison: $comp)\n" );
 391                                 // If that also has a collision, use codepoint as a tiebreaker.
 392                                 if ( $comp === 0 ) {
 393                                         // TODO Use <=> operator when PHP 7 is allowed.
 394                                         $comp = UtfNormal\Utils::utf8ToCodepoint( $letter ) -
 395                                                 UtfNormal\Utils::utf8ToCodepoint( $letterMap[$key] );
 396                                 }
 397                                 if ( $comp < 0 ) {
 398                                         $letterMap[$key] = $letter;
 399                                 }
 400                         } else {
 401                                 $letterMap[$key] = $letter;
 402                         }
 403                 }
 404                 ksort( $letterMap, SORT_STRING );
 405
 406                 /* Remove duplicate prefixes. Basically if something has a sortkey
 407                  * which is a prefix of some other sortkey, then it is an
 408                  * expansion and probably should not be considered a section
 409                  * header.
 410                  *
 411                  * For example 'þ' is sometimes sorted as if it is the letters
 412                  * 'th'. Other times it is its own primary element. Another
 413                  * example is '₨'. Sometimes its a currency symbol. Sometimes it
 414                  * is an 'R' followed by an 's'.
 415                  *
 416                  * Additionally an expanded element should always sort directly
 417                  * after its first element due to they way sortkeys work.
 418                  *
 419                  * UCA sortkey elements are of variable length but no collation
 420                  * element should be a prefix of some other element, so I think
 421                  * this is safe. See:
 422                  * - https://ssl.icu-project.org/repos/icu/icuhtml/trunk/design/collation/ICU_collation_design.htm
 423                  * - http://site.icu-project.org/design/collation/uca-weight-allocation
 424                  *
 425                  * Additionally, there is something called primary compression to
 426                  * worry about. Basically, if you have two primary elements that
 427                  * are more than one byte and both start with the same byte then
 428                  * the first byte is dropped on the second primary. Additionally
 429                  * either \x03 or \xFF may be added to mean that the next primary
 430                  * does not start with the first byte of the first primary.
 431                  *
 432                  * This shouldn't matter much, as the first primary is not
 433                  * changed, and that is what we are comparing against.
 434                  *
 435                  * tl;dr: This makes some assumptions about how icu implements
 436                  * collations. It seems incredibly unlikely these assumptions
 437                  * will change, but nonetheless they are assumptions.
 438                  */
 439
 440                 $prev = false;
 441                 $duplicatePrefixes = [];
 442                 foreach ( $letterMap as $key => $value ) {
 443                         // Remove terminator byte. Otherwise the prefix
 444                         // comparison will get hung up on that.
 445                         $trimmedKey = rtrim( $key, "\0" );
 446                         if ( $prev === false || $prev === '' ) {
 447                                 $prev = $trimmedKey;
 448                                 // We don't yet have a collation element
 449                                 // to compare against, so continue.
 450                                 continue;
 451                         }
 452
 453                         // Due to the fact the array is sorted, we only have
 454                         // to compare with the element directly previous
 455                         // to the current element (skipping expansions).
 456                         // An element "X" will always sort directly
 457                         // before "XZ" (Unless we have "XY", but we
 458                         // do not update $prev in that case).
 459                         if ( substr( $trimmedKey, 0, strlen( $prev ) ) === $prev ) {
 460                                 $duplicatePrefixes[] = $key;
 461                                 // If this is an expansion, we don't want to
 462                                 // compare the next element to this element,
 463                                 // but to what is currently $prev
 464                                 continue;
 465                         }
 466                         $prev = $trimmedKey;
 467                 }
 468                 foreach ( $duplicatePrefixes as $badKey ) {
 469                         wfDebug( "Removing '{$letterMap[$badKey]}' from first letters.\n" );
 470                         unset( $letterMap[$badKey] );
 471                         // This code assumes that unsetting does not change sort order.
 472                 }
 473                 $data = [
 474                         'chars' => array_values( $letterMap ),
 475                         'keys' => array_keys( $letterMap ),
 476                 ];
 477
 478                 // Reduce memory usage before caching
 479                 unset( $letterMap );
 480
 481                 return $data;
 482         }
 483
 484         /**
 485          * @param string $index
 486          * @return string
 487          * @since 1.16.3
 488          */
 489         public function getLetterByIndex( $index ) {
 490                 return $this->getFirstLetterData()['chars'][$index];
 491         }
 492
 493         /**
 494          * @param string $index
 495          * @return string
 496          * @since 1.16.3
 497          */
 498         public function getSortKeyByLetterIndex( $index ) {
 499                 return $this->getFirstLetterData()['keys'][$index];
 500         }
 501
 502         /**
 503          * @return string
 504          * @since 1.16.3
 505          */
 506         public function getFirstLetterCount() {
 507                 return count( $this->getFirstLetterData()['chars'] );
 508         }
 509
 510         /**
 511          * Test if a code point is a CJK (Chinese, Japanese, Korean) character
 512          * @param int $codepoint
 513          * @return bool
 514          * @since 1.16.3
 515          */
 516         public static function isCjk( $codepoint ) {
 517                 foreach ( self::$cjkBlocks as $block ) {
 518                         if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
 519                                 return true;
 520                         }
 521                 }
 522                 return false;
 523         }
 524
 525         /**
 526          * Return the version of ICU library used by PHP's intl extension,
 527          * or false when the extension is not installed of the version
 528          * can't be determined.
 529          *
 530          * The constant INTL_ICU_VERSION this function refers to isn't really
 531          * documented. It is available since PHP 5.3.7 (see PHP 54561
 532          * https://bugs.php.net/bug.php?id=54561). This function will return
 533          * false on older PHPs.
 534          *
 535          * TODO: Remove the backwards-compatibility as MediaWiki now requires
 536          * higher levels of PHP.
 537          *
 538          * @since 1.21
 539          * @return string|bool
 540          */
 541         static function getICUVersion() {
 542                 return defined( 'INTL_ICU_VERSION' ) ? INTL_ICU_VERSION : false;
 543         }
 544
 545         /**
 546          * Return the version of Unicode appropriate for the version of ICU library
 547          * currently in use, or false when it can't be determined.
 548          *
 549          * @since 1.21
 550          * @return string|bool
 551          */
 552         static function getUnicodeVersionForICU() {
 553                 $icuVersion = self::getICUVersion();
 554                 if ( !$icuVersion ) {
 555                         return false;
 556                 }
 557
 558                 $versionPrefix = substr( $icuVersion, 0, 3 );
 559                 // Source: http://site.icu-project.org/download
 560                 $map = [
 561                         '59.' => '9.0',
 562                         '58.' => '9.0',
 563                         '57.' => '8.0',
 564                         '56.' => '8.0',
 565                         '55.' => '7.0',
 566                         '54.' => '7.0',
 567                         '53.' => '6.3',
 568                         '52.' => '6.3',
 569                         '51.' => '6.2',
 570                         '50.' => '6.2',
 571                         '49.' => '6.1',
 572                         '4.8' => '6.0',
 573                         '4.6' => '6.0',
 574                         '4.4' => '5.2',
 575                         '4.2' => '5.1',
 576                         '4.0' => '5.1',
 577                         '3.8' => '5.0',
 578                         '3.6' => '5.0',
 579                         '3.4' => '4.1',
 580                 ];
 581
 582                 if ( isset( $map[$versionPrefix] ) ) {
 583                         return $map[$versionPrefix];
 584                 } else {
 585                         return false;
 586                 }
 587         }
 588 }