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 serde_json::Value;
6 :
7 : /// Scope Query evaluation (4.19) — `|`/`,` = OR, `(a;b)` = AND (parenthesis
8 : /// grouping), `+` one level, trailing `#` the subtree incl. the node, `/#`
9 : /// any non-empty scope.
10 1654 : pub fn scope_matches(scope_q: &str, doc: &Value) -> bool {
11 : // scope is an array in the entity internal form, but a bare string is
12 : // legal on documents stored verbatim (e.g. registrations, 5.2.9)
13 1654 : let scopes: Vec<&str> = match doc.get("scope") {
14 1284 : Some(Value::Array(a)) => a.iter().filter_map(Value::as_str).collect(),
15 328 : Some(Value::String(s)) => vec![s.as_str()],
16 42 : _ => Vec::new(),
17 : };
18 1902 : scope_q.split([',', '|']).any(|and_group| {
19 1902 : and_group
20 1902 : .trim()
21 1902 : .trim_start_matches('(')
22 1902 : .trim_end_matches(')')
23 1902 : .split(';')
24 2272 : .all(|pat| scopes.iter().any(|s| scope_pattern_matches(pat.trim(), s)))
25 1902 : })
26 1654 : }
27 :
28 : /// The Scope Query that selects what BOTH arguments select (4.19).
29 : ///
30 : /// A Scope Query is a disjunction of conjunctions, and the conjunction is
31 : /// over predicates that are independent of each other — each pattern asks
32 : /// whether SOME Scope of the Entity matches it — so `and` distributes over
33 : /// `or` and the intersection is a disjunction of the pairwise unions:
34 : /// `(a1,a2)` and `(b1,b2)` select what `(a1;b1),(a1;b2),(a2;b1),(a2;b2)`
35 : /// selects. Every term of the result is a `;`-conjunction of plain
36 : /// `ScopeQ`s, which is what the grammar's parenthesized `OrScopeQ` derives,
37 : /// so the answer is a Scope Query and not a broker-private structure.
38 : ///
39 : /// `None` when either side contributes no group, or when the product would
40 : /// exceed [`MAX_SCOPE_Q_BYTES`]: the caller then has an intersection it
41 : /// cannot express and must refuse rather than serve the wider of the two.
42 32 : pub fn intersect_scope_q(a: &str, b: &str) -> Option<String> {
43 64 : let groups = |s: &str| -> Vec<String> {
44 64 : s.split([',', '|'])
45 1668 : .map(|g| {
46 1668 : g.trim()
47 1668 : .trim_start_matches('(')
48 1668 : .trim_end_matches(')')
49 1668 : .trim()
50 1668 : })
51 1668 : .filter(|g| !g.is_empty())
52 64 : .map(str::to_owned)
53 64 : .collect()
54 64 : };
55 32 : let (ga, gb) = (groups(a), groups(b));
56 32 : if ga.is_empty() || gb.is_empty() {
57 4 : return None;
58 28 : }
59 28 : let mut out = String::new();
60 38 : for x in &ga {
61 1234 : for y in &gb {
62 1234 : if !out.is_empty() {
63 1206 : out.push(',');
64 1206 : }
65 : // `/#` selects every Entity that carries any Scope at all, so it
66 : // adds nothing to a conjunction that already names one — and it
67 : // is the one ScopesQ alternative the grammar does not derive
68 : // inside a parenthesized group.
69 1234 : match (x.as_str(), y.as_str()) {
70 1234 : (ANY_SCOPE, ANY_SCOPE) => out.push_str(ANY_SCOPE),
71 1228 : (ANY_SCOPE, term) | (term, ANY_SCOPE) => out.push_str(term),
72 1228 : (l, r) => {
73 1228 : out.push('(');
74 1228 : out.push_str(l);
75 1228 : out.push(';');
76 1228 : out.push_str(r);
77 1228 : out.push(')');
78 1228 : }
79 : }
80 1234 : if out.len() > MAX_SCOPE_Q_BYTES {
81 4 : return None;
82 1230 : }
83 : }
84 : }
85 24 : Some(out)
86 32 : }
87 :
88 : /// The ScopesQ that selects every Entity carrying a non-empty Scope (4.19).
89 : const ANY_SCOPE: &str = "/#";
90 :
91 : /// Ceiling on a Scope Query this crate will build. The store's own compiler
92 : /// declines a longer one and leaves it to the in-memory arbiter; an
93 : /// intersection past it is refused instead, so no caller is handed a query
94 : /// that is quietly wider than the one it asked for.
95 : pub const MAX_SCOPE_Q_BYTES: usize = 4096;
96 :
97 : /// One 4.19 ScopeQ against one Entity Scope: `/`-separated levels compared
98 : /// in order, `+` standing for any single level and a trailing `#` for the
99 : /// rest of the hierarchy including the node itself.
100 2272 : fn scope_pattern_matches(pat: &str, scope: &str) -> bool {
101 2272 : if pat == ANY_SCOPE {
102 108 : return true;
103 2164 : }
104 5404 : let pseg: Vec<&str> = pat.split('/').filter(|s| !s.is_empty()).collect();
105 5394 : let sseg: Vec<&str> = scope.split('/').filter(|s| !s.is_empty()).collect();
106 2164 : let mut i = 0;
107 3020 : for (pi, p) in pseg.iter().enumerate() {
108 3020 : if *p == "#" {
109 : // multi-level wildcard: matches the rest (including nothing)
110 668 : return pi == pseg.len() - 1;
111 2352 : }
112 2352 : let Some(sv) = sseg.get(i) else { return false };
113 2300 : if *p != "+" && p != sv {
114 956 : return false;
115 1344 : }
116 1344 : i += 1;
117 : }
118 488 : i == sseg.len()
119 2272 : }
120 :
121 : #[cfg(test)]
122 : mod clause_4_19 {
123 : use super::{intersect_scope_q, scope_matches};
124 : use serde_json::json;
125 :
126 66 : fn doc(scopes: &[&str]) -> serde_json::Value {
127 66 : json!({"id": "urn:x", "type": ["T"], "scope": scopes})
128 66 : }
129 :
130 : /// 4.19 EXAMPLES 1-3: direct scope, `#` subtree (including the node
131 : /// itself), `+` single-level wildcard, `/#` any non-empty scope.
132 : #[test]
133 2 : fn wildcards_and_direct_scopes() {
134 2 : assert!(scope_matches("/Madrid", &doc(&["/Madrid"])));
135 2 : assert!(!scope_matches("/Madrid", &doc(&["/Madrid/Gardens"])));
136 6 : for s in [
137 2 : "/Madrid/Gardens",
138 2 : "/Madrid/Gardens/ParqueNorte",
139 2 : "/Madrid/Gardens/ParqueNorte/Parterre1",
140 2 : ] {
141 6 : assert!(scope_matches("/Madrid/Gardens/#", &doc(&[s])), "{s}");
142 : }
143 2 : assert!(!scope_matches(
144 2 : "/Madrid/Gardens/#",
145 2 : &doc(&["/Madrid/Sights"])
146 2 : ));
147 2 : assert!(scope_matches(
148 2 : "/Madrid/+/ParqueNorte",
149 2 : &doc(&["/Madrid/Sights/ParqueNorte"])
150 : ));
151 2 : assert!(!scope_matches(
152 2 : "/Madrid/+/ParqueNorte",
153 2 : &doc(&["/Madrid/ParqueNorte"])
154 2 : ));
155 2 : assert!(scope_matches("/#", &doc(&["/Anything"])));
156 2 : assert!(
157 2 : !scope_matches("/#", &doc(&[])),
158 : "no scope = no match for /#"
159 : );
160 2 : }
161 :
162 : /// 4.19 EXAMPLES 4/5: conjunction needs parentheses; disjunction is `|`
163 : /// OR the compatibility comma.
164 : #[test]
165 2 : fn conjunction_and_both_or_spellings() {
166 2 : let both = doc(&["/Madrid/Districts", "/CompanyA"]);
167 2 : let only_b = doc(&["/CompanyB"]);
168 2 : let only_madrid = doc(&["/Madrid/Districts"]);
169 2 : assert!(scope_matches("(/Madrid/Districts;/CompanyA)", &both));
170 2 : assert!(
171 2 : !scope_matches("(/Madrid/Districts;/CompanyA)", &only_madrid),
172 : "conjunction requires ALL scopes"
173 : );
174 4 : for sel in [
175 2 : "(/Madrid/Districts;/CompanyA)|/CompanyB",
176 2 : "(/Madrid/Districts;/CompanyA),/CompanyB",
177 2 : ] {
178 4 : assert!(scope_matches(sel, &both), "{sel}");
179 4 : assert!(scope_matches(sel, &only_b), "{sel}");
180 4 : assert!(!scope_matches(sel, &only_madrid), "{sel}");
181 : }
182 2 : }
183 :
184 : /// The ABNF puts `andOp` inside the parenthesized `OrScopeQ` alone, so
185 : /// `(a;b),(c;d)` is the only spelling it derives — yet the official
186 : /// suite's `019_01_06 QueryWithAndScope` sends `a;b` bare and expects
187 : /// 200 (`testsuite-doubts.md`). Both are served, and they have to MEAN
188 : /// the same thing: `;` binds tighter than `,`/`|`, which is the reading
189 : /// the parentheses would have forced. A gateway narrowing a request by
190 : /// rewriting `scopeQ` may emit either form.
191 : #[test]
192 2 : fn a_conjunction_means_the_same_parenthesized_or_bare() {
193 2 : let docs = [
194 2 : doc(&[]),
195 2 : doc(&["/A"]),
196 2 : doc(&["/B"]),
197 2 : doc(&["/C"]),
198 2 : doc(&["/A", "/B"]),
199 2 : doc(&["/C", "/D"]),
200 2 : doc(&["/A", "/D"]),
201 2 : doc(&["/A", "/B", "/C", "/D"]),
202 2 : ];
203 16 : for d in &docs {
204 16 : assert_eq!(
205 16 : scope_matches("(/A;/B),(/C;/D)", d),
206 16 : scope_matches("/A;/B,/C;/D", d),
207 : "the two spellings disagree on {d}"
208 : );
209 16 : assert_eq!(
210 16 : scope_matches("(/A;/B)|(/C;/D)", d),
211 16 : scope_matches("/A;/B|/C;/D", d),
212 : "the two spellings disagree on {d}"
213 : );
214 : }
215 : // and the grouping is the one the parentheses state, not the other
216 : // one: `/A;/B,/C` is `(/A AND /B) OR /C`, never `/A AND (/B OR /C)`.
217 2 : assert!(scope_matches("/A;/B,/C", &doc(&["/C"])));
218 2 : assert!(!scope_matches("/A;/B,/C", &doc(&["/A"])));
219 2 : assert!(scope_matches("/A;/B,/C", &doc(&["/A", "/B"])));
220 2 : }
221 :
222 : /// The intersection has to select what BOTH select, for every Entity —
223 : /// a policy engine narrowing a request that brought its own Scope Query
224 : /// is the caller, and an intersection that is wider than either side is
225 : /// a disclosure.
226 : #[test]
227 2 : fn an_intersection_selects_exactly_what_both_select() {
228 2 : let docs = [
229 2 : doc(&[]),
230 2 : doc(&["/A"]),
231 2 : doc(&["/B"]),
232 2 : doc(&["/BB"]),
233 2 : doc(&["/BB/Traffic"]),
234 2 : doc(&["/A", "/B"]),
235 2 : doc(&["/A", "/BB/Traffic"]),
236 2 : doc(&["/BB", "/BB/Traffic"]),
237 2 : doc(&["/A", "/B", "/BB", "/BB/Traffic"]),
238 2 : ];
239 18 : for (a, b) in [
240 2 : ("/A", "/B"),
241 2 : ("/A,/B", "/B,/C"),
242 2 : ("/BB", "/BB/Traffic"),
243 2 : ("/BB/#", "/BB/Traffic"),
244 2 : ("(/A;/B)", "/BB/#"),
245 2 : ("(/A;/B),/BB", "(/BB;/BB/Traffic),/A"),
246 2 : ("/#", "/A,/B"),
247 2 : ("/#", "/#"),
248 2 : ("/A", "/A"),
249 2 : ] {
250 18 : let both = intersect_scope_q(a, b).expect("expressible");
251 162 : for d in &docs {
252 162 : assert_eq!(
253 162 : scope_matches(&both, d),
254 162 : scope_matches(a, d) && scope_matches(b, d),
255 : "{a} INTERSECT {b} = {both} disagrees on {d}"
256 : );
257 : }
258 : }
259 2 : }
260 :
261 : /// Nothing to intersect, and an intersection too large to write down:
262 : /// both leave the caller to refuse rather than serve the wider side.
263 : #[test]
264 2 : fn an_inexpressible_intersection_is_none() {
265 2 : assert_eq!(intersect_scope_q("", "/A"), None);
266 2 : assert_eq!(intersect_scope_q("/A", " "), None);
267 2 : let wide = (0..200)
268 400 : .map(|n| format!("/S{n}"))
269 2 : .collect::<Vec<_>>()
270 2 : .join(",");
271 2 : assert_eq!(intersect_scope_q(&wide, &wide), None, "200x200 groups");
272 2 : }
273 : }
|
