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

Issue:
Enforce constraints
## Problems
1. Currently, toml spec does not have any positional constraints on tables (cf [toml/issues/446](https://github.com/toml-lang/toml/issues/446)). E.g. this is a valid toml:
```toml
[[bin]] # bin 1
[a.b.c.d]
[a]
[other.table]
[a.b.c.e]
[[bin]] # bin 2
[a.b.c]
[[bin]] # bin 3
```
This greatly complicates internal design of `toml_edit`, e.g. we have to store this order somewhere outside of the tables (document), and in order to support table insertion and deletion on `Table`, we have to store a pointer to the document in it. That's why we don't allow a user to own a `Table`, providing only a (mut) ref to a `Table`.

If we are free to reorder the tables when printing them, we can simplify the design and get rid of the no-ownership constraint. This, in turn, would allow us to have a single `Value` enum and implement `serde_json`-like nice API and get rid of unsafe code!

2. Another annoying thing is whitespaces in headers.
```toml
[ 'this  '   . is . a .valid.    "header..." ]
```
In order to preserve this layout, we have to store the whole header in the `Table`, but then `Table` assignment would be unfortunate, because header will also be mutated, while in `hashmap`, storing subtable index, there still be the old key.

## Proposal
1. Allow any order when parsing the document, but internally store all children after theirs parent. Also store array of tables in one place. When printing the toml from above, it would look like: 
```toml
[[bin]] # bin 1
[[bin]] # bin 2
[[bin]] # bin 3
[a]
[a.b.c]
[a.b.c.e]
[a.b.c.d]
[other.table]
```
Unresolved: should we sort the children as well?

2. Drop all whitespaces in the header.
```toml
['this  '.is.a.valid."header..."]
```

cc @killercup, what do you think?


Discussion / hints:
I'm totally fine with this being a… let's call it "intention-preserving pretty printer" :)

At the last rust.cologne meetup, we talked about a more simplistic approach to a toml reader/writer specifically for cargo-edit. One design we landed on was Having the whole toml AST consist of slices of the input string (maybe represented as rope). Adding/removing an entry would then "just" be inserting another slice at some position, or removing slice(s). I doubt this scales well to a more general purpose library, though.
Thanks for the feedback! 

I think I've got an idea on how to improve API without implementing this proposal. As for duplication in Table and InlineTable, a viable approach worth investigating may be to create a common trait TableLike and implement a method on them, which will return a trait object.

I'm going to close this issue.

Fix patch:
diff --git a/README.md b/README.md
index bd5a561d..753e59e9 100644
--- a/README.md
+++ b/README.md
@@ -9,9 +9,16 @@
 
 
 This crate allows you to parse and modify toml
-documents, while preserving comments, spaces and
+documents, while *mostly* preserving comments, spaces and
 relative order or items.
 
+Things it does not preserve include:
+1. Spaces in headers, e.g. `[ ' a ' .  b ]` will be represented as [' a '.b]
+2. Children tables before parent table (tables are reordered).
+3. Scattered array of tables (tables are reordered).
+
+`toml_edit` is primarily tailored for [cargo-edit](https://github.com/killercup/cargo-edit/) needs.
+
 ## Example
 
 ```rust
@@ -20,20 +27,16 @@ extern crate toml_edit;
 use toml_edit::Document;
 
 fn main() {
-    let toml = r#"hello = 'toml!' # comment"#;
+    let toml = r#"
+      "hello" = 'toml!' # comment
+      ['a'.b]
+    "#;
     let doc = toml.parse::<Document>();
     assert!(doc.is_ok());
     assert_eq!(doc.unwrap().to_string(), toml);
 }
 ```
 
-## Caveats
-
-Due to internal design, `mem::swap`ping two `Table`s or `ArrayOfTables` is considered harmful 
-(it won't do what you'd expect, see [test_safety](./tests/test_safety.rs)).
-
-Swapping `Value`s is fine though (but you can lose formatting, e.g. comments).
-
 ## License
 
 Licensed under either of
diff --git a/fuzz/parse_document.rs b/fuzz/parse_document.rs
index da1190e0..9ae4d119 100644
--- a/fuzz/parse_document.rs
+++ b/fuzz/parse_document.rs
@@ -9,7 +9,11 @@ fuzz_target!(|data| {
     if let Ok(data) = std::str::from_utf8(data) {
         let doc = data.parse::<Document>();
         if let Ok(doc) = doc {
-            assert_eq!(doc.to_string(), data);
+            let toml = doc.to_string();
+            let doc = toml.parse::<Document>();
+            assert!(doc.is_ok());
+            let doc = doc.unwrap();
+            assert_eq!(doc.to_string(), toml);
         }
     }
 });
diff --git a/src/array_of_tables.rs b/src/array_of_tables.rs
index b537c25e..19b72b27 100644
--- a/src/array_of_tables.rs
+++ b/src/array_of_tables.rs
@@ -1,81 +1,43 @@
-use decor::*;
-use table::{remove_table_recursive, Header, HeaderKind, Table};
-use document::DocumentInner;
-use std::fmt;
+use table::Table;
 
 /// Type representing a TOML array of tables
+#[derive(Clone, Debug, Default)]
 pub struct ArrayOfTables {
-    pub(crate) values: Vec<*mut Table>,
-    // Example: in [["a". b]] key is "\"a\". b"
-    // we need the key in order to support
-    // insertion into an empty array.
-    key: InternalString,
-    // We need this pointer to support
-    // table insertion and deletion.
-    doc: *mut DocumentInner,
+    pub(crate) values: Vec<Table>,
 }
 
 impl ArrayOfTables {
-    pub(crate) fn new(key: &str, doc: *mut DocumentInner) -> Self {
-        Self {
-            key: key.into(),
-            doc: doc,
-            values: Default::default(),
-        }
-    }
-    /// Returns an optional reference to the table
-    pub fn get(&self, index: usize) -> Option<&Table> {
-        // safe, all pointer are valid
-        self.values
-            .get(index)
-            .map(|t| unsafe { (*t).as_ref().unwrap() })
+    pub fn new() -> Self {
+        Default::default()
     }
 
     /// Returns an iterator over tables
     pub fn iter<'a>(&'a self) -> Box<Iterator<Item = &'a Table> + 'a> {
-        Box::new(self.values.iter().map(|t| unsafe { &**t }))
+        Box::new(self.values.iter())
+    }
+
+    /// Returns an optional reference to the table
+    pub fn get(&self, index: usize) -> Option<&Table> {
+        self.values.get(index)
     }
 
     /// Returns an optional mutable reference to the table
     pub fn get_mut(&mut self, index: usize) -> Option<&mut Table> {
-        // safe, all pointer are valid
-        self.values
-            .get_mut(index)
-            .map(|t| unsafe { (*t).as_mut().unwrap() })
+        self.values.get_mut(index)
     }
 
-    /// Appends a new table after the last array's child,
-    /// or, if the array is empty, after the document.
-    pub fn append(&mut self) -> &mut Table {
-        let header = Header {
-            repr: Repr::new("\n", &self.key, "\n"),
-            kind: HeaderKind::Array,
-        };
-        let after_ptr = self.values
-            .iter()
-            .last()
-            .map(|p| *p as *const Table)
-            .unwrap_or(self.doc_mut().list.back().get().unwrap() as *const Table);
-        self.append_with_header(header, after_ptr)
+    pub fn append(&mut self, table: Table) -> &mut Table {
+        self.values.push(table);
+        let i = self.len() - 1;
+        self.get_mut(i).unwrap()
     }
 
-    /// Removes the table at the given index.
-    ///
-    /// # Panics
-    ///
-    /// If `index >= self.len()`
     pub fn remove(&mut self, index: usize) {
-        let ptr = self.values[index];
-        remove_table_recursive(ptr, self.doc_mut());
         self.values.remove(index);
     }
 
-    /// Removes all the tables
-    pub fn remove_all(&mut self) {
-        let n = self.len();
-        for i in (0..n).rev() {
-            self.remove(i);
-        }
+    pub fn clear(&mut self) {
+        self.values.clear()
     }
 
     pub fn len(&self) -> usize {
@@ -85,30 +47,4 @@ impl ArrayOfTables {
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
-
-    fn doc_mut(&mut self) -> &mut DocumentInner {
-        // safe, doc pointer is always valid
-        unsafe { self.doc.as_mut().unwrap() }
-    }
-
-    pub(crate) fn append_with_header(
-        &mut self,
-        header: Header,
-        after_ptr: *const Table,
-    ) -> &mut Table {
-        let table = Table::new(header, self.doc);
-        let ptr = self.doc_mut().insert(table, after_ptr);
-        self.values.push(ptr);
-        let i = self.len() - 1;
-        self.get_mut(i).unwrap()
-    }
-}
-
-impl fmt::Debug for ArrayOfTables {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        f.debug_struct("ArrayOfTables")
-            .field("key", &self.key)
-            .field("values", &self.values)
-            .finish()
-    }
 }
diff --git a/src/display.rs b/src/display.rs
index de6f0f44..c0242881 100644
--- a/src/display.rs
+++ b/src/display.rs
@@ -1,8 +1,9 @@
 use std::fmt::{Display, Formatter, Result};
-use value::{Array, DateTime, InlineTable, KeyValue, KeyValuePairs, Value};
+use value::{Array, DateTime, InlineTable, KeyValue, Value};
 use decor::{Formatted, Repr};
 use document::Document;
-use table::{Header, HeaderKind, Table};
+use table::{Container, Table};
+use std::cell::{Cell, RefCell};
 
 impl Display for Repr {
     fn fmt(&self, f: &mut Formatter) -> Result {
@@ -74,28 +75,47 @@ impl Display for InlineTable {
     }
 }
 
-impl Display for Header {
-    fn fmt(&self, f: &mut Formatter) -> Result {
-        if self.kind == HeaderKind::Implicit {
-            return Ok(());
-        }
-        let brackets = if self.kind == HeaderKind::Standard {
-            ["[", "]"]
-        } else {
-            ["[[", "]]"]
-        };
-        write!(f, "{}{}", self.repr.decor.prefix, brackets[0])?;
-        write!(f, "{}", self.repr.raw_value)?;
-        write!(f, "{}{}", brackets[1], self.repr.decor.suffix)
-    }
+struct TableFormatState<'t> {
+    path: RefCell<Vec<&'t str>>,
+    table: Cell<&'t Table>,
 }
 
-/// **Note**: It only displays Key/Value Pairs
-impl Display for Table {
+impl<'a> Display for TableFormatState<'a> {
     fn fmt(&self, f: &mut Formatter) -> Result {
-        if self.header.kind != HeaderKind::Implicit {
-            write!(f, "{}", self.header)?;
-            display_table_values(f, &self.key_value_pairs)?;
+        let table = self.table.get();
+
+        join(f, table.key_value_pairs.values(), "\n")?;
+        if !table.key_value_pairs.is_empty() {
+            write!(f, "\n")?;
+        }
+
+        for &(ref name, ref c) in table.containers.values() {
+            match *c {
+                Container::Table(ref t) => {
+                    self.path.borrow_mut().push(name);
+                    self.table.set(t);
+                    if !t.implicit {
+                        write!(f, "{}[", t.decor.prefix)?;
+                        write!(f, "{}", self.path.borrow().join("."))?;
+                        write!(f, "]{}\n", t.decor.suffix)?;
+                    }
+                    write!(f, "{}", self)?;
+                    self.table.set(table);
+                    self.path.borrow_mut().pop();
+                }
+                Container::Array(ref a) => {
+                    self.path.borrow_mut().push(name);
+                    for t in &a.values {
+                        self.table.set(t);
+                        write!(f, "{}[[", t.decor.prefix)?;
+                        write!(f, "{}", self.path.borrow().join("."))?;
+                        write!(f, "]]{}\n", t.decor.suffix)?;
+                        write!(f, "{}", self)?;
+                    }
+                    self.table.set(table);
+                    self.path.borrow_mut().pop();
+                }
+            }
         }
         Ok(())
     }
@@ -103,14 +123,11 @@ impl Display for Table {
 
 impl Display for Document {
     fn fmt(&self, f: &mut Formatter) -> Result {
-        for (i, c) in self.inner.list.iter().enumerate() {
-            if i > 0 {
-                write!(f, "{}", c)?;
-            } else {
-                // root table
-                display_table_values(f, &c.key_value_pairs)?;
-            }
-        }
+        let state = TableFormatState {
+            path: RefCell::new(Vec::new()),
+            table: Cell::new(&self.root),
+        };
+        write!(f, "{}", state)?;
         write!(f, "{}", self.trailing)
     }
 }
@@ -128,7 +145,3 @@ where
     }
     Ok(())
 }
-
-fn display_table_values(f: &mut Formatter, key_value_pairs: &KeyValuePairs) -> Result {
-    join(f, key_value_pairs.values(), "")
-}
diff --git a/src/document.rs b/src/document.rs
index b73ee2c4..7a782f44 100644
--- a/src/document.rs
+++ b/src/document.rs
@@ -1,141 +1,25 @@
-// WARNING: we're using unsafe code here (raw pointers)
-// until a better approach is found
-// (not involving replacing every pointer with Rc<RefCell<T>>).
-// Note, however, that the public API is *almost* safe to use.
-
-// Current design:
-// There are four main types: Value, Table, ArrayOfTables and Document(Inner).
-// Document allocates all tables in the typed arena.
-// Document also contains an intrusive list of all tables.
-// Each table contains a link to previous and next table,
-// the order is same as in the toml string representation.
-// Also each table and array of tables contain a link to the document,
-// in order to be able to insert and delete subtables.
-// See comments in the Table struct for details about safety.
-use intrusive_collections::{LinkedList, LinkedListLink, UnsafeRef};
 use std::str::FromStr;
-use std::mem;
-use typed_arena::Arena;
-use table::{Header, HeaderKind, Table, TableChild};
-use decor::{InternalString, Repr};
-use std::borrow::BorrowMut;
+use table::{Table, TableChild};
+use decor::InternalString;
 use parser;
-use std::fmt;
-
-// clippy is confused here
-#[cfg_attr(feature = "cargo-clippy", allow(unneeded_field_pattern))]
-pub(crate) mod intrusive {
-    use super::{LinkedListLink, Table, UnsafeRef};
-
-    intrusive_adapter!(pub TableAdapter = UnsafeRef<Table>:
-                       Table { link: LinkedListLink });
-}
-
-type TableList = LinkedList<intrusive::TableAdapter>;
-
-pub(crate) struct DocumentInner {
-    arena: Arena<Table>,
-    pub(crate) list: TableList,
-}
 
 /// Type representing a TOML document
-#[derive(Debug)]
+#[derive(Debug, Clone, Default)]
 pub struct Document {
-    // Note: box is needed in order to preserve
-    // the same address of *mut DocumentInner
-    // on document move in tables and arrays of tables.
-    pub(crate) inner: Box<DocumentInner>,
+    pub root: Table,
     // Trailing comments and whitespaces
     pub(crate) trailing: InternalString,
 }
 
 
-impl Default for Document {
-    fn default() -> Self {
-        Document::new()
-    }
-}
-
-pub(crate) const ROOT_HEADER: &'static str = "$root$";
-
 impl Document {
     /// Creates an empty document
     pub fn new() -> Self {
-        let list = LinkedList::new(intrusive::TableAdapter::new());
-        // reserve space for 10 tables
-        let arena = Arena::with_capacity(mem::size_of::<Table>() * 10);
-        let inner = DocumentInner::new(arena, list);
-        let mut doc = Box::new(inner);
-        let header = Header {
-            repr: Repr::new("\n", ROOT_HEADER, "\n"),
-            kind: HeaderKind::Implicit, // doesn't matter for root
-        };
-        let table = Table::new(header, doc.borrow_mut());
-        // safe, we're converting &mut to *mut
-        let ptr = unsafe { UnsafeRef::from_raw(doc.arena.alloc(table)) };
-        doc.list.push_front(ptr);
-        Self {
-            inner: doc,
-            trailing: "".into(),
-        }
-    }
-
-    pub fn root(&self) -> &Table {
-        // first element is always the root
-        let ptr = self.inner.list.front().get().unwrap() as *const Table;
-        // safe, since we're borrowing self
-        unsafe { ptr.as_ref().unwrap() }
-    }
-
-    pub fn root_mut(&mut self) -> &mut Table {
-        // first element is always the root
-        let ptr = self.inner.list.front_mut().get().unwrap() as *const Table as *mut Table;
-        // safe, since we're borrowing self mutably
-        unsafe { ptr.as_mut().unwrap() }
+        Default::default()
     }
 
     pub fn iter<'a>(&'a self) -> Box<Iterator<Item = (&'a str, TableChild<'a>)> + 'a> {
-        self.root().iter()
-    }
-}
-
-impl DocumentInner {
-    fn new(arena: Arena<Table>, list: TableList) -> Self {
-        Self {
-            arena: arena,
-            list: list,
-        }
-    }
-    pub(crate) fn insert(&mut self, table: Table, after: *const Table) -> *mut Table {
-        let node = self.arena.alloc(table);
-        let node_ptr = node as *const Table;
-        // safe, we're converting &mut to *mut
-        let ptr = unsafe { UnsafeRef::from_raw(node_ptr) };
-        // safe, since pointer `after` is always valid
-        let mut cursor = unsafe { self.list.cursor_mut_from_ptr(after) };
-        // insert into the documents list
-        cursor.insert_after(ptr);
-        node
-    }
-
-    pub(crate) fn move_to_end(&mut self, ptr: *const Table) {
-        self.remove(ptr);
-        let ptr = unsafe { UnsafeRef::from_raw(ptr) };
-        self.list.back_mut().insert_after(ptr);
-    }
-
-    pub(crate) fn remove(&mut self, ptr: *const Table) {
-        // safe, all pointers are valid list entries
-        let mut cursor = unsafe { self.list.cursor_mut_from_ptr(ptr) };
-        // remove from the list
-        let res = cursor.remove();
-        debug_assert!(res.is_some());
-    }
-}
-
-impl Drop for DocumentInner {
-    fn drop(&mut self) {
-        self.list.clear();
+        self.root.iter()
     }
 }
 
@@ -147,11 +31,3 @@ impl FromStr for Document {
         parser::TomlParser::parse(s)
     }
 }
-
-impl fmt::Debug for DocumentInner {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        f.debug_struct("DocumentInner")
-            .field("list", &self.list)
-            .finish()
-    }
-}
diff --git a/src/formatted.rs b/src/formatted.rs
index a42e780b..74a5c726 100644
--- a/src/formatted.rs
+++ b/src/formatted.rs
@@ -91,7 +91,7 @@ impl From<i64> for Value {
     fn from(i: i64) -> Self {
         Value::Integer(Formatted::new(
             i,
-            Repr::new(" ".to_string(), i.to_string(), "\n".to_string()),
+            Repr::new("".to_string(), i.to_string(), "".to_string()),
         ))
     }
 }
@@ -100,7 +100,7 @@ impl From<f64> for Value {
     fn from(f: f64) -> Self {
         Value::Float(Formatted::new(
             f,
-            Repr::new(" ".to_string(), f.to_string(), "\n".to_string()),
+            Repr::new("".to_string(), f.to_string(), "".to_string()),
         ))
     }
 }
@@ -109,7 +109,8 @@ impl<'b> From<&'b str> for Value {
     fn from(s: &'b str) -> Self {
         Value::String(Formatted::new(
             s.to_owned(),
-            Repr::new(" ".to_string(), format!("\"{}\"", s), "\n".to_string()),
+            // TODO: s.escape_debug() requires #![feature(str_escape)]
+            Repr::new("".to_string(), format!("\"{}\"", s), "".to_string()),
         ))
     }
 }
@@ -124,7 +125,7 @@ impl From<bool> for Value {
     fn from(b: bool) -> Self {
         Value::Boolean(Formatted::new(
             b,
-            Repr::new(" ", if b { "true" } else { "false" }, "\n"),
+            Repr::new("", if b { "true" } else { "false" }, ""),
         ))
     }
 }
@@ -134,7 +135,7 @@ impl From<DateTime> for Value {
         let s = d.to_string();
         Value::DateTime(Formatted::new(
             d,
-            Repr::new(" ".to_string(), s, "\n".to_string()),
+            Repr::new("".to_string(), s, "".to_string()),
         ))
     }
 }
@@ -150,26 +151,24 @@ impl<V: Into<Value>> FromIterator<V> for Value {
             ..Default::default()
         };
         decorate_array(&mut array);
-        array.decor.prefix = InternalString::from(" ");
-        array.decor.suffix = InternalString::from("\n");
         Value::Array(array)
     }
 }
 
-pub(crate) fn to_key_value_pairs<K, V, I>(iter: I) -> KeyValuePairs
+pub(crate) fn to_key_value_pairs<'k, K, V, I>(iter: I) -> KeyValuePairs
 where
-    K: Into<Key>,
+    K: Into<&'k Key>,
     V: Into<Value>,
     I: IntoIterator<Item = (K, V)>,
 {
     let v = iter.into_iter().map(|(a, b)| {
-        let s: Key = a.into();
-        (s.clone().into(), to_key_value(s.raw(), b.into()))
+        let s: &Key = a.into();
+        (s.get().into(), to_key_value(s.raw(), b.into()))
     });
     KeyValuePairs::from_iter(v)
 }
 
-impl<K: Into<Key>, V: Into<Value>> FromIterator<(K, V)> for Value {
+impl<'k, K: Into<&'k Key>, V: Into<Value>> FromIterator<(K, V)> for Value {
     fn from_iter<I>(iter: I) -> Self
     where
         I: IntoIterator<Item = (K, V)>,
@@ -178,8 +177,6 @@ impl<K: Into<Key>, V: Into<Value>> FromIterator<(K, V)> for Value {
             key_value_pairs: to_key_value_pairs(iter),
             ..Default::default()
         };
-        table.decor.prefix = InternalString::from(" ");
-        table.decor.suffix = InternalString::from("\n");
         decorate_inline_table(&mut table);
         Value::InlineTable(table)
     }
diff --git a/src/key.rs b/src/key.rs
index 15ad2e0c..d187aac8 100644
--- a/src/key.rs
+++ b/src/key.rs
@@ -43,16 +43,20 @@ impl FromStr for Key {
             Ok((_, ref rest)) if !rest.input.is_empty() => {
                 Err(Self::Err::from_unparsed(rest.positioner, s))
             }
-            Ok(((raw, key), _)) => Ok(Key {
-                raw: raw.into(),
-                key: key,
-            }),
+            Ok(((raw, key), _)) => Ok(Key::new(raw, key)),
             Err(e) => Err(Self::Err::new(e, s)),
         }
     }
 }
 
 impl Key {
+    pub(crate) fn new(raw: &str, key: InternalString) -> Self {
+        Self {
+            raw: raw.into(),
+            key: key,
+        }
+    }
+
     pub fn get(&self) -> &str {
         &self.key
     }
diff --git a/src/lib.rs b/src/lib.rs
index 9e9ac498..dbd30866 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -4,14 +4,10 @@
 //! # `toml_edit`
 //!
 //! This crate allows you to parse and modify toml
-//! documents, while preserving comments, spaces and
+//! documents, while *mostly* preserving comments, spaces and
 //! relative order or items.
 //!
-//! # Safety
-//!
-//! `mem::swap`ing `Table`s or `ArrayOfTables` is considered unsafe.
-//!
-//! Swapping `Value`s is fine.
+//! It is primarily tailored to the needs of [cargo-edit](https://github.com/killercup/cargo-edit/).
 //!
 //! # Example
 //!
@@ -21,19 +17,19 @@
 //! use toml_edit::Document;
 //!
 //! fn main() {
-//!     let toml = r#"hello = 'toml!' # comment"#;
+//!     let toml = r#"
+//!       "hello" = 'toml!' # comment
+//!       ['a'.b]
+//!     "#;
 //!     let doc = toml.parse::<Document>();
 //!     assert!(doc.is_ok());
 //!     assert_eq!(doc.unwrap().to_string(), toml);
 //! }
 //! ```
 #[macro_use]
-extern crate intrusive_collections;
-#[macro_use]
 extern crate combine;
 extern crate chrono;
 extern crate linked_hash_map;
-extern crate typed_arena;
 
 
 pub(crate) mod formatted;
diff --git a/src/parser/document.rs b/src/parser/document.rs
index 17211b49..4894d515 100644
--- a/src/parser/document.rs
+++ b/src/parser/document.rs
@@ -134,7 +134,7 @@ impl TomlParser {
             Ok((_, ref rest)) if !rest.input.is_empty() => {
                 Err(TomlError::from_unparsed(rest.positioner, s))
             }
-            Ok(..) => Ok(parser.into_inner().document),
+            Ok(..) => Ok(*parser.into_inner().document),
             Err(e) => Err(TomlError::new(e, s)),
         }
     }
