Line data Source code
1 : // SPDX-License-Identifier: EUPL-1.2
2 : //! NGSI-LD Query Language (CIM 009 clause 4.9): one AST, two backends.
3 : //!
4 : //! [`parse_q`] turns a `q=` expression into a [`QNode`]; [`eval`] evaluates
5 : //! it against an in-memory expanded entity (the broker's query path and its
6 : //! subscription matcher share this evaluator), [`sql`] lowers it to a
7 : //! bind-parameter jsonpath predicate for Postgres. The AST is `Serialize`
8 : //! and `Clone`, and renders back to `q=` syntax through `Display`, so a
9 : //! gateway can inspect or rewrite a query (strip an attribute, AND in an
10 : //! authorization predicate) and forward it with the broker's own semantics.
11 : //!
12 : #![doc = include_str!("../README.md")]
13 : // every surface calls into this crate on a request path, where a
14 : // panic is a remote DoS. Outside tests it may not unwrap, expect, panic,
15 : // index out of bounds or overflow.
16 : #![cfg_attr(
17 : not(test),
18 : deny(
19 : clippy::unwrap_used,
20 : clippy::expect_used,
21 : clippy::panic,
22 : clippy::indexing_slicing,
23 : clippy::arithmetic_side_effects
24 : )
25 : )]
26 : #![deny(missing_docs)]
27 : #![cfg_attr(test, allow(clippy::unwrap_used))]
28 :
29 : pub mod eval;
30 : pub mod geo;
31 : pub mod regex;
32 : mod render;
33 : pub mod scope;
34 : pub mod sql;
35 :
36 : use antares_model::NgsiError;
37 :
38 : /// The pinned core `@context`, parsed once for every test of the crate:
39 : /// under Miri one parse takes minutes.
40 : #[cfg(test)]
41 346 : pub(crate) fn test_core() -> std::sync::Arc<antares_jsonld::Context> {
42 : static CORE: std::sync::LazyLock<std::sync::Arc<antares_jsonld::Context>> =
43 2 : std::sync::LazyLock::new(|| std::sync::Arc::new(antares_jsonld::core_context()));
44 346 : std::sync::Arc::clone(&CORE)
45 346 : }
46 :
47 : /// Entity Type Selection Language (4.17) match against expanded type IRIs:
48 : /// `,`/`|` = OR of alternatives, `(a;b)` = AND within one alternative.
49 1210 : pub fn type_selection_matches(sel: &str, types: &[&str], ctx: &antares_jsonld::Context) -> bool {
50 1264 : sel.split([',', '|']).any(|alt| {
51 1264 : alt.trim()
52 1264 : .trim_start_matches('(')
53 1264 : .trim_end_matches(')')
54 1264 : .split(';')
55 1300 : .all(|t| types.contains(&ctx.expand_key(t.trim()).as_str()))
56 1264 : })
57 1210 : }
58 :
59 : /// The 4.17 grammar of a type selection: `EntityTypes = OrEntityType
60 : /// *(orOp OrEntityType)`, `OrEntityType = "(" EntityType *(";" EntityType)
61 : /// ")" / EntityType`, an EntityType never empty.
62 3792 : pub fn check_type_selection(sel: &str) -> Result<(), NgsiError> {
63 3792 : let bad = || NgsiError::BadRequestData(format!("type {sel:?} violates the 4.17 grammar"));
64 4290 : for alt in sel.split([',', '|']).map(str::trim) {
65 4290 : let inner = match alt.strip_prefix('(') {
66 34 : Some(rest) => rest.strip_suffix(')').ok_or_else(bad)?,
67 4256 : None if alt.contains(';') => return Err(bad()),
68 4248 : None => alt,
69 : };
70 4280 : if inner
71 4280 : .split(';')
72 4306 : .any(|t| t.trim().is_empty() || t.contains(['(', ')']))
73 : {
74 18 : return Err(bad());
75 4262 : }
76 : }
77 3764 : Ok(())
78 3792 : }
79 :
80 : /// RFC 3986 percent-decoding of a query value (`q`, `scopeQ` in a
81 : /// subscription body may arrive encoded, 4.9).
82 32825 : pub fn percent_decode(input: &[u8]) -> String {
83 32825 : let mut out = Vec::with_capacity(input.len());
84 32825 : let mut rest = input;
85 429226 : while let Some((&b, tail)) = rest.split_first() {
86 : // from_str_radix accepts a leading sign, so "%+1" would decode as
87 : // 0x01. RFC 3986 clause 2.1 admits two hex digits and nothing else.
88 396401 : let decoded = (b == b'%')
89 396401 : .then(|| tail.get(..2))
90 396401 : .flatten()
91 396401 : .filter(|h| h.iter().all(u8::is_ascii_hexdigit))
92 396401 : .and_then(|h| std::str::from_utf8(h).ok())
93 396401 : .and_then(|h| u8::from_str_radix(h, 16).ok());
94 396401 : match decoded {
95 74211 : Some(v) => {
96 74211 : out.push(v);
97 74211 : rest = tail.get(2..).unwrap_or_default();
98 74211 : }
99 322190 : None => {
100 322190 : out.push(b);
101 322190 : rest = tail;
102 322190 : }
103 : }
104 : }
105 32825 : String::from_utf8_lossy(&out).into_owned()
106 32825 : }
107 :
108 : /// One parsed 4.9 query expression.
109 : #[derive(Debug, Clone, PartialEq, serde::Serialize)]
110 : pub enum QNode {
111 : /// `a;b` — every operand must hold.
112 : And(Vec<QNode>),
113 : /// `a|b` — any operand holds.
114 : Or(Vec<QNode>),
115 : /// `path op value` — one comparison term.
116 : Cmp {
117 : /// The attribute (path) the term targets.
118 : path: QPath,
119 : /// The comparison operator.
120 : op: CmpOp,
121 : /// The literal compared against.
122 : value: QValue,
123 : },
124 : /// Bare attribute path = existence check (`q=temperature`).
125 : Exists {
126 : /// The attribute (path) whose presence is tested.
127 : path: QPath,
128 : /// `!path` — the attribute must be absent.
129 : negated: bool,
130 : },
131 : }
132 :
133 : /// 4.9 `Attribute = LinkedEntityRelation` — zero or more `attr{[T[,T]:]…}`
134 : /// hops (EXAMPLE 13/14), then `ValuePath = DottedPath *1([DottedPath])`:
135 : /// a dotted path plus an optional single trailing bracket that is either a
136 : /// compound-value member path (EXAMPLE 9/10/11) or a language filter
137 : /// (`[en]` / `[*]`, Equal/Unequal languageMap semantics).
138 : #[derive(Debug, Clone, PartialEq, serde::Serialize)]
139 : pub struct QPath {
140 : /// Linked-entity hops (`attr{…}`) preceding the path, outermost first.
141 : pub links: Vec<Link>,
142 : /// The dotted attribute path (terms, expanded at evaluation time).
143 : pub path: Vec<String>,
144 : /// The optional trailing `[…]`: a compound-value member path, or a
145 : /// language filter (`[en]`, `[*]`).
146 : pub bracket: Option<Vec<String>>,
147 : }
148 :
149 : /// One `attr{…}` linked-entity hop with its optional EntityType hints.
150 : #[derive(Debug, Clone, PartialEq, serde::Serialize)]
151 : pub struct Link {
152 : /// The Relationship followed.
153 : pub attr: String,
154 : /// EntityType hints (`attr{T1,T2:…}`), empty when none.
155 : pub types: Vec<String>,
156 : }
157 :
158 : impl QPath {
159 : /// Plain dotted path (the pre-4.9-extension shape).
160 5372 : pub fn dotted(path: Vec<String>) -> Self {
161 5372 : Self {
162 5372 : links: Vec::new(),
163 5372 : path,
164 5372 : bracket: None,
165 5372 : }
166 5372 : }
167 :
168 : /// The top-level Attribute name this path filters on.
169 27640 : pub fn top(&self) -> Option<&str> {
170 27640 : self.links
171 27640 : .first()
172 27640 : .map(|l| l.attr.as_str())
173 27640 : .or_else(|| self.path.first().map(String::as_str))
174 27640 : }
175 : }
176 :
177 : impl QNode {
178 : /// Every top-level attribute name this expression references, in source
179 : /// order.
180 : ///
181 : /// Purge (5.6.21.4 b/c) qualifies an `attrs` list or a `q` only when it
182 : /// includes "at least one non-system Attribute", so the caller needs the
183 : /// referenced names rather than just "is there a q".
184 1166 : pub fn attribute_paths(&self) -> Vec<&str> {
185 1166 : let mut out = Vec::new();
186 1166 : self.collect_paths(&mut out);
187 1166 : out
188 1166 : }
189 :
190 : /// True when any referenced Attribute path uses a `attr{…}` linked-entity
191 : /// hop (4.9 LinkedEntityRelation). Purge (5.6.21.4) must reject filter
192 : /// conditions that include Linked Entity attributes.
193 18700 : pub fn has_linked_paths(&self) -> bool {
194 18700 : match self {
195 1860 : QNode::And(ns) | QNode::Or(ns) => ns.iter().any(Self::has_linked_paths),
196 16840 : QNode::Cmp { path, .. } | QNode::Exists { path, .. } => !path.links.is_empty(),
197 : }
198 18700 : }
199 :
200 : /// Deepest chain of `attr{…}` hops any referenced path uses — the number
201 : /// of Linked Entity levels the query needs (5.7.2.4: must not exceed
202 : /// joinLevel).
203 14380 : pub fn max_link_depth(&self) -> usize {
204 14380 : match self {
205 946 : QNode::And(ns) | QNode::Or(ns) => {
206 1014 : ns.iter().map(Self::max_link_depth).max().unwrap_or(0)
207 : }
208 13366 : QNode::Cmp { path, .. } | QNode::Exists { path, .. } => path.links.len(),
209 : }
210 14380 : }
211 :
212 22010 : fn collect_paths<'a>(&'a self, out: &mut Vec<&'a str>) {
213 22010 : match self {
214 120 : QNode::And(ns) | QNode::Or(ns) => {
215 20844 : for n in ns {
216 20844 : n.collect_paths(out);
217 20844 : }
218 : }
219 21840 : QNode::Cmp { path, .. } | QNode::Exists { path, .. } => out.extend(path.top()),
220 : }
221 22010 : }
222 : }
223 :
224 : /// System-generated members that never count as a "non-system Attribute"
225 : /// (5.6.21.4). `id`/`type`/`scope` are Entity members, the timestamps are the
226 : /// system temporal attributes of 6.3.11.
227 : pub const SYSTEM_ATTRS: &[&str] = &[
228 : "id",
229 : "type",
230 : "scope",
231 : "createdAt",
232 : "modifiedAt",
233 : "expiresAt",
234 : "deletedAt",
235 : "instanceId",
236 : ];
237 :
238 : /// True when `name` is an ordinary (non-system) Attribute name.
239 1068 : pub fn is_non_system_attr(name: &str) -> bool {
240 1068 : !SYSTEM_ATTRS.contains(&name)
241 1068 : }
242 :
243 : /// The 4.9 comparison operators.
244 : #[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
245 : pub enum CmpOp {
246 : /// `==`
247 : Eq,
248 : /// `!=`
249 : Ne,
250 : /// `>`
251 : Gt,
252 : /// `>=`
253 : Ge,
254 : /// `<`
255 : Lt,
256 : /// `<=`
257 : Le,
258 : /// `~=` (patternOp)
259 : Pattern,
260 : /// `!~=` (notPatternOp)
261 : NotPattern,
262 : }
263 :
264 : /// A query term literal.
265 : #[derive(Debug, Clone, PartialEq, serde::Serialize)]
266 : pub enum QValue {
267 : /// A string (quoted, or an unquoted non-numeric token such as a date).
268 : Str(String),
269 : /// A number.
270 : Num(f64),
271 : /// `true` / `false`.
272 : Bool(bool),
273 : /// 4.9 `ValueList = Value 1*(, Value)` — scalars only, `==`/`!=` only.
274 : List(Vec<QValue>),
275 : /// 4.9 `Range = ComparableValue dots ComparableValue` — `==`/`!=` only.
276 : /// Endpoints are the same scalar variant (Num..Num or Str..Str; dates and
277 : /// times ride in Str and order correctly because 4.6.3 pins them to
278 : /// fixed-width UTC forms).
279 : Range(Box<QValue>, Box<QValue>),
280 : }
281 :
282 : /// Longest `q=` accepted, before parsing. The URI cap is 8 KiB but a POST
283 : /// query body carries `q` too, where the only other ceiling is the 4 MiB body
284 : /// limit — so the string needs its own bound at the one entry point.
285 : pub const MAX_Q_BYTES: usize = 4096;
286 :
287 : /// Nesting depth ceiling. `(` costs three stack frames (`or_expr` → `and_expr`
288 : /// → `term`), and a Rust stack overflow is a guard-page abort, NOT a catchable
289 : /// panic — no tower layer can contain it, so the parser must refuse before it
290 : /// recurses rather than be rescued afterwards. 64 is far past any real query
291 : /// and far below the ~2 MiB tokio worker stack.
292 : pub const MAX_Q_DEPTH: usize = 64;
293 :
294 : /// AST size cap — checked after parsing, which is safe once depth and
295 : /// length are bounded first. Public because `/q/health` publishes it: a
296 : /// second constant carrying the same number is one that can drift from the
297 : /// one actually enforced.
298 : pub const MAX_Q_NODES: usize = 512;
299 :
300 : /// Parse an NGSI-LD `q=` expression. Complexity ceilings raise
301 : /// TooComplexQuery per 5.5.6 ("a query operation … so complex that cannot
302 : /// be resolved").
303 16709 : pub fn parse_q(input: &str) -> Result<QNode, NgsiError> {
304 16709 : if input.len() > MAX_Q_BYTES {
305 9 : return Err(NgsiError::TooComplexQuery(format!(
306 9 : "q expression exceeds {MAX_Q_BYTES} bytes"
307 9 : )));
308 16700 : }
309 16700 : parse_capped(input, MAX_Q_DEPTH, MAX_Q_NODES)
310 16709 : }
311 :
312 : /// Paren depth a narrowed `q` may reach: the caller's [`MAX_Q_DEPTH`], one
313 : /// more where a hidden term becomes `(a;!a)`, one more for the conjunction,
314 : /// and a policy part held below it by [`fits_policy_q`].
315 : const MAX_NARROWED_Q_DEPTH: usize = 2 * MAX_Q_DEPTH;
316 :
317 : /// Nodes a narrowed `q` may hold: the caller's [`MAX_Q_NODES`], each term of
318 : /// it at most three once a hidden-Attribute rewrite has turned it into
319 : /// `(a;!a)`, the conjunction, and a policy part held below the rest by
320 : /// [`fits_policy_q`].
321 : pub const MAX_NARROWED_Q_NODES: usize = 8 * MAX_Q_NODES;
322 :
323 : /// Nodes the policy part of a narrowed `q` (an engine's, a view's, or both
324 : /// joined) may hold: what [`MAX_NARROWED_Q_NODES`] leaves after the
325 : /// rewritten caller part and the conjunction.
326 : const MAX_POLICY_Q_NODES: usize = MAX_NARROWED_Q_NODES - 3 * MAX_Q_NODES - 1;
327 :
328 : /// Parse a `q` the broker wrote by joining the caller's own `q` (already
329 : /// through [`parse_q`]) with a policy part that passed [`fits_policy_q`]
330 : /// (threat V23). The caps are the sum of the two, so a caller `q` that
331 : /// [`parse_q`] accepts is never refused here: the size of a predicate the
332 : /// caller cannot see changes no answer. No byte cap: the text is rendered
333 : /// from those two trees, and a rendered number is longer than the one
334 : /// written (`1e300`), so bytes would count the renderer, not the caller.
335 2130 : pub fn parse_narrowed_q(input: &str) -> Result<QNode, NgsiError> {
336 2130 : parse_capped(input, MAX_NARROWED_Q_DEPTH, MAX_NARROWED_Q_NODES)
337 2130 : }
338 :
339 : /// Whether a policy `q` stays inside the share of the narrowed caps the
340 : /// caller's part leaves it, so [`parse_narrowed_q`] accepts every join of
341 : /// it with a caller `q` that [`parse_q`] accepts. Judged on the tree alone,
342 : /// so the verdict is the same for every caller.
343 74 : pub fn fits_policy_q(node: &QNode) -> bool {
344 74 : q_nodes(node) <= MAX_POLICY_Q_NODES && paren_depth(node) < MAX_NARROWED_Q_DEPTH
345 74 : }
346 :
347 18830 : fn parse_capped(input: &str, depth: usize, nodes: usize) -> Result<QNode, NgsiError> {
348 18830 : let mut p = Parser {
349 18830 : rest: input.trim(),
350 18830 : depth: 0,
351 18830 : max_depth: depth,
352 18830 : };
353 18830 : let node = p.or_expr()?;
354 18097 : if !p.rest.is_empty() {
355 116 : return Err(bad(input, "trailing input"));
356 17981 : }
357 17981 : if q_nodes(&node) > nodes {
358 28 : return Err(NgsiError::TooComplexQuery(format!(
359 28 : "q expression exceeds {nodes} nodes"
360 28 : )));
361 17953 : }
362 17953 : Ok(node)
363 18830 : }
364 :
365 : /// 4.9 p.85: "`Number` shall be a number as mandated by the JSON
366 : /// Specification, following the ABNF Grammar, production rule named `number`,
367 : /// section 6 of IETF RFC 8259" — `[minus] int [frac] [exp]`, the int without
368 : /// a leading zero, the fraction and the exponent with at least one digit each.
369 : /// A float parse is much wider: `+5`, `01`, `.5`, `5.`, `NaN` and `inf` all
370 : /// come back as numbers from it and none of them is a Number here, so each
371 : /// would compare against a number where the term named text.
372 659992 : fn is_json_number(s: &str) -> bool {
373 659992 : let s = s.strip_prefix('-').unwrap_or(s);
374 662995 : let digits = |t: &str| t.bytes().take_while(u8::is_ascii_digit).count();
375 659992 : let int = digits(s);
376 659992 : if int == 0 || (int > 1 && s.starts_with('0')) {
377 190 : return false;
378 659802 : }
379 659802 : let rest = &s[int..];
380 659802 : let rest = match rest.strip_prefix('.') {
381 659547 : None => rest,
382 255 : Some(frac) => match digits(frac) {
383 2 : 0 => return false,
384 253 : n => &frac[n..],
385 : },
386 : };
387 659800 : match rest.strip_prefix(['e', 'E']) {
388 657050 : None => rest.is_empty(),
389 2750 : Some(exp) => {
390 2750 : let exp = exp.strip_prefix(['+', '-']).unwrap_or(exp);
391 2750 : !exp.is_empty() && digits(exp) == exp.len()
392 : }
393 : }
394 659992 : }
395 :
396 754975 : fn q_nodes(n: &QNode) -> usize {
397 754975 : match n {
398 13076 : QNode::And(xs) | QNode::Or(xs) => xs.iter().map(q_nodes).fold(1, usize::saturating_add),
399 741899 : _ => 1,
400 : }
401 754975 : }
402 :
403 : /// The parentheses `n` renders with at its deepest, as `render.rs` writes
404 : /// them: a group inside `;` and an `|` inside `|` are parenthesised.
405 40050 : fn paren_depth(n: &QNode) -> usize {
406 40050 : let deepest = |xs: &[QNode], wrapped: fn(&QNode) -> bool| {
407 17302 : xs.iter()
408 39716 : .map(|x| paren_depth(x).saturating_add(usize::from(wrapped(x))))
409 17302 : .max()
410 17302 : .unwrap_or(0)
411 17302 : };
412 40050 : match n {
413 34580 : QNode::And(xs) => deepest(xs, |x| matches!(x, QNode::And(_) | QNode::Or(_))),
414 5136 : QNode::Or(xs) => deepest(xs, |x| matches!(x, QNode::Or(_))),
415 22748 : _ => 0,
416 : }
417 40050 : }
418 :
419 837 : fn bad(input: &str, why: &str) -> NgsiError {
420 837 : NgsiError::BadRequestData(format!("invalid q expression {input:?}: {why}"))
421 837 : }
422 :
423 : struct Parser<'a> {
424 : rest: &'a str,
425 : /// open parentheses currently on the stack (see `MAX_Q_DEPTH`)
426 : depth: usize,
427 : /// the ceiling on `depth`: `MAX_Q_DEPTH` for a caller's `q`
428 : max_depth: usize,
429 : }
430 :
431 : impl<'a> Parser<'a> {
432 27510 : fn or_expr(&mut self) -> Result<QNode, NgsiError> {
433 27510 : let first = self.and_expr()?;
434 26056 : let mut rest = Vec::new();
435 165672 : while self.eat('|') {
436 139622 : rest.push(self.and_expr()?);
437 : }
438 26050 : Ok(if rest.is_empty() {
439 24681 : first
440 : } else {
441 1369 : QNode::Or(std::iter::once(first).chain(rest).collect())
442 : })
443 27510 : }
444 :
445 167132 : fn and_expr(&mut self) -> Result<QNode, NgsiError> {
446 167132 : let first = self.term()?;
447 165679 : let mut rest = Vec::new();
448 714604 : while self.eat(';') {
449 548932 : rest.push(self.term()?);
450 : }
451 165672 : Ok(if rest.is_empty() {
452 154486 : first
453 : } else {
454 11186 : QNode::And(std::iter::once(first).chain(rest).collect())
455 : })
456 167132 : }
457 :
458 716064 : fn term(&mut self) -> Result<QNode, NgsiError> {
459 716064 : if self.eat('(') {
460 : // refuse BEFORE recursing — an overflow here aborts the process
461 8688 : self.depth = self.depth.saturating_add(1);
462 8688 : if self.depth > self.max_depth {
463 8 : return Err(NgsiError::TooComplexQuery(format!(
464 8 : "q expression nests deeper than {}",
465 8 : self.max_depth
466 8 : )));
467 8680 : }
468 8680 : let node = self.or_expr()?;
469 7953 : self.depth = self.depth.saturating_sub(1);
470 7953 : if !self.eat(')') {
471 11 : return Err(bad(self.rest, "expected ')'"));
472 7942 : }
473 7942 : return Ok(node);
474 707376 : }
475 707376 : let negated = self.eat('!');
476 707376 : let path = self.qpath()?;
477 706945 : if let Some(op) = self.cmp_op() {
478 682129 : if negated {
479 2 : return Err(bad(self.rest, "'!' only prefixes an existence check"));
480 682127 : }
481 682127 : let value = self.value(op)?;
482 681846 : Ok(QNode::Cmp { path, op, value })
483 : } else {
484 24816 : Ok(QNode::Exists { path, negated })
485 : }
486 716064 : }
487 :
488 : /// 4.9 Attribute: `attr{[T[,T]:]…}` linked-entity hops, then a dotted
489 : /// path, then at most one trailing `[member.path]` / `[lang]` / `[*]`.
490 707376 : fn qpath(&mut self) -> Result<QPath, NgsiError> {
491 707376 : let mut links = Vec::new();
492 707376 : let mut braces = 0usize;
493 707376 : let mut name = self.name()?;
494 : // LinkedEntityRelation: AttrName{ [EntityType(,EntityType)*:] … }
495 707643 : while self.eat('{') {
496 388 : braces = braces.saturating_add(1);
497 388 : if braces > 8 {
498 4 : return Err(NgsiError::TooComplexQuery(
499 4 : "q linked-entity path nests deeper than 8".into(),
500 4 : ));
501 384 : }
502 384 : let mut types = Vec::new();
503 384 : let mut inner = self.name()?;
504 376 : if self.rest.starts_with(',') || self.rest.starts_with(':') {
505 54 : types.push(inner);
506 62 : while self.eat(',') {
507 8 : types.push(self.name()?);
508 : }
509 54 : if !self.eat(':') {
510 2 : return Err(bad(self.rest, "expected ':' after EntityType hints"));
511 52 : }
512 52 : inner = self.name()?;
513 322 : }
514 374 : links.push(Link { attr: name, types });
515 374 : name = inner;
516 : }
517 707255 : let mut path = vec![name];
518 707382 : while self.eat('.') {
519 131 : path.push(self.name()?);
520 : }
521 707251 : let bracket = if self.eat('[') {
522 : // spacing inside the bracket is insignificant, so `[ *a]` is
523 : // `[*a]` (refused) and never the member name `*a`
524 998 : self.rest = self.rest.trim_start();
525 998 : let b = if self.eat('*') {
526 118 : self.rest = self.rest.trim_start();
527 118 : vec!["*".to_owned()]
528 : } else {
529 880 : let mut b = vec![self.name_token()?];
530 862 : while self.eat('.') {
531 10 : b.push(self.name_token()?);
532 : }
533 852 : b
534 : };
535 970 : if !self.eat(']') {
536 276 : return Err(bad(self.rest, "expected ']'"));
537 694 : }
538 694 : Some(b)
539 : } else {
540 706253 : None
541 : };
542 706947 : for _ in 0..braces {
543 342 : if !self.eat('}') {
544 2 : return Err(bad(self.rest, "expected '}'"));
545 340 : }
546 : }
547 706945 : Ok(QPath {
548 706945 : links,
549 706945 : path,
550 706945 : bracket,
551 706945 : })
552 707376 : }
553 :
554 : /// One path segment: everything up to a structural delimiter or a
555 : /// space of any kind.
556 708841 : fn name_token(&mut self) -> Result<String, NgsiError> {
557 708841 : self.rest = self.rest.trim_start();
558 708841 : let end = self
559 708841 : .rest
560 1598424 : .find(|c: char| c.is_whitespace() || "=!<>~;|(),.{}[]:".contains(c))
561 708841 : .unwrap_or(self.rest.len());
562 708841 : let (raw, rest) = self.rest.split_at(end);
563 708841 : if raw.is_empty() {
564 119 : return Err(bad(rest, "expected attribute name"));
565 708722 : }
566 : // spacing around the segment is insignificant (`a ==1`, `a ; b`)
567 708722 : self.rest = rest.trim_start();
568 708722 : Ok(raw.to_owned())
569 708841 : }
570 :
571 : /// A segment that is a name in the 7.2.3.2 grammar (`AttrName`,
572 : /// `EntityType`): the 5.2.2.3 rule every stored name already obeys, so a
573 : /// query never names what no entity can hold.
574 707951 : fn name(&mut self) -> Result<String, NgsiError> {
575 707951 : let at = self.rest;
576 707951 : let name = self.name_token()?;
577 707860 : if !antares_jsonld::valid_name(&name) {
578 28 : return Err(bad(
579 28 : at,
580 28 : "an attribute or type name is a letter followed by letters, digits or '_'",
581 28 : ));
582 707832 : }
583 707832 : Ok(name)
584 707951 : }
585 :
586 706945 : fn cmp_op(&mut self) -> Option<CmpOp> {
587 912067 : for (tok, op) in [
588 706945 : ("==", CmpOp::Eq),
589 706945 : // "!~=" before "!=" — the longer token must win the prefix race
590 706945 : ("!~=", CmpOp::NotPattern),
591 706945 : ("!=", CmpOp::Ne),
592 706945 : ("~=", CmpOp::Pattern),
593 706945 : (">=", CmpOp::Ge),
594 706945 : ("<=", CmpOp::Le),
595 706945 : (">", CmpOp::Gt),
596 706945 : ("<", CmpOp::Lt),
597 706945 : ] {
598 912067 : if let Some(rest) = self.rest.strip_prefix(tok) {
599 682129 : self.rest = rest;
600 682129 : return Some(op);
601 229938 : }
602 : }
603 24816 : None
604 706945 : }
605 :
606 : /// Query Term value for `op` — 4.9 p.84 pairs them precisely:
607 : /// `Operator ComparableValue` (ordering), `equal/unequal CompEqualityValue`
608 : /// (adds true/false, ValueList, Range, URI), `patternOp/notPatternOp
609 : /// RegExp`. Lists and ranges with an ordering or pattern operator are a
610 : /// grammar violation, not an empty result.
611 682127 : fn value(&mut self, op: CmpOp) -> Result<QValue, NgsiError> {
612 : // 4.9: `patternOp`/`notPatternOp` take a `RegExp` (IEEE 1003.2), not
613 : // a `quotedStr`, so the operand is the pattern text as written — a
614 : // backslash in it belongs to the regular expression and is not an
615 : // RFC 8259 escape. Every other operand is a `quotedStr`, a Number, a
616 : // 4.6.3 dateTime/date/time or a URI.
617 682127 : let regexp = matches!(op, CmpOp::Pattern | CmpOp::NotPattern);
618 682127 : let first = self.scalar(regexp)?;
619 681888 : let equality = matches!(op, CmpOp::Eq | CmpOp::Ne);
620 681888 : self.rest = self.rest.trim_start();
621 681888 : if let Some(rest) = self.rest.strip_prefix("..") {
622 199 : if !equality {
623 6 : return Err(bad(
624 6 : self.rest,
625 6 : "a Range is only valid with == or != (4.9 CompEqualityValue)",
626 6 : ));
627 193 : }
628 193 : self.rest = rest.trim_start();
629 193 : let hi = self.scalar(false)?;
630 : // Range = ComparableValue..ComparableValue: booleans excluded, and
631 : // an order relation needs both endpoints in one value space
632 189 : if std::mem::discriminant(&first) != std::mem::discriminant(&hi)
633 185 : || matches!(first, QValue::Bool(_))
634 : {
635 6 : return Err(bad(
636 6 : self.rest,
637 6 : "Range endpoints must be two comparable values of the same type",
638 6 : ));
639 183 : }
640 183 : return Ok(QValue::Range(Box::new(first), Box::new(hi)));
641 681689 : }
642 681689 : if self.rest.starts_with(',') {
643 316 : if !equality {
644 4 : return Err(bad(
645 4 : self.rest,
646 4 : "a ValueList is only valid with == or != (4.9 CompEqualityValue)",
647 4 : ));
648 312 : }
649 312 : let mut items = vec![first];
650 624 : while self.eat(',') {
651 314 : self.rest = self.rest.trim_start();
652 314 : items.push(self.scalar(false)?);
653 312 : self.rest = self.rest.trim_start();
654 : }
655 310 : return Ok(QValue::List(items));
656 681373 : }
657 681373 : if matches!(op, CmpOp::Gt | CmpOp::Ge | CmpOp::Lt | CmpOp::Le)
658 5185 : && matches!(first, QValue::Bool(_))
659 : {
660 20 : return Err(bad(
661 20 : self.rest,
662 20 : "true/false are only valid with == or != (4.9 OtherValue)",
663 20 : ));
664 681353 : }
665 681353 : Ok(first)
666 682127 : }
667 :
668 : /// One scalar literal. Unquoted tokens stop at a delimiter or at `..`
669 : /// (the Range separator) — a decimal like `10.5` has no `..`, so
670 : /// `10.5..20.5` still splits at the right place.
671 : ///
672 : /// `regexp` selects the grammar the quoted form follows: a `RegExp`
673 : /// operand is taken as written, everything else is a `quotedStr`, i.e.
674 : /// "a text string as mandated by the JSON Specification, following the
675 : /// ABNF Grammar, production rule named String, section 7 of IETF
676 : /// RFC 8259" — escapes included, decoded to the text the term compares
677 : /// against, which is how the entity member reached the store too.
678 682634 : fn scalar(&mut self, regexp: bool) -> Result<QValue, NgsiError> {
679 : // The clause writes its own examples with a space before the value
680 : // (`color!= "black", "red"`, p.90). Deciding quoted-vs-unquoted on an
681 : // untrimmed head read that as an unquoted token and kept the quotes
682 : // INSIDE the value, so the term matched a value literally spelled
683 : // with them.
684 682634 : self.rest = self.rest.trim_start();
685 682634 : if self.rest.starts_with('"') {
686 22210 : if regexp {
687 611 : let rest = &self.rest[1..];
688 611 : let end = rest
689 611 : .find('"')
690 611 : .ok_or_else(|| bad(rest, "unterminated string"))?;
691 609 : let (s, rest) = rest.split_at(end);
692 609 : self.rest = &rest[1..];
693 609 : return Ok(QValue::Str(s.to_owned()));
694 21599 : }
695 21599 : let end = Self::json_string_end(self.rest)
696 21599 : .ok_or_else(|| bad(self.rest, "unterminated string"))?;
697 21576 : let (lit, rest) = self.rest.split_at(end);
698 21576 : let s: String = serde_json::from_str(lit)
699 21576 : .map_err(|_| bad(lit, "value is not an RFC 8259 String (4.9 quotedStr)"))?;
700 21416 : self.rest = rest;
701 21416 : return Ok(QValue::Str(s));
702 660424 : }
703 660424 : let stop = self
704 660424 : .rest
705 1879457 : .find(|c: char| ";|(),".contains(c))
706 660424 : .unwrap_or(self.rest.len());
707 : // the Range separator is looked for in this token only: across the
708 : // whole rest, every term rescanned the terms after it. A RegExp has
709 : // no Range form, and `..` is pattern text there (`n~=a..z`).
710 660424 : let end = self
711 660424 : .rest
712 660424 : .get(..stop)
713 660424 : .and_then(|token| token.find(".."))
714 660424 : .filter(|_| !regexp)
715 660424 : .unwrap_or(stop);
716 660424 : let (raw, rest) = self.rest.split_at(end);
717 660424 : let raw = raw.trim();
718 : // The unquoted alternatives are `dateTime`/`date`/`time` (4.6.3), a
719 : // Number and a `URI` (RFC 3986). None of them admits a `\"`, so one
720 : // here is an unterminated `quotedStr`, not a value. An unquoted
721 : // `RegExp` is refused one too: the term is rendered back with its
722 : // pattern between quotes (render.rs), where a `\"` in the pattern
723 : // ends it, so the rendered query (a policy narrowing, a forward)
724 : // no longer parsed.
725 660424 : if raw.contains('"') {
726 12 : return Err(bad(raw, "unquoted value must not contain a quote (4.9)"));
727 660412 : }
728 660412 : self.rest = rest;
729 260 : match raw {
730 : // 4.9 `patternOp RegExp`: the operand is pattern text whatever
731 : // it looks like — `code~=123` is the regex 123, not the Number
732 : // (which no regex is compiled from), `f~=true` no boolean
733 660412 : _ if regexp && !raw.is_empty() => Ok(QValue::Str(raw.to_owned())),
734 660388 : "true" => Ok(QValue::Bool(true)),
735 660161 : "false" => Ok(QValue::Bool(false)),
736 : // RFC 8259 section 6 lets a receiver limit the range: a Number
737 : // past f64 is refused, as serde_json refuses it in a body, so no
738 : // comparison runs against a value no Entity can hold
739 659992 : _ if is_json_number(raw) => match raw.parse::<f64>() {
740 659702 : Ok(n) if n.is_finite() => Ok(QValue::Num(n)),
741 10 : _ => Err(bad(raw, "Number is out of range (RFC 8259 section 6)")),
742 : },
743 : // the other unquoted alternatives: a URI, a dateTime, a date or a
744 : // time, all of them compared as text
745 290 : "" => Err(bad(raw, "expected value")),
746 : // A value that starts with an operator's character is a typo of
747 : // the operator (`speed>>`), never the text ">".
748 260 : _ if !regexp && raw.starts_with(['<', '>', '=', '!', '~']) => Err(bad(
749 8 : raw,
750 8 : "an unquoted value starts with no operator character (4.9); quote a text",
751 8 : )),
752 252 : _ => Ok(QValue::Str(raw.to_owned())),
753 : }
754 682634 : }
755 :
756 : /// Byte index one past the closing quote of the RFC 8259 string at the head
757 : /// of `s`, or `None` when it never closes. A quote is the closing one only
758 : /// when it is not itself escaped, so the scan skips the byte after every
759 : /// backslash — both are ASCII, so a skip can never land mid-character in a
760 : /// way that reads as either.
761 21599 : fn json_string_end(s: &str) -> Option<usize> {
762 21599 : let b = s.as_bytes();
763 21599 : let mut i = 1usize;
764 107143 : while let Some(&c) = b.get(i) {
765 107120 : match c {
766 150 : b'\\' => i = i.saturating_add(2),
767 21576 : b'"' => return i.checked_add(1),
768 85394 : _ => i = i.saturating_add(1),
769 : }
770 : }
771 23 : None
772 21599 : }
773 :
774 4437857 : fn eat(&mut self, c: char) -> bool {
775 4437857 : if let Some(rest) = self.rest.strip_prefix(c) {
776 720622 : self.rest = rest;
777 720622 : true
778 : } else {
779 3717235 : false
780 : }
781 4437857 : }
782 : }
783 :
784 : #[cfg(test)]
785 : mod tests {
786 : use super::*;
787 :
788 : /// A pattern operand holding a quote cannot be spelled back as a Query
789 : /// Term (render.rs writes it between quotes, where the quote ends it), so
790 : /// the unquoted form refuses one as the quoted form does: what parses
791 : /// renders to a query that parses to it again.
792 : #[test]
793 2 : fn an_unquoted_pattern_with_a_quote_is_refused() {
794 6 : for q in [r#"code~=a"b"#, r#"code!~=a"b"#, r#"code~=a""#] {
795 6 : assert!(parse_q(q).is_err(), "{q}");
796 : }
797 2 : let node = parse_q(r#"code~=a\\.b"#).expect("pattern");
798 2 : assert_eq!(parse_q(&node.to_string()).expect("round-trip"), node);
799 2 : assert_eq!(parse_narrowed_q(&node.to_string()).expect("narrowed"), node);
800 2 : }
801 :
802 : /// an unquoted value that starts with an operator's character is
803 : /// a typo of the operator, refused rather than compared as text.
804 : #[test]
805 2 : fn an_unquoted_value_starting_with_an_operator_is_refused() {
806 8 : for q in ["speed>>", "speed>=>", "speed==>1", "speed!=<"] {
807 8 : assert!(parse_q(q).is_err(), "{q}");
808 : }
809 12 : for q in [
810 2 : "speed>1",
811 2 : "speed>-1",
812 2 : "name==urn:ngsi-ld:Car:1",
813 2 : "observedAt>2026-01-01T00:00:00Z",
814 2 : "name==\">\"",
815 2 : "name~=>.*",
816 2 : ] {
817 12 : assert!(parse_q(q).is_ok(), "{q}");
818 : }
819 2 : }
820 :
821 : /// RFC 3986 2.1: "%" and exactly two hex digits; anything shorter or
822 : /// signed stays as written, at the end of the input too (the
823 : /// decoder walks the bytes without indexing past them).
824 : #[test]
825 2 : fn percent_decode_takes_two_hex_digits_and_nothing_else() {
826 18 : for (input, want) in [
827 2 : ("", ""),
828 2 : ("%", "%"),
829 2 : ("%4", "%4"),
830 2 : ("a%41", "aA"),
831 2 : ("%41%", "A%"),
832 2 : ("%+1", "%+1"),
833 2 : ("%zz%2", "%zz%2"),
834 2 : ("%C3%A9", "\u{e9}"),
835 2 : ("\u{e9}%20x", "\u{e9} x"),
836 2 : ] {
837 18 : assert_eq!(percent_decode(input.as_bytes()), want, "{input:?}");
838 : }
839 2 : }
840 :
841 : /// 4.9 p.85: "`Number` shall be a number as mandated by the JSON
842 : /// Specification, following the ABNF Grammar, production rule named
843 : /// `number`, section 6 of IETF RFC 8259" — an optional minus, an int with
844 : /// no leading zero, a fraction of at least one digit, an exponent of at
845 : /// least one digit. A plain float parse is far wider than that: it takes
846 : /// `+5`, `01`, `.5`, `5.`, `NaN` and `inf`, none of which is a Number.
847 : /// The other unquoted alternatives of `ComparableValue` and
848 : /// `CompEqualityValue` are `dateTime`/`date`/`time` and `URI`, all of
849 : /// which compare as text, so a token that is not a Number is a String.
850 : #[test]
851 2 : fn an_unquoted_token_is_a_number_only_when_rfc_8259_says_so() {
852 36 : for (q, want) in [
853 2 : ("x==5", QValue::Num(5.0)),
854 2 : ("x==-5", QValue::Num(-5.0)),
855 2 : ("x==0", QValue::Num(0.0)),
856 2 : ("x==0.5", QValue::Num(0.5)),
857 2 : ("x==1e3", QValue::Num(1000.0)),
858 2 : ("x==1E+3", QValue::Num(1000.0)),
859 2 : ("x==-2.5e-2", QValue::Num(-0.025)),
860 2 : // every one of these a plain float parse accepts and RFC 8259
861 2 : // does not
862 2 : ("x==+5", QValue::Str("+5".into())),
863 2 : ("x==01", QValue::Str("01".into())),
864 2 : ("x==.5", QValue::Str(".5".into())),
865 2 : ("x==5.", QValue::Str("5.".into())),
866 2 : ("x==NaN", QValue::Str("NaN".into())),
867 2 : ("x==nan", QValue::Str("nan".into())),
868 2 : ("x==inf", QValue::Str("inf".into())),
869 2 : ("x==-inf", QValue::Str("-inf".into())),
870 2 : ("x==infinity", QValue::Str("infinity".into())),
871 2 : ("x==1e", QValue::Str("1e".into())),
872 2 : ("x==-", QValue::Str("-".into())),
873 2 : ] {
874 36 : let node = parse_q(q).expect(q);
875 36 : assert!(
876 36 : matches!(&node, QNode::Cmp { value, .. } if *value == want),
877 : "{q}: {node:?}"
878 : );
879 : }
880 2 : }
881 :
882 : /// RFC 8259 section 6: "This specification allows implementations to
883 : /// set limits on the range and precision of numbers accepted." A Number
884 : /// past f64 is refused, as an entity body holding it is (serde_json);
885 : /// read as infinity it would compare against values no Entity can hold
886 : /// and render as `inf`, which parses back as a String (found by the
887 : /// parse_q fuzz target, fuzz/regressions/parse_q).
888 : /// 4.9 `[*]` is the whole bracket, never the start of a member name,
889 : /// and spacing inside the bracket is insignificant: `m[ *a]` was read
890 : /// as the member `*a` and rendered as `m[*a]`, which is refused (found
891 : /// by the parse_q fuzz target, fuzz/regressions/parse_q).
892 : #[test]
893 2 : fn a_star_in_a_bracket_is_the_whole_bracket_whatever_the_spacing() {
894 6 : for q in ["m[*a]!=c", "m[ *a]!=c", "m[\t*a]!=c"] {
895 6 : assert!(parse_q(q).is_err(), "{q:?}");
896 : }
897 6 : for q in ["m[*]==\"x\"", "m[ * ]==\"x\"", "m[\t*\t]==\"x\""] {
898 6 : let node = parse_q(q).expect(q);
899 6 : assert_eq!(node.to_string(), "m[*]==\"x\"", "{q:?}");
900 : }
901 2 : }
902 :
903 : #[test]
904 2 : fn a_number_past_the_float_range_is_refused() {
905 8 : for q in ["A>8e44444", "x==-1e400", "x==1e309..2", "x==1..1E+999"] {
906 8 : assert!(
907 8 : matches!(parse_q(q), Err(NgsiError::BadRequestData(_))),
908 : "{q}: {:?}",
909 0 : parse_q(q)
910 : );
911 : }
912 : // below the range is not past it: an underflow is the nearest value
913 2 : assert_eq!(
914 2 : parse_q("x==1e-400").expect("underflow"),
915 2 : parse_q("x==0").expect("zero")
916 : );
917 2 : }
918 :
919 : #[test]
920 2 : fn simple_comparison() {
921 2 : let q = parse_q(r#"brandName=="Mercedes""#).expect("parse");
922 2 : assert_eq!(
923 : q,
924 2 : QNode::Cmp {
925 2 : path: QPath::dotted(vec!["brandName".into()]),
926 2 : op: CmpOp::Eq,
927 2 : value: QValue::Str("Mercedes".into())
928 2 : }
929 : );
930 2 : }
931 :
932 : #[test]
933 2 : fn and_or_precedence() {
934 : // `a==1;b==2|c==3` == (a AND b) OR c per grammar: OR binds looser
935 2 : let q = parse_q("a==1;b==2|c==3").expect("parse");
936 2 : assert!(
937 2 : matches!(&q, QNode::Or(items) if items.len() == 2 && matches!(items[0], QNode::And(_))),
938 : "{q:?}"
939 : );
940 2 : }
941 :
942 : #[test]
943 2 : fn dotted_path_and_numbers() {
944 2 : let q = parse_q("speed.value>=80.5").expect("parse");
945 2 : assert_eq!(
946 : q,
947 2 : QNode::Cmp {
948 2 : path: QPath::dotted(vec!["speed".into(), "value".into()]),
949 2 : op: CmpOp::Ge,
950 2 : value: QValue::Num(80.5)
951 2 : }
952 : );
953 2 : }
954 :
955 : /// TS 104 175 7.2.3.2 / 5.2.2.3: an attribute path, a linked-entity
956 : /// attribute and an EntityType hint are names (`unicodeLetter
957 : /// *(unicodeLetter / unicodeNumber / "_")`); anything else is
958 : /// BadRequestData rather than a name no entity can hold. Found by the
959 : /// parse_q fuzz target's render round-trip:
960 : /// `(?\n<&3|$$\t)` parsed as the attributes "?\n" and "$$", and the
961 : /// tab before `)` was dropped where the one at the end was kept.
962 : #[test]
963 2 : fn attribute_names_follow_the_name_grammar() {
964 16 : for refused in [
965 2 : "(?\n<&3|$$\t)",
966 2 : "$$",
967 2 : "brand-name==1",
968 2 : "1st==1",
969 2 : "a\tb==1",
970 2 : "speed.$x==1",
971 2 : "rel{T-1:name}==1",
972 2 : "rel-x{name}==1",
973 2 : ] {
974 16 : assert!(
975 16 : matches!(parse_q(refused), Err(NgsiError::BadRequestData(_))),
976 : "{refused:?} parsed"
977 : );
978 : }
979 20 : for accepted in [
980 2 : "speed==1",
981 2 : "speed\t==1",
982 2 : "(speed\t)",
983 2 : "temperature_2==1",
984 2 : "größe>1",
985 2 : "owner{works{name}}==\"x\"",
986 2 : "rel{Building,Room:name}",
987 2 : "color[en-GB]==\"red\"",
988 2 : "address[city]==\"Berlin\"",
989 2 : "speed.observedAt>\"2020-01-01T00:00:00Z\"",
990 2 : ] {
991 20 : assert!(
992 20 : parse_q(accepted).is_ok(),
993 : "{accepted:?} refused: {:?}",
994 0 : parse_q(accepted)
995 : );
996 : }
997 2 : }
998 :
999 : #[test]
1000 2 : fn existence_and_negation() {
1001 2 : assert_eq!(
1002 2 : parse_q("!temperature").expect("parse"),
1003 2 : QNode::Exists {
1004 2 : path: QPath::dotted(vec!["temperature".into()]),
1005 2 : negated: true
1006 2 : }
1007 : );
1008 2 : }
1009 :
1010 : #[test]
1011 2 : fn parens_group() {
1012 2 : let q = parse_q("(a==1|b==2);c==3").expect("parse");
1013 2 : assert!(matches!(q, QNode::And(_)));
1014 2 : }
1015 :
1016 : #[test]
1017 2 : fn rejects_garbage() {
1018 8 : for bad in ["", "==5", "a==\"unterminated", "a==1)"] {
1019 8 : assert!(parse_q(bad).is_err(), "should reject {bad:?}");
1020 : }
1021 2 : }
1022 :
1023 : #[test]
1024 2 : fn value_list_parses_with_equality_ops_only() {
1025 : // 4.9 p.85 ValueList = Value 1*(, Value); p.84 pairs it with ==/!= only
1026 2 : let q = parse_q(r#"color=="black","red""#).expect("parse");
1027 2 : assert_eq!(
1028 : q,
1029 2 : QNode::Cmp {
1030 2 : path: QPath::dotted(vec!["color".into()]),
1031 2 : op: CmpOp::Eq,
1032 2 : value: QValue::List(vec![QValue::Str("black".into()), QValue::Str("red".into())])
1033 2 : }
1034 : );
1035 : // spec's own spacing (`color!= "black", "red"`, p.90) must parse to
1036 : // the same values — the space may not end up inside them, and neither
1037 : // may the quotes that delimit them
1038 2 : assert_eq!(
1039 2 : parse_q(r#"color!= "black", "red""#).expect("parse"),
1040 2 : QNode::Cmp {
1041 2 : path: QPath::dotted(vec!["color".into()]),
1042 2 : op: CmpOp::Ne,
1043 2 : value: QValue::List(vec![QValue::Str("black".into()), QValue::Str("red".into())])
1044 2 : }
1045 : );
1046 2 : assert_eq!(
1047 2 : parse_q(r#"color== "black""#).expect("parse"),
1048 2 : QNode::Cmp {
1049 2 : path: QPath::dotted(vec!["color".into()]),
1050 2 : op: CmpOp::Eq,
1051 2 : value: QValue::Str("black".into())
1052 2 : },
1053 : "a single spaced value keeps neither the space nor the quotes"
1054 : );
1055 : // mixed scalar kinds are legal (ValueList is over Value)
1056 2 : assert!(parse_q("a==1,2,3").is_ok());
1057 : // ordering + list is a grammar violation → 400, not empty result
1058 2 : assert!(parse_q(r#"a>"x","y""#).is_err());
1059 2 : assert!(parse_q("a>=1,2").is_err());
1060 2 : }
1061 :
1062 : #[test]
1063 2 : fn range_parses_with_equality_ops_only() {
1064 : // 4.9 p.85 Range = ComparableValue dots ComparableValue
1065 2 : let q = parse_q("temperature==10..20").expect("parse");
1066 2 : assert_eq!(
1067 : q,
1068 2 : QNode::Cmp {
1069 2 : path: QPath::dotted(vec!["temperature".into()]),
1070 2 : op: CmpOp::Eq,
1071 2 : value: QValue::Range(Box::new(QValue::Num(10.0)), Box::new(QValue::Num(20.0)))
1072 2 : }
1073 : );
1074 : // decimals keep their fraction; `..` is not mistaken for `.`
1075 2 : let q = parse_q("t!=10.5..20.5").expect("parse");
1076 2 : assert!(matches!(
1077 2 : q,
1078 : QNode::Cmp {
1079 : op: CmpOp::Ne,
1080 : value: QValue::Range(_, _),
1081 : ..
1082 : }
1083 : ));
1084 : // DateTime endpoints (unquoted, per EXAMPLE 8 style literals)
1085 2 : let q = parse_q("observedAt==2021-01-01T00:00:00Z..2021-02-01T00:00:00Z").expect("parse");
1086 2 : assert!(matches!(
1087 2 : q,
1088 : QNode::Cmp {
1089 : value: QValue::Range(_, _),
1090 : ..
1091 : }
1092 : ));
1093 : // ordering + range violates the grammar; bools are not ComparableValue
1094 2 : assert!(parse_q("a>1..5").is_err());
1095 2 : assert!(parse_q("a==true..false").is_err());
1096 2 : assert!(parse_q("a==1..\"x\"").is_err(), "mixed-type endpoints");
1097 2 : }
1098 :
1099 : #[test]
1100 2 : fn not_pattern_op() {
1101 : // 4.9 p.85 notPatternOp = !~=
1102 2 : let q = parse_q(r#"name!~="^Merc""#).expect("parse");
1103 2 : assert_eq!(
1104 : q,
1105 2 : QNode::Cmp {
1106 2 : path: QPath::dotted(vec!["name".into()]),
1107 2 : op: CmpOp::NotPattern,
1108 2 : value: QValue::Str("^Merc".into())
1109 2 : }
1110 : );
1111 2 : }
1112 :
1113 : /// 4.9 `patternOp RegExp`: an unquoted operand is the pattern text, not a
1114 : /// Number, a boolean or a Range — `code~=123` must not become 123.0.
1115 : #[test]
1116 2 : fn an_unquoted_pattern_is_regexp_text() {
1117 10 : for (q, want) in [
1118 2 : ("code~=123", "123"),
1119 2 : ("code~=1.50", "1.50"),
1120 2 : ("f~=true", "true"),
1121 2 : ("n~=a..z", "a..z"),
1122 2 : ("n!~=0..9;m==1", "0..9"),
1123 2 : ] {
1124 10 : let n = parse_q(q).unwrap_or_else(|e| panic!("{q}: {e:?}"));
1125 10 : let pattern = match &n {
1126 2 : QNode::And(items) => items.first(),
1127 8 : other => Some(other),
1128 : };
1129 10 : assert!(
1130 10 : matches!(pattern, Some(QNode::Cmp { value: QValue::Str(s), .. }) if s == want),
1131 : "{q}: {n:?}"
1132 : );
1133 : }
1134 2 : assert!(
1135 2 : parse_q("code~=").is_err(),
1136 : "an empty pattern is still no value"
1137 : );
1138 2 : }
1139 :
1140 : /// 4.9: `quotedStr = String`, and `String` "shall be a text string as
1141 : /// mandated by the JSON Specification, following the ABNF Grammar,
1142 : /// production rule named String, section 7 of IETF RFC 8259" — whose
1143 : /// `char` production is `unescaped / escape (…)`. So a Query Term value
1144 : /// may carry an escaped quote, an escaped backslash, the two-character
1145 : /// control escapes and `\uXXXX`, and the value the term compares against
1146 : /// is the DECODED text: the entity member it is matched to was decoded by
1147 : /// the JSON parser on the way in.
1148 : #[test]
1149 2 : fn a_quoted_string_is_an_rfc_8259_string() {
1150 14 : for (q, want) in [
1151 2 : (r#"a=="say \"hi\"""#, "say \"hi\""),
1152 2 : (r#"a=="back\\slash""#, "back\\slash"),
1153 2 : (r#"a=="line\nbreak""#, "line\nbreak"),
1154 2 : (r#"a=="tab\there""#, "tab\there"),
1155 2 : (r#"a=="caf\u00e9""#, "café"),
1156 2 : (r#"a=="sl\/ash""#, "sl/ash"),
1157 2 : (r#"a=="""#, ""),
1158 2 : ] {
1159 14 : let node = parse_q(q).unwrap_or_else(|e| panic!("{q}: {e:?}"));
1160 14 : assert!(
1161 14 : matches!(&node, QNode::Cmp { value: QValue::Str(s), .. } if s == want),
1162 : "{q}: {node:?}"
1163 : );
1164 : }
1165 2 : }
1166 :
1167 : /// The escape only ends the string when it is not itself escaped: a
1168 : /// trailing `\"` continues the literal, and `\\` before the closing
1169 : /// quote does not.
1170 : #[test]
1171 2 : fn an_escaped_quote_does_not_end_the_string() {
1172 2 : assert!(
1173 2 : parse_q(r#"a=="unterminated\""#).is_err(),
1174 : "an escaped quote leaves the string open"
1175 : );
1176 2 : let node = parse_q(r#"a=="ends with a backslash\\";b"#).expect("parses");
1177 2 : assert!(
1178 2 : matches!(&node, QNode::And(items)
1179 2 : if matches!(&items[0], QNode::Cmp { value: QValue::Str(s), .. } if s == "ends with a backslash\\")),
1180 : "{node:?}"
1181 : );
1182 2 : }
1183 :
1184 : /// An escape RFC 8259 does not define is not a String, so the term is
1185 : /// not a Query Term — refused rather than silently read as two
1186 : /// characters.
1187 : #[test]
1188 2 : fn an_undefined_escape_is_not_a_string() {
1189 6 : for q in [r#"a=="bad\x""#, r#"a=="short\u12""#, r#"a=="\u12zz""#] {
1190 6 : assert!(parse_q(q).is_err(), "{q} must not parse");
1191 : }
1192 2 : }
1193 :
1194 : /// The unquoted alternatives of the grammar are `dateTime`/`date`/`time`
1195 : /// (4.6.3) and `URI` (RFC 3986), and a raw `"` belongs to none of them.
1196 : /// Accepting one produced a value that could not be written back as a
1197 : /// Query Term at all.
1198 : #[test]
1199 2 : fn an_unquoted_value_may_not_carry_a_bare_quote() {
1200 6 : for q in [r#"a==x"y"#, r#"a==urn:x:"y"#, r#"a>2020-01-01T00:00:"0Z"#] {
1201 6 : assert!(parse_q(q).is_err(), "{q} must not parse");
1202 : }
1203 2 : }
1204 :
1205 : #[test]
1206 2 : fn bool_with_ordering_op_is_a_grammar_violation() {
1207 : // p.84: Operator (ordering) takes ComparableValue; true/false are
1208 : // OtherValue, reachable only through ==/!=
1209 2 : assert!(parse_q("a>true").is_err());
1210 2 : assert!(parse_q("a==true").is_ok());
1211 2 : }
1212 : }
1213 :
1214 : #[cfg(test)]
1215 : mod complexity_tests {
1216 : use super::*;
1217 :
1218 : #[test]
1219 2 : fn q_complexity_cap_is_403_class() {
1220 : // >512 nodes → TooComplexQuery, small trees untouched.
1221 2 : let ok = "a==1;b==2|c==3";
1222 2 : assert!(parse_q(ok).is_ok());
1223 2 : let huge = (0..600)
1224 1200 : .map(|i| format!("a{i}==1"))
1225 2 : .collect::<Vec<_>>()
1226 2 : .join(";");
1227 2 : let answer = parse_q(&huge);
1228 2 : assert!(
1229 2 : matches!(answer, Err(NgsiError::TooComplexQuery(_))),
1230 : "{answer:?}"
1231 : );
1232 2 : }
1233 :
1234 : /// Regression: the parser once recursed per `(` with
1235 : /// no depth counter. A Rust stack overflow is a guard-page ABORT, not a
1236 : /// catchable panic — no tower layer can contain it — so ~4000 parens in a
1237 : /// query string killed the whole broker process, and a percent-encoded
1238 : /// copy stored in a subscription made that a restart-surviving crash loop.
1239 : #[test]
1240 : #[cfg_attr(miri, ignore)] // 50k parens: nine minutes under the interpreter
1241 2 : fn deep_nesting_is_refused_before_it_can_overflow_the_stack() {
1242 2 : let deep = format!("{}a==1{}", "(".repeat(50_000), ")".repeat(50_000));
1243 2 : assert!(
1244 2 : matches!(parse_q(&deep), Err(NgsiError::TooComplexQuery(_))),
1245 : "deep nesting must be a 403, never an abort"
1246 : );
1247 : // the length cap fires first on that one; check depth alone too
1248 2 : let deep = format!("{}a==1{}", "(".repeat(300), ")".repeat(300));
1249 2 : assert!(deep.len() < MAX_Q_BYTES);
1250 2 : assert!(matches!(parse_q(&deep), Err(NgsiError::TooComplexQuery(_))));
1251 : // and ordinary grouping still parses
1252 2 : assert!(parse_q("((a==1|b==2);c==3)").is_ok());
1253 2 : }
1254 :
1255 : #[test]
1256 2 : fn overlong_q_is_refused_at_the_entry_point() {
1257 : // a POST query body carries `q` too, where the URI cap does not apply
1258 2 : let long = format!("a=={}", "x".repeat(MAX_Q_BYTES));
1259 2 : assert!(matches!(parse_q(&long), Err(NgsiError::TooComplexQuery(_))));
1260 2 : }
1261 :
1262 : /// The depth ceiling is exact and counts open parentheses, not the
1263 : /// parentheses seen: sibling groups close what they open, so a query may
1264 : /// carry any number of them.
1265 : #[test]
1266 2 : fn depth_cap_is_exact_and_counts_only_open_parens() {
1267 2 : let at_cap = format!("{}a==1{}", "(".repeat(MAX_Q_DEPTH), ")".repeat(MAX_Q_DEPTH));
1268 2 : assert!(parse_q(&at_cap).is_ok(), "{MAX_Q_DEPTH} nested must parse");
1269 2 : let over = format!(
1270 : "{}a==1{}",
1271 2 : "(".repeat(MAX_Q_DEPTH + 1),
1272 2 : ")".repeat(MAX_Q_DEPTH + 1)
1273 : );
1274 2 : assert!(matches!(parse_q(&over), Err(NgsiError::TooComplexQuery(_))));
1275 2 : let siblings = (0..200)
1276 400 : .map(|i| format!("(a{i}==1)"))
1277 2 : .collect::<Vec<_>>()
1278 2 : .join(";");
1279 2 : assert!(siblings.len() < MAX_Q_BYTES);
1280 2 : assert!(parse_q(&siblings).is_ok(), "siblings are not cumulative");
1281 2 : }
1282 :
1283 : /// The parser is a fuzz target: on any input it returns, and the error it
1284 : /// returns is safe to hand back — the input is echoed Debug-escaped, so a
1285 : /// rejected `q` cannot carry a raw CR/LF into a response or a log line.
1286 : #[test]
1287 2 : fn hostile_input_is_total_and_its_error_is_escaped() {
1288 90 : for hostile in [
1289 2 : "",
1290 2 : " ",
1291 2 : "\"",
1292 2 : "\"\"",
1293 2 : "a==\"",
1294 2 : "..",
1295 2 : "a==..",
1296 2 : "a==1..",
1297 2 : "a==..1",
1298 2 : "a.",
1299 2 : "a[",
1300 2 : "a[]",
1301 2 : "a{",
1302 2 : "a{}",
1303 2 : "a{b",
1304 2 : "a{,:b}",
1305 2 : ";",
1306 2 : "|",
1307 2 : "()",
1308 2 : "(((",
1309 2 : ")))",
1310 2 : "!",
1311 2 : "!!a",
1312 2 : "a==1,",
1313 2 : "a==,1",
1314 2 : "~=",
1315 2 : "a~=",
1316 2 : "a!~=",
1317 2 : "a==1)b",
1318 2 : "\u{202e}==1",
1319 2 : "ä==1",
1320 2 : "a==\"ä",
1321 2 : "温度.値>=1",
1322 2 : "a\u{2028}==1",
1323 2 : "a=={}",
1324 2 : "a==1e999",
1325 2 : "a==-0",
1326 2 : "a==NaN..1",
1327 2 : "a{b:c}{d:e}.f[g].h==1",
1328 2 : &"{".repeat(64),
1329 2 : &"[".repeat(64),
1330 2 : &"a{".repeat(64),
1331 2 : &".".repeat(64),
1332 2 : &"!".repeat(64),
1333 2 : &",".repeat(64),
1334 2 : ] {
1335 90 : match parse_q(hostile) {
1336 10 : Ok(_) => {}
1337 80 : Err(e) => {
1338 80 : let msg = e.to_string();
1339 80 : assert!(
1340 80 : !msg.chars().any(char::is_control),
1341 : "error text must stay escaped for {hostile:?}: {msg:?}"
1342 : );
1343 : }
1344 : }
1345 : }
1346 2 : }
1347 :
1348 : /// `!` is the existence-check prefix only (4.9): pairing it with a
1349 : /// comparison is a grammar violation, not a silently ignored negation.
1350 : #[test]
1351 2 : fn negated_comparison_is_a_grammar_violation() {
1352 2 : assert!(matches!(
1353 2 : parse_q("!a==1"),
1354 : Err(NgsiError::BadRequestData(_))
1355 : ));
1356 2 : assert!(matches!(
1357 2 : parse_q("!a"),
1358 : Ok(QNode::Exists { negated: true, .. })
1359 : ));
1360 : // `!=` after a path is the operator, not a negation prefix
1361 2 : assert!(matches!(
1362 2 : parse_q("a!=1"),
1363 : Ok(QNode::Cmp { op: CmpOp::Ne, .. })
1364 : ));
1365 2 : }
1366 :
1367 : /// 4.17: `,`/`|` is OR, `(a;b)` is AND inside one alternative; names are
1368 : /// expanded against the @context before they are compared.
1369 : #[test]
1370 2 : fn type_selection_or_and_and() {
1371 2 : let ctx = crate::test_core();
1372 4 : let d = |t: &str| format!("https://uri.etsi.org/ngsi-ld/default-context/{t}");
1373 2 : let (car, bus) = (d("Car"), d("Bus"));
1374 2 : let both = [car.as_str(), bus.as_str()];
1375 2 : let car_only = [car.as_str()];
1376 2 : assert!(type_selection_matches("Car", &car_only, &ctx));
1377 2 : assert!(type_selection_matches("Bus,Car", &car_only, &ctx));
1378 2 : assert!(type_selection_matches("Bus|Car", &car_only, &ctx));
1379 2 : assert!(type_selection_matches("(Car;Bus)", &both, &ctx));
1380 2 : assert!(!type_selection_matches("(Car;Bus)", &car_only, &ctx));
1381 2 : assert!(!type_selection_matches("Bus", &[], &ctx));
1382 2 : }
1383 :
1384 : /// 4.17 grammar: no empty EntityType, parentheses only around an
1385 : /// and-group, `;` only inside one (Coraine query_entities_errors).
1386 : #[test]
1387 2 : fn type_selection_grammar() {
1388 14 : for ok in [
1389 2 : "Car",
1390 2 : "Bus,Car",
1391 2 : "Bus|Car",
1392 2 : "(Car;Bus)",
1393 2 : "(Home;Vehicle)|Motorhome",
1394 2 : "https://e.org/T",
1395 2 : "(A)",
1396 2 : ] {
1397 14 : assert!(check_type_selection(ok).is_ok(), "{ok}");
1398 : }
1399 22 : for bad in [
1400 2 : "(A;)", "A;", ";A", "()", "A,", ",A", "A;;B", "(A;B", "A)", "((A))", "",
1401 2 : ] {
1402 22 : assert!(check_type_selection(bad).is_err(), "{bad}");
1403 : }
1404 2 : }
1405 :
1406 : /// 5.6.21.4: the referenced top-level names in source order, whether any
1407 : /// path hops a Linked Entity, and the deepest hop chain.
1408 : #[test]
1409 2 : fn referenced_paths_and_link_depth() {
1410 2 : let q = parse_q("speed>1;(brand==\"x\"|sensor{humidity}==2);!owner").expect("parse");
1411 2 : assert_eq!(q.attribute_paths(), ["speed", "brand", "sensor", "owner"]);
1412 2 : assert!(q.has_linked_paths());
1413 2 : assert_eq!(q.max_link_depth(), 1);
1414 2 : let flat = parse_q("speed>1|brand==\"x\"").expect("parse");
1415 2 : assert!(!flat.has_linked_paths());
1416 2 : assert_eq!(flat.max_link_depth(), 0);
1417 2 : assert!(is_non_system_attr("speed"));
1418 16 : for sys in SYSTEM_ATTRS {
1419 16 : assert!(!is_non_system_attr(sys), "{sys}");
1420 : }
1421 2 : }
1422 :
1423 : /// The unquoted value: `false` is a Boolean, an empty value is refused,
1424 : /// and a `..` past the next separator belongs to the next term.
1425 : #[test]
1426 2 : fn unquoted_scalars_and_where_a_range_stops() {
1427 2 : assert!(matches!(
1428 2 : parse_q("a==false").expect("parse"),
1429 : QNode::Cmp {
1430 : value: QValue::Bool(false),
1431 : ..
1432 : }
1433 : ));
1434 2 : assert!(parse_q("a==").is_err());
1435 2 : assert!(parse_q("a==;b==1").is_err());
1436 2 : let range = parse_q("a==1;b==2..3").expect("parse");
1437 2 : assert_eq!(range, parse_q("(a==1);(b==2..3)").expect("parse"));
1438 2 : assert!(
1439 2 : matches!(&range, QNode::And(terms) if terms.len() == 2),
1440 : "{range:?}"
1441 : );
1442 2 : }
1443 :
1444 : /// The byte ceiling is inclusive: MAX_Q_BYTES parses, one more is
1445 : /// TooComplexQuery (`>` → `>=`).
1446 : #[test]
1447 2 : fn a_query_of_exactly_the_byte_ceiling_parses() {
1448 6 : let at = |n: usize| format!("a==\"{}\"", "x".repeat(n - 5));
1449 2 : assert_eq!(at(MAX_Q_BYTES).len(), MAX_Q_BYTES);
1450 2 : assert!(parse_q(&at(MAX_Q_BYTES)).is_ok());
1451 2 : assert!(matches!(
1452 2 : parse_q(&at(MAX_Q_BYTES + 1)),
1453 : Err(NgsiError::TooComplexQuery(_))
1454 : ));
1455 2 : }
1456 :
1457 : /// The node budget: a flat chain within the depth limit but past
1458 : /// MAX_Q_NODES is 400 TooComplexQuery, one node fewer parses.
1459 : #[test]
1460 2 : fn a_query_past_the_node_budget_is_too_complex() {
1461 4 : let chain = |n: usize| vec!["a==1"; n].join(";");
1462 2 : assert!(parse_q(&chain(MAX_Q_NODES - 1)).is_ok());
1463 2 : assert!(matches!(
1464 2 : parse_q(&chain(MAX_Q_NODES)),
1465 : Err(NgsiError::TooComplexQuery(_))
1466 : ));
1467 2 : }
1468 :
1469 : /// Threat V23: the narrowed caps are the caller's and the policy's
1470 : /// summed. The largest, the deepest and the longest-rendering `q` a
1471 : /// caller may send, each term rewritten as a hidden one (`(a;!a)`) and
1472 : /// joined with the largest and the deepest policy `q` that fits, still
1473 : /// parse, so the policy's size decides no caller's answer.
1474 : #[test]
1475 : #[cfg_attr(miri, ignore)] // a cap-sized input: past the weekly Miri job's 90 min
1476 2 : fn every_join_of_an_accepted_q_and_a_fitting_policy_parses() {
1477 4388 : fn hidden(n: QNode) -> QNode {
1478 4388 : match n {
1479 136 : QNode::And(xs) => QNode::And(xs.into_iter().map(hidden).collect()),
1480 128 : QNode::Or(xs) => QNode::Or(xs.into_iter().map(hidden).collect()),
1481 4124 : _ => QNode::And(vec![parse_q("a").expect("a"), parse_q("!a").expect("!a")]),
1482 : }
1483 4388 : }
1484 264 : let leaf = || parse_q("b==1").expect("leaf");
1485 2 : let mut deep = "a==1".to_owned();
1486 128 : for i in 0..MAX_Q_DEPTH {
1487 128 : deep = format!("a==1{}({deep})", if i % 2 == 0 { ';' } else { '|' });
1488 : }
1489 2 : let callers = [
1490 2 : vec!["a==1"; MAX_Q_NODES - 1].join(";"),
1491 2 : deep,
1492 2 : vec!["a==1e300"; MAX_Q_BYTES / 9].join(";"),
1493 2 : ];
1494 2 : let wide = QNode::Or(vec![leaf(); MAX_POLICY_Q_NODES - 1]);
1495 : // bounded, so a `paren_depth` that stops counting fails here rather
1496 : // than loop (the mutants that did timed out)
1497 2 : let mut tall = QNode::And(vec![leaf(), leaf()]);
1498 2 : for _ in 0..MAX_NARROWED_Q_DEPTH {
1499 256 : if paren_depth(&tall) >= MAX_NARROWED_Q_DEPTH - 1 {
1500 2 : break;
1501 254 : }
1502 254 : tall = QNode::And(vec![leaf(), tall]);
1503 : }
1504 2 : assert_eq!(paren_depth(&tall), MAX_NARROWED_Q_DEPTH - 1);
1505 4 : for policy in [&wide, &tall] {
1506 4 : assert!(fits_policy_q(policy));
1507 12 : for caller in &callers {
1508 12 : let own = parse_q(caller).expect("an accepted q");
1509 24 : for own in [hidden(own.clone()), own] {
1510 24 : let joined = QNode::And(vec![own, policy.clone()]).to_string();
1511 24 : assert!(parse_narrowed_q(&joined).is_ok(), "{}", &joined[..64]);
1512 : }
1513 : }
1514 : }
1515 : // the last rendering is past the caller's byte cap, which does not
1516 : // apply to the broker's own text
1517 2 : assert!(callers[2].len() <= MAX_Q_BYTES);
1518 2 : assert!(parse_q(&callers[2]).expect("q").to_string().len() > MAX_Q_BYTES);
1519 : // one node or one level more is a policy that does not fit
1520 2 : assert!(!fits_policy_q(&QNode::Or(vec![leaf(); MAX_POLICY_Q_NODES])));
1521 2 : assert!(!fits_policy_q(&QNode::And(vec![leaf(), tall])));
1522 2 : }
1523 :
1524 : /// `paren_depth` counts the parentheses the renderer writes: a group
1525 : /// inside `;`, an `|` inside `|`, never a `;` inside `|`.
1526 : #[test]
1527 2 : fn paren_depth_is_the_rendered_one() {
1528 10 : for (q, depth) in [
1529 2 : ("a", 0),
1530 2 : ("a|b;c", 0),
1531 2 : ("a;(b|c)", 1),
1532 2 : ("a|(b|c)", 1),
1533 2 : ("a;(b;(c|d))", 2),
1534 2 : ] {
1535 10 : let node = parse_q(q).expect("q");
1536 10 : assert_eq!(paren_depth(&node), depth, "{q}");
1537 10 : let rendered = node.to_string();
1538 10 : let mut open = 0usize;
1539 62 : let deepest = rendered.chars().fold(0, |deepest, c| {
1540 62 : open = match c {
1541 8 : '(' => open + 1,
1542 8 : ')' => open - 1,
1543 46 : _ => open,
1544 : };
1545 62 : deepest.max(open)
1546 62 : });
1547 10 : assert_eq!(deepest, depth, "{rendered}");
1548 : }
1549 2 : }
1550 :
1551 : /// How the narrowed caps are made up: the depth is the
1552 : /// caller's twice over, half for the caller's part and its rewrite,
1553 : /// half for the policy; the nodes are the caller's rewritten part (each
1554 : /// term at most three), the conjunction, and the policy share, to the
1555 : /// node. Each cap is used symbolically everywhere else, so only these
1556 : /// equations notice one drifting.
1557 : #[test]
1558 2 : fn the_narrowed_caps_add_up() {
1559 2 : assert_eq!(MAX_NARROWED_Q_DEPTH, 2 * MAX_Q_DEPTH);
1560 2 : assert_eq!(
1561 2 : 3 * MAX_Q_NODES + 1 + MAX_POLICY_Q_NODES,
1562 : MAX_NARROWED_Q_NODES
1563 : );
1564 2 : }
1565 :
1566 : /// Parsing grows with the `q`, not with its square: each unquoted value
1567 : /// once looked for the Range `..` across the whole rest, so a chain of
1568 : /// `n` comparisons scanned n²/2 terms (the Miri job ran out of
1569 : /// time inside one 511-term parse). Eight parses of a chain against one
1570 : /// parse of a chain eight times as long: linear, the two take the same
1571 : /// time (measured 1.04 to 1.24, also beside twelve busy cores); the old
1572 : /// scan took 5.1 times as long. Both are timed alternately and of about
1573 : /// the same length, so a loaded host slows both alike (one small
1574 : /// and one large parse drifted from 9 to 18 under load, against a bound
1575 : /// of 20).
1576 : #[test]
1577 : #[cfg_attr(miri, ignore)] // a wall-clock ratio, measured natively
1578 2 : fn parsing_a_chain_grows_linearly() {
1579 : use std::time::{Duration, Instant};
1580 4 : let chain = |n: usize| vec!["a==1"; n].join(";");
1581 2 : let (small, large) = (chain(MAX_Q_NODES - 1), chain(MAX_NARROWED_Q_NODES - 1));
1582 2 : let (mut eight_small, mut one_large) = (Duration::MAX, Duration::MAX);
1583 2 : for _ in 0..31 {
1584 62 : let started = Instant::now();
1585 62 : for _ in 0..8 {
1586 496 : assert!(parse_narrowed_q(&small).is_ok());
1587 : }
1588 62 : eight_small = eight_small.min(started.elapsed());
1589 62 : let started = Instant::now();
1590 62 : assert!(parse_narrowed_q(&large).is_ok());
1591 62 : one_large = one_large.min(started.elapsed());
1592 : }
1593 2 : let ratio = one_large.as_secs_f64() / eight_small.as_secs_f64().max(1e-9);
1594 2 : assert!(
1595 2 : ratio < 2.5,
1596 : "one 8x chain took {ratio:.2}x eight short ones"
1597 : );
1598 2 : }
1599 :
1600 : /// The narrowed caps are ceilings too: past them a narrowed `q` is
1601 : /// TooComplexQuery, as a caller's is past [`MAX_Q_NODES`].
1602 : #[test]
1603 : #[cfg_attr(miri, ignore)] // a cap-sized input: past the weekly Miri job's 90 min
1604 2 : fn a_narrowed_q_past_its_caps_is_too_complex() {
1605 4 : let chain = |n: usize| vec!["a==1"; n].join(";");
1606 2 : assert!(parse_narrowed_q(&chain(MAX_NARROWED_Q_NODES - 1)).is_ok());
1607 2 : assert!(matches!(
1608 2 : parse_narrowed_q(&chain(MAX_NARROWED_Q_NODES)),
1609 : Err(NgsiError::TooComplexQuery(_))
1610 : ));
1611 6 : let nested = |d: usize| format!("{}a==1{}", "(".repeat(d), ")".repeat(d));
1612 2 : assert!(parse_narrowed_q(&nested(MAX_NARROWED_Q_DEPTH)).is_ok());
1613 2 : assert!(matches!(
1614 2 : parse_narrowed_q(&nested(MAX_NARROWED_Q_DEPTH + 1)),
1615 : Err(NgsiError::TooComplexQuery(_))
1616 : ));
1617 2 : assert!(matches!(
1618 2 : parse_q(&nested(MAX_Q_DEPTH + 1)),
1619 : Err(NgsiError::TooComplexQuery(_))
1620 : ));
1621 2 : }
1622 : }
1623 :
1624 : /// Two refusals of the grammar no other test spells, `<=` written back, and a `scope` member
1625 : /// of neither shape 4.19 reads.
1626 : #[cfg(test)]
1627 : mod edges {
1628 : use super::*;
1629 :
1630 : #[test]
1631 2 : fn grammar_edges_and_the_written_form() {
1632 4 : let said = |q: &str| parse_q(q).err().map(|e| e.to_string()).unwrap_or_default();
1633 2 : assert!(
1634 2 : said("sensor{Device,Car}==1").contains("expected ':'"),
1635 : "{}",
1636 0 : said("sensor{Device,Car}==1")
1637 : );
1638 2 : assert!(
1639 2 : said(r#"a~="abc"#).contains("unterminated string"),
1640 : "{}",
1641 0 : said(r#"a~="abc"#)
1642 : );
1643 2 : assert_eq!(parse_q("a<=1").expect("parse").to_string(), "a<=1");
1644 2 : assert!(!scope::scope_matches(
1645 2 : "/a",
1646 2 : &serde_json::json!({"scope": 5})
1647 2 : ));
1648 2 : }
1649 : }
|
