rustev-eval 0.4.0

//! Ranking measures (spec 041, 3.4.2 to 3.4.4 and 3.11).
//!
//! One case's contribution to each ranking metric, from the ranked list a
//! proposal carries and the case's gold relevance. Unjudged items are
//! removed from the top k (the condensed list) and counted, never read as
//! non-relevant; a short list is not padded; a case a metric cannot
//! measure is excluded with its reason, never scored 0 (I-2).
//!
//! Values use integer arithmetic, binary64 addition, multiplication and
//! division in the stated order, and the committed discount table, so they
//! are bit-identical on every target (I-4). Nothing here reads a clock or
//! performs I/O.

use std::collections::{BTreeMap, BTreeSet};

use rustev_contract::judgment::OutValue;
use rustev_contract::ranking_result::SelectionOrigin;
use serde::{Deserialize, Serialize};

use crate::eval_cases::CaseMeasure;

/// The largest cutoff a ranking metric declares (3.4.2).
pub const MAX_K: u64 = 100;

/// Exclusion reasons of 3.3 and 3.4, as the detail breakdown names them.
pub mod reason {
    pub const NO_GOLD: &str = "no_gold";
    pub const NOT_A_RANKING: &str = "not_a_ranking";
    pub const INVALID_RANKING: &str = "invalid_ranking";
    pub const NO_JUDGED_ITEMS: &str = "no_judged_items";
    pub const NO_RELEVANT: &str = "no_relevant";
    pub const NO_ORIGIN: &str = "no_origin";
    /// A list without position p is outside `backfill@p<p>`'s denominator.
    pub const NO_POSITION: &str = "no_position";
    /// Items, not cases: removed from a condensed list.
    pub const UNJUDGED_ITEMS: &str = "unjudged_items";
}

/// `D[i]` for i from 1 to 100: the binary64 value nearest to
/// `1 / log2(i + 1)`, as bit patterns. Generated by
/// `tests/data/metrics/discounts.py`; a test compares it with
/// `discounts.json` bit for bit (3.11.3).
const DISCOUNTS: [u64; 100] = [
    0x3ff0000000000000,
    0x3fe430939835353d,
    0x3fe0000000000000,
    0x3fdb903469050f73,
    0x3fd8c23246dc0a9f,
    0x3fd6cc193acea9b5,
    0x3fd5555555555555,
    0x3fd430939835353d,
    0x3fd34413509f79ff,
    0x3fd28009c1dd6454,
    0x3fd1da3383416064,
    0x3fd14b94f8d9641f,
    0x3fd0cf3ffed2d6ac,
    0x3fd0619dc46d3e15,
    0x3fd0000000000000,
    0x3fcf50b57eac5885,
    0x3fceb22cc68aa6e2,
    0x3fce21e1180c5dab,
    0x3fcd9dcd21439835,
    0x3fcd244c78367a0d,
    0x3fccb40589ac173e,
    0x3fcc4bd95ba8d72b,
    0x3fcbead76898f8ce,
    0x3fcb903469050f73,
    0x3fcb3b433f2eb06f,
    0x3fcaeb6f759c46fc,
    0x3fcaa038eb0e3bfd,
    0x3fca593062b38d8c,
    0x3fca15f4c32b95a3,
    0x3fc9d630dccc7ddf,
    0x3fc999999999999a,
    0x3fc95fec808a6094,
    0x3fc928ee7b0b4f23,
    0x3fc8f46acf8c06e3,
    0x3fc8c23246dc0a9f,
    0x3fc8921a744e1aed,
    0x3fc863fd1a4a3053,
    0x3fc837b7a642195e,
    0x3fc80d2abffdfee9,
    0x3fc7e439e8fed2b0,
    0x3fc7bccb2952736e,
    0x3fc796c6c7b22305,
    0x3fc772170b2747aa,
    0x3fc74ea804c2020f,
    0x3fc72c67602d3541,
    0x3fc70b443a1f7c88,
    0x3fc6eb2efbd2c1ad,
    0x3fc6cc193acea9b5,
    0x3fc6adf59c6e689d,
    0x3fc690b7bca1f15d,
    0x3fc67454177dda00,
    0x3fc658bff53d6bf2,
    0x3fc63df15867d0dd,
    0x3fc623deedd496ba,
    0x3fc60a7ffe55458a,
    0x3fc5f1cc61d1c5f0,
    0x3fc5d9bc73ac2288,
    0x3fc5c2490845f2f3,
    0x3fc5ab6b6386aaa4,
    0x3fc5951d3046396f,
    0x3fc57f587883063f,
    0x3fc56a179e4d652d,
    0x3fc5555555555555,
    0x3fc5410c9d09a12c,
    0x3fc52d38bb397b32,
    0x3fc519d5372b6ce4,
    0x3fc506ddd51defe7,
    0x3fc4f44e92275a60,
    0x3fc4e223a06beda9,
    0x3fc4d05963a1d8a7,
    0x3fc4beec6ddbe115,
    0x3fc4add97c942e46,
    0x3fc49d1d75f15f0e,
    0x3fc48cb56640af5f,
    0x3fc47c9e7da07ae1,
    0x3fc46cd60dd6e321,
    0x3fc45d598850cb5a,
    0x3fc44e267c45bba2,
    0x3fc43f3a94fd9227,
    0x3fc430939835353d,
    0x3fc4222f649fbc96,
    0x3fc4140bf081c4a8,
    0x3fc406274864d590,
    0x3fc3f87f8de0f744,
    0x3fc3eb12f67ab8e2,
    0x3fc3dddfca9417e7,
    0x3fc3d0e4646ed7c2,
    0x3fc3c41f2f3ef9fb,
    0x3fc3b78ea64c23f5,
    0x3fc3ab315420d981,
    0x3fc39f05d1c68ad2,
    0x3fc3930ac60d89e8,
    0x3fc3873ee4e00ec7,
    0x3fc37ba0ee9f8387,
    0x3fc3702faf8b610b,
    0x3fc364e9ff30f403,
    0x3fc359cebfe36ed6,
    0x3fc34edcde3bb953,
    0x3fc34413509f79ff,
    0x3fc3397116cededf,
];

