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