From 8446cd1c8b5747738264dea9acd2be76e2db054e Mon Sep 17 00:00:00 2001
From: Aspen Smith <root@gws.fyi>
Date: Thu, 8 Feb 2024 16:52:15 -0500
Subject: fix(tvix/eval): Inline List.sort_by, and propagate errors

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>
---
 tvix/eval/src/builtins/mod.rs | 48 ++++++++++++++++++++++++++++++++++++++---
 tvix/eval/src/value/list.rs   | 50 -------------------------------------------
 2 files changed, 45 insertions(+), 53 deletions(-)

(limited to 'tvix/eval/src')

diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index 716da4d041..d9f8567886 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -87,7 +87,7 @@ mod pure_builtins {
     use itertools::Itertools;
     use os_str_bytes::OsStringBytes;
 
-    use crate::{value::PointerEquality, NixContext, NixContextElement};
+    use crate::{value::PointerEquality, AddContext, NixContext, NixContextElement};
 
     use super::*;
 
@@ -1223,8 +1223,50 @@ mod pure_builtins {
     #[builtin("sort")]
     async fn builtin_sort(co: GenCo, comparator: Value, list: Value) -> Result<Value, ErrorKind> {
         let list = list.to_list()?;
-        let sorted = list.sort_by(&co, comparator).await?;
-        Ok(Value::List(sorted))
+        let mut len = list.len();
+        let mut data = list.into_inner();
+
+        // 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.
+        loop {
+            let mut new_len = 0;
+            for i in 1..len {
+                if try_value!(
+                    generators::request_force(
+                        &co,
+                        generators::request_call_with(
+                            &co,
+                            comparator.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(Value::List(data.into()))
     }
 
     #[builtin("splitVersion")]
diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs
index 6279563993..2b8b3de28d 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 {
-- 
cgit 1.4.1