Skip to main content

hypermail/
structs.rs

1use crate::message::{Body, BodyChain, EmailInfo, Header, HmList, Reply};
2use regex::Regex;
3use std::collections::HashMap;
4
5/// Normalize a Message-ID for lookup/dedup: trim whitespace and lowercase.
6/// Angle brackets are preserved if present so display values stay unchanged;
7/// comparison keys always use this form so `" <A@B> "` matches `"<a@b>"`.
8pub fn normalize_msgid(msgid: &str) -> String {
9    msgid.trim().to_ascii_lowercase()
10}
11
12#[derive(Debug, Clone)]
13pub struct EmailStore {
14    pub emails: Vec<EmailInfo>,
15    pub subject_list: Option<Box<Header>>,
16    pub author_list: Option<Box<Header>>,
17    pub date_list: Option<Box<Header>>,
18    pub msgid_table: HashMap<String, usize>,
19    pub msgnum_table: HashMap<i32, usize>,
20    pub threadlist: Vec<Reply>,
21    pub threadlist_by_msgnum: Vec<Option<usize>>,
22    pub replylist: Vec<Reply>,
23    pub max_msgnum: i32,
24}
25
26impl Default for EmailStore {
27    fn default() -> Self {
28        Self::new()
29    }
30}
31
32impl EmailStore {
33    pub fn new() -> Self {
34        EmailStore {
35            emails: Vec::new(),
36            subject_list: None,
37            author_list: None,
38            date_list: None,
39            msgid_table: HashMap::new(),
40            msgnum_table: HashMap::new(),
41            threadlist: Vec::new(),
42            threadlist_by_msgnum: Vec::new(),
43            replylist: Vec::new(),
44            max_msgnum: -1,
45        }
46    }
47
48    pub fn reinit(&mut self) {
49        self.emails.clear();
50        self.subject_list = None;
51        self.author_list = None;
52        self.date_list = None;
53        self.msgid_table.clear();
54        self.msgnum_table.clear();
55        self.threadlist.clear();
56        self.threadlist_by_msgnum.clear();
57        self.replylist.clear();
58        self.max_msgnum = -1;
59    }
60
61    pub fn find_by_msgid(&self, msgid: &str) -> Option<usize> {
62        self.msgid_table.get(&normalize_msgid(msgid)).copied()
63    }
64
65    pub fn find_by_msgnum(&self, msgnum: i32) -> Option<usize> {
66        self.msgnum_table.get(&msgnum).copied()
67    }
68
69    pub fn add_email(&mut self, email: EmailInfo) -> usize {
70        let idx = self.emails.len();
71        let msgnum = email.msgnum;
72
73        if let Some(ref msgid) = email.msgid {
74            self.msgid_table.insert(normalize_msgid(msgid), idx);
75        }
76
77        self.msgnum_table.insert(msgnum, idx);
78
79        if msgnum > self.max_msgnum {
80            self.max_msgnum = msgnum;
81        }
82
83        self.emails.push(email);
84        idx
85    }
86
87    pub fn insert_into_subject_list(&mut self, idx: usize) {
88        self.subject_list = Self::insert_into_tree_by_field(
89            self.subject_list.take(),
90            idx,
91            &self.emails,
92            |e| e.unre_subject.as_deref().or(e.subject.as_deref()).unwrap_or("").to_lowercase(),
93            |e| e.msgnum,
94        );
95    }
96
97    pub fn insert_into_author_list(&mut self, idx: usize) {
98        self.author_list = Self::insert_into_tree_by_field(
99            self.author_list.take(),
100            idx,
101            &self.emails,
102            |e| e.name.as_deref().or(e.email_addr.as_deref()).unwrap_or("").to_lowercase(),
103            |e| e.msgnum,
104        );
105    }
106
107    pub fn insert_into_date_list(&mut self, idx: usize) {
108        self.date_list = Self::insert_into_tree_by_field(
109            self.date_list.take(),
110            idx,
111            &self.emails,
112            |e| format!("{:020}", e.date),
113            |e| e.msgnum,
114        );
115    }
116
117    /// Inserts `idx` into the tree ordered by `field_fn`/`msgnum_fn`.
118    ///
119    /// # Robustness
120    ///
121    /// Iterative (not recursive) descent: a large near-sorted mailbox (the common
122    /// case — messages usually arrive in date order) degenerates this simple BST
123    /// into a linked list, so a recursive insert would recurse to depth N and risk
124    /// a stack overflow (an abort, not a catchable panic) on large archives.
125    fn insert_into_tree_by_field<F1, F2>(
126        node: Option<Box<Header>>,
127        idx: usize,
128        emails: &[EmailInfo],
129        field_fn: F1,
130        msgnum_fn: F2,
131    ) -> Option<Box<Header>>
132    where
133        F1: Fn(&EmailInfo) -> String,
134        F2: Fn(&EmailInfo) -> i32,
135    {
136        let email = &emails[idx];
137        let key = field_fn(email);
138        let msgnum = msgnum_fn(email);
139
140        let mut root = match node {
141            Some(n) => n,
142            None => return Some(Box::new(Header { email_index: idx, left: None, right: None })),
143        };
144
145        let mut cur: &mut Box<Header> = &mut root;
146        loop {
147            let node_email = &emails[cur.email_index];
148            let node_key = field_fn(node_email);
149            let node_msgnum = msgnum_fn(node_email);
150            let go_left = key < node_key || (key == node_key && msgnum < node_msgnum);
151            let slot = if go_left {
152                &mut cur.left
153            } else {
154                &mut cur.right
155            };
156            match slot {
157                Some(_) => cur = slot.as_mut().unwrap(),
158                None => {
159                    *slot = Some(Box::new(Header { email_index: idx, left: None, right: None }));
160                    break;
161                },
162            }
163        }
164        Some(root)
165    }
166
167    pub fn traverse_date_list(&self) -> Vec<usize> {
168        let mut result = Vec::new();
169        Self::inorder_traversal(&self.date_list, &mut result);
170        result
171    }
172
173    pub fn traverse_subject_list(&self) -> Vec<usize> {
174        let mut result = Vec::new();
175        Self::inorder_traversal(&self.subject_list, &mut result);
176        result
177    }
178
179    pub fn traverse_author_list(&self) -> Vec<usize> {
180        let mut result = Vec::new();
181        Self::inorder_traversal(&self.author_list, &mut result);
182        result
183    }
184
185    /// Iterative in-order traversal (explicit stack) — see `insert_into_tree_by_field`
186    /// for why recursion here would risk a stack overflow on large archives.
187    fn inorder_traversal(node: &Option<Box<Header>>, result: &mut Vec<usize>) {
188        let mut stack: Vec<&Header> = Vec::new();
189        let mut cur = node.as_deref();
190        while cur.is_some() || !stack.is_empty() {
191            while let Some(n) = cur {
192                stack.push(n);
193                cur = n.left.as_deref();
194            }
195            if let Some(n) = stack.pop() {
196                result.push(n.email_index);
197                cur = n.right.as_deref();
198            }
199        }
200    }
201}
202
203pub fn add_body(mut bodylist: BodyChain, line: &str, msgnum: i32) -> BodyChain {
204    bodylist.bodies.push(Body {
205        line: line.to_string(),
206        html: false,
207        header: false,
208        parsed_header: false,
209        attached: false,
210        demimed: false,
211        converted: false,
212        msgnum,
213    });
214    bodylist
215}
216
217pub fn inlist(list: &HmList, val: &str) -> bool {
218    list.values.iter().any(|v| v == val)
219}
220
221pub fn inlist_pos(list: &HmList, val: &str) -> Option<usize> {
222    list.values.iter().position(|v| v == val)
223}
224
225pub fn inlist_regex_pos(list: &HmList, pattern: &str) -> Option<usize> {
226    let re = Regex::new(pattern).ok()?;
227    list.values.iter().position(|v| re.is_match(v))
228}
229
230pub fn add_to_list(list: &mut HmList, val: &str) {
231    if !inlist(list, val) {
232        list.values.push(val.to_string());
233    }
234}
235
236pub fn add_to_list_multi(list: &mut HmList, vals: &str) {
237    for v in vals.split_whitespace() {
238        add_to_list(list, v);
239    }
240}
241
242pub fn link_reply(
243    replylist: &mut Vec<Reply>,
244    from_msgnum: i32,
245    to_msgnum: i32,
246    data: Option<usize>,
247    maybe_reply: bool,
248) {
249    replylist.push(Reply {
250        from_msgnum,
251        msgnum: to_msgnum,
252        data,
253        maybe_reply: if maybe_reply { 1 } else { 0 },
254    });
255}
256
257#[cfg(test)]
258mod tests {
259    use super::*;
260
261    fn make_email(msgnum: i32, msgid: &str, subject: &str, name: &str, date: i64) -> EmailInfo {
262        EmailInfo {
263            msgnum,
264            msgid: Some(msgid.to_string()),
265            subject: Some(subject.to_string()),
266            name: Some(name.to_string()),
267            date,
268            ..Default::default()
269        }
270    }
271
272    #[test]
273    fn test_add_and_find_email() {
274        let mut store = EmailStore::new();
275        let email = make_email(1, "<test@example.com>", "Test", "Alice", 1000000);
276        let idx = store.add_email(email);
277        assert_eq!(idx, 0);
278        assert_eq!(store.find_by_msgid("<test@example.com>"), Some(0));
279        assert_eq!(store.find_by_msgnum(1), Some(0));
280    }
281
282    #[test]
283    fn test_msgid_normalize_finds_whitespace_and_case_variants() {
284        let mut store = EmailStore::new();
285        store.add_email(make_email(1, "<Test@Example.COM>", "S", "A", 1));
286        assert_eq!(store.find_by_msgid("  <test@example.com>  "), Some(0));
287        assert_eq!(store.find_by_msgid("<TEST@EXAMPLE.COM>"), Some(0));
288        assert_eq!(normalize_msgid(" <X@Y> "), "<x@y>");
289    }
290
291    #[test]
292    fn test_date_sorting() {
293        let mut store = EmailStore::new();
294        let e1 = make_email(1, "<a@e>", "Z", "Zoe", 300);
295        let e2 = make_email(2, "<b@e>", "A", "Alice", 100);
296        let e3 = make_email(3, "<c@e>", "M", "Bob", 200);
297        store.add_email(e1);
298        store.add_email(e2);
299        store.add_email(e3);
300
301        store.insert_into_date_list(0);
302        store.insert_into_date_list(1);
303        store.insert_into_date_list(2);
304
305        let sorted = store.traverse_date_list();
306        assert_eq!(sorted.len(), 3);
307        assert_eq!(store.emails[sorted[0]].msgnum, 2); // date=100
308        assert_eq!(store.emails[sorted[1]].msgnum, 3); // date=200
309        assert_eq!(store.emails[sorted[2]].msgnum, 1); // date=300
310    }
311
312    #[test]
313    fn test_subject_sorting() {
314        let mut store = EmailStore::new();
315        let e1 = make_email(1, "<a@e>", "Zebra", "Zoe", 100);
316        let e2 = make_email(2, "<b@e>", "Alpha", "Alice", 100);
317        let e3 = make_email(3, "<c@e>", "Beta", "Bob", 100);
318        store.add_email(e1);
319        store.add_email(e2);
320        store.add_email(e3);
321
322        store.insert_into_subject_list(0);
323        store.insert_into_subject_list(1);
324        store.insert_into_subject_list(2);
325
326        let sorted = store.traverse_subject_list();
327        assert_eq!(sorted.len(), 3);
328        assert_eq!(store.emails[sorted[0]].subject.as_deref(), Some("Alpha"));
329        assert_eq!(store.emails[sorted[1]].subject.as_deref(), Some("Beta"));
330        assert_eq!(store.emails[sorted[2]].subject.as_deref(), Some("Zebra"));
331    }
332
333    #[test]
334    fn test_inlist() {
335        let list = HmList { values: vec!["a".to_string(), "b".to_string()] };
336        assert!(inlist(&list, "a"));
337        assert!(inlist(&list, "b"));
338        assert!(!inlist(&list, "c"));
339    }
340
341    #[test]
342    fn test_add_to_list() {
343        let mut list = HmList { values: Vec::new() };
344        add_to_list(&mut list, "test");
345        assert!(inlist(&list, "test"));
346        add_to_list(&mut list, "test");
347        assert_eq!(list.values.len(), 1);
348    }
349
350    #[test]
351    fn test_reinit() {
352        let mut store = EmailStore::new();
353        let email = make_email(1, "<a@e>", "T", "A", 100);
354        store.add_email(email);
355        assert_eq!(store.emails.len(), 1);
356        store.reinit();
357        assert_eq!(store.emails.len(), 0);
358        assert!(store.msgid_table.is_empty());
359    }
360
361    #[test]
362    fn test_subject_sorting_uses_unre_subject() {
363        // "Re: Alpha" should sort with "Alpha", not after "Zebra"
364        let mut store = EmailStore::new();
365
366        let mut e1 = make_email(1, "<a@e>", "Zebra", "Alice", 100);
367        e1.unre_subject = Some("zebra".to_string());
368
369        let mut e2 = make_email(2, "<b@e>", "Re: Alpha", "Bob", 200);
370        e2.unre_subject = Some("alpha".to_string());
371
372        let mut e3 = make_email(3, "<c@e>", "Alpha", "Carol", 300);
373        e3.unre_subject = Some("alpha".to_string());
374
375        store.add_email(e1);
376        store.add_email(e2);
377        store.add_email(e3);
378        store.insert_into_subject_list(0);
379        store.insert_into_subject_list(1);
380        store.insert_into_subject_list(2);
381
382        let sorted = store.traverse_subject_list();
383        assert_eq!(sorted.len(), 3);
384        // Both "Alpha" and "Re: Alpha" have unre_subject="alpha" → they sort before "Zebra"
385        let subjects: Vec<_> =
386            sorted.iter().map(|&i| store.emails[i].subject.as_deref().unwrap()).collect();
387        let zebra_pos = subjects.iter().position(|&s| s == "Zebra").unwrap();
388        let re_alpha_pos = subjects.iter().position(|&s| s == "Re: Alpha").unwrap();
389        let alpha_pos = subjects.iter().position(|&s| s == "Alpha").unwrap();
390        assert!(zebra_pos > re_alpha_pos, "Re: Alpha should sort before Zebra");
391        assert!(zebra_pos > alpha_pos, "Alpha should sort before Zebra");
392    }
393
394    #[test]
395    fn test_author_sorting_falls_back_to_email_addr() {
396        let mut store = EmailStore::new();
397
398        // Has a name — sorts by name
399        let e1 = EmailInfo {
400            msgnum: 1,
401            msgid: Some("<a@e>".to_string()),
402            name: Some("Zoe".to_string()),
403            email_addr: Some("zoe@example.com".to_string()),
404            date: 100,
405            ..Default::default()
406        };
407        // No name — should fall back to email_addr "amy@example.com" for sorting
408        let e2 = EmailInfo {
409            msgnum: 2,
410            msgid: Some("<b@e>".to_string()),
411            name: None,
412            email_addr: Some("amy@example.com".to_string()),
413            date: 200,
414            ..Default::default()
415        };
416        // Another no-name — falls back to "mid@example.com"
417        let e3 = EmailInfo {
418            msgnum: 3,
419            msgid: Some("<c@e>".to_string()),
420            name: None,
421            email_addr: Some("mid@example.com".to_string()),
422            date: 300,
423            ..Default::default()
424        };
425
426        store.add_email(e1);
427        store.add_email(e2);
428        store.add_email(e3);
429        store.insert_into_author_list(0);
430        store.insert_into_author_list(1);
431        store.insert_into_author_list(2);
432
433        let sorted = store.traverse_author_list();
434        assert_eq!(sorted.len(), 3);
435        // Expected order by sort key: amy@ < mid@ < Zoe
436        assert_eq!(store.emails[sorted[0]].email_addr.as_deref(), Some("amy@example.com"));
437        assert_eq!(store.emails[sorted[1]].email_addr.as_deref(), Some("mid@example.com"));
438        assert_eq!(store.emails[sorted[2]].name.as_deref(), Some("Zoe"));
439    }
440
441    #[test]
442    fn test_author_sorting_no_name_no_email_sorts_to_front() {
443        // Both name and email_addr are None → key is "" → sorts before everything
444        let mut store = EmailStore::new();
445        let e1 = make_email(1, "<a@e>", "T", "Bob", 100);
446        let e2 = EmailInfo {
447            msgnum: 2,
448            msgid: Some("<b@e>".to_string()),
449            name: None,
450            email_addr: None,
451            date: 200,
452            ..Default::default()
453        };
454        store.add_email(e1);
455        store.add_email(e2);
456        store.insert_into_author_list(0);
457        store.insert_into_author_list(1);
458        let sorted = store.traverse_author_list();
459        // "" < "bob" → nameless/emailless sorts first
460        assert_eq!(store.emails[sorted[0]].msgnum, 2);
461        assert_eq!(store.emails[sorted[1]].name.as_deref(), Some("Bob"));
462    }
463
464    #[test]
465    fn test_add_body() {
466        let chain = crate::message::BodyChain { bodies: Vec::new() };
467        let chain = add_body(chain, "Hello World", 1);
468        assert_eq!(chain.bodies.len(), 1);
469        assert_eq!(chain.bodies[0].line, "Hello World");
470        assert_eq!(chain.bodies[0].msgnum, 1);
471        assert!(!chain.bodies[0].attached);
472        assert!(!chain.bodies[0].header);
473    }
474
475    #[test]
476    fn test_inlist_pos_found() {
477        let list = HmList { values: vec!["a".to_string(), "b".to_string(), "c".to_string()] };
478        assert_eq!(inlist_pos(&list, "b"), Some(1));
479    }
480
481    #[test]
482    fn test_inlist_pos_not_found() {
483        let list = HmList { values: vec!["a".to_string()] };
484        assert_eq!(inlist_pos(&list, "z"), None);
485    }
486
487    #[test]
488    fn test_inlist_regex_pos_found() {
489        let list = HmList { values: vec!["foo".to_string(), "bar123".to_string()] };
490        assert_eq!(inlist_regex_pos(&list, r"bar\d+"), Some(1));
491    }
492
493    #[test]
494    fn test_inlist_regex_pos_not_found() {
495        let list = HmList { values: vec!["foo".to_string()] };
496        assert_eq!(inlist_regex_pos(&list, "xyz"), None);
497    }
498
499    #[test]
500    fn test_add_to_list_multi() {
501        let mut list = HmList { values: Vec::new() };
502        add_to_list_multi(&mut list, "a b c a");
503        assert_eq!(list.values.len(), 3);
504        assert!(inlist(&list, "a"));
505        assert!(inlist(&list, "b"));
506        assert!(inlist(&list, "c"));
507    }
508
509    #[test]
510    fn test_link_reply_adds_to_replylist() {
511        let mut replylist = Vec::new();
512        link_reply(&mut replylist, 1, 2, None, false);
513        assert_eq!(replylist.len(), 1);
514        assert_eq!(replylist[0].from_msgnum, 1);
515        assert_eq!(replylist[0].msgnum, 2);
516        assert_eq!(replylist[0].maybe_reply, 0);
517    }
518
519    #[test]
520    fn test_link_reply_maybe_flag() {
521        let mut replylist = Vec::new();
522        link_reply(&mut replylist, 3, 4, Some(0), true);
523        assert_eq!(replylist[0].maybe_reply, 1);
524    }
525
526    /// Regression test for a stack-overflow risk: a large near-sorted mailbox
527    /// (the common case) degenerates the ad-hoc BST into a linked list of depth N.
528    /// Insert/traversal/drop used to be recursive (stack overflow = process abort
529    /// at large N); all three are now iterative. Builds a deep left-leaning chain
530    /// directly (O(N), sidestepping the store's own O(N^2) degenerate-tree insert
531    /// cost — a separate, already-documented performance concern) at a depth that
532    /// would reliably blow the default thread stack if drop/traversal were still
533    /// recursive.
534    #[test]
535    fn test_deep_tree_traverse_and_drop_no_stack_overflow() {
536        const DEPTH: usize = 300_000;
537        let mut root: Option<Box<Header>> = None;
538        for i in (0..DEPTH).rev() {
539            root = Some(Box::new(Header { email_index: i, left: root, right: None }));
540        }
541        let mut result = Vec::new();
542        EmailStore::inorder_traversal(&root, &mut result);
543        assert_eq!(result.len(), DEPTH);
544        assert_eq!(result[0], DEPTH - 1);
545        assert_eq!(*result.last().unwrap(), 0);
546        drop(root); // must not stack-overflow dropping the deep left-only chain
547    }
548}