Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
0.00% covered (danger)
0.00%
0 / 138
0.00% covered (danger)
0.00%
0 / 13
CRAP
0.00% covered (danger)
0.00%
0 / 1
ActiveFormattingElements
0.00% covered (danger)
0.00%
0 / 138
0.00% covered (danger)
0.00%
0 / 13
3906
0.00% covered (danger)
0.00%
0 / 1
 __destruct
0.00% covered (danger)
0.00%
0 / 4
0.00% covered (danger)
0.00%
0 / 1
6
 insertMarker
0.00% covered (danger)
0.00%
0 / 7
0.00% covered (danger)
0.00%
0 / 1
6
 push
0.00% covered (danger)
0.00%
0 / 19
0.00% covered (danger)
0.00%
0 / 1
56
 clearToMarker
0.00% covered (danger)
0.00%
0 / 18
0.00% covered (danger)
0.00%
0 / 1
56
 findElementByName
0.00% covered (danger)
0.00%
0 / 6
0.00% covered (danger)
0.00%
0 / 1
20
 isInList
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
6
 remove
0.00% covered (danger)
0.00%
0 / 14
0.00% covered (danger)
0.00%
0 / 1
72
 addToNoahList
0.00% covered (danger)
0.00%
0 / 8
0.00% covered (danger)
0.00%
0 / 1
12
 removeFromNoahList
0.00% covered (danger)
0.00%
0 / 15
0.00% covered (danger)
0.00%
0 / 1
20
 replace
0.00% covered (danger)
0.00%
0 / 18
0.00% covered (danger)
0.00%
0 / 1
90
 insertAfter
0.00% covered (danger)
0.00%
0 / 12
0.00% covered (danger)
0.00%
0 / 1
42
 dump
