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