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 use MediaWiki\Language\Language;
  22 use MediaWiki\Languages\LanguageFactory;
  23 use MediaWiki\MediaWikiServices;
  24
  25 /**
  26  * @since 1.16.3
  27  */
  28 class IcuCollation extends Collation {
  29         private const FIRST_LETTER_VERSION = 4;
  30
  31         /** @var Collator */
  32         private $primaryCollator;
  33
  34         /** @var Collator */
  35         private $mainCollator;
  36
  37         /** @var string */
  38         private $locale;
  39
  40         /** @var Language */
  41         protected $digitTransformLanguage;
  42
  43         /** @var bool */
  44         private $useNumericCollation = false;
  45
  46         /** @var array */
  47         private $firstLetterData;
  48
  49         /**
  50          * Unified CJK blocks.
  51          *
  52          * The same definition of a CJK block must be used for both Collation and
  53          * generateCollationData.php. These blocks are omitted from the first
  54          * letter data, as an optimisation measure and because the default UCA table
  55          * is pretty useless for sorting Chinese text anyway. Japanese and Korean
  56          * blocks are not included here, because they are smaller and more useful.
  57          */
  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
  76         /**
  77          * Additional characters (or character groups) to be considered separate
  78          * letters for given languages, or to be removed from the list of such
  79          * letters (denoted by keys starting with '-').
  80          *
  81          * These are additions to (or subtractions from) the data stored in the
  82          * first-letters-root.php data file (which among others includes full basic
  83          * Latin, Cyrillic and Greek alphabets).
  84          *
  85          * "Separate letter" is a letter that would have a separate heading/section
  86          * for it in a dictionary or a phone book in this language. This data isn't
  87          * used for sorting (the ICU library handles that), only for deciding which
  88          * characters (or character groups) to use as headings.
  89          *
  90          * Initially generated based on the primary level of Unicode collation
  91          * tailorings available at http://developer.mimer.com/charts/tailorings.htm ,
  92          * later modified.
  93          *
  94          * Empty arrays are intended; this signifies that the data for the language is
  95          * available and that there are, in fact, no additional letters to consider.
  96          */
  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' => [ 'Č', 'Ǧ', 'Ȟ', 'Š', 'Ž' ],
 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
 246         /**
 247          * @param LanguageFactory $languageFactory
 248          * @param string $locale
 249          */
 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
 333         /**
 334          * @since 1.16.3
 335          * @return array
 336          */
 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
 356         /**
 357          * @return array
 358          */
 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
 475         /**
 476          * Test if a code point is a CJK (Chinese, Japanese, Korean) character
 477          * @param int $codepoint
 478          * @return bool
 479          * @since 1.16.3
 480          */
 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 }