1/*
2 * Copyright (C) 2004 Allan Sandfeld Jensen (kde@carewolf.com)
3 * Copyright (C) 2006-2018 Apple Inc. All rights reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB. If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22#include "config.h"
23#include "RenderCounter.h"
24
25#include "CounterNode.h"
26#include "Document.h"
27#include "Element.h"
28#include "ElementTraversal.h"
29#include "HTMLNames.h"
30#include "HTMLOListElement.h"
31#include "PseudoElement.h"
32#include "RenderListItem.h"
33#include "RenderListMarker.h"
34#include "RenderStyle.h"
35#include "RenderView.h"
36#include <wtf/IsoMallocInlines.h>
37#include <wtf/StdLibExtras.h>
38
39#if ENABLE(TREE_DEBUGGING)
40#include <stdio.h>
41#endif
42
43namespace WebCore {
44
45using namespace HTMLNames;
46
47WTF_MAKE_ISO_ALLOCATED_IMPL(RenderCounter);
48
49using CounterMap = HashMap<AtomicString, Ref<CounterNode>>;
50using CounterMaps = HashMap<const RenderElement*, std::unique_ptr<CounterMap>>;
51
52static CounterNode* makeCounterNode(RenderElement&, const AtomicString& identifier, bool alwaysCreateCounter);
53
54static CounterMaps& counterMaps()
55{
56 static NeverDestroyed<CounterMaps> staticCounterMaps;
57 return staticCounterMaps;
58}
59
60// This function processes the renderer tree in the order of the DOM tree
61// including pseudo elements as defined in CSS 2.1.
62static RenderElement* previousInPreOrder(const RenderElement& renderer)
63{
64 ASSERT(renderer.element());
65 Element* previous = ElementTraversal::previousIncludingPseudo(*renderer.element());
66 while (previous && !previous->renderer())
67 previous = ElementTraversal::previousIncludingPseudo(*previous);
68 return previous ? previous->renderer() : 0;
69}
70
71static inline Element* parentOrPseudoHostElement(const RenderElement& renderer)
72{
73 if (renderer.isPseudoElement())
74 return renderer.generatingElement();
75 return renderer.element() ? renderer.element()->parentElement() : nullptr;
76}
77
78// This function processes the renderer tree in the order of the DOM tree
79// including pseudo elements as defined in CSS 2.1.
80static RenderElement* previousSiblingOrParent(const RenderElement& renderer)
81{
82 ASSERT(renderer.element());
83 Element* previous = ElementTraversal::pseudoAwarePreviousSibling(*renderer.element());
84 while (previous && !previous->renderer())
85 previous = ElementTraversal::pseudoAwarePreviousSibling(*previous);
86 if (previous)
87 return previous->renderer();
88 previous = parentOrPseudoHostElement(renderer);
89 return previous ? previous->renderer() : nullptr;
90}
91
92static inline bool areRenderersElementsSiblings(const RenderElement& first, const RenderElement& second)
93{
94 return parentOrPseudoHostElement(first) == parentOrPseudoHostElement(second);
95}
96
97// This function processes the renderer tree in the order of the DOM tree
98// including pseudo elements as defined in CSS 2.1.
99static RenderElement* nextInPreOrder(const RenderElement& renderer, const Element* stayWithin, bool skipDescendants = false)
100{
101 ASSERT(renderer.element());
102 Element& self = *renderer.element();
103 Element* next = skipDescendants ? ElementTraversal::nextIncludingPseudoSkippingChildren(self, stayWithin) : ElementTraversal::nextIncludingPseudo(self, stayWithin);
104 while (next && !next->renderer())
105 next = skipDescendants ? ElementTraversal::nextIncludingPseudoSkippingChildren(*next, stayWithin) : ElementTraversal::nextIncludingPseudo(*next, stayWithin);
106 return next ? next->renderer() : nullptr;
107}
108
109static CounterDirectives listItemCounterDirectives(RenderElement& renderer)
110{
111 if (is<RenderListItem>(renderer)) {
112 auto& item = downcast<RenderListItem>(renderer);
113 if (auto explicitValue = item.explicitValue())
114 return { *explicitValue, WTF::nullopt };
115 return { WTF::nullopt, item.isInReversedOrderedList() ? -1 : 1 };
116 }
117 if (auto element = renderer.element()) {
118 if (is<HTMLOListElement>(*element)) {
119 auto& list = downcast<HTMLOListElement>(*element);
120 return { list.start(), list.isReversed() ? 1 : -1 };
121 }
122 if (isHTMLListElement(*element))
123 return { 0, WTF::nullopt };
124 }
125 return { };
126}
127
128struct CounterPlan {
129 bool isReset;
130 int value;
131};
132
133static Optional<CounterPlan> planCounter(RenderElement& renderer, const AtomicString& identifier)
134{
135 // We must have a generating node or else we cannot have a counter.
136 Element* generatingElement = renderer.generatingElement();
137 if (!generatingElement)
138 return WTF::nullopt;
139
140 auto& style = renderer.style();
141
142 switch (style.styleType()) {
143 case PseudoId::None:
144 // Sometimes elements have more then one renderer. Only the first one gets the counter
145 // LayoutTests/http/tests/css/counter-crash.html
146 if (generatingElement->renderer() != &renderer)
147 return WTF::nullopt;
148 break;
149 case PseudoId::Before:
150 case PseudoId::After:
151 break;
152 default:
153 return WTF::nullopt; // Counters are forbidden from all other pseudo elements.
154 }
155
156 CounterDirectives directives;
157
158 if (auto map = style.counterDirectives())
159 directives = map->get(identifier);
160
161 if (identifier == "list-item") {
162 auto itemDirectives = listItemCounterDirectives(renderer);
163 if (!directives.resetValue)
164 directives.resetValue = itemDirectives.resetValue;
165 if (!directives.incrementValue)
166 directives.incrementValue = itemDirectives.incrementValue;
167 }
168
169 if (directives.resetValue)
170 return CounterPlan { true, saturatedAddition(*directives.resetValue, directives.incrementValue.valueOr(0)) };
171 if (directives.incrementValue)
172 return CounterPlan { false, *directives.incrementValue };
173 return WTF::nullopt;
174}
175
176// - Finds the insertion point for the counter described by counterOwner, isReset and
177// identifier in the CounterNode tree for identifier and sets parent and
178// previousSibling accordingly.
179// - The function returns true if the counter whose insertion point is searched is NOT
180// the root of the tree.
181// - The root of the tree is a counter reference that is not in the scope of any other
182// counter with the same identifier.
183// - All the counter references with the same identifier as this one that are in
184// children or subsequent siblings of the renderer that owns the root of the tree
185// form the rest of of the nodes of the tree.
186// - The root of the tree is always a reset type reference.
187// - A subtree rooted at any reset node in the tree is equivalent to all counter
188// references that are in the scope of the counter or nested counter defined by that
189// reset node.
190// - Non-reset CounterNodes cannot have descendants.
191
192struct CounterInsertionPoint {
193 RefPtr<CounterNode> parent;
194 RefPtr<CounterNode> previousSibling;
195};
196
197static CounterInsertionPoint findPlaceForCounter(RenderElement& counterOwner, const AtomicString& identifier, bool isReset)
198{
199 // We cannot stop searching for counters with the same identifier before we also
200 // check this renderer, because it may affect the positioning in the tree of our counter.
201 RenderElement* searchEndRenderer = previousSiblingOrParent(counterOwner);
202 // We check renderers in preOrder from the renderer that our counter is attached to
203 // towards the begining of the document for counters with the same identifier as the one
204 // we are trying to find a place for. This is the next renderer to be checked.
205 RenderElement* currentRenderer = previousInPreOrder(counterOwner);
206 RefPtr<CounterNode> previousSibling;
207
208 while (currentRenderer) {
209 auto currentCounter = makeCounterNode(*currentRenderer, identifier, false);
210 if (searchEndRenderer == currentRenderer) {
211 // We may be at the end of our search.
212 if (currentCounter) {
213 // We have a suitable counter on the EndSearchRenderer.
214 if (previousSibling) {
215 // But we already found another counter that we come after.
216 if (currentCounter->actsAsReset()) {
217 // We found a reset counter that is on a renderer that is a sibling of ours or a parent.
218 if (isReset && areRenderersElementsSiblings(*currentRenderer, counterOwner)) {
219 // We are also a reset counter and the previous reset was on a sibling renderer
220 // hence we are the next sibling of that counter if that reset is not a root or
221 // we are a root node if that reset is a root.
222 auto* parent = currentCounter->parent();
223 return { parent, parent ? currentCounter : nullptr };
224 }
225 // We are not a reset node or the previous reset must be on an ancestor of our owner renderer
226 // hence we must be a child of that reset counter.
227 // In some cases renders can be reparented (ex. nodes inside a table but not in a column or row).
228 // In these cases the identified previousSibling will be invalid as its parent is different from
229 // our identified parent.
230 if (previousSibling->parent() != currentCounter)
231 previousSibling = nullptr;
232 return { currentCounter, WTFMove(previousSibling) };
233 }
234 // CurrentCounter, the counter at the EndSearchRenderer, is not reset.
235 if (!isReset || !areRenderersElementsSiblings(*currentRenderer, counterOwner)) {
236 // If the node we are placing is not reset or we have found a counter that is attached
237 // to an ancestor of the placed counter's owner renderer we know we are a sibling of that node.
238 if (currentCounter->parent() != previousSibling->parent())
239 return { };
240 return { currentCounter->parent(), WTFMove(previousSibling) };
241 }
242 } else {
243 // We are at the potential end of the search, but we had no previous sibling candidate
244 // In this case we follow pretty much the same logic as above but no ASSERTs about
245 // previousSibling, and when we are a sibling of the end counter we must set previousSibling
246 // to currentCounter.
247 if (currentCounter->actsAsReset()) {
248 if (isReset && areRenderersElementsSiblings(*currentRenderer, counterOwner))
249 return { currentCounter->parent(), currentCounter };
250 return { currentCounter, WTFMove(previousSibling) };
251 }
252 if (!isReset || !areRenderersElementsSiblings(*currentRenderer, counterOwner))
253 return { currentCounter->parent(), currentCounter };
254 previousSibling = currentCounter;
255 }
256 }
257 // We come here if the previous sibling or parent of our owner renderer had no
258 // good counter, or we are a reset node and the counter on the previous sibling
259 // of our owner renderer was not a reset counter.
260 // Set a new goal for the end of the search.
261 searchEndRenderer = previousSiblingOrParent(*currentRenderer);
262 } else {
263 // We are searching descendants of a previous sibling of the renderer that the
264 // counter being placed is attached to.
265 if (currentCounter) {
266 // We found a suitable counter.
267 if (previousSibling) {
268 // Since we had a suitable previous counter before, we should only consider this one as our
269 // previousSibling if it is a reset counter and hence the current previousSibling is its child.
270 if (currentCounter->actsAsReset()) {
271 previousSibling = currentCounter;
272 // We are no longer interested in previous siblings of the currentRenderer or their children
273 // as counters they may have attached cannot be the previous sibling of the counter we are placing.
274 currentRenderer = parentOrPseudoHostElement(*currentRenderer)->renderer();
275 continue;
276 }
277 } else
278 previousSibling = currentCounter;
279 currentRenderer = previousSiblingOrParent(*currentRenderer);
280 continue;
281 }
282 }
283 // This function is designed so that the same test is not done twice in an iteration, except for this one
284 // which may be done twice in some cases. Rearranging the decision points though, to accommodate this
285 // performance improvement would create more code duplication than is worthwhile in my oppinion and may further
286 // impede the readability of this already complex algorithm.
287 if (previousSibling)
288 currentRenderer = previousSiblingOrParent(*currentRenderer);
289 else
290 currentRenderer = previousInPreOrder(*currentRenderer);
291 }
292 return { };
293}
294
295static CounterNode* makeCounterNode(RenderElement& renderer, const AtomicString& identifier, bool alwaysCreateCounter)
296{
297 if (renderer.hasCounterNodeMap()) {
298 ASSERT(counterMaps().contains(&renderer));
299 if (auto* node = counterMaps().find(&renderer)->value->get(identifier))
300 return node;
301 }
302
303 auto plan = planCounter(renderer, identifier);
304 if (!plan && !alwaysCreateCounter)
305 return nullptr;
306
307 auto& maps = counterMaps();
308
309 auto newNode = CounterNode::create(renderer, plan && plan->isReset, plan ? plan->value : 0);
310
311 auto place = findPlaceForCounter(renderer, identifier, plan && plan->isReset);
312 if (place.parent)
313 place.parent->insertAfter(newNode, place.previousSibling.get(), identifier);
314
315 maps.add(&renderer, std::make_unique<CounterMap>()).iterator->value->add(identifier, newNode.copyRef());
316 renderer.setHasCounterNodeMap(true);
317
318 if (newNode->parent())
319 return newNode.ptr();
320
321 // Check if some nodes that were previously root nodes should become children of this node now.
322 auto* currentRenderer = &renderer;
323 auto* stayWithin = parentOrPseudoHostElement(renderer);
324 bool skipDescendants = false;
325 while ((currentRenderer = nextInPreOrder(*currentRenderer, stayWithin, skipDescendants))) {
326 skipDescendants = false;
327 if (!currentRenderer->hasCounterNodeMap())
328 continue;
329 auto* currentCounter = maps.find(currentRenderer)->value->get(identifier);
330 if (!currentCounter)
331 continue;
332 skipDescendants = true;
333 if (currentCounter->parent())
334 continue;
335 if (stayWithin == parentOrPseudoHostElement(*currentRenderer) && currentCounter->hasResetType())
336 break;
337 newNode->insertAfter(*currentCounter, newNode->lastChild(), identifier);
338 }
339
340 return newNode.ptr();
341}
342
343RenderCounter::RenderCounter(Document& document, const CounterContent& counter)
344 : RenderText(document, emptyString())
345 , m_counter(counter)
346{
347 view().addRenderCounter();
348}
349
350RenderCounter::~RenderCounter()
351{
352 // Do not add any code here. Add it to willBeDestroyed() instead.
353}
354
355void RenderCounter::willBeDestroyed()
356{
357 view().removeRenderCounter();
358
359 if (m_counterNode) {
360 m_counterNode->removeRenderer(*this);
361 ASSERT(!m_counterNode);
362 }
363
364 RenderText::willBeDestroyed();
365}
366
367const char* RenderCounter::renderName() const
368{
369 return "RenderCounter";
370}
371
372bool RenderCounter::isCounter() const
373{
374 return true;
375}
376
377String RenderCounter::originalText() const
378{
379 if (!m_counterNode) {
380 RenderElement* beforeAfterContainer = parent();
381 while (true) {
382 if (!beforeAfterContainer)
383 return String();
384 if (!beforeAfterContainer->isAnonymous() && !beforeAfterContainer->isPseudoElement())
385 return String(); // RenderCounters are restricted to before and after pseudo elements
386 PseudoId containerStyle = beforeAfterContainer->style().styleType();
387 if ((containerStyle == PseudoId::Before) || (containerStyle == PseudoId::After))
388 break;
389 beforeAfterContainer = beforeAfterContainer->parent();
390 }
391 makeCounterNode(*beforeAfterContainer, m_counter.identifier(), true)->addRenderer(const_cast<RenderCounter&>(*this));
392 ASSERT(m_counterNode);
393 }
394 CounterNode* child = m_counterNode;
395 int value = child->actsAsReset() ? child->value() : child->countInParent();
396
397 String text = listMarkerText(m_counter.listStyle(), value);
398
399 if (!m_counter.separator().isNull()) {
400 if (!child->actsAsReset())
401 child = child->parent();
402 while (CounterNode* parent = child->parent()) {
403 text = listMarkerText(m_counter.listStyle(), child->countInParent())
404 + m_counter.separator() + text;
405 child = parent;
406 }
407 }
408
409 return text;
410}
411
412void RenderCounter::updateCounter()
413{
414 computePreferredLogicalWidths(0);
415}
416
417void RenderCounter::computePreferredLogicalWidths(float lead)
418{
419#ifndef NDEBUG
420 // FIXME: We shouldn't be modifying the tree in computePreferredLogicalWidths.
421 // Instead, we should properly hook the appropriate changes in the DOM and modify
422 // the render tree then. When that's done, we also won't need to override
423 // computePreferredLogicalWidths at all.
424 // https://bugs.webkit.org/show_bug.cgi?id=104829
425 SetLayoutNeededForbiddenScope layoutForbiddenScope(this, false);
426#endif
427
428 setRenderedText(originalText());
429
430 RenderText::computePreferredLogicalWidths(lead);
431}
432
433static void destroyCounterNodeWithoutMapRemoval(const AtomicString& identifier, CounterNode& node)
434{
435 RefPtr<CounterNode> previous;
436 for (RefPtr<CounterNode> child = node.lastDescendant(); child && child != &node; child = WTFMove(previous)) {
437 previous = child->previousInPreOrder();
438 child->parent()->removeChild(*child);
439 ASSERT(counterMaps().find(&child->owner())->value->get(identifier) == child);
440 counterMaps().find(&child->owner())->value->remove(identifier);
441 }
442 if (auto* parent = node.parent())
443 parent->removeChild(node);
444}
445
446void RenderCounter::destroyCounterNodes(RenderElement& owner)
447{
448 ASSERT(owner.hasCounterNodeMap());
449 auto& maps = counterMaps();
450 ASSERT(maps.contains(&owner));
451 auto counterMap = maps.take(&owner);
452 for (auto& counterMapEntry : *counterMap)
453 destroyCounterNodeWithoutMapRemoval(counterMapEntry.key, counterMapEntry.value);
454 owner.setHasCounterNodeMap(false);
455}
456
457void RenderCounter::destroyCounterNode(RenderElement& owner, const AtomicString& identifier)
458{
459 auto map = counterMaps().find(&owner);
460 if (map == counterMaps().end())
461 return;
462 auto node = map->value->take(identifier);
463 if (!node)
464 return;
465 destroyCounterNodeWithoutMapRemoval(identifier, *node);
466 // We do not delete the map here even if it is now empty because we expect to
467 // reuse it. In order for a renderer to lose all its counters permanently,
468 // a style change for the renderer involving removal of all counter
469 // directives must occur, in which case, RenderCounter::destroyCounterNodes()
470 // will be called.
471}
472
473void RenderCounter::rendererRemovedFromTree(RenderElement& renderer)
474{
475 if (!renderer.view().hasRenderCounters())
476 return;
477 RenderObject* currentRenderer = renderer.lastLeafChild();
478 if (!currentRenderer)
479 currentRenderer = &renderer;
480 while (true) {
481 if (is<RenderElement>(*currentRenderer)) {
482 auto& counterNodeRenderer = downcast<RenderElement>(*currentRenderer);
483 if (counterNodeRenderer.hasCounterNodeMap())
484 destroyCounterNodes(counterNodeRenderer);
485 }
486 if (currentRenderer == &renderer)
487 break;
488 currentRenderer = currentRenderer->previousInPreOrder();
489 }
490}
491
492static void updateCounters(RenderElement& renderer)
493{
494 auto* directiveMap = renderer.style().counterDirectives();
495 if (!directiveMap)
496 return;
497 if (!renderer.hasCounterNodeMap()) {
498 for (auto& key : directiveMap->keys())
499 makeCounterNode(renderer, key, false);
500 return;
501 }
502 ASSERT(counterMaps().contains(&renderer));
503 auto* counterMap = counterMaps().find(&renderer)->value.get();
504 for (auto& key : directiveMap->keys()) {
505 RefPtr<CounterNode> node = counterMap->get(key);
506 if (!node) {
507 makeCounterNode(renderer, key, false);
508 continue;
509 }
510 auto place = findPlaceForCounter(renderer, key, node->hasResetType());
511 if (node != counterMap->get(key))
512 continue;
513 CounterNode* parent = node->parent();
514 if (place.parent == parent && place.previousSibling == node->previousSibling())
515 continue;
516 if (parent)
517 parent->removeChild(*node);
518 if (place.parent)
519 place.parent->insertAfter(*node, place.previousSibling.get(), key);
520 }
521}
522
523void RenderCounter::rendererSubtreeAttached(RenderElement& renderer)
524{
525 if (!renderer.view().hasRenderCounters())
526 return;
527 Element* element = renderer.element();
528 if (element && !element->isPseudoElement())
529 element = element->parentElement();
530 else
531 element = renderer.generatingElement();
532 if (element && !element->renderer())
533 return; // No need to update if the parent is not attached yet
534 for (RenderObject* descendant = &renderer; descendant; descendant = descendant->nextInPreOrder(&renderer)) {
535 if (is<RenderElement>(*descendant))
536 updateCounters(downcast<RenderElement>(*descendant));
537 }
538}
539
540void RenderCounter::rendererStyleChanged(RenderElement& renderer, const RenderStyle* oldStyle, const RenderStyle* newStyle)
541{
542 Element* element = renderer.generatingElement();
543 if (!element || !element->renderer())
544 return; // cannot have generated content or if it can have, it will be handled during attaching
545
546 const CounterDirectiveMap* newCounterDirectives;
547 const CounterDirectiveMap* oldCounterDirectives;
548 if (oldStyle && (oldCounterDirectives = oldStyle->counterDirectives())) {
549 if (newStyle && (newCounterDirectives = newStyle->counterDirectives())) {
550 for (auto& keyValue : *newCounterDirectives) {
551 auto existingEntry = oldCounterDirectives->find(keyValue.key);
552 if (existingEntry != oldCounterDirectives->end()) {
553 if (existingEntry->value == keyValue.value)
554 continue;
555 RenderCounter::destroyCounterNode(renderer, keyValue.key);
556 }
557 // We must create this node here, because the changed node may be a node with no display such as
558 // as those created by the increment or reset directives and the re-layout that will happen will
559 // not catch the change if the node had no children.
560 makeCounterNode(renderer, keyValue.key, false);
561 }
562 // Destroying old counters that do not exist in the new counterDirective map.
563 for (auto& key : oldCounterDirectives->keys()) {
564 if (!newCounterDirectives->contains(key))
565 RenderCounter::destroyCounterNode(renderer, key);
566 }
567 } else {
568 if (renderer.hasCounterNodeMap())
569 RenderCounter::destroyCounterNodes(renderer);
570 }
571 } else {
572 if (newStyle && (newCounterDirectives = newStyle->counterDirectives())) {
573 for (auto& key : newCounterDirectives->keys()) {
574 // We must create this node here, because the added node may be a node with no display such as
575 // as those created by the increment or reset directives and the re-layout that will happen will
576 // not catch the change if the node had no children.
577 makeCounterNode(renderer, key, false);
578 }
579 }
580 }
581}
582
583} // namespace WebCore
584
585#if ENABLE(TREE_DEBUGGING)
586
587void showCounterRendererTree(const WebCore::RenderObject* renderer, const char* counterName)
588{
589 if (!renderer)
590 return;
591 auto* root = renderer;
592 while (root->parent())
593 root = root->parent();
594
595 AtomicString identifier(counterName);
596 for (auto* current = root; current; current = current->nextInPreOrder()) {
597 if (!is<WebCore::RenderElement>(*current))
598 continue;
599 fprintf(stderr, "%c", (current == renderer) ? '*' : ' ');
600 for (auto* ancestor = current; ancestor && ancestor != root; ancestor = ancestor->parent())
601 fprintf(stderr, " ");
602 fprintf(stderr, "%p N:%p P:%p PS:%p NS:%p C:%p\n",
603 current, current->node(), current->parent(), current->previousSibling(),
604 current->nextSibling(), downcast<WebCore::RenderElement>(*current).hasCounterNodeMap() ?
605 counterName ? WebCore::counterMaps().find(downcast<WebCore::RenderElement>(current))->value->get(identifier) : (WebCore::CounterNode*)1 : (WebCore::CounterNode*)0);
606 }
607 fflush(stderr);
608}
609
610#endif // NDEBUG
611