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