1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
<?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
|
