<?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