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 "core/rendering/RenderListItem.h"
26
27#include "core/HTMLNames.h"
28#include "core/dom/NodeRenderingTraversal.h"
29#include "core/html/HTMLOListElement.h"
30#include "core/rendering/RenderListMarker.h"
31#include "core/rendering/RenderView.h"
32#include "core/rendering/TextAutosizer.h"
33#include "wtf/StdLibExtras.h"
34#include "wtf/text/StringBuilder.h"
35
36namespace blink {
37
38using namespace HTMLNames;
39
40RenderListItem::RenderListItem(Element* element)
41    : RenderBlockFlow(element)
42    , m_marker(nullptr)
43    , m_hasExplicitValue(false)
44    , m_isValueUpToDate(false)
45    , m_notInList(false)
46{
47    setInline(false);
48}
49
50void RenderListItem::trace(Visitor* visitor)
51{
52    visitor->trace(m_marker);
53    RenderBlockFlow::trace(visitor);
54}
55
56void RenderListItem::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
57{
58    RenderBlockFlow::styleDidChange(diff, oldStyle);
59
60    if (style()->listStyleType() != NoneListStyle
61        || (style()->listStyleImage() && !style()->listStyleImage()->errorOccurred())) {
62        RefPtr<RenderStyle> newStyle = RenderStyle::create();
63        // The marker always inherits from the list item, regardless of where it might end
64        // up (e.g., in some deeply nested line box). See CSS3 spec.
65        newStyle->inheritFrom(style());
66        if (!m_marker)
67            m_marker = RenderListMarker::createAnonymous(this);
68        m_marker->setStyle(newStyle.release());
69    } else if (m_marker) {
70        m_marker->destroy();
71        m_marker = nullptr;
72    }
73}
74
75void RenderListItem::willBeDestroyed()
76{
77    if (m_marker) {
78        m_marker->destroy();
79        m_marker = nullptr;
80    }
81    RenderBlockFlow::willBeDestroyed();
82}
83
84void RenderListItem::insertedIntoTree()
85{
86    RenderBlockFlow::insertedIntoTree();
87
88    updateListMarkerNumbers();
89}
90
91void RenderListItem::willBeRemovedFromTree()
92{
93    RenderBlockFlow::willBeRemovedFromTree();
94
95    updateListMarkerNumbers();
96}
97
98static bool isList(const Node& node)
99{
100    return isHTMLUListElement(node) || isHTMLOListElement(node);
101}
102
103// Returns the enclosing list with respect to the DOM order.
104static Node* enclosingList(const RenderListItem* listItem)
105{
106    Node* listItemNode = listItem->node();
107    Node* firstNode = 0;
108    // We use parentNode because the enclosing list could be a ShadowRoot that's not Element.
109    for (Node* parent = NodeRenderingTraversal::parent(listItemNode); parent; parent = NodeRenderingTraversal::parent(parent)) {
110        if (isList(*parent))
111            return parent;
112        if (!firstNode)
113            firstNode = parent;
114    }
115
116    // If there's no actual <ul> or <ol> list element, then the first found
117    // node acts as our list for purposes of determining what other list items
118    // should be numbered as part of the same list.
119    return firstNode;
120}
121
122// Returns the next list item with respect to the DOM order.
123static RenderListItem* nextListItem(const Node* listNode, const RenderListItem* item = 0)
124{
125    if (!listNode)
126        return 0;
127
128    const Node* current = item ? item->node() : listNode;
129    ASSERT(current);
130    ASSERT(!current->document().childNeedsDistributionRecalc());
131    current = NodeRenderingTraversal::next(current, listNode);
132
133    while (current) {
134        if (isList(*current)) {
135            // We've found a nested, independent list: nothing to do here.
136            current = NodeRenderingTraversal::next(current, listNode);
137            continue;
138        }
139
140        RenderObject* renderer = current->renderer();
141        if (renderer && renderer->isListItem())
142            return toRenderListItem(renderer);
143
144        // FIXME: Can this be optimized to skip the children of the elements without a renderer?
145        current = NodeRenderingTraversal::next(current, listNode);
146    }
147
148    return 0;
149}
150
151// Returns the previous list item with respect to the DOM order.
152static RenderListItem* previousListItem(const Node* listNode, const RenderListItem* item)
153{
154    Node* current = item->node();
155    ASSERT(current);
156    ASSERT(!current->document().childNeedsDistributionRecalc());
157    for (current = NodeRenderingTraversal::previous(current, listNode); current && current != listNode; current = NodeRenderingTraversal::previous(current, listNode)) {
158        RenderObject* renderer = current->renderer();
159        if (!renderer || (renderer && !renderer->isListItem()))
160            continue;
161        Node* otherList = enclosingList(toRenderListItem(renderer));
162        // This item is part of our current list, so it's what we're looking for.
163        if (listNode == otherList)
164            return toRenderListItem(renderer);
165        // We found ourself inside another list; lets skip the rest of it.
166        // Use nextIncludingPseudo() here because the other list itself may actually
167        // be a list item itself. We need to examine it, so we do this to counteract
168        // the previousIncludingPseudo() that will be done by the loop.
169        if (otherList)
170            current = NodeRenderingTraversal::next(otherList, listNode);
171    }
172    return 0;
173}
174
175void RenderListItem::updateItemValuesForOrderedList(const HTMLOListElement* listNode)
176{
177    ASSERT(listNode);
178
179    for (RenderListItem* listItem = nextListItem(listNode); listItem; listItem = nextListItem(listNode, listItem))
180        listItem->updateValue();
181}
182
183unsigned RenderListItem::itemCountForOrderedList(const HTMLOListElement* listNode)
184{
185    ASSERT(listNode);
186
187    unsigned itemCount = 0;
188    for (RenderListItem* listItem = nextListItem(listNode); listItem; listItem = nextListItem(listNode, listItem))
189        itemCount++;
190
191    return itemCount;
192}
193
194inline int RenderListItem::calcValue() const
195{
196    if (m_hasExplicitValue)
197        return m_explicitValue;
198
199    Node* list = enclosingList(this);
200    HTMLOListElement* oListElement = isHTMLOListElement(list) ? toHTMLOListElement(list) : 0;
201    int valueStep = 1;
202    if (oListElement && oListElement->isReversed())
203        valueStep = -1;
204
205    // FIXME: This recurses to a possible depth of the length of the list.
206    // That's not good -- we need to change this to an iterative algorithm.
207    if (RenderListItem* previousItem = previousListItem(list, this))
208        return previousItem->value() + valueStep;
209
210    if (oListElement)
211        return oListElement->start();
212
213    return 1;
214}
215
216void RenderListItem::updateValueNow() const
217{
218    m_value = calcValue();
219    m_isValueUpToDate = true;
220}
221
222bool RenderListItem::isEmpty() const
223{
224    return lastChild() == m_marker;
225}
226
227static RenderObject* getParentOfFirstLineBox(RenderBlockFlow* curr, RenderObject* marker)
228{
229    RenderObject* firstChild = curr->firstChild();
230    if (!firstChild)
231        return 0;
232
233    bool inQuirksMode = curr->document().inQuirksMode();
234    for (RenderObject* currChild = firstChild; currChild; currChild = currChild->nextSibling()) {
235        if (currChild == marker)
236            continue;
237
238        if (currChild->isInline() && (!currChild->isRenderInline() || curr->generatesLineBoxesForInlineChild(currChild)))
239            return curr;
240
241        if (currChild->isFloating() || currChild->isOutOfFlowPositioned())
242            continue;
243
244        if (!currChild->isRenderBlockFlow() || (currChild->isBox() && toRenderBox(currChild)->isWritingModeRoot()))
245            break;
246
247        if (curr->isListItem() && inQuirksMode && currChild->node() &&
248            (isHTMLUListElement(*currChild->node()) || isHTMLOListElement(*currChild->node())))
249            break;
250
251        RenderObject* lineBox = getParentOfFirstLineBox(toRenderBlockFlow(currChild), marker);
252        if (lineBox)
253            return lineBox;
254    }
255
256    return 0;
257}
258
259void RenderListItem::updateValue()
260{
261    if (!m_hasExplicitValue) {
262        m_isValueUpToDate = false;
263        if (m_marker)
264            m_marker->setNeedsLayoutAndPrefWidthsRecalcAndFullPaintInvalidation();
265    }
266}
267
268static RenderObject* firstNonMarkerChild(RenderObject* parent)
269{
270    RenderObject* result = parent->slowFirstChild();
271    while (result && result->isListMarker())
272        result = result->nextSibling();
273    return result;
274}
275
276void RenderListItem::updateMarkerLocationAndInvalidateWidth()
277{
278    ASSERT(m_marker);
279
280    // FIXME: We should not modify the structure of the render tree
281    // during layout. crbug.com/370461
282    DeprecatedDisableModifyRenderTreeStructureAsserts disabler;
283    if (updateMarkerLocation()) {
284        // If the marker is inside we need to redo the preferred width calculations
285        // as the size of the item now includes the size of the list marker.
286        if (m_marker->isInside())
287            containingBlock()->updateLogicalWidth();
288    }
289}
290
291bool RenderListItem::updateMarkerLocation()
292{
293    ASSERT(m_marker);
294    RenderObject* markerParent = m_marker->parent();
295    RenderObject* lineBoxParent = getParentOfFirstLineBox(this, m_marker);
296    if (!lineBoxParent) {
297        // If the marker is currently contained inside an anonymous box, then we
298        // are the only item in that anonymous box (since no line box parent was
299        // found). It's ok to just leave the marker where it is in this case.
300        if (markerParent && markerParent->isAnonymousBlock())
301            lineBoxParent = markerParent;
302        else
303            lineBoxParent = this;
304    }
305
306    if (markerParent != lineBoxParent) {
307        m_marker->remove();
308        lineBoxParent->addChild(m_marker, firstNonMarkerChild(lineBoxParent));
309        m_marker->updateMarginsAndContent();
310        // If markerParent is an anonymous block with no children, destroy it.
311        if (markerParent && markerParent->isAnonymousBlock() && !toRenderBlock(markerParent)->firstChild() && !toRenderBlock(markerParent)->continuation())
312            markerParent->destroy();
313        return true;
314    }
315
316    return false;
317}
318
319void RenderListItem::layout()
320{
321    ASSERT(needsLayout());
322
323    if (m_marker) {
324        // The marker must be autosized before calling
325        // updateMarkerLocationAndInvalidateWidth. It cannot be done in the
326        // parent's beginLayout because it is not yet in the render tree.
327        if (TextAutosizer* textAutosizer = document().textAutosizer())
328            textAutosizer->inflateListItem(this, m_marker);
329
330        updateMarkerLocationAndInvalidateWidth();
331    }
332
333    RenderBlockFlow::layout();
334}
335
336void RenderListItem::addOverflowFromChildren()
337{
338    RenderBlockFlow::addOverflowFromChildren();
339    positionListMarker();
340}
341
342void RenderListItem::positionListMarker()
343{
344    if (m_marker && m_marker->parent()->isBox() && !m_marker->isInside() && m_marker->inlineBoxWrapper()) {
345        LayoutUnit markerOldLogicalLeft = m_marker->logicalLeft();
346        LayoutUnit blockOffset = 0;
347        LayoutUnit lineOffset = 0;
348        for (RenderBox* o = m_marker->parentBox(); o != this; o = o->parentBox()) {
349            blockOffset += o->logicalTop();
350            lineOffset += o->logicalLeft();
351        }
352
353        bool adjustOverflow = false;
354        LayoutUnit markerLogicalLeft;
355        RootInlineBox& root = m_marker->inlineBoxWrapper()->root();
356        bool hitSelfPaintingLayer = false;
357
358        LayoutUnit lineTop = root.lineTop();
359        LayoutUnit lineBottom = root.lineBottom();
360
361        // FIXME: Need to account for relative positioning in the layout overflow.
362        if (style()->isLeftToRightDirection()) {
363            LayoutUnit leftLineOffset = logicalLeftOffsetForLine(blockOffset, logicalLeftOffsetForLine(blockOffset, false), false);
364            markerLogicalLeft = leftLineOffset - lineOffset - paddingStart() - borderStart() + m_marker->marginStart();
365            m_marker->inlineBoxWrapper()->adjustLineDirectionPosition((markerLogicalLeft - markerOldLogicalLeft).toFloat());
366            for (InlineFlowBox* box = m_marker->inlineBoxWrapper()->parent(); box; box = box->parent()) {
367                LayoutRect newLogicalVisualOverflowRect = box->logicalVisualOverflowRect(lineTop, lineBottom);
368                LayoutRect newLogicalLayoutOverflowRect = box->logicalLayoutOverflowRect(lineTop, lineBottom);
369                if (markerLogicalLeft < newLogicalVisualOverflowRect.x() && !hitSelfPaintingLayer) {
370                    newLogicalVisualOverflowRect.setWidth(newLogicalVisualOverflowRect.maxX() - markerLogicalLeft);
371                    newLogicalVisualOverflowRect.setX(markerLogicalLeft);
372                    if (box == root)
373                        adjustOverflow = true;
374                }
375                if (markerLogicalLeft < newLogicalLayoutOverflowRect.x()) {
376                    newLogicalLayoutOverflowRect.setWidth(newLogicalLayoutOverflowRect.maxX() - markerLogicalLeft);
377                    newLogicalLayoutOverflowRect.setX(markerLogicalLeft);
378                    if (box == root)
379                        adjustOverflow = true;
380                }
381                box->setOverflowFromLogicalRects(newLogicalLayoutOverflowRect, newLogicalVisualOverflowRect, lineTop, lineBottom);
382                if (box->boxModelObject()->hasSelfPaintingLayer())
383                    hitSelfPaintingLayer = true;
384            }
385        } else {
386            LayoutUnit rightLineOffset = logicalRightOffsetForLine(blockOffset, logicalRightOffsetForLine(blockOffset, false), false);
387            markerLogicalLeft = rightLineOffset - lineOffset + paddingStart() + borderStart() + m_marker->marginEnd();
388            m_marker->inlineBoxWrapper()->adjustLineDirectionPosition((markerLogicalLeft - markerOldLogicalLeft).toFloat());
389            for (InlineFlowBox* box = m_marker->inlineBoxWrapper()->parent(); box; box = box->parent()) {
390                LayoutRect newLogicalVisualOverflowRect = box->logicalVisualOverflowRect(lineTop, lineBottom);
391                LayoutRect newLogicalLayoutOverflowRect = box->logicalLayoutOverflowRect(lineTop, lineBottom);
392                if (markerLogicalLeft + m_marker->logicalWidth() > newLogicalVisualOverflowRect.maxX() && !hitSelfPaintingLayer) {
393                    newLogicalVisualOverflowRect.setWidth(markerLogicalLeft + m_marker->logicalWidth() - newLogicalVisualOverflowRect.x());
394                    if (box == root)
395                        adjustOverflow = true;
396                }
397                if (markerLogicalLeft + m_marker->logicalWidth() > newLogicalLayoutOverflowRect.maxX()) {
398                    newLogicalLayoutOverflowRect.setWidth(markerLogicalLeft + m_marker->logicalWidth() - newLogicalLayoutOverflowRect.x());
399                    if (box == root)
400                        adjustOverflow = true;
401                }
402                box->setOverflowFromLogicalRects(newLogicalLayoutOverflowRect, newLogicalVisualOverflowRect, lineTop, lineBottom);
403
404                if (box->boxModelObject()->hasSelfPaintingLayer())
405                    hitSelfPaintingLayer = true;
406            }
407        }
408
409        if (adjustOverflow) {
410            LayoutRect markerRect(markerLogicalLeft + lineOffset, blockOffset, m_marker->width(), m_marker->height());
411            if (!style()->isHorizontalWritingMode())
412                markerRect = markerRect.transposedRect();
413            RenderBox* o = m_marker;
414            bool propagateVisualOverflow = true;
415            bool propagateLayoutOverflow = true;
416            do {
417                o = o->parentBox();
418                if (o->isRenderBlock()) {
419                    if (propagateVisualOverflow)
420                        toRenderBlock(o)->addContentsVisualOverflow(markerRect);
421                    if (propagateLayoutOverflow)
422                        toRenderBlock(o)->addLayoutOverflow(markerRect);
423                }
424                if (o->hasOverflowClip()) {
425                    propagateLayoutOverflow = false;
426                    propagateVisualOverflow = false;
427                }
428                if (o->hasSelfPaintingLayer())
429                    propagateVisualOverflow = false;
430                markerRect.moveBy(-o->location());
431            } while (o != this && propagateVisualOverflow && propagateLayoutOverflow);
432        }
433    }
434}
435
436void RenderListItem::paint(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
437{
438    if (!logicalHeight() && hasOverflowClip())
439        return;
440
441    RenderBlockFlow::paint(paintInfo, paintOffset);
442}
443
444const String& RenderListItem::markerText() const
445{
446    if (m_marker)
447        return m_marker->text();
448    return nullAtom.string();
449}
450
451void RenderListItem::explicitValueChanged()
452{
453    if (m_marker)
454        m_marker->setNeedsLayoutAndPrefWidthsRecalcAndFullPaintInvalidation();
455    Node* listNode = enclosingList(this);
456    for (RenderListItem* item = this; item; item = nextListItem(listNode, item))
457        item->updateValue();
458}
459
460void RenderListItem::setExplicitValue(int value)
461{
462    ASSERT(node());
463
464    if (m_hasExplicitValue && m_explicitValue == value)
465        return;
466    m_explicitValue = value;
467    m_value = value;
468    m_hasExplicitValue = true;
469    explicitValueChanged();
470}
471
472void RenderListItem::clearExplicitValue()
473{
474    ASSERT(node());
475
476    if (!m_hasExplicitValue)
477        return;
478    m_hasExplicitValue = false;
479    m_isValueUpToDate = false;
480    explicitValueChanged();
481}
482
483void RenderListItem::setNotInList(bool notInList)
484{
485    m_notInList = notInList;
486    if (m_marker)
487        updateMarkerLocation();
488}
489
490static RenderListItem* previousOrNextItem(bool isListReversed, Node* list, RenderListItem* item)
491{
492    return isListReversed ? previousListItem(list, item) : nextListItem(list, item);
493}
494
495void RenderListItem::updateListMarkerNumbers()
496{
497    // If distribution recalc is needed, updateListMarkerNumber will be re-invoked
498    // after distribution is calculated.
499    if (node()->document().childNeedsDistributionRecalc())
500        return;
501
502    Node* listNode = enclosingList(this);
503    ASSERT(listNode);
504
505    bool isListReversed = false;
506    HTMLOListElement* oListElement = isHTMLOListElement(listNode) ? toHTMLOListElement(listNode) : 0;
507    if (oListElement) {
508        oListElement->itemCountChanged();
509        isListReversed = oListElement->isReversed();
510    }
511
512    // FIXME: The n^2 protection below doesn't help if the elements were inserted after the
513    // the list had already been displayed.
514
515    // Avoid an O(n^2) walk over the children below when they're all known to be attaching.
516    if (listNode->needsAttach())
517        return;
518
519    for (RenderListItem* item = previousOrNextItem(isListReversed, listNode, this); item; item = previousOrNextItem(isListReversed, listNode, item)) {
520        if (!item->m_isValueUpToDate) {
521            // If an item has been marked for update before, we can safely
522            // assume that all the following ones have too.
523            // This gives us the opportunity to stop here and avoid
524            // marking the same nodes again.
525            break;
526        }
527        item->updateValue();
528    }
529}
530
531} // namespace blink
532