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