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 "core/rendering/FloatingObjects.h"
26
27#include "core/rendering/RenderBlockFlow.h"
28#include "core/rendering/RenderBox.h"
29#include "core/rendering/RenderView.h"
30
31using namespace WTF;
32
33namespace blink {
34
35struct SameSizeAsFloatingObject {
36    void* pointers[2];
37    LayoutRect rect;
38    int paginationStrut;
39    uint32_t bitfields : 8;
40};
41
42COMPILE_ASSERT(sizeof(FloatingObject) == sizeof(SameSizeAsFloatingObject), FloatingObject_should_stay_small);
43
44FloatingObject::FloatingObject(RenderBox* renderer)
45    : m_renderer(renderer)
46    , m_originatingLine(0)
47    , m_paginationStrut(0)
48    , m_shouldPaint(true)
49    , m_isDescendant(false)
50    , m_isPlaced(false)
51#if ENABLE(ASSERT)
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
63FloatingObject::FloatingObject(RenderBox* renderer, Type type, const LayoutRect& frameRect, bool shouldPaint, bool isDescendant)
64    : m_renderer(renderer)
65    , m_originatingLine(0)
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#if ENABLE(ASSERT)
73    , m_isInPlacedTree(false)
74#endif
75{
76}
77
78PassOwnPtr<FloatingObject> FloatingObject::create(RenderBox* renderer)
79{
80    OwnPtr<FloatingObject> newObj = adoptPtr(new FloatingObject(renderer));
81    newObj->setShouldPaint(!renderer->hasSelfPaintingLayer()); // If a layer exists, the float will paint itself. Otherwise someone else will.
82    newObj->setIsDescendant(true);
83
84    return newObj.release();
85}
86
87PassOwnPtr<FloatingObject> FloatingObject::copyToNewContainer(LayoutSize offset, bool shouldPaint, bool isDescendant) const
88{
89    return adoptPtr(new FloatingObject(renderer(), type(), LayoutRect(frameRect().location() - offset, frameRect().size()), shouldPaint, isDescendant));
90}
91
92PassOwnPtr<FloatingObject> FloatingObject::unsafeClone() const
93{
94    OwnPtr<FloatingObject> cloneObject = adoptPtr(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.release();
98}
99
100template <FloatingObject::Type FloatTypeValue>
101class ComputeFloatOffsetAdapter {
102public:
103    typedef FloatingObjectInterval IntervalType;
104
105    ComputeFloatOffsetAdapter(const RenderBlockFlow* renderer, int lineTop, int lineBottom, LayoutUnit offset)
106        : m_renderer(renderer)
107        , m_lineTop(lineTop)
108        , m_lineBottom(lineBottom)
109        , m_offset(offset)
110        , m_outermostFloat(0)
111    {
112    }
113
114    virtual ~ComputeFloatOffsetAdapter() { }
115
116    int lowValue() const { return m_lineTop; }
117    int highValue() const { return m_lineBottom; }
118    void collectIfNeeded(const IntervalType&);
119
120    LayoutUnit offset() const { return m_offset; }
121
122protected:
123    virtual bool updateOffsetIfNeeded(const FloatingObject&) = 0;
124
125    const RenderBlockFlow* m_renderer;
126    int m_lineTop;
127    int m_lineBottom;
128    LayoutUnit m_offset;
129    const FloatingObject* m_outermostFloat;
130};
131
132template <FloatingObject::Type FloatTypeValue>
133class ComputeFloatOffsetForFloatLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
134public:
135    ComputeFloatOffsetForFloatLayoutAdapter(const RenderBlockFlow* renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
136        : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
137    {
138    }
139
140    virtual ~ComputeFloatOffsetForFloatLayoutAdapter() { }
141
142    LayoutUnit heightRemaining() const;
143
144protected:
145    virtual bool updateOffsetIfNeeded(const FloatingObject&) OVERRIDE FINAL;
146};
147
148template <FloatingObject::Type FloatTypeValue>
149class ComputeFloatOffsetForLineLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
150public:
151    ComputeFloatOffsetForLineLayoutAdapter(const RenderBlockFlow* renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
152        : ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
153    {
154    }
155
156    virtual ~ComputeFloatOffsetForLineLayoutAdapter() { }
157
158protected:
159    virtual bool updateOffsetIfNeeded(const FloatingObject&) OVERRIDE FINAL;
160};
161
162
163FloatingObjects::~FloatingObjects()
164{
165}
166void FloatingObjects::clearLineBoxTreePointers()
167{
168    // Clear references to originating lines, since the lines are being deleted
169    FloatingObjectSetIterator end = m_set.end();
170    for (FloatingObjectSetIterator it = m_set.begin(); it != end; ++it) {
171        ASSERT(!((*it)->originatingLine()) || (*it)->originatingLine()->renderer() == m_renderer);
172        (*it)->setOriginatingLine(0);
173    }
174}
175
176FloatingObjects::FloatingObjects(const RenderBlockFlow* renderer, bool horizontalWritingMode)
177    : m_placedFloatsTree(UninitializedTree)
178    , m_leftObjectsCount(0)
179    , m_rightObjectsCount(0)
180    , m_horizontalWritingMode(horizontalWritingMode)
181    , m_renderer(renderer)
182    , m_cachedHorizontalWritingMode(false)
183{
184}
185
186void FloatingObjects::clear()
187{
188    m_set.clear();
189    m_placedFloatsTree.clear();
190    m_leftObjectsCount = 0;
191    m_rightObjectsCount = 0;
192    markLowestFloatLogicalBottomCacheAsDirty();
193}
194
195LayoutUnit FloatingObjects::lowestFloatLogicalBottom(FloatingObject::Type floatType)
196{
197    bool isInHorizontalWritingMode = m_horizontalWritingMode;
198    if (floatType != FloatingObject::FloatLeftRight) {
199        if (hasLowestFloatLogicalBottomCached(isInHorizontalWritingMode, floatType))
200            return getCachedlowestFloatLogicalBottom(floatType);
201    } else {
202        if (hasLowestFloatLogicalBottomCached(isInHorizontalWritingMode, FloatingObject::FloatLeft) && hasLowestFloatLogicalBottomCached(isInHorizontalWritingMode, FloatingObject::FloatRight)) {
203            return std::max(getCachedlowestFloatLogicalBottom(FloatingObject::FloatLeft),
204                getCachedlowestFloatLogicalBottom(FloatingObject::FloatRight));
205        }
206    }
207
208    LayoutUnit lowestFloatBottom = 0;
209    const FloatingObjectSet& floatingObjectSet = set();
210    FloatingObjectSetIterator end = floatingObjectSet.end();
211    if (floatType == FloatingObject::FloatLeftRight) {
212        LayoutUnit lowestFloatBottomLeft = 0;
213        LayoutUnit lowestFloatBottomRight = 0;
214        for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
215            FloatingObject* floatingObject = it->get();
216            if (floatingObject->isPlaced()) {
217                FloatingObject::Type curType = floatingObject->type();
218                LayoutUnit curFloatLogicalBottom = m_renderer->logicalBottomForFloat(floatingObject);
219                if (curType & FloatingObject::FloatLeft)
220                    lowestFloatBottomLeft = std::max(lowestFloatBottomLeft, curFloatLogicalBottom);
221                if (curType & FloatingObject::FloatRight)
222                    lowestFloatBottomRight = std::max(lowestFloatBottomRight, curFloatLogicalBottom);
223            }
224        }
225        lowestFloatBottom = std::max(lowestFloatBottomLeft, lowestFloatBottomRight);
226        setCachedLowestFloatLogicalBottom(isInHorizontalWritingMode, FloatingObject::FloatLeft, lowestFloatBottomLeft);
227        setCachedLowestFloatLogicalBottom(isInHorizontalWritingMode, FloatingObject::FloatRight, lowestFloatBottomRight);
228    } else {
229        for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
230            FloatingObject* floatingObject = it->get();
231            if (floatingObject->isPlaced() && floatingObject->type() == floatType)
232                lowestFloatBottom = std::max(lowestFloatBottom, m_renderer->logicalBottomForFloat(floatingObject));
233        }
234        setCachedLowestFloatLogicalBottom(isInHorizontalWritingMode, floatType, lowestFloatBottom);
235    }
236
237    return lowestFloatBottom;
238}
239
240bool FloatingObjects::hasLowestFloatLogicalBottomCached(bool isHorizontal, FloatingObject::Type type) const
241{
242    int floatIndex = static_cast<int>(type) - 1;
243    ASSERT(floatIndex < static_cast<int>(sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue)));
244    ASSERT(floatIndex >= 0);
245    return (m_cachedHorizontalWritingMode == isHorizontal && !m_lowestFloatBottomCache[floatIndex].dirty);
246}
247
248LayoutUnit FloatingObjects::getCachedlowestFloatLogicalBottom(FloatingObject::Type type) const
249{
250    int floatIndex = static_cast<int>(type) - 1;
251    ASSERT(floatIndex < static_cast<int>(sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue)));
252    ASSERT(floatIndex >= 0);
253    return m_lowestFloatBottomCache[floatIndex].value;
254}
255
256void FloatingObjects::setCachedLowestFloatLogicalBottom(bool isHorizontal, FloatingObject::Type type, LayoutUnit value)
257{
258    int floatIndex = static_cast<int>(type) - 1;
259    ASSERT(floatIndex < static_cast<int>(sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue)));
260    ASSERT(floatIndex >= 0);
261    m_cachedHorizontalWritingMode = isHorizontal;
262    m_lowestFloatBottomCache[floatIndex].value = value;
263    m_lowestFloatBottomCache[floatIndex].dirty = false;
264}
265
266void FloatingObjects::markLowestFloatLogicalBottomCacheAsDirty()
267{
268    for (size_t i = 0; i < sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue); ++i)
269        m_lowestFloatBottomCache[i].dirty = true;
270}
271
272void FloatingObjects::moveAllToFloatInfoMap(RendererToFloatInfoMap& map)
273{
274    while (!m_set.isEmpty()) {
275        OwnPtr<FloatingObject> floatingObject = m_set.takeFirst();
276        RenderBox* renderer = floatingObject->renderer();
277        map.add(renderer, floatingObject.release());
278    }
279    clear();
280}
281
282inline void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
283{
284    if (type == FloatingObject::FloatLeft)
285        m_leftObjectsCount++;
286    else
287        m_rightObjectsCount++;
288}
289
290inline void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
291{
292    if (type == FloatingObject::FloatLeft)
293        m_leftObjectsCount--;
294    else
295        m_rightObjectsCount--;
296}
297
298inline FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
299{
300    if (m_horizontalWritingMode)
301        return FloatingObjectInterval(floatingObject->frameRect().pixelSnappedY(), floatingObject->frameRect().pixelSnappedMaxY(), floatingObject);
302    return FloatingObjectInterval(floatingObject->frameRect().pixelSnappedX(), floatingObject->frameRect().pixelSnappedMaxX(), floatingObject);
303}
304
305void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
306{
307    ASSERT(!floatingObject->isInPlacedTree());
308
309    floatingObject->setIsPlaced(true);
310    if (m_placedFloatsTree.isInitialized())
311        m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
312
313#if ENABLE(ASSERT)
314    floatingObject->setIsInPlacedTree(true);
315#endif
316    markLowestFloatLogicalBottomCacheAsDirty();
317}
318
319void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
320{
321    ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
322
323    if (m_placedFloatsTree.isInitialized()) {
324        bool removed = m_placedFloatsTree.remove(intervalForFloatingObject(floatingObject));
325        ASSERT_UNUSED(removed, removed);
326    }
327
328    floatingObject->setIsPlaced(false);
329#if ENABLE(ASSERT)
330    floatingObject->setIsInPlacedTree(false);
331#endif
332    markLowestFloatLogicalBottomCacheAsDirty();
333}
334
335FloatingObject* FloatingObjects::add(PassOwnPtr<FloatingObject> floatingObject)
336{
337    FloatingObject* newObject = floatingObject.leakPtr();
338    increaseObjectsCount(newObject->type());
339    m_set.add(adoptPtr(newObject));
340    if (newObject->isPlaced())
341        addPlacedObject(newObject);
342    markLowestFloatLogicalBottomCacheAsDirty();
343    return newObject;
344}
345
346void FloatingObjects::remove(FloatingObject* toBeRemoved)
347{
348    decreaseObjectsCount(toBeRemoved->type());
349    OwnPtr<FloatingObject> floatingObject = m_set.take(toBeRemoved);
350    ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
351    if (floatingObject->isPlaced())
352        removePlacedObject(floatingObject.get());
353    markLowestFloatLogicalBottomCacheAsDirty();
354    ASSERT(!floatingObject->originatingLine());
355}
356
357void FloatingObjects::computePlacedFloatsTree()
358{
359    ASSERT(!m_placedFloatsTree.isInitialized());
360    if (m_set.isEmpty())
361        return;
362    m_placedFloatsTree.initIfNeeded(m_renderer->view()->intervalArena());
363    FloatingObjectSetIterator it = m_set.begin();
364    FloatingObjectSetIterator end = m_set.end();
365    for (; it != end; ++it) {
366        FloatingObject* floatingObject = it->get();
367        if (floatingObject->isPlaced())
368            m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
369    }
370}
371
372LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
373{
374    int logicalTopAsInt = roundToInt(logicalTop);
375    ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, logicalTopAsInt, logicalTopAsInt, fixedOffset);
376    placedFloatsTree().allOverlapsWithAdapter(adapter);
377
378    if (heightRemaining)
379        *heightRemaining = adapter.heightRemaining();
380
381    return adapter.offset();
382}
383
384LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
385{
386    int logicalTopAsInt = roundToInt(logicalTop);
387    ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, logicalTopAsInt, logicalTopAsInt, fixedOffset);
388    placedFloatsTree().allOverlapsWithAdapter(adapter);
389
390    if (heightRemaining)
391        *heightRemaining = adapter.heightRemaining();
392
393    return std::min(fixedOffset, adapter.offset());
394}
395
396LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
397{
398    ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(m_renderer, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), fixedOffset);
399    placedFloatsTree().allOverlapsWithAdapter(adapter);
400
401    return adapter.offset();
402}
403
404LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
405{
406    ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(m_renderer, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), fixedOffset);
407    placedFloatsTree().allOverlapsWithAdapter(adapter);
408
409    return std::min(fixedOffset, adapter.offset());
410}
411
412FloatingObjects::FloatBottomCachedValue::FloatBottomCachedValue()
413    : value(0)
414    , dirty(true)
415{
416}
417
418inline static bool rangesIntersect(int floatTop, int floatBottom, int objectTop, int objectBottom)
419{
420    if (objectTop >= floatBottom || objectBottom < floatTop)
421        return false;
422
423    // The top of the object overlaps the float
424    if (objectTop >= floatTop)
425        return true;
426
427    // The object encloses the float
428    if (objectTop < floatTop && objectBottom > floatBottom)
429        return true;
430
431    // The bottom of the object overlaps the float
432    if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
433        return true;
434
435    return false;
436}
437
438template<>
439inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
440{
441    LayoutUnit logicalRight = m_renderer->logicalRightForFloat(&floatingObject);
442    if (logicalRight > m_offset) {
443        m_offset = logicalRight;
444        return true;
445    }
446    return false;
447}
448
449template<>
450inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
451{
452    LayoutUnit logicalLeft = m_renderer->logicalLeftForFloat(&floatingObject);
453    if (logicalLeft < m_offset) {
454        m_offset = logicalLeft;
455        return true;
456    }
457    return false;
458}
459
460template <FloatingObject::Type FloatTypeValue>
461LayoutUnit ComputeFloatOffsetForFloatLayoutAdapter<FloatTypeValue>::heightRemaining() const
462{
463    return this->m_outermostFloat ? this->m_renderer->logicalBottomForFloat(this->m_outermostFloat) - this->m_lineTop : LayoutUnit(1);
464}
465
466template <FloatingObject::Type FloatTypeValue>
467inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
468{
469    const FloatingObject* floatingObject = interval.data();
470    if (floatingObject->type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
471        return;
472
473    // Make sure the float hasn't changed since it was added to the placed floats tree.
474    ASSERT(floatingObject->isPlaced());
475    ASSERT(interval.low() == m_renderer->pixelSnappedLogicalTopForFloat(floatingObject));
476    ASSERT(interval.high() == m_renderer->pixelSnappedLogicalBottomForFloat(floatingObject));
477
478    bool floatIsNewExtreme = updateOffsetIfNeeded(*floatingObject);
479    if (floatIsNewExtreme)
480        m_outermostFloat = floatingObject;
481}
482
483template<>
484inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
485{
486    LayoutUnit logicalRight = m_renderer->logicalRightForFloat(&floatingObject);
487    if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer()->shapeOutsideInfo()) {
488        ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
489        if (!shapeDeltas.lineOverlapsShape())
490            return false;
491
492        logicalRight += shapeDeltas.rightMarginBoxDelta();
493    }
494    if (logicalRight > m_offset) {
495        m_offset = logicalRight;
496        return true;
497    }
498
499    return false;
500}
501
502template<>
503inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
504{
505    LayoutUnit logicalLeft = m_renderer->logicalLeftForFloat(&floatingObject);
506    if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer()->shapeOutsideInfo()) {
507        ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
508        if (!shapeDeltas.lineOverlapsShape())
509            return false;
510
511        logicalLeft += shapeDeltas.leftMarginBoxDelta();
512    }
513    if (logicalLeft < m_offset) {
514        m_offset = logicalLeft;
515        return true;
516    }
517
518    return false;
519}
520
521#ifndef NDEBUG
522// These helpers are only used by the PODIntervalTree for debugging purposes.
523String ValueToString<int>::string(const int value)
524{
525    return String::number(value);
526}
527
528String ValueToString<FloatingObject*>::string(const FloatingObject* floatingObject)
529{
530    return String::format("%p (%dx%d %dx%d)", floatingObject, floatingObject->frameRect().pixelSnappedX(), floatingObject->frameRect().pixelSnappedY(), floatingObject->frameRect().pixelSnappedMaxX(), floatingObject->frameRect().pixelSnappedMaxY());
531}
532#endif
533
534
535} // namespace blink
536