[core] sort symbols using symbol-sort-key before placement (#16023)

fix #15964
partially port mapbox/mapbox-gl-js#9054

11 files changed, 130 insertions, 27 deletions

diff --git a/src/mbgl/layout/symbol_instance.hpp b/src/mbgl/layout/symbol_instance.hpp
index 3cd67125b4..3303e5f7e3 100644
--- a/src/mbgl/layout/symbol_instance.hpp
+++ b/src/mbgl/layout/symbol_instance.hpp
@@ -123,4 +123,11 @@ public:
     static constexpr uint32_t invalidCrossTileID() { return std::numeric_limits<uint32_t>::max(); }
 };
 
+class SortKeyRange {
+public:
+    float sortKey;
+    size_t symbolInstanceStart;
+    size_t symbolInstanceEnd;
+};
+
 } // namespace mbgl
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index e0475f0acb..61c3b4ad66 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -106,7 +106,7 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
 
     const bool hasSymbolSortKey = !leader.layout.get<SymbolSortKey>().isUndefined();
     const auto symbolZOrder = layout->get<SymbolZOrder>();
-    const bool sortFeaturesByKey = symbolZOrder != SymbolZOrderType::ViewportY && hasSymbolSortKey;
+    sortFeaturesByKey = symbolZOrder != SymbolZOrderType::ViewportY && hasSymbolSortKey;
     const bool zOrderByViewportY = symbolZOrder == SymbolZOrderType::ViewportY || (symbolZOrder == SymbolZOrderType::Auto && !sortFeaturesByKey);
     sortFeaturesByY = zOrderByViewportY && (layout->get<TextAllowOverlap>() || layout->get<IconAllowOverlap>() ||
         layout->get<TextIgnorePlacement>() || layout->get<IconIgnorePlacement>());
@@ -572,9 +572,10 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex,
         }
     }
 
