Home | History | Annotate | Download | only in rendering 
      1 /*
      2  * Copyright (C) 1999 Lars Knoll (knoll (at) kde.org)
      3  *           (C) 1999 Antti Koivisto (koivisto (at) kde.org)
      4  *           (C) 2007 David Smith (catfish.man (at) 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 
     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(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 
     64 FloatingObject::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 
     79 PassOwnPtr<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 
     88 PassOwnPtr<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 
     93 PassOwnPtr<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 
    102 template <FloatingObject::Type FloatTypeValue>
    103 class ComputeFloatOffsetAdapter {
    104 public:
    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 
    124 private:
    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 
    135 FloatingObjects::~FloatingObjects()
    136 {
    137     // FIXME: m_set should use OwnPtr instead.
    138     deleteAllValues(m_set);
    139 }
    140 void 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 
    150 template<>
    151 inline 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 
    161 FloatingObjects::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 
    171 void 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 
    181 LayoutUnit 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 
    226 bool 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 
    234 LayoutUnit 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 
    242 void 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 
    252 void FloatingObjects::markLowestFloatLogicalBottomCacheAsDirty()
    253 {
    254     for (size_t i = 0; i < sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue); ++i)
    255         m_lowestFloatBottomCache[i].dirty = true;
    256 }
    257 
    258 void 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 
    270 inline void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
    271 {
    272     if (type == FloatingObject::FloatLeft)
    273         m_leftObjectsCount++;
    274     else
    275         m_rightObjectsCount++;
    276 }
    277 
    278 inline void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
    279 {
    280     if (type == FloatingObject::FloatLeft)
    281         m_leftObjectsCount--;
    282     else
    283         m_rightObjectsCount--;
    284 }
    285 
    286 inline 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 
    293 void 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 
    307 void 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 
    323 FloatingObject* 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 
    334 void 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 
    346 void 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 
    361 static 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 
    373 template<>
    374 inline 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 
    382 template<>
    383 inline 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 
    391 LayoutUnit 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 
    403 LayoutUnit 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 
    415 LayoutUnit 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 
    423 LayoutUnit 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 
    431 FloatingObjects::FloatBottomCachedValue::FloatBottomCachedValue()
    432     : value(0)
    433     , dirty(true)
    434 {
    435 }
    436 
    437 inline 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 
    457 template<>
    458 inline 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 
    468 template <FloatingObject::Type FloatTypeValue>
    469 inline 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 
    485 template <FloatingObject::Type FloatTypeValue>
    486 LayoutUnit 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.
    493 String ValueToString<int>::string(const int value)
    494 {
    495     return String::number(value);
    496 }
    497 
    498 String 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