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