Move the 'overflow' event dispatching logic out of RenderLayer
[WebKit.git] / Source / 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, 2009, 2010, 2011 Apple Inc. All rights reserved.
6  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23
24 #include "config.h"
25 #include "RenderBlock.h"
26
27 #include "ColumnInfo.h"
28 #include "Document.h"
29 #include "Element.h"
30 #include "FloatQuad.h"
31 #include "Frame.h"
32 #include "FrameSelection.h"
33 #include "FrameView.h"
34 #include "GraphicsContext.h"
35 #include "HTMLFormElement.h"
36 #include "HTMLNames.h"
37 #include "HitTestResult.h"
38 #include "InlineIterator.h"
39 #include "InlineTextBox.h"
40 #include "LayoutRepainter.h"
41 #include "OverflowEvent.h"
42 #include "PODFreeListArena.h"
43 #include "Page.h"
44 #include "PaintInfo.h"
45 #include "RenderBoxRegionInfo.h"
46 #include "RenderCombineText.h"
47 #include "RenderDeprecatedFlexibleBox.h"
48 #include "RenderFlowThread.h"
49 #include "RenderImage.h"
50 #include "RenderInline.h"
51 #include "RenderLayer.h"
52 #include "RenderMarquee.h"
53 #include "RenderRegion.h"
54 #include "RenderReplica.h"
55 #include "RenderTableCell.h"
56 #include "RenderTextFragment.h"
57 #include "RenderTheme.h"
58 #include "RenderView.h"
59 #include "Settings.h"
60 #include "SVGTextRunRenderingContext.h"
61 #include "TransformState.h"
62 #include <wtf/StdLibExtras.h>
63
64 using namespace std;
65 using namespace WTF;
66 using namespace Unicode;
67
68 namespace WebCore {
69
70 using namespace HTMLNames;
71
72 typedef WTF::HashMap<const RenderBox*, ColumnInfo*> ColumnInfoMap;
73 static ColumnInfoMap* gColumnInfoMap = 0;
74
75 typedef WTF::HashMap<const RenderBlock*, HashSet<RenderBox*>*> PercentHeightDescendantsMap;
76 static PercentHeightDescendantsMap* gPercentHeightDescendantsMap = 0;
77
78 typedef WTF::HashMap<const RenderBox*, HashSet<RenderBlock*>*> PercentHeightContainerMap;
79 static PercentHeightContainerMap* gPercentHeightContainerMap = 0;
80     
81 typedef WTF::HashMap<RenderBlock*, ListHashSet<RenderInline*>*> ContinuationOutlineTableMap;
82
83 typedef WTF::HashSet<RenderBlock*> DelayedUpdateScrollInfoSet;
84 static int gDelayUpdateScrollInfo = 0;
85 static DelayedUpdateScrollInfoSet* gDelayedUpdateScrollInfoSet = 0;
86
87 bool RenderBlock::s_canPropagateFloatIntoSibling = false;
88
89 // This class helps dispatching the 'overflow' event on layout change. overflow can be set on RenderBoxes, yet the existing code
90 // only works on RenderBlocks. If this change, this class should be shared with other RenderBoxes.
91 class OverflowEventDispatcher {
92     WTF_MAKE_NONCOPYABLE(OverflowEventDispatcher);
93 public:
94     OverflowEventDispatcher(const RenderBlock* block)
95         : m_block(block)
96         , m_hadHorizontalLayoutOverflow(false)
97         , m_hadVerticalLayoutOverflow(false)
98     {
99         m_shouldDispatchEvent = !m_block->isAnonymous() && m_block->hasOverflowClip() && m_block->document()->hasListenerType(Document::OVERFLOWCHANGED_LISTENER);
100         if (m_shouldDispatchEvent) {
101             m_hadHorizontalLayoutOverflow = m_block->hasHorizontalLayoutOverflow();
102             m_hadVerticalLayoutOverflow = m_block->hasVerticalLayoutOverflow();
103         }
104     }
105
106     ~OverflowEventDispatcher()
107     {
108         if (!m_shouldDispatchEvent)
109             return;
110
111         bool hasHorizontalLayoutOverflow = m_block->hasHorizontalLayoutOverflow();
112         bool hasVerticalLayoutOverflow = m_block->hasVerticalLayoutOverflow();
113
114         bool horizontalLayoutOverflowChanged = hasHorizontalLayoutOverflow != m_hadHorizontalLayoutOverflow;
115         bool verticalLayoutOverflowChanged = hasVerticalLayoutOverflow != m_hadVerticalLayoutOverflow;
116         if (horizontalLayoutOverflowChanged || verticalLayoutOverflowChanged) {
117             if (FrameView* frameView = m_block->document()->view())
118                 frameView->scheduleEvent(OverflowEvent::create(horizontalLayoutOverflowChanged, hasHorizontalLayoutOverflow, verticalLayoutOverflowChanged, hasVerticalLayoutOverflow), m_block->node());
119         }
120     }
121
122 private:
123     void computeOverflowStatus(bool& hasHorizontalLayoutOverflow, bool& hasVerticalLayoutOverflow)
124     {
125     }
126
127     const RenderBlock* m_block;
128     bool m_shouldDispatchEvent;
129     bool m_hadHorizontalLayoutOverflow;
130     bool m_hadVerticalLayoutOverflow;
131 };
132
133 // Our MarginInfo state used when laying out block children.
134 RenderBlock::MarginInfo::MarginInfo(RenderBlock* block, LayoutUnit beforeBorderPadding, LayoutUnit afterBorderPadding)
135     : m_atBeforeSideOfBlock(true)
136     , m_atAfterSideOfBlock(false)
137     , m_marginBeforeQuirk(false)
138     , m_marginAfterQuirk(false)
139     , m_determinedMarginBeforeQuirk(false)
140 {
141     // Whether or not we can collapse our own margins with our children.  We don't do this
142     // if we had any border/padding (obviously), if we're the root or HTML elements, or if
143     // we're positioned, floating, a table cell.
144     RenderStyle* blockStyle = block->style();
145     m_canCollapseWithChildren = !block->isRenderView() && !block->isRoot() && !block->isPositioned()
146         && !block->isFloating() && !block->isTableCell() && !block->hasOverflowClip() && !block->isInlineBlockOrInlineTable()
147         && !block->isWritingModeRoot() && blockStyle->hasAutoColumnCount() && blockStyle->hasAutoColumnWidth()
148         && !blockStyle->columnSpan();
149
150     m_canCollapseMarginBeforeWithChildren = m_canCollapseWithChildren && !beforeBorderPadding && blockStyle->marginBeforeCollapse() != MSEPARATE;
151
152     // If any height other than auto is specified in CSS, then we don't collapse our bottom
153     // margins with our children's margins.  To do otherwise would be to risk odd visual
154     // effects when the children overflow out of the parent block and yet still collapse
155     // with it.  We also don't collapse if we have any bottom border/padding.
156     m_canCollapseMarginAfterWithChildren = m_canCollapseWithChildren && (afterBorderPadding == 0) &&
157         (blockStyle->logicalHeight().isAuto() && !blockStyle->logicalHeight().value()) && blockStyle->marginAfterCollapse() != MSEPARATE;
158     
159     m_quirkContainer = block->isTableCell() || block->isBody() || blockStyle->marginBeforeCollapse() == MDISCARD
160         || blockStyle->marginAfterCollapse() == MDISCARD;
161
162     m_positiveMargin = m_canCollapseMarginBeforeWithChildren ? block->maxPositiveMarginBefore() : zeroLayoutUnit;
163     m_negativeMargin = m_canCollapseMarginBeforeWithChildren ? block->maxNegativeMarginBefore() : zeroLayoutUnit;
164 }
165
166 // -------------------------------------------------------------------------------------------------------
167
168 RenderBlock::RenderBlock(Node* node)
169       : RenderBox(node)
170       , m_lineHeight(-1)
171       , m_beingDestroyed(false)
172       , m_hasPositionedFloats(false)
173 {
174     setChildrenInline(true);
175 }
176
177 RenderBlock::~RenderBlock()
178 {
179     if (m_floatingObjects)
180         deleteAllValues(m_floatingObjects->set());
181     
182     if (hasColumns())
183         delete gColumnInfoMap->take(this);
184
185     if (gPercentHeightDescendantsMap) {
186         if (HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->take(this)) {
187             HashSet<RenderBox*>::iterator end = descendantSet->end();
188             for (HashSet<RenderBox*>::iterator descendant = descendantSet->begin(); descendant != end; ++descendant) {
189                 HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->get(*descendant);
190                 ASSERT(containerSet);
191                 if (!containerSet)
192                     continue;
193                 ASSERT(containerSet->contains(this));
194                 containerSet->remove(this);
195                 if (containerSet->isEmpty()) {
196                     gPercentHeightContainerMap->remove(*descendant);
197                     delete containerSet;
198                 }
199             }
200             delete descendantSet;
201         }
202     }
203 }
204
205 void RenderBlock::willBeDestroyed()
206 {
207     // Mark as being destroyed to avoid trouble with merges in removeChild().
208     m_beingDestroyed = true;
209
210     // Make sure to destroy anonymous children first while they are still connected to the rest of the tree, so that they will
211     // properly dirty line boxes that they are removed from. Effects that do :before/:after only on hover could crash otherwise.
212     children()->destroyLeftoverChildren();
213
214     // Destroy our continuation before anything other than anonymous children.
215     // The reason we don't destroy it before anonymous children is that they may
216     // have continuations of their own that are anonymous children of our continuation.
217     RenderBoxModelObject* continuation = this->continuation();
218     if (continuation) {
219         continuation->destroy();
220         setContinuation(0);
221     }
222     
223     if (!documentBeingDestroyed()) {
224         if (firstLineBox()) {
225             // We can't wait for RenderBox::destroy to clear the selection,
226             // because by then we will have nuked the line boxes.
227             // FIXME: The FrameSelection should be responsible for this when it
228             // is notified of DOM mutations.
229             if (isSelectionBorder())
230                 view()->clearSelection();
231
232             // If we are an anonymous block, then our line boxes might have children
233             // that will outlast this block. In the non-anonymous block case those
234             // children will be destroyed by the time we return from this function.
235             if (isAnonymousBlock()) {
236                 for (InlineFlowBox* box = firstLineBox(); box; box = box->nextLineBox()) {
237                     while (InlineBox* childBox = box->firstChild())
238                         childBox->remove();
239                 }
240             }
241         } else if (parent())
242             parent()->dirtyLinesFromChangedChild(this);
243     }
244
245     m_lineBoxes.deleteLineBoxes(renderArena());
246
247     if (lineGridBox())
248         lineGridBox()->destroy(renderArena());
249
250     if (UNLIKELY(gDelayedUpdateScrollInfoSet != 0))
251         gDelayedUpdateScrollInfoSet->remove(this);
252
253     RenderBox::willBeDestroyed();
254 }
255
256 void RenderBlock::styleWillChange(StyleDifference diff, const RenderStyle* newStyle)
257 {
258     RenderStyle* oldStyle = style();
259     s_canPropagateFloatIntoSibling = oldStyle ? !isFloatingOrPositioned() && !avoidsFloats() : false;
260
261     setReplaced(newStyle->isDisplayInlineType());
262     
263     if (oldStyle && parent() && diff == StyleDifferenceLayout && oldStyle->position() != newStyle->position()) {
264         if (newStyle->position() == StaticPosition)
265             // Clear our positioned objects list. Our absolutely positioned descendants will be
266             // inserted into our containing block's positioned objects list during layout.
267             removePositionedObjects(0);
268         else if (oldStyle->position() == StaticPosition) {
269             // Remove our absolutely positioned descendants from their current containing block.
270             // They will be inserted into our positioned objects list during layout.
271             RenderObject* cb = parent();
272             while (cb && (cb->style()->position() == StaticPosition || (cb->isInline() && !cb->isReplaced())) && !cb->isRenderView()) {
273                 if (cb->style()->position() == RelativePosition && cb->isInline() && !cb->isReplaced()) {
274                     cb = cb->containingBlock();
275                     break;
276                 }
277                 cb = cb->parent();
278             }
279             
280             if (cb->isRenderBlock())
281                 toRenderBlock(cb)->removePositionedObjects(this);
282         }
283
284         if (containsFloats() && !isFloating() && !isPositioned() && (newStyle->position() == AbsolutePosition || newStyle->position() == FixedPosition))
285             markAllDescendantsWithFloatsForLayout();
286     }
287
288     RenderBox::styleWillChange(diff, newStyle);
289 }
290
291 void RenderBlock::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
292 {
293     RenderBox::styleDidChange(diff, oldStyle);
294
295     if (!isAnonymousBlock()) {
296         // Ensure that all of our continuation blocks pick up the new style.
297         for (RenderBlock* currCont = blockElementContinuation(); currCont; currCont = currCont->blockElementContinuation()) {
298             RenderBoxModelObject* nextCont = currCont->continuation();
299             currCont->setContinuation(0);
300             currCont->setStyle(style());
301             currCont->setContinuation(nextCont);
302         }
303     }
304
305     propagateStyleToAnonymousChildren(true);    
306     m_lineHeight = -1;
307
308     // Update pseudos for :before and :after now.
309     if (!isAnonymous() && document()->usesBeforeAfterRules() && canHaveChildren()) {
310         updateBeforeAfterContent(BEFORE);
311         updateBeforeAfterContent(AFTER);
312     }
313
314     // After our style changed, if we lose our ability to propagate floats into next sibling
315     // blocks, then we need to find the top most parent containing that overhanging float and
316     // then mark its descendants with floats for layout and clear all floats from its next
317     // sibling blocks that exist in our floating objects list. See bug 56299 and 62875.
318     bool canPropagateFloatIntoSibling = !isFloatingOrPositioned() && !avoidsFloats();
319     if (diff == StyleDifferenceLayout && s_canPropagateFloatIntoSibling && !canPropagateFloatIntoSibling && hasOverhangingFloats()) {
320         RenderBlock* parentBlock = this;
321         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
322         FloatingObjectSetIterator end = floatingObjectSet.end();
323
324         for (RenderObject* curr = parent(); curr && !curr->isRenderView(); curr = curr->parent()) {
325             if (curr->isRenderBlock()) {
326                 RenderBlock* currBlock = toRenderBlock(curr);
327
328                 if (currBlock->hasOverhangingFloats()) {
329                     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
330                         RenderBox* renderer = (*it)->renderer();
331                         if (currBlock->hasOverhangingFloat(renderer)) {
332                             parentBlock = currBlock;
333                             break;
334                         }
335                     }
336                 }
337             }
338         }
339               
340         parentBlock->markAllDescendantsWithFloatsForLayout();
341         parentBlock->markSiblingsWithFloatsForLayout();
342     }
343 }
344
345 void RenderBlock::updateBeforeAfterContent(PseudoId pseudoId)
346 {
347     // If this is an anonymous wrapper, then the parent applies its own pseudo-element style to it.
348     if (parent() && parent()->createsAnonymousWrapper())
349         return;
350     children()->updateBeforeAfterContent(this, pseudoId);
351 }
352
353 RenderBlock* RenderBlock::continuationBefore(RenderObject* beforeChild)
354 {
355     if (beforeChild && beforeChild->parent() == this)
356         return this;
357
358     RenderBlock* curr = toRenderBlock(continuation());
359     RenderBlock* nextToLast = this;
360     RenderBlock* last = this;
361     while (curr) {
362         if (beforeChild && beforeChild->parent() == curr) {
363             if (curr->firstChild() == beforeChild)
364                 return last;
365             return curr;
366         }
367
368         nextToLast = last;
369         last = curr;
370         curr = toRenderBlock(curr->continuation());
371     }
372
373     if (!beforeChild && !last->firstChild())
374         return nextToLast;
375     return last;
376 }
377
378 void RenderBlock::addChildToContinuation(RenderObject* newChild, RenderObject* beforeChild)
379 {
380     RenderBlock* flow = continuationBefore(beforeChild);
381     ASSERT(!beforeChild || beforeChild->parent()->isAnonymousColumnSpanBlock() || beforeChild->parent()->isRenderBlock());
382     RenderBoxModelObject* beforeChildParent = 0;
383     if (beforeChild)
384         beforeChildParent = toRenderBoxModelObject(beforeChild->parent());
385     else {
386         RenderBoxModelObject* cont = flow->continuation();
387         if (cont)
388             beforeChildParent = cont;
389         else
390             beforeChildParent = flow;
391     }
392
393     if (newChild->isFloatingOrPositioned()) {
394         beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
395         return;
396     }
397
398     // A continuation always consists of two potential candidates: a block or an anonymous
399     // column span box holding column span children.
400     bool childIsNormal = newChild->isInline() || !newChild->style()->columnSpan();
401     bool bcpIsNormal = beforeChildParent->isInline() || !beforeChildParent->style()->columnSpan();
402     bool flowIsNormal = flow->isInline() || !flow->style()->columnSpan();
403
404     if (flow == beforeChildParent) {
405         flow->addChildIgnoringContinuation(newChild, beforeChild);
406         return;
407     }
408     
409     // The goal here is to match up if we can, so that we can coalesce and create the
410     // minimal # of continuations needed for the inline.
411     if (childIsNormal == bcpIsNormal) {
412         beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
413         return;
414     }
415     if (flowIsNormal == childIsNormal) {
416         flow->addChildIgnoringContinuation(newChild, 0); // Just treat like an append.
417         return;
418     }
419     beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
420 }
421
422
423 void RenderBlock::addChildToAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)
424 {
425     ASSERT(!continuation()); // We don't yet support column spans that aren't immediate children of the multi-column block.
426         
427     // The goal is to locate a suitable box in which to place our child.
428     RenderBlock* beforeChildParent = 0;
429     if (beforeChild) {
430         RenderObject* curr = beforeChild;
431         while (curr && curr->parent() != this)
432             curr = curr->parent();
433         beforeChildParent = toRenderBlock(curr);
434         ASSERT(beforeChildParent);
435         ASSERT(beforeChildParent->isAnonymousColumnsBlock() || beforeChildParent->isAnonymousColumnSpanBlock());
436     } else
437         beforeChildParent = toRenderBlock(lastChild());
438
439     // If the new child is floating or positioned it can just go in that block.
440     if (newChild->isFloatingOrPositioned()) {
441         beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
442         return;
443     }
444
445     // See if the child can be placed in the box.
446     bool newChildHasColumnSpan = newChild->style()->columnSpan() && !newChild->isInline();
447     bool beforeChildParentHoldsColumnSpans = beforeChildParent->isAnonymousColumnSpanBlock();
448
449     if (newChildHasColumnSpan == beforeChildParentHoldsColumnSpans) {
450         beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
451         return;
452     }
453
454     if (!beforeChild) {
455         // Create a new block of the correct type.
456         RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();
457         children()->appendChildNode(this, newBox);
458         newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);
459         return;
460     }
461
462     RenderObject* immediateChild = beforeChild;
463     bool isPreviousBlockViable = true;
464     while (immediateChild->parent() != this) {
465         if (isPreviousBlockViable)
466             isPreviousBlockViable = !immediateChild->previousSibling();
467         immediateChild = immediateChild->parent();
468     }
469     if (isPreviousBlockViable && immediateChild->previousSibling()) {
470         toRenderBlock(immediateChild->previousSibling())->addChildIgnoringAnonymousColumnBlocks(newChild, 0); // Treat like an append.
471         return;
472     }
473         
474     // Split our anonymous blocks.
475     RenderObject* newBeforeChild = splitAnonymousBlocksAroundChild(beforeChild);
476     
477     // Create a new anonymous box of the appropriate type.
478     RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();
479     children()->insertChildNode(this, newBox, newBeforeChild);
480     newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);
481     return;
482 }
483
484 RenderBlock* RenderBlock::containingColumnsBlock(bool allowAnonymousColumnBlock)
485 {
486     RenderBlock* firstChildIgnoringAnonymousWrappers = 0;
487     for (RenderObject* curr = this; curr; curr = curr->parent()) {
488         if (!curr->isRenderBlock() || curr->isFloatingOrPositioned() || curr->isTableCell() || curr->isRoot() || curr->isRenderView() || curr->hasOverflowClip()
489             || curr->isInlineBlockOrInlineTable())
490             return 0;
491
492         // FIXME: Table manages its own table parts, most of which are RenderBoxes.
493         // Multi-column code cannot handle splitting the flow in table. Disabling it
494         // to prevent crashes.
495         if (curr->isTable())
496             return 0;
497         
498         RenderBlock* currBlock = toRenderBlock(curr);
499         if (!currBlock->createsAnonymousWrapper())
500             firstChildIgnoringAnonymousWrappers = currBlock;
501
502         if (currBlock->style()->specifiesColumns() && (allowAnonymousColumnBlock || !currBlock->isAnonymousColumnsBlock()))
503             return firstChildIgnoringAnonymousWrappers;
504             
505         if (currBlock->isAnonymousColumnSpanBlock())
506             return 0;
507     }
508     return 0;
509 }
510
511 RenderBlock* RenderBlock::clone() const
512 {
513     RenderBlock* cloneBlock;
514     if (isAnonymousBlock()) {
515         cloneBlock = createAnonymousBlock();
516         cloneBlock->setChildrenInline(childrenInline());
517     }
518     else {
519         RenderObject* cloneRenderer = node()->createRenderer(renderArena(), style());
520         cloneBlock = toRenderBlock(cloneRenderer);
521         cloneBlock->setStyle(style());
522
523         // This takes care of setting the right value of childrenInline in case
524         // generated content is added to cloneBlock and 'this' does not have
525         // generated content added yet.
526         cloneBlock->setChildrenInline(cloneBlock->firstChild() ? cloneBlock->firstChild()->isInline() : childrenInline());
527     }
528     return cloneBlock;
529 }
530
531 void RenderBlock::splitBlocks(RenderBlock* fromBlock, RenderBlock* toBlock,
532                               RenderBlock* middleBlock,
533                               RenderObject* beforeChild, RenderBoxModelObject* oldCont)
534 {
535     // Create a clone of this inline.
536     RenderBlock* cloneBlock = clone();
537     if (!isAnonymousBlock())
538         cloneBlock->setContinuation(oldCont);
539
540     if (!beforeChild && isAfterContent(lastChild()))
541         beforeChild = lastChild();
542
543     // If we are moving inline children from |this| to cloneBlock, then we need
544     // to clear our line box tree.
545     if (beforeChild && childrenInline())
546         deleteLineBoxTree();
547
548     // We have to remove the descendant child from our positioned objects list
549     // before we do the split and move some of the children to cloneBlock. Since
550     // we are doing layout anyway, it is easier to blow away the entire list, than
551     // traversing down the subtree looking for positioned childs and then remove them
552     // from our positioned objects list.
553     if (beforeChild)
554         removePositionedObjects(0);
555
556     // Now take all of the children from beforeChild to the end and remove
557     // them from |this| and place them in the clone.
558     moveChildrenTo(cloneBlock, beforeChild, 0, true);
559     
560     // Hook |clone| up as the continuation of the middle block.
561     if (!cloneBlock->isAnonymousBlock())
562         middleBlock->setContinuation(cloneBlock);
563
564     // We have been reparented and are now under the fromBlock.  We need
565     // to walk up our block parent chain until we hit the containing anonymous columns block.
566     // Once we hit the anonymous columns block we're done.
567     RenderBoxModelObject* curr = toRenderBoxModelObject(parent());
568     RenderBoxModelObject* currChild = this;
569     
570     while (curr && curr != fromBlock) {
571         ASSERT(curr->isRenderBlock());
572         
573         RenderBlock* blockCurr = toRenderBlock(curr);
574         
575         // Create a new clone.
576         RenderBlock* cloneChild = cloneBlock;
577         cloneBlock = blockCurr->clone();
578
579         // Insert our child clone as the first child.
580         cloneBlock->addChildIgnoringContinuation(cloneChild, 0);
581
582         // Hook the clone up as a continuation of |curr|.  Note we do encounter
583         // anonymous blocks possibly as we walk up the block chain.  When we split an
584         // anonymous block, there's no need to do any continuation hookup, since we haven't
585         // actually split a real element.
586         if (!blockCurr->isAnonymousBlock()) {
587             oldCont = blockCurr->continuation();
588             blockCurr->setContinuation(cloneBlock);
589             cloneBlock->setContinuation(oldCont);
590         }
591
592         // Someone may have indirectly caused a <q> to split.  When this happens, the :after content
593         // has to move into the inline continuation.  Call updateBeforeAfterContent to ensure that the inline's :after
594         // content gets properly destroyed.
595         if (document()->usesBeforeAfterRules())
596             blockCurr->children()->updateBeforeAfterContent(blockCurr, AFTER);
597
598         // Now we need to take all of the children starting from the first child
599         // *after* currChild and append them all to the clone.
600         blockCurr->moveChildrenTo(cloneBlock, currChild->nextSibling(), 0, true);
601
602         // Keep walking up the chain.
603         currChild = curr;
604         curr = toRenderBoxModelObject(curr->parent());
605     }
606
607     // Now we are at the columns block level. We need to put the clone into the toBlock.
608     toBlock->children()->appendChildNode(toBlock, cloneBlock);
609
610     // Now take all the children after currChild and remove them from the fromBlock
611     // and put them in the toBlock.
612     fromBlock->moveChildrenTo(toBlock, currChild->nextSibling(), 0, true);
613 }
614
615 void RenderBlock::splitFlow(RenderObject* beforeChild, RenderBlock* newBlockBox,
616                             RenderObject* newChild, RenderBoxModelObject* oldCont)
617 {
618     RenderBlock* pre = 0;
619     RenderBlock* block = containingColumnsBlock();
620     
621     // Delete our line boxes before we do the inline split into continuations.
622     block->deleteLineBoxTree();
623     
624     bool madeNewBeforeBlock = false;
625     if (block->isAnonymousColumnsBlock()) {
626         // We can reuse this block and make it the preBlock of the next continuation.
627         pre = block;
628         pre->removePositionedObjects(0);
629         block = toRenderBlock(block->parent());
630     } else {
631         // No anonymous block available for use.  Make one.
632         pre = block->createAnonymousColumnsBlock();
633         pre->setChildrenInline(false);
634         madeNewBeforeBlock = true;
635     }
636
637     RenderBlock* post = block->createAnonymousColumnsBlock();
638     post->setChildrenInline(false);
639
640     RenderObject* boxFirst = madeNewBeforeBlock ? block->firstChild() : pre->nextSibling();
641     if (madeNewBeforeBlock)
642         block->children()->insertChildNode(block, pre, boxFirst);
643     block->children()->insertChildNode(block, newBlockBox, boxFirst);
644     block->children()->insertChildNode(block, post, boxFirst);
645     block->setChildrenInline(false);
646     
647     if (madeNewBeforeBlock)
648         block->moveChildrenTo(pre, boxFirst, 0, true);
649
650     splitBlocks(pre, post, newBlockBox, beforeChild, oldCont);
651
652     // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
653     // time in makeChildrenNonInline by just setting this explicitly up front.
654     newBlockBox->setChildrenInline(false);
655
656     // We delayed adding the newChild until now so that the |newBlockBox| would be fully
657     // connected, thus allowing newChild access to a renderArena should it need
658     // to wrap itself in additional boxes (e.g., table construction).
659     newBlockBox->addChild(newChild);
660
661     // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
662     // get deleted properly.  Because objects moves from the pre block into the post block, we want to
663     // make new line boxes instead of leaving the old line boxes around.
664     pre->setNeedsLayoutAndPrefWidthsRecalc();
665     block->setNeedsLayoutAndPrefWidthsRecalc();
666     post->setNeedsLayoutAndPrefWidthsRecalc();
667 }
668
669 RenderObject* RenderBlock::splitAnonymousBlocksAroundChild(RenderObject* beforeChild)
670 {
671     if (beforeChild->isTablePart())
672         beforeChild = splitTablePartsAroundChild(beforeChild);
673
674     while (beforeChild->parent() != this) {
675         RenderBlock* blockToSplit = toRenderBlock(beforeChild->parent());
676         if (blockToSplit->firstChild() != beforeChild) {
677             // We have to split the parentBlock into two blocks.
678             RenderBlock* post = createAnonymousBlockWithSameTypeAs(blockToSplit);
679             post->setChildrenInline(blockToSplit->childrenInline());
680             RenderBlock* parentBlock = toRenderBlock(blockToSplit->parent());
681             parentBlock->children()->insertChildNode(parentBlock, post, blockToSplit->nextSibling());
682             blockToSplit->moveChildrenTo(post, beforeChild, 0, blockToSplit->hasLayer());
683             post->setNeedsLayoutAndPrefWidthsRecalc();
684             blockToSplit->setNeedsLayoutAndPrefWidthsRecalc();
685             beforeChild = post;
686         } else
687             beforeChild = blockToSplit;
688     }
689     return beforeChild;
690 }
691
692 static void markTableForSectionAndCellRecalculation(RenderObject* child)
693 {
694     RenderObject* curr = child;
695     while (!curr->isTable()) {
696         if (curr->isTableSection())
697             toRenderTableSection(curr)->setNeedsCellRecalc();
698         curr = curr->parent();
699     }
700
701     RenderTable* table = toRenderTable(curr);
702     table->setNeedsSectionRecalc();
703     table->setNeedsLayoutAndPrefWidthsRecalc();
704 }
705
706 static void moveAllTableChildrenTo(RenderObject* fromTablePart, RenderTable* toTable, RenderObject* startChild)
707 {
708     for (RenderObject* curr = startChild; curr;) {
709         // Need to store next sibling as we won't have access to it
710         // after we are removed from table.
711         RenderObject* next = curr->nextSibling();
712         fromTablePart->removeChild(curr);
713         toTable->addChild(curr);
714         if (curr->isTableSection())
715             toRenderTableSection(curr)->setNeedsCellRecalc();
716         curr->setNeedsLayoutAndPrefWidthsRecalc();
717         curr = next; 
718     }
719
720     // This marks fromTable for section and cell recalculation.
721     markTableForSectionAndCellRecalculation(fromTablePart);
722
723     // startChild is now part of toTable. This marks toTable for section and cell recalculation.
724     markTableForSectionAndCellRecalculation(startChild);
725 }
726
727 RenderObject* RenderBlock::splitTablePartsAroundChild(RenderObject* beforeChild)
728 {
729     ASSERT(beforeChild->isTablePart());
730
731     while (beforeChild->parent() != this) {
732         RenderObject* tablePartToSplit = beforeChild->parent();
733         if (!tablePartToSplit->isTablePart() && !tablePartToSplit->isTable())
734             break;
735         if (tablePartToSplit->firstChild() != beforeChild) {
736             // Get our table container.
737             RenderObject* curr = tablePartToSplit;
738             while (!curr->isTable())
739                 curr = curr->parent();
740             RenderTable* table = toRenderTable(curr);
741
742             // Create an anonymous table container next to our table container.
743             RenderBlock* parentBlock = toRenderBlock(table->parent());
744             RenderTable* postTable = parentBlock->createAnonymousTable();
745             parentBlock->children()->insertChildNode(parentBlock, postTable, table->nextSibling());
746             
747             // Move all the children from beforeChild to the newly created anonymous table container.
748             moveAllTableChildrenTo(tablePartToSplit, postTable, beforeChild);
749
750             beforeChild = postTable;
751         } else
752             beforeChild = tablePartToSplit;
753     }
754     return beforeChild;
755 }
756
757 void RenderBlock::makeChildrenAnonymousColumnBlocks(RenderObject* beforeChild, RenderBlock* newBlockBox, RenderObject* newChild)
758 {
759     RenderBlock* pre = 0;
760     RenderBlock* post = 0;
761     RenderBlock* block = this; // Eventually block will not just be |this|, but will also be a block nested inside |this|.  Assign to a variable
762                                // so that we don't have to patch all of the rest of the code later on.
763     
764     // Delete the block's line boxes before we do the split.
765     block->deleteLineBoxTree();
766
767     if (beforeChild && beforeChild->parent() != this)
768         beforeChild = splitAnonymousBlocksAroundChild(beforeChild);
769
770     if (beforeChild != firstChild()) {
771         pre = block->createAnonymousColumnsBlock();
772         pre->setChildrenInline(block->childrenInline());
773     }
774
775     if (beforeChild) {
776         post = block->createAnonymousColumnsBlock();
777         post->setChildrenInline(block->childrenInline());
778     }
779
780     RenderObject* boxFirst = block->firstChild();
781     if (pre)
782         block->children()->insertChildNode(block, pre, boxFirst);
783     block->children()->insertChildNode(block, newBlockBox, boxFirst);
784     if (post)
785         block->children()->insertChildNode(block, post, boxFirst);
786     block->setChildrenInline(false);
787     
788     // The pre/post blocks always have layers, so we know to always do a full insert/remove (so we pass true as the last argument).
789     block->moveChildrenTo(pre, boxFirst, beforeChild, true);
790     block->moveChildrenTo(post, beforeChild, 0, true);
791
792     // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
793     // time in makeChildrenNonInline by just setting this explicitly up front.
794     newBlockBox->setChildrenInline(false);
795
796     // We delayed adding the newChild until now so that the |newBlockBox| would be fully
797     // connected, thus allowing newChild access to a renderArena should it need
798     // to wrap itself in additional boxes (e.g., table construction).
799     newBlockBox->addChild(newChild);
800
801     // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
802     // get deleted properly.  Because objects moved from the pre block into the post block, we want to
803     // make new line boxes instead of leaving the old line boxes around.
804     if (pre)
805         pre->setNeedsLayoutAndPrefWidthsRecalc();
806     block->setNeedsLayoutAndPrefWidthsRecalc();
807     if (post)
808         post->setNeedsLayoutAndPrefWidthsRecalc();
809 }
810
811 RenderBlock* RenderBlock::columnsBlockForSpanningElement(RenderObject* newChild)
812 {
813     // FIXME: This function is the gateway for the addition of column-span support.  It will
814     // be added to in three stages:
815     // (1) Immediate children of a multi-column block can span.
816     // (2) Nested block-level children with only block-level ancestors between them and the multi-column block can span.
817     // (3) Nested children with block or inline ancestors between them and the multi-column block can span (this is when we
818     // cross the streams and have to cope with both types of continuations mixed together).
819     // This function currently supports (1) and (2).
820     RenderBlock* columnsBlockAncestor = 0;
821     if (!newChild->isText() && newChild->style()->columnSpan() && !newChild->isBeforeOrAfterContent()
822         && !newChild->isFloatingOrPositioned() && !newChild->isInline() && !isAnonymousColumnSpanBlock()) {
823         columnsBlockAncestor = containingColumnsBlock(false);
824         if (columnsBlockAncestor) {
825             // Make sure that none of the parent ancestors have a continuation.
826             // If yes, we do not want split the block into continuations.
827             RenderObject* curr = this;
828             while (curr && curr != columnsBlockAncestor) {
829                 if (curr->isRenderBlock() && toRenderBlock(curr)->continuation()) {
830                     columnsBlockAncestor = 0;
831                     break;
832                 }
833                 curr = curr->parent();
834             }
835         }
836     }
837     return columnsBlockAncestor;
838 }
839
840 void RenderBlock::addChildIgnoringAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)
841 {
842     // Make sure we don't append things after :after-generated content if we have it.
843     if (!beforeChild)
844         beforeChild = afterPseudoElementRenderer();
845
846     if (beforeChild && beforeChild->parent() != this) {
847         RenderObject* beforeChildContainer = beforeChild->parent();
848         while (beforeChildContainer->parent() != this)
849             beforeChildContainer = beforeChildContainer->parent();
850         ASSERT(beforeChildContainer);
851
852         if (beforeChildContainer->isAnonymous()) {
853             // If the requested beforeChild is not one of our children, then this is because
854             // there is an anonymous container within this object that contains the beforeChild.
855             RenderObject* beforeChildAnonymousContainer = beforeChildContainer;
856             if (beforeChildAnonymousContainer->isAnonymousBlock()) {
857                 // Insert the child into the anonymous block box instead of here.
858                 if (newChild->isInline() || beforeChild->parent()->firstChild() != beforeChild)
859                     beforeChild->parent()->addChild(newChild, beforeChild);
860                 else
861                     addChild(newChild, beforeChild->parent());
862                 return;
863             }
864
865             ASSERT(beforeChildAnonymousContainer->isTable());
866             if (newChild->isTablePart()) {
867                 // Insert into the anonymous table.
868                 beforeChildAnonymousContainer->addChild(newChild, beforeChild);
869                 return;
870             }
871
872             beforeChild = splitTablePartsAroundChild(beforeChild);
873
874             ASSERT(beforeChild->parent() == this);
875             if (beforeChild->parent() != this) {
876                 // We should never reach here. If we do, we need to use the
877                 // safe fallback to use the topmost beforeChild container.
878                 beforeChild = beforeChildContainer;
879             }
880         } else {
881             // We will reach here when beforeChild is a run-in element.
882             // If run-in element precedes a block-level element, it becomes the
883             // the first inline child of that block level element. The insertion
884             // point will be before that block-level element.
885             ASSERT(beforeChild->isRunIn());
886             beforeChild = beforeChildContainer;
887         }
888     }
889
890     // Check for a spanning element in columns.
891     RenderBlock* columnsBlockAncestor = columnsBlockForSpanningElement(newChild);
892     if (columnsBlockAncestor) {
893         // We are placing a column-span element inside a block. 
894         RenderBlock* newBox = createAnonymousColumnSpanBlock();
895         
896         if (columnsBlockAncestor != this) {
897             // We are nested inside a multi-column element and are being split by the span.  We have to break up
898             // our block into continuations.
899             RenderBoxModelObject* oldContinuation = continuation();
900
901             // When we split an anonymous block, there's no need to do any continuation hookup,
902             // since we haven't actually split a real element.
903             if (!isAnonymousBlock())
904                 setContinuation(newBox);
905
906             // Someone may have put a <p> inside a <q>, causing a split.  When this happens, the :after content
907             // has to move into the inline continuation.  Call updateBeforeAfterContent to ensure that our :after
908             // content gets properly destroyed.
909             bool isLastChild = (beforeChild == lastChild());
910             if (document()->usesBeforeAfterRules())
911                 children()->updateBeforeAfterContent(this, AFTER);
912             if (isLastChild && beforeChild != lastChild())
913                 beforeChild = 0; // We destroyed the last child, so now we need to update our insertion
914                                  // point to be 0.  It's just a straight append now.
915
916             splitFlow(beforeChild, newBox, newChild, oldContinuation);
917             return;
918         }
919
920         // We have to perform a split of this block's children.  This involves creating an anonymous block box to hold
921         // the column-spanning |newChild|.  We take all of the children from before |newChild| and put them into
922         // one anonymous columns block, and all of the children after |newChild| go into another anonymous block.
923         makeChildrenAnonymousColumnBlocks(beforeChild, newBox, newChild);
924         return;
925     }
926
927     bool madeBoxesNonInline = false;
928
929     // A block has to either have all of its children inline, or all of its children as blocks.
930     // So, if our children are currently inline and a block child has to be inserted, we move all our
931     // inline children into anonymous block boxes.
932     if (childrenInline() && !newChild->isInline() && !newChild->isFloatingOrPositioned()) {
933         // This is a block with inline content. Wrap the inline content in anonymous blocks.
934         makeChildrenNonInline(beforeChild);
935         madeBoxesNonInline = true;
936
937         if (beforeChild && beforeChild->parent() != this) {
938             beforeChild = beforeChild->parent();
939             ASSERT(beforeChild->isAnonymousBlock());
940             ASSERT(beforeChild->parent() == this);
941         }
942     } else if (!childrenInline() && (newChild->isFloatingOrPositioned() || newChild->isInline())) {
943         // If we're inserting an inline child but all of our children are blocks, then we have to make sure
944         // it is put into an anomyous block box. We try to use an existing anonymous box if possible, otherwise
945         // a new one is created and inserted into our list of children in the appropriate position.
946         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : lastChild();
947
948         if (afterChild && afterChild->isAnonymousBlock()) {
949             afterChild->addChild(newChild);
950             return;
951         }
952
953         if (newChild->isInline()) {
954             // No suitable existing anonymous box - create a new one.
955             RenderBlock* newBox = createAnonymousBlock();
956             RenderBox::addChild(newBox, beforeChild);
957             newBox->addChild(newChild);
958             return;
959         }
960     }
961
962     RenderBox::addChild(newChild, beforeChild);
963
964     if (madeBoxesNonInline && parent() && isAnonymousBlock() && parent()->isRenderBlock())
965         toRenderBlock(parent())->removeLeftoverAnonymousBlock(this);
966     // this object may be dead here
967 }
968
969 void RenderBlock::addChild(RenderObject* newChild, RenderObject* beforeChild)
970 {
971     if (continuation() && !isAnonymousBlock())
972         addChildToContinuation(newChild, beforeChild);
973     else
974         addChildIgnoringContinuation(newChild, beforeChild);
975 }
976
977 void RenderBlock::addChildIgnoringContinuation(RenderObject* newChild, RenderObject* beforeChild)
978 {
979     if (!isAnonymousBlock() && firstChild() && (firstChild()->isAnonymousColumnsBlock() || firstChild()->isAnonymousColumnSpanBlock()))
980         addChildToAnonymousColumnBlocks(newChild, beforeChild);
981     else
982         addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
983 }
984
985 static void getInlineRun(RenderObject* start, RenderObject* boundary,
986                          RenderObject*& inlineRunStart,
987                          RenderObject*& inlineRunEnd)
988 {
989     // Beginning at |start| we find the largest contiguous run of inlines that
990     // we can.  We denote the run with start and end points, |inlineRunStart|
991     // and |inlineRunEnd|.  Note that these two values may be the same if
992     // we encounter only one inline.
993     //
994     // We skip any non-inlines we encounter as long as we haven't found any
995     // inlines yet.
996     //
997     // |boundary| indicates a non-inclusive boundary point.  Regardless of whether |boundary|
998     // is inline or not, we will not include it in a run with inlines before it.  It's as though we encountered
999     // a non-inline.
1000     
1001     // Start by skipping as many non-inlines as we can.
1002     RenderObject * curr = start;
1003     bool sawInline;
1004     do {
1005         while (curr && !(curr->isInline() || curr->isFloatingOrPositioned()))
1006             curr = curr->nextSibling();
1007         
1008         inlineRunStart = inlineRunEnd = curr;
1009         
1010         if (!curr)
1011             return; // No more inline children to be found.
1012         
1013         sawInline = curr->isInline();
1014         
1015         curr = curr->nextSibling();
1016         while (curr && (curr->isInline() || curr->isFloatingOrPositioned()) && (curr != boundary)) {
1017             inlineRunEnd = curr;
1018             if (curr->isInline())
1019                 sawInline = true;
1020             curr = curr->nextSibling();
1021         }
1022     } while (!sawInline);
1023 }
1024
1025 void RenderBlock::deleteLineBoxTree()
1026 {
1027     if (containsFloats()) {
1028         // Clear references to originating lines, since the lines are being deleted
1029         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1030         FloatingObjectSetIterator end = floatingObjectSet.end();
1031         for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
1032             ASSERT(!((*it)->m_originatingLine) || (*it)->m_originatingLine->renderer() == this);
1033             (*it)->m_originatingLine = 0;
1034         }
1035     }
1036     m_lineBoxes.deleteLineBoxTree(renderArena());
1037 }
1038
1039 RootInlineBox* RenderBlock::createRootInlineBox() 
1040 {
1041     return new (renderArena()) RootInlineBox(this);
1042 }
1043
1044 RootInlineBox* RenderBlock::createAndAppendRootInlineBox()
1045 {
1046     RootInlineBox* rootBox = createRootInlineBox();
1047     m_lineBoxes.appendLineBox(rootBox);
1048     return rootBox;
1049 }
1050
1051 void RenderBlock::moveChildTo(RenderBlock* toBlock, RenderObject* child, RenderObject* beforeChild, bool fullRemoveInsert)
1052 {
1053     ASSERT(this == child->parent());
1054     ASSERT(!beforeChild || toBlock == beforeChild->parent());
1055     if (fullRemoveInsert) {
1056         // Takes care of adding the new child correctly if toBlock and fromBlock
1057         // have different kind of children (block vs inline).
1058         toBlock->addChildIgnoringContinuation(children()->removeChildNode(this, child), beforeChild);
1059     } else
1060         toBlock->children()->insertChildNode(toBlock, children()->removeChildNode(this, child, false), beforeChild, false);
1061 }
1062
1063 void RenderBlock::moveChildrenTo(RenderBlock* toBlock, RenderObject* startChild, RenderObject* endChild, RenderObject* beforeChild, bool fullRemoveInsert)
1064 {
1065     ASSERT(!beforeChild || toBlock == beforeChild->parent());
1066
1067     for (RenderObject* child = startChild; child && child != endChild; ) {
1068         // Save our next sibling as moveChildTo will clear it.
1069         RenderObject* nextSibling = child->nextSibling();
1070         moveChildTo(toBlock, child, beforeChild, fullRemoveInsert);
1071         child = nextSibling;
1072     }
1073 }
1074
1075 void RenderBlock::makeChildrenNonInline(RenderObject *insertionPoint)
1076 {    
1077     // makeChildrenNonInline takes a block whose children are *all* inline and it
1078     // makes sure that inline children are coalesced under anonymous
1079     // blocks.  If |insertionPoint| is defined, then it represents the insertion point for
1080     // the new block child that is causing us to have to wrap all the inlines.  This
1081     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
1082     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
1083     // splitting them.
1084     ASSERT(isInlineBlockOrInlineTable() || !isInline());
1085     ASSERT(!insertionPoint || insertionPoint->parent() == this);
1086
1087     setChildrenInline(false);
1088
1089     RenderObject *child = firstChild();
1090     if (!child)
1091         return;
1092
1093     deleteLineBoxTree();
1094
1095     while (child) {
1096         RenderObject *inlineRunStart, *inlineRunEnd;
1097         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
1098
1099         if (!inlineRunStart)
1100             break;
1101
1102         child = inlineRunEnd->nextSibling();
1103
1104         RenderBlock* block = createAnonymousBlock();
1105         children()->insertChildNode(this, block, inlineRunStart);
1106         moveChildrenTo(block, inlineRunStart, child);
1107     }
1108
1109 #ifndef NDEBUG
1110     for (RenderObject *c = firstChild(); c; c = c->nextSibling())
1111         ASSERT(!c->isInline());
1112 #endif
1113
1114     repaint();
1115 }
1116
1117 void RenderBlock::removeLeftoverAnonymousBlock(RenderBlock* child)
1118 {
1119     ASSERT(child->isAnonymousBlock());
1120     ASSERT(!child->childrenInline());
1121     
1122     if (child->continuation() || (child->firstChild() && (child->isAnonymousColumnSpanBlock() || child->isAnonymousColumnsBlock())))
1123         return;
1124     
1125     RenderObject* firstAnChild = child->m_children.firstChild();
1126     RenderObject* lastAnChild = child->m_children.lastChild();
1127     if (firstAnChild) {
1128         RenderObject* o = firstAnChild;
1129         while (o) {
1130             o->setParent(this);
1131             o = o->nextSibling();
1132         }
1133         firstAnChild->setPreviousSibling(child->previousSibling());
1134         lastAnChild->setNextSibling(child->nextSibling());
1135         if (child->previousSibling())
1136             child->previousSibling()->setNextSibling(firstAnChild);
1137         if (child->nextSibling())
1138             child->nextSibling()->setPreviousSibling(lastAnChild);
1139             
1140         if (child == m_children.firstChild())
1141             m_children.setFirstChild(firstAnChild);
1142         if (child == m_children.lastChild())
1143             m_children.setLastChild(lastAnChild);
1144     } else {
1145         if (child == m_children.firstChild())
1146             m_children.setFirstChild(child->nextSibling());
1147         if (child == m_children.lastChild())
1148             m_children.setLastChild(child->previousSibling());
1149
1150         if (child->previousSibling())
1151             child->previousSibling()->setNextSibling(child->nextSibling());
1152         if (child->nextSibling())
1153             child->nextSibling()->setPreviousSibling(child->previousSibling());
1154     }
1155     child->setParent(0);
1156     child->setPreviousSibling(0);
1157     child->setNextSibling(0);
1158     
1159     child->children()->setFirstChild(0);
1160     child->m_next = 0;
1161
1162     child->destroy();
1163 }
1164
1165 static bool canMergeContiguousAnonymousBlocks(RenderObject* oldChild, RenderObject* prev, RenderObject* next)
1166 {
1167     if (oldChild->documentBeingDestroyed() || oldChild->isInline() || oldChild->virtualContinuation())
1168         return false;
1169
1170     if ((prev && (!prev->isAnonymousBlock() || toRenderBlock(prev)->continuation() || toRenderBlock(prev)->beingDestroyed()))
1171         || (next && (!next->isAnonymousBlock() || toRenderBlock(next)->continuation() || toRenderBlock(next)->beingDestroyed())))
1172         return false;
1173
1174     // FIXME: This check isn't required when inline run-ins can't be split into continuations.
1175     if (prev && prev->firstChild() && prev->firstChild()->isInline() && prev->firstChild()->isRunIn())
1176         return false;
1177
1178     if ((prev && (prev->isRubyRun() || prev->isRubyBase()))
1179         || (next && (next->isRubyRun() || next->isRubyBase())))
1180         return false;
1181
1182     if (!prev || !next)
1183         return true;
1184
1185     // Make sure the types of the anonymous blocks match up.
1186     return prev->isAnonymousColumnsBlock() == next->isAnonymousColumnsBlock()
1187            && prev->isAnonymousColumnSpanBlock() == next->isAnonymousColumnSpanBlock();
1188 }
1189
1190 void RenderBlock::collapseAnonymousBoxChild(RenderBlock* parent, RenderObject* child)
1191 {
1192     parent->setNeedsLayoutAndPrefWidthsRecalc();
1193     parent->setChildrenInline(child->childrenInline());
1194     RenderObject* nextSibling = child->nextSibling();
1195
1196     RenderFlowThread* childFlowThread = child->enclosingRenderFlowThread();
1197     RenderBlock* anonBlock = toRenderBlock(parent->children()->removeChildNode(parent, child, child->hasLayer()));
1198     anonBlock->moveAllChildrenTo(parent, nextSibling, child->hasLayer());
1199     // Delete the now-empty block's lines and nuke it.
1200     if (!parent->documentBeingDestroyed())
1201         anonBlock->deleteLineBoxTree();
1202     if (childFlowThread && !parent->documentBeingDestroyed())
1203         childFlowThread->removeFlowChildInfo(anonBlock);
1204     anonBlock->destroy();
1205 }
1206
1207 void RenderBlock::removeChild(RenderObject* oldChild)
1208 {
1209     // If this child is a block, and if our previous and next siblings are
1210     // both anonymous blocks with inline content, then we can go ahead and
1211     // fold the inline content back together.
1212     RenderObject* prev = oldChild->previousSibling();
1213     RenderObject* next = oldChild->nextSibling();
1214     bool canMergeAnonymousBlocks = canMergeContiguousAnonymousBlocks(oldChild, prev, next);
1215     if (canMergeAnonymousBlocks && prev && next) {
1216         prev->setNeedsLayoutAndPrefWidthsRecalc();
1217         RenderBlock* nextBlock = toRenderBlock(next);
1218         RenderBlock* prevBlock = toRenderBlock(prev);
1219        
1220         if (prev->childrenInline() != next->childrenInline()) {
1221             RenderBlock* inlineChildrenBlock = prev->childrenInline() ? prevBlock : nextBlock;
1222             RenderBlock* blockChildrenBlock = prev->childrenInline() ? nextBlock : prevBlock;
1223             
1224             // Place the inline children block inside of the block children block instead of deleting it.
1225             // In order to reuse it, we have to reset it to just be a generic anonymous block.  Make sure
1226             // to clear out inherited column properties by just making a new style, and to also clear the
1227             // column span flag if it is set.
1228             ASSERT(!inlineChildrenBlock->continuation());
1229             RefPtr<RenderStyle> newStyle = RenderStyle::createAnonymousStyle(style());
1230             children()->removeChildNode(this, inlineChildrenBlock, inlineChildrenBlock->hasLayer());
1231             inlineChildrenBlock->setStyle(newStyle);
1232             
1233             // Now just put the inlineChildrenBlock inside the blockChildrenBlock.
1234             blockChildrenBlock->children()->insertChildNode(blockChildrenBlock, inlineChildrenBlock, prev == inlineChildrenBlock ? blockChildrenBlock->firstChild() : 0,
1235                                                             inlineChildrenBlock->hasLayer() || blockChildrenBlock->hasLayer());
1236             next->setNeedsLayoutAndPrefWidthsRecalc();
1237             
1238             // inlineChildrenBlock got reparented to blockChildrenBlock, so it is no longer a child
1239             // of "this". we null out prev or next so that is not used later in the function.
1240             if (inlineChildrenBlock == prevBlock)
1241                 prev = 0;
1242             else
1243                 next = 0;
1244         } else {
1245             // Take all the children out of the |next| block and put them in
1246             // the |prev| block.
1247             nextBlock->moveAllChildrenTo(prevBlock, nextBlock->hasLayer() || prevBlock->hasLayer());        
1248             
1249             // Delete the now-empty block's lines and nuke it.
1250             nextBlock->deleteLineBoxTree();
1251             nextBlock->destroy();
1252             next = 0;
1253         }
1254     }
1255
1256     RenderBox::removeChild(oldChild);
1257
1258     RenderObject* child = prev ? prev : next;
1259     if (canMergeAnonymousBlocks && child && !child->previousSibling() && !child->nextSibling() && !isFlexibleBoxIncludingDeprecated()) {
1260         // The removal has knocked us down to containing only a single anonymous
1261         // box.  We can go ahead and pull the content right back up into our
1262         // box.
1263         collapseAnonymousBoxChild(this, child);
1264     } else if (((prev && prev->isAnonymousBlock()) || (next && next->isAnonymousBlock())) && !isFlexibleBoxIncludingDeprecated()) {
1265         // It's possible that the removal has knocked us down to a single anonymous
1266         // block with pseudo-style element siblings (e.g. first-letter). If these
1267         // are floating, then we need to pull the content up also.
1268         RenderBlock* anonBlock = toRenderBlock((prev && prev->isAnonymousBlock()) ? prev : next);
1269         if ((anonBlock->previousSibling() || anonBlock->nextSibling())
1270             && (!anonBlock->previousSibling() || (anonBlock->previousSibling()->style()->styleType() != NOPSEUDO && anonBlock->previousSibling()->isFloating() && !anonBlock->previousSibling()->previousSibling()))
1271             && (!anonBlock->nextSibling() || (anonBlock->nextSibling()->style()->styleType() != NOPSEUDO && anonBlock->nextSibling()->isFloating() && !anonBlock->nextSibling()->nextSibling()))) {
1272             collapseAnonymousBoxChild(this, anonBlock);
1273         }
1274     }
1275
1276     if (!firstChild() && !documentBeingDestroyed()) {
1277         // If this was our last child be sure to clear out our line boxes.
1278         if (childrenInline())
1279             deleteLineBoxTree();
1280     }
1281 }
1282
1283 bool RenderBlock::isSelfCollapsingBlock() const
1284 {
1285     // We are not self-collapsing if we
1286     // (a) have a non-zero height according to layout (an optimization to avoid wasting time)
1287     // (b) are a table,
1288     // (c) have border/padding,
1289     // (d) have a min-height
1290     // (e) have specified that one of our margins can't collapse using a CSS extension
1291     if (logicalHeight() > 0
1292         || isTable() || borderAndPaddingLogicalHeight()
1293         || style()->logicalMinHeight().isPositive()
1294         || style()->marginBeforeCollapse() == MSEPARATE || style()->marginAfterCollapse() == MSEPARATE)
1295         return false;
1296
1297     Length logicalHeightLength = style()->logicalHeight();
1298     bool hasAutoHeight = logicalHeightLength.isAuto();
1299     if (logicalHeightLength.isPercent() && !document()->inQuirksMode()) {
1300         hasAutoHeight = true;
1301         for (RenderBlock* cb = containingBlock(); !cb->isRenderView(); cb = cb->containingBlock()) {
1302             if (cb->style()->logicalHeight().isFixed() || cb->isTableCell())
1303                 hasAutoHeight = false;
1304         }
1305     }
1306
1307     // If the height is 0 or auto, then whether or not we are a self-collapsing block depends
1308     // on whether we have content that is all self-collapsing or not.
1309     if (hasAutoHeight || ((logicalHeightLength.isFixed() || logicalHeightLength.isPercent()) && logicalHeightLength.isZero())) {
1310         // If the block has inline children, see if we generated any line boxes.  If we have any
1311         // line boxes, then we can't be self-collapsing, since we have content.
1312         if (childrenInline())
1313             return !firstLineBox();
1314         
1315         // Whether or not we collapse is dependent on whether all our normal flow children
1316         // are also self-collapsing.
1317         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1318             if (child->isFloatingOrPositioned())
1319                 continue;
1320             if (!child->isSelfCollapsingBlock())
1321                 return false;
1322         }
1323         return true;
1324     }
1325     return false;
1326 }
1327
1328 void RenderBlock::startDelayUpdateScrollInfo()
1329 {
1330     if (gDelayUpdateScrollInfo == 0) {
1331         ASSERT(!gDelayedUpdateScrollInfoSet);
1332         gDelayedUpdateScrollInfoSet = new DelayedUpdateScrollInfoSet;
1333     }
1334     ASSERT(gDelayedUpdateScrollInfoSet);
1335     ++gDelayUpdateScrollInfo;
1336 }
1337
1338 void RenderBlock::finishDelayUpdateScrollInfo()
1339 {
1340     --gDelayUpdateScrollInfo;
1341     ASSERT(gDelayUpdateScrollInfo >= 0);
1342     if (gDelayUpdateScrollInfo == 0) {
1343         ASSERT(gDelayedUpdateScrollInfoSet);
1344
1345         OwnPtr<DelayedUpdateScrollInfoSet> infoSet(adoptPtr(gDelayedUpdateScrollInfoSet));
1346         gDelayedUpdateScrollInfoSet = 0;
1347
1348         for (DelayedUpdateScrollInfoSet::iterator it = infoSet->begin(); it != infoSet->end(); ++it) {
1349             RenderBlock* block = *it;
1350             if (block->hasOverflowClip()) {
1351                 block->layer()->updateScrollInfoAfterLayout();
1352             }
1353         }
1354     }
1355 }
1356
1357 void RenderBlock::updateScrollInfoAfterLayout()
1358 {
1359     if (hasOverflowClip()) {
1360         if (gDelayUpdateScrollInfo)
1361             gDelayedUpdateScrollInfoSet->add(this);
1362         else
1363             layer()->updateScrollInfoAfterLayout();
1364     }
1365 }
1366
1367 void RenderBlock::layout()
1368 {
1369     OverflowEventDispatcher dispatcher(this);
1370
1371     // Update our first letter info now.
1372     updateFirstLetter();
1373
1374     // Table cells call layoutBlock directly, so don't add any logic here.  Put code into
1375     // layoutBlock().
1376     layoutBlock(false);
1377     
1378     // It's safe to check for control clip here, since controls can never be table cells.
1379     // If we have a lightweight clip, there can never be any overflow from children.
1380     if (hasControlClip() && m_overflow)
1381         clearLayoutOverflow();
1382 }
1383
1384 void RenderBlock::computeInitialRegionRangeForBlock()
1385 {
1386     if (inRenderFlowThread()) {
1387         // Set our start and end regions. No regions above or below us will be considered by our children. They are
1388         // effectively clamped to our region range.
1389         LayoutUnit oldHeight =  logicalHeight();
1390         LayoutUnit oldLogicalTop = logicalTop();
1391         setLogicalHeight(numeric_limits<LayoutUnit>::max() / 2);
1392         computeLogicalHeight();
1393         enclosingRenderFlowThread()->setRegionRangeForBox(this, offsetFromLogicalTopOfFirstPage());
1394         setLogicalHeight(oldHeight);
1395         setLogicalTop(oldLogicalTop);
1396     }
1397 }
1398
1399 void RenderBlock::computeRegionRangeForBlock()
1400 {
1401     if (inRenderFlowThread())
1402         enclosingRenderFlowThread()->setRegionRangeForBox(this, offsetFromLogicalTopOfFirstPage());
1403 }
1404
1405 void RenderBlock::layoutBlock(bool relayoutChildren, LayoutUnit pageLogicalHeight, BlockLayoutPass layoutPass)
1406 {
1407     ASSERT(needsLayout());
1408
1409     if (isInline() && !isInlineBlockOrInlineTable()) // Inline <form>s inside various table elements can
1410         return;                                      // cause us to come in here.  Just bail.
1411
1412     if (!relayoutChildren && simplifiedLayout())
1413         return;
1414
1415     LayoutRepainter repainter(*this, everHadLayout() && checkForRepaintDuringLayout());
1416
1417     LayoutUnit oldWidth = logicalWidth();
1418     LayoutUnit oldColumnWidth = desiredColumnWidth();
1419
1420     computeLogicalWidth();
1421     calcColumnWidth();
1422
1423     m_overflow.clear();
1424
1425     if (oldWidth != logicalWidth() || oldColumnWidth != desiredColumnWidth())
1426         relayoutChildren = true;
1427
1428     // If nothing changed about our floating positioned objects, let's go ahead and try to place them as
1429     // floats to avoid doing two passes.
1430     BlockLayoutPass floatsLayoutPass = layoutPass;
1431     if (floatsLayoutPass == NormalLayoutPass && !relayoutChildren && !positionedFloatsNeedRelayout())
1432         floatsLayoutPass = PositionedFloatLayoutPass;
1433     clearFloats(floatsLayoutPass);
1434
1435     LayoutUnit previousHeight = logicalHeight();
1436     setLogicalHeight(0);
1437     bool hasSpecifiedPageLogicalHeight = false;
1438     bool pageLogicalHeightChanged = false;
1439     ColumnInfo* colInfo = columnInfo();
1440     if (hasColumns()) {
1441         if (!pageLogicalHeight) {
1442             // We need to go ahead and set our explicit page height if one exists, so that we can
1443             // avoid doing two layout passes.
1444             computeLogicalHeight();
1445             LayoutUnit columnHeight = contentLogicalHeight();
1446             if (columnHeight > 0) {
1447                 pageLogicalHeight = columnHeight;
1448                 hasSpecifiedPageLogicalHeight = true;
1449             }
1450             setLogicalHeight(0);
1451         }
1452         if (colInfo->columnHeight() != pageLogicalHeight && everHadLayout()) {
1453             colInfo->setColumnHeight(pageLogicalHeight);
1454             pageLogicalHeightChanged = true;
1455         }
1456         
1457         if (!hasSpecifiedPageLogicalHeight && !pageLogicalHeight)
1458             colInfo->clearForcedBreaks();
1459
1460         colInfo->setPaginationUnit(paginationUnit());
1461     }
1462
1463     RenderView* renderView = view();
1464     RenderStyle* styleToUse = style();
1465     LayoutStateMaintainer statePusher(renderView, this, locationOffset(), hasColumns() || hasTransform() || hasReflection() || styleToUse->isFlippedBlocksWritingMode(), pageLogicalHeight, pageLogicalHeightChanged, colInfo);
1466
1467     if (inRenderFlowThread()) {
1468         // Regions changing widths can force us to relayout our children.
1469         if (logicalWidthChangedInRegions())
1470             relayoutChildren = true;
1471     }
1472     computeInitialRegionRangeForBlock();
1473
1474     // We use four values, maxTopPos, maxTopNeg, maxBottomPos, and maxBottomNeg, to track
1475     // our current maximal positive and negative margins.  These values are used when we
1476     // are collapsed with adjacent blocks, so for example, if you have block A and B
1477     // collapsing together, then you'd take the maximal positive margin from both A and B
1478     // and subtract it from the maximal negative margin from both A and B to get the
1479     // true collapsed margin.  This algorithm is recursive, so when we finish layout()
1480     // our block knows its current maximal positive/negative values.
1481     //
1482     // Start out by setting our margin values to our current margins.  Table cells have
1483     // no margins, so we don't fill in the values for table cells.
1484     bool isCell = isTableCell();
1485     if (!isCell) {
1486         initMaxMarginValues();
1487         
1488         setMarginBeforeQuirk(styleToUse->marginBefore().quirk());
1489         setMarginAfterQuirk(styleToUse->marginAfter().quirk());
1490
1491         Node* n = node();
1492         if (n && n->hasTagName(formTag) && static_cast<HTMLFormElement*>(n)->isMalformed()) {
1493             // See if this form is malformed (i.e., unclosed). If so, don't give the form
1494             // a bottom margin.
1495             setMaxMarginAfterValues(0, 0);
1496         }
1497         
1498         setPaginationStrut(0);
1499     }
1500
1501     // For overflow:scroll blocks, ensure we have both scrollbars in place always.
1502     if (scrollsOverflow() && style()->appearance() != ListboxPart) {
1503         if (styleToUse->overflowX() == OSCROLL)
1504             layer()->setHasHorizontalScrollbar(true);
1505         if (styleToUse->overflowY() == OSCROLL)
1506             layer()->setHasVerticalScrollbar(true);
1507     }
1508
1509     LayoutUnit repaintLogicalTop = 0;
1510     LayoutUnit repaintLogicalBottom = 0;
1511     LayoutUnit maxFloatLogicalBottom = 0;
1512     if (!firstChild() && !isAnonymousBlock())
1513         setChildrenInline(true);
1514     if (childrenInline())
1515         layoutInlineChildren(relayoutChildren, repaintLogicalTop, repaintLogicalBottom);
1516     else
1517         layoutBlockChildren(relayoutChildren, maxFloatLogicalBottom);
1518
1519     // Expand our intrinsic height to encompass floats.
1520     LayoutUnit toAdd = borderAfter() + paddingAfter() + scrollbarLogicalHeight();
1521     if (lowestFloatLogicalBottom() > (logicalHeight() - toAdd) && expandsToEncloseOverhangingFloats())
1522         setLogicalHeight(lowestFloatLogicalBottom() + toAdd);
1523     
1524     if (layoutColumns(hasSpecifiedPageLogicalHeight, pageLogicalHeight, statePusher))
1525         return;
1526  
1527     // Calculate our new height.
1528     LayoutUnit oldHeight = logicalHeight();
1529     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
1530     computeLogicalHeight();
1531     LayoutUnit newHeight = logicalHeight();
1532     if (oldHeight != newHeight) {
1533         if (oldHeight > newHeight && maxFloatLogicalBottom > newHeight && !childrenInline()) {
1534             // One of our children's floats may have become an overhanging float for us. We need to look for it.
1535             for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
1536                 if (child->isBlockFlow() && !child->isFloatingOrPositioned()) {
1537                     RenderBlock* block = toRenderBlock(child);
1538                     if (block->lowestFloatLogicalBottomIncludingPositionedFloats() + block->logicalTop() > newHeight)
1539                         addOverhangingFloats(block, false);
1540                 }
1541             }
1542         }
1543     }
1544
1545     if (previousHeight != newHeight)
1546         relayoutChildren = true;
1547
1548     bool needAnotherLayoutPass = layoutPositionedObjects(relayoutChildren || isRoot());
1549
1550     computeRegionRangeForBlock();
1551
1552     // Add overflow from children (unless we're multi-column, since in that case all our child overflow is clipped anyway).
1553     computeOverflow(oldClientAfterEdge);
1554     
1555     statePusher.pop();
1556
1557     if (renderView->layoutState()->m_pageLogicalHeight)
1558         setPageLogicalOffset(renderView->layoutState()->pageLogicalOffset(logicalTop()));
1559
1560     updateLayerTransform();
1561
1562     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
1563     // we overflow or not.
1564     updateScrollInfoAfterLayout();
1565
1566     // FIXME: This repaint logic should be moved into a separate helper function!
1567     // Repaint with our new bounds if they are different from our old bounds.
1568     bool didFullRepaint = repainter.repaintAfterLayout();
1569     if (!didFullRepaint && repaintLogicalTop != repaintLogicalBottom && (styleToUse->visibility() == VISIBLE || enclosingLayer()->hasVisibleContent())) {
1570         // FIXME: We could tighten up the left and right invalidation points if we let layoutInlineChildren fill them in based off the particular lines
1571         // it had to lay out.  We wouldn't need the hasOverflowClip() hack in that case either.
1572         LayoutUnit repaintLogicalLeft = logicalLeftVisualOverflow();
1573         LayoutUnit repaintLogicalRight = logicalRightVisualOverflow();
1574         if (hasOverflowClip()) {
1575             // If we have clipped overflow, we should use layout overflow as well, since visual overflow from lines didn't propagate to our block's overflow.
1576             // Note the old code did this as well but even for overflow:visible.  The addition of hasOverflowClip() at least tightens up the hack a bit.
1577             // layoutInlineChildren should be patched to compute the entire repaint rect.
1578             repaintLogicalLeft = min(repaintLogicalLeft, logicalLeftLayoutOverflow());
1579             repaintLogicalRight = max(repaintLogicalRight, logicalRightLayoutOverflow());
1580         }
1581         
1582         LayoutRect repaintRect;
1583         if (isHorizontalWritingMode())
1584             repaintRect = LayoutRect(repaintLogicalLeft, repaintLogicalTop, repaintLogicalRight - repaintLogicalLeft, repaintLogicalBottom - repaintLogicalTop);
1585         else
1586             repaintRect = LayoutRect(repaintLogicalTop, repaintLogicalLeft, repaintLogicalBottom - repaintLogicalTop, repaintLogicalRight - repaintLogicalLeft);
1587
1588         // The repaint rect may be split across columns, in which case adjustRectForColumns() will return the union.
1589         adjustRectForColumns(repaintRect);
1590
1591         repaintRect.inflate(maximalOutlineSize(PaintPhaseOutline));
1592         
1593         if (hasOverflowClip()) {
1594             // Adjust repaint rect for scroll offset
1595             repaintRect.move(-scrolledContentOffset());
1596
1597             // Don't allow this rect to spill out of our overflow box.
1598             repaintRect.intersect(LayoutRect(LayoutPoint(), size()));
1599         }
1600
1601         // Make sure the rect is still non-empty after intersecting for overflow above
1602         if (!repaintRect.isEmpty()) {
1603             repaintRectangle(repaintRect); // We need to do a partial repaint of our content.
1604             if (hasReflection())
1605                 repaintRectangle(reflectedRect(repaintRect));
1606         }
1607     }
1608     
1609     if (needAnotherLayoutPass && layoutPass == NormalLayoutPass) {
1610         setChildNeedsLayout(true, false);
1611         layoutBlock(false, pageLogicalHeight, PositionedFloatLayoutPass);
1612     } else
1613         setNeedsLayout(false);
1614 }
1615
1616 void RenderBlock::addOverflowFromChildren()
1617 {
1618     if (!hasColumns()) {
1619         if (childrenInline())
1620             addOverflowFromInlineChildren();
1621         else
1622             addOverflowFromBlockChildren();
1623     } else {
1624         ColumnInfo* colInfo = columnInfo();
1625         if (columnCount(colInfo)) {
1626             LayoutRect lastRect = columnRectAt(colInfo, columnCount(colInfo) - 1);
1627             addLayoutOverflow(lastRect);
1628             if (!hasOverflowClip())
1629                 addVisualOverflow(lastRect);
1630         }
1631     }
1632 }
1633
1634 void RenderBlock::computeOverflow(LayoutUnit oldClientAfterEdge, bool recomputeFloats)
1635 {
1636     // Add overflow from children.
1637     addOverflowFromChildren();
1638
1639     if (!hasColumns() && (recomputeFloats || isRoot() || expandsToEncloseOverhangingFloats() || hasSelfPaintingLayer()))
1640         addOverflowFromFloats();
1641
1642     // Add in the overflow from positioned objects.
1643     addOverflowFromPositionedObjects();
1644
1645     if (hasOverflowClip()) {
1646         // When we have overflow clip, propagate the original spillout since it will include collapsed bottom margins
1647         // and bottom padding.  Set the axis we don't care about to be 1, since we want this overflow to always
1648         // be considered reachable.
1649         LayoutRect clientRect(clientBoxRect());
1650         LayoutRect rectToApply;
1651         if (isHorizontalWritingMode())
1652             rectToApply = LayoutRect(clientRect.x(), clientRect.y(), 1, max<LayoutUnit>(0, oldClientAfterEdge - clientRect.y()));
1653         else
1654             rectToApply = LayoutRect(clientRect.x(), clientRect.y(), max<LayoutUnit>(0, oldClientAfterEdge - clientRect.x()), 1);
1655         addLayoutOverflow(rectToApply);
1656     }
1657         
1658     // Add visual overflow from box-shadow and border-image-outset.
1659     addVisualEffectOverflow();
1660
1661     // Add visual overflow from theme.
1662     addVisualOverflowFromTheme();
1663
1664     if (isRenderFlowThread())
1665         enclosingRenderFlowThread()->computeOverflowStateForRegions(oldClientAfterEdge);
1666 }
1667
1668 void RenderBlock::addOverflowFromBlockChildren()
1669 {
1670     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1671         if (!child->isFloatingOrPositioned())
1672             addOverflowFromChild(child);
1673     }
1674 }
1675
1676 void RenderBlock::addOverflowFromFloats()
1677 {
1678     if (!m_floatingObjects)
1679         return;
1680
1681     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1682     FloatingObjectSetIterator end = floatingObjectSet.end();
1683     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
1684         FloatingObject* r = *it;
1685         if (r->m_isDescendant && !r->m_renderer->isPositioned())
1686             addOverflowFromChild(r->m_renderer, IntSize(xPositionForFloatIncludingMargin(r), yPositionForFloatIncludingMargin(r)));
1687     }
1688     return;
1689 }
1690
1691 void RenderBlock::addOverflowFromPositionedObjects()
1692 {
1693     if (!m_positionedObjects)
1694         return;
1695
1696     RenderBox* positionedObject;
1697     Iterator end = m_positionedObjects->end();
1698     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
1699         positionedObject = *it;
1700         
1701         // Fixed positioned elements don't contribute to layout overflow, since they don't scroll with the content.
1702         if (positionedObject->style()->position() != FixedPosition) {
1703             int x = positionedObject->x();
1704             if (style()->shouldPlaceBlockDirectionScrollbarOnLogicalLeft())
1705                 x -= verticalScrollbarWidth();
1706             addOverflowFromChild(positionedObject, IntSize(x, positionedObject->y()));
1707         }
1708     }
1709 }
1710
1711 void RenderBlock::addVisualOverflowFromTheme()
1712 {
1713     if (!style()->hasAppearance())
1714         return;
1715
1716     IntRect inflatedRect = borderBoxRect();
1717     theme()->adjustRepaintRect(this, inflatedRect);
1718     addVisualOverflow(inflatedRect);
1719 }
1720
1721 bool RenderBlock::expandsToEncloseOverhangingFloats() const
1722 {
1723     return isInlineBlockOrInlineTable() || isFloatingOrPositioned() || hasOverflowClip() || (parent() && parent()->isDeprecatedFlexibleBox())
1724            || hasColumns() || isTableCell() || isTableCaption() || isFieldset() || isWritingModeRoot() || isRoot();
1725 }
1726
1727 void RenderBlock::adjustPositionedBlock(RenderBox* child, const MarginInfo& marginInfo)
1728 {
1729     bool isHorizontal = isHorizontalWritingMode();
1730     bool hasStaticBlockPosition = child->style()->hasStaticBlockPosition(isHorizontal);
1731     
1732     LayoutUnit logicalTop = logicalHeight();
1733     setStaticInlinePositionForChild(child, logicalTop, startOffsetForContent(logicalTop));
1734
1735     if (!marginInfo.canCollapseWithMarginBefore()) {
1736         child->computeBlockDirectionMargins(this);
1737         LayoutUnit marginBefore = marginBeforeForChild(child);
1738         LayoutUnit collapsedBeforePos = marginInfo.positiveMargin();
1739         LayoutUnit collapsedBeforeNeg = marginInfo.negativeMargin();
1740         if (marginBefore > 0) {
1741             if (marginBefore > collapsedBeforePos)
1742                 collapsedBeforePos = marginBefore;
1743         } else {
1744             if (-marginBefore > collapsedBeforeNeg)
1745                 collapsedBeforeNeg = -marginBefore;
1746         }
1747         logicalTop += (collapsedBeforePos - collapsedBeforeNeg) - marginBefore;
1748     }
1749     
1750     RenderLayer* childLayer = child->layer();
1751     if (childLayer->staticBlockPosition() != logicalTop) {
1752         childLayer->setStaticBlockPosition(logicalTop);
1753         if (hasStaticBlockPosition)
1754             child->setChildNeedsLayout(true, false);
1755     }
1756 }
1757
1758 void RenderBlock::adjustFloatingBlock(const MarginInfo& marginInfo)
1759 {
1760     // The float should be positioned taking into account the bottom margin
1761     // of the previous flow.  We add that margin into the height, get the
1762     // float positioned properly, and then subtract the margin out of the
1763     // height again.  In the case of self-collapsing blocks, we always just
1764     // use the top margins, since the self-collapsing block collapsed its
1765     // own bottom margin into its top margin.
1766     //
1767     // Note also that the previous flow may collapse its margin into the top of
1768     // our block.  If this is the case, then we do not add the margin in to our
1769     // height when computing the position of the float.   This condition can be tested
1770     // for by simply calling canCollapseWithMarginBefore.  See
1771     // http://www.hixie.ch/tests/adhoc/css/box/block/margin-collapse/046.html for
1772     // an example of this scenario.
1773     LayoutUnit marginOffset = marginInfo.canCollapseWithMarginBefore() ? zeroLayoutUnit : marginInfo.margin();
1774     setLogicalHeight(logicalHeight() + marginOffset);
1775     positionNewFloats();
1776     setLogicalHeight(logicalHeight() - marginOffset);
1777 }
1778
1779 bool RenderBlock::handleSpecialChild(RenderBox* child, const MarginInfo& marginInfo)
1780 {
1781     // Handle in the given order
1782     return handlePositionedChild(child, marginInfo)
1783         || handleFloatingChild(child, marginInfo)
1784         || handleRunInChild(child);
1785 }
1786
1787
1788 bool RenderBlock::handlePositionedChild(RenderBox* child, const MarginInfo& marginInfo)
1789 {
1790     if (child->isPositioned()) {
1791         child->containingBlock()->insertPositionedObject(child);
1792         adjustPositionedBlock(child, marginInfo);
1793         return true;
1794     }
1795     return false;
1796 }
1797
1798 bool RenderBlock::handleFloatingChild(RenderBox* child, const MarginInfo& marginInfo)
1799 {
1800     if (child->isFloating()) {
1801         insertFloatingObject(child);
1802         adjustFloatingBlock(marginInfo);
1803         return true;
1804     }
1805     return false;
1806 }
1807
1808 bool RenderBlock::handleRunInChild(RenderBox* child)
1809 {
1810     // See if we have a run-in element with inline children.  If the
1811     // children aren't inline, then just treat the run-in as a normal
1812     // block.
1813     if (!child->isRunIn() || !child->childrenInline())
1814         return false;
1815     // FIXME: We don't handle non-block elements with run-in for now.
1816     if (!child->isRenderBlock())
1817         return false;  
1818     // Run-in child shouldn't intrude into the sibling block if it is part of a
1819     // continuation chain. In that case, treat it as a normal block.
1820     if (child->isElementContinuation() || child->virtualContinuation())
1821         return false;
1822
1823     RenderBlock* blockRunIn = toRenderBlock(child);
1824     RenderObject* curr = blockRunIn->nextSibling();
1825     if (!curr || !curr->isRenderBlock() || !curr->childrenInline() || curr->isRunIn() || curr->isAnonymous() || curr->isFloatingOrPositioned())
1826         return false;
1827
1828     RenderBlock* currBlock = toRenderBlock(curr);
1829
1830     // First we destroy any :before/:after content. It will be regenerated by the new inline.
1831     // Exception is if the run-in itself is generated.
1832     if (child->style()->styleType() != BEFORE && child->style()->styleType() != AFTER) {
1833         RenderObject* generatedContent;
1834         if (child->getCachedPseudoStyle(BEFORE) && (generatedContent = child->beforePseudoElementRenderer()))
1835             generatedContent->destroy();
1836         if (child->getCachedPseudoStyle(AFTER) && (generatedContent = child->afterPseudoElementRenderer()))
1837             generatedContent->destroy();
1838     }
1839
1840     // Remove the old child.
1841     children()->removeChildNode(this, blockRunIn);
1842
1843     // Create an inline.
1844     Node* runInNode = blockRunIn->node();
1845     RenderInline* inlineRunIn = new (renderArena()) RenderInline(runInNode ? runInNode : document());
1846     inlineRunIn->setStyle(blockRunIn->style());
1847
1848     // Move the nodes from the old child to the new child
1849     for (RenderObject* runInChild = blockRunIn->firstChild(); runInChild;) {
1850         RenderObject* nextSibling = runInChild->nextSibling();
1851         blockRunIn->children()->removeChildNode(blockRunIn, runInChild, false);
1852         inlineRunIn->addChild(runInChild); // Use addChild instead of appendChildNode since it handles correct placement of the children relative to :after-generated content.
1853         runInChild = nextSibling;
1854     }
1855
1856     // Now insert the new child under |currBlock|. Use addChild instead of insertChildNode since it handles correct placement of the children, esp where we cannot insert
1857     // anything before the first child. e.g. details tag. See https://bugs.webkit.org/show_bug.cgi?id=58228.
1858     currBlock->addChild(inlineRunIn, currBlock->firstChild());
1859     
1860     // If the run-in had an element, we need to set the new renderer.
1861     if (runInNode)
1862         runInNode->setRenderer(inlineRunIn);
1863
1864     // Destroy the block run-in, which includes deleting its line box tree.
1865     blockRunIn->deleteLineBoxTree();
1866     blockRunIn->destroy();
1867
1868     // The block acts like an inline, so just null out its
1869     // position.
1870     
1871     return true;
1872 }
1873
1874 LayoutUnit RenderBlock::collapseMargins(RenderBox* child, MarginInfo& marginInfo)
1875 {
1876     // Get the four margin values for the child and cache them.
1877     const MarginValues childMargins = marginValuesForChild(child);
1878
1879     // Get our max pos and neg top margins.
1880     LayoutUnit posTop = childMargins.positiveMarginBefore();
1881     LayoutUnit negTop = childMargins.negativeMarginBefore();
1882
1883     // For self-collapsing blocks, collapse our bottom margins into our
1884     // top to get new posTop and negTop values.
1885     if (child->isSelfCollapsingBlock()) {
1886         posTop = max(posTop, childMargins.positiveMarginAfter());
1887         negTop = max(negTop, childMargins.negativeMarginAfter());
1888     }
1889     
1890     // See if the top margin is quirky. We only care if this child has
1891     // margins that will collapse with us.
1892     bool topQuirk = child->isMarginBeforeQuirk() || style()->marginBeforeCollapse() == MDISCARD;
1893
1894     if (marginInfo.canCollapseWithMarginBefore()) {
1895         // This child is collapsing with the top of the
1896         // block.  If it has larger margin values, then we need to update
1897         // our own maximal values.
1898         if (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !topQuirk)
1899             setMaxMarginBeforeValues(max(posTop, maxPositiveMarginBefore()), max(negTop, maxNegativeMarginBefore()));
1900
1901         // The minute any of the margins involved isn't a quirk, don't
1902         // collapse it away, even if the margin is smaller (www.webreference.com
1903         // has an example of this, a <dt> with 0.8em author-specified inside
1904         // a <dl> inside a <td>.
1905         if (!marginInfo.determinedMarginBeforeQuirk() && !topQuirk && (posTop - negTop)) {
1906             setMarginBeforeQuirk(false);
1907             marginInfo.setDeterminedMarginBeforeQuirk(true);
1908         }
1909
1910         if (!marginInfo.determinedMarginBeforeQuirk() && topQuirk && !marginBefore())
1911             // We have no top margin and our top child has a quirky margin.
1912             // We will pick up this quirky margin and pass it through.
1913             // This deals with the <td><div><p> case.
1914             // Don't do this for a block that split two inlines though.  You do
1915             // still apply margins in this case.
1916             setMarginBeforeQuirk(true);
1917     }
1918
1919     if (marginInfo.quirkContainer() && marginInfo.atBeforeSideOfBlock() && (posTop - negTop))
1920         marginInfo.setMarginBeforeQuirk(topQuirk);
1921
1922     LayoutUnit beforeCollapseLogicalTop = logicalHeight();
1923     LayoutUnit logicalTop = beforeCollapseLogicalTop;
1924     if (child->isSelfCollapsingBlock()) {
1925         // This child has no height.  We need to compute our
1926         // position before we collapse the child's margins together,
1927         // so that we can get an accurate position for the zero-height block.
1928         LayoutUnit collapsedBeforePos = max(marginInfo.positiveMargin(), childMargins.positiveMarginBefore());
1929         LayoutUnit collapsedBeforeNeg = max(marginInfo.negativeMargin(), childMargins.negativeMarginBefore());
1930         marginInfo.setMargin(collapsedBeforePos, collapsedBeforeNeg);
1931         
1932         // Now collapse the child's margins together, which means examining our
1933         // bottom margin values as well. 
1934         marginInfo.setPositiveMarginIfLarger(childMargins.positiveMarginAfter());
1935         marginInfo.setNegativeMarginIfLarger(childMargins.negativeMarginAfter());
1936
1937         if (!marginInfo.canCollapseWithMarginBefore())
1938             // We need to make sure that the position of the self-collapsing block
1939             // is correct, since it could have overflowing content
1940             // that needs to be positioned correctly (e.g., a block that
1941             // had a specified height of 0 but that actually had subcontent).
1942             logicalTop = logicalHeight() + collapsedBeforePos - collapsedBeforeNeg;
1943     }
1944     else {
1945         if (child->style()->marginBeforeCollapse() == MSEPARATE) {
1946             setLogicalHeight(logicalHeight() + marginInfo.margin() + marginBeforeForChild(child));
1947             logicalTop = logicalHeight();
1948         }
1949         else if (!marginInfo.atBeforeSideOfBlock() ||
1950             (!marginInfo.canCollapseMarginBeforeWithChildren()
1951              && (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.marginBeforeQuirk()))) {
1952             // We're collapsing with a previous sibling's margins and not
1953             // with the top of the block.
1954             setLogicalHeight(logicalHeight() + max(marginInfo.positiveMargin(), posTop) - max(marginInfo.negativeMargin(), negTop));
1955             logicalTop = logicalHeight();
1956         }
1957
1958         marginInfo.setPositiveMargin(childMargins.positiveMarginAfter());
1959         marginInfo.setNegativeMargin(childMargins.negativeMarginAfter());
1960
1961         if (marginInfo.margin())
1962             marginInfo.setMarginAfterQuirk(child->isMarginAfterQuirk() || style()->marginAfterCollapse() == MDISCARD);
1963     }
1964     
1965     // If margins would pull us past the top of the next page, then we need to pull back and pretend like the margins
1966     // collapsed into the page edge.
1967     LayoutState* layoutState = view()->layoutState();
1968     if (layoutState->isPaginated() && layoutState->pageLogicalHeight() && logicalTop > beforeCollapseLogicalTop
1969         && hasNextPage(beforeCollapseLogicalTop)) {
1970         LayoutUnit oldLogicalTop = logicalTop;
1971         logicalTop = min(logicalTop, nextPageLogicalTop(beforeCollapseLogicalTop));
1972         setLogicalHeight(logicalHeight() + (logicalTop - oldLogicalTop));
1973     }
1974     return logicalTop;
1975 }
1976
1977 LayoutUnit RenderBlock::clearFloatsIfNeeded(RenderBox* child, MarginInfo& marginInfo, LayoutUnit oldTopPosMargin, LayoutUnit oldTopNegMargin, LayoutUnit yPos)
1978 {
1979     LayoutUnit heightIncrease = getClearDelta(child, yPos);
1980     if (!heightIncrease)
1981         return yPos;
1982
1983     if (child->isSelfCollapsingBlock()) {
1984         // For self-collapsing blocks that clear, they can still collapse their
1985         // margins with following siblings.  Reset the current margins to represent
1986         // the self-collapsing block's margins only.
1987         // CSS2.1 states:
1988         // "An element that has had clearance applied to it never collapses its top margin with its parent block's bottom margin.
1989         // Therefore if we are at the bottom of the block, let's go ahead and reset margins to only include the
1990         // self-collapsing block's bottom margin.
1991         bool atBottomOfBlock = true;
1992         for (RenderBox* curr = child->nextSiblingBox(); curr && atBottomOfBlock; curr = curr->nextSiblingBox()) {
1993             if (!curr->isFloatingOrPositioned())
1994                 atBottomOfBlock = false;
1995         }
1996         
1997         MarginValues childMargins = marginValuesForChild(child);
1998         if (atBottomOfBlock) {
1999             marginInfo.setPositiveMargin(childMargins.positiveMarginAfter());
2000             marginInfo.setNegativeMargin(childMargins.negativeMarginAfter());
2001         } else {
2002             marginInfo.setPositiveMargin(max(childMargins.positiveMarginBefore(), childMargins.positiveMarginAfter()));
2003             marginInfo.setNegativeMargin(max(childMargins.negativeMarginBefore(), childMargins.negativeMarginAfter()));
2004         }
2005         
2006         // Adjust our height such that we are ready to be collapsed with subsequent siblings (or the bottom
2007         // of the parent block).
2008         setLogicalHeight(child->y() - max<LayoutUnit>(0, marginInfo.margin()));
2009     } else
2010         // Increase our height by the amount we had to clear.
2011         setLogicalHeight(height() + heightIncrease);
2012     
2013     if (marginInfo.canCollapseWithMarginBefore()) {
2014         // We can no longer collapse with the top of the block since a clear
2015         // occurred.  The empty blocks collapse into the cleared block.
2016         // FIXME: This isn't quite correct.  Need clarification for what to do
2017         // if the height the cleared block is offset by is smaller than the
2018         // margins involved.
2019         setMaxMarginBeforeValues(oldTopPosMargin, oldTopNegMargin);
2020         marginInfo.setAtBeforeSideOfBlock(false);
2021     }
2022     
2023     return yPos + heightIncrease;
2024 }
2025
2026 LayoutUnit RenderBlock::estimateLogicalTopPosition(RenderBox* child, const MarginInfo& marginInfo, LayoutUnit& estimateWithoutPagination)
2027 {
2028     // FIXME: We need to eliminate the estimation of vertical position, because when it's wrong we sometimes trigger a pathological
2029     // relayout if there are intruding floats.
2030     LayoutUnit logicalTopEstimate = logicalHeight();
2031     if (!marginInfo.canCollapseWithMarginBefore()) {
2032         LayoutUnit childMarginBefore = child->selfNeedsLayout() ? marginBeforeForChild(child) : collapsedMarginBeforeForChild(child);
2033         logicalTopEstimate += max(marginInfo.margin(), childMarginBefore);
2034     }
2035
2036     // Adjust logicalTopEstimate down to the next page if the margins are so large that we don't fit on the current
2037     // page.
2038     LayoutState* layoutState = view()->layoutState();
2039     if (layoutState->isPaginated() && layoutState->pageLogicalHeight() && logicalTopEstimate > logicalHeight()
2040         && hasNextPage(logicalHeight()))
2041         logicalTopEstimate = min(logicalTopEstimate, nextPageLogicalTop(logicalHeight()));
2042
2043     logicalTopEstimate += getClearDelta(child, logicalTopEstimate);
2044     
2045     estimateWithoutPagination = logicalTopEstimate;
2046
2047     if (layoutState->isPaginated()) {
2048         // If the object has a page or column break value of "before", then we should shift to the top of the next page.
2049         logicalTopEstimate = applyBeforeBreak(child, logicalTopEstimate);
2050     
2051         // For replaced elements and scrolled elements, we want to shift them to the next page if they don't fit on the current one.
2052         logicalTopEstimate = adjustForUnsplittableChild(child, logicalTopEstimate);
2053         
2054         if (!child->selfNeedsLayout() && child->isRenderBlock())
2055             logicalTopEstimate += toRenderBlock(child)->paginationStrut();
2056     }
2057
2058     return logicalTopEstimate;
2059 }
2060
2061 LayoutUnit RenderBlock::computeStartPositionDeltaForChildAvoidingFloats(const RenderBox* child, LayoutUnit childMarginStart,
2062     LayoutUnit childLogicalWidth, RenderRegion* region, LayoutUnit offsetFromLogicalTopOfFirstPage)
2063 {
2064     LayoutUnit startPosition = startOffsetForContent(region, offsetFromLogicalTopOfFirstPage);
2065
2066     // Add in our start margin.
2067     LayoutUnit oldPosition = startPosition + childMarginStart;
2068     LayoutUnit newPosition = oldPosition;
2069
2070     LayoutUnit blockOffset = logicalTopForChild(child);
2071     if (region)
2072         blockOffset = max(blockOffset, blockOffset + (region->offsetFromLogicalTopOfFirstPage() - offsetFromLogicalTopOfFirstPage));
2073
2074     LayoutUnit startOff = startOffsetForLine(blockOffset, false, region, offsetFromLogicalTopOfFirstPage);
2075     if (style()->textAlign() != WEBKIT_CENTER && !child->style()->marginStartUsing(style()).isAuto()) {
2076         if (childMarginStart < 0)
2077             startOff += childMarginStart;
2078         newPosition = max(newPosition, startOff); // Let the float sit in the child's margin if it can fit.
2079     } else if (startOff != startPosition) {
2080         // The object is shifting to the "end" side of the block. The object might be centered, so we need to
2081         // recalculate our inline direction margins. Note that the containing block content
2082         // width computation will take into account the delta between |startOff| and |startPosition|
2083         // so that we can just pass the content width in directly to the |computeMarginsInContainingBlockInlineDirection|
2084         // function.
2085         LayoutUnit oldMarginStart = marginStartForChild(child);
2086         LayoutUnit oldMarginEnd = marginEndForChild(child);
2087         RenderBox* mutableChild = const_cast<RenderBox*>(child);
2088         mutableChild->computeInlineDirectionMargins(this,
2089             availableLogicalWidthForLine(blockOffset, false, region, offsetFromLogicalTopOfFirstPage), childLogicalWidth);
2090         newPosition = startOff + marginStartForChild(child);
2091         if (inRenderFlowThread()) {
2092             setMarginStartForChild(mutableChild, oldMarginStart);
2093             setMarginEndForChild(mutableChild, oldMarginEnd);
2094         }
2095     }
2096     
2097     return newPosition - oldPosition;
2098 }
2099
2100 void RenderBlock::determineLogicalLeftPositionForChild(RenderBox* child)
2101 {
2102     LayoutUnit startPosition = borderStart() + paddingStart();
2103     if (style()->shouldPlaceBlockDirectionScrollbarOnLogicalLeft())
2104         startPosition -= verticalScrollbarWidth();
2105     LayoutUnit totalAvailableLogicalWidth = borderAndPaddingLogicalWidth() + availableLogicalWidth();
2106
2107     // Add in our start margin.
2108     LayoutUnit childMarginStart = marginStartForChild(child);
2109     LayoutUnit newPosition = startPosition + childMarginStart;
2110         
2111     // Some objects (e.g., tables, horizontal rules, overflow:auto blocks) avoid floats.  They need
2112     // to shift over as necessary to dodge any floats that might get in the way.
2113     if (child->avoidsFloats() && containsFloats() && !inRenderFlowThread())
2114         newPosition += computeStartPositionDeltaForChildAvoidingFloats(child, marginStartForChild(child), logicalWidthForChild(child));
2115
2116     setLogicalLeftForChild(child, style()->isLeftToRightDirection() ? newPosition : totalAvailableLogicalWidth - newPosition - logicalWidthForChild(child), ApplyLayoutDelta);
2117 }
2118
2119 void RenderBlock::setCollapsedBottomMargin(const MarginInfo& marginInfo)
2120 {
2121     if (marginInfo.canCollapseWithMarginAfter() && !marginInfo.canCollapseWithMarginBefore()) {
2122         // Update our max pos/neg bottom margins, since we collapsed our bottom margins
2123         // with our children.
2124         setMaxMarginAfterValues(max(maxPositiveMarginAfter(), marginInfo.positiveMargin()), max(maxNegativeMarginAfter(), marginInfo.negativeMargin()));
2125
2126         if (!marginInfo.marginAfterQuirk())
2127             setMarginAfterQuirk(false);
2128
2129         if (marginInfo.marginAfterQuirk() && marginAfter() == 0)
2130             // We have no bottom margin and our last child has a quirky margin.
2131             // We will pick up this quirky margin and pass it through.
2132             // This deals with the <td><div><p> case.
2133             setMarginAfterQuirk(true);
2134     }
2135 }
2136
2137 void RenderBlock::handleAfterSideOfBlock(LayoutUnit beforeSide, LayoutUnit afterSide, MarginInfo& marginInfo)
2138 {
2139     marginInfo.setAtAfterSideOfBlock(true);
2140
2141     // If we can't collapse with children then go ahead and add in the bottom margin.
2142     if (!marginInfo.canCollapseWithMarginAfter() && !marginInfo.canCollapseWithMarginBefore()
2143         && (!document()->inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.marginAfterQuirk()))
2144         setLogicalHeight(logicalHeight() + marginInfo.margin());
2145         
2146     // Now add in our bottom border/padding.
2147     setLogicalHeight(logicalHeight() + afterSide);
2148
2149     // Negative margins can cause our height to shrink below our minimal height (border/padding).
2150     // If this happens, ensure that the computed height is increased to the minimal height.
2151     setLogicalHeight(max(logicalHeight(), beforeSide + afterSide));
2152
2153     // Update our bottom collapsed margin info.
2154     setCollapsedBottomMargin(marginInfo);
2155 }
2156
2157 void RenderBlock::setLogicalLeftForChild(RenderBox* child, LayoutUnit logicalLeft, ApplyLayoutDeltaMode applyDelta)
2158 {
2159     if (isHorizontalWritingMode()) {
2160         if (applyDelta == ApplyLayoutDelta)
2161             view()->addLayoutDelta(LayoutSize(child->x() - logicalLeft, 0));
2162         child->setX(logicalLeft);
2163     } else {
2164         if (applyDelta == ApplyLayoutDelta)
2165             view()->addLayoutDelta(LayoutSize(0, child->y() - logicalLeft));
2166         child->setY(logicalLeft);
2167     }
2168 }
2169
2170 void RenderBlock::setLogicalTopForChild(RenderBox* child, LayoutUnit logicalTop, ApplyLayoutDeltaMode applyDelta)
2171 {
2172     if (isHorizontalWritingMode()) {
2173         if (applyDelta == ApplyLayoutDelta)
2174             view()->addLayoutDelta(LayoutSize(0, child->y() - logicalTop));
2175         child->setY(logicalTop);
2176     } else {
2177         if (applyDelta == ApplyLayoutDelta)
2178             view()->addLayoutDelta(LayoutSize(child->x() - logicalTop, 0));
2179         child->setX(logicalTop);
2180     }
2181 }
2182
2183 void RenderBlock::layoutBlockChildren(bool relayoutChildren, LayoutUnit& maxFloatLogicalBottom)
2184 {
2185     if (gPercentHeightDescendantsMap) {
2186         if (HashSet<RenderBox*>* descendants = gPercentHeightDescendantsMap->get(this)) {
2187             HashSet<RenderBox*>::iterator end = descendants->end();
2188             for (HashSet<RenderBox*>::iterator it = descendants->begin(); it != end; ++it) {
2189                 RenderBox* box = *it;
2190                 while (box != this) {
2191                     if (box->normalChildNeedsLayout())
2192                         break;
2193                     box->setChildNeedsLayout(true, false);
2194                     box = box->containingBlock();
2195                     ASSERT(box);
2196                     if (!box)
2197                         break;
2198                 }
2199             }
2200         }
2201     }
2202
2203     LayoutUnit beforeEdge = borderBefore() + paddingBefore();
2204     LayoutUnit afterEdge = borderAfter() + paddingAfter() + scrollbarLogicalHeight();
2205
2206     setLogicalHeight(beforeEdge);
2207     
2208     // Lay out our hypothetical grid line as though it occurs at the top of the block.
2209     if (view()->layoutState()->lineGrid() == this)
2210         layoutLineGridBox();
2211
2212     // The margin struct caches all our current margin collapsing state.  The compact struct caches state when we encounter compacts,
2213     MarginInfo marginInfo(this, beforeEdge, afterEdge);
2214
2215     // Fieldsets need to find their legend and position it inside the border of the object.
2216     // The legend then gets skipped during normal layout.  The same is true for ruby text.
2217     // It doesn't get included in the normal layout process but is instead skipped.
2218     RenderObject* childToExclude = layoutSpecialExcludedChild(relayoutChildren);
2219
2220     LayoutUnit previousFloatLogicalBottom = 0;
2221     maxFloatLogicalBottom = 0;
2222
2223     RenderBox* next = firstChildBox();
2224
2225     while (next) {
2226         RenderBox* child = next;
2227         next = child->nextSiblingBox();
2228
2229         if (childToExclude == child)
2230             continue; // Skip this child, since it will be positioned by the specialized subclass (fieldsets and ruby runs).
2231
2232         // Make sure we layout children if they need it.
2233         // FIXME: Technically percentage height objects only need a relayout if their percentage isn't going to be turned into
2234         // an auto value.  Add a method to determine this, so that we can avoid the relayout.
2235         RenderStyle* childStyle = child->style();
2236         if (relayoutChildren || ((childStyle->logicalHeight().isPercent() || childStyle->logicalMinHeight().isPercent() || childStyle->logicalMaxHeight().isPercent()) && !isRenderView()))
2237             child->setChildNeedsLayout(true, false);
2238
2239         // If relayoutChildren is set and the child has percentage padding or an embedded content box, we also need to invalidate the childs pref widths.
2240         if (relayoutChildren && child->needsPreferredWidthsRecalculation())
2241             child->setPreferredLogicalWidthsDirty(true, false);
2242
2243         // Handle the four types of special elements first.  These include positioned content, floating content, compacts and
2244         // run-ins.  When we encounter these four types of objects, we don't actually lay them out as normal flow blocks.
2245         if (handleSpecialChild(child, marginInfo))
2246             continue;
2247
2248         // Lay out the child.
2249         layoutBlockChild(child, marginInfo, previousFloatLogicalBottom, maxFloatLogicalBottom);
2250     }
2251     
2252     // Now do the handling of the bottom of the block, adding in our bottom border/padding and
2253     // determining the correct collapsed bottom margin information.
2254     handleAfterSideOfBlock(beforeEdge, afterEdge, marginInfo);
2255 }
2256
2257 void RenderBlock::layoutBlockChild(RenderBox* child, MarginInfo& marginInfo, LayoutUnit& previousFloatLogicalBottom, LayoutUnit& maxFloatLogicalBottom)
2258 {
2259     LayoutUnit oldPosMarginBefore = maxPositiveMarginBefore();
2260     LayoutUnit oldNegMarginBefore = maxNegativeMarginBefore();
2261
2262     // The child is a normal flow object.  Compute the margins we will use for collapsing now.
2263     child->computeBlockDirectionMargins(this);
2264
2265     // Do not allow a collapse if the margin-before-collapse style is set to SEPARATE.
2266     RenderStyle* childStyle = child->style();
2267     if (childStyle->marginBeforeCollapse() == MSEPARATE) {
2268         marginInfo.setAtBeforeSideOfBlock(false);
2269         marginInfo.clearMargin();
2270     }
2271
2272     // Try to guess our correct logical top position.  In most cases this guess will
2273     // be correct.  Only if we're wrong (when we compute the real logical top position)
2274     // will we have to potentially relayout.
2275     LayoutUnit estimateWithoutPagination;
2276     LayoutUnit logicalTopEstimate = estimateLogicalTopPosition(child, marginInfo, estimateWithoutPagination);
2277
2278     // Cache our old rect so that we can dirty the proper repaint rects if the child moves.
2279     LayoutRect oldRect(child->x(), child->y() , child->width(), child->height());
2280     LayoutUnit oldLogicalTop = logicalTopForChild(child);
2281
2282 #if !ASSERT_DISABLED
2283     LayoutSize oldLayoutDelta = view()->layoutDelta();
2284 #endif
2285     // Go ahead and position the child as though it didn't collapse with the top.
2286     setLogicalTopForChild(child, logicalTopEstimate, ApplyLayoutDelta);
2287
2288     RenderBlock* childRenderBlock = child->isRenderBlock() ? toRenderBlock(child) : 0;
2289     bool markDescendantsWithFloats = false;
2290     if (logicalTopEstimate != oldLogicalTop && !child->avoidsFloats() && childRenderBlock && childRenderBlock->containsFloats())
2291         markDescendantsWithFloats = true;
2292     else if (!child->avoidsFloats() || child->shrinkToAvoidFloats()) {
2293         // If an element might be affected by the presence of floats, then always mark it for
2294         // layout.
2295         LayoutUnit fb = max(previousFloatLogicalBottom, lowestFloatLogicalBottomIncludingPositionedFloats());
2296         if (fb > logicalTopEstimate)
2297             markDescendantsWithFloats = true;
2298     }
2299
2300     if (childRenderBlock) {
2301         if (markDescendantsWithFloats)
2302             childRenderBlock->markAllDescendantsWithFloatsForLayout();
2303         if (!child->isWritingModeRoot())
2304             previousFloatLogicalBottom = max(previousFloatLogicalBottom, oldLogicalTop + childRenderBlock->lowestFloatLogicalBottomIncludingPositionedFloats());
2305     }
2306
2307     if (!child->needsLayout())
2308         child->markForPaginationRelayoutIfNeeded();
2309
2310     bool childHadLayout = child->everHadLayout();
2311     bool childNeededLayout = child->needsLayout();
2312     if (childNeededLayout)
2313         child->layout();
2314
2315     // Cache if we are at the top of the block right now.
2316     bool atBeforeSideOfBlock = marginInfo.atBeforeSideOfBlock();
2317
2318     // Now determine the correct ypos based off examination of collapsing margin
2319     // values.
2320     LayoutUnit logicalTopBeforeClear = collapseMargins(child, marginInfo);
2321
2322     // Now check for clear.
2323     LayoutUnit logicalTopAfterClear = clearFloatsIfNeeded(child, marginInfo, oldPosMarginBefore, oldNegMarginBefore, logicalTopBeforeClear);
2324     
2325     bool paginated = view()->layoutState()->isPaginated();
2326     if (paginated)
2327         logicalTopAfterClear = adjustBlockChildForPagination(logicalTopAfterClear, estimateWithoutPagination, child,
2328             atBeforeSideOfBlock && logicalTopBeforeClear == logicalTopAfterClear);
2329
2330     setLogicalTopForChild(child, logicalTopAfterClear, ApplyLayoutDelta);
2331
2332     // Now we have a final top position.  See if it really does end up being different from our estimate.
2333     if (logicalTopAfterClear != logicalTopEstimate) {
2334         if (child->shrinkToAvoidFloats()) {
2335             // The child's width depends on the line width.
2336             // When the child shifts to clear an item, its width can
2337             // change (because it has more available line width).
2338             // So go ahead and mark the item as dirty.
2339             child->setChildNeedsLayout(true, false);
2340         }
2341         
2342         if (childRenderBlock) {
2343             if (!child->avoidsFloats() && childRenderBlock->containsFloats())
2344                 childRenderBlock->markAllDescendantsWithFloatsForLayout();
2345             if (!child->needsLayout())
2346                 child->markForPaginationRelayoutIfNeeded();
2347         }
2348
2349         // Our guess was wrong. Make the child lay itself out again.
2350         child->layoutIfNeeded();
2351     }
2352
2353     // We are no longer at the top of the block if we encounter a non-empty child.  
2354     // This has to be done after checking for clear, so that margins can be reset if a clear occurred.
2355     if (marginInfo.atBeforeSideOfBlock() && !child->isSelfCollapsingBlock())
2356         marginInfo.setAtBeforeSideOfBlock(false);
2357
2358     // Now place the child in the correct left position
2359     determineLogicalLeftPositionForChild(child);
2360
2361     // Update our height now that the child has been placed in the correct position.
2362     setLogicalHeight(logicalHeight() + logicalHeightForChild(child));
2363     if (childStyle->marginAfterCollapse() == MSEPARATE) {
2364         setLogicalHeight(logicalHeight() + marginAfterForChild(child));
2365         marginInfo.clearMargin();
2366     }
2367     // If the child has overhanging floats that intrude into following siblings (or possibly out
2368     // of this block), then the parent gets notified of the floats now.
2369     if (childRenderBlock && childRenderBlock->containsFloats())
2370         maxFloatLogicalBottom = max(maxFloatLogicalBottom, addOverhangingFloats(toRenderBlock(child), !childNeededLayout));
2371
2372     LayoutSize childOffset(child->x() - oldRect.x(), child->y() - oldRect.y());
2373     if (childOffset.width() || childOffset.height()) {
2374         view()->addLayoutDelta(childOffset);
2375
2376         // If the child moved, we have to repaint it as well as any floating/positioned
2377         // descendants.  An exception is if we need a layout.  In this case, we know we're going to
2378         // repaint ourselves (and the child) anyway.
2379         if (childHadLayout && !selfNeedsLayout() && child->checkForRepaintDuringLayout())
2380             child->repaintDuringLayoutIfMoved(oldRect);
2381     }
2382
2383     if (!childHadLayout && child->checkForRepaintDuringLayout()) {
2384         child->repaint();
2385         child->repaintOverhangingFloats(true);
2386     }
2387
2388     if (paginated) {
2389         // Check for an after page/column break.
2390         LayoutUnit newHeight = applyAfterBreak(child, logicalHeight(), marginInfo);
2391         if (newHeight != height())
2392             setLogicalHeight(newHeight);
2393     }
2394
2395     ASSERT(oldLayoutDelta == view()->layoutDelta());
2396 }
2397
2398 void RenderBlock::simplifiedNormalFlowLayout()
2399 {
2400     if (childrenInline()) {
2401         ListHashSet<RootInlineBox*> lineBoxes;
2402         for (InlineWalker walker(this); !walker.atEnd(); walker.advance()) {
2403             RenderObject* o = walker.current();
2404             if (!o->isPositioned() && (o->isReplaced() || o->isFloating())) {
2405                 o->layoutIfNeeded();
2406                 if (toRenderBox(o)->inlineBoxWrapper()) {
2407                     RootInlineBox* box = toRenderBox(o)->inlineBoxWrapper()->root();
2408                     lineBoxes.add(box);
2409                 }
2410             } else if (o->isText() || (o->isRenderInline() && !walker.atEndOfInline()))
2411                 o->setNeedsLayout(false);
2412         }
2413
2414         // FIXME: Glyph overflow will get lost in this case, but not really a big deal.
2415         GlyphOverflowAndFallbackFontsMap textBoxDataMap;                  
2416         for (ListHashSet<RootInlineBox*>::const_iterator it = lineBoxes.begin(); it != lineBoxes.end(); ++it) {
2417             RootInlineBox* box = *it;
2418             box->computeOverflow(box->lineTop(), box->lineBottom(), textBoxDataMap);
2419         }
2420     } else {
2421         for (RenderBox* box = firstChildBox(); box; box = box->nextSiblingBox()) {
2422             if (!box->isPositioned())
2423                 box->layoutIfNeeded();
2424         }
2425     }
2426 }
2427
2428 bool RenderBlock::simplifiedLayout()
2429 {
2430     if ((!posChildNeedsLayout() && !needsSimplifiedNormalFlowLayout()) || normalChildNeedsLayout() || selfNeedsLayout())
2431         return false;
2432
2433     LayoutStateMaintainer statePusher(view(), this, IntSize(x(), y()), hasColumns() || hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode());
2434     
2435     if (needsPositionedMovementLayout() && !tryLayoutDoingPositionedMovementOnly())
2436         return false;
2437
2438     // Lay out positioned descendants or objects that just need to recompute overflow.
2439     if (needsSimplifiedNormalFlowLayout())
2440         simplifiedNormalFlowLayout();
2441
2442     // Lay out our positioned objects if our positioned child bit is set.
2443     if (posChildNeedsLayout() && layoutPositionedObjects(false))
2444         return false; // If a positioned float is causing our normal flow to change, then we have to bail and do a full layout.
2445
2446     // Recompute our overflow information.
2447     // FIXME: We could do better here by computing a temporary overflow object from layoutPositionedObjects and only
2448     // updating our overflow if we either used to have overflow or if the new temporary object has overflow.
2449     // For now just always recompute overflow.  This is no worse performance-wise than the old code that called rightmostPosition and
2450     // lowestPosition on every relayout so it's not a regression.
2451     m_overflow.clear();
2452     computeOverflow(clientLogicalBottom(), true);
2453
2454     statePusher.pop();
2455     
2456     updateLayerTransform();
2457
2458     updateScrollInfoAfterLayout();
2459
2460     setNeedsLayout(false);
2461     return true;
2462 }
2463
2464 bool RenderBlock::positionedFloatsNeedRelayout()
2465 {
2466     if (!hasPositionedFloats())
2467         return false;
2468     
2469     RenderBox* positionedObject;
2470     Iterator end = m_positionedObjects->end();
2471     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2472         positionedObject = *it;
2473         if (!positionedObject->isFloating())
2474             continue;
2475
2476         if (positionedObject->needsLayout())
2477             return true;
2478
2479         if (positionedObject->style()->hasStaticBlockPosition(isHorizontalWritingMode()) && positionedObject->parent() != this && positionedObject->parent()->isBlockFlow())
2480             return true;
2481         
2482         if (view()->layoutState()->pageLogicalHeightChanged() || (view()->layoutState()->pageLogicalHeight() && view()->layoutState()->pageLogicalOffset(logicalTop()) != pageLogicalOffset()))
2483             return true;
2484     }
2485     
2486     return false;
2487 }
2488
2489 bool RenderBlock::layoutPositionedObjects(bool relayoutChildren)
2490 {
2491     if (!m_positionedObjects)
2492         return false;
2493         
2494     if (hasColumns())
2495         view()->layoutState()->clearPaginationInformation(); // Positioned objects are not part of the column flow, so they don't paginate with the columns.
2496
2497     bool didFloatingBoxRelayout = false;
2498
2499     RenderBox* r;
2500     Iterator end = m_positionedObjects->end();
2501     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2502         r = *it;
2503         // When a non-positioned block element moves, it may have positioned children that are implicitly positioned relative to the
2504         // non-positioned block.  Rather than trying to detect all of these movement cases, we just always lay out positioned
2505         // objects that are positioned implicitly like this.  Such objects are rare, and so in typical DHTML menu usage (where everything is
2506         // positioned explicitly) this should not incur a performance penalty.
2507         if (relayoutChildren || (r->style()->hasStaticBlockPosition(isHorizontalWritingMode()) && r->parent() != this))
2508             r->setChildNeedsLayout(true, false);
2509             
2510         // If relayoutChildren is set and the child has percentage padding or an embedded content box, we also need to invalidate the childs pref widths.
2511         if (relayoutChildren && r->needsPreferredWidthsRecalculation())
2512             r->setPreferredLogicalWidthsDirty(true, false);
2513         
2514         if (!r->needsLayout())
2515             r->markForPaginationRelayoutIfNeeded();
2516         
2517         // FIXME: Technically we could check the old placement and the new placement of the box and only invalidate if
2518         // the margin box of the object actually changed.
2519         if (r->needsLayout() && r->isFloating())
2520             didFloatingBoxRelayout = true;
2521
2522         // 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
2523         // and we hit the available width constraint, the layoutIfNeeded() will catch it and do a full layout.
2524         if (r->needsPositionedMovementLayoutOnly() && r->tryLayoutDoingPositionedMovementOnly())
2525             r->setNeedsLayout(false);
2526             
2527         // If we are paginated or in a line grid, go ahead and compute a vertical position for our object now.
2528         // If it's wrong we'll lay out again.
2529         LayoutUnit oldLogicalTop = 0;
2530         bool needsBlockDirectionLocationSetBeforeLayout = r->needsLayout() && view()->layoutState()->needsBlockDirectionLocationSetBeforeLayout(); 
2531         if (needsBlockDirectionLocationSetBeforeLayout) {
2532             if (isHorizontalWritingMode() == r->isHorizontalWritingMode())
2533                 r->computeLogicalHeight();
2534             else
2535                 r->computeLogicalWidth();
2536             oldLogicalTop = logicalTopForChild(r);
2537         }
2538             
2539         r->layoutIfNeeded();
2540         
2541         // Lay out again if our estimate was wrong.
2542         if (needsBlockDirectionLocationSetBeforeLayout && logicalTopForChild(r) != oldLogicalTop) {
2543             r->setChildNeedsLayout(true, false);
2544             r->layoutIfNeeded();
2545         }
2546     }
2547     
2548     if (hasColumns())
2549         view()->layoutState()->m_columnInfo = columnInfo(); // FIXME: Kind of gross. We just put this back into the layout state so that pop() will work.
2550         
2551     return didFloatingBoxRelayout;
2552 }
2553
2554 void RenderBlock::markPositionedObjectsForLayout()
2555 {
2556     if (m_positionedObjects) {
2557         RenderBox* r;
2558         Iterator end = m_positionedObjects->end();
2559         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2560             r = *it;
2561             r->setChildNeedsLayout(true);
2562         }
2563     }
2564 }
2565
2566 void RenderBlock::markForPaginationRelayoutIfNeeded()
2567 {
2568     ASSERT(!needsLayout());
2569     if (needsLayout())
2570         return;
2571
2572     if (view()->layoutState()->pageLogicalHeightChanged() || (view()->layoutState()->pageLogicalHeight() && view()->layoutState()->pageLogicalOffset(logicalTop()) != pageLogicalOffset()))
2573         setChildNeedsLayout(true, false);
2574 }
2575
2576 void RenderBlock::repaintOverhangingFloats(bool paintAllDescendants)
2577 {
2578     // Repaint any overhanging floats (if we know we're the one to paint them).
2579     // Otherwise, bail out.
2580     if (!hasOverhangingFloats())
2581         return;
2582
2583     // FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
2584     // in this block. Better yet would be to push extra state for the containers of other floats.
2585     LayoutStateDisabler layoutStateDisabler(view());
2586     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2587     FloatingObjectSetIterator end = floatingObjectSet.end();
2588     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
2589         FloatingObject* r = *it;
2590         // Only repaint the object if it is overhanging, is not in its own layer, and
2591         // is our responsibility to paint (m_shouldPaint is set). When paintAllDescendants is true, the latter
2592         // condition is replaced with being a descendant of us.
2593         if (logicalBottomForFloat(r) > logicalHeight() && ((paintAllDescendants && r->m_renderer->isDescendantOf(this)) || r->m_shouldPaint) && !r->m_renderer->hasSelfPaintingLayer()) {
2594             r->m_renderer->repaint();
2595             r->m_renderer->repaintOverhangingFloats();
2596         }
2597     }
2598 }
2599  
2600 void RenderBlock::paint(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2601 {
2602     LayoutPoint adjustedPaintOffset = paintOffset + location();
2603     
2604     PaintPhase phase = paintInfo.phase;
2605
2606     // Check if we need to do anything at all.
2607     // FIXME: Could eliminate the isRoot() check if we fix background painting so that the RenderView
2608     // paints the root's background.
2609     if (!isRoot()) {
2610         LayoutRect overflowBox = visualOverflowRect();
2611         flipForWritingMode(overflowBox);
2612         overflowBox.inflate(maximalOutlineSize(paintInfo.phase));
2613         overflowBox.moveBy(adjustedPaintOffset);
2614         if (!overflowBox.intersects(paintInfo.rect))
2615             return;
2616     }
2617
2618     bool pushedClip = pushContentsClip(paintInfo, adjustedPaintOffset);
2619     paintObject(paintInfo, adjustedPaintOffset);
2620     if (pushedClip)
2621         popContentsClip(paintInfo, phase, adjustedPaintOffset);
2622
2623     // Our scrollbar widgets paint exactly when we tell them to, so that they work properly with
2624     // z-index.  We paint after we painted the background/border, so that the scrollbars will
2625     // sit above the background/border.
2626     if (hasOverflowClip() && style()->visibility() == VISIBLE && (phase == PaintPhaseBlockBackground || phase == PaintPhaseChildBlockBackground) && paintInfo.shouldPaintWithinRoot(this))
2627         layer()->paintOverflowControls(paintInfo.context, roundedIntPoint(adjustedPaintOffset), paintInfo.rect);
2628 }
2629
2630 void RenderBlock::paintColumnRules(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2631 {
2632     if (paintInfo.context->paintingDisabled())
2633         return;
2634
2635     const Color& ruleColor = style()->visitedDependentColor(CSSPropertyWebkitColumnRuleColor);
2636     bool ruleTransparent = style()->columnRuleIsTransparent();
2637     EBorderStyle ruleStyle = style()->columnRuleStyle();
2638     LayoutUnit ruleThickness = style()->columnRuleWidth();
2639     LayoutUnit colGap = columnGap();
2640     bool renderRule = ruleStyle > BHIDDEN && !ruleTransparent && ruleThickness <= colGap;
2641     if (!renderRule)
2642         return;
2643
2644     ColumnInfo* colInfo = columnInfo();
2645     unsigned colCount = columnCount(colInfo);
2646
2647     bool antialias = shouldAntialiasLines(paintInfo.context);
2648
2649     if (colInfo->progressionAxis() == ColumnInfo::InlineAxis) {
2650         LayoutUnit currLogicalLeftOffset = style()->isLeftToRightDirection() ? zeroLayoutUnit : contentLogicalWidth();
2651         LayoutUnit ruleAdd = logicalLeftOffsetForContent();
2652         LayoutUnit ruleLogicalLeft = style()->isLeftToRightDirection() ? zeroLayoutUnit : contentLogicalWidth();
2653         LayoutUnit inlineDirectionSize = colInfo->desiredColumnWidth();
2654         BoxSide boxSide = isHorizontalWritingMode()
2655             ? style()->isLeftToRightDirection() ? BSLeft : BSRight
2656             : style()->isLeftToRightDirection() ? BSTop : BSBottom;
2657
2658         for (unsigned i = 0; i < colCount; i++) {
2659             // Move to the next position.
2660             if (style()->isLeftToRightDirection()) {
2661                 ruleLogicalLeft += inlineDirectionSize + colGap / 2;
2662                 currLogicalLeftOffset += inlineDirectionSize + colGap;
2663             } else {
2664                 ruleLogicalLeft -= (inlineDirectionSize + colGap / 2);
2665                 currLogicalLeftOffset -= (inlineDirectionSize + colGap);
2666             }
2667            
2668             // Now paint the column rule.
2669             if (i < colCount - 1) {
2670                 LayoutUnit ruleLeft = isHorizontalWritingMode() ? paintOffset.x() + ruleLogicalLeft - ruleThickness / 2 + ruleAdd : paintOffset.x() + borderLeft() + paddingLeft();
2671                 LayoutUnit ruleRight = isHorizontalWritingMode() ? ruleLeft + ruleThickness : ruleLeft + contentWidth();
2672                 LayoutUnit ruleTop = isHorizontalWritingMode() ? paintOffset.y() + borderTop() + paddingTop() : paintOffset.y() + ruleLogicalLeft - ruleThickness / 2 + ruleAdd;
2673                 LayoutUnit ruleBottom = isHorizontalWritingMode() ? ruleTop + contentHeight() : ruleTop + ruleThickness;
2674                 IntRect pixelSnappedRuleRect = pixelSnappedIntRectFromEdges(ruleLeft, ruleTop, ruleRight, ruleBottom);
2675                 drawLineForBoxSide(paintInfo.context, pixelSnappedRuleRect.x(), pixelSnappedRuleRect.y(), pixelSnappedRuleRect.maxX(), pixelSnappedRuleRect.maxY(), boxSide, ruleColor, ruleStyle, 0, 0, antialias);
2676             }
2677             
2678             ruleLogicalLeft = currLogicalLeftOffset;
2679         }
2680     } else {
2681         LayoutUnit ruleLeft = isHorizontalWritingMode() ? borderLeft() + paddingLeft() : colGap / 2 - colGap - ruleThickness / 2 + borderBefore() + paddingBefore();
2682         LayoutUnit ruleWidth = isHorizontalWritingMode() ? contentWidth() : ruleThickness;
2683         LayoutUnit ruleTop = isHorizontalWritingMode() ? colGap / 2 - colGap - ruleThickness / 2 + borderBefore() + paddingBefore() : borderStart() + paddingStart();
2684         LayoutUnit ruleHeight = isHorizontalWritingMode() ? ruleThickness : contentHeight();
2685         LayoutRect ruleRect(ruleLeft, ruleTop, ruleWidth, ruleHeight);
2686
2687         flipForWritingMode(ruleRect);
2688         ruleRect.moveBy(paintOffset);
2689
2690         BoxSide boxSide = isHorizontalWritingMode()
2691             ? !style()->isFlippedBlocksWritingMode() ? BSTop : BSBottom
2692             : !style()->isFlippedBlocksWritingMode() ? BSLeft : BSRight;
2693
2694         LayoutSize step(0, !style()->isFlippedBlocksWritingMode() ? colInfo->columnHeight() + colGap : -(colInfo->columnHeight() + colGap));
2695         if (!isHorizontalWritingMode())
2696             step = step.transposedSize();
2697
2698         for (unsigned i = 1; i < colCount; i++) {
2699             ruleRect.move(step);
2700             IntRect pixelSnappedRuleRect = pixelSnappedIntRect(ruleRect);
2701             drawLineForBoxSide(paintInfo.context, pixelSnappedRuleRect.x(), pixelSnappedRuleRect.y(), pixelSnappedRuleRect.maxX(), pixelSnappedRuleRect.maxY(), boxSide, ruleColor, ruleStyle, 0, 0, antialias);
2702         }
2703     }
2704 }
2705
2706 void RenderBlock::paintColumnContents(PaintInfo& paintInfo, const LayoutPoint& paintOffset, bool paintingFloats)
2707 {
2708     // We need to do multiple passes, breaking up our child painting into strips.
2709     GraphicsContext* context = paintInfo.context;
2710     ColumnInfo* colInfo = columnInfo();
2711     unsigned colCount = columnCount(colInfo);
2712     if (!colCount)
2713         return;
2714     LayoutUnit currLogicalTopOffset = 0;
2715     for (unsigned i = 0; i < colCount; i++) {
2716         // For each rect, we clip to the rect, and then we adjust our coords.
2717         LayoutRect colRect = columnRectAt(colInfo, i);
2718         flipForWritingMode(colRect);
2719         LayoutUnit logicalLeftOffset = (isHorizontalWritingMode() ? colRect.x() : colRect.y()) - logicalLeftOffsetForContent();
2720         LayoutSize offset = isHorizontalWritingMode() ? LayoutSize(logicalLeftOffset, currLogicalTopOffset) : LayoutSize(currLogicalTopOffset, logicalLeftOffset);
2721         if (colInfo->progressionAxis() == ColumnInfo::BlockAxis) {
2722             if (isHorizontalWritingMode())
2723                 offset.expand(0, colRect.y() - borderTop() - paddingTop());
2724             else
2725                 offset.expand(colRect.x() - borderLeft() - paddingLeft(), 0);
2726         }
2727         colRect.moveBy(paintOffset);
2728         PaintInfo info(paintInfo);
2729         info.rect.intersect(pixelSnappedIntRect(colRect));
2730         
2731         if (!info.rect.isEmpty()) {
2732             GraphicsContextStateSaver stateSaver(*context);
2733             
2734             // Each strip pushes a clip, since column boxes are specified as being
2735             // like overflow:hidden.
2736             context->clip(colRect);
2737
2738             // Adjust our x and y when painting.
2739             LayoutPoint adjustedPaintOffset = paintOffset + offset;
2740             if (paintingFloats)
2741                 paintFloats(info, adjustedPaintOffset, paintInfo.phase == PaintPhaseSelection || paintInfo.phase == PaintPhaseTextClip);
2742             else
2743                 paintContents(info, adjustedPaintOffset);
2744         }
2745
2746         LayoutUnit blockDelta = (isHorizontalWritingMode() ? colRect.height() : colRect.width());
2747         if (style()->isFlippedBlocksWritingMode())
2748             currLogicalTopOffset += blockDelta;
2749         else
2750             currLogicalTopOffset -= blockDelta;
2751     }
2752 }
2753
2754 void RenderBlock::paintContents(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2755 {
2756     // Avoid painting descendants of the root element when stylesheets haven't loaded.  This eliminates FOUC.
2757     // It's ok not to draw, because later on, when all the stylesheets do load, updateStyleSelector on the Document
2758     // will do a full repaint().
2759     if (document()->didLayoutWithPendingStylesheets() && !isRenderView())
2760         return;
2761
2762     // We don't want to hand off painting in the line box tree with the accumulated error of the render tree, as this will cause
2763     // us to mess up painting aligned things (such as underlines in text) with both the render tree and line box tree's error.
2764     LayoutPoint roundedPaintOffset = roundedIntPoint(paintOffset);
2765     if (childrenInline())
2766         m_lineBoxes.paint(this, paintInfo, roundedPaintOffset);
2767     else
2768         paintChildren(paintInfo, roundedPaintOffset);
2769 }
2770
2771 void RenderBlock::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2772 {
2773     PaintPhase newPhase = (paintInfo.phase == PaintPhaseChildOutlines) ? PaintPhaseOutline : paintInfo.phase;
2774     newPhase = (newPhase == PaintPhaseChildBlockBackgrounds) ? PaintPhaseChildBlockBackground : newPhase;
2775     
2776     // We don't paint our own background, but we do let the kids paint their backgrounds.
2777     PaintInfo info(paintInfo);
2778     info.phase = newPhase;
2779     info.updatePaintingRootForChildren(this);
2780     
2781     // FIXME: Paint-time pagination is obsolete and is now only used by embedded WebViews inside AppKit
2782     // NSViews.  Do not add any more code for this.
2783     RenderView* renderView = view();
2784     bool usePrintRect = !renderView->printRect().isEmpty();
2785     
2786     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {        
2787         // Check for page-break-before: always, and if it's set, break and bail.
2788         bool checkBeforeAlways = !childrenInline() && (usePrintRect && child->style()->pageBreakBefore() == PBALWAYS);
2789         LayoutUnit absoluteChildY = paintOffset.y() + child->y();
2790         if (checkBeforeAlways
2791             && absoluteChildY > paintInfo.rect.y()
2792             && absoluteChildY < paintInfo.rect.maxY()) {
2793             view()->setBestTruncatedAt(absoluteChildY, this, true);
2794             return;
2795         }
2796
2797         if (!child->isFloating() && child->isReplaced() && usePrintRect && child->height() <= renderView->printRect().height()) {
2798             // Paginate block-level replaced elements.
2799             if (absoluteChildY + child->height() > renderView->printRect().maxY()) {
2800                 if (absoluteChildY < renderView->truncatedAt())
2801                     renderView->setBestTruncatedAt(absoluteChildY, child);
2802                 // If we were able to truncate, don't paint.
2803                 if (absoluteChildY >= renderView->truncatedAt())
2804                     break;
2805             }
2806         }
2807
2808         LayoutPoint childPoint = flipForWritingModeForChild(child, paintOffset);
2809         if (!child->hasSelfPaintingLayer() && !child->isFloating())
2810             child->paint(info, childPoint);
2811
2812         // Check for page-break-after: always, and if it's set, break and bail.
2813         bool checkAfterAlways = !childrenInline() && (usePrintRect && child->style()->pageBreakAfter() == PBALWAYS);
2814         if (checkAfterAlways
2815             && (absoluteChildY + child->height()) > paintInfo.rect.y()
2816             && (absoluteChildY + child->height()) < paintInfo.rect.maxY()) {
2817             view()->setBestTruncatedAt(absoluteChildY + child->height() + max<LayoutUnit>(0, child->collapsedMarginAfter()), this, true);
2818             return;
2819         }
2820     }
2821 }
2822
2823 void RenderBlock::paintCaret(PaintInfo& paintInfo, const LayoutPoint& paintOffset, CaretType type)
2824 {
2825     // Paint the caret if the FrameSelection says so or if caret browsing is enabled
2826     bool caretBrowsing = frame()->settings() && frame()->settings()->caretBrowsingEnabled();
2827     RenderObject* caretPainter;
2828     bool isContentEditable;
2829     if (type == CursorCaret) {
2830         caretPainter = frame()->selection()->caretRenderer();
2831         isContentEditable = frame()->selection()->isContentEditable();
2832     } else {
2833         caretPainter = frame()->page()->dragCaretController()->caretRenderer();
2834         isContentEditable = frame()->page()->dragCaretController()->isContentEditable();
2835     }
2836
2837     if (caretPainter == this && (isContentEditable || caretBrowsing)) {
2838         if (type == CursorCaret)
2839             frame()->selection()->paintCaret(paintInfo.context, paintOffset, paintInfo.rect);
2840         else
2841             frame()->page()->dragCaretController()->paintDragCaret(frame(), paintInfo.context, paintOffset, paintInfo.rect);
2842     }
2843 }
2844
2845 void RenderBlock::paintObject(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2846 {
2847     PaintPhase paintPhase = paintInfo.phase;
2848
2849     // 1. paint background, borders etc
2850     if ((paintPhase == PaintPhaseBlockBackground || paintPhase == PaintPhaseChildBlockBackground) && style()->visibility() == VISIBLE) {
2851         if (hasBoxDecorations())
2852             paintBoxDecorations(paintInfo, paintOffset);
2853         if (hasColumns())
2854             paintColumnRules(paintInfo, paintOffset);
2855     }
2856
2857     if (paintPhase == PaintPhaseMask && style()->visibility() == VISIBLE) {
2858         paintMask(paintInfo, paintOffset);
2859         return;
2860     }
2861
2862     // We're done.  We don't bother painting any children.
2863     if (paintPhase == PaintPhaseBlockBackground)
2864         return;
2865
2866     // Adjust our painting position if we're inside a scrolled layer (e.g., an overflow:auto div).
2867     LayoutPoint scrolledOffset = paintOffset;
2868     if (hasOverflowClip())
2869         scrolledOffset.move(-scrolledContentOffset());
2870
2871     // 2. paint contents
2872     if (paintPhase != PaintPhaseSelfOutline) {
2873         if (hasColumns())
2874             paintColumnContents(paintInfo, scrolledOffset);
2875         else
2876             paintContents(paintInfo, scrolledOffset);
2877     }
2878
2879     // 3. paint selection
2880     // FIXME: Make this work with multi column layouts.  For now don't fill gaps.
2881     bool isPrinting = document()->printing();
2882     if (!isPrinting && !hasColumns())
2883         paintSelection(paintInfo, scrolledOffset); // Fill in gaps in selection on lines and between blocks.
2884
2885     // 4. paint floats.
2886     if (paintPhase == PaintPhaseFloat || paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip) {
2887         if (hasColumns())
2888             paintColumnContents(paintInfo, scrolledOffset, true);
2889         else
2890             paintFloats(paintInfo, scrolledOffset, paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip);
2891     }
2892
2893     // 5. paint outline.
2894     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseSelfOutline) && hasOutline() && style()->visibility() == VISIBLE)
2895         paintOutline(paintInfo.context, LayoutRect(paintOffset, size()));
2896
2897     // 6. paint continuation outlines.
2898     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseChildOutlines)) {
2899         RenderInline* inlineCont = inlineElementContinuation();
2900         if (inlineCont && inlineCont->hasOutline() && inlineCont->style()->visibility() == VISIBLE) {
2901             RenderInline* inlineRenderer = toRenderInline(inlineCont->node()->renderer());
2902             RenderBlock* cb = containingBlock();
2903
2904             bool inlineEnclosedInSelfPaintingLayer = false;
2905             for (RenderBoxModelObject* box = inlineRenderer; box != cb; box = box->parent()->enclosingBoxModelObject()) {
2906                 if (box->hasSelfPaintingLayer()) {
2907                     inlineEnclosedInSelfPaintingLayer = true;
2908                     break;
2909                 }
2910             }
2911
2912             if (!inlineEnclosedInSelfPaintingLayer)
2913                 cb->addContinuationWithOutline(inlineRenderer);
2914             else if (!inlineRenderer->firstLineBox())
2915                 inlineRenderer->paintOutline(paintInfo.context, paintOffset - locationOffset() + inlineRenderer->containingBlock()->location());
2916         }
2917         paintContinuationOutlines(paintInfo, paintOffset);
2918     }
2919
2920     // 7. paint caret.
2921     // If the caret's node's render object's containing block is this block, and the paint action is PaintPhaseForeground,
2922     // then paint the caret.
2923     if (paintPhase == PaintPhaseForeground) {        
2924         paintCaret(paintInfo, paintOffset, CursorCaret);
2925         paintCaret(paintInfo, paintOffset, DragCaret);
2926     }
2927 }
2928
2929 LayoutPoint RenderBlock::flipFloatForWritingModeForChild(const FloatingObject* child, const LayoutPoint& point) const
2930 {
2931     if (!style()->isFlippedBlocksWritingMode())
2932         return point;
2933     
2934     // This is similar to RenderBox::flipForWritingModeForChild. We have to subtract out our left/top offsets twice, since
2935     // it's going to get added back in. We hide this complication here so that the calling code looks normal for the unflipped
2936     // case.
2937     if (isHorizontalWritingMode())
2938         return LayoutPoint(point.x(), point.y() + height() - child->renderer()->height() - 2 * yPositionForFloatIncludingMargin(child));
2939     return LayoutPoint(point.x() + width() - child->width() - 2 * xPositionForFloatIncludingMargin(child), point.y());
2940 }
2941
2942 void RenderBlock::paintFloats(PaintInfo& paintInfo, const LayoutPoint& paintOffset, bool preservePhase)
2943 {
2944     if (!m_floatingObjects)
2945         return;
2946
2947     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2948     FloatingObjectSetIterator end = floatingObjectSet.end();
2949     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
2950         FloatingObject* r = *it;
2951         // Only paint the object if our m_shouldPaint flag is set.
2952         if (r->m_shouldPaint && !r->m_renderer->hasSelfPaintingLayer()) {
2953             PaintInfo currentPaintInfo(paintInfo);
2954             currentPaintInfo.phase = preservePhase ? paintInfo.phase : PaintPhaseBlockBackground;
2955             LayoutPoint childPoint = flipFloatForWritingModeForChild(r, LayoutPoint(paintOffset.x() + xPositionForFloatIncludingMargin(r) - r->m_renderer->x(), paintOffset.y() + yPositionForFloatIncludingMargin(r) - r->m_renderer->y()));
2956             r->m_renderer->paint(currentPaintInfo, childPoint);
2957             if (!preservePhase) {
2958                 currentPaintInfo.phase = PaintPhaseChildBlockBackgrounds;
2959                 r->m_renderer->paint(currentPaintInfo, childPoint);
2960                 currentPaintInfo.phase = PaintPhaseFloat;
2961                 r->m_renderer->paint(currentPaintInfo, childPoint);
2962                 currentPaintInfo.phase = PaintPhaseForeground;
2963                 r->m_renderer->paint(currentPaintInfo, childPoint);
2964                 currentPaintInfo.phase = PaintPhaseOutline;
2965                 r->m_renderer->paint(currentPaintInfo, childPoint);
2966             }
2967         }
2968     }
2969 }
2970
2971 void RenderBlock::paintEllipsisBoxes(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2972 {
2973     if (!paintInfo.shouldPaintWithinRoot(this) || !firstLineBox())
2974         return;
2975
2976     if (style()->visibility() == VISIBLE && paintInfo.phase == PaintPhaseForeground) {
2977         // We can check the first box and last box and avoid painting if we don't
2978         // intersect.
2979         LayoutUnit yPos = paintOffset.y() + firstLineBox()->y();
2980         LayoutUnit h = lastLineBox()->y() + lastLineBox()->logicalHeight() - firstLineBox()->y();
2981         if (yPos >= paintInfo.rect.maxY() || yPos + h <= paintInfo.rect.y())
2982             return;
2983
2984         // See if our boxes intersect with the dirty rect.  If so, then we paint
2985         // them.  Note that boxes can easily overlap, so we can't make any assumptions
2986         // based off positions of our first line box or our last line box.
2987         for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2988             yPos = paintOffset.y() + curr->y();
2989             h = curr->logicalHeight();
2990             if (curr->ellipsisBox() && yPos < paintInfo.rect.maxY() && yPos + h > paintInfo.rect.y())
2991                 curr->paintEllipsisBox(paintInfo, paintOffset, curr->lineTop(), curr->lineBottom());
2992         }
2993     }
2994 }
2995
2996 RenderInline* RenderBlock::inlineElementContinuation() const
2997
2998     RenderBoxModelObject* continuation = this->continuation();
2999     return continuation && continuation->isInline() ? toRenderInline(continuation) : 0;
3000 }
3001
3002 RenderBlock* RenderBlock::blockElementContinuation() const
3003 {
3004     RenderBoxModelObject* currentContinuation = continuation();
3005     if (!currentContinuation || currentContinuation->isInline())
3006         return 0;
3007     RenderBlock* nextContinuation = toRenderBlock(currentContinuation);
3008     if (nextContinuation->isAnonymousBlock())
3009         return nextContinuation->blockElementContinuation();
3010     return nextContinuation;
3011 }
3012     
3013 static ContinuationOutlineTableMap* continuationOutlineTable()
3014 {
3015     DEFINE_STATIC_LOCAL(ContinuationOutlineTableMap, table, ());
3016     return &table;
3017 }
3018
3019 void RenderBlock::addContinuationWithOutline(RenderInline* flow)
3020 {
3021     // We can't make this work if the inline is in a layer.  We'll just rely on the broken
3022     // way of painting.
3023     ASSERT(!flow->layer() && !flow->isInlineElementContinuation());
3024     
3025     ContinuationOutlineTableMap* table = continuationOutlineTable();
3026     ListHashSet<RenderInline*>* continuations = table->get(this);
3027     if (!continuations) {
3028         continuations = new ListHashSet<RenderInline*>;
3029         table->set(this, continuations);
3030     }
3031     
3032     continuations->add(flow);
3033 }
3034
3035 bool RenderBlock::paintsContinuationOutline(RenderInline* flow)
3036 {
3037     ContinuationOutlineTableMap* table = continuationOutlineTable();
3038     if (table->isEmpty())
3039         return false;
3040         
3041     ListHashSet<RenderInline*>* continuations = table->get(this);
3042     if (!continuations)
3043         return false;
3044
3045     return continuations->contains(flow);
3046 }
3047
3048 void RenderBlock::paintContinuationOutlines(PaintInfo& info, const LayoutPoint& paintOffset)
3049 {
3050     ContinuationOutlineTableMap* table = continuationOutlineTable();
3051     if (table->isEmpty())
3052         return;
3053         
3054     ListHashSet<RenderInline*>* continuations = table->get(this);
3055     if (!continuations)
3056         return;
3057
3058     LayoutPoint accumulatedPaintOffset = paintOffset;
3059     // Paint each continuation outline.
3060     ListHashSet<RenderInline*>::iterator end = continuations->end();
3061     for (ListHashSet<RenderInline*>::iterator it = continuations->begin(); it != end; ++it) {
3062         // Need to add in the coordinates of the intervening blocks.
3063         RenderInline* flow = *it;
3064         RenderBlock* block = flow->containingBlock();
3065         for ( ; block && block != this; block = block->containingBlock())
3066             accumulatedPaintOffset.moveBy(block->location());
3067         ASSERT(block);   
3068         flow->paintOutline(info.context, accumulatedPaintOffset);
3069     }
3070     
3071     // Delete
3072     delete continuations;
3073     table->remove(this);
3074 }
3075
3076 bool RenderBlock::shouldPaintSelectionGaps() const
3077 {
3078     return selectionState() != SelectionNone && style()->visibility() == VISIBLE && isSelectionRoot();
3079 }
3080
3081 bool RenderBlock::isSelectionRoot() const
3082 {
3083     if (!node())
3084         return false;
3085         
3086     // FIXME: Eventually tables should have to learn how to fill gaps between cells, at least in simple non-spanning cases.
3087     if (isTable())
3088         return false;
3089         
3090     if (isBody() || isRoot() || hasOverflowClip() || isRelPositioned() ||
3091         isFloatingOrPositioned() || isTableCell() || isInlineBlockOrInlineTable() || hasTransform() ||
3092         hasReflection() || hasMask() || isWritingModeRoot())
3093         return true;
3094     
3095     if (view() && view()->selectionStart()) {
3096         Node* startElement = view()->selectionStart()->node();
3097         if (startElement && startElement->rootEditableElement() == node())
3098             return true;
3099     }
3100     
3101     return false;
3102 }
3103
3104 GapRects RenderBlock::selectionGapRectsForRepaint(RenderBoxModelObject* repaintContainer)
3105 {
3106     ASSERT(!needsLayout());
3107
3108     if (!shouldPaintSelectionGaps())
3109         return GapRects();
3110
3111     // FIXME: this is broken with transforms
3112     TransformState transformState(TransformState::ApplyTransformDirection, FloatPoint());
3113     mapLocalToContainer(repaintContainer, false, false, transformState);
3114     LayoutPoint offsetFromRepaintContainer = roundedLayoutPoint(transformState.mappedPoint());
3115
3116     if (hasOverflowClip())
3117         offsetFromRepaintContainer -= scrolledContentOffset();
3118
3119     LayoutUnit lastTop = 0;
3120     LayoutUnit lastLeft = logicalLeftSelectionOffset(this, lastTop);
3121     LayoutUnit lastRight = logicalRightSelectionOffset(this, lastTop);
3122     
3123     return selectionGaps(this, offsetFromRepaintContainer, IntSize(), lastTop, lastLeft, lastRight);
3124 }
3125
3126 void RenderBlock::paintSelection(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
3127 {
3128     if (shouldPaintSelectionGaps() && paintInfo.phase == PaintPhaseForeground) {
3129         LayoutUnit lastTop = 0;
3130         LayoutUnit lastLeft = logicalLeftSelectionOffset(this, lastTop);
3131         LayoutUnit lastRight = logicalRightSelectionOffset(this, lastTop);
3132         GraphicsContextStateSaver stateSaver(*paintInfo.context);
3133
3134         LayoutRect gapRectsBounds = selectionGaps(this, paintOffset, LayoutSize(), lastTop, lastLeft, lastRight, &paintInfo);
3135         if (!gapRectsBounds.isEmpty()) {
3136             if (RenderLayer* layer = enclosingLayer()) {
3137                 gapRectsBounds.moveBy(-paintOffset);
3138                 if (!hasLayer()) {
3139                     LayoutRect localBounds(gapRectsBounds);
3140                     flipForWritingMode(localBounds);
3141                     gapRectsBounds = localToContainerQuad(FloatRect(localBounds), layer->renderer()).enclosingBoundingBox();
3142                     if (layer->renderer()->hasOverflowClip())
3143                         gapRectsBounds.move(layer->renderBox()->scrolledContentOffset());
3144                 }
3145                 layer->addBlockSelectionGapsBounds(gapRectsBounds);
3146             }
3147         }
3148     }
3149 }
3150
3151 static void clipOutPositionedObjects(const PaintInfo* paintInfo, const LayoutPoint& offset, RenderBlock::PositionedObjectsListHashSet* positionedObjects)
3152 {
3153     if (!positionedObjects)
3154         return;
3155     
3156     RenderBlock::PositionedObjectsListHashSet::const_iterator end = positionedObjects->end();
3157     for (RenderBlock::PositionedObjectsListHashSet::const_iterator it = positionedObjects->begin(); it != end; ++it) {
3158         RenderBox* r = *it;
3159         paintInfo->context->clipOut(IntRect(offset.x() + r->x(), offset.y() + r->y(), r->width(), r->height()));
3160     }
3161 }
3162
3163 static int blockDirectionOffset(RenderBlock* rootBlock, const LayoutSize& offsetFromRootBlock)
3164 {
3165     return rootBlock->isHorizontalWritingMode() ? offsetFromRootBlock.height() : offsetFromRootBlock.width();
3166 }
3167
3168 static int inlineDirectionOffset(RenderBlock* rootBlock, const LayoutSize& offsetFromRootBlock)
3169 {
3170     return rootBlock->isHorizontalWritingMode() ? offsetFromRootBlock.width() : offsetFromRootBlock.height();
3171 }
3172
3173 LayoutRect RenderBlock::logicalRectToPhysicalRect(const LayoutPoint& rootBlockPhysicalPosition, const LayoutRect& logicalRect)
3174 {
3175     LayoutRect result;
3176     if (isHorizontalWritingMode())
3177         result = logicalRect;
3178     else
3179         result = LayoutRect(logicalRect.y(), logicalRect.x(), logicalRect.height(), logicalRect.width());
3180     flipForWritingMode(result);
3181     result.moveBy(rootBlockPhysicalPosition);
3182     return result;
3183 }
3184
3185 GapRects RenderBlock::selectionGaps(RenderBlock* rootBlock, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock,
3186                                     LayoutUnit& lastLogicalTop, LayoutUnit& lastLogicalLeft, LayoutUnit& lastLogicalRight, const PaintInfo* paintInfo)
3187 {
3188     // IMPORTANT: Callers of this method that intend for painting to happen need to do a save/restore.
3189     // Clip out floating and positioned objects when painting selection gaps.
3190     if (paintInfo) {
3191         // Note that we don't clip out overflow for positioned objects.  We just stick to the border box.
3192         LayoutRect flippedBlockRect(offsetFromRootBlock.width(), offsetFromRootBlock.height(), width(), height());
3193         rootBlock->flipForWritingMode(flippedBlockRect);
3194         flippedBlockRect.moveBy(rootBlockPhysicalPosition);
3195         clipOutPositionedObjects(paintInfo, flippedBlockRect.location(), m_positionedObjects.get());
3196         if (isBody() || isRoot()) // The <body> must make sure to examine its containingBlock's positioned objects.
3197             for (RenderBlock* cb = containingBlock(); cb && !cb->isRenderView(); cb = cb->containingBlock())
3198                 clipOutPositionedObjects(paintInfo, LayoutPoint(cb->x(), cb->y()), cb->m_positionedObjects.get()); // FIXME: Not right for flipped writing modes.
3199         if (m_floatingObjects) {
3200             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
3201             FloatingObjectSetIterator end = floatingObjectSet.end();
3202             for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
3203                 FloatingObject* r = *it;
3204                 LayoutRect floatBox(offsetFromRootBlock.width() + xPositionForFloatIncludingMargin(r),
3205                                     offsetFromRootBlock.height() + yPositionForFloatIncludingMargin(r),
3206                                     r->m_renderer->width(), r->m_renderer->height());
3207                 rootBlock->flipForWritingMode(floatBox);
3208                 floatBox.move(rootBlockPhysicalPosition.x(), rootBlockPhysicalPosition.y());
3209                 paintInfo->context->clipOut(pixelSnappedIntRect(floatBox));
3210             }
3211         }
3212     }
3213
3214     // 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
3215     // fixed).
3216     GapRects result;
3217     if (!isBlockFlow()) // FIXME: Make multi-column selection gap filling work someday.
3218         return result;
3219
3220     if (hasColumns() || hasTransform() || style()->columnSpan()) {
3221         // FIXME: We should learn how to gap fill multiple columns and transforms eventually.
3222         lastLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + logicalHeight();
3223         lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, logicalHeight());
3224         lastLogicalRight = logicalRightSelectionOffset(rootBlock, logicalHeight());
3225         return result;
3226     }
3227
3228     if (childrenInline())
3229         result = inlineSelectionGaps(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, paintInfo);
3230     else
3231         result = blockSelectionGaps(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, paintInfo);
3232
3233     // Go ahead and fill the vertical gap all the way to the bottom of our block if the selection extends past our block.
3234     if (rootBlock == this && (selectionState() != SelectionBoth && selectionState() != SelectionEnd))
3235         result.uniteCenter(blockSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, 
3236                                              logicalHeight(), paintInfo));
3237     return result;
3238 }
3239
3240 GapRects RenderBlock::inlineSelectionGaps(RenderBlock* rootBlock, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock,
3241                                           LayoutUnit& lastLogicalTop, LayoutUnit& lastLogicalLeft, LayoutUnit& lastLogicalRight, const PaintInfo* paintInfo)
3242 {
3243     GapRects result;
3244
3245     bool containsStart = selectionState() == SelectionStart || selectionState() == SelectionBoth;
3246
3247     if (!firstLineBox()) {
3248         if (containsStart) {
3249             // Go ahead and update our lastLogicalTop to be the bottom of the block.  <hr>s or empty blocks with height can trip this
3250             // case.
3251             lastLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + logicalHeight();
3252             lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, logicalHeight());
3253             lastLogicalRight = logicalRightSelectionOffset(rootBlock, logicalHeight());
3254         }
3255         return result;
3256     }
3257
3258     RootInlineBox* lastSelectedLine = 0;
3259     RootInlineBox* curr;
3260     for (curr = firstRootBox(); curr && !curr->hasSelectedChildren(); curr = curr->nextRootBox()) { }
3261
3262     // Now paint the gaps for the lines.
3263     for (; curr && curr->hasSelectedChildren(); curr = curr->nextRootBox()) {
3264         LayoutUnit selTop =  curr->selectionTop();
3265         LayoutUnit selHeight = curr->selectionHeight();
3266
3267         if (!containsStart && !lastSelectedLine &&
3268             selectionState() != SelectionStart && selectionState() != SelectionBoth)
3269             result.uniteCenter(blockSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, 
3270                                                  selTop, paintInfo));
3271         
3272         LayoutRect logicalRect(curr->logicalLeft(), selTop, curr->logicalWidth(), selTop + selHeight);
3273         logicalRect.move(isHorizontalWritingMode() ? offsetFromRootBlock : offsetFromRootBlock.transposedSize());
3274         LayoutRect physicalRect = rootBlock->logicalRectToPhysicalRect(rootBlockPhysicalPosition, logicalRect);
3275         if (!paintInfo || (isHorizontalWritingMode() && physicalRect.y() < paintInfo->rect.maxY() && physicalRect.maxY() > paintInfo->rect.y())
3276             || (!isHorizontalWritingMode() && physicalRect.x() < paintInfo->rect.maxX() && physicalRect.maxX() > paintInfo->rect.x()))