MTB::Entity: Address-stable, interior-mutable Slab allocator

中文版请见: README-zh.md

⚠️ Notes

• This allocator is experimental and unstable: for each semver 0.x.y, each .y change causes API breaking changes and each .x change causes rewrite or redesign of this project.
• Not thoroughly tested; may contain memory-safety issues. Use with care.
• Single-threaded only; no plans for multithreading.
• If you don’t specifically need interior mutability, prefer the slab crate for performance and safety.

Introduction

While building Remusys, needing a mutable reference to allocate with slab::Slab made some optimizations awkward. This allocator is chunked and address-stable, and it lets you allocate while reading existing elements.

use mtb_entity_slab::*;

/// You can use `#[entity_id]` to create an opaque ID wrapper bound to a fixed policy.
/// If the allocator type is too verbose, specify an alias via `allocator_type`.
#[entity_id(InstID, policy = 256, allocator_type = InstAllocT)]
#[derive(Debug, Clone, PartialEq, Eq)]
struct Inst {
    pub opcode: u32,
    pub operands: [u64; 4],
    pub heap_data: String,
}

impl Inst {
    fn new(opcode: u32) -> Self {
        Self {
            opcode,
            operands: [0; 4],
            heap_data: format!("InstData{}", opcode),
        }
    }
}

fn main() {
    // In general you specify the policy at the type level.
    // If you used `allocator_type = InstAllocT` above, you can use the alias instead of
    // the verbose type `EntityAlloc<Inst, AllocPolicy256>`.
    let alloc: EntityAlloc<Inst, AllocPolicy256> = EntityAlloc::with_capacity(1024);

    let ptrs = {
        let mut v = Vec::new();
        for i in 0..1000 {
            // Allocate while only holding &alloc (interior mutability)
            let ptr = alloc.allocate_ptr(Inst::new(i));
            v.push(ptr);
        }
        v
    };

    let inst = ptrs[500].deref(&alloc);

    // Allocate while reading
    let new_id = alloc.allocate_ptr(Inst::new(2000));
    assert_eq!(inst.opcode, 500);
    assert_eq!(new_id.deref(&alloc).opcode, 2000);
}

Core types

• EntityAlloc<E, P> — allocator managing chunks and elements.
• PtrID<E, P> — pointer-style ID; internally a raw pointer. Fast but unsafe to misuse.
• IndexedID<E, P> — index-style ID; chunk index + in-chunk index. Safer but slower.
• IEntityAllocID<E, P> — trait for converting between PtrID and IndexedID.
• IPoliciedID — trait binding an ID to its object type and allocator type (policy included). PtrID<E, P>, IndexedID<E, P> and macro-generated wrappers implement this.
• IDBoundAlloc<I> — convenience alias for EntityAlloc<<I as IPoliciedID>::ObjectT, <I as IPoliciedID>::PolicyT>.

Allocation policies

Policies are compile-time constants on P:

• AllocPolicy128 — 128 elements per chunk (single-level bitmap)
• AllocPolicy256 — 256 elements per chunk (single-level bitmap)
• AllocPolicy512 — 512 elements per chunk (single-level bitmap)
• AllocPolicy1024 — 1024 elements per chunk (two-level bitmap)
• AllocPolicy2048 — 2048 elements per chunk (two-level bitmap)
• AllocPolicy4096 — 4096 elements per chunk (two-level bitmap)

Examples with an Inst entity:

let alloc_128:  EntityAlloc<Inst, AllocPolicy128>  = EntityAlloc::new();
let alloc_256:  EntityAlloc<Inst, AllocPolicy256>  = EntityAlloc::new();
let alloc_512:  EntityAlloc<Inst, AllocPolicy512>  = EntityAlloc::new();
let alloc_1024: EntityAlloc<Inst, AllocPolicy1024> = EntityAlloc::new();
let alloc_2048: EntityAlloc<Inst, AllocPolicy2048> = EntityAlloc::new();
let alloc_4096: EntityAlloc<Inst, AllocPolicy4096> = EntityAlloc::new();

