///|
/// Why an expansion can fail even though the rule parsed.
#derive(Debug, Eq)
pub(all) suberror ExpandError {
  /// The rule uses a feature outside this package's supported boundary.
  Unsupported(feature~ : String)
  /// The rule is syntactically fine but semantically invalid with the
  /// `DTSTART` it was given; these checks were deferred from parsing
  /// because only expansion knows the `DTSTART`.
  Invalid(message~ : String)
}

///|
pub extend ExpandError with @moonbitlang/core/debug.Debug::{to_repr}

///|
pub extend ExpandError with Eq::{not_equal, equal}

///|
pub impl Show for ExpandError with fn output(self, logger) {
  match self {
    Unsupported(feature=f) =>
      logger.write_string("unsupported RRULE feature in expansion: \{f}")
    Invalid(message=m) => logger.write_string("invalid recurrence rule: \{m}")
  }
}

///|
pub extend ExpandError with Show::{to_string, output}

///|
/// A safety bound on walked periods. Reaching it without natural termination
/// or the requested instance limit is an explicit failure, even for empty output.
const MAX_PERIODS : Int32 = 10_000

///|
/// The last year moonbitlang/x's `PlainDate` can represent (its
/// `validate_year` bound). A candidate past it ends the expansion walk —
/// see [`expand`].
const MAX_PLAIN_YEAR : Int64 = 9999

///|
/// Expand a parsed [`Rule`] against its `DTSTART` into the occurrence
/// date-times of the series, in chronological order (RFC 5545 §3.3.10).
///
/// Supports the calendar-grade RFC 5545 rules in this project: `DAILY` /
/// `WEEKLY` / `MONTHLY` / `YEARLY`, ordinal `BYDAY`, positive and negative
/// `BYMONTHDAY`, `BYSETPOS`, `BYMONTH`, and `WKST`. The semantic
/// checks that need the `DTSTART` (`COUNT` + `UNTIL` exclusivity, `UNTIL`
/// value-type agreement) happen here.
///
/// Occurrences are wall-clock arithmetic: every occurrence carries the
/// `DTSTART`'s clock time, UTC offset, zone spelling, and all-day flag
/// unchanged (see [`@model.IcalDateTime::on_date`]). The binding is explicitly
/// fixed; dynamic TZIDs are rejected during parsing. A `DTSTART` that does not match the rule
/// is not forced into the series: the first occurrence is the first
/// matching date, exactly as the reference corpus behaves.
///
/// `COUNT` counts occurrences from the first match (RFC 5545 counts the
/// `DTSTART` only when it matches); `UNTIL` bounds the series
/// inclusively, compared by instant. `limit` caps how many occurrences
/// are returned — the safety valve for unbounded rules — and never
/// truncates a `COUNT`/`UNTIL` rule that ends within it. A series whose
/// next candidate would fall past the representable calendar (year 9999
/// in moonbitlang/x) ends there rather than raising, whatever `INTERVAL`
/// says — the huge-interval products are computed in 64-bit for the same
/// reason: a wrapped 32-bit product can name a *valid but wrong* date.
///
/// # Example
/// ```mbt nocheck
/// fn test_example() raise {
///   let rule = @rrule.parse_rule("FREQ=DAILY;COUNT=3")
///   let dtstart = @model.parse_single_date_time(
///     "20260901T090000Z",
///     @model.ZoneTable::empty(),
///   )
///   let occurrences = @rrule.expand(rule, dtstart)
///   assert_eq(occurrences.length(), 3)
///   assert_eq(occurrences[2].to_string(), "2026-09-03T09:00:00Z")
/// }
/// ```
pub fn expand(
  rule : Rule,
  dtstart : @model.IcalDateTime,
  limit~ : Int32 = 200,
) -> Array[@model.IcalDateTime] raise {
  let (out, exhausted) = expand_generated(rule, dtstart, limit~)
  if !exhausted && limit > 0 && out.length() < limit {
    raise ExpandError::Invalid(
      message="recurrence expansion exceeded \{MAX_PERIODS} periods without ending",
    )
  }
  out
}

