General version comparison

Greetings all,

I work on conda, and I would like to rework its underpinnings regarding package metadata handling to use Rust. One of the first things I need to work out is version comparison. I found version-compare and that is indeed a great start. Tim and I had a lot of discussion on how to improve it at https://github.com/timvisee/version-compare/issues/20

TL;DR: we think the best way to generalize version comparison is to have versions represented as vectors of parts, and have specific behavior implemented as parsing (which parts get emitted) and also specific comparison behavior for parts.

I'm a bit stuck on how to unify partial_cmp. Here's my current state:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7ef94a07310bfa81bb5cbef24c9d0fc4

This is failing to compile with:

 = note: the method `partial_cmp` exists but the following trait bounds were not satisfied:
       `&mut T : std::iter::Iterator`

I think that's because the generic type T requires that my code handle things with iterators (strings?) as well as things without (integers). Is that accurate? What's the best path forward here? Please feel free to tell me I'm doing this all wrong - I'm a rust neophyte coming from python, and a lot of the static typing is very foreign to me.

Welcome to Rust user forum! Great to see conda people here :slightly_smiling_face:

Let's fix the errors step by step using compiler helpful suggestions as follows:

Step 1: If you look closer, compiler is suggesting another thing

impl<T: std::cmp::PartialOrd> VersionPart<T> for DefaultPart<T>

Step 2: Adding it shows another error:

  --> src/lib.rs:27:39
   |
27 |         self._value.partial_cmp(other.into())
   |                                       ^^^^ the trait `std::convert::From<T>` is not implemented for `&T`
   |
   = help: the following implementations were found:
             <T as std::convert::From<T>>
   = note: required because of the requirements on the impl of `std::convert::Into<&T>` for `T`

so a fix can be to remove other.into() and make it &other.

Step 3: Making the above changes points to another error:

error[E0599]: no method named `compare_priority` found for type `&DefaultPart<T>` in the current scope
  --> src/lib.rs:38:15
   |
38 |         (self.compare_priority(other.priority()) == Some(Ordering::Equal)) &&
   |               ^^^^^^^^^^^^^^^^
   |
   = note: the method `compare_priority` exists but the following trait bounds were not satisfied:
           `DefaultPart<T> : VersionPart<_>`
   = help: items from traits can only be used if the trait is implemented and in scope
   = note: the following trait defines an item `compare_priority`, perhaps you need to implement it:
           candidate #1: `VersionPart`

then you might say how come? because we've implemented

impl<T: PartialOrd> VersionPart<T> for DefaultPart<T>

however, pay attention to the added bound T: PartialOrd which needs to be reflected to

impl<T, U> PartialEq<DefaultPart<U>> for DefaultPart<T>
    where
        T: std::convert::From<U>,
        T: PartialEq,
        U: PartialEq

Note that pub trait PartialOrd<Rhs = Self>: PartialEq<Rhs> i.e. a subtrait of PartialEq so

Step 4: making T: PartialOrd and U: PartialOrd points to another error:

error[E0277]: can't compare `T` with `T`
  --> src/lib.rs:13:17
   |
13 | #[derive(Debug, Eq, Ord)]
   |                 ^^ no implementation for `T < T` and `T > T`
   |
   = help: the trait `std::cmp::PartialOrd` is not implemented for `T`
   = help: consider adding a `where T: std::cmp::PartialOrd` bound
   = note: required because of the requirements on the impl of `std::cmp::PartialEq` for `DefaultPart<T>`

So we need to remove the derived Eq and Ord mainly because as doc says:

Implementations of PartialEq , PartialOrd , and Ord must agree with each other. It's easy to accidentally make them disagree by deriving some of the traits and manually implementing others.

Step 5: Compiling again points to the last error which is

error[E0507]: cannot move out of `self._value` which is behind a shared reference
  --> src/lib.rs:22:27
   |
22 |     fn value(&self) -> T {self._value.into()}
   |                           ^^^^^^^^^^^ move occurs because `self._value` has type `T`, which does not implement the `Copy` trait

The error says it all, you're moving an internal value from a shared reference &self without specifying T: Copy. A fix can be to add the more generate trait Clone (where Copy: Clone)
to make the code compile successfully.

However, since you have made all the fields of your struct private, then writing functions like

pub fn EpochPart<'a>(v: i32) -> DefaultPart<i32> {DefaultPart{_priority: 0, _value: v }}

results into leak of private parts

error[E0446]: private type `DefaultPart<i32>` in public interface
  --> src/lib.rs:63:1
   |
14 | struct DefaultPart<T: Clone> {
   | - `DefaultPart<i32>` declared as private
...
63 | pub fn EpochPart<'a>(v: i32) -> DefaultPart<i32> {DefaultPart{_priority: 0, _value: v }}
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ can't leak private type

So you'd need to make them public explicitly like

pub struct DefaultPart<T: Clone> {
    pub _priority: i8,
    pub _value: T,
}

however, in standard lint, _ implies a private field, so it'd better to remove _ from the fields

pub struct DefaultPart<T: Clone> {
    pub priority: i8,
    pub value: T,
}

The final last linting fix is that functions in Rust are snake_case which I leave them to you.

2 Likes

Thank you @ehsanmok for the very lengthy and detailed reply. I am very grateful for the time you've spent and saved me in researching each of these issues.

My hope had been to convey equivalence relations, per https://doc.rust-lang.org/std/cmp/trait.Eq.html, but now that I think more about it, I recognize that I can't really prove equivalence to the compiler. The intention of the priority is that it will preclude comparison of non-matching types, but even then, if a float type is compared with a NaN value, it will be valid under my assumption, and not valid for an equivalence relation.

The thought behind that was to try to create something that makes the types easier to use, especially getting the priority right. I'm happy to make them something like get_epoch_part(value), and I guess that's clear enough. I just find myself really wanting specialization/subclassing here.

The code here doesn't compare different structs, just the same struct with different types. I think I'll have to add that in at some point to deal with comparison that isn't just the default for a given type (i32, String, etc.), which will be the case for PEP440 strings and their special-cased "dev" and "post" behavior. At that point, I think I'll have to add in Box<dyn VersionPart> as the type for "other" - does that sound right? If I add that in, will comparisons for types within DefaultValue still be monomorphized, as I believe they are now?

I just find myself really wanting specialization/subclassing here.

This is a common feeling coming from OOP background and it goes away gradually :stuck_out_tongue_winking_eye: (fyi there's specialization but it's in nightly).

At that point, I think I'll have to add in Box<dyn VersionPart> as the type for "other" - does that sound right? If I add that in, will comparisons for types within DefaultValue still be monomorphized, as I believe they are now?

To enforce monomophization you can add impl VersionPart. The Box<dyn VersionPart> is dynamically dispatched which could be a option at the expense of some runtime overhead, depending on how you want to formulate stuff.

1 Like