4a04ade5f0f15bdadebe16de1d053e1e678fd3a4
[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 std;
32 using namespace WTF;
33
34 namespace WebCore {
35
36 struct SameSizeAsFloatingObject {
37     void* pointers[2];
38     LayoutRect rect;
39     int paginationStrut;
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_originatingLine(nullptr)
48     , m_paginationStrut(0)
49     , m_shouldPaint(true)
50     , m_isDescendant(false)
51     , m_isPlaced(false)
52 #ifndef NDEBUG
53     , m_isInPlacedTree(false)
54 #endif
55 {
56     EFloat type = renderer.style().floating();
57     ASSERT(type != NoFloat);
58     if (type == LeftFloat)
59         m_type = FloatLeft;
60     else if (type == RightFloat)
61         m_type = FloatRight;
62 }
63
64 FloatingObject::FloatingObject(RenderBox& renderer, Type type, const LayoutRect& frameRect, bool shouldPaint, bool isDescendant)
65     : m_renderer(renderer)
66     , m_originatingLine(nullptr)
67     , m_frameRect(frameRect)
68     , m_paginationStrut(0)
69     , m_type(type)
70     , m_shouldPaint(shouldPaint)
71     , m_isDescendant(isDescendant)
72     , m_isPlaced(true)
73 #ifndef NDEBUG
74     , m_isInPlacedTree(false)
75 #endif
76 {
77 }
78
79 std::unique_ptr<FloatingObject> FloatingObject::create(RenderBox& renderer)
80 {
81     auto object = std::make_unique<FloatingObject>(renderer);
82     object->setShouldPaint(!renderer.hasSelfPaintingLayer()); // If a layer exists, the float will paint itself. Otherwise someone else will.
83     object->setIsDescendant(true);
84     return object;
85 }
86
87 std::unique_ptr<FloatingObject> FloatingObject::copyToNewContainer(LayoutSize offset, bool shouldPaint, bool isDescendant) const
88 {
89     // FIXME: Use make_unique here, once we can get it to compile on all platforms we support.
90     return std::unique_ptr<FloatingObject>(new FloatingObject(renderer(), type(), LayoutRect(frameRect().location() - offset, frameRect().size()), shouldPaint, isDescendant));
91 }
92
93 std::unique_ptr<FloatingObject> FloatingObject::unsafeClone() const
94 {
95     // FIXME: Use make_unique here, once we can get it to compile on all platforms we support.
96     std::unique_ptr<FloatingObject> cloneObject(new FloatingObject(renderer(), type(), m_frameRect, m_shouldPaint, m_isDescendant));
97     cloneObject->m_originatingLine = m_originatingLine;
98     cloneObject->m_paginationStrut = m_paginationStrut;
99     cloneObject->m_isPlaced = m_isPlaced;
100     return cloneObject;
101 }
102
103 inline static bool rangesIntersect(int floatTop, int floatBottom, int objectTop, int objectBottom)
104 {
105     if (objectTop >= floatBottom || objectBottom < floatTop)
106         return false;
107
108     // The top of the object overlaps the float
109     if (objectTop >= floatTop)
110         return true;
111
112     // The object encloses the float
113     if (objectTop < floatTop && objectBottom > floatBottom)
114         return true;
115
116     // The bottom of the object overlaps the float
117     if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
118         return true;
119
120     return false;
121 }
122
123 template <FloatingObject::Type FloatTypeValue>
124 class ComputeFloatOffsetAdapter {
125 public:
126     typedef FloatingObjectInterval IntervalType;
127
128     ComputeFloatOffsetAdapter(const RenderBlockFlow* renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
129         : m_renderer(renderer)
130         , m_lineTop(roundToInt(lineTop))
131         , m_lineBottom(roundToInt(lineBottom))
132         , m_offset(offset)
133         , m_outermostFloat(0)
134     {
135     }
136
137     int lowValue() const { return m_lineTop; }
138     int highValue() const { return m_lineBottom; }
139     void collectIfNeeded(const IntervalType&);
140
141     LayoutUnit offset() const { return m_offset; }
142     LayoutUnit shapeOffset() const;
143     LayoutUnit heightRemaining() const;
144
145 private:
146     bool updateOffsetIfNeeded(const FloatingObject*);
147
148     const RenderBlockFlow* m_renderer;
149     int m_lineTop;
150     int m_lineBottom;
151     LayoutUnit m_offset;
152     const FloatingObject* m_outermostFloat;
153 };
154
155 class FindNextFloatLogicalBottomAdapter {
156 public:
157     typedef FloatingObjectInterval IntervalType;
158
159     FindNextFloatLogicalBottomAdapter(const RenderBlockFlow& renderer, LayoutUnit belowLogicalHeight)
160         : m_renderer(renderer)
161         , m_belowLogicalHeight(floorToInt(belowLogicalHeight))
162         , m_aboveLogicalHeight(roundToInt(LayoutUnit::max()))
163         , m_nextLogicalBottom(LayoutUnit::max())
164         , m_nextShapeLogicalBottom(LayoutUnit::max())
165     {
166     }
167
168     int lowValue() const { return m_belowLogicalHeight; }
169     int highValue() const { return m_aboveLogicalHeight; }
170     void collectIfNeeded(const IntervalType&);
171
172     LayoutUnit nextLogicalBottom() { return m_nextLogicalBottom == LayoutUnit::max() ? LayoutUnit() : m_nextLogicalBottom; }
173     LayoutUnit nextShapeLogicalBottom() { return m_nextShapeLogicalBottom == LayoutUnit::max() ? nextLogicalBottom() : m_nextShapeLogicalBottom; }
174
175 private:
176     const RenderBlockFlow& m_renderer;
177     int m_belowLogicalHeight;
178     int m_aboveLogicalHeight;
179     LayoutUnit m_nextLogicalBottom;
180     LayoutUnit m_nextShapeLogicalBottom;
181 };
182
183 inline void FindNextFloatLogicalBottomAdapter::collectIfNeeded(const IntervalType& interval)
184 {
185     const FloatingObject* floatingObject = interval.data();
186     if (!rangesIntersect(interval.low(), interval.high(), m_belowLogicalHeight, m_aboveLogicalHeight))
187         return;
188
189     // All the objects returned from the tree should be already placed.
190     ASSERT(floatingObject->isPlaced());
191     ASSERT(rangesIntersect(m_renderer.pixelSnappedLogicalTopForFloat(floatingObject), m_renderer.pixelSnappedLogicalBottomForFloat(floatingObject), m_belowLogicalHeight, m_aboveLogicalHeight));
192
193     LayoutUnit floatBottom = m_renderer.logicalBottomForFloat(floatingObject);
194     if (m_nextLogicalBottom < floatBottom)
195         return;
196
197 #if ENABLE(CSS_SHAPES)
198     if (ShapeOutsideInfo* shapeOutside = floatingObject->renderer().shapeOutsideInfo()) {
199         LayoutUnit shapeBottom = m_renderer.logicalTopForFloat(floatingObject) + m_renderer.marginBeforeForChild(floatingObject->renderer()) + shapeOutside->shapeLogicalBottom();
200         // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
201         m_nextShapeLogicalBottom = min(shapeBottom, floatBottom);
202     } else
203         m_nextShapeLogicalBottom = floatBottom;
204 #endif
205     m_nextLogicalBottom = floatBottom;
206 }
207
208 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelow(LayoutUnit logicalHeight)
209 {
210     FindNextFloatLogicalBottomAdapter adapter(*m_renderer, logicalHeight);
211     placedFloatsTree().allOverlapsWithAdapter(adapter);
212
213     return adapter.nextShapeLogicalBottom();
214 }
215
216 LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelowForBlock(LayoutUnit logicalHeight)
217 {
218     FindNextFloatLogicalBottomAdapter adapter(*m_renderer, logicalHeight);
219     placedFloatsTree().allOverlapsWithAdapter(adapter);
220
221     return adapter.nextLogicalBottom();
222 }
223
224 FloatingObjects::FloatingObjects(const RenderBlockFlow* renderer, bool horizontalWritingMode)
225     : m_placedFloatsTree(UninitializedTree)
226     , m_leftObjectsCount(0)
227     , m_rightObjectsCount(0)
228     , m_horizontalWritingMode(horizontalWritingMode)
229     , m_renderer(renderer)
230 {
231 }
232
233 FloatingObjects::~FloatingObjects()
234 {
235 }
236
237 void FloatingObjects::clearLineBoxTreePointers()
238 {
239     // Clear references to originating lines, since the lines are being deleted
240     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
241         ASSERT(!((*it)->originatingLine()) || &((*it)->originatingLine()->renderer()) == m_renderer);
242         (*it)->setOriginatingLine(0);
243     }
244 }
245
246 void FloatingObjects::clear()
247 {
248     m_set.clear();
249     m_placedFloatsTree.clear();
250     m_leftObjectsCount = 0;
251     m_rightObjectsCount = 0;
252 }
253
254 void FloatingObjects::moveAllToFloatInfoMap(RendererToFloatInfoMap& map)
255 {
256     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
257         auto& renderer = it->get()->renderer();
258         // FIXME: The only reason it is safe to move these out of the set is that
259         // we are about to clear it. Otherwise it would break the hash table invariant.
260         // A clean way to do this would be to add a takeAll function to HashSet.
261         map.add(&renderer, std::move(*it));
262     }
263     clear();
264 }
265
266 void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
267 {
268     if (type == FloatingObject::FloatLeft)
269         m_leftObjectsCount++;
270     else
271         m_rightObjectsCount++;
272 }
273
274 void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
275 {
276     if (type == FloatingObject::FloatLeft)
277         m_leftObjectsCount--;
278     else
279         m_rightObjectsCount--;
280 }
281
282 FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
283 {
284     if (m_horizontalWritingMode)
285         return FloatingObjectInterval(floatingObject->frameRect().y(), floatingObject->frameRect().maxY(), floatingObject);
286     return FloatingObjectInterval(floatingObject->frameRect().x(), floatingObject->frameRect().maxX(), floatingObject);
287 }
288
289 void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
290 {
291     ASSERT(!floatingObject->isInPlacedTree());
292
293     floatingObject->setIsPlaced(true);
294     if (m_placedFloatsTree.isInitialized())
295         m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
296
297 #ifndef NDEBUG
298     floatingObject->setIsInPlacedTree(true);
299 #endif
300 }
301
302 void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
303 {
304     ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
305
306     if (m_placedFloatsTree.isInitialized()) {
307         bool removed = m_placedFloatsTree.remove(intervalForFloatingObject(floatingObject));
308         ASSERT_UNUSED(removed, removed);
309     }
310
311     floatingObject->setIsPlaced(false);
312 #ifndef NDEBUG
313     floatingObject->setIsInPlacedTree(false);
314 #endif
315 }
316
317 FloatingObject* FloatingObjects::add(std::unique_ptr<FloatingObject> floatingObject)
318 {
319     increaseObjectsCount(floatingObject->type());
320     if (floatingObject->isPlaced())
321         addPlacedObject(floatingObject.get());
322     return m_set.add(std::move(floatingObject)).iterator->get();
323 }
324
325 void FloatingObjects::remove(FloatingObject* floatingObject)
326 {
327     ASSERT((m_set.contains<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject)));
328     decreaseObjectsCount(floatingObject->type());
329     ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
330     if (floatingObject->isPlaced())
331         removePlacedObject(floatingObject);
332     ASSERT(!floatingObject->originatingLine());
333     auto it = m_set.find<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject);
334     if (it == m_set.end())
335         return;
336     m_set.remove(it);
337 }
338
339 void FloatingObjects::computePlacedFloatsTree()
340 {
341     ASSERT(!m_placedFloatsTree.isInitialized());
342     if (m_set.isEmpty())
343         return;
344     m_placedFloatsTree.initIfNeeded(m_renderer->view().intervalArena());
345     for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
346         FloatingObject* floatingObject = it->get();
347         if (floatingObject->isPlaced())
348             m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
349     }
350 }
351
352 inline const FloatingObjectTree& FloatingObjects::placedFloatsTree()
353 {
354     if (!m_placedFloatsTree.isInitialized())
355         computePlacedFloatsTree();
356     return m_placedFloatsTree;
357 }
358
359 #if ENABLE(CSS_SHAPES)
360 static inline ShapeOutsideInfo* shapeInfoForFloat(const FloatingObject* floatingObject, const RenderBlockFlow* containingBlock, LayoutUnit lineTop, LayoutUnit lineBottom)
361 {
362     if (floatingObject) {
363         if (ShapeOutsideInfo* shapeOutside = floatingObject->renderer().shapeOutsideInfo()) {
364             shapeOutside->updateDeltasForContainingBlockLine(containingBlock, floatingObject, lineTop, lineBottom - lineTop);
365             return shapeOutside;
366         }
367     }
368
369     return 0;
370 }
371 #endif
372
373 template<>
374 inline LayoutUnit ComputeFloatOffsetAdapter<FloatingObject::FloatLeft>::shapeOffset() const
375 {
376 #if ENABLE(CSS_SHAPES)
377     if (ShapeOutsideInfo* shapeOutside = shapeInfoForFloat(m_outermostFloat, m_renderer, m_lineTop, m_lineBottom))
378         return m_offset + shapeOutside->rightMarginBoxDelta();
379 #endif
380
381     return m_offset;
382 }
383
384 template<>
385 inline LayoutUnit ComputeFloatOffsetAdapter<FloatingObject::FloatRight>::shapeOffset() const
386 {
387 #if ENABLE(CSS_SHAPES)
388     if (ShapeOutsideInfo* shapeOutside = shapeInfoForFloat(m_outermostFloat, m_renderer, m_lineTop, m_lineBottom))
389         return m_offset + shapeOutside->leftMarginBoxDelta();
390 #endif
391
392     return m_offset;
393 }
394
395 LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
396 {
397     ComputeFloatOffsetAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
398     placedFloatsTree().allOverlapsWithAdapter(adapter);
399
400     if (heightRemaining)
401         *heightRemaining = adapter.heightRemaining();
402
403     return adapter.offset();
404 }
405
406 LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
407 {
408     ComputeFloatOffsetAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop, fixedOffset);
409     placedFloatsTree().allOverlapsWithAdapter(adapter);
410
411     if (heightRemaining)
412         *heightRemaining = adapter.heightRemaining();
413
414     return min(fixedOffset, adapter.offset());
415 }
416
417 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
418 {
419     ComputeFloatOffsetAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
420     placedFloatsTree().allOverlapsWithAdapter(adapter);
421
422     return adapter.shapeOffset();
423 }
424
425 LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
426 {
427     ComputeFloatOffsetAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTop, logicalTop + logicalHeight, fixedOffset);
428     placedFloatsTree().allOverlapsWithAdapter(adapter);
429
430     return min(fixedOffset, adapter.shapeOffset());
431 }
432
433 template<>
434 inline bool ComputeFloatOffsetAdapter<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 ComputeFloatOffsetAdapter<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 inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
457 {
458     const FloatingObject* floatingObject = interval.data();
459     if (floatingObject->type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
460         return;
461
462     // All the objects returned from the tree should be already placed.
463     ASSERT(floatingObject->isPlaced());
464     ASSERT(rangesIntersect(m_renderer->pixelSnappedLogicalTopForFloat(floatingObject), m_renderer->pixelSnappedLogicalBottomForFloat(floatingObject), m_lineTop, m_lineBottom));
465
466     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
467     if (floatIsNewExtreme)
468         m_outermostFloat = floatingObject;
469 }
470
471 template <FloatingObject::Type FloatTypeValue>
472 LayoutUnit ComputeFloatOffsetAdapter<FloatTypeValue>::heightRemaining() const
473 {
474     return m_outermostFloat ? m_renderer->logicalBottomForFloat(m_outermostFloat) - m_lineTop : LayoutUnit(1);
475 }
476
477 #ifndef NDEBUG
478 // These helpers are only used by the PODIntervalTree for debugging purposes.
479 String ValueToString<int>::string(const int value)
480 {
481     return String::number(value);
482 }
483
484 String ValueToString<FloatingObject*>::string(const FloatingObject* floatingObject)
485 {
486     return String::format("%p (%ix%i %ix%i)", floatingObject, floatingObject->frameRect().x().toInt(), floatingObject->frameRect().y().toInt(), floatingObject->frameRect().maxX().toInt(), floatingObject->frameRect().maxY().toInt());
487 }
488 #endif
489
490
491 } // namespace WebCore