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          * @return string
  58          */
  59         static function delimiterReplaceCallback( $startDelim, $endDelim, $callback, $subject, $flags = '' ) {
  60                 $inputPos = 0;
  61                 $outputPos = 0;
  62                 $output = '';
  63                 $foundStart = false;
  64                 $encStart = preg_quote( $startDelim, '!' );
  65                 $encEnd = preg_quote( $endDelim, '!' );
  66                 $strcmp = strpos( $flags, 'i' ) === false ? 'strcmp' : 'strcasecmp';
  67                 $endLength = strlen( $endDelim );
  68                 $m = array();
  69
  70                 while ( $inputPos < strlen( $subject ) &&
  71                   preg_match( "!($encStart)|($encEnd)!S$flags", $subject, $m, PREG_OFFSET_CAPTURE, $inputPos ) )
  72                 {
  73                         $tokenOffset = $m[0][1];
  74                         if ( $m[1][0] != '' ) {
  75                                 if ( $foundStart &&
  76                                   $strcmp( $endDelim, substr( $subject, $tokenOffset, $endLength ) ) == 0 )
  77                                 {
  78                                         # An end match is present at the same location
  79                                         $tokenType = 'end';
  80                                         $tokenLength = $endLength;
  81                                 } else {
  82                                         $tokenType = 'start';
  83                                         $tokenLength = strlen( $m[0][0] );
  84                                 }
  85                         } elseif ( $m[2][0] != '' ) {
  86                                 $tokenType = 'end';
  87                                 $tokenLength = strlen( $m[0][0] );
  88                         } else {
  89                                 throw new MWException( 'Invalid delimiter given to ' . __METHOD__ );
  90                         }
  91
  92                         if ( $tokenType == 'start' ) {
  93                                 # Only move the start position if we haven't already found a start
  94                                 # This means that START START END matches outer pair
  95                                 if ( !$foundStart ) {
  96                                         # Found start
  97                                         $inputPos = $tokenOffset + $tokenLength;
  98                                         # Write out the non-matching section
  99                                         $output .= substr( $subject, $outputPos, $tokenOffset - $outputPos );
 100                                         $outputPos = $tokenOffset;
 101                                         $contentPos = $inputPos;
 102                                         $foundStart = true;
 103                                 } else {
 104                                         # Move the input position past the *first character* of START,
 105                                         # to protect against missing END when it overlaps with START
 106                                         $inputPos = $tokenOffset + 1;
 107                                 }
 108                         } elseif ( $tokenType == 'end' ) {
 109                                 if ( $foundStart ) {
 110                                         # Found match
 111                                         $output .= call_user_func( $callback, array(
 112                                                 substr( $subject, $outputPos, $tokenOffset + $tokenLength - $outputPos ),
 113                                                 substr( $subject, $contentPos, $tokenOffset - $contentPos )
 114                                         ));
 115                                         $foundStart = false;
 116                                 } else {
 117                                         # Non-matching end, write it out
 118                                         $output .= substr( $subject, $inputPos, $tokenOffset + $tokenLength - $outputPos );
 119                                 }
 120                                 $inputPos = $outputPos = $tokenOffset + $tokenLength;
 121                         } else {
 122                                 throw new MWException( 'Invalid delimiter given to ' . __METHOD__ );
 123                         }
 124                 }
 125                 if ( $outputPos < strlen( $subject ) ) {
 126                         $output .= substr( $subject, $outputPos );
 127                 }
 128                 return $output;
 129         }
 130
 131         /**
 132          * Perform an operation equivalent to
 133          *
 134          *   preg_replace( "!$startDelim(.*)$endDelim!$flags", $replace, $subject )
 135          *
 136          * @param $startDelim String: start delimiter regular expression
 137          * @param $endDelim String: end delimiter regular expression
 138          * @param $replace String: replacement string. May contain $1, which will be
 139          *                 replaced by the text between the delimiters
 140          * @param $subject String to search
 141          * @param $flags String: regular expression flags
 142          * @return String: The string with the matches replaced
 143          */
 144         static function delimiterReplace( $startDelim, $endDelim, $replace, $subject, $flags = '' ) {
 145                 $replacer = new RegexlikeReplacer( $replace );
 146                 return self::delimiterReplaceCallback( $startDelim, $endDelim,
 147                         $replacer->cb(), $subject, $flags );
 148         }
 149
 150         /**
 151          * More or less "markup-safe" explode()
 152          * Ignores any instances of the separator inside <...>
 153          * @param $separator String
 154          * @param $text String
 155          * @return array
 156          */
 157         static function explodeMarkup( $separator, $text ) {
 158                 $placeholder = "\x00";
 159
 160                 // Remove placeholder instances
 161                 $text = str_replace( $placeholder, '', $text );
 162
 163                 // Replace instances of the separator inside HTML-like tags with the placeholder
 164                 $replacer = new DoubleReplacer( $separator, $placeholder );
 165                 $cleaned = StringUtils::delimiterReplaceCallback( '<', '>', $replacer->cb(), $text );
 166
 167                 // Explode, then put the replaced separators back in
 168                 $items = explode( $separator, $cleaned );
 169                 foreach( $items as $i => $str ) {
 170                         $items[$i] = str_replace( $placeholder, $separator, $str );
 171                 }
 172
 173                 return $items;
 174         }
 175
 176         /**
 177          * Escape a string to make it suitable for inclusion in a preg_replace()
 178          * replacement parameter.
 179          *
 180          * @param $string String
 181          * @return String
 182          */
 183         static function escapeRegexReplacement( $string ) {
 184                 $string = str_replace( '\\', '\\\\', $string );
 185                 $string = str_replace( '$', '\\$', $string );
 186                 return $string;
 187         }
 188
 189         /**
 190          * Workalike for explode() with limited memory usage.
 191          * Returns an Iterator
 192          * @param $separator
 193          * @param $subject
 194          * @return \ArrayIterator|\ExplodeIterator
 195          */
 196         static function explode( $separator, $subject ) {
 197                 if ( substr_count( $subject, $separator ) > 1000 ) {
 198                         return new ExplodeIterator( $separator, $subject );
 199                 } else {
 200                         return new ArrayIterator( explode( $separator, $subject ) );
 201                 }
 202         }
 203 }
 204
 205 /**
 206  * Base class for "replacers", objects used in preg_replace_callback() and
 207  * StringUtils::delimiterReplaceCallback()
 208  */
 209 class Replacer {
 210         function cb() {
 211                 return array( &$this, 'replace' );
 212         }
 213 }
 214
 215 /**
 216  * Class to replace regex matches with a string similar to that used in preg_replace()
 217  */
 218 class RegexlikeReplacer extends Replacer {
 219         var $r;
 220         function __construct( $r ) {
 221                 $this->r = $r;
 222         }
 223
 224         function replace( $matches ) {
 225                 $pairs = array();
 226                 foreach ( $matches as $i => $match ) {
 227                         $pairs["\$$i"] = $match;
 228                 }
 229                 return strtr( $this->r, $pairs );
 230         }
 231
 232 }
 233
 234 /**
 235  * Class to perform secondary replacement within each replacement string
 236  */
 237 class DoubleReplacer extends Replacer {
 238         function __construct( $from, $to, $index = 0 ) {
 239                 $this->from = $from;
 240                 $this->to = $to;
 241                 $this->index = $index;
 242         }
 243
 244         function replace( $matches ) {
 245                 return str_replace( $this->from, $this->to, $matches[$this->index] );
 246         }
 247 }
 248
 249 /**
 250  * Class to perform replacement based on a simple hashtable lookup
 251  */
 252 class HashtableReplacer extends Replacer {
 253         var $table, $index;
 254
 255         function __construct( $table, $index = 0 ) {
 256                 $this->table = $table;
 257                 $this->index = $index;
 258         }
 259
 260         function replace( $matches ) {
 261                 return $this->table[$matches[$this->index]];
 262         }
 263 }
 264
 265 /**
 266  * Replacement array for FSS with fallback to strtr()
 267  * Supports lazy initialisation of FSS resource
 268  */
 269 class ReplacementArray {
 270         /*mostly private*/ var $data = false;
 271         /*mostly private*/ var $fss = false;
 272
 273         /**
 274          * Create an object with the specified replacement array
 275          * The array should have the same form as the replacement array for strtr()
 276          */
 277         function __construct( $data = array() ) {
 278                 $this->data = $data;
 279         }
 280
 281         function __sleep() {
 282                 return array( 'data' );
 283         }
 284
 285         function __wakeup() {
 286                 $this->fss = false;
 287         }
 288
 289         /**
 290          * Set the whole replacement array at once
 291          */
 292         function setArray( $data ) {
 293                 $this->data = $data;
 294                 $this->fss = false;
 295         }
 296
 297         function getArray() {
 298                 return $this->data;
 299         }
 300
 301         /**
 302          * Set an element of the replacement array
 303          */
 304         function setPair( $from, $to ) {
 305                 $this->data[$from] = $to;
 306                 $this->fss = false;
 307         }
 308
 309         function mergeArray( $data ) {
 310                 $this->data = array_merge( $this->data, $data );
 311                 $this->fss = false;
 312         }
 313
 314         function merge( $other ) {
 315                 $this->data = array_merge( $this->data, $other->data );
 316                 $this->fss = false;
 317         }
 318
 319         function removePair( $from ) {
 320                 unset($this->data[$from]);
 321                 $this->fss = false;
 322         }
 323
 324         function removeArray( $data ) {
 325                 foreach( $data as $from => $to )
 326                         $this->removePair( $from );
 327                 $this->fss = false;
 328         }
 329
 330         function replace( $subject ) {
 331                 if ( function_exists( 'fss_prep_replace' ) ) {
 332                         wfProfileIn( __METHOD__.'-fss' );
 333                         if ( $this->fss === false ) {
 334                                 $this->fss = fss_prep_replace( $this->data );
 335                         }
 336                         $result = fss_exec_replace( $this->fss, $subject );
 337                         wfProfileOut( __METHOD__.'-fss' );
 338                 } else {
 339                         wfProfileIn( __METHOD__.'-strtr' );
 340                         $result = strtr( $subject, $this->data );
 341                         wfProfileOut( __METHOD__.'-strtr' );
 342                 }
 343                 return $result;
 344         }
 345 }
 346
 347 /**
 348  * An iterator which works exactly like:
 349  *
 350  * foreach ( explode( $delim, $s ) as $element ) {
 351  *    ...
 352  * }
 353  *
 354  * Except it doesn't use 193 byte per element
 355  */
 356 class ExplodeIterator implements Iterator {
 357         // The subject string
 358         var $subject, $subjectLength;
 359
 360         // The delimiter
 361         var $delim, $delimLength;
 362
 363         // The position of the start of the line
 364         var $curPos;
 365
 366         // The position after the end of the next delimiter
 367         var $endPos;
 368
 369         // The current token
 370         var $current;
 371
 372         /**
 373          * Construct a DelimIterator
 374          */
 375         function __construct( $delim, $s ) {
 376                 $this->subject = $s;
 377                 $this->delim = $delim;
 378
 379                 // Micro-optimisation (theoretical)
 380                 $this->subjectLength = strlen( $s );
 381                 $this->delimLength = strlen( $delim );
 382
 383                 $this->rewind();
 384         }
 385
 386         function rewind() {
 387                 $this->curPos = 0;
 388                 $this->endPos = strpos( $this->subject, $this->delim );
 389                 $this->refreshCurrent();
 390         }
 391
 392
 393         function refreshCurrent() {
 394                 if ( $this->curPos === false ) {
 395                         $this->current = false;
 396                 } elseif ( $this->curPos >= $this->subjectLength ) {
 397                         $this->current = '';
 398                 } elseif ( $this->endPos === false ) {
 399                         $this->current = substr( $this->subject, $this->curPos );
 400                 } else {
 401                         $this->current = substr( $this->subject, $this->curPos, $this->endPos - $this->curPos );
 402                 }
 403         }
 404
 405         function current() {
 406                 return $this->current;
 407         }
 408
 409         function key() {
 410                 return $this->curPos;
 411         }
 412
 413         function next() {
 414                 if ( $this->endPos === false ) {
 415                         $this->curPos = false;
 416                 } else {
 417                         $this->curPos = $this->endPos + $this->delimLength;
 418                         if ( $this->curPos >= $this->subjectLength ) {
 419                                 $this->endPos = false;
 420                         } else {
 421                                 $this->endPos = strpos( $this->subject, $this->delim, $this->curPos );
 422                         }
 423                 }
 424                 $this->refreshCurrent();
 425                 return $this->current;
 426         }
 427
 428         function valid() {
 429                 return $this->curPos !== false;
 430         }
 431 }
 432