feat(tvix/eval): Support builtins.substring r/4916

Nix's `builtins.substring`:
- doesn't accept negative indexes for `beg` or `end`. Compare the error messages
  for:
  - `builtins.substring -3  5 "testing"`
  - `builtins.substring  3 -5 "testing"`
  - `builtins.substring -3 -5 "testing"`
- returns an empty string when `beg >= end`
- allows `end` to exceed the length of the input string

Change-Id: I83af7a099d81b6d537ebe5029d946c7031cb7113
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6555
Reviewed-by: wpcarro <wpcarro@gmail.com>
Autosubmit: wpcarro <wpcarro@gmail.com>
Reviewed-by: tazjin <tazjin@tvl.su>
Tested-by: BuildkiteCI

4 files changed, 61 insertions, 0 deletions

diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index aeffca4995..4bcaaf7a00 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -4,6 +4,7 @@
 //! available builtins in Nix.
 
 use std::{
+    cmp,
     collections::{BTreeMap, HashMap},
     path::PathBuf,
     rc::Rc,
@@ -192,6 +193,34 @@ fn pure_builtins() -> Vec<Builtin> {
             let a = args.pop().unwrap();
             arithmetic_op!(a, b, -)
         }),
+        Builtin::new("substring", 3, |args, vm| {
+            let beg = args[0].force(vm)?.as_int()?;
+            let len = args[1].force(vm)?.as_int()?;
+            let x = args[2].force(vm)?.to_str()?;
+
+            if beg < 0 {
+                return Err(ErrorKind::IndexOutOfBounds { index: beg });
+            }
+            let beg = beg as usize;
+
+            // Nix doesn't assert that the length argument is
+            // non-negative when the starting index is GTE the
+            // string's length.
+            if beg >= x.as_str().len() {
+                return Ok(Value::String("".into()));
+            }
+
+            if len < 0 {
+                return Err(ErrorKind::NegativeLength { length: len });
+            }
+
+            let len = len as usize;
+            let end = cmp::min(beg + len, x.as_str().len());
+
+            Ok(Value::String(
+                x.as_str()[(beg as usize)..(end as usize)].into(),
+            ))
+        }),
         Builtin::new("throw", 1, |mut args, _| {
             return Err(ErrorKind::Throw(
                 args.pop().unwrap().to_str()?.as_str().to_owned(),
diff --git a/tvix/eval/src/errors.rs b/tvix/eval/src/errors.rs
index 1b8f58356c..6331ee64be 100644
--- a/tvix/eval/src/errors.rs
+++ b/tvix/eval/src/errors.rs
@@ -80,6 +80,11 @@ pub enum ErrorKind {
     /// An error occurred when parsing an integer
     ParseIntError(ParseIntError),
 
+    /// A negative integer was used as a value representing length.
+    NegativeLength {
+        length: i64,
+    },
+
     /// Tvix internal warning for features triggered by users that are
     /// not actually implemented yet, and without which eval can not
     /// proceed.
@@ -213,6 +218,13 @@ to a missing value in the attribute set(s) included via `with`."#,
                 format!("invalid integer: {}", err)
             }
 
+            ErrorKind::NegativeLength { length } => {
+                format!(
+                    "cannot use a negative integer, {}, for a value representing length",
+                    length
+                )
+            }
+
             ErrorKind::NotImplemented(feature) => {
                 format!("feature not yet implemented in Tvix: {}", feature)
             }
@@ -244,6 +256,7 @@ to a missing value in the attribute set(s) included via `with`."#,
             ErrorKind::IndexOutOfBounds { .. } => "E019",
             ErrorKind::NotAnAbsolutePath(_) => "E020",
             ErrorKind::ParseIntError(_) => "E021",
+            ErrorKind::NegativeLength { .. } => "E022",
             ErrorKind::NotImplemented(_) => "E999",
         }
     }
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-substring.exp b/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-substring.exp
new file mode 100644
index 0000000000..1682760228
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-substring.exp
@@ -0,0 +1 @@
+[ "tes" "testing" "" "estin" "ting" "" "" "" "" "est" "est" "est" "est" "est" "est" "" ]
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-substring.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-substring.nix
new file mode 100644
index 0000000000..f4ee82e273
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-builtins-substring.nix
@@ -0,0 +1,18 @@
+[
+  (builtins.substring 0 3 "testing")
+  (builtins.substring 0 300 "testing")
+  (builtins.substring 3 0 "testing")
+  (builtins.substring 1 5 "testing")
+  (builtins.substring 3 5 "testing")
+  (builtins.substring 300 300 "testing")
+  (builtins.substring 301 300 "testing")
+  (builtins.substring 0 0 "")
+  (builtins.substring 0 1 "")
+  (builtins.substring (builtins.add 0 1) 3 "testing")
+  (builtins.substring 1 (builtins.add 3 0) "testing")
+  (builtins.substring (builtins.add 0 1) (builtins.add 3 0) "testing")
+  (builtins.substring (builtins.add 0 1) (builtins.add 3 0) "testing")
+  (builtins.substring (builtins.add 0 1) (builtins.add 3 0) ("test" + "ing"))
+  (builtins.substring (builtins.add 0 1) (builtins.add 3 0) ("test" + "ing"))
+  (builtins.substring 300 (-10) "testing")
+]