[core] Implement 'in' expression. (#16162)

* Implement in.cpp

* Fix review comments.

* Add expression_equality test for 'in'

* Fix review comments.

* [core] Update changelog.

* [core] Update mapbox-gl-js

* [core] Ignore render-tests/debug/padding

* [core] Update baseline.

12 files changed, 224 insertions, 13 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index fb643dd222..ce1d4f4a69 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -22,9 +22,13 @@
    
   The `within expression` enables checking whether a feature is inside a pre-defined geometry set/boundary or not. This `within expression` returns a boolean value, `true` indicates that the feature being evaluated is inside the geometry set. The returned value can be then consumed as input by another expression or used directly by a paint/layer property.
  
-  Support for using `within expression` with layout propery will be implemented separately.
+  Support for using `within expression` with layout property will be implemented separately.
 
-- [core] Add support for using `within expression` with layout propery. ([#16194](https://github.com/mapbox/mapbox-gl-native/pull/16194))
+- [core] Add support for using `within expression` with layout property. ([#16194](https://github.com/mapbox/mapbox-gl-native/pull/16194))
+
+- [core] Add support for `in expression`. ([#16162](https://github.com/mapbox/mapbox-gl-native/pull/16162))
+   
+  The `in expression` enables checking whether a Number/String/Boolean type item is in a String/Array and returns a boolean value.
 
 ### 🐞 Bug fixes
 
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 485ced04aa..deb000db9f 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -195,6 +195,7 @@ add_library(
     ${PROJECT_SOURCE_DIR}/include/mbgl/style/expression/get_covering_stops.hpp
     ${PROJECT_SOURCE_DIR}/include/mbgl/style/expression/image.hpp
     ${PROJECT_SOURCE_DIR}/include/mbgl/style/expression/image_expression.hpp
+    ${PROJECT_SOURCE_DIR}/include/mbgl/style/expression/in.hpp
     ${PROJECT_SOURCE_DIR}/include/mbgl/style/expression/interpolate.hpp
     ${PROJECT_SOURCE_DIR}/include/mbgl/style/expression/interpolator.hpp
     ${PROJECT_SOURCE_DIR}/include/mbgl/style/expression/is_constant.hpp
@@ -586,6 +587,7 @@ add_library(
     ${PROJECT_SOURCE_DIR}/src/mbgl/style/expression/get_covering_stops.cpp
     ${PROJECT_SOURCE_DIR}/src/mbgl/style/expression/image.cpp
     ${PROJECT_SOURCE_DIR}/src/mbgl/style/expression/image_expression.cpp
+    ${PROJECT_SOURCE_DIR}/src/mbgl/style/expression/in.cpp
     ${PROJECT_SOURCE_DIR}/src/mbgl/style/expression/interpolate.cpp
     ${PROJECT_SOURCE_DIR}/src/mbgl/style/expression/is_constant.cpp
     ${PROJECT_SOURCE_DIR}/src/mbgl/style/expression/is_expression.cpp
diff --git a/include/mbgl/style/expression/expression.hpp b/include/mbgl/style/expression/expression.hpp
index 0fd5c4959e..e522821185 100644
--- a/include/mbgl/style/expression/expression.hpp
+++ b/include/mbgl/style/expression/expression.hpp
@@ -168,6 +168,7 @@ enum class Kind : int32_t {
     FormatSectionOverride,
     NumberFormat,
     ImageExpression,
+    In,
     Within
 };
 
diff --git a/include/mbgl/style/expression/in.hpp b/include/mbgl/style/expression/in.hpp
new file mode 100644
index 0000000000..a7de17c94d
--- /dev/null
+++ b/include/mbgl/style/expression/in.hpp
@@ -0,0 +1,33 @@
+#pragma once
+
+#include <mbgl/style/conversion.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <memory>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class In final : public Expression {
+public:
+    In(std::unique_ptr<Expression> needle_, std::unique_ptr<Expression> haystack_);
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx);
+
+    EvaluationResult evaluate(const EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>&) const override;
+
+    bool operator==(const Expression& e) const override;
+
+    std::vector<optional<Value>> possibleOutputs() const override;
+
+    std::string getOperator() const override;
+
+private:
+    std::unique_ptr<Expression> needle;
+    std::unique_ptr<Expression> haystack;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/mapbox-gl-js b/mapbox-gl-js
-Subproject 9c5ac9c17545026d7ff05004be724f542b8c324
+Subproject 8905d24ffa30f4f5d5ebbd67fbbf8664dc12301
diff --git a/metrics/binary-size/macos-xcode11/metrics.json b/metrics/binary-size/macos-xcode11/metrics.json
index 06a6687143..7bd94ba992 100644
--- a/metrics/binary-size/macos-xcode11/metrics.json
+++ b/metrics/binary-size/macos-xcode11/metrics.json
@@ -3,17 +3,17 @@
         [
             "mbgl-glfw",
             "/tmp/attach/install/macos-xcode11-release/bin/mbgl-glfw",
-            5616056
+            5677792
         ],
         [
             "mbgl-offline",
             "/tmp/attach/install/macos-xcode11-release/bin/mbgl-offline",
-            5484604
+            5542252
         ],
         [
             "mbgl-render",
             "/tmp/attach/install/macos-xcode11-release/bin/mbgl-render",
-            5530720
+            5588368
         ]
     ]
 }
\ No newline at end of file
diff --git a/metrics/ignores/platform-all.json b/metrics/ignores/platform-all.json
index b53e923a9d..0ea2dbbc6d 100644
--- a/metrics/ignores/platform-all.json
+++ b/metrics/ignores/platform-all.json
@@ -1,11 +1,5 @@
 {
     "expression-tests/collator/accent-equals-de": "Locale-specific behavior changes based on platform.",
-    "expression-tests/in/assert-array": "https://github.com/mapbox/mapbox-gl-native/issues/15893",
-    "expression-tests/in/assert-string": "https://github.com/mapbox/mapbox-gl-native/issues/15893",
-    "expression-tests/in/basic-array": "https://github.com/mapbox/mapbox-gl-native/issues/15893",
-    "expression-tests/in/basic-string": "https://github.com/mapbox/mapbox-gl-native/issues/15893",
-    "expression-tests/in/invalid-haystack": "https://github.com/mapbox/mapbox-gl-native/issues/15893",
-    "expression-tests/in/invalid-needle": "https://github.com/mapbox/mapbox-gl-native/issues/15893",
     "expression-tests/interpolate-hcl/linear": "https://github.com/mapbox/mapbox-gl-native/issues/8720",
     "expression-tests/interpolate-lab/linear": "https://github.com/mapbox/mapbox-gl-native/issues/8720",
     "expression-tests/is-supported-script/default": "This tests RTL text plugin behavior specific to GL JS",
@@ -68,6 +62,12 @@
     "render-tests/custom-layer-js/tent-3d": "skip - js specific",
     "render-tests/debug/collision": "https://github.com/mapbox/mapbox-gl-native/issues/3841",
     "render-tests/debug/overdraw": "https://github.com/mapbox/mapbox-gl-native/issues/15638",
+    "render-tests/debug/padding/ease-to-btm-distort": "https://github.com/mapbox/mapbox-gl-native/issues/16212",
+    "render-tests/debug/padding/ease-to-left-distort": "https://github.com/mapbox/mapbox-gl-native/issues/16212",
+    "render-tests/debug/padding/ease-to-no-distort": "https://github.com/mapbox/mapbox-gl-native/issues/16212",
+    "render-tests/debug/padding/ease-to-right-distort": "https://github.com/mapbox/mapbox-gl-native/issues/16212",
+    "render-tests/debug/padding/ease-to-top-distort": "https://github.com/mapbox/mapbox-gl-native/issues/16212",
+    "render-tests/debug/padding/set-padding": "https://github.com/mapbox/mapbox-gl-native/issues/16212",
     "render-tests/debug/raster": "https://github.com/mapbox/mapbox-gl-native/issues/15510",
     "render-tests/debug/tile": "https://github.com/mapbox/mapbox-gl-native/issues/3841",
     "render-tests/debug/tile-overscaled": "https://github.com/mapbox/mapbox-gl-native/issues/3841",
diff --git a/src/mbgl/style/expression/in.cpp b/src/mbgl/style/expression/in.cpp
new file mode 100644
index 0000000000..fa2bd83656
--- /dev/null
+++ b/src/mbgl/style/expression/in.cpp
@@ -0,0 +1,130 @@
+#include <string.h>
+#include <mbgl/style/conversion_impl.hpp>
+#include <mbgl/style/expression/in.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+namespace {
+bool isComparableType(type::Type type) {
+    return type == type::Boolean || type == type::String || type == type::Number || type == type::Null ||
+           type == type::Value;
+}
+
+bool isComparableRuntimeType(type::Type type) {
+    return type == type::Boolean || type == type::String || type == type::Number || type == type::Null;
+}
+
+bool isSearchableType(type::Type type) {
+    return type == type::String || type.is<type::Array>() || type == type::Null || type == type::Value;
+}
+
+bool isSearchableRuntimeType(type::Type type) {
+    return type == type::String || type.is<type::Array>() || type == type::Null;
+}
+} // namespace
+
+In::In(std::unique_ptr<Expression> needle_, std::unique_ptr<Expression> haystack_)
+    : Expression(Kind::In, type::Boolean), needle(std::move(needle_)), haystack(std::move(haystack_)) {
+    assert(isComparableType(needle->getType()));
+    assert(isSearchableType(haystack->getType()));
+}
+
+EvaluationResult In::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult evaluatedHaystack = haystack->evaluate(params);
+    if (!evaluatedHaystack) {
+        return evaluatedHaystack.error();
+    }
+
+    const EvaluationResult evaluatedNeedle = needle->evaluate(params);
+    if (!evaluatedNeedle) {
+        return evaluatedNeedle.error();
+    }
+
+    type::Type evaluatedNeedleType = typeOf(*evaluatedNeedle);
+    if (!isComparableRuntimeType(evaluatedNeedleType)) {
+        return EvaluationError{"Expected first argument to be of type boolean, string or number, but found " +
+                               toString(evaluatedNeedleType) + " instead."};
+    }
+
+    type::Type evaluatedHaystackType = typeOf(*evaluatedHaystack);
+    if (!isSearchableRuntimeType(evaluatedHaystackType)) {
+        return EvaluationError{"Expected second argument to be of type array or string, but found " +
+                               toString(evaluatedHaystackType) + " instead."};
+    }
+
+    if (evaluatedNeedleType == type::Null || evaluatedHaystackType == type::Null) {
+        return EvaluationResult(false);
+    }
+
+    if (evaluatedHaystackType == type::String) {
+        const auto haystackString = evaluatedHaystack->get<std::string>();
+        const auto needleString = toString(*evaluatedNeedle);
+        return EvaluationResult(haystackString.find(needleString) != std::string::npos);
+    } else {
+        const auto haystackArray = evaluatedHaystack->get<std::vector<Value>>();
+        return EvaluationResult(std::find(haystackArray.begin(), haystackArray.end(), *evaluatedNeedle) !=
+                                haystackArray.end());
+    }
+}
+
+void In::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*needle);
+    visit(*haystack);
+}
+
+using namespace mbgl::style::conversion;
+ParseResult In::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    std::size_t length = arrayLength(value);
+    if (length != 3) {
+        ctx.error("Expected 2 arguments, but found " + util::toString(length - 1) + " instead.");
+        return ParseResult();
+    }
+
+    ParseResult needle = ctx.parse(arrayMember(value, 1), 1, {type::Value});
+    if (!needle) return ParseResult();
+
+    ParseResult haystack = ctx.parse(arrayMember(value, 2), 2, {type::Value});
+    if (!haystack) return ParseResult();
+
+    type::Type needleType = (*needle)->getType();
+    type::Type haystackType = (*haystack)->getType();
+
+    if (!isComparableType(needleType)) {
+        ctx.error("Expected first argument to be of type boolean, string or number, but found " + toString(needleType) +
+                  " instead.");
+        return ParseResult();
+    }
+
+    if (!isSearchableType(haystackType)) {
+        ctx.error("Expected second argument to be of type array or string, but found " + toString(haystackType) +
+                  " instead.");
+        return ParseResult();
+    }
+    return ParseResult(std::make_unique<In>(std::move(*needle), std::move(*haystack)));
+}
+
+bool In::operator==(const Expression& e) const {
+    if (e.getKind() == Kind::In) {
+        auto rhs = static_cast<const In*>(&e);
+        return *needle == *(rhs->needle) && *haystack == *(rhs->haystack);
+    }
+    return false;
+}
+
+std::vector<optional<Value>> In::possibleOutputs() const {
+    return {{true}, {false}};
+}
+
+std::string In::getOperator() const {
+    return "in";
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/parsing_context.cpp b/src/mbgl/style/expression/parsing_context.cpp
index d42c46bb09..2f1e1c1820 100644
--- a/src/mbgl/style/expression/parsing_context.cpp
+++ b/src/mbgl/style/expression/parsing_context.cpp
@@ -15,6 +15,7 @@
 #include <mbgl/style/expression/expression.hpp>
 #include <mbgl/style/expression/format_expression.hpp>
 #include <mbgl/style/expression/image_expression.hpp>
+#include <mbgl/style/expression/in.hpp>
 #include <mbgl/style/expression/interpolate.hpp>
 #include <mbgl/style/expression/length.hpp>
 #include <mbgl/style/expression/let.hpp>
@@ -114,6 +115,7 @@ MAPBOX_ETERNAL_CONSTEXPR const auto expressionRegistry =
         {"any", Any::parse},
         {"array", Assertion::parse},
         {"at", At::parse},
+        {"in", In::parse},
         {"boolean", Assertion::parse},
         {"case", Case::parse},
         {"coalesce", Coalesce::parse},
diff --git a/test/fixtures/expression_equality/in.a.json b/test/fixtures/expression_equality/in.a.json
new file mode 100644
index 0000000000..2632695c6f
--- /dev/null
+++ b/test/fixtures/expression_equality/in.a.json
@@ -0,0 +1,20 @@
+[
+  "number",
+  [
+    "in",
+    [
+      "number",
+      [
+        "get",
+        "i"
+      ]
+    ],
+    [
+      "array",
+      [
+        "get",
+        "arr"
+      ]
+    ]
+  ]
+]
\ No newline at end of file
diff --git a/test/fixtures/expression_equality/in.b.json b/test/fixtures/expression_equality/in.b.json
new file mode 100644
index 0000000000..a63a94fb00
--- /dev/null
+++ b/test/fixtures/expression_equality/in.b.json
@@ -0,0 +1,20 @@
+[
+  "number",
+  [
+    "in",
+    [
+      "number",
+      [
+        "get",
+        "i"
+      ]
+    ],
+    [
+      "array",
+      [
+        "get",
+        "arr_other"
+      ]
+    ]
+  ]
+]
\ No newline at end of file
diff --git a/test/style/expression/expression.test.cpp b/test/style/expression/expression.test.cpp
index bffadf1668..b137df769a 100644
--- a/test/style/expression/expression.test.cpp
+++ b/test/style/expression/expression.test.cpp
@@ -35,8 +35,7 @@ TEST(Expression, IsExpression) {
 
         // TODO: "interpolate-hcl": https://github.com/mapbox/mapbox-gl-native/issues/8720
         // TODO: "interpolate-lab": https://github.com/mapbox/mapbox-gl-native/issues/8720
-        // TODO: "in": https://github.com/mapbox/mapbox-gl-native/issues/15893
-        if (name == "interpolate-hcl" || name == "interpolate-lab" || name == "in") {
+        if (name == "interpolate-hcl" || name == "interpolate-lab") {
             if (expression::isExpression(conversion::Convertible(expression))) {
                 ASSERT_TRUE(false) << "Expression name" << name << "is implemented - please update Expression.IsExpression test.";
             }