let id_128  = alloc_128.allocate (Inst::new(10)); // PtrID<Inst, AllocPolicy128>
let id_256  = alloc_256.allocate (Inst::new(10)); // PtrID<Inst, AllocPolicy256>
let id_512  = alloc_512.allocate (Inst::new(10)); // PtrID<Inst, AllocPolicy512>
let id_1024 = alloc_1024.allocate(Inst::new(10)); // PtrID<Inst, AllocPolicy1024>
let id_2048 = alloc_2048.allocate(Inst::new(10)); // PtrID<Inst, AllocPolicy2048>
let id_4096 = alloc_4096.allocate(Inst::new(10)); // PtrID<Inst, AllocPolicy4096>

The policy on the ID helps prevent accidentally using an ID with an allocator of the wrong capacity.

Custom ID wrappers with #[entity_id]

This attribute generates a newtype wrapper around a backend ID (PtrID<Object, Policy> or IndexedID<Object, Policy>) bound to a fixed policy and, optionally, an allocator type alias.

Example:

// Pointer backend (default)
#[entity_id(InstID, policy = 256, allocator_type = InstAllocT, backend = ptr)]
#[derive(Debug, Clone, PartialEq, Eq)]
struct Inst { /* fields */ }

fn use_inst_id_ptr_backend() {
    // InstAllocT is a type alias for EntityAlloc<Inst, AllocPolicy256>
    let alloc_inst = InstAllocT::new();
    // Allocate raw backend ID then wrap
    let raw: PtrID<Inst, AllocPolicy256> = alloc_inst.allocate_ptr(Inst::new(42));
    let id = InstID::from(raw); // or InstID::from_backend(raw)
    let data: &Inst = id.deref_alloc(&alloc_inst);
    assert_eq!(data.opcode, 42);
}

// Index backend (safer, slower)
#[entity_id(InstIndexID, policy = 256, backend = index)]
#[derive(Debug, Clone, PartialEq, Eq)]
struct Inst2 { /* fields */ }

fn use_inst_id_index_backend() {
    let alloc: EntityAlloc<Inst2, AllocPolicy256> = EntityAlloc::new();
    let raw_index: IndexedID<Inst2, AllocPolicy256> = IndexedID::allocate_from(&alloc, Inst2 { /* init */ });
    let id = InstIndexID::from_backend(raw_index);
    let _data: &Inst2 = id.deref_alloc(&alloc);
}

Options:

• policy = NNN | PolicyNNN | AllocPolicyNNN — bind to a specific policy; NNN in [128, 4096].
• allocator_type = AliasName — emit a type alias for the allocator (type AliasName = EntityAlloc<Object, Policy>). Visibility follows the annotated type.
• backend = ptr | index — choose pointer or index ID backend (default: ptr).
• opaque — make the inner backend ID field crate-visible instead of public, reducing accidental exposure.

ID constraints

Library data structures rely on the IPoliciedID trait to describe "an ID tied to a particular object and allocator type." Raw PtrID<E, P>, IndexedID<E, P> and any #[entity_id] wrappers implement it, so you can use containers with any backend.

Note: Wrapper types intentionally do not expose allocation/free convenience methods; allocation stays at the raw layer (allocate_ptr, allocate_index or IEntityAllocID::allocate_from).

Containers

Built on IPoliciedID, the crate provides internally-mutable containers:

• EntityList<I> — doubly-linked list. Typical for instruction/basic-block lists. Internally mutable; no &mut alloc needed, but misuse can corrupt relationships.
• EntityRingList<I> — ring list. Useful for def-use sets; attach has no signals, detach does.

Note: In v0.2, container generics flipped from the object type ObjT to the constrained ID type I.

Safety notice

This crate uses unsafe code without formal verification. It is neither general-purpose nor guaranteed safe. Prefer slab unless you truly need these semantics.