Repository: toml-rs/toml (language: rust)

Issue:
`easy::Value` equality doesn't handle keys being in other orders
Noticed this when porting `toml-rs` tests.  `linked_hash_map` requires two maps to have keys in the same order to be equal.

Options
- `easy::Map` could have its own equality
- We can switch to `indexmap`, which is what `toml-rs` uses
  - It loses ordering on `remove` *but* I suspect that is less of a problem with us tracking table positions.   We don't track inline table positions (#163).


Discussion / hints:
> It loses ordering on remove but I suspect that is less of a problem with us tracking table positions. We don't track inline table positions

If we only delete by replacing the value with `Item::None`, then it's even less of a problem. I was considering replacing `linked_hash_map` with `indexmap` as well esp. considering it's only in maintenance mode: https://github.com/contain-rs/linked-hash-map. I think we should do it.
Good idea with the tombstones!

EDIT: Looks like they aren't needed, there is `shift_remove` that preserves order

Fix patch:
diff --git a/Cargo.toml b/Cargo.toml
index f6ef2d58..7cf2b95c 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -19,7 +19,7 @@ default = []
 easy = ["serde"]
 
 [dependencies]
-linked-hash-map = "0.5.2"
+indexmap = "1.7"
 combine = "4.5.2"
 vec1 = "1"
 itertools = "0.10"
diff --git a/src/easy/de/inline_table.rs b/src/easy/de/inline_table.rs
index a421bf8e..9e65d96c 100644
--- a/src/easy/de/inline_table.rs
+++ b/src/easy/de/inline_table.rs
@@ -3,7 +3,7 @@ use serde::de::IntoDeserializer;
 use crate::easy::de::Error;
 
 pub(crate) struct InlineTableMapAccess {
-    iter: linked_hash_map::IntoIter<crate::repr::InternalString, crate::table::TableKeyValue>,
+    iter: indexmap::map::IntoIter<crate::repr::InternalString, crate::table::TableKeyValue>,
     value: Option<crate::Item>,
 }
 
diff --git a/src/easy/de/table.rs b/src/easy/de/table.rs
index 30021dee..0edfb4c5 100644
--- a/src/easy/de/table.rs
+++ b/src/easy/de/table.rs
@@ -3,7 +3,7 @@ use serde::de::IntoDeserializer;
 use crate::easy::de::Error;
 
 pub(crate) struct TableMapAccess {
-    iter: linked_hash_map::IntoIter<crate::repr::InternalString, crate::table::TableKeyValue>,
+    iter: indexmap::map::IntoIter<crate::repr::InternalString, crate::table::TableKeyValue>,
     value: Option<crate::Item>,
 }
 
diff --git a/src/easy/map.rs b/src/easy/map.rs
index ab98fff7..3d18f1bb 100644
--- a/src/easy/map.rs
+++ b/src/easy/map.rs
@@ -14,7 +14,7 @@ use std::hash::Hash;
 use std::iter::FromIterator;
 use std::ops;
 
-use linked_hash_map::{self, LinkedHashMap};
+use indexmap::map::IndexMap;
 use serde::{de, ser};
 
 use crate::easy::value::Value;
@@ -24,7 +24,7 @@ pub struct Map<K, V> {
     map: MapImpl<K, V>,
 }
 
