Recurrence rule expansion

Deep dive

How it works

Parts:

• Rule — DTSTART, FREQ, INTERVAL, COUNT or UNTIL, BYxxx filters, WKST (week start, default MO).
• Period walker — steps FREQ x INTERVAL from DTSTART; each period is a candidate set.
• Civil-date layer — days-from-civil, weekday, month length; integers, no zone.
• Set operations — RDATE added, EXDATE removed; RECURRENCE-ID overrides replace one instance (matched by UID and original start).
• Zone converter — local to UTC per occurrence.

1. Start at DTSTART's period, then add INTERVAL periods per step.
2. Per period, expand BYxxx parts finer than FREQ and limit the others (table, verified against RFC 5545 §3.3.10).
3. 2TU is the second Tuesday of the month, -1FR the last Friday, BYMONTHDAY=-1 the last day; nonexistent dates are dropped.
4. BYSETPOS picks positions in the period's sorted set ("last weekday": BYDAY=MO,TU,WE,TH,FR;BYSETPOS=-1).
5. Drop instances before DTSTART; stop at COUNT (DTSTART is the first instance) or past UNTIL.
6. Apply EXDATE, merge RDATE, swap overridden instances.
7. Convert each local time to UTC for that date.

rule ──▶ period walker ──▶ BYxxx expand/limit ──▶ BYSETPOS ──▶ COUNT/UNTIL
          (lazy cursor)                                          │
        RDATE ──▶ merge ──▶ drop EXDATE ──▶ RECURRENCE-ID swap ──▶ local→UTC ──▶ out

Time zones. RFC 5545 §3.3.5: an ambiguous local time (clocks back) means the first occurrence; a nonexistent one (clocks forward) uses the offset before the gap, so 02:30 on the spring day is 03:30 daylight time. §3.3.10 is stricter for RRULE output: instances at a nonexistent local time MUST be ignored and not counted. Expand first, convert second.

Code

Monthly rules only, with INTERVAL, COUNT, UNTIL, EXDATE. Civil dates use Howard Hinnant's algorithms; the zone step is a fixed 2026 Europe/Berlin rule, no tz database.

// Days since 1970-01-01 <-> civil date (Howard Hinnant's algorithms).
fn days_from_civil(y: i64, m: i64, d: i64) -> i64 {
    let y = if m <= 2 { y - 1 } else { y };
    let era = y.div_euclid(400);
    let yoe = y - era * 400;
    let doy = (153 * (if m > 2 { m - 3 } else { m + 9 }) + 2) / 5 + d - 1;
    era * 146097 + yoe * 365 + yoe / 4 - yoe / 100 + doy - 719468
}
fn civil_from_days(z: i64) -> (i64, i64, i64) {
    let z = z + 719468;
    let era = z.div_euclid(146097);
    let doe = z - era * 146097;
    let yoe = (doe - doe / 1460 + doe / 36524 - doe / 146096) / 365;
    let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
    let mp = (5 * doy + 2) / 153;
    let d = doy - (153 * mp + 2) / 5 + 1;
    let m = if mp < 10 { mp + 3 } else { mp - 9 };
    (yoe + era * 400 + (m <= 2) as i64, m, d)
}
fn weekday(z: i64) -> i64 { (z + 4).rem_euclid(7) } // 0 = Sunday (1970-01-01 was a Thursday)
fn month_len(y: i64, m: i64) -> i64 {
    let (ny, nm) = if m == 12 { (y + 1, 1) } else { (y, m + 1) };
    days_from_civil(ny, nm, 1) - days_from_civil(y, m, 1)
}

enum By { NthWeekday(i64, i64), MonthDay(i64) } // (ordinal, weekday) e.g. (2, 2) = 2TU, (-1, 5) = -1FR
struct Rule { start: i64, by: By, interval: i64, count: Option<usize>, until: Option<i64>, ex: Vec<i64> }

impl Rule {
    /// Day of month selected in (y, m), or None: invalid dates are skipped (RFC 5545 §3.3.10).
    fn pick(&self, y: i64, m: i64) -> Option<i64> {
        let len = month_len(y, m);
        let d = match self.by {
            By::MonthDay(n) => if n > 0 { n } else { len + 1 + n },
            By::NthWeekday(n, wd) => {
                let first = weekday(days_from_civil(y, m, 1));
                            if n > 0 { 1 + (wd - first).rem_euclid(7) + 7 * (n - 1) }
                else { len - (weekday(days_from_civil(y, m, len)) - wd).rem_euclid(7) + 7 * (n + 1) }
            }
        };
        (1..=len).contains(&d).then_some(days_from_civil(y, m, d))
    }
    fn iter(&self) -> Occ<'_> {
        let (y, m, _) = civil_from_days(self.start);
        Occ { r: self, y, m, made: 0, misses: 0 }
    }
}
struct Occ<'a> { r: &'a Rule, y: i64, m: i64, made: usize, misses: u32 }

impl Iterator for Occ<'_> {
    type Item = i64; // day number; time of day is added by the caller
    fn next(&mut self) -> Option<i64> {
        loop {
            if self.r.count.is_some_and(|c| self.made >= c) { return None; }
            let cand = self.r.pick(self.y, self.m);
            let k = self.y * 12 + self.m - 1 + self.r.interval;
            (self.y, self.m) = (k.div_euclid(12), k.rem_euclid(12) + 1);
            match cand {
                Some(d) if d >= self.r.start => {
                    if self.r.until.is_some_and(|u| d > u) { return None; }
                    self.made += 1; // COUNT counts before EXDATE
                    self.misses = 0;
                    if !self.r.ex.contains(&d) { return Some(d); }
                }
                _ => { self.misses += 1; if self.misses > 1200 { return None; } } // rule can never match
            }
        }
    }
}

