diff options
Diffstat (limited to 'src/uidindex.rs')
| -rw-r--r-- | src/uidindex.rs | 281 |
1 files changed, 220 insertions, 61 deletions
diff --git a/src/uidindex.rs b/src/uidindex.rs index ecd52ff..8e4a189 100644 --- a/src/uidindex.rs +++ b/src/uidindex.rs @@ -1,19 +1,28 @@ -use im::OrdMap; -use serde::{Deserialize, Deserializer, Serialize, Serializer}; +use im::{HashMap, HashSet, OrdMap, OrdSet}; +use serde::{de::Error, Deserialize, Deserializer, Serialize, Serializer}; use crate::bayou::*; -use crate::mail_uuid::MailUuid; +use crate::mail_ident::MailIdent; -type ImapUid = u32; -type ImapUidvalidity = u32; +pub type ImapUid = u32; +pub type ImapUidvalidity = u32; +pub type Flag = String; #[derive(Clone)] +/// A UidIndex handles the mutable part of a mailbox +/// It is built by running the event log on it +/// Each applied log generates a new UidIndex by cloning the previous one +/// and applying the event. This is why we use immutable datastructures: +/// they are cheap to clone. pub struct UidIndex { - pub mail_uid: OrdMap<MailUuid, ImapUid>, - pub mail_flags: OrdMap<MailUuid, Vec<String>>, + // Source of trust + pub table: OrdMap<MailIdent, (ImapUid, Vec<Flag>)>, - pub mails_by_uid: OrdMap<ImapUid, MailUuid>, + // Indexes optimized for queries + pub idx_by_uid: OrdMap<ImapUid, MailIdent>, + pub idx_by_flag: FlagIndex, + // Counters pub uidvalidity: ImapUidvalidity, pub uidnext: ImapUid, pub internalseq: ImapUid, @@ -21,40 +30,66 @@ pub struct UidIndex { #[derive(Clone, Serialize, Deserialize, Debug)] pub enum UidIndexOp { - MailAdd(MailUuid, ImapUid, Vec<String>), - MailDel(MailUuid), - FlagAdd(MailUuid, Vec<String>), - FlagDel(MailUuid, Vec<String>), + MailAdd(MailIdent, ImapUid, Vec<Flag>), + MailDel(MailIdent), + FlagAdd(MailIdent, Vec<Flag>), + FlagDel(MailIdent, Vec<Flag>), } impl UidIndex { #[must_use] - pub fn op_mail_add(&self, uuid: MailUuid, flags: Vec<String>) -> UidIndexOp { - UidIndexOp::MailAdd(uuid, self.internalseq, flags) + pub fn op_mail_add(&self, ident: MailIdent, flags: Vec<Flag>) -> UidIndexOp { + UidIndexOp::MailAdd(ident, self.internalseq, flags) } #[must_use] - pub fn op_mail_del(&self, uuid: MailUuid) -> UidIndexOp { - UidIndexOp::MailDel(uuid) + pub fn op_mail_del(&self, ident: MailIdent) -> UidIndexOp { + UidIndexOp::MailDel(ident) } #[must_use] - pub fn op_flag_add(&self, uuid: MailUuid, flags: Vec<String>) -> UidIndexOp { - UidIndexOp::FlagAdd(uuid, flags) + pub fn op_flag_add(&self, ident: MailIdent, flags: Vec<Flag>) -> UidIndexOp { + UidIndexOp::FlagAdd(ident, flags) } #[must_use] - pub fn op_flag_del(&self, uuid: MailUuid, flags: Vec<String>) -> UidIndexOp { - UidIndexOp::FlagDel(uuid, flags) + pub fn op_flag_del(&self, ident: MailIdent, flags: Vec<Flag>) -> UidIndexOp { + UidIndexOp::FlagDel(ident, flags) + } + + // INTERNAL functions to keep state consistent + + fn reg_email(&mut self, ident: MailIdent, uid: ImapUid, flags: &Vec<Flag>) { + // Insert the email in our table + self.table.insert(ident, (uid, flags.clone())); + + // Update the indexes/caches + self.idx_by_uid.insert(uid, ident); + self.idx_by_flag.insert(uid, flags); + } + + fn unreg_email(&mut self, ident: &MailIdent) { + // We do nothing if the mail does not exist + let (uid, flags) = match self.table.get(ident) { + Some(v) => v, + None => return, + }; + + // Delete all cache entries + self.idx_by_uid.remove(uid); + self.idx_by_flag.remove(*uid, flags); + + // Remove from source of trust + self.table.remove(ident); } } impl Default for UidIndex { fn default() -> Self { Self { - mail_flags: OrdMap::new(), - mail_uid: OrdMap::new(), - mails_by_uid: OrdMap::new(), + table: OrdMap::new(), + idx_by_uid: OrdMap::new(), + idx_by_flag: FlagIndex::new(), uidvalidity: 1, uidnext: 1, internalseq: 1, @@ -68,42 +103,53 @@ impl BayouState for UidIndex { fn apply(&self, op: &UidIndexOp) -> Self { let mut new = self.clone(); match op { - UidIndexOp::MailAdd(uuid, uid, flags) => { + UidIndexOp::MailAdd(ident, uid, flags) => { + // Change UIDValidity if there is a conflict if *uid < new.internalseq { new.uidvalidity += new.internalseq - *uid; } + + // Assign the real uid of the email let new_uid = new.internalseq; - if let Some(prev_uid) = new.mail_uid.get(uuid) { - new.mails_by_uid.remove(prev_uid); - } else { - new.mail_flags.insert(*uuid, flags.clone()); - } - new.mails_by_uid.insert(new_uid, *uuid); - new.mail_uid.insert(*uuid, new_uid); + // Delete the previous entry if any. + // Our proof has no assumption on `ident` uniqueness, + // so we must handle this case even it is very unlikely + // In this case, we overwrite the email. + // Note: assigning a new UID is mandatory. + new.unreg_email(ident); + + // We record our email and update ou caches + new.reg_email(*ident, new_uid, flags); + // Update counters new.internalseq += 1; new.uidnext = new.internalseq; } - UidIndexOp::MailDel(uuid) => { - if let Some(uid) = new.mail_uid.get(uuid) { - new.mails_by_uid.remove(uid); - new.mail_uid.remove(uuid); - new.mail_flags.remove(uuid); - } + UidIndexOp::MailDel(ident) => { + // If the email is known locally, we remove its references in all our indexes + new.unreg_email(ident); + + // We update the counter new.internalseq += 1; } - UidIndexOp::FlagAdd(uuid, new_flags) => { - let mail_flags = new.mail_flags.entry(*uuid).or_insert(vec![]); - for flag in new_flags { - if !mail_flags.contains(flag) { - mail_flags.push(flag.to_string()); - } + UidIndexOp::FlagAdd(ident, new_flags) => { + if let Some((uid, existing_flags)) = new.table.get_mut(ident) { + // Add flags to the source of trust and the cache + let mut to_add: Vec<Flag> = new_flags + .iter() + .filter(|f| !existing_flags.contains(f)) + .cloned() + .collect(); + new.idx_by_flag.insert(*uid, &to_add); + existing_flags.append(&mut to_add); } } - UidIndexOp::FlagDel(uuid, rm_flags) => { - if let Some(mail_flags) = new.mail_flags.get_mut(uuid) { - mail_flags.retain(|x| !rm_flags.contains(x)); + UidIndexOp::FlagDel(ident, rm_flags) => { + if let Some((uid, existing_flags)) = new.table.get_mut(ident) { + // Remove flags from the source of trust and the cache + existing_flags.retain(|x| !rm_flags.contains(x)); + new.idx_by_flag.remove(*uid, rm_flags); } } } @@ -111,11 +157,34 @@ impl BayouState for UidIndex { } } +// ---- FlagIndex implementation ---- +#[derive(Clone)] +pub struct FlagIndex(HashMap<Flag, OrdSet<ImapUid>>); + +impl FlagIndex { + fn new() -> Self { + Self(HashMap::new()) + } + fn insert(&mut self, uid: ImapUid, flags: &Vec<Flag>) { + flags.iter().for_each(|flag| { + self.0 + .entry(flag.clone()) + .or_insert(OrdSet::new()) + .insert(uid); + }); + } + fn remove(&mut self, uid: ImapUid, flags: &Vec<Flag>) -> () { + flags.iter().for_each(|flag| { + self.0.get_mut(flag).and_then(|set| set.remove(&uid)); + }); + } +} + // ---- CUSTOM SERIALIZATION AND DESERIALIZATION ---- #[derive(Serialize, Deserialize)] struct UidIndexSerializedRepr { - mails: Vec<(ImapUid, MailUuid, Vec<String>)>, + mails: Vec<(ImapUid, MailIdent, Vec<Flag>)>, uidvalidity: ImapUidvalidity, uidnext: ImapUid, internalseq: ImapUid, @@ -129,19 +198,17 @@ impl<'de> Deserialize<'de> for UidIndex { let val: UidIndexSerializedRepr = UidIndexSerializedRepr::deserialize(d)?; let mut uidindex = UidIndex { - mail_flags: OrdMap::new(), - mail_uid: OrdMap::new(), - mails_by_uid: OrdMap::new(), + table: OrdMap::new(), + idx_by_uid: OrdMap::new(), + idx_by_flag: FlagIndex::new(), uidvalidity: val.uidvalidity, uidnext: val.uidnext, internalseq: val.internalseq, }; - for (uid, uuid, flags) in val.mails { - uidindex.mail_flags.insert(uuid, flags); - uidindex.mail_uid.insert(uuid, uid); - uidindex.mails_by_uid.insert(uid, uuid); - } + val.mails + .iter() + .for_each(|(u, i, f)| uidindex.reg_email(*i, *u, f)); Ok(uidindex) } @@ -153,12 +220,8 @@ impl Serialize for UidIndex { S: Serializer, { let mut mails = vec![]; - for (uid, uuid) in self.mails_by_uid.iter() { - mails.push(( - *uid, - *uuid, - self.mail_flags.get(uuid).cloned().unwrap_or_default(), - )); + for (ident, (uid, flags)) in self.table.iter() { + mails.push((*uid, *ident, flags.clone())); } let val = UidIndexSerializedRepr { @@ -171,3 +234,99 @@ impl Serialize for UidIndex { val.serialize(serializer) } } + +// ---- TESTS ---- + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_uidindex() { + let mut state = UidIndex::default(); + + // Add message 1 + { + let m = MailIdent([0x01; 24]); + let f = vec!["\\Recent".to_string(), "\\Archive".to_string()]; + let ev = state.op_mail_add(m, f); + state = state.apply(&ev); + + // Early checks + assert_eq!(state.table.len(), 1); + let (uid, flags) = state.table.get(&m).unwrap(); + assert_eq!(*uid, 1); + assert_eq!(flags.len(), 2); + let ident = state.idx_by_uid.get(&1).unwrap(); + assert_eq!(&m, ident); + let recent = state.idx_by_flag.0.get("\\Recent").unwrap(); + assert_eq!(recent.len(), 1); + assert_eq!(recent.iter().next().unwrap(), &1); + assert_eq!(state.uidnext, 2); + assert_eq!(state.uidvalidity, 1); + } + + // Add message 2 + { + let m = MailIdent([0x02; 24]); + let f = vec!["\\Seen".to_string(), "\\Archive".to_string()]; + let ev = state.op_mail_add(m, f); + state = state.apply(&ev); + + let archive = state.idx_by_flag.0.get("\\Archive").unwrap(); + assert_eq!(archive.len(), 2); + } + + // Add flags to message 1 + { + let m = MailIdent([0x01; 24]); + let f = vec!["Important".to_string(), "$cl_1".to_string()]; + let ev = state.op_flag_add(m, f); + state = state.apply(&ev); + } + + // Delete flags from message 1 + { + let m = MailIdent([0x01; 24]); + let f = vec!["\\Recent".to_string()]; + let ev = state.op_flag_del(m, f); + state = state.apply(&ev); + + let archive = state.idx_by_flag.0.get("\\Archive").unwrap(); + assert_eq!(archive.len(), 2); + } + + // Delete message 2 + { + let m = MailIdent([0x02; 24]); + let ev = state.op_mail_del(m); + state = state.apply(&ev); + + let archive = state.idx_by_flag.0.get("\\Archive").unwrap(); + assert_eq!(archive.len(), 1); + } + + // Add a message 3 concurrent to message 1 (trigger a uid validity change) + { + let m = MailIdent([0x03; 24]); + let f = vec!["\\Archive".to_string(), "\\Recent".to_string()]; + let ev = UidIndexOp::MailAdd(m, 1, f); + state = state.apply(&ev); + } + + // Checks + { + assert_eq!(state.table.len(), 2); + assert!(state.uidvalidity > 1); + + let (last_uid, ident) = state.idx_by_uid.get_max().unwrap(); + assert_eq!(ident, &MailIdent([0x03; 24])); + + let archive = state.idx_by_flag.0.get("\\Archive").unwrap(); + assert_eq!(archive.len(), 2); + let mut iter = archive.iter(); + assert_eq!(iter.next().unwrap(), &1); + assert_eq!(iter.next().unwrap(), last_uid); + } + } +} |