[core] sort symbols using symbol-sort-key before placement (#16023)upstream/release-ristretto-cherry-pick-sort-key

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

11 files changed, 283 insertions, 46 deletions

diff --git a/src/mbgl/layout/symbol_instance.hpp b/src/mbgl/layout/symbol_instance.hpp
index 4a57b527f7..35426ba9cf 100644
--- a/src/mbgl/layout/symbol_instance.hpp
+++ b/src/mbgl/layout/symbol_instance.hpp
@@ -122,4 +122,11 @@ public:
     uint32_t crossTileID = 0;
 };
 
+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 81d1d9a5b6..032ac37b1b 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -107,7 +107,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>());
@@ -542,9 +542,10 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex,
                                   layoutTextSize);
     }
 
-    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:
@@ -552,13 +553,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()});
+                }
+            }
         }
     };
 
@@ -678,8 +702,17 @@ std::vector<float> CalculateTileDistances(const GeometryCoordinates& line, const
 }
 
 void SymbolLayout::createBucket(const ImagePositions&, std::unique_ptr<FeatureIndex>&, std::unordered_map<std::string, LayerRenderData>& renderData, const bool firstLoad, const bool showCollisionBoxes) {
-    auto bucket = std::make_shared<SymbolBucket>(layout, layerPaintProperties, textSize, iconSize, zoom, iconsNeedLinear,
-                                                 sortFeaturesByY, bucketLeaderID, std::move(symbolInstances), tilePixelRatio,
+    auto bucket = std::make_shared<SymbolBucket>(layout,
+                                                 layerPaintProperties,
+                                                 textSize,
+                                                 iconSize,
+                                                 zoom,
+                                                 iconsNeedLinear,
+                                                 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 1abcaaa5d6..e8472a7406 100644
--- a/src/mbgl/layout/symbol_layout.hpp
+++ b/src/mbgl/layout/symbol_layout.hpp
@@ -44,6 +44,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();
     /**
@@ -105,6 +106,7 @@ private:
 
     bool iconsNeedLinear = false;
     bool sortFeaturesByY = false;
+    bool sortFeaturesByKey = false;
     bool allowVerticalPlacement = 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 5835dd9b86..519bc2c190 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.cpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp
@@ -22,6 +22,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_)
@@ -35,7 +36,8 @@ SymbolBucket::SymbolBucket(Immutable<style::SymbolLayoutProperties::PossiblyEval
       sortUploaded(false),
       justReloaded(false),
       hasVariablePlacement(false),
-      symbolInstances(std::move(symbolInstances_)),
+      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 3fe6cf20c4..f6449a8906 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.hpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.hpp
@@ -59,6 +59,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);
@@ -100,6 +101,7 @@ public:
     bool hasVariablePlacement : 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 06eacc041b..ac55b77a7b 100644
--- a/src/mbgl/renderer/layers/render_symbol_layer.cpp
+++ b/src/mbgl/renderer/layers/render_symbol_layer.cpp
@@ -362,6 +362,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);
@@ -518,7 +520,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 8b0a3975fc..379ced815c 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -1,8 +1,8 @@
-#include <mbgl/text/placement.hpp>
-
+#include <list>
 #include <mbgl/layout/symbol_layout.hpp>
 #include <mbgl/renderer/render_layer.hpp>
 #include <mbgl/renderer/render_tile.hpp>
+#include <mbgl/text/placement.hpp>
 #include <mbgl/tile/geometry_tile.hpp>
 #include <mbgl/renderer/buckets/symbol_bucket.hpp>
 #include <mbgl/renderer/bucket.hpp>
@@ -110,12 +110,14 @@ void Placement::placeLayer(const RenderLayer& layer, const mat4& projMatrix, boo
     std::set<uint32_t> seenCrossTileIDs;
     for (const auto& item : layer.getPlacementData()) {
         Bucket& bucket = item.bucket;
-        BucketPlacementParameters params{
-                item.tile,
-                projMatrix,
-                layer.baseImpl->source,
-                item.featureIndex,
-                showCollisionBoxes};
+        BucketPlacementParameters params{item.tile,
+                                         projMatrix,
+                                         layer.baseImpl->source,
+                                         item.featureIndex,
+                                         showCollisionBoxes,
+                                         item.sortKey,
+                                         item.symbolInstanceStart,
+                                         item.symbolInstanceEnd};
         bucket.place(*this, params, seenCrossTileIDs);
     }
 }
@@ -479,18 +481,20 @@ void Placement::placeBucket(
             placeSymbol(*it);
         }
     } 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(TimePoint now, const double zoom) {
@@ -551,7 +555,9 @@ void Placement::commit(TimePoint now, const double zoom) {
 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 662b44d2b0..5d3f77a0a9 100644
--- a/src/mbgl/text/placement.hpp
+++ b/src/mbgl/text/placement.hpp
@@ -96,6 +96,9 @@ public:
     std::string sourceId;
     std::shared_ptr<FeatureIndex> featureIndex;
     bool showCollisionBoxes;
+    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 13b30eb75d..aff55f9762 100644
--- a/test/gl/bucket.test.cpp
+++ b/test/gl/bucket.test.cpp
@@ -123,9 +123,23 @@ 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), {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(symbolInstances), 1.0f, false, {}};
+    SymbolBucket bucket{std::move(layout),
+                        {},
+                        16.0f,
+                        1.0f,
+                        0,
+                        iconsNeedLinear,
+                        sortFeaturesByY,
+                        bucketLeaderID,
+                        std::move(symbolInstances),
+                        std::move(symbolRanges),
+                        1.0f,
+                        false,
+                        {},
+                        false /*iconsInText*/};
     ASSERT_FALSE(bucket.hasIconData());
     ASSERT_FALSE(bucket.hasSdfIconData());
     ASSERT_FALSE(bucket.hasTextData());
diff --git a/test/text/cross_tile_symbol_index.test.cpp b/test/text/cross_tile_symbol_index.test.cpp
index 4ff84063f9..605d4fe46b 100644
--- a/test/text/cross_tile_symbol_index.test.cpp
+++ b/test/text/cross_tile_symbol_index.test.cpp
@@ -37,9 +37,23 @@ 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, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(mainInstances), 1.0f, false, {} };
+    SymbolBucket mainBucket{layout,
+                            {},
+                            16.0f,
+                            1.0f,
+                            0,
+                            iconsNeedLinear,
+                            sortFeaturesByY,
+                            bucketLeaderID,
+                            std::move(mainInstances),
+                            std::move(mainRanges),
+                            1.0f,
+                            false,
+                            {},
+                            false /*iconsInText*/};
     mainBucket.bucketInstanceId = ++maxBucketInstanceId;
     index.addBucket(mainID, mainBucket, maxCrossTileID);
 
@@ -50,11 +64,25 @@ 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"));
     childInstances.push_back(makeSymbolInstance(4001, 4001, u"Toronto"));
-    SymbolBucket childBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(childInstances), 1.0f, false, {} };
+    SymbolBucket childBucket{layout,
+                             {},
+                             16.0f,
+                             1.0f,
+                             0,
+                             iconsNeedLinear,
+                             sortFeaturesByY,
+                             bucketLeaderID,
+                             std::move(childInstances),
+                             std::move(childRanges),
+                             1.0f,
+                             false,
+                             {},
+                             false /*iconsInText*/};
     childBucket.bucketInstanceId = ++maxBucketInstanceId;
     index.addBucket(childID, childBucket, maxCrossTileID);
 
