Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_net/src/imap/uid_set.rs

11.5 KiB, 1 run

created by r1870400018:75219, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! A set of IMAP UIDs held as sorted, disjoint, non-adjacent ranges, so that the 10^5 UIDs of a
2//! large mailbox cost a few bytes rather than a few hundred kilobytes, and a command line carrying
3//! them stays short enough for a server to accept.
4//!
5//! Its text form is the RFC 3501 `sequence-set` (`1:3,7,9:*`), which is both what goes on the wire
6//! and what a server sends back in `COPYUID`, `APPENDUID` and `VANISHED`. A range ending in `*`
7//! is held as ending at `u32::MAX`, which is what `*` means for a set no larger than the mailbox;
8//! a caller asking for `n:*` must still drop any answer below `n`, because a server answers
9//! `n:*` past its last UID with that last message (RFC 3501 6.4.8).
10//!
11//! Tokio-free, so the sync engine can hold one in a browser.
12//!
13//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
14//! Anthropic Claude
15
16use oxedyne_fe2o3_core::prelude::*;
17
18use std::fmt;
19
20
21/// The largest UID; `*` in a set.
22pub const UID_STAR: u32 = u32::MAX;
23
24#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)]
25pub struct UidSet {
26 ranges: Vec<(u32, u32)>, // inclusive, sorted, disjoint and never touching
27}
28
29impl UidSet {
30
31 pub fn new() -> Self {
32 Self::default()
33 }
34
35 /// Every UID from `first` on, `first:*` on the wire.
36 pub fn from_open(first: u32) -> Self {
37 let mut s = Self::new();
38 s.insert_range(first, UID_STAR);
39 s
40 }
41
42 pub fn from_range(first: u32, last: u32) -> Self {
43 let mut s = Self::new();
44 s.insert_range(first, last);
45 s
46 }
47
48 /// Parses a `sequence-set`: comma-separated numbers and `a:b` ranges, either end of which may
49 /// be `*`, in either order. Zero is not a UID and is refused.
50 pub fn parse(text: &str) -> Outcome<Self> {
51 let mut s = Self::new();
52 for (a, b) in res!(parse_items(text)) {
53 s.insert_range(a, b);
54 }
55 Ok(s)
56 }
57
58 pub fn insert(&mut self, uid: u32) {
59 self.insert_range(uid, uid);
60 }
61
62 /// Either order; a range touching or overlapping others is merged with them.
63 pub fn insert_range(&mut self, a: u32, b: u32) {
64 let (mut lo, mut hi) = if a <= b { (a, b) } else { (b, a) };
65 // The first range that could touch [lo, hi]: its end is at least lo - 1.
66 let start = self.ranges.partition_point(|&(_, e)| e.saturating_add(1) < lo);
67 let mut end = start;
68 while end < self.ranges.len() && self.ranges[end].0 <= hi.saturating_add(1) {
69 lo = lo.min(self.ranges[end].0);
70 hi = hi.max(self.ranges[end].1);
71 end += 1;
72 }
73 self.ranges.splice(start..end, std::iter::once((lo, hi)));
74 }
75
76 pub fn remove(&mut self, uid: u32) {
77 let i = self.ranges.partition_point(|&(_, e)| e < uid);
78 if i >= self.ranges.len() || self.ranges[i].0 > uid {
79 return;
80 }
81 let (lo, hi) = self.ranges[i];
82 let mut parts = Vec::with_capacity(2);
83 if lo < uid { parts.push((lo, uid - 1)); }
84 if uid < hi { parts.push((uid + 1, hi)); }
85 self.ranges.splice(i..i + 1, parts);
86 }
87
88 pub fn contains(&self, uid: u32) -> bool {
89 let i = self.ranges.partition_point(|&(_, e)| e < uid);
90 i < self.ranges.len() && self.ranges[i].0 <= uid
91 }
92
93 /// How many UIDs, counting an open range up to `u32::MAX`.
94 pub fn len(&self) -> u64 {
95 self.ranges.iter().map(|&(a, b)| (b - a) as u64 + 1).sum()
96 }
97
98 pub fn is_empty(&self) -> bool {
99 self.ranges.is_empty()
100 }
101
102 pub fn ranges(&self) -> &[(u32, u32)] {
103 &self.ranges
104 }
105
106 pub fn first(&self) -> Option<u32> {
107 self.ranges.first().map(|r| r.0)
108 }
109
110 pub fn last(&self) -> Option<u32> {
111 self.ranges.last().map(|r| r.1)
112 }
113
114 /// Ascending. An open range runs to `u32::MAX`, so bound it before iterating.
115 pub fn iter(&self) -> impl Iterator<Item = u32> + '_ {
116 self.ranges.iter().flat_map(|&(a, b)| a..=b)
117 }
118
119 pub fn union(&self, other: &Self) -> Self {
120 let mut out = self.clone();
121 for &(a, b) in &other.ranges {
122 out.insert_range(a, b);
123 }
124 out
125 }
126
127 /// What is in `self` and not in `other`: the held UIDs a server no longer reports, say.
128 pub fn difference(&self, other: &Self) -> Self {
129 let mut out = Vec::new();
130 let mut j = 0usize;
131 for &(a, b) in &self.ranges {
132 let mut lo = a;
133 while j < other.ranges.len() && other.ranges[j].1 < lo {
134 j += 1;
135 }
136 let mut k = j;
137 let mut done = false;
138 while k < other.ranges.len() && other.ranges[k].0 <= b {
139 let (oa, ob) = other.ranges[k];
140 if oa > lo {
141 out.push((lo, oa - 1));
142 }
143 if ob >= b {
144 done = true;
145 break;
146 }
147 lo = ob + 1;
148 k += 1;
149 }
150 if !done {
151 out.push((lo, b));
152 }
153 }
154 Self { ranges: out }
155 }
156
157 /// What is in both.
158 pub fn intersection(&self, other: &Self) -> Self {
159 let mut out = Vec::new();
160 let (mut i, mut j) = (0usize, 0usize);
161 while i < self.ranges.len() && j < other.ranges.len() {
162 let (a, b) = self.ranges[i];
163 let (c, d) = other.ranges[j];
164 let lo = a.max(c);
165 let hi = b.min(d);
166 if lo <= hi {
167 out.push((lo, hi));
168 }
169 if b < d { i += 1; } else { j += 1; }
170 }
171 Self { ranges: out }
172 }
173}
174
175impl fmt::Display for UidSet {
176 /// The wire form; an empty set writes nothing, which no command accepts, so a caller sends no
177 /// command for one.
178 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
179 let end = |n: u32| if n == UID_STAR { fmt!("*") } else { fmt!("{}", n) };
180 let mut out = String::new();
181 for (i, &(a, b)) in self.ranges.iter().enumerate() {
182 if i > 0 {
183 out.push(',');
184 }
185 if a == b {
186 out.push_str(&end(a));
187 } else {
188 out.push_str(&fmt!("{}:{}", a, end(b)));
189 }
190 }
191 f.write_str(&out)
192 }
193}
194
195impl From<&[u32]> for UidSet {
196 fn from(uids: &[u32]) -> Self {
197 uids.iter().copied().collect()
198 }
199}
200
201impl<const N: usize> From<[u32; N]> for UidSet {
202 fn from(uids: [u32; N]) -> Self {
203 uids.into_iter().collect()
204 }
205}
206
207impl From<&Vec<u32>> for UidSet {
208 fn from(uids: &Vec<u32>) -> Self {
209 uids.iter().copied().collect()
210 }
211}
212
213impl FromIterator<u32> for UidSet {
214 fn from_iter<I: IntoIterator<Item = u32>>(it: I) -> Self {
215 let mut v: Vec<u32> = it.into_iter().collect();
216 v.sort_unstable();
217 v.dedup();
218 let mut ranges: Vec<(u32, u32)> = Vec::new();
219 for u in v {
220 match ranges.last_mut() {
221 Some(r) if r.1.checked_add(1) == Some(u) => r.1 = u,
222 _ => ranges.push((u, u)),
223 }
224 }
225 Self { ranges }
226 }
227}
228
229/// The UIDs of a `sequence-set` in the order written, each range expanded in its written
230/// direction. This is how `COPYUID` pairs a source UID with its destination: by position. A `*`
231/// has no number to expand to and is refused, and so is a list longer than `max`.
232pub fn uid_list(text: &str, max: usize) -> Outcome<Vec<u32>> {
233 let mut out = Vec::new();
234 for (a, b) in res!(parse_items_ordered(text)) {
235 if a == UID_STAR || b == UID_STAR {
236 return Err(err!("The UID list '{}' holds a '*', which names no one UID.", text;
237 Invalid, Input, Decode));
238 }
239 let n = (a.max(b) - a.min(b)) as usize + 1;
240 if out.len() + n > max {
241 return Err(err!("The UID list '{}' holds more than {} UIDs.", text, max;
242 Invalid, Input, Excessive));
243 }
244 if a <= b {
245 out.extend(a..=b);
246 } else {
247 out.extend((b..=a).rev());
248 }
249 }
250 Ok(out)
251}
252
253/// Each item as `(first, last)`, normalised to ascending.
254fn parse_items(text: &str) -> Outcome<Vec<(u32, u32)>> {
255 Ok(res!(parse_items_ordered(text)).into_iter()
256 .map(|(a, b)| if a <= b { (a, b) } else { (b, a) })
257 .collect())
258}
259
260/// Each item as `(first, last)` exactly as written.
261fn parse_items_ordered(text: &str) -> Outcome<Vec<(u32, u32)>> {
262 let text = text.trim();
263 if text.is_empty() {
264 return Err(err!("An empty UID set."; Invalid, Input, Decode));
265 }
266 let mut out = Vec::new();
267 for item in text.split(',') {
268 let (a, b) = match item.split_once(':') {
269 Some((a, b)) => (res!(one_uid(a, text)), res!(one_uid(b, text))),
270 None => { let n = res!(one_uid(item, text)); (n, n) },
271 };
272 out.push((a, b));
273 }
274 Ok(out)
275}
276
277fn one_uid(s: &str, whole: &str) -> Outcome<u32> {
278 if s == "*" {
279 return Ok(UID_STAR);
280 }
281 match s.parse::<u32>() {
282 Ok(0) => Err(err!("Zero is not a UID, in '{}'.", whole; Invalid, Input, Decode)),
283 Ok(n) => Ok(n),
284 Err(_) => Err(err!("'{}' is not a UID, in '{}'.", s, whole; Invalid, Input, Decode)),
285 }
286}
287
288
289#[cfg(test)]
290mod tests {
291 use super::*;
292
293 fn set(text: &str) -> Outcome<UidSet> {
294 UidSet::parse(text)
295 }
296
297 #[test]
298 fn test_runs_collapse_and_print_as_the_wire_form_00() -> Outcome<()> {
299 let s: UidSet = [10u32, 1, 2, 3, 7, 9, 3].into_iter().collect();
300 req!("1:3,7,9:10", s.to_string().as_str());
301 req!(6, s.len());
302 req!("5:*", UidSet::from_open(5).to_string().as_str());
303 req!("", UidSet::new().to_string().as_str());
304 Ok(())
305 }
306
307 #[test]
308 fn test_parse_merges_reversed_overlapping_and_touching_ranges_00() -> Outcome<()> {
309 let s = res!(set("9:7,1,2:4,5,20:*"));
310 req!(vec![(1, 5), (7, 9), (20, UID_STAR)], s.ranges().to_vec());
311 req!(true, UidSet::parse("0").is_err(), "zero was taken for a UID");
312 req!(true, UidSet::parse("1,,2").is_err());
313 req!(true, UidSet::parse("").is_err());
314 Ok(())
315 }
316
317 #[test]
318 fn test_insert_and_remove_keep_the_ranges_canonical_00() -> Outcome<()> {
319 let mut s = res!(set("1:3,7:9"));
320 s.insert(5);
321 req!("1:3,5,7:9", s.to_string().as_str());
322 s.insert(4);
323 s.insert(6);
324 req!("1:9", s.to_string().as_str());
325 s.remove(5);
326 s.remove(1);
327 s.remove(9);
328 s.remove(42);
329 req!("2:4,6:8", s.to_string().as_str());
330 req!(true, s.contains(3) && !s.contains(5) && !s.contains(9));
331 s.insert_range(UID_STAR, 1);
332 req!("1:*", s.to_string().as_str());
333 Ok(())
334 }
335
336 #[test]
337 fn test_difference_is_what_vanished_00() -> Outcome<()> {
338 let held = res!(set("1:10,20:30"));
339 let now = res!(set("2:4,6,10:21,25"));
340 req!("1,5,7:9,22:24,26:30", held.difference(&now).to_string().as_str());
341 req!("", held.difference(&held).to_string().as_str());
342 req!(held.to_string(), held.difference(&UidSet::new()).to_string());
343 req!("2:4,6,10,20:21,25", held.intersection(&now).to_string().as_str());
344 req!("1:30", held.union(&res!(set("11:19"))).to_string().as_str());
345 Ok(())
346 }
347
348 #[test]
349 fn test_a_uid_list_keeps_its_written_order_00() -> Outcome<()> {
350 req!(vec![304, 319, 320, 5, 4], res!(uid_list("304,319:320,5:4", 100)));
351 req!(true, uid_list("1:*", 100).is_err(), "a star was expanded");
352 req!(true, uid_list("1:1000", 100).is_err(), "the bound was not kept");
353 Ok(())
354 }
355}