Merge pull request #278 from Kerollmops/master

Add the preserve_order feature (rebased version)

3 files changed, 611 insertions, 8 deletions

diff --git a/src/lib.rs b/src/lib.rs
index e36ff52..4a32b13 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -153,7 +153,10 @@
 
 #[macro_use]
 extern crate serde;
+#[cfg(feature = "preserve_order")]
+extern crate linked_hash_map;
 
+pub mod map;
 pub mod value;
 #[doc(no_inline)]
 pub use value::Value;
diff --git a/src/map.rs b/src/map.rs
new file mode 100644
index 0000000..59ae24e
--- /dev/null
+++ b/src/map.rs
@@ -0,0 +1,595 @@
+// Copyright 2017 Serde Developers
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! A map of String to toml::Value.
+//!
+//! By default the map is backed by a [`BTreeMap`]. Enable the `preserve_order`
+//! feature of toml-rs to use [`LinkedHashMap`] instead.
+//!
+//! [`BTreeMap`]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
+//! [`LinkedHashMap`]: https://docs.rs/linked-hash-map/*/linked_hash_map/struct.LinkedHashMap.html
+
+use serde::{de, ser};
+use std::fmt::{self, Debug};
+use value::Value;
+use std::hash::Hash;
+use std::iter::FromIterator;
+use std::borrow::Borrow;
+use std::ops;
+
+#[cfg(not(feature = "preserve_order"))]
+use std::collections::{btree_map, BTreeMap};
+
+#[cfg(feature = "preserve_order")]
+use linked_hash_map::{self, LinkedHashMap};
+
+/// Represents a JSON key/value type.
+pub struct Map<K, V> {
+    map: MapImpl<K, V>,
+}
+
+#[cfg(not(feature = "preserve_order"))]
+type MapImpl<K, V> = BTreeMap<K, V>;
+#[cfg(feature = "preserve_order")]
+type MapImpl<K, V> = LinkedHashMap<K, V>;
+
+impl Map<String, Value> {
+    /// Makes a new empty Map.
+    #[inline]
+    pub fn new() -> Self {
+        Map {
+            map: MapImpl::new(),
+        }
+    }
+
+    #[cfg(not(feature = "preserve_order"))]
+    /// Makes a new empty Map with the given initial capacity.
+    #[inline]
+    pub fn with_capacity(capacity: usize) -> Self {
+        // does not support with_capacity
+        let _ = capacity;
+        Map {
+            map: BTreeMap::new(),
+        }
+    }
+
+    #[cfg(feature = "preserve_order")]
+    /// Makes a new empty Map with the given initial capacity.
+    #[inline]
+    pub fn with_capacity(capacity: usize) -> Self {
+        Map {
+            map: LinkedHashMap::with_capacity(capacity),
+        }
+    }
+
+    /// Clears the map, removing all values.
+    #[inline]
+    pub fn clear(&mut self) {
+        self.map.clear()
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    #[inline]
+    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&Value>
+    where
+        String: Borrow<Q>,
+        Q: Ord + Eq + Hash,
+    {
+        self.map.get(key)
+    }
+
+    /// Returns true if the map contains a value for the specified key.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    #[inline]
+    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
+    where
+        String: Borrow<Q>,
+        Q: Ord + Eq + Hash,
+    {
+        self.map.contains_key(key)
+    }
+
+    /// Returns a mutable reference to the value corresponding to the key.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    #[inline]
+    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut Value>
+    where
+        String: Borrow<Q>,
+        Q: Ord + Eq + Hash,
+    {
+        self.map.get_mut(key)
+    }
+
+    /// Inserts a key-value pair into the map.
+    ///
+    /// If the map did not have this key present, `None` is returned.
+    ///
+    /// If the map did have this key present, the value is updated, and the old
+    /// value is returned. The key is not updated, though; this matters for
+    /// types that can be `==` without being identical.
+    #[inline]
+    pub fn insert(&mut self, k: String, v: Value) -> Option<Value> {
+        self.map.insert(k, v)
+    }
+
+    /// Removes a key from the map, returning the value at the key if the key
+    /// was previously in the map.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    #[inline]
+    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<Value>
+    where
+        String: Borrow<Q>,
+        Q: Ord + Eq + Hash,
+    {
+        self.map.remove(key)
+    }
+
+    /// Gets the given key's corresponding entry in the map for in-place
+    /// manipulation.
+    pub fn entry<S>(&mut self, key: S) -> Entry
+    where
+        S: Into<String>,
+    {
+        #[cfg(not(feature = "preserve_order"))]
+        use std::collections::btree_map::Entry as EntryImpl;
+        #[cfg(feature = "preserve_order")]
+        use linked_hash_map::Entry as EntryImpl;
+
+        match self.map.entry(key.into()) {
+            EntryImpl::Vacant(vacant) => Entry::Vacant(VacantEntry { vacant: vacant }),
+            EntryImpl::Occupied(occupied) => Entry::Occupied(OccupiedEntry { occupied: occupied }),
+        }
+    }
+
+    /// Returns the number of elements in the map.
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.map.len()
+    }
+
+    /// Returns true if the map contains no elements.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.map.is_empty()
+    }
+
+    /// Gets an iterator over the entries of the map.
+    #[inline]
+    pub fn iter(&self) -> Iter {
+        Iter {
+            iter: self.map.iter(),
+        }
+    }
+
+    /// Gets a mutable iterator over the entries of the map.
+    #[inline]
+    pub fn iter_mut(&mut self) -> IterMut {
+        IterMut {
+            iter: self.map.iter_mut(),
+        }
+    }
+
+    /// Gets an iterator over the keys of the map.
+    #[inline]
+    pub fn keys(&self) -> Keys {
+        Keys {
+            iter: self.map.keys(),
+        }
+    }
+
+    /// Gets an iterator over the values of the map.
+    #[inline]
+    pub fn values(&self) -> Values {
+        Values {
+            iter: self.map.values(),
+        }
+    }
+}
+
+impl Default for Map<String, Value> {
+    #[inline]
+    fn default() -> Self {
+        Map {
+            map: MapImpl::new(),
+        }
+    }
+}
+
+impl Clone for Map<String, Value> {
+    #[inline]
+    fn clone(&self) -> Self {
+        Map {
+            map: self.map.clone(),
+        }
+    }
+}
+
+impl PartialEq for Map<String, Value> {
+    #[inline]
+    fn eq(&self, other: &Self) -> bool {
+        self.map.eq(&other.map)
+    }
+}
+
+/// Access an element of this map. Panics if the given key is not present in the
+/// map.
+impl<'a, Q: ?Sized> ops::Index<&'a Q> for Map<String, Value>
+where
+    String: Borrow<Q>,
+    Q: Ord + Eq + Hash,
+{
+    type Output = Value;
+
+    fn index(&self, index: &Q) -> &Value {
+        self.map.index(index)
+    }
+}
+
+/// Mutably access an element of this map. Panics if the given key is not
+/// present in the map.
+impl<'a, Q: ?Sized> ops::IndexMut<&'a Q> for Map<String, Value>
+where
+    String: Borrow<Q>,
+    Q: Ord + Eq + Hash,
+{
+    fn index_mut(&mut self, index: &Q) -> &mut Value {
+        self.map.get_mut(index).expect("no entry found for key")
+    }
+}
+
+impl Debug for Map<String, Value> {
+    #[inline]
+    fn fmt(&self, formatter: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+        self.map.fmt(formatter)
+    }
+}
+
+impl ser::Serialize for Map<String, Value> {
+    #[inline]
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: ser::Serializer,
+    {
+        use serde::ser::SerializeMap;
+        let mut map = try!(serializer.serialize_map(Some(self.len())));
+        for (k, v) in self {
+            try!(map.serialize_key(k));
+            try!(map.serialize_value(v));
+        }
+        map.end()
+    }
+}
+
+impl<'de> de::Deserialize<'de> for Map<String, Value> {
+    #[inline]
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: de::Deserializer<'de>,
+    {
+        struct Visitor;
+
+        impl<'de> de::Visitor<'de> for Visitor {
+            type Value = Map<String, Value>;
+
+            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+                formatter.write_str("a map")
+            }
+
+            #[inline]
+            fn visit_unit<E>(self) -> Result<Self::Value, E>
+            where
+                E: de::Error,
+            {
+                Ok(Map::new())
+            }
+
+            #[inline]
+            fn visit_map<V>(self, mut visitor: V) -> Result<Self::Value, V::Error>
+            where
+                V: de::MapAccess<'de>,
+            {
+                let mut values = Map::new();
+
+                while let Some((key, value)) = try!(visitor.next_entry()) {
+                    values.insert(key, value);
+                }
+
+                Ok(values)
+            }
+        }
+
+        deserializer.deserialize_map(Visitor)
+    }
+}
+
+impl FromIterator<(String, Value)> for Map<String, Value> {
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = (String, Value)>,
+    {
+        Map {
+            map: FromIterator::from_iter(iter),
+        }
+    }
+}
+
+impl Extend<(String, Value)> for Map<String, Value> {
+    fn extend<T>(&mut self, iter: T)
+    where
+        T: IntoIterator<Item = (String, Value)>,
+    {
+        self.map.extend(iter);
+    }
+}
+
+macro_rules! delegate_iterator {
+    (($name:ident $($generics:tt)*) => $item:ty) => {
+        impl $($generics)* Iterator for $name $($generics)* {
+            type Item = $item;
+            #[inline]
+            fn next(&mut self) -> Option<Self::Item> {
+                self.iter.next()
+            }
+            #[inline]
+            fn size_hint(&self) -> (usize, Option<usize>) {
+                self.iter.size_hint()
+            }
+        }
+
+        impl $($generics)* DoubleEndedIterator for $name $($generics)* {
+            #[inline]
+            fn next_back(&mut self) -> Option<Self::Item> {
+                self.iter.next_back()
+            }
+        }
+
+        impl $($generics)* ExactSizeIterator for $name $($generics)* {
+            #[inline]
+            fn len(&self) -> usize {
+                self.iter.len()
+            }
+        }
+    }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+
+/// A view into a single entry in a map, which may either be vacant or occupied.
+/// This enum is constructed from the [`entry`] method on [`Map`].
+///
+/// [`entry`]: struct.Map.html#method.entry
+/// [`Map`]: struct.Map.html
+pub enum Entry<'a> {
+    /// A vacant Entry.
+    Vacant(VacantEntry<'a>),
+    /// An occupied Entry.
+    Occupied(OccupiedEntry<'a>),
+}
+
+/// A vacant Entry. It is part of the [`Entry`] enum.
+///
+/// [`Entry`]: enum.Entry.html
+pub struct VacantEntry<'a> {
+    vacant: VacantEntryImpl<'a>,
+}
+
+/// An occupied Entry. It is part of the [`Entry`] enum.
+///
+/// [`Entry`]: enum.Entry.html
+pub struct OccupiedEntry<'a> {
+    occupied: OccupiedEntryImpl<'a>,
+}
+
+#[cfg(not(feature = "preserve_order"))]
+type VacantEntryImpl<'a> = btree_map::VacantEntry<'a, String, Value>;
+#[cfg(feature = "preserve_order")]
+type VacantEntryImpl<'a> = linked_hash_map::VacantEntry<'a, String, Value>;
+
+#[cfg(not(feature = "preserve_order"))]
+type OccupiedEntryImpl<'a> = btree_map::OccupiedEntry<'a, String, Value>;
+#[cfg(feature = "preserve_order")]
+type OccupiedEntryImpl<'a> = linked_hash_map::OccupiedEntry<'a, String, Value>;
+
+impl<'a> Entry<'a> {
+    /// Returns a reference to this entry's key.
+    pub fn key(&self) -> &String {
+        match *self {
+            Entry::Vacant(ref e) => e.key(),
+            Entry::Occupied(ref e) => e.key(),
+        }
+    }
+
+    /// Ensures a value is in the entry by inserting the default if empty, and
+    /// returns a mutable reference to the value in the entry.
+    pub fn or_insert(self, default: Value) -> &'a mut Value {
+        match self {
+            Entry::Vacant(entry) => entry.insert(default),
+            Entry::Occupied(entry) => entry.into_mut(),
+        }
+    }
+
+    /// Ensures a value is in the entry by inserting the result of the default
+    /// function if empty, and returns a mutable reference to the value in the
+    /// entry.
+    pub fn or_insert_with<F>(self, default: F) -> &'a mut Value
+    where
+        F: FnOnce() -> Value,
+    {
+        match self {
+            Entry::Vacant(entry) => entry.insert(default()),
+            Entry::Occupied(entry) => entry.into_mut(),
+        }
+    }
+}
+
+impl<'a> VacantEntry<'a> {
+    /// Gets a reference to the key that would be used when inserting a value
+    /// through the VacantEntry.
+    #[inline]
+    pub fn key(&self) -> &String {
+        self.vacant.key()
+    }
+
+    /// Sets the value of the entry with the VacantEntry's key, and returns a
+    /// mutable reference to it.
+    #[inline]
+    pub fn insert(self, value: Value) -> &'a mut Value {
+        self.vacant.insert(value)
+    }
+}
+
+impl<'a> OccupiedEntry<'a> {
+    /// Gets a reference to the key in the entry.
+    #[inline]
+    pub fn key(&self) -> &String {
+        self.occupied.key()
+    }
+
+    /// Gets a reference to the value in the entry.
+    #[inline]
+    pub fn get(&self) -> &Value {
+        self.occupied.get()
+    }
+
+    /// Gets a mutable reference to the value in the entry.
+    #[inline]
+    pub fn get_mut(&mut self) -> &mut Value {
+        self.occupied.get_mut()
+    }
+
+    /// Converts the entry into a mutable reference to its value.
+    #[inline]
+    pub fn into_mut(self) -> &'a mut Value {
+        self.occupied.into_mut()
+    }
+
+    /// Sets the value of the entry with the `OccupiedEntry`'s key, and returns
+    /// the entry's old value.
+    #[inline]
+    pub fn insert(&mut self, value: Value) -> Value {
+        self.occupied.insert(value)
+    }
+
+    /// Takes the value of the entry out of the map, and returns it.
+    #[inline]
+    pub fn remove(self) -> Value {
+        self.occupied.remove()
+    }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+
+impl<'a> IntoIterator for &'a Map<String, Value> {
+    type Item = (&'a String, &'a Value);
+    type IntoIter = Iter<'a>;
+    #[inline]
+    fn into_iter(self) -> Self::IntoIter {
+        Iter {
+            iter: self.map.iter(),
+        }
+    }
+}
+
+/// An iterator over a toml::Map's entries.
+pub struct Iter<'a> {
+    iter: IterImpl<'a>,
+}
+
+#[cfg(not(feature = "preserve_order"))]
+type IterImpl<'a> = btree_map::Iter<'a, String, Value>;
+#[cfg(feature = "preserve_order")]
+type IterImpl<'a> = linked_hash_map::Iter<'a, String, Value>;
+
+delegate_iterator!((Iter<'a>) => (&'a String, &'a Value));
+
+//////////////////////////////////////////////////////////////////////////////
+
+impl<'a> IntoIterator for &'a mut Map<String, Value> {
+    type Item = (&'a String, &'a mut Value);
+    type IntoIter = IterMut<'a>;
+    #[inline]
+    fn into_iter(self) -> Self::IntoIter {
+        IterMut {
+            iter: self.map.iter_mut(),
+        }
+    }
+}
+
+/// A mutable iterator over a toml::Map's entries.
+pub struct IterMut<'a> {
+    iter: IterMutImpl<'a>,
+}
+
+#[cfg(not(feature = "preserve_order"))]
+type IterMutImpl<'a> = btree_map::IterMut<'a, String, Value>;
+#[cfg(feature = "preserve_order")]
+type IterMutImpl<'a> = linked_hash_map::IterMut<'a, String, Value>;
+
+delegate_iterator!((IterMut<'a>) => (&'a String, &'a mut Value));
+
+//////////////////////////////////////////////////////////////////////////////
+
+impl IntoIterator for Map<String, Value> {
+    type Item = (String, Value);
+    type IntoIter = IntoIter;
+    #[inline]
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            iter: self.map.into_iter(),
+        }
+    }
+}
+
+/// An owning iterator over a toml::Map's entries.
+pub struct IntoIter {
+    iter: IntoIterImpl,
+}
+
+#[cfg(not(feature = "preserve_order"))]
+type IntoIterImpl = btree_map::IntoIter<String, Value>;
+#[cfg(feature = "preserve_order")]
+type IntoIterImpl = linked_hash_map::IntoIter<String, Value>;
+
+delegate_iterator!((IntoIter) => (String, Value));
+
+//////////////////////////////////////////////////////////////////////////////
+
+/// An iterator over a toml::Map's keys.
+pub struct Keys<'a> {
+    iter: KeysImpl<'a>,
+}
+
+#[cfg(not(feature = "preserve_order"))]
+type KeysImpl<'a> = btree_map::Keys<'a, String, Value>;
+#[cfg(feature = "preserve_order")]
+type KeysImpl<'a> = linked_hash_map::Keys<'a, String, Value>;
+
+delegate_iterator!((Keys<'a>) => &'a String);
+
+//////////////////////////////////////////////////////////////////////////////
+
+/// An iterator over a toml::Map's values.
+pub struct Values<'a> {
+    iter: ValuesImpl<'a>,
+}
+
+#[cfg(not(feature = "preserve_order"))]
+type ValuesImpl<'a> = btree_map::Values<'a, String, Value>;
+#[cfg(feature = "preserve_order")]
+type ValuesImpl<'a> = linked_hash_map::Values<'a, String, Value>;
+
+delegate_iterator!((Values<'a>) => &'a Value);
diff --git a/src/value.rs b/src/value.rs
index ee952b6..07378cf 100644
--- a/src/value.rs
+++ b/src/value.rs
@@ -14,6 +14,9 @@ use serde::ser;
 use datetime::{self, DatetimeFromString};
 pub use datetime::{Datetime, DatetimeParseError};
 
+pub use map::Map;
+
+
 /// Representation of a TOML value.
 #[derive(PartialEq, Clone, Debug)]
 pub enum Value {
@@ -36,8 +39,10 @@ pub enum Value {
 /// Type representing a TOML array, payload of the `Value::Array` variant
 pub type Array = Vec<Value>;
 
-/// Type representing a TOML table, payload of the `Value::Table` variant
-pub type Table = BTreeMap<String, Value>;
+/// Type representing a TOML table, payload of the `Value::Table` variant.
+/// By default it is backed by a BTreeMap, enable the `preserve_order` feature
+/// to use a LinkedHashMap instead.
+pub type Table = Map<String, Value>;
 
 impl Value {
     /// Convert a `T` into `toml::Value` which is an enum that can represent
@@ -525,10 +530,10 @@ impl<'de> de::Deserialize<'de> for Value {
                         let date: DatetimeFromString = visitor.next_value()?;
                         return Ok(Value::Datetime(date.value));
                     }
-                    None => return Ok(Value::Table(BTreeMap::new())),
+                    None => return Ok(Value::Table(Map::new())),
                     Some(false) => {}
                 }
-                let mut map = BTreeMap::new();
+                let mut map = Map::new();
                 map.insert(key, visitor.next_value()?);
                 while let Some(key) = visitor.next_key()? {
                     if map.contains_key(&key) {
@@ -663,12 +668,12 @@ impl<'de> de::SeqAccess<'de> for SeqDeserializer {
 }
 
 struct MapDeserializer {
-    iter: <BTreeMap<String, Value> as IntoIterator>::IntoIter,
+    iter: <Map<String, Value> as IntoIterator>::IntoIter,
     value: Option<(String, Value)>,
 }
 
 impl MapDeserializer {
-    fn new(map: BTreeMap<String, Value>) -> Self {
+    fn new(map: Map<String, Value>) -> Self {
         MapDeserializer {
             iter: map.into_iter(),
             value: None,
@@ -881,7 +886,7 @@ impl ser::Serializer for Serializer {
 
     fn serialize_map(self, _len: Option<usize>) -> Result<Self::SerializeMap, ::ser::Error> {
         Ok(SerializeMap {
-            map: BTreeMap::new(),
+            map: Map::new(),
             next_key: None,
         })
     }
@@ -910,7 +915,7 @@ struct SerializeVec {
 }
 
 struct SerializeMap {
-    map: BTreeMap<String, Value>,
+    map: Map<String, Value>,
     next_key: Option<String>,
 }