1use 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
16const MAX_RANGE_LEN: usize = 65_536;
18
19pub(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}