src/third_party/WebKit/Source/core/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, 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