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