[core] Introduce "collator" expressions

Cross platform parsing and evaluation code.

7 files changed, 199 insertions, 14 deletions

diff --git a/src/mbgl/style/expression/collator_expression.cpp b/src/mbgl/style/expression/collator_expression.cpp
new file mode 100644
index 0000000000..f5e4e3fdff
--- /dev/null
+++ b/src/mbgl/style/expression/collator_expression.cpp
@@ -0,0 +1,120 @@
+#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_,
+                   optional<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("Collator 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();
+        }
+    }
+    
+    return ParseResult(std::make_unique<CollatorExpression>(std::move(*caseSensitive), std::move(*diacriticSensitive), std::move(locale)));
+}
+    
+void CollatorExpression::eachChild(const std::function<void(const Expression&)>& fn) const {
+    fn(*caseSensitive);
+    fn(*diacriticSensitive);
+    if (locale) {
+        fn(**locale);
+    }
+}
+    
+bool CollatorExpression::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const CollatorExpression*>(&e)) {
+        if ((locale && (!rhs->locale || **locale != **(rhs->locale))) ||
+            (!locale && rhs->locale)) {
+            return false;
+        }
+        return *caseSensitive == *(rhs->caseSensitive) &&
+            *diacriticSensitive == *(rhs->diacriticSensitive);
+    }
+    return false;
+}
+
+mbgl::Value CollatorExpression::serialize() const {
+    std::unordered_map<std::string, mbgl::Value> options;
+    options["case-sensitive"] = caseSensitive->serialize();
+    options["diacritic-sensitive"] = diacriticSensitive->serialize();
+    if (locale) {
+        options["locale"] = (*locale)->serialize();
+    }
+    return std::vector<mbgl::Value>{{ std::string("collator"), options }};
+}
+    
+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) {
+        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 c37f02612b..46b0c7fe18 100644
--- a/src/mbgl/style/expression/compound_expression.cpp
+++ b/src/mbgl/style/expression/compound_expression.cpp
@@ -1,3 +1,5 @@
+#include <boost/algorithm/string/join.hpp>
+#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 +483,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 +513,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 };
     });
