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 line feed 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                 // intl extension produces non null-terminated
 134                 // strings. Appending '' fixes it so that it doesn't generate
 135                 // a warning on each access in debug php.
 136                 wfSuppressWarnings();
 137                 $key = $this->mainCollator->getSortKey( $string ) . '';
 138                 wfRestoreWarnings();
 139                 return $key;
 140         }
 141
 142         function getPrimarySortKey( $string ) {
 143                 wfSuppressWarnings();
 144                 $key = $this->primaryCollator->getSortKey( $string ) . '';
 145                 wfRestoreWarnings();
 146                 return $key;
 147         }
 148
 149         function getFirstLetter( $string ) {
 150                 $string = strval( $string );
 151                 if ( $string === '' ) {
 152                         return '';
 153                 }
 154
 155                 // Check for CJK
 156                 $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
 157                 if ( ord( $firstChar ) > 0x7f
 158                         && self::isCjk( utf8ToCodepoint( $firstChar ) ) )
 159                 {
 160                         return $firstChar;
 161                 }
 162
 163                 $sortKey = $this->getPrimarySortKey( $string );
 164
 165                 // Do a binary search to find the correct letter to sort under
 166                 $min = $this->findLowerBound(
 167                         array( $this, 'getSortKeyByLetterIndex' ),
 168                         $this->getFirstLetterCount(),
 169                         'strcmp',
 170                         $sortKey );
 171
 172                 if ( $min === false ) {
 173                         // Before the first letter
 174                         return '';
 175                 }
 176                 return $this->getLetterByIndex( $min );
 177         }
 178
 179         function getFirstLetterData() {
 180                 if ( $this->firstLetterData !== null ) {
 181                         return $this->firstLetterData;
 182                 }
 183
 184                 $cache = wfGetCache( CACHE_ANYTHING );
 185                 $cacheKey = wfMemcKey( 'first-letters', $this->locale );
 186                 $cacheEntry = $cache->get( $cacheKey );
 187
 188                 if ( $cacheEntry ) {
 189                         $this->firstLetterData = $cacheEntry;
 190                         return $this->firstLetterData;
 191                 }
 192
 193                 // Generate data from serialized data file
 194
 195                 $letters = wfGetPrecompiledData( "first-letters-{$this->locale}.ser" );
 196                 if ( $letters === false ) {
 197                         throw new MWException( "MediaWiki does not support ICU locale " .
 198                                 "\"{$this->locale}\"" );
 199                 }
 200
 201                 // Sort the letters.
 202                 //
 203                 // It's impossible to have the precompiled data file properly sorted,
 204                 // because the sort order changes depending on ICU version. If the
 205                 // array is not properly sorted, the binary search will return random
 206                 // results.
 207                 //
 208                 // We also take this opportunity to remove primary collisions.
 209                 $letterMap = array();
 210                 foreach ( $letters as $letter ) {
 211                         $key = $this->getPrimarySortKey( $letter );
 212                         if ( isset( $letterMap[$key] ) ) {
 213                                 // Primary collision
 214                                 // Keep whichever one sorts first in the main collator
 215                                 if ( $this->mainCollator->compare( $letter, $letterMap[$key] ) < 0 ) {
 216                                         $letterMap[$key] = $letter;
 217                                 }
 218                         } else {
 219                                 $letterMap[$key] = $letter;
 220                         }
 221                 }
 222                 ksort( $letterMap, SORT_STRING );
 223                 $data = array(
 224                         'chars' => array_values( $letterMap ),
 225                         'keys' => array_keys( $letterMap )
 226                 );
 227
 228                 // Reduce memory usage before caching
 229                 unset( $letterMap );
 230
 231                 // Save to cache
 232                 $this->firstLetterData = $data;
 233                 $cache->set( $cacheKey, $data, 86400 * 7 /* 1 week */ );
 234                 return $data;
 235         }
 236
 237         function getLetterByIndex( $index ) {
 238                 if ( $this->firstLetterData === null ) {
 239                         $this->getFirstLetterData();
 240                 }
 241                 return $this->firstLetterData['chars'][$index];
 242         }
 243
 244         function getSortKeyByLetterIndex( $index ) {
 245                 if ( $this->firstLetterData === null ) {
 246                         $this->getFirstLetterData();
 247                 }
 248                 return $this->firstLetterData['keys'][$index];
 249         }
 250
 251         function getFirstLetterCount() {
 252                 if ( $this->firstLetterData === null ) {
 253                         $this->getFirstLetterData();
 254                 }
 255                 return count( $this->firstLetterData['chars'] );
 256         }
 257
 258         /**
 259          * Do a binary search, and return the index of the largest item that sorts
 260          * less than or equal to the target value.
 261          *
 262          * @param $valueCallback A function to call to get the value with
 263          *     a given array index.
 264          * @param $valueCount The number of items accessible via $valueCallback,
 265          *     indexed from 0 to $valueCount - 1
 266          * @param $comparisonCallback A callback to compare two values, returning
 267          *     -1, 0 or 1 in the style of strcmp().
 268          * @param $target The target value to find.
 269          *
 270          * @return The item index of the lower bound, or false if the target value
 271          *     sorts before all items.
 272          */
 273         function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) {
 274                 $min = 0;
 275                 $max = $valueCount - 1;
 276                 do {
 277                         $mid = $min + ( ( $max - $min ) >> 1 );
 278                         $item = call_user_func( $valueCallback, $mid );
 279                         $comparison = call_user_func( $comparisonCallback, $target, $item );
 280                         if ( $comparison > 0 ) {
 281                                 $min = $mid;
 282                         } elseif ( $comparison == 0 ) {
 283                                 $min = $mid;
 284                                 break;
 285                         } else {
 286                                 $max = $mid;
 287                         }
 288                 } while ( $min < $max - 1 );
 289
 290                 if ( $min == 0 && $max == 0 && $comparison > 0 ) {
 291                         // Before the first item
 292                         return false;
 293                 } else {
 294                         return $min;
 295                 }
 296         }
 297
 298         static function isCjk( $codepoint ) {
 299                 foreach ( self::$cjkBlocks as $block ) {
 300                         if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
 301                                 return true;
 302                         }
 303                 }
 304                 return false;
 305         }
 306 }
 307