1use std::{2 any::Any,3 cell::RefCell,4 fmt::{self, Debug},5 mem::replace,6 rc::Rc,7};89use jrsonnet_gcmodule::{Cc, Trace};10use jrsonnet_interner::{IBytes, IStr};11use jrsonnet_ir::TrivialVal;1213use super::{ArrValue, arridx};14use crate::{15 Context, Error, ObjValue, Result, Thunk, Val,16 analyze::LExpr,17 error::ErrorKind::InfiniteRecursionDetected,18 evaluate::evaluate,19 function::NativeFn,20 typed::{IntoUntyped, Typed},21 val::ThunkValue,22};2324pub trait ArrayLike: Any + Trace + Debug {25 fn len32(&self) -> u32;26 fn is_empty(&self) -> bool {27 self.len32() == 028 }29 fn get32(&self, index: u32) -> Result<Option<Val>>;30 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>>;3132 fn is_cheap(&self) -> bool {33 false34 }35}36trait ArrayCheap {37 fn get32(&self, index: u32) -> Option<Val>;38 fn len32(&self) -> u32;39}40impl<T> ArrayLike for T41where42 T: Any + Trace + Debug + ArrayCheap,43{44 fn len32(&self) -> u32 {45 <T as ArrayCheap>::len32(self)46 }4748 fn get32(&self, index: u32) -> Result<Option<Val>> {49 Ok(<T as ArrayCheap>::get32(self, index))50 }5152 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {53 <T as ArrayCheap>::get32(self, index).map(Thunk::evaluated)54 }5556 fn is_cheap(&self) -> bool {57 true58 }59}6061impl ArrayCheap for () {62 fn len32(&self) -> u32 {63 064 }65 fn get32(&self, _index: u32) -> Option<Val> {66 None67 }68}6970#[derive(Debug, Trace)]71pub struct SliceArray {72 pub(crate) inner: ArrValue,73 pub(crate) from: u32,74 pub(crate) to: u32,75 pub(crate) step: u32,76}7778impl SliceArray {79 fn map_idx(&self, index: u32) -> u32 {80 self.from + self.step * index81 }82}83impl ArrayLike for SliceArray {84 fn len32(&self) -> u32 {85 (self.to - self.from).div_ceil(self.step)86 }8788 fn get32(&self, index: u32) -> Result<Option<Val>> {89 self.inner.get32(self.map_idx(index))90 }9192 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {93 self.inner.get_lazy32(self.map_idx(index))94 }9596 fn is_cheap(&self) -> bool {97 self.inner.is_cheap()98 }99}100101impl ArrayCheap for IBytes {102 fn len32(&self) -> u32 {103 arridx(self.as_slice().len())104 }105 fn get32(&self, index: u32) -> Option<Val> {106 self.as_slice()107 .get(index as usize)108 .map(|v| Val::Num((*v).into()))109 }110}111112impl ArrayCheap for Rc<Vec<TrivialVal>> {113 fn get32(&self, index: u32) -> Option<Val> {114 self.as_slice()115 .get(index as usize)116 .map(|tv| tv.clone().into())117 }118119 fn len32(&self) -> u32 {120 arridx(self.as_slice().len())121 }122}123124#[derive(Debug, Trace, Clone)]125enum ArrayThunk {126 Computed(Val),127 Errored(Error),128 Waiting,129 Pending,130}131132#[derive(Debug, Trace, Clone)]133pub struct ExprArray {134 ctx: Context,135 src: Rc<Vec<LExpr>>,136 cached: Cc<RefCell<Vec<ArrayThunk>>>,137}138impl ExprArray {139 pub fn new(ctx: Context, src: Rc<Vec<LExpr>>) -> Self {140 Self {141 ctx,142 cached: Cc::new(RefCell::new(vec![ArrayThunk::Waiting; src.len()])),143 src,144 }145 }146}147impl ArrayLike for ExprArray {148 fn len32(&self) -> u32 {149 arridx(self.cached.borrow().len())150 }151 fn get32(&self, index: u32) -> Result<Option<Val>> {152 if index >= self.len32() {153 return Ok(None);154 }155 match &self.cached.borrow()[index as usize] {156 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),157 ArrayThunk::Errored(e) => return Err(e.clone()),158 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),159 ArrayThunk::Waiting => {}160 }161162 let ArrayThunk::Waiting = replace(163 &mut self.cached.borrow_mut()[index as usize],164 ArrayThunk::Pending,165 ) else {166 unreachable!()167 };168169 let result = evaluate(self.ctx.clone(), &self.src[index as usize]);170 match result {171 Ok(new_value) => {172 self.cached.borrow_mut()[index as usize] = ArrayThunk::Computed(new_value.clone());173 Ok(Some(new_value))174 }175 Err(e) => {176 self.cached.borrow_mut()[index as usize] = ArrayThunk::Waiting;177 Err(e)178 }179 }180 }181 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {182 #[derive(Trace)]183 struct ExprArrThunk {184 expr: ExprArray,185 index: u32,186 }187 impl ThunkValue for ExprArrThunk {188 type Output = Val;189190 fn get(&self) -> Result<Self::Output> {191 self.expr192 .get32(self.index)193 .transpose()194 .expect("index checked")195 }196 }197198 if index >= self.len32() {199 return None;200 }201 match &self.cached.borrow()[index as usize] {202 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),203 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),204 ArrayThunk::Waiting | ArrayThunk::Pending => {}205 }206207 Some(Thunk::new(ExprArrThunk {208 expr: self.clone(),209 index,210 }))211 }212 fn is_cheap(&self) -> bool {213 false214 }215}216217#[derive(Trace, Debug)]218pub struct ExtendedArray {219 pub a: ArrValue,220 pub b: ArrValue,221 split: u32,222 len: u32,223}224impl ExtendedArray {225 pub fn new(a: ArrValue, b: ArrValue) -> Option<Self> {226 let a_len = a.len32();227 let b_len = b.len32();228 let len = a_len.checked_add(b_len)?;229 Some(Self {230 a,231 b,232 split: a_len,233 len,234 })235 }236}237238struct WithExactSize<I>(I, usize);239impl<I, T> Iterator for WithExactSize<I>240where241 I: Iterator<Item = T>,242{243 type Item = T;244245 fn next(&mut self) -> Option<Self::Item> {246 self.0.next()247 }248 fn nth(&mut self, n: usize) -> Option<Self::Item> {249 self.0.nth(n)250 }251 fn size_hint(&self) -> (usize, Option<usize>) {252 (self.1, Some(self.1))253 }254}255impl<I> DoubleEndedIterator for WithExactSize<I>256where257 I: DoubleEndedIterator,258{259 fn next_back(&mut self) -> Option<Self::Item> {260 self.0.next_back()261 }262 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {263 self.0.nth_back(n)264 }265}266impl<I> ExactSizeIterator for WithExactSize<I>267where268 I: Iterator,269{270 fn len(&self) -> usize {271 self.1272 }273}274impl ArrayLike for ExtendedArray {275 fn get32(&self, index: u32) -> Result<Option<Val>> {276 if self.split > index {277 self.a.get32(index)278 } else {279 self.b.get32(index - self.split)280 }281 }282 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {283 if self.split > index {284 self.a.get_lazy32(index)285 } else {286 self.b.get_lazy32(index - self.split)287 }288 }289290 fn len32(&self) -> u32 {291 self.len292 }293294 fn is_cheap(&self) -> bool {295 self.a.is_cheap() && self.b.is_cheap()296 }297}298299impl<T> ArrayLike for Vec<T>300where301 T: IntoUntyped + Trace + fmt::Debug,302 for<'a> &'a T: IntoUntyped,303{304 fn len32(&self) -> u32 {305 self.as_slice().len().try_into().unwrap_or(u32::MAX)306 }307308 fn get32(&self, index: u32) -> Result<Option<Val>> {309 let Some(elem) = self.as_slice().get(index as usize) else {310 return Ok(None);311 };312 IntoUntyped::into_untyped(elem).map(Some)313 }314315 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {316 let elem = self.as_slice().get(index as usize)?;317 Some(IntoUntyped::into_lazy_untyped(elem))318 }319320 fn is_cheap(&self) -> bool {321 !T::provides_lazy()322 }323}324325326#[derive(Debug, Trace, PartialEq, Eq)]327pub struct RangeArray {328 start: i32,329 end: i32,330}331impl RangeArray {332 pub fn empty() -> Self {333 Self::new_exclusive(0, 0)334 }335 pub fn new_exclusive(start: i32, end: i32) -> Self {336 end.checked_sub(1)337 .map_or_else(Self::empty, |end| Self { start, end })338 }339 pub fn new_inclusive(start: i32, end: i32) -> Self {340 Self { start, end }341 }342 #[expect(343 clippy::cast_sign_loss,344 reason = "the math is valid with wrapping, sign loss works as intended"345 )]346 fn size(&self) -> u32 {347 (self.end as u32)348 .wrapping_sub(self.start as u32)349 .wrapping_add(1)350 }351 fn range(&self) -> impl ExactSizeIterator<Item = i32> + DoubleEndedIterator {352 WithExactSize(self.start..=self.end, self.size() as usize)353 }354}355impl ArrayCheap for RangeArray {356 fn get32(&self, index: u32) -> Option<Val> {357 self.range().nth(index as usize).map(|i| Val::Num(i.into()))358 }359 fn len32(&self) -> u32 {360 self.size()361 }362}363364#[derive(Debug, Trace)]365pub struct ReverseArray(pub ArrValue);366impl ArrayLike for ReverseArray {367 fn len32(&self) -> u32 {368 self.0.len32()369 }370371 fn get32(&self, index: u32) -> Result<Option<Val>> {372 self.0.get32(self.0.len32() - index - 1)373 }374375 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {376 self.0.get_lazy32(self.0.len32() - index - 1)377 }378379 fn is_cheap(&self) -> bool {380 self.0.is_cheap()381 }382}383384#[derive(Trace, Clone, Debug)]385pub enum ArrayMapper {386 Plain(NativeFn!((Val) -> Val)),387 WithIndex(NativeFn!((u32, Val) -> Val)),388}389390#[derive(Trace, Debug, Clone)]391pub struct MappedArray {392 inner: ArrValue,393 cached: Cc<RefCell<Vec<ArrayThunk>>>,394 mapper: ArrayMapper,395}396impl MappedArray {397 pub fn new(inner: ArrValue, mapper: ArrayMapper) -> Self {398 let len = inner.len32();399 Self {400 inner,401 cached: Cc::new(RefCell::new(vec![ArrayThunk::Waiting; len as usize])),402 mapper,403 }404 }405 fn evaluate(&self, index: u32, value: Val) -> Result<Val> {406 match &self.mapper {407 ArrayMapper::Plain(f) => f.call(value),408 ArrayMapper::WithIndex(f) => f.call(index, value),409 }410 }411}412impl ArrayLike for MappedArray {413 fn len32(&self) -> u32 {414 arridx(self.cached.borrow().len())415 }416417 fn get32(&self, index: u32) -> Result<Option<Val>> {418 if index >= self.len32() {419 return Ok(None);420 }421 match &self.cached.borrow()[index as usize] {422 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),423 ArrayThunk::Errored(e) => return Err(e.clone()),424 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),425 ArrayThunk::Waiting => {}426 }427428 let ArrayThunk::Waiting = replace(429 &mut self.cached.borrow_mut()[index as usize],430 ArrayThunk::Pending,431 ) else {432 unreachable!()433 };434435 let val = self436 .inner437 .get32(index)438 .transpose()439 .expect("index checked")440 .and_then(|r| self.evaluate(index, r));441442 let new_value = match val {443 Ok(v) => v,444 Err(e) => {445 self.cached.borrow_mut()[index as usize] = ArrayThunk::Errored(e.clone());446 return Err(e);447 }448 };449 self.cached.borrow_mut()[index as usize] = ArrayThunk::Computed(new_value.clone());450 Ok(Some(new_value))451 }452 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {453 #[derive(Trace)]454 struct MappedArrayThunk {455 arr: MappedArray,456 index: u32,457 }458 impl ThunkValue for MappedArrayThunk {459 type Output = Val;460461 fn get(&self) -> Result<Self::Output> {462 self.arr463 .get32(self.index)464 .transpose()465 .expect("index checked")466 }467 }468469 if index >= self.len32() {470 return None;471 }472 match &self.cached.borrow()[index as usize] {473 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),474 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),475 ArrayThunk::Waiting | ArrayThunk::Pending => {}476 }477478 Some(Thunk::new(MappedArrayThunk {479 arr: self.clone(),480 index,481 }))482 }483}484#[derive(Trace, Debug, Clone)]485pub struct MakeArray {486 cached: Cc<RefCell<Vec<ArrayThunk>>>,487 mapper: NativeFn!((u32,)->Val),488}489impl MakeArray {490 pub fn new(len: u32, mapper: NativeFn!((u32)->Val)) -> Self {491 Self {492 cached: Cc::new(RefCell::new(vec![ArrayThunk::Waiting; len as usize])),493 mapper,494 }495 }496}497impl ArrayLike for MakeArray {498 fn len32(&self) -> u32 {499 arridx(self.cached.borrow().len())500 }501502 fn get32(&self, index: u32) -> Result<Option<Val>> {503 if index >= self.len32() {504 return Ok(None);505 }506 match &self.cached.borrow()[index as usize] {507 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),508 ArrayThunk::Errored(e) => return Err(e.clone()),509 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),510 ArrayThunk::Waiting => {}511 }512513 let ArrayThunk::Waiting = replace(514 &mut self.cached.borrow_mut()[index as usize],515 ArrayThunk::Pending,516 ) else {517 unreachable!()518 };519520 let val = self.mapper.call(index);521522 let new_value = match val {523 Ok(v) => v,524 Err(e) => {525 self.cached.borrow_mut()[index as usize] = ArrayThunk::Errored(e.clone());526 return Err(e);527 }528 };529 self.cached.borrow_mut()[index as usize] = ArrayThunk::Computed(new_value.clone());530 Ok(Some(new_value))531 }532 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {533 #[derive(Trace)]534 struct MakeArrayThunk {535 arr: MakeArray,536 index: u32,537 }538 impl ThunkValue for MakeArrayThunk {539 type Output = Val;540541 fn get(&self) -> Result<Self::Output> {542 self.arr543 .get32(self.index)544 .transpose()545 .expect("index checked")546 }547 }548549 if index >= self.len32() {550 return None;551 }552 match &self.cached.borrow()[index as usize] {553 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),554 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),555 ArrayThunk::Waiting | ArrayThunk::Pending => {}556 }557558 Some(Thunk::new(MakeArrayThunk {559 arr: self.clone(),560 index,561 }))562 }563}564565#[derive(Trace, Debug)]566pub struct RepeatedArray {567 data: ArrValue,568 repeats: u32,569 total_len: u32,570}571impl RepeatedArray {572 pub fn new(data: ArrValue, repeats: u32) -> Option<Self> {573 let total_len = data.len32().checked_mul(repeats)?;574 Some(Self {575 data,576 repeats,577 total_len,578 })579 }580 fn map_idx(&self, index: u32) -> Option<u32> {581 if index > self.total_len {582 return None;583 }584 Some(index % self.data.len32())585 }586}587588impl ArrayLike for RepeatedArray {589 fn len32(&self) -> u32 {590 self.total_len591 }592593 fn get32(&self, index: u32) -> Result<Option<Val>> {594 let Some(idx) = self.map_idx(index) else {595 return Ok(None);596 };597 self.data.get32(idx)598 }599600 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {601 let idx = self.map_idx(index)?;602 self.data.get_lazy32(idx)603 }604605 fn is_cheap(&self) -> bool {606 self.data.is_cheap()607 }608}609610#[derive(Trace, Debug)]611pub struct PickObjectValues {612 obj: ObjValue,613 keys: Vec<IStr>,614}615616impl PickObjectValues {617 pub fn new(obj: ObjValue, keys: Vec<IStr>) -> Self {618 Self { obj, keys }619 }620}621622impl ArrayLike for PickObjectValues {623 fn len32(&self) -> u32 {624 arridx(self.keys.len())625 }626627 fn get32(&self, index: u32) -> Result<Option<Val>> {628 let Some(key) = self.keys.as_slice().get(index as usize) else {629 return Ok(None);630 };631 Ok(Some(self.obj.get_or_bail(key.clone())?))632 }633634 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {635 let key = self.keys.as_slice().get(index as usize)?;636 Some(self.obj.get_lazy_or_bail(key.clone()))637 }638639 fn is_cheap(&self) -> bool {640 false641 }642}643644#[derive(Trace, Debug)]645pub struct PickObjectKeyValues {646 obj: ObjValue,647 keys: Vec<IStr>,648}649650impl PickObjectKeyValues {651 pub fn new(obj: ObjValue, keys: Vec<IStr>) -> Self {652 Self { obj, keys }653 }654}655656#[derive(Typed, IntoUntyped)]657pub struct KeyValue {658 key: IStr,659 value: Thunk<Val>,660}661662impl ArrayLike for PickObjectKeyValues {663 fn len32(&self) -> u32 {664 arridx(self.keys.len())665 }666667 fn get32(&self, index: u32) -> Result<Option<Val>> {668 let Some(key) = self.keys.as_slice().get(index as usize) else {669 return Ok(None);670 };671 Ok(Some(672 KeyValue::into_untyped(KeyValue {673 key: key.clone(),674 value: Thunk::evaluated(self.obj.get_or_bail(key.clone())?),675 })676 .expect("convertible"),677 ))678 }679680 fn get_lazy32(&self, index: u32) -> Option<Thunk<Val>> {681 let key = self.keys.as_slice().get(index as usize)?;682 683 684 Some(Thunk::evaluated(685 KeyValue::into_untyped(KeyValue {686 key: key.clone(),687 value: self.obj.get_lazy_or_bail(key.clone()),688 })689 .expect("convertible"),690 ))691 }692693 fn is_cheap(&self) -> bool {694 false695 }696}