← Back to branch summary

~ubuntu-branches/ubuntu/maverick/mahara/maverick-updates

« back to all changes in this revision

Viewing changes to htdocs/lib/htmlpurifier/HTMLPurifier/Strategy/FixNesting.php

  • Committer: Bazaar Package Importer
  • Author(s): Nigel McNie
  • Date: 2008-04-29 11:15:39 UTC
  • Revision ID: james.westby@ubuntu.com-20080429111539-b28eqkagavaub2zr
Tags: upstream-1.0.2
Import upstream version 1.0.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
htdocs/lib/htmlpurifier/HTMLPurifier/Strategy/FixNesting.php
 
1
<?php
 
2
 
 
3
require_once 'HTMLPurifier/Strategy.php';
 
4
require_once 'HTMLPurifier/HTMLDefinition.php';
 
5
 
 
6
/**
 
7
 * Takes a well formed list of tokens and fixes their nesting.
 
8
 * 
 
9
 * HTML elements dictate which elements are allowed to be their children,
 
10
 * for example, you can't have a p tag in a span tag.  Other elements have
 
11
 * much more rigorous definitions: tables, for instance, require a specific
 
12
 * order for their elements.  There are also constraints not expressible by
 
13
 * document type definitions, such as the chameleon nature of ins/del
 
14
 * tags and global child exclusions.
 
15
 * 
 
16
 * The first major objective of this strategy is to iterate through all the
 
17
 * nodes (not tokens) of the list of tokens and determine whether or not
 
18
 * their children conform to the element's definition.  If they do not, the
 
19
 * child definition may optionally supply an amended list of elements that
 
20
 * is valid or require that the entire node be deleted (and the previous
 
21
 * node rescanned).
 
22
 * 
 
23
 * The second objective is to ensure that explicitly excluded elements of
 
24
 * an element do not appear in its children.  Code that accomplishes this
 
25
 * task is pervasive through the strategy, though the two are distinct tasks
 
26
 * and could, theoretically, be seperated (although it's not recommended).
 
27
 * 
 
28
 * @note Whether or not unrecognized children are silently dropped or
 
29
 *       translated into text depends on the child definitions.
 
30
 * 
 
31
 * @todo Enable nodes to be bubbled out of the structure.
 
32
 */
 
33
 
 
34
class HTMLPurifier_Strategy_FixNesting extends HTMLPurifier_Strategy
 
