zenoh_keyexpr/keyexpr_tree/iters/intersection.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 Intersection<
32 'a,
33 Children: IChildrenProvider<Node>,
34 Node: UIKeyExprTreeNode<Weight>,
35 Weight,
36> where
37 Children::Assoc: IChildren<Node> + 'a,
38{
39 key: &'a keyexpr,
40 ke_indices: Vec<usize>,
41 iterators: Vec<StackFrame<'a, Children, Node, Weight>>,
42}
43
44impl<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
45 Intersection<'a, Children, Node, Weight>
46where
47 Children::Assoc: IChildren<Node> + 'a,
48{
49 pub(crate) fn new(children: &'a Children::Assoc, key: &'a keyexpr) -> Self {
50 let mut ke_indices = Vec::with_capacity(32);
51 ke_indices.push(0);
52 let mut iterators = Vec::with_capacity(16);
53 iterators.push(StackFrame {
54 iterator: children.children(),
55 start: 0,
56 end: 1,
57 _marker: Default::default(),
58 });
59 Self {
60 key,
61 ke_indices,
62 iterators,
63 }
64 }
65}
66
67impl<
68 'a,
69 Children: IChildrenProvider<Node>,
70 Node: UIKeyExprTreeNode<Weight, Children = Children::Assoc> + 'a,
71 Weight,
72 > Iterator for Intersection<'a, Children, Node, Weight>
73where
74 Children::Assoc: IChildren<Node> + 'a,
75{
76 type Item = &'a Node;
77 fn next(&mut self) -> Option<Self::Item> {
78 loop {
79 let StackFrame {
80 iterator,
81 start,
82 end,
83 _marker,
84 } = self.iterators.last_mut()?;
85 match iterator.next() {
86 Some(node) => {
87 let mut node_matches = false;
88 let new_start = *end;
89 let mut new_end = *end;
90 macro_rules! push {
91 ($index: expr) => {
92 let index = $index;
93 if new_end == new_start || self.ke_indices[new_end - 1] < index {
94 self.ke_indices.push(index);
95 new_end += 1;
96 }
97 };
98 }
99 let chunk = node.chunk();
100 let chunk_is_verbatim = chunk.first_byte() == b'@';
101 if unlikely(chunk.as_bytes() == b"**") {
102 // If the current node is `**`, it is guaranteed to match...
103 node_matches = true;
104 // and may consume any number of chunks from the KE
105 push!(self.ke_indices[*start]);
106 if self.key.len() != self.ke_indices[*start] {
107 if self.key.as_bytes()[self.ke_indices[*start]] != b'@' {
108 for i in self.ke_indices[*start]..self.key.len() {
109 if self.key.as_bytes()[i] == b'/' {
110 push!(i + 1);
111 if self.key.as_bytes()[i + 1] == b'@' {
112 node_matches = false; // ...unless the KE contains a verbatim chunk.
113 break;
114 }
115 }
116 }
117 } else {
118 node_matches = false;
119 }
120 }
121 } else {
122 // The current node is not `**`
123 // For all candidate chunks of the KE
124 for i in *start..*end {
125 // construct that chunk, while checking whether or not it's the last one
126 let kec_start = self.ke_indices[i];
127 if unlikely(kec_start == self.key.len()) {
128 break;
129 }
130 let key = &self.key.as_bytes()[kec_start..];
131 match key.iter().position(|&c| c == b'/') {
132 Some(kec_end) => {
133 // If we aren't in the last chunk
134 let subkey =
135 unsafe { keyexpr::from_slice_unchecked(&key[..kec_end]) };
136 if unlikely(subkey.as_bytes() == b"**") {
137 if !chunk_is_verbatim {
138 // If the query chunk is `**`:
139 // children will have to process it again
140 push!(kec_start);
141 }
142 // and we need to process this chunk as if the `**` wasn't there,
143 // but with the knowledge that the next chunk won't be `**`.
144 let post_key = &key[kec_end + 1..];
145 match post_key.iter().position(|&c| c == b'/') {
146 Some(sec_end) => {
147 let post_key = unsafe {
148 keyexpr::from_slice_unchecked(
149 &post_key[..sec_end],
150 )
151 };
152 if post_key.intersects(chunk) {
153 push!(kec_start + kec_end + sec_end + 2);
154 }
155 }
156 None => {
157 if unsafe {
158 keyexpr::from_slice_unchecked(post_key)
159 }
160 .intersects(chunk)
161 {
162 push!(self.key.len());
163 node_matches = true;
164 }
165 }
166 }
167 } else if chunk.intersects(subkey) {
168 push!(kec_start + kec_end + 1);
169 }
170 }
171 None => {
172 // If it's the last chunk of the query, check whether it's `**`
173 let key = unsafe { keyexpr::from_slice_unchecked(key) };
174 if unlikely(key.as_bytes() == b"**") && !chunk_is_verbatim {
175 // If yes, it automatically matches, and must be reused from now on for iteration.
176 push!(kec_start);
177 node_matches = true;
178 } else if chunk.intersects(key) {
179 // else, if it intersects with the chunk, make sure the children of the node
180 // are searched for `**`
181 push!(self.key.len());
182 node_matches = true;
183 }
184 }
185 }
186 }
187 }
188 // If new progress points have been set
189 if new_end != new_start {
190 // Check if any of them is `**`, as this would mean a match
191 for &i in &self.ke_indices[new_start..new_end] {
192 if &self.key.as_bytes()[i..] == b"**" {
193 node_matches = true;
194 break;
195 }
196 }
197 // Prepare the next children
198 let iterator = unsafe { node.as_node().__children() }.children();
199 self.iterators.push(StackFrame {
200 iterator,
201 start: new_start,
202 end: new_end,
203 _marker: Default::default(),
204 })
205 }
206 // yield the node if a match was found
207 if node_matches {
208 return Some(node.as_node());
209 }
210 }
211 None => {
212 if let Some(StackFrame { start, .. }) = self.iterators.pop() {
213 self.ke_indices.truncate(start);
214 }
215 }
216 }
217 }
218 }
219}
220struct StackFrameMut<'a, Children: IChildrenProvider<Node>, Node: IKeyExprTreeNode<Weight>, Weight>
221where
222 Children::Assoc: IChildren<Node> + 'a,
223 <Children::Assoc as IChildren<Node>>::Node: 'a,
224{
225 iterator: <Children::Assoc as IChildren<Node>>::IterMut<'a>,
226 start: usize,
227 end: usize,
228 _marker: core::marker::PhantomData<Weight>,
229}
230
231pub struct IntersectionMut<
232 'a,
233 Children: IChildrenProvider<Node>,
234 Node: IKeyExprTreeNode<Weight>,
235 Weight,
236> where
237 Children::Assoc: IChildren<Node> + 'a,
238{
239 key: &'a keyexpr,
240 ke_indices: Vec<usize>,
241 iterators: Vec<StackFrameMut<'a, Children, Node, Weight>>,
242}
243
244impl<'a, Children: IChildrenProvider<Node>, Node: IKeyExprTreeNode<Weight>, Weight>
245 IntersectionMut<'a, Children, Node, Weight>
246where
247 Children::Assoc: IChildren<Node> + 'a,
248{
249 pub(crate) fn new(children: &'a mut Children::Assoc, key: &'a keyexpr) -> Self {
250 let mut ke_indices = Vec::with_capacity(32);
251 ke_indices.push(0);
252 let mut iterators = Vec::with_capacity(16);
253 iterators.push(StackFrameMut {
254 iterator: children.children_mut(),
255 start: 0,
256 end: 1,
257 _marker: Default::default(),
258 });
259 Self {
260 key,
261 ke_indices,
262 iterators,
263 }
264 }
265}
266
267impl<
268 'a,
269 Children: IChildrenProvider<Node>,
270 Node: IKeyExprTreeNodeMut<Weight, Children = Children::Assoc> + 'a,
271 Weight,
272 > Iterator for IntersectionMut<'a, Children, Node, Weight>
273where
274 Children::Assoc: IChildren<Node> + 'a,
275{
276 type Item = &'a mut <Children::Assoc as IChildren<Node>>::Node;
277 fn next(&mut self) -> Option<Self::Item> {
278 loop {
279 let StackFrameMut {
280 iterator,
281 start,
282 end,
283 _marker,
284 } = self.iterators.last_mut()?;
285 match iterator.next() {
286 Some(node) => {
287 let mut node_matches = false;
288 let new_start = *end;
289 let mut new_end = *end;
290 macro_rules! push {
291 ($index: expr) => {
292 let index = $index;
293 if new_end == new_start || self.ke_indices[new_end - 1] < index {
294 self.ke_indices.push(index);
295 new_end += 1;
296 }
297 };
298 }
299 let chunk = node.chunk();
300 let chunk_is_verbatim = chunk.first_byte() == b'@';
301 if unlikely(chunk.as_bytes() == b"**") {
302 // If the current node is `**`, it is guaranteed to match...
303 node_matches = true;
304 // and may consume any number of chunks from the KE
305 push!(self.ke_indices[*start]);
306 if self.key.len() != self.ke_indices[*start] {
307 if self.key.as_bytes()[self.ke_indices[*start]] != b'@' {
308 for i in self.ke_indices[*start]..self.key.len() {
309 if self.key.as_bytes()[i] == b'/' {
310 push!(i + 1);
311 if self.key.as_bytes()[i + 1] == b'@' {
312 node_matches = false; // ...unless the KE contains a verbatim chunk.
313 break;
314 }
315 }
316 }
317 } else {
318 node_matches = false;
319 }
320 }
321 } else {
322 // The current node is not `**`
323 // For all candidate chunks of the KE
324 for i in *start..*end {
325 // construct that chunk, while checking whether or not it's the last one
326 let kec_start = self.ke_indices[i];
327 if unlikely(kec_start == self.key.len()) {
328 break;
329 }
330 let key = &self.key.as_bytes()[kec_start..];
331 match key.iter().position(|&c| c == b'/') {
332 Some(kec_end) => {
333 // If we aren't in the last chunk
334 let subkey =
335 unsafe { keyexpr::from_slice_unchecked(&key[..kec_end]) };
336 if unlikely(subkey.as_bytes() == b"**") {
337 if !chunk_is_verbatim {
338 // If the query chunk is `**`:
339 // children will have to process it again
340 push!(kec_start);
341 }
342 // and we need to process this chunk as if the `**` wasn't there,
343 // but with the knowledge that the next chunk won't be `**`.
344 let post_key = &key[kec_end + 1..];
345 match post_key.iter().position(|&c| c == b'/') {
346 Some(sec_end) => {
347 let post_key = unsafe {
348 keyexpr::from_slice_unchecked(
349 &post_key[..sec_end],
350 )
351 };
352 if post_key.intersects(chunk) {
353 push!(kec_start + kec_end + sec_end + 2);
354 }
355 }
356 None => {
357 if unsafe {
358 keyexpr::from_slice_unchecked(post_key)
359 }
360 .intersects(chunk)
361 {
362 push!(self.key.len());
363 node_matches = true;
364 }
365 }
366 }
367 } else if chunk.intersects(subkey) {
368 push!(kec_start + kec_end + 1);
369 }
370 }
371 None => {
372 // If it's the last chunk of the query, check whether it's `**`
373 let key = unsafe { keyexpr::from_slice_unchecked(key) };
374 if unlikely(key.as_bytes() == b"**") && !chunk_is_verbatim {
375 // If yes, it automatically matches, and must be reused from now on for iteration.
376 push!(kec_start);
377 node_matches = true;
378 } else if chunk.intersects(key) {
379 // else, if it intersects with the chunk, make sure the children of the node
380 // are searched for `**`
381 push!(self.key.len());
382 node_matches = true;
383 }
384 }
385 }
386 }
387 }
388 if new_end != new_start {
389 for &i in &self.ke_indices[new_start..new_end] {
390 if &self.key.as_bytes()[i..] == b"**" {
391 node_matches = true;
392 break;
393 }
394 }
395 let iterator = unsafe { &mut *(node.as_node_mut() as *mut Node) }
396 .children_mut()
397 .children_mut();
398 self.iterators.push(StackFrameMut {
399 iterator,
400 start: new_start,
401 end: new_end,
402 _marker: Default::default(),
403 })
404 }
405 if node_matches {
406 return Some(node);
407 }
408 }
409 None => {
410 if let Some(StackFrameMut { start, .. }) = self.iterators.pop() {
411 self.ke_indices.truncate(start);
412 }
413 }
414 }
415 }
416 }
417}