From 3412ae495661e8073075bbb8c24ee0098ca2bede Mon Sep 17 00:00:00 2001 From: Griffin Smith Date: Sun, 23 Oct 2022 13:50:07 -0400 Subject: feat(tvix/eval): Implement builtins.sort This is a bit tricky because the comparator can throw errors, so we need to propagate them out if they exist and try to avoid sorting forever by returning a reasonable ordering in this case (as short-circuiting is not available). Co-Authored-By: Vincent Ambo Change-Id: Icae1d30f43ec1ae64b2ba51e73ee467605686792 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7072 Tested-by: BuildkiteCI Reviewed-by: sterni --- tvix/eval/src/builtins/mod.rs | 41 ++++++++++++++++++++-- tvix/eval/src/tests/nix_tests/eval-okay-sort.exp | 1 + tvix/eval/src/tests/nix_tests/eval-okay-sort.nix | 20 +++++++++++ .../nix_tests/notyetpassing/eval-okay-sort.exp | 1 - .../nix_tests/notyetpassing/eval-okay-sort.nix | 20 ----------- tvix/eval/src/value/list.rs | 8 ++++- 6 files changed, 67 insertions(+), 24 deletions(-) create mode 100644 tvix/eval/src/tests/nix_tests/eval-okay-sort.exp create mode 100644 tvix/eval/src/tests/nix_tests/eval-okay-sort.nix delete mode 100644 tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-sort.exp delete mode 100644 tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-sort.nix (limited to 'tvix/eval/src') diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs index 5c029605f1ec..7f55c90c15ad 100644 --- a/tvix/eval/src/builtins/mod.rs +++ b/tvix/eval/src/builtins/mod.rs @@ -628,10 +628,47 @@ fn pure_builtins() -> Vec { }, ), Builtin::new("seq", &[true, true], |mut args: Vec, _: &mut VM| { - // The builtin calling infra has already forced both args for us, so we just return the - // second and ignore the first + // The builtin calling infra has already forced both args for us, so + // we just return the second and ignore the first Ok(args.pop().unwrap()) }), + Builtin::new("sort", &[true, true], |args: Vec, vm: &mut VM| { + let mut list = args[1].to_list()?; + let comparator = &args[0]; + + // Used to let errors "escape" from the sorting closure. If anything + // ends up setting an error, it is returned from this function. + let mut error: Option = None; + + list.sort_by(|lhs, rhs| { + let result = vm + .call_with(comparator, [lhs.clone(), rhs.clone()]) + .map_err(|err| ErrorKind::ThunkForce(Box::new(err))) + .and_then(|v| v.force(vm)?.as_bool()); + + match (&error, result) { + // The contained closure only returns a "less + // than?"-boolean, no way to yield "equal". + (None, Ok(true)) => Ordering::Less, + (None, Ok(false)) => Ordering::Greater, + + // Closest thing to short-circuiting out if an error was + // thrown. + (Some(_), _) => Ordering::Equal, + + // Propagate the error if one was encountered. + (_, Err(e)) => { + error = Some(e); + Ordering::Equal + } + } + }); + + match error { + None => Ok(Value::List(list)), + Some(e) => Err(e), + } + }), Builtin::new("splitVersion", &[true], |args: Vec, _: &mut VM| { let s = args[0].to_str()?; let s = VersionPartsIter::new(s.as_str()); diff --git a/tvix/eval/src/tests/nix_tests/eval-okay-sort.exp b/tvix/eval/src/tests/nix_tests/eval-okay-sort.exp new file mode 100644 index 000000000000..899119e20e38 --- /dev/null +++ b/tvix/eval/src/tests/nix_tests/eval-okay-sort.exp @@ -0,0 +1 @@ +[ [ 42 77 147 249 483 526 ] [ 526 483 249 147 77 42 ] [ "bar" "fnord" "foo" "xyzzy" ] [ { key = 1; value = "foo"; } { key = 1; value = "fnord"; } { key = 2; value = "bar"; } ] [ [ ] [ ] [ 1 ] [ 1 4 ] [ 1 5 ] [ 1 6 ] [ 2 ] [ 2 3 ] [ 3 ] [ 3 ] ] ] diff --git a/tvix/eval/src/tests/nix_tests/eval-okay-sort.nix b/tvix/eval/src/tests/nix_tests/eval-okay-sort.nix new file mode 100644 index 000000000000..50aa78e40325 --- /dev/null +++ b/tvix/eval/src/tests/nix_tests/eval-okay-sort.nix @@ -0,0 +1,20 @@ +with builtins; + +[ (sort lessThan [ 483 249 526 147 42 77 ]) + (sort (x: y: y < x) [ 483 249 526 147 42 77 ]) + (sort lessThan [ "foo" "bar" "xyzzy" "fnord" ]) + (sort (x: y: x.key < y.key) + [ { key = 1; value = "foo"; } { key = 2; value = "bar"; } { key = 1; value = "fnord"; } ]) + (sort lessThan [ + [ 1 6 ] + [ ] + [ 2 3 ] + [ 3 ] + [ 1 5 ] + [ 2 ] + [ 1 ] + [ ] + [ 1 4 ] + [ 3 ] + ]) +] diff --git a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-sort.exp b/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-sort.exp deleted file mode 100644 index 899119e20e38..000000000000 --- a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-sort.exp +++ /dev/null @@ -1 +0,0 @@ -[ [ 42 77 147 249 483 526 ] [ 526 483 249 147 77 42 ] [ "bar" "fnord" "foo" "xyzzy" ] [ { key = 1; value = "foo"; } { key = 1; value = "fnord"; } { key = 2; value = "bar"; } ] [ [ ] [ ] [ 1 ] [ 1 4 ] [ 1 5 ] [ 1 6 ] [ 2 ] [ 2 3 ] [ 3 ] [ 3 ] ] ] diff --git a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-sort.nix b/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-sort.nix deleted file mode 100644 index 50aa78e40325..000000000000 --- a/tvix/eval/src/tests/nix_tests/notyetpassing/eval-okay-sort.nix +++ /dev/null @@ -1,20 +0,0 @@ -with builtins; - -[ (sort lessThan [ 483 249 526 147 42 77 ]) - (sort (x: y: y < x) [ 483 249 526 147 42 77 ]) - (sort lessThan [ "foo" "bar" "xyzzy" "fnord" ]) - (sort (x: y: x.key < y.key) - [ { key = 1; value = "foo"; } { key = 2; value = "bar"; } { key = 1; value = "fnord"; } ]) - (sort lessThan [ - [ 1 6 ] - [ ] - [ 2 3 ] - [ 3 ] - [ 1 5 ] - [ 2 ] - [ 1 ] - [ ] - [ 1 4 ] - [ 3 ] - ]) -] diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs index 236a654ad88d..da8f70caacaf 100644 --- a/tvix/eval/src/value/list.rs +++ b/tvix/eval/src/value/list.rs @@ -1,5 +1,5 @@ //! This module implements Nix lists. -use std::ops::Deref; +use std::ops::{Deref, DerefMut}; use crate::errors::ErrorKind; use crate::vm::VM; @@ -135,3 +135,9 @@ impl Deref for NixList { &self.0 } } + +impl DerefMut for NixList { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} -- cgit 1.4.1