///|
fn expand_generated(
  rule : Rule,
  dtstart : @model.IcalDateTime,
  limit~ : Int32,
) -> (Array[@model.IcalDateTime], Bool) raise {
  check_expandable(rule, dtstart)
  if limit <= 0 {
    // A cap of zero or less caps everything. The semantic checks above
    // still ran, so an invalid rule is reported rather than silently
    // empty — only the count is clamped. (Before S14 the first candidate
    // was pushed before the limit was consulted and limit=0 returned it.)
    return ([], false)
  }
  let normalized = NormalizedRule::new(rule)
  let rule = normalized.rule
  if provably_empty(rule, normalized, dtstart.wall.month()) {
    // Every (month length x month-start weekday) combination the BYDAY
    // ordinals could match is exhausted against the BYMONTHDAY set — a
    // month's structure is fully determined by those two inputs and every
    // combination occurs across the Gregorian cycle, so the series is
    // empty by construction. Ending here (instead of walking MAX_PERIODS
    // empty periods) keeps a never-matching rule from surfacing as a
    // budget error — which, over CalDAV, let one stored resource fail
    // every REPORT over its collection, and blocked the single-threaded
    // event loop for the whole walk on a PUT-door validation.
    return ([], true)
  }
  let start = plain_date_of(dtstart.wall)
  let until_instant : Int64? = match rule.until {
    Some(u) => Some(u.instant_seconds())
    None => None
  }
  let out : Array[@model.IcalDateTime] = []
  let mut done = false
  let mut exhausted = false
  let mut period = 0
  while !done && period < MAX_PERIODS {
    let candidates : Array[@time.PlainDate] = match
      candidates_for(normalized, start, period) {
      // The next candidate would fall outside the representable calendar
      // (year -9999..9999 in moonbitlang/x), so the series has reached the
      // end of every date it could ever express — the walk is over, not
      // failed. Without this the walk raised x/time's untyped Failure
      // instead of ending (INTERVAL in the hundreds on MONTHLY, or an
      // Int32 product wrapping negative on WEEKLY/DAILY).
      None => {
        done = true
        exhausted = true
        []
      }
      Some(days) => days
    }
    for day in candidates {
      if day < start {
        continue
      }
      let occ = dtstart.on_date(day)
      let past_until = match until_instant {
        Some(u) => occ.instant_seconds() > u
        None => false
      }
      if past_until {
        // Candidates are chronological, so everything after this
        // occurrence is past UNTIL too — the series is finished.
        done = true
        exhausted = true
        break
      }
      if out.length() > 0 && out[out.length() - 1].compare(occ) == 0 {
        continue
      }
      out.push(occ)
      match rule.count {
        Some(cap) =>
          if out.length() >= cap {
            done = true
            exhausted = true
            break
          }
        None => ()
      }
      if out.length() >= limit {
        done = true
        break
      }
    }
    period = period + 1
  }
  // Period-budget exhaustion is independent of whether any candidates matched.
  // Strict callers reject a short prefix; queries expose the incomplete state.
  (out, exhausted)
}

///|
/// Normalize BYMONTH and BYMONTHDAY once for all periods. Cache the realized
/// day numbers for every possible month length; negative days depend on that
/// length, but not on the particular year or month.
priv struct NormalizedRule {
  rule : Rule
  monthdays_by_length : Array[Array[Int32]]
}

///|
fn NormalizedRule::new(rule : Rule) -> NormalizedRule {
  let bymonth = rule.bymonth.copy()
  let bymonthday = rule.bymonthday.copy()
  bymonth.sort()
  bymonthday.sort()
  let sorted_rule = { ..rule, bymonth, bymonthday, }
  let monthdays_by_length : Array[Array[Int32]] = []
  for days_in_month in 28..<=31 {
    let days : Array[Int32] = []
    for raw_day in bymonthday {
      let day = if raw_day > 0 { raw_day } else { days_in_month + raw_day + 1 }
      if day >= 1 && day <= days_in_month {
        days.push(day)
      }
    }
    days.sort()
    monthdays_by_length.push(days)
  }
  { rule: sorted_rule, monthdays_by_length, }
}

