]> git.lizzy.rs Git - enumset.git/blob - enumset/src/lib.rs
Fix from_bits_safe.
[enumset.git] / enumset / src / lib.rs
1 #![no_std]
2 #![forbid(missing_docs)]
3
4 //! A library for defining enums that can be used in compact bit sets. It supports enums up to 128
5 //! variants, and has a macro to use these sets in constants.
6 //!
7 //! For serde support, enable the `serde` feature.
8 //!
9 //! # Defining enums for use with EnumSet
10 //!
11 //! Enums to be used with [`EnumSet`] should be defined using `#[derive(EnumSetType)]`:
12 //!
13 //! ```rust
14 //! # use enumset::*;
15 //! #[derive(EnumSetType, Debug)]
16 //! pub enum Enum {
17 //!    A, B, C, D, E, F, G,
18 //! }
19 //! ```
20 //!
21 //! # Working with EnumSets
22 //!
23 //! EnumSets can be constructed via [`EnumSet::new()`] like a normal set. In addition,
24 //! `#[derive(EnumSetType)]` creates operator overloads that allow you to create EnumSets like so:
25 //!
26 //! ```rust
27 //! # use enumset::*;
28 //! # #[derive(EnumSetType, Debug)] pub enum Enum { A, B, C, D, E, F, G }
29 //! let new_set = Enum::A | Enum::C | Enum::G;
30 //! assert_eq!(new_set.len(), 3);
31 //! ```
32 //!
33 //! All bitwise operations you would expect to work on bitsets also work on both EnumSets and
34 //! enums with `#[derive(EnumSetType)]`:
35 //! ```rust
36 //! # use enumset::*;
37 //! # #[derive(EnumSetType, Debug)] pub enum Enum { A, B, C, D, E, F, G }
38 //! // Intersection of sets
39 //! assert_eq!((Enum::A | Enum::B) & Enum::C, EnumSet::empty());
40 //! assert_eq!((Enum::A | Enum::B) & Enum::A, Enum::A);
41 //! assert_eq!(Enum::A & Enum::B, EnumSet::empty());
42 //!
43 //! // Symmetric difference of sets
44 //! assert_eq!((Enum::A | Enum::B) ^ (Enum::B | Enum::C), Enum::A | Enum::C);
45 //! assert_eq!(Enum::A ^ Enum::C, Enum::A | Enum::C);
46 //!
47 //! // Difference of sets
48 //! assert_eq!((Enum::A | Enum::B | Enum::C) - Enum::B, Enum::A | Enum::C);
49 //!
50 //! // Complement of sets
51 //! assert_eq!(!(Enum::E | Enum::G), Enum::A | Enum::B | Enum::C | Enum::D | Enum::F);
52 //! ```
53 //!
54 //! The [`enum_set!`] macro allows you to create EnumSets in constant contexts:
55 //!
56 //! ```rust
57 //! # use enumset::*;
58 //! # #[derive(EnumSetType, Debug)] pub enum Enum { A, B, C, D, E, F, G }
59 //! const CONST_SET: EnumSet<Enum> = enum_set!(Enum::A | Enum::B);
60 //! assert_eq!(CONST_SET, Enum::A | Enum::B);
61 //! ```
62 //!
63 //! Mutable operations on the [`EnumSet`] otherwise work basically as expected:
64 //!
65 //! ```rust
66 //! # use enumset::*;
67 //! # #[derive(EnumSetType, Debug)] pub enum Enum { A, B, C, D, E, F, G }
68 //! let mut set = EnumSet::new();
69 //! set.insert(Enum::A);
70 //! set.insert_all(Enum::E | Enum::G);
71 //! assert!(set.contains(Enum::A));
72 //! assert!(!set.contains(Enum::B));
73 //! assert_eq!(set, Enum::A | Enum::E | Enum::G);
74 //! ```
75
76 pub use enumset_derive::*;
77
78 use core::cmp::Ordering;
79 use core::fmt;
80 use core::fmt::{Debug, Formatter};
81 use core::hash::{Hash, Hasher};
82 use core::iter::FromIterator;
83 use core::ops::*;
84
85 use num_traits::*;
86
87 #[doc(hidden)]
88 /// Everything in this module is internal API and may change at any time.
89 pub mod internal {
90     use super::*;
91
92     /// A struct used to type check [`enum_set!`].
93     pub struct EnumSetSameTypeHack<'a, T: EnumSetType + 'static> {
94         pub unified: &'a [T],
95         pub enum_set: EnumSet<T>,
96     }
97
98     /// A reexport of core to allow our macros to be generic to std vs core.
99     pub use ::core as core_export;
100
101     /// A reexport of serde so there is no requirement to depend on serde.
102     #[cfg(feature = "serde")] pub use serde2 as serde;
103
104     /// The actual members of EnumSetType. Put here to avoid polluting global namespaces.
105     pub unsafe trait EnumSetTypePrivate {
106         type Repr: EnumSetTypeRepr;
107         const ALL_BITS: Self::Repr;
108         fn enum_into_u8(self) -> u8;
109         unsafe fn enum_from_u8(val: u8) -> Self;
110
111         #[cfg(feature = "serde")]
112         fn serialize<S: serde::Serializer>(set: EnumSet<Self>, ser: S) -> Result<S::Ok, S::Error>
113             where Self: EnumSetType;
114         #[cfg(feature = "serde")]
115         fn deserialize<'de, D: serde::Deserializer<'de>>(de: D) -> Result<EnumSet<Self>, D::Error>
116             where Self: EnumSetType;
117     }
118 }
119 use crate::internal::EnumSetTypePrivate;
120 #[cfg(feature = "serde")] use crate::internal::serde;
121 #[cfg(feature = "serde")] use crate::serde::{Serialize, Deserialize};
122
123 mod private {
124     use super::*;
125     pub trait EnumSetTypeRepr : PrimInt + FromPrimitive + WrappingSub + CheckedShl + Debug + Hash {
126         const WIDTH: u8;
127     }
128     macro_rules! prim {
129         ($name:ty, $width:expr) => {
130             impl EnumSetTypeRepr for $name {
131                 const WIDTH: u8 = $width;
132             }
133         }
134     }
135     prim!(u8  , 8  );
136     prim!(u16 , 16 );
137     prim!(u32 , 32 );
138     prim!(u64 , 64 );
139     prim!(u128, 128);
140 }
141 use crate::private::EnumSetTypeRepr;
142
143 /// The trait used to define enum types that may be used with [`EnumSet`].
144 ///
145 /// This trait should be implemented using `#[derive(EnumSetType)]`. Its internal structure is
146 /// not currently stable, and may change at any time.
147 ///
148 /// # Custom Derive
149 ///
150 /// The custom derive for [`EnumSetType`] automatically creates implementations of [`PartialEq`],
151 /// [`Sub`], [`BitAnd`], [`BitOr`], [`BitXor`], and [`Not`] allowing the enum to be used as
152 /// if it were an [`EnumSet`] in expressions. This can be disabled by adding an `#[enumset(no_ops)]`
153 /// annotation to the enum.
154 ///
155 /// The custom derive for `EnumSetType` automatically implements [`Copy`], [`Clone`], [`Eq`], and
156 /// [`PartialEq`] on the enum. These are required for the [`EnumSet`] to function.
157 ///
158 /// Any C-like enum is supported, as long as there are no more than 128 variants in the enum,
159 /// and no variant discriminator is larger than 127.
160 ///
161 /// # Examples
162 ///
163 /// Deriving a plain EnumSetType:
164 ///
165 /// ```rust
166 /// # use enumset::*;
167 /// #[derive(EnumSetType)]
168 /// pub enum Enum {
169 ///    A, B, C, D, E, F, G,
170 /// }
171 /// ```
172 ///
173 /// Deriving a sparse EnumSetType:
174 ///
175 /// ```rust
176 /// # use enumset::*;
177 /// #[derive(EnumSetType)]
178 /// pub enum SparseEnum {
179 ///    A = 10, B = 20, C = 30, D = 127,
180 /// }
181 /// ```
182 ///
183 /// Deriving an EnumSetType without adding ops:
184 ///
185 /// ```rust
186 /// # use enumset::*;
187 /// #[derive(EnumSetType)]
188 /// #[enumset(no_ops)]
189 /// pub enum NoOpsEnum {
190 ///    A, B, C, D, E, F, G,
191 /// }
192 /// ```
193 pub unsafe trait EnumSetType: Copy + Eq + EnumSetTypePrivate { }
194
195 /// An efficient set type for enums.
196 ///
197 /// It is implemented using a bitset stored using the smallest integer that can fit all bits
198 /// in the underlying enum.
199 ///
200 /// # Serialization
201 ///
202 /// By default, `EnumSet`s are serialized as an unsigned integer of the same width as used to store
203 /// it in memory.
204 ///
205 /// Unknown bits are ignored, and are simply dropped. To override this behavior, you can add a
206 /// `#[enumset(serialize_deny_unknown)]` annotation to your enum.
207 ///
208 /// You can add a `#[enumset(serialize_repr = "u8")]` annotation to your enum to manually set
209 /// the number width the `EnumSet` is serialized as. Only unsigned integer types may be used. This
210 /// can be used to avoid breaking changes in certain serialization formats (such as `bincode`).
211 ///
212 /// In addition, the `#[enumset(serialize_as_list)]` annotation causes the `EnumSet` to be
213 /// instead serialized as a list of enum variants. This requires your enum type implement
214 /// [`Serialize`] and [`Deserialize`].
215 #[derive(Copy, Clone, PartialEq, Eq)]
216 pub struct EnumSet<T : EnumSetType> {
217     #[doc(hidden)]
218     /// This is public due to the [`enum_set!`] macro.
219     /// This is **NOT** public API and may change at any time.
220     pub __enumset_underlying: T::Repr
221 }
222 impl <T : EnumSetType> EnumSet<T> {
223     fn mask(bit: u8) -> T::Repr {
224         Shl::<usize>::shl(T::Repr::one(), bit as usize)
225     }
226     fn has_bit(&self, bit: u8) -> bool {
227         let mask = Self::mask(bit);
228         self.__enumset_underlying & mask == mask
229     }
230     fn partial_bits(bits: u8) -> T::Repr {
231         T::Repr::one().checked_shl(bits.into())
232             .unwrap_or(T::Repr::zero())
233             .wrapping_sub(&T::Repr::one())
234     }
235
236     // Returns all bits valid for the enum
237     fn all_bits() -> T::Repr {
238         T::ALL_BITS
239     }
240
241     /// Creates an empty `EnumSet`.
242     pub fn new() -> Self {
243         EnumSet { __enumset_underlying: T::Repr::zero() }
244     }
245
246     /// Returns an `EnumSet` containing a single element.
247     pub fn only(t: T) -> Self {
248         EnumSet { __enumset_underlying: Self::mask(t.enum_into_u8()) }
249     }
250
251     /// Creates an empty `EnumSet`.
252     ///
253     /// This is an alias for [`EnumSet::new`].
254     pub fn empty() -> Self {
255         Self::new()
256     }
257
258     /// Returns an `EnumSet` containing all valid variants of the enum.
259     pub fn all() -> Self {
260         EnumSet { __enumset_underlying: Self::all_bits() }
261     }
262
263     /// Total number of bits used by this type. Note that the actual amount of space used is
264     /// rounded up to the next highest integer type (`u8`, `u16`, `u32`, `u64`, or `u128`).
265     ///
266     /// This is the same as [`EnumSet::variant_count`] except in enums with "sparse" variants.
267     /// (e.g. `enum Foo { A = 10, B = 20 }`)
268     pub fn bit_width() -> u8 {
269         T::Repr::WIDTH - T::ALL_BITS.leading_zeros() as u8
270     }
271
272     /// The number of valid variants that this type can contain.
273     ///
274     /// This is the same as [`EnumSet::bit_width`] except in enums with "sparse" variants.
275     /// (e.g. `enum Foo { A = 10, B = 20 }`)
276     pub fn variant_count() -> u8 {
277         T::ALL_BITS.count_ones() as u8
278     }
279
280     /// Returns the raw bits of this set.
281     pub fn to_bits(&self) -> u128 {
282         self.__enumset_underlying.to_u128()
283             .expect("Impossible: Bits cannot be to converted into i128?")
284     }
285
286     /// Constructs a bitset from raw bits.
287     ///
288     /// # Panics
289     /// If bits not in the enum are set.
290     pub fn from_bits(bits: u128) -> Self {
291         assert!((bits & !Self::all().to_bits()) == 0, "Bits not valid for the enum were set.");
292         EnumSet {
293             __enumset_underlying: T::Repr::from_u128(bits)
294                 .expect("Impossible: Valid bits too large to fit in repr?")
295         }
296     }
297
298     /// Constructs a bitset from raw bits, ignoring any unknown variants.
299     pub fn from_bits_safe(bits: u128) -> Self {
300         Self::from_bits(bits & Self::all().to_bits())
301     }
302
303     /// Returns the number of elements in this set.
304     pub fn len(&self) -> usize {
305         self.__enumset_underlying.count_ones() as usize
306     }
307     /// Returns `true` if the set contains no elements.
308     pub fn is_empty(&self) -> bool {
309         self.__enumset_underlying.is_zero()
310     }
311     /// Removes all elements from the set.
312     pub fn clear(&mut self) {
313         self.__enumset_underlying = T::Repr::zero()
314     }
315
316     /// Returns `true` if `self` has no elements in common with `other`. This is equivalent to
317     /// checking for an empty intersection.
318     pub fn is_disjoint(&self, other: Self) -> bool {
319         (*self & other).is_empty()
320     }
321     /// Returns `true` if the set is a superset of another, i.e., `self` contains at least all the
322     /// values in `other`.
323     pub fn is_superset(&self, other: Self) -> bool {
324         (*self & other).__enumset_underlying == other.__enumset_underlying
325     }
326     /// Returns `true` if the set is a subset of another, i.e., `other` contains at least all
327     /// the values in `self`.
328     pub fn is_subset(&self, other: Self) -> bool {
329         other.is_superset(*self)
330     }
331
332     /// Returns a set containing any elements present in either set.
333     pub fn union(&self, other: Self) -> Self {
334         EnumSet { __enumset_underlying: self.__enumset_underlying | other.__enumset_underlying }
335     }
336     /// Returns a set containing every element present in both sets.
337     pub fn intersection(&self, other: Self) -> Self {
338         EnumSet { __enumset_underlying: self.__enumset_underlying & other.__enumset_underlying }
339     }
340     /// Returns a set containing element present in `self` but not in `other`.
341     pub fn difference(&self, other: Self) -> Self {
342         EnumSet { __enumset_underlying: self.__enumset_underlying & !other.__enumset_underlying }
343     }
344     /// Returns a set containing every element present in either `self` or `other`, but is not
345     /// present in both.
346     pub fn symmetrical_difference(&self, other: Self) -> Self {
347         EnumSet { __enumset_underlying: self.__enumset_underlying ^ other.__enumset_underlying }
348     }
349     /// Returns a set containing all enum variants not in this set.
350     pub fn complement(&self) -> Self {
351         EnumSet { __enumset_underlying: !self.__enumset_underlying & Self::all_bits() }
352     }
353
354     /// Checks whether this set contains a value.
355     pub fn contains(&self, value: T) -> bool {
356         self.has_bit(value.enum_into_u8())
357     }
358
359     /// Adds a value to this set.
360     ///
361     /// If the set did not have this value present, `true` is returned.
362     ///
363     /// If the set did have this value present, `false` is returned.
364     pub fn insert(&mut self, value: T) -> bool {
365         let contains = !self.contains(value);
366         self.__enumset_underlying = self.__enumset_underlying | Self::mask(value.enum_into_u8());
367         contains
368     }
369     /// Removes a value from this set. Returns whether the value was present in the set.
370     pub fn remove(&mut self, value: T) -> bool {
371         let contains = self.contains(value);
372         self.__enumset_underlying = self.__enumset_underlying & !Self::mask(value.enum_into_u8());
373         contains
374     }
375
376     /// Adds all elements in another set to this one.
377     pub fn insert_all(&mut self, other: Self) {
378         self.__enumset_underlying = self.__enumset_underlying | other.__enumset_underlying
379     }
380     /// Removes all values in another set from this one.
381     pub fn remove_all(&mut self, other: Self) {
382         self.__enumset_underlying = self.__enumset_underlying & !other.__enumset_underlying
383     }
384
385     /// Creates an iterator over the values in this set.
386     pub fn iter(&self) -> EnumSetIter<T> {
387         EnumSetIter(*self, 0)
388     }
389 }
390
391 impl <T: EnumSetType> Default for EnumSet<T> {
392     /// Returns an empty set.
393     fn default() -> Self {
394         Self::new()
395     }
396 }
397
398 impl <T : EnumSetType> IntoIterator for EnumSet<T> {
399     type Item = T;
400     type IntoIter = EnumSetIter<T>;
401
402     fn into_iter(self) -> Self::IntoIter {
403         self.iter()
404     }
405 }
406
407 impl <T : EnumSetType, O: Into<EnumSet<T>>> Sub<O> for EnumSet<T> {
408     type Output = Self;
409     fn sub(self, other: O) -> Self::Output {
410         self.difference(other.into())
411     }
412 }
413 impl <T : EnumSetType, O: Into<EnumSet<T>>> BitAnd<O> for EnumSet<T> {
414     type Output = Self;
415     fn bitand(self, other: O) -> Self::Output {
416         self.intersection(other.into())
417     }
418 }
419 impl <T : EnumSetType, O: Into<EnumSet<T>>> BitOr<O> for EnumSet<T> {
420     type Output = Self;
421     fn bitor(self, other: O) -> Self::Output {
422         self.union(other.into())
423     }
424 }
425 impl <T : EnumSetType, O: Into<EnumSet<T>>> BitXor<O> for EnumSet<T> {
426     type Output = Self;
427     fn bitxor(self, other: O) -> Self::Output {
428         self.symmetrical_difference(other.into())
429     }
430 }
431
432 impl <T : EnumSetType, O: Into<EnumSet<T>>> SubAssign<O> for EnumSet<T> {
433     fn sub_assign(&mut self, rhs: O) {
434         *self = *self - rhs;
435     }
436 }
437 impl <T : EnumSetType, O: Into<EnumSet<T>>> BitAndAssign<O> for EnumSet<T> {
438     fn bitand_assign(&mut self, rhs: O) {
439         *self = *self & rhs;
440     }
441 }
442 impl <T : EnumSetType, O: Into<EnumSet<T>>> BitOrAssign<O> for EnumSet<T> {
443     fn bitor_assign(&mut self, rhs: O) {
444         *self = *self | rhs;
445     }
446 }
447 impl <T : EnumSetType, O: Into<EnumSet<T>>> BitXorAssign<O> for EnumSet<T> {
448     fn bitxor_assign(&mut self, rhs: O) {
449         *self = *self ^ rhs;
450     }
451 }
452
453 impl <T : EnumSetType> Not for EnumSet<T> {
454     type Output = Self;
455     fn not(self) -> Self::Output {
456         self.complement()
457     }
458 }
459
460 impl <T : EnumSetType> From<T> for EnumSet<T> {
461     fn from(t: T) -> Self {
462         EnumSet::only(t)
463     }
464 }
465
466 impl <T : EnumSetType> PartialEq<T> for EnumSet<T> {
467     fn eq(&self, other: &T) -> bool {
468         self.__enumset_underlying == EnumSet::<T>::mask(other.enum_into_u8())
469     }
470 }
471 impl <T : EnumSetType + Debug> Debug for EnumSet<T> {
472     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
473         let mut is_first = true;
474         f.write_str("EnumSet(")?;
475         for v in self.iter() {
476             if !is_first { f.write_str(" | ")?; }
477             is_first = false;
478             v.fmt(f)?;
479         }
480         f.write_str(")")?;
481         Ok(())
482     }
483 }
484
485 impl <T: EnumSetType> Hash for EnumSet<T> {
486     fn hash<H: Hasher>(&self, state: &mut H) {
487         self.__enumset_underlying.hash(state)
488     }
489 }
490 impl <T: EnumSetType> PartialOrd for EnumSet<T> {
491     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
492         self.__enumset_underlying.partial_cmp(&other.__enumset_underlying)
493     }
494 }
495 impl <T: EnumSetType> Ord for EnumSet<T> {
496     fn cmp(&self, other: &Self) -> Ordering {
497         self.__enumset_underlying.cmp(&other.__enumset_underlying)
498     }
499 }
500
501 #[cfg(feature = "serde")]
502 impl <T : EnumSetType> Serialize for EnumSet<T> {
503     fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
504         T::serialize(*self, serializer)
505     }
506 }
507
508 #[cfg(feature = "serde")]
509 impl <'de, T : EnumSetType> Deserialize<'de> for EnumSet<T> {
510     fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
511         T::deserialize(deserializer)
512     }
513 }
514
515 /// The iterator used by [`EnumSet`]s.
516 #[derive(Clone, Debug)]
517 pub struct EnumSetIter<T : EnumSetType>(EnumSet<T>, u8);
518 impl <T : EnumSetType> Iterator for EnumSetIter<T> {
519     type Item = T;
520
521     fn next(&mut self) -> Option<Self::Item> {
522         while self.1 < EnumSet::<T>::bit_width() {
523             let bit = self.1;
524             self.1 += 1;
525             if self.0.has_bit(bit) {
526                 return unsafe { Some(T::enum_from_u8(bit)) }
527             }
528         }
529         None
530     }
531     fn size_hint(&self) -> (usize, Option<usize>) {
532         let left_mask = !EnumSet::<T>::partial_bits(self.1);
533         let left = (self.0.__enumset_underlying & left_mask).count_ones() as usize;
534         (left, Some(left))
535     }
536 }
537
538 impl<T: EnumSetType> Extend<T> for EnumSet<T> {
539     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
540         iter.into_iter().for_each(|v| { self.insert(v); });
541     }
542 }
543
544 impl<T: EnumSetType> FromIterator<T> for EnumSet<T> {
545     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
546         let mut set = EnumSet::default();
547         set.extend(iter);
548         set
549     }
550 }
551
552 /// Creates a EnumSet literal, which can be used in const contexts.
553 ///
554 /// The syntax used is `enum_set!(Type::A | Type::B | Type::C)`. Each variant must be of the same
555 /// type, or a error will occur at compile-time.
556 ///
557 /// # Examples
558 ///
559 /// ```rust
560 /// # use enumset::*;
561 /// # #[derive(EnumSetType, Debug)] enum Enum { A, B, C }
562 /// const CONST_SET: EnumSet<Enum> = enum_set!(Enum::A | Enum::B);
563 /// assert_eq!(CONST_SET, Enum::A | Enum::B);
564 /// ```
565 ///
566 /// This macro is strongly typed. For example, the following will not compile:
567 ///
568 /// ```compile_fail
569 /// # use enumset::*;
570 /// # #[derive(EnumSetType, Debug)] enum Enum { A, B, C }
571 /// # #[derive(EnumSetType, Debug)] enum Enum2 { A, B, C }
572 /// let type_error = enum_set!(Enum::A | Enum2::B);
573 /// ```
574 #[macro_export]
575 macro_rules! enum_set {
576     () => {
577         $crate::EnumSet { __enumset_underlying: 0 }
578     };
579     ($($value:path)|* $(|)*) => {
580         $crate::internal::EnumSetSameTypeHack {
581             unified: &[$($value,)*],
582             enum_set: $crate::EnumSet {
583                 __enumset_underlying: 0 $(| (1 << ($value as u8)))*
584             },
585         }.enum_set
586     };
587 }