use super::EpochScheduleError;
use crate::types::EpochNumber;
pub const SCHEDULE_ROWS: usize = 512;
pub const SCHEDULE_TIERS: usize = 10;
pub const TIER_ROWS: [u64; SCHEDULE_TIERS] = [128, 64, 64, 64, 64, 32, 32, 32, 16, 16];
pub const SCHEDULE_MIN_REACH: u64 = 20_993;
const LAST_TIER: usize = SCHEDULE_TIERS - 1;
const TIER_SLOTS: [usize; SCHEDULE_TIERS] = tier_slots();
const fn tier_slots() -> [usize; SCHEDULE_TIERS] {
let mut slots = [0; SCHEDULE_TIERS];
let mut next = 0;
let mut tier = 0;
while tier < SCHEDULE_TIERS {
slots[tier] = next;
next += TIER_ROWS[tier] as usize;
tier += 1;
}
assert!(next == SCHEDULE_ROWS);
slots
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct ScheduleRow {
pub start: EpochNumber,
pub end: EpochNumber,
slot: usize,
}
impl ScheduleRow {
#[inline]
pub fn slot(&self) -> usize {
self.slot
}
#[inline]
pub fn width(&self) -> u64 {
(self.end - self.start).as_u64()
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct ScheduleLayout {
now: EpochNumber,
ends: [EpochNumber; SCHEDULE_TIERS],
}
impl ScheduleLayout {
pub fn try_new(now: EpochNumber) -> Result<Self, EpochScheduleError> {
let mut ends = [now; SCHEDULE_TIERS];
let mut start = now.as_u64();
for (tier, end) in ends.iter_mut().enumerate() {
let width = row_width(tier);
let reach = if tier == LAST_TIER {
start.checked_add(TIER_ROWS[tier] * width)
} else {
start
.checked_add((TIER_ROWS[tier] - 1) * width)
.and_then(|reach| reach.checked_next_multiple_of(2 * width))
};
start = reach.ok_or(EpochScheduleError::Overflow)?;
*end = EpochNumber(start);
}
Ok(Self { now, ends })
}
#[inline]
pub fn start(&self) -> EpochNumber {
self.now
}
#[inline]
pub fn end(&self) -> EpochNumber {
self.ends[LAST_TIER]
}
pub fn row_at(&self, epoch: EpochNumber) -> Result<ScheduleRow, EpochScheduleError> {
if epoch < self.now {
return Err(EpochScheduleError::EpochInPast);
}
for (tier, end) in self.ends.iter().enumerate() {
if epoch < *end {
let width = row_width(tier);
let start = EpochNumber(epoch.as_u64() / width * width);
return Ok(row(tier, start));
}
}
Err(EpochScheduleError::EpochTooFar)
}
pub fn is_boundary(&self, epoch: EpochNumber) -> bool {
self.boundary_at_or_after(epoch) == Some(epoch)
}
pub fn boundary_at_or_after(&self, epoch: EpochNumber) -> Option<EpochNumber> {
let epoch = epoch.max(self.now);
for (tier, end) in self.ends.iter().enumerate() {
if epoch < *end {
let boundary = epoch.as_u64().checked_next_multiple_of(row_width(tier))?;
return Some(EpochNumber(boundary));
}
}
(epoch == self.end()).then_some(epoch)
}
pub fn boundary_at_or_before(&self, epoch: EpochNumber) -> EpochNumber {
match self.row_at(epoch.max(self.now)) {
Ok(row) => row.start,
Err(_) => self.end(),
}
}
pub fn latest_expiry(&self, max_epochs: u64) -> EpochNumber {
let reach = self.now.saturating_add(EpochNumber(max_epochs));
self.boundary_at_or_before(reach)
}
pub fn expiry_for(&self, requested: EpochNumber, max_epochs: u64) -> EpochNumber {
let latest = self.latest_expiry(max_epochs);
match self.boundary_at_or_after(requested) {
Some(boundary) => boundary.min(latest),
None => latest,
}
}
pub fn rows(
&self,
start: EpochNumber,
end: EpochNumber,
) -> Result<ScheduleRows, EpochScheduleError> {
if start < self.now {
return Err(EpochScheduleError::EpochInPast);
}
if end <= start {
return Err(EpochScheduleError::EndNotAfterStart);
}
if end > self.end() {
return Err(EpochScheduleError::EpochTooFar);
}
if !self.is_boundary(start) || !self.is_boundary(end) {
return Err(EpochScheduleError::MidRow);
}
Ok(ScheduleRows { layout: *self, tier: 0, next: start, end })
}
pub fn all_rows(&self) -> ScheduleRows {
ScheduleRows { layout: *self, tier: 0, next: self.now, end: self.end() }
}
pub fn splits(&self, next: &ScheduleLayout) -> ScheduleSplits {
ScheduleSplits { old: *self, new: *next, tier: 0 }
}
}
#[derive(Clone, Copy, Debug)]
pub struct ScheduleRows {
layout: ScheduleLayout,
tier: usize,
next: EpochNumber,
end: EpochNumber,
}
impl Iterator for ScheduleRows {
type Item = ScheduleRow;
fn next(&mut self) -> Option<ScheduleRow> {
if self.next >= self.end {
return None;
}
while self.tier < LAST_TIER && self.next >= self.layout.ends[self.tier] {
self.tier += 1;
}
let found = row(self.tier, self.next);
self.next = found.end;
Some(found)
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct ScheduleSplit {
pub parent: ScheduleRow,
pub children: [ScheduleRow; 2],
}
#[derive(Clone, Copy, Debug)]
pub struct ScheduleSplits {
old: ScheduleLayout,
new: ScheduleLayout,
tier: usize,
}
impl Iterator for ScheduleSplits {
type Item = ScheduleSplit;
fn next(&mut self) -> Option<ScheduleSplit> {
if self.tier >= LAST_TIER || self.new.ends[self.tier] == self.old.ends[self.tier] {
return None;
}
let start = self.old.ends[self.tier];
let first = row(self.tier, start);
let second = row(self.tier, first.end);
let parent = row(self.tier + 1, start);
self.tier += 1;
Some(ScheduleSplit { parent, children: [first, second] })
}
}
#[inline]
fn row_width(tier: usize) -> u64 {
1 << tier
}
fn row(tier: usize, start: EpochNumber) -> ScheduleRow {
let width = row_width(tier);
let index = (start.as_u64() / width) % TIER_ROWS[tier];
ScheduleRow {
start,
end: EpochNumber(start.as_u64().saturating_add(width)),
slot: TIER_SLOTS[tier] + index as usize,
}
}
#[cfg(test)]
mod tests {
use std::collections::HashSet;
use super::*;
const SCHEDULE_MAX_REACH: u64 = 21_504;
fn layout(now: u64) -> ScheduleLayout {
ScheduleLayout::try_new(EpochNumber(now)).expect("layout")
}
fn tier_start(layout: &ScheduleLayout, tier: usize) -> u64 {
match tier {
0 => layout.now.as_u64(),
_ => layout.ends[tier - 1].as_u64(),
}
}
#[test]
fn every_phase() {
for now in 0..2 * SCHEDULE_ROWS as u64 {
let layout = layout(now);
for tier in 0..SCHEDULE_TIERS {
let width = row_width(tier);
let start = tier_start(&layout, tier);
let rows = (layout.ends[tier].as_u64() - start) / width;
assert_eq!(start % width, 0);
assert!(rows == TIER_ROWS[tier] || rows + 1 == TIER_ROWS[tier]);
}
assert_eq!(
(layout.ends[LAST_TIER].as_u64() - tier_start(&layout, LAST_TIER)) / row_width(LAST_TIER),
TIER_ROWS[LAST_TIER],
);
let reach = (layout.end() - layout.start()).as_u64();
assert!((SCHEDULE_MIN_REACH..=SCHEDULE_MAX_REACH).contains(&reach));
}
}
#[test]
fn reach_bounds() {
let mut shortest = u64::MAX;
let mut longest = 0;
for now in 0..SCHEDULE_ROWS as u64 {
let layout = layout(now);
let reach = (layout.end() - layout.start()).as_u64();
shortest = shortest.min(reach);
longest = longest.max(reach);
}
assert_eq!(shortest, SCHEDULE_MIN_REACH);
assert_eq!(longest, SCHEDULE_MAX_REACH);
}
#[test]
fn rows_partition() {
for now in [0, 1, 127, 128, 511, 512, 1_000, 21_503, 21_504, 1 << 40] {
let layout = layout(now);
let mut slots = HashSet::new();
let mut next = layout.start();
for row in layout.all_rows() {
assert_eq!(row.start, next);
assert!(row.slot() < SCHEDULE_ROWS);
assert!(slots.insert(row.slot()));
next = row.end;
}
assert_eq!(next, layout.end());
assert!(slots.len() <= SCHEDULE_ROWS);
}
}
#[test]
fn boundaries_stay() {
let mut old = layout(0);
for now in 1..3_000 {
let new = layout(now);
for row in old.all_rows() {
assert!(row.start < new.start() || new.is_boundary(row.start));
}
assert!(new.is_boundary(old.end()));
old = new;
}
}
#[test]
fn splits_match() {
let mut old = layout(0);
for now in 1..3_000 {
let new = layout(now);
let mut expected: Vec<ScheduleRow> = old.all_rows().skip(1).collect();
for split in old.splits(&new) {
let at = expected
.iter()
.position(|row| *row == split.parent)
.expect("parent is a row");
expected.splice(at..=at, split.children);
}
if expected.last().map(|row| row.end) != Some(new.end()) {
expected.push(row(LAST_TIER, old.end()));
}
let rows: Vec<ScheduleRow> = new.all_rows().collect();
assert_eq!(rows, expected);
old = new;
}
}
#[test]
fn rounding() {
let layout = layout(1_000);
assert_eq!(layout.boundary_at_or_after(EpochNumber(1_127)), Some(EpochNumber(1_127)));
assert_eq!(layout.boundary_at_or_after(EpochNumber(1_129)), Some(EpochNumber(1_130)));
assert_eq!(layout.boundary_at_or_before(EpochNumber(1_129)), EpochNumber(1_128));
assert_eq!(layout.boundary_at_or_after(EpochNumber(1_257)), Some(EpochNumber(1_260)));
assert_eq!(layout.boundary_at_or_before(EpochNumber(1_259)), EpochNumber(1_256));
assert_eq!(layout.boundary_at_or_after(EpochNumber(3)), Some(EpochNumber(1_000)));
assert_eq!(layout.boundary_at_or_before(EpochNumber(3)), EpochNumber(1_000));
assert_eq!(layout.boundary_at_or_after(layout.end()), Some(layout.end()));
assert_eq!(layout.boundary_at_or_after(layout.end().next()), None);
assert_eq!(layout.boundary_at_or_before(EpochNumber(u64::MAX)), layout.end());
assert!(layout.is_boundary(EpochNumber(1_128)));
assert!(!layout.is_boundary(EpochNumber(1_129)));
assert!(!layout.is_boundary(EpochNumber(999)));
}
#[test]
fn expiry() {
let layout = layout(1_000);
assert_eq!(layout.expiry_for(EpochNumber(1_050), u64::MAX), EpochNumber(1_050));
assert_eq!(layout.expiry_for(EpochNumber(1_129), u64::MAX), EpochNumber(1_130));
assert_eq!(layout.expiry_for(EpochNumber(u64::MAX), u64::MAX), layout.end());
assert_eq!(layout.latest_expiry(129), EpochNumber(1_128));
assert_eq!(layout.expiry_for(EpochNumber(1_129), 129), EpochNumber(1_128));
assert_eq!(layout.expiry_for(EpochNumber(5_000), 100), EpochNumber(1_100));
assert_eq!(layout.expiry_for(EpochNumber(1_050), 100), EpochNumber(1_050));
assert_eq!(layout.latest_expiry(0), EpochNumber(1_000));
}
#[test]
fn range_errors() {
let layout = layout(1_000);
let end = layout.end();
assert_eq!(
layout.rows(EpochNumber(999), EpochNumber(1_010)).err(),
Some(EpochScheduleError::EpochInPast),
);
assert_eq!(
layout.rows(EpochNumber(1_010), EpochNumber(1_010)).err(),
Some(EpochScheduleError::EndNotAfterStart),
);
assert_eq!(
layout.rows(EpochNumber(1_010), EpochNumber(end.as_u64() + 512)).err(),
Some(EpochScheduleError::EpochTooFar),
);
assert_eq!(
layout.rows(EpochNumber(1_010), EpochNumber(1_129)).err(),
Some(EpochScheduleError::MidRow),
);
assert_eq!(
layout.rows(EpochNumber(1_129), EpochNumber(1_256)).err(),
Some(EpochScheduleError::MidRow),
);
assert_eq!(
layout.rows(EpochNumber(1_000), end).map(|rows| rows.count()).ok(),
Some(layout.all_rows().count()),
);
}
#[test]
fn overflow() {
assert_eq!(
ScheduleLayout::try_new(EpochNumber(u64::MAX - 100)),
Err(EpochScheduleError::Overflow),
);
}
}