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