[core] Implement Expression::serialize()

Issue #10714
- Each expression stores its operator as a string, and default serialization is [operator, serialize(child1), ...]
- Custom implementations of `serialize` for Expression types that don't follow the pattern
- expression::Value -> mbgl::Value converter
- node_expression bindings to expose `serialize`

10 files changed, 177 insertions, 23 deletions

diff --git a/src/mbgl/style/expression/array_assertion.cpp b/src/mbgl/style/expression/array_assertion.cpp
index 29f6a47b10..4049301b0b 100644
--- a/src/mbgl/style/expression/array_assertion.cpp
+++ b/src/mbgl/style/expression/array_assertion.cpp
@@ -81,6 +81,25 @@ ParseResult ArrayAssertion::parse(const Convertible& value, ParsingContext& ctx)
     ));
 }
 
+mbgl::Value ArrayAssertion::serialize() const {
+    std::vector<mbgl::Value> serialized;
+    serialized.emplace_back(getOperator());
+    
+    
+    const auto array = getType().get<type::Array>();
+    if (array.itemType.is<type::StringType>()
+     || array.itemType.is<type::NumberType>()
+     || array.itemType.is<type::BooleanType>()) {
+        serialized.emplace_back(type::toString(array.itemType));
+        if (array.N) {
+            serialized.emplace_back(uint64_t(*array.N));
+        }
+    }
+    
+    serialized.emplace_back(input->serialize());
+    return serialized;
+}
+
 } // namespace expression
 } // namespace style
 } // namespace mbgl
diff --git a/src/mbgl/style/expression/assertion.cpp b/src/mbgl/style/expression/assertion.cpp
index 0187921af9..d6f3f1b584 100644
--- a/src/mbgl/style/expression/assertion.cpp
+++ b/src/mbgl/style/expression/assertion.cpp
@@ -35,6 +35,10 @@ ParseResult Assertion::parse(const Convertible& value, ParsingContext& ctx) {
     return ParseResult(std::make_unique<Assertion>(it->second, std::move(parsed)));
 }
 
