includes/Collation.php

   1 <?php
   2
   3 abstract class Collation {
   4         static $instance;
   5
   6         static function singleton() {
   7                 if ( !self::$instance ) {
   8                         global $wgCategoryCollation;
   9                         self::$instance = self::factory( $wgCategoryCollation );
  10                 }
  11                 return self::$instance;
  12         }
  13
  14         static function factory( $collationName ) {
  15                 switch( $collationName ) {
  16                         case 'uppercase':
  17                                 return new UppercaseCollation;
  18                         case 'uca-default':
  19                                 return new IcuCollation( 'root' );
  20                         default:
  21                                 throw new MWException( __METHOD__.": unknown collation type \"$collationName\"" );
  22                 }
  23         }
  24
  25         /**
  26          * Given a string, convert it to a (hopefully short) key that can be used
  27          * for efficient sorting.  A binary sort according to the sortkeys
  28          * corresponds to a logical sort of the corresponding strings.  Current
  29          * code expects that a null character should sort before all others, but
  30          * has no other particular expectations (and that one can be changed if
  31          * necessary).
  32          *
  33          * @param string $string UTF-8 string
  34          * @return string Binary sortkey
  35          */
  36         abstract function getSortKey( $string );
  37
  38         /**
  39          * Given a string, return the logical "first letter" to be used for
  40          * grouping on category pages and so on.  This has to be coordinated
  41          * carefully with convertToSortkey(), or else the sorted list might jump
  42          * back and forth between the same "initial letters" or other pathological
  43          * behavior.  For instance, if you just return the first character, but "a"
  44          * sorts the same as "A" based on getSortKey(), then you might get a
  45          * list like
  46          *
  47          * == A ==
  48          * * [[Aardvark]]
  49          *
  50          * == a ==
  51          * * [[antelope]]
  52          *
  53          * == A ==
  54          * * [[Ape]]
  55          *
  56          * etc., assuming for the sake of argument that $wgCapitalLinks is false.
  57          *
  58          * @param string $string UTF-8 string
  59          * @return string UTF-8 string corresponding to the first letter of input
  60          */
  61         abstract function getFirstLetter( $string );
  62 }
  63
  64 class UppercaseCollation extends Collation {
  65         var $lang;
  66         function __construct() {
  67                 // Get a language object so that we can use the generic UTF-8 uppercase
  68                 // function there
  69                 $this->lang = Language::factory( 'en' );
  70         }
  71
  72         function getSortKey( $string ) {
  73                 return $this->lang->uc( $string );
  74         }
  75
  76         function getFirstLetter( $string ) {
  77                 if ( $string[0] == "\0" ) {
  78                         $string = substr( $string, 1 );
  79                 }
  80                 return $this->lang->ucfirst( $this->lang->firstChar( $string ) );
  81         }
  82 }
  83
  84 class IcuCollation extends Collation {
  85         var $primaryCollator, $mainCollator, $locale;
  86         var $firstLetterData;
  87
  88         /**
  89          * Unified CJK blocks.
  90          *
  91          * The same definition of a CJK block must be used for both Collation and
  92          * generateCollationData.php. These blocks are omitted from the first
  93          * letter data, as an optimisation measure and because the default UCA table
  94          * is pretty useless for sorting Chinese text anyway. Japanese and Korean
  95          * blocks are not included here, because they are smaller and more useful.
  96          */
  97         static $cjkBlocks = array(
  98                 array( 0x2E80, 0x2EFF ), // CJK Radicals Supplement
  99                 array( 0x2F00, 0x2FDF ), // Kangxi Radicals
 100                 array( 0x2FF0, 0x2FFF ), // Ideographic Description Characters
 101                 array( 0x3000, 0x303F ), // CJK Symbols and Punctuation
 102                 array( 0x31C0, 0x31EF ), // CJK Strokes
 103                 array( 0x3200, 0x32FF ), // Enclosed CJK Letters and Months
 104                 array( 0x3300, 0x33FF ), // CJK Compatibility
 105                 array( 0x3400, 0x4DBF ), // CJK Unified Ideographs Extension A
 106                 array( 0x4E00, 0x9FFF ), // CJK Unified Ideographs
 107                 array( 0xF900, 0xFAFF ), // CJK Compatibility Ideographs
 108                 array( 0xFE30, 0xFE4F ), // CJK Compatibility Forms
 109                 array( 0x20000, 0x2A6DF ), // CJK Unified Ideographs Extension B
 110                 array( 0x2A700, 0x2B73F ), // CJK Unified Ideographs Extension C
 111                 array( 0x2B740, 0x2B81F ), // CJK Unified Ideographs Extension D
 112                 array( 0x2F800, 0x2FA1F ), // CJK Compatibility Ideographs Supplement
 113         );
 114
 115         const RECORD_LENGTH = 14;
 116
 117         function __construct( $locale ) {
 118                 if ( !extension_loaded( 'intl' ) ) {
 119                         throw new MWException( 'An ICU collation was requested, ' .
 120                                 'but the intl extension is not available.' );
 121                 }
 122                 $this->locale = $locale;
 123                 $this->mainCollator = Collator::create( $locale );
 124                 if ( !$this->mainCollator ) {
 125                         throw new MWException( "Invalid ICU locale specified for collation: $locale" );
 126                 }
 127
 128                 $this->primaryCollator = Collator::create( $locale );
 129                 $this->primaryCollator->setStrength( Collator::PRIMARY );
 130         }
 131
 132         function getSortKey( $string ) {
 133                 wfSuppressWarnings();
 134                 $key = $this->mainCollator->getSortKey( $string ) . '';
 135                 wfRestoreWarnings();
 136                 return $key;
 137         }
 138
 139         function getPrimarySortKey( $string ) {
 140                 wfSuppressWarnings();
 141                 $key = $this->primaryCollator->getSortKey( $string ) . '';
 142                 wfRestoreWarnings();
 143                 return $key;
 144         }
 145
 146         function getFirstLetter( $string ) {
 147                 $string = strval( $string );
 148                 if ( $string === '' ) {
 149                         return '';
 150                 }
 151
 152                 // Check for CJK
 153                 $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
 154                 if ( ord( $firstChar ) > 0x7f
 155                         && self::isCjk( utf8ToCodepoint( $firstChar ) ) )
 156                 {
 157                         return $firstChar;
 158                 }
 159
 160                 $sortKey = $this->getPrimarySortKey( $string );
 161
 162                 // Do a binary search to find the correct letter to sort under
 163                 $min = $this->findLowerBound(
 164                         array( $this, 'getSortKeyByLetterIndex' ),
 165                         $this->getFirstLetterCount(),
 166                         'strcmp',
 167                         $sortKey );
 168
 169                 if ( $min === false ) {
 170                         // Before the first letter
 171                         return '';
 172                 }
 173                 return $this->getLetterByIndex( $min );
 174         }
 175
 176         function getFirstLetterData() {
 177                 if ( $this->firstLetterData !== null ) {
 178                         return $this->firstLetterData;
 179                 }
 180
 181                 $cache = wfGetCache( CACHE_ANYTHING );
 182                 $cacheKey = wfMemcKey( 'first-letters', $this->locale );
 183                 $cacheEntry = $cache->get( $cacheKey );
 184
 185                 if ( $cacheEntry ) {
 186                         $this->firstLetterData = $cacheEntry;
 187                         return $this->firstLetterData;
 188                 }
 189
 190                 // Generate data from serialized data file
 191
 192                 $letters = wfGetPrecompiledData( "first-letters-{$this->locale}.ser" );
 193                 if ( $letters === false ) {
 194                         throw new MWException( "MediaWiki does not support ICU locale " .
 195                                 "\"{$this->locale}\"" );
 196                 }
 197
 198                 // Sort the letters.
 199                 //
 200                 // It's impossible to have the precompiled data file properly sorted,
 201                 // because the sort order changes depending on ICU version. If the
 202                 // array is not properly sorted, the binary search will return random
 203                 // results.
 204                 //
 205                 // We also take this opportunity to remove primary collisions.
 206                 $letterMap = array();
 207                 foreach ( $letters as $letter ) {
 208                         $key = $this->getPrimarySortKey( $letter );
 209                         if ( isset( $letterMap[$key] ) ) {
 210                                 // Primary collision
 211                                 // Keep whichever one sorts first in the main collator
 212                                 if ( $this->mainCollator->compare( $letter, $letterMap[$key] ) < 0 ) {
 213                                         $letterMap[$key] = $letter;
 214                                 }
 215                         } else {
 216                                 $letterMap[$key] = $letter;
 217                         }
 218                 }
 219                 ksort( $letterMap, SORT_STRING );
 220                 $data = array(
 221                         'chars' => array_values( $letterMap ),
 222                         'keys' => array_keys( $letterMap )
 223                 );
 224
 225                 // Reduce memory usage before caching
 226                 unset( $letterMap );
 227
 228                 // Save to cache
 229                 $this->firstLetterData = $data;
 230                 $cache->set( $cacheKey, $data, 86400 * 7 /* 1 week */ );
 231                 return $data;
 232         }
 233
 234         function getLetterByIndex( $index ) {
 235                 if ( $this->firstLetterData === null ) {
 236                         $this->getFirstLetterData();
 237                 }
 238                 return $this->firstLetterData['chars'][$index];
 239         }
 240
 241         function getSortKeyByLetterIndex( $index ) {
 242                 if ( $this->firstLetterData === null ) {
 243                         $this->getFirstLetterData();
 244                 }
 245                 return $this->firstLetterData['keys'][$index];
 246         }
 247
 248         function getFirstLetterCount() {
 249                 if ( $this->firstLetterData === null ) {
 250                         $this->getFirstLetterData();
 251                 }
 252                 return count( $this->firstLetterData['chars'] );
 253         }
 254
 255         /**
 256          * Do a binary search, and return the index of the largest item that sorts
 257          * less than or equal to the target value.
 258          *
 259          * @param $valueCallback A function to call to get the value with
 260          *     a given array index.
 261          * @param $valueCount The number of items accessible via $valueCallback,
 262          *     indexed from 0 to $valueCount - 1
 263          * @param $comparisonCallback A callback to compare two values, returning
 264          *     -1, 0 or 1 in the style of strcmp().
 265          * @param $target The target value to find.
 266          *
 267          * @return The item index of the lower bound, or false if the target value
 268          *     sorts before all items.
 269          */
 270         function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) {
 271                 $min = 0;
 272                 $max = $valueCount - 1;
 273                 do {
 274                         $mid = $min + ( ( $max - $min ) >> 1 );
 275                         $item = call_user_func( $valueCallback, $mid );
 276                         $comparison = call_user_func( $comparisonCallback, $target, $item );
 277                         if ( $comparison > 0 ) {
 278                                 $min = $mid;
 279                         } elseif ( $comparison == 0 ) {
 280                                 $min = $mid;
 281                                 break;
 282                         } else {
 283                                 $max = $mid;
 284                         }
 285                 } while ( $min < $max - 1 );
 286
 287                 if ( $min == 0 && $max == 0 && $comparison > 0 ) {
 288                         // Before the first item
 289                         return false;
 290                 } else {
 291                         return $min;
 292                 }
 293         }
 294
 295         static function isCjk( $codepoint ) {
 296                 foreach ( self::$cjkBlocks as $block ) {
 297                         if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
 298                                 return true;
 299                         }
 300                 }
 301                 return false;
 302         }
 303 }
 304