wowlab_common/sim/permutations/

space.rs

use std::{collections::HashMap, fmt, hash::BuildHasher, num::TryFromIntError};

use serde::{
    Deserialize, Deserializer, Serialize,
    de::{Error as _, MapAccess, Visitor},
};
#[cfg(feature = "wasm")]
use tsify::Tsify;
use wowlab_parsers::{Item, Profile};
use wowlab_types::{
    game::GearSlot,
    sim::{FastMap, FastSet},
};

use crate::sim::sentinel_config::{CandidateItemConfig, SlotCandidatesConfig};

/// Where a candidate came from.
#[derive(Clone, Copy, Debug, Deserialize, Eq, PartialEq, Serialize)]
#[cfg_attr(feature = "wasm", derive(Tsify))]
#[serde(rename_all = "camelCase")]
// #t(rust_non_exhaustive_on_public) source list is fixed
pub enum CandidateSource {
    Equipped,
    Bag,
    Weekly,
}

/// Candidate item for a slot.
#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
#[cfg_attr(feature = "wasm", derive(Tsify))]
#[serde(rename_all = "camelCase")]
pub struct Candidate {
    pub item: Item,
    pub source: CandidateSource,
}

/// One slot with its candidates.
#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
#[cfg_attr(feature = "wasm", derive(Tsify))]
#[serde(rename_all = "camelCase")]
pub struct SlotCandidates {
    pub slot: GearSlot,
    pub candidates: Vec<Candidate>,
}

impl SlotCandidates {
    #[must_use]
    pub fn count(&self) -> usize {
        self.candidates.len()
    }

    /// True when more than one candidate.
    #[must_use]
    pub fn is_contested(&self) -> bool {
        self.candidates.len() > 1
    }
}

/// Cartesian product space.
#[derive(Clone, Debug, PartialEq, Serialize)]
#[cfg_attr(feature = "wasm", derive(Tsify))]
#[serde(rename_all = "camelCase")]
pub struct PermutationSpace {
    slots: Vec<SlotCandidates>,
    contested_indices: Vec<usize>,
    total: u64,
    contested_count: u32,
    total_candidates: u32,
}

const PERMUTATION_SPACE_FIELDS: &[&str] = &[
    "slots",
    "contestedIndices",
    "total",
    "contestedCount",
    "totalCandidates",
];

#[derive(Clone, Copy, Deserialize)]
#[serde(field_identifier, rename_all = "camelCase")]
enum PermutationSpaceField {
    Slots,
    ContestedIndices,
    Total,
    ContestedCount,
    TotalCandidates,
}

#[derive(Default)]
struct PendingPermutationSpace {
    slots: Option<Vec<SlotCandidates>>,
    contested_indices: Option<Vec<usize>>,
    total: Option<u64>,
    contested_count: Option<u32>,
    total_candidates: Option<u32>,
}

impl PendingPermutationSpace {
    fn deserialize_field<'de, A>(
        &mut self,
        field: PermutationSpaceField,
        map: &mut A,
    ) -> Result<(), A::Error>
    where
        A: MapAccess<'de>,
    {
        match field {
            PermutationSpaceField::Slots => {
                deserialize_required_field(&mut self.slots, map, "slots")
            }
            PermutationSpaceField::ContestedIndices => {
                deserialize_required_field(&mut self.contested_indices, map, "contestedIndices")
            }
            PermutationSpaceField::Total => {
                deserialize_required_field(&mut self.total, map, "total")
            }
            PermutationSpaceField::ContestedCount => {
                deserialize_required_field(&mut self.contested_count, map, "contestedCount")
            }
            PermutationSpaceField::TotalCandidates => {
                deserialize_required_field(&mut self.total_candidates, map, "totalCandidates")
            }
        }
    }

    fn validate<E>(self) -> Result<PermutationSpace, E>
    where
        E: serde::de::Error,
    {
        let space = PermutationSpace {
            slots: self.slots.ok_or_else(|| E::missing_field("slots"))?,
            contested_indices: self
                .contested_indices
                .ok_or_else(|| E::missing_field("contestedIndices"))?,
            total: self.total.ok_or_else(|| E::missing_field("total"))?,
            contested_count: self
                .contested_count
                .ok_or_else(|| E::missing_field("contestedCount"))?,
            total_candidates: self
                .total_candidates
                .ok_or_else(|| E::missing_field("totalCandidates"))?,
        };

        if let Err(error) = space.validate() {
            return Err(E::custom(error));
        }

        Ok(space)
    }
}