0.00% covered (danger)
0.00%
0 / 15
0.00% covered (danger)
0.00%
0 / 1
56
 getTail
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
1<?php
2declare( strict_types = 1 );
3
4namespace Wikimedia\RemexHtml\TreeBuilder;
5
6use LogicException;
7
8/**
9 * The list of active formatting elements
10 */
11class ActiveFormattingElements {
12    /**
13     * The last (most recent) element in the list
14     *
15     * @var Marker|Element|null
16     */
17    private $tail;
18
19    /**
20     * The first (least recent) element in the list
21     *
22     * @var Marker|Element|null
23     */
24    private $head;
25
26    /**
27     * An array of arrays representing the population of elements in each bucket
28     * according to the Noah's Ark clause. The outer array is stack-like, with each
29     * integer-indexed element representing a segment of the list, bounded by
30     * markers. The first element represents the segment of the list before the
31     * first marker.
32     *
33     * The inner arrays are indexed by "Noah key", which is a string which uniquely
34     * identifies each bucket according to the rules in the spec. The value in
35     * the inner array is the first (least recently inserted) element in the bucket,
36     * and subsequent members of the bucket can be found by iterating through the
37     * singly-linked list via $node->nextNoah.
38     *
39     * This is optimised for the most common case of inserting into a bucket
40     * with zero members, and deleting a bucket containing one member. In the
41     * worst case, iteration through the list is still O(1) in the document
42     * size, since each bucket can have at most 3 members.
43     *
44     * @var array<int,array<string,Element|Marker>>
45     */
46    private $noahTableStack = [ [] ];
47
48    /**
49     * Manually unlink the doubly-linked list, since otherwise, it is not freed
50     * due to reference cycles.
51     */
52    public function __destruct() {
53        for ( $node = $this->head; $node; $node = $next ) {
54            $next = $node->nextAFE;
55            $node->prevAFE = $node->nextAFE = $node->nextNoah = null;
56        }
57        // @phan-suppress-next-line PhanTypeMismatchPropertyProbablyReal
58        $this->head = $this->tail = $this->noahTableStack = null;
59    }
60
61    /**
62     * Insert a marker
63     */
64    public function insertMarker() {
65        $elt = new Marker( 'marker' );
66        if ( $this->tail ) {
67            $this->tail->nextAFE = $elt;
68            $elt->prevAFE = $this->tail;
69        } else {
70            $this->head = $elt;
71        }
72        $this->tail = $elt;
73        $this->noahTableStack[] = [];
74    }
75
76    /**
77     * Follow the steps required when the spec requires us to "push onto the
78     * list of active formatting elements".
79     * @param Element $elt
80     */
81    public function push( Element $elt ) {
82        // Must not be in the list already
83        if ( $elt->prevAFE !== null || $this->head === $elt ) {
84            throw new LogicException( 'Cannot insert a node into the AFE list twice' );
85        }
86
87        // "Noah's Ark clause" -- if there are already three copies of
88        // this element before we encounter a marker, then drop the last
89        // one.
90        $noahKey = $elt->getNoahKey();
91        $table =& $this->noahTableStack[ array_key_last( $this->noahTableStack ) ];
92        if ( !isset( $table[$noahKey] ) ) {
93            $table[$noahKey] = $elt;
94        } else {
95            $count = 1;
96            $head = $tail = $table[$noahKey];
97            while ( $tail->nextNoah ) {
98                $tail = $tail->nextNoah;
99                $count++;
100            }
101            if ( $count >= 3 ) {
102                $this->remove( $head );
103            }
104            $tail->nextNoah = $elt;
105        }
106        // Add to the main AFE list
107        if ( $this->tail ) {
108            $this->tail->nextAFE = $elt;
109            $elt->prevAFE = $this->tail;
110        } else {
111            $this->head = $elt;
112        }
113        $this->tail = $elt;
114    }
115
116    /**
117     * Follow the steps required when the spec asks us to "clear the list of
118     * active formatting elements up to the last marker".
119     */
120    public function clearToMarker() {
121        // Iterate back through the list starting from the tail
122        $tail = $this->tail;
123        while ( $tail && !( $tail instanceof Marker ) ) {
124            // Unlink the element
125            $prev = $tail->prevAFE;
126            $tail->prevAFE = null;
127            if ( $prev ) {
128                $prev->nextAFE = null;
129            }
130            $tail->nextNoah = null;
131            $tail = $prev;
132        }
133        // If we finished on a marker, unlink it and pop it off the Noah table stack
134        if ( $tail ) {
135            $prev = $tail->prevAFE;
136            if ( $prev ) {
137                $prev->nextAFE = null;
138            }
139            $tail = $prev;
140            array_pop( $this->noahTableStack );
141        } else {
142            // No marker: wipe the top-level Noah table (which is the only one)
143            $this->noahTableStack[0] = [];
144        }
145        // If we removed all the elements, clear the head pointer
146        if ( !$tail ) {
147            $this->head = null;
148        }
149        $this->tail = $tail;
150    }
151
152    /**
153     * Find and return the last element with the specified name between the
154     * end of the list and the last marker on the list.
155     * Used when parsing <a> "in body mode".
156     * @param string $name
157     * @return Element|null
158     */
159    public function findElementByName( $name ) {
160        $elt = $this->tail;
161        while ( $elt && !( $elt instanceof Marker ) ) {
162            if ( $elt->htmlName === $name ) {
163                return $elt;
164            }
165            $elt = $elt->prevAFE;
166        }
167        return null;
168    }
169
170    /**
171     * Determine whether an element is in the list of formatting elements.
172     * @param Element $elt
173     * @return bool
174     */
175    public function isInList( Element $elt ) {
176        return $this->head === $elt || $elt->prevAFE;
177    }
178
179    /**
180     * Find the element $elt in the list and remove it.
181     * Used when parsing <a> in body mode.
182     *
183     * @param FormattingElement $elt
184     */
185    public function remove( FormattingElement $elt ) {
186        '@phan-var Marker|Element $elt'; /** @var Marker|Element $elt */
187        if ( $this->head !== $elt && !$elt->prevAFE ) {
188            throw new TreeBuilderError(
189                "Attempted to remove an element which is not in the AFE list" );
190        }
191        // Update head and tail pointers
192        if ( $this->head === $elt ) {
193            $this->head = $elt->nextAFE;
194        }
195        if ( $this->tail === $elt ) {
196            $this->tail = $elt->prevAFE;
197        }
198        // Update previous element
199        if ( $elt->prevAFE ) {
200            $elt->prevAFE->nextAFE = $elt->nextAFE;
201        }
202        // Update next element
203        if ( $elt->nextAFE ) {
204            $elt->nextAFE->prevAFE = $elt->prevAFE;
205        }
206        // Clear pointers so that isInList() etc. will work
207        $elt->prevAFE = $elt->nextAFE = null;
208        // Update Noah list
209        if ( $elt instanceof Element ) {
210            $this->removeFromNoahList( $elt );
211        }
212    }
213
214    /**
215     * Add an element to a bucket of elements which are alike for the purposes
216     * of the Noah's Ark clause.
217     *
218     * @param Element $elt
219     */
220    private function addToNoahList( Element $elt ) {
221        $noahKey = $elt->getNoahKey();
222        $table =& $this->noahTableStack[ array_key_last( $this->noahTableStack ) ];
223        if ( !isset( $table[$noahKey] ) ) {
224            $table[$noahKey] = $elt;
225        } else {
226            $tail = $table[$noahKey];
227            while ( $tail->nextNoah ) {
228                $tail = $tail->nextNoah;
229            }
230            $tail->nextNoah = $elt;
231        }
232    }
233
234    /**
235     * Remove an element from its Noah's Ark bucket.
236     *
237     * @param Element $elt
238     */
239    private function removeFromNoahList( Element $elt ) {
240        $table =& $this->noahTableStack[ array_key_last( $this->noahTableStack ) ];
241        $key = $elt->getNoahKey();
242        $noahElt = $table[$key];
243        if ( $noahElt === $elt ) {
244            if ( $noahElt->nextNoah ) {
245                $table[$key] = $noahElt->nextNoah;
246                $noahElt->nextNoah = null;
247            } else {
248                unset( $table[$key] );
249            }
250        } else {
251            do {
252                $prevNoahElt = $noahElt;
253                $noahElt = $prevNoahElt->nextNoah;
254                if ( $noahElt === $elt ) {
255                    // Found it, unlink
256                    $prevNoahElt->nextNoah = $elt->nextNoah;
257                    $elt->nextNoah = null;
258                    break;
259                }
260            } while ( $noahElt );
261        }
262    }
263
264    /**
265     * Find element $a in the list and replace it with element $b
266     *
267     * @param FormattingElement $a
268     * @param FormattingElement $b
269     */
270    public function replace( FormattingElement $a, FormattingElement $b ) {
271        '@phan-var Marker|Element $a'; /** @var Marker|Element $a */
272        '@phan-var Marker|Element $b'; /** @var Marker|Element $b */
273        if ( $this->head !== $a && !$a->prevAFE ) {
274            throw new TreeBuilderError(
275                "Attempted to replace an element which is not in the AFE list" );
276        }
277        // Update head and tail pointers
278        if ( $this->head === $a ) {
279            $this->head = $b;
280        }
281        if ( $this->tail === $a ) {
282            $this->tail = $b;
283        }
284        // Update previous element
285        if ( $a->prevAFE ) {
286            $a->prevAFE->nextAFE = $b;
287        }
288        // Update next element
289        if ( $a->nextAFE ) {
290            $a->nextAFE->prevAFE = $b;
291        }
292        $b->prevAFE = $a->prevAFE;
293        $b->nextAFE = $a->nextAFE;
294        $a->nextAFE = $a->prevAFE = null;
295        // Update Noah list
296        if ( $a instanceof Element ) {
297            $this->removeFromNoahList( $a );
298        }
299        if ( $b instanceof Element ) {
300            $this->addToNoahList( $b );
301        }
302    }
303
304    /**
305     * Find $a in the list and insert $b after it.
306     *
307     * @param FormattingElement $a
308     * @param FormattingElement $b
309     */
310    public function insertAfter( FormattingElement $a, FormattingElement $b ) {
311        '@phan-var Marker|Element $a'; /** @var Marker|Element $a */
312        '@phan-var Marker|Element $b'; /** @var Marker|Element $b */
313        if ( $this->head !== $a && !$a->prevAFE ) {
314            throw new TreeBuilderError(
315                "Attempted to insert after an element which is not in the AFE list" );
316        }
317        if ( $this->tail === $a ) {
318            $this->tail = $b;
319        }
320        if ( $a->nextAFE ) {
321            $a->nextAFE->prevAFE = $b;
322        }
323        $b->nextAFE = $a->nextAFE;
324        $b->prevAFE = $a;
325        $a->nextAFE = $b;
326        if ( $b instanceof Element ) {
327            $this->addToNoahList( $b );
328        }
329    }
330
331    /**
332     * Get a string representation of the AFE list, for debugging
333     * @return string
334     */
335    public function dump() {
336        $prev = null;
337        $s = '';
338        for ( $node = $this->head; $node; $prev = $node, $node = $node->nextAFE ) {
339            if ( $node instanceof Marker ) {
340                $s .= "MARKER\n";
341                continue;
342            }
343            /** @var Element $node */
344            $s .= $node->getDebugTag();
345            if ( $node->nextNoah instanceof Element ) {
346                $s .= " (noah sibling: " . $node->nextNoah->getDebugTag() . ')';
347            }
348            if ( $node->nextAFE instanceof Element && $node->nextAFE->prevAFE !== $node ) {
349                $s .= " (reverse link is wrong!)";
350            }
351            $s .= "\n";
352        }
353        if ( $prev !== $this->tail ) {
354            $s .= "(tail pointer is wrong!)\n";
355        }
356        return $s;
357    }
358
359    /**
360     * Get the most recently inserted element in the list
361     * @return Element|null
362     */
363    public function getTail() {
364        return $this->tail;
365    }
366}