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