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