+std::string Assertion::getOperator() const {
+    return type::toString(getType());
+}
+
 EvaluationResult Assertion::evaluate(const EvaluationContext& params) const {
     for (std::size_t i = 0; i < inputs.size(); i++) {
         EvaluationResult value = inputs[i]->evaluate(params);
diff --git a/src/mbgl/style/expression/coercion.cpp b/src/mbgl/style/expression/coercion.cpp
index 56ab33fcfd..d9cd3ffdc9 100644
--- a/src/mbgl/style/expression/coercion.cpp
+++ b/src/mbgl/style/expression/coercion.cpp
@@ -81,6 +81,13 @@ Coercion::Coercion(type::Type type_, std::vector<std::unique_ptr<Expression>> in
     }
 }
 
+std::string Coercion::getOperator() const {
+    return getType().match(
+      [](const type::NumberType&) { return "to-number"; },
+      [](const type::ColorType&) { return "to-color"; },
+      [](const auto&) { assert(false); return ""; });
+}
+
 using namespace mbgl::style::conversion;
 ParseResult Coercion::parse(const Convertible& value, ParsingContext& ctx) {
     static std::unordered_map<std::string, type::Type> types {
diff --git a/src/mbgl/style/expression/compound_expression.cpp b/src/mbgl/style/expression/compound_expression.cpp
index 42cb655024..86d968c521 100644
--- a/src/mbgl/style/expression/compound_expression.cpp
+++ b/src/mbgl/style/expression/compound_expression.cpp
@@ -42,20 +42,19 @@ template <class R, class... Params>
 struct Signature<R (Params...)> : SignatureBase {
     using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
     
-    Signature(R (*evaluate_)(Params...)) :
+    Signature(R (*evaluate_)(Params...), std::string name_) :
         SignatureBase(
             valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
-            std::vector<type::Type> {valueTypeToExpressionType<std::decay_t<Params>>()...}
+            std::vector<type::Type> {valueTypeToExpressionType<std::decay_t<Params>>()...},
+            std::move(name_)
         ),
-        evaluate(evaluate_)
-    {}
+        evaluate(evaluate_)    {}
     
     EvaluationResult apply(const EvaluationContext& evaluationParameters, const Args& args) const {
         return applyImpl(evaluationParameters, args, std::index_sequence_for<Params...>{});
     }
     
-    std::unique_ptr<Expression> makeExpression(const std::string& name,
-                                               std::vector<std::unique_ptr<Expression>> args) const override {
+    std::unique_ptr<Expression> makeExpression(std::vector<std::unique_ptr<Expression>> args) const override {
         typename Signature::Args argsArray;
         std::copy_n(std::make_move_iterator(args.begin()), sizeof...(Params), argsArray.begin());
         return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(argsArray));
@@ -80,16 +79,16 @@ template <class R, typename T>
 struct Signature<R (const Varargs<T>&)> : SignatureBase {
     using Args = std::vector<std::unique_ptr<Expression>>;
     
-    Signature(R (*evaluate_)(const Varargs<T>&)) :
+    Signature(R (*evaluate_)(const Varargs<T>&), std::string name_) :
         SignatureBase(
             valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
-            VarargsType { valueTypeToExpressionType<T>() }
+            VarargsType { valueTypeToExpressionType<T>() },
+            std::move(name_)
         ),
         evaluate(evaluate_)
     {}
     
-    std::unique_ptr<Expression> makeExpression(const std::string& name,
-                                               std::vector<std::unique_ptr<Expression>> args) const override  {
+    std::unique_ptr<Expression> makeExpression(std::vector<std::unique_ptr<Expression>> args) const override  {
         return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(args));
     };
     
@@ -115,16 +114,16 @@ template <class R, class... Params>
 struct Signature<R (const EvaluationContext&, Params...)> : SignatureBase {
     using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
     
-    Signature(R (*evaluate_)(const EvaluationContext&, Params...)) :
+    Signature(R (*evaluate_)(const EvaluationContext&, Params...), std::string name_) :
         SignatureBase(
             valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
-            std::vector<type::Type> {valueTypeToExpressionType<std::decay_t<Params>>()...}
+            std::vector<type::Type> {valueTypeToExpressionType<std::decay_t<Params>>()...},
+            std::move(name_)
         ),
         evaluate(evaluate_)
     {}
     
-    std::unique_ptr<Expression> makeExpression(const std::string& name,
-                                               std::vector<std::unique_ptr<Expression>> args) const override {
+    std::unique_ptr<Expression> makeExpression(std::vector<std::unique_ptr<Expression>> args) const override {
         typename Signature::Args argsArray;
         std::copy_n(std::make_move_iterator(args.begin()), sizeof...(Params), argsArray.begin());
         return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(argsArray));
@@ -176,14 +175,14 @@ struct Signature<Lambda, std::enable_if_t<std::is_class<Lambda>::value>>
 using Definition = CompoundExpressionRegistry::Definition;
 
 template <typename Fn>
-static std::unique_ptr<detail::SignatureBase> makeSignature(Fn evaluateFunction) {
-    return std::make_unique<detail::Signature<Fn>>(evaluateFunction);
+static std::unique_ptr<detail::SignatureBase> makeSignature(Fn evaluateFunction, std::string name) {
+    return std::make_unique<detail::Signature<Fn>>(evaluateFunction, std::move(name));
 }
 
 std::unordered_map<std::string, CompoundExpressionRegistry::Definition> initializeDefinitions() {
     std::unordered_map<std::string, CompoundExpressionRegistry::Definition> definitions;
     auto define = [&](std::string name, auto fn) {
-        definitions[name].push_back(makeSignature(fn));
+        definitions[name].push_back(makeSignature(fn, name));
     };
     
     define("e", []() -> Result<double> { return 2.718281828459045; });
@@ -461,7 +460,7 @@ ParseResult parseCompoundExpression(const std::string name, const Convertible& v
         }
         args.push_back(std::move(*parsed));
     }
-    return createCompoundExpression(name, definition, std::move(args), ctx);
+    return createCompoundExpression(definition, std::move(args), ctx);
 }
 
 
@@ -469,12 +468,11 @@ ParseResult createCompoundExpression(const std::string& name,
                                      std::vector<std::unique_ptr<Expression>> args,
                                      ParsingContext& ctx)
 {
-    return createCompoundExpression(name, CompoundExpressionRegistry::definitions.at(name), std::move(args), ctx);
+    return createCompoundExpression(CompoundExpressionRegistry::definitions.at(name), std::move(args), ctx);
 }
 
 
-ParseResult createCompoundExpression(const std::string& name,
-                                     const Definition& definition,
+ParseResult createCompoundExpression(const Definition& definition,
                                      std::vector<std::unique_ptr<Expression>> args,
                                      ParsingContext& ctx)
 {
@@ -512,7 +510,7 @@ ParseResult createCompoundExpression(const std::string& name,
         }
         
         if (signatureContext.getErrors().size() == 0) {
-            return ParseResult(signature->makeExpression(name, std::move(args)));
+            return ParseResult(signature->makeExpression(std::move(args)));
         }
     }
     
diff --git a/src/mbgl/style/expression/interpolate.cpp b/src/mbgl/style/expression/interpolate.cpp
index 4cb22a3e4f..30b2cba81b 100644
--- a/src/mbgl/style/expression/interpolate.cpp
+++ b/src/mbgl/style/expression/interpolate.cpp
@@ -216,6 +216,30 @@ std::vector<optional<Value>> InterpolateBase::possibleOutputs() const {
     return result;
 }
 
+template <typename T>
+mbgl::Value Interpolate<T>::serialize() const {
+    std::vector<mbgl::Value> serialized;
+    serialized.emplace_back(getOperator());
+    
+    interpolator.match(
+        [&](const ExponentialInterpolator& exponential) {
+            serialized.emplace_back(std::vector<mbgl::Value>{{ std::string("exponential"), exponential.base }});
+        },
+        [&](const CubicBezierInterpolator& cubicBezier) {
+            static const std::string cubicBezierTag("cubic-bezier");
+            auto p1 = cubicBezier.ub.getP1();
+            auto p2 = cubicBezier.ub.getP2();
+            serialized.emplace_back(std::vector<mbgl::Value>{{ cubicBezierTag, p1.first, p1.second, p2.first, p2.second }});
+        }
+    );
+    serialized.emplace_back(input->serialize());
+    for (auto& entry : stops) {
+        serialized.emplace_back(entry.first);
+        serialized.emplace_back(entry.second->serialize());
+    };
+    return serialized;
+}
+
 } // namespace expression
 } // namespace style
 } // namespace mbgl
diff --git a/src/mbgl/style/expression/let.cpp b/src/mbgl/style/expression/let.cpp
index fe48138ac3..242a995b0b 100644
--- a/src/mbgl/style/expression/let.cpp
+++ b/src/mbgl/style/expression/let.cpp
@@ -65,6 +65,17 @@ ParseResult Let::parse(const Convertible& value, ParsingContext& ctx) {
     return ParseResult(std::make_unique<Let>(std::move(bindings_), std::move(*result_)));
 }
 
+mbgl::Value Let::serialize() const {
+    std::vector<mbgl::Value> serialized;
+    serialized.emplace_back(getOperator());
+    for (auto entry : bindings) {
+        serialized.emplace_back(entry.first);
+        serialized.emplace_back(entry.second->serialize());
+    }
+    serialized.emplace_back(result->serialize());
+    return serialized;
+}
+
 EvaluationResult Var::evaluate(const EvaluationContext& params) const {
     return value->evaluate(params);
 }
@@ -95,6 +106,10 @@ ParseResult Var::parse(const Convertible& value_, ParsingContext& ctx) {
     return ParseResult(std::make_unique<Var>(name_, std::move(*bindingValue)));
 }
 
+mbgl::Value Var::serialize() const {
+    return std::vector<mbgl::Value>{{ getOperator(), name }};
+}
+
 } // namespace expression
 } // namespace style
 } // namespace mbgl
diff --git a/src/mbgl/style/expression/literal.cpp b/src/mbgl/style/expression/literal.cpp
index 7e79fcbfe6..8a63980dba 100644
--- a/src/mbgl/style/expression/literal.cpp
+++ b/src/mbgl/style/expression/literal.cpp
@@ -102,6 +102,14 @@ ParseResult Literal::parse(const Convertible& value, ParsingContext& ctx) {
     }
 }
 
+mbgl::Value Literal::serialize() const {
+    if (getType().is<type::Array>() || getType().is<type::ObjectType>()) {
+        return std::vector<mbgl::Value>{{ getOperator(), *fromExpressionValue<mbgl::Value>(value) }};
+    } else {
+        return *fromExpressionValue<mbgl::Value>(value);
+    }
+}
+
 } // namespace expression
 } // namespace style
 } // namespace mbgl
