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