struct PermutationSpaceVisitor;

impl<'de> Visitor<'de> for PermutationSpaceVisitor {
    type Value = PermutationSpace;

    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        formatter.write_str("a permutation space")
    }

    fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
    where
        A: MapAccess<'de>,
    {
        let mut pending = PendingPermutationSpace::default();

        while let Some(field) = map.next_key()? {
            pending.deserialize_field(field, &mut map)?;
        }

        pending.validate()
    }
}

fn deserialize_required_field<'de, T, A>(
    destination: &mut Option<T>,
    map: &mut A,
    field: &'static str,
) -> Result<(), A::Error>
where
    T: Deserialize<'de>,
    A: MapAccess<'de>,
{
    if destination.is_some() {
        return Err(A::Error::duplicate_field(field));
    }

    *destination = Some(map.next_value()?);

    Ok(())
}

/// Largest exactly representable integer in JavaScript's `number` type.
pub const MAX_PERMUTATION_TOTAL: u64 = 9_007_199_254_740_991;

/// A mixed-radix choice is stored as `u8`, so one slot can expose at most 256 candidates.
pub const MAX_CANDIDATES_PER_SLOT: usize = u8::MAX as usize + 1;

wowlab_engine_macros::define_error! {
/// Invalid or unsupported permutation-space construction.
#[derive(Debug, Eq, PartialEq)]
pub struct PermutationError {
    #[source]
    kind: PermutationErrorKind,
}

#[derive(Debug, thiserror::Error, Eq, PartialEq)]
enum PermutationErrorKind {
    #[error("slot {slot_index} has no candidates")]
    EmptySlot { slot_index: usize },
    #[error(
        "slot {slot_index} has {count} candidates; maximum supported is {MAX_CANDIDATES_PER_SLOT}"
    )]
    TooManyCandidates { slot_index: usize, count: usize },
    #[error("permutation cardinality exceeds the JavaScript-safe maximum {MAX_PERMUTATION_TOTAL}")]
    CardinalityTooLarge,
    #[error("contestedIndices does not match the contested slots derived from slots")]
    ContestedIndicesMismatch,
    #[error("{field} is {actual}, but the value derived from slots is {expected}")]
    DerivedFieldMismatch {
        field: &'static str,
        expected: u64,
        actual: u64,
    },
    #[error("permutation cost overflow while computing {operation}")]
    CostOverflow { operation: &'static str },
    #[error("{field} cannot be represented by the permutation-space metadata: {source}")]
    IntegerConversion {
        field: &'static str,
        #[source]
        source: TryFromIntError,
    },
}
}

impl PermutationError {
    const fn new(kind: PermutationErrorKind) -> Self {
        Self { kind }
    }

    const fn empty_slot(slot_index: usize) -> Self {
        Self::new(PermutationErrorKind::EmptySlot { slot_index })
    }

    const fn too_many_candidates(slot_index: usize, count: usize) -> Self {
        Self::new(PermutationErrorKind::TooManyCandidates { slot_index, count })
    }

    const fn cardinality_too_large() -> Self {
        Self::new(PermutationErrorKind::CardinalityTooLarge)
    }

    const fn contested_indices_mismatch() -> Self {
        Self::new(PermutationErrorKind::ContestedIndicesMismatch)
    }

