Repository: mitsuhiko/minijinja (language: 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.


Discussion / hints:
Unfortunately the strictness in the new sort behavior is very annoying to deal with for types like Jinja's `Value` type.  I don't think the current implementation of `Ord` can cause a panic with the new sort algorithm but I'm not 100% sure.

The code internally undergoes a coercion step that is lossy if one side is a float.  That one is obviously incorrect but I'm not sure yet what the right fix is.
Refs https://github.com/rust-lang/rust/issues/129561
That BTW is incorrect: `Value::from(i64::MAX as f64)`. The largest value that can be represented as a float is `2^53`.
> That BTW is incorrect: `Value::from(i64::MAX as f64)`. The largest value that can be represented as a float is `2^53`.

You are right, though my intent was not to showcase the first value where this goes wrong, just "a" value where this goes wrong. `i64::MAX` was a convenient constant for that.

Fix patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index d3462437..32e5d07e 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 ce361b5c..4fdac445 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 e6a3fb22..42f124a0 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 14a61668..e29d1c66 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 df36f695..e97d0166 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>,
+    ]
+    "###);
+}