1use std::{cell::RefCell, fmt::Debug, rc::Rc};23use jrsonnet_gcmodule::{Cc, Trace};4use jrsonnet_interner::{IBytes, IStr};5use jrsonnet_types::ValType;67use crate::{8 error::{Error::*, LocError},9 function::FuncVal,10 gc::{GcHashMap, TraceBox},11 stdlib::manifest::{12 manifest_json_ex, manifest_yaml_ex, ManifestJsonOptions, ManifestType, ManifestYamlOptions,13 },14 throw,15 typed::BoundedUsize,16 ObjValue, Result, State, Unbound, WeakObjValue,17};1819pub trait ThunkValue: Trace {20 type Output;21 fn get(self: Box<Self>, s: State) -> Result<Self::Output>;22}2324#[derive(Trace)]25enum ThunkInner<T: Trace> {26 Computed(T),27 Errored(LocError),28 Waiting(TraceBox<dyn ThunkValue<Output = T>>),29 Pending,30}3132#[allow(clippy::module_name_repetitions)]33#[derive(Clone, Trace)]34pub struct Thunk<T: Trace>(Cc<RefCell<ThunkInner<T>>>);3536impl<T> Thunk<T>37where38 T: Clone + Trace,39{40 pub fn new(f: TraceBox<dyn ThunkValue<Output = T>>) -> Self {41 Self(Cc::new(RefCell::new(ThunkInner::Waiting(f))))42 }43 pub fn evaluated(val: T) -> Self {44 Self(Cc::new(RefCell::new(ThunkInner::Computed(val))))45 }46 pub fn force(&self, s: State) -> Result<()> {47 self.evaluate(s)?;48 Ok(())49 }50 pub fn evaluate(&self, s: State) -> Result<T> {51 match &*self.0.borrow() {52 ThunkInner::Computed(v) => return Ok(v.clone()),53 ThunkInner::Errored(e) => return Err(e.clone()),54 ThunkInner::Pending => return Err(InfiniteRecursionDetected.into()),55 ThunkInner::Waiting(..) => (),56 };57 let value = if let ThunkInner::Waiting(value) =58 std::mem::replace(&mut *self.0.borrow_mut(), ThunkInner::Pending)59 {60 value61 } else {62 unreachable!()63 };64 let new_value = match value.0.get(s) {65 Ok(v) => v,66 Err(e) => {67 *self.0.borrow_mut() = ThunkInner::Errored(e.clone());68 return Err(e);69 }70 };71 *self.0.borrow_mut() = ThunkInner::Computed(new_value.clone());72 Ok(new_value)73 }74}7576type CacheKey = (Option<WeakObjValue>, Option<WeakObjValue>);7778#[derive(Trace, Clone)]79pub struct CachedUnbound<I, T>80where81 I: Unbound<Bound = T>,82 T: Trace,83{84 cache: Cc<RefCell<GcHashMap<CacheKey, T>>>,85 value: I,86}87impl<I: Unbound<Bound = T>, T: Trace> CachedUnbound<I, T> {88 pub fn new(value: I) -> Self {89 Self {90 cache: Cc::new(RefCell::new(GcHashMap::new())),91 value,92 }93 }94}95impl<I: Unbound<Bound = T>, T: Clone + Trace> Unbound for CachedUnbound<I, T> {96 type Bound = T;97 fn bind(&self, s: State, sup: Option<ObjValue>, this: Option<ObjValue>) -> Result<T> {98 let cache_key = (99 sup.as_ref().map(|s| s.clone().downgrade()),100 this.as_ref().map(|t| t.clone().downgrade()),101 );102 {103 if let Some(t) = self.cache.borrow().get(&cache_key) {104 return Ok(t.clone());105 }106 }107 let bound = self.value.bind(s, sup, this)?;108109 {110 let mut cache = self.cache.borrow_mut();111 cache.insert(cache_key, bound.clone());112 }113114 Ok(bound)115 }116}117118impl<T: Debug + Trace> Debug for Thunk<T> {119 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {120 write!(f, "Lazy")121 }122}123impl<T: Trace> PartialEq for Thunk<T> {124 fn eq(&self, other: &Self) -> bool {125 Cc::ptr_eq(&self.0, &other.0)126 }127}128129#[derive(Clone)]130pub enum ManifestFormat {131 YamlStream(Box<ManifestFormat>),132 Yaml {133 padding: usize,134 #[cfg(feature = "exp-preserve-order")]135 preserve_order: bool,136 },137 Json {138 padding: usize,139 #[cfg(feature = "exp-preserve-order")]140 preserve_order: bool,141 },142 ToString,143 String,144}145impl ManifestFormat {146 #[cfg(feature = "exp-preserve-order")]147 fn preserve_order(&self) -> bool {148 match self {149 ManifestFormat::YamlStream(s) => s.preserve_order(),150 ManifestFormat::Yaml { preserve_order, .. } => *preserve_order,151 ManifestFormat::Json { preserve_order, .. } => *preserve_order,152 ManifestFormat::ToString => false,153 ManifestFormat::String => false,154 }155 }156}157158#[derive(Debug, Clone, Trace)]159pub struct Slice {160 pub(crate) inner: ArrValue,161 pub(crate) from: u32,162 pub(crate) to: u32,163 pub(crate) step: u32,164}165impl Slice {166 const fn from(&self) -> usize {167 self.from as usize168 }169 const fn to(&self) -> usize {170 self.to as usize171 }172 const fn step(&self) -> usize {173 self.step as usize174 }175 const fn len(&self) -> usize {176 177 let diff = self.to() - self.from();178 let rem = diff % self.step();179 let div = diff / self.step();180181 if rem == 0 {182 div183 } else {184 div + 1185 }186 }187}188189#[derive(Debug, Clone, Trace)]190191#[trace(tracking(force))]192pub enum ArrValue {193 Bytes(#[trace(skip)] IBytes),194 Lazy(Cc<Vec<Thunk<Val>>>),195 Eager(Cc<Vec<Val>>),196 Extended(Box<(Self, Self)>),197 Range(i32, i32),198 Slice(Box<Slice>),199 Reversed(Box<Self>),200}201202#[cfg(target_pointer_width = "64")]203static_assertions::assert_eq_size!(ArrValue, [u8; 16]);204205impl ArrValue {206 pub fn new_eager() -> Self {207 Self::Eager(Cc::new(Vec::new()))208 }209 pub fn empty() -> Self {210 Self::new_range(0, 0)211 }212213 214 215 #[inline]216 pub fn new_range(a: i32, b: i32) -> Self {217 assert!(a <= b);218 Self::Range(a, b)219 }220221 222 223 #[must_use]224 pub fn slice(self, from: Option<usize>, to: Option<usize>, step: Option<usize>) -> Self {225 let len = self.len();226 let from = from.unwrap_or(0);227 let to = to.unwrap_or(len).min(len);228 let step = step.unwrap_or(1);229 assert!(from < to);230 assert!(step > 0);231232 Self::Slice(Box::new(Slice {233 inner: self,234 from: from as u32,235 to: to as u32,236 step: step as u32,237 }))238 }239240 pub fn len(&self) -> usize {241 match self {242 Self::Bytes(i) => i.len(),243 Self::Lazy(l) => l.len(),244 Self::Eager(e) => e.len(),245 Self::Extended(v) => v.0.len() + v.1.len(),246 Self::Range(a, b) => a.abs_diff(*b) as usize + 1,247 Self::Reversed(i) => i.len(),248 Self::Slice(s) => s.len(),249 }250 }251252 pub fn is_empty(&self) -> bool {253 self.len() == 0254 }255256 pub fn get(&self, s: State, index: usize) -> Result<Option<Val>> {257 match self {258 Self::Bytes(i) => i259 .get(index)260 .map_or(Ok(None), |v| Ok(Some(Val::Num(f64::from(*v))))),261 Self::Lazy(vec) => {262 if let Some(v) = vec.get(index) {263 Ok(Some(v.evaluate(s)?))264 } else {265 Ok(None)266 }267 }268 Self::Eager(vec) => Ok(vec.get(index).cloned()),269 Self::Extended(v) => {270 let a_len = v.0.len();271 if a_len > index {272 v.0.get(s, index)273 } else {274 v.1.get(s, index - a_len)275 }276 }277 Self::Range(a, _) => {278 if index >= self.len() {279 return Ok(None);280 }281 Ok(Some(Val::Num(((*a as isize) + index as isize) as f64)))282 }283 Self::Reversed(v) => {284 let len = v.len();285 if index >= len {286 return Ok(None);287 }288 v.get(s, len - index - 1)289 }290 Self::Slice(v) => {291 let index = v.from() + index * v.step();292 if index >= v.to() {293 return Ok(None);294 }295 v.inner.get(s, index)296 }297 }298 }299300 pub fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {301 match self {302 Self::Bytes(i) => i303 .get(index)304 .map(|b| Thunk::evaluated(Val::Num(f64::from(*b)))),305 Self::Lazy(vec) => vec.get(index).cloned(),306 Self::Eager(vec) => vec.get(index).cloned().map(Thunk::evaluated),307 Self::Extended(v) => {308 let a_len = v.0.len();309 if a_len > index {310 v.0.get_lazy(index)311 } else {312 v.1.get_lazy(index - a_len)313 }314 }315 Self::Range(a, _) => {316 if index >= self.len() {317 return None;318 }319 Some(Thunk::evaluated(Val::Num(320 ((*a as isize) + index as isize) as f64,321 )))322 }323 Self::Reversed(v) => {324 let len = v.len();325 if index >= len {326 return None;327 }328 v.get_lazy(len - index - 1)329 }330 Self::Slice(s) => {331 let index = s.from() + index * s.step();332 if index >= s.to() {333 return None;334 }335 s.inner.get_lazy(index)336 }337 }338 }339340 pub fn evaluated(&self, s: State) -> Result<Cc<Vec<Val>>> {341 Ok(match self {342 Self::Bytes(i) => {343 let mut out = Vec::with_capacity(i.len());344 for v in i.iter() {345 out.push(Val::Num(f64::from(*v)));346 }347 Cc::new(out)348 }349 Self::Lazy(vec) => {350 let mut out = Vec::with_capacity(vec.len());351 for item in vec.iter() {352 out.push(item.evaluate(s.clone())?);353 }354 Cc::new(out)355 }356 Self::Eager(vec) => vec.clone(),357 Self::Extended(_v) => {358 let mut out = Vec::with_capacity(self.len());359 for item in self.iter(s) {360 out.push(item?);361 }362 Cc::new(out)363 }364 Self::Range(a, b) => {365 let mut out = Vec::with_capacity(self.len());366 for i in *a..*b {367 out.push(Val::Num(f64::from(i)));368 }369 Cc::new(out)370 }371 Self::Reversed(r) => {372 let mut r = r.evaluated(s)?;373 Cc::update_with(&mut r, |v| v.reverse());374 r375 }376 Self::Slice(v) => {377 let mut out = Vec::with_capacity(v.inner.len());378 for v in v379 .inner380 .iter_lazy()381 .skip(v.from())382 .take(v.to() - v.from())383 .step_by(v.step())384 {385 out.push(v.evaluate(s.clone())?);386 }387 Cc::new(out)388 }389 })390 }391392 pub fn iter(&self, s: State) -> impl DoubleEndedIterator<Item = Result<Val>> + '_ {393 (0..self.len()).map(move |idx| match self {394 Self::Bytes(b) => Ok(Val::Num(f64::from(b[idx]))),395 Self::Lazy(l) => l[idx].evaluate(s.clone()),396 Self::Eager(e) => Ok(e[idx].clone()),397 Self::Extended(..) | Self::Range(..) | Self::Reversed(..) | Self::Slice(..) => {398 self.get(s.clone(), idx).map(|e| e.expect("idx < len"))399 }400 })401 }402403 pub fn iter_lazy(&self) -> impl DoubleEndedIterator<Item = Thunk<Val>> + '_ {404 (0..self.len()).map(move |idx| match self {405 Self::Bytes(b) => Thunk::evaluated(Val::Num(f64::from(b[idx]))),406 Self::Lazy(l) => l[idx].clone(),407 Self::Eager(e) => Thunk::evaluated(e[idx].clone()),408 Self::Slice(..) | Self::Extended(..) | Self::Range(..) | Self::Reversed(..) => {409 self.get_lazy(idx).expect("idx < len")410 }411 })412 }413414 #[must_use]415 pub fn reversed(self) -> Self {416 Self::Reversed(Box::new(self))417 }418419 pub fn map(self, s: State, mapper: impl Fn(Val) -> Result<Val>) -> Result<Self> {420 let mut out = Vec::with_capacity(self.len());421422 for value in self.iter(s) {423 out.push(mapper(value?)?);424 }425426 Ok(Self::Eager(Cc::new(out)))427 }428429 pub fn filter(self, s: State, filter: impl Fn(&Val) -> Result<bool>) -> Result<Self> {430 let mut out = Vec::with_capacity(self.len());431432 for value in self.iter(s) {433 let value = value?;434 if filter(&value)? {435 out.push(value);436 }437 }438439 Ok(Self::Eager(Cc::new(out)))440 }441442 pub fn ptr_eq(a: &Self, b: &Self) -> bool {443 match (a, b) {444 (Self::Lazy(a), Self::Lazy(b)) => Cc::ptr_eq(a, b),445 (Self::Eager(a), Self::Eager(b)) => Cc::ptr_eq(a, b),446 _ => false,447 }448 }449}450451impl From<Vec<Thunk<Val>>> for ArrValue {452 fn from(v: Vec<Thunk<Val>>) -> Self {453 Self::Lazy(Cc::new(v))454 }455}456457impl From<Vec<Val>> for ArrValue {458 fn from(v: Vec<Val>) -> Self {459 Self::Eager(Cc::new(v))460 }461}462463#[allow(clippy::module_name_repetitions)]464pub enum IndexableVal {465 Str(IStr),466 Arr(ArrValue),467}468impl IndexableVal {469 pub fn slice(470 self,471 index: Option<BoundedUsize<0, { i32::MAX as usize }>>,472 end: Option<BoundedUsize<0, { i32::MAX as usize }>>,473 step: Option<BoundedUsize<1, { i32::MAX as usize }>>,474 ) -> Result<Self> {475 match &self {476 IndexableVal::Str(s) => {477 let index = index.as_deref().copied().unwrap_or(0);478 let end = end.as_deref().copied().unwrap_or(usize::MAX);479 let step = step.as_deref().copied().unwrap_or(1);480481 if index >= end {482 return Ok(Self::Str("".into()));483 }484485 Ok(Self::Str(486 (s.chars()487 .skip(index)488 .take(end - index)489 .step_by(step)490 .collect::<String>())491 .into(),492 ))493 }494 IndexableVal::Arr(arr) => {495 let index = index.as_deref().copied().unwrap_or(0);496 let end = end.as_deref().copied().unwrap_or(usize::MAX).min(arr.len());497 let step = step.as_deref().copied().unwrap_or(1);498499 if index >= end {500 return Ok(Self::Arr(ArrValue::new_eager()));501 }502503 Ok(Self::Arr(ArrValue::Slice(Box::new(Slice {504 inner: arr.clone(),505 from: index as u32,506 to: end as u32,507 step: step as u32,508 }))))509 }510 }511 }512}513514#[derive(Debug, Clone, Trace)]515pub enum Val {516 Bool(bool),517 Null,518 Str(IStr),519 Num(f64),520 Arr(ArrValue),521 Obj(ObjValue),522 Func(FuncVal),523}524525impl From<IndexableVal> for Val {526 fn from(v: IndexableVal) -> Self {527 match v {528 IndexableVal::Str(s) => Self::Str(s),529 IndexableVal::Arr(a) => Self::Arr(a),530 }531 }532}533534535536537538impl Val {539 pub const fn as_bool(&self) -> Option<bool> {540 match self {541 Self::Bool(v) => Some(*v),542 _ => None,543 }544 }545 pub const fn as_null(&self) -> Option<()> {546 match self {547 Self::Null => Some(()),548 _ => None,549 }550 }551 pub fn as_str(&self) -> Option<IStr> {552 match self {553 Self::Str(s) => Some(s.clone()),554 _ => None,555 }556 }557 pub const fn as_num(&self) -> Option<f64> {558 match self {559 Self::Num(n) => Some(*n),560 _ => None,561 }562 }563 pub fn as_arr(&self) -> Option<ArrValue> {564 match self {565 Self::Arr(a) => Some(a.clone()),566 _ => None,567 }568 }569 pub fn as_obj(&self) -> Option<ObjValue> {570 match self {571 Self::Obj(o) => Some(o.clone()),572 _ => None,573 }574 }575 pub fn as_func(&self) -> Option<FuncVal> {576 match self {577 Self::Func(f) => Some(f.clone()),578 _ => None,579 }580 }581582 583 584 pub fn new_checked_num(num: f64) -> Result<Self> {585 if num.is_finite() {586 Ok(Self::Num(num))587 } else {588 throw!(RuntimeError("overflow".into()))589 }590 }591592 pub const fn value_type(&self) -> ValType {593 match self {594 Self::Str(..) => ValType::Str,595 Self::Num(..) => ValType::Num,596 Self::Arr(..) => ValType::Arr,597 Self::Obj(..) => ValType::Obj,598 Self::Bool(_) => ValType::Bool,599 Self::Null => ValType::Null,600 Self::Func(..) => ValType::Func,601 }602 }603604 pub fn to_string(&self, s: State) -> Result<IStr> {605 Ok(match self {606 Self::Bool(true) => "true".into(),607 Self::Bool(false) => "false".into(),608 Self::Null => "null".into(),609 Self::Str(s) => s.clone(),610 v => manifest_json_ex(611 s,612 v,613 &ManifestJsonOptions {614 padding: "",615 mtype: ManifestType::ToString,616 newline: "\n",617 key_val_sep: ": ",618 #[cfg(feature = "exp-preserve-order")]619 preserve_order: false,620 },621 )?622 .into(),623 })624 }625626 627 pub fn manifest_multi(&self, s: State, ty: &ManifestFormat) -> Result<Vec<(IStr, IStr)>> {628 let obj = match self {629 Self::Obj(obj) => obj,630 _ => throw!(MultiManifestOutputIsNotAObject),631 };632 let keys = obj.fields(633 #[cfg(feature = "exp-preserve-order")]634 ty.preserve_order(),635 );636 let mut out = Vec::with_capacity(keys.len());637 for key in keys {638 let value = obj639 .get(s.clone(), key.clone())?640 .expect("item in object")641 .manifest(s.clone(), ty)?;642 out.push((key, value));643 }644 Ok(out)645 }646647 648 pub fn manifest_stream(&self, s: State, ty: &ManifestFormat) -> Result<Vec<IStr>> {649 let arr = match self {650 Self::Arr(a) => a,651 _ => throw!(StreamManifestOutputIsNotAArray),652 };653 let mut out = Vec::with_capacity(arr.len());654 for i in arr.iter(s.clone()) {655 out.push(i?.manifest(s.clone(), ty)?);656 }657 Ok(out)658 }659660 pub fn manifest(&self, s: State, ty: &ManifestFormat) -> Result<IStr> {661 Ok(match ty {662 ManifestFormat::YamlStream(format) => {663 let arr = match self {664 Self::Arr(a) => a,665 _ => throw!(StreamManifestOutputIsNotAArray),666 };667 let mut out = String::new();668669 match format as &ManifestFormat {670 ManifestFormat::YamlStream(_) => throw!(StreamManifestOutputCannotBeRecursed),671 ManifestFormat::String => throw!(StreamManifestCannotNestString),672 _ => {}673 };674675 if !arr.is_empty() {676 for v in arr.iter(s.clone()) {677 out.push_str("---\n");678 out.push_str(&v?.manifest(s.clone(), format)?);679 out.push('\n');680 }681 out.push_str("...");682 }683684 out.into()685 }686 ManifestFormat::Yaml {687 padding,688 #[cfg(feature = "exp-preserve-order")]689 preserve_order,690 } => self.to_yaml(691 s,692 *padding,693 #[cfg(feature = "exp-preserve-order")]694 *preserve_order,695 )?,696 ManifestFormat::Json {697 padding,698 #[cfg(feature = "exp-preserve-order")]699 preserve_order,700 } => self.to_json(701 s,702 *padding,703 #[cfg(feature = "exp-preserve-order")]704 *preserve_order,705 )?,706 ManifestFormat::ToString => self.to_string(s)?,707 ManifestFormat::String => match self {708 Self::Str(s) => s.clone(),709 _ => throw!(StringManifestOutputIsNotAString),710 },711 })712 }713714 715 pub fn to_json(716 &self,717 s: State,718 padding: usize,719 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,720 ) -> Result<IStr> {721 manifest_json_ex(722 s,723 self,724 &ManifestJsonOptions {725 padding: &" ".repeat(padding),726 mtype: if padding == 0 {727 ManifestType::Minify728 } else {729 ManifestType::Manifest730 },731 newline: "\n",732 key_val_sep: ": ",733 #[cfg(feature = "exp-preserve-order")]734 preserve_order,735 },736 )737 .map(Into::into)738 }739740 741 pub fn to_std_json(742 &self,743 s: State,744 padding: usize,745 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,746 ) -> Result<Rc<str>> {747 manifest_json_ex(748 s,749 self,750 &ManifestJsonOptions {751 padding: &" ".repeat(padding),752 mtype: ManifestType::Std,753 newline: "\n",754 key_val_sep: ": ",755 #[cfg(feature = "exp-preserve-order")]756 preserve_order,757 },758 )759 .map(Into::into)760 }761762 pub fn to_yaml(763 &self,764 s: State,765 padding: usize,766 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,767 ) -> Result<IStr> {768 let padding = &" ".repeat(padding);769 manifest_yaml_ex(770 s,771 self,772 &ManifestYamlOptions {773 padding,774 arr_element_padding: padding,775 quote_keys: false,776 #[cfg(feature = "exp-preserve-order")]777 preserve_order,778 },779 )780 .map(Into::into)781 }782 pub fn into_indexable(self) -> Result<IndexableVal> {783 Ok(match self {784 Val::Str(s) => IndexableVal::Str(s),785 Val::Arr(arr) => IndexableVal::Arr(arr),786 _ => throw!(ValueIsNotIndexable(self.value_type())),787 })788 }789}790791const fn is_function_like(val: &Val) -> bool {792 matches!(val, Val::Func(_))793}794795796pub fn primitive_equals(val_a: &Val, val_b: &Val) -> Result<bool> {797 Ok(match (val_a, val_b) {798 (Val::Bool(a), Val::Bool(b)) => a == b,799 (Val::Null, Val::Null) => true,800 (Val::Str(a), Val::Str(b)) => a == b,801 (Val::Num(a), Val::Num(b)) => (a - b).abs() <= f64::EPSILON,802 (Val::Arr(_), Val::Arr(_)) => throw!(RuntimeError(803 "primitiveEquals operates on primitive types, got array".into(),804 )),805 (Val::Obj(_), Val::Obj(_)) => throw!(RuntimeError(806 "primitiveEquals operates on primitive types, got object".into(),807 )),808 (a, b) if is_function_like(a) && is_function_like(b) => {809 throw!(RuntimeError("cannot test equality of functions".into()))810 }811 (_, _) => false,812 })813}814815816pub fn equals(s: State, val_a: &Val, val_b: &Val) -> Result<bool> {817 if val_a.value_type() != val_b.value_type() {818 return Ok(false);819 }820 match (val_a, val_b) {821 (Val::Arr(a), Val::Arr(b)) => {822 if ArrValue::ptr_eq(a, b) {823 return Ok(true);824 }825 if a.len() != b.len() {826 return Ok(false);827 }828 for (a, b) in a.iter(s.clone()).zip(b.iter(s.clone())) {829 if !equals(s.clone(), &a?, &b?)? {830 return Ok(false);831 }832 }833 Ok(true)834 }835 (Val::Obj(a), Val::Obj(b)) => {836 if ObjValue::ptr_eq(a, b) {837 return Ok(true);838 }839 let fields = a.fields(840 #[cfg(feature = "exp-preserve-order")]841 false,842 );843 if fields844 != b.fields(845 #[cfg(feature = "exp-preserve-order")]846 false,847 ) {848 return Ok(false);849 }850 for field in fields {851 if !equals(852 s.clone(),853 &a.get(s.clone(), field.clone())?.expect("field exists"),854 &b.get(s.clone(), field)?.expect("field exists"),855 )? {856 return Ok(false);857 }858 }859 Ok(true)860 }861 (a, b) => Ok(primitive_equals(a, b)?),862 }863}