///|
/// The gate every expansion passes first: DTSTART-dependent semantic checks
/// deferred from parsing happen here, along with RFC placement constraints.
fn check_expandable(rule : Rule, dtstart : @model.IcalDateTime) -> Unit raise {
  for entry in rule.byday {
    if entry.ordinal != 0 && (rule.freq is Daily || rule.freq is Weekly) {
      raise ExpandError::Invalid(
        message="ordinal BYDAY is only valid with MONTHLY or YEARLY",
      )
    }
  }
  // RFC 5545 §3.3.10: "The BYMONTHDAY rule part MUST NOT be specified when
  // the FREQ rule part is set to WEEKLY."
  if rule.bymonthday.length() > 0 && rule.freq is Weekly {
    raise ExpandError::Invalid(
      message="BYMONTHDAY must not be specified with WEEKLY",
    )
  }
  if rule.bysetpos.length() > 0 &&
    rule.byday.length() == 0 &&
    rule.bymonthday.length() == 0 &&
    rule.bymonth.length() == 0 {
    raise ExpandError::Invalid(message="BYSETPOS requires another BY rule")
  }
  match (rule.count, rule.until) {
    (Some(_), Some(_)) =>
      raise ExpandError::Invalid(
        message="COUNT and UNTIL are mutually exclusive",
      )
    _ => ()
  }
  match rule.until {
    Some(u) =>
      if u.all_day != dtstart.all_day {
        raise ExpandError::Invalid(
          message="UNTIL must have the same value type as DTSTART",
        )
      }
    None => ()
  }
}

///|
/// The candidate dates of period `period`, in chronological order. How
/// much of the calendar one period covers is what the frequency means:
/// one interval-step of days, weeks, months, or years.
fn candidates_for(
  normalized : NormalizedRule,
  start : @time.PlainDate,
  period : Int32,
) -> Array[@time.PlainDate]? raise {
  let rule = normalized.rule
  let all : Array[@time.PlainDate]? = match rule.freq {
    Daily => daily_candidates(normalized, start, period)
    Weekly => weekly_candidates(normalized, start, period)
    Monthly => monthly_candidates(normalized, start, period)
    Yearly => yearly_candidates(normalized, start, period)
  }
  match all {
    None => None
    Some(days) => {
      days.sort_by((a, b) => Compare::compare(a, b))
      let unique : Array[@time.PlainDate] = []
      for day in days {
        if unique.length() == 0 || unique[unique.length() - 1] != day {
          unique.push(day)
        }
      }
      Some(apply_setpos(unique, rule.bysetpos))
    }
  }
}

///|
/// Select positions from one frequency period after all other BY filters.
/// Positive positions count from one; negative positions count backwards.
fn apply_setpos(
  candidates : Array[@time.PlainDate],
  positions : Array[Int32],
) -> Array[@time.PlainDate] {
  if positions.length() == 0 {
    return candidates
  }
  let out : Array[@time.PlainDate] = []
  for position in positions {
    let index = if position > 0 {
      position - 1
    } else {
      candidates.length() + position
    }
    if index >= 0 &&
      index < candidates.length() &&
      !out.contains(candidates[index]) {
      out.push(candidates[index])
    }
  }
  out.sort_by((a, b) => Compare::compare(a, b))
  out
}

///|
/// `DAILY`: one date per period, the interval step from `DTSTART`, kept
/// only if it survives every present `BY*` filter. `None` when the step
/// leaves the representable calendar.
fn daily_candidates(
  normalized : NormalizedRule,
  start : @time.PlainDate,
  period : Int32,
) -> Array[@time.PlainDate]? {
  // Int64 on purpose: period * interval can exceed Int32 for the huge
  // INTERVAL values parse_rule admits, and a wrapped product can land on
  // a *valid* date — the wrong occurrence, silently.
  let step = period.to_int64() * normalized.rule.interval.to_int64()
  let day : @time.PlainDate? = Some(start.add_days(step)) catch { _ => None }
  match day {
    None => None
    Some(day) =>
      if passes_filters(normalized, day) {
        Some([day])
      } else {
        Some([])
      }
  }
}

