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-2019 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#include <wtf/HexNumber.h>
31#include <wtf/text/StringConcatenateNumbers.h>
32
33namespace WebCore {
34
35struct SameSizeAsFloatingObject {
36 void* pointers[2];
37 LayoutRect rect;
38 int paginationStrut;
39 LayoutSize size;
40 uint32_t bitfields : 8;
41};
42
43COMPILE_ASSERT(sizeof(FloatingObject) == sizeof(SameSizeAsFloatingObject), FloatingObject_should_stay_small);
44
45FloatingObject::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
62FloatingObject::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
76std::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
84std::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
89std::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
97LayoutSize FloatingObject::translationOffsetToAncestor() const
98{
99 return locationOffsetOfBorderBox() - renderer().locationOffset();
100}
101
102#ifndef NDEBUG
103
104String FloatingObject::debugString() const
105{
106 return makeString("0x", hex(reinterpret_cast<uintptr_t>(this)), " (", frameRect().x().toInt(), 'x', frameRect().y().toInt(), ' ', frameRect().maxX().toInt(), 'x', frameRect().maxY().toInt(), ')');
107}
108
109#endif
110
111inline static bool rangesIntersect(LayoutUnit floatTop, LayoutUnit floatBottom, LayoutUnit objectTop, LayoutUnit objectBottom)
112{
113 if (objectTop >= floatBottom || objectBottom < floatTop)
114 return false;
115
116 // The top of the object overlaps the float
117 if (objectTop >= floatTop)
118 return true;
119
120 // The object encloses the float
121 if (objectTop < floatTop && objectBottom > floatBottom)
122 return true;
123
124 // The bottom of the object overlaps the float
125 if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
126 return true;
127
128 return false;
129}
130
131template <FloatingObject::Type FloatTypeValue>
132class ComputeFloatOffsetAdapter {
133public:
134 typedef FloatingObjectInterval IntervalType;
135
136 ComputeFloatOffsetAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
137 : m_renderer(makeWeakPtr(renderer))
138 , m_lineTop(lineTop)
139 , m_lineBottom(lineBottom)
140 , m_offset(offset)
141 , m_outermostFloat(0)
142 {
143 }
144
145 virtual ~ComputeFloatOffsetAdapter() = default;
146
147 LayoutUnit lowValue() const { return m_lineTop; }
148 LayoutUnit highValue() const { return m_lineBottom; }
149 void collectIfNeeded(const IntervalType&);
150
151 LayoutUnit offset() const { return m_offset; }
152
153protected:
154 virtual bool updateOffsetIfNeeded(const FloatingObject&) = 0;
155
156 WeakPtr<const RenderBlockFlow> m_renderer;
157 LayoutUnit m_lineTop;
158 LayoutUnit m_lineBottom;
159 LayoutUnit m_offset;
160 const FloatingObject* m_outermostFloat;
161};
162
163template <FloatingObject::Type FloatTypeValue>
164class ComputeFloatOffsetForFloatLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
165public:
166 ComputeFloatOffsetForFloatLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
167 : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
168 {
169 }
170
171 virtual ~ComputeFloatOffsetForFloatLayoutAdapter() = default;
172
173 LayoutUnit heightRemaining() const;
174
175protected:
176 bool updateOffsetIfNeeded(const FloatingObject&) final;
177};
178
179template <FloatingObject::Type FloatTypeValue>
180class ComputeFloatOffsetForLineLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
181public:
182 ComputeFloatOffsetForLineLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
183 : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
184 {
185 }
186
187 virtual ~ComputeFloatOffsetForLineLayoutAdapter() = default;
188
189protected:
190 bool updateOffsetIfNeeded(const FloatingObject&) final;
191};
192
193class FindNextFloatLogicalBottomAdapter {
194public:
195 typedef FloatingObjectInterval IntervalType;
196
197 FindNextFloatLogicalBottomAdapter(const RenderBlockFlow& renderer, LayoutUnit belowLogicalHeight)
198 : m_renderer(makeWeakPtr(renderer))
199 , m_belowLogicalHeight(belowLogicalHeight)
200 {
201 }
202
203 LayoutUnit lowValue() const { return m_belowLogicalHeight; }
204 LayoutUnit highValue() const { return LayoutUnit::max(); }
205 void collectIfNeeded(const IntervalType&);
206
207 LayoutUnit nextLogicalBottom() const { return m_nextLogicalBottom.valueOr(0); }
208 LayoutUnit nextShapeLogicalBottom() const { return m_nextShapeLogicalBottom.valueOr(nextLogicalBottom()); }
209
210private:
211 WeakPtr<const RenderBlockFlow> m_renderer;
212 LayoutUnit m_belowLogicalHeight;
213 Optional<LayoutUnit> m_nextLogicalBottom;
214 Optional<LayoutUnit> m_nextShapeLogicalBottom;
215};
216
217inline void FindNextFloatLogicalBottomAdapter::collectIfNeeded(const IntervalType& interval)
218{
219 const auto& floatingObject = *interval.data();
220 if (!rangesIntersect(interval.low(), interval.high(), m_belowLogicalHeight, LayoutUnit::max()))
221 return;
222
223 // All the objects returned from the tree should be already placed.
224 ASSERT(floatingObject.isPlaced());
225 ASSERT(rangesIntersect(m_renderer->logicalTopForFloat(floatingObject), m_renderer->logicalBottomForFloat(floatingObject), m_belowLogicalHeight, LayoutUnit::max()));
226
227 LayoutUnit floatBottom = m_renderer->logicalBottomForFloat(floatingObject);
228 if (m_nextLogicalBottom && m_nextLogicalBottom.value() < floatBottom)
229 return;
230
231 if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
232 LayoutUnit shapeBottom = m_renderer->logicalTopForFloat(floatingObject) + m_renderer->marginBeforeForChild(floatingObject.renderer()) + shapeOutside->shapeLogicalBottom();
233 // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
234 m_nextShapeLogicalBottom = std::min(shapeBottom, floatBottom);
235 } else
236 m_nextShapeLogicalBottom = floatBottom;
237 m_nextLogicalBottom = floatBottom;
238}
239
240LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelow(LayoutUnit logicalHeight)
241{
242 FindNextFloatLogicalBottomAdapter adapter(renderer(), logicalHeight);
243 if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
244 placedFloatsTree->allOverlapsWithAdapter(adapter);
245
246 return adapter.nextShapeLogicalBottom();
247}
248
249LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelowForBlock(LayoutUnit logicalHeight)
250{
251 FindNextFloatLogicalBottomAdapter adapter(renderer(), logicalHeight);
252 if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
253 placedFloatsTree->allOverlapsWithAdapter(adapter);
254
255 return adapter.nextLogicalBottom();
256}
257
258FloatingObjects::FloatingObjects(const RenderBlockFlow& renderer)
259 : m_leftObjectsCount(0)
260 , m_rightObjectsCount(0)
261 , m_horizontalWritingMode(renderer.isHorizontalWritingMode())
262 , m_renderer(makeWeakPtr(renderer))
263{
264}
265
266FloatingObjects::~FloatingObjects() = default;
267
268void FloatingObjects::clearLineBoxTreePointers()
269{
270 // Clear references to originating lines, since the lines are being deleted
271 for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
272 ASSERT(!((*it)->originatingLine()) || &((*it)->originatingLine()->renderer()) == &renderer());
273 (*it)->clearOriginatingLine();
274 }
275}
276
277void FloatingObjects::clear()
278{
279 m_set.clear();
280 m_placedFloatsTree = nullptr;
281 m_leftObjectsCount = 0;
282 m_rightObjectsCount = 0;
283}
284
285void FloatingObjects::moveAllToFloatInfoMap(RendererToFloatInfoMap& map)
286{
287 for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
288 auto& renderer = it->get()->renderer();
289 // FIXME: The only reason it is safe to move these out of the set is that
290 // we are about to clear it. Otherwise it would break the hash table invariant.
291 // A clean way to do this would be to add a takeAll function to HashSet.
292 map.add(&renderer, WTFMove(*it));
293 }
294 clear();
295}
296
297void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
298{
299 if (type == FloatingObject::FloatLeft)
300 m_leftObjectsCount++;
301 else
302 m_rightObjectsCount++;
303}
304
305void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
306{
307 if (type == FloatingObject::FloatLeft)
308 m_leftObjectsCount--;
309 else
310 m_rightObjectsCount--;
311}
312
313FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
314{
315 // FIXME The endpoints of the floating object interval shouldn't need to be
316 // floored. See http://wkb.ug/125831 for more details.
317 if (m_horizontalWritingMode)
318 return FloatingObjectInterval(floatingObject->frameRect().y().floor(), floatingObject->frameRect().maxY().floor(), floatingObject);
319 return FloatingObjectInterval(floatingObject->frameRect().x().floor(), floatingObject->frameRect().maxX().floor(), floatingObject);
320}
321
322void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
323{
324 ASSERT(!floatingObject->isInPlacedTree());
325
326 floatingObject->setIsPlaced(true);
327 if (m_placedFloatsTree)
328 m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
329
330#ifndef NDEBUG
331 floatingObject->setIsInPlacedTree(true);
332#endif
333}
334
335void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
336{
337 ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
338
339 if (m_placedFloatsTree) {
340 bool removed = m_placedFloatsTree->remove(intervalForFloatingObject(floatingObject));
341 ASSERT_UNUSED(removed, removed);
342 }
343
344 floatingObject->setIsPlaced(false);
345#ifndef NDEBUG
346 floatingObject->setIsInPlacedTree(false);
347#endif
348}
349
350FloatingObject* FloatingObjects::add(std::unique_ptr<FloatingObject> floatingObject)
351{
352 increaseObjectsCount(floatingObject->type());
353 if (floatingObject->isPlaced())
354 addPlacedObject(floatingObject.get());
355 return m_set.add(WTFMove(floatingObject)).iterator->get();
356}
357
358void FloatingObjects::remove(FloatingObject* floatingObject)
359{
360 ASSERT((m_set.contains(floatingObject)));
361 decreaseObjectsCount(floatingObject->type());
362 ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
363 if (floatingObject->isPlaced())
364 removePlacedObject(floatingObject);
365 ASSERT(!floatingObject->originatingLine());
366 m_set.remove(floatingObject);
367}
368
369void 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
383inline const FloatingObjectTree* FloatingObjects::placedFloatsTree()
384{
385 if (!m_placedFloatsTree)
386 computePlacedFloatsTree();
387 return m_placedFloatsTree.get();
388}
389
390LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
391{
392 ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(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
402LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
403{
404 ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(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
414LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
415{
416 ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(renderer(), logicalTop, logicalTop + logicalHeight, fixedOffset);
417 if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
418 placedFloatsTree->allOverlapsWithAdapter(adapter);
419
420 return adapter.offset();
421}
422
423LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
424{
425 ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(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
432template<>
433inline 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
443template<>
444inline 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
454template <FloatingObject::Type FloatTypeValue>
455LayoutUnit ComputeFloatOffsetForFloatLayoutAdapter<FloatTypeValue>::heightRemaining() const
456{
457 return this->m_outermostFloat ? this->m_renderer->logicalBottomForFloat(*this->m_outermostFloat) - this->m_lineTop : 1_lu;
458}
459
460template <FloatingObject::Type FloatTypeValue>
461inline 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
476template<>
477inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
478{
479 LayoutUnit logicalRight = m_renderer->logicalRightForFloat(floatingObject);
480 if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
481 ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
482 if (!shapeDeltas.isValid() || !shapeDeltas.lineOverlapsShape())
483 return false;
484
485 logicalRight += shapeDeltas.rightMarginBoxDelta();
486 }
487 if (logicalRight > m_offset) {
488 m_offset = logicalRight;
489 return true;
490 }
491
492 return false;
493}
494
495template<>
496inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
497{
498 LayoutUnit logicalLeft = m_renderer->logicalLeftForFloat(floatingObject);
499 if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
500 ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
501 if (!shapeDeltas.isValid() || !shapeDeltas.lineOverlapsShape())
502 return false;
503
504 logicalLeft += shapeDeltas.leftMarginBoxDelta();
505 }
506 if (logicalLeft < m_offset) {
507 m_offset = logicalLeft;
508 return true;
509 }
510
511 return false;
512}
513
514} // namespace WebCore
515