3 * An implementation of the tree building portion of the HTML5 parsing
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; if not, write to the Free Software Foundation, Inc.,
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 * http://www.gnu.org/copyleft/gpl.html
24 * @author C. Scott Ananian, 2016
26 namespace MediaWiki\Tidy
;
28 use Wikimedia\Assert\Assert
;
29 use Wikimedia\Assert\ParameterAssertionException
;
31 use \IteratorAggregate
;
32 use \ReverseArrayIterator
;
35 # A note for future librarization[1] -- this file is a good candidate
36 # for splitting into an independent library, except that it is currently
37 # highly optimized for MediaWiki use. It only implements the portions
38 # of the HTML5 tree builder used by tags supported by MediaWiki, and
39 # does not contain a true tokenizer pass, instead relying on
40 # comment stripping, attribute normalization, and escaping done by
41 # the MediaWiki Sanitizer. It also deliberately avoids building
42 # a true DOM in memory, instead serializing elements to an output string
43 # as soon as possible (usually as soon as the tag is closed) to reduce
44 # its memory footprint.
46 # We've been gradually lifting some of these restrictions to handle
47 # non-sanitized output generated by extensions, but we shortcut the tokenizer
48 # for speed (primarily by splitting on `<`) and so rely on syntactic
51 # On the other hand, I've been pretty careful to note with comments in the
52 # code the places where this implementation omits features of the spec or
53 # depends on the MediaWiki Sanitizer. Perhaps in the future we'll want to
54 # implement the missing pieces and make this a standalone PHP HTML5 parser.
55 # In order to do so, some sort of MediaWiki-specific API will need
56 # to be added to (a) allow the Balancer to bypass the tokenizer,
57 # and (b) support on-the-fly flattening instead of DOM node creation.
59 # [1]: https://www.mediawiki.org/wiki/Library_infrastructure_for_MediaWiki
62 * Utility constants and sets for the HTML5 tree building algorithm.
63 * Sets are associative arrays indexed first by namespace and then by
64 * lower-cased tag name.
70 const HTML_NAMESPACE
= 'http://www.w3.org/1999/xhtml';
71 const MATHML_NAMESPACE
= 'http://www.w3.org/1998/Math/MathML';
72 const SVG_NAMESPACE
= 'http://www.w3.org/2000/svg';
74 public static $unsupportedSet = [
75 self
::HTML_NAMESPACE
=> [
76 'html' => true, 'head' => true, 'body' => true, 'frameset' => true,
78 'plaintext' => true, 'isindex' => true, 'textarea' => true,
79 'xmp' => true, 'iframe' => true, 'noembed' => true,
80 'noscript' => true, 'script' => true,
85 public static $emptyElementSet = [
86 self
::HTML_NAMESPACE
=> [
87 'area' => true, 'base' => true, 'basefont' => true,
88 'bgsound' => true, 'br' => true, 'col' => true, 'command' => true,
89 'embed' => true, 'frame' => true, 'hr' => true, 'img' => true,
90 'input' => true, 'keygen' => true, 'link' => true, 'meta' => true,
91 'param' => true, 'source' => true, 'track' => true, 'wbr' => true
95 public static $headingSet = [
96 self
::HTML_NAMESPACE
=> [
97 'h1' => true, 'h2' => true, 'h3' => true,
98 'h4' => true, 'h5' => true, 'h6' => true
102 public static $specialSet = [
103 self
::HTML_NAMESPACE
=> [
104 'address' => true, 'applet' => true, 'area' => true,
105 'article' => true, 'aside' => true, 'base' => true,
106 'basefont' => true, 'bgsound' => true, 'blockquote' => true,
107 'body' => true, 'br' => true, 'button' => true, 'caption' => true,
108 'center' => true, 'col' => true, 'colgroup' => true, 'dd' => true,
109 'details' => true, 'dir' => true, 'div' => true, 'dl' => true,
110 'dt' => true, 'embed' => true, 'fieldset' => true,
111 'figcaption' => true, 'figure' => true, 'footer' => true,
112 'form' => true, 'frame' => true, 'frameset' => true, 'h1' => true,
113 'h2' => true, 'h3' => true, 'h4' => true, 'h5' => true,
114 'h6' => true, 'head' => true, 'header' => true, 'hgroup' => true,
115 'hr' => true, 'html' => true, 'iframe' => true, 'img' => true,
116 'input' => true, 'isindex' => true, 'li' => true, 'link' => true,
117 'listing' => true, 'main' => true, 'marquee' => true,
118 'menu' => true, 'menuitem' => true, 'meta' => true, 'nav' => true,
119 'noembed' => true, 'noframes' => true, 'noscript' => true,
120 'object' => true, 'ol' => true, 'p' => true, 'param' => true,
121 'plaintext' => true, 'pre' => true, 'script' => true,
122 'section' => true, 'select' => true, 'source' => true,
123 'style' => true, 'summary' => true, 'table' => true,
124 'tbody' => true, 'td' => true, 'template' => true,
125 'textarea' => true, 'tfoot' => true, 'th' => true, 'thead' => true,
126 'title' => true, 'tr' => true, 'track' => true, 'ul' => true,
127 'wbr' => true, 'xmp' => true
129 self
::SVG_NAMESPACE
=> [
130 'foreignobject' => true, 'desc' => true, 'title' => true
132 self
::MATHML_NAMESPACE
=> [
133 'mi' => true, 'mo' => true, 'mn' => true, 'ms' => true,
134 'mtext' => true, 'annotation-xml' => true
138 public static $addressDivPSet = [
139 self
::HTML_NAMESPACE
=> [
140 'address' => true, 'div' => true, 'p' => true
144 public static $tableSectionRowSet = [
145 self
::HTML_NAMESPACE
=> [
146 'table' => true, 'thead' => true, 'tbody' => true,
147 'tfoot' => true, 'tr' => true
151 public static $impliedEndTagsSet = [
152 self
::HTML_NAMESPACE
=> [
153 'dd' => true, 'dt' => true, 'li' => true, 'optgroup' => true,
154 'option' => true, 'p' => true, 'rb' => true, 'rp' => true,
155 'rt' => true, 'rtc' => true
159 public static $thoroughImpliedEndTagsSet = [
160 self
::HTML_NAMESPACE
=> [
161 'caption' => true, 'colgroup' => true, 'dd' => true, 'dt' => true,
162 'li' => true, 'optgroup' => true, 'option' => true, 'p' => true,
163 'rb' => true, 'rp' => true, 'rt' => true, 'rtc' => true,
164 'tbody' => true, 'td' => true, 'tfoot' => true, 'th' => true,
165 'thead' => true, 'tr' => true
169 public static $tableCellSet = [
170 self
::HTML_NAMESPACE
=> [
171 'td' => true, 'th' => true
174 public static $tableContextSet = [
175 self
::HTML_NAMESPACE
=> [
176 'table' => true, 'template' => true, 'html' => true
180 public static $tableBodyContextSet = [
181 self
::HTML_NAMESPACE
=> [
182 'tbody' => true, 'tfoot' => true, 'thead' => true,
183 'template' => true, 'html' => true
187 public static $tableRowContextSet = [
188 self
::HTML_NAMESPACE
=> [
189 'tr' => true, 'template' => true, 'html' => true
193 // See https://html.spec.whatwg.org/multipage/forms.html#form-associated-element
194 public static $formAssociatedSet = [
195 self
::HTML_NAMESPACE
=> [
196 'button' => true, 'fieldset' => true, 'input' => true,
197 'keygen' => true, 'object' => true, 'output' => true,
198 'select' => true, 'textarea' => true, 'img' => true
202 public static $inScopeSet = [
203 self
::HTML_NAMESPACE
=> [
204 'applet' => true, 'caption' => true, 'html' => true,
205 'marquee' => true, 'object' => true,
206 'table' => true, 'td' => true, 'template' => true,
209 self
::SVG_NAMESPACE
=> [
210 'foreignobject' => true, 'desc' => true, 'title' => true
212 self
::MATHML_NAMESPACE
=> [
213 'mi' => true, 'mo' => true, 'mn' => true, 'ms' => true,
214 'mtext' => true, 'annotation-xml' => true
218 private static $inListItemScopeSet = null;
219 public static function inListItemScopeSet() {
220 if ( self
::$inListItemScopeSet === null ) {
221 self
::$inListItemScopeSet = self
::$inScopeSet;
222 self
::$inListItemScopeSet[self
::HTML_NAMESPACE
]['ol'] = true;
223 self
::$inListItemScopeSet[self
::HTML_NAMESPACE
]['ul'] = true;
225 return self
::$inListItemScopeSet;
228 private static $inButtonScopeSet = null;
229 public static function inButtonScopeSet() {
230 if ( self
::$inButtonScopeSet === null ) {
231 self
::$inButtonScopeSet = self
::$inScopeSet;
232 self
::$inButtonScopeSet[self
::HTML_NAMESPACE
]['button'] = true;
234 return self
::$inButtonScopeSet;
237 public static $inTableScopeSet = [
238 self
::HTML_NAMESPACE
=> [
239 'html' => true, 'table' => true, 'template' => true
243 public static $inInvertedSelectScopeSet = [
244 self
::HTML_NAMESPACE
=> [
245 'option' => true, 'optgroup' => true
249 public static $mathmlTextIntegrationPointSet = [
250 self
::MATHML_NAMESPACE
=> [
251 'mi' => true, 'mo' => true, 'mn' => true, 'ms' => true,
256 public static $htmlIntegrationPointSet = [
257 self
::SVG_NAMESPACE
=> [
258 'foreignobject' => true,
264 // For tidy compatibility.
265 public static $tidyPWrapSet = [
266 self
::HTML_NAMESPACE
=> [
267 'body' => true, 'blockquote' => true,
268 // We parse with <body> as the fragment context, but the top-level
269 // element on the stack is actually <html>. We could use the
270 // "adjusted current node" everywhere to work around this, but it's
271 // easier just to add <html> to the p-wrap set.
275 public static $tidyInlineSet = [
276 self
::HTML_NAMESPACE
=> [
277 'a' => true, 'abbr' => true, 'acronym' => true, 'applet' => true,
278 'b' => true, 'basefont' => true, 'bdo' => true, 'big' => true,
279 'br' => true, 'button' => true, 'cite' => true, 'code' => true,
280 'dfn' => true, 'em' => true, 'font' => true, 'i' => true,
281 'iframe' => true, 'img' => true, 'input' => true, 'kbd' => true,
282 'label' => true, 'legend' => true, 'map' => true, 'object' => true,
283 'param' => true, 'q' => true, 'rb' => true, 'rbc' => true,
284 'rp' => true, 'rt' => true, 'rtc' => true, 'ruby' => true,
285 's' => true, 'samp' => true, 'select' => true, 'small' => true,
286 'span' => true, 'strike' => true, 'strong' => true, 'sub' => true,
287 'sup' => true, 'textarea' => true, 'tt' => true, 'u' => true,
294 * A BalanceElement is a simplified version of a DOM Node. The main
295 * difference is that we only keep BalanceElements around for nodes
296 * currently on the BalanceStack of open elements. As soon as an
297 * element is closed, with some minor exceptions relating to the
298 * tree builder "adoption agency algorithm", the element and all its
299 * children are serialized to a string using the flatten() method.
300 * This keeps our memory usage low.
305 class BalanceElement
{
307 * The namespace of the element.
308 * @var string $namespaceURI
310 public $namespaceURI;
312 * The lower-cased name of the element.
313 * @var string $localName
317 * Attributes for the element, in array form
318 * @var array $attribs
323 * Parent of this element, or the string "flat" if this element has
324 * already been flattened into its parent.
325 * @var string|null $parent
330 * An array of children of this element. Typically only the last
331 * child will be an actual BalanceElement object; the rest will
332 * be strings, representing either text nodes or flattened
333 * BalanceElement objects.
334 * @var array $children
339 * A unique string identifier for Noah's Ark purposes, lazy initialized
344 * The next active formatting element in the list, or null if this is the
345 * end of the AFE list or if the element is not in the AFE list.
350 * The previous active formatting element in the list, or null if this is
351 * the start of the list or if the element is not in the AFE list.
356 * The next element in the Noah's Ark species bucket.
361 * Make a new BalanceElement corresponding to the HTML DOM Element
362 * with the given localname, namespace, and attributes.
364 * @param string $namespaceURI The namespace of the element.
365 * @param string $localName The lowercased name of the tag.
366 * @param array $attribs Attributes of the element
368 public function __construct( $namespaceURI, $localName, array $attribs ) {
369 $this->localName
= $localName;
370 $this->namespaceURI
= $namespaceURI;
371 $this->attribs
= $attribs;
372 $this->contents
= '';
373 $this->parent
= null;
374 $this->children
= [];
378 * Remove the given child from this element.
379 * @param BalanceElement $elt
381 private function removeChild( BalanceElement
$elt ) {
382 Assert
::precondition(
383 $this->parent
!== 'flat', "Can't removeChild after flattening $this"
386 $elt->parent
=== $this, 'elt', 'must have $this as a parent'
388 $idx = array_search( $elt, $this->children
, true );
389 Assert
::parameter( $idx !== false, '$elt', 'must be a child of $this' );
391 array_splice( $this->children
, $idx, 1 );
395 * Find $a in the list of children and insert $b before it.
396 * @param BalanceElement $a
397 * @param BalanceElement|string $b
399 public function insertBefore( BalanceElement
$a, $b ) {
400 Assert
::precondition(
401 $this->parent
!== 'flat', "Can't insertBefore after flattening."
403 $idx = array_search( $a, $this->children
, true );
404 Assert
::parameter( $idx !== false, '$a', 'must be a child of $this' );
405 if ( is_string( $b ) ) {
406 array_splice( $this->children
, $idx, 0, [ $b ] );
408 Assert
::parameter( $b->parent
!== 'flat', '$b', "Can't be flat" );
409 if ( $b->parent
!== null ) {
410 $b->parent
->removeChild( $b );
412 array_splice( $this->children
, $idx, 0, [ $b ] );
418 * Append $elt to the end of the list of children.
419 * @param BalanceElement|string $elt
421 public function appendChild( $elt ) {
422 Assert
::precondition(
423 $this->parent
!== 'flat', "Can't appendChild after flattening."
425 if ( is_string( $elt ) ) {
426 array_push( $this->children
, $elt );
429 // Remove $elt from parent, if it had one.
430 if ( $elt->parent
!== null ) {
431 $elt->parent
->removeChild( $elt );
433 array_push( $this->children
, $elt );
434 $elt->parent
= $this;
438 * Transfer all of the children of $elt to $this.
439 * @param BalanceElement $elt
441 public function adoptChildren( BalanceElement
$elt ) {
442 Assert
::precondition(
443 $elt->parent
!== 'flat', "Can't adoptChildren after flattening."
445 foreach ( $elt->children
as $child ) {
446 if ( !is_string( $child ) ) {
447 // This is an optimization which avoids an O(n^2) set of
448 // array_splice operations.
449 $child->parent
= null;
451 $this->appendChild( $child );
457 * Flatten this node and all of its children into a string, as specified
458 * by the HTML serialization specification, and replace this node
459 * in its parent by that string.
463 public function flatten( $tidyCompat = false ) {
464 Assert
::parameter( $this->parent
!== null, '$this', 'must be a child' );
465 Assert
::parameter( $this->parent
!== 'flat', '$this', 'already flat' );
466 $idx = array_search( $this, $this->parent
->children
, true );
468 $idx !== false, '$this', 'must be a child of its parent'
472 foreach ( $this->children
as $elt ) {
473 if ( !is_string( $elt ) ) {
474 $elt = $elt->flatten( $tidyCompat );
476 if ( $blank && preg_match( '/[^\t\n\f\r ]/', $elt ) ) {
480 if ( $this->isHtmlNamed( 'mw:p-wrap' ) ) {
481 $this->localName
= 'p';
482 } elseif ( $blank ) {
483 // Add 'mw-empty-elt' class so elements can be hidden via CSS
484 // for compatibility with legacy tidy.
485 if ( !count( $this->attribs
) &&
486 ( $this->localName
=== 'tr' ||
$this->localName
=== 'li' )
488 $this->attribs
= [ 'class' => "mw-empty-elt" ];
492 $flat = $blank ?
'' : "{$this}";
496 $this->parent
->children
[$idx] = $flat;
497 $this->parent
= 'flat'; # for assertion checking
502 * Serialize this node and all of its children to a string, as specified
503 * by the HTML serialization specification.
505 * @return string The serialization of the BalanceElement
506 * @see https://html.spec.whatwg.org/multipage/syntax.html#serialising-html-fragments
508 public function __toString() {
510 foreach ( $this->attribs
as $name => $value ) {
511 $encValue = Sanitizer
::encodeAttribute( $value );
512 $encAttribs .= " $name=\"$encValue\"";
514 if ( !$this->isA( BalanceSets
::$emptyElementSet ) ) {
515 $out = "<{$this->localName}{$encAttribs}>";
517 foreach ( $this->children
as $elt ) {
520 $out .= "</{$this->localName}>";
522 $out = "<{$this->localName}{$encAttribs} />";
524 count( $this->children
) === 0,
525 "Empty elements shouldn't have children."
531 # Utility functions on BalanceElements.
534 * Determine if $this represents a specific HTML tag, is a member of
535 * a tag set, or is equal to another BalanceElement.
537 * @param BalanceElement|array|string $set The target BalanceElement,
538 * set (from the BalanceSets class), or string (HTML tag name).
541 public function isA( $set ) {
542 if ( $set instanceof BalanceElement
) {
543 return $this === $set;
544 } elseif ( is_array( $set ) ) {
545 return isset( $set[$this->namespaceURI
] ) &&
546 isset( $set[$this->namespaceURI
][$this->localName
] );
548 # assume this is an HTML element name.
549 return $this->isHtml() && $this->localName
=== $set;
554 * Determine if this element is an HTML element with the specified name
555 * @param string $tagName
558 public function isHtmlNamed( $tagName ) {
559 return $this->namespaceURI
=== BalanceSets
::HTML_NAMESPACE
560 && $this->localName
=== $tagName;
564 * Determine if $this represents an element in the HTML namespace.
568 public function isHtml() {
569 return $this->namespaceURI
=== BalanceSets
::HTML_NAMESPACE
;
573 * Determine if $this represents a MathML text integration point,
574 * as defined in the HTML5 specification.
577 * @see https://html.spec.whatwg.org/multipage/syntax.html#mathml-text-integration-point
579 public function isMathmlTextIntegrationPoint() {
580 return $this->isA( BalanceSets
::$mathmlTextIntegrationPointSet );
584 * Determine if $this represents an HTML integration point,
585 * as defined in the HTML5 specification.
588 * @see https://html.spec.whatwg.org/multipage/syntax.html#html-integration-point
590 public function isHtmlIntegrationPoint() {
591 if ( $this->isA( BalanceSets
::$htmlIntegrationPointSet ) ) {
595 $this->namespaceURI
=== BalanceSets
::MATHML_NAMESPACE
&&
596 $this->localName
=== 'annotation-xml' &&
597 isset( $this->attribs
['encoding'] ) &&
598 ( strcasecmp( $this->attribs
['encoding'], 'text/html' ) == 0 ||
599 strcasecmp( $this->attribs
['encoding'], 'application/xhtml+xml' ) == 0 )
607 * Get a string key for the Noah's Ark algorithm
609 public function getNoahKey() {
610 if ( $this->noahKey
=== null ) {
611 $attribs = $this->attribs
;
613 $this->noahKey
= serialize( [ $this->namespaceURI
, $this->localName
, $attribs ] );
615 return $this->noahKey
;
620 * The "stack of open elements" as defined in the HTML5 tree builder
621 * spec. This contains methods to ensure that content (start tags, text)
622 * are inserted at the correct place in the output string, and to
623 * flatten BalanceElements are they are closed to avoid holding onto
624 * a complete DOM tree for the document in memory.
626 * The stack defines a PHP iterator to traverse it in "reverse order",
627 * that is, the most-recently-added element is visited first in a
632 * @see https://html.spec.whatwg.org/multipage/syntax.html#the-stack-of-open-elements
634 class BalanceStack
implements IteratorAggregate
{
636 * Backing storage for the stack.
637 * @var array $elements
639 private $elements = [];
641 * Foster parent mode determines how nodes are inserted into the
643 * @var bool $fosterParentMode
644 * @see https://html.spec.whatwg.org/multipage/syntax.html#foster-parent
646 public $fosterParentMode = false;
648 * Tidy compatibility mode, determines behavior of body/blockquote
650 public $tidyCompat = false;
652 * Reference to the current element
657 * Create a new BalanceStack with a single BalanceElement on it,
658 * representing the root <html> node.
660 public function __construct() {
661 # always a root <html> element on the stack
664 new BalanceElement( BalanceSets
::HTML_NAMESPACE
, 'html', [] )
666 $this->currentNode
= $this->elements
[0];
670 * Return a string representing the output of the tree builder:
671 * all the children of the root <html> node.
674 public function getOutput() {
675 // Don't include the outer '<html>....</html>'
677 foreach ( $this->elements
[0]->children
as $elt ) {
678 $out .= is_string( $elt ) ?
$elt :
679 $elt->flatten( $this->tidyCompat
);
685 * Insert a comment at the appropriate place for inserting a node.
686 * @param string $value Content of the comment.
687 * @see https://html.spec.whatwg.org/multipage/syntax.html#insert-a-comment
689 public function insertComment( $value ) {
690 // Just another type of text node, except for tidy p-wrapping.
691 return $this->insertText( '<!--' . $value . '-->', true );
695 * Insert text at the appropriate place for inserting a node.
696 * @param string $value
697 * @see https://html.spec.whatwg.org/multipage/syntax.html#appropriate-place-for-inserting-a-node
699 public function insertText( $value, $isComment = false ) {
701 $this->fosterParentMode
&&
702 $this->currentNode
->isA( BalanceSets
::$tableSectionRowSet )
704 $this->fosterParent( $value );
706 $this->tidyCompat
&& !$isComment &&
707 $this->currentNode
->isA( BalanceSets
::$tidyPWrapSet )
709 $this->insertHTMLELement( 'mw:p-wrap', [] );
710 return $this->insertText( $value );
712 $this->currentNode
->appendChild( $value );
717 * Insert a BalanceElement at the appropriate place, pushing it
718 * on to the open elements stack.
719 * @param string $namespaceURI The element namespace
720 * @param string $tag The tag name
721 * @param string $attribs Normalized attributes, as a string.
722 * @return BalanceElement
723 * @see https://html.spec.whatwg.org/multipage/syntax.html#insert-a-foreign-element
725 public function insertForeignElement( $namespaceURI, $tag, $attribs ) {
726 return $this->insertElement(
727 new BalanceElement( $namespaceURI, $tag, $attribs )
732 * Insert an HTML element at the appropriate place, pushing it on to
733 * the open elements stack.
734 * @param string $tag The tag name
735 * @param string $attribs Normalized attributes, as a string.
736 * @return BalanceElement
737 * @see https://html.spec.whatwg.org/multipage/syntax.html#insert-an-html-element
739 public function insertHTMLElement( $tag, $attribs ) {
740 return $this->insertForeignElement(
741 BalanceSets
::HTML_NAMESPACE
, $tag, $attribs
746 * Insert an element at the appropriate place and push it on to the
747 * open elements stack.
748 * @param BalanceElement $elt
749 * @return BalanceElement
750 * @see https://html.spec.whatwg.org/multipage/syntax.html#appropriate-place-for-inserting-a-node
752 public function insertElement( BalanceElement
$elt ) {
754 $this->currentNode
->isHtmlNamed( 'mw:p-wrap' ) &&
755 !$elt->isA( BalanceSets
::$tidyInlineSet )
757 // Tidy compatibility.
761 $this->fosterParentMode
&&
762 $this->currentNode
->isA( BalanceSets
::$tableSectionRowSet )
764 $elt = $this->fosterParent( $elt );
766 $this->currentNode
->appendChild( $elt );
768 Assert
::invariant( $elt->parent
!== null, "$elt must be in tree" );
769 Assert
::invariant( $elt->parent
!== 'flat', "$elt must not have been previous flattened" );
770 array_push( $this->elements
, $elt );
771 $this->currentNode
= $elt;
776 * Determine if the stack has $tag in scope.
777 * @param BalanceElement|array|string $tag
779 * @see https://html.spec.whatwg.org/multipage/syntax.html#has-an-element-in-scope
781 public function inScope( $tag ) {
782 return $this->inSpecificScope( $tag, BalanceSets
::$inScopeSet );
786 * Determine if the stack has $tag in button scope.
787 * @param BalanceElement|array|string $tag
789 * @see https://html.spec.whatwg.org/multipage/syntax.html#has-an-element-in-button-scope
791 public function inButtonScope( $tag ) {
792 return $this->inSpecificScope( $tag, BalanceSets
::inButtonScopeSet() );
796 * Determine if the stack has $tag in list item scope.
797 * @param BalanceElement|array|string $tag
799 * @see https://html.spec.whatwg.org/multipage/syntax.html#has-an-element-in-list-item-scope
801 public function inListItemScope( $tag ) {
802 return $this->inSpecificScope( $tag, BalanceSets
::inListItemScopeSet() );
806 * Determine if the stack has $tag in table scope.
807 * @param BalanceElement|array|string $tag
809 * @see https://html.spec.whatwg.org/multipage/syntax.html#has-an-element-in-table-scope
811 public function inTableScope( $tag ) {
812 return $this->inSpecificScope( $tag, BalanceSets
::$inTableScopeSet );
816 * Determine if the stack has $tag in select scope.
817 * @param BalanceElement|array|string $tag
819 * @see https://html.spec.whatwg.org/multipage/syntax.html#has-an-element-in-select-scope
821 public function inSelectScope( $tag ) {
822 // Can't use inSpecificScope to implement this, since it involves
823 // *inverting* a set of tags. Implement manually.
824 foreach ( $this as $elt ) {
825 if ( $elt->isA( $tag ) ) {
828 if ( !$elt->isA( BalanceSets
::$inInvertedSelectScopeSet ) ) {
836 * Determine if the stack has $tag in a specific scope, $set.
837 * @param BalanceElement|array|string $tag
838 * @param BalanceElement|array|string $set
840 * @see https://html.spec.whatwg.org/multipage/syntax.html#has-an-element-in-the-specific-scope
842 public function inSpecificScope( $tag, $set ) {
843 foreach ( $this as $elt ) {
844 if ( $elt->isA( $tag ) ) {
847 if ( $elt->isA( $set ) ) {
855 * Generate implied end tags.
856 * @param string $butnot
857 * @param bool $thorough True if we should generate end tags thoroughly.
858 * @see https://html.spec.whatwg.org/multipage/syntax.html#generate-implied-end-tags
860 public function generateImpliedEndTags( $butnot = null, $thorough = false ) {
861 $endTagSet = $thorough ?
862 BalanceSets
::$thoroughImpliedEndTagsSet :
863 BalanceSets
::$impliedEndTagsSet;
864 while ( $this->currentNode
) {
865 if ( $butnot !== null && $this->currentNode
->isHtmlNamed( $butnot ) ) {
868 if ( !$this->currentNode
->isA( $endTagSet ) ) {
876 * Return the adjusted current node.
878 public function adjustedCurrentNode( $fragmentContext ) {
879 return ( $fragmentContext && count( $this->elements
) === 1 ) ?
880 $fragmentContext : $this->currentNode
;
884 * Return an iterator over this stack which visits the current node
885 * first, and the root node last.
888 public function getIterator() {
889 return new ReverseArrayIterator( $this->elements
);
893 * Return the BalanceElement at the given position $idx, where
894 * position 0 represents the root element.
896 * @return BalanceElement
898 public function node( $idx ) {
899 return $this->elements
[ $idx ];
903 * Replace the element at position $idx in the BalanceStack with $elt.
905 * @param BalanceElement $elt
907 public function replaceAt( $idx, BalanceElement
$elt ) {
908 Assert
::precondition(
909 $this->elements
[$idx]->parent
!== 'flat',
910 'Replaced element should not have already been flattened.'
912 Assert
::precondition(
913 $elt->parent
!== 'flat',
914 'New element should not have already been flattened.'
916 $this->elements
[$idx] = $elt;
917 if ( $idx === count( $this->elements
) - 1 ) {
918 $this->currentNode
= $elt;
923 * Return the position of the given BalanceElement, set, or
924 * HTML tag name string in the BalanceStack.
925 * @param BalanceElement|array|string $tag
928 public function indexOf( $tag ) {
929 for ( $i = count( $this->elements
) - 1; $i >= 0; $i-- ) {
930 if ( $this->elements
[$i]->isA( $tag ) ) {
938 * Return the number of elements currently in the BalanceStack.
941 public function length() {
942 return count( $this->elements
);
946 * Remove the current node from the BalanceStack, flattening it
949 public function pop() {
950 $elt = array_pop( $this->elements
);
951 if ( count( $this->elements
) ) {
952 $this->currentNode
= $this->elements
[ count( $this->elements
) - 1 ];
954 $this->currentNode
= null;
956 if ( !$elt->isHtmlNamed( 'mw:p-wrap' ) ) {
957 $elt->flatten( $this->tidyCompat
);
962 * Remove all nodes up to and including position $idx from the
963 * BalanceStack, flattening them in the process.
966 public function popTo( $idx ) {
967 $length = count( $this->elements
);
968 for ( $length = count( $this->elements
); $length > $idx; $length-- ) {
974 * Pop elements off the stack up to and including the first
975 * element with the specified HTML tagname (or matching the given
977 * @param BalanceElement|array|string $tag
979 public function popTag( $tag ) {
980 while ( $this->currentNode
) {
981 if ( $this->currentNode
->isA( $tag ) ) {
990 * Pop elements off the stack *not including* the first element
991 * in the specified set.
992 * @param BalanceElement|array|string $set
994 public function clearToContext( $set ) {
995 // Note that we don't loop to 0. Never pop the <html> elt off.
996 for ( $length = count( $this->elements
); $length > 1; $length-- ) {
997 if ( $this->currentNode
->isA( $set ) ) {
1005 * Remove the given $elt from the BalanceStack, optionally
1006 * flattening it in the process.
1007 * @param BalanceElement $elt The element to remove.
1008 * @param bool $flatten Whether to flatten the removed element.
1010 public function removeElement( BalanceElement
$elt, $flatten = true ) {
1012 $elt->parent
!== 'flat',
1014 '$elt should not already have been flattened.'
1017 $elt->parent
->parent
!== 'flat',
1019 'The parent of $elt should not already have been flattened.'
1021 $idx = array_search( $elt, $this->elements
, true );
1022 Assert
::parameter( $idx !== false, '$elt', 'must be in stack' );
1023 array_splice( $this->elements
, $idx, 1 );
1024 if ( $idx === count( $this->elements
) ) {
1025 $this->currentNode
= $this->elements
[$idx - 1];
1028 // serialize $elt into its parent
1029 // otherwise, it will eventually serialize when the parent
1030 // is serialized, we just hold onto the memory for its
1031 // tree of objects a little longer.
1032 $elt->flatten( $this->tidyCompat
);
1034 Assert
::postcondition(
1035 array_search( $elt, $this->elements
, true ) === false,
1036 '$elt should no longer be in open elements stack'
1041 * Find $a in the BalanceStack and insert $b after it.
1042 * @param BalanceElement $a
1043 * @param BalanceElement $b
1045 public function insertAfter( BalanceElement
$a, BalanceElement
$b ) {
1046 $idx = $this->indexOf( $a );
1047 Assert
::parameter( $idx !== false, '$a', 'must be in stack' );
1048 if ( $idx === count( $this->elements
) - 1 ) {
1049 array_push( $this->elements
, $b );
1050 $this->currentNode
= $b;
1052 array_splice( $this->elements
, $idx +
1, 0, [ $b ] );
1056 # Fostering and adoption.
1059 * Foster parent the given $elt in the stack of open elements.
1060 * @param BalanceElement|string $elt
1061 * @see https://html.spec.whatwg.org/multipage/syntax.html#foster-parent
1063 private function fosterParent( $elt ) {
1064 $lastTable = $this->indexOf( 'table' );
1065 $lastTemplate = $this->indexOf( 'template' );
1069 if ( $lastTemplate >= 0 && ( $lastTable < 0 ||
$lastTemplate > $lastTable ) ) {
1070 $parent = $this->elements
[$lastTemplate];
1071 } elseif ( $lastTable >= 0 ) {
1072 $parent = $this->elements
[$lastTable]->parent
;
1073 # Assume all tables have parents, since we're not running scripts!
1075 $parent !== null, "All tables should have parents"
1077 $before = $this->elements
[$lastTable];
1079 $parent = $this->elements
[0]; // the `html` element.
1082 if ( $this->tidyCompat
) {
1083 if ( is_string( $elt ) ) {
1084 // We're fostering text: do we need a p-wrapper?
1085 if ( $parent->isA( BalanceSets
::$tidyPWrapSet ) ) {
1086 $this->insertHTMLElement( 'mw:p-wrap', [] );
1087 $this->insertText( $elt );
1091 // We're fostering an element; do we need to merge p-wrappers?
1092 if ( $elt->isHtmlNamed( 'mw:p-wrap' ) ) {
1094 array_search( $before, $parent->children
, true ) :
1095 count( $parent->children
);
1096 $after = $idx > 0 ?
$parent->children
[$idx - 1] : '';
1098 $after instanceof BalanceElement
&&
1099 $after->isHtmlNamed( 'mw:p-wrap' )
1101 return $after; // Re-use existing p-wrapper.
1108 $parent->insertBefore( $before, $elt );
1110 $parent->appendChild( $elt );
1116 * Run the "adoption agency algoritm" (AAA) for the given subject
1118 * @param string $tag The subject tag name.
1119 * @param BalanceActiveFormattingElements $afe The current
1120 * active formatting elements list.
1121 * @return true if the adoption agency algorithm "did something", false
1122 * if more processing is required by the caller.
1123 * @see https://html.spec.whatwg.org/multipage/syntax.html#adoption-agency-algorithm
1125 public function adoptionAgency( $tag, $afe ) {
1126 // If the current node is an HTML element whose tag name is subject,
1127 // and the current node is not in the list of active formatting
1128 // elements, then pop the current node off the stack of open
1129 // elements and abort these steps.
1131 $this->currentNode
->isHtmlNamed( $tag ) &&
1132 !$afe->isInList( $this->currentNode
)
1135 return true; // no more handling required
1138 // Let outer loop counter be zero.
1141 // Outer loop: If outer loop counter is greater than or
1142 // equal to eight, then abort these steps.
1143 while ( $outer < 8 ) {
1144 // Increment outer loop counter by one.
1147 // Let the formatting element be the last element in the list
1148 // of active formatting elements that: is between the end of
1149 // the list and the last scope marker in the list, if any, or
1150 // the start of the list otherwise, and has the same tag name
1152 $fmtelt = $afe->findElementByTag( $tag );
1154 // If there is no such node, then abort these steps and instead
1155 // act as described in the "any other end tag" entry below.
1157 return false; // false means handle by the default case
1160 // Otherwise, if there is such a node, but that node is not in
1161 // the stack of open elements, then this is a parse error;
1162 // remove the element from the list, and abort these steps.
1163 $index = $this->indexOf( $fmtelt );
1165 $afe->remove( $fmtelt );
1166 return true; // true means no more handling required
1169 // Otherwise, if there is such a node, and that node is also in
1170 // the stack of open elements, but the element is not in scope,
1171 // then this is a parse error; ignore the token, and abort
1173 if ( !$this->inScope( $fmtelt ) ) {
1177 // Let the furthest block be the topmost node in the stack of
1178 // open elements that is lower in the stack than the formatting
1179 // element, and is an element in the special category. There
1180 // might not be one.
1181 $furthestblock = null;
1182 $furthestblockindex = -1;
1183 $stacklen = $this->length();
1184 for ( $i = $index+
1; $i < $stacklen; $i++
) {
1185 if ( $this->node( $i )->isA( BalanceSets
::$specialSet ) ) {
1186 $furthestblock = $this->node( $i );
1187 $furthestblockindex = $i;
1192 // If there is no furthest block, then the UA must skip the
1193 // subsequent steps and instead just pop all the nodes from the
1194 // bottom of the stack of open elements, from the current node
1195 // up to and including the formatting element, and remove the
1196 // formatting element from the list of active formatting
1198 if ( !$furthestblock ) {
1199 $this->popTag( $fmtelt );
1200 $afe->remove( $fmtelt );
1203 // Let the common ancestor be the element immediately above
1204 // the formatting element in the stack of open elements.
1205 $ancestor = $this->node( $index-1 );
1207 // Let a bookmark note the position of the formatting
1208 // element in the list of active formatting elements
1209 // relative to the elements on either side of it in the
1211 $BOOKMARK = new BalanceElement( '[bookmark]', '[bookmark]', [] );
1212 $afe->insertAfter( $fmtelt, $BOOKMARK );
1214 // Let node and last node be the furthest block.
1215 $node = $furthestblock;
1216 $lastnode = $furthestblock;
1217 $nodeindex = $furthestblockindex;
1220 // Let inner loop counter be zero.
1225 // Increment inner loop counter by one.
1228 // Let node be the element immediately above node in
1229 // the stack of open elements, or if node is no longer
1230 // in the stack of open elements (e.g. because it got
1231 // removed by this algorithm), the element that was
1232 // immediately above node in the stack of open elements
1233 // before node was removed.
1234 $node = $this->node( --$nodeindex );
1236 // If node is the formatting element, then go
1237 // to the next step in the overall algorithm.
1238 if ( $node === $fmtelt ) break;
1240 // If the inner loop counter is greater than three and node
1241 // is in the list of active formatting elements, then remove
1242 // node from the list of active formatting elements.
1243 $isAFE = $afe->isInList( $node );
1244 if ( $inner > 3 && $isAFE ) {
1245 $afe->remove( $node );
1249 // If node is not in the list of active formatting
1250 // elements, then remove node from the stack of open
1251 // elements and then go back to the step labeled inner
1254 // Don't flatten here, since we're about to relocate
1255 // parts of this $node.
1256 $this->removeElement( $node, false );
1260 // Create an element for the token for which the
1261 // element node was created with common ancestor as
1262 // the intended parent, replace the entry for node
1263 // in the list of active formatting elements with an
1264 // entry for the new element, replace the entry for
1265 // node in the stack of open elements with an entry for
1266 // the new element, and let node be the new element.
1267 $newelt = new BalanceElement(
1268 $node->namespaceURI
, $node->localName
, $node->attribs
);
1269 $afe->replace( $node, $newelt );
1270 $this->replaceAt( $nodeindex, $newelt );
1273 // If last node is the furthest block, then move the
1274 // aforementioned bookmark to be immediately after the
1275 // new node in the list of active formatting elements.
1276 if ( $lastnode === $furthestblock ) {
1277 $afe->remove( $BOOKMARK );
1278 $afe->insertAfter( $newelt, $BOOKMARK );
1281 // Insert last node into node, first removing it from
1282 // its previous parent node if any.
1283 $node->appendChild( $lastnode );
1285 // Let last node be node.
1289 // If the common ancestor node is a table, tbody, tfoot,
1290 // thead, or tr element, then, foster parent whatever last
1291 // node ended up being in the previous step, first removing
1292 // it from its previous parent node if any.
1294 $this->fosterParentMode
&&
1295 $ancestor->isA( BalanceSets
::$tableSectionRowSet )
1297 $this->fosterParent( $lastnode );
1299 // Otherwise, append whatever last node ended up being in
1300 // the previous step to the common ancestor node, first
1301 // removing it from its previous parent node if any.
1302 $ancestor->appendChild( $lastnode );
1305 // Create an element for the token for which the
1306 // formatting element was created, with furthest block
1307 // as the intended parent.
1308 $newelt2 = new BalanceElement(
1309 $fmtelt->namespaceURI
, $fmtelt->localName
, $fmtelt->attribs
);
1311 // Take all of the child nodes of the furthest block and
1312 // append them to the element created in the last step.
1313 $newelt2->adoptChildren( $furthestblock );
1315 // Append that new element to the furthest block.
1316 $furthestblock->appendChild( $newelt2 );
1318 // Remove the formatting element from the list of active
1319 // formatting elements, and insert the new element into the
1320 // list of active formatting elements at the position of
1321 // the aforementioned bookmark.
1322 $afe->remove( $fmtelt );
1323 $afe->replace( $BOOKMARK, $newelt2 );
1325 // Remove the formatting element from the stack of open
1326 // elements, and insert the new element into the stack of
1327 // open elements immediately below the position of the
1328 // furthest block in that stack.
1329 $this->removeElement( $fmtelt );
1330 $this->insertAfter( $furthestblock, $newelt2 );
1338 * Return the contents of the open elements stack as a string for
1342 public function __toString() {
1344 foreach ( $this->elements
as $elt ) {
1345 array_push( $r, $elt->localName
);
1347 return implode( $r, ' ' );
1352 * A pseudo-element used as a marker in the list of active formatting elements
1357 class BalanceMarker
{
1363 * The list of active formatting elements, which is used to handle
1364 * mis-nested formatting element tags in the HTML5 tree builder
1369 * @see https://html.spec.whatwg.org/multipage/syntax.html#list-of-active-formatting-elements
1371 class BalanceActiveFormattingElements
{
1372 /** The last (most recent) element in the list */
1375 /** The first (least recent) element in the list */
1379 * An array of arrays representing the population of elements in each bucket
1380 * according to the Noah's Ark clause. The outer array is stack-like, with each
1381 * integer-indexed element representing a segment of the list, bounded by
1382 * markers. The first element represents the segment of the list before the
1385 * The inner arrays are indexed by "Noah key", which is a string which uniquely
1386 * identifies each bucket according to the rules in the spec. The value in
1387 * the inner array is the first (least recently inserted) element in the bucket,
1388 * and subsequent members of the bucket can be found by iterating through the
1389 * singly-linked list via $node->nextNoah.
1391 * This is optimised for the most common case of inserting into a bucket
1392 * with zero members, and deleting a bucket containing one member. In the
1393 * worst case, iteration through the list is still O(1) in the document
1394 * size, since each bucket can have at most 3 members.
1396 private $noahTableStack = [ [] ];
1398 public function __destruct() {
1399 for ( $node = $this->head
; $node; $node = $next ) {
1400 $next = $node->nextAFE
;
1401 $node->prevAFE
= $node->nextAFE
= $node->nextNoah
= null;
1403 $this->head
= $this->tail
= $this->noahTableStack
= null;
1406 public function insertMarker() {
1407 $elt = new BalanceMarker
;
1408 if ( $this->tail
) {
1409 $this->tail
->nextAFE
= $elt;
1410 $elt->prevAFE
= $this->tail
;
1415 $this->noahTableStack
[] = [];
1419 * Follow the steps required when the spec requires us to "push onto the
1420 * list of active formatting elements".
1421 * @param BalanceElement $elt
1423 public function push( BalanceElement
$elt ) {
1424 // Must not be in the list already
1425 if ( $elt->prevAFE
!== null ||
$this->head
=== $elt ) {
1426 throw new ParameterAssertionException( '$elt',
1427 'Cannot insert a node into the AFE list twice' );
1430 // "Noah's Ark clause" -- if there are already three copies of
1431 // this element before we encounter a marker, then drop the last
1433 $noahKey = $elt->getNoahKey();
1434 $table =& $this->noahTableStack
[ count( $this->noahTableStack
) - 1 ];
1435 if ( !isset( $table[$noahKey] ) ) {
1436 $table[$noahKey] = $elt;
1439 $head = $tail = $table[$noahKey];
1440 while ( $tail->nextNoah
) {
1441 $tail = $tail->nextNoah
;
1444 if ( $count >= 3 ) {
1445 $this->remove( $head );
1447 $tail->nextNoah
= $elt;
1449 // Add to the main AFE list
1450 if ( $this->tail
) {
1451 $this->tail
->nextAFE
= $elt;
1452 $elt->prevAFE
= $this->tail
;
1460 * Follow the steps required when the spec asks us to "clear the list of
1461 * active formatting elements up to the last marker".
1463 public function clearToMarker() {
1464 // Iterate back through the list starting from the tail
1465 $tail = $this->tail
;
1466 while ( $tail && !( $tail instanceof BalanceMarker
) ) {
1467 // Unlink the element
1468 $prev = $tail->prevAFE
;
1469 $tail->prevAFE
= null;
1471 $prev->nextAFE
= null;
1473 $tail->nextNoah
= null;
1476 // If we finished on a marker, unlink it and pop it off the Noah table stack
1478 $prev = $tail->prevAFE
;
1480 $prev->nextAFE
= null;
1483 array_pop( $this->noahTableStack
);
1485 // No marker: wipe the top-level Noah table (which is the only one)
1486 $this->noahTableStack
[0] = [];
1488 // If we removed all the elements, clear the head pointer
1492 $this->tail
= $tail;
1496 * Find and return the last element with the specified tag between the
1497 * end of the list and the last marker on the list.
1498 * Used when parsing <a> "in body mode".
1500 public function findElementByTag( $tag ) {
1502 while ( $elt && !( $elt instanceof BalanceMarker
) ) {
1503 if ( $elt->localName
=== $tag ) {
1506 $elt = $elt->prevAFE
;
1512 * Determine whether an element is in the list of formatting elements.
1515 public function isInList( BalanceElement
$elt ) {
1516 return $this->head
=== $elt ||
$elt->prevAFE
;
1520 * Find the element $elt in the list and remove it.
1521 * Used when parsing <a> in body mode.
1523 public function remove( BalanceElement
$elt ) {
1524 if ( $this->head
!== $elt && !$elt->prevAFE
) {
1525 throw new ParameterAssertionException( '$elt',
1526 "Attempted to remove an element which is not in the AFE list" );
1528 // Update head and tail pointers
1529 if ( $this->head
=== $elt ) {
1530 $this->head
= $elt->nextAFE
;
1532 if ( $this->tail
=== $elt ) {
1533 $this->tail
= $elt->prevAFE
;
1535 // Update previous element
1536 if ( $elt->prevAFE
) {
1537 $elt->prevAFE
->nextAFE
= $elt->nextAFE
;
1539 // Update next element
1540 if ( $elt->nextAFE
) {
1541 $elt->nextAFE
->prevAFE
= $elt->prevAFE
;
1543 // Clear pointers so that isInList() etc. will work
1544 $elt->prevAFE
= $elt->nextAFE
= null;
1546 $this->removeFromNoahList( $elt );
1549 private function addToNoahList( BalanceElement
$elt ) {
1550 $noahKey = $elt->getNoahKey();
1551 $table =& $this->noahTableStack
[ count( $this->noahTableStack
) - 1 ];
1552 if ( !isset( $table[$noahKey] ) ) {
1553 $table[$noahKey] = $elt;
1555 $tail = $table[$noahKey];
1556 while ( $tail->nextNoah
) {
1557 $tail = $tail->nextNoah
;
1559 $tail->nextNoah
= $elt;
1563 private function removeFromNoahList( BalanceElement
$elt ) {
1564 $table =& $this->noahTableStack
[ count( $this->noahTableStack
) - 1 ];
1565 $key = $elt->getNoahKey();
1566 $noahElt = $table[$key];
1567 if ( $noahElt === $elt ) {
1568 if ( $noahElt->nextNoah
) {
1569 $table[$key] = $noahElt->nextNoah
;
1570 $noahElt->nextNoah
= null;
1572 unset( $table[$key] );
1576 $prevNoahElt = $noahElt;
1577 $noahElt = $prevNoahElt->nextNoah
;
1578 if ( $noahElt === $elt ) {
1580 $prevNoahElt->nextNoah
= $elt->nextNoah
;
1581 $elt->nextNoah
= null;
1584 } while ( $noahElt );
1589 * Find element $a in the list and replace it with element $b
1591 public function replace( BalanceElement
$a, BalanceElement
$b ) {
1592 if ( $this->head
!== $a && !$a->prevAFE
) {
1593 throw new ParameterAssertionException( '$a',
1594 "Attempted to replace an element which is not in the AFE list" );
1596 // Update head and tail pointers
1597 if ( $this->head
=== $a ) {
1600 if ( $this->tail
=== $a ) {
1603 // Update previous element
1604 if ( $a->prevAFE
) {
1605 $a->prevAFE
->nextAFE
= $b;
1607 // Update next element
1608 if ( $a->nextAFE
) {
1609 $a->nextAFE
->prevAFE
= $b;
1611 $b->prevAFE
= $a->prevAFE
;
1612 $b->nextAFE
= $a->nextAFE
;
1613 $a->nextAFE
= $a->prevAFE
= null;
1615 $this->removeFromNoahList( $a );
1616 $this->addToNoahList( $b );
1620 * Find $a in the list and insert $b after it.
1622 public function insertAfter( BalanceElement
$a, BalanceElement
$b ) {
1623 if ( $this->head
!== $a && !$a->prevAFE
) {
1624 throw new ParameterAssertionException( '$a',
1625 "Attempted to insert after an element which is not in the AFE list" );
1627 if ( $this->tail
=== $a ) {
1630 if ( $a->nextAFE
) {
1631 $a->nextAFE
->prevAFE
= $b;
1633 $b->nextAFE
= $a->nextAFE
;
1636 $this->addToNoahList( $b );
1639 // @codingStandardsIgnoreStart Generic.Files.LineLength.TooLong
1641 * Reconstruct the active formatting elements.
1642 * @param BalanceStack $stack The open elements stack
1643 * @see https://html.spec.whatwg.org/multipage/syntax.html#reconstruct-the-active-formatting-elements
1645 // @codingStandardsIgnoreEnd
1646 public function reconstruct( $stack ) {
1647 $entry = $this->tail
;
1648 // If there are no entries in the list of active formatting elements,
1649 // then there is nothing to reconstruct
1653 // If the last is a marker, do nothing.
1654 if ( $entry instanceof BalanceMarker
) {
1657 // Or if it is an open element, do nothing.
1658 if ( $stack->indexOf( $entry ) >= 0 ) {
1662 // Loop backward through the list until we find a marker or an
1665 while ( $entry->prevAFE
) {
1666 $entry = $entry->prevAFE
;
1667 if ( $entry instanceof BalanceMarker ||
$stack->indexOf( $entry ) >= 0 ) {
1673 // Now loop forward, starting from the element after the current one (or
1674 // the first element if we didn't find a marker or open element),
1675 // recreating formatting elements and pushing them back onto the list
1676 // of open elements.
1678 $entry = $entry->nextAFE
;
1681 $newElement = $stack->insertHTMLElement(
1684 $this->replace( $entry, $newElement );
1685 $entry = $newElement->nextAFE
;
1690 * Get a string representation of the AFE list, for debugging
1692 public function __toString() {
1695 for ( $node = $this->head
; $node; $prev = $node, $node = $node->nextAFE
) {
1696 if ( $node instanceof BalanceMarker
) {
1700 $s .= $node->localName
. '#' . substr( md5( spl_object_hash( $node ) ), 0, 8 );
1701 if ( $node->nextNoah
) {
1702 $s .= " (noah sibling: {$node->nextNoah->localName}#" .
1703 substr( md5( spl_object_hash( $node->nextNoah
) ), 0, 8 ) .
1706 if ( $node->nextAFE
&& $node->nextAFE
->prevAFE
!== $node ) {
1707 $s .= " (reverse link is wrong!)";
1711 if ( $prev !== $this->tail
) {
1712 $s .= "(tail pointer is wrong!)\n";
1719 * An implementation of the tree building portion of the HTML5 parsing
1722 * This is used to balance and tidy output so that the result can
1723 * always be cleanly serialized/deserialized by an HTML5 parser. It
1724 * does *not* guarantee "conforming" output -- the HTML5 spec contains
1725 * a number of constraints which are not enforced by the HTML5 parsing
1726 * process. But the result will be free of gross errors: misnested or
1727 * unclosed tags, for example, and will be unchanged by spec-complient
1728 * parsing followed by serialization.
1730 * The tree building stage is structured as a state machine.
1731 * When comparing the implementation to
1732 * https://www.w3.org/TR/html5/syntax.html#tree-construction
1733 * note that each state is implemented as a function with a
1734 * name ending in `Mode` (because the HTML spec refers to them
1735 * as insertion modes). The current insertion mode is held by
1736 * the $parseMode property.
1738 * The following simplifications have been made:
1739 * - We handle body content only (ie, we start `in body`.)
1740 * - The document is never in "quirks mode".
1741 * - All occurrences of < and > have been entity escaped, so we
1742 * can parse tags by simply splitting on those two characters.
1743 * The character < must not appear inside comments.
1744 * Similarly, all attributes have been "cleaned" and are double-quoted
1746 * - All null characters are assumed to have been removed.
1747 * - We don't alter linefeeds after <pre>/<listing>.
1748 * - The following elements are disallowed: <html>, <head>, <body>, <frameset>,
1749 * <frame>, <plaintext>, <isindex>, <textarea>, <xmp>, <iframe>,
1750 * <noembed>, <noscript>, <script>, <title>. As a result,
1751 * further simplifications can be made:
1752 * - `frameset-ok` is not tracked.
1753 * - `head element pointer` is not tracked (but presumed non-null)
1754 * - Tokenizer has only a single mode.
1756 * We generally mark places where we omit cases from the spec due to
1757 * disallowed elements with a comment: `# OMITTED: <element-name>`.
1759 * The HTML spec keeps a flag during the parsing process to track
1760 * whether or not a "parse error" has been encountered. We don't
1761 * bother to track that flag, we just implement the error-handling
1762 * process as specified.
1766 * @see https://html.spec.whatwg.org/multipage/syntax.html#tree-construction
1770 private $bitsIterator;
1771 private $allowedHtmlElements;
1775 private $tidyCompat;
1776 private $allowComments;
1778 private $textIntegrationMode = false;
1779 private $pendingTableText;
1780 private $originalInsertionMode;
1781 private $fragmentContext;
1782 private $formElementPointer;
1785 * Valid HTML5 comments.
1786 * Regex borrowed from Tim Starling's "remex-html" project.
1788 const VALID_COMMENT_REGEX
= "~ !--
1789 ( # 1. Comment match detector
1790 > | -> | # Invalid short close
1791 ( # 2. Comment contents
1801 ( # 3. Comment close
1802 --> | # Normal close
1803 --!> | # Comment end bang
1804 ( # 4. Indicate matches requiring EOF
1805 --! | # EOF in comment end bang state
1806 -- | # EOF in comment end state
1807 - | # EOF in comment end dash state
1808 # EOF in comment state
1812 ([^<]*) \z # 5. Non-tag text after the comment
1816 * Create a new Balancer.
1817 * @param array $config Balancer configuration. Includes:
1818 * 'strict' : boolean, defaults to false.
1819 * When true, enforces syntactic constraints on input:
1820 * all non-tag '<' must be escaped, all attributes must be
1821 * separated by a single space and double-quoted. This is
1822 * consistent with the output of the Sanitizer.
1823 * 'allowedHtmlElements' : array, defaults to null.
1824 * When present, the keys of this associative array give
1825 * the acceptable HTML tag names. When not present, no
1826 * tag sanitization is done.
1827 * 'tidyCompat' : boolean, defaults to false.
1828 * When true, the serialization algorithm is tweaked to
1829 * provide historical compatibility with the old "tidy"
1830 * program: <p>-wrapping is done to the children of
1831 * <body> and <blockquote> elements, and empty elements
1833 * 'allowComments': boolean, defaults to true.
1834 * When true, allows HTML comments in the input.
1835 * The Sanitizer generally strips all comments, so if you
1836 * are running on sanitized output you can set this to
1837 * false to get a bit more performance.
1839 public function __construct( array $config = [] ) {
1840 $config = $config +
[
1842 'allowedHtmlElements' => null,
1843 'tidyCompat' => false,
1844 'allowComments' => true,
1846 $this->allowedHtmlElements
= $config['allowedHtmlElements'];
1847 $this->strict
= $config['strict'];
1848 $this->tidyCompat
= $config['tidyCompat'];
1849 $this->allowComments
= $config['allowComments'];
1850 if ( $this->allowedHtmlElements
!== null ) {
1852 $bad = array_uintersect_assoc(
1853 $this->allowedHtmlElements
,
1854 BalanceSets
::$unsupportedSet[BalanceSets
::HTML_NAMESPACE
],
1855 function( $a, $b ) {
1856 // Ignore the values (just intersect the keys) by saying
1857 // all values are equal to each other.
1861 if ( count( $bad ) > 0 ) {
1862 $badstr = implode( array_keys( $bad ), ',' );
1863 throw new ParameterAssertionException(
1865 'Balance attempted with sanitization including ' .
1866 "unsupported elements: {$badstr}"
1873 * Return a balanced HTML string for the HTML fragment given by $text,
1874 * subject to the caveats listed in the class description. The result
1875 * will typically be idempotent -- that is, rebalancing the output
1876 * would result in no change.
1878 * @param string $text The markup to be balanced
1879 * @param callable $processingCallback Callback to do any variable or
1880 * parameter replacements in HTML attributes values
1881 * @param array|bool $processingArgs Arguments for the processing callback
1882 * @return string The balanced markup
1884 public function balance( $text, $processingCallback = null, $processingArgs = [] ) {
1885 $this->parseMode
= 'inBodyMode';
1886 $this->bitsIterator
= new ExplodeIterator( '<', $text );
1887 $this->afe
= new BalanceActiveFormattingElements();
1888 $this->stack
= new BalanceStack();
1889 $this->stack
->tidyCompat
= $this->tidyCompat
;
1890 $this->processingCallback
= $processingCallback;
1891 $this->processingArgs
= $processingArgs;
1893 # The stack is constructed with an <html> element already on it.
1894 # Set this up as a fragment parsed with <body> as the context.
1895 $this->fragmentContext
=
1896 new BalanceElement( BalanceSets
::HTML_NAMESPACE
, 'body', [] );
1897 $this->resetInsertionMode();
1898 $this->formElementPointer
= null;
1899 for ( $e = $this->fragmentContext
; $e != null; $e = $e->parent
) {
1900 if ( $e->isHtmlNamed( 'form' ) ) {
1901 $this->formElementPointer
= $e;
1906 // First element is text not tag
1907 $x = $this->bitsIterator
->current();
1908 $this->bitsIterator
->next();
1909 $this->insertToken( 'text', str_replace( '>', '>', $x ) );
1910 // Now process each tag.
1911 while ( $this->bitsIterator
->valid() ) {
1914 $this->insertToken( 'eof', null );
1915 $result = $this->stack
->getOutput();
1916 // Free memory before returning.
1917 $this->bitsIterator
= null;
1919 $this->stack
= null;
1920 $this->fragmentContext
= null;
1921 $this->formElementPointer
= null;
1926 * Pass a token to the tree builder. The $token will be one of the
1927 * strings "tag", "endtag", or "text".
1929 private function insertToken( $token, $value, $attribs = null, $selfclose = false ) {
1930 // validate tags against $unsupportedSet
1931 if ( $token === 'tag' ||
$token === 'endtag' ) {
1932 if ( isset( BalanceSets
::$unsupportedSet[BalanceSets
::HTML_NAMESPACE
][$value] ) ) {
1933 # As described in "simplifications" above, these tags are
1934 # not supported in the balancer.
1937 "Unsupported $token <$value> found."
1941 } elseif ( $token === 'text' && $value === '' ) {
1942 # Don't actually inject the empty string as a text token.
1945 // Some hoops we have to jump through
1946 $adjusted = $this->stack
->adjustedCurrentNode( $this->fragmentContext
);
1950 $this->stack
->length() === 0 ||
1951 $adjusted->isHtml() ||
1955 } elseif ( $adjusted->isMathmlTextIntegrationPoint() ) {
1956 if ( $token === 'text' ) {
1960 $value !== 'mglyph' && $value !== 'malignmark'
1965 $adjusted->namespaceURI
=== BalanceSets
::MATHML_NAMESPACE
&&
1966 $adjusted->localName
=== 'annotation-xml' &&
1967 $token === 'tag' && $value === 'svg'
1971 $adjusted->isHtmlIntegrationPoint() &&
1972 ( $token === 'tag' ||
$token === 'text' )
1977 return $this->insertForeignToken( $token, $value, $attribs, $selfclose );
1979 $func = $this->parseMode
;
1980 return $this->$func( $token, $value, $attribs, $selfclose );
1984 private function insertForeignToken( $token, $value, $attribs = null, $selfclose = false ) {
1985 if ( $token === 'text' ) {
1986 $this->stack
->insertText( $value );
1988 } elseif ( $token === 'tag' ) {
1991 if ( isset( $attribs['color'] )
1992 ||
isset( $attribs['face'] )
1993 ||
isset( $attribs['size'] )
1997 /* otherwise, fall through */
2042 if ( $this->fragmentContext
) {
2046 $this->stack
->pop();
2047 $node = $this->stack
->currentNode
;
2049 $node->isMathmlTextIntegrationPoint() ||
2050 $node->isHtmlIntegrationPoint() ||
2056 return $this->insertToken( $token, $value, $attribs, $selfclose );
2058 // "Any other start tag"
2059 $adjusted = ( $this->fragmentContext
&& $this->stack
->length()===1 ) ?
2060 $this->fragmentContext
: $this->stack
->currentNode
;
2061 $this->stack
->insertForeignElement(
2062 $adjusted->namespaceURI
, $value, $attribs
2065 $this->stack
->pop();
2068 } elseif ( $token === 'endtag' ) {
2070 foreach ( $this->stack
as $i => $node ) {
2071 if ( $node->isHtml() && !$first ) {
2072 // process the end tag as HTML
2073 $func = $this->parseMode
;
2074 return $this->$func( $token, $value, $attribs, $selfclose );
2075 } elseif ( $i === 0 ) {
2077 } elseif ( $node->localName
=== $value ) {
2078 $this->stack
->popTag( $node );
2087 * Grab the next "token" from $bitsIterator. This is either a open/close
2088 * tag or text or a comment, depending on whether the Sanitizer approves.
2090 private function advance() {
2091 $x = $this->bitsIterator
->current();
2092 $this->bitsIterator
->next();
2094 # Handle comments. These won't be generated by mediawiki (they
2095 # are stripped in the Sanitizer) but may be generated by extensions.
2097 $this->allowComments
&&
2098 preg_match( Balancer
::VALID_COMMENT_REGEX
, $x, $regs, PREG_OFFSET_CAPTURE
) &&
2099 /* verify EOF condition where necessary */
2100 ( $regs[4][1] < 0 ||
!$this->bitsIterator
->valid() )
2102 $contents = $regs[2][0];
2103 $rest = $regs[5][0];
2104 $this->insertToken( 'comment', $contents );
2105 $this->insertToken( 'text', str_replace( '>', '>', $rest ) );
2108 # $slash: Does the current element start with a '/'?
2109 # $t: Current element name
2110 # $attribStr: String between element name and >
2111 # $brace: Ending '>' or '/>'
2112 # $rest: Everything until the next element from the $bitsIterator
2113 if ( preg_match( Sanitizer
::ELEMENT_BITS_REGEX
, $x, $regs ) ) {
2114 list( /* $qbar */, $slash, $t, $attribStr, $brace, $rest ) = $regs;
2115 $t = strtolower( $t );
2116 if ( $this->strict
) {
2117 /* Verify that attributes are all properly double-quoted */
2120 '/^( [:_A-Z0-9][-.:_A-Z0-9]*="[^"]*")*[ ]*$/i', $attribStr
2122 "Bad attribute string found"
2127 !$this->strict
, "< found which does not start a valid tag"
2129 $slash = $t = $attribStr = $brace = $rest = null;
2132 $sanitize = $this->allowedHtmlElements
!== null;
2134 $goodtag = $t && isset( $this->allowedHtmlElements
[$t] );
2137 if ( is_callable( $this->processingCallback
) ) {
2138 call_user_func_array( $this->processingCallback
, [ &$attribStr, $this->processingArgs
] );
2141 $goodtag = Sanitizer
::validateTag( $attribStr, $t );
2146 $attribs = Sanitizer
::decodeTagAttributes( $attribStr );
2147 $attribs = Sanitizer
::validateTagAttributes( $attribs, $t );
2149 $attribs = Sanitizer
::decodeTagAttributes( $attribStr );
2151 $goodtag = $this->insertToken(
2152 $slash ?
'endtag' : 'tag', $t, $attribs, $brace === '/>'
2156 $rest = str_replace( '>', '>', $rest );
2157 $this->insertToken( 'text', str_replace( '>', '>', $rest ) );
2159 # bad tag; serialize entire thing as text.
2160 $this->insertToken( 'text', '<' . str_replace( '>', '>', $x ) );
2164 private function switchMode( $mode ) {
2166 substr( $mode, -4 )==='Mode', '$mode', 'should end in Mode'
2168 $oldMode = $this->parseMode
;
2169 $this->parseMode
= $mode;
2173 private function switchModeAndReprocess( $mode, $token, $value, $attribs, $selfclose ) {
2174 $this->switchMode( $mode );
2175 return $this->insertToken( $token, $value, $attribs, $selfclose );
2178 private function resetInsertionMode() {
2180 foreach ( $this->stack
as $i => $node ) {
2183 if ( $this->fragmentContext
) {
2184 $node = $this->fragmentContext
;
2187 if ( $node->isHtml() ) {
2188 switch ( $node->localName
) {
2190 $stacklen = $this->stack
->length();
2191 for ( $j = $i +
1; $j < $stacklen-1; $j++
) {
2192 $ancestor = $this->stack
->node( $stacklen-$j-1 );
2193 if ( $ancestor->isHtmlNamed( 'template' ) ) {
2196 if ( $ancestor->isHtmlNamed( 'table' ) ) {
2197 $this->switchMode( 'inSelectInTableMode' );
2201 $this->switchMode( 'inSelectMode' );
2204 $this->switchMode( 'inRowMode' );
2209 $this->switchMode( 'inTableBodyMode' );
2212 $this->switchMode( 'inCaptionMode' );
2215 $this->switchMode( 'inColumnGroupMode' );
2218 $this->switchMode( 'inTableMode' );
2222 array_slice( $this->templateInsertionModes
, -1 )[0]
2226 $this->switchMode( 'inBodyMode' );
2228 # OMITTED: <frameset>
2234 if ( $node->isA( BalanceSets
::$tableCellSet ) ) {
2235 $this->switchMode( 'inCellMode' );
2242 $this->switchMode( 'inBodyMode' );
2248 private function stopParsing() {
2249 # Most of the spec methods are inapplicable, other than step 2:
2250 # "pop all the nodes off the stack of open elements".
2251 # We're going to keep the top-most <html> element on the stack, though.
2253 # Clear the AFE list first, otherwise the element objects will stay live
2254 # during serialization, potentially using O(N^2) memory. Note that
2255 # popping the stack will never result in reconstructing the active
2256 # formatting elements.
2258 $this->stack
->popTo( 1 );
2261 private function parseRawText( $value, $attribs = null ) {
2262 $this->stack
->insertHTMLElement( $value, $attribs );
2263 // XXX switch tokenizer to rawtext state?
2264 $this->originalInsertionMode
= $this->switchMode( 'inTextMode' );
2268 private function inTextMode( $token, $value, $attribs = null, $selfclose = false ) {
2269 if ( $token === 'text' ) {
2270 $this->stack
->insertText( $value );
2272 } elseif ( $token === 'eof' ) {
2273 $this->stack
->pop();
2274 return $this->switchModeAndReprocess(
2275 $this->originalInsertionMode
, $token, $value, $attribs, $selfclose
2277 } elseif ( $token === 'endtag' ) {
2278 $this->stack
->pop();
2279 $this->switchMode( $this->originalInsertionMode
);
2285 private function inHeadMode( $token, $value, $attribs = null, $selfclose = false ) {
2286 if ( $token === 'text' ) {
2287 if ( preg_match( '/^[\x09\x0A\x0C\x0D\x20]+/', $value, $matches ) ) {
2288 $this->stack
->insertText( $matches[0] );
2289 $value = substr( $value, strlen( $matches[0] ) );
2291 if ( strlen( $value ) === 0 ) {
2292 return true; // All text handled.
2294 // Fall through to handle non-whitespace below.
2295 } elseif ( $token === 'tag' ) {
2298 # OMITTED: in a full HTML parser, this might change the encoding.
2305 $this->stack
->insertHTMLElement( $value, $attribs );
2306 $this->stack
->pop();
2309 # OMITTED: <noscript>
2312 return $this->parseRawText( $value, $attribs );
2315 $this->stack
->insertHTMLElement( $value, $attribs );
2316 $this->afe
->insertMarker();
2317 # OMITTED: frameset_ok
2318 $this->switchMode( 'inTemplateMode' );
2319 $this->templateInsertionModes
[] = $this->parseMode
;
2323 } elseif ( $token === 'endtag' ) {
2329 break; // handle at the bottom of the function
2331 if ( $this->stack
->indexOf( $value ) < 0 ) {
2332 return true; // Ignore the token.
2334 $this->stack
->generateImpliedEndTags( null, true /* thorough */ );
2335 $this->stack
->popTag( $value );
2336 $this->afe
->clearToMarker();
2337 array_pop( $this->templateInsertionModes
);
2338 $this->resetInsertionMode();
2341 // ignore any other end tag
2344 } elseif ( $token === 'comment' ) {
2345 $this->stack
->insertComment( $value );
2349 // If not handled above
2350 $this->inHeadMode( 'endtag', 'head' ); // synthetic </head>
2351 // Then redo this one
2352 return $this->insertToken( $token, $value, $attribs, $selfclose );
2355 private function inBodyMode( $token, $value, $attribs = null, $selfclose = false ) {
2356 if ( $token === 'text' ) {
2357 $this->afe
->reconstruct( $this->stack
);
2358 $this->stack
->insertText( $value );
2360 } elseif ( $token === 'eof' ) {
2361 if ( !empty( $this->templateInsertionModes
) ) {
2362 return $this->inTemplateMode( $token, $value, $attribs, $selfclose );
2364 $this->stopParsing();
2366 } elseif ( $token === 'tag' ) {
2379 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
2381 # OMITTED: <frameset>
2407 if ( $this->stack
->inButtonScope( 'p' ) ) {
2408 $this->inBodyMode( 'endtag', 'p' );
2410 $this->stack
->insertHTMLElement( $value, $attribs );
2419 if ( $this->stack
->inButtonScope( 'p' ) ) {
2420 $this->inBodyMode( 'endtag', 'p' );
2422 if ( $this->stack
->currentNode
->isA( BalanceSets
::$headingSet ) ) {
2423 $this->stack
->pop();
2425 $this->stack
->insertHTMLElement( $value, $attribs );
2430 if ( $this->stack
->inButtonScope( 'p' ) ) {
2431 $this->inBodyMode( 'endtag', 'p' );
2433 $this->stack
->insertHTMLElement( $value, $attribs );
2434 # As described in "simplifications" above:
2435 # 1. We don't touch the next token, even if it's a linefeed.
2436 # 2. OMITTED: frameset_ok
2441 $this->formElementPointer
&&
2442 $this->stack
->indexOf( 'template' ) < 0
2444 return true; // in a form, not in a template.
2446 if ( $this->stack
->inButtonScope( "p" ) ) {
2447 $this->inBodyMode( 'endtag', 'p' );
2449 $elt = $this->stack
->insertHTMLElement( $value, $attribs );
2450 if ( $this->stack
->indexOf( 'template' ) < 0 ) {
2451 $this->formElementPointer
= $elt;
2456 # OMITTED: frameset_ok
2457 foreach ( $this->stack
as $node ) {
2458 if ( $node->isHtmlNamed( 'li' ) ) {
2459 $this->inBodyMode( 'endtag', 'li' );
2463 $node->isA( BalanceSets
::$specialSet ) &&
2464 !$node->isA( BalanceSets
::$addressDivPSet )
2469 if ( $this->stack
->inButtonScope( 'p' ) ) {
2470 $this->inBodyMode( 'endtag', 'p' );
2472 $this->stack
->insertHTMLElement( $value, $attribs );
2477 # OMITTED: frameset_ok
2478 foreach ( $this->stack
as $node ) {
2479 if ( $node->isHtmlNamed( 'dd' ) ) {
2480 $this->inBodyMode( 'endtag', 'dd' );
2483 if ( $node->isHtmlNamed( 'dt' ) ) {
2484 $this->inBodyMode( 'endtag', 'dt' );
2488 $node->isA( BalanceSets
::$specialSet ) &&
2489 !$node->isA( BalanceSets
::$addressDivPSet )
2494 if ( $this->stack
->inButtonScope( 'p' ) ) {
2495 $this->inBodyMode( 'endtag', 'p' );
2497 $this->stack
->insertHTMLElement( $value, $attribs );
2500 # OMITTED: <plaintext>
2503 if ( $this->stack
->inScope( 'button' ) ) {
2504 $this->inBodyMode( 'endtag', 'button' );
2505 return $this->insertToken( $token, $value, $attribs, $selfclose );
2507 $this->afe
->reconstruct( $this->stack
);
2508 $this->stack
->insertHTMLElement( $value, $attribs );
2512 $activeElement = $this->afe
->findElementByTag( 'a' );
2513 if ( $activeElement ) {
2514 $this->inBodyMode( 'endtag', 'a' );
2515 if ( $this->afe
->isInList( $activeElement ) ) {
2516 $this->afe
->remove( $activeElement );
2517 // Don't flatten here, since when we fall
2518 // through below we might foster parent
2519 // the new <a> tag inside this one.
2520 $this->stack
->removeElement( $activeElement, false );
2536 $this->afe
->reconstruct( $this->stack
);
2537 $this->afe
->push( $this->stack
->insertHTMLElement( $value, $attribs ), $attribs );
2541 $this->afe
->reconstruct( $this->stack
);
2542 if ( $this->stack
->inScope( 'nobr' ) ) {
2543 $this->inBodyMode( 'endtag', 'nobr' );
2544 $this->afe
->reconstruct( $this->stack
);
2546 $this->afe
->push( $this->stack
->insertHTMLElement( $value, $attribs ), $attribs );
2552 $this->afe
->reconstruct( $this->stack
);
2553 $this->stack
->insertHTMLElement( $value, $attribs );
2554 $this->afe
->insertMarker();
2555 # OMITTED: frameset_ok
2559 # The document is never in "quirks mode"; see simplifications
2561 if ( $this->stack
->inButtonScope( 'p' ) ) {
2562 $this->inBodyMode( 'endtag', 'p' );
2564 $this->stack
->insertHTMLElement( $value, $attribs );
2565 # OMITTED: frameset_ok
2566 $this->switchMode( 'inTableMode' );
2575 $this->afe
->reconstruct( $this->stack
);
2576 $this->stack
->insertHTMLElement( $value, $attribs );
2577 $this->stack
->pop();
2578 # OMITTED: frameset_ok
2582 $this->afe
->reconstruct( $this->stack
);
2583 $this->stack
->insertHTMLElement( $value, $attribs );
2584 $this->stack
->pop();
2585 # OMITTED: frameset_ok
2586 # (hence we don't need to examine the tag's "type" attribute)
2593 $this->stack
->insertHTMLElement( $value, $attribs );
2594 $this->stack
->pop();
2598 if ( $this->stack
->inButtonScope( 'p' ) ) {
2599 $this->inBodyMode( 'endtag', 'p' );
2601 $this->stack
->insertHTMLElement( $value, $attribs );
2602 $this->stack
->pop();
2607 return $this->inBodyMode( $token, 'img', $attribs, $selfclose );
2609 # OMITTED: <isindex>
2610 # OMITTED: <textarea>
2613 # OMITTED: <noembed>
2614 # OMITTED: <noscript>
2617 $this->afe
->reconstruct( $this->stack
);
2618 $this->stack
->insertHTMLElement( $value, $attribs );
2619 switch ( $this->parseMode
) {
2621 case 'inCaptionMode':
2622 case 'inTableBodyMode':
2625 $this->switchMode( 'inSelectInTableMode' );
2628 $this->switchMode( 'inSelectMode' );
2634 if ( $this->stack
->currentNode
->isHtmlNamed( 'option' ) ) {
2635 $this->inBodyMode( 'endtag', 'option' );
2637 $this->afe
->reconstruct( $this->stack
);
2638 $this->stack
->insertHTMLElement( $value, $attribs );
2643 if ( $this->stack
->inScope( 'ruby' ) ) {
2644 $this->stack
->generateImpliedEndTags();
2646 $this->stack
->insertHTMLElement( $value, $attribs );
2651 if ( $this->stack
->inScope( 'ruby' ) ) {
2652 $this->stack
->generateImpliedEndTags( 'rtc' );
2654 $this->stack
->insertHTMLElement( $value, $attribs );
2658 $this->afe
->reconstruct( $this->stack
);
2659 # We skip the spec's "adjust MathML attributes" and
2660 # "adjust foreign attributes" steps, since the browser will
2661 # do this later when it parses the output and it doesn't affect
2663 $this->stack
->insertForeignElement(
2664 BalanceSets
::MATHML_NAMESPACE
, $value, $attribs
2667 # emit explicit </math> tag.
2668 $this->stack
->pop();
2673 $this->afe
->reconstruct( $this->stack
);
2674 # We skip the spec's "adjust SVG attributes" and
2675 # "adjust foreign attributes" steps, since the browser will
2676 # do this later when it parses the output and it doesn't affect
2678 $this->stack
->insertForeignElement(
2679 BalanceSets
::SVG_NAMESPACE
, $value, $attribs
2682 # emit explicit </svg> tag.
2683 $this->stack
->pop();
2698 // Ignore table tags if we're not inTableMode
2702 // Handle any other start tag here
2703 $this->afe
->reconstruct( $this->stack
);
2704 $this->stack
->insertHTMLElement( $value, $attribs );
2706 } elseif ( $token === 'endtag' ) {
2708 # </body>,</html> are unsupported.
2711 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
2739 // Ignore if there is not a matching open tag
2740 if ( !$this->stack
->inScope( $value ) ) {
2743 $this->stack
->generateImpliedEndTags();
2744 $this->stack
->popTag( $value );
2748 if ( $this->stack
->indexOf( 'template' ) < 0 ) {
2749 $openform = $this->formElementPointer
;
2750 $this->formElementPointer
= null;
2751 if ( !$openform ||
!$this->stack
->inScope( $openform ) ) {
2754 $this->stack
->generateImpliedEndTags();
2755 // Don't flatten yet if we're removing a <form> element
2756 // out-of-order. (eg. `<form><div></form>`)
2757 $flatten = ( $this->stack
->currentNode
=== $openform );
2758 $this->stack
->removeElement( $openform, $flatten );
2760 if ( !$this->stack
->inScope( 'form' ) ) {
2763 $this->stack
->generateImpliedEndTags();
2764 $this->stack
->popTag( 'form' );
2769 if ( !$this->stack
->inButtonScope( 'p' ) ) {
2770 $this->inBodyMode( 'tag', 'p', [] );
2771 return $this->insertToken( $token, $value, $attribs, $selfclose );
2773 $this->stack
->generateImpliedEndTags( $value );
2774 $this->stack
->popTag( $value );
2778 if ( !$this->stack
->inListItemScope( $value ) ) {
2779 return true; # ignore
2781 $this->stack
->generateImpliedEndTags( $value );
2782 $this->stack
->popTag( $value );
2787 if ( !$this->stack
->inScope( $value ) ) {
2788 return true; # ignore
2790 $this->stack
->generateImpliedEndTags( $value );
2791 $this->stack
->popTag( $value );
2800 if ( !$this->stack
->inScope( BalanceSets
::$headingSet ) ) {
2801 return true; # ignore
2803 $this->stack
->generateImpliedEndTags();
2804 $this->stack
->popTag( BalanceSets
::$headingSet );
2808 # Take a deep breath, then:
2825 if ( $this->stack
->adoptionAgency( $value, $this->afe
) ) {
2826 return true; # If we did something, we're done.
2828 break; # Go to the "any other end tag" case.
2833 if ( !$this->stack
->inScope( $value ) ) {
2834 return true; # ignore
2836 $this->stack
->generateImpliedEndTags();
2837 $this->stack
->popTag( $value );
2838 $this->afe
->clearToMarker();
2842 # Turn </br> into <br>
2843 return $this->inBodyMode( 'tag', $value, [] );
2846 // Any other end tag goes here
2847 foreach ( $this->stack
as $i => $node ) {
2848 if ( $node->isHtmlNamed( $value ) ) {
2849 $this->stack
->generateImpliedEndTags( $value );
2850 $this->stack
->popTo( $i ); # including $i
2852 } elseif ( $node->isA( BalanceSets
::$specialSet ) ) {
2853 return true; // ignore this close token.
2857 } elseif ( $token === 'comment' ) {
2858 $this->stack
->insertComment( $value );
2861 Assert
::invariant( false, "Bad token type: $token" );
2865 private function inTableMode( $token, $value, $attribs = null, $selfclose = false ) {
2866 if ( $token === 'text' ) {
2867 if ( $this->textIntegrationMode
) {
2868 return $this->inBodyMode( $token, $value, $attribs, $selfclose );
2869 } elseif ( $this->stack
->currentNode
->isA( BalanceSets
::$tableSectionRowSet ) ) {
2870 $this->pendingTableText
= '';
2871 $this->originalInsertionMode
= $this->parseMode
;
2872 return $this->switchModeAndReprocess( 'inTableTextMode', $token, $value, $attribs, $selfclose );
2874 // fall through to default case.
2875 } elseif ( $token === 'eof' ) {
2876 $this->stopParsing();
2878 } elseif ( $token === 'tag' ) {
2881 $this->afe
->insertMarker();
2882 $this->stack
->insertHTMLElement( $value, $attribs );
2883 $this->switchMode( 'inCaptionMode' );
2886 $this->stack
->clearToContext( BalanceSets
::$tableContextSet );
2887 $this->stack
->insertHTMLElement( $value, $attribs );
2888 $this->switchMode( 'inColumnGroupMode' );
2891 $this->inTableMode( 'tag', 'colgroup', [] );
2892 return $this->insertToken( $token, $value, $attribs, $selfclose );
2896 $this->stack
->clearToContext( BalanceSets
::$tableContextSet );
2897 $this->stack
->insertHTMLElement( $value, $attribs );
2898 $this->switchMode( 'inTableBodyMode' );
2903 $this->inTableMode( 'tag', 'tbody', [] );
2904 return $this->insertToken( $token, $value, $attribs, $selfclose );
2906 if ( !$this->stack
->inTableScope( $value ) ) {
2907 return true; // Ignore this tag.
2909 $this->inTableMode( 'endtag', $value );
2910 return $this->insertToken( $token, $value, $attribs, $selfclose );
2915 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
2918 if ( !isset( $attribs['type'] ) ||
strcasecmp( $attribs['type'], 'hidden' ) !== 0 ) {
2919 break; // Handle this as "everything else"
2921 $this->stack
->insertHTMLElement( $value, $attribs );
2922 $this->stack
->pop();
2927 $this->formElementPointer ||
2928 $this->stack
->indexOf( 'template' ) >= 0
2930 return true; // ignore this token
2932 $this->formElementPointer
=
2933 $this->stack
->insertHTMLElement( $value, $attribs );
2934 $this->stack
->popTag( $this->formElementPointer
);
2937 // Fall through for "anything else" clause.
2938 } elseif ( $token === 'endtag' ) {
2941 if ( !$this->stack
->inTableScope( $value ) ) {
2942 return true; // Ignore.
2944 $this->stack
->popTag( $value );
2945 $this->resetInsertionMode();
2958 return true; // Ignore the token.
2960 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
2962 // Fall through for "anything else" clause.
2963 } elseif ( $token === 'comment' ) {
2964 $this->stack
->insertComment( $value );
2967 // This is the "anything else" case:
2968 $this->stack
->fosterParentMode
= true;
2969 $this->inBodyMode( $token, $value, $attribs, $selfclose );
2970 $this->stack
->fosterParentMode
= false;
2974 private function inTableTextMode( $token, $value, $attribs = null, $selfclose = false ) {
2975 if ( $token === 'text' ) {
2976 $this->pendingTableText
.= $value;
2980 $text = $this->pendingTableText
;
2981 $this->pendingTableText
= '';
2982 if ( preg_match( '/[^\x09\x0A\x0C\x0D\x20]/', $text ) ) {
2983 // This should match the "anything else" case inTableMode
2984 $this->stack
->fosterParentMode
= true;
2985 $this->inBodyMode( 'text', $text );
2986 $this->stack
->fosterParentMode
= false;
2988 // Pending text is just whitespace.
2989 $this->stack
->insertText( $text );
2991 return $this->switchModeAndReprocess(
2992 $this->originalInsertionMode
, $token, $value, $attribs, $selfclose
2996 // helper for inCaptionMode
2997 private function endCaption() {
2998 if ( !$this->stack
->inTableScope( 'caption' ) ) {
3001 $this->stack
->generateImpliedEndTags();
3002 $this->stack
->popTag( 'caption' );
3003 $this->afe
->clearToMarker();
3004 $this->switchMode( 'inTableMode' );
3008 private function inCaptionMode( $token, $value, $attribs = null, $selfclose = false ) {
3009 if ( $token === 'tag' ) {
3020 if ( $this->endCaption() ) {
3021 $this->insertToken( $token, $value, $attribs, $selfclose );
3025 // Fall through to "anything else" case.
3026 } elseif ( $token === 'endtag' ) {
3029 $this->endCaption();
3032 if ( $this->endCaption() ) {
3033 $this->insertToken( $token, $value, $attribs, $selfclose );
3049 // Fall through to "anything else" case.
3051 // The Anything Else case
3052 return $this->inBodyMode( $token, $value, $attribs, $selfclose );
3055 private function inColumnGroupMode( $token, $value, $attribs = null, $selfclose = false ) {
3056 if ( $token === 'text' ) {
3057 if ( preg_match( '/^[\x09\x0A\x0C\x0D\x20]+/', $value, $matches ) ) {
3058 $this->stack
->insertText( $matches[0] );
3059 $value = substr( $value, strlen( $matches[0] ) );
3061 if ( strlen( $value ) === 0 ) {
3062 return true; // All text handled.
3064 // Fall through to handle non-whitespace below.
3065 } elseif ( $token === 'tag' ) {
3069 $this->stack
->insertHTMLElement( $value, $attribs );
3070 $this->stack
->pop();
3073 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
3075 // Fall through for "anything else".
3076 } elseif ( $token === 'endtag' ) {
3079 if ( !$this->stack
->currentNode
->isHtmlNamed( 'colgroup' ) ) {
3080 return true; // Ignore the token.
3082 $this->stack
->pop();
3083 $this->switchMode( 'inTableMode' );
3086 return true; // Ignore the token.
3088 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
3090 // Fall through for "anything else".
3091 } elseif ( $token === 'eof' ) {
3092 return $this->inBodyMode( $token, $value, $attribs, $selfclose );
3093 } elseif ( $token === 'comment' ) {
3094 $this->stack
->insertComment( $value );
3099 if ( !$this->stack
->currentNode
->isHtmlNamed( 'colgroup' ) ) {
3100 return true; // Ignore the token.
3102 $this->inColumnGroupMode( 'endtag', 'colgroup' );
3103 return $this->insertToken( $token, $value, $attribs, $selfclose );
3106 // Helper function for inTableBodyMode
3107 private function endSection() {
3109 $this->stack
->inTableScope( 'tbody' ) ||
3110 $this->stack
->inTableScope( 'thead' ) ||
3111 $this->stack
->inTableScope( 'tfoot' )
3115 $this->stack
->clearToContext( BalanceSets
::$tableBodyContextSet );
3116 $this->stack
->pop();
3117 $this->switchMode( 'inTableMode' );
3120 private function inTableBodyMode( $token, $value, $attribs = null, $selfclose = false ) {
3121 if ( $token === 'tag' ) {
3124 $this->stack
->clearToContext( BalanceSets
::$tableBodyContextSet );
3125 $this->stack
->insertHTMLElement( $value, $attribs );
3126 $this->switchMode( 'inRowMode' );
3130 $this->inTableBodyMode( 'tag', 'tr', [] );
3131 $this->insertToken( $token, $value, $attribs, $selfclose );
3139 if ( $this->endSection() ) {
3140 $this->insertToken( $token, $value, $attribs, $selfclose );
3144 } elseif ( $token === 'endtag' ) {
3147 if ( $this->endSection() ) {
3148 $this->insertToken( $token, $value, $attribs, $selfclose );
3154 if ( $this->stack
->inTableScope( $value ) ) {
3155 $this->endSection();
3166 return true; // Ignore the token.
3170 return $this->inTableMode( $token, $value, $attribs, $selfclose );
3173 // Helper function for inRowMode
3174 private function endRow() {
3175 if ( !$this->stack
->inTableScope( 'tr' ) ) {
3178 $this->stack
->clearToContext( BalanceSets
::$tableRowContextSet );
3179 $this->stack
->pop();
3180 $this->switchMode( 'inTableBodyMode' );
3183 private function inRowMode( $token, $value, $attribs = null, $selfclose = false ) {
3184 if ( $token === 'tag' ) {
3188 $this->stack
->clearToContext( BalanceSets
::$tableRowContextSet );
3189 $this->stack
->insertHTMLElement( $value, $attribs );
3190 $this->switchMode( 'inCellMode' );
3191 $this->afe
->insertMarker();
3200 if ( $this->endRow() ) {
3201 $this->insertToken( $token, $value, $attribs, $selfclose );
3205 } elseif ( $token === 'endtag' ) {
3211 if ( $this->endRow() ) {
3212 $this->insertToken( $token, $value, $attribs, $selfclose );
3219 $this->stack
->inTableScope( $value ) &&
3222 $this->insertToken( $token, $value, $attribs, $selfclose );
3232 return true; // Ignore the token.
3236 return $this->inTableMode( $token, $value, $attribs, $selfclose );
3239 // Helper for inCellMode
3240 private function endCell() {
3241 if ( $this->stack
->inTableScope( 'td' ) ) {
3242 $this->inCellMode( 'endtag', 'td' );
3244 } elseif ( $this->stack
->inTableScope( 'th' ) ) {
3245 $this->inCellMode( 'endtag', 'th' );
3251 private function inCellMode( $token, $value, $attribs = null, $selfclose = false ) {
3252 if ( $token === 'tag' ) {
3263 if ( $this->endCell() ) {
3264 $this->insertToken( $token, $value, $attribs, $selfclose );
3268 } elseif ( $token === 'endtag' ) {
3272 if ( $this->stack
->inTableScope( $value ) ) {
3273 $this->stack
->generateImpliedEndTags();
3274 $this->stack
->popTag( $value );
3275 $this->afe
->clearToMarker();
3276 $this->switchMode( 'inRowMode' );
3291 if ( $this->stack
->inTableScope( $value ) ) {
3292 $this->stack
->generateImpliedEndTags();
3293 $this->stack
->popTag( BalanceSets
::$tableCellSet );
3294 $this->afe
->clearToMarker();
3295 $this->switchMode( 'inRowMode' );
3296 $this->insertToken( $token, $value, $attribs, $selfclose );
3302 return $this->inBodyMode( $token, $value, $attribs, $selfclose );
3305 private function inSelectMode( $token, $value, $attribs = null, $selfclose = false ) {
3306 if ( $token === 'text' ) {
3307 $this->stack
->insertText( $value );
3309 } elseif ( $token === 'eof' ) {
3310 return $this->inBodyMode( $token, $value, $attribs, $selfclose );
3311 } elseif ( $token === 'tag' ) {
3315 if ( $this->stack
->currentNode
->isHtmlNamed( 'option' ) ) {
3316 $this->stack
->pop();
3318 $this->stack
->insertHTMLElement( $value, $attribs );
3321 if ( $this->stack
->currentNode
->isHtmlNamed( 'option' ) ) {
3322 $this->stack
->pop();
3324 if ( $this->stack
->currentNode
->isHtmlNamed( 'optgroup' ) ) {
3325 $this->stack
->pop();
3327 $this->stack
->insertHTMLElement( $value, $attribs );
3330 $this->inSelectMode( 'endtag', $value ); // treat it like endtag
3335 if ( !$this->stack
->inSelectScope( 'select' ) ) {
3336 return true; // ignore token (fragment case)
3338 $this->inSelectMode( 'endtag', 'select' );
3339 return $this->insertToken( $token, $value, $attribs, $selfclose );
3342 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
3344 } elseif ( $token === 'endtag' ) {
3348 $this->stack
->currentNode
->isHtmlNamed( 'option' ) &&
3349 $this->stack
->length() >= 2 &&
3350 $this->stack
->node( $this->stack
->length() - 2 )->isHtmlNamed( 'optgroup' )
3352 $this->stack
->pop();
3354 if ( $this->stack
->currentNode
->isHtmlNamed( 'optgroup' ) ) {
3355 $this->stack
->pop();
3359 if ( $this->stack
->currentNode
->isHtmlNamed( 'option' ) ) {
3360 $this->stack
->pop();
3364 if ( !$this->stack
->inSelectScope( $value ) ) {
3365 return true; // fragment case
3367 $this->stack
->popTag( $value );
3368 $this->resetInsertionMode();
3371 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
3373 } elseif ( $token === 'comment' ) {
3374 $this->stack
->insertComment( $value );
3377 // anything else: just ignore the token
3381 private function inSelectInTableMode( $token, $value, $attribs = null, $selfclose = false ) {
3391 if ( $token === 'tag' ) {
3392 $this->inSelectInTableMode( 'endtag', 'select' );
3393 return $this->insertToken( $token, $value, $attribs, $selfclose );
3394 } elseif ( $token === 'endtag' ) {
3395 if ( $this->stack
->inTableScope( $value ) ) {
3396 $this->inSelectInTableMode( 'endtag', 'select' );
3397 return $this->insertToken( $token, $value, $attribs, $selfclose );
3403 return $this->inSelectMode( $token, $value, $attribs, $selfclose );
3406 private function inTemplateMode( $token, $value, $attribs = null, $selfclose = false ) {
3407 if ( $token === 'text' ||
$token === 'comment' ) {
3408 return $this->inBodyMode( $token, $value, $attribs, $selfclose );
3409 } elseif ( $token === 'eof' ) {
3410 if ( $this->stack
->indexOf( 'template' ) < 0 ) {
3411 $this->stopParsing();
3413 $this->stack
->popTag( 'template' );
3414 $this->afe
->clearToMarker();
3415 array_pop( $this->templateInsertionModes
);
3416 $this->resetInsertionMode();
3417 $this->insertToken( $token, $value, $attribs, $selfclose );
3420 } elseif ( $token === 'tag' ) {
3432 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
3439 return $this->switchModeAndReprocess(
3440 'inTableMode', $token, $value, $attribs, $selfclose
3444 return $this->switchModeAndReprocess(
3445 'inColumnGroupMode', $token, $value, $attribs, $selfclose
3449 return $this->switchModeAndReprocess(
3450 'inTableBodyMode', $token, $value, $attribs, $selfclose
3455 return $this->switchModeAndReprocess(
3456 'inRowMode', $token, $value, $attribs, $selfclose
3459 return $this->switchModeAndReprocess(
3460 'inBodyMode', $token, $value, $attribs, $selfclose
3462 } elseif ( $token === 'endtag' ) {
3465 return $this->inHeadMode( $token, $value, $attribs, $selfclose );
3469 Assert
::invariant( false, "Bad token type: $token" );