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 : #![cfg_attr(not(test), warn(clippy::expect_used))]
12 : #![deny(missing_docs)]
13 : #![cfg_attr(test, allow(clippy::unwrap_used))]
14 :
15 : pub mod eval;
16 : pub mod geo;
17 : pub mod regex;
18 : mod render;
19 : pub mod scope;
20 : pub mod sql;
21 :
22 : use antares_model::NgsiError;
23 :
24 : /// Entity Type Selection Language (4.17) match against expanded type IRIs:
25 : /// `,`/`|` = OR of alternatives, `(a;b)` = AND within one alternative.
26 562 : pub fn type_selection_matches(sel: &str, types: &[&str], ctx: &antares_jsonld::Context) -> bool {
27 598 : sel.split([',', '|']).any(|alt| {
28 598 : alt.trim()
29 598 : .trim_start_matches('(')
30 598 : .trim_end_matches(')')
31 598 : .split(';')
32 630 : .all(|t| types.contains(&ctx.expand_key(t.trim()).as_str()))
33 598 : })
34 562 : }
35 :
36 : /// RFC 3986 percent-decoding of a query value (`q`, `scopeQ` in a
37 : /// subscription body may arrive encoded, 4.9).
38 12818 : pub fn percent_decode(input: &[u8]) -> String {
39 12818 : let mut out = Vec::with_capacity(input.len());
40 12818 : let mut i = 0;
41 117504 : while i < input.len() {
42 104686 : if input[i] == b'%' && i + 2 < input.len() {
43 : // from_str_radix accepts a leading sign, so "%+1" would decode as
44 : // 0x01. RFC 3986 clause 2.1 admits two hex digits and nothing else.
45 2598 : let hex = std::str::from_utf8(&input[i + 1..i + 3])
46 2598 : .ok()
47 5184 : .filter(|h| h.bytes().all(|b| b.is_ascii_hexdigit()));
48 2598 : if let Some(b) = hex.and_then(|h| u8::from_str_radix(h, 16).ok()) {
49 2586 : out.push(b);
50 2586 : i += 3;
51 2586 : continue;
52 12 : }
53 102088 : }
54 102100 : out.push(input[i]);
55 102100 : i += 1;
56 : }
57 12818 : String::from_utf8_lossy(&out).into_owned()
58 12818 : }
59 :
60 : /// One parsed 4.9 query expression.
61 : #[derive(Debug, Clone, PartialEq, serde::Serialize)]
62 : pub enum QNode {
63 : /// `a;b` — every operand must hold.
64 : And(Vec<QNode>),
65 : /// `a|b` — any operand holds.
66 : Or(Vec<QNode>),
67 : /// `path op value` — one comparison term.
68 : Cmp {
69 : /// The attribute (path) the term targets.
70 : path: QPath,
71 : /// The comparison operator.
72 : op: CmpOp,
73 : /// The literal compared against.
74 : value: QValue,
75 : },
76 : /// Bare attribute path = existence check (`q=temperature`).
77 : Exists {
78 : /// The attribute (path) whose presence is tested.
79 : path: QPath,
80 : /// `!path` — the attribute must be absent.
81 : negated: bool,
82 : },
83 : }
84 :
85 : /// 4.9 `Attribute = LinkedEntityRelation` — zero or more `attr{[T[,T]:]…}`
86 : /// hops (EXAMPLE 13/14), then `ValuePath = DottedPath *1([DottedPath])`:
87 : /// a dotted path plus an optional single trailing bracket that is either a
88 : /// compound-value member path (EXAMPLE 9/10/11) or a language filter
89 : /// (`[en]` / `[*]`, Equal/Unequal languageMap semantics).
90 : #[derive(Debug, Clone, PartialEq, serde::Serialize)]
91 : pub struct QPath {
92 : /// Linked-entity hops (`attr{…}`) preceding the path, outermost first.
93 : pub links: Vec<Link>,
94 : /// The dotted attribute path (terms, expanded at evaluation time).
95 : pub path: Vec<String>,
96 : /// The optional trailing `[…]`: a compound-value member path, or a
97 : /// language filter (`[en]`, `[*]`).
98 : pub bracket: Option<Vec<String>>,
99 : }
100 :
101 : /// One `attr{…}` linked-entity hop with its optional EntityType hints.
102 : #[derive(Debug, Clone, PartialEq, serde::Serialize)]
103 : pub struct Link {
104 : /// The Relationship followed.
105 : pub attr: String,
106 : /// EntityType hints (`attr{T1,T2:…}`), empty when none.
107 : pub types: Vec<String>,
108 : }
109 :
110 : impl QPath {
111 : /// Plain dotted path (the pre-4.9-extension shape).
112 32 : pub fn dotted(path: Vec<String>) -> Self {
113 32 : Self {
114 32 : links: Vec::new(),
115 32 : path,
116 32 : bracket: None,
117 32 : }
118 32 : }
119 :
120 : /// The top-level Attribute name this path filters on.
121 416 : pub fn top(&self) -> Option<&str> {
122 416 : self.links
123 416 : .first()
124 416 : .map(|l| l.attr.as_str())
125 416 : .or_else(|| self.path.first().map(String::as_str))
126 416 : }
127 : }
128 :
129 : impl QNode {
130 : /// Every top-level attribute name this expression references, in source
131 : /// order.
132 : ///
133 : /// Purge (5.6.21.4 b/c) qualifies an `attrs` list or a `q` only when it
134 : /// includes "at least one non-system Attribute", so the caller needs the
135 : /// referenced names rather than just "is there a q".
136 356 : pub fn attribute_paths(&self) -> Vec<&str> {
137 356 : let mut out = Vec::new();
138 356 : self.collect_paths(&mut out);
139 356 : out
140 356 : }
141 :
142 : /// True when any referenced Attribute path uses a `attr{…}` linked-entity
143 : /// hop (4.9 LinkedEntityRelation). Purge (5.6.21.4) must reject filter
144 : /// conditions that include Linked Entity attributes.
145 12 : pub fn has_linked_paths(&self) -> bool {
146 12 : match self {
147 0 : QNode::And(ns) | QNode::Or(ns) => ns.iter().any(Self::has_linked_paths),
148 12 : QNode::Cmp { path, .. } | QNode::Exists { path, .. } => !path.links.is_empty(),
149 : }
150 12 : }
151 :
152 : /// Deepest chain of `attr{…}` hops any referenced path uses — the number
153 : /// of Linked Entity levels the query needs (5.7.2.4: must not exceed
154 : /// joinLevel).
155 338 : pub fn max_link_depth(&self) -> usize {
156 338 : match self {
157 18 : QNode::And(ns) | QNode::Or(ns) => {
158 30 : ns.iter().map(Self::max_link_depth).max().unwrap_or(0)
159 : }
160 308 : QNode::Cmp { path, .. } | QNode::Exists { path, .. } => path.links.len(),
161 : }
162 338 : }
163 :
164 412 : fn collect_paths<'a>(&'a self, out: &mut Vec<&'a str>) {
165 412 : match self {
166 16 : QNode::And(ns) | QNode::Or(ns) => {
167 56 : for n in ns {
168 56 : n.collect_paths(out);
169 56 : }
170 : }
171 384 : QNode::Cmp { path, .. } | QNode::Exists { path, .. } => out.extend(path.top()),
172 : }
173 412 : }
174 : }
175 :
176 : /// System-generated members that never count as a "non-system Attribute"
177 : /// (5.6.21.4). `id`/`type`/`scope` are Entity members, the timestamps are the
178 : /// system temporal attributes of 6.3.11.
179 : pub const SYSTEM_ATTRS: &[&str] = &[
180 : "id",
181 : "type",
182 : "scope",
183 : "createdAt",
184 : "modifiedAt",
185 : "expiresAt",
186 : "deletedAt",
187 : "instanceId",
188 : ];
189 :
190 : /// True when `name` is an ordinary (non-system) Attribute name.
191 366 : pub fn is_non_system_attr(name: &str) -> bool {
192 366 : !SYSTEM_ATTRS.contains(&name)
193 366 : }
194 :
195 : /// The 4.9 comparison operators.
196 : #[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
197 : pub enum CmpOp {
198 : /// `==`
199 : Eq,
200 : /// `!=`
201 : Ne,
202 : /// `>`
203 : Gt,
204 : /// `>=`
205 : Ge,
206 : /// `<`
207 : Lt,
208 : /// `<=`
209 : Le,
210 : /// `~=` (patternOp)
211 : Pattern,
212 : /// `!~=` (notPatternOp)
213 : NotPattern,
214 : }
215 :
216 : /// A query term literal.
217 : #[derive(Debug, Clone, PartialEq, serde::Serialize)]
218 : pub enum QValue {
219 : /// A string (quoted, or an unquoted non-numeric token such as a date).
220 : Str(String),
221 : /// A number.
222 : Num(f64),
223 : /// `true` / `false`.
224 : Bool(bool),
225 : /// 4.9 `ValueList = Value 1*(, Value)` — scalars only, `==`/`!=` only.
226 : List(Vec<QValue>),
227 : /// 4.9 `Range = ComparableValue dots ComparableValue` — `==`/`!=` only.
228 : /// Endpoints are the same scalar variant (Num..Num or Str..Str; dates and
229 : /// times ride in Str and order correctly because 4.6.3 pins them to
230 : /// fixed-width UTC forms).
231 : Range(Box<QValue>, Box<QValue>),
232 : }
233 :
234 : /// Longest `q=` accepted, before parsing. The URI cap is 8 KiB but a POST
235 : /// query body carries `q` too, where the only other ceiling is the 4 MiB body
236 : /// limit — so the string needs its own bound at the one entry point.
237 : const MAX_Q_BYTES: usize = 4096;
238 :
239 : /// Nesting depth ceiling. `(` costs three stack frames (`or_expr` → `and_expr`
240 : /// → `term`), and a Rust stack overflow is a guard-page abort, NOT a catchable
241 : /// panic — no tower layer can contain it, so the parser must refuse before it
242 : /// recurses rather than be rescued afterwards. 64 is far past any real query
243 : /// and far below the ~2 MiB tokio worker stack.
244 : const MAX_Q_DEPTH: usize = 64;
245 :
246 : /// AST size cap — checked after parsing, which is safe once depth and
247 : /// length are bounded first. Public because `/q/health` publishes it: a
248 : /// second constant carrying the same number is one that can drift from the
249 : /// one actually enforced.
250 : pub const MAX_Q_NODES: usize = 512;
251 :
252 : /// Parse an NGSI-LD `q=` expression. Complexity ceilings raise
253 : /// TooComplexQuery per 5.5.6 ("a query operation … so complex that cannot
254 : /// be resolved").
255 3979 : pub fn parse_q(input: &str) -> Result<QNode, NgsiError> {
256 3979 : if input.len() > MAX_Q_BYTES {
257 6 : return Err(NgsiError::TooComplexQuery(format!(
258 6 : "q expression exceeds {MAX_Q_BYTES} bytes"
259 6 : )));
260 3973 : }
261 3973 : let mut p = Parser {
262 3973 : rest: input.trim(),
263 3973 : depth: 0,
264 3973 : };
265 3973 : let node = p.or_expr()?;
266 3813 : if !p.rest.is_empty() {
267 8 : return Err(bad(input, "trailing input"));
268 3805 : }
269 3805 : if q_nodes(&node) > MAX_Q_NODES {
270 4 : return Err(NgsiError::TooComplexQuery(format!(
271 4 : "q expression exceeds {MAX_Q_NODES} nodes"
272 4 : )));
273 3801 : }
274 3801 : Ok(node)
275 3979 : }
276 :
277 : /// 4.9 p.85: "`Number` shall be a number as mandated by the JSON
278 : /// Specification, following the ABNF Grammar, production rule named `number`,
279 : /// section 6 of IETF RFC 8259" — `[minus] int [frac] [exp]`, the int without
280 : /// a leading zero, the fraction and the exponent with at least one digit each.
281 : /// A float parse is much wider: `+5`, `01`, `.5`, `5.`, `NaN` and `inf` all
282 : /// come back as numbers from it and none of them is a Number here, so each
283 : /// would compare against a number where the term named text.
284 7687 : fn is_json_number(s: &str) -> bool {
285 7687 : let s = s.strip_prefix('-').unwrap_or(s);
286 8833 : let digits = |t: &str| t.len() - t.trim_start_matches(|c: char| c.is_ascii_digit()).len();
287 7687 : let int = digits(s);
288 7687 : if int == 0 || (int > 1 && s.starts_with('0')) {
289 102 : return false;
290 7585 : }
291 7585 : let rest = &s[int..];
292 7585 : let rest = match rest.strip_prefix('.') {
293 7557 : None => rest,
294 28 : Some(frac) => match digits(frac) {
295 2 : 0 => return false,
296 26 : n => &frac[n..],
297 : },
298 : };
299 7583 : match rest.strip_prefix(['e', 'E']) {
300 7573 : None => rest.is_empty(),
301 10 : Some(exp) => {
302 10 : let exp = exp.strip_prefix(['+', '-']).unwrap_or(exp);
303 10 : !exp.is_empty() && digits(exp) == exp.len()
304 : }
305 : }
306 7687 : }
307 :
308 8753 : fn q_nodes(n: &QNode) -> usize {
309 8753 : match n {
310 235 : QNode::And(xs) | QNode::Or(xs) => 1 + xs.iter().map(q_nodes).sum::<usize>(),
311 8518 : _ => 1,
312 : }
313 8753 : }
314 :
315 160 : fn bad(input: &str, why: &str) -> NgsiError {
316 160 : NgsiError::BadRequestData(format!("invalid q expression {input:?}: {why}"))
317 160 : }
318 :
319 : struct Parser<'a> {
320 : rest: &'a str,
321 : /// open parentheses currently on the stack (see `MAX_Q_DEPTH`)
322 : depth: usize,
323 : }
324 :
325 : impl<'a> Parser<'a> {
326 4855 : fn or_expr(&mut self) -> Result<QNode, NgsiError> {
327 4855 : let first = self.and_expr()?;
328 4379 : let mut rest = Vec::new();
329 8557 : while self.eat('|') {
330 4178 : rest.push(self.and_expr()?);
331 : }
332 4379 : Ok(if rest.is_empty() {
333 4281 : first
334 : } else {
335 98 : QNode::Or(std::iter::once(first).chain(rest).collect())
336 : })
337 4855 : }
338 :
339 9033 : fn and_expr(&mut self) -> Result<QNode, NgsiError> {
340 9033 : let first = self.term()?;
341 8557 : let mut rest = Vec::new();
342 9092 : while self.eat(';') {
343 535 : rest.push(self.term()?);
344 : }
345 8557 : Ok(if rest.is_empty() {
346 8420 : first
347 : } else {
348 137 : QNode::And(std::iter::once(first).chain(rest).collect())
349 : })
350 9033 : }
351 :
352 9568 : fn term(&mut self) -> Result<QNode, NgsiError> {
353 9568 : if self.eat('(') {
354 : // refuse BEFORE recursing — an overflow here aborts the process
355 886 : self.depth += 1;
356 886 : if self.depth > MAX_Q_DEPTH {
357 4 : return Err(NgsiError::TooComplexQuery(format!(
358 4 : "q expression nests deeper than {MAX_Q_DEPTH}"
359 4 : )));
360 882 : }
361 882 : let node = self.or_expr()?;
362 566 : self.depth -= 1;
363 566 : if !self.eat(')') {
364 2 : return Err(bad(self.rest, "expected ')'"));
365 564 : }
366 564 : return Ok(node);
367 8682 : }
368 8682 : let negated = self.eat('!');
369 8682 : let path = self.qpath()?;
370 8584 : if let Some(op) = self.cmp_op() {
371 8476 : if negated {
372 2 : return Err(bad(self.rest, "'!' only prefixes an existence check"));
373 8474 : }
374 8474 : let value = self.value(op)?;
375 8420 : Ok(QNode::Cmp { path, op, value })
376 : } else {
377 108 : Ok(QNode::Exists { path, negated })
378 : }
379 9568 : }
380 :
381 : /// 4.9 Attribute: `attr{[T[,T]:]…}` linked-entity hops, then a dotted
382 : /// path, then at most one trailing `[member.path]` / `[lang]` / `[*]`.
383 8682 : fn qpath(&mut self) -> Result<QPath, NgsiError> {
384 8682 : let mut links = Vec::new();
385 8682 : let mut braces = 0usize;
386 8682 : let mut name = self.name_token()?;
387 : // LinkedEntityRelation: AttrName{ [EntityType(,EntityType)*:] … }
388 8796 : while self.eat('{') {
389 204 : braces += 1;
390 204 : if braces > 8 {
391 4 : return Err(NgsiError::TooComplexQuery(
392 4 : "q linked-entity path nests deeper than 8".into(),
393 4 : ));
394 200 : }
395 200 : let mut types = Vec::new();
396 200 : let mut inner = self.name_token()?;
397 194 : if self.rest.starts_with(',') || self.rest.starts_with(':') {
398 10 : types.push(inner);
399 14 : while self.eat(',') {
400 4 : types.push(self.name_token()?);
401 : }
402 10 : if !self.eat(':') {
403 0 : return Err(bad(self.rest, "expected ':' after EntityType hints"));
404 10 : }
405 10 : inner = self.name_token()?;
406 184 : }
407 194 : links.push(Link { attr: name, types });
408 194 : name = inner;
409 : }
410 8592 : let mut path = vec![name];
411 8616 : while self.eat('.') {
412 26 : path.push(self.name_token()?);
413 : }
414 8590 : let bracket = if self.eat('[') {
415 118 : let b = if self.eat('*') {
416 34 : vec!["*".to_owned()]
417 : } else {
418 84 : let mut b = vec![self.name_token()?];
419 86 : while self.eat('.') {
420 6 : b.push(self.name_token()?);
421 : }
422 80 : b
423 : };
424 114 : if !self.eat(']') {
425 0 : return Err(bad(self.rest, "expected ']'"));
426 114 : }
427 114 : Some(b)
428 : } else {
429 8472 : None
430 : };
431 8586 : for _ in 0..braces {
432 162 : if !self.eat('}') {
433 2 : return Err(bad(self.rest, "expected '}'"));
434 160 : }
435 : }
436 8584 : Ok(QPath {
437 8584 : links,
438 8584 : path,
439 8584 : bracket,
440 8584 : })
441 8682 : }
442 :
443 : /// One path segment: everything up to a structural delimiter.
444 9012 : fn name_token(&mut self) -> Result<String, NgsiError> {
445 9012 : self.rest = self.rest.trim_start();
446 9012 : let end = self
447 9012 : .rest
448 45017 : .find(|c: char| "=!<>~;|(),.{}[]: ".contains(c))
449 9012 : .unwrap_or(self.rest.len());
450 9012 : let (raw, rest) = self.rest.split_at(end);
451 9012 : if raw.is_empty() {
452 92 : return Err(bad(rest, "expected attribute name"));
453 8920 : }
454 : // spacing around the segment is insignificant (`a ==1`, `a ; b`)
455 8920 : self.rest = rest.trim_start();
456 8920 : Ok(raw.to_owned())
457 9012 : }
458 :
459 8584 : fn cmp_op(&mut self) -> Option<CmpOp> {
460 26998 : for (tok, op) in [
461 8584 : ("==", CmpOp::Eq),
462 8584 : // "!~=" before "!=" — the longer token must win the prefix race
463 8584 : ("!~=", CmpOp::NotPattern),
464 8584 : ("!=", CmpOp::Ne),
465 8584 : ("~=", CmpOp::Pattern),
466 8584 : (">=", CmpOp::Ge),
467 8584 : ("<=", CmpOp::Le),
468 8584 : (">", CmpOp::Gt),
469 8584 : ("<", CmpOp::Lt),
470 8584 : ] {
471 26998 : if let Some(rest) = self.rest.strip_prefix(tok) {
472 8476 : self.rest = rest;
473 8476 : return Some(op);
474 18522 : }
475 : }
476 108 : None
477 8584 : }
478 :
479 : /// Query Term value for `op` — 4.9 p.84 pairs them precisely:
480 : /// `Operator ComparableValue` (ordering), `equal/unequal CompEqualityValue`
481 : /// (adds true/false, ValueList, Range, URI), `patternOp/notPatternOp
482 : /// RegExp`. Lists and ranges with an ordering or pattern operator are a
483 : /// grammar violation, not an empty result.
484 8474 : fn value(&mut self, op: CmpOp) -> Result<QValue, NgsiError> {
485 : // 4.9: `patternOp`/`notPatternOp` take a `RegExp` (IEEE 1003.2), not
486 : // a `quotedStr`, so the operand is the pattern text as written — a
487 : // backslash in it belongs to the regular expression and is not an
488 : // RFC 8259 escape. Every other operand is a `quotedStr`, a Number, a
489 : // 4.6.3 dateTime/date/time or a URI.
490 8474 : let regexp = matches!(op, CmpOp::Pattern | CmpOp::NotPattern);
491 8474 : let first = self.scalar(regexp)?;
492 8438 : let equality = matches!(op, CmpOp::Eq | CmpOp::Ne);
493 8438 : self.rest = self.rest.trim_start();
494 8438 : if let Some(rest) = self.rest.strip_prefix("..") {
495 74 : if !equality {
496 2 : return Err(bad(
497 2 : self.rest,
498 2 : "a Range is only valid with == or != (4.9 CompEqualityValue)",
499 2 : ));
500 72 : }
501 72 : self.rest = rest.trim_start();
502 72 : let hi = self.scalar(false)?;
503 : // Range = ComparableValue..ComparableValue: booleans excluded, and
504 : // an order relation needs both endpoints in one value space
505 70 : if std::mem::discriminant(&first) != std::mem::discriminant(&hi)
506 66 : || matches!(first, QValue::Bool(_))
507 : {
508 6 : return Err(bad(
509 6 : self.rest,
510 6 : "Range endpoints must be two comparable values of the same type",
511 6 : ));
512 64 : }
513 64 : return Ok(QValue::Range(Box::new(first), Box::new(hi)));
514 8364 : }
515 8364 : if self.rest.starts_with(',') {
516 80 : if !equality {
517 4 : return Err(bad(
518 4 : self.rest,
519 4 : "a ValueList is only valid with == or != (4.9 CompEqualityValue)",
520 4 : ));
521 76 : }
522 76 : let mut items = vec![first];
523 152 : while self.eat(',') {
524 78 : self.rest = self.rest.trim_start();
525 78 : items.push(self.scalar(false)?);
526 76 : self.rest = self.rest.trim_start();
527 : }
528 74 : return Ok(QValue::List(items));
529 8284 : }
530 8284 : if matches!(op, CmpOp::Gt | CmpOp::Ge | CmpOp::Lt | CmpOp::Le)
531 2836 : && matches!(first, QValue::Bool(_))
532 : {
533 2 : return Err(bad(
534 2 : self.rest,
535 2 : "true/false are only valid with == or != (4.9 OtherValue)",
536 2 : ));
537 8282 : }
538 8282 : Ok(first)
539 8474 : }
540 :
541 : /// One scalar literal. Unquoted tokens stop at a delimiter or at `..`
542 : /// (the Range separator) — a decimal like `10.5` has no `..`, so
543 : /// `10.5..20.5` still splits at the right place.
544 : ///
545 : /// `regexp` selects the grammar the quoted form follows: a `RegExp`
546 : /// operand is taken as written, everything else is a `quotedStr`, i.e.
547 : /// "a text string as mandated by the JSON Specification, following the
548 : /// ABNF Grammar, production rule named String, section 7 of IETF
549 : /// RFC 8259" — escapes included, decoded to the text the term compares
550 : /// against, which is how the entity member reached the store too.
551 8624 : fn scalar(&mut self, regexp: bool) -> Result<QValue, NgsiError> {
552 : // The clause writes its own examples with a space before the value
553 : // (`color!= "black", "red"`, p.90). Deciding quoted-vs-unquoted on an
554 : // untrimmed head read that as an unquoted token and kept the quotes
555 : // INSIDE the value, so the term matched a value literally spelled
556 : // with them.
557 8624 : self.rest = self.rest.trim_start();
558 8624 : if self.rest.starts_with('"') {
559 889 : if regexp {
560 141 : let rest = &self.rest[1..];
561 141 : let end = rest
562 141 : .find('"')
563 141 : .ok_or_else(|| bad(rest, "unterminated string"))?;
564 141 : let (s, rest) = rest.split_at(end);
565 141 : self.rest = &rest[1..];
566 141 : return Ok(QValue::Str(s.to_owned()));
567 748 : }
568 748 : let end = Self::json_string_end(self.rest)
569 748 : .ok_or_else(|| bad(self.rest, "unterminated string"))?;
570 738 : let (lit, rest) = self.rest.split_at(end);
571 738 : let s: String = serde_json::from_str(lit)
572 738 : .map_err(|_| bad(lit, "value is not an RFC 8259 String (4.9 quotedStr)"))?;
573 732 : self.rest = rest;
574 732 : return Ok(QValue::Str(s));
575 7735 : }
576 7735 : let stop = self
577 7735 : .rest
578 15824 : .find(|c: char| ";|(),".contains(c))
579 7735 : .unwrap_or(self.rest.len());
580 7735 : let end = match self.rest.find("..") {
581 76 : Some(d) if d < stop => d,
582 7659 : _ => stop,
583 : };
584 7735 : let (raw, rest) = self.rest.split_at(end);
585 7735 : let raw = raw.trim();
586 : // The unquoted alternatives are `dateTime`/`date`/`time` (4.6.3), a
587 : // Number and a `URI` (RFC 3986). None of them admits a `\"`, so one
588 : // here is an unterminated `quotedStr`, not a value.
589 7735 : if !regexp && raw.contains('"') {
590 6 : return Err(bad(raw, "unquoted value must not contain a quote (4.9)"));
591 7729 : }
592 7729 : self.rest = rest;
593 7687 : match raw {
594 7729 : "true" => Ok(QValue::Bool(true)),
595 7697 : "false" => Ok(QValue::Bool(false)),
596 7687 : _ if is_json_number(raw) => match raw.parse::<f64>() {
597 7514 : Ok(n) => Ok(QValue::Num(n)),
598 0 : Err(_) => Ok(QValue::Str(raw.to_owned())),
599 : },
600 : // the other unquoted alternatives: a URI, a dateTime, a date or a
601 : // time, all of them compared as text
602 173 : "" => Err(bad(raw, "expected value")),
603 155 : _ => Ok(QValue::Str(raw.to_owned())),
604 : }
605 8624 : }
606 :
607 : /// Byte index one past the closing quote of the RFC 8259 string at the head
608 : /// of `s`, or `None` when it never closes. A quote is the closing one only
609 : /// when it is not itself escaped, so the scan skips the byte after every
610 : /// backslash — both are ASCII, so a skip can never land mid-character in a
611 : /// way that reads as either.
612 748 : fn json_string_end(s: &str) -> Option<usize> {
613 748 : let b = s.as_bytes();
614 748 : let mut i = 1;
615 5334 : while i < b.len() {
616 5324 : match b[i] {
617 40 : b'\\' => i += 2,
618 738 : b'"' => return Some(i + 1),
619 4546 : _ => i += 1,
620 : }
621 : }
622 10 : None
623 748 : }
624 :
625 63123 : fn eat(&mut self, c: char) -> bool {
626 63123 : if let Some(rest) = self.rest.strip_prefix(c) {
627 6960 : self.rest = rest;
628 6960 : true
629 : } else {
630 56163 : false
631 : }
632 63123 : }
633 : }
634 :
635 : #[cfg(test)]
636 : mod tests {
637 : use super::*;
638 :
639 : /// 4.9 p.85: "`Number` shall be a number as mandated by the JSON
640 : /// Specification, following the ABNF Grammar, production rule named
641 : /// `number`, section 6 of IETF RFC 8259" — an optional minus, an int with
642 : /// no leading zero, a fraction of at least one digit, an exponent of at
643 : /// least one digit. A plain float parse is far wider than that: it takes
644 : /// `+5`, `01`, `.5`, `5.`, `NaN` and `inf`, none of which is a Number.
645 : /// The other unquoted alternatives of `ComparableValue` and
646 : /// `CompEqualityValue` are `dateTime`/`date`/`time` and `URI`, all of
647 : /// which compare as text, so a token that is not a Number is a String.
648 : #[test]
649 2 : fn an_unquoted_token_is_a_number_only_when_rfc_8259_says_so() {
650 36 : for (q, want) in [
651 2 : ("x==5", QValue::Num(5.0)),
652 2 : ("x==-5", QValue::Num(-5.0)),
653 2 : ("x==0", QValue::Num(0.0)),
654 2 : ("x==0.5", QValue::Num(0.5)),
655 2 : ("x==1e3", QValue::Num(1000.0)),
656 2 : ("x==1E+3", QValue::Num(1000.0)),
657 2 : ("x==-2.5e-2", QValue::Num(-0.025)),
658 2 : // every one of these a plain float parse accepts and RFC 8259
659 2 : // does not
660 2 : ("x==+5", QValue::Str("+5".into())),
661 2 : ("x==01", QValue::Str("01".into())),
662 2 : ("x==.5", QValue::Str(".5".into())),
663 2 : ("x==5.", QValue::Str("5.".into())),
664 2 : ("x==NaN", QValue::Str("NaN".into())),
665 2 : ("x==nan", QValue::Str("nan".into())),
666 2 : ("x==inf", QValue::Str("inf".into())),
667 2 : ("x==-inf", QValue::Str("-inf".into())),
668 2 : ("x==infinity", QValue::Str("infinity".into())),
669 2 : ("x==1e", QValue::Str("1e".into())),
670 2 : ("x==-", QValue::Str("-".into())),
671 2 : ] {
672 36 : let QNode::Cmp { value, .. } = parse_q(q).expect(q) else {
673 0 : panic!("{q} is a comparison");
674 : };
675 36 : assert_eq!(value, want, "{q}");
676 : }
677 2 : }
678 :
679 : #[test]
680 2 : fn simple_comparison() {
681 2 : let q = parse_q(r#"brandName=="Mercedes""#).expect("parse");
682 2 : assert_eq!(
683 : q,
684 2 : QNode::Cmp {
685 2 : path: QPath::dotted(vec!["brandName".into()]),
686 2 : op: CmpOp::Eq,
687 2 : value: QValue::Str("Mercedes".into())
688 2 : }
689 : );
690 2 : }
691 :
692 : #[test]
693 2 : fn and_or_precedence() {
694 : // `a==1;b==2|c==3` == (a AND b) OR c per grammar: OR binds looser
695 2 : let q = parse_q("a==1;b==2|c==3").expect("parse");
696 2 : match q {
697 2 : QNode::Or(items) => {
698 2 : assert_eq!(items.len(), 2);
699 2 : assert!(matches!(items[0], QNode::And(_)));
700 : }
701 0 : other => panic!("expected Or, got {other:?}"),
702 : }
703 2 : }
704 :
705 : #[test]
706 2 : fn dotted_path_and_numbers() {
707 2 : let q = parse_q("speed.value>=80.5").expect("parse");
708 2 : assert_eq!(
709 : q,
710 2 : QNode::Cmp {
711 2 : path: QPath::dotted(vec!["speed".into(), "value".into()]),
712 2 : op: CmpOp::Ge,
713 2 : value: QValue::Num(80.5)
714 2 : }
715 : );
716 2 : }
717 :
718 : #[test]
719 2 : fn existence_and_negation() {
720 2 : assert_eq!(
721 2 : parse_q("!temperature").expect("parse"),
722 2 : QNode::Exists {
723 2 : path: QPath::dotted(vec!["temperature".into()]),
724 2 : negated: true
725 2 : }
726 : );
727 2 : }
728 :
729 : #[test]
730 2 : fn parens_group() {
731 2 : let q = parse_q("(a==1|b==2);c==3").expect("parse");
732 2 : assert!(matches!(q, QNode::And(_)));
733 2 : }
734 :
735 : #[test]
736 2 : fn rejects_garbage() {
737 8 : for bad in ["", "==5", "a==\"unterminated", "a==1)"] {
738 8 : assert!(parse_q(bad).is_err(), "should reject {bad:?}");
739 : }
740 2 : }
741 :
742 : #[test]
743 2 : fn value_list_parses_with_equality_ops_only() {
744 : // 4.9 p.85 ValueList = Value 1*(, Value); p.84 pairs it with ==/!= only
745 2 : let q = parse_q(r#"color=="black","red""#).expect("parse");
746 2 : assert_eq!(
747 : q,
748 2 : QNode::Cmp {
749 2 : path: QPath::dotted(vec!["color".into()]),
750 2 : op: CmpOp::Eq,
751 2 : value: QValue::List(vec![QValue::Str("black".into()), QValue::Str("red".into())])
752 2 : }
753 : );
754 : // spec's own spacing (`color!= "black", "red"`, p.90) must parse to
755 : // the same values — the space may not end up inside them, and neither
756 : // may the quotes that delimit them
757 2 : assert_eq!(
758 2 : parse_q(r#"color!= "black", "red""#).expect("parse"),
759 2 : QNode::Cmp {
760 2 : path: QPath::dotted(vec!["color".into()]),
761 2 : op: CmpOp::Ne,
762 2 : value: QValue::List(vec![QValue::Str("black".into()), QValue::Str("red".into())])
763 2 : }
764 : );
765 2 : assert_eq!(
766 2 : parse_q(r#"color== "black""#).expect("parse"),
767 2 : QNode::Cmp {
768 2 : path: QPath::dotted(vec!["color".into()]),
769 2 : op: CmpOp::Eq,
770 2 : value: QValue::Str("black".into())
771 2 : },
772 : "a single spaced value keeps neither the space nor the quotes"
773 : );
774 : // mixed scalar kinds are legal (ValueList is over Value)
775 2 : assert!(parse_q("a==1,2,3").is_ok());
776 : // ordering + list is a grammar violation → 400, not empty result
777 2 : assert!(parse_q(r#"a>"x","y""#).is_err());
778 2 : assert!(parse_q("a>=1,2").is_err());
779 2 : }
780 :
781 : #[test]
782 2 : fn range_parses_with_equality_ops_only() {
783 : // 4.9 p.85 Range = ComparableValue dots ComparableValue
784 2 : let q = parse_q("temperature==10..20").expect("parse");
785 2 : assert_eq!(
786 : q,
787 2 : QNode::Cmp {
788 2 : path: QPath::dotted(vec!["temperature".into()]),
789 2 : op: CmpOp::Eq,
790 2 : value: QValue::Range(Box::new(QValue::Num(10.0)), Box::new(QValue::Num(20.0)))
791 2 : }
792 : );
793 : // decimals keep their fraction; `..` is not mistaken for `.`
794 2 : let q = parse_q("t!=10.5..20.5").expect("parse");
795 2 : assert!(matches!(
796 2 : q,
797 : QNode::Cmp {
798 : op: CmpOp::Ne,
799 : value: QValue::Range(_, _),
800 : ..
801 : }
802 : ));
803 : // DateTime endpoints (unquoted, per EXAMPLE 8 style literals)
804 2 : let q = parse_q("observedAt==2021-01-01T00:00:00Z..2021-02-01T00:00:00Z").expect("parse");
805 2 : assert!(matches!(
806 2 : q,
807 : QNode::Cmp {
808 : value: QValue::Range(_, _),
809 : ..
810 : }
811 : ));
812 : // ordering + range violates the grammar; bools are not ComparableValue
813 2 : assert!(parse_q("a>1..5").is_err());
814 2 : assert!(parse_q("a==true..false").is_err());
815 2 : assert!(parse_q("a==1..\"x\"").is_err(), "mixed-type endpoints");
816 2 : }
817 :
818 : #[test]
819 2 : fn not_pattern_op() {
820 : // 4.9 p.85 notPatternOp = !~=
821 2 : let q = parse_q(r#"name!~="^Merc""#).expect("parse");
822 2 : assert_eq!(
823 : q,
824 2 : QNode::Cmp {
825 2 : path: QPath::dotted(vec!["name".into()]),
826 2 : op: CmpOp::NotPattern,
827 2 : value: QValue::Str("^Merc".into())
828 2 : }
829 : );
830 2 : }
831 :
832 : /// 4.9: `quotedStr = String`, and `String` "shall be a text string as
833 : /// mandated by the JSON Specification, following the ABNF Grammar,
834 : /// production rule named String, section 7 of IETF RFC 8259" — whose
835 : /// `char` production is `unescaped / escape (…)`. So a Query Term value
836 : /// may carry an escaped quote, an escaped backslash, the two-character
837 : /// control escapes and `\uXXXX`, and the value the term compares against
838 : /// is the DECODED text: the entity member it is matched to was decoded by
839 : /// the JSON parser on the way in.
840 : #[test]
841 2 : fn a_quoted_string_is_an_rfc_8259_string() {
842 14 : for (q, want) in [
843 2 : (r#"a=="say \"hi\"""#, "say \"hi\""),
844 2 : (r#"a=="back\\slash""#, "back\\slash"),
845 2 : (r#"a=="line\nbreak""#, "line\nbreak"),
846 2 : (r#"a=="tab\there""#, "tab\there"),
847 2 : (r#"a=="caf\u00e9""#, "café"),
848 2 : (r#"a=="sl\/ash""#, "sl/ash"),
849 2 : (r#"a=="""#, ""),
850 2 : ] {
851 14 : let node = parse_q(q).unwrap_or_else(|e| panic!("{q}: {e:?}"));
852 14 : let QNode::Cmp { value, .. } = node else {
853 0 : panic!("{q}: expected a comparison")
854 : };
855 14 : assert_eq!(value, QValue::Str(want.to_owned()), "{q}");
856 : }
857 2 : }
858 :
859 : /// The escape only ends the string when it is not itself escaped: a
860 : /// trailing `\"` continues the literal, and `\\` before the closing
861 : /// quote does not.
862 : #[test]
863 2 : fn an_escaped_quote_does_not_end_the_string() {
864 2 : assert!(
865 2 : parse_q(r#"a=="unterminated\""#).is_err(),
866 : "an escaped quote leaves the string open"
867 : );
868 2 : let node = parse_q(r#"a=="ends with a backslash\\";b"#).expect("parses");
869 2 : let QNode::And(items) = node else {
870 0 : panic!("expected an And")
871 : };
872 2 : let QNode::Cmp { value, .. } = &items[0] else {
873 0 : panic!("expected a comparison")
874 : };
875 2 : assert_eq!(value, &QValue::Str("ends with a backslash\\".to_owned()));
876 2 : }
877 :
878 : /// An escape RFC 8259 does not define is not a String, so the term is
879 : /// not a Query Term — refused rather than silently read as two
880 : /// characters.
881 : #[test]
882 2 : fn an_undefined_escape_is_not_a_string() {
883 6 : for q in [r#"a=="bad\x""#, r#"a=="short\u12""#, r#"a=="\u12zz""#] {
884 6 : assert!(parse_q(q).is_err(), "{q} must not parse");
885 : }
886 2 : }
887 :
888 : /// The unquoted alternatives of the grammar are `dateTime`/`date`/`time`
889 : /// (4.6.3) and `URI` (RFC 3986), and a raw `"` belongs to none of them.
890 : /// Accepting one produced a value that could not be written back as a
891 : /// Query Term at all.
892 : #[test]
893 2 : fn an_unquoted_value_may_not_carry_a_bare_quote() {
894 6 : for q in [r#"a==x"y"#, r#"a==urn:x:"y"#, r#"a>2020-01-01T00:00:"0Z"#] {
895 6 : assert!(parse_q(q).is_err(), "{q} must not parse");
896 : }
897 2 : }
898 :
899 : #[test]
900 2 : fn bool_with_ordering_op_is_a_grammar_violation() {
901 : // p.84: Operator (ordering) takes ComparableValue; true/false are
902 : // OtherValue, reachable only through ==/!=
903 2 : assert!(parse_q("a>true").is_err());
904 2 : assert!(parse_q("a==true").is_ok());
905 2 : }
906 : }
907 :
908 : #[cfg(test)]
909 : mod complexity_tests {
910 : use super::*;
911 :
912 : #[test]
913 2 : fn q_complexity_cap_is_403_class() {
914 : // >512 nodes → TooComplexQuery, small trees untouched.
915 2 : let ok = "a==1;b==2|c==3";
916 2 : assert!(parse_q(ok).is_ok());
917 2 : let huge = (0..600)
918 1200 : .map(|i| format!("a{i}==1"))
919 2 : .collect::<Vec<_>>()
920 2 : .join(";");
921 2 : match parse_q(&huge) {
922 2 : Err(NgsiError::TooComplexQuery(_)) => {}
923 0 : other => panic!("expected TooComplexQuery, got {other:?}"),
924 : }
925 2 : }
926 :
927 : /// Regression: the parser once recursed per `(` with
928 : /// no depth counter. A Rust stack overflow is a guard-page ABORT, not a
929 : /// catchable panic — no tower layer can contain it — so ~4000 parens in a
930 : /// query string killed the whole broker process, and a percent-encoded
931 : /// copy stored in a subscription made that a restart-surviving crash loop.
932 : #[test]
933 : #[cfg_attr(miri, ignore)] // 50k parens: nine minutes under the interpreter
934 2 : fn deep_nesting_is_refused_before_it_can_overflow_the_stack() {
935 2 : let deep = format!("{}a==1{}", "(".repeat(50_000), ")".repeat(50_000));
936 2 : assert!(
937 2 : matches!(parse_q(&deep), Err(NgsiError::TooComplexQuery(_))),
938 : "deep nesting must be a 403, never an abort"
939 : );
940 : // the length cap fires first on that one; check depth alone too
941 2 : let deep = format!("{}a==1{}", "(".repeat(300), ")".repeat(300));
942 2 : assert!(deep.len() < MAX_Q_BYTES);
943 2 : assert!(matches!(parse_q(&deep), Err(NgsiError::TooComplexQuery(_))));
944 : // and ordinary grouping still parses
945 2 : assert!(parse_q("((a==1|b==2);c==3)").is_ok());
946 2 : }
947 :
948 : #[test]
949 2 : fn overlong_q_is_refused_at_the_entry_point() {
950 : // a POST query body carries `q` too, where the URI cap does not apply
951 2 : let long = format!("a=={}", "x".repeat(MAX_Q_BYTES));
952 2 : assert!(matches!(parse_q(&long), Err(NgsiError::TooComplexQuery(_))));
953 2 : }
954 :
955 : /// The depth ceiling is exact and counts open parentheses, not the
956 : /// parentheses seen: sibling groups close what they open, so a query may
957 : /// carry any number of them.
958 : #[test]
959 2 : fn depth_cap_is_exact_and_counts_only_open_parens() {
960 2 : let at_cap = format!("{}a==1{}", "(".repeat(MAX_Q_DEPTH), ")".repeat(MAX_Q_DEPTH));
961 2 : assert!(parse_q(&at_cap).is_ok(), "{MAX_Q_DEPTH} nested must parse");
962 2 : let over = format!(
963 : "{}a==1{}",
964 2 : "(".repeat(MAX_Q_DEPTH + 1),
965 2 : ")".repeat(MAX_Q_DEPTH + 1)
966 : );
967 2 : assert!(matches!(parse_q(&over), Err(NgsiError::TooComplexQuery(_))));
968 2 : let siblings = (0..200)
969 400 : .map(|i| format!("(a{i}==1)"))
970 2 : .collect::<Vec<_>>()
971 2 : .join(";");
972 2 : assert!(siblings.len() < MAX_Q_BYTES);
973 2 : assert!(parse_q(&siblings).is_ok(), "siblings are not cumulative");
974 2 : }
975 :
976 : /// The parser is a fuzz target: on any input it returns, and the error it
977 : /// returns is safe to hand back — the input is echoed Debug-escaped, so a
978 : /// rejected `q` cannot carry a raw CR/LF into a response or a log line.
979 : #[test]
980 2 : fn hostile_input_is_total_and_its_error_is_escaped() {
981 90 : for hostile in [
982 2 : "",
983 2 : " ",
984 2 : "\"",
985 2 : "\"\"",
986 2 : "a==\"",
987 2 : "..",
988 2 : "a==..",
989 2 : "a==1..",
990 2 : "a==..1",
991 2 : "a.",
992 2 : "a[",
993 2 : "a[]",
994 2 : "a{",
995 2 : "a{}",
996 2 : "a{b",
997 2 : "a{,:b}",
998 2 : ";",
999 2 : "|",
1000 2 : "()",
1001 2 : "(((",
1002 2 : ")))",
1003 2 : "!",
1004 2 : "!!a",
1005 2 : "a==1,",
1006 2 : "a==,1",
1007 2 : "~=",
1008 2 : "a~=",
1009 2 : "a!~=",
1010 2 : "a==1)b",
1011 2 : "\u{202e}==1",
1012 2 : "ä==1",
1013 2 : "a==\"ä",
1014 2 : "温度.値>=1",
1015 2 : "a\u{2028}==1",
1016 2 : "a=={}",
1017 2 : "a==1e999",
1018 2 : "a==-0",
1019 2 : "a==NaN..1",
1020 2 : "a{b:c}{d:e}.f[g].h==1",
1021 2 : &"{".repeat(64),
1022 2 : &"[".repeat(64),
1023 2 : &"a{".repeat(64),
1024 2 : &".".repeat(64),
1025 2 : &"!".repeat(64),
1026 2 : &",".repeat(64),
1027 2 : ] {
1028 90 : match parse_q(hostile) {
1029 18 : Ok(_) => {}
1030 72 : Err(e) => {
1031 72 : let msg = e.to_string();
1032 72 : assert!(
1033 72 : !msg.chars().any(char::is_control),
1034 : "error text must stay escaped for {hostile:?}: {msg:?}"
1035 : );
1036 : }
1037 : }
1038 : }
1039 2 : }
1040 :
1041 : /// `!` is the existence-check prefix only (4.9): pairing it with a
1042 : /// comparison is a grammar violation, not a silently ignored negation.
1043 : #[test]
1044 2 : fn negated_comparison_is_a_grammar_violation() {
1045 2 : assert!(matches!(
1046 2 : parse_q("!a==1"),
1047 : Err(NgsiError::BadRequestData(_))
1048 : ));
1049 2 : assert!(matches!(
1050 2 : parse_q("!a"),
1051 : Ok(QNode::Exists { negated: true, .. })
1052 : ));
1053 : // `!=` after a path is the operator, not a negation prefix
1054 2 : assert!(matches!(
1055 2 : parse_q("a!=1"),
1056 : Ok(QNode::Cmp { op: CmpOp::Ne, .. })
1057 : ));
1058 2 : }
1059 : }
|
