ui: move Collection to Account

Each account had one mailbox per folder, which had one associated
collection. Now each Account has one Collection for all folders and each
Mailbox object holds only the hashes of each message.

Collection also gets Threads for each folder in order to mix messages
(ie from/to Sent folder).

Insert Sent emails in chronological order

if inserted unsorted, mails a, b with a happened-before b, might never
  get added.

Fix multiple insertions in ThreadTree upon insert_reply

insert_reply was creating multiple copies in threading

14 files changed, 914 insertions, 625 deletions

diff --git a/melib/src/mailbox.rs b/melib/src/mailbox.rs
index c593bc8a..773d226d 100644
--- a/melib/src/mailbox.rs
+++ b/melib/src/mailbox.rs
@@ -41,26 +41,30 @@ pub use self::collection::*;
 
 use std::option::Option;
 
+use fnv::{FnvHashMap, FnvHashSet};
 /// `Mailbox` represents a folder of mail.
 #[derive(Debug, Deserialize, Serialize, Clone, Default)]
 pub struct Mailbox {
     #[serde(skip_serializing, skip_deserializing)]
     pub folder: Folder,
     name: String,
-    pub collection: Collection,
+    pub envelopes: FnvHashSet<EnvelopeHash>,
+    pub thread_root_set: FnvHashSet<ThreadHash>,
     has_sent: bool,
 }
 
 impl Mailbox {
-    pub fn new(folder: Folder, envelopes: Result<Vec<Envelope>>) -> Result<Mailbox> {
-        let mut envelopes: Vec<Envelope> = envelopes?;
-        envelopes.sort_by(|a, b| a.date().cmp(&b.date()));
-        let collection = Collection::new(envelopes, &folder);
+    pub fn new(
+        folder: Folder,
+        envelopes: Result<&FnvHashMap<EnvelopeHash, Envelope>>,
+    ) -> Result<Mailbox> {
+        let envelopes = envelopes?;
         let name = folder.name().into();
+        let envelopes = envelopes.keys().cloned().collect();
         Ok(Mailbox {
             folder,
-            collection,
             name,
+            envelopes,
             ..Default::default()
         })
     }
@@ -70,65 +74,20 @@ impl Mailbox {
     }
 
     pub fn is_empty(&self) -> bool {
-        self.collection.is_empty()
+        self.envelopes.is_empty()
     }
     pub fn len(&self) -> usize {
-        self.collection.len()
+        self.envelopes.len()
     }
-    pub fn thread_to_mail_mut(&mut self, h: ThreadHash) -> &mut Envelope {
-        self.collection
-            .envelopes
-            .entry(self.collection.threads.thread_to_mail(h))
-            .or_default()
+    pub fn insert(&mut self, h: EnvelopeHash) {
+        self.envelopes.insert(h);
     }
-    pub fn thread_to_mail(&self, h: ThreadHash) -> &Envelope {
-        &self.collection.envelopes[&self.collection.threads.thread_to_mail(h)]
-    }
-    pub fn threaded_mail(&self, h: ThreadHash) -> EnvelopeHash {
-        self.collection.threads.thread_to_mail(h)
-    }
-    pub fn mail_and_thread(&mut self, i: EnvelopeHash) -> (&mut Envelope, &ThreadNode) {
-        let thread;
-        {
-            let x = &mut self.collection.envelopes.entry(i).or_default();
-            thread = &self.collection.threads[&x.thread()];
-        }
-        (self.collection.envelopes.entry(i).or_default(), thread)
-    }
-    pub fn thread(&self, h: ThreadHash) -> &ThreadNode {
-        &self.collection.threads.thread_nodes()[&h]
-    }
-
-    pub fn insert_sent_folder(&mut self, _sent: &Mailbox) {
-        /*if !self.has_sent {
-            for envelope in sent.collection.envelopes.values() {
-                self.insert_reply(envelope);
-            }
-            self.has_sent = true;
-        }*/
-    }
-
     pub fn rename(&mut self, old_hash: EnvelopeHash, new_hash: EnvelopeHash) {
-        self.collection.rename(old_hash, new_hash);
-    }
-
-    pub fn update(&mut self, old_hash: EnvelopeHash, envelope: Envelope) {
-        self.collection.update_envelope(old_hash, envelope);
-    }
+        self.envelopes.remove(&old_hash);
 
-    pub fn insert(&mut self, envelope: Envelope) -> &Envelope {
-        let hash = envelope.hash();
-        self.collection.insert(envelope);
-        &self.collection[&hash]
+        self.envelopes.insert(new_hash);
     }
-
-    pub fn insert_reply(&mut self, envelope: &Envelope) {
-        debug!("mailbox insert reply {}", self.name);
-        self.collection.insert_reply(envelope);
-    }
-
-    pub fn remove(&mut self, envelope_hash: EnvelopeHash) {
-        self.collection.remove(envelope_hash);
-        //    debug!("envelope_hash: {}\ncollection:\n{:?}", envelope_hash, self.collection);
+    pub fn remove(&mut self, h: EnvelopeHash) {
+        self.envelopes.remove(&h);
     }
 }
diff --git a/melib/src/mailbox/collection.rs b/melib/src/mailbox/collection.rs
index b53987ea..9298d3ea 100644
--- a/melib/src/mailbox/collection.rs
+++ b/melib/src/mailbox/collection.rs
@@ -1,4 +1,5 @@
 use super::*;
+use crate::mailbox::backends::FolderHash;
 use std::collections::BTreeMap;
 use std::fs;
 use std::io;
@@ -6,22 +7,20 @@ use std::ops::{Deref, DerefMut};
 
 use fnv::FnvHashMap;
 
-/// `Mailbox` represents a folder of mail.
 #[derive(Debug, Clone, Deserialize, Default, Serialize)]
 pub struct Collection {
-    #[serde(skip_serializing, skip_deserializing)]
-    folder: Folder,
     pub envelopes: FnvHashMap<EnvelopeHash, Envelope>,
+    message_ids: FnvHashMap<Vec<u8>, EnvelopeHash>,
     date_index: BTreeMap<UnixTimestamp, EnvelopeHash>,
     subject_index: Option<BTreeMap<String, EnvelopeHash>>,
-    pub threads: Threads,
+    pub threads: FnvHashMap<FolderHash, Threads>,
+    sent_folder: Option<FolderHash>,
 }
 
 impl Drop for Collection {
     fn drop(&mut self) {
-        let cache_dir =
-            xdg::BaseDirectories::with_profile("meli", format!("{}_Thread", self.folder.hash()))
-                .unwrap();
+        let cache_dir: xdg::BaseDirectories =
+            xdg::BaseDirectories::with_profile("meli", "threads".to_string()).unwrap();
         if let Ok(cached) = cache_dir.place_cache_file("threads") {
             /* place result in cache directory */
             let f = match fs::File::create(cached) {
@@ -37,47 +36,24 @@ impl Drop for Collection {
 }
 
 impl Collection {
-    pub fn new(vec: Vec<Envelope>, folder: &Folder) -> Collection {
-        let mut envelopes: FnvHashMap<EnvelopeHash, Envelope> =
-            FnvHashMap::with_capacity_and_hasher(vec.len(), Default::default());
-        for e in vec {
-            envelopes.insert(e.hash(), e);
-        }
+    pub fn new(envelopes: FnvHashMap<EnvelopeHash, Envelope>) -> Collection {
         let date_index = BTreeMap::new();
         let subject_index = None;
+        let message_ids = FnvHashMap::with_capacity_and_hasher(2048, Default::default());
 
         /* Scrap caching for now. When a cached threads file is loaded, we must remove/rehash the
          * thread nodes that shouldn't exist anymore (e.g. because their file moved from /new to
          * /cur, or it was deleted).
          */
-        let threads = Threads::new(&mut envelopes);
-
-        /*let cache_dir =
-                    xdg::BaseDirectories::with_profile("meli", format!("{}_Thread", folder.hash()))
-                        .unwrap();
-                if let Some(cached) = cache_dir.find_cache_file("threads") {
-                    let reader = io::BufReader::new(fs::File::open(cached).unwrap());
-                    let result: result::Result<Threads, _> = bincode::deserialize_from(reader);
-                    let ret = if let Ok(mut cached_t) = result {
-        use std::iter::FromIterator;
-        debug!("loaded cache, our hash set is {:?}\n and the cached one is {:?}", FnvHashSet::from_iter(envelopes.keys().cloned()), cached_t.hash_set);
-                        cached_t.amend(&mut envelopes);
-                        cached_t
-                    } else {
-                        Threads::new(&mut envelopes)
-                    };
-                    ret
-                } else {
-                    Threads::new(&mut envelopes)
-                };
-                */
+        let threads = FnvHashMap::with_capacity_and_hasher(16, Default::default());
 
         Collection {
-            folder: folder.clone(),
             envelopes,
             date_index,
+            message_ids,
             subject_index,
             threads,
+            sent_folder: None,
         }
     }
 
@@ -89,22 +65,34 @@ impl Collection {
         self.envelopes.is_empty()
     }
 
-    pub fn remove(&mut self, envelope_hash: EnvelopeHash) {
+    pub fn remove(&mut self, envelope_hash: EnvelopeHash, folder_hash: FolderHash) {
         debug!("DEBUG: Removing {}", envelope_hash);
         self.envelopes.remove(&envelope_hash);
-        self.threads.remove(envelope_hash, &mut self.envelopes);
+        self.threads
+            .entry(folder_hash)
+            .or_default()
+            .remove(envelope_hash, &mut self.envelopes);
     }
 
-    pub fn rename(&mut self, old_hash: EnvelopeHash, new_hash: EnvelopeHash) {
+    pub fn rename(
+        &mut self,
+        old_hash: EnvelopeHash,
+        new_hash: EnvelopeHash,
+        folder_hash: FolderHash,
+    ) {
         if !self.envelopes.contains_key(&old_hash) {
             return;
         }
         let mut env = self.envelopes.remove(&old_hash).unwrap();
         env.set_hash(new_hash);
+        self.message_ids
+            .insert(env.message_id().raw().to_vec(), new_hash);
         self.envelopes.insert(new_hash, env);
         {
             if self
                 .threads
+                .entry(folder_hash)
+                .or_default()
                 .update_envelope(old_hash, new_hash, &self.envelopes)
                 .is_ok()
             {
@@ -114,17 +102,102 @@ impl Collection {
         /* envelope is not in threads, so insert it */
         let env = self.envelopes.entry(new_hash).or_default() as *mut Envelope;
         unsafe {
-            self.threads.insert(&mut (*env), &self.envelopes);
+            self.threads
+                .entry(folder_hash)
+                .or_default()
+                .insert(&mut (*env), &self.envelopes);
         }
     }
 
-    pub fn update_envelope(&mut self, old_hash: EnvelopeHash, envelope: Envelope) {
+    pub fn merge(
+        &mut self,
+        mut envelopes: FnvHashMap<EnvelopeHash, Envelope>,
+        folder_hash: FolderHash,
+        mailbox: &mut Result<Mailbox>,
+        sent_folder: Option<FolderHash>,
+    ) {
+        self.sent_folder = sent_folder;
+        envelopes.retain(|&h, e| {
+            if self.message_ids.contains_key(e.message_id().raw()) {
+                /* skip duplicates until a better way to handle them is found. */
+                //FIXME
+                if let Ok(mailbox) = mailbox.as_mut() {
+                    mailbox.remove(h);
+                }
+                false
+            } else {
+                self.message_ids.insert(e.message_id().raw().to_vec(), h);
+                true
+            }
+        });
+        let mut threads = Threads::new(&mut envelopes);
+
+        for (h, e) in envelopes {
+            self.envelopes.insert(h, e);
+        }
+        for (t_fh, t) in self.threads.iter_mut() {
+            if self.sent_folder.map(|f| f == folder_hash).unwrap_or(false) {
+                let mut ordered_hash_set = threads
+                    .hash_set
+                    .iter()
+                    .cloned()
+                    .collect::<Vec<EnvelopeHash>>();
+                unsafe {
+                    /* FIXME NLL
+                     * Sorting ordered_hash_set triggers a borrow which should not happen with NLL
+                     * probably */
+                    let envelopes = &self.envelopes as *const FnvHashMap<EnvelopeHash, Envelope>;
+                    ordered_hash_set.sort_by(|a, b| {
+                        (*envelopes)[a]
+                            .date()
+                            .partial_cmp(&(*(envelopes))[b].date())
+                            .unwrap()
+                    });
+                }
+                for h in ordered_hash_set {
+                    t.insert_reply(&mut self.envelopes, h);
+                }
+                continue;
+            }
+            if self.sent_folder.map(|f| f == *t_fh).unwrap_or(false) {
+                let mut ordered_hash_set =
+                    t.hash_set.iter().cloned().collect::<Vec<EnvelopeHash>>();
+                unsafe {
+                    /* FIXME NLL
+                     * Sorting ordered_hash_set triggers a borrow which should not happen with NLL
+                     * probably */
+                    let envelopes = &self.envelopes as *const FnvHashMap<EnvelopeHash, Envelope>;
+                    ordered_hash_set.sort_by(|a, b| {
+                        (*envelopes)[a]
+                            .date()
+                            .partial_cmp(&(*(envelopes))[b].date())
+                            .unwrap()
+                    });
+                }
+                for h in ordered_hash_set {
+                    threads.insert_reply(&mut self.envelopes, h);
+                }
+            }
+        }
+        self.threads.insert(folder_hash, threads);
+    }
+
+    pub fn update(&mut self, old_hash: EnvelopeHash, envelope: Envelope, folder_hash: FolderHash) {
         self.envelopes.remove(&old_hash);
         let new_hash = envelope.hash();
+        self.message_ids
+            .insert(envelope.message_id().raw().to_vec(), new_hash);
         self.envelopes.insert(new_hash, envelope);
+        if self.sent_folder.map(|f| f == folder_hash).unwrap_or(false) {
+            for (_, t) in self.threads.iter_mut() {
+                t.update_envelope(old_hash, new_hash, &self.envelopes);
+            }
+        }
         {
             if self
                 .threads
+                .entry(folder_hash)
+                .or_default()
                 .update_envelope(old_hash, new_hash, &self.envelopes)
                 .is_ok()
             {
@@ -134,26 +207,28 @@ impl Collection {
         /* envelope is not in threads, so insert it */
         let env = self.envelopes.entry(new_hash).or_default() as *mut Envelope;
         unsafe {
-            self.threads.insert(&mut (*env), &self.envelopes);
+            self.threads
+                .entry(folder_hash)
+                .or_default()
+                .insert(&mut (*env), &self.envelopes);
         }
     }
 
-    pub fn insert(&mut self, envelope: Envelope) {
+    pub fn insert(&mut self, envelope: Envelope, folder_hash: FolderHash) -> &Envelope {
         let hash = envelope.hash();
-        debug!("DEBUG: Inserting hash {} in {}", hash, self.folder.name());
+        self.message_ids
+            .insert(envelope.message_id().raw().to_vec(), hash);
         self.envelopes.insert(hash, envelope);
-        let env = self.envelopes.entry(hash).or_default() as *mut Envelope;
-        unsafe {
-            self.threads.insert(&mut (*env), &self.envelopes);
-        }
+        self.threads
+            .entry(folder_hash)
+            .or_default()
+            .insert_reply(&mut self.envelopes, hash);
+        &self.envelopes[&hash]
     }
-    pub(crate) fn insert_reply(&mut self, _envelope: &Envelope) {
-        return;
-        /*
-        //self.insert(envelope);
-        debug!("insert_reply in collections");
-        self.threads.insert_reply(envelope, &mut self.envelopes);
-        */
+    pub fn insert_reply(&mut self, env_hash: EnvelopeHash) {
+        for (_, t) in self.threads.iter_mut() {
+            t.insert_reply(&mut self.envelopes, env_hash);
+        }
     }
 }
 
diff --git a/melib/src/mailbox/thread.rs b/melib/src/mailbox/thread.rs
index ded6b943..79cb1600 100644
--- a/melib/src/mailbox/thread.rs
+++ b/melib/src/mailbox/thread.rs
@@ -32,6 +32,7 @@
  * user having mutable ownership.
  */
 
+use crate::grapheme_clusters::*;
 use crate::mailbox::email::parser::BytesExt;
 use crate::mailbox::email::*;
 use uuid::Uuid;
@@ -49,9 +50,21 @@ use std::str::FromStr;
 
 type Envelopes = FnvHashMap<EnvelopeHash, Envelope>;
 
-#[derive(PartialEq, Hash, Eq, Debug, Copy, Clone, Serialize, Deserialize, Default)]
+#[derive(PartialEq, Hash, Eq, Copy, Clone, Serialize, Deserialize, Default)]
 pub struct ThreadHash(Uuid);
 
+impl fmt::Debug for ThreadHash {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.0.to_string())
+    }
+}
+
+impl fmt::Display for ThreadHash {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.0.to_string())
+    }
+}
+
 impl ThreadHash {
     fn new() -> Self {
         ThreadHash(Uuid::new_v4())
@@ -80,18 +93,24 @@ fn rec_change_children(
     idx: ThreadHash,
     new_root: ThreadHash,
 ) {
-    let entry = b.entry(idx).or_default();
-    entry.thread_group = new_root;
+    b.entry(idx).and_modify(|e| {
+        e.thread_group = new_root;
+    });
 
-    for c in entry.children.clone() {
+    let mut ctr = 0;
+    while ctr < b[&idx].children.len() {
+        let c = b[&idx].children[ctr];
         rec_change_children(b, c, new_root);
+        ctr += 1;
     }
 }
 
 macro_rules! remove_from_parent {
     ($buf:expr, $idx:expr) => {{
+        let mut parent: Option<ThreadHash> = None;
         let entry = $buf.entry($idx).or_default();
         if let Some(p) = entry.parent {
+            parent = Some(p);
             if let Some(pos) = $buf[&p].children.iter().position(|c| *c == $idx) {
                 $buf.entry(p).and_modify(|e| {
                     e.children.remove(pos);
@@ -102,20 +121,22 @@ macro_rules! remove_from_parent {
         $buf.entry($idx).and_modify(|e| e.parent = None);
         rec_change_children($buf, $idx, $idx);
         $buf.entry($idx).and_modify(|e| e.thread_group = $idx);
+        parent
     }};
 }
 
 macro_rules! make {
-    (($p:expr)parent of($c:expr), $buf:expr) => {
-        remove_from_parent!($buf, $c);
+    (($p:expr)parent of($c:expr), $buf:expr) => {{
+        let prev_parent = remove_from_parent!($buf, $c);
         if !($buf[&$p]).children.contains(&$c) {
+            /* Pruned nodes keep their children in case they show up in a later merge, so do not panic
+             * if children exists */
             $buf.entry($p).and_modify(|e| e.children.push($c));
-        } else {
-            panic!();
         }
         $buf.entry($c).and_modify(|e| e.parent = Some($p));
         union($buf, $c, $p);
-    };
+        prev_parent
+        }};
 }
 
 /* Strip common prefixes from subjects */
@@ -225,18 +246,12 @@ impl FromStr for SortOrder {
 /*
  * The thread tree holds the sorted state of the thread nodes */
 
-#[derive(Clone, Deserialize, Serialize)]
+#[derive(Clone, Debug, Deserialize, Serialize)]
 struct ThreadTree {
     id: ThreadHash,
     children: Vec<ThreadTree>,
 }
 
-impl fmt::Debug for ThreadTree {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "")
-    }
-}
-
 impl ThreadTree {
     fn new(id: ThreadHash) -> Self {
         ThreadTree {
@@ -244,6 +259,78 @@ impl ThreadTree {
             children: Vec::new(),
         }
     }
+    fn insert_child(
+        vec: &mut Vec<ThreadTree>,
+        child: ThreadTree,
+        sort: (SortField, SortOrder),
+        buf: &FnvHashMap<ThreadHash, ThreadNode>,
+        envelopes: &Envelopes,
+    ) -> usize {
+        let pos = match sort {
+            (SortField::Date, SortOrder::Asc) => {
+                match vec.binary_search_by(|probe| buf[&probe.id].date.cmp(&buf[&child.id].date)) {
+                    Ok(p) => p,
+                    Err(p) => p,
+                }
+            }
+            (SortField::Date, SortOrder::Desc) => {
+                match vec.binary_search_by(|probe| {
+                    buf[&probe.id].date.cmp(&buf[&child.id].date).reverse()
+                }) {
+                    Ok(p) => p,
+                    Err(p) => p,
+                }
+            }
+            (SortField::Subject, SortOrder::Asc) => {
+                match vec.binary_search_by(|probe| {
+                    match (
+                        buf.get(&probe.id)
+                            .map(|n| n.message.as_ref())
+                            .unwrap_or(None),
+                        buf.get(&child.id)
+                            .map(|n| n.message.as_ref())
+                            .unwrap_or(None),
+                    ) {
+                        (Some(p), Some(c)) => envelopes[p]
+                            .subject()
+                            .split_graphemes()
+                            .cmp(&envelopes[c].subject().split_graphemes()),
+                        (Some(_), None) => Ordering::Greater,
+                        (None, Some(_)) => Ordering::Less,
+                        (None, None) => Ordering::Equal,
+                    }
+                }) {
+                    Ok(p) => p,
+                    Err(p) => p,
+                }
+            }
+            (SortField::Subject, SortOrder::Desc) => {
+                match vec.binary_search_by(|probe| {
+                    match (
+                        buf.get(&probe.id)
+                            .map(|n| n.message.as_ref())
+                            .unwrap_or(None),
+                        buf.get(&child.id)
+                            .map(|n| n.message.as_ref())
+                            .unwrap_or(None),
+                    ) {
+                        (Some(p), Some(c)) => envelopes[c]
+                            .subject()
+                            .split_graphemes()
+                            .cmp(&envelopes[p].subject().split_graphemes()),
+                        (Some(_), None) => Ordering::Less,
+                        (None, Some(_)) => Ordering::Greater,
+                        (None, None) => Ordering::Equal,
+                    }
+                }) {
+                    Ok(p) => p,
+                    Err(p) => p,
+                }
+            }
+        };
+        vec.insert(pos, child);
+        pos
+    }
 }
 
 /* `ThreadsIterator` returns messages according to the sorted order. For example, for the following
@@ -285,7 +372,7 @@ impl<'a> Iterator for ThreadsIterator<'a> {
                 let ret = (
                     self.stack.len(),
                     tree[self.pos].id,
-                    !tree.is_empty() && !self.stack.is_empty() && (self.pos != (tree.len() - 1)),
+                    !self.stack.is_empty() && (self.pos < (tree.len() - 1)),
                 );
                 if !tree[self.pos].children.is_empty() {
                     self.stack.push(self.pos);
@@ -355,6 +442,7 @@ pub struct ThreadNode {
     date: UnixTimestamp,
     indentation: usize,
     show_subject: bool,
+    pruned: bool,
 
     len: usize,
     has_unseen: bool,
@@ -375,6 +463,7 @@ impl Default for ThreadNode {
             date: UnixTimestamp::default(),
             indentation: 0,
             show_subject: true,
+            pruned: false,
 
             len: 0,
             has_unseen: false,
@@ -406,7 +495,7 @@ impl ThreadNode {
     }
 
     pub fn is_empty(&self) -> bool {
-        self.len == 0
+        self.parent.is_none() && self.message.is_none() && self.children.is_empty()
     }
 
     pub fn message(&self) -> Option<EnvelopeHash> {
@@ -453,6 +542,8 @@ pub struct Threads {
     tree: RefCell<Vec<ThreadTree>>,
 
     message_ids: FnvHashMap<Vec<u8>, ThreadHash>,
+    pub message_ids_set: FnvHashSet<Vec<u8>>,
+    pub missing_message_ids: FnvHashSet<Vec<u8>>,
     pub hash_set: FnvHashSet<EnvelopeHash>,
     sort: RefCell<(SortField, SortOrder)>,
     subsort: RefCell<(SortField, SortOrder)>,
@@ -564,31 +655,40 @@ impl Threads {
             /* "If it is an empty container with no children, nuke it." */
             if !thread_nodes[&idx].has_message() && thread_nodes[&idx].children.is_empty() {
                 remove_from_parent!(thread_nodes, idx);
+                thread_nodes.entry(idx).and_modify(|n| n.pruned = true);
                 return true;
             }
 
-            if !thread_nodes[&idx].has_message() && !thread_nodes[&idx].has_parent() {
-                if thread_nodes[&idx].children.len() == 1 {
-                    /* "Do not promote the children if doing so would promote them to the root set
-                     * -- unless there is only one child, in which case, do." */
-                    let child = thread_nodes[&idx].children[0];
-                    root_set.push(child);
-                    remove_from_parent!(thread_nodes, child);
-                    return true; // Pruned
-                }
-            } else if let Some(p) = thread_nodes[&idx].parent {
-                if !thread_nodes[&idx].has_message() {
-                    let orphans = thread_nodes[&idx].children.clone();
-                    for c in orphans {
-                        make!((p) parent of (c), thread_nodes);
+            /*
+                    if !thread_nodes[&idx].has_message() && !thread_nodes[&idx].has_parent() {
+                        if thread_nodes[&idx].children.len() == 1 {
+                            /* "Do not promote the children if doing so would promote them to the root set
+                             * -- unless there is only one child, in which case, do." */
+                            let child = thread_nodes[&idx].children[0];
+                            root_set.push(child);
+                            remove_from_parent!(thread_nodes, child);
+                            thread_nodes.entry(idx).and_modify(|n| {
+                                n.pruned = true;
+                                n.children.push(child);
+                            });
+                            return true; // Pruned
+                        }
+                    } else if let Some(p) = thread_nodes[&idx].parent {
+                        if !thread_nodes[&idx].has_message() {
+                            let orphans = thread_nodes[&idx].children.clone();
+                            for c in &orphans {
+                                make!((p) parent of (*c), thread_nodes);
+                            }
+                            remove_from_parent!(thread_nodes, idx);
+                            /* Keep children in case we happen upon them later and mark it as pruned */
+                            thread_nodes.entry(idx).and_modify(|n| {
+                                n.pruned = true;
+                                n.children = orphans;
+                            });
+                            return true; // Pruned
+                        }
                     }
-                    remove_from_parent!(thread_nodes, idx);
-                    thread_nodes.entry(idx).and_modify(|e| {
-                        e.children.clear();
-                    });
-                    return true; // Pruned
-                }
-            }
+            */
 
             /*  Recurse to children, but keep in mind more children can be added in each iteration
              */
@@ -602,12 +702,12 @@ impl Threads {
                     c_idx += 1;
                 }
             }
-            !thread_nodes[&idx].has_message() && thread_nodes[&idx].children.is_empty()
+            thread_nodes[&idx].pruned
         }
 
         let mut idx = 0;
         loop {
-            if idx == root_set.len() {
+            if idx >= root_set.len() {
                 break;
             }
             if prune(&mut self.thread_nodes, root_set[idx], root_set) {
@@ -618,23 +718,37 @@ impl Threads {
         }
     }
 
-    pub fn new(collection: &mut Envelopes) -> Threads {
+    pub fn prune_tree(&self) {
+        self.tree
+            .borrow_mut()
+            .retain(|c| !self.thread_nodes[&c.id].is_empty());
+    }
+
+    pub fn new(envelopes: &mut Envelopes) -> Threads {
         /* To reconstruct thread information from the mails we need: */
 
         /* a vector to hold thread members */
         let thread_nodes: FnvHashMap<ThreadHash, ThreadNode> = FnvHashMap::with_capacity_and_hasher(
-            (collection.len() as f64 * 1.2) as usize,
+            (envelopes.len() as f64 * 1.2) as usize,
             Default::default(),
         );
         /* A hash table of Message IDs */
         let message_ids: FnvHashMap<Vec<u8>, ThreadHash> =
-            FnvHashMap::with_capacity_and_hasher(collection.len(), Default::default());
+            FnvHashMap::with_capacity_and_hasher(envelopes.len(), Default::default());
+        /* A hash set of Message IDs we haven't encountered yet as an Envelope */
+        let missing_message_ids: FnvHashSet<Vec<u8>> =
+            FnvHashSet::with_capacity_and_hasher(envelopes.len(), Default::default());
+        /* A hash set of Message IDs we have encountered as a MessageID */
+        let message_ids_set: FnvHashSet<Vec<u8>> =
+            FnvHashSet::with_capacity_and_hasher(envelopes.len(), Default::default());
         let hash_set: FnvHashSet<EnvelopeHash> =
-            FnvHashSet::with_capacity_and_hasher(collection.len(), Default::default());
+            FnvHashSet::with_capacity_and_hasher(envelopes.len(), Default::default());
 
         let mut t = Threads {
             thread_nodes,
             message_ids,
+            message_ids_set,
+            missing_message_ids,
             hash_set,
             subsort: RefCell::new((SortField::Subject, SortOrder::Desc)),
 
@@ -642,10 +756,10 @@ impl Threads {
         };
         /* Add each message to message_ids and threads, and link them together according to the
          * References / In-Reply-To headers */
-        t.link_threads(collection);
+        t.link_threads(envelopes);
 
-        t.create_root_set(collection);
-        t.build_collection(collection);
+        t.create_root_set(envelopes);
+        t.build_envelopes(envelopes);
         //for (i, _t) in t.thread_nodes.iter().enumerate() {
         //    if !_t.has_parent() && _t.children.is_empty() && !_t.has_message() {
         //        continue;
@@ -654,8 +768,8 @@ impl Threads {
         //    if let Some(m) = _t.message {
         //        debug!(
         //            "\tmessage: {}\t{}",
-        //            collection[&m].subject(),
-        //            collection[&m].message_id()
+        //            envelopes[&m].subject(),
+        //            envelopes[&m].message_id()
         //        );
         //    } else {
         //        debug!("\tNo message");
@@ -673,7 +787,7 @@ impl Threads {
         //for (i, _t) in t.tree.borrow().iter().enumerate() {
         //    debug!("Tree #{} id {}, children {}", i, _t.id, _t.children.len());
         //    if let Some(m) = t.thread_nodes[_t.id].message {
-        //        debug!("\tmessage: {}", collection[&m].subject());
+        //        debug!("\tmessage: {}", envelopes[&m].subject());
         //    } else {
         //        debug!("\tNo message");
         //    }
@@ -681,10 +795,10 @@ impl Threads {
         t
     }
 
-    fn create_root_set(&mut self, collection: &Envelopes) {
+    fn create_root_set(&mut self, envelopes: &Envelopes) {
         /* Walk over the elements of message_ids, and gather a list of the ThreadNode objects that
          * have no parents. These are the root messages of each thread */
-        let mut root_set: Vec<ThreadHash> = Vec::with_capacity(collection.len());
+        let mut root_set: Vec<ThreadHash> = Vec::with_capacity(envelopes.len());
 
         /* Find the root set */
         for v in self.message_ids.values() {
@@ -693,181 +807,19 @@ impl Threads {
             }
         }
 
-        let mut roots_to_remove: Vec<usize> = Vec::with_capacity(root_set.len());
         /* Prune empty thread nodes */
         self.prune_empty_nodes(&mut root_set);
 
-        /* "Group root set by subject."
-         *
-         * "If any two members of the root set have the same subject, merge them. This is so that
-         * messages which don't have References headers at all still get threaded (to the extent
-         * possible, at least.)"
-         */
-        let mut subject_table: FnvHashMap<Vec<u8>, (bool, ThreadHash)> =
-            FnvHashMap::with_capacity_and_hasher(collection.len(), Default::default());
-
-        for &r in root_set.iter() {
-            /* "Find the subject of that sub-tree": */
-            let (mut subject, mut is_re): (_, bool) = if self.thread_nodes[&r].message.is_some() {
-                /* "If there is a message in the Container, the subject is the subject of that
-                 * message. " */
-                let msg_idx = self.thread_nodes[&r].message.unwrap();
-                let envelope = &collection[&msg_idx];
-                (envelope.subject(), !envelope.references().is_empty())
-            } else {
-                /* "If there is no message in the Container, then the Container will have at least
-                 * one child Container, and that Container will have a message. Use the subject of
-                 * that message instead." */
-                let msg_idx = self.thread_nodes[&self.thread_nodes[&r].children[0]]
-                    .message
-                    .unwrap();
-                let envelope = &collection[&msg_idx];
-                (envelope.subject(), !envelope.references().is_empty())
-            };
-
-            /* "Strip ``Re:'', ``RE:'', ``RE[5]:'', ``Re: Re[4]: Re:'' and so on." */
-            /* References of this envelope can be empty but if the subject contains a ``Re:``
-             * prefix, it's a reply */
-            let mut stripped_subj = subject.to_mut().as_bytes();
-            is_re |= stripped_subj.is_a_reply();
-            stripped_subj.strip_prefixes();
-
-            if stripped_subj.is_empty() {
-                continue;
-            }
-
-            /* "A