//! Recurrence expansion: DTSTART + RRULE + RDATE - EXRULE - EXDATE, with
//! RECURRENCE-ID overrides applied.

use std::collections::{BTreeMap, HashMap, HashSet};
use std::ops::Range;

use calcard::common::{CalendarScale, PartialDateTime};
use calcard::icalendar::{
    ICalendar, ICalendarComponent, ICalendarComponentType, ICalendarDuration, ICalendarFrequency,
    ICalendarParameterName, ICalendarPeriod, ICalendarProperty, ICalendarRecurrenceRule,
    ICalendarSkip, ICalendarValue,
};
use chrono::{DateTime, NaiveDateTime, NaiveTime, TimeDelta, TimeZone, Timelike, Utc, Weekday};

use crate::zone::{Zone, Zones, add, add_local};

/// Occurrences the rules of one series may generate together before
/// expansion gives up.
// ponytail: COUNT, MONTHLY and YEARLY rules iterate from DTSTART, so a long
// running one can hit this. Skip ahead for them if that matters.
pub(crate) const MAX_OCCURRENCES: usize = 1_000_000;

#[derive(Debug, Clone, PartialEq)]
pub struct Instance {
    pub start: DateTime<Utc>,
    pub end: DateTime<Utc>,
    /// The original start. `None` if the component does not recur.
    pub recurrence_id: Option<DateTime<Utc>>,
    /// Index into `ICalendar::components` of the master or override that
    /// describes this instance.
    pub component: usize,
}

#[derive(Debug, Default)]
pub struct Expansion {
    /// Sorted by start.
    pub instances: Vec<Instance>,
    /// A series reached `MAX_OCCURRENCES`, so later instances are missing.
    pub truncated: bool,
    /// Occurrences the rules produced, also those outside the window.
    pub generated: usize,
}

/// The instances of all VEVENT, VTODO and VJOURNAL components that overlap
/// `window`. A zero-length instance overlaps if it starts inside.
///
/// Components are grouped by type and UID into one master and its overrides.
/// Components without DTSTART are skipped. `floating` interprets values
/// without a zone.
pub fn expand(cal: &ICalendar, window: Range<DateTime<Utc>>, floating: Zone) -> Expansion {
    expand_in(cal, &Zones::new(cal, floating), window, MAX_OCCURRENCES)
}

/// `expand` with the zones built, and at most `cap` occurrences per series.
pub(crate) fn expand_in(
    cal: &ICalendar,
    zones: &Zones,
    window: Range<DateTime<Utc>>,
    cap: usize,
) -> Expansion {
    let mut out = Expansion::default();
    let mut groups: HashMap<(&ICalendarComponentType, &str), Vec<usize>> = HashMap::new();
    for (i, c) in cal.components.iter().enumerate() {
        if !matches!(
            c.component_type,
            ICalendarComponentType::VEvent
                | ICalendarComponentType::VTodo
                | ICalendarComponentType::VJournal
        ) {
            continue;
        }
        match c.uid() {
            Some(uid) => groups.entry((&c.component_type, uid)).or_default().push(i),
            None => expand_group(cal, zones, &[i], &window, cap, &mut out),
        }
    }
    for group in groups.values() {
        expand_group(cal, zones, group, &window, cap, &mut out);
    }
    out.instances.sort_by_key(|i| (i.start, i.component));
    out
}

/// A date or date-time value and the zone it is in.
#[derive(Debug, Clone)]
pub(crate) struct Stamp {
    pub(crate) local: NaiveDateTime,
    zone: Zone,
    pub(crate) date: bool,
    /// A date-time without TZID or UTC offset.
    floating: bool,
}

impl Stamp {
    pub(crate) fn utc(&self) -> DateTime<Utc> {
        self.zone.to_utc(self.local)
    }
}

#[derive(Debug, Clone)]
enum Length {
    Exact(TimeDelta),
    /// Whole days count in wall-clock time, so a day can last 23 or 25 hours.
    Nominal {
        days: i64,
        exact: TimeDelta,
    },
}

