simple expression support

5 files changed, 177 insertions, 74 deletions

diff --git a/include/llmr/map/vector_tile.hpp b/include/llmr/map/vector_tile.hpp
index 1e809556e5..8c70016bc3 100644
--- a/include/llmr/map/vector_tile.hpp
+++ b/include/llmr/map/vector_tile.hpp
@@ -7,12 +7,15 @@
 #include <llmr/text/glyph.hpp>
 #include <vector>
 #include <map>
+#include <unordered_map>
 #include <set>
 #include <limits>
 
 namespace llmr {
 
 class BucketDescription;
+class BucketExpression;
+class BucketFilter;
 class VectorTileLayer;
 
 struct pbf;
@@ -53,7 +56,11 @@ public:
         const pbf& operator*() const;
 
     private:
-        const FilteredVectorTileLayer& filter;
+        bool matchesExpression(const BucketExpression &expression, const pbf &tags_pbf);
+        bool matchesFilter(const BucketFilter &filter, const pbf &tags_pbf);
+
+    private:
+        const FilteredVectorTileLayer& parent;
         bool valid = false;
         pbf feature;
         pbf data;
@@ -68,8 +75,6 @@ public:
 private:
     const VectorTileLayer& layer;
     const BucketDescription& bucket_desc;
-    int32_t key = -1;
-    std::set<uint32_t> values;
 };
 
 std::ostream& operator<<(std::ostream&, const GlyphPlacement& placement);
@@ -82,6 +87,7 @@ public:
     std::string name;
     uint32_t extent = 4096;
     std::vector<std::string> keys;
+    std::unordered_map<std::string, uint32_t> key_index;
     std::vector<Value> values;
     std::map<std::string, std::map<Value, Shaping>> shaping;
 };
diff --git a/include/llmr/style/bucket_description.hpp b/include/llmr/style/bucket_description.hpp
index 3b6fc43136..e7b8a63e79 100644
--- a/include/llmr/style/bucket_description.hpp
+++ b/include/llmr/style/bucket_description.hpp
@@ -38,6 +38,16 @@ enum class TextPathType {
     Curve = 1
 };
 