/// The discount of condensed position `i`, 1 to 100.
pub fn discount(i: usize) -> f64 {
    f64::from_bits(DISCOUNTS[i - 1])
}

/// How a grade becomes a gain (3.4.3).
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum Gain {
    /// `g`.
    Linear,
    /// `2^g - 1`.
    Exponential,
}

impl Gain {
    /// An exact integer converted to binary64 for every grade 0 to 10
    /// (3.4.3). Total over `u8`: `2^g` is a power of two, exact in
    /// binary64 for any `u8`, so a grade outside 3.3.1's bound gives a
    /// finite gain, never a panic.
    pub fn of(self, grade: u8) -> f64 {
        match self {
            Gain::Linear => f64::from(grade),
            Gain::Exponential => 2f64.powi(i32::from(grade)) - 1.0,
        }
    }
}

/// A ranking metric specification (3.4.2): `precision@k`, `recall@k`,
/// `ndcg@k`, `hit@k`, `mrr` or `mrr@k`, with k from 1 to 100.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum RankingMetric {
    Precision(u64),
    Recall(u64),
    Ndcg(u64),
    Hit(u64),
    Mrr,
    MrrAt(u64),
}

impl RankingMetric {
    pub fn parse(s: &str) -> Option<RankingMetric> {
        if s == "mrr" {
            return Some(RankingMetric::Mrr);
        }
        let (name, k) = s.split_once('@')?;
        // Canonical digits only: no sign, no leading zero.
        if k.is_empty() || k.starts_with('0') || !k.bytes().all(|b| b.is_ascii_digit()) {
            return None;
        }
        let k: u64 = k.parse().ok()?;
        if !(1..=MAX_K).contains(&k) {
            return None;
        }
        Some(match name {
            "precision" => RankingMetric::Precision(k),
            "recall" => RankingMetric::Recall(k),
            "ndcg" => RankingMetric::Ndcg(k),
            "hit" => RankingMetric::Hit(k),
            "mrr" => RankingMetric::MrrAt(k),
            _ => return None,
        })
    }

