Implement v6 filters

5 files changed, 145 insertions, 385 deletions

diff --git a/src/map/vector_tile.cpp b/src/map/vector_tile.cpp
index 8f097c8292..ac7134fb0c 100644
--- a/src/map/vector_tile.cpp
+++ b/src/map/vector_tile.cpp
@@ -1,6 +1,5 @@
 #include <mbgl/map/vector_tile.hpp>
 #include <mbgl/style/filter_expression_private.hpp>
-#include <mbgl/style/filter_comparison_private.hpp>
 
 #include <algorithm>
 #include <iostream>
@@ -123,81 +122,6 @@ FilteredVectorTileLayer::iterator::iterator(const FilteredVectorTileLayer& paren
     operator++();
 }
 
-//bool FilteredVectorTileLayer::iterator::matchesFilterExpression(const FilterExpression &filterExpression, const pbf &tags_pbf) {
-//    if (filterExpression.empty()) {
-//        return true;
-//    }
-//
-//
-//
-//
-//    if (filterExpression.is<util::recursive_wrapper<PropertyFilter>>()) {
-//        return matchesFilter(filterExpression.get<util::recursive_wrapper<PropertyFilter>>().get(), tags_pbf);
-//    } else if (filterExpression.is<util::recursive_wrapper<PropertyExpression>>()) {
-//        return matchesExpression(filterExpression.get<util::recursive_wrapper<PropertyExpression>>().get(), tags_pbf);
-//    } else if (filterExpression.is<std::true_type>()) {
-//        return true;
-//    } else {
-//        return false;
-//    }
-//    return true;
-//}
-
-//
-//bool FilteredVectorTileLayer::iterator::matchesFilter(const PropertyFilter &filter, const pbf &const_tags_pbf) {
-//    auto field_it = parent.layer.key_index.find(filter.field);
-//    if (field_it != parent.layer.key_index.end()) {
-//        const uint32_t filter_key = field_it->second;
-//
-//        // Now loop through all the key/value pair tags.
-//        // tags are packed varints. They should have an even length.
-//        pbf tags_pbf = const_tags_pbf;
-//        while (tags_pbf) {
-//            uint32_t tag_key = tags_pbf.varint();
-//            if (!tags_pbf) {
-//                // This should not happen; otherwise the vector tile
-//                // is invalid.
-//                throw std::runtime_error("uneven number of feature tag ids");
-//            }
-//            uint32_t tag_val = tags_pbf.varint();
-//
-//            if (tag_key == filter_key) {
-//                if (parent.layer.values.size() > tag_val) {
-//                    const Value &value = parent.layer.values[tag_val];
-//                    return filter.compare(value);
-//                } else {
-//                    throw std::runtime_error("feature references out of range value");
-//                }
-//            }
-//        }
-//    }
-//
-//    // The feature doesn't contain the field that we're looking to compare.
-//    // Depending on the filter, this may still be okay.
-//    return filter.isMissingFieldOkay();
-//}
-//
-//bool FilteredVectorTileLayer::iterator::matchesExpression(const PropertyExpression &expression, const pbf &tags_pbf) {
-//    if (expression.op == ExpressionOperator::Or) {
-//        for (const PropertyFilterExpression &filterExpression : expression.operands) {
-//            if (matchesFilterExpression(filterExpression, tags_pbf)) {
-//                return true;
-//            }
-//        }
-//        return false;
-//    } else if (expression.op == ExpressionOperator::And) {
-//        for (const PropertyFilterExpression &filterExpression : expression.operands) {
-//            if (!matchesFilterExpression(filterExpression, tags_pbf)) {
-//                return false;
-//            }
-//        }
-//        return true;
-//    } else {
-//        return false;
-//    }
-//}
-//
-
 VectorTileTagExtractor::VectorTileTagExtractor(const VectorTileLayer &layer) : layer_(layer) {}
 
 
@@ -205,8 +129,12 @@ void VectorTileTagExtractor::setTags(const pbf &pbf) {
     tags_ = pbf;
 }
 
