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