impl Length {
    fn end(&self, zone: &Zone, local: NaiveDateTime, utc: DateTime<Utc>) -> DateTime<Utc> {
        match self {
            Length::Exact(d) => add(utc, *d),
            Length::Nominal { days, exact } => add(
                zone.to_utc(add_local(local, TimeDelta::days(*days))),
                *exact,
            ),
        }
    }

    /// An upper bound, for widening the generation window.
    fn max(&self) -> TimeDelta {
        match self {
            Length::Exact(d) => *d,
            Length::Nominal { days, exact } => TimeDelta::days(days + 1) + *exact,
        }
    }
}

/// DTSTART and length of one component.
#[derive(Debug, Clone)]
struct Timing {
    start: Stamp,
    length: Length,
    component: usize,
}

impl Timing {
    fn of(cal: &ICalendar, zones: &Zones, component: usize) -> Option<Self> {
        let c = &cal.components[component];
        let start = prop_stamp(zones, c, &ICalendarProperty::Dtstart)?;
        let end = match c.component_type {
            ICalendarComponentType::VTodo => ICalendarProperty::Due,
            _ => ICalendarProperty::Dtend,
        };
        let zero = TimeDelta::zero();
        let length = if let Some(end) = prop_stamp(zones, c, &end) {
            if start.date && end.date {
                Length::Nominal {
                    days: (end.local - start.local).num_days().max(0),
                    exact: zero,
                }
            } else {
                Length::Exact((end.utc() - start.utc()).max(zero))
            }
        } else if let Some(ICalendarValue::Duration(d)) = c
            .property(&ICalendarProperty::Duration)
            .and_then(|e| e.values.first())
        {
            nominal(d)
        } else if start.date {
            Length::Nominal {
                days: 1,
                exact: zero,
            }
        } else {
            Length::Exact(zero)
        };
        Some(Timing {
            start,
            length,
            component,
        })
    }

    fn end_at(&self, local: NaiveDateTime, utc: DateTime<Utc>) -> DateTime<Utc> {
        self.length.end(&self.start.zone, local, utc)
    }

    /// A RECURRENCE-ID, RDATE or EXDATE value. Dates and floating times are
    /// read in the zone of the series: clients write them that way.
    fn utc_of(&self, s: &Stamp) -> DateTime<Utc> {
        if s.date || s.floating {
            self.start.zone.to_utc(s.local)
        } else {
            s.utc()
        }
    }

    /// The identity of a recurrence instance. An all-day series matches by
    /// date alone, whatever zone the other value names.
    fn key(&self, s: &Stamp) -> i64 {
        if self.start.date {
            day_key(s.local)
        } else {
            self.utc_of(s).timestamp()
        }
    }

    fn member_key(&self, local: NaiveDateTime, utc: DateTime<Utc>) -> i64 {
        if self.start.date {
            day_key(local)
        } else {
            utc.timestamp()
        }
    }
}

struct Member {
    local: NaiveDateTime,
    utc: DateTime<Utc>,
    /// From an RDATE period.
    length: Option<Length>,
}

struct Override {
    sequence: i64,
    recurrence_id: DateTime<Utc>,
    timing: Timing,
}

