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

zenoh_keyexpr/keyexpr_tree/iters/
includer.rs
