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