dovenest

dovenest/pimdav/src/expand.rs
expand.rs
⎇
Raw
1//! Recurrence expansion: DTSTART + RRULE + RDATE - EXRULE - EXDATE, with
2//! RECURRENCE-ID overrides applied.
3
4use std::collections::{BTreeMap, HashMap, HashSet};
5use std::ops::Range;
6
7use calcard::common::{CalendarScale, PartialDateTime};
8use calcard::icalendar::{
9 ICalendar, ICalendarComponent, ICalendarComponentType, ICalendarDuration, ICalendarFrequency,
10 ICalendarParameterName, ICalendarPeriod, ICalendarProperty, ICalendarRecurrenceRule,
11 ICalendarSkip, ICalendarValue,
12};
13use chrono::{DateTime, NaiveDateTime, NaiveTime, TimeDelta, TimeZone, Timelike, Utc, Weekday};
14
15use crate::zone::{Zone, Zones, add, add_local};
16
17/// Occurrences the rules of one series may generate together before
18/// expansion gives up.
19// ponytail: COUNT, MONTHLY and YEARLY rules iterate from DTSTART, so a long
20// running one can hit this. Skip ahead for them if that matters.
21pub(crate) const MAX_OCCURRENCES: usize = 1_000_000;
22
23#[derive(Debug, Clone, PartialEq)]
24pub struct Instance {
25 pub start: DateTime<Utc>,
26 pub end: DateTime<Utc>,
27 /// The original start. `None` if the component does not recur.
28 pub recurrence_id: Option<DateTime<Utc>>,
29 /// Index into `ICalendar::components` of the master or override that
30 /// describes this instance.
31 pub component: usize,
32}
33
34#[derive(Debug, Default)]
35pub struct Expansion {
36 /// Sorted by start.
37 pub instances: Vec<Instance>,
38 /// A series reached `MAX_OCCURRENCES`, so later instances are missing.
39 pub truncated: bool,
40 /// Occurrences the rules produced, also those outside the window.
41 pub generated: usize,
42}
43
44/// The instances of all VEVENT, VTODO and VJOURNAL components that overlap
45/// `window`. A zero-length instance overlaps if it starts inside.
46///
47/// Components are grouped by type and UID into one master and its overrides.
48/// Components without DTSTART are skipped. `floating` interprets values
49/// without a zone.
50pub fn expand(cal: &ICalendar, window: Range<DateTime<Utc>>, floating: Zone) -> Expansion {
51 expand_in(cal, &Zones::new(cal, floating), window, MAX_OCCURRENCES)
52}
53
54/// `expand` with the zones built, and at most `cap` occurrences per series.
55pub(crate) fn expand_in(
56 cal: &ICalendar,
57 zones: &Zones,
58 window: Range<DateTime<Utc>>,
59 cap: usize,
60) -> Expansion {
61 let mut out = Expansion::default();
62 let mut groups: HashMap<(&ICalendarComponentType, &str), Vec<usize>> = HashMap::new();
63 for (i, c) in cal.components.iter().enumerate() {
64 if !is_item(c) {
65 continue;
66 }
67 match c.uid() {
68 Some(uid) => groups.entry((&c.component_type, uid)).or_default().push(i),
69 None => expand_group(cal, zones, &[i], &window, cap, &mut out),
70 }
71 }
72 for group in groups.values() {
73 expand_group(cal, zones, group, &window, cap, &mut out);
74 }
75 out.instances.sort_by_key(|i| (i.start, i.component));
76 out
77}
78
79/// A VEVENT, VTODO or VJOURNAL.
80pub(crate) fn is_item(c: &ICalendarComponent) -> bool {
81 matches!(
82 c.component_type,
83 ICalendarComponentType::VEvent
84 | ICalendarComponentType::VTodo
85 | ICalendarComponentType::VJournal
86 )
87}
88
89/// A date or date-time value and the zone it is in.
90#[derive(Debug, Clone)]
91pub(crate) struct Stamp {
92 pub(crate) local: NaiveDateTime,
93 zone: Zone,
94 pub(crate) date: bool,
95 /// A date-time without TZID or UTC offset.
96 floating: bool,
97}
98
99impl Stamp {
100 pub(crate) fn utc(&self) -> DateTime<Utc> {
101 self.zone.to_utc(self.local)
102 }
103}
104
105#[derive(Debug, Clone)]
106enum Length {
107 Exact(TimeDelta),
108 /// Whole days count in wall-clock time, so a day can last 23 or 25 hours.
109 Nominal {
110 days: i64,
111 exact: TimeDelta,
112 },
113}
114
115impl Length {
116 fn end(&self, zone: &Zone, local: NaiveDateTime, utc: DateTime<Utc>) -> DateTime<Utc> {
117 match self {
118 Length::Exact(d) => add(utc, *d),
119 Length::Nominal { days, exact } => add(
120 zone.to_utc(add_local(local, TimeDelta::days(*days))),
121 *exact,
122 ),
123 }
124 }
125
126 /// An upper bound, for widening the generation window.
127 fn max(&self) -> TimeDelta {
128 match self {
129 Length::Exact(d) => *d,
130 Length::Nominal { days, exact } => TimeDelta::days(days + 1) + *exact,
131 }
132 }
133}
134
135/// DTSTART and length of one component.
136#[derive(Debug, Clone)]
137struct Timing {
138 start: Stamp,
139 length: Length,
140 component: usize,
141}
142
143impl Timing {
144 fn of(cal: &ICalendar, zones: &Zones, component: usize) -> Option<Self> {
145 let c = &cal.components[component];
146 let start = prop_stamp(zones, c, &ICalendarProperty::Dtstart)?;
147 let end = match c.component_type {
148 ICalendarComponentType::VTodo => ICalendarProperty::Due,
149 _ => ICalendarProperty::Dtend,
150 };
151 let zero = TimeDelta::zero();
152 let length = if let Some(end) = prop_stamp(zones, c, &end) {
153 if start.date && end.date {
154 Length::Nominal {
155 days: (end.local - start.local).num_days().max(0),
156 exact: zero,
157 }
158 } else {
159 Length::Exact((end.utc() - start.utc()).max(zero))
160 }
161 } else if let Some(ICalendarValue::Duration(d)) = c
162 .property(&ICalendarProperty::Duration)
163 .and_then(|e| e.values.first())
164 {
165 nominal(d)
166 } else if start.date {
167 Length::Nominal {
168 days: 1,
169 exact: zero,
170 }
171 } else {
172 Length::Exact(zero)
173 };
174 Some(Timing {
175 start,
176 length,
177 component,
178 })
179 }
180
181 fn end_at(&self, local: NaiveDateTime, utc: DateTime<Utc>) -> DateTime<Utc> {
182 self.length.end(&self.start.zone, local, utc)
183 }
184
185 /// A RECURRENCE-ID, RDATE or EXDATE value. Dates and floating times are
186 /// read in the zone of the series: clients write them that way.
187 fn utc_of(&self, s: &Stamp) -> DateTime<Utc> {
188 if s.date || s.floating {
189 self.start.zone.to_utc(s.local)
190 } else {
191 s.utc()
192 }
193 }
194
195 /// The identity of a recurrence instance. An all-day series matches by
196 /// date alone, whatever zone the other value names.
197 fn key(&self, s: &Stamp) -> i64 {
198 if self.start.date {
199 day_key(s.local)
200 } else {
201 self.utc_of(s).timestamp()
202 }
203 }
204
205 fn member_key(&self, local: NaiveDateTime, utc: DateTime<Utc>) -> i64 {
206 if self.start.date {
207 day_key(local)
208 } else {
209 utc.timestamp()
210 }
211 }
212}
213
214struct Member {
215 local: NaiveDateTime,
216 utc: DateTime<Utc>,
217 /// From an RDATE period.
218 length: Option<Length>,
219}
220
221struct Override {
222 sequence: i64,
223 recurrence_id: DateTime<Utc>,
224 timing: Timing,
225}
226
227fn expand_group(
228 cal: &ICalendar,
229 zones: &Zones,
230 group: &[usize],
231 window: &Range<DateTime<Utc>>,
232 max: usize,
233 out: &mut Expansion,
234) {
235 let comp = |i: usize| &cal.components[i];
236 let sequence = |i: usize| {
237 comp(i)
238 .property(&ICalendarProperty::Sequence)
239 .and_then(|e| e.values.first()?.as_integer())
240 .unwrap_or(0)
241 };
242 let (overrides, masters): (Vec<usize>, Vec<usize>) = group
243 .iter()
244 .partition(|&&i| comp(i).has_property(&ICalendarProperty::RecurrenceId));
245 // Several masters for one UID are invalid. Take the latest revision,
246 // or the first one on a tie.
247 let master = masters
248 .into_iter()
249 .rev()
250 .max_by_key(|&i| sequence(i))
251 .and_then(|i| Timing::of(cal, zones, i));
252
253 // Matched by RECURRENCE-ID only. SEQUENCE picks between two overrides of
254 // one instance and never decides whether an override applies.
255 let mut exact: HashMap<i64, Override> = HashMap::new();
256 let mut future: Vec<(i64, DateTime<Utc>, Timing)> = Vec::new();
257 for i in overrides {
258 let Some(e) = comp(i).property(&ICalendarProperty::RecurrenceId) else {
259 continue;
260 };
261 let (Some(timing), Some(rid)) = (
262 Timing::of(cal, zones, i),
263 e.values
264 .first()
265 .and_then(|v| stamp(zones, v.as_partial_date_time()?, e.tz_id())),
266 ) else {
267 continue;
268 };
269 let (key, rid_utc) = match &master {
270 Some(m) => (m.key(&rid), m.utc_of(&rid)),
271 None => (rid.utc().timestamp(), rid.utc()),
272 };
273 if e.parameter(&ICalendarParameterName::Range).is_some() {
274 future.push((key, rid_utc, timing.clone()));
275 }
276 if exact.get(&key).is_none_or(|old| sequence(i) > old.sequence) {
277 let sequence = sequence(i);
278 exact.insert(
279 key,
280 Override {
281 sequence,
282 recurrence_id: rid_utc,
283 timing,
284 },
285 );
286 }
287 }
288 future.sort_by_key(|f| f.0);
289
290 let Some(m) = master else {
291 push_overrides(out, window, exact.values());
292 return;
293 };
294 let mc = comp(m.component);
295 let mz = &m.start.zone;
296
297 let rules: Vec<_> = mc
298 .properties(&ICalendarProperty::Rrule)
299 .filter_map(|e| rule(e.values.first()?))
300 .collect();
301 let mut set: BTreeMap<i64, Member> = BTreeMap::new();
302 let mut slack = m.length.max();
303 // DTSTART is an instance even when it does not match the RRULE, unless
304 // the series ended before it.
305 let ended = !rules.is_empty()
306 && rules.iter().all(|r| {
307 r.until
308 .as_ref()
309 .and_then(|u| until_local(u, &m.start))
310 .is_some_and(|u| u < m.start.local)
311 });
312 if !ended {
313 let utc = m.start.utc();
314 set.insert(
315 m.member_key(m.start.local, utc),
316 Member {
317 local: m.start.local,
318 utc,
319 length: None,
320 },
321 );
322 }
323 for e in mc.properties(&ICalendarProperty::Rdate) {
324 for v in &e.values {
325 let (s, length) = match v {
326 ICalendarValue::PartialDateTime(p) => {
327 let Some(s) = stamp(zones, p, e.tz_id()) else {
328 continue;
329 };
330 (s, None)
331 }
332 ICalendarValue::Period(ICalendarPeriod::Range { start, end }) => {
333 let (Some(s), Some(end)) =
334 (stamp(zones, start, e.tz_id()), stamp(zones, end, e.tz_id()))
335 else {
336 continue;
337 };
338 let d = (end.utc() - s.utc()).max(TimeDelta::zero());
339 (s, Some(Length::Exact(d)))
340 }
341 ICalendarValue::Period(ICalendarPeriod::Duration { start, duration }) => {
342 let Some(s) = stamp(zones, start, e.tz_id()) else {
343 continue;
344 };
345 (s, Some(nominal(duration)))
346 }
347 _ => continue,
348 };
349 let utc = m.utc_of(&s);
350 let local = mz.to_local(utc);
351 if let Some(l) = &length {
352 slack = slack.max(l.max());
353 }
354 // A period on DTSTART or a rule instance still sets its length.
355 let member = set.entry(m.key(&s)).or_insert(Member {
356 local,
357 utc,
358 length: None,
359 });
360 member.length = length.or(member.length.take());
361 }
362 }
363 for (_, rid, t) in &future {
364 slack = slack.max((t.start.utc() - *rid).abs() + t.length.max());
365 }
366 let wide = slack
367 .checked_add(&TimeDelta::days(1))
368 .unwrap_or(TimeDelta::MAX);
369 let reach = add(window.start, -wide);
370 // A huge DURATION would run an endless rule to the cap, so the rules
371 // iterate at most 1000 periods of the fastest rule around the window.
372 // ponytail: a rule instance longer than that is missed where it starts early.
373 let cap = mc
374 .properties(&ICalendarProperty::Rrule)
375 .chain(mc.properties(&ICalendarProperty::Exrule))
376 .filter_map(|e| rule(e.values.first()?))
377 .map(|r| period(r) * 1000)
378 .min();
379 let slack = cap.map_or(wide, |c| wide.min(c + TimeDelta::days(1)));
380 let (from, to) = (add(window.start, -slack), add(window.end, slack));
381 let (from_local, to_local) = (mz.to_local(from), mz.to_local(to));
382
383 let mut budget = max;
384 let mut excluded = HashSet::new();
385 for e in mc.properties(&ICalendarProperty::Exrule) {
386 let Some(rule) = e.values.first().and_then(rule) else {
387 continue;
388 };
389 for local in occurrences_capped(rule, &m, from_local, to_local, &mut budget, out) {
390 excluded.insert(m.member_key(local, mz.to_utc(local)));
391 }
392 }
393 // ponytail: sub-daily rules iterate in wall time. A DST fall-back skips the
394 // repeated hour, and a spring-forward collapses a shifted instance into the
395 // next (COUNT=5 gives 4). Iterate in elapsed time, BYHOUR in local, to fix.
396 for rule in rules {
397 for local in occurrences_capped(rule, &m, from_local, to_local, &mut budget, out) {
398 let utc = mz.to_utc(local);
399 if utc >= from {
400 set.entry(m.member_key(local, utc)).or_insert(Member {
401 local,
402 utc,
403 length: None,
404 });
405 }
406 }
407 }
408
409 // A DATE EXDATE on a DATE-TIME series removes every instance on that day.
410 let mut excluded_days = HashSet::new();
411 for e in mc.properties(&ICalendarProperty::Exdate) {
412 for s in e
413 .values
414 .iter()
415 .filter_map(|v| stamp(zones, v.as_partial_date_time()?, e.tz_id()))
416 {
417 if s.date && !m.start.date {
418 excluded_days.insert(s.local.date());
419 } else {
420 excluded.insert(m.key(&s));
421 }
422 }
423 }
424
425 // An EXDATE removes an override of that instance too. An override whose
426 // RECURRENCE-ID matches no instance still shows, as in clients.
427 push_overrides(
428 out,
429 window,
430 exact.iter().filter_map(|(key, o)| {
431 let day = mz.to_local(o.recurrence_id).date();
432 (!excluded.contains(key) && !excluded_days.contains(&day)).then_some(o)
433 }),
434 );
435
436 let recurs =
437 mc.has_property(&ICalendarProperty::Rrule) || mc.has_property(&ICalendarProperty::Rdate);
438 for (key, member) in &set {
439 if member.utc < reach
440 || excluded.contains(key)
441 || excluded_days.contains(&member.local.date())
442 || exact.contains_key(key)
443 {
444 continue;
445 }
446 let recurrence_id = recurs.then_some(member.utc);
447 // The latest THISANDFUTURE override before this instance moves it by
448 // the same offset and gives it the override's length. The offset is
449 // wall-clock time, so later instances keep their local time across DST.
450 let latest = future.partition_point(|f| f.0 <= *key).checked_sub(1);
451 let instance = match latest.map(|i| &future[i]) {
452 Some((_, rid, t)) => {
453 let shift = mz.to_local(t.start.utc()) - mz.to_local(*rid);
454 let start = mz.to_utc(add_local(member.local, shift));
455 Instance {
456 start,
457 end: t.end_at(t.start.zone.to_local(start), start),
458 recurrence_id,
459 component: t.component,
460 }
461 }
462 None => Instance {
463 start: member.utc,
464 end: member.length.as_ref().map_or_else(
465 || m.end_at(member.local, member.utc),
466 |l| l.end(mz, member.local, member.utc),
467 ),
468 recurrence_id,
469 component: m.component,
470 },
471 };
472 push(out, window, instance);
473 }
474}
475
476fn push_overrides<'a>(
477 out: &mut Expansion,
478 window: &Range<DateTime<Utc>>,
479 overrides: impl Iterator<Item = &'a Override>,
480) {
481 for o in overrides {
482 let t = &o.timing;
483 let start = t.start.utc();
484 let end = t.end_at(t.start.local, start);
485 push(
486 out,
487 window,
488 Instance {
489 start,
490 end,
491 recurrence_id: Some(o.recurrence_id),
492 component: t.component,
493 },
494 );
495 }
496}
497
498fn occurrences_capped(
499 rule: &ICalendarRecurrenceRule,
500 m: &Timing,
501 from_local: NaiveDateTime,
502 to_local: NaiveDateTime,
503 budget: &mut usize,
504 out: &mut Expansion,
505) -> Vec<NaiveDateTime> {
506 let until = match &rule.until {
507 Some(u) => match until_local(u, &m.start) {
508 Some(u) => Some(u),
509 None => return Vec::new(),
510 },
511 None => None,
512 };
513 let mut first = m.start.local;
514 // Whole steps keep the period grid, so INTERVAL and BYxxx still line up.
515 // Months and years vary in length. BYSETPOS picks from a whole period,
516 // which a mid-period start would cut.
517 if !matches!(
518 rule.freq,
519 ICalendarFrequency::Yearly | ICalendarFrequency::Monthly
520 ) && rule.count.is_none()
521 && rule.bysetpos.is_empty()
522 {
523 let step = period(rule).num_seconds();
524 let behind = (from_local - first).num_seconds();
525 if behind > 0 {
526 first += TimeDelta::seconds(behind / step * step);
527 }
528 }
529 let mut list: Vec<_> = occurrences(rule, first, until, to_local)
530 .take(*budget + 1)
531 .collect();
532 if list.len() > *budget {
533 list.pop();
534 out.truncated = true;
535 }
536 *budget -= list.len();
537 out.generated += list.len();
538 // DTSTART is the first of COUNT (RFC 5545, 3.3.10), also when the rule
539 // skips it.
540 if let Some(n) = rule.count.filter(|_| until.is_none()).map(|n| n as usize)
541 && list.first() != Some(&m.start.local)
542 && list.len() >= n
543 {
544 list.truncate(n.saturating_sub(1));
545 }
546 list
547}
548
549/// The longest time between two periods of `r`.
550fn period(r: &ICalendarRecurrenceRule) -> TimeDelta {
551 let days = match r.freq {
552 ICalendarFrequency::Yearly => 366,
553 ICalendarFrequency::Monthly => 31,
554 ICalendarFrequency::Weekly => 7,
555 _ => 1,
556 };
557 let unit = match r.freq {
558 ICalendarFrequency::Hourly => TimeDelta::hours(1),
559 ICalendarFrequency::Minutely => TimeDelta::minutes(1),
560 ICalendarFrequency::Secondly => TimeDelta::seconds(1),
561 _ => TimeDelta::days(days),
562 };
563 unit * i32::from(r.interval.unwrap_or(1).max(1))
564}
565
566fn push(out: &mut Expansion, window: &Range<DateTime<Utc>>, i: Instance) {
567 let overlaps = if i.start == i.end {
568 window.contains(&i.start)
569 } else {
570 i.start < window.end && i.end > window.start
571 };
572 if overlaps {
573 out.instances.push(i);
574 }
575}
576
577/// UNTIL as wall-clock time in the zone of DTSTART. The rule iterates in wall
578/// time, so a UTC UNTIL compared as-is cuts the last instance east of UTC.
579fn until_local(u: &PartialDateTime, start: &Stamp) -> Option<NaiveDateTime> {
580 let dt = u.to_date_time()?;
581 Some(match dt.offset {
582 Some(o) => {
583 let utc = dt.date_time - TimeDelta::seconds(o.local_minus_utc().into());
584 let local = start.zone.to_local(utc.and_utc());
585 match start.date {
586 // Clients write midnight in UTC or in their own zone. The
587 // later date is the last day either way.
588 true => utc.date().max(local.date()).and_hms_opt(23, 59, 59)?,
589 false => local,
590 }
591 }
592 // A DATE on a DATE-TIME series includes that whole day.
593 None if u.hour.is_none() && !start.date => dt.date_time.date().and_hms_opt(23, 59, 59)?,
594 // Floating, or a DATE on an all-day series: already wall time.
595 None => dt.date_time,
596 })
597}
598
599/// The last instant a rule with DTSTART `start` and UNTIL `u` starts at.
600pub(crate) fn until_utc(u: &PartialDateTime, start: &Stamp) -> Option<DateTime<Utc>> {
601 Some(start.zone.to_utc(until_local(u, start)?))
602}
603
604fn day_key(local: NaiveDateTime) -> i64 {
605 local.date().and_time(NaiveTime::MIN).and_utc().timestamp()
606}
607
608fn nominal(d: &ICalendarDuration) -> Length {
609 if d.neg {
610 return Length::Exact(TimeDelta::zero());
611 }
612 Length::Nominal {
613 days: i64::from(d.weeks) * 7 + i64::from(d.days),
614 exact: TimeDelta::seconds(
615 i64::from(d.hours) * 3600 + i64::from(d.minutes) * 60 + i64::from(d.seconds),
616 ),
617 }
618}
619
620/// The original start and end of the instance at `rid` of the series in
621/// component `master`.
622pub(crate) fn original(
623 cal: &ICalendar,
624 zones: &Zones,
625 master: usize,
626 rid: &Stamp,
627) -> Option<(DateTime<Utc>, DateTime<Utc>)> {
628 let t = Timing::of(cal, zones, master)?;
629 let start = t.utc_of(rid);
630 Some((start, t.end_at(t.start.zone.to_local(start), start)))
631}
632
633pub(crate) fn stamp(zones: &Zones, v: &PartialDateTime, tzid: Option<&str>) -> Option<Stamp> {
634 let dt = v.to_date_time()?;
635 let date = v.hour.is_none();
636 let zone = match dt.offset {
637 Some(o) if o.local_minus_utc() == 0 => Zone::Utc,
638 Some(o) => Zone::Fixed(o.local_minus_utc()),
639 None if date => zones.floating().clone(),
640 None => zones.get(tzid),
641 };
642 Some(Stamp {
643 local: dt.date_time,
644 zone,
645 date,
646 floating: !date && dt.offset.is_none() && tzid.is_none(),
647 })
648}
649
650pub(crate) fn prop_stamp(
651 zones: &Zones,
652 c: &ICalendarComponent,
653 prop: &ICalendarProperty,
654) -> Option<Stamp> {
655 let e = c.property(prop)?;
656 stamp(zones, e.values.first()?.as_partial_date_time()?, e.tz_id())
657}
658
659pub(crate) fn rule(v: &ICalendarValue) -> Option<&ICalendarRecurrenceRule> {
660 match v {
661 ICalendarValue::RecurrenceRule(r) => Some(r),
662 _ => None,
663 }
664}
665
666/// Wall-clock occurrences of `rule` from `start` up to `end`. An invalid or
667/// unsupported rule yields none.
668pub(crate) fn occurrences(
669 rule: &ICalendarRecurrenceRule,
670 start: NaiveDateTime,
671 until: Option<NaiveDateTime>,
672 end: NaiveDateTime,
673) -> impl Iterator<Item = NaiveDateTime> {
674 let wall = |t: NaiveDateTime| rrule::Tz::UTC.from_utc_datetime(&t);
675 let freq = match rule.freq {
676 ICalendarFrequency::Yearly => rrule::Frequency::Yearly,
677 ICalendarFrequency::Monthly => rrule::Frequency::Monthly,
678 ICalendarFrequency::Weekly => rrule::Frequency::Weekly,
679 ICalendarFrequency::Daily => rrule::Frequency::Daily,
680 ICalendarFrequency::Hourly => rrule::Frequency::Hourly,
681 ICalendarFrequency::Minutely => rrule::Frequency::Minutely,
682 ICalendarFrequency::Secondly => rrule::Frequency::Secondly,
683 };
684 // Other calendar scales and leap months (RFC 7529) are unsupported. RFC
685 // 7529 allows treating such a rule as absent.
686 let months: Option<Vec<chrono::Month>> = rule
687 .bymonth
688 .iter()
689 .map(|m| (!m.is_leap()).then(|| chrono::Month::try_from(m.month()).ok())?)
690 .collect();
691 let valid = months.is_some()
692 && rule
693 .rscale
694 .as_ref()
695 .is_none_or(|s| *s == CalendarScale::Gregorian)
696 && rule.skip.is_none_or(|s| s == ICalendarSkip::Omit);
697 // rrule intersects plain and numbered weekdays, RFC 5545 unites them.
698 // Numbering every occurrence of the plain ones gives the union.
699 let mixed = rule.byday.iter().any(|d| d.ordwk.is_some())
700 && rule.byday.iter().any(|d| d.ordwk.is_none());
701 let max_nth = if rule.freq == ICalendarFrequency::Monthly || !rule.bymonth.is_empty() {
702 5
703 } else {
704 53
705 };
706 let weekdays = rule
707 .byday
708 .iter()
709 .flat_map(|d| {
710 let wd = d.weekday.into();
711 match d.ordwk {
712 Some(n) => vec![rrule::NWeekday::Nth(n, wd)],
713 None if mixed => (1..=max_nth).map(|n| rrule::NWeekday::Nth(n, wd)).collect(),
714 None => vec![rrule::NWeekday::Every(wd)],
715 }
716 })
717 .collect();
718 let interval = rule.interval.unwrap_or(1).max(1);
719 // rrule loses the INTERVAL grid when it jumps to the next allowed hour or
720 // minute and the interval does not divide 60. Filter those limits here.
721 let (hours, minutes) = match rule.freq {
722 ICalendarFrequency::Minutely if 60 % interval != 0 => (rule.byhour.clone(), Vec::new()),
723 ICalendarFrequency::Secondly if 60 % interval != 0 => {
724 (rule.byhour.clone(), rule.byminute.clone())
725 }
726 _ => (Vec::new(), Vec::new()),
727 };
728 let filtered = !(hours.is_empty() && minutes.is_empty());
729 let mut r = rrule::RRule::new(freq)
730 .interval(interval)
731 .week_start(rule.wkst.map_or(Weekday::Mon, Into::into))
732 .by_set_pos(rule.bysetpos.clone())
733 .by_month(&months.unwrap_or_default())
734 .by_month_day(rule.bymonthday.clone())
735 .by_year_day(rule.byyearday.clone())
736 .by_week_no(rule.byweekno.clone())
737 .by_weekday(weekdays)
738 .by_hour(if hours.is_empty() {
739 rule.byhour.clone()
740 } else {
741 Vec::new()
742 })
743 .by_minute(if minutes.is_empty() {
744 rule.byminute.clone()
745 } else {
746 Vec::new()
747 })
748 .by_second(rule.bysecond.clone());
749 // COUNT and UNTIL together are invalid. UNTIL is the safer bound.
750 let count = rule.count.filter(|_| until.is_none());
751 if let Some(n) = count.filter(|_| !filtered) {
752 r = r.count(n);
753 }
754 if let Some(u) = until {
755 r = r.until(wall(u));
756 }
757 r.build(wall(start))
758 .ok()
759 .filter(|_| valid)
760 // Stops a rule that never matches after 100k periods, not at year 9999.
761 .map(|set| (&set.limit()).into_iter())
762 .into_iter()
763 .flatten()
764 .map(|t| t.naive_utc())
765 .filter(move |t| {
766 (hours.is_empty() || hours.contains(&(t.hour() as u8)))
767 && (minutes.is_empty() || minutes.contains(&(t.minute() as u8)))
768 })
769 .take(
770 count
771 .filter(|_| filtered)
772 .map_or(usize::MAX, |n| n as usize),
773 )
774 .take_while(move |t| *t <= end)
775}
776