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

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 {