src/proto/key.rs
//
// Copyright (c) 2025 ZettaScale Technology
//
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License 2.0 which is available at
// http://www.eclipse.org/legal/epl-2.0, or the Apache License, Version 2.0
// which is available at https://www.apache.org/licenses/LICENSE-2.0.
//
// SPDX-License-Identifier: EPL-2.0 OR Apache-2.0
//
// Contributors:
// ZettaScale Zenoh Team, <zenoh@zettascale.tech>
//
use core::{fmt::Display, ops::Deref};
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum KeyError {
EmptyChunk,
StarInChunk,
SingleStarAfterDoubleStar,
DoubleStarAfterDoubleStar,
UnboundDollar,
DollarAfterDollar,
LoneDollarStar,
SharpOrQMark,
}
#[allow(non_camel_case_types)]
#[repr(transparent)]
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct key(str);
impl Display for key {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
write!(f, "{}", self.as_str())
}
}
impl key {
pub fn new(s: &str) -> Result<&key, KeyError> {
if s.is_empty() || s.ends_with('/') {
return Err(KeyError::EmptyChunk);
}
Self::validate(s.as_bytes())?;
Ok(unsafe { &*(s as *const str as *const key) })
}
pub fn unchecked(s: &str) -> &key {
unsafe { &*(s as *const str as *const key) }
}
fn validate(bytes: &[u8]) -> Result<(), KeyError> {
let mut chunk_start = 0;
let mut i = 0;
while i < bytes.len() {
match bytes[i] {
c if c > b'/' && c != b'?' => i += 1,
b'#' | b'?' => return Err(KeyError::SharpOrQMark),
b'/' if i == chunk_start => return Err(KeyError::EmptyChunk),
b'/' => {
i += 1;
chunk_start = i;
}
b'*' if i != chunk_start => return Err(KeyError::StarInChunk),
b'*' => match bytes.get(i + 1) {
None => break,
Some(&b'/') => {
i += 2;
chunk_start = i;
}
Some(&b'*') => match bytes.get(i + 2) {
None => break,
Some(&b'/') if matches!(bytes.get(i + 3), Some(b'*')) => {
return Err(match (bytes.get(i + 4), bytes.get(i + 5)) {
(None | Some(&b'/'), _) => KeyError::SingleStarAfterDoubleStar,
(Some(&b'*'), None | Some(&b'/')) => {
KeyError::DoubleStarAfterDoubleStar
}
_ => KeyError::StarInChunk,
});
}
Some(&b'/') => {
i += 3;
chunk_start = i;
}
_ => return Err(KeyError::StarInChunk),
},
_ => return Err(KeyError::StarInChunk),
},
b'$' if bytes.get(i + 1) != Some(&b'*') => return Err(KeyError::UnboundDollar),
b'$' => match bytes.get(i + 2) {
Some(&b'$') => return Err(KeyError::DollarAfterDollar),
Some(&b'/') | None if i == chunk_start => return Err(KeyError::LoneDollarStar),
None => break,
_ => i += 2,
},
_ => i += 1,
}
}
Ok(())
}
pub const fn as_str(&self) -> &str {
&self.0
}
fn match_complexity(&self) -> MatchComplexity {
let mut has_wilds = false;
for &c in self.as_bytes() {
match c {
b'*' => has_wilds = true,
b'$' => return MatchComplexity::Dsl,
_ => {}
}
}
if has_wilds {
MatchComplexity::ChunkWildsOnly
} else {
MatchComplexity::NoWilds
}
}
pub fn intersects(&self, other: &key) -> bool {
let left = self.as_bytes();
let right = other.as_bytes();
if left == right {
return true;
}
match self.match_complexity() as u8 | other.match_complexity() as u8 {
0 => false,
1 => intersect_impl::<false>(left, right),
_ => intersect_impl::<true>(left, right),
}
}
}
impl Deref for key {
type Target = str;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl AsRef<str> for key {
fn as_ref(&self) -> &str {
&self.0
}
}
impl PartialEq<str> for key {
fn eq(&self, other: &str) -> bool {
self.as_str() == other
}
}
impl PartialEq<key> for str {
fn eq(&self, other: &key) -> bool {
self == other.as_str()
}
}
#[repr(u8)]
enum MatchComplexity {
NoWilds = 0,
ChunkWildsOnly = 1,
Dsl = 2,
}
fn next_chunk(s: &[u8]) -> (&[u8], &[u8]) {
match s.iter().position(|c| *c == b'/') {
Some(i) => (&s[..i], &s[i + 1..]),
None => (s, b""),
}
}
fn has_verbatim_prefix(chunk: &[u8]) -> bool {
matches!(chunk.first(), Some(&b'@'))
}
fn has_any_verbatim(s: &[u8]) -> bool {
s.split(|c| *c == b'/').any(has_verbatim_prefix)
}
fn intersect_impl<const WITH_DSL: bool>(mut left: &[u8], mut right: &[u8]) -> bool {
while !left.is_empty() && !right.is_empty() {
let (chunk_l, rest_l) = next_chunk(left);
let (chunk_r, rest_r) = next_chunk(right);
match (chunk_l, chunk_r) {
(b"**", _) => {
if rest_l.is_empty() {
return !has_any_verbatim(right);
}
return (!has_verbatim_prefix(chunk_r) && intersect_impl::<WITH_DSL>(left, rest_r))
|| intersect_impl::<WITH_DSL>(rest_l, right);
}
(_, b"**") => {
if rest_r.is_empty() {
return !has_any_verbatim(left);
}
return (!has_verbatim_prefix(chunk_l)
&& intersect_impl::<WITH_DSL>(rest_l, right))
|| intersect_impl::<WITH_DSL>(left, rest_r);
}
(l, r) if chunks_intersect::<WITH_DSL>(l, r) => {
left = rest_l;
right = rest_r;
}
_ => return false,
}
}
(left.is_empty() || left == b"**") && (right.is_empty() || right == b"**")
}
fn chunks_intersect<const WITH_DSL: bool>(left: &[u8], right: &[u8]) -> bool {
if left == right {
return true;
}
if has_verbatim_prefix(left) || has_verbatim_prefix(right) {
return false;
}
left == b"*" || right == b"*" || (WITH_DSL && dsl_intersect(left, right))
}
fn dsl_intersect(mut left: &[u8], mut right: &[u8]) -> bool {
while !left.is_empty() && !right.is_empty() {
match (left[0], right[0]) {
(b'$', b'$') => {
if left.len() == 2 || right.len() == 2 {
return true;
}
if dsl_intersect(&left[2..], right) {
return true;
}
return dsl_intersect(left, &right[2..]);
}
(b'$', _) => {
if left.len() == 2 {
return true;
}
if dsl_intersect(&left[2..], right) {
return true;
}
right = &right[1..];
}
(_, b'$') => {
if right.len() == 2 {
return true;
}
if dsl_intersect(left, &right[2..]) {
return true;
}
left = &left[1..];
}
(l, r) if l == r => {
left = &left[1..];
right = &right[1..];
}
_ => return false,
}
}
(left.is_empty() && right.is_empty()) || left == b"$*" || right == b"$*"
}
#[cfg(test)]
mod tests {
use super::*;
macro_rules! test_valid {
($($name:ident: $input:expr),+ $(,)?) => {
$(
#[test]
fn $name() {
assert!(key::new($input).is_ok(), "Expected '{}' to be valid", $input);
}
)+
};
}
macro_rules! test_invalid {
($($name:ident: $input:expr => $err:expr),+ $(,)?) => {
$(
#[test]
fn $name() {
let result = key::new($input);
assert!(matches!(result, Err(e) if e == $err),
"Expected '{}' to fail with {:?}, got {:?}", $input, $err, result);
}
)+
};
}
macro_rules! test_intersect {
($($name:ident: $left:expr, $right:expr => $expected:expr),+ $(,)?) => {
$(
#[test]
fn $name() {
let left = key::new($left).unwrap();
let right = key::new($right).unwrap();
let result = left.intersects(right);
assert_eq!(result, $expected,
"intersects('{}', '{}') expected {}, got {}",
$left, $right, $expected, result);
}
)+
};
}
test_valid! {
valid_simple: "demo/example/test",
valid_single_star: "demo/*",
valid_double_star: "demo/**",
valid_multi_star: "demo/*/*/test",
valid_star_double: "demo/*/**/test",
valid_dollar_star: "demo/example$*/test",
valid_dollar_multi: "demo/example$*-$*/test",
valid_dollar_end: "demo/example$*",
valid_single_chunk: "demo",
valid_verbatim: "@a/b/c",
}
test_invalid! {
invalid_empty: "" => KeyError::EmptyChunk,
invalid_leading_slash: "/demo/example/test" => KeyError::EmptyChunk,
invalid_trailing_slash: "demo/example/test/" => KeyError::EmptyChunk,
invalid_lone_dollar_star: "demo/$*/test" => KeyError::LoneDollarStar,
invalid_lone_dollar_star_end: "demo/$*" => KeyError::LoneDollarStar,
invalid_star_after_double_star: "demo/**/*/test" => KeyError::SingleStarAfterDoubleStar,
invalid_double_after_double: "demo/**/**/test" => KeyError::DoubleStarAfterDoubleStar,
invalid_double_slash: "demo//test" => KeyError::EmptyChunk,
invalid_star_in_chunk: "demo/exam*ple/test" => KeyError::StarInChunk,
invalid_dollar_after_dollar_1: "demo/example$*$/test" => KeyError::DollarAfterDollar,
invalid_dollar_after_dollar_2: "demo/example$*$*/test" => KeyError::DollarAfterDollar,
invalid_sharp: "demo/example#/test" => KeyError::SharpOrQMark,
invalid_qmark: "demo/example?/test" => KeyError::SharpOrQMark,
invalid_unbound_dollar: "demo/$/test" => KeyError::UnboundDollar,
}
test_intersect! {
intersect_equal_simple: "a", "a" => true,
intersect_equal_path: "a/b", "a/b" => true,
intersect_star_simple: "*", "abc" => true,
intersect_star_multi: "*", "xxx" => true,
intersect_path_star: "x/*", "x/abc" => true,
intersect_star_no_slash: "*", "x/abc" => false,
intersect_star_mismatch: "x/*", "abc" => false,
intersect_dollar_suffix: "ab$*", "abcd" => true,
intersect_dollar_suffix_end: "ab$*d", "abcd" => true,
intersect_dollar_exact: "ab$*", "ab" => true,
intersect_dollar_no_match: "ab$*cd", "abxxcxxd" => false,
intersect_dollar_match: "ab$*cd", "abxxcxxcd" => true,
intersect_dollar_trailing: "ab$*cd", "abxxcxxcdx" => false,
intersect_dollar_path: "x/$*abc", "x/abc$*" => true,
intersect_dollar_prefix: "x/a$*", "x/abc$*" => true,
intersect_dollar_both: "x/a$*de", "x/abc$*de" => true,
intersect_dollar_nested: "x/a$*d$*e", "x/a$*e" => true,
intersect_dollar_double: "x/a$*d$*e", "x/a$*c$*e" => true,
intersect_dollar_collapse: "x/a$*d$*e", "x/ade" => true,
intersect_dollar_no_prefix: "x/c$*", "x/abc$*" => false,
intersect_dollar_no_suffix: "x/$*d", "x/$*e" => false,
intersect_multi_star: "a/*/c/*/e", "a/b/c/d/e" => true,
intersect_multi_star_dollar: "a/$*b/c/$*d/e", "a/xb/c/xd/e" => true,
intersect_multi_too_short: "a/*/c/*/e", "a/c/e" => false,
intersect_multi_too_long: "a/*/c/*/e", "a/b/c/d/x/e" => false,
intersect_dstar_simple: "**", "abc" => true,
intersect_dstar_path: "**", "a/b/c" => true,
intersect_dstar_prefix: "ab/**", "ab" => true,
intersect_dstar_suffix: "**/xyz", "a/b/xyz/d/e/f/xyz" => true,
intersect_dstar_dollar: "**/xyz$*xyz", "a/b/xyzdefxyz" => true,
intersect_dstar_no_match: "**/xyz$*xyz", "a/b/xyz/d/e/f/xyz" => false,
intersect_dstar_multi: "a/**/c/**/e", "a/b/b/b/c/d/d/d/e" => true,
intersect_dstar_collapse: "a/**/c/**/e", "a/c/e" => true,
intersect_dstar_complex: "a/**/c/*/e/*", "a/b/b/b/c/d/d/c/d/e/f" => true,
intersect_dstar_no_match_2: "a/**/c/*/e/*", "a/b/b/b/c/d/d/c/d/d/e/f" => false,
intersect_path_mismatch_1: "x/abc", "abc" => false,
intersect_path_prefix: "x/abc", "x/abc" => true,
intersect_no_slash_mismatch: "ab/*", "ab" => false,
intersect_verbatim_equal: "@a", "@a" => true,
intersect_verbatim_prefix: "@a", "@ab" => false,
intersect_verbatim_no_slash: "@a", "@a/b" => false,
intersect_verbatim_no_star: "@a", "@a/*" => false,
intersect_verbatim_no_dstar: "@a", "@a/*/**" => false,
intersect_verbatim_no_dollar: "@a", "@a$*/**" => false,
intersect_verbatim_dstar: "@a", "@a/**" => true,
intersect_verbatim_dstar_dollar: "**/xyz$*xyz", "@a/b/xyzdefxyz" => false,
intersect_verbatim_multi_dstar: "@a/**/c/**/e", "@a/b/b/b/c/d/d/d/e" => true,
intersect_verbatim_no_verbatim_mid: "@a/**/c/**/e", "@a/@b/b/b/c/d/d/d/e" => false,
intersect_verbatim_both: "@a/**/@c/**/e", "@a/b/b/b/@c/d/d/d/e" => true,
intersect_verbatim_paths: "@a/**/e", "@a/b/b/d/d/d/e" => true,
intersect_verbatim_block: "@a/**/e", "@a/b/b/@c/b/d/d/d/e" => false,
intersect_verbatim_star_no: "@a/*", "@a/@b" => false,
intersect_verbatim_dstar_no: "@a/**", "@a/@b" => false,
intersect_verbatim_dstar_yes: "@a/**/@b", "@a/@b" => true,
intersect_verbatim_prefix_dstar: "@a/@b/**", "@a/@b" => true,
intersect_verbatim_complex_1: "@a/**/@c/**/@b", "@a/**/@c/@b" => true,
intersect_verbatim_complex_2: "@a/**/@c/**/@b", "@a/@c/**/@b" => true,
intersect_verbatim_complex_3: "@a/**/@c/@b", "@a/@c/**/@b" => true,
intersect_verbatim_no_subset: "@a/**/@b", "@a/**/@c/**/@b" => false,
}
}