[core] Add expression filter support (#11251)

* WIP

* WIP

* WIP

* Remove Filter::operator()(const Feature&)

* WIP

* WIP

* WIP

* WIP

* Hook up expression filter evaluator

* Replace `shared_ptr` with &reference

* Fill in implementation of `void operator()(const ExpressionFilter&)`

* Fix failing tests

* Switch back to a shared_ptr per chat with @anandthakker

* Fix benchmark compilation

* Shot in the dark to fix CI

* Shot in the dark to fix CI (part 2)

* Shot in the dark to fix CI (part 3)

* In src/mbgl/style/conversion/filter.cpp, add a port of isExpressionFilter and use it to decide in Converter<Filter>::operator() whether to parse the incoming JSON as an ExpressionFilter or one of the legacy filter types

* Remove bool Filter::operator()(const GeometryTileFeature&) const

*  Ensure the map zoom is passed into filtering operations wherever applicable

* Add expression filter tests

* Addressed PR feedback

* Implement `NSPredicate *operator()(mbgl::style::ExpressionFilter filter)`

* Fix formatting& nit

10 files changed, 307 insertions, 12 deletions

diff --git a/src/mbgl/geometry/feature_index.cpp b/src/mbgl/geometry/feature_index.cpp
index 3b5e12b54a..6fb0d5e446 100644
--- a/src/mbgl/geometry/feature_index.cpp
+++ b/src/mbgl/geometry/feature_index.cpp
@@ -125,7 +125,7 @@ void FeatureIndex::addFeature(
             continue;
         }
 
-        if (options.filter && !(*options.filter)(*geometryTileFeature)) {
+        if (options.filter && !(*options.filter)(style::expression::EvaluationContext { static_cast<float>(tileID.z), geometryTileFeature.get() })) {
             continue;
         }
 
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index a41a98fcaf..3bf85407c6 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -100,7 +100,7 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
     const size_t featureCount = sourceLayer->featureCount();
     for (size_t i = 0; i < featureCount; ++i) {
         auto feature = sourceLayer->getFeature(i);
-        if (!leader.filter(feature->getType(), feature->getID(), [&] (const auto& key) { return feature->getValue(key); }))
+        if (!leader.filter(expression::EvaluationContext { this->zoom, feature.get() }))
             continue;
         
         SymbolFeature ft(std::move(feature));
diff --git a/src/mbgl/style/conversion/filter.cpp b/src/mbgl/style/conversion/filter.cpp
index bb7bb6ea98..fba149da12 100644
--- a/src/mbgl/style/conversion/filter.cpp
+++ b/src/mbgl/style/conversion/filter.cpp
@@ -1,11 +1,52 @@
 #include <mbgl/style/conversion/filter.hpp>
 #include <mbgl/util/geometry.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/conversion/expression.hpp>
 
 namespace mbgl {
 namespace style {
 namespace conversion {
+    
+using GeometryValue = mapbox::geometry::value;
 
-static optional<Value> normalizeValue(const optional<Value>& value, Error& error) {
+// This is a port from https://github.com/mapbox/mapbox-gl-js/blob/master/src/style-spec/feature_filter/index.js
+static bool isExpressionFilter(const Convertible& filter) {
+    if (!isArray(filter) || arrayLength(filter) == 0) {
+        return false;
+    }
+    
+    optional<std::string> op = toString(arrayMember(filter, 0));
+    
+    if (!op) {
+        return false;
+
+    } else if (*op == "has") {
+        if (arrayLength(filter) < 2) return false;
+        optional<std::string> operand = toString(arrayMember(filter, 1));
+        return operand && *operand != "$id" && *operand != "$type";
+        
+    } else if (*op == "in" || *op == "!in" || *op == "!has" || *op == "none") {
+        return false;
+        
+    } else if (*op == "==" || *op == "!=" || *op == ">" || *op == ">=" || *op == "<" || *op == "<=") {
+        return arrayLength(filter) == 3 && (isArray(arrayMember(filter, 1)) || isArray(arrayMember(filter, 2)));
+        
+    } else if (*op == "any" || *op == "all") {
+        for (std::size_t i = 1; i < arrayLength(filter); i++) {
+            Convertible f = arrayMember(filter, i);
+            if (!isExpressionFilter(f) && !toBool(f)) {
+                return false;
+            }
+        }
+        return true;
+        
+    } else {
+        return true;
+    }
+}
+    
+static optional<GeometryValue> normalizeValue(const optional<GeometryValue>& value, Error& error) {
     if (!value) {
         error = { "filter expression value must be a boolean, number, or string" };
         return {};
@@ -32,7 +73,7 @@ static optional<FeatureType> toFeatureType(const Convertible& value, Error& erro
 }
 
 static optional<FeatureIdentifier> toFeatureIdentifier(const Convertible& value, Error& error) {
-    optional<Value> identifier = toValue(value);
+    optional<GeometryValue> identifier = toValue(value);
     if (!identifier) {
         error = { "filter expression value must be a boolean, number, or string" };
         return {};
@@ -99,7 +140,7 @@ optional<Filter> convertEqualityFilter(const Convertible& value, Error& error) {
         return { IdentifierFilterType { *filterValue } };
 
     } else {
-        optional<Value> filterValue = normalizeValue(toValue(arrayMember(value, 2)), error);
+        optional<GeometryValue> filterValue = normalizeValue(toValue(arrayMember(value, 2)), error);
         if (!filterValue) {
             return {};
         }
@@ -121,7 +162,7 @@ optional<Filter> convertBinaryFilter(const Convertible& value, Error& error) {
         return {};
     }
 
-    optional<Value> filterValue = normalizeValue(toValue(arrayMember(value, 2)), error);
+    optional<GeometryValue> filterValue = normalizeValue(toValue(arrayMember(value, 2)), error);
     if (!filterValue) {
         return {};
     }
@@ -167,9 +208,9 @@ optional<Filter> convertSetFilter(const Convertible& value, Error& error) {
         return { IdentifierFilterType { std::move(values) } };
 
     } else {
-        std::vector<Value> values;
+        std::vector<GeometryValue> values;
         for (std::size_t i = 2; i < arrayLength(value); ++i) {
-            optional<Value> filterValue = normalizeValue(toValue(arrayMember(value, i)), error);
+            optional<GeometryValue> filterValue = normalizeValue(toValue(arrayMember(value, i)), error);
             if (!filterValue) {
                 return {};
             }
@@ -193,8 +234,20 @@ optional<Filter> convertCompoundFilter(const Convertible& value, Error& error) {
 
     return { FilterType { std::move(filters) } };
 }
+    
+optional<Filter> convertExpressionFilter(const Convertible& value, Error& error) {
+    optional<std::unique_ptr<Expression>> expression = convert<std::unique_ptr<Expression>>(value, error, expression::type::Boolean);
+    if (!expression) {
+        return {};
+    }
+    return { ExpressionFilter { std::move(*expression) } };
+}
 
 optional<Filter> Converter<Filter>::operator()(const Convertible& value, Error& error) const {
+    if (isExpressionFilter(value)) {
+        return convertExpressionFilter(value, error);
+    }
+    
     if (!isArray(value)) {
         error = { "filter expression must be an array" };
         return {};
diff --git a/src/mbgl/style/conversion/stringify.hpp b/src/mbgl/style/conversion/stringify.hpp
index 6ae6fede42..7924a442c4 100644
--- a/src/mbgl/style/conversion/stringify.hpp
+++ b/src/mbgl/style/conversion/stringify.hpp
@@ -225,6 +225,10 @@ public:
     void operator()(const NotHasIdentifierFilter&) {
         stringifyUnaryFilter("!has", "$id");
     }
+    
+    void operator()(const ExpressionFilter& filter) {
+        stringify(writer, filter.expression->serialize());
+    }
 
 private:
     template <class F>
diff --git a/src/mbgl/style/filter.cpp b/src/mbgl/style/filter.cpp
new file mode 100644
index 0000000000..51aa6bcf82
--- /dev/null
+++ b/src/mbgl/style/filter.cpp
@@ -0,0 +1,13 @@
+#include <mbgl/style/filter.hpp>
+#include <mbgl/style/filter_evaluator.hpp>
+#include <mbgl/tile/geometry_tile_data.hpp>
+
+namespace mbgl {
+namespace style {
+
+bool Filter::operator()(const expression::EvaluationContext &context) const {
+    return FilterBase::visit(*this, FilterEvaluator { context });
+}
+
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/filter_evaluator.cpp b/src/mbgl/style/filter_evaluator.cpp
new file mode 100644
index 0000000000..72022172f4
--- /dev/null
+++ b/src/mbgl/style/filter_evaluator.cpp
@@ -0,0 +1,225 @@
+#include <mbgl/style/filter.hpp>
+#include <mbgl/style/filter_evaluator.hpp>
+#include <mbgl/tile/geometry_tile_data.hpp>
+
+namespace mbgl {
+namespace style {
+    
+template <class Op>
+struct Comparator {
+    const Op& op;
+    
+    template <class T>
+    bool operator()(const T& lhs, const T& rhs) const {
+        return op(lhs, rhs);
+    }
+    
+    template <class T0, class T1>
+    auto operator()(const T0& lhs, const T1& rhs) const
+    -> typename std::enable_if_t<std::is_arithmetic<T0>::value && !std::is_same<T0, bool>::value &&
+    std::is_arithmetic<T1>::value && !std::is_same<T1, bool>::value, bool> {
+        return op(double(lhs), double(rhs));
+    }
+    
+    template <class T0, class T1>
+    auto operator()(const T0&, const T1&) const
+    -> typename std::enable_if_t<!std::is_arithmetic<T0>::value || std::is_same<T0, bool>::value ||
+    !std::is_arithmetic<T1>::value || std::is_same<T1, bool>::value, bool> {
+        return false;
+    }
+    
+    bool operator()(const NullValue&,
+                    const NullValue&) const {
+        // Should be unreachable; null is not currently allowed by the style specification.
+        assert(false);
+        return false;
+    }
+    
+    bool operator()(const std::vector<Value>&,
+                    const std::vector<Value>&) const {
+        // Should be unreachable; nested values are not currently allowed by the style specification.
+        assert(false);
+        return false;
+    }
+    
+    bool operator()(const PropertyMap&,
+                    const PropertyMap&) const {
+        // Should be unreachable; nested values are not currently allowed by the style specification.
+        assert(false);
+        return false;
+    }
+};
+
+template <class Op>
+bool compare(const Value& lhs, const Value& rhs, const Op& op) {
+    return Value::binary_visit(lhs, rhs, Comparator<Op> { op });
+}
+
+bool equal(const Value& lhs, const Value& rhs) {
+    return compare(lhs, rhs, [] (const auto& lhs_, const auto& rhs_) { return lhs_ == rhs_; });
+}
+
+bool FilterEvaluator::operator()(const NullFilter&) const {
+    return true;
+}
+
+bool FilterEvaluator::operator()(const EqualsFilter& filter) const {
+    optional<Value> actual = context.feature->getValue(filter.key);
+    return actual && equal(*actual, filter.value);
+}
+
+bool FilterEvaluator::operator()(const NotEqualsFilter& filter) const {
+    optional<Value> actual = context.feature->getValue(filter.key);
+    return !actual || !equal(*actual, filter.value);
+}
+
+bool FilterEvaluator::operator()(const LessThanFilter& filter) const {
+    optional<Value> actual = context.feature->getValue(filter.key);
+    return actual && compare(*actual, filter.value, [] (const auto& lhs_, const auto& rhs_) { return lhs_ < rhs_; });
+}
+
+bool FilterEvaluator::operator()(const LessThanEqualsFilter& filter) const {
+    optional<Value> actual = context.feature->getValue(filter.key);
+    return actual && compare(*actual, filter.value, [] (const auto& lhs_, const auto& rhs_) { return lhs_ <= rhs_; });
+}
+
+bool FilterEvaluator::operator()(const GreaterThanFilter& filter) const {
+    optional<Value> actual = context.feature->getValue(filter.key);
+    return actual && compare(*actual, filter.value, [] (const auto& lhs_, const auto& rhs_) { return lhs_ > rhs_; });
+}
+
+bool FilterEvaluator::operator()(const GreaterThanEqualsFilter& filter) const {
+    optional<Value> actual = context.feature->getValue(filter.key);
+    return actual && compare(*actual, filter.value, [] (const auto& lhs_, const auto& rhs_) { return lhs_ >= rhs_; });
+}
+
+bool FilterEvaluator::operator()(const InFilter& filter) const {
+    optional<Value> actual = context.feature->getValue(filter.key);
+    if (!actual)
+        return false;
+    for (const auto& v: filter.values) {
+        if (equal(*actual, v)) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool FilterEvaluator::operator()(const NotInFilter& filter) const {
+    optional<Value> actual = context.feature->getValue(filter.key);
+    if (!actual)
+        return true;
+    for (const auto& v: filter.values) {
+        if (equal(*actual, v)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+bool FilterEvaluator::operator()(const AnyFilter& filter) const {
+    for (const auto& f: filter.filters) {
+        if (Filter::visit(f, *this)) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool FilterEvaluator::operator()(const AllFilter& filter) const {
+    for (const auto& f: filter.filters) {
+        if (!Filter::visit(f, *this)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+bool FilterEvaluator::operator()(const NoneFilter& filter) const {
+    for (const auto& f: filter.filters) {
+        if (Filter::visit(f, *this)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+bool FilterEvaluator::operator()(const HasFilter& filter) const {
+    return bool(context.feature->getValue(filter.key));
+}
+
+bool FilterEvaluator::operator()(const NotHasFilter& filter) const {
+    return !context.feature->getValue(filter.key);
+}
+
+bool FilterEvaluator::operator()(const TypeEqualsFilter& filter) const {
+    return context.feature->getType() == filter.value;
+}
+
+bool FilterEvaluator::operator()(const TypeNotEqualsFilter& filter) const {
+    return context.feature->getType() != filter.value;
+}
+
+bool FilterEvaluator::operator()(const TypeInFilter& filter) const {
+    for (const auto& v: filter.values) {
+        if (context.feature->getType() == v) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool FilterEvaluator::operator()(const TypeNotInFilter& filter) const {
+    for (const auto& v: filter.values) {
+        if (context.feature->getType() == v) {
+            return false;
+        }
+    }
+    return true;
+}
+
+bool FilterEvaluator::operator()(const IdentifierEqualsFilter& filter) const {
+    return context.feature->getID() == filter.value;
+}
+
+bool FilterEvaluator::operator()(const IdentifierNotEqualsFilter& filter) const {
+    return context.feature->getID() != filter.value;
+}
+
+bool FilterEvaluator::operator()(const IdentifierInFilter& filter) const {
+    for (const auto& v: filter.values) {
+        if (context.feature->getID() == v) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool FilterEvaluator::operator()(const IdentifierNotInFilter& filter) const {
+    for (const auto& v: filter.values) {
+        if (context.feature->getID() == v) {
+            return false;
+        }
+    }
+    return true;
+}
+
+bool FilterEvaluator::operator()(const HasIdentifierFilter&) const {
+    return bool(context.feature->getID());
+}
+
+bool FilterEvaluator::operator()(const NotHasIdentifierFilter&) const {
+    return !context.feature->getID();
+}
+
+bool FilterEvaluator::operator()(const ExpressionFilter& filter) const {
+    const expression::EvaluationResult result = filter.expression->evaluate(context);
+    if (result) {
+        const optional<bool> typed = expression::fromExpressionValue<bool>(*result);
+        return typed ? *typed : false;
+    }
+    return false;
+}
+    
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/tile/custom_geometry_tile.cpp b/src/mbgl/tile/custom_geometry_tile.cpp
index 33962ad87d..a2fefcfa9f 100644
--- a/src/mbgl/tile/custom_geometry_tile.cpp
+++ b/src/mbgl/tile/custom_geometry_tile.cpp
@@ -79,7 +79,7 @@ void CustomGeometryTile::querySourceFeatures(
             auto feature = layer->getFeature(i);
             
             // Apply filter, if any
-            if (queryOptions.filter && !(*queryOptions.filter)(*feature)) {
+            if (queryOptions.filter && !(*queryOptions.filter)(style::expression::EvaluationContext { static_cast<float>(id.overscaledZ), feature.get() })) {
                 continue;
             }
 
diff --git a/src/mbgl/tile/geojson_tile.cpp b/src/mbgl/tile/geojson_tile.cpp
index bbec899950..f211c03569 100644
--- a/src/mbgl/tile/geojson_tile.cpp
+++ b/src/mbgl/tile/geojson_tile.cpp
@@ -30,7 +30,7 @@ void GeoJSONTile::querySourceFeatures(
                 auto feature = layer->getFeature(i);
 
                 // Apply filter, if any
-                if (options.filter && !(*options.filter)(*feature)) {
+                if (options.filter && !(*options.filter)(style::expression::EvaluationContext { static_cast<float>(this->id.overscaledZ), feature.get() })) {
                     continue;
                 }
 
diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp
index a58c744065..82d0c91806 100644
--- a/src/mbgl/tile/geometry_tile.cpp
+++ b/src/mbgl/tile/geometry_tile.cpp
@@ -281,7 +281,7 @@ void GeometryTile::querySourceFeatures(
                 auto feature = layer->getFeature(i);
 
                 // Apply filter, if any
-                if (options.filter && !(*options.filter)(*feature)) {
+                if (options.filter && !(*options.filter)(style::expression::EvaluationContext { static_cast<float>(this->id.overscaledZ), feature.get() })) {
                     continue;
                 }
 
diff --git a/src/mbgl/tile/geometry_tile_worker.cpp b/src/mbgl/tile/geometry_tile_worker.cpp
index 24841dd125..8b6f1f63bf 100644
--- a/src/mbgl/tile/geometry_tile_worker.cpp
+++ b/src/mbgl/tile/geometry_tile_worker.cpp
@@ -339,7 +339,7 @@ void GeometryTileWorker::redoLayout() {
             for (std::size_t i = 0; !obsolete && i < geometryLayer->featureCount(); i++) {
                 std::unique_ptr<GeometryTileFeature> feature = geometryLayer->getFeature(i);
 
-                if (!filter(feature->getType(), feature->getID(), [&] (const auto& key) { return feature->getValue(key); }))
+                if (!filter(expression::EvaluationContext { static_cast<float>(this->id.overscaledZ), feature.get() }))
                     continue;
 
                 GeometryCollection geometries = feature->getGeometries();