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 alphabetically by property name.
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 to normalize query parts into the same order as
72// an equivalent multi-property canonical value. Query tuple impls have to do this dynamically,
73// because they do not (and cannot) have a proc-macro-generated trait impl.
74
75/// An iota function that returns an array of the form `[0, 1, 2, 3, ..., N-1]`. The size of the array
76/// is statically known, avoiding `Vec` allocations.
77const fn make_indices<const N: usize>() -> [usize; N] {
78    let mut arr = [0; N];
79    let mut i = 0;
80    while i < N {
81        arr[i] = i;
82        i += 1;
83    }
84    arr
85}
86
87/// Returns the indices of `keys` in sorted order. These indices are used to reorder some other
88/// array according to the sorted order of the `keys`, e.g. by `static_apply_reordering`.
89///
90/// "Static" in the name refers to the fact that it takes and returns an array of statically
91/// known size, avoiding `Vec` allocations.
92pub fn static_sorted_indices<T: Ord, const N: usize>(keys: &[T; N]) -> [usize; N] {
93    let mut indices = make_indices::<N>();
94    indices.sort_unstable_by_key(|&i| &keys[i]);
95    indices
96}
97
98/// Reorders the `values` in place according to the ordering defined by `indices`. The `indices`
99/// is an ordering produced by `sorted_indices`/`static_sorted_indices` and encodes the sorted
100/// order of the `keys` (the names of the tag types).
101///
102/// "Static" in the name refers to the fact that it takes and returns an array of statically
103/// known size, avoiding `Vec` allocations.
104pub fn static_apply_reordering<T: Copy, const N: usize>(values: &mut [T; N], indices: &[usize; N]) {
105    let tmp_values: [T; N] = *values;
106    for (old_index, new_index) in indices.iter().enumerate() {
107        values[old_index] = tmp_values[*new_index];
108    }
109}
110
111/// Reorder `values` in place according to the sorted order of `keys`.
112///
113/// Both slices must have the same length. "Static" in the name refers to the fact that it
114/// takes and returns an array of statically known size, avoiding `Vec` allocations.
115pub fn static_reorder_by_keys<T: Ord + Copy, U: Copy, const N: usize>(
116    keys: &[T; N],
117    values: &mut [U; N],
118) {
119    let indices: [usize; N] = static_sorted_indices(keys);
120    static_apply_reordering(values, &indices);
121}
ixa/entity/multi_property.rs

ixa/entity/
multi_property.rs