diff --git a/src/mbgl/style/expression/match.cpp b/src/mbgl/style/expression/match.cpp
index 0b2790b688..3d41f0bdd3 100644
--- a/src/mbgl/style/expression/match.cpp
+++ b/src/mbgl/style/expression/match.cpp
@@ -40,6 +40,42 @@ std::vector<optional<Value>> Match<T>::possibleOutputs() const {
     return result;
 }
 
+template <typename T>
+mbgl::Value Match<T>::serialize() const {
+    std::vector<mbgl::Value> serialized;
+    serialized.emplace_back(getOperator());
+    serialized.emplace_back(input->serialize());
+    
+    // Sort so serialization has an arbitrary defined order, even though branch order doesn't affect evaluation
+    std::map<T, std::shared_ptr<Expression>> sortedBranches(branches.begin(), branches.end());
+
+    // Group branches by unique match expression to support condensed serializations
+    // of the form [case1, case2, ...] -> matchExpression
+    std::map<Expression*, size_t> outputLookup;
+    std::vector<std::pair<Expression*, std::vector<mbgl::Value>>> groupedByOutput;
+    for (auto& entry : sortedBranches) {
+        auto outputIndex = outputLookup.find(entry.second.get());
+        if (outputIndex == outputLookup.end()) {
+            // First time seeing this output, add it to the end of the grouped list
+            outputLookup[entry.second.get()] = groupedByOutput.size();
+            groupedByOutput.emplace_back(entry.second.get(), std::vector<mbgl::Value>{{entry.first}});
+        } else {
+            // We've seen this expression before, add the label to that output's group
+            groupedByOutput[outputIndex->second].second.emplace_back(entry.first);
+        }
+    };
+    
+    for (auto& entry : groupedByOutput) {
+        entry.second.size() == 1
+            ? serialized.emplace_back(entry.second[0])       // Only a single label matches this output expression
+            : serialized.emplace_back(entry.second);         // Array of literal labels pointing to this output expression
+        serialized.emplace_back(entry.first->serialize());   // The output expression itself
+    }
+    
+    serialized.emplace_back(otherwise->serialize());
+    return serialized;
+}
+    
 
 template<> EvaluationResult Match<std::string>::evaluate(const EvaluationContext& params) const {
     const EvaluationResult inputValue = input->evaluate(params);
diff --git a/src/mbgl/style/expression/step.cpp b/src/mbgl/style/expression/step.cpp
index 34537d48ae..ddaf9417cb 100644
--- a/src/mbgl/style/expression/step.cpp
+++ b/src/mbgl/style/expression/step.cpp
@@ -168,6 +168,18 @@ ParseResult Step::parse(const mbgl::style::conversion::Convertible& value, Parsi
     return ParseResult(std::make_unique<Step>(*outputType, std::move(*input), std::move(stops)));
 }
 
+mbgl::Value Step::serialize() const {
+    std::vector<mbgl::Value> serialized;
+    serialized.emplace_back(getOperator());
+    serialized.emplace_back(input->serialize());
+    for (auto& entry : stops) {
+        if (entry.first > -std::numeric_limits<double>::infinity()) {
+            serialized.emplace_back(entry.first);
+        }
+        serialized.emplace_back(entry.second->serialize());
+    }
+    return serialized;
+}
 
 } // namespace expression
 } // namespace style
