MediaWiki  REL1_22
Collation.php
Go to the documentation of this file.
00001 <?php
00023 abstract class Collation {
00024     static $instance;
00025 
00029     static function singleton() {
00030         if ( !self::$instance ) {
00031             global $wgCategoryCollation;
00032             self::$instance = self::factory( $wgCategoryCollation );
00033         }
00034         return self::$instance;
00035     }
00036 
00042     static function factory( $collationName ) {
00043         switch ( $collationName ) {
00044             case 'uppercase':
00045                 return new UppercaseCollation;
00046             case 'identity':
00047                 return new IdentityCollation;
00048             case 'uca-default':
00049                 return new IcuCollation( 'root' );
00050             default:
00051                 $match = array();
00052                 if ( preg_match( '/^uca-([a-z@=-]+)$/', $collationName, $match ) ) {
00053                     return new IcuCollation( $match[1] );
00054                 }
00055 
00056                 # Provide a mechanism for extensions to hook in.
00057                 $collationObject = null;
00058                 wfRunHooks( 'Collation::factory', array( $collationName, &$collationObject ) );
00059 
00060                 if ( $collationObject instanceof Collation ) {
00061                     return $collationObject;
00062                 }
00063 
00064                 // If all else fails...
00065                 throw new MWException( __METHOD__ . ": unknown collation type \"$collationName\"" );
00066         }
00067     }
00068 
00080     abstract function getSortKey( $string );
00081 
00105     abstract function getFirstLetter( $string );
00106 }
00107 
00108 class UppercaseCollation extends Collation {
00109     var $lang;
00110     function __construct() {
00111         // Get a language object so that we can use the generic UTF-8 uppercase
00112         // function there
00113         $this->lang = Language::factory( 'en' );
00114     }
00115 
00116     function getSortKey( $string ) {
00117         return $this->lang->uc( $string );
00118     }
00119 
00120     function getFirstLetter( $string ) {
00121         if ( $string[0] == "\0" ) {
00122             $string = substr( $string, 1 );
00123         }
00124         return $this->lang->ucfirst( $this->lang->firstChar( $string ) );
00125     }
00126 }
00127 
00134 class IdentityCollation extends Collation {
00135 
00136     function getSortKey( $string ) {
00137         return $string;
00138     }
00139 
00140     function getFirstLetter( $string ) {
00141         global $wgContLang;
00142         // Copied from UppercaseCollation.
00143         // I'm kind of unclear on when this could happen...
00144         if ( $string[0] == "\0" ) {
00145             $string = substr( $string, 1 );
00146         }
00147         return $wgContLang->firstChar( $string );
00148     }
00149 }
00150 
00151 class IcuCollation extends Collation {
00152     const FIRST_LETTER_VERSION = 1;
00153 
00154     var $primaryCollator, $mainCollator, $locale;
00155     var $firstLetterData;
00156 
00166     static $cjkBlocks = array(
00167         array( 0x2E80, 0x2EFF ), // CJK Radicals Supplement
00168         array( 0x2F00, 0x2FDF ), // Kangxi Radicals
00169         array( 0x2FF0, 0x2FFF ), // Ideographic Description Characters
00170         array( 0x3000, 0x303F ), // CJK Symbols and Punctuation
00171         array( 0x31C0, 0x31EF ), // CJK Strokes
00172         array( 0x3200, 0x32FF ), // Enclosed CJK Letters and Months
00173         array( 0x3300, 0x33FF ), // CJK Compatibility
00174         array( 0x3400, 0x4DBF ), // CJK Unified Ideographs Extension A
00175         array( 0x4E00, 0x9FFF ), // CJK Unified Ideographs
00176         array( 0xF900, 0xFAFF ), // CJK Compatibility Ideographs
00177         array( 0xFE30, 0xFE4F ), // CJK Compatibility Forms
00178         array( 0x20000, 0x2A6DF ), // CJK Unified Ideographs Extension B
00179         array( 0x2A700, 0x2B73F ), // CJK Unified Ideographs Extension C
00180         array( 0x2B740, 0x2B81F ), // CJK Unified Ideographs Extension D
00181         array( 0x2F800, 0x2FA1F ), // CJK Compatibility Ideographs Supplement
00182     );
00183 
00205     static $tailoringFirstLetters = array(
00206         // Verified by native speakers
00207         'be' => array( "Ё" ),
00208         'be-tarask' => array( "Ё" ),
00209         'en' => array(),
00210         'fi' => array( "Å", "Ä", "Ö" ),
00211         'hu' => array( "Cs", "Dz", "Dzs", "Gy", "Ly", "Ny", "Ö", "Sz", "Ty", "Ü", "Zs" ),
00212         'it' => array(),
00213         'pl' => array( "Ą", "Ć", "Ę", "Ł", "Ń", "Ó", "Ś", "Ź", "Ż" ),
00214         'pt' => array(),
00215         'ru' => array(),
00216         'sv' => array( "Å", "Ä", "Ö" ),
00217         'sv@collation=standard' => array( "Å", "Ä", "Ö" ),
00218         'uk' => array( "Ґ", "Ь" ),
00219         'vi' => array( "Ă", "Â", "Đ", "Ê", "Ô", "Ơ", "Ư" ),
00220         // Not verified, but likely correct
00221         'af' => array(),
00222         'ast' => array( "Ch", "Ll", "Ñ" ),
00223         'az' => array( "Ç", "Ə", "Ğ", "İ", "Ö", "Ş", "Ü" ),
00224         'bg' => array(),
00225         'br' => array( "Ch", "C'h" ),
00226         'bs' => array( "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ),
00227         'ca' => array(),
00228         'co' => array(),
00229         'cs' => array( "Č", "Ch", "Ř", "Š", "Ž" ),
00230         'cy' => array( "Ch", "Dd", "Ff", "Ng", "Ll", "Ph", "Rh", "Th" ),
00231         'da' => array( "Æ", "Ø", "Å" ),
00232         'de' => array(),
00233         'dsb' => array( "Č", "Ć", "Dź", "Ě", "Ch", "Ł", "Ń", "Ŕ", "Š", "Ś", "Ž", "Ź" ),
00234         'el' => array(),
00235         'eo' => array( "Ĉ", "Ĝ", "Ĥ", "Ĵ", "Ŝ", "Ŭ" ),
00236         'es' => array( "Ñ" ),
00237         'et' => array( "Š", "Ž", "Õ", "Ä", "Ö", "Ü" ),
00238         'eu' => array( "Ñ" ),
00239         'fa' => array( "آ", "ء", "ه" ),
00240         'fo' => array( "Á", "Ð", "Í", "Ó", "Ú", "Ý", "Æ", "Ø", "Å" ),
00241         'fr' => array(),
00242         'fur' => array( "À", "Á", "Â", "È", "Ì", "Ò", "Ù" ),
00243         'fy' => array(),
00244         'ga' => array(),
00245         'gd' => array(),
00246         'gl' => array( "Ch", "Ll", "Ñ" ),
00247         'hr' => array( "Č", "Ć", "Dž", "Đ", "Lj", "Nj", "Š", "Ž" ),
00248         'hsb' => array( "Č", "Dź", "Ě", "Ch", "Ł", "Ń", "Ř", "Š", "Ć", "Ž" ),
00249         'is' => array( "Á", "Ð", "É", "Í", "Ó", "Ú", "Ý", "Þ", "Æ", "Ö", "Å" ),
00250         'kk' => array( "Ү", "І" ),
00251         'kl' => array( "Æ", "Ø", "Å" ),
00252         'ku' => array( "Ç", "Ê", "Î", "Ş", "Û" ),
00253         'ky' => array( "Ё" ),
00254         'la' => array(),
00255         'lb' => array(),
00256         'lt' => array( "Č", "Š", "Ž" ),
00257         'lv' => array( "Č", "Ģ", "Ķ", "Ļ", "Ņ", "Š", "Ž" ),
00258         'mk' => array(),
00259         'mo' => array( "Ă", "Â", "Î", "Ş", "Ţ" ),
00260         'mt' => array( "Ċ", "Ġ", "Għ", "Ħ", "Ż" ),
00261         'nl' => array(),
00262         'no' => array( "Æ", "Ø", "Å" ),
00263         'oc' => array(),
00264         'rm' => array(),
00265         'ro' => array( "Ă", "Â", "Î", "Ş", "Ţ" ),
00266         'rup' => array( "Ă", "Â", "Î", "Ľ", "Ń", "Ş", "Ţ" ),
00267         'sco' => array(),
00268         'sk' => array( "Ä", "Č", "Ch", "Ô", "Š", "Ž" ),
00269         'sl' => array( "Č", "Š", "Ž" ),
00270         'smn' => array( "Á", "Č", "Đ", "Ŋ", "Š", "Ŧ", "Ž", "Æ", "Ø", "Å", "Ä", "Ö" ),
00271         'sq' => array( "Ç", "Dh", "Ë", "Gj", "Ll", "Nj", "Rr", "Sh", "Th", "Xh", "Zh" ),
00272         'sr' => array(),
00273         'tk' => array( "Ç", "Ä", "Ž", "Ň", "Ö", "Ş", "Ü", "Ý" ),
00274         'tl' => array( "Ñ", "Ng" ),
00275         'tr' => array( "Ç", "Ğ", "İ", "Ö", "Ş", "Ü" ),
00276         'tt' => array( "Ә", "Ө", "Ү", "Җ", "Ң", "Һ" ),
00277         'uz' => array( "Ch", "G'", "Ng", "O'", "Sh" ),
00278     );
00279 
00280     const RECORD_LENGTH = 14;
00281 
00282     function __construct( $locale ) {
00283         if ( !extension_loaded( 'intl' ) ) {
00284             throw new MWException( 'An ICU collation was requested, ' .
00285                 'but the intl extension is not available.' );
00286         }
00287         $this->locale = $locale;
00288         $this->mainCollator = Collator::create( $locale );
00289         if ( !$this->mainCollator ) {
00290             throw new MWException( "Invalid ICU locale specified for collation: $locale" );
00291         }
00292 
00293         $this->primaryCollator = Collator::create( $locale );
00294         $this->primaryCollator->setStrength( Collator::PRIMARY );
00295     }
00296 
00297     function getSortKey( $string ) {
00298         // intl extension produces non null-terminated
00299         // strings. Appending '' fixes it so that it doesn't generate
00300         // a warning on each access in debug php.
00301         wfSuppressWarnings();
00302         $key = $this->mainCollator->getSortKey( $string ) . '';
00303         wfRestoreWarnings();
00304         return $key;
00305     }
00306 
00307     function getPrimarySortKey( $string ) {
00308         wfSuppressWarnings();
00309         $key = $this->primaryCollator->getSortKey( $string ) . '';
00310         wfRestoreWarnings();
00311         return $key;
00312     }
00313 
00314     function getFirstLetter( $string ) {
00315         $string = strval( $string );
00316         if ( $string === '' ) {
00317             return '';
00318         }
00319 
00320         // Check for CJK
00321         $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
00322         if ( ord( $firstChar ) > 0x7f
00323             && self::isCjk( utf8ToCodepoint( $firstChar ) ) )
00324         {
00325             return $firstChar;
00326         }
00327 
00328         $sortKey = $this->getPrimarySortKey( $string );
00329 
00330         // Do a binary search to find the correct letter to sort under
00331         $min = $this->findLowerBound(
00332             array( $this, 'getSortKeyByLetterIndex' ),
00333             $this->getFirstLetterCount(),
00334             'strcmp',
00335             $sortKey );
00336 
00337         if ( $min === false ) {
00338             // Before the first letter
00339             return '';
00340         }
00341         return $this->getLetterByIndex( $min );
00342     }
00343 
00344     function getFirstLetterData() {
00345         if ( $this->firstLetterData !== null ) {
00346             return $this->firstLetterData;
00347         }
00348 
00349         $cache = wfGetCache( CACHE_ANYTHING );
00350         $cacheKey = wfMemcKey( 'first-letters', $this->locale );
00351         $cacheEntry = $cache->get( $cacheKey );
00352 
00353         if ( $cacheEntry && isset( $cacheEntry['version'] )
00354             && $cacheEntry['version'] == self::FIRST_LETTER_VERSION
00355         ) {
00356             $this->firstLetterData = $cacheEntry;
00357             return $this->firstLetterData;
00358         }
00359 
00360         // Generate data from serialized data file
00361 
00362         if ( isset( self::$tailoringFirstLetters[$this->locale] ) ) {
00363             $letters = wfGetPrecompiledData( "first-letters-root.ser" );
00364             // Append additional characters
00365             $letters = array_merge( $letters, self::$tailoringFirstLetters[$this->locale] );
00366             // Remove unnecessary ones, if any
00367             if ( isset( self::$tailoringFirstLetters['-' . $this->locale] ) ) {
00368                 $letters = array_diff( $letters, self::$tailoringFirstLetters['-' . $this->locale] );
00369             }
00370         } else {
00371             $letters = wfGetPrecompiledData( "first-letters-{$this->locale}.ser" );
00372             if ( $letters === false ) {
00373                 throw new MWException( "MediaWiki does not support ICU locale " .
00374                     "\"{$this->locale}\"" );
00375             }
00376         }
00377 
00378         // Sort the letters.
00379         //
00380         // It's impossible to have the precompiled data file properly sorted,
00381         // because the sort order changes depending on ICU version. If the
00382         // array is not properly sorted, the binary search will return random
00383         // results.
00384         //
00385         // We also take this opportunity to remove primary collisions.
00386         $letterMap = array();
00387         foreach ( $letters as $letter ) {
00388             $key = $this->getPrimarySortKey( $letter );
00389             if ( isset( $letterMap[$key] ) ) {
00390                 // Primary collision
00391                 // Keep whichever one sorts first in the main collator
00392                 if ( $this->mainCollator->compare( $letter, $letterMap[$key] ) < 0 ) {
00393                     $letterMap[$key] = $letter;
00394                 }
00395             } else {
00396                 $letterMap[$key] = $letter;
00397             }
00398         }
00399         ksort( $letterMap, SORT_STRING );
00400         // Remove duplicate prefixes. Basically if something has a sortkey
00401         // which is a prefix of some other sortkey, then it is an
00402         // expansion and probably should not be considered a section
00403         // header.
00404         //
00405         // For example 'þ' is sometimes sorted as if it is the letters
00406         // 'th'. Other times it is its own primary element. Another
00407         // example is '₨'. Sometimes its a currency symbol. Sometimes it
00408         // is an 'R' followed by an 's'.
00409         //
00410         // Additionally an expanded element should always sort directly
00411         // after its first element due to they way sortkeys work.
00412         //
00413         // UCA sortkey elements are of variable length but no collation
00414         // element should be a prefix of some other element, so I think
00415         // this is safe. See:
00416         // * https://ssl.icu-project.org/repos/icu/icuhtml/trunk/design/collation/ICU_collation_design.htm
00417         // * http://site.icu-project.org/design/collation/uca-weight-allocation
00418         //
00419         // Additionally, there is something called primary compression to
00420         // worry about. Basically, if you have two primary elements that
00421         // are more than one byte and both start with the same byte then
00422         // the first byte is dropped on the second primary. Additionally
00423         // either \x03 or \xFF may be added to mean that the next primary
00424         // does not start with the first byte of the first primary.
00425         //
00426         // This shouldn't matter much, as the first primary is not
00427         // changed, and that is what we are comparing against.
00428         //
00429         // tl;dr: This makes some assumptions about how icu implements
00430         // collations. It seems incredibly unlikely these assumptions
00431         // will change, but nonetheless they are assumptions.
00432 
00433         $prev = false;
00434         $duplicatePrefixes = array();
00435         foreach ( $letterMap as $key => $value ) {
00436             // Remove terminator byte. Otherwise the prefix
00437             // comparison will get hung up on that.
00438             $trimmedKey = rtrim( $key, "\0" );
00439             if ( $prev === false || $prev === '' ) {
00440                 $prev = $trimmedKey;
00441                 // We don't yet have a collation element
00442                 // to compare against, so continue.
00443                 continue;
00444             }
00445 
00446             // Due to the fact the array is sorted, we only have
00447             // to compare with the element directly previous
00448             // to the current element (skipping expansions).
00449             // An element "X" will always sort directly
00450             // before "XZ" (Unless we have "XY", but we
00451             // do not update $prev in that case).
00452             if ( substr( $trimmedKey, 0, strlen( $prev ) ) === $prev ) {
00453                 $duplicatePrefixes[] = $key;
00454                 // If this is an expansion, we don't want to
00455                 // compare the next element to this element,
00456                 // but to what is currently $prev
00457                 continue;
00458             }
00459             $prev = $trimmedKey;
00460         }
00461         foreach ( $duplicatePrefixes as $badKey ) {
00462             wfDebug( "Removing '{$letterMap[$badKey]}' from first letters." );
00463             unset( $letterMap[$badKey] );
00464             // This code assumes that unsetting does not change sort order.
00465         }
00466         $data = array(
00467             'chars' => array_values( $letterMap ),
00468             'keys' => array_keys( $letterMap ),
00469             'version' => self::FIRST_LETTER_VERSION,
00470         );
00471 
00472         // Reduce memory usage before caching
00473         unset( $letterMap );
00474 
00475         // Save to cache
00476         $this->firstLetterData = $data;
00477         $cache->set( $cacheKey, $data, 86400 * 7 /* 1 week */ );
00478         return $data;
00479     }
00480 
00481     function getLetterByIndex( $index ) {
00482         if ( $this->firstLetterData === null ) {
00483             $this->getFirstLetterData();
00484         }
00485         return $this->firstLetterData['chars'][$index];
00486     }
00487 
00488     function getSortKeyByLetterIndex( $index ) {
00489         if ( $this->firstLetterData === null ) {
00490             $this->getFirstLetterData();
00491         }
00492         return $this->firstLetterData['keys'][$index];
00493     }
00494 
00495     function getFirstLetterCount() {
00496         if ( $this->firstLetterData === null ) {
00497             $this->getFirstLetterData();
00498         }
00499         return count( $this->firstLetterData['chars'] );
00500     }
00501 
00517     function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) {
00518         if ( $valueCount === 0 ) {
00519             return false;
00520         }
00521 
00522         $min = 0;
00523         $max = $valueCount;
00524         do {
00525             $mid = $min + ( ( $max - $min ) >> 1 );
00526             $item = call_user_func( $valueCallback, $mid );
00527             $comparison = call_user_func( $comparisonCallback, $target, $item );
00528             if ( $comparison > 0 ) {
00529                 $min = $mid;
00530             } elseif ( $comparison == 0 ) {
00531                 $min = $mid;
00532                 break;
00533             } else {
00534                 $max = $mid;
00535             }
00536         } while ( $min < $max - 1 );
00537 
00538         if ( $min == 0 ) {
00539             $item = call_user_func( $valueCallback, $min );
00540             $comparison = call_user_func( $comparisonCallback, $target, $item );
00541             if ( $comparison < 0 ) {
00542                 // Before the first item
00543                 return false;
00544             }
00545         }
00546         return $min;
00547     }
00548 
00549     static function isCjk( $codepoint ) {
00550         foreach ( self::$cjkBlocks as $block ) {
00551             if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
00552                 return true;
00553             }
00554         }
00555         return false;
00556     }
00557 
00570     static function getICUVersion() {
00571         return defined( 'INTL_ICU_VERSION' ) ? INTL_ICU_VERSION : false;
00572     }
00573 
00581     static function getUnicodeVersionForICU() {
00582         $icuVersion = IcuCollation::getICUVersion();
00583         if ( !$icuVersion ) {
00584             return false;
00585         }
00586 
00587         $versionPrefix = substr( $icuVersion, 0, 3 );
00588         // Source: http://site.icu-project.org/download
00589         $map = array(
00590             '50.' => '6.2',
00591             '49.' => '6.1',
00592             '4.8' => '6.0',
00593             '4.6' => '6.0',
00594             '4.4' => '5.2',
00595             '4.2' => '5.1',
00596             '4.0' => '5.1',
00597             '3.8' => '5.0',
00598             '3.6' => '5.0',
00599             '3.4' => '4.1',
00600         );
00601 
00602         if ( isset( $map[$versionPrefix] ) ) {
00603             return $map[$versionPrefix];
00604         } else {
00605             return false;
00606         }
00607     }
00608 }