Port global symbol query from GL JS:

 - Symbol querying is now global instead of per-tile
 - Symbols that bleed over tile boundaries no longer missed in queries
 - Symbol results now sorted based on rendering order (ie overlapping symbols change their sort order when a bearing change causes their render order to change)
 - Placement::retainedQueryData now responsible for maintaining symbol querying data for buckets that may no longer be in the TilePyramid.

19 files changed, 67 insertions, 51 deletions

diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp
index 60e8a0b504..3d40a1714d 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.cpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp
@@ -200,8 +200,12 @@ void SymbolBucket::sortFeatures(const float angle) {
     text.triangles.clear();
     icon.triangles.clear();
 
+    featureSortOrder = std::make_unique<std::vector<size_t>>();
+    featureSortOrder->reserve(symbolInstanceIndexes.size());
+    
     for (auto i : symbolInstanceIndexes) {
         const SymbolInstance& symbolInstance = symbolInstances[i];
+        featureSortOrder->push_back(symbolInstance.featureIndex);
 
         if (symbolInstance.placedTextIndex) {
             addPlacedSymbol(text.triangles, text.placedSymbols[*symbolInstance.placedTextIndex]);
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.hpp b/src/mbgl/renderer/buckets/symbol_bucket.hpp
index ed8afb052c..e52d18372d 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.hpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.hpp
@@ -131,6 +131,8 @@ public:
 
     uint32_t bucketInstanceId = 0;
     bool justReloaded = false;
+    
+    std::shared_ptr<std::vector<size_t>> featureSortOrder;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/renderer/render_source.hpp b/src/mbgl/renderer/render_source.hpp
index 53519c763e..54a0b5db43 100644
--- a/src/mbgl/renderer/render_source.hpp
+++ b/src/mbgl/renderer/render_source.hpp
@@ -64,8 +64,7 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options,
-                          const CollisionIndex& collisionIndex) const = 0;
+                          const RenderedQueryOptions& options) const = 0;
 
     virtual std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const = 0;
diff --git a/src/mbgl/renderer/renderer_impl.cpp b/src/mbgl/renderer/renderer_impl.cpp
index 962a6571db..5b739678fb 100644
--- a/src/mbgl/renderer/renderer_impl.cpp
+++ b/src/mbgl/renderer/renderer_impl.cpp
@@ -396,10 +396,6 @@ void Renderer::Impl::render(const UpdateParameters& updateParameters) {
         }
 
         placementChanged = newPlacement->commit(*placement, parameters.timePoint);
-        // commitFeatureIndexes depends on the assumption that no new FeatureIndex has been loaded since placement
-        // started. If we violate this assumption, then we need to either make CollisionIndex completely independendent of
-        // FeatureIndex, or find a way for its entries to point to multiple FeatureIndexes.
-        commitFeatureIndexes();
         crossTileSymbolIndex.pruneUnusedLayers(usedSymbolLayers);
         if (placementChanged || symbolBucketsChanged) {
             placement = std::move(newPlacement);
@@ -668,6 +664,39 @@ std::vector<Feature> Renderer::Impl::queryRenderedFeatures(const ScreenLineStrin
 
     return queryRenderedFeatures(geometry, options, layers);
 }
+    
+void Renderer::Impl::queryRenderedSymbols(std::unordered_map<std::string, std::vector<Feature>>& resultsByLayer,
+                                          const ScreenLineString& geometry,
+                                          const std::vector<const RenderLayer*>& layers,
+                                          const RenderedQueryOptions& options) const {
+    
+    auto renderedSymbols = placement->getCollisionIndex().queryRenderedSymbols(geometry);
+    std::vector<std::reference_wrapper<const RetainedQueryData>> bucketQueryData;
+    for (auto entry : renderedSymbols) {
+        bucketQueryData.push_back(placement->getQueryData(entry.first));
+    }
+    // Although symbol query is global, symbol results are only sortable within a bucket
+    // For a predictable global sort order, we sort the buckets based on their corresponding tile position
+    std::sort(bucketQueryData.begin(), bucketQueryData.end(), [](const RetainedQueryData& a, const RetainedQueryData& b) {
+        return
+            std::tie(a.tileID.canonical.z, a.tileID.canonical.y, a.tileID.wrap, a.tileID.canonical.x) <
+            std::tie(b.tileID.canonical.z, b.tileID.canonical.y, b.tileID.wrap, b.tileID.canonical.x);
+    });
+    
+    for (auto wrappedQueryData : bucketQueryData) {
+        auto& queryData = wrappedQueryData.get();
+        auto bucketSymbols = queryData.featureIndex->lookupSymbolFeatures(renderedSymbols[queryData.bucketInstanceId],
+                                                                          options,
+                                                                          layers,
+                                                                          queryData.tileID,
+                                                                          queryData.featureSortOrder);
+        
+        for (auto layer : bucketSymbols) {
+            auto& resultFeatures = resultsByLayer[layer.first];
+            std::move(layer.second.begin(), layer.second.end(), std::inserter(resultFeatures, resultFeatures.end()));
+        }
+    }
+}
 
 std::vector<Feature> Renderer::Impl::queryRenderedFeatures(const ScreenLineString& geometry, const RenderedQueryOptions& options, const std::vector<const RenderLayer*>& layers) const {
     std::unordered_set<std::string> sourceIDs;
@@ -678,10 +707,12 @@ std::vector<Feature> Renderer::Impl::queryRenderedFeatures(const ScreenLineStrin
     std::unordered_map<std::string, std::vector<Feature>> resultsByLayer;
     for (const auto& sourceID : sourceIDs) {
         if (RenderSource* renderSource = getRenderSource(sourceID)) {
-            auto sourceResults = renderSource->queryRenderedFeatures(geometry, transformState, layers, options, placement->getCollisionIndex());
+            auto sourceResults = renderSource->queryRenderedFeatures(geometry, transformState, layers, options);
             std::move(sourceResults.begin(), sourceResults.end(), std::inserter(resultsByLayer, resultsByLayer.begin()));
         }
     }
+    
+    queryRenderedSymbols(resultsByLayer, geometry, layers, options);
 
     std::vector<Feature> result;
 
@@ -780,15 +811,6 @@ bool Renderer::Impl::hasTransitions(TimePoint timePoint) const {
     return false;
 }
 
-void Renderer::Impl::commitFeatureIndexes() {
-    for (auto& source : renderSources) {
-        for (auto& renderTile : source.second->getRenderTiles()) {
-            Tile& tile = renderTile.get().tile;
-            tile.commitFeatureIndex();
-        }
-    }
-}
-
 void Renderer::Impl::updateFadingTiles() {
     fadingTiles = false;
     for (auto& source : renderSources) {
diff --git a/src/mbgl/renderer/renderer_impl.hpp b/src/mbgl/renderer/renderer_impl.hpp
index 4675ac79ea..4124f6f416 100644
--- a/src/mbgl/renderer/renderer_impl.hpp
+++ b/src/mbgl/renderer/renderer_impl.hpp
@@ -64,7 +64,12 @@ private:
 
           RenderLayer* getRenderLayer(const std::string& id);
     const RenderLayer* getRenderLayer(const std::string& id) const;
-                           
+              
+    void queryRenderedSymbols(std::unordered_map<std::string, std::vector<Feature>>& resultsByLayer,
+                              const ScreenLineString& geometry,
+                              const std::vector<const RenderLayer*>& layers,
+                              const RenderedQueryOptions& options) const;
+    
     std::vector<Feature> queryRenderedFeatures(const ScreenLineString&, const RenderedQueryOptions&, const std::vector<const RenderLayer*>&) const;
 
     // GlyphManagerObserver implementation.
@@ -74,7 +79,6 @@ private:
     void onTileChanged(RenderSource&, const OverscaledTileID&) override;
     void onTileError(RenderSource&, const OverscaledTileID&, std::exception_ptr) override;
 
-    void commitFeatureIndexes();
     void updateFadingTiles();
 
     friend class Renderer;
diff --git a/src/mbgl/renderer/sources/render_custom_geometry_source.cpp b/src/mbgl/renderer/sources/render_custom_geometry_source.cpp
index 057ad5a4a7..88792db00b 100644
--- a/src/mbgl/renderer/sources/render_custom_geometry_source.cpp
+++ b/src/mbgl/renderer/sources/render_custom_geometry_source.cpp
@@ -67,9 +67,8 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderCustomGeometrySource::queryRenderedFeatures(const ScreenLineString& geometry,
                                            const TransformState& transformState,
                                            const std::vector<const RenderLayer*>& layers,
-                                           const RenderedQueryOptions& options,
-                                           const CollisionIndex& collisionIndex) const {
-   return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex);
+                                           const RenderedQueryOptions& options) const {
+   return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options);
 }
 
 std::vector<Feature> RenderCustomGeometrySource::querySourceFeatures(const SourceQueryOptions& options) const {
diff --git a/src/mbgl/renderer/sources/render_custom_geometry_source.hpp b/src/mbgl/renderer/sources/render_custom_geometry_source.hpp
index 033d731029..9e47b9e392 100644
--- a/src/mbgl/renderer/sources/render_custom_geometry_source.hpp
+++ b/src/mbgl/renderer/sources/render_custom_geometry_source.hpp
@@ -27,8 +27,7 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options,
-                          const CollisionIndex& collisionIndex) const final;
+                          const RenderedQueryOptions& options) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/renderer/sources/render_geojson_source.cpp b/src/mbgl/renderer/sources/render_geojson_source.cpp
index cbf4db70b5..7492a4cf16 100644
--- a/src/mbgl/renderer/sources/render_geojson_source.cpp
+++ b/src/mbgl/renderer/sources/render_geojson_source.cpp
@@ -85,9 +85,8 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderGeoJSONSource::queryRenderedFeatures(const ScreenLineString& geometry,
                                            const TransformState& transformState,
                                            const std::vector<const RenderLayer*>& layers,
-                                           const RenderedQueryOptions& options,
-                                           const CollisionIndex& collisionIndex) const {
-    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex);
+                                           const RenderedQueryOptions& options) const {
+    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options);
 }
 
 std::vector<Feature> RenderGeoJSONSource::querySourceFeatures(const SourceQueryOptions& options) const {
diff --git a/src/mbgl/renderer/sources/render_geojson_source.hpp b/src/mbgl/renderer/sources/render_geojson_source.hpp
index 72fccbd043..bcdc109953 100644
--- a/src/mbgl/renderer/sources/render_geojson_source.hpp
+++ b/src/mbgl/renderer/sources/render_geojson_source.hpp
@@ -31,8 +31,7 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options,
-                          const CollisionIndex&) const final;
+                          const RenderedQueryOptions& options) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/renderer/sources/render_image_source.cpp b/src/mbgl/renderer/sources/render_image_source.cpp
index 31a5916a34..b35e151f82 100644
--- a/src/mbgl/renderer/sources/render_image_source.cpp
+++ b/src/mbgl/renderer/sources/render_image_source.cpp
@@ -84,8 +84,7 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderImageSource::queryRenderedFeatures(const ScreenLineString&,
                                          const TransformState&,
                                          const std::vector<const RenderLayer*>&,
-                                         const RenderedQueryOptions&,
-                                         const CollisionIndex&) const {
+                                         const RenderedQueryOptions&) const {
     return std::unordered_map<std::string, std::vector<Feature>> {};
 }
 