    pub fn name(self) -> String {
        match self {
            RankingMetric::Precision(k) => format!("precision@{k}"),
            RankingMetric::Recall(k) => format!("recall@{k}"),
            RankingMetric::Ndcg(k) => format!("ndcg@{k}"),
            RankingMetric::Hit(k) => format!("hit@{k}"),
            RankingMetric::Mrr => "mrr".into(),
            RankingMetric::MrrAt(k) => format!("mrr@{k}"),
        }
    }

    /// The cutoff; none for `mrr`, which reads the whole list.
    pub fn k(self) -> Option<u64> {
        match self {
            RankingMetric::Precision(k)
            | RankingMetric::Recall(k)
            | RankingMetric::Ndcg(k)
            | RankingMetric::Hit(k)
            | RankingMetric::MrrAt(k) => Some(k),
            RankingMetric::Mrr => None,
        }
    }
}

impl Serialize for RankingMetric {
    fn serialize<S: serde::Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
        s.serialize_str(&self.name())
    }
}

impl<'de> Deserialize<'de> for RankingMetric {
    fn deserialize<D: serde::Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
        let s = String::deserialize(d)?;
        RankingMetric::parse(&s)
            .ok_or_else(|| serde::de::Error::custom("a ranking metric is precision@k, recall@k, ndcg@k, hit@k, mrr or mrr@k, k 1 to 100"))
    }
}

/// One entry of a ranked list: its id, and its origin when the list is a
/// `Selection` of spec 039.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Ranked {
    pub id: String,
    pub origin: Option<SelectionOrigin>,
}

/// A proposal's ranked list, in position order (3.4.2).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RankedList {
    pub entries: Vec<Ranked>,
    /// Whether the list records a per-position origin (a `Selection`).
    pub has_origin: bool,
}

/// The ranked list of a proposal parameter (3.4.2): a `Ranking`, a
/// `Shortlist` or a `Selection`. Any other value, or none, is
/// `not_a_ranking`; a list naming one id twice is `invalid_ranking`.
pub fn ranked_list(param: Option<&OutValue>) -> Result<RankedList, &'static str> {
    let (entries, has_origin): (Vec<Ranked>, bool) = match param {
        Some(OutValue::Ranking(r)) => (
            r.entries
                .iter()
                .map(|e| Ranked {
                    id: e.candidate.clone(),
                    origin: None,
                })
                .collect(),
            false,
        ),
        Some(OutValue::Shortlist(s)) => (
            s.ids
                .iter()
                .map(|id| Ranked {
                    id: id.clone(),
                    origin: None,
                })
                .collect(),
            false,
        ),
        // A shortfall adds no entry; it shows in `short@k`.
        Some(OutValue::Selection(s)) => (
            s.entries
                .iter()
                .map(|e| Ranked {
                    id: e.id.clone(),
                    origin: Some(e.origin),
                })
                .collect(),
            true,
        ),
        _ => return Err(reason::NOT_A_RANKING),
    };
    let mut seen = BTreeSet::new();
    if !entries.iter().all(|e| seen.insert(e.id.as_str())) {
        return Err(reason::INVALID_RANKING);
    }
    Ok(RankedList {
        entries,
        has_origin,
    })
}

/// One case's result for one ranking metric.
#[derive(Debug, Clone, PartialEq)]
pub struct RankingCase {
    /// The case's measure, or the reason it is excluded.
    pub outcome: Result<CaseMeasure, &'static str>,
    /// Unjudged items removed from the list the metric read; counted even
    /// when the case is excluded.
    pub unjudged_items: u64,
}

/// What a ranking declaration fixes for every case (3.4.2).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Relevance {
    pub relevant_at_least: u8,
    pub gain: Gain,
}

fn mean(value: f64) -> CaseMeasure {
    CaseMeasure::Mean { num: value, den: 1 }
}

fn excluded(reason: &'static str, unjudged_items: u64) -> RankingCase {
    RankingCase {
        outcome: Err(reason),
        unjudged_items,
    }
}