    const fn derived_field_mismatch(field: &'static str, expected: u64, actual: u64) -> Self {
        Self::new(PermutationErrorKind::DerivedFieldMismatch {
            field,
            expected,
            actual,
        })
    }

    pub(super) const fn cost_overflow(operation: &'static str) -> Self {
        Self::new(PermutationErrorKind::CostOverflow { operation })
    }

    fn integer_conversion(field: &'static str, source: TryFromIntError) -> Self {
        Self::new(PermutationErrorKind::IntegerConversion { field, source })
    }
}

impl PermutationSpace {
    /// Validate all structural and derived invariants.
    ///
    /// # Errors
    ///
    /// Returns an error for empty or oversized candidate sets and inconsistent derived fields.
    /// Cardinalities not exactly representable by the JavaScript API are also rejected.
    pub fn validate(&self) -> Result<(), PermutationError> {
        let (contested_indices, total, contested_count, total_candidates) =
            derive_space_metadata(&self.slots)?;

        if self.contested_indices != contested_indices {
            return Err(PermutationError::contested_indices_mismatch());
        }

        validate_derived_field("total", total, self.total)?;
        validate_derived_field(
            "contestedCount",
            u64::from(contested_count),
            u64::from(self.contested_count),
        )?;

        validate_derived_field(
            "totalCandidates",
            u64::from(total_candidates),
            u64::from(self.total_candidates),
        )
    }

    #[must_use]
    pub fn slots(&self) -> &[SlotCandidates] {
        &self.slots
    }

    #[must_use]
    pub fn contested_indices(&self) -> &[usize] {
        &self.contested_indices
    }

    #[must_use]
    pub const fn total(&self) -> u64 {
        self.total
    }

    #[must_use]
    pub const fn contested_count(&self) -> u32 {
        self.contested_count
    }

    #[must_use]
    pub const fn total_candidates(&self) -> u32 {
        self.total_candidates
    }

    /// Mixed-radix decode of a combination index.
    #[must_use]
    pub fn decode(&self, mut index: u64) -> Vec<u8> {
        let mut choices = vec![0u8; self.contested_indices.len()];

        // #t(block: rust_unchecked_indexing) indices bounded by construction
        for i in (0..self.contested_indices.len()).rev() {
            let slot_idx = self.contested_indices[i];
            let radix = self.slots[slot_idx].count() as u64;

            // BOUNDS: i is produced by the contested_indices range used to size choices.

            choices[i] = u8::try_from(index % radix).unwrap_or(u8::MAX);
            index /= radix;
        }

        choices
    }

    /// Encode per-slot choices to a combination index.
    #[must_use]
    pub fn encode(&self, choices: &[u8]) -> u64 {
        let mut index = 0u64;

        // #t(block: rust_unchecked_indexing) indices bounded by construction
        for (i, &choice) in choices.iter().enumerate() {
            let slot_idx = self.contested_indices[i];
            let radix = self.slots[slot_idx].count() as u64;

            index = index * radix + u64::from(choice);
        }

        index
    }

    /// Full item picks for a combination index.
    #[must_use]
    pub fn picks(&self, index: u64) -> Vec<(GearSlot, &Candidate)> {
        let choices = self.decode(index);
        let mut choice_map = FastMap::default();

        choice_map.reserve(self.contested_indices.len());

        // #t(block: rust_unchecked_indexing) ci bounded by enumerate
        for (ci, &slot_idx) in self.contested_indices.iter().enumerate() {
            choice_map.insert(slot_idx, choices[ci]);
        }

        self.slots
            .iter()
            .enumerate()
            .filter_map(|(i, sc)| {
                let pick_idx = *choice_map.get(&i).unwrap_or(&0) as usize;

                sc.candidates.get(pick_idx).map(|c| (sc.slot, c))
            })
            .collect()
    }

