--- /dev/null
+<?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
projects / yaffs-website / blobdiff