Repository: mitsuhiko/minijinja (rust)

Issue:
`Value::PartialEq` not comparing iterators correctly
Thank you for implementing jinja template rendering in Rust!

I noticed that the `PartialEq` trait for `Value` doesn't handle iterators correctly. I am specifically interested in comparing `Value`s of `HashMap`s. `PartialEq` iterates over two iterators item-by-item and compares whether two consumed items are equal. However, in the case of `HashMap` for example, the order is arbitrary. So, comparing two Values with HashMaps in it currently doesn't work.

https://github.com/mitsuhiko/minijinja/blob/42ea1a12ecc78d74d6005307542ba0482205e478/minijinja/src/value/mod.rs#L493-L495

The following piece of code I would expect to succeed, but it is flaky, it fails sometimes but also succeeds sometimes:

```rust
use std::collections::HashMap;

use minijinja::Value;

assert_eq!(
    Value::from(
        [("key1", "value1"), ("key2", "value2")]
            .iter()
            .cloned()
            .collect::<HashMap<&str, &str>>()
    ),
    Value::from(
        [("key1", "value1"), ("key2", "value2")]
            .iter()
            .cloned()
            .collect::<HashMap<&str, &str>>()
    ),
);
```

Is this intentional? If not, could we maybe, in the case of `HashMap`, use the [standard `PartialEq` implementation](https://doc.rust-lang.org/src/std/collections/hash/map.rs.html#1281-1287) of `HashMap`?

Pull request description:
Fix the implementation of PartialEq for maps
This fixes the implementation of `PartialEq` for `Value`s containing maps and it slightly improves `Ord`.  `Ord` is not really fixed as the order of keys just does stupid stuff to the ordering.  I'm going to accept this for now because you're most likely not going to sort maps all that often.

Fixes #568

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index be2316d..19979d0 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,6 +2,11 @@
 
 All notable changes to MiniJinja are documented here.
 
+## 2.2.1
+
+- Fixes incorrect ordering of maps when the keys of those maps
+  were not in consistent order.  #569
+
 ## 2.2.0
 
 - Fixes a bug where some enums did not deserialize correctly when
diff --git a/minijinja/src/value/mod.rs b/minijinja/src/value/mod.rs
index 08fc24d..719e22d 100644
--- a/minijinja/src/value/mod.rs
+++ b/minijinja/src/value/mod.rs
@@ -488,14 +488,29 @@ impl PartialEq for Value {
                 Some(ops::CoerceResult::Str(a, b)) => a == b,
                 None => {
                     if let (Some(a), Some(b)) = (self.as_object(), other.as_object()) {
-                        if a.repr() != b.repr() {
-                            false
-                        } else if let (Some(ak), Some(bk)) =
-                            (a.try_iter_pairs(), b.try_iter_pairs())
-                        {
-                            ak.eq(bk)
-                        } else {
-                            false
+                        if a.is_same_object(b) {
+                            return true;
+                        }
+                        match (a.repr(), b.repr()) {
+                            (ObjectRepr::Map, ObjectRepr::Map) => {
+                                if a.enumerator_len() != b.enumerator_len() {
+                                    return false;
+                                }
+                                a.try_iter_pairs().map_or(false, |mut ak| {
+                                    ak.all(|(k, v1)| b.get_value(&k).map_or(false, |v2| v1 == v2))
+                                })
+                            }
+                            (
+                                ObjectRepr::Seq | ObjectRepr::Iterable,
+                                ObjectRepr::Seq | ObjectRepr::Iterable,
+                            ) => {
+                                if let (Some(ak), Some(bk)) = (a.try_iter(), b.try_iter()) {
+                                    ak.eq(bk)
+                                } else {
+                                    false
+                                }
+                            }
+                            _ => false,
                         }
                     } else {
                         false
@@ -540,13 +555,24 @@ impl Ord for Value {
                         (Ok(a), Ok(b)) => a.cmp(b),
                         _ => self.len().cmp(&other.len()),
                     },
-                    (ValueKind::Map, ValueKind::Map) => match (
-                        self.as_object().and_then(|x| x.try_iter_pairs()),
-                        other.as_object().and_then(|x| x.try_iter_pairs()),
-                    ) {
-                        (Some(a), Some(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()),
+                                }
+                            }
+                        } else {
+                            unreachable!();
+                        }
+                    }
                     _ => Ordering::Equal,
                 },
             },
diff --git a/minijinja/src/value/object.rs b/minijinja/src/value/object.rs
index a63feaf..662a20c 100644
--- a/minijinja/src/value/object.rs
+++ b/minijinja/src/value/object.rs
@@ -646,6 +646,11 @@ unsafe impl Sync for DynObject {}
 
 impl DynObject {
     impl_object_helpers!(pub &Self);
+
+    /// Checks if this dyn object is the same as another.
+    pub(crate) fn is_same_object(&self, other: &DynObject) -> bool {
+        self.ptr == other.ptr && self.vtable == other.vtable
+    }
 }
 
 impl Hash for DynObject {
@@ -758,6 +763,10 @@ macro_rules! impl_str_map_helper {
                     Box::new(this.keys().map(|k| intern(k.as_ref())).map(Value::from))
                 })
             }
+
+            fn enumerator_len(self: &Arc<Self>) -> Option<usize> {
+                Some(self.len())
+            }
         }
     };
 }
@@ -834,6 +843,10 @@ macro_rules! impl_value_map {
             fn enumerate(self: &Arc<Self>) -> Enumerator {
                 self.$enumerator(|this| Box::new(this.keys().cloned()))
             }
+
+            fn enumerator_len(self: &Arc<Self>) -> Option<usize> {
+                Some(self.len())
+            }
         }
 
         impl<V> From<$map_type<Value, V>> for Value


Test patch:
diff --git a/minijinja/tests/test_value.rs b/minijinja/tests/test_value.rs
index ad432bf..e02bbfb 100644
--- a/minijinja/tests/test_value.rs
+++ b/minijinja/tests/test_value.rs
@@ -1016,3 +1016,36 @@ fn test_downcast_arg() {
         "A|B"
     );
 }
+
+#[test]
+fn test_map_eq() {
+    #[derive(Debug, Copy, Clone)]
+    struct Thing {
+        rev: bool,
+    }
+
+    impl Object for Thing {
+        fn get_value(self: &Arc<Self>, key: &Value) -> Option<Value> {
+            match key.as_str()? {
+                "a" => Some(Value::from(1)),
+                "b" => Some(Value::from(2)),
+                _ => None,
+            }
+        }
+
+        fn enumerate(self: &Arc<Self>) -> Enumerator {
+            if self.rev {
+                Enumerator::Str(&["b", "a"])
+            } else {
+                Enumerator::Str(&["a", "b"])
+            }
+        }
+    }
+
+    let t1 = Value::from_object(Thing { rev: false });
+    let t2 = Value::from_object(Thing { rev: true });
+
+    assert_snapshot!(t1.to_string(), @r###"{"a": 1, "b": 2}"###);
+    assert_snapshot!(t2.to_string(), @r###"{"b": 2, "a": 1}"###);
+    assert_eq!(t1, t2);
+}