zenoh_keyexpr/key_expr/
borrowed.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
15#[cfg(feature = "internal")]
16use alloc::vec::Vec;
17use alloc::{
18    borrow::{Borrow, ToOwned},
19    format,
20    string::String,
21};
22use core::{
23    convert::{TryFrom, TryInto},
24    fmt,
25    ops::{Deref, Div},
26};
27
28use zenoh_result::{anyhow, bail, zerror, Error as ZError, ZResult};
29
30use super::{canon::Canonize, OwnedKeyExpr, OwnedNonWildKeyExpr};
31
32/// A [`str`] newtype that is statically known to be a valid key expression.
33///
34/// The exact key expression specification can be found [here](https://github.com/eclipse-zenoh/roadmap/blob/main/rfcs/ALL/Key%20Expressions.md). Here are the major lines:
35/// * Key expressions are conceptually a `/`-separated list of UTF-8 string typed chunks. These chunks are not allowed to be empty.
36/// * Key expressions must be valid UTF-8 strings.
37///   Be aware that Zenoh does not perform UTF normalization for you, so get familiar with that concept if your key expression contains glyphs that may have several unicode representation, such as accented characters.
38/// * Key expressions may never start or end with `'/'`, nor contain `"//"` or any of the following characters: `#$?`
39/// * Key expression must be in canon-form (this ensure that key expressions representing the same set are always the same string).
40///   Note that safe constructors will perform canonization for you if this can be done without extraneous allocations.
41///
42/// Since Key Expressions define sets of keys, you may want to be aware of the hierarchy of [relations](keyexpr::relation_to) between such sets:
43/// * Trivially, two sets can have no elements in common: `a/**` and `b/**` for example define two disjoint sets of keys.
44/// * Two sets [intersect](keyexpr::intersects()) if they have at least one element in common. `a/*` intersects `*/a` on `a/a` for example.
45/// * One set A [includes](keyexpr::includes()) the other set B if all of B's elements are in A: `a/*/**` includes `a/b/**`
46/// * Two sets A and B are equal if all A includes B and B includes A. The Key Expression language is designed so that string equality is equivalent to set equality.
47#[allow(non_camel_case_types)]
48#[repr(transparent)]
49#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
50pub struct keyexpr(str);
51
52impl keyexpr {
53    /// Equivalent to `<&keyexpr as TryFrom>::try_from(t)`.
54    ///
55    /// Will return an Err if `t` isn't a valid key expression.
56    /// Note that to be considered a valid key expression, a string MUST be canon.
57    ///
58    /// [`keyexpr::autocanonize`] is an alternative constructor that will canonize the passed expression before constructing it.
59    pub fn new<'a, T, E>(t: &'a T) -> Result<&'a Self, E>
60    where
61        &'a Self: TryFrom<&'a T, Error = E>,
62        T: ?Sized,
63    {
64        t.try_into()
65    }
66
67    /// Canonizes the passed value before returning it as a `&keyexpr`.
68    ///
69    /// Will return Err if the passed value isn't a valid key expression despite canonization.
70    ///
71    /// Note that this function does not allocate, and will instead mutate the passed value in place during canonization.
72    pub fn autocanonize<'a, T, E>(t: &'a mut T) -> Result<&'a Self, E>
73    where
74        &'a Self: TryFrom<&'a T, Error = E>,
75        T: Canonize + ?Sized,
76    {
77        t.canonize();
78        Self::new(t)
79    }
80
81    /// Returns `true` if the `keyexpr`s intersect, i.e. there exists at least one key which is contained in both of the sets defined by `self` and `other`.
82    pub fn intersects(&self, other: &Self) -> bool {
83        use super::intersect::Intersector;
84        super::intersect::DEFAULT_INTERSECTOR.intersect(self, other)
85    }
86
87    /// Returns `true` if `self` includes `other`, i.e. the set defined by `self` contains every key belonging to the set defined by `other`.
88    pub fn includes(&self, other: &Self) -> bool {
89        use super::include::Includer;
90        super::include::DEFAULT_INCLUDER.includes(self, other)
91    }
92
93    /// Returns the relation between `self` and `other` from `self`'s point of view ([`SetIntersectionLevel::Includes`] signifies that `self` includes `other`).
94    ///
95    /// Note that this is slower than [`keyexpr::intersects`] and [`keyexpr::includes`], so you should favor these methods for most applications.
96    #[cfg(feature = "unstable")]
97    pub fn relation_to(&self, other: &Self) -> SetIntersectionLevel {
98        use SetIntersectionLevel::*;
99        if self.intersects(other) {
100            if self == other {
101                Equals
102            } else if self.includes(other) {
103                Includes
104            } else {
105                Intersects
106            }
107        } else {
108            Disjoint
109        }
110    }
111
112    /// Joins both sides, inserting a `/` in between them.
113    ///
114    /// This should be your preferred method when concatenating path segments.
115    ///
116    /// This is notably useful for workspaces:
117    /// ```rust
118    /// # use core::convert::TryFrom;
119    /// # use zenoh_keyexpr::OwnedKeyExpr;
120    /// # let get_workspace = || OwnedKeyExpr::try_from("some/workspace").unwrap();
121    /// let workspace: OwnedKeyExpr = get_workspace();
122    /// let topic = workspace.join("some/topic").unwrap();
123    /// ```
124    ///
125    /// If `other` is of type `&keyexpr`, you may use `self / other` instead, as the joining becomes infallible.
126    pub fn join<S: AsRef<str> + ?Sized>(&self, other: &S) -> ZResult<OwnedKeyExpr> {
127        OwnedKeyExpr::autocanonize(format!("{}/{}", self, other.as_ref()))
128    }
129
130    /// Returns `true` if `self` contains any wildcard character (`**` or `$*`).
131    #[cfg(feature = "internal")]
132    #[doc(hidden)]
133    pub fn is_wild(&self) -> bool {
134        self.is_wild_impl()
135    }
136    pub(crate) fn is_wild_impl(&self) -> bool {
137        self.0.contains(super::SINGLE_WILD as char)
138    }
139
140    pub(crate) const fn is_double_wild(&self) -> bool {
141        let bytes = self.0.as_bytes();
142        bytes.len() == 2 && bytes[0] == b'*'
143    }
144
145    /// Returns the longest prefix of `self` that doesn't contain any wildcard character (`**` or `$*`).
146    ///
147    /// NOTE: this operation can typically be used in a backend implementation, at creation of a Storage to get the keys prefix,
148    /// and then in `zenoh_backend_traits::Storage::on_sample()` this prefix has to be stripped from all received
149    /// `Sample::key_expr` to retrieve the corresponding key.
150    ///
151    /// # Examples:
152    /// ```
153    /// # use zenoh_keyexpr::keyexpr;
154    /// assert_eq!(
155    ///     Some(keyexpr::new("demo/example").unwrap()),
156    ///     keyexpr::new("demo/example/**").unwrap().get_nonwild_prefix());
157    /// assert_eq!(
158    ///     Some(keyexpr::new("demo").unwrap()),
159    ///     keyexpr::new("demo/**/test/**").unwrap().get_nonwild_prefix());
160    /// assert_eq!(
161    ///     Some(keyexpr::new("demo/example/test").unwrap()),
162    ///     keyexpr::new("demo/example/test").unwrap().get_nonwild_prefix());
163    /// assert_eq!(
164    ///     Some(keyexpr::new("demo").unwrap()),
165    ///     keyexpr::new("demo/ex$*/**").unwrap().get_nonwild_prefix());
166    /// assert_eq!(
167    ///     None,
168    ///     keyexpr::new("**").unwrap().get_nonwild_prefix());
169    /// assert_eq!(
170    ///     None,
171    ///     keyexpr::new("dem$*").unwrap().get_nonwild_prefix());
172    /// ```
173    #[cfg(feature = "internal")]
174    #[doc(hidden)]
175    pub fn get_nonwild_prefix(&self) -> Option<&keyexpr> {
176        match self.0.find('*') {
177            Some(i) => match self.0[..i].rfind('/') {
178                Some(j) => unsafe { Some(keyexpr::from_str_unchecked(&self.0[..j])) },
179                None => None, // wildcard in the first segment => no invariant prefix
180            },
181            None => Some(self), // no wildcard => return self
182        }
183    }
184
185    /// Remove the specified `prefix` from `self`.
186    /// The result is a list of `keyexpr`, since there might be several ways for the prefix to match the beginning of the `self` key expression.
187    /// For instance, if `self` is `"a/**/c/*" and `prefix` is `a/b/c` then:
188    ///   - the `prefix` matches `"a/**/c"` leading to a result of `"*"` when stripped from `self`
189    ///   - the `prefix` matches `"a/**"` leading to a result of `"**/c/*"` when stripped from `self`
190    ///
191    /// So the result is `["*", "**/c/*"]`.
192    /// If `prefix` cannot match the beginning of `self`, an empty list is reuturned.
193    ///
194    /// See below more examples.
195    ///
196    /// NOTE: this operation can typically used in a backend implementation, within the `zenoh_backend_traits::Storage::on_query()` implementation,
197    /// to transform the received `Query::selector()`'s `key_expr` into a list of key selectors
198    /// that will match all the relevant stored keys (that correspond to keys stripped from the prefix).
199    ///
200    /// # Examples:
201    /// ```
202    /// # use core::convert::{TryFrom, TryInto};
203    /// # use zenoh_keyexpr::keyexpr;
204    /// assert_eq!(
205    ///     ["abc"],
206    ///     keyexpr::new("demo/example/test/abc").unwrap().strip_prefix(keyexpr::new("demo/example/test").unwrap()).as_slice()
207    /// );
208    /// assert_eq!(
209    ///     ["**"],
210    ///     keyexpr::new("demo/example/test/**").unwrap().strip_prefix(keyexpr::new("demo/example/test").unwrap()).as_slice()
211    /// );
212    /// assert_eq!(
213    ///     ["**"],
214    ///     keyexpr::new("demo/example/**").unwrap().strip_prefix(keyexpr::new("demo/example/test").unwrap()).as_slice()
215    /// );
216    /// assert_eq!(
217    ///     ["**"],
218    ///     keyexpr::new("**").unwrap().strip_prefix(keyexpr::new("demo/example/test").unwrap()).as_slice()
219    /// );
220    /// assert_eq!(
221    ///     ["**/xyz"],
222    ///     keyexpr::new("demo/**/xyz").unwrap().strip_prefix(keyexpr::new("demo/example/test").unwrap()).as_slice()
223    /// );
224    /// assert_eq!(
225    ///     ["**"],
226    ///     keyexpr::new("demo/**/test/**").unwrap().strip_prefix(keyexpr::new("demo/example/test").unwrap()).as_slice()
227    /// );
228    /// assert_eq!(
229    ///     ["xyz", "**/ex$*/*/xyz"],
230    ///     keyexpr::new("demo/**/ex$*/*/xyz").unwrap().strip_prefix(keyexpr::new("demo/example/test").unwrap()).as_slice()
231    /// );
232    /// assert_eq!(
233    ///     ["*", "**/test/*"],
234    ///     keyexpr::new("demo/**/test/*").unwrap().strip_prefix(keyexpr::new("demo/example/test").unwrap()).as_slice()
235    /// );
236    /// assert!(
237    ///     keyexpr::new("demo/example/test/**").unwrap().strip_prefix(keyexpr::new("not/a/prefix").unwrap()).is_empty()
238    /// );
239    /// ```
240    #[cfg(feature = "internal")]
241    #[doc(hidden)]
242    pub fn strip_prefix(&self, prefix: &Self) -> Vec<&keyexpr> {
243        let mut result = alloc::vec![];
244        'chunks: for i in (0..=self.len()).rev() {
245            if if i == self.len() {
246                self.ends_with("**")
247            } else {
248                self.as_bytes()[i] == b'/'
249            } {
250                let sub_part = keyexpr::new(&self[..i]).unwrap();
251                if sub_part.intersects(prefix) {
252                    // if sub_part ends with "**", keep those in remaining part
253                    let remaining = if sub_part.ends_with("**") {
254                        &self[i - 2..]
255                    } else {
256                        &self[i + 1..]
257                    };
258                    let remaining: &keyexpr = if remaining.is_empty() {
259                        continue 'chunks;
260                    } else {
261                        remaining
262                    }
263                    .try_into()
264                    .unwrap();
265                    // if remaining is "**" return only this since it covers all
266                    if remaining.as_bytes() == b"**" {
267                        result.clear();
268                        result.push(unsafe { keyexpr::from_str_unchecked(remaining) });
269                        return result;
270                    }
271                    for i in (0..(result.len())).rev() {
272                        if result[i].includes(remaining) {
273                            continue 'chunks;
274                        }
275                        if remaining.includes(result[i]) {
276                            result.swap_remove(i);
277                        }
278                    }
279                    result.push(remaining);
280                }
281            }
282        }
283        result
284    }
285
286    /// Remove the specified namespace `prefix` from `self`.
287    ///
288    /// This method works essentially like [`keyexpr::strip_prefix()`], but returns only the longest possible suffix.
289    /// Prefix can not contain '*' character.
290    #[cfg(feature = "internal")]
291    #[doc(hidden)]
292    pub fn strip_nonwild_prefix(&self, prefix: &nonwild_keyexpr) -> Option<&keyexpr> {
293        fn is_chunk_matching(target: &[u8], prefix: &[u8]) -> bool {
294            let mut target_idx: usize = 0;
295            let mut prefix_idx: usize = 0;
296            let mut target_prev: u8 = b'/';
297            if prefix.first() == Some(&b'@') && target.first() != Some(&b'@') {
298                // verbatim chunk can only be matched by verbatim chunk
299                return false;
300            }
301
302            while target_idx < target.len() && prefix_idx < prefix.len() {
303                if target[target_idx] == b'*' {
304                    if target_prev == b'*' || target_idx + 1 == target.len() {
305                        // either a ** wild chunk or a single * chunk at the end of the string - this matches anything
306                        return true;
307                    } else if target_prev == b'$' {
308                        for i in prefix_idx..prefix.len() - 1 {
309                            if is_chunk_matching(&target[target_idx + 1..], &prefix[i..]) {
310                                return true;
311                            }
312                        }
313                    }
314                } else if target[target_idx] == prefix[prefix_idx] {
315                    prefix_idx += 1;
316                } else if target[target_idx] != b'$' {
317                    // non-special character, which do not match the one in prefix
318                    return false;
319                }
320                target_prev = target[target_idx];
321                target_idx += 1;
322            }
323            if prefix_idx != prefix.len() {
324                // prefix was not matched entirely
325                return false;
326            }
327            target_idx == target.len()
328                || (target_idx + 2 == target.len() && target[target_idx] == b'$')
329        }
330
331        fn strip_nonwild_prefix_inner<'a>(
332            target_bytes: &'a [u8],
333            prefix_bytes: &[u8],
334        ) -> Option<&'a keyexpr> {
335            let mut target_idx = 0;
336            let mut prefix_idx = 0;
337
338            while target_idx < target_bytes.len() && prefix_idx < prefix_bytes.len() {
339                let target_end = target_idx
340                    + target_bytes[target_idx..]
341                        .iter()
342                        .position(|&i| i == b'/')
343                        .unwrap_or(target_bytes.len() - target_idx);
344                let prefix_end = prefix_idx
345                    + prefix_bytes[prefix_idx..]
346                        .iter()
347                        .position(|&i| i == b'/')
348                        .unwrap_or(prefix_bytes.len() - prefix_idx);
349                let target_chunk = &target_bytes[target_idx..target_end];
350                if target_chunk.len() == 2 && target_chunk[0] == b'*' {
351                    let remaining_prefix = &prefix_bytes[prefix_idx..];
352                    return match remaining_prefix.iter().position(|&x| x == b'@') {
353                        Some(mut p) => {
354                            if target_end + 1 >= target_bytes.len() {
355                                // "**" is the last chunk, and it is not allowed to match @verbatim chunks, so we stop here
356                                return None;
357                            } else {
358                                loop {
359                                    // try to use "**" to match as many non-verbatim chunks as possible
360                                    if let Some(ke) = strip_nonwild_prefix_inner(
361                                        &target_bytes[(target_end + 1)..],
362                                        &remaining_prefix[p..],
363                                    ) {
364                                        return Some(ke);
365                                    } else if p == 0 {
366                                        // "**" is not allowed to match @verbatim chunks
367                                        return None;
368                                    } else {
369                                        // search for the beginning of the next chunk from the end
370                                        p -= 2;
371                                        while p > 0 && remaining_prefix[p - 1] != b'/' {
372                                            p -= 1;
373                                        }
374                                    }
375                                }
376                            }
377                        }
378                        None => unsafe {
379                            // "**" can match all remaining non-verbatim chunks
380                            Some(keyexpr::from_str_unchecked(core::str::from_utf8_unchecked(
381                                &target_bytes[target_idx..],
382                            )))
383                        },
384                    };
385                }
386                if target_end == target_bytes.len() {
387                    // target contains no more chunks than prefix and the last one is non double-wild - so it can not match
388                    return None;
389                }
390                let prefix_chunk = &prefix_bytes[prefix_idx..prefix_end];
391                if !is_chunk_matching(target_chunk, prefix_chunk) {
392                    return None;
393                }
394                if prefix_end == prefix_bytes.len() {
395                    // Safety: every chunk of keyexpr is also a valid keyexpr
396                    return unsafe {
397                        Some(keyexpr::from_str_unchecked(core::str::from_utf8_unchecked(
398                            &target_bytes[(target_end + 1)..],
399                        )))
400                    };
401                }
402                target_idx = target_end + 1;
403                prefix_idx = prefix_end + 1;
404            }
405            None
406        }
407
408        let target_bytes = self.0.as_bytes();
409        let prefix_bytes = prefix.0.as_bytes();
410
411        strip_nonwild_prefix_inner(target_bytes, prefix_bytes)
412    }
413
414    pub const fn as_str(&self) -> &str {
415        &self.0
416    }
417
418    /// # Safety
419    /// This constructs a [`keyexpr`] without ensuring that it is a valid key-expression.
420    ///
421    /// Much like [`core::str::from_utf8_unchecked`], this is memory-safe, but calling this without maintaining
422    /// [`keyexpr`]'s invariants yourself may lead to unexpected behaviors, the Zenoh network dropping your messages.
423    pub const unsafe fn from_str_unchecked(s: &str) -> &Self {
424        core::mem::transmute(s)
425    }
426
427    /// # Safety
428    /// This constructs a [`keyexpr`] without ensuring that it is a valid key-expression.
429    ///
430    /// Much like [`core::str::from_utf8_unchecked`], this is memory-safe, but calling this without maintaining
431    /// [`keyexpr`]'s invariants yourself may lead to unexpected behaviors, the Zenoh network dropping your messages.
432    pub unsafe fn from_slice_unchecked(s: &[u8]) -> &Self {
433        core::mem::transmute(s)
434    }
435
436    #[cfg(feature = "internal")]
437    #[doc(hidden)]
438    pub const fn chunks(&self) -> Chunks<'_> {
439        self.chunks_impl()
440    }
441    pub(crate) const fn chunks_impl(&self) -> Chunks<'_> {
442        Chunks {
443            inner: self.as_str(),
444        }
445    }
446    pub(crate) fn next_delimiter(&self, i: usize) -> Option<usize> {
447        self.as_str()
448            .get(i + 1..)
449            .and_then(|s| s.find('/').map(|j| i + 1 + j))
450    }
451    pub(crate) fn previous_delimiter(&self, i: usize) -> Option<usize> {
452        self.as_str().get(..i).and_then(|s| s.rfind('/'))
453    }
454    pub(crate) fn first_byte(&self) -> u8 {
455        unsafe { *self.as_bytes().get_unchecked(0) }
456    }
457    pub(crate) fn iter_splits_ltr(&self) -> SplitsLeftToRight<'_> {
458        SplitsLeftToRight {
459            inner: self,
460            index: 0,
461        }
462    }
463    pub(crate) fn iter_splits_rtl(&self) -> SplitsRightToLeft<'_> {
464        SplitsRightToLeft {
465            inner: self,
466            index: self.len(),
467        }
468    }
469}
470#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
471pub(crate) struct SplitsLeftToRight<'a> {
472    inner: &'a keyexpr,
473    index: usize,
474}
475impl<'a> SplitsLeftToRight<'a> {
476    fn right(&self) -> &'a str {
477        &self.inner[self.index + ((self.index != 0) as usize)..]
478    }
479    fn left(&self, followed_by_double: bool) -> &'a str {
480        &self.inner[..(self.index + ((self.index != 0) as usize + 2) * followed_by_double as usize)]
481    }
482}
483impl<'a> Iterator for SplitsLeftToRight<'a> {
484    type Item = (&'a keyexpr, &'a keyexpr);
485    fn next(&mut self) -> Option<Self::Item> {
486        match self.index < self.inner.len() {
487            false => None,
488            true => {
489                let right = self.right();
490                let double_wild = right.starts_with("**");
491                let left = self.left(double_wild);
492                self.index = if left.is_empty() {
493                    self.inner.next_delimiter(0).unwrap_or(self.inner.len())
494                } else {
495                    self.inner
496                        .next_delimiter(left.len())
497                        .unwrap_or(self.inner.len() + (left.len() == self.inner.len()) as usize)
498                };
499                if left.is_empty() {
500                    self.next()
501                } else {
502                    // SAFETY: because any keyexpr split at `/` becomes 2 valid keyexprs by design, it's safe to assume the constraint is valid once both sides have been validated to not be empty.
503                    (!right.is_empty()).then(|| unsafe {
504                        (
505                            keyexpr::from_str_unchecked(left),
506                            keyexpr::from_str_unchecked(right),
507                        )
508                    })
509                }
510            }
511        }
512    }
513}
514#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
515pub(crate) struct SplitsRightToLeft<'a> {
516    inner: &'a keyexpr,
517    index: usize,
518}
519impl<'a> SplitsRightToLeft<'a> {
520    fn right(&self, followed_by_double: bool) -> &'a str {
521        &self.inner[(self.index
522            - ((self.index != self.inner.len()) as usize + 2) * followed_by_double as usize)..]
523    }
524    fn left(&self) -> &'a str {
525        &self.inner[..(self.index - ((self.index != self.inner.len()) as usize))]
526    }
527}
528impl<'a> Iterator for SplitsRightToLeft<'a> {
529    type Item = (&'a keyexpr, &'a keyexpr);
530    fn next(&mut self) -> Option<Self::Item> {
531        match self.index {
532            0 => None,
533            _ => {
534                let left = self.left();
535                let double_wild = left.ends_with("**");
536                let right = self.right(double_wild);
537                self.index = if right.is_empty() {
538                    self.inner
539                        .previous_delimiter(self.inner.len())
540                        .map_or(0, |n| n + 1)
541                } else {
542                    self.inner
543                        .previous_delimiter(
544                            self.inner.len()
545                                - right.len()
546                                - (self.inner.len() != right.len()) as usize,
547                        )
548                        .map_or(0, |n| n + 1)
549                };
550                if right.is_empty() {
551                    self.next()
552                } else {
553                    // SAFETY: because any keyexpr split at `/` becomes 2 valid keyexprs by design, it's safe to assume the constraint is valid once both sides have been validated to not be empty.
554                    (!left.is_empty()).then(|| unsafe {
555                        (
556                            keyexpr::from_str_unchecked(left),
557                            keyexpr::from_str_unchecked(right),
558                        )
559                    })
560                }
561            }
562        }
563    }
564}
565#[test]
566fn splits() {
567    let ke = keyexpr::new("a/**/b/c").unwrap();
568    let mut splits = ke.iter_splits_ltr();
569    assert_eq!(
570        splits.next(),
571        Some((
572            keyexpr::new("a/**").unwrap(),
573            keyexpr::new("**/b/c").unwrap()
574        ))
575    );
576    assert_eq!(
577        splits.next(),
578        Some((keyexpr::new("a/**/b").unwrap(), keyexpr::new("c").unwrap()))
579    );
580    assert_eq!(splits.next(), None);
581    let mut splits = ke.iter_splits_rtl();
582    assert_eq!(
583        splits.next(),
584        Some((keyexpr::new("a/**/b").unwrap(), keyexpr::new("c").unwrap()))
585    );
586    assert_eq!(
587        splits.next(),
588        Some((
589            keyexpr::new("a/**").unwrap(),
590            keyexpr::new("**/b/c").unwrap()
591        ))
592    );
593    assert_eq!(splits.next(), None);
594    let ke = keyexpr::new("**").unwrap();
595    let mut splits = ke.iter_splits_ltr();
596    assert_eq!(
597        splits.next(),
598        Some((keyexpr::new("**").unwrap(), keyexpr::new("**").unwrap()))
599    );
600    assert_eq!(splits.next(), None);
601    let ke = keyexpr::new("ab").unwrap();
602    let mut splits = ke.iter_splits_ltr();
603    assert_eq!(splits.next(), None);
604    let ke = keyexpr::new("ab/cd").unwrap();
605    let mut splits = ke.iter_splits_ltr();
606    assert_eq!(
607        splits.next(),
608        Some((keyexpr::new("ab").unwrap(), keyexpr::new("cd").unwrap()))
609    );
610    assert_eq!(splits.next(), None);
611    for (i, ke) in crate::fuzzer::KeyExprFuzzer(rand::thread_rng())
612        .take(100)
613        .enumerate()
614    {
615        dbg!(i, &ke);
616        let splits = ke.iter_splits_ltr().collect::<Vec<_>>();
617        assert_eq!(splits, {
618            let mut rtl_rev = ke.iter_splits_rtl().collect::<Vec<_>>();
619            rtl_rev.reverse();
620            rtl_rev
621        });
622        assert!(!splits
623            .iter()
624            .any(|s| s.0.ends_with('/') || s.1.starts_with('/')));
625    }
626}
627
628#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
629pub struct Chunks<'a> {
630    inner: &'a str,
631}
632impl<'a> Chunks<'a> {
633    /// Convert the remaining part of the iterator to a keyexpr if it is not empty.
634    pub const fn as_keyexpr(self) -> Option<&'a keyexpr> {
635        match self.inner.is_empty() {
636            true => None,
637            _ => Some(unsafe { keyexpr::from_str_unchecked(self.inner) }),
638        }
639    }
640    /// Peek at the next chunk without consuming it.
641    pub fn peek(&self) -> Option<&keyexpr> {
642        if self.inner.is_empty() {
643            None
644        } else {
645            Some(unsafe {
646                keyexpr::from_str_unchecked(
647                    &self.inner[..self.inner.find('/').unwrap_or(self.inner.len())],
648                )
649            })
650        }
651    }
652    /// Peek at the last chunk without consuming it.
653    pub fn peek_back(&self) -> Option<&keyexpr> {
654        if self.inner.is_empty() {
655            None
656        } else {
657            Some(unsafe {
658                keyexpr::from_str_unchecked(
659                    &self.inner[self.inner.rfind('/').map_or(0, |i| i + 1)..],
660                )
661            })
662        }
663    }
664}
665impl<'a> Iterator for Chunks<'a> {
666    type Item = &'a keyexpr;
667    fn next(&mut self) -> Option<Self::Item> {
668        if self.inner.is_empty() {
669            return None;
670        }
671        let (next, inner) = self.inner.split_once('/').unwrap_or((self.inner, ""));
672        self.inner = inner;
673        Some(unsafe { keyexpr::from_str_unchecked(next) })
674    }
675}
676impl DoubleEndedIterator for Chunks<'_> {
677    fn next_back(&mut self) -> Option<Self::Item> {
678        if self.inner.is_empty() {
679            return None;
680        }
681        let (inner, next) = self.inner.rsplit_once('/').unwrap_or(("", self.inner));
682        self.inner = inner;
683        Some(unsafe { keyexpr::from_str_unchecked(next) })
684    }
685}
686
687impl Div for &keyexpr {
688    type Output = OwnedKeyExpr;
689    fn div(self, rhs: Self) -> Self::Output {
690        self.join(rhs).unwrap() // Joining 2 key expressions should always result in a canonizable string.
691    }
692}
693
694/// The possible relations between two sets.
695///
696/// Note that [`Equals`](SetIntersectionLevel::Equals) implies [`Includes`](SetIntersectionLevel::Includes), which itself implies [`Intersects`](SetIntersectionLevel::Intersects).
697///
698/// You can check for intersection with `level >= SetIntersecionLevel::Intersection` and for inclusion with `level >= SetIntersectionLevel::Includes`.
699#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
700#[cfg(feature = "unstable")]
701pub enum SetIntersectionLevel {
702    Disjoint,
703    Intersects,
704    Includes,
705    Equals,
706}
707
708#[cfg(feature = "unstable")]
709#[test]
710fn intersection_level_cmp() {
711    use SetIntersectionLevel::*;
712    assert!(Disjoint < Intersects);
713    assert!(Intersects < Includes);
714    assert!(Includes < Equals);
715}
716
717impl fmt::Debug for keyexpr {
718    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
719        write!(f, "ke`{}`", self.as_ref())
720    }
721}
722
723impl fmt::Display for keyexpr {
724    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
725        f.write_str(self)
726    }
727}
728
729#[repr(i8)]
730enum KeyExprError {
731    LoneDollarStar = -1,
732    SingleStarAfterDoubleStar = -2,
733    DoubleStarAfterDoubleStar = -3,
734    EmptyChunk = -4,
735    StarInChunk = -5,
736    DollarAfterDollar = -6,
737    SharpOrQMark = -7,
738    UnboundDollar = -8,
739}
740
741impl KeyExprError {
742    #[cold]
743    fn into_err(self, s: &str) -> ZError {
744        let error = match &self {
745            Self::LoneDollarStar => anyhow!("Invalid Key Expr `{s}`: empty chunks are forbidden, as well as leading and trailing slashes"),
746            Self::SingleStarAfterDoubleStar => anyhow!("Invalid Key Expr `{s}`: `**/*` must be replaced by `*/**` to reach canon-form"),
747            Self::DoubleStarAfterDoubleStar => anyhow!("Invalid Key Expr `{s}`: `**/**` must be replaced by `**` to reach canon-form"),
748            Self::EmptyChunk => anyhow!("Invalid Key Expr `{s}`: empty chunks are forbidden, as well as leading and trailing slashes"),
749            Self::StarInChunk => anyhow!("Invalid Key Expr `{s}`: `*` may only be preceded by `/` or `$`"),
750            Self::DollarAfterDollar => anyhow!("Invalid Key Expr `{s}`: `$` is not allowed after `$*`"),
751            Self::SharpOrQMark => anyhow!("Invalid Key Expr `{s}`: `#` and `?` are forbidden characters"),
752            Self::UnboundDollar => anyhow!("Invalid Key Expr `{s}`: `$` is only allowed in `$*`")
753        };
754        zerror!((self) error).into()
755    }
756}
757
758impl<'a> TryFrom<&'a str> for &'a keyexpr {
759    type Error = ZError;
760
761    fn try_from(value: &'a str) -> Result<Self, Self::Error> {
762        use KeyExprError::*;
763        // Check for emptiness or trailing slash, as they are not caught after.
764        if value.is_empty() || value.ends_with('/') {
765            return Err(EmptyChunk.into_err(value));
766        }
767        let bytes = value.as_bytes();
768        // The start of the chunk, i.e. the index of the char after the '/'.
769        let mut chunk_start = 0;
770        // Use a while loop to scan the string because it requires to advance the iteration
771        // manually for some characters, e.g. '$'.
772        let mut i = 0;
773        while i < bytes.len() {
774            match bytes[i] {
775                // In UTF-8, all keyexpr special characters are lesser or equal to '/', except '?'
776                // This shortcut greatly reduce the number of operations for alphanumeric
777                // characters, which are the most common in keyexprs.
778                c if c > b'/' && c != b'?' => i += 1,
779                // A chunk cannot start with '/'
780                b'/' if i == chunk_start => return Err(EmptyChunk.into_err(value)),
781                // `chunk_start` is updated when starting a new chunk.
782                b'/' => {
783                    i += 1;
784                    chunk_start = i;
785                }
786                // The first encountered '*' must be at the beginning of a chunk
787                b'*' if i != chunk_start => return Err(StarInChunk.into_err(value)),
788                // When a '*' is match, it means this is a wildcard chunk, possibly with two "**",
789                // which must be followed by a '/' or the end of the string.
790                // So the next character is checked, and the cursor
791                b'*' => match bytes.get(i + 1) {
792                    // Break if end of string is reached.
793                    None => break,
794                    // If a '/' is found, start a new chunk, and advance the cursor to take in
795                    // previous check.
796                    Some(&b'/') => {
797                        i += 2;
798                        chunk_start = i;
799                    }
800                    // If a second '*' is found, the next character must be a slash.
801                    Some(&b'*') => match bytes.get(i + 2) {
802                        // Break if end of string is reached.
803                        None => break,
804                        // Because a "**" chunk cannot be followed by "*" or "**", the next char is
805                        // checked to not be a '*'.
806                        Some(&b'/') if matches!(bytes.get(i + 3), Some(b'*')) => {
807                            // If there are two consecutive wildcard chunks, raise the appropriate
808                            // error.
809                            #[cold]
810                            fn double_star_err(value: &str, i: usize) -> ZError {
811                                match (value.as_bytes().get(i + 4), value.as_bytes().get(i + 5)) {
812                                    (None | Some(&b'/'), _) => SingleStarAfterDoubleStar,
813                                    (Some(&b'*'), None | Some(&b'/')) => DoubleStarAfterDoubleStar,
814                                    _ => StarInChunk,
815                                }
816                                .into_err(value)
817                            }
818                            return Err(double_star_err(value, i));
819                        }
820                        // If a '/' is found, start a new chunk, and advance the cursor to take in
821                        // previous checks.
822                        Some(&b'/') => {
823                            i += 3;
824                            chunk_start = i;
825                        }
826                        // This is not a "**" chunk, raise an error.
827                        _ => return Err(StarInChunk.into_err(value)),
828                    },
829                    // This is not a "*" chunk, raise an error.
830                    _ => return Err(StarInChunk.into_err(value)),
831                },
832                // A '$' must be followed by '*'.
833                b'$' if bytes.get(i + 1) != Some(&b'*') => {
834                    return Err(UnboundDollar.into_err(value))
835                }
836                // "$*" has some additional rules to check.
837                b'$' => match bytes.get(i + 2) {
838                    // "$*" cannot be followed by '$'.
839                    Some(&b'$') => return Err(DollarAfterDollar.into_err(value)),
840                    // "$*" cannot be alone in a chunk
841                    Some(&b'/') | None if i == chunk_start => {
842                        return Err(LoneDollarStar.into_err(value))
843                    }
844                    // Break if end of string is reached.
845                    None => break,
846                    // Everything is fine, advance the cursor taking the '*' check in account.
847                    _ => i += 2,
848                },
849                // '#' and '?' are forbidden.
850                b'#' | b'?' => return Err(SharpOrQMark.into_err(value)),
851                // Fallback for unmatched characters
852                _ => i += 1,
853            }
854        }
855        Ok(unsafe { keyexpr::from_str_unchecked(value) })
856    }
857}
858
859impl<'a> TryFrom<&'a mut str> for &'a keyexpr {
860    type Error = ZError;
861    fn try_from(value: &'a mut str) -> Result<Self, Self::Error> {
862        (value as &'a str).try_into()
863    }
864}
865
866impl<'a> TryFrom<&'a mut String> for &'a keyexpr {
867    type Error = ZError;
868    fn try_from(value: &'a mut String) -> Result<Self, Self::Error> {
869        (value.as_str()).try_into()
870    }
871}
872
873impl<'a> TryFrom<&'a String> for &'a keyexpr {
874    type Error = ZError;
875    fn try_from(value: &'a String) -> Result<Self, Self::Error> {
876        (value.as_str()).try_into()
877    }
878}
879impl<'a> TryFrom<&'a &'a str> for &'a keyexpr {
880    type Error = ZError;
881    fn try_from(value: &'a &'a str) -> Result<Self, Self::Error> {
882        (*value).try_into()
883    }
884}
885impl<'a> TryFrom<&'a &'a mut str> for &'a keyexpr {
886    type Error = ZError;
887    fn try_from(value: &'a &'a mut str) -> Result<Self, Self::Error> {
888        keyexpr::new(*value)
889    }
890}
891#[test]
892fn autocanon() {
893    let mut s: Box<str> = Box::from("hello/**/*");
894    let mut s: &mut str = &mut s;
895    assert_eq!(keyexpr::autocanonize(&mut s).unwrap(), "hello/*/**");
896}
897
898impl Deref for keyexpr {
899    type Target = str;
900    fn deref(&self) -> &Self::Target {
901        unsafe { core::mem::transmute(self) }
902    }
903}
904impl AsRef<str> for keyexpr {
905    fn as_ref(&self) -> &str {
906        self
907    }
908}
909
910impl PartialEq<str> for keyexpr {
911    fn eq(&self, other: &str) -> bool {
912        self.as_str() == other
913    }
914}
915
916impl PartialEq<keyexpr> for str {
917    fn eq(&self, other: &keyexpr) -> bool {
918        self == other.as_str()
919    }
920}
921
922impl Borrow<keyexpr> for OwnedKeyExpr {
923    fn borrow(&self) -> &keyexpr {
924        self
925    }
926}
927impl ToOwned for keyexpr {
928    type Owned = OwnedKeyExpr;
929    fn to_owned(&self) -> Self::Owned {
930        OwnedKeyExpr::from(self)
931    }
932}
933
934/// A keyexpr that is statically known not to contain any wild chunks.
935#[allow(non_camel_case_types)]
936#[repr(transparent)]
937#[derive(PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
938pub struct nonwild_keyexpr(keyexpr);
939
940impl nonwild_keyexpr {
941    /// Attempts to construct a non-wild key expression from anything convertible to keyexpression.
942    ///
943    /// Will return an Err if `t` isn't a valid key expression.
944    pub fn new<'a, T, E>(t: &'a T) -> Result<&'a Self, ZError>
945    where
946        &'a keyexpr: TryFrom<&'a T, Error = E>,
947        E: Into<ZError>,
948        T: ?Sized,
949    {
950        let ke: &'a keyexpr = t.try_into().map_err(|e: E| e.into())?;
951        ke.try_into()
952    }
953
954    /// # Safety
955    /// This constructs a [`nonwild_keyexpr`] without ensuring that it is a valid key-expression without wild chunks.
956    ///
957    /// Much like [`core::str::from_utf8_unchecked`], this is memory-safe, but calling this without maintaining
958    /// [`nonwild_keyexpr`]'s invariants yourself may lead to unexpected behaviors, the Zenoh network dropping your messages.
959    pub const unsafe fn from_str_unchecked(s: &str) -> &Self {
960        core::mem::transmute(s)
961    }
962}
963
964impl Deref for nonwild_keyexpr {
965    type Target = keyexpr;
966    fn deref(&self) -> &Self::Target {
967        &self.0
968    }
969}
970
971impl<'a> TryFrom<&'a keyexpr> for &'a nonwild_keyexpr {
972    type Error = ZError;
973    fn try_from(value: &'a keyexpr) -> Result<Self, Self::Error> {
974        if value.is_wild_impl() {
975            bail!("nonwild_keyexpr can not contain any wild chunks")
976        }
977        Ok(unsafe { core::mem::transmute::<&keyexpr, &nonwild_keyexpr>(value) })
978    }
979}
980
981impl Borrow<nonwild_keyexpr> for OwnedNonWildKeyExpr {
982    fn borrow(&self) -> &nonwild_keyexpr {
983        self
984    }
985}
986
987impl ToOwned for nonwild_keyexpr {
988    type Owned = OwnedNonWildKeyExpr;
989    fn to_owned(&self) -> Self::Owned {
990        OwnedNonWildKeyExpr::from(self)
991    }
992}
993
994#[cfg(feature = "internal")]
995#[test]
996fn test_keyexpr_strip_prefix() {
997    let expectations = [
998        (("demo/example/test/**", "demo/example/test"), &["**"][..]),
999        (("demo/example/**", "demo/example/test"), &["**"]),
1000        (("**", "demo/example/test"), &["**"]),
1001        (
1002            ("demo/example/test/**/x$*/**", "demo/example/test"),
1003            &["**/x$*/**"],
1004        ),
1005        (("demo/**/xyz", "demo/example/test"), &["**/xyz"]),
1006        (("demo/**/test/**", "demo/example/test"), &["**"]),
1007        (
1008            ("demo/**/ex$*/*/xyz", "demo/example/test"),
1009            ["xyz", "**/ex$*/*/xyz"].as_ref(),
1010        ),
1011        (
1012            ("demo/**/ex$*/t$*/xyz", "demo/example/test"),
1013            ["xyz", "**/ex$*/t$*/xyz"].as_ref(),
1014        ),
1015        (
1016            ("demo/**/te$*/*/xyz", "demo/example/test"),
1017            ["*/xyz", "**/te$*/*/xyz"].as_ref(),
1018        ),
1019        (("demo/example/test", "demo/example/test"), [].as_ref()),
1020    ]
1021    .map(|((a, b), expected)| {
1022        (
1023            (keyexpr::new(a).unwrap(), keyexpr::new(b).unwrap()),
1024            expected
1025                .iter()
1026                .map(|s| keyexpr::new(*s).unwrap())
1027                .collect::<Vec<_>>(),
1028        )
1029    });
1030    for ((ke, prefix), expected) in expectations {
1031        dbg!(ke, prefix);
1032        assert_eq!(ke.strip_prefix(prefix), expected)
1033    }
1034}
1035
1036#[cfg(feature = "internal")]
1037#[test]
1038fn test_keyexpr_strip_nonwild_prefix() {
1039    let expectations = [
1040        (("demo/example/test/**", "demo/example/test"), Some("**")),
1041        (("demo/example/**", "demo/example/test"), Some("**")),
1042        (("**", "demo/example/test"), Some("**")),
1043        (("*/example/test/1", "demo/example/test"), Some("1")),
1044        (("demo/*/test/1", "demo/example/test"), Some("1")),
1045        (("*/*/test/1", "demo/example/test"), Some("1")),
1046        (("*/*/*/1", "demo/example/test"), Some("1")),
1047        (("*/test/1", "demo/example/test"), None),
1048        (("*/*/1", "demo/example/test"), None),
1049        (("*/*/**", "demo/example/test"), Some("**")),
1050        (
1051            ("demo/example/test/**/x$*/**", "demo/example/test"),
1052            Some("**/x$*/**"),
1053        ),
1054        (("demo/**/xyz", "demo/example/test"), Some("**/xyz")),
1055        (("demo/**/test/**", "demo/example/test"), Some("**/test/**")),
1056        (
1057            ("demo/**/ex$*/*/xyz", "demo/example/test"),
1058            Some("**/ex$*/*/xyz"),
1059        ),
1060        (
1061            ("demo/**/ex$*/t$*/xyz", "demo/example/test"),
1062            Some("**/ex$*/t$*/xyz"),
1063        ),
1064        (
1065            ("demo/**/te$*/*/xyz", "demo/example/test"),
1066            Some("**/te$*/*/xyz"),
1067        ),
1068        (("demo/example/test", "demo/example/test"), None),
1069        (("demo/example/test1/something", "demo/example/test"), None),
1070        (
1071            ("demo/example/test$*/something", "demo/example/test"),
1072            Some("something"),
1073        ),
1074        (("*/example/test/something", "@demo/example/test"), None),
1075        (("**/test/something", "@demo/example/test"), None),
1076        (("**/test/something", "demo/example/@test"), None),
1077        (
1078            ("@demo/*/test/something", "@demo/example/test"),
1079            Some("something"),
1080        ),
1081        (("@demo/*/test/something", "@demo/@example/test"), None),
1082        (("**/@demo/test/something", "@demo/test"), Some("something")),
1083        (("**/@test/something", "demo/@test"), Some("something")),
1084        (
1085            ("@demo/**/@test/something", "@demo/example/@test"),
1086            Some("something"),
1087        ),
1088    ]
1089    .map(|((a, b), expected)| {
1090        (
1091            (keyexpr::new(a).unwrap(), nonwild_keyexpr::new(b).unwrap()),
1092            expected.map(|t| keyexpr::new(t).unwrap()),
1093        )
1094    });
1095    for ((ke, prefix), expected) in expectations {
1096        dbg!(ke, prefix);
1097        assert_eq!(ke.strip_nonwild_prefix(prefix), expected)
1098    }
1099}
1100
1101#[cfg(test)]
1102mod tests {
1103    use test_case::test_case;
1104    use zenoh_result::ErrNo;
1105
1106    use crate::{
1107        key_expr::borrowed::{KeyExprError, KeyExprError::*},
1108        keyexpr,
1109    };
1110
1111    #[test_case("", EmptyChunk; "Empty")]
1112    #[test_case("demo/example/test", None; "Normal key_expr")]
1113    #[test_case("demo/*", None; "Single star at the end")]
1114    #[test_case("demo/**", None; "Double star at the end")]
1115    #[test_case("demo/*/*/test", None; "Single star after single star")]
1116    #[test_case("demo/*/**/test", None; "Double star after single star")]
1117    #[test_case("demo/example$*/test", None; "Dollar with star")]
1118    #[test_case("demo/example$*-$*/test", None; "Multiple dollar with star")]
1119    #[test_case("/demo/example/test", EmptyChunk; "Leading /")]
1120    #[test_case("demo/example/test/", EmptyChunk; "Trailing /")]
1121    #[test_case("demo/$*/test", LoneDollarStar; "Lone $*")]
1122    #[test_case("demo/$*", LoneDollarStar; "Lone $* at the end")]
1123    #[test_case("demo/example$*", None; "Trailing lone $*")]
1124    #[test_case("demo/**/*/test", SingleStarAfterDoubleStar; "Single star after double star")]
1125    #[test_case("demo/**/**/test", DoubleStarAfterDoubleStar; "Double star after double star")]
1126    #[test_case("demo//test", EmptyChunk; "Empty Chunk")]
1127    #[test_case("demo/exam*ple/test", StarInChunk; "Star in chunk")]
1128    #[test_case("demo/example$*$/test", DollarAfterDollar; "Dollar after dollar or star")]
1129    #[test_case("demo/example$*$*/test", DollarAfterDollar; "Dollar star after dollar or star")]
1130    #[test_case("demo/example#/test", SharpOrQMark; "Contain sharp")]
1131    #[test_case("demo/example?/test", SharpOrQMark; "Contain mark")]
1132    #[test_case("demo/$/test", UnboundDollar; "Contain unbounded dollar")]
1133    fn test_keyexpr_new(key_str: &str, error: impl Into<Option<KeyExprError>>) {
1134        assert_eq!(
1135            keyexpr::new(key_str).err().map(|err| {
1136                err.downcast_ref::<zenoh_result::ZError>()
1137                    .unwrap()
1138                    .errno()
1139                    .get()
1140            }),
1141            error.into().map(|err| err as i8)
1142        );
1143    }
1144}
zenoh_keyexpr/key_expr/borrowed.rs

zenoh_keyexpr/key_expr/
borrowed.rs
