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};
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                continue;
771            }
772            in_big_wild = false;
773            if chunk == "*" {
774                continue;
775            }
776
777            // Perform character-level validation for the chunk
778            let chunk_bytes = chunk.as_bytes();
779            let mut i = 0;
780            while i < chunk_bytes.len() {
781                let byte = chunk_bytes[i];
782                match byte {
783                    b'#' | b'?' => {
784                        bail!((KeyExprConstructionError::ContainsSharpOrQMark)
785                            "Invalid Key Expr `{}`: `#` and `?` are forbidden characters",
786                            value
787                        );
788                    }
789                    b'$' => {
790                        if chunk_bytes.get(i + 1) == Some(&b'*') {
791                            if chunk_bytes.get(i + 2) == Some(&b'$') {
792                                bail!((KeyExprConstructionError::DollarAfterDollarOrStar)
793                                    "Invalid Key Expr `{}`: `$` is not allowed after `$*`",
794                                    value
795                                )
796                            }
797                        } else {
798                            bail!((KeyExprConstructionError::ContainsUnboundDollar)
799                                "Invalid Key Expr `{}`: `$` is only allowed in `$*`",
800                                value
801                            );
802                        }
803                        // A valid `$*` was found, skip the next character in the check.
804                        i += 2;
805                    }
806                    b'*' => {
807                        // A bare `*` is not allowed inside a chunk. It must be part of `$*`.
808                        // If we are here, it means it wasn't preceded by a `$`.
809                        bail!((KeyExprConstructionError::StarsInChunk)
810                            "Invalid Key Expr `{}`: `*` may only be preceded by `/` or `$`",
811                            value
812                        );
813                    }
814                    _ => i += 1, // Move to the next character
815                }
816            }
817        }
818
819        Ok(unsafe { keyexpr::from_str_unchecked(value) })
820    }
821}
822
823impl<'a> TryFrom<&'a mut str> for &'a keyexpr {
824    type Error = ZError;
825    fn try_from(value: &'a mut str) -> Result<Self, Self::Error> {
826        (value as &'a str).try_into()
827    }
828}
829
830impl<'a> TryFrom<&'a mut String> for &'a keyexpr {
831    type Error = ZError;
832    fn try_from(value: &'a mut String) -> Result<Self, Self::Error> {
833        (value.as_str()).try_into()
834    }
835}
836
837impl<'a> TryFrom<&'a String> for &'a keyexpr {
838    type Error = ZError;
839    fn try_from(value: &'a String) -> Result<Self, Self::Error> {
840        (value.as_str()).try_into()
841    }
842}
843impl<'a> TryFrom<&'a &'a str> for &'a keyexpr {
844    type Error = ZError;
845    fn try_from(value: &'a &'a str) -> Result<Self, Self::Error> {
846        (*value).try_into()
847    }
848}
849impl<'a> TryFrom<&'a &'a mut str> for &'a keyexpr {
850    type Error = ZError;
851    fn try_from(value: &'a &'a mut str) -> Result<Self, Self::Error> {
852        keyexpr::new(*value)
853    }
854}
855#[test]
856fn autocanon() {
857    let mut s: Box<str> = Box::from("hello/**/*");
858    let mut s: &mut str = &mut s;
859    assert_eq!(keyexpr::autocanonize(&mut s).unwrap(), "hello/*/**");
860}
861
862impl Deref for keyexpr {
863    type Target = str;
864    fn deref(&self) -> &Self::Target {
865        unsafe { core::mem::transmute(self) }
866    }
867}
868impl AsRef<str> for keyexpr {
869    fn as_ref(&self) -> &str {
870        self
871    }
872}
873
874impl PartialEq<str> for keyexpr {
875    fn eq(&self, other: &str) -> bool {
876        self.as_str() == other
877    }
878}
879
880impl PartialEq<keyexpr> for str {
881    fn eq(&self, other: &keyexpr) -> bool {
882        self == other.as_str()
883    }
884}
885
886impl Borrow<keyexpr> for OwnedKeyExpr {
887    fn borrow(&self) -> &keyexpr {
888        self
889    }
890}
891impl ToOwned for keyexpr {
892    type Owned = OwnedKeyExpr;
893    fn to_owned(&self) -> Self::Owned {
894        OwnedKeyExpr::from(self)
895    }
896}
897
898/// A keyexpr that is statically known not to contain any wild chunks.
899#[allow(non_camel_case_types)]
900#[repr(transparent)]
901#[derive(PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
902pub struct nonwild_keyexpr(keyexpr);
903
904impl nonwild_keyexpr {
905    /// Attempts to construct a non-wild key expression from anything convertible to keyexpression.
906    ///
907    /// Will return an Err if `t` isn't a valid key expression.
908    pub fn new<'a, T, E>(t: &'a T) -> Result<&'a Self, ZError>
909    where
910        &'a keyexpr: TryFrom<&'a T, Error = E>,
911        E: Into<ZError>,
912        T: ?Sized,
913    {
914        let ke: &'a keyexpr = t.try_into().map_err(|e: E| e.into())?;
915        ke.try_into()
916    }
917
918    /// # Safety
919    /// This constructs a [`nonwild_keyexpr`] without ensuring that it is a valid key-expression without wild chunks.
920    ///
921    /// Much like [`core::str::from_utf8_unchecked`], this is memory-safe, but calling this without maintaining
922    /// [`nonwild_keyexpr`]'s invariants yourself may lead to unexpected behaviors, the Zenoh network dropping your messages.
923    pub const unsafe fn from_str_unchecked(s: &str) -> &Self {
924        core::mem::transmute(s)
925    }
926}
927
928impl Deref for nonwild_keyexpr {
929    type Target = keyexpr;
930    fn deref(&self) -> &Self::Target {
931        &self.0
932    }
933}
934
935impl<'a> TryFrom<&'a keyexpr> for &'a nonwild_keyexpr {
936    type Error = ZError;
937    fn try_from(value: &'a keyexpr) -> Result<Self, Self::Error> {
938        if value.is_wild_impl() {
939            bail!("nonwild_keyexpr can not contain any wild chunks")
940        }
941        Ok(unsafe { core::mem::transmute::<&keyexpr, &nonwild_keyexpr>(value) })
942    }
943}
944
945impl Borrow<nonwild_keyexpr> for OwnedNonWildKeyExpr {
946    fn borrow(&self) -> &nonwild_keyexpr {
947        self
948    }
949}
950
951impl ToOwned for nonwild_keyexpr {
952    type Owned = OwnedNonWildKeyExpr;
953    fn to_owned(&self) -> Self::Owned {
954        OwnedNonWildKeyExpr::from(self)
955    }
956}
957
958#[test]
959fn test_keyexpr_strip_prefix() {
960    let expectations = [
961        (("demo/example/test/**", "demo/example/test"), &["**"][..]),
962        (("demo/example/**", "demo/example/test"), &["**"]),
963        (("**", "demo/example/test"), &["**"]),
964        (
965            ("demo/example/test/**/x$*/**", "demo/example/test"),
966            &["**/x$*/**"],
967        ),
968        (("demo/**/xyz", "demo/example/test"), &["**/xyz"]),
969        (("demo/**/test/**", "demo/example/test"), &["**"]),
970        (
971            ("demo/**/ex$*/*/xyz", "demo/example/test"),
972            ["xyz", "**/ex$*/*/xyz"].as_ref(),
973        ),
974        (
975            ("demo/**/ex$*/t$*/xyz", "demo/example/test"),
976            ["xyz", "**/ex$*/t$*/xyz"].as_ref(),
977        ),
978        (
979            ("demo/**/te$*/*/xyz", "demo/example/test"),
980            ["*/xyz", "**/te$*/*/xyz"].as_ref(),
981        ),
982        (("demo/example/test", "demo/example/test"), [].as_ref()),
983    ]
984    .map(|((a, b), expected)| {
985        (
986            (keyexpr::new(a).unwrap(), keyexpr::new(b).unwrap()),
987            expected
988                .iter()
989                .map(|s| keyexpr::new(*s).unwrap())
990                .collect::<Vec<_>>(),
991        )
992    });
993    for ((ke, prefix), expected) in expectations {
994        dbg!(ke, prefix);
995        assert_eq!(ke.strip_prefix(prefix), expected)
996    }
997}
998
999#[test]
1000fn test_keyexpr_strip_nonwild_prefix() {
1001    let expectations = [
1002        (("demo/example/test/**", "demo/example/test"), Some("**")),
1003        (("demo/example/**", "demo/example/test"), Some("**")),
1004        (("**", "demo/example/test"), Some("**")),
1005        (("*/example/test/1", "demo/example/test"), Some("1")),
1006        (("demo/*/test/1", "demo/example/test"), Some("1")),
1007        (("*/*/test/1", "demo/example/test"), Some("1")),
1008        (("*/*/*/1", "demo/example/test"), Some("1")),
1009        (("*/test/1", "demo/example/test"), None),
1010        (("*/*/1", "demo/example/test"), None),
1011        (("*/*/**", "demo/example/test"), Some("**")),
1012        (
1013            ("demo/example/test/**/x$*/**", "demo/example/test"),
1014            Some("**/x$*/**"),
1015        ),
1016        (("demo/**/xyz", "demo/example/test"), Some("**/xyz")),
1017        (("demo/**/test/**", "demo/example/test"), Some("**/test/**")),
1018        (
1019            ("demo/**/ex$*/*/xyz", "demo/example/test"),
1020            Some("**/ex$*/*/xyz"),
1021        ),
1022        (
1023            ("demo/**/ex$*/t$*/xyz", "demo/example/test"),
1024            Some("**/ex$*/t$*/xyz"),
1025        ),
1026        (
1027            ("demo/**/te$*/*/xyz", "demo/example/test"),
1028            Some("**/te$*/*/xyz"),
1029        ),
1030        (("demo/example/test", "demo/example/test"), None),
1031        (("demo/example/test1/something", "demo/example/test"), None),
1032        (
1033            ("demo/example/test$*/something", "demo/example/test"),
1034            Some("something"),
1035        ),
1036        (("*/example/test/something", "@demo/example/test"), None),
1037        (("**/test/something", "@demo/example/test"), None),
1038        (("**/test/something", "demo/example/@test"), None),
1039        (
1040            ("@demo/*/test/something", "@demo/example/test"),
1041            Some("something"),
1042        ),
1043        (("@demo/*/test/something", "@demo/@example/test"), None),
1044        (("**/@demo/test/something", "@demo/test"), Some("something")),
1045        (("**/@test/something", "demo/@test"), Some("something")),
1046        (
1047            ("@demo/**/@test/something", "@demo/example/@test"),
1048            Some("something"),
1049        ),
1050    ]
1051    .map(|((a, b), expected)| {
1052        (
1053            (keyexpr::new(a).unwrap(), nonwild_keyexpr::new(b).unwrap()),
1054            expected.map(|t| keyexpr::new(t).unwrap()),
1055        )
1056    });
1057    for ((ke, prefix), expected) in expectations {
1058        dbg!(ke, prefix);
1059        assert_eq!(ke.strip_nonwild_prefix(prefix), expected)
1060    }
1061}
1062
1063#[cfg(test)]
1064mod tests {
1065    use test_case::test_case;
1066
1067    use crate::keyexpr;
1068
1069    #[test_case("demo/example/test", true; "Normal key_expr")]
1070    #[test_case("demo/*/*/test", true; "Single star after single star")]
1071    #[test_case("demo/*/**/test", true; "Single star after double star")]
1072    #[test_case("demo/example$*/test", true; "Dollar with star")]
1073    #[test_case("demo/example$*-$*/test", true; "Multiple dollar with star")]
1074    #[test_case("/demo/example/test", false; "Leading /")]
1075    #[test_case("demo/$*/test", false; "Lone $*")]
1076    #[test_case("demo/**/*/test", false; "Double star after single star")]
1077    #[test_case("demo/**/**/test", false; "Double star after double star")]
1078    #[test_case("demo//test", false; "Empty Chunk")]
1079    #[test_case("demo/exam*ple/test", false; "Stars in chunk")]
1080    #[test_case("demo/example$*$*/test", false; "Dollar after dollar or star")]
1081    #[test_case("demo/example#/test", false; "Contain sharp")]
1082    #[test_case("demo/example?/test", false; "Contain mark")]
1083    #[test_case("demo/$/test", false; "Contain unbounded dollar")]
1084    fn test_str_to_keyexpr(key_str: &str, valid: bool) {
1085        let key = keyexpr::new(key_str);
1086        assert!(key.is_ok() == valid);
1087    }
1088}
zenoh_keyexpr/key_expr/borrowed.rs

zenoh_keyexpr/key_expr/
borrowed.rs