fn expand_group(
    cal: &ICalendar,
    zones: &Zones,
    group: &[usize],
    window: &Range<DateTime<Utc>>,
    max: usize,
    out: &mut Expansion,
) {
    let comp = |i: usize| &cal.components[i];
    let sequence = |i: usize| {
        comp(i)
            .property(&ICalendarProperty::Sequence)
            .and_then(|e| e.values.first()?.as_integer())
            .unwrap_or(0)
    };
    let (overrides, masters): (Vec<usize>, Vec<usize>) = group
        .iter()
        .partition(|&&i| comp(i).has_property(&ICalendarProperty::RecurrenceId));
    // Several masters for one UID are invalid. Take the latest revision,
    // or the first one on a tie.
    let master = masters
        .into_iter()
        .rev()
        .max_by_key(|&i| sequence(i))
        .and_then(|i| Timing::of(cal, zones, i));

    // Matched by RECURRENCE-ID only. SEQUENCE picks between two overrides of
    // one instance and never decides whether an override applies.
    let mut exact: HashMap<i64, Override> = HashMap::new();
    let mut future: Vec<(i64, DateTime<Utc>, Timing)> = Vec::new();
    for i in overrides {
        let Some(e) = comp(i).property(&ICalendarProperty::RecurrenceId) else {
            continue;
        };
        let (Some(timing), Some(rid)) = (
            Timing::of(cal, zones, i),
            e.values
                .first()
                .and_then(|v| stamp(zones, v.as_partial_date_time()?, e.tz_id())),
        ) else {
            continue;
        };
        let (key, rid_utc) = match &master {
            Some(m) => (m.key(&rid), m.utc_of(&rid)),
            None => (rid.utc().timestamp(), rid.utc()),
        };
        if e.parameter(&ICalendarParameterName::Range).is_some() {
            future.push((key, rid_utc, timing.clone()));
        }
        if exact.get(&key).is_none_or(|old| sequence(i) > old.sequence) {
            let sequence = sequence(i);
            exact.insert(
                key,
                Override {
                    sequence,
                    recurrence_id: rid_utc,
                    timing,
                },
            );
        }
    }
    future.sort_by_key(|f| f.0);

    let Some(m) = master else {
        push_overrides(out, window, exact.values());
        return;
    };
    let mc = comp(m.component);
    let mz = &m.start.zone;

    let rules: Vec<_> = mc
        .properties(&ICalendarProperty::Rrule)
        .filter_map(|e| rule(e.values.first()?))
        .collect();
    let mut set: BTreeMap<i64, Member> = BTreeMap::new();
    let mut slack = m.length.max();
    // DTSTART is an instance even when it does not match the RRULE, unless
    // the series ended before it.
    let ended = !rules.is_empty()
        && rules.iter().all(|r| {
            r.until
                .as_ref()
                .and_then(|u| until_local(u, &m.start))
                .is_some_and(|u| u < m.start.local)
        });
    if !ended {
        let utc = m.start.utc();
        set.insert(
            m.member_key(m.start.local, utc),
            Member {
                local: m.start.local,
                utc,
                length: None,
            },
        );
    }
    for e in mc.properties(&ICalendarProperty::Rdate) {
        for v in &e.values {
            let (s, length) = match v {
                ICalendarValue::PartialDateTime(p) => {
                    let Some(s) = stamp(zones, p, e.tz_id()) else {
                        continue;
                    };
                    (s, None)
                }
                ICalendarValue::Period(ICalendarPeriod::Range { start, end }) => {
                    let (Some(s), Some(end)) =
                        (stamp(zones, start, e.tz_id()), stamp(zones, end, e.tz_id()))
                    else {
                        continue;
                    };
                    let d = (end.utc() - s.utc()).max(TimeDelta::zero());
                    (s, Some(Length::Exact(d)))
                }
                ICalendarValue::Period(ICalendarPeriod::Duration { start, duration }) => {
                    let Some(s) = stamp(zones, start, e.tz_id()) else {
                        continue;
                    };
                    (s, Some(nominal(duration)))
                }
                _ => continue,
            };
            let utc = m.utc_of(&s);
            let local = mz.to_local(utc);
            if let Some(l) = &length {
                slack = slack.max(l.max());
            }
            // A period on DTSTART or a rule instance still sets its length.
            let member = set.entry(m.key(&s)).or_insert(Member {
                local,
                utc,
                length: None,
            });
            member.length = length.or(member.length.take());
        }
    }
    for (_, rid, t) in &future {
        slack = slack.max((t.start.utc() - *rid).abs() + t.length.max());
    }
    let wide = slack
        .checked_add(&TimeDelta::days(1))
        .unwrap_or(TimeDelta::MAX);
    let reach = add(window.start, -wide);
    // A huge DURATION would run an endless rule to the cap, so the rules
    // iterate at most 1000 periods of the fastest rule around the window.
    // ponytail: a rule instance longer than that is missed where it starts early.
    let cap = mc
        .properties(&ICalendarProperty::Rrule)
        .chain(mc.properties(&ICalendarProperty::Exrule))
        .filter_map(|e| rule(e.values.first()?))
        .map(|r| period(r) * 1000)
        .min();
    let slack = cap.map_or(wide, |c| wide.min(c + TimeDelta::days(1)));
    let (from, to) = (add(window.start, -slack), add(window.end, slack));
    let (from_local, to_local) = (mz.to_local(from), mz.to_local(to));

    let mut budget = max;
    let mut excluded = HashSet::new();
    for e in mc.properties(&ICalendarProperty::Exrule) {
        let Some(rule) = e.values.first().and_then(rule) else {
            continue;
        };
        for local in occurrences_capped(rule, &m, from_local, to_local, &mut budget, out) {
            excluded.insert(m.member_key(local, mz.to_utc(local)));
        }
    }
    // ponytail: sub-daily rules iterate in wall time. A DST fall-back skips the
    // repeated hour, and a spring-forward collapses a shifted instance into the
    // next (COUNT=5 gives 4). Iterate in elapsed time, BYHOUR in local, to fix.
    for rule in rules {
        for local in occurrences_capped(rule, &m, from_local, to_local, &mut budget, out) {
            let utc = mz.to_utc(local);
            if utc >= from {
                set.entry(m.member_key(local, utc)).or_insert(Member {
                    local,
                    utc,
                    length: None,
                });
            }
        }
    }

    // A DATE EXDATE on a DATE-TIME series removes every instance on that day.
    let mut excluded_days = HashSet::new();
    for e in mc.properties(&ICalendarProperty::Exdate) {
        for s in e
            .values
            .iter()
            .filter_map(|v| stamp(zones, v.as_partial_date_time()?, e.tz_id()))
        {
            if s.date && !m.start.date {
                excluded_days.insert(s.local.date());
            } else {
                excluded.insert(m.key(&s));
            }
        }
    }

    // An EXDATE removes an override of that instance too. An override whose
    // RECURRENCE-ID matches no instance still shows, as in clients.
    push_overrides(
        out,
        window,
        exact.iter().filter_map(|(key, o)| {
            let day = mz.to_local(o.recurrence_id).date();
            (!excluded.contains(key) && !excluded_days.contains(&day)).then_some(o)
        }),
    );

    let recurs =
        mc.has_property(&ICalendarProperty::Rrule) || mc.has_property(&ICalendarProperty::Rdate);
    for (key, member) in &set {
        if member.utc < reach
            || excluded.contains(key)
            || excluded_days.contains(&member.local.date())
            || exact.contains_key(key)
        {
            continue;
        }
        let recurrence_id = recurs.then_some(member.utc);
        // The latest THISANDFUTURE override before this instance moves it by
        // the same offset and gives it the override's length. The offset is
        // wall-clock time, so later instances keep their local time across DST.
        let latest = future.partition_point(|f| f.0 <= *key).checked_sub(1);
        let instance = match latest.map(|i| &future[i]) {
            Some((_, rid, t)) => {
                let shift = mz.to_local(t.start.utc()) - mz.to_local(*rid);
                let start = mz.to_utc(add_local(member.local, shift));
                Instance {
                    start,
                    end: t.end_at(t.start.zone.to_local(start), start),
                    recurrence_id,
                    component: t.component,
                }
            }
            None => Instance {
                start: member.utc,
                end: member.length.as_ref().map_or_else(
                    || m.end_at(member.local, member.utc),
                    |l| l.end(mz, member.local, member.utc),
                ),
                recurrence_id,
                component: m.component,
            },
        };
        push(out, window, instance);
    }
}

