Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
| Total | |
0.00% |
0 / 138 |
|
0.00% |
0 / 13 |
CRAP | |
0.00% |
0 / 1 |
| ActiveFormattingElements | |
0.00% |
0 / 138 |
|
0.00% |
0 / 13 |
3906 | |
0.00% |
0 / 1 |
| __destruct | |
0.00% |
0 / 4 |
|
0.00% |
0 / 1 |
6 | |||
| insertMarker | |
0.00% |
0 / 7 |
|
0.00% |
0 / 1 |
6 | |||
| push | |
0.00% |
0 / 19 |
|
0.00% |
0 / 1 |
56 | |||
| clearToMarker | |
0.00% |
0 / 18 |
|
0.00% |
0 / 1 |
56 | |||
| findElementByName | |
0.00% |
0 / 6 |
|
0.00% |
0 / 1 |
20 | |||
| isInList | |
0.00% |
0 / 1 |
|
0.00% |
0 / 1 |
6 | |||
| remove | |
0.00% |
0 / 14 |
|
0.00% |
0 / 1 |
72 | |||
| addToNoahList | |
0.00% |
0 / 8 |
|
0.00% |
0 / 1 |
12 | |||
| removeFromNoahList | |
0.00% |
0 / 15 |
|
0.00% |
0 / 1 |
20 | |||
| replace | |
0.00% |
0 / 18 |
|
0.00% |
0 / 1 |
90 | |||
| insertAfter | |
0.00% |
0 / 12 |
|
0.00% |
0 / 1 |
42 | |||
| dump | |
0.00% |
0 / 15 |
|
0.00% |
0 / 1 |
56 | |||
| getTail | |
0.00% |
0 / 1 |
|
0.00% |
0 / 1 |
2 | |||
| 1 | <?php |
| 2 | declare( strict_types = 1 ); |
| 3 | |
| 4 | namespace Wikimedia\RemexHtml\TreeBuilder; |
| 5 | |
| 6 | use LogicException; |
| 7 | |
| 8 | /** |
| 9 | * The list of active formatting elements |
| 10 | */ |
| 11 | class 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 | } |