Line data Source code
1 : // SPDX-License-Identifier: EUPL-1.2
2 : //! Scope Query Language (CIM 009 clause 4.19), evaluated in memory over the
3 : //! entity's `scope` member.
4 :
5 : use antares_model::NgsiError;
6 : use serde_json::Value;
7 :
8 : /// Scope Query evaluation (4.19) — `|`/`,` = OR, `(a;b)` = AND (parenthesis
9 : /// grouping), `+` one level, trailing `#` the subtree incl. the node, `/#`
10 : /// any non-empty scope.
11 8402 : pub fn scope_matches(scope_q: &str, doc: &Value) -> bool {
12 : // scope is an array in the entity internal form, but a bare string is
13 : // legal on documents stored verbatim (e.g. registrations, 5.2.9)
14 8402 : let scopes: Vec<&str> = match doc.get("scope") {
15 4851 : Some(Value::Array(a)) => a.iter().filter_map(Value::as_str).collect(),
16 380 : Some(Value::String(s)) => vec![s.as_str()],
17 3171 : _ => Vec::new(),
18 : };
19 8833 : scope_q.split([',', '|']).any(|and_group| {
20 8833 : and_group
21 8833 : .trim()
22 8833 : .trim_start_matches('(')
23 8833 : .trim_end_matches(')')
24 8833 : .split(';')
25 9100 : .all(|pat| scopes.iter().any(|s| scope_pattern_matches(pat.trim(), s)))
26 8833 : })
27 8402 : }
28 :
29 : /// Checks a `scopeQ` against the 4.19 grammar (TS 104 175 7.2.5) before it is
30 : /// evaluated: a disjunction (`,` or `|`) of ScopeQs and parenthesized
31 : /// `;`-conjunctions of them, each `/level(/level)*` with `+` a whole level and
32 : /// `#` only as the last one, or `/#`; a level starts with a letter. A bare
33 : /// conjunction (`/a;/b`) is a 400 like any other text outside the grammar. An empty query, an empty group or pattern (`/a,,/b`,
34 : /// `/a;;/b`) or an empty level (`//a`) is a 400 BadRequestData: without this
35 : /// [`scope_matches`] skips the empty piece and answers a wider query than the
36 : /// one asked. Longer than [`MAX_SCOPE_Q_BYTES`] is a 403 TooComplexQuery.
37 : ///
38 : /// # Errors
39 : /// [`NgsiError::BadRequestData`] or [`NgsiError::TooComplexQuery`] as above.
40 376 : pub fn check_scope_q(scope_q: &str) -> Result<(), NgsiError> {
41 376 : if scope_q.len() > MAX_SCOPE_Q_BYTES {
42 2 : return Err(NgsiError::TooComplexQuery(format!(
43 2 : "scopeQ is longer than {MAX_SCOPE_Q_BYTES} bytes"
44 2 : )));
45 374 : }
46 374 : let bad = |why: &str| NgsiError::BadRequestData(format!("invalid scopeQ {scope_q:?}: {why}"));
47 822 : for group in scope_q.split([',', '|']) {
48 822 : let group = group.trim();
49 822 : let inner = match (group.strip_prefix('('), group.strip_suffix(')')) {
50 34 : (Some(_), Some(_)) => group.get(1..group.len().saturating_sub(1)).unwrap_or(""),
51 : // TS 104 175 7.2.5: "For logical and grouping parenthesis are needed"
52 782 : (None, None) if group.contains(';') => {
53 41 : return Err(bad("a ';' conjunction needs parentheses, e.g. (/a;/b)"));
54 : }
55 741 : (None, None) => group,
56 6 : _ => return Err(bad("unbalanced parenthesis")),
57 : };
58 775 : if inner.is_empty() {
59 26 : return Err(bad("empty group"));
60 749 : }
61 781 : for pat in inner.split(';') {
62 781 : check_scope_pattern(pat.trim()).map_err(bad)?;
63 : }
64 : }
65 236 : Ok(())
66 376 : }
67 :
68 781 : fn check_scope_pattern(pat: &str) -> Result<(), &'static str> {
69 781 : if pat.is_empty() {
70 4 : return Err("empty pattern");
71 777 : }
72 777 : let Some(rest) = pat.strip_prefix('/') else {
73 2 : return Err("a ScopeQ starts with '/'");
74 : };
75 775 : let levels: Vec<&str> = rest.split('/').collect();
76 775 : let last = levels.len().saturating_sub(1);
77 1467 : for (i, level) in levels.iter().enumerate() {
78 74 : match *level {
79 1467 : "" => return Err("empty scope level"),
80 1446 : "#" if i != last => return Err("'#' is only the last level"),
81 1372 : "#" | "+" => {}
82 : // ScopeQLevel = unicodeLetter *(unicodeNumber / unicodeLetter / "_"), the
83 : // grammar every stored Scope already follows (antares-jsonld valid_scope_value)
84 1358 : l => {
85 1358 : let mut ch = l.chars();
86 1358 : if !(ch.next().is_some_and(char::is_alphabetic)
87 3686 : && ch.all(|c| c.is_alphabetic() || c.is_numeric() || c == '_'))
88 : {
89 32 : return Err("a scope level is a letter, then letters, digits or '_'");
90 1326 : }
91 : }
92 : }
93 : }
94 716 : Ok(())
95 781 : }
96 :
97 : /// The Scope Query that selects what BOTH arguments select (4.19).
98 : ///
99 : /// A Scope Query is a disjunction of conjunctions, and the conjunction is
100 : /// over predicates that are independent of each other — each pattern asks
101 : /// whether SOME Scope of the Entity matches it — so `and` distributes over
102 : /// `or` and the intersection is a disjunction of the pairwise unions:
103 : /// `(a1,a2)` and `(b1,b2)` select what `(a1;b1),(a1;b2),(a2;b1),(a2;b2)`
104 : /// selects. Every term of the result is a `;`-conjunction of plain
105 : /// `ScopeQ`s, which is what the grammar's parenthesized `OrScopeQ` derives,
106 : /// so the answer is a Scope Query and not a broker-private structure.
107 : ///
108 : /// `None` when either side contributes no group, or when the product would
109 : /// exceed [`MAX_SCOPE_Q_BYTES`]: the caller then has an intersection it
110 : /// cannot express and must refuse rather than serve the wider of the two.
111 36 : pub fn intersect_scope_q(a: &str, b: &str) -> Option<String> {
112 72 : let groups = |s: &str| -> Vec<String> {
113 72 : s.split([',', '|'])
114 1676 : .map(|g| {
115 1676 : g.trim()
116 1676 : .trim_start_matches('(')
117 1676 : .trim_end_matches(')')
118 1676 : .trim()
119 1676 : })
120 1676 : .filter(|g| !g.is_empty())
121 72 : .map(str::to_owned)
122 72 : .collect()
123 72 : };
124 36 : let (ga, gb) = (groups(a), groups(b));
125 36 : if ga.is_empty() || gb.is_empty() {
126 4 : return None;
127 32 : }
128 32 : let mut out = String::new();
129 42 : for x in &ga {
130 1238 : for y in &gb {
131 1238 : if !out.is_empty() {
132 1206 : out.push(',');
133 1206 : }
134 : // `/#` selects every Entity that carries any Scope at all, so it
135 : // adds nothing to a conjunction that already names one — and it
136 : // is the one ScopesQ alternative the grammar does not derive
137 : // inside a parenthesized group.
138 1238 : match (x.as_str(), y.as_str()) {
139 1238 : (ANY_SCOPE, ANY_SCOPE) => out.push_str(ANY_SCOPE),
140 1228 : (ANY_SCOPE, term) | (term, ANY_SCOPE) => out.push_str(term),
141 1228 : (l, r) => {
142 1228 : out.push('(');
143 1228 : out.push_str(l);
144 1228 : out.push(';');
145 1228 : out.push_str(r);
146 1228 : out.push(')');
147 1228 : }
148 : }
149 1238 : if out.len() > MAX_SCOPE_Q_BYTES {
150 6 : return None;
151 1232 : }
152 : }
153 : }
154 26 : Some(out)
155 36 : }
156 :
157 : /// The ScopesQ that selects every Entity carrying a non-empty Scope (4.19).
158 : const ANY_SCOPE: &str = "/#";
159 :
160 : /// Ceiling on a Scope Query this crate will build. The store's own compiler
161 : /// declines a longer one and leaves it to the in-memory arbiter; an
162 : /// intersection past it is refused instead, so no caller is handed a query
163 : /// that is quietly wider than the one it asked for.
164 : pub const MAX_SCOPE_Q_BYTES: usize = 4096;
165 :
166 : /// One 4.19 ScopeQ against one Entity Scope: `/`-separated levels compared
167 : /// in order, `+` standing for any single level and a trailing `#` for the
168 : /// rest of the hierarchy including the node itself.
169 6303 : fn scope_pattern_matches(pat: &str, scope: &str) -> bool {
170 6303 : if pat == ANY_SCOPE {
171 172 : return true;
172 6131 : }
173 14104 : let pseg: Vec<&str> = pat.split('/').filter(|s| !s.is_empty()).collect();
174 14345 : let sseg: Vec<&str> = scope.split('/').filter(|s| !s.is_empty()).collect();
175 6131 : let mut i = 0;
176 7559 : for (pi, p) in pseg.iter().enumerate() {
177 7559 : if *p == "#" {
178 : // multi-level wildcard: matches the rest (including nothing)
179 792 : return pi.saturating_add(1) == pseg.len();
180 6767 : }
181 6767 : let Some(sv) = sseg.get(i) else { return false };
182 6618 : if *p != "+" && p != sv {
183 1404 : return false;
184 5214 : }
185 5214 : i = i.saturating_add(1);
186 : }
187 3786 : i == sseg.len()
188 6303 : }
189 :
190 : #[cfg(test)]
191 : mod clause_4_19 {
192 : use super::{check_scope_q, intersect_scope_q, scope_matches, MAX_SCOPE_Q_BYTES};
193 : use serde_json::json;
194 :
195 66 : fn doc(scopes: &[&str]) -> serde_json::Value {
196 66 : json!({"id": "urn:x", "type": ["T"], "scope": scopes})
197 66 : }
198 :
199 : /// 4.19 EXAMPLES 1-3: direct scope, `#` subtree (including the node
200 : /// itself), `+` single-level wildcard, `/#` any non-empty scope.
201 : #[test]
202 2 : fn wildcards_and_direct_scopes() {
203 2 : assert!(scope_matches("/Madrid", &doc(&["/Madrid"])));
204 2 : assert!(!scope_matches("/Madrid", &doc(&["/Madrid/Gardens"])));
205 6 : for s in [
206 2 : "/Madrid/Gardens",
207 2 : "/Madrid/Gardens/ParqueNorte",
208 2 : "/Madrid/Gardens/ParqueNorte/Parterre1",
209 2 : ] {
210 6 : assert!(scope_matches("/Madrid/Gardens/#", &doc(&[s])), "{s}");
211 : }
212 2 : assert!(!scope_matches(
213 2 : "/Madrid/Gardens/#",
214 2 : &doc(&["/Madrid/Sights"])
215 2 : ));
216 2 : assert!(scope_matches(
217 2 : "/Madrid/+/ParqueNorte",
218 2 : &doc(&["/Madrid/Sights/ParqueNorte"])
219 : ));
220 2 : assert!(!scope_matches(
221 2 : "/Madrid/+/ParqueNorte",
222 2 : &doc(&["/Madrid/ParqueNorte"])
223 2 : ));
224 2 : assert!(scope_matches("/#", &doc(&["/Anything"])));
225 2 : assert!(
226 2 : !scope_matches("/#", &doc(&[])),
227 : "no scope = no match for /#"
228 : );
229 2 : }
230 :
231 : /// 4.19 EXAMPLES 4/5: conjunction needs parentheses; disjunction is `|`
232 : /// OR the compatibility comma.
233 : #[test]
234 2 : fn conjunction_and_both_or_spellings() {
235 2 : let both = doc(&["/Madrid/Districts", "/CompanyA"]);
236 2 : let only_b = doc(&["/CompanyB"]);
237 2 : let only_madrid = doc(&["/Madrid/Districts"]);
238 2 : assert!(scope_matches("(/Madrid/Districts;/CompanyA)", &both));
239 2 : assert!(
240 2 : !scope_matches("(/Madrid/Districts;/CompanyA)", &only_madrid),
241 : "conjunction requires ALL scopes"
242 : );
243 4 : for sel in [
244 2 : "(/Madrid/Districts;/CompanyA)|/CompanyB",
245 2 : "(/Madrid/Districts;/CompanyA),/CompanyB",
246 2 : ] {
247 4 : assert!(scope_matches(sel, &both), "{sel}");
248 4 : assert!(scope_matches(sel, &only_b), "{sel}");
249 4 : assert!(!scope_matches(sel, &only_madrid), "{sel}");
250 : }
251 2 : }
252 :
253 : /// The ABNF puts `andOp` inside the parenthesized `OrScopeQ` alone, so
254 : /// `(a;b),(c;d)` is the only spelling it derives, and [`check_scope_q`]
255 : /// refuses the bare `a;b` at every entry (forge cc8711ce moved
256 : /// `019_01_06_05` to the parenthesized form and added `019_03_07_05`).
257 : /// [`scope_matches`] still evaluates a bare conjunction an internal
258 : /// caller builds, and the two spellings have to MEAN the same thing:
259 : /// `;` binds tighter than `,`/`|`, the reading the parentheses force.
260 : #[test]
261 2 : fn a_conjunction_means_the_same_parenthesized_or_bare() {
262 2 : let docs = [
263 2 : doc(&[]),
264 2 : doc(&["/A"]),
265 2 : doc(&["/B"]),
266 2 : doc(&["/C"]),
267 2 : doc(&["/A", "/B"]),
268 2 : doc(&["/C", "/D"]),
269 2 : doc(&["/A", "/D"]),
270 2 : doc(&["/A", "/B", "/C", "/D"]),
271 2 : ];
272 16 : for d in &docs {
273 16 : assert_eq!(
274 16 : scope_matches("(/A;/B),(/C;/D)", d),
275 16 : scope_matches("/A;/B,/C;/D", d),
276 : "the two spellings disagree on {d}"
277 : );
278 16 : assert_eq!(
279 16 : scope_matches("(/A;/B)|(/C;/D)", d),
280 16 : scope_matches("/A;/B|/C;/D", d),
281 : "the two spellings disagree on {d}"
282 : );
283 : }
284 : // and the grouping is the one the parentheses state, not the other
285 : // one: `/A;/B,/C` is `(/A AND /B) OR /C`, never `/A AND (/B OR /C)`.
286 2 : assert!(scope_matches("/A;/B,/C", &doc(&["/C"])));
287 2 : assert!(!scope_matches("/A;/B,/C", &doc(&["/A"])));
288 2 : assert!(scope_matches("/A;/B,/C", &doc(&["/A", "/B"])));
289 2 : }
290 :
291 : /// The intersection has to select what BOTH select, for every Entity —
292 : /// a policy engine narrowing a request that brought its own Scope Query
293 : /// is the caller, and an intersection that is wider than either side is
294 : /// a disclosure.
295 : #[test]
296 2 : fn an_intersection_selects_exactly_what_both_select() {
297 2 : let docs = [
298 2 : doc(&[]),
299 2 : doc(&["/A"]),
300 2 : doc(&["/B"]),
301 2 : doc(&["/BB"]),
302 2 : doc(&["/BB/Traffic"]),
303 2 : doc(&["/A", "/B"]),
304 2 : doc(&["/A", "/BB/Traffic"]),
305 2 : doc(&["/BB", "/BB/Traffic"]),
306 2 : doc(&["/A", "/B", "/BB", "/BB/Traffic"]),
307 2 : ];
308 18 : for (a, b) in [
309 2 : ("/A", "/B"),
310 2 : ("/A,/B", "/B,/C"),
311 2 : ("/BB", "/BB/Traffic"),
312 2 : ("/BB/#", "/BB/Traffic"),
313 2 : ("(/A;/B)", "/BB/#"),
314 2 : ("(/A;/B),/BB", "(/BB;/BB/Traffic),/A"),
315 2 : ("/#", "/A,/B"),
316 2 : ("/#", "/#"),
317 2 : ("/A", "/A"),
318 2 : ] {
319 18 : let both = intersect_scope_q(a, b).expect("expressible");
320 162 : for d in &docs {
321 162 : assert_eq!(
322 162 : scope_matches(&both, d),
323 162 : scope_matches(a, d) && scope_matches(b, d),
324 : "{a} INTERSECT {b} = {both} disagrees on {d}"
325 : );
326 : }
327 : }
328 2 : }
329 :
330 : /// Nothing to intersect, and an intersection too large to write down:
331 : /// both leave the caller to refuse rather than serve the wider side.
332 : #[test]
333 2 : fn an_inexpressible_intersection_is_none() {
334 2 : assert_eq!(intersect_scope_q("", "/A"), None);
335 2 : assert_eq!(intersect_scope_q("/A", " "), None);
336 2 : let wide = (0..200)
337 400 : .map(|n| format!("/S{n}"))
338 2 : .collect::<Vec<_>>()
339 2 : .join(",");
340 2 : assert_eq!(intersect_scope_q(&wide, &wide), None, "200x200 groups");
341 2 : }
342 :
343 : /// A Scope stored as a bare string (a registration kept verbatim) is
344 : /// matched like a one-element array; the intersection may be exactly
345 : /// MAX_SCOPE_Q_BYTES long, one byte more is refused.
346 : #[test]
347 2 : fn bare_string_scope_and_the_intersection_ceiling() {
348 : use serde_json::json;
349 2 : assert!(scope_matches("/a", &json!({"scope": "/a"})));
350 2 : assert!(!scope_matches("/b", &json!({"scope": "/a"})));
351 4 : let at = |n: usize| format!("/{}", "s".repeat(n - 1));
352 2 : assert_eq!(
353 2 : intersect_scope_q("/#", &at(super::MAX_SCOPE_Q_BYTES)).map(|s| s.len()),
354 : Some(super::MAX_SCOPE_Q_BYTES)
355 : );
356 2 : assert_eq!(
357 2 : intersect_scope_q("/#", &at(super::MAX_SCOPE_Q_BYTES + 1)),
358 : None
359 : );
360 2 : }
361 :
362 : /// 4.19 grammar: the shapes the examples use pass; an empty piece, a
363 : /// level after `#`, or a missing leading `/` is a 400, never a silent
364 : /// widening; past the ceiling is a 403.
365 : #[test]
366 2 : fn check_scope_q_follows_the_grammar() {
367 22 : for ok in [
368 2 : "/Madrid",
369 2 : "/Madrid/+/ParqueNorte",
370 2 : "/Madrid/#",
371 2 : "/#",
372 2 : "/Madrid,/Berlin",
373 2 : "/Madrid|/Berlin",
374 2 : "(/Madrid;/Gardens),/Berlin",
375 2 : "(/Madrid/Gardens/ParqueNorte;/CompanyA/OrganizationB/UnitC)",
376 2 : "/Madrid/Gardens/ParqueNorte/#",
377 2 : "/Madrid/+/#",
378 2 : "/Ma_drid2/Été",
379 2 : ] {
380 22 : assert!(check_scope_q(ok).is_ok(), "{ok}");
381 : }
382 40 : for bad in [
383 2 : "",
384 2 : "/a,,/b",
385 2 : "/a;;/b",
386 2 : "//a",
387 2 : "/a/",
388 2 : "Madrid",
389 2 : "/a/#/b",
390 2 : "(/a;/b",
391 2 : "()",
392 2 : "/a b",
393 2 : "/a#",
394 2 : // TS 104 175 7.2.5 (forge 019_03_07): "For logical and grouping parenthesis are
395 2 : // needed", and a ScopeQLevel is a unicodeLetter then letters, numbers or "_"
396 2 : "/a;/b",
397 2 : "/Madrid;",
398 2 : "/a;/b,/c",
399 2 : "/Madrid/1st",
400 2 : "/Madrid/+G",
401 2 : "/a.b",
402 2 : "/a-b",
403 2 : // an empty pattern inside a group
404 2 : "(/a;;/b)",
405 2 : "(/Madrid;)",
406 2 : ] {
407 40 : let err = check_scope_q(bad).unwrap_err();
408 40 : assert_eq!(err.status(), 400, "{bad:?}: {err}");
409 : }
410 2 : let long = "/a,".repeat(MAX_SCOPE_Q_BYTES);
411 2 : assert_eq!(check_scope_q(&long).unwrap_err().status(), 403);
412 2 : }
413 : }
|
