includes/StringUtils.php

   1 <?php
   2 /**
   3  * A collection of static methods to play with strings.
   4  */
   5 class StringUtils {
   6         /**
   7          * Perform an operation equivalent to
   8          *
   9          *     preg_replace( "!$startDelim(.*?)$endDelim!", $replace, $subject );
  10          *
  11          * except that it's worst-case O(N) instead of O(N^2)
  12          *
  13          * Compared to delimiterReplace(), this implementation is fast but memory-
  14          * hungry and inflexible. The memory requirements are such that I don't
  15          * recommend using it on anything but guaranteed small chunks of text.
  16          *
  17          * @param $startDelim
  18          * @param $endDelim
  19          * @param $replace
  20          * @param $subject
  21          *
  22          * @return string
  23          */
  24         static function hungryDelimiterReplace( $startDelim, $endDelim, $replace, $subject ) {
  25                 $segments = explode( $startDelim, $subject );
  26                 $output = array_shift( $segments );
  27                 foreach ( $segments as $s ) {
  28                         $endDelimPos = strpos( $s, $endDelim );
  29                         if ( $endDelimPos === false ) {
  30                                 $output .= $startDelim . $s;
  31                         } else {
  32                                 $output .= $replace . substr( $s, $endDelimPos + strlen( $endDelim ) );
  33                         }
  34                 }
  35                 return $output;
  36         }
  37
  38         /**
  39          * Perform an operation equivalent to
  40          *
  41          *   preg_replace_callback( "!$startDelim(.*)$endDelim!s$flags", $callback, $subject )
  42          *
  43          * This implementation is slower than hungryDelimiterReplace but uses far less
  44          * memory. The delimiters are literal strings, not regular expressions.
  45          *
  46          * If the start delimiter ends with an initial substring of the end delimiter,
  47          * e.g. in the case of C-style comments, the behaviour differs from the model
  48          * regex. In this implementation, the end must share no characters with the
  49          * start, so e.g. /*\/ is not considered to be both the start and end of a
  50          * comment. /*\/xy/*\/ is considered to be a single comment with contents /xy/.
  51          *
  52          * @param $startDelim String: start delimiter
  53          * @param $endDelim String: end delimiter
  54          * @param $callback Callback: function to call on each match
  55          * @param $subject String
  56          * @param $flags String: regular expression flags
  57          * @throws MWException
  58          * @return string
  59          */
  60         static function delimiterReplaceCallback( $startDelim, $endDelim, $callback, $subject, $flags = '' ) {
  61                 $inputPos = 0;
  62                 $outputPos = 0;
  63                 $output = '';
  64                 $foundStart = false;
  65                 $encStart = preg_quote( $startDelim, '!' );
  66                 $encEnd = preg_quote( $endDelim, '!' );
  67                 $strcmp = strpos( $flags, 'i' ) === false ? 'strcmp' : 'strcasecmp';
  68                 $endLength = strlen( $endDelim );
  69                 $m = array();
  70
  71                 while ( $inputPos < strlen( $subject ) &&
  72                   preg_match( "!($encStart)|($encEnd)!S$flags", $subject, $m, PREG_OFFSET_CAPTURE, $inputPos ) )
  73                 {
  74                         $tokenOffset = $m[0][1];
  75                         if ( $m[1][0] != '' ) {
  76                                 if ( $foundStart &&
  77                                   $strcmp( $endDelim, substr( $subject, $tokenOffset, $endLength ) ) == 0 )
  78                                 {
  79                                         # An end match is present at the same location
  80                                         $tokenType = 'end';
  81                                         $tokenLength = $endLength;
  82                                 } else {
  83                                         $tokenType = 'start';
  84                                         $tokenLength = strlen( $m[0][0] );
  85                                 }
  86                         } elseif ( $m[2][0] != '' ) {
  87                                 $tokenType = 'end';
  88                                 $tokenLength = strlen( $m[0][0] );
  89                         } else {
  90                                 throw new MWException( 'Invalid delimiter given to ' . __METHOD__ );
  91                         }
  92
  93                         if ( $tokenType == 'start' ) {
  94                                 # Only move the start position if we haven't already found a start
  95                                 # This means that START START END matches outer pair
  96                                 if ( !$foundStart ) {
  97                                         # Found start
  98                                         $inputPos = $tokenOffset + $tokenLength;
  99                                         # Write out the non-matching section
 100                                         $output .= substr( $subject, $outputPos, $tokenOffset - $outputPos );
 101                                         $outputPos = $tokenOffset;
 102                                         $contentPos = $inputPos;
 103                                         $foundStart = true;
 104                                 } else {
 105                                         # Move the input position past the *first character* of START,
 106                                         # to protect against missing END when it overlaps with START
 107                                         $inputPos = $tokenOffset + 1;
 108                                 }
 109                         } elseif ( $tokenType == 'end' ) {
 110                                 if ( $foundStart ) {
 111                                         # Found match
 112                                         $output .= call_user_func( $callback, array(
 113                                                 substr( $subject, $outputPos, $tokenOffset + $tokenLength - $outputPos ),
 114                                                 substr( $subject, $contentPos, $tokenOffset - $contentPos )
 115                                         ));
 116                                         $foundStart = false;
 117                                 } else {
 118                                         # Non-matching end, write it out
 119                                         $output .= substr( $subject, $inputPos, $tokenOffset + $tokenLength - $outputPos );
 120                                 }
 121                                 $inputPos = $outputPos = $tokenOffset + $tokenLength;
 122                         } else {
 123                                 throw new MWException( 'Invalid delimiter given to ' . __METHOD__ );
 124                         }
 125                 }
 126                 if ( $outputPos < strlen( $subject ) ) {
 127                         $output .= substr( $subject, $outputPos );
 128                 }
 129                 return $output;
 130         }
 131
 132         /**
 133          * Perform an operation equivalent to
 134          *
 135          *   preg_replace( "!$startDelim(.*)$endDelim!$flags", $replace, $subject )
 136          *
 137          * @param $startDelim String: start delimiter regular expression
 138          * @param $endDelim String: end delimiter regular expression
 139          * @param $replace String: replacement string. May contain $1, which will be
 140          *                 replaced by the text between the delimiters
 141          * @param $subject String to search
 142          * @param $flags String: regular expression flags
 143          * @return String: The string with the matches replaced
 144          */
 145         static function delimiterReplace( $startDelim, $endDelim, $replace, $subject, $flags = '' ) {
 146                 $replacer = new RegexlikeReplacer( $replace );
 147                 return self::delimiterReplaceCallback( $startDelim, $endDelim,
 148                         $replacer->cb(), $subject, $flags );
 149         }
 150
 151         /**
 152          * More or less "markup-safe" explode()
 153          * Ignores any instances of the separator inside <...>
 154          * @param $separator String
 155          * @param $text String
 156          * @return array
 157          */
 158         static function explodeMarkup( $separator, $text ) {
 159                 $placeholder = "\x00";
 160
 161                 // Remove placeholder instances
 162                 $text = str_replace( $placeholder, '', $text );
 163
 164                 // Replace instances of the separator inside HTML-like tags with the placeholder
 165                 $replacer = new DoubleReplacer( $separator, $placeholder );
 166                 $cleaned = StringUtils::delimiterReplaceCallback( '<', '>', $replacer->cb(), $text );
 167
 168                 // Explode, then put the replaced separators back in
 169                 $items = explode( $separator, $cleaned );
 170                 foreach( $items as $i => $str ) {
 171                         $items[$i] = str_replace( $placeholder, $separator, $str );
 172                 }
 173
 174                 return $items;
 175         }
 176
 177         /**
 178          * Escape a string to make it suitable for inclusion in a preg_replace()
 179          * replacement parameter.
 180          *
 181          * @param $string String
 182          * @return String
 183          */
 184         static function escapeRegexReplacement( $string ) {
 185                 $string = str_replace( '\\', '\\\\', $string );
 186                 $string = str_replace( '$', '\\$', $string );
 187                 return $string;
 188         }
 189
 190         /**
 191          * Workalike for explode() with limited memory usage.
 192          * Returns an Iterator
 193          * @param $separator
 194          * @param $subject
 195          * @return ArrayIterator|\ExplodeIterator
 196          */
 197         static function explode( $separator, $subject ) {
 198                 if ( substr_count( $subject, $separator ) > 1000 ) {
 199                         return new ExplodeIterator( $separator, $subject );
 200                 } else {
 201                         return new ArrayIterator( explode( $separator, $subject ) );
 202                 }
 203         }
 204 }
 205
 206 /**
 207  * Base class for "replacers", objects used in preg_replace_callback() and
 208  * StringUtils::delimiterReplaceCallback()
 209  */
 210 class Replacer {
 211
 212         /**
 213          * @return array
 214          */
 215         function cb() {
 216                 return array( &$this, 'replace' );
 217         }
 218 }
 219
 220 /**
 221  * Class to replace regex matches with a string similar to that used in preg_replace()
 222  */
 223 class RegexlikeReplacer extends Replacer {
 224         var $r;
 225
 226         /**
 227          * @param $r string
 228          */
 229         function __construct( $r ) {
 230                 $this->r = $r;
 231         }
 232
 233         /**
 234          * @param $matches array
 235          * @return string
 236          */
 237         function replace( $matches ) {
 238                 $pairs = array();
 239                 foreach ( $matches as $i => $match ) {
 240                         $pairs["\$$i"] = $match;
 241                 }
 242                 return strtr( $this->r, $pairs );
 243         }
 244
 245 }
 246
 247 /**
 248  * Class to perform secondary replacement within each replacement string
 249  */
 250 class DoubleReplacer extends Replacer {
 251
 252         /**
 253          * @param $from
 254          * @param $to
 255          * @param $index int
 256          */
 257         function __construct( $from, $to, $index = 0 ) {
 258                 $this->from = $from;
 259                 $this->to = $to;
 260                 $this->index = $index;
 261         }
 262
 263         /**
 264          * @param $matches array
 265          * @return mixed
 266          */
 267         function replace( $matches ) {
 268                 return str_replace( $this->from, $this->to, $matches[$this->index] );
 269         }
 270 }
 271
 272 /**
 273  * Class to perform replacement based on a simple hashtable lookup
 274  */
 275 class HashtableReplacer extends Replacer {
 276         var $table, $index;
 277
 278         /**
 279          * @param $table
 280          * @param $index int
 281          */
 282         function __construct( $table, $index = 0 ) {
 283                 $this->table = $table;
 284                 $this->index = $index;
 285         }
 286
 287         /**
 288          * @param $matches array
 289          * @return mixed
 290          */
 291         function replace( $matches ) {
 292                 return $this->table[$matches[$this->index]];
 293         }
 294 }
 295
 296 /**
 297  * Replacement array for FSS with fallback to strtr()
 298  * Supports lazy initialisation of FSS resource
 299  */
 300 class ReplacementArray {
 301         /*mostly private*/ var $data = false;
 302         /*mostly private*/ var $fss = false;
 303
 304         /**
 305          * Create an object with the specified replacement array
 306          * The array should have the same form as the replacement array for strtr()
 307          * @param array $data
 308          */
 309         function __construct( $data = array() ) {
 310                 $this->data = $data;
 311         }
 312
 313         /**
 314          * @return array
 315          */
 316         function __sleep() {
 317                 return array( 'data' );
 318         }
 319
 320         function __wakeup() {
 321                 $this->fss = false;
 322         }
 323
 324         /**
 325          * Set the whole replacement array at once
 326          */
 327         function setArray( $data ) {
 328                 $this->data = $data;
 329                 $this->fss = false;
 330         }
 331
 332         /**
 333          * @return array|bool
 334          */
 335         function getArray() {
 336                 return $this->data;
 337         }
 338
 339         /**
 340          * Set an element of the replacement array
 341          * @param $from string
 342          * @param $to stromg
 343          */
 344         function setPair( $from, $to ) {
 345                 $this->data[$from] = $to;
 346                 $this->fss = false;
 347         }
 348
 349         /**
 350          * @param $data array
 351          */
 352         function mergeArray( $data ) {
 353                 $this->data = array_merge( $this->data, $data );
 354                 $this->fss = false;
 355         }
 356
 357         /**
 358          * @param $other
 359          */
 360         function merge( $other ) {
 361                 $this->data = array_merge( $this->data, $other->data );
 362                 $this->fss = false;
 363         }
 364
 365         /**
 366          * @param $from string
 367          */
 368         function removePair( $from ) {
 369                 unset($this->data[$from]);
 370                 $this->fss = false;
 371         }
 372
 373         /**
 374          * @param $data array
 375          */
 376         function removeArray( $data ) {
 377                 foreach( $data as $from => $to ) {
 378                         $this->removePair( $from );
 379                 }
 380                 $this->fss = false;
 381         }
 382
 383         /**
 384          * @param $subject string
 385          * @return string
 386          */
 387         function replace( $subject ) {
 388                 if ( function_exists( 'fss_prep_replace' ) ) {
 389                         wfProfileIn( __METHOD__.'-fss' );
 390                         if ( $this->fss === false ) {
 391                                 $this->fss = fss_prep_replace( $this->data );
 392                         }
 393                         $result = fss_exec_replace( $this->fss, $subject );
 394                         wfProfileOut( __METHOD__.'-fss' );
 395                 } else {
 396                         wfProfileIn( __METHOD__.'-strtr' );
 397                         $result = strtr( $subject, $this->data );
 398                         wfProfileOut( __METHOD__.'-strtr' );
 399                 }
 400                 return $result;
 401         }
 402 }
 403
 404 /**
 405  * An iterator which works exactly like:
 406  *
 407  * foreach ( explode( $delim, $s ) as $element ) {
 408  *    ...
 409  * }
 410  *
 411  * Except it doesn't use 193 byte per element
 412  */
 413 class ExplodeIterator implements Iterator {
 414         // The subject string
 415         var $subject, $subjectLength;
 416
 417         // The delimiter
 418         var $delim, $delimLength;
 419
 420         // The position of the start of the line
 421         var $curPos;
 422
 423         // The position after the end of the next delimiter
 424         var $endPos;
 425
 426         // The current token
 427         var $current;
 428
 429         /**
 430          * Construct a DelimIterator
 431          * @param $delim string
 432          * @param $s string
 433          */
 434         function __construct( $delim, $s ) {
 435                 $this->subject = $s;
 436                 $this->delim = $delim;
 437
 438                 // Micro-optimisation (theoretical)
 439                 $this->subjectLength = strlen( $s );
 440                 $this->delimLength = strlen( $delim );
 441
 442                 $this->rewind();
 443         }
 444
 445         function rewind() {
 446                 $this->curPos = 0;
 447                 $this->endPos = strpos( $this->subject, $this->delim );
 448                 $this->refreshCurrent();
 449         }
 450
 451         function refreshCurrent() {
 452                 if ( $this->curPos === false ) {
 453                         $this->current = false;
 454                 } elseif ( $this->curPos >= $this->subjectLength ) {
 455                         $this->current = '';
 456                 } elseif ( $this->endPos === false ) {
 457                         $this->current = substr( $this->subject, $this->curPos );
 458                 } else {
 459                         $this->current = substr( $this->subject, $this->curPos, $this->endPos - $this->curPos );
 460                 }
 461         }
 462
 463         function current() {
 464                 return $this->current;
 465         }
 466
 467         function key() {
 468                 return $this->curPos;
 469         }
 470
 471         /**
 472          * @return string
 473          */
 474         function next() {
 475                 if ( $this->endPos === false ) {
 476                         $this->curPos = false;
 477                 } else {
 478                         $this->curPos = $this->endPos + $this->delimLength;
 479                         if ( $this->curPos >= $this->subjectLength ) {
 480                                 $this->endPos = false;
 481                         } else {
 482                                 $this->endPos = strpos( $this->subject, $this->delim, $this->curPos );
 483                         }
 484                 }
 485                 $this->refreshCurrent();
 486                 return $this->current;
 487         }
 488
 489         /**
 490          * @return bool
 491          */
 492         function valid() {
 493                 return $this->curPos !== false;
 494         }
 495 }