Add WTF::move()
[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_paginationStrut = m_paginationStrut;
97     cloneObject->m_isPlaced = m_isPlaced;
98     return cloneObject;
99 }
100
101 inline static bool rangesIntersect(LayoutUnit floatTop, LayoutUnit floatBottom, LayoutUnit objectTop, LayoutUnit objectBottom)
102 {
103     if (objectTop >= floatBottom || objectBottom < floatTop)
104         return false;
105
106     // The top of the object overlaps the float
107     if (objectTop >= floatTop)
108         return true;
109
110     // The object encloses the float
111     if (objectTop < floatTop && objectBottom > floatBottom)
112         return true;
113
114     // The bottom of the object overlaps the float
115     if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
116         return true;
117
118     return false;
119 }
120
121 template <FloatingObject::Type FloatTypeValue>
122 class ComputeFloatOffsetAdapter {
123 public:
124     typedef FloatingObjectInterval IntervalType;
125
126     ComputeFloatOffsetAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
127         : m_renderer(renderer)
128         , m_lineTop(lineTop)
129         , m_lineBottom(lineBottom)
130         , m_offset(offset)
131         , m_outermostFloat(0)
132     {
133     }
134
135     virtual ~ComputeFloatOffsetAdapter() { }
136
137     LayoutUnit lowValue() const { return m_lineTop; }
138     LayoutUnit highValue() const { return m_lineBottom; }
139     void collectIfNeeded(const IntervalType&);
140
141     LayoutUnit offset() const { return m_offset; }
142
143 protected:
144     virtual bool updateOffsetIfNeeded(const FloatingObject*) = 0;
145
146     const RenderBlockFlow& m_renderer;
147     LayoutUnit m_lineTop;
148     LayoutUnit m_lineBottom;
149     LayoutUnit m_offset;
150     const FloatingObject* m_outermostFloat;
151 };
152
153 template <FloatingObject::Type FloatTypeValue>
154 class ComputeFloatOffsetForFloatLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> { 
155 public:
156     ComputeFloatOffsetForFloatLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
157         : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
158     {
159     }
160
161     virtual ~ComputeFloatOffsetForFloatLayoutAdapter() { }
162
163     LayoutUnit heightRemaining() const;
164
165 protected:
166     virtual bool updateOffsetIfNeeded(const FloatingObject*) override final;
167 };
168
169 template <FloatingObject::Type FloatTypeValue>
170 class ComputeFloatOffsetForLineLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
171 public:
172     ComputeFloatOffsetForLineLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
173         : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
174     {
175     }
176
177     virtual ~ComputeFloatOffsetForLineLayoutAdapter() { }
178
179 protected:
180     virtual bool updateOffsetIfNeeded(const FloatingObject*) override final;
181 };
182
183 class FindNextFloatLogicalBottomAdapter {
184 public:
185     typedef FloatingObjectInterval IntervalType;
186
187     FindNextFloatLogicalBottomAdapter(const RenderBlockFlow& renderer, LayoutUnit belowLogicalHeight)
188         : m_renderer(renderer)
189         , m_belowLogicalHeight(belowLogicalHeight)
190         , m_aboveLogicalHeight(LayoutUnit::max())
191         , m_nextLogicalBottom(LayoutUnit::max())
192         , m_nextShapeLogicalBottom(LayoutUnit::max())
193     {
194     }
195
196     LayoutUnit lowValue() const { return m_belowLogicalHeight; }
197     LayoutUnit highValue() const { return m_aboveLogicalHeight; }
198     void collectIfNeeded(const IntervalType&);
199
200     LayoutUnit nextLogicalBottom() { return m_nextLogicalBottom == LayoutUnit::max() ? LayoutUnit() : m_nextLogicalBottom; }
201     LayoutUnit nextShapeLogicalBottom() { return m_nextShapeLogicalBottom == LayoutUnit::max() ? nextLogicalBottom() : m_nextShapeLogicalBottom; }
202
203 private:
204     const RenderBlockFlow& m_renderer;
205     LayoutUnit m_belowLogicalHeight;
206     LayoutUnit m_aboveLogicalHeight;
207     LayoutUnit m_nextLogicalBottom;
208     LayoutUnit m_nextShapeLogicalBottom;
209 };
210
211 inline void FindNextFloatLogicalBottomAdapter::collectIfNeeded(const IntervalType& interval)
212 {
213     const FloatingObject* floatingObject = interval.data();
214     if (!rangesIntersect(interval.low(), interval.high(), m_belowLogicalHeight, m_aboveLogicalHeight))
215         return;
216
217     // All the objects returned from the tree should be already placed.
218     ASSERT(floatingObject->isPlaced());
219     ASSERT(rangesIntersect(m_renderer.logicalTopForFloat(floatingObject), m_renderer.logicalBottomForFloat(floatingObject), m_belowLogicalHeight, m_aboveLogicalHeight));
220
221     LayoutUnit floatBottom = m_renderer.logicalBottomForFloat(floatingObject);
222     if (m_nextLogicalBottom < floatBottom)
223         return;
224
225 #if ENABLE(CSS_SHAPES)
226     if (ShapeOutsideInfo* shapeOutside = floatingObject->renderer().shapeOutsideInfo()) {
227         LayoutUnit shapeBottom = m_renderer.logicalTopForFloat(floatingObject) + m_renderer.marginBeforeForChild(floatingObject->renderer()) + shapeOutside->shapeLogicalBottom();
228         // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
229         m_nextShapeLogicalBottom = std::min(shapeBottom, floatBottom);
230     } else
231         m_nextShapeLogicalBottom = floatBottom;
232 #endif
233     m_nextLogicalBottom = floatBottom;
234 }
235
236 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelow(LayoutUnit logicalHeight)
237 {
238     FindNextFloatLogicalBottomAdapter adapter(m_renderer, logicalHeight);
239     placedFloatsTree().allOverlapsWithAdapter(adapter);
240
241     return adapter.nextShapeLogicalBottom();
242 }
243
244 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelowForBlock(LayoutUnit logicalHeight)
245 {
246     FindNextFloatLogicalBottomAdapter adapter(m_renderer, logicalHeight);
247     placedFloatsTree().allOverlapsWithAdapter(adapter);
248
249     return adapter.nextLogicalBottom();
250 }
251
252 FloatingObjects::FloatingObjects(const RenderBlockFlow& renderer)
253     : m_placedFloatsTree(UninitializedTree)
254     , m_leftObjectsCount(0)
255     , m_rightObjectsCount(0)
256     , m_horizontalWritingMode(renderer.isHorizontalWritingMode())
257     , m_renderer(renderer)
258 {
259 }
260
261 FloatingObjects::~FloatingObjects()
262 {
263 }
264
265 void FloatingObjects::clearLineBoxTreePointers()
266 {
267     // Clear references to originating lines, since the lines are being deleted
268     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
269         ASSERT(!((*it)->originatingLine()) || &((*it)->originatingLine()->renderer()) == &m_renderer);
270         (*it)->setOriginatingLine(0);
271     }
272 }
273
274 void FloatingObjects::clear()
275 {
276     m_set.clear();
277     m_placedFloatsTree.clear();
278     m_leftObjectsCount = 0;
279     m_rightObjectsCount = 0;
280 }
281
282 void FloatingObjects::moveAllToFloatInfoMap(RendererToFloatInfoMap& map)
283 {
284     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
285         auto& renderer = it->get()->renderer();
286         // FIXME: The only reason it is safe to move these out of the set is that
287         // we are about to clear it. Otherwise it would break the hash table invariant.
288         // A clean way to do this would be to add a takeAll function to HashSet.
289         map.add(&renderer, WTF::move(*it));
290     }
291     clear();
292 }
293
294 void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
295 {
296     if (type == FloatingObject::FloatLeft)
297         m_leftObjectsCount++;
298     else
299         m_rightObjectsCount++;
300 }
301
302 void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
303 {
304     if (type == FloatingObject::FloatLeft)
305         m_leftObjectsCount--;
306     else
307         m_rightObjectsCount--;
308 }
309
310 FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
311 {
312     // FIXME The endpoints of the floating object interval shouldn't need to be
313     // floored. See http://wkb.ug/125831 for more details.
314     if (m_horizontalWritingMode)
315         return FloatingObjectInterval(floatingObject->frameRect().y().floor(), floatingObject->frameRect().maxY().floor(), floatingObject);
316     return FloatingObjectInterval(floatingObject->frameRect().x().floor(), floatingObject->frameRect().maxX().floor(), floatingObject);
317 }
318
319 void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
320 {
321     ASSERT(!floatingObject->isInPlacedTree());
322
323     floatingObject->setIsPlaced(true);
324     if (m_placedFloatsTree.isInitialized())
325         m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
326
327 #ifndef NDEBUG
328     floatingObject->setIsInPlacedTree(true);
329 #endif
330 }
331
332 void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
333 {
334     ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
335
336     if (m_placedFloatsTree.isInitialized()) {
337         bool removed = m_placedFloatsTree.remove(intervalForFloatingObject(floatingObject));
338         ASSERT_UNUSED(removed, removed);
339     }
340
341     floatingObject->setIsPlaced(false);
342 #ifndef NDEBUG
343     floatingObject->setIsInPlacedTree(false);
344 #endif
345 }
346
347 FloatingObject* FloatingObjects::add(std::unique_ptr<FloatingObject> floatingObject)
348 {
349     increaseObjectsCount(floatingObject->type());
350     if (floatingObject->isPlaced())
351         addPlacedObject(floatingObject.get());
352     return m_set.add(WTF::move(floatingObject)).iterator->get();
353 }
354
355 void FloatingObjects::remove(FloatingObject* floatingObject)
356 {
357     ASSERT((m_set.contains<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject)));
358     decreaseObjectsCount(floatingObject->type());
359     ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
360     if (floatingObject->isPlaced())
361         removePlacedObject(floatingObject);
362     ASSERT(!floatingObject->originatingLine());
363     auto it = m_set.find<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject);
364     if (it == m_set.end())
365         return;
366     m_set.remove(it);
367 }
368
369 void FloatingObjects::computePlacedFloatsTree()
370 {
371     ASSERT(!m_placedFloatsTree.isInitialized());
372     if (m_set.isEmpty())
373         return;
374     m_placedFloatsTree.initIfNeeded(m_renderer.view().intervalArena());
375     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
376         FloatingObject* floatingObject = it->get();
377         if (floatingObject->isPlaced())
378             m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
379     }
380 }
381
382 inline const FloatingObjectTree& FloatingObjects::placedFloatsTree()
383 {
384     if (!m_placedFloatsTree.isInitialized())
385         computePlacedFloatsTree();
386     return m_placedFloatsTree;
387 }
388
389 LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
390 {
391     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
392     placedFloatsTree().allOverlapsWithAdapter(adapter);
393
394     if (heightRemaining)
395         *heightRemaining = adapter.heightRemaining();
396
397     return adapter.offset();
398 }
399
400 LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
401 {
402     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
403     placedFloatsTree().allOverlapsWithAdapter(adapter);
404
405     if (heightRemaining)
406         *heightRemaining = adapter.heightRemaining();
407
408     return std::min(fixedOffset, adapter.offset());
409 }
410
411 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
412 {
413     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
414     placedFloatsTree().allOverlapsWithAdapter(adapter);
415
416     return adapter.offset();
417 }
418
419 LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
420 {
421     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
422     placedFloatsTree().allOverlapsWithAdapter(adapter);
423
424     return std::min(fixedOffset, adapter.offset());
425 }
426
427 template<>
428 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
429 {
430     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
431     if (logicalRight > m_offset) {
432         m_offset = logicalRight;
433         return true;
434     }
435     return false;
436 }
437
438 template<>
439 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
440 {
441     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
442     if (logicalLeft < m_offset) {
443         m_offset = logicalLeft;
444         return true;
445     }
446     return false;
447 }
448
449 template <FloatingObject::Type FloatTypeValue>
450 LayoutUnit ComputeFloatOffsetForFloatLayoutAdapter<FloatTypeValue>::heightRemaining() const
451 {
452     return this->m_outermostFloat ? this->m_renderer.logicalBottomForFloat(this->m_outermostFloat) - this->m_lineTop : LayoutUnit::fromPixel(1);
453 }
454
455 template <FloatingObject::Type FloatTypeValue>
456 inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
457 {
458     const FloatingObject* floatingObject = interval.data();
459     if (floatingObject->type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
460         return;
461
462     // All the objects returned from the tree should be already placed.
463     ASSERT(floatingObject->isPlaced());
464     ASSERT(rangesIntersect(m_renderer.logicalTopForFloat(floatingObject), m_renderer.logicalBottomForFloat(floatingObject), m_lineTop, m_lineBottom));
465
466     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
467     if (floatIsNewExtreme)
468         m_outermostFloat = floatingObject;
469 }
470
471 #if ENABLE(CSS_SHAPES)
472 static inline ShapeOutsideInfo* shapeInfoForFloat(const FloatingObject* floatingObject, const RenderBlockFlow& containingBlock, LayoutUnit lineTop, LayoutUnit lineBottom)
473 {
474     if (floatingObject) {
475         if (ShapeOutsideInfo* shapeOutside = floatingObject->renderer().shapeOutsideInfo()) {
476             shapeOutside->updateDeltasForContainingBlockLine(containingBlock, *floatingObject, lineTop, lineBottom - lineTop);
477             return shapeOutside;
478         }
479     }
480
481     return nullptr;
482 }
483 #endif
484
485 template<>
486 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
487 {
488     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
489 #if ENABLE(CSS_SHAPES)
490     if (ShapeOutsideInfo* shapeOutside = shapeInfoForFloat(floatingObject, m_renderer, m_lineTop, m_lineBottom)) {
491         if (!shapeOutside->lineOverlapsShape())
492             return false;
493
494         logicalRight += shapeOutside->rightMarginBoxDelta();
495     }
496 #endif
497     if (logicalRight > m_offset) {
498         m_offset = logicalRight;
499         return true;
500     }
501
502     return false;
503 }
504
505 template<>
506 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
507 {
508     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
509 #if ENABLE(CSS_SHAPES)
510     if (ShapeOutsideInfo* shapeOutside = shapeInfoForFloat(floatingObject, m_renderer, m_lineTop, m_lineBottom)) {
511         if (!shapeOutside->lineOverlapsShape())
512             return false;
513
514         logicalLeft += shapeOutside->leftMarginBoxDelta();
515     }
516 #endif
517     if (logicalLeft < m_offset) {
518         m_offset = logicalLeft;
519         return true;
520     }
521
522     return false;
523 }
524
525 } // namespace WebCore