///|
/// `WEEKLY`: the seven days of the `WKST`-aligned week that is
/// `period * interval` weeks from `DTSTART`'s week, filtered to the
/// `BYDAY` weekdays — or, with no `BYDAY`, to `DTSTART`'s own weekday.
/// `WKST` decides which week a date belongs to, which is why it changes
/// the result near a week boundary. `None` past the representable
/// calendar.
fn weekly_candidates(
  normalized : NormalizedRule,
  start : @time.PlainDate,
  period : Int32,
) -> Array[@time.PlainDate]? raise {
  let rule = normalized.rule
  let into_week = (weekday_num(start.weekday()) - weekday_num(rule.wkst) + 7) %
    7
  let week0 = start.add_days(-into_week.to_int64())
  let step = period.to_int64() * rule.interval.to_int64() * 7
  let base : @time.PlainDate? = Some(week0.add_days(step)) catch { _ => None }
  match base {
    None => None
    Some(base) => {
      let out : Array[@time.PlainDate] = []
      for i in 0..<7 {
        // `base` is a valid date, but the week it opens can run past the
        // representable calendar: with base in year 9999's final week the
        // later days of that week do not exist. S12 guarded the step to
        // `base` but not the days within the week, so the walk escaped as
        // x/time's untyped Failure; a day past the horizon ends this week
        // (everything after it is further out) rather than failing it.
        let day : @time.PlainDate? = Some(base.add_days(i.to_int64())) catch {
          _ => None
        }
        match day {
          None => break
          Some(day) => {
            let wanted = if rule.byday.length() > 0 {
              weekday_selected(rule.byday, day.weekday())
            } else {
              day.weekday() == start.weekday()
            }
            if wanted && passes_filters(normalized, day) {
              out.push(day)
            }
          }
        }
      }
      Some(out)
    }
  }
}

///|
/// `MONTHLY`: the month `period * interval` months on. Within it, the
/// `BYMONTHDAY` days and the `BYDAY` weekdays combine — both present
/// means dates matching both, either alone means its own dates, and
/// neither falls back to `DTSTART`'s day-of-month (skipped in months too
/// short for it). `BYMONTH` drops the whole month when it does not
/// match. Days missing from the calendar (February 30) are skipped, not
/// clamped: RFC 5545 has no such date to emit.
fn monthly_candidates(
  normalized : NormalizedRule,
  start : @time.PlainDate,
  period : Int32,
) -> Array[@time.PlainDate]? raise {
  let rule = normalized.rule
  // Int64 arithmetic: period * interval overflows Int32 for the huge
  // INTERVAL values parse_rule admits, and a wrapped month count would
  // realize a wrong-but-valid year.
  let months = start.year().to_int64() * 12 +
    (start.month() - 1).to_int64() +
    period.to_int64() * rule.interval.to_int64()
  let year = months / 12
  if year > MAX_PLAIN_YEAR {
    return None
  }
  let year = Int64::to_int(year)
  let month = Int64::to_int(months % 12 + 1)
  if rule.bymonth.length() > 0 && !int_selected(rule.bymonth, month) {
    return Some([])
  }
  let days = month_days(normalized, start, year, month)
  let out : Array[@time.PlainDate] = []
  for day in days {
    out.push(@time.PlainDate::of(year, month, day))
  }
  Some(out)
}

