use core::mem::{self, MaybeUninit};
use crate::layout::{Endian, Field, Kind, Layout, Spec, Valid, load, max_value};
pub const fn sample<T: crate::Pun>() -> MaybeUninit<T> {
assert!(T::LAYOUT.is_inhabited(), "a type without values has no sample");
let mut value = MaybeUninit::<T>::uninit();
unsafe { write(&T::LAYOUT, value.as_mut_ptr().cast()) };
value
}
const unsafe fn write(layout: &Layout, ptr: *mut u8) {
unsafe {
match layout.kind {
Kind::Scalar(spec) => match spec.valid {
Valid::Uninit => {}
Valid::Any => store(ptr, spec.size, spec.endian, 0),
Valid::In(ranges) => store(ptr, spec.size, spec.endian, ranges[0].0),
},
Kind::Array(elem, len) => {
if len == 0 || elem.size == 0 {
return;
}
write(elem, ptr);
let mut done = 1;
while done < len {
let count = if done < len - done { done } else { len - done };
core::ptr::copy_nonoverlapping(ptr, ptr.add(done * elem.size), count * elem.size);
done += count;
}
}
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
write(fields[i].layout, ptr.add(fields[i].offset));
i += 1;
}
}
Kind::Enum(layout) => {
let mut i = 0;
while !layout.variants[i].is_present() {
i += 1;
}
let (variant, tag) = (&layout.variants[i], &layout.tag);
if !variant.holds_tag
&& let Kind::Scalar(spec) = tag.layout.kind
{
store(ptr.add(tag.offset), spec.size, spec.endian, variant.tags().get(0).0);
}
write(variant.layout, ptr);
}
Kind::Pointer(_) => panic!("a self-relative pointer is not made of nothing"),
Kind::Slice(_) | Kind::Pattern(_) => panic!("a field of an enum is sized"),
}
}
}
const unsafe fn store(ptr: *mut u8, size: usize, endian: Endian, value: u128) {
let mut i = 0;
while i < size {
let digit = if endian.is_little() { i } else { size - 1 - i };
unsafe { ptr.add(i).write((value >> (8 * digit)) as u8) };
i += 1;
}
}
const unsafe fn variant<E>(ptr: *const E) -> usize {
let discriminant = mem::discriminant(unsafe { &*ptr });
assert!(
size_of::<mem::Discriminant<E>>() == size_of::<isize>(),
"the discriminant of an enum without `repr` is not an `isize`"
);
let index = unsafe { core::ptr::from_ref(&discriminant).cast::<isize>().read() };
index.cast_unsigned()
}
struct Buf<E>(MaybeUninit<E>);
impl<E> Buf<E> {
const fn of(sample: &MaybeUninit<E>) -> Self {
let mut copy = MaybeUninit::<E>::uninit();
unsafe { core::ptr::copy_nonoverlapping(sample.as_ptr(), copy.as_mut_ptr(), 1) };
Self(copy)
}
const fn transplant(&mut self, from: &MaybeUninit<E>, offset: usize, len: usize) {
assert!(offset + len <= size_of::<E>());
unsafe {
core::ptr::copy_nonoverlapping(
from.as_ptr().cast::<u8>().add(offset),
self.0.as_mut_ptr().cast::<u8>().add(offset),
len,
);
}
}
const fn fill(&mut self, offset: usize, len: usize, byte: u8) {
assert!(offset + len <= size_of::<E>());
unsafe { core::ptr::write_bytes(self.0.as_mut_ptr().cast::<u8>().add(offset), byte, len) };
}
const fn variant(&self) -> usize {
unsafe { variant(self.0.as_ptr()) }
}
}
#[doc(hidden)]
#[derive(Copy, Clone, Debug)]
pub struct Desc<const V: usize> {
tag: (usize, usize),
dataful: usize,
inhabited: [bool; V],
tags: [(u128, u128); V],
dataful_tags: ([(u128, u128); V], usize),
dataful_known: Option<&'static [(u128, u128)]>,
valid: ([(u128, u128); V], usize),
}
impl<const V: usize> Desc<V> {
#[must_use]
pub const fn none() -> Self {
Self {
tag: (0, 0),
dataful: V,
inhabited: [false; V],
tags: [(0, 0); V],
dataful_tags: ([(0, 0); V], 0),
dataful_known: None,
valid: ([(0, 0); V], 0),
}
}
#[must_use]
pub const fn tag_offset(&self) -> usize {
self.tag.0
}
#[must_use]
pub const fn holds_tag(&self, variant: usize) -> bool {
variant == self.dataful
}
#[must_use]
pub const fn inhabited(&self, variant: usize) -> bool {
self.inhabited[variant]
}
#[must_use]
pub const fn variant_ranges(&'static self, variant: usize) -> &'static [(u128, u128)] {
if !self.inhabited[variant] {
&[]
} else if variant == self.dataful {
match self.dataful_known {
Some(ranges) => ranges,
None => self.dataful_tags.0.split_at(self.dataful_tags.1).0,
}
} else {
self.tags.split_at(variant).1.split_at(1).0
}
}
#[must_use]
pub const fn tag(&'static self) -> Layout {
let (size, ranges) = (self.tag.1, self.valid.0.split_at(self.valid.1).0);
let full = ranges.len() == 1 && ranges[0].0 == 0 && ranges[0].1 == max_value(size);
let spec = if size == 0 || ranges.is_empty() || full {
Spec::of_size(size)
} else {
Spec::of_size(size).with_ranges(ranges)
};
Layout::tag(spec.not_a_number())
}
}
const fn covers(fields: &[Field], offset: usize, len: usize) -> bool {
let mut i = 0;
while i < fields.len() {
let field = &fields[i];
if field.layout.size > 0
&& field.offset < offset + len
&& offset < field.offset + field.layout.size
{
return true;
}
i += 1;
}
false
}
const fn fill_gaps<E>(buf: &mut Buf<E>, fields: &[Field], skip: usize, len: usize, byte: u8) {
let (size, mut pos) = (size_of::<E>(), 0);
while pos < size {
let (mut next, mut i, mut inside) = (size, 0, false);
while i < fields.len() {
let field = &fields[i];
let end = field.offset + field.layout.size;
if field.layout.size > 0 && field.offset <= pos && pos < end {
(pos, inside) = (end, true);
break;
}
if field.layout.size > 0 && field.offset > pos && field.offset < next {
next = field.offset;
}
i += 1;
}
if inside {
continue;
}
let (stop, resume) = (skip, skip + len);
if next <= stop || pos >= resume || len == 0 {
buf.fill(pos, next - pos, byte);
} else {
if pos < stop {
buf.fill(pos, stop - pos, byte);
}
if next > resume {
buf.fill(resume, next - resume, byte);
}
}
pos = next;
}
}
const fn decided_by<E>(
sample: &MaybeUninit<E>,
fields: &[Field],
v: usize,
offset: usize,
len: usize,
) -> bool {
let (mut zeros, mut ones) = (Buf::of(sample), Buf::of(sample));
fill_gaps(&mut zeros, fields, offset, len, 0);
fill_gaps(&mut ones, fields, offset, len, 0xff);
zeros.variant() == v && ones.variant() == v
}
const fn read<E>(sample: &MaybeUninit<E>, offset: usize, len: usize) -> u128 {
assert!(offset + len <= size_of::<E>() && len <= 16);
unsafe { load(sample.as_ptr().cast::<u8>().add(offset), len, Endian::NATIVE) }
}
#[expect(
clippy::many_single_char_names,
reason = "`v`, `u` and `d` are variants, `i` and `c` fields and candidates, by their index"
)]
pub const fn discover<E, const V: usize>(
samples: &[MaybeUninit<E>; V],
fields: &[&[Field]; V],
) -> Desc<V> {
let (size, mut desc) = (size_of::<E>(), Desc::none());
let (mut count, mut first, mut sized, mut start, mut v) = (0, V, false, size, 0);
while v < V {
let (these, mut i) = (fields[v], 0);
let mut inhabited = true;
while i < these.len() {
let field = &these[i];
assert!(
!field.layout.has_pointers(),
"an enum without `repr` holds no self-relative pointer"
);
inhabited &= field.layout.is_inhabited();
i += 1;
}
if inhabited {
assert!(unsafe { variant(samples[v].as_ptr()) } == v, "the discriminant is not the index");
let mut i = 0;
while i < these.len() {
let field = &these[i];
assert!(field.offset + field.layout.size <= size, "a field is out of the enum");
assert!(!covers(these.split_at(i).0, field.offset, field.layout.size), "fields overlap");
if field.layout.size > 0 && field.offset < start {
start = field.offset;
}
i += 1;
}
desc.inhabited[v] = true;
if first == V {
first = v;
}
count += 1;
} else {
let mut i = 0;
while i < these.len() {
sized |= these[i].layout.size > 0;
i += 1;
}
}
v += 1;
}
if count == 0 {
return desc;
}
if count == 1 && (!sized || start == 0) {
let these = fields[first];
assert!(
decided_by(&samples[first], these, first, 0, 0),
"the only variant that has values is told by bytes that are not its fields"
);
desc.tags[first] = (0, 0);
desc.valid = ([(0, 0); V], 1);
return desc;
}
if start > 0 {
assert!(
matches!(start, 1 | 2 | 4 | 8 | 16),
"the bytes before the fields of an enum without `repr` are not an integer: unsupported layout"
);
try_tag(&mut desc, samples, fields, (0, start, None), V);
assert!(desc.tag.1 > 0, "the tag of the enum does not tell its variants: unsupported layout");
return desc;
}
let (mut largest, mut most, mut v) = (first, 0, 0);
while v < V {
if desc.inhabited[v] {
let (these, mut bytes, mut i) = (fields[v], 0, 0);
while i < these.len() {
bytes += these[i].layout.size;
i += 1;
}
if bytes > most {
(largest, most) = (v, bytes);
}
}
v += 1;
}
let mut round = 0;
while round <= V {
let d = if round == 0 { largest } else { round - 1 };
round += 1;
if !desc.inhabited[d] || (round > 1 && d == largest) {
continue;
}
let (these, mut i) = (fields[d], 0);
while i < these.len() {
let mut candidates = Candidates::NEW;
candidates.collect(these[i].layout, these[i].offset);
let mut c = 0;
while c < candidates.len {
let (offset, len, known) = candidates.list[c];
c += 1;
let mut free = true;
let mut u = 0;
while u < V {
if u != d && desc.inhabited[u] && covers(fields[u], offset, len) {
free = false;
}
u += 1;
}
if free && try_tag(&mut desc, samples, fields, (offset, len, known), d) {
return desc;
}
}
i += 1;
}
}
panic!("no tag found in the enum: unsupported layout")
}
const fn try_tag<E, const V: usize>(
desc: &mut Desc<V>,
samples: &[MaybeUninit<E>; V],
fields: &[&[Field]; V],
window: (usize, usize, Option<&'static [(u128, u128)]>),
dataful: usize,
) -> bool {
let (offset, len, known) = window;
let mut base = 0;
while base < V && (!desc.inhabited[base] || base == dataful) {
base += 1;
}
assert!(base < V, "no variant without the tag");
let mut r = 0;
while r < V {
if desc.inhabited[r] && r != base {
let mut buf = Buf::of(&samples[base]);
buf.transplant(&samples[r], offset, len);
if buf.variant() != r {
return false;
}
}
r += 1;
}
let mut v = 0;
while v < V {
if desc.inhabited[v]
&& v != dataful
&& (covers(fields[v], offset, len) || !decided_by(&samples[v], fields[v], v, offset, len))
{
return false;
}
v += 1;
}
if dataful < V && !decided_by(&samples[dataful], fields[dataful], dataful, 0, 0) {
return false;
}
let (mut values, mut single, mut v) = ([0; V], [false; V], 0);
while v < V {
if desc.inhabited[v] && v != dataful {
let value = read(&samples[v], offset, len);
let mut u = 0;
while u < v {
assert!(!single[u] || values[u] != value, "two variants have the same tag");
u += 1;
}
(values[v], single[v], desc.tags[v]) = (value, true, (value, value));
}
v += 1;
}
let mut v = 0;
while v < V {
if !single[v] {
values[v] = values[base];
}
v += 1;
}
let (singles, n) = crate::layout::sorted_ranges(values);
if dataful == V {
let mut i = 0;
while i < n {
desc.valid.0[i] = singles[i];
i += 1;
}
desc.valid.1 = n;
} else {
let (max, mut next, mut i, mut out) = (max_value(len), 0u128, 0, 0);
let mut done = false;
while i < n && !done {
let (lo, hi) = singles[i];
if lo > next {
desc.dataful_tags.0[out] = (next, lo - 1);
out += 1;
}
if hi == max {
done = true;
} else {
next = hi + 1;
}
i += 1;
}
if !done {
desc.dataful_tags.0[out] = (next, max);
out += 1;
}
desc.dataful_tags.1 = out;
if let Some(ranges) = known {
let mut v = 0;
while v < V {
assert!(
!single[v] || !crate::layout::contains(ranges, values[v]),
"the tag of a variant is a value of the scalar that holds it: unsupported layout"
);
v += 1;
}
desc.dataful_known = Some(ranges);
}
desc.valid = ([(0, 0); V], 1);
desc.valid.0[0] = (0, max);
}
(desc.tag, desc.dataful) = ((offset, len), dataful);
true
}
struct Candidates {
list: [Candidate; 16],
len: usize,
}
type Candidate = (usize, usize, Option<&'static [(u128, u128)]>);
impl Candidates {
const NEW: Self = Self { list: [(0, 0, None); 16], len: 0 };
const fn push(&mut self, offset: usize, spec: Spec) {
if self.len < self.list.len() && spec.size > 0 && spec.size <= 16 {
let native = spec.size == 1 || spec.endian.equals(Endian::NATIVE);
let known = match spec.known {
Valid::In(ranges) if native => Some(ranges),
_ => None,
};
self.list[self.len] = (offset, spec.size, known);
self.len += 1;
}
}
const fn collect(&mut self, layout: &'static Layout, base: usize) {
match layout.kind {
Kind::Scalar(spec) => {
if matches!(spec.known, Valid::In(_)) {
self.push(base, spec);
}
}
Kind::Array(elem, len) => {
if len > 0 {
self.collect(elem, base);
}
}
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
if !fields[i].restricted {
self.collect(fields[i].layout, base + fields[i].offset);
}
i += 1;
}
}
Kind::Enum(layout) => {
if let Kind::Scalar(spec) = layout.tag.layout.kind {
self.push(base + layout.tag.offset, spec);
}
}
Kind::Slice(_) | Kind::Pattern(_) | Kind::Pointer(_) => {}
}
}
}