0a0471dc186e0a999b7ebc3fcc97ad900096c6a1
[WebKit-https.git] / Source / WebCore / rendering / RenderBlock.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2007 David Smith (catfish.man@gmail.com)
5  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
6  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23
24 #include "config.h"
25 #include "RenderBlock.h"
26
27 #include "ColumnInfo.h"
28 #include "Document.h"
29 #include "Element.h"
30 #include "FloatQuad.h"
31 #include "Frame.h"
32 #include "FrameView.h"
33 #include "GraphicsContext.h"
34 #include "HTMLFormElement.h"
35 #include "HTMLNames.h"
36 #include "HitTestResult.h"
37 #include "InlineIterator.h"
38 #include "InlineTextBox.h"
39 #include "PaintInfo.h"
40 #include "RenderCombineText.h"
41 #include "RenderFlexibleBox.h"
42 #include "RenderImage.h"
43 #include "RenderInline.h"
44 #include "RenderLayer.h"
45 #include "RenderMarquee.h"
46 #include "RenderReplica.h"
47 #include "RenderTableCell.h"
48 #include "RenderTextFragment.h"
49 #include "RenderTheme.h"
50 #include "RenderView.h"
51 #include "SelectionController.h"
52 #include "Settings.h"
53 #include "TextRun.h"
54 #include "TransformState.h"
55 #include <wtf/StdLibExtras.h>
56
57 using namespace std;
58 using namespace WTF;
59 using namespace Unicode;
60
61 namespace WebCore {
62
63 using namespace HTMLNames;
64
65 typedef WTF::HashMap<const RenderBox*, ColumnInfo*> ColumnInfoMap;
66 static ColumnInfoMap* gColumnInfoMap = 0;
67
68 typedef WTF::HashMap<const RenderBlock*, HashSet<RenderBox*>*> PercentHeightDescendantsMap;
69 static PercentHeightDescendantsMap* gPercentHeightDescendantsMap = 0;
70
71 typedef WTF::HashMap<const RenderBox*, HashSet<RenderBlock*>*> PercentHeightContainerMap;
72 static PercentHeightContainerMap* gPercentHeightContainerMap = 0;
73     
74 typedef WTF::HashMap<RenderBlock*, ListHashSet<RenderInline*>*> ContinuationOutlineTableMap;
75
76 typedef WTF::HashSet<RenderBlock*> DelayedUpdateScrollInfoSet;
77 static int gDelayUpdateScrollInfo = 0;
78 static DelayedUpdateScrollInfoSet* gDelayedUpdateScrollInfoSet = 0;
79
80 // Our MarginInfo state used when laying out block children.
81 RenderBlock::MarginInfo::MarginInfo(RenderBlock* block, int beforeBorderPadding, int afterBorderPadding)
82     : m_atBeforeSideOfBlock(true)
83     , m_atAfterSideOfBlock(false)
84     , m_marginBeforeQuirk(false)
85     , m_marginAfterQuirk(false)
86     , m_determinedMarginBeforeQuirk(false)
87 {
88     // Whether or not we can collapse our own margins with our children.  We don't do this
89     // if we had any border/padding (obviously), if we're the root or HTML elements, or if
90     // we're positioned, floating, a table cell.
91     m_canCollapseWithChildren = !block->isRenderView() && !block->isRoot() && !block->isPositioned()
92         && !block->isFloating() && !block->isTableCell() && !block->hasOverflowClip() && !block->isInlineBlockOrInlineTable()
93         && !block->isWritingModeRoot();
94
95     m_canCollapseMarginBeforeWithChildren = m_canCollapseWithChildren && (beforeBorderPadding == 0) && block->style()->marginBeforeCollapse() != MSEPARATE;
96
97     // If any height other than auto is specified in CSS, then we don't collapse our bottom
98     // margins with our children's margins.  To do otherwise would be to risk odd visual
99     // effects when the children overflow out of the parent block and yet still collapse
100     // with it.  We also don't collapse if we have any bottom border/padding.
101     m_canCollapseMarginAfterWithChildren = m_canCollapseWithChildren && (afterBorderPadding == 0) &&
102         (block->style()->logicalHeight().isAuto() && block->style()->logicalHeight().value() == 0) && block->style()->marginAfterCollapse() != MSEPARATE;
103     
104     m_quirkContainer = block->isTableCell() || block->isBody() || block->style()->marginBeforeCollapse() == MDISCARD || 
105         block->style()->marginAfterCollapse() == MDISCARD;
106
107     m_positiveMargin = m_canCollapseMarginBeforeWithChildren ? block->maxPositiveMarginBefore() : 0;
108     m_negativeMargin = m_canCollapseMarginBeforeWithChildren ? block->maxNegativeMarginBefore() : 0;
109 }
110
111 // -------------------------------------------------------------------------------------------------------
112
113 RenderBlock::RenderBlock(Node* node)
114       : RenderBox(node)
115       , m_lineHeight(-1)
116       , m_beingDestroyed(false)
117 {
118     setChildrenInline(true);
119 }
120
121 RenderBlock::~RenderBlock()
122 {
123     if (m_floatingObjects)
124         deleteAllValues(m_floatingObjects->set());
125     
126     if (hasColumns())
127         delete gColumnInfoMap->take(this);
128
129     if (gPercentHeightDescendantsMap) {
130         if (HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->take(this)) {
131             HashSet<RenderBox*>::iterator end = descendantSet->end();
132             for (HashSet<RenderBox*>::iterator descendant = descendantSet->begin(); descendant != end; ++descendant) {
133                 HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->get(*descendant);
134                 ASSERT(containerSet);
135                 if (!containerSet)
136                     continue;
137                 ASSERT(containerSet->contains(this));
138                 containerSet->remove(this);
139                 if (containerSet->isEmpty()) {
140                     gPercentHeightContainerMap->remove(*descendant);
141                     delete containerSet;
142                 }
143             }
144             delete descendantSet;
145         }
146     }
147 }
148
149 void RenderBlock::destroy()
150 {
151     // Mark as being destroyed to avoid trouble with merges in removeChild().
152     m_beingDestroyed = true;
153
154     // Make sure to destroy anonymous children first while they are still connected to the rest of the tree, so that they will
155     // properly dirty line boxes that they are removed from. Effects that do :before/:after only on hover could crash otherwise.
156     children()->destroyLeftoverChildren();
157
158     // Destroy our continuation before anything other than anonymous children.
159     // The reason we don't destroy it before anonymous children is that they may
160     // have continuations of their own that are anonymous children of our continuation.
161     RenderBoxModelObject* continuation = this->continuation();
162     if (continuation) {
163         continuation->destroy();
164         setContinuation(0);
165     }
166     
167     if (!documentBeingDestroyed()) {
168         if (firstLineBox()) {
169             // We can't wait for RenderBox::destroy to clear the selection,
170             // because by then we will have nuked the line boxes.
171             // FIXME: The SelectionController should be responsible for this when it
172             // is notified of DOM mutations.
173             if (isSelectionBorder())
174                 view()->clearSelection();
175
176             // If we are an anonymous block, then our line boxes might have children
177             // that will outlast this block. In the non-anonymous block case those
178             // children will be destroyed by the time we return from this function.
179             if (isAnonymousBlock()) {
180                 for (InlineFlowBox* box = firstLineBox(); box; box = box->nextLineBox()) {
181                     while (InlineBox* childBox = box->firstChild())
182                         childBox->remove();
183                 }
184             }
185         } else if (isInline() && parent())
186             parent()->dirtyLinesFromChangedChild(this);
187     }
188
189     m_lineBoxes.deleteLineBoxes(renderArena());
190
191     RenderBox::destroy();
192 }
193
194 void RenderBlock::styleWillChange(StyleDifference diff, const RenderStyle* newStyle)
195 {
196     setReplaced(newStyle->isDisplayInlineType());
197     
198     if (style() && parent() && diff == StyleDifferenceLayout && style()->position() != newStyle->position()) {
199         if (newStyle->position() == StaticPosition)
200             // Clear our positioned objects list. Our absolutely positioned descendants will be
201             // inserted into our containing block's positioned objects list during layout.
202             removePositionedObjects(0);
203         else if (style()->position() == StaticPosition) {
204             // Remove our absolutely positioned descendants from their current containing block.
205             // They will be inserted into our positioned objects list during layout.
206             RenderObject* cb = parent();
207             while (cb && (cb->style()->position() == StaticPosition || (cb->isInline() && !cb->isReplaced())) && !cb->isRenderView()) {
208                 if (cb->style()->position() == RelativePosition && cb->isInline() && !cb->isReplaced()) {
209                     cb = cb->containingBlock();
210                     break;
211                 }
212                 cb = cb->parent();
213             }
214             
215             if (cb->isRenderBlock())
216                 toRenderBlock(cb)->removePositionedObjects(this);
217         }
218     }
219
220     RenderBox::styleWillChange(diff, newStyle);
221 }
222
223 void RenderBlock::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
224 {
225     RenderBox::styleDidChange(diff, oldStyle);
226
227     if (!isAnonymousBlock()) {
228         // Ensure that all of our continuation blocks pick up the new style.
229         for (RenderBlock* currCont = blockElementContinuation(); currCont; currCont = currCont->blockElementContinuation()) {
230             RenderBoxModelObject* nextCont = currCont->continuation();
231             currCont->setContinuation(0);
232             currCont->setStyle(style());
233             currCont->setContinuation(nextCont);
234         }
235     }
236
237     // FIXME: We could save this call when the change only affected non-inherited properties
238     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
239         if (child->isAnonymousBlock()) {
240             RefPtr<RenderStyle> newStyle = RenderStyle::createAnonymousStyle(style());
241             if (style()->specifiesColumns()) {
242                 if (child->style()->specifiesColumns())
243                     newStyle->inheritColumnPropertiesFrom(style());
244                 if (child->style()->columnSpan())
245                     newStyle->setColumnSpan(true);
246             }
247             newStyle->setDisplay(BLOCK);
248             child->setStyle(newStyle.release());
249         }
250     }
251
252     m_lineHeight = -1;
253
254     // Update pseudos for :before and :after now.
255     if (!isAnonymous() && document()->usesBeforeAfterRules() && canHaveChildren()) {
256         updateBeforeAfterContent(BEFORE);
257         updateBeforeAfterContent(AFTER);
258     }
259 }
260
261 void RenderBlock::updateBeforeAfterContent(PseudoId pseudoId)
262 {
263     // If this is an anonymous wrapper, then the parent applies its own pseudo-element style to it.
264     if (parent() && parent()->createsAnonymousWrapper())
265         return;
266     return children()->updateBeforeAfterContent(this, pseudoId);
267 }
268
269 RenderBlock* RenderBlock::continuationBefore(RenderObject* beforeChild)
270 {
271     if (beforeChild && beforeChild->parent() == this)
272         return this;
273
274     RenderBlock* curr = toRenderBlock(continuation());
275     RenderBlock* nextToLast = this;
276     RenderBlock* last = this;
277     while (curr) {
278         if (beforeChild && beforeChild->parent() == curr) {
279             if (curr->firstChild() == beforeChild)
280                 return last;
281             return curr;
282         }
283
284         nextToLast = last;
285         last = curr;
286         curr = toRenderBlock(curr->continuation());
287     }
288
289     if (!beforeChild && !last->firstChild())
290         return nextToLast;
291     return last;
292 }
293
294 void RenderBlock::addChildToContinuation(RenderObject* newChild, RenderObject* beforeChild)
295 {
296     RenderBlock* flow = continuationBefore(beforeChild);
297     ASSERT(!beforeChild || beforeChild->parent()->isAnonymousColumnSpanBlock() || beforeChild->parent()->isRenderBlock());
298     RenderBoxModelObject* beforeChildParent = 0;
299     if (beforeChild)
300         beforeChildParent = toRenderBoxModelObject(beforeChild->parent());
301     else {
302         RenderBoxModelObject* cont = flow->continuation();
303         if (cont)
304             beforeChildParent = cont;
305         else
306             beforeChildParent = flow;
307     }
308
309     if (newChild->isFloatingOrPositioned())
310         return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
311
312     // A continuation always consists of two potential candidates: a block or an anonymous
313     // column span box holding column span children.
314     bool childIsNormal = newChild->isInline() || !newChild->style()->columnSpan();
315     bool bcpIsNormal = beforeChildParent->isInline() || !beforeChildParent->style()->columnSpan();
316     bool flowIsNormal = flow->isInline() || !flow->style()->columnSpan();
317
318     if (flow == beforeChildParent)
319         return flow->addChildIgnoringContinuation(newChild, beforeChild);
320     
321     // The goal here is to match up if we can, so that we can coalesce and create the
322     // minimal # of continuations needed for the inline.
323     if (childIsNormal == bcpIsNormal)
324         return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
325     if (flowIsNormal == childIsNormal)
326         return flow->addChildIgnoringContinuation(newChild, 0); // Just treat like an append.
327     return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
328 }
329
330
331 void RenderBlock::addChildToAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)
332 {
333     ASSERT(!continuation()); // We don't yet support column spans that aren't immediate children of the multi-column block.
334         
335     // The goal is to locate a suitable box in which to place our child.
336     RenderBlock* beforeChildParent = toRenderBlock(beforeChild && beforeChild->parent()->isRenderBlock() ? beforeChild->parent() : lastChild());
337     
338     // If the new child is floating or positioned it can just go in that block.
339     if (newChild->isFloatingOrPositioned())
340         return beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
341
342     // See if the child can be placed in the box.
343     bool newChildHasColumnSpan = newChild->style()->columnSpan() && !newChild->isInline();
344     bool beforeChildParentHoldsColumnSpans = beforeChildParent->isAnonymousColumnSpanBlock();
345
346     if (newChildHasColumnSpan == beforeChildParentHoldsColumnSpans)
347         return beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
348
349     if (!beforeChild) {
350         // Create a new block of the correct type.
351         RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();
352         children()->appendChildNode(this, newBox);
353         newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);
354         return;
355     }
356
357     RenderObject* immediateChild = beforeChild;
358     bool isPreviousBlockViable = true;
359     while (immediateChild->parent() != this) {
360         if (isPreviousBlockViable)
361             isPreviousBlockViable = !immediateChild->previousSibling();
362         immediateChild = immediateChild->parent();
363     }
364     if (isPreviousBlockViable && immediateChild->previousSibling())
365         return toRenderBlock(immediateChild->previousSibling())->addChildIgnoringAnonymousColumnBlocks(newChild, 0); // Treat like an append.
366         
367     // Split our anonymous blocks.
368     RenderObject* newBeforeChild = splitAnonymousBlocksAroundChild(beforeChild);
369     
370     // Create a new anonymous box of the appropriate type.
371     RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();
372     children()->insertChildNode(this, newBox, newBeforeChild);
373     newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);
374     return;
375 }
376
377 RenderBlock* RenderBlock::containingColumnsBlock(bool allowAnonymousColumnBlock)
378 {
379     for (RenderObject* curr = this; curr; curr = curr->parent()) {
380         if (!curr->isRenderBlock() || curr->isFloatingOrPositioned() || curr->isTableCell() || curr->isRoot() || curr->isRenderView() || curr->hasOverflowClip()
381             || curr->isInlineBlockOrInlineTable())
382             return 0;
383         
384         RenderBlock* currBlock = toRenderBlock(curr);
385         if (currBlock->style()->specifiesColumns() && (allowAnonymousColumnBlock || !currBlock->isAnonymousColumnsBlock()))
386             return currBlock;
387             
388         if (currBlock->isAnonymousColumnSpanBlock())
389             return 0;
390     }
391     return 0;
392 }
393
394 RenderBlock* RenderBlock::clone() const
395 {
396     RenderBlock* cloneBlock;
397     if (isAnonymousBlock())
398         cloneBlock = createAnonymousBlock();
399     else {
400         cloneBlock = new (renderArena()) RenderBlock(node());
401         cloneBlock->setStyle(style());
402     }
403     cloneBlock->setChildrenInline(childrenInline());
404     return cloneBlock;
405 }
406
407 void RenderBlock::splitBlocks(RenderBlock* fromBlock, RenderBlock* toBlock,
408                               RenderBlock* middleBlock,
409                               RenderObject* beforeChild, RenderBoxModelObject* oldCont)
410 {
411     // Create a clone of this inline.
412     RenderBlock* cloneBlock = clone();
413     if (!isAnonymousBlock())
414         cloneBlock->setContinuation(oldCont);
415
416     // Now take all of the children from beforeChild to the end and remove
417     // them from |this| and place them in the clone.
418     if (!beforeChild && isAfterContent(lastChild()))
419         beforeChild = lastChild();
420     moveChildrenTo(cloneBlock, beforeChild, 0);
421     
422     // Hook |clone| up as the continuation of the middle block.
423     if (!cloneBlock->isAnonymousBlock())
424         middleBlock->setContinuation(cloneBlock);
425
426     // We have been reparented and are now under the fromBlock.  We need
427     // to walk up our block parent chain until we hit the containing anonymous columns block.
428     // Once we hit the anonymous columns block we're done.
429     RenderBoxModelObject* curr = toRenderBoxModelObject(parent());
430     RenderBoxModelObject* currChild = this;
431     
432     while (curr && curr != fromBlock) {
433         ASSERT(curr->isRenderBlock());
434         
435         RenderBlock* blockCurr = toRenderBlock(curr);
436         
437         // Create a new clone.
438         RenderBlock* cloneChild = cloneBlock;
439         cloneBlock = blockCurr->clone();
440
441         // Insert our child clone as the first child.
442         cloneBlock->children()->appendChildNode(cloneBlock, cloneChild);
443
444         // Hook the clone up as a continuation of |curr|.  Note we do encounter
445         // anonymous blocks possibly as we walk up the block chain.  When we split an
446         // anonymous block, there's no need to do any continuation hookup, since we haven't
447         // actually split a real element.
448         if (!blockCurr->isAnonymousBlock()) {
449             oldCont = blockCurr->continuation();
450             blockCurr->setContinuation(cloneBlock);
451             cloneBlock->setContinuation(oldCont);
452         }
453
454         // Someone may have indirectly caused a <q> to split.  When this happens, the :after content
455         // has to move into the inline continuation.  Call updateBeforeAfterContent to ensure that the inline's :after
456         // content gets properly destroyed.
457         if (document()->usesBeforeAfterRules())
458             blockCurr->children()->updateBeforeAfterContent(blockCurr, AFTER);
459
460         // Now we need to take all of the children starting from the first child
461         // *after* currChild and append them all to the clone.
462         RenderObject* afterContent = isAfterContent(cloneBlock->lastChild()) ? cloneBlock->lastChild() : 0;
463         blockCurr->moveChildrenTo(cloneBlock, currChild->nextSibling(), 0, afterContent);
464
465         // Keep walking up the chain.
466         currChild = curr;
467         curr = toRenderBoxModelObject(curr->parent());
468     }
469
470     // Now we are at the columns block level. We need to put the clone into the toBlock.
471     toBlock->children()->appendChildNode(toBlock, cloneBlock);
472
473     // Now take all the children after currChild and remove them from the fromBlock
474     // and put them in the toBlock.
475     fromBlock->moveChildrenTo(toBlock, currChild->nextSibling(), 0);
476 }
477
478 void RenderBlock::splitFlow(RenderObject* beforeChild, RenderBlock* newBlockBox,
479                             RenderObject* newChild, RenderBoxModelObject* oldCont)
480 {
481     RenderBlock* pre = 0;
482     RenderBlock* block = containingColumnsBlock();
483     
484     // Delete our line boxes before we do the inline split into continuations.
485     block->deleteLineBoxTree();
486     
487     bool madeNewBeforeBlock = false;
488     if (block->isAnonymousColumnsBlock()) {
489         // We can reuse this block and make it the preBlock of the next continuation.
490         pre = block;
491         pre->removePositionedObjects(0);
492         block = toRenderBlock(block->parent());
493     } else {
494         // No anonymous block available for use.  Make one.
495         pre = block->createAnonymousColumnsBlock();
496         pre->setChildrenInline(false);
497         madeNewBeforeBlock = true;
498     }
499
500     RenderBlock* post = block->createAnonymousColumnsBlock();
501     post->setChildrenInline(false);
502
503     RenderObject* boxFirst = madeNewBeforeBlock ? block->firstChild() : pre->nextSibling();
504     if (madeNewBeforeBlock)
505         block->children()->insertChildNode(block, pre, boxFirst);
506     block->children()->insertChildNode(block, newBlockBox, boxFirst);
507     block->children()->insertChildNode(block, post, boxFirst);
508     block->setChildrenInline(false);
509     
510     if (madeNewBeforeBlock)
511         block->moveChildrenTo(pre, boxFirst, 0);
512
513     splitBlocks(pre, post, newBlockBox, beforeChild, oldCont);
514
515     // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
516     // time in makeChildrenNonInline by just setting this explicitly up front.
517     newBlockBox->setChildrenInline(false);
518
519     // We delayed adding the newChild until now so that the |newBlockBox| would be fully
520     // connected, thus allowing newChild access to a renderArena should it need
521     // to wrap itself in additional boxes (e.g., table construction).
522     newBlockBox->addChild(newChild);
523
524     // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
525     // get deleted properly.  Because objects moves from the pre block into the post block, we want to
526     // make new line boxes instead of leaving the old line boxes around.
527     pre->setNeedsLayoutAndPrefWidthsRecalc();
528     block->setNeedsLayoutAndPrefWidthsRecalc();
529     post->setNeedsLayoutAndPrefWidthsRecalc();
530 }
531
532 RenderObject* RenderBlock::splitAnonymousBlocksAroundChild(RenderObject* beforeChild)
533 {
534     while (beforeChild->parent() != this) {
535         RenderBlock* blockToSplit = toRenderBlock(beforeChild->parent());
536         if (blockToSplit->firstChild() != beforeChild) {
537             // We have to split the parentBlock into two blocks.
538             RenderBlock* post = createAnonymousBlockWithSameTypeAs(blockToSplit);
539             post->setChildrenInline(blockToSplit->childrenInline());
540             RenderBlock* parentBlock = toRenderBlock(blockToSplit->parent());
541             parentBlock->children()->insertChildNode(parentBlock, post, blockToSplit->nextSibling());
542             blockToSplit->moveChildrenTo(post, beforeChild, 0, blockToSplit->hasLayer());
543             post->setNeedsLayoutAndPrefWidthsRecalc();
544             blockToSplit->setNeedsLayoutAndPrefWidthsRecalc();
545             beforeChild = post;
546         } else
547             beforeChild = blockToSplit;
548     }
549     return beforeChild;
550 }
551
552 void RenderBlock::makeChildrenAnonymousColumnBlocks(RenderObject* beforeChild, RenderBlock* newBlockBox, RenderObject* newChild)
553 {
554     RenderBlock* pre = 0;
555     RenderBlock* post = 0;
556     RenderBlock* block = this; // Eventually block will not just be |this|, but will also be a block nested inside |this|.  Assign to a variable
557                                // so that we don't have to patch all of the rest of the code later on.
558     
559     // Delete the block's line boxes before we do the split.
560     block->deleteLineBoxTree();
561
562     if (beforeChild && beforeChild->parent() != this)
563         beforeChild = splitAnonymousBlocksAroundChild(beforeChild);
564
565     if (beforeChild != firstChild()) {
566         pre = block->createAnonymousColumnsBlock();
567         pre->setChildrenInline(block->childrenInline());
568     }
569
570     if (beforeChild) {
571         post = block->createAnonymousColumnsBlock();
572         post->setChildrenInline(block->childrenInline());
573     }
574
575     RenderObject* boxFirst = block->firstChild();
576     if (pre)
577         block->children()->insertChildNode(block, pre, boxFirst);
578     block->children()->insertChildNode(block, newBlockBox, boxFirst);
579     if (post)
580         block->children()->insertChildNode(block, post, boxFirst);
581     block->setChildrenInline(false);
582     
583     // The pre/post blocks always have layers, so we know to always do a full insert/remove (so we pass true as the last argument).
584     block->moveChildrenTo(pre, boxFirst, beforeChild, true);
585     block->moveChildrenTo(post, beforeChild, 0, true);
586
587     // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
588     // time in makeChildrenNonInline by just setting this explicitly up front.
589     newBlockBox->setChildrenInline(false);
590
591     // We delayed adding the newChild until now so that the |newBlockBox| would be fully
592     // connected, thus allowing newChild access to a renderArena should it need
593     // to wrap itself in additional boxes (e.g., table construction).
594     newBlockBox->addChild(newChild);
595
596     // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
597     // get deleted properly.  Because objects moved from the pre block into the post block, we want to
598     // make new line boxes instead of leaving the old line boxes around.
599     if (pre)
600         pre->setNeedsLayoutAndPrefWidthsRecalc();
601     block->setNeedsLayoutAndPrefWidthsRecalc();
602     if (post)
603         post->setNeedsLayoutAndPrefWidthsRecalc();
604 }
605
606 RenderBlock* RenderBlock::columnsBlockForSpanningElement(RenderObject* newChild)
607 {
608     // FIXME: This function is the gateway for the addition of column-span support.  It will
609     // be added to in three stages:
610     // (1) Immediate children of a multi-column block can span.
611     // (2) Nested block-level children with only block-level ancestors between them and the multi-column block can span.
612     // (3) Nested children with block or inline ancestors between them and the multi-column block can span (this is when we
613     // cross the streams and have to cope with both types of continuations mixed together).
614     // This function currently supports (1) and (2).
615     RenderBlock* columnsBlockAncestor = 0;
616     if (!newChild->isText() && newChild->style()->columnSpan() && !newChild->isFloatingOrPositioned()
617         && !newChild->isInline() && !isAnonymousColumnSpanBlock()) {
618         if (style()->specifiesColumns())
619             columnsBlockAncestor = this;
620         else if (parent() && parent()->isRenderBlock())
621             columnsBlockAncestor = toRenderBlock(parent())->containingColumnsBlock(false);
622     }
623     return columnsBlockAncestor;
624 }
625
626 void RenderBlock::addChildIgnoringAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)
627 {
628     // Make sure we don't append things after :after-generated content if we have it.
629     if (!beforeChild) {
630         RenderObject* lastRenderer = lastChild();
631         if (isAfterContent(lastRenderer))
632             beforeChild = lastRenderer;
633         else if (lastRenderer && lastRenderer->isAnonymousBlock() && isAfterContent(lastRenderer->lastChild()))
634             beforeChild = lastRenderer->lastChild();
635     }
636
637     // If the requested beforeChild is not one of our children, then this is because
638     // there is an anonymous container within this object that contains the beforeChild.
639     if (beforeChild && beforeChild->parent() != this) {
640         RenderObject* anonymousChild = beforeChild->parent();
641         ASSERT(anonymousChild);
642
643         while (anonymousChild->parent() != this)
644             anonymousChild = anonymousChild->parent();
645
646         ASSERT(anonymousChild->isAnonymous());
647
648         if (anonymousChild->isAnonymousBlock()) {
649             // Insert the child into the anonymous block box instead of here.
650             if (newChild->isInline() || beforeChild->parent()->firstChild() != beforeChild)
651                 beforeChild->parent()->addChild(newChild, beforeChild);
652             else
653                 addChild(newChild, beforeChild->parent());
654             return;
655         }
656
657         ASSERT(anonymousChild->isTable());
658         if ((newChild->isTableCol() && newChild->style()->display() == TABLE_COLUMN_GROUP)
659                 || (newChild->isRenderBlock() && newChild->style()->display() == TABLE_CAPTION)
660                 || newChild->isTableSection()
661                 || newChild->isTableRow()
662                 || newChild->isTableCell()) {
663             // Insert into the anonymous table.
664             anonymousChild->addChild(newChild, beforeChild);
665             return;
666         }
667
668         // Go on to insert before the anonymous table.
669         beforeChild = anonymousChild;
670     }
671
672     // Check for a spanning element in columns.
673     RenderBlock* columnsBlockAncestor = columnsBlockForSpanningElement(newChild);
674     if (columnsBlockAncestor) {
675         // We are placing a column-span element inside a block. 
676         RenderBlock* newBox = createAnonymousColumnSpanBlock();
677         
678         if (columnsBlockAncestor != this) {
679             // We are nested inside a multi-column element and are being split by the span.  We have to break up
680             // our block into continuations.
681             RenderBoxModelObject* oldContinuation = continuation();
682             setContinuation(newBox);
683
684             // Someone may have put a <p> inside a <q>, causing a split.  When this happens, the :after content
685             // has to move into the inline continuation.  Call updateBeforeAfterContent to ensure that our :after
686             // content gets properly destroyed.
687             bool isLastChild = (beforeChild == lastChild());
688             if (document()->usesBeforeAfterRules())
689                 children()->updateBeforeAfterContent(this, AFTER);
690             if (isLastChild && beforeChild != lastChild())
691                 beforeChild = 0; // We destroyed the last child, so now we need to update our insertion
692                                  // point to be 0.  It's just a straight append now.
693
694             splitFlow(beforeChild, newBox, newChild, oldContinuation);
695             return;
696         }
697
698         // We have to perform a split of this block's children.  This involves creating an anonymous block box to hold
699         // the column-spanning |newChild|.  We take all of the children from before |newChild| and put them into
700         // one anonymous columns block, and all of the children after |newChild| go into another anonymous block.
701         makeChildrenAnonymousColumnBlocks(beforeChild, newBox, newChild);
702         return;
703     }
704
705     bool madeBoxesNonInline = false;
706
707     // A block has to either have all of its children inline, or all of its children as blocks.
708     // So, if our children are currently inline and a block child has to be inserted, we move all our
709     // inline children into anonymous block boxes.
710     if (childrenInline() && !newChild->isInline() && !newChild->isFloatingOrPositioned()) {
711         // This is a block with inline content. Wrap the inline content in anonymous blocks.
712         makeChildrenNonInline(beforeChild);
713         madeBoxesNonInline = true;
714
715         if (beforeChild && beforeChild->parent() != this) {
716             beforeChild = beforeChild->parent();
717             ASSERT(beforeChild->isAnonymousBlock());
718             ASSERT(beforeChild->parent() == this);
719         }
720     } else if (!childrenInline() && (newChild->isFloatingOrPositioned() || newChild->isInline())) {
721         // If we're inserting an inline child but all of our children are blocks, then we have to make sure
722         // it is put into an anomyous block box. We try to use an existing anonymous box if possible, otherwise
723         // a new one is created and inserted into our list of children in the appropriate position.
724         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : lastChild();
725
726         if (afterChild && afterChild->isAnonymousBlock()) {
727             afterChild->addChild(newChild);
728             return;
729         }
730
731         if (newChild->isInline()) {
732             // No suitable existing anonymous box - create a new one.
733             RenderBlock* newBox = createAnonymousBlock();
734             RenderBox::addChild(newBox, beforeChild);
735             newBox->addChild(newChild);
736             return;
737         }
738     }
739
740     RenderBox::addChild(newChild, beforeChild);
741
742     if (madeBoxesNonInline && parent() && isAnonymousBlock() && parent()->isRenderBlock())
743         toRenderBlock(parent())->removeLeftoverAnonymousBlock(this);
744     // this object may be dead here
745 }
746
747 void RenderBlock::addChild(RenderObject* newChild, RenderObject* beforeChild)
748 {
749     if (continuation() && !isAnonymousBlock())
750         return addChildToContinuation(newChild, beforeChild);
751     return addChildIgnoringContinuation(newChild, beforeChild);
752 }
753
754 void RenderBlock::addChildIgnoringContinuation(RenderObject* newChild, RenderObject* beforeChild)
755 {
756     if (!isAnonymousBlock() && firstChild() && (firstChild()->isAnonymousColumnsBlock() || firstChild()->isAnonymousColumnSpanBlock()))
757         return addChildToAnonymousColumnBlocks(newChild, beforeChild);
758     return addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
759 }
760
761 static void getInlineRun(RenderObject* start, RenderObject* boundary,
762                          RenderObject*& inlineRunStart,
763                          RenderObject*& inlineRunEnd)
764 {
765     // Beginning at |start| we find the largest contiguous run of inlines that
766     // we can.  We denote the run with start and end points, |inlineRunStart|
767     // and |inlineRunEnd|.  Note that these two values may be the same if
768     // we encounter only one inline.
769     //
770     // We skip any non-inlines we encounter as long as we haven't found any
771     // inlines yet.
772     //
773     // |boundary| indicates a non-inclusive boundary point.  Regardless of whether |boundary|
774     // is inline or not, we will not include it in a run with inlines before it.  It's as though we encountered
775     // a non-inline.
776     
777     // Start by skipping as many non-inlines as we can.
778     RenderObject * curr = start;
779     bool sawInline;
780     do {
781         while (curr && !(curr->isInline() || curr->isFloatingOrPositioned()))
782             curr = curr->nextSibling();
783         
784         inlineRunStart = inlineRunEnd = curr;
785         
786         if (!curr)
787             return; // No more inline children to be found.
788         
789         sawInline = curr->isInline();
790         
791         curr = curr->nextSibling();
792         while (curr && (curr->isInline() || curr->isFloatingOrPositioned()) && (curr != boundary)) {
793             inlineRunEnd = curr;
794             if (curr->isInline())
795                 sawInline = true;
796             curr = curr->nextSibling();
797         }
798     } while (!sawInline);
799 }
800
801 void RenderBlock::deleteLineBoxTree()
802 {
803     m_lineBoxes.deleteLineBoxTree(renderArena());
804 }
805
806 RootInlineBox* RenderBlock::createRootInlineBox() 
807 {
808     return new (renderArena()) RootInlineBox(this);
809 }
810
811 RootInlineBox* RenderBlock::createAndAppendRootInlineBox()
812 {
813     RootInlineBox* rootBox = createRootInlineBox();
814     m_lineBoxes.appendLineBox(rootBox);
815     return rootBox;
816 }
817
818 void RenderBlock::moveChildTo(RenderBlock* to, RenderObject* child, RenderObject* beforeChild, bool fullRemoveInsert)
819 {
820     ASSERT(this == child->parent());
821     ASSERT(!beforeChild || to == beforeChild->parent());
822     to->children()->insertChildNode(to, children()->removeChildNode(this, child, fullRemoveInsert), beforeChild, fullRemoveInsert);
823 }
824
825 void RenderBlock::moveChildrenTo(RenderBlock* to, RenderObject* startChild, RenderObject* endChild, RenderObject* beforeChild, bool fullRemoveInsert)
826 {
827     ASSERT(!beforeChild || to == beforeChild->parent());
828     RenderObject* nextChild = startChild;
829     while (nextChild && nextChild != endChild) {
830         RenderObject* child = nextChild;
831         nextChild = child->nextSibling();
832         to->children()->insertChildNode(to, children()->removeChildNode(this, child, fullRemoveInsert), beforeChild, fullRemoveInsert);
833         if (child == endChild)
834             return;
835     }
836 }
837
838 void RenderBlock::makeChildrenNonInline(RenderObject *insertionPoint)
839 {    
840     // makeChildrenNonInline takes a block whose children are *all* inline and it
841     // makes sure that inline children are coalesced under anonymous
842     // blocks.  If |insertionPoint| is defined, then it represents the insertion point for
843     // the new block child that is causing us to have to wrap all the inlines.  This
844     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
845     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
846     // splitting them.
847     ASSERT(isInlineBlockOrInlineTable() || !isInline());
848     ASSERT(!insertionPoint || insertionPoint->parent() == this);
849
850     setChildrenInline(false);
851
852     RenderObject *child = firstChild();
853     if (!child)
854         return;
855
856     deleteLineBoxTree();
857
858     while (child) {
859         RenderObject *inlineRunStart, *inlineRunEnd;
860         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
861
862         if (!inlineRunStart)
863             break;
864
865         child = inlineRunEnd->nextSibling();
866
867         RenderBlock* block = createAnonymousBlock();
868         children()->insertChildNode(this, block, inlineRunStart);
869         moveChildrenTo(block, inlineRunStart, child);
870     }
871
872 #ifndef NDEBUG
873     for (RenderObject *c = firstChild(); c; c = c->nextSibling())
874         ASSERT(!c->isInline());
875 #endif
876
877     repaint();
878 }
879
880 void RenderBlock::removeLeftoverAnonymousBlock(RenderBlock* child)
881 {
882     ASSERT(child->isAnonymousBlock());
883     ASSERT(!child->childrenInline());
884     
885     if (child->continuation() || (child->firstChild() && (child->isAnonymousColumnSpanBlock() || child->isAnonymousColumnsBlock())))
886         return;
887     
888     RenderObject* firstAnChild = child->m_children.firstChild();
889     RenderObject* lastAnChild = child->m_children.lastChild();
890     if (firstAnChild) {
891         RenderObject* o = firstAnChild;
892         while (o) {
893             o->setParent(this);
894             o = o->nextSibling();
895         }
896         firstAnChild->setPreviousSibling(child->previousSibling());
897         lastAnChild->setNextSibling(child->nextSibling());
898         if (child->previousSibling())
899             child->previousSibling()->setNextSibling(firstAnChild);
900         if (child->nextSibling())
901             child->nextSibling()->setPreviousSibling(lastAnChild);
902             
903         if (child == m_children.firstChild())
904             m_children.setFirstChild(firstAnChild);
905         if (child == m_children.lastChild())
906             m_children.setLastChild(lastAnChild);
907     } else {
908         if (child == m_children.firstChild())
909             m_children.setFirstChild(child->nextSibling());
910         if (child == m_children.lastChild())
911             m_children.setLastChild(child->previousSibling());
912
913         if (child->previousSibling())
914             child->previousSibling()->setNextSibling(child->nextSibling());
915         if (child->nextSibling())
916             child->nextSibling()->setPreviousSibling(child->previousSibling());
917     }
918     child->setParent(0);
919     child->setPreviousSibling(0);
920     child->setNextSibling(0);
921     
922     child->children()->setFirstChild(0);
923     child->m_next = 0;
924
925     child->destroy();
926 }
927
928 static bool canMergeContiguousAnonymousBlocks(RenderObject* oldChild, RenderObject* prev, RenderObject* next)
929 {
930     if (oldChild->documentBeingDestroyed() || oldChild->isInline() || oldChild->virtualContinuation())
931         return false;
932
933 #if ENABLE(DETAILS)
934     if (oldChild->parent() && oldChild->parent()->isDetails())
935         return false;
936 #endif
937
938     if ((prev && (!prev->isAnonymousBlock() || toRenderBlock(prev)->continuation() || toRenderBlock(prev)->beingDestroyed()))
939         || (next && (!next->isAnonymousBlock() || toRenderBlock(next)->continuation() || toRenderBlock(next)->beingDestroyed())))
940         return false;
941
942     // FIXME: This check isn't required when inline run-ins can't be split into continuations.
943     if (prev && prev->firstChild() && prev->firstChild()->isInline() && prev->firstChild()->isRunIn())
944         return false;
945
946     if ((prev && (prev->isRubyRun() || prev->isRubyBase()))
947         || (next && (next->isRubyRun() || next->isRubyBase())))
948         return false;
949
950     if (!prev || !next)
951         return true;
952
953     // Make sure the types of the anonymous blocks match up.
954     return prev->isAnonymousColumnsBlock() == next->isAnonymousColumnsBlock()
955            && prev->isAnonymousColumnSpanBlock() == next->isAnonymousColumnSpanBlock();
956 }
957
958 void RenderBlock::removeChild(RenderObject* oldChild)
959 {
960     // If this child is a block, and if our previous and next siblings are
961     // both anonymous blocks with inline content, then we can go ahead and
962     // fold the inline content back together.
963     RenderObject* prev = oldChild->previousSibling();
964     RenderObject* next = oldChild->nextSibling();
965     bool canMergeAnonymousBlocks = canMergeContiguousAnonymousBlocks(oldChild, prev, next);
966     if (canMergeAnonymousBlocks && prev && next) {
967         prev->setNeedsLayoutAndPrefWidthsRecalc();
968         RenderBlock* nextBlock = toRenderBlock(next);
969         RenderBlock* prevBlock = toRenderBlock(prev);
970        
971         if (prev->childrenInline() != next->childrenInline()) {
972             RenderBlock* inlineChildrenBlock = prev->childrenInline() ? prevBlock : nextBlock;
973             RenderBlock* blockChildrenBlock = prev->childrenInline() ? nextBlock : prevBlock;
974             
975             // Place the inline children block inside of the block children block instead of deleting it.
976             // In order to reuse it, we have to reset it to just be a generic anonymous block.  Make sure
977             // to clear out inherited column properties by just making a new style, and to also clear the
978             // column span flag if it is set.
979             ASSERT(!inlineChildrenBlock->continuation());
980             RefPtr<RenderStyle> newStyle = RenderStyle::createAnonymousStyle(style());
981             children()->removeChildNode(this, inlineChildrenBlock, inlineChildrenBlock->hasLayer());
982             inlineChildrenBlock->setStyle(newStyle);
983             
984             // Now just put the inlineChildrenBlock inside the blockChildrenBlock.
985             blockChildrenBlock->children()->insertChildNode(blockChildrenBlock, inlineChildrenBlock, prev == inlineChildrenBlock ? blockChildrenBlock->firstChild() : 0,
986                                                             inlineChildrenBlock->hasLayer() || blockChildrenBlock->hasLayer());
987             next->setNeedsLayoutAndPrefWidthsRecalc();
988             
989             // inlineChildrenBlock got reparented to blockChildrenBlock, so it is no longer a child
990             // of "this". we null out prev or next so that is not used later in the function.
991             if (inlineChildrenBlock == prevBlock)
992                 prev = 0;
993             else
994                 next = 0;
995         } else {
996             // Take all the children out of the |next| block and put them in
997             // the |prev| block.
998             nextBlock->moveAllChildrenTo(prevBlock, nextBlock->hasLayer() || prevBlock->hasLayer());        
999             
1000             // Delete the now-empty block's lines and nuke it.
1001             nextBlock->deleteLineBoxTree();
1002             nextBlock->destroy();
1003             next = 0;
1004         }
1005     }
1006
1007     RenderBox::removeChild(oldChild);
1008
1009     RenderObject* child = prev ? prev : next;
1010     if (canMergeAnonymousBlocks && child && !child->previousSibling() && !child->nextSibling() && !isFlexibleBox()) {
1011         // The removal has knocked us down to containing only a single anonymous
1012         // box.  We can go ahead and pull the content right back up into our
1013         // box.
1014         setNeedsLayoutAndPrefWidthsRecalc();
1015         setChildrenInline(child->childrenInline());
1016         RenderBlock* anonBlock = toRenderBlock(children()->removeChildNode(this, child, child->hasLayer()));
1017         anonBlock->moveAllChildrenTo(this, child->hasLayer());
1018         // Delete the now-empty block's lines and nuke it.
1019         anonBlock->deleteLineBoxTree();
1020         anonBlock->destroy();
1021     }
1022
1023     if (!firstChild() && !documentBeingDestroyed()) {
1024         // If this was our last child be sure to clear out our line boxes.
1025         if (childrenInline())
1026             lineBoxes()->deleteLineBoxes(renderArena());
1027     }
1028 }
1029
1030 bool RenderBlock::isSelfCollapsingBlock() const
1031 {
1032     // We are not self-collapsing if we
1033     // (a) have a non-zero height according to layout (an optimization to avoid wasting time)
1034     // (b) are a table,
1035     // (c) have border/padding,
1036     // (d) have a min-height
1037     // (e) have specified that one of our margins can't collapse using a CSS extension
1038     if (logicalHeight() > 0
1039         || isTable() || borderAndPaddingLogicalHeight()
1040         || style()->logicalMinHeight().isPositive()
1041         || style()->marginBeforeCollapse() == MSEPARATE || style()->marginAfterCollapse() == MSEPARATE)
1042         return false;
1043
1044     Length logicalHeightLength = style()->logicalHeight();
1045     bool hasAutoHeight = logicalHeightLength.isAuto();
1046     if (logicalHeightLength.isPercent() && !document()->inQuirksMode()) {
1047         hasAutoHeight = true;
1048         for (RenderBlock* cb = containingBlock(); !cb->isRenderView(); cb = cb->containingBlock()) {
1049             if (cb->style()->logicalHeight().isFixed() || cb->isTableCell())
1050                 hasAutoHeight = false;
1051         }
1052     }
1053
1054     // If the height is 0 or auto, then whether or not we are a self-collapsing block depends
1055     // on whether we have content that is all self-collapsing or not.
1056     if (hasAutoHeight || ((logicalHeightLength.isFixed() || logicalHeightLength.isPercent()) && logicalHeightLength.isZero())) {
1057         // If the block has inline children, see if we generated any line boxes.  If we have any
1058         // line boxes, then we can't be self-collapsing, since we have content.
1059         if (childrenInline())
1060             return !firstLineBox();
1061         
1062         // Whether or not we collapse is dependent on whether all our normal flow children
1063         // are also self-collapsing.
1064         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1065             if (child->isFloatingOrPositioned())
1066                 continue;
1067             if (!child->isSelfCollapsingBlock())
1068                 return false;
1069         }
1070         return true;
1071     }
1072     return false;
1073 }
1074
1075 void RenderBlock::startDelayUpdateScrollInfo()
1076 {
1077     if (gDelayUpdateScrollInfo == 0) {
1078         ASSERT(!gDelayedUpdateScrollInfoSet);
1079         gDelayedUpdateScrollInfoSet = new DelayedUpdateScrollInfoSet;
1080     }
1081     ASSERT(gDelayedUpdateScrollInfoSet);
1082     ++gDelayUpdateScrollInfo;
1083 }
1084
1085 void RenderBlock::finishDelayUpdateScrollInfo()
1086 {
1087     --gDelayUpdateScrollInfo;
1088     ASSERT(gDelayUpdateScrollInfo >= 0);
1089     if (gDelayUpdateScrollInfo == 0) {
1090         ASSERT(gDelayedUpdateScrollInfoSet);
1091
1092         OwnPtr<DelayedUpdateScrollInfoSet> infoSet(adoptPtr(gDelayedUpdateScrollInfoSet));
1093         gDelayedUpdateScrollInfoSet = 0;
1094
1095         for (DelayedUpdateScrollInfoSet::iterator it = infoSet->begin(); it != infoSet->end(); ++it) {
1096             RenderBlock* block = *it;
1097             if (block->hasOverflowClip()) {
1098                 block->layer()->updateScrollInfoAfterLayout();
1099             }
1100         }
1101     }
1102 }
1103
1104 void RenderBlock::updateScrollInfoAfterLayout()
1105 {
1106     if (hasOverflowClip()) {
1107         if (gDelayUpdateScrollInfo)
1108             gDelayedUpdateScrollInfoSet->add(this);
1109         else
1110             layer()->updateScrollInfoAfterLayout();
1111     }
1112 }
1113
1114 void RenderBlock::layout()
1115 {
1116     // Update our first letter info now.
1117     updateFirstLetter();
1118
1119     // Table cells call layoutBlock directly, so don't add any logic here.  Put code into
1120     // layoutBlock().
1121     layoutBlock(false);
1122     
1123     // It's safe to check for control clip here, since controls can never be table cells.
1124     // If we have a lightweight clip, there can never be any overflow from children.
1125     if (hasControlClip() && m_overflow)
1126         clearLayoutOverflow();
1127 }
1128
1129 void RenderBlock::layoutBlock(bool relayoutChildren, int pageLogicalHeight)
1130 {
1131     ASSERT(needsLayout());
1132
1133     if (isInline() && !isInlineBlockOrInlineTable()) // Inline <form>s inside various table elements can
1134         return;                                      // cause us to come in here.  Just bail.
1135
1136     if (!relayoutChildren && simplifiedLayout())
1137         return;
1138
1139     LayoutRepainter repainter(*this, m_everHadLayout && checkForRepaintDuringLayout());
1140
1141     int oldWidth = logicalWidth();
1142     int oldColumnWidth = desiredColumnWidth();
1143
1144     computeLogicalWidth();
1145     calcColumnWidth();
1146
1147     m_overflow.clear();
1148
1149     if (oldWidth != logicalWidth() || oldColumnWidth != desiredColumnWidth())
1150         relayoutChildren = true;
1151
1152     clearFloats();
1153
1154     int previousHeight = logicalHeight();
1155     setLogicalHeight(0);
1156     bool hasSpecifiedPageLogicalHeight = false;
1157     bool pageLogicalHeightChanged = false;
1158     ColumnInfo* colInfo = columnInfo();
1159     if (hasColumns()) {
1160         if (!pageLogicalHeight) {
1161             // We need to go ahead and set our explicit page height if one exists, so that we can
1162             // avoid doing two layout passes.
1163             computeLogicalHeight();
1164             int columnHeight = contentLogicalHeight();
1165             if (columnHeight > 0) {
1166                 pageLogicalHeight = columnHeight;
1167                 hasSpecifiedPageLogicalHeight = true;
1168             }
1169             setLogicalHeight(0);
1170         }
1171         if (colInfo->columnHeight() != pageLogicalHeight && m_everHadLayout) {
1172             colInfo->setColumnHeight(pageLogicalHeight);
1173             pageLogicalHeightChanged = true;
1174         }
1175         
1176         if (!hasSpecifiedPageLogicalHeight && !pageLogicalHeight)
1177             colInfo->clearForcedBreaks();
1178     }
1179
1180     LayoutStateMaintainer statePusher(view(), this, IntSize(x(), y()), hasColumns() || hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode(), pageLogicalHeight, pageLogicalHeightChanged, colInfo);
1181
1182     // We use four values, maxTopPos, maxTopNeg, maxBottomPos, and maxBottomNeg, to track
1183     // our current maximal positive and negative margins.  These values are used when we
1184     // are collapsed with adjacent blocks, so for example, if you have block A and B
1185     // collapsing together, then you'd take the maximal positive margin from both A and B
1186     // and subtract it from the maximal negative margin from both A and B to get the
1187     // true collapsed margin.  This algorithm is recursive, so when we finish layout()
1188     // our block knows its current maximal positive/negative values.
1189     //
1190     // Start out by setting our margin values to our current margins.  Table cells have
1191     // no margins, so we don't fill in the values for table cells.
1192     bool isCell = isTableCell();
1193     if (!isCell) {
1194         initMaxMarginValues();
1195         
1196         setMarginBeforeQuirk(style()->marginBefore().quirk());
1197         setMarginAfterQuirk(style()->marginAfter().quirk());
1198
1199         Node* n = node();
1200         if (n && n->hasTagName(formTag) && static_cast<HTMLFormElement*>(n)->isMalformed()) {
1201             // See if this form is malformed (i.e., unclosed). If so, don't give the form
1202             // a bottom margin.
1203             setMaxMarginAfterValues(0, 0);
1204         }
1205         
1206         setPaginationStrut(0);
1207     }
1208
1209     // For overflow:scroll blocks, ensure we have both scrollbars in place always.
1210     if (scrollsOverflow()) {
1211         if (style()->overflowX() == OSCROLL)
1212             layer()->setHasHorizontalScrollbar(true);
1213         if (style()->overflowY() == OSCROLL)
1214             layer()->setHasVerticalScrollbar(true);
1215     }
1216
1217     int repaintLogicalTop = 0;
1218     int repaintLogicalBottom = 0;
1219     int maxFloatLogicalBottom = 0;
1220     if (!firstChild() && !isAnonymousBlock())
1221         setChildrenInline(true);
1222     if (childrenInline())
1223         layoutInlineChildren(relayoutChildren, repaintLogicalTop, repaintLogicalBottom);
1224     else
1225         layoutBlockChildren(relayoutChildren, maxFloatLogicalBottom);
1226
1227     // Expand our intrinsic height to encompass floats.
1228     int toAdd = borderAfter() + paddingAfter() + scrollbarLogicalHeight();
1229     if (lowestFloatLogicalBottom() > (logicalHeight() - toAdd) && expandsToEncloseOverhangingFloats())
1230         setLogicalHeight(lowestFloatLogicalBottom() + toAdd);
1231     
1232     if (layoutColumns(hasSpecifiedPageLogicalHeight, pageLogicalHeight, statePusher))
1233         return;
1234  
1235     // Calculate our new height.
1236     int oldHeight = logicalHeight();
1237     int oldClientAfterEdge = clientLogicalBottom();
1238     computeLogicalHeight();
1239     int newHeight = logicalHeight();
1240     if (oldHeight != newHeight) {
1241         if (oldHeight > newHeight && maxFloatLogicalBottom > newHeight && !childrenInline()) {
1242             // One of our children's floats may have become an overhanging float for us. We need to look for it.
1243             for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
1244                 if (child->isBlockFlow() && !child->isFloatingOrPositioned()) {
1245                     RenderBlock* block = toRenderBlock(child);
1246                     if (block->lowestFloatLogicalBottom() + block->logicalTop() > newHeight)
1247                         addOverhangingFloats(block, -block->logicalLeft(), -block->logicalTop(), false);
1248                 }
1249             }
1250         }
1251     }
1252
1253     if (previousHeight != newHeight)
1254         relayoutChildren = true;
1255
1256     layoutPositionedObjects(relayoutChildren || isRoot());
1257
1258     // Add overflow from children (unless we're multi-column, since in that case all our child overflow is clipped anyway).
1259     computeOverflow(oldClientAfterEdge);
1260     
1261     statePusher.pop();
1262
1263     if (view()->layoutState()->m_pageLogicalHeight)
1264         setPageLogicalOffset(view()->layoutState()->pageLogicalOffset(logicalTop()));
1265
1266     updateLayerTransform();
1267
1268     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
1269     // we overflow or not.
1270     updateScrollInfoAfterLayout();
1271
1272     // Repaint with our new bounds if they are different from our old bounds.
1273     bool didFullRepaint = repainter.repaintAfterLayout();
1274     if (!didFullRepaint && repaintLogicalTop != repaintLogicalBottom && (style()->visibility() == VISIBLE || enclosingLayer()->hasVisibleContent())) {
1275         // FIXME: We could tighten up the left and right invalidation points if we let layoutInlineChildren fill them in based off the particular lines
1276         // it had to lay out.  We wouldn't need the hasOverflowClip() hack in that case either.
1277         int repaintLogicalLeft = logicalLeftVisualOverflow();
1278         int repaintLogicalRight = logicalRightVisualOverflow();
1279         if (hasOverflowClip()) {
1280             // If we have clipped overflow, we should use layout overflow as well, since visual overflow from lines didn't propagate to our block's overflow.
1281             // Note the old code did this as well but even for overflow:visible.  The addition of hasOverflowClip() at least tightens up the hack a bit.
1282             // layoutInlineChildren should be patched to compute the entire repaint rect.
1283             repaintLogicalLeft = min(repaintLogicalLeft, logicalLeftLayoutOverflow());
1284             repaintLogicalRight = max(repaintLogicalRight, logicalRightLayoutOverflow());
1285         }
1286         
1287         IntRect repaintRect;
1288         if (isHorizontalWritingMode())
1289             repaintRect = IntRect(repaintLogicalLeft, repaintLogicalTop, repaintLogicalRight - repaintLogicalLeft, repaintLogicalBottom - repaintLogicalTop);
1290         else
1291             repaintRect = IntRect(repaintLogicalTop, repaintLogicalLeft, repaintLogicalBottom - repaintLogicalTop, repaintLogicalRight - repaintLogicalLeft);
1292
1293         // The repaint rect may be split across columns, in which case adjustRectForColumns() will return the union.
1294         adjustRectForColumns(repaintRect);
1295
1296         repaintRect.inflate(maximalOutlineSize(PaintPhaseOutline));
1297         
1298         if (hasOverflowClip()) {
1299             // Adjust repaint rect for scroll offset
1300             repaintRect.move(-layer()->scrolledContentOffset());
1301
1302             // Don't allow this rect to spill out of our overflow box.
1303             repaintRect.intersect(IntRect(0, 0, width(), height()));
1304         }
1305
1306         // Make sure the rect is still non-empty after intersecting for overflow above
1307         if (!repaintRect.isEmpty()) {
1308             repaintRectangle(repaintRect); // We need to do a partial repaint of our content.
1309             if (hasReflection())
1310                 repaintRectangle(reflectedRect(repaintRect));
1311         }
1312     }
1313     setNeedsLayout(false);
1314 }
1315
1316 void RenderBlock::addOverflowFromChildren()
1317 {
1318     if (!hasColumns()) {
1319         if (childrenInline())
1320             addOverflowFromInlineChildren();
1321         else
1322             addOverflowFromBlockChildren();
1323     } else {
1324         ColumnInfo* colInfo = columnInfo();
1325         if (columnCount(colInfo)) {
1326             IntRect lastRect = columnRectAt(colInfo, columnCount(colInfo) - 1);
1327             if (isHorizontalWritingMode()) {
1328                 int overflowLeft = !style()->isLeftToRightDirection() ? min(0, lastRect.x()) : 0;
1329                 int overflowRight = style()->isLeftToRightDirection() ? max(width(), lastRect.maxX()) : 0;
1330                 int overflowHeight = borderBefore() + paddingBefore() + colInfo->columnHeight();
1331                 addLayoutOverflow(IntRect(overflowLeft, 0, overflowRight - overflowLeft, overflowHeight));
1332                 if (!hasOverflowClip())
1333                     addVisualOverflow(IntRect(overflowLeft, 0, overflowRight - overflowLeft, overflowHeight));
1334             } else {
1335                 IntRect lastRect = columnRectAt(colInfo, columnCount(colInfo) - 1);
1336                 int overflowTop = !style()->isLeftToRightDirection() ? min(0, lastRect.y()) : 0;
1337                 int overflowBottom = style()->isLeftToRightDirection() ? max(height(), lastRect.maxY()) : 0;
1338                 int overflowWidth = borderBefore() + paddingBefore() + colInfo->columnHeight();
1339                 addLayoutOverflow(IntRect(0, overflowTop, overflowWidth, overflowBottom - overflowTop));
1340                 if (!hasOverflowClip())
1341                     addVisualOverflow(IntRect(0, overflowTop, overflowWidth, overflowBottom - overflowTop));
1342             }
1343         }
1344     }
1345 }
1346
1347 void RenderBlock::computeOverflow(int oldClientAfterEdge, bool recomputeFloats)
1348 {
1349     // Add overflow from children.
1350     addOverflowFromChildren();
1351
1352     if (!hasColumns() && (recomputeFloats || isRoot() || expandsToEncloseOverhangingFloats() || hasSelfPaintingLayer()))
1353         addOverflowFromFloats();
1354
1355     // Add in the overflow from positioned objects.
1356     addOverflowFromPositionedObjects();
1357
1358     if (hasOverflowClip()) {
1359         // When we have overflow clip, propagate the original spillout since it will include collapsed bottom margins
1360         // and bottom padding.  Set the axis we don't care about to be 1, since we want this overflow to always
1361         // be considered reachable.
1362         IntRect clientRect(clientBoxRect());
1363         IntRect rectToApply;
1364         if (isHorizontalWritingMode())
1365             rectToApply = IntRect(clientRect.x(), clientRect.y(), 1, max(0, oldClientAfterEdge - clientRect.y()));
1366         else
1367             rectToApply = IntRect(clientRect.x(), clientRect.y(), max(0, oldClientAfterEdge - clientRect.x()), 1);
1368         addLayoutOverflow(rectToApply);
1369     }
1370         
1371     // Add visual overflow from box-shadow and reflections.
1372     addShadowOverflow();
1373 }
1374
1375 void RenderBlock::addOverflowFromBlockChildren()
1376 {
1377     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1378         if (!child->isFloatingOrPositioned())
1379             addOverflowFromChild(child);
1380     }
1381 }
1382
1383 void RenderBlock::addOverflowFromFloats()
1384 {
1385     if (!m_floatingObjects)
1386         return;
1387
1388     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1389     FloatingObjectSetIterator end = floatingObjectSet.end();
1390     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
1391         FloatingObject* r = *it;
1392         if (r->m_isDescendant)
1393             addOverflowFromChild(r->m_renderer, IntSize(xPositionForFloatIncludingMargin(r), yPositionForFloatIncludingMargin(r)));
1394     }
1395     return;
1396 }
1397
1398 void RenderBlock::addOverflowFromPositionedObjects()
1399 {
1400     if (!m_positionedObjects)
1401         return;
1402
1403     RenderBox* positionedObject;
1404     Iterator end = m_positionedObjects->end();
1405     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
1406         positionedObject = *it;
1407         
1408         // Fixed positioned elements don't contribute to layout overflow, since they don't scroll with the content.
1409         if (positionedObject->style()->position() != FixedPosition)
1410             addOverflowFromChild(positionedObject);
1411     }
1412 }
1413
1414 bool RenderBlock::expandsToEncloseOverhangingFloats() const
1415 {
1416     return isInlineBlockOrInlineTable() || isFloatingOrPositioned() || hasOverflowClip() || (parent() && parent()->isFlexibleBox())
1417            || hasColumns() || isTableCell() || isFieldset() || isWritingModeRoot() || isRoot();
1418 }
1419
1420 void RenderBlock::adjustPositionedBlock(RenderBox* child, const MarginInfo& marginInfo)
1421 {
1422     bool isHorizontal = isHorizontalWritingMode();
1423     bool hasStaticBlockPosition = child->style()->hasStaticBlockPosition(isHorizontal);
1424     RenderLayer* childLayer = child->layer();
1425         
1426     childLayer->setStaticInlinePosition(borderAndPaddingStart());
1427
1428     int logicalTop = logicalHeight();
1429     if (!marginInfo.canCollapseWithMarginBefore()) {
1430         child->computeBlockDirectionMargins(this);
1431         int marginBefore = marginBeforeForChild(child);
1432         int collapsedBeforePos = marginInfo.positiveMargin();
1433         int collapsedBeforeNeg = marginInfo.negativeMargin();
1434         if (marginBefore > 0) {
1435             if (marginBefore > collapsedBeforePos)
1436                 collapsedBeforePos = marginBefore;
1437         } else {
1438             if (-marginBefore > collapsedBeforeNeg)
1439                 collapsedBeforeNeg = -marginBefore;
1440         }
1441         logicalTop += (collapsedBeforePos - collapsedBeforeNeg) - marginBefore;
1442     }
1443     if (childLayer->staticBlockPosition() != logicalTop) {
1444         childLayer->setStaticBlockPosition(logicalTop);
1445         if (hasStaticBlockPosition)
1446             child->setChildNeedsLayout(true, false);
1447     }
1448 }
1449
1450 void RenderBlock::adjustFloatingBlock(const MarginInfo& marginInfo)
1451 {
1452     // The float should be positioned taking into account the bottom margin
1453     // of the previous flow.  We add that margin into the height, get the
1454     // float positioned properly, and then subtract the margin out of the
1455     // height again.  In the case of self-collapsing blocks, we always just
1456     // use the top margins, since the self-collapsing block collapsed its
1457     // own bottom margin into its top margin.
1458     //
1459     // Note also that the previous flow may collapse its margin into the top of
1460     // our block.  If this is the case, then we do not add the margin in to our
1461     // height when computing the position of the float.   This condition can be tested
1462     // for by simply calling canCollapseWithMarginBefore.  See
1463     // http://www.hixie.ch/tests/adhoc/css/box/block/margin-collapse/046.html for
1464     // an example of this scenario.
1465     int marginOffset = marginInfo.canCollapseWithMarginBefore() ? 0 : marginInfo.margin();
1466     setLogicalHeight(logicalHeight() + marginOffset);
1467     positionNewFloats();
1468     setLogicalHeight(logicalHeight() - marginOffset);
1469 }
1470
1471 bool RenderBlock::handleSpecialChild(RenderBox* child, const MarginInfo& marginInfo)
1472 {
1473     // Handle in the given order
1474     return handlePositionedChild(child, marginInfo)
1475         || handleFloatingChild(child, marginInfo)
1476         || handleRunInChild(child);
1477 }
1478
1479
1480 bool RenderBlock::handlePositionedChild(RenderBox* child, const MarginInfo& marginInfo)
1481 {
1482     if (child->isPositioned()) {
1483         child->containingBlock()->insertPositionedObject(child);
1484         adjustPositionedBlock(child, marginInfo);
1485         return true;
1486     }
1487     return false;
1488 }
1489
1490 bool RenderBlock::handleFloatingChild(RenderBox* child, const MarginInfo& marginInfo)
1491 {
1492     if (child->isFloating()) {
1493         insertFloatingObject(child);
1494         adjustFloatingBlock(marginInfo);
1495         return true;
1496     }
1497     return false;
1498 }
1499
1500 bool RenderBlock::handleRunInChild(RenderBox* child)
1501 {
1502     // See if we have a run-in element with inline children.  If the
1503     // children aren't inline, then just treat the run-in as a normal
1504     // block.
1505     if (!child->isRunIn() || !child->childrenInline())
1506         return false;
1507     // FIXME: We don't handle non-block elements with run-in for now.
1508     if (!child->isRenderBlock())
1509         return false;
1510
1511     // Get the next non-positioned/non-floating RenderBlock.
1512     RenderBlock* blockRunIn = toRenderBlock(child);
1513     RenderObject* curr = blockRunIn->nextSibling();
1514     while (curr && curr->isFloatingOrPositioned())
1515         curr = curr->nextSibling();
1516
1517     if (!curr || !curr->isRenderBlock() || !curr->childrenInline() || curr->isRunIn() || curr->isAnonymous())
1518         return false;
1519
1520     RenderBlock* currBlock = toRenderBlock(curr);
1521
1522     // Remove the old child.
1523     children()->removeChildNode(this, blockRunIn);
1524
1525     // Create an inline.
1526     Node* runInNode = blockRunIn->node();
1527     RenderInline* inlineRunIn = new (renderArena()) RenderInline(runInNode ? runInNode : document());
1528     inlineRunIn->setStyle(blockRunIn->style());
1529
1530     bool runInIsGenerated = child->style()->styleType() == BEFORE || child->style()->styleType() == AFTER;
1531
1532     // Move the nodes from the old child to the new child, but skip any :before/:after content.  It has already
1533     // been regenerated by the new inline.
1534     for (RenderObject* runInChild = blockRunIn->firstChild(); runInChild;) {
1535         RenderObject* nextSibling = runInChild->nextSibling();
1536         if (runInIsGenerated || (runInChild->style()->styleType() != BEFORE && runInChild->style()->styleType() != AFTER)) {
1537             blockRunIn->children()->removeChildNode(blockRunIn, runInChild, false);
1538             inlineRunIn->addChild(runInChild); // Use addChild instead of appendChildNode since it handles correct placement of the children relative to :after-generated content.
1539         }
1540         runInChild = nextSibling;
1541     }
1542
1543     // Now insert the new child under |currBlock|. Use addChild instead of insertChildNode since it handles correct placement of the children, esp where we cannot insert
1544     // anything before the first child. e.g. details tag. See https://bugs.webkit.org/show_bug.cgi?id=58228.
1545     currBlock->addChild(inlineRunIn, currBlock->firstChild());
1546     
1547     // If the run-in had an element, we need to set the new renderer.
1548     if (runInNode)
1549         runInNode->setRenderer(inlineRunIn);
1550
1551     // Destroy the block run-in, which includes deleting its line box tree.
1552     blockRunIn->deleteLineBoxTree();
1553     blockRunIn->destroy();
1554
1555     // The block acts like an inline, so just null out its
1556     // position.
1557     
1558     return true;
1559 }
1560
1561 int RenderBlock::collapseMargins(RenderBox* child, MarginInfo& marginInfo)
1562 {
1563     // Get the four margin values for the child and cache them.
1564     const MarginValues childMargins = marginValuesForChild(child);
1565
1566     // Get our max pos and neg top margins.
1567     int posTop = childMargins.positiveMarginBefore();
1568     int negTop = childMargins.negativeMarginBefore();
1569
1570     // For self-collapsing blocks, collapse our bottom margins into our
1571     // top to get new posTop and negTop values.
1572     if (child->isSelfCollapsingBlock()) {
1573         posTop = max(posTop, childMargins.positiveMarginAfter());
1574         negTop = max(negTop, childMargins.negativeMarginAfter());
1575     }
1576     
1577     // See if the top margin is quirky. We only care if this child has
1578     // margins that will collapse with us.
1579     bool topQuirk = child->isMarginBeforeQuirk() || style()->marginBeforeCollapse() == MDISCARD;
1580
1581     if (marginInfo.canCollapseWithMarginBefore()) {
1582         // This child is collapsing with the top of the
1583         // block.  If it has larger margin values, then we need to update
1584         // our own maximal values.
1585         if (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !topQuirk)
1586             setMaxMarginBeforeValues(max(posTop, maxPositiveMarginBefore()), max(negTop, maxNegativeMarginBefore()));
1587
1588         // The minute any of the margins involved isn't a quirk, don't
1589         // collapse it away, even if the margin is smaller (www.webreference.com
1590         // has an example of this, a <dt> with 0.8em author-specified inside
1591         // a <dl> inside a <td>.
1592         if (!marginInfo.determinedMarginBeforeQuirk() && !topQuirk && (posTop - negTop)) {
1593             setMarginBeforeQuirk(false);
1594             marginInfo.setDeterminedMarginBeforeQuirk(true);
1595         }
1596
1597         if (!marginInfo.determinedMarginBeforeQuirk() && topQuirk && !marginBefore())
1598             // We have no top margin and our top child has a quirky margin.
1599             // We will pick up this quirky margin and pass it through.
1600             // This deals with the <td><div><p> case.
1601             // Don't do this for a block that split two inlines though.  You do
1602             // still apply margins in this case.
1603             setMarginBeforeQuirk(true);
1604     }
1605
1606     if (marginInfo.quirkContainer() && marginInfo.atBeforeSideOfBlock() && (posTop - negTop))
1607         marginInfo.setMarginBeforeQuirk(topQuirk);
1608
1609     int beforeCollapseLogicalTop = logicalHeight();
1610     int logicalTop = beforeCollapseLogicalTop;
1611     if (child->isSelfCollapsingBlock()) {
1612         // This child has no height.  We need to compute our
1613         // position before we collapse the child's margins together,
1614         // so that we can get an accurate position for the zero-height block.
1615         int collapsedBeforePos = max(marginInfo.positiveMargin(), childMargins.positiveMarginBefore());
1616         int collapsedBeforeNeg = max(marginInfo.negativeMargin(), childMargins.negativeMarginBefore());
1617         marginInfo.setMargin(collapsedBeforePos, collapsedBeforeNeg);
1618         
1619         // Now collapse the child's margins together, which means examining our
1620         // bottom margin values as well. 
1621         marginInfo.setPositiveMarginIfLarger(childMargins.positiveMarginAfter());
1622         marginInfo.setNegativeMarginIfLarger(childMargins.negativeMarginAfter());
1623
1624         if (!marginInfo.canCollapseWithMarginBefore())
1625             // We need to make sure that the position of the self-collapsing block
1626             // is correct, since it could have overflowing content
1627             // that needs to be positioned correctly (e.g., a block that
1628             // had a specified height of 0 but that actually had subcontent).
1629             logicalTop = logicalHeight() + collapsedBeforePos - collapsedBeforeNeg;
1630     }
1631     else {
1632         if (child->style()->marginBeforeCollapse() == MSEPARATE) {
1633             setLogicalHeight(logicalHeight() + marginInfo.margin() + marginBeforeForChild(child));
1634             logicalTop = logicalHeight();
1635         }
1636         else if (!marginInfo.atBeforeSideOfBlock() ||
1637             (!marginInfo.canCollapseMarginBeforeWithChildren()
1638              && (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.marginBeforeQuirk()))) {
1639             // We're collapsing with a previous sibling's margins and not
1640             // with the top of the block.
1641             setLogicalHeight(logicalHeight() + max(marginInfo.positiveMargin(), posTop) - max(marginInfo.negativeMargin(), negTop));
1642             logicalTop = logicalHeight();
1643         }
1644
1645         marginInfo.setPositiveMargin(childMargins.positiveMarginAfter());
1646         marginInfo.setNegativeMargin(childMargins.negativeMarginAfter());
1647
1648         if (marginInfo.margin())
1649             marginInfo.setMarginAfterQuirk(child->isMarginAfterQuirk() || style()->marginAfterCollapse() == MDISCARD);
1650     }
1651     
1652     // If margins would pull us past the top of the next page, then we need to pull back and pretend like the margins
1653     // collapsed into the page edge.
1654     bool paginated = view()->layoutState()->isPaginated();
1655     if (paginated && logicalTop > beforeCollapseLogicalTop) {
1656         int oldLogicalTop = logicalTop;
1657         logicalTop = min(logicalTop, nextPageLogicalTop(beforeCollapseLogicalTop));
1658         setLogicalHeight(logicalHeight() + (logicalTop - oldLogicalTop));
1659     }
1660     return logicalTop;
1661 }
1662
1663 int RenderBlock::clearFloatsIfNeeded(RenderBox* child, MarginInfo& marginInfo, int oldTopPosMargin, int oldTopNegMargin, int yPos)
1664 {
1665     int heightIncrease = getClearDelta(child, yPos);
1666     if (!heightIncrease)
1667         return yPos;
1668
1669     if (child->isSelfCollapsingBlock()) {
1670         // For self-collapsing blocks that clear, they can still collapse their
1671         // margins with following siblings.  Reset the current margins to represent
1672         // the self-collapsing block's margins only.
1673         // CSS2.1 states:
1674         // "An element that has had clearance applied to it never collapses its top margin with its parent block's bottom margin.
1675         // Therefore if we are at the bottom of the block, let's go ahead and reset margins to only include the
1676         // self-collapsing block's bottom margin.
1677         bool atBottomOfBlock = true;
1678         for (RenderBox* curr = child->nextSiblingBox(); curr && atBottomOfBlock; curr = curr->nextSiblingBox()) {
1679             if (!curr->isFloatingOrPositioned())
1680                 atBottomOfBlock = false;
1681         }
1682         
1683         MarginValues childMargins = marginValuesForChild(child);
1684         if (atBottomOfBlock) {
1685             marginInfo.setPositiveMargin(childMargins.positiveMarginAfter());
1686             marginInfo.setNegativeMargin(childMargins.negativeMarginAfter());
1687         } else {
1688             marginInfo.setPositiveMargin(max(childMargins.positiveMarginBefore(), childMargins.positiveMarginAfter()));
1689             marginInfo.setNegativeMargin(max(childMargins.negativeMarginBefore(), childMargins.negativeMarginAfter()));
1690         }
1691         
1692         // Adjust our height such that we are ready to be collapsed with subsequent siblings (or the bottom
1693         // of the parent block).
1694         setLogicalHeight(child->y() - max(0, marginInfo.margin()));
1695     } else
1696         // Increase our height by the amount we had to clear.
1697         setLogicalHeight(height() + heightIncrease);
1698     
1699     if (marginInfo.canCollapseWithMarginBefore()) {
1700         // We can no longer collapse with the top of the block since a clear
1701         // occurred.  The empty blocks collapse into the cleared block.
1702         // FIXME: This isn't quite correct.  Need clarification for what to do
1703         // if the height the cleared block is offset by is smaller than the
1704         // margins involved.
1705         setMaxMarginBeforeValues(oldTopPosMargin, oldTopNegMargin);
1706         marginInfo.setAtBeforeSideOfBlock(false);
1707     }
1708     
1709     return yPos + heightIncrease;
1710 }
1711
1712 int RenderBlock::estimateLogicalTopPosition(RenderBox* child, const MarginInfo& marginInfo)
1713 {
1714     // FIXME: We need to eliminate the estimation of vertical position, because when it's wrong we sometimes trigger a pathological
1715     // relayout if there are intruding floats.
1716     int logicalTopEstimate = logicalHeight();
1717     if (!marginInfo.canCollapseWithMarginBefore()) {
1718         int childMarginBefore = child->selfNeedsLayout() ? marginBeforeForChild(child) : collapsedMarginBeforeForChild(child);
1719         logicalTopEstimate += max(marginInfo.margin(), childMarginBefore);
1720     }
1721     
1722     bool paginated = view()->layoutState()->isPaginated();
1723
1724     // Adjust logicalTopEstimate down to the next page if the margins are so large that we don't fit on the current
1725     // page.
1726     if (paginated && logicalTopEstimate > logicalHeight())
1727         logicalTopEstimate = min(logicalTopEstimate, nextPageLogicalTop(logicalHeight()));
1728
1729     logicalTopEstimate += getClearDelta(child, logicalTopEstimate);
1730     
1731     if (paginated) {
1732         // If the object has a page or column break value of "before", then we should shift to the top of the next page.
1733         logicalTopEstimate = applyBeforeBreak(child, logicalTopEstimate);
1734     
1735         // For replaced elements and scrolled elements, we want to shift them to the next page if they don't fit on the current one.
1736         logicalTopEstimate = adjustForUnsplittableChild(child, logicalTopEstimate);
1737         
1738         if (!child->selfNeedsLayout() && child->isRenderBlock())
1739             logicalTopEstimate += toRenderBlock(child)->paginationStrut();
1740     }
1741
1742     return logicalTopEstimate;
1743 }
1744
1745 void RenderBlock::determineLogicalLeftPositionForChild(RenderBox* child)
1746 {
1747     int startPosition = borderStart() + paddingStart();
1748     int totalAvailableLogicalWidth = borderAndPaddingLogicalWidth() + availableLogicalWidth();
1749
1750     // Add in our start margin.
1751     int childMarginStart = marginStartForChild(child);
1752     int newPosition = startPosition + childMarginStart;
1753         
1754     // Some objects (e.g., tables, horizontal rules, overflow:auto blocks) avoid floats.  They need
1755     // to shift over as necessary to dodge any floats that might get in the way.
1756     if (child->avoidsFloats()) {
1757         int startOff = style()->isLeftToRightDirection() ? logicalLeftOffsetForLine(logicalHeight(), false) : totalAvailableLogicalWidth - logicalRightOffsetForLine(logicalHeight(), false);
1758         if (style()->textAlign() != WEBKIT_CENTER && !child->style()->marginStartUsing(style()).isAuto()) {
1759             if (childMarginStart < 0)
1760                 startOff += childMarginStart;
1761             newPosition = max(newPosition, startOff); // Let the float sit in the child's margin if it can fit.
1762         } else if (startOff != startPosition) {
1763             // The object is shifting to the "end" side of the block. The object might be centered, so we need to
1764             // recalculate our inline direction margins. Note that the containing block content
1765             // width computation will take into account the delta between |startOff| and |startPosition|
1766             // so that we can just pass the content width in directly to the |computeMarginsInContainingBlockInlineDirection|
1767             // function.
1768             child->computeInlineDirectionMargins(this, availableLogicalWidthForLine(logicalTopForChild(child), false), logicalWidthForChild(child));
1769             newPosition = startOff + marginStartForChild(child);
1770         }
1771     }
1772
1773     setLogicalLeftForChild(child, style()->isLeftToRightDirection() ? newPosition : totalAvailableLogicalWidth - newPosition - logicalWidthForChild(child), ApplyLayoutDelta);
1774 }
1775
1776 void RenderBlock::setCollapsedBottomMargin(const MarginInfo& marginInfo)
1777 {
1778     if (marginInfo.canCollapseWithMarginAfter() && !marginInfo.canCollapseWithMarginBefore()) {
1779         // Update our max pos/neg bottom margins, since we collapsed our bottom margins
1780         // with our children.
1781         setMaxMarginAfterValues(max(maxPositiveMarginAfter(), marginInfo.positiveMargin()), max(maxNegativeMarginAfter(), marginInfo.negativeMargin()));
1782
1783         if (!marginInfo.marginAfterQuirk())
1784             setMarginAfterQuirk(false);
1785
1786         if (marginInfo.marginAfterQuirk() && marginAfter() == 0)
1787             // We have no bottom margin and our last child has a quirky margin.
1788             // We will pick up this quirky margin and pass it through.
1789             // This deals with the <td><div><p> case.
1790             setMarginAfterQuirk(true);
1791     }
1792 }
1793
1794 void RenderBlock::handleAfterSideOfBlock(int beforeSide, int afterSide, MarginInfo& marginInfo)
1795 {
1796     marginInfo.setAtAfterSideOfBlock(true);
1797
1798     // If we can't collapse with children then go ahead and add in the bottom margin.
1799     if (!marginInfo.canCollapseWithMarginAfter() && !marginInfo.canCollapseWithMarginBefore()
1800         && (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.marginAfterQuirk()))
1801         setLogicalHeight(logicalHeight() + marginInfo.margin());
1802         
1803     // Now add in our bottom border/padding.
1804     setLogicalHeight(logicalHeight() + afterSide);
1805
1806     // Negative margins can cause our height to shrink below our minimal height (border/padding).
1807     // If this happens, ensure that the computed height is increased to the minimal height.
1808     setLogicalHeight(max(logicalHeight(), beforeSide + afterSide));
1809
1810     // Update our bottom collapsed margin info.
1811     setCollapsedBottomMargin(marginInfo);
1812 }
1813
1814 void RenderBlock::setLogicalLeftForChild(RenderBox* child, int logicalLeft, ApplyLayoutDeltaMode applyDelta)
1815 {
1816     if (isHorizontalWritingMode()) {
1817         if (applyDelta == ApplyLayoutDelta)
1818             view()->addLayoutDelta(IntSize(child->x() - logicalLeft, 0));
1819         child->setX(logicalLeft);
1820     } else {
1821         if (applyDelta == ApplyLayoutDelta)
1822             view()->addLayoutDelta(IntSize(0, child->y() - logicalLeft));
1823         child->setY(logicalLeft);
1824     }
1825 }
1826
1827 void RenderBlock::setLogicalTopForChild(RenderBox* child, int logicalTop, ApplyLayoutDeltaMode applyDelta)
1828 {
1829     if (isHorizontalWritingMode()) {
1830         if (applyDelta == ApplyLayoutDelta)
1831             view()->addLayoutDelta(IntSize(0, child->y() - logicalTop));
1832         child->setY(logicalTop);
1833     } else {
1834         if (applyDelta == ApplyLayoutDelta)
1835             view()->addLayoutDelta(IntSize(child->x() - logicalTop, 0));
1836         child->setX(logicalTop);
1837     }
1838 }
1839
1840 void RenderBlock::layoutBlockChildren(bool relayoutChildren, int& maxFloatLogicalBottom)
1841 {
1842     if (gPercentHeightDescendantsMap) {
1843         if (HashSet<RenderBox*>* descendants = gPercentHeightDescendantsMap->get(this)) {
1844             HashSet<RenderBox*>::iterator end = descendants->end();
1845             for (HashSet<RenderBox*>::iterator it = descendants->begin(); it != end; ++it) {
1846                 RenderBox* box = *it;
1847                 while (box != this) {
1848                     if (box->normalChildNeedsLayout())
1849                         break;
1850                     box->setChildNeedsLayout(true, false);
1851                     box = box->containingBlock();
1852                     ASSERT(box);
1853                     if (!box)
1854                         break;
1855                 }
1856             }
1857         }
1858     }
1859
1860     int beforeEdge = borderBefore() + paddingBefore();
1861     int afterEdge = borderAfter() + paddingAfter() + scrollbarLogicalHeight();
1862
1863     setLogicalHeight(beforeEdge);
1864
1865     // The margin struct caches all our current margin collapsing state.  The compact struct caches state when we encounter compacts,
1866     MarginInfo marginInfo(this, beforeEdge, afterEdge);
1867
1868     // Fieldsets need to find their legend and position it inside the border of the object.
1869     // The legend then gets skipped during normal layout.  The same is true for ruby text.
1870     // It doesn't get included in the normal layout process but is instead skipped.
1871     RenderObject* childToExclude = layoutSpecialExcludedChild(relayoutChildren);
1872
1873     int previousFloatLogicalBottom = 0;
1874     maxFloatLogicalBottom = 0;
1875
1876     RenderBox* next = firstChildBox();
1877
1878     while (next) {
1879         RenderBox* child = next;
1880         next = child->nextSiblingBox();
1881
1882         if (childToExclude == child)
1883             continue; // Skip this child, since it will be positioned by the specialized subclass (fieldsets and ruby runs).
1884
1885         // Make sure we layout children if they need it.
1886         // FIXME: Technically percentage height objects only need a relayout if their percentage isn't going to be turned into
1887         // an auto value.  Add a method to determine this, so that we can avoid the relayout.
1888         if (relayoutChildren || ((child->style()->logicalHeight().isPercent() || child->style()->logicalMinHeight().isPercent() || child->style()->logicalMaxHeight().isPercent()) && !isRenderView()))
1889             child->setChildNeedsLayout(true, false);
1890
1891         // If relayoutChildren is set and the child has percentage padding, we also need to invalidate the child's pref widths.
1892         if (relayoutChildren && (child->style()->paddingStart().isPercent() || child->style()->paddingEnd().isPercent()))
1893             child->setPreferredLogicalWidthsDirty(true, false);
1894
1895         // Handle the four types of special elements first.  These include positioned content, floating content, compacts and
1896         // run-ins.  When we encounter these four types of objects, we don't actually lay them out as normal flow blocks.
1897         if (handleSpecialChild(child, marginInfo))
1898             continue;
1899
1900         // Lay out the child.
1901         layoutBlockChild(child, marginInfo, previousFloatLogicalBottom, maxFloatLogicalBottom);
1902     }
1903     
1904     // Now do the handling of the bottom of the block, adding in our bottom border/padding and
1905     // determining the correct collapsed bottom margin information.
1906     handleAfterSideOfBlock(beforeEdge, afterEdge, marginInfo);
1907 }
1908
1909 void RenderBlock::layoutBlockChild(RenderBox* child, MarginInfo& marginInfo, int& previousFloatLogicalBottom, int& maxFloatLogicalBottom)
1910 {
1911     int oldPosMarginBefore = maxPositiveMarginBefore();
1912     int oldNegMarginBefore = maxNegativeMarginBefore();
1913
1914     // The child is a normal flow object.  Compute the margins we will use for collapsing now.
1915     child->computeBlockDirectionMargins(this);
1916
1917     // Do not allow a collapse if the margin-before-collapse style is set to SEPARATE.
1918     if (child->style()->marginBeforeCollapse() == MSEPARATE) {
1919         marginInfo.setAtBeforeSideOfBlock(false);
1920         marginInfo.clearMargin();
1921     }
1922
1923     // Try to guess our correct logical top position.  In most cases this guess will
1924     // be correct.  Only if we're wrong (when we compute the real logical top position)
1925     // will we have to potentially relayout.
1926     int logicalTopEstimate = estimateLogicalTopPosition(child, marginInfo);
1927
1928     // Cache our old rect so that we can dirty the proper repaint rects if the child moves.
1929     IntRect oldRect(child->x(), child->y() , child->width(), child->height());
1930     int oldLogicalTop = logicalTopForChild(child);
1931
1932 #ifndef NDEBUG
1933     IntSize oldLayoutDelta = view()->layoutDelta();
1934 #endif
1935     // Go ahead and position the child as though it didn't collapse with the top.
1936     setLogicalTopForChild(child, logicalTopEstimate, ApplyLayoutDelta);
1937
1938     RenderBlock* childRenderBlock = child->isRenderBlock() ? toRenderBlock(child) : 0;
1939     bool markDescendantsWithFloats = false;
1940     if (logicalTopEstimate != oldLogicalTop && !child->avoidsFloats() && childRenderBlock && childRenderBlock->containsFloats())
1941         markDescendantsWithFloats = true;
1942     else if (!child->avoidsFloats() || child->shrinkToAvoidFloats()) {
1943         // If an element might be affected by the presence of floats, then always mark it for
1944         // layout.
1945         int fb = max(previousFloatLogicalBottom, lowestFloatLogicalBottom());
1946         if (fb > logicalTopEstimate)
1947             markDescendantsWithFloats = true;
1948     }
1949
1950     if (childRenderBlock) {
1951         if (markDescendantsWithFloats)
1952             childRenderBlock->markAllDescendantsWithFloatsForLayout();
1953         if (!child->isWritingModeRoot())
1954             previousFloatLogicalBottom = max(previousFloatLogicalBottom, oldLogicalTop + childRenderBlock->lowestFloatLogicalBottom());
1955     }
1956
1957     if (!child->needsLayout())
1958         child->markForPaginationRelayoutIfNeeded();
1959
1960     bool childHadLayout = child->m_everHadLayout;
1961     bool childNeededLayout = child->needsLayout();
1962     if (childNeededLayout)
1963         child->layout();
1964
1965     // Cache if we are at the top of the block right now.
1966     bool atBeforeSideOfBlock = marginInfo.atBeforeSideOfBlock();
1967
1968     // Now determine the correct ypos based off examination of collapsing margin
1969     // values.
1970     int logicalTopBeforeClear = collapseMargins(child, marginInfo);
1971
1972     // Now check for clear.
1973     int logicalTopAfterClear = clearFloatsIfNeeded(child, marginInfo, oldPosMarginBefore, oldNegMarginBefore, logicalTopBeforeClear);
1974     
1975     bool paginated = view()->layoutState()->isPaginated();
1976     if (paginated) {
1977         int oldTop = logicalTopAfterClear;
1978         
1979         // If the object has a page or column break value of "before", then we should shift to the top of the next page.
1980         logicalTopAfterClear = applyBeforeBreak(child, logicalTopAfterClear);
1981     
1982         // For replaced elements and scrolled elements, we want to shift them to the next page if they don't fit on the current one.
1983         int logicalTopBeforeUnsplittableAdjustment = logicalTopAfterClear;
1984         int logicalTopAfterUnsplittableAdjustment = adjustForUnsplittableChild(child, logicalTopAfterClear);
1985         
1986         int paginationStrut = 0;
1987         int unsplittableAdjustmentDelta = logicalTopAfterUnsplittableAdjustment - logicalTopBeforeUnsplittableAdjustment;
1988         if (unsplittableAdjustmentDelta)
1989             paginationStrut = unsplittableAdjustmentDelta;
1990         else if (childRenderBlock && childRenderBlock->paginationStrut())
1991             paginationStrut = childRenderBlock->paginationStrut();
1992
1993         if (paginationStrut) {
1994             // We are willing to propagate out to our parent block as long as we were at the top of the block prior
1995             // to collapsing our margins, and as long as we didn't clear or move as a result of other pagination.
1996             if (atBeforeSideOfBlock && oldTop == logicalTopBeforeClear && !isPositioned() && !isTableCell()) {
1997                 // FIXME: Should really check if we're exceeding the page height before propagating the strut, but we don't
1998                 // have all the information to do so (the strut only has the remaining amount to push).  Gecko gets this wrong too
1999                 // and pushes to the next page anyway, so not too concerned about it.
2000                 setPaginationStrut(logicalTopAfterClear + paginationStrut);
2001                 if (childRenderBlock)
2002                     childRenderBlock->setPaginationStrut(0);
2003             } else
2004                 logicalTopAfterClear += paginationStrut;
2005         }
2006
2007         // Similar to how we apply clearance.  Go ahead and boost height() to be the place where we're going to position the child.
2008         setLogicalHeight(logicalHeight() + (logicalTopAfterClear - oldTop));
2009     }
2010
2011     setLogicalTopForChild(child, logicalTopAfterClear, ApplyLayoutDelta);
2012
2013     // Now we have a final top position.  See if it really does end up being different from our estimate.
2014     if (logicalTopAfterClear != logicalTopEstimate) {
2015         if (child->shrinkToAvoidFloats()) {
2016             // The child's width depends on the line width.
2017             // When the child shifts to clear an item, its width can
2018             // change (because it has more available line width).
2019             // So go ahead and mark the item as dirty.
2020             child->setChildNeedsLayout(true, false);
2021         }
2022         if (childRenderBlock) {
2023             if (!child->avoidsFloats() && childRenderBlock->containsFloats())
2024                 childRenderBlock->markAllDescendantsWithFloatsForLayout();
2025             if (!child->needsLayout())
2026                 child->markForPaginationRelayoutIfNeeded();
2027         }
2028
2029         // Our guess was wrong. Make the child lay itself out again.
2030         child->layoutIfNeeded();
2031     }
2032
2033     // We are no longer at the top of the block if we encounter a non-empty child.  
2034     // This has to be done after checking for clear, so that margins can be reset if a clear occurred.
2035     if (marginInfo.atBeforeSideOfBlock() && !child->isSelfCollapsingBlock())
2036         marginInfo.setAtBeforeSideOfBlock(false);
2037
2038     // Now place the child in the correct left position
2039     determineLogicalLeftPositionForChild(child);
2040
2041     // Update our height now that the child has been placed in the correct position.
2042     setLogicalHeight(logicalHeight() + logicalHeightForChild(child));
2043     if (child->style()->marginAfterCollapse() == MSEPARATE) {
2044         setLogicalHeight(logicalHeight() + marginAfterForChild(child));
2045         marginInfo.clearMargin();
2046     }
2047     // If the child has overhanging floats that intrude into following siblings (or possibly out
2048     // of this block), then the parent gets notified of the floats now.
2049     if (childRenderBlock && childRenderBlock->containsFloats())
2050         maxFloatLogicalBottom = max(maxFloatLogicalBottom, addOverhangingFloats(toRenderBlock(child), -child->logicalLeft(), -child->logicalTop(), !childNeededLayout));
2051
2052     IntSize childOffset(child->x() - oldRect.x(), child->y() - oldRect.y());
2053     if (childOffset.width() || childOffset.height()) {
2054         view()->addLayoutDelta(childOffset);
2055
2056         // If the child moved, we have to repaint it as well as any floating/positioned
2057         // descendants.  An exception is if we need a layout.  In this case, we know we're going to
2058         // repaint ourselves (and the child) anyway.
2059         if (childHadLayout && !selfNeedsLayout() && child->checkForRepaintDuringLayout())
2060             child->repaintDuringLayoutIfMoved(oldRect);
2061     }
2062
2063     if (!childHadLayout && child->checkForRepaintDuringLayout()) {
2064         child->repaint();
2065         child->repaintOverhangingFloats(true);
2066     }
2067
2068     if (paginated) {
2069         // Check for an after page/column break.
2070         int newHeight = applyAfterBreak(child, logicalHeight(), marginInfo);
2071         if (newHeight != height())
2072             setLogicalHeight(newHeight);
2073     }
2074
2075     ASSERT(oldLayoutDelta == view()->layoutDelta());
2076 }
2077
2078 void RenderBlock::simplifiedNormalFlowLayout()
2079 {
2080     if (childrenInline()) {
2081         ListHashSet<RootInlineBox*> lineBoxes;
2082         bool endOfInline = false;
2083         RenderObject* o = bidiFirstNotSkippingInlines(this);
2084         while (o) {
2085             if (!o->isPositioned() && (o->isReplaced() || o->isFloating())) {
2086                 o->layoutIfNeeded();
2087                 if (toRenderBox(o)->inlineBoxWrapper()) {
2088                     RootInlineBox* box = toRenderBox(o)->inlineBoxWrapper()->root();
2089                     lineBoxes.add(box);
2090                 }
2091             } else if (o->isText() || (o->isRenderInline() && !endOfInline))
2092                 o->setNeedsLayout(false);
2093             o = bidiNext(this, o, 0, false, &endOfInline);
2094         }
2095
2096         // FIXME: Glyph overflow will get lost in this case, but not really a big deal.
2097         GlyphOverflowAndFallbackFontsMap textBoxDataMap;                  
2098         for (ListHashSet<RootInlineBox*>::const_iterator it = lineBoxes.begin(); it != lineBoxes.end(); ++it) {
2099             RootInlineBox* box = *it;
2100             box->computeOverflow(box->lineTop(), box->lineBottom(), textBoxDataMap);
2101         }
2102     } else {
2103         for (RenderBox* box = firstChildBox(); box; box = box->nextSiblingBox()) {
2104             if (!box->isPositioned())
2105                 box->layoutIfNeeded();
2106         }
2107     }
2108 }
2109
2110 bool RenderBlock::simplifiedLayout()
2111 {
2112     if ((!posChildNeedsLayout() && !needsSimplifiedNormalFlowLayout()) || normalChildNeedsLayout() || selfNeedsLayout())
2113         return false;
2114
2115     LayoutStateMaintainer statePusher(view(), this, IntSize(x(), y()), hasColumns() || hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode());
2116     
2117     if (needsPositionedMovementLayout() && !tryLayoutDoingPositionedMovementOnly())
2118         return false;
2119
2120     // Lay out positioned descendants or objects that just need to recompute overflow.
2121     if (needsSimplifiedNormalFlowLayout())
2122         simplifiedNormalFlowLayout();
2123
2124     // Lay out our positioned objects if our positioned child bit is set.
2125     if (posChildNeedsLayout())
2126         layoutPositionedObjects(false);
2127
2128     // Recompute our overflow information.
2129     // FIXME: We could do better here by computing a temporary overflow object from layoutPositionedObjects and only
2130     // updating our overflow if we either used to have overflow or if the new temporary object has overflow.
2131     // For now just always recompute overflow.  This is no worse performance-wise than the old code that called rightmostPosition and
2132     // lowestPosition on every relayout so it's not a regression.
2133     m_overflow.clear();
2134     computeOverflow(clientLogicalBottom(), true);
2135
2136     statePusher.pop();
2137     
2138     updateLayerTransform();
2139
2140     updateScrollInfoAfterLayout();
2141
2142     setNeedsLayout(false);
2143     return true;
2144 }
2145
2146 void RenderBlock::layoutPositionedObjects(bool relayoutChildren)
2147 {
2148     if (!m_positionedObjects)
2149         return;
2150         
2151     if (hasColumns())
2152         view()->layoutState()->clearPaginationInformation(); // Positioned objects are not part of the column flow, so they don't paginate with the columns.
2153
2154     RenderBox* r;
2155     Iterator end = m_positionedObjects->end();
2156     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2157         r = *it;
2158         // When a non-positioned block element moves, it may have positioned children that are implicitly positioned relative to the
2159         // non-positioned block.  Rather than trying to detect all of these movement cases, we just always lay out positioned
2160         // objects that are positioned implicitly like this.  Such objects are rare, and so in typical DHTML menu usage (where everything is
2161         // positioned explicitly) this should not incur a performance penalty.
2162         if (relayoutChildren || (r->style()->hasStaticBlockPosition(isHorizontalWritingMode()) && r->parent() != this && r->parent()->isBlockFlow()))
2163             r->setChildNeedsLayout(true, false);
2164             
2165         // If relayoutChildren is set and we have percentage padding, we also need to invalidate the child's pref widths.
2166         if (relayoutChildren && (r->style()->paddingStart().isPercent() || r->style()->paddingEnd().isPercent()))
2167             r->setPreferredLogicalWidthsDirty(true, false);
2168         
2169         if (!r->needsLayout())
2170             r->markForPaginationRelayoutIfNeeded();
2171
2172         // We don't have to do a full layout.  We just have to update our position. Try that first. If we have shrink-to-fit width
2173         // and we hit the available width constraint, the layoutIfNeeded() will catch it and do a full layout.
2174         if (r->needsPositionedMovementLayoutOnly() && r->tryLayoutDoingPositionedMovementOnly())
2175             r->setNeedsLayout(false);
2176         r->layoutIfNeeded();
2177     }
2178     
2179     if (hasColumns())
2180         view()->layoutState()->m_columnInfo = columnInfo(); // FIXME: Kind of gross. We just put this back into the layout state so that pop() will work.
2181 }
2182
2183 void RenderBlock::markPositionedObjectsForLayout()
2184 {
2185     if (m_positionedObjects) {
2186         RenderBox* r;
2187         Iterator end = m_positionedObjects->end();
2188         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2189             r = *it;
2190             r->setChildNeedsLayout(true);
2191         }
2192     }
2193 }
2194
2195 void RenderBlock::markForPaginationRelayoutIfNeeded()
2196 {
2197     ASSERT(!needsLayout());
2198     if (needsLayout())
2199         return;
2200
2201     if (view()->layoutState()->pageLogicalHeightChanged() || (view()->layoutState()->pageLogicalHeight() && view()->layoutState()->pageLogicalOffset(logicalTop()) != pageLogicalOffset()))
2202         setChildNeedsLayout(true, false);
2203 }
2204
2205 void RenderBlock::repaintOverhangingFloats(bool paintAllDescendants)
2206 {
2207     // Repaint any overhanging floats (if we know we're the one to paint them).
2208     if (hasOverhangingFloats()) {
2209         // We think that we must be in a bad state if m_floatingObjects is nil at this point, so 
2210         // we assert on Debug builds and nil-check Release builds.
2211         ASSERT(m_floatingObjects);
2212         if (!m_floatingObjects)
2213             return;
2214
2215         // FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
2216         // in this block. Better yet would be to push extra state for the containers of other floats.
2217         view()->disableLayoutState();
2218         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2219         FloatingObjectSetIterator end = floatingObjectSet.end();
2220         for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
2221             FloatingObject* r = *it;
2222             // Only repaint the object if it is overhanging, is not in its own layer, and
2223             // is our responsibility to paint (m_shouldPaint is set). When paintAllDescendants is true, the latter
2224             // condition is replaced with being a descendant of us.
2225             if (logicalBottomForFloat(r) > logicalHeight() && ((paintAllDescendants && r->m_renderer->isDescendantOf(this)) || r->m_shouldPaint) && !r->m_renderer->hasSelfPaintingLayer()) {
2226                 r->m_renderer->repaint();
2227                 r->m_renderer->repaintOverhangingFloats();
2228             }
2229         }
2230         view()->enableLayoutState();
2231     }
2232 }
2233  
2234 void RenderBlock::paint(PaintInfo& paintInfo, int tx, int ty)
2235 {
2236     tx += x();
2237     ty += y();
2238     
2239     PaintPhase phase = paintInfo.phase;
2240
2241     // Check if we need to do anything at all.
2242     // FIXME: Could eliminate the isRoot() check if we fix background painting so that the RenderView
2243     // paints the root's background.
2244     if (!isRoot()) {
2245         IntRect overflowBox = visualOverflowRect();
2246         flipForWritingMode(overflowBox);
2247         overflowBox.inflate(maximalOutlineSize(paintInfo.phase));
2248         overflowBox.move(tx, ty);
2249         if (!overflowBox.intersects(paintInfo.rect))
2250             return;
2251     }
2252
2253     bool pushedClip = pushContentsClip(paintInfo, tx, ty);
2254     paintObject(paintInfo, tx, ty);
2255     if (pushedClip)
2256         popContentsClip(paintInfo, phase, tx, ty);
2257
2258     // Our scrollbar widgets paint exactly when we tell them to, so that they work properly with
2259     // z-index.  We paint after we painted the background/border, so that the scrollbars will
2260     // sit above the background/border.
2261     if (hasOverflowClip() && style()->visibility() == VISIBLE && (phase == PaintPhaseBlockBackground || phase == PaintPhaseChildBlockBackground) && paintInfo.shouldPaintWithinRoot(this))
2262         layer()->paintOverflowControls(paintInfo.context, tx, ty, paintInfo.rect);
2263 }
2264
2265 void RenderBlock::paintColumnRules(PaintInfo& paintInfo, int tx, int ty)
2266 {
2267     const Color& ruleColor = style()->visitedDependentColor(CSSPropertyWebkitColumnRuleColor);
2268     bool ruleTransparent = style()->columnRuleIsTransparent();
2269     EBorderStyle ruleStyle = style()->columnRuleStyle();
2270     int ruleWidth = style()->columnRuleWidth();
2271     int colGap = columnGap();
2272     bool renderRule = ruleStyle > BHIDDEN && !ruleTransparent && ruleWidth <= colGap;
2273     if (!renderRule)
2274         return;
2275
2276     // We need to do multiple passes, breaking up our child painting into strips.
2277     ColumnInfo* colInfo = columnInfo();
2278     unsigned colCount = columnCount(colInfo);
2279     int currLogicalLeftOffset = style()->isLeftToRightDirection() ? 0 : contentLogicalWidth();
2280     int ruleAdd = logicalLeftOffsetForContent();
2281     int ruleLogicalLeft = style()->isLeftToRightDirection() ? 0 : contentLogicalWidth();
2282     for (unsigned i = 0; i < colCount; i++) {
2283         IntRect colRect = columnRectAt(colInfo, i);
2284
2285         int inlineDirectionSize = isHorizontalWritingMode() ? colRect.width() : colRect.height();
2286         
2287         // Move to the next position.
2288         if (style()->isLeftToRightDirection()) {
2289             ruleLogicalLeft += inlineDirectionSize + colGap / 2;
2290             currLogicalLeftOffset += inlineDirectionSize + colGap;
2291         } else {
2292             ruleLogicalLeft -= (inlineDirectionSize + colGap / 2);
2293             currLogicalLeftOffset -= (inlineDirectionSize + colGap);
2294         }
2295        
2296         // Now paint the column rule.
2297         if (i < colCount - 1) {
2298             int ruleLeft = isHorizontalWritingMode() ? tx + ruleLogicalLeft - ruleWidth / 2 + ruleAdd : tx + borderBefore() + paddingBefore();
2299             int ruleRight = isHorizontalWritingMode() ? ruleLeft + ruleWidth : ruleLeft + contentWidth();
2300             int ruleTop = isHorizontalWritingMode() ? ty + borderTop() + paddingTop() : ty + ruleLogicalLeft - ruleWidth / 2 + ruleAdd;
2301             int ruleBottom = isHorizontalWritingMode() ? ruleTop + contentHeight() : ruleTop + ruleWidth;
2302             drawLineForBoxSide(paintInfo.context, ruleLeft, ruleTop, ruleRight, ruleBottom,
2303                                style()->isLeftToRightDirection() ? BSLeft : BSRight, ruleColor, ruleStyle, 0, 0);
2304         }
2305         
2306         ruleLogicalLeft = currLogicalLeftOffset;
2307     }
2308 }
2309
2310 void RenderBlock::paintColumnContents(PaintInfo& paintInfo, int tx, int ty, bool paintingFloats)
2311 {
2312     // We need to do multiple passes, breaking up our child painting into strips.
2313     GraphicsContext* context = paintInfo.context;
2314     ColumnInfo* colInfo = columnInfo();
2315     unsigned colCount = columnCount(colInfo);
2316     if (!colCount)
2317         return;
2318     int currLogicalTopOffset = 0;
2319     for (unsigned i = 0; i < colCount; i++) {
2320         // For each rect, we clip to the rect, and then we adjust our coords.
2321         IntRect colRect = columnRectAt(colInfo, i);
2322         flipForWritingMode(colRect);
2323         int logicalLeftOffset = (isHorizontalWritingMode() ? colRect.x() : colRect.y()) - logicalLeftOffsetForContent();
2324         IntSize offset = isHorizontalWritingMode() ? IntSize(logicalLeftOffset, currLogicalTopOffset) : IntSize(currLogicalTopOffset, logicalLeftOffset);
2325         colRect.move(tx, ty);
2326         PaintInfo info(paintInfo);
2327         info.rect.intersect(colRect);
2328         
2329         if (!info.rect.isEmpty()) {
2330             GraphicsContextStateSaver stateSaver(*context);
2331             
2332             // Each strip pushes a clip, since column boxes are specified as being
2333             // like overflow:hidden.
2334             context->clip(colRect);
2335
2336             // Adjust our x and y when painting.
2337             int finalX = tx + offset.width();
2338             int finalY = ty + offset.height();
2339             if (paintingFloats)
2340                 paintFloats(info, finalX, finalY, paintInfo.phase == PaintPhaseSelection || paintInfo.phase == PaintPhaseTextClip);
2341             else
2342                 paintContents(info, finalX, finalY);
2343         }
2344
2345         int blockDelta = (isHorizontalWritingMode() ? colRect.height() : colRect.width());
2346         if (style()->isFlippedBlocksWritingMode())
2347             currLogicalTopOffset += blockDelta;
2348         else
2349             currLogicalTopOffset -= blockDelta;
2350     }
2351 }
2352
2353 void RenderBlock::paintContents(PaintInfo& paintInfo, int tx, int ty)
2354 {
2355     // Avoid painting descendants of the root element when stylesheets haven't loaded.  This eliminates FOUC.
2356     // It's ok not to draw, because later on, when all the stylesheets do load, updateStyleSelector on the Document
2357     // will do a full repaint().
2358     if (document()->didLayoutWithPendingStylesheets() && !isRenderView())
2359         return;
2360
2361     if (childrenInline())
2362         m_lineBoxes.paint(this, paintInfo, tx, ty);
2363     else
2364         paintChildren(paintInfo, tx, ty);
2365 }
2366
2367 void RenderBlock::paintChildren(PaintInfo& paintInfo, int tx, int ty)
2368 {
2369     PaintPhase newPhase = (paintInfo.phase == PaintPhaseChildOutlines) ? PaintPhaseOutline : paintInfo.phase;
2370     newPhase = (newPhase == PaintPhaseChildBlockBackgrounds) ? PaintPhaseChildBlockBackground : newPhase;
2371     
2372     // We don't paint our own background, but we do let the kids paint their backgrounds.
2373     PaintInfo info(paintInfo);
2374     info.phase = newPhase;
2375     info.updatePaintingRootForChildren(this);
2376     
2377     // FIXME: Paint-time pagination is obsolete and is now only used by embedded WebViews inside AppKit
2378     // NSViews.  Do not add any more code for this.
2379     RenderView* renderView = view();
2380     bool usePrintRect = !renderView->printRect().isEmpty();
2381     
2382     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {        
2383         // Check for page-break-before: always, and if it's set, break and bail.
2384         bool checkBeforeAlways = !childrenInline() && (usePrintRect && child->style()->pageBreakBefore() == PBALWAYS);
2385         if (checkBeforeAlways
2386             && (ty + child->y()) > paintInfo.rect.y()
2387             && (ty + child->y()) < paintInfo.rect.maxY()) {
2388             view()->setBestTruncatedAt(ty + child->y(), this, true);
2389             return;
2390         }
2391
2392         if (!child->isFloating() && child->isReplaced() && usePrintRect && child->height() <= renderView->printRect().height()) {
2393             // Paginate block-level replaced elements.
2394             if (ty + child->y() + child->height() > renderView->printRect().maxY()) {
2395                 if (ty + child->y() < renderView->truncatedAt())
2396                     renderView->setBestTruncatedAt(ty + child->y(), child);
2397                 // If we were able to truncate, don't paint.
2398                 if (ty + child->y() >= renderView->truncatedAt())
2399                     break;
2400             }
2401         }
2402
2403         IntPoint childPoint = flipForWritingMode(child, IntPoint(tx, ty), ParentToChildFlippingAdjustment);
2404         if (!child->hasSelfPaintingLayer() && !child->isFloating())
2405             child->paint(info, childPoint.x(), childPoint.y());
2406
2407         // Check for page-break-after: always, and if it's set, break and bail.
2408         bool checkAfterAlways = !childrenInline() && (usePrintRect && child->style()->pageBreakAfter() == PBALWAYS);
2409         if (checkAfterAlways
2410             && (ty + child->y() + child->height()) > paintInfo.rect.y()
2411             && (ty + child->y() + child->height()) < paintInfo.rect.maxY()) {
2412             view()->setBestTruncatedAt(ty + child->y() + child->height() + max(0, child->collapsedMarginAfter()), this, true);
2413             return;
2414         }
2415     }
2416 }
2417
2418 void RenderBlock::paintCaret(PaintInfo& paintInfo, int tx, int ty, CaretType type)
2419 {
2420     SelectionController* selection = type == CursorCaret ? frame()->selection() : frame()->page()->dragCaretController();
2421
2422     // Paint the caret if the SelectionController says so or if caret browsing is enabled
2423     bool caretBrowsing = frame()->settings() && frame()->settings()->caretBrowsingEnabled();
2424     RenderObject* caretPainter = selection->caretRenderer();
2425     if (caretPainter == this && (selection->isContentEditable() || caretBrowsing)) {
2426         // Convert the painting offset into the local coordinate system of this renderer,
2427         // to match the localCaretRect computed by the SelectionController
2428         offsetForContents(tx, ty);
2429
2430         if (type == CursorCaret)
2431             frame()->selection()->paintCaret(paintInfo.context, tx, ty, paintInfo.rect);
2432         else
2433             frame()->selection()->paintDragCaret(paintInfo.context, tx, ty, paintInfo.rect);
2434     }
2435 }
2436
2437 void RenderBlock::paintObject(PaintInfo& paintInfo, int tx, int ty)
2438 {
2439     PaintPhase paintPhase = paintInfo.phase;
2440
2441     // 1. paint background, borders etc
2442     if ((paintPhase == PaintPhaseBlockBackground || paintPhase == PaintPhaseChildBlockBackground) && style()->visibility() == VISIBLE) {
2443         if (hasBoxDecorations())
2444             paintBoxDecorations(paintInfo, tx, ty);
2445         if (hasColumns())
2446             paintColumnRules(paintInfo, tx, ty);
2447     }
2448
2449     if (paintPhase == PaintPhaseMask && style()->visibility() == VISIBLE) {
2450         paintMask(paintInfo, tx, ty);
2451         return;
2452     }
2453
2454     // We're done.  We don't bother painting any children.
2455     if (paintPhase == PaintPhaseBlockBackground)
2456         return;
2457
2458     // Adjust our painting position if we're inside a scrolled layer (e.g., an overflow:auto div).
2459     int scrolledX = tx;
2460     int scrolledY = ty;
2461     if (hasOverflowClip()) {
2462         IntSize offset = layer()->scrolledContentOffset();
2463         scrolledX -= offset.width();
2464         scrolledY -= offset.height();
2465     }
2466
2467     // 2. paint contents
2468     if (paintPhase != PaintPhaseSelfOutline) {
2469         if (hasColumns())
2470             paintColumnContents(paintInfo, scrolledX, scrolledY);
2471         else
2472             paintContents(paintInfo, scrolledX, scrolledY);
2473     }
2474
2475     // 3. paint selection
2476     // FIXME: Make this work with multi column layouts.  For now don't fill gaps.
2477     bool isPrinting = document()->printing();
2478     if (!isPrinting && !hasColumns())
2479         paintSelection(paintInfo, scrolledX, scrolledY); // Fill in gaps in selection on lines and between blocks.
2480
2481     // 4. paint floats.
2482     if (paintPhase == PaintPhaseFloat || paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip) {
2483         if (hasColumns())
2484             paintColumnContents(paintInfo, scrolledX, scrolledY, true);
2485         else
2486             paintFloats(paintInfo, scrolledX, scrolledY, paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip);
2487     }
2488
2489     // 5. paint outline.
2490     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseSelfOutline) && hasOutline() && style()->visibility() == VISIBLE)
2491         paintOutline(paintInfo.context, tx, ty, width(), height());
2492
2493     // 6. paint continuation outlines.
2494     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseChildOutlines)) {
2495         RenderInline* inlineCont = inlineElementContinuation();
2496         if (inlineCont && inlineCont->hasOutline() && inlineCont->style()->visibility() == VISIBLE) {
2497             RenderInline* inlineRenderer = toRenderInline(inlineCont->node()->renderer());
2498             RenderBlock* cb = containingBlock();
2499
2500             bool inlineEnclosedInSelfPaintingLayer = false;
2501             for (RenderBoxModelObject* box = inlineRenderer; box != cb; box = box->parent()->enclosingBoxModelObject()) {
2502                 if (box->hasSelfPaintingLayer()) {
2503                     inlineEnclosedInSelfPaintingLayer = true;
2504                     break;
2505                 }
2506             }
2507
2508             if (!inlineEnclosedInSelfPaintingLayer)
2509                 cb->addContinuationWithOutline(inlineRenderer);
2510             else if (!inlineRenderer->firstLineBox())
2511                 inlineRenderer->paintOutline(paintInfo.context, tx - x() + inlineRenderer->containingBlock()->x(),
2512                                              ty - y() + inlineRenderer->containingBlock()->y());
2513         }
2514         paintContinuationOutlines(paintInfo, tx, ty);
2515     }
2516
2517     // 7. paint caret.
2518     // If the caret's node's render object's containing block is this block, and the paint action is PaintPhaseForeground,
2519     // then paint the caret.
2520     if (paintPhase == PaintPhaseForeground) {        
2521         paintCaret(paintInfo, scrolledX, scrolledY, CursorCaret);
2522         paintCaret(paintInfo, scrolledX, scrolledY, DragCaret);
2523     }
2524 }
2525
2526 IntPoint RenderBlock::flipFloatForWritingMode(const FloatingObject* child, const IntPoint& point) const
2527 {
2528     if (!style()->isFlippedBlocksWritingMode())
2529         return point;
2530     
2531     // This is similar to the ParentToChildFlippingAdjustment in RenderBox::flipForWritingMode.  We have to subtract out our left/top offsets twice, since
2532     // it's going to get added back in.  We hide this complication here so that the calling code looks normal for the unflipped
2533     // case.
2534     if (isHorizontalWritingMode())
2535         return IntPoint(point.x(), point.y() + height() - child->renderer()->height() - 2 * yPositionForFloatIncludingMargin(child));
2536     return IntPoint(point.x() + width() - child->width() - 2 * xPositionForFloatIncludingMargin(child), point.y());
2537 }
2538
2539 void RenderBlock::paintFloats(PaintInfo& paintInfo, int tx, int ty, bool preservePhase)
2540 {
2541     if (!m_floatingObjects)
2542         return;
2543
2544     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2545     FloatingObjectSetIterator end = floatingObjectSet.end();
2546     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
2547         FloatingObject* r = *it;
2548         // Only paint the object if our m_shouldPaint flag is set.
2549         if (r->m_shouldPaint && !r->m_renderer->hasSelfPaintingLayer()) {
2550             PaintInfo currentPaintInfo(paintInfo);
2551             currentPaintInfo.phase = preservePhase ? paintInfo.phase : PaintPhaseBlockBackground;
2552             IntPoint childPoint = flipFloatForWritingMode(r, IntPoint(tx + xPositionForFloatIncludingMargin(r) - r->m_renderer->x(), ty + yPositionForFloatIncludingMargin(r) - r->m_renderer->y()));
2553             r->m_renderer->paint(currentPaintInfo, childPoint.x(), childPoint.y());
2554             if (!preservePhase) {
2555                 currentPaintInfo.phase = PaintPhaseChildBlockBackgrounds;
2556                 r->m_renderer->paint(currentPaintInfo, childPoint.x(), childPoint.y());
2557                 currentPaintInfo.phase = PaintPhaseFloat;
2558                 r->m_renderer->paint(currentPaintInfo, childPoint.x(), childPoint.y());
2559                 currentPaintInfo.phase = PaintPhaseForeground;
2560                 r->m_renderer->paint(currentPaintInfo, childPoint.x(), childPoint.y());
2561                 currentPaintInfo.phase = PaintPhaseOutline;
2562                 r->m_renderer->paint(currentPaintInfo, childPoint.x(), childPoint.y());
2563             }
2564         }
2565     }
2566 }
2567
2568 void RenderBlock::paintEllipsisBoxes(PaintInfo& paintInfo, int tx, int ty)
2569 {
2570     if (!paintInfo.shouldPaintWithinRoot(this) || !firstLineBox())
2571         return;
2572
2573     if (style()->visibility() == VISIBLE && paintInfo.phase == PaintPhaseForeground) {
2574         // We can check the first box and last box and avoid painting if we don't
2575         // intersect.
2576         int yPos = ty + firstLineBox()->y();
2577         int h = lastLineBox()->y() + lastLineBox()->logicalHeight() - firstLineBox()->y();
2578         if (yPos >= paintInfo.rect.maxY() || yPos + h <= paintInfo.rect.y())
2579             return;
2580
2581         // See if our boxes intersect with the dirty rect.  If so, then we paint
2582         // them.  Note that boxes can easily overlap, so we can't make any assumptions
2583         // based off positions of our first line box or our last line box.
2584         for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2585             yPos = ty + curr->y();
2586             h = curr->logicalHeight();
2587             if (curr->ellipsisBox() && yPos < paintInfo.rect.maxY() && yPos + h > paintInfo.rect.y())
2588                 curr->paintEllipsisBox(paintInfo, tx, ty, curr->lineTop(), curr->lineBottom());
2589         }
2590     }
2591 }
2592
2593 RenderInline* RenderBlock::inlineElementContinuation() const
2594
2595     RenderBoxModelObject* continuation = this->continuation();
2596     return continuation && continuation->isInline() ? toRenderInline(continuation) : 0;
2597 }
2598
2599 RenderBlock* RenderBlock::blockElementContinuation() const
2600 {
2601     RenderBoxModelObject* currentContinuation = continuation();
2602     if (!currentContinuation || currentContinuation->isInline())
2603         return 0;
2604     RenderBlock* nextContinuation = toRenderBlock(currentContinuation);
2605     if (nextContinuation->isAnonymousBlock())
2606         return nextContinuation->blockElementContinuation();
2607     return nextContinuation;
2608 }
2609     
2610 static ContinuationOutlineTableMap* continuationOutlineTable()
2611 {
2612     DEFINE_STATIC_LOCAL(ContinuationOutlineTableMap, table, ());
2613     return &table;
2614 }
2615
2616 void RenderBlock::addContinuationWithOutline(RenderInline* flow)
2617 {
2618     // We can't make this work if the inline is in a layer.  We'll just rely on the broken
2619     // way of painting.
2620     ASSERT(!flow->layer() && !flow->isInlineElementContinuation());
2621     
2622     ContinuationOutlineTableMap* table = continuationOutlineTable();
2623     ListHashSet<RenderInline*>* continuations = table->get(this);
2624     if (!continuations) {
2625         continuations = new ListHashSet<RenderInline*>;
2626         table->set(this, continuations);
2627     }
2628     
2629     continuations->add(flow);
2630 }
2631
2632 bool RenderBlock::paintsContinuationOutline(RenderInline* flow)
2633 {
2634     ContinuationOutlineTableMap* table = continuationOutlineTable();
2635     if (table->isEmpty())
2636         return false;
2637         
2638     ListHashSet<RenderInline*>* continuations = table->get(this);
2639     if (!continuations)
2640         return false;
2641
2642     return continuations->contains(flow);
2643 }
2644
2645 void RenderBlock::paintContinuationOutlines(PaintInfo& info, int tx, int ty)
2646 {
2647     ContinuationOutlineTableMap* table = continuationOutlineTable();
2648     if (table->isEmpty())
2649         return;
2650         
2651     ListHashSet<RenderInline*>* continuations = table->get(this);
2652     if (!continuations)
2653         return;
2654         
2655     // Paint each continuation outline.
2656     ListHashSet<RenderInline*>::iterator end = continuations->end();
2657     for (ListHashSet<RenderInline*>::iterator it = continuations->begin(); it != end; ++it) {
2658         // Need to add in the coordinates of the intervening blocks.
2659         RenderInline* flow = *it;
2660         RenderBlock* block = flow->containingBlock();
2661         for ( ; block && block != this; block = block->containingBlock()) {
2662             tx += block->x();
2663             ty += block->y();
2664         }
2665         ASSERT(block);   
2666         flow->paintOutline(info.context, tx, ty);
2667     }
2668     
2669     // Delete
2670     delete continuations;
2671     table->remove(this);
2672 }
2673
2674 bool RenderBlock::shouldPaintSelectionGaps() const
2675 {
2676     return selectionState() != SelectionNone && style()->visibility() == VISIBLE && isSelectionRoot();
2677 }
2678
2679 bool RenderBlock::isSelectionRoot() const
2680 {
2681     if (!node())
2682         return false;
2683         
2684     // FIXME: Eventually tables should have to learn how to fill gaps between cells, at least in simple non-spanning cases.
2685     if (isTable())
2686         return false;
2687         
2688     if (isBody() || isRoot() || hasOverflowClip() || isRelPositioned() ||
2689         isFloatingOrPositioned() || isTableCell() || isInlineBlockOrInlineTable() || hasTransform() ||
2690         hasReflection() || hasMask() || isWritingModeRoot())
2691         return true;
2692     
2693     if (view() && view()->selectionStart()) {
2694         Node* startElement = view()->selectionStart()->node();
2695         if (startElement && startElement->rootEditableElement() == node())
2696             return true;
2697     }
2698     
2699     return false;
2700 }
2701
2702 GapRects RenderBlock::selectionGapRectsForRepaint(RenderBoxModelObject* repaintContainer)
2703 {
2704     ASSERT(!needsLayout());
2705
2706     if (!shouldPaintSelectionGaps())
2707         return GapRects();
2708
2709     // FIXME: this is broken with transforms
2710     TransformState transformState(TransformState::ApplyTransformDirection, FloatPoint());
2711     mapLocalToContainer(repaintContainer, false, false, transformState);
2712     IntPoint offsetFromRepaintContainer = roundedIntPoint(transformState.mappedPoint());
2713
2714     if (hasOverflowClip())
2715         offsetFromRepaintContainer -= layer()->scrolledContentOffset();
2716
2717     int lastTop = 0;
2718     int lastLeft = logicalLeftSelectionOffset(this, lastTop);
2719     int lastRight = logicalRightSelectionOffset(this, lastTop);
2720     
2721     return selectionGaps(this, offsetFromRepaintContainer, IntSize(), lastTop, lastLeft, lastRight);
2722 }
2723
2724 void RenderBlock::paintSelection(PaintInfo& paintInfo, int tx, int ty)
2725 {
2726     if (shouldPaintSelectionGaps() && paintInfo.phase == PaintPhaseForeground) {
2727         int lastTop = 0;
2728         int lastLeft = logicalLeftSelectionOffset(this, lastTop);
2729         int lastRight = logicalRightSelectionOffset(this, lastTop);
2730         GraphicsContextStateSaver stateSaver(*paintInfo.context);
2731
2732         IntRect gapRectsBounds = selectionGaps(this, IntPoint(tx, ty), IntSize(), lastTop, lastLeft, lastRight, &paintInfo);
2733         if (!gapRectsBounds.isEmpty()) {
2734             if (RenderLayer* layer = enclosingLayer()) {
2735                 gapRectsBounds.move(IntSize(-tx, -ty));
2736                 if (!hasLayer()) {
2737                     IntRect localBounds(gapRectsBounds);
2738                     flipForWritingMode(localBounds);
2739                     gapRectsBounds = localToContainerQuad(FloatRect(localBounds), layer->renderer()).enclosingBoundingBox();
2740                     gapRectsBounds.move(layer->scrolledContentOffset());
2741                 }
2742                 layer->addBlockSelectionGapsBounds(gapRectsBounds);
2743             }
2744         }
2745     }
2746 }
2747
2748 static void clipOutPositionedObjects(const PaintInfo* paintInfo, const IntPoint& offset, RenderBlock::PositionedObjectsListHashSet* positionedObjects)
2749 {
2750     if (!positionedObjects)
2751         return;
2752     
2753     RenderBlock::PositionedObjectsListHashSet::const_iterator end = positionedObjects->end();
2754     for (RenderBlock::PositionedObjectsListHashSet::const_iterator it = positionedObjects->begin(); it != end; ++it) {
2755         RenderBox* r = *it;
2756         paintInfo->context->clipOut(IntRect(offset.x() + r->x(), offset.y() + r->y(), r->width(), r->height()));
2757     }
2758 }
2759
2760 static int blockDirectionOffset(RenderBlock* rootBlock, const IntSize& offsetFromRootBlock)
2761 {
2762     return rootBlock->isHorizontalWritingMode() ? offsetFromRootBlock.height() : offsetFromRootBlock.width();
2763 }
2764
2765 static int inlineDirectionOffset(RenderBlock* rootBlock, const IntSize& offsetFromRootBlock)
2766 {
2767     return rootBlock->isHorizontalWritingMode() ? offsetFromRootBlock.width() : offsetFromRootBlock.height();
2768 }
2769
2770 IntRect RenderBlock::logicalRectToPhysicalRect(const IntPoint& rootBlockPhysicalPosition, const IntRect& logicalRect)
2771 {
2772     IntRect result;
2773     if (isHorizontalWritingMode())
2774         result = logicalRect;
2775     else
2776         result = IntRect(logicalRect.y(), logicalRect.x(), logicalRect.height(), logicalRect.width());
2777     flipForWritingMode(result);
2778     result.move(rootBlockPhysicalPosition.x(), rootBlockPhysicalPosition.y());
2779     return result;
2780 }
2781
2782 GapRects RenderBlock::selectionGaps(RenderBlock* rootBlock, const IntPoint& rootBlockPhysicalPosition, const IntSize& offsetFromRootBlock,
2783                                     int& lastLogicalTop, int& lastLogicalLeft, int& lastLogicalRight, const PaintInfo* paintInfo)
2784 {
2785     // IMPORTANT: Callers of this method that intend for painting to happen need to do a save/restore.
2786     // Clip out floating and positioned objects when painting selection gaps.
2787     if (paintInfo) {
2788         // Note that we don't clip out overflow for positioned objects.  We just stick to the border box.
2789         IntRect flippedBlockRect = IntRect(offsetFromRootBlock.width(), offsetFromRootBlock.height(), width(), height());
2790         rootBlock->flipForWritingMode(flippedBlockRect);
2791         flippedBlockRect.move(rootBlockPhysicalPosition.x(), rootBlockPhysicalPosition.y());
2792         clipOutPositionedObjects(paintInfo, flippedBlockRect.location(), m_positionedObjects.get());
2793         if (isBody() || isRoot()) // The <body> must make sure to examine its containingBlock's positioned objects.
2794             for (RenderBlock* cb = containingBlock(); cb && !cb->isRenderView(); cb = cb->containingBlock())
2795                 clipOutPositionedObjects(paintInfo, IntPoint(cb->x(), cb->y()), cb->m_positionedObjects.get()); // FIXME: Not right for flipped writing modes.
2796         if (m_floatingObjects) {
2797             FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2798             FloatingObjectSetIterator end = floatingObjectSet.end();
2799             for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
2800                 FloatingObject* r = *it;
2801                 IntRect floatBox = IntRect(offsetFromRootBlock.width() + xPositionForFloatIncludingMargin(r),
2802                                            offsetFromRootBlock.height() + yPositionForFloatIncludingMargin(r),
2803                                            r->m_renderer->width(), r->m_renderer->height());
2804                 rootBlock->flipForWritingMode(floatBox);
2805                 floatBox.move(rootBlockPhysicalPosition.x(), rootBlockPhysicalPosition.y());
2806                 paintInfo->context->clipOut(floatBox);
2807             }
2808         }
2809     }
2810
2811     // FIXME: overflow: auto/scroll regions need more math here, since painting in the border box is different from painting in the padding box (one is scrolled, the other is
2812     // fixed).
2813     GapRects result;
2814     if (!isBlockFlow()) // FIXME: Make multi-column selection gap filling work someday.
2815         return result;
2816
2817     if (hasColumns() || hasTransform() || style()->columnSpan()) {
2818         // FIXME: We should learn how to gap fill multiple columns and transforms eventually.
2819         lastLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + logicalHeight();
2820         lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, logicalHeight());
2821         lastLogicalRight = logicalRightSelectionOffset(rootBlock, logicalHeight());
2822         return result;
2823     }
2824
2825     if (childrenInline())
2826         result = inlineSelectionGaps(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, paintInfo);
2827     else
2828         result = blockSelectionGaps(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, paintInfo);
2829
2830     // Go ahead and fill the vertical gap all the way to the bottom of our block if the selection extends past our block.
2831     if (rootBlock == this && (selectionState() != SelectionBoth && selectionState() != SelectionEnd))
2832         result.uniteCenter(blockSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, 
2833                                              logicalHeight(), paintInfo));
2834     return result;
2835 }
2836
2837 GapRects RenderBlock::inlineSelectionGaps(RenderBlock* rootBlock, const IntPoint& rootBlockPhysicalPosition, const IntSize& offsetFromRootBlock,
2838                                           int& lastLogicalTop, int& lastLogicalLeft, int& lastLogicalRight, const PaintInfo* paintInfo)
2839 {
2840     GapRects result;
2841
2842     bool containsStart = selectionState() == SelectionStart || selectionState() == SelectionBoth;
2843
2844     if (!firstLineBox()) {
2845         if (containsStart) {
2846             // Go ahead and update our lastLogicalTop to be the bottom of the block.  <hr>s or empty blocks with height can trip this
2847             // case.
2848             lastLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + logicalHeight();
2849             lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, logicalHeight());
2850             lastLogicalRight = logicalRightSelectionOffset(rootBlock, logicalHeight());
2851         }
2852         return result;
2853     }
2854
2855     RootInlineBox* lastSelectedLine = 0;
2856     RootInlineBox* curr;
2857     for (curr = firstRootBox(); curr && !curr->hasSelectedChildren(); curr = curr->nextRootBox()) { }
2858
2859     // Now paint the gaps for the lines.
2860     for (; curr && curr->hasSelectedChildren(); curr = curr->nextRootBox()) {
2861         int selTop =  curr->selectionTop();
2862         int selHeight = curr->selectionHeight();
2863
2864         if (!containsStart && !lastSelectedLine &&
2865             selectionState() != SelectionStart && selectionState() != SelectionBoth)
2866             result.uniteCenter(blockSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, 
2867                                                  selTop, paintInfo));
2868         
2869         IntRect logicalRect(curr->logicalLeft(), selTop, curr->logicalWidth(), selTop + selHeight);
2870         logicalRect.move(isHorizontalWritingMode() ? offsetFromRootBlock : IntSize(offsetFromRootBlock.height(), offsetFromRootBlock.width()));
2871         IntRect physicalRect = rootBlock->logicalRectToPhysicalRect(rootBlockPhysicalPosition, logicalRect);
2872         if (!paintInfo || (isHorizontalWritingMode() && physicalRect.y() < paintInfo->rect.maxY() && physicalRect.maxY() > paintInfo->rect.y())
2873             || (!isHorizontalWritingMode() && physicalRect.x() < paintInfo->rect.maxX() && physicalRect.maxX() > paintInfo->rect.x()))
2874             result.unite(curr->lineSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, selTop, selHeight, paintInfo));
2875
2876         lastSelectedLine = curr;
2877     }
2878
2879     if (containsStart && !lastSelectedLine)
2880         // VisibleSelection must start just after our last line.
2881         lastSelectedLine = lastRootBox();
2882
2883     if (lastSelectedLine && selectionState() != SelectionEnd && selectionState() != SelectionBoth) {
2884         // Go ahead and update our lastY to be the bottom of the last selected line.
2885         lastLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + lastSelectedLine->selectionBottom();
2886         lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, lastSelectedLine->selectionBottom());
2887         lastLogicalRight = logicalRightSelectionOffset(rootBlock, lastSelectedLine->selectionBottom());
2888     }
2889     return result;
2890 }
2891
2892 GapRects RenderBlock::blockSelectionGaps(RenderBlock* rootBlock, const IntPoint& rootBlockPhysicalPosition, const IntSize& offsetFromRootBlock,
2893                                          int& lastLogicalTop, int& lastLogicalLeft, int& lastLogicalRight, const PaintInfo* paintInfo)
2894 {
2895     GapRects result;
2896
2897     // Go ahead and jump right to the first block child that contains some selected objects.
2898     RenderBox* curr;
2899     for (curr = firstChildBox(); curr && curr->selectionState() == SelectionNone; curr = curr->nextSiblingBox()) { }
2900
2901     for (bool sawSelectionEnd = false; curr && !sawSelectionEnd; curr = curr->nextSiblingBox()) {
2902         SelectionState childState = curr->selectionState();
2903         if (childState == SelectionBoth || childState == SelectionEnd)
2904             sawSelectionEnd = true;
2905
2906         if (curr->isFloatingOrPositioned())
2907             continue; // We must be a normal flow object in order to even be considered.
2908
2909         if (curr->isRelPositioned() && curr->hasLayer()) {
2910             // If the relposition offset is anything other than 0, then treat this just like an absolute positioned element.
2911             // Just disregard it completely.
2912             IntSize relOffset = curr->layer()->relativePositionOffset();
2913             if (relOffset.width() || relOffset.height())
2914                 continue;
2915         }
2916
2917         bool paintsOwnSelection = curr->shouldPaintSelectionGaps() || curr->isTable(); // FIXME: Eventually we won't special-case table like this.
2918         bool fillBlockGaps = paintsOwnSelection || (curr->canBeSelectionLeaf() && childState != SelectionNone);
2919         if (fillBlockGaps) {
2920             // We need to fill the vertical gap above this object.
2921             if (childState == SelectionEnd || childState == SelectionInside)
2922                 // Fill the gap above the object.
2923                 result.uniteCenter(blockSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, 
2924                                                      curr->logicalTop(), paintInfo));
2925
2926             // Only fill side gaps for objects that paint their own selection if we know for sure the selection is going to extend all the way *past*
2927             // our object.  We know this if the selection did not end inside our object.
2928             if (paintsOwnSelection && (childState == SelectionStart || sawSelectionEnd))
2929                 childState = SelectionNone;
2930
2931             // Fill side gaps on this object based off its state.
2932             bool leftGap, rightGap;
2933             getSelectionGapInfo(childState, leftGap, rightGap);
2934
2935             if (leftGap)
2936                 result.uniteLeft(logicalLeftSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, this, curr->logicalLeft(), curr->logicalTop(), curr->logicalHeight(), paintInfo));
2937             if (rightGap)
2938                 result.uniteRight(logicalRightSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, this, curr->logicalRight(), curr->logicalTop(), curr->logicalHeight(), paintInfo));
2939
2940             // Update lastLogicalTop to be just underneath the object.  lastLogicalLeft and lastLogicalRight extend as far as
2941             // they can without bumping into floating or positioned objects.  Ideally they will go right up
2942             // to the border of the root selection block.
2943             lastLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + curr->logicalBottom();
2944             lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, curr->logicalBottom());
2945             lastLogicalRight = logicalRightSelectionOffset(rootBlock, curr->logicalBottom());
2946         } else if (childState != SelectionNone)
2947             // We must be a block that has some selected object inside it.  Go ahead and recur.
2948             result.unite(toRenderBlock(curr)->selectionGaps(rootBlock, rootBlockPhysicalPosition, IntSize(offsetFromRootBlock.width() + curr->x(), offsetFromRootBlock.height() + curr->y()), 
2949                                                             lastLogicalTop, lastLogicalLeft, lastLogicalRight, paintInfo));
2950     }
2951     return result;
2952 }
2953
2954 IntRect RenderBlock::blockSelectionGap(RenderBlock* rootBlock, const IntPoint& rootBlockPhysicalPosition, const IntSize& offsetFromRootBlock,
2955                                        int lastLogicalTop, int lastLogicalLeft, int lastLogicalRight, int logicalBottom, const PaintInfo* paintInfo)
2956 {
2957     int logicalTop = lastLogicalTop;
2958     int logicalHeight = blockDirectionOffset(rootBlock, offsetFromRootBlock) + logicalBottom - logicalTop;
2959     if (logicalHeight <= 0)
2960         return IntRect();
2961
2962     // Get the selection offsets for the bottom of the gap
2963     int logicalLeft = max(lastLogicalLeft, logicalLeftSelectionOffset(rootBlock, logicalBottom));
2964     int logicalRight = min(lastLogicalRight, logicalRightSelectionOffset(rootBlock, logicalBottom));
2965     int logicalWidth = logicalRight - logicalLeft;
2966     if (logicalWidth <= 0)
2967         return IntRect();
2968
2969     IntRect gapRect = rootBlock->logicalRectToPhysicalRect(rootBlockPhysicalPosition, IntRect(logicalLeft, logicalTop, logicalWidth, logicalHeight));
2970     if (paintInfo)
2971         paintInfo->context->fillRect(gapRect, selectionBackgroundColor(), style()->colorSpace());
2972     return gapRect;
2973 }
2974
2975 IntRect RenderBlock::logicalLeftSelectionGap(RenderBlock* rootBlock, const IntPoint& rootBlockPhysicalPosition, const IntSize& offsetFromRootBlock,
2976                                              RenderObject* selObj, int logicalLeft, int logicalTop, int logicalHeight, const PaintInfo* paintInfo)
2977 {
2978     int rootBlockLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + logicalTop;
2979     int rootBlockLogicalLeft = max(logicalLeftSelectionOffset(rootBlock, logicalTop), logicalLeftSelectionOffset(rootBlock, logicalTop + logicalHeight));
2980     int rootBlockLogicalRight = min(inlineDirectionOffset(rootBlock, offsetFromRootBlock) + logicalLeft, min(logicalRightSelectionOffset(rootBlock, logicalTop), logicalRightSelectionOffset(rootBlock, logicalTop + logicalHeight)));
2981     int rootBlockLogicalWidth = rootBlockLogicalRight - rootBlockLogicalLeft;
2982     if (rootBlockLogicalWidth <= 0)
2983         return IntRect();
2984
2985     IntRect gapRect = rootBlock->logicalRectToPhysicalRect(rootBlockPhysicalPosition, IntRect(rootBlockLogicalLeft, rootBlockLogicalTop, rootBlockLogicalWidth, logicalHeight));
2986     if (paintInfo)
2987         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor(), selObj->style()->colorSpace());
2988     return gapRect;
2989 }
2990
2991 IntRect RenderBlock::logicalRightSelectionGap(RenderBlock* rootBlock, const IntPoint& rootBlockPhysicalPosition, const IntSize& offsetFromRootBlock,
2992                                               RenderObject* selObj, int logicalRight, int logicalTop, int logicalHeight, const PaintInfo* paintInfo)
2993 {
2994     int rootBlockLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + logicalTop;
2995     int rootBlockLogicalLeft = max(inlineDirectionOffset(rootBlock, offsetFromRootBlock) + logicalRight, max(logicalLeftSelectionOffset(rootBlock, logicalTop), logicalLeftSelectionOffset(rootBlock, logicalTop + logicalHeight)));
2996     int rootBlockLogicalRight = min(logicalRightSelectionOffset(rootBlock, logicalTop), logicalRightSelectionOffset(rootBlock, logicalTop + logicalHeight));
2997     int rootBlockLogicalWidth = rootBlockLogicalRight - rootBlockLogicalLeft;
2998     if (rootBlockLogicalWidth <= 0)
2999         return IntRect();
3000
3001     IntRect gapRect = rootBlock->logicalRectToPhysicalRect(rootBlockPhysicalPosition, IntRect(rootBlockLogicalLeft, rootBlockLogicalTop, rootBlockLogicalWidth, logicalHeight));
3002     if (paintInfo)
3003         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor(), selObj->style()->colorSpace());
3004     return gapRect;
3005 }
3006
3007 void RenderBlock::getSelectionGapInfo(SelectionState state, bool& leftGap, bool& rightGap)
3008 {
3009     bool ltr = style()->isLeftToRightDirection();
3010     leftGap = (state == RenderObject::SelectionInside) ||
3011               (state == RenderObject::SelectionEnd && ltr) ||
3012               (state == RenderObject::SelectionStart && !ltr);
3013     rightGap = (state == RenderObject::SelectionInside) ||
3014                (state == RenderObject::SelectionStart && ltr) ||
3015                (state == RenderObject::SelectionEnd && !ltr);
3016 }
3017
3018 int RenderBlock::logicalLeftSelectionOffset(RenderBlock* rootBlock, int position)
3019 {
3020     int logicalLeft = logicalLeftOffsetForLine(position, false);
3021     if (logicalLeft == logicalLeftOffsetForContent()) {
3022         if (rootBlock != this)
3023             // The border can potentially be further extended by our containingBlock().
3024             return containingBlock()->logicalLeftSelectionOffset(rootBlock, position + logicalTop());
3025         return logicalLeft;
3026     } else {
3027         RenderBlock* cb = this;
3028         while (cb != rootBlock) {
3029             logicalLeft += cb->logicalLeft();
3030             cb = cb->containingBlock();
3031         }
3032     }
3033     return logicalLeft;
3034 }
3035
3036 int RenderBlock::logicalRightSelectionOffset(RenderBlock* rootBlock, int position)
3037 {
3038     int logicalRight = logicalRightOffsetForLine(position, false);
3039     if (logicalRight == logicalRightOffsetForContent()) {
3040         if (rootBlock != this)
3041             // The border can potentially be further extended by our containingBlock().
3042             return containingBlock()->logicalRightSelectionOffset(rootBlock, position + logicalTop());
3043         return logicalRight;
3044     } else {
3045         RenderBlock* cb = this;
3046         while (cb != rootBlock) {
3047             logicalRight += cb->logicalLeft();
3048             cb = cb->containingBlock();
3049         }
3050     }
3051     return logicalRight;
3052 }
3053
3054 void RenderBlock::insertPositionedObject(RenderBox* o)
3055 {
3056     // Create the list of special objects if we don't aleady have one
3057     if (!m_positionedObjects)
3058         m_positionedObjects = adoptPtr(new PositionedObjectsListHashSet);
3059
3060     m_positionedObjects->add(o);
3061 }
3062
3063 void RenderBlock::removePositionedObject(RenderBox* o)
3064 {
3065     if (m_positionedObjects)
3066         m_positionedObjects->remove(o);
3067 }
3068
3069 void RenderBlock::removePositionedObjects(RenderBlock* o)
3070 {
3071     if (!m_positionedObjects)
3072         return;
3073     
3074     RenderBox* r;
3075     
3076     Iterator end = m_positionedObjects->end();
3077     
3078     Vector<RenderBox*, 16> deadObjects;
3079
3080     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
3081         r = *it;
3082         if (!o || r->isDescendantOf(o)) {
3083             if (o)
3084                 r->setChildNeedsLayout(true, false);
3085             
3086             // It is parent blocks job to add positioned child to positioned objects list of its containing block
3087             // Parent layout needs to be invalidated to ensure this happens.
3088             RenderObject* p = r->parent();
3089             while (p && !p->isRenderBlock())
3090                 p = p->parent();
3091             if (p)
3092                 p->setChildNeedsLayout(true);
3093             
3094             deadObjects.append(r);
3095         }
3096     }
3097     
3098     for (unsigned i = 0; i < deadObjects.size(); i++)
3099         m_positionedObjects->remove(deadObjects.at(i));
3100 }
3101
3102 RenderBlock::FloatingObject* RenderBlock::insertFloatingObject(RenderBox* o)
3103 {
3104     ASSERT(o->isFloating());
3105
3106     // Create the list of special objects if we don't aleady have one
3107     if (!m_floatingObjects)
3108         m_floatingObjects = adoptPtr(new FloatingObjects);
3109     else {
3110         // Don't insert the object again if it's already in the list
3111         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3112         FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
3113         if (it != floatingObjectSet.end())
3114             return *it;
3115     }
3116
3117     // Create the special object entry & append it to the list
3118
3119     FloatingObject* newObj = new FloatingObject(o->style()->floating() == FLEFT ? FloatingObject::FloatLeft : FloatingObject::FloatRight);
3120     
3121     // Our location is irrelevant if we're unsplittable or no pagination is in effect.
3122     // Just go ahead and lay out the float.
3123     bool isChildRenderBlock = o->isRenderBlock();
3124     if (isChildRenderBlock && !o->needsLayout() && view()->layoutState()->pageLogicalHeightChanged())
3125         o->setChildNeedsLayout(true, false);
3126         
3127     bool affectedByPagination = isChildRenderBlock && view()->layoutState()->m_pageLogicalHeight;
3128     if (!affectedByPagination || isWritingModeRoot()) // We are unsplittable if we're a block flow root.
3129         o->layoutIfNeeded();
3130     else {
3131         o->computeLogicalWidth();
3132         o->computeBlockDirectionMargins(this);
3133     }
3134     setLogicalWidthForFloat(newObj, logicalWidthForChild(o) + marginStartForChild(o) + marginEndForChild(o));
3135
3136     newObj->m_shouldPaint = !o->hasSelfPaintingLayer(); // If a layer exists, the float will paint itself.  Otherwise someone else will.
3137     newObj->m_isDescendant = true;
3138     newObj->m_renderer = o;
3139
3140     m_floatingObjects->increaseObjectsCount(newObj->type());
3141     m_floatingObjects->set().add(newObj);
3142     
3143     return newObj;
3144 }
3145
3146 void RenderBlock::removeFloatingObject(RenderBox* o)
3147 {
3148     if (m_floatingObjects) {
3149         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3150         FloatingObjectSet::iterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
3151         if (it != floatingObjectSet.end()) {
3152             FloatingObject* r = *it;
3153             if (childrenInline()) {
3154                 int logicalTop = logicalTopForFloat(r);
3155                 int logicalBottom = logicalBottomForFloat(r);
3156
3157                 // Fix for https://bugs.webkit.org/show_bug.cgi?id=54995.
3158                 if (logicalBottom < 0 || logicalBottom < logicalTop || logicalTop == numeric_limits<int>::max())
3159                     logicalBottom = numeric_limits<int>::max();
3160                 else {
3161                     // Special-case zero- and less-than-zero-height floats: those don't touch
3162                     // the line that they're on, but it still needs to be dirtied. This is
3163                     // accomplished by pretending they have a height of 1.
3164                     logicalBottom = max(logicalBottom, logicalTop + 1);
3165                 }
3166                 markLinesDirtyInBlockRange(0, logicalBottom);
3167             }
3168             m_floatingObjects->decreaseObjectsCount(r->type());
3169             floatingObjectSet.remove(it);
3170             delete r;
3171         }
3172     }
3173 }
3174
3175 void RenderBlock::removeFloatingObjectsBelow(FloatingObject* lastFloat, int logicalOffset)
3176 {
3177     if (!m_floatingObjects)
3178         return;
3179     
3180     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3181     FloatingObject* curr = floatingObjectSet.last();
3182     while (curr != lastFloat && (!curr->isPlaced() || logicalTopForFloat(curr) >= logicalOffset)) {
3183         m_floatingObjects->decreaseObjectsCount(curr->type());
3184         floatingObjectSet.removeLast();
3185         delete curr;
3186         curr = floatingObjectSet.last();
3187     }
3188 }
3189
3190 bool RenderBlock::positionNewFloats()
3191 {
3192     if (!m_floatingObjects)
3193         return false;
3194
3195     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3196     if (floatingObjectSet.isEmpty())
3197         return false;
3198
3199     // If all floats have already been positioned, then we have no work to do.
3200     if (floatingObjectSet.last()->isPlaced())
3201         return false;
3202
3203     // Move backwards through our floating object list until we find a float that has
3204     // already been positioned.  Then we'll be able to move forward, positioning all of
3205     // the new floats that need it.
3206     FloatingObjectSetIterator it = floatingObjectSet.end();
3207     --it; // Go to last item.
3208     FloatingObjectSetIterator begin = floatingObjectSet.begin();
3209     FloatingObject* lastPlacedFloatingObject = 0;
3210     while (it != begin) {
3211         --it;
3212         if ((*it)->isPlaced()) {
3213             lastPlacedFloatingObject = *it;
3214             ++it;
3215             break;
3216         }
3217     }
3218
3219     int logicalTop = logicalHeight();
3220     
3221     // The float cannot start above the top position of the last positioned float.
3222     if (lastPlacedFloatingObject)
3223         logicalTop = max(logicalTopForFloat(lastPlacedFloatingObject), logicalTop);
3224
3225     FloatingObjectSetIterator end = floatingObjectSet.end();
3226     // Now walk through the set of unpositioned floats and place them.
3227     for (; it != end; ++it) {
3228          FloatingObject* floatingObject = *it;
3229         // The containing block is responsible for positioning floats, so if we have floats in our
3230         // list that come from somewhere else, do not attempt to position them.
3231         if (floatingObject->renderer()->containingBlock() != this)
3232             continue;
3233
3234         RenderBox* childBox = floatingObject->renderer();
3235         int childLogicalLeftMargin = style()->isLeftToRightDirection() ? marginStartForChild(childBox) : marginEndForChild(childBox);
3236
3237         int rightOffset = logicalRightOffsetForContent(); // Constant part of right offset.
3238         int leftOffset = logicalLeftOffsetForContent(); // Constant part of left offset.
3239         int floatLogicalWidth = logicalWidthForFloat(floatingObject); // The width we look for.
3240         if (rightOffset - leftOffset < floatLogicalWidth)
3241             floatLogicalWidth = rightOffset - leftOffset; // Never look for more than what will be available.
3242         
3243         IntRect oldRect(childBox->x(), childBox->y() , childBox->width(), childBox->height());
3244
3245         if (childBox->style()->clear() & CLEFT)
3246             logicalTop = max(lowestFloatLogicalBottom(FloatingObject::FloatLeft), logicalTop);
3247         if (childBox->style()->clear() & CRIGHT)
3248             logicalTop = max(lowestFloatLogicalBottom(FloatingObject::FloatRight), logicalTop);
3249
3250         int floatLogicalLeft;
3251         if (childBox->style()->floating() == FLEFT) {
3252             int heightRemainingLeft = 1;
3253             int heightRemainingRight = 1;
3254             floatLogicalLeft = logicalLeftOffsetForLine(logicalTop, leftOffset, false, &heightRemainingLeft);
3255             while (logicalRightOffsetForLine(logicalTop, rightOffset, false, &heightRemainingRight) - floatLogicalLeft < floatLogicalWidth) {
3256                 logicalTop += min(heightRemainingLeft, heightRemainingRight);
3257                 floatLogicalLeft = logicalLeftOffsetForLine(logicalTop, leftOffset, false, &heightRemainingLeft);
3258             }
3259             floatLogicalLeft = max(0, floatLogicalLeft);
3260         } else {
3261             int heightRemainingLeft = 1;
3262             int heightRemainingRight = 1;
3263             floatLogicalLeft = logicalRightOffsetForLine(logicalTop, rightOffset, false, &heightRemainingRight);
3264             while (floatLogicalLeft - logicalLeftOffsetForLine(logicalTop, leftOffset, false, &heightRemainingLeft) < floatLogicalWidth) {
3265                 logicalTop += min(heightRemainingLeft, heightRemainingRight);
3266                 floatLogicalLeft = logicalRightOffsetForLine(logicalTop, rightOffset, false, &heightRemainingRight);
3267             }
3268             floatLogicalLeft -= logicalWidthForFloat(floatingObject); // Use the original width of the float here, since the local variable
3269                                                                       // |floatLogicalWidth| was capped to the available line width.
3270                                                                       // See fast/block/float/clamped-right-float.html.
3271         }
3272         
3273         setLogicalLeftForFloat(floatingObject, floatLogicalLeft);
3274         setLogicalLeftForChild(childBox, floatLogicalLeft + childLogicalLeftMargin);
3275         setLogicalTopForChild(childBox, logicalTop + marginBeforeForChild(childBox));
3276
3277         if (view()->layoutState()->isPaginated()) {
3278             RenderBlock* childBlock = childBox->isRenderBlock() ? toRenderBlock(childBox) : 0;
3279
3280             if (!childBox->needsLayout())
3281                 childBox->markForPaginationRelayoutIfNeeded();;
3282             childBox->layoutIfNeeded();
3283
3284             // If we are unsplittable and don't fit, then we need to move down.
3285             // We include our margins as part of the unsplittable area.
3286             int newLogicalTop = adjustForUnsplittableChild(childBox, logicalTop, true);
3287             
3288             // See if we have a pagination strut that is making us move down further.
3289             // Note that an unsplittable child can't also have a pagination strut, so this is
3290             // exclusive with the case above.
3291             if (childBlock && childBlock->paginationStrut()) {
3292                 newLogicalTop += childBlock->paginationStrut();
3293                 childBlock->setPaginationStrut(0);
3294             }
3295             
3296             if (newLogicalTop != logicalTop) {
3297                 floatingObject->m_paginationStrut = newLogicalTop - logicalTop;
3298                 logicalTop = newLogicalTop;
3299                 setLogicalTopForChild(childBox, logicalTop + marginBeforeForChild(childBox));
3300                 if (childBlock)
3301                     childBlock->setChildNeedsLayout(true, false);
3302                 childBox->layoutIfNeeded();
3303             }
3304         }
3305
3306         setLogicalTopForFloat(floatingObject, logicalTop);
3307         setLogicalHeightForFloat(floatingObject, logicalHeightForChild(childBox) + marginBeforeForChild(childBox) + marginAfterForChild(childBox));
3308
3309         floatingObject->setIsPlaced();
3310
3311         // If the child moved, we have to repaint it.
3312         if (childBox->checkForRepaintDuringLayout())
3313             childBox->repaintDuringLayoutIfMoved(oldRect);
3314     }
3315     return true;
3316 }
3317
3318 void RenderBlock::newLine(EClear clear)
3319 {
3320     positionNewFloats();
3321     // set y position
3322     int newY = 0;
3323     switch (clear)
3324     {
3325         case CLEFT:
3326             newY = lowestFloatLogicalBottom(FloatingObject::FloatLeft);
3327             break;
3328         case CRIGHT:
3329             newY = lowestFloatLogicalBottom(FloatingObject::FloatRight);
3330             break;
3331         case CBOTH:
3332             newY = lowestFloatLogicalBottom();
3333         default:
3334             break;
3335     }
3336     if (height() < newY)
3337         setLogicalHeight(newY);
3338 }
3339
3340 void RenderBlock::addPercentHeightDescendant(RenderBox* descendant)
3341 {
3342     if (!gPercentHeightDescendantsMap) {
3343         gPercentHeightDescendantsMap = new PercentHeightDescendantsMap;
3344         gPercentHeightContainerMap = new PercentHeightContainerMap;
3345     }
3346
3347     HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->get(this);
3348     if (!descendantSet) {
3349         descendantSet = new HashSet<RenderBox*>;
3350         gPercentHeightDescendantsMap->set(this, descendantSet);
3351     }
3352     bool added = descendantSet->add(descendant).second;
3353     if (!added) {
3354         ASSERT(gPercentHeightContainerMap->get(descendant));
3355         ASSERT(gPercentHeightContainerMap->get(descendant)->contains(this));
3356         return;
3357     }
3358
3359     HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->get(descendant);
3360     if (!containerSet) {
3361         containerSet = new HashSet<RenderBlock*>;
3362         gPercentHeightContainerMap->set(descendant, containerSet);
3363     }
3364     ASSERT(!containerSet->contains(this));
3365     containerSet->add(this);
3366 }
3367
3368 void RenderBlock::removePercentHeightDescendant(RenderBox* descendant)
3369 {
3370     if (!gPercentHeightContainerMap)
3371         return;
3372
3373     HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->take(descendant);
3374     if (!containerSet)
3375         return;
3376
3377     HashSet<RenderBlock*>::iterator end = containerSet->end();
3378     for (HashSet<RenderBlock*>::iterator it = containerSet->begin(); it != end; ++it) {
3379         RenderBlock* container = *it;
3380         HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->get(container);
3381         ASSERT(descendantSet);
3382         if (!descendantSet)
3383             continue;
3384         ASSERT(descendantSet->contains(descendant));
3385         descendantSet->remove(descendant);
3386         if (descendantSet->isEmpty()) {
3387             gPercentHeightDescendantsMap->remove(container);
3388             delete descendantSet;
3389         }
3390     }
3391
3392     delete containerSet;
3393 }
3394
3395 HashSet<RenderBox*>* RenderBlock::percentHeightDescendants() const
3396 {
3397     return gPercentHeightDescendantsMap ? gPercentHeightDescendantsMap->get(this) : 0;
3398 }
3399
3400 // FIXME: The logicalLeftOffsetForLine/logicalRightOffsetForLine functions are very slow if there are many floats
3401 // present. We need to add a structure to floating objects to represent "lines" of floats.  Then instead of checking
3402 // each float individually, we'd just walk backwards through the "lines" and stop when we hit a line that is fully above
3403 // the vertical offset that we'd like to check.  Computing the "lines" would be rather complicated, but could replace the left
3404 // objects and right objects count hack that is currently used here.
3405 int RenderBlock::logicalLeftOffsetForLine(int logicalTop, int fixedOffset, bool applyTextIndent, int* heightRemaining) const
3406 {
3407     int left = fixedOffset;
3408     if (m_floatingObjects && m_floatingObjects->hasLeftObjects()) {
3409         if (heightRemaining)
3410             *heightRemaining = 1;
3411
3412         // We know the list is non-empty, since we have "left" objects to search for.
3413         // Therefore we can assume that begin != end, and that we can do at least one
3414         // decrement.
3415         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3416         FloatingObjectSetIterator begin = floatingObjectSet.begin();
3417         FloatingObjectSetIterator it = floatingObjectSet.end();
3418         do {
3419             --it;
3420             FloatingObject* r = *it;
3421             if (r->isPlaced() && logicalTopForFloat(r) <= logicalTop && logicalBottomForFloat(r) > logicalTop
3422                 && r->type() == FloatingObject::FloatLeft
3423                 && logicalRightForFloat(r) > left) {
3424                 left = max(left, logicalRightForFloat(r));
3425                 if (heightRemaining)
3426                     *heightRemaining = logicalBottomForFloat(r) - logicalTop;
3427             }
3428         } while (it != begin);
3429     }
3430
3431     if (applyTextIndent && style()->isLeftToRightDirection()) {
3432         int cw = 0;
3433         if (style()->textIndent().isPercent())
3434             cw = containingBlock()->availableLogicalWidth();
3435         left += style()->textIndent().calcMinValue(cw);
3436     }
3437
3438     return left;
3439 }
3440
3441 int RenderBlock::logicalRightOffsetForLine(int logicalTop, int fixedOffset, bool applyTextIndent, int* heightRemaining) const
3442 {
3443     int right = fixedOffset;
3444
3445     if (m_floatingObjects && m_floatingObjects->hasRightObjects()) {
3446         if (heightRemaining)
3447             *heightRemaining = 1;
3448             
3449         // We know the list is non-empty, since we have "right" objects to search for.
3450         // Therefore we can assume that begin != end, and that we can do at least one
3451         // decrement.
3452         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3453         FloatingObjectSetIterator begin = floatingObjectSet.begin();
3454         FloatingObjectSetIterator it = floatingObjectSet.end();
3455         do {
3456             --it;
3457             FloatingObject* r = *it;
3458             if (r->isPlaced() && logicalTopForFloat(r) <= logicalTop && logicalBottomForFloat(r) > logicalTop
3459                 && r->type() == FloatingObject::FloatRight
3460                 && logicalLeftForFloat(r) < right) {
3461                 right = min(right, logicalLeftForFloat(r));
3462                 if (heightRemaining)
3463                     *heightRemaining = logicalBottomForFloat(r) - logicalTop;
3464             }
3465         } while (it != begin);
3466     }
3467     
3468     if (applyTextIndent && !style()->isLeftToRightDirection()) {
3469         int cw = 0;
3470         if (style()->textIndent().isPercent())
3471             cw = containingBlock()->availableLogicalWidth();
3472         right -= style()->textIndent().calcMinValue(cw);
3473     }
3474     
3475     return right;
3476 }
3477
3478 int RenderBlock::availableLogicalWidthForLine(int position, bool firstLine) const
3479 {
3480     int result = logicalRightOffsetForLine(position, firstLine) - logicalLeftOffsetForLine(position, firstLine);
3481     return (result < 0) ? 0 : result;
3482 }
3483
3484 int RenderBlock::nextFloatLogicalBottomBelow(int logicalHeight) const
3485 {
3486     if (!m_floatingObjects)
3487         return 0;
3488
3489     int bottom = INT_MAX;
3490     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3491     FloatingObjectSetIterator end = floatingObjectSet.end();
3492     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
3493         FloatingObject* r = *it;
3494         int floatBottom = logicalBottomForFloat(r);
3495         if (floatBottom > logicalHeight)
3496             bottom = min(floatBottom, bottom);
3497     }
3498
3499     return bottom == INT_MAX ? 0 : bottom;
3500 }
3501
3502 int RenderBlock::lowestFloatLogicalBottom(FloatingObject::Type floatType) const
3503 {
3504     if (!m_floatingObjects)
3505         return 0;
3506     int lowestFloatBottom = 0;
3507     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3508     FloatingObjectSetIterator end = floatingObjectSet.end();
3509     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
3510         FloatingObject* r = *it;
3511         if (r->isPlaced() && r->type() & floatType)
3512             lowestFloatBottom = max(lowestFloatBottom, logicalBottomForFloat(r));
3513     }
3514     return lowestFloatBottom;
3515 }
3516
3517 void RenderBlock::markLinesDirtyInBlockRange(int logicalTop, int logicalBottom, RootInlineBox* highest)
3518 {
3519     if (logicalTop >= logicalBottom)
3520         return;
3521
3522     RootInlineBox* lowestDirtyLine = lastRootBox();
3523     RootInlineBox* afterLowest = lowestDirtyLine;
3524     while (lowestDirtyLine && lowestDirtyLine->blockLogicalHeight() >= logicalBottom && logicalBottom < numeric_limits<int>::max()) {
3525         afterLowest = lowestDirtyLine;
3526         lowestDirtyLine = lowestDirtyLine->prevRootBox();
3527     }
3528
3529     while (afterLowest && afterLowest != highest && (afterLowest->blockLogicalHeight() >= logicalTop || afterLowest->blockLogicalHeight() < 0)) {
3530         afterLowest->markDirty();
3531         afterLowest = afterLowest->prevRootBox();
3532     }
3533 }
3534
3535 void RenderBlock::clearFloats()
3536 {
3537     // Inline blocks are covered by the isReplaced() check in the avoidFloats method.
3538     if (avoidsFloats() || isRoot() || isRenderView() || isFloatingOrPositioned() || isTableCell()) {
3539         if (m_floatingObjects) {
3540             deleteAllValues(m_floatingObjects->set());
3541             m_floatingObjects->clear();
3542         }
3543         return;
3544     }
3545
3546     typedef HashMap<RenderObject*, FloatingObject*> RendererToFloatInfoMap;
3547     RendererToFloatInfoMap floatMap;
3548
3549     if (m_floatingObjects) {
3550         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3551         if (childrenInline()) {
3552             FloatingObjectSet::iterator end = floatingObjectSet.end();
3553             for (FloatingObjectSet::iterator it = floatingObjectSet.begin(); it != end; ++it) {
3554                 FloatingObject* f = *it;
3555                 floatMap.add(f->m_renderer, f);
3556             }
3557         } else
3558             deleteAllValues(floatingObjectSet);
3559         m_floatingObjects->clear();
3560     }
3561
3562     // We should not process floats if the parent node is not a RenderBlock. Otherwise, we will add 
3563     // floats in an invalid context. This will cause a crash arising from a bad cast on the parent.
3564     // See <rdar://problem/8049753>, where float property is applied on a text node in a SVG.
3565     if (!parent() || !parent()->isRenderBlock())
3566         return;
3567
3568     // Attempt to locate a previous sibling with overhanging floats.  We skip any elements that are
3569     // out of flow (like floating/positioned elements), and we also skip over any objects that may have shifted
3570     // to avoid floats.
3571     bool parentHasFloats = false;
3572     RenderBlock* parentBlock = toRenderBlock(parent());
3573     RenderObject* prev = previousSibling();
3574     while (prev && (prev->isFloatingOrPositioned() || !prev->isBox() || !prev->isRenderBlock() || toRenderBlock(prev)->avoidsFloats())) {
3575         if (prev->isFloating())
3576             parentHasFloats = true;
3577          prev = prev->previousSibling();
3578     }
3579
3580     // First add in floats from the parent.
3581     int logicalTopOffset = logicalTop();
3582     if (parentHasFloats)
3583         addIntrudingFloats(parentBlock, parentBlock->logicalLeftOffsetForContent(), logicalTopOffset);
3584     
3585     int logicalLeftOffset = 0;
3586     if (prev)
3587         logicalTopOffset -= toRenderBox(prev)->logicalTop();
3588     else {
3589         prev = parentBlock;
3590         logicalLeftOffset += parentBlock->logicalLeftOffsetForContent();
3591     }
3592
3593     // Add overhanging floats from the previous RenderBlock, but only if it has a float that intrudes into our space.
3594     if (!prev || !prev->isRenderBlock())
3595         return;
3596     
3597     RenderBlock* block = toRenderBlock(prev);
3598     if (block->m_floatingObjects && block->lowestFloatLogicalBottom() > logicalTopOffset)
3599         addIntrudingFloats(block, logicalLeftOffset, logicalTopOffset);
3600
3601     if (childrenInline()) {
3602         int changeLogicalTop = numeric_limits<int>::max();
3603         int changeLogicalBottom = numeric_limits<int>::min();
3604         if (m_floatingObjects) {
3605             FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3606             FloatingObjectSetIterator end = floatingObjectSet.end();
3607             for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
3608                 FloatingObject* f = *it;
3609                 FloatingObject* oldFloatingObject = floatMap.get(f->m_renderer);
3610                 int logicalBottom = logicalBottomForFloat(f);
3611                 if (oldFloatingObject) {
3612                     int oldLogicalBottom = logicalBottomForFloat(oldFloatingObject);
3613                     if (logicalWidthForFloat(f) != logicalWidthForFloat(oldFloatingObject) || logicalLeftForFloat(f) != logicalLeftForFloat(oldFloatingObject)) {
3614                         changeLogicalTop = 0;
3615                         changeLogicalBottom = max(changeLogicalBottom, max(logicalBottom, oldLogicalBottom));
3616                     } else if (logicalBottom != oldLogicalBottom) {
3617                         changeLogicalTop = min(changeLogicalTop, min(logicalBottom, oldLogicalBottom));
3618                         changeLogicalBottom = max(changeLogicalBottom, max(logicalBottom, oldLogicalBottom));
3619                     }
3620
3621                     floatMap.remove(f->m_renderer);
3622                     delete oldFloatingObject;
3623                 } else {
3624                     changeLogicalTop = 0;
3625                     changeLogicalBottom = max(changeLogicalBottom, logicalBottom);
3626                 }
3627             }
3628         }
3629
3630         RendererToFloatInfoMap::iterator end = floatMap.end();
3631         for (RendererToFloatInfoMap::iterator it = floatMap.begin(); it != end; ++it) {
3632             FloatingObject* floatingObject = (*it).second;
3633             if (!floatingObject->m_isDescendant) {
3634                 changeLogicalTop = 0;
3635                 changeLogicalBottom = max(changeLogicalBottom, logicalBottomForFloat(floatingObject));
3636             }
3637         }
3638         deleteAllValues(floatMap);
3639
3640         markLinesDirtyInBlockRange(changeLogicalTop, changeLogicalBottom);
3641     }
3642 }
3643
3644 int RenderBlock::addOverhangingFloats(RenderBlock* child, int logicalLeftOffset, int logicalTopOffset, bool makeChildPaintOtherFloats)
3645 {
3646     // Prevent floats from being added to the canvas by the root element, e.g., <html>.
3647     if (child->hasOverflowClip() || !child->containsFloats() || child->isRoot() || child->hasColumns() || child->isWritingModeRoot())
3648         return 0;
3649
3650     int childLogicalTop = child->logicalTop();
3651     int lowestFloatLogicalBottom = 0;
3652
3653     // Floats that will remain the child's responsibility to paint should factor into its
3654     // overflow.
3655     FloatingObjectSetIterator childEnd = child->m_floatingObjects->set().end();
3656     for (FloatingObjectSetIterator childIt = child->m_floatingObjects->set().begin(); childIt != childEnd; ++childIt) {
3657         FloatingObject* r = *childIt;
3658         int logicalBottomForFloat = min(this->logicalBottomForFloat(r), numeric_limits<int>::max() - childLogicalTop);
3659         int logicalBottom = childLogicalTop + logicalBottomForFloat;
3660         lowestFloatLogicalBottom = max(lowestFloatLogicalBottom, logicalBottom);
3661
3662         if (logicalBottom > logicalHeight()) {
3663             // If the object is not in the list, we add it now.
3664             if (!containsFloat(r->m_renderer)) {
3665                 int leftOffset = isHorizontalWritingMode() ? logicalLeftOffset : logicalTopOffset;
3666                 int topOffset = isHorizontalWritingMode() ? logicalTopOffset : logicalLeftOffset;
3667                 FloatingObject* floatingObj = new FloatingObject(r->type(), IntRect(r->x() - leftOffset, r->y() - topOffset, r->width(), r->height()));
3668                 floatingObj->m_renderer = r->m_renderer;
3669
3670                 // The nearest enclosing layer always paints the float (so that zindex and stacking
3671                 // behaves properly).  We always want to propagate the desire to paint the float as
3672                 // far out as we can, to the outermost block that overlaps the float, stopping only
3673                 // if we hit a self-painting layer boundary.
3674                 if (r->m_renderer->enclosingFloatPaintingLayer() == enclosingFloatPaintingLayer())
3675                     r->m_shouldPaint = false;
3676                 else
3677                     floatingObj->m_shouldPaint = false;
3678                 
3679                 floatingObj->m_isDescendant = true;
3680
3681                 // We create the floating object list lazily.
3682                 if (!m_floatingObjects)
3683                     m_floatingObjects = adoptPtr(new FloatingObjects);
3684
3685                 m_floatingObjects->increaseObjectsCount(floatingObj->type());
3686                 m_floatingObjects->set().add(floatingObj);
3687             }
3688         } else {
3689             if (makeChildPaintOtherFloats && !r->m_shouldPaint && !r->m_renderer->hasSelfPaintingLayer() &&
3690                 r->m_renderer->isDescendantOf(child) && r->m_renderer->enclosingFloatPaintingLayer() == child->enclosingFloatPaintingLayer()) {
3691                 // The float is not overhanging from this block, so if it is a descendant of the child, the child should
3692                 // paint it (the other case is that it is intruding into the child), unless it has its own layer or enclosing
3693                 // layer.
3694