@@ -157,7 +157,7 @@ impl TomlParser {
         if table.contains_key(&key) {
             Err(CustomError::DuplicateKey {
                 key: key.into(),
-                table: table.header.repr.raw_value.to_string(),
+                table: "<unknown>".into(), // TODO: get actual table name
             })
         } else {
             table.key_value_pairs.insert(key, kv);
diff --git a/src/parser/mod.rs b/src/parser/mod.rs
index 05e94687..956116a6 100644
--- a/src/parser/mod.rs
+++ b/src/parser/mod.rs
@@ -23,17 +23,17 @@ use document::Document;
 use table::Table;
 
 pub struct TomlParser {
-    document: Document,
+    document: Box<Document>,
     current_table: *mut Table,
 }
 
 impl Default for TomlParser {
     fn default() -> Self {
-        let mut doc = Document::new();
-        let root = doc.root_mut() as *mut Table;
+        let mut doc = Box::new(Document::new());
+        let table = &mut doc.root as *mut Table;
         Self {
             document: doc,
-            current_table: root,
+            current_table: table,
         }
     }
 }
@@ -460,7 +460,8 @@ that
 # trailing comment"#,
             r#""#,
             r#"  "#,
-            r#" hello = 'darkness' # my old friend "#,
+            r#" hello = 'darkness' # my old friend
+"#,
         ];
         for document in &documents {
             let doc = TomlParser::parse(document);
diff --git a/src/parser/table.rs b/src/parser/table.rs
index 2dc6ac27..d70cc927 100644
--- a/src/parser/table.rs
+++ b/src/parser/table.rs
@@ -1,13 +1,15 @@
 use combine::*;
 use combine::char::char;
-use combine::range::{range, recognize_with_value};
+use combine::range::range;
 use combine::primitives::RangeStream;
 use parser::TomlParser;
 use parser::errors::CustomError;
 use parser::trivia::{line_trailing, ws};
 use parser::key::key;
-use decor::{InternalString, Repr};
-use table::{Header, HeaderKind, Table, TableChildMut, TableEntry};
+use key::Key;
+use array_of_tables::ArrayOfTables;
+use decor::{Decor, InternalString};
+use table::{Table, TableChildMut, TableEntry};
 use std::mem;
 use std::cell::RefCell;
 // https://github.com/rust-lang/rust/issues/41358
@@ -29,11 +31,9 @@ const ARRAY_TABLE_CLOSE: &'static str = "]]";
 
 // note: this rule is not present in the original grammar
 // key-path = key *( table-key-sep key)
-parse!(key_path() -> (&'a str, Vec<InternalString>), {
-    recognize_with_value(
-        sep_by1(between(ws(), ws(), key().map(|(_, key)| key)),
-                char(TABLE_KEY_SEP))
-    )
+parse!(key_path() -> Vec<Key>, {
+    sep_by1(between(ws(), ws(), key().map(|(raw, key)| Key::new(raw, key))),
+            char(TABLE_KEY_SEP))
 });
 
 
@@ -94,29 +94,37 @@ parser!{
     }
 }
 
+pub(crate) fn duplicate_key(path: &[Key], i: usize) -> CustomError {
+    assert!(i < path.len());
+    let header: Vec<&str> = path[..i].iter().map(|key| key.raw()).collect();
+    CustomError::DuplicateKey {
+        key: path[i].raw().into(),
+        table: format!("[{}]", header.join(".")),
+    }
+}
+
 impl TomlParser {
     fn descend_path<'a>(
         table: &'a mut Table,
-        path: &[InternalString],
+        path: &[Key],
+        i: usize,
     ) -> Result<&'a mut Table, CustomError> {
-        if let Some(key) = path.get(0) {
-            let header = table.child_header(key, HeaderKind::Implicit);
-            let parent_header = table.header.repr.raw_value.to_string();
-            match table.append_table_with_header(key, header) {
-                TableChildMut::Value(..) => Err(CustomError::DuplicateKey {
-                    key: key.clone(),
-                    table: parent_header,
-                }),
+        if let Some(key) = path.get(i) {
+            let mut new_table = Table::new();
+            new_table.set_implicit();
+
+            match table.append_table(key, new_table) {
+                TableChildMut::Value(..) => Err(duplicate_key(path, i)),
                 TableChildMut::Array(array) => {
                     debug_assert!(!array.is_empty());
 
-                    let i = array.len() - 1;
-                    let last_child = array.get_mut(i).unwrap();
+                    let index = array.len() - 1;
+                    let last_child = array.get_mut(index).unwrap();
 
-                    Self::descend_path(last_child, &path[1..])
+                    Self::descend_path(last_child, path, i + 1)
                 }
                 TableChildMut::Table(sweet_child_of_mine) => {
-                    TomlParser::descend_path(sweet_child_of_mine, &path[1..])
+                    TomlParser::descend_path(sweet_child_of_mine, path, i + 1)
                 }
             }
         } else {
@@ -124,81 +132,61 @@ impl TomlParser {
         }
     }
 
-    fn on_std_header(
-        &mut self,
-        header: (&str, Vec<InternalString>),
-        trailing: &str,
-    ) -> Result<(), CustomError> {
-        let (span, header) = header;
-        debug_assert!(!header.is_empty());
+    fn on_std_header(&mut self, path: Vec<Key>, trailing: &str) -> Result<(), CustomError> {
+        debug_assert!(!path.is_empty());
 
         let leading = mem::replace(&mut self.document.trailing, InternalString::new());
-        let mut table = self.document.root_mut();
+        let table = &mut self.document.root;
 
-        let table = Self::descend_path(table, &header[..header.len() - 1]);
-        let key = &header[header.len() - 1];
+        let table = Self::descend_path(table, &path[..path.len() - 1], 0);
+        let key = &path[path.len() - 1];
 
         match table {
             Ok(table) => {
-                let header = Header {
-                    repr: Repr::new(leading, span.into(), trailing.into()),
-                    kind: HeaderKind::Standard,
-                };
+                let decor = Decor::new(leading, trailing.into());
 
-                match table.entry(key) {
+                match table.entry(key.get()) {
                     // if [a.b.c] header preceded [a.b]
-                    TableEntry::Table(ref mut t) if t.header.kind == HeaderKind::Implicit => {
-                        t.move_to_end();
-                        t.header = header;
+                    TableEntry::Table(ref mut t) if t.implicit => {
+                        debug_assert!(t.key_value_pairs.is_empty());
+                        t.decor = decor;
+                        t.implicit = false;
                         self.current_table = *t;
                         return Ok(());
                     }
                     TableEntry::Vacant(ref mut parent) => {
-                        let mut table = parent.append_table_with_header(key, header);
-                        self.current_table = table.as_table_mut().unwrap();
+                        let mut table = parent.append_table(key, Table::with_decor(decor));
+                        self.current_table = table.as_table_mut().expect("table");
                         return Ok(());
                     }
                     _ => {}
                 }
-                Err(CustomError::DuplicateKey {
-                    key: key.clone(),
-                    table: table.header.repr.raw_value.to_string(),
-                })
+                Err(duplicate_key(&path[..], path.len() - 1))
             }
             Err(e) => Err(e),
         }
     }
 
-    fn on_array_header(
-        &mut self,
-        header: (&str, Vec<InternalString>),
-        trailing: &str,
-    ) -> Result<(), CustomError> {
-        let (span, header) = header;
-        debug_assert!(!header.is_empty());
+    fn on_array_header(&mut self, path: Vec<Key>, trailing: &str) -> Result<(), CustomError> {
+        debug_assert!(!path.is_empty());
 
         let leading = mem::replace(&mut self.document.trailing, InternalString::new());
-        let mut table = self.document.root_mut();
+        let table = &mut self.document.root;
 
-        let key = &header[header.len() - 1];
-        let table = Self::descend_path(table, &header[..header.len() - 1]);
+        let key = &path[path.len() - 1];
+        let table = Self::descend_path(table, &path[..path.len() - 1], 0);
 
         match table {
-            Ok(table) => if !table.contains_table(key) && !table.contains_value(key) {
-                let header = Header {
-                    repr: Repr::new(leading, span.into(), trailing.into()),
-                    kind: HeaderKind::Array,
-                };
+            Ok(table) => if !table.contains_table(key.get()) && !table.contains_value(key.get()) {
+                let decor = Decor::new(leading, trailing.into());
 
-                let array = table.insert_array_assume_vacant(key);
-                self.current_table = array.append_with_header(header, self.current_table);
+                let mut array = table.append_array(key, ArrayOfTables::new());
+                let array = array.as_array_mut().expect("array");
+                self.current_table = array.append(Table::with_decor(decor));
 
                 Ok(())
             } else {
-                Err(CustomError::DuplicateKey {
-                    key: key.clone(),
-                    table: table.header.repr.raw_value.to_string(),
-                })
+                Err(duplicate_key(&path[..], path.len() - 1))
             },
             Err(e) => Err(e),
         }
diff --git a/src/parser/trivia.rs b/src/parser/trivia.rs
index 43a4d0ba..47528b38 100644
--- a/src/parser/trivia.rs
+++ b/src/parser/trivia.rs
@@ -95,11 +95,10 @@ parse!(line_ending() -> &'a str, {
 });
 
 // note: this rule is not present in the original grammar
-// line-trailing = ws [comment] line-ending
+// line-trailing = ws [comment] skip-line-ending
 parse!(line_trailing() -> &'a str, {
     recognize((
         ws(),
         optional(comment()),
-        line_ending(),
-    ))
+    )).skip(line_ending())
 });
diff --git a/src/table.rs b/src/table.rs
index e1c9ce53..9f8221af 100644
--- a/src/table.rs
+++ b/src/table.rs
@@ -1,75 +1,31 @@
-use std::collections::HashMap;
-use std::collections::hash_map::Entry;
+use linked_hash_map::LinkedHashMap;
 use value::{sort_key_value_pairs, InlineTable, KeyValuePairs, Value};
-use decor::{InternalString, Repr};
+use decor::{Decor, InternalString};
 use key::Key;
 use array_of_tables::ArrayOfTables;
-use intrusive_collections::LinkedListLink;
-use document::{DocumentInner, ROOT_HEADER};
-use formatted::{decorate, to_key_value};
-use std::fmt;
+use formatted::to_key_value;
 
-// TODO: add method to extract a child table into an inline table
+// TODO: add method to convert a table into inline table
 // TODO: impl Index
 // TODO: documentation
 
 /// Type representing a TOML non-inline table
+#[derive(Clone, Debug, Default)]
 pub struct Table {
-    pub(crate) header: Header,
     pub(crate) key_value_pairs: KeyValuePairs,
-
-    // Value in the map is a  pointer to a linked list node.
-    // All nodes are allocated in the typed arena and,
-    // therefore, won't relocate.
-    // Linked list itself (head of the list) is stored in the Document.
-    //
-    // Using pointer here is safe, since none of the pointers
-    // will outlive the document. Also, we can't use a reference to
-    // a table while having a mut ref to its child (granted by brwchk).
-    //
-    // Note: pointers should be wrapped in NonZero,
-    // but this API is nightly-only atm.
-    tables: HashMap<InternalString, *mut Table>,
-    arrays: HashMap<InternalString, ArrayOfTables>,
-
-    // Intrusive pointers to next and previous table in the document
-    pub(crate) link: LinkedListLink,
-    // We need this pointer to support (sub)table insertion and deletion
-    doc: *mut DocumentInner,
-}
-
-#[derive(Eq, PartialEq, Clone, Debug, Hash)]
-pub(crate) struct Header {
-    // ```notrust
-    // # comment
-    // [ a.  'escaped \n'.  c ]
-    // ```
-    //
-    // Corresponds to `Repr("#comment\n", " a.  'escaped \\n'.  c ", "\n")`
-    pub repr: Repr,
-    pub kind: HeaderKind,
+    pub(crate) containers: LinkedHashMap<InternalString, (InternalString, Container)>,
+    pub(crate) decor: Decor,
+    pub(crate) implicit: bool,
 }
 
-// # Example
-//
-// ```notrust
-// [dependencies.serde]
-// version = "1.0"
-// [[bin]]
-// name = "add"
-// ```
-//
-// Header kind of `dependencies` is `Implicit`,
-// header kind of `dependencies.serde` is `Standard`,
-// header kind of `bin` is `Array`.
-#[derive(Eq, PartialEq, Clone, Copy, Debug, Hash)]
-pub(crate) enum HeaderKind {
-    Implicit,
-    Standard,
-    Array,
+#[derive(Clone, Debug)]
+pub(crate) enum Container {
+    Table(Table),
+    Array(ArrayOfTables),
 }
 
 /// An immutable reference to a child
+#[derive(Clone, Debug)]
 pub enum TableChild<'a> {
     /// A reference to a child value
     Value(&'a Value),
@@ -82,6 +38,7 @@ pub enum TableChild<'a> {
 pub type Iter<'a> = Box<Iterator<Item = (&'a str, TableChild<'a>)> + 'a>;
 
 /// A mutable reference to a child
+#[derive(Debug)]
 pub enum TableChildMut<'a> {
     /// A mutable reference to a child value
     Value(&'a mut Value),
@@ -94,6 +51,7 @@ pub enum TableChildMut<'a> {
 pub type IterMut<'a> = Box<Iterator<Item = (&'a str, TableChildMut<'a>)> + 'a>;
 
 /// Return type of table.entry("key")
+#[derive(Debug)]
 pub enum TableEntry<'a> {
     /// A mutable reference to a child value
     Value(&'a mut Value),
@@ -105,46 +63,62 @@ pub enum TableEntry<'a> {
     Vacant(&'a mut Table),
 }
 
+impl Container {
+    fn as_table_please(&mut self) -> &mut Table {
+        match *self {
+            Container::Table(ref mut t) => t,
+            _ => unreachable!("table please"),
+        }
+    }
+    fn as_array_please(&mut self) -> &mut ArrayOfTables {
+        match *self {
+            Container::Array(ref mut a) => a,
+            _ => unreachable!("array please"),
+        }
+    }
+}
+
 impl Table {
-    pub(crate) fn new(header: Header, doc: *mut DocumentInner) -> Self {
+    pub fn new() -> Self {
+        Self::with_decor(Decor::new("\n", ""))
+    }
+
+    pub(crate) fn with_decor(decor: Decor) -> Self {
         Self {
-            header: header,
-            doc: doc,
-            key_value_pairs: Default::default(),
-            tables: Default::default(),
-            arrays: Default::default(),
-            link: Default::default(),
+            decor: decor,
+            ..Default::default()
         }
     }
     pub fn contains_key(&self, key: &str) -> bool {
-        self.contains_value(key) || self.contains_array(key) || self.contains_table(key)
+        self.contains_value(key) || self.contains_container(key)
     }
-    pub fn contains_value(&self, key: &str) -> bool {
+    pub(crate) fn contains_value(&self, key: &str) -> bool {
         self.key_value_pairs.contains_key(key)
     }
-    pub fn contains_table(&self, key: &str) -> bool {
-        self.tables.contains_key(key)
+    fn contains_container(&self, key: &str) -> bool {
+        self.containers.contains_key(key)
     }
-    pub fn contains_array(&self, key: &str) -> bool {
-        self.arrays.contains_key(key)
+    pub(crate) fn contains_table(&self, key: &str) -> bool {
+        match self.containers.get(key) {
+            Some(&(_, Container::Table(..))) => true,
+            _ => false,
+        }
     }
-
     /// Iterator over key/value pairs, arrays of tables and subtables.
     pub fn iter(&self) -> Iter {
         Box::new(
             self.key_value_pairs
                 .iter()
                 .map(|(k, kv)| (&k[..], TableChild::Value(&kv.value)))
-                .chain(
-                    self.arrays
-                        .iter()
-                        .map(|(k, a)| (&k[..], TableChild::Array(a))),
-                )
-                .chain(
-                    self.tables
-                        .iter()
-                        .map(|(k, ptr)| (&k[..], TableChild::Table(unsafe { &**ptr }))),
-                ),
+                .chain(self.containers.iter().map(|(k, c)| {
+                    (
+                        &k[..],
+                        match c.1 {
+                            Container::Table(ref t) => TableChild::Table(t),
+                            Container::Array(ref a) => TableChild::Array(a),
+                        },
+                    )
+                })),
         )
     }
 
@@ -155,13 +129,14 @@ impl Table {
             self.key_value_pairs
                 .iter_mut()
                 .map(|(k, kv)| (&k[..], TableChildMut::Value(&mut kv.value)))
-                .chain(
-                    self.arrays
-                        .iter_mut()
-                        .map(|(k, a)| (&k[..], TableChildMut::Array(a))),
-                )
-                .chain(self.tables.iter_mut().map(|(k, ptr)| {
-                    (&k[..], TableChildMut::Table(unsafe { &mut **ptr }))
+                .chain(self.containers.iter_mut().map(|(k, p)| {
+                    (
+                        &k[..],
+                        match p.1 {
+                            Container::Table(ref mut t) => TableChildMut::Table(t),
+                            Container::Array(ref mut a) => TableChildMut::Array(a),
+                        },
+                    )
                 })),
         )
     }
@@ -175,12 +150,11 @@ impl Table {
         }
     }
 
-
     pub fn remove(&mut self, key: &str) -> bool {
-        self.remove_table(key) || self.remove_array(key) || self.remove_value(key).is_some()
+        self.remove_container(key) || self.remove_value(key).is_some()
     }
 
-    pub fn remove_value<'a>(&'a mut self, key: &str) -> Option<Value> {
+    pub fn remove_value(&mut self, key: &str) -> Option<Value> {
         let val = self.key_value_pairs.remove(key).map(|kv| kv.value);
         if val.is_some() {
             self.set_implicit();
@@ -188,6 +162,10 @@ impl Table {
         val
     }
 
+    fn remove_container(&mut self, key: &str) -> bool {
+        self.containers.remove(key).is_some()
+    }
+
     /// Sorts Key/Value Pairs of the table,
     /// doesn't affect subtables or subarrays.
     pub fn sort_values(&mut self) {
@@ -195,7 +173,7 @@ impl Table {
     }
 
     pub fn len(&self) -> usize {
-        self.key_value_pairs.len() + self.tables.len() + self.arrays.len()
+        self.key_value_pairs.len() + self.containers.len()
     }
 
     pub fn is_empty(&self) -> bool {
@@ -203,15 +181,13 @@ impl Table {
     }
 
     pub fn get<'a>(&'a self, key: &str) -> Option<TableChild<'a>> {
-        if let Some(table) = self.tables.get(key) {
-            Some(TableChild::Table(
-                // safe, all child pointers are valid
-                unsafe { table.as_ref().unwrap() },
-            ))
+        if let Some(c) = self.containers.get(key) {
+            match c.1 {
+                Container::Table(ref t) => Some(TableChild::Table(t)),
+                Container::Array(ref a) => Some(TableChild::Array(a)),
+            }
         } else if let Some(kv) = self.key_value_pairs.get(key) {
             Some(TableChild::Value(&kv.value))
-        } else if let Some(a) = self.arrays.get(key) {
-            Some(TableChild::Array(a))
         } else {
             None
         }
@@ -220,23 +196,23 @@ impl Table {
     pub fn entry<'a>(&'a mut self, key: &str) -> TableEntry<'a> {
         if !self.contains_key(key) {
             TableEntry::Vacant(self)
-        } else if let Some(table) = self.tables.get_mut(key) {
-            TableEntry::Table(
-                // safe, all child pointers are valid
-                unsafe { table.as_mut().unwrap() },
-            )
-        } else if let Some(kv) = self.key_value_pairs.get_mut(key) {
-            TableEntry::Value(&mut kv.value)
+        } else if let Some(c) = self.containers.get_mut(key) {
+            match c.1 {
+                Container::Table(ref mut t) => TableEntry::Table(t),
+                Container::Array(ref mut a) => TableEntry::Array(a),
+            }
         } else {
-            // argh, non-lexical lifetimes please
-            TableEntry::Array(self.arrays.get_mut(key).unwrap())
+            let kv = self.key_value_pairs
+                .get_mut(key)
+                .expect("non-lexical lifetimes");
+            TableEntry::Value(&mut kv.value)
         }
     }
 
-    pub fn append_value<V: Into<Value>>(&mut self, key: Key, value: V) -> TableChildMut {
+    pub fn append_value<V: Into<Value>>(&mut self, key: &Key, value: V) -> TableChildMut {
         match self.entry(key.get()) {
             TableEntry::Vacant(me) => {
-                TableChildMut::Value(me.insert_value_assume_vacant(key, value.into()))
+                TableChildMut::Value(me.append_value_assume_vacant(key, value.into()))
             }
             TableEntry::Array(v) => TableChildMut::Array(v),
             TableEntry::Table(v) => TableChildMut::Table(v),
@@ -244,51 +220,21 @@ impl Table {
         }
     }
 
-    /// Tries to remove the table with the given key,
-    /// returns true if this operation succeeds, false otherwise.
-    pub fn remove_table<'a>(&'a mut self, key: &str) -> bool {
-        match self.tables.entry(key.into()) {
-            Entry::Vacant(..) => false,
-            Entry::Occupied(e) => {
-                // safe, doc pointer is always valid
-                remove_table_recursive(*e.get(), unsafe { self.doc.as_mut().unwrap() });
-                e.remove();
-                true
+    pub fn append_table(&mut self, key: &Key, table: Table) -> TableChildMut {
+        match self.entry(key.get()) {
+            TableEntry::Vacant(me) => {
+                TableChildMut::Table(me.append_table_assume_vacant(key, table))
             }
+            TableEntry::Array(v) => TableChildMut::Array(v),
+            TableEntry::Table(v) => TableChildMut::Table(v),
+            TableEntry::Value(v) => TableChildMut::Value(v),
         }
     }
 
-    /// Tries to insert a new table after the last table's child or,
-    /// if the table has no children, after the table itself.
-    /// If a child with the given key is present, returns a reference
-    /// to this child.
-    pub fn insert_table(&mut self, key: Key) -> TableChildMut {
-        let after_ptr = self.tables
-            .values()
-            .last()
-            .map(|p| *p as *const Table)
-            .unwrap_or(self as *const Table);
-        let header = self.child_header(key.raw(), HeaderKind::Standard);
-        self.insert_table_with_header(key.get(), header, after_ptr)
-    }
-
-    pub fn append_table(&mut self, key: Key) -> TableChildMut {
-        let header = self.child_header(key.raw(), HeaderKind::Standard);
-        self.append_table_with_header(key.get(), header)
-    }
-
-    pub fn remove_array<'a>(&'a mut self, key: &str) -> bool {
-        self.arrays
-            .remove(key)
-            .map(|mut a| a.remove_all())
-            .is_some()
-    }
-
-    pub fn insert_array(&mut self, key: Key) -> TableChildMut {
-        let child_key = self.child_key(key.raw());
+    pub fn append_array(&mut self, key: &Key, array: ArrayOfTables) -> TableChildMut {
         match self.entry(key.get()) {
             TableEntry::Vacant(me) => {
-                TableChildMut::Array(me.insert_array_assume_vacant(&child_key))
+                TableChildMut::Array(me.append_array_assume_vacant(key, array))
             }
             TableEntry::Array(v) => TableChildMut::Array(v),
             TableEntry::Table(v) => TableChildMut::Table(v),
@@ -309,94 +255,53 @@ impl Table {
     /// # use toml_edit::Document;
     /// #
     /// # fn main() {
-    /// let mut doc = "[a]\n[a.b]".parse::<Document>().unwrap();
-    /// assert!(doc.root_mut().entry("a").as_table_mut().unwrap().set_implicit());
-    /// assert_eq!(doc.to_string(), "[a.b]");
+    /// let mut doc = "[a]\n[a.b]\n".parse::<Document>().expect("valid toml");
+    ///
+    /// assert!(doc.root.entry("a").as_table_mut().unwrap().set_implicit());
+    /// assert_eq!(doc.to_string(), "[a.b]\n");
     /// # }
     /// ```
     pub fn set_implicit(&mut self) -> bool {
-        if self.key_value_pairs.is_empty() && self.header.kind == HeaderKind::Standard {
-            self.header.kind = HeaderKind::Implicit;
+        if self.key_value_pairs.is_empty() && !self.implicit {
+            self.implicit = true;
             true
         } else {
             false
         }
     }
 
-    fn insert_value_assume_vacant(&mut self, key: Key, value: Value) -> &mut Value {
-        debug_assert!(!self.tables.contains_key(key.get()));
-        debug_assert!(!self.arrays.contains_key(key.get()));
-        let mut kv = to_key_value(key.raw(), value);
-        decorate(&mut kv.value, " ", "\n");
-        if self.header.kind == HeaderKind::Implicit {
-            self.header.kind = HeaderKind::Standard;
-        }
-        &mut self.key_value_pairs.entry(key.into()).or_insert(kv).value
-    }
-
-    pub(crate) fn insert_array_assume_vacant<'a>(&'a mut self, key: &str) -> &'a mut ArrayOfTables {
-        let doc = self.doc;
-        self.arrays
-            .entry(InternalString::from(key))
-            .or_insert_with(|| ArrayOfTables::new(key, doc))
-    }
-
-    pub(crate) fn move_to_end(&mut self) {
-        let doc: &mut DocumentInner = unsafe { self.doc.as_mut().unwrap() };
-        doc.move_to_end(self);
-    }
-
-    pub(crate) fn child_header(&self, key: &str, kind: HeaderKind) -> Header {
-        let child_key = self.child_key(key);
-        Header {
-            repr: Repr::new("\n", &child_key, "\n"),
-            kind: kind,
-        }
-    }
-
-    pub(crate) fn child_key(&self, key: &str) -> InternalString {
-        let prefix = &self.header.repr.raw_value;
-        if prefix == ROOT_HEADER {
-            key.into()
-        } else {
-            format!("{}.{}", prefix, key)
-        }
-    }
-
-    pub(crate) fn append_table_with_header<'a>(
-        &'a mut self,
-        key: &str,
-        header: Header,
-    ) -> TableChildMut<'a> {
-        let doc = unsafe { self.doc.as_ref().unwrap() };
-        let back = doc.list.back().get().unwrap();
-        self.insert_table_with_header(key, header, back)
-    }
-
-    pub(crate) fn insert_table_with_header<'a>(
-        &'a mut self,
-        key: &str,
-        header: Header,
-        after_ptr: *const Table,
-    ) -> TableChildMut<'a> {
-        let doc = self.doc;
-        match self.entry(key) {
-            TableEntry::Vacant(me) => {
-                let table = Table::new(header, me.doc);
-                // safe, doc pointer is always valid
-                let doc: &mut DocumentInner = unsafe { doc.as_mut().unwrap() };
-                // insert into the document
-                let node_ptr = doc.insert(table, after_ptr);
-                // insert into the table
-                let result = me.tables.insert(key.into(), node_ptr);
-                debug_assert!(result.is_none());
-                // safe, because we're borrowing self mutably
-                TableChildMut::Table(unsafe { node_ptr.as_mut().unwrap() })
-            }
-            TableEntry::Array(v) => TableChildMut::Array(v),
-            TableEntry::Table(v) => TableChildMut::Table(v),
-            TableEntry::Value(v) => TableChildMut::Value(v),
+    fn append_value_assume_vacant(&mut self, key: &Key, value: Value) -> &mut Value {
+        debug_assert!(!self.contains_key(key.get()));
+        let kv = to_key_value(key.raw(), value);
+        if self.implicit {
+            self.implicit = false;
         }
+        &mut self.key_value_pairs
+            .entry(key.get().into())
+            .or_insert(kv)
+            .value
+    }
+
+    pub(crate) fn append_array_assume_vacant(
+        &mut self,
+        key: &Key,
+        array: ArrayOfTables,
+    ) -> &mut ArrayOfTables {
+        debug_assert!(!self.contains_key(key.get()));
+        let pair = (key.raw().into(), Container::Array(array));
+        let result = self.containers
+            .entry(key.get().into())
+            .or_insert_with(|| pair);
+        result.1.as_array_please()
+    }
+
+    pub(crate) fn append_table_assume_vacant(&mut self, key: &Key, table: Table) -> &mut Table {
+        debug_assert!(!self.contains_key(key.get()));
+        let pair = (key.raw().to_owned(), Container::Table(table));
+        let result = self.containers
+            .entry(key.get().into())
+            .or_insert_with(|| pair);
+        result.1.as_table_please()
     }
 }
 
@@ -556,31 +461,37 @@ impl<'a> TableChildMut<'a> {
     }
 }
 
-pub(crate) fn remove_table_recursive(ptr: *mut Table, doc: &mut DocumentInner) {
-    // safe, all child pointers are valid
-    let child: &mut Table = unsafe { ptr.as_mut().unwrap() };
-    let keys: Vec<InternalString> = child.tables.keys().cloned().collect();
-    // recursive subtables removal
-    for key in keys {
-        child.remove_table(&key);
-    }
-    let keys: Vec<InternalString> = child.arrays.keys().cloned().collect();
-    // recursive subarrays removal
-    for key in keys {
-        child.remove_array(&key);
-    }
-    // remove from the list
-    doc.remove(ptr);
+impl<'a> TableChildMut<'a> {
+    pub fn into_entry(self) -> TableEntry<'a> {
+        match self {
+            TableChildMut::Table(t) => TableEntry::Table(t),
+            TableChildMut::Array(t) => TableEntry::Array(t),
+            TableChildMut::Value(t) => TableEntry::Value(t),
+        }
+    }
 }
 
-impl fmt::Debug for Table {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        f.debug_struct("Table")
-            .field("header", &self.header)
-            .field("key_values_pairs", &self.key_value_pairs)
-            .field("tables", &self.tables)
-            .field("arrays", &self.arrays)
-            .field("link", &self.link)
-            .finish()
+impl<'e> TableEntry<'e> {
+    pub fn get(self, s: &str) -> TableEntry<'e> {
+        match self {
+            TableEntry::Table(table) => table.entry(s),
+            TableEntry::Value(&mut Value::InlineTable(ref mut t)) if t.contains_key(s) => {
+                t.get_mut(s).map(TableEntry::Value).unwrap()
+            }
+            a => a,
+        }
+    }
+
+    pub fn get_or_insert(self, s: &str) -> TableEntry<'e> {
+        let key: Key = s.parse().expect("valid key");
+        match self {
+            TableEntry::Value(&mut Value::InlineTable(ref mut t)) => TableEntry::Value(
+                t.try_insert(&key, Value::InlineTable(InlineTable::default())),
+            ),
+            TableEntry::Vacant(table) | TableEntry::Table(table) => {
+                table.append_table(&key, Table::new()).into_entry()
+            }
+            _ => panic!("can't access key {} in {:?}", s, self),
+        }
     }
 }
diff --git a/src/value.rs b/src/value.rs
index e23b2cdb..810ac156 100644
--- a/src/value.rs
+++ b/src/value.rs
@@ -161,14 +161,19 @@ impl InlineTable {
         self.key_value_pairs.contains_key(key)
     }
 
-    pub fn try_insert<V: Into<Value>>(&mut self, key: Key, value: V) -> &mut Value {
+    pub fn try_insert<V: Into<Value>>(&mut self, key: &Key, value: V) -> &mut Value {
         let kv = formatted::to_key_value(key.raw(), value.into());
-        &mut self.key_value_pairs.entry(key.into()).or_insert(kv).value
+        &mut self.key_value_pairs
+            .entry(key.get().into())
+            .or_insert(kv)
+            .value
     }
 
-    pub fn insert<V: Into<Value>>(&mut self, key: Key, value: V) -> Option<Value> {
+    pub fn insert<V: Into<Value>>(&mut self, key: &Key, value: V) -> Option<Value> {
         let kv = formatted::to_key_value(key.raw(), value.into());
-        self.key_value_pairs.insert(key.into(), kv).map(|p| p.value)
+        self.key_value_pairs
+            .insert(key.get().into(), kv)
+            .map(|p| p.value)
     }
 
     pub fn append(&mut self, other: &mut InlineTable) {


Test patch:
diff --git a/tests/test_edit.rs b/tests/test_edit.rs
index 6da6faa0..286196b9 100644
--- a/tests/test_edit.rs
+++ b/tests/test_edit.rs
@@ -5,7 +5,7 @@ macro_rules! parse_key {
         {
             let key = $s.parse::<Key>();
             assert!(key.is_ok());
-            key.unwrap()
+            &key.unwrap()
         }
     );
 }
@@ -23,7 +23,7 @@ macro_rules! as_table {
 #[cfg(test)]
 #[cfg_attr(rustfmt, rustfmt_skip)]
 mod tests {
-    use toml_edit::{Document, Key, Value, Table};
+    use toml_edit::{Document, Key, Value, Table, ArrayOfTables};
     use std::iter::FromIterator;
 
     struct Test {
@@ -43,7 +43,7 @@ mod tests {
             where F: Fn(&mut Table)
         {
             {
-                let mut root = self.doc.root_mut();
+                let root = &mut self.doc.root;
                 func(root);
             }
             self
@@ -69,7 +69,7 @@ fn test_insert_leaf_table() {
     ).running(|root| {
         let mut servers = root.entry("servers");
         let servers = as_table!(servers);
-        let mut beta = servers.insert_table(parse_key!("beta"));
+        let mut beta = servers.append_table(parse_key!("beta"), Table::new());
         let beta = as_table!(beta);
         beta.append_value(parse_key!("ip"), "10.0.0.2");
         beta.append_value(parse_key!("dc"), "eqdc10");
@@ -84,7 +84,8 @@ fn test_insert_leaf_table() {
 ip = "10.0.0.2"
 dc = "eqdc10"
 
-        [other.table]"#
+        [other.table]
+"#
     );
 }
 
@@ -93,14 +94,15 @@ fn test_insert_nonleaf_table() {
     given(r#"
         [other.table]"#
     ).running(|root| {
-        let mut servers = root.append_table(parse_key!("servers"));
+        let mut servers = root.append_table(parse_key!("servers"), Table::new());
         let servers = as_table!(servers);
-        let mut alpha = servers.insert_table(parse_key!("alpha"));
+        let mut alpha = servers.append_table(parse_key!("alpha"), Table::new());
         let alpha = as_table!(alpha);
         alpha.append_value(parse_key!("ip"), "10.0.0.1");
         alpha.append_value(parse_key!("dc"), "eqdc10");
     }).produces(r#"
         [other.table]
+
 [servers]
 
 [servers.alpha]
@@ -116,17 +118,18 @@ fn test_insert_array() {
         [package]
         title = "withoutarray""#
     ).running(|root| {
-        let mut array = root.insert_array(parse_key!("bin"));
+        let mut array = root.append_array(parse_key!("bin"), ArrayOfTables::new());
         assert!(array.is_array());
         let array = array.as_array_mut().unwrap();
         {
-            let mut first = array.append();
+            let mut first = array.append(Table::new());
             first.append_value(parse_key!("hello"), "world");
         }
-        array.append();
+        array.append(Table::new());
     }).produces(r#"
         [package]
         title = "withoutarray"
+
 [[bin]]
 hello = "world"
 
@@ -152,7 +155,8 @@ key1 = "value1"
 "key2" = 42
 'key3' = 8.1415926
 
-        [tbl.son]"#
+        [tbl.son]
+"#
     );
 }
 
@@ -174,13 +178,14 @@ fn test_remove_leaf_table() {
     ).running(|root| {
         let mut servers = root.entry("servers");
         let servers = as_table!(servers);
-        assert!(servers.remove_table("alpha"));
+        assert!(servers.remove("alpha"));
     }).produces(r#"
         [servers]
 
         [servers.beta]
         ip = "10.0.0.2"
-        dc = "eqdc10""#
+        dc = "eqdc10"
+"#
     );
 }
 
@@ -290,7 +295,7 @@ fn test_remove_array() {
         name = "delete me please"
         path = "src/bin/dmp/main.rs""#
     ).running(|root| {
-        assert!(root.remove_array("bin"));
+        assert!(root.remove("bin"));
     }).produces(r#"
         [package]
         name = "hello"
@@ -319,7 +324,8 @@ fn test_remove_value() {
         assert_eq!(value, "1.0.0");
     }).produces(r#"
         name = "hello"
-        documentation = "https://docs.rs/hello""#
+        documentation = "https://docs.rs/hello"
+"#
     );
 }
 
@@ -358,15 +364,16 @@ fn test_sort_values() {
         let a = as_table!(a);
         a.sort_values();
     }).produces(r#"
-        [a.z]
-
         [a]
         a = 1
         # this comment is attached to b
         b = 2 # as well as this
         c = 3
 
-        [a.y]"#
+        [a.z]
+
+        [a.y]
+"#
     );
 }
 
@@ -403,7 +410,8 @@ fn test_insert_into_array() {
         assert_eq!(b.len(), 1);
     }).produces(r#"
         a = [1, 2, 3, 4]
-        b = ["hello"]"#
+        b = ["hello"]
+"#
     );
 }
 
@@ -427,7 +435,8 @@ fn test_remove_from_array() {
         assert!(b.is_empty());
     }).produces(r#"
         a = [1, 2, 3]
-        b = []"#
+        b = []
+"#
     );
 }
 
@@ -465,7 +474,8 @@ fn test_insert_into_inline_table() {
         b.fmt()
     }).produces(r#"
         a = { a = 2, c = 3, b = 42 }
-        b = { 'hello' = "world" }"#
+        b = { 'hello' = "world" }
+"#
     );
 }
 
@@ -489,7 +499,8 @@ fn test_remove_from_inline_table() {
         assert!(b.is_empty());
     }).produces(r#"
         a = {a=2, b = 42}
-        b = {}"#
+        b = {}
+"#
     );
 }
 
diff --git a/tests/test_safety.rs b/tests/test_safety.rs
deleted file mode 100644
index 16d966a5..00000000
--- a/tests/test_safety.rs
+++ /dev/null
@@ -1,116 +0,0 @@
-// TL;DR don't mem::swap the tables
-// it's unsafe
-extern crate toml_edit;
-
-use toml_edit::{Document, Key};
-use std::mem;
-
-macro_rules! parse_doc {
-    ($toml:ident) => (
-        {
-            let doc = $toml.parse::<Document>();
-            assert!(doc.is_ok());
-            doc.unwrap()
-        }
-    );
-}
-
-
-macro_rules! as_table {
-    ($entry:ident) => (
-        {
-            assert!($entry.is_table());
-            $entry.as_table_mut().unwrap()
-        }
-    );
-}
-
-macro_rules! parse_key {
-    ($s:expr) => ($s.parse::<Key>().unwrap());
-}
-
-#[test]
-fn test_safety_issue() {
-
-    let toml1 = r#"
-[a]
-b = 2
-[a.c]
-b = 3
-[d]
-"#;
-    let toml2 = r#"
-[b.c]
-a = 3
-[b]
-a = 2
-[e]
-"#;
-    let mut doc1 = parse_doc!(toml1);
-    let mut doc2 = parse_doc!(toml2);
-
-    {
-        let mut r1 = doc1.root_mut();
-        let mut r2 = doc2.root_mut();
-        {
-            let mut a = r1.entry("a");
-            let mut a = as_table!(a);
-            let mut ac = a.entry("c");
-            let mut ac = as_table!(ac);
-            ac.insert_table(parse_key!("ac"));
-
-            let mut b = r2.entry("b");
-            let mut b = as_table!(b);
-            let mut bc = b.entry("c");
-            let mut bc = as_table!(bc);
-            bc.insert_table(parse_key!("bc"));
-
-            mem::swap(ac, bc); // now both documents are invalid (duplicate keys) :(
-        }
-
-        // what's even worse,
-        // `a.c` is now pointing to `[b.c]`
-        // also, the trailing tables list is swapped
-        let mut a = r1.entry("a");
-        let mut a = as_table!(a);
-        let mut ac = a.entry("c");
-        let mut ac = as_table!(ac);
-        ac.insert_table(parse_key!("'i am in [b.c]'"));
-
-        // same for `b.c`
-        let mut b = r2.entry("b");
-        let mut b = as_table!(b);
-        let mut bc = b.entry("c");
-        let mut bc = as_table!(bc);
-        bc.insert_table(parse_key!("'i am in [a.c]'"));
-    }
-
-    assert_eq!(
-        doc1.to_string(),
-        r#"
-[a]
-b = 2
-
-[b.c]
-a = 3
-
-[b.c.bc]
-
-[b.c.'i am in [b.c]']
-[b]
-a = 2
-[e]
-"#
-    );
-    assert_eq!(
-        doc2.to_string(),
-        r#"[a.c]
-b = 3
-
-[a.c.ac]
-
-[a.c.'i am in [a.c]']
-[d]
-"#
-    );
-}
diff --git a/tests/test_valid.rs b/tests/test_valid.rs
index 1b014f59..340ab4dc 100644
--- a/tests/test_valid.rs
+++ b/tests/test_valid.rs
@@ -54,6 +54,10 @@ fn run(json: &str, toml: &str) {
     assert_eq!(json, toml_json);
 
     // check round-trip equality
+    let toml = doc.to_string();
+    let doc = toml.parse::<Document>();
+    assert!(doc.is_ok());
+    let doc = doc.unwrap();
     assert_eq!(doc.to_string(), toml);
 }