@@ -69,8 +97,22 @@ 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, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(parentInstances), 1.0f, false, {} };
+    SymbolBucket parentBucket{layout,
+                              {},
+                              16.0f,
+                              1.0f,
+                              0,
+                              iconsNeedLinear,
+                              sortFeaturesByY,
+                              bucketLeaderID,
+                              std::move(parentInstances),
+                              std::move(parentRanges),
+                              1.0f,
+                              false,
+                              {},
+                              false /*iconsInText*/};
     parentBucket.bucketInstanceId = ++maxBucketInstanceId;
     index.addBucket(parentID, parentBucket, maxCrossTileID);
 
@@ -84,9 +126,23 @@ 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, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(grandchildInstances), 1.0f, false, {} };
+    SymbolBucket grandchildBucket{layout,
+                                  {},
+                                  16.0f,
+                                  1.0f,
+                                  0,
+                                  iconsNeedLinear,
+                                  sortFeaturesByY,
+                                  bucketLeaderID,
+                                  std::move(grandchildInstances),
+                                  std::move(grandchildRanges),
+                                  1.0f,
+                                  false,
+                                  {},
+                                  false /*iconsInText*/};
     grandchildBucket.bucketInstanceId = ++maxBucketInstanceId;
     index.addBucket(grandchildID, grandchildBucket, maxCrossTileID);
 