diff --git a/src/mbgl/renderer/sources/render_image_source.hpp b/src/mbgl/renderer/sources/render_image_source.hpp
index 85ee0ace11..7dc89d3591 100644
--- a/src/mbgl/renderer/sources/render_image_source.hpp
+++ b/src/mbgl/renderer/sources/render_image_source.hpp
@@ -32,8 +32,7 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options,
-                          const CollisionIndex& collisionIndex) const final;
+                          const RenderedQueryOptions& options) const final;
 
     std::vector<Feature> querySourceFeatures(const SourceQueryOptions&) const final;
 
diff --git a/src/mbgl/renderer/sources/render_raster_dem_source.cpp b/src/mbgl/renderer/sources/render_raster_dem_source.cpp
index b3153622c3..58bdba1840 100644
--- a/src/mbgl/renderer/sources/render_raster_dem_source.cpp
+++ b/src/mbgl/renderer/sources/render_raster_dem_source.cpp
@@ -146,8 +146,7 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderRasterDEMSource::queryRenderedFeatures(const ScreenLineString&,
                                           const TransformState&,
                                           const std::vector<const RenderLayer*>&,
-                                          const RenderedQueryOptions&,
-                                          const CollisionIndex& ) const {
+                                          const RenderedQueryOptions&) const {
     return std::unordered_map<std::string, std::vector<Feature>> {};
 }
 
