1use std::{cell::RefCell, iter, mem::replace, rc::Rc};23use jrsonnet_gcmodule::{Cc, Trace};4use jrsonnet_interner::{IBytes, IStr};5use jrsonnet_parser::LocExpr;67use super::ArrValue;8use crate::{9 error::ErrorKind::InfiniteRecursionDetected,10 evaluate,11 function::FuncVal,12 val::{StrValue, ThunkValue},13 Context, Error, Result, Thunk, Val,14};1516pub trait ArrayLike: Sized + Into<ArrValue> {17 fn len(&self) -> usize;18 fn is_empty(&self) -> bool {19 self.len() == 020 }21 fn get(&self, index: usize) -> Result<Option<Val>>;22 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>>;23 fn get_cheap(&self, index: usize) -> Option<Val>;2425 fn reverse(self) -> ArrValue {26 ArrValue::Reverse(Cc::new(ReverseArray(self.into())))27 }28}2930#[derive(Debug, Clone, Trace)]31pub struct SliceArray {32 pub(crate) inner: ArrValue,33 pub(crate) from: u32,34 pub(crate) to: u32,35 pub(crate) step: u32,36}3738impl SliceArray {39 fn iter(&self) -> impl Iterator<Item = Result<Val>> + '_ {40 self.inner41 .iter()42 .skip(self.from as usize)43 .take((self.to - self.from) as usize)44 .step_by(self.step as usize)45 }4647 fn iter_lazy(&self) -> impl Iterator<Item = Thunk<Val>> + '_ {48 self.inner49 .iter_lazy()50 .skip(self.from as usize)51 .take((self.to - self.from) as usize)52 .step_by(self.step as usize)53 }5455 fn iter_cheap(&self) -> Option<impl crate::arr::ArrayLikeIter<Val> + '_> {56 Some(57 self.inner58 .iter_cheap()?59 .skip(self.from as usize)60 .take((self.to - self.from) as usize)61 .step_by(self.step as usize),62 )63 }64}65impl ArrayLike for SliceArray {66 fn len(&self) -> usize {67 iter::repeat(())68 .take((self.to - self.from) as usize)69 .step_by(self.step as usize)70 .count()71 }7273 fn get(&self, index: usize) -> Result<Option<Val>> {74 self.iter().nth(index).transpose()75 }7677 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {78 self.iter_lazy().nth(index)79 }8081 fn get_cheap(&self, index: usize) -> Option<Val> {82 self.iter_cheap()?.nth(index)83 }84}85impl From<SliceArray> for ArrValue {86 fn from(value: SliceArray) -> Self {87 Self::Slice(Cc::new(value))88 }89}9091#[derive(Trace, Debug, Clone)]92pub struct CharArray(pub Rc<Vec<char>>);93impl ArrayLike for CharArray {94 fn len(&self) -> usize {95 self.0.len()96 }9798 fn get(&self, index: usize) -> Result<Option<Val>> {99 Ok(self.get_cheap(index))100 }101102 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {103 self.get_cheap(index).map(Thunk::evaluated)104 }105106 fn get_cheap(&self, index: usize) -> Option<Val> {107 self.0108 .get(index)109 .map(|v| Val::Str(StrValue::Flat(IStr::from(*v))))110 }111}112impl From<CharArray> for ArrValue {113 fn from(value: CharArray) -> Self {114 ArrValue::Chars(value)115 }116}117118#[derive(Trace, Debug, Clone)]119pub struct BytesArray(pub IBytes);120impl ArrayLike for BytesArray {121 fn len(&self) -> usize {122 self.0.len()123 }124125 fn get(&self, index: usize) -> Result<Option<Val>> {126 Ok(self.get_cheap(index))127 }128129 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {130 self.get_cheap(index).map(Thunk::evaluated)131 }132133 fn get_cheap(&self, index: usize) -> Option<Val> {134 self.0.get(index).map(|v| Val::Num(f64::from(*v)))135 }136}137impl From<BytesArray> for ArrValue {138 fn from(value: BytesArray) -> Self {139 ArrValue::Bytes(value)140 }141}142143#[derive(Debug, Trace, Clone)]144enum ArrayThunk<T: 'static + Trace> {145 Computed(Val),146 Errored(Error),147 Waiting(T),148 Pending,149}150151#[derive(Debug, Trace)]152pub struct ExprArrayInner {153 ctx: Context,154 cached: RefCell<Vec<ArrayThunk<LocExpr>>>,155}156#[derive(Debug, Trace, Clone)]157pub struct ExprArray(pub Cc<ExprArrayInner>);158impl ExprArray {159 pub fn new(ctx: Context, items: impl IntoIterator<Item = LocExpr>) -> Self {160 Self(Cc::new(ExprArrayInner {161 ctx,162 cached: RefCell::new(items.into_iter().map(ArrayThunk::Waiting).collect()),163 }))164 }165}166impl ArrayLike for ExprArray {167 fn len(&self) -> usize {168 self.0.cached.borrow().len()169 }170 fn get(&self, index: usize) -> Result<Option<Val>> {171 if index >= self.len() {172 return Ok(None);173 }174 match &self.0.cached.borrow()[index] {175 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),176 ArrayThunk::Errored(e) => return Err(e.clone()),177 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),178 ArrayThunk::Waiting(..) => {}179 };180181 let ArrayThunk::Waiting(expr) =182 replace(&mut self.0.cached.borrow_mut()[index], ArrayThunk::Pending)183 else {184 unreachable!()185 };186187 let new_value = match evaluate(self.0.ctx.clone(), &expr) {188 Ok(v) => v,189 Err(e) => {190 self.0.cached.borrow_mut()[index] = ArrayThunk::Errored(e.clone());191 return Err(e);192 }193 };194 self.0.cached.borrow_mut()[index] = ArrayThunk::Computed(new_value.clone());195 Ok(Some(new_value))196 }197 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {198 #[derive(Trace)]199 struct ArrayElement {200 arr_thunk: ExprArray,201 index: usize,202 }203204 impl ThunkValue for ArrayElement {205 type Output = Val;206207 fn get(self: Box<Self>) -> Result<Self::Output> {208 self.arr_thunk209 .get(self.index)210 .transpose()211 .expect("index checked")212 }213 }214215 if index >= self.len() {216 return None;217 }218 match &self.0.cached.borrow()[index] {219 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),220 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),221 ArrayThunk::Waiting(_) | ArrayThunk::Pending => {}222 };223224 Some(Thunk::new(ArrayElement {225 arr_thunk: self.clone(),226 index,227 }))228 }229 fn get_cheap(&self, _index: usize) -> Option<Val> {230 None231 }232}233impl From<ExprArray> for ArrValue {234 fn from(value: ExprArray) -> Self {235 Self::Expr(value)236 }237}238239#[derive(Trace, Debug, Clone)]240pub struct ExtendedArray {241 pub a: ArrValue,242 pub b: ArrValue,243 split: usize,244 len: usize,245}246impl ExtendedArray {247 pub fn new(a: ArrValue, b: ArrValue) -> Self {248 let a_len = a.len();249 let b_len = b.len();250 Self {251 a,252 b,253 split: a_len,254 len: a_len.checked_add(b_len).expect("too large array value"),255 }256 }257}258259struct WithExactSize<I>(I, usize);260impl<I, T> Iterator for WithExactSize<I>261where262 I: Iterator<Item = T>,263{264 type Item = T;265266 fn next(&mut self) -> Option<Self::Item> {267 self.0.next()268 }269 fn nth(&mut self, n: usize) -> Option<Self::Item> {270 self.0.nth(n)271 }272 fn size_hint(&self) -> (usize, Option<usize>) {273 (self.1, Some(self.1))274 }275}276impl<I> DoubleEndedIterator for WithExactSize<I>277where278 I: DoubleEndedIterator,279{280 fn next_back(&mut self) -> Option<Self::Item> {281 self.0.next_back()282 }283 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {284 self.0.nth_back(n)285 }286}287impl<I> ExactSizeIterator for WithExactSize<I>288where289 I: Iterator,290{291 fn len(&self) -> usize {292 self.1293 }294}295impl ArrayLike for ExtendedArray {296 fn get(&self, index: usize) -> Result<Option<Val>> {297 if self.split > index {298 self.a.get(index)299 } else {300 self.b.get(index - self.split)301 }302 }303 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {304 if self.split > index {305 self.a.get_lazy(index)306 } else {307 self.b.get_lazy(index - self.split)308 }309 }310311 fn len(&self) -> usize {312 self.len313 }314315 fn get_cheap(&self, index: usize) -> Option<Val> {316 if self.split > index {317 self.a.get_cheap(index)318 } else {319 self.b.get_cheap(index - self.split)320 }321 }322}323impl From<ExtendedArray> for ArrValue {324 fn from(value: ExtendedArray) -> Self {325 Self::Extended(Cc::new(value))326 }327}328329#[derive(Trace, Debug, Clone)]330pub struct LazyArray(pub Cc<Vec<Thunk<Val>>>);331impl ArrayLike for LazyArray {332 fn len(&self) -> usize {333 self.0.len()334 }335 fn get(&self, index: usize) -> Result<Option<Val>> {336 let Some(v) = self.0.get(index) else {337 return Ok(None);338 };339 v.evaluate().map(Some)340 }341 fn get_cheap(&self, _index: usize) -> Option<Val> {342 None343 }344 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {345 self.0.get(index).cloned()346 }347}348impl From<LazyArray> for ArrValue {349 fn from(value: LazyArray) -> Self {350 Self::Lazy(value)351 }352}353354#[derive(Trace, Debug, Clone)]355pub struct EagerArray(pub Cc<Vec<Val>>);356impl ArrayLike for EagerArray {357 fn len(&self) -> usize {358 self.0.len()359 }360361 fn get(&self, index: usize) -> Result<Option<Val>> {362 Ok(self.0.get(index).cloned())363 }364365 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {366 self.0.get(index).cloned().map(Thunk::evaluated)367 }368369 fn get_cheap(&self, index: usize) -> Option<Val> {370 self.0.get(index).cloned()371 }372}373impl From<EagerArray> for ArrValue {374 fn from(value: EagerArray) -> Self {375 Self::Eager(value)376 }377}378379380#[derive(Debug, Trace, Clone, PartialEq, Eq)]381pub struct RangeArray {382 start: i32,383 end: i32,384}385impl RangeArray {386 pub fn empty() -> Self {387 Self::new_exclusive(0, 0)388 }389 pub fn new_exclusive(start: i32, end: i32) -> Self {390 end.checked_sub(1)391 .map_or_else(Self::empty, |end| Self { start, end })392 }393 pub fn new_inclusive(start: i32, end: i32) -> Self {394 Self { start, end }395 }396 fn range(&self) -> impl Iterator<Item = i32> + ExactSizeIterator + DoubleEndedIterator {397 WithExactSize(398 self.start..=self.end,399 (self.end as usize)400 .wrapping_sub(self.start as usize)401 .wrapping_add(1),402 )403 }404}405406impl ArrayLike for RangeArray {407 fn len(&self) -> usize {408 self.range().len()409 }410 fn is_empty(&self) -> bool {411 self.range().len() == 0412 }413414 fn get(&self, index: usize) -> Result<Option<Val>> {415 Ok(self.get_cheap(index))416 }417418 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {419 self.get_cheap(index).map(Thunk::evaluated)420 }421422 fn get_cheap(&self, index: usize) -> Option<Val> {423 self.range().nth(index).map(|i| Val::Num(f64::from(i)))424 }425}426impl From<RangeArray> for ArrValue {427 fn from(value: RangeArray) -> Self {428 Self::Range(value)429 }430}431432#[derive(Debug, Trace, Clone)]433pub struct ReverseArray(pub ArrValue);434impl ArrayLike for ReverseArray {435 fn len(&self) -> usize {436 self.0.len()437 }438439 fn get(&self, index: usize) -> Result<Option<Val>> {440 self.0.get(self.0.len() - index - 1)441 }442443 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {444 self.0.get_lazy(self.0.len() - index - 1)445 }446447 fn get_cheap(&self, index: usize) -> Option<Val> {448 self.0.get_cheap(self.0.len() - index - 1)449 }450 fn reverse(self) -> ArrValue {451 self.0452 }453}454impl From<ReverseArray> for ArrValue {455 fn from(value: ReverseArray) -> Self {456 Self::Reverse(Cc::new(value))457 }458}459460#[derive(Trace, Debug)]461pub struct MappedArrayInner {462 inner: ArrValue,463 cached: RefCell<Vec<ArrayThunk<()>>>,464 mapper: FuncVal,465}466#[derive(Trace, Debug, Clone)]467pub struct MappedArray(Cc<MappedArrayInner>);468impl MappedArray {469 pub fn new(inner: ArrValue, mapper: FuncVal) -> Self {470 let len = inner.len();471 Self(Cc::new(MappedArrayInner {472 inner,473 cached: RefCell::new(vec![ArrayThunk::Waiting(()); len]),474 mapper,475 }))476 }477}478impl ArrayLike for MappedArray {479 fn len(&self) -> usize {480 self.0.cached.borrow().len()481 }482483 fn get(&self, index: usize) -> Result<Option<Val>> {484 if index >= self.len() {485 return Ok(None);486 }487 match &self.0.cached.borrow()[index] {488 ArrayThunk::Computed(c) => return Ok(Some(c.clone())),489 ArrayThunk::Errored(e) => return Err(e.clone()),490 ArrayThunk::Pending => return Err(InfiniteRecursionDetected.into()),491 ArrayThunk::Waiting(..) => {}492 };493494 let ArrayThunk::Waiting(_) =495 replace(&mut self.0.cached.borrow_mut()[index], ArrayThunk::Pending)496 else {497 unreachable!()498 };499500 let val = self501 .0502 .inner503 .get(index)504 .transpose()505 .expect("index checked")506 .and_then(|r| self.0.mapper.evaluate_simple(&(r,), false));507508 let new_value = match val {509 Ok(v) => v,510 Err(e) => {511 self.0.cached.borrow_mut()[index] = ArrayThunk::Errored(e.clone());512 return Err(e);513 }514 };515 self.0.cached.borrow_mut()[index] = ArrayThunk::Computed(new_value.clone());516 Ok(Some(new_value))517 }518 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {519 #[derive(Trace)]520 struct ArrayElement {521 arr_thunk: MappedArray,522 index: usize,523 }524525 impl ThunkValue for ArrayElement {526 type Output = Val;527528 fn get(self: Box<Self>) -> Result<Self::Output> {529 self.arr_thunk530 .get(self.index)531 .transpose()532 .expect("index checked")533 }534 }535536 if index >= self.len() {537 return None;538 }539 match &self.0.cached.borrow()[index] {540 ArrayThunk::Computed(c) => return Some(Thunk::evaluated(c.clone())),541 ArrayThunk::Errored(e) => return Some(Thunk::errored(e.clone())),542 ArrayThunk::Waiting(_) | ArrayThunk::Pending => {}543 };544545 Some(Thunk::new(ArrayElement {546 arr_thunk: self.clone(),547 index,548 }))549 }550551 fn get_cheap(&self, _index: usize) -> Option<Val> {552 None553 }554}555impl From<MappedArray> for ArrValue {556 fn from(value: MappedArray) -> Self {557 Self::Mapped(value)558 }559}560561#[derive(Trace, Debug)]562pub struct RepeatedArrayInner {563 data: ArrValue,564 repeats: usize,565 total_len: usize,566}567#[derive(Trace, Debug, Clone)]568pub struct RepeatedArray(Cc<RepeatedArrayInner>);569impl RepeatedArray {570 pub fn new(data: ArrValue, repeats: usize) -> Option<Self> {571 let total_len = data.len().checked_mul(repeats)?;572 Some(Self(Cc::new(RepeatedArrayInner {573 data,574 repeats,575 total_len,576 })))577 }578 pub fn is_cheap(&self) -> bool {579 self.0.data.is_cheap()580 }581}582583impl ArrayLike for RepeatedArray {584 fn len(&self) -> usize {585 self.0.total_len586 }587588 fn get(&self, index: usize) -> Result<Option<Val>> {589 if index > self.0.total_len {590 return Ok(None);591 }592 self.0.data.get(index % self.0.data.len())593 }594595 fn get_lazy(&self, index: usize) -> Option<Thunk<Val>> {596 if index > self.0.total_len {597 return None;598 }599 self.0.data.get_lazy(index % self.0.data.len())600 }601602 fn get_cheap(&self, index: usize) -> Option<Val> {603 if index > self.0.total_len {604 return None;605 }606 self.0.data.get_cheap(index % self.0.data.len())607 }608}609impl From<RepeatedArray> for ArrValue {610 fn from(value: RepeatedArray) -> Self {611 Self::Repeated(value)612 }613}614615macro_rules! pass {616 ($t:ident.$m:ident($($ident:ident),*)) => {617 match $t {618 Self::Bytes(e) => e.$m($($ident)*),619 Self::Chars(e) => e.$m($($ident)*),620 Self::Expr(e) => e.$m($($ident)*),621 Self::Lazy(e) => e.$m($($ident)*),622 Self::Eager(e) => e.$m($($ident)*),623 Self::Range(e) => e.$m($($ident)*),624 Self::Slice(e) => e.$m($($ident)*),625 Self::Extended(e) => e.$m($($ident)*),626 Self::Reverse(e) => e.$m($($ident)*),627 Self::Mapped(e) => e.$m($($ident)*),628 Self::Repeated(e) => e.$m($($ident)*),629 }630 };631}632pub(super) use pass;