ixa/entity/
multi_property.rs

1#![allow(dead_code)]
2//! Utilities for managing and querying multi-properties.
3//!
4//! A multi-property is a derived property composed of a tuple of other properties. They are
5//! primarily used to enable joint indexing and efficient multi-column style queries.
6//!
7//! ## Indexing and Normalization
8//!
9//! To ensure that queries can efficiently find matching indexes, multi-properties that consist
10//! of the same set of component properties are considered equivalent, regardless of their
11//! definition order. The system achieves this by:
12//! 1.  **Canonicalization**: Component properties are sorted based on their unique identifiers.
13//! 2.  **Shared Indexes**: The index subsystem reuses a single `Index` instance for all
14//!     multi-properties that are equivalent up to reordering.
15//!
16//! ## Query Integration
17//!
18//! The querying subsystem uses the utilities in this module to detect when a query involving
19//! multiple individual properties can be satisfied by an existing multi-property index. If a
20//! match is found, the query can perform a fast index lookup instead of iterating over component
21//! properties.
22//!
23//! ## Implementation Details
24//!
25//! Multi-properties are defined using the [`define_multi_property!`](crate::define_multi_property) macro, which
26//! handles the registration and mapping between the property set and its canonical
27//! index ID. This module provides the runtime registry (`MULTI_PROPERTY_INDEX_MAP`)
28//! and reordering logic used by both the macro-generated code and the query engine.
29
30use std::any::TypeId;
31use std::cell::RefCell;
32use std::sync::{LazyLock, Mutex};
33
34use crate::hashing::{one_shot_128, HashMap, HashValueType};
35
36/// A map from a list of `TypeId`s to the index ID of the equivalent multi-property
37/// type. The list of `TypeId`s is assumed to be sorted.
38///
39/// Use `register_type_ids_to_multi_property_index()` to register a multi-property.
40/// We could instead just rely on `TypeId::of::<P::CanonicalValue>()`, but this
41/// allows us to determine the type dynamically, e.g. for the web API or debug
42/// console.
43static MULTI_PROPERTY_INDEX_MAP: LazyLock<Mutex<RefCell<HashMap<HashValueType, usize>>>> =
44    LazyLock::new(|| Mutex::new(RefCell::new(HashMap::default())));
45
46/// A method that looks up the index ID of the multi-property that has the given
47/// list of `TypeId`s as its properties.
48pub fn type_ids_to_multi_property_index(type_ids: &[TypeId]) -> Option<usize> {
49    let hash = one_shot_128(&type_ids);
50    MULTI_PROPERTY_INDEX_MAP
51        .lock()
52        .unwrap()
53        .borrow()
54        .get(&hash)
55        .copied()
56}
57
58/// A method that registers the index ID of the multi-property tuple type that has the given
59/// list of `TypeId`s as its properties.
60///
61/// Use `type_ids_to_muli_property_index()` to look up an index ID.
62pub fn register_type_ids_to_multi_property_index(type_ids: &[TypeId], index: usize) {
63    let hash = one_shot_128(&type_ids);
64    MULTI_PROPERTY_INDEX_MAP
65        .lock()
66        .unwrap()
67        .borrow_mut()
68        .insert(hash, index);
69}
70
71// The following free functions are utilities used in the macro implementation of `Query::multi_property_value_hash`,
72// which computes the same hash as an equivalent multi-property. This requires the values to be ordered according to
73// the lexicographic order of the property type names, which for queries must be done dynamically, as queries do
74// not (and cannot) have a proc macro trait impl.
75
76/// An iota function that returns an array of the form `[0, 1, 2, 3, ..., N-1]`. The size of the array
77/// is statically known, avoiding `Vec` allocations.
78const fn make_indices<const N: usize>() -> [usize; N] {
79    let mut arr = [0; N];
80    let mut i = 0;
81    while i < N {
82        arr[i] = i;
83        i += 1;
84    }
85    arr
86}
87
88/// Returns the indices of `keys` in sorted order. These indices are used to reorder some other
89/// array according to the sorted order of the `keys`, e.g. by `static_apply_reordering`.
90///
91/// "Static" in the name refers to the fact that it takes and returns an array of statically
92/// known size, avoiding `Vec` allocations.
93pub fn static_sorted_indices<T: Ord, const N: usize>(keys: &[T; N]) -> [usize; N] {
94    let mut indices = make_indices::<N>();
95    indices.sort_unstable_by_key(|&i| &keys[i]);
96    indices
97}
98
99/// Reorders the `values` in place according to the ordering defined by `indices`. The `indices`
100/// is an ordering produced by `sorted_indices`/`static_sorted_indices` and encodes the sorted
101/// order of the `keys` (the names of the tag types).
102///
103/// "Static" in the name refers to the fact that it takes and returns an array of statically
104/// known size, avoiding `Vec` allocations.
105pub fn static_apply_reordering<T: Copy, const N: usize>(values: &mut [T; N], indices: &[usize; N]) {
106    let tmp_values: [T; N] = *values;
107    for (old_index, new_index) in indices.iter().enumerate() {
108        values[old_index] = tmp_values[*new_index];
109    }
110}
111
112/// Reorder `values` in place according to the sorted order of `keys`.
113///
114/// Both slices must have the same length. "Static" in the name refers to the fact that it
115/// takes and returns an array of statically known size, avoiding `Vec` allocations.
116pub fn static_reorder_by_keys<T: Ord + Copy, U: Copy, const N: usize>(
117    keys: &[T; N],
118    values: &mut [U; N],
119) {
120    let indices: [usize; N] = static_sorted_indices(keys);
121    static_apply_reordering(values, &indices);
122}
ixa/entity/multi_property.rs

ixa/entity/
multi_property.rs
