ixa/entity/

multi_property.rs

#![allow(dead_code)]
//! Utilities for managing and querying multi-properties.
//!
//! A multi-property is a derived property composed of a tuple of other properties. They are
//! primarily used to enable joint indexing and efficient multi-column style queries.
//!
//! ## Normalization
//!
//! To ensure that queries can efficiently find matching indexes, multi-properties that consist
//! of the same set of component properties are considered equivalent, regardless of their
//! definition order. Component properties are sorted alphabetically by property name to produce
//! a canonical identity for that unordered component set. A query with the same component set can
//! then resolve to the index (if it exists) of an equivalent (multi-)property regardless of the
//! order client code provides the component values.
//!
//! ## Query Integration
//!
//! The querying subsystem uses the utilities in this module to detect when a query involving
//! multiple individual properties can be satisfied by an existing multi-property index. If a
//! match is found, the query can perform a fast index lookup instead of iterating over component
//! properties.
//!
//! ## Implementation Details
//!
//! Multi-properties are defined using the [`define_multi_property!`](crate::define_multi_property) macro, which
//! handles the registration and mapping between the property set and its representative
//! property ID. This module provides the runtime registries
//! and reordering logic used by both the macro-generated code and the query engine.

use std::any::TypeId;
use std::sync::{LazyLock, Mutex};

use crate::hashing::{one_shot_128, HashMap, HashValueType};
use crate::warn;

/// Local convenience type; we store the name of the property for use in diagnostics.
#[derive(Clone, Copy)]
struct MultiPropertyId {
    pub id: usize,
    pub name: &'static str,
}

enum PreMainDiagnostic {
    Warning(String),
}

/// A map from an entity-scoped, sorted list of component `TypeId`s to the representative
/// multi-property ID for that unordered component set.
///
/// Query tuple lookup uses this to resolve unordered query component sets to the
/// multi-property index that can satisfy the query.
static MULTI_PROPERTY_ID_MAP: LazyLock<Mutex<HashMap<(usize, HashValueType), MultiPropertyId>>> =
    LazyLock::new(|| Mutex::new(HashMap::default()));

/// A map from an entity-scoped concrete multi-property logical `TypeId` to the representative
/// multi-property ID for that unordered component set.
///
/// Singleton multi-property queries, source identity, and index creation guards use this to
/// resolve a concrete multi-property type to the representative selected for its component set.
static MULTI_PROPERTY_TYPE_ID_MAP: LazyLock<Mutex<HashMap<(usize, TypeId), MultiPropertyId>>> =
    LazyLock::new(|| Mutex::new(HashMap::default()));

/// Diagnostics generated by ctors before execution reaches `main`.
///
/// Ctors run before normal logging setup, so warnings and errors are queued here and emitted when
/// the first `Context` is constructed. Right now detecting equivalent multi-property registration
/// is our only use case.
static PRE_MAIN_DIAGNOSTICS: LazyLock<Mutex<Vec<PreMainDiagnostic>>> =
    LazyLock::new(|| Mutex::new(Vec::new()));

/// Looks up the representative multi-property ID for a sorted list of component `TypeId`s.
#[must_use]
pub fn type_ids_to_multi_property_id(entity_id: usize, type_ids: &[TypeId]) -> Option<usize> {
    let hash = one_shot_128(&type_ids);
    MULTI_PROPERTY_ID_MAP
        .lock()
        .unwrap()
        .get(&(entity_id, hash))
        .map(|value| value.id)
}

/// Looks up the representative multi-property ID and name for a concrete multi-property
/// logical `TypeId`.
pub(crate) fn multi_property_id_for_property_type_id(
    entity_id: usize,
    property_type_id: TypeId,
) -> Option<(usize, &'static str)> {
    MULTI_PROPERTY_TYPE_ID_MAP
        .lock()
        .unwrap()
        .get(&(entity_id, property_type_id))
        .map(|value| (value.id, value.name))
}