///|
/// `YEARLY`: the year `period * interval` years on. With `BYMONTH`, the
/// ordinal `BYDAY` counts within each specified month (RFC 5545 §3.3.10).
/// Without `BYMONTH`, an ordinal `BYDAY` counts within the *year* — the
/// "Nth Monday of the year" reading the RFC's own `20MO` example fixes —
/// so the whole year is scanned and `BYMONTHDAY` only *limits* it (plain
/// `BYDAY` entries stay weekday filters). With neither, the same day
/// selection as `MONTHLY` applies per month, so the `DTSTART` fallback
/// yields the anniversary date.
fn yearly_candidates(
  normalized : NormalizedRule,
  start : @time.PlainDate,
  period : Int32,
) -> Array[@time.PlainDate]? raise {
  let rule = normalized.rule
  let year = start.year().to_int64() +
    period.to_int64() * rule.interval.to_int64()
  if year > MAX_PLAIN_YEAR {
    return None
  }
  let year = Int64::to_int(year)
  if rule.bymonth.length() == 0 && has_ordinal_byday(rule.byday) {
    let out : Array[@time.PlainDate] = []
    for month in 1..<=12 {
      let dim = @time.PlainDate::of(year, month, 1).days_in_month()
      for day in 1..<=dim {
        let date = @time.PlainDate::of(year, month, day)
        if weekday_selected_in_year(rule.byday, date) &&
          (
            rule.bymonthday.length() == 0 ||
            int_selected(normalized.monthdays_by_length[dim - 28], day)
          ) {
          out.push(date)
        }
      }
    }
    return Some(out)
  }
  let months : Array[Int32] = []
  if rule.bymonth.length() > 0 {
    for month in rule.bymonth {
      months.push(month)
    }
  } else if rule.byday.length() > 0 || rule.bymonthday.length() > 0 {
    for month in 1..<=12 {
      months.push(month)
    }
  } else {
    months.push(start.month())
  }
  let out : Array[@time.PlainDate] = []
  for month in months {
    for day in month_days(normalized, start, year, month) {
      out.push(@time.PlainDate::of(year, month, day))
    }
  }
  Some(out)
}

///|
/// The day numbers of one month under this rule: `BYMONTHDAY` ∩ `BYDAY`
/// when both are present, either alone, or `DTSTART`'s day as the
/// fallback. Ascending, and never a day the calendar lacks.
fn month_days(
  normalized : NormalizedRule,
  start : @time.PlainDate,
  year : Int32,
  month : Int32,
) -> Array[Int32] raise {
  let rule = normalized.rule
  let dim = @time.PlainDate::of(year, month, 1).days_in_month()
  let out : Array[Int32] = []
  if rule.bymonthday.length() > 0 {
    for day in normalized.monthdays_by_length[dim - 28] {
      let weekday = @time.PlainDate::of(year, month, day).weekday()
      if rule.byday.length() == 0 ||
        weekday_selected_in_month(rule.byday, year, month, day, weekday) {
        out.push(day)
      }
    }
  } else if rule.byday.length() > 0 {
    for day in 1..<=dim {
      let weekday = @time.PlainDate::of(year, month, day).weekday()
      if weekday_selected_in_month(rule.byday, year, month, day, weekday) {
        out.push(day)
      }
    }
  } else if start.day() <= dim {
    out.push(start.day())
  }
  out
}

///|
/// Whether a `DAILY`/`WEEKLY` candidate survives every present `BY*`
/// filter. Frequencies below monthly cannot generate from `BYMONTHDAY`,
/// so it limits here instead — and a negative `BYMONTHDAY` counts from the
/// end of the candidate's *own* month, so the test runs against the same
/// realized day numbers [`month_days`] generates from, never the raw
/// negative clause (which can never equal a 1..31 day number).
fn passes_filters(normalized : NormalizedRule, day : @time.PlainDate) -> Bool {
  let rule = normalized.rule
  if rule.bymonth.length() > 0 && !int_selected(rule.bymonth, day.month()) {
    return false
  }
  if rule.bymonthday.length() > 0 {
    let dim = day.days_in_month()
    if !int_selected(normalized.monthdays_by_length[dim - 28], day.day()) {
      return false
    }
  }
  if rule.byday.length() > 0 && !weekday_selected(rule.byday, day.weekday()) {
    return false
  }
  true
}

