includes/parser/Preprocessor_Hash.php

   1 <?php
   2 /**
   3  * Preprocessor using PHP arrays
   4  *
   5  * @file
   6  * @ingroup Parser
   7  */
   8
   9 /**
  10  * Differences from DOM schema:
  11  *   * attribute nodes are children
  12  *   * <h> nodes that aren't at the top are replaced with <possible-h>
  13  * @ingroup Parser
  14  */
  15 class Preprocessor_Hash implements Preprocessor {
  16         /**
  17          * @var Parser
  18          */
  19         var $parser;
  20
  21         const CACHE_VERSION = 1;
  22
  23         function __construct( $parser ) {
  24                 $this->parser = $parser;
  25         }
  26
  27         /**
  28          * @return PPFrame_Hash
  29          */
  30         function newFrame() {
  31                 return new PPFrame_Hash( $this );
  32         }
  33
  34         /**
  35          * @param $args
  36          * @return PPCustomFrame_Hash
  37          */
  38         function newCustomFrame( $args ) {
  39                 return new PPCustomFrame_Hash( $this, $args );
  40         }
  41
  42         function newPartNodeArray( $values ) {
  43                 $list = array();
  44
  45                 foreach ( $values as $k => $val ) {
  46                         $partNode = new PPNode_Hash_Tree( 'part' );
  47                         $nameNode = new PPNode_Hash_Tree( 'name' );
  48
  49                         if ( is_int( $k ) ) {
  50                                 $nameNode->addChild( new PPNode_Hash_Attr( 'index', $k ) );
  51                                 $partNode->addChild( $nameNode );
  52                         } else {
  53                                 $nameNode->addChild( new PPNode_Hash_Text( $k ) );
  54                                 $partNode->addChild( $nameNode );
  55                                 $partNode->addChild( new PPNode_Hash_Text( '=' ) );
  56                         }
  57
  58                         $valueNode = new PPNode_Hash_Tree( 'value' );
  59                         $valueNode->addChild( new PPNode_Hash_Text( $val ) );
  60                         $partNode->addChild( $valueNode );
  61
  62                         $list[] = $partNode;
  63                 }
  64
  65                 $node = new PPNode_Hash_Array( $list );
  66                 return $node;
  67         }
  68
  69         /**
  70          * Preprocess some wikitext and return the document tree.
  71          * This is the ghost of Parser::replace_variables().
  72          *
  73          * @param $text String: the text to parse
  74          * @param $flags Integer: bitwise combination of:
  75          *          Parser::PTD_FOR_INCLUSION    Handle <noinclude>/<includeonly> as if the text is being
  76          *                                     included. Default is to assume a direct page view.
  77          *
  78          * The generated DOM tree must depend only on the input text and the flags.
  79          * The DOM tree must be the same in OT_HTML and OT_WIKI mode, to avoid a regression of bug 4899.
  80          *
  81          * Any flag added to the $flags parameter here, or any other parameter liable to cause a
  82          * change in the DOM tree for a given text, must be passed through the section identifier
  83          * in the section edit link and thus back to extractSections().
  84          *
  85          * The output of this function is currently only cached in process memory, but a persistent
  86          * cache may be implemented at a later date which takes further advantage of these strict
  87          * dependency requirements.
  88          *
  89          * @private
  90          */
  91         function preprocessToObj( $text, $flags = 0 ) {
  92                 wfProfileIn( __METHOD__ );
  93
  94                 // Check cache.
  95                 global $wgMemc, $wgPreprocessorCacheThreshold;
  96
  97                 $cacheable = $wgPreprocessorCacheThreshold !== false && strlen( $text ) > $wgPreprocessorCacheThreshold;
  98                 if ( $cacheable ) {
  99                         wfProfileIn( __METHOD__.'-cacheable' );
 100
 101                         $cacheKey = wfMemcKey( 'preprocess-hash', md5($text), $flags );
 102                         $cacheValue = $wgMemc->get( $cacheKey );
 103                         if ( $cacheValue ) {
 104                                 $version = substr( $cacheValue, 0, 8 );
 105                                 if ( intval( $version ) == self::CACHE_VERSION ) {
 106                                         $hash = unserialize( substr( $cacheValue, 8 ) );
 107                                         // From the cache
 108                                         wfDebugLog( "Preprocessor",
 109                                                 "Loaded preprocessor hash from memcached (key $cacheKey)" );
 110                                         wfProfileOut( __METHOD__.'-cacheable' );
 111                                         wfProfileOut( __METHOD__ );
 112                                         return $hash;
 113                                 }
 114                         }
 115                         wfProfileIn( __METHOD__.'-cache-miss' );
 116                 }
 117
 118                 $rules = array(
 119                         '{' => array(
 120                                 'end' => '}',
 121                                 'names' => array(
 122                                         2 => 'template',
 123                                         3 => 'tplarg',
 124                                 ),
 125                                 'min' => 2,
 126                                 'max' => 3,
 127                         ),
 128                         '[' => array(
 129                                 'end' => ']',
 130                                 'names' => array( 2 => null ),
 131                                 'min' => 2,
 132                                 'max' => 2,
 133                         )
 134                 );
 135
 136                 $forInclusion = $flags & Parser::PTD_FOR_INCLUSION;
 137
 138                 $xmlishElements = $this->parser->getStripList();
 139                 $enableOnlyinclude = false;
 140                 if ( $forInclusion ) {
 141                         $ignoredTags = array( 'includeonly', '/includeonly' );
 142                         $ignoredElements = array( 'noinclude' );
 143                         $xmlishElements[] = 'noinclude';
 144                         if ( strpos( $text, '<onlyinclude>' ) !== false && strpos( $text, '</onlyinclude>' ) !== false ) {
 145                                 $enableOnlyinclude = true;
 146                         }
 147                 } else if ( $this->parser->ot['wiki'] ) {
 148                         $ignoredTags = array( 'noinclude', '/noinclude', 'onlyinclude', '/onlyinclude', 'includeonly', '/includeonly' );
 149                         $ignoredElements = array();
 150                 } else {
 151                         $ignoredTags = array( 'noinclude', '/noinclude', 'onlyinclude', '/onlyinclude' );
 152                         $ignoredElements = array( 'includeonly' );
 153                         $xmlishElements[] = 'includeonly';
 154                 }
 155                 $xmlishRegex = implode( '|', array_merge( $xmlishElements, $ignoredTags ) );
 156
 157                 // Use "A" modifier (anchored) instead of "^", because ^ doesn't work with an offset
 158                 $elementsRegex = "~($xmlishRegex)(?:\s|\/>|>)|(!--)~iA";
 159
 160                 $stack = new PPDStack_Hash;
 161
 162                 $searchBase = "[{<\n";
 163                 $revText = strrev( $text ); // For fast reverse searches
 164
 165                 $i = 0;                     # Input pointer, starts out pointing to a pseudo-newline before the start
 166                 $accum =& $stack->getAccum();   # Current accumulator
 167                 $findEquals = false;            # True to find equals signs in arguments
 168                 $findPipe = false;              # True to take notice of pipe characters
 169                 $headingIndex = 1;
 170                 $inHeading = false;        # True if $i is inside a possible heading
 171                 $noMoreGT = false;         # True if there are no more greater-than (>) signs right of $i
 172                 $findOnlyinclude = $enableOnlyinclude; # True to ignore all input up to the next <onlyinclude>
 173                 $fakeLineStart = true;     # Do a line-start run without outputting an LF character
 174
 175                 while ( true ) {
 176                         //$this->memCheck();
 177
 178                         if ( $findOnlyinclude ) {
 179                                 // Ignore all input up to the next <onlyinclude>
 180                                 $startPos = strpos( $text, '<onlyinclude>', $i );
 181                                 if ( $startPos === false ) {
 182                                         // Ignored section runs to the end
 183                                         $accum->addNodeWithText( 'ignore', substr( $text, $i ) );
 184                                         break;
 185                                 }
 186                                 $tagEndPos = $startPos + strlen( '<onlyinclude>' ); // past-the-end
 187                                 $accum->addNodeWithText( 'ignore', substr( $text, $i, $tagEndPos - $i ) );
 188                                 $i = $tagEndPos;
 189                                 $findOnlyinclude = false;
 190                         }
 191
 192                         if ( $fakeLineStart ) {
 193                                 $found = 'line-start';
 194                                 $curChar = '';
 195                         } else {
 196                                 # Find next opening brace, closing brace or pipe
 197                                 $search = $searchBase;
 198                                 if ( $stack->top === false ) {
 199                                         $currentClosing = '';
 200                                 } else {
 201                                         $currentClosing = $stack->top->close;
 202                                         $search .= $currentClosing;
 203                                 }
 204                                 if ( $findPipe ) {
 205                                         $search .= '|';
 206                                 }
 207                                 if ( $findEquals ) {
 208                                         // First equals will be for the template
 209                                         $search .= '=';
 210                                 }
 211                                 $rule = null;
 212                                 # Output literal section, advance input counter
 213                                 $literalLength = strcspn( $text, $search, $i );
 214                                 if ( $literalLength > 0 ) {
 215                                         $accum->addLiteral( substr( $text, $i, $literalLength ) );
 216                                         $i += $literalLength;
 217                                 }
 218                                 if ( $i >= strlen( $text ) ) {
 219                                         if ( $currentClosing == "\n" ) {
 220                                                 // Do a past-the-end run to finish off the heading
 221                                                 $curChar = '';
 222                                                 $found = 'line-end';
 223                                         } else {
 224                                                 # All done
 225                                                 break;
 226                                         }
 227                                 } else {
 228                                         $curChar = $text[$i];
 229                                         if ( $curChar == '|' ) {
 230                                                 $found = 'pipe';
 231                                         } elseif ( $curChar == '=' ) {
 232                                                 $found = 'equals';
 233                                         } elseif ( $curChar == '<' ) {
 234                                                 $found = 'angle';
 235                                         } elseif ( $curChar == "\n" ) {
 236                                                 if ( $inHeading ) {
 237                                                         $found = 'line-end';
 238                                                 } else {
 239                                                         $found = 'line-start';
 240                                                 }
 241                                         } elseif ( $curChar == $currentClosing ) {
 242                                                 $found = 'close';
 243                                         } elseif ( isset( $rules[$curChar] ) ) {
 244                                                 $found = 'open';
 245                                                 $rule = $rules[$curChar];
 246                                         } else {
 247                                                 # Some versions of PHP have a strcspn which stops on null characters
 248                                                 # Ignore and continue
 249                                                 ++$i;
 250                                                 continue;
 251                                         }
 252                                 }
 253                         }
 254
 255                         if ( $found == 'angle' ) {
 256                                 $matches = false;
 257                                 // Handle </onlyinclude>
 258                                 if ( $enableOnlyinclude && substr( $text, $i, strlen( '</onlyinclude>' ) ) == '</onlyinclude>' ) {
 259                                         $findOnlyinclude = true;
 260                                         continue;
 261                                 }
 262
 263                                 // Determine element name
 264                                 if ( !preg_match( $elementsRegex, $text, $matches, 0, $i + 1 ) ) {
 265                                         // Element name missing or not listed
 266                                         $accum->addLiteral( '<' );
 267                                         ++$i;
 268                                         continue;
 269                                 }
 270                                 // Handle comments
 271                                 if ( isset( $matches[2] ) && $matches[2] == '!--' ) {
 272                                         // To avoid leaving blank lines, when a comment is both preceded
 273                                         // and followed by a newline (ignoring spaces), trim leading and
 274                                         // trailing spaces and one of the newlines.
 275
 276                                         // Find the end
 277                                         $endPos = strpos( $text, '-->', $i + 4 );
 278                                         if ( $endPos === false ) {
 279                                                 // Unclosed comment in input, runs to end
 280                                                 $inner = substr( $text, $i );
 281                                                 $accum->addNodeWithText( 'comment', $inner );
 282                                                 $i = strlen( $text );
 283                                         } else {
 284                                                 // Search backwards for leading whitespace
 285                                                 $wsStart = $i ? ( $i - strspn( $revText, ' ', strlen( $text ) - $i ) ) : 0;
 286                                                 // Search forwards for trailing whitespace
 287                                                 // $wsEnd will be the position of the last space (or the '>' if there's none)
 288                                                 $wsEnd = $endPos + 2 + strspn( $text, ' ', $endPos + 3 );
 289                                                 // Eat the line if possible
 290                                                 // TODO: This could theoretically be done if $wsStart == 0, i.e. for comments at
 291                                                 // the overall start. That's not how Sanitizer::removeHTMLcomments() did it, but
 292                                                 // it's a possible beneficial b/c break.
 293                                                 if ( $wsStart > 0 && substr( $text, $wsStart - 1, 1 ) == "\n"
 294                                                         && substr( $text, $wsEnd + 1, 1 ) == "\n" )
 295                                                 {
 296                                                         $startPos = $wsStart;
 297                                                         $endPos = $wsEnd + 1;
 298                                                         // Remove leading whitespace from the end of the accumulator
 299                                                         // Sanity check first though
 300                                                         $wsLength = $i - $wsStart;
 301                                                         if ( $wsLength > 0
 302                                                                 && $accum->lastNode instanceof PPNode_Hash_Text
 303                                                                 && substr( $accum->lastNode->value, -$wsLength ) === str_repeat( ' ', $wsLength ) )
 304                                                         {
 305                                                                 $accum->lastNode->value = substr( $accum->lastNode->value, 0, -$wsLength );
 306                                                         }
 307                                                         // Do a line-start run next time to look for headings after the comment
 308                                                         $fakeLineStart = true;
 309                                                 } else {
 310                                                         // No line to eat, just take the comment itself
 311                                                         $startPos = $i;
 312                                                         $endPos += 2;
 313                                                 }
 314
 315                                                 if ( $stack->top ) {
 316                                                         $part = $stack->top->getCurrentPart();
 317                                                         if ( ! (isset( $part->commentEnd ) && $part->commentEnd == $wsStart - 1 )) {
 318                                                                 $part->visualEnd = $wsStart;
 319                                                         }
 320                                                         // Else comments abutting, no change in visual end
 321                                                         $part->commentEnd = $endPos;
 322                                                 }
 323                                                 $i = $endPos + 1;
 324                                                 $inner = substr( $text, $startPos, $endPos - $startPos + 1 );
 325                                                 $accum->addNodeWithText( 'comment', $inner );
 326                                         }
 327                                         continue;
 328                                 }
 329                                 $name = $matches[1];
 330                                 $lowerName = strtolower( $name );
 331                                 $attrStart = $i + strlen( $name ) + 1;
 332
 333                                 // Find end of tag
 334                                 $tagEndPos = $noMoreGT ? false : strpos( $text, '>', $attrStart );
 335                                 if ( $tagEndPos === false ) {
 336                                         // Infinite backtrack
 337                                         // Disable tag search to prevent worst-case O(N^2) performance
 338                                         $noMoreGT = true;
 339                                         $accum->addLiteral( '<' );
 340                                         ++$i;
 341                                         continue;
 342                                 }
 343
 344                                 // Handle ignored tags
 345                                 if ( in_array( $lowerName, $ignoredTags ) ) {
 346                                         $accum->addNodeWithText( 'ignore', substr( $text, $i, $tagEndPos - $i + 1 ) );
 347                                         $i = $tagEndPos + 1;
 348                                         continue;
 349                                 }
 350
 351                                 $tagStartPos = $i;
 352                                 if ( $text[$tagEndPos-1] == '/' ) {
 353                                         // Short end tag
 354                                         $attrEnd = $tagEndPos - 1;
 355                                         $inner = null;
 356                                         $i = $tagEndPos + 1;
 357                                         $close = null;
 358                                 } else {
 359                                         $attrEnd = $tagEndPos;
 360                                         // Find closing tag
 361                                         if ( preg_match( "/<\/" . preg_quote( $name, '/' ) . "\s*>/i",
 362                                                         $text, $matches, PREG_OFFSET_CAPTURE, $tagEndPos + 1 ) )
 363                                         {
 364                                                 $inner = substr( $text, $tagEndPos + 1, $matches[0][1] - $tagEndPos - 1 );
 365                                                 $i = $matches[0][1] + strlen( $matches[0][0] );
 366                                                 $close = $matches[0][0];
 367                                         } else {
 368                                                 // No end tag -- let it run out to the end of the text.
 369                                                 $inner = substr( $text, $tagEndPos + 1 );
 370                                                 $i = strlen( $text );
 371                                                 $close = null;
 372                                         }
 373                                 }
 374                                 // <includeonly> and <noinclude> just become <ignore> tags
 375                                 if ( in_array( $lowerName, $ignoredElements ) ) {
 376                                         $accum->addNodeWithText(  'ignore', substr( $text, $tagStartPos, $i - $tagStartPos ) );
 377                                         continue;
 378                                 }
 379
 380                                 if ( $attrEnd <= $attrStart ) {
 381                                         $attr = '';
 382                                 } else {
 383                                         // Note that the attr element contains the whitespace between name and attribute,
 384                                         // this is necessary for precise reconstruction during pre-save transform.
 385                                         $attr = substr( $text, $attrStart, $attrEnd - $attrStart );
 386                                 }
 387
 388                                 $extNode = new PPNode_Hash_Tree( 'ext' );
 389                                 $extNode->addChild( PPNode_Hash_Tree::newWithText( 'name', $name ) );
 390                                 $extNode->addChild( PPNode_Hash_Tree::newWithText( 'attr', $attr ) );
 391                                 if ( $inner !== null ) {
 392                                         $extNode->addChild( PPNode_Hash_Tree::newWithText( 'inner', $inner ) );
 393                                 }
 394                                 if ( $close !== null ) {
 395                                         $extNode->addChild( PPNode_Hash_Tree::newWithText( 'close', $close ) );
 396                                 }
 397                                 $accum->addNode( $extNode );
 398                         }
 399
 400                         elseif ( $found == 'line-start' ) {
 401                                 // Is this the start of a heading?
 402                                 // Line break belongs before the heading element in any case
 403                                 if ( $fakeLineStart ) {
 404                                         $fakeLineStart = false;
 405                                 } else {
 406                                         $accum->addLiteral( $curChar );
 407                                         $i++;
 408                                 }
 409
 410                                 $count = strspn( $text, '=', $i, 6 );
 411                                 if ( $count == 1 && $findEquals ) {
 412                                         // DWIM: This looks kind of like a name/value separator
 413                                         // Let's let the equals handler have it and break the potential heading
 414                                         // This is heuristic, but AFAICT the methods for completely correct disambiguation are very complex.
 415                                 } elseif ( $count > 0 ) {
 416                                         $piece = array(
 417                                                 'open' => "\n",
 418                                                 'close' => "\n",
 419                                                 'parts' => array( new PPDPart_Hash( str_repeat( '=', $count ) ) ),
 420                                                 'startPos' => $i,
 421                                                 'count' => $count );
 422                                         $stack->push( $piece );
 423                                         $accum =& $stack->getAccum();
 424                                         extract( $stack->getFlags() );
 425                                         $i += $count;
 426                                 }
 427                         }
 428
 429                         elseif ( $found == 'line-end' ) {
 430                                 $piece = $stack->top;
 431                                 // A heading must be open, otherwise \n wouldn't have been in the search list
 432                                 assert( $piece->open == "\n" );
 433                                 $part = $piece->getCurrentPart();
 434                                 // Search back through the input to see if it has a proper close
 435                                 // Do this using the reversed string since the other solutions (end anchor, etc.) are inefficient
 436                                 $wsLength = strspn( $revText, " \t", strlen( $text ) - $i );
 437                                 $searchStart = $i - $wsLength;
 438                                 if ( isset( $part->commentEnd ) && $searchStart - 1 == $part->commentEnd ) {
 439                                         // Comment found at line end
 440                                         // Search for equals signs before the comment
 441                                         $searchStart = $part->visualEnd;
 442                                         $searchStart -= strspn( $revText, " \t", strlen( $text ) - $searchStart );
 443                                 }
 444                                 $count = $piece->count;
 445                                 $equalsLength = strspn( $revText, '=', strlen( $text ) - $searchStart );
 446                                 if ( $equalsLength > 0 ) {
 447                                         if ( $searchStart - $equalsLength == $piece->startPos ) {
 448                                                 // This is just a single string of equals signs on its own line
 449                                                 // Replicate the doHeadings behaviour /={count}(.+)={count}/
 450                                                 // First find out how many equals signs there really are (don't stop at 6)
 451                                                 $count = $equalsLength;
 452                                                 if ( $count < 3 ) {
 453                                                         $count = 0;
 454                                                 } else {
 455                                                         $count = min( 6, intval( ( $count - 1 ) / 2 ) );
 456                                                 }
 457                                         } else {
 458                                                 $count = min( $equalsLength, $count );
 459                                         }
 460                                         if ( $count > 0 ) {
 461                                                 // Normal match, output <h>
 462                                                 $element = new PPNode_Hash_Tree( 'possible-h' );
 463                                                 $element->addChild( new PPNode_Hash_Attr( 'level', $count ) );
 464                                                 $element->addChild( new PPNode_Hash_Attr( 'i', $headingIndex++ ) );
 465                                                 $element->lastChild->nextSibling = $accum->firstNode;
 466                                                 $element->lastChild = $accum->lastNode;
 467                                         } else {
 468                                                 // Single equals sign on its own line, count=0
 469                                                 $element = $accum;
 470                                         }
 471                                 } else {
 472                                         // No match, no <h>, just pass down the inner text
 473                                         $element = $accum;
 474                                 }
 475                                 // Unwind the stack
 476                                 $stack->pop();
 477                                 $accum =& $stack->getAccum();
 478                                 extract( $stack->getFlags() );
 479
 480                                 // Append the result to the enclosing accumulator
 481                                 if ( $element instanceof PPNode ) {
 482                                         $accum->addNode( $element );
 483                                 } else {
 484                                         $accum->addAccum( $element );
 485                                 }
 486                                 // Note that we do NOT increment the input pointer.
 487                                 // This is because the closing linebreak could be the opening linebreak of
 488                                 // another heading. Infinite loops are avoided because the next iteration MUST
 489                                 // hit the heading open case above, which unconditionally increments the
 490                                 // input pointer.
 491                         }
 492
 493                         elseif ( $found == 'open' ) {
 494                                 # count opening brace characters
 495                                 $count = strspn( $text, $curChar, $i );
 496
 497                                 # we need to add to stack only if opening brace count is enough for one of the rules
 498                                 if ( $count >= $rule['min'] ) {
 499                                         # Add it to the stack
 500                                         $piece = array(
 501                                                 'open' => $curChar,
 502                                                 'close' => $rule['end'],
 503                                                 'count' => $count,
 504                                                 'lineStart' => ($i == 0 || $text[$i-1] == "\n"),
 505                                         );
 506
 507                                         $stack->push( $piece );
 508                                         $accum =& $stack->getAccum();
 509                                         extract( $stack->getFlags() );
 510                                 } else {
 511                                         # Add literal brace(s)
 512                                         $accum->addLiteral( str_repeat( $curChar, $count ) );
 513                                 }
 514                                 $i += $count;
 515                         }
 516
 517                         elseif ( $found == 'close' ) {
 518                                 $piece = $stack->top;
 519                                 # lets check if there are enough characters for closing brace
 520                                 $maxCount = $piece->count;
 521                                 $count = strspn( $text, $curChar, $i, $maxCount );
 522
 523                                 # check for maximum matching characters (if there are 5 closing
 524                                 # characters, we will probably need only 3 - depending on the rules)
 525                                 $rule = $rules[$piece->open];
 526                                 if ( $count > $rule['max'] ) {
 527                                         # The specified maximum exists in the callback array, unless the caller
 528                                         # has made an error
 529                                         $matchingCount = $rule['max'];
 530                                 } else {
 531                                         # Count is less than the maximum
 532                                         # Skip any gaps in the callback array to find the true largest match
 533                                         # Need to use array_key_exists not isset because the callback can be null
 534                                         $matchingCount = $count;
 535                                         while ( $matchingCount > 0 && !array_key_exists( $matchingCount, $rule['names'] ) ) {
 536                                                 --$matchingCount;
 537                                         }
 538                                 }
 539
 540                                 if ($matchingCount <= 0) {
 541                                         # No matching element found in callback array
 542                                         # Output a literal closing brace and continue
 543                                         $accum->addLiteral( str_repeat( $curChar, $count ) );
 544                                         $i += $count;
 545                                         continue;
 546                                 }
 547                                 $name = $rule['names'][$matchingCount];
 548                                 if ( $name === null ) {
 549                                         // No element, just literal text
 550                                         $element = $piece->breakSyntax( $matchingCount );
 551                                         $element->addLiteral( str_repeat( $rule['end'], $matchingCount ) );
 552                                 } else {
 553                                         # Create XML element
 554                                         # Note: $parts is already XML, does not need to be encoded further
 555                                         $parts = $piece->parts;
 556                                         $titleAccum = $parts[0]->out;
 557                                         unset( $parts[0] );
 558
 559                                         $element = new PPNode_Hash_Tree( $name );
 560
 561                                         # The invocation is at the start of the line if lineStart is set in
 562                                         # the stack, and all opening brackets are used up.
 563                                         if ( $maxCount == $matchingCount && !empty( $piece->lineStart ) ) {
 564                                                 $element->addChild( new PPNode_Hash_Attr( 'lineStart', 1 ) );
 565                                         }
 566                                         $titleNode = new PPNode_Hash_Tree( 'title' );
 567                                         $titleNode->firstChild = $titleAccum->firstNode;
 568                                         $titleNode->lastChild = $titleAccum->lastNode;
 569                                         $element->addChild( $titleNode );
 570                                         $argIndex = 1;
 571                                         foreach ( $parts as $part ) {
 572                                                 if ( isset( $part->eqpos ) ) {
 573                                                         // Find equals
 574                                                         $lastNode = false;
 575                                                         for ( $node = $part->out->firstNode; $node; $node = $node->nextSibling ) {
 576                                                                 if ( $node === $part->eqpos ) {
 577                                                                         break;
 578                                                                 }
 579                                                                 $lastNode = $node;
 580                                                         }
 581                                                         if ( !$node ) {
 582                                                                 throw new MWException( __METHOD__. ': eqpos not found' );
 583                                                         }
 584                                                         if ( $node->name !== 'equals' ) {
 585                                                                 throw new MWException( __METHOD__ .': eqpos is not equals' );
 586                                                         }
 587                                                         $equalsNode = $node;
 588
 589                                                         // Construct name node
 590                                                         $nameNode = new PPNode_Hash_Tree( 'name' );
 591                                                         if ( $lastNode !== false ) {
 592                                                                 $lastNode->nextSibling = false;
 593                                                                 $nameNode->firstChild = $part->out->firstNode;
 594                                                                 $nameNode->lastChild = $lastNode;
 595                                                         }
 596
 597                                                         // Construct value node
 598                                                         $valueNode = new PPNode_Hash_Tree( 'value' );
 599                                                         if ( $equalsNode->nextSibling !== false ) {
 600                                                                 $valueNode->firstChild = $equalsNode->nextSibling;
 601                                                                 $valueNode->lastChild = $part->out->lastNode;
 602                                                         }
 603                                                         $partNode = new PPNode_Hash_Tree( 'part' );
 604                                                         $partNode->addChild( $nameNode );
 605                                                         $partNode->addChild( $equalsNode->firstChild );
 606                                                         $partNode->addChild( $valueNode );
 607                                                         $element->addChild( $partNode );
 608                                                 } else {
 609                                                         $partNode = new PPNode_Hash_Tree( 'part' );
 610                                                         $nameNode = new PPNode_Hash_Tree( 'name' );
 611                                                         $nameNode->addChild( new PPNode_Hash_Attr( 'index', $argIndex++ ) );
 612                                                         $valueNode = new PPNode_Hash_Tree( 'value' );
 613                                                         $valueNode->firstChild = $part->out->firstNode;
 614                                                         $valueNode->lastChild = $part->out->lastNode;
 615                                                         $partNode->addChild( $nameNode );
 616                                                         $partNode->addChild( $valueNode );
 617                                                         $element->addChild( $partNode );
 618                                                 }
 619                                         }
 620                                 }
 621
 622                                 # Advance input pointer
 623                                 $i += $matchingCount;
 624
 625                                 # Unwind the stack
 626                                 $stack->pop();
 627                                 $accum =& $stack->getAccum();
 628
 629                                 # Re-add the old stack element if it still has unmatched opening characters remaining
 630                                 if ($matchingCount < $piece->count) {
 631                                         $piece->parts = array( new PPDPart_Hash );
 632                                         $piece->count -= $matchingCount;
 633                                         # do we still qualify for any callback with remaining count?
 634                                         $names = $rules[$piece->open]['names'];
 635                                         $skippedBraces = 0;
 636                                         $enclosingAccum =& $accum;
 637                                         while ( $piece->count ) {
 638                                                 if ( array_key_exists( $piece->count, $names ) ) {
 639                                                         $stack->push( $piece );
 640                                                         $accum =& $stack->getAccum();
 641                                                         break;
 642                                                 }
 643                                                 --$piece->count;
 644                                                 $skippedBraces ++;
 645                                         }
 646                                         $enclosingAccum->addLiteral( str_repeat( $piece->open, $skippedBraces ) );
 647                                 }
 648
 649                                 extract( $stack->getFlags() );
 650
 651                                 # Add XML element to the enclosing accumulator
 652                                 if ( $element instanceof PPNode ) {
 653                                         $accum->addNode( $element );
 654                                 } else {
 655                                         $accum->addAccum( $element );
 656                                 }
 657                         }
 658
 659                         elseif ( $found == 'pipe' ) {
 660                                 $findEquals = true; // shortcut for getFlags()
 661                                 $stack->addPart();
 662                                 $accum =& $stack->getAccum();
 663                                 ++$i;
 664                         }
 665
 666                         elseif ( $found == 'equals' ) {
 667                                 $findEquals = false; // shortcut for getFlags()
 668                                 $accum->addNodeWithText( 'equals', '=' );
 669                                 $stack->getCurrentPart()->eqpos = $accum->lastNode;
 670                                 ++$i;
 671                         }
 672                 }
 673
 674                 # Output any remaining unclosed brackets
 675                 foreach ( $stack->stack as $piece ) {
 676                         $stack->rootAccum->addAccum( $piece->breakSyntax() );
 677                 }
 678
 679                 # Enable top-level headings
 680                 for ( $node = $stack->rootAccum->firstNode; $node; $node = $node->nextSibling ) {
 681                         if ( isset( $node->name ) && $node->name === 'possible-h' ) {
 682                                 $node->name = 'h';
 683                         }
 684                 }
 685
 686                 $rootNode = new PPNode_Hash_Tree( 'root' );
 687                 $rootNode->firstChild = $stack->rootAccum->firstNode;
 688                 $rootNode->lastChild = $stack->rootAccum->lastNode;
 689
 690                 // Cache
 691                 if ($cacheable) {
 692                         $cacheValue = sprintf( "%08d", self::CACHE_VERSION ) . serialize( $rootNode );
 693                         $wgMemc->set( $cacheKey, $cacheValue, 86400 );
 694                         wfProfileOut( __METHOD__.'-cache-miss' );
 695                         wfProfileOut( __METHOD__.'-cacheable' );
 696                         wfDebugLog( "Preprocessor", "Saved preprocessor Hash to memcached (key $cacheKey)" );
 697                 }
 698
 699                 wfProfileOut( __METHOD__ );
 700                 return $rootNode;
 701         }
 702 }
 703
 704 /**
 705  * Stack class to help Preprocessor::preprocessToObj()
 706  * @ingroup Parser
 707  */
 708 class PPDStack_Hash extends PPDStack {
 709         function __construct() {
 710                 $this->elementClass = 'PPDStackElement_Hash';
 711                 parent::__construct();
 712                 $this->rootAccum = new PPDAccum_Hash;
 713         }
 714 }
 715
 716 /**
 717  * @ingroup Parser
 718  */
 719 class PPDStackElement_Hash extends PPDStackElement {
 720         function __construct( $data = array() ) {
 721                 $this->partClass = 'PPDPart_Hash';
 722                 parent::__construct( $data );
 723         }
 724
 725         /**
 726          * Get the accumulator that would result if the close is not found.
 727          */
 728         function breakSyntax( $openingCount = false ) {
 729                 if ( $this->open == "\n" ) {
 730                         $accum = $this->parts[0]->out;
 731                 } else {
 732                         if ( $openingCount === false ) {
 733                                 $openingCount = $this->count;
 734                         }
 735                         $accum = new PPDAccum_Hash;
 736                         $accum->addLiteral( str_repeat( $this->open, $openingCount ) );
 737                         $first = true;
 738                         foreach ( $this->parts as $part ) {
 739                                 if ( $first ) {
 740                                         $first = false;
 741                                 } else {
 742                                         $accum->addLiteral( '|' );
 743                                 }
 744                                 $accum->addAccum( $part->out );
 745                         }
 746                 }
 747                 return $accum;
 748         }
 749 }
 750
 751 /**
 752  * @ingroup Parser
 753  */
 754 class PPDPart_Hash extends PPDPart {
 755         function __construct( $out = '' ) {
 756                 $accum = new PPDAccum_Hash;
 757                 if ( $out !== '' ) {
 758                         $accum->addLiteral( $out );
 759                 }
 760                 parent::__construct( $accum );
 761         }
 762 }
 763
 764 /**
 765  * @ingroup Parser
 766  */
 767 class PPDAccum_Hash {
 768         var $firstNode, $lastNode;
 769
 770         function __construct() {
 771                 $this->firstNode = $this->lastNode = false;
 772         }
 773
 774         /**
 775          * Append a string literal
 776          */
 777         function addLiteral( $s ) {
 778                 if ( $this->lastNode === false ) {
 779                         $this->firstNode = $this->lastNode = new PPNode_Hash_Text( $s );
 780                 } elseif ( $this->lastNode instanceof PPNode_Hash_Text ) {
 781                         $this->lastNode->value .= $s;
 782                 } else {
 783                         $this->lastNode->nextSibling = new PPNode_Hash_Text( $s );
 784                         $this->lastNode = $this->lastNode->nextSibling;
 785                 }
 786         }
 787
 788         /**
 789          * Append a PPNode
 790          */
 791         function addNode( PPNode $node ) {
 792                 if ( $this->lastNode === false ) {
 793                         $this->firstNode = $this->lastNode = $node;
 794                 } else {
 795                         $this->lastNode->nextSibling = $node;
 796                         $this->lastNode = $node;
 797                 }
 798         }
 799
 800         /**
 801          * Append a tree node with text contents
 802          */
 803         function addNodeWithText( $name, $value ) {
 804                 $node = PPNode_Hash_Tree::newWithText( $name, $value );
 805                 $this->addNode( $node );
 806         }
 807
 808         /**
 809          * Append a PPAccum_Hash
 810          * Takes over ownership of the nodes in the source argument. These nodes may
 811          * subsequently be modified, especially nextSibling.
 812          */
 813         function addAccum( $accum ) {
 814                 if ( $accum->lastNode === false ) {
 815                         // nothing to add
 816                 } elseif ( $this->lastNode === false ) {
 817                         $this->firstNode = $accum->firstNode;
 818                         $this->lastNode = $accum->lastNode;
 819                 } else {
 820                         $this->lastNode->nextSibling = $accum->firstNode;
 821                         $this->lastNode = $accum->lastNode;
 822                 }
 823         }
 824 }
 825
 826 /**
 827  * An expansion frame, used as a context to expand the result of preprocessToObj()
 828  * @ingroup Parser
 829  */
 830 class PPFrame_Hash implements PPFrame {
 831
 832         /**
 833          * @var Parser
 834          */
 835         var $parser;
 836
 837         /**
 838          * @var Preprocessor
 839          */
 840         var $preprocessor;
 841
 842         /**
 843          * @var Title
 844          */
 845         var $title;
 846         var $titleCache;
 847
 848         /**
 849          * Hashtable listing templates which are disallowed for expansion in this frame,
 850          * having been encountered previously in parent frames.
 851          */
 852         var $loopCheckHash;
 853
 854         /**
 855          * Recursion depth of this frame, top = 0
 856          * Note that this is NOT the same as expansion depth in expand()
 857          */
 858         var $depth;
 859
 860
 861         /**
 862          * Construct a new preprocessor frame.
 863          * @param $preprocessor Preprocessor: the parent preprocessor
 864          */
 865         function __construct( $preprocessor ) {
 866                 $this->preprocessor = $preprocessor;
 867                 $this->parser = $preprocessor->parser;
 868                 $this->title = $this->parser->mTitle;
 869                 $this->titleCache = array( $this->title ? $this->title->getPrefixedDBkey() : false );
 870                 $this->loopCheckHash = array();
 871                 $this->depth = 0;
 872         }
 873
 874         /**
 875          * Create a new child frame
 876          * $args is optionally a multi-root PPNode or array containing the template arguments
 877          */
 878         function newChild( $args = false, $title = false ) {
 879                 $namedArgs = array();
 880                 $numberedArgs = array();
 881                 if ( $title === false ) {
 882                         $title = $this->title;
 883                 }
 884                 if ( $args !== false ) {
 885                         if ( $args instanceof PPNode_Hash_Array ) {
 886                                 $args = $args->value;
 887                         } elseif ( !is_array( $args ) ) {
 888                                 throw new MWException( __METHOD__ . ': $args must be array or PPNode_Hash_Array' );
 889                         }
 890                         foreach ( $args as $arg ) {
 891                                 $bits = $arg->splitArg();
 892                                 if ( $bits['index'] !== '' ) {
 893                                         // Numbered parameter
 894                                         $numberedArgs[$bits['index']] = $bits['value'];
 895                                         unset( $namedArgs[$bits['index']] );
 896                                 } else {
 897                                         // Named parameter
 898                                         $name = trim( $this->expand( $bits['name'], PPFrame::STRIP_COMMENTS ) );
 899                                         $namedArgs[$name] = $bits['value'];
 900                                         unset( $numberedArgs[$name] );
 901                                 }
 902                         }
 903                 }
 904                 return new PPTemplateFrame_Hash( $this->preprocessor, $this, $numberedArgs, $namedArgs, $title );
 905         }
 906
 907         function expand( $root, $flags = 0 ) {
 908                 static $expansionDepth = 0;
 909                 if ( is_string( $root ) ) {
 910                         return $root;
 911                 }
 912
 913                 if ( ++$this->parser->mPPNodeCount > $this->parser->mOptions->getMaxPPNodeCount() ) {
 914                         return '<span class="error">Node-count limit exceeded</span>';
 915                 }
 916                 if ( $expansionDepth > $this->parser->mOptions->getMaxPPExpandDepth() ) {
 917                         return '<span class="error">Expansion depth limit exceeded</span>';
 918                 }
 919                 ++$expansionDepth;
 920
 921                 $outStack = array( '', '' );
 922                 $iteratorStack = array( false, $root );
 923                 $indexStack = array( 0, 0 );
 924
 925                 while ( count( $iteratorStack ) > 1 ) {
 926                         $level = count( $outStack ) - 1;
 927                         $iteratorNode =& $iteratorStack[ $level ];
 928                         $out =& $outStack[$level];
 929                         $index =& $indexStack[$level];
 930
 931                         if ( is_array( $iteratorNode ) ) {
 932                                 if ( $index >= count( $iteratorNode ) ) {
 933                                         // All done with this iterator
 934                                         $iteratorStack[$level] = false;
 935                                         $contextNode = false;
 936                                 } else {
 937                                         $contextNode = $iteratorNode[$index];
 938                                         $index++;
 939                                 }
 940                         } elseif ( $iteratorNode instanceof PPNode_Hash_Array ) {
 941                                 if ( $index >= $iteratorNode->getLength() ) {
 942                                         // All done with this iterator
 943                                         $iteratorStack[$level] = false;
 944                                         $contextNode = false;
 945                                 } else {
 946                                         $contextNode = $iteratorNode->item( $index );
 947                                         $index++;
 948                                 }
 949                         } else {
 950                                 // Copy to $contextNode and then delete from iterator stack,
 951                                 // because this is not an iterator but we do have to execute it once
 952                                 $contextNode = $iteratorStack[$level];
 953                                 $iteratorStack[$level] = false;
 954                         }
 955
 956                         $newIterator = false;
 957
 958                         if ( $contextNode === false ) {
 959                                 // nothing to do
 960                         } elseif ( is_string( $contextNode ) ) {
 961                                 $out .= $contextNode;
 962                         } elseif ( is_array( $contextNode ) || $contextNode instanceof PPNode_Hash_Array ) {
 963                                 $newIterator = $contextNode;
 964                         } elseif ( $contextNode instanceof PPNode_Hash_Attr ) {
 965                                 // No output
 966                         } elseif ( $contextNode instanceof PPNode_Hash_Text ) {
 967                                 $out .= $contextNode->value;
 968                         } elseif ( $contextNode instanceof PPNode_Hash_Tree ) {
 969                                 if ( $contextNode->name == 'template' ) {
 970                                         # Double-brace expansion
 971                                         $bits = $contextNode->splitTemplate();
 972                                         if ( $flags & PPFrame::NO_TEMPLATES ) {
 973                                                 $newIterator = $this->virtualBracketedImplode( '{{', '|', '}}', $bits['title'], $bits['parts'] );
 974                                         } else {
 975                                                 $ret = $this->parser->braceSubstitution( $bits, $this );
 976                                                 if ( isset( $ret['object'] ) ) {
 977                                                         $newIterator = $ret['object'];
 978                                                 } else {
 979                                                         $out .= $ret['text'];
 980                                                 }
 981                                         }
 982                                 } elseif ( $contextNode->name == 'tplarg' ) {
 983                                         # Triple-brace expansion
 984                                         $bits = $contextNode->splitTemplate();
 985                                         if ( $flags & PPFrame::NO_ARGS ) {
 986                                                 $newIterator = $this->virtualBracketedImplode( '{{{', '|', '}}}', $bits['title'], $bits['parts'] );
 987                                         } else {
 988                                                 $ret = $this->parser->argSubstitution( $bits, $this );
 989                                                 if ( isset( $ret['object'] ) ) {
 990                                                         $newIterator = $ret['object'];
 991                                                 } else {
 992                                                         $out .= $ret['text'];
 993                                                 }
 994                                         }
 995                                 } elseif ( $contextNode->name == 'comment' ) {
 996                                         # HTML-style comment
 997                                         # Remove it in HTML, pre+remove and STRIP_COMMENTS modes
 998                                         if ( $this->parser->ot['html']
 999                                                 || ( $this->parser->ot['pre'] && $this->parser->mOptions->getRemoveComments() )
1000                                                 || ( $flags & PPFrame::STRIP_COMMENTS ) )
1001                                         {
1002                                                 $out .= '';
1003                                         }
1004                                         # Add a strip marker in PST mode so that pstPass2() can run some old-fashioned regexes on the result
1005                                         # Not in RECOVER_COMMENTS mode (extractSections) though
1006                                         elseif ( $this->parser->ot['wiki'] && ! ( $flags & PPFrame::RECOVER_COMMENTS ) ) {
1007                                                 $out .= $this->parser->insertStripItem( $contextNode->firstChild->value );
1008                                         }
1009                                         # Recover the literal comment in RECOVER_COMMENTS and pre+no-remove
1010                                         else {
1011                                                 $out .= $contextNode->firstChild->value;
1012                                         }
1013                                 } elseif ( $contextNode->name == 'ignore' ) {
1014                                         # Output suppression used by <includeonly> etc.
1015                                         # OT_WIKI will only respect <ignore> in substed templates.
1016                                         # The other output types respect it unless NO_IGNORE is set.
1017                                         # extractSections() sets NO_IGNORE and so never respects it.
1018                                         if ( ( !isset( $this->parent ) && $this->parser->ot['wiki'] ) || ( $flags & PPFrame::NO_IGNORE ) ) {
1019                                                 $out .= $contextNode->firstChild->value;
1020                                         } else {
1021                                                 //$out .= '';
1022                                         }
1023                                 } elseif ( $contextNode->name == 'ext' ) {
1024                                         # Extension tag
1025                                         $bits = $contextNode->splitExt() + array( 'attr' => null, 'inner' => null, 'close' => null );
1026                                         $out .= $this->parser->extensionSubstitution( $bits, $this );
1027                                 } elseif ( $contextNode->name == 'h' ) {
1028                                         # Heading
1029                                         if ( $this->parser->ot['html'] ) {
1030                                                 # Expand immediately and insert heading index marker
1031                                                 $s = '';
1032                                                 for ( $node = $contextNode->firstChild; $node; $node = $node->nextSibling ) {
1033                                                         $s .= $this->expand( $node, $flags );
1034                                                 }
1035
1036                                                 $bits = $contextNode->splitHeading();
1037                                                 $titleText = $this->title->getPrefixedDBkey();
1038                                                 $this->parser->mHeadings[] = array( $titleText, $bits['i'] );
1039                                                 $serial = count( $this->parser->mHeadings ) - 1;
1040                                                 $marker = "{$this->parser->mUniqPrefix}-h-$serial-" . Parser::MARKER_SUFFIX;
1041                                                 $s = substr( $s, 0, $bits['level'] ) . $marker . substr( $s, $bits['level'] );
1042                                                 $this->parser->mStripState->addGeneral( $marker, '' );
1043                                                 $out .= $s;
1044                                         } else {
1045                                                 # Expand in virtual stack
1046                                                 $newIterator = $contextNode->getChildren();
1047                                         }
1048                                 } else {
1049                                         # Generic recursive expansion
1050                                         $newIterator = $contextNode->getChildren();
1051                                 }
1052                         } else {
1053                                 throw new MWException( __METHOD__.': Invalid parameter type' );
1054                         }
1055
1056                         if ( $newIterator !== false ) {
1057                                 $outStack[] = '';
1058                                 $iteratorStack[] = $newIterator;
1059                                 $indexStack[] = 0;
1060                         } elseif ( $iteratorStack[$level] === false ) {
1061                                 // Return accumulated value to parent
1062                                 // With tail recursion
1063                                 while ( $iteratorStack[$level] === false && $level > 0 ) {
1064                                         $outStack[$level - 1] .= $out;
1065                                         array_pop( $outStack );
1066                                         array_pop( $iteratorStack );
1067                                         array_pop( $indexStack );
1068                                         $level--;
1069                                 }
1070                         }
1071                 }
1072                 --$expansionDepth;
1073                 return $outStack[0];
1074         }
1075
1076         function implodeWithFlags( $sep, $flags /*, ... */ ) {
1077                 $args = array_slice( func_get_args(), 2 );
1078
1079                 $first = true;
1080                 $s = '';
1081                 foreach ( $args as $root ) {
1082                         if ( $root instanceof PPNode_Hash_Array ) {
1083                                 $root = $root->value;
1084                         }
1085                         if ( !is_array( $root ) ) {
1086                                 $root = array( $root );
1087                         }
1088                         foreach ( $root as $node ) {
1089                                 if ( $first ) {
1090                                         $first = false;
1091                                 } else {
1092                                         $s .= $sep;
1093                                 }
1094                                 $s .= $this->expand( $node, $flags );
1095                         }
1096                 }
1097                 return $s;
1098         }
1099
1100         /**
1101          * Implode with no flags specified
1102          * This previously called implodeWithFlags but has now been inlined to reduce stack depth
1103          */
1104         function implode( $sep /*, ... */ ) {
1105                 $args = array_slice( func_get_args(), 1 );
1106
1107                 $first = true;
1108                 $s = '';
1109                 foreach ( $args as $root ) {
1110                         if ( $root instanceof PPNode_Hash_Array ) {
1111                                 $root = $root->value;
1112                         }
1113                         if ( !is_array( $root ) ) {
1114                                 $root = array( $root );
1115                         }
1116                         foreach ( $root as $node ) {
1117                                 if ( $first ) {
1118                                         $first = false;
1119                                 } else {
1120                                         $s .= $sep;
1121                                 }
1122                                 $s .= $this->expand( $node );
1123                         }
1124                 }
1125                 return $s;
1126         }
1127
1128         /**
1129          * Makes an object that, when expand()ed, will be the same as one obtained
1130          * with implode()
1131          */
1132         function virtualImplode( $sep /*, ... */ ) {
1133                 $args = array_slice( func_get_args(), 1 );
1134                 $out = array();
1135                 $first = true;
1136
1137                 foreach ( $args as $root ) {
1138                         if ( $root instanceof PPNode_Hash_Array ) {
1139                                 $root = $root->value;
1140                         }
1141                         if ( !is_array( $root ) ) {
1142                                 $root = array( $root );
1143                         }
1144                         foreach ( $root as $node ) {
1145                                 if ( $first ) {
1146                                         $first = false;
1147                                 } else {
1148                                         $out[] = $sep;
1149                                 }
1150                                 $out[] = $node;
1151                         }
1152                 }
1153                 return new PPNode_Hash_Array( $out );
1154         }
1155
1156         /**
1157          * Virtual implode with brackets
1158          */
1159         function virtualBracketedImplode( $start, $sep, $end /*, ... */ ) {
1160                 $args = array_slice( func_get_args(), 3 );
1161                 $out = array( $start );
1162                 $first = true;
1163
1164                 foreach ( $args as $root ) {
1165                         if ( $root instanceof PPNode_Hash_Array ) {
1166                                 $root = $root->value;
1167                         }
1168                         if ( !is_array( $root ) ) {
1169                                 $root = array( $root );
1170                         }
1171                         foreach ( $root as $node ) {
1172                                 if ( $first ) {
1173                                         $first = false;
1174                                 } else {
1175                                         $out[] = $sep;
1176                                 }
1177                                 $out[] = $node;
1178                         }
1179                 }
1180                 $out[] = $end;
1181                 return new PPNode_Hash_Array( $out );
1182         }
1183
1184         function __toString() {
1185                 return 'frame{}';
1186         }
1187
1188         function getPDBK( $level = false ) {
1189                 if ( $level === false ) {
1190                         return $this->title->getPrefixedDBkey();
1191                 } else {
1192                         return isset( $this->titleCache[$level] ) ? $this->titleCache[$level] : false;
1193                 }
1194         }
1195
1196         function getArguments() {
1197                 return array();
1198         }
1199
1200         function getNumberedArguments() {
1201                 return array();
1202         }
1203
1204         function getNamedArguments() {
1205                 return array();
1206         }
1207
1208         /**
1209          * Returns true if there are no arguments in this frame
1210          */
1211         function isEmpty() {
1212                 return true;
1213         }
1214
1215         function getArgument( $name ) {
1216                 return false;
1217         }
1218
1219         /**
1220          * Returns true if the infinite loop check is OK, false if a loop is detected
1221          *
1222          * @param $title Title
1223          */
1224         function loopCheck( $title ) {
1225                 return !isset( $this->loopCheckHash[$title->getPrefixedDBkey()] );
1226         }
1227
1228         /**
1229          * Return true if the frame is a template frame
1230          */
1231         function isTemplate() {
1232                 return false;
1233         }
1234 }
1235
1236 /**
1237  * Expansion frame with template arguments
1238  * @ingroup Parser
1239  */
1240 class PPTemplateFrame_Hash extends PPFrame_Hash {
1241         var $numberedArgs, $namedArgs, $parent;
1242         var $numberedExpansionCache, $namedExpansionCache;
1243
1244         /**
1245          * @param $preprocessor
1246          * @param $parent
1247          * @param $numberedArgs array
1248          * @param $namedArgs array
1249          * @param $title Title
1250          */
1251         function __construct( $preprocessor, $parent = false, $numberedArgs = array(), $namedArgs = array(), $title = false ) {
1252                 parent::__construct( $preprocessor );
1253
1254                 $this->parent = $parent;
1255                 $this->numberedArgs = $numberedArgs;
1256                 $this->namedArgs = $namedArgs;
1257                 $this->title = $title;
1258                 $pdbk = $title ? $title->getPrefixedDBkey() : false;
1259                 $this->titleCache = $parent->titleCache;
1260                 $this->titleCache[] = $pdbk;
1261                 $this->loopCheckHash = /*clone*/ $parent->loopCheckHash;
1262                 if ( $pdbk !== false ) {
1263                         $this->loopCheckHash[$pdbk] = true;
1264                 }
1265                 $this->depth = $parent->depth + 1;
1266                 $this->numberedExpansionCache = $this->namedExpansionCache = array();
1267         }
1268
1269         function __toString() {
1270                 $s = 'tplframe{';
1271                 $first = true;
1272                 $args = $this->numberedArgs + $this->namedArgs;
1273                 foreach ( $args as $name => $value ) {
1274                         if ( $first ) {
1275                                 $first = false;
1276                         } else {
1277                                 $s .= ', ';
1278                         }
1279                         $s .= "\"$name\":\"" .
1280                                 str_replace( '"', '\\"', $value->__toString() ) . '"';
1281                 }
1282                 $s .= '}';
1283                 return $s;
1284         }
1285         /**
1286          * Returns true if there are no arguments in this frame
1287          *
1288          * @return bool
1289          */
1290         function isEmpty() {
1291                 return !count( $this->numberedArgs ) && !count( $this->namedArgs );
1292         }
1293
1294         /**
1295          * @return array
1296          */
1297         function getArguments() {
1298                 $arguments = array();
1299                 foreach ( array_merge(
1300                                 array_keys($this->numberedArgs),
1301                                 array_keys($this->namedArgs)) as $key ) {
1302                         $arguments[$key] = $this->getArgument($key);
1303                 }
1304                 return $arguments;
1305         }
1306
1307         /**
1308          * @return array
1309          */
1310         function getNumberedArguments() {
1311                 $arguments = array();
1312                 foreach ( array_keys($this->numberedArgs) as $key ) {
1313                         $arguments[$key] = $this->getArgument($key);
1314                 }
1315                 return $arguments;
1316         }
1317
1318         /**
1319          * @return array
1320          */
1321         function getNamedArguments() {
1322                 $arguments = array();
1323                 foreach ( array_keys($this->namedArgs) as $key ) {
1324                         $arguments[$key] = $this->getArgument($key);
1325                 }
1326                 return $arguments;
1327         }
1328
1329         function getNumberedArgument( $index ) {
1330                 if ( !isset( $this->numberedArgs[$index] ) ) {
1331                         return false;
1332                 }
1333                 if ( !isset( $this->numberedExpansionCache[$index] ) ) {
1334                         # No trimming for unnamed arguments
1335                         $this->numberedExpansionCache[$index] = $this->parent->expand( $this->numberedArgs[$index], PPFrame::STRIP_COMMENTS );
1336                 }
1337                 return $this->numberedExpansionCache[$index];
1338         }
1339
1340         function getNamedArgument( $name ) {
1341                 if ( !isset( $this->namedArgs[$name] ) ) {
1342                         return false;
1343                 }
1344                 if ( !isset( $this->namedExpansionCache[$name] ) ) {
1345                         # Trim named arguments post-expand, for backwards compatibility
1346                         $this->namedExpansionCache[$name] = trim(
1347                                 $this->parent->expand( $this->namedArgs[$name], PPFrame::STRIP_COMMENTS ) );
1348                 }
1349                 return $this->namedExpansionCache[$name];
1350         }
1351
1352         function getArgument( $name ) {
1353                 $text = $this->getNumberedArgument( $name );
1354                 if ( $text === false ) {
1355                         $text = $this->getNamedArgument( $name );
1356                 }
1357                 return $text;
1358         }
1359
1360         /**
1361          * Return true if the frame is a template frame
1362          */
1363         function isTemplate() {
1364                 return true;
1365         }
1366 }
1367
1368 /**
1369  * Expansion frame with custom arguments
1370  * @ingroup Parser
1371  */
1372 class PPCustomFrame_Hash extends PPFrame_Hash {
1373         var $args;
1374
1375         function __construct( $preprocessor, $args ) {
1376                 parent::__construct( $preprocessor );
1377                 $this->args = $args;
1378         }
1379
1380         function __toString() {
1381                 $s = 'cstmframe{';
1382                 $first = true;
1383                 foreach ( $this->args as $name => $value ) {
1384                         if ( $first ) {
1385                                 $first = false;
1386                         } else {
1387                                 $s .= ', ';
1388                         }
1389                         $s .= "\"$name\":\"" .
1390                                 str_replace( '"', '\\"', $value->__toString() ) . '"';
1391                 }
1392                 $s .= '}';
1393                 return $s;
1394         }
1395
1396         function isEmpty() {
1397                 return !count( $this->args );
1398         }
1399
1400         function getArgument( $index ) {
1401                 if ( !isset( $this->args[$index] ) ) {
1402                         return false;
1403                 }
1404                 return $this->args[$index];
1405         }
1406 }
1407
1408 /**
1409  * @ingroup Parser
1410  */
1411 class PPNode_Hash_Tree implements PPNode {
1412         var $name, $firstChild, $lastChild, $nextSibling;
1413
1414         function __construct( $name ) {
1415                 $this->name = $name;
1416                 $this->firstChild = $this->lastChild = $this->nextSibling = false;
1417         }
1418
1419         function __toString() {
1420                 $inner = '';
1421                 $attribs = '';
1422                 for ( $node = $this->firstChild; $node; $node = $node->nextSibling ) {
1423                         if ( $node instanceof PPNode_Hash_Attr ) {
1424                                 $attribs .= ' ' . $node->name . '="' . htmlspecialchars( $node->value ) . '"';
1425                         } else {
1426                                 $inner .= $node->__toString();
1427                         }
1428                 }
1429                 if ( $inner === '' ) {
1430                         return "<{$this->name}$attribs/>";
1431                 } else {
1432                         return "<{$this->name}$attribs>$inner</{$this->name}>";
1433                 }
1434         }
1435
1436         static function newWithText( $name, $text ) {
1437                 $obj = new self( $name );
1438                 $obj->addChild( new PPNode_Hash_Text( $text ) );
1439                 return $obj;
1440         }
1441
1442         function addChild( $node ) {
1443                 if ( $this->lastChild === false ) {
1444                         $this->firstChild = $this->lastChild = $node;
1445                 } else {
1446                         $this->lastChild->nextSibling = $node;
1447                         $this->lastChild = $node;
1448                 }
1449         }
1450
1451         function getChildren() {
1452                 $children = array();
1453                 for ( $child = $this->firstChild; $child; $child = $child->nextSibling ) {
1454                         $children[] = $child;
1455                 }
1456                 return new PPNode_Hash_Array( $children );
1457         }
1458
1459         function getFirstChild() {
1460                 return $this->firstChild;
1461         }
1462
1463         function getNextSibling() {
1464                 return $this->nextSibling;
1465         }
1466
1467         function getChildrenOfType( $name ) {
1468                 $children = array();
1469                 for ( $child = $this->firstChild; $child; $child = $child->nextSibling ) {
1470                         if ( isset( $child->name ) && $child->name === $name ) {
1471                                 $children[] = $name;
1472                         }
1473                 }
1474                 return $children;
1475         }
1476
1477         function getLength() { return false; }
1478         function item( $i ) { return false; }
1479
1480         function getName() {
1481                 return $this->name;
1482         }
1483
1484         /**
1485          * Split a <part> node into an associative array containing:
1486          *    name          PPNode name
1487          *    index         String index
1488          *    value         PPNode value
1489          */
1490         function splitArg() {
1491                 $bits = array();
1492                 for ( $child = $this->firstChild; $child; $child = $child->nextSibling ) {
1493                         if ( !isset( $child->name ) ) {
1494                                 continue;
1495                         }
1496                         if ( $child->name === 'name' ) {
1497                                 $bits['name'] = $child;
1498                                 if ( $child->firstChild instanceof PPNode_Hash_Attr
1499                                         && $child->firstChild->name === 'index' )
1500                                 {
1501                                         $bits['index'] = $child->firstChild->value;
1502                                 }
1503                         } elseif ( $child->name === 'value' ) {
1504                                 $bits['value'] = $child;
1505                         }
1506                 }
1507
1508                 if ( !isset( $bits['name'] ) ) {
1509                         throw new MWException( 'Invalid brace node passed to ' . __METHOD__ );
1510                 }
1511                 if ( !isset( $bits['index'] ) ) {
1512                         $bits['index'] = '';
1513                 }
1514                 return $bits;
1515         }
1516
1517         /**
1518          * Split an <ext> node into an associative array containing name, attr, inner and close
1519          * All values in the resulting array are PPNodes. Inner and close are optional.
1520          */
1521         function splitExt() {
1522                 $bits = array();
1523                 for ( $child = $this->firstChild; $child; $child = $child->nextSibling ) {
1524                         if ( !isset( $child->name ) ) {
1525                                 continue;
1526                         }
1527                         if ( $child->name == 'name' ) {
1528                                 $bits['name'] = $child;
1529                         } elseif ( $child->name == 'attr' ) {
1530                                 $bits['attr'] = $child;
1531                         } elseif ( $child->name == 'inner' ) {
1532                                 $bits['inner'] = $child;
1533                         } elseif ( $child->name == 'close' ) {
1534                                 $bits['close'] = $child;
1535                         }
1536                 }
1537                 if ( !isset( $bits['name'] ) ) {
1538                         throw new MWException( 'Invalid ext node passed to ' . __METHOD__ );
1539                 }
1540                 return $bits;
1541         }
1542
1543         /**
1544          * Split an <h> node
1545          */
1546         function splitHeading() {
1547                 if ( $this->name !== 'h' ) {
1548                         throw new MWException( 'Invalid h node passed to ' . __METHOD__ );
1549                 }
1550                 $bits = array();
1551                 for ( $child = $this->firstChild; $child; $child = $child->nextSibling ) {
1552                         if ( !isset( $child->name ) ) {
1553                                 continue;
1554                         }
1555                         if ( $child->name == 'i' ) {
1556                                 $bits['i'] = $child->value;
1557                         } elseif ( $child->name == 'level' ) {
1558                                 $bits['level'] = $child->value;
1559                         }
1560                 }
1561                 if ( !isset( $bits['i'] ) ) {
1562                         throw new MWException( 'Invalid h node passed to ' . __METHOD__ );
1563                 }
1564                 return $bits;
1565         }
1566
1567         /**
1568          * Split a <template> or <tplarg> node
1569          */
1570         function splitTemplate() {
1571                 $parts = array();
1572                 $bits = array( 'lineStart' => '' );
1573                 for ( $child = $this->firstChild; $child; $child = $child->nextSibling ) {
1574                         if ( !isset( $child->name ) ) {
1575                                 continue;
1576                         }
1577                         if ( $child->name == 'title' ) {
1578                                 $bits['title'] = $child;
1579                         }
1580                         if ( $child->name == 'part' ) {
1581                                 $parts[] = $child;
1582                         }
1583                         if ( $child->name == 'lineStart' ) {
1584                                 $bits['lineStart'] = '1';
1585                         }
1586                 }
1587                 if ( !isset( $bits['title'] ) ) {
1588                         throw new MWException( 'Invalid node passed to ' . __METHOD__ );
1589                 }
1590                 $bits['parts'] = new PPNode_Hash_Array( $parts );
1591                 return $bits;
1592         }
1593 }
1594
1595 /**
1596  * @ingroup Parser
1597  */
1598 class PPNode_Hash_Text implements PPNode {
1599         var $value, $nextSibling;
1600
1601         function __construct( $value ) {
1602                 if ( is_object( $value ) ) {
1603                         throw new MWException( __CLASS__ . ' given object instead of string' );
1604                 }
1605                 $this->value = $value;
1606         }
1607
1608         function __toString() {
1609                 return htmlspecialchars( $this->value );
1610         }
1611
1612         function getNextSibling() {
1613                 return $this->nextSibling;
1614         }
1615
1616         function getChildren() { return false; }
1617         function getFirstChild() { return false; }
1618         function getChildrenOfType( $name ) { return false; }
1619         function getLength() { return false; }
1620         function item( $i ) { return false; }
1621         function getName() { return '#text'; }
1622         function splitArg() { throw new MWException( __METHOD__ . ': not supported' ); }
1623         function splitExt() { throw new MWException( __METHOD__ . ': not supported' ); }
1624         function splitHeading() { throw new MWException( __METHOD__ . ': not supported' ); }
1625 }
1626
1627 /**
1628  * @ingroup Parser
1629  */
1630 class PPNode_Hash_Array implements PPNode {
1631         var $value, $nextSibling;
1632
1633         function __construct( $value ) {
1634                 $this->value = $value;
1635         }
1636
1637         function __toString() {
1638                 return var_export( $this, true );
1639         }
1640
1641         function getLength() {
1642                 return count( $this->value );
1643         }
1644
1645         function item( $i ) {
1646                 return $this->value[$i];
1647         }
1648
1649         function getName() { return '#nodelist'; }
1650
1651         function getNextSibling() {
1652                 return $this->nextSibling;
1653         }
1654
1655         function getChildren() { return false; }
1656         function getFirstChild() { return false; }
1657         function getChildrenOfType( $name ) { return false; }
1658         function splitArg() { throw new MWException( __METHOD__ . ': not supported' ); }
1659         function splitExt() { throw new MWException( __METHOD__ . ': not supported' ); }
1660         function splitHeading() { throw new MWException( __METHOD__ . ': not supported' ); }
1661 }
1662
1663 /**
1664  * @ingroup Parser
1665  */
1666 class PPNode_Hash_Attr implements PPNode {
1667         var $name, $value, $nextSibling;
1668
1669         function __construct( $name, $value ) {
1670                 $this->name = $name;
1671                 $this->value = $value;
1672         }
1673
1674         function __toString() {
1675                 return "<@{$this->name}>" . htmlspecialchars( $this->value ) . "</@{$this->name}>";
1676         }
1677
1678         function getName() {
1679                 return $this->name;
1680         }
1681
1682         function getNextSibling() {
1683                 return $this->nextSibling;
1684         }
1685
1686         function getChildren() { return false; }
1687         function getFirstChild() { return false; }
1688         function getChildrenOfType( $name ) { return false; }
1689         function getLength() { return false; }
1690         function item( $i ) { return false; }
1691         function splitArg() { throw new MWException( __METHOD__ . ': not supported' ); }
1692         function splitExt() { throw new MWException( __METHOD__ . ': not supported' ); }
1693         function splitHeading() { throw new MWException( __METHOD__ . ': not supported' ); }
1694 }