/* * Copyright (C) 2011 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF * THE POSSIBILITY OF SUCH DAMAGE. */ #include "config.h" #include "LegacyTileGrid.h" #if PLATFORM(IOS) #include "CoreGraphicsSPI.h" #include "LegacyTileGridTile.h" #include "LegacyTileLayer.h" #include "LegacyTileLayerPool.h" #include "QuartzCoreSPI.h" #include "SystemMemory.h" #include "WAKWindow.h" #include <algorithm> #include <functional> #include <wtf/MemoryPressureHandler.h> namespace WebCore { LegacyTileGrid::LegacyTileGrid(LegacyTileCache& tileCache, const IntSize& tileSize) : m_tileCache(tileCache) , m_tileHostLayer(adoptNS([[LegacyTileHostLayer alloc] initWithTileGrid:this])) , m_tileSize(tileSize) , m_scale(1) , m_validBounds(0, 0, std::numeric_limits<int>::max(), std::numeric_limits<int>::max()) { } LegacyTileGrid::~LegacyTileGrid() { [m_tileHostLayer removeFromSuperlayer]; } IntRect LegacyTileGrid::visibleRect() const { IntRect visibleRect = enclosingIntRect(m_tileCache.visibleRectInLayer(m_tileHostLayer.get())); // When fast scrolling to the top, move the visible rect there immediately so we have tiles when the scrolling completes. if (m_tileCache.tilingMode() == LegacyTileCache::ScrollToTop) visibleRect.setY(0); return visibleRect; } void LegacyTileGrid::dropAllTiles() { m_tiles.clear(); } void LegacyTileGrid::dropTilesIntersectingRect(const IntRect& dropRect) { dropTilesBetweenRects(dropRect, IntRect()); } void LegacyTileGrid::dropTilesOutsideRect(const IntRect& keepRect) { dropTilesBetweenRects(IntRect(0, 0, std::numeric_limits<int>::max(), std::numeric_limits<int>::max()), keepRect); } void LegacyTileGrid::dropTilesBetweenRects(const IntRect& dropRect, const IntRect& keepRect) { Vector<TileIndex> toRemove; for (const auto& tile : m_tiles) { const TileIndex& index = tile.key; IntRect tileRect = tile.value->rect(); if (tileRect.intersects(dropRect) && !tileRect.intersects(keepRect)) toRemove.append(index); } unsigned removeCount = toRemove.size(); for (unsigned n = 0; n < removeCount; ++n) m_tiles.remove(toRemove[n]); } unsigned LegacyTileGrid::tileByteSize() const { IntSize tilePixelSize = m_tileSize; tilePixelSize.scale(m_tileCache.screenScale()); return LegacyTileLayerPool::bytesBackingLayerWithPixelSize(tilePixelSize); } template <typename T> static bool isFartherAway(const std::pair<double, T>& a, const std::pair<double, T>& b) { return a.first > b.first; } bool LegacyTileGrid::dropDistantTiles(unsigned tilesNeeded, double shortestDistance) { unsigned bytesPerTile = tileByteSize(); unsigned bytesNeeded = tilesNeeded * bytesPerTile; unsigned bytesUsed = tileCount() * bytesPerTile; unsigned maximumBytes = m_tileCache.tileCapacityForGrid(this); int bytesToReclaim = int(bytesUsed) - (int(maximumBytes) - bytesNeeded); if (bytesToReclaim <= 0) return true; unsigned tilesToRemoveCount = bytesToReclaim / bytesPerTile; IntRect visibleRect = this->visibleRect(); Vector<std::pair<double, TileIndex>> toRemove; for (const auto& tile : m_tiles) { const TileIndex& index = tile.key; const IntRect& tileRect = tile.value->rect(); double distance = tileDistance2(visibleRect, tileRect); if (distance <= shortestDistance) continue; toRemove.append(std::make_pair(distance, index)); std::push_heap(toRemove.begin(), toRemove.end(), std::ptr_fun(isFartherAway<TileIndex>)); if (toRemove.size() > tilesToRemoveCount) { std::pop_heap(toRemove.begin(), toRemove.end(), std::ptr_fun(isFartherAway<TileIndex>)); toRemove.removeLast(); } } size_t removeCount = toRemove.size(); for (size_t n = 0; n < removeCount; ++n) m_tiles.remove(toRemove[n].second); if (!shortestDistance) return true; return tileCount() * bytesPerTile + bytesNeeded <= maximumBytes; } void LegacyTileGrid::addTilesCoveringRect(const IntRect& rectToCover) { // We never draw anything outside of our bounds. IntRect rect(rectToCover); rect.intersect(bounds()); if (rect.isEmpty()) return; TileIndex topLeftIndex = tileIndexForPoint(topLeft(rect)); TileIndex bottomRightIndex = tileIndexForPoint(bottomRight(rect)); for (int yIndex = topLeftIndex.y(); yIndex <= bottomRightIndex.y(); ++yIndex) { for (int xIndex = topLeftIndex.x(); xIndex <= bottomRightIndex.x(); ++xIndex) { TileIndex index(xIndex, yIndex); if (!tileForIndex(index)) addTileForIndex(index); } } } void LegacyTileGrid::addTileForIndex(const TileIndex& index) { m_tiles.set(index, LegacyTileGridTile::create(this, tileRectForIndex(index))); } CALayer* LegacyTileGrid::tileHostLayer() const { return m_tileHostLayer.get(); } IntRect LegacyTileGrid::bounds() const { return IntRect(IntPoint(), IntSize([tileHostLayer() size])); } RefPtr<LegacyTileGridTile> LegacyTileGrid::tileForIndex(const TileIndex& index) const { return m_tiles.get(index); } IntRect LegacyTileGrid::tileRectForIndex(const TileIndex& index) const { IntRect rect(index.x() * m_tileSize.width() - (m_origin.x() ? m_tileSize.width() - m_origin.x() : 0), index.y() * m_tileSize.height() - (m_origin.y() ? m_tileSize.height() - m_origin.y() : 0), m_tileSize.width(), m_tileSize.height()); rect.intersect(bounds()); return rect; } LegacyTileGrid::TileIndex LegacyTileGrid::tileIndexForPoint(const IntPoint& point) const { ASSERT(m_origin.x() < m_tileSize.width()); ASSERT(m_origin.y() < m_tileSize.height()); int x = (point.x() + (m_origin.x() ? m_tileSize.width() - m_origin.x() : 0)) / m_tileSize.width(); int y = (point.y() + (m_origin.y() ? m_tileSize.height() - m_origin.y() : 0)) / m_tileSize.height(); return TileIndex(std::max(x, 0), std::max(y, 0)); } void LegacyTileGrid::centerTileGridOrigin(const IntRect& visibleRect) { if (visibleRect.isEmpty()) return; unsigned minimumHorizontalTiles = 1 + (visibleRect.width() - 1) / m_tileSize.width(); unsigned minimumVerticalTiles = 1 + (visibleRect.height() - 1) / m_tileSize.height(); TileIndex currentTopLeftIndex = tileIndexForPoint(topLeft(visibleRect)); TileIndex currentBottomRightIndex = tileIndexForPoint(bottomRight(visibleRect)); unsigned currentHorizontalTiles = currentBottomRightIndex.x() - currentTopLeftIndex.x() + 1; unsigned currentVerticalTiles = currentBottomRightIndex.y() - currentTopLeftIndex.y() + 1; // If we have tiles already, only center if we would get benefits from both directions (as we need to throw out existing tiles). if (tileCount() && (currentHorizontalTiles == minimumHorizontalTiles || currentVerticalTiles == minimumVerticalTiles)) return; IntPoint newOrigin(0, 0); IntSize size = bounds().size(); if (size.width() > m_tileSize.width()) { newOrigin.setX((visibleRect.x() - (minimumHorizontalTiles * m_tileSize.width() - visibleRect.width()) / 2) % m_tileSize.width()); if (newOrigin.x() < 0) newOrigin.setX(0); } if (size.height() > m_tileSize.height()) { newOrigin.setY((visibleRect.y() - (minimumVerticalTiles * m_tileSize.height() - visibleRect.height()) / 2) % m_tileSize.height()); if (newOrigin.y() < 0) newOrigin.setY(0); } // Drop all existing tiles if the origin moved. if (newOrigin == m_origin) return; m_tiles.clear(); m_origin = newOrigin; } RefPtr<LegacyTileGridTile> LegacyTileGrid::tileForPoint(const IntPoint& point) const { return tileForIndex(tileIndexForPoint(point)); } bool LegacyTileGrid::tilesCover(const IntRect& rect) const { return tileForPoint(rect.location()) && tileForPoint(IntPoint(rect.maxX() - 1, rect.y())) && tileForPoint(IntPoint(rect.x(), rect.maxY() - 1)) && tileForPoint(IntPoint(rect.maxX() - 1, rect.maxY() - 1)); } void LegacyTileGrid::updateTileOpacity() { TileMap::iterator end = m_tiles.end(); for (TileMap::iterator it = m_tiles.begin(); it != end; ++it) [it->value->tileLayer() setOpaque:m_tileCache.tilesOpaque()]; } void LegacyTileGrid::updateTileBorderVisibility() { TileMap::iterator end = m_tiles.end(); for (TileMap::iterator it = m_tiles.begin(); it != end; ++it) it->value->showBorder(m_tileCache.tileBordersVisible()); } unsigned LegacyTileGrid::tileCount() const { return m_tiles.size(); } bool LegacyTileGrid::checkDoSingleTileLayout() { IntSize size = bounds().size(); if (size.width() > m_tileSize.width() || size.height() > m_tileSize.height()) return false; if (m_origin != IntPoint(0, 0)) { m_tiles.clear(); m_origin = IntPoint(0, 0); } dropInvalidTiles(); if (size.isEmpty()) { ASSERT(!m_tiles.get(TileIndex(0, 0))); return true; } TileIndex originIndex(0, 0); if (!m_tiles.get(originIndex)) m_tiles.set(originIndex, LegacyTileGridTile::create(this, tileRectForIndex(originIndex))); return true; } void LegacyTileGrid::updateHostLayerSize() { CALayer* hostLayer = m_tileCache.hostLayer(); CGRect tileHostBounds = [hostLayer convertRect:[hostLayer bounds] toLayer:tileHostLayer()]; CGSize transformedSize; transformedSize.width = CGRound(tileHostBounds.size.width); transformedSize.height = CGRound(tileHostBounds.size.height); CGRect bounds = [tileHostLayer() bounds]; if (CGSizeEqualToSize(bounds.size, transformedSize)) return; bounds.size = transformedSize; [tileHostLayer() setBounds:bounds]; } void LegacyTileGrid::dropInvalidTiles() { IntRect bounds = this->bounds(); IntRect dropBounds = intersection(m_validBounds, bounds); Vector<TileIndex> toRemove; for (const auto& tile : m_tiles) { const TileIndex& index = tile.key; const IntRect& tileRect = tile.value->rect(); IntRect expectedTileRect = tileRectForIndex(index); if (expectedTileRect != tileRect || !dropBounds.contains(tileRect)) toRemove.append(index); } unsigned removeCount = toRemove.size(); for (unsigned n = 0; n < removeCount; ++n) m_tiles.remove(toRemove[n]); m_validBounds = bounds; } void LegacyTileGrid::invalidateTiles(const IntRect& dirtyRect) { if (!hasTiles()) return; IntRect bounds = this->bounds(); if (intersection(bounds, m_validBounds) != m_validBounds) { // The bounds have got smaller. Everything outside will also be considered invalid and will be dropped by dropInvalidTiles(). // Due to dirtyRect being limited to current bounds the tiles that are temporarily outside might miss invalidation // completely othwerwise. m_validBounds = bounds; } Vector<TileIndex> invalidatedTiles; if (dirtyRect.width() > m_tileSize.width() * 4 || dirtyRect.height() > m_tileSize.height() * 4) { // For large invalidates, iterate over live tiles. TileMap::iterator end = m_tiles.end(); for (TileMap::iterator it = m_tiles.begin(); it != end; ++it) { LegacyTileGridTile* tile = it->value.get(); if (!tile->rect().intersects(dirtyRect)) continue; tile->invalidateRect(dirtyRect); invalidatedTiles.append(it->key); } } else { TileIndex topLeftIndex = tileIndexForPoint(topLeft(dirtyRect)); TileIndex bottomRightIndex = tileIndexForPoint(bottomRight(dirtyRect)); for (int yIndex = topLeftIndex.y(); yIndex <= bottomRightIndex.y(); ++yIndex) { for (int xIndex = topLeftIndex.x(); xIndex <= bottomRightIndex.x(); ++xIndex) { TileIndex index(xIndex, yIndex); RefPtr<LegacyTileGridTile> tile = tileForIndex(index); if (!tile) continue; if (!tile->rect().intersects(dirtyRect)) continue; tile->invalidateRect(dirtyRect); invalidatedTiles.append(index); } } } if (invalidatedTiles.isEmpty()) return; // When using minimal coverage, drop speculative tiles instead of updating them. if (!shouldUseMinimalTileCoverage()) return; if (m_tileCache.tilingMode() != LegacyTileCache::Minimal && m_tileCache.tilingMode() != LegacyTileCache::Normal) return; IntRect visibleRect = this->visibleRect(); unsigned count = invalidatedTiles.size(); for (unsigned i = 0; i < count; ++i) { RefPtr<LegacyTileGridTile> tile = tileForIndex(invalidatedTiles[i]); if (!tile->rect().intersects(visibleRect)) m_tiles.remove(invalidatedTiles[i]); } } bool LegacyTileGrid::shouldUseMinimalTileCoverage() const { return m_tileCache.tilingMode() == LegacyTileCache::Minimal || !m_tileCache.isSpeculativeTileCreationEnabled() || MemoryPressureHandler::singleton().isUnderMemoryPressure(); } IntRect LegacyTileGrid::adjustCoverRectForPageBounds(const IntRect& rect) const { // Adjust the rect so that it stays within the bounds and keeps the pixel size. IntRect bounds = this->bounds(); IntRect adjustedRect = rect; adjustedRect.move(rect.x() < bounds.x() ? bounds.x() - rect.x() : 0, rect.y() < bounds.y() ? bounds.y() - rect.y() : 0); adjustedRect.move(rect.maxX() > bounds.maxX() ? bounds.maxX() - rect.maxX() : 0, rect.maxY() > bounds.maxY() ? bounds.maxY() - rect.maxY() : 0); adjustedRect = intersection(bounds, adjustedRect); if (adjustedRect == rect || adjustedRect.isEmpty() || shouldUseMinimalTileCoverage()) return adjustedRect; int pixels = adjustedRect.width() * adjustedRect.height(); if (adjustedRect.width() != rect.width()) adjustedRect.inflateY((pixels / adjustedRect.width() - adjustedRect.height()) / 2); else if (adjustedRect.height() != rect.height()) adjustedRect.inflateX((pixels / adjustedRect.height() - adjustedRect.width()) / 2); return intersection(adjustedRect, bounds); } IntRect LegacyTileGrid::calculateCoverRect(const IntRect& visibleRect, bool& centerGrid) { // Use minimum coverRect if we are under memory pressure. if (shouldUseMinimalTileCoverage()) { centerGrid = true; return visibleRect; } IntRect coverRect = visibleRect; centerGrid = false; coverRect.inflateX(visibleRect.width() / 2); coverRect.inflateY(visibleRect.height()); return adjustCoverRectForPageBounds(coverRect); } double LegacyTileGrid::tileDistance2(const IntRect& visibleRect, const IntRect& tileRect) const { // The "distance" calculated here is used to pick which tile to cache next. The idea is to create those // closest to the current viewport first so the user is more likely to see already rendered content we she // scrolls. The calculation is weighted to prefer vertical and downward direction. if (visibleRect.intersects(tileRect)) return 0; IntPoint visibleCenter = visibleRect.location() + IntSize(visibleRect.width() / 2, visibleRect.height() / 2); IntPoint tileCenter = tileRect.location() + IntSize(tileRect.width() / 2, tileRect.height() / 2); double horizontalBias = 1.0; double leftwardBias = 1.0; double rightwardBias = 1.0; double verticalBias = 1.0; double upwardBias = 1.0; double downwardBias = 1.0; const double tilingBiasVeryLikely = 0.8; const double tilingBiasLikely = 0.9; switch (m_tileCache.tilingDirection()) { case LegacyTileCache::TilingDirectionUp: verticalBias = tilingBiasVeryLikely; upwardBias = tilingBiasLikely; break; case LegacyTileCache::TilingDirectionDown: verticalBias = tilingBiasVeryLikely; downwardBias = tilingBiasLikely; break; case LegacyTileCache::TilingDirectionLeft: horizontalBias = tilingBiasVeryLikely; leftwardBias = tilingBiasLikely; break; case LegacyTileCache::TilingDirectionRight: horizontalBias = tilingBiasVeryLikely; rightwardBias = tilingBiasLikely; break; } double xScale = horizontalBias * visibleRect.height() / visibleRect.width() * (tileCenter.x() >= visibleCenter.x() ? rightwardBias : leftwardBias); double yScale = verticalBias * visibleRect.width() / visibleRect.height() * (tileCenter.y() >= visibleCenter.y() ? downwardBias : upwardBias); double xDistance = xScale * (tileCenter.x() - visibleCenter.x()); double yDistance = yScale * (tileCenter.y() - visibleCenter.y()); double distance2 = xDistance * xDistance + yDistance * yDistance; return distance2; } void LegacyTileGrid::createTiles(LegacyTileCache::SynchronousTileCreationMode creationMode) { IntRect visibleRect = this->visibleRect(); if (visibleRect.isEmpty()) return; // Drop tiles that are wrong size or outside the frame (because the frame has been resized). dropInvalidTiles(); bool centerGrid; IntRect coverRect = calculateCoverRect(visibleRect, centerGrid); // If tile size is bigger than the view, centering minimizes the painting needed to cover the screen. // This is especially useful after zooming centerGrid = centerGrid || !tileCount(); if (centerGrid) centerTileGridOrigin(visibleRect); double shortestDistance = std::numeric_limits<double>::infinity(); double coveredDistance = 0; Vector<LegacyTileGrid::TileIndex> tilesToCreate; unsigned pendingTileCount = 0; LegacyTileGrid::TileIndex topLeftIndex = tileIndexForPoint(topLeft(coverRect)); LegacyTileGrid::TileIndex bottomRightIndex = tileIndexForPoint(bottomRight(coverRect)); for (int yIndex = topLeftIndex.y(); yIndex <= bottomRightIndex.y(); ++yIndex) { for (int xIndex = topLeftIndex.x(); xIndex <= bottomRightIndex.x(); ++xIndex) { LegacyTileGrid::TileIndex index(xIndex, yIndex); // Currently visible tiles have distance of 0 and get all created in the same transaction. double distance = tileDistance2(visibleRect, tileRectForIndex(index)); if (distance > coveredDistance) coveredDistance = distance; if (tileForIndex(index)) continue; ++pendingTileCount; if (distance > shortestDistance) continue; if (distance < shortestDistance) { tilesToCreate.clear(); shortestDistance = distance; } tilesToCreate.append(index); } } size_t tilesToCreateCount = tilesToCreate.size(); // Tile creation timer will invoke this function again in CoverSpeculative mode. bool candidateTilesAreSpeculative = shortestDistance > 0; if (creationMode == LegacyTileCache::CoverVisibleOnly && candidateTilesAreSpeculative) tilesToCreateCount = 0; // Even if we don't create any tiles, we should still drop distant tiles // in case coverRect got smaller. double keepDistance = std::min(shortestDistance, coveredDistance); if (!dropDistantTiles(tilesToCreateCount, keepDistance)) return; ASSERT(pendingTileCount >= tilesToCreateCount); if (!pendingTileCount) return; for (size_t n = 0; n < tilesToCreateCount; ++n) addTileForIndex(tilesToCreate[n]); bool didCreateTiles = !!tilesToCreateCount; bool createMoreTiles = pendingTileCount > tilesToCreateCount; m_tileCache.finishedCreatingTiles(didCreateTiles, createMoreTiles); } void LegacyTileGrid::dumpTiles() { IntRect visibleRect = this->visibleRect(); NSLog(@"transformed visibleRect = [%6d %6d %6d %6d]", visibleRect.x(), visibleRect.y(), visibleRect.width(), visibleRect.height()); unsigned i = 0; TileMap::iterator end = m_tiles.end(); for (TileMap::iterator it = m_tiles.begin(); it != end; ++it) { TileIndex& index = it->key; IntRect tileRect = it->value->rect(); NSLog(@"#%-3d (%3d %3d) - [%6d %6d %6d %6d]%@", ++i, index.x(), index.y(), tileRect.x(), tileRect.y(), tileRect.width(), tileRect.height(), tileRect.intersects(visibleRect) ? @" *" : @""); NSLog(@" %@", [it->value->tileLayer() contents]); } } } // namespace WebCore #endif // PLATFORM(IOS)