///|
/// Monday as 0 through Sunday as 6 — the arithmetic week-position of a
/// weekday, whatever spelling it came in as.
fn weekday_num(weekday : @time.Weekday) -> Int32 {
  match weekday {
    @time.Weekday::Monday => 0
    @time.Weekday::Tuesday => 1
    @time.Weekday::Wednesday => 2
    @time.Weekday::Thursday => 3
    @time.Weekday::Friday => 4
    @time.Weekday::Saturday => 5
    @time.Weekday::Sunday => 6
  }
}

///|
/// Whether one of the plain `BYDAY` entries names this weekday.
fn weekday_selected(entries : Array[Byday], weekday : @time.Weekday) -> Bool {
  for entry in entries {
    if entry.ordinal == 0 && entry.weekday == weekday {
      return true
    }
  }
  false
}

///|
fn weekday_selected_in_month(
  entries : Array[Byday],
  year : Int32,
  month : Int32,
  day : Int32,
  weekday : @time.Weekday,
) -> Bool raise {
  let dim = @time.PlainDate::of(year, month, 1).days_in_month()
  for entry in entries {
    if entry.weekday == weekday {
      if entry.ordinal == 0 {
        return true
      }
      let ordinal = if entry.ordinal > 0 {
        (day - 1) / 7 + 1
      } else {
        -((dim - day) / 7 + 1)
      }
      if ordinal == entry.ordinal {
        return true
      }
    }
  }
  false
}

///|
fn weekday_selected_in_year(
  entries : Array[Byday],
  date : @time.PlainDate,
) -> Bool raise {
  for entry in entries {
    if entry.weekday == date.weekday() {
      if entry.ordinal == 0 {
        return true
      }
      let jan1 = @time.PlainDate::of(date.year(), 1, 1)
      let dec31 = @time.PlainDate::of(date.year(), 12, 31)
      let ordinal = if entry.ordinal > 0 {
        (date.to_unix_day() - jan1.to_unix_day()).to_int() / 7 + 1
      } else {
        -((dec31.to_unix_day() - date.to_unix_day()).to_int() / 7 + 1)
      }
      if ordinal == entry.ordinal {
        return true
      }
    }
  }
  false
}

///|
fn has_ordinal_byday(entries : Array[Byday]) -> Bool {
  for entry in entries {
    if entry.ordinal != 0 {
      return true
    }
  }
  false
}

///|
/// Whether a normalized, ascending clause list contains the value.
fn int_selected(list : Array[Int32], value : Int32) -> Bool {
  list.binary_search(value) is Ok(_)
}

///|
/// The calendar date of a wall-clock value.
fn plain_date_of(wall : @time.PlainDateTime) -> @time.PlainDate raise {
  @time.PlainDate::of(wall.year(), wall.month(), wall.day())
}

