Implement special forms: match, curve, coalesce

Port 'match'

Implement curve

Implement coalesce

8 files changed, 758 insertions, 4 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index a86900f06b..24d7fb7013 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -390,8 +390,13 @@ set(MBGL_CORE_FILES
     src/mbgl/style/conversion/stringify.hpp
 
     # style/expression
+    include/mbgl/style/expression/case.hpp
+    include/mbgl/style/expression/coalesce.hpp
     include/mbgl/style/expression/compound_expression.hpp
+    include/mbgl/style/expression/curve.hpp
     include/mbgl/style/expression/expression.hpp
+    include/mbgl/style/expression/let.hpp
+    include/mbgl/style/expression/match.hpp
     include/mbgl/style/expression/parse.hpp
     include/mbgl/style/expression/parsing_context.hpp
     include/mbgl/style/expression/type.hpp
diff --git a/include/mbgl/style/expression/case.hpp b/include/mbgl/style/expression/case.hpp
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/include/mbgl/style/expression/case.hpp
diff --git a/include/mbgl/style/expression/coalesce.hpp b/include/mbgl/style/expression/coalesce.hpp
new file mode 100644
index 0000000000..5c7cc0c7c1
--- /dev/null
+++ b/include/mbgl/style/expression/coalesce.hpp
@@ -0,0 +1,116 @@
+#pragma once
+
+#include <map>
+#include <mbgl/util/interpolate.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class TypedCoalesce : public TypedExpression {
+public:
+    using Args = std::vector<std::unique_ptr<TypedExpression>>;
+    TypedCoalesce(const type::Type& type, Args args_) :
+        TypedExpression(type),
+        args(std::move(args_))
+    {}
+    
+    EvaluationResult evaluate(const EvaluationParameters& params) const override {
+        for (auto it = args.begin(); it != args.end(); it++) {
+            const auto& result = (*it)->evaluate(params);
+            if (!result && (std::next(it) != args.end())) {
+                continue;
+            }
+            return result;
+        }
+        
+        return Null;
+    }
+    
+    bool isFeatureConstant() const override {
+        for (const auto& arg : args) {
+            if (!arg->isFeatureConstant()) return false;
+        }
+        return true;
+    }
+
+    bool isZoomConstant() const override {
+        for (const auto& arg : args) {
+            if (!arg->isZoomConstant()) return false;
+        }
+        return true;
+    }
+    
+private:
+    Args args;
+};
+
+class UntypedCoalesce : public UntypedExpression {
+public:
+    using Args = std::vector<std::unique_ptr<UntypedExpression>>;
+    
+    UntypedCoalesce(const std::string& key, Args args_) :
+        UntypedExpression(key),
+        args(std::move(args_))
+    {}
+    
+    template <typename V>
+    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+        using namespace mbgl::style::conversion;
+        assert(isArray(value));
+        auto length = arrayLength(value);
+        if (length < 2) {
+            return CompileError {
+                "Expected at least one argument to \"coalesce\".",
+                ctx.key()
+            };
+        }
+        
+        Args args;
+        for (std::size_t i = 1; i < length; i++) {
+            auto parsed = parseExpression(arrayMember(value, i), ParsingContext(ctx, {i}, {"coalesce"}));
+            if (parsed.template is<CompileError>()) {
+                return parsed;
+            }
+            args.push_back(std::move(parsed.template get<std::unique_ptr<UntypedExpression>>()));
+        }
+        return std::make_unique<UntypedCoalesce>(ctx.key(), std::move(args));
+    }
+    
+    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
+        optional<type::Type> outputType;
+        TypedCoalesce::Args checkedArgs;
+        
+        for (const auto& arg : args) {
+            auto checked = arg->typecheck(errors);
+            if (!checked) {
+                continue;
+            }
+            if (!outputType) {
+                outputType = (*checked)->getType();
+            } else {
+                const auto& error = matchType(*outputType, (*checked)->getType());
+                if (error) {
+                    errors.push_back({ *error, arg->getKey() });
+                    continue;
+                }
+            }
+            
+            checkedArgs.push_back(std::move(*checked));
+        }
+        
+        if (errors.size() > 0) return TypecheckResult();
+        
+        return TypecheckResult(std::make_unique<TypedCoalesce>(*outputType, std::move(checkedArgs)));
+    }
+
+private:
+    Args args;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/curve.hpp b/include/mbgl/style/expression/curve.hpp
new file mode 100644
index 0000000000..00ea15eb46
--- /dev/null
+++ b/include/mbgl/style/expression/curve.hpp
@@ -0,0 +1,339 @@
+#pragma once
+
+#include <map>
+#include <mbgl/util/interpolate.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+
+namespace util {
+
+struct InterpolateExpressionValue {
+    const double t;
+    
+    template <typename T, typename Enabled = void>
+    optional<Value> operator()(const T&, const T&) const {
+        return optional<Value>();
+    };
+    
+    template <typename T, typename std::enable_if_t<Interpolatable<T>::value>>
+    optional<Value> operator()(const T& a, const T& b) const {
+        return util::interpolate(a, b, t);
+    }
+    
+    template <typename T, typename U>
+    optional<Value> operator()(const T&, const U&) const {
+        return {};
+    }
+};
+
+template<>
+struct Interpolator<std::vector<Value>> {
+    std::vector<Value> operator()(const std::vector<Value>& a, const std::vector<Value>& b, const double t) const {
+        assert(a.size() == b.size());
+        if (a.size() == 0) return {};
+        std::vector<Value> result;
+        InterpolateExpressionValue visitor {t};
+        for (std::size_t i = 0; i < a.size(); i++) {
+            const auto& v = Value::binary_visit(a[i], b[i], visitor);
+            assert(v);
+            result.push_back(*v);
+        }
+        return result;
+    }
+};
+
+} // namespace util
+
+namespace style {
+namespace expression {
+
+template <class T = void>
+class ExponentialCurve {
+public:
+    using Stops = std::map<float, std::unique_ptr<TypedExpression>>;
+
+    ExponentialCurve(Stops stops_, float base_)
+        : stops(std::move(stops_)),
+          base(base_)
+    {}
+
+    Stops stops;
+    float base;
+
+    EvaluationResult evaluate(float x, const EvaluationParameters& parameters) const {
+        if (stops.empty()) {
+            return EvaluationError { "No stops in exponential curve." };
+        }
+
+        auto it = stops.upper_bound(x);
+        if (it == stops.end()) {
+            return stops.rbegin()->second->evaluate(parameters);
+        } else if (it == stops.begin()) {
+            return stops.begin()->second->evaluate(parameters);
+        } else {
+            const auto& lower = std::prev(it)->second->template evaluate<T>(parameters);
+            if (!lower) { return lower.error(); }
+            const auto& upper = it->second->template evaluate<T>(parameters);
+            if (!upper) { return upper.error(); }
+            return util::interpolate(*lower, *upper,
+                util::interpolationFactor(base, { std::prev(it)->first, it->first }, x));
+        }
+    }
+};
+
+class StepCurve {
+public:
+    using Stops = std::map<float, std::unique_ptr<TypedExpression>>;
+    StepCurve(Stops stops_) : stops(std::move(stops_)) {}
+    
+    Stops stops;
+
+    EvaluationResult evaluate(float x, const EvaluationParameters& parameters) const {
+        if (stops.empty()) {
+            return EvaluationError { "No stops in exponential curve." };
+        }
+        
+        auto it = stops.upper_bound(x);
+        if (it == stops.end()) {
+            return stops.rbegin()->second->evaluate(parameters);
+        } else if (it == stops.begin()) {
+            return stops.begin()->second->evaluate(parameters);
+        } else {
+            return std::prev(it)->second->evaluate(parameters);
+        }
+    }
+};
+
+template <typename Curve>
+class TypedCurve : public TypedExpression {
+public:
+    TypedCurve(const type::Type& type, std::unique_ptr<TypedExpression> input_, Curve curve_) :
+        TypedExpression(type),
+        input(std::move(input_)),
+        curve(std::move(curve_))
+    {}
+    
+    EvaluationResult evaluate(const EvaluationParameters& params) const override {
+        const auto& x = input->evaluate<float>(params);
+        if (!x) { return x.error(); }
+        return curve.evaluate(*x, params);
+    }
+    
+    bool isFeatureConstant() const override {
+        if (!input->isFeatureConstant()) { return false; }
+        for (const auto& stop : curve.stops) {
+            if (!stop.second->isFeatureConstant()) { return false; }
+        }
+        return true;
+    }
+
+    bool isZoomConstant() const override {
+        if (!input->isZoomConstant()) { return false; }
+        for (const auto& stop : curve.stops) {
+            if (!stop.second->isZoomConstant()) { return false; }
+        }
+        return true;
+    }
+    
+private:
+    std::unique_ptr<TypedExpression> input;
+    Curve curve;
+};
+
+struct ExponentialInterpolation { float base; std::string name = "exponential"; };
+struct StepInterpolation {};
+
+class UntypedCurve : public UntypedExpression {
+public:
+    using Stops = std::vector<std::pair<float, std::unique_ptr<UntypedExpression>>>;
+    using Interpolation = variant<
+        StepInterpolation,
+        ExponentialInterpolation>;
+    UntypedCurve(const std::string& key,
+                 std::unique_ptr<UntypedExpression> input_,
+                 Stops stops_,
+                 Interpolation interpolation_
+    ) : UntypedExpression(key),
+        input(std::move(input_)),
+        stops(std::move(stops_)),
+        interpolation(interpolation_)
+    {}
+    
+    template <typename V>
+    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+        using namespace mbgl::style::conversion;
+        assert(isArray(value));
+        auto length = arrayLength(value);
+        if (length < 4) {
+            return CompileError {
+                "Expected at least 3 arguments, but found only " + std::to_string(length - 1) + ".",
+                ctx.key()
+            };
+        }
+        
+        // [curve, interp, input, 2 * (n pairs)...]
+        if (length % 2 != 1) {
+            return CompileError {
+                "Missing final output value for \"curve\" expression.",
+                ctx.key()
+            };
+        }
+        
+        const auto& interp = arrayMember(value, 1);
+        if (!isArray(interp) || arrayLength(interp) == 0) {
+            return CompileError {
+                "Expected an interpolation type expression, e.g. [\"linear\"].",
+                ctx.key(1)
+            };
+        }
+        
+        Interpolation interpolation;
+        const auto& interpName = toString(arrayMember(interp, 0));
+        if (interpName && *interpName == "step") {
+            interpolation = StepInterpolation {};
+        } else if (interpName && *interpName == "linear") {
+            interpolation = ExponentialInterpolation { 1.0f, "linear" };
+        } else if (interpName && *interpName == "exponential") {
+            optional<double> base;
+            if (arrayLength(interp) == 2) {
+                base = toDouble(arrayMember(interp, 1));
+            }
+            if (!base) {
+                return CompileError {
+                    "Exponential interpolation requires a numeric base",
+                    ctx.key(1)
+                };
+            }
+            interpolation = ExponentialInterpolation { static_cast<float>(*base) };
+        } else {
+            std::string name = interpName ? *interpName : "";
+            return CompileError {
+                "Unknown interpolation type " + name,
+                ctx.key(1)
+            };
+        }
+        
+        auto input = parseExpression(arrayMember(value, 2), ParsingContext(ctx, {2}, {"curve"}));
+        if (input.template is<CompileError>()) {
+            return input;
+        }
+        
+        Stops stops;
+        double previous = - std::numeric_limits<double>::infinity();
+        for (std::size_t i = 3; i + 1 < length; i += 2) {
+            const auto& inputValue = toDouble(arrayMember(value, i));
+            if (!inputValue) {
+                return CompileError {
+                    "Input/output pairs for \"curve\" expressions must be defined using literal numeric values (not computed expressions) for the input values.",
+                    ctx.key(i)
+                };
+            }
+            if (*inputValue < previous) {
+                return CompileError {
+                    "Input/output pairs for \"curve\" expressions must be arranged with input values in strictly ascending order.",
+                    ctx.key(i)
+                };
+            }
+            previous = *inputValue;
+            
+            auto output = parseExpression(arrayMember(value, i + 1), ParsingContext(ctx, {i + 1}, {"curve"}));
+            if (output.template is<CompileError>()) {
+                return output;
+            }
+            stops.push_back(std::make_pair(
+                *inputValue,
+                std::move(output.template get<std::unique_ptr<UntypedExpression>>())
+            ));
+        }
+        
+        return std::make_unique<UntypedCurve>(ctx.key(),
+                                              std::move(input.template get<std::unique_ptr<UntypedExpression>>()),
+                                              std::move(stops),
+                                              interpolation);
+    }
+    
+    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
+        auto checkedInput = input->typecheck(errors);
+        if (!checkedInput) {
+            return TypecheckResult();
+        }
+        auto error = matchType(type::Number, (*checkedInput)->getType());
+        if (error) {
+            errors.push_back({*error, input->getKey()});
+        }
+        
+        optional<type::Type> outputType;
+        std::map<float, std::unique_ptr<TypedExpression>> checkedStops;
+        for (const auto& stop : stops) {
+            auto checkedOutput = stop.second->typecheck(errors);
+            if (!checkedOutput) {
+                continue;
+            }
+            if (!outputType) {
+                outputType = (*checkedOutput)->getType();
+            } else {
+                error = matchType(*outputType, (*checkedOutput)->getType());
+                if (error) {
+                    errors.push_back({ *error, stop.second->getKey() });
+                    continue;
+                }
+            }
+            checkedStops.emplace(stop.first, std::move(*checkedOutput));
+        }
+        
+        if (stops.size() > 0) return TypecheckResult();
+        
+        return interpolation.match(
+            [&](const StepInterpolation&) -> TypecheckResult {
+                return {std::make_unique<TypedCurve<StepCurve>>(
+                        *outputType,
+                        std::move(*checkedInput),
+                        StepCurve(std::move(checkedStops)))};
+            },
+            [&](const ExponentialInterpolation& interp) {
+                TypecheckResult result = outputType->match(
+                    [&](const type::NumberType&) -> TypecheckResult {
+                        return makeExponential<float>(*outputType, std::move(*checkedInput), std::move(checkedStops), interp.base);
+                    },
+                    [&](const type::ColorType&) -> TypecheckResult {
+                        return makeExponential<mbgl::Color>(*outputType, std::move(*checkedInput), std::move(checkedStops), interp.base);
+                    },
+                    [&](const type::Array& arrayType) -> TypecheckResult {
+                        if (toString(arrayType.itemType) == type::Number.getName() && arrayType.N) {
+                            return makeExponential<std::vector<Value>>(*outputType, std::move(*checkedInput), std::move(checkedStops), interp.base);
+                        } else {
+                            return TypecheckResult();
+                        }
+                    },
+                    [&](const auto&) { return TypecheckResult(); }
+                );
+                if (!result) {
+                    errors.push_back({"Type " + toString(*outputType) + " is not interpolatable, and thus cannot be used as an exponential curve's output type", stops.begin()->second->getKey() });
+                }
+                return result;
+            }
+        );
+    }
+    
+    
+private:
+    template <typename T>
+    std::unique_ptr<TypedExpression> makeExponential(const type::Type type, std::unique_ptr<TypedExpression> checkedInput, std::map<float, std::unique_ptr<TypedExpression>> checkedStops, float base) const {
+        return std::make_unique<TypedCurve<ExponentialCurve<T>>>(
+            type,
+            std::move(checkedInput),
+            ExponentialCurve<T>(std::move(checkedStops), base)
+        );
+    }
+
+    std::unique_ptr<UntypedExpression> input;
+    Stops stops;
+    Interpolation interpolation;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/let.hpp b/include/mbgl/style/expression/let.hpp
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/include/mbgl/style/expression/let.hpp
diff --git a/include/mbgl/style/expression/match.hpp b/include/mbgl/style/expression/match.hpp
new file mode 100644
index 0000000000..8bd2e1d238
--- /dev/null
+++ b/include/mbgl/style/expression/match.hpp
@@ -0,0 +1,287 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using InputType = variant<int64_t, std::string>;
+using MatchKey = variant<InputType, std::vector<InputType>>;
+
+template <typename T>
+class TypedMatch : public TypedExpression {
+public:
+    TypedMatch(std::unique_ptr<TypedExpression> input_,
+               std::vector<std::pair<MatchKey, std::unique_ptr<TypedExpression>>> cases_,
+               std::unique_ptr<TypedExpression> otherwise_
+    ) : TypedExpression(otherwise_->getType()),
+        input(std::move(input_)),
+        otherwise(std::move(otherwise_))
+    {
+        for(auto& pair : cases_) {
+            pair.first.match(
+                [&](const InputType& key) {
+                    cases.emplace(key.get<T>(), std::move(pair.second));
+                },
+                [&](const std::vector<InputType>& keys) {
+                    std::shared_ptr<TypedExpression> output = std::move(pair.second);
+                    for (const auto& key : keys) {
+                        cases.emplace(key.get<T>(), output);
+                    }
+                }
+            );
+        }
+    }
+    
+    bool isFeatureConstant() const override {
+        if (!input->isFeatureConstant()) { return false; }
+        if (!otherwise->isFeatureConstant()) { return false; }
+        for (const auto& pair : cases) {
+            if (!pair.second->isFeatureConstant()) { return false; }
+        }
+        return true;
+    }
+
+    bool isZoomConstant() const override {
+        if (!input->isZoomConstant()) { return false; }
+        if (!otherwise->isZoomConstant()) { return false; }
+        for (const auto& pair : cases) {
+            if (!pair.second->isZoomConstant()) { return false; }
+        }
+        return true;
+    }
+    
+    EvaluationResult evaluate(const EvaluationParameters& params) const override {
+        const auto& inputValue = input->evaluate<T>(params);
+        if (!inputValue) {
+            return inputValue.error();
+        }
+        if (cases.find(*inputValue) == cases.end()) {
+            return otherwise->evaluate(params);
+        }
+        return cases.at(*inputValue)->evaluate(params);
+    }
+
+private:
+    std::unique_ptr<TypedExpression> input;
+    std::unordered_map<T, std::shared_ptr<TypedExpression>> cases;
+    std::unique_ptr<TypedExpression> otherwise;
+};
+
+template <> EvaluationResult TypedMatch<int64_t>::evaluate(const EvaluationParameters& params) const {
+    const auto& inputValue = input->evaluate<float>(params);
+    if (!inputValue) {
+        return inputValue.error();
+    }
+    int64_t rounded = ceilf(*inputValue);
+    if (*inputValue != rounded || cases.find(rounded) == cases.end()) {
+        return otherwise->evaluate(params);
+    }
+    return cases.at(rounded)->evaluate(params);
+}
+
+class UntypedMatch : public UntypedExpression {
+public:
+    using Cases = std::vector<std::pair<MatchKey, std::unique_ptr<UntypedExpression>>>;
+    
+    UntypedMatch(std::string key,
+                 std::unique_ptr<UntypedExpression> input_,
+                 Cases cases_,
+                 std::unique_ptr<UntypedExpression> otherwise_,
+                 const type::Type& inputType_) :
+        UntypedExpression(key),
+        input(std::move(input_)),
+        cases(std::move(cases_)),
+        otherwise(std::move(otherwise_)),
+        inputType(inputType_)
+    {}
+    
+    template <class V>
+    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+        using namespace mbgl::style::conversion;
+        
+        assert(isArray(value));
+        auto length = arrayLength(value);
+        if (length < 3) {
+            return CompileError {
+                "Expected at least 2 arguments, but found only " + std::to_string(length - 1) + ".",
+                ctx.key()
+            };
+        }
+        
+        // Expect odd-length array: ["match", input, 2 * (n pairs)..., otherwise]
+        if (length % 2 != 1) {
+            return CompileError {
+                "Missing final output value for \"match\" expression.",
+                ctx.key()
+            };
+        }
+        
+        auto parsedInput = parseExpression(arrayMember(value, 1), ParsingContext(ctx, {1}, {"match"}));
+        if (parsedInput.template is<CompileError>()) {
+            return parsedInput;
+        }
+        
+        auto otherwise = parseExpression(arrayMember(value, length - 1), ParsingContext(ctx, {length - 1}, {"match"}));
+        if (otherwise.template is<CompileError>()) {
+            return otherwise;
+        }
+        
+        Cases cases;
+        optional<type::Type> inputType;
+        for (size_t i = 2; i + 1 < length; i += 2) {
+            auto output = parseExpression(arrayMember(value, i + 1), ParsingContext(ctx, {i + 1}, {"match"}));
+            if (output.template is<CompileError>()) {
+                return output.template get<CompileError>();
+            }
+
+            const auto& inputArg = arrayMember(value, i);
+            // Match pair inputs are provided as either a literal value or a
+            // raw JSON array of string / number / boolean values.
+            if (isArray(inputArg)) {
+                auto groupLength = arrayLength(inputArg);
+                if (groupLength == 0) return CompileError {
+                    "Expected at least one input value.",
+                    ctx.key(i)
+                };
+                std::vector<InputType> inputGroup;
+                for (size_t j = 0; j < groupLength; j++) {
+                    const auto& inputValue = parseInputValue(arrayMember(inputArg, j), ctx.key(i), inputType);
+                    if (inputValue.template is<CompileError>()) {
+                        return inputValue.template get<CompileError>();
+                    }
+                    inputGroup.emplace_back(inputValue.template get<InputType>());
+                }
+                cases.push_back(std::make_pair(
+                    inputGroup,
+                    std::move(output.template get<std::unique_ptr<UntypedExpression>>()))
+                );
+            } else {
+                const auto& inputValue = parseInputValue(inputArg, ctx.key(i), inputType);
+                if (inputValue.template is<CompileError>()) {
+                    return inputValue.template get<CompileError>();
+                }
+                cases.push_back(std::make_pair(
+                    inputValue.template get<InputType>(),
+                    std::move(output.template get<std::unique_ptr<UntypedExpression>>()))
+                );
+            }
+        }
+        
+        return std::make_unique<UntypedMatch>(ctx.key(),
+                                              std::move(parsedInput.template get<std::unique_ptr<UntypedExpression>>()),
+                                              std::move(cases),
+                                              std::move(otherwise.template get<std::unique_ptr<UntypedExpression>>()),
+                                              *inputType);
+    }
+    
+    template <typename V>
+    static variant<CompileError, InputType> parseInputValue(const V& input, const std::string& key, optional<type::Type>& inputType) {
+        using namespace mbgl::style::conversion;
+        optional<InputType> result;
+        optional<type::Type> type;
+        
+        auto value = toValue(input);
+        if (value && isIntegerValue(*value)) {
+            type = {type::Number};
+            result = {*numericValue<int64_t>(*value)};
+        } else if (value && value->template is<std::string>()) {
+            type = {type::String};
+            result = {value->template get<std::string>()};
+        } else {
+            return CompileError {
+                "Match inputs must be either literal integer or string values or arrays of integer or string values.",
+                key
+            };
+        }
+        
+        if (!inputType) {
+            inputType = type;
+        } else {
+            const auto& expected = toString(*inputType);
+            const auto& actual = toString(*type);
+            // TODO: replace with real == check
+            if (expected != actual) {
+                return CompileError {
+                    "Expected " + expected + " but found " + actual + " instead.",
+                    key
+                };
+            }
+        }
+        
+        return *result;
+    }
+    
+    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
+        auto checkedInput = input->typecheck(errors);
+        if (!checkedInput) {
+            return TypecheckResult();
+        }
+        auto checkedOtherwise = otherwise->typecheck(errors);
+        if (!checkedOtherwise) {
+            return TypecheckResult();
+        }
+
+        auto error = matchType(inputType, (*checkedInput)->getType());
+        if (error) {
+            errors.push_back({ *error, input->getKey() });
+        }
+        
+        optional<type::Type> outputType;
+        std::vector<std::pair<MatchKey, std::unique_ptr<TypedExpression>>> checkedCases;
+        for (const auto& pair : cases) {
+            auto checkedOutput = pair.second->typecheck(errors);
+            if (!checkedOutput) continue;
+            if (!outputType) {
+                outputType = (*checkedOutput)->getType();
+            } else {
+                error = matchType(*outputType, (*checkedOutput)->getType());
+                if (error) {
+                    errors.push_back({ *error, pair.second->getKey() });
+                    continue;
+                }
+            }
+            checkedCases.emplace_back(pair.first, std::move(*checkedOutput));
+        }
+        
+        error = matchType(*outputType, (*checkedOtherwise)->getType());
+        if (error) {
+            errors.push_back({ *error, otherwise->getKey() });
+        }
+        
+        if (inputType.is<type::StringType>()) {
+            return TypecheckResult(std::make_unique<TypedMatch<std::string>>(
+                std::move(*checkedInput), std::move(checkedCases), std::move(*checkedOtherwise)
+            ));
+        } else if (inputType.is<type::NumberType>()) {
+            return TypecheckResult(std::make_unique<TypedMatch<int64_t>>(
+                std::move(*checkedInput), std::move(checkedCases), std::move(*checkedOtherwise)
+            ));
+        }
+        
+        assert(false);
+        return TypecheckResult();
+    }
+    
+private:
+    static bool isIntegerValue(const mbgl::Value& v) {
+        return v.match(
+            [] (uint64_t) { return true; },
+            [] (int64_t) { return true; },
+            [] (double t) { return t == ceilf(t); },
+            [] (const auto&) { return false; }
+        );
+    }
+
+    std::unique_ptr<UntypedExpression> input;
+    Cases cases;
+    std::unique_ptr<UntypedExpression> otherwise;
+    type::Type inputType;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/parse.hpp b/include/mbgl/style/expression/parse.hpp
index e621441c3b..97ad880ae5 100644
--- a/include/mbgl/style/expression/parse.hpp
+++ b/include/mbgl/style/expression/parse.hpp
@@ -4,6 +4,9 @@
 #include <mbgl/style/expression/parsing_context.hpp>
 #include <mbgl/style/expression/expression.hpp>
 #include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/match.hpp>
