FloatingObject should not hold a raw pointer to RootInlineBox.
[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     LayoutSize size;
40     uint32_t bitfields : 8;
41 };
42
43 COMPILE_ASSERT(sizeof(FloatingObject) == sizeof(SameSizeAsFloatingObject), FloatingObject_should_stay_small);
44
45 FloatingObject::FloatingObject(RenderBox& renderer)
46     : m_renderer(renderer)
47     , m_shouldPaint(true)
48     , m_isDescendant(false)
49     , m_isPlaced(false)
50 #ifndef NDEBUG
51     , m_isInPlacedTree(false)
52 #endif
53 {
54     EFloat type = renderer.style().floating();
55     ASSERT(type != NoFloat);
56     if (type == LeftFloat)
57         m_type = FloatLeft;
58     else if (type == RightFloat)
59         m_type = FloatRight;
60 }
61
62 FloatingObject::FloatingObject(RenderBox& renderer, Type type, const LayoutRect& frameRect, const LayoutSize& marginOffset, bool shouldPaint, bool isDescendant)
63     : m_renderer(renderer)
64     , m_frameRect(frameRect)
65     , m_marginOffset(marginOffset)
66     , m_type(type)
67     , m_shouldPaint(shouldPaint)
68     , m_isDescendant(isDescendant)
69     , m_isPlaced(true)
70 #ifndef NDEBUG
71     , m_isInPlacedTree(false)
72 #endif
73 {
74 }
75
76 std::unique_ptr<FloatingObject> FloatingObject::create(RenderBox& renderer)
77 {
78     auto object = std::make_unique<FloatingObject>(renderer);
79     object->setShouldPaint(!renderer.hasSelfPaintingLayer()); // If a layer exists, the float will paint itself. Otherwise someone else will.
80     object->setIsDescendant(true);
81     return object;
82 }
83
84 std::unique_ptr<FloatingObject> FloatingObject::copyToNewContainer(LayoutSize offset, bool shouldPaint, bool isDescendant) const
85 {
86     return std::make_unique<FloatingObject>(renderer(), type(), LayoutRect(frameRect().location() - offset, frameRect().size()), marginOffset(), shouldPaint, isDescendant);
87 }
88
89 std::unique_ptr<FloatingObject> FloatingObject::cloneForNewParent() const
90 {
91     auto cloneObject = std::make_unique<FloatingObject>(renderer(), type(), m_frameRect, m_marginOffset, m_shouldPaint, m_isDescendant);
92     cloneObject->m_paginationStrut = m_paginationStrut;
93     cloneObject->m_isPlaced = m_isPlaced;
94     return cloneObject;
95 }
96
97 LayoutSize FloatingObject::translationOffsetToAncestor() const
98 {
99     return locationOffsetOfBorderBox() - renderer().locationOffset();
100 }
101
102 inline static bool rangesIntersect(LayoutUnit floatTop, LayoutUnit floatBottom, LayoutUnit objectTop, LayoutUnit 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(lineTop)
130         , m_lineBottom(lineBottom)
131         , m_offset(offset)
132         , m_outermostFloat(0)
133     {
134     }
135
136     virtual ~ComputeFloatOffsetAdapter() { }
137
138     LayoutUnit lowValue() const { return m_lineTop; }
139     LayoutUnit highValue() const { return m_lineBottom; }
140     void collectIfNeeded(const IntervalType&);
141
142     LayoutUnit offset() const { return m_offset; }
143
144 protected:
145     virtual bool updateOffsetIfNeeded(const FloatingObject&) = 0;
146
147     const RenderBlockFlow& m_renderer;
148     LayoutUnit m_lineTop;
149     LayoutUnit m_lineBottom;
150     LayoutUnit m_offset;
151     const FloatingObject* m_outermostFloat;
152 };
153
154 template <FloatingObject::Type FloatTypeValue>
155 class ComputeFloatOffsetForFloatLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
156 public:
157     ComputeFloatOffsetForFloatLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
158         : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
159     {
160     }
161
162     virtual ~ComputeFloatOffsetForFloatLayoutAdapter() { }
163
164     LayoutUnit heightRemaining() const;
165
166 protected:
167     bool updateOffsetIfNeeded(const FloatingObject&) final;
168 };
169
170 template <FloatingObject::Type FloatTypeValue>
171 class ComputeFloatOffsetForLineLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
172 public:
173     ComputeFloatOffsetForLineLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
174         : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
175     {
176     }
177
178     virtual ~ComputeFloatOffsetForLineLayoutAdapter() { }
179
180 protected:
181     bool updateOffsetIfNeeded(const FloatingObject&) final;
182 };
183
184 class FindNextFloatLogicalBottomAdapter {
185 public:
186     typedef FloatingObjectInterval IntervalType;
187
188     FindNextFloatLogicalBottomAdapter(const RenderBlockFlow& renderer, LayoutUnit belowLogicalHeight)
189         : m_renderer(renderer)
190         , m_belowLogicalHeight(belowLogicalHeight)
191     {
192     }
193
194     LayoutUnit lowValue() const { return m_belowLogicalHeight; }
195     LayoutUnit highValue() const { return LayoutUnit::max(); }
196     void collectIfNeeded(const IntervalType&);
197
198     LayoutUnit nextLogicalBottom() const { return m_nextLogicalBottom.value_or(0); }
199     LayoutUnit nextShapeLogicalBottom() const { return m_nextShapeLogicalBottom.value_or(nextLogicalBottom()); }
200
201 private:
202     const RenderBlockFlow& m_renderer;
203     LayoutUnit m_belowLogicalHeight;
204     std::optional<LayoutUnit> m_nextLogicalBottom;
205     std::optional<LayoutUnit> m_nextShapeLogicalBottom;
206 };
207
208 inline void FindNextFloatLogicalBottomAdapter::collectIfNeeded(const IntervalType& interval)
209 {
210     const auto& floatingObject = *interval.data();
211     if (!rangesIntersect(interval.low(), interval.high(), m_belowLogicalHeight, LayoutUnit::max()))
212         return;
213
214     // All the objects returned from the tree should be already placed.
215     ASSERT(floatingObject.isPlaced());
216     ASSERT(rangesIntersect(m_renderer.logicalTopForFloat(floatingObject), m_renderer.logicalBottomForFloat(floatingObject), m_belowLogicalHeight, LayoutUnit::max()));
217
218     LayoutUnit floatBottom = m_renderer.logicalBottomForFloat(floatingObject);
219     if (m_nextLogicalBottom && m_nextLogicalBottom.value() < floatBottom)
220         return;
221
222     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
223         LayoutUnit shapeBottom = m_renderer.logicalTopForFloat(floatingObject) + m_renderer.marginBeforeForChild(floatingObject.renderer()) + shapeOutside->shapeLogicalBottom();
224         // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
225         m_nextShapeLogicalBottom = std::min(shapeBottom, floatBottom);
226     } else
227         m_nextShapeLogicalBottom = floatBottom;
228     m_nextLogicalBottom = floatBottom;
229 }
230
231 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelow(LayoutUnit logicalHeight)
232 {
233     FindNextFloatLogicalBottomAdapter adapter(m_renderer, logicalHeight);
234     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
235         placedFloatsTree->allOverlapsWithAdapter(adapter);
236
237     return adapter.nextShapeLogicalBottom();
238 }
239
240 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelowForBlock(LayoutUnit logicalHeight)
241 {
242     FindNextFloatLogicalBottomAdapter adapter(m_renderer, logicalHeight);
243     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
244         placedFloatsTree->allOverlapsWithAdapter(adapter);
245
246     return adapter.nextLogicalBottom();
247 }
248
249 FloatingObjects::FloatingObjects(const RenderBlockFlow& renderer)
250     : m_leftObjectsCount(0)
251     , m_rightObjectsCount(0)
252     , m_horizontalWritingMode(renderer.isHorizontalWritingMode())
253     , m_renderer(renderer)
254 {
255 }
256
257 FloatingObjects::~FloatingObjects()
258 {
259 }
260
261 void FloatingObjects::clearLineBoxTreePointers()
262 {
263     // Clear references to originating lines, since the lines are being deleted
264     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
265         ASSERT(!((*it)->originatingLine()) || &((*it)->originatingLine()->renderer()) == &m_renderer);
266         (*it)->clearOriginatingLine();
267     }
268 }
269
270 void FloatingObjects::clear()
271 {
272     m_set.clear();
273     m_placedFloatsTree = nullptr;
274     m_leftObjectsCount = 0;
275     m_rightObjectsCount = 0;
276 }
277
278 void FloatingObjects::moveAllToFloatInfoMap(RendererToFloatInfoMap& map)
279 {
280     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
281         auto& renderer = it->get()->renderer();
282         // FIXME: The only reason it is safe to move these out of the set is that
283         // we are about to clear it. Otherwise it would break the hash table invariant.
284         // A clean way to do this would be to add a takeAll function to HashSet.
285         map.add(&renderer, WTFMove(*it));
286     }
287     clear();
288 }
289
290 void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
291 {
292     if (type == FloatingObject::FloatLeft)
293         m_leftObjectsCount++;
294     else
295         m_rightObjectsCount++;
296 }
297
298 void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
299 {
300     if (type == FloatingObject::FloatLeft)
301         m_leftObjectsCount--;
302     else
303         m_rightObjectsCount--;
304 }
305
306 FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
307 {
308     // FIXME The endpoints of the floating object interval shouldn't need to be
309     // floored. See http://wkb.ug/125831 for more details.
310     if (m_horizontalWritingMode)
311         return FloatingObjectInterval(floatingObject->frameRect().y().floor(), floatingObject->frameRect().maxY().floor(), floatingObject);
312     return FloatingObjectInterval(floatingObject->frameRect().x().floor(), floatingObject->frameRect().maxX().floor(), floatingObject);
313 }
314
315 void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
316 {
317     ASSERT(!floatingObject->isInPlacedTree());
318
319     floatingObject->setIsPlaced(true);
320     if (m_placedFloatsTree)
321         m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
322
323 #ifndef NDEBUG
324     floatingObject->setIsInPlacedTree(true);
325 #endif
326 }
327
328 void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
329 {
330     ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
331
332     if (m_placedFloatsTree) {
333         bool removed = m_placedFloatsTree->remove(intervalForFloatingObject(floatingObject));
334         ASSERT_UNUSED(removed, removed);
335     }
336
337     floatingObject->setIsPlaced(false);
338 #ifndef NDEBUG
339     floatingObject->setIsInPlacedTree(false);
340 #endif
341 }
342
343 FloatingObject* FloatingObjects::add(std::unique_ptr<FloatingObject> floatingObject)
344 {
345     increaseObjectsCount(floatingObject->type());
346     if (floatingObject->isPlaced())
347         addPlacedObject(floatingObject.get());
348     return m_set.add(WTFMove(floatingObject)).iterator->get();
349 }
350
351 void FloatingObjects::remove(FloatingObject* floatingObject)
352 {
353     ASSERT((m_set.contains<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject)));
354     decreaseObjectsCount(floatingObject->type());
355     ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
356     if (floatingObject->isPlaced())
357         removePlacedObject(floatingObject);
358     ASSERT(!floatingObject->originatingLine());
359     auto it = m_set.find<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject);
360     if (it == m_set.end())
361         return;
362     m_set.remove(it);
363 }
364
365 void FloatingObjects::computePlacedFloatsTree()
366 {
367     ASSERT(!m_placedFloatsTree);
368     if (m_set.isEmpty())
369         return;
370
371     m_placedFloatsTree = std::make_unique<FloatingObjectTree>();
372     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
373         FloatingObject* floatingObject = it->get();
374         if (floatingObject->isPlaced())
375             m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
376     }
377 }
378
379 inline const FloatingObjectTree* FloatingObjects::placedFloatsTree()
380 {
381     if (!m_placedFloatsTree)
382         computePlacedFloatsTree();
383     return m_placedFloatsTree.get();
384 }
385
386 LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
387 {
388     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
389     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
390         placedFloatsTree->allOverlapsWithAdapter(adapter);
391
392     if (heightRemaining)
393         *heightRemaining = adapter.heightRemaining();
394
395     return adapter.offset();
396 }
397
398 LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
399 {
400     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
401     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
402         placedFloatsTree->allOverlapsWithAdapter(adapter);
403
404     if (heightRemaining)
405         *heightRemaining = adapter.heightRemaining();
406
407     return std::min(fixedOffset, adapter.offset());
408 }
409
410 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
411 {
412     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
413     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
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     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
423         placedFloatsTree->allOverlapsWithAdapter(adapter);
424
425     return std::min(fixedOffset, adapter.offset());
426 }
427
428 template<>
429 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
430 {
431     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
432     if (logicalRight > m_offset) {
433         m_offset = logicalRight;
434         return true;
435     }
436     return false;
437 }
438
439 template<>
440 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
441 {
442     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
443     if (logicalLeft < m_offset) {
444         m_offset = logicalLeft;
445         return true;
446     }
447     return false;
448 }
449
450 template <FloatingObject::Type FloatTypeValue>
451 LayoutUnit ComputeFloatOffsetForFloatLayoutAdapter<FloatTypeValue>::heightRemaining() const
452 {
453     return this->m_outermostFloat ? this->m_renderer.logicalBottomForFloat(*this->m_outermostFloat) - this->m_lineTop : LayoutUnit::fromPixel(1);
454 }
455
456 template <FloatingObject::Type FloatTypeValue>
457 inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
458 {
459     const auto& floatingObject = *interval.data();
460     if (floatingObject.type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
461         return;
462
463     // All the objects returned from the tree should be already placed.
464     ASSERT(floatingObject.isPlaced());
465     ASSERT(rangesIntersect(m_renderer.logicalTopForFloat(floatingObject), m_renderer.logicalBottomForFloat(floatingObject), m_lineTop, m_lineBottom));
466
467     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
468     if (floatIsNewExtreme)
469         m_outermostFloat = &floatingObject;
470 }
471
472 template<>
473 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
474 {
475     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
476     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
477         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
478         if (!shapeDeltas.lineOverlapsShape())
479             return false;
480
481         logicalRight += shapeDeltas.rightMarginBoxDelta();
482     }
483     if (logicalRight > m_offset) {
484         m_offset = logicalRight;
485         return true;
486     }
487
488     return false;
489 }
490
491 template<>
492 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
493 {
494     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
495     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
496         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
497         if (!shapeDeltas.lineOverlapsShape())
498             return false;
499
500         logicalLeft += shapeDeltas.leftMarginBoxDelta();
501     }
502     if (logicalLeft < m_offset) {
503         m_offset = logicalLeft;
504         return true;
505     }
506
507     return false;
508 }
509
510 } // namespace WebCore