arena_lang/
id.rs

1//! The typed handle into an arena.
2
3use core::cmp::Ordering;
4use core::fmt;
5use core::hash::{Hash, Hasher};
6use core::marker::PhantomData;
7
8/// A small, copyable, type-tagged handle to one value in an [`Arena`](crate::Arena).
9///
10/// An `Id<T>` is the stable way to refer to an allocated value: it stays valid for
11/// the life of the arena that issued it, and it is a single `u32` — four bytes,
12/// the same as a bare index — so passing one is no more expensive than passing an
13/// integer. Unlike a `&T`, it carries no borrow, so a tree of nodes can store ids
14/// pointing at one another without tangling the borrow checker — which is exactly
15/// why an AST or IR holds child handles rather than child references.
16///
17/// The `T` tag is compile-time only (it occupies no space): it stops an
18/// `Id<Expr>` from being passed where an `Id<Stmt>` is expected, so a handle can
19/// only ever index the arena that produced it. `Id<T>` is `Copy`, `Eq`, `Ord`, and
20/// `Hash` for **every** `T` — the tag never adds a bound — so it works as a map key
21/// regardless of what it points at.
22///
23/// Resolve a handle with [`Arena::get`](crate::Arena::get) /
24/// [`get_mut`](crate::Arena::get_mut); there is no public constructor, so an `Id`
25/// can only come from an [`Arena::alloc`](crate::Arena::alloc).
26///
27/// # Examples
28///
29/// ```
30/// use arena_lang::Arena;
31///
32/// let mut arena = Arena::new();
33/// let id = arena.alloc("node");
34///
35/// // The handle round-trips back to the value it named.
36/// assert_eq!(arena.get(id), Some(&"node"));
37///
38/// // It is Copy and four bytes wide, whatever it points at.
39/// let also = id;
40/// assert_eq!(id, also);
41/// assert_eq!(core::mem::size_of_val(&id), 4);
42/// ```
43pub struct Id<T> {
44    raw: u32,
45    /// Compile-time type tag. `fn() -> T` keeps `Id<T>` `Copy`, `Send`, and `Sync`
46    /// for any `T`, and covariant in `T`, without ever borrowing or owning a `T`.
47    marker: PhantomData<fn() -> T>,
48}
49
50impl<T> Id<T> {
51    /// Wraps a raw arena index. Internal: only an arena mints handles, so that the
52    /// type tag always matches the arena the handle indexes.
53    #[inline]
54    pub(crate) const fn new(raw: u32) -> Self {
55        Self {
56            raw,
57            marker: PhantomData,
58        }
59    }
60
61    /// Returns the raw arena index this handle wraps.
62    #[inline]
63    pub(crate) const fn raw(self) -> u32 {
64        self.raw
65    }
66}
67
68// The trait impls are written by hand rather than derived: a derive would bound
69// each impl on `T` (e.g. `T: Clone`), but a handle must be `Copy`, comparable, and
70// hashable for every `T`, since `T` is only a compile-time tag.
71
72impl<T> Clone for Id<T> {
73    #[inline]
74    fn clone(&self) -> Self {
75        *self
76    }
77}
78
79impl<T> Copy for Id<T> {}
80
81impl<T> PartialEq for Id<T> {
82    #[inline]
83    fn eq(&self, other: &Self) -> bool {
84        self.raw == other.raw
85    }
86}
87
88impl<T> Eq for Id<T> {}
89
90impl<T> PartialOrd for Id<T> {
91    #[inline]
92    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
93        Some(self.cmp(other))
94    }
95}
96
97impl<T> Ord for Id<T> {
98    #[inline]
99    fn cmp(&self, other: &Self) -> Ordering {
100        self.raw.cmp(&other.raw)
101    }
102}
103
104impl<T> Hash for Id<T> {
105    #[inline]
106    fn hash<H: Hasher>(&self, state: &mut H) {
107        self.raw.hash(state);
108    }
109}
110
111impl<T> fmt::Debug for Id<T> {
112    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
113        write!(f, "Id({})", self.raw)
114    }
115}
116
117#[cfg(test)]
118mod tests {
119    extern crate alloc;
120    use alloc::collections::BTreeSet;
121    use alloc::format;
122
123    use crate::Arena;
124
125    #[test]
126    fn test_id_traits_do_not_depend_on_the_tag() {
127        // A tag that is neither `Clone` nor `Eq` must not stop `Id` from being
128        // `Copy`, `Eq`, and `Debug` — the tag is compile-time only.
129        struct NotClone;
130        let mut arena = Arena::<NotClone>::new();
131        let id = arena.alloc(NotClone);
132        let copy = id; // Copy
133        assert_eq!(id, copy); // Eq
134        assert!(format!("{id:?}").starts_with("Id")); // Debug
135    }
136
137    #[test]
138    fn test_distinct_allocations_have_distinct_ids() {
139        let mut arena = Arena::new();
140        let ids: BTreeSet<_> = (0..16).map(|i| arena.alloc(i)).collect();
141        assert_eq!(ids.len(), 16); // all distinct, usable as ordered-set keys
142    }
143
144    #[test]
145    fn test_id_is_four_bytes_for_any_element() {
146        assert_eq!(core::mem::size_of::<crate::Id<u8>>(), 4);
147        assert_eq!(core::mem::size_of::<crate::Id<[u128; 4]>>(), 4);
148    }
149}
arena_lang/id.rs

arena_lang/
id.rs
