zenoh_protocol_core/key_expr/intersect/
classical.rs

1//
2// Copyright (c) 2022 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    chunk_it_intersect::<STAR_DSL>(c1, c2)
70}
71
72#[inline(always)]
73fn next(s: &[u8]) -> (&[u8], &[u8]) {
74    match s.iter().position(|c| *c == b'/') {
75        Some(i) => (&s[..i], &s[(i + 1)..]),
76        None => (s, b""),
77    }
78}
79
80fn it_intersect<const STAR_DSL: bool>(mut it1: &[u8], mut it2: &[u8]) -> bool {
81    while !it1.is_empty() && !it2.is_empty() {
82        let (current1, advanced1) = next(it1);
83        let (current2, advanced2) = next(it2);
84        match (current1, current2) {
85            (b"**", _) => {
86                return advanced1.is_empty()
87                    || it_intersect::<STAR_DSL>(advanced1, it2)
88                    || it_intersect::<STAR_DSL>(it1, advanced2);
89            }
90            (_, b"**") => {
91                return advanced2.is_empty()
92                    || it_intersect::<STAR_DSL>(it1, advanced2)
93                    || it_intersect::<STAR_DSL>(advanced1, it2);
94            }
95            (sub1, sub2) if chunk_intersect::<STAR_DSL>(sub1, sub2) => {
96                it1 = advanced1;
97                it2 = advanced2;
98            }
99            (_, _) => return false,
100        }
101    }
102    (it1.is_empty() || it1 == b"**") && (it2.is_empty() || it2 == b"**")
103}
104/// Retruns `true` if the given key expressions intersect.
105///
106/// I.e. if it exists a resource key (with no wildcards) that matches
107/// both given key expressions.
108#[inline(always)]
109pub fn intersect<const STAR_DSL: bool>(s1: &[u8], s2: &[u8]) -> bool {
110    it_intersect::<STAR_DSL>(s1, s2)
111}
112
113use super::restiction::NoSubWilds;
114use super::Intersector;
115
116pub struct ClassicIntersector;
117impl Intersector<NoSubWilds<&[u8]>, NoSubWilds<&[u8]>> for ClassicIntersector {
118    fn intersect(&self, left: NoSubWilds<&[u8]>, right: NoSubWilds<&[u8]>) -> bool {
119        intersect::<false>(left.0, right.0)
120    }
121}
122
123impl Intersector<&[u8], &[u8]> for ClassicIntersector {
124    fn intersect(&self, left: &[u8], right: &[u8]) -> bool {
125        intersect::<true>(left, right)
126    }
127}
zenoh_protocol_core/key_expr/intersect/classical.rs

zenoh_protocol_core/key_expr/intersect/
classical.rs
