///|
/// Bounds and safety limits for a recurrence expansion request.
pub struct ExpansionOptions {
  window_start : DateTime
  window_end : DateTime
  limit : Int
  iteration_limit : Int
} derive(Eq, Debug)

///|
pub fn ExpansionOptions::new(
  window_start : DateTime,
  window_end : DateTime,
  limit? : Int = 100,
  iteration_limit? : Int = 200000,
) -> ExpansionOptions {
  { window_start, window_end, limit, iteration_limit }
}

///|
pub suberror ExpansionError {
  InvalidRule(Array[Diagnostic])
  InvalidWindow
  InvalidLimit(Int)
  IterationLimitExceeded(Int)
} derive(Debug)

///|
fn datetime_less(left : DateTime, right : DateTime) -> Bool {
  left.to_epoch_second() < right.to_epoch_second()
}

///|
fn datetime_less_or_equal(left : DateTime, right : DateTime) -> Bool {
  left.to_epoch_second() <= right.to_epoch_second()
}

///|
fn datetime_in_window(value : DateTime, options : ExpansionOptions) -> Bool {
  datetime_less_or_equal(options.window_start, value) &&
  datetime_less(value, options.window_end)
}

///|
fn weekday_distance(start : Weekday, target : Weekday) -> Int {
  (target.iso_number() - start.iso_number() + 7) % 7
}

///|
fn start_of_week(date : Date, week_start : Weekday) -> Date {
  date.add_days(-weekday_distance(week_start, date.weekday()))
}

///|
fn positive_month_day(year : Int, month : Int, value : Int) -> Int? {
  let limit = days_in_month(year, month)
  let day = if value > 0 { value } else { limit + value + 1 }
  if day >= 1 && day <= limit {
    Some(day)
  } else {
    None
  }
}

///|
fn positive_year_day(year : Int, value : Int) -> Int? {
  let limit = if is_leap_year(year) { 366 } else { 365 }
  let day = if value > 0 { value } else { limit + value + 1 }
  if day >= 1 && day <= limit {
    Some(day)
  } else {
    None
  }
}

///|
fn weekday_ordinal_in_month(date : Date) -> Int {
  (date.day - 1) / 7 + 1
}

///|
fn reverse_weekday_ordinal_in_month(date : Date) -> Int {
  -((days_in_month(date.year, date.month) - date.day) / 7 + 1)
}

///|
fn matches_byday(
  date : Date,
  rules : Array[ByDay],
  frequency : Frequency,
) -> Bool {
  if rules.length() == 0 {
    return true
  }
  for item in rules {
    if item.weekday != date.weekday() {
      continue
    }
    match item.ordinal {
      None => return true
      Some(value) =>
        if frequency == Monthly {
          if value > 0 && weekday_ordinal_in_month(date) == value {
            return true
          }
          if value < 0 && reverse_weekday_ordinal_in_month(date) == value {
            return true
          }
        } else if frequency == Yearly {
          if value > 0 {
            let ordinal = (date.day_of_year() - 1) / 7 + 1
            if ordinal == value {
              return true
            }
          } else {
            let total = if is_leap_year(date.year) { 366 } else { 365 }
            let ordinal = -((total - date.day_of_year()) / 7 + 1)
            if ordinal == value {
              return true
            }
          }
        }
    }
  }
  false
}

///|
fn matches_month_day(date : Date, values : Array[Int]) -> Bool {
  if values.length() == 0 {
    return true
  }
  for value in values {
    match positive_month_day(date.year, date.month, value) {
      Some(day) if day == date.day => return true
      _ => ()
    }
  }
  false
}

///|
fn matches_year_day(date : Date, values : Array[Int]) -> Bool {
  if values.length() == 0 {
    return true
  }
  for value in values {
    match positive_year_day(date.year, value) {
      Some(day) if day == date.day_of_year() => return true
      _ => ()
    }
  }
  false
}

///|
fn iso_week_number(date : Date) -> Int {
  let thursday = date.add_days(4 - date.weekday().iso_number())
  let first = Date::new(thursday.year, 1, 4) catch {
    _ => abort("valid ISO week anchor")
  }
  let first_thursday = first.add_days(4 - first.weekday().iso_number())
  (thursday.to_epoch_day() - first_thursday.to_epoch_day()) / 7 + 1
}

///|
fn iso_weeks_in_year(year : Int) -> Int {
  let date = Date::new(year, 12, 28) catch { _ => abort("valid ISO week date") }
  iso_week_number(date)
}

