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