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.
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.
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
24 class IcuCollation
extends Collation
{
25 const FIRST_LETTER_VERSION
= 3;
28 private $primaryCollator;
31 private $mainCollator;
37 protected $digitTransformLanguage;
40 private $useNumericCollation = false;
43 private $firstLetterData;
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.
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
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 '-').
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).
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.
86 * Initially generated based on the primary level of Unicode collation
87 * tailorings available at http://developer.mimer.com/charts/tailorings.htm ,
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.
93 private static $tailoringFirstLetters = [
97 'as' => [ "\u{0982}", "\u{0981}", "\u{0983}", "\u{09CE}", "ক্ষ " ],
98 'ast' => [ "Ch", "Ll", "Ñ" ], // not in libicu
99 'az' => [ "Ç", "Ə", "Ğ", "İ", "Ö", "Ş", "Ü" ],
101 'be-tarask' => [ "Ё" ],
103 'bn' => [ 'ং', 'ঃ', 'ঁ' ],
104 'bn@collation=traditional' => [
105 'ং', 'ঃ', 'ঁ', 'ক্', 'খ্', 'গ্', 'ঘ্', 'ঙ্', 'চ্', 'ছ্', 'জ্', 'ঝ্',
106 'ঞ্', 'ট্', 'ঠ্', 'ড্', 'ঢ্', 'ণ্', 'ৎ', 'থ্', 'দ্', 'ধ্', 'ন্', 'প্',
107 'ফ্', 'ব্', 'ভ্', 'ম্', 'য্', 'র্', 'ৰ্', 'ল্', 'ৱ্', 'শ্', 'ষ্', 'স্', 'হ্'
110 'br' => [ "Ch", "C'h" ],
111 'bs' => [ "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ],
115 'co' => [], // not in libicu
116 'cs' => [ "Č", "Ch", "Ř", "Š", "Ž" ],
117 'cy' => [ "Ch", "Dd", "Ff", "Ng", "Ll", "Ph", "Rh", "Th" ],
118 'da' => [ "Æ", "Ø", "Å" ],
120 'de-AT@collation=phonebook' => [ 'ä', 'ö', 'ü', 'ß' ],
121 'dsb' => [ "Č", "Ć", "Dź", "Ě", "Ch", "Ł", "Ń", "Ŕ", "Š", "Ś", "Ž", "Ź" ],
122 'ee' => [ "Dz", "Ɖ", "Ɛ", "Ƒ", "Gb", "Ɣ", "Kp", "Ny", "Ŋ", "Ɔ", "Ts", "Ʋ" ],
125 'eo' => [ "Ĉ", "Ĝ", "Ĥ", "Ĵ", "Ŝ", "Ŭ" ],
127 'et' => [ "Š", "Ž", "Õ", "Ä", "Ö", "Ü" ],
128 'eu' => [ "Ñ" ], // not in libicu
130 // RTL, let's put each letter on a new line
137 'fi' => [ "Å", "Ä", "Ö" ],
138 'fil' => [ "Ñ", "Ng" ],
139 'fo' => [ "Á", "Ð", "Í", "Ó", "Ú", "Ý", "Æ", "Ø", "Å" ],
141 'fr-CA' => [], // fr-CA sorts accents slightly different from fr.
142 'fur' => [ "À", "Á", "Â", "È", "Ì", "Ò", "Ù" ], // not in libicu
143 'fy' => [], // not in libicu
145 'gd' => [], // not in libicu
146 'gl' => [ "Ch", "Ll", "Ñ" ],
147 'gu' => [ "\u{0A82}", "\u{0A83}", "\u{0A81}", "\u{0AB3}" ],
148 'ha' => [ 'Ɓ', 'Ɗ', 'Ƙ', 'Sh', 'Ts', 'Ƴ' ],
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" ],
157 'ig' => [ "Ch", "Gb", "Gh", "Gw", "Ị", "Kp", "Kw", "Ṅ", "Nw", "Ny", "Ọ", "Sh", "Ụ" ],
158 'is' => [ "Á", "Ð", "É", "Í", "Ó", "Ú", "Ý", "Þ", "Æ", "Ö", "Å" ],
161 'kk' => [ "Ү", "І" ],
162 'kl' => [ "Æ", "Ø", "Å" ],
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}",
169 'kn' => [ "\u{0C81}", "\u{0C83}", "\u{0CF1}", "\u{0CF2}" ],
170 'kok' => [ "\u{0902}", "\u{0903}", "ळ", "क्ष" ],
171 'ku' => [ "Ç", "Ê", "Î", "Ş", "Û" ], // not in libicu
173 'la' => [], // not in libicu
175 'lkt' => [ 'Č', 'Ǧ', 'Ȟ', 'Š', 'Ž' ],
178 'lt' => [ "Č", "Š", "Ž" ],
179 'lv' => [ "Č", "Ģ", "Ķ", "Ļ", "Ņ", "Š", "Ž" ],
180 'mk' => [ "Ѓ", "Ќ" ],
183 'mo' => [ "Ă", "Â", "Î", "Ș", "Ț" ], // not in libicu
184 'mr' => [ "\u{0902}", "\u{0903}", "ळ", "क्ष", "ज्ञ" ],
186 'mt' => [ "Ċ", "Ġ", "Għ", "Ħ", "Ż" ],
187 'nb' => [ "Æ", "Ø", "Å" ],
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' => [ "Ą", "Ć", "Ę", "Ł", "Ń", "Ó", "Ś", "Ź", "Ż" ],
198 'rm' => [], // not in libicu
199 'ro' => [ "Ă", "Â", "Î", "Ș", "Ț" ],
201 'rup' => [ "Ă", "Â", "Î", "Ľ", "Ń", "Ș", "Ț" ], // not in libicu
204 'Á', 'Č', 'Ʒ', 'Ǯ', 'Đ', 'Ǧ', 'Ǥ', 'Ǩ', 'Ŋ',
205 'Š', 'Ŧ', 'Ž', 'Ø', 'Æ', 'Ȧ', 'Ä', 'Ö'
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" ],
213 'sr-Latn' => [ "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ],
214 'sv' => [ "Å", "Ä", "Ö" ],
215 'sv@collation=standard' => [ "Å", "Ä", "Ö" ],
218 "\u{0B82}", "ஃ", "க்ஷ", "க்", "ங்", "ச்", "ஞ்", "ட்", "ண்", "த்", "ந்",
219 "ப்", "ம்", "ய்", "ர்", "ல்", "வ்", "ழ்", "ள்", "ற்", "ன்", "ஜ்", "ஶ்", "ஷ்",
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 'tt' => [ "Ә", "Ө", "Ү", "Җ", "Ң", "Һ" ], // not in libicu
229 'uk' => [ "Ґ", "Ь" ],
230 'uz' => [ "Ch", "G'", "Ng", "O'", "Sh" ], // not in libicu
231 'vi' => [ "Ă", "Â", "Đ", "Ê", "Ô", "Ơ", "Ư" ],
232 'vo' => [ "Ä", "Ö", "Ü" ],
234 "\u{05D1}\u{05BF}", "\u{05DB}\u{05BC}", "\u{05E4}\u{05BC}",
235 "\u{05E9}\u{05C2}", "\u{05EA}\u{05BC}"
237 'yo' => [ "Ẹ", "Gb", "Ọ", "Ṣ" ],
244 const RECORD_LENGTH
= 14;
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.' );
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] );
257 $this->mainCollator
= Collator
::create( $locale );
258 if ( !$this->mainCollator
) {
259 throw new MWException( "Invalid ICU locale specified for collation: $locale" );
262 $this->primaryCollator
= Collator
::create( $locale );
263 $this->primaryCollator
->setStrength( Collator
::PRIMARY
);
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
);
275 public function getSortKey( $string ) {
276 return $this->mainCollator
->getSortKey( $string );
279 public function getPrimarySortKey( $string ) {
280 return $this->primaryCollator
->getSortKey( $string );
283 public function getFirstLetter( $string ) {
284 $string = strval( $string );
285 if ( $string === '' ) {
289 $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
291 // If the first character is a CJK character, just return that character.
292 if ( ord( $firstChar ) > 0x7f && self
::isCjk( UtfNormal\Utils
::utf8ToCodepoint( $firstChar ) ) ) {
296 $sortKey = $this->getPrimarySortKey( $string );
298 // Do a binary search to find the correct letter to sort under
299 $min = ArrayUtils
::findLowerBound(
300 [ $this, 'getSortKeyByLetterIndex' ],
301 $this->getFirstLetterCount(),
305 if ( $min === false ) {
306 // Before the first letter
310 $sortLetter = $this->getLetterByIndex( $min );
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();
328 public function getFirstLetterData() {
329 if ( $this->firstLetterData
=== null ) {
330 $cache = ObjectCache
::getLocalServerInstance( CACHE_ANYTHING
);
331 $cacheKey = $cache->makeKey(
335 $this->digitTransformLanguage
->getCode(),
337 self
::FIRST_LETTER_VERSION
339 $this->firstLetterData
= $cache->getWithSetCallback( $cacheKey, $cache::TTL_WEEK
, function () {
340 return $this->fetchFirstLetterData();
343 return $this->firstLetterData
;
348 * @throws MWException
350 private function fetchFirstLetterData() {
352 // Generate data from serialized data file
353 if ( isset( self
::$tailoringFirstLetters[$this->locale
] ) ) {
354 $letters = require "$IP/includes/collation/data/first-letters-root.php";
355 // Append additional characters
356 $letters = array_merge( $letters, self
::$tailoringFirstLetters[$this->locale
] );
357 // Remove unnecessary ones, if any
358 if ( isset( self
::$tailoringFirstLetters['-' . $this->locale
] ) ) {
359 $letters = array_diff( $letters, self
::$tailoringFirstLetters['-' . $this->locale
] );
361 // Apply digit transforms
362 $digits = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' ];
363 $letters = array_diff( $letters, $digits );
364 foreach ( $digits as $digit ) {
365 $letters[] = $this->digitTransformLanguage
->formatNum( $digit, true );
368 if ( $this->locale
=== 'root' ) {
369 $letters = require "$IP/includes/collation/data/first-letters-root.php";
371 // FIXME: Is this still used?
372 $letters = wfGetPrecompiledData( "first-letters-{$this->locale}.ser" );
373 if ( $letters === false ) {
374 throw new MWException( "MediaWiki does not support ICU locale " .
375 "\"{$this->locale}\"" );
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
387 * We also take this opportunity to remove primary collisions.
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)\n" );
397 // If that also has a collision, use codepoint as a tiebreaker.
399 $comp = UtfNormal\Utils
::utf8ToCodepoint( $letter ) <=>
400 UtfNormal\Utils
::utf8ToCodepoint( $letterMap[$key] );
403 $letterMap[$key] = $letter;
406 $letterMap[$key] = $letter;
409 ksort( $letterMap, SORT_STRING
);
411 /* Remove duplicate prefixes. Basically if something has a sortkey
412 * which is a prefix of some other sortkey, then it is an
413 * expansion and probably should not be considered a section
416 * For example 'þ' is sometimes sorted as if it is the letters
417 * 'th'. Other times it is its own primary element. Another
418 * example is '₨'. Sometimes its a currency symbol. Sometimes it
419 * is an 'R' followed by an 's'.
421 * Additionally an expanded element should always sort directly
422 * after its first element due to they way sortkeys work.
424 * UCA sortkey elements are of variable length but no collation
425 * element should be a prefix of some other element, so I think
427 * - https://ssl.icu-project.org/repos/icu/icuhtml/trunk/design/collation/ICU_collation_design.htm
428 * - http://site.icu-project.org/design/collation/uca-weight-allocation
430 * Additionally, there is something called primary compression to
431 * worry about. Basically, if you have two primary elements that
432 * are more than one byte and both start with the same byte then
433 * the first byte is dropped on the second primary. Additionally
434 * either \x03 or \xFF may be added to mean that the next primary
435 * does not start with the first byte of the first primary.
437 * This shouldn't matter much, as the first primary is not
438 * changed, and that is what we are comparing against.
440 * tl;dr: This makes some assumptions about how icu implements
441 * collations. It seems incredibly unlikely these assumptions
442 * will change, but nonetheless they are assumptions.
446 $duplicatePrefixes = [];
447 foreach ( $letterMap as $key => $value ) {
448 // Remove terminator byte. Otherwise the prefix
449 // comparison will get hung up on that.
450 $trimmedKey = rtrim( $key, "\0" );
451 if ( $prev === false ||
$prev === '' ) {
453 // We don't yet have a collation element
454 // to compare against, so continue.
458 // Due to the fact the array is sorted, we only have
459 // to compare with the element directly previous
460 // to the current element (skipping expansions).
461 // An element "X" will always sort directly
462 // before "XZ" (Unless we have "XY", but we
463 // do not update $prev in that case).
464 if ( substr( $trimmedKey, 0, strlen( $prev ) ) === $prev ) {
465 $duplicatePrefixes[] = $key;
466 // If this is an expansion, we don't want to
467 // compare the next element to this element,
468 // but to what is currently $prev
473 foreach ( $duplicatePrefixes as $badKey ) {
474 wfDebug( "Removing '{$letterMap[$badKey]}' from first letters.\n" );
475 unset( $letterMap[$badKey] );
476 // This code assumes that unsetting does not change sort order.
479 'chars' => array_values( $letterMap ),
480 'keys' => array_keys( $letterMap ),
483 // Reduce memory usage before caching
490 * @param string $index
494 public function getLetterByIndex( $index ) {
495 return $this->getFirstLetterData()['chars'][$index];
499 * @param string $index
503 public function getSortKeyByLetterIndex( $index ) {
504 return $this->getFirstLetterData()['keys'][$index];
511 public function getFirstLetterCount() {
512 return count( $this->getFirstLetterData()['chars'] );
516 * Test if a code point is a CJK (Chinese, Japanese, Korean) character
517 * @param int $codepoint
521 public static function isCjk( $codepoint ) {
522 foreach ( self
::$cjkBlocks as $block ) {
523 if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
531 * Return the version of ICU library used by PHP's intl extension,
532 * or false when the extension is not installed of the version
533 * can't be determined.
535 * The constant INTL_ICU_VERSION this function refers to isn't really
536 * documented, but see https://bugs.php.net/bug.php?id=54561.
539 * @deprecated since 1.32, use INTL_ICU_VERSION directly
542 static function getICUVersion() {
543 wfDeprecated( __METHOD__
, '1.32' );
544 return INTL_ICU_VERSION
;
548 * Return the version of Unicode appropriate for the version of ICU library
549 * currently in use, or false when it can't be determined.
552 * @return string|bool
554 static function getUnicodeVersionForICU() {
555 $icuVersion = INTL_ICU_VERSION
;
556 if ( !$icuVersion ) {
560 $versionPrefix = substr( $icuVersion, 0, 3 );
561 // Source: http://site.icu-project.org/download
588 return $map[$versionPrefix] ??
false;