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
= 4;
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' => [ "Ç", "Ğ", "İ", "Ö", "Ş", "Ü" ],
229 'tt' => [ "Ә", "Ө", "Ү", "Җ", "Ң", "Һ" ], // not in libicu
230 'uk' => [ "Ґ", "Ь" ],
231 'uz' => [ "Ch", "G'", "Ng", "O'", "Sh" ], // not in libicu
232 'vi' => [ "Ă", "Â", "Đ", "Ê", "Ô", "Ơ", "Ư" ],
233 'vo' => [ "Ä", "Ö", "Ü" ],
235 "\u{05D1}\u{05BF}", "\u{05DB}\u{05BC}", "\u{05E4}\u{05BC}",
236 "\u{05E9}\u{05C2}", "\u{05EA}\u{05BC}"
238 'yo' => [ "Ẹ", "Gb", "Ọ", "Ṣ" ],
245 const RECORD_LENGTH
= 14;
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.' );
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] );
258 $this->mainCollator
= Collator
::create( $locale );
259 if ( !$this->mainCollator
) {
260 throw new MWException( "Invalid ICU locale specified for collation: $locale" );
263 $this->primaryCollator
= Collator
::create( $locale );
264 $this->primaryCollator
->setStrength( Collator
::PRIMARY
);
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
);
276 public function getSortKey( $string ) {
277 return $this->mainCollator
->getSortKey( $string );
280 public function getPrimarySortKey( $string ) {
281 return $this->primaryCollator
->getSortKey( $string );
284 public function getFirstLetter( $string ) {
285 $string = strval( $string );
286 if ( $string === '' ) {
290 $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
292 // If the first character is a CJK character, just return that character.
293 if ( ord( $firstChar ) > 0x7f && self
::isCjk( UtfNormal\Utils
::utf8ToCodepoint( $firstChar ) ) ) {
297 $sortKey = $this->getPrimarySortKey( $string );
299 // Do a binary search to find the correct letter to sort under
300 $min = ArrayUtils
::findLowerBound(
301 [ $this, 'getSortKeyByLetterIndex' ],
302 $this->getFirstLetterCount(),
306 if ( $min === false ) {
307 // Before the first letter
311 $sortLetter = $this->getLetterByIndex( $min );
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();
329 public function getFirstLetterData() {
330 if ( $this->firstLetterData
=== null ) {
331 $cache = ObjectCache
::getLocalServerInstance( CACHE_ANYTHING
);
332 $cacheKey = $cache->makeKey(
336 $this->digitTransformLanguage
->getCode(),
338 self
::FIRST_LETTER_VERSION
340 $this->firstLetterData
= $cache->getWithSetCallback( $cacheKey, $cache::TTL_WEEK
, function () {
341 return $this->fetchFirstLetterData();
344 return $this->firstLetterData
;
349 * @throws MWException
351 private function fetchFirstLetterData() {
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
] );
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 );
369 if ( $this->locale
=== 'root' ) {
370 $letters = require "$IP/includes/collation/data/first-letters-root.php";
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}\"" );
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
388 * We also take this opportunity to remove primary collisions.
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.
400 $comp = UtfNormal\Utils
::utf8ToCodepoint( $letter ) <=>
401 UtfNormal\Utils
::utf8ToCodepoint( $letterMap[$key] );
404 $letterMap[$key] = $letter;
407 $letterMap[$key] = $letter;
410 ksort( $letterMap, SORT_STRING
);
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
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'.
422 * Additionally an expanded element should always sort directly
423 * after its first element due to they way sortkeys work.
425 * UCA sortkey elements are of variable length but no collation
426 * element should be a prefix of some other element, so I think
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
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.
438 * This shouldn't matter much, as the first primary is not
439 * changed, and that is what we are comparing against.
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.
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 === '' ) {
454 // We don't yet have a collation element
455 // to compare against, so continue.
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
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.
480 'chars' => array_values( $letterMap ),
481 'keys' => array_keys( $letterMap ),
484 // Reduce memory usage before caching
491 * @param string $index
495 public function getLetterByIndex( $index ) {
496 return $this->getFirstLetterData()['chars'][$index];
500 * @param string $index
504 public function getSortKeyByLetterIndex( $index ) {
505 return $this->getFirstLetterData()['keys'][$index];
512 public function getFirstLetterCount() {
513 return count( $this->getFirstLetterData()['chars'] );
517 * Test if a code point is a CJK (Chinese, Japanese, Korean) character
518 * @param int $codepoint
522 public static function isCjk( $codepoint ) {
523 foreach ( self
::$cjkBlocks as $block ) {
524 if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
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.
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.
540 * @deprecated since 1.32, use INTL_ICU_VERSION directly
543 static function getICUVersion() {
544 wfDeprecated( __METHOD__
, '1.32' );
545 return INTL_ICU_VERSION
;
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.
553 * @return string|bool
555 static function getUnicodeVersionForICU() {
556 $icuVersion = INTL_ICU_VERSION
;
557 if ( !$icuVersion ) {
561 $versionPrefix = substr( $icuVersion, 0, 3 );
562 // Source: http://site.icu-project.org/download
589 return $map[$versionPrefix] ??
false;