+enum class FilterOperator {
+    Equal,
+    NotEqual
+};
+
+enum class ExpressionOperator {
+    Or,
+    And
+};
+
 
 inline BucketType bucketType(const std::string& type) {
     if (type == "fill") return BucketType::Fill;
@@ -81,6 +91,23 @@ inline float verticalAlignmentType(const std::string& alignment) {
     else return 0.5;
 };
 
+inline FilterOperator filterOperatorType(const std::string &op) {
+    if (op == "!=" || op == "not") {
+        return FilterOperator::NotEqual;
+    } else {
+        return FilterOperator::Equal;
+    }
+}
+
+inline ExpressionOperator expressionOperatorType(const std::string &op) {
+    if (op == "&&" || op == "and") {
+        return ExpressionOperator::And;
+    } else {
+        return ExpressionOperator::Or;
+    }
+}
+
+
 class BucketGeometryDescription {
 public:
     CapType cap = CapType::None;
@@ -105,6 +132,42 @@ public:
     bool alwaysVisible = false;
 };
 
+
+class BucketFilter {
+public:
+    inline BucketFilter(const std::string &field, const Value &value) : field(field), value(value) {};
+
+    // Returns true if the filter passes, even if the key is missing.
+    inline bool isMissingFieldOkay() const {
+        switch (op) {
+        case FilterOperator::NotEqual:
+            return true;
+        default:
+            return false;
+        }
+    }
+
+    inline bool compare(const Value &other) const {
+        switch (op) {
+        case FilterOperator::NotEqual:
+            return !util::relaxed_equal(value)(other);
+        default:
+            return util::relaxed_equal(value)(other);
+        }
+    }
+
+public:
+    std::string field;
+    Value value;
+    FilterOperator op = FilterOperator::Equal;
+};
+
+class BucketExpression {
+public:
+    ExpressionOperator op = ExpressionOperator::Or;
+    std::vector<BucketFilter> operands;
+};
+
 class BucketDescription {
 public:
     BucketType feature_type = BucketType::None;
@@ -113,8 +176,8 @@ public:
     // Specify what data to pull into this bucket
     std::string source_name;
     std::string source_layer;
-    std::string source_field;
-    std::vector<Value> source_value;
+
+    BucketExpression filter;
 
     // Specifies how the geometry for this bucket should be created
     BucketGeometryDescription geometry;
diff --git a/src/map/vector_tile.cpp b/src/map/vector_tile.cpp
index f0f5a85cdf..bc6386e858 100644
--- a/src/map/vector_tile.cpp
+++ b/src/map/vector_tile.cpp
@@ -91,6 +91,7 @@ VectorTileLayer::VectorTileLayer(pbf layer) : data(layer) {
             name = layer.string();
         } else if (layer.tag == 3) { // keys
             keys.emplace_back(layer.string());
+            key_index.emplace(keys.back(), keys.size() - 1);
         } else if (layer.tag == 4) { // values
             values.emplace_back(std::move(parseValue(layer.message())));
         } else if (layer.tag == 5) { // extent
@@ -104,81 +105,108 @@ VectorTileLayer::VectorTileLayer(pbf layer) : data(layer) {
 FilteredVectorTileLayer::FilteredVectorTileLayer(const VectorTileLayer& layer, const BucketDescription& bucket_desc)
     : layer(layer),
       bucket_desc(bucket_desc) {
-    // If we filter further by field/value, parse the key/value indices first
-    // because protobuf doesn't mandate a particular key order.
-    if (bucket_desc.source_field.size()) {
-        // Get the ID of the desired layer key.
-        auto key_it = std::find(layer.keys.begin(), layer.keys.end(), bucket_desc.source_field);
-        if (key_it != layer.keys.end()) {
-            key = (int32_t)(key_it - layer.keys.begin());
-        }
-        // Get the ID of the desired layer value(s), comparing as strings in
-        // order to avoid numeric type mismatches between the layer and the
-        // style definition.
-        for (const Value& source_value : bucket_desc.source_value) {
-            auto value_it = std::find_if(layer.values.begin(), layer.values.end(), util::relaxed_equal(source_value));
-            if (value_it != layer.values.end()) {
-                values.insert((uint32_t)(value_it - layer.values.begin()));
-            }
-        }
-    }
 }
 
 FilteredVectorTileLayer::iterator FilteredVectorTileLayer::begin() const {
-    if (bucket_desc.source_field.size() && (key < 0 || values.empty())) {
-        // There are no valid values that we could possibly find. Abort early.
-        return end();
-    } else {
-        return iterator(*this, layer.data);
-    }
+    return iterator(*this, layer.data);
 }
 
 FilteredVectorTileLayer::iterator FilteredVectorTileLayer::end() const {
     return iterator(*this, pbf(layer.data.end, 0));
 }
 
-FilteredVectorTileLayer::iterator::iterator(const FilteredVectorTileLayer& filter, const pbf& data)
-    : filter(filter),
+FilteredVectorTileLayer::iterator::iterator(const FilteredVectorTileLayer& parent, const pbf& data)
+    : parent(parent),
       feature(pbf()),
       data(data) {
     operator++();
 }
 
+bool FilteredVectorTileLayer::iterator::matchesFilter(const BucketFilter &filter, const pbf &const_tags_pbf) {
+    bool missing = true;
+
+    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 BucketExpression &expression, const pbf &tags_pbf) {
+    if (expression.op == ExpressionOperator::Or) {
+        for (const BucketFilter &filter : expression.operands) {
+            if (matchesFilter(filter, tags_pbf)) {
+                return true;
+            }
+        }
+        return false;
+    } else if (expression.op == ExpressionOperator::And) {
+        for (const BucketFilter &filter : expression.operands) {
+            if (!matchesFilter(filter, tags_pbf)) {
+                return false;
+            }
+        }
+        return true;
+    } else {
+        return false;
+    }
+}
+
+
+
 void FilteredVectorTileLayer::iterator::operator++() {
     valid = false;
 
+    BucketExpression expression = parent.bucket_desc.filter;
+
     while (data.next(2)) { // feature
         feature = data.message();
         pbf feature_pbf = feature;
         BucketType type = BucketType::None;
 
-        bool skip = false;
-        while (!skip && feature_pbf.next()) {
+        bool matched = false;
+
+        // Treat the absence of any expression filters as a match.
+        if (expression.operands.size() == 0) {
+            matched = true;
+        }
+
+        while (feature_pbf.next()) {
             if (feature_pbf.tag == 2) { // tags
-                if (filter.key < 0) {
-                    // We want to parse the entire layer anyway
+                if (matched) {
+                    // There is no filter, so we want to parse the entire layer anyway.
                     feature_pbf.skip();
                 } else {
                     // We only want to parse some features.
-                    skip = true;
-
-                    // tags are packed varints. They should have an even length.
-                    pbf tags_pbf = feature_pbf.message();
-                    while (tags_pbf) {
-                        int32_t tag_key = tags_pbf.varint();
-                        if (tags_pbf) {
-                            uint32_t tag_val = tags_pbf.varint();
-                            // Now check if the tag_key/tag_val pair is included
-                            // in the set of key/values that we are looking for.
-                            if (filter.key == tag_key && filter.values.find(tag_val) != filter.values.end()) {
-                                skip = false;
-                                break; // feature_pbf loop
-                            }
-                        } else {
-                            // This should not happen; otherwise the vector tile
-                            // is invalid.
-                            throw std::runtime_error("uneven number of feature tag ids");
-                        }
+                    const pbf tags_pbf = feature_pbf.message();
+                    matched = matchesExpression(expression, tags_pbf);
+                    if (!matched) {
+                        break; // feature_pbf loop early
                     }
                 }
             } else if (feature_pbf.tag == 3) { // geometry type
@@ -189,7 +217,8 @@ void FilteredVectorTileLayer::iterator::operator++() {
                     default:                 type = BucketType::None; break;
                 }
 
-                if (type != filter.bucket_desc.feature_type) {
+                if (type != parent.bucket_desc.feature_type) {
+                    matched = false;
                     break; // feature_pbf loop early
                 }
             } else {
@@ -197,7 +226,7 @@ void FilteredVectorTileLayer::iterator::operator++() {
             }
         }
 
-        if (!skip && type == filter.bucket_desc.feature_type) {
+        if (matched) {
             valid = true;
             return; // data loop
         } else {
diff --git a/src/style/bucket_description.cpp b/src/style/bucket_description.cpp
index 864603e315..b154c3a176 100644
--- a/src/style/bucket_description.cpp
+++ b/src/style/bucket_description.cpp
@@ -2,15 +2,12 @@
 
 #include <iostream>
 
+
 std::ostream& llmr::operator<<(std::ostream& os, const BucketDescription& bucket) {
     os << "Bucket:" << std::endl;
     os << "  - type: " << (uint32_t)bucket.type << std::endl;
     os << "  - source_name: " << bucket.source_name << std::endl;
     os << "  - source_layer: " << bucket.source_layer << std::endl;
-    os << "  - source_field: " << bucket.source_field << std::endl;
-    for (const Value& value : bucket.source_value) {
-        os << "  - source_value: " << value << std::endl;
-    }
     os << "  - cap: " << (uint32_t)bucket.geometry.cap << std::endl;
     os << "  - join: " << (uint32_t)bucket.geometry.join << std::endl;
     os << "  - font: " << bucket.geometry.font << std::endl;
diff --git a/src/style/style_parser.cpp b/src/style/style_parser.cpp
index 2b6c0e3f22..21840397c7 100644
--- a/src/style/style_parser.cpp
+++ b/src/style/style_parser.cpp
@@ -52,20 +52,6 @@ BucketDescription StyleParser::parseBucket(JSVal value) {
             } else {
                 throw Style::exception("layer name must be a string");
             }
-        } else if (name == "field") {
-            if (value.IsString()) {
-                bucket.source_field = { value.GetString(), value.GetStringLength() };
-            } else {
-                throw Style::exception("field name must be a string");
-            }
-        } else if (name == "value") {
-            if (value.IsArray()) {
-                for (rapidjson::SizeType i = 0; i < value.Size(); ++i) {
-                    bucket.source_value.push_back(parseValue(value[i]));
-                }
-            } else {
-                bucket.source_value.push_back(parseValue(value));
-            }
         } else if (name == "cap") {
             if (value.IsString()) {
                 bucket.geometry.cap = capType({ value.GetString(), value.GetStringLength() });
@@ -167,6 +153,28 @@ BucketDescription StyleParser::parseBucket(JSVal value) {
 
     }
 
+
+    if (value.HasMember("field") && value.HasMember("value")) {
+        JSVal field = value["field"];
+        JSVal val = value["value"];
+
+        if (!field.IsString()) {
+            throw Style::exception("field name must be a string");
+        }
+
+        const std::string field_name { field.GetString(), field.GetStringLength() };
+
+        bucket.filter = {};
+
+        if (val.IsArray()) {
+            for (rapidjson::SizeType i = 0; i < val.Size(); ++i) {
+                bucket.filter.operands.emplace_back(field_name, parseValue(val[i]));
+            }
+        } else {
+            bucket.filter.operands.emplace_back(field_name, parseValue(val));
+        }
+    }
+
     if (bucket.feature_type == BucketType::None) {
         bucket.feature_type = bucket.type;
     }