includes/Collation.php

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