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