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