[ContentChangeObserver] Content observation should be limited to the current document.
[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-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
33 namespace WebCore {
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 #ifndef NDEBUG
103
104 String 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
111 inline 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
131 template <FloatingObject::Type FloatTypeValue>
132 class ComputeFloatOffsetAdapter {
133 public:
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
153 protected:
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
163 template <FloatingObject::Type FloatTypeValue>
164 class ComputeFloatOffsetForFloatLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
165 public:
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
175 protected:
176     bool updateOffsetIfNeeded(const FloatingObject&) final;
177 };
178
179 template <FloatingObject::Type FloatTypeValue>
180 class ComputeFloatOffsetForLineLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
181 public:
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
189 protected:
190     bool updateOffsetIfNeeded(const FloatingObject&) final;
191 };
192
193 class FindNextFloatLogicalBottomAdapter {
194 public:
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
210 private:
211     WeakPtr<const RenderBlockFlow> m_renderer;
212     LayoutUnit m_belowLogicalHeight;
213     Optional<LayoutUnit> m_nextLogicalBottom;
214     Optional<LayoutUnit> m_nextShapeLogicalBottom;
215 };
216
217 inline 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
240 LayoutUnit 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
249 LayoutUnit 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
258 FloatingObjects::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
266 FloatingObjects::~FloatingObjects() = default;
267
268 void 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
277 void FloatingObjects::clear()
278 {
279     m_set.clear();
280     m_placedFloatsTree = nullptr;
281     m_leftObjectsCount = 0;
282     m_rightObjectsCount = 0;
283 }
284
285 void 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
297 void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
298 {
299     if (type == FloatingObject::FloatLeft)
300         m_leftObjectsCount++;
301     else
302         m_rightObjectsCount++;
303 }
304
305 void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
306 {
307     if (type == FloatingObject::FloatLeft)
308         m_leftObjectsCount--;
309     else
310         m_rightObjectsCount--;
311 }
312
313 FloatingObjectInterval 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
322 void 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
335 void 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
350 FloatingObject* 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
358 void 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
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(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(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(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(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 : 1_lu;
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 (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
481         ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
482         if (!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
495 template<>
496 inline 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.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