[core] implement queryRenderedFeatures

10 files changed, 141 insertions, 33 deletions

diff --git a/src/mbgl/tile/geojson_tile.hpp b/src/mbgl/tile/geojson_tile.hpp
index 340d1053c6..f6d9d9cce7 100644
--- a/src/mbgl/tile/geojson_tile.hpp
+++ b/src/mbgl/tile/geojson_tile.hpp
@@ -39,6 +39,7 @@ public:
     GeoJSONTileLayer(Features&&);
     std::size_t featureCount() const override;
     util::ptr<const GeometryTileFeature> getFeature(std::size_t) const override;
+    std::string getName() const override { return ""; };
 
 private:
     const Features features;
diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp
index 71077d03ac..57d8eab1cc 100644
--- a/src/mbgl/tile/geometry_tile.hpp
+++ b/src/mbgl/tile/geometry_tile.hpp
@@ -13,6 +13,7 @@
 #include <cstdint>
 #include <string>
 #include <vector>
+#include <unordered_map>
 #include <functional>
 
 namespace mbgl {
@@ -38,6 +39,8 @@ public:
     virtual ~GeometryTileFeature() = default;
     virtual FeatureType getType() const = 0;
     virtual optional<Value> getValue(const std::string& key) const = 0;
+    virtual std::unordered_map<std::string,Value> getProperties() const { return std::unordered_map<std::string,Value>{}; };
+    virtual uint64_t getID() const { return 0; }
     virtual GeometryCollection getGeometries() const = 0;
     virtual uint32_t getExtent() const { return defaultExtent; }
 };
@@ -47,6 +50,7 @@ public:
     virtual ~GeometryTileLayer() = default;
     virtual std::size_t featureCount() const = 0;
     virtual util::ptr<const GeometryTileFeature> getFeature(std::size_t) const = 0;
+    virtual std::string getName() const = 0;
 };
 
 class GeometryTile : private util::noncopyable {
diff --git a/src/mbgl/tile/tile_data.cpp b/src/mbgl/tile/tile_data.cpp
index 46ce64771c..cb12e301f2 100644
--- a/src/mbgl/tile/tile_data.cpp
+++ b/src/mbgl/tile/tile_data.cpp
@@ -29,4 +29,12 @@ void TileData::dumpDebugLogs() const {
     Log::Info(Event::General, "TileData::state: %s", TileData::StateToString(state));
 }
 
+void TileData::queryRenderedFeatures(
+        std::unordered_map<std::string, std::vector<std::string>>&,
+        const GeometryCollection&,
+        const double,
+        const double,
+        const double,
+        const optional<std::vector<std::string>>&) {}
+
 } // namespace mbgl
diff --git a/src/mbgl/tile/tile_data.hpp b/src/mbgl/tile/tile_data.hpp
index 201507f799..26c0032e35 100644
--- a/src/mbgl/tile/tile_data.hpp
+++ b/src/mbgl/tile/tile_data.hpp
@@ -7,11 +7,13 @@
 #include <mbgl/map/tile_id.hpp>
 #include <mbgl/renderer/bucket.hpp>
 #include <mbgl/text/placement_config.hpp>
+#include <mbgl/tile/geometry_tile.hpp>
 
 #include <atomic>
 #include <string>
 #include <memory>
 #include <functional>