35
{
 
36
    
 
37
    public function execute($tokens, $config, $context) {
 
38
        //####################################################################//
 
39
        // Pre-processing
 
40
        
 
41
        // get a copy of the HTML definition
 
42
        $definition = $config->getHTMLDefinition();
 
43
        
 
44
        // insert implicit "parent" node, will be removed at end.
 
45
        // DEFINITION CALL
 
46
        $parent_name = $definition->info_parent;
 
47
        array_unshift($tokens, new HTMLPurifier_Token_Start($parent_name));
 
48
        $tokens[] = new HTMLPurifier_Token_End($parent_name);
 
49
        
 
50
        // setup the context variable 'IsInline', for chameleon processing
 
51
        // is 'false' when we are not inline, 'true' when it must always
 
52
        // be inline, and an integer when it is inline for a certain
 
53
        // branch of the document tree
 
54
        $is_inline = $definition->info_parent_def->descendants_are_inline;
 
55
        $context->register('IsInline', $is_inline);
 
56
        
 
57
        // setup error collector
 
58
        $e =& $context->get('ErrorCollector', true);
 
59
        
 
60
        //####################################################################//
 
61
        // Loop initialization
 
62
        
 
63
        // stack that contains the indexes of all parents,
 
64
        // $stack[count($stack)-1] being the current parent
 
65
        $stack = array();
 
66
        
 
67
        // stack that contains all elements that are excluded
 
68
        // it is organized by parent elements, similar to $stack, 
 
69
        // but it is only populated when an element with exclusions is
 
70
        // processed, i.e. there won't be empty exclusions.
 
71
        $exclude_stack = array();
 
72
        
 
73
        // variable that contains the start token while we are processing
 
74
        // nodes. This enables error reporting to do its job
 
75
        $start_token = false;
 
76
        $context->register('CurrentToken', $start_token);
 
77
        
 
78
        //####################################################################//
 
79
        // Loop
 
80
        
 
81
        // iterate through all start nodes. Determining the start node
 
82
        // is complicated so it has been omitted from the loop construct
 
83
        for ($i = 0, $size = count($tokens) ; $i < $size; ) {
 
84
            
 
85
            //################################################################//
 
86
            // Gather information on children
 
87
            
 
88
            // child token accumulator
 
89
            $child_tokens = array();
 
90
            
 
91
            // scroll to the end of this node, report number, and collect
 
92
            // all children
 
93
            for ($j = $i, $depth = 0; ; $j++) {
 
94
                if ($tokens[$j]->type == 'start') {
 
95
                    $depth++;
 
96
                    // skip token assignment on first iteration, this is the
 
97
                    // token we currently are on
 
98
                    if ($depth == 1) continue;
 
99
                } elseif ($tokens[$j]->type == 'end') {
 
100
                    $depth--;
 
101
                    // skip token assignment on last iteration, this is the
 
102
                    // end token of the token we're currently on
 
103
                    if ($depth == 0) break;
 
104
                }
 
105
                $child_tokens[] = $tokens[$j];
 
106
            }
 
107
            
 
108
            // $i is index of start token
 
109
            // $j is index of end token
 
110
            
 
111
            $start_token = $tokens[$i]; // to make token available via CurrentToken
 
112
            
 
113
            //################################################################//
 
114
            // Gather information on parent
 
115
            
 
116
            // calculate parent information
 
117
            if ($count = count($stack)) {
 
118
                $parent_index = $stack[$count-1];
 
119
                $parent_name  = $tokens[$parent_index]->name;
 
120
                if ($parent_index == 0) {
 
121
                    $parent_def   = $definition->info_parent_def;
 
122
                } else {
 
123
                    $parent_def   = $definition->info[$parent_name];
 
124
                }
 
125
            } else {
 
126
                // processing as if the parent were the "root" node
 
127
                // unknown info, it won't be used anyway, in the future,
 
128
                // we may want to enforce one element only (this is 
 
129
                // necessary for HTML Purifier to clean entire documents
 
130
                $parent_index = $parent_name = $parent_def = null;
 
131
            }
 
132
            
 
133
            // calculate context
 
134
            if ($is_inline === false) {
 
135
                // check if conditions make it inline
 
136
                if (!empty($parent_def) && $parent_def->descendants_are_inline) {
 
137
                    $is_inline = $count - 1;
 
138
                }
 
139
            } else {
 
140
                // check if we're out of inline
 
141
                if ($count === $is_inline) {
 
142
                    $is_inline = false;
 
143
                }
 
144
            }
 
145
            
 
146
            //################################################################//
 
147
            // Determine whether element is explicitly excluded SGML-style
 
148
            
 
149
            // determine whether or not element is excluded by checking all
 
150
            // parent exclusions. The array should not be very large, two
 
151
            // elements at most.
 
152
            $excluded = false;
 
153
            if (!empty($exclude_stack)) {
 
154
                foreach ($exclude_stack as $lookup) {
 
155
                    if (isset($lookup[$tokens[$i]->name])) {
 
156
                        $excluded = true;
 
157
                        // no need to continue processing
 
158
                        break;
 
159
                    }
 
160
                }
 
161
            }
 
162
            
 
163
            //################################################################//
 
164
            // Perform child validation
 
165
            
 
166
            if ($excluded) {
 
167
                // there is an exclusion, remove the entire node
 
168
                $result = false;
 
169
                $excludes = array(); // not used, but good to initialize anyway
 
170
            } else {
 
171
                // DEFINITION CALL
 
172
                if ($i === 0) {
 
173
                    // special processing for the first node
 
174
                    $def = $definition->info_parent_def;
 
175
                } else {
 
176
                    $def = $definition->info[$tokens[$i]->name];
 
177
                    
 
178
                }
 
179
                
 
180
                if (!empty($def->child)) {
 
181
                    // have DTD child def validate children
 
182
                    $result = $def->child->validateChildren(
 
183
                        $child_tokens, $config, $context);
 
184
                } else {
 
185
                    // weird, no child definition, get rid of everything
 
186
                    $result = false;
 
187
                }
 
188
                
 
189
                // determine whether or not this element has any exclusions
 
190
                $excludes = $def->excludes;
 
191
            }
 
192
            
 
193
            // $result is now a bool or array
 
194
            
 
195
            //################################################################//
 
196
            // Process result by interpreting $result
 
197
            
 
198
            if ($result === true || $child_tokens === $result) {
 
199
                // leave the node as is
 
200
                
 
201
                // register start token as a parental node start
 
202
                $stack[] = $i;
 
203
                
 
204
                // register exclusions if there are any
 
205
                if (!empty($excludes)) $exclude_stack[] = $excludes;
 
206
                
 
207
                // move cursor to next possible start node
 
208
                $i++;
 
209
                
 
210
            } elseif($result === false) {
 
211
                // remove entire node
 
212
                
 
213
                if ($e) {
 
214
                    if ($excluded) {
 
215
                        $e->send(E_ERROR, 'Strategy_FixNesting: Node excluded');
 
216
                    } else {
 
217
                        $e->send(E_ERROR, 'Strategy_FixNesting: Node removed');
 
218
                    }
 
219
                }
 
220
                
 
221
                // calculate length of inner tokens and current tokens
 
222
                $length = $j - $i + 1;
 
223
                
 
224
                // perform removal
 
225
                array_splice($tokens, $i, $length);
 
226
                
 
227
                // update size
 
228
                $size -= $length;
 
229
                
 
230
                // there is no start token to register,
 
231
                // current node is now the next possible start node
 
232
                // unless it turns out that we need to do a double-check
 
233
                
 
234
                // this is a rought heuristic that covers 100% of HTML's
 
235
                // cases and 99% of all other cases. A child definition
 
236
                // that would be tricked by this would be something like:
 
237
                // ( | a b c) where it's all or nothing. Fortunately,
 
238
                // our current implementation claims that that case would
 
239
                // not allow empty, even if it did
 
240
                if (!$parent_def->child->allow_empty) {
 
241
                    // we need to do a double-check
 
242
                    $i = $parent_index;
 
243
                    array_pop($stack);
 
244
                }
 
245
                
 
246
                // PROJECTED OPTIMIZATION: Process all children elements before
 
247
                // reprocessing parent node.
 
248
                
 
249
            } else {
 
250
                // replace node with $result
 
251
                
 
252
                // calculate length of inner tokens
 
253
                $length = $j - $i - 1;
 
254
                
 
255
                if ($e) {
 
256
                    if (empty($result) && $length) {
 
257
                        $e->send(E_ERROR, 'Strategy_FixNesting: Node contents removed');
 
258
                    } else {
 
259
                        $e->send(E_WARNING, 'Strategy_FixNesting: Node reorganized');
 
260
                    }
 
261
                }
 
262
                
 
263
                // perform replacement
 
264
                array_splice($tokens, $i + 1, $length, $result);
 
265
                
 
266
                // update size
 
267
                $size -= $length;
 
268
                $size += count($result);
 
269
                
 
270
                // register start token as a parental node start
 
271
                $stack[] = $i;
 
272
                
 
273
                // register exclusions if there are any
 
274
                if (!empty($excludes)) $exclude_stack[] = $excludes;
 
275
                
 
276
                // move cursor to next possible start node
 
277
                $i++;
 
278
                
 
279
            }
 
280
            
 
281
            //################################################################//
 
282
            // Scroll to next start node
 
283
            
 
284
            // We assume, at this point, that $i is the index of the token
 
285
            // that is the first possible new start point for a node.
 
286
            
 
287
            // Test if the token indeed is a start tag, if not, move forward
 
288
            // and test again.
 
289
            $size = count($tokens);
 
290
            while ($i < $size and $tokens[$i]->type != 'start') {
 
291
                if ($tokens[$i]->type == 'end') {
 
292
                    // pop a token index off the stack if we ended a node
 
293
                    array_pop($stack);
 
294
                    // pop an exclusion lookup off exclusion stack if
 
295
                    // we ended node and that node had exclusions
 
296
                    if ($i == 0 || $i == $size - 1) {
 
297
                        // use specialized var if it's the super-parent
 
298
                        $s_excludes = $definition->info_parent_def->excludes;
 
299
                    } else {
 
300
                        $s_excludes = $definition->info[$tokens[$i]->name]->excludes;
 
301
                    }
 
302
                    if ($s_excludes) {
 
303
                        array_pop($exclude_stack);
 
304
                    }
 
305
                }
 
306
                $i++;
 
307
            }
 
308
            
 
309
        }
 
310
        
 
311
        //####################################################################//
 
312
        // Post-processing
 
313
        
 
314
        // remove implicit parent tokens at the beginning and end
 
315
        array_shift($tokens);
 
316
        array_pop($tokens);
 
317
        
 
318
        // remove context variables
 
319
        $context->destroy('IsInline');
 
320
        $context->destroy('CurrentToken');
 
321
        
 
322
        //####################################################################//
 
323
        // Return
 
324
        
 
325
        return $tokens;
 
326
        
 
327
    }
 
328
    
 
329
}
 
330
 
 
331