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