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

zenoh_keyexpr/keyexpr_tree/iters/
inclusion.rs
