use core::mem;
#[doc(hidden)]
pub use crate::discover::Desc;
use crate::{
narrow::{self, How, fit},
ptr,
};
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub enum Endian {
Little,
Big,
}
impl Endian {
pub const NATIVE: Endian =
if cfg!(target_endian = "little") { Endian::Little } else { Endian::Big };
#[inline]
pub(crate) const fn is_little(self) -> bool {
matches!(self, Endian::Little)
}
#[inline]
pub(crate) const fn equals(self, other: Endian) -> bool {
self.is_little() == other.is_little()
}
}
#[derive(Copy, Clone, Debug)]
pub(crate) enum Valid {
Uninit,
Any,
In(&'static [(u128, u128)]),
}
#[derive(Copy, Clone, Debug)]
pub struct Spec {
pub(crate) size: usize,
pub(crate) endian: Endian,
pub(crate) valid: Valid,
pub(crate) known: Valid,
pub(crate) number: bool,
}
#[inline]
pub(crate) const fn max_value(size: usize) -> u128 {
if size >= 16 { u128::MAX } else { (1u128 << (8 * size)) - 1 }
}
impl Spec {
#[inline]
#[must_use]
pub const fn any<T>() -> Self {
let size = size_of::<T>();
Self { size, endian: Endian::NATIVE, valid: Valid::Any, known: Valid::Any, number: true }
}
pub(crate) const fn of_size(size: usize) -> Self {
assert!(size <= 16, "a scalar is at most 16 bytes wide");
Self { size, endian: Endian::NATIVE, valid: Valid::Any, known: Valid::Any, number: true }
}
#[inline]
#[must_use]
pub const fn uninit<T>() -> Self {
let (size, endian) = (size_of::<T>(), Endian::NATIVE);
Self { size, endian, valid: Valid::Uninit, known: Valid::Uninit, number: true }
}
#[must_use]
pub const fn ranges<T>(endian: Endian, ranges: &'static [(u128, u128)]) -> Self {
let size = size_of::<T>();
Self { size, endian, valid: Valid::Any, known: Valid::Any, number: true }.with_ranges(ranges)
}
#[must_use]
pub const fn with_ranges(self, ranges: &'static [(u128, u128)]) -> Self {
let size = self.size;
assert!(size >= 1 && size <= 16, "a constrained scalar must be 1 to 16 bytes wide");
assert!(!ranges.is_empty(), "a scalar must have at least one valid value");
let max = max_value(size);
let mut i = 0;
while i < ranges.len() {
let (lo, hi) = ranges[i];
assert!(lo <= hi && hi <= max, "scalar range is empty or out of bounds");
if i > 0 {
let prev = ranges[i - 1].1;
assert!(prev < lo && lo - prev > 1, "scalar ranges must be sorted and non-adjacent");
}
i += 1;
}
let full = ranges.len() == 1 && ranges[0].0 == 0 && ranges[0].1 == max;
let valid = if full { Valid::Any } else { Valid::In(ranges) };
Self { valid, known: valid, ..self }
}
#[must_use]
pub const fn maybe_uninit(self) -> Self {
assert!(matches!(self.valid, Valid::In(_)), "a scalar that may be uninitialized restricts");
Self { known: Valid::Uninit, ..self }
}
#[inline]
pub(crate) const fn may_be_uninit(&self) -> bool {
matches!(self.known, Valid::Uninit)
}
#[must_use]
pub const fn not_a_number(self) -> Self {
Self { number: false, ..self }
}
#[doc(hidden)]
#[must_use]
pub const fn is_zero_sized<T>() -> bool {
size_of::<T>() == 0
}
#[doc(hidden)]
#[must_use]
pub const fn native_ranges<T>(ranges: &'static [(u128, u128)]) -> Self {
Self::ranges::<T>(Endian::NATIVE, ranges).not_a_number()
}
#[doc(hidden)]
#[must_use]
pub const fn sorted_ranges<const N: usize>(values: [u128; N]) -> ([(u128, u128); N], usize) {
sorted_ranges(values)
}
#[doc(hidden)]
#[must_use]
pub const fn range<T>(start: Option<u128>, end: Option<u128>, inclusive: bool) -> (u128, u128) {
range::<T>(start, end, inclusive)
}
#[doc(hidden)]
#[must_use]
pub const fn merge_ranges<const N: usize>(
ranges: [(u128, u128); N],
) -> ([(u128, u128); N], usize) {
merge_ranges(ranges)
}
#[doc(hidden)]
#[must_use]
pub const unsafe fn bits_of<T>(value: &T) -> u128 {
unsafe { bits_of(value) }
}
#[inline]
pub(crate) const fn is_soft(&self) -> bool {
matches!(self.known, Valid::Any) && matches!(self.valid, Valid::In(_))
}
#[inline]
#[must_use]
pub const fn with_endian(self, endian: Endian) -> Self {
Self { endian, ..self }
}
#[doc(hidden)]
#[must_use]
pub const fn is_integer(&self) -> bool {
self.size <= 16 && !matches!(self.known, Valid::Uninit) && !matches!(self.valid, Valid::Uninit)
}
#[doc(hidden)]
#[inline(always)]
#[must_use]
pub const unsafe fn load(&self, ptr: *const u8) -> u128 {
unsafe { load(ptr, self.size, self.endian) }
}
#[inline]
pub(crate) const fn is_constrained(&self) -> bool {
matches!(self.valid, Valid::In(_))
}
#[must_use]
pub const fn contains(&self, value: u128) -> bool {
match self.valid {
Valid::Uninit | Valid::Any => self.size >= 16 || value <= max_value(self.size),
Valid::In(ranges) => contains(ranges, value),
}
}
#[inline(always)]
pub(crate) const unsafe fn matches(&self, ptr: *const u8) -> bool {
match self.valid {
Valid::Uninit | Valid::Any => true,
Valid::In(ranges) => contains(ranges, unsafe { load(ptr, self.size, self.endian) }),
}
}
}
#[inline(always)]
pub(crate) const fn contains(ranges: &[(u128, u128)], value: u128) -> bool {
let mut i = 0;
if ranges.len() <= 8 {
let mut found = false;
while i < ranges.len() {
found |= value.wrapping_sub(ranges[i].0) <= ranges[i].1 - ranges[i].0;
i += 1;
}
return found;
}
while i < ranges.len() {
if ranges[i].0 <= value && value <= ranges[i].1 {
return true;
}
i += 1;
}
false
}
#[inline(always)]
pub(crate) const unsafe fn load(ptr: *const u8, size: usize, endian: Endian) -> u128 {
let mut buf = [0u8; 16];
unsafe {
match endian {
Endian::Little => {
core::ptr::copy_nonoverlapping(ptr, buf.as_mut_ptr(), size);
u128::from_le_bytes(buf)
}
Endian::Big => {
core::ptr::copy_nonoverlapping(ptr, buf.as_mut_ptr().add(16 - size), size);
u128::from_be_bytes(buf)
}
}
}
}
#[must_use]
pub const fn sorted_ranges<const N: usize>(mut values: [u128; N]) -> ([(u128, u128); N], usize) {
let mut i = 1;
while i < N {
let mut j = i;
while j > 0 && values[j - 1] > values[j] {
values.swap(j - 1, j);
j -= 1;
}
i += 1;
}
let (mut ranges, mut len, mut i) = ([(0, 0); N], 0, 0);
while i < N {
if len > 0 && values[i] - ranges[len - 1].1 <= 1 {
ranges[len - 1].1 = values[i];
} else {
ranges[len] = (values[i], values[i]);
len += 1;
}
i += 1;
}
(ranges, len)
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub(crate) enum Uniform {
No,
Pad,
Any,
}
#[derive(Copy, Clone, Debug)]
pub(crate) enum Kind {
Scalar(Spec),
Array(&'static Layout, usize),
Slice(&'static Layout),
Struct(&'static [Field], &'static [Rule]),
Pattern(&'static Dfa),
Enum(&'static Enum),
Pointer(Pointer),
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum Aim {
One,
Sequence {
align: usize,
},
Text,
}
#[derive(Copy, Clone, Debug)]
pub struct Pointer {
pub(crate) scheme: &'static str,
pub(crate) aim: Aim,
pub(crate) nullable: bool,
pub(crate) nonzero: bool,
pub(crate) width: usize,
pub(crate) endian: Endian,
pub(crate) size: usize,
pub(crate) align: usize,
}
impl Pointer {
const fn new(
scheme: &'static str,
aim: Aim,
width: usize,
endian: Endian,
(size, align): (usize, usize),
) -> Self {
assert!(width >= 1 && width <= 16, "the offset of a pointer is 1 to 16 bytes");
Self { scheme, aim, nullable: false, nonzero: false, width, endian, size, align }
}
const fn target<T>() -> (usize, usize) {
assert!(size_of::<T>() != 0, "a pointer aims at a type with a size");
(size_of::<T>(), align_of::<T>())
}
#[must_use]
pub const fn one<T>(scheme: &'static str, width: usize, endian: Endian) -> Self {
Self::new(scheme, Aim::One, width, endian, Self::target::<T>())
}
#[must_use]
pub const fn sequence<T>(
scheme: &'static str,
width: usize,
endian: Endian,
align: usize,
) -> Self {
assert!(
align.is_power_of_two() && align >= align_of::<T>(),
"the elements of a sequence are at an address aligned for them: a power of two, at least \
the alignment of their type"
);
Self::new(scheme, Aim::Sequence { align }, width, endian, Self::target::<T>())
}
#[must_use]
pub const fn text(scheme: &'static str, width: usize, endian: Endian) -> Self {
Self::new(scheme, Aim::Text, width, endian, (size_of::<()>(), align_of::<()>()))
}
#[must_use]
pub const fn or_null(self) -> Self {
Self { nullable: true, nonzero: false, ..self }
}
#[must_use]
pub const fn is_nullable(&self) -> bool {
self.nullable
}
#[must_use]
pub const fn scheme(&self) -> &'static str {
self.scheme
}
#[must_use]
pub const fn aim(&self) -> Aim {
self.aim
}
#[must_use]
pub const fn width(&self) -> usize {
self.width
}
#[must_use]
pub const fn endian(&self) -> Endian {
self.endian
}
#[must_use]
pub const fn size(&self) -> usize {
self.size
}
#[must_use]
pub const fn align(&self) -> usize {
self.align
}
pub(crate) const fn reads_as(&self, to: &Pointer) -> Option<bool> {
let fits = str_equals(self.scheme, to.scheme)
&& self.width == to.width
&& self.endian.equals(to.endian)
&& match (self.aim, to.aim) {
(Aim::One, Aim::One) => to.size <= self.size && to.align <= self.align,
(Aim::Sequence { align: from }, Aim::Sequence { align: into }) => {
to.size == self.size && into <= from
}
(Aim::Text, Aim::Text) => true,
_ => false,
};
let zero = self.nullable || !self.nonzero;
if fits { Some(to.nullable || !to.nonzero && !self.nullable || !zero) } else { None }
}
const fn same(&self, other: &Pointer) -> bool {
let aims = match (self.aim, other.aim) {
(Aim::One, Aim::One) | (Aim::Text, Aim::Text) => true,
(Aim::Sequence { align: a }, Aim::Sequence { align: b }) => a == b,
_ => false,
};
aims
&& str_equals(self.scheme, other.scheme)
&& self.nullable == other.nullable
&& self.nonzero == other.nonzero
&& self.width == other.width
&& self.endian.equals(other.endian)
&& self.size == other.size
&& self.align == other.align
}
}
const fn str_equals(a: &str, b: &str) -> bool {
let (a, b) = (a.as_bytes(), b.as_bytes());
if a.len() != b.len() {
return false;
}
let mut i = 0;
while i < a.len() {
if a[i] != b[i] {
return false;
}
i += 1;
}
true
}
#[derive(Debug)]
pub struct Enum {
pub(crate) tag: Field,
pub(crate) variants: &'static [Variant],
pub(crate) specified: (usize, usize),
pub(crate) union: bool,
}
impl Enum {
#[must_use]
pub const fn new(
tag: &'static Layout,
outside: bool,
shadows: &[(usize, usize)],
fields: usize,
variants: &'static [Variant],
) -> Self {
let (mut size, mut align, mut i) = (0, 1, 0);
while i < shadows.len() {
if shadows[i].0 > size {
size = shadows[i].0;
}
if shadows[i].1 > align {
align = shadows[i].1;
}
i += 1;
}
let specified = if outside {
assert!(fields == Self::fields(tag, shadows), "not where the fields of the variants are");
let align = if tag.align > align { tag.align } else { align };
(tail_offset(fields + size, align, usize::MAX), align)
} else {
assert!(fields == 0, "not where the fields of the variants are");
(tail_offset(size, align, usize::MAX), align)
};
Self { tag: Field::new(0, tag), variants, specified, union: false }
}
#[doc(hidden)]
#[must_use]
pub const fn discovered(
tag: &'static Layout,
offset: usize,
variants: &'static [Variant],
specified: (usize, usize),
) -> Self {
Self { tag: Field::new(offset, tag), variants, specified, union: false }
}
#[doc(hidden)]
#[must_use]
pub const fn union(fields: &'static [Variant]) -> Self {
Self { tag: Field::new(0, &NO_TAG), variants: fields, specified: (0, 1), union: true }
}
const NEVER: Self =
Self { tag: Field::new(0, &NO_TAG), variants: &[], specified: (0, 1), union: false };
#[must_use]
pub const fn fields(tag: &Layout, shadows: &[(usize, usize)]) -> usize {
let (mut align, mut i) = (1, 0);
while i < shadows.len() {
if shadows[i].1 > align {
align = shadows[i].1;
}
i += 1;
}
tail_offset(tag.size, align, usize::MAX)
}
}
#[derive(Copy, Clone, Debug)]
pub struct Variant {
pub(crate) tag: u128,
pub(crate) ranges: Option<&'static [(u128, u128)]>,
pub(crate) holds_tag: bool,
pub(crate) layout: &'static Layout,
}
#[derive(Copy, Clone)]
pub(crate) struct Tags {
one: (u128, u128),
ranges: Option<&'static [(u128, u128)]>,
}
impl Tags {
pub(crate) const fn range(lo: u128, hi: u128) -> Self {
Self { one: (lo, hi), ranges: None }
}
pub(crate) const fn of(ranges: &'static [(u128, u128)]) -> Self {
Self { one: (0, 0), ranges: Some(ranges) }
}
pub(crate) const fn len(&self) -> usize {
match self.ranges {
Some(ranges) => ranges.len(),
None => 1,
}
}
pub(crate) const fn get(&self, index: usize) -> (u128, u128) {
match self.ranges {
Some(ranges) => ranges[index],
None => self.one,
}
}
pub(crate) const fn has(&self, value: u128) -> bool {
let mut i = 0;
while i < self.len() {
let (lo, hi) = self.get(i);
if lo <= value && value <= hi {
return true;
}
i += 1;
}
false
}
pub(crate) const fn meets(&self, other: &Tags) -> bool {
let (mut mine, mut theirs) = (0, 0);
while mine < self.len() && theirs < other.len() {
let ((lo, hi), (other_lo, other_hi)) = (self.get(mine), other.get(theirs));
if lo <= other_hi && other_lo <= hi {
return true;
}
if hi < other_hi {
mine += 1;
} else {
theirs += 1;
}
}
false
}
pub(crate) const fn within(&self, other: &Tags) -> bool {
let mut i = 0;
while i < self.len() {
let ((lo, hi), mut j, mut inside) = (self.get(i), 0, false);
while j < other.len() {
let (a, b) = other.get(j);
inside |= a <= lo && hi <= b;
j += 1;
}
if !inside {
return false;
}
i += 1;
}
true
}
const fn equals(&self, other: &Tags) -> bool {
if self.len() != other.len() {
return false;
}
let mut index = 0;
while index < self.len() {
let (mine, theirs) = (self.get(index), other.get(index));
if mine.0 != theirs.0 || mine.1 != theirs.1 {
return false;
}
index += 1;
}
true
}
}
impl Variant {
#[must_use]
pub const fn new(tag: u128, layout: &'static Layout) -> Self {
Self { tag, ranges: None, holds_tag: false, layout }
}
#[doc(hidden)]
#[must_use]
pub const fn discovered(
index: usize,
ranges: &'static [(u128, u128)],
holds_tag: bool,
layout: &'static Layout,
) -> Self {
Self { tag: index as u128, ranges: Some(ranges), holds_tag, layout }
}
pub(crate) const fn tags(&self) -> Tags {
Tags { one: (self.tag, self.tag), ranges: self.ranges }
}
pub(crate) const fn is_present(&self) -> bool {
!matches!(self.ranges, Some(ranges) if ranges.is_empty()) && self.layout.is_inhabited()
}
pub(crate) const fn fields(&self) -> &'static [Field] {
let Kind::Struct(fields, _) = self.layout.kind else { panic!("not a variant") };
fields
}
}
#[derive(Copy, Clone, Debug)]
pub struct Field {
pub(crate) offset: usize,
pub(crate) layout: &'static Layout,
pub(crate) index: usize,
pub(crate) leaf: usize,
pub(crate) restricted: bool,
}
impl Field {
#[inline]
#[must_use]
pub const fn new(offset: usize, layout: &'static Layout) -> Self {
Self { offset, layout, index: 0, leaf: 0, restricted: false }
}
#[inline]
#[must_use]
pub const fn restricted(offset: usize, layout: &'static Layout) -> Self {
assert!(matches!(layout.kind, Kind::Scalar(_)), "only scalar fields can be restricted");
Self { offset, layout, index: 0, leaf: 0, restricted: true }
}
#[doc(hidden)]
#[must_use]
pub const fn restriction(&self) -> Option<Spec> {
match self.layout.kind {
Kind::Scalar(spec) if self.restricted => Some(spec),
_ => None,
}
}
#[doc(hidden)]
#[must_use]
pub const fn offset(&self) -> usize {
self.offset
}
#[doc(hidden)]
#[must_use]
pub const fn leaf(&self) -> usize {
self.leaf
}
}
#[derive(Copy, Clone, Debug)]
pub struct Layout {
pub(crate) kind: Kind,
pub(crate) size: usize,
pub(crate) align: usize,
pub(crate) tail: usize,
pub(crate) unsized_: bool,
pub(crate) leaves: usize,
pub(crate) uniform: Uniform,
pub(crate) has_rules: bool,
}
#[derive(Copy, Clone)]
pub(crate) enum Shape {
Scalar(Spec),
Array(usize),
Slice,
Struct,
Pattern(&'static Dfa),
Enum(&'static Enum),
Pointer(Pointer),
}
#[inline]
pub(crate) const fn round_up(value: usize, align: usize) -> Option<usize> {
match value.checked_add(align - 1) {
Some(v) => Some(v & !(align - 1)),
None => None,
}
}
#[doc(hidden)]
#[must_use]
pub const fn tail_offset(end: usize, align: usize, pack: usize) -> usize {
match round_up(end, if align < pack { align } else { pack }) {
Some(offset) => offset,
None => panic!("struct is too large"),
}
}
const fn excludes_zero<P>() -> bool {
if size_of::<Option<P>>() != size_of::<P>() {
return false;
}
let none = mem::MaybeUninit::new(None::<P>);
let mut i = 0;
while i < size_of::<P>() {
let byte = unsafe { *none.as_ptr().cast::<u8>().add(i) };
assert!(
byte == 0,
"the offset of a self-relative pointer excludes values other than zero (a niche that is not \
zero): not supported, nothing tells which"
);
i += 1;
}
true
}
const NO_TAG: Layout = Layout::scalar::<()>(Spec::any::<()>());
fn pin<T>(_: T) {}
impl Layout {
#[doc(hidden)]
#[expect(
clippy::type_complexity,
reason = "the derive writes this tuple of `fn` types out, with the paths it is told"
)]
pub const PIN: (fn(Rule), fn(Op), fn(Field), fn(Enum), fn(Variant)) =
(pin::<Rule>, pin::<Op>, pin::<Field>, pin::<Enum>, pin::<Variant>);
#[doc(hidden)]
#[must_use]
pub const fn uninit<T>() -> mem::MaybeUninit<T> {
mem::MaybeUninit::uninit()
}
#[doc(hidden)]
#[must_use]
pub const fn discover<E, const V: usize>(
samples: &[mem::MaybeUninit<E>; V],
fields: &[&[Field]; V],
) -> Desc<V> {
crate::discover::discover(samples, fields)
}
#[doc(hidden)]
#[must_use]
pub const fn sample<T: crate::Pun>() -> mem::MaybeUninit<T> {
crate::discover::sample::<T>()
}
#[doc(hidden)]
#[must_use]
pub const fn wrap<T>(value: T) -> mem::MaybeUninit<T> {
mem::MaybeUninit::new(value)
}
#[doc(hidden)]
#[must_use]
pub const fn inhabited_all(fields: &[&'static Layout]) -> bool {
let mut i = 0;
while i < fields.len() {
if !fields[i].is_inhabited() {
return false;
}
i += 1;
}
true
}
#[doc(hidden)]
#[must_use]
pub const fn repr_c<const N: usize>(
start: (usize, usize),
fields: [(usize, usize); N],
) -> ([usize; N], (usize, usize)) {
let (mut offsets, (mut end, mut align), mut i) = ([0; N], start, 0);
while i < N {
offsets[i] = tail_offset(end, fields[i].1, usize::MAX);
end = offsets[i] + fields[i].0;
if fields[i].1 > align {
align = fields[i].1;
}
i += 1;
}
(offsets, (tail_offset(end, align, usize::MAX), align))
}
#[doc(hidden)]
#[must_use]
pub const fn size_align<T>() -> (usize, usize) {
(size_of::<T>(), align_of::<T>())
}
#[doc(hidden)]
#[must_use]
pub const fn tail_offset(end: usize, align: usize) -> usize {
tail_offset(end, align, usize::MAX)
}
#[doc(hidden)]
#[must_use]
pub const fn tail_offset_packed(end: usize, align: usize, pack: usize) -> usize {
tail_offset(end, align, pack)
}
#[must_use]
pub const fn scalar<T>(spec: Spec) -> Self {
assert!(spec.size == size_of::<T>(), "`Spec` size mismatch");
Self {
kind: Kind::Scalar(spec),
size: spec.size,
align: align_of::<T>(),
tail: 0,
unsized_: false,
leaves: spec.is_constrained() as usize,
uniform: match spec.valid {
Valid::Uninit => Uniform::Pad,
Valid::Any => Uniform::Any,
Valid::In(_) => Uniform::No,
},
has_rules: false,
}
}
pub(crate) const fn tag(spec: Spec) -> Self {
Self {
kind: Kind::Scalar(spec),
size: spec.size,
align: 1,
tail: 0,
unsized_: false,
leaves: spec.is_constrained() as usize,
uniform: match spec.valid {
Valid::Uninit => Uniform::Pad,
Valid::Any => Uniform::Any,
Valid::In(_) => Uniform::No,
},
has_rules: false,
}
}
#[must_use]
pub const fn restricted(&self, ranges: &'static [(u128, u128)]) -> Self {
let Kind::Scalar(spec) = self.kind else { panic!("only scalars can be restricted") };
assert!(!matches!(spec.valid, Valid::Uninit), "only initialized scalars can be restricted");
let new = Spec { known: spec.known, ..spec.with_ranges(ranges) };
let mut i = 0;
while i < ranges.len() {
assert!(
spec.contains(ranges[i].0) && spec.contains(ranges[i].1),
"restricted to values that are not valid for the type"
);
if let Valid::In(old) = spec.valid {
assert!(
matches!(crate::analysis::relate_ranges(ranges, old), crate::analysis::Rel::Subset),
"restricted to values that are not valid for the type"
);
}
i += 1;
}
Self {
kind: Kind::Scalar(new),
leaves: new.is_constrained() as usize,
uniform: if new.is_constrained() { Uniform::No } else { self.uniform },
..*self
}
}
pub const unsafe fn pattern<T: ?Sized>(probe: *const T, dfa: &'static Dfa) -> Self {
unsafe { ptr::verify::<T>(probe) };
assert!(unsafe { mem::size_of_val_raw(probe) } == ptr::PROBE_LEN, "not a byte string");
dfa.check();
Self {
kind: Kind::Pattern(dfa),
size: 0,
align: 1,
tail: 1,
unsized_: true,
leaves: 1,
uniform: Uniform::No,
has_rules: false,
}
}
#[must_use]
pub const fn padding<T>() -> Self {
Self {
kind: Kind::Struct(&[], &[]),
size: size_of::<T>(),
align: align_of::<T>(),
tail: 0,
unsized_: false,
leaves: 0,
uniform: Uniform::Pad,
has_rules: false,
}
}
#[doc(hidden)]
#[must_use]
pub const fn pointer<P, T>(pointer: Pointer) -> Self {
assert!(size_of::<P>() == pointer.width, "a self-relative pointer is its offset");
let nonzero = excludes_zero::<P>();
assert!(
!(nonzero && pointer.nullable),
"a self-relative pointer that may be null has a value of zeros: its offset is no `NonZero`"
);
let pointer = Pointer { nonzero, ..pointer };
assert!(
size_of::<T>() == pointer.size && align_of::<T>() == pointer.align,
"the `POINTER` of a `SelfRelative` type is made for its `Target`"
);
Self {
kind: Kind::Pointer(pointer),
size: pointer.width,
align: align_of::<P>(),
tail: 0,
unsized_: false,
leaves: 1,
uniform: Uniform::No,
has_rules: false,
}
}
#[must_use]
pub const fn nullable<P, T>(pointer: Pointer) -> Self {
assert!(!pointer.is_nullable(), "`Option` of a pointer that may be null is not a pointer");
assert!(
size_of::<Option<P>>() == size_of::<P>(),
"`Option` of this self-relative pointer is larger than it: its offset has no niche at zero \
(a `NonZero` has one), so `None` is not the pointer of zeros"
);
let none = mem::MaybeUninit::new(None::<P>);
let mut i = 0;
while i < size_of::<P>() {
let byte = unsafe { *none.as_ptr().cast::<u8>().add(i) };
assert!(byte == 0, "`None` of this self-relative pointer is not zeros");
i += 1;
}
Self::pointer::<Option<P>, T>(pointer.or_null())
}
#[must_use]
pub const fn as_pointer(&self) -> Option<Pointer> {
match self.kind {
Kind::Pointer(pointer) => Some(pointer),
_ => None,
}
}
#[must_use]
pub const fn is_free(&self) -> bool {
self.leaves == 0
}
#[must_use]
pub const fn is_plain(&self) -> bool {
match self.kind {
Kind::Scalar(spec) => !spec.may_be_uninit(),
Kind::Array(elem, _) => elem.is_plain(),
Kind::Struct(fields, _) => {
let (mut i, mut covered) = (0, 0);
while i < fields.len() {
if fields[i].offset != covered || !fields[i].layout.is_plain() {
return false;
}
covered += fields[i].layout.size;
i += 1;
}
!self.unsized_ && covered == self.size
}
Kind::Slice(_) | Kind::Pattern(_) | Kind::Enum(_) | Kind::Pointer(_) => false,
}
}
#[must_use]
pub const fn has_pointers(&self) -> bool {
if self.leaves == 0 {
return false;
}
match self.kind {
Kind::Pointer(_) => true,
Kind::Scalar(_) | Kind::Pattern(_) => false,
Kind::Array(elem, _) | Kind::Slice(elem) => elem.has_pointers(),
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
if fields[i].layout.has_pointers() {
return true;
}
i += 1;
}
false
}
Kind::Enum(layout) => {
let mut i = 0;
while i < layout.variants.len() {
if layout.variants[i].layout.has_pointers() {
return true;
}
i += 1;
}
false
}
}
}
#[must_use]
pub const fn array(elem: &'static Layout, len: usize) -> Self {
assert!(!elem.unsized_);
Self {
kind: Kind::Array(elem, len),
size: match elem.size.checked_mul(len) {
Some(size) => size,
None => panic!("array is too large"),
},
align: elem.align,
tail: 0,
unsized_: false,
leaves: elem.leaves,
uniform: elem.uniform,
has_rules: elem.has_rules,
}
}
pub const unsafe fn slice<T>(probe: *const [T], elem: &'static Layout) -> Self {
assert!(!elem.unsized_ && elem.size == size_of::<T>());
unsafe { ptr::verify::<[T]>(probe) };
Self {
kind: Kind::Slice(elem),
size: 0,
align: elem.align,
tail: elem.size,
unsized_: true,
leaves: elem.leaves,
uniform: elem.uniform,
has_rules: elem.has_rules,
}
}
pub const unsafe fn structure<T: ?Sized>(
probe: *const T,
fields: &'static [Field],
rules: &'static [Rule],
) -> Self {
let (mut i, mut end, mut leaves) = (0, 0, (!rules.is_empty()) as usize);
let mut has_rules = !rules.is_empty();
let (mut all_any, mut all_pad) = (true, true);
let mut tail: Option<&Field> = None;
while i < fields.len() {
let field = &fields[i];
assert!(tail.is_none(), "only the last field of a struct can be unsized");
leaves += field.layout.leaves;
has_rules |= field.layout.has_rules;
if field.layout.unsized_ {
assert!(field.offset >= end, "fields must not overlap");
tail = Some(field);
} else if field.layout.size > 0 {
assert!(field.offset >= end, "fields must be sorted and must not overlap");
all_any &= field.offset == end && matches!(field.layout.uniform, Uniform::Any);
all_pad &= matches!(field.layout.uniform, Uniform::Pad);
end = field.offset + field.layout.size;
}
i += 1;
}
match tail {
None => {
let (size, align) = unsafe { (mem::size_of_val_raw(probe), mem::align_of_val_raw(probe)) };
assert!(end <= size, "field out of bounds");
let uniform = match (all_any && end == size, all_pad) {
_ if size == 0 => Uniform::Any,
(true, _) => Uniform::Any,
(_, true) => Uniform::Pad,
_ => Uniform::No,
};
check_rules(rules, end);
let this = Self {
kind: Kind::Struct(fields, rules),
size,
align,
tail: 0,
unsized_: false,
leaves,
uniform,
has_rules,
};
let mut i = 0;
while i < rules.len() {
assert!(
!matches!(rules[i], Rule::Len(_)) || this.tail_shape().array,
"`len` is about a last field that is a slice, or an array"
);
i += 1;
}
this
}
Some(field) => {
unsafe { ptr::verify::<T>(probe) };
let align = unsafe { mem::align_of_val_raw(probe) };
check_rules(rules, end);
let this = Self {
kind: Kind::Struct(fields, rules),
size: field.offset + field.layout.size,
align,
tail: field.layout.tail,
unsized_: true,
leaves,
uniform: Uniform::No,
has_rules,
};
let mut len = 0;
while len <= 8 {
let size = unsafe { mem::size_of_val_raw(ptr::raw_with_len(probe, len)) };
assert!(
matches!(this.size_of_val(len), Some(s) if s == size),
"unsupported layout: the trailing padding of this unsized struct is not the one of \
its unsized field (packed struct with an aligned unsized field?)",
);
len += 1;
}
this
}
}
}
#[must_use]
pub const fn variant<T>(fields: &'static [Field]) -> Self {
let (mut i, mut leaves, mut has_rules) = (0, 0, false);
while i < fields.len() {
leaves += fields[i].layout.leaves;
has_rules |= fields[i].layout.has_rules;
i += 1;
}
Self {
kind: Kind::Struct(fields, &[]),
size: size_of::<T>(),
align: align_of::<T>(),
tail: 0,
unsized_: false,
leaves,
uniform: Uniform::No,
has_rules,
}
}
#[must_use]
pub const fn enumeration<T>(layout: &'static Enum) -> Self {
let (size, tag) = (size_of::<T>(), &layout.tag);
let Kind::Scalar(spec) = tag.layout.kind else { panic!("the tag of an enum is a scalar") };
assert!(
align_of::<T>() >= layout.specified.1
&& size == tail_offset(layout.specified.0, align_of::<T>(), usize::MAX),
"the enum is not laid out as its representation specifies"
);
assert!(spec.is_integer() && tag.offset + spec.size <= size, "tag out of bounds");
let (mut i, mut holders) = (0, 0);
while i < layout.variants.len() {
let variant = &layout.variants[i];
let tags = variant.tags();
let mut j = 0;
while j < tags.len() {
let (lo, hi) = tags.get(j);
assert!(lo <= hi && spec.contains(lo) && spec.contains(hi), "not a value of the tag");
assert!(j == 0 || tags.get(j - 1).1 < lo, "the tags of a variant are not sorted");
j += 1;
}
holders += variant.holds_tag as usize;
let (fields, mut j, mut end) = (variant.fields(), 0, 0);
assert!(variant.layout.size == size, "not a variant of this enum");
while j < fields.len() {
let field = &fields[j];
assert!(!field.layout.unsized_, "the fields of an enum are sized");
if field.layout.size > 0 {
let field_end = field.offset + field.layout.size;
assert!(field.offset >= end && field_end <= size, "fields overlap or are out of bounds");
assert!(
variant.holds_tag || field_end <= tag.offset || field.offset >= tag.offset + spec.size,
"a field overlaps the tag"
);
end = field_end;
}
j += 1;
}
let mut j = 0;
while j < i {
assert!(!layout.variants[j].tags().meets(&tags), "two variants have the same tag");
j += 1;
}
i += 1;
}
assert!(holders <= 1, "the tag is in the fields of two variants");
Self {
kind: Kind::Enum(layout),
size,
align: align_of::<T>(),
tail: 0,
unsized_: false,
leaves: 1,
uniform: Uniform::No,
has_rules: false,
}
}
pub(crate) const fn rule_ops(&self, rule: usize) -> &'static [Op] {
let rules = self.rules();
if rule >= rules.len() {
return &[];
}
match rules[rule].ops() {
Some(ops) => ops,
None => &[],
}
}
pub(crate) const fn rule(&self, index: usize) -> Option<Rule> {
let rules = self.rules();
if index < rules.len() { Some(rules[index]) } else { None }
}
#[doc(hidden)]
#[must_use]
pub const fn variant_tag(&self, variant: usize) -> u128 {
let Kind::Enum(layout) = self.kind else { panic!("not an enum") };
layout.variants[variant].tag
}
#[doc(hidden)]
#[must_use]
pub const fn variant_ranges(&self, variant: usize) -> Option<&'static [(u128, u128)]> {
let Kind::Enum(layout) = self.kind else { panic!("not an enum") };
layout.variants[variant].ranges
}
#[must_use]
pub const fn uninhabited<T>() -> Self {
Self {
kind: Kind::Enum(&Enum::NEVER),
size: size_of::<T>(),
align: align_of::<T>(),
tail: 0,
unsized_: false,
leaves: 1,
uniform: Uniform::No,
has_rules: false,
}
}
#[must_use]
pub const fn is_inhabited(&self) -> bool {
match self.kind {
Kind::Scalar(_) | Kind::Pattern(_) | Kind::Pointer(_) | Kind::Slice(_) => true,
Kind::Array(elem, len) => len == 0 || elem.is_inhabited(),
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
if !fields[i].layout.unsized_ && !fields[i].layout.is_inhabited() {
return false;
}
i += 1;
}
true
}
Kind::Enum(layout) => {
let mut i = 0;
while i < layout.variants.len() {
if layout.variants[i].is_present() {
return true;
}
i += 1;
}
false
}
}
}
#[must_use]
pub const fn union<T>(layout: &'static Enum) -> Self {
assert!(layout.union, "not a union");
let (size, mut i) = (size_of::<T>(), 0);
while i < layout.variants.len() {
let variant = &layout.variants[i];
let fields = variant.fields();
assert!(variant.layout.size == size, "not a field of this union");
assert!(fields.len() <= 1, "a field of a union is one field");
if fields.len() == 1 {
let field = &fields[0];
assert!(field.offset == 0 && field.layout.size <= size, "the fields of a union are at 0");
assert!(!field.layout.unsized_, "the fields of a union are sized");
}
assert!(!variant.layout.has_pointers(), "a union holds no self-relative pointer");
i += 1;
}
Self {
kind: Kind::Enum(layout),
size,
align: align_of::<T>(),
tail: 0,
unsized_: false,
leaves: 1,
uniform: Uniform::No,
has_rules: false,
}
}
#[doc(hidden)]
#[must_use]
pub const fn variant_field(&self, variant: usize, index: usize) -> &Field {
let Kind::Enum(layout) = self.kind else { panic!("not an enum") };
let (fields, mut i) = (layout.variants[variant].fields(), 0);
while i < fields.len() {
if fields[i].index == index {
return &fields[i];
}
i += 1;
}
panic!("no such field")
}
pub(crate) const fn segment(&self, offset: usize, always: bool, checked: bool) -> (bool, usize) {
if checked && !always && self.rules_read_bytes() {
return (true, self.size);
}
match self.uniform {
Uniform::Any => return (true, self.size),
Uniform::Pad => return (false, self.size),
Uniform::No => {}
}
match self.kind {
Kind::Scalar(spec) => {
(!matches!(if always { spec.known } else { spec.valid }, Valid::Uninit), self.size)
}
Kind::Pointer(_) => (true, self.size),
Kind::Pattern(_) | Kind::Slice(_) => panic!("not sized"),
Kind::Array(..) => (!always, self.size),
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
let field = &fields[i];
if offset < field.offset {
return (false, field.offset);
}
if offset < field.offset + field.layout.size {
let (init, end) = field.layout.segment(offset - field.offset, always, checked);
return (init, field.offset + end);
}
i += 1;
}
(false, self.size)
}
Kind::Enum(layout) if layout.union && always => (false, self.size),
Kind::Enum(layout) => {
let (start, end) = (layout.tag.offset, layout.tag.offset + layout.tag.layout.size);
if offset >= start && offset < end {
return (true, end);
}
let (mut i, mut every, mut some) = (0, true, false);
let mut stop = if offset < start { start } else { self.size };
while i < layout.variants.len() {
if !layout.variants[i].is_present() {
i += 1;
continue;
}
let (init, end) = layout.variants[i].layout.segment(offset, always, checked);
(every, some) = (every && init, some || init);
if end < stop {
stop = end;
}
i += 1;
}
(if always { every } else { some }, stop)
}
}
}
#[must_use]
pub const fn sort_fields<const N: usize>(mut fields: [Field; N]) -> [Field; N] {
let (mut i, mut leaf) = (0, 0);
while i < N {
(fields[i].index, fields[i].leaf) = (i, leaf);
leaf += fields[i].layout.leaves;
i += 1;
}
let mut i = 1;
while i < N {
let mut j = i;
while j > 0 && fields[j - 1].offset > fields[j].offset {
fields.swap(j - 1, j);
j -= 1;
}
i += 1;
}
fields
}
#[inline]
#[must_use]
pub const fn align(&self) -> usize {
self.align
}
#[inline]
#[must_use]
pub const fn size(&self) -> usize {
self.size
}
#[inline]
pub(crate) const fn is_unsized(&self) -> bool {
self.unsized_
}
#[inline]
pub(crate) const fn is_dynamic(&self) -> bool {
self.unsized_ && self.tail > 0
}
#[inline]
pub(crate) const fn stride(&self) -> usize {
if self.unsized_ { self.tail } else { 0 }
}
#[inline]
pub(crate) const fn size_of_val(&self, len: usize) -> Option<usize> {
if !self.unsized_ {
return Some(self.size);
}
match self.tail.checked_mul(len) {
Some(tail) => match self.size.checked_add(tail) {
Some(extent) => round_up(extent, self.align),
None => None,
},
None => None,
}
}
#[doc(hidden)]
#[must_use]
pub const fn field(&self, index: usize) -> &Field {
let Kind::Struct(fields, _) = self.kind else { panic!("not a struct") };
let mut i = 0;
while i < fields.len() {
if fields[i].index == index {
return &fields[i];
}
i += 1;
}
panic!("no such field")
}
#[doc(hidden)]
#[must_use]
pub const fn field_offset(&self, index: usize) -> usize {
self.field(index).offset
}
#[doc(hidden)]
#[must_use]
pub const fn field_leaf(&self, index: usize) -> usize {
self.field(index).leaf
}
#[inline]
pub(crate) const fn shape(&self) -> Shape {
match self.kind {
Kind::Scalar(spec) => Shape::Scalar(spec),
Kind::Array(_, len) => Shape::Array(len),
Kind::Slice(_) => Shape::Slice,
Kind::Struct(..) => Shape::Struct,
Kind::Pattern(dfa) => Shape::Pattern(dfa),
Kind::Enum(layout) => Shape::Enum(layout),
Kind::Pointer(pointer) => Shape::Pointer(pointer),
}
}
pub(crate) const fn rules_read_bytes(&self) -> bool {
let (rules, mut i) = (self.rules(), 0);
while i < rules.len() {
if let Some(ops) = rules[i].ops()
&& ops_read_bytes(ops)
{
return true;
}
i += 1;
}
false
}
pub(crate) const fn key(&self) -> Option<(usize, Spec)> {
match self.kind {
Kind::Scalar(spec) if spec.is_constrained() => Some((0, spec)),
Kind::Struct(fields, _) => {
let (mut best, mut i): (Option<(usize, Spec)>, usize) = (None, 0);
while i < fields.len() {
if let Some((offset, spec)) = fields[i].layout.key() {
let offset = fields[i].offset + offset;
if !matches!(best, Some((first, _)) if first <= offset) {
best = Some((offset, spec));
}
}
i += 1;
}
best
}
Kind::Array(elem, len) if len > 0 => elem.key(),
_ => None,
}
}
pub(crate) const fn block(&self) -> usize {
if self.size == 0 || self.size > 16 || self.unsized_ || !self.is_cheap() {
return 1;
}
64 / self.size
}
const fn is_cheap(&self) -> bool {
match self.kind {
Kind::Scalar(_) => true,
Kind::Array(elem, len) => len <= 16 && elem.is_cheap(),
Kind::Struct(fields, rules) => {
let mut i = 0;
while i < fields.len() {
if !fields[i].layout.is_cheap() {
return false;
}
i += 1;
}
let mut i = 0;
while i < rules.len() {
if let Some(ops) = rules[i].ops()
&& !cheap_ops(ops)
{
return false;
}
i += 1;
}
true
}
Kind::Slice(_) | Kind::Pattern(_) | Kind::Enum(_) | Kind::Pointer(_) => false,
}
}
#[inline]
pub(crate) const fn rules(&self) -> &'static [Rule] {
match self.kind {
Kind::Struct(_, rules) => rules,
_ => &[],
}
}
pub(crate) const fn struct_fields(&self) -> &'static [Field] {
match self.kind {
Kind::Struct(fields, _) => fields,
_ => &[],
}
}
pub(crate) const fn has_last_region(&self) -> bool {
matches!(self.rules().last(), Some(Rule::Region(None)))
}
pub(crate) const fn length_rule(&self) -> Option<LengthRule> {
let (mut layout, mut base) = (self, 0);
loop {
let Kind::Struct(fields, rules) = layout.kind else { return None };
let mut i = 0;
while i < rules.len() {
match rules[i] {
Rule::Size(ops) => return Some(LengthRule { base, elements: false, ops }),
Rule::Len(ops) => return Some(LengthRule { base, elements: true, ops }),
_ => {}
}
i += 1;
}
if fields.is_empty() || !layout.unsized_ {
return None;
}
let last = &fields[fields.len() - 1];
(layout, base) = (last.layout, base + last.offset);
}
}
#[doc(hidden)]
#[must_use]
pub const fn as_integer(&self) -> Option<Spec> {
match self.kind {
Kind::Scalar(spec) if spec.is_integer() && spec.number && spec.size >= 1 => Some(spec),
Kind::Struct(fields, _) if !self.unsized_ => {
let (mut inner, mut i): (Option<&Layout>, usize) = (None, 0);
while i < fields.len() {
let field = &fields[i];
if field.layout.size > 0 {
if inner.is_some() || field.offset != 0 || field.layout.size != self.size {
return None;
}
inner = Some(field.layout);
}
i += 1;
}
match inner {
Some(inner) => inner.as_integer(),
None => None,
}
}
_ => None,
}
}
pub(crate) const fn tail_shape(&self) -> TailShape {
let mut shape = TailShape { start: self.size, bytes: 0, len: 0, array: false };
let Kind::Struct(fields, _) = self.kind else { return shape };
if self.unsized_ || fields.is_empty() {
return shape;
}
let (mut last, mut i) = (&fields[0], 1);
while i < fields.len() {
if fields[i].index > last.index {
last = &fields[i];
}
i += 1;
}
(shape.start, shape.bytes) = (last.offset, last.layout.size);
let mut layout = last.layout;
loop {
match layout.kind {
Kind::Array(_, len) => {
(shape.len, shape.array) = (len, true);
return shape;
}
Kind::Struct(fields, _) if !fields.is_empty() => layout = fields[fields.len() - 1].layout,
_ => return shape,
}
}
}
#[inline]
pub(crate) const fn head(&self) -> usize {
self.size
}
pub(crate) const fn zeroable(&self) -> bool {
match self.kind {
Kind::Scalar(spec) => spec.contains(0),
Kind::Array(elem, len) => len == 0 || elem.zeroable(),
Kind::Slice(elem) => elem.zeroable(),
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
if !fields[i].layout.zeroable() {
return false;
}
i += 1;
}
true
}
Kind::Pattern(dfa) => dfa.states[0].accept,
Kind::Pointer(pointer) => pointer.nullable,
Kind::Enum(layout) if layout.union => {
let mut i = 0;
while i < layout.variants.len() {
if layout.variants[i].is_present() && layout.variants[i].layout.zeroable() {
return true;
}
i += 1;
}
false
}
Kind::Enum(layout) => {
let mut i = 0;
while i < layout.variants.len() {
if layout.variants[i].tags().has(0) && layout.variants[i].is_present() {
let (fields, mut j) = (layout.variants[i].fields(), 0);
while j < fields.len() {
if !fields[j].layout.zeroable() {
return false;
}
j += 1;
}
return true;
}
i += 1;
}
false
}
}
}
pub(crate) const fn same_rules(&self, other: &Layout) -> bool {
let (Kind::Struct(_, mine), Kind::Struct(_, theirs)) = (self.kind, other.kind) else {
return false;
};
let (tail, other_tail) = (self.tail_shape(), other.tail_shape());
if mine.is_empty()
|| mine.len() != theirs.len()
|| self.size != other.size
|| self.tail != other.tail
|| self.unsized_ != other.unsized_
|| tail.start != other_tail.start
|| tail.bytes != other_tail.bytes
|| tail.len != other_tail.len
|| tail.array != other_tail.array
{
return false;
}
let mut i = 0;
while i < mine.len() {
if !mine[i].equals(&theirs[i]) {
return false;
}
i += 1;
}
true
}
#[expect(
clippy::many_single_char_names,
reason = "`a` and `x` are parts of `self`, `b` and `y` the same parts of `other`"
)]
pub(crate) const fn equals(&self, other: &Layout) -> bool {
if self.size != other.size
|| self.align != other.align
|| self.tail != other.tail
|| self.unsized_ != other.unsized_
{
return false;
}
match (self.kind, other.kind) {
(Kind::Scalar(a), Kind::Scalar(b)) => {
!a.may_be_uninit()
&& a.size == b.size
&& same_valid(a.valid, b.valid, a.endian, b.endian)
&& same_valid(a.known, b.known, a.endian, b.endian)
}
(Kind::Array(a, n), Kind::Array(b, m)) => n == m && a.equals(b),
(Kind::Slice(a), Kind::Slice(b)) => a.equals(b),
(Kind::Struct(a, ra), Kind::Struct(b, rb)) => {
if a.len() != b.len() || ra.len() != rb.len() {
return false;
}
let mut i = 0;
while i < a.len() {
if a[i].offset != b[i].offset || !a[i].layout.equals(b[i].layout) {
return false;
}
i += 1;
}
let mut i = 0;
while i < ra.len() {
if !ra[i].equals(&rb[i]) {
return false;
}
i += 1;
}
true
}
(Kind::Pattern(a), Kind::Pattern(b)) => a.id == b.id && a.same(b),
(Kind::Pointer(a), Kind::Pointer(b)) => a.same(&b),
(Kind::Enum(a), Kind::Enum(b)) => {
if a.tag.offset != b.tag.offset
|| a.union != b.union
|| !a.tag.layout.equals(b.tag.layout)
|| a.variants.len() != b.variants.len()
{
return false;
}
let mut i = 0;
while i < a.variants.len() {
let (x, y) = (&a.variants[i], &b.variants[i]);
if !x.tags().equals(&y.tags()) || x.holds_tag != y.holds_tag || !x.layout.equals(y.layout)
{
return false;
}
i += 1;
}
true
}
_ => false,
}
}
}
#[expect(
clippy::many_single_char_names,
reason = "`a` and `x` are of one scalar, `b` and `y` the same of the other"
)]
const fn same_valid(a: Valid, b: Valid, endian_a: Endian, endian_b: Endian) -> bool {
match (a, b) {
(Valid::Uninit, Valid::Uninit) | (Valid::Any, Valid::Any) => true,
(Valid::In(x), Valid::In(y)) => {
let mut i = 0;
while i < x.len() && i < y.len() && x[i].0 == y[i].0 && x[i].1 == y[i].1 {
i += 1;
}
endian_a.equals(endian_b) && x.len() == y.len() && i == x.len()
}
_ => false,
}
}
#[derive(Debug, PartialEq, Eq)]
pub struct Dfa {
pub id: u32,
pub states: &'static [DfaState],
}
#[derive(Debug, PartialEq, Eq)]
pub struct DfaState {
pub accept: bool,
pub edges: &'static [(u8, u8, u8)],
}
impl Dfa {
pub const UTF8: &'static Dfa = &Dfa {
id: 1,
states: &[
DfaState {
accept: true,
edges: &[
(0x00, 0x7f, 0),
(0xc2, 0xdf, 1),
(0xe0, 0xe0, 4),
(0xe1, 0xec, 2),
(0xed, 0xed, 5),
(0xee, 0xef, 2),
(0xf0, 0xf0, 6),
(0xf1, 0xf3, 3),
(0xf4, 0xf4, 7),
],
},
DfaState { accept: false, edges: &[(0x80, 0xbf, 0)] },
DfaState { accept: false, edges: &[(0x80, 0xbf, 1)] },
DfaState { accept: false, edges: &[(0x80, 0xbf, 2)] },
DfaState { accept: false, edges: &[(0xa0, 0xbf, 1)] },
DfaState { accept: false, edges: &[(0x80, 0x9f, 1)] },
DfaState { accept: false, edges: &[(0x90, 0xbf, 2)] },
DfaState { accept: false, edges: &[(0x80, 0x8f, 2)] },
],
};
pub const ASCII: &'static Dfa =
&Dfa { id: 2, states: &[DfaState { accept: true, edges: &[(0x00, 0x7f, 0)] }] };
pub const DIGITS: &'static Dfa =
&Dfa { id: 3, states: &[DfaState { accept: true, edges: &[(b'0', b'9', 0)] }] };
pub const OCTAL: &'static Dfa =
&Dfa { id: 4, states: &[DfaState { accept: true, edges: &[(b'0', b'7', 0)] }] };
pub const HEX: &'static Dfa = &Dfa {
id: 5,
states: &[DfaState {
accept: true,
edges: &[(b'0', b'9', 0), (b'A', b'F', 0), (b'a', b'f', 0)],
}],
};
pub const UTF8_NO_NUL: &'static Dfa = &Dfa {
id: 6,
states: &[
DfaState {
accept: true,
edges: &[
(0x01, 0x7f, 0),
(0xc2, 0xdf, 1),
(0xe0, 0xe0, 4),
(0xe1, 0xec, 2),
(0xed, 0xed, 5),
(0xee, 0xef, 2),
(0xf0, 0xf0, 6),
(0xf1, 0xf3, 3),
(0xf4, 0xf4, 7),
],
},
DfaState { accept: false, edges: &[(0x80, 0xbf, 0)] },
DfaState { accept: false, edges: &[(0x80, 0xbf, 1)] },
DfaState { accept: false, edges: &[(0x80, 0xbf, 2)] },
DfaState { accept: false, edges: &[(0xa0, 0xbf, 1)] },
DfaState { accept: false, edges: &[(0x80, 0x9f, 1)] },
DfaState { accept: false, edges: &[(0x90, 0xbf, 2)] },
DfaState { accept: false, edges: &[(0x80, 0x8f, 2)] },
],
};
pub(crate) const fn same(&self, other: &Dfa) -> bool {
if self.states.len() != other.states.len() {
return false;
}
let mut state = 0;
while state < self.states.len() {
let (ours, theirs) = (&self.states[state], &other.states[state]);
if ours.accept != theirs.accept || ours.edges.len() != theirs.edges.len() {
return false;
}
let mut edge = 0;
while edge < ours.edges.len() {
let (first, second) = (ours.edges[edge], theirs.edges[edge]);
if first.0 != second.0 || first.1 != second.1 || first.2 != second.2 {
return false;
}
edge += 1;
}
state += 1;
}
true
}
pub(crate) const fn accepts_bytes(&self, bytes: &[u8]) -> bool {
let (mut state, mut i) = (0, 0);
'bytes: while i < bytes.len() {
let (edges, mut j) = (self.states[state].edges, 0);
while j < edges.len() {
if edges[j].0 <= bytes[i] && bytes[i] <= edges[j].1 {
state = edges[j].2 as usize;
i += 1;
continue 'bytes;
}
j += 1;
}
return false;
}
self.states[state].accept
}
const fn check(&self) {
assert!(!self.states.is_empty() && self.states.len() <= 64, "a DFA has 1 to 64 states");
let mut i = 0;
while i < self.states.len() {
let (edges, mut j) = (self.states[i].edges, 0);
while j < edges.len() {
assert!(edges[j].0 <= edges[j].1 && (edges[j].2 as usize) < self.states.len());
assert!(j == 0 || edges[j - 1].1 < edges[j].0, "DFA edges must be sorted and disjoint");
j += 1;
}
i += 1;
}
}
pub(crate) const fn step(&self, set: u64, lo: u8, hi: u8) -> (u64, bool) {
let (mut next, mut total, mut state) = (0, true, 0);
while state < self.states.len() {
if set & (1 << state) != 0 {
let (edges, mut need, mut i) = (self.states[state].edges, lo as u16, 0);
while i < edges.len() && need <= hi as u16 {
let (first, last, to) = edges[i];
if last as u16 >= need && first <= hi {
total &= first as u16 <= need;
next |= 1 << to;
need = last as u16 + 1;
}
i += 1;
}
total &= need > hi as u16;
}
state += 1;
}
(next, total)
}
pub(crate) const fn accepts(&self, set: u64) -> bool {
let mut state = 0;
while state < self.states.len() {
if set & (1 << state) != 0 && !self.states[state].accept {
return false;
}
state += 1;
}
true
}
pub(crate) const fn reachable(&self) -> u64 {
let mut set = 1;
loop {
let next = set | self.step(set, 0, 0xff).0;
if next == set {
return set;
}
set = next;
}
}
pub(crate) const fn is_utf8(&self) -> bool {
self.id == Self::UTF8.id && self.same(Self::UTF8)
}
#[inline]
pub(crate) const unsafe fn matches(&self, ptr: *const u8, len: usize) -> bool {
self.accepts_bytes(unsafe { core::slice::from_raw_parts(ptr, len) })
}
#[inline]
pub(crate) const unsafe fn matches_utf8(ptr: *const u8, len: usize) -> bool {
core::str::from_utf8(unsafe { core::slice::from_raw_parts(ptr, len) }).is_ok()
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum Op {
Lit(u128),
Load {
offset: usize,
size: u8,
big: bool,
},
Size,
At {
size: u8,
big: bool,
},
Varint {
form: Varint,
length: bool,
},
Crc32,
Sum16,
Crc(&'static Crc),
CrcZeros(&'static Crc),
Checksum(Checksum),
Matches(&'static Dfa),
Add,
Sub,
Mul,
Div,
Rem,
And,
Or,
Xor,
Shl,
Shr,
Eq,
Ne,
Lt,
Le,
Gt,
Ge,
Both,
Either,
Shortcut {
either: bool,
len: u16,
},
Not,
Then(u16),
Else(u16),
Select,
Set(u8),
Get(u8),
Walk {
var: u8,
cond: &'static [Op],
next: &'static [Op],
},
}
#[doc(hidden)]
#[diagnostic::on_unimplemented(
message = "a constant of `#[pun(..)]` is an unsigned integer: `{Self}` is not one",
label = "`#[pun(..)]` computes on unsigned integers",
note = "an expression of `#[pun(..)]` means what it means in Rust, where every integer is a `u128`"
)]
pub trait Unsigned: Copy + seal::Unsigned {}
mod seal {
pub trait Unsigned {}
}
impl seal::Unsigned for u8 {}
impl seal::Unsigned for u16 {}
impl seal::Unsigned for u32 {}
impl seal::Unsigned for u64 {}
impl seal::Unsigned for u128 {}
impl seal::Unsigned for usize {}
impl Unsigned for u8 {}
impl Unsigned for u16 {}
impl Unsigned for u32 {}
impl Unsigned for u64 {}
impl Unsigned for u128 {}
impl Unsigned for usize {}
impl Op {
#[doc(hidden)]
#[must_use]
pub const fn matches(dfa: &'static Dfa) -> Self {
dfa.check();
Op::Matches(dfa)
}
#[doc(hidden)]
pub const USIZE_MAX: u128 = usize::MAX as u128;
#[doc(hidden)]
#[must_use]
pub const fn constant<T: Unsigned>(value: &T) -> u128 {
unsafe { load(core::ptr::from_ref::<T>(value).cast(), size_of::<T>(), Endian::NATIVE) }
}
#[must_use]
pub const fn load<T: crate::Pun>(offset: usize) -> Self {
let Some(spec) = T::LAYOUT.as_integer() else {
panic!(
"a rule reads the unsigned integer fields of its struct, and this field is not one (a \
signed or floating-point number, a `bool`, a `char` or an enum is not): read its bytes \
with `le(offset, size)` or `be(offset, size)`"
)
};
Op::Load { offset, size: spec.size as u8, big: !spec.endian.is_little() }
}
#[expect(
clippy::many_single_char_names,
reason = "`a`, `b`, `c` of one side are compared with `x`, `y`, `z` of the other"
)]
const fn equals(&self, other: &Op) -> bool {
match (*self, *other) {
(Op::Lit(a), Op::Lit(b)) => a == b,
(Op::Load { offset: a, size: b, big: c }, Op::Load { offset: x, size: y, big: z }) => {
a == x && b == y && c == z
}
(Op::At { size: a, big: b }, Op::At { size: x, big: y }) => a == x && b == y,
(Op::Varint { form: a, length: b }, Op::Varint { form: x, length: y }) => {
a as u8 == x as u8 && b == y
}
(Op::Crc(a), Op::Crc(b)) | (Op::CrcZeros(a), Op::CrcZeros(b)) => a.equals(b),
(Op::Checksum(a), Op::Checksum(b)) => a as u8 == b as u8,
(Op::Matches(a), Op::Matches(b)) => a.same(b),
(Op::Set(a), Op::Set(b)) | (Op::Get(a), Op::Get(b)) => a == b,
(Op::Shortcut { either: a, len: b }, Op::Shortcut { either: x, len: y }) => a == x && b == y,
(Op::Then(a), Op::Then(b)) | (Op::Else(a), Op::Else(b)) => a == b,
(Op::Walk { var: a, cond: b, next: c }, Op::Walk { var: x, cond: y, next: z }) => {
a == x && same_ops(b, y) && same_ops(c, z)
}
(
Op::Lit(_)
| Op::Load { .. }
| Op::At { .. }
| Op::Varint { .. }
| Op::Crc(_)
| Op::CrcZeros(_)
| Op::Checksum(_)
| Op::Matches(_)
| Op::Set(_)
| Op::Get(_)
| Op::Shortcut { .. }
| Op::Then(_)
| Op::Else(_)
| Op::Walk { .. },
_,
)
| (
_,
Op::Lit(_)
| Op::Load { .. }
| Op::At { .. }
| Op::Varint { .. }
| Op::Crc(_)
| Op::CrcZeros(_)
| Op::Checksum(_)
| Op::Matches(_)
| Op::Set(_)
| Op::Get(_)
| Op::Shortcut { .. }
| Op::Then(_)
| Op::Else(_)
| Op::Walk { .. },
) => false,
(a, b) => a.code() == b.code(),
}
}
const fn code(self) -> u8 {
match self {
Op::Lit(_) => 0,
Op::Load { .. } => 1,
Op::Add => 2,
Op::Sub => 3,
Op::Mul => 4,
Op::Div => 5,
Op::Rem => 6,
Op::And => 7,
Op::Or => 8,
Op::Xor => 9,
Op::Shl => 10,
Op::Shr => 11,
Op::Eq => 12,
Op::Ne => 13,
Op::Lt => 14,
Op::Le => 15,
Op::Gt => 16,
Op::Ge => 17,
Op::Both => 18,
Op::Either => 19,
Op::Not => 20,
Op::Size => 21,
Op::At { .. } => 22,
Op::Crc32 => 23,
Op::Sum16 => 24,
Op::Select => 25,
Op::Set(_) => 26,
Op::Get(_) => 27,
Op::Walk { .. } => 28,
Op::Varint { .. } => 30,
Op::Crc(_) => 31,
Op::CrcZeros(_) => 32,
Op::Checksum(_) => 33,
Op::Matches(_) => 34,
Op::Shortcut { .. } => 29,
Op::Then(_) => 35,
Op::Else(_) => 36,
}
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct Crc {
width: u32,
poly: u64,
init: u64,
reflect: bool,
xorout: u64,
tables: Tables,
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
#[expect(
clippy::large_enum_variant,
reason = "a `Crc` is a constant of 32 KiB, as it was with tables of `u64`s only: nothing to box"
)]
enum Tables {
Narrow([[u32; 256]; CRC_TABLES]),
Wide([[u64; 256]; CRC_TABLES]),
}
pub(crate) const CRC_TABLES: usize = if cfg!(target_pointer_width = "16") { 1 } else { 16 };
const _: () = assert!(size_of::<[[u64; 256]; CRC_TABLES]>() <= isize::MAX as usize);
impl Crc {
pub const CRC32: Self = Self::new(32, 0x04c1_1db7, 0xffff_ffff, true, 0xffff_ffff);
#[must_use]
#[expect(clippy::large_stack_arrays, reason = "made in const evaluation, as a constant")]
pub const fn new(width: u32, poly: u64, init: u64, reflect: bool, xorout: u64) -> Self {
assert!(width >= 1 && width <= 64, "a CRC has 1 to 64 bits");
let mask = u64::MAX >> (64 - width);
assert!(
poly <= mask && init <= mask && xorout <= mask,
"a parameter has more bits than the CRC"
);
let (mut tables, mut i) = ([[0; 256]; CRC_TABLES], 0);
while i < 256 {
let mut register = if reflect { i as u64 } else { (i as u64) << 56 };
let mut bit = 0;
while bit < 8 {
register = match (reflect, register & 1, register >> 63) {
(true, 1, _) => (register >> 1) ^ (poly.reverse_bits() >> (64 - width)),
(true, ..) => register >> 1,
(false, _, 1) => (register << 1) ^ (poly << (64 - width)),
(false, ..) => register << 1,
};
bit += 1;
}
tables[0][i] = register;
i += 1;
}
let mut k = 1;
while k < CRC_TABLES {
let mut i = 0;
while i < 256 {
let register = tables[k - 1][i];
tables[k][i] = if reflect {
tables[0][(register & 0xff) as usize] ^ (register >> 8)
} else {
tables[0][(register >> 56) as usize] ^ (register << 8)
};
i += 1;
}
k += 1;
}
let tables = if width > 32 {
Tables::Wide(tables)
} else {
let (mut narrow, mut k) = ([[0; 256]; CRC_TABLES], 0);
while k < CRC_TABLES {
let mut i = 0;
while i < 256 {
narrow[k][i] = if reflect { tables[k][i] as u32 } else { (tables[k][i] >> 32) as u32 };
i += 1;
}
k += 1;
}
Tables::Narrow(narrow)
};
Self { width, poly, init, reflect, xorout, tables }
}
#[must_use]
pub const fn check(&self, bytes: &[u8]) -> u64 {
self.compute(bytes, (0, 0))
}
#[inline]
pub(crate) const fn compute(&self, bytes: &[u8], zeros: (usize, usize)) -> u64 {
let mut register = if self.reflect {
self.init.reverse_bits() >> (64 - self.width)
} else {
self.init << (64 - self.width)
};
let to = if zeros.1 < bytes.len() { zeros.1 } else { bytes.len() };
let from = if zeros.0 < to { zeros.0 } else { to };
let (before, rest) = bytes.split_at(from);
let (zeros, after) = rest.split_at(to - from);
register = self.update(register, before);
let mut zeros = zeros.len();
while zeros > 0 {
let count = if zeros < 64 { zeros } else { 64 };
register = self.update(register, [0; 64].split_at(count).0);
zeros -= count;
}
register = self.update(register, after);
if !self.reflect {
register >>= 64 - self.width;
}
register ^ self.xorout
}
#[inline]
const fn update(&self, register: u64, bytes: &[u8]) -> u64 {
match &self.tables {
Tables::Narrow(t) => {
let narrow = if self.reflect { register as u32 } else { (register >> 32) as u32 };
let narrow = Self::update_narrow(t, self.reflect, narrow, bytes);
if self.reflect { narrow as u64 } else { (narrow as u64) << 32 }
}
Tables::Wide(t) => Self::update_wide(t, self.reflect, register, bytes),
}
}
#[inline]
const fn update_narrow(
t: &[[u32; 256]; CRC_TABLES],
reflect: bool,
mut register: u32,
bytes: &[u8],
) -> u32 {
let (blocks, rest): (&[[u8; 16]], &[u8]) =
if CRC_TABLES == 16 { bytes.as_chunks::<16>() } else { (&[], bytes) };
#[cfg(target_pointer_width = "16")]
let t: &[[u32; 256]] = t;
let mut i = 0;
while i < blocks.len() {
let b = &blocks[i];
let head = [b[0], b[1], b[2], b[3]];
let x = register ^ if reflect { u32::from_le_bytes(head) } else { u32::from_be_bytes(head) };
let x = if reflect { x.to_le_bytes() } else { x.to_be_bytes() };
register = t[15][x[0] as usize]
^ t[14][x[1] as usize]
^ t[13][x[2] as usize]
^ t[12][x[3] as usize]
^ t[11][b[4] as usize]
^ t[10][b[5] as usize]
^ t[9][b[6] as usize]
^ t[8][b[7] as usize]
^ t[7][b[8] as usize]
^ t[6][b[9] as usize]
^ t[5][b[10] as usize]
^ t[4][b[11] as usize]
^ t[3][b[12] as usize]
^ t[2][b[13] as usize]
^ t[1][b[14] as usize]
^ t[0][b[15] as usize];
i += 1;
}
let mut i = 0;
while i < rest.len() {
register = if reflect {
t[0][((register ^ rest[i] as u32) & 0xff) as usize] ^ (register >> 8)
} else {
t[0][((register >> 24) ^ rest[i] as u32) as usize] ^ (register << 8)
};
i += 1;
}
register
}
#[inline]
const fn update_wide(
t: &[[u64; 256]; CRC_TABLES],
reflect: bool,
mut register: u64,
bytes: &[u8],
) -> u64 {
let (blocks, rest): (&[[u8; 16]], &[u8]) =
if CRC_TABLES == 16 { bytes.as_chunks::<16>() } else { (&[], bytes) };
#[cfg(target_pointer_width = "16")]
let t: &[[u64; 256]] = t;
let mut i = 0;
while i < blocks.len() {
let b = &blocks[i];
let head = [b[0], b[1], b[2], b[3], b[4], b[5], b[6], b[7]];
let x = register ^ if reflect { u64::from_le_bytes(head) } else { u64::from_be_bytes(head) };
let x = if reflect { x.to_le_bytes() } else { x.to_be_bytes() };
register = t[15][x[0] as usize]
^ t[14][x[1] as usize]
^ t[13][x[2] as usize]
^ t[12][x[3] as usize]
^ t[11][x[4] as usize]
^ t[10][x[5] as usize]
^ t[9][x[6] as usize]
^ t[8][x[7] as usize]
^ t[7][b[8] as usize]
^ t[6][b[9] as usize]
^ t[5][b[10] as usize]
^ t[4][b[11] as usize]
^ t[3][b[12] as usize]
^ t[2][b[13] as usize]
^ t[1][b[14] as usize]
^ t[0][b[15] as usize];
i += 1;
}
let mut i = 0;
while i < rest.len() {
register = if reflect {
t[0][((register ^ rest[i] as u64) & 0xff) as usize] ^ (register >> 8)
} else {
t[0][((register >> 56) ^ rest[i] as u64) as usize] ^ (register << 8)
};
i += 1;
}
register
}
#[cfg(test)]
pub(crate) fn bytewise(&self, bytes: &[u8]) -> u64 {
let mut register = if self.reflect {
self.init.reverse_bits() >> (64 - self.width)
} else {
self.init << (64 - self.width)
};
let t = |i: u64| match &self.tables {
Tables::Narrow(t) if self.reflect => u64::from(t[0][i as usize]),
Tables::Narrow(t) => u64::from(t[0][i as usize]) << 32,
Tables::Wide(t) => t[0][i as usize],
};
for &byte in bytes {
register = if self.reflect {
t((register ^ u64::from(byte)) & 0xff) ^ (register >> 8)
} else {
t((register >> 56) ^ u64::from(byte)) ^ (register << 8)
};
}
if !self.reflect {
register >>= 64 - self.width;
}
register ^ self.xorout
}
const fn equals(&self, other: &Crc) -> bool {
self.width == other.width
&& self.poly == other.poly
&& self.init == other.init
&& self.reflect == other.reflect
&& self.xorout == other.xorout
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum Checksum {
Sum,
Fletcher16,
Adler32,
}
impl Checksum {
const fn compute(self, bytes: &[u8]) -> u128 {
let (modulo, mut first, mut second, mut i) = match self {
Checksum::Sum => (0, 0u128, 0u128, 0),
Checksum::Fletcher16 => (255, 0, 0, 0),
Checksum::Adler32 => (65521, 1, 0, 0),
};
while i < bytes.len() {
first += bytes[i] as u128;
if modulo > 0 {
first %= modulo;
second = (second + first) % modulo;
}
i += 1;
}
match self {
Checksum::Sum => first,
Checksum::Fletcher16 => second << 8 | first,
Checksum::Adler32 => second << 16 | first,
}
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum Varint {
Leb128,
Quic,
Vlq,
}
impl Varint {
#[inline]
const unsafe fn read(self, ptr: *const u8, size: usize) -> Option<(u128, usize)> {
let bytes = unsafe { core::slice::from_raw_parts(ptr, size) };
if matches!(self, Varint::Quic) {
if bytes.is_empty() {
return None;
}
let length = 1 << (bytes[0] >> 6);
if bytes.len() < length {
return None;
}
let (mut value, mut i) = ((bytes[0] & 0x3f) as u128, 1);
while i < length {
value = value << 8 | bytes[i] as u128;
i += 1;
}
return Some((value, length));
}
let (mut value, mut i) = (0u128, 0);
while i < bytes.len() {
let bits = (bytes[i] & 0x7f) as u128;
match self {
Varint::Leb128 if i < 18 || (i == 18 && bits < 4) => value |= bits << (7 * i),
Varint::Vlq if value >> 121 == 0 => value = value << 7 | bits,
_ => return None,
}
i += 1;
if bytes[i - 1] & 0x80 == 0 {
return Some((value, i));
}
}
None
}
}
const fn cheap_ops(ops: &[Op]) -> bool {
let mut i = 0;
while i < ops.len() {
if matches!(
ops[i],
Op::At { .. }
| Op::Varint { .. }
| Op::Crc32
| Op::Sum16
| Op::Crc(_)
| Op::CrcZeros(_)
| Op::Checksum(_)
| Op::Matches(_)
| Op::Walk { .. }
| Op::Div
| Op::Rem
) {
return false;
}
i += 1;
}
true
}
pub(crate) const fn same_ops(a: &[Op], b: &[Op]) -> bool {
let mut i = 0;
while i < a.len() && i < b.len() && a[i].equals(&b[i]) {
i += 1;
}
a.len() == b.len() && i == a.len()
}
#[derive(Copy, Clone, Debug)]
pub enum Rule {
Size(&'static [Op]),
Len(&'static [Op]),
Assert(&'static [Op]),
Region(Option<&'static [Op]>),
}
const fn ops_read_bytes(ops: &[Op]) -> bool {
let mut i = 0;
while i < ops.len() {
match ops[i] {
Op::At { .. }
| Op::Varint { .. }
| Op::Crc32
| Op::Sum16
| Op::Crc(_)
| Op::CrcZeros(_)
| Op::Checksum(_)
| Op::Matches(_) => return true,
Op::Walk { cond, next, .. } if ops_read_bytes(cond) || ops_read_bytes(next) => return true,
_ => {}
}
i += 1;
}
false
}
impl Rule {
pub(crate) const fn ops(&self) -> Option<&'static [Op]> {
match *self {
Rule::Size(ops) | Rule::Len(ops) | Rule::Assert(ops) | Rule::Region(Some(ops)) => Some(ops),
Rule::Region(None) => None,
}
}
pub(crate) const fn equals(&self, other: &Rule) -> bool {
let same_kind = matches!(
(self, other),
(Rule::Size(_), Rule::Size(_))
| (Rule::Len(_), Rule::Len(_))
| (Rule::Assert(_), Rule::Assert(_))
| (Rule::Region(_), Rule::Region(_))
);
match (self.ops(), other.ops()) {
(None, None) => same_kind,
(Some(a), Some(b)) => same_kind && same_ops(a, b),
_ => false,
}
}
}
#[derive(Copy, Clone)]
pub(crate) struct TailShape {
pub(crate) start: usize,
pub(crate) bytes: usize,
pub(crate) len: usize,
pub(crate) array: bool,
}
#[derive(Copy, Clone)]
pub(crate) struct LengthRule {
pub(crate) base: usize,
pub(crate) elements: bool,
pub(crate) ops: &'static [Op],
}
pub(crate) const STACK: usize = 16;
pub(crate) const VARIABLES: usize = 8;
pub(crate) const MAX_OPS: usize = 256;
pub(crate) const MAX_WALKS: usize = 4;
const fn check_rules(rules: &[Rule], head: usize) {
let mut i = 0;
while i < rules.len() {
if let Some(ops) = rules[i].ops() {
let sizes = matches!(rules[i], Rule::Size(_) | Rule::Len(_));
check_ops(ops, head, sizes, 0, 0);
}
i += 1;
}
}
pub(crate) const fn op_at(ops: &[Op], index: usize) -> Option<Op> {
if index < ops.len() { Some(ops[index]) } else { None }
}
pub(crate) const fn check_ops(ops: &[Op], head: usize, sizes: bool, mut defined: u8, walks: usize) {
assert!(ops.len() <= MAX_OPS, "an expression is too long");
let (mut depth, mut i) = (0usize, 0);
let (mut parts, mut open) = ([(0usize, 0usize, 0u8, Op::Size); STACK], 0);
while i < ops.len() {
let op = ops[i];
assert!(
!(sizes && matches!(op, Op::Size)),
"a size or a length cannot be computed from `size_of_val(self)`, which it defines"
);
let ends = open > 0 && parts[open - 1].0 == i;
if ends {
let (_, floor, before, opener) = parts[open - 1];
assert!(depth == floor + 1, "malformed expression");
let fits = match (opener, op) {
(Op::Shortcut { either, .. }, Op::Both) => !either,
(Op::Shortcut { either, .. }, Op::Either) => either,
(Op::Then(_), Op::Else(_)) | (Op::Else(_), Op::Select) => true,
_ => false,
};
assert!(fits, "malformed expression");
(open, defined) = (open - 1, before);
} else {
assert!(
!matches!(op, Op::Both | Op::Either | Op::Else(_) | Op::Select),
"malformed expression"
);
}
let (pops, pushes) = effect(op);
assert!(depth >= pops, "malformed expression");
assert!(open == 0 || depth - pops >= parts[open - 1].1, "malformed expression");
if let Op::Shortcut { len, .. } | Op::Then(len) | Op::Else(len) = op {
let end = i + len as usize + matches!(op, Op::Else(_)) as usize;
assert!(depth >= 1 && len >= 1 && end < ops.len(), "malformed expression");
assert!(open == 0 || end < parts[open - 1].0, "malformed expression");
assert!(open < STACK, "expression is too deep");
parts[open] = (end, depth, defined, op);
open += 1;
}
match op {
Op::At { size, .. } => assert!(size >= 1 && size <= 16, "malformed expression"),
Op::Load { offset, size, .. } => {
assert!(size >= 1 && size <= 16 && offset + size as usize <= head, "field out of bounds");
}
Op::Set(index) => {
assert!((index as usize) < VARIABLES, "too many variables in an expression");
defined |= 1 << index;
}
Op::Get(index) => {
assert!((index as usize) < VARIABLES && defined & (1 << index) != 0, "no such variable");
}
Op::Walk { var, cond, next } => {
assert!(walks < MAX_WALKS, "walks are nested too deeply");
assert!((var as usize) < VARIABLES, "too many variables in an expression");
check_ops(cond, head, sizes, defined | 1 << var, walks + 1);
check_ops(next, head, sizes, defined | 1 << var, walks + 1);
}
_ => {}
}
depth = depth - pops + pushes;
assert!(depth <= STACK, "expression is too deep");
i += 1;
}
assert!(depth == 1 && open == 0, "malformed expression");
}
const fn effect(op: Op) -> (usize, usize) {
match op {
Op::Lit(_) | Op::Load { .. } | Op::Size | Op::Get(_) => (0, 1),
Op::At { .. }
| Op::Varint { .. }
| Op::Not
| Op::Walk { .. }
| Op::Shortcut { .. }
| Op::Then(_) => (1, 1),
Op::Else(_) => (0, 0),
Op::Set(_) => (1, 0),
Op::Select => (3, 1),
Op::CrcZeros(_) => (4, 1),
Op::Crc32
| Op::Sum16
| Op::Crc(_)
| Op::Checksum(_)
| Op::Matches(_)
| Op::Add
| Op::Sub
| Op::Mul
| Op::Div
| Op::Rem
| Op::And
| Op::Or
| Op::Xor
| Op::Shl
| Op::Shr
| Op::Eq
| Op::Ne
| Op::Lt
| Op::Le
| Op::Gt
| Op::Ge
| Op::Both
| Op::Either => (2, 1),
}
}
#[derive(Copy, Clone)]
pub(crate) struct Machine {
stack: Stack,
variables: Variables,
depth: usize,
skip: usize,
}
macro_rules! slots {
($($name:ident: [$($index:tt)+] $last:tt)+) => {$(
#[derive(Copy, Clone)]
struct $name($(slots!(@u128 $index),)+ u128);
impl $name {
const NEW: Self = Self($(slots!(@zero $index),)+ 0);
#[inline(always)]
const fn get(&self, index: usize) -> u128 {
match index {
$($index => self.$index,)+
_ => self.$last,
}
}
#[inline(always)]
const fn set(&mut self, index: usize, value: u128) {
match index {
$($index => self.$index = value,)+
_ => self.$last = value,
}
}
}
)+};
(@u128 $index:tt) => { u128 };
(@zero $index:tt) => { 0 };
}
slots! {
Stack: [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14] 15
Variables: [0 1 2 3 4 5 6] 7
}
impl Machine {
pub(crate) const NEW: Self =
Self { stack: Stack::NEW, variables: Variables::NEW, depth: 0, skip: 0 };
#[inline(always)]
const fn get(&self, slot: usize) -> u128 {
self.stack.get(slot)
}
#[inline(always)]
const fn set(&mut self, slot: usize, value: u128) {
self.stack.set(slot, value);
}
#[inline(always)]
const fn push(&mut self, value: u128) {
self.stack.set(self.depth, value);
self.depth += 1;
}
#[inline(always)]
pub(crate) const fn computes(&self, at: usize) -> bool {
at >= self.skip
}
#[inline(always)]
pub(crate) const fn result(&self) -> u128 {
self.get(0)
}
#[inline(always)]
pub(crate) const fn top(&self) -> u128 {
self.get(self.depth - 1)
}
#[must_use]
#[inline(always)]
pub(crate) const fn replace(&mut self, value: Option<u128>) -> bool {
match value {
Some(value) => {
self.set(self.depth - 1, value);
true
}
None => false,
}
}
#[inline(always)]
pub(crate) const fn enter(&self, index: u8, value: u128) -> Self {
let mut inner = Self { depth: 0, skip: 0, ..*self };
inner.variables.set(index as usize, value);
inner
}
#[must_use]
#[cfg_attr(not(debug_assertions), inline(always))]
pub(crate) const unsafe fn apply(
&mut self,
op: Op,
at: usize,
how: How,
base: *const u8,
size: usize,
) -> bool {
if !self.computes(at) {
return true;
}
let depth = self.depth;
match op {
Op::Lit(value) => self.push(value),
Op::Load { offset, size, big } => {
let endian = if big { Endian::Big } else { Endian::Little };
self.push(unsafe { load(base.add(offset), size as usize, endian) });
}
Op::Size => self.push(size as u128),
Op::Get(index) => self.push(fit(self.variables.get(index as usize), how.result)),
Op::Set(index) => {
self.variables.set(index as usize, self.get(depth - 1));
self.depth -= 1;
}
Op::Not => self.set(depth - 1, (self.get(depth - 1) == 0) as u128),
Op::Varint { form, length } => {
let offset = self.get(depth - 1);
let value = if offset <= size as u128 {
match unsafe { form.read(base.add(offset as usize), size - offset as usize) } {
Some((value, bytes)) => Some(if length { bytes as u128 } else { value }),
None => None,
}
} else {
None
};
return self.replace(value);
}
Op::At { size: width, big } => {
let (offset, endian) =
(self.get(depth - 1), if big { Endian::Big } else { Endian::Little });
if size >= width as usize && offset <= (size - width as usize) as u128 {
self.set(depth - 1, unsafe { load(base.add(offset as usize), width as usize, endian) });
} else {
return false;
}
}
op @ (Op::Crc32
| Op::Sum16
| Op::Crc(_)
| Op::CrcZeros(_)
| Op::Checksum(_)
| Op::Matches(_)) => {
let operands = if matches!(op, Op::CrcZeros(_)) { 4 } else { 2 };
let (start, end) = (self.get(depth - operands), self.get(depth - operands + 1));
let (zeros, to) =
if operands == 4 { (self.get(depth - 2), self.get(depth - 1)) } else { (0, 0) };
self.depth -= operands - 1;
if start <= end && end <= size as u128 && zeros <= to && to <= size as u128 {
let bytes = unsafe {
core::slice::from_raw_parts(base.add(start as usize), (end - start) as usize)
};
let zeros = (zeros.saturating_sub(start) as usize, to.saturating_sub(start) as usize);
let value = match op {
Op::Crc32 => crc32_inline(bytes) as u128,
Op::Sum16 => sum16_inline(bytes) as u128,
Op::Crc(crc) | Op::CrcZeros(crc) => crc.compute(bytes, zeros) as u128,
Op::Checksum(checksum) => checksum.compute(bytes),
Op::Matches(dfa) => dfa.accepts_bytes(bytes) as u128,
_ => 0,
};
self.set(depth - operands, value);
} else {
return false;
}
}
Op::Shortcut { either, len } => {
if (self.get(depth - 1) != 0) == either {
self.set(depth - 1, either as u128);
self.skip = at + 1 + len as usize;
}
}
Op::Then(len) => {
if self.get(depth - 1) == 0 {
self.push(0);
self.skip = at + 1 + len as usize;
}
}
Op::Else(len) => {
self.push(0);
self.skip = at + 1 + len as usize;
}
Op::Both | Op::Either => {
self.set(depth - 2, (self.get(depth - 1) != 0) as u128);
self.depth -= 1;
}
Op::Select => {
let value =
if self.get(depth - 3) != 0 { self.get(depth - 2) } else { self.get(depth - 1) };
self.set(depth - 3, fit(value, how.result));
self.depth -= 2;
}
Op::Walk { .. } => return false,
op => {
match narrow::binary(op, how, self.get(depth - 2), self.get(depth - 1)) {
Some(value) => self.set(depth - 2, fit(value, how.result)),
None => return false,
}
self.depth -= 1;
}
}
true
}
}
const _: () = assert!(isize::MAX as usize <= usize::MAX - 16);
#[inline(always)]
pub(crate) const fn walk_limit(size: usize) -> usize {
(size + 16).saturating_mul(8)
}
#[inline(always)]
pub(crate) const fn binary(op: Op, a: u128, b: u128) -> Option<u128> {
match op {
Op::Add => a.checked_add(b),
Op::Sub => a.checked_sub(b),
Op::Mul => a.checked_mul(b),
Op::Div => a.checked_div(b),
Op::Rem => a.checked_rem(b),
Op::And => Some(a & b),
Op::Or => Some(a | b),
Op::Xor => Some(a ^ b),
Op::Shl => {
if b < 128 {
Some(a << b)
} else {
None
}
}
Op::Shr => {
if b < 128 {
Some(a >> b)
} else {
None
}
}
Op::Eq => Some((a == b) as u128),
Op::Ne => Some((a != b) as u128),
Op::Lt => Some((a < b) as u128),
Op::Le => Some((a <= b) as u128),
Op::Gt => Some((a > b) as u128),
Op::Ge => Some((a >= b) as u128),
Op::Lit(_)
| Op::Load { .. }
| Op::Size
| Op::Not
| Op::At { .. }
| Op::Varint { .. }
| Op::Crc32
| Op::Sum16
| Op::Crc(_)
| Op::CrcZeros(_)
| Op::Checksum(_)
| Op::Matches(_)
| Op::Both
| Op::Either
| Op::Select
| Op::Set(_)
| Op::Get(_)
| Op::Shortcut { .. }
| Op::Then(_)
| Op::Else(_)
| Op::Walk { .. } => None,
}
}
#[must_use]
pub const fn crc32(bytes: &[u8]) -> u32 {
crc32_inline(bytes)
}
#[inline(always)]
const fn crc32_inline(bytes: &[u8]) -> u32 {
const TABLES: [[u32; 256]; 16] = {
let mut tables = [[0u32; 256]; 16];
let mut i = 0;
while i < 256 {
let (mut value, mut bit) = (i as u32, 0);
while bit < 8 {
value = if value & 1 != 0 { (value >> 1) ^ 0xedb8_8320 } else { value >> 1 };
bit += 1;
}
tables[0][i] = value;
i += 1;
}
let mut k = 1;
while k < 16 {
let mut i = 0;
while i < 256 {
let value = tables[k - 1][i];
tables[k][i] = tables[0][(value & 0xff) as usize] ^ (value >> 8);
i += 1;
}
k += 1;
}
tables
};
let (blocks, rest) = bytes.as_chunks::<16>();
let (t, mut crc, mut i) = (&TABLES, !0u32, 0);
while i < blocks.len() {
let b = &blocks[i];
let x = (crc ^ u32::from_le_bytes([b[0], b[1], b[2], b[3]])).to_le_bytes();
crc = t[15][x[0] as usize]
^ t[14][x[1] as usize]
^ t[13][x[2] as usize]
^ t[12][x[3] as usize]
^ t[11][b[4] as usize]
^ t[10][b[5] as usize]
^ t[9][b[6] as usize]
^ t[8][b[7] as usize]
^ t[7][b[8] as usize]
^ t[6][b[9] as usize]
^ t[5][b[10] as usize]
^ t[4][b[11] as usize]
^ t[3][b[12] as usize]
^ t[2][b[13] as usize]
^ t[1][b[14] as usize]
^ t[0][b[15] as usize];
i += 1;
}
let mut i = 0;
while i < rest.len() {
crc = t[0][((crc ^ rest[i] as u32) & 0xff) as usize] ^ (crc >> 8);
i += 1;
}
!crc
}
#[must_use]
pub const fn sum16(bytes: &[u8]) -> u16 {
sum16_inline(bytes)
}
const SUM16_FOLD: usize = if usize::BITS > 20 { 1 << (20 % usize::BITS) } else { usize::MAX };
const _: () = assert!((SUM16_FOLD as u128) << 33 < 1 << 64);
#[inline(always)]
const fn sum16_inline(bytes: &[u8]) -> u16 {
let (mut blocks, rest) = bytes.as_chunks::<8>();
let mut sum = 0u64;
while !blocks.is_empty() {
let (now, later) =
blocks.split_at(if blocks.len() > SUM16_FOLD { SUM16_FOLD } else { blocks.len() });
let (mut wide, mut i) = (0u64, 0);
while i < now.len() {
let block = u64::from_ne_bytes(now[i]);
wide += (block & 0xffff_ffff) + (block >> 32);
i += 1;
}
sum = fold(sum + fold(wide) as u64) as u64;
blocks = later;
}
if cfg!(target_endian = "little") {
sum = (sum as u16).swap_bytes() as u64;
}
let mut i = 0;
while i < rest.len() {
let low = if i + 1 < rest.len() { rest[i + 1] } else { 0 };
sum += ((rest[i] as u64) << 8) | low as u64;
i += 2;
}
fold(sum)
}
#[inline(always)]
const fn fold(mut sum: u64) -> u16 {
while sum > 0xffff {
sum = (sum & 0xffff) + (sum >> 16);
}
sum as u16
}
#[doc(hidden)]
#[must_use]
pub const fn range<T>(start: Option<u128>, end: Option<u128>, inclusive: bool) -> (u128, u128) {
let start = match start {
Some(start) => start,
None => 0,
};
let end = match end {
Some(end) if inclusive => end,
Some(end) => {
assert!(end > start, "empty range");
end - 1
}
None => max_value(size_of::<T>()),
};
assert!(start <= end, "empty range");
(start, end)
}
#[doc(hidden)]
#[must_use]
pub const fn merge_ranges<const N: usize>(
mut ranges: [(u128, u128); N],
) -> ([(u128, u128); N], usize) {
let mut i = 1;
while i < N {
let mut j = i;
while j > 0 && ranges[j - 1].0 > ranges[j].0 {
ranges.swap(j - 1, j);
j -= 1;
}
i += 1;
}
let (mut merged, mut len, mut i) = ([(0, 0); N], 0, 0);
while i < N {
if len > 0 && (ranges[i].0 <= merged[len - 1].1 || ranges[i].0 - merged[len - 1].1 == 1) {
if ranges[i].1 > merged[len - 1].1 {
merged[len - 1].1 = ranges[i].1;
}
} else {
merged[len] = ranges[i];
len += 1;
}
i += 1;
}
(merged, len)
}
#[doc(hidden)]
pub const unsafe fn bits_of<T>(value: &T) -> u128 {
assert!(size_of::<T>() <= 16, "a fieldless enum cannot be larger than 16 bytes");
unsafe { load(core::ptr::from_ref::<T>(value).cast(), size_of::<T>(), Endian::NATIVE) }
}