Collator native port step 1:

 - CollatorExpression parsing/evaluation/etc.
 - Hook up comparison operators to Collator
 - Stub darwin Collator implementation that doesn't do anything yet

14 files changed, 312 insertions, 7 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index 7e48b336b4..e0f7595d48 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -447,6 +447,8 @@ set(MBGL_CORE_FILES
     include/mbgl/style/expression/check_subtype.hpp
     include/mbgl/style/expression/coalesce.hpp
     include/mbgl/style/expression/coercion.hpp
+    include/mbgl/style/expression/collator.hpp
+    include/mbgl/style/expression/collator_expression.hpp
     include/mbgl/style/expression/compound_expression.hpp
     include/mbgl/style/expression/equals.hpp
     include/mbgl/style/expression/expression.hpp
@@ -471,6 +473,7 @@ set(MBGL_CORE_FILES
     src/mbgl/style/expression/check_subtype.cpp
     src/mbgl/style/expression/coalesce.cpp
     src/mbgl/style/expression/coercion.cpp
+    src/mbgl/style/expression/collator_expression.cpp
     src/mbgl/style/expression/compound_expression.cpp
     src/mbgl/style/expression/equals.cpp
     src/mbgl/style/expression/find_zoom_curve.cpp
diff --git a/include/mbgl/style/expression/collator.hpp b/include/mbgl/style/expression/collator.hpp
new file mode 100644
index 0000000000..c4b47c9453
--- /dev/null
+++ b/include/mbgl/style/expression/collator.hpp
@@ -0,0 +1,36 @@
+#pragma once
+
+#include <mbgl/util/feature.hpp>
+#include <mbgl/util/optional.hpp>
+
+#include <string>
+#include <memory>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Collator {
+public:
+    Collator(bool caseSensitive, bool diacriticSensitive, const std::string& locale);
+    Collator(bool caseSensitive, bool diacriticSenstive);
+
+    bool operator==(const Collator& other) const;
+    
+    int compare(const std::string& lhs, const std::string& rhs) const;
+    
+    const std::string& resolvedLocale() const;
+    
+    // TODO: This serialization shouldn't ever be used, but since we're part of
+    // mbgl::style::expression::Value we're expected to have a serialize()
+    mbgl::Value serialize() const;
+    
+private:
+//    bool caseSensitive;
+//    bool diacriticSensitive;
+//    optional<std::string> locale;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/collator_expression.hpp b/include/mbgl/style/expression/collator_expression.hpp
new file mode 100644
index 0000000000..9e7b527e89
--- /dev/null
+++ b/include/mbgl/style/expression/collator_expression.hpp
@@ -0,0 +1,44 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <memory>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class CollatorExpression : public Expression {
+public:
+    CollatorExpression(std::unique_ptr<Expression> caseSensitive,
+             std::unique_ptr<Expression> diacriticSensitive,
+             std::unique_ptr<Expression> locale);
+
+    EvaluationResult evaluate(const EvaluationContext&) const override;
+    static ParseResult parse(const mbgl::style::conversion::Convertible&, ParsingContext&);
+
+    void eachChild(const std::function<void(const Expression&)>&) const override;
+
+    bool operator==(const Expression& e) const override;
+
+    std::vector<optional<Value>> possibleOutputs() const override {
+        // Technically the set of possible outputs is the combinatoric set of Collators produced
+        // by all possibleOutputs of locale/caseSensitive/diacriticSensitive
+        // But for the primary use of Collators in comparison operators, we ignore the Collator's
+        // possibleOutputs anyway, so we can get away with leaving this undefined for now.
+        return { nullopt };
+    }
+
+    mbgl::Value serialize() const override;
+    std::string getOperator() const override { return "collator"; }
+private:
+    std::unique_ptr<Expression> caseSensitive;
+    std::unique_ptr<Expression> diacriticSensitive;
+    std::unique_ptr<Expression> locale;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/equals.hpp b/include/mbgl/style/expression/equals.hpp
index 54df890a68..3458eede91 100644
--- a/include/mbgl/style/expression/equals.hpp
+++ b/include/mbgl/style/expression/equals.hpp
@@ -1,5 +1,6 @@
 #pragma once
 
+#include <mbgl/style/expression/collator_expression.hpp>
 #include <mbgl/style/expression/expression.hpp>
 #include <mbgl/style/expression/parsing_context.hpp>
 #include <mbgl/style/conversion.hpp>
@@ -12,7 +13,7 @@ namespace expression {
 
 class Equals : public Expression {
 public:
-    Equals(std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs, bool negate);
+    Equals(std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs, std::unique_ptr<Expression> collator, bool negate);
 
     static ParseResult parse(const mbgl::style::conversion::Convertible&, ParsingContext&);
 
@@ -25,6 +26,7 @@ public:
 private:
     std::unique_ptr<Expression> lhs;
     std::unique_ptr<Expression> rhs;
+    std::unique_ptr<Expression> collator;
     bool negate;
 };
 
diff --git a/include/mbgl/style/expression/type.hpp b/include/mbgl/style/expression/type.hpp
index 513c4bdc17..0909b67c81 100644
--- a/include/mbgl/style/expression/type.hpp
+++ b/include/mbgl/style/expression/type.hpp
@@ -60,6 +60,12 @@ struct ValueType {
     std::string getName() const { return "value"; }
     bool operator==(const ValueType&) const { return true; }
 };
+    
+struct CollatorType {
+    constexpr CollatorType() {}; // NOLINT
+    std::string getName() const { return "collator"; }
+    bool operator==(const CollatorType&) const { return true; }
+};
 
 constexpr NullType Null;
 constexpr NumberType Number;
@@ -69,6 +75,7 @@ constexpr ColorType Color;
 constexpr ValueType Value;
 constexpr ObjectType Object;
 constexpr ErrorType Error;
+constexpr CollatorType Collator;
 
 struct Array;
 
@@ -81,7 +88,8 @@ using Type = variant<
     ObjectType,
     ValueType,
     mapbox::util::recursive_wrapper<Array>,
-    ErrorType>;
+    ErrorType,
+    CollatorType>;
 
 struct Array {
     explicit Array(Type itemType_) : itemType(std::move(itemType_)) {}
diff --git a/include/mbgl/style/expression/value.hpp b/include/mbgl/style/expression/value.hpp
index 7839ff2ca7..fc38c36ff0 100644
--- a/include/mbgl/style/expression/value.hpp
+++ b/include/mbgl/style/expression/value.hpp
@@ -1,5 +1,6 @@
 #pragma once
 
+#include <mbgl/style/expression/collator.hpp>
 #include <mbgl/style/expression/type.hpp>
 #include <mbgl/style/position.hpp>
 #include <mbgl/style/types.hpp>
@@ -23,6 +24,7 @@ using ValueBase = variant<
     double,
     std::string,
     Color,
+    Collator,
     mapbox::util::recursive_wrapper<std::vector<Value>>,
     mapbox::util::recursive_wrapper<std::unordered_map<std::string, Value>>>;
 struct Value : ValueBase {
diff --git a/platform/darwin/src/collator.mm b/platform/darwin/src/collator.mm
new file mode 100644
index 0000000000..83c94c9ec3
--- /dev/null
+++ b/platform/darwin/src/collator.mm
@@ -0,0 +1,33 @@
+#include <mbgl/style/expression/collator.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+    
+Collator::Collator(bool , bool , const std::string& )
+    {}
+    
+Collator::Collator(bool , bool )
+    {}
+
+bool Collator::operator==(const Collator& ) const {
+    return true;
+}
+    
+int Collator::compare(const std::string&, const std::string&) const {
+    return 0;
+}
+    
+const std::string& Collator::resolvedLocale() const {
+    static std::string placeholder;
+    return placeholder;
+}
+mbgl::Value Collator::serialize() const {
+    return mbgl::Value(true);
+}
+    
+            
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/platform/ios/config.cmake b/platform/ios/config.cmake
index 1caf372b25..9378c4c25d 100644
--- a/platform/ios/config.cmake
+++ b/platform/ios/config.cmake
@@ -29,6 +29,7 @@ macro(mbgl_platform_core)
         PRIVATE platform/darwin/mbgl/storage/reachability.h
         PRIVATE platform/darwin/mbgl/storage/reachability.m
         PRIVATE platform/darwin/src/CFHandle.hpp
+        PRIVATE platform/darwin/src/collator.mm
         PRIVATE platform/darwin/src/local_glyph_rasterizer.mm
         PRIVATE platform/darwin/src/logging_nslog.mm
         PRIVATE platform/darwin/src/nsthread.mm
diff --git a/platform/macos/config.cmake b/platform/macos/config.cmake
index 57475f0c7c..81bc632cc6 100644
--- a/platform/macos/config.cmake
+++ b/platform/macos/config.cmake
@@ -14,6 +14,7 @@ macro(mbgl_platform_core)
         PRIVATE platform/darwin/mbgl/storage/reachability.h
         PRIVATE platform/darwin/mbgl/storage/reachability.m
         PRIVATE platform/darwin/src/CFHandle.hpp
+        PRIVATE platform/darwin/src/collator.mm
         PRIVATE platform/darwin/src/local_glyph_rasterizer.mm
         PRIVATE platform/darwin/src/logging_nslog.mm
         PRIVATE platform/darwin/src/nsthread.mm
diff --git a/src/mbgl/style/expression/collator_expression.cpp b/src/mbgl/style/expression/collator_expression.cpp
new file mode 100644
index 0000000000..9330d41a8c
--- /dev/null
+++ b/src/mbgl/style/expression/collator_expression.cpp
@@ -0,0 +1,124 @@
+#include <mbgl/style/expression/collator.hpp>
+#include <mbgl/style/expression/collator_expression.hpp>
+#include <mbgl/style/expression/literal.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+    
+CollatorExpression::CollatorExpression(std::unique_ptr<Expression> caseSensitive_,
+                   std::unique_ptr<Expression> diacriticSensitive_,
+                   std::unique_ptr<Expression> locale_)
+    : Expression(type::Collator)
+    , caseSensitive(std::move(caseSensitive_))
+    , diacriticSensitive(std::move(diacriticSensitive_))
+    , locale(std::move(locale_))
+{}
+
+using namespace mbgl::style::conversion;
+
+ParseResult CollatorExpression::parse(const Convertible& value, ParsingContext& ctx) {
+    if (arrayLength(value) != 2) {
+        ctx.error("Expected one argument.");
+        return ParseResult();
+    }
+
+    auto options = arrayMember(value, 1);
+    if (!isObject(options)) {
+        ctx.error("CollatorExpression options argument must be an object.");
+        return ParseResult();
+    }
+    
+    const optional<Convertible> caseSensitiveOption = objectMember(options, "case-sensitive");
+    ParseResult caseSensitive;
+    if (caseSensitiveOption) {
+        caseSensitive = ctx.parse(*caseSensitiveOption, 1, {type::Boolean});
+    } else {
+        caseSensitive = { std::make_unique<Literal>(false) };
+    }
+    if (!caseSensitive) {
+        return ParseResult();
+    }
+
+    const optional<Convertible> diacriticSensitiveOption = objectMember(options, "diacritic-sensitive");
+    ParseResult diacriticSensitive;
+    if (diacriticSensitiveOption) {
+        diacriticSensitive = ctx.parse(*diacriticSensitiveOption, 1, {type::Boolean});
+    } else {
+        diacriticSensitive = { std::make_unique<Literal>(false) };
+    }
+    if (!diacriticSensitive) {
+        return ParseResult();
+    }
+    
+    const optional<Convertible> localeOption = objectMember(options, "locale");
+    ParseResult locale;
+    if (localeOption) {
+        locale = ctx.parse(*localeOption, 1, {type::String});
+        if (!locale) {
+            return ParseResult();
+        }
+    }
+    
+    std::unique_ptr<Expression> localePtr;
+    if (locale) {
+        localePtr = std::move(*locale);
+    }
+    return ParseResult(std::make_unique<CollatorExpression>(std::move(*caseSensitive), std::move(*diacriticSensitive), std::move(localePtr)));
+}
+    
+void CollatorExpression::eachChild(const std::function<void(const Expression&)>& fn) const {
+    fn(*caseSensitive);
+    fn(*diacriticSensitive);
+    if (locale.get()) {
+        fn(*locale);
+    }
+}
+    
+bool CollatorExpression::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const CollatorExpression*>(&e)) {
+        if ((locale.get() && (!rhs->locale.get() || *locale != *(rhs->locale))) ||
+            (!locale.get() && rhs->locale.get())) {
+            return false;
+        }
+        return *caseSensitive == *(rhs->caseSensitive) &&
+            *diacriticSensitive == *(rhs->diacriticSensitive);
+    }
+    return false;
+}
+
+mbgl::Value CollatorExpression::serialize() const {
+    std::unordered_map<std::string, mbgl::Value> result;
+    result["case-sensitive"] = caseSensitive->serialize();
+    result["diacritic-sensitive"] = diacriticSensitive->serialize();
+    if (locale.get()) {
+        result["locale"] = locale->serialize();
+    }
+    return result;
+}
+    
+EvaluationResult CollatorExpression::evaluate(const EvaluationContext& params) const {
+    auto caseSensitiveResult = caseSensitive->evaluate(params);
+    if (!caseSensitiveResult) {
+        return caseSensitiveResult.error();
+    }
+    auto diacriticSensitiveResult = diacriticSensitive->evaluate(params);
+    if (!diacriticSensitiveResult) {
+        return diacriticSensitiveResult.error();
+    }
+    
+    if (locale.get()) {
+        auto localeResult = locale->evaluate(params);
+        if (!localeResult) {
+            return localeResult.error();
+        }
+        return Collator(caseSensitiveResult->get<bool>(), diacriticSensitiveResult->get<bool>(), localeResult->get<std::string>());
+    } else {
+        return Collator(caseSensitiveResult->get<bool>(), diacriticSensitiveResult->get<bool>());
+    }
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/compound_expression.cpp b/src/mbgl/style/expression/compound_expression.cpp
index a961de60ae..d0fef503a5 100644
--- a/src/mbgl/style/expression/compound_expression.cpp
+++ b/src/mbgl/style/expression/compound_expression.cpp
@@ -1,3 +1,4 @@
+#include <mbgl/style/expression/collator.hpp>
 #include <mbgl/style/expression/compound_expression.hpp>
 #include <mbgl/style/expression/check_subtype.hpp>
 #include <mbgl/style/expression/util.hpp>
@@ -481,12 +482,16 @@ std::unordered_map<std::string, CompoundExpressionRegistry::Definition> initiali
 
     define(">", [](double lhs, double rhs) -> Result<bool> { return lhs > rhs; });
     define(">", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs > rhs; });
+    define(">", [](const std::string& lhs, const std::string& rhs, const Collator& c) -> Result<bool> { return c.compare(lhs, rhs) > 0; });
     define(">=", [](double lhs, double rhs) -> Result<bool> { return lhs >= rhs; });
     define(">=",[](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs >= rhs; });
+    define(">=", [](const std::string& lhs, const std::string& rhs, const Collator& c) -> Result<bool> { return c.compare(lhs, rhs) >= 0; });
     define("<", [](double lhs, double rhs) -> Result<bool> { return lhs < rhs; });
     define("<", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs < rhs; });
+    define("<", [](const std::string& lhs, const std::string& rhs, const Collator& c) -> Result<bool> { return c.compare(lhs, rhs) < 0; });
     define("<=", [](double lhs, double rhs) -> Result<bool> { return lhs <= rhs; });
     define("<=", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs <= rhs; });
+    define("<=", [](const std::string& lhs, const std::string& rhs, const Collator& c) -> Result<bool> { return c.compare(lhs, rhs) <= 0; });
 
     define("!", [](bool e) -> Result<bool> { return !e; });
     
@@ -507,6 +512,10 @@ std::unordered_map<std::string, CompoundExpressionRegistry::Definition> initiali
         }
         return s;
     });
