diff options
Diffstat (limited to 'aero-proto/src/imap/index.rs')
| -rw-r--r-- | aero-proto/src/imap/index.rs | 211 |
1 files changed, 211 insertions, 0 deletions
diff --git a/aero-proto/src/imap/index.rs b/aero-proto/src/imap/index.rs new file mode 100644 index 0000000..afe6991 --- /dev/null +++ b/aero-proto/src/imap/index.rs @@ -0,0 +1,211 @@ +use std::num::{NonZeroU32, NonZeroU64}; + +use anyhow::{anyhow, Result}; +use imap_codec::imap_types::sequence::{SeqOrUid, Sequence, SequenceSet}; + +use aero_collections::mail::uidindex::{ImapUid, ModSeq, UidIndex}; +use aero_collections::unique_ident::UniqueIdent; + +pub struct Index<'a> { + pub imap_index: Vec<MailIndex<'a>>, + pub internal: &'a UidIndex, +} +impl<'a> Index<'a> { + pub fn new(internal: &'a UidIndex) -> Result<Self> { + let imap_index = internal + .idx_by_uid + .iter() + .enumerate() + .map(|(i_enum, (&uid, &uuid))| { + let (_, modseq, flags) = internal + .table + .get(&uuid) + .ok_or(anyhow!("mail is missing from index"))?; + let i_int: u32 = (i_enum + 1).try_into()?; + let i: NonZeroU32 = i_int.try_into()?; + + Ok(MailIndex { + i, + uid, + uuid, + modseq: *modseq, + flags, + }) + }) + .collect::<Result<Vec<_>>>()?; + + Ok(Self { + imap_index, + internal, + }) + } + + pub fn last(&'a self) -> Option<&'a MailIndex<'a>> { + self.imap_index.last() + } + + /// Fetch mail descriptors based on a sequence of UID + /// + /// Complexity analysis: + /// - Sort is O(n * log n) where n is the number of uid generated by the sequence + /// - Finding the starting point in the index O(log m) where m is the size of the mailbox + /// While n =< m, it's not clear if the difference is big or not. + /// + /// For now, the algorithm tries to be fast for small values of n, + /// as it is what is expected by clients. + /// + /// So we assume for our implementation that : n << m. + /// It's not true for full mailbox searches for example... + pub fn fetch_on_uid(&'a self, sequence_set: &SequenceSet) -> Vec<&'a MailIndex<'a>> { + if self.imap_index.is_empty() { + return vec![]; + } + let largest = self.last().expect("The mailbox is not empty").uid; + let mut unroll_seq = sequence_set.iter(largest).collect::<Vec<_>>(); + unroll_seq.sort(); + + let start_seq = match unroll_seq.iter().next() { + Some(elem) => elem, + None => return vec![], + }; + + // Quickly jump to the right point in the mailbox vector O(log m) instead + // of iterating one by one O(m). Works only because both unroll_seq & imap_index are sorted per uid. + let mut imap_idx = { + let start_idx = self + .imap_index + .partition_point(|mail_idx| &mail_idx.uid < start_seq); + &self.imap_index[start_idx..] + }; + + let mut acc = vec![]; + for wanted_uid in unroll_seq.iter() { + // Slide the window forward as long as its first element is lower than our wanted uid. + let start_idx = match imap_idx.iter().position(|midx| &midx.uid >= wanted_uid) { + Some(v) => v, + None => break, + }; + imap_idx = &imap_idx[start_idx..]; + + // If the beginning of our new window is the uid we want, we collect it + if &imap_idx[0].uid == wanted_uid { + acc.push(&imap_idx[0]); + } + } + + acc + } + + pub fn fetch_on_id(&'a self, sequence_set: &SequenceSet) -> Result<Vec<&'a MailIndex<'a>>> { + if self.imap_index.is_empty() { + return Ok(vec![]); + } + let largest = NonZeroU32::try_from(self.imap_index.len() as u32)?; + let mut acc = sequence_set + .iter(largest) + .map(|wanted_id| { + self.imap_index + .get((wanted_id.get() as usize) - 1) + .ok_or(anyhow!("Mail not found")) + }) + .collect::<Result<Vec<_>>>()?; + + // Sort the result to be consistent with UID + acc.sort_by(|a, b| a.i.cmp(&b.i)); + + Ok(acc) + } + + pub fn fetch( + self: &'a Index<'a>, + sequence_set: &SequenceSet, + by_uid: bool, + ) -> Result<Vec<&'a MailIndex<'a>>> { + match by_uid { + true => Ok(self.fetch_on_uid(sequence_set)), + _ => self.fetch_on_id(sequence_set), + } + } + + pub fn fetch_changed_since( + self: &'a Index<'a>, + sequence_set: &SequenceSet, + maybe_modseq: Option<NonZeroU64>, + by_uid: bool, + ) -> Result<Vec<&'a MailIndex<'a>>> { + let raw = self.fetch(sequence_set, by_uid)?; + let res = match maybe_modseq { + Some(pit) => raw.into_iter().filter(|midx| midx.modseq > pit).collect(), + None => raw, + }; + + Ok(res) + } + + pub fn fetch_unchanged_since( + self: &'a Index<'a>, + sequence_set: &SequenceSet, + maybe_modseq: Option<NonZeroU64>, + by_uid: bool, + ) -> Result<(Vec<&'a MailIndex<'a>>, Vec<&'a MailIndex<'a>>)> { + let raw = self.fetch(sequence_set, by_uid)?; + let res = match maybe_modseq { + Some(pit) => raw.into_iter().partition(|midx| midx.modseq <= pit), + None => (raw, vec![]), + }; + + Ok(res) + } +} + +#[derive(Clone, Debug)] +pub struct MailIndex<'a> { + pub i: NonZeroU32, + pub uid: ImapUid, + pub uuid: UniqueIdent, + pub modseq: ModSeq, + pub flags: &'a Vec<String>, +} + +impl<'a> MailIndex<'a> { + // The following functions are used to implement the SEARCH command + pub fn is_in_sequence_i(&self, seq: &Sequence) -> bool { + match seq { + Sequence::Single(SeqOrUid::Asterisk) => true, + Sequence::Single(SeqOrUid::Value(target)) => target == &self.i, + Sequence::Range(SeqOrUid::Asterisk, SeqOrUid::Value(x)) + | Sequence::Range(SeqOrUid::Value(x), SeqOrUid::Asterisk) => x <= &self.i, + Sequence::Range(SeqOrUid::Value(x1), SeqOrUid::Value(x2)) => { + if x1 < x2 { + x1 <= &self.i && &self.i <= x2 + } else { + x1 >= &self.i && &self.i >= x2 + } + } + Sequence::Range(SeqOrUid::Asterisk, SeqOrUid::Asterisk) => true, + } + } + + pub fn is_in_sequence_uid(&self, seq: &Sequence) -> bool { + match seq { + Sequence::Single(SeqOrUid::Asterisk) => true, + Sequence::Single(SeqOrUid::Value(target)) => target == &self.uid, + Sequence::Range(SeqOrUid::Asterisk, SeqOrUid::Value(x)) + | Sequence::Range(SeqOrUid::Value(x), SeqOrUid::Asterisk) => x <= &self.uid, + Sequence::Range(SeqOrUid::Value(x1), SeqOrUid::Value(x2)) => { + if x1 < x2 { + x1 <= &self.uid && &self.uid <= x2 + } else { + x1 >= &self.uid && &self.uid >= x2 + } + } + Sequence::Range(SeqOrUid::Asterisk, SeqOrUid::Asterisk) => true, + } + } + + pub fn is_flag_set(&self, flag: &str) -> bool { + self.flags + .iter() + .any(|candidate| candidate.as_str() == flag) + } +} |