Fix the line truncation function for Emerson so that at the far left setting of...
[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->setPos(box->xPos(), -500000);
263     }
264 }
265
266 void RenderBlock::removeChildrenFromLineBoxes()
267 {
268     // In the case where we do a collapse/merge from the destruction
269     // of a block in between two anonymous blocks with inlines (see removeChild in render_block.cpp),
270     // we have line boxes that need to have their parents nulled.
271     KHTMLAssert(!documentBeingDestroyed());
272     for (InlineFlowBox* box = m_firstLineBox; box; box = box->nextFlowBox())
273         for (InlineBox* child = box->firstChild(); child; child = child->nextOnLine())
274             child->remove();
275 }
276
277 void RenderBlock::removeChild(RenderObject *oldChild)
278 {
279     // If this child is a block, and if our previous and next siblings are
280     // both anonymous blocks with inline content, then we can go ahead and
281     // fold the inline content back together.
282     RenderObject* prev = oldChild->previousSibling();
283     RenderObject* next = oldChild->nextSibling();
284     bool mergedBlocks = false;
285     if (!documentBeingDestroyed() && !isInline() && !oldChild->isInline() && !oldChild->continuation() &&
286         prev && prev->isAnonymousBlock() && prev->childrenInline() &&
287         next && next->isAnonymousBlock() && next->childrenInline()) {
288         // Clean up the line box children inside |next|.
289         static_cast<RenderBlock*>(next)->removeChildrenFromLineBoxes();
290         
291         // Take all the children out of the |next| block and put them in
292         // the |prev| block.
293         RenderObject* o = next->firstChild();
294         while (o) {
295             RenderObject* no = o;
296             o = no->nextSibling();
297             prev->appendChildNode(next->removeChildNode(no));
298             no->setNeedsLayoutAndMinMaxRecalc();
299         }
300         prev->setNeedsLayoutAndMinMaxRecalc();
301
302         // Nuke the now-empty block.
303         next->detach();
304
305         mergedBlocks = true;
306     }
307
308     RenderFlow::removeChild(oldChild);
309
310     if (mergedBlocks && prev && !prev->previousSibling() && !prev->nextSibling()) {
311         // The remerge has knocked us down to containing only a single anonymous
312         // box.  We can go ahead and pull the content right back up into our
313         // box.
314         static_cast<RenderBlock*>(prev)->removeChildrenFromLineBoxes();
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.start().node();
1314         RenderObject *renderer = caretNode ? caretNode->renderer() : 0;
1315         if (renderer && (renderer == this || renderer->containingBlock() == this) && caretNode && caretNode->isContentEditable()) {
1316             document()->part()->paintCaret(i.p, i.r);
1317             document()->part()->paintDragCaret(i.p, i.r);
1318         }
1319     }
1320
1321 #ifdef BOX_DEBUG
1322     if ( style() && style()->visibility() == VISIBLE ) {
1323         if(isAnonymous())
1324             outlineBox(i.p, _tx, _ty, "green");
1325         if(isFloating())
1326             outlineBox(i.p, _tx, _ty, "yellow");
1327         else
1328             outlineBox(i.p, _tx, _ty);
1329     }
1330 #endif
1331 }
1332
1333 void RenderBlock::paintFloats(PaintInfo& i, int _tx, int _ty, bool paintSelection)
1334 {
1335     if (!m_floatingObjects)
1336         return;
1337
1338     FloatingObject* r;
1339     QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1340     for ( ; (r = it.current()); ++it) {
1341         // Only paint the object if our noPaint flag isn't set.
1342         if (!r->noPaint && !r->node->layer()) {
1343             PaintInfo info(i.p, i.r, paintSelection ? PaintActionSelection : PaintActionElementBackground, i.paintingRoot);
1344             int tx = _tx + r->left - r->node->xPos() + r->node->marginLeft();
1345             int ty = _ty + r->startY - r->node->yPos() + r->node->marginTop();
1346             r->node->paint(info, tx, ty);
1347             if (!paintSelection) {
1348                 info.phase = PaintActionChildBackgrounds;
1349                 r->node->paint(info, tx, ty);
1350                 info.phase = PaintActionFloat;
1351                 r->node->paint(info, tx, ty);
1352                 info.phase = PaintActionForeground;
1353                 r->node->paint(info, tx, ty);
1354                 info.phase = PaintActionOutline;
1355                 r->node->paint(info, tx, ty);
1356             }
1357         }
1358     }
1359 }
1360
1361 void RenderBlock::paintEllipsisBoxes(PaintInfo& i, int _tx, int _ty)
1362 {
1363     if (!shouldPaintWithinRoot(i) || !firstLineBox())
1364         return;
1365
1366     if (style()->visibility() == VISIBLE && i.phase == PaintActionForeground) {
1367         // We can check the first box and last box and avoid painting if we don't
1368         // intersect.
1369         int yPos = _ty + firstLineBox()->yPos();;
1370         int h = lastLineBox()->yPos() + lastLineBox()->height() - firstLineBox()->yPos();
1371         if( (yPos >= i.r.y() + i.r.height()) || (yPos + h <= i.r.y()))
1372             return;
1373
1374         // See if our boxes intersect with the dirty rect.  If so, then we paint
1375         // them.  Note that boxes can easily overlap, so we can't make any assumptions
1376         // based off positions of our first line box or our last line box.
1377         if (!isInlineFlow()) {
1378             for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
1379                 yPos = _ty + curr->yPos();
1380                 h = curr->height();
1381                 if (curr->ellipsisBox() && (yPos < i.r.y() + i.r.height()) && (yPos + h > i.r.y()))
1382                     curr->paintEllipsisBox(i, _tx, _ty);
1383             }
1384         }
1385     }
1386 }
1387
1388 void RenderBlock::insertPositionedObject(RenderObject *o)
1389 {
1390     // Create the list of special objects if we don't aleady have one
1391     if (!m_positionedObjects) {
1392         m_positionedObjects = new QPtrList<RenderObject>;
1393         m_positionedObjects->setAutoDelete(false);
1394     }
1395     else {
1396         // Don't insert the object again if it's already in the list
1397         QPtrListIterator<RenderObject> it(*m_positionedObjects);
1398         RenderObject* f;
1399         while ( (f = it.current()) ) {
1400             if (f == o) return;
1401             ++it;
1402         }
1403     }
1404
1405     m_positionedObjects->append(o);
1406 }
1407
1408 void RenderBlock::removePositionedObject(RenderObject *o)
1409 {
1410     if (m_positionedObjects) {
1411         QPtrListIterator<RenderObject> it(*m_positionedObjects);
1412         while (it.current()) {
1413             if (it.current() == o)
1414                 m_positionedObjects->removeRef(it.current());
1415             ++it;
1416         }
1417     }
1418 }
1419
1420 void RenderBlock::insertFloatingObject(RenderObject *o)
1421 {
1422     // Create the list of special objects if we don't aleady have one
1423     if (!m_floatingObjects) {
1424         m_floatingObjects = new QPtrList<FloatingObject>;
1425         m_floatingObjects->setAutoDelete(true);
1426     }
1427     else {
1428         // Don't insert the object again if it's already in the list
1429         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1430         FloatingObject* f;
1431         while ( (f = it.current()) ) {
1432             if (f->node == o) return;
1433             ++it;
1434         }
1435     }
1436
1437     // Create the special object entry & append it to the list
1438
1439     FloatingObject *newObj;
1440     if (o->isFloating()) {
1441         // floating object
1442         o->layoutIfNeeded();
1443
1444         if(o->style()->floating() == FLEFT)
1445             newObj = new FloatingObject(FloatingObject::FloatLeft);
1446         else
1447             newObj = new FloatingObject(FloatingObject::FloatRight);
1448
1449         newObj->startY = -1;
1450         newObj->endY = -1;
1451         newObj->width = o->width() + o->marginLeft() + o->marginRight();
1452     }
1453     else {
1454         // We should never get here, as insertFloatingObject() should only ever be called with floating
1455         // objects.
1456         KHTMLAssert(false);
1457         newObj = 0; // keep gcc's uninitialized variable warnings happy
1458     }
1459
1460     newObj->node = o;
1461
1462     m_floatingObjects->append(newObj);
1463 }
1464
1465 void RenderBlock::removeFloatingObject(RenderObject *o)
1466 {
1467     if (m_floatingObjects) {
1468         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1469         while (it.current()) {
1470             if (it.current()->node == o)
1471                 m_floatingObjects->removeRef(it.current());
1472             ++it;
1473         }
1474     }
1475 }
1476
1477 void RenderBlock::positionNewFloats()
1478 {
1479     if(!m_floatingObjects) return;
1480     FloatingObject *f = m_floatingObjects->getLast();
1481     if(!f || f->startY != -1) return;
1482     FloatingObject *lastFloat;
1483     while(1)
1484     {
1485         lastFloat = m_floatingObjects->prev();
1486         if (!lastFloat || lastFloat->startY != -1) {
1487             m_floatingObjects->next();
1488             break;
1489         }
1490         f = lastFloat;
1491     }
1492
1493
1494     int y = m_height;
1495
1496
1497     // the float can not start above the y position of the last positioned float.
1498     if(lastFloat && lastFloat->startY > y)
1499         y = lastFloat->startY;
1500
1501     while(f)
1502     {
1503         //skip elements copied from elsewhere and positioned elements
1504         if (f->node->containingBlock()!=this)
1505         {
1506             f = m_floatingObjects->next();
1507             continue;
1508         }
1509
1510         RenderObject *o = f->node;
1511         int _height = o->height() + o->marginTop() + o->marginBottom();
1512
1513         int ro = rightOffset(); // Constant part of right offset.
1514         int lo = leftOffset(); // Constat part of left offset.
1515         int fwidth = f->width; // The width we look for.
1516                                //kdDebug( 6040 ) << " Object width: " << fwidth << " available width: " << ro - lo << endl;
1517         if (ro - lo < fwidth)
1518             fwidth = ro - lo; // Never look for more than what will be available.
1519         
1520         int oldChildX = o->xPos();
1521         int oldChildY = o->yPos();
1522         
1523         if ( o->style()->clear() & CLEFT )
1524             y = kMax( leftBottom(), y );
1525         if ( o->style()->clear() & CRIGHT )
1526             y = kMax( rightBottom(), y );
1527
1528         if (o->style()->floating() == FLEFT)
1529         {
1530             int heightRemainingLeft = 1;
1531             int heightRemainingRight = 1;
1532             int fx = leftRelOffset(y,lo, false, &heightRemainingLeft);
1533             while (rightRelOffset(y,ro, false, &heightRemainingRight)-fx < fwidth)
1534             {
1535                 y += kMin( heightRemainingLeft, heightRemainingRight );
1536                 fx = leftRelOffset(y,lo, false, &heightRemainingLeft);
1537             }
1538             if (fx<0) fx=0;
1539             f->left = fx;
1540             //kdDebug( 6040 ) << "positioning left aligned float at (" << fx + o->marginLeft()  << "/" << y + o->marginTop() << ") fx=" << fx << endl;
1541             o->setPos(fx + o->marginLeft(), y + o->marginTop());
1542         }
1543         else
1544         {
1545             int heightRemainingLeft = 1;
1546             int heightRemainingRight = 1;
1547             int fx = rightRelOffset(y,ro, false, &heightRemainingRight);
1548             while (fx - leftRelOffset(y,lo, false, &heightRemainingLeft) < fwidth)
1549             {
1550                 y += kMin(heightRemainingLeft, heightRemainingRight);
1551                 fx = rightRelOffset(y,ro, false, &heightRemainingRight);
1552             }
1553             if (fx<f->width) fx=f->width;
1554             f->left = fx - f->width;
1555             //kdDebug( 6040 ) << "positioning right aligned float at (" << fx - o->marginRight() - o->width() << "/" << y + o->marginTop() << ")" << endl;
1556             o->setPos(fx - o->marginRight() - o->width(), y + o->marginTop());
1557         }
1558         f->startY = y;
1559         f->endY = f->startY + _height;
1560
1561         // If the child moved, we have to repaint it.
1562         if (o->checkForRepaintDuringLayout())
1563             o->repaintDuringLayoutIfMoved(oldChildX, oldChildY);
1564
1565         //kdDebug( 6040 ) << "floatingObject x/y= (" << f->left << "/" << f->startY << "-" << f->width << "/" << f->endY - f->startY << ")" << endl;
1566
1567         f = m_floatingObjects->next();
1568     }
1569 }
1570
1571 void RenderBlock::newLine()
1572 {
1573     positionNewFloats();
1574     // set y position
1575     int newY = 0;
1576     switch(m_clearStatus)
1577     {
1578         case CLEFT:
1579             newY = leftBottom();
1580             break;
1581         case CRIGHT:
1582             newY = rightBottom();
1583             break;
1584         case CBOTH:
1585             newY = floatBottom();
1586         default:
1587             break;
1588     }
1589     if(m_height < newY)
1590     {
1591         //      kdDebug( 6040 ) << "adjusting y position" << endl;
1592         m_height = newY;
1593     }
1594     m_clearStatus = CNONE;
1595 }
1596
1597 int
1598 RenderBlock::leftOffset() const
1599 {
1600     return borderLeft()+paddingLeft();
1601 }
1602
1603 int
1604 RenderBlock::leftRelOffset(int y, int fixedOffset, bool applyTextIndent,
1605                            int *heightRemaining ) const
1606 {
1607     int left = fixedOffset;
1608     if (m_floatingObjects) {
1609         if ( heightRemaining ) *heightRemaining = 1;
1610         FloatingObject* r;
1611         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1612         for ( ; (r = it.current()); ++it )
1613         {
1614             //kdDebug( 6040 ) <<(void *)this << " left: sy, ey, x, w " << r->startY << "," << r->endY << "," << r->left << "," << r->width << " " << endl;
1615             if (r->startY <= y && r->endY > y &&
1616                 r->type == FloatingObject::FloatLeft &&
1617                 r->left + r->width > left) {
1618                 left = r->left + r->width;
1619                 if ( heightRemaining ) *heightRemaining = r->endY - y;
1620             }
1621         }
1622     }
1623
1624     if (applyTextIndent && m_firstLine && style()->direction() == LTR) {
1625         int cw=0;
1626         if (style()->textIndent().isPercent())
1627             cw = containingBlock()->contentWidth();
1628         left += style()->textIndent().minWidth(cw);
1629     }
1630
1631     //kdDebug( 6040 ) << "leftOffset(" << y << ") = " << left << endl;
1632     return left;
1633 }
1634
1635 int
1636 RenderBlock::rightOffset() const
1637 {
1638     int right = m_width - borderRight() - paddingRight();
1639     if (includeScrollbarSize())
1640         right -= m_layer->verticalScrollbarWidth();
1641     return right;
1642 }
1643
1644 int
1645 RenderBlock::rightRelOffset(int y, int fixedOffset, bool applyTextIndent,
1646                             int *heightRemaining ) const
1647 {
1648     int right = fixedOffset;
1649
1650     if (m_floatingObjects) {
1651         if (heightRemaining) *heightRemaining = 1;
1652         FloatingObject* r;
1653         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1654         for ( ; (r = it.current()); ++it )
1655         {
1656             //kdDebug( 6040 ) << "right: sy, ey, x, w " << r->startY << "," << r->endY << "," << r->left << "," << r->width << " " << endl;
1657             if (r->startY <= y && r->endY > y &&
1658                 r->type == FloatingObject::FloatRight &&
1659                 r->left < right) {
1660                 right = r->left;
1661                 if ( heightRemaining ) *heightRemaining = r->endY - y;
1662             }
1663         }
1664     }
1665     
1666     if (applyTextIndent && m_firstLine && style()->direction() == RTL) {
1667         int cw=0;
1668         if (style()->textIndent().isPercent())
1669             cw = containingBlock()->contentWidth();
1670         right += style()->textIndent().minWidth(cw);
1671     }
1672     
1673     //kdDebug( 6040 ) << "rightOffset(" << y << ") = " << right << endl;
1674     return right;
1675 }
1676
1677 int
1678 RenderBlock::lineWidth(int y) const
1679 {
1680     //kdDebug( 6040 ) << "lineWidth(" << y << ")=" << rightOffset(y) - leftOffset(y) << endl;
1681     int result = rightOffset(y) - leftOffset(y);
1682     return (result < 0) ? 0 : result;
1683 }
1684
1685 int
1686 RenderBlock::nearestFloatBottom(int height) const
1687 {
1688     if (!m_floatingObjects) return 0;
1689     int bottom = 0;
1690     FloatingObject* r;
1691     QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1692     for ( ; (r = it.current()); ++it )
1693         if (r->endY>height && (r->endY<bottom || bottom==0))
1694             bottom=r->endY;
1695     return QMAX(bottom, height);
1696 }
1697
1698 int
1699 RenderBlock::floatBottom() const
1700 {
1701     if (!m_floatingObjects) return 0;
1702     int bottom=0;
1703     FloatingObject* r;
1704     QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1705     for ( ; (r = it.current()); ++it )
1706         if (r->endY>bottom)
1707             bottom=r->endY;
1708     return bottom;
1709 }
1710
1711 int
1712 RenderBlock::lowestPosition(bool includeOverflowInterior, bool includeSelf) const
1713 {
1714     int bottom = RenderFlow::lowestPosition(includeOverflowInterior, includeSelf);
1715     if (!includeOverflowInterior && hasOverflowClip())
1716         return bottom;
1717     if (includeSelf && m_overflowHeight > bottom)
1718         bottom = m_overflowHeight;
1719     
1720     if (m_floatingObjects) {
1721         FloatingObject* r;
1722         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1723         for ( ; (r = it.current()); ++it ) {
1724             if (!r->noPaint) {
1725                 int lp = r->startY + r->node->marginTop() + r->node->lowestPosition(false);
1726                 bottom = kMax(bottom, lp);
1727             }
1728         }
1729     }
1730
1731     // Fixed positioned objects do not scroll and thus should not constitute
1732     // part of the lowest position.
1733     if (m_positionedObjects && !isCanvas()) {
1734         RenderObject* r;
1735         QPtrListIterator<RenderObject> it(*m_positionedObjects);
1736         for ( ; (r = it.current()); ++it ) {
1737             int lp = r->yPos() + r->lowestPosition(false);
1738             bottom = kMax(bottom, lp);
1739         }
1740     }
1741
1742     if (!includeSelf && lastLineBox()) {
1743         int lp = lastLineBox()->yPos() + lastLineBox()->height();
1744         bottom = kMax(bottom, lp);
1745     }
1746     
1747     return bottom;
1748 }
1749
1750 int RenderBlock::rightmostPosition(bool includeOverflowInterior, bool includeSelf) const
1751 {
1752     int right = RenderFlow::rightmostPosition(includeOverflowInterior, includeSelf);
1753     if (!includeOverflowInterior && hasOverflowClip())
1754         return right;
1755     if (includeSelf && m_overflowWidth > right)
1756         right = m_overflowWidth;
1757     
1758     if (m_floatingObjects) {
1759         FloatingObject* r;
1760         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1761         for ( ; (r = it.current()); ++it ) {
1762             if (!r->noPaint) {
1763                 int rp = r->left + r->node->marginLeft() + r->node->rightmostPosition(false);
1764                 right = kMax(right, rp);
1765             }
1766         }
1767     }
1768
1769     if (m_positionedObjects && !isCanvas()) {
1770         RenderObject* r;
1771         QPtrListIterator<RenderObject> it(*m_positionedObjects);
1772         for ( ; (r = it.current()); ++it ) {
1773             int rp = r->xPos() + r->rightmostPosition(false);
1774             right = kMax(right, rp);
1775         }
1776     }
1777
1778     if (!includeSelf && firstLineBox()) {
1779         for (InlineRunBox* currBox = firstLineBox(); currBox; currBox = currBox->nextLineBox()) {
1780             int rp = currBox->xPos() + currBox->width();
1781             right = kMax(right, rp);
1782         }
1783     }
1784     
1785     return right;
1786 }
1787
1788 int RenderBlock::leftmostPosition(bool includeOverflowInterior, bool includeSelf) const
1789 {
1790     int left = RenderFlow::leftmostPosition(includeOverflowInterior, includeSelf);
1791     if (!includeOverflowInterior && hasOverflowClip())
1792         return left;
1793
1794     // FIXME: Check left overflow when we eventually support it.
1795     
1796     if (m_floatingObjects) {
1797         FloatingObject* r;
1798         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1799         for ( ; (r = it.current()); ++it ) {
1800             if (!r->noPaint) {
1801                 int lp = r->left + r->node->marginLeft() + r->node->leftmostPosition(false);
1802                 left = kMin(left, lp);
1803             }
1804         }
1805     }
1806     
1807     if (m_positionedObjects && !isCanvas()) {
1808         RenderObject* r;
1809         QPtrListIterator<RenderObject> it(*m_positionedObjects);
1810         for ( ; (r = it.current()); ++it ) {
1811             int lp = r->xPos() + r->leftmostPosition(false);
1812             left = kMin(left, lp);
1813         }
1814     }
1815     
1816     if (!includeSelf && firstLineBox()) {
1817         for (InlineRunBox* currBox = firstLineBox(); currBox; currBox = currBox->nextLineBox())
1818             left = kMin(left, (int)currBox->xPos());
1819     }
1820     
1821     return left;
1822 }
1823
1824 int
1825 RenderBlock::leftBottom()
1826 {
1827     if (!m_floatingObjects) return 0;
1828     int bottom=0;
1829     FloatingObject* r;
1830     QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1831     for ( ; (r = it.current()); ++it )
1832         if (r->endY>bottom && r->type == FloatingObject::FloatLeft)
1833             bottom=r->endY;
1834
1835     return bottom;
1836 }
1837
1838 int
1839 RenderBlock::rightBottom()
1840 {
1841     if (!m_floatingObjects) return 0;
1842     int bottom=0;
1843     FloatingObject* r;
1844     QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1845     for ( ; (r = it.current()); ++it )
1846         if (r->endY>bottom && r->type == FloatingObject::FloatRight)
1847             bottom=r->endY;
1848
1849     return bottom;
1850 }
1851
1852 void
1853 RenderBlock::clearFloats()
1854 {
1855     if (m_floatingObjects)
1856         m_floatingObjects->clear();
1857
1858     // Inline blocks are covered by the isReplaced() check in the avoidFloats method.
1859     if (avoidsFloats() || isRoot() || isCanvas() || isFloatingOrPositioned() || isTableCell())
1860         return;
1861     
1862     // Attempt to locate a previous sibling with overhanging floats.  We skip any elements that are
1863     // out of flow (like floating/positioned elements), and we also skip over any objects that may have shifted
1864     // to avoid floats.
1865     bool parentHasFloats = false;
1866     RenderObject *prev = previousSibling();
1867     while (prev && (!prev->isRenderBlock() || prev->avoidsFloats() || prev->isFloatingOrPositioned())) {
1868         if (prev->isFloating())
1869             parentHasFloats = true;
1870          prev = prev->previousSibling();
1871     }
1872
1873     // First add in floats from the parent.
1874     int offset = m_y;
1875     if (parentHasFloats)
1876         addOverHangingFloats( static_cast<RenderBlock *>( parent() ),
1877                               parent()->borderLeft() + parent()->paddingLeft(), offset, false );
1878
1879     int xoffset = 0;
1880     if (prev)
1881         offset -= prev->yPos();
1882     else {
1883         prev = parent();
1884         xoffset += prev->borderLeft() + prev->paddingLeft();
1885     }
1886     //kdDebug() << "RenderBlock::clearFloats found previous "<< (void *)this << " prev=" << (void *)prev<< endl;
1887
1888     // Add overhanging floats from the previous RenderBlock, but only if it has a float that intrudes into our space.
1889     if (!prev->isRenderBlock()) return;
1890     RenderBlock* block = static_cast<RenderBlock *>(prev);
1891     if (!block->m_floatingObjects) return;
1892     if (block->floatBottom() > offset)
1893         addOverHangingFloats(block, xoffset, offset);
1894 }
1895
1896 void RenderBlock::addOverHangingFloats( RenderBlock *flow, int xoff, int offset, bool child )
1897 {
1898 #ifdef DEBUG_LAYOUT
1899     kdDebug( 6040 ) << (void *)this << ": adding overhanging floats xoff=" << xoff << "  offset=" << offset << " child=" << child << endl;
1900 #endif
1901
1902     // Prevent floats from being added to the canvas by the root element, e.g., <html>.
1903     if ( !flow->m_floatingObjects || (child && flow->isRoot()) )
1904         return;
1905
1906     // we have overhanging floats
1907     if (!m_floatingObjects) {
1908         m_floatingObjects = new QPtrList<FloatingObject>;
1909         m_floatingObjects->setAutoDelete(true);
1910     }
1911
1912     QPtrListIterator<FloatingObject> it(*flow->m_floatingObjects);
1913     FloatingObject *r;
1914     for ( ; (r = it.current()); ++it ) {
1915         if ( ( !child && r->endY > offset ) ||
1916              ( child && flow->yPos() + r->endY > height() ) ) {
1917
1918             if (child && (flow->enclosingLayer() == enclosingLayer()))
1919                 // Set noPaint to true only if we didn't cross layers.
1920                 r->noPaint = true;
1921
1922             FloatingObject* f = 0;
1923             // don't insert it twice!
1924             QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1925             while ( (f = it.current()) ) {
1926                 if (f->node == r->node) break;
1927                 ++it;
1928             }
1929             if ( !f ) {
1930                 FloatingObject *floatingObj = new FloatingObject(r->type);
1931                 floatingObj->startY = r->startY - offset;
1932                 floatingObj->endY = r->endY - offset;
1933                 floatingObj->left = r->left - xoff;
1934                 // Applying the child's margin makes no sense in the case where the child was passed in.
1935                 // since his own margin was added already through the subtraction of the |xoff| variable
1936                 // above.  |xoff| will equal -flow->marginLeft() in this case, so it's already been taken
1937                 // into account.  Only apply this code if |child| is false, since otherwise the left margin
1938                 // will get applied twice. -dwh
1939                 if (!child && flow != parent())
1940                     floatingObj->left += flow->marginLeft();
1941                 if ( !child ) {
1942                     floatingObj->left -= marginLeft();
1943                     floatingObj->noPaint = true;
1944                 }
1945                 else
1946                     // Only paint if |flow| isn't.
1947                     floatingObj->noPaint = !r->noPaint;
1948                 
1949                 floatingObj->width = r->width;
1950                 floatingObj->node = r->node;
1951                 m_floatingObjects->append(floatingObj);
1952 #ifdef DEBUG_LAYOUT
1953                 kdDebug( 6040 ) << "addOverHangingFloats x/y= (" << floatingObj->left << "/" << floatingObj->startY << "-" << floatingObj->width << "/" << floatingObj->endY - floatingObj->startY << ")" << endl;
1954 #endif
1955             }
1956         }
1957     }
1958 }
1959
1960 bool RenderBlock::containsFloat(RenderObject* o)
1961 {
1962     if (m_floatingObjects) {
1963         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
1964         while (it.current()) {
1965             if (it.current()->node == o)
1966                 return true;
1967             ++it;
1968         }
1969     }
1970     return false;
1971 }
1972
1973 void RenderBlock::markAllDescendantsWithFloatsForLayout(RenderObject* floatToRemove)
1974 {
1975     setNeedsLayout(true);
1976
1977     if (floatToRemove)
1978         removeFloatingObject(floatToRemove);
1979
1980     // Iterate over our children and mark them as needed.
1981     if (!childrenInline()) {
1982         for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
1983             if (isBlockFlow() && !child->isFloatingOrPositioned() &&
1984                 (floatToRemove ? child->containsFloat(floatToRemove) : child->containsFloats()))
1985                 child->markAllDescendantsWithFloatsForLayout(floatToRemove);
1986         }
1987     }
1988 }
1989
1990 int RenderBlock::getClearDelta(RenderObject *child)
1991 {
1992     //kdDebug( 6040 ) << "checkClear oldheight=" << m_height << endl;
1993     int bottom = 0;
1994     switch(child->style()->clear())
1995     {
1996         case CNONE:
1997             return 0;
1998         case CLEFT:
1999             bottom = leftBottom();
2000             break;
2001         case CRIGHT:
2002             bottom = rightBottom();
2003             break;
2004         case CBOTH:
2005             bottom = floatBottom();
2006             break;
2007     }
2008
2009     return QMAX(0, bottom-(child->yPos()));
2010 }
2011
2012 bool RenderBlock::isPointInScrollbar(int _x, int _y, int _tx, int _ty)
2013 {
2014     if (!scrollsOverflow())
2015         return false;
2016
2017     if (m_layer->verticalScrollbarWidth()) {
2018         QRect vertRect(_tx + width() - borderRight() - m_layer->verticalScrollbarWidth(),
2019                        _ty + borderTop(),
2020                        m_layer->verticalScrollbarWidth(),
2021                        height()-borderTop()-borderBottom());
2022         if (vertRect.contains(_x, _y)) {
2023             RenderLayer::gScrollBar = m_layer->verticalScrollbar();
2024             return true;
2025         }
2026     }
2027
2028     if (m_layer->horizontalScrollbarHeight()) {
2029         QRect horizRect(_tx + borderLeft(),
2030                         _ty + height() - borderBottom() - m_layer->horizontalScrollbarHeight(),
2031                         width()-borderLeft()-borderRight(),
2032                         m_layer->horizontalScrollbarHeight());
2033         if (horizRect.contains(_x, _y)) {
2034             RenderLayer::gScrollBar = m_layer->horizontalScrollbar();
2035             return true;
2036         }
2037     }
2038
2039     return false;    
2040 }
2041
2042 bool RenderBlock::nodeAtPoint(NodeInfo& info, int _x, int _y, int _tx, int _ty,
2043                               HitTestAction hitTestAction, bool inBox)
2044 {
2045     bool inScrollbar = isPointInScrollbar(_x, _y, _tx+xPos(), _ty+yPos());
2046     if (inScrollbar && hitTestAction != HitTestChildrenOnly)
2047         inBox = true;
2048     
2049     if (hitTestAction != HitTestSelfOnly && !inScrollbar) {
2050         int stx = _tx + xPos();
2051         int sty = _ty + yPos();
2052         
2053         if (m_floatingObjects) {
2054             if (hasOverflowClip())
2055                 m_layer->subtractScrollOffset(stx, sty);
2056             if (isCanvas()) {
2057                 stx += static_cast<RenderCanvas*>(this)->view()->contentsX();
2058                 sty += static_cast<RenderCanvas*>(this)->view()->contentsY();
2059             }
2060             FloatingObject* o;
2061             QPtrListIterator<FloatingObject> it(*m_floatingObjects);
2062             for (it.toLast(); (o = it.current()); --it)
2063                 if (!o->noPaint && !o->node->layer())
2064                     inBox |= o->node->nodeAtPoint(info, _x, _y,
2065                                                   stx+o->left + o->node->marginLeft() - o->node->xPos(),
2066                                                   sty+o->startY + o->node->marginTop() - o->node->yPos());
2067         }
2068
2069         if (hasMarkupTruncation()) {
2070             for (RootInlineBox* box = lastRootBox(); box; box = box->prevRootBox()) {
2071                 if (box->ellipsisBox()) {
2072                     inBox |= box->hitTestEllipsisBox(info, _x, _y, stx, sty, hitTestAction, inBox);
2073                     break;
2074                 }
2075             }
2076         }
2077     }
2078
2079     inBox |= RenderFlow::nodeAtPoint(info, _x, _y, _tx, _ty, hitTestAction, inBox);
2080     return inBox;
2081 }
2082
2083 Position RenderBlock::positionForBox(InlineBox *box, bool start) const
2084 {
2085     if (!box)
2086         return Position();
2087
2088     if (!box->object()->element())
2089         return Position(element(), start ? caretMinOffset() : caretMaxOffset());
2090
2091     if (!box->isInlineTextBox())
2092         return Position(box->object()->element(), start ? box->object()->caretMinOffset() : box->object()->caretMaxOffset());
2093
2094     InlineTextBox *textBox = static_cast<InlineTextBox *>(box);
2095     return Position(box->object()->element(), start ? textBox->start() : textBox->start() + textBox->len());
2096 }
2097
2098 Position RenderBlock::positionForRenderer(RenderObject *renderer, bool start) const
2099 {
2100     if (!renderer)
2101         return Position(element(), 0);
2102
2103     NodeImpl *node = renderer->element() ? renderer->element() : element();
2104     if (!node)
2105         return Position();
2106
2107     long offset = start ? node->caretMinOffset() : node->caretMaxOffset();
2108     return Position(node, offset);
2109 }
2110
2111 Position RenderBlock::positionForCoordinates(int _x, int _y)
2112 {
2113     if (isTable())
2114         return RenderFlow::positionForCoordinates(_x, _y); 
2115
2116     int absx, absy;
2117     absolutePosition(absx, absy);
2118
2119     int top = absy + borderTop() + paddingTop();
2120     int bottom = top + contentHeight();
2121
2122     if (_y < top)
2123         // y coordinate is above block
2124         return positionForRenderer(firstLeafChild(), true);
2125
2126     if (_y >= bottom)
2127         // y coordinate is below block
2128         return positionForRenderer(lastLeafChild(), false);
2129
2130     if (childrenInline()) {
2131         if (!firstRootBox())
2132             return Position(element(), 0);
2133             
2134         if (_y >= top && _y < absy + firstRootBox()->topOverflow())
2135             // y coordinate is above first root line box
2136             return positionForBox(firstRootBox()->firstLeafChild(), true);
2137         
2138         // look for the closest line box in the root box which is at the passed-in y coordinate
2139         for (RootInlineBox *root = firstRootBox(); root; root = root->nextRootBox()) {
2140             top = absy + root->topOverflow();
2141             // set the bottom based on whether there is a next root box
2142             if (root->nextRootBox())
2143                 bottom = absy + root->nextRootBox()->topOverflow();
2144             else
2145                 bottom = absy + root->bottomOverflow();
2146             // check if this root line box is located at this y coordinate
2147             if (_y >= top && _y < bottom && root->firstChild()) {
2148                 InlineBox *closestBox = root->closestLeafChildForXPos(_x, absx);
2149                 if (closestBox) {
2150                     // pass the box a y position that is inside it
2151                     return closestBox->object()->positionForCoordinates(_x, absy + closestBox->m_y);
2152                 }
2153             }
2154         }
2155
2156         if (lastRootBox())
2157             // y coordinate is below last root line box
2158             return positionForBox(lastRootBox()->lastLeafChild(), false);
2159         
2160         return Position(element(), 0);
2161     }
2162     
2163     // see if any child blocks exist at this y coordinate
2164     for (RenderObject *renderer = firstChild(); renderer; renderer = renderer->nextSibling()) {
2165         if (renderer->isFloatingOrPositioned())
2166             continue;
2167         renderer->absolutePosition(absx, top);
2168         RenderObject *next = renderer->nextSibling();
2169         while (next && next->isFloatingOrPositioned())
2170             next = next->nextSibling();
2171         if (next) 
2172             next->absolutePosition(absx, bottom);
2173         else
2174             bottom = top + contentHeight();
2175         if (_y >= top && _y < bottom) {
2176             return renderer->positionForCoordinates(_x, _y);
2177         }
2178     }
2179
2180     // pass along to the first child
2181     if (firstChild())
2182         return firstChild()->positionForCoordinates(_x, _y);
2183     
2184     // still no luck...return this render object's element and offset 0
2185     return Position(element(), 0);
2186 }
2187
2188 void RenderBlock::calcMinMaxWidth()
2189 {
2190     KHTMLAssert( !minMaxKnown() );
2191
2192 #ifdef DEBUG_LAYOUT
2193     kdDebug( 6040 ) << renderName() << "(RenderBlock)::calcMinMaxWidth() this=" << this << endl;
2194 #endif
2195
2196     m_minWidth = 0;
2197     m_maxWidth = 0;
2198
2199     bool preOrNowrap = style()->whiteSpace() != NORMAL;
2200     if (childrenInline())
2201         calcInlineMinMaxWidth();
2202     else
2203         calcBlockMinMaxWidth();
2204
2205     if(m_maxWidth < m_minWidth) m_maxWidth = m_minWidth;
2206
2207     if (preOrNowrap && childrenInline()) {
2208         m_minWidth = m_maxWidth;
2209         
2210         // A horizontal marquee with inline children has no minimum width.
2211         if (style()->overflow() == OMARQUEE && m_layer && m_layer->marquee() && 
2212             m_layer->marquee()->isHorizontal() && !m_layer->marquee()->isUnfurlMarquee())
2213             m_minWidth = 0;
2214     }
2215
2216     if (style()->width().isFixed() && style()->width().value > 0) {
2217         if (isTableCell())
2218             m_maxWidth = KMAX(m_minWidth, style()->width().value);
2219         else
2220             m_minWidth = m_maxWidth = style()->width().value;
2221     }
2222     
2223     if (style()->minWidth().isFixed() && style()->minWidth().value > 0) {
2224         m_maxWidth = KMAX(m_maxWidth, style()->minWidth().value);
2225         m_minWidth = KMAX(m_minWidth, style()->minWidth().value);
2226     }
2227     
2228     if (style()->maxWidth().isFixed() && style()->maxWidth().value != UNDEFINED) {
2229         m_maxWidth = KMIN(m_maxWidth, style()->maxWidth().value);
2230         m_minWidth = KMIN(m_minWidth, style()->maxWidth().value);
2231     }
2232
2233     int toAdd = 0;
2234     toAdd = borderLeft() + borderRight() + paddingLeft() + paddingRight();
2235
2236     m_minWidth += toAdd;
2237     m_maxWidth += toAdd;
2238
2239     setMinMaxKnown();
2240
2241     //kdDebug( 6040 ) << "Text::calcMinMaxWidth(" << this << "): min = " << m_minWidth << " max = " << m_maxWidth << endl;
2242 }
2243
2244 struct InlineMinMaxIterator
2245 {
2246 /* InlineMinMaxIterator is a class that will iterate over all render objects that contribute to
2247    inline min/max width calculations.  Note the following about the way it walks:
2248    (1) Positioned content is skipped (since it does not contribute to min/max width of a block)
2249    (2) We do not drill into the children of floats or replaced elements, since you can't break
2250        in the middle of such an element.
2251    (3) Inline flows (e.g., <a>, <span>, <i>) are walked twice, since each side can have
2252        distinct borders/margin/padding that contribute to the min/max width.
2253 */
2254     RenderObject* parent;
2255     RenderObject* current;
2256     bool endOfInline;
2257
2258     InlineMinMaxIterator(RenderObject* p, RenderObject* o, bool end = false)
2259         :parent(p), current(o), endOfInline(end) {}
2260
2261     RenderObject* next();
2262 };
2263
2264 RenderObject* InlineMinMaxIterator::next()
2265 {
2266     RenderObject* result = 0;
2267     bool oldEndOfInline = endOfInline;
2268     endOfInline = false;
2269     while (current != 0 || (current == parent))
2270     {
2271         //kdDebug( 6040 ) << "current = " << current << endl;
2272         if (!oldEndOfInline &&
2273             (current == parent ||
2274              (!current->isFloating() && !current->isReplaced() && !current->isPositioned())))
2275             result = current->firstChild();
2276         if (!result) {
2277             // We hit the end of our inline. (It was empty, e.g., <span></span>.)
2278             if (!oldEndOfInline && current->isInlineFlow()) {
2279                 result = current;
2280                 endOfInline = true;
2281                 break;
2282             }
2283
2284             while (current && current != parent) {
2285                 result = current->nextSibling();
2286                 if (result) break;
2287                 current = current->parent();
2288                 if (current && current != parent && current->isInlineFlow()) {
2289                     result = current;
2290                     endOfInline = true;
2291                     break;
2292                 }
2293             }
2294         }
2295
2296         if (!result) break;
2297
2298         if (!result->isPositioned() && (result->isText() || result->isBR() ||
2299             result->isFloating() || result->isReplaced() ||
2300             result->isInlineFlow()))
2301             break;
2302         
2303         current = result;
2304         result = 0;
2305     }
2306
2307     // Update our position.
2308     current = result;
2309     return current;
2310 }
2311
2312 static int getBPMWidth(int childValue, Length cssUnit)
2313 {
2314     if (cssUnit.type != Variable)
2315         return (cssUnit.type == Fixed ? cssUnit.value : childValue);
2316     return 0;
2317 }
2318
2319 static int getBorderPaddingMargin(RenderObject* child, bool endOfInline)
2320 {
2321     RenderStyle* cstyle = child->style();
2322     int result = 0;
2323     bool leftSide = (cstyle->direction() == LTR) ? !endOfInline : endOfInline;
2324     result += getBPMWidth((leftSide ? child->marginLeft() : child->marginRight()),
2325                           (leftSide ? cstyle->marginLeft() :
2326                                       cstyle->marginRight()));
2327     result += getBPMWidth((leftSide ? child->paddingLeft() : child->paddingRight()),
2328                           (leftSide ? cstyle->paddingLeft() :
2329                                       cstyle->paddingRight()));
2330     result += leftSide ? child->borderLeft() : child->borderRight();
2331     return result;
2332 }
2333
2334 static void stripTrailingSpace(bool pre,
2335                                int& inlineMax, int& inlineMin,
2336                                RenderObject* trailingSpaceChild)
2337 {
2338     if (!pre && trailingSpaceChild && trailingSpaceChild->isText()) {
2339         // Collapse away the trailing space at the end of a block.
2340         RenderText* t = static_cast<RenderText *>(trailingSpaceChild);
2341         const Font *f = t->htmlFont( false );
2342         QChar space[1]; space[0] = ' ';
2343         int spaceWidth = f->width(space, 1, 0);
2344         inlineMax -= spaceWidth;
2345         if (inlineMin > inlineMax)
2346             inlineMin = inlineMax;
2347     }
2348 }
2349
2350 void RenderBlock::calcInlineMinMaxWidth()
2351 {
2352     int inlineMax=0;
2353     int inlineMin=0;
2354
2355     int cw = containingBlock()->contentWidth();
2356
2357     // If we are at the start of a line, we want to ignore all white-space.
2358     // Also strip spaces if we previously had text that ended in a trailing space.
2359     bool stripFrontSpaces = true;
2360     RenderObject* trailingSpaceChild = 0;
2361
2362     bool normal, oldnormal;
2363     normal = oldnormal = style()->whiteSpace() == NORMAL;
2364
2365     InlineMinMaxIterator childIterator(this, this);
2366     bool addedTextIndent = false; // Only gets added in once.
2367     RenderObject* prevFloat = 0;
2368     while (RenderObject* child = childIterator.next())
2369     {
2370         normal = child->style()->whiteSpace() == NORMAL;
2371
2372         if (!child->isBR()) {
2373             // Step One: determine whether or not we need to go ahead and
2374             // terminate our current line.  Each discrete chunk can become
2375             // the new min-width, if it is the widest chunk seen so far, and
2376             // it can also become the max-width.
2377
2378             // Children fall into three categories:
2379             // (1) An inline flow object.  These objects always have a min/max of 0,
2380             // and are included in the iteration solely so that their margins can
2381             // be added in.
2382             //
2383             // (2) An inline non-text non-flow object, e.g., an inline replaced element.
2384             // These objects can always be on a line by themselves, so in this situation
2385             // we need to go ahead and break the current line, and then add in our own
2386             // margins and min/max width on its own line, and then terminate the line.
2387             //
2388             // (3) A text object.  Text runs can have breakable characters at the start,
2389             // the middle or the end.  They may also lose whitespace off the front if
2390             // we're already ignoring whitespace.  In order to compute accurate min-width
2391             // information, we need three pieces of information.
2392             // (a) the min-width of the first non-breakable run.  Should be 0 if the text string
2393             // starts with whitespace.
2394             // (b) the min-width of the last non-breakable run. Should be 0 if the text string
2395             // ends with whitespace.
2396             // (c) the min/max width of the string (trimmed for whitespace).
2397             //
2398             // If the text string starts with whitespace, then we need to go ahead and
2399             // terminate our current line (unless we're already in a whitespace stripping
2400             // mode.
2401             //
2402             // If the text string has a breakable character in the middle, but didn't start
2403             // with whitespace, then we add the width of the first non-breakable run and
2404             // then end the current line.  We then need to use the intermediate min/max width
2405             // values (if any of them are larger than our current min/max).  We then look at
2406             // the width of the last non-breakable run and use that to start a new line
2407             // (unless we end in whitespace).
2408             RenderStyle* cstyle = child->style();
2409             int childMin = 0;
2410             int childMax = 0;
2411
2412             if (!child->isText()) {
2413                 // Case (1) and (2).  Inline replaced and inline flow elements.
2414                 if (child->isInlineFlow()) {
2415                     // Add in padding/border/margin from the appropriate side of
2416                     // the element.
2417                     int bpm = getBorderPaddingMargin(child, childIterator.endOfInline);
2418                     childMin += bpm;
2419                     childMax += bpm;
2420
2421                     inlineMin += childMin;
2422                     inlineMax += childMax;
2423                 }
2424                 else {
2425                     // Inline replaced elts add in their margins to their min/max values.
2426                     int margins = 0;
2427                     LengthType type = cstyle->marginLeft().type;
2428                     if ( type != Variable )
2429                         margins += (type == Fixed ? cstyle->marginLeft().value : child->marginLeft());
2430                     type = cstyle->marginRight().type;
2431                     if ( type != Variable )
2432                         margins += (type == Fixed ? cstyle->marginRight().value : child->marginRight());
2433                     childMin += margins;
2434                     childMax += margins;
2435                 }
2436             }
2437
2438             if (!child->isRenderInline() && !child->isText()) {
2439                 // Case (2). Inline replaced elements and floats.
2440                 // Go ahead and terminate the current line as far as
2441                 // minwidth is concerned.
2442                 childMin += child->minWidth();
2443                 childMax += child->maxWidth();
2444
2445                 if (normal || oldnormal) {
2446                     if(m_minWidth < inlineMin) m_minWidth = inlineMin;
2447                     inlineMin = 0;
2448                 }
2449
2450                 // Check our "clear" setting.  If we're supposed to clear the previous float, then
2451                 // go ahead and terminate maxwidth as well.
2452                 if (child->isFloating()) {
2453                     if (prevFloat &&
2454                         ((prevFloat->style()->floating() == FLEFT && (child->style()->clear() & CLEFT)) ||
2455                          (prevFloat->style()->floating() == FRIGHT && (child->style()->clear() & CRIGHT)))) {
2456                         m_maxWidth = kMax(inlineMax, m_maxWidth);
2457                         inlineMax = 0;
2458                     }
2459                     prevFloat = child;
2460                 }
2461                 
2462                 // Add in text-indent.  This is added in only once.
2463                 int ti = 0;
2464                 if (!addedTextIndent) {
2465                     addedTextIndent = true;
2466                     ti = style()->textIndent().minWidth(cw);
2467                     childMin+=ti;
2468                     childMax+=ti;
2469                 }
2470                 
2471                 // Add our width to the max.
2472                 inlineMax += childMax;
2473
2474                 if (!normal)
2475                     inlineMin += childMin;
2476                 else {
2477                     // Now check our line.
2478                     inlineMin = childMin;
2479                     if(m_minWidth < inlineMin) m_minWidth = inlineMin;
2480
2481                     // Now start a new line.
2482                     inlineMin = 0;
2483                 }
2484
2485                 // We are no longer stripping whitespace at the start of
2486                 // a line.
2487                 if (!child->isFloating()) {
2488                     stripFrontSpaces = false;
2489                     trailingSpaceChild = 0;
2490                 }
2491             }
2492             else if (child->isText())
2493             {
2494                 // Case (3). Text.
2495                 RenderText* t = static_cast<RenderText *>(child);
2496
2497                 // Determine if we have a breakable character.  Pass in
2498                 // whether or not we should ignore any spaces at the front
2499                 // of the string.  If those are going to be stripped out,
2500                 // then they shouldn't be considered in the breakable char
2501                 // check.
2502                 bool hasBreakableChar, hasBreak;
2503                 int beginMin, endMin;
2504                 bool beginWS, endWS;
2505                 int beginMax, endMax;
2506                 t->trimmedMinMaxWidth(beginMin, beginWS, endMin, endWS, hasBreakableChar,
2507                                       hasBreak, beginMax, endMax,
2508                                       childMin, childMax, stripFrontSpaces);
2509
2510                 // This text object is insignificant and will not be rendered.  Just
2511                 // continue.
2512                 if (!hasBreak && childMax == 0) continue;
2513                 
2514                 if (stripFrontSpaces)
2515                     trailingSpaceChild = child;
2516                 else
2517                     trailingSpaceChild = 0;
2518
2519                 // Add in text-indent.  This is added in only once.
2520                 int ti = 0;
2521                 if (!addedTextIndent) {
2522                     addedTextIndent = true;
2523                     ti = style()->textIndent().minWidth(cw);
2524                     childMin+=ti; beginMin += ti;
2525                     childMax+=ti; beginMax += ti;
2526                 }
2527                 
2528                 // If we have no breakable characters at all,
2529                 // then this is the easy case. We add ourselves to the current
2530                 // min and max and continue.
2531                 if (!hasBreakableChar) {
2532                     inlineMin += childMin;
2533                 }
2534                 else {
2535                     // We have a breakable character.  Now we need to know if
2536                     // we start and end with whitespace.
2537                     if (beginWS) {
2538                         // Go ahead and end the current line.
2539                         if(m_minWidth < inlineMin) m_minWidth = inlineMin;
2540                     }
2541                     else {
2542                         inlineMin += beginMin;
2543                         if(m_minWidth < inlineMin) m_minWidth = inlineMin;
2544                         childMin -= ti;
2545                     }
2546
2547                     inlineMin = childMin;
2548
2549                     if (endWS) {
2550                         // We end in whitespace, which means we can go ahead
2551                         // and end our current line.
2552                         if(m_minWidth < inlineMin) m_minWidth = inlineMin;
2553                         inlineMin = 0;
2554                     }
2555                     else {
2556                         if(m_minWidth < inlineMin) m_minWidth = inlineMin;
2557                         inlineMin = endMin;
2558                     }
2559                 }
2560
2561                 if (hasBreak) {
2562                     inlineMax += beginMax;
2563                     if (m_maxWidth < inlineMax) m_maxWidth = inlineMax;
2564                     if (m_maxWidth < childMax) m_maxWidth = childMax;
2565                     inlineMax = endMax;
2566                 }
2567                 else
2568                     inlineMax += childMax;
2569             }
2570         }
2571         else
2572         {
2573             if(m_minWidth < inlineMin) m_minWidth = inlineMin;
2574             if(m_maxWidth < inlineMax) m_maxWidth = inlineMax;
2575             inlineMin = inlineMax = 0;
2576             stripFrontSpaces = true;
2577             trailingSpaceChild = 0;
2578         }
2579
2580         oldnormal = normal;
2581     }
2582
2583     stripTrailingSpace(m_pre, inlineMax, inlineMin, trailingSpaceChild);
2584     
2585     if(m_minWidth < inlineMin) m_minWidth = inlineMin;
2586     if(m_maxWidth < inlineMax) m_maxWidth = inlineMax;
2587
2588     //         kdDebug( 6040 ) << "m_minWidth=" << m_minWidth
2589     //                  << " m_maxWidth=" << m_maxWidth << endl;
2590 }
2591
2592 // Use a very large value (in effect infinite).
2593 #define BLOCK_MAX_WIDTH 15000
2594
2595 void RenderBlock::calcBlockMinMaxWidth()
2596 {
2597     bool nowrap = style()->whiteSpace() == NOWRAP;
2598
2599     RenderObject *child = firstChild();
2600     RenderObject* prevFloat = 0;
2601     int floatWidths = 0;
2602     while (child) {
2603         // Positioned children don't affect the min/max width
2604         if (child->isPositioned()) {
2605             child = child->nextSibling();
2606             continue;
2607         }
2608
2609         if (prevFloat && (!child->isFloating() || 
2610                           (prevFloat->style()->floating() == FLEFT && (child->style()->clear() & CLEFT)) ||
2611                           (prevFloat->style()->floating() == FRIGHT && (child->style()->clear() & CRIGHT)))) {
2612             m_maxWidth = kMax(floatWidths, m_maxWidth);
2613             floatWidths = 0;
2614         }
2615
2616         Length ml = child->style()->marginLeft();
2617         Length mr = child->style()->marginRight();
2618
2619         // Call calcWidth on the child to ensure that our margins are
2620         // up to date.  This method can be called before the child has actually
2621         // calculated its margins (which are computed inside calcWidth).
2622         if (ml.type == Percent || mr.type == Percent)
2623             calcWidth();
2624
2625         // A margin basically has three types: fixed, percentage, and auto (variable).
2626         // Auto margins simply become 0 when computing min/max width.
2627         // Fixed margins can be added in as is.
2628         // Percentage margins are computed as a percentage of the width we calculated in
2629         // the calcWidth call above.  In this case we use the actual cached margin values on
2630         // the RenderObject itself.
2631         int margin = 0;
2632         if (ml.type == Fixed)
2633             margin += ml.value;
2634         else if (ml.type == Percent)
2635             margin += child->marginLeft();
2636
2637         if (mr.type == Fixed)
2638             margin += mr.value;
2639         else if (mr.type == Percent)
2640             margin += child->marginRight();
2641         
2642         if (margin < 0) margin = 0;
2643
2644         int w = child->minWidth() + margin;
2645         if (m_minWidth < w) m_minWidth = w;
2646         // IE ignores tables for calculation of nowrap. Makes some sense.
2647         if (nowrap && !child->isTable() && m_maxWidth < w)
2648             m_maxWidth = w;
2649
2650         w = child->maxWidth() + margin;
2651
2652         if (child->isFloating())
2653             floatWidths += w;
2654         else if (m_maxWidth < w)
2655             m_maxWidth = w;
2656
2657         // A very specific WinIE quirk.
2658         // Example:
2659         /*
2660            <div style="position:absolute; width:100px; top:50px;">
2661               <div style="position:absolute;left:0px;top:50px;height:50px;background-color:green">
2662                 <table style="width:100%"><tr><td></table>
2663               </div>
2664            </div>
2665         */
2666         // In the above example, the inner absolute positioned block should have a computed width
2667         // of 100px because of the table.
2668         // We can achieve this effect by making the maxwidth of blocks that contain tables
2669         // with percentage widths be infinite (as long as they are not inside a table cell).
2670         if (style()->htmlHacks() && child->style()->width().type == Percent &&
2671             !isTableCell() && child->isTable() && m_maxWidth < BLOCK_MAX_WIDTH) {
2672             RenderBlock* cb = containingBlock();
2673             while (!cb->isCanvas() && !cb->isTableCell())
2674                 cb = cb->containingBlock();
2675             if (!cb->isTableCell())
2676                 m_maxWidth = BLOCK_MAX_WIDTH;
2677         }
2678         
2679         if (child->isFloating())
2680             prevFloat = child;
2681         child = child->nextSibling();
2682     }
2683     
2684     m_maxWidth = kMax(floatWidths, m_maxWidth);
2685 }
2686
2687 short RenderBlock::lineHeight(bool b, bool isRootLineBox) const
2688 {
2689     // Inline blocks are replaced elements. Otherwise, just pass off to
2690     // the base class.  If we're being queried as though we're the root line
2691     // box, then the fact that we're an inline-block is irrelevant, and we behave
2692     // just like a block.
2693     if (isReplaced() && !isRootLineBox)
2694         return height()+marginTop()+marginBottom();
2695     return RenderFlow::lineHeight(b, isRootLineBox);
2696 }
2697
2698 short RenderBlock::baselinePosition(bool b, bool isRootLineBox) const
2699 {
2700     // Inline blocks are replaced elements. Otherwise, just pass off to
2701     // the base class.  If we're being queried as though we're the root line
2702     // box, then the fact that we're an inline-block is irrelevant, and we behave
2703     // just like a block.
2704     if (isReplaced() && !isRootLineBox)
2705         return height() + marginTop() + marginBottom();
2706     return RenderFlow::baselinePosition(b, isRootLineBox);
2707 }
2708
2709 int RenderBlock::getBaselineOfFirstLineBox() const
2710 {
2711     if (!isBlockFlow())
2712         return RenderFlow::getBaselineOfFirstLineBox();
2713
2714     if (childrenInline()) {
2715         if (m_firstLineBox)
2716             return m_firstLineBox->yPos() + m_firstLineBox->baseline();
2717         else
2718             return -1;
2719     }
2720     else {
2721         for (RenderObject* curr = firstChild(); curr; curr = curr->nextSibling()) {
2722             if (!curr->isFloatingOrPositioned()) {
2723                 int result = curr->getBaselineOfFirstLineBox();
2724                 if (result != -1)
2725                     return curr->yPos() + result; // Translate to our coordinate space.
2726             }
2727         }
2728     }
2729
2730     return -1;
2731 }
2732
2733 RenderBlock* RenderBlock::firstLineBlock() const
2734 {
2735     const RenderObject* firstLineBlock = this;
2736     bool hasPseudo = false;
2737     while (true) {
2738         hasPseudo = firstLineBlock->style()->hasPseudoStyle(RenderStyle::FIRST_LINE);
2739         if (hasPseudo)
2740             break;
2741         RenderObject* parentBlock = firstLineBlock->parent();
2742         if (firstLineBlock->isReplaced() || firstLineBlock->isFloating() || 
2743             !parentBlock || parentBlock->firstChild() != firstLineBlock || !parentBlock->isBlockFlow())
2744             break;
2745         firstLineBlock = parentBlock;
2746     } 
2747     
2748     if (!hasPseudo)
2749         return 0;
2750     
2751     return (RenderBlock*)(firstLineBlock);
2752 }
2753
2754 void RenderBlock::updateFirstLetter()
2755 {
2756     // FIXME: We need to destroy the first-letter object if it is no longer the first child.  Need to find
2757     // an efficient way to check for that situation though before implementing anything.
2758     RenderObject* firstLetterBlock = this;
2759     bool hasPseudoStyle = false;
2760     while (true) {
2761         hasPseudoStyle = firstLetterBlock->style()->hasPseudoStyle(RenderStyle::FIRST_LETTER);
2762         if (hasPseudoStyle)
2763             break;
2764         RenderObject* parentBlock = firstLetterBlock->parent();
2765         if (firstLetterBlock->isReplaced() || !parentBlock || parentBlock->firstChild() != firstLetterBlock || 
2766             !parentBlock->isBlockFlow())
2767             break;
2768         firstLetterBlock = parentBlock;
2769     } 
2770
2771     if (!hasPseudoStyle)
2772         return;
2773     
2774     // Drill into inlines looking for our first text child.
2775     RenderObject* currChild = firstLetterBlock->firstChild();
2776     while (currChild && currChild->needsLayout() && !currChild->isReplaced() && !currChild->isText())
2777         currChild = currChild->firstChild();
2778     
2779     if (currChild && currChild->isText() && !currChild->isBR() && 
2780         currChild->parent()->style()->styleType() != RenderStyle::FIRST_LETTER) {
2781         RenderObject* firstLetterContainer = currChild->parent();
2782         if (!firstLetterContainer)
2783             firstLetterContainer = this;
2784         
2785         RenderText* textObj = static_cast<RenderText*>(currChild);
2786         
2787         // Create our pseudo style now that we have our firstLetterContainer determined.
2788         RenderStyle* pseudoStyle = firstLetterBlock->getPseudoStyle(RenderStyle::FIRST_LETTER,
2789                                                                     firstLetterContainer->style(true));
2790         
2791         // Force inline display (except for floating first-letters)
2792         pseudoStyle->setDisplay( pseudoStyle->isFloating() ? BLOCK : INLINE);
2793         pseudoStyle->setPosition( STATIC ); // CSS2 says first-letter can't be positioned.
2794         
2795         RenderObject* firstLetter = RenderFlow::createAnonymousFlow(document(), pseudoStyle); // anonymous box
2796         firstLetterContainer->addChild(firstLetter, firstLetterContainer->firstChild());
2797         
2798         // The original string is going to be either a generated content string or a DOM node's
2799         // string.  We want the original string before it got transformed in case first-letter has
2800         // no text-transform or a different text-transform applied to it.
2801         DOMStringImpl* oldText = textObj->originalString();
2802         KHTMLAssert(oldText);
2803         
2804         if (oldText && oldText->l >= 1) {
2805             unsigned int length = 0;
2806             while ( length < oldText->l &&
2807                     ( (oldText->s+length)->isSpace() || (oldText->s+length)->isPunct() ) )
2808                 length++;
2809             length++;
2810             //kdDebug( 6040 ) << "letter= '" << DOMString(oldText->substring(0,length)).string() << "'" << endl;
2811             
2812             RenderTextFragment* remainingText = 
2813                 new (renderArena()) RenderTextFragment(textObj->node(), oldText, length, oldText->l-length);
2814             remainingText->setStyle(textObj->style());
2815             if (remainingText->element())
2816                 remainingText->element()->setRenderer(remainingText);
2817             
2818             RenderObject* nextObj = textObj->nextSibling();
2819             firstLetterContainer->removeChild(textObj);
2820             firstLetterContainer->addChild(remainingText, nextObj);
2821             
2822             RenderTextFragment* letter = 
2823                 new (renderArena()) RenderTextFragment(remainingText->node(), oldText, 0, length);
2824             RenderStyle* newStyle = new (renderArena()) RenderStyle();
2825             newStyle->inheritFrom(pseudoStyle);
2826             letter->setStyle(newStyle);
2827             firstLetter->addChild(letter);
2828         }
2829     }
2830 }
2831
2832 bool RenderBlock::inRootBlockContext() const
2833 {
2834     if (isTableCell() || isFloatingOrPositioned() || hasOverflowClip())
2835         return false;
2836     
2837     if (isRoot() || isCanvas())
2838         return true;
2839     
2840     return containingBlock()->inRootBlockContext();
2841 }
2842
2843 // Helper methods for obtaining the last line, computing line counts and heights for line counts
2844 // (crawling into blocks).
2845 static bool shouldCheckLines(RenderObject* obj)
2846 {
2847     return !obj->isFloatingOrPositioned() && !obj->isCompact() && !obj->isRunIn() &&
2848             obj->isBlockFlow() && obj->style()->height().isVariable() &&
2849             (!obj->isFlexibleBox() || obj->style()->boxOrient() == VERTICAL);
2850 }
2851
2852 static RootInlineBox* getLineAtIndex(RenderBlock* block, int i, int& count)
2853 {
2854     if (block->style()->visibility() == VISIBLE) {
2855         if (block->childrenInline()) {
2856             for (RootInlineBox* box = block->firstRootBox(); box; box = box->nextRootBox()) {
2857                 if (count++ == i)
2858                     return box;
2859             }
2860         }
2861         else {
2862             for (RenderObject* obj = block->firstChild(); obj; obj = obj->nextSibling()) {
2863                 if (shouldCheckLines(obj)) {
2864                     RootInlineBox *box = getLineAtIndex(static_cast<RenderBlock*>(obj), i, count);
2865                     if (box)
2866                         return box;
2867                 }
2868             }
2869         }
2870     }
2871     return 0;
2872 }
2873
2874 int getHeightForLineCount(RenderBlock* block, int l, bool includeBottom, int& count)
2875 {
2876     if (block->style()->visibility() == VISIBLE) {
2877         if (block->childrenInline()) {
2878             for (RootInlineBox* box = block->firstRootBox(); box; box = box->nextRootBox()) {
2879                 if (++count == l)
2880                     return box->bottomOverflow() + (includeBottom ? (block->borderBottom() + block->paddingBottom()) : 0);
2881             }
2882         }
2883         else {
2884             RenderObject* normalFlowChildWithoutLines = 0;
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                 else if (!obj->isFloatingOrPositioned() && !obj->isCompact() && !obj->isRunIn())
2892                     normalFlowChildWithoutLines = obj;
2893             }
2894             if (normalFlowChildWithoutLines && l == 0)
2895                 return normalFlowChildWithoutLines->yPos() + normalFlowChildWithoutLines->height() + 
2896                     (includeBottom ? (block->borderBottom() + block->paddingBottom()) : 0);
2897         }
2898     }
2899     
2900     return -1;
2901 }
2902
2903 RootInlineBox* RenderBlock::lineAtIndex(int i)
2904 {
2905     int count = 0;
2906     return getLineAtIndex(this, i, count);
2907 }
2908
2909 int RenderBlock::lineCount()
2910 {
2911     int count = 0;
2912     if (style()->visibility() == VISIBLE) {
2913         if (childrenInline())
2914             for (RootInlineBox* box = firstRootBox(); box; box = box->nextRootBox())
2915                 count++;
2916         else
2917             for (RenderObject* obj = firstChild(); obj; obj = obj->nextSibling())
2918                 if (shouldCheckLines(obj))
2919                     count += static_cast<RenderBlock*>(obj)->lineCount();
2920     }
2921     return count;
2922 }
2923
2924 int RenderBlock::heightForLineCount(int l)
2925 {
2926     int count = 0;
2927     return getHeightForLineCount(this, l, true, count);
2928 }
2929
2930 void RenderBlock::clearTruncation()
2931 {
2932     if (style()->visibility() == VISIBLE) {
2933         if (childrenInline() && hasMarkupTruncation()) {
2934             setHasMarkupTruncation(false);
2935             for (RootInlineBox* box = firstRootBox(); box; box = box->nextRootBox())
2936                 box->clearTruncation();
2937         }
2938         else
2939             for (RenderObject* obj = firstChild(); obj; obj = obj->nextSibling())
2940                 if (shouldCheckLines(obj))
2941                     static_cast<RenderBlock*>(obj)->clearTruncation();
2942     }
2943 }
2944
2945 const char *RenderBlock::renderName() const
2946 {
2947     if (isBody())
2948         return "RenderBody"; // FIXME: Temporary hack until we know that the regression tests pass.
2949     
2950     if (isFloating())
2951         return "RenderBlock (floating)";
2952     if (isPositioned())
2953         return "RenderBlock (positioned)";
2954     if (isAnonymousBlock())
2955         return "RenderBlock (anonymous)";
2956     else if (isAnonymous())
2957         return "RenderBlock (generated)";
2958     if (isRelPositioned())
2959         return "RenderBlock (relative positioned)";
2960     if (isCompact())
2961         return "RenderBlock (compact)";
2962     if (isRunIn())
2963         return "RenderBlock (run-in)";
2964     return "RenderBlock";
2965 }
2966
2967 #ifndef NDEBUG
2968 void RenderBlock::printTree(int indent) const
2969 {
2970     RenderFlow::printTree(indent);
2971
2972     if (m_floatingObjects)
2973     {
2974         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
2975         FloatingObject *r;
2976         for ( ; (r = it.current()); ++it )
2977         {
2978             QString s;
2979             s.fill(' ', indent);
2980             kdDebug() << s << renderName() << ":  " <<
2981                 (r->type == FloatingObject::FloatLeft ? "FloatLeft" : "FloatRight" )  <<
2982                 "[" << r->node->renderName() << ": " << (void*)r->node << "] (" << r->startY << " - " << r->endY << ")" << "width: " << r->width <<
2983                 endl;
2984         }
2985     }
2986 }
2987
2988 void RenderBlock::dump(QTextStream *stream, QString ind) const
2989 {
2990     if (m_childrenInline) { *stream << " childrenInline"; }
2991     if (m_pre) { *stream << " pre"; }
2992     if (m_firstLine) { *stream << " firstLine"; }
2993
2994     if (m_floatingObjects && !m_floatingObjects->isEmpty())
2995     {
2996         *stream << " special(";
2997         QPtrListIterator<FloatingObject> it(*m_floatingObjects);
2998         FloatingObject *r;
2999         bool first = true;
3000         for ( ; (r = it.current()); ++it )
3001         {
3002             if (!first)
3003                 *stream << ",";
3004             *stream << r->node->renderName();
3005             first = false;
3006         }
3007         *stream << ")";
3008     }
3009
3010     // ### EClear m_clearStatus
3011
3012     RenderFlow::dump(stream,ind);
3013 }
3014 #endif
3015
3016 #undef DEBUG
3017 #undef DEBUG_LAYOUT
3018 #undef BOX_DEBUG
3019
3020 } // namespace khtml
3021