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};1112use super::ArrValue;13use crate::{14 Context, Error, ObjValue, Result, Thunk, Val,15 analyze::LExpr,16 error::ErrorKind::InfiniteRecursionDetected,17 evaluate::evaluate,18 function::NativeFn,19 typed::{IntoUntyped, Typed},20 val::ThunkValue,21};2223pub trait ArrayLike: Any + Trace + Debug {24 fn len(&self) -> u32;25 fn is_empty(&self) -> bool {26 self.len() == 027 }28 fn get(&self, index: u32) -> Result<Option<Val>>;29 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>>;3031 fn is_cheap(&self) -> bool {32 false33 }34}35trait ArrayCheap {36 fn get(&self, index: u32) -> Option<Val>;37 fn len(&self) -> u32;38}39impl<T> ArrayLike for T40where41 T: Any + Trace + Debug + ArrayCheap,42{43 fn len(&self) -> u32 {44 <T as ArrayCheap>::len(self)45 }4647 fn get(&self, index: u32) -> Result<Option<Val>> {48 Ok(<T as ArrayCheap>::get(self, index))49 }5051 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {52 <T as ArrayCheap>::get(self, index).map(Thunk::evaluated)53 }5455 fn is_cheap(&self) -> bool {56 true57 }58}5960impl ArrayCheap for () {61 fn len(&self) -> u32 {62 063 }64 fn get(&self, _index: u32) -> Option<Val> {65 None66 }67}6869#[derive(Debug, Trace)]70pub struct SliceArray {71 pub(crate) inner: ArrValue,72 pub(crate) from: u32,73 pub(crate) to: u32,74 pub(crate) step: u32,75}7677impl SliceArray {78 fn map_idx(&self, index: u32) -> u32 {79 self.from + self.step * index80 }81}82impl ArrayLike for SliceArray {83 fn len(&self) -> u32 {84 (self.to - self.from).div_ceil(self.step)85 }8687 fn get(&self, index: u32) -> Result<Option<Val>> {88 self.inner.get(self.map_idx(index))89 }9091 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {92 self.inner.get_lazy(self.map_idx(index))93 }9495 fn is_cheap(&self) -> bool {96 self.inner.is_cheap()97 }98}99100impl ArrayCheap for IBytes {101 fn len(&self) -> u32 {102 self.as_slice().len() as u32103 }104 fn get(&self, index: u32) -> Option<Val> {105 self.as_slice()106 .get(index as usize)107 .map(|v| Val::Num((*v).into()))108 }109}110111#[derive(Debug, Trace, Clone)]112enum ArrayThunk {113 Computed(Val),114 Errored(Error),115 Waiting,116 Pending,117}118119#[derive(Debug, Trace, Clone)]120pub struct ExprArray {121 ctx: Context,122 src: Rc<Vec<LExpr>>,123 cached: Cc<RefCell<Vec<ArrayThunk>>>,124}125impl ExprArray {126 pub fn new(ctx: Context, src: Rc<Vec<LExpr>>) -> Self {127 Self {128 ctx,129 cached: Cc::new(RefCell::new(vec![ArrayThunk::Waiting; src.len()])),130 src,131 }132 }133}134impl ArrayLike for ExprArray {135 fn len(&self) -> u32 {136 self.cached.borrow().len() as u32137 }138 fn get(&self, index: u32) -> Result<Option<Val>> {139 if index >= self.len() {140 return Ok(None);141 }142 match &self.cached.borrow()[index as usize] {143 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),144 ArrayThunk::Errored(e) => return Err(e.clone()),145 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),146 ArrayThunk::Waiting => {}147 }148149 let ArrayThunk::Waiting = replace(150 &mut self.cached.borrow_mut()[index as usize],151 ArrayThunk::Pending,152 ) else {153 unreachable!()154 };155156 let new_value: Val = evaluate(self.ctx.clone(), &self.src[index as usize])?;157 self.cached.borrow_mut()[index as usize] = ArrayThunk::Computed(new_value.clone());158 Ok(Some(new_value))159 }160 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {161 #[derive(Trace)]162 struct ExprArrThunk {163 expr: ExprArray,164 index: u32,165 }166 impl ThunkValue for ExprArrThunk {167 type Output = Val;168169 fn get(&self) -> Result<Self::Output> {170 self.expr171 .get(self.index)172 .transpose()173 .expect("index checked")174 }175 }176177 if index >= self.len() {178 return None;179 }180 match &self.cached.borrow()[index as usize] {181 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),182 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),183 ArrayThunk::Waiting | ArrayThunk::Pending => {}184 }185186 Some(Thunk::new(ExprArrThunk {187 expr: self.clone(),188 index,189 }))190 }191 fn is_cheap(&self) -> bool {192 false193 }194}195196#[derive(Trace, Debug)]197pub struct ExtendedArray {198 pub a: ArrValue,199 pub b: ArrValue,200 split: u32,201 len: u32,202}203impl ExtendedArray {204 pub fn new(a: ArrValue, b: ArrValue) -> Option<Self> {205 let a_len = a.len();206 let b_len = b.len();207 let len = a_len.checked_add(b_len)?;208 Some(Self {209 a,210 b,211 split: a_len,212 len,213 })214 }215}216217struct WithExactSize<I>(I, usize);218impl<I, T> Iterator for WithExactSize<I>219where220 I: Iterator<Item = T>,221{222 type Item = T;223224 fn next(&mut self) -> Option<Self::Item> {225 self.0.next()226 }227 fn nth(&mut self, n: usize) -> Option<Self::Item> {228 self.0.nth(n)229 }230 fn size_hint(&self) -> (usize, Option<usize>) {231 (self.1, Some(self.1))232 }233}234impl<I> DoubleEndedIterator for WithExactSize<I>235where236 I: DoubleEndedIterator,237{238 fn next_back(&mut self) -> Option<Self::Item> {239 self.0.next_back()240 }241 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {242 self.0.nth_back(n)243 }244}245impl<I> ExactSizeIterator for WithExactSize<I>246where247 I: Iterator,248{249 fn len(&self) -> usize {250 self.1251 }252}253impl ArrayLike for ExtendedArray {254 fn get(&self, index: u32) -> Result<Option<Val>> {255 if self.split > index {256 self.a.get(index)257 } else {258 self.b.get(index - self.split)259 }260 }261 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {262 if self.split > index {263 self.a.get_lazy(index)264 } else {265 self.b.get_lazy(index - self.split)266 }267 }268269 fn len(&self) -> u32 {270 self.len271 }272273 fn is_cheap(&self) -> bool {274 self.a.is_cheap() && self.b.is_cheap()275 }276}277278impl<T> ArrayLike for Vec<T>279where280 T: IntoUntyped + Trace + fmt::Debug,281 for<'a> &'a T: IntoUntyped,282{283 fn len(&self) -> u32 {284 self.as_slice().len().try_into().unwrap_or(u32::MAX)285 }286287 fn get(&self, index: u32) -> Result<Option<Val>> {288 let Some(elem) = self.as_slice().get(index as usize) else {289 return Ok(None);290 };291 IntoUntyped::into_untyped(elem).map(Some)292 }293294 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {295 let elem = self.as_slice().get(index as usize)?;296 Some(IntoUntyped::into_lazy_untyped(elem))297 }298299 fn is_cheap(&self) -> bool {300 !T::provides_lazy()301 }302}303304305#[derive(Debug, Trace, PartialEq, Eq)]306pub struct RangeArray {307 start: i32,308 end: i32,309}310impl RangeArray {311 pub fn empty() -> Self {312 Self::new_exclusive(0, 0)313 }314 pub fn new_exclusive(start: i32, end: i32) -> Self {315 end.checked_sub(1)316 .map_or_else(Self::empty, |end| Self { start, end })317 }318 pub fn new_inclusive(start: i32, end: i32) -> Self {319 Self { start, end }320 }321 #[expect(322 clippy::cast_sign_loss,323 reason = "the math is valid with wrapping, sign loss works as intended"324 )]325 fn size(&self) -> u32 {326 (self.end as u32)327 .wrapping_sub(self.start as u32)328 .wrapping_add(1)329 }330 fn range(&self) -> impl ExactSizeIterator<Item = i32> + DoubleEndedIterator {331 WithExactSize(self.start..=self.end, self.size() as usize)332 }333}334impl ArrayCheap for RangeArray {335 fn get(&self, index: u32) -> Option<Val> {336 self.range().nth(index as usize).map(|i| Val::Num(i.into()))337 }338 fn len(&self) -> u32 {339 self.size()340 }341}342343#[derive(Debug, Trace)]344pub struct ReverseArray(pub ArrValue);345impl ArrayLike for ReverseArray {346 fn len(&self) -> u32 {347 self.0.len()348 }349350 fn get(&self, index: u32) -> Result<Option<Val>> {351 self.0.get(self.0.len() - index - 1)352 }353354 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {355 self.0.get_lazy(self.0.len() - index - 1)356 }357358 fn is_cheap(&self) -> bool {359 self.0.is_cheap()360 }361}362363#[derive(Trace, Clone, Debug)]364pub enum ArrayMapper {365 Plain(NativeFn!((Val) -> Val)),366 WithIndex(NativeFn!((u32, Val) -> Val)),367}368369#[derive(Trace, Debug, Clone)]370pub struct MappedArray {371 inner: ArrValue,372 cached: Cc<RefCell<Vec<ArrayThunk>>>,373 mapper: ArrayMapper,374}375impl MappedArray {376 pub fn new(inner: ArrValue, mapper: ArrayMapper) -> Self {377 let len = inner.len();378 Self {379 inner,380 cached: Cc::new(RefCell::new(vec![ArrayThunk::Waiting; len as usize])),381 mapper,382 }383 }384 fn evaluate(&self, index: u32, value: Val) -> Result<Val> {385 match &self.mapper {386 ArrayMapper::Plain(f) => f.call(value),387 ArrayMapper::WithIndex(f) => f.call(index, value),388 }389 }390}391impl ArrayLike for MappedArray {392 fn len(&self) -> u32 {393 self.cached.borrow().len() as u32394 }395396 fn get(&self, index: u32) -> Result<Option<Val>> {397 if index >= self.len() {398 return Ok(None);399 }400 match &self.cached.borrow()[index as usize] {401 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),402 ArrayThunk::Errored(e) => return Err(e.clone()),403 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),404 ArrayThunk::Waiting => {}405 }406407 let ArrayThunk::Waiting = replace(408 &mut self.cached.borrow_mut()[index as usize],409 ArrayThunk::Pending,410 ) else {411 unreachable!()412 };413414 let val = self415 .inner416 .get(index)417 .transpose()418 .expect("index checked")419 .and_then(|r| self.evaluate(index, r));420421 let new_value = match val {422 Ok(v) => v,423 Err(e) => {424 self.cached.borrow_mut()[index as usize] = ArrayThunk::Errored(e.clone());425 return Err(e);426 }427 };428 self.cached.borrow_mut()[index as usize] = ArrayThunk::Computed(new_value.clone());429 Ok(Some(new_value))430 }431 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {432 #[derive(Trace)]433 struct MappedArrayThunk {434 arr: MappedArray,435 index: u32,436 }437 impl ThunkValue for MappedArrayThunk {438 type Output = Val;439440 fn get(&self) -> Result<Self::Output> {441 self.arr.get(self.index).transpose().expect("index checked")442 }443 }444445 if index >= self.len() {446 return None;447 }448 match &self.cached.borrow()[index as usize] {449 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),450 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),451 ArrayThunk::Waiting | ArrayThunk::Pending => {}452 }453454 Some(Thunk::new(MappedArrayThunk {455 arr: self.clone(),456 index,457 }))458 }459}460#[derive(Trace, Debug, Clone)]461pub struct MakeArray {462 cached: Cc<RefCell<Vec<ArrayThunk>>>,463 mapper: NativeFn!((u32,)->Val),464}465impl MakeArray {466 pub fn new(len: u32, mapper: NativeFn!((u32)->Val)) -> Self {467 Self {468 cached: Cc::new(RefCell::new(vec![ArrayThunk::Waiting; len as usize])),469 mapper,470 }471 }472}473impl ArrayLike for MakeArray {474 fn len(&self) -> u32 {475 self.cached.borrow().len() as u32476 }477478 fn get(&self, index: u32) -> Result<Option<Val>> {479 if index >= self.len() {480 return Ok(None);481 }482 match &self.cached.borrow()[index as usize] {483 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),484 ArrayThunk::Errored(e) => return Err(e.clone()),485 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),486 ArrayThunk::Waiting => {}487 }488489 let ArrayThunk::Waiting = replace(490 &mut self.cached.borrow_mut()[index as usize],491 ArrayThunk::Pending,492 ) else {493 unreachable!()494 };495496 let val = self.mapper.call(index as u32);497498 let new_value = match val {499 Ok(v) => v,500 Err(e) => {501 self.cached.borrow_mut()[index as usize] = ArrayThunk::Errored(e.clone());502 return Err(e);503 }504 };505 self.cached.borrow_mut()[index as usize] = ArrayThunk::Computed(new_value.clone());506 Ok(Some(new_value))507 }508 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {509 #[derive(Trace)]510 struct MakeArrayThunk {511 arr: MakeArray,512 index: u32,513 }514 impl ThunkValue for MakeArrayThunk {515 type Output = Val;516517 fn get(&self) -> Result<Self::Output> {518 self.arr.get(self.index).transpose().expect("index checked")519 }520 }521522 if index >= self.len() {523 return None;524 }525 match &self.cached.borrow()[index as usize] {526 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),527 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),528 ArrayThunk::Waiting | ArrayThunk::Pending => {}529 }530531 Some(Thunk::new(MakeArrayThunk {532 arr: self.clone(),533 index,534 }))535 }536}537538#[derive(Trace, Debug)]539pub struct RepeatedArray {540 data: ArrValue,541 repeats: u32,542 total_len: u32,543}544impl RepeatedArray {545 pub fn new(data: ArrValue, repeats: u32) -> Option<Self> {546 let total_len = data.len().checked_mul(repeats)?;547 Some(Self {548 data,549 repeats,550 total_len,551 })552 }553 fn map_idx(&self, index: u32) -> Option<u32> {554 if index > self.total_len {555 return None;556 }557 Some(index % self.data.len())558 }559}560561impl ArrayLike for RepeatedArray {562 fn len(&self) -> u32 {563 self.total_len564 }565566 fn get(&self, index: u32) -> Result<Option<Val>> {567 let Some(idx) = self.map_idx(index) else {568 return Ok(None);569 };570 self.data.get(idx)571 }572573 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {574 let idx = self.map_idx(index)?;575 self.data.get_lazy(idx)576 }577578 fn is_cheap(&self) -> bool {579 self.data.is_cheap()580 }581}582583#[derive(Trace, Debug)]584pub struct PickObjectValues {585 obj: ObjValue,586 keys: Vec<IStr>,587}588589impl PickObjectValues {590 pub fn new(obj: ObjValue, keys: Vec<IStr>) -> Self {591 Self { obj, keys }592 }593}594595impl ArrayLike for PickObjectValues {596 fn len(&self) -> u32 {597 self.keys.len() as u32598 }599600 fn get(&self, index: u32) -> Result<Option<Val>> {601 let Some(key) = self.keys.as_slice().get(index as usize) else {602 return Ok(None);603 };604 Ok(Some(self.obj.get_or_bail(key.clone())?))605 }606607 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {608 let key = self.keys.as_slice().get(index as usize)?;609 Some(self.obj.get_lazy_or_bail(key.clone()))610 }611612 fn is_cheap(&self) -> bool {613 false614 }615}616617#[derive(Trace, Debug)]618pub struct PickObjectKeyValues {619 obj: ObjValue,620 keys: Vec<IStr>,621}622623impl PickObjectKeyValues {624 pub fn new(obj: ObjValue, keys: Vec<IStr>) -> Self {625 Self { obj, keys }626 }627}628629#[derive(Typed, IntoUntyped)]630pub struct KeyValue {631 key: IStr,632 value: Thunk<Val>,633}634635impl ArrayLike for PickObjectKeyValues {636 fn len(&self) -> u32 {637 self.keys.len() as u32638 }639640 fn get(&self, index: u32) -> Result<Option<Val>> {641 let Some(key) = self.keys.as_slice().get(index as usize) else {642 return Ok(None);643 };644 Ok(Some(645 KeyValue::into_untyped(KeyValue {646 key: key.clone(),647 value: Thunk::evaluated(self.obj.get_or_bail(key.clone())?),648 })649 .expect("convertible"),650 ))651 }652653 fn get_lazy(&self, index: u32) -> Option<Thunk<Val>> {654 let key = self.keys.as_slice().get(index as usize)?;655 656 657 Some(Thunk::evaluated(658 KeyValue::into_untyped(KeyValue {659 key: key.clone(),660 value: self.obj.get_lazy_or_bail(key.clone()),661 })662 .expect("convertible"),663 ))664 }665666 fn is_cheap(&self) -> bool {667 false668 }669}