use super::protocol::{JsonValue, PayloadPredicate, SignalEnvelope, SignalPattern};
const MAX_SEGMENTS: usize = 16;
const MAX_KEYPATH_DEPTH: usize = 8;
const MAX_AST_NODES: usize = 64;
#[must_use]
pub fn validate_pattern(pattern: &SignalPattern) -> bool {
if pattern.kind_glob().is_empty() {
return false;
}
let segments: Vec<&str> = pattern.kind_glob().split('.').collect();
if segments.len() > MAX_SEGMENTS {
return false;
}
let last = segments.len().saturating_sub(1);
for segment in segments.iter().take(last) {
if *segment == "**" {
return false;
}
}
match pattern.payload_predicate() {
None => true,
Some(predicate) => {
count_ast_nodes(predicate) <= MAX_AST_NODES && validate_predicate_structure(predicate)
}
}
}
fn count_ast_nodes(predicate: &PayloadPredicate) -> usize {
match *predicate {
PayloadPredicate::And(ref children) | PayloadPredicate::Or(ref children) => {
children.iter().fold(1_usize, |sum, child| {
sum.saturating_add(count_ast_nodes(child))
})
}
_ => 1,
}
}
fn validate_predicate_structure(predicate: &PayloadPredicate) -> bool {
match *predicate {
PayloadPredicate::Eq { ref keypath, .. }
| PayloadPredicate::Neq { ref keypath, .. }
| PayloadPredicate::In { ref keypath, .. }
| PayloadPredicate::Exists { ref keypath } => keypath_depth(keypath) <= MAX_KEYPATH_DEPTH,
PayloadPredicate::And(ref children) | PayloadPredicate::Or(ref children) => {
children.iter().all(validate_predicate_structure)
}
}
}
fn keypath_depth(keypath: &str) -> usize {
keypath.split('.').filter(|part| !part.is_empty()).count()
}
#[must_use]
pub fn match_pattern(envelope: &SignalEnvelope, pattern: &SignalPattern) -> bool {
if !validate_pattern(pattern) {
return false;
}
if !match_kind_glob(pattern.kind_glob(), envelope.kind()) {
return false;
}
match pattern.payload_predicate() {
None => true,
Some(predicate) => eval_predicate(predicate, envelope.payload()),
}
}
fn match_kind_glob(glob: &str, kind: &str) -> bool {
let glob_segments: Vec<&str> = glob.split('.').collect();
let kind_segments: Vec<&str> = kind.split('.').collect();
if glob_segments.last() == Some(&"**") {
let prefix_len = glob_segments.len().saturating_sub(1);
if kind_segments.len() < prefix_len {
return false;
}
for (index, segment) in glob_segments.iter().take(prefix_len).enumerate() {
let Some(kind_segment) = kind_segments.get(index) else {
return false;
};
if *segment != "*" && segment != kind_segment {
return false;
}
}
return true;
}
if glob_segments.len() != kind_segments.len() {
return false;
}
glob_segments
.iter()
.zip(kind_segments.iter())
.all(|(glob_segment, kind_segment)| *glob_segment == "*" || glob_segment == kind_segment)
}
fn get_at_keypath<'a>(payload: &'a JsonValue, keypath: &str) -> Option<&'a JsonValue> {
let mut current = payload;
for part in keypath.split('.').filter(|part| !part.is_empty()) {
let map = current.object_value()?;
current = map.get(part)?;
}
Some(current)
}
fn eval_predicate(predicate: &PayloadPredicate, payload: &JsonValue) -> bool {
match *predicate {
PayloadPredicate::Eq {
ref keypath,
ref value,
} => match get_at_keypath(payload, keypath) {
Some(found) => json_value_equals(found, value),
None => false,
},
PayloadPredicate::Neq {
ref keypath,
ref value,
} => match get_at_keypath(payload, keypath) {
Some(found) => !json_value_equals(found, value),
None => false,
},
PayloadPredicate::In {
ref keypath,
ref values,
} => match get_at_keypath(payload, keypath) {
Some(found) => values
.iter()
.any(|candidate| json_value_equals(found, candidate)),
None => false,
},
PayloadPredicate::Exists { ref keypath } => get_at_keypath(payload, keypath).is_some(),
PayloadPredicate::And(ref clauses) => {
clauses.iter().all(|clause| eval_predicate(clause, payload))
}
PayloadPredicate::Or(ref clauses) => {
clauses.iter().any(|clause| eval_predicate(clause, payload))
}
}
}
fn json_value_equals(actual: &JsonValue, expected: &JsonValue) -> bool {
match *actual {
JsonValue::Null => matches!(*expected, JsonValue::Null),
JsonValue::Bool(left) => match *expected {
JsonValue::Bool(right) => left == right,
_ => false,
},
JsonValue::Number(left) => match *expected {
JsonValue::Number(right) => left.to_bits() == right.to_bits(),
_ => false,
},
JsonValue::String(ref left) => match *expected {
JsonValue::String(ref right) => left == right,
_ => false,
},
JsonValue::Array(_) | JsonValue::Object(_) => false,
}
}
#[must_use]
pub fn glob_match(pattern: &str, value: &str) -> bool {
if !pattern.contains('*') && !pattern.contains('?') {
return pattern == value;
}
let pattern_chars: Vec<char> = pattern.chars().collect();
let value_chars: Vec<char> = value.chars().collect();
let mut pattern_index = 0_usize;
let mut value_index = 0_usize;
let mut star_index: Option<usize> = None;
let mut match_index = 0_usize;
while value_index < value_chars.len() {
let in_pattern = pattern_chars.get(pattern_index).copied();
if in_pattern == Some('*') {
star_index = Some(pattern_index);
match_index = value_index;
pattern_index = pattern_index.saturating_add(1);
} else if in_pattern == Some('?') || in_pattern == Some(value_chars[value_index]) {
pattern_index = pattern_index.saturating_add(1);
value_index = value_index.saturating_add(1);
} else if let Some(star) = star_index {
pattern_index = star.saturating_add(1);
match_index = match_index.saturating_add(1);
value_index = match_index;
} else {
return false;
}
}
while pattern_chars.get(pattern_index).copied() == Some('*') {
pattern_index = pattern_index.saturating_add(1);
}
pattern_index >= pattern_chars.len()
}
#[cfg(test)]
mod tests {
use super::{glob_match, validate_pattern};
use crate::native_host::protocol::{PayloadPredicate, SignalPattern};
fn glob_only(glob: &str) -> SignalPattern {
SignalPattern::new(String::from(glob), None)
}
#[test]
fn validation_rejects_bad_shapes() -> Result<(), String> {
if validate_pattern(&glob_only("")) {
return Err(String::from("empty glob must be invalid"));
}
if validate_pattern(&glob_only("a.**.b")) {
return Err(String::from("non-trailing ** must be invalid"));
}
let seventeen = (0..17)
.map(|index| format!("s{index}"))
.collect::<Vec<_>>()
.join(".");
if validate_pattern(&glob_only(&seventeen)) {
return Err(String::from("17 segments must be invalid"));
}
let leaves: Vec<PayloadPredicate> = (0..63)
.map(|index| PayloadPredicate::exists(format!("k{index}")))
.collect();
if !validate_pattern(&SignalPattern::new(
String::from("a"),
Some(PayloadPredicate::And(leaves)),
)) {
return Err(String::from("64 nodes must be valid"));
}
let leaves: Vec<PayloadPredicate> = (0..64)
.map(|index| PayloadPredicate::exists(format!("k{index}")))
.collect();
if validate_pattern(&SignalPattern::new(
String::from("a"),
Some(PayloadPredicate::And(leaves)),
)) {
return Err(String::from("65 nodes must be invalid"));
}
let deep = (0..9)
.map(|index| format!("k{index}"))
.collect::<Vec<_>>()
.join(".");
if validate_pattern(&SignalPattern::new(
String::from("a"),
Some(PayloadPredicate::exists(deep)),
)) {
return Err(String::from("depth 9 must be invalid"));
}
let shallow = (0..8)
.map(|index| format!("k{index}"))
.collect::<Vec<_>>()
.join(".");
if !validate_pattern(&SignalPattern::new(
String::from("a"),
Some(PayloadPredicate::exists(shallow)),
)) {
return Err(String::from("depth 8 must be valid"));
}
Ok(())
}
fn assert_glob(pattern: &str, value: &str, want: bool) -> Result<(), String> {
if glob_match(pattern, value) != want {
return Err(format!("glob_match({pattern:?}, {value:?}) != {want}"));
}
Ok(())
}
#[test]
fn governance_globs_match() -> Result<(), String> {
assert_glob("intent.*", "intent.find", true)?;
assert_glob("intent.*", "intent.find.extra", true)?;
assert_glob("intent.*", "other.find", false)?;
assert_glob("*.find", "intent.find", true)?;
assert_glob("forms.?", "forms.x", true)?;
assert_glob("forms.?", "forms.xy", false)?;
assert_glob("*", "anything.at.all", true)?;
assert_glob("a.**.b", "a.x.b", true)?;
assert_glob("a.**.b", "a.b", false)?;
assert_glob("exact", "exact", true)?;
assert_glob("exact", "other", false)?;
Ok(())
}
}