1use std::rc::Rc;2use std::{any::Any, cell::RefCell, fmt::Debug, mem::replace};34use jrsonnet_gcmodule::{Cc, Trace};5use jrsonnet_interner::{IBytes, IStr};6use jrsonnet_parser::{Expr, Spanned};78use super::ArrValue;9use crate::function::NativeFn;10use crate::{11 error::ErrorKind::InfiniteRecursionDetected, evaluate, typed::Typed, val::ThunkValue, Context,12 Error, ObjValue, Result, Thunk, Val,13};1415pub trait ArrayLike: Any + Trace + Debug {16 fn len(&self) -> usize;17 fn is_empty(&self) -> bool {18 self.len() == 019 }20 fn get(&self, index: usize) -> Result<Option<Val>>;21 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>>;22 fn get_cheap(&self, index: usize) -> Option<Val>;2324 fn is_cheap(&self) -> bool;25}2627#[derive(Debug, Trace)]28pub struct SliceArray {29 pub(crate) inner: ArrValue,30 pub(crate) from: u32,31 pub(crate) to: u32,32 pub(crate) step: u32,33}3435impl SliceArray {36 fn map_idx(&self, index: usize) -> usize {37 self.from as usize + self.step as usize * index38 }39}40impl ArrayLike for SliceArray {41 fn len(&self) -> usize {42 (self.to - self.from).div_ceil(self.step) as usize43 }4445 fn get(&self, index: usize) -> Result<Option<Val>> {46 self.inner.get(self.map_idx(index))47 }4849 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {50 self.inner.get_lazy(self.map_idx(index))51 }5253 fn get_cheap(&self, index: usize) -> Option<Val> {54 self.inner.get_cheap(self.map_idx(index))55 }56 fn is_cheap(&self) -> bool {57 self.inner.is_cheap()58 }59}6061#[derive(Trace, Debug)]62pub struct CharArray(pub Vec<char>);63impl ArrayLike for CharArray {64 fn len(&self) -> usize {65 self.0.len()66 }6768 fn get(&self, index: usize) -> Result<Option<Val>> {69 Ok(self.get_cheap(index))70 }7172 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {73 self.get_cheap(index).map(Thunk::evaluated)74 }7576 fn get_cheap(&self, index: usize) -> Option<Val> {77 self.0.get(index).map(|v| Val::string(*v))78 }79 fn is_cheap(&self) -> bool {80 true81 }82}8384#[derive(Trace, Debug)]85pub struct BytesArray(pub IBytes);86impl ArrayLike for BytesArray {87 fn len(&self) -> usize {88 self.0.len()89 }9091 fn get(&self, index: usize) -> Result<Option<Val>> {92 Ok(self.get_cheap(index))93 }9495 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {96 self.get_cheap(index).map(Thunk::evaluated)97 }9899 fn get_cheap(&self, index: usize) -> Option<Val> {100 self.0.get(index).map(|v| Val::Num((*v).into()))101 }102 fn is_cheap(&self) -> bool {103 true104 }105}106107#[derive(Debug, Trace, Clone)]108enum ArrayThunk {109 Computed(Val),110 Errored(Error),111 Waiting,112 Pending,113}114115#[derive(Debug, Trace, Clone)]116pub struct ExprArray {117 ctx: Context,118 src: Rc<Vec<Spanned<Expr>>>,119 cached: Cc<RefCell<Vec<ArrayThunk>>>,120}121impl ExprArray {122 pub fn new(ctx: Context, src: Rc<Vec<Spanned<Expr>>>) -> Self {123 Self {124 ctx,125 cached: Cc::new(RefCell::new(vec![ArrayThunk::Waiting; src.len()])),126 src,127 }128 }129}130impl ArrayLike for ExprArray {131 fn len(&self) -> usize {132 self.cached.borrow().len()133 }134 fn get(&self, index: usize) -> Result<Option<Val>> {135 if index >= self.len() {136 return Ok(None);137 }138 match &self.cached.borrow()[index] {139 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),140 ArrayThunk::Errored(e) => return Err(e.clone()),141 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),142 ArrayThunk::Waiting => {}143 }144145 let ArrayThunk::Waiting =146 replace(&mut self.cached.borrow_mut()[index], ArrayThunk::Pending)147 else {148 unreachable!()149 };150151 let new_value = match evaluate(self.ctx.clone(), &self.src[index]) {152 Ok(v) => v,153 Err(e) => {154 self.cached.borrow_mut()[index] = ArrayThunk::Errored(e.clone());155 return Err(e);156 }157 };158 self.cached.borrow_mut()[index] = ArrayThunk::Computed(new_value.clone());159 Ok(Some(new_value))160 }161 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {162 #[derive(Trace)]163 struct ExprArrThunk {164 expr: ExprArray,165 index: usize,166 }167 impl ThunkValue for ExprArrThunk {168 type Output = Val;169170 fn get(&self) -> Result<Self::Output> {171 self.expr172 .get(self.index)173 .transpose()174 .expect("index checked")175 }176 }177178 if index >= self.len() {179 return None;180 }181 match &self.cached.borrow()[index] {182 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),183 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),184 ArrayThunk::Waiting | ArrayThunk::Pending => {}185 }186187 Some(Thunk::new(ExprArrThunk {188 expr: self.clone(),189 index,190 }))191 }192 fn get_cheap(&self, _index: usize) -> Option<Val> {193 None194 }195 fn is_cheap(&self) -> bool {196 false197 }198}199200#[derive(Trace, Debug)]201pub struct ExtendedArray {202 pub a: ArrValue,203 pub b: ArrValue,204 split: usize,205 len: usize,206}207impl ExtendedArray {208 pub fn new(a: ArrValue, b: ArrValue) -> Self {209 let a_len = a.len();210 let b_len = b.len();211 Self {212 a,213 b,214 split: a_len,215 len: a_len.checked_add(b_len).expect("too large array value"),216 }217 }218}219220struct WithExactSize<I>(I, usize);221impl<I, T> Iterator for WithExactSize<I>222where223 I: Iterator<Item = T>,224{225 type Item = T;226227 fn next(&mut self) -> Option<Self::Item> {228 self.0.next()229 }230 fn nth(&mut self, n: usize) -> Option<Self::Item> {231 self.0.nth(n)232 }233 fn size_hint(&self) -> (usize, Option<usize>) {234 (self.1, Some(self.1))235 }236}237impl<I> DoubleEndedIterator for WithExactSize<I>238where239 I: DoubleEndedIterator,240{241 fn next_back(&mut self) -> Option<Self::Item> {242 self.0.next_back()243 }244 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {245 self.0.nth_back(n)246 }247}248impl<I> ExactSizeIterator for WithExactSize<I>249where250 I: Iterator,251{252 fn len(&self) -> usize {253 self.1254 }255}256impl ArrayLike for ExtendedArray {257 fn get(&self, index: usize) -> Result<Option<Val>> {258 if self.split > index {259 self.a.get(index)260 } else {261 self.b.get(index - self.split)262 }263 }264 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {265 if self.split > index {266 self.a.get_lazy(index)267 } else {268 self.b.get_lazy(index - self.split)269 }270 }271272 fn len(&self) -> usize {273 self.len274 }275276 fn get_cheap(&self, index: usize) -> Option<Val> {277 if self.split > index {278 self.a.get_cheap(index)279 } else {280 self.b.get_cheap(index - self.split)281 }282 }283 fn is_cheap(&self) -> bool {284 self.a.is_cheap() && self.b.is_cheap()285 }286}287288#[derive(Trace, Debug)]289pub struct LazyArray(pub Vec<Thunk<Val>>);290impl ArrayLike for LazyArray {291 fn len(&self) -> usize {292 self.0.len()293 }294 fn get(&self, index: usize) -> Result<Option<Val>> {295 let Some(v) = self.0.get(index) else {296 return Ok(None);297 };298 v.evaluate().map(Some)299 }300 fn get_cheap(&self, _index: usize) -> Option<Val> {301 None302 }303 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {304 self.0.get(index).cloned()305 }306 fn is_cheap(&self) -> bool {307 false308 }309}310311#[derive(Trace, Debug)]312pub struct EagerArray(pub Vec<Val>);313impl ArrayLike for EagerArray {314 fn len(&self) -> usize {315 self.0.len()316 }317318 fn get(&self, index: usize) -> Result<Option<Val>> {319 Ok(self.0.get(index).cloned())320 }321322 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {323 self.0.get(index).cloned().map(Thunk::evaluated)324 }325326 fn get_cheap(&self, index: usize) -> Option<Val> {327 self.0.get(index).cloned()328 }329 fn is_cheap(&self) -> bool {330 true331 }332}333334335#[derive(Debug, Trace, PartialEq, Eq)]336pub struct RangeArray {337 start: i32,338 end: i32,339}340impl RangeArray {341 pub fn empty() -> Self {342 Self::new_exclusive(0, 0)343 }344 pub fn new_exclusive(start: i32, end: i32) -> Self {345 end.checked_sub(1)346 .map_or_else(Self::empty, |end| Self { start, end })347 }348 pub fn new_inclusive(start: i32, end: i32) -> Self {349 Self { start, end }350 }351 fn range(&self) -> impl ExactSizeIterator<Item = i32> + DoubleEndedIterator {352 WithExactSize(353 self.start..=self.end,354 (self.end as usize)355 .wrapping_sub(self.start as usize)356 .wrapping_add(1),357 )358 }359}360361impl ArrayLike for RangeArray {362 fn len(&self) -> usize {363 self.range().len()364 }365 fn is_empty(&self) -> bool {366 self.range().len() == 0367 }368369 fn get(&self, index: usize) -> Result<Option<Val>> {370 Ok(self.get_cheap(index))371 }372373 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {374 self.get_cheap(index).map(Thunk::evaluated)375 }376377 fn get_cheap(&self, index: usize) -> Option<Val> {378 self.range().nth(index).map(|i| Val::Num(i.into()))379 }380 fn is_cheap(&self) -> bool {381 true382 }383}384385#[derive(Debug, Trace)]386pub struct ReverseArray(pub ArrValue);387impl ArrayLike for ReverseArray {388 fn len(&self) -> usize {389 self.0.len()390 }391392 fn get(&self, index: usize) -> Result<Option<Val>> {393 self.0.get(self.0.len() - index - 1)394 }395396 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {397 self.0.get_lazy(self.0.len() - index - 1)398 }399400 fn get_cheap(&self, index: usize) -> Option<Val> {401 self.0.get_cheap(self.0.len() - index - 1)402 }403 fn is_cheap(&self) -> bool {404 self.0.is_cheap()405 }406}407408#[derive(Trace, Clone, Debug)]409pub enum ArrayMapper {410 Plain(NativeFn!((Val) -> Val)),411 WithIndex(NativeFn!((u32, Val) -> Val)),412}413414#[derive(Trace, Debug, Clone)]415pub struct MappedArray {416 inner: ArrValue,417 cached: Cc<RefCell<Vec<ArrayThunk>>>,418 mapper: ArrayMapper,419}420impl MappedArray {421 pub fn new(inner: ArrValue, mapper: ArrayMapper) -> Self {422 let len = inner.len();423 Self {424 inner,425 cached: Cc::new(RefCell::new(vec![ArrayThunk::Waiting; len])),426 mapper,427 }428 }429 fn evaluate(&self, index: usize, value: Val) -> Result<Val> {430 match &self.mapper {431 ArrayMapper::Plain(f) => f.call(value),432 ArrayMapper::WithIndex(f) => f.call(index as u32, value),433 }434 }435}436impl ArrayLike for MappedArray {437 fn len(&self) -> usize {438 self.cached.borrow().len()439 }440441 fn get(&self, index: usize) -> Result<Option<Val>> {442 if index >= self.len() {443 return Ok(None);444 }445 match &self.cached.borrow()[index] {446 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),447 ArrayThunk::Errored(e) => return Err(e.clone()),448 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),449 ArrayThunk::Waiting => {}450 }451452 let ArrayThunk::Waiting =453 replace(&mut self.cached.borrow_mut()[index], ArrayThunk::Pending)454 else {455 unreachable!()456 };457458 let val = self459 .inner460 .get(index)461 .transpose()462 .expect("index checked")463 .and_then(|r| self.evaluate(index, r));464465 let new_value = match val {466 Ok(v) => v,467 Err(e) => {468 self.cached.borrow_mut()[index] = ArrayThunk::Errored(e.clone());469 return Err(e);470 }471 };472 self.cached.borrow_mut()[index] = ArrayThunk::Computed(new_value.clone());473 Ok(Some(new_value))474 }475 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {476 #[derive(Trace)]477 struct MappedArrayThunk {478 arr: MappedArray,479 index: usize,480 }481 impl ThunkValue for MappedArrayThunk {482 type Output = Val;483484 fn get(&self) -> Result<Self::Output> {485 self.arr.get(self.index).transpose().expect("index checked")486 }487 }488489 if index >= self.len() {490 return None;491 }492 match &self.cached.borrow()[index] {493 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),494 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),495 ArrayThunk::Waiting | ArrayThunk::Pending => {}496 }497498 Some(Thunk::new(MappedArrayThunk {499 arr: self.clone(),500 index,501 }))502 }503504 fn get_cheap(&self, _index: usize) -> Option<Val> {505 None506 }507 fn is_cheap(&self) -> bool {508 false509 }510}511512#[derive(Trace, Debug)]513pub struct RepeatedArray {514 data: ArrValue,515 repeats: usize,516 total_len: usize,517}518impl RepeatedArray {519 pub fn new(data: ArrValue, repeats: usize) -> Option<Self> {520 let total_len = data.len().checked_mul(repeats)?;521 Some(Self {522 data,523 repeats,524 total_len,525 })526 }527}528529impl ArrayLike for RepeatedArray {530 fn len(&self) -> usize {531 self.total_len532 }533534 fn get(&self, index: usize) -> Result<Option<Val>> {535 if index > self.total_len {536 return Ok(None);537 }538 self.data.get(index % self.data.len())539 }540541 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {542 if index > self.total_len {543 return None;544 }545 self.data.get_lazy(index % self.data.len())546 }547548 fn get_cheap(&self, index: usize) -> Option<Val> {549 if index > self.total_len {550 return None;551 }552 self.data.get_cheap(index % self.data.len())553 }554 fn is_cheap(&self) -> bool {555 self.data.is_cheap()556 }557}558559#[derive(Trace, Debug)]560pub struct PickObjectValues {561 obj: ObjValue,562 keys: Vec<IStr>,563}564565impl PickObjectValues {566 pub fn new(obj: ObjValue, keys: Vec<IStr>) -> Self {567 Self { obj, keys }568 }569}570571impl ArrayLike for PickObjectValues {572 fn len(&self) -> usize {573 self.keys.len()574 }575576 fn get(&self, index: usize) -> Result<Option<Val>> {577 let Some(key) = self.keys.get(index) else {578 return Ok(None);579 };580 Ok(Some(self.obj.get_or_bail(key.clone())?))581 }582583 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {584 let key = self.keys.get(index)?;585 Some(self.obj.get_lazy_or_bail(key.clone()))586 }587588 fn get_cheap(&self, _index: usize) -> Option<Val> {589 None590 }591592 fn is_cheap(&self) -> bool {593 false594 }595}596597#[derive(Trace, Debug)]598pub struct PickObjectKeyValues {599 obj: ObjValue,600 keys: Vec<IStr>,601}602603impl PickObjectKeyValues {604 pub fn new(obj: ObjValue, keys: Vec<IStr>) -> Self {605 Self { obj, keys }606 }607}608609#[derive(Typed)]610pub struct KeyValue {611 key: IStr,612 value: Thunk<Val>,613}614615impl ArrayLike for PickObjectKeyValues {616 fn len(&self) -> usize {617 self.keys.len()618 }619620 fn get(&self, index: usize) -> Result<Option<Val>> {621 let Some(key) = self.keys.get(index) else {622 return Ok(None);623 };624 Ok(Some(625 KeyValue::into_untyped(KeyValue {626 key: key.clone(),627 value: Thunk::evaluated(self.obj.get_or_bail(key.clone())?),628 })629 .expect("convertible"),630 ))631 }632633 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {634 let key = self.keys.get(index)?;635 636 637 Some(Thunk::evaluated(638 KeyValue::into_untyped(KeyValue {639 key: key.clone(),640 value: self.obj.get_lazy_or_bail(key.clone()),641 })642 .expect("convertible"),643 ))644 }645646 fn get_cheap(&self, _index: usize) -> Option<Val> {647 None648 }649650 fn is_cheap(&self) -> bool {651 false652 }653}