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

zenoh_keyexpr/keyexpr_tree/iters/
inclusion.rs
