Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
88.71%
55 / 62
76.92%
10 / 13
 CRAP
0.00%
0 / 1
ActiveFormattingElements
88.71%
55 / 62
76.92%
10 / 13
 44.54
0.00%
0 / 1
 push
100.00%
12 / 12
100.00%
1 / 1
 5
 elementsMatchForNoahsArk
100.00%
14 / 14
100.00%
1 / 1
 9
 pushMarker
100.00%
1 / 1
100.00%
1 / 1
 1
 clearToLastMarker
100.00%
4 / 4
100.00%
1 / 1
 3
 isEmpty
0.00%
0 / 1
0.00%
0 / 1
 2
 entries
100.00%
1 / 1
100.00%
1 / 1
 1
 contains
100.00%
4 / 4
100.00%
1 / 1
 3
 remove
100.00%
4 / 4
100.00%
1 / 1
 3
 replace
100.00%
4 / 4
100.00%
1 / 1
 3
 indexOf
75.00%
3 / 4
0.00%
0 / 1
 3.14
 insertAt
100.00%
1 / 1
100.00%
1 / 1
 1
 findLastBetweenMarkerAnd
100.00%
7 / 7
100.00%
1 / 1
 5
 lastElement
0.00%
0 / 5
0.00%
0 / 1
 20
1<?php
2
3declare(strict_types=1);
4
5namespace Phpdftk\Html\TreeConstruction;
6
7use Phpdftk\Html\Dom\Element;
8
9/**
10 * List of active formatting elements per WHATWG §13.2.4.3.
11 *
12 * Stores Element entries plus null sentinels ("markers") inserted at
13 * applet/object/marquee/template scope boundaries. The list is what makes
14 * the adoption agency algorithm work — it lets the tree builder remember
15 * which formatting elements (b, i, code, etc.) are "active" but possibly
16 * mis-nested with respect to the open-elements stack.
17 *
18 * Phase 1B.3 ships the data-structure operations; the full reconstruction
19 * loop (which materialises formatting elements onto the open-elements stack
20 * after they get popped by an unrelated end tag) is implemented as part of
21 * TreeBuilder so it has access to the insertion algorithms.
22 */
23final class ActiveFormattingElements
24{
25    /**
26     * Entries are either Element (for an active formatting element) or null
27     * (for a marker).
28     *
29     * @var list<?Element>
30     */
31    private array $entries = [];
32
33    public function push(Element $element): void
34    {
35        // Noah's Ark clause per WHATWG §13.2.4.3: if three entries already
36        // exist between the last marker (or list start) and the end that
37        // have the same tag name, namespace, and attribute set, remove the
38        // earliest. This prevents O(N^2) blowups on pathological input like
39        // `<b><b><b>...<b>`.
40        $matches = [];
41        for ($i = count($this->entries) - 1; $i >= 0; $i--) {
42            $entry = $this->entries[$i];
43            if ($entry === null) {
44                break; // hit a marker
45            }
46            if ($this->elementsMatchForNoahsArk($entry, $element)) {
47                $matches[] = $i;
48                if (count($matches) >= 3) {
49                    // Remove the earliest of the three.
50                    $earliest = $matches[count($matches) - 1];
51                    array_splice($this->entries, $earliest, 1);
52                    break;
53                }
54            }
55        }
56        $this->entries[] = $element;
57    }
58
59    /**
60     * Two elements match for the Noah's Ark clause iff: same local name,
61     * same namespace, and identical attribute sets (name → value).
62     */
63    private function elementsMatchForNoahsArk(Element $a, Element $b): bool
64    {
65        if ($a->localName !== $b->localName || $a->namespaceURI !== $b->namespaceURI) {
66            return false;
67        }
68        $attrsA = [];
69        foreach ($a->attributes() as $attr) {
70            $attrsA[$attr->qualifiedName()] = $attr->value;
71        }
72        $attrsB = [];
73        foreach ($b->attributes() as $attr) {
74            $attrsB[$attr->qualifiedName()] = $attr->value;
75        }
76        if (count($attrsA) !== count($attrsB)) {
77            return false;
78        }
79        foreach ($attrsA as $name => $value) {
80            if (!array_key_exists($name, $attrsB) || $attrsB[$name] !== $value) {
81                return false;
82            }
83        }
84        return true;
85    }
86
87    public function pushMarker(): void
88    {
89        $this->entries[] = null;
90    }
91
92    public function clearToLastMarker(): void
93    {
94        while ($this->entries !== []) {
95            $popped = array_pop($this->entries);
96            if ($popped === null) {
97                return;
98            }
99        }
100    }
101
102    public function isEmpty(): bool
103    {
104        return $this->entries === [];
105    }
106
107    /** @return list<?Element> */
108    public function entries(): array
109    {
110        return $this->entries;
111    }
112
113    public function contains(Element $element): bool
114    {
115        foreach ($this->entries as $entry) {
116            if ($entry === $element) {
117                return true;
118            }
119        }
120        return false;
121    }
122
123    public function remove(Element $element): void
124    {
125        foreach ($this->entries as $i => $entry) {
126            if ($entry === $element) {
127                array_splice($this->entries, $i, 1);
128                return;
129            }
130        }
131    }
132
133    public function replace(Element $old, Element $new): void
134    {
135        foreach ($this->entries as $i => $entry) {
136            if ($entry === $old) {
137                $this->entries[$i] = $new;
138                return;
139            }
140        }
141    }
142
143    public function indexOf(Element $element): ?int
144    {
145        foreach ($this->entries as $i => $entry) {
146            if ($entry === $element) {
147                return $i;
148            }
149        }
150        return null;
151    }
152
153    public function insertAt(int $index, Element $element): void
154    {
155        array_splice($this->entries, $index, 0, [$element]);
156    }
157
158    /**
159     * Find the last element entry between the end of the list and the most
160     * recent marker (or the start) whose local name matches. Returns null if
161     * no match.
162     */
163    public function findLastBetweenMarkerAnd(string $localName): ?Element
164    {
165        for ($i = array_key_last($this->entries); $i !== null && $i >= 0; $i--) {
166            $entry = $this->entries[$i];
167            if ($entry === null) {
168                return null; // hit a marker
169            }
170            if ($entry->localName === $localName) {
171                return $entry;
172            }
173        }
174        return null;
175    }
176
177    /** Last entry that is an Element (skip trailing markers). */
178    public function lastElement(): ?Element
179    {
180        for ($i = array_key_last($this->entries); $i !== null && $i >= 0; $i--) {
181            $entry = $this->entries[$i];
182            if ($entry !== null) {
183                return $entry;
184            }
185        }
186        return null;
187    }
188}