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