Takes a well formed list of tokens and fixes their nesting.
HTML elements dictate which elements are allowed to be their children, for example, you can't have a p tag in a span tag. Other elements have much more rigorous definitions: tables, for instance, require a specific order for their elements. There are also constraints not expressible by document type definitions, such as the chameleon nature of ins/del tags and global child exclusions.
The first major objective of this strategy is to iterate through all the nodes and determine whether or not their children conform to the element's definition. If they do not, the child definition may optionally supply an amended list of elements that is valid or require that the entire node be deleted (and the previous node rescanned).
The second objective is to ensure that explicitly excluded elements of an element do not appear in its children. Code that accomplishes this task is pervasive through the strategy, though the two are distinct tasks and could, theoretically, be seperated (although it's not recommended).
execute(\HTMLPurifier_Token[] $tokens, \HTMLPurifier_Config $config, \HTMLPurifier_Context $context) : array|\HTMLPurifier_Token[]
Executes the strategy on the tokens.
| \HTMLPurifier_Token[] | $tokens | |
| \HTMLPurifier_Config | $config | |
| \HTMLPurifier_Context | $context |
<?php
/**
* Takes a well formed list of tokens and fixes their nesting.
*
* HTML elements dictate which elements are allowed to be their children,
* for example, you can't have a p tag in a span tag. Other elements have
* much more rigorous definitions: tables, for instance, require a specific
* order for their elements. There are also constraints not expressible by
* document type definitions, such as the chameleon nature of ins/del
* tags and global child exclusions.
*
* The first major objective of this strategy is to iterate through all
* the nodes and determine whether or not their children conform to the
* element's definition. If they do not, the child definition may
* optionally supply an amended list of elements that is valid or
* require that the entire node be deleted (and the previous node
* rescanned).
*
* The second objective is to ensure that explicitly excluded elements of
* an element do not appear in its children. Code that accomplishes this
* task is pervasive through the strategy, though the two are distinct tasks
* and could, theoretically, be seperated (although it's not recommended).
*
* @note Whether or not unrecognized children are silently dropped or
* translated into text depends on the child definitions.
*
* @todo Enable nodes to be bubbled out of the structure. This is
* easier with our new algorithm.
*/
class HTMLPurifier_Strategy_FixNesting extends HTMLPurifier_Strategy
{
/**
* @param HTMLPurifier_Token[] $tokens
* @param HTMLPurifier_Config $config
* @param HTMLPurifier_Context $context
* @return array|HTMLPurifier_Token[]
*/
public function execute($tokens, $config, $context)
{
//####################################################################//
// Pre-processing
// O(n) pass to convert to a tree, so that we can efficiently
// refer to substrings
$top_node = HTMLPurifier_Arborize::arborize($tokens, $config, $context);
// get a copy of the HTML definition
$definition = $config->getHTMLDefinition();
$excludes_enabled = !$config->get('Core.DisableExcludes');
// setup the context variable 'IsInline', for chameleon processing
// is 'false' when we are not inline, 'true' when it must always
// be inline, and an integer when it is inline for a certain
// branch of the document tree
$is_inline = $definition->info_parent_def->descendants_are_inline;
$context->register('IsInline', $is_inline);
// setup error collector
$e =& $context->get('ErrorCollector', true);
//####################################################################//
// Loop initialization
// stack that contains all elements that are excluded
// it is organized by parent elements, similar to $stack,
// but it is only populated when an element with exclusions is
// processed, i.e. there won't be empty exclusions.
$exclude_stack = array($definition->info_parent_def->excludes);
// variable that contains the start token while we are processing
// nodes. This enables error reporting to do its job
$node = $top_node;
// dummy token
list($token, $d) = $node->toTokenPair();
$context->register('CurrentNode', $node);
$context->register('CurrentToken', $token);
//####################################################################//
// Loop
// We need to implement a post-order traversal iteratively, to
// avoid running into stack space limits. This is pretty tricky
// to reason about, so we just manually stack-ify the recursive
// variant:
//
// function f($node) {
// foreach ($node->children as $child) {
// f($child);
// }
// validate($node);
// }
//
// Thus, we will represent a stack frame as array($node,
// $is_inline, stack of children)
// e.g. array_reverse($node->children) - already processed
// children.
$parent_def = $definition->info_parent_def;
$stack = array(
array($top_node,
$parent_def->descendants_are_inline,
$parent_def->excludes, // exclusions
0)
);
while (!empty($stack)) {
list($node, $is_inline, $excludes, $ix) = array_pop($stack);
// recursive call
$go = false;
$def = empty($stack) ? $definition->info_parent_def : $definition->info[$node->name];
while (isset($node->children[$ix])) {
$child = $node->children[$ix++];
if ($child instanceof HTMLPurifier_Node_Element) {
$go = true;
$stack[] = array($node, $is_inline, $excludes, $ix);
$stack[] = array($child,
// ToDo: I don't think it matters if it's def or
// child_def, but double check this...
$is_inline || $def->descendants_are_inline,
empty($def->excludes) ? $excludes
: array_merge($excludes, $def->excludes),
0);
break;
}
};
if ($go) continue;
list($token, $d) = $node->toTokenPair();
// base case
if ($excludes_enabled && isset($excludes[$node->name])) {
$node->dead = true;
if ($e) $e->send(E_ERROR, 'Strategy_FixNesting: Node excluded');
} else {
// XXX I suppose it would be slightly more efficient to
// avoid the allocation here and have children
// strategies handle it
$children = array();
foreach ($node->children as $child) {
if (!$child->dead) $children[] = $child;
}
$result = $def->child->validateChildren($children, $config, $context);
if ($result === true) {
// nop
$node->children = $children;
} elseif ($result === false) {
$node->dead = true;
if ($e) $e->send(E_ERROR, 'Strategy_FixNesting: Node removed');
} else {
$node->children = $result;
if ($e) {
// XXX This will miss mutations of internal nodes. Perhaps defer to the child validators
if (empty($result) && !empty($children)) {
$e->send(E_ERROR, 'Strategy_FixNesting: Node contents removed');
} else if ($result != $children) {
$e->send(E_WARNING, 'Strategy_FixNesting: Node reorganized');
}
}
}
}
}
//####################################################################//
// Post-processing
// remove context variables
$context->destroy('IsInline');
$context->destroy('CurrentNode');
$context->destroy('CurrentToken');
//####################################################################//
// Return
return HTMLPurifier_Arborize::flatten($node, $config, $context);
}
}
// vim: et sw=4 sts=4