diff options
author | Vincent Ambo <mail@tazj.in> | 2023-03-10T11·17+0300 |
---|---|---|
committer | tazjin <tazjin@tvl.su> | 2023-03-13T20·30+0000 |
commit | d00229753d32de2a38b52a3ae5feddc6ee10cefd (patch) | |
tree | 767ef8b350b0b193b8a9ce2f5685112ade3f2619 | |
parent | 21782d24f5f16942cb67fee6c098aa15bdf88d0c (diff) |
feat(tvix/eval): implement asynchronous list sorting algorithm r/5961
In order to implement an asynchronous builtins.sort (required for moving builtins to generators), we need an `async` sorting algorithm as our comparators involve invoking a Nix function. This commit implements a fairly simple, optimised bubble sort as the sorting algorithm used in our `async fn sort_by`. There don't seem to be any crates providing async versions of things like this, and they might actually be pretty hard to implement generically due to some constraints about how `async` works. Note that this algorithm is less efficient than the hybrid "timsort/mergesort/insert sort" used in the Rust standard library. I tried to write a merge sort implementation, but ran into isuses with the sort becoming unstable because our comparators can not yield equality. This is the simplest implementation which I know to be correct. Note that as of this commit this is *not* covered by the Tvix test suite, but it will be as soon as the rest of the generator code lands. Change-Id: Ia9a604f7dd941d6acc9212c902e0e637ed75bebc Reviewed-on: https://cl.tvl.fyi/c/depot/+/8239 Reviewed-by: Adam Joseph <adam@westernsemico.com> Tested-by: BuildkiteCI
-rw-r--r-- | tvix/eval/src/value/list.rs | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs index 5d1daf7c9c0b..e5ddc7bb96b9 100644 --- a/tvix/eval/src/value/list.rs +++ b/tvix/eval/src/value/list.rs @@ -5,7 +5,10 @@ use imbl::{vector, Vector}; use serde::{Deserialize, Serialize}; +use crate::errors::AddContext; use crate::errors::ErrorKind; +use crate::vm::generators; +use crate::vm::generators::GenCo; use crate::vm::VM; use super::thunk::ThunkSet; @@ -98,6 +101,50 @@ impl NixList { pub fn from_vec(vs: Vec<Value>) -> Self { Self(Vector::from_iter(vs.into_iter())) } + + /// 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(&mut self, co: &GenCo, cmp: Value) -> Result<(), ErrorKind> { + let mut len = self.len(); + + loop { + let mut new_len = 0; + for i in 1..len { + if generators::request_force( + co, + generators::request_call_with( + co, + cmp.clone(), + [self.0[i].clone(), self.0[i - 1].clone()], + ) + .await, + ) + .await + .as_bool() + .context("evaluating comparator in `builtins.sort`")? + { + self.0.swap(i, i - 1); + new_len = i; + } + } + + if new_len == 0 { + break; + } + + len = new_len; + } + + Ok(()) + } } impl IntoIterator for NixList { |