Skip to main content

vibe/stdlib_v2/text_and_collections/
collections.rs

1//! Immutable-by-Default Collections, Type-Aware Natural Sorting, Seeded Fisher-Yates Shuffle,
2//! Double-Ended Queue (`deque.*`), Priority Queue (`pqueue.*`), and Structural Sets (`set.*`).
3
4use std::cmp::Ordering;
5use std::collections::BTreeMap;
6
7use crate::error::{DiagCode, Diagnostic};
8use crate::span::Span;
9use crate::value::Value;
10
11use super::{
12    extract_i64, extract_list, extract_opt_i64, extract_str, resolve_element_index,
13    resolve_slice_bound,
14};
15
16/// Maximum elements produced by `list.range` inside a single pure call.
17const MAX_RANGE_LEN: usize = 65_536;
18
19/// Dispatch `list.*`, `deque.*`, `pqueue.*`, and `set.*` calls.
20pub(crate) fn call_collections(
21    path: &str,
22    args: &[Value],
23    span: Span,
24) -> Result<Option<Value>, Diagnostic> {
25    match path {
26        "list.range" => {
27            let start = extract_i64(args, 0, "list.range(start, end, step_opt)", span)?;
28            let end = extract_i64(args, 1, "list.range(start, end, step_opt)", span)?;
29            let default_step = if start <= end { 1 } else { -1 };
30            let step = extract_opt_i64(args, 2).unwrap_or(default_step);
31            if step == 0 {
32                return Err(Diagnostic::new(DiagCode::E100, span, "list.range: step cannot be 0"));
33            }
34            let mut out = Vec::new();
35            let mut cur = start;
36            while (step > 0 && cur < end) || (step < 0 && cur > end) {
37                if out.len() >= MAX_RANGE_LEN {
38                    return Err(Diagnostic::new(
39                        DiagCode::E400,
40                        span,
41                        "list.range: range exceeds maximum bounded length",
42                    ));
43                }
44                out.push(Value::I64(cur));
45                cur = cur.saturating_add(step);
46            }
47            Ok(Some(Value::List(out)))
48        }
49        "list.at" => {
50            let xs = extract_list(args, 0, "list.at(xs, idx)", span)?;
51            let idx = extract_i64(args, 1, "list.at(xs, idx)", span)?;
52            let val = resolve_element_index(idx, xs.len())
53                .map(|i| xs[i].clone())
54                .unwrap_or(Value::Null);
55            Ok(Some(val))
56        }
57        "list.slice" => {
58            let xs = extract_list(args, 0, "list.slice(xs, start, end_opt, step_opt)", span)?;
59            let len = xs.len();
60            let start_raw = extract_opt_i64(args, 1).unwrap_or(0);
61            let step = extract_opt_i64(args, 3).unwrap_or(1);
62            if step == 0 {
63                return Err(Diagnostic::new(DiagCode::E100, span, "list.slice: step cannot be 0"));
64            }
65            let s_idx = resolve_slice_bound(start_raw, len);
66            let e_idx = extract_opt_i64(args, 2)
67                .map(|e| resolve_slice_bound(e, len))
68                .unwrap_or(len);
69
70            let mut out = Vec::new();
71            if step > 0 {
72                let stride = step as usize;
73                let mut i = s_idx;
74                while i < e_idx && i < len {
75                    out.push(xs[i].clone());
76                    i += stride;
77                }
78            } else {
79                let stride = (-step) as usize;
80                if s_idx <= e_idx {
81                    let sub = &xs[s_idx..e_idx.min(len)];
82                    let mut i = sub.len();
83                    while i > 0 {
84                        out.push(sub[i - 1].clone());
85                        if i <= stride {
86                            break;
87                        }
88                        i -= stride;
89                    }
90                } else {
91                    let mut i = s_idx.min(len.saturating_sub(1));
92                    while i > e_idx {
93                        out.push(xs[i].clone());
94                        if i < e_idx + stride {
95                            break;
96                        }
97                        i -= stride;
98                    }
99                }
100            }
101            Ok(Some(Value::List(out)))
102        }
103        "list.sort_natural" => {
104            let mut xs = extract_list(args, 0, "list.sort_natural(xs)", span)?;
105            xs.sort_by(compare_values_natural);
106            Ok(Some(Value::List(xs)))
107        }
108        "list.chunk" => {
109            let xs = extract_list(args, 0, "list.chunk(xs, size)", span)?;
110            let size = extract_i64(args, 1, "list.chunk(xs, size)", span)?;
111            if size <= 0 {
112                return Err(Diagnostic::new(
113                    DiagCode::E100,
114                    span,
115                    "list.chunk: size must be positive",
116                ));
117            }
118            let chunks = xs.chunks(size as usize).map(|c| Value::List(c.to_vec())).collect();
119            Ok(Some(Value::List(chunks)))
120        }
121        "list.windows" => {
122            let xs = extract_list(args, 0, "list.windows(xs, size)", span)?;
123            let size = extract_i64(args, 1, "list.windows(xs, size)", span)?;
124            if size <= 0 {
125                return Err(Diagnostic::new(
126                    DiagCode::E100,
127                    span,
128                    "list.windows: size must be positive",
129                ));
130            }
131            let w = size as usize;
132            let windows = if w > xs.len() {
133                Vec::new()
134            } else {
135                xs.windows(w).map(|win| Value::List(win.to_vec())).collect()
136            };
137            Ok(Some(Value::List(windows)))
138        }
139        "list.zip" => {
140            let a = extract_list(args, 0, "list.zip(a, b)", span)?;
141            let b = extract_list(args, 1, "list.zip(a, b)", span)?;
142            let zipped = a.into_iter().zip(b).map(|(x, y)| Value::List(vec![x, y])).collect();
143            Ok(Some(Value::List(zipped)))
144        }
145        "list.unzip" => {
146            let pairs = extract_list(args, 0, "list.unzip(pairs)", span)?;
147            let mut left = Vec::with_capacity(pairs.len());
148            let mut right = Vec::with_capacity(pairs.len());
149            for item in pairs {
150                match item {
151                    Value::List(mut p) if p.len() >= 2 => {
152                        let r = p.remove(1);
153                        let l = p.remove(0);
154                        left.push(l);
155                        right.push(r);
156                    }
157                    Value::Record(rec) => {
158                        left.push(
159                            rec.get("first")
160                                .or_else(|| rec.get("index"))
161                                .cloned()
162                                .unwrap_or(Value::Null),
163                        );
164                        right.push(
165                            rec.get("second")
166                                .or_else(|| rec.get("value"))
167                                .cloned()
168                                .unwrap_or(Value::Null),
169                        );
170                    }
171                    _ => {}
172                }
173            }
174            Ok(Some(Value::List(vec![Value::List(left), Value::List(right)])))
175        }
176        "list.enumerate" => {
177            let xs = extract_list(args, 0, "list.enumerate(xs)", span)?;
178            let out = xs
179                .into_iter()
180                .enumerate()
181                .map(|(idx, val)| {
182                    let mut rec = BTreeMap::new();
183                    rec.insert("index".to_string(), Value::I64(idx as i64));
184                    rec.insert("value".to_string(), val);
185                    Value::Record(rec)
186                })
187                .collect();
188            Ok(Some(Value::List(out)))
189        }
190        "list.partition" => {
191            let xs = extract_list(args, 0, "list.partition(xs, pivot_or_field)", span)?;
192            let crit = args.get(1).cloned().unwrap_or(Value::Null);
193            let mut matches = Vec::new();
194            let mut rest = Vec::new();
195            for item in xs {
196                let hit = match (&item, &crit) {
197                    (Value::Record(rec), Value::String(field)) => {
198                        rec.get(field).map(Value::is_truthy).unwrap_or(false)
199                    }
200                    (a, b) if a.as_f64().is_some() && b.as_f64().is_some() => {
201                        a.as_f64().unwrap_or(0.0) < b.as_f64().unwrap_or(0.0)
202                    }
203                    (a, b) => a == b,
204                };
205                if hit { matches.push(item) } else { rest.push(item) }
206            }
207            let mut rec = BTreeMap::new();
208            rec.insert("matches".to_string(), Value::List(matches.clone()));
209            rec.insert("rest".to_string(), Value::List(rest.clone()));
210            rec.insert("left".to_string(), Value::List(matches));
211            rec.insert("right".to_string(), Value::List(rest));
212            Ok(Some(Value::Record(rec)))
213        }
214        "list.uniq" => {
215            let xs = extract_list(args, 0, "list.uniq(xs)", span)?;
216            Ok(Some(Value::List(dedup_values(xs))))
217        }
218        "list.uniq_by" => {
219            let xs = extract_list(args, 0, "list.uniq_by(xs, key_field)", span)?;
220            let key_field = extract_str(args, 1, "list.uniq_by(xs, key_field)", span)?;
221            let mut seen = Vec::new();
222            let mut out = Vec::new();
223            for item in xs {
224                let proj = match &item {
225                    Value::Record(rec) => rec.get(&key_field).cloned().unwrap_or(Value::Null),
226                    other => other.clone(),
227                };
228                if !seen.contains(&proj) {
229                    seen.push(proj);
230                    out.push(item);
231                }
232            }
233            Ok(Some(Value::List(out)))
234        }
235        "list.intersperse" => {
236            let xs = extract_list(args, 0, "list.intersperse(xs, sep)", span)?;
237            let sep = args.get(1).cloned().unwrap_or(Value::Null);
238            let mut out = Vec::with_capacity(xs.len().saturating_mul(2));
239            for (i, item) in xs.into_iter().enumerate() {
240                if i > 0 {
241                    out.push(sep.clone());
242                }
243                out.push(item);
244            }
245            Ok(Some(Value::List(out)))
246        }
247        "list.flatten" => {
248            let xs = extract_list(args, 0, "list.flatten(xs)", span)?;
249            let mut out = Vec::new();
250            for item in xs {
251                match item {
252                    Value::List(sub) => out.extend(sub),
253                    other => out.push(other),
254                }
255            }
256            Ok(Some(Value::List(out)))
257        }
258        "list.shuffle_seeded" => {
259            let mut xs = extract_list(args, 0, "list.shuffle_seeded(xs, seed)", span)?;
260            let mut state = extract_i64(args, 1, "list.shuffle_seeded(xs, seed)", span)? as u64;
261            for i in (1..xs.len()).rev() {
262                state = splitmix64_next(state);
263                xs.swap(i, (state as usize) % (i + 1));
264            }
265            Ok(Some(Value::List(xs)))
266        }
267        "deque.new" => {
268            let items = match args.first() {
269                Some(Value::List(xs)) => xs.clone(),
270                _ => Vec::new(),
271            };
272            Ok(Some(wrap_collection("__deque", items)))
273        }
274        "deque.push_front" => {
275            let mut items = extract_collection_items(args, 0, "deque.push_front(d, val)", span)?;
276            items.insert(0, args.get(1).cloned().unwrap_or(Value::Null));
277            Ok(Some(wrap_collection("__deque", items)))
278        }
279        "deque.push_back" => {
280            let mut items = extract_collection_items(args, 0, "deque.push_back(d, val)", span)?;
281            items.push(args.get(1).cloned().unwrap_or(Value::Null));
282            Ok(Some(wrap_collection("__deque", items)))
283        }
284        "deque.pop_front" => {
285            let mut items = extract_collection_items(args, 0, "deque.pop_front(d)", span)?;
286            let val = if items.is_empty() { Value::Null } else { items.remove(0) };
287            let mut rec = BTreeMap::new();
288            rec.insert("value".to_string(), val);
289            rec.insert("deque".to_string(), wrap_collection("__deque", items));
290            Ok(Some(Value::Record(rec)))
291        }
292        "deque.pop_back" => {
293            let mut items = extract_collection_items(args, 0, "deque.pop_back(d)", span)?;
294            let val = items.pop().unwrap_or(Value::Null);
295            let mut rec = BTreeMap::new();
296            rec.insert("value".to_string(), val);
297            rec.insert("deque".to_string(), wrap_collection("__deque", items));
298            Ok(Some(Value::Record(rec)))
299        }
300        "pqueue.new" => {
301            let mut items = match args.first() {
302                Some(Value::List(xs)) => xs.clone(),
303                _ => Vec::new(),
304            };
305            items.sort_by(compare_pqueue_entries);
306            Ok(Some(wrap_collection("__pqueue", items)))
307        }
308        "pqueue.push" => {
309            let mut items =
310                extract_collection_items(args, 0, "pqueue.push(pq, priority, value)", span)?;
311            let mut entry = BTreeMap::new();
312            entry.insert("priority".to_string(), args.get(1).cloned().unwrap_or(Value::I64(0)));
313            entry.insert("value".to_string(), args.get(2).cloned().unwrap_or(Value::Null));
314            items.push(Value::Record(entry));
315            items.sort_by(compare_pqueue_entries);
316            Ok(Some(wrap_collection("__pqueue", items)))
317        }
318        "pqueue.pop_min" | "pqueue.pop_max" => {
319            let mut items = extract_collection_items(args, 0, path, span)?;
320            items.sort_by(compare_pqueue_entries);
321            let popped = if items.is_empty() {
322                None
323            } else if path == "pqueue.pop_min" {
324                Some(items.remove(0))
325            } else {
326                items.pop()
327            };
328            let (prio, val) = popped.map(unpack_pqueue_entry).unwrap_or((Value::Null, Value::Null));
329            let mut rec = BTreeMap::new();
330            rec.insert("priority".to_string(), prio);
331            rec.insert("value".to_string(), val);
332            rec.insert("pqueue".to_string(), wrap_collection("__pqueue", items));
333            Ok(Some(Value::Record(rec)))
334        }
335        "set.from_list" => {
336            let xs = extract_collection_items(args, 0, "set.from_list(xs)", span)?;
337            Ok(Some(Value::List(dedup_values(xs))))
338        }
339        "set.union" => {
340            let mut a = extract_collection_items(args, 0, "set.union(a, b)", span)?;
341            a.extend(extract_collection_items(args, 1, "set.union(a, b)", span)?);
342            Ok(Some(Value::List(dedup_values(a))))
343        }
344        "set.intersection" => {
345            let a = dedup_values(extract_collection_items(args, 0, "set.intersection(a, b)", span)?);
346            let b = extract_collection_items(args, 1, "set.intersection(a, b)", span)?;
347            Ok(Some(Value::List(a.into_iter().filter(|x| b.contains(x)).collect())))
348        }
349        "set.difference" => {
350            let a = dedup_values(extract_collection_items(args, 0, "set.difference(a, b)", span)?);
351            let b = extract_collection_items(args, 1, "set.difference(a, b)", span)?;
352            Ok(Some(Value::List(a.into_iter().filter(|x| !b.contains(x)).collect())))
353        }
354        "set.symmetric_difference" => {
355            let a = dedup_values(extract_collection_items(args, 0, path, span)?);
356            let b = dedup_values(extract_collection_items(args, 1, path, span)?);
357            let mut out: Vec<Value> = a.iter().filter(|x| !b.contains(x)).cloned().collect();
358            out.extend(b.into_iter().filter(|x| !a.contains(x)));
359            Ok(Some(Value::List(out)))
360        }
361        "set.is_subset" => {
362            let a = extract_collection_items(args, 0, "set.is_subset(a, b)", span)?;
363            let b = extract_collection_items(args, 1, "set.is_subset(a, b)", span)?;
364            Ok(Some(Value::Bool(a.iter().all(|x| b.contains(x)))))
365        }
366        "set.is_disjoint" => {
367            let a = extract_collection_items(args, 0, "set.is_disjoint(a, b)", span)?;
368            let b = extract_collection_items(args, 1, "set.is_disjoint(a, b)", span)?;
369            Ok(Some(Value::Bool(a.iter().all(|x| !b.contains(x)))))
370        }
371        _ => Ok(None),
372    }
373}
374
375fn compare_values_natural(a: &Value, b: &Value) -> Ordering {
376    match (a.as_f64(), b.as_f64()) {
377        (Some(fa), Some(fb)) => fa.partial_cmp(&fb).unwrap_or(Ordering::Equal),
378        _ => match (a, b) {
379            (Value::String(sa), Value::String(sb)) | (Value::Iri(sa), Value::Iri(sb)) => sa.cmp(sb),
380            (Value::Bool(ba), Value::Bool(bb)) => ba.cmp(bb),
381            _ => format!("{a}").cmp(&format!("{b}")),
382        },
383    }
384}
385
386fn dedup_values(xs: Vec<Value>) -> Vec<Value> {
387    let mut out = Vec::new();
388    for x in xs {
389        if !out.contains(&x) {
390            out.push(x);
391        }
392    }
393    out
394}
395
396fn splitmix64_next(state: u64) -> u64 {
397    let mut z = state.wrapping_add(0x9e3779b97f4a7c15);
398    z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
399    z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
400    z ^ (z >> 31)
401}
402
403fn wrap_collection(tag: &str, items: Vec<Value>) -> Value {
404    let mut rec = BTreeMap::new();
405    rec.insert(tag.to_string(), Value::Bool(true));
406    rec.insert("len".to_string(), Value::I64(items.len() as i64));
407    rec.insert("items".to_string(), Value::List(items));
408    Value::Record(rec)
409}
410
411fn extract_collection_items(
412    args: &[Value],
413    idx: usize,
414    ctx: &str,
415    span: Span,
416) -> Result<Vec<Value>, Diagnostic> {
417    match args.get(idx) {
418        Some(Value::List(xs)) => Ok(xs.clone()),
419        Some(Value::Record(rec)) => match rec.get("items") {
420            Some(Value::List(xs)) => Ok(xs.clone()),
421            _ => Ok(Vec::new()),
422        },
423        _ => Err(Diagnostic::new(
424            DiagCode::E100,
425            span,
426            format!("{ctx}: argument #{idx} must be a collection or list"),
427        )),
428    }
429}
430
431fn compare_pqueue_entries(a: &Value, b: &Value) -> Ordering {
432    let (pa, va) = borrow_pqueue_entry(a);
433    let (pb, vb) = borrow_pqueue_entry(b);
434    compare_values_natural(pa, pb).then_with(|| compare_values_natural(va, vb))
435}
436
437fn borrow_pqueue_entry(v: &Value) -> (&Value, &Value) {
438    if let Value::Record(rec) = v {
439        (
440            rec.get("priority").unwrap_or(&Value::Null),
441            rec.get("value").unwrap_or(&Value::Null),
442        )
443    } else {
444        (v, &Value::Null)
445    }
446}
447
448fn unpack_pqueue_entry(v: Value) -> (Value, Value) {
449    if let Value::Record(mut rec) = v {
450        (
451            rec.remove("priority").unwrap_or(Value::Null),
452            rec.remove("value").unwrap_or(Value::Null),
453        )
454    } else {
455        (Value::I64(0), v)
456    }
457}