includes/Collation.php

   1 <?php
   2 /**
   3  * Database row sorting.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  * http://www.gnu.org/copyleft/gpl.html
  19  *
  20  * @file
  21  */
  22
  23 abstract class Collation {
  24         static $instance;
  25
  26         /**
  27          * @return Collation
  28          */
  29         static function singleton() {
  30                 if ( !self::$instance ) {
  31                         global $wgCategoryCollation;
  32                         self::$instance = self::factory( $wgCategoryCollation );
  33                 }
  34                 return self::$instance;
  35         }
  36
  37         /**
  38          * @throws MWException
  39          * @param $collationName string
  40          * @return Collation
  41          */
  42         static function factory( $collationName ) {
  43                 switch( $collationName ) {
  44                         case 'uppercase':
  45                                 return new UppercaseCollation;
  46                         case 'uppercase-sv':
  47                                 return new UppercaseSvCollation;
  48                         case 'identity':
  49                                 return new IdentityCollation;
  50                         case 'uca-default':
  51                                 return new IcuCollation( 'root' );
  52                         default:
  53                                 # Provide a mechanism for extensions to hook in.
  54
  55                                 $collationObject = null;
  56                                 wfRunHooks( 'Collation::factory', array( $collationName, &$collationObject ) );
  57
  58                                 if ( $collationObject instanceof Collation ) {
  59                                         return $collationObject;
  60                                 }
  61
  62                                 // If all else fails...
  63                                 throw new MWException( __METHOD__.": unknown collation type \"$collationName\"" );
  64                 }
  65         }
  66
  67         /**
  68          * Given a string, convert it to a (hopefully short) key that can be used
  69          * for efficient sorting.  A binary sort according to the sortkeys
  70          * corresponds to a logical sort of the corresponding strings.  Current
  71          * code expects that a line feed character should sort before all others, but
  72          * has no other particular expectations (and that one can be changed if
  73          * necessary).
  74          *
  75          * @param string $string UTF-8 string
  76          * @return string Binary sortkey
  77          */
  78         abstract function getSortKey( $string );
  79
  80         /**
  81          * Given a string, return the logical "first letter" to be used for
  82          * grouping on category pages and so on.  This has to be coordinated
  83          * carefully with convertToSortkey(), or else the sorted list might jump
  84          * back and forth between the same "initial letters" or other pathological
  85          * behavior.  For instance, if you just return the first character, but "a"
  86          * sorts the same as "A" based on getSortKey(), then you might get a
  87          * list like
  88          *
  89          * == A ==
  90          * * [[Aardvark]]
  91          *
  92          * == a ==
  93          * * [[antelope]]
  94          *
  95          * == A ==
  96          * * [[Ape]]
  97          *
  98          * etc., assuming for the sake of argument that $wgCapitalLinks is false.
  99          *
 100          * @param string $string UTF-8 string
 101          * @return string UTF-8 string corresponding to the first letter of input
 102          */
 103         abstract function getFirstLetter( $string );
 104 }
 105
 106 class UppercaseCollation extends Collation {
 107         var $lang;
 108         function __construct() {
 109                 // Get a language object so that we can use the generic UTF-8 uppercase
 110                 // function there
 111                 $this->lang = Language::factory( 'en' );
 112         }
 113
 114         function getSortKey( $string ) {
 115                 return $this->lang->uc( $string );
 116         }
 117
 118         function getFirstLetter( $string ) {
 119                 if ( $string[0] == "\0" ) {
 120                         $string = substr( $string, 1 );
 121                 }
 122                 return $this->lang->ucfirst( $this->lang->firstChar( $string ) );
 123         }
 124 }
 125
 126 /**
 127  * Like UppercaseCollation but swaps Ä and Æ.
 128  *
 129  * This provides an ordering suitable for Swedish.
 130  * @author Lejonel
 131  */
 132 class UppercaseSvCollation extends UppercaseCollation {
 133
 134         /* Unicode code point order is ÄÅÆÖ, Swedish order is ÅÄÖ and Æ is often sorted as Ä.
 135          * Replacing Ä for Æ should give a better collation. */
 136         function getSortKey( $string ) {
 137                 $uppercase = $this->lang->uc( $string );
 138                 return strtr( $uppercase, array( 'Ä' => 'Æ', 'Æ' => 'Ä' ) );
 139         }
 140 }
 141
 142 /**
 143  * Collation class that's essentially a no-op.
 144  *
 145  * Does sorting based on binary value of the string.
 146  * Like how things were pre 1.17.
 147  */
 148 class IdentityCollation extends Collation {
 149
 150         function getSortKey( $string ) {
 151                 return $string;
 152         }
 153
 154         function getFirstLetter( $string ) {
 155                 global $wgContLang;
 156                 // Copied from UppercaseCollation.
 157                 // I'm kind of unclear on when this could happen...
 158                 if ( $string[0] == "\0" ) {
 159                         $string = substr( $string, 1 );
 160                 }
 161                 return $wgContLang->firstChar( $string );
 162         }
 163 }
 164
 165
 166 class IcuCollation extends Collation {
 167         var $primaryCollator, $mainCollator, $locale;
 168         var $firstLetterData;
 169
 170         /**
 171          * Unified CJK blocks.
 172          *
 173          * The same definition of a CJK block must be used for both Collation and
 174          * generateCollationData.php. These blocks are omitted from the first
 175          * letter data, as an optimisation measure and because the default UCA table
 176          * is pretty useless for sorting Chinese text anyway. Japanese and Korean
 177          * blocks are not included here, because they are smaller and more useful.
 178          */
 179         static $cjkBlocks = array(
 180                 array( 0x2E80, 0x2EFF ), // CJK Radicals Supplement
 181                 array( 0x2F00, 0x2FDF ), // Kangxi Radicals
 182                 array( 0x2FF0, 0x2FFF ), // Ideographic Description Characters
 183                 array( 0x3000, 0x303F ), // CJK Symbols and Punctuation
 184                 array( 0x31C0, 0x31EF ), // CJK Strokes
 185                 array( 0x3200, 0x32FF ), // Enclosed CJK Letters and Months
 186                 array( 0x3300, 0x33FF ), // CJK Compatibility
 187                 array( 0x3400, 0x4DBF ), // CJK Unified Ideographs Extension A
 188                 array( 0x4E00, 0x9FFF ), // CJK Unified Ideographs
 189                 array( 0xF900, 0xFAFF ), // CJK Compatibility Ideographs
 190                 array( 0xFE30, 0xFE4F ), // CJK Compatibility Forms
 191                 array( 0x20000, 0x2A6DF ), // CJK Unified Ideographs Extension B
 192                 array( 0x2A700, 0x2B73F ), // CJK Unified Ideographs Extension C
 193                 array( 0x2B740, 0x2B81F ), // CJK Unified Ideographs Extension D
 194                 array( 0x2F800, 0x2FA1F ), // CJK Compatibility Ideographs Supplement
 195         );
 196
 197         const RECORD_LENGTH = 14;
 198
 199         function __construct( $locale ) {
 200                 if ( !extension_loaded( 'intl' ) ) {
 201                         throw new MWException( 'An ICU collation was requested, ' .
 202                                 'but the intl extension is not available.' );
 203                 }
 204                 $this->locale = $locale;
 205                 $this->mainCollator = Collator::create( $locale );
 206                 if ( !$this->mainCollator ) {
 207                         throw new MWException( "Invalid ICU locale specified for collation: $locale" );
 208                 }
 209
 210                 $this->primaryCollator = Collator::create( $locale );
 211                 $this->primaryCollator->setStrength( Collator::PRIMARY );
 212         }
 213
 214         function getSortKey( $string ) {
 215                 // intl extension produces non null-terminated
 216                 // strings. Appending '' fixes it so that it doesn't generate
 217                 // a warning on each access in debug php.
 218                 wfSuppressWarnings();
 219                 $key = $this->mainCollator->getSortKey( $string ) . '';
 220                 wfRestoreWarnings();
 221                 return $key;
 222         }
 223
 224         function getPrimarySortKey( $string ) {
 225                 wfSuppressWarnings();
 226                 $key = $this->primaryCollator->getSortKey( $string ) . '';
 227                 wfRestoreWarnings();
 228                 return $key;
 229         }
 230
 231         function getFirstLetter( $string ) {
 232                 $string = strval( $string );
 233                 if ( $string === '' ) {
 234                         return '';
 235                 }
 236
 237                 // Check for CJK
 238                 $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
 239                 if ( ord( $firstChar ) > 0x7f
 240                         && self::isCjk( utf8ToCodepoint( $firstChar ) ) )
 241                 {
 242                         return $firstChar;
 243                 }
 244
 245                 $sortKey = $this->getPrimarySortKey( $string );
 246
 247                 // Do a binary search to find the correct letter to sort under
 248                 $min = $this->findLowerBound(
 249                         array( $this, 'getSortKeyByLetterIndex' ),
 250                         $this->getFirstLetterCount(),
 251                         'strcmp',
 252                         $sortKey );
 253
 254                 if ( $min === false ) {
 255                         // Before the first letter
 256                         return '';
 257                 }
 258                 return $this->getLetterByIndex( $min );
 259         }
 260
 261         function getFirstLetterData() {
 262                 if ( $this->firstLetterData !== null ) {
 263                         return $this->firstLetterData;
 264                 }
 265
 266                 $cache = wfGetCache( CACHE_ANYTHING );
 267                 $cacheKey = wfMemcKey( 'first-letters', $this->locale );
 268                 $cacheEntry = $cache->get( $cacheKey );
 269
 270                 if ( $cacheEntry ) {
 271                         $this->firstLetterData = $cacheEntry;
 272                         return $this->firstLetterData;
 273                 }
 274
 275                 // Generate data from serialized data file
 276
 277                 $letters = wfGetPrecompiledData( "first-letters-{$this->locale}.ser" );
 278                 if ( $letters === false ) {
 279                         throw new MWException( "MediaWiki does not support ICU locale " .
 280                                 "\"{$this->locale}\"" );
 281                 }
 282
 283                 // Sort the letters.
 284                 //
 285                 // It's impossible to have the precompiled data file properly sorted,
 286                 // because the sort order changes depending on ICU version. If the
 287                 // array is not properly sorted, the binary search will return random
 288                 // results.
 289                 //
 290                 // We also take this opportunity to remove primary collisions.
 291                 $letterMap = array();
 292                 foreach ( $letters as $letter ) {
 293                         $key = $this->getPrimarySortKey( $letter );
 294                         if ( isset( $letterMap[$key] ) ) {
 295                                 // Primary collision
 296                                 // Keep whichever one sorts first in the main collator
 297                                 if ( $this->mainCollator->compare( $letter, $letterMap[$key] ) < 0 ) {
 298                                         $letterMap[$key] = $letter;
 299                                 }
 300                         } else {
 301                                 $letterMap[$key] = $letter;
 302                         }
 303                 }
 304                 ksort( $letterMap, SORT_STRING );
 305                 $data = array(
 306                         'chars' => array_values( $letterMap ),
 307                         'keys' => array_keys( $letterMap )
 308                 );
 309
 310                 // Reduce memory usage before caching
 311                 unset( $letterMap );
 312
 313                 // Save to cache
 314                 $this->firstLetterData = $data;
 315                 $cache->set( $cacheKey, $data, 86400 * 7 /* 1 week */ );
 316                 return $data;
 317         }
 318
 319         function getLetterByIndex( $index ) {
 320                 if ( $this->firstLetterData === null ) {
 321                         $this->getFirstLetterData();
 322                 }
 323                 return $this->firstLetterData['chars'][$index];
 324         }
 325
 326         function getSortKeyByLetterIndex( $index ) {
 327                 if ( $this->firstLetterData === null ) {
 328                         $this->getFirstLetterData();
 329                 }
 330                 return $this->firstLetterData['keys'][$index];
 331         }
 332
 333         function getFirstLetterCount() {
 334                 if ( $this->firstLetterData === null ) {
 335                         $this->getFirstLetterData();
 336                 }
 337                 return count( $this->firstLetterData['chars'] );
 338         }
 339
 340         /**
 341          * Do a binary search, and return the index of the largest item that sorts
 342          * less than or equal to the target value.
 343          *
 344          * @param $valueCallback array A function to call to get the value with
 345          *     a given array index.
 346          * @param $valueCount int The number of items accessible via $valueCallback,
 347          *     indexed from 0 to $valueCount - 1
 348          * @param $comparisonCallback array A callback to compare two values, returning
 349          *     -1, 0 or 1 in the style of strcmp().
 350          * @param $target string The target value to find.
 351          *
 352          * @return int|bool The item index of the lower bound, or false if the target value
 353          *     sorts before all items.
 354          */
 355         function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) {
 356                 if ( $valueCount === 0 ) {
 357                         return false;
 358                 }
 359
 360                 $min = 0;
 361                 $max = $valueCount;
 362                 do {
 363                         $mid = $min + ( ( $max - $min ) >> 1 );
 364                         $item = call_user_func( $valueCallback, $mid );
 365                         $comparison = call_user_func( $comparisonCallback, $target, $item );
 366                         if ( $comparison > 0 ) {
 367                                 $min = $mid;
 368                         } elseif ( $comparison == 0 ) {
 369                                 $min = $mid;
 370                                 break;
 371                         } else {
 372                                 $max = $mid;
 373                         }
 374                 } while ( $min < $max - 1 );
 375
 376                 if ( $min == 0 ) {
 377                         $item = call_user_func( $valueCallback, $min );
 378                         $comparison = call_user_func( $comparisonCallback, $target, $item );
 379                         if ( $comparison < 0 ) {
 380                                 // Before the first item
 381                                 return false;
 382                         }
 383                 }
 384                 return $min;
 385         }
 386
 387         static function isCjk( $codepoint ) {
 388                 foreach ( self::$cjkBlocks as $block ) {
 389                         if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {
 390                                 return true;
 391                         }
 392                 }
 393                 return false;
 394         }
 395
 396         /**
 397          * Return the version of ICU library used by PHP's intl extension,
 398          * or false when the extension is not installed of the version
 399          * can't be determined.
 400          *
 401          * The constant INTL_ICU_VERSION this function refers to isn't really
 402          * documented. It is available since PHP 5.3.7 (see PHP bug 54561).
 403          * This function will return false on older PHPs.
 404          *
 405          * @since 1.21
 406          * @return string|false
 407          */
 408         static function getICUVersion() {
 409                 return defined( 'INTL_ICU_VERSION' ) ? INTL_ICU_VERSION : false;
 410         }
 411 }