diff --git a/src/mbgl/renderer/sources/render_raster_dem_source.hpp b/src/mbgl/renderer/sources/render_raster_dem_source.hpp
index 741214a14d..512fe6367c 100644
--- a/src/mbgl/renderer/sources/render_raster_dem_source.hpp
+++ b/src/mbgl/renderer/sources/render_raster_dem_source.hpp
@@ -27,8 +27,7 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options,
-                          const CollisionIndex& collisionIndex) const final;
+                          const RenderedQueryOptions& options) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/renderer/sources/render_raster_source.cpp b/src/mbgl/renderer/sources/render_raster_source.cpp
index 60b3fa9a3b..3162acc7b4 100644
--- a/src/mbgl/renderer/sources/render_raster_source.cpp
+++ b/src/mbgl/renderer/sources/render_raster_source.cpp
@@ -76,8 +76,7 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderRasterSource::queryRenderedFeatures(const ScreenLineString&,
                                           const TransformState&,
                                           const std::vector<const RenderLayer*>&,
-                                          const RenderedQueryOptions&,
-                                          const CollisionIndex& ) const {
+                                          const RenderedQueryOptions&) const {
     return std::unordered_map<std::string, std::vector<Feature>> {};
 }
 
diff --git a/src/mbgl/renderer/sources/render_raster_source.hpp b/src/mbgl/renderer/sources/render_raster_source.hpp
index 78eda199ac..c60a51c63b 100644
--- a/src/mbgl/renderer/sources/render_raster_source.hpp
+++ b/src/mbgl/renderer/sources/render_raster_source.hpp
@@ -27,8 +27,7 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options,
-                          const CollisionIndex& collisionIndex) const final;
+                          const RenderedQueryOptions& options) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/renderer/sources/render_vector_source.cpp b/src/mbgl/renderer/sources/render_vector_source.cpp
index e87bea5dcd..c9c47359f4 100644
--- a/src/mbgl/renderer/sources/render_vector_source.cpp
+++ b/src/mbgl/renderer/sources/render_vector_source.cpp
@@ -79,9 +79,8 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderVectorSource::queryRenderedFeatures(const ScreenLineString& geometry,
                                           const TransformState& transformState,
                                           const std::vector<const RenderLayer*>& layers,
-                                          const RenderedQueryOptions& options,
-                                          const CollisionIndex& collisionIndex) const {
-    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex);
+                                          const RenderedQueryOptions& options) const {
+    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options);
 }
 
 std::vector<Feature> RenderVectorSource::querySourceFeatures(const SourceQueryOptions& options) const {
diff --git a/src/mbgl/renderer/sources/render_vector_source.hpp b/src/mbgl/renderer/sources/render_vector_source.hpp
index 592160dc16..a0351c226c 100644
--- a/src/mbgl/renderer/sources/render_vector_source.hpp
+++ b/src/mbgl/renderer/sources/render_vector_source.hpp
@@ -27,8 +27,7 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options,
-                          const CollisionIndex& collisionIndex) const final;
+                          const RenderedQueryOptions& options) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index 8f83a0f982..e2d4d9829f 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -241,8 +241,7 @@ void TilePyramid::update(const std::vector<Immutable<style::Layer::Impl>>& layer
 std::unordered_map<std::string, std::vector<Feature>> TilePyramid::queryRenderedFeatures(const ScreenLineString& geometry,
                                            const TransformState& transformState,
                                            const std::vector<const RenderLayer*>& layers,
-                                           const RenderedQueryOptions& options,
-                                           const CollisionIndex& collisionIndex) const {
+                                           const RenderedQueryOptions& options) const {
     std::unordered_map<std::string, std::vector<Feature>> result;
     if (renderTiles.empty() || geometry.empty()) {
         return result;
@@ -285,8 +284,7 @@ std::unordered_map<std::string, std::vector<Feature>> TilePyramid::queryRendered
                                               tileSpaceQueryGeometry,
                                               transformState,
                                               layers,
-                                              options,
-                                              collisionIndex);
+                                              options);
     }
 
     return result;
diff --git a/src/mbgl/renderer/tile_pyramid.hpp b/src/mbgl/renderer/tile_pyramid.hpp
index 2638599c38..bf3ba0d7b8 100644
--- a/src/mbgl/renderer/tile_pyramid.hpp
+++ b/src/mbgl/renderer/tile_pyramid.hpp
@@ -53,8 +53,7 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>&,
-                          const RenderedQueryOptions& options,
-                          const CollisionIndex& collisionIndex) const;
+                          const RenderedQueryOptions& options) const;
 
     std::vector<Feature> querySourceFeatures(const SourceQueryOptions&) const;