<?php

namespace WPForms\Vendor;

/**
 * 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 separated (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