fn push_overrides<'a>(
    out: &mut Expansion,
    window: &Range<DateTime<Utc>>,
    overrides: impl Iterator<Item = &'a Override>,
) {
    for o in overrides {
        let t = &o.timing;
        let start = t.start.utc();
        let end = t.end_at(t.start.local, start);
        push(
            out,
            window,
            Instance {
                start,
                end,
                recurrence_id: Some(o.recurrence_id),
                component: t.component,
            },
        );
    }
}

fn occurrences_capped(
    rule: &ICalendarRecurrenceRule,
    m: &Timing,
    from_local: NaiveDateTime,
    to_local: NaiveDateTime,
    budget: &mut usize,
    out: &mut Expansion,
) -> Vec<NaiveDateTime> {
    let until = match &rule.until {
        Some(u) => match until_local(u, &m.start) {
            Some(u) => Some(u),
            None => return Vec::new(),
        },
        None => None,
    };
    // Whole steps keep the period grid, so INTERVAL and BYxxx still line up.
    let unit = match rule.freq {
        ICalendarFrequency::Weekly => 7 * 86400,
        ICalendarFrequency::Daily => 86400,
        ICalendarFrequency::Hourly => 3600,
        ICalendarFrequency::Minutely => 60,
        ICalendarFrequency::Secondly => 1,
        _ => 0,
    };
    let mut first = m.start.local;
    // BYSETPOS picks from a whole period, which a mid-period start would cut.
    if unit > 0 && rule.count.is_none() && rule.bysetpos.is_empty() {
        let step = unit * i64::from(rule.interval.unwrap_or(1).max(1));
        let behind = (from_local - first).num_seconds();
        if behind > 0 {
            first += TimeDelta::seconds(behind / step * step);
        }
    }
    let mut list: Vec<_> = occurrences(rule, first, until, to_local)
        .take(*budget + 1)
        .collect();
    if list.len() > *budget {
        list.pop();
        out.truncated = true;
    }
    *budget -= list.len();
    out.generated += list.len();
    // DTSTART is the first of COUNT (RFC 5545, 3.3.10), also when the rule
    // skips it.
    if let Some(n) = rule.count.filter(|_| until.is_none()).map(|n| n as usize)
        && list.first() != Some(&m.start.local)
        && list.len() >= n
    {
        list.truncate(n.saturating_sub(1));
    }
    list
}

