Line data Source code
1 : // SPDX-License-Identifier: EUPL-1.2
2 : //! Geoquery evaluation (CIM 009 4.10) — in-memory, over GeoJSON values,
3 : //! via `geo`'s DE-9IM relate (polygon holes, edge-crossing
4 : //! intersects, line/line, MultiPolygon, topological equals — the planar
5 : //! approximations this file used to carry are retired).
6 : //!
7 : //! The query geometry is parsed ONCE at construction; targets are parsed per
8 : //! evaluation. `near` is the metric minimum distance between the two
9 : //! geometries (`min_distance_m`: local equirectangular projection, so
10 : //! closest-point selection is metric and extended reference/target
11 : //! geometries measure from their true closest points); the small
12 : //! equirectangular residual vs PostGIS `ST_DWithin` on geography is the
13 : //! remaining documented ceiling (the SQL path is the metric authority).
14 : //! Known ceiling: per-call relate without a prepared edge index — a
15 : //! PreparedGeometry cache is the matcher lever when 10k subscriptions
16 : //! demand it.
17 :
18 : use antares_jsonld::Context;
19 : use antares_model::NgsiError;
20 : use geo::Relate;
21 : use serde_json::Value;
22 : use std::collections::HashMap;
23 :
24 : /// The default GeoProperty — the only one backends extract a column for.
25 : pub const LOCATION_IRI: &str = "https://uri.etsi.org/ngsi-ld/location";
26 :
27 : /// Vertices one query geometry may carry; above it the parse is refused
28 : /// (BadRequestData), so a relate never runs over an unbounded ring.
29 : pub const MAX_GEO_VERTICES: usize = 1024;
30 :
31 : /// `georel` as parsed from the request (4.10), distances in metres.
32 : #[derive(Debug, Clone)]
33 : pub enum Rel {
34 : /// `near;maxDistance==…` / `near;minDistance==…` — either bound may be absent.
35 : Near {
36 : /// `maxDistance` in metres.
37 : max: Option<f64>,
38 : /// `minDistance` in metres.
39 : min: Option<f64>,
40 : },
41 : /// `within`
42 : Within,
43 : /// `contains`
44 : Contains,
45 : /// `intersects`
46 : Intersects,
47 : /// `disjoint`
48 : Disjoint,
49 : /// `overlaps`
50 : Overlaps,
51 : /// `equals`
52 : Equals,
53 : }
54 :
55 : /// The parsed relation of a [`GeoQuery`].
56 : pub type Georel = Rel;
57 :
58 : /// A geoquery in the borrowed shape the SQL compilers take (4.10 params
59 : /// as the API already validated them).
60 : pub struct GeoSpec<'a> {
61 : /// The relation.
62 : pub rel: Rel,
63 : /// GeoJSON geometry type of the query geometry.
64 : pub geometry: &'a str,
65 : /// The query geometry's coordinates.
66 : pub coordinates: &'a Value,
67 : /// EXPANDED `geoproperty`; empty means the default (`location`).
68 : pub geoproperty_iri: &'a str,
69 : }
70 :
71 : /// A parsed 4.10 geoquery: the query geometry is parsed once at construction.
72 : #[derive(Debug, Clone)]
73 : pub struct GeoQuery {
74 : /// The relation.
75 : pub rel: Georel,
76 : /// GeoJSON geometry type of the query geometry.
77 : pub geometry: String,
78 : /// The query geometry's coordinates.
79 : pub coordinates: Value,
80 : /// The `geoproperty` term as sent (empty = default `location`).
81 : pub geoproperty: String,
82 : /// Parsed once at construction.
83 : query_geom: geo_types::Geometry<f64>,
84 : }
85 :
86 : /// Coordinate positions in a GeoJSON `coordinates` value — the leaves of its
87 : /// nested arrays, at whatever depth the geometry type nests them.
88 19574 : fn count_positions(v: &Value) -> usize {
89 19574 : match v.as_array() {
90 19574 : Some(a) if a.first().is_some_and(Value::is_array) => a.iter().map(count_positions).sum(),
91 17716 : Some(_) => 1,
92 0 : None => 0,
93 : }
94 19574 : }
95 :
96 : /// Every position of a geometry a REQUEST carries in is an edge walked once
97 : /// per candidate entity (`relate`, `min_distance_m`), so the count is bounded
98 : /// by `bounds::MAX_GEO_VERTICES` before the geometry is built. Geometries
99 : /// already stored as entity attributes are not capped — they are the targets,
100 : /// evaluated once each.
101 290 : fn check_vertex_budget(coords: &Value) -> Result<(), String> {
102 290 : let n = count_positions(coords);
103 290 : if n > MAX_GEO_VERTICES {
104 8 : return Err(format!(
105 8 : "geometry has {n} coordinate positions (maximum {})",
106 8 : MAX_GEO_VERTICES
107 8 : ));
108 282 : }
109 282 : Ok(())
110 290 : }
111 :
112 : /// 4.23: reference geometry for distance ordering (orderFrom/orderGeometry),
113 : /// also the 4.7 well-formedness check for a registration's geometries.
114 44 : pub fn parse_ref_geometry(gtype: &str, coords: &Value) -> Result<geo_types::Geometry<f64>, String> {
115 44 : check_vertex_budget(coords)?;
116 42 : parse_geometry(gtype, coords)
117 44 : }
118 :
119 : /// 4.23: metres from the reference geometry to a target GeoJSON value —
120 : /// the same metric minimum distance as `near` (4.10). None when the target
121 : /// is not a valid geometry.
122 118 : pub fn order_distance_m(refg: &geo_types::Geometry<f64>, target: &Value) -> Option<f64> {
123 96 : let (t, c) = (
124 118 : target.get("type").and_then(Value::as_str)?,
125 98 : target.get("coordinates")?,
126 : );
127 96 : let target = parse_geometry(t, c).ok()?;
128 94 : Some(min_distance_m(refg, &target))
129 118 : }
130 :
131 : /// metres per degree of latitude (WGS-84 mean)
132 : const DEG_M: f64 = 111_319.490_793;
133 :
134 : /// 4.10 near / 4.23 ordering: minimum distance in metres between two
135 : /// geometries. Both are projected into a local equirectangular plane
136 : /// (x = lon·cos(lat₀)), so closest-point selection is metric and EXTENDED
137 : /// reference and target geometries both measure from their true closest
138 : /// points; intersecting/containing pairs are distance 0.
139 : /// Known ceiling: equirectangular residual (<~0.5 % over sub-1000 km spans, no
140 : /// antimeridian wrap) — the PostGIS geography path stays the metric
141 : /// authority; geodesic segment distance if a geo TP ever demands exactness.
142 186 : fn min_distance_m(a: &geo_types::Geometry<f64>, b: &geo_types::Geometry<f64>) -> f64 {
143 : use geo::algorithm::line_measures::{Distance, Euclidean};
144 : use geo::algorithm::{BoundingRect, MapCoords};
145 186 : let mid_lat =
146 372 : |g: &geo_types::Geometry<f64>| g.bounding_rect().map(|r| (r.min().y + r.max().y) / 2.0);
147 186 : let (Some(la), Some(lb)) = (mid_lat(a), mid_lat(b)) else {
148 : // A geometry with no position has no bounding box. RFC 7946 3.1:
149 : // "GeoJSON processors MAY interpret Geometry objects with empty
150 : // `coordinates` arrays as null objects" — nothing is near a null
151 : // object, and reading the absent box as the origin made an empty
152 : // stored geometry match every `near` query in the tenant.
153 10 : return f64::INFINITY;
154 : };
155 176 : let lat0 = (la + lb) / 2.0;
156 176 : let k = lat0.to_radians().cos().max(1e-9);
157 176 : let proj =
158 392 : |g: &geo_types::Geometry<f64>| g.map_coords(|c| geo_types::Coord { x: c.x * k, y: c.y });
159 176 : Euclidean.distance(&proj(a), &proj(b)) * DEG_M
160 186 : }
161 :
162 : /// GeoJSON `{type, coordinates}` → geo_types. 4.7.2 admits a geometry only
163 : /// when it meets "the syntax and restrictions mandated by IETF RFC 7946 \[8\]
164 : /// when representing a valid Geometry of the type specified", so the shape
165 : /// and the WGS84 coordinate range are checked by the one validator the write
166 : /// path uses: a reference geometry the broker would not have stored is a 400,
167 : /// and a target that is not a geometry is a non-match.
168 692 : fn parse_geometry(gtype: &str, coords: &Value) -> Result<geo_types::Geometry<f64>, String> {
169 692 : antares_jsonld::expand::check_geometry(gtype, coords)?;
170 646 : let gj = serde_json::json!({"type": gtype, "coordinates": coords});
171 646 : let geom: geojson::Geometry =
172 646 : serde_json::from_value(gj).map_err(|e| format!("invalid GeoJSON geometry: {e}"))?;
173 646 : geo_types::Geometry::<f64>::try_from(geom).map_err(|e| format!("invalid geometry: {e}"))
174 692 : }
175 :
176 : impl GeoQuery {
177 : /// Build from query params; `None` when no georel present. Validates per
178 : /// 4.10 (georel present ⇒ geometry+coordinates required and well-formed).
179 : /// The 4.11 twin is `antares_api::temporal::TemporalQ::from_params`: the
180 : /// name is the workspace convention for one query family parsed from its
181 : /// own parameters, and the two share no code.
182 3476 : pub fn from_params(params: &HashMap<String, String>) -> Result<Option<Self>, NgsiError> {
183 3476 : let Some(georel) = params.get("georel") else {
184 3186 : if params.contains_key("geometry") || params.contains_key("coordinates") {
185 8 : return Err(NgsiError::BadRequestData(
186 8 : "geometry/coordinates given without georel".into(),
187 8 : ));
188 3178 : }
189 3178 : return Ok(None);
190 : };
191 290 : let bad = NgsiError::BadRequestData;
192 290 : let mut parts = georel.split(';');
193 290 : let base = parts.next().unwrap_or("").trim();
194 290 : let mut max = None;
195 290 : let mut min = None;
196 : // 4.10 PositiveNumber: RFC 8259 Number "excluding the 'minus' symbol
197 : // and excluding the number 0".
198 290 : let positive = |v: &str, name: &str| -> Result<f64, NgsiError> {
199 146 : let n = v
200 146 : .parse::<f64>()
201 146 : .map_err(|_| bad(format!("invalid {name} {v:?}")))?;
202 : // NaN and the infinities parse as valid f64 but are not RFC 8259
203 : // Numbers; the Greater-only comparison rejects NaN as well.
204 146 : if !n.is_finite() || n.partial_cmp(&0.0) != Some(std::cmp::Ordering::Greater) {
205 18 : return Err(bad(format!("{name} must be a positive non-zero number")));
206 128 : }
207 128 : Ok(n)
208 146 : };
209 290 : for p in parts {
210 150 : let p = p.trim();
211 : // 4.10 nearRel = nearOp andOp distance equal PositiveNumber —
212 : // exactly one distance modifier is in the grammar.
213 150 : if max.is_some() || min.is_some() {
214 4 : return Err(bad("near takes a single distance modifier".into()));
215 146 : }
216 146 : if let Some(v) = p.strip_prefix("maxDistance==") {
217 138 : max = Some(positive(v, "maxDistance")?);
218 8 : } else if let Some(v) = p.strip_prefix("minDistance==") {
219 8 : min = Some(positive(v, "minDistance")?);
220 : } else {
221 0 : return Err(bad(format!("invalid georel modifier {p:?}")));
222 : }
223 : }
224 268 : let rel = match base {
225 268 : "near" => {
226 132 : if max.is_none() && min.is_none() {
227 8 : return Err(bad("near requires maxDistance or minDistance".into()));
228 124 : }
229 124 : Georel::Near { max, min }
230 : }
231 136 : "within" => Georel::Within,
232 84 : "contains" => Georel::Contains,
233 78 : "intersects" => Georel::Intersects,
234 42 : "equals" => Georel::Equals,
235 26 : "disjoint" => Georel::Disjoint,
236 14 : "overlaps" => Georel::Overlaps,
237 10 : other => return Err(bad(format!("invalid georel {other:?}"))),
238 : };
239 250 : let geometry = params
240 250 : .get("geometry")
241 250 : .ok_or_else(|| bad("georel requires geometry".into()))?
242 250 : .clone();
243 : const GEOMETRIES: &[&str] = &[
244 : "Point",
245 : "MultiPoint",
246 : "LineString",
247 : "MultiLineString",
248 : "Polygon",
249 : "MultiPolygon",
250 : ];
251 250 : if !GEOMETRIES.contains(&geometry.as_str()) {
252 4 : return Err(bad(format!("invalid geometry {geometry:?}")));
253 246 : }
254 246 : let coords_raw = params
255 246 : .get("coordinates")
256 246 : .ok_or_else(|| bad("georel requires coordinates".into()))?;
257 246 : let coordinates: Value = serde_json::from_str(coords_raw)
258 246 : .map_err(|_| bad(format!("invalid coordinates {coords_raw:?}")))?;
259 246 : if !coordinates.is_array() {
260 0 : return Err(bad("coordinates must be a JSON array".into()));
261 246 : }
262 246 : check_vertex_budget(&coordinates).map_err(bad)?;
263 240 : let query_geom = parse_geometry(&geometry, &coordinates).map_err(bad)?;
264 210 : Ok(Some(Self {
265 210 : rel,
266 210 : geometry,
267 210 : coordinates,
268 210 : geoproperty: params.get("geoproperty").cloned().unwrap_or_default(),
269 210 : query_geom,
270 210 : }))
271 3476 : }
272 :
273 : /// The entity against the query: every instance of the target GeoProperty
274 : /// (the default `location`, or the expanded `geoproperty`) is a candidate.
275 254 : pub fn matches(&self, doc: &Value, ctx: &Context) -> bool {
276 254 : let iri = if self.geoproperty.is_empty() {
277 228 : LOCATION_IRI.to_owned()
278 : } else {
279 26 : ctx.expand_key(&self.geoproperty)
280 : };
281 254 : let Some(instances) = doc.get(&iri).and_then(Value::as_array) else {
282 64 : return false;
283 : };
284 200 : instances.iter().any(|inst| {
285 188 : inst.get("value")
286 188 : .is_some_and(|geo| self.matches_geometry(geo))
287 188 : })
288 254 : }
289 :
290 : /// The same query, in the shape `antares-sql` compiles to PostGIS.
291 : /// `geoproperty` is expanded here because the compiler only pushes down
292 : /// the DEFAULT GeoProperty — the one with an extracted column.
293 34 : pub fn to_sql_spec<'a>(&'a self, ctx: &antares_jsonld::Context) -> Option<GeoSpec<'a>> {
294 34 : let (spec, iri) = self.to_instance_spec(ctx);
295 34 : (iri == LOCATION_IRI).then_some(spec)
296 34 : }
297 :
298 : /// 5.7.4.4 S3: the prefilter shape for the temporal store — like
299 : /// `to_sql_spec` but for the per-instance `attr_instances.geo_value`
300 : /// rows, where EVERY geoproperty has extracted geometries; returns the
301 : /// spec plus the expanded IRI the windowed EXISTS binds as `attr_id`.
302 70 : pub fn to_instance_spec<'a>(&'a self, ctx: &antares_jsonld::Context) -> (GeoSpec<'a>, String) {
303 70 : let rel = self.rel.clone();
304 70 : let iri = if self.geoproperty.is_empty() {
305 60 : LOCATION_IRI.to_owned()
306 : } else {
307 10 : ctx.expand_key(&self.geoproperty)
308 : };
309 70 : (
310 70 : GeoSpec {
311 70 : rel,
312 70 : geometry: &self.geometry,
313 70 : coordinates: &self.coordinates,
314 70 : geoproperty_iri: "",
315 70 : },
316 70 : iri,
317 70 : )
318 70 : }
319 :
320 : /// One target GeoJSON value against the query. A malformed TARGET is a
321 : /// non-match (queries 400 at parse; stored data must never 500 a read).
322 318 : pub fn matches_geometry(&self, geo: &Value) -> bool {
323 314 : let (Some(t), Some(c)) = (
324 318 : geo.get("type").and_then(Value::as_str),
325 318 : geo.get("coordinates"),
326 : ) else {
327 4 : return false;
328 : };
329 314 : let Ok(target) = parse_geometry(t, c) else {
330 14 : return false;
331 : };
332 300 : let q = &self.query_geom;
333 300 : match &self.rel {
334 92 : Georel::Near { max, min } => {
335 : // 4.10: metric minimum distance between the geometries;
336 : // maxDistance = within the (closed) buffer => d <= max;
337 : // minDistance = DISJOINT with the buffer — boundary contact
338 : // is not disjoint => strictly d > min.
339 92 : let d = min_distance_m(q, &target);
340 92 : max.is_none_or(|m| d <= m) && min.is_none_or(|m| d > m)
341 : }
342 : Georel::Equals => {
343 : // literal-identical geometry is equal even when the ring is
344 : // technically invalid (self-intersecting fixtures exist in
345 : // the wild — DE-9IM is undefined there); topo-equal covers
346 : // reordered-but-equivalent rings.
347 34 : (t == self.geometry && *c == self.coordinates) || target.relate(q).is_equal_topo()
348 : }
349 60 : Georel::Within => target.relate(q).is_within(),
350 26 : Georel::Contains => target.relate(q).is_contains(),
351 50 : Georel::Intersects => target.relate(q).is_intersects(),
352 28 : Georel::Disjoint => !target.relate(q).is_intersects(),
353 10 : Georel::Overlaps => target.relate(q).is_overlaps(),
354 : }
355 318 : }
356 : }
357 :
358 : #[cfg(test)]
359 : mod tests {
360 : use super::*;
361 : use antares_jsonld::Loader;
362 : use serde_json::json;
363 :
364 50 : fn q(rel: &str, gtype: &str, coords: &str) -> GeoQuery {
365 50 : let mut params = HashMap::new();
366 50 : params.insert("georel".to_owned(), rel.to_owned());
367 50 : params.insert("geometry".to_owned(), gtype.to_owned());
368 50 : params.insert("coordinates".to_owned(), coords.to_owned());
369 50 : GeoQuery::from_params(¶ms).unwrap().unwrap()
370 50 : }
371 :
372 76 : fn geoval(gtype: &str, coords: Value) -> Value {
373 76 : json!({"type": gtype, "coordinates": coords})
374 76 : }
375 :
376 : /// 4.10 near with an EXTENDED reference geometry: "near;maxDistance==x
377 : /// (in meters)" is the distance to the reference GEOMETRY — measured
378 : /// from its closest point, not from its first coordinate.
379 : #[test]
380 2 : fn clause_4_10_near_extended_reference() {
381 : // LineString [0,60]→[10,60]; the target sits ~1 km north of the
382 : // EAST end (~557 km from the first coordinate)
383 2 : let g = q("near;maxDistance==2000", "LineString", "[[0,60],[10,60]]");
384 2 : assert!(
385 2 : g.matches_geometry(&geoval("Point", json!([10.0, 60.009]))),
386 : "distance must be measured from the closest point of the line"
387 : );
388 : // ~111 km north of the line must NOT match
389 2 : assert!(!g.matches_geometry(&geoval("Point", json!([10.0, 61.0]))));
390 2 : }
391 :
392 : /// 4.10 near: closest-point selection on an extended TARGET is METRIC —
393 : /// at lat 85 a 1°-longitude offset (~9.7 km) is closer than a
394 : /// 0.6°-latitude offset (~67 km), though planar lon/lat says otherwise.
395 : #[test]
396 2 : fn clause_4_10_near_metric_closest_point_high_latitude() {
397 2 : let target = geoval("LineString", json!([[0.0, 85.6], [1.0, 85.0]]));
398 2 : let g = q("near;maxDistance==20000", "Point", "[0,85]");
399 2 : assert!(
400 2 : g.matches_geometry(&target),
401 : "metric closest point is the lon-offset end (~9.7 km)"
402 : );
403 : // ...but it is farther than 5 km — must NOT match
404 2 : let g5 = q("near;maxDistance==5000", "Point", "[0,85]");
405 2 : assert!(!g5.matches_geometry(&target));
406 2 : }
407 :
408 : #[test]
409 2 : fn near_point() {
410 2 : let g = q("near;maxDistance==2000", "Point", "[2.29,48.85]");
411 2 : let ctx = Loader::new().core();
412 2 : let doc = json!({
413 2 : "https://uri.etsi.org/ngsi-ld/location": [
414 2 : {"type": "GeoProperty", "value": {"type": "Point", "coordinates": [2.30, 48.86]}}
415 : ]
416 : });
417 2 : assert!(g.matches(&doc, &ctx));
418 2 : let far = json!({
419 2 : "https://uri.etsi.org/ngsi-ld/location": [
420 2 : {"type": "GeoProperty", "value": {"type": "Point", "coordinates": [10.0, 50.0]}}
421 : ]
422 : });
423 2 : assert!(!g.matches(&far, &ctx));
424 2 : }
425 :
426 : #[test]
427 2 : fn within_polygon_and_holes() {
428 : // A polygon HOLE excludes points — the planar approximation
429 : // this replaces got this wrong by only reading outer rings.
430 2 : let g = q(
431 2 : "within",
432 2 : "Polygon",
433 2 : "[[[0,0],[10,0],[10,10],[0,10],[0,0]],[[4,4],[6,4],[6,6],[4,6],[4,4]]]",
434 : );
435 2 : assert!(g.matches_geometry(&geoval("Point", json!([2, 2]))));
436 2 : assert!(
437 2 : !g.matches_geometry(&geoval("Point", json!([5, 5]))),
438 : "point in the hole is NOT within"
439 : );
440 2 : }
441 :
442 : #[test]
443 2 : fn edge_crossing_intersects_and_line_line() {
444 : // two lines crossing mid-edge share no vertex — the old
445 : // shared-point approximation missed this
446 2 : let g = q("intersects", "LineString", "[[0,0],[10,10]]");
447 2 : assert!(g.matches_geometry(&geoval("LineString", json!([[0, 10], [10, 0]]))));
448 2 : assert!(!g.matches_geometry(&geoval("LineString", json!([[20, 20], [30, 30]]))));
449 : // polygon edge crossing without contained vertices
450 2 : let g = q("intersects", "Polygon", "[[[0,0],[4,0],[4,4],[0,4],[0,0]]]");
451 2 : assert!(g.matches_geometry(&geoval(
452 2 : "Polygon",
453 2 : json!([[[-1, 1], [5, 1], [5, 3], [-1, 3], [-1, 1]]])
454 2 : )));
455 2 : }
456 :
457 : #[test]
458 2 : fn multipolygon_and_topological_equals() {
459 2 : let g = q(
460 2 : "within",
461 2 : "MultiPolygon",
462 2 : "[[[[0,0],[4,0],[4,4],[0,4],[0,0]]],[[[10,10],[14,10],[14,14],[10,14],[10,10]]]]",
463 : );
464 2 : assert!(g.matches_geometry(&geoval("Point", json!([12, 12]))));
465 2 : assert!(!g.matches_geometry(&geoval("Point", json!([7, 7]))));
466 : // equals is topological, not literal-coordinate order
467 2 : let g = q("equals", "Polygon", "[[[0,0],[4,0],[4,4],[0,4],[0,0]]]");
468 2 : assert!(g.matches_geometry(&geoval(
469 2 : "Polygon",
470 2 : json!([[[4, 0], [4, 4], [0, 4], [0, 0], [4, 0]]])
471 2 : )));
472 2 : }
473 :
474 : #[test]
475 2 : fn malformed_rings_are_400_on_query_and_nonmatch_on_target() {
476 2 : let mut params = HashMap::new();
477 2 : params.insert("georel".to_owned(), "within".to_owned());
478 2 : params.insert("geometry".to_owned(), "Polygon".to_owned());
479 2 : params.insert("coordinates".to_owned(), "[[[0,0],[4,0],[4,4]]]".to_owned());
480 2 : assert!(
481 2 : GeoQuery::from_params(¶ms).is_err(),
482 : "3-position ring must 400"
483 : );
484 2 : params.insert(
485 2 : "coordinates".to_owned(),
486 2 : "[[[0,0],[4,0],[4,4],[0,4]]]".to_owned(),
487 : );
488 2 : assert!(
489 2 : GeoQuery::from_params(¶ms).is_err(),
490 : "unclosed ring must 400"
491 : );
492 : // stored (target) data malformed: non-match, never an error
493 2 : let g = q("within", "Polygon", "[[[0,0],[4,0],[4,4],[0,4],[0,0]]]");
494 2 : assert!(!g.matches_geometry(&geoval("Polygon", json!([[[0, 0], [4, 0]]]))));
495 2 : }
496 :
497 : #[test]
498 2 : fn rejects_bad_params() {
499 2 : let mut params = HashMap::new();
500 2 : params.insert("georel".to_owned(), "nearish".to_owned());
501 2 : assert!(GeoQuery::from_params(¶ms).is_err());
502 2 : }
503 :
504 : /// 4.10 leaves the size of the reference geometry open, and a POST query
505 : /// carries its coordinates in the body, not the URI. Every position is an
506 : /// edge `relate` walks once per candidate entity, so an over-cap geometry
507 : /// is BadRequestData and NO entity is evaluated.
508 : #[test]
509 2 : fn oversized_query_geometry_is_rejected_before_any_entity_is_scanned() {
510 2 : let cap = MAX_GEO_VERTICES;
511 : // a closed ring of n positions on the unit circle
512 4 : let ring = |n: usize| {
513 4 : let pts: Vec<String> = (0..n - 1)
514 4094 : .map(|i| {
515 4094 : let a = std::f64::consts::TAU * i as f64 / (n - 1) as f64;
516 4094 : format!("[{},{}]", a.cos(), a.sin())
517 4094 : })
518 4 : .collect();
519 4 : format!("[[{},{}]]", pts.join(","), pts[0])
520 4 : };
521 2 : let ctx = Loader::new().core();
522 2 : let corpus: Vec<Value> = (0..8)
523 16 : .map(|i| {
524 16 : json!({"https://uri.etsi.org/ngsi-ld/location": [
525 16 : {"type": "GeoProperty",
526 16 : "value": {"type": "Point", "coordinates": [i as f64 / 1e3, 0.0]}}
527 : ]})
528 16 : })
529 2 : .collect();
530 : // counts the entities the query actually touches — it can only run
531 : // once a geometry was accepted
532 2 : let scanned = std::cell::Cell::new(0usize);
533 4 : let scan = |params: &HashMap<String, String>| -> Result<(), NgsiError> {
534 4 : let g = GeoQuery::from_params(params)?.expect("georel present");
535 16 : for doc in &corpus {
536 16 : scanned.set(scanned.get() + 1);
537 16 : let _ = g.matches(doc, &ctx);
538 16 : }
539 2 : Ok(())
540 4 : };
541 2 : let mut params = HashMap::new();
542 2 : params.insert("georel".to_owned(), "within".to_owned());
543 2 : params.insert("geometry".to_owned(), "Polygon".to_owned());
544 2 : params.insert("coordinates".to_owned(), ring(cap + 1));
545 2 : assert!(
546 2 : matches!(scan(¶ms), Err(NgsiError::BadRequestData(_))),
547 : "over the cap must be rejected as BadRequestData"
548 : );
549 2 : assert_eq!(
550 2 : scanned.get(),
551 : 0,
552 : "the rejection lands before any entity is evaluated"
553 : );
554 : // …and the ceiling itself still parses — which also proves the
555 : // counter above is not vacuous
556 2 : params.insert("coordinates".to_owned(), ring(cap));
557 2 : assert!(scan(¶ms).is_ok(), "exactly at the cap is accepted");
558 2 : assert_eq!(scanned.get(), corpus.len());
559 : // a MultiPoint spends the same budget across its members
560 2 : params.insert("georel".to_owned(), "intersects".to_owned());
561 2 : params.insert("geometry".to_owned(), "MultiPoint".to_owned());
562 2 : let pts: Vec<String> = (0..=cap)
563 2050 : .map(|i| format!("[{},0]", i as f64 / 1e6))
564 2 : .collect();
565 2 : params.insert("coordinates".to_owned(), format!("[{}]", pts.join(",")));
566 2 : assert!(
567 2 : GeoQuery::from_params(¶ms).is_err(),
568 : "the cap counts leaves, not rings"
569 : );
570 2 : }
571 :
572 : /// A MultiPolygon nests its positions three levels down, so a length
573 : /// check on the top-level array sees a couple of hundred members and
574 : /// passes while the geometry spends more than the whole budget. The cap
575 : /// counts leaves, at whatever depth the geometry type puts them.
576 : #[test]
577 2 : fn nested_multipolygon_cannot_smuggle_vertices_past_the_cap() {
578 2 : let cap = MAX_GEO_VERTICES;
579 : // the squares march along a meridian band, so 205 of them still sit
580 : // inside the WGS84 longitude range a reference geometry must respect
581 410 : let square = |i: usize| {
582 410 : let x = i as f64 * 0.7 - 100.0;
583 410 : json!([[[x, 0.0], [x + 0.5, 0.0], [x + 0.5, 0.5], [x, 0.5], [x, 0.0]]])
584 410 : };
585 2 : let members = cap / 5 + 1; // 5 positions per member => one over the cap
586 2 : let coords: Vec<Value> = (0..members).map(square).collect();
587 2 : assert!(
588 2 : members <= cap,
589 : "a top-level length check would see {members} members and pass"
590 : );
591 2 : let mut params = HashMap::new();
592 2 : params.insert("georel".to_owned(), "intersects".to_owned());
593 2 : params.insert("geometry".to_owned(), "MultiPolygon".to_owned());
594 2 : params.insert("coordinates".to_owned(), json!(coords).to_string());
595 2 : assert!(
596 0 : matches!(
597 2 : GeoQuery::from_params(¶ms),
598 : Err(NgsiError::BadRequestData(_))
599 : ),
600 : "nested positions count against the same budget"
601 : );
602 : // one member fewer is inside the budget and still parses
603 2 : params.insert(
604 2 : "coordinates".to_owned(),
605 2 : json!(coords[..members - 1]).to_string(),
606 : );
607 2 : assert!(GeoQuery::from_params(¶ms).is_ok());
608 2 : }
609 :
610 : /// 4.23 ordering: the reference geometry is measured against every result
611 : /// row, so it carries the same vertex ceiling as a geoquery geometry.
612 : #[test]
613 2 : fn ordering_reference_geometry_carries_the_same_vertex_cap() {
614 2 : let n = MAX_GEO_VERTICES + 1;
615 2050 : let pts: Vec<Value> = (0..n).map(|i| json!([i as f64 / 1e6, 0.0])).collect();
616 2 : assert!(
617 2 : parse_ref_geometry("MultiPoint", &json!(pts)).is_err(),
618 : "an oversized ordering reference must be rejected"
619 : );
620 2 : assert!(parse_ref_geometry("Point", &json!([1.0, 2.0])).is_ok());
621 2 : }
622 :
623 : /// 4.10 PositiveNumber is an RFC 8259 Number — "inf"/"Infinity" and an
624 : /// overflowing literal are not numbers, however happily f64 parses them.
625 : #[test]
626 2 : fn a_non_finite_distance_is_not_a_positive_number() {
627 10 : for rel in [
628 2 : "near;maxDistance==inf",
629 2 : "near;maxDistance==infinity",
630 2 : "near;minDistance==inf",
631 2 : "near;maxDistance==1e400",
632 2 : "near;maxDistance==NaN",
633 2 : ] {
634 10 : let mut params = HashMap::new();
635 10 : params.insert("georel".to_owned(), rel.to_owned());
636 10 : params.insert("geometry".to_owned(), "Point".to_owned());
637 10 : params.insert("coordinates".to_owned(), "[8,40]".to_owned());
638 10 : assert!(
639 10 : GeoQuery::from_params(¶ms).is_err(),
640 : "{rel} must be rejected"
641 : );
642 : }
643 2 : }
644 :
645 : /// Degenerate but well-formed GeoJSON (empty rings, empty coordinate
646 : /// arrays) reaches the predicates from both sides — a query 400s or
647 : /// evaluates, a stored target is a non-match. Neither may panic.
648 : #[test]
649 2 : fn degenerate_geometries_never_panic() {
650 10 : for gtype in [
651 2 : "Point",
652 2 : "LineString",
653 2 : "Polygon",
654 2 : "MultiPoint",
655 2 : "MultiPolygon",
656 2 : ] {
657 10 : let mut params = HashMap::new();
658 10 : params.insert("georel".to_owned(), "intersects".to_owned());
659 10 : params.insert("geometry".to_owned(), gtype.to_owned());
660 10 : params.insert("coordinates".to_owned(), "[]".to_owned());
661 10 : if let Ok(Some(g)) = GeoQuery::from_params(¶ms) {
662 6 : let _ = g.matches_geometry(&geoval("Point", json!([1, 1])));
663 6 : let _ = g.matches_geometry(&geoval("Polygon", json!([])));
664 6 : }
665 : }
666 : // degenerate TARGETS against an ordinary query
667 2 : let g = q("within", "Polygon", "[[[0,0],[4,0],[4,4],[0,4],[0,0]]]");
668 12 : for target in [
669 2 : geoval("Polygon", json!([])),
670 2 : geoval("LineString", json!([])),
671 2 : geoval("MultiPoint", json!([])),
672 2 : geoval("Point", json!([])),
673 2 : json!({"type": "Point"}),
674 2 : json!("not a geometry"),
675 12 : ] {
676 12 : let _ = g.matches_geometry(&target);
677 12 : }
678 2 : }
679 :
680 : /// 4.23: distance ordering skips rows whose ordering value is not a
681 : /// geometry rather than failing the query.
682 : #[test]
683 2 : fn order_distance_is_none_for_a_non_geometry() {
684 2 : let refg = parse_ref_geometry("Point", &json!([0.0, 0.0])).expect("ref");
685 2 : assert!(order_distance_m(&refg, &json!({"type": "Point"})).is_none());
686 2 : assert!(order_distance_m(&refg, &json!({"coordinates": [1, 1]})).is_none());
687 2 : assert!(order_distance_m(&refg, &json!(42)).is_none());
688 2 : assert!(
689 2 : order_distance_m(&refg, &geoval("Polygon", json!([[[0, 0], [1, 0]]]))).is_none(),
690 : "a malformed ring is not a distance"
691 : );
692 2 : let d = order_distance_m(&refg, &geoval("Point", json!([0.0, 1.0]))).expect("distance");
693 2 : assert!((d - DEG_M).abs() < 1.0, "one degree of latitude, got {d}");
694 2 : }
695 :
696 : /// The PostGIS push-down only owns the DEFAULT GeoProperty column: a
697 : /// geoquery on any other geoproperty must NOT produce a SQL spec (it is
698 : /// evaluated in memory instead), while the per-instance spec carries the
699 : /// expanded IRI for every geoproperty.
700 : #[test]
701 2 : fn only_the_default_geoproperty_is_pushed_down_to_sql() {
702 2 : let ctx = Loader::new().core();
703 2 : let mut params = HashMap::new();
704 2 : params.insert("georel".to_owned(), "within".to_owned());
705 2 : params.insert("geometry".to_owned(), "Polygon".to_owned());
706 2 : params.insert(
707 2 : "coordinates".to_owned(),
708 2 : "[[[0,0],[4,0],[4,4],[0,4],[0,0]]]".to_owned(),
709 : );
710 2 : let g = GeoQuery::from_params(¶ms)
711 2 : .expect("parse")
712 2 : .expect("some");
713 2 : assert!(
714 2 : g.to_sql_spec(&ctx).is_some(),
715 : "default location pushes down"
716 : );
717 2 : assert_eq!(g.to_instance_spec(&ctx).1, LOCATION_IRI);
718 :
719 2 : params.insert("geoproperty".to_owned(), "operationSpace".to_owned());
720 2 : let g = GeoQuery::from_params(¶ms)
721 2 : .expect("parse")
722 2 : .expect("some");
723 2 : assert!(
724 2 : g.to_sql_spec(&ctx).is_none(),
725 : "a non-default geoproperty has no extracted column — no push-down"
726 : );
727 2 : let (_, iri) = g.to_instance_spec(&ctx);
728 2 : assert_ne!(iri, LOCATION_IRI);
729 2 : assert!(
730 2 : iri.starts_with("https://uri.etsi.org/ngsi-ld/"),
731 : "expanded, got {iri}"
732 : );
733 2 : }
734 :
735 : /// A stored TARGET that is not a valid geometry is a non-match, not a
736 : /// panic and not a match: reads over data written before the check must
737 : /// still answer.
738 : #[test]
739 2 : fn a_malformed_target_geometry_is_a_nonmatch() {
740 2 : let g = q("intersects", "Polygon", "[[[0,0],[2,0],[2,2],[0,2],[0,0]]]");
741 8 : for target in [
742 2 : geoval("Point", json!([1, 999])),
743 2 : geoval("Point", json!([1])),
744 2 : geoval("Polygon", json!([[[0, 0], [1, 0], [1, 1]]])),
745 2 : geoval("GeometryCollection", json!([])),
746 2 : ] {
747 8 : assert!(!g.matches_geometry(&target), "{target}");
748 : }
749 2 : }
750 :
751 : /// RFC 7946 3.1 puts no minimum on a multi-geometry, so an empty one is a
752 : /// geometry and reaches both sides of every relation. Neither the DE-9IM
753 : /// relate nor the metric distance may panic on it: an empty geometry
754 : /// touches nothing, so every relation but `disjoint` is a non-match.
755 : #[test]
756 2 : fn an_empty_geometry_relates_without_panicking() {
757 2 : let empties = [
758 2 : geoval("MultiPoint", json!([])),
759 2 : geoval("MultiLineString", json!([])),
760 2 : geoval("Polygon", json!([])),
761 2 : geoval("MultiPolygon", json!([])),
762 2 : ];
763 12 : for rel in [
764 2 : "intersects",
765 2 : "within",
766 2 : "contains",
767 2 : "overlaps",
768 2 : "equals",
769 2 : "near;maxDistance==1000000",
770 2 : ] {
771 12 : let g = q(rel, "Polygon", "[[[0,0],[2,0],[2,2],[0,2],[0,0]]]");
772 48 : for target in &empties {
773 48 : assert!(!g.matches_geometry(target), "{rel} vs {target}");
774 : }
775 : // and with the empty geometry as the REFERENCE side
776 12 : let g = q(rel, "MultiPoint", "[]");
777 12 : assert!(
778 12 : !g.matches_geometry(&geoval("Point", json!([1.0, 1.0]))),
779 : "{rel} with an empty reference"
780 : );
781 : }
782 : // disjoint is the complement: nothing intersects an empty geometry
783 2 : let g = q("disjoint", "Polygon", "[[[0,0],[2,0],[2,2],[0,2],[0,0]]]");
784 8 : for target in &empties {
785 8 : assert!(g.matches_geometry(target), "disjoint vs {target}");
786 : }
787 2 : }
788 : }
789 :
790 : #[cfg(test)]
791 : mod clause_4_10_grammar {
792 : use super::*;
793 : use antares_jsonld::Loader;
794 : use serde_json::json;
795 :
796 16 : fn params(rel: &str) -> HashMap<String, String> {
797 16 : let mut p = HashMap::new();
798 16 : p.insert("georel".to_owned(), rel.to_owned());
799 16 : p.insert("geometry".to_owned(), "Point".to_owned());
800 16 : p.insert("coordinates".to_owned(), "[8,40]".to_owned());
801 16 : p
802 16 : }
803 :
804 : /// 4.10 PositiveNumber: "excluding the 'minus' symbol and excluding the
805 : /// number 0" — a zero or negative distance is a grammar violation, 400.
806 : #[test]
807 2 : fn distance_must_be_a_positive_nonzero_number() {
808 8 : for rel in [
809 2 : "near;maxDistance==0",
810 2 : "near;maxDistance==-100",
811 2 : "near;minDistance==0",
812 2 : "near;minDistance==-0.5",
813 2 : ] {
814 8 : assert!(
815 8 : GeoQuery::from_params(¶ms(rel)).is_err(),
816 : "{rel} must be rejected"
817 : );
818 : }
819 : // a positive number stays valid
820 2 : assert!(GeoQuery::from_params(¶ms("near;maxDistance==0.5")).is_ok());
821 2 : }
822 :
823 : /// 4.10 nearRel = nearOp andOp distance equal PositiveNumber — exactly
824 : /// ONE distance modifier; a second (or duplicate) one is not in the
825 : /// grammar.
826 : #[test]
827 2 : fn near_takes_exactly_one_distance_modifier() {
828 2 : assert!(GeoQuery::from_params(¶ms("near;maxDistance==5;minDistance==1")).is_err());
829 2 : assert!(GeoQuery::from_params(¶ms("near;maxDistance==5;maxDistance==7")).is_err());
830 2 : }
831 :
832 : /// 4.10: "Entities which do not convey the target GeoProperty of the
833 : /// query shall be considered as non-matching."
834 : #[test]
835 2 : fn missing_target_geoproperty_is_a_nonmatch() {
836 2 : let ctx = Loader::new().core();
837 2 : let g = GeoQuery::from_params(¶ms("near;maxDistance==2000"))
838 2 : .unwrap()
839 2 : .unwrap();
840 2 : let doc = json!({
841 2 : "https://uri.etsi.org/ngsi-ld/default-context/temperature": [
842 2 : {"type": "Property", "value": 20}
843 : ]
844 : });
845 2 : assert!(!g.matches(&doc, &ctx), "no location => non-matching");
846 2 : }
847 :
848 : /// 4.7.1 through 4.10: `coordinates` expresses "the reference geometry",
849 : /// and a reference geometry is a GeoJSON Geometry — "meeting the syntax
850 : /// and restrictions mandated by IETF RFC 7946 \[8\] when representing a
851 : /// valid Geometry of the type specified" (4.7.2). A geometry outside the
852 : /// WGS84 range the format fixes is not one, and reaching PostGIS it is a
853 : /// `::geography` cast that errors rather than a 400.
854 : #[test]
855 2 : fn a_reference_geometry_is_a_valid_rfc_7946_geometry() {
856 36 : let ask = |gtype: &str, coords: &str| {
857 36 : let mut p = HashMap::new();
858 36 : p.insert("georel".to_owned(), "near;maxDistance==100".to_owned());
859 36 : p.insert("geometry".to_owned(), gtype.to_owned());
860 36 : p.insert("coordinates".to_owned(), coords.to_owned());
861 36 : GeoQuery::from_params(&p)
862 36 : };
863 22 : for (why, gtype, coords) in [
864 2 : ("latitude past the pole", "Point", "[0, 999]"),
865 2 : ("longitude past the antimeridian", "Point", "[181, 0]"),
866 2 : ("latitude just past the pole", "Point", "[0, -90.5]"),
867 2 : ("one-element position", "Point", "[1]"),
868 2 : ("position of strings", "Point", r#"["1", "2"]"#),
869 2 : ("nested where a position belongs", "Point", "[[1, 2]]"),
870 2 : ("one-position LineString", "LineString", "[[1, 2]]"),
871 2 : ("open ring", "Polygon", "[[[0,0],[1,0],[1,1]]]"),
872 2 : ("short ring", "Polygon", "[[[0,0],[1,0],[0,0]]]"),
873 2 : (
874 2 : "ring out of range",
875 2 : "Polygon",
876 2 : "[[[0,0],[1,0],[1,91],[0,0]]]",
877 2 : ),
878 2 : (
879 2 : "MultiPolygon nested one level short",
880 2 : "MultiPolygon",
881 2 : "[[[0,0],[1,0],[1,1],[0,0]]]",
882 2 : ),
883 2 : ] {
884 22 : let err = ask(gtype, coords).expect_err(why);
885 22 : assert!(
886 22 : matches!(err, NgsiError::BadRequestData(_)),
887 : "{why}: {err:?}"
888 : );
889 : }
890 : // the shapes RFC 7946 allows stay valid, edges of the range included
891 14 : for (gtype, coords) in [
892 2 : ("Point", "[17.1, 48.7]"),
893 2 : ("Point", "[-180, -90]"),
894 2 : ("Point", "[180, 90]"),
895 2 : ("Point", "[1, 2, 300]"),
896 2 : ("LineString", "[[1,2],[3,4]]"),
897 2 : ("Polygon", "[[[0,0],[1,0],[1,1],[0,0]]]"),
898 2 : ("MultiPolygon", "[[[[0,0],[1,0],[1,1],[0,0]]]]"),
899 2 : ] {
900 14 : assert!(ask(gtype, coords).is_ok(), "{gtype} {coords}");
901 : }
902 2 : }
903 : }
|
