add filter expressions

4 files changed, 411 insertions, 90 deletions

diff --git a/src/map/filter_expression.cpp b/src/map/filter_expression.cpp
new file mode 100644
index 0000000000..9e293b0026
--- /dev/null
+++ b/src/map/filter_expression.cpp
@@ -0,0 +1,282 @@
+#include <llmr/map/filter_expression.hpp>
+#include <llmr/map/vector_tile.hpp>
+
+namespace llmr {
+
+
+template <typename Comparer>
+inline bool FilterComparison::Instance::includes(const Value &property_value, const Comparer &comparer) const {
+    for (const Value &filter_value : values) {
+        if (comparer(property_value, filter_value)) {
+            return true;
+        }
+    }
+    return false;
+}
+
+template <typename Comparer>
+inline bool FilterComparison::Instance::compare(const Value &property_value, const Comparer &comparer) const {
+    for (const Value &filter_value : values) {
+        if (!comparer(property_value, filter_value)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+template <typename Comparer>
+inline bool FilterComparison::Instance::all(const std::forward_list<Value> &property_values, const Comparer &comparer) const {
+    for (const Value &property_value : property_values) {
+        if (!compare(property_value, comparer)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+
+
+bool FilterComparison::Instance::compare(const Value &property_value) const {
+    switch (op) {
+        case Operator::Equal:
+        case Operator::In:
+            return includes(property_value, util::relaxed_equal);
+        case Operator::NotEqual:
+        case Operator::NotIn:
+            return !includes(property_value, util::relaxed_equal);
+        case Operator::Greater:
+            return compare(property_value, util::relaxed_greater);
+        case Operator::GreaterEqual:
+            return compare(property_value, util::relaxed_greater_equal);
+        case Operator::Less:
+            return compare(property_value, util::relaxed_less);
+        case Operator::LessEqual:
+            return compare(property_value, util::relaxed_less_equal);
+        default:
+            return false;
+    }
+}
+
+bool FilterComparison::Instance::compare(const std::forward_list<Value> &property_values) const {
+    switch (op) {
+        case Operator::Equal:
+            for (const Value &property_value : property_values) {
+                if (!includes(property_value, util::relaxed_equal)) {
+                    return false;
+                }
+            }
+            return true;
+        case Operator::NotEqual:
+            for (const Value &property_value : property_values) {
+                if (includes(property_value, util::relaxed_equal)) {
+                    return false;
+                }
+            }
+            return true;
+        case Operator::In:
+            for (const Value &property_value : property_values) {
+                if (includes(property_value, util::relaxed_equal)) {
+                    return true;
+                }
+            }
+            return false;
+        case Operator::NotIn:
+            for (const Value &property_value : property_values) {
+                if (!includes(property_value, util::relaxed_equal)) {
+                    return true;
+                }
+            }
+            return false;
+        case Operator::Greater:
+            return all(property_values, util::relaxed_greater);
+        case Operator::GreaterEqual:
+            return all(property_values, util::relaxed_greater_equal);
+        case Operator::Less:
+            return all(property_values, util::relaxed_less);
+        case Operator::LessEqual:
+            return all(property_values, util::relaxed_less_equal);
+    }
+}
+
+
+const std::string &FilterComparison::getField() const {
+    return field;
+}
+
+inline bool FilterComparison::compare(const VectorTileTagExtractor &extractor) const {
+    const std::forward_list<Value> values = extractor.getValues(field);
+
+    // All instances are ANDed together.
+    for (const Instance &instance : instances) {
+        if (!instance.compare(values)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+
+
+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;
+}
+
+
+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;
+    }
+    return s;
+}
+
+
+std::ostream& operator <<(std::ostream &s, FilterExpression::GeometryType type) {
+    switch (type) {
+        case FilterExpression::GeometryType::Point: s << "point"; break;
+        case FilterExpression::GeometryType::Line: s << "line"; break;
+        case FilterExpression::GeometryType::Polygon: s << "polygon"; break;
+        case FilterExpression::GeometryType::Any: s << "any"; break;
+    }
+    return s;
+}
+
+
+
+bool FilterExpression::compare(const VectorTileTagExtractor &extractor) const {
+    if (type != GeometryType::Any && extractor.getType() != type && extractor.getType() != GeometryType::Any) {
+        return false;
+    }
+
+    switch (op) {
+    case Operator::And:
+        for (const FilterComparison &comparison : comparisons) {
+            if (!comparison.compare(extractor)) {
+                return false;
+            }
+        }
+        for (const FilterExpression &expression: expressions) {
+            if (!expression.compare(extractor)) {
+                return false;
+            }
+        }
+        return true;
+    case Operator::Or:
+        for (const FilterComparison &comparison : comparisons) {
+            if (comparison.compare(extractor)) {
+                return true;
+            }
+        }
+        for (const FilterExpression &expression: expressions) {
+            if (expression.compare(extractor)) {
+                return true;
+            }
+        }
+        return false;
+    case Operator::Xor: {
+        int count = 0;
+        for (const FilterComparison &comparison : comparisons) {
+            count += comparison.compare(extractor);
+            if (count > 1) {
+                return false;
+            }
+        }
+        for (const FilterExpression &expression: expressions) {
+            count += expression.compare(extractor);
+            if (count > 1) {
+                return false;
+            }
+        }
+        return count == 1;
+    }
+    case Operator::Nor:
+        for (const FilterComparison &comparison : comparisons) {
+            if (comparison.compare(extractor)) {
+                return false;
+            }
+        }
+        for (const FilterExpression &expression: expressions) {
+            if (expression.compare(extractor)) {
+                return false;
+            }
+        }
+        return true;
+    default:
+        return true;
+    }
+}
+
+bool FilterExpression::empty() const {
+    return type == GeometryType::Any && comparisons.empty() && expressions.empty();
+}
+
+void FilterExpression::add(const FilterComparison &comparison) {
+    comparisons.emplace_front(comparison);
+}
+
+void FilterExpression::add(const FilterExpression &expression) {
+    expressions.emplace_front(expression);
+}
+
+void FilterExpression::setGeometryType(GeometryType g) {
+    type = g;
+}
+
+FilterExpression::GeometryType parseGeometryType(const std::string &geometry) {
+    if (geometry == "point") return FilterExpression::GeometryType::Point;
+    if (geometry == "line") return FilterExpression::GeometryType::Line;
+    if (geometry == "polygon") return FilterExpression::GeometryType::Polygon;
+    return FilterExpression::GeometryType::Any;
+}
+
+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;
+    }
+    s << "end expression" << std::endl;
+    return s;
+}
+
+}
diff --git a/src/map/map.cpp b/src/map/map.cpp
index 01f7ac6072..db94ca97db 100644
--- a/src/map/map.cpp
+++ b/src/map/map.cpp
@@ -169,8 +169,6 @@ void Map::setup() {
     view.make_active();
 
     painter.setup();
-
-    setStyleJSON(styleJSON);
 }
 
 void Map::setStyleJSON(std::string newStyleJSON) {
diff --git a/src/map/tile_parser.cpp b/src/map/tile_parser.cpp
index b4041ada4e..e834e6fa95 100644
--- a/src/map/tile_parser.cpp
+++ b/src/map/tile_parser.cpp
@@ -132,7 +132,7 @@ std::unique_ptr<Bucket> TileParser::createBucket(std::shared_ptr<StyleBucket> bu
 }
 
 template <class Bucket>
-void TileParser::addBucketFeatures(Bucket& bucket, const VectorTileLayer& layer, const PropertyFilterExpression &filter) {
+void TileParser::addBucketFeatures(Bucket& bucket, const VectorTileLayer& layer, const FilterExpression &filter) {
     FilteredVectorTileLayer filtered_layer(layer, filter);
     for (pbf feature : filtered_layer) {
         if (obsolete())
@@ -150,7 +150,7 @@ void TileParser::addBucketFeatures(Bucket& bucket, const VectorTileLayer& layer,
 }
 
 template <class Bucket, typename... Args>
-void TileParser::addBucketFeatures(Bucket& bucket, const VectorTileLayer& layer, const PropertyFilterExpression &filter, Args&& ...args) {
+void TileParser::addBucketFeatures(Bucket& bucket, const VectorTileLayer& layer, const FilterExpression &filter, Args&& ...args) {
     FilteredVectorTileLayer filtered_layer(layer, filter);
     for (const pbf &feature_pbf : filtered_layer) {
         if (obsolete()) {
@@ -161,25 +161,25 @@ void TileParser::addBucketFeatures(Bucket& bucket, const VectorTileLayer& layer,
 }
 
 
-std::unique_ptr<Bucket> TileParser::createFillBucket(const VectorTileLayer& layer, const PropertyFilterExpression &filter, const StyleBucketFill &fill) {
+std::unique_ptr<Bucket> TileParser::createFillBucket(const VectorTileLayer& layer, const FilterExpression &filter, const StyleBucketFill &fill) {
     std::unique_ptr<FillBucket> bucket = std::make_unique<FillBucket>(tile.fillVertexBuffer, tile.triangleElementsBuffer, tile.lineElementsBuffer, fill);
     addBucketFeatures(bucket, layer, filter);
     return obsolete() ? nullptr : std::move(bucket);
 }
 
-std::unique_ptr<Bucket> TileParser::createLineBucket(const VectorTileLayer& layer, const PropertyFilterExpression &filter, const StyleBucketLine &line) {
+std::unique_ptr<Bucket> TileParser::createLineBucket(const VectorTileLayer& layer, const FilterExpression &filter, const StyleBucketLine &line) {
     std::unique_ptr<LineBucket> bucket = std::make_unique<LineBucket>(tile.lineVertexBuffer, tile.triangleElementsBuffer, tile.pointElementsBuffer, line);
     addBucketFeatures(bucket, layer, filter);
     return obsolete() ? nullptr : std::move(bucket);
 }
 
-std::unique_ptr<Bucket> TileParser::createIconBucket(const VectorTileLayer& layer, const PropertyFilterExpression &filter, const StyleBucketIcon &icon) {
+std::unique_ptr<Bucket> TileParser::createIconBucket(const VectorTileLayer& layer, const FilterExpression &filter, const StyleBucketIcon &icon) {
     std::unique_ptr<IconBucket> bucket = std::make_unique<IconBucket>(tile.iconVertexBuffer, icon);
     addBucketFeatures(bucket, layer, filter, *spriteAtlas);
     return obsolete() ? nullptr : std::move(bucket);
 }
 
-std::unique_ptr<Bucket> TileParser::createTextBucket(const VectorTileLayer& layer, const PropertyFilterExpression &filter, const StyleBucketText &text) {
+std::unique_ptr<Bucket> TileParser::createTextBucket(const VectorTileLayer& layer, const FilterExpression &filter, const StyleBucketText &text) {
 
     const StyleBucketText &properties = text;
 
@@ -235,9 +235,3 @@ std::unique_ptr<Bucket> TileParser::createTextBucket(const VectorTileLayer& laye
 
     return std::move(bucket);
 }
-
-
-
-
-//typedef std::pair<uint16_t, uint16_t> GlyphRange;
-//
diff --git a/src/map/vector_tile.cpp b/src/map/vector_tile.cpp
index 24f03e1a97..54a971cd87 100644
--- a/src/map/vector_tile.cpp
+++ b/src/map/vector_tile.cpp
@@ -102,7 +102,7 @@ VectorTileLayer::VectorTileLayer(pbf layer) : data(layer) {
     }
 }
 
-FilteredVectorTileLayer::FilteredVectorTileLayer(const VectorTileLayer& layer, const PropertyFilterExpression &filterExpression)
+FilteredVectorTileLayer::FilteredVectorTileLayer(const VectorTileLayer& layer, const FilterExpression &filterExpression)
     : layer(layer),
       filterExpression(filterExpression) {
 }
@@ -122,120 +122,167 @@ FilteredVectorTileLayer::iterator::iterator(const FilteredVectorTileLayer& paren
     operator++();
 }
 
-bool FilteredVectorTileLayer::iterator::matchesFilterExpression(const PropertyFilterExpression &filterExpression, const pbf &tags_pbf) {
-    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;
-    }
+//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) {}
+
+
+void VectorTileTagExtractor::setTags(const pbf &pbf) {
+    tags_ = pbf;
 }
 
+std::forward_list<Value> VectorTileTagExtractor::getValues(const std::string &key) const {
+    std::forward_list<Value> values;
 
-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()) {
+    auto field_it = layer_.key_index.find(key);
+    if (field_it != layer_.key_index.end()) {
+        auto it = values.before_begin();
         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;
+        pbf tags_pbf = tags_;
+        uint32_t tag_key, tag_val;
         while (tags_pbf) {
-            uint32_t tag_key = tags_pbf.varint();
+            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");
+                // This should not happen; otherwise the vector tile is invalid.
+                fprintf(stderr, "[WARNING] uneven number of feature tag ids\n");
+                return values;
             }
-            uint32_t tag_val = tags_pbf.varint();
+            // 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 (parent.layer.values.size() > tag_val) {
-                    const Value &value = parent.layer.values[tag_val];
-                    return filter.compare(value);
+                if (layer_.values.size() > tag_val) {
+                    it = values.emplace_after(it, layer_.values[tag_val]);
                 } else {
-                    throw std::runtime_error("feature references out of range value");
+                    fprintf(stderr, "[WARNING] feature references out of range value\n");
+                    break;
                 }
             }
         }
     }
 
-    // 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();
+    return values;
 }
 
-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;
-    }
+void VectorTileTagExtractor::setType(FilterExpression::GeometryType type) {
+    type_ = type;
 }
 
-
+FilterExpression::GeometryType VectorTileTagExtractor::getType() const {
+    return type_;
+}
 
 void FilteredVectorTileLayer::iterator::operator++() {
     valid = false;
 
-    const PropertyFilterExpression &expression = parent.filterExpression;
+    const FilterExpression &expression = parent.filterExpression;
 
     while (data.next(2)) { // feature
         feature = data.message();
         pbf feature_pbf = feature;
-        BucketType type = BucketType::None;
-
         bool matched = false;
 
         // Treat the absence of any expression filters as a match.
-        if (!expression.valid() || expression.is<std::true_type>()) {
+        if (expression.empty()) {
             matched = true;
         }
 
-        while (feature_pbf.next()) {
-            if (feature_pbf.tag == 2) { // tags
-                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.
-                    const pbf tags_pbf = feature_pbf.message();
-                    matched = matchesFilterExpression(expression, tags_pbf);
-                    if (!matched) {
-                        break; // feature_pbf loop early
+        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::Line); break;
+                        case FeatureType::Polygon:    extractor.setType(FilterExpression::GeometryType::Polygon); break;
+                        default: break;
                     }
+                } else {
+                    feature_pbf.skip();
                 }
-            } else if (feature_pbf.tag == 3) { // geometry type
-                switch (feature_pbf.varint()) {
-                    case 1 /* Point */:      type = BucketType::Icon; break;
-                    case 2 /* LineString */: type = BucketType::Line; break;
-                    case 3 /* Polygon */:    type = BucketType::Fill; break;
-                    default:                 type = BucketType::None; break;
-                }
-
-                // TODO: Parse feature type
-//                if (type != parent.bucket_desc.feature_type) {
-//                    matched = false;
-//                    break; // feature_pbf loop early
-//                }
-            } else {
-                feature_pbf.skip();
             }
+
+            matched = expression.compare(extractor);
         }
 
         if (matched) {