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