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        msgnum,
212    });
213    bodylist
214}
215
216pub fn inlist(list: &HmList, val: &str) -> bool {
217    list.values.iter().any(|v| v == val)
218}
219
220pub fn inlist_pos(list: &HmList, val: &str) -> Option<usize> {
221    list.values.iter().position(|v| v == val)
222}
223
224pub fn inlist_regex_pos(list: &HmList, pattern: &str) -> Option<usize> {
225    let re = Regex::new(pattern).ok()?;
226    list.values.iter().position(|v| re.is_match(v))
227}
228
229pub fn add_to_list(list: &mut HmList, val: &str) {
230    if !inlist(list, val) {
231        list.values.push(val.to_string());
232    }
233}
234
235pub fn add_to_list_multi(list: &mut HmList, vals: &str) {
236    for v in vals.split_whitespace() {
237        add_to_list(list, v);
238    }
239}
240
241pub fn link_reply(
242    replylist: &mut Vec<Reply>,
243    from_msgnum: i32,
244    to_msgnum: i32,
245    data: Option<usize>,
246    maybe_reply: bool,
247) {
248    replylist.push(Reply {
249        from_msgnum,
250        msgnum: to_msgnum,
251        data,
252        maybe_reply: if maybe_reply { 1 } else { 0 },
253    });
254}
255
256#[cfg(test)]
257mod tests {
258    use super::*;
259
260    fn make_email(msgnum: i32, msgid: &str, subject: &str, name: &str, date: i64) -> EmailInfo {
261        EmailInfo {
262            msgnum,
263            msgid: Some(msgid.to_string()),
264            subject: Some(subject.to_string()),
265            name: Some(name.to_string()),
266            date,
267            ..Default::default()
268        }
269    }
270
271    #[test]
272    fn test_add_and_find_email() {
273        let mut store = EmailStore::new();
274        let email = make_email(1, "<test@example.com>", "Test", "Alice", 1000000);
275        let idx = store.add_email(email);
276        assert_eq!(idx, 0);
277        assert_eq!(store.find_by_msgid("<test@example.com>"), Some(0));
278        assert_eq!(store.find_by_msgnum(1), Some(0));
279    }
280
281    #[test]
282    fn test_msgid_normalize_finds_whitespace_and_case_variants() {
283        let mut store = EmailStore::new();
284        store.add_email(make_email(1, "<Test@Example.COM>", "S", "A", 1));
285        assert_eq!(store.find_by_msgid("  <test@example.com>  "), Some(0));
286        assert_eq!(store.find_by_msgid("<TEST@EXAMPLE.COM>"), Some(0));
287        assert_eq!(normalize_msgid(" <X@Y> "), "<x@y>");
288    }
289
290    #[test]
291    fn test_date_sorting() {
292        let mut store = EmailStore::new();
293        let e1 = make_email(1, "<a@e>", "Z", "Zoe", 300);
294        let e2 = make_email(2, "<b@e>", "A", "Alice", 100);
295        let e3 = make_email(3, "<c@e>", "M", "Bob", 200);
296        store.add_email(e1);
297        store.add_email(e2);
298        store.add_email(e3);
299
300        store.insert_into_date_list(0);
301        store.insert_into_date_list(1);
302        store.insert_into_date_list(2);
303
304        let sorted = store.traverse_date_list();
305        assert_eq!(sorted.len(), 3);
306        assert_eq!(store.emails[sorted[0]].msgnum, 2); // date=100
307        assert_eq!(store.emails[sorted[1]].msgnum, 3); // date=200
308        assert_eq!(store.emails[sorted[2]].msgnum, 1); // date=300
309    }
310
311    #[test]
312    fn test_subject_sorting() {
313        let mut store = EmailStore::new();
314        let e1 = make_email(1, "<a@e>", "Zebra", "Zoe", 100);
315        let e2 = make_email(2, "<b@e>", "Alpha", "Alice", 100);
316        let e3 = make_email(3, "<c@e>", "Beta", "Bob", 100);
317        store.add_email(e1);
318        store.add_email(e2);
319        store.add_email(e3);
320
321        store.insert_into_subject_list(0);
322        store.insert_into_subject_list(1);
323        store.insert_into_subject_list(2);
324
325        let sorted = store.traverse_subject_list();
326        assert_eq!(sorted.len(), 3);
327        assert_eq!(store.emails[sorted[0]].subject.as_deref(), Some("Alpha"));
328        assert_eq!(store.emails[sorted[1]].subject.as_deref(), Some("Beta"));
329        assert_eq!(store.emails[sorted[2]].subject.as_deref(), Some("Zebra"));
330    }
331
332    #[test]
333    fn test_inlist() {
334        let list = HmList { values: vec!["a".to_string(), "b".to_string()] };
335        assert!(inlist(&list, "a"));
336        assert!(inlist(&list, "b"));
337        assert!(!inlist(&list, "c"));
338    }
339
340    #[test]
341    fn test_add_to_list() {
342        let mut list = HmList { values: Vec::new() };
343        add_to_list(&mut list, "test");
344        assert!(inlist(&list, "test"));
345        add_to_list(&mut list, "test");
346        assert_eq!(list.values.len(), 1);
347    }
348
349    #[test]
350    fn test_reinit() {
351        let mut store = EmailStore::new();
352        let email = make_email(1, "<a@e>", "T", "A", 100);
353        store.add_email(email);
354        assert_eq!(store.emails.len(), 1);
355        store.reinit();
356        assert_eq!(store.emails.len(), 0);
357        assert!(store.msgid_table.is_empty());
358    }
359
360    #[test]
361    fn test_subject_sorting_uses_unre_subject() {
362        // "Re: Alpha" should sort with "Alpha", not after "Zebra"
363        let mut store = EmailStore::new();
364
365        let mut e1 = make_email(1, "<a@e>", "Zebra", "Alice", 100);
366        e1.unre_subject = Some("zebra".to_string());
367
368        let mut e2 = make_email(2, "<b@e>", "Re: Alpha", "Bob", 200);
369        e2.unre_subject = Some("alpha".to_string());
370
371        let mut e3 = make_email(3, "<c@e>", "Alpha", "Carol", 300);
372        e3.unre_subject = Some("alpha".to_string());
373
374        store.add_email(e1);
375        store.add_email(e2);
376        store.add_email(e3);
377        store.insert_into_subject_list(0);
378        store.insert_into_subject_list(1);
379        store.insert_into_subject_list(2);
380
381        let sorted = store.traverse_subject_list();
382        assert_eq!(sorted.len(), 3);
383        // Both "Alpha" and "Re: Alpha" have unre_subject="alpha" → they sort before "Zebra"
384        let subjects: Vec<_> =
385            sorted.iter().map(|&i| store.emails[i].subject.as_deref().unwrap()).collect();
386        let zebra_pos = subjects.iter().position(|&s| s == "Zebra").unwrap();
387        let re_alpha_pos = subjects.iter().position(|&s| s == "Re: Alpha").unwrap();
388        let alpha_pos = subjects.iter().position(|&s| s == "Alpha").unwrap();
389        assert!(zebra_pos > re_alpha_pos, "Re: Alpha should sort before Zebra");
390        assert!(zebra_pos > alpha_pos, "Alpha should sort before Zebra");
391    }
392
393    #[test]
394    fn test_author_sorting_falls_back_to_email_addr() {
395        let mut store = EmailStore::new();
396
397        // Has a name — sorts by name
398        let e1 = EmailInfo {
399            msgnum: 1,
400            msgid: Some("<a@e>".to_string()),
401            name: Some("Zoe".to_string()),
402            email_addr: Some("zoe@example.com".to_string()),
403            date: 100,
404            ..Default::default()
405        };
406        // No name — should fall back to email_addr "amy@example.com" for sorting
407        let e2 = EmailInfo {
408            msgnum: 2,
409            msgid: Some("<b@e>".to_string()),
410            name: None,
411            email_addr: Some("amy@example.com".to_string()),
412            date: 200,
413            ..Default::default()
414        };
415        // Another no-name — falls back to "mid@example.com"
416        let e3 = EmailInfo {
417            msgnum: 3,
418            msgid: Some("<c@e>".to_string()),
419            name: None,
420            email_addr: Some("mid@example.com".to_string()),
421            date: 300,
422            ..Default::default()
423        };
424
425        store.add_email(e1);
426        store.add_email(e2);
427        store.add_email(e3);
428        store.insert_into_author_list(0);
429        store.insert_into_author_list(1);
430        store.insert_into_author_list(2);
431
432        let sorted = store.traverse_author_list();
433        assert_eq!(sorted.len(), 3);
434        // Expected order by sort key: amy@ < mid@ < Zoe
435        assert_eq!(store.emails[sorted[0]].email_addr.as_deref(), Some("amy@example.com"));
436        assert_eq!(store.emails[sorted[1]].email_addr.as_deref(), Some("mid@example.com"));
437        assert_eq!(store.emails[sorted[2]].name.as_deref(), Some("Zoe"));
438    }
439
440    #[test]
441    fn test_author_sorting_no_name_no_email_sorts_to_front() {
442        // Both name and email_addr are None → key is "" → sorts before everything
443        let mut store = EmailStore::new();
444        let e1 = make_email(1, "<a@e>", "T", "Bob", 100);
445        let e2 = EmailInfo {
446            msgnum: 2,
447            msgid: Some("<b@e>".to_string()),
448            name: None,
449            email_addr: None,
450            date: 200,
451            ..Default::default()
452        };
453        store.add_email(e1);
454        store.add_email(e2);
455        store.insert_into_author_list(0);
456        store.insert_into_author_list(1);
457        let sorted = store.traverse_author_list();
458        // "" < "bob" → nameless/emailless sorts first
459        assert_eq!(store.emails[sorted[0]].msgnum, 2);
460        assert_eq!(store.emails[sorted[1]].name.as_deref(), Some("Bob"));
461    }
462
463    #[test]
464    fn test_add_body() {
465        let chain = crate::message::BodyChain { bodies: Vec::new() };
466        let chain = add_body(chain, "Hello World", 1);
467        assert_eq!(chain.bodies.len(), 1);
468        assert_eq!(chain.bodies[0].line, "Hello World");
469        assert_eq!(chain.bodies[0].msgnum, 1);
470        assert!(!chain.bodies[0].attached);
471        assert!(!chain.bodies[0].header);
472    }
473
474    #[test]
475    fn test_inlist_pos_found() {
476        let list = HmList { values: vec!["a".to_string(), "b".to_string(), "c".to_string()] };
477        assert_eq!(inlist_pos(&list, "b"), Some(1));
478    }
479
480    #[test]
481    fn test_inlist_pos_not_found() {
482        let list = HmList { values: vec!["a".to_string()] };
483        assert_eq!(inlist_pos(&list, "z"), None);
484    }
485
486    #[test]
487    fn test_inlist_regex_pos_found() {
488        let list = HmList { values: vec!["foo".to_string(), "bar123".to_string()] };
489        assert_eq!(inlist_regex_pos(&list, r"bar\d+"), Some(1));
490    }
491
492    #[test]
493    fn test_inlist_regex_pos_not_found() {
494        let list = HmList { values: vec!["foo".to_string()] };
495        assert_eq!(inlist_regex_pos(&list, "xyz"), None);
496    }
497
498    #[test]
499    fn test_add_to_list_multi() {
500        let mut list = HmList { values: Vec::new() };
501        add_to_list_multi(&mut list, "a b c a");
502        assert_eq!(list.values.len(), 3);
503        assert!(inlist(&list, "a"));
504        assert!(inlist(&list, "b"));
505        assert!(inlist(&list, "c"));
506    }
507
508    #[test]
509    fn test_link_reply_adds_to_replylist() {
510        let mut replylist = Vec::new();
511        link_reply(&mut replylist, 1, 2, None, false);
512        assert_eq!(replylist.len(), 1);
513        assert_eq!(replylist[0].from_msgnum, 1);
514        assert_eq!(replylist[0].msgnum, 2);
515        assert_eq!(replylist[0].maybe_reply, 0);
516    }
517
518    #[test]
519    fn test_link_reply_maybe_flag() {
520        let mut replylist = Vec::new();
521        link_reply(&mut replylist, 3, 4, Some(0), true);
522        assert_eq!(replylist[0].maybe_reply, 1);
523    }
524
525    /// Regression test for a stack-overflow risk: a large near-sorted mailbox
526    /// (the common case) degenerates the ad-hoc BST into a linked list of depth N.
527    /// Insert/traversal/drop used to be recursive (stack overflow = process abort
528    /// at large N); all three are now iterative. Builds a deep left-leaning chain
529    /// directly (O(N), sidestepping the store's own O(N^2) degenerate-tree insert
530    /// cost — a separate, already-documented performance concern) at a depth that
531    /// would reliably blow the default thread stack if drop/traversal were still
532    /// recursive.
533    #[test]
534    fn test_deep_tree_traverse_and_drop_no_stack_overflow() {
535        const DEPTH: usize = 300_000;
536        let mut root: Option<Box<Header>> = None;
537        for i in (0..DEPTH).rev() {
538            root = Some(Box::new(Header { email_index: i, left: root, right: None }));
539        }
540        let mut result = Vec::new();
541        EmailStore::inorder_traversal(&root, &mut result);
542        assert_eq!(result.len(), DEPTH);
543        assert_eq!(result[0], DEPTH - 1);
544        assert_eq!(*result.last().unwrap(), 0);
545        drop(root); // must not stack-overflow dropping the deep left-only chain
546    }
547}
hypermail/structs.rs

hypermail/
structs.rs
