git.delta.rocks / jrsonnet / refs/commits / 5585b94101d8

1use std::{2	cell::RefCell,3	cmp::Ordering,4	fmt::{self, Debug, Display},5	mem::replace,6	num::NonZeroU32,7	ops::Deref,8	rc::Rc,9};1011use jrsonnet_gcmodule::{Acyclic, Cc, Trace, TraceBox};12use jrsonnet_interner::IStr;13pub use jrsonnet_macros::Thunk;14use jrsonnet_types::ValType;15use rustc_hash::FxHashMap;16use thiserror::Error;1718pub use crate::arr::{ArrValue, ArrayLike};19use crate::{20	bail,21	error::{Error, ErrorKind::*},22	function::FuncVal,23	gc::WithCapacityExt as _,24	manifest::{ManifestFormat, ToStringFormat},25	typed::{BoundedUsize, MAX_SAFE_INTEGER, MIN_SAFE_INTEGER},26	ObjValue, Result, Unbound, WeakObjValue,27};2829pub trait ThunkValue: Trace {30	type Output;31	fn get(self: Box<Self>) -> Result<Self::Output>;32}3334#[derive(Trace)]35pub struct ThunkValueClosure<D: Trace, O: 'static> {36	env: D,37	// Carries no data, as it is not a real closure, all the38	// captured environment is stored in `env` field.39	#[trace(skip)]40	closure: fn(D) -> Result<O>,41}42impl<D: Trace, O: 'static> ThunkValueClosure<D, O> {43	pub fn new(env: D, closure: fn(D) -> Result<O>) -> Self {44		Self { env, closure }45	}46}47impl<D: Trace, O: 'static> ThunkValue for ThunkValueClosure<D, O> {48	type Output = O;4950	fn get(self: Box<Self>) -> Result<Self::Output> {51		(self.closure)(self.env)52	}53}5455#[derive(Trace)]56enum ThunkInner<T: Trace> {57	Computed(T),58	Errored(Error),59	Waiting(TraceBox<dyn ThunkValue<Output = T>>),60	Pending,61}6263/// Lazily evaluated value64#[allow(clippy::module_name_repetitions)]65#[derive(Clone, Trace)]66pub struct Thunk<T: Trace>(Cc<RefCell<ThunkInner<T>>>);6768impl<T: Trace> Thunk<T> {69	pub fn evaluated(val: T) -> Self {70		Self(Cc::new(RefCell::new(ThunkInner::Computed(val))))71	}72	pub fn new(f: impl ThunkValue<Output = T> + 'static) -> Self {73		Self(Cc::new(RefCell::new(ThunkInner::Waiting(TraceBox(74			Box::new(f),75		)))))76	}77	pub fn errored(e: Error) -> Self {78		Self(Cc::new(RefCell::new(ThunkInner::Errored(e))))79	}80	pub fn result(res: Result<T, Error>) -> Self {81		match res {82			Ok(o) => Self::evaluated(o),83			Err(e) => Self::errored(e),84		}85	}86}8788impl<T> Thunk<T>89where90	T: Clone + Trace,91{92	pub fn force(&self) -> Result<()> {93		self.evaluate()?;94		Ok(())95	}9697	/// Evaluate thunk, or return cached value98	///99	/// # Errors100	///101	/// - Lazy value evaluation returned error102	/// - This method was called during inner value evaluation103	pub fn evaluate(&self) -> Result<T> {104		match &*self.0.borrow() {105			ThunkInner::Computed(v) => return Ok(v.clone()),106			ThunkInner::Errored(e) => return Err(e.clone()),107			ThunkInner::Pending => return Err(InfiniteRecursionDetected.into()),108			ThunkInner::Waiting(..) => (),109		};110		let ThunkInner::Waiting(value) = replace(&mut *self.0.borrow_mut(), ThunkInner::Pending)111		else {112			unreachable!();113		};114		let new_value = match value.0.get() {115			Ok(v) => v,116			Err(e) => {117				*self.0.borrow_mut() = ThunkInner::Errored(e.clone());118				return Err(e);119			}120		};121		*self.0.borrow_mut() = ThunkInner::Computed(new_value.clone());122		Ok(new_value)123	}124}125126pub trait ThunkMapper<Input>: Trace {127	type Output;128	fn map(self, from: Input) -> Result<Self::Output>;129}130impl<Input> Thunk<Input>131where132	Input: Trace + Clone,133{134	pub fn map<M>(self, mapper: M) -> Thunk<M::Output>135	where136		M: ThunkMapper<Input>,137		M::Output: Trace,138	{139		let inner = self;140		Thunk!(move || {141			let value = inner.evaluate()?;142			let mapped = mapper.map(value)?;143			Ok(mapped)144		})145	}146}147148impl<T: Trace> From<Result<T>> for Thunk<T> {149	fn from(value: Result<T>) -> Self {150		match value {151			Ok(o) => Self::evaluated(o),152			Err(e) => Self::errored(e),153		}154	}155}156impl<T, V: Trace> From<T> for Thunk<V>157where158	T: ThunkValue<Output = V>,159{160	fn from(value: T) -> Self {161		Self::new(value)162	}163}164165impl<T: Trace + Default> Default for Thunk<T> {166	fn default() -> Self {167		Self::evaluated(T::default())168	}169}170171type CacheKey = (Option<WeakObjValue>, Option<WeakObjValue>);172173#[derive(Trace, Clone)]174pub struct CachedUnbound<I, T>175where176	I: Unbound<Bound = T>,177	T: Trace,178{179	cache: Cc<RefCell<FxHashMap<CacheKey, T>>>,180	value: I,181}182impl<I: Unbound<Bound = T>, T: Trace> CachedUnbound<I, T> {183	pub fn new(value: I) -> Self {184		Self {185			cache: Cc::new(RefCell::new(FxHashMap::new())),186			value,187		}188	}189}190impl<I: Unbound<Bound = T>, T: Clone + Trace> Unbound for CachedUnbound<I, T> {191	type Bound = T;192	fn bind(&self, sup: Option<ObjValue>, this: Option<ObjValue>) -> Result<T> {193		let cache_key = (194			sup.as_ref().map(|s| s.clone().downgrade()),195			this.as_ref().map(|t| t.clone().downgrade()),196		);197		{198			if let Some(t) = self.cache.borrow().get(&cache_key) {199				return Ok(t.clone());200			}201		}202		let bound = self.value.bind(sup, this)?;203204		{205			let mut cache = self.cache.borrow_mut();206			cache.insert(cache_key, bound.clone());207		}208209		Ok(bound)210	}211}212213impl<T: Debug + Trace> Debug for Thunk<T> {214	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {215		write!(f, "Lazy")216	}217}218impl<T: Trace> PartialEq for Thunk<T> {219	fn eq(&self, other: &Self) -> bool {220		Cc::ptr_eq(&self.0, &other.0)221	}222}223224/// Represents a Jsonnet value, which can be sliced or indexed (string or array).225#[allow(clippy::module_name_repetitions)]226pub enum IndexableVal {227	/// String.228	Str(IStr),229	/// Array.230	Arr(ArrValue),231}232impl IndexableVal {233	pub fn is_empty(&self) -> bool {234		match self {235			Self::Str(s) => s.is_empty(),236			Self::Arr(s) => s.is_empty(),237		}238	}239240	pub fn to_array(self) -> ArrValue {241		match self {242			Self::Str(s) => ArrValue::chars(s.chars()),243			Self::Arr(arr) => arr,244		}245	}246	/// Slice the value.247	///248	/// # Implementation249	///250	/// For strings, will create a copy of specified interval.251	///252	/// For arrays, nothing will be copied on this call, instead [`ArrValue::Slice`] view will be returned.253	pub fn slice(254		self,255		index: Option<i32>,256		end: Option<i32>,257		step: Option<BoundedUsize<1, { i32::MAX as usize }>>,258	) -> Result<Self> {259		match &self {260			Self::Str(s) => {261				let mut computed_len = None;262				let mut get_len = || {263					computed_len.map_or_else(264						|| {265							let len = s.chars().count();266							let _ = computed_len.insert(len);267							len268						},269						|len| len,270					)271				};272				let mut get_idx = |pos: Option<i32>, default| {273					match pos {274						Some(v) if v < 0 => get_len().saturating_sub((-v) as usize),275						// No need to clamp, as iterator interface is used276						Some(v) => v as usize,277						None => default,278					}279				};280281				let index = get_idx(index, 0);282				let end = get_idx(end, usize::MAX);283				let step = step.as_deref().copied().unwrap_or(1);284285				if index >= end {286					return Ok(Self::Str("".into()));287				}288289				Ok(Self::Str(290					(s.chars()291						.skip(index)292						.take(end - index)293						.step_by(step)294						.collect::<String>())295					.into(),296				))297			}298			Self::Arr(arr) => Ok(Self::Arr(arr.clone().slice(299				index,300				end,301				step.map(|v| NonZeroU32::new(v.value() as u32).expect("bounded != 0")),302			))),303		}304	}305}306307#[derive(Debug, Clone, Acyclic)]308pub enum StrValue {309	Flat(IStr),310	Tree(Rc<(StrValue, StrValue, usize)>),311}312impl StrValue {313	pub fn concat(a: Self, b: Self) -> Self {314		// TODO: benchmark for an optimal value, currently just a arbitrary choice315		const STRING_EXTEND_THRESHOLD: usize = 100;316317		if a.is_empty() {318			b319		} else if b.is_empty() {320			a321		} else if a.len() + b.len() < STRING_EXTEND_THRESHOLD {322			Self::Flat(format!("{a}{b}").into())323		} else {324			let len = a.len() + b.len();325			Self::Tree(Rc::new((a, b, len)))326		}327	}328	pub fn into_flat(self) -> IStr {329		#[cold]330		fn write_buf(s: &StrValue, out: &mut String) {331			match s {332				StrValue::Flat(f) => out.push_str(f),333				StrValue::Tree(t) => {334					write_buf(&t.0, out);335					write_buf(&t.1, out);336				}337			}338		}339		match self {340			Self::Flat(f) => f,341			Self::Tree(_) => {342				let mut buf = String::with_capacity(self.len());343				write_buf(&self, &mut buf);344				buf.into()345			}346		}347	}348	pub fn len(&self) -> usize {349		match self {350			Self::Flat(v) => v.len(),351			Self::Tree(t) => t.2,352		}353	}354	pub fn is_empty(&self) -> bool {355		match self {356			Self::Flat(v) => v.is_empty(),357			// Can't create non-flat empty string358			Self::Tree(_) => false,359		}360	}361}362impl<T> From<T> for StrValue363where364	IStr: From<T>,365{366	fn from(value: T) -> Self {367		Self::Flat(IStr::from(value))368	}369}370impl Display for StrValue {371	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {372		match self {373			Self::Flat(v) => write!(f, "{v}"),374			Self::Tree(t) => {375				write!(f, "{}", t.0)?;376				write!(f, "{}", t.1)377			}378		}379	}380}381impl PartialEq for StrValue {382	// False positive, into_flat returns not StrValue, but IStr, thus no infinite recursion here.383	#[allow(clippy::unconditional_recursion)]384	fn eq(&self, other: &Self) -> bool {385		let a = self.clone().into_flat();386		let b = other.clone().into_flat();387		a == b388	}389}390impl Eq for StrValue {}391impl PartialOrd for StrValue {392	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {393		Some(self.cmp(other))394	}395}396impl Ord for StrValue {397	fn cmp(&self, other: &Self) -> Ordering {398		let a = self.clone().into_flat();399		let b = other.clone().into_flat();400		a.cmp(&b)401	}402}403404/// Represents jsonnet number405/// Jsonnet numbers are finite f64, with NaNs disallowed406#[derive(Trace, Clone, Copy)]407#[repr(transparent)]408pub struct NumValue(f64);409impl NumValue {410	/// Creates a [`NumValue`], if value is finite and not NaN411	pub fn new(v: f64) -> Option<Self> {412		if !v.is_finite() {413			return None;414		}415		Some(Self(v))416	}417	#[inline]418	pub const fn get(&self) -> f64 {419		self.0420	}421	pub(crate) fn truncate_for_bitwise(&self) -> Result<i64> {422		if self.0 < MIN_SAFE_INTEGER || self.0 > dbg!(MAX_SAFE_INTEGER) {423			bail!("numberic value outside of safe integer range for bitwise operation");424		}425		Ok(self.0 as i64)426	}427}428impl PartialEq for NumValue {429	fn eq(&self, other: &Self) -> bool {430		self.0 == other.0431	}432}433impl Eq for NumValue {}434impl Ord for NumValue {435	#[inline]436	fn cmp(&self, other: &Self) -> Ordering {437		// Can't use `total_cmp`: its behavior for `-0` and `0`438		// is not following wanted.439		unsafe { self.0.partial_cmp(&other.0).unwrap_unchecked() }440	}441}442impl PartialOrd for NumValue {443	#[inline]444	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {445		Some(self.cmp(other))446	}447}448impl Debug for NumValue {449	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {450		Debug::fmt(&self.0, f)451	}452}453impl Display for NumValue {454	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {455		Display::fmt(&self.0, f)456	}457}458impl Deref for NumValue {459	type Target = f64;460461	#[inline]462	fn deref(&self) -> &Self::Target {463		&self.0464	}465}466macro_rules! impl_num {467	($($ty:ty),+) => {$(468		impl From<$ty> for NumValue {469			#[inline]470			fn from(value: $ty) -> Self {471				Self(value.into())472			}473		}474	)+};475}476impl_num!(i8, u8, i16, u16, i32, u32);477478#[derive(Clone, Copy, Debug, Error, Trace)]479pub enum ConvertNumValueError {480	#[error("overflow")]481	Overflow,482	#[error("underflow")]483	Underflow,484	#[error("non-finite")]485	NonFinite,486}487impl From<ConvertNumValueError> for Error {488	fn from(e: ConvertNumValueError) -> Self {489		Self::new(e.into())490	}491}492493macro_rules! impl_try_num {494	($($ty:ty),+) => {$(495		impl TryFrom<$ty> for NumValue {496			type Error = ConvertNumValueError;497			#[inline]498			fn try_from(value: $ty) -> Result<Self, ConvertNumValueError> {499				let value = value as f64;500				if value < MIN_SAFE_INTEGER {501					return Err(ConvertNumValueError::Underflow)502				} else if value > MAX_SAFE_INTEGER {503					return Err(ConvertNumValueError::Overflow)504				}505				// Number is finite.506				Ok(Self(value))507			}508		}509	)+};510}511impl_try_num!(usize, isize, i64, u64);512513impl TryFrom<f64> for NumValue {514	type Error = ConvertNumValueError;515516	#[inline]517	fn try_from(value: f64) -> Result<Self, Self::Error> {518		Self::new(value).ok_or(ConvertNumValueError::NonFinite)519	}520}521impl TryFrom<f32> for NumValue {522	type Error = ConvertNumValueError;523524	#[inline]525	fn try_from(value: f32) -> Result<Self, Self::Error> {526		Self::new(f64::from(value)).ok_or(ConvertNumValueError::NonFinite)527	}528}529530/// Represents any valid Jsonnet value.531#[derive(Debug, Clone, Trace, Default)]532pub enum Val {533	/// Represents a Jsonnet boolean.534	Bool(bool),535	/// Represents a Jsonnet null value.536	#[default]537	Null,538	/// Represents a Jsonnet string.539	Str(StrValue),540	/// Represents a Jsonnet number.541	/// Should be finite, and not NaN542	/// This restriction isn't enforced by enum, as enum field can't be marked as private543	Num(NumValue),544	/// Experimental bigint545	#[cfg(feature = "exp-bigint")]546	BigInt(#[trace(skip)] Box<num_bigint::BigInt>),547	/// Represents a Jsonnet array.548	Arr(ArrValue),549	/// Represents a Jsonnet object.550	Obj(ObjValue),551	/// Represents a Jsonnet function.552	Func(FuncVal),553}554555#[cfg(target_pointer_width = "64")]556static_assertions::assert_eq_size!(Val, [u8; 24]);557558impl From<IndexableVal> for Val {559	fn from(v: IndexableVal) -> Self {560		match v {561			IndexableVal::Str(s) => Self::string(s),562			IndexableVal::Arr(a) => Self::Arr(a),563		}564	}565}566567impl Val {568	pub const fn as_bool(&self) -> Option<bool> {569		match self {570			Self::Bool(v) => Some(*v),571			_ => None,572		}573	}574	pub const fn as_null(&self) -> Option<()> {575		match self {576			Self::Null => Some(()),577			_ => None,578		}579	}580	pub fn as_str(&self) -> Option<IStr> {581		match self {582			Self::Str(s) => Some(s.clone().into_flat()),583			_ => None,584		}585	}586	pub const fn as_num(&self) -> Option<f64> {587		match self {588			Self::Num(n) => Some(n.get()),589			_ => None,590		}591	}592	#[cfg(feature = "exp-bigint")]593	pub fn as_bigint(&self) -> Option<num_bigint::BigInt> {594		match self {595			Self::BigInt(n) => Some(*n.clone()),596			_ => None,597		}598	}599	pub fn as_arr(&self) -> Option<ArrValue> {600		match self {601			Self::Arr(a) => Some(a.clone()),602			_ => None,603		}604	}605	pub fn as_obj(&self) -> Option<ObjValue> {606		match self {607			Self::Obj(o) => Some(o.clone()),608			_ => None,609		}610	}611	pub fn as_func(&self) -> Option<FuncVal> {612		match self {613			Self::Func(f) => Some(f.clone()),614			_ => None,615		}616	}617618	pub const fn value_type(&self) -> ValType {619		match self {620			Self::Str(..) => ValType::Str,621			Self::Num(..) => ValType::Num,622			#[cfg(feature = "exp-bigint")]623			Self::BigInt(..) => ValType::BigInt,624			Self::Arr(..) => ValType::Arr,625			Self::Obj(..) => ValType::Obj,626			Self::Bool(_) => ValType::Bool,627			Self::Null => ValType::Null,628			Self::Func(..) => ValType::Func,629		}630	}631632	pub fn manifest(&self, format: impl ManifestFormat) -> Result<String> {633		fn manifest_dyn(val: &Val, manifest: &dyn ManifestFormat) -> Result<String> {634			manifest.manifest(val.clone())635		}636		manifest_dyn(self, &format)637	}638639	pub fn to_string(&self) -> Result<IStr> {640		Ok(match self {641			Self::Bool(true) => "true".into(),642			Self::Bool(false) => "false".into(),643			Self::Null => "null".into(),644			Self::Str(s) => s.clone().into_flat(),645			_ => self.manifest(ToStringFormat).map(IStr::from)?,646		})647	}648649	pub fn into_indexable(self) -> Result<IndexableVal> {650		Ok(match self {651			Self::Str(s) => IndexableVal::Str(s.into_flat()),652			Self::Arr(arr) => IndexableVal::Arr(arr),653			_ => bail!(ValueIsNotIndexable(self.value_type())),654		})655	}656657	pub fn function(function: impl Into<FuncVal>) -> Self {658		Self::Func(function.into())659	}660	pub fn string(string: impl Into<StrValue>) -> Self {661		Self::Str(string.into())662	}663	pub fn num(num: impl Into<NumValue>) -> Self {664		Self::Num(num.into())665	}666	pub fn try_num<V, E>(num: V) -> Result<Self, E>667	where668		NumValue: TryFrom<V, Error = E>,669	{670		Ok(Self::Num(num.try_into()?))671	}672}673674impl From<IStr> for Val {675	fn from(value: IStr) -> Self {676		Self::string(value)677	}678}679impl From<String> for Val {680	fn from(value: String) -> Self {681		Self::string(value)682	}683}684impl From<&str> for Val {685	fn from(value: &str) -> Self {686		Self::string(value)687	}688}689impl From<ObjValue> for Val {690	fn from(value: ObjValue) -> Self {691		Self::Obj(value)692	}693}694695const fn is_function_like(val: &Val) -> bool {696	matches!(val, Val::Func(_))697}698699/// Native implementation of `std.primitiveEquals`700pub fn primitive_equals(val_a: &Val, val_b: &Val) -> Result<bool> {701	Ok(match (val_a, val_b) {702		(Val::Bool(a), Val::Bool(b)) => a == b,703		(Val::Null, Val::Null) => true,704		(Val::Str(a), Val::Str(b)) => a == b,705		(Val::Num(a), Val::Num(b)) => (a.get() - b.get()).abs() <= f64::EPSILON,706		#[cfg(feature = "exp-bigint")]707		(Val::BigInt(a), Val::BigInt(b)) => a == b,708		(Val::Arr(_), Val::Arr(_)) => {709			bail!("primitiveEquals operates on primitive types, got array")710		}711		(Val::Obj(_), Val::Obj(_)) => {712			bail!("primitiveEquals operates on primitive types, got object")713		}714		(a, b) if is_function_like(a) && is_function_like(b) => {715			bail!("cannot test equality of functions")716		}717		(_, _) => false,718	})719}720721/// Native implementation of `std.equals`722pub fn equals(val_a: &Val, val_b: &Val) -> Result<bool> {723	if val_a.value_type() != val_b.value_type() {724		return Ok(false);725	}726	match (val_a, val_b) {727		(Val::Arr(a), Val::Arr(b)) => {728			if ArrValue::ptr_eq(a, b) {729				return Ok(true);730			}731			if a.len() != b.len() {732				return Ok(false);733			}734			for (a, b) in a.iter().zip(b.iter()) {735				if !equals(&a?, &b?)? {736					return Ok(false);737				}738			}739			Ok(true)740		}741		(Val::Obj(a), Val::Obj(b)) => {742			if ObjValue::ptr_eq(a, b) {743				return Ok(true);744			}745			let fields = a.fields(746				#[cfg(feature = "exp-preserve-order")]747				false,748			);749			if fields750				!= b.fields(751					#[cfg(feature = "exp-preserve-order")]752					false,753				) {754				return Ok(false);755			}756			for field in fields {757				if !equals(758					&a.get(field.clone())?.expect("field exists"),759					&b.get(field)?.expect("field exists"),760				)? {761					return Ok(false);762				}763			}764			Ok(true)765		}766		(a, b) => Ok(primitive_equals(a, b)?),767	}768}