Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/eval/lib/array.rs

15.3 KiB, 6 runs

created by r1870400018:63216, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1// U3 owns this file. Methods on `array`. `push`, `pop`, `insert` and `remove` are not here: they change
2// a place, which only the evaluator holds, so `methods.rs` carries them out. Comparison, equality, addition and joining
3// are `ops.rs`'s, so `sorted`, `dedup`, `sum` and `join` agree with the operators by construction.
4
5use crate::diag::DiagnosticKind;
6use crate::eval::args::Args;
7use crate::eval::func::Func;
8use crate::eval::lib::foundations::{
9 as_func,
10 finish,
11 func_refusal,
12 int_of,
13 locate_index,
14 mismatch,
15 named_bool,
16 need,
17 receiver,
18 slice_bounds,
19 words,
20};
21use crate::eval::ops;
22use crate::eval::scope::Scope;
23use crate::eval::value::{
24 Dict,
25 Value,
26};
27use crate::eval::Engine;
28use crate::syntax::Span;
29
30use oxedyne_fe2o3_core::prelude::*;
31
32use std::cmp::Ordering;
33use std::sync::Arc;
34
35native_fns! {
36 pub enum ArrayFn {
37 Construct => "array",
38 Len => "len",
39 First => "first",
40 Last => "last",
41 At => "at",
42 Slice => "slice",
43 Contains => "contains",
44 Find => "find",
45 Position => "position",
46 Filter => "filter",
47 Map => "map",
48 Enumerate => "enumerate",
49 Zip => "zip",
50 Fold => "fold",
51 Reduce => "reduce",
52 Sum => "sum",
53 Product => "product",
54 Any => "any",
55 All => "all",
56 Flatten => "flatten",
57 Rev => "rev",
58 Split => "split",
59 Join => "join",
60 Intersperse => "intersperse",
61 Chunks => "chunks",
62 Windows => "windows",
63 Sorted => "sorted",
64 Dedup => "dedup",
65 ToDict => "to-dict",
66 }
67}
68
69pub fn define(_scope: &mut Scope) {}
70
71pub fn method(name: &str) -> Option<ArrayFn> {
72 ArrayFn::ALL.iter().copied().find(|f| f.name() == name && *f != ArrayFn::Construct)
73}
74
75
76
77fn no_default(engine: &mut Engine, span: Span, i: i64, len: usize) -> Error<ErrTag> {
78 engine.error(DiagnosticKind::Type, span, fmt!(
79 "array index out of bounds (index: {}, len: {}) and no default value was specified", i, len))
80}
81
82pub fn func_of(engine: &mut Engine, span: Span, v: Value) -> Outcome<Func> {
83 match as_func(&v) {
84 Some(f) => Ok(f),
85 None => Err(engine.error(DiagnosticKind::Type, span, func_refusal(&v))),
86 }
87}
88
89/// Calls `f` with the given positional arguments.
90pub fn apply(engine: &mut Engine, span: Span, f: &Func, vals: Vec<Value>) -> Outcome<Value> {
91 let mut a = Args::new(span);
92 for v in vals {
93 a.push(span, v);
94 }
95 engine.call_func(f, a)
96}
97
98fn test(engine: &mut Engine, span: Span, f: &Func, v: Value) -> Outcome<bool> {
99 match res!(apply(engine, span, f, vec![v])) {
100 Value::Bool(b) => Ok(b),
101 other => Err(mismatch(engine, span, "boolean", &other)),
102 }
103}
104
105// An operator's error, as a diagnostic at the call.
106fn op_error(engine: &mut Engine, span: Span, e: Error<ErrTag>) -> Error<ErrTag> {
107 let w = words(&e);
108 engine.error(DiagnosticKind::Type, span, w)
109}
110
111pub fn call(f: ArrayFn, engine: &mut Engine, mut args: Args) -> Outcome<Value> {
112 let span = args.span;
113 if f == ArrayFn::Construct {
114 let v = res!(need(engine, &mut args, "value"));
115 res!(finish(engine, args));
116 return match v {
117 Value::Array(a) => Ok(Value::Array(a)),
118 Value::Bytes(b) => Ok(Value::array(b.iter().map(|x| Value::Int(*x as i64)).collect())),
119 Value::Version(p) => Ok(Value::array(p.iter().map(|x| Value::Int(*x as i64)).collect())),
120 other => Err(mismatch(engine, span, "array, bytes, or version", &other)),
121 };
122 }
123 let recv = res!(receiver(&mut args));
124 let arr = match recv {
125 Value::Array(a) => a,
126 other => return Err(mismatch(engine, span, "array", &other)),
127 };
128 let out = match f {
129 ArrayFn::Len => Value::Int(arr.len() as i64),
130 ArrayFn::First | ArrayFn::Last => {
131 let default = res!(args.named::<Value>("default"));
132 let v = if f == ArrayFn::First { arr.first() } else { arr.last() };
133 match (v, default) {
134 (Some(v), _) => v.clone(),
135 (None, Some(d)) => d,
136 (None, None) => return Err(engine.error(DiagnosticKind::Type, span, "array is empty")),
137 }
138 }
139 ArrayFn::At => {
140 let i = res!(need(engine, &mut args, "index"));
141 let i = res!(int_of(engine, span, i));
142 let default = res!(args.named::<Value>("default"));
143 match (locate_index(i, arr.len()), default) {
144 (Some(k), _) => arr[k].clone(),
145 (None, Some(d)) => d,
146 (None, None) => return Err(no_default(engine, span, i, arr.len())),
147 }
148 }
149 ArrayFn::Slice => {
150 let (a, b) = res!(slice_bounds(engine, &mut args, arr.len(), "array", |_| true));
151 Value::array(arr[a..b].to_vec())
152 }
153 ArrayFn::Contains => {
154 let v = res!(need(engine, &mut args, "value"));
155 Value::Bool(arr.iter().any(|x| ops::equal(x, &v)))
156 }
157 ArrayFn::Find | ArrayFn::Position | ArrayFn::Any | ArrayFn::All | ArrayFn::Filter => {
158 let fv = res!(need(engine, &mut args, "searcher"));
159 let func = res!(func_of(engine, span, fv));
160 res!(finish(engine, args));
161 return search(engine, span, f, &arr, &func);
162 }
163 ArrayFn::Map => {
164 let fv = res!(need(engine, &mut args, "mapper"));
165 let func = res!(func_of(engine, span, fv));
166 res!(finish(engine, args));
167 let mut out = Vec::with_capacity(arr.len());
168 for v in arr.iter() {
169 out.push(res!(apply(engine, span, &func, vec![v.clone()])));
170 }
171 return Ok(Value::array(out));
172 }
173 ArrayFn::Enumerate => {
174 let start = match res!(args.named::<Value>("start")) {
175 None => 0,
176 Some(v) => res!(int_of(engine, span, v)),
177 };
178 let mut out = Vec::with_capacity(arr.len());
179 for (i, v) in arr.iter().enumerate() {
180 let k = match start.checked_add(i as i64) {
181 Some(k) => k,
182 None => return Err(engine.error(DiagnosticKind::Type, span, "array index is too large")),
183 };
184 out.push(Value::array(vec![Value::Int(k), v.clone()]));
185 }
186 Value::array(out)
187 }
188 ArrayFn::Zip => {
189 let exact = res!(named_bool(engine, &mut args, "exact", false));
190 let others = res!(args.all::<Value>());
191 let one = others.len() == 1;
192 let mut lists: Vec<Arc<Vec<Value>>> = vec![arr.clone()];
193 for o in others {
194 match o {
195 Value::Array(a) => {
196 if exact && a.len() != arr.len() {
197 let which = if one { "second array" } else { "array" };
198 return Err(engine.error(DiagnosticKind::Type, span, fmt!(
199 "{} has different length ({}) from first array ({})", which, a.len(), arr.len())));
200 }
201 lists.push(a);
202 }
203 other => return Err(mismatch(engine, span, "array", &other)),
204 }
205 }
206 let n = lists.iter().map(|l| l.len()).min().unwrap_or(0);
207 let out = (0..n).map(|i| Value::array(lists.iter().map(|l| l[i].clone()).collect())).collect();
208 Value::array(out)
209 }
210 ArrayFn::Fold => {
211 let init = res!(need(engine, &mut args, "init"));
212 let fv = res!(need(engine, &mut args, "folder"));
213 let func = res!(func_of(engine, span, fv));
214 res!(finish(engine, args));
215 let mut acc = init;
216 for v in arr.iter() {
217 acc = res!(apply(engine, span, &func, vec![acc, v.clone()]));
218 }
219 return Ok(acc);
220 }
221 ArrayFn::Reduce => {
222 let fv = res!(need(engine, &mut args, "reducer"));
223 let func = res!(func_of(engine, span, fv));
224 res!(finish(engine, args));
225 let mut it = arr.iter();
226 let mut acc = match it.next() {
227 Some(v) => v.clone(),
228 None => return Ok(Value::None),
229 };
230 for v in it {
231 acc = res!(apply(engine, span, &func, vec![acc, v.clone()]));
232 }
233 return Ok(acc);
234 }
235 ArrayFn::Sum | ArrayFn::Product => {
236 let default = res!(args.named::<Value>("default"));
237 let mut it = arr.iter();
238 let mut acc = match (it.next(), default) {
239 (Some(v), _) => v.clone(),
240 (None, Some(d)) => d,
241 (None, None) => return Err(engine.error(DiagnosticKind::Type, span, fmt!(
242 "cannot calculate {} of empty array with no default",
243 if f == ArrayFn::Sum { "sum" } else { "product" }))),
244 };
245 for v in it {
246 let r = if f == ArrayFn::Sum { ops::add(acc, v.clone()) } else { ops::mul(acc, v.clone()) };
247 acc = match r {
248 Ok(x) => x,
249 Err(e) => return Err(op_error(engine, span, e)),
250 };
251 }
252 acc
253 }
254 ArrayFn::Flatten => {
255 let mut out = Vec::new();
256 flatten(&arr, &mut out);
257 Value::array(out)
258 }
259 ArrayFn::Rev => {
260 let mut v = (*arr).clone();
261 v.reverse();
262 Value::array(v)
263 }
264 ArrayFn::Split => {
265 let at = res!(need(engine, &mut args, "at"));
266 let mut out = Vec::new();
267 let mut cur = Vec::new();
268 for v in arr.iter() {
269 if ops::equal(v, &at) {
270 out.push(Value::array(std::mem::take(&mut cur)));
271 } else {
272 cur.push(v.clone());
273 }
274 }
275 out.push(Value::array(cur));
276 Value::array(out)
277 }
278 ArrayFn::Join => {
279 let sep = res!(args.eat::<Value>()).unwrap_or(Value::None);
280 let mut last = res!(args.named::<Value>("last"));
281 let default = res!(args.named::<Value>("default"));
282 res!(finish(engine, args));
283 if arr.is_empty() {
284 return Ok(default.unwrap_or(Value::None));
285 }
286 let len = arr.len();
287 let mut acc = Value::None;
288 for (i, v) in arr.iter().enumerate() {
289 if i > 0 {
290 let s = match (i + 1 == len, last.take()) {
291 (true, Some(l)) => l,
292 (_, l) => {
293 last = l;
294 sep.clone()
295 }
296 };
297 acc = match ops::join(acc, s) {
298 Ok(x) => x,
299 Err(e) => return Err(op_error(engine, span, e)),
300 };
301 }
302 acc = match ops::join(acc, v.clone()) {
303 Ok(x) => x,
304 Err(e) => return Err(op_error(engine, span, e)),
305 };
306 }
307 return Ok(acc);
308 }
309 ArrayFn::Intersperse => {
310 let sep = res!(need(engine, &mut args, "separator"));
311 let mut out = Vec::with_capacity(arr.len() * 2);
312 for (i, v) in arr.iter().enumerate() {
313 if i > 0 {
314 out.push(sep.clone());
315 }
316 out.push(v.clone());
317 }
318 Value::array(out)
319 }
320 ArrayFn::Chunks | ArrayFn::Windows => {
321 let n = res!(need(engine, &mut args, "chunk-size"));
322 let n = res!(int_of(engine, span, n));
323 let exact = if f == ArrayFn::Chunks {
324 res!(named_bool(engine, &mut args, "exact", false))
325 } else {
326 false
327 };
328 if n <= 0 {
329 return Err(engine.error(DiagnosticKind::Type, span, "number must be positive"));
330 }
331 let n = n as usize;
332 let out: Vec<Value> = if f == ArrayFn::Chunks {
333 arr.chunks(n).filter(|c| !exact || c.len() == n).map(|c| Value::array(c.to_vec())).collect()
334 } else {
335 arr.windows(n).map(|c| Value::array(c.to_vec())).collect()
336 };
337 Value::array(out)
338 }
339 ArrayFn::Sorted => {
340 let key = match res!(args.named::<Value>("key")) {
341 None | Some(Value::None) => None,
342 Some(v) => Some(res!(func_of(engine, span, v))),
343 };
344 let by = match res!(args.named::<Value>("by")) {
345 None | Some(Value::None) => None,
346 Some(v) => Some(res!(func_of(engine, span, v))),
347 };
348 res!(finish(engine, args));
349 return sorted(engine, span, &arr, key, by);
350 }
351 ArrayFn::Dedup => {
352 let key = match res!(args.named::<Value>("key")) {
353 None | Some(Value::None) => None,
354 Some(v) => Some(res!(func_of(engine, span, v))),
355 };
356 res!(finish(engine, args));
357 let mut keys: Vec<Value> = Vec::new();
358 let mut out = Vec::new();
359 for v in arr.iter() {
360 let k = match &key {
361 Some(kf) => res!(apply(engine, span, kf, vec![v.clone()])),
362 None => v.clone(),
363 };
364 if !keys.iter().any(|x| ops::equal(x, &k)) {
365 keys.push(k);
366 out.push(v.clone());
367 }
368 }
369 return Ok(Value::array(out));
370 }
371 ArrayFn::ToDict => {
372 let mut d = Dict::new();
373 for v in arr.iter() {
374 let pair = match v {
375 Value::Array(p) => p,
376 other => return Err(engine.error(DiagnosticKind::Type, span, fmt!(
377 "expected (str, any) pairs, found {}", other.ty().name()))),
378 };
379 if pair.len() != 2 {
380 return Err(engine.error(DiagnosticKind::Type, span, fmt!("expected pairs of length 2, found length {}", pair.len())));
381 }
382 match &pair[0] {
383 Value::Str(k) => d.insert(k, pair[1].clone()),
384 other => return Err(engine.error(DiagnosticKind::Type, span, fmt!(
385 "expected key of type str, found {}",
386 crate::eval::lib::foundations::type_desc(other.ty())))),
387 }
388 }
389 Value::dict(d)
390 }
391 ArrayFn::Construct => Value::None,
392 };
393 res!(finish(engine, args));
394 Ok(out)
395}
396
397fn search(engine: &mut Engine, span: Span, f: ArrayFn, arr: &[Value], func: &Func) -> Outcome<Value> {
398 match f {
399 ArrayFn::Find => {
400 for v in arr {
401 if res!(test(engine, span, func, v.clone())) {
402 return Ok(v.clone());
403 }
404 }
405 Ok(Value::None)
406 }
407 ArrayFn::Position => {
408 for (i, v) in arr.iter().enumerate() {
409 if res!(test(engine, span, func, v.clone())) {
410 return Ok(Value::Int(i as i64));
411 }
412 }
413 Ok(Value::None)
414 }
415 ArrayFn::Any => {
416 for v in arr {
417 if res!(test(engine, span, func, v.clone())) {
418 return Ok(Value::Bool(true));
419 }
420 }
421 Ok(Value::Bool(false))
422 }
423 ArrayFn::All => {
424 for v in arr {
425 if !res!(test(engine, span, func, v.clone())) {
426 return Ok(Value::Bool(false));
427 }
428 }
429 Ok(Value::Bool(true))
430 }
431 _ => {
432 let mut out = Vec::new();
433 for v in arr {
434 if res!(test(engine, span, func, v.clone())) {
435 out.push(v.clone());
436 }
437 }
438 Ok(Value::array(out))
439 }
440 }
441}
442
443fn flatten(arr: &[Value], out: &mut Vec<Value>) {
444 for v in arr {
445 match v {
446 Value::Array(a) => flatten(a, out),
447 other => out.push(other.clone()),
448 }
449 }
450}
451
452fn sorted(engine: &mut Engine, span: Span, arr: &[Value], key: Option<Func>, by: Option<Func>) -> Outcome<Value> {
453 if key.is_some() && by.is_some() {
454 return Err(engine.error(DiagnosticKind::Type, span, "`key` and `by` are mutually exclusive"));
455 }
456 // Pair each element with its sort key, so a key function runs once per element.
457 let mut items: Vec<(Value, Value)> = Vec::with_capacity(arr.len());
458 for v in arr {
459 let k = match &key {
460 Some(kf) => res!(apply(engine, span, kf, vec![v.clone()])),
461 None => v.clone(),
462 };
463 items.push((k, v.clone()));
464 }
465 let items = match by {
466 Some(byf) => res!(merge_sort(items, &mut |a: &(Value, Value), b: &(Value, Value)| {
467 let ab = res!(by_call(engine, span, &byf, &a.1, &b.1));
468 if ab {
469 return Ok(Ordering::Less);
470 }
471 let ba = res!(by_call(engine, span, &byf, &b.1, &a.1));
472 Ok(if ba { Ordering::Greater } else { Ordering::Equal })
473 })),
474 None => res!(merge_sort(items, &mut |a: &(Value, Value), b: &(Value, Value)| {
475 match ops::compare(&a.0, &b.0) {
476 Ok(o) => Ok(o),
477 Err(e) => Err(engine.error_hint(DiagnosticKind::Type, span, words(&e),
478 "consider choosing a `key` or defining the comparison with `by`")),
479 }
480 })),
481 };
482 Ok(Value::array(items.into_iter().map(|(_, v)| v).collect()))
483}
484
485fn by_call(engine: &mut Engine, span: Span, f: &Func, a: &Value, b: &Value) -> Outcome<bool> {
486 match res!(apply(engine, span, f, vec![a.clone(), b.clone()])) {
487 Value::Bool(x) => Ok(x),
488 other => Err(engine.error(DiagnosticKind::Type, span, fmt!(
489 "expected boolean from `by` function, got {}",
490 crate::eval::lib::foundations::type_desc(other.ty())))),
491 }
492}
493
494/// A stable bottom-up merge sort whose comparison may fail (a closure erring, incomparable values).
495fn merge_sort<T: Clone, F: FnMut(&T, &T) -> Outcome<Ordering>>(v: Vec<T>, cmp: &mut F) -> Outcome<Vec<T>> {
496 let n = v.len();
497 let mut src = v;
498 let mut width = 1;
499 while width < n {
500 let mut dst: Vec<T> = Vec::with_capacity(n);
501 let mut lo = 0;
502 while lo < n {
503 let mid = (lo + width).min(n);
504 let hi = (lo + 2 * width).min(n);
505 let (mut i, mut j) = (lo, mid);
506 while i < mid && j < hi {
507 // Take from the right only when strictly less, which keeps equal elements in order.
508 if res!(cmp(&src[j], &src[i])) == Ordering::Less {
509 dst.push(src[j].clone());
510 j += 1;
511 } else {
512 dst.push(src[i].clone());
513 i += 1;
514 }
515 }
516 dst.extend_from_slice(&src[i..mid]);
517 dst.extend_from_slice(&src[j..hi]);
518 lo = hi;
519 }
520 src = dst;
521 width *= 2;
522 }
523 Ok(src)
524}