https://bugs.webkit.org/show_bug.cgi?id=44788, implement HTML5-compliant doctype...
[WebKit-https.git] / 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 "Document.h"
28 #include "Element.h"
29 #include "FloatQuad.h"
30 #include "Frame.h"
31 #include "FrameView.h"
32 #include "GraphicsContext.h"
33 #include "HTMLFormElement.h"
34 #include "HTMLNames.h"
35 #include "HitTestResult.h"
36 #include "InlineTextBox.h"
37 #include "RenderFlexibleBox.h"
38 #include "RenderImage.h"
39 #include "RenderInline.h"
40 #include "RenderLayer.h"
41 #include "RenderMarquee.h"
42 #include "RenderReplica.h"
43 #include "RenderTableCell.h"
44 #include "RenderTextFragment.h"
45 #include "RenderTheme.h"
46 #include "RenderView.h"
47 #include "SelectionController.h"
48 #include "Settings.h"
49 #include "TransformState.h"
50 #include <wtf/StdLibExtras.h>
51
52 using namespace std;
53 using namespace WTF;
54 using namespace Unicode;
55
56 namespace WebCore {
57
58 // Number of pixels to allow as a fudge factor when clicking above or below a line.
59 // clicking up to verticalLineClickFudgeFactor pixels above a line will correspond to the closest point on the line.   
60 static const int verticalLineClickFudgeFactor = 3;
61
62 using namespace HTMLNames;
63
64 struct ColumnInfo : public Noncopyable {
65     ColumnInfo()
66         : m_desiredColumnWidth(0)
67         , m_desiredColumnCount(1)
68         { }
69     int m_desiredColumnWidth;
70     unsigned m_desiredColumnCount;
71     Vector<IntRect> m_columnRects;
72 };
73
74 typedef WTF::HashMap<const RenderBox*, ColumnInfo*> ColumnInfoMap;
75 static ColumnInfoMap* gColumnInfoMap = 0;
76
77 typedef WTF::HashMap<const RenderBlock*, HashSet<RenderBox*>*> PercentHeightDescendantsMap;
78 static PercentHeightDescendantsMap* gPercentHeightDescendantsMap = 0;
79
80 typedef WTF::HashMap<const RenderBox*, HashSet<RenderBlock*>*> PercentHeightContainerMap;
81 static PercentHeightContainerMap* gPercentHeightContainerMap = 0;
82     
83 typedef WTF::HashMap<RenderBlock*, ListHashSet<RenderInline*>*> ContinuationOutlineTableMap;
84
85 typedef WTF::HashSet<RenderBlock*> DelayedUpdateScrollInfoSet;
86 static int gDelayUpdateScrollInfo = 0;
87 static DelayedUpdateScrollInfoSet* gDelayedUpdateScrollInfoSet = 0;
88
89 // Our MarginInfo state used when laying out block children.
90 RenderBlock::MarginInfo::MarginInfo(RenderBlock* block, int top, int bottom)
91 {
92     // Whether or not we can collapse our own margins with our children.  We don't do this
93     // if we had any border/padding (obviously), if we're the root or HTML elements, or if
94     // we're positioned, floating, a table cell.
95     m_canCollapseWithChildren = !block->isRenderView() && !block->isRoot() && !block->isPositioned() &&
96         !block->isFloating() && !block->isTableCell() && !block->hasOverflowClip() && !block->isInlineBlockOrInlineTable();
97
98     m_canCollapseTopWithChildren = m_canCollapseWithChildren && (top == 0) && block->style()->marginTopCollapse() != MSEPARATE;
99
100     // If any height other than auto is specified in CSS, then we don't collapse our bottom
101     // margins with our children's margins.  To do otherwise would be to risk odd visual
102     // effects when the children overflow out of the parent block and yet still collapse
103     // with it.  We also don't collapse if we have any bottom border/padding.
104     m_canCollapseBottomWithChildren = m_canCollapseWithChildren && (bottom == 0) &&
105         (block->style()->height().isAuto() && block->style()->height().value() == 0) && block->style()->marginBottomCollapse() != MSEPARATE;
106     
107     m_quirkContainer = block->isTableCell() || block->isBody() || block->style()->marginTopCollapse() == MDISCARD || 
108         block->style()->marginBottomCollapse() == MDISCARD;
109
110     m_atTopOfBlock = true;
111     m_atBottomOfBlock = false;
112
113     m_posMargin = m_canCollapseTopWithChildren ? block->maxTopMargin(true) : 0;
114     m_negMargin = m_canCollapseTopWithChildren ? block->maxTopMargin(false) : 0;
115     
116     m_topQuirk = m_bottomQuirk = m_determinedTopQuirk = false;
117 }
118
119 // -------------------------------------------------------------------------------------------------------
120
121 RenderBlock::RenderBlock(Node* node)
122       : RenderBox(node)
123       , m_floatingObjects(0)
124       , m_positionedObjects(0)
125       , m_continuation(0)
126       , m_maxMargin(0)
127       , m_lineHeight(-1)
128 {
129     setChildrenInline(true);
130 }
131
132 RenderBlock::~RenderBlock()
133 {
134     delete m_floatingObjects;
135     delete m_positionedObjects;
136     delete m_maxMargin;
137     
138     if (hasColumns())
139         delete gColumnInfoMap->take(this);
140
141     if (gPercentHeightDescendantsMap) {
142         if (HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->take(this)) {
143             HashSet<RenderBox*>::iterator end = descendantSet->end();
144             for (HashSet<RenderBox*>::iterator descendant = descendantSet->begin(); descendant != end; ++descendant) {
145                 HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->get(*descendant);
146                 ASSERT(containerSet);
147                 if (!containerSet)
148                     continue;
149                 ASSERT(containerSet->contains(this));
150                 containerSet->remove(this);
151                 if (containerSet->isEmpty()) {
152                     gPercentHeightContainerMap->remove(*descendant);
153                     delete containerSet;
154                 }
155             }
156             delete descendantSet;
157         }
158     }
159 }
160
161 void RenderBlock::destroy()
162 {
163     // Make sure to destroy anonymous children first while they are still connected to the rest of the tree, so that they will
164     // properly dirty line boxes that they are removed from. Effects that do :before/:after only on hover could crash otherwise.
165     children()->destroyLeftoverChildren();
166
167     // Destroy our continuation before anything other than anonymous children.
168     // The reason we don't destroy it before anonymous children is that they may
169     // have continuations of their own that are anonymous children of our continuation.
170     if (m_continuation) {
171         m_continuation->destroy();
172         m_continuation = 0;
173     }
174     
175     if (!documentBeingDestroyed()) {
176         if (firstLineBox()) {
177             // We can't wait for RenderBox::destroy to clear the selection,
178             // because by then we will have nuked the line boxes.
179             // FIXME: The SelectionController should be responsible for this when it
180             // is notified of DOM mutations.
181             if (isSelectionBorder())
182                 view()->clearSelection();
183
184             // If we are an anonymous block, then our line boxes might have children
185             // that will outlast this block. In the non-anonymous block case those
186             // children will be destroyed by the time we return from this function.
187             if (isAnonymousBlock()) {
188                 for (InlineFlowBox* box = firstLineBox(); box; box = box->nextLineBox()) {
189                     while (InlineBox* childBox = box->firstChild())
190                         childBox->remove();
191                 }
192             }
193         } else if (isInline() && parent())
194             parent()->dirtyLinesFromChangedChild(this);
195     }
196
197     m_lineBoxes.deleteLineBoxes(renderArena());
198
199     RenderBox::destroy();
200 }
201
202 void RenderBlock::styleWillChange(StyleDifference diff, const RenderStyle* newStyle)
203 {
204     setReplaced(newStyle->isDisplayReplacedType());
205     
206     if (style() && parent() && diff == StyleDifferenceLayout && style()->position() != newStyle->position()) {
207         if (newStyle->position() == StaticPosition)
208             // Clear our positioned objects list. Our absolutely positioned descendants will be
209             // inserted into our containing block's positioned objects list during layout.
210             removePositionedObjects(0);
211         else if (style()->position() == StaticPosition) {
212             // Remove our absolutely positioned descendants from their current containing block.
213             // They will be inserted into our positioned objects list during layout.
214             RenderObject* cb = parent();
215             while (cb && (cb->style()->position() == StaticPosition || (cb->isInline() && !cb->isReplaced())) && !cb->isRenderView()) {
216                 if (cb->style()->position() == RelativePosition && cb->isInline() && !cb->isReplaced()) {
217                     cb = cb->containingBlock();
218                     break;
219                 }
220                 cb = cb->parent();
221             }
222             
223             if (cb->isRenderBlock())
224                 toRenderBlock(cb)->removePositionedObjects(this);
225         }
226     }
227
228     RenderBox::styleWillChange(diff, newStyle);
229 }
230
231 void RenderBlock::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
232 {
233     RenderBox::styleDidChange(diff, oldStyle);
234
235     if (!isAnonymousBlock()) {
236         // Ensure that all of our continuation blocks pick up the new style.
237         for (RenderBlock* currCont = blockElementContinuation(); currCont; currCont = currCont->blockElementContinuation()) {
238             RenderBoxModelObject* nextCont = currCont->continuation();
239             currCont->setContinuation(0);
240             currCont->setStyle(style());
241             currCont->setContinuation(nextCont);
242         }
243     }
244
245     // FIXME: We could save this call when the change only affected non-inherited properties
246     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
247         if (child->isAnonymousBlock()) {
248             RefPtr<RenderStyle> newStyle = RenderStyle::create();
249             newStyle->inheritFrom(style());
250             if (style()->specifiesColumns()) {
251                 if (child->style()->specifiesColumns())
252                     newStyle->inheritColumnPropertiesFrom(style());
253                 if (child->style()->columnSpan())
254                     newStyle->setColumnSpan(true);
255             }
256             newStyle->setDisplay(BLOCK);
257             child->setStyle(newStyle.release());
258         }
259     }
260
261     m_lineHeight = -1;
262
263     // Update pseudos for :before and :after now.
264     if (!isAnonymous() && document()->usesBeforeAfterRules() && canHaveChildren()) {
265         updateBeforeAfterContent(BEFORE);
266         updateBeforeAfterContent(AFTER);
267     }
268     updateFirstLetter();
269 }
270
271 void RenderBlock::updateBeforeAfterContent(PseudoId pseudoId)
272 {
273     // If this is an anonymous wrapper, then the parent applies its own pseudo-element style to it.
274     if (parent() && parent()->createsAnonymousWrapper())
275         return;
276     return children()->updateBeforeAfterContent(this, pseudoId);
277 }
278
279 RenderBlock* RenderBlock::continuationBefore(RenderObject* beforeChild)
280 {
281     if (beforeChild && beforeChild->parent() == this)
282         return this;
283
284     RenderBlock* curr = toRenderBlock(continuation());
285     RenderBlock* nextToLast = this;
286     RenderBlock* last = this;
287     while (curr) {
288         if (beforeChild && beforeChild->parent() == curr) {
289             if (curr->firstChild() == beforeChild)
290                 return last;
291             return curr;
292         }
293
294         nextToLast = last;
295         last = curr;
296         curr = toRenderBlock(curr->continuation());
297     }
298
299     if (!beforeChild && !last->firstChild())
300         return nextToLast;
301     return last;
302 }
303
304 void RenderBlock::addChildToContinuation(RenderObject* newChild, RenderObject* beforeChild)
305 {
306     RenderBlock* flow = continuationBefore(beforeChild);
307     ASSERT(!beforeChild || beforeChild->parent()->isAnonymousColumnSpanBlock() || beforeChild->parent()->isRenderBlock());
308     RenderBoxModelObject* beforeChildParent = 0;
309     if (beforeChild)
310         beforeChildParent = toRenderBoxModelObject(beforeChild->parent());
311     else {
312         RenderBoxModelObject* cont = flow->continuation();
313         if (cont)
314             beforeChildParent = cont;
315         else
316             beforeChildParent = flow;
317     }
318
319     if (newChild->isFloatingOrPositioned())
320         return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
321
322     // A continuation always consists of two potential candidates: a block or an anonymous
323     // column span box holding column span children.
324     bool childIsNormal = newChild->isInline() || !newChild->style()->columnSpan();
325     bool bcpIsNormal = beforeChildParent->isInline() || !beforeChildParent->style()->columnSpan();
326     bool flowIsNormal = flow->isInline() || !flow->style()->columnSpan();
327
328     if (flow == beforeChildParent)
329         return flow->addChildIgnoringContinuation(newChild, beforeChild);
330     
331     // The goal here is to match up if we can, so that we can coalesce and create the
332     // minimal # of continuations needed for the inline.
333     if (childIsNormal == bcpIsNormal)
334         return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
335     if (flowIsNormal == childIsNormal)
336         return flow->addChildIgnoringContinuation(newChild, 0); // Just treat like an append.
337     return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
338 }
339
340
341 void RenderBlock::addChildToAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)
342 {
343     ASSERT(!continuation()); // We don't yet support column spans that aren't immediate children of the multi-column block.
344         
345     // The goal is to locate a suitable box in which to place our child.
346     RenderBlock* beforeChildParent = toRenderBlock(beforeChild ? beforeChild->parent() : lastChild());
347     
348     // If the new child is floating or positioned it can just go in that block.
349     if (newChild->isFloatingOrPositioned())
350         return beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
351
352     // See if the child can be placed in the box.
353     bool newChildHasColumnSpan = newChild->style()->columnSpan() && !newChild->isInline();
354     bool beforeChildParentHoldsColumnSpans = beforeChildParent->isAnonymousColumnSpanBlock();
355
356     if (newChildHasColumnSpan == beforeChildParentHoldsColumnSpans)
357         return beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
358
359     if (!beforeChild) {
360         // Create a new block of the correct type.
361         RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();
362         children()->appendChildNode(this, newBox);
363         newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);
364         return;
365     }
366
367     RenderObject* immediateChild = beforeChild;
368     bool isPreviousBlockViable = true;
369     while (immediateChild->parent() != this) {
370         if (isPreviousBlockViable)
371             isPreviousBlockViable = !immediateChild->previousSibling();
372         immediateChild = immediateChild->parent();
373     }
374     if (isPreviousBlockViable && immediateChild->previousSibling())
375         return toRenderBlock(immediateChild->previousSibling())->addChildIgnoringAnonymousColumnBlocks(newChild, 0); // Treat like an append.
376         
377     // Split our anonymous blocks.
378     RenderObject* newBeforeChild = splitAnonymousBlocksAroundChild(beforeChild);
379     
380     // Create a new anonymous box of the appropriate type.
381     RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();
382     children()->insertChildNode(this, newBox, newBeforeChild);
383     newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);
384     return;
385 }
386
387 RenderBlock* RenderBlock::containingColumnsBlock(bool allowAnonymousColumnBlock)
388 {
389     for (RenderObject* curr = this; curr; curr = curr->parent()) {
390         if (!curr->isRenderBlock() || curr->isFloatingOrPositioned() || curr->isTableCell() || curr->isRoot() || curr->isRenderView() || curr->hasOverflowClip()
391             || curr->isInlineBlockOrInlineTable())
392             return 0;
393         
394         RenderBlock* currBlock = toRenderBlock(curr);
395         if (currBlock->style()->specifiesColumns() && (allowAnonymousColumnBlock || !currBlock->isAnonymousColumnsBlock()))
396             return currBlock;
397             
398         if (currBlock->isAnonymousColumnSpanBlock())
399             return 0;
400     }
401     return 0;
402 }
403
404 RenderBlock* RenderBlock::clone() const
405 {
406     RenderBlock* o = new (renderArena()) RenderBlock(node());
407     o->setStyle(style());
408     o->setChildrenInline(childrenInline());
409     return o;
410 }
411
412 void RenderBlock::splitBlocks(RenderBlock* fromBlock, RenderBlock* toBlock,
413                               RenderBlock* middleBlock,
414                               RenderObject* beforeChild, RenderBoxModelObject* oldCont)
415 {
416     // Create a clone of this inline.
417     RenderBlock* cloneBlock = clone();
418     cloneBlock->setContinuation(oldCont);
419
420     // Now take all of the children from beforeChild to the end and remove
421     // them from |this| and place them in the clone.
422     if (!beforeChild && isAfterContent(lastChild()))
423         beforeChild = lastChild();
424     moveChildrenTo(cloneBlock, beforeChild, 0);
425     
426     // Hook |clone| up as the continuation of the middle block.
427     middleBlock->setContinuation(cloneBlock);
428
429     // We have been reparented and are now under the fromBlock.  We need
430     // to walk up our block parent chain until we hit the containing anonymous columns block.
431     // Once we hit the anonymous columns block we're done.
432     RenderBoxModelObject* curr = toRenderBoxModelObject(parent());
433     RenderBoxModelObject* currChild = this;
434     
435     while (curr && curr != fromBlock) {
436         ASSERT(curr->isRenderBlock() && !curr->isAnonymousBlock());
437         
438         RenderBlock* blockCurr = toRenderBlock(curr);
439         
440         // Create a new clone.
441         RenderBlock* cloneChild = cloneBlock;
442         cloneBlock = blockCurr->clone();
443
444         // Insert our child clone as the first child.
445         cloneBlock->children()->appendChildNode(cloneBlock, cloneChild);
446
447         // Hook the clone up as a continuation of |curr|.  Note we do encounter
448         // anonymous blocks possibly as we walk up the block chain.  When we split an
449         // anonymous block, there's no need to do any continuation hookup, since we haven't
450         // actually split a real element.
451         if (!blockCurr->isAnonymousBlock()) {
452             oldCont = blockCurr->continuation();
453             blockCurr->setContinuation(cloneBlock);
454             cloneBlock->setContinuation(oldCont);
455         }
456
457         // Someone may have indirectly caused a <q> to split.  When this happens, the :after content
458         // has to move into the inline continuation.  Call updateBeforeAfterContent to ensure that the inline's :after
459         // content gets properly destroyed.
460         if (document()->usesBeforeAfterRules())
461             blockCurr->children()->updateBeforeAfterContent(blockCurr, AFTER);
462
463         // Now we need to take all of the children starting from the first child
464         // *after* currChild and append them all to the clone.
465         RenderObject* afterContent = isAfterContent(cloneBlock->lastChild()) ? cloneBlock->lastChild() : 0;
466         blockCurr->moveChildrenTo(cloneBlock, currChild->nextSibling(), 0, afterContent);
467
468         // Keep walking up the chain.
469         currChild = curr;
470         curr = toRenderBoxModelObject(curr->parent());
471     }
472
473     // Now we are at the columns block level. We need to put the clone into the toBlock.
474     toBlock->children()->appendChildNode(toBlock, cloneBlock);
475
476     // Now take all the children after currChild and remove them from the fromBlock
477     // and put them in the toBlock.
478     fromBlock->moveChildrenTo(toBlock, currChild->nextSibling(), 0);
479 }
480
481 void RenderBlock::splitFlow(RenderObject* beforeChild, RenderBlock* newBlockBox,
482                             RenderObject* newChild, RenderBoxModelObject* oldCont)
483 {
484     RenderBlock* pre = 0;
485     RenderBlock* block = containingColumnsBlock();
486     
487     // Delete our line boxes before we do the inline split into continuations.
488     block->deleteLineBoxTree();
489     
490     bool madeNewBeforeBlock = false;
491     if (block->isAnonymousColumnsBlock()) {
492         // We can reuse this block and make it the preBlock of the next continuation.
493         pre = block;
494         pre->removePositionedObjects(0);
495         block = toRenderBlock(block->parent());
496     } else {
497         // No anonymous block available for use.  Make one.
498         pre = block->createAnonymousColumnsBlock();
499         pre->setChildrenInline(false);
500         madeNewBeforeBlock = true;
501     }
502
503     RenderBlock* post = block->createAnonymousColumnsBlock();
504     post->setChildrenInline(false);
505
506     RenderObject* boxFirst = madeNewBeforeBlock ? block->firstChild() : pre->nextSibling();
507     if (madeNewBeforeBlock)
508         block->children()->insertChildNode(block, pre, boxFirst);
509     block->children()->insertChildNode(block, newBlockBox, boxFirst);
510     block->children()->insertChildNode(block, post, boxFirst);
511     block->setChildrenInline(false);
512     
513     if (madeNewBeforeBlock)
514         block->moveChildrenTo(pre, boxFirst, 0);
515
516     splitBlocks(pre, post, newBlockBox, beforeChild, oldCont);
517
518     // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
519     // time in makeChildrenNonInline by just setting this explicitly up front.
520     newBlockBox->setChildrenInline(false);
521
522     // We delayed adding the newChild until now so that the |newBlockBox| would be fully
523     // connected, thus allowing newChild access to a renderArena should it need
524     // to wrap itself in additional boxes (e.g., table construction).
525     newBlockBox->addChild(newChild);
526
527     // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
528     // get deleted properly.  Because objects moves from the pre block into the post block, we want to
529     // make new line boxes instead of leaving the old line boxes around.
530     pre->setNeedsLayoutAndPrefWidthsRecalc();
531     block->setNeedsLayoutAndPrefWidthsRecalc();
532     post->setNeedsLayoutAndPrefWidthsRecalc();
533 }
534
535 RenderObject* RenderBlock::splitAnonymousBlocksAroundChild(RenderObject* beforeChild)
536 {
537     while (beforeChild->parent() != this) {
538         RenderBlock* blockToSplit = toRenderBlock(beforeChild->parent());
539         if (blockToSplit->firstChild() != beforeChild) {
540             // We have to split the parentBlock into two blocks.
541             RenderBlock* post = createAnonymousBlockWithSameTypeAs(blockToSplit);
542             post->setChildrenInline(blockToSplit->childrenInline());
543             RenderBlock* parentBlock = toRenderBlock(blockToSplit->parent());
544             parentBlock->children()->insertChildNode(parentBlock, post, blockToSplit->nextSibling());
545             blockToSplit->moveChildrenTo(post, beforeChild, 0, blockToSplit->hasLayer());
546             post->setNeedsLayoutAndPrefWidthsRecalc();
547             blockToSplit->setNeedsLayoutAndPrefWidthsRecalc();
548             beforeChild = post;
549         } else
550             beforeChild = blockToSplit;
551     }
552     return beforeChild;
553 }
554
555 void RenderBlock::makeChildrenAnonymousColumnBlocks(RenderObject* beforeChild, RenderBlock* newBlockBox, RenderObject* newChild)
556 {
557     RenderBlock* pre = 0;
558     RenderBlock* post = 0;
559     RenderBlock* block = this; // Eventually block will not just be |this|, but will also be a block nested inside |this|.  Assign to a variable
560                                // so that we don't have to patch all of the rest of the code later on.
561     
562     // Delete the block's line boxes before we do the split.
563     block->deleteLineBoxTree();
564
565     if (beforeChild && beforeChild->parent() != this)
566         beforeChild = splitAnonymousBlocksAroundChild(beforeChild);
567
568     if (beforeChild != firstChild()) {
569         pre = block->createAnonymousColumnsBlock();
570         pre->setChildrenInline(block->childrenInline());
571     }
572
573     if (beforeChild) {
574         post = block->createAnonymousColumnsBlock();
575         post->setChildrenInline(block->childrenInline());
576     }
577
578     RenderObject* boxFirst = block->firstChild();
579     if (pre)
580         block->children()->insertChildNode(block, pre, boxFirst);
581     block->children()->insertChildNode(block, newBlockBox, boxFirst);
582     if (post)
583         block->children()->insertChildNode(block, post, boxFirst);
584     block->setChildrenInline(false);
585     
586     // 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).
587     block->moveChildrenTo(pre, boxFirst, beforeChild, true);
588     block->moveChildrenTo(post, beforeChild, 0, true);
589
590     // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
591     // time in makeChildrenNonInline by just setting this explicitly up front.
592     newBlockBox->setChildrenInline(false);
593
594     // We delayed adding the newChild until now so that the |newBlockBox| would be fully
595     // connected, thus allowing newChild access to a renderArena should it need
596     // to wrap itself in additional boxes (e.g., table construction).
597     newBlockBox->addChild(newChild);
598
599     // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
600     // get deleted properly.  Because objects moved from the pre block into the post block, we want to
601     // make new line boxes instead of leaving the old line boxes around.
602     if (pre)
603         pre->setNeedsLayoutAndPrefWidthsRecalc();
604     block->setNeedsLayoutAndPrefWidthsRecalc();
605     if (post)
606         post->setNeedsLayoutAndPrefWidthsRecalc();
607 }
608
609 RenderBlock* RenderBlock::columnsBlockForSpanningElement(RenderObject* newChild)
610 {
611     // FIXME: This function is the gateway for the addition of column-span support.  It will
612     // be added to in three stages:
613     // (1) Immediate children of a multi-column block can span.
614     // (2) Nested block-level children with only block-level ancestors between them and the multi-column block can span.
615     // (3) Nested children with block or inline ancestors between them and the multi-column block can span (this is when we
616     // cross the streams and have to cope with both types of continuations mixed together).
617     // This function currently supports (1) and (2).
618     RenderBlock* columnsBlockAncestor = 0;
619     if (!newChild->isText() && newChild->style()->columnSpan() && !newChild->isFloatingOrPositioned()
620         && !newChild->isInline() && !isAnonymousColumnSpanBlock()) {
621         if (style()->specifiesColumns())
622             columnsBlockAncestor = this;
623         else
624             columnsBlockAncestor = toRenderBlock(parent())->containingColumnsBlock(false);
625     }
626     return columnsBlockAncestor;
627 }
628
629 void RenderBlock::addChildIgnoringAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)
630 {
631     // Make sure we don't append things after :after-generated content if we have it.
632     if (!beforeChild) {
633         RenderObject* lastRenderer = lastChild();
634         if (isAfterContent(lastRenderer))
635             beforeChild = lastRenderer;
636         else if (lastRenderer && lastRenderer->isAnonymousBlock() && isAfterContent(lastRenderer->lastChild()))
637             beforeChild = lastRenderer->lastChild();
638     }
639
640     // Check for a spanning element in columns.
641     RenderBlock* columnsBlockAncestor = columnsBlockForSpanningElement(newChild);
642     if (columnsBlockAncestor) {
643         // We are placing a column-span element inside a block. 
644         RenderBlock* newBox = createAnonymousColumnSpanBlock();
645         
646         if (columnsBlockAncestor != this) {
647             // We are nested inside a multi-column element and are being split by the span.  We have to break up
648             // our block into continuations.
649             RenderBoxModelObject* oldContinuation = continuation();
650             setContinuation(newBox);
651
652             // Someone may have put a <p> inside a <q>, causing a split.  When this happens, the :after content
653             // has to move into the inline continuation.  Call updateBeforeAfterContent to ensure that our :after
654             // content gets properly destroyed.
655             bool isLastChild = (beforeChild == lastChild());
656             if (document()->usesBeforeAfterRules())
657                 children()->updateBeforeAfterContent(this, AFTER);
658             if (isLastChild && beforeChild != lastChild())
659                 beforeChild = 0; // We destroyed the last child, so now we need to update our insertion
660                                  // point to be 0.  It's just a straight append now.
661
662             splitFlow(beforeChild, newBox, newChild, oldContinuation);
663             return;
664         }
665
666         // We have to perform a split of this block's children.  This involves creating an anonymous block box to hold
667         // the column-spanning |newChild|.  We take all of the children from before |newChild| and put them into
668         // one anonymous columns block, and all of the children after |newChild| go into another anonymous block.
669         makeChildrenAnonymousColumnBlocks(beforeChild, newBox, newChild);
670         return;
671     }
672
673     bool madeBoxesNonInline = false;
674
675     // If the requested beforeChild is not one of our children, then this is because
676     // there is an anonymous container within this object that contains the beforeChild.
677     if (beforeChild && beforeChild->parent() != this) {
678         RenderObject* anonymousChild = beforeChild->parent();
679         ASSERT(anonymousChild);
680
681         while (anonymousChild->parent() != this)
682             anonymousChild = anonymousChild->parent();
683
684         ASSERT(anonymousChild->isAnonymous());
685
686         if (anonymousChild->isAnonymousBlock()) {
687             // Insert the child into the anonymous block box instead of here.
688             if (newChild->isInline() || beforeChild->parent()->firstChild() != beforeChild)
689                 beforeChild->parent()->addChild(newChild, beforeChild);
690             else
691                 addChild(newChild, beforeChild->parent());
692             return;
693         }
694
695         ASSERT(anonymousChild->isTable());
696         if ((newChild->isTableCol() && newChild->style()->display() == TABLE_COLUMN_GROUP)
697                 || (newChild->isRenderBlock() && newChild->style()->display() == TABLE_CAPTION)
698                 || newChild->isTableSection()
699                 || newChild->isTableRow()
700                 || newChild->isTableCell()) {
701             // Insert into the anonymous table.
702             anonymousChild->addChild(newChild, beforeChild);
703             return;
704         }
705
706         // Go on to insert before the anonymous table.
707         beforeChild = anonymousChild;
708     }
709
710     // A block has to either have all of its children inline, or all of its children as blocks.
711     // So, if our children are currently inline and a block child has to be inserted, we move all our
712     // inline children into anonymous block boxes.
713     if (childrenInline() && !newChild->isInline() && !newChild->isFloatingOrPositioned()) {
714         // This is a block with inline content. Wrap the inline content in anonymous blocks.
715         makeChildrenNonInline(beforeChild);
716         madeBoxesNonInline = true;
717
718         if (beforeChild && beforeChild->parent() != this) {
719             beforeChild = beforeChild->parent();
720             ASSERT(beforeChild->isAnonymousBlock());
721             ASSERT(beforeChild->parent() == this);
722         }
723     } else if (!childrenInline() && (newChild->isFloatingOrPositioned() || newChild->isInline())) {
724         // If we're inserting an inline child but all of our children are blocks, then we have to make sure
725         // it is put into an anomyous block box. We try to use an existing anonymous box if possible, otherwise
726         // a new one is created and inserted into our list of children in the appropriate position.
727         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : lastChild();
728
729         if (afterChild && afterChild->isAnonymousBlock()) {
730             afterChild->addChild(newChild);
731             return;
732         }
733
734         if (newChild->isInline()) {
735             // No suitable existing anonymous box - create a new one.
736             RenderBlock* newBox = createAnonymousBlock();
737             RenderBox::addChild(newBox, beforeChild);
738             newBox->addChild(newChild);
739             return;
740         }
741     }
742
743     RenderBox::addChild(newChild, beforeChild);
744
745     if (madeBoxesNonInline && parent() && isAnonymousBlock() && parent()->isRenderBlock())
746         toRenderBlock(parent())->removeLeftoverAnonymousBlock(this);
747     // this object may be dead here
748 }
749
750 void RenderBlock::addChild(RenderObject* newChild, RenderObject* beforeChild)
751 {
752     if (continuation() && !isAnonymousBlock())
753         return addChildToContinuation(newChild, beforeChild);
754     return addChildIgnoringContinuation(newChild, beforeChild);
755 }
756
757 void RenderBlock::addChildIgnoringContinuation(RenderObject* newChild, RenderObject* beforeChild)
758 {
759     if (!isAnonymousBlock() && firstChild() && (firstChild()->isAnonymousColumnsBlock() || firstChild()->isAnonymousColumnSpanBlock()))
760         return addChildToAnonymousColumnBlocks(newChild, beforeChild);
761     return addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
762 }
763
764 static void getInlineRun(RenderObject* start, RenderObject* boundary,
765                          RenderObject*& inlineRunStart,
766                          RenderObject*& inlineRunEnd)
767 {
768     // Beginning at |start| we find the largest contiguous run of inlines that
769     // we can.  We denote the run with start and end points, |inlineRunStart|
770     // and |inlineRunEnd|.  Note that these two values may be the same if
771     // we encounter only one inline.
772     //
773     // We skip any non-inlines we encounter as long as we haven't found any
774     // inlines yet.
775     //
776     // |boundary| indicates a non-inclusive boundary point.  Regardless of whether |boundary|
777     // is inline or not, we will not include it in a run with inlines before it.  It's as though we encountered
778     // a non-inline.
779     
780     // Start by skipping as many non-inlines as we can.
781     RenderObject * curr = start;
782     bool sawInline;
783     do {
784         while (curr && !(curr->isInline() || curr->isFloatingOrPositioned()))
785             curr = curr->nextSibling();
786         
787         inlineRunStart = inlineRunEnd = curr;
788         
789         if (!curr)
790             return; // No more inline children to be found.
791         
792         sawInline = curr->isInline();
793         
794         curr = curr->nextSibling();
795         while (curr && (curr->isInline() || curr->isFloatingOrPositioned()) && (curr != boundary)) {
796             inlineRunEnd = curr;
797             if (curr->isInline())
798                 sawInline = true;
799             curr = curr->nextSibling();
800         }
801     } while (!sawInline);
802 }
803
804 void RenderBlock::deleteLineBoxTree()
805 {
806     m_lineBoxes.deleteLineBoxTree(renderArena());
807 }
808
809 RootInlineBox* RenderBlock::createRootInlineBox() 
810 {
811     return new (renderArena()) RootInlineBox(this);
812 }
813
814 RootInlineBox* RenderBlock::createAndAppendRootInlineBox()
815 {
816     RootInlineBox* rootBox = createRootInlineBox();
817     m_lineBoxes.appendLineBox(rootBox);
818     return rootBox;
819 }
820
821 void RenderBlock::moveChildTo(RenderBlock* to, RenderObject* child, RenderObject* beforeChild, bool fullRemoveInsert)
822 {
823     ASSERT(this == child->parent());
824     ASSERT(!beforeChild || to == beforeChild->parent());
825     to->children()->insertChildNode(to, children()->removeChildNode(this, child, fullRemoveInsert), beforeChild, fullRemoveInsert);
826 }
827
828 void RenderBlock::moveChildrenTo(RenderBlock* to, RenderObject* startChild, RenderObject* endChild, RenderObject* beforeChild, bool fullRemoveInsert)
829 {
830     ASSERT(!beforeChild || to == beforeChild->parent());
831     RenderObject* nextChild = startChild;
832     while (nextChild && nextChild != endChild) {
833         RenderObject* child = nextChild;
834         nextChild = child->nextSibling();
835         to->children()->insertChildNode(to, children()->removeChildNode(this, child, fullRemoveInsert), beforeChild, fullRemoveInsert);
836         if (child == endChild)
837             return;
838     }
839 }
840
841 void RenderBlock::makeChildrenNonInline(RenderObject *insertionPoint)
842 {    
843     // makeChildrenNonInline takes a block whose children are *all* inline and it
844     // makes sure that inline children are coalesced under anonymous
845     // blocks.  If |insertionPoint| is defined, then it represents the insertion point for
846     // the new block child that is causing us to have to wrap all the inlines.  This
847     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
848     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
849     // splitting them.
850     ASSERT(isInlineBlockOrInlineTable() || !isInline());
851     ASSERT(!insertionPoint || insertionPoint->parent() == this);
852
853     setChildrenInline(false);
854
855     RenderObject *child = firstChild();
856     if (!child)
857         return;
858
859     deleteLineBoxTree();
860
861     while (child) {
862         RenderObject *inlineRunStart, *inlineRunEnd;
863         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
864
865         if (!inlineRunStart)
866             break;
867
868         child = inlineRunEnd->nextSibling();
869
870         RenderBlock* block = createAnonymousBlock();
871         children()->insertChildNode(this, block, inlineRunStart);
872         moveChildrenTo(block, inlineRunStart, child);
873     }
874
875 #ifndef NDEBUG
876     for (RenderObject *c = firstChild(); c; c = c->nextSibling())
877         ASSERT(!c->isInline());
878 #endif
879
880     repaint();
881 }
882
883 void RenderBlock::removeLeftoverAnonymousBlock(RenderBlock* child)
884 {
885     ASSERT(child->isAnonymousBlock());
886     ASSERT(!child->childrenInline());
887     
888     if (child->continuation() || (child->firstChild() && (child->isAnonymousColumnSpanBlock() || child->isAnonymousColumnsBlock())))
889         return;
890     
891     RenderObject* firstAnChild = child->m_children.firstChild();
892     RenderObject* lastAnChild = child->m_children.lastChild();
893     if (firstAnChild) {
894         RenderObject* o = firstAnChild;
895         while (o) {
896             o->setParent(this);
897             o = o->nextSibling();
898         }
899         firstAnChild->setPreviousSibling(child->previousSibling());
900         lastAnChild->setNextSibling(child->nextSibling());
901         if (child->previousSibling())
902             child->previousSibling()->setNextSibling(firstAnChild);
903         if (child->nextSibling())
904             child->nextSibling()->setPreviousSibling(lastAnChild);
905             
906         if (child == m_children.firstChild())
907             m_children.setFirstChild(firstAnChild);
908         if (child == m_children.lastChild())
909             m_children.setLastChild(lastAnChild);
910     } else {
911         if (child == m_children.firstChild())
912             m_children.setFirstChild(child->nextSibling());
913         if (child == m_children.lastChild())
914             m_children.setLastChild(child->previousSibling());
915
916         if (child->previousSibling())
917             child->previousSibling()->setNextSibling(child->nextSibling());
918         if (child->nextSibling())
919             child->nextSibling()->setPreviousSibling(child->previousSibling());
920     }
921     child->setParent(0);
922     child->setPreviousSibling(0);
923     child->setNextSibling(0);
924     
925     child->children()->setFirstChild(0);
926     child->m_next = 0;
927
928     child->destroy();
929 }
930
931 static bool canMergeContiguousAnonymousBlocks(RenderObject* oldChild, RenderObject* prev, RenderObject* next)
932 {
933     if (oldChild->documentBeingDestroyed() || oldChild->isInline() || oldChild->virtualContinuation())
934         return false;
935
936     if ((prev && (!prev->isAnonymousBlock() || toRenderBlock(prev)->continuation()))
937         || (next && (!next->isAnonymousBlock() || toRenderBlock(next)->continuation())))
938         return false;
939
940     // FIXME: This check isn't required when inline run-ins can't be split into continuations.
941     if (prev && prev->firstChild() && prev->firstChild()->isInline() && prev->firstChild()->isRunIn())
942         return false;
943
944 #if ENABLE(RUBY)
945     if ((prev && (prev->isRubyRun() || prev->isRubyBase()))
946         || (next && (next->isRubyRun() || next->isRubyBase())))
947         return false;
948 #endif
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() == prev->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::create();
981             newStyle->inheritFrom(style());
982             children()->removeChildNode(this, inlineChildrenBlock, inlineChildrenBlock->hasLayer());
983             inlineChildrenBlock->setStyle(newStyle);
984             
985             // Now just put the inlineChildrenBlock inside the blockChildrenBlock.
986             blockChildrenBlock->children()->insertChildNode(blockChildrenBlock, inlineChildrenBlock, prev == inlineChildrenBlock ? blockChildrenBlock->firstChild() : 0,
987                                                             inlineChildrenBlock->hasLayer() || blockChildrenBlock->hasLayer());
988             next->setNeedsLayoutAndPrefWidthsRecalc();
989         } else {
990             // Take all the children out of the |next| block and put them in
991             // the |prev| block.
992             nextBlock->moveAllChildrenTo(prevBlock, nextBlock->hasLayer() || prevBlock->hasLayer());
993        
994             // Delete the now-empty block's lines and nuke it.
995             nextBlock->deleteLineBoxTree();
996             nextBlock->destroy();
997         }
998     }
999
1000     RenderBox::removeChild(oldChild);
1001
1002     RenderObject* child = prev ? prev : next;
1003     if (canMergeAnonymousBlocks && child && !child->previousSibling() && !child->nextSibling() && !isFlexibleBox()) {
1004         // The removal has knocked us down to containing only a single anonymous
1005         // box.  We can go ahead and pull the content right back up into our
1006         // box.
1007         setNeedsLayoutAndPrefWidthsRecalc();
1008         setChildrenInline(child->childrenInline());
1009         RenderBlock* anonBlock = toRenderBlock(children()->removeChildNode(this, child, child->hasLayer()));
1010         anonBlock->moveAllChildrenTo(this, child->hasLayer());
1011         // Delete the now-empty block's lines and nuke it.
1012         anonBlock->deleteLineBoxTree();
1013         anonBlock->destroy();
1014     }
1015
1016     if (!firstChild() && !documentBeingDestroyed()) {
1017         // If this was our last child be sure to clear out our line boxes.
1018         if (childrenInline())
1019             lineBoxes()->deleteLineBoxes(renderArena());
1020         // If we're now an empty anonymous columns or column span block, then go ahead and delete ourselves.
1021         else if ((isAnonymousColumnsBlock() || isAnonymousColumnSpanBlock()) && parent() && parent()->isRenderBlock() && !continuation())
1022             destroy();
1023     }
1024 }
1025
1026 bool RenderBlock::isSelfCollapsingBlock() const
1027 {
1028     // We are not self-collapsing if we
1029     // (a) have a non-zero height according to layout (an optimization to avoid wasting time)
1030     // (b) are a table,
1031     // (c) have border/padding,
1032     // (d) have a min-height
1033     // (e) have specified that one of our margins can't collapse using a CSS extension
1034     if (height() > 0
1035         || isTable() || borderAndPaddingHeight()
1036         || style()->minHeight().isPositive()
1037         || style()->marginTopCollapse() == MSEPARATE || style()->marginBottomCollapse() == MSEPARATE)
1038         return false;
1039
1040     bool hasAutoHeight = style()->height().isAuto();
1041     if (style()->height().isPercent() && !document()->inQuirksMode()) {
1042         hasAutoHeight = true;
1043         for (RenderBlock* cb = containingBlock(); !cb->isRenderView(); cb = cb->containingBlock()) {
1044             if (cb->style()->height().isFixed() || cb->isTableCell())
1045                 hasAutoHeight = false;
1046         }
1047     }
1048
1049     // If the height is 0 or auto, then whether or not we are a self-collapsing block depends
1050     // on whether we have content that is all self-collapsing or not.
1051     if (hasAutoHeight || ((style()->height().isFixed() || style()->height().isPercent()) && style()->height().isZero())) {
1052         // If the block has inline children, see if we generated any line boxes.  If we have any
1053         // line boxes, then we can't be self-collapsing, since we have content.
1054         if (childrenInline())
1055             return !firstLineBox();
1056         
1057         // Whether or not we collapse is dependent on whether all our normal flow children
1058         // are also self-collapsing.
1059         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1060             if (child->isFloatingOrPositioned())
1061                 continue;
1062             if (!child->isSelfCollapsingBlock())
1063                 return false;
1064         }
1065         return true;
1066     }
1067     return false;
1068 }
1069
1070 void RenderBlock::startDelayUpdateScrollInfo()
1071 {
1072     if (gDelayUpdateScrollInfo == 0) {
1073         ASSERT(!gDelayedUpdateScrollInfoSet);
1074         gDelayedUpdateScrollInfoSet = new DelayedUpdateScrollInfoSet;
1075     }
1076     ASSERT(gDelayedUpdateScrollInfoSet);
1077     ++gDelayUpdateScrollInfo;
1078 }
1079
1080 void RenderBlock::finishDelayUpdateScrollInfo()
1081 {
1082     --gDelayUpdateScrollInfo;
1083     ASSERT(gDelayUpdateScrollInfo >= 0);
1084     if (gDelayUpdateScrollInfo == 0) {
1085         ASSERT(gDelayedUpdateScrollInfoSet);
1086
1087         OwnPtr<DelayedUpdateScrollInfoSet> infoSet(gDelayedUpdateScrollInfoSet);
1088         gDelayedUpdateScrollInfoSet = 0;
1089
1090         for (DelayedUpdateScrollInfoSet::iterator it = infoSet->begin(); it != infoSet->end(); ++it) {
1091             RenderBlock* block = *it;
1092             if (block->hasOverflowClip()) {
1093                 block->layer()->updateScrollInfoAfterLayout();
1094             }
1095         }
1096     }
1097 }
1098
1099 void RenderBlock::updateScrollInfoAfterLayout()
1100 {
1101     if (hasOverflowClip()) {
1102         if (gDelayUpdateScrollInfo)
1103             gDelayedUpdateScrollInfoSet->add(this);
1104         else
1105             layer()->updateScrollInfoAfterLayout();
1106     }
1107 }
1108
1109 void RenderBlock::layout()
1110 {
1111     // Update our first letter info now.
1112     updateFirstLetter();
1113
1114     // Table cells call layoutBlock directly, so don't add any logic here.  Put code into
1115     // layoutBlock().
1116     layoutBlock(false);
1117     
1118     // It's safe to check for control clip here, since controls can never be table cells.
1119     // If we have a lightweight clip, there can never be any overflow from children.
1120     if (hasControlClip() && m_overflow)
1121         clearLayoutOverflow();
1122 }
1123
1124 void RenderBlock::layoutBlock(bool relayoutChildren)
1125 {
1126     ASSERT(needsLayout());
1127
1128     if (isInline() && !isInlineBlockOrInlineTable()) // Inline <form>s inside various table elements can
1129         return;                                      // cause us to come in here.  Just bail.
1130
1131     if (!relayoutChildren && layoutOnlyPositionedObjects())
1132         return;
1133
1134     LayoutRepainter repainter(*this, m_everHadLayout && checkForRepaintDuringLayout());
1135     LayoutStateMaintainer statePusher(view(), this, IntSize(x(), y()), hasColumns() || hasTransform() || hasReflection());
1136
1137     int oldWidth = width();
1138     int oldColumnWidth = desiredColumnWidth();
1139
1140     calcWidth();
1141     calcColumnWidth();
1142
1143     m_overflow.clear();
1144
1145     if (oldWidth != width() || oldColumnWidth != desiredColumnWidth())
1146         relayoutChildren = true;
1147
1148     clearFloats();
1149
1150     int previousHeight = height();
1151     setHeight(0);
1152
1153     // We use four values, maxTopPos, maxTopNeg, maxBottomPos, and maxBottomNeg, to track
1154     // our current maximal positive and negative margins.  These values are used when we
1155     // are collapsed with adjacent blocks, so for example, if you have block A and B
1156     // collapsing together, then you'd take the maximal positive margin from both A and B
1157     // and subtract it from the maximal negative margin from both A and B to get the
1158     // true collapsed margin.  This algorithm is recursive, so when we finish layout()
1159     // our block knows its current maximal positive/negative values.
1160     //
1161     // Start out by setting our margin values to our current margins.  Table cells have
1162     // no margins, so we don't fill in the values for table cells.
1163     bool isCell = isTableCell();
1164     if (!isCell) {
1165         initMaxMarginValues();
1166
1167         setTopMarginQuirk(style()->marginTop().quirk());
1168         setBottomMarginQuirk(style()->marginBottom().quirk());
1169
1170         Node* n = node();
1171         if (n && n->hasTagName(formTag) && static_cast<HTMLFormElement*>(n)->isMalformed()) {
1172             // See if this form is malformed (i.e., unclosed). If so, don't give the form
1173             // a bottom margin.
1174             setMaxBottomMargins(0, 0);
1175         }
1176     }
1177
1178     // For overflow:scroll blocks, ensure we have both scrollbars in place always.
1179     if (scrollsOverflow()) {
1180         if (style()->overflowX() == OSCROLL)
1181             layer()->setHasHorizontalScrollbar(true);
1182         if (style()->overflowY() == OSCROLL)
1183             layer()->setHasVerticalScrollbar(true);
1184     }
1185
1186     int repaintTop = 0;
1187     int repaintBottom = 0;
1188     int maxFloatBottom = 0;
1189     if (!firstChild() && !isAnonymousBlock())
1190         setChildrenInline(true);
1191     if (childrenInline())
1192         layoutInlineChildren(relayoutChildren, repaintTop, repaintBottom);
1193     else
1194         layoutBlockChildren(relayoutChildren, maxFloatBottom);
1195
1196     // Expand our intrinsic height to encompass floats.
1197     int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
1198     if (floatBottom() > (height() - toAdd) && expandsToEncloseOverhangingFloats())
1199         setHeight(floatBottom() + toAdd);
1200     
1201     // Now lay out our columns within this intrinsic height, since they can slightly affect the intrinsic height as
1202     // we adjust for clean column breaks.
1203     int singleColumnBottom = layoutColumns();
1204
1205     // Calculate our new height.
1206     int oldHeight = height();
1207     calcHeight();
1208     if (oldHeight != height()) {
1209         if (oldHeight > height() && maxFloatBottom > height() && !childrenInline()) {
1210             // One of our children's floats may have become an overhanging float for us. We need to look for it.
1211             for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
1212                 if (child->isBlockFlow() && !child->isFloatingOrPositioned()) {
1213                     RenderBlock* block = toRenderBlock(child);
1214                     if (block->floatBottom() + block->y() > height())
1215                         addOverhangingFloats(block, -block->x(), -block->y(), false);
1216                 }
1217             }
1218         }
1219         
1220         // We have to rebalance columns to the new height.
1221         layoutColumns(singleColumnBottom);
1222     }
1223
1224     if (previousHeight != height())
1225         relayoutChildren = true;
1226
1227     // This check is designed to catch anyone
1228     // who wasn't going to propagate float information up to the parent and yet could potentially be painted by its ancestor.
1229     if (isRoot() || expandsToEncloseOverhangingFloats())
1230         addOverflowFromFloats();
1231
1232     // Add overflow from children (unless we're multi-column, since in that case all our child overflow is clipped anyway).
1233     if (!hasColumns()) {
1234         if (childrenInline())
1235             addOverflowFromInlineChildren();
1236         else
1237             addOverflowFromBlockChildren();
1238     }
1239
1240     // Add visual overflow from box-shadow and reflections.
1241     addShadowOverflow();
1242
1243     layoutPositionedObjects(relayoutChildren || isRoot());
1244
1245     positionListMarker();
1246     
1247     statePusher.pop();
1248
1249     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
1250     // we overflow or not.
1251     updateScrollInfoAfterLayout();
1252
1253     // Repaint with our new bounds if they are different from our old bounds.
1254     bool didFullRepaint = repainter.repaintAfterLayout();
1255     if (!didFullRepaint && repaintTop != repaintBottom && (style()->visibility() == VISIBLE || enclosingLayer()->hasVisibleContent())) {
1256         int repaintLeft = min(leftVisualOverflow(), leftLayoutOverflow());
1257         int repaintRight = max(rightVisualOverflow(), rightLayoutOverflow());
1258         IntRect repaintRect(repaintLeft, repaintTop, repaintRight - repaintLeft, repaintBottom - repaintTop);
1259
1260         // The repaint rect may be split across columns, in which case adjustRectForColumns() will return the union.
1261         adjustRectForColumns(repaintRect);
1262
1263         repaintRect.inflate(maximalOutlineSize(PaintPhaseOutline));
1264         
1265         if (hasOverflowClip()) {
1266             // Adjust repaint rect for scroll offset
1267             repaintRect.move(-layer()->scrolledContentOffset());
1268
1269             // Don't allow this rect to spill out of our overflow box.
1270             repaintRect.intersect(IntRect(0, 0, width(), height()));
1271         }
1272
1273         // Make sure the rect is still non-empty after intersecting for overflow above
1274         if (!repaintRect.isEmpty()) {
1275             repaintRectangle(repaintRect); // We need to do a partial repaint of our content.
1276             if (hasReflection())
1277                 repaintRectangle(reflectedRect(repaintRect));
1278         }
1279     }
1280     setNeedsLayout(false);
1281 }
1282
1283 void RenderBlock::addOverflowFromBlockChildren()
1284 {
1285     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1286         if (!child->isFloatingOrPositioned())
1287             addOverflowFromChild(child);
1288     }
1289 }
1290
1291 void RenderBlock::addOverflowFromFloats()
1292 {
1293     IntRect result;
1294     if (!m_floatingObjects)
1295         return;
1296     FloatingObject* r;
1297     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
1298     for (; (r = it.current()); ++it) {
1299         if (r->m_shouldPaint && !r->m_renderer->hasSelfPaintingLayer())
1300             addOverflowFromChild(r->m_renderer, IntSize(r->m_left + r->m_renderer->marginLeft(), r->m_top + r->m_renderer->marginTop()));
1301     }
1302     return;
1303 }
1304
1305 bool RenderBlock::expandsToEncloseOverhangingFloats() const
1306 {
1307     return isInlineBlockOrInlineTable() || isFloatingOrPositioned() || hasOverflowClip() || (parent() && parent()->isFlexibleBox()) || hasColumns() || isTableCell() || isFieldset();
1308 }
1309
1310 void RenderBlock::adjustPositionedBlock(RenderBox* child, const MarginInfo& marginInfo)
1311 {
1312     if (child->style()->hasStaticX()) {
1313         if (style()->direction() == LTR)
1314             child->layer()->setStaticX(borderLeft() + paddingLeft());
1315         else
1316             child->layer()->setStaticX(borderRight() + paddingRight());
1317     }
1318
1319     if (child->style()->hasStaticY()) {
1320         int y = height();
1321         if (!marginInfo.canCollapseWithTop()) {
1322             child->calcVerticalMargins();
1323             int marginTop = child->marginTop();
1324             int collapsedTopPos = marginInfo.posMargin();
1325             int collapsedTopNeg = marginInfo.negMargin();
1326             if (marginTop > 0) {
1327                 if (marginTop > collapsedTopPos)
1328                     collapsedTopPos = marginTop;
1329             } else {
1330                 if (-marginTop > collapsedTopNeg)
1331                     collapsedTopNeg = -marginTop;
1332             }
1333             y += (collapsedTopPos - collapsedTopNeg) - marginTop;
1334         }
1335         RenderLayer* childLayer = child->layer();
1336         if (childLayer->staticY() != y) {
1337             child->layer()->setStaticY(y);
1338             child->setChildNeedsLayout(true, false);
1339         }
1340     }
1341 }
1342
1343 void RenderBlock::adjustFloatingBlock(const MarginInfo& marginInfo)
1344 {
1345     // The float should be positioned taking into account the bottom margin
1346     // of the previous flow.  We add that margin into the height, get the
1347     // float positioned properly, and then subtract the margin out of the
1348     // height again.  In the case of self-collapsing blocks, we always just
1349     // use the top margins, since the self-collapsing block collapsed its
1350     // own bottom margin into its top margin.
1351     //
1352     // Note also that the previous flow may collapse its margin into the top of
1353     // our block.  If this is the case, then we do not add the margin in to our
1354     // height when computing the position of the float.   This condition can be tested
1355     // for by simply calling canCollapseWithTop.  See
1356     // http://www.hixie.ch/tests/adhoc/css/box/block/margin-collapse/046.html for
1357     // an example of this scenario.
1358     int marginOffset = marginInfo.canCollapseWithTop() ? 0 : marginInfo.margin();
1359     setHeight(height() + marginOffset);
1360     positionNewFloats();
1361     setHeight(height() - marginOffset);
1362 }
1363
1364 bool RenderBlock::handleSpecialChild(RenderBox* child, const MarginInfo& marginInfo)
1365 {
1366     // Handle in the given order
1367     return handlePositionedChild(child, marginInfo)
1368         || handleFloatingChild(child, marginInfo)
1369         || handleRunInChild(child);
1370 }
1371
1372
1373 bool RenderBlock::handlePositionedChild(RenderBox* child, const MarginInfo& marginInfo)
1374 {
1375     if (child->isPositioned()) {
1376         child->containingBlock()->insertPositionedObject(child);
1377         adjustPositionedBlock(child, marginInfo);
1378         return true;
1379     }
1380     return false;
1381 }
1382
1383 bool RenderBlock::handleFloatingChild(RenderBox* child, const MarginInfo& marginInfo)
1384 {
1385     if (child->isFloating()) {
1386         insertFloatingObject(child);
1387         adjustFloatingBlock(marginInfo);
1388         return true;
1389     }
1390     return false;
1391 }
1392
1393 bool RenderBlock::handleRunInChild(RenderBox* child)
1394 {
1395     // See if we have a run-in element with inline children.  If the
1396     // children aren't inline, then just treat the run-in as a normal
1397     // block.
1398     if (!child->isRunIn() || !child->childrenInline())
1399         return false;
1400     // FIXME: We don't handle non-block elements with run-in for now.
1401     if (!child->isRenderBlock())
1402         return false;
1403
1404     // Get the next non-positioned/non-floating RenderBlock.
1405     RenderBlock* blockRunIn = toRenderBlock(child);
1406     RenderObject* curr = blockRunIn->nextSibling();
1407     while (curr && curr->isFloatingOrPositioned())
1408         curr = curr->nextSibling();
1409
1410     if (!curr || !curr->isRenderBlock() || !curr->childrenInline() || curr->isRunIn() || curr->isAnonymous())
1411         return false;
1412
1413     RenderBlock* currBlock = toRenderBlock(curr);
1414
1415     // Remove the old child.
1416     children()->removeChildNode(this, blockRunIn);
1417
1418     // Create an inline.
1419     Node* runInNode = blockRunIn->node();
1420     RenderInline* inlineRunIn = new (renderArena()) RenderInline(runInNode ? runInNode : document());
1421     inlineRunIn->setStyle(blockRunIn->style());
1422
1423     bool runInIsGenerated = child->style()->styleType() == BEFORE || child->style()->styleType() == AFTER;
1424
1425     // Move the nodes from the old child to the new child, but skip any :before/:after content.  It has already
1426     // been regenerated by the new inline.
1427     for (RenderObject* runInChild = blockRunIn->firstChild(); runInChild;) {
1428         RenderObject* nextSibling = runInChild->nextSibling();
1429         if (runInIsGenerated || (runInChild->style()->styleType() != BEFORE && runInChild->style()->styleType() != AFTER)) {
1430             blockRunIn->children()->removeChildNode(blockRunIn, runInChild, false);
1431             inlineRunIn->addChild(runInChild); // Use addChild instead of appendChildNode since it handles correct placement of the children relative to :after-generated content.
1432         }
1433         runInChild = nextSibling;
1434     }
1435
1436     // Now insert the new child under |currBlock|.
1437     currBlock->children()->insertChildNode(currBlock, inlineRunIn, currBlock->firstChild());
1438     
1439     // If the run-in had an element, we need to set the new renderer.
1440     if (runInNode)
1441         runInNode->setRenderer(inlineRunIn);
1442
1443     // Destroy the block run-in.
1444     blockRunIn->destroy();
1445
1446     // The block acts like an inline, so just null out its
1447     // position.
1448     
1449     return true;
1450 }
1451
1452 int RenderBlock::collapseMargins(RenderBox* child, MarginInfo& marginInfo)
1453 {
1454     // Get our max pos and neg top margins.
1455     int posTop = child->maxTopMargin(true);
1456     int negTop = child->maxTopMargin(false);
1457
1458     // For self-collapsing blocks, collapse our bottom margins into our
1459     // top to get new posTop and negTop values.
1460     if (child->isSelfCollapsingBlock()) {
1461         posTop = max(posTop, child->maxBottomMargin(true));
1462         negTop = max(negTop, child->maxBottomMargin(false));
1463     }
1464     
1465     // See if the top margin is quirky. We only care if this child has
1466     // margins that will collapse with us.
1467     bool topQuirk = child->isTopMarginQuirk() || style()->marginTopCollapse() == MDISCARD;
1468
1469     if (marginInfo.canCollapseWithTop()) {
1470         // This child is collapsing with the top of the
1471         // block.  If it has larger margin values, then we need to update
1472         // our own maximal values.
1473         if (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !topQuirk)
1474             setMaxTopMargins(max(posTop, maxTopPosMargin()), max(negTop, maxTopNegMargin()));
1475
1476         // The minute any of the margins involved isn't a quirk, don't
1477         // collapse it away, even if the margin is smaller (www.webreference.com
1478         // has an example of this, a <dt> with 0.8em author-specified inside
1479         // a <dl> inside a <td>.
1480         if (!marginInfo.determinedTopQuirk() && !topQuirk && (posTop-negTop)) {
1481             setTopMarginQuirk(false);
1482             marginInfo.setDeterminedTopQuirk(true);
1483         }
1484
1485         if (!marginInfo.determinedTopQuirk() && topQuirk && marginTop() == 0)
1486             // We have no top margin and our top child has a quirky margin.
1487             // We will pick up this quirky margin and pass it through.
1488             // This deals with the <td><div><p> case.
1489             // Don't do this for a block that split two inlines though.  You do
1490             // still apply margins in this case.
1491             setTopMarginQuirk(true);
1492     }
1493
1494     if (marginInfo.quirkContainer() && marginInfo.atTopOfBlock() && (posTop - negTop))
1495         marginInfo.setTopQuirk(topQuirk);
1496
1497     int ypos = height();
1498     if (child->isSelfCollapsingBlock()) {
1499         // This child has no height.  We need to compute our
1500         // position before we collapse the child's margins together,
1501         // so that we can get an accurate position for the zero-height block.
1502         int collapsedTopPos = max(marginInfo.posMargin(), child->maxTopMargin(true));
1503         int collapsedTopNeg = max(marginInfo.negMargin(), child->maxTopMargin(false));
1504         marginInfo.setMargin(collapsedTopPos, collapsedTopNeg);
1505         
1506         // Now collapse the child's margins together, which means examining our
1507         // bottom margin values as well. 
1508         marginInfo.setPosMarginIfLarger(child->maxBottomMargin(true));
1509         marginInfo.setNegMarginIfLarger(child->maxBottomMargin(false));
1510
1511         if (!marginInfo.canCollapseWithTop())
1512             // We need to make sure that the position of the self-collapsing block
1513             // is correct, since it could have overflowing content
1514             // that needs to be positioned correctly (e.g., a block that
1515             // had a specified height of 0 but that actually had subcontent).
1516             ypos = height() + collapsedTopPos - collapsedTopNeg;
1517     }
1518     else {
1519         if (child->style()->marginTopCollapse() == MSEPARATE) {
1520             setHeight(height() + marginInfo.margin() + child->marginTop());
1521             ypos = height();
1522         }
1523         else if (!marginInfo.atTopOfBlock() ||
1524             (!marginInfo.canCollapseTopWithChildren()
1525              && (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.topQuirk()))) {
1526             // We're collapsing with a previous sibling's margins and not
1527             // with the top of the block.
1528             setHeight(height() + max(marginInfo.posMargin(), posTop) - max(marginInfo.negMargin(), negTop));
1529             ypos = height();
1530         }
1531
1532         marginInfo.setPosMargin(child->maxBottomMargin(true));
1533         marginInfo.setNegMargin(child->maxBottomMargin(false));
1534
1535         if (marginInfo.margin())
1536             marginInfo.setBottomQuirk(child->isBottomMarginQuirk() || style()->marginBottomCollapse() == MDISCARD);
1537     }
1538     
1539     return ypos;
1540 }
1541
1542 int RenderBlock::clearFloatsIfNeeded(RenderBox* child, MarginInfo& marginInfo, int oldTopPosMargin, int oldTopNegMargin, int yPos)
1543 {
1544     int heightIncrease = getClearDelta(child, yPos);
1545     if (!heightIncrease)
1546         return yPos;
1547
1548     if (child->isSelfCollapsingBlock()) {
1549         // For self-collapsing blocks that clear, they can still collapse their
1550         // margins with following siblings.  Reset the current margins to represent
1551         // the self-collapsing block's margins only.
1552         // CSS2.1 states:
1553         // "An element that has had clearance applied to it never collapses its top margin with its parent block's bottom margin.
1554         // Therefore if we are at the bottom of the block, let's go ahead and reset margins to only include the
1555         // self-collapsing block's bottom margin.
1556         bool atBottomOfBlock = true;
1557         for (RenderBox* curr = child->nextSiblingBox(); curr && atBottomOfBlock; curr = curr->nextSiblingBox()) {
1558             if (!curr->isFloatingOrPositioned())
1559                 atBottomOfBlock = false;
1560         }
1561         if (atBottomOfBlock) {
1562             marginInfo.setPosMargin(child->maxBottomMargin(true));
1563             marginInfo.setNegMargin(child->maxBottomMargin(false));
1564         } else {
1565             marginInfo.setPosMargin(max(child->maxTopMargin(true), child->maxBottomMargin(true)));
1566             marginInfo.setNegMargin(max(child->maxTopMargin(false), child->maxBottomMargin(false)));
1567         }
1568         
1569         // Adjust our height such that we are ready to be collapsed with subsequent siblings (or the bottom
1570         // of the parent block).
1571         setHeight(child->y() - max(0, marginInfo.margin()));
1572     } else
1573         // Increase our height by the amount we had to clear.
1574         setHeight(height() + heightIncrease);
1575     
1576     if (marginInfo.canCollapseWithTop()) {
1577         // We can no longer collapse with the top of the block since a clear
1578         // occurred.  The empty blocks collapse into the cleared block.
1579         // FIXME: This isn't quite correct.  Need clarification for what to do
1580         // if the height the cleared block is offset by is smaller than the
1581         // margins involved.
1582         setMaxTopMargins(oldTopPosMargin, oldTopNegMargin);
1583         marginInfo.setAtTopOfBlock(false);
1584     }
1585     
1586     return yPos + heightIncrease;
1587 }
1588
1589 int RenderBlock::estimateVerticalPosition(RenderBox* child, const MarginInfo& marginInfo)
1590 {
1591     // FIXME: We need to eliminate the estimation of vertical position, because when it's wrong we sometimes trigger a pathological
1592     // relayout if there are intruding floats.
1593     int yPosEstimate = height();
1594     if (!marginInfo.canCollapseWithTop()) {
1595         int childMarginTop = child->selfNeedsLayout() ? child->marginTop() : child->collapsedMarginTop();
1596         yPosEstimate += max(marginInfo.margin(), childMarginTop);
1597     }
1598     yPosEstimate += getClearDelta(child, yPosEstimate);
1599     return yPosEstimate;
1600 }
1601
1602 void RenderBlock::determineHorizontalPosition(RenderBox* child)
1603 {
1604     int xPos = borderLeft() + paddingLeft();
1605     if (style()->direction() == LTR) {
1606         // Add in our left margin.
1607         int chPos = xPos + child->marginLeft();
1608         
1609         // Some objects (e.g., tables, horizontal rules, overflow:auto blocks) avoid floats.  They need
1610         // to shift over as necessary to dodge any floats that might get in the way.
1611         if (child->avoidsFloats()) {
1612             int leftOff = leftOffset(height(), false);
1613             if (style()->textAlign() != WEBKIT_CENTER && child->style()->marginLeft().type() != Auto) {
1614                 if (child->marginLeft() < 0)
1615                     leftOff += child->marginLeft();
1616                 chPos = max(chPos, leftOff); // Let the float sit in the child's margin if it can fit.
1617             }
1618             else if (leftOff != xPos) {
1619                 // The object is shifting right. The object might be centered, so we need to
1620                 // recalculate our horizontal margins. Note that the containing block content
1621                 // width computation will take into account the delta between |leftOff| and |xPos|
1622                 // so that we can just pass the content width in directly to the |calcHorizontalMargins|
1623                 // function.
1624                 child->calcHorizontalMargins(child->style()->marginLeft(), child->style()->marginRight(), lineWidth(child->y(), false));
1625                 chPos = leftOff + child->marginLeft();
1626             }
1627         }
1628         view()->addLayoutDelta(IntSize(child->x() - chPos, 0));
1629         child->setLocation(chPos, child->y());
1630     } else {
1631         xPos += availableWidth();
1632         int chPos = xPos - (child->width() + child->marginRight());
1633         if (child->avoidsFloats()) {
1634             int rightOff = rightOffset(height(), false);
1635             if (style()->textAlign() != WEBKIT_CENTER && child->style()->marginRight().type() != Auto) {
1636                 if (child->marginRight() < 0)
1637                     rightOff -= child->marginRight();
1638                 chPos = min(chPos, rightOff - child->width()); // Let the float sit in the child's margin if it can fit.
1639             } else if (rightOff != xPos) {
1640                 // The object is shifting left. The object might be centered, so we need to
1641                 // recalculate our horizontal margins. Note that the containing block content
1642                 // width computation will take into account the delta between |rightOff| and |xPos|
1643                 // so that we can just pass the content width in directly to the |calcHorizontalMargins|
1644                 // function.
1645                 child->calcHorizontalMargins(child->style()->marginLeft(), child->style()->marginRight(), lineWidth(child->y(), false));
1646                 chPos = rightOff - child->marginRight() - child->width();
1647             }
1648         }
1649         view()->addLayoutDelta(IntSize(child->x() - chPos, 0));
1650         child->setLocation(chPos, child->y());
1651     }
1652 }
1653
1654 void RenderBlock::setCollapsedBottomMargin(const MarginInfo& marginInfo)
1655 {
1656     if (marginInfo.canCollapseWithBottom() && !marginInfo.canCollapseWithTop()) {
1657         // Update our max pos/neg bottom margins, since we collapsed our bottom margins
1658         // with our children.
1659         setMaxBottomMargins(max(maxBottomPosMargin(), marginInfo.posMargin()), max(maxBottomNegMargin(), marginInfo.negMargin()));
1660
1661         if (!marginInfo.bottomQuirk())
1662             setBottomMarginQuirk(false);
1663
1664         if (marginInfo.bottomQuirk() && marginBottom() == 0)
1665             // We have no bottom margin and our last child has a quirky margin.
1666             // We will pick up this quirky margin and pass it through.
1667             // This deals with the <td><div><p> case.
1668             setBottomMarginQuirk(true);
1669     }
1670 }
1671
1672 void RenderBlock::handleBottomOfBlock(int top, int bottom, MarginInfo& marginInfo)
1673 {
1674     marginInfo.setAtBottomOfBlock(true);
1675
1676     // If we can't collapse with children then go ahead and add in the bottom margin.
1677     if (!marginInfo.canCollapseWithBottom() && !marginInfo.canCollapseWithTop()
1678         && (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.bottomQuirk()))
1679         setHeight(height() + marginInfo.margin());
1680         
1681     // Now add in our bottom border/padding.
1682     setHeight(height() + bottom);
1683
1684     // Negative margins can cause our height to shrink below our minimal height (border/padding).
1685     // If this happens, ensure that the computed height is increased to the minimal height.
1686     setHeight(max(height(), top + bottom));
1687
1688     // Update our bottom collapsed margin info.
1689     setCollapsedBottomMargin(marginInfo);
1690 }
1691
1692 void RenderBlock::layoutBlockChildren(bool relayoutChildren, int& maxFloatBottom)
1693 {
1694     if (gPercentHeightDescendantsMap) {
1695         if (HashSet<RenderBox*>* descendants = gPercentHeightDescendantsMap->get(this)) {
1696             HashSet<RenderBox*>::iterator end = descendants->end();
1697             for (HashSet<RenderBox*>::iterator it = descendants->begin(); it != end; ++it) {
1698                 RenderBox* box = *it;
1699                 while (box != this) {
1700                     if (box->normalChildNeedsLayout())
1701                         break;
1702                     box->setChildNeedsLayout(true, false);
1703                     box = box->containingBlock();
1704                     ASSERT(box);
1705                     if (!box)
1706                         break;
1707                 }
1708             }
1709         }
1710     }
1711
1712     int top = borderTop() + paddingTop();
1713     int bottom = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
1714
1715     setHeight(top);
1716
1717     // The margin struct caches all our current margin collapsing state.  The compact struct caches state when we encounter compacts,
1718     MarginInfo marginInfo(this, top, bottom);
1719
1720     // Fieldsets need to find their legend and position it inside the border of the object.
1721     // The legend then gets skipped during normal layout.
1722     RenderObject* legend = layoutLegend(relayoutChildren);
1723
1724     int previousFloatBottom = 0;
1725     maxFloatBottom = 0;
1726
1727     RenderBox* next = firstChildBox();
1728
1729     while (next) {
1730         RenderBox* child = next;
1731         next = child->nextSiblingBox();
1732
1733         if (legend == child)
1734             continue; // Skip the legend, since it has already been positioned up in the fieldset's border.
1735
1736         // Make sure we layout children if they need it.
1737         // FIXME: Technically percentage height objects only need a relayout if their percentage isn't going to be turned into
1738         // an auto value.  Add a method to determine this, so that we can avoid the relayout.
1739         if (relayoutChildren || ((child->style()->height().isPercent() || child->style()->minHeight().isPercent() || child->style()->maxHeight().isPercent()) && !isRenderView()))
1740             child->setChildNeedsLayout(true, false);
1741
1742         // If relayoutChildren is set and we have percentage padding, we also need to invalidate the child's pref widths.
1743         if (relayoutChildren && (child->style()->paddingLeft().isPercent() || child->style()->paddingRight().isPercent()))
1744             child->setPrefWidthsDirty(true, false);
1745
1746         // Handle the four types of special elements first.  These include positioned content, floating content, compacts and
1747         // run-ins.  When we encounter these four types of objects, we don't actually lay them out as normal flow blocks.
1748         if (handleSpecialChild(child, marginInfo))
1749             continue;
1750
1751         // Lay out the child.
1752         layoutBlockChild(child, marginInfo, previousFloatBottom, maxFloatBottom);
1753     }
1754     
1755     // Now do the handling of the bottom of the block, adding in our bottom border/padding and
1756     // determining the correct collapsed bottom margin information.
1757     handleBottomOfBlock(top, bottom, marginInfo);
1758 }
1759
1760 void RenderBlock::layoutBlockChild(RenderBox* child, MarginInfo& marginInfo, int& previousFloatBottom, int& maxFloatBottom)
1761 {
1762     int oldTopPosMargin = maxTopPosMargin();
1763     int oldTopNegMargin = maxTopNegMargin();
1764
1765     // The child is a normal flow object.  Compute its vertical margins now.
1766     child->calcVerticalMargins();
1767
1768     // Do not allow a collapse if the margin top collapse style is set to SEPARATE.
1769     if (child->style()->marginTopCollapse() == MSEPARATE) {
1770         marginInfo.setAtTopOfBlock(false);
1771         marginInfo.clearMargin();
1772     }
1773
1774     // Try to guess our correct y position.  In most cases this guess will
1775     // be correct.  Only if we're wrong (when we compute the real y position)
1776     // will we have to potentially relayout.
1777     int yPosEstimate = estimateVerticalPosition(child, marginInfo);
1778
1779     // Cache our old rect so that we can dirty the proper repaint rects if the child moves.
1780     IntRect oldRect(child->x(), child->y() , child->width(), child->height());
1781 #ifndef NDEBUG
1782     IntSize oldLayoutDelta = view()->layoutDelta();
1783 #endif
1784     // Go ahead and position the child as though it didn't collapse with the top.
1785     view()->addLayoutDelta(IntSize(0, child->y() - yPosEstimate));
1786     child->setLocation(child->x(), yPosEstimate);
1787
1788     bool markDescendantsWithFloats = false;
1789     if (yPosEstimate != oldRect.y() && !child->avoidsFloats() && child->isBlockFlow() && toRenderBlock(child)->containsFloats())
1790         markDescendantsWithFloats = true;
1791     else if (!child->avoidsFloats() || child->shrinkToAvoidFloats()) {
1792         // If an element might be affected by the presence of floats, then always mark it for
1793         // layout.
1794         int fb = max(previousFloatBottom, floatBottom());
1795         if (fb > yPosEstimate)
1796             markDescendantsWithFloats = true;
1797     }
1798
1799     if (child->isRenderBlock()) {
1800         if (markDescendantsWithFloats)
1801             toRenderBlock(child)->markAllDescendantsWithFloatsForLayout();
1802
1803         previousFloatBottom = max(previousFloatBottom, oldRect.y() + toRenderBlock(child)->floatBottom());
1804     }
1805
1806     bool childHadLayout = child->m_everHadLayout;
1807     bool childNeededLayout = child->needsLayout();
1808     if (childNeededLayout)
1809         child->layout();
1810
1811     // Now determine the correct ypos based off examination of collapsing margin
1812     // values.
1813     int yBeforeClear = collapseMargins(child, marginInfo);
1814
1815     // Now check for clear.
1816     int yAfterClear = clearFloatsIfNeeded(child, marginInfo, oldTopPosMargin, oldTopNegMargin, yBeforeClear);
1817     
1818     view()->addLayoutDelta(IntSize(0, yPosEstimate - yAfterClear));
1819     child->setLocation(child->x(), yAfterClear);
1820
1821     // Now we have a final y position.  See if it really does end up being different from our estimate.
1822     if (yAfterClear != yPosEstimate) {
1823         if (child->shrinkToAvoidFloats()) {
1824             // The child's width depends on the line width.
1825             // When the child shifts to clear an item, its width can
1826             // change (because it has more available line width).
1827             // So go ahead and mark the item as dirty.
1828             child->setChildNeedsLayout(true, false);
1829         }
1830         if (!child->avoidsFloats() && child->isBlockFlow() && toRenderBlock(child)->containsFloats())
1831             toRenderBlock(child)->markAllDescendantsWithFloatsForLayout();
1832         // Our guess was wrong. Make the child lay itself out again.
1833         child->layoutIfNeeded();
1834     }
1835
1836     // We are no longer at the top of the block if we encounter a non-empty child.  
1837     // This has to be done after checking for clear, so that margins can be reset if a clear occurred.
1838     if (marginInfo.atTopOfBlock() && !child->isSelfCollapsingBlock())
1839         marginInfo.setAtTopOfBlock(false);
1840
1841     // Now place the child in the correct horizontal position
1842     determineHorizontalPosition(child);
1843
1844     // Update our height now that the child has been placed in the correct position.
1845     setHeight(height() + child->height());
1846     if (child->style()->marginBottomCollapse() == MSEPARATE) {
1847         setHeight(height() + child->marginBottom());
1848         marginInfo.clearMargin();
1849     }
1850     // If the child has overhanging floats that intrude into following siblings (or possibly out
1851     // of this block), then the parent gets notified of the floats now.
1852     if (child->isBlockFlow() && toRenderBlock(child)->containsFloats())
1853         maxFloatBottom = max(maxFloatBottom, addOverhangingFloats(toRenderBlock(child), -child->x(), -child->y(), !childNeededLayout));
1854
1855     IntSize childOffset(child->x() - oldRect.x(), child->y() - oldRect.y());
1856     if (childOffset.width() || childOffset.height()) {
1857         view()->addLayoutDelta(childOffset);
1858
1859         // If the child moved, we have to repaint it as well as any floating/positioned
1860         // descendants.  An exception is if we need a layout.  In this case, we know we're going to
1861         // repaint ourselves (and the child) anyway.
1862         if (childHadLayout && !selfNeedsLayout() && child->checkForRepaintDuringLayout())
1863             child->repaintDuringLayoutIfMoved(oldRect);
1864     }
1865
1866     if (!childHadLayout && child->checkForRepaintDuringLayout()) {
1867         child->repaint();
1868         child->repaintOverhangingFloats(true);
1869     }
1870
1871     ASSERT(oldLayoutDelta == view()->layoutDelta());
1872 }
1873
1874 bool RenderBlock::layoutOnlyPositionedObjects()
1875 {
1876     if (!posChildNeedsLayout() || normalChildNeedsLayout() || selfNeedsLayout())
1877         return false;
1878
1879     LayoutStateMaintainer statePusher(view(), this, IntSize(x(), y()), hasColumns() || hasTransform() || hasReflection());
1880
1881     if (needsPositionedMovementLayout()) {
1882         tryLayoutDoingPositionedMovementOnly();
1883         if (needsLayout())
1884             return false;
1885     }
1886
1887     // All we have to is lay out our positioned objects.
1888     layoutPositionedObjects(false);
1889
1890     statePusher.pop();
1891
1892     updateScrollInfoAfterLayout();
1893
1894     setNeedsLayout(false);
1895     return true;
1896 }
1897
1898 void RenderBlock::layoutPositionedObjects(bool relayoutChildren)
1899 {
1900     if (m_positionedObjects) {
1901         RenderBox* r;
1902         Iterator end = m_positionedObjects->end();
1903         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
1904             r = *it;
1905             // When a non-positioned block element moves, it may have positioned children that are implicitly positioned relative to the
1906             // non-positioned block.  Rather than trying to detect all of these movement cases, we just always lay out positioned
1907             // objects that are positioned implicitly like this.  Such objects are rare, and so in typical DHTML menu usage (where everything is
1908             // positioned explicitly) this should not incur a performance penalty.
1909             if (relayoutChildren || (r->style()->hasStaticY() && r->parent() != this && r->parent()->isBlockFlow()))
1910                 r->setChildNeedsLayout(true, false);
1911                 
1912             // If relayoutChildren is set and we have percentage padding, we also need to invalidate the child's pref widths.
1913             //if (relayoutChildren && (r->style()->paddingLeft().isPercent() || r->style()->paddingRight().isPercent()))
1914                 r->setPrefWidthsDirty(true, false);
1915             
1916             // 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
1917             // and we hit the available width constraint, the layoutIfNeeded() will catch it and do a full layout.
1918             if (r->needsPositionedMovementLayoutOnly())
1919                 r->tryLayoutDoingPositionedMovementOnly();
1920             r->layoutIfNeeded();
1921         }
1922     }
1923 }
1924
1925 void RenderBlock::markPositionedObjectsForLayout()
1926 {
1927     if (m_positionedObjects) {
1928         RenderBox* r;
1929         Iterator end = m_positionedObjects->end();
1930         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
1931             r = *it;
1932             r->setChildNeedsLayout(true);
1933         }
1934     }
1935 }
1936
1937 void RenderBlock::repaintOverhangingFloats(bool paintAllDescendants)
1938 {
1939     // Repaint any overhanging floats (if we know we're the one to paint them).
1940     if (hasOverhangingFloats()) {
1941         // We think that we must be in a bad state if m_floatingObjects is nil at this point, so 
1942         // we assert on Debug builds and nil-check Release builds.
1943         ASSERT(m_floatingObjects);
1944         if (!m_floatingObjects)
1945             return;
1946         
1947         FloatingObject* r;
1948         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
1949
1950         // FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
1951         // in this block. Better yet would be to push extra state for the containers of other floats.
1952         view()->disableLayoutState();
1953         for ( ; (r = it.current()); ++it) {
1954             // Only repaint the object if it is overhanging, is not in its own layer, and
1955             // is our responsibility to paint (m_shouldPaint is set). When paintAllDescendants is true, the latter
1956             // condition is replaced with being a descendant of us.
1957             if (r->m_bottom > height() && ((paintAllDescendants && r->m_renderer->isDescendantOf(this)) || r->m_shouldPaint) && !r->m_renderer->hasSelfPaintingLayer()) {
1958                 r->m_renderer->repaint();
1959                 r->m_renderer->repaintOverhangingFloats();
1960             }
1961         }
1962         view()->enableLayoutState();
1963     }
1964 }
1965  
1966 void RenderBlock::paint(PaintInfo& paintInfo, int tx, int ty)
1967 {
1968     tx += x();
1969     ty += y();
1970     
1971     PaintPhase phase = paintInfo.phase;
1972
1973     // Check if we need to do anything at all.
1974     // FIXME: Could eliminate the isRoot() check if we fix background painting so that the RenderView
1975     // paints the root's background.
1976     if (!isRoot()) {
1977         IntRect overflowBox = visibleOverflowRect();
1978         overflowBox.inflate(maximalOutlineSize(paintInfo.phase));
1979         overflowBox.move(tx, ty);
1980         if (!overflowBox.intersects(paintInfo.rect))
1981             return;
1982     }
1983
1984     bool pushedClip = pushContentsClip(paintInfo, tx, ty);
1985     paintObject(paintInfo, tx, ty);
1986     if (pushedClip)
1987         popContentsClip(paintInfo, phase, tx, ty);
1988
1989     // Our scrollbar widgets paint exactly when we tell them to, so that they work properly with
1990     // z-index.  We paint after we painted the background/border, so that the scrollbars will
1991     // sit above the background/border.
1992     if (hasOverflowClip() && style()->visibility() == VISIBLE && (phase == PaintPhaseBlockBackground || phase == PaintPhaseChildBlockBackground) && paintInfo.shouldPaintWithinRoot(this))
1993         layer()->paintOverflowControls(paintInfo.context, tx, ty, paintInfo.rect);
1994 }
1995
1996 void RenderBlock::paintColumnRules(PaintInfo& paintInfo, int tx, int ty)
1997 {
1998     const Color& ruleColor = style()->visitedDependentColor(CSSPropertyWebkitColumnRuleColor);
1999     bool ruleTransparent = style()->columnRuleIsTransparent();
2000     EBorderStyle ruleStyle = style()->columnRuleStyle();
2001     int ruleWidth = style()->columnRuleWidth();
2002     int colGap = columnGap();
2003     bool renderRule = ruleStyle > BHIDDEN && !ruleTransparent && ruleWidth <= colGap;
2004     if (!renderRule)
2005         return;
2006
2007     // We need to do multiple passes, breaking up our child painting into strips.
2008     Vector<IntRect>* colRects = columnRects();
2009     unsigned colCount = colRects->size();
2010     int currXOffset = style()->direction() == LTR ? 0 : contentWidth();
2011     int ruleAdd = borderLeft() + paddingLeft();
2012     int ruleX = style()->direction() == LTR ? 0 : contentWidth();
2013     for (unsigned i = 0; i < colCount; i++) {
2014         IntRect colRect = colRects->at(i);
2015
2016         // Move to the next position.
2017         if (style()->direction() == LTR) {
2018             ruleX += colRect.width() + colGap / 2;
2019             currXOffset += colRect.width() + colGap;
2020         } else {
2021             ruleX -= (colRect.width() + colGap / 2);
2022             currXOffset -= (colRect.width() + colGap);
2023         }
2024        
2025         // Now paint the column rule.
2026         if (i < colCount - 1) {
2027             int ruleStart = tx + ruleX - ruleWidth / 2 + ruleAdd;
2028             int ruleEnd = ruleStart + ruleWidth;
2029             int ruleTop = ty + borderTop() + paddingTop();
2030             int ruleBottom = ruleTop + contentHeight();
2031             drawLineForBoxSide(paintInfo.context, ruleStart, ruleTop, ruleEnd, ruleBottom,
2032                                style()->direction() == LTR ? BSLeft : BSRight, ruleColor, ruleStyle, 0, 0);
2033         }
2034         
2035         ruleX = currXOffset;
2036     }
2037 }
2038
2039 void RenderBlock::paintColumnContents(PaintInfo& paintInfo, int tx, int ty, bool paintingFloats)
2040 {
2041     // We need to do multiple passes, breaking up our child painting into strips.
2042     GraphicsContext* context = paintInfo.context;
2043     int colGap = columnGap();
2044     Vector<IntRect>* colRects = columnRects();
2045     unsigned colCount = colRects->size();
2046     if (!colCount)
2047         return;
2048     int currXOffset = style()->direction() == LTR ? 0 : contentWidth() - colRects->at(0).width();
2049     int currYOffset = 0;
2050     for (unsigned i = 0; i < colCount; i++) {
2051         // For each rect, we clip to the rect, and then we adjust our coords.
2052         IntRect colRect = colRects->at(i);
2053         colRect.move(tx, ty);
2054         PaintInfo info(paintInfo);
2055         info.rect.intersect(colRect);
2056         
2057         if (!info.rect.isEmpty()) {
2058             context->save();
2059             
2060             // Each strip pushes a clip, since column boxes are specified as being
2061             // like overflow:hidden.
2062             context->clip(colRect);
2063             
2064             // Adjust our x and y when painting.
2065             int finalX = tx + currXOffset;
2066             int finalY = ty + currYOffset;
2067             if (paintingFloats)
2068                 paintFloats(info, finalX, finalY, paintInfo.phase == PaintPhaseSelection || paintInfo.phase == PaintPhaseTextClip);
2069             else
2070                 paintContents(info, finalX, finalY);
2071
2072             context->restore();
2073         }
2074         
2075         // Move to the next position.
2076         if (style()->direction() == LTR)
2077             currXOffset += colRect.width() + colGap;
2078         else
2079             currXOffset -= (colRect.width() + colGap);
2080         
2081         currYOffset -= colRect.height();
2082     }
2083 }
2084
2085 void RenderBlock::paintContents(PaintInfo& paintInfo, int tx, int ty)
2086 {
2087     // Avoid painting descendants of the root element when stylesheets haven't loaded.  This eliminates FOUC.
2088     // It's ok not to draw, because later on, when all the stylesheets do load, updateStyleSelector on the Document
2089     // will do a full repaint().
2090     if (document()->didLayoutWithPendingStylesheets() && !isRenderView())
2091         return;
2092
2093     if (childrenInline())
2094         m_lineBoxes.paint(this, paintInfo, tx, ty);
2095     else
2096         paintChildren(paintInfo, tx, ty);
2097 }
2098
2099 void RenderBlock::paintChildren(PaintInfo& paintInfo, int tx, int ty)
2100 {
2101     PaintPhase newPhase = (paintInfo.phase == PaintPhaseChildOutlines) ? PaintPhaseOutline : paintInfo.phase;
2102     newPhase = (newPhase == PaintPhaseChildBlockBackgrounds) ? PaintPhaseChildBlockBackground : newPhase;
2103     
2104     // We don't paint our own background, but we do let the kids paint their backgrounds.
2105     PaintInfo info(paintInfo);
2106     info.phase = newPhase;
2107     info.updatePaintingRootForChildren(this);
2108     bool checkPageBreaks = document()->paginated() && !document()->settings()->paginateDuringLayoutEnabled();
2109     bool checkColumnBreaks = !checkPageBreaks && !view()->printRect().isEmpty() && !document()->settings()->paginateDuringLayoutEnabled();
2110
2111     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {        
2112         // Check for page-break-before: always, and if it's set, break and bail.
2113         bool checkBeforeAlways = !childrenInline() && ((checkPageBreaks && child->style()->pageBreakBefore() == PBALWAYS) || (checkColumnBreaks && child->style()->columnBreakBefore() == PBALWAYS));
2114         if (checkBeforeAlways
2115             && (ty + child->y()) > paintInfo.rect.y()
2116             && (ty + child->y()) < paintInfo.rect.bottom()) {
2117             view()->setBestTruncatedAt(ty + child->y(), this, true);
2118             return;
2119         }
2120
2121         if (!child->hasSelfPaintingLayer() && !child->isFloating())
2122             child->paint(info, tx, ty);
2123
2124         // Check for page-break-after: always, and if it's set, break and bail.
2125         bool checkAfterAlways = !childrenInline() && ((checkPageBreaks && child->style()->pageBreakAfter() == PBALWAYS) || (checkColumnBreaks && child->style()->columnBreakAfter() == PBALWAYS));
2126         if (checkAfterAlways
2127             && (ty + child->y() + child->height()) > paintInfo.rect.y()
2128             && (ty + child->y() + child->height()) < paintInfo.rect.bottom()) {
2129             view()->setBestTruncatedAt(ty + child->y() + child->height() + max(0, child->collapsedMarginBottom()), this, true);
2130             return;
2131         }
2132     }
2133 }
2134
2135 void RenderBlock::paintCaret(PaintInfo& paintInfo, int tx, int ty, CaretType type)
2136 {
2137     SelectionController* selection = type == CursorCaret ? frame()->selection() : frame()->dragCaretController();
2138
2139     // Paint the caret if the SelectionController says so or if caret browsing is enabled
2140     bool caretBrowsing = frame()->settings() && frame()->settings()->caretBrowsingEnabled();
2141     RenderObject* caretPainter = selection->caretRenderer();
2142     if (caretPainter == this && (selection->isContentEditable() || caretBrowsing)) {
2143         // Convert the painting offset into the local coordinate system of this renderer,
2144         // to match the localCaretRect computed by the SelectionController
2145         offsetForContents(tx, ty);
2146
2147         if (type == CursorCaret)
2148             frame()->selection()->paintCaret(paintInfo.context, tx, ty, paintInfo.rect);
2149         else
2150             frame()->paintDragCaret(paintInfo.context, tx, ty, paintInfo.rect);
2151     }
2152 }
2153
2154 void RenderBlock::paintObject(PaintInfo& paintInfo, int tx, int ty)
2155 {
2156     PaintPhase paintPhase = paintInfo.phase;
2157
2158     // 1. paint background, borders etc
2159     if ((paintPhase == PaintPhaseBlockBackground || paintPhase == PaintPhaseChildBlockBackground) && style()->visibility() == VISIBLE) {
2160         if (hasBoxDecorations())
2161             paintBoxDecorations(paintInfo, tx, ty);
2162         if (hasColumns())
2163             paintColumnRules(paintInfo, tx, ty);
2164     }
2165
2166     if (paintPhase == PaintPhaseMask && style()->visibility() == VISIBLE) {
2167         paintMask(paintInfo, tx, ty);
2168         return;
2169     }
2170
2171     // We're done.  We don't bother painting any children.
2172     if (paintPhase == PaintPhaseBlockBackground)
2173         return;
2174
2175     // Adjust our painting position if we're inside a scrolled layer (e.g., an overflow:auto div).
2176     int scrolledX = tx;
2177     int scrolledY = ty;
2178     if (hasOverflowClip()) {
2179         IntSize offset = layer()->scrolledContentOffset();
2180         scrolledX -= offset.width();
2181         scrolledY -= offset.height();
2182     }
2183
2184     // 2. paint contents
2185     if (paintPhase != PaintPhaseSelfOutline) {
2186         if (hasColumns())
2187             paintColumnContents(paintInfo, scrolledX, scrolledY);
2188         else
2189             paintContents(paintInfo, scrolledX, scrolledY);
2190     }
2191
2192     // 3. paint selection
2193     // FIXME: Make this work with multi column layouts.  For now don't fill gaps.
2194     bool isPrinting = document()->printing();
2195     if (!isPrinting && !hasColumns())
2196         paintSelection(paintInfo, scrolledX, scrolledY); // Fill in gaps in selection on lines and between blocks.
2197
2198     // 4. paint floats.
2199     if (paintPhase == PaintPhaseFloat || paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip) {
2200         if (hasColumns())
2201             paintColumnContents(paintInfo, scrolledX, scrolledY, true);
2202         else
2203             paintFloats(paintInfo, scrolledX, scrolledY, paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip);
2204     }
2205
2206     // 5. paint outline.
2207     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseSelfOutline) && hasOutline() && style()->visibility() == VISIBLE)
2208         paintOutline(paintInfo.context, tx, ty, width(), height());
2209
2210     // 6. paint continuation outlines.
2211     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseChildOutlines)) {
2212         RenderInline* inlineCont = inlineElementContinuation();
2213         if (inlineCont && inlineCont->hasOutline() && inlineCont->style()->visibility() == VISIBLE) {
2214             RenderInline* inlineRenderer = toRenderInline(inlineCont->node()->renderer());
2215             RenderBlock* cb = containingBlock();
2216
2217             bool inlineEnclosedInSelfPaintingLayer = false;
2218             for (RenderBoxModelObject* box = inlineRenderer; box != cb; box = box->parent()->enclosingBoxModelObject()) {
2219                 if (box->hasSelfPaintingLayer()) {
2220                     inlineEnclosedInSelfPaintingLayer = true;
2221                     break;
2222                 }
2223             }
2224
2225             if (!inlineEnclosedInSelfPaintingLayer)
2226                 cb->addContinuationWithOutline(inlineRenderer);
2227             else if (!inlineRenderer->firstLineBox())
2228                 inlineRenderer->paintOutline(paintInfo.context, tx - x() + inlineRenderer->containingBlock()->x(),
2229                                              ty - y() + inlineRenderer->containingBlock()->y());
2230         }
2231         paintContinuationOutlines(paintInfo, tx, ty);
2232     }
2233
2234     // 7. paint caret.
2235     // If the caret's node's render object's containing block is this block, and the paint action is PaintPhaseForeground,
2236     // then paint the caret.
2237     if (paintPhase == PaintPhaseForeground) {        
2238         paintCaret(paintInfo, scrolledX, scrolledY, CursorCaret);
2239         paintCaret(paintInfo, scrolledX, scrolledY, DragCaret);
2240     }
2241 }
2242
2243 void RenderBlock::paintFloats(PaintInfo& paintInfo, int tx, int ty, bool preservePhase)
2244 {
2245     if (!m_floatingObjects)
2246         return;
2247
2248     FloatingObject* r;
2249     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2250     for (; (r = it.current()); ++it) {
2251         // Only paint the object if our m_shouldPaint flag is set.
2252         if (r->m_shouldPaint && !r->m_renderer->hasSelfPaintingLayer()) {
2253             PaintInfo currentPaintInfo(paintInfo);
2254             currentPaintInfo.phase = preservePhase ? paintInfo.phase : PaintPhaseBlockBackground;
2255             int currentTX = tx + r->m_left - r->m_renderer->x() + r->m_renderer->marginLeft();
2256             int currentTY = ty + r->m_top - r->m_renderer->y() + r->m_renderer->marginTop();
2257             r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
2258             if (!preservePhase) {
2259                 currentPaintInfo.phase = PaintPhaseChildBlockBackgrounds;
2260                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
2261                 currentPaintInfo.phase = PaintPhaseFloat;
2262                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
2263                 currentPaintInfo.phase = PaintPhaseForeground;
2264                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
2265                 currentPaintInfo.phase = PaintPhaseOutline;
2266                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
2267             }
2268         }
2269     }
2270 }
2271
2272 void RenderBlock::paintEllipsisBoxes(PaintInfo& paintInfo, int tx, int ty)
2273 {
2274     if (!paintInfo.shouldPaintWithinRoot(this) || !firstLineBox())
2275         return;
2276
2277     if (style()->visibility() == VISIBLE && paintInfo.phase == PaintPhaseForeground) {
2278         // We can check the first box and last box and avoid painting if we don't
2279         // intersect.
2280         int yPos = ty + firstLineBox()->y();
2281         int h = lastLineBox()->y() + lastLineBox()->height() - firstLineBox()->y();
2282         if (yPos >= paintInfo.rect.bottom() || yPos + h <= paintInfo.rect.y())
2283             return;
2284
2285         // See if our boxes intersect with the dirty rect.  If so, then we paint
2286         // them.  Note that boxes can easily overlap, so we can't make any assumptions
2287         // based off positions of our first line box or our last line box.
2288         for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2289             yPos = ty + curr->y();
2290             h = curr->height();
2291             if (curr->ellipsisBox() && yPos < paintInfo.rect.bottom() && yPos + h > paintInfo.rect.y())
2292                 curr->paintEllipsisBox(paintInfo, tx, ty);
2293         }
2294     }
2295 }
2296
2297 RenderInline* RenderBlock::inlineElementContinuation() const
2298
2299     return m_continuation && m_continuation->isInline() ? toRenderInline(m_continuation) : 0;
2300 }
2301
2302 RenderBlock* RenderBlock::blockElementContinuation() const
2303 {
2304     if (!m_continuation || m_continuation->isInline())
2305         return 0;
2306     RenderBlock* nextContinuation = toRenderBlock(m_continuation);
2307     if (nextContinuation->isAnonymousBlock())
2308         return nextContinuation->blockElementContinuation();
2309     return nextContinuation;
2310 }
2311     
2312 static ContinuationOutlineTableMap* continuationOutlineTable()
2313 {
2314     DEFINE_STATIC_LOCAL(ContinuationOutlineTableMap, table, ());
2315     return &table;
2316 }
2317
2318 void RenderBlock::addContinuationWithOutline(RenderInline* flow)
2319 {
2320     // We can't make this work if the inline is in a layer.  We'll just rely on the broken
2321     // way of painting.
2322     ASSERT(!flow->layer() && !flow->isInlineElementContinuation());
2323     
2324     ContinuationOutlineTableMap* table = continuationOutlineTable();
2325     ListHashSet<RenderInline*>* continuations = table->get(this);
2326     if (!continuations) {
2327         continuations = new ListHashSet<RenderInline*>;
2328         table->set(this, continuations);
2329     }
2330     
2331     continuations->add(flow);
2332 }
2333
2334 void RenderBlock::paintContinuationOutlines(PaintInfo& info, int tx, int ty)
2335 {
2336     ContinuationOutlineTableMap* table = continuationOutlineTable();
2337     if (table->isEmpty())
2338         return;
2339         
2340     ListHashSet<RenderInline*>* continuations = table->get(this);
2341     if (!continuations)
2342         return;
2343         
2344     // Paint each continuation outline.
2345     ListHashSet<RenderInline*>::iterator end = continuations->end();
2346     for (ListHashSet<RenderInline*>::iterator it = continuations->begin(); it != end; ++it) {
2347         // Need to add in the coordinates of the intervening blocks.
2348         RenderInline* flow = *it;
2349         RenderBlock* block = flow->containingBlock();
2350         for ( ; block && block != this; block = block->containingBlock()) {
2351             tx += block->x();
2352             ty += block->y();
2353         }
2354         ASSERT(block);   
2355         flow->paintOutline(info.context, tx, ty);
2356     }
2357     
2358     // Delete
2359     delete continuations;
2360     table->remove(this);
2361 }
2362
2363 bool RenderBlock::shouldPaintSelectionGaps() const
2364 {
2365     return selectionState() != SelectionNone && style()->visibility() == VISIBLE && isSelectionRoot();
2366 }
2367
2368 bool RenderBlock::isSelectionRoot() const
2369 {
2370     if (!node())
2371         return false;
2372         
2373     // FIXME: Eventually tables should have to learn how to fill gaps between cells, at least in simple non-spanning cases.
2374     if (isTable())
2375         return false;
2376         
2377     if (isBody() || isRoot() || hasOverflowClip() || isRelPositioned() ||
2378         isFloatingOrPositioned() || isTableCell() || isInlineBlockOrInlineTable() || hasTransform() ||
2379         hasReflection() || hasMask())
2380         return true;
2381     
2382     if (view() && view()->selectionStart()) {
2383         Node* startElement = view()->selectionStart()->node();
2384         if (startElement && startElement->rootEditableElement() == node())
2385             return true;
2386     }
2387     
2388     return false;
2389 }
2390
2391 GapRects RenderBlock::selectionGapRectsForRepaint(RenderBoxModelObject* repaintContainer)
2392 {
2393     ASSERT(!needsLayout());
2394
2395     if (!shouldPaintSelectionGaps())
2396         return GapRects();
2397
2398     // FIXME: this is broken with transforms
2399     TransformState transformState(TransformState::ApplyTransformDirection, FloatPoint());
2400     mapLocalToContainer(repaintContainer, false, false, transformState);
2401     IntPoint offsetFromRepaintContainer = roundedIntPoint(transformState.mappedPoint());
2402
2403     if (hasOverflowClip())
2404         offsetFromRepaintContainer -= layer()->scrolledContentOffset();
2405
2406     int lastTop = 0;
2407     int lastLeft = leftSelectionOffset(this, lastTop);
2408     int lastRight = rightSelectionOffset(this, lastTop);
2409     
2410     return fillSelectionGaps(this, offsetFromRepaintContainer.x(), offsetFromRepaintContainer.y(), offsetFromRepaintContainer.x(), offsetFromRepaintContainer.y(), lastTop, lastLeft, lastRight);
2411 }
2412
2413 void RenderBlock::paintSelection(PaintInfo& paintInfo, int tx, int ty)
2414 {
2415     if (shouldPaintSelectionGaps() && paintInfo.phase == PaintPhaseForeground) {
2416         int lastTop = 0;
2417         int lastLeft = leftSelectionOffset(this, lastTop);
2418         int lastRight = rightSelectionOffset(this, lastTop);
2419         paintInfo.context->save();
2420         IntRect gapRectsBounds = fillSelectionGaps(this, tx, ty, tx, ty, lastTop, lastLeft, lastRight, &paintInfo);
2421         if (!gapRectsBounds.isEmpty()) {
2422             if (RenderLayer* layer = enclosingLayer()) {
2423                 gapRectsBounds.move(IntSize(-tx, -ty));
2424                 if (!hasLayer()) {
2425                     FloatRect localBounds(gapRectsBounds);
2426                     gapRectsBounds = localToContainerQuad(localBounds, layer->renderer()).enclosingBoundingBox();
2427                     gapRectsBounds.move(layer->scrolledContentOffset());
2428                 }
2429                 layer->addBlockSelectionGapsBounds(gapRectsBounds);
2430             }
2431         }
2432         paintInfo.context->restore();
2433     }
2434 }
2435
2436 #ifndef BUILDING_ON_TIGER
2437 static void clipOutPositionedObjects(const PaintInfo* paintInfo, int tx, int ty, RenderBlock::PositionedObjectsListHashSet* positionedObjects)
2438 {
2439     if (!positionedObjects)
2440         return;
2441     
2442     RenderBlock::PositionedObjectsListHashSet::const_iterator end = positionedObjects->end();
2443     for (RenderBlock::PositionedObjectsListHashSet::const_iterator it = positionedObjects->begin(); it != end; ++it) {
2444         RenderBox* r = *it;
2445         paintInfo->context->clipOut(IntRect(tx + r->x(), ty + r->y(), r->width(), r->height()));
2446     }
2447 }
2448 #endif
2449
2450 GapRects RenderBlock::fillSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty,
2451                                         int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
2452 {
2453 #ifndef BUILDING_ON_TIGER
2454     // IMPORTANT: Callers of this method that intend for painting to happen need to do a save/restore.
2455     // Clip out floating and positioned objects when painting selection gaps.
2456     if (paintInfo) {
2457         // Note that we don't clip out overflow for positioned objects.  We just stick to the border box.
2458         clipOutPositionedObjects(paintInfo, tx, ty, m_positionedObjects);
2459         if (isBody() || isRoot()) // The <body> must make sure to examine its containingBlock's positioned objects.
2460             for (RenderBlock* cb = containingBlock(); cb && !cb->isRenderView(); cb = cb->containingBlock())
2461                 clipOutPositionedObjects(paintInfo, cb->x(), cb->y(), cb->m_positionedObjects);
2462         if (m_floatingObjects) {
2463             for (DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects); it.current(); ++it) {
2464                 FloatingObject* r = it.current();
2465                 paintInfo->context->clipOut(IntRect(tx + r->m_left + r->m_renderer->marginLeft(), 
2466                                                     ty + r->m_top + r->m_renderer->marginTop(),
2467                                                     r->m_renderer->width(), r->m_renderer->height()));
2468             }
2469         }
2470     }
2471 #endif
2472
2473     // 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
2474     // fixed).
2475     GapRects result;
2476     if (!isBlockFlow()) // FIXME: Make multi-column selection gap filling work someday.
2477         return result;
2478
2479     if (hasColumns() || hasTransform() || style()->columnSpan()) {
2480         // FIXME: We should learn how to gap fill multiple columns and transforms eventually.
2481         lastTop = (ty - blockY) + height();
2482         lastLeft = leftSelectionOffset(rootBlock, height());
2483         lastRight = rightSelectionOffset(rootBlock, height());
2484         return result;
2485     }
2486
2487     if (childrenInline())
2488         result = fillInlineSelectionGaps(rootBlock, blockX, blockY, tx, ty, lastTop, lastLeft, lastRight, paintInfo);
2489     else
2490         result = fillBlockSelectionGaps(rootBlock, blockX, blockY, tx, ty, lastTop, lastLeft, lastRight, paintInfo);
2491
2492     // Go ahead and fill the vertical gap all the way to the bottom of our block if the selection extends past our block.
2493     if (rootBlock == this && (selectionState() != SelectionBoth && selectionState() != SelectionEnd))
2494         result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight, ty + height(),
2495                                                     rootBlock, blockX, blockY, paintInfo));
2496     return result;
2497 }
2498
2499 GapRects RenderBlock::fillInlineSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty, 
2500                                               int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
2501 {
2502     GapRects result;
2503
2504     bool containsStart = selectionState() == SelectionStart || selectionState() == SelectionBoth;
2505
2506     if (!firstLineBox()) {
2507         if (containsStart) {
2508             // Go ahead and update our lastY to be the bottom of the block.  <hr>s or empty blocks with height can trip this
2509             // case.
2510             lastTop = (ty - blockY) + height();
2511             lastLeft = leftSelectionOffset(rootBlock, height());
2512             lastRight = rightSelectionOffset(rootBlock, height());
2513         }
2514         return result;
2515     }
2516
2517     RootInlineBox* lastSelectedLine = 0;
2518     RootInlineBox* curr;
2519     for (curr = firstRootBox(); curr && !curr->hasSelectedChildren(); curr = curr->nextRootBox()) { }
2520
2521     // Now paint the gaps for the lines.
2522     for (; curr && curr->hasSelectedChildren(); curr = curr->nextRootBox()) {
2523         int selTop =  curr->selectionTop();
2524         int selHeight = curr->selectionHeight();
2525
2526         if (!containsStart && !lastSelectedLine &&
2527             selectionState() != SelectionStart && selectionState() != SelectionBoth)
2528             result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight, ty + selTop,
2529                                                         rootBlock, blockX, blockY, paintInfo));
2530
2531         if (!paintInfo || (ty + selTop < paintInfo->rect.bottom() && ty + selTop + selHeight > paintInfo->rect.y()))
2532             result.unite(curr->fillLineSelectionGap(selTop, selHeight, rootBlock, blockX, blockY, tx, ty, paintInfo));
2533
2534         lastSelectedLine = curr;
2535     }
2536
2537     if (containsStart && !lastSelectedLine)
2538         // VisibleSelection must start just after our last line.
2539         lastSelectedLine = lastRootBox();
2540
2541     if (lastSelectedLine && selectionState() != SelectionEnd && selectionState() != SelectionBoth) {
2542         // Go ahead and update our lastY to be the bottom of the last selected line.
2543         lastTop = (ty - blockY) + lastSelectedLine->selectionBottom();
2544         lastLeft = leftSelectionOffset(rootBlock, lastSelectedLine->selectionBottom());
2545         lastRight = rightSelectionOffset(rootBlock, lastSelectedLine->selectionBottom());
2546     }
2547     return result;
2548 }
2549
2550 GapRects RenderBlock::fillBlockSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty,
2551                                              int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
2552 {
2553     GapRects result;
2554
2555     // Go ahead and jump right to the first block child that contains some selected objects.
2556     RenderBox* curr;
2557     for (curr = firstChildBox(); curr && curr->selectionState() == SelectionNone; curr = curr->nextSiblingBox()) { }
2558
2559     for (bool sawSelectionEnd = false; curr && !sawSelectionEnd; curr = curr->nextSiblingBox()) {
2560         SelectionState childState = curr->selectionState();
2561         if (childState == SelectionBoth || childState == SelectionEnd)
2562             sawSelectionEnd = true;
2563
2564         if (curr->isFloatingOrPositioned())
2565             continue; // We must be a normal flow object in order to even be considered.
2566
2567         if (curr->isRelPositioned() && curr->hasLayer()) {
2568             // If the relposition offset is anything other than 0, then treat this just like an absolute positioned element.
2569             // Just disregard it completely.
2570             IntSize relOffset = curr->layer()->relativePositionOffset();
2571             if (relOffset.width() || relOffset.height())
2572                 continue;
2573         }
2574
2575         bool paintsOwnSelection = curr->shouldPaintSelectionGaps() || curr->isTable(); // FIXME: Eventually we won't special-case table like this.
2576         bool fillBlockGaps = paintsOwnSelection || (curr->canBeSelectionLeaf() && childState != SelectionNone);
2577         if (fillBlockGaps) {
2578             // We need to fill the vertical gap above this object.
2579             if (childState == SelectionEnd || childState == SelectionInside)
2580                 // Fill the gap above the object.
2581                 result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight, 
2582                                                             ty + curr->y(), rootBlock, blockX, blockY, paintInfo));
2583
2584             // 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*
2585             // our object.  We know this if the selection did not end inside our object.
2586             if (paintsOwnSelection && (childState == SelectionStart || sawSelectionEnd))
2587                 childState = SelectionNone;
2588
2589             // Fill side gaps on this object based off its state.
2590             bool leftGap, rightGap;
2591             getHorizontalSelectionGapInfo(childState, leftGap, rightGap);
2592
2593             if (leftGap)
2594                 result.uniteLeft(fillLeftSelectionGap(this, curr->x(), curr->y(), curr->height(), rootBlock, blockX, blockY, tx, ty, paintInfo));
2595             if (rightGap)
2596                 result.uniteRight(fillRightSelectionGap(this, curr->x() + curr->width(), curr->y(), curr->height(), rootBlock, blockX, blockY, tx, ty, paintInfo));
2597
2598             // Update lastTop to be just underneath the object.  lastLeft and lastRight extend as far as
2599             // they can without bumping into floating or positioned objects.  Ideally they will go right up
2600             // to the border of the root selection block.
2601             lastTop = (ty - blockY) + (curr->y() + curr->height());
2602             lastLeft = leftSelectionOffset(rootBlock, curr->y() + curr->height());
2603             lastRight = rightSelectionOffset(rootBlock, curr->y() + curr->height());
2604         } else if (childState != SelectionNone)
2605             // We must be a block that has some selected object inside it.  Go ahead and recur.
2606             result.unite(toRenderBlock(curr)->fillSelectionGaps(rootBlock, blockX, blockY, tx + curr->x(), ty + curr->y(), 
2607                                                                             lastTop, lastLeft, lastRight, paintInfo));
2608     }
2609     return result;
2610 }
2611
2612 IntRect RenderBlock::fillHorizontalSelectionGap(RenderObject* selObj, int xPos, int yPos, int width, int height, const PaintInfo* paintInfo)
2613 {
2614     if (width <= 0 || height <= 0)
2615         return IntRect();
2616     IntRect gapRect(xPos, yPos, width, height);
2617     if (paintInfo && selObj->style()->visibility() == VISIBLE)
2618         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor(), selObj->style()->colorSpace());
2619     return gapRect;
2620 }
2621
2622 IntRect RenderBlock::fillVerticalSelectionGap(int lastTop, int lastLeft, int lastRight, int bottomY, RenderBlock* rootBlock,
2623                                               int blockX, int blockY, const PaintInfo* paintInfo)
2624 {
2625     int top = blockY + lastTop;
2626     int height = bottomY - top;
2627     if (height <= 0)
2628         return IntRect();
2629
2630     // Get the selection offsets for the bottom of the gap
2631     int left = blockX + max(lastLeft, leftSelectionOffset(rootBlock, bottomY));
2632     int right = blockX + min(lastRight, rightSelectionOffset(rootBlock, bottomY));
2633     int width = right - left;
2634     if (width <= 0)
2635         return IntRect();
2636
2637     IntRect gapRect(left, top, width, height);
2638     if (paintInfo)
2639         paintInfo->context->fillRect(gapRect, selectionBackgroundColor(), style()->colorSpace());
2640     return gapRect;
2641 }
2642
2643 IntRect RenderBlock::fillLeftSelectionGap(RenderObject* selObj, int xPos, int yPos, int height, RenderBlock* rootBlock,
2644                                           int blockX, int /*blockY*/, int tx, int ty, const PaintInfo* paintInfo)
2645 {
2646     int top = yPos + ty;
2647     int left = blockX + max(leftSelectionOffset(rootBlock, yPos), leftSelectionOffset(rootBlock, yPos + height));
2648     int right = min(xPos + tx, blockX + min(rightSelectionOffset(rootBlock, yPos), rightSelectionOffset(rootBlock, yPos + height)));
2649     int width = right - left;
2650     if (width <= 0)
2651         return IntRect();
2652
2653     IntRect gapRect(left, top, width, height);
2654     if (paintInfo)
2655         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor(), selObj->style()->colorSpace());
2656     return gapRect;
2657 }
2658
2659 IntRect RenderBlock::fillRightSelectionGap(RenderObject* selObj, int xPos, int yPos, int height, RenderBlock* rootBlock,
2660                                            int blockX, int /*blockY*/, int tx, int ty, const PaintInfo* paintInfo)
2661 {
2662     int left = max(xPos + tx, blockX + max(leftSelectionOffset(rootBlock, yPos), leftSelectionOffset(rootBlock, yPos + height)));
2663     int top = yPos + ty;
2664     int right = blockX + min(rightSelectionOffset(rootBlock, yPos), rightSelectionOffset(rootBlock, yPos + height));
2665     int width = right - left;
2666     if (width <= 0)
2667         return IntRect();
2668
2669     IntRect gapRect(left, top, width, height);
2670     if (paintInfo)
2671         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor(), selObj->style()->colorSpace());
2672     return gapRect;
2673 }
2674
2675 void RenderBlock::getHorizontalSelectionGapInfo(SelectionState state, bool& leftGap, bool& rightGap)
2676 {
2677     bool ltr = style()->direction() == LTR;
2678     leftGap = (state == RenderObject::SelectionInside) ||
2679               (state == RenderObject::SelectionEnd && ltr) ||
2680               (state == RenderObject::SelectionStart && !ltr);
2681     rightGap = (state == RenderObject::SelectionInside) ||
2682                (state == RenderObject::SelectionStart && ltr) ||
2683                (state == RenderObject::SelectionEnd && !ltr);
2684 }
2685
2686 int RenderBlock::leftSelectionOffset(RenderBlock* rootBlock, int yPos)
2687 {
2688     int left = leftOffset(yPos, false);
2689     if (left == borderLeft() + paddingLeft()) {
2690         if (rootBlock != this)
2691             // The border can potentially be further extended by our containingBlock().
2692             return containingBlock()->leftSelectionOffset(rootBlock, yPos + y());
2693         return left;
2694     }
2695     else {
2696         RenderBlock* cb = this;
2697         while (cb != rootBlock) {
2698             left += cb->x();
2699             cb = cb->containingBlock();
2700         }
2701     }
2702     
2703     return left;
2704 }
2705
2706 int RenderBlock::rightSelectionOffset(RenderBlock* rootBlock, int yPos)
2707 {
2708     int right = rightOffset(yPos, false);
2709     if (right == (contentWidth() + (borderLeft() + paddingLeft()))) {
2710         if (rootBlock != this)
2711             // The border can potentially be further extended by our containingBlock().
2712             return containingBlock()->rightSelectionOffset(rootBlock, yPos + y());
2713         return right;
2714     }
2715     else {
2716         RenderBlock* cb = this;
2717         while (cb != rootBlock) {
2718             right += cb->x();
2719             cb = cb->containingBlock();
2720         }
2721     }
2722     return right;
2723 }
2724
2725 void RenderBlock::insertPositionedObject(RenderBox* o)
2726 {
2727     // Create the list of special objects if we don't aleady have one
2728     if (!m_positionedObjects)
2729         m_positionedObjects = new PositionedObjectsListHashSet;
2730
2731     m_positionedObjects->add(o);
2732 }
2733
2734 void RenderBlock::removePositionedObject(RenderBox* o)
2735 {
2736     if (m_positionedObjects)
2737         m_positionedObjects->remove(o);
2738 }
2739
2740 void RenderBlock::removePositionedObjects(RenderBlock* o)
2741 {
2742     if (!m_positionedObjects)
2743         return;
2744     
2745     RenderBox* r;
2746     
2747     Iterator end = m_positionedObjects->end();
2748     
2749     Vector<RenderBox*, 16> deadObjects;
2750
2751     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2752         r = *it;
2753         if (!o || r->isDescendantOf(o)) {
2754             if (o)
2755                 r->setChildNeedsLayout(true, false);
2756             
2757             // It is parent blocks job to add positioned child to positioned objects list of its containing block
2758             // Parent layout needs to be invalidated to ensure this happens.
2759             RenderObject* p = r->parent();
2760             while (p && !p->isRenderBlock())
2761                 p = p->parent();
2762             if (p)
2763                 p->setChildNeedsLayout(true);
2764             
2765             deadObjects.append(r);
2766         }
2767     }
2768     
2769     for (unsigned i = 0; i < deadObjects.size(); i++)
2770         m_positionedObjects->remove(deadObjects.at(i));
2771 }
2772
2773 void RenderBlock::insertFloatingObject(RenderBox* o)
2774 {
2775     ASSERT(o->isFloating());
2776
2777     // Create the list of special objects if we don't aleady have one
2778     if (!m_floatingObjects) {
2779         m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
2780         m_floatingObjects->setAutoDelete(true);
2781     } else {
2782         // Don't insert the object again if it's already in the list
2783         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2784         FloatingObject* f;
2785         while ( (f = it.current()) ) {
2786             if (f->m_renderer == o) return;
2787             ++it;
2788         }
2789     }
2790
2791     // Create the special object entry & append it to the list
2792
2793     o->layoutIfNeeded();
2794
2795     FloatingObject* newObj = new FloatingObject(o->style()->floating() == FLEFT ? FloatingObject::FloatLeft : FloatingObject::FloatRight);
2796
2797     newObj->m_top = -1;
2798     newObj->m_bottom = -1;
2799     newObj->m_width = o->width() + o->marginLeft() + o->marginRight();
2800     newObj->m_shouldPaint = !o->hasSelfPaintingLayer(); // If a layer exists, the float will paint itself.  Otherwise someone else will.
2801     newObj->m_isDescendant = true;
2802     newObj->m_renderer = o;
2803
2804     m_floatingObjects->append(newObj);
2805 }
2806
2807 void RenderBlock::removeFloatingObject(RenderBox* o)
2808 {
2809     if (m_floatingObjects) {
2810         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2811         while (it.current()) {
2812             if (it.current()->m_renderer == o) {
2813                 if (childrenInline()) {
2814                     int bottom = it.current()->m_bottom;
2815                     // Special-case zero- and less-than-zero-height floats: those don't touch
2816                     // the line that they're on, but it still needs to be dirtied. This is
2817                     // accomplished by pretending they have a height of 1.
2818                     bottom = max(bottom, it.current()->m_top + 1);
2819                     markLinesDirtyInVerticalRange(0, bottom);
2820                 }
2821                 m_floatingObjects->removeRef(it.current());
2822             }
2823             ++it;
2824         }
2825     }
2826 }
2827
2828 bool RenderBlock::positionNewFloats()
2829 {
2830     if (!m_floatingObjects)
2831         return false;
2832     
2833     FloatingObject* f = m_floatingObjects->last();
2834
2835     // If all floats have already been positioned, then we have no work to do.
2836     if (!f || f->m_top != -1)
2837         return false;
2838
2839     // Move backwards through our floating object list until we find a float that has
2840     // already been positioned.  Then we'll be able to move forward, positioning all of
2841     // the new floats that need it.
2842     FloatingObject* lastFloat = m_floatingObjects->getPrev();
2843     while (lastFloat && lastFloat->m_top == -1) {
2844         f = m_floatingObjects->prev();
2845         lastFloat = m_floatingObjects->getPrev();
2846     }
2847
2848     int y = height();
2849     
2850     // The float cannot start above the y position of the last positioned float.
2851     if (lastFloat)
2852         y = max(lastFloat->m_top, y);
2853
2854     // Now walk through the set of unpositioned floats and place them.
2855     while (f) {
2856         // The containing block is responsible for positioning floats, so if we have floats in our
2857         // list that come from somewhere else, do not attempt to position them.
2858         if (f->m_renderer->containingBlock() != this) {
2859             f = m_floatingObjects->next();
2860             continue;
2861         }
2862
2863         RenderBox* o = f->m_renderer;
2864         int _height = o->height() + o->marginTop() + o->marginBottom();
2865
2866         int ro = rightOffset(); // Constant part of right offset.
2867         int lo = leftOffset(); // Constat part of left offset.
2868         int fwidth = f->m_width; // The width we look for.
2869         if (ro - lo < fwidth)
2870             fwidth = ro - lo; // Never look for more than what will be available.
2871         
2872         IntRect oldRect(o->x(), o->y() , o->width(), o->height());
2873         
2874         if (o->style()->clear() & CLEFT)
2875             y = max(leftBottom(), y);
2876         if (o->style()->clear() & CRIGHT)
2877             y = max(rightBottom(), y);
2878
2879         if (o->style()->floating() == FLEFT) {
2880             int heightRemainingLeft = 1;
2881             int heightRemainingRight = 1;
2882             int fx = leftRelOffset(y, lo, false, &heightRemainingLeft);
2883             while (rightRelOffset(y, ro, false, &heightRemainingRight)-fx < fwidth) {
2884                 y += min(heightRemainingLeft, heightRemainingRight);
2885                 fx = leftRelOffset(y, lo, false, &heightRemainingLeft);
2886             }
2887             fx = max(0, fx);
2888             f->m_left = fx;
2889             o->setLocation(fx + o->marginLeft(), y + o->marginTop());
2890         } else {
2891             int heightRemainingLeft = 1;
2892             int heightRemainingRight = 1;
2893             int fx = rightRelOffset(y, ro, false, &heightRemainingRight);
2894             while (fx - leftRelOffset(y, lo, false, &heightRemainingLeft) < fwidth) {
2895                 y += min(heightRemainingLeft, heightRemainingRight);
2896                 fx = rightRelOffset(y, ro, false, &heightRemainingRight);
2897             }
2898             f->m_left = fx - f->m_width;
2899             o->setLocation(fx - o->marginRight() - o->width(), y + o->marginTop());
2900         }
2901
2902         f->m_top = y;
2903         f->m_bottom = f->m_top + _height;
2904
2905         // If the child moved, we have to repaint it.
2906         if (o->checkForRepaintDuringLayout())
2907             o->repaintDuringLayoutIfMoved(oldRect);
2908
2909         f = m_floatingObjects->next();
2910     }
2911     return true;
2912 }
2913
2914 void RenderBlock::newLine(EClear clear)
2915 {
2916     positionNewFloats();
2917     // set y position
2918     int newY = 0;
2919     switch (clear)
2920     {
2921         case CLEFT:
2922             newY = leftBottom();
2923             break;
2924         case CRIGHT:
2925             newY = rightBottom();
2926             break;
2927         case CBOTH:
2928             newY = floatBottom();
2929         default:
2930             break;
2931     }
2932     if (height() < newY)
2933         setHeight(newY);
2934 }
2935
2936 void RenderBlock::addPercentHeightDescendant(RenderBox* descendant)
2937 {
2938     if (!gPercentHeightDescendantsMap) {
2939         gPercentHeightDescendantsMap = new PercentHeightDescendantsMap;
2940         gPercentHeightContainerMap = new PercentHeightContainerMap;
2941     }
2942
2943     HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->get(this);
2944     if (!descendantSet) {
2945         descendantSet = new HashSet<RenderBox*>;
2946         gPercentHeightDescendantsMap->set(this, descendantSet);
2947     }
2948     bool added = descendantSet->add(descendant).second;
2949     if (!added) {
2950         ASSERT(gPercentHeightContainerMap->get(descendant));
2951         ASSERT(gPercentHeightContainerMap->get(descendant)->contains(this));
2952         return;
2953     }
2954
2955     HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->get(descendant);
2956     if (!containerSet) {
2957         containerSet = new HashSet<RenderBlock*>;
2958         gPercentHeightContainerMap->set(descendant, containerSet);
2959     }
2960     ASSERT(!containerSet->contains(this));
2961     containerSet->add(this);
2962 }
2963
2964 void RenderBlock::removePercentHeightDescendant(RenderBox* descendant)
2965 {
2966     if (!gPercentHeightContainerMap)
2967         return;
2968
2969     HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->take(descendant);
2970     if (!containerSet)
2971         return;
2972
2973     HashSet<RenderBlock*>::iterator end = containerSet->end();
2974     for (HashSet<RenderBlock*>::iterator it = containerSet->begin(); it != end; ++it) {
2975         RenderBlock* container = *it;
2976         HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->get(container);
2977         ASSERT(descendantSet);
2978         if (!descendantSet)
2979             continue;
2980         ASSERT(descendantSet->contains(descendant));
2981         descendantSet->remove(descendant);
2982         if (descendantSet->isEmpty()) {
2983             gPercentHeightDescendantsMap->remove(container);
2984             delete descendantSet;
2985         }
2986     }
2987
2988     delete containerSet;
2989 }
2990
2991 HashSet<RenderBox*>* RenderBlock::percentHeightDescendants() const
2992 {
2993     return gPercentHeightDescendantsMap ? gPercentHeightDescendantsMap->get(this) : 0;
2994 }
2995
2996 int RenderBlock::leftOffset() const
2997 {
2998     return borderLeft() + paddingLeft();
2999 }
3000
3001 int RenderBlock::leftRelOffset(int y, int fixedOffset, bool applyTextIndent, int* heightRemaining) const
3002 {
3003     int left = fixedOffset;
3004     if (m_floatingObjects) {
3005         if ( heightRemaining ) *heightRemaining = 1;
3006         FloatingObject* r;
3007         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3008         for ( ; (r = it.current()); ++it )
3009         {
3010             if (r->m_top <= y && r->m_bottom > y &&
3011                 r->type() == FloatingObject::FloatLeft &&
3012                 r->m_left + r->m_width > left) {
3013                 left = r->m_left + r->m_width;
3014                 if ( heightRemaining ) *heightRemaining = r->m_bottom - y;
3015             }
3016         }
3017     }
3018
3019     if (applyTextIndent && style()->direction() == LTR) {
3020         int cw = 0;
3021         if (style()->textIndent().isPercent())
3022             cw = containingBlock()->availableWidth();
3023         left += style()->textIndent().calcMinValue(cw);
3024     }
3025
3026     return left;
3027 }
3028
3029 int RenderBlock::rightOffset() const
3030 {
3031     return borderLeft() + paddingLeft() + availableWidth();
3032 }
3033
3034 int RenderBlock::rightRelOffset(int y, int fixedOffset, bool applyTextIndent, int* heightRemaining) const
3035 {
3036     int right = fixedOffset;
3037
3038     if (m_floatingObjects) {
3039         if (heightRemaining) *heightRemaining = 1;
3040         FloatingObject* r;
3041         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3042         for ( ; (r = it.current()); ++it )
3043         {
3044             if (r->m_top <= y && r->m_bottom > y &&
3045                 r->type() == FloatingObject::FloatRight &&
3046                 r->m_left < right) {
3047                 right = r->m_left;
3048                 if ( heightRemaining ) *heightRemaining = r->m_bottom - y;
3049             }
3050         }
3051     }
3052     
3053     if (applyTextIndent && style()->direction() == RTL) {
3054         int cw = 0;
3055         if (style()->textIndent().isPercent())
3056             cw = containingBlock()->availableWidth();
3057         right -= style()->textIndent().calcMinValue(cw);
3058     }
3059     
3060     return right;
3061 }
3062
3063 int
3064 RenderBlock::lineWidth(int y, bool firstLine) const
3065 {
3066     int result = rightOffset(y, firstLine) - leftOffset(y, firstLine);
3067     return (result < 0) ? 0 : result;
3068 }
3069
3070 int RenderBlock::nextFloatBottomBelow(int height) const
3071 {
3072     if (!m_floatingObjects)
3073         return 0;
3074
3075     int bottom = INT_MAX;
3076     FloatingObject* r;
3077     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3078     for ( ; (r = it.current()); ++it) {
3079         if (r->m_bottom > height)
3080             bottom = min(r->m_bottom, bottom);
3081     }
3082
3083     return bottom == INT_MAX ? 0 : bottom;
3084 }
3085
3086 int
3087 RenderBlock::floatBottom() const
3088 {
3089     if (!m_floatingObjects) return 0;
3090     int bottom = 0;
3091     FloatingObject* r;
3092     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3093     for ( ; (r = it.current()); ++it )
3094         if (r->m_bottom>bottom)
3095             bottom = r->m_bottom;
3096     return bottom;
3097 }
3098
3099 int RenderBlock::lowestPosition(bool includeOverflowInterior, bool includeSelf) const
3100 {
3101     int bottom = includeSelf && width() > 0 ? height() : 0;
3102
3103     if (!includeOverflowInterior && (hasOverflowClip() || hasControlClip()))
3104         return bottom;
3105
3106     if (!firstChild() && (!width() || !height()))
3107         return bottom;
3108     
3109     if (!hasColumns()) {
3110         // FIXME: Come up with a way to use the layer tree to avoid visiting all the kids.
3111         // For now, we have to descend into all the children, since we may have a huge abs div inside
3112         // a tiny rel div buried somewhere deep in our child tree.  In this case we have to get to
3113         // the abs div.
3114         // See the last test case in https://bugs.webkit.org/show_bug.cgi?id=9314 for why this is a problem.
3115         // For inline children, we miss relative positioned boxes that might be buried inside <span>s.
3116         for (RenderObject* c = firstChild(); c; c = c->nextSibling()) {
3117             if (!c->isFloatingOrPositioned() && c->isBox()) {
3118                 RenderBox* childBox = toRenderBox(c);
3119                 bottom = max(bottom, childBox->y() + childBox->lowestPosition(false));
3120             }
3121         }
3122     }
3123
3124     if (includeSelf && isRelPositioned())
3125         bottom += relativePositionOffsetY();     
3126     if (!includeOverflowInterior && hasOverflowClip())
3127         return bottom;
3128
3129     int relativeOffset = includeSelf && isRelPositioned() ? relativePositionOffsetY() : 0;
3130
3131     if (includeSelf)
3132         bottom = max(bottom, bottomLayoutOverflow() + relativeOffset);
3133         
3134     if (m_positionedObjects) {
3135         RenderBox* r;
3136         Iterator end = m_positionedObjects->end();
3137         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
3138             r = *it;
3139             // Fixed positioned objects do not scroll and thus should not constitute
3140             // part of the lowest position.
3141             if (r->style()->position() != FixedPosition) {
3142                 // FIXME: Should work for overflow sections too.
3143                 // If a positioned object lies completely to the left of the root it will be unreachable via scrolling.
3144                 // Therefore we should not allow it to contribute to the lowest position.
3145                 if (!isRenderView() || r->x() + r->width() > 0 || r->x() + r->rightmostPosition(false) > 0) {
3146                     int lp = r->y() + r->lowestPosition(false);
3147                     bottom = max(bottom, lp + relativeOffset);
3148                 }
3149             }
3150         }
3151     }
3152
3153     if (hasColumns()) {
3154         Vector<IntRect>* colRects = columnRects();
3155         for (unsigned i = 0; i < colRects->size(); i++)
3156             bottom = max(bottom, colRects->at(i).bottom() + relativeOffset);
3157         return bottom;
3158     }
3159
3160     if (m_floatingObjects) {
3161         FloatingObject* r;
3162         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3163         for ( ; (r = it.current()); ++it ) {
3164             if (r->m_shouldPaint || r->m_renderer->hasSelfPaintingLayer()) {
3165                 int lp = r->m_top + r->m_renderer->marginTop() + r->m_renderer->lowestPosition(false);
3166                 bottom = max(bottom, lp + relativeOffset);
3167             }
3168         }
3169     }
3170
3171     if (!includeSelf) {
3172         bottom = max(bottom, borderTop() + paddingTop() + paddingBottom() + relativeOffset);
3173         if (childrenInline()) {
3174             if (lastRootBox()) {
3175                 int childBottomEdge = lastRootBox()->selectionBottom();
3176                 bottom = max(bottom, childBottomEdge + paddingBottom() + relativeOffset);
3177             }
3178         } else {
3179             // Find the last normal flow child.
3180             RenderBox* currBox = lastChildBox();
3181             while (currBox && currBox->isFloatingOrPositioned())
3182                 currBox = currBox->previousSiblingBox();
3183             if (currBox) {
3184                 int childBottomEdge = currBox->y() + currBox->height() + currBox->collapsedMarginBottom();
3185                 bottom = max(bottom, childBottomEdge + paddingBottom() + relativeOffset);
3186             }
3187         }
3188     }
3189     
3190     return bottom;
3191 }
3192
3193 int RenderBlock::rightmostPosition(bool includeOverflowInterior, bool includeSelf) const
3194 {
3195     int right = includeSelf && height() > 0 ? width() : 0;
3196
3197     if (!includeOverflowInterior && (hasOverflowClip() || hasControlClip()))
3198         return right;
3199
3200     if (!firstChild() && (!width() || !height()))
3201         return right;
3202
3203     if (!hasColumns()) {
3204         // FIXME: Come up with a way to use the layer tree to avoid visiting all the kids.
3205         // For now, we have to descend into all the children, since we may have a huge abs div inside
3206         // a tiny rel div buried somewhere deep in our child tree.  In this case we have to get to
3207         // the abs div.
3208         for (RenderObject* c = firstChild(); c; c = c->nextSibling()) {
3209             if (!c->isFloatingOrPositioned() && c->isBox()) {
3210                 RenderBox* childBox = toRenderBox(c);
3211                 right = max(right, childBox->x() + childBox->rightmostPosition(false));
3212             }
3213         }
3214     }
3215
3216     if (includeSelf && isRelPositioned())
3217         right += relativePositionOffsetX();
3218
3219     if (!includeOverflowInterior && hasOverflowClip())
3220         return right;
3221
3222     int relativeOffset = includeSelf && isRelPositioned() ? relativePositionOffsetX() : 0;
3223
3224     if (includeSelf)
3225         right = max(right, rightLayoutOverflow() + relativeOffset);
3226
3227     if (m_positionedObjects) {
3228         RenderBox* r;
3229         Iterator end = m_positionedObjects->end();
3230         for (Iterator it = m_positionedObjects->begin() ; it != end; ++it) {
3231             r = *it;
3232             // Fixed positioned objects do not scroll and thus should not constitute
3233             // part of the rightmost position.
3234             if (r->style()->position() != FixedPosition) {
3235                 // FIXME: Should work for overflow sections too.
3236                 // If a positioned object lies completely above the root it will be unreachable via scrolling.
3237                 // Therefore we should not allow it to contribute to the rightmost position.
3238                 if (!isRenderView() || r->y() + r->height() > 0 || r->y() + r->lowestPosition(false) > 0) {
3239                     int rp = r->x() + r->rightmostPosition(false);
3240                     right = max(right, rp + relativeOffset);
3241                 }
3242             }
3243         }
3244     }
3245
3246     if (hasColumns()) {
3247         // This only matters for LTR
3248         if (style()->direction() == LTR)
3249             right = max(columnRects()->last().right() + relativeOffset, right);
3250         return right;
3251     }
3252
3253     if (m_floatingObjects) {
3254         FloatingObject* r;
3255         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3256         for ( ; (r = it.current()); ++it ) {
3257             if (r->m_shouldPaint || r->m_renderer->hasSelfPaintingLayer()) {
3258                 int rp = r->m_left + r->m_renderer->marginLeft() + r->m_renderer->rightmostPosition(false);
3259                 right = max(right, rp + relativeOffset);
3260             }
3261         }
3262     }
3263
3264     if (!includeSelf) {
3265         right = max(right, borderLeft() + paddingLeft() + paddingRight() + relativeOffset);
3266         if (childrenInline()) {
3267             for (InlineFlowBox* currBox = firstLineBox(); currBox; currBox = currBox->nextLineBox()) {
3268                 int childRightEdge = currBox->x() + currBox->width();
3269                 
3270                 // If this node is a root editable element, then the rightmostPosition should account for a caret at the end.
3271                 // FIXME: Need to find another way to do this, since scrollbars could show when we don't want them to.
3272                 if (node() && node()->isContentEditable() && node() == node()->rootEditableElement() && style()->direction() == LTR && !paddingRight())
3273                     childRightEdge += 1;
3274                 right = max(right, childRightEdge + paddingRight() + relativeOffset);
3275             }
3276         } else {
3277             // Walk all normal flow children.
3278             for (RenderBox* currBox = firstChildBox(); currBox; currBox = currBox->nextSiblingBox()) {
3279                 if (currBox->isFloatingOrPositioned())
3280                     continue;
3281                 int childRightEdge = currBox->x() + currBox->width() + currBox->marginRight();
3282                 right = max(right, childRightEdge + paddingRight() + relativeOffset);
3283             }
3284         }
3285     }
3286     
3287     return right;
3288 }
3289
3290 int RenderBlock::leftmostPosition(bool includeOverflowInterior, bool includeSelf) const
3291 {
3292     int left = includeSelf && height() > 0 ? 0 : width();
3293     
3294     if (!includeOverflowInterior && (hasOverflowClip() || hasControlClip()))
3295         return left;
3296
3297     if (!firstChild() && (!width() || !height()))
3298         return left;
3299
3300     if (!hasColumns()) {
3301         // FIXME: Come up with a way to use the layer tree to avoid visiting all the kids.
3302         // For now, we have to descend into all the children, since we may have a huge abs div inside
3303         // a tiny rel div buried&nb