Move Floats out of RenderBlock
[WebKit-https.git] / Source / WebCore / rendering / FloatingObjects.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 "FloatingObjects.h"
26
27 #include "RenderBlock.h"
28 #include "RenderBox.h"
29 #include "RenderView.h"
30
31 using namespace std;
32 using namespace WTF;
33
34 namespace WebCore {
35
36 struct SameSizeAsFloatingObject {
37     void* pointers[2];
38     LayoutRect rect;
39     int paginationStrut;
40     uint32_t bitfields : 8;
41 };
42
43 COMPILE_ASSERT(sizeof(FloatingObject) == sizeof(SameSizeAsFloatingObject), FloatingObject_should_stay_small);
44
45 template <FloatingObject::Type FloatTypeValue>
46 class ComputeFloatOffsetAdapter {
47 public:
48     typedef FloatingObjectInterval IntervalType;
49
50     ComputeFloatOffsetAdapter(const RenderBlock* renderer, int lineTop, int lineBottom, LayoutUnit& offset)
51         : m_renderer(renderer)
52         , m_lineTop(lineTop)
53         , m_lineBottom(lineBottom)
54         , m_offset(offset)
55         , m_outermostFloat(0)
56     {
57     }
58
59     int lowValue() const { return m_lineTop; }
60     int highValue() const { return m_lineBottom; }
61     void collectIfNeeded(const IntervalType&);
62
63 #if ENABLE(CSS_SHAPES)
64     // When computing the offset caused by the floats on a given line, if
65     // the outermost float on that line has a shape-outside, the inline
66     // content that butts up against that float must be positioned using
67     // the contours of the shape, not the margin box of the float.
68     const FloatingObject* outermostFloat() const { return m_outermostFloat; }
69 #endif
70
71     LayoutUnit getHeightRemaining() const;
72
73 private:
74     bool updateOffsetIfNeeded(const FloatingObject*);
75
76     const RenderBlock* m_renderer;
77     int m_lineTop;
78     int m_lineBottom;
79     LayoutUnit& m_offset;
80     const FloatingObject* m_outermostFloat;
81 };
82
83 FloatingObjects::FloatingObjects(const RenderBlock* renderer, bool horizontalWritingMode)
84     : m_placedFloatsTree(UninitializedTree)
85     , m_leftObjectsCount(0)
86     , m_rightObjectsCount(0)
87     , m_horizontalWritingMode(horizontalWritingMode)
88     , m_renderer(renderer)
89 {
90 }
91
92 FloatingObjects::~FloatingObjects()
93 {
94     // FIXME: m_set should use OwnPtr instead.
95     deleteAllValues(m_set);
96 }
97
98 void FloatingObjects::clearLineBoxTreePointers()
99 {
100     // Clear references to originating lines, since the lines are being deleted
101     FloatingObjectSetIterator end = m_set.end();
102     for (FloatingObjectSetIterator it = m_set.begin(); it != end; ++it) {
103         ASSERT(!((*it)->originatingLine()) || &((*it)->originatingLine()->renderer()) == m_renderer);
104         (*it)->setOriginatingLine(0);
105     }
106 }
107
108 void FloatingObjects::clear()
109 {
110     // FIXME: This should call deleteAllValues, except clearFloats
111     // like to play fast and loose with ownership of these pointers.
112     // If we move to OwnPtr that will fix this ownership oddness.
113     m_set.clear();
114     m_placedFloatsTree.clear();
115     m_leftObjectsCount = 0;
116     m_rightObjectsCount = 0;
117 }
118
119 void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
120 {
121     if (type == FloatingObject::FloatLeft)
122         m_leftObjectsCount++;
123     else
124         m_rightObjectsCount++;
125 }
126
127 void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
128 {
129     if (type == FloatingObject::FloatLeft)
130         m_leftObjectsCount--;
131     else
132         m_rightObjectsCount--;
133 }
134
135 FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
136 {
137     if (m_horizontalWritingMode)
138         return FloatingObjectInterval(floatingObject->frameRect().y(), floatingObject->frameRect().maxY(), floatingObject);
139     return FloatingObjectInterval(floatingObject->frameRect().x(), floatingObject->frameRect().maxX(), floatingObject);
140 }
141
142 void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
143 {
144     ASSERT(!floatingObject->isInPlacedTree());
145
146     floatingObject->setIsPlaced(true);
147     if (m_placedFloatsTree.isInitialized())
148         m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
149
150 #ifndef NDEBUG
151     floatingObject->setIsInPlacedTree(true);
152 #endif
153 }
154
155 void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
156 {
157     ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
158
159     if (m_placedFloatsTree.isInitialized()) {
160         bool removed = m_placedFloatsTree.remove(intervalForFloatingObject(floatingObject));
161         ASSERT_UNUSED(removed, removed);
162     }
163
164     floatingObject->setIsPlaced(false);
165 #ifndef NDEBUG
166     floatingObject->setIsInPlacedTree(false);
167 #endif
168 }
169
170 void FloatingObjects::add(FloatingObject* floatingObject)
171 {
172     increaseObjectsCount(floatingObject->type());
173     m_set.add(floatingObject);
174     if (floatingObject->isPlaced())
175         addPlacedObject(floatingObject);
176 }
177
178 void FloatingObjects::remove(FloatingObject* floatingObject)
179 {
180     decreaseObjectsCount(floatingObject->type());
181     m_set.remove(floatingObject);
182     ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
183     if (floatingObject->isPlaced())
184         removePlacedObject(floatingObject);
185 }
186
187 void FloatingObjects::computePlacedFloatsTree()
188 {
189     ASSERT(!m_placedFloatsTree.isInitialized());
190     if (m_set.isEmpty())
191         return;
192     m_placedFloatsTree.initIfNeeded(m_renderer->view().intervalArena());
193     FloatingObjectSetIterator it = m_set.begin();
194     FloatingObjectSetIterator end = m_set.end();
195     for (; it != end; ++it) {
196         FloatingObject* floatingObject = *it;
197         if (floatingObject->isPlaced())
198             m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
199     }
200 }
201
202 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight, ShapeOutsideFloatOffsetMode offsetMode, LayoutUnit *heightRemaining)
203 {
204 #if !ENABLE(CSS_SHAPES)
205     UNUSED_PARAM(offsetMode);
206 #endif
207
208     LayoutUnit offset = fixedOffset;
209     ComputeFloatOffsetAdapter<FloatingObject::FloatLeft> adapter(m_renderer, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), offset);
210     placedFloatsTree().allOverlapsWithAdapter(adapter);
211
212     if (heightRemaining)
213         *heightRemaining = adapter.getHeightRemaining();
214
215 #if ENABLE(CSS_SHAPES)
216     const FloatingObject* outermostFloat = adapter.outermostFloat();
217     if (offsetMode == ShapeOutsideFloatShapeOffset && outermostFloat) {
218         if (ShapeOutsideInfo* shapeOutside = outermostFloat->renderer()->shapeOutsideInfo()) {
219             shapeOutside->computeSegmentsForContainingBlockLine(logicalTop, outermostFloat->logicalTop(m_horizontalWritingMode), logicalHeight);
220             offset += shapeOutside->rightSegmentMarginBoxDelta();
221         }
222     }
223 #endif
224
225     return offset;
226 }
227
228 LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight, ShapeOutsideFloatOffsetMode offsetMode, LayoutUnit *heightRemaining)
229 {
230 #if !ENABLE(CSS_SHAPES)
231     UNUSED_PARAM(offsetMode);
232 #endif
233
234     LayoutUnit offset = fixedOffset;
235     ComputeFloatOffsetAdapter<FloatingObject::FloatRight> adapter(m_renderer, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), offset);
236     placedFloatsTree().allOverlapsWithAdapter(adapter);
237
238     if (heightRemaining)
239         *heightRemaining = adapter.getHeightRemaining();
240
241 #if ENABLE(CSS_SHAPES)
242     const FloatingObject* outermostFloat = adapter.outermostFloat();
243     if (offsetMode == ShapeOutsideFloatShapeOffset && outermostFloat) {
244         if (ShapeOutsideInfo* shapeOutside = outermostFloat->renderer()->shapeOutsideInfo()) {
245             shapeOutside->computeSegmentsForContainingBlockLine(logicalTop, outermostFloat->logicalTop(m_horizontalWritingMode), logicalHeight);
246             offset += shapeOutside->leftSegmentMarginBoxDelta();
247         }
248     }
249 #endif
250
251     return min(fixedOffset, offset);
252 }
253
254 inline static bool rangesIntersect(int floatTop, int floatBottom, int objectTop, int objectBottom)
255 {
256     if (objectTop >= floatBottom || objectBottom < floatTop)
257         return false;
258
259     // The top of the object overlaps the float
260     if (objectTop >= floatTop)
261         return true;
262
263     // The object encloses the float
264     if (objectTop < floatTop && objectBottom > floatBottom)
265         return true;
266
267     // The bottom of the object overlaps the float
268     if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
269         return true;
270
271     return false;
272 }
273
274 template<>
275 inline bool ComputeFloatOffsetAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
276 {
277     LayoutUnit logicalRight = floatingObject->logicalRight(m_renderer->isHorizontalWritingMode());
278     if (logicalRight > m_offset) {
279         m_offset = logicalRight;
280         return true;
281     }
282     return false;
283 }
284
285 template<>
286 inline bool ComputeFloatOffsetAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
287 {
288     LayoutUnit logicalLeft = floatingObject->logicalLeft(m_renderer->isHorizontalWritingMode());
289     if (logicalLeft < m_offset) {
290         m_offset = logicalLeft;
291         return true;
292     }
293     return false;
294 }
295
296 template <FloatingObject::Type FloatTypeValue>
297 inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
298 {
299     const FloatingObject* floatingObject = interval.data();
300     if (floatingObject->type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
301         return;
302
303     // All the objects returned from the tree should be already placed.
304     ASSERT(floatingObject->isPlaced());
305     ASSERT(rangesIntersect(floatingObject->pixelSnappedLogicalTop(m_renderer->isHorizontalWritingMode()), floatingObject->pixelSnappedLogicalBottom(m_renderer->isHorizontalWritingMode()), m_lineTop, m_lineBottom));
306
307     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
308     if (floatIsNewExtreme)
309         m_outermostFloat = floatingObject;
310 }
311
312 template <FloatingObject::Type FloatTypeValue>
313 LayoutUnit ComputeFloatOffsetAdapter<FloatTypeValue>::getHeightRemaining() const
314 {
315     return m_outermostFloat ? m_outermostFloat->logicalBottom(m_renderer->isHorizontalWritingMode()) - m_lineTop : LayoutUnit(1);
316 }
317
318 #ifndef NDEBUG
319 // These helpers are only used by the PODIntervalTree for debugging purposes.
320 String ValueToString<int>::string(const int value)
321 {
322     return String::number(value);
323 }
324
325 String ValueToString<FloatingObject*>::string(const FloatingObject* floatingObject)
326 {
327     return String::format("%p (%ix%i %ix%i)", floatingObject, floatingObject->frameRect().x().toInt(), floatingObject->frameRect().y().toInt(), floatingObject->frameRect().maxX().toInt(), floatingObject->frameRect().maxY().toInt());
328 }
329 #endif
330
331
332 } // namespace WebCore