diff options
author | Aspen Smith <root@gws.fyi> | 2024-02-08T21·52-0500 |
---|---|---|
committer | aspen <root@gws.fyi> | 2024-02-08T22·50+0000 |
commit | 8446cd1c8b5747738264dea9acd2be76e2db054e (patch) | |
tree | 69d5298c4dad04da84ce02babc8a61f5656e390c /tvix/eval/src/value/list.rs | |
parent | ddb7bc8d18bd11deb87a70ec300a281aaf34c2c7 (diff) |
fix(tvix/eval): Inline List.sort_by, and propagate errors r/7488
In order to correctly propagate errors in the comparator passed to builtins.sort, we need to do all the sorting in a context where we can short-circuit return `Value`s (because catchables are Values on the `Ok` side of the Result , not `Err`s). Unfortunately this means we have to *inline* the List `sort_by` implementation into the builtin_sort function - fortunately this is the only place that was called so this is relatively low cost. This does that, and adds the requisite `try_value!` invocation to allow us to propagate comparator errors here. As before, this doesn't include tests, primarily since those are coming in the next commit. Change-Id: I8453c3aa2cd82299eae89828e2a2bb118da4cd48 Reviewed-on: https://cl.tvl.fyi/c/depot/+/10754 Tested-by: BuildkiteCI Reviewed-by: raitobezarius <tvl@lahfa.xyz>
Diffstat (limited to 'tvix/eval/src/value/list.rs')
-rw-r--r-- | tvix/eval/src/value/list.rs | 50 |
1 files changed, 0 insertions, 50 deletions
diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs index 627956399399..2b8b3de28d19 100644 --- a/tvix/eval/src/value/list.rs +++ b/tvix/eval/src/value/list.rs @@ -6,11 +6,6 @@ use imbl::{vector, Vector}; use serde::Deserialize; -use crate::generators; -use crate::generators::GenCo; -use crate::AddContext; -use crate::ErrorKind; - use super::thunk::ThunkSet; use super::TotalDisplay; use super::Value; @@ -78,51 +73,6 @@ impl NixList { pub fn from_vec(vs: Vec<Value>) -> Self { Self(Rc::new(Vector::from_iter(vs))) } - - /// Asynchronous sorting algorithm in which the comparator can make use of - /// VM requests (required as `builtins.sort` uses comparators written in - /// Nix). - /// - /// This is a simple, optimised bubble sort implementation. The choice of - /// algorithm is constrained by the comparator in Nix not being able to - /// yield equality, and us being unable to use the standard library - /// implementation of sorting (which is a lot longer, but a lot more - /// efficient) here. - // TODO(amjoseph): Investigate potential impl in Nix code, or Tvix bytecode. - pub async fn sort_by(self, co: &GenCo, cmp: Value) -> Result<Self, ErrorKind> { - let mut len = self.len(); - let mut data = self.into_inner(); - - loop { - let mut new_len = 0; - for i in 1..len { - if generators::request_force( - co, - generators::request_call_with( - co, - cmp.clone(), - [data[i].clone(), data[i - 1].clone()], - ) - .await, - ) - .await - .as_bool() - .context("evaluating comparator in `builtins.sort`")? - { - data.swap(i, i - 1); - new_len = i; - } - } - - if new_len == 0 { - break; - } - - len = new_len; - } - - Ok(data.into()) - } } impl IntoIterator for NixList { |