includes/Collation.php

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