zenoh_keyexpr/key_expr/intersect/
classical.rs

1//
2// Copyright (c) 2023 ZettaScale Technology
3//
4// This program and the accompanying materials are made available under the
5// terms of the Eclipse Public License 2.0 which is available at
6// http://www.eclipse.org/legal/epl-2.0, or the Apache License, Version 2.0
7// which is available at https://www.apache.org/licenses/LICENSE-2.0.
8//
9// SPDX-License-Identifier: EPL-2.0 OR Apache-2.0
10//
11// Contributors:
12//   ZettaScale Zenoh Team, <zenoh@zettascale.tech>
13//
14#[cold]
15fn star_dsl_intersect(mut it1: &[u8], mut it2: &[u8]) -> bool {
16    fn next(s: &[u8]) -> (u8, &[u8]) {
17        (s[0], &s[1..])
18    }
19    while !it1.is_empty() && !it2.is_empty() {
20        let (current1, advanced1) = next(it1);
21        let (current2, advanced2) = next(it2);
22        match (current1, current2) {
23            (b'$', b'$') => {
24                if advanced1.len() == 1 || advanced2.len() == 1 {
25                    return true;
26                }
27                if star_dsl_intersect(&advanced1[1..], it2) {
28                    return true;
29                } else {
30                    return star_dsl_intersect(it1, &advanced2[1..]);
31                };
32            }
33            (b'$', _) => {
34                if advanced1.len() == 1 {
35                    return true;
36                }
37                if star_dsl_intersect(&advanced1[1..], it2) {
38                    return true;
39                }
40                it2 = advanced2;
41            }
42            (_, b'$') => {
43                if advanced2.len() == 1 {
44                    return true;
45                }
46                if star_dsl_intersect(it1, &advanced2[1..]) {
47                    return true;
48                }
49                it1 = advanced1;
50            }
51            (sub1, sub2) if sub1 == sub2 => {
52                it1 = advanced1;
53                it2 = advanced2;
54            }
55            (_, _) => return false,
56        }
57    }
58    it1.is_empty() && it2.is_empty() || it1 == b"$*" || it2 == b"$*"
59}
60
61fn chunk_it_intersect<const STAR_DSL: bool>(it1: &[u8], it2: &[u8]) -> bool {
62    it1 == b"*" || it2 == b"*" || (STAR_DSL && star_dsl_intersect(it1, it2))
63}
64#[inline(always)]
65fn chunk_intersect<const STAR_DSL: bool>(c1: &[u8], c2: &[u8]) -> bool {
66    if c1 == c2 {
67        return true;
68    }
69    if c1.has_direct_verbatim() || c2.has_direct_verbatim() {
70        return false;
71    }
72    chunk_it_intersect::<STAR_DSL>(c1, c2)
73}
74
75#[inline(always)]
76fn next(s: &[u8]) -> (&[u8], &[u8]) {
77    match s.iter().position(|c| *c == b'/') {
78        Some(i) => (&s[..i], &s[(i + 1)..]),
79        None => (s, b""),
80    }
81}
82
83fn it_intersect<const STAR_DSL: bool>(mut it1: &[u8], mut it2: &[u8]) -> bool {
84    while !it1.is_empty() && !it2.is_empty() {
85        let (current1, advanced1) = next(it1);
86        let (current2, advanced2) = next(it2);
87        match (current1, current2) {
88            (b"**", _) => {
89                if advanced1.is_empty() {
90                    return !it2.has_verbatim();
91                }
92                return (!unsafe { current2.has_direct_verbatim_non_empty() }
93                    && it_intersect::<STAR_DSL>(it1, advanced2))
94                    || it_intersect::<STAR_DSL>(advanced1, it2);
95            }
96            (_, b"**") => {
97                if advanced2.is_empty() {
98                    return !it1.has_verbatim();
99                }
100                return (!unsafe { current1.has_direct_verbatim_non_empty() }
101                    && it_intersect::<STAR_DSL>(advanced1, it2))
102                    || it_intersect::<STAR_DSL>(it1, advanced2);
103            }
104            (sub1, sub2) if chunk_intersect::<STAR_DSL>(sub1, sub2) => {
105                it1 = advanced1;
106                it2 = advanced2;
107            }
108            (_, _) => return false,
109        }
110    }
111    (it1.is_empty() || it1 == b"**") && (it2.is_empty() || it2 == b"**")
112}
113/// Returns `true` if the given key expressions intersect.
114///
115/// I.e. if it exists a resource key (with no wildcards) that matches
116/// both given key expressions.
117#[inline(always)]
118pub fn intersect<const STAR_DSL: bool>(s1: &[u8], s2: &[u8]) -> bool {
119    it_intersect::<STAR_DSL>(s1, s2)
120}
121
122use super::{restriction::NoSubWilds, Intersector, MayHaveVerbatim};
123
124pub struct ClassicIntersector;
125impl Intersector<NoSubWilds<&[u8]>, NoSubWilds<&[u8]>> for ClassicIntersector {
126    fn intersect(&self, left: NoSubWilds<&[u8]>, right: NoSubWilds<&[u8]>) -> bool {
127        intersect::<false>(left.0, right.0)
128    }
129}
130
131impl Intersector<&[u8], &[u8]> for ClassicIntersector {
132    fn intersect(&self, left: &[u8], right: &[u8]) -> bool {
133        intersect::<true>(left, right)
134    }
135}
zenoh_keyexpr/key_expr/intersect/classical.rs

zenoh_keyexpr/key_expr/intersect/
classical.rs