-type MapImpl<K, V> = LinkedHashMap<K, V>;
+type MapImpl<K, V> = IndexMap<K, V>;
 
 impl Map<String, Value> {
     /// Makes a new empty Map.
@@ -39,7 +39,7 @@ impl Map<String, Value> {
     #[inline]
     pub fn with_capacity(capacity: usize) -> Self {
         Map {
-            map: LinkedHashMap::with_capacity(capacity),
+            map: IndexMap::with_capacity(capacity),
         }
     }
 
@@ -120,7 +120,7 @@ impl Map<String, Value> {
     where
         S: Into<String>,
     {
-        use linked_hash_map::Entry as EntryImpl;
+        use indexmap::map::Entry as EntryImpl;
 
         match self.map.entry(key.into()) {
             EntryImpl::Vacant(vacant) => Entry::Vacant(VacantEntry { vacant }),
@@ -367,9 +367,9 @@ pub struct OccupiedEntry<'a> {
     occupied: OccupiedEntryImpl<'a>,
 }
 
-type VacantEntryImpl<'a> = linked_hash_map::VacantEntry<'a, String, Value>;
+type VacantEntryImpl<'a> = indexmap::map::VacantEntry<'a, String, Value>;
 
-type OccupiedEntryImpl<'a> = linked_hash_map::OccupiedEntry<'a, String, Value>;
+type OccupiedEntryImpl<'a> = indexmap::map::OccupiedEntry<'a, String, Value>;
 
 impl<'a> Entry<'a> {
     /// Returns a reference to this entry's key.
@@ -476,7 +476,7 @@ pub struct Iter<'a> {
     iter: IterImpl<'a>,
 }
 
-type IterImpl<'a> = linked_hash_map::Iter<'a, String, Value>;
+type IterImpl<'a> = indexmap::map::Iter<'a, String, Value>;
 
 delegate_iterator!((Iter<'a>) => (&'a String, &'a Value));
 
@@ -498,7 +498,7 @@ pub struct IterMut<'a> {
     iter: IterMutImpl<'a>,
 }
 
-type IterMutImpl<'a> = linked_hash_map::IterMut<'a, String, Value>;
+type IterMutImpl<'a> = indexmap::map::IterMut<'a, String, Value>;
 
 delegate_iterator!((IterMut<'a>) => (&'a String, &'a mut Value));
 
@@ -520,7 +520,7 @@ pub struct IntoIter {
     iter: IntoIterImpl,
 }
 
-type IntoIterImpl = linked_hash_map::IntoIter<String, Value>;
+type IntoIterImpl = indexmap::map::IntoIter<String, Value>;
 
 delegate_iterator!((IntoIter) => (String, Value));
 
@@ -531,7 +531,7 @@ pub struct Keys<'a> {
     iter: KeysImpl<'a>,
 }
 
-type KeysImpl<'a> = linked_hash_map::Keys<'a, String, Value>;
+type KeysImpl<'a> = indexmap::map::Keys<'a, String, Value>;
 
 delegate_iterator!((Keys<'a>) => &'a String);
 
@@ -542,6 +542,6 @@ pub struct Values<'a> {
     iter: ValuesImpl<'a>,
 }
 
-type ValuesImpl<'a> = linked_hash_map::Values<'a, String, Value>;
+type ValuesImpl<'a> = indexmap::map::Values<'a, String, Value>;
 
 delegate_iterator!((Values<'a>) => &'a Value);
diff --git a/src/inline_table.rs b/src/inline_table.rs
index 06625c4e..fd2355b4 100644
--- a/src/inline_table.rs
+++ b/src/inline_table.rs
@@ -76,22 +76,15 @@ impl InlineTable {
 
     /// Sorts the key/value pairs by key.
     pub fn sort_values(&mut self) {
-        let mut keys: Vec<InternalString> = self
-            .items
-            .iter_mut()
-            .filter_map(|(key, kv)| match &mut kv.value {
+        // Assuming standard tables have their position set and this won't negatively impact them
+        self.items.sort_keys();
+        for kv in self.items.values_mut() {
+            match &mut kv.value {
                 Item::Value(Value::InlineTable(table)) if table.is_dotted() => {
                     table.sort_values();
-                    Some(key)
                 }
-                Item::Value(_) => Some(key),
-                _ => None,
-            })
-            .cloned()
-            .collect();
-        keys.sort();
-        for key in keys {
-            self.items.get_refresh(&key);
+                _ => {}
+            }
         }
     }
 
@@ -166,7 +159,7 @@ impl InlineTable {
     pub fn entry<'a>(&'a mut self, key: &str) -> InlineEntry<'a> {
         // Accept a `&str` rather than an owned type to keep `InternalString`, well, internal
         match self.items.entry(key.to_owned()) {
-            linked_hash_map::Entry::Occupied(mut entry) => {
+            indexmap::map::Entry::Occupied(mut entry) => {
                 // Ensure it is a `Value` to simplify `InlineOccupiedEntry`'s code.
                 let mut scratch = Item::None;
                 std::mem::swap(&mut scratch, &mut entry.get_mut().value);
@@ -181,7 +174,7 @@ impl InlineTable {
 
                 InlineEntry::Occupied(InlineOccupiedEntry { entry })
             }
-            linked_hash_map::Entry::Vacant(entry) => {
+            indexmap::map::Entry::Vacant(entry) => {
                 InlineEntry::Vacant(InlineVacantEntry { entry, key: None })
             }
         }
@@ -191,7 +184,7 @@ impl InlineTable {
     pub fn entry_format<'a>(&'a mut self, key: &'a Key) -> InlineEntry<'a> {
         // Accept a `&Key` to be consistent with `entry`
         match self.items.entry(key.get().to_owned()) {
-            linked_hash_map::Entry::Occupied(mut entry) => {
+            indexmap::map::Entry::Occupied(mut entry) => {
                 // Ensure it is a `Value` to simplify `InlineOccupiedEntry`'s code.
                 let mut scratch = Item::None;
                 std::mem::swap(&mut scratch, &mut entry.get_mut().value);
@@ -206,7 +199,7 @@ impl InlineTable {
 
                 InlineEntry::Occupied(InlineOccupiedEntry { entry })
             }
-            linked_hash_map::Entry::Vacant(entry) => InlineEntry::Vacant(InlineVacantEntry {
+            indexmap::map::Entry::Vacant(entry) => InlineEntry::Vacant(InlineVacantEntry {
                 entry,
                 key: Some(key),
             }),
@@ -263,13 +256,13 @@ impl InlineTable {
     /// Removes an item given the key.
     pub fn remove(&mut self, key: &str) -> Option<Value> {
         self.items
-            .remove(key)
+            .shift_remove(key)
             .and_then(|kv| kv.value.into_value().ok())
     }
 
     /// Removes a key from the map, returning the stored key and value if the key was previously in the map.
     pub fn remove_entry(&mut self, key: &str) -> Option<(Key, Value)> {
-        self.items.remove(key).and_then(|kv| {
+        self.items.shift_remove(key).and_then(|kv| {
             let key = kv.key;
             kv.value.into_value().ok().map(|value| (key, value))
         })
@@ -426,9 +419,9 @@ impl<'a> InlineEntry<'a> {
     }
 }
 
-/// A view into a single occupied location in a `LinkedHashMap`.
+/// A view into a single occupied location in a `IndexMap`.
 pub struct InlineOccupiedEntry<'a> {
-    entry: linked_hash_map::OccupiedEntry<'a, InternalString, TableKeyValue>,
+    entry: indexmap::map::OccupiedEntry<'a, InternalString, TableKeyValue>,
 }
 
 impl<'a> InlineOccupiedEntry<'a> {
@@ -472,13 +465,13 @@ impl<'a> InlineOccupiedEntry<'a> {
 
     /// Takes the value out of the entry, and returns it
     pub fn remove(self) -> Value {
-        self.entry.remove().value.into_value().unwrap()
+        self.entry.shift_remove().value.into_value().unwrap()
     }
 }
 
-/// A view into a single empty location in a `LinkedHashMap`.
+/// A view into a single empty location in a `IndexMap`.
 pub struct InlineVacantEntry<'a> {
-    entry: linked_hash_map::VacantEntry<'a, InternalString, TableKeyValue>,
+    entry: indexmap::map::VacantEntry<'a, InternalString, TableKeyValue>,
     key: Option<&'a Key>,
 }
 
diff --git a/src/table.rs b/src/table.rs
index 54f2b9d3..be2db9f4 100644
--- a/src/table.rs
+++ b/src/table.rs
@@ -1,6 +1,6 @@
 use std::iter::FromIterator;
 
-use linked_hash_map::LinkedHashMap;
+use indexmap::map::IndexMap;
 
 use crate::key::Key;
 use crate::repr::{Decor, InternalString};
@@ -104,22 +104,15 @@ impl Table {
     ///
     /// Doesn't affect subtables or subarrays.
     pub fn sort_values(&mut self) {
-        let mut keys: Vec<InternalString> = self
-            .items
-            .iter_mut()
-            .filter_map(|(key, kv)| match &mut kv.value {
+        // Assuming standard tables have their position set and this won't negatively impact them
+        self.items.sort_keys();
+        for kv in self.items.values_mut() {
+            match &mut kv.value {
                 Item::Table(table) if table.is_dotted() => {
                     table.sort_values();
-                    Some(key)
                 }
-                Item::Value(_) => Some(key),
-                _ => None,
-            })
-            .cloned()
-            .collect();
-        keys.sort();
-        for key in keys {
-            self.items.get_refresh(&key);
+                _ => {}
+            }
         }
     }
 
@@ -230,10 +223,8 @@ impl Table {
     pub fn entry<'a>(&'a mut self, key: &str) -> Entry<'a> {
         // Accept a `&str` rather than an owned type to keep `InternalString`, well, internal
         match self.items.entry(key.to_owned()) {
-            linked_hash_map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { entry }),
-            linked_hash_map::Entry::Vacant(entry) => {
-                Entry::Vacant(VacantEntry { entry, key: None })
-            }
+            indexmap::map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { entry }),
+            indexmap::map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry { entry, key: None }),
         }
     }
 
@@ -241,8 +232,8 @@ impl Table {
     pub fn entry_format<'a>(&'a mut self, key: &'a Key) -> Entry<'a> {
         // Accept a `&Key` to be consistent with `entry`
         match self.items.entry(key.get().to_owned()) {
-            linked_hash_map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { entry }),
-            linked_hash_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
+            indexmap::map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { entry }),
+            indexmap::map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
                 entry,
                 key: Some(key),
             }),
@@ -311,12 +302,12 @@ impl Table {
 
     /// Removes an item given the key.
     pub fn remove(&mut self, key: &str) -> Option<Item> {
-        self.items.remove(key).map(|kv| kv.value)
+        self.items.shift_remove(key).map(|kv| kv.value)
     }
 
     /// Removes a key from the map, returning the stored key and value if the key was previously in the map.
     pub fn remove_entry(&mut self, key: &str) -> Option<(Key, Item)> {
-        self.items.remove(key).map(|kv| (kv.key, kv.value))
+        self.items.shift_remove(key).map(|kv| (kv.key, kv.value))
     }
 }
 
@@ -360,7 +351,7 @@ impl<'s> IntoIterator for &'s Table {
     }
 }
 
-pub(crate) type KeyValuePairs = LinkedHashMap<InternalString, TableKeyValue>;
+pub(crate) type KeyValuePairs = IndexMap<InternalString, TableKeyValue>;
 
 fn decorate_table(table: &mut Table) {
     for (key_decor, value) in table
@@ -508,9 +499,9 @@ impl<'a> Entry<'a> {
     }
 }
 
-/// A view into a single occupied location in a `LinkedHashMap`.
+/// A view into a single occupied location in a `IndexMap`.
 pub struct OccupiedEntry<'a> {
-    entry: linked_hash_map::OccupiedEntry<'a, InternalString, TableKeyValue>,
+    entry: indexmap::map::OccupiedEntry<'a, InternalString, TableKeyValue>,
 }
 
 impl<'a> OccupiedEntry<'a> {
@@ -553,13 +544,13 @@ impl<'a> OccupiedEntry<'a> {
 
     /// Takes the value out of the entry, and returns it
     pub fn remove(self) -> Item {
-        self.entry.remove().value
+        self.entry.shift_remove().value
     }
 }
 
-/// A view into a single empty location in a `LinkedHashMap`.
+/// A view into a single empty location in a `IndexMap`.
 pub struct VacantEntry<'a> {
-    entry: linked_hash_map::VacantEntry<'a, InternalString, TableKeyValue>,
+    entry: indexmap::map::VacantEntry<'a, InternalString, TableKeyValue>,
     key: Option<&'a Key>,
 }
 


Test patch:
diff --git a/tests/serde.rs b/tests/serde.rs
index 6b1cbb71..decbd732 100644
--- a/tests/serde.rs
+++ b/tests/serde.rs
@@ -1,7 +1,7 @@
 #![cfg(feature = "easy")]
 
 use serde::{Deserialize, Serialize};
-use std::collections::{BTreeMap, HashSet};
+use std::collections::BTreeMap;
 
 use toml_edit::easy::map::Map;
 use toml_edit::easy::Value;
@@ -176,39 +176,6 @@ fn inner_structs_with_options() {
     }
 }
 
-#[test]
-#[should_panic] // Our equality is broken, see https://github.com/ordian/toml_edit/issues/194
-fn hashmap() {
-    #[derive(Serialize, Deserialize, PartialEq, Debug, Clone)]
-    struct Foo {
-        set: HashSet<char>,
-        map: BTreeMap<String, isize>,
-    }
-
-    equivalent! {
-        Foo {
-            map: {
-                let mut m = BTreeMap::new();
-                m.insert("foo".to_string(), 10);
-                m.insert("bar".to_string(), 4);
-                m
-            },
-            set: {
-                let mut s = HashSet::new();
-                s.insert('a');
-                s
-            },
-        },
-        Table(map! {
-            map: Table(map! {
-                foo: Integer(10),
-                bar: Integer(4)
-            }),
-            set: Array(vec![Value::String("a".to_string())])
-        }),
-    }
-}
-
 #[test]
 fn table_array() {
     #[derive(Serialize, Deserialize, PartialEq, Debug, Clone)]
@@ -335,131 +302,6 @@ fn parse_enum_string() {
     }
 }
 
-// #[test]
-// fn unused_fields() {
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Foo { a: isize }
-//
-//     let v = Foo { a: 2 };
-//     let mut d = Decoder::new(Table(map! {
-//         a, Integer(2),
-//         b, Integer(5)
-//     }));
-//     assert_eq!(v, t!(Deserialize::deserialize(&mut d)));
-//
-//     assert_eq!(d.toml, Some(Table(map! {
-//         b, Integer(5)
-//     })));
-// }
-//
-// #[test]
-// fn unused_fields2() {
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Foo { a: Bar }
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Bar { a: isize }
-//
-//     let v = Foo { a: Bar { a: 2 } };
-//     let mut d = Decoder::new(Table(map! {
-//         a, Table(map! {
-//             a, Integer(2),
-//             b, Integer(5)
-//         })
-//     }));
-//     assert_eq!(v, t!(Deserialize::deserialize(&mut d)));
-//
-//     assert_eq!(d.toml, Some(Table(map! {
-//         a, Table(map! {
-//             b, Integer(5)
-//         })
-//     })));
-// }
-//
-// #[test]
-// fn unused_fields3() {
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Foo { a: Bar }
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Bar { a: isize }
-//
-//     let v = Foo { a: Bar { a: 2 } };
-//     let mut d = Decoder::new(Table(map! {
-//         a, Table(map! {
-//             a, Integer(2)
-//         })
-//     }));
-//     assert_eq!(v, t!(Deserialize::deserialize(&mut d)));
-//
-//     assert_eq!(d.toml, None);
-// }
-//
-// #[test]
-// fn unused_fields4() {
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Foo { a: BTreeMap<String, String> }
-//
-//     let v = Foo { a: map! { a, "foo".to_string() } };
-//     let mut d = Decoder::new(Table(map! {
-//         a, Table(map! {
-//             a, Value::String("foo".to_string())
-//         })
-//     }));
-//     assert_eq!(v, t!(Deserialize::deserialize(&mut d)));
-//
-//     assert_eq!(d.toml, None);
-// }
-//
-// #[test]
-// fn unused_fields5() {
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Foo { a: Vec<String> }
-//
-//     let v = Foo { a: vec!["a".to_string()] };
-//     let mut d = Decoder::new(Table(map! {
-//         a, Array(vec![Value::String("a".to_string())])
-//     }));
-//     assert_eq!(v, t!(Deserialize::deserialize(&mut d)));
-//
-//     assert_eq!(d.toml, None);
-// }
-//
-// #[test]
-// fn unused_fields6() {
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Foo { a: Option<Vec<String>> }
-//
-//     let v = Foo { a: Some(vec![]) };
-//     let mut d = Decoder::new(Table(map! {
-//         a, Array(vec![])
-//     }));
-//     assert_eq!(v, t!(Deserialize::deserialize(&mut d)));
-//
-//     assert_eq!(d.toml, None);
-// }
-//
-// #[test]
-// fn unused_fields7() {
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Foo { a: Vec<Bar> }
-//     #[derive(Serialize, Deserialize, PartialEq, Debug)]
-//     struct Bar { a: isize }
-//
-//     let v = Foo { a: vec![Bar { a: 1 }] };
-//     let mut d = Decoder::new(Table(map! {
-//         a, Array(vec![Table(map! {
-//             a, Integer(1),
-//             b, Integer(2)
-//         })])
-//     }));
-//     assert_eq!(v, t!(Deserialize::deserialize(&mut d)));
-//
-//     assert_eq!(d.toml, Some(Table(map! {
-//         a, Array(vec![Table(map! {
-//             b, Integer(2)
-//         })])
-//     })));
-// }
-
 #[test]
 fn empty_arrays() {
     #[derive(Serialize, Deserialize, PartialEq, Debug, Clone)]