1/*
2 * Copyright (C) 2008 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1.  Redistributions of source code must retain the above copyright
9 *     notice, this list of conditions and the following disclaimer.
10 * 2.  Redistributions in binary form must reproduce the above copyright
11 *     notice, this list of conditions and the following disclaimer in the
12 *     documentation and/or other materials provided with the distribution.
13 * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
14 *     its contributors may be used to endorse or promote products derived
15 *     from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#include "config.h"
30#include "RenderLineBoxList.h"
31
32#include "HitTestResult.h"
33#include "InlineElementBox.h"
34#include "InlineTextBox.h"
35#include "PaintInfo.h"
36#include "RenderBlockFlow.h"
37#include "RenderInline.h"
38#include "RenderLineBreak.h"
39#include "RenderView.h"
40#include "RootInlineBox.h"
41
42namespace WebCore {
43
44#ifndef NDEBUG
45RenderLineBoxList::~RenderLineBoxList()
46{
47    ASSERT(!m_firstLineBox);
48    ASSERT(!m_lastLineBox);
49}
50#endif
51
52void RenderLineBoxList::appendLineBox(std::unique_ptr<InlineFlowBox> box)
53{
54    checkConsistency();
55
56    InlineFlowBox* boxPtr = box.release();
57
58    if (!m_firstLineBox) {
59        m_firstLineBox = boxPtr;
60        m_lastLineBox = boxPtr;
61    } else {
62        m_lastLineBox->setNextLineBox(boxPtr);
63        boxPtr->setPreviousLineBox(m_lastLineBox);
64        m_lastLineBox = boxPtr;
65    }
66
67    checkConsistency();
68}
69
70void RenderLineBoxList::deleteLineBoxTree()
71{
72    InlineFlowBox* line = m_firstLineBox;
73    InlineFlowBox* nextLine;
74    while (line) {
75        nextLine = line->nextLineBox();
76        line->deleteLine();
77        line = nextLine;
78    }
79    m_firstLineBox = m_lastLineBox = 0;
80}
81
82void RenderLineBoxList::extractLineBox(InlineFlowBox* box)
83{
84    checkConsistency();
85
86    m_lastLineBox = box->prevLineBox();
87    if (box == m_firstLineBox)
88        m_firstLineBox = 0;
89    if (box->prevLineBox())
90        box->prevLineBox()->setNextLineBox(0);
91    box->setPreviousLineBox(0);
92    for (InlineFlowBox* curr = box; curr; curr = curr->nextLineBox())
93        curr->setExtracted();
94
95    checkConsistency();
96}
97
98void RenderLineBoxList::attachLineBox(InlineFlowBox* box)
99{
100    checkConsistency();
101
102    if (m_lastLineBox) {
103        m_lastLineBox->setNextLineBox(box);
104        box->setPreviousLineBox(m_lastLineBox);
105    } else
106        m_firstLineBox = box;
107    InlineFlowBox* last = box;
108    for (InlineFlowBox* curr = box; curr; curr = curr->nextLineBox()) {
109        curr->setExtracted(false);
110        last = curr;
111    }
112    m_lastLineBox = last;
113
114    checkConsistency();
115}
116
117void RenderLineBoxList::removeLineBox(InlineFlowBox* box)
118{
119    checkConsistency();
120
121    if (box == m_firstLineBox)
122        m_firstLineBox = box->nextLineBox();
123    if (box == m_lastLineBox)
124        m_lastLineBox = box->prevLineBox();
125    if (box->nextLineBox())
126        box->nextLineBox()->setPreviousLineBox(box->prevLineBox());
127    if (box->prevLineBox())
128        box->prevLineBox()->setNextLineBox(box->nextLineBox());
129
130    checkConsistency();
131}
132
133void RenderLineBoxList::deleteLineBoxes()
134{
135    if (m_firstLineBox) {
136        InlineFlowBox* next;
137        for (InlineFlowBox* curr = m_firstLineBox; curr; curr = next) {
138            next = curr->nextLineBox();
139            delete curr;
140        }
141        m_firstLineBox = 0;
142        m_lastLineBox = 0;
143    }
144}
145
146void RenderLineBoxList::dirtyLineBoxes()
147{
148    for (InlineFlowBox* curr = firstLineBox(); curr; curr = curr->nextLineBox())
149        curr->dirtyLineBoxes();
150}
151
152bool RenderLineBoxList::rangeIntersectsRect(RenderBoxModelObject* renderer, LayoutUnit logicalTop, LayoutUnit logicalBottom, const LayoutRect& rect, const LayoutPoint& offset) const
153{
154    RenderBox* block;
155    if (renderer->isBox())
156        block = toRenderBox(renderer);
157    else
158        block = renderer->containingBlock();
159    LayoutUnit physicalStart = block->flipForWritingMode(logicalTop);
160    LayoutUnit physicalEnd = block->flipForWritingMode(logicalBottom);
161    LayoutUnit physicalExtent = absoluteValue(physicalEnd - physicalStart);
162    physicalStart = std::min(physicalStart, physicalEnd);
163
164    if (renderer->style().isHorizontalWritingMode()) {
165        physicalStart += offset.y();
166        if (physicalStart >= rect.maxY() || physicalStart + physicalExtent <= rect.y())
167            return false;
168    } else {
169        physicalStart += offset.x();
170        if (physicalStart >= rect.maxX() || physicalStart + physicalExtent <= rect.x())
171            return false;
172    }
173
174    return true;
175}
176
177bool RenderLineBoxList::anyLineIntersectsRect(RenderBoxModelObject* renderer, const LayoutRect& rect, const LayoutPoint& offset, bool usePrintRect, LayoutUnit outlineSize) const
178{
179    // We can check the first box and last box and avoid painting/hit testing if we don't
180    // intersect.  This is a quick short-circuit that we can take to avoid walking any lines.
181    // FIXME: This check is flawed in the following extremely obscure way:
182    // if some line in the middle has a huge overflow, it might actually extend below the last line.
183    const RootInlineBox& firstRootBox = firstLineBox()->root();
184    const RootInlineBox& lastRootBox = lastLineBox()->root();
185    LayoutUnit firstLineTop = firstLineBox()->logicalTopVisualOverflow(firstRootBox.lineTop());
186    if (usePrintRect && !firstLineBox()->parent())
187        firstLineTop = std::min(firstLineTop, firstRootBox.lineTop());
188    LayoutUnit lastLineBottom = lastLineBox()->logicalBottomVisualOverflow(lastRootBox.lineBottom());
189    if (usePrintRect && !lastLineBox()->parent())
190        lastLineBottom = std::max(lastLineBottom, lastRootBox.lineBottom());
191    LayoutUnit logicalTop = firstLineTop - outlineSize;
192    LayoutUnit logicalBottom = outlineSize + lastLineBottom;
193
194    return rangeIntersectsRect(renderer, logicalTop, logicalBottom, rect, offset);
195}
196
197bool RenderLineBoxList::lineIntersectsDirtyRect(RenderBoxModelObject* renderer, InlineFlowBox* box, const PaintInfo& paintInfo, const LayoutPoint& offset) const
198{
199    const RootInlineBox& rootBox = box->root();
200    LayoutUnit logicalTop = std::min<LayoutUnit>(box->logicalTopVisualOverflow(rootBox.lineTop()), rootBox.selectionTop()) - renderer->maximalOutlineSize(paintInfo.phase);
201    LayoutUnit logicalBottom = box->logicalBottomVisualOverflow(rootBox.lineBottom()) + renderer->maximalOutlineSize(paintInfo.phase);
202
203    return rangeIntersectsRect(renderer, logicalTop, logicalBottom, paintInfo.rect, offset);
204}
205
206void RenderLineBoxList::paint(RenderBoxModelObject* renderer, PaintInfo& paintInfo, const LayoutPoint& paintOffset) const
207{
208    // Only paint during the foreground/selection phases.
209    if (paintInfo.phase != PaintPhaseForeground && paintInfo.phase != PaintPhaseSelection && paintInfo.phase != PaintPhaseOutline
210        && paintInfo.phase != PaintPhaseSelfOutline && paintInfo.phase != PaintPhaseChildOutlines && paintInfo.phase != PaintPhaseTextClip
211        && paintInfo.phase != PaintPhaseMask)
212        return;
213
214    ASSERT(renderer->isRenderBlock() || (renderer->isRenderInline() && renderer->hasLayer())); // The only way an inline could paint like this is if it has a layer.
215
216    // If we have no lines then we have no work to do.
217    if (!firstLineBox())
218        return;
219
220    // FIXME: Paint-time pagination is obsolete and is now only used by embedded WebViews inside AppKit
221    // NSViews.  Do not add any more code for this.
222    RenderView& v = renderer->view();
223    bool usePrintRect = !v.printRect().isEmpty();
224    LayoutUnit outlineSize = renderer->maximalOutlineSize(paintInfo.phase);
225    if (!anyLineIntersectsRect(renderer, paintInfo.rect, paintOffset, usePrintRect, outlineSize))
226        return;
227
228    PaintInfo info(paintInfo);
229    ListHashSet<RenderInline*> outlineObjects;
230    info.outlineObjects = &outlineObjects;
231
232    // See if our root lines intersect with the dirty rect.  If so, then we paint
233    // them.  Note that boxes can easily overlap, so we can't make any assumptions
234    // based off positions of our first line box or our last line box.
235    for (InlineFlowBox* curr = firstLineBox(); curr; curr = curr->nextLineBox()) {
236        if (usePrintRect) {
237            // FIXME: This is the deprecated pagination model that is still needed
238            // for embedded views inside AppKit.  AppKit is incapable of paginating vertical
239            // text pages, so we don't have to deal with vertical lines at all here.
240            const RootInlineBox& rootBox = curr->root();
241            LayoutUnit topForPaginationCheck = curr->logicalTopVisualOverflow(rootBox.lineTop());
242            LayoutUnit bottomForPaginationCheck = curr->logicalLeftVisualOverflow();
243            if (!curr->parent()) {
244                // We're a root box.  Use lineTop and lineBottom as well here.
245                topForPaginationCheck = std::min(topForPaginationCheck, rootBox.lineTop());
246                bottomForPaginationCheck = std::max(bottomForPaginationCheck, rootBox.lineBottom());
247            }
248            if (bottomForPaginationCheck - topForPaginationCheck <= v.printRect().height()) {
249                if (paintOffset.y() + bottomForPaginationCheck > v.printRect().maxY()) {
250                    if (RootInlineBox* nextRootBox = rootBox.nextRootBox())
251                        bottomForPaginationCheck = std::min(bottomForPaginationCheck, std::min<LayoutUnit>(nextRootBox->logicalTopVisualOverflow(), nextRootBox->lineTop()));
252                }
253                if (paintOffset.y() + bottomForPaginationCheck > v.printRect().maxY()) {
254                    if (paintOffset.y() + topForPaginationCheck < v.truncatedAt())
255                        v.setBestTruncatedAt(paintOffset.y() + topForPaginationCheck, renderer);
256                    // If we were able to truncate, don't paint.
257                    if (paintOffset.y() + topForPaginationCheck >= v.truncatedAt())
258                        break;
259                }
260            }
261        }
262
263        if (lineIntersectsDirtyRect(renderer, curr, info, paintOffset)) {
264            const RootInlineBox& rootBox = curr->root();
265            curr->paint(info, paintOffset, rootBox.lineTop(), rootBox.lineBottom());
266        }
267    }
268
269    if (info.phase == PaintPhaseOutline || info.phase == PaintPhaseSelfOutline || info.phase == PaintPhaseChildOutlines) {
270        ListHashSet<RenderInline*>::iterator end = info.outlineObjects->end();
271        for (ListHashSet<RenderInline*>::iterator it = info.outlineObjects->begin(); it != end; ++it) {
272            RenderInline* flow = *it;
273            flow->paintOutline(info, paintOffset);
274        }
275        info.outlineObjects->clear();
276    }
277}
278
279bool RenderLineBoxList::hitTest(RenderBoxModelObject* renderer, const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction hitTestAction) const
280{
281    if (hitTestAction != HitTestForeground)
282        return false;
283
284    ASSERT(renderer->isRenderBlock() || (renderer->isRenderInline() && renderer->hasLayer())); // The only way an inline could hit test like this is if it has a layer.
285
286    // If we have no lines then we have no work to do.
287    if (!firstLineBox())
288        return false;
289
290    LayoutPoint point = locationInContainer.point();
291    LayoutRect rect = firstLineBox()->isHorizontal() ?
292        IntRect(point.x(), point.y() - locationInContainer.topPadding(), 1, locationInContainer.topPadding() + locationInContainer.bottomPadding() + 1) :
293        IntRect(point.x() - locationInContainer.leftPadding(), point.y(), locationInContainer.rightPadding() + locationInContainer.leftPadding() + 1, 1);
294
295    if (!anyLineIntersectsRect(renderer, rect, accumulatedOffset))
296        return false;
297
298    // See if our root lines contain the point.  If so, then we hit test
299    // them further.  Note that boxes can easily overlap, so we can't make any assumptions
300    // based off positions of our first line box or our last line box.
301    for (InlineFlowBox* curr = lastLineBox(); curr; curr = curr->prevLineBox()) {
302        const RootInlineBox& rootBox = curr->root();
303        if (rangeIntersectsRect(renderer, curr->logicalTopVisualOverflow(rootBox.lineTop()), curr->logicalBottomVisualOverflow(rootBox.lineBottom()), rect, accumulatedOffset)) {
304            bool inside = curr->nodeAtPoint(request, result, locationInContainer, accumulatedOffset, rootBox.lineTop(), rootBox.lineBottom());
305            if (inside) {
306                renderer->updateHitTestResult(result, locationInContainer.point() - toLayoutSize(accumulatedOffset));
307                return true;
308            }
309        }
310    }
311
312    return false;
313}
314
315void RenderLineBoxList::dirtyLinesFromChangedChild(RenderBoxModelObject* container, RenderObject* child)
316{
317    ASSERT(container->isRenderInline() || container->isRenderBlockFlow());
318    if (!container->parent() || (container->isRenderBlockFlow() && container->selfNeedsLayout()))
319        return;
320
321    RenderInline* inlineContainer = container->isRenderInline() ? toRenderInline(container) : 0;
322    InlineBox* firstBox = inlineContainer ? inlineContainer->firstLineBoxIncludingCulling() : firstLineBox();
323
324    // If we have no first line box, then just bail early.
325    if (!firstBox) {
326        // For an empty inline, go ahead and propagate the check up to our parent, unless the parent
327        // is already dirty.
328        if (container->isInline() && !container->ancestorLineBoxDirty()) {
329            container->parent()->dirtyLinesFromChangedChild(container);
330            container->setAncestorLineBoxDirty(); // Mark the container to avoid dirtying the same lines again across multiple destroy() calls of the same subtree.
331        }
332        return;
333    }
334
335    // Try to figure out which line box we belong in.  First try to find a previous
336    // line box by examining our siblings.  If we didn't find a line box, then use our
337    // parent's first line box.
338    RootInlineBox* box = 0;
339    RenderObject* curr = 0;
340    for (curr = child->previousSibling(); curr; curr = curr->previousSibling()) {
341        if (curr->isFloatingOrOutOfFlowPositioned())
342            continue;
343
344        if (curr->isReplaced()) {
345            if (auto wrapper = toRenderBox(curr)->inlineBoxWrapper())
346                box = &wrapper->root();
347        } if (curr->isLineBreak()) {
348            if (auto wrapper = toRenderLineBreak(curr)->inlineBoxWrapper())
349                box = &wrapper->root();
350        } else if (curr->isText()) {
351            InlineTextBox* textBox = toRenderText(curr)->lastTextBox();
352            if (textBox)
353                box = &textBox->root();
354        } else if (curr->isRenderInline()) {
355            InlineBox* lastSiblingBox = toRenderInline(curr)->lastLineBoxIncludingCulling();
356            if (lastSiblingBox)
357                box = &lastSiblingBox->root();
358        }
359
360        if (box)
361            break;
362    }
363    if (!box) {
364        if (inlineContainer && !inlineContainer->alwaysCreateLineBoxes()) {
365            // https://bugs.webkit.org/show_bug.cgi?id=60778
366            // We may have just removed a <br> with no line box that was our first child. In this case
367            // we won't find a previous sibling, but firstBox can be pointing to a following sibling.
368            // This isn't good enough, since we won't locate the root line box that encloses the removed
369            // <br>. We have to just over-invalidate a bit and go up to our parent.
370            if (!inlineContainer->ancestorLineBoxDirty()) {
371                inlineContainer->parent()->dirtyLinesFromChangedChild(inlineContainer);
372                inlineContainer->setAncestorLineBoxDirty(); // Mark the container to avoid dirtying the same lines again across multiple destroy() calls of the same subtree.
373            }
374            return;
375        }
376        box = &firstBox->root();
377    }
378
379    // If we found a line box, then dirty it.
380    if (box) {
381        RootInlineBox* adjacentBox;
382        box->markDirty();
383
384        // dirty the adjacent lines that might be affected
385        // NOTE: we dirty the previous line because RootInlineBox objects cache
386        // the address of the first object on the next line after a BR, which we may be
387        // invalidating here.  For more info, see how RenderBlock::layoutInlineChildren
388        // calls setLineBreakInfo with the result of findNextLineBreak.  findNextLineBreak,
389        // despite the name, actually returns the first RenderObject after the BR.
390        // <rdar://problem/3849947> "Typing after pasting line does not appear until after window resize."
391        adjacentBox = box->prevRootBox();
392        if (adjacentBox)
393            adjacentBox->markDirty();
394        adjacentBox = box->nextRootBox();
395        // If |child| has been inserted before the first element in the linebox, but after collapsed leading
396        // space, the search for |child|'s linebox will go past the leading space to the previous linebox and select that
397        // one as |box|. If we hit that situation here, dirty the |box| actually containing the child too.
398        bool insertedAfterLeadingSpace = box->lineBreakObj() == child->previousSibling();
399        if (adjacentBox && (adjacentBox->lineBreakObj() == child || child->isBR() || (curr && curr->isBR())
400            || insertedAfterLeadingSpace || isIsolated(container->style().unicodeBidi())))
401            adjacentBox->markDirty();
402    }
403}
404
405#ifndef NDEBUG
406
407void RenderLineBoxList::checkConsistency() const
408{
409#ifdef CHECK_CONSISTENCY
410    const InlineFlowBox* prev = 0;
411    for (const InlineFlowBox* child = m_firstLineBox; child != 0; child = child->nextLineBox()) {
412        ASSERT(child->prevLineBox() == prev);
413        prev = child;
414    }
415    ASSERT(prev == m_lastLineBox);
416#endif
417}
418
419#endif
420
421}
422