zenoh_keyexpr/keyexpr_tree/iters/
inclusion.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
15use alloc::vec::Vec;
16
17use zenoh_result::unlikely;
18
19use crate::keyexpr_tree::*;
20
21struct StackFrame<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
22where
23    Children::Assoc: IChildren<Node> + 'a,
24    <Children::Assoc as IChildren<Node>>::Node: 'a,
25{
26    iterator: <Children::Assoc as IChildren<Node>>::Iter<'a>,
27    start: usize,
28    end: usize,
29    _marker: core::marker::PhantomData<Weight>,
30}
31pub struct Inclusion<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
32where
33    Children::Assoc: IChildren<Node> + 'a,
34{
35    key: &'a keyexpr,
36    ke_indices: Vec<usize>,
37    iterators: Vec<StackFrame<'a, Children, Node, Weight>>,
38}
39
40impl<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
41    Inclusion<'a, Children, Node, Weight>
42where
43    Children::Assoc: IChildren<Node> + 'a,
44{
45    pub(crate) fn new(children: &'a Children::Assoc, key: &'a keyexpr) -> Self {
46        let mut ke_indices = Vec::with_capacity(32);
47        ke_indices.push(0);
48        let mut iterators = Vec::with_capacity(16);
49        iterators.push(StackFrame {
50            iterator: children.children(),
51            start: 0,
52            end: 1,
53            _marker: Default::default(),
54        });
55        Self {
56            key,
57            ke_indices,
58            iterators,
59        }
60    }
61}
62
63impl<
64        'a,
65        Children: IChildrenProvider<Node>,
66        Node: UIKeyExprTreeNode<Weight, Children = Children::Assoc> + 'a,
67        Weight,
68    > Iterator for Inclusion<'a, Children, Node, Weight>
69where
70    Children::Assoc: IChildren<Node> + 'a,
71{
72    type Item = &'a Node;
73    fn next(&mut self) -> Option<Self::Item> {
74        loop {
75            let StackFrame {
76                iterator,
77                start,
78                end,
79                _marker,
80            } = self.iterators.last_mut()?;
81            match iterator.next() {
82                Some(node) => {
83                    let mut node_matches = false;
84                    let new_start = *end;
85                    let mut new_end = *end;
86                    macro_rules! push {
87                        ($index: expr) => {
88                            let index = $index;
89                            if new_end == new_start
90                                || self.ke_indices[new_start..new_end]
91                                    .iter()
92                                    .rev()
93                                    .all(|c| *c < index)
94                            {
95                                self.ke_indices.push(index);
96                                new_end += 1;
97                            }
98                        };
99                    }
100                    let chunk = node.chunk();
101                    let chunk_is_verbatim = chunk.first_byte() == b'@';
102                    for i in *start..*end {
103                        let kec_start = self.ke_indices[i];
104                        if kec_start == self.key.len() {
105                            break;
106                        }
107                        let key = &self.key.as_bytes()[kec_start..];
108                        match key.iter().position(|&c| c == b'/') {
109                            Some(kec_end) => {
110                                let subkey =
111                                    // SAFETY: upheld by the surrounding invariants and prior validation.
112                                    unsafe { keyexpr::from_slice_unchecked(&key[..kec_end]) };
113                                if unlikely(subkey == "**") {
114                                    if !chunk_is_verbatim {
115                                        push!(kec_start);
116                                        push!(kec_start + kec_end + 1);
117                                    }
118                                    let post_key = &key[kec_end + 1..];
119                                    match post_key.iter().position(|&c| c == b'/') {
120                                        Some(sec_end) => {
121                                            // SAFETY: upheld by the surrounding invariants and prior validation.
122                                            let post_key = unsafe {
123                                                keyexpr::from_slice_unchecked(&post_key[..sec_end])
124                                            };
125                                            if post_key.includes(chunk) {
126                                                push!(kec_start + kec_end + sec_end + 2);
127                                            }
128                                        }
129                                        None => {
130                                            // SAFETY: upheld by the surrounding invariants and prior validation.
131                                            if unsafe { keyexpr::from_slice_unchecked(post_key) }
132                                                .includes(chunk)
133                                            {
134                                                node_matches = true;
135                                            }
136                                        }
137                                    }
138                                } else if subkey.includes(chunk) {
139                                    push!(kec_start + kec_end + 1);
140                                }
141                            }
142                            None => {
143                                // SAFETY: upheld by the surrounding invariants and prior validation.
144                                let key = unsafe { keyexpr::from_slice_unchecked(key) };
145                                if unlikely(key == "**") && chunk.first_byte() != b'@' {
146                                    push!(kec_start);
147                                    node_matches = true;
148                                } else if key.includes(chunk) {
149                                    push!(self.key.len());
150                                    node_matches = true;
151                                }
152                            }
153                        }
154                    }
155                    if new_end > new_start {
156                        for &i in &self.ke_indices[new_start..new_end] {
157                            if &self.key.as_bytes()[i..] == b"**" {
158                                node_matches = true;
159                                break;
160                            }
161                        }
162                        // SAFETY: upheld by the surrounding invariants and prior validation.
163                        let iterator = unsafe { node.as_node().__children() }.children();
164                        self.iterators.push(StackFrame {
165                            iterator,
166                            start: new_start,
167                            end: new_end,
168                            _marker: Default::default(),
169                        })
170                    }
171                    if node_matches {
172                        return Some(node.as_node());
173                    }
174                }
175                None => {
176                    if let Some(StackFrame { start, .. }) = self.iterators.pop() {
177                        self.ke_indices.truncate(start);
178                    }
179                }
180            }
181        }
182    }
183}
184struct StackFrameMut<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
185where
186    Children::Assoc: IChildren<Node> + 'a,
187    <Children::Assoc as IChildren<Node>>::Node: 'a,
188{
189    iterator: <Children::Assoc as IChildren<Node>>::IterMut<'a>,
190    start: usize,
191    end: usize,
192    _marker: core::marker::PhantomData<Weight>,
193}
194
195pub struct InclusionMut<
196    'a,
197    Children: IChildrenProvider<Node>,
198    Node: UIKeyExprTreeNode<Weight>,
199    Weight,
200> where
201    Children::Assoc: IChildren<Node> + 'a,
202{
203    key: &'a keyexpr,
204    ke_indices: Vec<usize>,
205    iterators: Vec<StackFrameMut<'a, Children, Node, Weight>>,
206}
207
208impl<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
209    InclusionMut<'a, Children, Node, Weight>
210where
211    Children::Assoc: IChildren<Node> + 'a,
212{
213    pub(crate) fn new(children: &'a mut Children::Assoc, key: &'a keyexpr) -> Self {
214        let mut ke_indices = Vec::with_capacity(32);
215        ke_indices.push(0);
216        let mut iterators = Vec::with_capacity(16);
217        iterators.push(StackFrameMut {
218            iterator: children.children_mut(),
219            start: 0,
220            end: 1,
221            _marker: Default::default(),
222        });
223        Self {
224            key,
225            ke_indices,
226            iterators,
227        }
228    }
229}
230
231impl<
232        'a,
233        Children: IChildrenProvider<Node>,
234        Node: IKeyExprTreeNodeMut<Weight, Children = Children::Assoc> + 'a,
235        Weight,
236    > Iterator for InclusionMut<'a, Children, Node, Weight>
237where
238    Children::Assoc: IChildren<Node> + 'a,
239{
240    type Item = &'a mut <Children::Assoc as IChildren<Node>>::Node;
241    fn next(&mut self) -> Option<Self::Item> {
242        loop {
243            let StackFrameMut {
244                iterator,
245                start,
246                end,
247                _marker,
248            } = self.iterators.last_mut()?;
249            match iterator.next() {
250                Some(node) => {
251                    let mut node_matches = false;
252                    let new_start = *end;
253                    let mut new_end = *end;
254                    macro_rules! push {
255                        ($index: expr) => {
256                            let index = $index;
257                            if new_end == new_start
258                                || self.ke_indices[new_start..new_end]
259                                    .iter()
260                                    .rev()
261                                    .all(|c| *c < index)
262                            {
263                                self.ke_indices.push(index);
264                                new_end += 1;
265                            }
266                        };
267                    }
268                    let chunk = node.chunk();
269                    let chunk_is_verbatim = chunk.first_byte() == b'@';
270                    for i in *start..*end {
271                        let kec_start = self.ke_indices[i];
272                        if kec_start == self.key.len() {
273                            break;
274                        }
275                        let key = &self.key.as_bytes()[kec_start..];
276                        match key.iter().position(|&c| c == b'/') {
277                            Some(kec_end) => {
278                                let subkey =
279                                    // SAFETY: upheld by the surrounding invariants and prior validation.
280                                    unsafe { keyexpr::from_slice_unchecked(&key[..kec_end]) };
281                                if unlikely(subkey == "**") {
282                                    if !chunk_is_verbatim {
283                                        push!(kec_start);
284                                        push!(kec_start + kec_end + 1);
285                                    }
286                                    let post_key = &key[kec_end + 1..];
287                                    match post_key.iter().position(|&c| c == b'/') {
288                                        Some(sec_end) => {
289                                            // SAFETY: upheld by the surrounding invariants and prior validation.
290                                            let post_key = unsafe {
291                                                keyexpr::from_slice_unchecked(&post_key[..sec_end])
292                                            };
293                                            if post_key.includes(chunk) {
294                                                push!(kec_start + kec_end + sec_end + 2);
295                                            }
296                                        }
297                                        None => {
298                                            // SAFETY: upheld by the surrounding invariants and prior validation.
299                                            if unsafe { keyexpr::from_slice_unchecked(post_key) }
300                                                .includes(chunk)
301                                            {
302                                                node_matches = true;
303                                            }
304                                        }
305                                    }
306                                } else if subkey.includes(chunk) {
307                                    push!(kec_start + kec_end + 1);
308                                }
309                            }
310                            None => {
311                                // SAFETY: upheld by the surrounding invariants and prior validation.
312                                let key = unsafe { keyexpr::from_slice_unchecked(key) };
313                                if unlikely(key == "**") && chunk.first_byte() != b'@' {
314                                    push!(kec_start);
315                                    node_matches = true;
316                                } else if key.includes(chunk) {
317                                    push!(self.key.len());
318                                    node_matches = true;
319                                }
320                            }
321                        }
322                    }
323                    if new_end > new_start {
324                        for &i in &self.ke_indices[new_start..new_end] {
325                            if &self.key.as_bytes()[i..] == b"**" {
326                                node_matches = true;
327                                break;
328                            }
329                        }
330                        // SAFETY: upheld by the surrounding invariants and prior validation.
331                        let iterator = unsafe { &mut *(node.as_node_mut() as *mut Node) }
332                            .children_mut()
333                            .children_mut();
334                        self.iterators.push(StackFrameMut {
335                            iterator,
336                            start: new_start,
337                            end: new_end,
338                            _marker: Default::default(),
339                        })
340                    }
341                    if node_matches {
342                        return Some(node);
343                    }
344                }
345                None => {
346                    if let Some(StackFrameMut { start, .. }) = self.iterators.pop() {
347                        self.ke_indices.truncate(start);
348                    }
349                }
350            }
351        }
352    }
353}
zenoh_keyexpr/keyexpr_tree/iters/inclusion.rs

zenoh_keyexpr/keyexpr_tree/iters/
inclusion.rs