@@ -686,26 +696,35 @@ static ParseResult createCompoundExpression(const Definition& definition,
     if (definition.size() == 1) {
         ctx.appendErrors(std::move(signatureContext));
     } else {
-        std::string signatures;
+        std::vector<std::string> availableOverloads; // Only used if there are no overloads with matching number of args
+        std::vector<std::string> overloads;
         for (const auto& signature : definition) {
-            signatures += (signatures.size() > 0 ? " | " : "");
             signature->params.match(
                 [&](const VarargsType& varargs) {
-                    signatures += "(" + toString(varargs.type) + ")";
+                    std::string overload = "(" + toString(varargs.type) + ")";
+                    overloads.push_back(overload);
                 },
                 [&](const std::vector<type::Type>& params) {
-                    signatures += "(";
+                    std::string overload = "(";
                     bool first = true;
                     for (const type::Type& param : params) {
-                        if (!first) signatures += ", ";
-                        signatures += toString(param);
+                        if (!first) overload += ", ";
+                        overload += toString(param);
                         first = false;
                     }
-                    signatures += ")";
+                    overload += ")";
+                    if (params.size() == args.size()) {
+                        overloads.push_back(overload);
+                    } else {
+                        availableOverloads.push_back(overload);
+                    }
                 }
             );
 
         }
+        std::string signatures = overloads.empty() ?
+            boost::algorithm::join(availableOverloads, " | ") :
+            boost::algorithm::join(overloads, " | ");
         std::string actualTypes;
         for (const auto& arg : args) {
             if (actualTypes.size() > 0) {
diff --git a/src/mbgl/style/expression/dsl.cpp b/src/mbgl/style/expression/dsl.cpp
index 15822ccf66..2298bdf8d3 100644
--- a/src/mbgl/style/expression/dsl.cpp
+++ b/src/mbgl/style/expression/dsl.cpp
@@ -86,12 +86,12 @@ std::unique_ptr<Expression> zoom() {
 
 std::unique_ptr<Expression> eq(std::unique_ptr<Expression> lhs,
                                std::unique_ptr<Expression> rhs) {
-    return std::make_unique<Equals>(std::move(lhs), std::move(rhs), false);
+    return std::make_unique<Equals>(std::move(lhs), std::move(rhs), nullopt, false);
 }
 
 std::unique_ptr<Expression> ne(std::unique_ptr<Expression> lhs,
                                std::unique_ptr<Expression> rhs) {
-    return std::make_unique<Equals>(std::move(lhs), std::move(rhs), true);
+    return std::make_unique<Equals>(std::move(lhs), std::move(rhs), nullopt, true);
 }
 
 std::unique_ptr<Expression> gt(std::unique_ptr<Expression> lhs,
diff --git a/src/mbgl/style/expression/equals.cpp b/src/mbgl/style/expression/equals.cpp
index f2f59e31ef..245899f975 100644
--- a/src/mbgl/style/expression/equals.cpp
+++ b/src/mbgl/style/expression/equals.cpp
@@ -1,3 +1,4 @@
+#include <mbgl/style/expression/collator.hpp>
 #include <mbgl/style/expression/equals.hpp>
 
 namespace mbgl {
@@ -11,10 +12,11 @@ static bool isComparableType(const type::Type& type) {
         type == type::Null;
 }
 
-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_, optional<std::unique_ptr<Expression>> collator_, bool negate_)
     : Expression(type::Boolean),
       lhs(std::move(lhs_)),
       rhs(std::move(rhs_)),
+      collator(std::move(collator_)),
       negate(negate_) {
     assert(isComparableType(lhs->getType()) || isComparableType(rhs->getType()));
     assert(lhs->getType() == rhs->getType() || lhs->getType() == type::Value || rhs->getType() == type::Value);
@@ -27,7 +29,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) {
+        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;
     }
@@ -37,6 +47,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) {
+        visit(**collator);
+    }
 }
 
 bool Equals::operator==(const Expression& e) const {
@@ -54,8 +67,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();
     }
 
@@ -80,8 +93,18 @@ ParseResult Equals::parse(const Convertible& value, ParsingContext& ctx) {
         ctx.error("Cannot compare " + toString(lhsType) + " and " + toString(rhsType) + ".");
         return ParseResult();
     }
+    
+    ParseResult collatorParseResult;
+    if (length == 4) {
+        if (lhsType != type::String && rhsType != type::String) {
+            ctx.error("Cannot use collator to compare non-string types.");
+            return ParseResult();
+        }
+        collatorParseResult = ctx.parse(arrayMember(value, 3), 3, {type::Collator});
+        if (!collatorParseResult) return ParseResult();
+    }
 
-    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(collatorParseResult), negate));
 }
 
 } // namespace expression
diff --git a/src/mbgl/style/expression/is_constant.cpp b/src/mbgl/style/expression/is_constant.cpp
index 577ecf8cb6..b877ed550a 100644
--- a/src/mbgl/style/expression/is_constant.cpp
+++ b/src/mbgl/style/expression/is_constant.cpp
@@ -1,4 +1,6 @@
 #include <mbgl/style/expression/is_constant.hpp>
+#include <mbgl/style/expression/collator_expression.hpp>
+
 
 namespace mbgl {
 namespace style {
@@ -25,6 +27,13 @@ bool isFeatureConstant(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 featureConstant = true;
     expression.eachChild([&](const Expression& e) {
diff --git a/src/mbgl/style/expression/parsing_context.cpp b/src/mbgl/style/expression/parsing_context.cpp
index 72585c35df..fe3102f158 100644
--- a/src/mbgl/style/expression/parsing_context.cpp
+++ b/src/mbgl/style/expression/parsing_context.cpp
@@ -102,6 +102,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 7c329e8f1f..b1b05ea617 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&) {
+            // 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.
+            assert(false);
+        },
         [&] (const std::vector<Value>& arr) {
             writer.StartArray();
             for(const auto& item : arr) {
@@ -115,6 +121,12 @@ mbgl::Value ValueConverter<mbgl::Value>::fromExpressionValue(const Value& value)
                 array[3],
             };
         },
+        [&](const Collator&)->mbgl::Value {
+            // fromExpressionValue can't be used for Collator values,
+            // because they have no meaningful representation as an mbgl::Value
+            assert(false);
+            return mbgl::Value();
+        },
         [&](const std::vector<Value>& values)->mbgl::Value {
             std::vector<mbgl::Value> converted;
             converted.reserve(values.size());
@@ -261,6 +273,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); }