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