+#include <mbgl/style/expression/curve.hpp>
+#include <mbgl/style/expression/coalesce.hpp>
 #include <mbgl/style/conversion.hpp>
 
 namespace mbgl {
@@ -65,6 +68,14 @@ ParseResult parseExpression(const V& value, const ParsingContext& context)
             return UntypedLiteral::parse(arrayMember(value, 1), ParsingContext(context, {1}, {"literal"}));
         }
         
+        if (*op == "match") {
+            return UntypedMatch::parse(value, context);
+        } else if (*op == "curve") {
+            return UntypedCurve::parse(value, context);
+        } else if (*op == "coalesce") {
+            return UntypedCoalesce::parse(value, context);
+        }
+        
         return UntypedCompoundExpression::parse(value, context);
     }
     
diff --git a/src/mbgl/style/expression/compound_expression.cpp b/src/mbgl/style/expression/compound_expression.cpp
index 189cb0f6a1..6767842b9a 100644
--- a/src/mbgl/style/expression/compound_expression.cpp
+++ b/src/mbgl/style/expression/compound_expression.cpp
@@ -172,10 +172,6 @@ std::unordered_map<std::string, CompoundExpression::Definition> CompoundExpressi
     define("-", [](float a, float b) -> Result<float> { return a - b; })
 );
 
-//        if (*op == "string") return LambdaExpression::parse<Assertion<std::string>>(value, context);
-//        if (*op == "number") return LambdaExpression::parse<Assertion<float>>(value, context);
-//        if (*op == "boolean") return LambdaExpression::parse<Assertion<bool>>(value, context);
-//        if (*op == "array") return Array::parse(value, context);
 //        if (*op == "to_string") return LambdaExpression::parse<ToString>(value, context);
 //        if (*op == "to_number") return LambdaExpression::parse<ToNumber>(value, context);
 //        if (*op == "to_boolean") return LambdaExpression::parse<ToBoolean>(value, context);