+    define("resolved-locale", [](const Collator& collator) -> Result<std::string> {
+        return collator.resolvedLocale();
+    });
+    
     define("error", [](const std::string& input) -> Result<type::ErrorType> {
         return EvaluationError { input };
     });
diff --git a/src/mbgl/style/expression/equals.cpp b/src/mbgl/style/expression/equals.cpp
index 6d963cc1d8..9a31338807 100644
--- a/src/mbgl/style/expression/equals.cpp
+++ b/src/mbgl/style/expression/equals.cpp
@@ -1,13 +1,15 @@
+#include <mbgl/style/expression/collator.hpp>
 #include <mbgl/style/expression/equals.hpp>
 
 namespace mbgl {
 namespace style {
 namespace expression {
 
-Equals::Equals(std::unique_ptr<Expression> lhs_, std::unique_ptr<Expression> rhs_, bool negate_)
+Equals::Equals(std::unique_ptr<Expression> lhs_, std::unique_ptr<Expression> rhs_, std::unique_ptr<Expression> collator_, bool negate_)
     : Expression(type::Boolean),
       lhs(std::move(lhs_)),
       rhs(std::move(rhs_)),
+      collator(std::move(collator_)),
       negate(negate_) {
 }
 
@@ -18,7 +20,15 @@ EvaluationResult Equals::evaluate(const EvaluationContext& params) const {
     EvaluationResult rhsResult = rhs->evaluate(params);
     if (!rhsResult) return lhsResult;
 
-    bool result = *lhsResult == *rhsResult;
+    bool result;
+    
+    if (collator.get()) {
+        auto collatorResult = collator->evaluate(params);
+        const Collator& c = collatorResult->get<Collator>();
+        result = c.compare(lhsResult->get<std::string>(), rhsResult->get<std::string>()) == 0;
+    } else {
+       result = *lhsResult == *rhsResult;
+    }
     if (negate) {
         result = !result;
     }
@@ -28,6 +38,9 @@ EvaluationResult Equals::evaluate(const EvaluationContext& params) const {
 void Equals::eachChild(const std::function<void(const Expression&)>& visit) const {
     visit(*lhs);
     visit(*rhs);
+    if (collator.get()) {
+        visit(*collator);
+    }
 }
 
 bool Equals::operator==(const Expression& e) const {
@@ -52,8 +65,8 @@ using namespace mbgl::style::conversion;
 ParseResult Equals::parse(const Convertible& value, ParsingContext& ctx) {
     std::size_t length = arrayLength(value);
 
-    if (length != 3) {
-        ctx.error("Expected two arguments.");
+    if (length != 3 && length != 4) {
+        ctx.error("Expected two or three arguments.");
         return ParseResult();
     }
 
@@ -78,8 +91,19 @@ ParseResult Equals::parse(const Convertible& value, ParsingContext& ctx) {
         ctx.error("Cannot compare " + toString(lhsType) + " and " + toString(rhsType) + ".");
         return ParseResult();
     }
+    
+    std::unique_ptr<Expression> collatorResult;
+    if (length == 4) {
+        if (lhsType != type::String && rhsType != type::String) {
+            ctx.error("Cannot use collator to compare non-string types.");
+            return ParseResult();
+        }
+        ParseResult collatorParseResult = ctx.parse(arrayMember(value, 3), 3, {type::Collator});
+        if (!collatorParseResult) return ParseResult();
+        collatorResult = std::move(*collatorParseResult);
+    }
 
-    return ParseResult(std::make_unique<Equals>(std::move(*lhs), std::move(*rhs), negate));
+    return ParseResult(std::make_unique<Equals>(std::move(*lhs), std::move(*rhs), std::move(collatorResult), negate));
 }
 
 } // namespace expression
diff --git a/src/mbgl/style/expression/parsing_context.cpp b/src/mbgl/style/expression/parsing_context.cpp
index b522aeff9a..fb6f377987 100644
--- a/src/mbgl/style/expression/parsing_context.cpp
+++ b/src/mbgl/style/expression/parsing_context.cpp
@@ -41,6 +41,13 @@ bool isConstant(const Expression& expression) {
             return false;
         }
     }
+    
+    if (dynamic_cast<const CollatorExpression*>(&expression)) {
+        // Although the results of a Collator expression with fixed arguments
+        // generally shouldn't change between executions, we can't serialize them
+        // as constant expressions because results change based on environment.
+        return false;
+    }
 
     bool isTypeAnnotation = dynamic_cast<const Coercion*>(&expression) ||
         dynamic_cast<const Assertion*>(&expression) ||
@@ -102,6 +109,7 @@ const ExpressionRegistry& getExpressionRegistry() {
         {"boolean", Assertion::parse},
         {"case", Case::parse},
         {"coalesce", Coalesce::parse},
+        {"collator", CollatorExpression::parse},
         {"interpolate", parseInterpolate},
         {"length", Length::parse},
         {"let", Let::parse},
diff --git a/src/mbgl/style/expression/value.cpp b/src/mbgl/style/expression/value.cpp
index 1b3257c755..746e1f0179 100644
--- a/src/mbgl/style/expression/value.cpp
+++ b/src/mbgl/style/expression/value.cpp
@@ -12,6 +12,7 @@ type::Type typeOf(const Value& value) {
         [&](double) -> type::Type { return type::Number; },
         [&](const std::string&) -> type::Type { return type::String; },
         [&](const Color&) -> type::Type { return type::Color; },
+        [&](const Collator&) -> type::Type { return type::Collator; },
         [&](const NullValue&) -> type::Type { return type::Null; },
         [&](const std::unordered_map<std::string, Value>&) -> type::Type { return type::Object; },
         [&](const std::vector<Value>& arr) -> type::Type {
@@ -43,6 +44,11 @@ void writeJSON(rapidjson::Writer<rapidjson::StringBuffer>& writer, const Value&
         },
         [&] (const std::string& s) { writer.String(s); },
         [&] (const Color& c) { writer.String(c.stringify()); },
+        [&] (const Collator&) {
+            // TODO: Collators are excluded from constant folding and there's no Literal parser
+            // for them so there shouldn't be any way to serialize this value.
+            // Is there a better way to omit this?
+        },
         [&] (const std::vector<Value>& arr) {
             writer.StartArray();
             for(const auto& item : arr) {
@@ -115,6 +121,9 @@ mbgl::Value ValueConverter<mbgl::Value>::fromExpressionValue(const Value& value)
                 array[3],
             };
         },
+        [&](const Collator& collator)->mbgl::Value {
+            return collator.serialize();
+        },
         [&](const std::vector<Value>& values)->mbgl::Value {
             std::vector<mbgl::Value> converted;
             converted.reserve(values.size());
@@ -261,6 +270,7 @@ template <> type::Type valueTypeToExpressionType<bool>() { return type::Boolean;
 template <> type::Type valueTypeToExpressionType<double>() { return type::Number; }
 template <> type::Type valueTypeToExpressionType<std::string>() { return type::String; }
 template <> type::Type valueTypeToExpressionType<Color>() { return type::Color; }
+template <> type::Type valueTypeToExpressionType<Collator>() { return type::Collator; }
 template <> type::Type valueTypeToExpressionType<std::unordered_map<std::string, Value>>() { return type::Object; }
 template <> type::Type valueTypeToExpressionType<std::vector<Value>>() { return type::Array(type::Value); }