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            && !target.intersects(unsafe { keyexpr::from_str_unchecked(self.suffix) })
120        {
121            bail!("{target} does not intersect with {self}")
122        }
123        let mut results = self.storage.values_storage(|_| None);
124        let results_mut = results.as_mut();
125        debug_assert_eq!(segments.len(), results_mut.len());
126        let found = 'a: {
127            match self.suffix.as_bytes() {
128                [] => do_parse(Some(target), segments, results_mut),
129                [b'/', suffix @ ..] => {
130                    let suffix = unsafe { keyexpr::from_slice_unchecked(suffix) };
131                    for (target, candidate) in target.iter_splits_rtl() {
132                        if suffix.intersects(candidate)
133                            && do_parse(Some(target), segments, results_mut)
134                        {
135                            break 'a true;
136                        }
137                    }
138                    suffix.intersects(target) && do_parse(None, segments, results_mut)
139                }
140                _ => {
141                    unreachable!();
142                }
143            }
144        };
145        if found {
146            Ok(Parsed {
147                format: self,
148                results,
149            })
150        } else {
151            bail!("{target} does not intersect with {self}")
152        }
153    }
154}
155
156fn do_parse<'a>(
157    target: Option<&'a keyexpr>,
158    segments: &[Segment],
159    results: &mut [Option<&'a keyexpr>],
160) -> bool {
161    match (segments, results) {
162        ([], []) => target.map_or(true, keyexpr::is_double_wild),
163        ([segment, segments @ ..], [result, results @ ..]) => {
164            let prefix = segment.prefix();
165            let pattern = segment.pattern();
166            // if target is empty
167            let Some(target) = target else {
168                // this segment only matches if the pattern is `**` and the prefix is empty (since it cannot be `**`)
169                if prefix.is_none() && pattern.is_double_wild() {
170                    *result = None;
171                    // the next segments still have to be checked to respect the same condition
172                    return !segments.iter().zip(results).any(|(segment, result)| {
173                        *result = None;
174                        segment.prefix().is_some() || !segment.pattern().is_double_wild()
175                    });
176                } else {
177                    return false;
178                }
179            };
180            macro_rules! try_intersect {
181                ($pattern: expr, $result: expr, $target: expr, $segments: expr, $results: expr) => {{
182                    let target = $target;
183                    let segments = $segments;
184                    if $pattern.intersects(target)
185                        && do_parse(
186                            target.is_double_wild().then_some(target),
187                            segments,
188                            $results,
189                        )
190                    {
191                        *$result = Some(target);
192                        return true;
193                    }
194                    for (candidate, target) in target.iter_splits_rtl() {
195                        if $pattern.intersects(candidate)
196                            && do_parse(Some(target), segments, $results)
197                        {
198                            *result = Some(candidate);
199                            return true;
200                        }
201                    }
202                    if $pattern.is_double_wild() && do_parse(Some(target), segments, $results) {
203                        *$result = None;
204                        return true;
205                    }
206                }};
207            }
208            //if the prefix can be compressed to empty,
209            if prefix.is_none() {
210                try_intersect!(pattern, result, target, segments, results);
211            }
212            // iterate through as many splits as `prefix` could possibly consume.
213            for (candidate, target) in target.iter_splits_ltr().take(match prefix {
214                None => 1,
215                Some(prefix) => (prefix.bytes().filter(|&c| c == b'/').count() + 1) * 3,
216            }) {
217                if prefix.map_or(candidate.is_double_wild(), |prefix| {
218                    prefix.intersects(candidate)
219                }) {
220                    try_intersect!(pattern, result, target, segments, results);
221                }
222            }
223            pattern.is_double_wild()
224                && prefix.is_some_and(|prefix| prefix.intersects(target))
225                && do_parse(None, segments, results)
226        }
227        _ => unreachable!(),
228    }
229}
230
231#[test]
232fn parsing() {
233    use core::convert::TryFrom;
234
235    use crate::key_expr::OwnedKeyExpr;
236    for a_spec in ["${a:*}", "a/${a:*}"] {
237        for b_spec in ["b/${b:**}", "${b:**}"] {
238            let specs = [a_spec, b_spec, "c"];
239            for spec in [2, 3] {
240                let spec = specs[..spec].join("/");
241                let format: KeFormat<[Segment; 2]> = KeFormat::noalloc_new(&spec).unwrap();
242                let mut formatter = format.formatter();
243                for a_val in ["hi"] {
244                    formatter.set("a", a_val).unwrap();
245                    for b_val in ["hello", "hello/there", ""] {
246                        formatter.set("b", b_val).unwrap();
247                        let ke = OwnedKeyExpr::try_from(&formatter).unwrap();
248                        let parsed = format.parse(&ke).unwrap();
249                        assert_eq!(parsed.get("a").unwrap(), a_val);
250                        assert_eq!(parsed.get("b").unwrap(), b_val);
251                    }
252                }
253            }
254        }
255    }
256    KeFormat::new("**/${a:**}/${b:**}/**").unwrap_err();
257    let format = KeFormat::new("${a:**}/${b:**}").unwrap();
258    assert_eq!(
259        format
260            .parse(keyexpr::new("a/b/c").unwrap())
261            .unwrap()
262            .get("a")
263            .unwrap(),
264        "a/b/c"
265    );
266    assert_eq!(
267        format
268            .parse(keyexpr::new("**").unwrap())
269            .unwrap()
270            .get("a")
271            .unwrap(),
272        "**"
273    );
274    assert_eq!(
275        format
276            .parse(keyexpr::new("**").unwrap())
277            .unwrap()
278            .get("b")
279            .unwrap(),
280        "**"
281    );
282    let format = KeFormat::new("hi/${a:there}/${b:**}").unwrap();
283    assert_eq!(
284        format
285            .parse(keyexpr::new("hi/**").unwrap())
286            .unwrap()
287            .get("a")
288            .unwrap(),
289        "**"
290    );
291    assert_eq!(
292        format
293            .parse(keyexpr::new("hi/**").unwrap())
294            .unwrap()
295            .get("b")
296            .unwrap(),
297        "**"
298    );
299    let format = KeFormat::new("hi/${a:there}/@/${b:**}").unwrap();
300    assert_eq!(
301        format
302            .parse(keyexpr::new("hi/**/@").unwrap())
303            .unwrap()
304            .get("a")
305            .unwrap(),
306        "**"
307    );
308    assert_eq!(
309        format
310            .parse(keyexpr::new("hi/**/@").unwrap())
311            .unwrap()
312            .get("b")
313            .unwrap(),
314        ""
315    );
316}
zenoh_keyexpr/key_expr/format/parsing.rs

zenoh_keyexpr/key_expr/format/
parsing.rs
