Optimize fetching the Node for never-anonymous renderers.
[WebKit-https.git] / Source / WebCore / rendering / RenderListItem.cpp
1 /**
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  * Copyright (C) 2003, 2004, 2005, 2006, 2010 Apple Inc. All rights reserved.
5  * Copyright (C) 2006 Andrew Wellington (proton@wiretapped.net)
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #include "config.h"
25 #include "RenderListItem.h"
26
27 #include "ElementTraversal.h"
28 #include "HTMLNames.h"
29 #include "HTMLOListElement.h"
30 #include "PseudoElement.h"
31 #include "RenderListMarker.h"
32 #include "RenderView.h"
33 #include "StyleInheritedData.h"
34 #include <wtf/StackStats.h>
35 #include <wtf/StdLibExtras.h>
36 #include <wtf/text/StringBuilder.h>
37
38 using namespace std;
39
40 namespace WebCore {
41
42 using namespace HTMLNames;
43
44 RenderListItem::RenderListItem(Element& element)
45     : RenderBlockFlow(&element)
46     , m_marker(0)
47     , m_hasExplicitValue(false)
48     , m_isValueUpToDate(false)
49     , m_notInList(false)
50 {
51     setInline(false);
52 }
53
54 void RenderListItem::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
55 {
56     RenderBlock::styleDidChange(diff, oldStyle);
57
58     if (style()->listStyleType() != NoneListStyle
59         || (style()->listStyleImage() && !style()->listStyleImage()->errorOccurred())) {
60         RefPtr<RenderStyle> newStyle = RenderStyle::create();
61         // The marker always inherits from the list item, regardless of where it might end
62         // up (e.g., in some deeply nested line box). See CSS3 spec.
63         newStyle->inheritFrom(style()); 
64         if (!m_marker)
65             m_marker = RenderListMarker::createAnonymous(*this);
66         m_marker->setStyle(newStyle.release());
67     } else if (m_marker) {
68         m_marker->destroy();
69         m_marker = 0;
70     }
71 }
72
73 void RenderListItem::willBeDestroyed()
74 {    
75     if (m_marker) {
76         m_marker->destroy();
77         m_marker = 0;
78     }
79     RenderBlockFlow::willBeDestroyed();
80 }
81
82 void RenderListItem::insertedIntoTree()
83 {
84     RenderBlock::insertedIntoTree();
85
86     updateListMarkerNumbers();
87 }
88
89 void RenderListItem::willBeRemovedFromTree()
90 {
91     RenderBlockFlow::willBeRemovedFromTree();
92
93     updateListMarkerNumbers();
94 }
95
96 static bool isList(const Element* element)
97 {
98     return element->hasTagName(ulTag) || element->hasTagName(olTag);
99 }
100
101 // Returns the enclosing list with respect to the DOM order.
102 static Element* enclosingList(const RenderListItem* listItem)
103 {
104     Element& listItemElement = listItem->element();
105     Element* firstNode = 0;
106     Element* parent = listItemElement.isPseudoElement() ? toPseudoElement(listItemElement).hostElement() : listItemElement.parentElement();
107     // We use parentNode because the enclosing list could be a ShadowRoot that's not Element.
108     for (; parent; parent = parent->parentElement()) {
109         if (isList(parent))
110             return parent;
111         if (!firstNode)
112             firstNode = parent;
113     }
114
115     // If there's no actual <ul> or <ol> list element, then the first found
116     // node acts as our list for purposes of determining what other list items
117     // should be numbered as part of the same list.
118     return firstNode;
119 }
120
121 // Returns the next list item with respect to the DOM order.
122 static RenderListItem* nextListItem(const Element* listNode, const RenderListItem* item = 0)
123 {
124     if (!listNode)
125         return 0;
126
127     const Element* current = item ? &item->element() : listNode;
128     current = ElementTraversal::nextIncludingPseudo(current, listNode);
129
130     while (current) {
131         if (isList(current)) {
132             // We've found a nested, independent list: nothing to do here.
133             current = ElementTraversal::nextIncludingPseudoSkippingChildren(current, listNode);
134             continue;
135         }
136
137         RenderObject* renderer = current->renderer();
138         if (renderer && renderer->isListItem())
139             return toRenderListItem(renderer);
140
141         // FIXME: Can this be optimized to skip the children of the elements without a renderer?
142         current = ElementTraversal::nextIncludingPseudo(current, listNode);
143     }
144
145     return 0;
146 }
147
148 // Returns the previous list item with respect to the DOM order.
149 static RenderListItem* previousListItem(const Element* listNode, const RenderListItem* item)
150 {
151     Element* current = &item->element();
152     for (current = ElementTraversal::previousIncludingPseudo(current, listNode); current; current = ElementTraversal::previousIncludingPseudo(current, listNode)) {
153         RenderObject* renderer = current->renderer();
154         if (!renderer || (renderer && !renderer->isListItem()))
155             continue;
156         Node* otherList = enclosingList(toRenderListItem(renderer));
157         // This item is part of our current list, so it's what we're looking for.
158         if (listNode == otherList)
159             return toRenderListItem(renderer);
160         // We found ourself inside another list; lets skip the rest of it.
161         // Use nextIncludingPseudo() here because the other list itself may actually
162         // be a list item itself. We need to examine it, so we do this to counteract
163         // the previousIncludingPseudo() that will be done by the loop.
164         if (otherList)
165             current = ElementTraversal::nextIncludingPseudo(otherList);
166     }
167     return 0;
168 }
169
170 void RenderListItem::updateItemValuesForOrderedList(const HTMLOListElement* listNode)
171 {
172     ASSERT(listNode);
173
174     for (RenderListItem* listItem = nextListItem(listNode); listItem; listItem = nextListItem(listNode, listItem))
175         listItem->updateValue();
176 }
177
178 unsigned RenderListItem::itemCountForOrderedList(const HTMLOListElement* listNode)
179 {
180     ASSERT(listNode);
181
182     unsigned itemCount = 0;
183     for (RenderListItem* listItem = nextListItem(listNode); listItem; listItem = nextListItem(listNode, listItem))
184         itemCount++;
185
186     return itemCount;
187 }
188
189 inline int RenderListItem::calcValue() const
190 {
191     if (m_hasExplicitValue)
192         return m_explicitValue;
193
194     Element* list = enclosingList(this);
195     HTMLOListElement* oListElement = (list && list->hasTagName(olTag)) ? static_cast<HTMLOListElement*>(list) : 0;
196     int valueStep = 1;
197     if (oListElement && oListElement->isReversed())
198         valueStep = -1;
199
200     // FIXME: This recurses to a possible depth of the length of the list.
201     // That's not good -- we need to change this to an iterative algorithm.
202     if (RenderListItem* previousItem = previousListItem(list, this))
203         return previousItem->value() + valueStep;
204
205     if (oListElement)
206         return oListElement->start();
207
208     return 1;
209 }
210
211 void RenderListItem::updateValueNow() const
212 {
213     m_value = calcValue();
214     m_isValueUpToDate = true;
215 }
216
217 bool RenderListItem::isEmpty() const
218 {
219     return lastChild() == m_marker;
220 }
221
222 static RenderBlock* getParentOfFirstLineBox(RenderBlock* curr, RenderObject* marker)
223 {
224     RenderObject* firstChild = curr->firstChild();
225     if (!firstChild)
226         return 0;
227
228     bool inQuirksMode = curr->document().inQuirksMode();
229     for (RenderObject* currChild = firstChild; currChild; currChild = currChild->nextSibling()) {
230         if (currChild == marker)
231             continue;
232
233         if (currChild->isInline() && (!currChild->isRenderInline() || curr->generatesLineBoxesForInlineChild(currChild)))
234             return curr;
235
236         if (currChild->isFloating() || currChild->isOutOfFlowPositioned())
237             continue;
238
239         if (currChild->isTable() || !currChild->isRenderBlock() || (currChild->isBox() && toRenderBox(currChild)->isWritingModeRoot()))
240             break;
241
242         if (curr->isListItem() && inQuirksMode && currChild->node() &&
243             (currChild->node()->hasTagName(ulTag)|| currChild->node()->hasTagName(olTag)))
244             break;
245
246         RenderBlock* lineBox = getParentOfFirstLineBox(toRenderBlock(currChild), marker);
247         if (lineBox)
248             return lineBox;
249     }
250
251     return 0;
252 }
253
254 void RenderListItem::updateValue()
255 {
256     if (!m_hasExplicitValue) {
257         m_isValueUpToDate = false;
258         if (m_marker)
259             m_marker->setNeedsLayoutAndPrefWidthsRecalc();
260     }
261 }
262
263 static RenderObject* firstNonMarkerChild(RenderObject* parent)
264 {
265     RenderObject* result = parent->firstChild();
266     while (result && result->isListMarker())
267         result = result->nextSibling();
268     return result;
269 }
270
271 void RenderListItem::insertOrMoveMarkerRendererIfNeeded()
272 {
273     // Sanity check the location of our marker.
274     if (!m_marker)
275         return;
276
277     RenderElement* currentParent = m_marker->parent();
278     RenderBlock* newParent = getParentOfFirstLineBox(this, m_marker);
279     if (!newParent) {
280         // If the marker is currently contained inside an anonymous box,
281         // then we are the only item in that anonymous box (since no line box
282         // parent was found). It's ok to just leave the marker where it is
283         // in this case.
284         if (currentParent && currentParent->isAnonymousBlock())
285             return;
286         newParent = this;
287     }
288
289     if (newParent != currentParent) {
290         // Removing and adding the marker can trigger repainting in
291         // containers other than ourselves, so we need to disable LayoutState.
292         LayoutStateDisabler layoutStateDisabler(&view());
293         m_marker->removeFromParent();
294         newParent->addChild(m_marker, firstNonMarkerChild(newParent));
295         m_marker->updateMarginsAndContent();
296         // If current parent is an anonymous block that has lost all its children, destroy it.
297         if (currentParent && currentParent->isAnonymousBlock() && !currentParent->firstChild() && !toRenderBlock(currentParent)->continuation())
298             currentParent->destroy();
299     }
300
301 }
302
303 void RenderListItem::layout()
304 {
305     StackStats::LayoutCheckPoint layoutCheckPoint;
306     ASSERT(needsLayout()); 
307
308     insertOrMoveMarkerRendererIfNeeded();
309     RenderBlockFlow::layout();
310 }
311
312 void RenderListItem::addOverflowFromChildren()
313 {
314     RenderBlockFlow::addOverflowFromChildren();
315     positionListMarker();
316 }
317
318 void RenderListItem::computePreferredLogicalWidths()
319 {
320 #ifndef NDEBUG
321     // FIXME: We shouldn't be modifying the tree in computePreferredLogicalWidths.
322     // Instead, we should insert the marker soon after the tree construction.
323     // This is similar case to RenderCounter::computePreferredLogicalWidths()
324     // See https://bugs.webkit.org/show_bug.cgi?id=104829
325     SetLayoutNeededForbiddenScope layoutForbiddenScope(this, false);
326 #endif
327     insertOrMoveMarkerRendererIfNeeded();
328     RenderBlockFlow::computePreferredLogicalWidths();
329 }
330
331 void RenderListItem::positionListMarker()
332 {
333     if (m_marker && m_marker->parent()->isBox() && !m_marker->isInside() && m_marker->inlineBoxWrapper()) {
334         LayoutUnit markerOldLogicalLeft = m_marker->logicalLeft();
335         LayoutUnit blockOffset = 0;
336         LayoutUnit lineOffset = 0;
337         for (RenderBox* o = m_marker->parentBox(); o != this; o = o->parentBox()) {
338             blockOffset += o->logicalTop();
339             lineOffset += o->logicalLeft();
340         }
341
342         bool adjustOverflow = false;
343         LayoutUnit markerLogicalLeft;
344         bool hitSelfPaintingLayer = false;
345         
346         const RootInlineBox& rootBox = m_marker->inlineBoxWrapper()->root();
347         LayoutUnit lineTop = rootBox.lineTop();
348         LayoutUnit lineBottom = rootBox.lineBottom();
349
350         // FIXME: Need to account for relative positioning in the layout overflow.
351         if (style()->isLeftToRightDirection()) {
352             LayoutUnit leftLineOffset = logicalLeftOffsetForLine(blockOffset, logicalLeftOffsetForLine(blockOffset, false), false);
353             markerLogicalLeft = leftLineOffset - lineOffset - paddingStart() - borderStart() + m_marker->marginStart();
354             m_marker->inlineBoxWrapper()->adjustLineDirectionPosition(markerLogicalLeft - markerOldLogicalLeft);
355             for (InlineFlowBox* box = m_marker->inlineBoxWrapper()->parent(); box; box = box->parent()) {
356                 LayoutRect newLogicalVisualOverflowRect = box->logicalVisualOverflowRect(lineTop, lineBottom);
357                 LayoutRect newLogicalLayoutOverflowRect = box->logicalLayoutOverflowRect(lineTop, lineBottom);
358                 if (markerLogicalLeft < newLogicalVisualOverflowRect.x() && !hitSelfPaintingLayer) {
359                     newLogicalVisualOverflowRect.setWidth(newLogicalVisualOverflowRect.maxX() - markerLogicalLeft);
360                     newLogicalVisualOverflowRect.setX(markerLogicalLeft);
361                     if (box == &rootBox)
362                         adjustOverflow = true;
363                 }
364                 if (markerLogicalLeft < newLogicalLayoutOverflowRect.x()) {
365                     newLogicalLayoutOverflowRect.setWidth(newLogicalLayoutOverflowRect.maxX() - markerLogicalLeft);
366                     newLogicalLayoutOverflowRect.setX(markerLogicalLeft);
367                     if (box == &rootBox)
368                         adjustOverflow = true;
369                 }
370                 box->setOverflowFromLogicalRects(newLogicalLayoutOverflowRect, newLogicalVisualOverflowRect, lineTop, lineBottom);
371                 if (box->boxModelObject()->hasSelfPaintingLayer())
372                     hitSelfPaintingLayer = true;
373             }
374         } else {
375             LayoutUnit rightLineOffset = logicalRightOffsetForLine(blockOffset, logicalRightOffsetForLine(blockOffset, false), false);
376             markerLogicalLeft = rightLineOffset - lineOffset + paddingStart() + borderStart() + m_marker->marginEnd();
377             m_marker->inlineBoxWrapper()->adjustLineDirectionPosition(markerLogicalLeft - markerOldLogicalLeft);
378             for (InlineFlowBox* box = m_marker->inlineBoxWrapper()->parent(); box; box = box->parent()) {
379                 LayoutRect newLogicalVisualOverflowRect = box->logicalVisualOverflowRect(lineTop, lineBottom);
380                 LayoutRect newLogicalLayoutOverflowRect = box->logicalLayoutOverflowRect(lineTop, lineBottom);
381                 if (markerLogicalLeft + m_marker->logicalWidth() > newLogicalVisualOverflowRect.maxX() && !hitSelfPaintingLayer) {
382                     newLogicalVisualOverflowRect.setWidth(markerLogicalLeft + m_marker->logicalWidth() - newLogicalVisualOverflowRect.x());
383                     if (box == &rootBox)
384                         adjustOverflow = true;
385                 }
386                 if (markerLogicalLeft + m_marker->logicalWidth() > newLogicalLayoutOverflowRect.maxX()) {
387                     newLogicalLayoutOverflowRect.setWidth(markerLogicalLeft + m_marker->logicalWidth() - newLogicalLayoutOverflowRect.x());
388                     if (box == &rootBox)
389                         adjustOverflow = true;
390                 }
391                 box->setOverflowFromLogicalRects(newLogicalLayoutOverflowRect, newLogicalVisualOverflowRect, lineTop, lineBottom);
392                 
393                 if (box->boxModelObject()->hasSelfPaintingLayer())
394                     hitSelfPaintingLayer = true;
395             }
396         }
397
398         if (adjustOverflow) {
399             LayoutRect markerRect(markerLogicalLeft + lineOffset, blockOffset, m_marker->width(), m_marker->height());
400             if (!style()->isHorizontalWritingMode())
401                 markerRect = markerRect.transposedRect();
402             RenderBox* o = m_marker;
403             bool propagateVisualOverflow = true;
404             bool propagateLayoutOverflow = true;
405             do {
406                 o = o->parentBox();
407                 if (o->hasOverflowClip())
408                     propagateVisualOverflow = false;
409                 if (o->isRenderBlock()) {
410                     if (propagateVisualOverflow)
411                         toRenderBlock(o)->addVisualOverflow(markerRect);
412                     if (propagateLayoutOverflow)
413                         toRenderBlock(o)->addLayoutOverflow(markerRect);
414                 }
415                 if (o->hasOverflowClip())
416                     propagateLayoutOverflow = false;
417                 if (o->hasSelfPaintingLayer())
418                     propagateVisualOverflow = false;
419                 markerRect.moveBy(-o->location());
420             } while (o != this && propagateVisualOverflow && propagateLayoutOverflow);
421         }
422     }
423 }
424
425 void RenderListItem::paint(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
426 {
427     if (!logicalHeight() && hasOverflowClip())
428         return;
429
430     RenderBlockFlow::paint(paintInfo, paintOffset);
431 }
432
433 const String& RenderListItem::markerText() const
434 {
435     if (m_marker)
436         return m_marker->text();
437     return nullAtom.string();
438 }
439
440 String RenderListItem::markerTextWithSuffix() const
441 {
442     if (!m_marker)
443         return String();
444
445     // Append the suffix for the marker in the right place depending
446     // on the direction of the text (right-to-left or left-to-right).
447
448     const String& markerText = m_marker->text();
449     const String markerSuffix = m_marker->suffix();
450     StringBuilder result;
451
452     if (!m_marker->style()->isLeftToRightDirection())
453         result.append(markerSuffix);
454
455     result.append(markerText);
456
457     if (m_marker->style()->isLeftToRightDirection())
458         result.append(markerSuffix);
459
460     return result.toString();
461 }
462
463 void RenderListItem::explicitValueChanged()
464 {
465     if (m_marker)
466         m_marker->setNeedsLayoutAndPrefWidthsRecalc();
467     Element* listNode = enclosingList(this);
468     for (RenderListItem* item = this; item; item = nextListItem(listNode, item))
469         item->updateValue();
470 }
471
472 void RenderListItem::setExplicitValue(int value)
473 {
474     if (m_hasExplicitValue && m_explicitValue == value)
475         return;
476     m_explicitValue = value;
477     m_value = value;
478     m_hasExplicitValue = true;
479     explicitValueChanged();
480 }
481
482 void RenderListItem::clearExplicitValue()
483 {
484     if (!m_hasExplicitValue)
485         return;
486     m_hasExplicitValue = false;
487     m_isValueUpToDate = false;
488     explicitValueChanged();
489 }
490
491 static RenderListItem* previousOrNextItem(bool isListReversed, Element* list, RenderListItem* item)
492 {
493     return isListReversed ? previousListItem(list, item) : nextListItem(list, item);
494 }
495
496 void RenderListItem::updateListMarkerNumbers()
497 {
498     Element* listNode = enclosingList(this);
499     // The list node can be the shadow root which has no renderer.
500     ASSERT(listNode);
501     if (!listNode)
502         return;
503
504     bool isListReversed = false;
505     HTMLOListElement* oListElement = (listNode && listNode->hasTagName(olTag)) ? static_cast<HTMLOListElement*>(listNode) : 0;
506     if (oListElement) {
507         oListElement->itemCountChanged();
508         isListReversed = oListElement->isReversed();
509     }
510     for (RenderListItem* item = previousOrNextItem(isListReversed, listNode, this); item; item = previousOrNextItem(isListReversed, listNode, item)) {
511         if (!item->m_isValueUpToDate) {
512             // If an item has been marked for update before, we can safely
513             // assume that all the following ones have too.
514             // This gives us the opportunity to stop here and avoid
515             // marking the same nodes again.
516             break;
517         }
518         item->updateValue();
519     }
520 }
521
522 } // namespace WebCore