Replace WTF::move with WTFMove
[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 auto& 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     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
240         placedFloatsTree->allOverlapsWithAdapter(adapter);
241
242     return adapter.nextShapeLogicalBottom();
243 }
244
245 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelowForBlock(LayoutUnit logicalHeight)
246 {
247     FindNextFloatLogicalBottomAdapter adapter(m_renderer, logicalHeight);
248     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
249         placedFloatsTree->allOverlapsWithAdapter(adapter);
250
251     return adapter.nextLogicalBottom();
252 }
253
254 FloatingObjects::FloatingObjects(const RenderBlockFlow& renderer)
255     : m_leftObjectsCount(0)
256     , m_rightObjectsCount(0)
257     , m_horizontalWritingMode(renderer.isHorizontalWritingMode())
258     , m_renderer(renderer)
259 {
260 }
261
262 FloatingObjects::~FloatingObjects()
263 {
264 }
265
266 void FloatingObjects::clearLineBoxTreePointers()
267 {
268     // Clear references to originating lines, since the lines are being deleted
269     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
270         ASSERT(!((*it)->originatingLine()) || &((*it)->originatingLine()->renderer()) == &m_renderer);
271         (*it)->setOriginatingLine(0);
272     }
273 }
274
275 void FloatingObjects::clear()
276 {
277     m_set.clear();
278     m_placedFloatsTree = nullptr;
279     m_leftObjectsCount = 0;
280     m_rightObjectsCount = 0;
281 }
282
283 void FloatingObjects::moveAllToFloatInfoMap(RendererToFloatInfoMap& map)
284 {
285     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
286         auto& renderer = it->get()->renderer();
287         // FIXME: The only reason it is safe to move these out of the set is that
288         // we are about to clear it. Otherwise it would break the hash table invariant.
289         // A clean way to do this would be to add a takeAll function to HashSet.
290         map.add(&renderer, WTFMove(*it));
291     }
292     clear();
293 }
294
295 void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
296 {
297     if (type == FloatingObject::FloatLeft)
298         m_leftObjectsCount++;
299     else
300         m_rightObjectsCount++;
301 }
302
303 void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
304 {
305     if (type == FloatingObject::FloatLeft)
306         m_leftObjectsCount--;
307     else
308         m_rightObjectsCount--;
309 }
310
311 FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
312 {
313     // FIXME The endpoints of the floating object interval shouldn't need to be
314     // floored. See http://wkb.ug/125831 for more details.
315     if (m_horizontalWritingMode)
316         return FloatingObjectInterval(floatingObject->frameRect().y().floor(), floatingObject->frameRect().maxY().floor(), floatingObject);
317     return FloatingObjectInterval(floatingObject->frameRect().x().floor(), floatingObject->frameRect().maxX().floor(), floatingObject);
318 }
319
320 void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
321 {
322     ASSERT(!floatingObject->isInPlacedTree());
323
324     floatingObject->setIsPlaced(true);
325     if (m_placedFloatsTree)
326         m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
327
328 #ifndef NDEBUG
329     floatingObject->setIsInPlacedTree(true);
330 #endif
331 }
332
333 void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
334 {
335     ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
336
337     if (m_placedFloatsTree) {
338         bool removed = m_placedFloatsTree->remove(intervalForFloatingObject(floatingObject));
339         ASSERT_UNUSED(removed, removed);
340     }
341
342     floatingObject->setIsPlaced(false);
343 #ifndef NDEBUG
344     floatingObject->setIsInPlacedTree(false);
345 #endif
346 }
347
348 FloatingObject* FloatingObjects::add(std::unique_ptr<FloatingObject> floatingObject)
349 {
350     increaseObjectsCount(floatingObject->type());
351     if (floatingObject->isPlaced())
352         addPlacedObject(floatingObject.get());
353     return m_set.add(WTFMove(floatingObject)).iterator->get();
354 }
355
356 void FloatingObjects::remove(FloatingObject* floatingObject)
357 {
358     ASSERT((m_set.contains<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject)));
359     decreaseObjectsCount(floatingObject->type());
360     ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
361     if (floatingObject->isPlaced())
362         removePlacedObject(floatingObject);
363     ASSERT(!floatingObject->originatingLine());
364     auto it = m_set.find<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject);
365     if (it == m_set.end())
366         return;
367     m_set.remove(it);
368 }
369
370 void FloatingObjects::computePlacedFloatsTree()
371 {
372     ASSERT(!m_placedFloatsTree);
373     if (m_set.isEmpty())
374         return;
375
376     m_placedFloatsTree = std::make_unique<FloatingObjectTree>();
377     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
378         FloatingObject* floatingObject = it->get();
379         if (floatingObject->isPlaced())
380             m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
381     }
382 }
383
384 inline const FloatingObjectTree* FloatingObjects::placedFloatsTree()
385 {
386     if (!m_placedFloatsTree)
387         computePlacedFloatsTree();
388     return m_placedFloatsTree.get();
389 }
390
391 LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
392 {
393     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
394     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
395         placedFloatsTree->allOverlapsWithAdapter(adapter);
396
397     if (heightRemaining)
398         *heightRemaining = adapter.heightRemaining();
399
400     return adapter.offset();
401 }
402
403 LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
404 {
405     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
406     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
407         placedFloatsTree->allOverlapsWithAdapter(adapter);
408
409     if (heightRemaining)
410         *heightRemaining = adapter.heightRemaining();
411
412     return std::min(fixedOffset, adapter.offset());
413 }
414
415 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
416 {
417     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
418     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
419         placedFloatsTree->allOverlapsWithAdapter(adapter);
420
421     return adapter.offset();
422 }
423
424 LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
425 {
426     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
427     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
428         placedFloatsTree->allOverlapsWithAdapter(adapter);
429
430     return std::min(fixedOffset, adapter.offset());
431 }
432
433 template<>
434 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
435 {
436     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
437     if (logicalRight > m_offset) {
438         m_offset = logicalRight;
439         return true;
440     }
441     return false;
442 }
443
444 template<>
445 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
446 {
447     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
448     if (logicalLeft < m_offset) {
449         m_offset = logicalLeft;
450         return true;
451     }
452     return false;
453 }
454
455 template <FloatingObject::Type FloatTypeValue>
456 LayoutUnit ComputeFloatOffsetForFloatLayoutAdapter<FloatTypeValue>::heightRemaining() const
457 {
458     return this->m_outermostFloat ? this->m_renderer.logicalBottomForFloat(*this->m_outermostFloat) - this->m_lineTop : LayoutUnit::fromPixel(1);
459 }
460
461 template <FloatingObject::Type FloatTypeValue>
462 inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
463 {
464     const auto& floatingObject = *interval.data();
465     if (floatingObject.type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
466         return;
467
468     // All the objects returned from the tree should be already placed.
469     ASSERT(floatingObject.isPlaced());
470     ASSERT(rangesIntersect(m_renderer.logicalTopForFloat(floatingObject), m_renderer.logicalBottomForFloat(floatingObject), m_lineTop, m_lineBottom));
471
472     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
473     if (floatIsNewExtreme)
474         m_outermostFloat = &floatingObject;
475 }
476
477 template<>
478 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
479 {
480     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
481 #if ENABLE(CSS_SHAPES)
482     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
483         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
484         if (!shapeDeltas.lineOverlapsShape())
485             return false;
486
487         logicalRight += shapeDeltas.rightMarginBoxDelta();
488     }
489 #endif
490     if (logicalRight > m_offset) {
491         m_offset = logicalRight;
492         return true;
493     }
494
495     return false;
496 }
497
498 template<>
499 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
500 {
501     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
502 #if ENABLE(CSS_SHAPES)
503     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
504         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
505         if (!shapeDeltas.lineOverlapsShape())
506             return false;
507
508         logicalLeft += shapeDeltas.leftMarginBoxDelta();
509     }
510 #endif
511     if (logicalLeft < m_offset) {
512         m_offset = logicalLeft;
513         return true;
514     }
515
516     return false;
517 }
518
519 } // namespace WebCore