7acd5f69291b4f5b4396cf9bcbc743bb79b0a88e
[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     return std::make_unique<FloatingObject>(renderer(), type(), LayoutRect(frameRect().location() - offset, frameRect().size()), shouldPaint, isDescendant);
89 }
90
91 std::unique_ptr<FloatingObject> FloatingObject::unsafeClone() const
92 {
93     // FIXME: Use make_unique here, once we can get it to compile on all platforms we support.
94     std::unique_ptr<FloatingObject> cloneObject(new FloatingObject(renderer(), type(), m_frameRect, m_shouldPaint, m_isDescendant));
95     cloneObject->m_paginationStrut = m_paginationStrut;
96     cloneObject->m_isPlaced = m_isPlaced;
97     return cloneObject;
98 }
99
100 inline static bool rangesIntersect(LayoutUnit floatTop, LayoutUnit floatBottom, LayoutUnit objectTop, LayoutUnit objectBottom)
101 {
102     if (objectTop >= floatBottom || objectBottom < floatTop)
103         return false;
104
105     // The top of the object overlaps the float
106     if (objectTop >= floatTop)
107         return true;
108
109     // The object encloses the float
110     if (objectTop < floatTop && objectBottom > floatBottom)
111         return true;
112
113     // The bottom of the object overlaps the float
114     if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
115         return true;
116
117     return false;
118 }
119
120 template <FloatingObject::Type FloatTypeValue>
121 class ComputeFloatOffsetAdapter {
122 public:
123     typedef FloatingObjectInterval IntervalType;
124
125     ComputeFloatOffsetAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
126         : m_renderer(renderer)
127         , m_lineTop(lineTop)
128         , m_lineBottom(lineBottom)
129         , m_offset(offset)
130         , m_outermostFloat(0)
131     {
132     }
133
134     virtual ~ComputeFloatOffsetAdapter() { }
135
136     LayoutUnit lowValue() const { return m_lineTop; }
137     LayoutUnit highValue() const { return m_lineBottom; }
138     void collectIfNeeded(const IntervalType&);
139
140     LayoutUnit offset() const { return m_offset; }
141
142 protected:
143     virtual bool updateOffsetIfNeeded(const FloatingObject&) = 0;
144
145     const RenderBlockFlow& m_renderer;
146     LayoutUnit m_lineTop;
147     LayoutUnit m_lineBottom;
148     LayoutUnit m_offset;
149     const FloatingObject* m_outermostFloat;
150 };
151
152 template <FloatingObject::Type FloatTypeValue>
153 class ComputeFloatOffsetForFloatLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
154 public:
155     ComputeFloatOffsetForFloatLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
156         : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
157     {
158     }
159
160     virtual ~ComputeFloatOffsetForFloatLayoutAdapter() { }
161
162     LayoutUnit heightRemaining() const;
163
164 protected:
165     bool updateOffsetIfNeeded(const FloatingObject&) final;
166 };
167
168 template <FloatingObject::Type FloatTypeValue>
169 class ComputeFloatOffsetForLineLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
170 public:
171     ComputeFloatOffsetForLineLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
172         : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
173     {
174     }
175
176     virtual ~ComputeFloatOffsetForLineLayoutAdapter() { }
177
178 protected:
179     bool updateOffsetIfNeeded(const FloatingObject&) final;
180 };
181
182 class FindNextFloatLogicalBottomAdapter {
183 public:
184     typedef FloatingObjectInterval IntervalType;
185
186     FindNextFloatLogicalBottomAdapter(const RenderBlockFlow& renderer, LayoutUnit belowLogicalHeight)
187         : m_renderer(renderer)
188         , m_belowLogicalHeight(belowLogicalHeight)
189         , m_aboveLogicalHeight(LayoutUnit::max())
190         , m_nextLogicalBottom(LayoutUnit::max())
191         , m_nextShapeLogicalBottom(LayoutUnit::max())
192     {
193     }
194
195     LayoutUnit lowValue() const { return m_belowLogicalHeight; }
196     LayoutUnit highValue() const { return m_aboveLogicalHeight; }
197     void collectIfNeeded(const IntervalType&);
198
199     LayoutUnit nextLogicalBottom() { return m_nextLogicalBottom == LayoutUnit::max() ? LayoutUnit() : m_nextLogicalBottom; }
200     LayoutUnit nextShapeLogicalBottom() { return m_nextShapeLogicalBottom == LayoutUnit::max() ? nextLogicalBottom() : m_nextShapeLogicalBottom; }
201
202 private:
203     const RenderBlockFlow& m_renderer;
204     LayoutUnit m_belowLogicalHeight;
205     LayoutUnit m_aboveLogicalHeight;
206     LayoutUnit m_nextLogicalBottom;
207     LayoutUnit m_nextShapeLogicalBottom;
208 };
209
210 inline void FindNextFloatLogicalBottomAdapter::collectIfNeeded(const IntervalType& interval)
211 {
212     const auto& floatingObject = *interval.data();
213     if (!rangesIntersect(interval.low(), interval.high(), m_belowLogicalHeight, m_aboveLogicalHeight))
214         return;
215
216     // All the objects returned from the tree should be already placed.
217     ASSERT(floatingObject.isPlaced());
218     ASSERT(rangesIntersect(m_renderer.logicalTopForFloat(floatingObject), m_renderer.logicalBottomForFloat(floatingObject), m_belowLogicalHeight, m_aboveLogicalHeight));
219
220     LayoutUnit floatBottom = m_renderer.logicalBottomForFloat(floatingObject);
221     if (m_nextLogicalBottom < floatBottom)
222         return;
223
224 #if ENABLE(CSS_SHAPES)
225     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
226         LayoutUnit shapeBottom = m_renderer.logicalTopForFloat(floatingObject) + m_renderer.marginBeforeForChild(floatingObject.renderer()) + shapeOutside->shapeLogicalBottom();
227         // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
228         m_nextShapeLogicalBottom = std::min(shapeBottom, floatBottom);
229     } else
230         m_nextShapeLogicalBottom = floatBottom;
231 #endif
232     m_nextLogicalBottom = floatBottom;
233 }
234
235 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelow(LayoutUnit logicalHeight)
236 {
237     FindNextFloatLogicalBottomAdapter adapter(m_renderer, logicalHeight);
238     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
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     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
248         placedFloatsTree->allOverlapsWithAdapter(adapter);
249
250     return adapter.nextLogicalBottom();
251 }
252
253 FloatingObjects::FloatingObjects(const RenderBlockFlow& renderer)
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 = nullptr;
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, WTFMove(*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)
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) {
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(WTFMove(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);
372     if (m_set.isEmpty())
373         return;
374
375     m_placedFloatsTree = std::make_unique<FloatingObjectTree>();
376     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
377         FloatingObject* floatingObject = it->get();
378         if (floatingObject->isPlaced())
379             m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
380     }
381 }
382
383 inline const FloatingObjectTree* FloatingObjects::placedFloatsTree()
384 {
385     if (!m_placedFloatsTree)
386         computePlacedFloatsTree();
387     return m_placedFloatsTree.get();
388 }
389
390 LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
391 {
392     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
393     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
394         placedFloatsTree->allOverlapsWithAdapter(adapter);
395
396     if (heightRemaining)
397         *heightRemaining = adapter.heightRemaining();
398
399     return adapter.offset();
400 }
401
402 LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
403 {
404     ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
405     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
406         placedFloatsTree->allOverlapsWithAdapter(adapter);
407
408     if (heightRemaining)
409         *heightRemaining = adapter.heightRemaining();
410
411     return std::min(fixedOffset, adapter.offset());
412 }
413
414 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
415 {
416     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
417     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
418         placedFloatsTree->allOverlapsWithAdapter(adapter);
419
420     return adapter.offset();
421 }
422
423 LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
424 {
425     ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
426     if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
427         placedFloatsTree->allOverlapsWithAdapter(adapter);
428
429     return std::min(fixedOffset, adapter.offset());
430 }
431
432 template<>
433 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
434 {
435     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
436     if (logicalRight > m_offset) {
437         m_offset = logicalRight;
438         return true;
439     }
440     return false;
441 }
442
443 template<>
444 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
445 {
446     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
447     if (logicalLeft < m_offset) {
448         m_offset = logicalLeft;
449         return true;
450     }
451     return false;
452 }
453
454 template <FloatingObject::Type FloatTypeValue>
455 LayoutUnit ComputeFloatOffsetForFloatLayoutAdapter<FloatTypeValue>::heightRemaining() const
456 {
457     return this->m_outermostFloat ? this->m_renderer.logicalBottomForFloat(*this->m_outermostFloat) - this->m_lineTop : LayoutUnit::fromPixel(1);
458 }
459
460 template <FloatingObject::Type FloatTypeValue>
461 inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
462 {
463     const auto& floatingObject = *interval.data();
464     if (floatingObject.type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
465         return;
466
467     // All the objects returned from the tree should be already placed.
468     ASSERT(floatingObject.isPlaced());
469     ASSERT(rangesIntersect(m_renderer.logicalTopForFloat(floatingObject), m_renderer.logicalBottomForFloat(floatingObject), m_lineTop, m_lineBottom));
470
471     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
472     if (floatIsNewExtreme)
473         m_outermostFloat = &floatingObject;
474 }
475
476 template<>
477 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
478 {
479     LayoutUnit logicalRight = m_renderer.logicalRightForFloat(floatingObject);
480 #if ENABLE(CSS_SHAPES)
481     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
482         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
483         if (!shapeDeltas.lineOverlapsShape())
484             return false;
485
486         logicalRight += shapeDeltas.rightMarginBoxDelta();
487     }
488 #endif
489     if (logicalRight > m_offset) {
490         m_offset = logicalRight;
491         return true;
492     }
493
494     return false;
495 }
496
497 template<>
498 inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
499 {
500     LayoutUnit logicalLeft = m_renderer.logicalLeftForFloat(floatingObject);
501 #if ENABLE(CSS_SHAPES)
502     if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
503         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
504         if (!shapeDeltas.lineOverlapsShape())
505             return false;
506
507         logicalLeft += shapeDeltas.leftMarginBoxDelta();
508     }
509 #endif
510     if (logicalLeft < m_offset) {
511         m_offset = logicalLeft;
512         return true;
513     }
514
515     return false;
516 }
517
518 } // namespace WebCore