/// The longest time between two periods of `r`.
fn period(r: &ICalendarRecurrenceRule) -> TimeDelta {
    let days = match r.freq {
        ICalendarFrequency::Yearly => 366,
        ICalendarFrequency::Monthly => 31,
        ICalendarFrequency::Weekly => 7,
        _ => 1,
    };
    let unit = match r.freq {
        ICalendarFrequency::Hourly => TimeDelta::hours(1),
        ICalendarFrequency::Minutely => TimeDelta::minutes(1),
        ICalendarFrequency::Secondly => TimeDelta::seconds(1),
        _ => TimeDelta::days(days),
    };
    unit * i32::from(r.interval.unwrap_or(1).max(1))
}

fn push(out: &mut Expansion, window: &Range<DateTime<Utc>>, i: Instance) {
    let overlaps = if i.start == i.end {
        window.contains(&i.start)
    } else {
        i.start < window.end && i.end > window.start
    };
    if overlaps {
        out.instances.push(i);
    }
}

/// UNTIL as wall-clock time in the zone of DTSTART. The rule iterates in wall
/// time, so a UTC UNTIL compared as-is cuts the last instance east of UTC.
fn until_local(u: &PartialDateTime, start: &Stamp) -> Option<NaiveDateTime> {
    let dt = u.to_date_time()?;
    Some(match dt.offset {
        Some(o) => {
            let utc = dt.date_time - TimeDelta::seconds(o.local_minus_utc().into());
            let local = start.zone.to_local(utc.and_utc());
            match start.date {
                // Clients write midnight in UTC or in their own zone. The
                // later date is the last day either way.
                true => utc.date().max(local.date()).and_hms_opt(23, 59, 59)?,
                false => local,
            }
        }
        // A DATE on a DATE-TIME series includes that whole day.
        None if u.hour.is_none() && !start.date => dt.date_time.date().and_hms_opt(23, 59, 59)?,
        // Floating, or a DATE on an all-day series: already wall time.
        None => dt.date_time,
    })
}

