rustev_core/ranking/
mod.rs

1//! Pure ranking building blocks (spec 039); not wired into compilation or evaluation.
2pub mod permute;
3pub mod schedules;
4pub mod select;
5pub mod value;
6
7use rustev_contract::ranking::{Bias, PairwiseSchedule, RankMode};
8
9/// Invalid controls or a bound that cannot be represented.
10#[derive(Debug, Clone, Copy, PartialEq, Eq)]
11pub enum BoundError {
12    InvalidBias,
13    Overflow,
14}
15
16/// Worst-case logical pairs before presentation multiplication (039, 3.7.5).
17/// This is independent of the execution cap, which compilation must compare
18/// against the presentation count returned by `max_requests`.
19pub fn pairwise_bound(n: u64, schedule: PairwiseSchedule) -> Result<u64, BoundError> {
20    let count = match schedule {
21        PairwiseSchedule::RoundRobin => u128::from(n) * u128::from(n.saturating_sub(1)) / 2,
22        PairwiseSchedule::MergeSort => {
23            // At each width, full merges cost 2*width-1. A trailing run
24            // contributes only when it has a nonempty right side.
25            let n = u128::from(n);
26            let mut width = 1u128;
27            let mut total = 0u128;
28            while width < n {
29                let span = width * 2;
30                let remainder = n % span;
31                total += (n / span) * (span - 1);
32                if remainder > width {
33                    total += remainder - 1;
34                }
35                width = span;
36            }
37            total
38        }
39    };
40    // u64 inputs require at most 64 levels; intermediates fit in u128.
41    u64::try_from(count).map_err(|_| BoundError::Overflow)
42}
43
44/// Declared request bound (039, 3.5.4, 3.6.3, 3.7.5), not actual requests.
45/// In particular listwise's declared bound is orders even for a zero pool
46/// bound; request planning must suppress requests for an empty actual pool.
47pub fn max_requests(n: u64, mode: &RankMode, bias: &Bias) -> Result<u64, BoundError> {
48    let orders = match bias {
49        Bias::None | Bias::Shuffle { .. } => 1,
50        Bias::PermutationAverage { orders, .. } if (2..=8).contains(orders) => *orders,
51        Bias::PermutationAverage { .. } => return Err(BoundError::InvalidBias),
52    };
53    match mode {
54        RankMode::Listwise { .. } => Ok(orders),
55        RankMode::Pointwise if *bias == Bias::None => Ok(n),
56        RankMode::Pointwise => Err(BoundError::InvalidBias),
57        RankMode::Pairwise { schedule, .. } => {
58            if orders > 2 {
59                return Err(BoundError::InvalidBias);
60            }
61            pairwise_bound(n, *schedule)?
62                .checked_mul(orders)
63                .ok_or(BoundError::Overflow)
64        }
65    }
66}
rustev_core/ranking/mod.rs

rustev_core/ranking/
mod.rs