/// Registers the representative multi-property ID for an unordered component set.
///
/// Returns `None` if `id` became the representative. Returns the existing representative ID and
/// name if an equivalent multi-property had already been registered.
pub fn register_type_ids_to_multi_property_id(
    entity_id: usize,
    type_ids: &[TypeId],
    property_type_id: TypeId,
    id: usize,
    name: &'static str,
) -> Option<(usize, &'static str)> {
    let hash = one_shot_128(&type_ids);
    let key = (entity_id, hash);
    let value = MultiPropertyId { id, name };
    let existing = {
        let mut map = MULTI_PROPERTY_ID_MAP.lock().unwrap();
        match map.get(&key).copied() {
            Some(existing) => Some(existing),
            None => {
                map.insert(key, value);
                None
            }
        }
    };

    let representative = existing.unwrap_or(value);
    MULTI_PROPERTY_TYPE_ID_MAP
        .lock()
        .unwrap()
        .entry((entity_id, property_type_id))
        .or_insert(representative);

    existing.map(|existing| (existing.id, existing.name))
}

#[doc(hidden)]
pub fn record_pre_main_warning(message: String) {
    PRE_MAIN_DIAGNOSTICS
        .lock()
        .unwrap()
        .push(PreMainDiagnostic::Warning(message));
}

pub(crate) fn emit_pre_main_diagnostics() {
    for diagnostic in PRE_MAIN_DIAGNOSTICS.lock().unwrap().drain(..) {
        match diagnostic {
            PreMainDiagnostic::Warning(message) => warn!("{message}"),
        }
    }
}

// The following free functions are utilities used to normalize query parts into the same order as
// an equivalent multi-property canonical value. Query tuple impls have to do this dynamically,
// because they do not (and cannot) have a proc-macro-generated trait impl.

/// An iota function that returns an array of the form `[0, 1, 2, 3, ..., N-1]`. The size of the array
/// is statically known, avoiding `Vec` allocations.
const fn make_indices<const N: usize>() -> [usize; N] {
    let mut arr = [0; N];
    let mut i = 0;
    while i < N {
        arr[i] = i;
        i += 1;
    }
    arr
}

/// Returns the indices of `keys` in sorted order. These indices are used to reorder some other
/// array according to the sorted order of the `keys`, e.g. by `static_apply_reordering`.
///
/// "Static" in the name refers to the fact that it takes and returns an array of statically
/// known size, avoiding `Vec` allocations.
#[must_use]
pub fn static_sorted_indices<T: Ord, const N: usize>(keys: &[T; N]) -> [usize; N] {
    let mut indices = make_indices::<N>();
    indices.sort_unstable_by_key(|&i| &keys[i]);
    indices
}

/// Reorders the `values` in place according to the ordering defined by `indices`. The `indices`
/// is an ordering produced by `sorted_indices`/`static_sorted_indices` and encodes the sorted
/// order of the `keys` (the names of the tag types).
///
/// "Static" in the name refers to the fact that it takes and returns an array of statically
/// known size, avoiding `Vec` allocations.
pub fn static_apply_reordering<T: Copy, const N: usize>(values: &mut [T; N], indices: &[usize; N]) {
    let tmp_values: [T; N] = *values;
    for (old_index, new_index) in indices.iter().enumerate() {
        values[old_index] = tmp_values[*new_index];
    }
}

/// Returns the inverse of a reordering produced by [`static_sorted_indices`].
///
/// If `indices[sorted_position] == original_position`, the returned array maps
/// `original_position` back to `sorted_position`.
#[must_use]
pub fn static_inverse_indices<const N: usize>(indices: &[usize; N]) -> [usize; N] {
    let mut inverse = [0; N];
    for (sorted_position, &original_position) in indices.iter().enumerate() {
        inverse[original_position] = sorted_position;
    }
    inverse
}

/// Reorder `values` in place according to the sorted order of `keys`.
///
/// Both slices must have the same length. "Static" in the name refers to the fact that it
/// takes and returns an array of statically known size, avoiding `Vec` allocations.
pub fn static_reorder_by_keys<T: Ord + Copy, U: Copy, const N: usize>(
    keys: &[T; N],
    values: &mut [U; N],
) {
    let indices: [usize; N] = static_sorted_indices(keys);
    static_apply_reordering(values, &indices);
}