btree-indexmap 1.0.0

//! Internal utilities shared by the map and set implementations.

/// Reinterprets a slice of `(T, ())` pairs as a slice of `T`.
///
/// This is used by [`BTreeIndexSet`](crate::BTreeIndexSet) and
/// [`BTreeIndexMultiSet`](crate::BTreeIndexMultiSet), which are implemented
/// as thin wrappers around [`BTreeIndexMap<T, ()>`](crate::BTreeIndexMap)
/// and [`BTreeIndexMultiMap<T, ()>`](crate::BTreeIndexMultiMap)
/// respectively, to expose their entries as `&[T]` without allocating or
/// copying.
///
/// # Safety
///
/// `()` is a zero-sized type with an alignment of `1`. This function
/// compiles only if, for the concrete `T` it gets instantiated with,
/// `size_of::<(T, ())>() == size_of::<T>()` (and likewise for alignment).
/// Given that `()` itself takes up no space, an equal size proves that the
/// tuple has no room left for padding: the `T` field must occupy the
/// tuple's *entire* representation, starting at offset `0`. In other
/// words, whenever the assertions below hold, `(T, ())` and `T` are
/// necessarily byte-for-byte identical, so a slice of one can be
/// reinterpreted as a slice of the other.
///
/// Note that this isn't merely assumed: the equality is checked at compile
/// time for the actual, monomorphized `T`. If a future Rust compiler were
/// to ever pick a different layout for `(T, ())` (e.g. by inserting
/// padding), this function would fail to compile instead of silently
/// becoming unsound.
pub(crate) fn entries_as_slice<T>(entries: &[(T, ())]) -> &[T] {
	const {
		assert!(size_of::<(T, ())>() == size_of::<T>());
		assert!(align_of::<(T, ())>() == align_of::<T>());
	}

	// SAFETY: see the reasoning above. The compile-time assertions prove
	// that `(T, ())` and `T` have identical size, alignment and layout, so
	// a `&[(T, ())]` can be soundly reinterpreted as a `&[T]` of the same
	// length.
	unsafe { std::mem::transmute::<&[(T, ())], &[T]>(entries) }
}

#[cfg(test)]
mod tests {
	use super::entries_as_slice;

	#[test]
	fn entries_as_slice_empty() {
		let entries: [(i32, ()); 0] = [];
		assert_eq!(entries_as_slice(&entries), &[] as &[i32]);
	}

	#[test]
	fn entries_as_slice_primitive() {
		let entries = [(1i32, ()), (2i32, ()), (3i32, ())];
		assert_eq!(entries_as_slice(&entries), [1, 2, 3]);
	}

	#[test]
	fn entries_as_slice_str_ref() {
		let entries = [("a", ()), ("b", ())];
		assert_eq!(entries_as_slice(&entries), ["a", "b"]);
	}

	#[test]
	fn entries_as_slice_zero_sized_t() {
		// `T` itself is zero-sized here: `(T, ())` is then also zero-sized,
		// and the transmute must still be sound.
		let entries = [((), ()), ((), ())];
		assert_eq!(entries_as_slice(&entries), [(), ()]);
	}

	#[test]
	fn entries_as_slice_over_aligned_t() {
		#[derive(Debug, PartialEq, Eq, Clone, Copy)]
		#[repr(align(16))]
		struct OverAligned(u8);

		let entries = [(OverAligned(1), ()), (OverAligned(2), ())];
		assert_eq!(entries_as_slice(&entries), [OverAligned(1), OverAligned(2)]);
	}
}