diff options
author | sterni <sternenseemann@systemli.org> | 2022-09-21T11·44+0200 |
---|---|---|
committer | sterni <sternenseemann@systemli.org> | 2022-09-21T14·23+0000 |
commit | 9a8a6a33f9265a3844e91f2c1aab0b28ac46decf (patch) | |
tree | 6ed0e4dba73bf1ce9e5fd272d303b931c6080e7e | |
parent | e9e06b8bae9b4f55ace0e8e6b6ae5e77de4c8e71 (diff) |
fix(tvix/eval): implement C++ Nix version part comparison algorithm r/4949
This is based on the [relevant code] in C++ Nix. Our version has more branches because the C++ one only checks if it is less than or not, so can save handling a few cases. We on the other hand, can avoid calling the algorithm twice. It'd be nice to implement proptests for this in the future and to make sure that this weird little algorithm doesn't violate the Ord laws. [relevant code]: https://github.com/NixOS/nix/blob/cd35bbbeef72375873e396b9ffed14a4638693a8/src/libstore/names.cc#L81-L94 Change-Id: I46642e6da5eac7c0883cdce860622cdba04cd12b Reviewed-on: https://cl.tvl.fyi/c/depot/+/6719 Tested-by: BuildkiteCI Reviewed-by: tazjin <tazjin@tvl.su>
-rw-r--r-- | tvix/eval/src/builtins/versions.rs | 38 |
1 files changed, 37 insertions, 1 deletions
diff --git a/tvix/eval/src/builtins/versions.rs b/tvix/eval/src/builtins/versions.rs index 33679ed4034b..ee75eeaeed3b 100644 --- a/tvix/eval/src/builtins/versions.rs +++ b/tvix/eval/src/builtins/versions.rs @@ -1,14 +1,50 @@ +use std::cmp::Ordering; 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)] +#[derive(PartialEq, Eq, Clone, Debug)] pub enum VersionPart<'a> { Word(&'a str), Number(&'a str), } +impl PartialOrd for VersionPart<'_> { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + Some(self.cmp(other)) + } +} + +impl Ord for VersionPart<'_> { + fn cmp(self: &Self, other: &Self) -> Ordering { + match (self, other) { + (VersionPart::Number(s1), VersionPart::Number(s2)) => { + // Note: C++ Nix uses `int`, but probably doesn't make a difference + // We trust that the splitting was done correctly and parsing will work + let n1: u64 = s1.parse().unwrap(); + let n2: u64 = s2.parse().unwrap(); + n1.cmp(&n2) + } + + // empty Word always looses + (VersionPart::Word(""), VersionPart::Number(_)) => Ordering::Less, + (VersionPart::Number(_), VersionPart::Word("")) => Ordering::Greater, + + // `pre` looses unless the other part is also a `pre` + (VersionPart::Word("pre"), VersionPart::Word("pre")) => Ordering::Equal, + (VersionPart::Word("pre"), _) => Ordering::Less, + (_, VersionPart::Word("pre")) => Ordering::Greater, + + // Number wins against Word + (VersionPart::Number(_), VersionPart::Word(_)) => Ordering::Greater, + (VersionPart::Word(_), VersionPart::Number(_)) => Ordering::Less, + + (VersionPart::Word(w1), VersionPart::Word(w2)) => w1.cmp(w2), + } + } +} + /// Type used to hold information about a VersionPart during creation enum InternalPart { Number { range: RangeInclusive<usize> }, |