/// The last instant a rule with DTSTART `start` and UNTIL `u` starts at.
pub(crate) fn until_utc(u: &PartialDateTime, start: &Stamp) -> Option<DateTime<Utc>> {
    Some(start.zone.to_utc(until_local(u, start)?))
}

fn day_key(local: NaiveDateTime) -> i64 {
    local.date().and_time(NaiveTime::MIN).and_utc().timestamp()
}

fn nominal(d: &ICalendarDuration) -> Length {
    if d.neg {
        return Length::Exact(TimeDelta::zero());
    }
    Length::Nominal {
        days: i64::from(d.weeks) * 7 + i64::from(d.days),
        exact: TimeDelta::seconds(
            i64::from(d.hours) * 3600 + i64::from(d.minutes) * 60 + i64::from(d.seconds),
        ),
    }
}

/// The original start and end of the instance at `rid` of the series in
/// component `master`.
pub(crate) fn original(
    cal: &ICalendar,
    zones: &Zones,
    master: usize,
    rid: &Stamp,
) -> Option<(DateTime<Utc>, DateTime<Utc>)> {
    let t = Timing::of(cal, zones, master)?;
    let start = t.utc_of(rid);
    Some((start, t.end_at(t.start.zone.to_local(start), start)))
}

pub(crate) fn stamp(zones: &Zones, v: &PartialDateTime, tzid: Option<&str>) -> Option<Stamp> {
    let dt = v.to_date_time()?;
    let date = v.hour.is_none();
    let zone = match dt.offset {
        Some(o) if o.local_minus_utc() == 0 => Zone::Utc,
        Some(o) => Zone::Fixed(o.local_minus_utc()),
        None if date => zones.floating().clone(),
        None => zones.get(tzid),
    };
    Some(Stamp {
        local: dt.date_time,
        zone,
        date,
        floating: !date && dt.offset.is_none() && tzid.is_none(),
    })
}

fn prop_stamp(zones: &Zones, c: &ICalendarComponent, prop: &ICalendarProperty) -> Option<Stamp> {
    let e = c.property(prop)?;
    stamp(zones, e.values.first()?.as_partial_date_time()?, e.tz_id())
}

pub(crate) fn rule(v: &ICalendarValue) -> Option<&ICalendarRecurrenceRule> {
    match v {
        ICalendarValue::RecurrenceRule(r) => Some(r),
        _ => None,
    }
}