    #[must_use]
    pub fn contested_slots(&self) -> Vec<&SlotCandidates> {
        self.contested_indices
            .iter()
            // BOUNDS: contested_indices contains valid slot indices by construction
            .map(|&i| &self.slots[i])
            .collect()
    }
}

impl<'de> Deserialize<'de> for PermutationSpace {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        deserializer.deserialize_struct(
            "PermutationSpace",
            PERMUTATION_SPACE_FIELDS,
            PermutationSpaceVisitor,
        )
    }
}

/// Build a permutation space from a parsed `SimC` profile.
///
/// # Errors
///
/// Returns an error when a slot has too many candidates.
/// Cartesian products not exactly representable by the JavaScript API are also rejected.
pub fn build_space(profile: &Profile) -> Result<PermutationSpace, PermutationError> {
    let candidate_count =
        profile.equipment.len() + profile.bag_items.len() + profile.weekly_rewards.len();
    let mut slot_map: FastMap<GearSlot, Vec<Candidate>> = FastMap::default();

    slot_map.reserve(candidate_count);

    // #t(block: rust_clone_in_loop) construction-time, not hot path
    for item in &profile.equipment {
        slot_map.entry(item.gear.slot).or_default().push(Candidate {
            item: item.clone(),
            source: CandidateSource::Equipped,
        });
    }

    for item in &profile.bag_items {
        let candidates = slot_map.entry(item.gear.slot).or_default();

        if !has_dup(candidates, item) {
            candidates.push(Candidate {
                // #t(rust_clone_in_loop) candidate storage owns the selected profile item
                item: item.clone(),
                source: CandidateSource::Bag,
            });
        }
    }

    for item in &profile.weekly_rewards {
        let candidates = slot_map.entry(item.gear.slot).or_default();

        if !has_dup(candidates, item) {
            candidates.push(Candidate {
                // #t(rust_clone_in_loop) candidate storage owns the selected profile item
                item: item.clone(),
                source: CandidateSource::Weekly,
            });
        }
    }

    finalize_space(collect_slots_in_order(profile, &mut slot_map))
}

/// Build a permutation space restricted to user-selected bag/weekly items.
///
/// # Errors
///
/// Returns an error when a slot has too many candidates.
/// Cartesian products not exactly representable by the JavaScript API are also rejected.
// #t(fn: rust_clone_in_loop) construction-time, not hot path
pub fn build_space_for_selection<S>(
    profile: &Profile,
    selections: &HashMap<GearSlot, Vec<u32>, S>,
) -> Result<PermutationSpace, PermutationError>
where
    S: BuildHasher,
{
    let candidate_count =
        profile.equipment.len() + profile.bag_items.len() + profile.weekly_rewards.len();
    let mut slot_map: FastMap<GearSlot, Vec<Candidate>> = FastMap::default();

    slot_map.reserve(candidate_count);

    for item in &profile.equipment {
        slot_map.entry(item.gear.slot).or_default().push(Candidate {
            item: item.clone(),
            source: CandidateSource::Equipped,
        });
    }

    for (&slot, indices) in selections {
        if indices.is_empty() {
            continue;
        }

        let bag: Vec<&Item> = profile
            .bag_items
            .iter()
            .filter(|i| i.gear.slot == slot)
            .collect();
        let weekly: Vec<&Item> = profile
            .weekly_rewards
            .iter()
            .filter(|i| i.gear.slot == slot)
            .collect();
        let candidates = slot_map.entry(slot).or_default();

        for &idx in indices {
            let i = idx as usize;
            let (item, source) = if i < bag.len() {
                // BOUNDS: i < bag.len() checked above
                (bag[i], CandidateSource::Bag)
            } else if i - bag.len() < weekly.len() {
                // BOUNDS: i - bag.len() < weekly.len() checked above
                (weekly[i - bag.len()], CandidateSource::Weekly)
            } else {
                continue;
            };

            if !has_dup(candidates, item) {
                candidates.push(Candidate {
                    item: item.clone(),
                    source,
                });
            }
        }
    }

    finalize_space(collect_slots_in_order(profile, &mut slot_map))
}