/// One case's contribution to `metric` (3.4.3). `gold` is the case's gold
/// `relevance` map; none excludes the case (`no_gold`).
pub fn ranking_case(
    metric: RankingMetric,
    list: &RankedList,
    gold: Option<&BTreeMap<String, u8>>,
    rel: Relevance,
) -> RankingCase {
    let Some(gold) = gold else {
        return excluded(reason::NO_GOLD, 0);
    };
    let read = match metric.k() {
        Some(k) => list
            .entries
            .len()
            .min(usize::try_from(k).unwrap_or(usize::MAX)),
        None => list.entries.len(),
    };
    // The condensed list: judged items in order, renumbered from 1.
    let condensed: Vec<u8> = list.entries[..read]
        .iter()
        .filter_map(|e| gold.get(&e.id).copied())
        .collect();
    let unjudged = (read - condensed.len()) as u64;
    let relevant_total = gold
        .values()
        .filter(|g| **g >= rel.relevant_at_least)
        .count() as u64;
    let relevant = |g: &u8| *g >= rel.relevant_at_least;
    if !matches!(metric, RankingMetric::Precision(_)) && relevant_total == 0 {
        return excluded(reason::NO_RELEVANT, unjudged);
    }
    if condensed.is_empty() {
        return excluded(reason::NO_JUDGED_ITEMS, unjudged);
    }
    let hits = condensed.iter().filter(|g| relevant(g)).count() as u64;
    let first = condensed.iter().position(relevant);
    let outcome = match metric {
        RankingMetric::Precision(_) => mean(hits as f64 / condensed.len() as f64),
        RankingMetric::Recall(_) => mean(hits as f64 / relevant_total as f64),
        RankingMetric::Hit(_) => CaseMeasure::Count {
            num: u64::from(hits > 0),
            den: 1,
        },
        RankingMetric::Mrr | RankingMetric::MrrAt(_) => {
            mean(first.map_or(0.0, |r| 1.0 / (r as u64 + 1) as f64))
        }
        RankingMetric::Ndcg(k) => {
            let mut dcg = 0.0;
            for (i, g) in condensed.iter().enumerate() {
                dcg += rel.gain.of(*g) * discount(i + 1);
            }
            let mut ideal: Vec<u8> = gold.values().copied().collect();
            ideal.sort_unstable_by(|a, b| b.cmp(a));
            let mut idcg = 0.0;
            for (i, g) in ideal
                .iter()
                .take(usize::try_from(k).unwrap_or(usize::MAX))
                .enumerate()
            {
                idcg += rel.gain.of(*g) * discount(i + 1);
            }
            // 3.4.3: R > 0 implies IDCG > 0 when relevant_at_least is at
            // least 1, as every declared ranking's is (3.4.2). A caller
            // passing 0 gets the exclusion, never a NaN.
            if idcg <= 0.0 {
                return excluded(reason::NO_RELEVANT, unjudged);
            }
            mean(dcg / idcg)
        }
    };
    RankingCase {
        outcome: Ok(outcome),
        unjudged_items: unjudged,
    }
}

/// One case's contribution to `short@k` (3.4.3): whether its list has
/// fewer than k entries, over the cases with a ranking.
pub fn short_case(list: &RankedList, k: u64) -> CaseMeasure {
    CaseMeasure::Count {
        num: u64::from((list.entries.len() as u64) < k),
        den: 1,
    }
}

/// One case's contribution to `backfill@p<p>` (3.4.4): whether the entry
/// at position p came from backfill, over the lists that have a position
/// p. A list without per-position origin is `no_origin`.
pub fn backfill_case(list: &RankedList, p: u64) -> Result<CaseMeasure, &'static str> {
    if !list.has_origin {
        return Err(reason::NO_ORIGIN);
    }
    // Positions count from 1: position 0 is no position of any list.
    let entry = p
        .checked_sub(1)
        .and_then(|i| usize::try_from(i).ok())
        .and_then(|i| list.entries.get(i))
        .ok_or(reason::NO_POSITION)?;
    Ok(CaseMeasure::Count {
        num: u64::from(entry.origin == Some(SelectionOrigin::Backfill)),
        den: 1,
    })
}