[core] retain tiles differently and remove old TileID class

25 files changed, 857 insertions, 673 deletions

diff --git a/include/mbgl/storage/offline.hpp b/include/mbgl/storage/offline.hpp
index fc0bf7f01e..e0c5ba6247 100644
--- a/include/mbgl/storage/offline.hpp
+++ b/include/mbgl/storage/offline.hpp
@@ -30,7 +30,7 @@ public:
     OfflineTilePyramidRegionDefinition(const std::string&, const LatLngBounds&, double, double, float);
 
     /* Private */
-    std::vector<TileID> tileCover(SourceType, uint16_t tileSize, const SourceInfo&) const;
+    std::vector<CanonicalTileID> tileCover(SourceType, uint16_t tileSize, const SourceInfo&) const;
 
     const std::string styleURL;
     const LatLngBounds bounds;
diff --git a/platform/default/mbgl/storage/offline.cpp b/platform/default/mbgl/storage/offline.cpp
index 931e079771..b13aa05039 100644
--- a/platform/default/mbgl/storage/offline.cpp
+++ b/platform/default/mbgl/storage/offline.cpp
@@ -23,20 +23,20 @@ OfflineTilePyramidRegionDefinition::OfflineTilePyramidRegionDefinition(
     }
 }
 
-std::vector<TileID> OfflineTilePyramidRegionDefinition::tileCover(SourceType type, uint16_t tileSize, const SourceInfo& info) const {
-    double minZ = std::max<double>(coveringZoomLevel(minZoom, type, tileSize), info.minZoom);
-    double maxZ = std::min<double>(coveringZoomLevel(maxZoom, type, tileSize), info.maxZoom);
+std::vector<CanonicalTileID> OfflineTilePyramidRegionDefinition::tileCover(SourceType type, uint16_t tileSize, const SourceInfo& info) const {
+    double minZ = std::max<double>(util::coveringZoomLevel(minZoom, type, tileSize), info.minZoom);
+    double maxZ = std::min<double>(util::coveringZoomLevel(maxZoom, type, tileSize), info.maxZoom);
 
     assert(minZ >= 0);
     assert(maxZ >= 0);
     assert(minZ < std::numeric_limits<uint8_t>::max());
     assert(maxZ < std::numeric_limits<uint8_t>::max());
 
-    std::vector<TileID> result;
+    std::vector<CanonicalTileID> result;
 
     for (uint8_t z = minZ; z <= maxZ; z++) {
-        for (const auto& tile : mbgl::tileCover(bounds, z, z)) {
-            result.push_back(tile.normalized());
+        for (const auto& tile : util::tileCover(bounds, z)) {
+            result.emplace_back(tile.canonical);
         }
     }
 
diff --git a/platform/default/mbgl/storage/offline_database.cpp b/platform/default/mbgl/storage/offline_database.cpp
index 7826d140a1..52ab6504fa 100644
--- a/platform/default/mbgl/storage/offline_database.cpp
+++ b/platform/default/mbgl/storage/offline_database.cpp
@@ -4,7 +4,6 @@
 #include <mbgl/util/io.hpp>
 #include <mbgl/util/string.hpp>
 #include <mbgl/util/chrono.hpp>
-#include <mbgl/map/tile_id.hpp>
 #include <mbgl/platform/log.hpp>
 
 #include "sqlite3.hpp"
diff --git a/src/mbgl/algorithm/update_renderables.cpp b/src/mbgl/algorithm/update_renderables.cpp
new file mode 100644
index 0000000000..7b571308c7
--- /dev/null
+++ b/src/mbgl/algorithm/update_renderables.cpp
@@ -0,0 +1,10 @@
+#include <mbgl/algorithm/update_renderables_impl.hpp>
+#include <mbgl/style/style_layer.hpp>
+
+namespace mbgl {
+namespace algorithm {
+
+//template void updateRenderables(StyleLayer& layer, const uint8_t z);
+
+} // namespace algorithm
+} // namespace mbgl
diff --git a/src/mbgl/algorithm/update_renderables.hpp b/src/mbgl/algorithm/update_renderables.hpp
new file mode 100644
index 0000000000..a1fa6b1e6c
--- /dev/null
+++ b/src/mbgl/algorithm/update_renderables.hpp
@@ -0,0 +1,15 @@
+#ifndef MBGL_ALGORITHM_UPDATE_RENDERABLES
+#define MBGL_ALGORITHM_UPDATE_RENDERABLES
+
+#include <cstdint>
+
+namespace mbgl {
+namespace algorithm {
+
+template <typename Layer>
+void updateRenderables(Layer& layer, const uint8_t z);
+
+} // namespace algorithm
+} // namespace mbgl
+
+#endif
diff --git a/src/mbgl/algorithm/update_renderables_impl.hpp b/src/mbgl/algorithm/update_renderables_impl.hpp
new file mode 100644
index 0000000000..d7221be21c
--- /dev/null
+++ b/src/mbgl/algorithm/update_renderables_impl.hpp
@@ -0,0 +1,93 @@
+#ifndef MBGL_ALGORITHM_UPDATE_RENDERABLES_IMPL
+#define MBGL_ALGORITHM_UPDATE_RENDERABLES_IMPL
+
+#include <mbgl/algorithm/update_renderables.hpp>
+#include <mbgl/tile/tile_id.hpp>
+
+#include <map>
+
+namespace mbgl {
+namespace algorithm {
+
+namespace {
+
+template <typename DataTiles, typename Renderables>
+bool tryTile(const UnwrappedTileID& renderTileID,
+             const OverscaledTileID& dataTileID,
+             const DataTiles& dataTiles,
+             Renderables& renderables) {
+    if (renderables.find(renderTileID) == renderables.end()) {
+        const auto it = dataTiles.find(dataTileID);
+        if (it == dataTiles.end() || !it->second->isReady()) {
+            return false;
+        }
+
+        using Renderable = typename Renderables::mapped_type;
+        renderables.emplace(renderTileID, Renderable{ renderTileID, *it->second });
+    }
+
+    return true;
+}
+
+} // namespace
+
+template <typename Renderable, typename DataTiles, typename IdealTileIDs, typename SourceInfo>
+std::map<UnwrappedTileID, Renderable> updateRenderables(const DataTiles& dataTiles,
+                                                        const IdealTileIDs& idealTileIDs,
+                                                        const SourceInfo& info,
+                                                        const uint8_t z) {
+    std::map<UnwrappedTileID, Renderable> renderables;
+
+    // for (all in the set of ideal tiles of the source) {
+    for (const auto& renderTileID : idealTileIDs) {
+        assert(renderTileID.canonical.z >= info.minZoom);
+        assert(renderTileID.canonical.z <= info.maxZoom);
+        assert(z >= renderTileID.canonical.z);
+        const auto wrap = renderTileID.wrap;
+        const OverscaledTileID dataTileID(z, renderTileID.canonical);
+
+        // if (source has the tile and bucket is loaded) {
+        if (!tryTile(renderTileID, dataTileID, dataTiles, renderables)) {
+            // The source doesn't have the tile, or the bucket isn't loaded.
+            bool covered = true;
+            int32_t overscaledZ = z + 1;
+            if (overscaledZ > info.maxZoom) {
+                // We're looking for an overzoomed child tile.
+                const auto childDataTileID = dataTileID.scaledTo(overscaledZ);
+                if (!tryTile(renderTileID, childDataTileID, dataTiles, renderables)) {
+                    covered = false;
+                }
+            } else {
+                // Check all four actual child tiles.
+                for (const auto& childTileID : dataTileID.canonical.children()) {
+                    const OverscaledTileID childDataTileID(overscaledZ, childTileID);
+                    const UnwrappedTileID childRenderTileID(wrap, childTileID);
+                    if (!tryTile(childRenderTileID, childDataTileID, dataTiles, renderables)) {
+                        // At least one child tile doesn't exist, so we are going to look for
+                        // parents as well.
+                        covered = false;
+                    }
+                }
+            }
+
+            if (!covered) {
+                // We couldn't find child tiles that entirely cover the ideal tile.
+                for (overscaledZ = z - 1; overscaledZ >= info.minZoom; --overscaledZ) {
+                    const auto parentDataTileID = dataTileID.scaledTo(overscaledZ);
+                    const auto parentRenderTileID = parentDataTileID.unwrapTo(renderTileID.wrap);
+                    if (tryTile(parentRenderTileID, parentDataTileID, dataTiles, renderables)) {
+                        // Break parent tile ascent, since we found one.
+                        break;
+                    }
+                }
+            }
+        }
+    }
+
+    return renderables;
+}
+
+} // namespace algorithm
+} // namespace mbgl
+
+#endif
diff --git a/src/mbgl/map/tile_id.cpp b/src/mbgl/map/tile_id.cpp
deleted file mode 100644
index b47cf158a2..0000000000
--- a/src/mbgl/map/tile_id.cpp
+++ /dev/null
@@ -1,71 +0,0 @@
-#include <mbgl/map/tile_id.hpp>
-#include <mbgl/util/string.hpp>
-#include <mbgl/util/constants.hpp>
-
-#include <cassert>
-
-namespace mbgl {
-
-float TileID::pixelsToTileUnits(float pixelValue, float zoom) const {
-    return pixelValue * (util::EXTENT / (util::tileSize * overscaleFactor() * std::pow(2, zoom - z)));
-}
-
-TileID TileID::parent(uint8_t parent_z, uint8_t sourceMaxZoom) const {
-    assert(parent_z < z);
-    auto newX = x;
-    auto newY = y;
-    for (auto newZ = z; newZ > parent_z; newZ--) {
-        if (newZ > sourceMaxZoom) {
-            // the id represents an overscaled tile, return the same coordinates with a lower z
-            // do nothing
-        } else {
-            newX = newX / 2;
-            newY = newY / 2;
-        }
-    }
-
-    return TileID{parent_z, newX, newY, parent_z > sourceMaxZoom ? sourceMaxZoom : parent_z};
-}
-
-std::forward_list<TileID> TileID::children(uint8_t sourceMaxZoom) const {
-    auto childZ = z + 1;
-
-    std::forward_list<TileID> child_ids;
-    if (z >= sourceMaxZoom) {
-        // return a single tile id representing a an overscaled tile
-        child_ids.emplace_front(childZ, x, y, sourceMaxZoom);
-
-    } else {
-        auto childX = x * 2;
-        auto childY = y * 2;
-        child_ids.emplace_front(childZ, childX, childY, childZ);
-        child_ids.emplace_front(childZ, childX + 1, childY, childZ);
-        child_ids.emplace_front(childZ, childX, childY + 1, childZ);
-        child_ids.emplace_front(childZ, childX + 1, childY + 1, childZ);
-    }
-
-    return child_ids;
-}
-
-TileID TileID::normalized() const {
-    int32_t dim = std::pow(2, sourceZ);
-    int32_t nx = x, ny = y;
-    while (nx < 0) nx += dim;
-    while (nx >= dim) nx -= dim;
-    return TileID { z, nx, ny, sourceZ};
-}
-
-bool TileID::isChildOf(const TileID &parent_id) const {
-    if (parent_id.z >= z || parent_id.w != w) {
-        return false;
-    }
-    int32_t scale = std::pow(2, z - parent_id.z);
-    return parent_id.x == ((x < 0 ? x - scale + 1 : x) / scale) &&
-           parent_id.y == y / scale;
-}
-
-TileID::operator std::string() const {
-    return util::toString(z) + "/" + util::toString(x) + "/" + util::toString(y);
-}
-
-} // namespace mbgl
diff --git a/src/mbgl/map/tile_id.hpp b/src/mbgl/map/tile_id.hpp
deleted file mode 100644
index 47cdd3b4d9..0000000000
--- a/src/mbgl/map/tile_id.hpp
+++ /dev/null
@@ -1,71 +0,0 @@
-#ifndef MBGL_MAP_TILE_ID
-#define MBGL_MAP_TILE_ID
-
-#include <cstdint>
-#include <cmath>
-#include <string>
-#include <functional>
-#include <forward_list>
-#include <limits>
-
-namespace mbgl {
-
-class TileID {
-public:
-    const int16_t w = 0;
-    const uint8_t z;
-    const int32_t x;
-    const int32_t y;
-    const uint8_t sourceZ;
-
-    explicit TileID(uint8_t z_, int32_t x_, int32_t y_, uint8_t sourceZ_)
-        : w((x_ < 0 ? x_ - (1 << z_) + 1 : x_) / (1 << z_)), z(z_), x(x_), y(y_),
-        sourceZ(sourceZ_) {}
-
-    uint64_t to_uint64() const {
-        return ((std::pow(2, z) * y + x) * 32) + z;
-    }
-
-    uint32_t overscaleFactor() const {
-        return static_cast<uint32_t>(1) << (z - sourceZ);
-    }
-
-    bool operator==(const TileID& rhs) const {
-        return w == rhs.w && z == rhs.z && x == rhs.x && y == rhs.y;
-    }
-
-    bool operator!=(const TileID& rhs) const {
-        return !operator==(rhs);
-    }
-
-    bool operator<(const TileID& rhs) const {
-        if (w != rhs.w) return w < rhs.w;
-        if (z != rhs.z) return z < rhs.z;
-        if (x != rhs.x) return x < rhs.x;
-        return y < rhs.y;
-    }
-
-    float pixelsToTileUnits(float pixelValue, float zoom) const;
-    TileID parent(uint8_t z, uint8_t sourceMaxZoom) const;
-    TileID normalized() const;
-    std::forward_list<TileID>
-    children(uint8_t sourceMaxZoom = std::numeric_limits<uint8_t>::max()) const;
-    bool isChildOf(const TileID&) const;
-    operator std::string() const;
-};
-
-} // namespace mbgl
-
-namespace std {
-template <>
-struct hash<mbgl::TileID> {
-    typedef mbgl::TileID argument_type;
-    typedef std::size_t result_type;
-
-    result_type operator()(const mbgl::TileID& id) const {
-            return std::hash<uint64_t>()(id.to_uint64());
-    }
-};
-} // namespace std
-
-#endif
diff --git a/src/mbgl/renderer/painter.cpp b/src/mbgl/renderer/painter.cpp
index 6e2da79db8..e993e3dddf 100644
--- a/src/mbgl/renderer/painter.cpp
+++ b/src/mbgl/renderer/painter.cpp
@@ -153,8 +153,7 @@ void Painter::render(const Style& style, const FrameData& frame_, SpriteAtlas& a
         for (const auto& source : sources) {
             if (source->type == SourceType::Vector || source->type == SourceType::GeoJSON ||
                 source->type == SourceType::Annotations) {
-                auto renderables = source->getRenderables();
-                generator.update(renderables);
+                source->updateClipIDs(generator);
             }
             source->updateMatrices(projMatrix, state);
         }
@@ -253,7 +252,6 @@ void Painter::renderPass(RenderPass pass_,
             layer.as<CustomLayer>()->render(state);
             config.setDirty();
         } else {
-            assert(item.tile->data);
             MBGL_DEBUG_GROUP(layer.id + " - " + util::toString(item.tile->id));
             if (item.bucket->needsClipping()) {
                 setClipping(item.tile->clip);
diff --git a/src/mbgl/renderer/painter_background.cpp b/src/mbgl/renderer/painter_background.cpp
index 658d6535f6..e71e9677d1 100644
--- a/src/mbgl/renderer/painter_background.cpp
+++ b/src/mbgl/renderer/painter_background.cpp
@@ -55,12 +55,11 @@ void Painter::renderBackground(const BackgroundLayer& layer) {
     config.depthMask = GL_FALSE;
     setDepthSublayer(0);
 
-    auto tileIDs = tileCover(state, state.getIntegerZoom(), state.getIntegerZoom());
+    auto tileIDs = util::tileCover(state, state.getIntegerZoom());
 
-    for (auto &id: tileIDs) {
+    for (auto& id : tileIDs) {
         mat4 vtxMatrix;
-        const UnwrappedTileID tileID(id.z, id.x, id.y);
-        state.matrixFor(vtxMatrix, tileID);
+        state.matrixFor(vtxMatrix, id);
         matrix::multiply(vtxMatrix, projMatrix, vtxMatrix);
 
         if (isPatterned) {
@@ -84,11 +83,15 @@ void Painter::renderBackground(const BackgroundLayer& layer) {
                 1.0f / id.pixelsToTileUnits(imageSizeScaledB[1], state.getIntegerZoom())
             }};
 
-            float offsetAx = (std::fmod(util::tileSize, imageSizeScaledA[0]) * id.x) / (float)imageSizeScaledA[0];
-            float offsetAy = (std::fmod(util::tileSize, imageSizeScaledA[1]) * id.y) / (float)imageSizeScaledA[1];
+            float offsetAx = (std::fmod(util::tileSize, imageSizeScaledA[0]) * id.canonical.x) /
+                             (float)imageSizeScaledA[0];
+            float offsetAy = (std::fmod(util::tileSize, imageSizeScaledA[1]) * id.canonical.y) /
+                             (float)imageSizeScaledA[1];
 
-            float offsetBx = (std::fmod(util::tileSize, imageSizeScaledB[0]) * id.x) / (float)imageSizeScaledB[0];
-            float offsetBy = (std::fmod(util::tileSize, imageSizeScaledB[1]) * id.y) / (float)imageSizeScaledB[1];
+            float offsetBx = (std::fmod(util::tileSize, imageSizeScaledB[0]) * id.canonical.x) /
+                             (float)imageSizeScaledB[0];
+            float offsetBy = (std::fmod(util::tileSize, imageSizeScaledB[1]) * id.canonical.y) /
+                             (float)imageSizeScaledB[1];
 
             patternShader->u_offset_a = std::array<float, 2>{{offsetAx, offsetAy}};
             patternShader->u_offset_b = std::array<float, 2>{{offsetBx, offsetBy}};
diff --git a/src/mbgl/renderer/painter_debug.cpp b/src/mbgl/renderer/painter_debug.cpp
index 6139eff9d4..ac23310b3d 100644
--- a/src/mbgl/renderer/painter_debug.cpp
+++ b/src/mbgl/renderer/painter_debug.cpp
@@ -10,11 +10,10 @@ using namespace mbgl;
 
 void Painter::renderTileDebug(const Tile& tile) {
     MBGL_DEBUG_GROUP(std::string { "debug " } + util::toString(tile.id));
-    assert(tile.data);
     if (frame.debugOptions != MapDebugOptions::NoDebug) {
         setClipping(tile.clip);
         if (frame.debugOptions & (MapDebugOptions::Timestamps | MapDebugOptions::ParseStatus)) {
-            renderDebugText(*tile.data, tile.matrix);
+            renderDebugText(tile.data, tile.matrix);
         }
         if (frame.debugOptions & MapDebugOptions::TileBorders) {
             renderDebugFrame(tile.matrix);
diff --git a/src/mbgl/source/source.cpp b/src/mbgl/source/source.cpp
index d00cbdb034..167a1d2714 100644
--- a/src/mbgl/source/source.cpp
+++ b/src/mbgl/source/source.cpp
@@ -26,6 +26,8 @@
 #include <mbgl/style/style_parser.hpp>
 #include <mbgl/gl/debugging.hpp>
 
+#include <mbgl/algorithm/update_renderables_impl.hpp>
+
 #include <mapbox/geojsonvt.hpp>
 #include <mapbox/geojsonvt/convert.hpp>
 
@@ -55,8 +57,8 @@ Source::~Source() = default;
 bool Source::isLoaded() const {
     if (!loaded) return false;
 
-    for (const auto& tile : tiles) {
-        if (tile.second->data->getState() != TileData::State::parsed) {
+    for (const auto& pair : tileDataMap) {
+        if (pair.second->getState() != TileData::State::parsed) {
             return false;
         }
     }
@@ -148,7 +150,6 @@ void Source::load(FileSource& fileSource) {
 
             if (reloadTiles) {
                 // Tile information changed because we got new GeoJSON data, or a new tile URL.
-                tilePtrs.clear();
                 tileDataMap.clear();
                 tiles.clear();
                 cache.clear();
@@ -161,196 +162,66 @@ void Source::load(FileSource& fileSource) {
 }
 
 void Source::updateMatrices(const mat4 &projMatrix, const TransformState &transform) {
-    for (const auto& pair : tiles) {
-        auto& tile = *pair.second;
+    for (auto& pair : tiles) {
+        auto& tile = pair.second;
         transform.matrixFor(tile.matrix, tile.id);
         matrix::multiply(tile.matrix, projMatrix, tile.matrix);
     }
 }
 
 void Source::finishRender(Painter &painter) {
-    for (const auto& pair : tiles) {
-        Tile &tile = *pair.second;
+    for (auto& pair : tiles) {
+        auto& tile = pair.second;
         painter.renderTileDebug(tile);
     }
 }
 
-std::map<UnwrappedTileID, Renderable> Source::getRenderables() const {
-    std::map<UnwrappedTileID, Renderable> renderables;
-    for (const auto& pair : tiles) {
-        auto& tile = *pair.second;
-        if (tile.data->isReady() && tile.data->hasData()) {
-            renderables.emplace(tile.id, Renderable{ tile.clip });
-        }
-    }
-    return renderables;
-}
-
-const std::vector<Tile*>& Source::getTiles() const {
-    return tilePtrs;
-}
-
-TileData::State Source::hasTile(const TileID& tileID) {
-    auto it = tiles.find(tileID);
-    if (it != tiles.end()) {
-        Tile& tile = *it->second;
-        if (it->first == tileID && tile.data) {
-            return tile.data->getState();
-        }
-    }
-
-    return TileData::State::invalid;
+const std::map<UnwrappedTileID, Tile>& Source::getTiles() const {
+    return tiles;
 }
 
-bool Source::handlePartialTile(const TileID& tileID) {
-    const OverscaledTileID overscaledTileID{
-        tileID.z, UnwrappedTileID{ tileID.sourceZ, tileID.x, tileID.y }.canonical
-    };
-
-    auto it = tileDataMap.find(overscaledTileID);
-    if (it == tileDataMap.end()) {
-        return true;
-    }
-
-    auto tileData = it->second.lock();
-    if (!tileData) {
-        return true;
+std::unique_ptr<TileData> Source::createTile(const OverscaledTileID& overscaledTileID,
+                                             const StyleUpdateParameters& parameters) {
+    std::unique_ptr<TileData> data = cache.get(overscaledTileID);
+    if (data) {
+        return data;
     }
 
     auto callback = std::bind(&Source::tileLoadingCallback, this, overscaledTileID,
-            std::placeholders::_1, false);
-
-    return tileData->parsePending(callback);
-}
-
-TileData::State Source::addTile(const TileID& tileID, const StyleUpdateParameters& parameters) {
-    const TileData::State state = hasTile(tileID);
-
-    if (state != TileData::State::invalid) {
-        return state;
-    }
-
-    auto newTile = std::make_unique<Tile>(UnwrappedTileID{ tileID.sourceZ, tileID.x, tileID.y });
-
-    // We couldn't find the tile in the list. Create a new one.
-    // Try to find the associated TileData object.
-    const OverscaledTileID overscaledTileID{ tileID.z, newTile->id.canonical };
-
-    auto it = tileDataMap.find(overscaledTileID);
-    if (it != tileDataMap.end()) {
-        // Create a shared_ptr handle. Note that this might be empty!
-        newTile->data = it->second.lock();
-    }
-
-    if (newTile->data && newTile->data->getState() == TileData::State::obsolete) {
-        // Do not consider the tile if it's already obsolete.
-        newTile->data.reset();
-    }
-
-    if (!newTile->data) {
-        newTile->data = cache.get(overscaledTileID);
-    }
-
-    if (!newTile->data) {
-        auto callback = std::bind(&Source::tileLoadingCallback, this, overscaledTileID,
-                                  std::placeholders::_1, true);
-
-        // If we don't find working tile data, we're just going to load it.
-        if (type == SourceType::Raster) {
-            newTile->data = std::make_shared<RasterTileData>(overscaledTileID,
-                                                             parameters.pixelRatio,
-                                                             info->tiles.at(0),
-                                                             parameters.texturePool,
-                                                             parameters.worker,
-                                                             parameters.fileSource,
-                                                             callback);
+                              std::placeholders::_1, true);
+
+    // If we don't find working tile data, we're just going to load it.
+    if (type == SourceType::Raster) {
+        data = std::make_unique<RasterTileData>(overscaledTileID, parameters.pixelRatio,
+                                                info->tiles.at(0), parameters.texturePool,
+                                                parameters.worker, parameters.fileSource, callback);
+    } else {
+        std::unique_ptr<GeometryTileMonitor> monitor;
+
+        if (type == SourceType::Vector) {
+            monitor = std::make_unique<VectorTileMonitor>(overscaledTileID, parameters.pixelRatio, info->tiles.at(0), parameters.fileSource);
+        } else if (type == SourceType::Annotations) {
+            monitor = std::make_unique<AnnotationTileMonitor>(overscaledTileID, parameters.annotationManager);
+        } else if (type == SourceType::GeoJSON) {
+            monitor = std::make_unique<GeoJSONTileMonitor>(geojsonvt.get(), overscaledTileID);
         } else {
-            std::unique_ptr<GeometryTileMonitor> monitor;
-
-            if (type == SourceType::Vector) {
-                monitor = std::make_unique<VectorTileMonitor>(overscaledTileID, parameters.pixelRatio, info->tiles.at(0), parameters.fileSource);
-            } else if (type == SourceType::Annotations) {
-                monitor = std::make_unique<AnnotationTileMonitor>(overscaledTileID, parameters.annotationManager);
-            } else if (type == SourceType::GeoJSON) {
-                monitor = std::make_unique<GeoJSONTileMonitor>(geojsonvt.get(), overscaledTileID);
-            } else {
-                Log::Warning(Event::Style, "Source type '%s' is not implemented", SourceTypeClass(type).c_str());
-                return TileData::State::invalid;
-            }
-
-            newTile->data = std::make_shared<VectorTileData>(overscaledTileID,
-                                                             std::move(monitor),
-                                                             id,
-                                                             parameters.style,
-                                                             parameters.mode,
-                                                             callback);
+            Log::Warning(Event::Style, "Source type '%s' is not implemented", SourceTypeClass(type).c_str());
+            return nullptr;
         }
 
-        tileDataMap.emplace(newTile->data->id, newTile->data);
+        data = std::make_unique<VectorTileData>(overscaledTileID, std::move(monitor), id,
+                                                parameters.style, parameters.mode, callback);
     }
 
-    const auto newState = newTile->data->getState();
-    tiles.emplace(tileID, std::move(newTile));
-    return newState;
-}
-
-/**
- * Recursively find children of the given tile that are already loaded.
- *
- * @param id The tile ID that we should find children for.
- * @param maxCoveringZoom The maximum zoom level of children to look for.
- * @param retain An object that we add the found tiles to.
- *
- * @return boolean Whether the children found completely cover the tile.
- */
-bool Source::findLoadedChildren(const TileID& tileID, int32_t maxCoveringZoom, std::vector<TileID>& retain) {
-    bool complete = true;
-    int32_t z = tileID.z;
-    auto ids = tileID.children(info->maxZoom);
-    for (const auto& child_id : ids) {
-        const TileData::State state = hasTile(child_id);
-        if (TileData::isReadyState(state)) {
-            retain.emplace_back(child_id);
-        }
-        if (state != TileData::State::parsed) {
-            complete = false;
-            if (z < maxCoveringZoom) {
-                // Go further down the hierarchy to find more unloaded children.
-                findLoadedChildren(child_id, maxCoveringZoom, retain);
-            }
-        }
-    }
-    return complete;
+    return data;
 }
 
-/**
- * Find a loaded parent of the given tile.
- *
- * @param id The tile ID that we should find children for.
- * @param minCoveringZoom The minimum zoom level of parents to look for.
- * @param retain An object that we add the found tiles to.
- *
- * @return boolean Whether a parent was found.
- */
-void Source::findLoadedParent(const TileID& tileID, int32_t minCoveringZoom, std::vector<TileID>& retain, const StyleUpdateParameters& parameters) {
-    for (int32_t z = tileID.z - 1; z >= minCoveringZoom; --z) {
-        const TileID parent_id = tileID.parent(z, info->maxZoom);
-        const TileData::State state = hasTile(parent_id);
-        if (TileData::isReadyState(state)) {
-            retain.emplace_back(parent_id);
-            if (state == TileData::State::parsed) {
-                return;
-            }
-        }
-
-        const UnwrappedTileID unwrappedTileID(tileID.sourceZ, static_cast<uint32_t>(tileID.x),
-                                              static_cast<uint32_t>(tileID.y));
-
-        if (cache.has(OverscaledTileID{ tileID.z, unwrappedTileID.canonical })) {
-            addTile(parent_id, parameters);
-            retain.emplace_back(parent_id);
-            return;
-        }
+TileData* Source::getTileData(const OverscaledTileID& overscaledTileID) const {
+    auto it = tileDataMap.find(overscaledTileID);
+    if (it != tileDataMap.end()) {
+        return it->second.get();
+    } else {
+        return nullptr;
     }
 }
 
@@ -362,116 +233,89 @@ bool Source::update(const StyleUpdateParameters& parameters) {
     }
 
     // Determine the overzooming/underzooming amounts and required tiles.
-    std::vector<TileID> required;
-    int32_t zoom = coveringZoomLevel(parameters.transformState.getZoom(), type, tileSize);
-    int32_t minCoveringZoom = util::clamp<int32_t>(zoom - 10, info->minZoom, info->maxZoom);
-    int32_t maxCoveringZoom = util::clamp<int32_t>(zoom + 1,  info->minZoom, info->maxZoom);
+    int32_t overscaledZoom = util::coveringZoomLevel(parameters.transformState.getZoom(), type, tileSize);
+    int32_t dataTileZoom = overscaledZoom;
 
-    if (zoom >= info->minZoom) {
-        const bool reparseOverscaled = type != SourceType::Raster;
+    std::vector<UnwrappedTileID> idealTiles;
+    if (overscaledZoom >= info->minZoom) {
+        int32_t idealZoom = std::min<int32_t>(info->maxZoom, overscaledZoom);
 
-        const auto actualZ = zoom;
-        if (zoom > info->maxZoom) {
-            zoom = info->maxZoom;
+        // Make sure we're not reparsing overzoomed raster tiles.
+        if (type == SourceType::Raster) {
+            dataTileZoom = idealZoom;
         }
 
-        required = tileCover(parameters.transformState, zoom, reparseOverscaled ? actualZ : zoom);
-    }
+        idealTiles = util::tileCover(parameters.transformState, idealZoom);
+   }
 
-    // Retain is a list of tiles that we shouldn't delete, even if they are not
-    // the most ideal tile for the current viewport. This may include tiles like
-    // parent or child tiles that are *already* loaded.
-    std::vector<TileID> retain(required);
+    // Stores a list of all the data tiles that we're definitely going to retain. There are two
+    // kinds of tiles we need: the ideal tiles determined by the tile cover. They may not yet be in
+    // use because they're still loading. In addition to that, we also need to retain all tiles that
+    // we're actively using, e.g. as a replacement for tile that aren't loaded yet.
+    std::set<OverscaledTileID> retain;
 
-    // Add existing child/parent tiles if the actual tile is not yet loaded
-    for (const auto& tileID : required) {
-        TileData::State state = hasTile(tileID);
+    // Create all tiles that we definitely want to load
+    for (const auto& unwrappedTileID : idealTiles) {
+        const OverscaledTileID dataTileID(dataTileZoom, unwrappedTileID.canonical);
+        retain.emplace(dataTileID);
 
-        switch (state) {
-        case TileData::State::partial:
-            if (parameters.shouldReparsePartialTiles) {
-                if (!handlePartialTile(tileID)) {
-                    allTilesUpdated = false;
-                }
+        auto it = tileDataMap.find(dataTileID);
+        if (it == tileDataMap.end()) {
+            if (auto data = createTile(dataTileID, parameters)) {
+                it = tileDataMap.emplace(dataTileID, std::move(data)).first;
             }
-            break;
-        case TileData::State::invalid:
-            state = addTile(tileID, parameters);
-            break;
-        default:
-            break;
         }
+    }
 
-        if (!TileData::isReadyState(state)) {
-            // The tile we require is not yet loaded. Try to find a parent or
-            // child tile that we already have.
-
-            // First, try to find existing child tiles that completely cover the
-            // missing tile.
-            bool complete = findLoadedChildren(tileID, maxCoveringZoom, retain);
+    tiles = algorithm::updateRenderables<Tile>(tileDataMap, idealTiles, *info, overscaledZoom);
 
-            // Then, if there are no complete child tiles, try to find existing
-            // parent tiles that completely cover the missing tile.
-            if (!complete) {
-                findLoadedParent(tileID, minCoveringZoom, retain, parameters);
-            }
-        }
+    for (auto& pair : tiles) {
+        retain.emplace(pair.second.data.id);
     }
 
-    if (type != SourceType::Raster && cache.getSize() == 0) {
-        size_t conservativeCacheSize = ((float)parameters.transformState.getWidth()  / util::tileSize) *
-                                       ((float)parameters.transformState.getHeight() / util::tileSize) *
-                                       (parameters.transformState.getMaxZoom() - parameters.transformState.getMinZoom() + 1) *
-                                       0.5;
+    if (type != SourceType::Raster && type != SourceType::Annotations && cache.getSize() == 0) {
+        size_t conservativeCacheSize =
+            ((float)parameters.transformState.getWidth() / util::tileSize) *
+            ((float)parameters.transformState.getHeight() / util::tileSize) *
+            (parameters.transformState.getMaxZoom() - parameters.transformState.getMinZoom() + 1) *
+            0.5;
         cache.setSize(conservativeCacheSize);
     }
 
-    auto& tileCache = cache;
-
-    // Remove tiles that we definitely don't need, i.e. tiles that are not on
-    // the required list.
-    std::set<OverscaledTileID> retain_data;
-    util::erase_if(tiles, [this, &retain, &retain_data, &tileCache](auto &pair) {
-        const auto& tileID = pair.first;
-        Tile &tile = *pair.second;
-        bool obsolete = std::find(retain.begin(), retain.end(), tileID) == retain.end();
-        if (!obsolete) {
-            retain_data.insert(tile.data->id);
-        } else if (type != SourceType::Raster && tile.data->getState() == TileData::State::parsed) {
-            // Partially parsed tiles are never added to the cache because otherwise
-            // they never get updated if the go out from the viewport and the pending
-            // resources arrive.
-            tileCache.add(tile.data->id, tile.data);
+    // Remove stale data tiles from the active set of tiles.
+    // This goes through the (sorted!) tileDataMap and retain set in lockstep and removes items from
+    // tileDataMap that don't have the corresponding key in the retain set.
+    auto dataIt = tileDataMap.begin();
+    auto retainIt = retain.begin();
+    while (dataIt != tileDataMap.end()) {
+        if (retainIt == retain.end() || dataIt->first < *retainIt) {
+            cache.add(dataIt->first, std::move(dataIt->second));
+            tileDataMap.erase(dataIt++);
+        } else {
+            if (!(*retainIt < dataIt->first)) {
+                ++dataIt;
+            }
+            ++retainIt;
         }
-        return obsolete;
-    });
+    }
 
-    // Remove all the expired pointers from the set.
-    util::erase_if(tileDataMap, [&retain_data, &tileCache](auto &pair) {
-        const auto tileData = pair.second.lock();
-        if (!tileData) {
-            return true;
-        }
+    for (auto& pair : tileDataMap) {
+        const auto& dataTileID = pair.first;
+        auto tileData = pair.second.get();
+        if (parameters.shouldReparsePartialTiles &&
+            tileData->getState() == TileData::State::partial) {
+            auto callback = std::bind(&Source::tileLoadingCallback, this, dataTileID,
+                                      std::placeholders::_1, false);
 
-        bool obsolete = retain_data.find(tileData->id) == retain_data.end();
-        if (obsolete) {
-            if (!tileCache.has(tileData->id)) {
-                tileData->cancel();
+            if (!tileData->parsePending(callback)) {
+                allTilesUpdated = false;
             }
-            return true;
         } else {
-            return false;
+            tileData->redoPlacement({ parameters.transformState.getAngle(),
+                                      parameters.transformState.getPitch(),
+                                      parameters.debugOptions & MapDebugOptions::Collision },
+                                    [this]() { observer->onPlacementRedone(); });
         }
-    });
-
-    updateTilePtrs();
-
-    for (auto& tilePtr : tilePtrs) {
-        tilePtr->data->redoPlacement(
-            { parameters.transformState.getAngle(), parameters.transformState.getPitch(), parameters.debugOptions & MapDebugOptions::Collision },
-            [this]() {
-                observer->onPlacementRedone();
-            });
     }
 
     updated = parameters.animationTime;
@@ -479,13 +323,6 @@ bool Source::update(const StyleUpdateParameters& parameters) {
     return allTilesUpdated;
 }
 
-void Source::updateTilePtrs() {
-    tilePtrs.clear();
-    for (const auto& pair : tiles) {
-        tilePtrs.push_back(pair.second.get());
-    }
-}
-
 static Point<int16_t> coordinateToTilePoint(const CanonicalTileID& tileID, const TileCoordinate& coord) {
     auto zoomedCoord = coord.zoomTo(tileID.z);
     return {
@@ -499,7 +336,7 @@ static Point<int16_t> coordinateToTilePoint(const CanonicalTileID& tileID, const
 }
 
 struct TileQuery {
-    Tile* tile;
+    TileData& tileData;
     GeometryCollection queryGeometry;
     double tileSize;
     double scale;
@@ -528,8 +365,8 @@ std::unordered_map<std::string, std::vector<Feature>> Source::queryRenderedFeatu
 
     std::map<CanonicalTileID, TileQuery> tileQueries;
 
-    for (auto& tilePtr : tilePtrs) {
-        auto& tile = *tilePtr;
+    for (auto& tilePtr : tiles) {
+        auto& tile = tilePtr.second;
 
         auto tileSpaceBoundsMin = coordinateToTilePoint(tile.id.canonical, { minX, minY, z });
         auto tileSpaceBoundsMax = coordinateToTilePoint(tile.id.canonical, { maxX, maxY, z });
@@ -549,10 +386,10 @@ std::unordered_map<std::string, std::vector<Feature>> Source::queryRenderedFeatu
         } else {
             (void)zoom;
             tileQueries.emplace(tile.id.canonical, TileQuery{
-                    tilePtr,
+                    tile.data,
                     { tileSpaceQueryGeometry },
-                    util::tileSize * tile.data->id.overscaleFactor(),
-                    std::pow(2, zoom - tile.data->id.overscaledZ)
+                    util::tileSize * tile.data.id.overscaleFactor(),
+                    std::pow(2, zoom - tile.data.id.overscaledZ)
                 });
         }
     }
@@ -560,7 +397,7 @@ std::unordered_map<std::string, std::vector<Feature>> Source::queryRenderedFeatu
 
     for (auto& it : tileQueries) {
         auto& tileQuery = std::get<1>(it);
-        tileQuery.tile->data->queryRenderedFeatures(result, tileQuery.queryGeometry, bearing, tileQuery.tileSize, tileQuery.scale, layerIDs);
+        tileQuery.tileData.queryRenderedFeatures(result, tileQuery.queryGeometry, bearing, tileQuery.tileSize, tileQuery.scale, layerIDs);
     }
 
     return result;
@@ -586,7 +423,7 @@ void Source::tileLoadingCallback(const OverscaledTileID& tileID,
         return;
     }
 
-    util::ptr<TileData> tileData = it->second.lock();
+    auto& tileData = it->second;
     if (!tileData) {
         return;
     }
@@ -606,8 +443,9 @@ void Source::dumpDebugLogs() const {
     Log::Info(Event::General, "Source::id: %s", id.c_str());
     Log::Info(Event::General, "Source::loaded: %d", loaded);
 
-    for (const auto& tile : tiles) {
-        tile.second->data->dumpDebugLogs();
+    for (const auto& pair : tileDataMap) {
+        auto& tileData = pair.second;
+        tileData->dumpDebugLogs();
     }
 }
 
diff --git a/src/mbgl/source/source.hpp b/src/mbgl/source/source.hpp
index 4cd29eef0a..8fa61bbd3f 100644
--- a/src/mbgl/source/source.hpp
+++ b/src/mbgl/source/source.hpp
@@ -69,11 +69,17 @@ public:
     // new data available that a tile in the "partial" state might be interested at.
     bool update(const StyleUpdateParameters&);
 
+    template <typename ClipIDGenerator>
+    void updateClipIDs(ClipIDGenerator& generator) {
+        generator.update(tiles);
+    }
+
     void updateMatrices(const mat4 &projMatrix, const TransformState &transform);
     void finishRender(Painter &painter);
 
-    std::map<UnwrappedTileID, Renderable> getRenderables() const;
-    const std::vector<Tile*>& getTiles() const;
+    const std::map<UnwrappedTileID, Tile>& getTiles() const;
+
+    TileData* getTileData(const OverscaledTileID&) const;
 
     std::unordered_map<std::string, std::vector<Feature>> queryRenderedFeatures(
             const std::vector<TileCoordinate>& queryGeometry,
@@ -94,16 +100,10 @@ public:
     bool enabled = false;
 
 private:
-    void tileLoadingCallback(const OverscaledTileID&,
-                             std::exception_ptr,
-                             bool isNewTile);
-    bool handlePartialTile(const TileID&);
-    bool findLoadedChildren(const TileID&, int32_t maxCoveringZoom, std::vector<TileID>& retain);
-    void findLoadedParent(const TileID&, int32_t minCoveringZoom, std::vector<TileID>& retain, const StyleUpdateParameters&);
+    void tileLoadingCallback(const OverscaledTileID&, std::exception_ptr, bool isNewTile);
 
-    TileData::State addTile(const TileID&, const StyleUpdateParameters&);
-    TileData::State hasTile(const TileID&);
-    void updateTilePtrs();
+    std::unique_ptr<TileData> createTile(const OverscaledTileID&,
+                                         const StyleUpdateParameters& parameters);
 
 private:
     std::unique_ptr<const SourceInfo> info;
@@ -113,9 +113,8 @@ private:
     // Stores the time when this source was most recently updated.
     TimePoint updated = TimePoint::min();
 
-    std::map<TileID, std::unique_ptr<Tile>> tiles;
-    std::vector<Tile*> tilePtrs;
-    std::map<OverscaledTileID, std::weak_ptr<TileData>> tileDataMap;
+    std::map<UnwrappedTileID, Tile> tiles;
+    std::map<OverscaledTileID, std::unique_ptr<TileData>> tileDataMap;
     TileCache cache;
 
     std::unique_ptr<AsyncRequest> req;
diff --git a/src/mbgl/style/style.cpp b/src/mbgl/style/style.cpp
index 5c3f15d292..1a6f3626a7 100644
--- a/src/mbgl/style/style.cpp
+++ b/src/mbgl/style/style.cpp
@@ -282,9 +282,11 @@ RenderData Style::getRenderData() const {
             continue;
         }
 
-        for (auto tile : source->getTiles()) {
-            if (!tile->data || !tile->data->isReady())
+        for (auto& pair : source->getTiles()) {
+            auto& tile = pair.second;
+            if (!tile.data.isReady()) {
                 continue;
+            }
 
             // We're not clipping symbol layers, so when we have both parents and children of symbol
             // layers, we drop all children in favor of their parent to avoid duplicate labels.
@@ -295,7 +297,7 @@ RenderData Style::getRenderData() const {
                 // already a bucket from this layer that is a parent of this tile. Tiles are ordered
                 // by zoom level when we obtain them from getTiles().
                 for (auto it = result.order.rbegin(); it != result.order.rend() && (&it->layer == layer.get()); ++it) {
-                    if (tile->data->id.isChildOf(it->tile->data->id)) {
+                    if (tile.data.id.isChildOf(it->tile->data.id)) {
                         skip = true;
                         break;
                     }
@@ -305,9 +307,9 @@ RenderData Style::getRenderData() const {
                 }
             }
 
-            auto bucket = tile->data->getBucket(*layer);
+            auto bucket = tile.data.getBucket(*layer);
             if (bucket) {
-                result.order.emplace_back(*layer, tile, bucket);
+                result.order.emplace_back(*layer, &tile, bucket);
             }
         }
     }
diff --git a/src/mbgl/tile/tile.hpp b/src/mbgl/tile/tile.hpp
index 5cb23f58f3..78df995157 100644
--- a/src/mbgl/tile/tile.hpp
+++ b/src/mbgl/tile/tile.hpp
@@ -3,7 +3,6 @@
 
 #include <mbgl/tile/tile_id.hpp>
 #include <mbgl/util/mat4.hpp>
-#include <mbgl/util/noncopyable.hpp>
 #include <mbgl/util/ptr.hpp>
 #include <mbgl/util/clip_id.hpp>
 
@@ -12,15 +11,20 @@ namespace mbgl {
 class TileData;
 struct box;
 
-class Tile : private util::noncopyable {
+class Tile {
 public:
-    Tile(const UnwrappedTileID& id_) : id(id_) {
+    Tile(const UnwrappedTileID& id_, TileData& data_) : id(id_), data(data_) {
     }
 
+    Tile(const Tile&) = delete;
+    Tile(Tile&&) = default;
+    Tile& operator=(const Tile&) = delete;
+    Tile& operator=(Tile&&) = default;
+
     const UnwrappedTileID id;
+    TileData& data;
     ClipID clip;
     mat4 matrix;
-    util::ptr<TileData> data;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/tile/tile_cache.cpp b/src/mbgl/tile/tile_cache.cpp
index 0f0a231d54..15e8a38ce5 100644
--- a/src/mbgl/tile/tile_cache.cpp
+++ b/src/mbgl/tile/tile_cache.cpp
@@ -17,10 +17,13 @@ void TileCache::setSize(size_t size_) {
     assert(orderedKeys.size() <= size);
 }
 
-void TileCache::add(const OverscaledTileID& key, std::shared_ptr<TileData> data) {
+void TileCache::add(const OverscaledTileID& key, std::unique_ptr<TileData> data) {
+    if (!data->isReady() || !size) {
+        return;
+    }
 
     // insert new or query existing data
-    if (tiles.emplace(key, data).second) {
+    if (tiles.emplace(key, std::move(data)).second) {
         // remove existing data key
         orderedKeys.remove(key);
     }
@@ -36,13 +39,13 @@ void TileCache::add(const OverscaledTileID& key, std::shared_ptr<TileData> data)
     assert(orderedKeys.size() <= size);
 };
 
-std::shared_ptr<TileData> TileCache::get(const OverscaledTileID& key) {
+std::unique_ptr<TileData> TileCache::get(const OverscaledTileID& key) {
 
-    std::shared_ptr<TileData> data;
+    std::unique_ptr<TileData> data;
 
     auto it = tiles.find(key);
     if (it != tiles.end()) {
-        data = it->second;
+        data = std::move(it->second);
         tiles.erase(it);
         orderedKeys.remove(key);
         assert(data->isReady());
diff --git a/src/mbgl/tile/tile_cache.hpp b/src/mbgl/tile/tile_cache.hpp
index 8bf747035e..e63d8cee99 100644
--- a/src/mbgl/tile/tile_cache.hpp
+++ b/src/mbgl/tile/tile_cache.hpp
@@ -17,13 +17,13 @@ public:
 
     void setSize(size_t);
     size_t getSize() const { return size; };
-    void add(const OverscaledTileID& key, std::shared_ptr<TileData> data);
-    std::shared_ptr<TileData> get(const OverscaledTileID& key);
+    void add(const OverscaledTileID& key, std::unique_ptr<TileData> data);
+    std::unique_ptr<TileData> get(const OverscaledTileID& key);
     bool has(const OverscaledTileID& key);
     void clear();
 
 private:
-    std::map<OverscaledTileID, std::shared_ptr<TileData>> tiles;
+    std::map<OverscaledTileID, std::unique_ptr<TileData>> tiles;
     std::list<OverscaledTileID> orderedKeys;
 
     size_t size;
diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index 6cd5d4b4ab..739528a8b8 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -3,6 +3,8 @@
 #include <mbgl/util/interpolate.hpp>
 #include <mbgl/map/transform_state.hpp>
 
+#include <functional>
+
 namespace mbgl {
 
 namespace {
@@ -69,30 +71,36 @@ static void scanTriangle(const TileCoordinate& a, const TileCoordinate& b, const
 
 } // namespace
 
-int32_t coveringZoomLevel(double zoom, SourceType type, uint16_t tileSize) {
-    zoom += std::log(util::tileSize / tileSize) / std::log(2);
-    if (type == SourceType::Raster || type == SourceType::Video) {
-        return ::round(zoom);
-    } else {
-        return std::floor(zoom);
-    }
-}
+namespace util {
+
+namespace {
 
-std::vector<TileID> tileCover(const TileCoordinate& tl,
-                              const TileCoordinate& tr,
-                              const TileCoordinate& br,
-                              const TileCoordinate& bl,
-                              const TileCoordinate& c,
-                              int32_t z,
-                              int32_t actualZ) {
-    int32_t tiles = 1 << z;
-    std::forward_list<mbgl::TileID> t;
+std::vector<UnwrappedTileID> tileCover(const TileCoordinate& tl,
+                                       const TileCoordinate& tr,
+                                       const TileCoordinate& br,
+                                       const TileCoordinate& bl,
+                                       const TileCoordinate& c,
+                                       int32_t z) {
+    assert(tl.z == z);
+    assert(tr.z == z);
+    assert(br.z == z);
+    assert(bl.z == z);
+    assert(c.z == z);
+    const int32_t tiles = 1 << z;
+
+    struct ID {
+        int32_t x, y;
+        double sqDist;
+    };
+
+    std::vector<ID> t;
 
     auto scanLine = [&](int32_t x0, int32_t x1, int32_t y) {
         int32_t x;
         if (y >= 0 && y <= tiles) {
             for (x = x0; x < x1; ++x) {
-                t.emplace_front(actualZ, x, y, z);
+                const auto dx = x + 0.5 - c.x, dy = y + 0.5 - c.y;
+                t.emplace_back(ID{ x, y, dx * dx + dy * dy });
             }
         }
     };
@@ -104,19 +112,36 @@ std::vector<TileID> tileCover(const TileCoordinate& tl,
     scanTriangle(tl, tr, br, 0, tiles, scanLine);
     scanTriangle(br, bl, tl, 0, tiles, scanLine);
 
-    t.sort();
-    t.unique();
-
-    t.sort([&](const TileID& a, const TileID& b) {
-        // Sorts by distance from the box center
-        return std::fabs(a.x - c.x) + std::fabs(a.y - c.y) <
-               std::fabs(b.x - c.x) + std::fabs(b.y - c.y);
+    // Sort first by distance, then by x/y.
+    std::sort(t.begin(), t.end(), [](const ID& a, const ID& b) {
+        return (a.sqDist != b.sqDist) ? (a.sqDist < b.sqDist)
+                                      : ((a.x != b.x) ? (a.x < b.x) : (a.y < b.y));
     });
 
-    return std::vector<TileID>(t.begin(), t.end());
+    // Erase duplicate tile IDs (they typically occur at the common side of both triangles).
+    t.erase(std::unique(t.begin(), t.end(), [](const ID& a, const ID& b) {
+                return a.x == b.x && a.y == b.y;
+            }), t.end());
+
+    std::vector<UnwrappedTileID> result;
+    for (const auto& id : t) {
+        result.emplace_back(z, id.x, id.y);
+    }
+    return result;
+}
+
+} // namespace
+
+int32_t coveringZoomLevel(double zoom, SourceType type, uint16_t size) {
+    zoom += std::log(util::tileSize / size) / std::log(2);
+    if (type == SourceType::Raster || type == SourceType::Video) {
+        return ::round(zoom);
+    } else {
+        return std::floor(zoom);
+    }
 }
 
-std::vector<TileID> tileCover(const LatLngBounds& bounds_, int32_t z, int32_t actualZ) {
+std::vector<UnwrappedTileID> tileCover(const LatLngBounds& bounds_, int32_t z) {
     if (bounds_.isEmpty() ||
         bounds_.south() >  util::LATITUDE_MAX ||
         bounds_.north() < -util::LATITUDE_MAX) {
@@ -134,10 +159,10 @@ std::vector<TileID> tileCover(const LatLngBounds& bounds_, int32_t z, int32_t ac
         TileCoordinate::fromLatLng(state, z, bounds.southeast()),
         TileCoordinate::fromLatLng(state, z, bounds.southwest()),
         TileCoordinate::fromLatLng(state, z, bounds.center()),
-        z, actualZ);
+        z);
 }
 
-std::vector<TileID> tileCover(const TransformState& state, int32_t z, int32_t actualZ) {
+std::vector<UnwrappedTileID> tileCover(const TransformState& state, int32_t z) {
     const double w = state.getWidth();
     const double h = state.getHeight();
     return tileCover(
@@ -146,7 +171,8 @@ std::vector<TileID> tileCover(const TransformState& state, int32_t z, int32_t ac
         TileCoordinate::fromScreenCoordinate(state, z, { w,   h   }),
         TileCoordinate::fromScreenCoordinate(state, z, { 0,   h   }),
         TileCoordinate::fromScreenCoordinate(state, z, { w/2, h/2 }),
-        z, actualZ);
+        z);
 }
 
+} // namespace util
 } // namespace mbgl
diff --git a/src/mbgl/util/tile_cover.hpp b/src/mbgl/util/tile_cover.hpp
index 7323df520c..aab96c8436 100644
--- a/src/mbgl/util/tile_cover.hpp
+++ b/src/mbgl/util/tile_cover.hpp
@@ -1,7 +1,7 @@
 #ifndef MBGL_UTIL_TILE_COVER
 #define MBGL_UTIL_TILE_COVER
 
-#include <mbgl/map/tile_id.hpp>
+#include <mbgl/tile/tile_id.hpp>
 #include <mbgl/style/types.hpp>
 #include <mbgl/util/tile_coordinate.hpp>
 
@@ -12,11 +12,14 @@ namespace mbgl {
 class TransformState;
 class LatLngBounds;
 
+namespace util {
+
 int32_t coveringZoomLevel(double z, SourceType type, uint16_t tileSize);
 
-std::vector<TileID> tileCover(const TransformState&, int32_t z, int32_t actualZ);
-std::vector<TileID> tileCover(const LatLngBounds&,   int32_t z, int32_t actualZ);
+std::vector<UnwrappedTileID> tileCover(const TransformState&, int32_t z);
+std::vector<UnwrappedTileID> tileCover(const LatLngBounds&, int32_t z);
 
+} // namespace util
 } // namespace mbgl
 
 #endif
diff --git a/test/algorithm/mock.hpp b/test/algorithm/mock.hpp
new file mode 100644
index 0000000000..89f51b15b8
--- /dev/null
+++ b/test/algorithm/mock.hpp
@@ -0,0 +1,60 @@
+#ifndef MBGL_TEST_MOCK
+#define MBGL_TEST_MOCK
+
+#include <cstdint>
+#include <string>
+#include <memory>
+#include <set>
+#include <map>
+
+#include <mbgl/tile/tile_id.hpp>
+
+struct MockSourceInfo {
+    uint8_t maxZoom = 16;
+    uint8_t minZoom = 0;
+};
+
+struct MockTileData;
+
+struct MockRenderable {
+    MockRenderable(mbgl::UnwrappedTileID id_, MockTileData& data_) : id(id_), data(data_) {}
+
+    const mbgl::UnwrappedTileID id;
+    MockTileData& data;
+
+    bool operator==(const MockRenderable& rhs) const {
+        return &data == &rhs.data;
+    }
+};
+
+::std::ostream& operator<<(::std::ostream& os, const MockRenderable&) {
+    return os << "Renderable{}";
+}
+
+struct MockSource {
+    MockSourceInfo info;
+    std::map<mbgl::OverscaledTileID, std::unique_ptr<MockTileData>> dataTiles;
+    std::set<mbgl::UnwrappedTileID> idealTiles;
+    std::map<mbgl::UnwrappedTileID, MockRenderable> renderables;
+
+    // Test API
+    inline MockTileData* createTileData(const mbgl::OverscaledTileID& tileID);
+};
+
+struct MockBucket {};
+
+
+struct MockTileData {
+    bool isReady() {
+        return ready;
+    }
+
+    bool ready = false;
+};
+
+MockTileData* MockSource::createTileData(const mbgl::OverscaledTileID& tileID) {
+    // Replace the existing MockTileData object, if any.
+    return (dataTiles[tileID] = std::make_unique<MockTileData>()).get();
+}
+
+#endif
diff --git a/test/algorithm/update_renderables.cpp b/test/algorithm/update_renderables.cpp
new file mode 100644
index 0000000000..860381bdfa
--- /dev/null
+++ b/test/algorithm/update_renderables.cpp
@@ -0,0 +1,367 @@
+#include <mbgl/test/util.hpp>
+#include "mock.hpp"
+
+#include <mbgl/algorithm/update_renderables_impl.hpp>
+
+using namespace mbgl;
+
+TEST(UpdateRenderables, SingleTile) {
+    MockSource source;
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 1, 1 });
+
+    // Make sure that we're getting the tile back.
+    auto tile_1_1_1 = source.createTileData(OverscaledTileID{ 1, 1, 1 });
+    tile_1_1_1->ready = true;
+
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 1, 1 }, MockRenderable{ { 1, 1, 1 }, *tile_1_1_1 } },
+              }),
+              source.renderables);
+
+    // Check a repeated render with the same data.
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 1, 1 }, MockRenderable{ { 1, 1, 1 }, *tile_1_1_1 } },
+              }),
+              source.renderables);
+
+    // Insert a tile we don't have data for.
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 1 });
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 1, 1 }, MockRenderable{ { 1, 1, 1 }, *tile_1_1_1 } },
+              }),
+              source.renderables);
+
+    // Now insert the missing tile and check that we're rendering it.
+    auto tile_1_0_1 = source.createTileData(OverscaledTileID{ 1, 0, 1 });
+    tile_1_0_1->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 0, 1 }, MockRenderable{ { 1, 0, 1 }, *tile_1_0_1 } },
+                  { { 1, 1, 1 }, MockRenderable{ { 1, 1, 1 }, *tile_1_1_1 } },
+              }),
+              source.renderables);
+
+    // Insert another tile, and another bucket that has a different name and check that we're not
+    // using it.
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 });
+    auto tile_1_0_0 = source.createTileData(OverscaledTileID{ 1, 0, 0 });
+
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 0, 1 }, MockRenderable{ { 1, 0, 1 }, *tile_1_0_1 } },
+                  { { 1, 1, 1 }, MockRenderable{ { 1, 1, 1 }, *tile_1_1_1 } },
+              }),
+              source.renderables);
+
+    // Then, add the bucket and check that it's getting used.
+    tile_1_0_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 0, 0 }, MockRenderable{ { 1, 0, 0 }, *tile_1_0_0 } },
+                  { { 1, 0, 1 }, MockRenderable{ { 1, 0, 1 }, *tile_1_0_1 } },
+                  { { 1, 1, 1 }, MockRenderable{ { 1, 1, 1 }, *tile_1_1_1 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, UseParentTile) {
+    MockSource source;
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 1 });
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 1, 0 });
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 1, 1 });
+
+    // Make sure that we're getting the tile back.
+    auto tile_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 });
+    tile_0_0_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 0, 0, 0 }, MockRenderable{ { 0, 0, 0 }, *tile_0_0_0 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, DontUseWrongParentTile) {
+    MockSource source;
+    source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 });
+
+    auto tile_1_1_0 = source.createTileData(OverscaledTileID{ 1, 1, 0 });
+    tile_1_1_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 2);
+    EXPECT_EQ(decltype(source.renderables)({}), source.renderables);
+
+    // Add a new child tile and check that it is now used.
+    source.idealTiles.emplace(UnwrappedTileID{ 2, 2, 0 });
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 2);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 1, 0 }, MockRenderable{ { 1, 1, 0 }, *tile_1_1_0 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, UseParentTileWhenChildNotReady) {
+    MockSource source;
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 1 });
+
+    auto tile_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 });
+    tile_0_0_0->ready = true;
+
+    auto tile_1_0_1 = source.createTileData(OverscaledTileID{ 1, 0, 1 });
+    // Don't create bucket.
+
+    // Make sure that it renders the parent tile.
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 0, 0, 0 }, MockRenderable{ { 0, 0, 0 }, *tile_0_0_0 } },
+              }),
+              source.renderables);
+
+    // Now insert the bucket and make sure we're now using the matching tile
+    tile_1_0_1->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 0, 1 }, MockRenderable{ { 1, 0, 1 }, *tile_1_0_1 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, UseOverlappingParentTile) {
+    MockSource source;
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 });
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 1 });
+
+    auto tile_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 });
+    tile_0_0_0->ready = true;
+
+    auto tile_1_0_1 = source.createTileData(OverscaledTileID{ 1, 0, 1 });
+    tile_1_0_1->ready = true;
+
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 0, 0, 0 }, MockRenderable{ { 0, 0, 0 }, *tile_0_0_0 } },
+                  { { 1, 0, 1 }, MockRenderable{ { 1, 0, 1 }, *tile_1_0_1 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, UseChildTiles) {
+    MockSource source;
+    source.idealTiles.emplace(UnwrappedTileID{ 0, 0, 0 });
+
+    auto tile_1_0_0 = source.createTileData(OverscaledTileID{ 1, 0, 0 });
+    tile_1_0_0->ready = true;
+    auto tile_1_1_0 = source.createTileData(OverscaledTileID{ 1, 1, 0 });
+    tile_1_1_0->ready = true;
+
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 0);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 0, 0 }, MockRenderable{ { 1, 0, 0 }, *tile_1_0_0 } },
+                  { { 1, 1, 0 }, MockRenderable{ { 1, 1, 0 }, *tile_1_1_0 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, PreferChildTiles) {
+    MockSource source;
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 });
+
+    auto tile_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 });
+    tile_0_0_0->ready = true;
+    auto tile_2_0_0 = source.createTileData(OverscaledTileID{ 2, 0, 0 });
+    tile_2_0_0->ready = true;
+
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 0, 0, 0 }, MockRenderable{ { 0, 0, 0 }, *tile_0_0_0 } },
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_2_0_0 } },
+              }),
+              source.renderables);
+
+    // Now add more children to cover the ideal tile fully, until it is covered fully, and verify
+    // that the parent doesn't get rendered.
+    auto tile_2_0_1 = source.createTileData(OverscaledTileID{ 2, 0, 1 });
+    tile_2_0_1->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 0, 0, 0 }, MockRenderable{ { 0, 0, 0 }, *tile_0_0_0 } },
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_2_0_0 } },
+                  { { 2, 0, 1 }, MockRenderable{ { 2, 0, 1 }, *tile_2_0_1 } },
+              }),
+              source.renderables);
+
+    auto tile_2_1_0 = source.createTileData(OverscaledTileID{ 2, 1, 0 });
+    tile_2_1_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 0, 0, 0 }, MockRenderable{ { 0, 0, 0 }, *tile_0_0_0 } },
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_2_0_0 } },
+                  { { 2, 0, 1 }, MockRenderable{ { 2, 0, 1 }, *tile_2_0_1 } },
+                  { { 2, 1, 0 }, MockRenderable{ { 2, 1, 0 }, *tile_2_1_0 } },
+              }),
+              source.renderables);
+
+    // Adding the last child tile covers 1/0/0 fully, so we don't need 0/0/0 anymore.
+    auto tile_2_1_1 = source.createTileData(OverscaledTileID{ 2, 1, 1 });
+    tile_2_1_1->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_2_0_0 } },
+                  { { 2, 0, 1 }, MockRenderable{ { 2, 0, 1 }, *tile_2_0_1 } },
+                  { { 2, 1, 0 }, MockRenderable{ { 2, 1, 0 }, *tile_2_1_0 } },
+                  { { 2, 1, 1 }, MockRenderable{ { 2, 1, 1 }, *tile_2_1_1 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, UseParentAndChildTiles) {
+    MockSource source;
+    source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 });
+
+    auto tile_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 });
+    tile_0_0_0->ready = true;
+    auto tile_2_0_0 = source.createTileData(OverscaledTileID{ 2, 0, 0 });
+    tile_2_0_0->ready = true;
+
+    // Check that it uses the child tile, but not the parent tile.
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 0, 0, 0 }, MockRenderable{ { 0, 0, 0 }, *tile_0_0_0 } },
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_2_0_0 } },
+              }),
+              source.renderables);
+
+    // Then, remove the child tile and check that it now uses the parent tile.
+    source.dataTiles.erase(OverscaledTileID{ 2, 0, 0 });
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 1);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 0, 0, 0 }, MockRenderable{ { 0, 0, 0 }, *tile_0_0_0 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, DontUseTilesLowerThanMinzoom) {
+    MockSource source;
+    source.info.minZoom = 2;
+    source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 });
+
+    auto tile_1_0_0 = source.createTileData(OverscaledTileID{ 1, 0, 0 });
+    tile_1_0_0->ready = true;
+
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 2);
+    EXPECT_EQ(decltype(source.renderables)({}), source.renderables);
+}
+
+TEST(UpdateRenderables, UseOverzoomedTileAfterMaxzoom) {
+    MockSource source;
+    source.info.maxZoom = 2;
+    source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 });
+
+    // Add a child tile (that should never occur in practice) and make sure it's not selected.
+    auto tile_3_3_0_0 = source.createTileData(OverscaledTileID{ 3, 0, 0 });
+    tile_3_3_0_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 2);
+    EXPECT_EQ(decltype(source.renderables)({}), source.renderables);
+
+    // Only add a non-overzoomed ("parent") tile at first.
+    auto tile_2_2_0_0 = source.createTileData(OverscaledTileID{ 2, { 2, 0, 0 } });
+    tile_2_2_0_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 3);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_2_2_0_0 } },
+              }),
+              source.renderables);
+
+    // Then add the overzoomed tile matching the zoom level we're rendering.
+    auto tile_3_2_0_0 = source.createTileData(OverscaledTileID{ 3, { 2, 0, 0 } });
+    tile_3_2_0_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 3);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_3_2_0_0 } },
+              }),
+              source.renderables);
+
+    // Check that it's switching back to the tile that has the matching overzoom value.
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 2);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_2_2_0_0 } },
+              }),
+              source.renderables);
+
+    // Now remove the best match.
+    source.dataTiles.erase(OverscaledTileID{ 2, { 2, 0, 0 } });
+    tile_2_2_0_0 = nullptr;
+
+    // Use the overzoomed tile even though it doesn't match the zoom level.
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 2);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_3_2_0_0 } },
+              }),
+              source.renderables);
+}
+
+TEST(UpdateRenderables, AscendToNonOverzoomedTiles) {
+    MockSource source;
+    source.info.maxZoom = 2;
+    source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 });
+
+    // Add a matching overzoomed tile and make sure it gets selected.
+    auto tile_3_2_0_0 = source.createTileData(OverscaledTileID{ 3, { 2, 0, 0 } });
+    tile_3_2_0_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 3);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_3_2_0_0 } },
+              }),
+              source.renderables);
+
+    // Then, swap it with a non-overzoomed tile.
+    source.dataTiles.erase(OverscaledTileID{ 3, { 2, 0, 0 } });
+    tile_3_2_0_0 = nullptr;
+    auto tile_2_2_0_0 = source.createTileData(OverscaledTileID{ 2, { 2, 0, 0 } });
+    tile_2_2_0_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 3);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 2, 0, 0 }, MockRenderable{ { 2, 0, 0 }, *tile_2_2_0_0 } },
+              }),
+              source.renderables);
+
+    // Then, swap it with a parent tile.
+    source.dataTiles.erase(OverscaledTileID{ 2, { 2, 0, 0 } });
+    tile_2_2_0_0 = nullptr;
+    auto tile_1_1_0_0 = source.createTileData(OverscaledTileID{ 1, { 1, 0, 0 } });
+    tile_1_1_0_0->ready = true;
+    source.renderables = algorithm::updateRenderables<MockRenderable>(
+        source.dataTiles, source.idealTiles, source.info, 3);
+    EXPECT_EQ(decltype(source.renderables)({
+                  { { 1, 0, 0 }, MockRenderable{ { 1, 0, 0 }, *tile_1_1_0_0 } },
+              }),
+              source.renderables);
+}
diff --git a/test/map/tile.cpp b/test/map/tile.cpp
deleted file mode 100644
index ad703595ad..0000000000
--- a/test/map/tile.cpp
+++ /dev/null
@@ -1,50 +0,0 @@
-#include <iostream>
-#include <mbgl/test/util.hpp>
-
-#include <mbgl/map/tile_id.hpp>
-
-using namespace mbgl;
-
-
-TEST(Variant, isChild) {
-    ASSERT_TRUE(TileID(1, 0, 0, 1).isChildOf(TileID(0, 0, 0, 0)));
-    ASSERT_TRUE(TileID(1, 1, 0, 1).isChildOf(TileID(0, 0, 0, 0)));
-    ASSERT_TRUE(TileID(1, 2, 0, 1).isChildOf(TileID(0, 1, 0, 0)));
-    ASSERT_TRUE(TileID(1, 3, 0, 1).isChildOf(TileID(0, 1, 0, 0)));
-    ASSERT_TRUE(TileID(1, 4, 0, 1).isChildOf(TileID(0, 2, 0, 0)));
-    ASSERT_TRUE(TileID(1, 5, 0, 1).isChildOf(TileID(0, 2, 0, 0)));
-    ASSERT_TRUE(TileID(2, 0, 0, 2).isChildOf(TileID(0, 0, 0, 0)));
-
-    ASSERT_TRUE(TileID(2, 8, 0, 2).isChildOf(TileID(0, 2, 0, 0)));
-    ASSERT_TRUE(TileID(2, 9, 0, 2).isChildOf(TileID(0, 2, 0, 0)));
-    ASSERT_TRUE(TileID(2, 10, 0, 2).isChildOf(TileID(0, 2, 0, 0)));
-    ASSERT_TRUE(TileID(2, 11, 0, 2).isChildOf(TileID(0, 2, 0, 0)));
-    ASSERT_TRUE(TileID(2, 12, 0, 2).isChildOf(TileID(0, 3, 0, 0)));
-    ASSERT_TRUE(TileID(2, 13, 0, 2).isChildOf(TileID(0, 3, 0, 0)));
-
-    ASSERT_TRUE(TileID(1, -1, 0, 1).isChildOf(TileID(0, -1, 0, 0)));
-    ASSERT_TRUE(TileID(1, -2, 0, 1).isChildOf(TileID(0, -1, 0, 0)));
-    ASSERT_TRUE(TileID(1, -3, 0, 1).isChildOf(TileID(0, -2, 0, 0)));
-    ASSERT_TRUE(TileID(1, -4, 0, 1).isChildOf(TileID(0, -2, 0, 0)));
-    ASSERT_TRUE(TileID(2, -1, 0, 2).isChildOf(TileID(0, -1, 0, 0)));
-    ASSERT_TRUE(TileID(2, -2, 0, 2).isChildOf(TileID(0, -1, 0, 0)));
-    ASSERT_TRUE(TileID(2, -3, 0, 2).isChildOf(TileID(0, -1, 0, 0)));
-    ASSERT_TRUE(TileID(2, -4, 0, 2).isChildOf(TileID(0, -1, 0, 0)));
-    ASSERT_TRUE(TileID(2, -5, 0, 2).isChildOf(TileID(0, -2, 0, 0)));
-    ASSERT_TRUE(TileID(2, -6, 0, 2).isChildOf(TileID(0, -2, 0, 0)));
-    ASSERT_TRUE(TileID(2, -7, 0, 2).isChildOf(TileID(0, -2, 0, 0)));
-    ASSERT_TRUE(TileID(2, -8, 0, 2).isChildOf(TileID(0, -2, 0, 0)));
-
-    ASSERT_FALSE(TileID(4, -16, 0, 4).isChildOf(TileID(0, -2, 0, 0)));
-    ASSERT_TRUE(TileID(4, -17, 0, 4).isChildOf(TileID(0, -2, 0, 0)));
-
-    ASSERT_TRUE(TileID(2, -1, 0, 2).isChildOf(TileID(1, -1, 0, 1)));
-    ASSERT_TRUE(TileID(2, -2, 0, 2).isChildOf(TileID(1, -1, 0, 1)));
-    ASSERT_TRUE(TileID(2, -3, 0, 2).isChildOf(TileID(1, -2, 0, 1)));
-    ASSERT_TRUE(TileID(2, -4, 0, 2).isChildOf(TileID(1, -2, 0, 1)));
-    ASSERT_TRUE(TileID(3, -1, 0, 3).isChildOf(TileID(1, -1, 0, 1)));
-    ASSERT_TRUE(TileID(3, -2, 0, 3).isChildOf(TileID(1, -1, 0, 1)));
-    ASSERT_TRUE(TileID(3, -3, 0, 3).isChildOf(TileID(1, -1, 0, 1)));
-    ASSERT_TRUE(TileID(3, -4, 0, 3).isChildOf(TileID(1, -1, 0, 1)));
-    ASSERT_TRUE(TileID(3, -5, 0, 3).isChildOf(TileID(1, -2, 0, 1)));
-}
diff --git a/test/storage/offline.cpp b/test/storage/offline.cpp
index e8f78425f5..3b64c0f50e 100644
--- a/test/storage/offline.cpp
+++ b/test/storage/offline.cpp
@@ -1,25 +1,22 @@
 #include <mbgl/storage/offline.hpp>
 #include <mbgl/source/source_info.hpp>