/// Tournament `slot_candidates` payload; contested slots only.
#[must_use]
pub fn tournament_payload(space: &PermutationSpace) -> Vec<SlotCandidatesConfig> {
    space
        .slots()
        .iter()
        .filter(|sc| sc.is_contested())
        .map(|sc| SlotCandidatesConfig {
            slot: sc.slot.to_string(),
            items: sc
                .candidates
                .iter()
                .map(|c| CandidateItemConfig {
                    item_id: c.item.gear.id,
                    bonus_ids: c.item.gear.bonus_ids.clone().unwrap_or_default(),
                    enchant_id: c.item.gear.enchant_id.unwrap_or(0),
                    gem_ids: c.item.gear.gem_ids.clone().unwrap_or_default(),
                })
                .collect(),
        })
        .collect()
}

fn collect_slots_in_order(
    profile: &Profile,
    slot_map: &mut FastMap<GearSlot, Vec<Candidate>>,
) -> Vec<SlotCandidates> {
    let mut seen = FastSet::default();

    seen.reserve(profile.equipment.len());
    let mut slots = Vec::with_capacity(slot_map.len());

    for item in &profile.equipment {
        if seen.insert(item.gear.slot) {
            if let Some(candidates) = slot_map.remove(&item.gear.slot) {
                slots.push(SlotCandidates {
                    slot: item.gear.slot,
                    candidates,
                });
            }
        }
    }

    for (slot, candidates) in slot_map.drain() {
        slots.push(SlotCandidates { slot, candidates });
    }

    slots
}

fn finalize_space(slots: Vec<SlotCandidates>) -> Result<PermutationSpace, PermutationError> {
    let (contested_indices, total, contested_count, total_candidates) =
        derive_space_metadata(&slots)?;

    Ok(PermutationSpace {
        slots,
        contested_indices,
        total,
        contested_count,
        total_candidates,
    })
}

fn derive_space_metadata(
    slots: &[SlotCandidates],
) -> Result<(Vec<usize>, u64, u32, u32), PermutationError> {
    let mut contested_indices = Vec::new();
    let mut total = 1_u64;
    let mut total_candidates = 0_u32;

    for (slot_index, slot) in slots.iter().enumerate() {
        let count = slot.count();

        if count == 0 {
            return Err(PermutationError::empty_slot(slot_index));
        }

        if count > MAX_CANDIDATES_PER_SLOT {
            return Err(PermutationError::too_many_candidates(slot_index, count));
        }

        let count_u32 = u32::try_from(count).map_err(|source| {
            PermutationError::integer_conversion("slot candidate count", source)
        })?;

        total_candidates = total_candidates
            .checked_add(count_u32)
            .ok_or_else(PermutationError::cardinality_too_large)?;

        if slot.is_contested() {
            contested_indices.push(slot_index);
            total = total
                .checked_mul(u64::from(count_u32))
                .filter(|&value| value <= MAX_PERMUTATION_TOTAL)
                .ok_or_else(PermutationError::cardinality_too_large)?;
        }
    }

    let contested_count = u32::try_from(contested_indices.len())
        .map_err(|source| PermutationError::integer_conversion("contested slot count", source))?;

    Ok((contested_indices, total, contested_count, total_candidates))
}

fn validate_derived_field(
    field: &'static str,
    expected: u64,
    actual: u64,
) -> Result<(), PermutationError> {
    if expected == actual {
        Ok(())
    } else {
        Err(PermutationError::derived_field_mismatch(
            field, expected, actual,
        ))
    }
}

fn has_dup(candidates: &[Candidate], item: &Item) -> bool {
    candidates
        .iter()
        .any(|c| c.item.gear.id == item.gear.id && c.item.gear.bonus_ids == item.gear.bonus_ids)
}