1use core::{cmp::Ordering, fmt, mem, num::NonZeroU32};
62
63use alloc::{collections::BTreeMap, string::String, string::ToString, vec::Vec};
64
65use imap_codec::{
66 CommandCodec,
67 fragmentizer::Fragmentizer,
68 imap_types::{
69 command::{Command, CommandBody},
70 core::{Charset, TagGenerator, Vec1},
71 extensions::sort::{SortCriterion, SortKey},
72 fetch::{MacroOrMessageDataItemNames, MessageDataItem, MessageDataItemName},
73 response::{Data, StatusKind, Tagged},
74 search::SearchKey,
75 sequence::SequenceSet,
76 },
77};
78use log::{debug, trace};
79use thiserror::Error;
80
81use crate::{
82 coroutine::*,
83 imap_try,
84 rfc3501::{fetch::*, search::*},
85 send::*,
86};
87
88const MAX_CHUNK: usize = 255;
90
91#[derive(Clone, Debug, Error)]
93pub enum ImapMessageSortError {
94 #[error("IMAP SORT failed: NO {0}")]
96 No(String),
97 #[error("IMAP SORT failed: BAD {0}")]
99 Bad(String),
100 #[error("IMAP SORT failed: BYE {0}")]
102 Bye(String),
103 #[error("IMAP SORT failed: server did not return a tagged response")]
105 MissingTagged,
106 #[error("IMAP SORT failed: server did not return any data")]
108 MissingData,
109 #[error("IMAP SORT failed: could not build the fetch sequence set")]
111 InvalidSequenceSet,
112 #[error("IMAP SORT failed: {0}")]
114 Send(#[from] ImapSendError),
115 #[error(transparent)]
117 Search(#[from] ImapMessageSearchError),
118 #[error(transparent)]
120 Fetch(#[from] ImapMessageFetchError),
121}
122
123#[derive(Clone, Debug, Default, Eq, PartialEq)]
125pub struct ImapMessageSortOptions {
126 pub uid: bool,
128 pub fallback: bool,
134}
135
136pub struct ImapMessageSort {
142 state: State,
143 uid: bool,
144 sort_criteria: Vec1<SortCriterion>,
145 items: Vec<MessageDataItemName<'static>>,
146 remaining: Vec<NonZeroU32>,
147 fetched: BTreeMap<NonZeroU32, Vec1<MessageDataItem<'static>>>,
148}
149
150impl ImapMessageSort {
151 pub fn new(
157 sort_criteria: Vec1<SortCriterion>,
158 search_criteria: Vec1<SearchKey<'static>>,
159 opts: ImapMessageSortOptions,
160 ) -> Self {
161 let items = fetch_items(&sort_criteria, opts.uid);
162
163 let state = if opts.fallback {
164 trace!("using IMAP SORT fallback");
165 let search =
166 ImapMessageSearch::new(search_criteria, ImapMessageSearchOptions { uid: opts.uid });
167 State::Search(search)
168 } else {
169 let command = Command {
170 tag: TagGenerator::new().generate(),
171 body: CommandBody::Sort {
172 sort_criteria: sort_criteria.clone(),
173 charset: Charset::try_from("UTF-8").unwrap(),
174 search_criteria,
175 uid: opts.uid,
176 },
177 };
178
179 trace!("send IMAP command {command:?}");
180
181 State::Sort(ImapSend::new(CommandCodec::new(), command))
182 };
183
184 Self {
185 state,
186 uid: opts.uid,
187 sort_criteria,
188 items,
189 remaining: Vec::new(),
190 fetched: BTreeMap::new(),
191 }
192 }
193
194 fn next_fetch(&mut self) -> Result<Option<ImapMessageFetch>, ImapMessageSortError> {
197 if self.remaining.is_empty() {
198 return Ok(None);
199 }
200
201 let take = self.remaining.len().min(MAX_CHUNK);
202 let chunk: Vec<NonZeroU32> = self.remaining.drain(..take).collect();
203 let sequence_set =
204 SequenceSet::try_from(chunk).map_err(|_| ImapMessageSortError::InvalidSequenceSet)?;
205 let items = MacroOrMessageDataItemNames::MessageDataItemNames(self.items.clone());
206
207 Ok(Some(ImapMessageFetch::new(
208 sequence_set,
209 items,
210 ImapMessageFetchOptions {
211 uid: self.uid,
212 ..Default::default()
213 },
214 )))
215 }
216
217 fn local_sort(&mut self) -> Vec<NonZeroU32> {
219 let uid = self.uid;
220 let criteria = self.sort_criteria.clone();
221 let mut entries: Vec<(NonZeroU32, Vec1<MessageDataItem<'static>>)> =
222 mem::take(&mut self.fetched).into_iter().collect();
223
224 entries.sort_by(|(_, a), (_, b)| {
225 for criterion in criteria.as_ref() {
226 let mut cmp = cmp_fetch_items(&criterion.key, a, b);
227
228 if criterion.reverse {
229 cmp = cmp.reverse();
230 }
231
232 if cmp.is_ne() {
233 return cmp;
234 }
235 }
236
237 cmp_fetch_items(&SortKey::Date, a, b)
238 });
239
240 entries
241 .into_iter()
242 .filter_map(|(seq, items)| {
243 if uid {
244 items.as_ref().iter().find_map(|item| match item {
245 MessageDataItem::Uid(uid) => Some(*uid),
246 _ => None,
247 })
248 } else {
249 Some(seq)
250 }
251 })
252 .collect()
253 }
254}
255
256impl ImapCoroutine for ImapMessageSort {
257 type Yield = ImapYield;
258 type Return = Result<Vec<NonZeroU32>, ImapMessageSortError>;
259
260 fn resume(
261 &mut self,
262 fragmentizer: &mut Fragmentizer,
263 arg: Option<&[u8]>,
264 ) -> ImapCoroutineState<Self::Yield, Self::Return> {
265 loop {
266 match &mut self.state {
267 State::Sort(send) => {
268 let out = imap_try!(send, fragmentizer, arg);
269
270 if let Some(bye) = out.bye {
271 let err = ImapMessageSortError::Bye(bye.text.to_string());
272 return ImapCoroutineState::Complete(Err(err));
273 }
274
275 let Some(Tagged { body, .. }) = out.tagged else {
276 let err = ImapMessageSortError::MissingTagged;
277 return ImapCoroutineState::Complete(Err(err));
278 };
279
280 let mut ids = None;
281
282 for data in out.data {
283 if let Data::Sort(sort_ids, _) = data {
284 ids = Some(sort_ids);
285 }
286 }
287
288 return match body.kind {
289 StatusKind::Ok => match ids {
290 Some(ids) => ImapCoroutineState::Complete(Ok(ids)),
291 None => {
292 ImapCoroutineState::Complete(Err(ImapMessageSortError::MissingData))
293 }
294 },
295 StatusKind::No => {
296 let err = ImapMessageSortError::No(body.text.to_string());
297 ImapCoroutineState::Complete(Err(err))
298 }
299 StatusKind::Bad => {
300 let err = ImapMessageSortError::Bad(body.text.to_string());
301 ImapCoroutineState::Complete(Err(err))
302 }
303 };
304 }
305 State::Search(search) => {
306 self.remaining = imap_try!(search, fragmentizer, arg);
307
308 match self.next_fetch() {
309 Ok(Some(fetch)) => {
310 self.state = State::Fetch(fetch);
311 debug!("{}", self.state);
312 }
313 Ok(None) => return ImapCoroutineState::Complete(Ok(Vec::new())),
314 Err(err) => return ImapCoroutineState::Complete(Err(err)),
315 }
316 }
317 State::Fetch(fetch) => {
318 let map = imap_try!(fetch, fragmentizer, arg);
319 self.fetched.extend(map);
320
321 match self.next_fetch() {
322 Ok(Some(fetch)) => {
323 self.state = State::Fetch(fetch);
324 debug!("{}", self.state);
325 }
326 Ok(None) => return ImapCoroutineState::Complete(Ok(self.local_sort())),
327 Err(err) => return ImapCoroutineState::Complete(Err(err)),
328 }
329 }
330 }
331 }
332 }
333}
334
335enum State {
336 Sort(ImapSend<CommandCodec>),
337 Search(ImapMessageSearch),
338 Fetch(ImapMessageFetch),
339}
340
341impl fmt::Display for State {
342 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
343 match self {
344 Self::Sort(_) => f.write_str("send sort command"),
345 Self::Search(_) => f.write_str("search for candidates"),
346 Self::Fetch(_) => f.write_str("fetch sort keys"),
347 }
348 }
349}
350
351fn fetch_items(
357 sort_criteria: &Vec1<SortCriterion>,
358 uid: bool,
359) -> Vec<MessageDataItemName<'static>> {
360 let mut items: Vec<MessageDataItemName<'static>> = Vec::new();
361
362 for criterion in sort_criteria.as_ref() {
363 let item = match &criterion.key {
364 SortKey::Arrival => Some(MessageDataItemName::InternalDate),
365 SortKey::Size => Some(MessageDataItemName::Rfc822Size),
366 SortKey::Cc | SortKey::Date | SortKey::From | SortKey::Subject | SortKey::To => {
367 Some(MessageDataItemName::Envelope)
368 }
369 SortKey::DisplayFrom | SortKey::DisplayTo => None,
370 };
371
372 if let Some(item) = item {
373 if !items.contains(&item) {
374 items.push(item);
375 }
376 }
377 }
378
379 if !items.contains(&MessageDataItemName::Envelope) {
380 items.push(MessageDataItemName::Envelope);
381 }
382
383 if uid && !items.contains(&MessageDataItemName::Uid) {
384 items.push(MessageDataItemName::Uid);
385 }
386
387 items
388}
389
390fn cmp_fetch_items(
396 key: &SortKey,
397 a: &Vec1<MessageDataItem<'static>>,
398 b: &Vec1<MessageDataItem<'static>>,
399) -> Ordering {
400 match key {
401 SortKey::Arrival => {
402 let a = a.as_ref().iter().find_map(|item| match item {
403 MessageDataItem::InternalDate(date) => Some(date.as_ref()),
404 _ => None,
405 });
406 let b = b.as_ref().iter().find_map(|item| match item {
407 MessageDataItem::InternalDate(date) => Some(date.as_ref()),
408 _ => None,
409 });
410 a.cmp(&b)
411 }
412 SortKey::Size => {
413 let a = a.as_ref().iter().find_map(|item| match item {
414 MessageDataItem::Rfc822Size(size) => Some(size),
415 _ => None,
416 });
417 let b = b.as_ref().iter().find_map(|item| match item {
418 MessageDataItem::Rfc822Size(size) => Some(size),
419 _ => None,
420 });
421 a.cmp(&b)
422 }
423 SortKey::Date => {
424 let a = a.as_ref().iter().find_map(|item| match item {
425 MessageDataItem::Envelope(envelope) => envelope.date.0.as_ref().map(AsRef::as_ref),
426 _ => None,
427 });
428 let b = b.as_ref().iter().find_map(|item| match item {
429 MessageDataItem::Envelope(envelope) => envelope.date.0.as_ref().map(AsRef::as_ref),
430 _ => None,
431 });
432 a.cmp(&b)
433 }
434 SortKey::Subject => {
435 let a = a.as_ref().iter().find_map(|item| match item {
436 MessageDataItem::Envelope(envelope) => {
437 envelope.subject.0.as_ref().map(AsRef::as_ref)
438 }
439 _ => None,
440 });
441 let b = b.as_ref().iter().find_map(|item| match item {
442 MessageDataItem::Envelope(envelope) => {
443 envelope.subject.0.as_ref().map(AsRef::as_ref)
444 }
445 _ => None,
446 });
447 a.cmp(&b)
448 }
449 SortKey::Cc | SortKey::From | SortKey::To | SortKey::DisplayFrom | SortKey::DisplayTo => {
450 Ordering::Equal
451 }
452 }
453}
454
455#[cfg(test)]
456mod tests {
457 use core::str;
458
459 use alloc::{borrow::ToOwned, format, vec, vec::Vec};
460
461 use crate::rfc5256::sort::*;
462
463 fn arrival() -> Vec1<SortCriterion> {
464 Vec1::try_from(vec![SortCriterion {
465 reverse: false,
466 key: SortKey::Arrival,
467 }])
468 .expect("one sort criterion")
469 }
470
471 fn search_criteria() -> Vec1<SearchKey<'static>> {
472 Vec1::try_from(vec![SearchKey::All]).expect("one search criterion")
473 }
474
475 fn first_word(line: &str) -> &str {
476 line.split_whitespace()
477 .next()
478 .expect("first whitespace-separated token")
479 }
480
481 #[test]
482 fn sort_success_returns_ids() {
483 let mut sort = ImapMessageSort::new(
484 arrival(),
485 search_criteria(),
486 ImapMessageSortOptions::default(),
487 );
488 let mut frag = Fragmentizer::new(50 * 1024 * 1024);
489
490 let bytes = wants_write(&mut sort, &mut frag, None);
491 let line = str::from_utf8(&bytes).expect("utf8 command");
492 let tag = first_word(line).to_owned();
493 assert!(line.contains("SORT "));
494 assert!(!line.contains("SEARCH"));
495
496 wants_read(&mut sort, &mut frag, None);
497
498 let reply = format!("* SORT 3 1 2\r\n{tag} OK SORT completed\r\n");
499 let ids = complete_ok(&mut sort, &mut frag, Some(reply.as_bytes()));
500 assert_eq!(
501 vec![nz(3), nz(1), nz(2)],
502 ids,
503 "server order preserved verbatim"
504 );
505 }
506
507 #[test]
508 fn sort_uid_variant_sends_uid_sort() {
509 let mut sort = ImapMessageSort::new(
510 arrival(),
511 search_criteria(),
512 ImapMessageSortOptions {
513 uid: true,
514 ..Default::default()
515 },
516 );
517 let mut frag = Fragmentizer::new(50 * 1024 * 1024);
518
519 let bytes = wants_write(&mut sort, &mut frag, None);
520 let line = str::from_utf8(&bytes).expect("utf8 command");
521 assert!(line.contains("UID SORT "));
522 }
523
524 #[test]
525 fn sort_missing_data_returns_missing_data_error() {
526 let mut sort = ImapMessageSort::new(
527 arrival(),
528 search_criteria(),
529 ImapMessageSortOptions::default(),
530 );
531 let mut frag = Fragmentizer::new(50 * 1024 * 1024);
532
533 let bytes = wants_write(&mut sort, &mut frag, None);
534 let tag = first_word(str::from_utf8(&bytes).expect("utf8 command")).to_owned();
535
536 wants_read(&mut sort, &mut frag, None);
537
538 let reply = format!("{tag} OK SORT completed\r\n");
539 let err = complete_err(&mut sort, &mut frag, reply.as_bytes());
540 assert!(matches!(err, ImapMessageSortError::MissingData));
541 }
542
543 #[test]
544 fn sort_tagged_no_returns_no_error() {
545 let mut sort = ImapMessageSort::new(
546 arrival(),
547 search_criteria(),
548 ImapMessageSortOptions::default(),
549 );
550 let mut frag = Fragmentizer::new(50 * 1024 * 1024);
551
552 let bytes = wants_write(&mut sort, &mut frag, None);
553 let tag = first_word(str::from_utf8(&bytes).expect("utf8 command")).to_owned();
554
555 wants_read(&mut sort, &mut frag, None);
556
557 let reply = format!("{tag} NO no mailbox selected\r\n");
558 let err = complete_err(&mut sort, &mut frag, reply.as_bytes());
559 let ImapMessageSortError::No(text) = err else {
560 panic!("expected ImapMessageSortError::No, got {err:?}");
561 };
562 assert_eq!(text, "no mailbox selected");
563 }
564
565 #[test]
566 fn fallback_searches_then_fetches_then_sorts() {
567 let mut sort = ImapMessageSort::new(
568 arrival(),
569 search_criteria(),
570 ImapMessageSortOptions {
571 uid: true,
572 fallback: true,
573 },
574 );
575 let mut frag = Fragmentizer::new(50 * 1024 * 1024);
576
577 let bytes = wants_write(&mut sort, &mut frag, None);
578 let line = str::from_utf8(&bytes).expect("utf8 command");
579 let search_tag = first_word(line).to_owned();
580 assert!(line.contains("UID SEARCH"));
581
582 wants_read(&mut sort, &mut frag, None);
583
584 let search_reply = format!("* SEARCH 1 2\r\n{search_tag} OK SEARCH completed\r\n");
585 let bytes = wants_write(&mut sort, &mut frag, Some(search_reply.as_bytes()));
586 let line = str::from_utf8(&bytes).expect("utf8 command");
587 let fetch_tag = first_word(line).to_owned();
588 assert!(line.contains("UID FETCH"));
589 assert!(line.contains("INTERNALDATE"));
590 assert!(line.contains("UID"));
591
592 wants_read(&mut sort, &mut frag, None);
593
594 let fetch_reply = format!(
597 "* 1 FETCH (UID 1 INTERNALDATE \"02-Feb-2021 00:00:00 +0000\")\r\n\
598 * 2 FETCH (UID 2 INTERNALDATE \"01-Jan-2020 00:00:00 +0000\")\r\n\
599 {fetch_tag} OK FETCH completed\r\n"
600 );
601 let ids = complete_ok(&mut sort, &mut frag, Some(fetch_reply.as_bytes()));
602 assert_eq!(vec![nz(2), nz(1)], ids);
603 }
604
605 #[test]
606 fn fallback_reverse_flips_order() {
607 let criteria = Vec1::try_from(vec![SortCriterion {
608 reverse: true,
609 key: SortKey::Arrival,
610 }])
611 .expect("one criterion");
612 let mut sort = ImapMessageSort::new(
613 criteria,
614 search_criteria(),
615 ImapMessageSortOptions {
616 uid: true,
617 fallback: true,
618 },
619 );
620 let mut frag = Fragmentizer::new(50 * 1024 * 1024);
621
622 let bytes = wants_write(&mut sort, &mut frag, None);
623 let search_tag = first_word(str::from_utf8(&bytes).expect("utf8 command")).to_owned();
624 wants_read(&mut sort, &mut frag, None);
625
626 let search_reply = format!("* SEARCH 1 2\r\n{search_tag} OK SEARCH completed\r\n");
627 let bytes = wants_write(&mut sort, &mut frag, Some(search_reply.as_bytes()));
628 let fetch_tag = first_word(str::from_utf8(&bytes).expect("utf8 command")).to_owned();
629 wants_read(&mut sort, &mut frag, None);
630
631 let fetch_reply = format!(
632 "* 1 FETCH (UID 1 INTERNALDATE \"02-Feb-2021 00:00:00 +0000\")\r\n\
633 * 2 FETCH (UID 2 INTERNALDATE \"01-Jan-2020 00:00:00 +0000\")\r\n\
634 {fetch_tag} OK FETCH completed\r\n"
635 );
636 let ids = complete_ok(&mut sort, &mut frag, Some(fetch_reply.as_bytes()));
637 assert_eq!(vec![nz(1), nz(2)], ids);
638 }
639
640 #[test]
641 fn fallback_empty_search_returns_empty_without_fetch() {
642 let mut sort = ImapMessageSort::new(
643 arrival(),
644 search_criteria(),
645 ImapMessageSortOptions {
646 uid: true,
647 fallback: true,
648 },
649 );
650 let mut frag = Fragmentizer::new(50 * 1024 * 1024);
651
652 let bytes = wants_write(&mut sort, &mut frag, None);
653 let search_tag = first_word(str::from_utf8(&bytes).expect("utf8 command")).to_owned();
654 wants_read(&mut sort, &mut frag, None);
655
656 let search_reply = format!("* SEARCH\r\n{search_tag} OK SEARCH completed\r\n");
657 let ids = complete_ok(&mut sort, &mut frag, Some(search_reply.as_bytes()));
658 assert!(ids.is_empty());
659 }
660
661 fn nz(n: u32) -> NonZeroU32 {
662 NonZeroU32::new(n).expect("non-zero")
663 }
664
665 fn wants_write(
666 cor: &mut ImapMessageSort,
667 frag: &mut Fragmentizer,
668 arg: Option<&[u8]>,
669 ) -> Vec<u8> {
670 match cor.resume(frag, arg) {
671 ImapCoroutineState::Yielded(ImapYield::WantsWrite(bytes)) => bytes,
672 state => panic!("expected WantsWrite, got {state:?}"),
673 }
674 }
675
676 fn wants_read(cor: &mut ImapMessageSort, frag: &mut Fragmentizer, arg: Option<&[u8]>) {
677 match cor.resume(frag, arg) {
678 ImapCoroutineState::Yielded(ImapYield::WantsRead) => {}
679 state => panic!("expected WantsRead, got {state:?}"),
680 }
681 }
682
683 fn complete_ok(
684 cor: &mut ImapMessageSort,
685 frag: &mut Fragmentizer,
686 arg: Option<&[u8]>,
687 ) -> Vec<NonZeroU32> {
688 match cor.resume(frag, arg) {
689 ImapCoroutineState::Complete(Ok(value)) => value,
690 state => panic!("expected Complete(Ok), got {state:?}"),
691 }
692 }
693
694 fn complete_err(
695 cor: &mut ImapMessageSort,
696 frag: &mut Fragmentizer,
697 reply: &[u8],
698 ) -> ImapMessageSortError {
699 match cor.resume(frag, Some(reply)) {
700 ImapCoroutineState::Complete(Err(err)) => err,
701 state => panic!("expected Complete(Err), got {state:?}"),
702 }
703 }
704}