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