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 | |
| 16 | use oxedyne_fe2o3_core::prelude::*; |
| 17 | |
| 18 | use std::fmt; |
| 19 | |
| 20 | |
| 21 | /// The largest UID; `*` in a set. |
| 22 | pub const UID_STAR: u32 = u32::MAX; |
| 23 | |
| 24 | #[derive(Clone, Debug, Default, Eq, PartialEq, Hash)] |
| 25 | pub struct UidSet { |
| 26 | ranges: Vec<(u32, u32)>, // inclusive, sorted, disjoint and never touching |
| 27 | } |
| 28 | |
| 29 | impl 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 | |
| 175 | impl 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 | |
| 195 | impl From<&[u32]> for UidSet { |
| 196 | fn from(uids: &[u32]) -> Self { |
| 197 | uids.iter().copied().collect() |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | impl<const N: usize> From<[u32; N]> for UidSet { |
| 202 | fn from(uids: [u32; N]) -> Self { |
| 203 | uids.into_iter().collect() |
| 204 | } |
| 205 | } |
| 206 | |
| 207 | impl From<&Vec<u32>> for UidSet { |
| 208 | fn from(uids: &Vec<u32>) -> Self { |
| 209 | uids.iter().copied().collect() |
| 210 | } |
| 211 | } |
| 212 | |
| 213 | impl 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`. |
| 232 | pub 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. |
| 254 | fn 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. |
| 261 | fn 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 | |
| 277 | fn 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)] |
| 290 | mod 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 | } |