zenoh_keyexpr/key_expr/format/
parsing.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 zenoh_result::{bail, ZResult};
16
17use super::{IKeFormatStorage, KeFormat, Segment};
18use crate::key_expr::keyexpr;
19
20pub struct Parsed<'s, Storage: IKeFormatStorage<'s>> {
21    format: &'s KeFormat<'s, Storage>,
22    results: Storage::ValuesStorage<Option<&'s keyexpr>>,
23}
24
25impl<'s, Storage: IKeFormatStorage<'s>> Parsed<'s, Storage> {
26    /// Access the `id` element.
27    ///
28    /// The returned string is guaranteed to either be an empty string or a valid key expression.
29    ///
30    /// # Errors
31    /// If `id` is not part of `self`'s specs.
32    pub fn get(&self, id: &str) -> ZResult<&'s str> {
33        let Some(i) = self
34            .format
35            .storage
36            .segments()
37            .iter()
38            .position(|s| s.spec.id() == id)
39        else {
40            bail!("{} has no {id} field", self.format)
41        };
42        Ok(self.results.as_ref()[i].map_or("", keyexpr::as_str))
43    }
44    /// The raw values for each spec, in left-to-right order.
45    pub fn values(&self) -> &[Option<&'s keyexpr>] {
46        self.results.as_ref()
47    }
48    /// Iterates over id-value pairs.
49    pub fn iter(&'s self) -> Iter<'s, Storage> {
50        self.into_iter()
51    }
52}
53
54impl<'s, Storage: IKeFormatStorage<'s>> IntoIterator for &'s Parsed<'s, Storage> {
55    type Item = <Self::IntoIter as Iterator>::Item;
56    type IntoIter = Iter<'s, Storage>;
57    fn into_iter(self) -> Self::IntoIter {
58        Iter {
59            parsed: self,
60            start: 0,
61            end: self.format.storage.segments().len(),
62        }
63    }
64}
65pub struct Iter<'s, Storage: IKeFormatStorage<'s>> {
66    parsed: &'s Parsed<'s, Storage>,
67    start: usize,
68    end: usize,
69}
70impl<'s, Storage: IKeFormatStorage<'s>> Iterator for Iter<'s, Storage> {
71    type Item = (&'s str, Option<&'s keyexpr>);
72    fn next(&mut self) -> Option<Self::Item> {
73        if self.start < self.end {
74            let id = self.parsed.format.storage.segments()[self.start].spec.id();
75            let ke = self.parsed.results.as_ref()[self.start];
76            self.start += 1;
77            Some((id, ke))
78        } else {
79            None
80        }
81    }
82    fn nth(&mut self, n: usize) -> Option<Self::Item> {
83        self.start += n;
84        self.next()
85    }
86    fn size_hint(&self) -> (usize, Option<usize>) {
87        let result = self.end - self.start;
88        (result, Some(result))
89    }
90}
91impl<'s, Storage: IKeFormatStorage<'s>> ExactSizeIterator for Iter<'s, Storage> {
92    fn len(&self) -> usize {
93        self.end - self.start
94    }
95}
96impl<'s, Storage: IKeFormatStorage<'s>> DoubleEndedIterator for Iter<'s, Storage> {
97    fn next_back(&mut self) -> Option<Self::Item> {
98        if self.start < self.end {
99            self.end -= 1;
100            let id = self.parsed.format.storage.segments()[self.end].spec.id();
101            let ke = self.parsed.results.as_ref()[self.end];
102            Some((id, ke))
103        } else {
104            None
105        }
106    }
107}
108
109impl<'s, Storage: IKeFormatStorage<'s> + 's> KeFormat<'s, Storage> {
110    /// Parses `target` according to `self`. The returned [`Parsed`] object can be used to extract the values of the fields in `self` from `target`.
111    ///
112    /// Parsing is greedy and done left-to-right. Please refer to [`KeFormat`]'s documentation for more details.
113    ///
114    /// # Errors
115    /// If `target` does not intersect with `self`, an error is returned.
116    pub fn parse(&'s self, target: &'s keyexpr) -> ZResult<Parsed<'s, Storage>> {
117        let segments = self.storage.segments();
118        if segments.is_empty()
119            // SAFETY: upheld by the surrounding invariants and prior validation.
120            && !target.intersects(unsafe { keyexpr::from_str_unchecked(self.suffix) })
121        {
122            bail!("{target} does not intersect with {self}")
123        }
124        let mut results = self.storage.values_storage(|_| None);
125        let results_mut = results.as_mut();
126        debug_assert_eq!(segments.len(), results_mut.len());
127        let found = 'a: {
128            match self.suffix.as_bytes() {
129                [] => do_parse(Some(target), segments, results_mut),
130                [b'/', suffix @ ..] => {
131                    // SAFETY: upheld by the surrounding invariants and prior validation.
132                    let suffix = unsafe { keyexpr::from_slice_unchecked(suffix) };
133                    for (target, candidate) in target.iter_splits_rtl() {
134                        if suffix.intersects(candidate)
135                            && do_parse(Some(target), segments, results_mut)
136                        {
137                            break 'a true;
138                        }
139                    }
140                    suffix.intersects(target) && do_parse(None, segments, results_mut)
141                }
142                _ => {
143                    unreachable!();
144                }
145            }
146        };
147        if found {
148            Ok(Parsed {
149                format: self,
150                results,
151            })
152        } else {
153            bail!("{target} does not intersect with {self}")
154        }
155    }
156}
157
158fn do_parse<'a>(
159    target: Option<&'a keyexpr>,
160    segments: &[Segment],
161    results: &mut [Option<&'a keyexpr>],
162) -> bool {
163    match (segments, results) {
164        ([], []) => target.map_or(true, keyexpr::is_double_wild),
165        ([segment, segments @ ..], [result, results @ ..]) => {
166            let prefix = segment.prefix();
167            let pattern = segment.pattern();
168            // if target is empty
169            let Some(target) = target else {
170                // this segment only matches if the pattern is `**` and the prefix is empty (since it cannot be `**`)
171                if prefix.is_none() && pattern.is_double_wild() {
172                    *result = None;
173                    // the next segments still have to be checked to respect the same condition
174                    return !segments.iter().zip(results).any(|(segment, result)| {
175                        *result = None;
176                        segment.prefix().is_some() || !segment.pattern().is_double_wild()
177                    });
178                } else {
179                    return false;
180                }
181            };
182            macro_rules! try_intersect {
183                ($pattern: expr, $result: expr, $target: expr, $segments: expr, $results: expr) => {{
184                    let target = $target;
185                    let segments = $segments;
186                    if $pattern.intersects(target)
187                        && do_parse(
188                            target.is_double_wild().then_some(target),
189                            segments,
190                            $results,
191                        )
192                    {
193                        *$result = Some(target);
194                        return true;
195                    }
196                    for (candidate, target) in target.iter_splits_rtl() {
197                        if $pattern.intersects(candidate)
198                            && do_parse(Some(target), segments, $results)
199                        {
200                            *result = Some(candidate);
201                            return true;
202                        }
203                    }
204                    if $pattern.is_double_wild() && do_parse(Some(target), segments, $results) {
205                        *$result = None;
206                        return true;
207                    }
208                }};
209            }
210            //if the prefix can be compressed to empty,
211            if prefix.is_none() {
212                try_intersect!(pattern, result, target, segments, results);
213            }
214            // iterate through as many splits as `prefix` could possibly consume.
215            for (candidate, target) in target.iter_splits_ltr().take(match prefix {
216                None => 1,
217                Some(prefix) => (prefix.bytes().filter(|&c| c == b'/').count() + 1) * 3,
218            }) {
219                if prefix.map_or(candidate.is_double_wild(), |prefix| {
220                    prefix.intersects(candidate)
221                }) {
222                    try_intersect!(pattern, result, target, segments, results);
223                }
224            }
225            pattern.is_double_wild()
226                && prefix.is_some_and(|prefix| prefix.intersects(target))
227                && do_parse(None, segments, results)
228        }
229        _ => unreachable!(),
230    }
231}
232
233#[test]
234fn parsing() {
235    use core::convert::TryFrom;
236
237    use crate::key_expr::OwnedKeyExpr;
238    for a_spec in ["${a:*}", "a/${a:*}"] {
239        for b_spec in ["b/${b:**}", "${b:**}"] {
240            let specs = [a_spec, b_spec, "c"];
241            for spec in [2, 3] {
242                let spec = specs[..spec].join("/");
243                let format: KeFormat<[Segment; 2]> = KeFormat::noalloc_new(&spec).unwrap();
244                let mut formatter = format.formatter();
245                for a_val in ["hi"] {
246                    formatter.set("a", a_val).unwrap();
247                    for b_val in ["hello", "hello/there", ""] {
248                        formatter.set("b", b_val).unwrap();
249                        let ke = OwnedKeyExpr::try_from(&formatter).unwrap();
250                        let parsed = format.parse(&ke).unwrap();
251                        assert_eq!(parsed.get("a").unwrap(), a_val);
252                        assert_eq!(parsed.get("b").unwrap(), b_val);
253                    }
254                }
255            }
256        }
257    }
258    KeFormat::new("**/${a:**}/${b:**}/**").unwrap_err();
259    let format = KeFormat::new("${a:**}/${b:**}").unwrap();
260    assert_eq!(
261        format
262            .parse(keyexpr::new("a/b/c").unwrap())
263            .unwrap()
264            .get("a")
265            .unwrap(),
266        "a/b/c"
267    );
268    assert_eq!(
269        format
270            .parse(keyexpr::new("**").unwrap())
271            .unwrap()
272            .get("a")
273            .unwrap(),
274        "**"
275    );
276    assert_eq!(
277        format
278            .parse(keyexpr::new("**").unwrap())
279            .unwrap()
280            .get("b")
281            .unwrap(),
282        "**"
283    );
284    let format = KeFormat::new("hi/${a:there}/${b:**}").unwrap();
285    assert_eq!(
286        format
287            .parse(keyexpr::new("hi/**").unwrap())
288            .unwrap()
289            .get("a")
290            .unwrap(),
291        "**"
292    );
293    assert_eq!(
294        format
295            .parse(keyexpr::new("hi/**").unwrap())
296            .unwrap()
297            .get("b")
298            .unwrap(),
299        "**"
300    );
301    let format = KeFormat::new("hi/${a:there}/@/${b:**}").unwrap();
302    assert_eq!(
303        format
304            .parse(keyexpr::new("hi/**/@").unwrap())
305            .unwrap()
306            .get("a")
307            .unwrap(),
308        "**"
309    );
310    assert_eq!(
311        format
312            .parse(keyexpr::new("hi/**/@").unwrap())
313            .unwrap()
314            .get("b")
315            .unwrap(),
316        ""
317    );
318}
zenoh_keyexpr/key_expr/format/parsing.rs

zenoh_keyexpr/key_expr/format/
parsing.rs
