Repository: mitsuhiko/minijinja (rust)

Issue:
Violation of `PartialEq`, `Eq`, `PartialOrd` and `Ord` contracts in `minijinja::Value`
## Description

The `Ord` and `PartialEq` implementations of `minijinja::Value` work as follows:

1. Coerce the types of the two `Value`s to be equal
    - Equal types are left as-is
    - When both sides are integers, everything is converted to `i128`
    - When either side is a float, both sides are coerced to a float,
    - Otherwise try to coerce to `i128` on both sides
2. If this coercion was successful, do the comparison on the resulting values
2. Otherwise, try to compare the values as if they were objects

This violates the transitivity property of the comparison traits, which, in addition to producing unexpected but niche behaviour, also can cause panics while sorting [due to the new sorting algorithms of Rust 1.81 panicking on invalid `Ord` implementations](https://blog.rust-lang.org/2024/09/05/Rust-1.81.0.html#new-sort-implementations).

## Reproduction steps

I wrote a small program that demonstrates the issue

```rust
use minijinja::Value;

fn main() {
    let a = Value::from(i64::MAX as i128);
    let b = Value::from(i64::MAX as f64);
    let c = Value::from(i64::MAX as i128 + 1);

    assert_eq!(a, b, "Equal because they are the same value");
    assert_eq!(b, c, "Equal because the float approximations are equal");
    assert_ne!(a, c, "Not equal because they are different values");
}
```

Additional helpful information:

- Version of minijinja: 2.2.0
- Version of rustc: 1.81.0
- Operating system and version: Ubuntu 22.04

Though none of the above should matter, I think this bug applies to all versions.

## What did you expect

Equality and comparison operators should maintain their transitive properties. This is a hard problem with many corner cases. It would involve checking:

- if the float is an integer, otherwise the comparison should be false
- if the float is within the relevant integer range, otherwise the comparison should be false
- and then the comparison should happen in integers, not floats

This is much more complicated than the existing solution, so it's understandable you went this route, but it does have the issue described above.

Also the above fix only works for `(Partial)Eq`, fixing `Ord` is much more complicated.

Pull request description:
Changed Ord to have a more consistent order
This changes the order of `Ord` to order strictly by value type first.  This now means that things order primarily by `ValueType` and secondarily by what the value type looks like.

This changes the order from earlier versions but addresses potential panics caused by the new sort function.

Fixes #577 

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index d346243..32e5d07 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,12 +2,9 @@
 
 All notable changes to MiniJinja are documented here.
 
-## 2.3.1
-
-- Fixes some compiler warnings in Rust 1.81.  #575
-
 ## 2.3.0
 
+- Fixes some compiler warnings in Rust 1.81.  #575
 - Fixes incorrect ordering of maps when the keys of those maps
   were not in consistent order.  #569
 - Implemented the missing `groupby` filter.  #570
@@ -15,6 +12,8 @@ All notable changes to MiniJinja are documented here.
   Jinja2 and supports an optional flag to make it case sensitive.
   It also now lets one check individual attributes instead of
   values.  #571
+- Changed sort order of `Ord` to avoid accidentally non total order
+  that could cause panics on Rust 1.81.  #579
 
 ## 2.2.0
 
diff --git a/minijinja/src/value/mod.rs b/minijinja/src/value/mod.rs
index ce361b5..4fdac44 100644
--- a/minijinja/src/value/mod.rs
+++ b/minijinja/src/value/mod.rs
@@ -540,7 +540,11 @@ fn f64_total_cmp(left: f64, right: f64) -> Ordering {
 
 impl Ord for Value {
     fn cmp(&self, other: &Self) -> Ordering {
-        let value_ordering = match (&self.0, &other.0) {
+        let kind_ordering = self.kind().cmp(&other.kind());
+        if matches!(kind_ordering, Ordering::Less | Ordering::Greater) {
+            return kind_ordering;
+        }
+        match (&self.0, &other.0) {
             (ValueRepr::None, ValueRepr::None) => Ordering::Equal,
             (ValueRepr::Undefined, ValueRepr::Undefined) => Ordering::Equal,
             (ValueRepr::String(ref a, _), ValueRepr::String(ref b, _)) => a.cmp(b),
@@ -550,34 +554,38 @@ impl Ord for Value {
                 Some(ops::CoerceResult::F64(a, b)) => f64_total_cmp(a, b),
                 Some(ops::CoerceResult::I128(a, b)) => a.cmp(&b),
                 Some(ops::CoerceResult::Str(a, b)) => a.cmp(b),
-                None => match (self.kind(), other.kind()) {
-                    (ValueKind::Seq, ValueKind::Seq) => match (self.try_iter(), other.try_iter()) {
-                        (Ok(a), Ok(b)) => a.cmp(b),
-                        _ => self.len().cmp(&other.len()),
-                    },
-                    (ValueKind::Map, ValueKind::Map) => {
-                        if let (Some(a), Some(b)) = (self.as_object(), other.as_object()) {
-                            if a.is_same_object(b) {
-                                Ordering::Equal
-                            } else {
-                                // This is not really correct.  Because the keys can be in arbitrary
-                                // order this could just sort really weirdly as a result.  However
-                                // we don't want to pay the cost of actually sorting the keys for
-                                // ordering so we just accept this for now.
-                                match (a.try_iter_pairs(), b.try_iter_pairs()) {
-                                    (Some(a), Some(b)) => a.cmp(b),
-                                    _ => self.len().cmp(&other.len()),
+                None => {
+                    if let (Some(a), Some(b)) = (self.as_object(), other.as_object()) {
+                        if a.is_same_object(b) {
+                            Ordering::Equal
+                        } else {
+                            match (a.repr(), b.repr()) {
+                                (ObjectRepr::Map, ObjectRepr::Map) => {
+                                    // This is not really correct.  Because the keys can be in arbitrary
+                                    // order this could just sort really weirdly as a result.  However
+                                    // we don't want to pay the cost of actually sorting the keys for
+                                    // ordering so we just accept this for now.
+                                    match (a.try_iter_pairs(), b.try_iter_pairs()) {
+                                        (Some(a), Some(b)) => a.cmp(b),
+                                        _ => unreachable!(),
+                                    }
                                 }
+                                (
+                                    ObjectRepr::Seq | ObjectRepr::Iterable,
+                                    ObjectRepr::Seq | ObjectRepr::Iterable,
+                                ) => match (a.try_iter(), b.try_iter()) {
+                                    (Some(a), Some(b)) => a.cmp(b),
+                                    _ => unreachable!(),
+                                },
+                                (_, _) => unreachable!(),
                             }
-                        } else {
-                            unreachable!();
                         }
+                    } else {
+                        unreachable!()
                     }
-                    _ => Ordering::Equal,
-                },
+                }
             },
-        };
-        value_ordering.then((self.kind() as usize).cmp(&(other.kind() as usize)))
+        }
     }
 }
 


Test patch:
diff --git a/minijinja/tests/snapshots/test_templates__vm@coerce.txt.snap b/minijinja/tests/snapshots/test_templates__vm@coerce.txt.snap
index e6a3fb2..42f124a 100644
--- a/minijinja/tests/snapshots/test_templates__vm@coerce.txt.snap
+++ b/minijinja/tests/snapshots/test_templates__vm@coerce.txt.snap
@@ -2,6 +2,7 @@
 source: minijinja/tests/test_templates.rs
 description: "{{ \"World\"[0] == \"W\" }}\n{{ \"W\" == \"W\" }}\n{{ 1.0 == 1 }}\n{{ 1 != 2 }}\n{{ none == none }}\n{{ none != undefined }}\n{{ undefined == undefined }}\n{{ true == true }}\n{{ 1 == true }}\n{{ 0 == false }}\n{{ 1 != 0 }}\n{{ \"a\" < \"b\" }}\n{{ \"a\"[0] < \"b\" }}\n{{ false < true }}\n{{ 0 < true }}\n{{ [0, 0] == [0, 0] }}\n{{ [\"a\"] == [\"a\"[0]] }}"
 info: {}
+input_file: minijinja/tests/inputs/coerce.txt
 ---
 true
 true
@@ -17,7 +18,6 @@ true
 true
 true
 true
+false
 true
 true
-true
-
diff --git a/minijinja/tests/snapshots/test_templates__vm@filters.txt.snap b/minijinja/tests/snapshots/test_templates__vm@filters.txt.snap
index 14a6166..e29d1c6 100644
--- a/minijinja/tests/snapshots/test_templates__vm@filters.txt.snap
+++ b/minijinja/tests/snapshots/test_templates__vm@filters.txt.snap
@@ -70,8 +70,8 @@ sort: [1, 2, 4, 9, 111]
 sort-reverse: [111, 9, 4, 2, 1]
 sort-case-insensitive: ["a", "B", "C", "z"]
 sort-case-sensitive: ["B", "C", "a", "z"]
-sort-case-insensitive-mixed: [false, 0, true, 1, "false", "False", "true", "True"]
-sort-case-sensitive-mixed: [false, 0, true, 1, "False", "True", "false", "true"]
+sort-case-insensitive-mixed: [false, true, 0, 1, "false", "False", "true", "True"]
+sort-case-sensitive-mixed: [false, true, 0, 1, "False", "True", "false", "true"]
 sort-attribute [{"name": "a"}, {"name": "b"}]
 d: true
 json: {"a":"b","c":"d"}
diff --git a/minijinja/tests/test_value.rs b/minijinja/tests/test_value.rs
index df36f69..e97d016 100644
--- a/minijinja/tests/test_value.rs
+++ b/minijinja/tests/test_value.rs
@@ -1,11 +1,11 @@
 use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, LinkedList, VecDeque};
 use std::sync::Arc;
 
-use insta::assert_snapshot;
+use insta::{assert_debug_snapshot, assert_snapshot};
 use similar_asserts::assert_eq;
 
 use minijinja::value::{DynObject, Enumerator, Kwargs, Object, ObjectRepr, Rest, Value};
-use minijinja::{args, render, Environment, Error};
+use minijinja::{args, render, Environment, Error, ErrorKind};
 
 #[test]
 fn test_sort() {
@@ -69,13 +69,13 @@ fn test_sort_different_types() {
     [
         undefined,
         none,
+        false,
+        true,
         -inf,
         -100,
         -75.0,
         -50.0,
-        false,
         0,
-        true,
         1,
         30,
         80,
@@ -1059,3 +1059,69 @@ fn test_float_eq() {
     let xb = Value::from(i64::MAX as f64);
     assert_ne!(xa, xb);
 }
+
+#[test]
+fn test_sorting() {
+    let mut values = vec![
+        Value::from(-f64::INFINITY),
+        Value::from(1.0),
+        Value::from(f64::NAN),
+        Value::from(f64::INFINITY),
+        Value::from(42.0),
+        Value::from(41),
+        Value::from(128),
+        Value::from(-2),
+        Value::from(-5.0),
+        Value::from(32i32),
+        Value::from(true),
+        Value::from(false),
+        Value::from(vec![1, 2, 3]),
+        Value::from(vec![1, 2, 3, 4]),
+        Value::from(vec![1]),
+        Value::from("whatever"),
+        Value::from("floats"),
+        Value::from("the"),
+        Value::from("boat"),
+        Value::UNDEFINED,
+        Value::from(()),
+        Value::from(Error::new(ErrorKind::InvalidOperation, "shit hit the fan")),
+    ];
+    values.sort();
+    assert_debug_snapshot!(&values, @r###"
+    [
+        undefined,
+        none,
+        false,
+        true,
+        -inf,
+        -5.0,
+        -2,
+        1.0,
+        32,
+        41,
+        42.0,
+        128,
+        inf,
+        NaN,
+        "boat",
+        "floats",
+        "the",
+        "whatever",
+        [
+            1,
+        ],
+        [
+            1,
+            2,
+            3,
+        ],
+        [
+            1,
+            2,
+            3,
+            4,
+        ],
+        <invalid value: invalid operation: shit hit the fan>,
+    ]
+    "###);
+}