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