///|
fn matches_week_number(date : Date, values : Array[Int]) -> Bool {
  if values.length() == 0 {
    return true
  }
  let week = iso_week_number(date)
  let total = iso_weeks_in_year(date.year)
  for value in values {
    let normalized = if value > 0 { value } else { total + value + 1 }
    if normalized == week {
      return true
    }
  }
  false
}

///|
fn date_matches_filters(date : Date, rule : RRule) -> Bool {
  if rule.by_month.length() > 0 && !rule.by_month.contains(date.month) {
    return false
  }
  if !matches_month_day(date, rule.by_month_day) {
    return false
  }
  if !matches_year_day(date, rule.by_year_day) {
    return false
  }
  if !matches_week_number(date, rule.by_week_number) {
    return false
  }
  if !matches_byday(date, rule.by_day, rule.frequency) {
    return false
  }
  true
}

///|
fn effective_hours(rule : RRule, start : DateTime) -> Array[Int] {
  if rule.by_hour.length() > 0 {
    rule.by_hour
  } else {
    [start.time.hour]
  }
}

///|
fn effective_minutes(rule : RRule, start : DateTime) -> Array[Int] {
  if rule.by_minute.length() > 0 {
    rule.by_minute
  } else {
    [start.time.minute]
  }
}

///|
fn effective_seconds(rule : RRule, start : DateTime) -> Array[Int] {
  if rule.by_second.length() > 0 {
    rule.by_second
  } else {
    [start.time.second]
  }
}

///|
fn times_for_date(
  date : Date,
  start : DateTime,
  rule : RRule,
) -> Array[DateTime] {
  let result : Array[DateTime] = []
  for hour in effective_hours(rule, start) {
    for minute in effective_minutes(rule, start) {
      for second in effective_seconds(rule, start) {
        if hour >= 0 &&
          hour <= 23 &&
          minute >= 0 &&
          minute <= 59 &&
          second >= 0 &&
          second <= 59 {
          result.push({ date, time: { hour, minute, second } })
        }
      }
    }
  }
  result.sort()
  result
}

///|
fn apply_set_positions(
  values : Array[DateTime],
  positions : Array[Int],
) -> Array[DateTime] {
  if positions.length() == 0 {
    return values
  }
  let result : Array[DateTime] = []
  for position in positions {
    let index = if position > 0 {
      position - 1
    } else {
      values.length() + position
    }
    if index >= 0 && index < values.length() {
      let item = values[index]
      if !result.contains(item) {
        result.push(item)
      }
    }
  }
  result.sort()
  result
}

///|
fn daily_bucket(anchor : DateTime, rule : RRule) -> Array[DateTime] {
  if !date_matches_filters(anchor.date, rule) {
    return []
  }
  apply_set_positions(
    times_for_date(anchor.date, anchor, rule),
    rule.by_set_position,
  )
}

///|
fn weekly_bucket(
  anchor : DateTime,
  start : DateTime,
  rule : RRule,
) -> Array[DateTime] {
  let week = start_of_week(anchor.date, rule.week_start)
  let weekdays = if rule.by_day.length() > 0 {
    rule.by_day.map(value => value.weekday)
  } else {
    [start.date.weekday()]
  }
  let result : Array[DateTime] = []
  for weekday in weekdays {
    let date = week.add_days(weekday_distance(rule.week_start, weekday))
    if date_matches_filters(date, rule) {
      for item in times_for_date(date, start, rule) {
        result.push(item)
      }
    }
  }
  result.sort()
  apply_set_positions(result, rule.by_set_position)
}

///|
fn monthly_bucket(
  anchor : DateTime,
  start : DateTime,
  rule : RRule,
) -> Array[DateTime] {
  let result : Array[DateTime] = []
  let limit = days_in_month(anchor.date.year, anchor.date.month)
  for day = 1; day <= limit; day = day + 1 {
    let date = Date::new(anchor.date.year, anchor.date.month, day) catch {
      _ => continue
    }
    let default_day = rule.by_month_day.length() == 0 &&
      rule.by_day.length() == 0
    if default_day && day != start.date.day {
      continue
    }
    if date_matches_filters(date, rule) {
      for item in times_for_date(date, start, rule) {
        result.push(item)
      }
    }
  }
  result.sort()
  apply_set_positions(result, rule.by_set_position)
}

