99758308ea731099e412d6125b9d3ef86e736e10
[WebKit-https.git] / WebCore / rendering / RenderBlock.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2007 David Smith (catfish.man@gmail.com)
5  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  */
22
23 #include "config.h"
24 #include "RenderBlock.h"
25
26 #include "Document.h"
27 #include "Element.h"
28 #include "FloatQuad.h"
29 #include "Frame.h"
30 #include "FrameView.h"
31 #include "GraphicsContext.h"
32 #include "HTMLNames.h"
33 #include "HitTestResult.h"
34 #include "InlineTextBox.h"
35 #include "RenderImage.h"
36 #include "RenderInline.h"
37 #include "RenderMarquee.h"
38 #include "RenderReplica.h"
39 #include "RenderTableCell.h"
40 #include "RenderTextFragment.h"
41 #include "RenderTheme.h"
42 #include "RenderView.h"
43 #include "SelectionController.h"
44 #include <wtf/StdLibExtras.h>
45
46 using namespace std;
47 using namespace WTF;
48 using namespace Unicode;
49
50 namespace WebCore {
51
52 // Number of pixels to allow as a fudge factor when clicking above or below a line.
53 // clicking up to verticalLineClickFudgeFactor pixels above a line will correspond to the closest point on the line.   
54 const int verticalLineClickFudgeFactor= 3;
55
56 using namespace HTMLNames;
57
58 struct ColumnInfo {
59     ColumnInfo()
60         : m_desiredColumnWidth(0)
61         , m_desiredColumnCount(1)
62         { }
63     int m_desiredColumnWidth;
64     unsigned m_desiredColumnCount;
65     Vector<IntRect> m_columnRects;
66 };
67
68 typedef WTF::HashMap<const RenderBox*, ColumnInfo*> ColumnInfoMap;
69 static ColumnInfoMap* gColumnInfoMap = 0;
70
71 typedef WTF::HashMap<const RenderBlock*, HashSet<RenderBox*>*> PercentHeightDescendantsMap;
72 static PercentHeightDescendantsMap* gPercentHeightDescendantsMap = 0;
73
74 typedef WTF::HashMap<const RenderBox*, HashSet<RenderBlock*>*> PercentHeightContainerMap;
75 static PercentHeightContainerMap* gPercentHeightContainerMap = 0;
76     
77 typedef WTF::HashMap<RenderBlock*, ListHashSet<RenderInline*>*> ContinuationOutlineTableMap;
78
79 // Our MarginInfo state used when laying out block children.
80 RenderBlock::MarginInfo::MarginInfo(RenderBlock* block, int top, int bottom)
81 {
82     // Whether or not we can collapse our own margins with our children.  We don't do this
83     // if we had any border/padding (obviously), if we're the root or HTML elements, or if
84     // we're positioned, floating, a table cell.
85     m_canCollapseWithChildren = !block->isRenderView() && !block->isRoot() && !block->isPositioned() &&
86         !block->isFloating() && !block->isTableCell() && !block->hasOverflowClip() && !block->isInlineBlockOrInlineTable();
87
88     m_canCollapseTopWithChildren = m_canCollapseWithChildren && (top == 0) && block->style()->marginTopCollapse() != MSEPARATE;
89
90     // If any height other than auto is specified in CSS, then we don't collapse our bottom
91     // margins with our children's margins.  To do otherwise would be to risk odd visual
92     // effects when the children overflow out of the parent block and yet still collapse
93     // with it.  We also don't collapse if we have any bottom border/padding.
94     m_canCollapseBottomWithChildren = m_canCollapseWithChildren && (bottom == 0) &&
95         (block->style()->height().isAuto() && block->style()->height().value() == 0) && block->style()->marginBottomCollapse() != MSEPARATE;
96     
97     m_quirkContainer = block->isTableCell() || block->isBody() || block->style()->marginTopCollapse() == MDISCARD || 
98         block->style()->marginBottomCollapse() == MDISCARD;
99
100     m_atTopOfBlock = true;
101     m_atBottomOfBlock = false;
102
103     m_posMargin = m_canCollapseTopWithChildren ? block->maxTopMargin(true) : 0;
104     m_negMargin = m_canCollapseTopWithChildren ? block->maxTopMargin(false) : 0;
105
106     m_selfCollapsingBlockClearedFloat = false;
107     
108     m_topQuirk = m_bottomQuirk = m_determinedTopQuirk = false;
109 }
110
111 // -------------------------------------------------------------------------------------------------------
112
113 RenderBlock::RenderBlock(Node* node)
114       : RenderContainer(node)
115       , m_floatingObjects(0)
116       , m_positionedObjects(0)
117       , m_inlineContinuation(0)
118       , m_maxMargin(0)
119       , m_overflowHeight(0)
120       , m_overflowWidth(0)
121       , m_overflowLeft(0)
122       , m_overflowTop(0)
123       , m_lineHeight(-1)
124 {
125     setChildrenInline(true);
126 }
127
128 RenderBlock::~RenderBlock()
129 {
130     delete m_floatingObjects;
131     delete m_positionedObjects;
132     delete m_maxMargin;
133     
134     if (hasColumns())
135         delete gColumnInfoMap->take(this);
136
137     if (gPercentHeightDescendantsMap) {
138         if (HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->take(this)) {
139             HashSet<RenderBox*>::iterator end = descendantSet->end();
140             for (HashSet<RenderBox*>::iterator descendant = descendantSet->begin(); descendant != end; ++descendant) {
141                 HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->get(*descendant);
142                 ASSERT(containerSet);
143                 if (!containerSet)
144                     continue;
145                 ASSERT(containerSet->contains(this));
146                 containerSet->remove(this);
147                 if (containerSet->isEmpty()) {
148                     gPercentHeightContainerMap->remove(*descendant);
149                     delete containerSet;
150                 }
151             }
152             delete descendantSet;
153         }
154     }
155 }
156
157 void RenderBlock::destroy()
158 {
159     // Detach our continuation first.
160     if (m_inlineContinuation)
161         m_inlineContinuation->destroy();
162     m_inlineContinuation = 0;
163     
164     // Make sure to destroy anonymous children first while they are still connected to the rest of the tree, so that they will
165     // properly dirty line boxes that they are removed from.  Effects that do :before/:after only on hover could crash otherwise.
166     children()->destroyLeftoverChildren();
167
168     if (!documentBeingDestroyed()) {
169         if (firstLineBox()) {
170             // We can't wait for RenderContainer::destroy to clear the selection,
171             // because by then we will have nuked the line boxes.
172             // FIXME: The SelectionController should be responsible for this when it
173             // is notified of DOM mutations.
174             if (isSelectionBorder())
175                 view()->clearSelection();
176
177             // If we are an anonymous block, then our line boxes might have children
178             // that will outlast this block. In the non-anonymous block case those
179             // children will be destroyed by the time we return from this function.
180             if (isAnonymousBlock()) {
181                 for (InlineFlowBox* box = firstLineBox(); box; box = box->nextFlowBox()) {
182                     while (InlineBox* childBox = box->firstChild())
183                         childBox->remove();
184                 }
185             }
186         } else if (isInline() && parent())
187             parent()->dirtyLinesFromChangedChild(this);
188     }
189
190     m_lineBoxes.deleteLineBoxes(renderArena());
191
192     RenderContainer::destroy();
193 }
194
195 void RenderBlock::styleWillChange(RenderStyle::Diff diff, const RenderStyle* newStyle)
196 {
197     setReplaced(newStyle->isDisplayReplacedType());
198     
199     if (style() && parent() && diff == RenderStyle::Layout && style()->position() != newStyle->position()) {
200         if (newStyle->position() == StaticPosition)
201             // Clear our positioned objects list. Our absolutely positioned descendants will be
202             // inserted into our containing block's positioned objects list during layout.
203             removePositionedObjects(0);
204         else if (style()->position() == StaticPosition) {
205             // Remove our absolutely positioned descendants from their current containing block.
206             // They will be inserted into our positioned objects list during layout.
207             RenderObject* cb = parent();
208             while (cb && (cb->style()->position() == StaticPosition || (cb->isInline() && !cb->isReplaced())) && !cb->isRenderView()) {
209                 if (cb->style()->position() == RelativePosition && cb->isInline() && !cb->isReplaced()) {
210                     cb = cb->containingBlock();
211                     break;
212                 }
213                 cb = cb->parent();
214             }
215             
216             if (cb->isRenderBlock())
217                 toRenderBlock(cb)->removePositionedObjects(this);
218         }
219     }
220
221     RenderContainer::styleWillChange(diff, newStyle);
222 }
223
224 void RenderBlock::styleDidChange(RenderStyle::Diff diff, const RenderStyle* oldStyle)
225 {
226     RenderContainer::styleDidChange(diff, oldStyle);
227
228     // FIXME: We could save this call when the change only affected non-inherited properties
229     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
230         if (child->isAnonymousBlock()) {
231             RefPtr<RenderStyle> newStyle = RenderStyle::create();
232             newStyle->inheritFrom(style());
233             newStyle->setDisplay(BLOCK);
234             child->setStyle(newStyle.release());
235         }
236     }
237
238     m_lineHeight = -1;
239
240     // Update pseudos for :before and :after now.
241     if (!isAnonymous() && document()->usesBeforeAfterRules() && canHaveChildren()) {
242         updateBeforeAfterContent(RenderStyle::BEFORE);
243         updateBeforeAfterContent(RenderStyle::AFTER);
244     }
245     updateFirstLetter();
246 }
247
248 void RenderBlock::updateBeforeAfterContent(RenderStyle::PseudoId pseudoId)
249 {
250     // If this is an anonymous wrapper, then the parent applies its own pseudo-element style to it.
251     if (parent() && parent()->createsAnonymousWrapper())
252         return;
253     return children()->updateBeforeAfterContent(this, pseudoId);
254 }
255     
256 void RenderBlock::addChild(RenderObject* newChild, RenderObject* beforeChild)
257 {
258     // Make sure we don't append things after :after-generated content if we have it.
259     if (!beforeChild && isAfterContent(lastChild()))
260         beforeChild = lastChild();
261
262     bool madeBoxesNonInline = false;
263
264     // If the requested beforeChild is not one of our children, then this is because
265     // there is an anonymous container within this object that contains the beforeChild.
266     if (beforeChild && beforeChild->parent() != this) {
267         RenderObject* anonymousChild = beforeChild->parent();
268         ASSERT(anonymousChild);
269
270         while (anonymousChild->parent() != this)
271             anonymousChild = anonymousChild->parent();
272
273         ASSERT(anonymousChild->isAnonymous());
274
275         if (anonymousChild->isAnonymousBlock()) {
276             // Insert the child into the anonymous block box instead of here.
277             if (newChild->isInline() || beforeChild->parent()->firstChild() != beforeChild)
278                 beforeChild->parent()->addChild(newChild, beforeChild);
279             else
280                 addChild(newChild, beforeChild->parent());
281             return;
282         }
283
284         ASSERT(anonymousChild->isTable());
285         if (newChild->isTableCol() && newChild->style()->display() == TABLE_COLUMN_GROUP
286                 || newChild->isRenderBlock() && newChild->style()->display() == TABLE_CAPTION
287                 || newChild->isTableSection()
288                 || newChild->isTableRow()
289                 || newChild->isTableCell()) {
290             // Insert into the anonymous table.
291             anonymousChild->addChild(newChild, beforeChild);
292             return;
293         }
294
295         // Go on to insert before the anonymous table.
296         beforeChild = anonymousChild;
297     }
298
299     // A block has to either have all of its children inline, or all of its children as blocks.
300     // So, if our children are currently inline and a block child has to be inserted, we move all our
301     // inline children into anonymous block boxes.
302     if (childrenInline() && !newChild->isInline() && !newChild->isFloatingOrPositioned()) {
303         // This is a block with inline content. Wrap the inline content in anonymous blocks.
304         makeChildrenNonInline(beforeChild);
305         madeBoxesNonInline = true;
306
307         if (beforeChild && beforeChild->parent() != this) {
308             beforeChild = beforeChild->parent();
309             ASSERT(beforeChild->isAnonymousBlock());
310             ASSERT(beforeChild->parent() == this);
311         }
312     } else if (!childrenInline() && (newChild->isFloatingOrPositioned() || newChild->isInline())) {
313         // If we're inserting an inline child but all of our children are blocks, then we have to make sure
314         // it is put into an anomyous block box. We try to use an existing anonymous box if possible, otherwise
315         // a new one is created and inserted into our list of children in the appropriate position.
316         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : lastChild();
317
318         if (afterChild && afterChild->isAnonymousBlock()) {
319             afterChild->addChild(newChild);
320             return;
321         }
322
323         if (newChild->isInline()) {
324             // No suitable existing anonymous box - create a new one.
325             RenderBlock* newBox = createAnonymousBlock();
326             RenderContainer::addChild(newBox, beforeChild);
327             newBox->addChild(newChild);
328             return;
329         }
330     }
331
332     RenderContainer::addChild(newChild, beforeChild);
333
334     if (madeBoxesNonInline && parent() && isAnonymousBlock() && parent()->isRenderBlock())
335         toRenderBlock(parent())->removeLeftoverAnonymousBlock(this);
336     // this object may be dead here
337 }
338
339 static void getInlineRun(RenderObject* start, RenderObject* boundary,
340                          RenderObject*& inlineRunStart,
341                          RenderObject*& inlineRunEnd)
342 {
343     // Beginning at |start| we find the largest contiguous run of inlines that
344     // we can.  We denote the run with start and end points, |inlineRunStart|
345     // and |inlineRunEnd|.  Note that these two values may be the same if
346     // we encounter only one inline.
347     //
348     // We skip any non-inlines we encounter as long as we haven't found any
349     // inlines yet.
350     //
351     // |boundary| indicates a non-inclusive boundary point.  Regardless of whether |boundary|
352     // is inline or not, we will not include it in a run with inlines before it.  It's as though we encountered
353     // a non-inline.
354     
355     // Start by skipping as many non-inlines as we can.
356     RenderObject * curr = start;
357     bool sawInline;
358     do {
359         while (curr && !(curr->isInline() || curr->isFloatingOrPositioned()))
360             curr = curr->nextSibling();
361         
362         inlineRunStart = inlineRunEnd = curr;
363         
364         if (!curr)
365             return; // No more inline children to be found.
366         
367         sawInline = curr->isInline();
368         
369         curr = curr->nextSibling();
370         while (curr && (curr->isInline() || curr->isFloatingOrPositioned()) && (curr != boundary)) {
371             inlineRunEnd = curr;
372             if (curr->isInline())
373                 sawInline = true;
374             curr = curr->nextSibling();
375         }
376     } while (!sawInline);
377 }
378
379 void RenderBlock::deleteLineBoxTree()
380 {
381     m_lineBoxes.deleteLineBoxTree(renderArena());
382 }
383
384 void RenderBlock::dirtyLineBoxes(bool fullLayout, bool isRootLineBox)
385 {
386     if (!isRootLineBox && isReplaced())
387         return RenderContainer::dirtyLineBoxes(fullLayout, isRootLineBox);
388
389     if (fullLayout)
390         m_lineBoxes.deleteLineBoxes(renderArena());
391     else
392         m_lineBoxes.dirtyLineBoxes();
393 }
394
395 InlineBox* RenderBlock::createInlineBox(bool makePlaceHolderBox, bool isRootLineBox, bool /*isOnlyRun*/)
396 {
397     if (!isRootLineBox && (isReplaced() || makePlaceHolderBox))                     // Inline tables and inline blocks
398         return RenderContainer::createInlineBox(false, isRootLineBox);              // (or positioned element placeholders).
399     InlineFlowBox* flowBox = new (renderArena()) RootInlineBox(this);
400     m_lineBoxes.appendLineBox(flowBox);
401     return flowBox;
402 }
403
404 void RenderBlock::makeChildrenNonInline(RenderObject *insertionPoint)
405 {    
406     // makeChildrenNonInline takes a block whose children are *all* inline and it
407     // makes sure that inline children are coalesced under anonymous
408     // blocks.  If |insertionPoint| is defined, then it represents the insertion point for
409     // the new block child that is causing us to have to wrap all the inlines.  This
410     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
411     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
412     // splitting them.
413     ASSERT(isInlineBlockOrInlineTable() || !isInline());
414     ASSERT(!insertionPoint || insertionPoint->parent() == this);
415
416     setChildrenInline(false);
417
418     RenderObject *child = firstChild();
419     if (!child)
420         return;
421
422     deleteLineBoxTree();
423
424     while (child) {
425         RenderObject *inlineRunStart, *inlineRunEnd;
426         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
427
428         if (!inlineRunStart)
429             break;
430
431         child = inlineRunEnd->nextSibling();
432
433         RenderBlock* box = createAnonymousBlock();
434         insertChildNode(box, inlineRunStart);
435         RenderObject* o = inlineRunStart;
436         while(o != inlineRunEnd)
437         {
438             RenderObject* no = o;
439             o = no->nextSibling();
440             box->moveChildNode(no);
441         }
442         box->moveChildNode(inlineRunEnd);
443     }
444
445 #ifndef NDEBUG
446     for (RenderObject *c = firstChild(); c; c = c->nextSibling())
447         ASSERT(!c->isInline());
448 #endif
449
450     repaint();
451 }
452
453 void RenderBlock::removeLeftoverAnonymousBlock(RenderBlock* child)
454 {
455     ASSERT(child->isAnonymousBlock());
456     ASSERT(!child->childrenInline());
457     
458     if (child->inlineContinuation()) 
459         return;
460     
461     RenderObject* firstAnChild = child->m_children.firstChild();
462     RenderObject* lastAnChild = child->m_children.lastChild();
463     if (firstAnChild) {
464         RenderObject* o = firstAnChild;
465         while (o) {
466             o->setParent(this);
467             o = o->nextSibling();
468         }
469         firstAnChild->setPreviousSibling(child->previousSibling());
470         lastAnChild->setNextSibling(child->nextSibling());
471         if (child->previousSibling())
472             child->previousSibling()->setNextSibling(firstAnChild);
473         if (child->nextSibling())
474             child->nextSibling()->setPreviousSibling(lastAnChild);
475     } else {
476         if (child->previousSibling())
477             child->previousSibling()->setNextSibling(child->nextSibling());
478         if (child->nextSibling())
479             child->nextSibling()->setPreviousSibling(child->previousSibling());
480     }
481     if (child == m_children.firstChild())
482         m_children.setFirstChild(firstAnChild);
483     if (child == m_children.lastChild())
484         m_children.setLastChild(lastAnChild);
485     child->setParent(0);
486     child->setPreviousSibling(0);
487     child->setNextSibling(0);
488     
489     child->children()->setFirstChild(0);
490     child->m_next = 0;
491
492     child->destroy();
493 }
494
495 void RenderBlock::removeChild(RenderObject* oldChild)
496 {
497     // If this child is a block, and if our previous and next siblings are
498     // both anonymous blocks with inline content, then we can go ahead and
499     // fold the inline content back together.
500     RenderObject* prev = oldChild->previousSibling();
501     RenderObject* next = oldChild->nextSibling();
502     bool canDeleteAnonymousBlocks = !documentBeingDestroyed() && !isInline() && !oldChild->isInline() && 
503                                     (!oldChild->isRenderBlock() || !toRenderBlock(oldChild)->inlineContinuation()) && 
504                                     (!prev || (prev->isAnonymousBlock() && prev->childrenInline())) &&
505                                     (!next || (next->isAnonymousBlock() && next->childrenInline()));
506     if (canDeleteAnonymousBlocks && prev && next) {
507         // Take all the children out of the |next| block and put them in
508         // the |prev| block.
509         prev->setNeedsLayoutAndPrefWidthsRecalc();
510         RenderObject* o = next->firstChild();
511         while (o) {
512             RenderObject* no = o;
513             o = no->nextSibling();
514             prev->moveChildNode(no);
515         }
516  
517         RenderBlock* nextBlock = toRenderBlock(next);
518         nextBlock->deleteLineBoxTree();
519         
520         // Nuke the now-empty block.
521         next->destroy();
522     }
523
524     RenderContainer::removeChild(oldChild);
525
526     RenderObject* child = prev ? prev : next;
527     if (canDeleteAnonymousBlocks && child && !child->previousSibling() && !child->nextSibling() && !isFlexibleBox()) {
528         // The removal has knocked us down to containing only a single anonymous
529         // box.  We can go ahead and pull the content right back up into our
530         // box.
531         setNeedsLayoutAndPrefWidthsRecalc();
532         RenderBlock* anonBlock = toRenderBlock(removeChildNode(child, false));
533         setChildrenInline(true);
534         RenderObject* o = anonBlock->firstChild();
535         while (o) {
536             RenderObject* no = o;
537             o = no->nextSibling();
538             moveChildNode(no);
539         }
540
541         // Delete the now-empty block's lines and nuke it.
542         anonBlock->deleteLineBoxTree();
543         anonBlock->destroy();
544     }
545 }
546
547 int RenderBlock::overflowHeight(bool includeInterior) const
548 {
549     if (!includeInterior && hasOverflowClip()) {
550         int shadowHeight = 0;
551         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
552             shadowHeight = max(boxShadow->y + boxShadow->blur, shadowHeight);
553         int inflatedHeight = height() + shadowHeight;
554         if (hasReflection())
555             inflatedHeight = max(inflatedHeight, reflectionBox().bottom());
556         return inflatedHeight;
557     }
558     return m_overflowHeight;
559 }
560
561 int RenderBlock::overflowWidth(bool includeInterior) const
562 {
563     if (!includeInterior && hasOverflowClip()) {
564         int shadowWidth = 0;
565         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
566             shadowWidth = max(boxShadow->x + boxShadow->blur, shadowWidth);
567         int inflatedWidth = width() + shadowWidth;
568         if (hasReflection())
569             inflatedWidth = max(inflatedWidth, reflectionBox().right());
570         return inflatedWidth;
571     }
572     return m_overflowWidth;
573 }
574
575 int RenderBlock::overflowLeft(bool includeInterior) const
576 {
577     if (!includeInterior && hasOverflowClip()) {
578         int shadowLeft = 0;
579         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
580             shadowLeft = min(boxShadow->x - boxShadow->blur, shadowLeft);
581         int left = shadowLeft;
582         if (hasReflection())
583             left = min(left, reflectionBox().x());
584         return left;
585     }
586     return m_overflowLeft;
587 }
588
589 int RenderBlock::overflowTop(bool includeInterior) const
590 {
591     if (!includeInterior && hasOverflowClip()) {
592         int shadowTop = 0;
593         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
594             shadowTop = min(boxShadow->y - boxShadow->blur, shadowTop);
595         int top = shadowTop;
596         if (hasReflection())
597             top = min(top, reflectionBox().y());
598         return top;
599     }
600     return m_overflowTop;
601 }
602
603 IntRect RenderBlock::overflowRect(bool includeInterior) const
604 {
605     if (!includeInterior && hasOverflowClip()) {
606         IntRect box = borderBoxRect();
607         int shadowLeft = 0;
608         int shadowRight = 0;
609         int shadowTop = 0;
610         int shadowBottom = 0;
611
612         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next) {
613             shadowLeft = min(boxShadow->x - boxShadow->blur, shadowLeft);
614             shadowRight = max(boxShadow->x + boxShadow->blur, shadowRight);
615             shadowTop = min(boxShadow->y - boxShadow->blur, shadowTop);
616             shadowBottom = max(boxShadow->y + boxShadow->blur, shadowBottom);
617         }
618
619         box.move(shadowLeft, shadowTop);
620         box.setWidth(box.width() - shadowLeft + shadowRight);
621         box.setHeight(box.height() - shadowTop + shadowBottom);
622
623         if (hasReflection()) {
624             IntRect reflection(reflectionBox());
625             int reflectTop = min(box.y(), reflection.y());
626             int reflectBottom = max(box.bottom(), reflection.bottom());
627             box.setHeight(reflectBottom - reflectTop);
628             box.setY(reflectTop);
629             
630             int reflectLeft = min(box.x(), reflection.x());
631             int reflectRight = max(box.right(), reflection.right());
632             box.setWidth(reflectRight - reflectLeft);
633             box.setX(reflectLeft);
634         }
635         return box;
636     }
637
638     if (!includeInterior && hasOverflowClip())
639         return borderBoxRect();
640     int l = overflowLeft(includeInterior);
641     int t = overflowTop(includeInterior);
642     return IntRect(l, t, overflowWidth(includeInterior) - l, max(overflowHeight(includeInterior), height()) - t);
643 }
644
645 bool RenderBlock::isSelfCollapsingBlock() const
646 {
647     // We are not self-collapsing if we
648     // (a) have a non-zero height according to layout (an optimization to avoid wasting time)
649     // (b) are a table,
650     // (c) have border/padding,
651     // (d) have a min-height
652     // (e) have specified that one of our margins can't collapse using a CSS extension
653     if (height() > 0 ||
654         isTable() || (borderBottom() + paddingBottom() + borderTop() + paddingTop()) != 0 ||
655         style()->minHeight().isPositive() || 
656         style()->marginTopCollapse() == MSEPARATE || style()->marginBottomCollapse() == MSEPARATE)
657         return false;
658
659     bool hasAutoHeight = style()->height().isAuto();
660     if (style()->height().isPercent() && !style()->htmlHacks()) {
661         hasAutoHeight = true;
662         for (RenderBlock* cb = containingBlock(); !cb->isRenderView(); cb = cb->containingBlock()) {
663             if (cb->style()->height().isFixed() || cb->isTableCell())
664                 hasAutoHeight = false;
665         }
666     }
667
668     // If the height is 0 or auto, then whether or not we are a self-collapsing block depends
669     // on whether we have content that is all self-collapsing or not.
670     if (hasAutoHeight || ((style()->height().isFixed() || style()->height().isPercent()) && style()->height().isZero())) {
671         // If the block has inline children, see if we generated any line boxes.  If we have any
672         // line boxes, then we can't be self-collapsing, since we have content.
673         if (childrenInline())
674             return !firstLineBox();
675         
676         // Whether or not we collapse is dependent on whether all our normal flow children
677         // are also self-collapsing.
678         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
679             if (child->isFloatingOrPositioned())
680                 continue;
681             if (!child->isSelfCollapsingBlock())
682                 return false;
683         }
684         return true;
685     }
686     return false;
687 }
688
689 void RenderBlock::layout()
690 {
691     // Update our first letter info now.
692     updateFirstLetter();
693
694     // Table cells call layoutBlock directly, so don't add any logic here.  Put code into
695     // layoutBlock().
696     layoutBlock(false);
697     
698     // It's safe to check for control clip here, since controls can never be table cells.
699     if (hasControlClip()) {
700         // Because of the lightweight clip, there can never be any overflow from children.
701         m_overflowWidth = width();
702         m_overflowHeight = height();
703         m_overflowLeft = 0;
704         m_overflowTop = 0;
705     }
706 }
707
708 void RenderBlock::layoutBlock(bool relayoutChildren)
709 {
710     ASSERT(needsLayout());
711
712     if (isInline() && !isInlineBlockOrInlineTable()) // Inline <form>s inside various table elements can
713         return;                                      // cause us to come in here.  Just bail.
714
715     if (!relayoutChildren && layoutOnlyPositionedObjects())
716         return;
717
718     LayoutRepainter repainter(*this, m_everHadLayout && checkForRepaintDuringLayout());
719     LayoutStateMaintainer statePusher(view(), this, IntSize(x(), y()), hasColumns() || hasTransform() || hasReflection());
720
721     int oldWidth = width();
722     int oldColumnWidth = desiredColumnWidth();
723
724     calcWidth();
725     calcColumnWidth();
726
727     m_overflowWidth = width();
728     m_overflowLeft = 0;
729
730     if (oldWidth != width() || oldColumnWidth != desiredColumnWidth())
731         relayoutChildren = true;
732
733     clearFloats();
734
735     int previousHeight = height();
736     setHeight(0);
737
738     m_overflowHeight = 0;
739
740     // We use four values, maxTopPos, maxPosNeg, maxBottomPos, and maxBottomNeg, to track
741     // our current maximal positive and negative margins.  These values are used when we
742     // are collapsed with adjacent blocks, so for example, if you have block A and B
743     // collapsing together, then you'd take the maximal positive margin from both A and B
744     // and subtract it from the maximal negative margin from both A and B to get the
745     // true collapsed margin.  This algorithm is recursive, so when we finish layout()
746     // our block knows its current maximal positive/negative values.
747     //
748     // Start out by setting our margin values to our current margins.  Table cells have
749     // no margins, so we don't fill in the values for table cells.
750     bool isCell = isTableCell();
751     if (!isCell) {
752         initMaxMarginValues();
753
754         setTopMarginQuirk(style()->marginTop().quirk());
755         setBottomMarginQuirk(style()->marginBottom().quirk());
756
757         Node* node = element();
758         if (node && node->hasTagName(formTag) && static_cast<HTMLFormElement*>(node)->isMalformed()) {
759             // See if this form is malformed (i.e., unclosed). If so, don't give the form
760             // a bottom margin.
761             setMaxBottomMargins(0, 0);
762         }
763     }
764
765     // For overflow:scroll blocks, ensure we have both scrollbars in place always.
766     if (scrollsOverflow()) {
767         if (style()->overflowX() == OSCROLL)
768             m_layer->setHasHorizontalScrollbar(true);
769         if (style()->overflowY() == OSCROLL)
770             m_layer->setHasVerticalScrollbar(true);
771     }
772
773     int repaintTop = 0;
774     int repaintBottom = 0;
775     int maxFloatBottom = 0;
776     if (childrenInline())
777         layoutInlineChildren(relayoutChildren, repaintTop, repaintBottom);
778     else
779         layoutBlockChildren(relayoutChildren, maxFloatBottom);
780
781     // Expand our intrinsic height to encompass floats.
782     int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
783     if (floatBottom() > (height() - toAdd) && expandsToEncloseOverhangingFloats())
784         setHeight(floatBottom() + toAdd);
785     
786     // Now lay out our columns within this intrinsic height, since they can slightly affect the intrinsic height as
787     // we adjust for clean column breaks.
788     int singleColumnBottom = layoutColumns();
789
790     // Calculate our new height.
791     int oldHeight = height();
792     calcHeight();
793     if (oldHeight != height()) {
794         if (oldHeight > height() && maxFloatBottom > height() && !childrenInline()) {
795             // One of our children's floats may have become an overhanging float for us. We need to look for it.
796             for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
797                 if (child->isBlockFlow() && !child->isFloatingOrPositioned()) {
798                     RenderBlock* block = toRenderBlock(child);
799                     if (block->floatBottom() + block->y() > height())
800                         addOverhangingFloats(block, -block->x(), -block->y(), false);
801                 }
802             }
803         }
804         // We have to rebalance columns to the new height.
805         layoutColumns(singleColumnBottom);
806
807         // If the block got expanded in size, then increase our overflowheight to match.
808         if (m_overflowHeight > height())
809             m_overflowHeight -= toAdd;
810         if (m_overflowHeight < height())
811             m_overflowHeight = height();
812     }
813     if (previousHeight != height())
814         relayoutChildren = true;
815
816     if ((isCell || isInline() || isFloatingOrPositioned() || isRoot()) && !hasOverflowClip() && !hasControlClip())
817         addVisualOverflow(floatRect());
818
819     layoutPositionedObjects(relayoutChildren || isRoot());
820
821     positionListMarker();
822
823     // Always ensure our overflow width/height are at least as large as our width/height.
824     m_overflowWidth = max(m_overflowWidth, width());
825     m_overflowHeight = max(m_overflowHeight, height());
826
827     if (!hasOverflowClip()) {
828         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next) {
829             m_overflowLeft = min(m_overflowLeft, boxShadow->x - boxShadow->blur);
830             m_overflowWidth = max(m_overflowWidth, width() + boxShadow->x + boxShadow->blur);
831             m_overflowTop = min(m_overflowTop, boxShadow->y - boxShadow->blur);
832             m_overflowHeight = max(m_overflowHeight, height() + boxShadow->y + boxShadow->blur);
833         }
834         
835         if (hasReflection()) {
836             m_overflowTop = min(m_overflowTop, reflectionBox().y());
837             m_overflowHeight = max(m_overflowHeight, reflectionBox().bottom());
838         }
839     }
840
841     statePusher.pop();
842
843     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
844     // we overflow or not.
845     if (hasOverflowClip())
846         m_layer->updateScrollInfoAfterLayout();
847
848     // Repaint with our new bounds if they are different from our old bounds.
849     bool didFullRepaint = repainter.repaintAfterLayout();
850     if (!didFullRepaint && repaintTop != repaintBottom && (style()->visibility() == VISIBLE || enclosingLayer()->hasVisibleContent())) {
851         IntRect repaintRect(m_overflowLeft, repaintTop, m_overflowWidth - m_overflowLeft, repaintBottom - repaintTop);
852
853         // FIXME: Deal with multiple column repainting.  We have to split the repaint
854         // rect up into multiple rects if it spans columns.
855
856         repaintRect.inflate(maximalOutlineSize(PaintPhaseOutline));
857         
858         if (hasOverflowClip()) {
859             // Adjust repaint rect for scroll offset
860             int x = repaintRect.x();
861             int y = repaintRect.y();
862             layer()->subtractScrolledContentOffset(x, y);
863             repaintRect.setX(x);
864             repaintRect.setY(y);
865
866             // Don't allow this rect to spill out of our overflow box.
867             repaintRect.intersect(IntRect(0, 0, width(), height()));
868         }
869
870         // Make sure the rect is still non-empty after intersecting for overflow above
871         if (!repaintRect.isEmpty()) {
872             repaintRectangle(repaintRect); // We need to do a partial repaint of our content.
873             if (hasReflection())
874                 layer()->reflection()->repaintRectangle(repaintRect);
875         }
876     }
877     setNeedsLayout(false);
878 }
879
880 bool RenderBlock::expandsToEncloseOverhangingFloats() const
881 {
882     return isInlineBlockOrInlineTable() || isFloatingOrPositioned() || hasOverflowClip() || (parent() && parent()->isFlexibleBox()) || hasColumns() || isTableCell() || isFieldset();
883 }
884
885 void RenderBlock::adjustPositionedBlock(RenderBox* child, const MarginInfo& marginInfo)
886 {
887     if (child->hasStaticX()) {
888         if (style()->direction() == LTR)
889             child->setStaticX(borderLeft() + paddingLeft());
890         else
891             child->setStaticX(borderRight() + paddingRight());
892     }
893
894     if (child->hasStaticY()) {
895         int y = height();
896         if (!marginInfo.canCollapseWithTop()) {
897             child->calcVerticalMargins();
898             int marginTop = child->marginTop();
899             int collapsedTopPos = marginInfo.posMargin();
900             int collapsedTopNeg = marginInfo.negMargin();
901             if (marginTop > 0) {
902                 if (marginTop > collapsedTopPos)
903                     collapsedTopPos = marginTop;
904             } else {
905                 if (-marginTop > collapsedTopNeg)
906                     collapsedTopNeg = -marginTop;
907             }
908             y += (collapsedTopPos - collapsedTopNeg) - marginTop;
909         }
910         child->setStaticY(y);
911     }
912 }
913
914 void RenderBlock::adjustFloatingBlock(const MarginInfo& marginInfo)
915 {
916     // The float should be positioned taking into account the bottom margin
917     // of the previous flow.  We add that margin into the height, get the
918     // float positioned properly, and then subtract the margin out of the
919     // height again.  In the case of self-collapsing blocks, we always just
920     // use the top margins, since the self-collapsing block collapsed its
921     // own bottom margin into its top margin.
922     //
923     // Note also that the previous flow may collapse its margin into the top of
924     // our block.  If this is the case, then we do not add the margin in to our
925     // height when computing the position of the float.   This condition can be tested
926     // for by simply calling canCollapseWithTop.  See
927     // http://www.hixie.ch/tests/adhoc/css/box/block/margin-collapse/046.html for
928     // an example of this scenario.
929     int marginOffset = marginInfo.canCollapseWithTop() ? 0 : marginInfo.margin();
930     setHeight(height() + marginOffset);
931     positionNewFloats();
932     setHeight(height() - marginOffset);
933 }
934
935 RenderBox* RenderBlock::handleSpecialChild(RenderBox* child, const MarginInfo& marginInfo, bool& handled)
936 {
937     // Handle positioned children first.
938     RenderBox* next = handlePositionedChild(child, marginInfo, handled);
939     if (handled) return next;
940     
941     // Handle floating children next.
942     next = handleFloatingChild(child, marginInfo, handled);
943     if (handled) return next;
944
945     // Finally, see if we have a run-in element.
946     return handleRunInChild(child, handled);
947 }
948
949
950 RenderBox* RenderBlock::handlePositionedChild(RenderBox* child, const MarginInfo& marginInfo, bool& handled)
951 {
952     if (child->isPositioned()) {
953         handled = true;
954         child->containingBlock()->insertPositionedObject(child);
955         adjustPositionedBlock(child, marginInfo);
956         return child->nextSiblingBox();
957     }
958
959     return 0;
960 }
961
962 RenderBox* RenderBlock::handleFloatingChild(RenderBox* child, const MarginInfo& marginInfo, bool& handled)
963 {
964     if (child->isFloating()) {
965         handled = true;
966         insertFloatingObject(child);
967         adjustFloatingBlock(marginInfo);
968         return child->nextSiblingBox();
969     }
970     
971     return 0;
972 }
973
974 RenderBox* RenderBlock::handleRunInChild(RenderBox* blockRunIn, bool& handled)
975 {
976     // See if we have a run-in element with inline children.  If the
977     // children aren't inline, then just treat the run-in as a normal
978     // block.
979     if (blockRunIn->isRunIn() && (blockRunIn->childrenInline() || blockRunIn->isReplaced())) {
980         // Get the next non-positioned/non-floating RenderBlock.
981         RenderObject* curr = blockRunIn->nextSibling();
982         while (curr && curr->isFloatingOrPositioned())
983             curr = curr->nextSibling();
984         if (curr && (curr->isRenderBlock() && curr->childrenInline() && !curr->isRunIn())) {
985             // The block acts like an inline, so just null out its
986             // position.
987             handled = true;
988             
989             // Remove the old child.
990             RenderBox* next = blockRunIn->nextSiblingBox();
991             removeChildNode(blockRunIn);
992
993             // Create an inline.
994             RenderInline* inlineRunIn = new (renderArena()) RenderInline(blockRunIn->node());
995             inlineRunIn->setStyle(blockRunIn->style());
996
997             // Move the nodes from the old child to the new child.
998             for (RenderObject* runInChild = blockRunIn->firstChild(); runInChild; runInChild = runInChild->nextSibling())
999                 inlineRunIn->moveChildNode(runInChild);
1000
1001             // Now insert the new child under |curr|.
1002             curr->insertChildNode(inlineRunIn, curr->firstChild());
1003             
1004             // If the run-in had an element, we need to set the new renderer.
1005             if (blockRunIn->element())
1006                 blockRunIn->element()->setRenderer(inlineRunIn);
1007             
1008             // Destroy the block run-in.
1009             blockRunIn->destroy();
1010
1011             return next;
1012         }
1013     }
1014     return 0;
1015 }
1016
1017 void RenderBlock::collapseMargins(RenderBox* child, MarginInfo& marginInfo, int yPosEstimate)
1018 {
1019     // Get our max pos and neg top margins.
1020     int posTop = child->maxTopMargin(true);
1021     int negTop = child->maxTopMargin(false);
1022
1023     // For self-collapsing blocks, collapse our bottom margins into our
1024     // top to get new posTop and negTop values.
1025     if (child->isSelfCollapsingBlock()) {
1026         posTop = max(posTop, child->maxBottomMargin(true));
1027         negTop = max(negTop, child->maxBottomMargin(false));
1028     }
1029     
1030     // See if the top margin is quirky. We only care if this child has
1031     // margins that will collapse with us.
1032     bool topQuirk = child->isTopMarginQuirk() || style()->marginTopCollapse() == MDISCARD;
1033
1034     if (marginInfo.canCollapseWithTop()) {
1035         // This child is collapsing with the top of the
1036         // block.  If it has larger margin values, then we need to update
1037         // our own maximal values.
1038         if (!style()->htmlHacks() || !marginInfo.quirkContainer() || !topQuirk)
1039             setMaxTopMargins(max(posTop, maxTopPosMargin()), max(negTop, maxTopNegMargin()));
1040
1041         // The minute any of the margins involved isn't a quirk, don't
1042         // collapse it away, even if the margin is smaller (www.webreference.com
1043         // has an example of this, a <dt> with 0.8em author-specified inside
1044         // a <dl> inside a <td>.
1045         if (!marginInfo.determinedTopQuirk() && !topQuirk && (posTop-negTop)) {
1046             setTopMarginQuirk(false);
1047             marginInfo.setDeterminedTopQuirk(true);
1048         }
1049
1050         if (!marginInfo.determinedTopQuirk() && topQuirk && marginTop() == 0)
1051             // We have no top margin and our top child has a quirky margin.
1052             // We will pick up this quirky margin and pass it through.
1053             // This deals with the <td><div><p> case.
1054             // Don't do this for a block that split two inlines though.  You do
1055             // still apply margins in this case.
1056             setTopMarginQuirk(true);
1057     }
1058
1059     if (marginInfo.quirkContainer() && marginInfo.atTopOfBlock() && (posTop - negTop))
1060         marginInfo.setTopQuirk(topQuirk);
1061
1062     int ypos = height();
1063     if (child->isSelfCollapsingBlock()) {
1064         // This child has no height.  We need to compute our
1065         // position before we collapse the child's margins together,
1066         // so that we can get an accurate position for the zero-height block.
1067         int collapsedTopPos = max(marginInfo.posMargin(), child->maxTopMargin(true));
1068         int collapsedTopNeg = max(marginInfo.negMargin(), child->maxTopMargin(false));
1069         marginInfo.setMargin(collapsedTopPos, collapsedTopNeg);
1070         
1071         // Now collapse the child's margins together, which means examining our
1072         // bottom margin values as well. 
1073         marginInfo.setPosMarginIfLarger(child->maxBottomMargin(true));
1074         marginInfo.setNegMarginIfLarger(child->maxBottomMargin(false));
1075
1076         if (!marginInfo.canCollapseWithTop())
1077             // We need to make sure that the position of the self-collapsing block
1078             // is correct, since it could have overflowing content
1079             // that needs to be positioned correctly (e.g., a block that
1080             // had a specified height of 0 but that actually had subcontent).
1081             ypos = height() + collapsedTopPos - collapsedTopNeg;
1082     }
1083     else {
1084         if (child->style()->marginTopCollapse() == MSEPARATE) {
1085             setHeight(height() + marginInfo.margin() + child->marginTop());
1086             ypos = height();
1087         }
1088         else if (!marginInfo.atTopOfBlock() ||
1089             (!marginInfo.canCollapseTopWithChildren()
1090              && (!style()->htmlHacks() || !marginInfo.quirkContainer() || !marginInfo.topQuirk()))) {
1091             // We're collapsing with a previous sibling's margins and not
1092             // with the top of the block.
1093             setHeight(height() + max(marginInfo.posMargin(), posTop) - max(marginInfo.negMargin(), negTop));
1094             ypos = height();
1095         }
1096
1097         marginInfo.setPosMargin(child->maxBottomMargin(true));
1098         marginInfo.setNegMargin(child->maxBottomMargin(false));
1099
1100         if (marginInfo.margin())
1101             marginInfo.setBottomQuirk(child->isBottomMarginQuirk() || style()->marginBottomCollapse() == MDISCARD);
1102
1103         marginInfo.setSelfCollapsingBlockClearedFloat(false);
1104     }
1105
1106     view()->addLayoutDelta(IntSize(0, yPosEstimate - ypos));
1107     child->setLocation(child->x(), ypos);
1108     if (ypos != yPosEstimate) {
1109         if (child->shrinkToAvoidFloats())
1110             // The child's width depends on the line width.
1111             // When the child shifts to clear an item, its width can
1112             // change (because it has more available line width).
1113             // So go ahead and mark the item as dirty.
1114             child->setChildNeedsLayout(true, false);
1115
1116         if (!child->avoidsFloats() && child->containsFloats())
1117             toRenderBlock(child)->markAllDescendantsWithFloatsForLayout();
1118
1119         // Our guess was wrong. Make the child lay itself out again.
1120         child->layoutIfNeeded();
1121     }
1122 }
1123
1124 void RenderBlock::clearFloatsIfNeeded(RenderBox* child, MarginInfo& marginInfo, int oldTopPosMargin, int oldTopNegMargin)
1125 {
1126     int heightIncrease = getClearDelta(child);
1127     if (!heightIncrease)
1128         return;
1129
1130     // The child needs to be lowered.  Move the child so that it just clears the float.
1131     view()->addLayoutDelta(IntSize(0, -heightIncrease));
1132     child->setLocation(child->x(), child->y() + heightIncrease);
1133
1134     if (child->isSelfCollapsingBlock()) {
1135         // For self-collapsing blocks that clear, they can still collapse their
1136         // margins with following siblings.  Reset the current margins to represent
1137         // the self-collapsing block's margins only.
1138         marginInfo.setPosMargin(max(child->maxTopMargin(true), child->maxBottomMargin(true)));
1139         marginInfo.setNegMargin(max(child->maxTopMargin(false), child->maxBottomMargin(false)));
1140         
1141         // Adjust our height such that we are ready to be collapsed with subsequent siblings.
1142         setHeight(child->y() - max(0, marginInfo.margin()));
1143         
1144         // Set a flag that we cleared a float so that we know both to increase the height of the block
1145         // to compensate for the clear and to avoid collapsing our margins with the parent block's
1146         // bottom margin.
1147         marginInfo.setSelfCollapsingBlockClearedFloat(true);
1148     } else
1149         // Increase our height by the amount we had to clear.
1150         setHeight(height() + heightIncrease);
1151     
1152     if (marginInfo.canCollapseWithTop()) {
1153         // We can no longer collapse with the top of the block since a clear
1154         // occurred.  The empty blocks collapse into the cleared block.
1155         // FIXME: This isn't quite correct.  Need clarification for what to do
1156         // if the height the cleared block is offset by is smaller than the
1157         // margins involved.
1158         setMaxTopMargins(oldTopPosMargin, oldTopNegMargin);
1159         marginInfo.setAtTopOfBlock(false);
1160     }
1161
1162     // If our value of clear caused us to be repositioned vertically to be
1163     // underneath a float, we might have to do another layout to take into account
1164     // the extra space we now have available.
1165     if (child->shrinkToAvoidFloats())
1166         // The child's width depends on the line width.
1167         // When the child shifts to clear an item, its width can
1168         // change (because it has more available line width).
1169         // So go ahead and mark the item as dirty.
1170         child->setChildNeedsLayout(true, false);
1171     if (!child->avoidsFloats() && child->containsFloats())
1172         toRenderBlock(child)->markAllDescendantsWithFloatsForLayout();
1173     child->layoutIfNeeded();
1174 }
1175
1176 int RenderBlock::estimateVerticalPosition(RenderBox* child, const MarginInfo& marginInfo)
1177 {
1178     // FIXME: We need to eliminate the estimation of vertical position, because when it's wrong we sometimes trigger a pathological
1179     // relayout if there are intruding floats.
1180     int yPosEstimate = height();
1181     if (!marginInfo.canCollapseWithTop()) {
1182         int childMarginTop = child->selfNeedsLayout() ? child->marginTop() : child->collapsedMarginTop();
1183         yPosEstimate += max(marginInfo.margin(), childMarginTop);
1184     }
1185     return yPosEstimate;
1186 }
1187
1188 void RenderBlock::determineHorizontalPosition(RenderBox* child)
1189 {
1190     if (style()->direction() == LTR) {
1191         int xPos = borderLeft() + paddingLeft();
1192         
1193         // Add in our left margin.
1194         int chPos = xPos + child->marginLeft();
1195         
1196         // Some objects (e.g., tables, horizontal rules, overflow:auto blocks) avoid floats.  They need
1197         // to shift over as necessary to dodge any floats that might get in the way.
1198         if (child->avoidsFloats()) {
1199             int leftOff = leftOffset(height(), false);
1200             if (style()->textAlign() != WEBKIT_CENTER && child->style()->marginLeft().type() != Auto) {
1201                 if (child->marginLeft() < 0)
1202                     leftOff += child->marginLeft();
1203                 chPos = max(chPos, leftOff); // Let the float sit in the child's margin if it can fit.
1204             }
1205             else if (leftOff != xPos) {
1206                 // The object is shifting right. The object might be centered, so we need to
1207                 // recalculate our horizontal margins. Note that the containing block content
1208                 // width computation will take into account the delta between |leftOff| and |xPos|
1209                 // so that we can just pass the content width in directly to the |calcHorizontalMargins|
1210                 // function.
1211                 child->calcHorizontalMargins(child->style()->marginLeft(), child->style()->marginRight(), lineWidth(child->y(), false));
1212                 chPos = leftOff + child->marginLeft();
1213             }
1214         }
1215         view()->addLayoutDelta(IntSize(child->x() - chPos, 0));
1216         child->setLocation(chPos, child->y());
1217     } else {
1218         int xPos = width() - borderRight() - paddingRight() - verticalScrollbarWidth();
1219         int chPos = xPos - (child->width() + child->marginRight());
1220         if (child->avoidsFloats()) {
1221             int rightOff = rightOffset(height(), false);
1222             if (style()->textAlign() != WEBKIT_CENTER && child->style()->marginRight().type() != Auto) {
1223                 if (child->marginRight() < 0)
1224                     rightOff -= child->marginRight();
1225                 chPos = min(chPos, rightOff - child->width()); // Let the float sit in the child's margin if it can fit.
1226             } else if (rightOff != xPos) {
1227                 // The object is shifting left. The object might be centered, so we need to
1228                 // recalculate our horizontal margins. Note that the containing block content
1229                 // width computation will take into account the delta between |rightOff| and |xPos|
1230                 // so that we can just pass the content width in directly to the |calcHorizontalMargins|
1231                 // function.
1232                 child->calcHorizontalMargins(child->style()->marginLeft(), child->style()->marginRight(), lineWidth(child->y(), false));
1233                 chPos = rightOff - child->marginRight() - child->width();
1234             }
1235         }
1236         view()->addLayoutDelta(IntSize(child->x() - chPos, 0));
1237         child->setLocation(chPos, child->y());
1238     }
1239 }
1240
1241 void RenderBlock::setCollapsedBottomMargin(const MarginInfo& marginInfo)
1242 {
1243     if (marginInfo.canCollapseWithBottom() && !marginInfo.canCollapseWithTop()) {
1244         // Update our max pos/neg bottom margins, since we collapsed our bottom margins
1245         // with our children.
1246         setMaxBottomMargins(max(maxBottomPosMargin(), marginInfo.posMargin()), max(maxBottomNegMargin(), marginInfo.negMargin()));
1247
1248         if (!marginInfo.bottomQuirk())
1249             setBottomMarginQuirk(false);
1250
1251         if (marginInfo.bottomQuirk() && marginBottom() == 0)
1252             // We have no bottom margin and our last child has a quirky margin.
1253             // We will pick up this quirky margin and pass it through.
1254             // This deals with the <td><div><p> case.
1255             setBottomMarginQuirk(true);
1256     }
1257 }
1258
1259 void RenderBlock::handleBottomOfBlock(int top, int bottom, MarginInfo& marginInfo)
1260 {
1261     // If our last flow was a self-collapsing block that cleared a float, then we don't
1262     // collapse it with the bottom of the block.
1263     if (!marginInfo.selfCollapsingBlockClearedFloat())
1264         marginInfo.setAtBottomOfBlock(true);
1265     else {
1266         // We have to special case the negative margin situation (where the collapsed
1267         // margin of the self-collapsing block is negative), since there's no need
1268         // to make an adjustment in that case.
1269         if (marginInfo.margin() < 0)
1270             marginInfo.clearMargin();
1271     }
1272
1273     // If we can't collapse with children then go ahead and add in the bottom margin.
1274     if (!marginInfo.canCollapseWithBottom() && !marginInfo.canCollapseWithTop()
1275         && (!style()->htmlHacks() || !marginInfo.quirkContainer() || !marginInfo.bottomQuirk()))
1276         setHeight(height() + marginInfo.margin());
1277         
1278     // Now add in our bottom border/padding.
1279     setHeight(height() + bottom);
1280
1281     // Negative margins can cause our height to shrink below our minimal height (border/padding).
1282     // If this happens, ensure that the computed height is increased to the minimal height.
1283     setHeight(max(height(), top + bottom));
1284
1285     // Always make sure our overflow height is at least our height.
1286     m_overflowHeight = max(height(), m_overflowHeight);
1287
1288     // Update our bottom collapsed margin info.
1289     setCollapsedBottomMargin(marginInfo);
1290 }
1291
1292 void RenderBlock::layoutBlockChildren(bool relayoutChildren, int& maxFloatBottom)
1293 {
1294     if (gPercentHeightDescendantsMap) {
1295         if (HashSet<RenderBox*>* descendants = gPercentHeightDescendantsMap->get(this)) {
1296             HashSet<RenderBox*>::iterator end = descendants->end();
1297             for (HashSet<RenderBox*>::iterator it = descendants->begin(); it != end; ++it) {
1298                 RenderBox* box = *it;
1299                 while (box != this) {
1300                     if (box->normalChildNeedsLayout())
1301                         break;
1302                     box->setChildNeedsLayout(true, false);
1303                     box = box->containingBlock();
1304                     ASSERT(box);
1305                     if (!box)
1306                         break;
1307                 }
1308             }
1309         }
1310     }
1311
1312     int top = borderTop() + paddingTop();
1313     int bottom = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
1314
1315     m_overflowHeight = top;
1316     setHeight(m_overflowHeight);
1317
1318     // The margin struct caches all our current margin collapsing state.  The compact struct caches state when we encounter compacts,
1319     MarginInfo marginInfo(this, top, bottom);
1320
1321     // Fieldsets need to find their legend and position it inside the border of the object.
1322     // The legend then gets skipped during normal layout.
1323     RenderObject* legend = layoutLegend(relayoutChildren);
1324
1325     int previousFloatBottom = 0;
1326     maxFloatBottom = 0;
1327
1328     RenderBox* child = firstChildBox();
1329     while (child) {
1330         if (legend == child) {
1331             child = child->nextSiblingBox();
1332             continue; // Skip the legend, since it has already been positioned up in the fieldset's border.
1333         }
1334
1335         int oldTopPosMargin = maxTopPosMargin();
1336         int oldTopNegMargin = maxTopNegMargin();
1337
1338         // Make sure we layout children if they need it.
1339         // FIXME: Technically percentage height objects only need a relayout if their percentage isn't going to be turned into
1340         // an auto value.  Add a method to determine this, so that we can avoid the relayout.
1341         if (relayoutChildren || ((child->style()->height().isPercent() || child->style()->minHeight().isPercent() || child->style()->maxHeight().isPercent()) && !isRenderView()))
1342             child->setChildNeedsLayout(true, false);
1343
1344         // If relayoutChildren is set and we have percentage padding, we also need to invalidate the child's pref widths.
1345         if (relayoutChildren && (child->style()->paddingLeft().isPercent() || child->style()->paddingRight().isPercent()))
1346             child->setPrefWidthsDirty(true, false);
1347
1348         // Handle the four types of special elements first.  These include positioned content, floating content, compacts and
1349         // run-ins.  When we encounter these four types of objects, we don't actually lay them out as normal flow blocks.
1350         bool handled = false;
1351         RenderBox* next = handleSpecialChild(child, marginInfo, handled);
1352         if (handled) {
1353             child = next;
1354             continue;
1355         }
1356
1357         // The child is a normal flow object.  Compute its vertical margins now.
1358         child->calcVerticalMargins();
1359
1360         // Do not allow a collapse if the margin top collapse style is set to SEPARATE.
1361         if (child->style()->marginTopCollapse() == MSEPARATE) {
1362             marginInfo.setAtTopOfBlock(false);
1363             marginInfo.clearMargin();
1364         }
1365
1366         // Try to guess our correct y position.  In most cases this guess will
1367         // be correct.  Only if we're wrong (when we compute the real y position)
1368         // will we have to potentially relayout.
1369         int yPosEstimate = estimateVerticalPosition(child, marginInfo);
1370
1371         // Cache our old rect so that we can dirty the proper repaint rects if the child moves.
1372         IntRect oldRect(child->x(), child->y() , child->width(), child->height());
1373 #ifndef NDEBUG
1374         IntSize oldLayoutDelta = view()->layoutDelta();
1375 #endif
1376         // Go ahead and position the child as though it didn't collapse with the top.
1377         view()->addLayoutDelta(IntSize(0, child->y() - yPosEstimate));
1378         child->setLocation(child->x(), yPosEstimate);
1379
1380         bool markDescendantsWithFloats = false;
1381         if (yPosEstimate != oldRect.y() && !child->avoidsFloats() && child->containsFloats())
1382             markDescendantsWithFloats = true;
1383         else if (!child->avoidsFloats() || child->shrinkToAvoidFloats()) {
1384             // If an element might be affected by the presence of floats, then always mark it for
1385             // layout.
1386             int fb = max(previousFloatBottom, floatBottom());
1387             if (fb > height() || fb > yPosEstimate)
1388                 markDescendantsWithFloats = true;
1389         }
1390
1391         if (child->isRenderBlock()) {
1392             if (markDescendantsWithFloats)
1393                 toRenderBlock(child)->markAllDescendantsWithFloatsForLayout();
1394
1395             previousFloatBottom = max(previousFloatBottom, oldRect.y() + toRenderBlock(child)->floatBottom());
1396         }
1397
1398         bool childHadLayout = child->m_everHadLayout;
1399         bool childNeededLayout = child->needsLayout();
1400         if (childNeededLayout)
1401             child->layout();
1402
1403         // Now determine the correct ypos based off examination of collapsing margin
1404         // values.
1405         collapseMargins(child, marginInfo, yPosEstimate);
1406
1407         // Now check for clear.
1408         clearFloatsIfNeeded(child, marginInfo, oldTopPosMargin, oldTopNegMargin);
1409
1410         // We are no longer at the top of the block if we encounter a non-empty child.  
1411         // This has to be done after checking for clear, so that margins can be reset if a clear occurred.
1412         if (marginInfo.atTopOfBlock() && !child->isSelfCollapsingBlock())
1413             marginInfo.setAtTopOfBlock(false);
1414
1415         // Now place the child in the correct horizontal position
1416         determineHorizontalPosition(child);
1417
1418         // Update our height now that the child has been placed in the correct position.
1419         setHeight(height() + child->height());
1420         if (child->style()->marginBottomCollapse() == MSEPARATE) {
1421             setHeight(height() + child->marginBottom());
1422             marginInfo.clearMargin();
1423         }
1424         // If the child has overhanging floats that intrude into following siblings (or possibly out
1425         // of this block), then the parent gets notified of the floats now.
1426         if (child->containsFloats())
1427             maxFloatBottom = max(maxFloatBottom, addOverhangingFloats(toRenderBlock(child), -child->x(), -child->y(), !childNeededLayout));
1428
1429         // Update our overflow in case the child spills out the block.
1430         m_overflowTop = min(m_overflowTop, child->y() + child->overflowTop(false));
1431         m_overflowHeight = max(m_overflowHeight, height() + child->overflowHeight(false) - child->height());
1432         m_overflowWidth = max(child->x() + child->overflowWidth(false), m_overflowWidth);
1433         m_overflowLeft = min(child->x() + child->overflowLeft(false), m_overflowLeft);
1434
1435         IntSize childOffset(child->x() - oldRect.x(), child->y() - oldRect.y());
1436         if (childOffset.width() || childOffset.height()) {
1437             view()->addLayoutDelta(childOffset);
1438
1439             // If the child moved, we have to repaint it as well as any floating/positioned
1440             // descendants.  An exception is if we need a layout.  In this case, we know we're going to
1441             // repaint ourselves (and the child) anyway.
1442             if (childHadLayout && !selfNeedsLayout() && child->checkForRepaintDuringLayout())
1443                 child->repaintDuringLayoutIfMoved(oldRect);
1444         }
1445
1446         if (!childHadLayout && child->checkForRepaintDuringLayout())
1447             child->repaint();
1448
1449         ASSERT(oldLayoutDelta == view()->layoutDelta());
1450         child = child->nextSiblingBox();
1451     }
1452
1453     // Now do the handling of the bottom of the block, adding in our bottom border/padding and
1454     // determining the correct collapsed bottom margin information.
1455     handleBottomOfBlock(top, bottom, marginInfo);
1456 }
1457
1458 bool RenderBlock::layoutOnlyPositionedObjects()
1459 {
1460     if (!posChildNeedsLayout() || normalChildNeedsLayout() || selfNeedsLayout())
1461         return false;
1462
1463     LayoutStateMaintainer statePusher(view(), this, IntSize(x(), y()), hasColumns() || hasTransform() || hasReflection());
1464
1465     if (needsPositionedMovementLayout()) {
1466         tryLayoutDoingPositionedMovementOnly();
1467         if (needsLayout())
1468             return false;
1469     }
1470
1471     // All we have to is lay out our positioned objects.
1472     layoutPositionedObjects(false);
1473
1474     statePusher.pop();
1475
1476     if (hasOverflowClip())
1477         m_layer->updateScrollInfoAfterLayout();
1478
1479     setNeedsLayout(false);
1480     return true;
1481 }
1482
1483 void RenderBlock::layoutPositionedObjects(bool relayoutChildren)
1484 {
1485     if (m_positionedObjects) {
1486         RenderBox* r;
1487         Iterator end = m_positionedObjects->end();
1488         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
1489             r = *it;
1490             // When a non-positioned block element moves, it may have positioned children that are implicitly positioned relative to the
1491             // non-positioned block.  Rather than trying to detect all of these movement cases, we just always lay out positioned
1492             // objects that are positioned implicitly like this.  Such objects are rare, and so in typical DHTML menu usage (where everything is
1493             // positioned explicitly) this should not incur a performance penalty.
1494             if (relayoutChildren || (r->hasStaticY() && r->parent() != this && r->parent()->isBlockFlow()))
1495                 r->setChildNeedsLayout(true, false);
1496                 
1497             // If relayoutChildren is set and we have percentage padding, we also need to invalidate the child's pref widths.
1498             //if (relayoutChildren && (r->style()->paddingLeft().isPercent() || r->style()->paddingRight().isPercent()))
1499                 r->setPrefWidthsDirty(true, false);
1500             
1501             // We don't have to do a full layout.  We just have to update our position. Try that first. If we have shrink-to-fit width
1502             // and we hit the available width constraint, the layoutIfNeeded() will catch it and do a full layout.
1503             if (r->needsPositionedMovementLayoutOnly())
1504                 r->tryLayoutDoingPositionedMovementOnly();
1505             r->layoutIfNeeded();
1506         }
1507     }
1508 }
1509
1510 void RenderBlock::markPositionedObjectsForLayout()
1511 {
1512     if (m_positionedObjects) {
1513         RenderBox* r;
1514         Iterator end = m_positionedObjects->end();
1515         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
1516             r = *it;
1517             r->setChildNeedsLayout(true);
1518         }
1519     }
1520 }
1521
1522 void RenderBlock::repaintOverhangingFloats(bool paintAllDescendants)
1523 {
1524     // Repaint any overhanging floats (if we know we're the one to paint them).
1525     if (hasOverhangingFloats()) {
1526         // We think that we must be in a bad state if m_floatingObjects is nil at this point, so 
1527         // we assert on Debug builds and nil-check Release builds.
1528         ASSERT(m_floatingObjects);
1529         if (!m_floatingObjects)
1530             return;
1531         
1532         FloatingObject* r;
1533         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
1534
1535         // FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
1536         // in this block. Better yet would be to push extra state for the containers of other floats.
1537         view()->disableLayoutState();
1538         for ( ; (r = it.current()); ++it) {
1539             // Only repaint the object if it is overhanging, is not in its own layer, and
1540             // is our responsibility to paint (m_shouldPaint is set). When paintAllDescendants is true, the latter
1541             // condition is replaced with being a descendant of us.
1542             if (r->m_bottom > height() && (paintAllDescendants && r->m_renderer->isDescendantOf(this) || r->m_shouldPaint) && !r->m_renderer->hasLayer()) {                
1543                 r->m_renderer->repaint();
1544                 r->m_renderer->repaintOverhangingFloats();
1545             }
1546         }
1547         view()->enableLayoutState();
1548     }
1549 }
1550  
1551 void RenderBlock::paint(PaintInfo& paintInfo, int tx, int ty)
1552 {
1553     tx += x();
1554     ty += y();
1555     
1556     PaintPhase phase = paintInfo.phase;
1557
1558     // Check if we need to do anything at all.
1559     // FIXME: Could eliminate the isRoot() check if we fix background painting so that the RenderView
1560     // paints the root's background.
1561     if (!isRoot()) {
1562         IntRect overflowBox = overflowRect(false);
1563         overflowBox.inflate(maximalOutlineSize(paintInfo.phase));
1564         overflowBox.move(tx, ty);
1565         if (!overflowBox.intersects(paintInfo.rect))
1566             return;
1567     }
1568
1569     bool useControlClip = phase != PaintPhaseBlockBackground && phase != PaintPhaseSelfOutline && phase != PaintPhaseMask && hasControlClip();
1570
1571     // Push a clip.
1572     if (useControlClip) {
1573         if (phase == PaintPhaseOutline)
1574             paintInfo.phase = PaintPhaseChildOutlines;
1575         else if (phase == PaintPhaseChildBlockBackground) {
1576             paintInfo.phase = PaintPhaseBlockBackground;
1577             paintObject(paintInfo, tx, ty);
1578             paintInfo.phase = PaintPhaseChildBlockBackgrounds;
1579         }
1580         IntRect clipRect(controlClipRect(tx, ty));
1581         if (clipRect.isEmpty())
1582             return;
1583         paintInfo.context->save();
1584         paintInfo.context->clip(clipRect);
1585     }
1586
1587     paintObject(paintInfo, tx, ty);
1588     
1589     // Pop the clip.
1590     if (useControlClip) {
1591         paintInfo.context->restore();
1592         if (phase == PaintPhaseOutline) {
1593             paintInfo.phase = PaintPhaseSelfOutline;
1594             paintObject(paintInfo, tx, ty);
1595             paintInfo.phase = phase;
1596         } else if (phase == PaintPhaseChildBlockBackground)
1597             paintInfo.phase = phase;
1598     }
1599 }
1600
1601 void RenderBlock::paintColumns(PaintInfo& paintInfo, int tx, int ty, bool paintingFloats)
1602 {
1603     // We need to do multiple passes, breaking up our child painting into strips.
1604     GraphicsContext* context = paintInfo.context;
1605     int currXOffset = 0;
1606     int currYOffset = 0;
1607     int ruleAdd = borderLeft() + paddingLeft();
1608     int ruleX = 0;
1609     int colGap = columnGap();
1610     const Color& ruleColor = style()->columnRuleColor();
1611     bool ruleTransparent = style()->columnRuleIsTransparent();
1612     EBorderStyle ruleStyle = style()->columnRuleStyle();
1613     int ruleWidth = style()->columnRuleWidth();
1614     bool renderRule = !paintingFloats && ruleStyle > BHIDDEN && !ruleTransparent && ruleWidth <= colGap;
1615     Vector<IntRect>* colRects = columnRects();
1616     unsigned colCount = colRects->size();
1617     for (unsigned i = 0; i < colCount; i++) {
1618         // For each rect, we clip to the rect, and then we adjust our coords.
1619         IntRect colRect = colRects->at(i);
1620         colRect.move(tx, ty);
1621         context->save();
1622         
1623         // Each strip pushes a clip, since column boxes are specified as being
1624         // like overflow:hidden.
1625         context->clip(colRect);
1626         
1627         // Adjust tx and ty to change where we paint.
1628         PaintInfo info(paintInfo);
1629         info.rect.intersect(colRect);
1630         
1631         // Adjust our x and y when painting.
1632         int finalX = tx + currXOffset;
1633         int finalY = ty + currYOffset;
1634         if (paintingFloats)
1635             paintFloats(info, finalX, finalY, paintInfo.phase == PaintPhaseSelection || paintInfo.phase == PaintPhaseTextClip);
1636         else
1637             paintContents(info, finalX, finalY);
1638
1639         // Move to the next position.
1640         if (style()->direction() == LTR) {
1641             ruleX += colRect.width() + colGap / 2;
1642             currXOffset += colRect.width() + colGap;
1643         } else {
1644             ruleX -= (colRect.width() + colGap / 2);
1645             currXOffset -= (colRect.width() + colGap);
1646         }
1647
1648         currYOffset -= colRect.height();
1649         
1650         context->restore();
1651         
1652         // Now paint the column rule.
1653         if (renderRule && paintInfo.phase == PaintPhaseForeground && i < colCount - 1) {
1654             int ruleStart = ruleX - ruleWidth / 2 + ruleAdd;
1655             int ruleEnd = ruleStart + ruleWidth;
1656             drawBorder(paintInfo.context, tx + ruleStart, ty + borderTop() + paddingTop(), tx + ruleEnd, ty + borderTop() + paddingTop() + contentHeight(),
1657                        style()->direction() == LTR ? BSLeft : BSRight, ruleColor, style()->color(), ruleStyle, 0, 0);
1658         }
1659         
1660         ruleX = currXOffset;
1661     }
1662 }
1663
1664 void RenderBlock::paintContents(PaintInfo& paintInfo, int tx, int ty)
1665 {
1666     // Avoid painting descendants of the root element when stylesheets haven't loaded.  This eliminates FOUC.
1667     // It's ok not to draw, because later on, when all the stylesheets do load, updateStyleSelector on the Document
1668     // will do a full repaint().
1669     if (document()->didLayoutWithPendingStylesheets() && !isRenderView())
1670         return;
1671
1672     if (childrenInline())
1673         m_lineBoxes.paint(this, paintInfo, tx, ty);
1674     else
1675         paintChildren(paintInfo, tx, ty);
1676 }
1677
1678 void RenderBlock::paintChildren(PaintInfo& paintInfo, int tx, int ty)
1679 {
1680     PaintPhase newPhase = (paintInfo.phase == PaintPhaseChildOutlines) ? PaintPhaseOutline : paintInfo.phase;
1681     newPhase = (newPhase == PaintPhaseChildBlockBackgrounds) ? PaintPhaseChildBlockBackground : newPhase;
1682     
1683     // We don't paint our own background, but we do let the kids paint their backgrounds.
1684     PaintInfo info(paintInfo);
1685     info.phase = newPhase;
1686     info.paintingRoot = paintingRootForChildren(paintInfo);
1687     bool isPrinting = document()->printing();
1688
1689     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {        
1690         // Check for page-break-before: always, and if it's set, break and bail.
1691         if (isPrinting && !childrenInline() && child->style()->pageBreakBefore() == PBALWAYS &&
1692             inRootBlockContext() && (ty + child->y()) > paintInfo.rect.y() && 
1693             (ty + child->y()) < paintInfo.rect.bottom()) {
1694             view()->setBestTruncatedAt(ty + child->y(), this, true);
1695             return;
1696         }
1697
1698         if (!child->hasLayer() && !child->isFloating())
1699             child->paint(info, tx, ty);
1700
1701         // Check for page-break-after: always, and if it's set, break and bail.
1702         if (isPrinting && !childrenInline() && child->style()->pageBreakAfter() == PBALWAYS && 
1703             inRootBlockContext() && (ty + child->y() + child->height()) > paintInfo.rect.y() && 
1704             (ty + child->y() + child->height()) < paintInfo.rect.bottom()) {
1705             view()->setBestTruncatedAt(ty + child->y() + child->height() + max(0, child->collapsedMarginBottom()), this, true);
1706             return;
1707         }
1708     }
1709 }
1710
1711 void RenderBlock::paintCaret(PaintInfo& paintInfo, int tx, int ty, CaretType type)
1712 {
1713     SelectionController* selection = type == CursorCaret ? document()->frame()->selection() : document()->frame()->dragCaretController();
1714
1715     // Ask the SelectionController if the caret should be painted by this block
1716     RenderObject* caretPainter = selection->caretRenderer();
1717     if (caretPainter == this && selection->isContentEditable()) {
1718         // Convert the painting offset into the local coordinate system of this renderer,
1719         // to match the localCaretRect computed by the SelectionController
1720         offsetForContents(tx, ty);
1721
1722         if (type == CursorCaret)
1723             document()->frame()->paintCaret(paintInfo.context, tx, ty, paintInfo.rect);
1724         else
1725             document()->frame()->paintDragCaret(paintInfo.context, tx, ty, paintInfo.rect);
1726     }
1727 }
1728
1729 void RenderBlock::paintObject(PaintInfo& paintInfo, int tx, int ty)
1730 {
1731     PaintPhase paintPhase = paintInfo.phase;
1732
1733     // 1. paint background, borders etc
1734     if ((paintPhase == PaintPhaseBlockBackground || paintPhase == PaintPhaseChildBlockBackground) &&
1735         hasBoxDecorations() && style()->visibility() == VISIBLE) {
1736         paintBoxDecorations(paintInfo, tx, ty);
1737     }
1738
1739     if (paintPhase == PaintPhaseMask && style()->visibility() == VISIBLE) {
1740         paintMask(paintInfo, tx, ty);
1741         return;
1742     }
1743
1744     // We're done.  We don't bother painting any children.
1745     if (paintPhase == PaintPhaseBlockBackground)
1746         return;
1747
1748     // Adjust our painting position if we're inside a scrolled layer (e.g., an overflow:auto div).s
1749     int scrolledX = tx;
1750     int scrolledY = ty;
1751     if (hasOverflowClip())
1752         m_layer->subtractScrolledContentOffset(scrolledX, scrolledY);
1753
1754     // 2. paint contents
1755     if (paintPhase != PaintPhaseSelfOutline) {
1756         if (hasColumns())
1757             paintColumns(paintInfo, scrolledX, scrolledY);
1758         else
1759             paintContents(paintInfo, scrolledX, scrolledY);
1760     }
1761
1762     // 3. paint selection
1763     // FIXME: Make this work with multi column layouts.  For now don't fill gaps.
1764     bool isPrinting = document()->printing();
1765     if (!isPrinting && !hasColumns())
1766         paintSelection(paintInfo, scrolledX, scrolledY); // Fill in gaps in selection on lines and between blocks.
1767
1768     // 4. paint floats.
1769     if (paintPhase == PaintPhaseFloat || paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip) {
1770         if (hasColumns())
1771             paintColumns(paintInfo, scrolledX, scrolledY, true);
1772         else
1773             paintFloats(paintInfo, scrolledX, scrolledY, paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip);
1774     }
1775
1776     // 5. paint outline.
1777     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseSelfOutline) && hasOutline() && style()->visibility() == VISIBLE)
1778         paintOutline(paintInfo.context, tx, ty, width(), height(), style());
1779
1780     // 6. paint continuation outlines.
1781     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseChildOutlines)) {
1782         if (inlineContinuation() && inlineContinuation()->hasOutline() && inlineContinuation()->style()->visibility() == VISIBLE) {
1783             RenderInline* inlineRenderer = toRenderInline(inlineContinuation()->element()->renderer());
1784             if (!inlineRenderer->hasLayer())
1785                 containingBlock()->addContinuationWithOutline(inlineRenderer);
1786             else if (!inlineRenderer->firstLineBox())
1787                 inlineRenderer->paintOutline(paintInfo.context, tx - x() + inlineRenderer->containingBlock()->x(),
1788                                              ty - y() + inlineRenderer->containingBlock()->y());
1789         }
1790         paintContinuationOutlines(paintInfo, tx, ty);
1791     }
1792
1793     // 7. paint caret.
1794     // If the caret's node's render object's containing block is this block, and the paint action is PaintPhaseForeground,
1795     // then paint the caret.
1796     if (paintPhase == PaintPhaseForeground) {        
1797         paintCaret(paintInfo, scrolledX, scrolledY, CursorCaret);
1798         paintCaret(paintInfo, scrolledX, scrolledY, DragCaret);
1799     }
1800 }
1801
1802 void RenderBlock::paintFloats(PaintInfo& paintInfo, int tx, int ty, bool preservePhase)
1803 {
1804     if (!m_floatingObjects)
1805         return;
1806
1807     FloatingObject* r;
1808     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
1809     for (; (r = it.current()); ++it) {
1810         // Only paint the object if our m_shouldPaint flag is set.
1811         if (r->m_shouldPaint && !r->m_renderer->hasLayer()) {
1812             PaintInfo currentPaintInfo(paintInfo);
1813             currentPaintInfo.phase = preservePhase ? paintInfo.phase : PaintPhaseBlockBackground;
1814             int currentTX = tx + r->m_left - r->m_renderer->x() + r->m_renderer->marginLeft();
1815             int currentTY = ty + r->m_top - r->m_renderer->y() + r->m_renderer->marginTop();
1816             r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1817             if (!preservePhase) {
1818                 currentPaintInfo.phase = PaintPhaseChildBlockBackgrounds;
1819                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1820                 currentPaintInfo.phase = PaintPhaseFloat;
1821                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1822                 currentPaintInfo.phase = PaintPhaseForeground;
1823                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1824                 currentPaintInfo.phase = PaintPhaseOutline;
1825                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1826             }
1827         }
1828     }
1829 }
1830
1831 void RenderBlock::paintEllipsisBoxes(PaintInfo& paintInfo, int tx, int ty)
1832 {
1833     if (!shouldPaintWithinRoot(paintInfo) || !firstLineBox())
1834         return;
1835
1836     if (style()->visibility() == VISIBLE && paintInfo.phase == PaintPhaseForeground) {
1837         // We can check the first box and last box and avoid painting if we don't
1838         // intersect.
1839         int yPos = ty + firstLineBox()->yPos();
1840         int h = lastLineBox()->yPos() + lastLineBox()->height() - firstLineBox()->yPos();
1841         if (yPos >= paintInfo.rect.bottom() || yPos + h <= paintInfo.rect.y())
1842             return;
1843
1844         // See if our boxes intersect with the dirty rect.  If so, then we paint
1845         // them.  Note that boxes can easily overlap, so we can't make any assumptions
1846         // based off positions of our first line box or our last line box.
1847         for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
1848             yPos = ty + curr->yPos();
1849             h = curr->height();
1850             if (curr->ellipsisBox() && yPos < paintInfo.rect.bottom() && yPos + h > paintInfo.rect.y())
1851                 curr->paintEllipsisBox(paintInfo, tx, ty);
1852         }
1853     }
1854 }
1855
1856 static ContinuationOutlineTableMap* continuationOutlineTable()
1857 {
1858     DEFINE_STATIC_LOCAL(ContinuationOutlineTableMap, table, ());
1859     return &table;
1860 }
1861
1862 void RenderBlock::addContinuationWithOutline(RenderInline* flow)
1863 {
1864     // We can't make this work if the inline is in a layer.  We'll just rely on the broken
1865     // way of painting.
1866     ASSERT(!flow->layer() && !flow->isInlineContinuation());
1867     
1868     ContinuationOutlineTableMap* table = continuationOutlineTable();
1869     ListHashSet<RenderInline*>* continuations = table->get(this);
1870     if (!continuations) {
1871         continuations = new ListHashSet<RenderInline*>;
1872         table->set(this, continuations);
1873     }
1874     
1875     continuations->add(flow);
1876 }
1877
1878 void RenderBlock::paintContinuationOutlines(PaintInfo& info, int tx, int ty)
1879 {
1880     ContinuationOutlineTableMap* table = continuationOutlineTable();
1881     if (table->isEmpty())
1882         return;
1883         
1884     ListHashSet<RenderInline*>* continuations = table->get(this);
1885     if (!continuations)
1886         return;
1887         
1888     // Paint each continuation outline.
1889     ListHashSet<RenderInline*>::iterator end = continuations->end();
1890     for (ListHashSet<RenderInline*>::iterator it = continuations->begin(); it != end; ++it) {
1891         // Need to add in the coordinates of the intervening blocks.
1892         RenderInline* flow = *it;
1893         RenderBlock* block = flow->containingBlock();
1894         for ( ; block && block != this; block = block->containingBlock()) {
1895             tx += block->x();
1896             ty += block->y();
1897         }
1898         ASSERT(block);   
1899         flow->paintOutline(info.context, tx, ty);
1900     }
1901     
1902     // Delete
1903     delete continuations;
1904     table->remove(this);
1905 }
1906
1907 void RenderBlock::setSelectionState(SelectionState s)
1908 {
1909     if (selectionState() == s)
1910         return;
1911     
1912     if (s == SelectionInside && selectionState() != SelectionNone)
1913         return;
1914
1915     if ((s == SelectionStart && selectionState() == SelectionEnd) ||
1916         (s == SelectionEnd && selectionState() == SelectionStart))
1917         RenderContainer::setSelectionState(SelectionBoth);
1918     else
1919         RenderContainer::setSelectionState(s);
1920     
1921     RenderBlock* cb = containingBlock();
1922     if (cb && !cb->isRenderView())
1923         cb->setSelectionState(s);
1924 }
1925
1926 bool RenderBlock::shouldPaintSelectionGaps() const
1927 {
1928     return selectionState() != SelectionNone && style()->visibility() == VISIBLE && isSelectionRoot();
1929 }
1930
1931 bool RenderBlock::isSelectionRoot() const
1932 {
1933     if (!element())
1934         return false;
1935         
1936     // FIXME: Eventually tables should have to learn how to fill gaps between cells, at least in simple non-spanning cases.
1937     if (isTable())
1938         return false;
1939         
1940     if (isBody() || isRoot() || hasOverflowClip() || isRelPositioned() ||
1941         isFloatingOrPositioned() || isTableCell() || isInlineBlockOrInlineTable() || hasTransform() ||
1942         hasReflection() || hasMask())
1943         return true;
1944     
1945     if (view() && view()->selectionStart()) {
1946         Node* startElement = view()->selectionStart()->element();
1947         if (startElement && startElement->rootEditableElement() == element())
1948             return true;
1949     }
1950     
1951     return false;
1952 }
1953
1954 GapRects RenderBlock::selectionGapRects()
1955 {
1956     ASSERT(!needsLayout());
1957
1958     if (!shouldPaintSelectionGaps())
1959         return GapRects();
1960
1961     // FIXME: this is broken with transforms
1962     FloatPoint absContentPoint = localToAbsolute(FloatPoint());
1963     if (hasOverflowClip())
1964         absContentPoint -= layer()->scrolledContentOffset();
1965
1966     int lastTop = 0;
1967     int lastLeft = leftSelectionOffset(this, lastTop);
1968     int lastRight = rightSelectionOffset(this, lastTop);
1969     
1970     return fillSelectionGaps(this, absContentPoint.x(), absContentPoint.y(), absContentPoint.x(), absContentPoint.y(), lastTop, lastLeft, lastRight);
1971 }
1972
1973 void RenderBlock::paintSelection(PaintInfo& paintInfo, int tx, int ty)
1974 {
1975     if (shouldPaintSelectionGaps() && paintInfo.phase == PaintPhaseForeground) {
1976         int lastTop = 0;
1977         int lastLeft = leftSelectionOffset(this, lastTop);
1978         int lastRight = rightSelectionOffset(this, lastTop);
1979         paintInfo.context->save();
1980         fillSelectionGaps(this, tx, ty, tx, ty, lastTop, lastLeft, lastRight, &paintInfo);
1981         paintInfo.context->restore();
1982     }
1983 }
1984
1985 static void clipOutPositionedObjects(const RenderObject::PaintInfo* paintInfo, int tx, int ty, ListHashSet<RenderBox*>* positionedObjects)
1986 {
1987     if (!positionedObjects)
1988         return;
1989     
1990     ListHashSet<RenderBox*>::const_iterator end = positionedObjects->end();
1991     for (ListHashSet<RenderBox*>::const_iterator it = positionedObjects->begin(); it != end; ++it) {
1992         RenderBox* r = *it;
1993         paintInfo->context->clipOut(IntRect(tx + r->x(), ty + r->y(), r->width(), r->height()));
1994     }
1995 }
1996
1997 GapRects RenderBlock::fillSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty,
1998                                         int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
1999 {
2000     // IMPORTANT: Callers of this method that intend for painting to happen need to do a save/restore.
2001     // Clip out floating and positioned objects when painting selection gaps.
2002     if (paintInfo) {
2003         // Note that we don't clip out overflow for positioned objects.  We just stick to the border box.
2004         clipOutPositionedObjects(paintInfo, tx, ty, m_positionedObjects);
2005         if (isBody() || isRoot()) // The <body> must make sure to examine its containingBlock's positioned objects.
2006             for (RenderBlock* cb = containingBlock(); cb && !cb->isRenderView(); cb = cb->containingBlock())
2007                 clipOutPositionedObjects(paintInfo, cb->x(), cb->y(), cb->m_positionedObjects);
2008         if (m_floatingObjects) {
2009             for (DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects); it.current(); ++it) {
2010                 FloatingObject* r = it.current();
2011                 paintInfo->context->clipOut(IntRect(tx + r->m_left + r->m_renderer->marginLeft(), 
2012                                                     ty + r->m_top + r->m_renderer->marginTop(),
2013                                                     r->m_renderer->width(), r->m_renderer->height()));
2014             }
2015         }
2016     }
2017
2018     // 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
2019     // fixed).
2020     GapRects result;
2021     if (!isBlockFlow()) // FIXME: Make multi-column selection gap filling work someday.
2022         return result;
2023
2024     if (hasColumns() || hasTransform()) {
2025         // FIXME: We should learn how to gap fill multiple columns and transforms eventually.
2026         lastTop = (ty - blockY) + height();
2027         lastLeft = leftSelectionOffset(rootBlock, height());
2028         lastRight = rightSelectionOffset(rootBlock, height());
2029         return result;
2030     }
2031
2032     if (childrenInline())
2033         result = fillInlineSelectionGaps(rootBlock, blockX, blockY, tx, ty, lastTop, lastLeft, lastRight, paintInfo);
2034     else
2035         result = fillBlockSelectionGaps(rootBlock, blockX, blockY, tx, ty, lastTop, lastLeft, lastRight, paintInfo);
2036
2037     // Go ahead and fill the vertical gap all the way to the bottom of our block if the selection extends past our block.
2038     if (rootBlock == this && (selectionState() != SelectionBoth && selectionState() != SelectionEnd))
2039         result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight, ty + height(),
2040                                                     rootBlock, blockX, blockY, paintInfo));
2041     return result;
2042 }
2043
2044 GapRects RenderBlock::fillInlineSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty, 
2045                                               int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
2046 {
2047     GapRects result;
2048
2049     bool containsStart = selectionState() == SelectionStart || selectionState() == SelectionBoth;
2050
2051     if (!firstLineBox()) {
2052         if (containsStart) {
2053             // Go ahead and update our lastY to be the bottom of the block.  <hr>s or empty blocks with height can trip this
2054             // case.
2055             lastTop = (ty - blockY) + height();
2056             lastLeft = leftSelectionOffset(rootBlock, height());
2057             lastRight = rightSelectionOffset(rootBlock, height());
2058         }
2059         return result;
2060     }
2061
2062     RootInlineBox* lastSelectedLine = 0;
2063     RootInlineBox* curr;
2064     for (curr = firstRootBox(); curr && !curr->hasSelectedChildren(); curr = curr->nextRootBox()) { }
2065
2066     // Now paint the gaps for the lines.
2067     for (; curr && curr->hasSelectedChildren(); curr = curr->nextRootBox()) {
2068         int selTop =  curr->selectionTop();
2069         int selHeight = curr->selectionHeight();
2070
2071         if (!containsStart && !lastSelectedLine &&
2072             selectionState() != SelectionStart && selectionState() != SelectionBoth)
2073             result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight, ty + selTop,
2074                                                         rootBlock, blockX, blockY, paintInfo));
2075
2076         if (!paintInfo || ty + selTop < paintInfo->rect.bottom() && ty + selTop + selHeight > paintInfo->rect.y())
2077             result.unite(curr->fillLineSelectionGap(selTop, selHeight, rootBlock, blockX, blockY, tx, ty, paintInfo));
2078
2079         lastSelectedLine = curr;
2080     }
2081
2082     if (containsStart && !lastSelectedLine)
2083         // Selection must start just after our last line.
2084         lastSelectedLine = lastRootBox();
2085
2086     if (lastSelectedLine && selectionState() != SelectionEnd && selectionState() != SelectionBoth) {
2087         // Go ahead and update our lastY to be the bottom of the last selected line.
2088         lastTop = (ty - blockY) + lastSelectedLine->bottomOverflow();
2089         lastLeft = leftSelectionOffset(rootBlock, lastSelectedLine->bottomOverflow());
2090         lastRight = rightSelectionOffset(rootBlock, lastSelectedLine->bottomOverflow());
2091     }
2092     return result;
2093 }
2094
2095 GapRects RenderBlock::fillBlockSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty,
2096                                              int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
2097 {
2098     GapRects result;
2099
2100     // Go ahead and jump right to the first block child that contains some selected objects.
2101     RenderBox* curr;
2102     for (curr = firstChildBox(); curr && curr->selectionState() == SelectionNone; curr = curr->nextSiblingBox()) { }
2103
2104     for (bool sawSelectionEnd = false; curr && !sawSelectionEnd; curr = curr->nextSiblingBox()) {
2105         SelectionState childState = curr->selectionState();
2106         if (childState == SelectionBoth || childState == SelectionEnd)
2107             sawSelectionEnd = true;
2108
2109         if (curr->isFloatingOrPositioned())
2110             continue; // We must be a normal flow object in order to even be considered.
2111
2112         if (curr->isRelPositioned() && curr->hasLayer()) {
2113             // If the relposition offset is anything other than 0, then treat this just like an absolute positioned element.
2114             // Just disregard it completely.
2115             IntSize relOffset = curr->layer()->relativePositionOffset();
2116             if (relOffset.width() || relOffset.height())
2117                 continue;
2118         }
2119
2120         bool paintsOwnSelection = curr->shouldPaintSelectionGaps() || curr->isTable(); // FIXME: Eventually we won't special-case table like this.
2121         bool fillBlockGaps = paintsOwnSelection || (curr->canBeSelectionLeaf() && childState != SelectionNone);
2122         if (fillBlockGaps) {
2123             // We need to fill the vertical gap above this object.
2124             if (childState == SelectionEnd || childState == SelectionInside)
2125                 // Fill the gap above the object.
2126                 result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight, 
2127                                                             ty + curr->y(), rootBlock, blockX, blockY, paintInfo));
2128
2129             // 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*
2130             // our object.  We know this if the selection did not end inside our object.
2131             if (paintsOwnSelection && (childState == SelectionStart || sawSelectionEnd))
2132                 childState = SelectionNone;
2133
2134             // Fill side gaps on this object based off its state.
2135             bool leftGap, rightGap;
2136             getHorizontalSelectionGapInfo(childState, leftGap, rightGap);
2137
2138             if (leftGap)
2139                 result.uniteLeft(fillLeftSelectionGap(this, curr->x(), curr->y(), curr->height(), rootBlock, blockX, blockY, tx, ty, paintInfo));
2140             if (rightGap)
2141                 result.uniteRight(fillRightSelectionGap(this, curr->x() + curr->width(), curr->y(), curr->height(), rootBlock, blockX, blockY, tx, ty, paintInfo));
2142
2143             // Update lastTop to be just underneath the object.  lastLeft and lastRight extend as far as
2144             // they can without bumping into floating or positioned objects.  Ideally they will go right up
2145             // to the border of the root selection block.
2146             lastTop = (ty - blockY) + (curr->y() + curr->height());
2147             lastLeft = leftSelectionOffset(rootBlock, curr->y() + curr->height());
2148             lastRight = rightSelectionOffset(rootBlock, curr->y() + curr->height());
2149         } else if (childState != SelectionNone)
2150             // We must be a block that has some selected object inside it.  Go ahead and recur.
2151             result.unite(toRenderBlock(curr)->fillSelectionGaps(rootBlock, blockX, blockY, tx + curr->x(), ty + curr->y(), 
2152                                                                             lastTop, lastLeft, lastRight, paintInfo));
2153     }
2154     return result;
2155 }
2156
2157 IntRect RenderBlock::fillHorizontalSelectionGap(RenderObject* selObj, int xPos, int yPos, int width, int height, const PaintInfo* paintInfo)
2158 {
2159     if (width <= 0 || height <= 0)
2160         return IntRect();
2161     IntRect gapRect(xPos, yPos, width, height);
2162     if (paintInfo && selObj->style()->visibility() == VISIBLE)
2163         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor());
2164     return gapRect;
2165 }
2166
2167 IntRect RenderBlock::fillVerticalSelectionGap(int lastTop, int lastLeft, int lastRight, int bottomY, RenderBlock* rootBlock,
2168                                               int blockX, int blockY, const PaintInfo* paintInfo)
2169 {
2170     int top = blockY + lastTop;
2171     int height = bottomY - top;
2172     if (height <= 0)
2173         return IntRect();
2174
2175     // Get the selection offsets for the bottom of the gap
2176     int left = blockX + max(lastLeft, leftSelectionOffset(rootBlock, bottomY));
2177     int right = blockX + min(lastRight, rightSelectionOffset(rootBlock, bottomY));
2178     int width = right - left;
2179     if (width <= 0)
2180         return IntRect();
2181
2182     IntRect gapRect(left, top, width, height);
2183     if (paintInfo)
2184         paintInfo->context->fillRect(gapRect, selectionBackgroundColor());
2185     return gapRect;
2186 }
2187
2188 IntRect RenderBlock::fillLeftSelectionGap(RenderObject* selObj, int xPos, int yPos, int height, RenderBlock* rootBlock,
2189                                           int blockX, int /*blockY*/, int tx, int ty, const PaintInfo* paintInfo)
2190 {
2191     int top = yPos + ty;
2192     int left = blockX + max(leftSelectionOffset(rootBlock, yPos), leftSelectionOffset(rootBlock, yPos + height));
2193     int right = min(xPos + tx, blockX + min(rightSelectionOffset(rootBlock, yPos), rightSelectionOffset(rootBlock, yPos + height)));
2194     int width = right - left;
2195     if (width <= 0)
2196         return IntRect();
2197
2198     IntRect gapRect(left, top, width, height);
2199     if (paintInfo)
2200         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor());
2201     return gapRect;
2202 }
2203
2204 IntRect RenderBlock::fillRightSelectionGap(RenderObject* selObj, int xPos, int yPos, int height, RenderBlock* rootBlock,
2205                                            int blockX, int /*blockY*/, int tx, int ty, const PaintInfo* paintInfo)
2206 {
2207     int left = max(xPos + tx, blockX + max(leftSelectionOffset(rootBlock, yPos), leftSelectionOffset(rootBlock, yPos + height)));
2208     int top = yPos + ty;
2209     int right = blockX + min(rightSelectionOffset(rootBlock, yPos), rightSelectionOffset(rootBlock, yPos + height));
2210     int width = right - left;
2211     if (width <= 0)
2212         return IntRect();
2213
2214     IntRect gapRect(left, top, width, height);
2215     if (paintInfo)
2216         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor());
2217     return gapRect;
2218 }
2219
2220 void RenderBlock::getHorizontalSelectionGapInfo(SelectionState state, bool& leftGap, bool& rightGap)
2221 {
2222     bool ltr = style()->direction() == LTR;
2223     leftGap = (state == RenderObject::SelectionInside) ||
2224               (state == RenderObject::SelectionEnd && ltr) ||
2225               (state == RenderObject::SelectionStart && !ltr);
2226     rightGap = (state == RenderObject::SelectionInside) ||
2227                (state == RenderObject::SelectionStart && ltr) ||
2228                (state == RenderObject::SelectionEnd && !ltr);
2229 }
2230
2231 int RenderBlock::leftSelectionOffset(RenderBlock* rootBlock, int yPos)
2232 {
2233     int left = leftOffset(yPos, false);
2234     if (left == borderLeft() + paddingLeft()) {
2235         if (rootBlock != this)
2236             // The border can potentially be further extended by our containingBlock().
2237             return containingBlock()->leftSelectionOffset(rootBlock, yPos + y());
2238         return left;
2239     }
2240     else {
2241         RenderBlock* cb = this;
2242         while (cb != rootBlock) {
2243             left += cb->x();
2244             cb = cb->containingBlock();
2245         }
2246     }
2247     
2248     return left;
2249 }
2250
2251 int RenderBlock::rightSelectionOffset(RenderBlock* rootBlock, int yPos)
2252 {
2253     int right = rightOffset(yPos, false);
2254     if (right == (contentWidth() + (borderLeft() + paddingLeft()))) {
2255         if (rootBlock != this)
2256             // The border can potentially be further extended by our containingBlock().
2257             return containingBlock()->rightSelectionOffset(rootBlock, yPos + y());
2258         return right;
2259     }
2260     else {
2261         RenderBlock* cb = this;
2262         while (cb != rootBlock) {
2263             right += cb->x();
2264             cb = cb->containingBlock();
2265         }
2266     }
2267     return right;
2268 }
2269
2270 void RenderBlock::insertPositionedObject(RenderBox* o)
2271 {
2272     // Create the list of special objects if we don't aleady have one
2273     if (!m_positionedObjects)
2274         m_positionedObjects = new ListHashSet<RenderBox*>;
2275
2276     m_positionedObjects->add(o);
2277 }
2278
2279 void RenderBlock::removePositionedObject(RenderBox* o)
2280 {
2281     if (m_positionedObjects)
2282         m_positionedObjects->remove(o);
2283 }
2284
2285 void RenderBlock::removePositionedObjects(RenderBlock* o)
2286 {
2287     if (!m_positionedObjects)
2288         return;
2289     
2290     RenderBox* r;
2291     
2292     Iterator end = m_positionedObjects->end();
2293     
2294     Vector<RenderBox*, 16> deadObjects;
2295
2296     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2297         r = *it;
2298         if (!o || r->isDescendantOf(o)) {
2299             if (o)
2300                 r->setChildNeedsLayout(true, false);
2301             
2302             // It is parent blocks job to add positioned child to positioned objects list of its containing block
2303             // Parent layout needs to be invalidated to ensure this happens.
2304             RenderObject* p = r->parent();
2305             while (p && !p->isRenderBlock())
2306                 p = p->parent();
2307             if (p)
2308                 p->setChildNeedsLayout(true);
2309             
2310             deadObjects.append(r);
2311         }
2312     }
2313     
2314     for (unsigned i = 0; i < deadObjects.size(); i++)
2315         m_positionedObjects->remove(deadObjects.at(i));
2316 }
2317
2318 void RenderBlock::insertFloatingObject(RenderBox* o)
2319 {
2320     ASSERT(o->isFloating());
2321
2322     // Create the list of special objects if we don't aleady have one
2323     if (!m_floatingObjects) {
2324         m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
2325         m_floatingObjects->setAutoDelete(true);
2326     } else {
2327         // Don't insert the object again if it's already in the list
2328         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2329         FloatingObject* f;
2330         while ( (f = it.current()) ) {
2331             if (f->m_renderer == o) return;
2332             ++it;
2333         }
2334     }
2335
2336     // Create the special object entry & append it to the list
2337
2338     o->layoutIfNeeded();
2339
2340     FloatingObject* newObj = new FloatingObject(o->style()->floating() == FLEFT ? FloatingObject::FloatLeft : FloatingObject::FloatRight);
2341
2342     newObj->m_top = -1;
2343     newObj->m_bottom = -1;
2344     newObj->m_width = o->width() + o->marginLeft() + o->marginRight();
2345     newObj->m_shouldPaint = !o->hasLayer(); // If a layer exists, the float will paint itself.  Otherwise someone else will.
2346     newObj->m_isDescendant = true;
2347     newObj->m_renderer = o;
2348
2349     m_floatingObjects->append(newObj);
2350 }
2351
2352 void RenderBlock::removeFloatingObject(RenderBox* o)
2353 {
2354     if (m_floatingObjects) {
2355         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2356         while (it.current()) {
2357             if (it.current()->m_renderer == o) {
2358                 if (childrenInline())
2359                     markLinesDirtyInVerticalRange(0, it.current()->m_bottom);
2360                 m_floatingObjects->removeRef(it.current());
2361             }
2362             ++it;
2363         }
2364     }
2365 }
2366
2367 bool RenderBlock::positionNewFloats()
2368 {
2369     if (!m_floatingObjects)
2370         return false;
2371     
2372     FloatingObject* f = m_floatingObjects->last();
2373
2374     // If all floats have already been positioned, then we have no work to do.
2375     if (!f || f->m_top != -1)
2376         return false;
2377
2378     // Move backwards through our floating object list until we find a float that has
2379     // already been positioned.  Then we'll be able to move forward, positioning all of
2380     // the new floats that need it.
2381     FloatingObject* lastFloat = m_floatingObjects->getPrev();
2382     while (lastFloat && lastFloat->m_top == -1) {
2383         f = m_floatingObjects->prev();
2384         lastFloat = m_floatingObjects->getPrev();
2385     }
2386
2387     int y = height();
2388     
2389     // The float cannot start above the y position of the last positioned float.
2390     if (lastFloat)
2391         y = max(lastFloat->m_top, y);
2392
2393     // Now walk through the set of unpositioned floats and place them.
2394     while (f) {
2395         // The containing block is responsible for positioning floats, so if we have floats in our
2396         // list that come from somewhere else, do not attempt to position them.
2397         if (f->m_renderer->containingBlock() != this) {
2398             f = m_floatingObjects->next();
2399             continue;
2400         }
2401
2402         RenderBox* o = f->m_renderer;
2403         int _height = o->height() + o->marginTop() + o->marginBottom();
2404
2405         int ro = rightOffset(); // Constant part of right offset.
2406         int lo = leftOffset(); // Constat part of left offset.
2407         int fwidth = f->m_width; // The width we look for.
2408         if (ro - lo < fwidth)
2409             fwidth = ro - lo; // Never look for more than what will be available.
2410         
2411         IntRect oldRect(o->x(), o->y() , o->width(), o->height());
2412         
2413         if (o->style()->clear() & CLEFT)
2414             y = max(leftBottom(), y);
2415         if (o->style()->clear() & CRIGHT)
2416             y = max(rightBottom(), y);
2417
2418         if (o->style()->floating() == FLEFT) {
2419             int heightRemainingLeft = 1;
2420             int heightRemainingRight = 1;
2421             int fx = leftRelOffset(y,lo, false, &heightRemainingLeft);
2422             while (rightRelOffset(y,ro, false, &heightRemainingRight)-fx < fwidth) {
2423                 y += min(heightRemainingLeft, heightRemainingRight);
2424                 fx = leftRelOffset(y,lo, false, &heightRemainingLeft);
2425             }
2426             fx = max(0, fx);
2427             f->m_left = fx;
2428             o->setLocation(fx + o->marginLeft(), y + o->marginTop());
2429         } else {
2430             int heightRemainingLeft = 1;
2431             int heightRemainingRight = 1;
2432             int fx = rightRelOffset(y,ro, false, &heightRemainingRight);
2433             while (fx - leftRelOffset(y,lo, false, &heightRemainingLeft) < fwidth) {
2434                 y += min(heightRemainingLeft, heightRemainingRight);
2435                 fx = rightRelOffset(y, ro, false, &heightRemainingRight);
2436             }
2437             f->m_left = fx - f->m_width;
2438             o->setLocation(fx - o->marginRight() - o->width(), y + o->marginTop());
2439         }
2440
2441         f->m_top = y;
2442         f->m_bottom = f->m_top + _height;
2443
2444         // If the child moved, we have to repaint it.
2445         if (o->checkForRepaintDuringLayout())
2446             o->repaintDuringLayoutIfMoved(oldRect);
2447
2448         f = m_floatingObjects->next();
2449     }
2450     return true;
2451 }
2452
2453 void RenderBlock::newLine(EClear clear)
2454 {
2455     positionNewFloats();
2456     // set y position
2457     int newY = 0;
2458     switch(clear)
2459     {
2460         case CLEFT:
2461             newY = leftBottom();
2462             break;
2463         case CRIGHT:
2464             newY = rightBottom();
2465             break;
2466         case CBOTH:
2467             newY = floatBottom();
2468         default:
2469             break;
2470     }
2471     if (height() < newY)
2472         setHeight(newY);
2473 }
2474
2475 void RenderBlock::addPercentHeightDescendant(RenderBox* descendant)
2476 {
2477     if (!gPercentHeightDescendantsMap) {
2478         gPercentHeightDescendantsMap = new PercentHeightDescendantsMap;
2479         gPercentHeightContainerMap = new PercentHeightContainerMap;
2480     }
2481
2482     HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->get(this);
2483     if (!descendantSet) {
2484         descendantSet = new HashSet<RenderBox*>;
2485         gPercentHeightDescendantsMap->set(this, descendantSet);
2486     }
2487     bool added = descendantSet->add(descendant).second;
2488     if (!added) {
2489         ASSERT(gPercentHeightContainerMap->get(descendant));
2490         ASSERT(gPercentHeightContainerMap->get(descendant)->contains(this));
2491         return;
2492     }
2493
2494     HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->get(descendant);
2495     if (!containerSet) {
2496         containerSet = new HashSet<RenderBlock*>;
2497         gPercentHeightContainerMap->set(descendant, containerSet);
2498     }
2499     ASSERT(!containerSet->contains(this));
2500     containerSet->add(this);
2501 }
2502
2503 void RenderBlock::removePercentHeightDescendant(RenderBox* descendant)
2504 {
2505     if (!gPercentHeightContainerMap)
2506         return;
2507
2508     HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->take(descendant);
2509     if (!containerSet)
2510         return;
2511
2512     HashSet<RenderBlock*>::iterator end = containerSet->end();
2513     for (HashSet<RenderBlock*>::iterator it = containerSet->begin(); it != end; ++it) {
2514         RenderBlock* container = *it;
2515         HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->get(container);
2516         ASSERT(descendantSet);
2517         if (!descendantSet)
2518             continue;
2519         ASSERT(descendantSet->contains(descendant));
2520         descendantSet->remove(descendant);
2521         if (descendantSet->isEmpty()) {
2522             gPercentHeightDescendantsMap->remove(container);
2523             delete descendantSet;
2524         }
2525     }
2526
2527     delete containerSet;
2528 }
2529
2530 int RenderBlock::leftOffset() const
2531 {
2532     return borderLeft() + paddingLeft();
2533 }
2534
2535 int RenderBlock::leftRelOffset(int y, int fixedOffset, bool applyTextIndent, int* heightRemaining) const
2536 {
2537     int left = fixedOffset;
2538     if (m_floatingObjects) {
2539         if ( heightRemaining ) *heightRemaining = 1;
2540         FloatingObject* r;
2541         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2542         for ( ; (r = it.current()); ++it )
2543         {
2544             if (r->m_top <= y && r->m_bottom > y &&
2545                 r->type() == FloatingObject::FloatLeft &&
2546                 r->m_left + r->m_width > left) {
2547                 left = r->m_left + r->m_width;
2548                 if ( heightRemaining ) *heightRemaining = r->m_bottom - y;
2549             }
2550         }
2551     }
2552
2553     if (applyTextIndent && style()->direction() == LTR) {
2554         int cw = 0;
2555         if (style()->textIndent().isPercent())
2556             cw = containingBlock()->availableWidth();
2557         left += style()->textIndent().calcMinValue(cw);
2558     }
2559
2560     return left;
2561 }
2562
2563 int RenderBlock::rightOffset() const
2564 {
2565     return borderLeft() + paddingLeft() + availableWidth();
2566 }
2567
2568 int RenderBlock::rightRelOffset(int y, int fixedOffset, bool applyTextIndent, int* heightRemaining) const
2569 {
2570     int right = fixedOffset;
2571
2572     if (m_floatingObjects) {
2573         if (heightRemaining) *heightRemaining = 1;
2574         FloatingObject* r;
2575         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2576         for ( ; (r = it.current()); ++it )
2577         {
2578             if (r->m_top <= y && r->m_bottom > y &&
2579                 r->type() == FloatingObject::FloatRight &&
2580                 r->m_left < right) {
2581                 right = r->m_left;
2582                 if ( heightRemaining ) *heightRemaining = r->m_bottom - y;
2583             }
2584         }
2585     }
2586     
2587     if (applyTextIndent && style()->direction() == RTL) {
2588         int cw = 0;
2589         if (style()->textIndent().isPercent())
2590             cw = containingBlock()->availableWidth();
2591         right -= style()->textIndent().calcMinValue(cw);
2592     }
2593     
2594     return right;
2595 }
2596
2597 int
2598 RenderBlock::lineWidth(int y, bool firstLine) const
2599 {
2600     int result = rightOffset(y, firstLine) - leftOffset(y, firstLine);
2601     return (result < 0) ? 0 : result;
2602 }
2603
2604 int RenderBlock::nextFloatBottomBelow(int height) const
2605 {
2606     if (!m_floatingObjects)
2607         return 0;
2608
2609     int bottom = INT_MAX;
2610     FloatingObject* r;
2611     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2612     for ( ; (r = it.current()); ++it) {
2613         if (r->m_bottom > height)
2614             bottom = min(r->m_bottom, bottom);
2615     }
2616
2617     return bottom == INT_MAX ? 0 : bottom;
2618 }
2619
2620 int
2621 RenderBlock::floatBottom() const
2622 {
2623     if (!m_floatingObjects) return 0;
2624     int bottom=0;
2625     FloatingObject* r;
2626     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2627     for ( ; (r = it.current()); ++it )
2628         if (r->m_bottom>bottom)
2629             bottom=r->m_bottom;
2630     return bottom;
2631 }
2632
2633 IntRect RenderBlock::floatRect() const
2634 {
2635     IntRect result;
2636     if (!m_floatingObjects || hasOverflowClip())
2637         return result;
2638     FloatingObject* r;
2639     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2640     for (; (r = it.current()); ++it) {
2641         if (r->m_shouldPaint && !r->m_renderer->hasLayer()) {
2642             IntRect childRect = r->m_renderer->overflowRect(false);
2643             childRect.move(r->m_left + r->m_renderer->marginLeft(), r->m_top + r->m_renderer->marginTop());
2644             result.unite(childRect);
2645         }
2646     }
2647
2648     return result;
2649 }
2650
2651 int RenderBlock::lowestPosition(bool includeOverflowInterior, bool includeSelf) const
2652 {
2653     if (!includeOverflowInterior && (hasOverflowClip() || hasControlClip()))
2654         return includeSelf && width() > 0 ? overflowHeight(false) : 0;
2655     
2656     int bottom = includeSelf && width() > 0 ? height() : 0;
2657     if (!hasColumns()) {
2658         // FIXME: Come up with a way to use the layer tree to avoid visiting all the kids.
2659         // For now, we have to descend into all the children, since we may have a huge abs div inside
2660         // a tiny rel div buried somewhere deep in our child tree.  In this case we have to get to
2661         // the abs div.
2662         for (RenderObject* c = firstChild(); c; c = c->nextSibling()) {
2663             if (!c->isFloatingOrPositioned() && !c->isText() && !c->isRenderInline())
2664                 bottom = max(bottom, toRenderBox(c)->y() + c->lowestPosition(false));
2665         }
2666     }
2667
2668     if (includeSelf && isRelPositioned())
2669         bottom += relativePositionOffsetY();     
2670     if (!includeOverflowInterior && hasOverflowClip())
2671         return bottom;
2672
2673     int relativeOffset = includeSelf && isRelPositioned() ? relativePositionOffsetY() : 0;
2674
2675     if (includeSelf)
2676         bottom = max(bottom, m_overflowHeight + relativeOffset);
2677         
2678     if (m_positionedObjects) {
2679         RenderBox* r;
2680         Iterator end = m_positionedObjects->end();
2681         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2682             r = *it;
2683             // Fixed positioned objects do not scroll and thus should not constitute
2684             // part of the lowest position.
2685             if (r->style()->position() != FixedPosition) {
2686                 // FIXME: Should work for overflow sections too.
2687                 // If a positioned object lies completely to the left of the root it will be unreachable via scrolling.
2688                 // Therefore we should not allow it to contribute to the lowest position.
2689                 if (!isRenderView() || r->x() + r->width() > 0 || r->x() + r->rightmostPosition(false) > 0) {
2690                     int lp = r->y() + r->lowestPosition(false);
2691                     bottom = max(bottom, lp + relativeOffset);
2692                 }
2693             }
2694         }
2695     }
2696
2697     if (hasColumns()) {
2698         Vector<IntRect>* colRects = columnRects();
2699         for (unsigned i = 0; i < colRects->size(); i++)
2700             bottom = max(bottom, colRects->at(i).bottom() + relativeOffset);
2701         return bottom;
2702     }
2703
2704     if (m_floatingObjects) {
2705         FloatingObject* r;
2706         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2707         for ( ; (r = it.current()); ++it ) {
2708             if (r->m_shouldPaint || r->m_renderer->hasLayer()) {
2709                 int lp = r->m_top + r->m_renderer->marginTop() + r->m_renderer->lowestPosition(false);
2710                 bottom = max(bottom, lp + relativeOffset);
2711             }
2712         }
2713     }
2714
2715     if (!includeSelf && lastLineBox()) {
2716         int lp = lastLineBox()->yPos() + lastLineBox()->height();
2717         bottom = max(bottom, lp);
2718     }
2719     
2720     return bottom;
2721 }
2722
2723 int RenderBlock::rightmostPosition(bool includeOverflowInterior, bool includeSelf) const
2724 {
2725     if (!includeOverflowInterior && (hasOverflowClip() || hasControlClip()))
2726         return includeSelf && height() > 0 ? overflowWidth(false) : 0;
2727
2728     int right = includeSelf && height() > 0 ? width() : 0;
2729
2730     if (!hasColumns()) {
2731         // FIXME: Come up with a way to use the layer tree to avoid visiting all the kids.
2732         // For now, we have to descend into all the children, since we may have a huge abs div inside
2733         // a tiny rel div buried somewhere deep in our child tree.  In this case we have to get to
2734         // the abs div.
2735         for (RenderObject* c = firstChild(); c; c = c->nextSibling()) {
2736             if (!c->isFloatingOrPositioned() && c->isBox() && !c->isRenderInline())
2737                 right = max(right, toRenderBox(c)->x() + c->rightmostPosition(false));
2738         }
2739     }
2740
2741     if (includeSelf && isRelPositioned())
2742         right += relativePositionOffsetX();
2743
2744     if (!includeOverflowInterior && hasOverflowClip())
2745         return right;
2746
2747     int relativeOffset = includeSelf && isRelPositioned() ? relativePositionOffsetX() : 0;
2748
2749     if (includeSelf)
2750         right = max(right, m_overflowWidth + relativeOffset);
2751
2752     if (m_positionedObjects) {
2753         RenderBox* r;
2754         Iterator end = m_positionedObjects->end();
2755         for (Iterator it = m_positionedObjects->begin() ; it != end; ++it) {
2756             r = *it;
2757             // Fixed positioned objects do not scroll and thus should not constitute
2758             // part of the rightmost position.
2759             if (r->style()->position() != FixedPosition) {
2760                 // FIXME: Should work for overflow sections too.
2761                 // If a positioned object lies completely above the root it will be unreachable via scrolling.
2762                 // Therefore we should not allow it to contribute to the rightmost position.
2763                 if (!isRenderView() || r->y() + r->height() > 0 || r->y() + r->lowestPosition(false) > 0) {
2764                     int rp = r->x() + r->rightmostPosition(false);
2765                     right = max(right, rp + relativeOffset);
2766                 }
2767             }
2768         }
2769     }
2770
2771     if (hasColumns()) {
2772         // This only matters for LTR
2773         if (style()->direction() == LTR)
2774             right = max(columnRects()->last().right() + relativeOffset, right);
2775         return right;
2776     }
2777
2778     if (m_floatingObjects) {
2779         FloatingObject* r;
2780         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2781         for ( ; (r = it.current()); ++it ) {
2782             if (r->m_shouldPaint || r->m_renderer->hasLayer()) {
2783                 int rp = r->m_left + r->m_renderer->marginLeft() + r->m_renderer->rightmostPosition(false);
2784                 right = max(right, rp + relativeOffset);
2785             }
2786         }
2787     }
2788
2789     if (!includeSelf && firstLineBox()) {
2790         for (InlineRunBox* currBox = firstLineBox(); currBox; currBox = currBox->nextLineBox()) {
2791             int rp = currBox->xPos() + currBox->width();
2792             // If this node is a root editable element, then the rightmostPosition should account for a caret at the end.
2793             // FIXME: Need to find another way to do this, since scrollbars could show when we don't want them to.
2794             if (node()->isContentEditable() && node() == node()->rootEditableElement() && style()->direction() == LTR)
2795                 rp += 1;
2796             right = max(right, rp);
2797         }
2798     }
2799     
2800     return right;
2801 }
2802
2803 int RenderBlock::leftmostPosition(bool includeOverflowInterior, bool includeSelf) const
2804 {
2805     if (!includeOverflowInterior && (hasOverflowClip() || hasControlClip()))
2806         return includeSelf && height() > 0 ? overflowLeft(false) : width();
2807
2808     int left = includeSelf && height() > 0 ? 0 : width();
2809     if (!hasColumns()) {
2810         // FIXME: Come up with a way to use the layer tree to avoid visiting all the kids.
2811         // For now, we have to descend into all the children, since we may have a huge abs div inside
2812         // a tiny rel div buried somewhere deep in our child tree.  In this case we have to get to
2813         // the abs div.
2814         for (RenderObject* c = firstChild(); c; c = c->nextSibling()) {
2815             if (!c->isFloatingOrPositioned() && c->isBox() && !c->isRenderInline())
2816                 left = min(left, toRenderBox(c)->x() + c->leftmostPosition(false));
2817         }
2818     }
2819
2820     if (includeSelf && isRelPositioned())
2821         left += relativePositionOffsetX(); 
2822
2823     if (!includeOverflowInterior && hasOverflowClip())
2824         return left;
2825     
2826     int relativeOffset = includeSelf && isRelPositioned() ? relativePositionOffsetX() : 0;
2827
2828     if (includeSelf)
2829         left = min(left, m_overflowLeft + relativeOffset);
2830
2831     if (m_positionedObjects) {
2832         RenderBox* r;
2833         Iterator end = m_positionedObjects->end();
2834         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2835             r = *it;
2836             // Fixed positioned objects do not scroll and thus should not constitute
2837             // part of the leftmost position.
2838             if (r->style()->position() != FixedPosition) {
2839                 // FIXME: Should work for overflow sections too.
2840                 // If a positioned object lies completely above the root it will be unreachable via scrolling.
2841                 // Therefore we should not allow it to contribute to the leftmost position.
2842                 if (!isRenderView() || r->y() + r->height() > 0 || r->y() + r->lowestPosition(false) > 0) {
2843                     int lp = r->x() + r->leftmostPosition(false);
2844                     left = min(left, lp + relativeOffset);
2845                 }
2846             }
2847         }
2848     }
2849
2850     if (hasColumns()) {
2851         // This only matters for RTL
2852         if (style()->direction() == RTL)
2853             left = min(columnRects()->last().x() + relativeOffset, left);
2854         return left;
2855     }
2856
2857     if (m_floatingObjects) {
2858         FloatingObject* r;
2859         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2860         for ( ; (r = it.current()); ++it ) {
2861             if (r->m_shouldPaint || r->m_renderer->hasLayer()) {
2862                 int lp = r->m_left + r->m_renderer->marginLeft() + r->m_renderer->leftmostPosition(false);
2863                 left = min(left, lp + relativeOffset);
2864             }
2865         }
2866     }
2867
2868     if (!includeSelf && firstLineBox()) {
2869         for (InlineRunBox* currBox = firstLineBox(); currBox; currBox = currBox->nextLineBox())
2870             left = min(left, (int)currBox->xPos());
2871     }
2872     
2873     return left;
2874 }
2875
2876 int
2877 RenderBlock::leftBottom()
2878 {
2879     if (!m_floatingObjects) return 0;
2880     int bottom=0;
2881     FloatingObject* r;
2882     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2883     for ( ; (r = it.current()); ++it )
2884         if (r->m_bottom > bottom && r->type() == FloatingObject::FloatLeft)
2885             bottom=r->m_bottom;
2886
2887     return bottom;
2888 }
2889
2890 int
2891 RenderBlock::rightBottom()
2892 {
2893     if (!m_floatingObjects) return 0;
2894     int bottom=0;
2895     FloatingObject* r;
2896     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2897     for ( ; (r = it.current()); ++it )
2898         if (r->m_bottom>bottom && r->type() == FloatingObject::FloatRight)
2899             bottom=r->m_bottom;
2900
2901     return bottom;
2902 }
2903
2904 void RenderBlock::markLinesDirtyInVerticalRange(int top, int bottom)
2905 {
2906     if (top >= bottom)
2907         return;
2908
2909     RootInlineBox* lowestDirtyLine = lastRootBox();
2910     RootInlineBox* afterLowest = lowestDirtyLine;
2911     while (lowestDirtyLine && lowestDirtyLine->blockHeight() >= bottom) {
2912         afterLowest = lowestDirtyLine;
2913         lowestDirtyLine = lowestDirtyLine->prevRootBox();
2914     }
2915
2916     while (afterLowest && afterLowest->blockHeight() >= top) {
2917         afterLowest->markDirty();
2918         afterLowest = afterLowest->prevRootBox();
2919     }
2920 }
2921
2922 void RenderBlock::clearFloats()
2923 {
2924     // Inline blocks are covered by the isReplaced() check in the avoidFloats method.
2925     if (avoidsFloats() || isRoot() || isRenderView() || isFloatingOrPositioned() || isTableCell()) {
2926         if (m_floatingObjects)
2927             m_floatingObjects->clear();
2928         return;
2929     }
2930
2931     typedef HashMap<RenderObject*, FloatingObject*> RendererToFloatInfoMap;
2932     RendererToFloatInfoMap floatMap;
2933
2934     if (m_floatingObjects) {
2935         if (childrenInline()) {
2936             m_floatingObjects->first();
2937             while (FloatingObject* f = m_floatingObjects->take())
2938                 floatMap.add(f->m_renderer, f);
2939         } else
2940             m_floatingObjects->clear();
2941     }
2942
2943     // Attempt to locate a previous sibling with overhanging floats.  We skip any elements that are
2944     // out of flow (like floating/positioned elements), and we also skip over any objects that may have shifted
2945     // to avoid floats.
2946     bool parentHasFloats = false;
2947     RenderObject* prev = previousSibling();
2948     while (prev && (!prev->isBox() || !prev->isRenderBlock() || prev->avoidsFloats() || prev->isFloatingOrPositioned())) {
2949         if (prev->isFloating())
2950             parentHasFloats = true;
2951          prev = prev->previousSibling();
2952     }
2953
2954     // First add in floats from the parent.
2955     int offset = y();
2956     if (parentHasFloats) {
2957         RenderBlock* parentBlock = static_cast<RenderBlock *>(parent());
2958         addIntrudingFloats(parentBlock, parentBlock->borderLeft() + parentBlock->paddingLeft(), offset);
2959     }
2960     
2961     int xoffset = 0;
2962     if (prev)
2963         offset -= toRenderBox(prev)->y();
2964     else if (parent()->isBox()) {
2965         prev = parent();
2966         xoffset += toRenderBox(prev)->borderLeft() + toRenderBox(prev)->paddingLeft();
2967     }
2968
2969     // Add overhanging floats from the previous RenderBlock, but only if it has a float that intrudes into our space.
2970     if (!prev || !prev->isRenderBlock())
2971         return;
2972     
2973     RenderBlock* block = static_cast<RenderBlock *>(prev);
2974     if (block->m_floatingObjects && block->floatBottom() > offset)
2975         addIntrudingFloats(block, xoffset, offset);
2976
2977     if (childrenInline()) {
2978         int changeTop = INT_MAX;
2979         int changeBottom = INT_MIN;
2980         if (m_floatingObjects) {
2981             for (FloatingObject* f = m_floatingObjects->first(); f; f = m_floatingObjects->next()) {
2982                 FloatingObject* oldFloatingObject = floatMap.get(f->m_renderer);
2983                 if (oldFloatingObject) {
2984                     if (f->m_width != oldFloatingObject->m_width || f->m_left != oldFloatingObject->m_left) {
2985                         changeTop = 0;
2986                         changeBottom = max(changeBottom, max(f->m_bottom, oldFloatingObject->m_bottom));
2987                     } else if (f->m_bottom != oldFloatingObject->m_bottom) {
2988                         changeTop = min(changeTop, min(f->m_bottom, oldFloatingObject->m_bottom));
2989                         changeBottom = max(changeBottom, max(f->m_bottom, oldFloatingObject->m_bottom));
2990                     }
2991
2992                     floatMap.remove(f->m_renderer);
2993                     delete oldFloatingObject;
2994                 } else {
2995                     changeTop = 0;
2996                     changeBottom = max(changeBottom, f->m_bottom);
2997                 }
2998             }
2999         }
3000
3001         RendererToFloatInfoMap::iterator end = floatMap.end();
3002         for (RendererToFloatInfoMap::iterator it = floatMap.begin(); it != end; ++it) {
3003             FloatingObject* floatingObject = (*it).second;
3004             if (!floatingObject->m_isDescendant) {
3005                 changeTop = 0;
3006                 changeBottom = max(changeBottom, floatingObject->m_bottom);
3007             }
3008         }
3009         deleteAllValues(floatMap);
3010
3011         markLinesDirtyInVerticalRange(changeTop, changeBottom);
3012     }
3013 }
3014
3015 int RenderBlock::addOverhangingFloats(RenderBlock* child, int xoff, int yoff, bool makeChildPaintOtherFloats)
3016 {
3017     // Prevent floats from being added to the canvas by the root element, e.g., <html>.
3018     if (child->hasOverflowClip() || !child->containsFloats() || child->isRoot())
3019         return 0;
3020
3021     int lowestFloatBottom = 0;
3022
3023     // Floats that will remain the child's responsiblity to paint should factor into its
3024     // visual overflow.
3025     IntRect floatsOverflowRect;
3026     DeprecatedPtrListIterator<FloatingObject> it(*child->m_floatingObjects);
3027     for (FloatingObject* r; (r = it.current()); ++it) {
3028         int bottom = child->y() + r->m_bottom;
3029         lowestFloatBottom = max(lowestFloatBottom, bottom);
3030
3031         if (bottom > height()) {
3032             // If the object is not in the list, we add it now.
3033             if (!containsFloat(r->m_renderer)) {
3034                 FloatingObject *floatingObj = new FloatingObject(r->type());
3035                 floatingObj->m_top = r->m_top - yoff;
3036                 floatingObj->m_bottom = r->m_bottom - yoff;
3037                 floatingObj->m_left = r->m_left - xoff;
3038                 floatingObj->m_width = r->m_width;
3039                 floatingObj->m_renderer = r->m_renderer;
3040
3041                 // The nearest enclosing layer always paints the float (so that zindex and stacking
3042                 // behaves properly).  We always want to propagate the desire to paint the float as
3043                 // far out as we can, to the outermost block that overlaps the float, stopping only
3044                 // if we hit a layer boundary.
3045                 if (r->m_renderer->enclosingLayer() == enclosingLayer())
3046                     r->m_shouldPaint = false;
3047                 else
3048                     floatingObj->m_shouldPaint = false;
3049                 
3050                 // We create the floating object list lazily.
3051                 if (!m_floatingObjects) {
3052                     m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
3053                     m_floatingObjects->setAutoDelete(true);
3054                 }
3055                 m_floatingObjects->append(floatingObj);
3056             }
3057         } else if (makeChildPaintOtherFloats && !r->m_shouldPaint && !r->m_renderer->hasLayer() && r->m_renderer->isDescendantOf(child) && r->m_renderer->enclosingLayer() == child->enclosingLayer())
3058             // The float is not overhanging from this block, so if it is a descendant of the child, the child should
3059             // paint it (the other case is that it is intruding into the child), unless it has its own layer or enclosing
3060             // layer.
3061             // If makeChildPaintOtherFloats is false, it means that the child must already know about all the floats
3062             // it should paint.
3063             r->m_shouldPaint = true;
3064
3065         if (r->m_shouldPaint && !r->m_renderer->hasLayer()) {
3066             IntRect floatOverflowRect = r->m_renderer->overflowRect(false);
3067             floatOverflowRect.move(r->m_left + r->m_renderer->marginLeft(), r->m_top + r->m_renderer->marginTop());
3068             floatsOverflowRect.unite(floatOverflowRect);
3069         }
3070     }
3071     child->addVisualOverflow(floatsOverflowRect);
3072     return lowestFloatBottom;
3073 }
3074
3075 void RenderBlock::addIntrudingFloats(RenderBlock* prev, int xoff, int yoff)
3076 {
3077     // If the parent or previous sibling doesn't have any floats to add, don't bother.
3078     if (!prev->m_floatingObjects)
3079         return;
3080
3081     DeprecatedPtrListIterator<FloatingObject> it(*prev->m_floatingObjects);
3082     for (FloatingObject *r; (r = it.current()); ++it) {
3083         if (r->m_bottom > yoff) {
3084             // The object may already be in our list. Check for it up front to avoid
3085             // creating duplicate entries.
3086             FloatingObject* f = 0;
3087             if (m_floatingObjects) {
3088                 DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3089                 while ((f = it.current())) {
3090                     if (f->m_renderer == r->m_renderer) break;
3091                     ++it;
3092                 }
3093             }
3094             if (!f) {
3095                 FloatingObject *floatingObj = new FloatingObject(r->type());
3096                 floatingObj->m_top = r->m_top - yoff;
3097                 floatingObj->m_bottom = r->m_bottom - yoff;
3098                 floatingObj->m_left = r->m_left - xoff;
3099                 // Applying the child's margin makes no sense in the case where the child was passed in.
3100                 // since his own margin was added already through the subtraction of the |xoff| variable
3101                 // above.  |xoff| will equal -flow->marginLeft() in this case, so it's already been taken
3102                 // into account.  Only apply this code if |child| is false, since otherwise the left margin
3103                 // will get applied twice.
3104                 if (prev != parent())
3105                     floatingObj->m_left += prev->marginLeft();
3106                 floatingObj->m_left -= marginLeft();
3107                 floatingObj->m_shouldPaint = false;  // We are not in the direct inheritance chain for this float. We will never paint it.
3108                 floatingObj->m_width = r->m_width;
3109                 floatingObj->m_renderer = r->m_renderer;
3110                 
3111                 // We create the floating object list lazily.
3112                 if (!m_floatingObjects) {
3113                     m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
3114                     m_floatingObjects->setAutoDelete(true);
3115                 }
3116                 m_floatingObjects->append(floatingObj);
3117             }
3118         }
3119     }
3120 }
3121
3122 bool RenderBlock::avoidsFloats() const
3123 {
3124     // Floats can't intrude into our box if we have a non-auto column count or width.
3125     return RenderContainer::avoidsFloats() || !style()->hasAutoColumnCount() || !style()->hasAutoColumnWidth();
3126 }
3127
3128 bool RenderBlock::containsFloat(RenderObject* o)
3129 {
3130     if (m_floatingObjects) {
3131         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3132         while (it.current()) {
3133             if (it.current()->m_renderer == o)
3134                 return true;
3135             ++it;
3136         }
3137     }
3138     return false;
3139 }
3140
3141 void RenderBlock::markAllDescendantsWithFloatsForLayout(RenderBox* floatToRemove, bool inLayout)
3142 {
3143     setChildNeedsLayout(true, !inLayout);
3144
3145     if (floatToRemove)
3146         removeFloatingObject(floatToRemove);
3147
3148     // Iterate over our children and mark them as needed.
3149     if (!childrenInline()) {
3150         for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
3151             if (child->isRenderBlock() && !child->isFloatingOrPositioned() &&
3152                 ((floatToRemove ? child->containsFloat(floatToRemove) : child->containsFloats()) || child->shrinkToAvoidFloats()))
3153                 toRenderBlock(child)->markAllDescendantsWithFloatsForLayout(floatToRemove, inLayout);
3154         }
3155     }
3156 }
3157
3158 int RenderBlock::getClearDelta(RenderBox* child)
3159 {
3160     // There is no need to compute clearance if we have no floats.
3161     if (!containsFloats())
3162         return 0;
3163     
3164     // At least one float is present.  We need to perform the clearance computation.
3165     bool clearSet = child->style()->clear() != CNONE;
3166     int bottom = 0;
3167     switch (child->style()->clear()) {
3168         case CNONE:
3169             break;
3170         case CLEFT:
3171             bottom = leftBottom();
3172             break;
3173         case CRIGHT:
3174             bottom = rightBottom();
3175             break;
3176         case CBOTH:
3177             bottom = floatBottom();
3178             break;
3179     }
3180
3181     // 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).
3182     // FIXME: Note that the remaining space checks aren't quite accurate, since you should be able to clear only some floats (the minimum # needed
3183     // to fit) and not all (we should be using nextFloatBottomBelow and looping).
3184     // Do not allow tables to wrap in quirks or even in almost strict mode 
3185     // (ebay on the PLT, finance.yahoo.com in the real world, versiontracker.com forces even almost strict mode not to work)
3186     int result = clearSet ? max(0, bottom - child->y()) : 0;
3187     if (!result && child->avoidsFloats() && child->style()->width().isFixed() && 
3188         child->minPrefWidth() > lineWidth(child->y(), false) && child->minPrefWidth() <= availableWidth() && 
3189         document()->inStrictMode())   
3190         result = max(0, floatBottom() - child->y());
3191     return result;
3192 }
3193
3194 void RenderBlock::addVisualOverflow(const IntRect& r)
3195 {
3196     if (r.isEmpty())
3197         return;
3198     m_overflowLeft = min(m_overflowLeft, r.x());
3199     m_overflowWidth = max(m_overflowWidth, r.right());
3200     m_overflowTop = min(m_overflowTop, r.y());
3201     m_overflowHeight = max(m_overflowHeight, r.bottom());
3202 }
3203
3204 bool RenderBlock::isPointInOverflowControl(HitTestResult& result, int, int, int, int)
3205 {
3206     if (!scrollsOverflow())
3207         return false;
3208
3209     return layer()->hitTestOverflowControls(result);
3210 }
3211
3212 bool RenderBlock::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, int _x, int _y, int _tx, int _ty, HitTestAction hitTestAction)
3213 {
3214     int tx = _tx + x();
3215     int ty = _ty + y();
3216
3217     if (!isRenderView()) {
3218         // Check if we need to do anything at all.
3219         IntRect overflowBox = overflowRect(false);
3220         overflowBox.move(tx, ty);
3221         if (!overflowBox.contains(_x, _y))
3222             return false;
3223     }
3224
3225     if (isPointInOverflowControl(result, _x, _y, tx, ty)) {
3226         if (hitTestAction == HitTestBlockBackground) {
3227             updateHitTestResult(result, IntPoint(_x - tx, _y - ty));
3228             return true;
3229         }
3230         return false;
3231     }
3232
3233      // If we have lightweight control clipping, then we can't have any spillout. 
3234     if (!hasControlClip() || controlClipRect(tx, ty).contains(_x, _y)) {
3235         // Hit test descendants first.
3236         int scrolledX = tx;
3237         int scrolledY = ty;
3238         if (hasOverflowClip())
3239             m_layer->subtractScrolledContentOffset(scrolledX, scrolledY);
3240
3241         // Hit test contents if we don't have columns.
3242         if (!hasColumns() && hitTestContents(request, result, _x, _y, scrolledX, scrolledY, hitTestAction))
3243             return true;
3244             
3245         // Hit test our columns if we do have them.
3246         if (hasColumns() && hitTestColumns(request, result, _x, _y, scrolledX, scrolledY, hitTestAction))
3247             return true;
3248
3249         // Hit test floats.
3250         if (hitTestAction == HitTestFloat && m_floatingObjects) {
3251             if (isRenderView()) {
3252                 scrolledX += toRenderView(this)->frameView()->scrollX();
3253                 scrolledY += toRenderView(this)->frameView()->scrollY();
3254             }
3255             
3256             FloatingObject* o;
3257             DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
3258             for (it.toLast(); (o = it.current()); --it) {
3259                 if (o->m_shouldPaint && !o->m_renderer->hasLayer()) {
3260                     int xoffset = scrolledX + o->m_left + o->m_renderer->marginLeft() - o->m_renderer->x();
3261                     int yoffset =  scrolledY + o->m_top + o->m_renderer->marginTop() - o->m_renderer->y();
3262                     if (o->m_renderer->hitTest(request, result, IntPoint(_x, _y), xoffset, yoffset)) {
3263                         updateHitTestResult(result, IntPoint(_x - xoffset, _y - yoffset));
3264                         return true;
3265                     }
3266                 }
3267             }
3268         }
3269     }
3270
3271     // Now hit test our background
3272     if (hitTestAction == HitTestBlockBackground || hitTestAction == HitTestChildBlockBackground) {
3273         IntRect boundsRect(tx, ty, width(), height());
3274         if (visibleToHitTesting() && boundsRect.contains(_x, _y)) {
3275             updateHitTestResult(result, IntPoint(_x - tx, _y - ty));
3276             return true;
3277         }
3278     }
3279
3280     return false;
3281 }
3282
3283 bool RenderBlock::hitTestColumns(const HitTestRequest& request, HitTestResult& result, int x, int y, int tx, int ty, HitTestAction hitTestAction)
3284 {
3285     // We need to do multiple passes, breaking up our hit testing into strips.
3286     // We can always go left to right, since column contents are clipped (meaning that there
3287     // can't be any overlap).
3288     int currXOffset = 0;
3289     int currYOffset = 0;
3290     int colGap = columnGap();
3291     Vector<IntRect>* colRects = columnRects();
3292     for (unsigned i = 0; i < colRects->size(); i++) {
3293         IntRect colRect = colRects->at(i);
3294         colRect.move(tx, ty);
3295         
3296         if (colRect.contains(x, y)) {
3297             // The point is inside this column.
3298             // Adjust tx and ty to change where we hit test.
3299         
3300             int finalX = tx + currXOffset;
3301             int finalY = ty + currYOffset;
3302             return hitTestContents(request, result, x, y, finalX, finalY, hitTestAction);
3303         }
3304         
3305         // Move to the next position.
3306         if (style()->direction() == LTR)
3307             currXOffset += colRect.width() + colGap;
3308         else
3309             currXOffset -= (colRect.width() + colGap);
3310
3311         currYOffset -= colRect.height();
3312     }
3313
3314     return false;
3315 }
3316
3317 bool RenderBlock::hitTestContents(const HitTestRequest& request, HitTestResult& result, int x, int y, int tx, int ty, HitTestAction hitTestAction)
3318 {
3319     if (childrenInline() && !isTable()) {
3320         // We have to hit-test our line boxes.
3321         if (m_lineBoxes.hitTest(this, request, result, x, y, tx, ty, hitTestAction)) {
3322             updateHitTestResult(result, IntPoint(x - tx, y - ty));
3323             return true;
3324         }
3325     } else {
3326         // Hit test our children.
3327         HitTestAction childHitTest = hitTestAction;
3328         if (hitTestAction == HitTestChildBlockBackgrounds)
3329             childHitTest = HitTestChildBlockBackground;
3330         for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
3331             // FIXME: We have to skip over inline flows, since they can show up inside RenderTables at the moment (a demoted inline <form> for example).  If we ever implement a
3332             // table-specific hit-test method (which we should do for performance reasons anyway), then we can remove this check.
3333             if (!child->hasLayer() && !child->isFloating() && !child->isRenderInline() && child->nodeAtPoint(request, result, x, y, tx, ty, childHitTest)) {
3334                 updateHitTestResult(result, IntPoint(x - tx, y - ty));
3335                 return true;
3336             }
3337         }
3338     }
3339     
3340     return false;
3341 }
3342
3343 Position RenderBlock::positionForBox(InlineBox *box, bool start) const
3344 {
3345     if (!box)
3346         return Position();
3347
3348     if (!box->object()->element())
3349         return Position(element(), start ? caretMinOffset() : caretMaxOffset());
3350
3351     if (!box->isInlineTextBox())
3352         return Position(box->object()->element(), start ? box->object()->caretMinOffset() : box->object()->caretMaxOffset());
3353
3354     InlineTextBox *textBox = static_cast<InlineTextBox *>(box);
3355     return Position(box->object()->element(), start ? textBox->start() : textBox->start() + textBox->len());
3356 }
3357
3358 Position RenderBlock::positionForRenderer(RenderObject* renderer, bool start) const
3359 {
3360     if (!renderer)
3361         return Position(element(), 0);
3362
3363     Node* node = renderer->element() ? renderer->element() : element();
3364     if (!node)
3365         return Position();
3366
3367     ASSERT(renderer == node->renderer());
3368
3369     int offset = start ? renderer->caretMinOffset() : renderer->caretMaxOffset();
3370
3371     // FIXME: This was a runtime check that seemingly couldn't fail; changed it to an assertion for now.
3372     ASSERT(!node->isCharacterDataNode() || renderer->isText());
3373
3374     return Position(node, offset);
3375 }
3376
3377 VisiblePosition RenderBlock::positionForCoordinates(int x, int y)
3378 {
3379     if (isTable())
3380         return RenderContainer::positionForCoordinates(x, y); 
3381
3382     int top = borderTop();
3383     int bottom = top + paddingTop() + contentHeight() + paddingBottom();
3384
3385     int left = borderLeft();
3386     int right = left + paddingLeft() + contentWidth() + paddingRight();
3387
3388     Node* n = element();
3389     
3390     int contentsX = x;
3391     int contentsY = y;
3392     offsetForContents(contentsX, contentsY);
3393
3394     if (isReplaced()) {
3395         if (y < 0 || y < height() && x < 0)
3396             return VisiblePosition(n, caretMinOffset(), DOWNSTREAM);
3397         if (y >= height() || y >= 0 && x >= width())
3398             return VisiblePosition(n, caretMaxOffset(), DOWNSTREAM);
3399     } 
3400
3401     // If we start inside the shadow tree, we will stay inside (even if the point is above or below).
3402     if (!(n && n->isShadowNode()) && !childrenInline()) {
3403         // Don't return positions inside editable roots for coordinates outside those roots, except for coordinates outside
3404         // a document that is entirely editable.
3405         bool isEditableRoot = n && n->rootEditableElement() == n && !n->hasTagName(bodyTag) && !n->hasTagName(htmlTag);
3406
3407         if (y < top || (isEditableRoot && (y < bottom && x < left))) {
3408             if (!isEditableRoot)
3409                 if (RenderBox* c = firstChildBox()) { // FIXME: This code doesn't make any sense.  This child could be an inline or a positioned element or a float, etc.
3410                     VisiblePosition p = c->positionForCoordinates(contentsX - c->x(), contentsY - c->y());
3411                     if (p.isNotNull())
3412                         return p;
3413                 }
3414             if (n) {
3415                 if (Node* sp = n->shadowParentNode())
3416                     n = sp;
3417                 if (Node* p = n->parent())
3418                     return VisiblePosition(p, n->nodeIndex(), DOWNSTREAM);
3419             }
3420             return VisiblePosition(n, 0, DOWNSTREAM);
3421         }
3422
3423         if (y >= bottom || (isEditableRoot && (y >= top && x >= right))) {
3424             if (!isEditableRoot)
3425                 if (RenderBox* c = lastChildBox()) { // FIXME: This code doesn't make any sense.  This child could be an inline or a positioned element or a float, etc.
3426                     VisiblePosition p = c->positionForCoordinates(contentsX - c->x(), contentsY - c->y());
3427                     if (p.isNotNull())
3428                         return p;
3429                 }
3430             if (n) {
3431                 if (Node* sp = n->shadowParentNode())
3432                     n = sp;
3433                 if (Node* p = n->parent())
3434                     return VisiblePosition(p, n->nodeIndex() + 1, DOWNSTREAM);
3435             }
3436             return VisiblePosition(n, 0, DOWNSTREAM);
3437         }
3438     }
3439
3440     if (childrenInline()) {
3441         if (!firstRootBox())
3442             return VisiblePosition(n, 0, DOWNSTREAM);
3443
3444         if (contentsY < firstRootBox()->topOverflow() - verticalLineClickFudgeFactor)
3445             // y coordinate is above first root line box
3446             return VisiblePosition(positionForBox(firstRootBox()->firstLeafChild(), true), DOWNSTREAM);
3447         
3448         // look for the closest line box in the root box which is at the passed-in y coordinate
3449         for (RootInlineBox* root = firstRootBox(); root; root = root->nextRootBox()) {
3450             // set the bottom based on whether there is a next root box
3451             if (root->nextRootBox())
3452                 // FIXME: make the break point halfway between the bottom of the previous root box and the top of the next root box
3453                 bottom = root->nextRootBox()->topOverflow();
3454             else
3455                 bottom = root->bottomOverflow() + verticalLineClickFudgeFactor;
3456             // check if this root line box is located at this y coordinate
3457             if (contentsY < bottom && root->firstChild()) {
3458                 InlineBox* closestBox = root->closestLeafChildForXPos(x);
3459                 if (closestBox)
3460                     // pass the box a y position that is inside it
3461                     return closestBox->object()->positionForCoordinates(contentsX, closestBox->m_y);
3462             }
3463         }
3464
3465         if (lastRootBox())
3466             // y coordinate is below last root line box
3467             return VisiblePosition(positionForBox(lastRootBox()->lastLeafChild(), false), DOWNSTREAM);
3468
3469         return VisiblePosition(n, 0, DOWNSTREAM);
3470     }
3471     
3472     // See if any child blocks exist at this y coordinate.
3473     if (firstChildBox() && contentsY < firstChildBox()->y())
3474         return VisiblePosition(n, 0, DOWNSTREAM);
3475     for (RenderBox* renderer = firstChildBox(); renderer; renderer = renderer->nextSiblingBox()) {
3476         if (renderer->height() == 0 || renderer->style()->visibility() != VISIBLE || renderer->isFloatingOrPositioned())
3477             continue;
3478         RenderBox* next = renderer->nextSiblingBox();
3479         while (next && next->isFloatingOrPositioned())
3480             next = next->nextSiblingBox();
3481         if (next) 
3482             bottom = next->y();
3483         else
3484             bottom = top + scrollHeight();
3485         if (contentsY >= renderer->y() && contentsY < bottom)
3486             return renderer->positionForCoordinates(contentsX - renderer->x(), contentsY - renderer->y());
3487     }
3488     
3489     return RenderContainer::positionForCoordinates(x, y);
3490 }
3491
3492 void RenderBlock::offsetForContents(int& tx, int& ty) const
3493 {
3494     if (hasOverflowClip())
3495         m_layer->addScrolledContentOffset(tx, ty);
3496
3497     if (hasColumns()) {
3498         IntPoint contentsPoint(tx, ty);
3499         adjustPointToColumnContents(contentsPoint);
3500         tx = contentsPoint.x();
3501         ty = contentsPoint.y();
3502     }
3503 }
3504
3505 int RenderBlock::availableWidth() const
3506 {
3507     // If we have multiple columns, then the available width is reduced to our column width.
3508     if (hasColumns())
3509         return desiredColumnWidth();
3510     return contentWidth();
3511 }
3512
3513 int RenderBlock::columnGap() const
3514 {
3515     if (style()->hasNormalColumnGap())
3516         return style()->fontDescription().computedPixelSize(); // "1em" is recommended as the normal gap setting. Matches <p> margins.
3517     return static_cast<int>(style()->columnGap());
3518 }
3519
3520 void RenderBlock::calcColumnWidth()
3521 {    
3522     // Calculate our column width and column count.
3523     unsigned desiredColumnCount = 1;
3524     int desiredColumnWidth = contentWidth();
3525     
3526     // For now, we don't support multi-column layouts when printing, since we have to do a lot of work for proper pagination.
3527     if (document()->printing() || (style()->hasAutoColumnCount() && style()->hasAutoColumnWidth())) {
3528         setDesiredColumnCountAndWidth(desiredColumnCount, desiredColumnWidth);
3529         return;
3530     }
3531         
3532     int availWidth = desiredColumnWidth;
3533     int colGap = columnGap();
3534     int colWidth = max(1, static_cast<int>(style()->columnWidth()));
3535     int colCount = max(1, static_cast<int>(style()->columnCount()));
3536
3537     if (style()->hasAutoColumnWidth()) {
3538         if ((colCount - 1) * colGap < availWidth) {
3539             desiredColumnCount = colCount;
3540             desiredColumnWidth = (availWidth - (desiredColumnCount - 1) * colGap) / desiredColumnCount;
3541         } else if (colGap < availWidth) {
3542             desiredColumnCount = availWidth / colGap;
3543             desiredColumnWidth = (availWidth - (desiredColumnCount - 1) * colGap) / desiredColumnCount;
3544         }
3545     } else if (style()->hasAutoColumnCount()) {
3546         if (colWidth < availWidth) {
3547             desiredColumnCount = (availWidth + colGap) / (colWidth + colGap);
3548             desiredColumnWidth = (availWidth - (desiredColumnCount - 1) * colGap) / desiredColumnCount;
3549         }
3550     } else {
3551         // Both are set.
3552         if (colCount * colWidth + (colCount - 1) * colGap <= availWidth) {
3553             desiredColumnCount = colCount;
3554             desiredColumnWidth = colWidth;
3555         } else if (colWidth < availWidth) {
3556             desiredColumnCount = (availWidth + colGap) / (colWidth + colGap);
3557             desiredColumnWidth = (availWidth - (desiredColumnCount - 1) * colGap) / desiredColumnCount;
3558         }
3559     }
3560     setDesiredColumnCountAndWidth(desiredColumnCount, desiredColumnWidth);
3561 }
3562
3563 void RenderBlock::setDesiredColumnCountAndWidth(int count, int width)
3564 {
3565     if (count == 1) {
3566         if (hasColumns()) {
3567             delete gColumnInfoMap->take(this);
3568             setHasColumns(false);
3569         }
3570     } else {
3571         ColumnInfo* info;
3572         if (hasColumns())
3573             info = gColumnInfoMap->get(this);
3574         else {
3575             if (!gColumnInfoMap)
3576                 gColumnInfoMap = new ColumnInfoMap;
3577             info = new ColumnInfo;
3578             gColumnInfoMap->add(this, info);
3579             setHasColumns(true);
3580         }
3581         info->m_desiredColumnCount = count;
3582         info->m_desiredColumnWidth = width;   
3583     }
3584 }
3585
3586 int RenderBlock::desiredColumnWidth() const
3587 {
3588     if (!hasColumns())
3589         return contentWidth();
3590     return gColumnInfoMap->get(this)->m_desiredColumnWidth;
3591 }
3592
3593 unsigned RenderBlock::desiredColumnCount() const
3594 {
3595     if (!hasColumns())
3596         return 1;
3597     return gColumnInfoMap->get(this)->m_desiredColumnCount;
3598 }
3599
3600 Vector<IntRect>* RenderBlock::columnRects() const
3601 {
3602     if (!hasColumns())
3603         return 0;
3604     return &gColumnInfoMap->get(this)->m_columnRects;    
3605 }
3606
3607 int RenderBlock::layoutColumns(int endOfContent)
3608 {
3609     // Don't do anything if we have no columns
3610     if (!hasColumns())
3611         return -1;
3612
3613     ColumnInfo* info = gColumnInfoMap->get(this);
3614     int desiredColumnWidth = info->m_desiredColumnWidth;
3615     int desiredColumnCount = info->m_desiredColumnCount;
3616     Vector<IntRect>* columnRects = &info->m_columnRects;
3617     
3618     bool computeIntrinsicHeight = (endOfContent == -1);
3619
3620     // Fill the columns in to the available height.  Attempt to balance the height of the columns
3621     int availableHeight = contentHeight();
3622     int colHeight = computeIntrinsicHeight ? availableHeight / desiredColumnCount : availableHeight;
3623     
3624     // Add in half our line-height to help with best-guess initial balancing.
3625     int columnSlop = lineHeight(false) / 2;
3626     int remainingSlopSpace = columnSlop * desiredColumnCount;
3627
3628     if (computeIntrinsicHeight)
3629         colHeight += columnSlop;
3630                                                                             
3631     int colGap = columnGap();
3632
3633     // Compute a collection of column rects.
3634     columnRects->clear();
3635     
3636     // Then we do a simulated "paint" into the column slices and allow the content to slightly adjust our individual column rects.
3637     // FIXME: We need to take into account layers that are affected by the columns as well here so that they can have an opportunity
3638     // to adjust column rects also.
3639     RenderView* v = view();
3640     int left = borderLeft() + paddingLeft();
3641     int top = borderTop() + paddingTop();
3642     int currX = style()->direction() == LTR ? borderLeft() + paddingLeft() : borderLeft() + paddingLeft() + contentWidth() - desiredColumnWidth;
3643     int currY = top;
3644     unsigned colCount = desiredColumnCount;
3645     int maxColBottom = borderTop() + paddingTop();
3646     int contentBottom = top + availableHeight; 
3647     for (unsigned i = 0; i < colCount; i++) {
3648         // If we aren't constrained, then the last column can just get all the remaining space.
3649         if (computeIntrinsicHeight && i == colCount - 1)
3650             colHeight = availableHeight;
3651
3652         // This represents the real column position.
3653         IntRect colRect(currX, top, desiredColumnWidth, colHeight);
3654         
3655         // For the simulated paint, we pretend like everything is in one long strip.
3656         IntRect pageRect(left, currY, desiredColumnWidth, colHeight);
3657         v->setPrintRect(pageRect);
3658         v->setTruncatedAt(currY + colHeight);
3659         GraphicsContext context((PlatformGraphicsContext*)0);
3660         RenderObject::PaintInfo paintInfo(&context, pageRect, PaintPhaseForeground, false, 0, 0);
3661         
3662         setHasColumns(false);
3663         paintObject(paintInfo, 0, 0);
3664         setHasColumns(true);
3665
3666         int adjustedBottom = v->bestTruncatedAt();
3667         if (adjustedBottom <= currY)
3668             adjustedBottom = currY + colHeight;
3669         
3670         colRect.setHeight(adjustedBottom - currY);
3671         
3672         // Add in the lost space to the subsequent columns.
3673         // FIXME: This will create a "staircase" effect if there are enough columns, but the effect should be pretty subtle.
3674         if (computeIntrinsicHeight) {
3675             int lostSpace = colHeight - colRect.height();
3676             if (lostSpace > remainingSlopSpace) {
3677                 // Redestribute the space among the remaining columns.
3678                 int spaceToRedistribute = lostSpace - remainingSlopSpace;
3679                 int remainingColumns = colCount - i + 1;
3680                 colHeight += spaceToRedistribute / remainingColumns;
3681             } 
3682             remainingSlopSpace = max(0, remainingSlopSpace - lostSpace);
3683         }
3684         
3685         if (style()->direction() == LTR)
3686             currX += desiredColumnWidth + colGap;
3687         else
3688             currX -= (desiredColumnWidth + colGap);
3689
3690         currY += colRect.height();
3691         availableHeight -= colRect.height();
3692
3693         maxColBottom = max(colRect.bottom(), maxColBottom);
3694
3695         columnRects->append(colRect);
3696         
3697         // Start adding in more columns as long as there's still content left.
3698         if (currY < endOfContent && i == colCount - 1 && (computeIntrinsicHeight || contentHeight()))
3699             colCount++;
3700     }
3701
3702     m_overflowWidth = max(width(), currX - colGap);
3703     m_overflowLeft = min(0, currX + desiredColumnWidth + colGap);
3704
3705     m_overflowHeight = maxColBottom;
3706     int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
3707         
3708     if (computeIntrinsicHeight)
3709         setHeight(m_overflowHeight + toAdd);
3710
3711     v->setPrintRect(IntRect());
3712     v->setTruncatedAt(0);
3713     
3714     ASSERT(colCount == columnRects->size());
3715     
3716     return contentBottom;
3717 }
3718
3719 void RenderBlock::adjustPointToColumnContents(IntPoint& point) const
3720 {
3721     // Just bail if we have no columns.
3722     if (!hasColumns())
3723         return;
3724     
3725     Vector<IntRect>* colRects = columnRects();
3726
3727     // Determine which columns we intersect.
3728     int colGap = columnGap();
3729     int leftGap = colGap / 2;
3730     IntPoint columnPoint(colRects->at(0).location());
3731     int yOffset = 0;
3732     for (unsigned i = 0; i < colRects->size(); i++) {
3733         // Add in half the column gap to the left and right of the rect.
3734         IntRect colRect = colRects->at(i);
3735         IntRect gapAndColumnRect(colRect.x() - leftGap, colRect.y(), colRect.width() + colGap, colRect.height());
3736         
3737         if (gapAndColumnRect.contains(point)) {
3738             // We're inside the column.  Translate the x and y into our column coordinate space.
3739             point.move(columnPoint.x() - colRect.x(), yOffset);
3740             return;
3741         }
3742
3743         // Move to the next position.
3744         yOffset += colRect.height();
3745     }
3746 }
3747
3748 void RenderBlock::adjustRectForColumns(IntRect& r) const
3749 {
3750     // Just bail if we have no columns.
3751     if (!hasColumns())
3752         return;
3753     
3754     Vector<IntRect>* colRects = columnRects();
3755
3756     // Begin with a result rect that is empty.
3757     IntRect result;
3758     
3759     // Determine which columns we intersect.
3760     int currXOffset = 0;
3761     int currYOffset = 0;
3762     int colGap = columnGap();
3763     for (unsigned i = 0; i < colRects->size(); i++) {
3764         IntRect colRect = colRects->at(i);
3765         
3766         IntRect repaintRect = r;
3767         repaintRect.move(currXOffset, currYOffset);
3768         
3769         repaintRect.intersect(colRect);
3770         
3771         result.unite(repaintRect);
3772
3773         // Move to the next position.
3774         if (style()->direction() == LTR)
3775             currXOffset += colRect.width() + colGap;
3776         else
3777             currXOffset -= (colRect.width() + colGap);
3778
3779         currYOffset -= colRect.height();
3780     }
3781
3782     r = result;
3783 }
3784
3785 void RenderBlock::calcPrefWidths()
3786 {
3787     ASSERT(prefWidthsDirty());
3788
3789     updateFirstLetter();
3790
3791     if (!isTableCell() && style()->width().isFixed() && style()->width().value() > 0)
3792         m_minPrefWidth = m_maxPrefWidth = calcContentBoxWidth(style()->width().value());
3793     else {
3794         m_minPrefWidth = 0;
3795         m_maxPrefWidth = 0;
3796
3797         if (childrenInline())
3798             calcInlinePrefWidths();
3799         else
3800             calcBlockPrefWidths();
3801
3802         m_maxPrefWidth = max(m_minPrefWidth, m_maxPrefWidth);
3803
3804         if (!style()->autoWrap() && childrenInline()) {
3805             m_minPrefWidth = m_maxPrefWidth;
3806             
3807             // A horizontal marquee with inline children has no minimum width.
3808             if (m_layer && m_layer->marquee() && m_layer->marquee()->isHorizontal())
3809                 m_minPrefWidth = 0;
3810         }
3811
3812         if (isTableCell()) {
3813             Length w = static_cast<const RenderTableCell*>(this)->styleOrColWidth();
3814             if (w.isFixed() && w.value() > 0)
3815                 m_maxPrefWidth = max(m_minPrefWidth, calcContentBoxWidth(w.value()));
3816         }
3817     }
3818     
3819     if (style()->minWidth().isFixed() && style()->minWidth().value() > 0) {
3820         m_maxPrefWidth = max(m_maxPrefWidth, calcContentBoxWidth(style()->minWidth().value()));
3821         m_minPrefWidth = max(m_minPrefWidth, calcContentBoxWidth(style()->minWidth().value()));
3822     }
3823     
3824     if (style()->maxWidth().isFixed() && style()->maxWidth().value() != undefinedLength) {
3825         m_maxPrefWidth = min(m_maxPrefWidth, calcContentBoxWidth(style()->maxWidth().value()));
3826         m_minPrefWidth = min(m_minPrefWidth, calcContentBoxWidth(style()->maxWidth().value()));
3827     }
3828
3829     int toAdd = 0;
3830     toAdd = borderLeft() + borderRight() + paddingLeft() + paddingRight();
3831
3832     m_minPrefWidth += toAdd;
3833     m_maxPrefWidth += toAdd;
3834
3835     setPrefWidthsDirty(false);
3836 }
3837
3838 struct InlineMinMaxIterator
3839 {
3840 /* InlineMinMaxIterator is a class that will iterate over all render objects that contribute to