use alloc::{
boxed::Box,
format,
string::{String, ToString},
sync::Arc,
vec::Vec,
};
use core::fmt::{Debug, Display};
#[cfg(feature = "std")]
use std::{
hash::{DefaultHasher, Hash, Hasher},
sync::{
RwLock,
atomic::{AtomicU64, Ordering},
},
};
use crate::{
ast::Parser,
error::{Error, Result},
op::{BinOp, UnaryOp, err_op},
token::Tokenizer,
val::Val,
};
use hashbrown::HashMap;
use hashbrown::HashSet as HbHashSet;
#[cfg(feature = "std")]
use once_cell::sync::Lazy;
#[cfg(feature = "std")]
const MAX_PARSE_CACHE_ENTRIES: usize = 4096;
#[cfg(feature = "std")]
const MAX_CACHED_EXPR_LEN: usize = 4096;
#[cfg(feature = "std")]
const PARSE_CACHE_SHARDS: usize = 16;
#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
Bin(Box<Expr>, BinOp, Box<Expr>),
Unary(UnaryOp, Box<Expr>),
And(Box<Expr>, Box<Expr>),
Or(Box<Expr>, Box<Expr>),
Coalesce(Box<Expr>, Box<Expr>),
Ternary(Box<Expr>, Box<Expr>, Box<Expr>),
At(Vec<Box<Expr>>),
Access(Box<Expr>, Box<Expr>),
Paren(Box<Expr>),
List(Vec<Box<Expr>>),
Map(Vec<(Box<Expr>, Box<Expr>)>),
Val(Val),
}
#[cfg(feature = "std")]
struct ParseCacheShard {
state: RwLock<ParseCacheState>,
}
#[cfg(feature = "std")]
struct ParseCacheState {
entries: HashMap<String, (Arc<Expr>, u64)>,
}
#[cfg(feature = "std")]
static CACHE_CLOCK: AtomicU64 = AtomicU64::new(0);
#[cfg(feature = "std")]
impl ParseCacheState {
fn new() -> Self {
Self {
entries: HashMap::new(),
}
}
fn get(&mut self, expression: &str) -> Option<Arc<Expr>> {
let entry = self.entries.get_mut(expression)?;
entry.1 = CACHE_CLOCK.fetch_add(1, Ordering::Relaxed);
Some(entry.0.clone())
}
fn insert(&mut self, expression: String, expr: Arc<Expr>) {
if self.entries.contains_key(expression.as_str()) {
return;
}
if self.entries.len() >= parse_cache_entries_per_shard() {
self.evict_oldest();
}
let ts = CACHE_CLOCK.fetch_add(1, Ordering::Relaxed);
self.entries.insert(expression, (expr, ts));
}
fn evict_oldest(&mut self) {
if let Some(oldest_key) = self
.entries
.iter()
.min_by_key(|(_, (_, ts))| *ts)
.map(|(k, _)| k.clone())
{
self.entries.remove(&oldest_key);
}
}
}
#[cfg(feature = "std")]
static PARSE_CACHE: Lazy<Box<[ParseCacheShard]>> = Lazy::new(|| {
(0..PARSE_CACHE_SHARDS)
.map(|_| ParseCacheShard {
state: RwLock::new(ParseCacheState::new()),
})
.collect::<Vec<_>>()
.into_boxed_slice()
});
#[cfg(feature = "std")]
#[inline]
const fn parse_cache_entries_per_shard() -> usize {
MAX_PARSE_CACHE_ENTRIES.div_ceil(PARSE_CACHE_SHARDS)
}
#[cfg(feature = "std")]
#[inline]
fn parse_cache_shard_idx(expression: &str) -> usize {
let mut hasher = DefaultHasher::new();
expression.hash(&mut hasher);
(hasher.finish() as usize) % PARSE_CACHE_SHARDS
}
#[cfg(feature = "std")]
#[inline]
fn parse_cache_shard(expression: &str) -> &'static ParseCacheShard {
&PARSE_CACHE[parse_cache_shard_idx(expression)]
}
impl Expr {
pub fn eval(&self, ctx: &Val) -> Result<Val> {
match self {
Expr::Bin(l, op, r) => op.eval(l, r, ctx),
Expr::Unary(op, expr) => op.eval(expr, ctx),
Expr::And(e1, e2) => {
let l = e1.eval(ctx)?;
if let Val::Bool(false) = l {
return Ok(Val::Bool(false));
}
let r = e2.eval(ctx)?;
match (&l, &r) {
(Val::Bool(true), Val::Bool(true)) => Ok(Val::Bool(true)),
(Val::Bool(_), Val::Bool(_)) => Ok(Val::Bool(false)),
_ => err_op(&l, "&&", &r),
}
}
Expr::Or(e1, e2) => {
let l = e1.eval(ctx)?;
if let Val::Bool(true) = l {
return Ok(Val::Bool(true));
}
let r = e2.eval(ctx)?;
match (&l, &r) {
(Val::Bool(_), Val::Bool(true)) => Ok(Val::Bool(true)),
(Val::Bool(_), Val::Bool(_)) => Ok(Val::Bool(false)),
_ => err_op(&l, "||", &r),
}
}
Expr::Coalesce(l, r) => {
let left = l.eval(ctx)?;
if left == Val::Nil { r.eval(ctx) } else { Ok(left) }
}
Expr::Ternary(cond, t, f) => {
let cond_val = cond.eval(ctx)?;
match cond_val {
Val::Bool(true) => t.eval(ctx),
Val::Bool(false) => f.eval(ctx),
_ => Err(Error::Eval(format!("Ternary condition must be bool, got: {cond_val}"))),
}
}
Expr::At(paths) => {
if paths.is_empty() {
return Ok(Val::Nil);
}
let mut val = ctx;
for path in paths {
let tmp;
let key = match &**path {
Expr::Val(v) => v,
_ => {
tmp = path.eval(ctx)?;
&tmp
}
};
val = match val.access(key) {
Some(v) => v,
None => return Ok(Val::Nil),
};
}
Ok(val.clone())
}
Expr::Access(expr, field) => {
let val = expr.eval(ctx)?;
let tmp;
let field_val = match &**field {
Expr::Val(v) => v,
_ => {
tmp = field.eval(ctx)?;
&tmp
}
};
match val.access(field_val) {
Some(v) => Ok(v.clone()),
None => Ok(Val::Nil),
}
}
Expr::List(exprs) => {
let mut values = Vec::with_capacity(exprs.len());
for expr in exprs {
values.push(expr.eval(ctx)?);
}
Ok(Val::List(Arc::new(values)))
}
Expr::Map(pairs) => {
let mut map = hashbrown::HashMap::with_capacity(pairs.len());
for (key_expr, value_expr) in pairs {
let key_val = key_expr.eval(ctx)?;
let value_val = value_expr.eval(ctx)?;
let Some(key_str) = primitive_map_key_to_string(&key_val) else {
return Err(Error::Eval(format!(
"Map key must be a primitive type, got: {:?}",
key_val
)));
};
map.insert(key_str, value_val);
}
Ok(Val::Map(Arc::new(map)))
}
Expr::Paren(expr) => expr.eval(ctx),
Expr::Val(val) => Ok(val.clone()), }
}
pub fn requested_ctx(&self) -> alloc::collections::BTreeSet<String> {
let mut names = HbHashSet::new();
self.collect_ctx_names(&mut names);
names.into_iter().collect()
}
pub fn is_ctx_independent(&self) -> bool {
match self {
Expr::At(_) => false,
Expr::Bin(l, _, r) | Expr::And(l, r) | Expr::Or(l, r) | Expr::Access(l, r) | Expr::Coalesce(l, r) => {
l.is_ctx_independent() && r.is_ctx_independent()
}
Expr::Unary(_, expr) | Expr::Paren(expr) => expr.is_ctx_independent(),
Expr::Ternary(cond, t, f) => cond.is_ctx_independent() && t.is_ctx_independent() && f.is_ctx_independent(),
Expr::List(exprs) => exprs.iter().all(|expr| expr.is_ctx_independent()),
Expr::Map(pairs) => pairs
.iter()
.all(|(key, value)| key.is_ctx_independent() && value.is_ctx_independent()),
Expr::Val(_) => true,
}
}
fn collect_ctx_names(&self, names: &mut HbHashSet<String>) {
match self {
Expr::At(paths) => {
if !paths.is_empty() {
if let Expr::Val(Val::Str(name)) = &*paths[0] {
names.insert(name.as_ref().to_string());
} else {
paths[0].collect_ctx_names(names);
}
for path in &paths[1..] {
match &**path {
Expr::Val(_) => {}
_ => path.collect_ctx_names(names),
}
}
}
}
Expr::Access(expr, field) => {
expr.collect_ctx_names(names);
field.collect_ctx_names(names);
}
Expr::Bin(l, _, r) => {
l.collect_ctx_names(names);
r.collect_ctx_names(names);
}
Expr::Unary(_, expr) => {
expr.collect_ctx_names(names);
}
Expr::And(l, r) | Expr::Or(l, r) | Expr::Coalesce(l, r) => {
l.collect_ctx_names(names);
r.collect_ctx_names(names);
}
Expr::Ternary(cond, t, f) => {
cond.collect_ctx_names(names);
t.collect_ctx_names(names);
f.collect_ctx_names(names);
}
Expr::List(exprs) => {
for expr in exprs {
expr.collect_ctx_names(names);
}
}
Expr::Map(pairs) => {
for (key, value) in pairs {
key.collect_ctx_names(names);
value.collect_ctx_names(names);
}
}
Expr::Paren(expr) => {
expr.collect_ctx_names(names);
}
Expr::Val(_) => {}
}
}
#[cfg(feature = "std")]
pub fn parse_cached(expression: &str) -> Result<Expr> {
Ok((*Self::parse_cached_arc(expression)?).clone())
}
#[cfg(feature = "std")]
pub fn parse_cached_arc(expression: &str) -> Result<Arc<Expr>> {
if expression.len() <= MAX_CACHED_EXPR_LEN {
let shard = parse_cache_shard(expression);
if let Some(cached) = shard.state.write().unwrap().get(expression) {
return Ok(cached);
}
}
let tokens = Tokenizer::new(expression)?;
let expr = Parser::new(&tokens).parse()?; let expr = Arc::new(expr);
if expression.len() <= MAX_CACHED_EXPR_LEN {
let shard = parse_cache_shard(expression);
let mut state = shard.state.write().unwrap();
if let Some(cached) = state.get(expression) {
return Ok(cached);
}
state.insert(expression.to_string(), expr.clone());
}
Ok(expr)
}
pub(crate) fn fold_constants(self) -> Expr {
match self {
Expr::Val(_) => self, Expr::Bin(l_box, op, r_box) => {
let left = (*l_box).fold_constants();
let right = (*r_box).fold_constants();
if let (Expr::Val(lval), Expr::Val(rval)) = (&left, &right) {
if op.is_arith() {
let result = match op {
BinOp::Add => (lval as &Val) + (rval as &Val),
BinOp::Sub => (lval as &Val) - (rval as &Val),
BinOp::Mul => (lval as &Val) * (rval as &Val),
BinOp::Div => (lval as &Val) / (rval as &Val),
BinOp::Mod => (lval as &Val) % (rval as &Val),
_ => unreachable!(),
};
if let Ok(result_val) = result {
return Expr::Val(result_val);
}
} else if op.is_cmp() {
if let Ok(res_bool) = op.cmp(lval, rval) {
return Expr::Val(Val::Bool(res_bool));
}
}
}
Expr::Bin(Box::new(left), op, Box::new(right))
}
Expr::Unary(op, expr_box) => {
let inner = (*expr_box).fold_constants();
match (&op, &inner) {
(UnaryOp::Not, Expr::Val(Val::Bool(b))) => {
return Expr::Val(Val::Bool(!*b));
}
(UnaryOp::Neg, Expr::Val(Val::Int(i))) => {
if let Some(neg) = i.checked_neg() {
return Expr::Val(Val::Int(neg));
}
}
(UnaryOp::Neg, Expr::Val(Val::Float(f))) => {
return Expr::Val(Val::Float(-*f));
}
_ => {}
}
Expr::Unary(op, Box::new(inner))
}
Expr::And(e1_box, e2_box) => {
let e1 = (*e1_box).fold_constants();
if let Expr::Val(Val::Bool(false)) = e1 {
return Expr::Val(Val::Bool(false));
}
let e2 = (*e2_box).fold_constants();
if let Expr::Val(Val::Bool(true)) = e1 {
return e2;
}
if let (Expr::Val(Val::Bool(b1)), Expr::Val(Val::Bool(b2))) = (&e1, &e2) {
return Expr::Val(Val::Bool(*b1 && *b2));
}
Expr::And(Box::new(e1), Box::new(e2))
}
Expr::Or(e1_box, e2_box) => {
let e1 = (*e1_box).fold_constants();
if let Expr::Val(Val::Bool(true)) = e1 {
return Expr::Val(Val::Bool(true));
}
let e2 = (*e2_box).fold_constants();
if let Expr::Val(Val::Bool(false)) = e1 {
return e2;
}
if let (Expr::Val(Val::Bool(b1)), Expr::Val(Val::Bool(b2))) = (&e1, &e2) {
return Expr::Val(Val::Bool(*b1 || *b2));
}
Expr::Or(Box::new(e1), Box::new(e2))
}
Expr::At(paths) => {
let folded_paths = paths.into_iter().map(|p| Box::new(p.fold_constants())).collect();
Expr::At(folded_paths)
}
Expr::Access(base_box, field_box) => {
let base = (*base_box).fold_constants();
let field = (*field_box).fold_constants();
if let (Expr::Val(base_val), Expr::Val(field_val)) = (&base, &field) {
if let Some(res_val) = base_val.access(field_val) {
return Expr::Val(res_val.clone());
} else {
return Expr::Val(Val::Nil);
}
}
Expr::Access(Box::new(base), Box::new(field))
}
Expr::List(exprs) => {
let mut folded_elems = Vec::with_capacity(exprs.len());
let mut const_vals = Vec::with_capacity(exprs.len());
let mut all_const = true;
for expr in exprs {
let folded = expr.fold_constants();
if let Expr::Val(v) = &folded {
if all_const {
const_vals.push(v.clone());
}
} else {
all_const = false;
}
folded_elems.push(folded);
}
if all_const {
return Expr::Val(Val::List(Arc::new(const_vals)));
}
Expr::List(folded_elems.into_iter().map(Box::new).collect())
}
Expr::Map(pairs) => {
let mut folded_pairs = Vec::with_capacity(pairs.len());
let mut const_map = HashMap::with_capacity(pairs.len());
let mut all_const = true;
for (k, v) in pairs {
let key = k.fold_constants();
let value = v.fold_constants();
if let (Expr::Val(k_val), Expr::Val(v_val)) = (&key, &value) {
if all_const {
if let Some(key_str) = primitive_map_key_to_string(k_val) {
const_map.insert(key_str, v_val.clone());
} else {
all_const = false;
}
}
} else {
all_const = false;
}
folded_pairs.push((Box::new(key), Box::new(value)));
}
if all_const {
return Expr::Val(Val::Map(Arc::new(const_map)));
}
Expr::Map(folded_pairs)
}
Expr::Paren(expr_box) => {
Expr::Paren(Box::new((*expr_box).fold_constants()))
}
Expr::Coalesce(l_box, r_box) => {
let left = (*l_box).fold_constants();
match &left {
Expr::Val(Val::Nil) => return (*r_box).fold_constants(),
Expr::Val(_) => return left,
_ => {}
}
let right = (*r_box).fold_constants();
Expr::Coalesce(Box::new(left), Box::new(right))
}
Expr::Ternary(cond_box, t_box, f_box) => {
let cond = (*cond_box).fold_constants();
match &cond {
Expr::Val(Val::Bool(true)) => return (*t_box).fold_constants(),
Expr::Val(Val::Bool(false)) => return (*f_box).fold_constants(),
_ => {}
}
let t = (*t_box).fold_constants();
let f = (*f_box).fold_constants();
Expr::Ternary(Box::new(cond), Box::new(t), Box::new(f))
}
}
}
}
impl TryInto<Val> for &Expr {
type Error = crate::error::Error;
fn try_into(self) -> Result<Val> {
match self {
Expr::Val(val) => Ok(val.clone()), _ => {
let msg = format!("Can't convert Expr::{:?} to Val", self);
Err(crate::error::Error::Eval(msg))
}
}
}
}
fn primitive_map_key_to_string(value: &Val) -> Option<String> {
match value {
Val::Str(s) => Some(s.as_ref().to_string()),
Val::Int(i) => Some(i.to_string()),
Val::Float(f) => Some(f.to_string()),
Val::Bool(b) => Some(b.to_string()),
_ => None,
}
}
fn into_expr<S: AsRef<str>>(s: S) -> Result<Expr> {
let tokens = Tokenizer::new(s.as_ref())?;
let expr = Parser::new(&tokens).parse()?;
Ok(expr)
}
impl TryFrom<&str> for Expr {
type Error = crate::error::Error;
fn try_from(value: &str) -> core::result::Result<Self, Self::Error> {
into_expr(value)
}
}
impl TryFrom<String> for Expr {
type Error = crate::error::Error;
fn try_from(value: String) -> core::result::Result<Self, Self::Error> {
into_expr(value)
}
}
impl Display for Expr {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Expr::Bin(left, op, right) => write!(f, "{left} {op:?} {right}"),
Expr::Unary(op, expr) => write!(f, "{op:?}{expr}"),
Expr::And(left, right) => write!(f, "{left} && {right}"),
Expr::Or(left, right) => write!(f, "{left} || {right}"),
Expr::Coalesce(left, right) => write!(f, "{left} ?? {right}"),
Expr::Ternary(cond, t, fa) => write!(f, "{cond} ? {t} : {fa}"),
Expr::At(paths) => {
let paths: Vec<String> = paths.iter().map(|p| p.to_string()).collect();
write!(f, "@{}", paths.join("."))
}
Expr::Access(expr, field) => write!(f, "{}.{}", expr, field),
Expr::List(exprs) => {
let exprs: Vec<String> = exprs.iter().map(|e| e.to_string()).collect();
write!(f, "[{}]", exprs.join(", "))
}
Expr::Map(pairs) => {
let pairs: Vec<String> = pairs.iter().map(|(k, v)| format!("{}: {}", k, v)).collect();
write!(f, "{{{}}}", pairs.join(", "))
}
Expr::Paren(expr) => write!(f, "{expr}"),
Expr::Val(val) => write!(f, "{}", val),
}
}
}
impl From<Val> for Expr {
fn from(val: Val) -> Self {
Expr::Val(val)
}
}
#[cfg(test)]
pub(crate) fn reset_parse_cache_for_tests() {
for shard in PARSE_CACHE.iter() {
let mut state = shard.state.write().unwrap();
state.entries.clear();
}
}
#[cfg(test)]
pub(crate) fn parse_cache_shard_idx_for_tests(expression: &str) -> usize {
parse_cache_shard_idx(expression)
}
#[cfg(test)]
pub(crate) fn parse_cache_entry_count_for_tests() -> usize {
PARSE_CACHE
.iter()
.map(|shard| shard.state.read().unwrap().entries.len())
.sum()
}
#[cfg(test)]
pub(crate) const fn parse_cache_entries_per_shard_for_tests() -> usize {
parse_cache_entries_per_shard()
}
#[cfg(test)]
pub(crate) const fn parse_cache_shard_count_for_tests() -> usize {
PARSE_CACHE_SHARDS
}