// Berlin 2026: +120 min from the last Sunday of March to that of October, else +60 (not valid in the 02:00-03:00 hour).
fn berlin_utc_minute(day: i64, local_min: i64) -> i64 {
    let last_sun = |m| Rule { start: days_from_civil(2026, m, 1), by: By::NthWeekday(-1, 0), interval: 1, count: Some(1), until: None, ex: vec![] }.iter().next().unwrap();
    let off = if day >= last_sun(3) && day < last_sun(10) { 120 } else { 60 };
    day * 1440 + local_min - off
}

fn main() {
    let ymd = |y, m, d| days_from_civil(y, m, d);
    assert_eq!(weekday(ymd(2026, 10, 21)), 3); // Wednesday
    let rule = |by, count, until, ex| Rule { start: ymd(2026, 1, 1), by, interval: 1, count, until, ex };
    let fmt = |z| { let (y, m, d) = civil_from_days(z); format!("{y}-{m:02}-{d:02}") };

    let tue2: Vec<_> = rule(By::NthWeekday(2, 2), Some(12), None, vec![]).iter().map(fmt).collect();
    assert_eq!(tue2.join(" "), "2026-01-13 2026-02-10 2026-03-10 2026-04-14 2026-05-12 2026-06-09 2026-07-14 2026-08-11 2026-09-08 2026-10-13 2026-11-10 2026-12-08");

    for (i, d) in rule(By::NthWeekday(-1, 5), Some(12), None, vec![]).iter().enumerate() {
        let (y, m, day) = civil_from_days(d);
        assert!(weekday(d) == 5 && day + 7 > month_len(y, m) && m == i as i64 + 1);
    }
    let r31 = rule(By::MonthDay(31), None, Some(ymd(2026, 12, 31)), vec![]);
    assert_eq!(r31.iter().count(), 7); // Jan Mar May Jul Aug Oct Dec
    assert_eq!(rule(By::NthWeekday(2, 2), Some(5), None, vec![]).iter().count(), 5); // COUNT stops exactly
    let ex = rule(By::NthWeekday(2, 2), Some(4), None, vec![ymd(2026, 2, 10)]).iter().map(fmt).collect::<Vec<_>>();
    assert_eq!(ex, ["2026-01-13", "2026-03-10", "2026-04-14"]); // EXDATE removes one, COUNT unaffected
    assert_eq!(rule(By::NthWeekday(2, 2), None, None, vec![]).iter().take(3).count(), 3); // unbounded, lazy
    assert_eq!(berlin_utc_minute(ymd(2026, 3, 10), 540) % 1440, 8 * 60); // CET: 09:00 = 08:00 UTC
    assert_eq!(berlin_utc_minute(ymd(2026, 4, 14), 540) % 1440, 7 * 60); // CEST: 09:00 = 07:00 UTC
    println!("ok");
}

Compiled and run; all asserts pass; the 2TU dates were hand-checked.

Complexity and constants

• Each instance costs O(1): a few integer operations on days since 1970; skipped periods cost the same and emit nothing.
• A rule with no valid date needs a miss guard (here 1200 periods, arbitrary).
• State is a cursor and a counter; a horizon of k instances costs k steps plus k zone lookups.

Efficiency

• Cost: integer arithmetic per instance, no allocation; compute-bound, zone lookup largest. Not measured.
• Levers:
  • Lazy iterator plus seek by period index — work only for the window asked — unbounded rules.
  • Rolling materialised horizon — a job inserts the next weeks into an index, reads become range scans — calendar views, durable-job-queue triggers.
  • Store the rule, not rows — one row replaces thousands — any series.
• Naive → standard → state of the art:
  • Expand to a fixed year, store rows · O(total) space.
  • Lazy expansion over a window with an EXDATE set · O(window).
  • Rule plus rolling horizon plus next-fire timer in a hierarchical-timing-wheel · O(1) per due occurrence.

Implementation notes

• UNTIL with a zoned DTSTART must be UTC.
• Key overrides by (UID, RECURRENCE-ID); changing the rule's time orphans them.
• Index the next occurrence as a UTC instant; derive successors from the rule, not by adding a duration.

Pitfalls

• Adding 24 h or 7 days in UTC: local time slips at DST changes.
• Counting skipped dates in COUNT; exceptions come off after counting.
• BYMONTHDAY=31 means 7 months a year; "month end" is -1.
• rrule.js returns "floating" local times tagged UTC; do not read them as real UTC.

Variants and alternatives

In production

Calendar and CalDAV software (meetings), appointment and medication schedulers (healthcare), on-call and maintenance-window tools (operations), subscription billing (retail, finance), timetables (education).

Implementations

Sources

• B. Desruisseaux (ed.), Internet Calendaring and Scheduling Core Object Specification (iCalendar), RFC 5545, 2009, §3.3.5, §3.3.10, §3.8.4.4, §3.8.5. RFC
• Howard Hinnant, chrono-Compatible Low-Level Date Algorithms. page
• python-dateutil, rrule documentation. docs