dovenest

itip.rs

1	//! Implicit scheduling (RFC 6638) as iTIP messages (RFC 5546): what a change
2	//! to a scheduling object sends to whom, and how each copy changes.
3	//!
4	//! Calendar user addresses are compared through closures, so the caller maps
5	//! them onto its principals.
6
7	use std::cell::{Cell, OnceCell, RefCell};
8	use std::cmp::Ordering;
9	use std::collections::{HashMap, HashSet};
10	use std::sync::Arc;
11
12	use calcard::common::PartialDateTime;
13	use calcard::icalendar::{
14	ICalendar, ICalendarComponent, ICalendarComponentType, ICalendarDuration, ICalendarEntry,
15	ICalendarFrequency, ICalendarMethod, ICalendarParameter, ICalendarParameterName,
16	ICalendarParameterValue, ICalendarParticipationStatus, ICalendarProperty,
17	ICalendarRecurrenceRule, ICalendarStatus, ICalendarValue, ICalendarWeekday, Uri,
18	};
19	use chrono::{DateTime, TimeDelta, Utc};
20	use xmltree::Element;
21
22	use crate::expand::{Expansion, MAX_OCCURRENCES, expand, expand_in, stamp, until_utc};
23	use crate::filter::TimeRange;
24	use crate::freebusy::{Busy, Period, merge};
25	use crate::object::MAX_COMPONENTS;
26	use crate::text::{fold, logical_lines, name, param_parts, unfold, value};
27	use crate::xml::{CALDAV, el};
28	use crate::zone::{Zone, Zones, add, add_local};
29
30	/// Whether an address belongs to someone in particular.
31	pub type Is<'a> = &'a dyn Fn(&str) -> bool;
32
33	/// How the owner of a calendar takes part in one of its objects (RFC 6638,
34	/// 3.1).
35	#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36	pub enum Role {
37	Organizer,
38	Attendee,
39	/// Not a scheduling object for this owner.
40	None,
41	}
42
43	/// A scheduling precondition a PUT fails.
44	#[derive(Debug, Clone, Copy, PartialEq, Eq)]
45	pub enum Refused {
46	SameOrganizer,
47	AttendeeChange,
48	}
49
50	impl Refused {
51	pub fn condition(self) -> Element {
52	match self {
53	Refused::SameOrganizer => el(CALDAV, "same-organizer-in-all-components"),
54	Refused::AttendeeChange => el(CALDAV, "allowed-attendee-scheduling-object-change"),
55	}
56	}
57	}
58
59	#[derive(Debug, Clone, Copy, PartialEq, Eq)]
60	pub enum Method {
61	Request,
62	Cancel,
63	Reply,
64	}
65
66	#[derive(Debug, Clone)]
67	pub struct Message {
68	/// The recipient's address, as the object writes it.
69	pub to: String,
70	pub method: Method,
71	/// Only other attendees' answers or the SEQUENCE changed. It updates an
72	/// existing copy, keeps its Schedule-Tag and leaves no inbox entry.
73	pub quiet: bool,
74	/// With METHOD. Recipients who see the same thing share one.
75	pub cal: Arc<ICalendar>,
76	}
77
78	pub fn role(cal: &ICalendar, owner: Is) -> Result<Role, Refused> {
79	let obj = Obj::new(cal);
80	let mut organizers = obj
81	.comps()
82	.filter_map(\|c\| address(c.c.property(&ICalendarProperty::Organizer)?));
83	let Some(organizer) = organizers.next() else {
84	return Ok(Role::None);
85	};
86	if organizers.any(\|o\| !o.eq_ignore_ascii_case(organizer)) {
87	return Err(Refused::SameOrganizer);
88	}
89	if owner(organizer) {
90	return Ok(Role::Organizer);
91	}
92	let attends = obj
93	.comps()
94	.flat_map(\|c\| attendees(&c.c))
95	.any(\|e\| address(e).is_some_and(owner));
96	Ok(if attends { Role::Attendee } else { Role::None })
97	}
98
99	/// The ORGANIZER address of a scheduling object.
100	pub fn organizer(cal: &ICalendar) -> Option<&str> {
101	cal.components
102	.iter()
103	.filter(\|c\| is_scheduled(c))
104	.find_map(\|c\| address(c.property(&ICalendarProperty::Organizer)?))
105	}
106
107	/// An organizer's PUT (`new`) or DELETE (`None`) of a scheduling object.
108	/// `old` is the stored organizer object, if any. Returns what to store and
109	/// what to deliver.
110	pub fn organize(
111	old: Option<&ICalendar>,
112	new: Option<ICalendar>,
113	organizer: Is,
114	now: DateTime<Utc>,
115	) -> (Option<ICalendar>, Vec<Message>) {
116	let mut force = Vec::new();
117	let new = new.map(\|n\| guard(old, &n, organizer, &mut force));
118	let messages = messages(old, new.as_ref(), organizer, &force, now);
119	(new, messages)
120	}
121
122	/// The first half of [`organize`] for a PUT: what to store, with the
123	/// attendee state the server owns, and the attendees whose REQUEST is
124	/// forced. [`messages`] is the second half.
125	pub fn prepare(
126	old: Option<&ICalendar>,
127	new: &ICalendar,
128	organizer: Is,
129	) -> (ICalendar, Vec<String>) {
130	let mut force = Vec::new();
131	let store = guard(old, new, organizer, &mut force);
132	(store, force)
133	}
134
135	/// Names who acted for the owner: `SENT-BY` on the owner's ORGANIZER and
136	/// ATTENDEE properties when `sender` is someone else, none when it is the
137	/// owner. Only for writes that send a message, so every message names its
138	/// real sender.
139	pub fn stamp_sender(cal: &mut ICalendar, owner: Is, sender: Option<&str>) {
140	for c in cal.components.iter_mut().filter(\|c\| is_scheduled(c)) {
141	for e in &mut c.entries {
142	let theirs = matches!(
143	e.name,
144	ICalendarProperty::Organizer \| ICalendarProperty::Attendee
145	) && address(e).is_some_and(owner);
146	match (theirs, sender) {
147	(false, _) => {}
148	(true, Some(s)) => set_param(
149	e,
150	ICalendarParameterName::SentBy,
151	ICalendarParameterValue::Uri(Uri::Location(s.to_string())),
152	),
153	(true, None) => remove_param(e, &ICalendarParameterName::SentBy),
154	}
155	}
156	}
157	}
158
159	/// How far ahead a room checks an invitation against its bookings. A
160	/// series without end has infinite instances, so it is checked for two years
161	/// and accepted beyond. Anything else is checked to its end, at most ten
162	/// years ahead.
163	pub fn answer_horizon(copy: &ICalendar) -> TimeDelta {
164	let endless = copy.components.iter().any(\|c\| {
165	is_scheduled(c) && !c.has_property(&ICalendarProperty::RecurrenceId) && endless(c)
166	});
167	TimeDelta::days(if endless { 731 } else { 3653 })
168	}
169
170	/// New overrides and EXDATE values one attendee PUT may bring.
171	const MAX_ATTENDEE_CHANGES: usize = 1000;
172
173	/// Conflicting instances of a series a room declines one by one. Beyond
174	/// that it declines the series.
175	const MAX_DECLINED_INSTANCES: usize = 100;
176
177	/// The answer of a room or resource to the invitation in its copy:
178	/// ACCEPTED, and DECLINED where an instance in `window` overlaps `taken`. A
179	/// declined instance of a series gets an override of its own.
180	pub fn auto_answer(
181	copy: &ICalendar,
182	me: Is,
183	taken: &[Period],
184	window: &TimeRange,
185	floating: &Zone,
186	) -> ICalendar {
187	let taken = merge(
188	taken
189	.iter()
190	.map(\|p\| Period {
191	kind: Busy::Busy,
192	start: p.start,
193	end: p.end,
194	})
195	.collect(),
196	);
197	let conflicts = \|s: DateTime<Utc>, e: DateTime<Utc>\| {
198	let i = taken.partition_point(\|p\| p.end <= s);
199	taken
200	.get(i)
201	.is_some_and(\|p\| p.start < e \|\| (s == e && p.start <= s))
202	};
203	let mut obj = Obj::new(copy);
204	let form = obj
205	.master()
206	.and_then(\|m\| m.c.property(&ICalendarProperty::Dtstart))
207	.cloned();
208	let mut declined: HashSet<Option<i64>> = HashSet::new();
209	let mut slots: Vec<DateTime<Utc>> = Vec::new();
210	for x in expand(copy, window.clone(), floating.clone()).instances {
211	if !conflicts(x.start, x.end) {
212	continue;
213	}
214	match x.recurrence_id {
215	Some(rid) if form.is_some() => slots.push(rid),
216	_ => {
217	declined.insert(obj.key(&copy.components[x.component]));
218	}
219	}
220	}
221	// One override each would bloat the copy and the REPLY.
222	let all = slots.len() > MAX_DECLINED_INSTANCES;
223	if let (false, Some(form)) = (all, &form) {
224	// In order, so a range moved on past one instance can move again.
225	slots.sort_unstable();
226	for rid in slots {
227	let Some(key) = obj
228	.recurrence_id(form, rid, floating)
229	.and_then(\|id\| obj.instant(&id))
230	else {
231	continue;
232	};
233	if obj.find(Some(key)).is_some() {
234	obj.narrow(copy, rid, key, floating);
235	} else if let Some(inst) = obj.single(rid, floating) {
236	obj.push(inst);
237	} else {
238	continue;
239	}
240	declined.insert(Some(key));
241	}
242	}
243	let keys: Vec<Option<i64>> = obj.comps().map(\|c\| obj.key(&c.c)).collect();
244	for (c, key) in obj.comps_mut().zip(&keys) {
245	let answer = match all \|\| declined.contains(key) {
246	true => ICalendarParticipationStatus::Declined,
247	false => ICalendarParticipationStatus::Accepted,
248	};
249	for e in
250	c.c.entries
251	.iter_mut()
252	.filter(\|e\| e.name == ICalendarProperty::Attendee && address(e).is_some_and(me))
253	{
254	set_param(
255	e,
256	ICalendarParameterName::Partstat,
257	partstat(answer.clone()),
258	);
259	}
260	}
261	obj.done()
262	}
263
264	/// The attendee's copy with `me` answering `answer`: for every component, or
265	/// only for the instance at `instance`, which gets an override of its own
266	/// when it has none. `floating` reads the instance of an all-day series.
267	/// Storing the result through a PUT sends the REPLY. `None` if the series
268	/// has no instance at `instance`.
269	pub fn respond(
270	copy: &ICalendar,
271	me: Is,
272	answer: ICalendarParticipationStatus,
273	instance: Option<DateTime<Utc>>,
274	floating: &Zone,
275	) -> Option<ICalendar> {
276	let mut obj = Obj::new(copy);
277	let target = match instance {
278	None => None,
279	Some(rid) => {
280	let form = obj
281	.master()
282	.and_then(\|m\| m.c.property(&ICalendarProperty::Dtstart))
283	.or_else(\|\| {
284	obj.comps()
285	.find_map(\|c\| c.c.property(&ICalendarProperty::RecurrenceId))
286	})?
287	.clone();
288	let key = obj.instant(&obj.recurrence_id(&form, rid, floating)?)?;
289	if obj.find(Some(key)).is_some() {
290	obj.narrow(copy, rid, key, floating);
291	} else {
292	if !obj.occurs(copy, rid, key, floating) {
293	return None;
294	}
295	let inst = obj.single(rid, floating)?;
296	obj.push(inst);
297	}
298	Some(Some(key))
299	}
300	};
301	let keys: Vec<Option<i64>> = obj.comps().map(\|c\| obj.key(&c.c)).collect();
302	for (c, key) in obj.comps_mut().zip(&keys) {
303	if target.is_some_and(\|t\| t != *key) {
304	continue;
305	}
306	for e in
307	c.c.entries
308	.iter_mut()
309	.filter(\|e\| e.name == ICalendarProperty::Attendee && address(e).is_some_and(me))
310	{
311	set_param(
312	e,
313	ICalendarParameterName::Partstat,
314	partstat(answer.clone()),
315	);
316	remove_param(e, &ICalendarParameterName::Rsvp);
317	}
318	}
319	Some(obj.done())
320	}
321
322	/// The messages a change of the organizer object sends, without touching
323	/// the attendee state in it. `force` lists attendees who get a REQUEST even
324	/// if nothing changed for them.
325	pub fn messages(
326	old: Option<&ICalendar>,
327	new: Option<&ICalendar>,
328	organizer: Is,
329	force: &[String],
330	now: DateTime<Utc>,
331	) -> Vec<Message> {
332	let old = old.map(Obj::new);
333	let new = new.map(Obj::new);
334	let mut who: Vec<&str> = Vec::new();
335	let mut seen: HashSet<String> = HashSet::new();
336	for obj in old.iter().chain(new.iter()) {
337	for e in obj.comps().flat_map(\|c\| attendees(&c.c)) {
338	if let Some(a) = address(e)
339	&& server_agent(e)
340	&& !organizer(a)
341	&& seen.insert(a.to_ascii_lowercase())
342	{
343	who.push(a);
344	}
345	}
346	}
347	// Attendees invited to the same components share one view and one
348	// message body.
349	let old_inv = old.as_ref().map(Obj::invitations);
350	let new_inv = new.as_ref().map(Obj::invitations);
351	let client: HashSet<String> = new
352	.iter()
353	.flat_map(\|n\| n.comps().flat_map(\|c\| attendees(&c.c)))
354	.filter(\|e\| !server_agent(e))
355	.filter_map(address)
356	.map(str::to_ascii_lowercase)
357	.collect();
358	let mut old_views: HashMap<Vec<bool>, Option<Vec<Node>>> = HashMap::new();
359	let mut new_views: HashMap<Vec<bool>, Option<Vec<Node>>> = HashMap::new();
360	let mut changes: HashMap<(Vec<bool>, Vec<bool>), Change> = HashMap::new();
361	let mut requests: HashMap<Vec<bool>, Arc<ICalendar>> = HashMap::new();
362	let mut cancels: HashMap<(Vec<bool>, Vec<bool>), Arc<ICalendar>> = HashMap::new();
363	let mut out = Vec::new();
364	for a in who {
365	let lower = a.to_ascii_lowercase();
366	let sig = \|inv: &Vec<HashSet<String>>\| -> Vec<bool> {
367	inv.iter().map(\|s\| s.contains(&lower)).collect()
368	};
369	let sb = old_inv.as_ref().map(sig);
370	let sa = new_inv.as_ref().map(sig);
371	if let (Some(o), Some(s)) = (&old, &sb) {
372	old_views.entry(s.clone()).or_insert_with(\|\| o.view(s));
373	}
374	if let (Some(n), Some(s)) = (&new, &sa) {
375	new_views.entry(s.clone()).or_insert_with(\|\| n.view(s));
376	}
377	let before = old
378	.as_ref()
379	.zip(sb.as_ref())
380	.and_then(\|(o, s)\| Some((o, s, old_views[s].as_ref()?)));
381	let after = new
382	.as_ref()
383	.zip(sa.as_ref())
384	.and_then(\|(n, s)\| Some((n, s, new_views[s].as_ref()?)));
385	let request = \|n: &Obj, sa: &Vec<bool>, comps: &Vec<Node>, requests: &mut HashMap<_, _>\| {
386	Arc::clone(
387	requests
388	.entry(sa.clone())
389	.or_insert_with(\|\| Arc::new(n.envelope(comps.clone(), Method::Request, now))),
390	)
391	};
392	let (method, quiet, cal) = match (before, after) {
393	(Some((src, sb, b)), None) => {
394	// A component that lists them with SCHEDULE-AGENT=CLIENT
395	// now: the client tells them.
396	let lost: Vec<bool> = match client.contains(&lower) {
397	false => vec![true; b.len()],
398	true => b
399	.iter()
400	.map(\|c\| {
401	!new.as_ref()
402	.and_then(\|n\| n.find(src.key(&c.c)))
403	.is_some_and(\|nc\| client_scheduled(&nc.c, a))
404	})
405	.collect(),
406	};
407	if !lost.contains(&true) {
408	continue;
409	}
410	let key = (sb.clone(), lost);
411	let cal = cancels.entry(key).or_insert_with_key(\|(_, lost)\| {
412	let comps = b
413	.iter()
414	.zip(lost)
415	.filter(\|(_, l)\| **l)
416	.map(\|(c, _)\| c.clone());
417	Arc::new(src.envelope(cancelled(comps.collect()), Method::Cancel, now))
418	});
419	(Method::Cancel, false, Arc::clone(cal))
420	}
421	(None, Some((n, sa, comps))) => {
422	(Method::Request, false, request(n, sa, comps, &mut requests))
423	}
424	(Some((_, sb, b)), Some((n, sa, comps))) => {
425	let change = *changes
426	.entry((sb.clone(), sa.clone()))
427	.or_insert_with(\|\| change(b, comps));
428	let forced = force.iter().any(\|f\| f.eq_ignore_ascii_case(a));
429	let quiet = match change {
430	Change::Content => false,
431	Change::Answers => true,
432	_ if forced => false,
433	// Copies carry the new SEQUENCE, or their replies count
434	// as stale.
435	Change::Sequence => true,
436	Change::None => continue,
437	};
438	(Method::Request, quiet, request(n, sa, comps, &mut requests))
439	}
440	(None, None) => continue,
441	};
442	out.push(Message {
443	to: a.to_string(),
444	method,
445	quiet,
446	cal,
447	});
448	}
449	out
450	}
451
452	/// Records the delivery status for `to` on its ATTENDEE properties.
453	pub fn set_attendee_status(cal: &mut ICalendar, to: &str, status: &str) {
454	for c in &mut cal.components {
455	for e in c
456	.entries
457	.iter_mut()
458	.filter(\|e\| e.name == ICalendarProperty::Attendee)
459	{
460	if address(e).is_some_and(\|a\| a.eq_ignore_ascii_case(to)) {
461	set_param(e, ICalendarParameterName::ScheduleStatus, text(status));
462	}
463	}
464	}
465	}
466
467	/// Records the delivery status of a REPLY on the ORGANIZER properties.
468	pub fn set_organizer_status(cal: &mut ICalendar, status: &str) {
469	for c in &mut cal.components {
470	for e in c
471	.entries
472	.iter_mut()
473	.filter(\|e\| e.name == ICalendarProperty::Organizer)
474	{
475	set_param(e, ICalendarParameterName::ScheduleStatus, text(status));
476	}
477	}
478	}
479
480	/// An attendee's PUT over the stored copy. Returns what to store and the
481	/// REPLY, if the attendee's participation changed.
482	pub fn attend(
483	old: &ICalendar,
484	new: ICalendar,
485	me: Is,
486	now: DateTime<Utc>,
487	) -> Result<(ICalendar, Option<Message>), Refused> {
488	let old_cal = old;
489	let old = Obj::new(old_cal);
490	if !old.organizer_schedules() {
491	return Ok((new, None));
492	}
493	let mut next = Obj::new(&new);
494	let master = old.master();
495	let added: Vec<i64> = next
496	.comps()
497	.filter_map(\|c\| next.key(&c.c))
498	.filter(\|k\| old.find(Some(*k)).is_none())
499	.collect();
500	let excluded = next.master().map_or(0, \|m\| {
501	let before = master.map_or_else(HashSet::new, \|om\| {
502	old.times(&om.c, &ICalendarProperty::Exdate)
503	});
504	next.times(&m.c, &ICalendarProperty::Exdate)
505	.difference(&before)
506	.count()
507	});
508	// Each becomes a part of the REPLY and an override in the organizer object.
509	if added.len() + excluded > MAX_ATTENDEE_CHANGES {
510	return Err(Refused::AttendeeChange);
511	}
512	// A key a cut-short expansion cannot confirm is refused, as the
513	// organizer's side would drop its reply.
514	let (instances, _) = old.instances(old_cal, &added);
515
516	for c in next.comps() {
517	let key = next.key(&c.c);
518	match old.find(key) {
519	Some(oc) => {
520	// The end, not its property: clients rewrite DURATION as DTEND.
521	let same_times = [
522	ICalendarProperty::Dtstart,
523	ICalendarProperty::Rdate,
524	ICalendarProperty::Exrule,
525	]
526	.iter()
527	.all(\|p\| old.times(&oc.c, p) == next.times(&c.c, p))
528	&& old.end(&oc.c) == next.end(&c.c)
529	&& same_rules(&old, &oc.c, &next, &c.c);
530	let kept_exdates = old
531	.times(&oc.c, &ICalendarProperty::Exdate)
532	.is_subset(&next.times(&c.c, &ICalendarProperty::Exdate));
533	if !same_times
534	\|\| !kept_exdates
535	\|\| organizer_of(&oc.c) != organizer_of(&c.c)
536	\|\| addresses(&oc.c) != addresses(&c.c)
537	{
538	return Err(Refused::AttendeeChange);
539	}
540	}
541	// An instance the attendee overrides, to set its own status.
542	None => {
543	if !key.is_some_and(\|k\| {
544	master.is_some() && instances.contains(&k) && old.plain(&next, &c.c, k, true)
545	}) {
546	return Err(Refused::AttendeeChange);
547	}
548	}
549	}
550	}
551	// Dropping an override is fine where it held no change of the
552	// organizer's, where the attendee deletes that instance with an EXDATE,
553	// and in a copy of single instances.
554	let exdated: HashSet<i64> = next
555	.master()
556	.into_iter()
557	.flat_map(\|m\| m.c.properties(&ICalendarProperty::Exdate))
558	.flat_map(\|e\| {
559	e.values
560	.iter()
561	.filter_map(\|v\| next.at(v.as_partial_date_time()?, e.tz_id()))
562	})
563	.collect();
564	let mut reverted: Vec<(i64, Option<String>)> = Vec::new();
565	for oc in old.comps() {
566	let key = old.key(&oc.c);
567	if next.find(key).is_some() {
568	continue;
569	}
570	let plain = \|k: i64\| old.plain(&old, &oc.c, k, false);
571	let allowed =
572	\|k: i64\| master.is_none() \|\| !is_range(&oc.c) && (exdated.contains(&k) \|\| plain(k));
573	if !key.is_some_and(allowed) {
574	return Err(Refused::AttendeeChange);
575	}
576	if let Some(k) = key.filter(\|k\| master.is_some() && !exdated.contains(k)) {
577	reverted.push((k, own_partstat(&oc.c, me)));
578	}
579	}
580
581	// The state of the others and of the organizer is the server's. A new
582	// override takes it from the THISANDFUTURE override that moves it.
583	let base = \|key: Option<i64>\| {
584	old.find(key)
585	.or_else(\|\| old.future(key?).map(\|(n, _)\| n))
586	.or(master)
587	};
588	let mut force = false;
589	let keys: Vec<Option<i64>> = next.comps().map(\|c\| next.key(&c.c)).collect();
590	for (c, key) in next.comps_mut().zip(&keys) {
591	let Some(base) = base(*key) else {
592	continue;
593	};
594	for e in &mut c.c.entries {
595	match e.name {
596	ICalendarProperty::Attendee if !address(e).is_some_and(me) => {
597	if let Some(b) = same_attendee(&base.c, e) {
598	e.params = b.params.clone();
599	}
600	}
601	ICalendarProperty::Organizer => {
602	force \|= param(e, &ICalendarParameterName::ScheduleForceSend)
603	.is_some_and(\|v\| v.eq_ignore_ascii_case("REPLY"));
604	if let Some(b) = base.c.property(&ICalendarProperty::Organizer) {
605	e.params = b.params.clone();
606	}
607	}
608	_ => {}
609	}
610	}
611	}
612
613	let mut replied: Vec<Node> = Vec::new();
614	for (c, key) in next.comps().zip(&keys) {
615	let now_stat = own_partstat(&c.c, me);
616	let before = base(*key).and_then(\|b\| own_partstat(&b.c, me));
617	if now_stat.is_some() && (force \|\| now_stat != before) {
618	replied.push(reply_part(c, me));
619	}
620	}
621	// A dropped override falls back to the series' answer for that instance.
622	for (k, held) in reverted {
623	let Some(inst) = DateTime::from_timestamp(k, 0).and_then(\|t\| next.single(t, &Zone::Utc))
624	else {
625	continue;
626	};
627	if own_partstat(&inst.c, me).is_some_and(\|now\| Some(now) != held) {
628	replied.push(reply_part(&inst, me));
629	}
630	}
631	if let Some(m) = next.master() {
632	let before = master.map_or_else(HashSet::new, \|om\| {
633	old.times(&om.c, &ICalendarProperty::Exdate)
634	});
635	for e in m.c.properties(&ICalendarProperty::Exdate) {
636	for value in &e.values {
637	if before.contains(&next.value_key(e, value)) {
638	continue;
639	}
640	let rid = ICalendarEntry {
641	name: ICalendarProperty::RecurrenceId,
642	params: e.params.clone(),
643	values: vec![value.clone()],
644	};
645	replied.push(declined_instance(m, rid, me));
646	}
647	}
648	}
649
650	let reply = match replied.is_empty() {
651	true => None,
652	false => next.organizer().map(\|to\| Message {
653	to,
654	method: Method::Reply,
655	quiet: false,
656	cal: Arc::new(next.envelope(replied, Method::Reply, now)),
657	}),
658	};
659	Ok((next.done(), reply))
660	}
661
662	/// An attendee's DELETE: the REPLY declining every instance, unless the
663	/// organizer handles scheduling itself or already cancelled.
664	pub fn decline(old: &ICalendar, me: Is, now: DateTime<Utc>) -> Option<Message> {
665	let old = Obj::new(old);
666	if !old.organizer_schedules() {
667	return None;
668	}
669	let cancelled = old.comps().all(\|c\| {
670	c.c.property(&ICalendarProperty::Status)
671	.and_then(\|e\| e.values.first()?.as_text())
672	.is_some_and(\|s\| s.eq_ignore_ascii_case("CANCELLED"))
673	});
674	if cancelled {
675	return None;
676	}
677	let comps: Vec<Node> =
678	old.comps()
679	.filter(\|c\| own_partstat(&c.c, me).is_some())
680	.map(\|c\| {
681	let mut part = reply_part(c, me);
682	for e in
683	part.c.entries.iter_mut().filter(\|e\| {
684	e.name == ICalendarProperty::Attendee && address(e).is_some_and(me)
685	})
686	{
687	set_param(
688	e,
689	ICalendarParameterName::Partstat,
690	partstat(ICalendarParticipationStatus::Declined),
691	);
692	}
693	part
694	})
695	.collect();
696	if comps.is_empty() {
697	return None;
698	}
699	Some(Message {
700	to: old.organizer()?,
701	method: Method::Reply,
702	quiet: false,
703	cal: Arc::new(old.envelope(comps, Method::Reply, now)),
704	})
705	}
706
707	/// A REQUEST or CANCEL applied to the attendee's copy. `None`: nothing to
708	/// store.
709	pub fn receive(copy: Option<&ICalendar>, msg: &Message) -> Option<ICalendar> {
710	match msg.method {
711	Method::Request => {
712	if msg.quiet && copy.is_none() {
713	return None;
714	}
715	let copy = copy.map(Obj::new);
716	let mut next = Obj::new(&msg.cal);
717	next.root
718	.c
719	.entries
720	.retain(\|e\| e.name != ICalendarProperty::Method);
721	let keys: Vec<Option<i64>> = next.comps().map(\|c\| next.key(&c.c)).collect();
722	let Some(copy) = copy else {
723	return Some(next.done());
724	};
725	// What the attendee may keep for itself (RFC 6638, 3.2.2.1).
726	for (c, key) in next.comps_mut().zip(&keys) {
727	let Some(base) = copy.find(*key).or(copy.master()) else {
728	continue;
729	};
730	c.children
731	.retain(\|n\| n.c.component_type != ICalendarComponentType::VAlarm);
732	c.children.extend(
733	base.children
734	.iter()
735	.filter(\|n\| n.c.component_type == ICalendarComponentType::VAlarm)
736	.cloned(),
737	);
738	for p in [
739	ICalendarProperty::Transp,
740	ICalendarProperty::PercentComplete,
741	ICalendarProperty::Completed,
742	] {
743	c.c.entries.retain(\|e\| e.name != p);
744	c.c.entries.extend(base.c.properties(&p).cloned());
745	}
746	let status = base
747	.c
748	.property(&ICalendarProperty::Organizer)
749	.and_then(\|e\| e.parameter(&ICalendarParameterName::ScheduleStatus))
750	.cloned();
751	if let Some(s) = status {
752	for e in
753	c.c.entries
754	.iter_mut()
755	.filter(\|e\| e.name == ICalendarProperty::Organizer)
756	{
757	set_param(e, ICalendarParameterName::ScheduleStatus, s.clone());
758	}
759	}
760	}
761	Some(next.done())
762	}
763	Method::Cancel => {
764	let msg_obj = Obj::new(&msg.cal);
765	let mut next = Obj::new(copy?);
766	let whole = msg_obj.master().is_some();
767	let gone: Vec<(i64, ICalendarEntry)> = msg_obj
768	.comps()
769	.filter_map(\|c\| {
770	let rid = c.c.property(&ICalendarProperty::RecurrenceId)?;
771	Some((msg_obj.instant(rid)?, rid.clone()))
772	})
773	.collect();
774	let range =
775	\|rid: &ICalendarEntry\| rid.parameter(&ICalendarParameterName::Range).cloned();
776	let hit = \|k: i64\| {
777	gone.iter()
778	.any(\|(g, rid)\| g == k \|\| (g < k && range(rid).is_some()))
779	};
780	// A cancelled range stands for later instances too, which an
781	// EXDATE cannot cover: the override carries the range.
782	let mut missing = Vec::new();
783	for (k, rid) in gone.iter().filter(\|_\| !whole) {
784	let Some(r) = range(rid) else { continue };
785	let at = next.position(Some(*k)).or_else(\|\| {
786	let n = next.single(DateTime::from_timestamp(*k, 0)?, &Zone::Utc)?;
787	Some(next.push(n))
788	});
789	let entry = at.and_then(\|at\| {
790	next.children_mut()[at]
791	.c
792	.entries
793	.iter_mut()
794	.find(\|e\| e.name == ICalendarProperty::RecurrenceId)
795	});
796	match entry {
797	Some(e) => set_param(e, ICalendarParameterName::Range, r),
798	None => missing.push(rid.clone()),
799	}
800	}
801	let keys: Vec<Option<i64>> = next.comps().map(\|c\| next.key(&c.c)).collect();
802	for (c, key) in next.comps_mut().zip(&keys) {
803	if whole \|\| key.is_some_and(hit) {
804	set_prop(
805	&mut c.c,
806	ICalendarProperty::Status,
807	ICalendarValue::Status(ICalendarStatus::Cancelled),
808	);
809	}
810	}
811	if !whole {
812	missing.extend(
813	gone.into_iter()
814	.filter(\|(k, rid)\| range(rid).is_none() && !keys.contains(&Some(*k)))
815	.map(\|(_, rid)\| rid),
816	);
817	let missing: Vec<ICalendarEntry> = missing
818	.into_iter()
819	.map(\|rid\| ICalendarEntry {
820	name: ICalendarProperty::Exdate,
821	params: without(rid.params, &ICalendarParameterName::Range),
822	values: rid.values,
823	})
824	.collect();
825	if let Some(m) = next
826	.comps_mut()
827	.find(\|c\| !c.c.has_property(&ICalendarProperty::RecurrenceId))
828	{
829	m.c.entries.extend(missing);
830	}
831	}
832	Some(next.done())
833	}
834	Method::Reply => None,
835	}
836	}
837
838	/// The RECURRENCE-IDs an expansion gives.
839	fn rids(e: &Expansion) -> HashSet<i64> {
840	e.instances
841	.iter()
842	.filter_map(\|i\| Some(i.recurrence_id?.timestamp()))
843	.collect()
844	}
845
846	/// What a REPLY did to the organizer object.
847	#[derive(Debug, Default)]
848	pub struct Applied {
849	pub changed: bool,
850	/// Parts left out: the object would pass `MAX_COMPONENTS`, or a
851	/// cut-short expansion cannot confirm the instance.
852	pub dropped: usize,
853	}
854
855	/// A REPLY applied to the organizer object.
856	pub fn apply_reply(org: &mut ICalendar, reply: &ICalendar, replier: Is) -> Applied {
857	let rep = Obj::new(reply);
858	let mut next = Obj::new(org);
859	let mut changed = false;
860	let mut dropped = 0;
861	let mut parts: Vec<&Node> = rep.comps().collect();
862	// In order: a range narrowed for one instance moves on to the next.
863	parts.sort_by_key(\|c\| rep.key(&c.c));
864	let missing: Vec<i64> = parts
865	.iter()
866	.filter_map(\|c\| rep.key(&c.c))
867	.filter(\|k\| next.position(Some(*k)).is_none())
868	.collect();
869	let (found, unknown) = next.instances(org, &missing);
870	// A reply may not grow the object past what a PUT of it may hold.
871	let mut size = org.components.len();
872	for rc in parts {
873	let key = rep.key(&rc.c);
874	let at = match next.position(key) {
875	Some(at) => {
876	if let Some(t) = key
877	&& !is_range(&rc.c)
878	&& let Some(rid) = DateTime::from_timestamp(t, 0)
879	{
880	// Narrowing copies the range to the next instance.
881	if is_range(&next.root.children[at].c)
882	&& size + nodes(&next.root.children[at]) > MAX_COMPONENTS
883	{
884	dropped += 1;
885	continue;
886	}
887	let had = next.root.children.len();
888	next.narrow(org, rid, t, &Zone::Utc);
889	size += next.root.children[had..].iter().map(nodes).sum::<usize>();
890	}
891	at
892	}
893	// A reply for one instance of the series gets its own override.
894	// Obj reads floating times in UTC; expand must match.
895	None => {
896	let Some((t, at)) = key.and_then(\|t\| Some((t, DateTime::from_timestamp(t, 0)?)))
897	else {
898	continue;
899	};
900	if unknown.contains(&t) {
901	dropped += 1;
902	continue;
903	}
904	if !found.contains(&t) {
905	continue;
906	}
907	let Some(inst) = next.single(at, &Zone::Utc) else {
908	continue;
909	};
910	if size + nodes(&inst) > MAX_COMPONENTS {
911	dropped += 1;
912	continue;
913	}
914	size += nodes(&inst);
915	next.push(inst)
916	}
917	};
918	// Attendee parameters leave the index as it is.
919	let target = &mut next.root.children[at];
920	if sequence(&rc.c) < sequence(&target.c) {
921	continue;
922	}
923	let Some(stat) =
924	rc.c.properties(&ICalendarProperty::Attendee)
925	.find(\|e\| address(e).is_some_and(replier))
926	.map(\|e\| {
927	e.parameter(&ICalendarParameterName::Partstat)
928	.cloned()
929	.unwrap_or(partstat(ICalendarParticipationStatus::NeedsAction))
930	})
931	else {
932	continue;
933	};
934	// The attendee writes these; only digits and dots are a status code.
935	let codes: Vec<String> =
936	rc.c.properties(&ICalendarProperty::RequestStatus)
937	.filter_map(\|e\| e.values.first()?.as_text())
938	.map(\|s\| {
939	let code = s.split(';').next().unwrap_or(s);
940	code.chars()
941	.filter(\|c\| c.is_ascii_digit() \|\| *c == '.')
942	.collect::<String>()
943	})
944	.filter(\|c\| !c.is_empty())
945	.collect();
946	let status = match codes.is_empty() {
947	true => "2.0".to_string(),
948	false => codes.join(","),
949	};
950	for e in
951	target.c.entries.iter_mut().filter(\|e\| {
952	e.name == ICalendarProperty::Attendee && address(e).is_some_and(replier)
953	})
954	{
955	changed \|= e.parameter(&ICalendarParameterName::Partstat) != Some(&stat);
956	set_param(e, ICalendarParameterName::Partstat, stat.clone());
957	set_param(e, ICalendarParameterName::ScheduleStatus, text(&status));
958	}
959	}
960	if changed {
961	*org = next.done();
962	}
963	Applied { changed, dropped }
964	}
965
966	// ---------------------------------------------------------------------------
967	// The organizer object
968	// ---------------------------------------------------------------------------
969
970	/// The client's organizer object with the attendee state the server owns:
971	/// their PARTSTAT (reset on a reschedule, RFC 6638 3.2.8) and
972	/// SCHEDULE-STATUS. Collects SCHEDULE-FORCE-SEND=REQUEST into `force`.
973	fn guard(
974	old: Option<&ICalendar>,
975	new: &ICalendar,
976	organizer: Is,
977	force: &mut Vec<String>,
978	) -> ICalendar {
979	let old = old.map(Obj::new);
980	let mut next = Obj::new(new);
981	// A new override takes the state of the THISANDFUTURE override that moves
982	// its instance, else of the master.
983	let base_of = \|key: Option<i64>\| {
984	let o = old.as_ref()?;
985	o.find(key)
986	.or_else(\|\| o.future(key?).map(\|(n, _)\| n))
987	.or(o.master())
988	};
989	let keys: Vec<Option<i64>> = next.comps().map(\|c\| next.key(&c.c)).collect();
990	let moved: Vec<bool> = next
991	.comps()
992	.map(\|c\| match &old {
993	Some(o) => match o.find(next.key(&c.c)) {
994	Some(oc) => rescheduled(o, &oc.c, &next, &c.c),
995	// A new override: rescheduled if it moves its instance.
996	None => {
997	let start =
998	c.c.property(&ICalendarProperty::Dtstart)
999	.and_then(\|e\| next.instant(e));
1000	let key = next.key(&c.c);
1001	key.is_none()
1002	\|\| start != key.map(\|k\| o.moved(k))
1003	\|\| base_of(key).is_some_and(\|b\| {
1004	next.end(&c.c) != start.and_then(\|s\| o.end_from(&b.c, s))
1005	})
1006	}
1007	},
1008	None => true,
1009	})
1010	.collect();
1011	let bumps: Vec<Option<i64>> = keys
1012	.iter()
1013	.zip(next.comps())
1014	.zip(&moved)
1015	.map(\|((key, c), moved)\| {
1016	let oc = base_of(*key)?;
1017	(*moved && sequence(&c.c) <= sequence(&oc.c)).then(\|\| sequence(&oc.c).saturating_add(1))
1018	})
1019	.collect();
1020
1021	for ((c, key), (moved, bump)) in next.comps_mut().zip(&keys).zip(moved.iter().zip(&bumps)) {
1022	let base = base_of(*key);
1023	for e in &mut c.c.entries {
1024	match e.name {
1025	ICalendarProperty::Organizer => {
1026	remove_param(e, &ICalendarParameterName::ScheduleForceSend);
1027	}
1028	ICalendarProperty::Attendee => {
1029	let forced = param(e, &ICalendarParameterName::ScheduleForceSend)
1030	.is_some_and(\|v\| v.eq_ignore_ascii_case("REQUEST"));
1031	remove_param(e, &ICalendarParameterName::ScheduleForceSend);
1032	let Some(a) = address(e).map(str::to_string) else {
1033	continue;
1034	};
1035	if organizer(&a) \|\| !server_agent(e) {
1036	continue;
1037	}
1038	if forced {
1039	force.push(a.clone());
1040	}
1041	let prev = base.and_then(\|b\| same_attendee(&b.c, e));
1042	let stat = match (moved, prev) {
1043	(false, Some(p)) => p
1044	.parameter(&ICalendarParameterName::Partstat)
1045	.cloned()
1046	.unwrap_or(partstat(ICalendarParticipationStatus::NeedsAction)),
1047	_ => partstat(ICalendarParticipationStatus::NeedsAction),
1048	};
1049	set_param(e, ICalendarParameterName::Partstat, stat);
1050	match prev.and_then(\|p\| p.parameter(&ICalendarParameterName::ScheduleStatus)) {
1051	Some(s) => set_param(e, ICalendarParameterName::ScheduleStatus, s.clone()),
1052	None => remove_param(e, &ICalendarParameterName::ScheduleStatus),
1053	}
1054	}
1055	_ => {}
1056	}
1057	}
1058	if let Some(n) = bump {
1059	set_prop(
1060	&mut c.c,
1061	ICalendarProperty::Sequence,
1062	ICalendarValue::Integer(*n),
1063	);
1064	}
1065	}
1066	next.done()
1067	}
1068
1069	/// Whether a change moves instances in time (RFC 6638, 3.2.8). Shortening a
1070	/// series or excluding instances does not.
1071	fn rescheduled(old: &Obj, oc: &ICalendarComponent, new: &Obj, nc: &ICalendarComponent) -> bool {
1072	let moved = [ICalendarProperty::Dtstart, ICalendarProperty::Rdate]
1073	.iter()
1074	.any(\|p\| old.times(oc, p) != new.times(nc, p))
1075	\|\| old.end(oc) != new.end(nc);
1076	let reinstated = !old
1077	.times(oc, &ICalendarProperty::Exdate)
1078	.is_subset(&new.times(nc, &ICalendarProperty::Exdate));
1079	// A changed or removed EXRULE can bring instances back; a new one cannot.
1080	let exrules = (
1081	rules(oc, &ICalendarProperty::Exrule),
1082	rules(nc, &ICalendarProperty::Exrule),
1083	);
1084	let exrule_changed = !exrules.0.is_empty() && exrules.0 != exrules.1;
1085	moved \|\| reinstated \|\| exrule_changed \|\| rules_grew(old, oc, new, nc)
1086	}
1087
1088	/// A rule in one form: BY lists sorted, INTERVAL=1 as absent, and WKST
1089	/// absent where it cannot change the instances.
1090	fn canonical(r: &ICalendarRecurrenceRule) -> ICalendarRecurrenceRule {
1091	fn tidy<T: Ord>(v: &mut Vec<T>) {
1092	v.sort();
1093	v.dedup();
1094	}
1095	let mut r = r.clone();
1096	tidy(&mut r.bysecond);
1097	tidy(&mut r.byminute);
1098	tidy(&mut r.byhour);
1099	tidy(&mut r.byday);
1100	tidy(&mut r.bymonthday);
1101	tidy(&mut r.byyearday);
1102	tidy(&mut r.byweekno);
1103	tidy(&mut r.bymonth);
1104	tidy(&mut r.bysetpos);
1105	r.interval = r.interval.filter(\|i\| *i > 1);
1106	// WKST only bounds weeks of a WEEKLY rule that skips weeks or picks by
1107	// BYSETPOS, and the weeks of BYWEEKNO (RFC 5545, 3.3.10).
1108	let weeks =
1109	r.freq == ICalendarFrequency::Weekly && (r.interval.is_some() \|\| !r.bysetpos.is_empty());
1110	if !weeks && r.byweekno.is_empty() {
1111	r.wkst = None;
1112	}
1113	r.wkst = r.wkst.filter(\|w\| *w != ICalendarWeekday::Monday);
1114	r
1115	}
1116
1117	fn rules(c: &ICalendarComponent, prop: &ICalendarProperty) -> Vec<ICalendarRecurrenceRule> {
1118	let mut v: Vec<_> = c
1119	.properties(prop)
1120	.filter_map(\|e\| match e.values.first()? {
1121	ICalendarValue::RecurrenceRule(r) => Some(canonical(r)),
1122	_ => None,
1123	})
1124	.collect();
1125	v.sort_by_key(\|r\| format!("{r:?}"));
1126	v
1127	}
1128
1129	fn rules_grew(old: &Obj, oc: &ICalendarComponent, new: &Obj, nc: &ICalendarComponent) -> bool {
1130	let rules = \|c\| rules(c, &ICalendarProperty::Rrule);
1131	let (o, n) = (rules(oc), rules(nc));
1132	if o == n {
1133	return false;
1134	}
1135	let (o, n) = match (&o[..], &n[..]) {
1136	// Dropping the rule leaves the first instance only.
1137	([_, ..], []) => return false,
1138	([o], [n]) => (o, n),
1139	_ => return true,
1140	};
1141	if !same_starts(old, oc, o, new, nc, n) {
1142	return true;
1143	}
1144	match (bounded(o), bounded(n)) {
1145	(true, false) => true,
1146	(false, _) => false,
1147	(true, true) => new
1148	.compare_ends(nc, o, n)
1149	.is_none_or(\|c\| c == Ordering::Greater),
1150	}
1151	}
1152
1153	/// Whether an attendee's copy keeps the organizer's rule. Clients rewrite
1154	/// UNTIL, swap COUNT for UNTIL, or name the start's weekday, month or day,
1155	/// so forms that may give the same instances compare by them.
1156	fn same_rules(old: &Obj, oc: &ICalendarComponent, new: &Obj, nc: &ICalendarComponent) -> bool {
1157	let (o, n) = (
1158	rules(oc, &ICalendarProperty::Rrule),
1159	rules(nc, &ICalendarProperty::Rrule),
1160	);
1161	if o == n {
1162	return true;
1163	}
1164	let ([o], [n]) = (&o[..], &n[..]) else {
1165	return false;
1166	};
1167	bounded(o) == bounded(n)
1168	&& same_starts(old, oc, o, new, nc, n)
1169	&& (!bounded(o) \|\| new.compare_ends(nc, o, n) == Some(Ordering::Equal))
1170	}
1171
1172	/// Whether rules `o` of `oc` and `n` of `nc`, without their ends, give the
1173	/// same starts.
1174	fn same_starts(
1175	old: &Obj,
1176	oc: &ICalendarComponent,
1177	o: &ICalendarRecurrenceRule,
1178	new: &Obj,
1179	nc: &ICalendarComponent,
1180	n: &ICalendarRecurrenceRule,
1181	) -> bool {
1182	if unbounded(o) == unbounded(n) {
1183	return true;
1184	}
1185	let loose = \|r: &ICalendarRecurrenceRule\| {
1186	let mut r = unbounded(r);
1187	match r.freq {
1188	ICalendarFrequency::Weekly => r.byday.clear(),
1189	ICalendarFrequency::Monthly => r.bymonthday.clear(),
1190	ICalendarFrequency::Yearly => {
1191	r.bymonth.clear();
1192	r.bymonthday.clear();
1193	}
1194	_ => {}
1195	}
1196	r
1197	};
1198	if loose(o) != loose(n) {
1199	return false;
1200	}
1201	// Weekdays and month days show within a year of periods. Leap days
1202	// show within two leap cycles, also where BYMONTH leaves one month a year.
1203	let yearly =
1204	n.freq == ICalendarFrequency::Yearly \|\| !o.bymonth.is_empty() \|\| !n.bymonth.is_empty();
1205	let days = match yearly {
1206	true => 8 * 366,
1207	false => 400,
1208	} * i64::from(n.interval.unwrap_or(1).max(1));
1209	let starts = \|obj: &Obj, c, r: &ICalendarRecurrenceRule\| {
1210	let c = with_rule(c, unbounded(r));
1211	let start = obj.start(&c)?;
1212	obj.rule_starts(c, start..add(start, TimeDelta::days(days)))
1213	};
1214	let a = starts(old, oc, o);
1215	a.is_some() && a == starts(new, nc, n)
1216	}
1217
1218	/// `c` with `r` as its only RRULE.
1219	fn with_rule(c: &ICalendarComponent, r: ICalendarRecurrenceRule) -> ICalendarComponent {
1220	let mut c = c.clone();
1221	let mut first = true;
1222	c.entries.retain_mut(\|e\| {
1223	if e.name != ICalendarProperty::Rrule {
1224	return true;
1225	}
1226	e.values = vec![ICalendarValue::RecurrenceRule(Box::new(r.clone()))];
1227	std::mem::take(&mut first)
1228	});
1229	c
1230	}
1231
1232	fn unbounded(r: &ICalendarRecurrenceRule) -> ICalendarRecurrenceRule {
1233	let mut r = r.clone();
1234	r.until = None;
1235	r.count = None;
1236	r
1237	}
1238
1239	fn bounded(r: &ICalendarRecurrenceRule) -> bool {
1240	r.count.is_some() \|\| r.until.is_some()
1241	}
1242
1243	fn cancelled(comps: Vec<Node>) -> Vec<Node> {
1244	comps
1245	.into_iter()
1246	.map(\|mut n\| {
1247	set_prop(
1248	&mut n.c,
1249	ICalendarProperty::Status,
1250	ICalendarValue::Status(ICalendarStatus::Cancelled),
1251	);
1252	let seq = sequence(&n.c).saturating_add(1);
1253	set_prop(
1254	&mut n.c,
1255	ICalendarProperty::Sequence,
1256	ICalendarValue::Integer(seq),
1257	);
1258	n
1259	})
1260	.collect()
1261	}
1262
1263	/// How an attendee's view changed.
1264	#[derive(Clone, Copy)]
1265	enum Change {
1266	/// More than the participation of others.
1267	Content,
1268	/// Only the participation of others.
1269	Answers,
1270	/// Only the SEQUENCE.
1271	Sequence,
1272	None,
1273	}
1274
1275	fn change(before: &[Node], after: &[Node]) -> Change {
1276	let sequences = \|comps: &[Node]\| {
1277	let mut v: Vec<i64> = comps.iter().map(\|n\| sequence(&n.c)).collect();
1278	v.sort_unstable();
1279	v
1280	};
1281	if normalized(before, true) != normalized(after, true) {
1282	Change::Content
1283	} else if normalized(before, false) != normalized(after, false) {
1284	Change::Answers
1285	} else if sequences(before) != sequences(after) {
1286	Change::Sequence
1287	} else {
1288	Change::None
1289	}
1290	}
1291
1292	/// For comparing what an attendee would receive: without the stamps a
1293	/// client rewrites on every save, and optionally without participation.
1294	fn normalized(comps: &[Node], without_partstat: bool) -> Vec<Node> {
1295	let mut out = comps
1296	.iter()
1297	.map(\|n\| {
1298	let mut n = n.clone();
1299	n.c.entries.retain(\|e\| {
1300	!matches!(
1301	e.name,
1302	ICalendarProperty::Dtstamp
1303	\| ICalendarProperty::LastModified
1304	\| ICalendarProperty::Created
1305	\| ICalendarProperty::Sequence
1306	) && !matches!(&e.name, ICalendarProperty::Other(x) if x.to_ascii_uppercase().starts_with("X-"))
1307	});
1308	// A new SENT-BY alone is no change for an attendee.
1309	for e in n.c.entries.iter_mut().filter(\|e\| {
1310	matches!(
1311	e.name,
1312	ICalendarProperty::Organizer \| ICalendarProperty::Attendee
1313	)
1314	}) {
1315	remove_param(e, &ICalendarParameterName::SentBy);
1316	}
1317	if without_partstat {
1318	for e in n.c.entries.iter_mut().filter(\|e\| e.name == ICalendarProperty::Attendee) {
1319	remove_param(e, &ICalendarParameterName::Partstat);
1320	}
1321	}
1322	sorted(&mut n);
1323	n
1324	})
1325	.collect::<Vec<_>>();
1326	out.sort_by_cached_key(\|n\| format!("{n:?}"));
1327	out
1328	}
1329
1330	/// In one order, so another client's order of properties is no change.
1331	fn sorted(n: &mut Node) {
1332	for e in &mut n.c.entries {
1333	e.params.sort_by_cached_key(\|p\| format!("{p:?}"));
1334	}
1335	n.c.entries.sort_by_cached_key(\|e\| format!("{e:?}"));
1336	for ch in &mut n.children {
1337	sorted(ch);
1338	}
1339	n.children.sort_by_cached_key(\|ch\| format!("{ch:?}"));
1340	}
1341
1342	/// A component of the attendee's REPLY: only its own ATTENDEE, no alarms.
1343	fn reply_part(c: &Node, me: Is) -> Node {
1344	let mut n = Node {
1345	c: c.c.clone(),
1346	children: Vec::new(),
1347	};
1348	n.c.entries
1349	.retain(\|e\| e.name != ICalendarProperty::Attendee \|\| address(e).is_some_and(me));
1350	strip_scheduling_params(&mut n.c);
1351	n
1352	}
1353
1354	/// The REPLY component for an instance the attendee excluded with EXDATE.
1355	fn declined_instance(master: &Node, rid: ICalendarEntry, me: Is) -> Node {
1356	let mut c = ICalendarComponent {
1357	component_type: master.c.component_type.clone(),
1358	entries: Vec::new(),
1359	component_ids: Vec::new(),
1360	};
1361	for p in [
1362	ICalendarProperty::Uid,
1363	ICalendarProperty::Sequence,
1364	ICalendarProperty::Organizer,
1365	ICalendarProperty::Summary,
1366	] {
1367	c.entries.extend(master.c.properties(&p).cloned());
1368	}
1369	c.entries.push(ICalendarEntry {
1370	name: ICalendarProperty::Dtstart,
1371	..rid.clone()
1372	});
1373	c.entries.push(rid);
1374	for e in master
1375	.c
1376	.properties(&ICalendarProperty::Attendee)
1377	.filter(\|e\| address(e).is_some_and(me))
1378	{
1379	let mut e = e.clone();
1380	set_param(
1381	&mut e,
1382	ICalendarParameterName::Partstat,
1383	partstat(ICalendarParticipationStatus::Declined),
1384	);
1385	c.entries.push(e);
1386	}
1387	strip_scheduling_params(&mut c);
1388	Node {
1389	c,
1390	children: Vec::new(),
1391	}
1392	}
1393
1394	// ---------------------------------------------------------------------------
1395	// The object as a tree
1396	// ---------------------------------------------------------------------------
1397
1398	/// A component with its sub-components, detached from the flat list calcard
1399	/// keeps.
1400	#[derive(Debug, Clone, PartialEq)]
1401	struct Node {
1402	/// `component_ids` is empty; `children` replaces it.
1403	c: ICalendarComponent,
1404	children: Vec<Node>,
1405	}
1406
1407	fn node(cal: &ICalendar, i: usize) -> Node {
1408	let mut c = cal.components[i].clone();
1409	let ids = std::mem::take(&mut c.component_ids);
1410	let children = ids
1411	.iter()
1412	.map(\|&id\| id as usize)
1413	.filter(\|&id\| id > i && id < cal.components.len())
1414	.map(\|id\| node(cal, id))
1415	.collect();
1416	Node { c, children }
1417	}
1418
1419	/// How many components `n` flattens to.
1420	fn nodes(n: &Node) -> usize {
1421	1 + n.children.iter().map(nodes).sum::<usize>()
1422	}
1423
1424	fn flatten(n: &Node, out: &mut Vec<ICalendarComponent>) -> u32 {
1425	let at = out.len();
1426	out.push(n.c.clone());
1427	for ch in &n.children {
1428	let id = flatten(ch, out);
1429	out[at].component_ids.push(id);
1430	}
1431	at as u32
1432	}
1433
1434	/// A calendar object: the VCALENDAR with its time zones and components.
1435	struct Obj {
1436	/// Change its children only through `children_mut` or `comps_mut`, which
1437	/// drop `index`, or `push`, which keeps it.
1438	root: Node,
1439	zones: Zones,
1440	index: OnceCell<Index>,
1441	/// Occurrences left for comparing rules. Spent, a rule change counts as
1442	/// growth for the organizer and is refused from an attendee.
1443	budget: Cell<usize>,
1444	}
1445
1446	const RULE_BUDGET: usize = 100_000;
1447
1448	/// Lookups over `Obj::root`, built on first use.
1449	struct Index {
1450	/// The first scheduled component with each key.
1451	by_key: HashMap<Option<i64>, usize>,
1452	/// THISANDFUTURE overrides by key, ascending.
1453	ranges: Vec<(i64, usize)>,
1454	/// Answers of `Obj::in_series`, which expands.
1455	in_series: RefCell<HashMap<i64, bool>>,
1456	/// The expansion for all ranges at once was cut short.
1457	ranges_cut: Cell<bool>,
1458	}
1459
1460	impl Obj {
1461	fn new(cal: &ICalendar) -> Self {
1462	let root = match cal.components.is_empty() {
1463	true => Node {
1464	c: ICalendarComponent {
1465	component_type: ICalendarComponentType::VCalendar,
1466	entries: Vec::new(),
1467	component_ids: Vec::new(),
1468	},
1469	children: Vec::new(),
1470	},
1471	false => node(cal, 0),
1472	};
1473	Obj {
1474	root,
1475	zones: Zones::new(cal, Zone::Utc),
1476	index: OnceCell::new(),
1477	budget: Cell::new(RULE_BUDGET),
1478	}
1479	}
1480
1481	fn index(&self) -> &Index {
1482	self.index.get_or_init(\|\| {
1483	let mut by_key = HashMap::new();
1484	let mut ranges = Vec::new();
1485	for (i, n) in self.root.children.iter().enumerate() {
1486	if !is_scheduled(&n.c) {
1487	continue;
1488	}
1489	let key = self.key(&n.c);
1490	by_key.entry(key).or_insert(i);
1491	if let Some(k) = key.filter(\|_\| is_range(&n.c)) {
1492	ranges.push((k, i));
1493	}
1494	}
1495	ranges.sort_by_key(\|(k, _)\| *k);
1496	Index {
1497	by_key,
1498	ranges,
1499	in_series: RefCell::default(),
1500	ranges_cut: Cell::default(),
1501	}
1502	})
1503	}
1504
1505	fn children_mut(&mut self) -> &mut Vec<Node> {
1506	self.index.take();
1507	&mut self.root.children
1508	}
1509
1510	/// Appends a child and returns where it is.
1511	fn push(&mut self, n: Node) -> usize {
1512	let at = self.root.children.len();
1513	let key = is_scheduled(&n.c).then(\|\| self.key(&n.c));
1514	let range = is_range(&n.c);
1515	self.root.children.push(n);
1516	if let (Some(ix), Some(key)) = (self.index.get_mut(), key) {
1517	ix.by_key.entry(key).or_insert(at);
1518	if let Some(k) = key.filter(\|_\| range) {
1519	let p = ix.ranges.partition_point(\|(r, _)\| *r <= k);
1520	ix.ranges.insert(p, (k, at));
1521	}
1522	}
1523	at
1524	}
1525
1526	fn done(self) -> ICalendar {
1527	let mut components = Vec::new();
1528	flatten(&self.root, &mut components);
1529	ICalendar { components }
1530	}
1531
1532	fn comps(&self) -> impl Iterator<Item = &Node> {
1533	self.root.children.iter().filter(\|n\| is_scheduled(&n.c))
1534	}
1535
1536	fn comps_mut(&mut self) -> impl Iterator<Item = &mut Node> {
1537	self.children_mut()
1538	.iter_mut()
1539	.filter(\|n\| is_scheduled(&n.c))
1540	}
1541
1542	fn master(&self) -> Option<&Node> {
1543	self.find(None)
1544	}
1545
1546	fn find(&self, key: Option<i64>) -> Option<&Node> {
1547	Some(&self.root.children[self.position(key)?])
1548	}
1549
1550	fn position(&self, key: Option<i64>) -> Option<usize> {
1551	self.index().by_key.get(&key).copied()
1552	}
1553
1554	/// The RECURRENCE-ID as an instant; `None` for the master.
1555	fn key(&self, c: &ICalendarComponent) -> Option<i64> {
1556	self.instant(c.property(&ICalendarProperty::RecurrenceId)?)
1557	}
1558
1559	/// The first value of a date or date-time property, in UTC seconds.
1560	/// Dates count from midnight, whatever the zone.
1561	fn instant(&self, e: &ICalendarEntry) -> Option<i64> {
1562	let v = e.values.first()?.as_partial_date_time()?;
1563	self.at(v, e.tz_id())
1564	}
1565
1566	fn at(&self, v: &PartialDateTime, tzid: Option<&str>) -> Option<i64> {
1567	let dt = v.to_date_time()?;
1568	Some(match dt.offset {
1569	_ if v.hour.is_none() => dt.date_time.and_utc().timestamp(),
1570	Some(o) => dt.date_time.and_utc().timestamp() - i64::from(o.local_minus_utc()),
1571	None => self.zones.get(tzid).to_utc(dt.date_time).timestamp(),
1572	})
1573	}
1574
1575	/// Every value of a property, comparable across encodings: instants for
1576	/// dates and date-times, the text otherwise.
1577	fn times(&self, c: &ICalendarComponent, prop: &ICalendarProperty) -> HashSet<String> {
1578	c.properties(prop)
1579	.flat_map(\|e\| e.values.iter().map(move \|v\| self.value_key(e, v)))
1580	.collect()
1581	}
1582
1583	fn value_key(&self, e: &ICalendarEntry, v: &ICalendarValue) -> String {
1584	match v.as_partial_date_time() {
1585	Some(p) => match self.at(p, e.tz_id()) {
1586	Some(t) if p.hour.is_none() => format!("{t}d"),
1587	Some(t) => t.to_string(),
1588	None => format!("{v:?}"),
1589	},
1590	None => match v {
1591	ICalendarValue::RecurrenceRule(r) => format!("{:?}", canonical(r)),
1592	_ => format!("{v:?}"),
1593	},
1594	}
1595	}
1596
1597	fn organizer(&self) -> Option<String> {
1598	self.comps()
1599	.find_map(\|c\| address(c.c.property(&ICalendarProperty::Organizer)?))
1600	.map(str::to_string)
1601	}
1602
1603	/// Whether the server replies for the attendee (RFC 6638, 3.2.2).
1604	fn organizer_schedules(&self) -> bool {
1605	self.comps()
1606	.filter_map(\|c\| c.c.property(&ICalendarProperty::Organizer))
1607	.all(server_agent)
1608	}
1609
1610	/// Per child of `root`, the addresses it invites through the server,
1611	/// lowercase.
1612	fn invitations(&self) -> Vec<HashSet<String>> {
1613	self.root
1614	.children
1615	.iter()
1616	.map(\|n\| match is_scheduled(&n.c) {
1617	true => attendees(&n.c)
1618	.filter(\|e\| server_agent(e))
1619	.filter_map(address)
1620	.map(str::to_ascii_lowercase)
1621	.collect(),
1622	false => HashSet::new(),
1623	})
1624	.collect()
1625	}
1626
1627	/// What an attendee sees (RFC 6638, 3.2.6), given which children invite
1628	/// them. Overrides they are not in become EXDATEs. A THISANDFUTURE
1629	/// override they are not in ends their series.
1630	fn view(&self, invited: &[bool]) -> Option<Vec<Node>> {
1631	let overrides = \|\| {
1632	self.root.children.iter().enumerate().filter(\|(_, c)\| {
1633	is_scheduled(&c.c) && c.c.has_property(&ICalendarProperty::RecurrenceId)
1634	})
1635	};
1636	let mut out = Vec::new();
1637	let master = self
1638	.position(None)
1639	.filter(\|i\| invited[*i])
1640	.map(\|i\| &self.root.children[i]);
1641	if let Some(m) = master {
1642	let mut m = m.clone();
1643	let mut end: Option<i64> = None;
1644	for (i, o) in overrides() {
1645	let Some(rid) = o.c.property(&ICalendarProperty::RecurrenceId) else {
1646	continue;
1647	};
1648	if invited[i] {
1649	continue;
1650	}
1651	if is_range(&o.c) {
1652	// ponytail: a later range that invites them again is lost too.
1653	// A stale range past the series' end cuts nothing.
1654	if let Some(t) = self.instant(rid).filter(\|t\| self.in_series(*t)) {
1655	end = Some(end.map_or(t, \|e\| e.min(t)));
1656	}
1657	continue;
1658	}
1659	m.c.entries.push(ICalendarEntry {
1660	name: ICalendarProperty::Exdate,
1661	params: without(rid.params.clone(), &ICalendarParameterName::Range),
1662	values: rid.values.clone(),
1663	});
1664	}
1665	let first =
1666	m.c.property(&ICalendarProperty::Dtstart)
1667	.and_then(\|e\| self.instant(e));
1668	match end {
1669	// The range starts with the first instance: none is left.
1670	Some(t) if first.is_some_and(\|f\| t <= f) => {}
1671	Some(t) => {
1672	self.end_series(&mut m.c, t);
1673	out.push(m);
1674	}
1675	None => out.push(m),
1676	}
1677	}
1678	out.extend(
1679	overrides()
1680	.filter(\|(i, _)\| invited[*i])
1681	.map(\|(_, c)\| c.clone()),
1682	);
1683	for n in &mut out {
1684	n.children
1685	.retain(\|ch\| ch.c.component_type != ICalendarComponentType::VAlarm);
1686	strip_scheduling_params(&mut n.c);
1687	}
1688	(!out.is_empty()).then_some(out)
1689	}
1690
1691	/// Whether override `c`, read through `obj`, is instance `key` of this
1692	/// series unchanged: its start, length and people, no rules of its own.
1693	fn plain(&self, obj: &Obj, c: &ICalendarComponent, key: i64, added: bool) -> bool {
1694	let Some(base) = self.base(key) else {
1695	return false;
1696	};
1697	let start = c
1698	.property(&ICalendarProperty::Dtstart)
1699	.and_then(\|e\| obj.instant(e));
1700	start == Some(self.moved(key))
1701	&& [
1702	ICalendarProperty::Rrule,
1703	ICalendarProperty::Rdate,
1704	ICalendarProperty::Exrule,
1705	]
1706	.iter()
1707	.all(\|p\| !c.has_property(p))
1708	&& obj.end(c) == self.end_from(&base.c, self.moved(key))
1709	&& organizer_of(c) == organizer_of(&base.c)
1710	&& addresses(c) == addresses(&base.c)
1711	&& (c.status() == base.c.status()
1712	\|\| own_progress(c, &base.c)
1713	// Some clients mark the instance they answer as confirmed.
1714	\|\| added
1715	&& base.c.status().is_none()
1716	&& c.status() == Some(&ICalendarStatus::Confirmed))
1717	}
1718
1719	/// Whether the master's own rules have an instance at `key`.
1720	fn in_series(&self, key: i64) -> bool {
1721	let ix = self.index();
1722	if let Some(&k) = ix.in_series.borrow().get(&key) {
1723	return k;
1724	}
1725	// One expansion answers every range override at once.
1726	let mut keys = vec![key];
1727	if !ix.ranges_cut.get() {
1728	keys.extend(ix.ranges.iter().map(\|(k, _)\| *k));
1729	}
1730	// Cut short, the batch falls back to the key alone with the full cap.
1731	let cap = match keys.len() {
1732	1 => MAX_OCCURRENCES,
1733	_ => RULE_BUDGET,
1734	};
1735	let (mut found, cut) = self.expands_to(&keys, cap);
1736	if cut && keys.len() > 1 {
1737	ix.ranges_cut.set(true);
1738	keys = vec![key];
1739	found = self.expands_to(&keys, MAX_OCCURRENCES).0;
1740	}
1741	let mut memo = ix.in_series.borrow_mut();
1742	for k in keys {
1743	memo.insert(k, found.contains(&k));
1744	}
1745	memo[&key]
1746	}
1747
1748	/// Which of `keys` the master's own rules reach, and whether the
1749	/// expansion was cut short.
1750	fn expands_to(&self, keys: &[i64], cap: usize) -> (HashSet<i64>, bool) {
1751	let at = \|t: Option<&i64>\| DateTime::from_timestamp(*t?, 0);
1752	let (Some(m), Some(from), Some(to)) =
1753	(self.master(), at(keys.iter().min()), at(keys.iter().max()))
1754	else {
1755	return (HashSet::new(), false);
1756	};
1757	let window = from - TimeDelta::days(1)..to + TimeDelta::days(1);
1758	let e = expand_in(&self.alone(m.c.clone()), &self.zones, window, cap);
1759	(rids(&e), e.truncated)
1760	}
1761
1762	/// The DTSTART of `c` as an instant.
1763	fn start(&self, c: &ICalendarComponent) -> Option<DateTime<Utc>> {
1764	DateTime::from_timestamp(self.instant(c.property(&ICalendarProperty::Dtstart)?)?, 0)
1765	}
1766
1767	/// The starts the RRULE of `c` gives in `window`, without RDATE, EXDATE
1768	/// and EXRULE. `None` if the expansion was cut short.
1769	fn rule_starts(
1770	&self,
1771	mut c: ICalendarComponent,
1772	window: std::ops::Range<DateTime<Utc>>,
1773	) -> Option<Vec<i64>> {
1774	c.entries.retain(\|e\| {
1775	!matches!(
1776	e.name,
1777	ICalendarProperty::Rdate
1778	\| ICalendarProperty::Exdate
1779	\| ICalendarProperty::Exrule
1780	\| ICalendarProperty::RecurrenceId
1781	)
1782	});
1783	let left = self.budget.get();
1784	let e = expand_in(&self.alone(c), &self.zones, window, left);
1785	if e.truncated {
1786	self.budget.set(0);
1787	return None;
1788	}
1789	self.budget.set(left.saturating_sub(e.generated));
1790	let mut v: Vec<i64> = e
1791	.instances
1792	.iter()
1793	.map(\|i\| i.recurrence_id.unwrap_or(i.start).timestamp())
1794	.collect();
1795	v.sort_unstable();
1796	Some(v)
1797	}
1798
1799	/// How the instances `n` keeps compare with those `o` keeps, for rules of
1800	/// `c` that differ only in COUNT or UNTIL. `Greater` if `n` keeps more.
1801	/// Only COUNT, or the gap between two UNTILs, is expanded.
1802	fn compare_ends(
1803	&self,
1804	c: &ICalendarComponent,
1805	o: &ICalendarRecurrenceRule,
1806	n: &ICalendarRecurrenceRule,
1807	) -> Option<Ordering> {
1808	let dtstart = c.property(&ICalendarProperty::Dtstart)?;
1809	let s = stamp(
1810	&self.zones,
1811	dtstart.values.first()?.as_partial_date_time()?,
1812	dtstart.tz_id(),
1813	)?;
1814	let end = \|u: &PartialDateTime\| Some(until_utc(u, &s)?.timestamp());
1815	let start = self.start(c)?;
1816	// The last start COUNT keeps and the one after it.
1817	let counted = \|k: u32\| {
1818	let mut r = o.clone();
1819	r.until = None;
1820	r.count = Some(k + 1);
1821	let v = self.rule_starts(with_rule(c, r), start..DateTime::<Utc>::MAX_UTC)?;
1822	Some((
1823	v.get((k as usize).checked_sub(1)?).copied(),
1824	v.get(k as usize).copied(),
1825	))
1826	};
1827	// Whether COUNT keeps more (`Greater`) than an UNTIL at `u`.
1828	let count_vs_until = \|k: u32, u: i64\| {
1829	let (last, next) = counted(k)?;
1830	Some(if last.is_some_and(\|l\| l > u) {
1831	Ordering::Greater
1832	} else if next.is_some_and(\|x\| x <= u) {
1833	Ordering::Less
1834	} else {
1835	Ordering::Equal
1836	})
1837	};
1838	match (o.count, &o.until, n.count, &n.until) {
1839	(Some(a), None, Some(b), None) => Some(b.cmp(&a)),
1840	(None, Some(a), None, Some(b)) => {
1841	let (a, b) = (end(a)?, end(b)?);
1842	if a == b {
1843	return Some(Ordering::Equal);
1844	}
1845	let (lo, hi) = (a.min(b), a.max(b));
1846	let at = \|t: i64\| DateTime::from_timestamp(t + 1, 0);
1847	let mut r = o.clone();
1848	r.until = None;
1849	let between = self.rule_starts(with_rule(c, r), at(lo)?..at(hi)?);
1850	// The window also holds instances that only overlap it.
1851	Some(match between {
1852	Some(v) if v.iter().all(\|t\| t <= lo \|\| t > hi) => Ordering::Equal,
1853	_ => b.cmp(&a),
1854	})
1855	}
1856	(Some(k), None, None, Some(u)) => count_vs_until(k, end(u)?).map(Ordering::reverse),
1857	(None, Some(u), Some(k), None) => count_vs_until(k, end(u)?),
1858	_ => None,
1859	}
1860	}
1861
1862	/// A calendar of `c` alone, to expand with this object's zones.
1863	fn alone(&self, c: ICalendarComponent) -> ICalendar {
1864	let root = Node {
1865	c: self.root.c.clone(),
1866	children: vec![Node {
1867	c,
1868	children: Vec::new(),
1869	}],
1870	};
1871	let mut components = Vec::new();
1872	flatten(&root, &mut components);
1873	ICalendar { components }
1874	}
1875
1876	/// What instance `key` copies: the THISANDFUTURE override that moves it,
1877	/// else the master.
1878	fn base(&self, key: i64) -> Option<&Node> {
1879	self.future(key).map(\|(n, _)\| n).or(self.master())
1880	}
1881
1882	/// When the component ends: DTSTART plus its length, else its DUE.
1883	fn end(&self, c: &ICalendarComponent) -> Option<i64> {
1884	match c.property(&ICalendarProperty::Dtstart) {
1885	Some(s) => self.end_from(c, self.instant(s)?),
1886	None => self.instant(c.property(&ICalendarProperty::Due)?),
1887	}
1888	}
1889
1890	/// When `c` would end if it started at `start`. The days and weeks of a
1891	/// DURATION count in wall-clock time (RFC 5545, 3.3.6).
1892	fn end_from(&self, c: &ICalendarComponent, start: i64) -> Option<i64> {
1893	let duration = c.property(&ICalendarProperty::Duration);
1894	let d = match duration.and_then(\|e\| e.values.first()) {
1895	Some(ICalendarValue::Duration(d))
1896	if !d.neg
1897	&& !c.has_property(&ICalendarProperty::Dtend)
1898	&& !c.has_property(&ICalendarProperty::Due) =>
1899	{
1900	d
1901	}
1902	_ => return Some(start + self.length(c)?),
1903	};
1904	let zone = self
1905	.zones
1906	.get(c.property(&ICalendarProperty::Dtstart)?.tz_id());
1907	let days = TimeDelta::try_days(i64::from(d.weeks) * 7 + i64::from(d.days))?;
1908	let local = add_local(zone.to_local(DateTime::from_timestamp(start, 0)?), days);
1909	let exact = i64::from(d.hours) * 3600 + i64::from(d.minutes) * 60 + i64::from(d.seconds);
1910	Some(zone.to_utc(local).timestamp() + exact)
1911	}
1912
1913	/// Which of `keys` are instances of the series in `cal`, and which a
1914	/// cut-short expansion cannot tell.
1915	fn instances(&self, cal: &ICalendar, keys: &[i64]) -> (HashSet<i64>, HashSet<i64>) {
1916	let zones = Zones::new(cal, Zone::Utc);
1917	let at = \|t: i64\| DateTime::from_timestamp(t, 0);
1918	let starts: Vec<(i64, DateTime<Utc>)> = keys
1919	.iter()
1920	.filter_map(\|k\| Some((k, at(self.moved(k))?)))
1921	.collect();
1922	let (Some(lo), Some(hi)) = (
1923	starts.iter().map(\|(_, s)\| *s).min(),
1924	starts.iter().map(\|(_, s)\| *s).max(),
1925	) else {
1926	return Default::default();
1927	};
1928	// A day either side: an all-day shift is whole days, not 24 hours.
1929	let day = TimeDelta::days(1);
1930	// Cut short, the keys get checked one by one, so a small cap is safe.
1931	let e = expand_in(cal, &zones, lo - day..hi + day, RULE_BUDGET);
1932	if !e.truncated {
1933	return (rids(&e), HashSet::new());
1934	}
1935	// The sender picks the keys and so the span.
1936	let (mut found, mut unknown) = (HashSet::new(), HashSet::new());
1937	let mut left = MAX_OCCURRENCES;
1938	for (k, s) in starts {
1939	let slack = match self.future(k) {
1940	Some(_) => day,
1941	None => TimeDelta::seconds(1),
1942	};
1943	let e = expand_in(cal, &zones, s - slack..s + slack, left);
1944	left = left.saturating_sub(e.generated);
1945	match e.truncated {
1946	true => unknown.insert(k),
1947	false => rids(&e).contains(&k) && found.insert(k),
1948	};
1949	}
1950	(found, unknown)
1951	}
1952
1953	/// Seconds from DTSTART to DTEND or DUE, or the DURATION. Without
1954	/// either, a day for a date and nothing for a date-time (RFC 5545).
1955	fn length(&self, c: &ICalendarComponent) -> Option<i64> {
1956	let start = c.property(&ICalendarProperty::Dtstart)?;
1957	let instant = \|p: &ICalendarProperty\| c.property(p).and_then(\|e\| self.instant(e));
1958	match instant(&ICalendarProperty::Dtend).or_else(\|\| instant(&ICalendarProperty::Due)) {
1959	Some(end) => Some(end - self.instant(start)?),
1960	None => match c.property(&ICalendarProperty::Duration) {
1961	Some(d) => match d.values.first()? {
1962	ICalendarValue::Duration(d) => Some(d.as_seconds()),
1963	_ => None,
1964	},
1965	None => {
1966	let date = start.values.first()?.as_partial_date_time()?.hour.is_none();
1967	Some(if date { 86400 } else { 0 })
1968	}
1969	},
1970	}
1971	}
1972
1973	/// Ends the series of master `m` before instant `at`: UNTIL in the form
1974	/// RFC 5545 asks for, COUNT dropped, later RDATEs removed. `at` is an
1975	/// instance, so COUNT had not ended before it.
1976	fn end_series(&self, m: &mut ICalendarComponent, at: i64) {
1977	let Some(start) = m.property(&ICalendarProperty::Dtstart).cloned() else {
1978	return;
1979	};
1980	let Some(form) = start.values.first().and_then(\|v\| v.as_partial_date_time()) else {
1981	return;
1982	};
1983	let s = stamp(&self.zones, form, start.tz_id());
1984	// Obj reads floating times in UTC, so `at` is their wall-clock time.
1985	let until = if form.hour.is_none() {
1986	PartialDateTime::from_date_timestamp(at - 86400)
1987	} else if form.tz_hour.is_none() && start.tz_id().is_none() {
1988	PartialDateTime::from_naive_timestamp(at - 1)
1989	} else {
1990	PartialDateTime::from_utc_timestamp(at - 1)
1991	};
1992	for e in m.entries.iter_mut() {
1993	match e.name {
1994	ICalendarProperty::Rrule => {
1995	for v in &mut e.values {
1996	if let ICalendarValue::RecurrenceRule(r) = v
1997	&& !r
1998	.until
1999	.as_ref()
2000	.and_then(\|u\| until_utc(u, s.as_ref()?))
2001	.is_some_and(\|u\| u.timestamp() < at)
2002	{
2003	r.until = Some(until.clone());
2004	r.count = None;
2005	}
2006	}
2007	}
2008	ICalendarProperty::Rdate => {
2009	let tz = e.tz_id().map(str::to_string);
2010	e.values.retain(\|v\| {
2011	v.as_partial_date_time()
2012	.and_then(\|p\| self.at(p, tz.as_deref()))
2013	.is_none_or(\|t\| t < at)
2014	});
2015	}
2016	_ => {}
2017	}
2018	}
2019	m.entries
2020	.retain(\|e\| e.name != ICalendarProperty::Rdate \|\| !e.values.is_empty());
2021	}
2022
2023	/// A message: this object's VCALENDAR and time zones around `comps`.
2024	fn envelope(&self, comps: Vec<Node>, method: Method, now: DateTime<Utc>) -> ICalendar {
2025	let mut root = Node {
2026	c: self.root.c.clone(),
2027	children: self
2028	.root
2029	.children
2030	.iter()
2031	.filter(\|n\| n.c.component_type == ICalendarComponentType::VTimezone)
2032	.cloned()
2033	.collect(),
2034	};
2035	let method = match method {
2036	Method::Request => ICalendarMethod::Request,
2037	Method::Cancel => ICalendarMethod::Cancel,
2038	Method::Reply => ICalendarMethod::Reply,
2039	};
2040	set_prop(
2041	&mut root.c,
2042	ICalendarProperty::Method,
2043	ICalendarValue::Method(method),
2044	);
2045	let stamp = PartialDateTime::from_utc_timestamp(now.timestamp());
2046	for mut n in comps {
2047	set_prop(
2048	&mut n.c,
2049	ICalendarProperty::Dtstamp,
2050	ICalendarValue::PartialDateTime(Box::new(stamp.clone())),
2051	);
2052	root.children.push(n);
2053	}
2054	let mut components = Vec::new();
2055	flatten(&root, &mut components);
2056	ICalendar { components }
2057	}
2058
2059	/// A RECURRENCE-ID for the instance at `rid`, in the form of `start`.
2060	fn recurrence_id(
2061	&self,
2062	start: &ICalendarEntry,
2063	rid: DateTime<Utc>,
2064	floating: &Zone,
2065	) -> Option<ICalendarEntry> {
2066	let v = start.values.first()?.as_partial_date_time()?;
2067	let local = \|zone: &Zone\| zone.to_local(rid).and_utc().timestamp();
2068	let value = if v.hour.is_none() {
2069	PartialDateTime::from_date_timestamp(local(floating))
2070	} else if v.tz_hour.is_some() {
2071	PartialDateTime::from_utc_timestamp(rid.timestamp())
2072	} else if start.tz_id().is_some() {
2073	PartialDateTime::from_naive_timestamp(local(&self.zones.get(start.tz_id())))
2074	} else {
2075	PartialDateTime::from_naive_timestamp(local(floating))
2076	};
2077	Some(ICalendarEntry {
2078	name: ICalendarProperty::RecurrenceId,
2079	params: without(start.params.clone(), &ICalendarParameterName::Range),
2080	values: vec![ICalendarValue::PartialDateTime(Box::new(value))],
2081	})
2082	}
2083
2084	/// The latest THISANDFUTURE override at or before instance `key`, and
2085	/// its key.
2086	fn future(&self, key: i64) -> Option<(&Node, i64)> {
2087	let ranges = &self.index().ranges;
2088	let (k, at) = ranges[..ranges.partition_point(\|(k, _)\| *k <= key)].last()?;
2089	Some((&self.root.children[at], k))
2090	}
2091
2092	/// Where instance `key` starts once a THISANDFUTURE override moves it.
2093	/// The move is wall-clock time in the zone of the series, as in expand.
2094	fn moved(&self, key: i64) -> i64 {
2095	let shifted = \|\| {
2096	let (n, k) = self.future(key)?;
2097	let dtstart = n.c.property(&ICalendarProperty::Dtstart)?;
2098	let start = self.instant(dtstart)?;
2099	// A copy without its master still has the override's zone.
2100	let series = self
2101	.master()
2102	.and_then(\|m\| m.c.property(&ICalendarProperty::Dtstart));
2103	let zone = self.zones.get(series.unwrap_or(dtstart).tz_id());
2104	let local = \|t: i64\| Some(zone.to_local(DateTime::from_timestamp(t, 0)?));
2105	let shift = local(start)? - local(k)?;
2106	Some(zone.to_utc(add_local(local(key)?, shift)).timestamp())
2107	};
2108	shifted().unwrap_or(key)
2109	}
2110
2111	/// Whether the series in `cal` has an instance at `rid`, whose key is
2112	/// `key`.
2113	fn occurs(&self, cal: &ICalendar, rid: DateTime<Utc>, key: i64, floating: &Zone) -> bool {
2114	let Some(at) = DateTime::from_timestamp(self.moved(key), 0) else {
2115	return false;
2116	};
2117	// A day either side: an all-day shift is whole days, not 24 hours.
2118	let window = at - TimeDelta::days(1)..at + TimeDelta::days(1);
2119	expand(cal, window, floating.clone())
2120	.instances
2121	.iter()
2122	.any(\|i\| i.recurrence_id == Some(rid))
2123	}
2124
2125	/// An override for the instance at `rid`, from the master or from the
2126	/// THISANDFUTURE override that moves it.
2127	fn single(&self, rid: DateTime<Utc>, floating: &Zone) -> Option<Node> {
2128	let master = self.master()?;
2129	let form = master.c.property(&ICalendarProperty::Dtstart)?;
2130	let id = self.recurrence_id(form, rid, floating)?;
2131	let key = self.instant(&id)?;
2132	let Some((base, _)) = self.future(key) else {
2133	return Some(self.instance(master, &id, &id));
2134	};
2135	let at = self.moved(key);
2136	let start = match form.values.first()?.as_partial_date_time()?.hour {
2137	None => ICalendarEntry {
2138	values: vec![ICalendarValue::PartialDateTime(Box::new(
2139	PartialDateTime::from_date_timestamp(at),
2140	))],
2141	..id.clone()
2142	},
2143	Some(_) => self.recurrence_id(form, DateTime::from_timestamp(at, 0)?, floating)?,
2144	};
2145	Some(self.instance(base, &id, &start))
2146	}
2147
2148	/// Narrows the THISANDFUTURE override at instance `rid` (key `key`) to
2149	/// that instance. A copy of it carries the range on from the next instance
2150	/// without an override of its own, found by expanding `cal`.
2151	fn narrow(&mut self, cal: &ICalendar, rid: DateTime<Utc>, key: i64, floating: &Zone) {
2152	let Some(at) = self.position(Some(key)) else {
2153	return;
2154	};
2155	let Some(range) = self.root.children[at]
2156	.c
2157	.property(&ICalendarProperty::RecurrenceId)
2158	.and_then(\|e\| e.parameter(&ICalendarParameterName::Range))
2159	.cloned()
2160	else {
2161	return;
2162	};
2163	let later = self
2164	.comps()
2165	.filter(\|c\| is_range(&c.c))
2166	.filter_map(\|c\| self.key(&c.c))
2167	.filter(\|k\| *k > key)
2168	.min();
2169	let next = self
2170	.next_free(cal, rid, key, floating)
2171	.filter(\|(_, k)\| later.is_none_or(\|l\| *k < l))
2172	.and_then(\|(r, _)\| self.single(r, floating));
2173	if let Some(mut n) = next {
2174	if let Some(e) =
2175	n.c.entries
2176	.iter_mut()
2177	.find(\|e\| e.name == ICalendarProperty::RecurrenceId)
2178	{
2179	set_param(e, ICalendarParameterName::Range, range);
2180	}
2181	self.push(n);
2182	}
2183	if let Some(e) = self.children_mut()[at]
2184	.c
2185	.entries
2186	.iter_mut()
2187	.find(\|e\| e.name == ICalendarProperty::RecurrenceId)
2188	{
2189	remove_param(e, &ICalendarParameterName::Range);
2190	}
2191	}
2192
2193	/// The first instance after `rid` that has no override, and its key.
2194	// ponytail: looks ten years ahead; a range beyond that falls back to the master.
2195	fn next_free(
2196	&self,
2197	cal: &ICalendar,
2198	rid: DateTime<Utc>,
2199	key: i64,
2200	floating: &Zone,
2201	) -> Option<(DateTime<Utc>, i64)> {
2202	let form = self.master()?.c.property(&ICalendarProperty::Dtstart)?;
2203	let from = DateTime::from_timestamp(self.moved(key), 0)?;
2204	[1, 32, 400, 3700].into_iter().find_map(\|days\| {
2205	expand(cal, from..from + TimeDelta::days(days), floating.clone())
2206	.instances
2207	.iter()
2208	.filter_map(\|i\| i.recurrence_id)
2209	.filter(\|r\| *r > rid)
2210	.filter_map(\|r\| Some((r, self.instant(&self.recurrence_id(form, r, floating)?)?)))
2211	.filter(\|(_, k)\| self.find(Some(*k)).is_none())
2212	.min()
2213	})
2214	}
2215
2216	/// An override of `base` for the instance `rid` starting at `start`, so
2217	/// it can hold a status of its own. Its length becomes a DURATION.
2218	fn instance(&self, base: &Node, rid: &ICalendarEntry, start: &ICalendarEntry) -> Node {
2219	let mut n = base.clone();
2220	let begin =
2221	n.c.property(&ICalendarProperty::Dtstart)
2222	.and_then(\|e\| self.instant(e));
2223	let end_prop = match n.c.component_type {
2224	ICalendarComponentType::VTodo => ICalendarProperty::Due,
2225	_ => ICalendarProperty::Dtend,
2226	};
2227	let end = n.c.property(&end_prop).and_then(\|e\| self.instant(e));
2228	if let (Some(s), Some(e)) = (begin, end) {
2229	n.c.entries.retain(\|x\| x.name != end_prop);
2230	n.c.entries.push(ICalendarEntry {
2231	name: ICalendarProperty::Duration,
2232	params: Vec::new(),
2233	values: vec![ICalendarValue::Duration(ICalendarDuration::from_seconds(
2234	(e - s).max(0),
2235	))],
2236	});
2237	}
2238	n.c.entries.retain(\|e\| {
2239	!matches!(
2240	e.name,
2241	ICalendarProperty::Rrule
2242	\| ICalendarProperty::Rdate
2243	\| ICalendarProperty::Exdate
2244	\| ICalendarProperty::Exrule
2245	\| ICalendarProperty::Dtstart
2246	\| ICalendarProperty::RecurrenceId
2247	)
2248	});
2249	n.c.entries.push(ICalendarEntry {
2250	name: ICalendarProperty::Dtstart,
2251	params: without(start.params.clone(), &ICalendarParameterName::Range),
2252	values: start.values.clone(),
2253	});
2254	n.c.entries.push(ICalendarEntry {
2255	name: ICalendarProperty::RecurrenceId,
2256	params: without(rid.params.clone(), &ICalendarParameterName::Range),
2257	values: rid.values.clone(),
2258	});
2259	n
2260	}
2261	}
2262
2263	// ---------------------------------------------------------------------------
2264	// Properties and parameters
2265	// ---------------------------------------------------------------------------
2266
2267	fn is_scheduled(c: &ICalendarComponent) -> bool {
2268	matches!(
2269	c.component_type,
2270	ICalendarComponentType::VEvent
2271	\| ICalendarComponentType::VTodo
2272	\| ICalendarComponentType::VJournal
2273	)
2274	}
2275
2276	fn address(e: &ICalendarEntry) -> Option<&str> {
2277	e.values.first()?.as_text().map(str::trim)
2278	}
2279
2280	fn attendees(c: &ICalendarComponent) -> impl Iterator<Item = &ICalendarEntry> {
2281	c.properties(&ICalendarProperty::Attendee)
2282	}
2283
2284	/// A task's progress is the assignee's to set per instance, unless the
2285	/// organizer cancelled it.
2286	fn own_progress(c: &ICalendarComponent, base: &ICalendarComponent) -> bool {
2287	use ICalendarStatus::*;
2288	c.component_type == ICalendarComponentType::VTodo
2289	&& matches!(c.status(), None \| Some(NeedsAction \| InProcess \| Completed))
2290	&& base.status() != Some(&Cancelled)
2291	}
2292
2293	fn organizer_of(c: &ICalendarComponent) -> Option<String> {
2294	c.property(&ICalendarProperty::Organizer)
2295	.and_then(address)
2296	.map(str::to_ascii_lowercase)
2297	}
2298
2299	/// Whether `c` repeats without end.
2300	pub(crate) fn endless(c: &ICalendarComponent) -> bool {
2301	c.properties(&ICalendarProperty::Rrule).any(\|e\| {
2302	matches!(e.values.first(), Some(ICalendarValue::RecurrenceRule(r))
2303	if r.count.is_none() && r.until.is_none())
2304	})
2305	}
2306
2307	fn addresses(c: &ICalendarComponent) -> Vec<String> {
2308	let mut v: Vec<String> = attendees(c)
2309	.filter_map(address)
2310	.map(str::to_ascii_lowercase)
2311	.collect();
2312	v.sort();
2313	v.dedup();
2314	v
2315	}
2316
2317	fn is_range(c: &ICalendarComponent) -> bool {
2318	c.property(&ICalendarProperty::RecurrenceId)
2319	.is_some_and(\|e\| e.parameter(&ICalendarParameterName::Range).is_some())
2320	}
2321
2322	fn client_scheduled(c: &ICalendarComponent, a: &str) -> bool {
2323	attendees(c).any(\|e\| address(e).is_some_and(\|x\| x.eq_ignore_ascii_case(a)) && !server_agent(e))
2324	}
2325
2326	fn same_attendee<'a>(c: &'a ICalendarComponent, e: &ICalendarEntry) -> Option<&'a ICalendarEntry> {
2327	let a = address(e)?;
2328	attendees(c).find(\|x\| address(x).is_some_and(\|b\| b.eq_ignore_ascii_case(a)))
2329	}
2330
2331	fn own_partstat(c: &ICalendarComponent, me: Is) -> Option<String> {
2332	attendees(c).find(\|e\| address(e).is_some_and(me)).map(\|e\| {
2333	param(e, &ICalendarParameterName::Partstat)
2334	.unwrap_or("NEEDS-ACTION")
2335	.to_ascii_uppercase()
2336	})
2337	}
2338
2339	/// `SCHEDULE-AGENT` absent or `SERVER`. Unknown values count as `NONE`.
2340	fn server_agent(e: &ICalendarEntry) -> bool {
2341	param(e, &ICalendarParameterName::ScheduleAgent)
2342	.is_none_or(\|v\| v.eq_ignore_ascii_case("SERVER"))
2343	}
2344
2345	fn sequence(c: &ICalendarComponent) -> i64 {
2346	c.property(&ICalendarProperty::Sequence)
2347	.and_then(\|e\| e.values.first()?.as_integer())
2348	.unwrap_or(0)
2349	}
2350
2351	fn param<'a>(e: &'a ICalendarEntry, name: &ICalendarParameterName) -> Option<&'a str> {
2352	e.parameter(name)?.as_text()
2353	}
2354
2355	fn set_param(e: &mut ICalendarEntry, name: ICalendarParameterName, value: ICalendarParameterValue) {
2356	remove_param(e, &name);
2357	e.params.push(ICalendarParameter::new(name, value));
2358	}
2359
2360	fn remove_param(e: &mut ICalendarEntry, name: &ICalendarParameterName) {
2361	e.params.retain(\|p\| &p.name != name);
2362	}
2363
2364	fn without(
2365	mut params: Vec<ICalendarParameter>,
2366	name: &ICalendarParameterName,
2367	) -> Vec<ICalendarParameter> {
2368	params.retain(\|p\| &p.name != name);
2369	params
2370	}
2371
2372	fn set_prop(c: &mut ICalendarComponent, name: ICalendarProperty, value: ICalendarValue) {
2373	c.entries.retain(\|e\| e.name != name);
2374	c.entries.push(ICalendarEntry {
2375	name,
2376	params: Vec::new(),
2377	values: vec![value],
2378	});
2379	}
2380
2381	/// Messages carry none of the scheduling parameters (RFC 6638, 7).
2382	fn strip_scheduling_params(c: &mut ICalendarComponent) {
2383	for e in c.entries.iter_mut().filter(\|e\| {
2384	matches!(
2385	e.name,
2386	ICalendarProperty::Attendee \| ICalendarProperty::Organizer
2387	)
2388	}) {
2389	for p in [
2390	ICalendarParameterName::ScheduleAgent,
2391	ICalendarParameterName::ScheduleStatus,
2392	ICalendarParameterName::ScheduleForceSend,
2393	] {
2394	remove_param(e, &p);
2395	}
2396	}
2397	}
2398
2399	fn text(s: &str) -> ICalendarParameterValue {
2400	ICalendarParameterValue::Text(s.to_string())
2401	}
2402
2403	fn partstat(p: ICalendarParticipationStatus) -> ICalendarParameterValue {
2404	ICalendarParameterValue::Partstat(p)
2405	}
2406
2407	/// Makes an object forget a principal that is about to be deleted, so that
2408	/// a later principal of the same name is not taken for it. Every ORGANIZER
2409	/// and ATTENDEE that `gone` names gets the address `tombstone`, and such an
2410	/// ATTENDEE gets SCHEDULE-STATUS 3.7. A component the gone principal
2411	/// organized is cancelled. All other lines keep their bytes. `None` when
2412	/// nothing names the principal.
2413	pub fn forget(text: &str, gone: Is, tombstone: &str) -> Option<String> {
2414	let mut out: Vec<String> = Vec::new();
2415	// Per open component: name, index of its BEGIN line in `out`, index of
2416	// its STATUS line, whether the gone principal organized it.
2417	let mut open: Vec<(String, usize, Option<usize>, bool)> = Vec::new();
2418	let mut changed = false;
2419	for raw in logical_lines(text) {
2420	let eol = match raw.ends_with('\n') {
2421	true if raw.ends_with("\r\n") => "\r\n",
2422	true => "\n",
2423	false => "\r\n",
2424	};
2425	let line = unfold(raw);
2426	let n = name(&line);
2427	match n.as_str() {
2428	"BEGIN" => open.push((
2429	value(&line).trim().to_ascii_uppercase(),
2430	out.len(),
2431	None,
2432	false,
2433	)),
2434	"END" => {
2435	if let Some((comp, begin, status, true)) = open.pop()
2436	&& ["VEVENT", "VTODO", "VJOURNAL"].contains(&comp.as_str())
2437	{
2438	let cancelled = format!("STATUS:CANCELLED{eol}");
2439	match status {
2440	Some(i) => out[i] = cancelled,
2441	None => out.insert(begin + 1, cancelled),
2442	}
2443	}
2444	}
2445	"STATUS" => {
2446	if let Some(top) = open.last_mut() {
2447	top.2 = Some(out.len());
2448	}
2449	}
2450	"ORGANIZER" \| "ATTENDEE" if gone(value(&line).trim()) => {
2451	let attendee = n == "ATTENDEE";
2452	let mut new = n.clone();
2453	for p in param_parts(&line) {
2454	if !(attendee
2455	&& p.trim()
2456	.to_ascii_uppercase()
2457	.starts_with("SCHEDULE-STATUS="))
2458	{
2459	new.push(';');
2460	new.push_str(p);
2461	}
2462	}
2463	if attendee {
2464	new.push_str(";SCHEDULE-STATUS=3.7");
2465	} else if let Some(top) = open.last_mut() {
2466	top.3 = true;
2467	}
2468	new.push(':');
2469	new.push_str(tombstone);
2470	out.push(fold(&new, eol));
2471	changed = true;
2472	continue;
2473	}
2474	_ => {}
2475	}
2476	out.push(raw.to_string());
2477	}
2478	changed.then(\|\| out.concat())
2479	}
2480