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                    unsafe { node.as_node().__keyexpr() };
100                    let chunk_is_super = chunk == "**";
101                    if chunk_is_super {
102                        let mut latest_idx = usize::MAX;
103                        'outer: for i in *start..*end {
104                            let mut kec_start = self.ke_indices[i];
105                            if kec_start == self.key.len() {
106                                node_matches = true;
107                                break;
108                            }
109                            if latest_idx <= kec_start && latest_idx != usize::MAX {
110                                continue;
111                            }
112                            loop {
113                                push!(kec_start);
114                                latest_idx = kec_start;
115                                let key = &self.key.as_bytes()[kec_start..];
116                                if key[0] == b'@' {
117                                    break;
118                                }
119                                match key.iter().position(|&c| c == b'/') {
120                                    Some(kec_end) => kec_start += kec_end + 1,
121                                    None => {
122                                        node_matches = true;
123                                        break 'outer;
124                                    }
125                                }
126                            }
127                        }
128                    } else {
129                        for i in *start..*end {
130                            let kec_start = self.ke_indices[i];
131                            if kec_start == self.key.len() {
132                                break;
133                            }
134                            let key = &self.key.as_bytes()[kec_start..];
135                            unsafe { keyexpr::from_slice_unchecked(key) };
136                            match key.iter().position(|&c| c == b'/') {
137                                Some(kec_end) => {
138                                    let subkey =
139                                        unsafe { keyexpr::from_slice_unchecked(&key[..kec_end]) };
140                                    if chunk.includes(subkey) {
141                                        push!(kec_start + kec_end + 1);
142                                    }
143                                }
144                                None => {
145                                    let key = unsafe { keyexpr::from_slice_unchecked(key) };
146                                    if chunk.includes(key) {
147                                        push!(self.key.len());
148                                        node_matches = true;
149                                    }
150                                }
151                            }
152                        }
153                    }
154                    if new_end > new_start {
155                        let iterator = unsafe { node.as_node().__children() }.children();
156                        self.iterators.push(StackFrame {
157                            iterator,
158                            start: new_start,
159                            end: new_end,
160                            _marker: Default::default(),
161                        })
162                    }
163                    if node_matches {
164                        return Some(node.as_node());
165                    }
166                }
167                None => {
168                    if let Some(StackFrame { start, .. }) = self.iterators.pop() {
169                        self.ke_indices.truncate(start);
170                    }
171                }
172            }
173        }
174    }
175}
176struct StackFrameMut<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
177where
178    Children::Assoc: IChildren<Node> + 'a,
179    <Children::Assoc as IChildren<Node>>::Node: 'a,
180{
181    iterator: <Children::Assoc as IChildren<Node>>::IterMut<'a>,
182    start: usize,
183    end: usize,
184    _marker: core::marker::PhantomData<Weight>,
185}
186
187pub struct IncluderMut<
188    'a,
189    Children: IChildrenProvider<Node>,
190    Node: UIKeyExprTreeNode<Weight>,
191    Weight,
192> where
193    Children::Assoc: IChildren<Node> + 'a,
194{
195    key: &'a keyexpr,
196    ke_indices: Vec<usize>,
197    iterators: Vec<StackFrameMut<'a, Children, Node, Weight>>,
198}
199
200impl<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
201    IncluderMut<'a, Children, Node, Weight>
202where
203    Children::Assoc: IChildren<Node> + 'a,
204{
205    pub(crate) fn new(children: &'a mut Children::Assoc, key: &'a keyexpr) -> Self {
206        let mut ke_indices = Vec::with_capacity(32);
207        ke_indices.push(0);
208        let mut iterators = Vec::with_capacity(16);
209        iterators.push(StackFrameMut {
210            iterator: children.children_mut(),
211            start: 0,
212            end: 1,
213            _marker: Default::default(),
214        });
215        Self {
216            key,
217            ke_indices,
218            iterators,
219        }
220    }
221}
222
223impl<
224        'a,
225        Children: IChildrenProvider<Node>,
226        Node: IKeyExprTreeNodeMut<Weight, Children = Children::Assoc> + 'a,
227        Weight,
228    > Iterator for IncluderMut<'a, Children, Node, Weight>
229where
230    Children::Assoc: IChildren<Node> + 'a,
231{
232    type Item = &'a mut <Children::Assoc as IChildren<Node>>::Node;
233    fn next(&mut self) -> Option<Self::Item> {
234        loop {
235            let StackFrameMut {
236                iterator,
237                start,
238                end,
239                _marker,
240            } = self.iterators.last_mut()?;
241            match iterator.next() {
242                Some(node) => {
243                    let mut node_matches = false;
244                    let new_start = *end;
245                    let mut new_end = *end;
246                    macro_rules! push {
247                        ($index: expr) => {
248                            let index = $index;
249                            if new_end == new_start
250                                || self.ke_indices[new_start..new_end]
251                                    .iter()
252                                    .rev()
253                                    .all(|c| *c < index)
254                            {
255                                self.ke_indices.push(index);
256                                new_end += 1;
257                            }
258                        };
259                    }
260                    let chunk = node.chunk();
261                    let chunk_is_super = chunk == "**";
262                    if chunk_is_super {
263                        let mut latest_idx = usize::MAX;
264                        'outer: for i in *start..*end {
265                            let mut kec_start = self.ke_indices[i];
266                            if kec_start == self.key.len() {
267                                node_matches = true;
268                                break;
269                            }
270                            if latest_idx <= kec_start && latest_idx != usize::MAX {
271                                continue;
272                            }
273                            loop {
274                                push!(kec_start);
275                                latest_idx = kec_start;
276                                let key = &self.key.as_bytes()[kec_start..];
277                                if key[0] == b'@' {
278                                    break;
279                                }
280                                match key.iter().position(|&c| c == b'/') {
281                                    Some(kec_end) => kec_start += kec_end + 1,
282                                    None => {
283                                        node_matches = true;
284                                        break 'outer;
285                                    }
286                                }
287                            }
288                        }
289                    } else {
290                        for i in *start..*end {
291                            let kec_start = self.ke_indices[i];
292                            if kec_start == self.key.len() {
293                                break;
294                            }
295                            let key = &self.key.as_bytes()[kec_start..];
296                            unsafe { keyexpr::from_slice_unchecked(key) };
297                            match key.iter().position(|&c| c == b'/') {
298                                Some(kec_end) => {
299                                    let subkey =
300                                        unsafe { keyexpr::from_slice_unchecked(&key[..kec_end]) };
301                                    if chunk.includes(subkey) {
302                                        push!(kec_start + kec_end + 1);
303                                    }
304                                }
305                                None => {
306                                    let key = unsafe { keyexpr::from_slice_unchecked(key) };
307                                    if chunk.includes(key) {
308                                        push!(self.key.len());
309                                        node_matches = true;
310                                    }
311                                }
312                            }
313                        }
314                    }
315                    if new_end > new_start {
316                        let iterator = unsafe { &mut *(node.as_node_mut() as *mut Node) }
317                            .children_mut()
318                            .children_mut();
319                        self.iterators.push(StackFrameMut {
320                            iterator,
321                            start: new_start,
322                            end: new_end,
323                            _marker: Default::default(),
324                        })
325                    }
326                    if node_matches {
327                        return Some(node);
328                    }
329                }
330                None => {
331                    if let Some(StackFrameMut { start, .. }) = self.iterators.pop() {
332                        self.ke_indices.truncate(start);
333                    }
334                }
335            }
336        }
337    }
338}
zenoh_keyexpr/keyexpr_tree/iters/includer.rs

zenoh_keyexpr/keyexpr_tree/iters/
includer.rs
