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