Skip to main content

prjcombine_entity/
id.rs

1//! ID types.
2use core::marker::PhantomData;
3use core::ops::{AddAssign, Sub, SubAssign};
4use core::{hash::Hash, ops::Add};
5
6use std::{
7    fmt::{Debug, Display},
8    num::NonZero,
9};
10
11#[cfg(feature = "bincode")]
12use bincode::{BorrowDecode, Decode, Encode};
13
14/// Implemented by types that can be used as IDs in `prjcombine_entity` datastructures.
15///
16/// For new code, you use one of [`EntityIdU8`], [`EntityIdU16`], or [`EntityIdU32`],
17/// as appropriate.
18pub trait EntityId:
19    Debug + Copy + Clone + Send + Sync + Eq + PartialEq + Ord + PartialOrd + Hash
20{
21    fn from_idx(idx: usize) -> Self;
22    fn to_idx(self) -> usize;
23}
24
25pub trait EntityIdArith:
26    EntityId
27    + Add<usize, Output = Self>
28    + AddAssign<usize>
29    + Sub<usize, Output = Self>
30    + SubAssign<usize>
31    + Add<isize, Output = Self>
32    + AddAssign<isize>
33    + Sub<isize, Output = Self>
34    + SubAssign<isize>
35    + Add<i32, Output = Self>
36    + AddAssign<i32>
37    + Sub<i32, Output = Self>
38    + SubAssign<i32>
39    + Sub<Self, Output = isize>
40{
41    fn range_until(self, other: Self) -> EntityRange<Self> {
42        EntityRange::new(self.to_idx(), other.to_idx())
43    }
44
45    fn range_until_inclusive(self, other: Self) -> EntityRange<Self> {
46        self.range_until(other + 1)
47    }
48
49    fn range_around(self, down: usize, up: usize) -> EntityRange<Self> {
50        (self - down).range_until(self + up)
51    }
52
53    fn range_up(self, len: usize) -> EntityRange<Self> {
54        self.range_around(0, len)
55    }
56
57    fn range_down(self, len: usize) -> EntityRange<Self> {
58        self.range_around(len, 0)
59    }
60}
61
62pub trait EntityDelta: Copy {
63    fn add_to(self, index: usize) -> usize;
64    fn sub_from(self, index: usize) -> usize;
65}
66
67impl EntityDelta for usize {
68    fn add_to(self, index: usize) -> usize {
69        index + self
70    }
71
72    fn sub_from(self, index: usize) -> usize {
73        index - self
74    }
75}
76
77impl EntityDelta for isize {
78    fn add_to(self, index: usize) -> usize {
79        index.checked_add_signed(self).unwrap()
80    }
81
82    fn sub_from(self, index: usize) -> usize {
83        index.checked_sub_signed(self).unwrap()
84    }
85}
86
87impl EntityDelta for i32 {
88    fn add_to(self, index: usize) -> usize {
89        index
90            .checked_add_signed(isize::try_from(self).unwrap())
91            .unwrap()
92    }
93
94    fn sub_from(self, index: usize) -> usize {
95        index
96            .checked_sub_signed(isize::try_from(self).unwrap())
97            .unwrap()
98    }
99}
100
101/// Marker for types usable as ID tag types.
102///
103/// Types that implement this trait can be used as the `Tag` for [`EntityIdU8`] and similar types.
104pub trait EntityTag {
105    /// The prefix that should be shown before the actual value of the id, when an id type is
106    /// printed with either [`Debug`] or [`Display`].
107    const PREFIX: &'static str = "ID";
108}
109
110/// Marker for tag types for which arithmetic makes sense.
111///
112/// ```
113/// # use prjcombine_entity::id::{EntityId, EntityTag, EntityTagArith, EntityIdU16};
114/// struct RowTag;
115/// type RowId = EntityIdU16<RowTag>;
116/// impl EntityTag for RowTag {
117///     const PREFIX: &'static str = "X";
118/// }
119/// impl EntityTagArith for RowTag {}
120///
121/// let begin = RowId::from_idx(21);
122/// let end = RowId::from_idx(37);
123/// assert_eq!(end - begin, 16);
124/// assert_eq!(begin + 16, end);
125/// ```
126pub trait EntityTagArith: EntityTag {}
127
128// HORRIBLE HACK ALERT: we want `EntityIdU*` to be `StructuralEq`, so that we can match on constants
129// of that type.  However, the only way to get it is deriving `Eq`, which introduces a where-bound
130// on `Tag: Eq`, which we do not want.  Therefore, `EntityIdU*` are actually type aliases which
131// wrap the parameter in `PhantomData` (which is always `Eq` and `StructuralEq`) and pass it into
132// the inner type, which has derived `Eq`.
133
134macro_rules! make_id {
135    ($ty:ident, $inner:ident, $intty:ident) => {
136        #[doc(hidden)]
137        #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
138        pub struct $inner<Tag>(NonZero<$intty>, PhantomData<fn(Tag) -> Tag>);
139
140        #[doc = concat!("A `", stringify!($intty), "`-sized id type.")]
141        ///
142        /// The `Tag` generic parameter allows distinguishing IDs that are semantically of a different type.
143        ///
144        /// The `Tag` must implement [`EntityTag`]. While implementing that trait, you may also
145        /// specify how the IDs with that tag should be displayed.
146        ///
147        /// ## Formatting
148        ///
149        /// When formatting the ID with either the [`Debug`] (`{:?}`) or [`Display`] (`{}`)
150        /// specifier, the numeric value will be prefixed by [`EntityTag::PREFIX`]. However, this
151        /// can be suppressed by using the `{:#}` format specifier, i.e. [`Display`] with the
152        /// alternate flag set.
153        ///
154        /// ```
155        /// # use prjcombine_entity::id::{EntityId, EntityTag, EntityIdU16};
156        /// struct ChipTag;
157        /// type ChipId = EntityIdU16<ChipTag>;
158        /// impl EntityTag for ChipTag {
159        ///     const PREFIX: &'static str = "CHIP";
160        /// }
161        ///
162        /// let n = ChipId::from_idx(3);
163        /// assert_eq!(format!("{}", n), "CHIP3");
164        /// assert_eq!(format!("{:?}", n), "CHIP3");
165        /// assert_eq!(format!("{:#}", n), "3");
166        /// ```
167        pub type $ty<Tag> = $inner<PhantomData<Tag>>;
168
169        impl<Tag> $ty<Tag> {
170            pub const fn from_idx_const(idx: usize) -> Self {
171                assert!(idx < $intty::MAX as usize);
172                let idx = (idx + 1) as $intty;
173                let idx = NonZero::new(idx).unwrap();
174                Self(idx, PhantomData)
175            }
176
177            pub const fn to_idx_const(self) -> usize {
178                (self.0.get() - 1) as usize
179            }
180        }
181
182        impl<Tag: EntityTag> EntityId for $ty<Tag> {
183            fn from_idx(idx: usize) -> Self {
184                let idx = $intty::try_from(idx.checked_add(1).unwrap()).unwrap();
185                let idx = NonZero::new(idx).unwrap();
186                Self(idx, PhantomData)
187            }
188
189            fn to_idx(self) -> usize {
190                let idx = self.0.get() - 1;
191                idx.try_into().unwrap()
192            }
193        }
194
195        impl<Tag: EntityTag> Debug for $ty<Tag> {
196            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
197                write!(f, "{}{}", Tag::PREFIX, self.to_idx())
198            }
199        }
200
201        impl<Tag: EntityTag> Display for $ty<Tag> {
202            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
203                if f.alternate() {
204                    write!(f, "{}", self.to_idx())
205                } else {
206                    write!(f, "{}{}", Tag::PREFIX, self.to_idx())
207                }
208            }
209        }
210
211        #[cfg(feature = "bincode")]
212        impl<Tag> Encode for $ty<Tag> {
213            fn encode<E: bincode::enc::Encoder>(
214                &self,
215                encoder: &mut E,
216            ) -> Result<(), bincode::error::EncodeError> {
217                let idx = self.0.get() - 1;
218                idx.encode(encoder)
219            }
220        }
221
222        #[cfg(feature = "bincode")]
223        impl<Tag, Context> Decode<Context> for $ty<Tag> {
224            fn decode<D: bincode::de::Decoder<Context = Context>>(
225                decoder: &mut D,
226            ) -> Result<Self, bincode::error::DecodeError> {
227                let idx = $intty::decode(decoder)?;
228                let idx = idx.checked_add(1).unwrap();
229                let idx = NonZero::new(idx).unwrap();
230                Ok(Self(idx, PhantomData))
231            }
232        }
233
234        #[cfg(feature = "bincode")]
235        impl<'de, Tag, Context> BorrowDecode<'de, Context> for $ty<Tag> {
236            fn borrow_decode<D: bincode::de::BorrowDecoder<'de, Context = Context>>(
237                decoder: &mut D,
238            ) -> Result<Self, bincode::error::DecodeError> {
239                let idx = $intty::borrow_decode(decoder)?;
240                let idx = idx.checked_add(1).unwrap();
241                let idx = NonZero::new(idx).unwrap();
242                Ok(Self(idx, PhantomData))
243            }
244        }
245
246        impl<Tag: EntityTagArith, Delta: EntityDelta> core::ops::Add<Delta> for $ty<Tag> {
247            type Output = Self;
248            fn add(self, x: Delta) -> Self {
249                use $crate::EntityId;
250                Self::from_idx(x.add_to(self.to_idx()))
251            }
252        }
253
254        impl<Tag: EntityTagArith, Delta: EntityDelta> core::ops::AddAssign<Delta> for $ty<Tag> {
255            fn add_assign(&mut self, x: Delta) {
256                *self = *self + x;
257            }
258        }
259
260        impl<Tag: EntityTagArith, Delta: EntityDelta> core::ops::Sub<Delta> for $ty<Tag> {
261            type Output = Self;
262            fn sub(self, x: Delta) -> Self {
263                use $crate::EntityId;
264                Self::from_idx(x.sub_from(self.to_idx()))
265            }
266        }
267
268        impl<Tag: EntityTagArith, Delta: EntityDelta> core::ops::SubAssign<Delta> for $ty<Tag> {
269            fn sub_assign(&mut self, x: Delta) {
270                *self = *self - x;
271            }
272        }
273
274        impl<Tag: EntityTagArith> core::ops::Sub<Self> for $ty<Tag> {
275            type Output = isize;
276            fn sub(self, x: Self) -> isize {
277                use $crate::EntityId;
278                self.to_idx() as isize - x.to_idx() as isize
279            }
280        }
281
282        impl<Tag: EntityTagArith> EntityIdArith for $ty<Tag> {}
283    };
284}
285
286make_id!(EntityIdU8, EntityIdU8Inner, u8);
287make_id!(EntityIdU16, EntityIdU16Inner, u16);
288make_id!(EntityIdU32, EntityIdU32Inner, u32);
289
290#[doc(hidden)]
291#[macro_export]
292macro_rules! __entity_id_idopt {
293    ($tag:ident, arith) => {
294        impl $crate::id::EntityTagArith for $tag {}
295    };
296    ($tag:ident, ) => {};
297}
298
299#[doc(hidden)]
300#[macro_export]
301macro_rules! __entity_id_tagopt {
302    ($vis:vis $tag:ident, tag) => {
303        $vis struct $tag;
304    };
305    ($vis:vis $tag:ident, ) => {};
306}
307
308#[macro_export]
309macro_rules! entity_id_u8 {
310    ($vis:vis $ty:ident $($idopt:ident)*, $tag:ident $($tagopt:ident)*, $prefix:literal) => {
311        $crate::__entity_id_idopt!($tag, $($idopt)*);
312        $crate::__entity_id_tagopt!($vis $tag, $($tagopt)*);
313        impl $crate::id::EntityTag for $tag {
314            const PREFIX: &'static str = $prefix;
315        }
316        $vis type $ty = $crate::id::EntityIdU8<$tag>;
317    };
318}
319
320#[macro_export]
321macro_rules! entity_id_u16 {
322    ($vis:vis $ty:ident $($idopt:ident)*, $tag:ident $($tagopt:ident)*, $prefix:literal) => {
323        $crate::__entity_id_idopt!($tag, $($idopt)*);
324        $crate::__entity_id_tagopt!($vis $tag, $($tagopt)*);
325        impl $crate::id::EntityTag for $tag {
326            const PREFIX: &'static str = $prefix;
327        }
328        $vis type $ty = $crate::id::EntityIdU16<$tag>;
329    };
330}
331
332#[macro_export]
333macro_rules! entity_id_u32 {
334    ($vis:vis $ty:ident $($idopt:ident)*, $tag:ident $($tagopt:ident)*, $prefix:literal) => {
335        $crate::__entity_id_idopt!($tag, $($idopt)*);
336        $crate::__entity_id_tagopt!($vis $tag, $($tagopt)*);
337        impl $crate::id::EntityTag for $tag {
338            const PREFIX: &'static str = $prefix;
339        }
340        $vis type $ty = $crate::id::EntityIdU32<$tag>;
341    };
342}
343
344// range
345
346/// A range of IDs.
347#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
348#[cfg_attr(feature = "bincode", derive(Encode, Decode))]
349pub struct EntityRange<I: EntityId> {
350    start: I,
351    end: I,
352}
353
354impl<I: EntityId> EntityRange<I> {
355    /// Construct the range of IDs corresponding to `start..end`.
356    pub fn new(start: usize, end: usize) -> Self {
357        assert!(start <= end);
358        Self {
359            start: I::from_idx(start),
360            end: I::from_idx(end),
361        }
362    }
363
364    pub fn len(self) -> usize {
365        self.end.to_idx() - self.start.to_idx()
366    }
367
368    pub fn is_empty(self) -> bool {
369        self.end == self.start
370    }
371
372    pub fn map<T>(
373        self,
374        f: impl FnMut(I) -> T,
375    ) -> impl DoubleEndedIterator<Item = T> + ExactSizeIterator<Item = T> {
376        self.into_iter().map(f)
377    }
378
379    pub fn rev(self) -> impl DoubleEndedIterator<Item = I> + ExactSizeIterator<Item = I> {
380        self.into_iter().rev()
381    }
382
383    pub fn filter(self, f: impl FnMut(&I) -> bool) -> impl DoubleEndedIterator<Item = I> {
384        self.into_iter().filter(f)
385    }
386
387    /// Returns the lower bound of this range, even if it is empty.
388    pub fn start(self) -> I {
389        self.start
390    }
391
392    /// Returns the upper bound of this range, even if it is empty.
393    ///
394    /// In other words, returns the ID that immediately follows this range.
395    pub fn end(self) -> I {
396        self.end
397    }
398
399    /// Returns the first ID in the range, or `None` if the range is empty.
400    pub fn first(self) -> Option<I> {
401        if self.start == self.end {
402            None
403        } else {
404            Some(self.start)
405        }
406    }
407
408    /// Returns the last ID in the range, or `None` if the range is empty.
409    pub fn last(self) -> Option<I> {
410        if self.start == self.end {
411            None
412        } else {
413            Some(I::from_idx(self.end.to_idx() - 1))
414        }
415    }
416
417    /// Return `self[idx]`, conceptually.
418    ///
419    /// Note that we cannot actually implement the [`Index`][std::ops::Index] trait, because
420    /// it requires us to return a reference which we cannot materialize.
421    pub fn index(self, idx: usize) -> I {
422        assert!(idx < self.len());
423        I::from_idx(self.start.to_idx() + idx)
424    }
425
426    /// Return the position of `id` in this range, if present.
427    pub fn index_of(&self, id: I) -> Option<usize> {
428        if id.to_idx() < self.start.to_idx() || id.to_idx() >= self.end.to_idx() {
429            None
430        } else {
431            Some(id.to_idx() - self.start.to_idx())
432        }
433    }
434
435    pub fn contains(&self, id: I) -> bool {
436        self.index_of(id).is_some()
437    }
438}
439
440impl<I: EntityId> IntoIterator for EntityRange<I> {
441    type Item = I;
442
443    type IntoIter = EntityRangeIter<I>;
444
445    fn into_iter(self) -> Self::IntoIter {
446        EntityRangeIter {
447            start: self.start.to_idx(),
448            end: self.end.to_idx(),
449            ids: PhantomData,
450        }
451    }
452}
453
454impl<I: EntityId + Display> std::fmt::Display for EntityRange<I> {
455    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
456        write!(f, "{s}..{e}", s = self.start, e = self.end)
457    }
458}
459
460// iterator
461
462/// An iterator over an [`EntityRange`].
463#[derive(Clone, Debug)]
464pub struct EntityRangeIter<I: EntityId> {
465    start: usize,
466    end: usize,
467    ids: PhantomData<I>,
468}
469
470impl<I: EntityId> Iterator for EntityRangeIter<I> {
471    type Item = I;
472    fn next(&mut self) -> Option<I> {
473        if self.start == self.end {
474            None
475        } else {
476            let res = I::from_idx(self.start);
477            self.start += 1;
478            Some(res)
479        }
480    }
481}
482
483impl<I: EntityId> DoubleEndedIterator for EntityRangeIter<I> {
484    fn next_back(&mut self) -> Option<I> {
485        if self.start == self.end {
486            None
487        } else {
488            self.end -= 1;
489            Some(I::from_idx(self.end))
490        }
491    }
492}
493
494impl<I: EntityId> ExactSizeIterator for EntityRangeIter<I> {
495    fn len(&self) -> usize {
496        self.end - self.start
497    }
498}
499
500// static range
501
502/// A range of IDs materialized at compile-time.
503///
504/// The purpose of this type is to support indexing with the `[_]` operator, whether rustc likes it
505/// or not. Internally, this is done by preparing an array which lists all the IDs in the range, so
506/// that we may freely return references to it.
507#[derive(Copy, Clone, Debug)]
508pub struct EntityStaticRange<I: EntityId, const N: usize> {
509    data: [I; N],
510}
511
512macro_rules! impl_static_range {
513    ($ty:ident) => {
514        impl<T: EntityTag, const N: usize> EntityStaticRange<$ty<T>, N> {
515            pub const fn new_const(base: usize) -> Self {
516                let mut data = [$ty::from_idx_const(0); N];
517                let mut i = 0;
518                while i < N {
519                    data[i] = $ty::from_idx_const(base + i);
520                    i += 1;
521                }
522                Self { data }
523            }
524        }
525    };
526}
527
528impl_static_range!(EntityIdU8);
529impl_static_range!(EntityIdU16);
530impl_static_range!(EntityIdU32);
531
532impl<I: EntityId, const N: usize> EntityStaticRange<I, N> {
533    /// Returns `self[idx]`, but available in a `const` context.
534    pub const fn index_const(&self, idx: usize) -> I {
535        self.data[idx]
536    }
537
538    /// Return the position of `id` in this range, if present.
539    ///
540    /// This is done in `O(1)` time, without scanning through the materialized array.
541    pub fn index_of(&self, id: I) -> Option<usize> {
542        let base = *self.data.first()?;
543        if id.to_idx() < base.to_idx() {
544            None
545        } else {
546            let res = id.to_idx() - base.to_idx();
547            if res >= N { None } else { Some(res) }
548        }
549    }
550
551    pub fn contains(&self, id: I) -> bool {
552        self.index_of(id).is_some()
553    }
554}
555
556impl<I: EntityId, const N: usize> core::ops::Deref for EntityStaticRange<I, N> {
557    type Target = [I; N];
558
559    fn deref(&self) -> &Self::Target {
560        &self.data
561    }
562}
563
564impl<I: EntityId, const N: usize> IntoIterator for EntityStaticRange<I, N> {
565    type Item = I;
566
567    type IntoIter = core::array::IntoIter<I, N>;
568
569    fn into_iter(self) -> Self::IntoIter {
570        self.data.into_iter()
571    }
572}