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