-#include <mbgl/map/tile_id.hpp>
+#include <mbgl/tile/tile_id.hpp>
 
 #include <gtest/gtest.h>
 
 using namespace mbgl;
 
-static const LatLngBounds sanFrancisco = LatLngBounds::hull(
-    { 37.6609, -122.5744 },
-    { 37.8271, -122.3204 });
+static const LatLngBounds sanFrancisco =
+    LatLngBounds::hull({ 37.6609, -122.5744 }, { 37.8271, -122.3204 });
 
-static const LatLngBounds sanFranciscoWrapped = LatLngBounds::hull(
-    { 37.6609, 238.5744 },
-    { 37.8271, 238.3204 });
+static const LatLngBounds sanFranciscoWrapped =
+    LatLngBounds::hull({ 37.6609, 238.5744 }, { 37.8271, 238.3204 });
 
 TEST(OfflineTilePyramidRegionDefinition, TileCoverEmpty) {
     OfflineTilePyramidRegionDefinition region("", LatLngBounds::empty(), 0, 20, 1.0);
     SourceInfo info;
 
-    auto result = region.tileCover(SourceType::Vector, 512, info);
-    ASSERT_TRUE(result.empty());
+    EXPECT_EQ((std::vector<CanonicalTileID>{}), region.tileCover(SourceType::Vector, 512, info));
 }
 
 TEST(OfflineTilePyramidRegionDefinition, TileCoverZoomIntersection) {
@@ -27,47 +24,39 @@ TEST(OfflineTilePyramidRegionDefinition, TileCoverZoomIntersection) {
     SourceInfo info;
 
     info.minZoom = 0;
-    auto resultIntersection = region.tileCover(SourceType::Vector, 512, info);
-    ASSERT_EQ(1, resultIntersection.size());
+    EXPECT_EQ((std::vector<CanonicalTileID>{ { 2, 0, 1 } }),
+              region.tileCover(SourceType::Vector, 512, info));
 
     info.minZoom = 3;
-    auto resultNoIntersection = region.tileCover(SourceType::Vector, 512, info);
-    ASSERT_TRUE(resultNoIntersection.empty());
+    EXPECT_EQ((std::vector<CanonicalTileID>{}), region.tileCover(SourceType::Vector, 512, info));
 }
 
 TEST(OfflineTilePyramidRegionDefinition, TileCoverTileSize) {
     OfflineTilePyramidRegionDefinition region("", LatLngBounds::world(), 0, 0, 1.0);
     SourceInfo info;
 
-    auto result512 = region.tileCover(SourceType::Vector, 512, info);
-    ASSERT_EQ(1, result512.size());
-    ASSERT_EQ(0, result512[0].z);
+    EXPECT_EQ((std::vector<CanonicalTileID>{ { 0, 0, 0 } }),
+              region.tileCover(SourceType::Vector, 512, info));
 
-    auto result256 = region.tileCover(SourceType::Vector, 256, info);
-    ASSERT_EQ(4, result256.size());
-    ASSERT_EQ(1, result256[0].z);
+    EXPECT_EQ((std::vector<CanonicalTileID>{ { 1, 0, 0 }, { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 1 } }),
+              region.tileCover(SourceType::Vector, 256, info));
 }
 
 TEST(OfflineTilePyramidRegionDefinition, TileCoverZoomRounding) {
     OfflineTilePyramidRegionDefinition region("", sanFrancisco, 0.6, 0.7, 1.0);
     SourceInfo info;
 
-    auto resultVector = region.tileCover(SourceType::Vector, 512, info);
-    ASSERT_EQ(1, resultVector.size());
-    ASSERT_EQ(0, resultVector[0].z);
+    EXPECT_EQ((std::vector<CanonicalTileID>{ { 0, 0, 0 } }),
+              region.tileCover(SourceType::Vector, 512, info));
 
-    auto resultRaster = region.tileCover(SourceType::Raster, 512, info);
-    ASSERT_EQ(1, resultRaster.size());
-    ASSERT_EQ(1, resultRaster[0].z);
+    EXPECT_EQ((std::vector<CanonicalTileID>{ { 1, 0, 0 } }),
+              region.tileCover(SourceType::Raster, 512, info));
 }
 
 TEST(OfflineTilePyramidRegionDefinition, TileCoverWrapped) {
     OfflineTilePyramidRegionDefinition region("", sanFranciscoWrapped, 0, 0, 1.0);
     SourceInfo info;
 
-    auto result = region.tileCover(SourceType::Vector, 512, info);
-    ASSERT_EQ(1, result.size());
-    ASSERT_EQ(0, result[0].z);
-    ASSERT_EQ(0, result[0].x);
-    ASSERT_EQ(0, result[0].y);
+    EXPECT_EQ((std::vector<CanonicalTileID>{ { 0, 0, 0 } }),
+              region.tileCover(SourceType::Vector, 512, info));
 }
diff --git a/test/test.gypi b/test/test.gypi
index 2cb98df654..1db886e097 100644
--- a/test/test.gypi
+++ b/test/test.gypi
@@ -35,6 +35,8 @@
 
         'algorithm/covered_by_children.cpp',
         'algorithm/generate_clip_ids.cpp',
+        'algorithm/mock.hpp',
+        'algorithm/update_renderables.cpp',
 
         'api/annotations.cpp',
         'api/api_misuse.cpp',
@@ -46,7 +48,6 @@
         'geometry/binpack.cpp',
 
         'map/map.cpp',
-        'map/tile.cpp',
         'map/transform.cpp',
 
         'math/minmax.cpp',
diff --git a/test/util/tile_cover.cpp b/test/util/tile_cover.cpp
index d003653fd8..2fde6da54b 100644
--- a/test/util/tile_cover.cpp
+++ b/test/util/tile_cover.cpp
@@ -1,118 +1,85 @@
 #include <mbgl/util/tile_cover.hpp>
 #include <mbgl/util/geo.hpp>
-#include <mbgl/map/tile_id.hpp>
+#include <mbgl/map/transform.hpp>
+#include <mbgl/test/mock_view.hpp>
 
 #include <gtest/gtest.h>
 
-#include <unordered_set>
-
 using namespace mbgl;
-using set = std::unordered_set<TileID>;
 
 TEST(TileCover, Empty) {
-    auto result = tileCover(LatLngBounds::empty(), 0, 0);
-    ASSERT_TRUE(result.empty());
+    EXPECT_EQ((std::vector<UnwrappedTileID>{}), util::tileCover(LatLngBounds::empty(), 0));
 }
 
 TEST(TileCover, Arctic) {
-    auto result = tileCover(LatLngBounds::hull({ 86, -180 }, { 90, 180 }), 0, 0);
-    ASSERT_TRUE(result.empty());
+    EXPECT_EQ((std::vector<UnwrappedTileID>{}),
+              util::tileCover(LatLngBounds::hull({ 86, -180 }, { 90, 180 }), 0));
 }
 
 TEST(TileCover, Antarctic) {
-    auto result = tileCover(LatLngBounds::hull({ -86, -180 }, { -90, 180 }), 0, 0);
-    ASSERT_TRUE(result.empty());
+    EXPECT_EQ((std::vector<UnwrappedTileID>{}),
+              util::tileCover(LatLngBounds::hull({ -86, -180 }, { -90, 180 }), 0));
 }
 
 TEST(TileCover, WorldZ0) {
-    auto result = tileCover(LatLngBounds::world(), 0, 0);
-    ASSERT_EQ(1, result.size());
-    ASSERT_EQ(0, result[0].z);
-    ASSERT_EQ(0, result[0].x);
-    ASSERT_EQ(0, result[0].y);
+    EXPECT_EQ((std::vector<UnwrappedTileID>{
+                  { 0, 0, 0 },
+              }),
+              util::tileCover(LatLngBounds::world(), 0));
+}
+
+TEST(TileCover, Pitch) {
+    MockView view;
+    Transform transform(view, ConstrainMode::HeightOnly);
+    transform.resize({ { 512, 512 } });
+    transform.setZoom(2);
+    transform.setPitch(40.0 * M_PI / 180.0);
+
+    EXPECT_EQ((std::vector<UnwrappedTileID>{
+                  { 2, 1, 1 }, { 2, 1, 2 }, { 2, 2, 1 }, { 2, 2, 2 },
+              }),
+              util::tileCover(transform.getState(), 2));
 }
 
 TEST(TileCover, WorldZ1) {
-    auto result = tileCover(LatLngBounds::world(), 1, 1);
-    ASSERT_EQ(4, result.size());
-    ASSERT_EQ(
-        (set {{
-            TileID(1, 1, 1, 1),
-            TileID(1, 0, 1, 1),
-            TileID(1, 1, 0, 1),
-            TileID(1, 0, 0, 1)
-        }}),
-        (set {
-            result.begin(),
-            result.end()
-        }));
+    EXPECT_EQ((std::vector<UnwrappedTileID>{
+                  { 1, 0, 0 }, { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 1 },
+              }),
+              util::tileCover(LatLngBounds::world(), 1));
 }
 
-//TEST(TileCover, SingletonZ0) {
-//    auto result = tileCover(LatLngBounds::singleton({0, 0}), 0, 0);
-//    ASSERT_EQ(1, result.size());
-//    ASSERT_EQ(0, result[0].z);
-//    ASSERT_EQ(0, result[0].x);
-//    ASSERT_EQ(0, result[0].y);
-//}
-//
-//TEST(TileCover, SingletonZ1) {
-//    auto result = tileCover(LatLngBounds::singleton({0, 0}), 1, 1);
-//    ASSERT_EQ(1, result.size());
-//    ASSERT_EQ(0, result[0].z);
-//    ASSERT_EQ(0, result[0].x);
-//    ASSERT_EQ(0, result[0].y);
-//}
-
-static const LatLngBounds sanFrancisco = LatLngBounds::hull(
-    { 37.6609, -122.5744 },
-    { 37.8271, -122.3204 });
+TEST(TileCover, SingletonZ0) {
+    EXPECT_EQ((std::vector<UnwrappedTileID>{}),
+              util::tileCover(LatLngBounds::singleton({ 0, 0 }), 0));
+}
+
+TEST(TileCover, SingletonZ1) {
+    EXPECT_EQ((std::vector<UnwrappedTileID>{}),
+              util::tileCover(LatLngBounds::singleton({ 0, 0 }), 1));
+}
+
+static const LatLngBounds sanFrancisco =
+    LatLngBounds::hull({ 37.6609, -122.5744 }, { 37.8271, -122.3204 });
 
 TEST(TileCover, SanFranciscoZ0) {
-    auto result = tileCover(sanFrancisco, 0, 0);
-    ASSERT_EQ(1, result.size());
-    ASSERT_EQ(0, result[0].w);
-    ASSERT_EQ(0, result[0].z);
-    ASSERT_EQ(0, result[0].x);
-    ASSERT_EQ(0, result[0].y);
+    EXPECT_EQ((std::vector<UnwrappedTileID>{
+                  { 0, 0, 0 },
+              }),
+              util::tileCover(sanFrancisco, 0));
 }
 
 TEST(TileCover, SanFranciscoZ10) {
-    auto result = tileCover(sanFrancisco, 10, 10);
-    ASSERT_EQ(4, result.size());
-    ASSERT_EQ(
-        (set {{
-            TileID(10, 163, 395, 10),
-            TileID(10, 164, 395, 10),
-            TileID(10, 163, 396, 10),
-            TileID(10, 164, 396, 10)
-        }}),
-        (set {
-            result.begin(),
-            result.end()
-        }));
+    EXPECT_EQ((std::vector<UnwrappedTileID>{
+                  { 10, 163, 395 }, { 10, 163, 396 }, { 10, 164, 395 }, { 10, 164, 396 },
+
+              }),
+              util::tileCover(sanFrancisco, 10));
 }
 
-//TEST(TileCover, OrderedByDistanceToCenter) {
-//    auto result = tileCover(sanFrancisco, 12, 12);
-//    ASSERT_EQ(12, result.size());
-//    ASSERT_EQ(  12, result[0].z);
-//    ASSERT_EQ( 654, result[0].x);
-//    ASSERT_EQ(1583, result[0].y);
-//    ASSERT_EQ(  12, result[1].z);
-//    ASSERT_EQ( 655, result[1].x);
-//    ASSERT_EQ(1583, result[1].y);
-//}
-//
-//static const LatLngBounds sanFranciscoWrapped = LatLngBounds::hull(
-//    { 37.6609, 238.5744 },
-//    { 37.8271, 238.3204 });
-//
-//TEST(TileCover, SanFranciscoZ0Wrapped) {
-//    auto result = tileCover(sanFranciscoWrapped, 0, 0);
-//    ASSERT_EQ(1, result.size());
-//    ASSERT_EQ(1, result[0].w);
-//    ASSERT_EQ(0, result[0].z);
-//    ASSERT_EQ(0, result[0].x);
-//    ASSERT_EQ(0, result[0].y);
-//}
+static const LatLngBounds sanFranciscoWrapped =
+    LatLngBounds::hull({ 37.6609, 238.5744 }, { 37.8271, 238.3204 });
+
+TEST(TileCover, SanFranciscoZ0Wrapped) {
+    EXPECT_EQ((std::vector<UnwrappedTileID>{ { 0, 1, 0 } }),
+              util::tileCover(sanFranciscoWrapped, 0));
+}