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