pamoja_zenoh/
keyexpr.rs

1//! The Zenoh key-expression language: validity, canonical form, matching, and the relations
2//! between two expressions.
3//!
4//! A key expression is a `/`-joined list of non-empty chunks. A chunk is either a literal, the
5//! single-chunk wildcard `*` (one non-empty chunk), the multi-chunk wildcard `**` (zero or more
6//! chunks), or a literal carrying the sub-chunk wildcard `$*` (any run of characters, including
7//! none, within one chunk). A concrete key carries no wildcards. Leading, trailing, and doubled
8//! `/` are forbidden, as are the bare characters `*`, `$`, `?`, and `#` outside the wildcard forms.
9//!
10//! A chunk that starts with `@` is verbatim: no wildcard selects it, and only an identical chunk
11//! matches it. That seals the keys beneath it off from every expression that does not name it, which
12//! is how Zenoh keeps its administration space, `@/...`, out of a subscription on `**`.
13//!
14//! The rules follow the Zenoh key-expression specification, including its canonical-form rules:
15//! `**/**` collapses to `**`, `**/*` reorders to `*/**`, `$*$*` collapses to `$*`, and a chunk that
16//! is exactly `$*` becomes `*`. A Zenoh session accepts only the canonical form, so [`is_canon`] is
17//! the check a key passes before it goes on the wire, and [`is_valid`] the weaker one that
18//! [`canonize`] can repair.
19//!
20//! Two expressions relate the way two sets do. They [`intersects`] when at least one key belongs
21//! to both, which is the question a router asks before forwarding a publication to a subscriber,
22//! and one [`includes`] the other when every key of the second belongs to the first, which is how a
23//! bridge knows a new subscription adds nothing to one it already holds.
24
25use alloc::format;
26use alloc::string::{String, ToString};
27use alloc::vec;
28use alloc::vec::Vec;
29
30/// Returns whether a string is a well-formed key expression.
31///
32/// A well-formed expression may still need [`canonize`] before a Zenoh session accepts it; see
33/// [`is_canon`].
34///
35/// # Arguments
36///
37/// * `ke` - the candidate key expression.
38///
39/// # Returns
40///
41/// `true` if `ke` is `/`-joined non-empty chunks with no leading, trailing, or doubled `/`, where
42/// each chunk is `*`, `**`, or a literal in which `*` appears only as part of `$*` and `$` only
43/// before `*`, with no `?` or `#`.
44///
45/// # Examples
46///
47/// ```
48/// use pamoja_zenoh::keyexpr::is_valid;
49///
50/// assert!(is_valid("fleet/*/battery"));
51/// assert!(is_valid("fleet/**/**/battery")); // well formed, though not yet canonical
52/// assert!(!is_valid("fleet//battery")); // an empty chunk
53/// assert!(!is_valid("fleet/n7*")); // `*` inside a chunk is legal only as `$*`
54/// ```
55pub fn is_valid(ke: &str) -> bool {
56    if ke.is_empty() || ke.starts_with('/') || ke.ends_with('/') {
57        return false;
58    }
59    ke.split('/').all(chunk_valid)
60}
61
62/// Returns whether a key expression is valid and in canonical form.
63///
64/// The canonical form is the only one a Zenoh session accepts: the Zenoh API refuses any other
65/// spelling, and a router that receives one drops the message and closes the connection.
66///
67/// # Arguments
68///
69/// * `ke` - the candidate key expression.
70///
71/// # Returns
72///
73/// `true` if `ke` equals its own [`canonize`] output, so two expressions selecting the same keys
74/// compare equal as strings.
75///
76/// # Examples
77///
78/// ```
79/// use pamoja_zenoh::keyexpr::is_canon;
80///
81/// assert!(is_canon("fleet/*/**"));
82/// assert!(!is_canon("fleet/**/*")); // the same keys, spelled the other way round
83/// ```
84pub fn is_canon(ke: &str) -> bool {
85    canonize(ke).as_deref() == Some(ke)
86}
87
88/// Returns the canonical form of a key expression, or `None` if it is invalid.
89///
90/// # Arguments
91///
92/// * `ke` - the key expression to canonicalize.
93///
94/// # Returns
95///
96/// `Some(canonical)` for a valid `ke`, applying the canonical-form rules (`**/**` to `**`, `**/*`
97/// to `*/**`, `$*$*` to `$*`, and a `$*` chunk to `*`); `None` if `ke` is not a valid key
98/// expression.
99///
100/// # Examples
101///
102/// ```
103/// use pamoja_zenoh::keyexpr::canonize;
104///
105/// assert_eq!(canonize("robot/sensor/**/*").as_deref(), Some("robot/sensor/*/**"));
106/// assert_eq!(canonize("a/**/**/b").as_deref(), Some("a/**/b"));
107/// assert_eq!(canonize("a//b"), None); // a doubled slash is not a valid key expression
108/// ```
109pub fn canonize(ke: &str) -> Option<String> {
110    if !is_valid(ke) {
111        return None;
112    }
113    let canon_chunks: Vec<String> = ke.split('/').map(canon_chunk).collect();
114    let mut out: Vec<String> = Vec::new();
115    let mut i = 0;
116    while i < canon_chunks.len() {
117        if is_wildcard(canon_chunks[i].as_str()) {
118            let mut stars = 0;
119            let mut has_multi = false;
120            while i < canon_chunks.len() && is_wildcard(canon_chunks[i].as_str()) {
121                if canon_chunks[i].as_str() == "*" {
122                    stars += 1;
123                } else {
124                    has_multi = true;
125                }
126                i += 1;
127            }
128            out.extend((0..stars).map(|_| String::from("*")));
129            if has_multi {
130                out.push(String::from("**"));
131            }
132        } else {
133            out.push(canon_chunks[i].clone());
134            i += 1;
135        }
136    }
137    Some(out.join("/"))
138}
139
140/// Joins two key expressions with a `/` and returns the canonical form of the result.
141///
142/// This is how a key is built under a prefix, such as a node's own subtree of a fleet, without
143/// spelling the separator by hand or leaving a non-canonical pair of wildcards at the seam.
144///
145/// # Arguments
146///
147/// * `prefix` - the leading key expression.
148/// * `suffix` - the key expression to place beneath it.
149///
150/// # Returns
151///
152/// `Some(joined)` in canonical form; `None` if either side is empty or the joined expression is
153/// not valid.
154///
155/// # Examples
156///
157/// ```
158/// use pamoja_zenoh::keyexpr::join;
159///
160/// assert_eq!(join("fleet/n7", "battery").as_deref(), Some("fleet/n7/battery"));
161/// assert_eq!(join("fleet/**", "*").as_deref(), Some("fleet/*/**")); // canonized at the seam
162/// assert_eq!(join("fleet/", "battery"), None); // the seam would be an empty chunk
163/// ```
164pub fn join(prefix: &str, suffix: &str) -> Option<String> {
165    canonize(&format!("{prefix}/{suffix}"))
166}
167
168/// Returns whether a concrete key is selected by a pattern key expression.
169///
170/// # Arguments
171///
172/// * `pattern` - the key expression to test against; it may contain wildcards.
173/// * `key` - the concrete key being routed; it must be valid and carry no wildcards.
174///
175/// # Returns
176///
177/// `true` if `key` is one of the keys `pattern` selects. Returns `false` if `pattern` is not a
178/// valid key expression, or if `key` is not a valid concrete key. To compare two expressions that
179/// both carry wildcards, use [`intersects`] or [`includes`].
180///
181/// # Examples
182///
183/// ```
184/// use pamoja_zenoh::keyexpr::matches;
185///
186/// assert!(matches("room275/*/temperature", "room275/device1/temperature"));
187/// assert!(!matches("room275/*/temperature", "room275/temperature")); // `*` needs one chunk
188/// assert!(matches("organizationA/**/temperature", "organizationA/temperature")); // `**` allows none
189/// assert!(matches("thermometer$*/temperature", "thermometer1/temperature"));
190/// assert!(!matches("**", "@/router/status")); // no wildcard selects a verbatim chunk
191/// ```
192pub fn matches(pattern: &str, key: &str) -> bool {
193    is_valid(key) && !key.contains('*') && includes(pattern, key)
194}
195
196/// Returns whether two key expressions share at least one key.
197///
198/// This is the relation Zenoh routes by: a publication on one expression reaches a subscriber on
199/// another exactly when the two intersect. It is symmetric.
200///
201/// # Arguments
202///
203/// * `a` - one key expression; it may contain wildcards.
204/// * `b` - the other key expression; it may contain wildcards.
205///
206/// # Returns
207///
208/// `true` if some concrete key is selected by both; `false` if none is, or if either expression is
209/// not valid.
210///
211/// # Examples
212///
213/// ```
214/// use pamoja_zenoh::keyexpr::intersects;
215///
216/// assert!(intersects("fleet/*/battery", "fleet/n7/**")); // both select fleet/n7/battery
217/// assert!(!intersects("fleet/*/battery", "fleet/*/rack/**"));
218/// assert!(!intersects("fleet/@v1/**", "fleet/*/**")); // a verbatim chunk is sealed off
219/// ```
220pub fn intersects(a: &str, b: &str) -> bool {
221    let (Some(a), Some(b)) = (canonize(a), canonize(b)) else {
222        return false;
223    };
224    let a: Vec<&str> = a.split('/').collect();
225    let b: Vec<&str> = b.split('/').collect();
226    chunks_intersect(&a, &b)
227}
228
229/// Returns whether one key expression selects every key another one selects.
230///
231/// # Arguments
232///
233/// * `a` - the key expression that may be the wider one.
234/// * `b` - the key expression tested for being covered by `a`.
235///
236/// # Returns
237///
238/// `true` if every concrete key `b` selects is also selected by `a`, so a subscription on `a`
239/// already receives everything one on `b` would; `false` otherwise, or if either expression is
240/// not valid. An expression includes itself, and inclusion implies [`intersects`].
241///
242/// # Examples
243///
244/// ```
245/// use pamoja_zenoh::keyexpr::includes;
246///
247/// assert!(includes("fleet/**", "fleet/*/battery"));
248/// assert!(!includes("fleet/*/battery", "fleet/**"));
249/// assert!(includes("fleet/n$*", "fleet/n7")); // the sub-chunk wildcard selects within a chunk
250/// ```
251pub fn includes(a: &str, b: &str) -> bool {
252    let (Some(a), Some(b)) = (canonize(a), canonize(b)) else {
253        return false;
254    };
255    let a: Vec<&str> = a.split('/').collect();
256    let b: Vec<&str> = b.split('/').collect();
257    chunks_include(&a, &b)
258}
259
260fn is_wildcard(chunk: &str) -> bool {
261    chunk == "*" || chunk == "**"
262}
263
264fn is_verbatim(chunk: &str) -> bool {
265    chunk.starts_with('@')
266}
267
268fn chunk_valid(chunk: &str) -> bool {
269    if chunk.is_empty() {
270        return false;
271    }
272    if is_wildcard(chunk) {
273        return true;
274    }
275    let bytes = chunk.as_bytes();
276    let mut i = 0;
277    while i < bytes.len() {
278        match bytes[i] {
279            b'?' | b'#' | b'/' => return false,
280            b'$' => {
281                if i + 1 >= bytes.len() || bytes[i + 1] != b'*' {
282                    return false;
283                }
284                i += 2;
285            }
286            b'*' => return false,
287            _ => i += 1,
288        }
289    }
290    true
291}
292
293fn canon_chunk(chunk: &str) -> String {
294    if is_wildcard(chunk) {
295        return chunk.to_string();
296    }
297    let mut s = chunk.to_string();
298    while s.contains("$*$*") {
299        s = s.replace("$*$*", "$*");
300    }
301    if s == "$*" {
302        return String::from("*");
303    }
304    s
305}
306
307fn chunks_intersect(a: &[&str], b: &[&str]) -> bool {
308    let width = b.len() + 1;
309    let mut below = vec![false; width];
310    let mut row = vec![false; width];
311    below[b.len()] = true;
312    for j in (0..b.len()).rev() {
313        below[j] = b[j] == "**" && below[j + 1];
314    }
315    for i in (0..a.len()).rev() {
316        row[b.len()] = a[i] == "**" && below[b.len()];
317        for j in (0..b.len()).rev() {
318            row[j] = if a[i] == "**" {
319                below[j] || (!is_verbatim(b[j]) && row[j + 1])
320            } else if b[j] == "**" {
321                row[j + 1] || (!is_verbatim(a[i]) && below[j])
322            } else {
323                chunk_intersects(a[i], b[j]) && below[j + 1]
324            };
325        }
326        core::mem::swap(&mut row, &mut below);
327    }
328    below[0]
329}
330
331fn chunks_include(a: &[&str], b: &[&str]) -> bool {
332    let width = b.len() + 1;
333    let mut below = vec![false; width];
334    let mut row = vec![false; width];
335    below[b.len()] = true;
336    for i in (0..a.len()).rev() {
337        row[b.len()] = a[i] == "**" && below[b.len()];
338        for j in (0..b.len()).rev() {
339            row[j] = if a[i] == "**" {
340                below[j] || (!is_verbatim(b[j]) && row[j + 1])
341            } else {
342                b[j] != "**" && chunk_includes(a[i], b[j]) && below[j + 1]
343            };
344        }
345        core::mem::swap(&mut row, &mut below);
346    }
347    below[0]
348}
349
350fn chunk_intersects(a: &str, b: &str) -> bool {
351    if a == b {
352        return true;
353    }
354    if is_verbatim(a) || is_verbatim(b) {
355        return false;
356    }
357    a == "*" || b == "*" || globs_intersect(a, b)
358}
359
360fn chunk_includes(a: &str, b: &str) -> bool {
361    if a == b {
362        return true;
363    }
364    if is_verbatim(a) || is_verbatim(b) {
365        return false;
366    }
367    if a == "*" {
368        return true;
369    }
370    b != "*" && a.contains("$*") && glob_includes(a, b)
371}
372
373fn glob_tokens(chunk: &str) -> Vec<Option<u8>> {
374    let bytes = chunk.as_bytes();
375    let mut tokens = Vec::with_capacity(bytes.len());
376    let mut i = 0;
377    while i < bytes.len() {
378        if bytes[i] == b'$' {
379            tokens.push(None);
380            i += 2;
381        } else {
382            tokens.push(Some(bytes[i]));
383            i += 1;
384        }
385    }
386    tokens
387}
388
389fn globs_intersect(a: &str, b: &str) -> bool {
390    let a = glob_tokens(a);
391    let b = glob_tokens(b);
392    let width = b.len() + 1;
393    let mut below = vec![false; width];
394    let mut row = vec![false; width];
395    below[b.len()] = true;
396    for j in (0..b.len()).rev() {
397        below[j] = b[j].is_none() && below[j + 1];
398    }
399    for i in (0..a.len()).rev() {
400        row[b.len()] = a[i].is_none() && below[b.len()];
401        for j in (0..b.len()).rev() {
402            row[j] = match (a[i], b[j]) {
403                (None, _) => below[j] || row[j + 1],
404                (_, None) => row[j + 1] || below[j],
405                (Some(x), Some(y)) => x == y && below[j + 1],
406            };
407        }
408        core::mem::swap(&mut row, &mut below);
409    }
410    below[0]
411}
412
413fn glob_includes(a: &str, b: &str) -> bool {
414    let mut segments: Vec<&str> = a.split("$*").collect();
415    let Some(last) = segments.pop() else {
416        return false;
417    };
418    let Some(rest) = b.strip_prefix(segments[0]) else {
419        return false;
420    };
421    let Some(mut rest) = rest.strip_suffix(last) else {
422        return false;
423    };
424    for needle in segments[1..].iter().filter(|needle| !needle.is_empty()) {
425        match rest.find(needle) {
426            Some(at) => rest = &rest[at + needle.len()..],
427            None => return false,
428        }
429    }
430    true
431}
432
433#[cfg(test)]
434mod tests {
435    use super::*;
436
437    #[test]
438    fn validity_follows_the_chunk_rules() {
439        assert!(is_valid("a/b/c"));
440        assert!(is_valid("a/*/c"));
441        assert!(is_valid("a/**/c"));
442        assert!(is_valid("thermometer$*/temperature"));
443        assert!(is_valid("@/router/status"));
444        assert!(!is_valid("")); // empty
445        assert!(!is_valid("/a")); // leading slash
446        assert!(!is_valid("a/")); // trailing slash
447        assert!(!is_valid("a//b")); // doubled slash
448        assert!(!is_valid("a/b*")); // bare `*` inside a chunk
449        assert!(!is_valid("a/$x")); // `$` not before `*`
450        assert!(!is_valid("a/**b")); // `**` only as a whole chunk
451        assert!(!is_valid("a/b?")); // `?` is reserved
452        assert!(!is_valid("a/#")); // and so is `#`
453    }
454
455    #[test]
456    fn matching_against_concrete_keys() {
457        assert!(matches(
458            "room275/*/temperature",
459            "room275/device1/temperature"
460        ));
461        assert!(!matches("room275/*/temperature", "room275/temperature"));
462        assert!(!matches("room275/*/temperature", "room275/a/b/temperature"));
463
464        assert!(matches(
465            "organizationA/**/temperature",
466            "organizationA/temperature"
467        ));
468        assert!(matches(
469            "organizationA/**/temperature",
470            "organizationA/b8/r275/temperature"
471        ));
472
473        assert!(matches("**", "anything/at/all"));
474        assert!(matches("demo/**", "demo/a/b/c"));
475    }
476
477    #[test]
478    fn sub_chunk_wildcard_matches_within_a_chunk() {
479        assert!(matches(
480            "thermometer$*/temperature",
481            "thermometer1/temperature"
482        ));
483        assert!(matches(
484            "thermometer$*/temperature",
485            "thermometerA/temperature"
486        ));
487        assert!(matches(
488            "thermometer$*/temperature",
489            "thermometer/temperature"
490        )); // `$*` may be empty
491        assert!(!matches(
492            "thermometer$*/temperature",
493            "xthermometer1/temperature"
494        ));
495        assert!(matches("a$*b$*c", "aXXbYYc"));
496        assert!(!matches("a$*b$*c", "aXXc")); // the middle `b` is missing
497    }
498
499    #[test]
500    fn a_pattern_does_not_match_a_key_with_wildcards() {
501        assert!(!matches("a/*", "a/*"));
502        assert!(!matches("a/b", "a/*"));
503    }
504
505    #[test]
506    fn no_wildcard_selects_a_verbatim_chunk() {
507        assert!(!matches("**", "@/router/status"));
508        assert!(!matches("*/router/status", "@/router/status"));
509        assert!(!matches("fleet/*/battery", "fleet/@v1/battery"));
510        assert!(!matches("fleet/**/battery", "fleet/@v1/battery"));
511        assert!(!matches("fleet/$*/battery", "fleet/@v1/battery"));
512        assert!(matches("@/**", "@/router/status"));
513        assert!(matches("fleet/@v1/*", "fleet/@v1/battery"));
514        assert!(matches("fleet/**/@v1/battery", "fleet/n7/@v1/battery"));
515        // `$*` inside a verbatim chunk is part of its name, not a wildcard.
516        assert!(!matches("@v$*", "@v1"));
517        // A chunk is verbatim only when `@` leads it.
518        assert!(matches("fleet/*", "fleet/n@7"));
519    }
520
521    #[test]
522    fn canonical_form_examples() {
523        assert_eq!(
524            canonize("robot/sensor/**/*").as_deref(),
525            Some("robot/sensor/*/**")
526        );
527        assert_eq!(canonize("a/**/**/b").as_deref(), Some("a/**/b"));
528        assert_eq!(canonize("a/x$*$*y/$*").as_deref(), Some("a/x$*y/*"));
529        assert_eq!(canonize("**/*/*").as_deref(), Some("*/*/**"));
530
531        assert!(is_canon("robot/sensor/*/**"));
532        assert!(!is_canon("robot/sensor/**/*"));
533        assert!(!is_canon("a//b")); // invalid is never canonical
534    }
535
536    // The canonical-form statements of the Key Expressions RFC, as zenoh-keyexpr's own canon.rs
537    // checks them.
538    #[test]
539    fn canonical_form_matches_the_rfc_statements() {
540        let cases = [
541            ("hello/foo$*$*/bar", "hello/foo$*/bar"),
542            ("hello/**/**/bye", "hello/**/bye"),
543            ("hello/**/**", "hello/**"),
544            ("hello/$*/bye", "hello/*/bye"),
545            ("hello/$*$*/bye", "hello/*/bye"),
546            ("$*/hello/$*/bye", "*/hello/*/bye"),
547            ("$*$*$*/hello/$*/bye/$*", "*/hello/*/bye/*"),
548            ("$*$*$*/hello/$*$*/bye/$*$*", "*/hello/*/bye/*"),
549            ("hello/**/*", "hello/*/**"),
550        ];
551        for (written, canonical) in cases {
552            assert_eq!(canonize(written).as_deref(), Some(canonical), "{written}");
553        }
554        for invalid in [
555            "/a/b/",
556            "/a/b",
557            "a/b/",
558            "a/b/*$*",
559            "a/b/$**",
560            "a/b/**$*",
561            "a/b/*$**",
562            "a/b/*$***",
563            "a/b/**$**",
564            "a/b/**$***",
565        ] {
566            assert_eq!(canonize(invalid), None, "{invalid}");
567        }
568    }
569
570    #[test]
571    fn join_places_a_key_beneath_a_prefix() {
572        assert_eq!(
573            join("fleet/n7", "battery").as_deref(),
574            Some("fleet/n7/battery")
575        );
576        assert_eq!(join("fleet/**", "**").as_deref(), Some("fleet/**"));
577        assert_eq!(join("fleet/**", "*").as_deref(), Some("fleet/*/**"));
578        assert_eq!(join("fleet", ""), None);
579        assert_eq!(join("", "battery"), None);
580        assert_eq!(join("fleet/", "battery"), None);
581        assert_eq!(join("fleet", "bat?tery"), None);
582    }
583
584    // The examples of the Key Expressions RFC, in the eclipse-zenoh roadmap repository.
585    #[test]
586    fn relations_match_the_rfc_examples() {
587        for key in ["a/c/b", "a/hi/b"] {
588            assert!(includes("a/*/b", key), "a/*/b includes {key}");
589        }
590        for other in ["*/a/b", "*/*/*"] {
591            assert!(intersects("a/*/b", other), "a/*/b intersects {other}");
592        }
593        for other in ["a/*/c", "b/*/a", "a/hi/there/b", "a/hi/*/b"] {
594            assert!(
595                !intersects("a/*/b", other),
596                "a/*/b is disjoint with {other}"
597            );
598        }
599
600        for other in [
601            "a/b",
602            "a/**/b/b",
603            "a/*/b",
604            "a/*/*/b",
605            "a/*/**/b",
606            "a/**/c/**/b",
607        ] {
608            assert!(includes("a/**/b", other), "a/**/b includes {other}");
609        }
610        for other in ["**/b", "a/**"] {
611            assert!(intersects("a/**/b", other), "a/**/b intersects {other}");
612        }
613        assert!(!intersects("a/**/b", "a/**/b/c"));
614
615        assert!(includes("a/c$*/b", "a/cool/b"));
616        for other in ["a/*/b", "a/$*c/b"] {
617            assert!(intersects("a/c$*/b", other), "a/c$*/b intersects {other}");
618        }
619        assert!(!intersects("a/c$*/b", "a/uncool/b"));
620
621        let sealed = ["my-api/@v1/**", "my-api/@v2/**", "my-api/@$*/**"];
622        let open = ["my-api/*/**", "my-api/**"];
623        for (i, a) in sealed.iter().enumerate() {
624            for b in sealed[i + 1..].iter().chain(&open) {
625                assert!(!intersects(a, b), "{a} and {b} share no key");
626            }
627        }
628        assert!(includes("my-api/**", "my-api/*/**"));
629    }
630
631    // Every intersection vector in zenoh-keyexpr's src/key_expr/tests.rs.
632    #[test]
633    fn intersection_matches_the_zenoh_vectors() {
634        let cases = [
635            ("a", "a", true),
636            ("a/b", "a/b", true),
637            ("*", "abc", true),
638            ("*", "xxx", true),
639            ("ab$*", "abcd", true),
640            ("ab$*d", "abcd", true),
641            ("ab$*", "ab", true),
642            ("ab/*", "ab", false),
643            ("a/*/c/*/e", "a/b/c/d/e", true),
644            ("a/$*b/c/$*d/e", "a/xb/c/xd/e", true),
645            ("a/*/c/*/e", "a/c/e", false),
646            ("a/*/c/*/e", "a/b/c/d/x/e", false),
647            ("ab$*cd", "abxxcxxd", false),
648            ("ab$*cd", "abxxcxxcd", true),
649            ("ab$*cd", "abxxcxxcdx", false),
650            ("**", "abc", true),
651            ("**", "a/b/c", true),
652            ("ab/**", "ab", true),
653            ("**/xyz", "a/b/xyz/d/e/f/xyz", true),
654            ("**/xyz$*xyz", "a/b/xyz/d/e/f/xyz", false),
655            ("**/xyz$*xyz", "a/b/xyzdefxyz", true),
656            ("a/**/c/**/e", "a/b/b/b/c/d/d/d/e", true),
657            ("a/**/c/**/e", "a/c/e", true),
658            ("a/**/c/*/e/*", "a/b/b/b/c/d/d/c/d/e/f", true),
659            ("a/**/c/*/e/*", "a/b/b/b/c/d/d/c/d/d/e/f", false),
660            ("x/abc", "x/abc", true),
661            ("x/abc", "abc", false),
662            ("x/*", "x/abc", true),
663            ("x/*", "abc", false),
664            ("*", "x/abc", false),
665            ("x/*", "x/abc$*", true),
666            ("x/$*abc", "x/abc$*", true),
667            ("x/a$*", "x/abc$*", true),
668            ("x/a$*de", "x/abc$*de", true),
669            ("x/a$*d$*e", "x/a$*e", true),
670            ("x/a$*d$*e", "x/a$*c$*e", true),
671            ("x/a$*d$*e", "x/ade", true),
672            ("x/c$*", "x/abc$*", false),
673            ("x/$*d", "x/$*e", false),
674            ("@a", "@a", true),
675            ("@a", "@ab", false),
676            ("@a", "@a/b", false),
677            ("@a", "@a/*", false),
678            ("@a", "@a/*/**", false),
679            ("@a", "@a$*/**", false),
680            ("@a", "@a/**", true),
681            ("**/xyz$*xyz", "@a/b/xyzdefxyz", false),
682            ("@a/**/c/**/e", "@a/b/b/b/c/d/d/d/e", true),
683            ("@a/**/c/**/e", "@a/@b/b/b/c/d/d/d/e", false),
684            ("@a/**/@c/**/e", "@a/b/b/b/@c/d/d/d/e", true),
685            ("@a/**/e", "@a/b/b/d/d/d/e", true),
686            ("@a/**/e", "@a/b/b/b/d/d/d/e", true),
687            ("@a/**/e", "@a/b/b/c/d/d/d/e", true),
688            ("@a/**/e", "@a/b/b/@c/b/d/d/d/e", false),
689            ("@a/*", "@a/@b", false),
690            ("@a/**", "@a/@b", false),
691            ("@a/**/@b", "@a/@b", true),
692            ("@a/@b/**", "@a/@b", true),
693            ("@a/**/@c/**/@b", "@a/**/@c/@b", true),
694            ("@a/**/@c/**/@b", "@a/@c/**/@b", true),
695            ("@a/**/@c/@b", "@a/@c/**/@b", true),
696            ("@a/**/@b", "@a/**/@c/**/@b", false),
697            ("@a", "**/@a", true),
698        ];
699        for (a, b, want) in cases {
700            assert_eq!(intersects(a, b), want, "{a} intersects {b}");
701            assert_eq!(intersects(b, a), want, "{b} intersects {a}");
702        }
703    }
704
705    // Every inclusion vector in zenoh-keyexpr's src/key_expr/tests.rs.
706    #[test]
707    fn inclusion_matches_the_zenoh_vectors() {
708        let cases = [
709            ("a", "a", true),
710            ("a/b", "a/b", true),
711            ("*", "abc", true),
712            ("*", "xxx", true),
713            ("ab$*", "abcd", true),
714            ("ab$*d", "abcd", true),
715            ("ab$*", "ab", true),
716            ("ab/*", "ab", false),
717            ("a/*/c/*/e", "a/b/c/d/e", true),
718            ("a/$*b/c/$*d/e", "a/xb/c/xd/e", true),
719            ("a/*/c/*/e", "a/c/e", false),
720            ("a/*/c/*/e", "a/b/c/d/x/e", false),
721            ("ab$*cd", "abxxcxxd", false),
722            ("ab$*c$*d", "abxxcxxd", true),
723            ("ab$*cd", "abxxcxxcd", true),
724            ("ab$*cd", "abxxcxxcdx", false),
725            ("**", "abc", true),
726            ("**", "a/b/c", true),
727            ("ab/**", "ab", true),
728            ("**/xyz", "a/b/xyz/d/e/f/xyz", true),
729            ("**/xyz$*xyz", "a/b/xyz/d/e/f/xyz", false),
730            ("**/xyz$*xyz", "a/b/xyzdefxyz", true),
731            ("a/**/c/**/e", "a/b/b/b/c/d/d/d/e", true),
732            ("a/**/c/**/e", "a/c/e", true),
733            ("a/**/c/*/e/*", "a/b/b/b/c/d/d/c/d/e/f", true),
734            ("a/**/c/*/e/*", "a/b/b/b/c/d/d/c/d/d/e/f", false),
735            ("x/abc", "x/abc", true),
736            ("x/abc", "abc", false),
737            ("x/*", "x/abc", true),
738            ("x/*", "abc", false),
739            ("*", "x/abc", false),
740            ("x/*", "x/abc$*", true),
741            ("x/$*abc", "x/abc$*", false),
742            ("x/a$*", "x/abc$*", true),
743            ("x/abc$*", "x/a$*", false),
744            ("x/a$*de", "x/abc$*de", true),
745            ("x/a$*e", "x/a$*d$*e", true),
746            ("x/a$*d$*e", "x/a$*e", false),
747            ("x/a$*d$*e", "x/a$*c$*e", false),
748            ("x/a$*d$*e", "x/ade", true),
749            ("x/c$*", "x/abc$*", false),
750            ("x/$*c$*", "x/abc$*", true),
751            ("x/$*d", "x/$*e", false),
752            ("@a", "@a", true),
753            ("@a", "@ab", false),
754            ("@a", "@a/b", false),
755            ("@a", "@a/*", false),
756            ("@a", "@a/*/**", false),
757            ("@a$*/**", "@a", false),
758            ("@a", "@a/**", false),
759            ("@a/**", "@a", true),
760            ("**/xyz$*xyz", "@a/b/xyzdefxyz", false),
761            ("@a/**/c/**/e", "@a/b/b/b/c/d/d/d/e", true),
762            ("@a/*", "@a/@b", false),
763            ("@a/**", "@a/@b", false),
764            ("@a/**/@b", "@a/@b", true),
765            ("@a/@b/**", "@a/@b", true),
766        ];
767        for (a, b, want) in cases {
768            assert_eq!(includes(a, b), want, "{a} includes {b}");
769        }
770    }
771
772    #[test]
773    fn relations_refuse_a_malformed_expression() {
774        assert!(!intersects("a//b", "**"));
775        assert!(!intersects("**", "a/b?"));
776        assert!(!includes("**", "a//b"));
777        assert!(!includes("a/", "a"));
778    }
779
780    #[test]
781    fn relations_read_any_spelling_of_the_same_set() {
782        assert!(includes("a/**/**/b", "a/x/b"));
783        assert!(intersects("a/**/*", "a/*/**"));
784        assert!(includes("a/**/*", "a/*/**") && includes("a/*/**", "a/**/*"));
785        assert!(includes("@v$*$*", "@v$*")); // one verbatim chunk, once canonized
786    }
787
788    // Checks the three answers against each other on every key a small alphabet spells: a
789    // shared key proves an intersection, and inclusion has to hold key by key.
790    #[test]
791    fn relations_agree_with_the_keys_they_select() {
792        let keys = spell(&["a", "b", "ab", "ba", "@a"], 3);
793        let patterns = spell(&["a", "@a", "*", "**", "a$*", "$*a", "$*b$*", "a$*b"], 3);
794        let selected: Vec<Vec<bool>> = patterns
795            .iter()
796            .map(|pattern| keys.iter().map(|key| matches(pattern, key)).collect())
797            .collect();
798        for (a, a_keys) in patterns.iter().zip(&selected) {
799            for (b, b_keys) in patterns.iter().zip(&selected) {
800                let shared = a_keys.iter().zip(b_keys).any(|(x, y)| *x && *y);
801                if shared {
802                    assert!(intersects(a, b), "{a} and {b} share a key");
803                }
804                if includes(a, b) {
805                    assert!(intersects(a, b), "{a} includes {b}, so they intersect");
806                    let covered = a_keys.iter().zip(b_keys).all(|(x, y)| *x || !*y);
807                    assert!(covered, "{a} includes {b}, key by key");
808                }
809                assert_eq!(intersects(a, b), intersects(b, a), "{a} and {b}");
810            }
811        }
812    }
813
814    fn spell(forms: &[&str], depth: usize) -> Vec<String> {
815        let mut spelled: Vec<String> = forms.iter().map(|form| form.to_string()).collect();
816        let mut last = spelled.clone();
817        for _ in 1..depth {
818            last = last
819                .iter()
820                .flat_map(|head| forms.iter().map(move |form| format!("{head}/{form}")))
821                .collect();
822            spelled.extend(last.iter().cloned());
823        }
824        spelled
825    }
826
827    // Asks Zenoh's own implementation the same questions, on every expression three chunks of
828    // these forms spell, well formed or not. Zenoh 1.10.1's canonizer indexes past the end of a
829    // string that ends within two bytes of a doubled `$*`, so the doubled form is spelled with
830    // two characters after it.
831    #[cfg(feature = "runtime")]
832    #[test]
833    fn answers_agree_with_zenoh() {
834        use zenoh::key_expr::{keyexpr, OwnedKeyExpr};
835
836        let written = spell(
837            &[
838                "a", "@a", "*", "**", "$*", "$*$*", "a$*$*bc", "@a$*", "a*", "$a", "a?", "#",
839            ],
840            3,
841        );
842        for text in &written {
843            let theirs = OwnedKeyExpr::autocanonize(text.clone())
844                .ok()
845                .map(|ke| ke.to_string());
846            assert_eq!(canonize(text), theirs, "the canonical form of {text}");
847            assert_eq!(
848                is_canon(text),
849                keyexpr::new(text.as_str()).is_ok(),
850                "whether {text} is canonical"
851            );
852        }
853
854        let canonical: Vec<String> = spell(
855            &["a", "ab", "@a", "*", "**", "a$*", "$*b", "a$*b", "$*a$*"],
856            3,
857        )
858        .into_iter()
859        .filter(|text| is_canon(text))
860        .collect();
861        for a in &canonical {
862            let theirs_a = keyexpr::new(a.as_str()).expect("a canonical expression");
863            for b in &canonical {
864                let theirs_b = keyexpr::new(b.as_str()).expect("a canonical expression");
865                assert_eq!(
866                    intersects(a, b),
867                    theirs_a.intersects(theirs_b),
868                    "{a} intersects {b}"
869                );
870                assert_eq!(
871                    includes(a, b),
872                    theirs_a.includes(theirs_b),
873                    "{a} includes {b}"
874                );
875            }
876        }
877    }
878}
pamoja_zenoh/keyexpr.rs

pamoja_zenoh/
keyexpr.rs
