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. Logical property `TypeId`s are sorted and hashed 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};

#[cfg(feature = "profiling")]
use crate::entity::property_store::registered_property_name;
use crate::entity::Entity;
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,
}

/// Process-local identifier for an entity-scoped unordered property set.
///
/// The numeric value is an implementation detail and is not stable across
/// processes.
#[cfg(feature = "profiling")]
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub(crate) struct QueryIdentityId(usize);

#[cfg(feature = "profiling")]
impl QueryIdentityId {
    pub(crate) const fn from_raw(raw: usize) -> Self {
        Self(raw)
    }
}

#[derive(Clone, Copy, Default)]
struct QueryShapeRecord {
    representative: Option<MultiPropertyId>,
    #[cfg(feature = "profiling")]
    identity: Option<QueryIdentityId>,
}

#[derive(Default)]
struct QueryShapeRegistry {
    shapes: HashMap<(usize, HashValueType), QueryShapeRecord>,
    #[cfg(feature = "profiling")]
    labels: Vec<&'static str>,
}

enum PreMainDiagnostic {
    Warning(String),
}

/// Metadata for entity-scoped, unordered component-property sets.
///
/// Query tuple lookup uses this to resolve a representative multi-property
/// index. Profiling additionally interns each observed shape to a compact ID
/// and stores its reporting label here.
static QUERY_SHAPE_REGISTRY: LazyLock<Mutex<QueryShapeRegistry>> =
    LazyLock::new(|| Mutex::new(QueryShapeRegistry::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()));

fn query_shape_key(entity_id: usize, type_ids: &[TypeId]) -> (usize, HashValueType) {
    (entity_id, one_shot_128(&type_ids))
}

/// 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 key = query_shape_key(entity_id, type_ids);
    QUERY_SHAPE_REGISTRY
        .lock()
        .unwrap()
        .shapes
        .get(&key)
        .and_then(|record| record.representative)
        .map(|representative| representative.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 key = query_shape_key(entity_id, type_ids);
    let value = MultiPropertyId { id, name };
    let existing = {
        let mut registry = QUERY_SHAPE_REGISTRY.lock().unwrap();
        let record = registry.shapes.entry(key).or_default();
        match record.representative {
            Some(existing) => Some(existing),
            None => {
                record.representative = Some(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))
}

#[cfg(feature = "profiling")]
fn build_query_identity_label<E: Entity>(type_ids: &[TypeId]) -> String {
    if type_ids.is_empty() {
        return format!("{}: All", E::name());
    }

    let mut names = type_ids
        .iter()
        .map(|&type_id| registered_property_name(E::id(), type_id))
        .collect::<Vec<_>>();
    names.sort_unstable();

    format!("{}: ({})", E::name(), names.join(", "))
}

/// Returns the process-local profiling identity for a sorted query shape.
#[cfg(feature = "profiling")]
pub(crate) fn intern_query_identity<E: Entity>(type_ids: &[TypeId]) -> QueryIdentityId {
    let key = query_shape_key(E::id(), type_ids);

    {
        let registry = QUERY_SHAPE_REGISTRY.lock().unwrap();
        if let Some(identity) = registry.shapes.get(&key).and_then(|record| record.identity) {
            return identity;
        }
    }

    // Property metadata has its own lock, so build the label without holding
    // the query-shape registry lock.
    let label = build_query_identity_label::<E>(type_ids);

    let mut registry = QUERY_SHAPE_REGISTRY.lock().unwrap();
    if let Some(identity) = registry.shapes.get(&key).and_then(|record| record.identity) {
        return identity;
    }

    let identity = QueryIdentityId(registry.labels.len());
    registry.labels.push(Box::leak(label.into_boxed_str()));
    registry.shapes.entry(key).or_default().identity = Some(identity);
    identity
}

/// Returns the raw process-local profiling identity for an entity-scoped query shape.
///
/// This function exists for Ixa's exported entity and property macros. The returned value is an
/// implementation detail and is not stable across processes.
#[doc(hidden)]
pub fn intern_query_identity_raw<E: Entity>(type_ids: &[TypeId]) -> usize {
    #[cfg(feature = "profiling")]
    {
        intern_query_identity::<E>(type_ids).0
    }

    #[cfg(not(feature = "profiling"))]
    {
        let _ = type_ids;
        panic!("query profiling identities require the profiling feature")
    }
}

/// Returns the reporting label for a process-local profiling identity.
#[cfg(feature = "profiling")]
pub(crate) fn query_identity_label(identity: QueryIdentityId) -> &'static str {
    QUERY_SHAPE_REGISTRY.lock().unwrap().labels[identity.0]
}

#[cfg(all(test, feature = "profiling"))]
pub(crate) fn test_query_identity(label: &'static str) -> QueryIdentityId {
    let mut registry = QUERY_SHAPE_REGISTRY.lock().unwrap();
    let identity = QueryIdentityId(registry.labels.len());
    registry.labels.push(label);
    identity
}

#[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);
}