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

zenoh_keyexpr/keyexpr_tree/iters/
includer.rs
