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