///|
fn yearly_bucket(
  anchor : DateTime,
  start : DateTime,
  rule : RRule,
) -> Array[DateTime] {
  let result : Array[DateTime] = []
  let year = anchor.date.year
  let days = if is_leap_year(year) { 366 } else { 365 }
  let first = Date::new(year, 1, 1) catch { _ => abort("valid year") }
  for offset = 0; offset < days; offset = offset + 1 {
    let date = first.add_days(offset)
    let no_date_filter = rule.by_month.length() == 0 &&
      rule.by_month_day.length() == 0 &&
      rule.by_year_day.length() == 0 &&
      rule.by_week_number.length() == 0 &&
      rule.by_day.length() == 0
    if no_date_filter &&
      (date.month != start.date.month || date.day != start.date.day) {
      continue
    }
    if date_matches_filters(date, rule) {
      for item in times_for_date(date, start, rule) {
        result.push(item)
      }
    }
  }
  result.sort()
  apply_set_positions(result, rule.by_set_position)
}

///|
fn next_anchor(anchor : DateTime, rule : RRule) -> DateTime {
  match rule.frequency {
    Secondly => anchor.add_seconds(rule.interval.to_int64())
    Minutely => anchor.add_seconds(rule.interval.to_int64() * 60L)
    Hourly => anchor.add_seconds(rule.interval.to_int64() * 3600L)
    Daily => anchor.add_days(rule.interval)
    Weekly => anchor.add_days(rule.interval * 7)
    Monthly => anchor.add_months(rule.interval)
    Yearly => anchor.add_years(rule.interval)
  }
}

///|
fn bucket_for(
  anchor : DateTime,
  start : DateTime,
  rule : RRule,
) -> Array[DateTime] {
  match rule.frequency {
    Secondly =>
      if date_matches_filters(anchor.date, rule) {
        [anchor]
      } else {
        []
      }
    Minutely =>
      if date_matches_filters(anchor.date, rule) &&
        (
          rule.by_minute.length() == 0 ||
          rule.by_minute.contains(anchor.time.minute)
        ) &&
        (
          rule.by_second.length() == 0 ||
          rule.by_second.contains(anchor.time.second)
        ) {
        [anchor]
      } else {
        []
      }
    Hourly =>
      if date_matches_filters(anchor.date, rule) &&
        (rule.by_hour.length() == 0 || rule.by_hour.contains(anchor.time.hour)) {
        [anchor]
      } else {
        []
      }
    Daily => daily_bucket(anchor, rule)
    Weekly => weekly_bucket(anchor, start, rule)
    Monthly => monthly_bucket(anchor, start, rule)
    Yearly => yearly_bucket(anchor, start, rule)
  }
}

///|
/// Expand a recurrence within a half-open time window [start, end).
pub fn expand_rrule(
  start : DateTime,
  rule : RRule,
  options : ExpansionOptions,
) -> Array[DateTime] raise ExpansionError {
  let diagnostics = rule.validate()
  for item in diagnostics {
    if item.severity == Error {
      raise InvalidRule(diagnostics)
    }
  }
  if !datetime_less(options.window_start, options.window_end) {
    raise InvalidWindow
  }
  if options.limit < 1 {
    raise InvalidLimit(options.limit)
  }
  let result : Array[DateTime] = []
  let mut anchor = start
  let mut generated = 0
  let mut iterations = 0
  while iterations < options.iteration_limit && result.length() < options.limit {
    iterations = iterations + 1
    let bucket = bucket_for(anchor, start, rule)
    for candidate in bucket {
      if datetime_less(candidate, start) {
        continue
      }
      match rule.until {
        Some(until) if datetime_less(until, candidate) => continue
        _ => ()
      }
      generated = generated + 1
      match rule.count {
        Some(count) if generated > count => break
        _ => ()
      }
      if datetime_in_window(candidate, options) && !result.contains(candidate) {
        result.push(candidate)
      }
    }
    match rule.count {
      Some(count) if generated >= count => break
      _ => ()
    }
    match rule.until {
      Some(until) if datetime_less(until, anchor) => break
      _ => ()
    }
    if !datetime_less(anchor, options.window_end) && rule.count is None {
      break
    }
    anchor = next_anchor(anchor, rule)
  }
  if iterations >= options.iteration_limit && result.length() < options.limit {
    raise IterationLimitExceeded(options.iteration_limit)
  }
  result.sort()
  result
}

///|
pub fn expand(
  start : DateTime,
  rule_source : String,
  window_start : DateTime,
  window_end : DateTime,
  limit? : Int = 100,
) -> Array[DateTime] raise {
  let rule = parse_rrule(rule_source)
  expand_rrule(
    start,
    rule,
    ExpansionOptions::new(window_start, window_end, limit~),
  )
}