@@ -111,14 +167,42 @@ 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, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(mainInstances), 1.0f, false, {} };
+    SymbolBucket mainBucket{layout,
+                            {},
+                            16.0f,
+                            1.0f,
+                            0,
+                            iconsNeedLinear,
+                            sortFeaturesByY,
+                            bucketLeaderID,
+                            std::move(mainInstances),
+                            std::move(mainRanges),
+                            1.0f,
+                            false,
+                            {},
+                            false /*iconsInText*/};
     mainBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     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, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(childInstances), 1.0f, false, {} };
+    SymbolBucket childBucket{layout,
+                             {},
+                             16.0f,
+                             1.0f,
+                             0,
+                             iconsNeedLinear,
+                             sortFeaturesByY,
+                             bucketLeaderID,
+                             std::move(childInstances),
+                             std::move(childRanges),
+                             1.0f,
+                             false,
+                             {},
+                             false /*iconsInText*/};
     childBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     // assigns a new id
@@ -151,17 +235,45 @@ 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, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(mainInstances), 1.0f, false, {} };
+    SymbolBucket mainBucket{layout,
+                            {},
+                            16.0f,
+                            1.0f,
+                            0,
+                            iconsNeedLinear,
+                            sortFeaturesByY,
+                            bucketLeaderID,
+                            std::move(mainInstances),
+                            std::move(mainRanges),
+                            1.0f,
+                            false,
+                            {},
+                            false /*iconsInText*/};
     mainBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     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'
-    SymbolBucket childBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(childInstances), 1.0f, false, {} };
+    SymbolBucket childBucket{layout,
+                             {},
+                             16.0f,
+                             1.0f,
+                             0,
+                             iconsNeedLinear,
+                             sortFeaturesByY,
+                             bucketLeaderID,
+                             std::move(childInstances),
+                             std::move(childRanges),
+                             1.0f,
+                             false,
+                             {},
+                             false /*iconsInText*/};
     childBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     // assigns new ids
@@ -189,16 +301,44 @@ 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, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(firstInstances), 1.0f, false, {} };
+    SymbolBucket firstBucket{layout,
+                             {},
+                             16.0f,
+                             1.0f,
+                             0,
+                             iconsNeedLinear,
+                             sortFeaturesByY,
+                             bucketLeaderID,
+                             std::move(firstInstances),
+                             std::move(firstRanges),
+                             1.0f,
+                             false,
+                             {},
+                             false /*iconsInText*/};
     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'
-    SymbolBucket secondBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(secondInstances), 1.0f, false, {} };
+    SymbolBucket secondBucket{layout,
+                              {},
+                              16.0f,
+                              1.0f,
+                              0,
+                              iconsNeedLinear,
+                              sortFeaturesByY,
+                              bucketLeaderID,
+                              std::move(secondInstances),
+                              std::move(secondRanges),
+                              1.0f,
+                              false,
+                              {},
+                              false /*iconsInText*/};
     secondBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     // assigns new ids
@@ -212,4 +352,3 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
     ASSERT_EQ(secondBucket.symbolInstances.at(1).crossTileID, 2u); // B' copies from B
     ASSERT_EQ(secondBucket.symbolInstances.at(2).crossTileID, 3u); // C' gets new ID
 }
-