-std::vector<Value> VectorTileTagExtractor::getValues(const std::string &key) const {
-    std::vector<Value> values;
+mapbox::util::optional<Value> VectorTileTagExtractor::getValue(const std::string &key) const {
+    if (key == "$type") {
+        return Value(uint64_t(type_));
+    }
+
+    mapbox::util::optional<Value> value;
 
     auto field_it = layer_.key_index.find(key);
     if (field_it != layer_.key_index.end()) {
@@ -221,14 +149,14 @@ std::vector<Value> VectorTileTagExtractor::getValues(const std::string &key) con
             if (!tags_pbf) {
                 // This should not happen; otherwise the vector tile is invalid.
                 fprintf(stderr, "[WARNING] uneven number of feature tag ids\n");
-                return values;
+                return value;
             }
             // Note: We need to run this command in all cases, even if the keys don't match.
             tag_val = tags_pbf.varint();
 
             if (tag_key == filter_key) {
                 if (layer_.values.size() > tag_val) {
-                    values.emplace_back(layer_.values[tag_val]);
+                    value = layer_.values[tag_val];
                 } else {
                     fprintf(stderr, "[WARNING] feature references out of range value\n");
                     break;
@@ -237,16 +165,14 @@ std::vector<Value> VectorTileTagExtractor::getValues(const std::string &key) con
         }
     }
 
-    return values;
+    return value;
 }
 
-void VectorTileTagExtractor::setType(FilterExpression::GeometryType type) {
+void VectorTileTagExtractor::setType(FeatureType type) {
     type_ = type;
 }
 
-FilterExpression::GeometryType VectorTileTagExtractor::getType() const {
-    return type_;
-}
+template bool mbgl::evaluate(const FilterExpression&, const VectorTileTagExtractor&);
 
 void FilteredVectorTileLayer::iterator::operator++() {
     valid = false;
@@ -256,36 +182,21 @@ void FilteredVectorTileLayer::iterator::operator++() {
     while (data.next(2)) { // feature
         feature = data.message();
         pbf feature_pbf = feature;
-        bool matched = false;
 
-        // Treat the absence of any expression filters as a match.
-        if (expression.empty()) {
-            matched = true;
-        }
+        VectorTileTagExtractor extractor(parent.layer);
 
-        if (!matched) {
-            VectorTileTagExtractor extractor(parent.layer);
-
-            // Retrieve the basic information
-            while (feature_pbf.next()) {
-                if (feature_pbf.tag == 2) { // tags
-                    extractor.setTags(feature_pbf.message());
-                } else if (feature_pbf.tag == 3) { // geometry type
-                    switch (FeatureType(feature_pbf.varint())) {
-                        case FeatureType::Point:      extractor.setType(FilterExpression::GeometryType::Point); break;
-                        case FeatureType::LineString: extractor.setType(FilterExpression::GeometryType::LineString); break;
-                        case FeatureType::Polygon:    extractor.setType(FilterExpression::GeometryType::Polygon); break;
-                        default: break;
-                    }
-                } else {
-                    feature_pbf.skip();
-                }
+        // Retrieve the basic information
+        while (feature_pbf.next()) {
+            if (feature_pbf.tag == 2) { // tags
+                extractor.setTags(feature_pbf.message());
+            } else if (feature_pbf.tag == 3) { // geometry type
+                extractor.setType(FeatureType(feature_pbf.varint()));
+            } else {
+                feature_pbf.skip();
             }
-
-            matched = expression.compare(extractor);
         }
 
-        if (matched) {
+        if (evaluate(expression, extractor)) {
             valid = true;
             return; // data loop
         } else {
diff --git a/src/style/filter_comparison.cpp b/src/style/filter_comparison.cpp
deleted file mode 100644
index b3f3a9ef08..0000000000
--- a/src/style/filter_comparison.cpp
+++ /dev/null
@@ -1,143 +0,0 @@
-#include <mbgl/map/vector_tile.hpp>
-#include <mbgl/style/filter_comparison_private.hpp>
-
-#include <mbgl/style/value_comparison.hpp>
-
-#include <ostream>
-
-namespace mbgl {
-
-
-inline bool includes(const Value &property_value, const std::vector<Value> &filter_values) {
-    for (const Value &filter_value : filter_values) {
-        if (util::relaxed_equal(property_value, filter_value)) {
-            return true;
-        }
-    }
-    return false;
-}
-
-template <typename Comparer>
-inline bool compare(const Value &property_value, const std::vector<Value> &filter_values, const Comparer &comparer) {
-    for (const Value &filter_value : filter_values) {
-        if (!comparer(property_value, filter_value)) {
-            return false;
-        }
-    }
-    return true;
-}
-
-template <typename Comparer>
-inline bool all(const std::vector<Value> &property_values, const std::vector<Value> &filter_values, const Comparer &comparer) {
-    for (const Value &property_value : property_values) {
-        if (!compare(property_value, filter_values, comparer)) {
-            return false;
-        }
-    }
-    return true;
-}
-
-
-inline bool set_equal(const std::vector<Value> &property_values, const std::vector<Value> &filter_values) {
-    for (const Value &property_value : property_values) {
-        if (!includes(property_value, filter_values)) {
-            return false;
-        }
-    }
-    if (property_values.size() == filter_values.size()) {
-        // Optimization: When the count is the same, the set is guaranteed to be identical.
-        return true;
-    }
-    // Otherwise, check again for identical reverse-mapped values.
-    for (const Value &filter_value : filter_values) {
-        if (!includes(filter_value, property_values)) {
-            return false;
-        }
-    }
-    return true;
-}
-
-
-bool FilterComparison::Instance::compare(const std::vector<Value> &property_values) const {
-    switch (op) {
-        case Operator::Equal:
-            return set_equal(property_values, values);
-        case Operator::NotEqual:
-            return !set_equal(property_values, values);
-        case Operator::In:
-            for (const Value &property_value : property_values) {
-                if (includes(property_value, values)) {
-                    return true;
-                }
-            }
-            return false;
-        case Operator::NotIn:
-            for (const Value &property_value : property_values) {
-                if (!includes(property_value, values)) {
-                    return true;
-                }
-            }
-            return false;
-        case Operator::Greater:
-            return all(property_values, values, util::relaxed_greater);
-        case Operator::GreaterEqual:
-            return all(property_values, values, util::relaxed_greater_equal);
-        case Operator::Less:
-            return all(property_values, values, util::relaxed_less);
-        case Operator::LessEqual:
-            return all(property_values, values, util::relaxed_less_equal);
-        default:
-            return false;
-    }
-}
-
-
-const std::string &FilterComparison::getField() const {
-    return field;
-}
-
-std::ostream& operator <<(std::ostream &s, const FilterComparison &comparison) {
-    s << "comparison" << std::endl;
-    for (const FilterComparison::Instance &instance : comparison.instances) {
-        s << " - " << comparison.field << " " << instance << std::endl;
-    }
-    return s;
-}
-
-
-std::ostream& operator <<(std::ostream &s, const FilterComparison::Instance &instance) {
-    switch (instance.op) {
-        case FilterComparison::Operator::Equal: s << "=="; break;
-        case FilterComparison::Operator::NotEqual: s << "!="; break;
-        case FilterComparison::Operator::Greater: s << ">"; break;
-        case FilterComparison::Operator::GreaterEqual: s << ">="; break;
-        case FilterComparison::Operator::Less: s << "<"; break;
-        case FilterComparison::Operator::LessEqual: s << "<="; break;
-        case FilterComparison::Operator::In: s << "in"; break;
-        case FilterComparison::Operator::NotIn: s << "!in"; break;
-    }
-
-    s << " [ ";
-    for (const Value &value : instance.values) {
-        s << toString(value) << " ";
-    }
-    s << "]";
-    return s;
-}
-
-
-FilterComparison::Operator parseFilterComparisonOperator(const std::string &op) {
-    if (op == "==") return FilterComparison::Operator::Equal;
-    if (op == "!=") return FilterComparison::Operator::NotEqual;
-    if (op == ">") return FilterComparison::Operator::Greater;
-    if (op == ">=") return FilterComparison::Operator::GreaterEqual;
-    if (op == "<") return FilterComparison::Operator::Less;
-    if (op == "<=") return FilterComparison::Operator::LessEqual;
-    if (op == "in") return FilterComparison::Operator::In;
-    if (op == "!in") return FilterComparison::Operator::NotIn;
-    return FilterComparison::Operator::Equal;
-}
-
-template bool FilterComparison::compare(const VectorTileTagExtractor &extractor) const;
-
-}
diff --git a/src/style/filter_expression.cpp b/src/style/filter_expression.cpp
index ff4073b129..7d4f60b3ed 100644
--- a/src/style/filter_expression.cpp
+++ b/src/style/filter_expression.cpp
@@ -1,66 +1,123 @@
-#include <mbgl/style/filter_expression_private.hpp>
 #include <mbgl/map/vector_tile.hpp>
-
-#include <mbgl/style/value_comparison.hpp>
-
-#include <ostream>
+#include <mbgl/platform/log.hpp>
 
 namespace mbgl {
 
-std::ostream& operator <<(std::ostream &s, FilterExpression::Operator op) {
-    switch (op) {
-        case FilterExpression::Operator::And: s << "AND"; break;
-        case FilterExpression::Operator::Or: s << "OR"; break;
-        case FilterExpression::Operator::Xor: s << "XOR"; break;
-        case FilterExpression::Operator::Nor: s << "NOR"; break;
+Value parseFeatureType(const Value& value) {
+    if (value == std::string("Point")) {
+        return Value(uint64_t(FeatureType::Point));
+    } else if (value == std::string("LineString")) {
+        return Value(uint64_t(FeatureType::LineString));
+    } else if (value == std::string("Polygon")) {
+        return Value(uint64_t(FeatureType::Polygon));
+    } else {
+        Log::Warning(Event::ParseStyle, "value for $type filter must be Point, LineString, or Polygon");
+        return Value(uint64_t(FeatureType::Unknown));
     }
-    return s;
 }
 
+template <class Expression>
+FilterExpression parseBinaryFilter(const rapidjson::Value& value) {
+    FilterExpression empty;
 
-std::ostream& operator <<(std::ostream &s, FilterExpression::GeometryType type) {
-    switch (type) {
-        case FilterExpression::GeometryType::Point: s << "Point"; break;
-        case FilterExpression::GeometryType::LineString: s << "LineString"; break;
-        case FilterExpression::GeometryType::Polygon: s << "Polygon"; break;
-        case FilterExpression::GeometryType::Any: s << "<Any>"; break;
+    if (value.Size() < 3) {
+        Log::Warning(Event::ParseStyle, "filter expression must have 3 elements");
+        return empty;
     }
-    return s;
-}
 
-bool FilterExpression::empty() const {
-    return type == GeometryType::Any && comparisons.empty() && expressions.empty();
-}
+    if (!value[1u].IsString()) {
+        Log::Warning(Event::ParseStyle, "filter expression key must be a string");
+        return empty;
+    }
 
-void FilterExpression::add(const FilterComparison &comparison) {
-    comparisons.emplace_back(comparison);
-}
+    Expression expression;
+    expression.key = { value[1u].GetString(), value[1u].GetStringLength() };
+    expression.value = parseValue(value[2u]);
 
-void FilterExpression::add(const FilterExpression &expression) {
-    expressions.emplace_back(expression);
-}
+    if (expression.key == "$type") {
+        expression.value = parseFeatureType(expression.value);
+    }
 
-void FilterExpression::setGeometryType(GeometryType g) {
-    type = g;
+    return expression;
 }
 
-FilterExpression::GeometryType parseGeometryType(const std::string &geometry) {
-    if (geometry == "Point") return FilterExpression::GeometryType::Point;
-    if (geometry == "LineString") return FilterExpression::GeometryType::LineString;
-    if (geometry == "Polygon") return FilterExpression::GeometryType::Polygon;
-    return FilterExpression::GeometryType::Any;
+template <class Expression>
+FilterExpression parseSetFilter(const rapidjson::Value& value) {
+    FilterExpression empty;
+
+    if (value.Size() < 2) {
+        Log::Warning(Event::ParseStyle, "filter expression must at least 2 elements");
+        return empty;
+    }
+
+    if (!value[1u].IsString()) {
+        Log::Warning(Event::ParseStyle, "filter expression key must be a string");
+        return empty;
+    }
+
+    Expression expression;
+    expression.key = { value[1u].GetString(), value[1u].GetStringLength() };
+    for (rapidjson::SizeType i = 2; i < value.Size(); ++i) {
+        expression.values.push_back(parseValue(value[i]));
+    }
+    return expression;
 }
 
-std::ostream& operator <<(std::ostream &s, const FilterExpression &expression) {
-    s << "expression " << expression.op << std::endl;
-    s << " - $type = " << expression.type << std::endl;
-    for (const FilterComparison &comparison : expression.comparisons) {
-        s << comparison;
+template <class Expression>
+FilterExpression parseCompoundFilter(const rapidjson::Value& value) {
+    Expression expression;
+    for (rapidjson::SizeType i = 1; i < value.Size(); ++i) {
+        expression.expressions.push_back(parseFilterExpression(value[i]));
     }
-    s << "end expression" << std::endl;
-    return s;
+    return expression;
 }
 
-template bool FilterExpression::compare(const VectorTileTagExtractor &extractor) const;
+FilterExpression parseFilterExpression(const rapidjson::Value& value) {
+    FilterExpression empty;
+
+    if (!value.IsArray()) {
+        Log::Warning(Event::ParseStyle, "filter expression must be an array");
+        return empty;
+    }
+
+    if (value.Size() < 1) {
+        Log::Warning(Event::ParseStyle, "filter expression must have at least 1 element");
+        return empty;
+    }
+
+    if (!value[0u].IsString()) {
+        Log::Warning(Event::ParseStyle, "filter operator must be a string");
+        return empty;
+    }
+
+    std::string op = { value[0u].GetString(), value[0u].GetStringLength() };
+
+    if (op == "==") {
+        return parseBinaryFilter<EqualsExpression>(value);
+    } else if (op == "!=") {
+        return parseBinaryFilter<NotEqualsExpression>(value);
+    } else if (op == ">") {
+        return parseBinaryFilter<GreaterThanExpression>(value);
+    } else if (op == ">=") {
+        return parseBinaryFilter<GreaterThanEqualsExpression>(value);
+    } else if (op == "<") {
+        return parseBinaryFilter<LessThanExpression>(value);
+    } else if (op == "<=") {
+        return parseBinaryFilter<LessThanEqualsExpression>(value);
+    } else if (op == "in") {
+        return parseSetFilter<InExpression>(value);
+    } else if (op == "!in") {
+        return parseSetFilter<NotInExpression>(value);
+    } else if (op == "all") {
+        return parseCompoundFilter<AllExpression>(value);
+    } else if (op == "any") {
+        return parseCompoundFilter<AnyExpression>(value);
+    } else if (op == "none") {
+        return parseCompoundFilter<NoneExpression>(value);
+    } else {
+        Log::Warning(Event::ParseStyle, "filter operator must be one of \"==\", \"!=\", \">\", \">=\", \"<\", \"<=\", \"in\", \"!in\", \"all\", \"any\", \"none\"");
+        return empty;
+    }
+}
 
 }
diff --git a/src/style/style_parser.cpp b/src/style/style_parser.cpp
index 6dd2e678cc..9f23074419 100644
--- a/src/style/style_parser.cpp
+++ b/src/style/style_parser.cpp
@@ -711,7 +711,7 @@ void StyleParser::parseBucket(JSVal value, util::ptr<StyleLayer> &layer) {
 
     if (value.HasMember("filter")) {
         JSVal value_filter = replaceConstant(value["filter"]);
-        layer->bucket->filter = parseFilter(value_filter);
+        layer->bucket->filter = parseFilterExpression(value_filter);
     }
 
     if (value.HasMember("render")) {
@@ -738,93 +738,6 @@ void StyleParser::parseBucket(JSVal value, util::ptr<StyleLayer> &layer) {
     }
 }
 
-FilterExpression StyleParser::parseFilter(JSVal value) {
-    return parseFilter(value, value.IsArray() ? FilterExpression::Operator::Or : FilterExpression::Operator::And);
-}
-
-FilterExpression StyleParser::parseFilter(JSVal value, FilterExpression::Operator op) {
-    FilterExpression expression(op);
-    if (value.IsObject()) {
-        rapidjson::Value::ConstMemberIterator itr = value.MemberBegin();
-        for (; itr != value.MemberEnd(); ++itr) {
-            const std::string name { itr->name.GetString(), itr->name.GetStringLength() };
-            if (name == "&") {
-                expression.add(parseFilter(replaceConstant(itr->value), FilterExpression::Operator::And));
-            } else if (name == "|") {
-                expression.add(parseFilter(replaceConstant(itr->value), FilterExpression::Operator::Or));
-            } else if (name == "^") {
-                expression.add(parseFilter(replaceConstant(itr->value), FilterExpression::Operator::Xor));
-            } else if (name == "!") {
-                expression.add(parseFilter(replaceConstant(itr->value), FilterExpression::Operator::Nor));
-            } else if (name == "$type") {
-                JSVal type = replaceConstant(itr->value);
-                if (type.IsString()) {
-                    expression.setGeometryType(parseGeometryType({ type.GetString(), type.GetStringLength() }));
-                }
-            } else {
-                FilterComparison comparison(name);
-                JSVal filterValue = replaceConstant(itr->value);
-                if (filterValue.IsObject()) {
-                    rapidjson::Value::ConstMemberIterator filter_itr = filterValue.MemberBegin();
-                    for (; filter_itr != filterValue.MemberEnd(); ++filter_itr) {
-                        comparison.add(
-                            parseFilterComparisonOperator({ filter_itr->name.GetString(), filter_itr->name.GetStringLength() }),
-                            parseValues(replaceConstant(filter_itr->value))
-                        );
-                    }
-                } else if (filterValue.IsArray()) {
-                    comparison.add(FilterComparison::Operator::In, parseValues(filterValue));
-                } else {
-                    comparison.add(FilterComparison::Operator::Equal, std::vector<Value>({ parseValue(filterValue) }));
-                }
-                expression.add(comparison);
-            }
-        }
-    } else if (value.IsArray()) {
-        for (rapidjson::SizeType i = 0; i < value.Size(); i++) {
-            expression.add(parseFilter(replaceConstant(value[i])));
-        }
-    } else {
-        Log::Warning(Event::ParseStyle, "expression must be either an array or an object");
-    }
-
-    return expression;
-}
-
-Value StyleParser::parseValue(JSVal value) {
-    switch (value.GetType()) {
-        case rapidjson::kNullType:
-        case rapidjson::kFalseType:
-            return false;
-
-        case rapidjson::kTrueType:
-            return true;
-
-        case rapidjson::kStringType:
-            return std::string { value.GetString(), value.GetStringLength() };
-
-        case rapidjson::kNumberType:
-            if (value.IsUint64()) return value.GetUint64();
-            if (value.IsInt64()) return value.GetInt64();
-            return value.GetDouble();
-
-        default:
-            return false;
-    }
-}
-
-std::vector<Value> StyleParser::parseValues(JSVal value) {
-    std::vector<Value> values;
-    if (value.IsArray()) {
-        for (rapidjson::SizeType i = 0; i < value.Size(); i++) {
-            values.emplace_back(parseValue(replaceConstant(value[i])));
-        }
-    } else {
-        values.emplace_back(parseValue(value));
-    }
-    return values;
-}
-
 void StyleParser::parseRender(JSVal value, util::ptr<StyleLayer> &layer) {
     if (!value.IsObject()) {
         Log::Warning(Event::ParseStyle, "render property of layer '%s' must be an object", layer->id.c_str());
diff --git a/src/style/value.cpp b/src/style/value.cpp
index 5cd32376ab..bda9a089a8 100644
--- a/src/style/value.cpp
+++ b/src/style/value.cpp
@@ -42,3 +42,25 @@ std::string mbgl::toString(const mbgl::Value& value) {
     else if (value.is<double>()) return boost::lexical_cast<std::string>(value.get<double>());
     else return "null";
 }
+
+mbgl::Value mbgl::parseValue(const rapidjson::Value& value) {
+    switch (value.GetType()) {
+        case rapidjson::kNullType:
+        case rapidjson::kFalseType:
+            return false;
+
+        case rapidjson::kTrueType:
+            return true;
+
+        case rapidjson::kStringType:
+            return std::string { value.GetString(), value.GetStringLength() };
+
+        case rapidjson::kNumberType:
+            if (value.IsUint64()) return value.GetUint64();
+            if (value.IsInt64()) return value.GetInt64();
+            return value.GetDouble();
+
+        default:
+            return false;
+    }
+}