difftreelog
feat(evaluator) `IndexableMap::slice` helper
in: master
Previously `slice` method was only in `ArrayVal`, and for strings it needed to be implemented manually
1 file changed
crates/jrsonnet-evaluator/src/val.rsdiffbeforeafterboth1use 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, ObjValue, Result, State, Unbound, WeakObjValue,15};1617pub trait ThunkValue: Trace {18 type Output;19 fn get(self: Box<Self>, s: State) -> Result<Self::Output>;20}2122#[derive(Trace)]23enum ThunkInner<T: Trace> {24 Computed(T),25 Errored(LocError),26 Waiting(TraceBox<dyn ThunkValue<Output = T>>),27 Pending,28}2930#[allow(clippy::module_name_repetitions)]31#[derive(Clone, Trace)]32pub struct Thunk<T: Trace>(Cc<RefCell<ThunkInner<T>>>);3334impl<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 T: Trace,81{82 cache: Cc<RefCell<GcHashMap<CacheKey, T>>>,83 value: I,84}85impl<I: Unbound<Bound = T>, T: Trace> CachedUnbound<I, T> {86 pub fn new(value: I) -> Self {87 Self {88 cache: Cc::new(RefCell::new(GcHashMap::new())),89 value,90 }91 }92}93impl<I: Unbound<Bound = T>, T: Clone + Trace> Unbound for CachedUnbound<I, T> {94 type Bound = T;95 fn bind(&self, s: State, sup: Option<ObjValue>, this: Option<ObjValue>) -> Result<T> {96 let cache_key = (97 sup.as_ref().map(|s| s.clone().downgrade()),98 this.as_ref().map(|t| t.clone().downgrade()),99 );100 {101 if let Some(t) = self.cache.borrow().get(&cache_key) {102 return Ok(t.clone());103 }104 }105 let bound = self.value.bind(s, sup, this)?;106107 {108 let mut cache = self.cache.borrow_mut();109 cache.insert(cache_key, bound.clone());110 }111112 Ok(bound)113 }114}115116impl<T: Debug + Trace> Debug for Thunk<T> {117 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {118 write!(f, "Lazy")119 }120}121impl<T: Trace> PartialEq for Thunk<T> {122 fn eq(&self, other: &Self) -> bool {123 Cc::ptr_eq(&self.0, &other.0)124 }125}126127#[derive(Clone)]128pub enum ManifestFormat {129 YamlStream(Box<ManifestFormat>),130 Yaml {131 padding: usize,132 #[cfg(feature = "exp-preserve-order")]133 preserve_order: bool,134 },135 Json {136 padding: usize,137 #[cfg(feature = "exp-preserve-order")]138 preserve_order: bool,139 },140 ToString,141 String,142}143impl ManifestFormat {144 #[cfg(feature = "exp-preserve-order")]145 fn preserve_order(&self) -> bool {146 match self {147 ManifestFormat::YamlStream(s) => s.preserve_order(),148 ManifestFormat::Yaml { preserve_order, .. } => *preserve_order,149 ManifestFormat::Json { preserve_order, .. } => *preserve_order,150 ManifestFormat::ToString => false,151 ManifestFormat::String => false,152 }153 }154}155156#[derive(Debug, Clone, Trace)]157pub struct Slice {158 pub(crate) inner: ArrValue,159 pub(crate) from: u32,160 pub(crate) to: u32,161 pub(crate) step: u32,162}163impl Slice {164 const fn from(&self) -> usize {165 self.from as usize166 }167 const fn to(&self) -> usize {168 self.to as usize169 }170 const fn step(&self) -> usize {171 self.step as usize172 }173 const fn len(&self) -> usize {174 // TODO: use div_ceil175 let diff = self.to() - self.from();176 let rem = diff % self.step();177 let div = diff / self.step();178179 if rem == 0 {180 div181 } else {182 div + 1183 }184 }185}186187#[derive(Debug, Clone, Trace)]188// may contrain other ArrValue189#[trace(tracking(force))]190pub enum ArrValue {191 Bytes(#[trace(skip)] IBytes),192 Lazy(Cc<Vec<Thunk<Val>>>),193 Eager(Cc<Vec<Val>>),194 Extended(Box<(Self, Self)>),195 Range(i32, i32),196 Slice(Box<Slice>),197 Reversed(Box<Self>),198}199200#[cfg(target_pointer_width = "64")]201static_assertions::assert_eq_size!(ArrValue, [u8; 16]);202203impl ArrValue {204 pub fn new_eager() -> Self {205 Self::Eager(Cc::new(Vec::new()))206 }207208 /// # Panics209 /// If a > b210 pub fn new_range(a: i32, b: i32) -> Self {211 assert!(a <= b);212 Self::Range(a, b)213 }214215 /// # Panics216 /// If passed numbers are incorrect217 #[must_use]218 pub fn slice(self, from: Option<usize>, to: Option<usize>, step: Option<usize>) -> Self {219 let len = self.len();220 let from = from.unwrap_or(0);221 let to = to.unwrap_or(len).min(len);222 let step = step.unwrap_or(1);223 assert!(from < to);224 assert!(step > 0);225226 Self::Slice(Box::new(Slice {227 inner: self,228 from: from as u32,229 to: to as u32,230 step: step as u32,231 }))232 }233234 pub fn len(&self) -> usize {235 match self {236 Self::Bytes(i) => i.len(),237 Self::Lazy(l) => l.len(),238 Self::Eager(e) => e.len(),239 Self::Extended(v) => v.0.len() + v.1.len(),240 Self::Range(a, b) => a.abs_diff(*b) as usize + 1,241 Self::Reversed(i) => i.len(),242 Self::Slice(s) => s.len(),243 }244 }245246 pub fn is_empty(&self) -> bool {247 self.len() == 0248 }249250 pub fn get(&self, s: State, index: usize) -> Result<Option<Val>> {251 match self {252 Self::Bytes(i) => i253 .get(index)254 .map_or(Ok(None), |v| Ok(Some(Val::Num(f64::from(*v))))),255 Self::Lazy(vec) => {256 if let Some(v) = vec.get(index) {257 Ok(Some(v.evaluate(s)?))258 } else {259 Ok(None)260 }261 }262 Self::Eager(vec) => Ok(vec.get(index).cloned()),263 Self::Extended(v) => {264 let a_len = v.0.len();265 if a_len > index {266 v.0.get(s, index)267 } else {268 v.1.get(s, index - a_len)269 }270 }271 Self::Range(a, _) => {272 if index >= self.len() {273 return Ok(None);274 }275 Ok(Some(Val::Num(((*a as isize) + index as isize) as f64)))276 }277 Self::Reversed(v) => {278 let len = v.len();279 if index >= len {280 return Ok(None);281 }282 v.get(s, len - index - 1)283 }284 Self::Slice(v) => {285 let index = v.from() + index * v.step();286 if index >= v.to() {287 return Ok(None);288 }289 v.inner.get(s, index as usize)290 }291 }292 }293294 pub fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {295 match self {296 Self::Bytes(i) => i297 .get(index)298 .map(|b| Thunk::evaluated(Val::Num(f64::from(*b)))),299 Self::Lazy(vec) => vec.get(index).cloned(),300 Self::Eager(vec) => vec.get(index).cloned().map(Thunk::evaluated),301 Self::Extended(v) => {302 let a_len = v.0.len();303 if a_len > index {304 v.0.get_lazy(index)305 } else {306 v.1.get_lazy(index - a_len)307 }308 }309 Self::Range(a, _) => {310 if index >= self.len() {311 return None;312 }313 Some(Thunk::evaluated(Val::Num(314 ((*a as isize) + index as isize) as f64,315 )))316 }317 Self::Reversed(v) => {318 let len = v.len();319 if index >= len {320 return None;321 }322 v.get_lazy(len - index - 1)323 }324 Self::Slice(s) => {325 let index = s.from() + index * s.step();326 if index >= s.to() {327 return None;328 }329 s.inner.get_lazy(index as usize)330 }331 }332 }333334 pub fn evaluated(&self, s: State) -> Result<Cc<Vec<Val>>> {335 Ok(match self {336 Self::Bytes(i) => {337 let mut out = Vec::with_capacity(i.len());338 for v in i.iter() {339 out.push(Val::Num(f64::from(*v)));340 }341 Cc::new(out)342 }343 Self::Lazy(vec) => {344 let mut out = Vec::with_capacity(vec.len());345 for item in vec.iter() {346 out.push(item.evaluate(s.clone())?);347 }348 Cc::new(out)349 }350 Self::Eager(vec) => vec.clone(),351 Self::Extended(_v) => {352 let mut out = Vec::with_capacity(self.len());353 for item in self.iter(s) {354 out.push(item?);355 }356 Cc::new(out)357 }358 Self::Range(a, b) => {359 let mut out = Vec::with_capacity(self.len());360 for i in *a..*b {361 out.push(Val::Num(f64::from(i)));362 }363 Cc::new(out)364 }365 Self::Reversed(r) => {366 let mut r = r.evaluated(s)?;367 Cc::update_with(&mut r, |v| v.reverse());368 r369 }370 Self::Slice(v) => {371 let mut out = Vec::with_capacity(v.inner.len());372 for v in v373 .inner374 .iter_lazy()375 .skip(v.from())376 .take(v.to() - v.from())377 .step_by(v.step())378 {379 out.push(v.evaluate(s.clone())?);380 }381 Cc::new(out)382 }383 })384 }385386 pub fn iter(&self, s: State) -> impl DoubleEndedIterator<Item = Result<Val>> + '_ {387 (0..self.len()).map(move |idx| match self {388 Self::Bytes(b) => Ok(Val::Num(f64::from(b[idx]))),389 Self::Lazy(l) => l[idx].evaluate(s.clone()),390 Self::Eager(e) => Ok(e[idx].clone()),391 Self::Extended(..) | Self::Range(..) | Self::Reversed(..) | Self::Slice(..) => {392 self.get(s.clone(), idx).map(|e| e.expect("idx < len"))393 }394 })395 }396397 pub fn iter_lazy(&self) -> impl DoubleEndedIterator<Item = Thunk<Val>> + '_ {398 (0..self.len()).map(move |idx| match self {399 Self::Bytes(b) => Thunk::evaluated(Val::Num(f64::from(b[idx]))),400 Self::Lazy(l) => l[idx].clone(),401 Self::Eager(e) => Thunk::evaluated(e[idx].clone()),402 Self::Slice(..) | Self::Extended(..) | Self::Range(..) | Self::Reversed(..) => {403 self.get_lazy(idx).expect("idx < len")404 }405 })406 }407408 #[must_use]409 pub fn reversed(self) -> Self {410 Self::Reversed(Box::new(self))411 }412413 pub fn map(self, s: State, mapper: impl Fn(Val) -> Result<Val>) -> Result<Self> {414 let mut out = Vec::with_capacity(self.len());415416 for value in self.iter(s) {417 out.push(mapper(value?)?);418 }419420 Ok(Self::Eager(Cc::new(out)))421 }422423 pub fn filter(self, s: State, filter: impl Fn(&Val) -> Result<bool>) -> Result<Self> {424 let mut out = Vec::with_capacity(self.len());425426 for value in self.iter(s) {427 let value = value?;428 if filter(&value)? {429 out.push(value);430 }431 }432433 Ok(Self::Eager(Cc::new(out)))434 }435436 pub fn ptr_eq(a: &Self, b: &Self) -> bool {437 match (a, b) {438 (Self::Lazy(a), Self::Lazy(b)) => Cc::ptr_eq(a, b),439 (Self::Eager(a), Self::Eager(b)) => Cc::ptr_eq(a, b),440 _ => false,441 }442 }443}444445impl From<Vec<Thunk<Val>>> for ArrValue {446 fn from(v: Vec<Thunk<Val>>) -> Self {447 Self::Lazy(Cc::new(v))448 }449}450451impl From<Vec<Val>> for ArrValue {452 fn from(v: Vec<Val>) -> Self {453 Self::Eager(Cc::new(v))454 }455}456457#[allow(clippy::module_name_repetitions)]458pub enum IndexableVal {459 Str(IStr),460 Arr(ArrValue),461}462463#[derive(Debug, Clone, Trace)]464pub enum Val {465 Bool(bool),466 Null,467 Str(IStr),468 Num(f64),469 Arr(ArrValue),470 Obj(ObjValue),471 Func(FuncVal),472}473474#[cfg(target_pointer_width = "64")]475static_assertions::assert_eq_size!(Val, [u8; 32]);476477impl Val {478 pub const fn as_bool(&self) -> Option<bool> {479 match self {480 Self::Bool(v) => Some(*v),481 _ => None,482 }483 }484 pub const fn as_null(&self) -> Option<()> {485 match self {486 Self::Null => Some(()),487 _ => None,488 }489 }490 pub fn as_str(&self) -> Option<IStr> {491 match self {492 Self::Str(s) => Some(s.clone()),493 _ => None,494 }495 }496 pub const fn as_num(&self) -> Option<f64> {497 match self {498 Self::Num(n) => Some(*n),499 _ => None,500 }501 }502 pub fn as_arr(&self) -> Option<ArrValue> {503 match self {504 Self::Arr(a) => Some(a.clone()),505 _ => None,506 }507 }508 pub fn as_obj(&self) -> Option<ObjValue> {509 match self {510 Self::Obj(o) => Some(o.clone()),511 _ => None,512 }513 }514 pub fn as_func(&self) -> Option<FuncVal> {515 match self {516 Self::Func(f) => Some(f.clone()),517 _ => None,518 }519 }520521 /// Creates `Val::Num` after checking for numeric overflow.522 /// As numbers are `f64`, we can just check for their finity.523 pub fn new_checked_num(num: f64) -> Result<Self> {524 if num.is_finite() {525 Ok(Self::Num(num))526 } else {527 throw!(RuntimeError("overflow".into()))528 }529 }530531 pub const fn value_type(&self) -> ValType {532 match self {533 Self::Str(..) => ValType::Str,534 Self::Num(..) => ValType::Num,535 Self::Arr(..) => ValType::Arr,536 Self::Obj(..) => ValType::Obj,537 Self::Bool(_) => ValType::Bool,538 Self::Null => ValType::Null,539 Self::Func(..) => ValType::Func,540 }541 }542543 pub fn to_string(&self, s: State) -> Result<IStr> {544 Ok(match self {545 Self::Bool(true) => "true".into(),546 Self::Bool(false) => "false".into(),547 Self::Null => "null".into(),548 Self::Str(s) => s.clone(),549 v => manifest_json_ex(550 s,551 v,552 &ManifestJsonOptions {553 padding: "",554 mtype: ManifestType::ToString,555 newline: "\n",556 key_val_sep: ": ",557 #[cfg(feature = "exp-preserve-order")]558 preserve_order: false,559 },560 )?561 .into(),562 })563 }564565 /// Expects value to be object, outputs (key, manifested value) pairs566 pub fn manifest_multi(&self, s: State, ty: &ManifestFormat) -> Result<Vec<(IStr, IStr)>> {567 let obj = match self {568 Self::Obj(obj) => obj,569 _ => throw!(MultiManifestOutputIsNotAObject),570 };571 let keys = obj.fields(572 #[cfg(feature = "exp-preserve-order")]573 ty.preserve_order(),574 );575 let mut out = Vec::with_capacity(keys.len());576 for key in keys {577 let value = obj578 .get(s.clone(), key.clone())?579 .expect("item in object")580 .manifest(s.clone(), ty)?;581 out.push((key, value));582 }583 Ok(out)584 }585586 /// Expects value to be array, outputs manifested values587 pub fn manifest_stream(&self, s: State, ty: &ManifestFormat) -> Result<Vec<IStr>> {588 let arr = match self {589 Self::Arr(a) => a,590 _ => throw!(StreamManifestOutputIsNotAArray),591 };592 let mut out = Vec::with_capacity(arr.len());593 for i in arr.iter(s.clone()) {594 out.push(i?.manifest(s.clone(), ty)?);595 }596 Ok(out)597 }598599 pub fn manifest(&self, s: State, ty: &ManifestFormat) -> Result<IStr> {600 Ok(match ty {601 ManifestFormat::YamlStream(format) => {602 let arr = match self {603 Self::Arr(a) => a,604 _ => throw!(StreamManifestOutputIsNotAArray),605 };606 let mut out = String::new();607608 match format as &ManifestFormat {609 ManifestFormat::YamlStream(_) => throw!(StreamManifestOutputCannotBeRecursed),610 ManifestFormat::String => throw!(StreamManifestCannotNestString),611 _ => {}612 };613614 if !arr.is_empty() {615 for v in arr.iter(s.clone()) {616 out.push_str("---\n");617 out.push_str(&v?.manifest(s.clone(), format)?);618 out.push('\n');619 }620 out.push_str("...");621 }622623 out.into()624 }625 ManifestFormat::Yaml {626 padding,627 #[cfg(feature = "exp-preserve-order")]628 preserve_order,629 } => self.to_yaml(630 s,631 *padding,632 #[cfg(feature = "exp-preserve-order")]633 *preserve_order,634 )?,635 ManifestFormat::Json {636 padding,637 #[cfg(feature = "exp-preserve-order")]638 preserve_order,639 } => self.to_json(640 s,641 *padding,642 #[cfg(feature = "exp-preserve-order")]643 *preserve_order,644 )?,645 ManifestFormat::ToString => self.to_string(s)?,646 ManifestFormat::String => match self {647 Self::Str(s) => s.clone(),648 _ => throw!(StringManifestOutputIsNotAString),649 },650 })651 }652653 /// For manifestification654 pub fn to_json(655 &self,656 s: State,657 padding: usize,658 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,659 ) -> Result<IStr> {660 manifest_json_ex(661 s,662 self,663 &ManifestJsonOptions {664 padding: &" ".repeat(padding),665 mtype: if padding == 0 {666 ManifestType::Minify667 } else {668 ManifestType::Manifest669 },670 newline: "\n",671 key_val_sep: ": ",672 #[cfg(feature = "exp-preserve-order")]673 preserve_order,674 },675 )676 .map(Into::into)677 }678679 /// Calls `std.manifestJson`680 pub fn to_std_json(681 &self,682 s: State,683 padding: usize,684 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,685 ) -> Result<Rc<str>> {686 manifest_json_ex(687 s,688 self,689 &ManifestJsonOptions {690 padding: &" ".repeat(padding),691 mtype: ManifestType::Std,692 newline: "\n",693 key_val_sep: ": ",694 #[cfg(feature = "exp-preserve-order")]695 preserve_order,696 },697 )698 .map(Into::into)699 }700701 pub fn to_yaml(702 &self,703 s: State,704 padding: usize,705 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,706 ) -> Result<IStr> {707 let padding = &" ".repeat(padding);708 manifest_yaml_ex(709 s,710 self,711 &ManifestYamlOptions {712 padding,713 arr_element_padding: padding,714 quote_keys: false,715 #[cfg(feature = "exp-preserve-order")]716 preserve_order,717 },718 )719 .map(Into::into)720 }721 pub fn into_indexable(self) -> Result<IndexableVal> {722 Ok(match self {723 Val::Str(s) => IndexableVal::Str(s),724 Val::Arr(arr) => IndexableVal::Arr(arr),725 _ => throw!(ValueIsNotIndexable(self.value_type())),726 })727 }728}729730const fn is_function_like(val: &Val) -> bool {731 matches!(val, Val::Func(_))732}733734/// Native implementation of `std.primitiveEquals`735pub fn primitive_equals(val_a: &Val, val_b: &Val) -> Result<bool> {736 Ok(match (val_a, val_b) {737 (Val::Bool(a), Val::Bool(b)) => a == b,738 (Val::Null, Val::Null) => true,739 (Val::Str(a), Val::Str(b)) => a == b,740 (Val::Num(a), Val::Num(b)) => (a - b).abs() <= f64::EPSILON,741 (Val::Arr(_), Val::Arr(_)) => throw!(RuntimeError(742 "primitiveEquals operates on primitive types, got array".into(),743 )),744 (Val::Obj(_), Val::Obj(_)) => throw!(RuntimeError(745 "primitiveEquals operates on primitive types, got object".into(),746 )),747 (a, b) if is_function_like(a) && is_function_like(b) => {748 throw!(RuntimeError("cannot test equality of functions".into()))749 }750 (_, _) => false,751 })752}753754/// Native implementation of `std.equals`755pub fn equals(s: State, val_a: &Val, val_b: &Val) -> Result<bool> {756 if val_a.value_type() != val_b.value_type() {757 return Ok(false);758 }759 match (val_a, val_b) {760 (Val::Arr(a), Val::Arr(b)) => {761 if ArrValue::ptr_eq(a, b) {762 return Ok(true);763 }764 if a.len() != b.len() {765 return Ok(false);766 }767 for (a, b) in a.iter(s.clone()).zip(b.iter(s.clone())) {768 if !equals(s.clone(), &a?, &b?)? {769 return Ok(false);770 }771 }772 Ok(true)773 }774 (Val::Obj(a), Val::Obj(b)) => {775 if ObjValue::ptr_eq(a, b) {776 return Ok(true);777 }778 let fields = a.fields(779 #[cfg(feature = "exp-preserve-order")]780 false,781 );782 if fields783 != b.fields(784 #[cfg(feature = "exp-preserve-order")]785 false,786 ) {787 return Ok(false);788 }789 for field in fields {790 if !equals(791 s.clone(),792 &a.get(s.clone(), field.clone())?.expect("field exists"),793 &b.get(s.clone(), field)?.expect("field exists"),794 )? {795 return Ok(false);796 }797 }798 Ok(true)799 }800 (a, b) => Ok(primitive_equals(a, b)?),801 }802}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 // TODO: use div_ceil177 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)]190// may contrain other ArrValue191#[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 }209210 /// # Panics211 /// If a > b212 pub fn new_range(a: i32, b: i32) -> Self {213 assert!(a <= b);214 Self::Range(a, b)215 }216217 /// # Panics218 /// If passed numbers are incorrect219 #[must_use]220 pub fn slice(self, from: Option<usize>, to: Option<usize>, step: Option<usize>) -> Self {221 let len = self.len();222 let from = from.unwrap_or(0);223 let to = to.unwrap_or(len).min(len);224 let step = step.unwrap_or(1);225 assert!(from < to);226 assert!(step > 0);227228 Self::Slice(Box::new(Slice {229 inner: self,230 from: from as u32,231 to: to as u32,232 step: step as u32,233 }))234 }235236 pub fn len(&self) -> usize {237 match self {238 Self::Bytes(i) => i.len(),239 Self::Lazy(l) => l.len(),240 Self::Eager(e) => e.len(),241 Self::Extended(v) => v.0.len() + v.1.len(),242 Self::Range(a, b) => a.abs_diff(*b) as usize + 1,243 Self::Reversed(i) => i.len(),244 Self::Slice(s) => s.len(),245 }246 }247248 pub fn is_empty(&self) -> bool {249 self.len() == 0250 }251252 pub fn get(&self, s: State, index: usize) -> Result<Option<Val>> {253 match self {254 Self::Bytes(i) => i255 .get(index)256 .map_or(Ok(None), |v| Ok(Some(Val::Num(f64::from(*v))))),257 Self::Lazy(vec) => {258 if let Some(v) = vec.get(index) {259 Ok(Some(v.evaluate(s)?))260 } else {261 Ok(None)262 }263 }264 Self::Eager(vec) => Ok(vec.get(index).cloned()),265 Self::Extended(v) => {266 let a_len = v.0.len();267 if a_len > index {268 v.0.get(s, index)269 } else {270 v.1.get(s, index - a_len)271 }272 }273 Self::Range(a, _) => {274 if index >= self.len() {275 return Ok(None);276 }277 Ok(Some(Val::Num(((*a as isize) + index as isize) as f64)))278 }279 Self::Reversed(v) => {280 let len = v.len();281 if index >= len {282 return Ok(None);283 }284 v.get(s, len - index - 1)285 }286 Self::Slice(v) => {287 let index = v.from() + index * v.step();288 if index >= v.to() {289 return Ok(None);290 }291 v.inner.get(s, index as usize)292 }293 }294 }295296 pub fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {297 match self {298 Self::Bytes(i) => i299 .get(index)300 .map(|b| Thunk::evaluated(Val::Num(f64::from(*b)))),301 Self::Lazy(vec) => vec.get(index).cloned(),302 Self::Eager(vec) => vec.get(index).cloned().map(Thunk::evaluated),303 Self::Extended(v) => {304 let a_len = v.0.len();305 if a_len > index {306 v.0.get_lazy(index)307 } else {308 v.1.get_lazy(index - a_len)309 }310 }311 Self::Range(a, _) => {312 if index >= self.len() {313 return None;314 }315 Some(Thunk::evaluated(Val::Num(316 ((*a as isize) + index as isize) as f64,317 )))318 }319 Self::Reversed(v) => {320 let len = v.len();321 if index >= len {322 return None;323 }324 v.get_lazy(len - index - 1)325 }326 Self::Slice(s) => {327 let index = s.from() + index * s.step();328 if index >= s.to() {329 return None;330 }331 s.inner.get_lazy(index as usize)332 }333 }334 }335336 pub fn evaluated(&self, s: State) -> Result<Cc<Vec<Val>>> {337 Ok(match self {338 Self::Bytes(i) => {339 let mut out = Vec::with_capacity(i.len());340 for v in i.iter() {341 out.push(Val::Num(f64::from(*v)));342 }343 Cc::new(out)344 }345 Self::Lazy(vec) => {346 let mut out = Vec::with_capacity(vec.len());347 for item in vec.iter() {348 out.push(item.evaluate(s.clone())?);349 }350 Cc::new(out)351 }352 Self::Eager(vec) => vec.clone(),353 Self::Extended(_v) => {354 let mut out = Vec::with_capacity(self.len());355 for item in self.iter(s) {356 out.push(item?);357 }358 Cc::new(out)359 }360 Self::Range(a, b) => {361 let mut out = Vec::with_capacity(self.len());362 for i in *a..*b {363 out.push(Val::Num(f64::from(i)));364 }365 Cc::new(out)366 }367 Self::Reversed(r) => {368 let mut r = r.evaluated(s)?;369 Cc::update_with(&mut r, |v| v.reverse());370 r371 }372 Self::Slice(v) => {373 let mut out = Vec::with_capacity(v.inner.len());374 for v in v375 .inner376 .iter_lazy()377 .skip(v.from())378 .take(v.to() - v.from())379 .step_by(v.step())380 {381 out.push(v.evaluate(s.clone())?);382 }383 Cc::new(out)384 }385 })386 }387388 pub fn iter(&self, s: State) -> impl DoubleEndedIterator<Item = Result<Val>> + '_ {389 (0..self.len()).map(move |idx| match self {390 Self::Bytes(b) => Ok(Val::Num(f64::from(b[idx]))),391 Self::Lazy(l) => l[idx].evaluate(s.clone()),392 Self::Eager(e) => Ok(e[idx].clone()),393 Self::Extended(..) | Self::Range(..) | Self::Reversed(..) | Self::Slice(..) => {394 self.get(s.clone(), idx).map(|e| e.expect("idx < len"))395 }396 })397 }398399 pub fn iter_lazy(&self) -> impl DoubleEndedIterator<Item = Thunk<Val>> + '_ {400 (0..self.len()).map(move |idx| match self {401 Self::Bytes(b) => Thunk::evaluated(Val::Num(f64::from(b[idx]))),402 Self::Lazy(l) => l[idx].clone(),403 Self::Eager(e) => Thunk::evaluated(e[idx].clone()),404 Self::Slice(..) | Self::Extended(..) | Self::Range(..) | Self::Reversed(..) => {405 self.get_lazy(idx).expect("idx < len")406 }407 })408 }409410 #[must_use]411 pub fn reversed(self) -> Self {412 Self::Reversed(Box::new(self))413 }414415 pub fn map(self, s: State, mapper: impl Fn(Val) -> Result<Val>) -> Result<Self> {416 let mut out = Vec::with_capacity(self.len());417418 for value in self.iter(s) {419 out.push(mapper(value?)?);420 }421422 Ok(Self::Eager(Cc::new(out)))423 }424425 pub fn filter(self, s: State, filter: impl Fn(&Val) -> Result<bool>) -> Result<Self> {426 let mut out = Vec::with_capacity(self.len());427428 for value in self.iter(s) {429 let value = value?;430 if filter(&value)? {431 out.push(value);432 }433 }434435 Ok(Self::Eager(Cc::new(out)))436 }437438 pub fn ptr_eq(a: &Self, b: &Self) -> bool {439 match (a, b) {440 (Self::Lazy(a), Self::Lazy(b)) => Cc::ptr_eq(a, b),441 (Self::Eager(a), Self::Eager(b)) => Cc::ptr_eq(a, b),442 _ => false,443 }444 }445}446447impl From<Vec<Thunk<Val>>> for ArrValue {448 fn from(v: Vec<Thunk<Val>>) -> Self {449 Self::Lazy(Cc::new(v))450 }451}452453impl From<Vec<Val>> for ArrValue {454 fn from(v: Vec<Val>) -> Self {455 Self::Eager(Cc::new(v))456 }457}458459#[allow(clippy::module_name_repetitions)]460pub enum IndexableVal {461 Str(IStr),462 Arr(ArrValue),463}464impl IndexableVal {465 pub fn slice(466 self,467 index: Option<BoundedUsize<0, { i32::MAX as usize }>>,468 end: Option<BoundedUsize<0, { i32::MAX as usize }>>,469 step: Option<BoundedUsize<1, { i32::MAX as usize }>>,470 ) -> Result<Self> {471 match &self {472 IndexableVal::Str(s) => {473 let index = index.as_deref().copied().unwrap_or(0);474 let end = end.as_deref().copied().unwrap_or(usize::MAX);475 let step = step.as_deref().copied().unwrap_or(1);476477 if index >= end {478 return Ok(Self::Str("".into()));479 }480481 Ok(Self::Str(482 (s.chars()483 .skip(index)484 .take(end - index)485 .step_by(step)486 .collect::<String>())487 .into(),488 ))489 }490 IndexableVal::Arr(arr) => {491 let index = index.as_deref().copied().unwrap_or(0);492 let end = end.as_deref().copied().unwrap_or(usize::MAX).min(arr.len());493 let step = step.as_deref().copied().unwrap_or(1);494495 if index >= end {496 return Ok(Self::Arr(ArrValue::new_eager()));497 }498499 Ok(Self::Arr(ArrValue::Slice(Box::new(Slice {500 inner: arr.clone(),501 from: index as u32,502 to: end as u32,503 step: step as u32,504 }))))505 }506 }507 }508}509510#[derive(Debug, Clone, Trace)]511pub enum Val {512 Bool(bool),513 Null,514 Str(IStr),515 Num(f64),516 Arr(ArrValue),517 Obj(ObjValue),518 Func(FuncVal),519}520521impl From<IndexableVal> for Val {522 fn from(v: IndexableVal) -> Self {523 match v {524 IndexableVal::Str(s) => Self::Str(s),525 IndexableVal::Arr(a) => Self::Arr(a),526 }527 }528}529530#[cfg(target_pointer_width = "64")]531static_assertions::assert_eq_size!(Val, [u8; 32]);532533impl Val {534 pub const fn as_bool(&self) -> Option<bool> {535 match self {536 Self::Bool(v) => Some(*v),537 _ => None,538 }539 }540 pub const fn as_null(&self) -> Option<()> {541 match self {542 Self::Null => Some(()),543 _ => None,544 }545 }546 pub fn as_str(&self) -> Option<IStr> {547 match self {548 Self::Str(s) => Some(s.clone()),549 _ => None,550 }551 }552 pub const fn as_num(&self) -> Option<f64> {553 match self {554 Self::Num(n) => Some(*n),555 _ => None,556 }557 }558 pub fn as_arr(&self) -> Option<ArrValue> {559 match self {560 Self::Arr(a) => Some(a.clone()),561 _ => None,562 }563 }564 pub fn as_obj(&self) -> Option<ObjValue> {565 match self {566 Self::Obj(o) => Some(o.clone()),567 _ => None,568 }569 }570 pub fn as_func(&self) -> Option<FuncVal> {571 match self {572 Self::Func(f) => Some(f.clone()),573 _ => None,574 }575 }576577 /// Creates `Val::Num` after checking for numeric overflow.578 /// As numbers are `f64`, we can just check for their finity.579 pub fn new_checked_num(num: f64) -> Result<Self> {580 if num.is_finite() {581 Ok(Self::Num(num))582 } else {583 throw!(RuntimeError("overflow".into()))584 }585 }586587 pub const fn value_type(&self) -> ValType {588 match self {589 Self::Str(..) => ValType::Str,590 Self::Num(..) => ValType::Num,591 Self::Arr(..) => ValType::Arr,592 Self::Obj(..) => ValType::Obj,593 Self::Bool(_) => ValType::Bool,594 Self::Null => ValType::Null,595 Self::Func(..) => ValType::Func,596 }597 }598599 pub fn to_string(&self, s: State) -> Result<IStr> {600 Ok(match self {601 Self::Bool(true) => "true".into(),602 Self::Bool(false) => "false".into(),603 Self::Null => "null".into(),604 Self::Str(s) => s.clone(),605 v => manifest_json_ex(606 s,607 v,608 &ManifestJsonOptions {609 padding: "",610 mtype: ManifestType::ToString,611 newline: "\n",612 key_val_sep: ": ",613 #[cfg(feature = "exp-preserve-order")]614 preserve_order: false,615 },616 )?617 .into(),618 })619 }620621 /// Expects value to be object, outputs (key, manifested value) pairs622 pub fn manifest_multi(&self, s: State, ty: &ManifestFormat) -> Result<Vec<(IStr, IStr)>> {623 let obj = match self {624 Self::Obj(obj) => obj,625 _ => throw!(MultiManifestOutputIsNotAObject),626 };627 let keys = obj.fields(628 #[cfg(feature = "exp-preserve-order")]629 ty.preserve_order(),630 );631 let mut out = Vec::with_capacity(keys.len());632 for key in keys {633 let value = obj634 .get(s.clone(), key.clone())?635 .expect("item in object")636 .manifest(s.clone(), ty)?;637 out.push((key, value));638 }639 Ok(out)640 }641642 /// Expects value to be array, outputs manifested values643 pub fn manifest_stream(&self, s: State, ty: &ManifestFormat) -> Result<Vec<IStr>> {644 let arr = match self {645 Self::Arr(a) => a,646 _ => throw!(StreamManifestOutputIsNotAArray),647 };648 let mut out = Vec::with_capacity(arr.len());649 for i in arr.iter(s.clone()) {650 out.push(i?.manifest(s.clone(), ty)?);651 }652 Ok(out)653 }654655 pub fn manifest(&self, s: State, ty: &ManifestFormat) -> Result<IStr> {656 Ok(match ty {657 ManifestFormat::YamlStream(format) => {658 let arr = match self {659 Self::Arr(a) => a,660 _ => throw!(StreamManifestOutputIsNotAArray),661 };662 let mut out = String::new();663664 match format as &ManifestFormat {665 ManifestFormat::YamlStream(_) => throw!(StreamManifestOutputCannotBeRecursed),666 ManifestFormat::String => throw!(StreamManifestCannotNestString),667 _ => {}668 };669670 if !arr.is_empty() {671 for v in arr.iter(s.clone()) {672 out.push_str("---\n");673 out.push_str(&v?.manifest(s.clone(), format)?);674 out.push('\n');675 }676 out.push_str("...");677 }678679 out.into()680 }681 ManifestFormat::Yaml {682 padding,683 #[cfg(feature = "exp-preserve-order")]684 preserve_order,685 } => self.to_yaml(686 s,687 *padding,688 #[cfg(feature = "exp-preserve-order")]689 *preserve_order,690 )?,691 ManifestFormat::Json {692 padding,693 #[cfg(feature = "exp-preserve-order")]694 preserve_order,695 } => self.to_json(696 s,697 *padding,698 #[cfg(feature = "exp-preserve-order")]699 *preserve_order,700 )?,701 ManifestFormat::ToString => self.to_string(s)?,702 ManifestFormat::String => match self {703 Self::Str(s) => s.clone(),704 _ => throw!(StringManifestOutputIsNotAString),705 },706 })707 }708709 /// For manifestification710 pub fn to_json(711 &self,712 s: State,713 padding: usize,714 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,715 ) -> Result<IStr> {716 manifest_json_ex(717 s,718 self,719 &ManifestJsonOptions {720 padding: &" ".repeat(padding),721 mtype: if padding == 0 {722 ManifestType::Minify723 } else {724 ManifestType::Manifest725 },726 newline: "\n",727 key_val_sep: ": ",728 #[cfg(feature = "exp-preserve-order")]729 preserve_order,730 },731 )732 .map(Into::into)733 }734735 /// Calls `std.manifestJson`736 pub fn to_std_json(737 &self,738 s: State,739 padding: usize,740 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,741 ) -> Result<Rc<str>> {742 manifest_json_ex(743 s,744 self,745 &ManifestJsonOptions {746 padding: &" ".repeat(padding),747 mtype: ManifestType::Std,748 newline: "\n",749 key_val_sep: ": ",750 #[cfg(feature = "exp-preserve-order")]751 preserve_order,752 },753 )754 .map(Into::into)755 }756757 pub fn to_yaml(758 &self,759 s: State,760 padding: usize,761 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,762 ) -> Result<IStr> {763 let padding = &" ".repeat(padding);764 manifest_yaml_ex(765 s,766 self,767 &ManifestYamlOptions {768 padding,769 arr_element_padding: padding,770 quote_keys: false,771 #[cfg(feature = "exp-preserve-order")]772 preserve_order,773 },774 )775 .map(Into::into)776 }777 pub fn into_indexable(self) -> Result<IndexableVal> {778 Ok(match self {779 Val::Str(s) => IndexableVal::Str(s),780 Val::Arr(arr) => IndexableVal::Arr(arr),781 _ => throw!(ValueIsNotIndexable(self.value_type())),782 })783 }784}785786const fn is_function_like(val: &Val) -> bool {787 matches!(val, Val::Func(_))788}789790/// Native implementation of `std.primitiveEquals`791pub fn primitive_equals(val_a: &Val, val_b: &Val) -> Result<bool> {792 Ok(match (val_a, val_b) {793 (Val::Bool(a), Val::Bool(b)) => a == b,794 (Val::Null, Val::Null) => true,795 (Val::Str(a), Val::Str(b)) => a == b,796 (Val::Num(a), Val::Num(b)) => (a - b).abs() <= f64::EPSILON,797 (Val::Arr(_), Val::Arr(_)) => throw!(RuntimeError(798 "primitiveEquals operates on primitive types, got array".into(),799 )),800 (Val::Obj(_), Val::Obj(_)) => throw!(RuntimeError(801 "primitiveEquals operates on primitive types, got object".into(),802 )),803 (a, b) if is_function_like(a) && is_function_like(b) => {804 throw!(RuntimeError("cannot test equality of functions".into()))805 }806 (_, _) => false,807 })808}809810/// Native implementation of `std.equals`811pub fn equals(s: State, val_a: &Val, val_b: &Val) -> Result<bool> {812 if val_a.value_type() != val_b.value_type() {813 return Ok(false);814 }815 match (val_a, val_b) {816 (Val::Arr(a), Val::Arr(b)) => {817 if ArrValue::ptr_eq(a, b) {818 return Ok(true);819 }820 if a.len() != b.len() {821 return Ok(false);822 }823 for (a, b) in a.iter(s.clone()).zip(b.iter(s.clone())) {824 if !equals(s.clone(), &a?, &b?)? {825 return Ok(false);826 }827 }828 Ok(true)829 }830 (Val::Obj(a), Val::Obj(b)) => {831 if ObjValue::ptr_eq(a, b) {832 return Ok(true);833 }834 let fields = a.fields(835 #[cfg(feature = "exp-preserve-order")]836 false,837 );838 if fields839 != b.fields(840 #[cfg(feature = "exp-preserve-order")]841 false,842 ) {843 return Ok(false);844 }845 for field in fields {846 if !equals(847 s.clone(),848 &a.get(s.clone(), field.clone())?.expect("field exists"),849 &b.get(s.clone(), field)?.expect("field exists"),850 )? {851 return Ok(false);852 }853 }854 Ok(true)855 }856 (a, b) => Ok(primitive_equals(a, b)?),857 }858}