1use std::{cell::RefCell, fmt::Debug, rc::Rc};23use gcmodule::{Cc, Trace};4use jrsonnet_interner::IStr;5use jrsonnet_types::ValType;67use crate::{8 cc_ptr_eq,9 error::{Error::*, LocError},10 function::FuncVal,11 gc::{GcHashMap, TraceBox},12 stdlib::manifest::{13 manifest_json_ex, manifest_yaml_ex, ManifestJsonOptions, ManifestType, ManifestYamlOptions,14 },15 throw, ObjValue, Result, State, Unbound, WeakObjValue,16};1718pub trait ThunkValue: Trace {19 type Output;20 fn get(self: Box<Self>, s: State) -> Result<Self::Output>;21}2223#[derive(Trace)]24enum ThunkInner<T> {25 Computed(T),26 Errored(LocError),27 Waiting(TraceBox<dyn ThunkValue<Output = T>>),28 Pending,29}3031#[allow(clippy::module_name_repetitions)]32#[derive(Clone, Trace)]33pub struct Thunk<T>(Cc<RefCell<ThunkInner<T>>>);34impl<T> Thunk<T>35where36 T: Clone + Trace,37{38 pub fn new(f: TraceBox<dyn ThunkValue<Output = T>>) -> Self {39 Self(Cc::new(RefCell::new(ThunkInner::Waiting(f))))40 }41 pub fn evaluated(val: T) -> Self {42 Self(Cc::new(RefCell::new(ThunkInner::Computed(val))))43 }44 pub fn force(&self, s: State) -> Result<()> {45 self.evaluate(s)?;46 Ok(())47 }48 pub fn evaluate(&self, s: State) -> Result<T> {49 match &*self.0.borrow() {50 ThunkInner::Computed(v) => return Ok(v.clone()),51 ThunkInner::Errored(e) => return Err(e.clone()),52 ThunkInner::Pending => return Err(InfiniteRecursionDetected.into()),53 ThunkInner::Waiting(..) => (),54 };55 let value = if let ThunkInner::Waiting(value) =56 std::mem::replace(&mut *self.0.borrow_mut(), ThunkInner::Pending)57 {58 value59 } else {60 unreachable!()61 };62 let new_value = match value.0.get(s) {63 Ok(v) => v,64 Err(e) => {65 *self.0.borrow_mut() = ThunkInner::Errored(e.clone());66 return Err(e);67 }68 };69 *self.0.borrow_mut() = ThunkInner::Computed(new_value.clone());70 Ok(new_value)71 }72}7374type CacheKey = (Option<WeakObjValue>, Option<WeakObjValue>);7576#[derive(Trace, Clone)]77pub struct CachedUnbound<I, T>78where79 I: Unbound<Bound = T>,80{81 cache: Cc<RefCell<GcHashMap<CacheKey, T>>>,82 value: I,83}84impl<I: Unbound<Bound = T>, T: Trace> CachedUnbound<I, T> {85 pub fn new(value: I) -> Self {86 Self {87 cache: Cc::new(RefCell::new(GcHashMap::new())),88 value,89 }90 }91}92impl<I: Unbound<Bound = T>, T: Clone + Trace> Unbound for CachedUnbound<I, T> {93 type Bound = T;94 fn bind(&self, s: State, sup: Option<ObjValue>, this: Option<ObjValue>) -> Result<T> {95 let cache_key = (96 sup.as_ref().map(|s| s.clone().downgrade()),97 this.as_ref().map(|t| t.clone().downgrade()),98 );99 {100 if let Some(t) = self.cache.borrow().get(&cache_key) {101 return Ok(t.clone());102 }103 }104 let bound = self.value.bind(s, sup, this)?;105106 {107 let mut cache = self.cache.borrow_mut();108 cache.insert(cache_key, bound.clone());109 }110111 Ok(bound)112 }113}114115impl<T: Debug> Debug for Thunk<T> {116 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {117 write!(f, "Lazy")118 }119}120impl<T> PartialEq for Thunk<T> {121 fn eq(&self, other: &Self) -> bool {122 cc_ptr_eq(&self.0, &other.0)123 }124}125126#[derive(Clone)]127pub enum ManifestFormat {128 YamlStream(Box<ManifestFormat>),129 Yaml {130 padding: usize,131 #[cfg(feature = "exp-preserve-order")]132 preserve_order: bool,133 },134 Json {135 padding: usize,136 #[cfg(feature = "exp-preserve-order")]137 preserve_order: bool,138 },139 ToString,140 String,141}142impl ManifestFormat {143 #[cfg(feature = "exp-preserve-order")]144 fn preserve_order(&self) -> bool {145 match self {146 ManifestFormat::YamlStream(s) => s.preserve_order(),147 ManifestFormat::Yaml { preserve_order, .. } => *preserve_order,148 ManifestFormat::Json { preserve_order, .. } => *preserve_order,149 ManifestFormat::ToString => false,150 ManifestFormat::String => false,151 }152 }153}154155#[derive(Debug, Clone, Trace)]156pub struct Slice {157 pub(crate) inner: ArrValue,158 pub(crate) from: u32,159 pub(crate) to: u32,160 pub(crate) step: u32,161}162impl Slice {163 const fn from(&self) -> usize {164 self.from as usize165 }166 const fn to(&self) -> usize {167 self.to as usize168 }169 const fn step(&self) -> usize {170 self.step as usize171 }172 const fn len(&self) -> usize {173 174 let diff = self.to() - self.from();175 let rem = diff % self.step();176 let div = diff / self.step();177178 if rem == 0 {179 div180 } else {181 div + 1182 }183 }184}185186#[derive(Debug, Clone, Trace)]187#[force_tracking]188pub enum ArrValue {189 Bytes(#[skip_trace] Rc<[u8]>),190 Lazy(Cc<Vec<Thunk<Val>>>),191 Eager(Cc<Vec<Val>>),192 Extended(Box<(Self, Self)>),193 Range(i32, i32),194 Slice(Box<Slice>),195 Reversed(Box<Self>),196}197impl ArrValue {198 pub fn new_eager() -> Self {199 Self::Eager(Cc::new(Vec::new()))200 }201202 203 204 pub fn new_range(a: i32, b: i32) -> Self {205 assert!(a <= b);206 Self::Range(a, b)207 }208209 210 211 #[must_use]212 pub fn slice(self, from: Option<usize>, to: Option<usize>, step: Option<usize>) -> Self {213 let len = self.len();214 let from = from.unwrap_or(0);215 let to = to.unwrap_or(len).min(len);216 let step = step.unwrap_or(1);217 assert!(from < to);218 assert!(step > 0);219220 Self::Slice(Box::new(Slice {221 inner: self,222 from: from as u32,223 to: to as u32,224 step: step as u32,225 }))226 }227228 pub fn len(&self) -> usize {229 match self {230 Self::Bytes(i) => i.len(),231 Self::Lazy(l) => l.len(),232 Self::Eager(e) => e.len(),233 Self::Extended(v) => v.0.len() + v.1.len(),234 Self::Range(a, b) => a.abs_diff(*b) as usize + 1,235 Self::Reversed(i) => i.len(),236 Self::Slice(s) => s.len(),237 }238 }239240 pub fn is_empty(&self) -> bool {241 self.len() == 0242 }243244 pub fn get(&self, s: State, index: usize) -> Result<Option<Val>> {245 match self {246 Self::Bytes(i) => i247 .get(index)248 .map_or(Ok(None), |v| Ok(Some(Val::Num(f64::from(*v))))),249 Self::Lazy(vec) => {250 if let Some(v) = vec.get(index) {251 Ok(Some(v.evaluate(s)?))252 } else {253 Ok(None)254 }255 }256 Self::Eager(vec) => Ok(vec.get(index).cloned()),257 Self::Extended(v) => {258 let a_len = v.0.len();259 if a_len > index {260 v.0.get(s, index)261 } else {262 v.1.get(s, index - a_len)263 }264 }265 Self::Range(a, _) => {266 if index >= self.len() {267 return Ok(None);268 }269 Ok(Some(Val::Num(((*a as isize) + index as isize) as f64)))270 }271 Self::Reversed(v) => {272 let len = v.len();273 if index >= len {274 return Ok(None);275 }276 v.get(s, len - index - 1)277 }278 Self::Slice(v) => {279 let index = v.from() + index * v.step();280 if index >= v.to() {281 return Ok(None);282 }283 v.inner.get(s, index as usize)284 }285 }286 }287288 pub fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {289 match self {290 Self::Bytes(i) => i291 .get(index)292 .map(|b| Thunk::evaluated(Val::Num(f64::from(*b)))),293 Self::Lazy(vec) => vec.get(index).cloned(),294 Self::Eager(vec) => vec.get(index).cloned().map(Thunk::evaluated),295 Self::Extended(v) => {296 let a_len = v.0.len();297 if a_len > index {298 v.0.get_lazy(index)299 } else {300 v.1.get_lazy(index - a_len)301 }302 }303 Self::Range(a, _) => {304 if index >= self.len() {305 return None;306 }307 Some(Thunk::evaluated(Val::Num(308 ((*a as isize) + index as isize) as f64,309 )))310 }311 Self::Reversed(v) => {312 let len = v.len();313 if index >= len {314 return None;315 }316 v.get_lazy(len - index - 1)317 }318 Self::Slice(s) => {319 let index = s.from() + index * s.step();320 if index >= s.to() {321 return None;322 }323 s.inner.get_lazy(index as usize)324 }325 }326 }327328 pub fn evaluated(&self, s: State) -> Result<Cc<Vec<Val>>> {329 Ok(match self {330 Self::Bytes(i) => {331 let mut out = Vec::with_capacity(i.len());332 for v in i.iter() {333 out.push(Val::Num(f64::from(*v)));334 }335 Cc::new(out)336 }337 Self::Lazy(vec) => {338 let mut out = Vec::with_capacity(vec.len());339 for item in vec.iter() {340 out.push(item.evaluate(s.clone())?);341 }342 Cc::new(out)343 }344 Self::Eager(vec) => vec.clone(),345 Self::Extended(_v) => {346 let mut out = Vec::with_capacity(self.len());347 for item in self.iter(s) {348 out.push(item?);349 }350 Cc::new(out)351 }352 Self::Range(a, b) => {353 let mut out = Vec::with_capacity(self.len());354 for i in *a..*b {355 out.push(Val::Num(f64::from(i)));356 }357 Cc::new(out)358 }359 Self::Reversed(r) => {360 let mut r = r.evaluated(s)?;361 Cc::update_with(&mut r, |v| v.reverse());362 r363 }364 Self::Slice(v) => {365 let mut out = Vec::with_capacity(v.inner.len());366 for v in v367 .inner368 .iter_lazy()369 .skip(v.from())370 .take(v.to() - v.from())371 .step_by(v.step())372 {373 out.push(v.evaluate(s.clone())?);374 }375 Cc::new(out)376 }377 })378 }379380 pub fn iter(&self, s: State) -> impl DoubleEndedIterator<Item = Result<Val>> + '_ {381 (0..self.len()).map(move |idx| match self {382 Self::Bytes(b) => Ok(Val::Num(f64::from(b[idx]))),383 Self::Lazy(l) => l[idx].evaluate(s.clone()),384 Self::Eager(e) => Ok(e[idx].clone()),385 Self::Extended(..) | Self::Range(..) | Self::Reversed(..) | Self::Slice(..) => {386 self.get(s.clone(), idx).map(|e| e.expect("idx < len"))387 }388 })389 }390391 pub fn iter_lazy(&self) -> impl DoubleEndedIterator<Item = Thunk<Val>> + '_ {392 (0..self.len()).map(move |idx| match self {393 Self::Bytes(b) => Thunk::evaluated(Val::Num(f64::from(b[idx]))),394 Self::Lazy(l) => l[idx].clone(),395 Self::Eager(e) => Thunk::evaluated(e[idx].clone()),396 Self::Slice(..) | Self::Extended(..) | Self::Range(..) | Self::Reversed(..) => {397 self.get_lazy(idx).expect("idx < len")398 }399 })400 }401402 #[must_use]403 pub fn reversed(self) -> Self {404 Self::Reversed(Box::new(self))405 }406407 pub fn map(self, s: State, mapper: impl Fn(Val) -> Result<Val>) -> Result<Self> {408 let mut out = Vec::with_capacity(self.len());409410 for value in self.iter(s) {411 out.push(mapper(value?)?);412 }413414 Ok(Self::Eager(Cc::new(out)))415 }416417 pub fn filter(self, s: State, filter: impl Fn(&Val) -> Result<bool>) -> Result<Self> {418 let mut out = Vec::with_capacity(self.len());419420 for value in self.iter(s) {421 let value = value?;422 if filter(&value)? {423 out.push(value);424 }425 }426427 Ok(Self::Eager(Cc::new(out)))428 }429430 pub fn ptr_eq(a: &Self, b: &Self) -> bool {431 match (a, b) {432 (Self::Lazy(a), Self::Lazy(b)) => cc_ptr_eq(a, b),433 (Self::Eager(a), Self::Eager(b)) => cc_ptr_eq(a, b),434 _ => false,435 }436 }437}438439impl From<Vec<Thunk<Val>>> for ArrValue {440 fn from(v: Vec<Thunk<Val>>) -> Self {441 Self::Lazy(Cc::new(v))442 }443}444445impl From<Vec<Val>> for ArrValue {446 fn from(v: Vec<Val>) -> Self {447 Self::Eager(Cc::new(v))448 }449}450451#[allow(clippy::module_name_repetitions)]452pub enum IndexableVal {453 Str(IStr),454 Arr(ArrValue),455}456457#[derive(Debug, Clone, Trace)]458pub enum Val {459 Bool(bool),460 Null,461 Str(IStr),462 Num(f64),463 Arr(ArrValue),464 Obj(ObjValue),465 Func(FuncVal),466}467468impl Val {469 pub const fn as_bool(&self) -> Option<bool> {470 match self {471 Val::Bool(v) => Some(*v),472 _ => None,473 }474 }475 pub const fn as_null(&self) -> Option<()> {476 match self {477 Val::Null => Some(()),478 _ => None,479 }480 }481 pub fn as_str(&self) -> Option<IStr> {482 match self {483 Val::Str(s) => Some(s.clone()),484 _ => None,485 }486 }487 pub const fn as_num(&self) -> Option<f64> {488 match self {489 Val::Num(n) => Some(*n),490 _ => None,491 }492 }493 pub fn as_arr(&self) -> Option<ArrValue> {494 match self {495 Val::Arr(a) => Some(a.clone()),496 _ => None,497 }498 }499 pub fn as_obj(&self) -> Option<ObjValue> {500 match self {501 Val::Obj(o) => Some(o.clone()),502 _ => None,503 }504 }505 pub fn as_func(&self) -> Option<FuncVal> {506 match self {507 Val::Func(f) => Some(f.clone()),508 _ => None,509 }510 }511512 513 514 pub fn new_checked_num(num: f64) -> Result<Self> {515 if num.is_finite() {516 Ok(Self::Num(num))517 } else {518 throw!(RuntimeError("overflow".into()))519 }520 }521522 pub const fn value_type(&self) -> ValType {523 match self {524 Self::Str(..) => ValType::Str,525 Self::Num(..) => ValType::Num,526 Self::Arr(..) => ValType::Arr,527 Self::Obj(..) => ValType::Obj,528 Self::Bool(_) => ValType::Bool,529 Self::Null => ValType::Null,530 Self::Func(..) => ValType::Func,531 }532 }533534 pub fn to_string(&self, s: State) -> Result<IStr> {535 Ok(match self {536 Self::Bool(true) => "true".into(),537 Self::Bool(false) => "false".into(),538 Self::Null => "null".into(),539 Self::Str(s) => s.clone(),540 v => manifest_json_ex(541 s,542 v,543 &ManifestJsonOptions {544 padding: "",545 mtype: ManifestType::ToString,546 newline: "\n",547 key_val_sep: ": ",548 #[cfg(feature = "exp-preserve-order")]549 preserve_order: false,550 },551 )?552 .into(),553 })554 }555556 557 pub fn manifest_multi(&self, s: State, ty: &ManifestFormat) -> Result<Vec<(IStr, IStr)>> {558 let obj = match self {559 Self::Obj(obj) => obj,560 _ => throw!(MultiManifestOutputIsNotAObject),561 };562 let keys = obj.fields(563 #[cfg(feature = "exp-preserve-order")]564 ty.preserve_order(),565 );566 let mut out = Vec::with_capacity(keys.len());567 for key in keys {568 let value = obj569 .get(s.clone(), key.clone())?570 .expect("item in object")571 .manifest(s.clone(), ty)?;572 out.push((key, value));573 }574 Ok(out)575 }576577 578 pub fn manifest_stream(&self, s: State, ty: &ManifestFormat) -> Result<Vec<IStr>> {579 let arr = match self {580 Self::Arr(a) => a,581 _ => throw!(StreamManifestOutputIsNotAArray),582 };583 let mut out = Vec::with_capacity(arr.len());584 for i in arr.iter(s.clone()) {585 out.push(i?.manifest(s.clone(), ty)?);586 }587 Ok(out)588 }589590 pub fn manifest(&self, s: State, ty: &ManifestFormat) -> Result<IStr> {591 Ok(match ty {592 ManifestFormat::YamlStream(format) => {593 let arr = match self {594 Self::Arr(a) => a,595 _ => throw!(StreamManifestOutputIsNotAArray),596 };597 let mut out = String::new();598599 match format as &ManifestFormat {600 ManifestFormat::YamlStream(_) => throw!(StreamManifestOutputCannotBeRecursed),601 ManifestFormat::String => throw!(StreamManifestCannotNestString),602 _ => {}603 };604605 if !arr.is_empty() {606 for v in arr.iter(s.clone()) {607 out.push_str("---\n");608 out.push_str(&v?.manifest(s.clone(), format)?);609 out.push('\n');610 }611 out.push_str("...");612 }613614 out.into()615 }616 ManifestFormat::Yaml {617 padding,618 #[cfg(feature = "exp-preserve-order")]619 preserve_order,620 } => self.to_yaml(621 s,622 *padding,623 #[cfg(feature = "exp-preserve-order")]624 *preserve_order,625 )?,626 ManifestFormat::Json {627 padding,628 #[cfg(feature = "exp-preserve-order")]629 preserve_order,630 } => self.to_json(631 s,632 *padding,633 #[cfg(feature = "exp-preserve-order")]634 *preserve_order,635 )?,636 ManifestFormat::ToString => self.to_string(s)?,637 ManifestFormat::String => match self {638 Self::Str(s) => s.clone(),639 _ => throw!(StringManifestOutputIsNotAString),640 },641 })642 }643644 645 pub fn to_json(646 &self,647 s: State,648 padding: usize,649 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,650 ) -> Result<IStr> {651 manifest_json_ex(652 s,653 self,654 &ManifestJsonOptions {655 padding: &" ".repeat(padding),656 mtype: if padding == 0 {657 ManifestType::Minify658 } else {659 ManifestType::Manifest660 },661 newline: "\n",662 key_val_sep: ": ",663 #[cfg(feature = "exp-preserve-order")]664 preserve_order,665 },666 )667 .map(Into::into)668 }669670 671 pub fn to_std_json(672 &self,673 s: State,674 padding: usize,675 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,676 ) -> Result<Rc<str>> {677 manifest_json_ex(678 s,679 self,680 &ManifestJsonOptions {681 padding: &" ".repeat(padding),682 mtype: ManifestType::Std,683 newline: "\n",684 key_val_sep: ": ",685 #[cfg(feature = "exp-preserve-order")]686 preserve_order,687 },688 )689 .map(Into::into)690 }691692 pub fn to_yaml(693 &self,694 s: State,695 padding: usize,696 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,697 ) -> Result<IStr> {698 let padding = &" ".repeat(padding);699 manifest_yaml_ex(700 s,701 self,702 &ManifestYamlOptions {703 padding,704 arr_element_padding: padding,705 quote_keys: false,706 #[cfg(feature = "exp-preserve-order")]707 preserve_order,708 },709 )710 .map(Into::into)711 }712 pub fn into_indexable(self) -> Result<IndexableVal> {713 Ok(match self {714 Val::Str(s) => IndexableVal::Str(s),715 Val::Arr(arr) => IndexableVal::Arr(arr),716 _ => throw!(ValueIsNotIndexable(self.value_type())),717 })718 }719}720721const fn is_function_like(val: &Val) -> bool {722 matches!(val, Val::Func(_))723}724725726pub fn primitive_equals(val_a: &Val, val_b: &Val) -> Result<bool> {727 Ok(match (val_a, val_b) {728 (Val::Bool(a), Val::Bool(b)) => a == b,729 (Val::Null, Val::Null) => true,730 (Val::Str(a), Val::Str(b)) => a == b,731 (Val::Num(a), Val::Num(b)) => (a - b).abs() <= f64::EPSILON,732 (Val::Arr(_), Val::Arr(_)) => throw!(RuntimeError(733 "primitiveEquals operates on primitive types, got array".into(),734 )),735 (Val::Obj(_), Val::Obj(_)) => throw!(RuntimeError(736 "primitiveEquals operates on primitive types, got object".into(),737 )),738 (a, b) if is_function_like(a) && is_function_like(b) => {739 throw!(RuntimeError("cannot test equality of functions".into()))740 }741 (_, _) => false,742 })743}744745746pub fn equals(s: State, val_a: &Val, val_b: &Val) -> Result<bool> {747 if val_a.value_type() != val_b.value_type() {748 return Ok(false);749 }750 match (val_a, val_b) {751 (Val::Arr(a), Val::Arr(b)) => {752 if ArrValue::ptr_eq(a, b) {753 return Ok(true);754 }755 if a.len() != b.len() {756 return Ok(false);757 }758 for (a, b) in a.iter(s.clone()).zip(b.iter(s.clone())) {759 if !equals(s.clone(), &a?, &b?)? {760 return Ok(false);761 }762 }763 Ok(true)764 }765 (Val::Obj(a), Val::Obj(b)) => {766 if ObjValue::ptr_eq(a, b) {767 return Ok(true);768 }769 let fields = a.fields(770 #[cfg(feature = "exp-preserve-order")]771 false,772 );773 if fields774 != b.fields(775 #[cfg(feature = "exp-preserve-order")]776 false,777 ) {778 return Ok(false);779 }780 for field in fields {781 if !equals(782 s.clone(),783 &a.get(s.clone(), field.clone())?.expect("field exists"),784 &b.get(s.clone(), field)?.expect("field exists"),785 )? {786 return Ok(false);787 }788 }789 Ok(true)790 }791 (a, b) => Ok(primitive_equals(a, b)?),792 }793}