///|
/// Whether the rule can never produce a single occurrence by construction.
///
/// Two proofs, tried in order:
///
/// 1. Shape-disjoint (definitive, requires BYMONTHDAY): a month is fully
///    determined by its length (28/29/30/31) and its start weekday (seven
///    values), and every (length, start) combination occurs across the
///    Gregorian cycle. If no day in the BYMONTHDAY realization matches any
///    BYDAY entry under any start, the series is empty by construction —
///    regardless of what the other BY clauses do.
///
/// 2. All-ordinal bound (for BYMONTHDAY-less rules, where proof 1 is
///    vacuous): every BYDAY entry is an ordinal past the scoped bound — a
///    month holds at most five of any weekday, a year at most 53.
///
/// Ending the expansion here (instead of walking MAX_PERIODS empty
/// periods) keeps a never-matching rule from surfacing as a budget error
/// — which, over CalDAV, let one stored resource fail every REPORT over
/// its collection, and blocked the single-threaded event loop for the
/// whole walk on a PUT-door validation.
fn provably_empty(
  rule : Rule,
  normalized : NormalizedRule,
  month : Int32,
) -> Bool {
  let entries = rule.byday
  if entries.length() == 0 {
    return false
  }
  if rule.bymonthday.length() > 0 {
    // MONTHLY walks every civil month, so all four lengths are in play.
    // YEARLY with BYMONTH walks only the named months; YEARLY without
    // BYMONTH walks DTSTART's own month (its length is fixed across the
    // anniversary scan).
    // MONTHLY/DAILY/WEEKLY walk every civil month: all four lengths are in
    // play. YEARLY with BYMONTH walks only the named months; YEARLY without
    // BYMONTH walks DTSTART's own month (its length is fixed across the
    // anniversary scan).
    let lengths = match rule.freq {
      Yearly => {
        let all = []
        if rule.bymonth.length() > 0 {
          for m in rule.bymonth {
            for length in month_lengths(m) {
              all.push(length)
            }
          }
        } else {
          for length in month_lengths(month) {
            all.push(length)
          }
        }
        all
      }
      _ => [31, 30, 29, 28]
    }
    return lengths_unsatisfiable(rule, normalized, lengths)
  }
  let mut all_ordinal = true
  for entry in entries {
    if entry.ordinal == 0 {
      all_ordinal = false
    }
  }
  if all_ordinal {
    match rule.freq {
      Monthly => all_ordinals_beyond(entries, 5)
      Yearly =>
        if rule.bymonth.length() == 0 {
          all_ordinals_beyond(entries, 53)
        } else {
          all_ordinals_beyond(entries, 5)
        }
      _ => false
    }
  } else {
    false
  }
}

///|
/// Whether the BYMONTHDAY x BYDAY-ordinal intersection is empty for a
/// month of `length` days starting on weekday `start` (0 = Monday). A
/// month's structure is fully determined by those two inputs, and every
/// (length, start) combination occurs across the Gregorian cycle, so
/// unsatisfiability over the 7 starts proves the rule can never match.
/// Requires BYMONTHDAY to be present (the caller routes BYMONTHDAY-less
/// rules to the ordinal-bound proof).
fn month_shape_unsatisfiable(
  rule : Rule,
  normalized : NormalizedRule,
  length : Int32,
  start : Int32,
) -> Bool {
  let days = normalized.monthdays_by_length[length - 28]
  if days.is_empty() {
    // e.g. BYMONTHDAY=31 against a 28-day February: that length cannot
    // realize any requested day, so this shape matches nothing.
    return true
  }
  if rule.byday.is_empty() {
    // No weekday constraint: every realized BYMONTHDAY day is reachable
    // under some start weekday, so this length is satisfiable.
    return false
  }
  for d in days {
    let weekday = (start + d - 1) % 7
    for entry in rule.byday {
      if weekday_num(entry.weekday) == weekday {
        if entry.ordinal == 0 {
          return false
        }
        let ord = if entry.ordinal > 0 {
          (d - 1) / 7 + 1
        } else {
          -((length - d) / 7 + 1)
        }
        if ord == entry.ordinal {
          return false
        }
      }
    }
  }
  true
}

///|
/// Unsatisfiable for every month length in `lengths` and every month-start
/// weekday — the exhaustive enumeration behind the shape-disjoint proof.
fn lengths_unsatisfiable(
  rule : Rule,
  normalized : NormalizedRule,
  lengths : Array[Int32],
) -> Bool {
  for length in lengths {
    for start in 0..<7 {
      if !month_shape_unsatisfiable(rule, normalized, length, start) {
        return false
      }
    }
  }
  true
}

///|
fn all_ordinals_beyond(entries : Array[Byday], bound : Int32) -> Bool {
  for entry in entries {
    if entry.ordinal <= bound && entry.ordinal >= -bound {
      return false
    }
  }
  true
}

///|
/// The lengths a civil month can have. February is the only variable one
/// (28 common, 29 leap); every other month is fixed, and its start
/// weekday cycles through all seven values across the Gregorian cycle.
fn month_lengths(month : Int32) -> Array[Int32] {
  if month == 2 {
    [28, 29]
  } else if month == 4 || month == 6 || month == 9 || month == 11 {
    [30]
  } else {
    [31]
  }
}