fix(tvix/eval): compare versions with an extra empty component r/4950

This is necessary because builtins.compareVersions compares versions in
a subtly not-quite-but-still-lexicographical way: `pre` for example can
have an effect if it is post-fixed: `2.3 < 2.3pre`. This is a violation
of the rule that in a lexicographical ordering, the longer string is
considered greater if they are otherwise equal. builtins.compareVersion
is comparing lexicographically though, if you do the following
transformation beforehand:

  2.3 --split--> [ "2" "3" ] --append--> [ "2" "3" "" ]
  2.3pre --split--> [ "2" "3" "pre" ] --append--> [ "2" "3" "pre" "" ]

Comparing the transformed version is then done lexicographically:

  2.3 < 2.3.0pre since [ "2" "3" "" ] < [ "2" "3" "0" "pre" ]

Here, the `pre` rule never comes into effect because no comparison on it
happens, instead we use the longer string rule of a lexicographical
comparison.

In the C++ codebase, the reason for this behavior is that the
iterator-esque construct they use always yields the empty string before
it exposes it has been fully consumed. This is probably intentional to
support the postfixed `pre` which is, for example, used by NixOS
versions (e.g. unstable post 22.05 is 22.11-pre). We replicate this
behavior using the `Chain` iterator in `VersionPartsIter::new_for_cmp`.

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

2 files changed, 17 insertions, 2 deletions

diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index 0b1fe540fe..55135c4d8d 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -103,9 +103,9 @@ fn pure_builtins() -> Vec<Builtin> {
         }),
         Builtin::new("compareVersions", &[true, true], |args, _| {
             let s1 = args[0].to_str()?;
-            let s1 = VersionPartsIter::new(s1.as_str());
+            let s1 = VersionPartsIter::new_for_cmp(s1.as_str());
             let s2 = args[1].to_str()?;
-            let s2 = VersionPartsIter::new(s2.as_str());
+            let s2 = VersionPartsIter::new_for_cmp(s2.as_str());
 
             match s1.cmp(s2) {
                 std::cmp::Ordering::Less => Ok(Value::Integer(-1)),
diff --git a/tvix/eval/src/builtins/versions.rs b/tvix/eval/src/builtins/versions.rs
index ee75eeaeed..e149cc4dba 100644
--- a/tvix/eval/src/builtins/versions.rs
+++ b/tvix/eval/src/builtins/versions.rs
@@ -1,4 +1,5 @@
 use std::cmp::Ordering;
+use std::iter::{once, Chain, Once};
 use std::ops::RangeInclusive;
 
 /// Version strings can be broken up into Parts.
@@ -69,6 +70,20 @@ impl<'a> VersionPartsIter<'a> {
             version,
         }
     }
+
+    /// Create an iterator that yields all version parts followed by an additional
+    /// `VersionPart::Word("")` part (i.e. you can think of this as
+    /// `builtins.splitVersion version ++ [ "" ]`). This is necessary, because
+    /// Nix's `compareVersions` is not entirely lexicographical: If we have two
+    /// equal versions, but one is longer, the longer one is only considered
+    /// greater if the first additional part of the longer version is not `pre`,
+    /// e.g. `2.3 > 2.3pre`. It is otherwise lexicographical, so peculiar behavior
+    /// like `2.3 < 2.3.0pre` ensues. Luckily for us, this means that we can
+    /// lexicographically compare two version strings, _if_ we append an extra
+    /// component to both versions.
+    pub fn new_for_cmp(version: &'a str) -> Chain<Self, Once<VersionPart>> {
+        Self::new(version).chain(once(VersionPart::Word("")))
+    }
 }
 
 impl<'a> Iterator for VersionPartsIter<'a> {