de28d67dd4b382083fccb543ce70db78f7797e52
[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(makeWeakPtr(renderer))
47     , m_shouldPaint(true)
48     , m_isDescendant(false)
49     , m_isPlaced(false)
50 #ifndef NDEBUG
51     , m_isInPlacedTree(false)
52 #endif
53 {
54     Float type = renderer.style().floating();
55     ASSERT(type != Float::No);
56     if (type == Float::Left)
57         m_type = FloatLeft;
58     else if (type == Float::Right)
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(makeWeakPtr(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(makeWeakPtr(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     WeakPtr<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(makeWeakPtr(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     WeakPtr<const RenderBlockFlow> m_renderer;
203     LayoutUnit m_belowLogicalHeight;
204     Optional<LayoutUnit> m_nextLogicalBottom;
205     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(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(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(makeWeakPtr(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()) == &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)));
352     decreaseObjectsCount(floatingObject->type());
353     ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
354     if (floatingObject->isPlaced())
355         removePlacedObject(floatingObject);
356     ASSERT(!floatingObject->originatingLine());
357     m_set.remove(floatingObject);
358 }
359
360 void FloatingObjects::computePlacedFloatsTree()
361 {
362     ASSERT(!m_placedFloatsTree);
363     if (m_set.isEmpty())
364         return;
365
366     m_placedFloatsTree = std::make_unique<FloatingObjectTree>();
367     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
368         FloatingObject* floatingObject = it->get();
369         if (floatingObject->isPlaced())
370             m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
371     }
372 }
373
374 inline const FloatingObjectTree* FloatingObjects::placedFloatsTree()
375 {
376     if (!m_placedFloatsTree)
377         computePlacedFloatsTree();
378     return m_placedFloatsTree.get();
379 }
380
381 LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
382 {
383     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(renderer(), logicalTop, logicalTop, fixedOffset);
384     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
385         placedFloatsTree->allOverlapsWithAdapter(adapter);
386
387     if (heightRemaining)
388         *heightRemaining = adapter.heightRemaining();
389
390     return adapter.offset();
391 }
392
393 LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
394 {
395     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(renderer(), logicalTop, logicalTop, fixedOffset);
396     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
397         placedFloatsTree->allOverlapsWithAdapter(adapter);
398
399     if (heightRemaining)
400         *heightRemaining = adapter.heightRemaining();
401
402     return std::min(fixedOffset, adapter.offset());
403 }
404
405 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
406 {
407     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(renderer(), logicalTop, logicalTop + logicalHeight, fixedOffset);
408     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
409         placedFloatsTree->allOverlapsWithAdapter(adapter);
410
411     return adapter.offset();
412 }
413
414 LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
415 {
416     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(renderer(), logicalTop, logicalTop + logicalHeight, fixedOffset);
417     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
418         placedFloatsTree->allOverlapsWithAdapter(adapter);
419
420     return std::min(fixedOffset, adapter.offset());
421 }
422
423 template<>
424 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
425 {
426     LayoutUnit logicalRight = m_renderer->logicalRightForFloat(floatingObject);
427     if (logicalRight > m_offset) {
428         m_offset = logicalRight;
429         return true;
430     }
431     return false;
432 }
433
434 template<>
435 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
436 {
437     LayoutUnit logicalLeft = m_renderer->logicalLeftForFloat(floatingObject);
438     if (logicalLeft < m_offset) {
439         m_offset = logicalLeft;
440         return true;
441     }
442     return false;
443 }
444
445 template <FloatingObject::Type FloatTypeValue>
446 LayoutUnit ComputeFloatOffsetForFloatLayoutAdapter<FloatTypeValue>::heightRemaining() const
447 {
448     return this->m_outermostFloat ? this->m_renderer->logicalBottomForFloat(*this->m_outermostFloat) - this->m_lineTop : 1_lu;
449 }
450
451 template <FloatingObject::Type FloatTypeValue>
452 inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
453 {
454     const auto& floatingObject = *interval.data();
455     if (floatingObject.type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
456         return;
457
458     // All the objects returned from the tree should be already placed.
459     ASSERT(floatingObject.isPlaced());
460     ASSERT(rangesIntersect(m_renderer->logicalTopForFloat(floatingObject), m_renderer->logicalBottomForFloat(floatingObject), m_lineTop, m_lineBottom));
461
462     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
463     if (floatIsNewExtreme)
464         m_outermostFloat = &floatingObject;
465 }
466
467 template<>
468 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
469 {
470     LayoutUnit logicalRight = m_renderer->logicalRightForFloat(floatingObject);
471     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
472         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
473         if (!shapeDeltas.lineOverlapsShape())
474             return false;
475
476         logicalRight += shapeDeltas.rightMarginBoxDelta();
477     }
478     if (logicalRight > m_offset) {
479         m_offset = logicalRight;
480         return true;
481     }
482
483     return false;
484 }
485
486 template<>
487 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
488 {
489     LayoutUnit logicalLeft = m_renderer->logicalLeftForFloat(floatingObject);
490     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
491         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
492         if (!shapeDeltas.lineOverlapsShape())
493             return false;
494
495         logicalLeft += shapeDeltas.leftMarginBoxDelta();
496     }
497     if (logicalLeft < m_offset) {
498         m_offset = logicalLeft;
499         return true;
500     }
501
502     return false;
503 }
504
505 } // namespace WebCore