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