60e19102135311e75a39826572bd48fef911cd60
[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 "RenderBlockFlow.h"
28 #include "RenderBox.h"
29 #include "RenderView.h"
30
31 using namespace WTF;
32
33 namespace WebCore {
34
35 struct SameSizeAsFloatingObject {
36     void* pointers[2];
37     LayoutRect rect;
38     int paginationStrut;
39     uint32_t bitfields : 8;
40 };
41
42 COMPILE_ASSERT(sizeof(FloatingObject) == sizeof(SameSizeAsFloatingObject), FloatingObject_should_stay_small);
43
44 FloatingObject::FloatingObject(RenderBox& renderer)
45     : m_renderer(renderer)
46     , m_originatingLine(nullptr)
47     , m_paginationStrut(0)
48     , m_shouldPaint(true)
49     , m_isDescendant(false)
50     , m_isPlaced(false)
51 #ifndef NDEBUG
52     , m_isInPlacedTree(false)
53 #endif
54 {
55     EFloat type = renderer.style().floating();
56     ASSERT(type != NoFloat);
57     if (type == LeftFloat)
58         m_type = FloatLeft;
59     else if (type == RightFloat)
60         m_type = FloatRight;
61 }
62
63 FloatingObject::FloatingObject(RenderBox& renderer, Type type, const LayoutRect& frameRect, bool shouldPaint, bool isDescendant)
64     : m_renderer(renderer)
65     , m_originatingLine(nullptr)
66     , m_frameRect(frameRect)
67     , m_paginationStrut(0)
68     , m_type(type)
69     , m_shouldPaint(shouldPaint)
70     , m_isDescendant(isDescendant)
71     , m_isPlaced(true)
72 #ifndef NDEBUG
73     , m_isInPlacedTree(false)
74 #endif
75 {
76 }
77
78 std::unique_ptr<FloatingObject> FloatingObject::create(RenderBox& renderer)
79 {
80     auto object = std::make_unique<FloatingObject>(renderer);
81     object->setShouldPaint(!renderer.hasSelfPaintingLayer()); // If a layer exists, the float will paint itself. Otherwise someone else will.
82     object->setIsDescendant(true);
83     return object;
84 }
85
86 std::unique_ptr<FloatingObject> FloatingObject::copyToNewContainer(LayoutSize offset, bool shouldPaint, bool isDescendant) const
87 {
88     // FIXME: Use make_unique here, once we can get it to compile on all platforms we support.
89     return std::unique_ptr<FloatingObject>(new FloatingObject(renderer(), type(), LayoutRect(frameRect().location() - offset, frameRect().size()), shouldPaint, isDescendant));
90 }
91
92 std::unique_ptr<FloatingObject> FloatingObject::unsafeClone() const
93 {
94     // FIXME: Use make_unique here, once we can get it to compile on all platforms we support.
95     std::unique_ptr<FloatingObject> cloneObject(new FloatingObject(renderer(), type(), m_frameRect, m_shouldPaint, m_isDescendant));
96     cloneObject->m_originatingLine = m_originatingLine;
97     cloneObject->m_paginationStrut = m_paginationStrut;
98     cloneObject->m_isPlaced = m_isPlaced;
99     return cloneObject;
100 }
101
102 inline static bool rangesIntersect(int floatTop, int floatBottom, int objectTop, int objectBottom)
103 {
104     if (objectTop >= floatBottom || objectBottom < floatTop)
105         return false;
106
107     // The top of the object overlaps the float
108     if (objectTop >= floatTop)
109         return true;
110
111     // The object encloses the float
112     if (objectTop < floatTop && objectBottom > floatBottom)
113         return true;
114
115     // The bottom of the object overlaps the float
116     if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
117         return true;
118
119     return false;
120 }
121
122 template <FloatingObject::Type FloatTypeValue>
123 class ComputeFloatOffsetAdapter {
124 public:
125     typedef FloatingObjectInterval IntervalType;
126
127     ComputeFloatOffsetAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
128         : m_renderer(renderer)
129         , m_lineTop(roundToInt(lineTop))
130         , m_lineBottom(roundToInt(lineBottom))
131         , m_offset(offset)
132         , m_outermostFloat(0)
133     {
134     }
135
136     int lowValue() const { return m_lineTop; }
137     int highValue() const { return m_lineBottom; }
138     void collectIfNeeded(const IntervalType&);
139
140     LayoutUnit offset() const { return m_offset; }
141     LayoutUnit shapeOffset() const;
142     LayoutUnit heightRemaining() const;
143
144 private:
145     bool updateOffsetIfNeeded(const FloatingObject*);
146
147     const RenderBlockFlow& m_renderer;
148     int m_lineTop;
149     int m_lineBottom;
150     LayoutUnit m_offset;
151     const FloatingObject* m_outermostFloat;
152 };
153
154 class FindNextFloatLogicalBottomAdapter {
155 public:
156     typedef FloatingObjectInterval IntervalType;
157
158     FindNextFloatLogicalBottomAdapter(const RenderBlockFlow& renderer, LayoutUnit belowLogicalHeight)
159         : m_renderer(renderer)
160         , m_belowLogicalHeight(floorToInt(belowLogicalHeight))
161         , m_aboveLogicalHeight(roundToInt(LayoutUnit::max()))
162         , m_nextLogicalBottom(LayoutUnit::max())
163         , m_nextShapeLogicalBottom(LayoutUnit::max())
164     {
165     }
166
167     int lowValue() const { return m_belowLogicalHeight; }
168     int highValue() const { return m_aboveLogicalHeight; }
169     void collectIfNeeded(const IntervalType&);
170
171     LayoutUnit nextLogicalBottom() { return m_nextLogicalBottom == LayoutUnit::max() ? LayoutUnit() : m_nextLogicalBottom; }
172     LayoutUnit nextShapeLogicalBottom() { return m_nextShapeLogicalBottom == LayoutUnit::max() ? nextLogicalBottom() : m_nextShapeLogicalBottom; }
173
174 private:
175     const RenderBlockFlow& m_renderer;
176     int m_belowLogicalHeight;
177     int m_aboveLogicalHeight;
178     LayoutUnit m_nextLogicalBottom;
179     LayoutUnit m_nextShapeLogicalBottom;
180 };
181
182 inline void FindNextFloatLogicalBottomAdapter::collectIfNeeded(const IntervalType& interval)
183 {
184     const FloatingObject* floatingObject = interval.data();
185     if (!rangesIntersect(interval.low(), interval.high(), m_belowLogicalHeight, m_aboveLogicalHeight))
186         return;
187
188     // All the objects returned from the tree should be already placed.
189     ASSERT(floatingObject->isPlaced());
190     ASSERT(rangesIntersect(m_renderer.pixelSnappedLogicalTopForFloat(floatingObject), m_renderer.pixelSnappedLogicalBottomForFloat(floatingObject), m_belowLogicalHeight, m_aboveLogicalHeight));
191
192     LayoutUnit floatBottom = m_renderer.logicalBottomForFloat(floatingObject);
193     if (m_nextLogicalBottom < floatBottom)
194         return;
195
196 #if ENABLE(CSS_SHAPES)
197     if (ShapeOutsideInfo* shapeOutside = floatingObject->renderer().shapeOutsideInfo()) {
198         LayoutUnit shapeBottom = m_renderer.logicalTopForFloat(floatingObject) + m_renderer.marginBeforeForChild(floatingObject->renderer()) + shapeOutside->shapeLogicalBottom();
199         // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
200         m_nextShapeLogicalBottom = std::min(shapeBottom, floatBottom);
201     } else
202         m_nextShapeLogicalBottom = floatBottom;
203 #endif
204     m_nextLogicalBottom = floatBottom;
205 }
206
207 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelow(LayoutUnit logicalHeight)
208 {
209     FindNextFloatLogicalBottomAdapter adapter(m_renderer, logicalHeight);
210     placedFloatsTree().allOverlapsWithAdapter(adapter);
211
212     return adapter.nextShapeLogicalBottom();
213 }
214
215 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelowForBlock(LayoutUnit logicalHeight)
216 {
217     FindNextFloatLogicalBottomAdapter adapter(m_renderer, logicalHeight);
218     placedFloatsTree().allOverlapsWithAdapter(adapter);
219
220     return adapter.nextLogicalBottom();
221 }
222
223 FloatingObjects::FloatingObjects(const RenderBlockFlow& renderer)
224     : m_placedFloatsTree(UninitializedTree)
225     , m_leftObjectsCount(0)
226     , m_rightObjectsCount(0)
227     , m_horizontalWritingMode(renderer.isHorizontalWritingMode())
228     , m_renderer(renderer)
229 {
230 }
231
232 FloatingObjects::~FloatingObjects()
233 {
234 }
235
236 void FloatingObjects::clearLineBoxTreePointers()
237 {
238     // Clear references to originating lines, since the lines are being deleted
239     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
240         ASSERT(!((*it)->originatingLine()) || &((*it)->originatingLine()->renderer()) == &m_renderer);
241         (*it)->setOriginatingLine(0);
242     }
243 }
244
245 void FloatingObjects::clear()
246 {
247     m_set.clear();
248     m_placedFloatsTree.clear();
249     m_leftObjectsCount = 0;
250     m_rightObjectsCount = 0;
251 }
252
253 void FloatingObjects::moveAllToFloatInfoMap(RendererToFloatInfoMap& map)
254 {
255     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
256         auto& renderer = it->get()->renderer();
257         // FIXME: The only reason it is safe to move these out of the set is that
258         // we are about to clear it. Otherwise it would break the hash table invariant.
259         // A clean way to do this would be to add a takeAll function to HashSet.
260         map.add(&renderer, std::move(*it));
261     }
262     clear();
263 }
264
265 void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
266 {
267     if (type == FloatingObject::FloatLeft)
268         m_leftObjectsCount++;
269     else
270         m_rightObjectsCount++;
271 }
272
273 void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
274 {
275     if (type == FloatingObject::FloatLeft)
276         m_leftObjectsCount--;
277     else
278         m_rightObjectsCount--;
279 }
280
281 FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
282 {
283     if (m_horizontalWritingMode)
284         return FloatingObjectInterval(floatingObject->frameRect().y(), floatingObject->frameRect().maxY(), floatingObject);
285     return FloatingObjectInterval(floatingObject->frameRect().x(), floatingObject->frameRect().maxX(), floatingObject);
286 }
287
288 void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
289 {
290     ASSERT(!floatingObject->isInPlacedTree());
291
292     floatingObject->setIsPlaced(true);
293     if (m_placedFloatsTree.isInitialized())
294         m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
295
296 #ifndef NDEBUG
297     floatingObject->setIsInPlacedTree(true);
298 #endif
299 }
300
301 void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
302 {
303     ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
304
305     if (m_placedFloatsTree.isInitialized()) {
306         bool removed = m_placedFloatsTree.remove(intervalForFloatingObject(floatingObject));
307         ASSERT_UNUSED(removed, removed);
308     }
309
310     floatingObject->setIsPlaced(false);
311 #ifndef NDEBUG
312     floatingObject->setIsInPlacedTree(false);
313 #endif
314 }
315
316 FloatingObject* FloatingObjects::add(std::unique_ptr<FloatingObject> floatingObject)
317 {
318     increaseObjectsCount(floatingObject->type());
319     if (floatingObject->isPlaced())
320         addPlacedObject(floatingObject.get());
321     return m_set.add(std::move(floatingObject)).iterator->get();
322 }
323
324 void FloatingObjects::remove(FloatingObject* floatingObject)
325 {
326     ASSERT((m_set.contains<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject)));
327     decreaseObjectsCount(floatingObject->type());
328     ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
329     if (floatingObject->isPlaced())
330         removePlacedObject(floatingObject);
331     ASSERT(!floatingObject->originatingLine());
332     auto it = m_set.find<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject);
333     if (it == m_set.end())
334         return;
335     m_set.remove(it);
336 }
337
338 void FloatingObjects::computePlacedFloatsTree()
339 {
340     ASSERT(!m_placedFloatsTree.isInitialized());
341     if (m_set.isEmpty())
342         return;
343     m_placedFloatsTree.initIfNeeded(m_renderer.view().intervalArena());
344     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
345         FloatingObject* floatingObject = it->get();
346         if (floatingObject->isPlaced())
347             m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
348     }
349 }
350
351 inline const FloatingObjectTree& FloatingObjects::placedFloatsTree()
352 {
353     if (!m_placedFloatsTree.isInitialized())
354         computePlacedFloatsTree();
355     return m_placedFloatsTree;
356 }
357
358 #if ENABLE(CSS_SHAPES)
359 static inline ShapeOutsideInfo* shapeInfoForFloat(const FloatingObject* floatingObject, const RenderBlockFlow& containingBlock, LayoutUnit lineTop, LayoutUnit lineBottom)
360 {
361     if (floatingObject) {
362         if (ShapeOutsideInfo* shapeOutside = floatingObject->renderer().shapeOutsideInfo()) {
363             shapeOutside->updateDeltasForContainingBlockLine(&containingBlock, floatingObject, lineTop, lineBottom - lineTop);
364             return shapeOutside;
365         }
366     }
367
368     return 0;
369 }
370 #endif
371
372 template<>
373 inline LayoutUnit ComputeFloatOffsetAdapter<FloatingObject::FloatLeft>::shapeOffset() const
374 {
375 #if ENABLE(CSS_SHAPES)
376     if (ShapeOutsideInfo* shapeOutside = shapeInfoForFloat(m_outermostFloat, m_renderer, m_lineTop, m_lineBottom))
377         return m_offset + shapeOutside->rightMarginBoxDelta();
378 #endif
379
380     return m_offset;
381 }
382
383 template<>
384 inline LayoutUnit ComputeFloatOffsetAdapter<FloatingObject::FloatRight>::shapeOffset() const
385 {
386 #if ENABLE(CSS_SHAPES)
387     if (ShapeOutsideInfo* shapeOutside = shapeInfoForFloat(m_outermostFloat, m_renderer, m_lineTop, m_lineBottom))
388         return m_offset + shapeOutside->leftMarginBoxDelta();
389 #endif
390
391     return m_offset;
392 }
393
394 LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
395 {
396     ComputeFloatOffsetAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
397     placedFloatsTree().allOverlapsWithAdapter(adapter);
398
399     if (heightRemaining)
400         *heightRemaining = adapter.heightRemaining();
401
402     return adapter.offset();
403 }
404
405 LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
406 {
407     ComputeFloatOffsetAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
408     placedFloatsTree().allOverlapsWithAdapter(adapter);
409
410     if (heightRemaining)
411         *heightRemaining = adapter.heightRemaining();
412
413     return std::min(fixedOffset, adapter.offset());
414 }
415
416 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
417 {
418     ComputeFloatOffsetAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
419     placedFloatsTree().allOverlapsWithAdapter(adapter);
420
421     return adapter.shapeOffset();
422 }
423
424 LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
425 {
426     ComputeFloatOffsetAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
427     placedFloatsTree().allOverlapsWithAdapter(adapter);
428
429     return std::min(fixedOffset, adapter.shapeOffset());
430 }
431
432 template<>
433 inline bool ComputeFloatOffsetAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
434 {
435     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
436     if (logicalRight > m_offset) {
437         m_offset = logicalRight;
438         return true;
439     }
440     return false;
441 }
442
443 template<>
444 inline bool ComputeFloatOffsetAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
445 {
446     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
447     if (logicalLeft < m_offset) {
448         m_offset = logicalLeft;
449         return true;
450     }
451     return false;
452 }
453
454 template <FloatingObject::Type FloatTypeValue>
455 inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
456 {
457     const FloatingObject* floatingObject = interval.data();
458     if (floatingObject->type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
459         return;
460
461     // All the objects returned from the tree should be already placed.
462     ASSERT(floatingObject->isPlaced());
463     ASSERT(rangesIntersect(m_renderer.pixelSnappedLogicalTopForFloat(floatingObject), m_renderer.pixelSnappedLogicalBottomForFloat(floatingObject), m_lineTop, m_lineBottom));
464
465     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
466     if (floatIsNewExtreme)
467         m_outermostFloat = floatingObject;
468 }
469
470 template <FloatingObject::Type FloatTypeValue>
471 LayoutUnit ComputeFloatOffsetAdapter<FloatTypeValue>::heightRemaining() const
472 {
473     return m_outermostFloat ? m_renderer.logicalBottomForFloat(m_outermostFloat) - m_lineTop : LayoutUnit(1);
474 }
475
476 } // namespace WebCore