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::{bail, Error as ZError, ZResult};
29
30use super::{canon::Canonize, OwnedKeyExpr, OwnedNonWildKeyExpr, FORBIDDEN_CHARS};
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#[test]
709fn intersection_level_cmp() {
710    use SetIntersectionLevel::*;
711    assert!(Disjoint < Intersects);
712    assert!(Intersects < Includes);
713    assert!(Includes < Equals);
714}
715
716impl fmt::Debug for keyexpr {
717    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
718        write!(f, "ke`{}`", self.as_ref())
719    }
720}
721
722impl fmt::Display for keyexpr {
723    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
724        f.write_str(self)
725    }
726}
727
728#[repr(i8)]
729enum KeyExprConstructionError {
730    LoneDollarStar = -1,
731    SingleStarAfterDoubleStar = -2,
732    DoubleStarAfterDoubleStar = -3,
733    EmptyChunk = -4,
734    StarsInChunk = -5,
735    DollarAfterDollarOrStar = -6,
736    ContainsSharpOrQMark = -7,
737    ContainsUnboundDollar = -8,
738}
739
740impl<'a> TryFrom<&'a str> for &'a keyexpr {
741    type Error = ZError;
742
743    fn try_from(value: &'a str) -> Result<Self, Self::Error> {
744        let mut in_big_wild = false;
745        for chunk in value.split('/') {
746            if chunk.is_empty() {
747                bail!((KeyExprConstructionError::EmptyChunk) "Invalid Key Expr `{}`: empty chunks are forbidden, as well as leading and trailing slashes", value)
748            }
749            if chunk == "$*" {
750                bail!((KeyExprConstructionError::LoneDollarStar)
751                    "Invalid Key Expr `{}`: lone `$*`s must be replaced by `*` to reach canon-form",
752                    value
753                )
754            }
755            if in_big_wild {
756                match chunk {
757                    "**" => bail!((KeyExprConstructionError::DoubleStarAfterDoubleStar)
758                        "Invalid Key Expr `{}`: `**/**` must be replaced by `**` to reach canon-form",
759                        value
760                    ),
761                    "*" => bail!((KeyExprConstructionError::SingleStarAfterDoubleStar)
762                        "Invalid Key Expr `{}`: `**/*` must be replaced by `*/**` to reach canon-form",
763                        value
764                    ),
765                    _ => {}
766                }
767            }
768            if chunk == "**" {
769                in_big_wild = true;
770            } else {
771                in_big_wild = false;
772                if chunk != "*" {
773                    let mut split = chunk.split('*');
774                    split.next_back();
775                    if split.any(|s| !s.ends_with('$')) {
776                        bail!((KeyExprConstructionError::StarsInChunk)
777                            "Invalid Key Expr `{}`: `*` and `**` may only be preceded an followed by `/`",
778                            value
779                        )
780                    }
781                }
782            }
783        }
784
785        for (index, forbidden) in value.bytes().enumerate().filter_map(|(i, c)| {
786            if FORBIDDEN_CHARS.contains(&c) {
787                Some((i, c))
788            } else {
789                None
790            }
791        }) {
792            let bytes = value.as_bytes();
793            if forbidden == b'$' {
794                if let Some(b'*') = bytes.get(index + 1) {
795                    if let Some(b'$') = bytes.get(index + 2) {
796                        bail!((KeyExprConstructionError::DollarAfterDollarOrStar)
797                            "Invalid Key Expr `{}`: `$` is not allowed after `$*`",
798                            value
799                        )
800                    }
801                } else {
802                    bail!((KeyExprConstructionError::ContainsUnboundDollar)"Invalid Key Expr `{}`: `$` is only allowed in `$*`", value)
803                }
804            } else {
805                bail!((KeyExprConstructionError::ContainsSharpOrQMark)
806                    "Invalid Key Expr `{}`: `#` and `?` are forbidden characters",
807                    value
808                )
809            }
810        }
811        Ok(unsafe { keyexpr::from_str_unchecked(value) })
812    }
813}
814
815impl<'a> TryFrom<&'a mut str> for &'a keyexpr {
816    type Error = ZError;
817    fn try_from(value: &'a mut str) -> Result<Self, Self::Error> {
818        (value as &'a str).try_into()
819    }
820}
821
822impl<'a> TryFrom<&'a mut String> for &'a keyexpr {
823    type Error = ZError;
824    fn try_from(value: &'a mut String) -> Result<Self, Self::Error> {
825        (value.as_str()).try_into()
826    }
827}
828
829impl<'a> TryFrom<&'a String> for &'a keyexpr {
830    type Error = ZError;
831    fn try_from(value: &'a String) -> Result<Self, Self::Error> {
832        (value.as_str()).try_into()
833    }
834}
835impl<'a> TryFrom<&'a &'a str> for &'a keyexpr {
836    type Error = ZError;
837    fn try_from(value: &'a &'a str) -> Result<Self, Self::Error> {
838        (*value).try_into()
839    }
840}
841impl<'a> TryFrom<&'a &'a mut str> for &'a keyexpr {
842    type Error = ZError;
843    fn try_from(value: &'a &'a mut str) -> Result<Self, Self::Error> {
844        keyexpr::new(*value)
845    }
846}
847#[test]
848fn autocanon() {
849    let mut s: Box<str> = Box::from("hello/**/*");
850    let mut s: &mut str = &mut s;
851    assert_eq!(keyexpr::autocanonize(&mut s).unwrap(), "hello/*/**");
852}
853
854impl Deref for keyexpr {
855    type Target = str;
856    fn deref(&self) -> &Self::Target {
857        unsafe { core::mem::transmute(self) }
858    }
859}
860impl AsRef<str> for keyexpr {
861    fn as_ref(&self) -> &str {
862        self
863    }
864}
865
866impl PartialEq<str> for keyexpr {
867    fn eq(&self, other: &str) -> bool {
868        self.as_str() == other
869    }
870}
871
872impl PartialEq<keyexpr> for str {
873    fn eq(&self, other: &keyexpr) -> bool {
874        self == other.as_str()
875    }
876}
877
878impl Borrow<keyexpr> for OwnedKeyExpr {
879    fn borrow(&self) -> &keyexpr {
880        self
881    }
882}
883impl ToOwned for keyexpr {
884    type Owned = OwnedKeyExpr;
885    fn to_owned(&self) -> Self::Owned {
886        OwnedKeyExpr::from(self)
887    }
888}
889
890/// A keyexpr that is statically known not to contain any wild chunks.
891#[allow(non_camel_case_types)]
892#[repr(transparent)]
893#[derive(PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
894pub struct nonwild_keyexpr(keyexpr);
895
896impl nonwild_keyexpr {
897    /// Attempts to construct a non-wild key expression from anything convertible to keyexpression.
898    ///
899    /// Will return an Err if `t` isn't a valid key expression.
900    pub fn new<'a, T, E>(t: &'a T) -> Result<&'a Self, ZError>
901    where
902        &'a keyexpr: TryFrom<&'a T, Error = E>,
903        E: Into<ZError>,
904        T: ?Sized,
905    {
906        let ke: &'a keyexpr = t.try_into().map_err(|e: E| e.into())?;
907        ke.try_into()
908    }
909
910    /// # Safety
911    /// This constructs a [`nonwild_keyexpr`] without ensuring that it is a valid key-expression without wild chunks.
912    ///
913    /// Much like [`core::str::from_utf8_unchecked`], this is memory-safe, but calling this without maintaining
914    /// [`nonwild_keyexpr`]'s invariants yourself may lead to unexpected behaviors, the Zenoh network dropping your messages.
915    pub const unsafe fn from_str_unchecked(s: &str) -> &Self {
916        core::mem::transmute(s)
917    }
918}
919
920impl Deref for nonwild_keyexpr {
921    type Target = keyexpr;
922    fn deref(&self) -> &Self::Target {
923        &self.0
924    }
925}
926
927impl<'a> TryFrom<&'a keyexpr> for &'a nonwild_keyexpr {
928    type Error = ZError;
929    fn try_from(value: &'a keyexpr) -> Result<Self, Self::Error> {
930        if value.is_wild_impl() {
931            bail!("nonwild_keyexpr can not contain any wild chunks")
932        }
933        Ok(unsafe { core::mem::transmute::<&keyexpr, &nonwild_keyexpr>(value) })
934    }
935}
936
937impl Borrow<nonwild_keyexpr> for OwnedNonWildKeyExpr {
938    fn borrow(&self) -> &nonwild_keyexpr {
939        self
940    }
941}
942
943impl ToOwned for nonwild_keyexpr {
944    type Owned = OwnedNonWildKeyExpr;
945    fn to_owned(&self) -> Self::Owned {
946        OwnedNonWildKeyExpr::from(self)
947    }
948}
949
950#[test]
951fn test_keyexpr_strip_prefix() {
952    let expectations = [
953        (("demo/example/test/**", "demo/example/test"), &["**"][..]),
954        (("demo/example/**", "demo/example/test"), &["**"]),
955        (("**", "demo/example/test"), &["**"]),
956        (
957            ("demo/example/test/**/x$*/**", "demo/example/test"),
958            &["**/x$*/**"],
959        ),
960        (("demo/**/xyz", "demo/example/test"), &["**/xyz"]),
961        (("demo/**/test/**", "demo/example/test"), &["**"]),
962        (
963            ("demo/**/ex$*/*/xyz", "demo/example/test"),
964            ["xyz", "**/ex$*/*/xyz"].as_ref(),
965        ),
966        (
967            ("demo/**/ex$*/t$*/xyz", "demo/example/test"),
968            ["xyz", "**/ex$*/t$*/xyz"].as_ref(),
969        ),
970        (
971            ("demo/**/te$*/*/xyz", "demo/example/test"),
972            ["*/xyz", "**/te$*/*/xyz"].as_ref(),
973        ),
974        (("demo/example/test", "demo/example/test"), [].as_ref()),
975    ]
976    .map(|((a, b), expected)| {
977        (
978            (keyexpr::new(a).unwrap(), keyexpr::new(b).unwrap()),
979            expected
980                .iter()
981                .map(|s| keyexpr::new(*s).unwrap())
982                .collect::<Vec<_>>(),
983        )
984    });
985    for ((ke, prefix), expected) in expectations {
986        dbg!(ke, prefix);
987        assert_eq!(ke.strip_prefix(prefix), expected)
988    }
989}
990
991#[test]
992fn test_keyexpr_strip_nonwild_prefix() {
993    let expectations = [
994        (("demo/example/test/**", "demo/example/test"), Some("**")),
995        (("demo/example/**", "demo/example/test"), Some("**")),
996        (("**", "demo/example/test"), Some("**")),
997        (("*/example/test/1", "demo/example/test"), Some("1")),
998        (("demo/*/test/1", "demo/example/test"), Some("1")),
999        (("*/*/test/1", "demo/example/test"), Some("1")),
1000        (("*/*/*/1", "demo/example/test"), Some("1")),
1001        (("*/test/1", "demo/example/test"), None),
1002        (("*/*/1", "demo/example/test"), None),
1003        (("*/*/**", "demo/example/test"), Some("**")),
1004        (
1005            ("demo/example/test/**/x$*/**", "demo/example/test"),
1006            Some("**/x$*/**"),
1007        ),
1008        (("demo/**/xyz", "demo/example/test"), Some("**/xyz")),
1009        (("demo/**/test/**", "demo/example/test"), Some("**/test/**")),
1010        (
1011            ("demo/**/ex$*/*/xyz", "demo/example/test"),
1012            Some("**/ex$*/*/xyz"),
1013        ),
1014        (
1015            ("demo/**/ex$*/t$*/xyz", "demo/example/test"),
1016            Some("**/ex$*/t$*/xyz"),
1017        ),
1018        (
1019            ("demo/**/te$*/*/xyz", "demo/example/test"),
1020            Some("**/te$*/*/xyz"),
1021        ),
1022        (("demo/example/test", "demo/example/test"), None),
1023        (("demo/example/test1/something", "demo/example/test"), None),
1024        (
1025            ("demo/example/test$*/something", "demo/example/test"),
1026            Some("something"),
1027        ),
1028        (("*/example/test/something", "@demo/example/test"), None),
1029        (("**/test/something", "@demo/example/test"), None),
1030        (("**/test/something", "demo/example/@test"), None),
1031        (
1032            ("@demo/*/test/something", "@demo/example/test"),
1033            Some("something"),
1034        ),
1035        (("@demo/*/test/something", "@demo/@example/test"), None),
1036        (("**/@demo/test/something", "@demo/test"), Some("something")),
1037        (("**/@test/something", "demo/@test"), Some("something")),
1038        (
1039            ("@demo/**/@test/something", "@demo/example/@test"),
1040            Some("something"),
1041        ),
1042    ]
1043    .map(|((a, b), expected)| {
1044        (
1045            (keyexpr::new(a).unwrap(), nonwild_keyexpr::new(b).unwrap()),
1046            expected.map(|t| keyexpr::new(t).unwrap()),
1047        )
1048    });
1049    for ((ke, prefix), expected) in expectations {
1050        dbg!(ke, prefix);
1051        assert_eq!(ke.strip_nonwild_prefix(prefix), expected)
1052    }
1053}
zenoh_keyexpr/key_expr/borrowed.rs

zenoh_keyexpr/key_expr/
borrowed.rs