/// Wall-clock occurrences of `rule` from `start` up to `end`. An invalid or
/// unsupported rule yields none.
pub(crate) fn occurrences(
    rule: &ICalendarRecurrenceRule,
    start: NaiveDateTime,
    until: Option<NaiveDateTime>,
    end: NaiveDateTime,
) -> impl Iterator<Item = NaiveDateTime> {
    let wall = |t: NaiveDateTime| rrule::Tz::UTC.from_utc_datetime(&t);
    let freq = match rule.freq {
        ICalendarFrequency::Yearly => rrule::Frequency::Yearly,
        ICalendarFrequency::Monthly => rrule::Frequency::Monthly,
        ICalendarFrequency::Weekly => rrule::Frequency::Weekly,
        ICalendarFrequency::Daily => rrule::Frequency::Daily,
        ICalendarFrequency::Hourly => rrule::Frequency::Hourly,
        ICalendarFrequency::Minutely => rrule::Frequency::Minutely,
        ICalendarFrequency::Secondly => rrule::Frequency::Secondly,
    };
    // Other calendar scales and leap months (RFC 7529) are unsupported. RFC
    // 7529 allows treating such a rule as absent.
    let months: Option<Vec<chrono::Month>> = rule
        .bymonth
        .iter()
        .map(|m| (!m.is_leap()).then(|| chrono::Month::try_from(m.month()).ok())?)
        .collect();
    let valid = months.is_some()
        && rule
            .rscale
            .as_ref()
            .is_none_or(|s| *s == CalendarScale::Gregorian)
        && rule.skip.is_none_or(|s| s == ICalendarSkip::Omit);
    // rrule intersects plain and numbered weekdays, RFC 5545 unites them.
    // Numbering every occurrence of the plain ones gives the union.
    let mixed = rule.byday.iter().any(|d| d.ordwk.is_some())
        && rule.byday.iter().any(|d| d.ordwk.is_none());
    let max_nth = if rule.freq == ICalendarFrequency::Monthly || !rule.bymonth.is_empty() {
        5
    } else {
        53
    };
    let weekdays = rule
        .byday
        .iter()
        .flat_map(|d| {
            let wd = d.weekday.into();
            match d.ordwk {
                Some(n) => vec![rrule::NWeekday::Nth(n, wd)],
                None if mixed => (1..=max_nth).map(|n| rrule::NWeekday::Nth(n, wd)).collect(),
                None => vec![rrule::NWeekday::Every(wd)],
            }
        })
        .collect();
    let interval = rule.interval.unwrap_or(1).max(1);
    // rrule loses the INTERVAL grid when it jumps to the next allowed hour or
    // minute and the interval does not divide 60. Filter those limits here.
    let (hours, minutes) = match rule.freq {
        ICalendarFrequency::Minutely if 60 % interval != 0 => (rule.byhour.clone(), Vec::new()),
        ICalendarFrequency::Secondly if 60 % interval != 0 => {
            (rule.byhour.clone(), rule.byminute.clone())
        }
        _ => (Vec::new(), Vec::new()),
    };
    let filtered = !(hours.is_empty() && minutes.is_empty());
    let mut r = rrule::RRule::new(freq)
        .interval(interval)
        .week_start(rule.wkst.map_or(Weekday::Mon, Into::into))
        .by_set_pos(rule.bysetpos.clone())
        .by_month(&months.unwrap_or_default())
        .by_month_day(rule.bymonthday.clone())
        .by_year_day(rule.byyearday.clone())
        .by_week_no(rule.byweekno.clone())
        .by_weekday(weekdays)
        .by_hour(if hours.is_empty() {
            rule.byhour.clone()
        } else {
            Vec::new()
        })
        .by_minute(if minutes.is_empty() {
            rule.byminute.clone()
        } else {
            Vec::new()
        })
        .by_second(rule.bysecond.clone());
    // COUNT and UNTIL together are invalid. UNTIL is the safer bound.
    let count = rule.count.filter(|_| until.is_none());
    if let Some(n) = count.filter(|_| !filtered) {
        r = r.count(n);
    }
    if let Some(u) = until {
        r = r.until(wall(u));
    }
    r.build(wall(start))
        .ok()
        .filter(|_| valid)
        // Stops a rule that never matches after 100k periods, not at year 9999.
        .map(|set| (&set.limit()).into_iter())
        .into_iter()
        .flatten()
        .map(|t| t.naive_utc())
        .filter(move |t| {
            (hours.is_empty() || hours.contains(&(t.hour() as u8)))
                && (minutes.is_empty() || minutes.contains(&(t.minute() as u8)))
        })
        .take(
            count
                .filter(|_| filtered)
                .map_or(usize::MAX, |n| n as usize),
        )
        .take_while(move |t| *t <= end)
}