feat(tvix_eval): Support builtins.compareVersions r/4885

Added an Iterator over &str wich yields the VersionParts.

Change-Id: I8043d423127446a173d01d290aab10de0c24a6fc
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6619
Reviewed-by: tazjin <tazjin@tvl.su>
Tested-by: BuildkiteCI

4 files changed, 144 insertions, 0 deletions

diff --git a/tvix/eval/eval-okay-builtins-compareVersions.exp b/tvix/eval/eval-okay-builtins-compareVersions.exp
new file mode 100644
index 0000000000..b4d1452f4d
--- /dev/null
+++ b/tvix/eval/eval-okay-builtins-compareVersions.exp
@@ -0,0 +1 @@
+[ 0 -1 -1 0 0 0 1 1 -1 1 ]
\ No newline at end of file
diff --git a/tvix/eval/eval-okay-builtins-compareVersions.nix b/tvix/eval/eval-okay-builtins-compareVersions.nix
new file mode 100644
index 0000000000..769de79ad5
--- /dev/null
+++ b/tvix/eval/eval-okay-builtins-compareVersions.nix
@@ -0,0 +1,12 @@
+[
+  (builtins.compareVersions "1.2.3" "1.2.3")
+  (builtins.compareVersions "1.2.2" "1.2.3")
+  (builtins.compareVersions "1.2.3" "1.2.40")
+  (builtins.compareVersions "1.2.3" ".1.2.3")
+  (builtins.compareVersions "1.2.3" "1..2.3")
+  (builtins.compareVersions "1.2.3" "1.2.3.")
+  (builtins.compareVersions "1.2.3" "1.2")
+  (builtins.compareVersions "1.2.3" "1.2.a")
+  (builtins.compareVersions "1a.b" "1a.2")
+  (builtins.compareVersions "1" "")
+]
diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index 3f8b73f7d7..5b497cde7e 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -17,6 +17,10 @@ use crate::{
 
 use crate::arithmetic_op;
 
+use self::versions::VersionPartsIter;
+
+pub mod versions;
+
 /// Helper macro to ensure that a value has been forced. The structure
 /// of this is a little cumbersome as there are different reference
 /// types depending on whether the value is inside a thunk or not.
@@ -135,6 +139,25 @@ fn pure_builtins() -> Vec<Builtin> {
 
             Ok(Value::List(NixList::construct(output.len(), output)))
         }),
+        Builtin::new("compareVersions", 2, |mut args, vm| {
+            if let Value::Thunk(t) = &args[0] {
+                t.force(vm)?;
+            }
+            if let Value::Thunk(t) = &args[1] {
+                t.force(vm)?;
+            }
+
+            let s1 = args.pop().unwrap().to_str()?;
+            let s1 = VersionPartsIter::new(s1.as_str());
+            let s2 = args.pop().unwrap().to_str()?;
+            let s2 = VersionPartsIter::new(s2.as_str());
+
+            match s1.cmp(s2) {
+                std::cmp::Ordering::Less => Ok(Value::Integer(1)),
+                std::cmp::Ordering::Equal => Ok(Value::Integer(0)),
+                std::cmp::Ordering::Greater => Ok(Value::Integer(-1)),
+            }
+        }),
         Builtin::new("div", 2, |mut args, _| {
             let b = args.pop().unwrap();
             let a = args.pop().unwrap();
diff --git a/tvix/eval/src/builtins/versions.rs b/tvix/eval/src/builtins/versions.rs
new file mode 100644
index 0000000000..cc36ae5b6e
--- /dev/null
+++ b/tvix/eval/src/builtins/versions.rs
@@ -0,0 +1,108 @@
+use std::ops::RangeInclusive;
+
+/// Version strings can be broken up into Parts.
+/// One Part represents either a string of digits or characters.
+/// '.' and '_' represent deviders between parts and are not included in any part.
+#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Debug)]
+pub enum VersionPart<'a> {
+    Word(&'a str),
+    Number(u64),
+}
+
+/// Type used to hold information about a VersionPart during creation
+enum InternalPart {
+    Number { range: RangeInclusive<usize> },
+    Word { range: RangeInclusive<usize> },
+    Break,
+}
+
+/// An iterator which yields the parts of a version string.
+///
+/// This can then be directly used to compare two versions
+pub struct VersionPartsIter<'a> {
+    cached_part: InternalPart,
+    iter: std::str::CharIndices<'a>,
+    version: &'a str,
+}
+
+impl<'a> VersionPartsIter<'a> {
+    pub fn new(version: &'a str) -> Self {
+        Self {
+            cached_part: InternalPart::Break,
+            iter: version.char_indices(),
+            version,
+        }
+    }
+}
+
+impl<'a> Iterator for VersionPartsIter<'a> {
+    type Item = VersionPart<'a>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let char = self.iter.next();
+
+        if char.is_none() {
+            let cached_part = std::mem::replace(&mut self.cached_part, InternalPart::Break);
+            match cached_part {
+                InternalPart::Break => return None,
+                InternalPart::Number { range } => {
+                    return Some(VersionPart::Number(self.version[range].parse().unwrap()))
+                }
+                InternalPart::Word { range } => {
+                    return Some(VersionPart::Word(&self.version[range]))
+                }
+            }
+        }
+
+        let (pos, char) = char.unwrap();
+        match char {
+            // Divider encountered
+            '.' | '_' => {
+                let cached_part = std::mem::replace(&mut self.cached_part, InternalPart::Break);
+                match cached_part {
+                    InternalPart::Number { range } => {
+                        Some(VersionPart::Number(self.version[range].parse().unwrap()))
+                    }
+                    InternalPart::Word { range } => Some(VersionPart::Word(&self.version[range])),
+                    InternalPart::Break => self.next(),
+                }
+            }
+
+            // digit encountered
+            _ if char.is_ascii_digit() => {
+                let cached_part = std::mem::replace(
+                    &mut self.cached_part,
+                    InternalPart::Number { range: pos..=pos },
+                );
+                match cached_part {
+                    InternalPart::Number { range } => {
+                        self.cached_part = InternalPart::Number {
+                            range: *range.start()..=*range.end() + 1,
+                        };
+                        self.next()
+                    }
+                    InternalPart::Word { range } => Some(VersionPart::Word(&self.version[range])),
+                    InternalPart::Break => self.next(),
+                }
+            }
+
+            // char encountered
+            _ => {
+                let mut cached_part = InternalPart::Word { range: pos..=pos };
+                std::mem::swap(&mut cached_part, &mut self.cached_part);
+                match cached_part {
+                    InternalPart::Word { range } => {
+                        self.cached_part = InternalPart::Word {
+                            range: *range.start()..=*range.end() + char.len_utf8(),
+                        };
+                        self.next()
+                    }
+                    InternalPart::Number { range } => {
+                        Some(VersionPart::Number(self.version[range].parse().unwrap()))
+                    }
+                    InternalPart::Break => self.next(),
+                }
+            }
+        }
+    }
+}