+#include <unordered_map>
 
 namespace mbgl {
 
@@ -82,6 +84,14 @@ public:
     virtual void redoPlacement(PlacementConfig, const std::function<void()>&) {}
     virtual void redoPlacement(const std::function<void()>&) {}
 
+    virtual void queryRenderedFeatures(
+            std::unordered_map<std::string, std::vector<std::string>>& result,
+            const GeometryCollection& queryGeometry,
+            const double bearing,
+            const double tileSize,
+            const double scale,
+            const optional<std::vector<std::string>>& layerIDs);
+
     bool isReady() const {
         return isReadyState(state);
     }
diff --git a/src/mbgl/tile/tile_worker.cpp b/src/mbgl/tile/tile_worker.cpp
index 917b61fde9..2a631de7bd 100644
--- a/src/mbgl/tile/tile_worker.cpp
+++ b/src/mbgl/tile/tile_worker.cpp
@@ -37,12 +37,14 @@ TileWorker::~TileWorker() {
 }
 
 TileParseResult TileWorker::parseAllLayers(std::vector<std::unique_ptr<StyleLayer>> layers_,
-                                           std::unique_ptr<const GeometryTile> geometryTile,
+                                           std::unique_ptr<const GeometryTile> geometryTile_,
                                            PlacementConfig config) {
     // We're doing a fresh parse of the tile, because the underlying data has changed.
     pending.clear();
     placementPending.clear();
     partialParse = false;
+    featureIndex = std::make_unique<FeatureIndex>();
+    geometryTile = std::move(geometryTile_);
 
     // Store the layers for use in redoPlacement.
     layers = std::move(layers_);
@@ -55,17 +57,12 @@ TileParseResult TileWorker::parseAllLayers(std::vector<std::unique_ptr<StyleLaye
         const StyleLayer* layer = i->get();
         if (parsed.find(layer->bucketName()) == parsed.end()) {
             parsed.emplace(layer->bucketName());
-            parseLayer(layer, *geometryTile);
+            parseLayer(layer);
         }
+        featureIndex->addBucketLayerName(layer->bucketName(), layer->id);
     }
 
-    result.state = pending.empty() ? TileData::State::parsed : TileData::State::partial;
-
-    if (result.state == TileData::State::parsed) {
-        placeLayers(config);
-    }
-
-    return std::move(result);
+    return prepareResult(config);
 }
 
 TileParseResult TileWorker::parsePendingLayers(const PlacementConfig config) {
@@ -90,39 +87,49 @@ TileParseResult TileWorker::parsePendingLayers(const PlacementConfig config) {
         ++it;
     }
 
+    return prepareResult(config);
+}
+
+TileParseResult TileWorker::prepareResult(const PlacementConfig& config) {
     result.state = pending.empty() ? TileData::State::parsed : TileData::State::partial;
 
     if (result.state == TileData::State::parsed) {
-        placeLayers(config);
+        featureIndex->setCollisionTile(placeLayers(config));
+        featureIndex->loadTree();
+        result.featureIndex = std::move(featureIndex);
+        result.geometryTile = std::move(geometryTile);
     }
 
     return std::move(result);
 }
 
-void TileWorker::placeLayers(const PlacementConfig config) {
-    redoPlacement(&placementPending, config);
+std::unique_ptr<CollisionTile> TileWorker::placeLayers(const PlacementConfig config) {
+    auto collisionTile = redoPlacement(&placementPending, config);
     for (auto &p : placementPending) {
         p.second->swapRenderData();
         insertBucket(p.first, std::move(p.second));
     }
     placementPending.clear();
+    return collisionTile;
 }
 
-void TileWorker::redoPlacement(
+std::unique_ptr<CollisionTile> TileWorker::redoPlacement(
     const std::unordered_map<std::string, std::unique_ptr<Bucket>>* buckets,
     PlacementConfig config) {
 
-    CollisionTile collisionTile(config);
+    auto collisionTile = std::make_unique<CollisionTile>(config);
 
     for (auto i = layers.rbegin(); i != layers.rend(); i++) {
         const auto it = buckets->find((*i)->id);
         if (it != buckets->end()) {
-            it->second->placeFeatures(collisionTile);
+            it->second->placeFeatures(*collisionTile);
         }
     }
+
+    return collisionTile;
 }
 
-void TileWorker::parseLayer(const StyleLayer* layer, const GeometryTile& geometryTile) {
+void TileWorker::parseLayer(const StyleLayer* layer) {
     // Cancel early when parsing.
     if (state == TileData::State::obsolete)
         return;
@@ -139,7 +146,7 @@ void TileWorker::parseLayer(const StyleLayer* layer, const GeometryTile& geometr
         return;
     }
 
-    auto geometryLayer = geometryTile.getLayer(layer->sourceLayer);
+    auto geometryLayer = geometryTile->getLayer(layer->sourceLayer);
     if (!geometryLayer) {
         // The layer specified in the bucket does not exist. Do nothing.
         if (debug::tileParseWarnings) {
@@ -157,6 +164,7 @@ void TileWorker::parseLayer(const StyleLayer* layer, const GeometryTile& geometr
                                      spriteStore,
                                      glyphAtlas,
                                      glyphStore,
+                                     *featureIndex,
                                      mode);
 
     std::unique_ptr<Bucket> bucket = layer->createBucket(parameters);
diff --git a/src/mbgl/tile/tile_worker.hpp b/src/mbgl/tile/tile_worker.hpp
index 2943b100ab..7c4b147d08 100644
--- a/src/mbgl/tile/tile_worker.hpp
+++ b/src/mbgl/tile/tile_worker.hpp
@@ -7,6 +7,7 @@
 #include <mbgl/util/variant.hpp>
 #include <mbgl/util/ptr.hpp>
 #include <mbgl/text/placement_config.hpp>
+#include <mbgl/geometry/feature_index.hpp>
 
 #include <string>
 #include <memory>
@@ -27,14 +28,16 @@ class SymbolLayer;
 
 // We're using this class to shuttle the resulting buckets from the worker thread to the MapContext
 // thread. This class is movable-only because the vector contains movable-only value elements.
-class TileParseResultBuckets {
+class TileParseResultData {
 public:
     TileData::State state = TileData::State::invalid;
     std::unordered_map<std::string, std::unique_ptr<Bucket>> buckets;
+    std::unique_ptr<FeatureIndex> featureIndex;
+    std::unique_ptr<const GeometryTile> geometryTile;
 };
 
 using TileParseResult = variant<
-    TileParseResultBuckets, // success
+    TileParseResultData, // success
     std::exception_ptr>;    // error
 
 class TileWorker : public util::noncopyable {
@@ -54,13 +57,14 @@ public:
 
     TileParseResult parsePendingLayers(PlacementConfig);
 
-    void redoPlacement(const std::unordered_map<std::string, std::unique_ptr<Bucket>>*,
+    std::unique_ptr<CollisionTile> redoPlacement(const std::unordered_map<std::string, std::unique_ptr<Bucket>>*,
                        PlacementConfig);
 
 private:
-    void parseLayer(const StyleLayer*, const GeometryTile&);
+    TileParseResult prepareResult(const PlacementConfig& config);
+    void parseLayer(const StyleLayer*);
     void insertBucket(const std::string& name, std::unique_ptr<Bucket>);
-    void placeLayers(PlacementConfig);
+    std::unique_ptr<CollisionTile> placeLayers(PlacementConfig);
 
     const TileID id;
     const std::string sourceID;
@@ -75,6 +79,9 @@ private:
 
     std::vector<std::unique_ptr<StyleLayer>> layers;
 
+    std::unique_ptr<FeatureIndex> featureIndex;
+    std::unique_ptr<const GeometryTile> geometryTile;
+
     // Contains buckets that we couldn't parse so far due to missing resources.
     // They will be attempted on subsequent parses.
     std::list<std::pair<const SymbolLayer*, std::unique_ptr<Bucket>>> pending;
@@ -84,7 +91,7 @@ private:
     std::unordered_map<std::string, std::unique_ptr<Bucket>> placementPending;
 
     // Temporary holder
-    TileParseResultBuckets result;
+    TileParseResultData result;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/tile/vector_tile.cpp b/src/mbgl/tile/vector_tile.cpp
index 4c6027d36c..f3a02c5d76 100644
--- a/src/mbgl/tile/vector_tile.cpp
+++ b/src/mbgl/tile/vector_tile.cpp
@@ -54,8 +54,8 @@ VectorTileFeature::VectorTileFeature(pbf feature_pbf, const VectorTileLayer& lay
 }
 
 optional<Value> VectorTileFeature::getValue(const std::string& key) const {
-    auto keyIter = layer.keys.find(key);
-    if (keyIter == layer.keys.end()) {
+    auto keyIter = layer.keysMap.find(key);
+    if (keyIter == layer.keysMap.end()) {
         return optional<Value>();
     }
 
@@ -63,7 +63,7 @@ optional<Value> VectorTileFeature::getValue(const std::string& key) const {
     while (tags) {
         uint32_t tag_key = tags.varint();
 
-        if (layer.keys.size() <= tag_key) {
+        if (layer.keysMap.size() <= tag_key) {
             throw std::runtime_error("feature referenced out of range key");
         }
 
@@ -84,6 +84,21 @@ optional<Value> VectorTileFeature::getValue(const std::string& key) const {
     return optional<Value>();
 }
 
+std::unordered_map<std::string,Value> VectorTileFeature::getProperties() const {
+    std::unordered_map<std::string,Value> properties;
+    pbf tags = tags_pbf;
+    while (tags) {
+        uint32_t tag_key = tags.varint();
+        uint32_t tag_val = tags.varint();
+        properties[layer.keys.at(tag_key)] = layer.values.at(tag_val);
+    }
+    return properties;
+}
+
+uint64_t VectorTileFeature::getID() const {
+    return id;
+}
+
 GeometryCollection VectorTileFeature::getGeometries() const {
     pbf data(geometry_pbf);
     uint8_t cmd = 1;
@@ -166,7 +181,7 @@ VectorTileLayer::VectorTileLayer(pbf layer_pbf) {
         } else if (layer_pbf.tag == 2) { // feature
             features.push_back(layer_pbf.message());
         } else if (layer_pbf.tag == 3) { // keys
-            keys.emplace(layer_pbf.string(), keys.size());
+            keysMap.emplace(layer_pbf.string(), keysMap.size());
         } else if (layer_pbf.tag == 4) { // values
             values.emplace_back(parseValue(layer_pbf.message()));
         } else if (layer_pbf.tag == 5) { // extent
@@ -175,12 +190,20 @@ VectorTileLayer::VectorTileLayer(pbf layer_pbf) {
             layer_pbf.skip();
         }
     }
+
+    for (auto &pair : keysMap) {
+        keys.emplace_back(std::reference_wrapper<const std::string>(pair.first));
+    }
 }
 
 util::ptr<const GeometryTileFeature> VectorTileLayer::getFeature(std::size_t i) const {
     return std::make_shared<VectorTileFeature>(features.at(i), *this);
 }
 
+std::string VectorTileLayer::getName() const {
+    return name;
+}
+
 VectorTileMonitor::VectorTileMonitor(const TileID& tileID_, float pixelRatio_, const std::string& urlTemplate_, FileSource& fileSource_)
     : tileID(tileID_),
       pixelRatio(pixelRatio_),
diff --git a/src/mbgl/tile/vector_tile.hpp b/src/mbgl/tile/vector_tile.hpp
index 4d330f17f2..0e583ab33a 100644
--- a/src/mbgl/tile/vector_tile.hpp
+++ b/src/mbgl/tile/vector_tile.hpp
@@ -6,6 +6,8 @@
 #include <mbgl/util/pbf.hpp>
 
 #include <map>
+#include <unordered_map>
+#include <functional>
 
 namespace mbgl {
 
@@ -17,6 +19,8 @@ public:
 
     FeatureType getType() const override { return type; }
     optional<Value> getValue(const std::string&) const override;
+    std::unordered_map<std::string,Value> getProperties() const override;
+    uint64_t getID() const override;
     GeometryCollection getGeometries() const override;
     uint32_t getExtent() const override;
 
@@ -34,6 +38,7 @@ public:
 
     std::size_t featureCount() const override { return features.size(); }
     util::ptr<const GeometryTileFeature> getFeature(std::size_t) const override;
+    std::string getName() const override;
 
 private:
     friend class VectorTile;
@@ -41,7 +46,8 @@ private:
 
     std::string name;
     uint32_t extent = 4096;
-    std::map<std::string, uint32_t> keys;
+    std::map<std::string, uint32_t> keysMap;
+    std::vector<std::reference_wrapper<const std::string>> keys;
     std::vector<Value> values;
     std::vector<pbf> features;
 };
diff --git a/src/mbgl/tile/vector_tile_data.cpp b/src/mbgl/tile/vector_tile_data.cpp
index 9727b4cb0b..c71b2b733d 100644
--- a/src/mbgl/tile/vector_tile_data.cpp
+++ b/src/mbgl/tile/vector_tile_data.cpp
@@ -5,6 +5,8 @@
 #include <mbgl/util/work_request.hpp>
 #include <mbgl/style/style.hpp>
 #include <mbgl/storage/file_source.hpp>
+#include <mbgl/geometry/feature_index.hpp>
+#include <mbgl/text/collision_tile.hpp>
 
 namespace mbgl {
 
@@ -65,8 +67,8 @@ VectorTileData::VectorTileData(const TileID& id_,
             }
 
             std::exception_ptr error;
-            if (result.is<TileParseResultBuckets>()) {
-                auto& resultBuckets = result.get<TileParseResultBuckets>();
+            if (result.is<TileParseResultData>()) {
+                auto& resultBuckets = result.get<TileParseResultData>();
                 state = resultBuckets.state;
 
                 // Persist the configuration we just placed so that we can later check whether we need to
@@ -77,6 +79,11 @@ VectorTileData::VectorTileData(const TileID& id_,
                 // existing buckets in case we got a refresh parse.
                 buckets = std::move(resultBuckets.buckets);
 
+                if (state == State::parsed) {
+                    featureIndex = std::move(resultBuckets.featureIndex);
+                    geometryTile = std::move(resultBuckets.geometryTile);
+                }
+
             } else {
                 error = result.get<std::exception_ptr>();
                 state = State::obsolete;
@@ -105,8 +112,8 @@ bool VectorTileData::parsePending(std::function<void(std::exception_ptr)> callba
         }
 
         std::exception_ptr error;
-        if (result.is<TileParseResultBuckets>()) {
-            auto& resultBuckets = result.get<TileParseResultBuckets>();
+        if (result.is<TileParseResultData>()) {
+            auto& resultBuckets = result.get<TileParseResultData>();
             state = resultBuckets.state;
 
             // Move over all buckets we received in this parse request, potentially overwriting
@@ -119,6 +126,11 @@ bool VectorTileData::parsePending(std::function<void(std::exception_ptr)> callba
             // place again in case the configuration has changed.
             placedConfig = config;
 
+            if (state == State::parsed) {
+                featureIndex = std::move(resultBuckets.featureIndex);
+                geometryTile = std::move(resultBuckets.geometryTile);
+            }
+
         } else {
             error = result.get<std::exception_ptr>();
             state = State::obsolete;
@@ -153,7 +165,7 @@ void VectorTileData::redoPlacement(const std::function<void()>& callback) {
     // we are parsing buckets.
     if (workRequest) return;
 
-    workRequest = worker.redoPlacement(tileWorker, buckets, targetConfig, [this, callback, config = targetConfig] {
+    workRequest = worker.redoPlacement(tileWorker, buckets, targetConfig, [this, callback, config = targetConfig](std::unique_ptr<CollisionTile> collisionTile) {
         workRequest.reset();
 
         // Persist the configuration we just placed so that we can later check whether we need to
@@ -164,6 +176,10 @@ void VectorTileData::redoPlacement(const std::function<void()>& callback) {
             bucket.second->swapRenderData();
         }
 
+        if (featureIndex) {
+            featureIndex->setCollisionTile(std::move(collisionTile));
+        }
+
         // The target configuration could have changed since we started placement. In this case,
         // we're starting another placement run.
         if (placedConfig != targetConfig) {
@@ -174,6 +190,19 @@ void VectorTileData::redoPlacement(const std::function<void()>& callback) {
     });
 }
 
+void VectorTileData::queryRenderedFeatures(
+        std::unordered_map<std::string, std::vector<std::string>>& result,
+        const GeometryCollection& queryGeometry,
+        const double bearing,
+        const double tileSize,
+        const double scale,
+        const optional<std::vector<std::string>>& layerIDs) {
+
+    if (!featureIndex || !geometryTile) return;
+
+    featureIndex->query(result, queryGeometry, bearing, tileSize, scale, layerIDs, *geometryTile, style);
+}
+
 void VectorTileData::cancel() {
     state = State::obsolete;
     tileRequest.reset();
diff --git a/src/mbgl/tile/vector_tile_data.hpp b/src/mbgl/tile/vector_tile_data.hpp
index ef405e34b4..303fe343fe 100644
--- a/src/mbgl/tile/vector_tile_data.hpp
+++ b/src/mbgl/tile/vector_tile_data.hpp
@@ -14,6 +14,7 @@ namespace mbgl {
 class Style;
 class AsyncRequest;
 class GeometryTileMonitor;
+class FeatureIndex;
 
 class VectorTileData : public TileData {
 public:
@@ -35,6 +36,14 @@ public:
 
     bool hasData() const override;
 
+    void queryRenderedFeatures(
+            std::unordered_map<std::string, std::vector<std::string>>& result,
+            const GeometryCollection& queryGeometry,
+            const double bearing,
+            const double tileSize,
+            const double scale,
+            const optional<std::vector<std::string>>& layerIDs) override;
+
     void cancel() override;
 
 private:
@@ -50,6 +59,9 @@ private:
     // objects and they get added by tile parsing operations.
     std::unordered_map<std::string, std::unique_ptr<Bucket>> buckets;
 
+    std::unique_ptr<FeatureIndex> featureIndex;
+    std::unique_ptr<const GeometryTile> geometryTile;
+
     // Stores the placement configuration of the text that is currently placed on the screen.
     PlacementConfig placedConfig;