-    auto addSymbolInstance = [&] (Anchor& anchor, std::shared_ptr<SymbolInstanceSharedData> sharedData) {
+    auto addSymbolInstance = [&](Anchor& anchor, std::shared_ptr<SymbolInstanceSharedData> sharedData) {
         assert(sharedData);
-        const bool anchorInsideTile = anchor.point.x >= 0 && anchor.point.x < util::EXTENT && anchor.point.y >= 0 && anchor.point.y < util::EXTENT;
+        const bool anchorInsideTile = anchor.point.x >= 0 && anchor.point.x < util::EXTENT && anchor.point.y >= 0 &&
+                                      anchor.point.y < util::EXTENT;
 
         if (mode == MapMode::Tile || anchorInsideTile) {
             // For static/continuous rendering, only add symbols anchored within this tile:
@@ -582,13 +583,36 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex,
             // In tiled rendering mode, add all symbols in the buffers so that we can:
             //  (1) render symbols that overlap into this tile
             //  (2) approximate collision detection effects from neighboring symbols
-            symbolInstances.emplace_back(anchor, std::move(sharedData), shapedTextOrientations,
-                    shapedIcon, verticallyShapedIcon,
-                    textBoxScale, textPadding, textPlacement, textOffset,
-                    iconBoxScale, iconPadding, iconOffset, indexedFeature,
-                    layoutFeatureIndex, feature.index,
-                    feature.formattedText ? feature.formattedText->rawText() : std::u16string(),
-                    overscaling, iconRotation, textRotation, variableTextOffset, allowVerticalPlacement, iconType);
+            symbolInstances.emplace_back(anchor,
+                                         std::move(sharedData),
+                                         shapedTextOrientations,
+                                         shapedIcon,
+                                         verticallyShapedIcon,
+                                         textBoxScale,
+                                         textPadding,
+                                         textPlacement,
+                                         textOffset,
+                                         iconBoxScale,
+                                         iconPadding,
+                                         iconOffset,
+                                         indexedFeature,
+                                         layoutFeatureIndex,
+                                         feature.index,
+                                         feature.formattedText ? feature.formattedText->rawText() : std::u16string(),
+                                         overscaling,
+                                         iconRotation,
+                                         textRotation,
+                                         variableTextOffset,
+                                         allowVerticalPlacement,
+                                         iconType);
+
+            if (sortFeaturesByKey) {
+                if (sortKeyRanges.size() && sortKeyRanges.back().sortKey == feature.sortKey) {
+                    sortKeyRanges.back().symbolInstanceEnd = symbolInstances.size();
+                } else {
+                    sortKeyRanges.push_back({feature.sortKey, symbolInstances.size() - 1, symbolInstances.size()});
+                }
+            }
         }
     };
 
@@ -728,6 +752,7 @@ void SymbolLayout::createBucket(const ImagePositions&, std::unique_ptr<FeatureIn
                                                  sortFeaturesByY,
                                                  bucketLeaderID,
                                                  std::move(symbolInstances),
+                                                 std::move(sortKeyRanges),
                                                  tilePixelRatio,
                                                  allowVerticalPlacement,
                                                  std::move(placementModes),
diff --git a/src/mbgl/layout/symbol_layout.hpp b/src/mbgl/layout/symbol_layout.hpp
index b906b0b36c..52c912c8ae 100644
--- a/src/mbgl/layout/symbol_layout.hpp
+++ b/src/mbgl/layout/symbol_layout.hpp
@@ -45,6 +45,7 @@ public:
 
     const std::string bucketLeaderID;
     std::vector<SymbolInstance> symbolInstances;
+    std::vector<SortKeyRange> sortKeyRanges;
 
     static constexpr float INVALID_OFFSET_VALUE = std::numeric_limits<float>::max();
     /**
@@ -115,6 +116,7 @@ private:
 
     bool iconsNeedLinear = false;
     bool sortFeaturesByY = false;
+    bool sortFeaturesByKey = false;
     bool allowVerticalPlacement = false;
     bool iconsInText = false;
     std::vector<style::TextWritingModeType> placementModes;
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp
index 55002e7851..7b8eec4471 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.cpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp
@@ -23,6 +23,7 @@ SymbolBucket::SymbolBucket(Immutable<style::SymbolLayoutProperties::PossiblyEval
                            bool sortFeaturesByY_,
                            const std::string bucketName_,
                            const std::vector<SymbolInstance>&& symbolInstances_,
+                           const std::vector<SortKeyRange>&& sortKeyRanges_,
                            float tilePixelRatio_,
                            bool allowVerticalPlacement_,
                            std::vector<style::TextWritingModeType> placementModes_,
@@ -40,6 +41,7 @@ SymbolBucket::SymbolBucket(Immutable<style::SymbolLayoutProperties::PossiblyEval
       hasVariablePlacement(false),
       hasUninitializedSymbols(false),
       symbolInstances(symbolInstances_),
+      sortKeyRanges(sortKeyRanges_),
       textSizeBinder(SymbolSizeBinder::create(zoom, textSize, TextSize::defaultValue())),
       iconSizeBinder(SymbolSizeBinder::create(zoom, iconSize, IconSize::defaultValue())),
       tilePixelRatio(tilePixelRatio_),
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.hpp b/src/mbgl/renderer/buckets/symbol_bucket.hpp
index 82d8c682aa..2b41ac9295 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.hpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.hpp
@@ -73,6 +73,7 @@ public:
                  bool sortFeaturesByY,
                  const std::string bucketLeaderID,
                  const std::vector<SymbolInstance>&&,
+                 const std::vector<SortKeyRange>&&,
                  const float tilePixelRatio,
                  bool allowVerticalPlacement,
                  std::vector<style::TextWritingModeType> placementModes,
@@ -117,6 +118,7 @@ public:
     bool hasUninitializedSymbols : 1;
 
     std::vector<SymbolInstance> symbolInstances;
+    std::vector<SortKeyRange> sortKeyRanges;
 
     struct PaintProperties {
         SymbolIconProgram::Binders iconBinders;
diff --git a/src/mbgl/renderer/layers/render_symbol_layer.cpp b/src/mbgl/renderer/layers/render_symbol_layer.cpp
index 17376fd864..955ad2ce51 100644
--- a/src/mbgl/renderer/layers/render_symbol_layer.cpp
+++ b/src/mbgl/renderer/layers/render_symbol_layer.cpp
@@ -424,6 +424,8 @@ void RenderSymbolLayer::render(PaintParameters& parameters) {
         assert(bucket.paintProperties.find(getID()) != bucket.paintProperties.end());
         const auto& bucketPaintProperties = bucket.paintProperties.at(getID());
 
+        bucket.justReloaded = false;
+
         auto addRenderables = [&renderableSegments, &tile, renderData, &bucketPaintProperties, it = renderableSegments.begin()] (auto& segments, const SymbolType type) mutable {
             for (auto& segment : segments) {
                 it = renderableSegments.emplace_hint(it, SegmentWrapper{std::ref(segment)}, tile, *renderData, bucketPaintProperties, segment.sortKey, type);
@@ -580,7 +582,28 @@ void RenderSymbolLayer::prepare(const LayerPrepareParameters& params) {
             const Tile* tile = params.source->getRenderedTile(renderTile.id);
             assert(tile);
             assert(tile->kind == Tile::Kind::Geometry);
-            placementData.push_back({*bucket, renderTile, static_cast<const GeometryTile*>(tile)->getFeatureIndex()});
+
+            bool firstInBucket = true;
+            auto featureIndex = static_cast<const GeometryTile*>(tile)->getFeatureIndex();
+
+            if (bucket->sortKeyRanges.empty()) {
+                placementData.push_back(
+                    {*bucket, renderTile, featureIndex, firstInBucket, 0.0f, 0, bucket->symbolInstances.size()});
+            } else {
+                for (const SortKeyRange& sortKeyRange : bucket->sortKeyRanges) {
+                    LayerPlacementData layerData{*bucket,
+                                                 renderTile,
+                                                 featureIndex,
+                                                 firstInBucket,
+                                                 sortKeyRange.sortKey,
+                                                 sortKeyRange.symbolInstanceStart,
+                                                 sortKeyRange.symbolInstanceEnd};
+                    auto sortPosition = std::upper_bound(placementData.cbegin(), placementData.cend(), layerData);
+                    placementData.insert(sortPosition, std::move(layerData));
+
+                    firstInBucket = false;
+                }
+            }
         }
     }
 }
diff --git a/src/mbgl/renderer/render_layer.hpp b/src/mbgl/renderer/render_layer.hpp
index ba3c638f88..4931893271 100644
--- a/src/mbgl/renderer/render_layer.hpp
+++ b/src/mbgl/renderer/render_layer.hpp
@@ -1,11 +1,11 @@
 #pragma once
+#include <list>
 #include <mbgl/layout/layout.hpp>
 #include <mbgl/renderer/render_pass.hpp>
 #include <mbgl/renderer/render_source.hpp>
 #include <mbgl/style/layer_properties.hpp>
 #include <mbgl/tile/geometry_tile_data.hpp>
 #include <mbgl/util/mat4.hpp>
-
 #include <memory>
 #include <string>
 
@@ -20,6 +20,7 @@ class RenderTile;
 class TransformState;
 class PatternAtlas;
 class LineAtlas;
+class SymbolBucket;
 
 class LayerRenderData {
 public:
@@ -29,9 +30,16 @@ public:
 
 class LayerPlacementData {
 public:
+    friend bool operator<(const LayerPlacementData& lhs, const LayerPlacementData& rhs) {
+        return lhs.sortKey < rhs.sortKey;
+    }
     std::reference_wrapper<Bucket> bucket;
     std::reference_wrapper<const RenderTile> tile;
     std::shared_ptr<FeatureIndex> featureIndex;
+    bool firstInBucket;
+    float sortKey;
+    size_t symbolInstanceStart;
+    size_t symbolInstanceEnd;
 };
 
 class LayerPrepareParameters {
@@ -95,9 +103,7 @@ public:
 
     virtual void prepare(const LayerPrepareParameters&);
 
-    const std::vector<LayerPlacementData>& getPlacementData() const { 
-        return placementData; 
-    }
+    const std::list<LayerPlacementData>& getPlacementData() const { return placementData; }
 
     // Latest evaluated properties.
     Immutable<style::LayerProperties> evaluatedProperties;
@@ -126,7 +132,7 @@ protected:
     // evaluated StyleProperties object and is updated accordingly.
     RenderPass passes = RenderPass::None;
 
-    std::vector<LayerPlacementData> placementData;
+    std::list<LayerPlacementData> placementData;
 
 private:
     // Some layers may not render correctly on some hardware when the vertex attribute limit of
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index c927fdd782..57cf1f0f1f 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -1,11 +1,11 @@
-#include <mbgl/text/placement.hpp>
-
+#include <list>
 #include <mbgl/layout/symbol_layout.hpp>
 #include <mbgl/renderer/bucket.hpp>
 #include <mbgl/renderer/buckets/symbol_bucket.hpp>
 #include <mbgl/renderer/render_layer.hpp>
 #include <mbgl/renderer/render_tile.hpp>
 #include <mbgl/renderer/update_parameters.hpp>
+#include <mbgl/text/placement.hpp>
 #include <mbgl/tile/geometry_tile.hpp>
 #include <mbgl/util/math.hpp>
 #include <utility>
@@ -113,7 +113,12 @@ void Placement::placeLayer(const RenderLayer& layer) {
     std::set<uint32_t> seenCrossTileIDs;
     for (const auto& item : layer.getPlacementData()) {
         Bucket& bucket = item.bucket;
-        BucketPlacementParameters params{item.tile, layer.baseImpl->source, item.featureIndex};
+        BucketPlacementParameters params{item.tile,
+                                         layer.baseImpl->source,
+                                         item.featureIndex,
+                                         item.sortKey,
+                                         item.symbolInstanceStart,
+                                         item.symbolInstanceEnd};
         bucket.place(*this, params, seenCrossTileIDs);
     }
 }
@@ -656,18 +661,20 @@ void Placement::placeBucket(const SymbolBucket& bucket,
         }
 
     } else {
-        for (const SymbolInstance& symbol : bucket.symbolInstances) {
-            placeSymbol(symbol);
+        auto beginIt = bucket.symbolInstances.begin() + params.symbolInstanceStart;
+        auto endIt = bucket.symbolInstances.begin() + params.symbolInstanceEnd;
+        assert(params.symbolInstanceStart < params.symbolInstanceEnd);
+        assert(params.symbolInstanceEnd <= bucket.symbolInstances.size());
+        for (auto it = beginIt; it != endIt; ++it) {
+            placeSymbol(*it);
         }
     }
 
-    bucket.justReloaded = false;
-
     // As long as this placement lives, we have to hold onto this bucket's
     // matching FeatureIndex/data for querying purposes
     retainedQueryData.emplace(std::piecewise_construct,
-                                std::forward_as_tuple(bucket.bucketInstanceId),
-                                std::forward_as_tuple(bucket.bucketInstanceId, params.featureIndex, overscaledID));
+                              std::forward_as_tuple(bucket.bucketInstanceId),
+                              std::forward_as_tuple(bucket.bucketInstanceId, params.featureIndex, overscaledID));
 }
 
 void Placement::commit() {
@@ -737,7 +744,9 @@ void Placement::commit() {
 void Placement::updateLayerBuckets(const RenderLayer& layer, const TransformState& state, bool updateOpacities) const {
     std::set<uint32_t> seenCrossTileIDs;
     for (const auto& item : layer.getPlacementData()) {
-        item.bucket.get().updateVertices(*this, updateOpacities, state, item.tile, seenCrossTileIDs);
+        if (item.firstInBucket) {
+            item.bucket.get().updateVertices(*this, updateOpacities, state, item.tile, seenCrossTileIDs);
+        }
     }
 }
 
diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp
index 46d560b673..9fbd6b9743 100644
--- a/src/mbgl/text/placement.hpp
+++ b/src/mbgl/text/placement.hpp
@@ -91,6 +91,9 @@ public:
     const RenderTile& tile;
     std::string sourceId;
     std::shared_ptr<FeatureIndex> featureIndex;
+    float sortKey;
+    size_t symbolInstanceStart;
+    size_t symbolInstanceEnd;
 };
 
 class Placement;
diff --git a/test/gl/bucket.test.cpp b/test/gl/bucket.test.cpp
index 2a7455e17c..c7636dabcf 100644
--- a/test/gl/bucket.test.cpp
+++ b/test/gl/bucket.test.cpp
@@ -123,6 +123,7 @@ TEST(Buckets, SymbolBucket) {
     bool sortFeaturesByY = false;
     std::string bucketLeaderID = "test";
     std::vector<SymbolInstance> symbolInstances;
+    std::vector<SortKeyRange> symbolRanges;
 
     gl::Context context{ backend };
     SymbolBucket bucket{std::move(layout),
@@ -134,6 +135,7 @@ TEST(Buckets, SymbolBucket) {
                         sortFeaturesByY,
                         bucketLeaderID,
                         std::move(symbolInstances),
+                        std::move(symbolRanges),
                         1.0f,
                         false,
                         {},
diff --git a/test/text/cross_tile_symbol_index.test.cpp b/test/text/cross_tile_symbol_index.test.cpp
index 6119392fd2..bedf96b430 100644
--- a/test/text/cross_tile_symbol_index.test.cpp
+++ b/test/text/cross_tile_symbol_index.test.cpp
@@ -47,6 +47,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
 
     OverscaledTileID mainID(6, 0, 6, 8, 8);
     std::vector<SymbolInstance> mainInstances;
+    std::vector<SortKeyRange> mainRanges;
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Detroit"));
     mainInstances.push_back(makeSymbolInstance(2000, 2000, u"Toronto"));
     SymbolBucket mainBucket{layout,
@@ -58,6 +59,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                             sortFeaturesByY,
                             bucketLeaderID,
                             std::move(mainInstances),
+                            std::move(mainRanges),
                             1.0f,
                             false,
                             {},
@@ -72,6 +74,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
 
     OverscaledTileID childID(7, 0, 7, 16, 16);
     std::vector<SymbolInstance> childInstances;
+    std::vector<SortKeyRange> childRanges;
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"Detroit"));
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"Windsor"));
     childInstances.push_back(makeSymbolInstance(3000, 3000, u"Toronto"));
@@ -85,6 +88,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                              sortFeaturesByY,
                              bucketLeaderID,
                              std::move(childInstances),
+                             std::move(childRanges),
                              1.0f,
                              false,
                              {},
@@ -103,6 +107,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
 
     OverscaledTileID parentID(5, 0, 5, 4, 4);
     std::vector<SymbolInstance> parentInstances;
+    std::vector<SortKeyRange> parentRanges;
     parentInstances.push_back(makeSymbolInstance(500, 500, u"Detroit"));
     SymbolBucket parentBucket{layout,
                               {},
@@ -113,6 +118,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                               sortFeaturesByY,
                               bucketLeaderID,
                               std::move(parentInstances),
+                              std::move(parentRanges),
                               1.0f,
                               false,
                               {},
@@ -130,6 +136,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
     // grandchild
     OverscaledTileID grandchildID(8, 0, 8, 32, 32);
     std::vector<SymbolInstance> grandchildInstances;
+    std::vector<SortKeyRange> grandchildRanges;
     grandchildInstances.push_back(makeSymbolInstance(4000, 4000, u"Detroit"));
     grandchildInstances.push_back(makeSymbolInstance(4000, 4000, u"Windsor"));
     SymbolBucket grandchildBucket{layout,
@@ -141,6 +148,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                                   sortFeaturesByY,
                                   bucketLeaderID,
                                   std::move(grandchildInstances),
+                                  std::move(grandchildRanges),
                                   1.0f,
                                   false,
                                   {},
@@ -169,6 +177,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
 
     OverscaledTileID mainID(6, 0, 6, 8, 8);
     std::vector<SymbolInstance> mainInstances;
+    std::vector<SortKeyRange> mainRanges;
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Detroit"));
     SymbolBucket mainBucket{layout,
                             {},
@@ -179,6 +188,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
                             sortFeaturesByY,
                             bucketLeaderID,
                             std::move(mainInstances),
+                            std::move(mainRanges),
                             1.0f,
                             false,
                             {},
@@ -187,6 +197,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
 
     OverscaledTileID childID(7, 0, 7, 16, 16);
     std::vector<SymbolInstance> childInstances;
+    std::vector<SortKeyRange> childRanges;
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"Detroit"));
     SymbolBucket childBucket{layout,
                              {},
@@ -197,6 +208,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
                              sortFeaturesByY,
                              bucketLeaderID,
                              std::move(childInstances),
+                             std::move(childRanges),
                              1.0f,
                              false,
                              {},
@@ -233,6 +245,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
 
     OverscaledTileID mainID(6, 0, 6, 8, 8);
     std::vector<SymbolInstance> mainInstances;
+    std::vector<SortKeyRange> mainRanges;
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B
     SymbolBucket mainBucket{layout,
@@ -244,6 +257,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
                             sortFeaturesByY,
                             bucketLeaderID,
                             std::move(mainInstances),
+                            std::move(mainRanges),
                             1.0f,
                             false,
                             {},
@@ -252,6 +266,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
 
     OverscaledTileID childID(7, 0, 7, 16, 16);
     std::vector<SymbolInstance> childInstances;
+    std::vector<SortKeyRange> childRanges;
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // A'
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // B'
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // C'
@@ -264,6 +279,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
                              sortFeaturesByY,
                              bucketLeaderID,
                              std::move(childInstances),
+                             std::move(childRanges),
                              1.0f,
                              false,
                              {},
@@ -295,6 +311,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
 
     OverscaledTileID tileID(6, 0, 6, 8, 8);
     std::vector<SymbolInstance> firstInstances;
+    std::vector<SortKeyRange> firstRanges;
     firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A
     firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B
     SymbolBucket firstBucket{layout,
@@ -306,6 +323,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
                              sortFeaturesByY,
                              bucketLeaderID,
                              std::move(firstInstances),
+                             std::move(firstRanges),
                              1.0f,
                              false,
                              {},
@@ -313,6 +331,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
     firstBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     std::vector<SymbolInstance> secondInstances;
+    std::vector<SortKeyRange> secondRanges;
     secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A'
     secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B'
     secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // C'
@@ -325,6 +344,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
                               sortFeaturesByY,
                               bucketLeaderID,
                               std::move(secondInstances),
+                              std::move(secondRanges),
                               1.0f,
                               false,
                               {},
@@ -369,6 +389,7 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) {
     std::vector<SymbolInstance> mainInstances;
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Washington"));
     mainInstances.push_back(makeSymbolInstance(2000, 2000, u"Richmond"));
+    std::vector<SortKeyRange> mainRanges;
     SymbolBucket symbolBucket{layout,
                               {},
                               16.0f,
@@ -378,6 +399,7 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) {
                               sortFeaturesByY,
                               bucketLeaderID,
                               std::move(mainInstances),
+                              std::move(mainRanges),
                               1.0f,
                               false,
                               {},
@@ -394,4 +416,4 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) {
 
     EXPECT_EQ(symbolBucket.symbolInstances.at(0).crossTileID, 1u);
     EXPECT_EQ(symbolBucket.symbolInstances.at(1).crossTileID, 2u);
-}
\ No newline at end of file
+}