use core::marker::PhantomData;
use crate::{
Plan, Pun,
analysis::{Exact, Marks, analyze},
layout::{Kind, Layout, Spec, Valid},
ptr, rejects,
validate::Checks,
};
mod sealed {
pub trait Sealed {}
}
pub struct Leaf<T: ?Sized>(PhantomData<T>);
pub struct Pair<A, B>(PhantomData<A>, PhantomData<B>);
pub trait List: sealed::Sealed {
const LEN: usize;
const TREE: Tree;
}
#[derive(Copy, Clone)]
pub struct Tree {
len: usize,
leaf: Option<&'static Layout>,
pair: Option<(&'static Tree, &'static Tree)>,
}
impl<T: ?Sized + Pun> sealed::Sealed for Leaf<T> {}
impl<A: List, B: List> sealed::Sealed for Pair<A, B> {}
impl<T: ?Sized + Pun> List for Leaf<T> {
const LEN: usize = 1;
const TREE: Tree = Tree { len: 1, leaf: Some(&T::LAYOUT), pair: None };
}
impl<A: List, B: List> List for Pair<A, B> {
const LEN: usize = A::LEN + B::LEN;
const TREE: Tree = Tree { len: A::LEN + B::LEN, leaf: None, pair: Some((&A::TREE, &B::TREE)) };
}
pub trait Index: sealed::Sealed {}
pub struct Here;
pub struct First<I>(PhantomData<I>);
pub struct Second<I>(PhantomData<I>);
impl sealed::Sealed for Here {}
impl<I: Index> sealed::Sealed for First<I> {}
impl<I: Index> sealed::Sealed for Second<I> {}
impl Index for Here {}
impl<I: Index> Index for First<I> {}
impl<I: Index> Index for Second<I> {}
pub trait Get<I: Index>: List {
type Type: ?Sized + Pun;
const INDEX: usize;
}
impl<T: ?Sized + Pun> Get<Here> for Leaf<T> {
type Type = T;
const INDEX: usize = 0;
}
impl<A: Get<I>, B: List, I: Index> Get<First<I>> for Pair<A, B> {
type Type = A::Type;
const INDEX: usize = A::INDEX;
}
impl<A: List, B: Get<I>, I: Index> Get<Second<I>> for Pair<A, B> {
type Type = B::Type;
const INDEX: usize = A::LEN + B::INDEX;
}
pub trait Views {
type List: List;
}
const fn layout_at(mut tree: &'static Tree, mut index: usize) -> &'static Layout {
loop {
match (tree.leaf, tree.pair) {
(Some(layout), _) if index == 0 => return layout,
(_, Some((first, _))) if index < first.len => tree = first,
(_, Some((first, second))) => (tree, index) = (second, index - first.len),
_ => panic!("no such variant"),
}
}
}
const NONE: usize = usize::MAX;
struct Choice<V: ?Sized, I>(PhantomData<V>, PhantomData<I>);
impl<V: ?Sized + Views, I: Index> Choice<V, I>
where
V::List: Get<I>,
{
const WHOLE: (usize, Marks) = {
let index = <V::List as Get<I>>::INDEX;
base(&V::List::TREE, index, index + 1, false)
};
const HEAD: (usize, Marks) = {
let (tree, index, whole) = (&V::List::TREE, <V::List as Get<I>>::INDEX, Self::WHOLE);
match whole.0 {
NONE => whole,
j if same_extent(layout_at(tree, index), layout_at(tree, j)) => whole,
j => base(tree, index, j + 1, true),
}
};
const fn base(head: bool) -> usize {
if head { Self::HEAD.0 } else { Self::WHOLE.0 }
}
}
impl<V: ?Sized + Views, I: Index> Checks for Choice<V, I>
where
V::List: Get<I>,
{
const MARKS: Marks = {
let all = <Plan<[u8], <V::List as Get<I>>::Type> as Checks>::MARKS;
let (whole, head) = (Self::WHOLE, Self::HEAD);
let whole = if whole.0 == NONE { all } else { whole.1 };
let head = if head.0 == NONE { all } else { head.1 };
whole.union(&head)
};
}
const fn base(tree: &'static Tree, index: usize, from: usize, head: bool) -> (usize, Marks) {
let layout = layout_at(tree, index);
let mut j = from;
while j < tree.len {
let other = layout_at(tree, j);
if !apart(layout, 0, other) && (!head || same_extent(layout, other)) {
let into = analyze(layout, other);
let relation = into.relation;
let proven = matches!(into.fit.exact, Exact::Always)
&& into.aligned
&& relation.uninit.is_none()
&& relation.disjoint.is_none()
&& relation.partial.is_none()
&& relation.pointer.is_none();
if proven {
let from = analyze(other, layout);
let relation = from.relation;
if !matches!(from.fit.exact, Exact::Never(_))
&& relation.uninit.is_none()
&& relation.disjoint.is_none()
&& relation.pointer.is_none()
{
return (j, relation.marks);
}
}
}
j += 1;
}
(NONE, Marks::NONE)
}
const fn apart(a: &Layout, at: usize, b: &Layout) -> bool {
match a.kind {
Kind::Scalar(spec) => match scalar_at(b, at, spec.size) {
Some(other) => disjoint(&spec, &other),
None => false,
},
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
if apart(fields[i].layout, at + fields[i].offset, b) {
return true;
}
i += 1;
}
false
}
Kind::Array(elem, len) if len > 0 => apart(elem, at, b),
_ => false,
}
}
const fn scalar_at(layout: &Layout, at: usize, size: usize) -> Option<Spec> {
match layout.kind {
Kind::Scalar(spec) if at == 0 && spec.size == size => Some(spec),
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
let field = &fields[i];
if field.offset <= at && at < field.offset + field.layout.size() {
return scalar_at(field.layout, at - field.offset, size);
}
i += 1;
}
None
}
Kind::Array(elem, len) if elem.size() > 0 && at < elem.size() * len => {
scalar_at(elem, at % elem.size(), size)
}
_ => None,
}
}
const fn disjoint(a: &Spec, b: &Spec) -> bool {
let (Valid::In(a_ranges), Valid::In(b_ranges)) = (a.valid, b.valid) else { return false };
if !a.endian.equals(b.endian) {
return false;
}
let (mut i, mut j) = (0, 0);
while i < a_ranges.len() && j < b_ranges.len() {
let ((a_lo, a_hi), (b_lo, b_hi)) = (a_ranges[i], b_ranges[j]);
if a_hi < b_lo {
i += 1;
} else if b_hi < a_lo {
j += 1;
} else {
return false;
}
}
true
}
const fn same_extent(a: &Layout, b: &Layout) -> bool {
const fn told(layout: &Layout) -> bool {
layout.stride() == 0 || layout.length_rule().is_some()
}
match (told(a), told(b)) {
(true, true) => true,
(false, false) => {
a.align() == b.align()
&& a.stride() == b.stride()
&& a.head() % a.stride() == b.head() % b.stride()
}
_ => false,
}
}
const OPEN: u8 = 0;
const NOT: u8 = 1;
const IS: u8 = 2;
pub struct Known<'a, V: ?Sized, const N: usize, const HEAD: bool> {
bytes: &'a [u8],
state: [u8; N],
taken: [(usize, usize); N],
view: PhantomData<fn() -> V>,
}
impl<'a, V: ?Sized + Views, const N: usize, const HEAD: bool> Known<'a, V, N, HEAD> {
#[doc(hidden)]
#[inline(always)]
#[must_use]
pub const fn new(bytes: &'a [u8]) -> Self {
const { assert!(N == V::List::LEN, "one state for each variant") };
Self { bytes, state: [OPEN; N], taken: [(0, 0); N], view: PhantomData }
}
#[doc(hidden)]
#[inline(always)]
#[must_use]
pub const fn rest(&self, index: usize) -> &'a [u8] {
self.bytes.split_at(self.taken[index].1).1
}
}
#[inline(always)]
#[must_use]
pub const fn open<V: ?Sized + Views, I: Index, const N: usize, const HEAD: bool>(
known: &Known<'_, V, N, HEAD>,
) -> bool
where
V::List: Get<I>,
{
known.state[<V::List as Get<I>>::INDEX] == OPEN
&& !rejects::<<V::List as Get<I>>::Type>(known.bytes)
}
#[must_use]
pub const fn base_of<V: ?Sized + Views, I: Index, const HEAD: bool>() -> usize
where
V::List: Get<I>,
{
Choice::<V, I>::base(HEAD)
}
#[inline(always)]
pub const fn decide<'a, V: ?Sized + Views, I: Index, const N: usize, const HEAD: bool>(
known: &mut Known<'a, V, N, HEAD>,
) -> Option<&'a <V::List as Get<I>>::Type>
where
V::List: Get<I>,
{
let index = <V::List as Get<I>>::INDEX;
let value = match known.state[index] {
IS => {
let target = ptr::from_raw_parts(known.bytes.as_ptr(), known.taken[index].0);
return Some(unsafe { &*target });
}
NOT => None,
_ => find::<V, I, N, HEAD>(known),
};
let Some((target, size)) = value else {
known.state[index] = NOT;
return None;
};
(known.state[index], known.taken[index]) = (IS, (ptr::metadata(target), size));
Some(unsafe { &*target })
}
#[inline(always)]
const fn find<V: ?Sized + Views, I: Index, const N: usize, const HEAD: bool>(
known: &Known<'_, V, N, HEAD>,
) -> Option<(*const <V::List as Get<I>>::Type, usize)>
where
V::List: Get<I>,
{
const { Plan::<[u8], <V::List as Get<I>>::Type>::TRY_REF };
let bytes = known.bytes;
if rejects::<<V::List as Get<I>>::Type>(bytes) {
return None;
}
let extent = if const { Choice::<V, I>::base(HEAD) < N } {
let (base, head, stride) = const {
match Choice::<V, I>::base(HEAD) {
NONE => (NONE, 0, 0),
base => {
(base, layout_at(&V::List::TREE, base).head(), layout_at(&V::List::TREE, base).stride())
}
}
};
if known.state[base] != IS {
return None;
}
head + known.taken[base].0 * stride
} else {
usize::MAX
};
unsafe { take::<<V::List as Get<I>>::Type, Choice<V, I>, HEAD>(bytes, extent) }
}
#[inline(always)]
const unsafe fn take<D: ?Sized + Pun, C: Checks, const HEAD: bool>(
bytes: &[u8],
extent: usize,
) -> Option<(*const D, usize)> {
let found = unsafe {
if HEAD {
Plan::<[u8], D>::front_by::<C>(bytes.as_ptr(), bytes.len(), extent)
} else {
match Plan::<[u8], D>::try_cast_by::<C>(bytes) {
Ok(target) => Ok((target, bytes.len())),
Err(error) => Err(error),
}
}
};
match found {
Ok(found) => Some(found),
Err(_) => None,
}
}