diff --git a/src/mbgl/style/expression/value.cpp b/src/mbgl/style/expression/value.cpp
index faa44e78aa..72779d4956 100644
--- a/src/mbgl/style/expression/value.cpp
+++ b/src/mbgl/style/expression/value.cpp
@@ -103,6 +103,37 @@ Value ValueConverter<mbgl::Value>::toExpressionValue(const mbgl::Value& value) {
     return mbgl::Value::visit(value, FromMBGLValue());
 }
 
+mbgl::Value ValueConverter<mbgl::Value>::fromExpressionValue(const Value& value) {
+    return value.match(
+        [&](const Color& color)->mbgl::Value {
+            return std::vector<mbgl::Value>{
+                std::string("rgba"),
+                double(255 * color.r / color.a),
+                double(255 * color.g / color.a),
+                double(255 * color.b / color.a),
+                double(color.a)
+            };
+        },
+        [&](const std::vector<Value>& values)->mbgl::Value {
+            std::vector<mbgl::Value> converted;
+            converted.reserve(values.size());
+            for (const Value& v : values) {
+                converted.emplace_back(fromExpressionValue(v));
+            }
+            return converted;
+        },
+        [&](const std::unordered_map<std::string, Value>& values)->mbgl::Value {
+            std::unordered_map<std::string, mbgl::Value> converted;
+            converted.reserve(values.size());
+            for(const auto& entry : values) {
+                converted.emplace(entry.first, fromExpressionValue(entry.second));
+            }
+            return converted;
+        },
+        [&](const auto& a)->mbgl::Value { return a; }
+    );
+}
+
 Value ValueConverter<float>::toExpressionValue(const float value) {
     return static_cast<double>(value);
 }
@@ -237,7 +268,7 @@ template <> type::Type valueTypeToExpressionType<type::ErrorType>() { return typ
 
 
 template Value toExpressionValue(const mbgl::Value&);
-
+template optional<mbgl::Value> fromExpressionValue<mbgl::Value>(const Value&);
 
 // for to_rgba expression
 template type::Type valueTypeToExpressionType<std::array<double, 4>>();