use crate::layout::{Dfa, Endian, Kind, Layout, Pointer, Spec, Tags, Uniform, Valid, max_value};
const MAX_DEPTH: usize = 32;
#[derive(Copy, Clone)]
pub enum RunKind {
Pad,
Any,
Atom(Spec),
Pattern(&'static Dfa),
Pointer(Pointer),
}
impl RunKind {
const fn may_be_uninit(&self) -> bool {
match self {
RunKind::Pad => true,
RunKind::Atom(spec) => spec.may_be_uninit(),
RunKind::Any | RunKind::Pattern(_) | RunKind::Pointer(_) => false,
}
}
}
#[derive(Copy, Clone)]
pub struct Run {
kind: RunKind,
start: usize,
end: usize,
leaf: usize,
}
#[derive(Copy, Clone)]
struct Frame {
layout: &'static Layout,
base: usize,
leaf: usize,
field: usize,
}
impl Frame {
const fn end(&self) -> usize {
if self.layout.is_dynamic() { usize::MAX } else { self.base + self.layout.size }
}
}
#[derive(Copy, Clone)]
struct Repeat {
stride: usize,
end: usize,
run: bool,
id: (usize, usize),
}
#[derive(Copy, Clone)]
pub struct Cursor {
stack: [Frame; MAX_DEPTH],
depth: usize,
target: bool,
checked: Checked,
known: Known,
}
const KNOWN: usize = 8;
#[derive(Copy, Clone)]
struct Known {
start: usize,
end: usize,
endian: Endian,
ranges: [(u128, u128); KNOWN],
len: usize,
}
impl Known {
const NONE: Self =
Self { start: 0, end: 0, endian: Endian::Little, ranges: [(0, 0); KNOWN], len: 0 };
const fn both(start: usize, size: usize, endian: Endian, a: &Tags, b: &Tags) -> Self {
let mut known = Self { start, end: start + size, endian, ..Self::NONE };
let (mut i, mut j) = (0, 0);
while i < a.len() && j < b.len() {
let ((lo_a, hi_a), (lo_b, hi_b)) = (a.get(i), b.get(j));
let (lo, hi) = (if lo_a > lo_b { lo_a } else { lo_b }, if hi_a < hi_b { hi_a } else { hi_b });
if lo <= hi {
if known.len == KNOWN {
return Self::NONE;
}
known.ranges[known.len] = (lo, hi);
known.len += 1;
}
if hi_a < hi_b {
i += 1;
} else {
j += 1;
}
}
known
}
const fn covers(&self, pos: usize) -> bool {
self.len > 0 && self.start <= pos && pos < self.end
}
const fn of(&self, start: usize, end: usize, endian: Endian) -> Option<&[(u128, u128)]> {
let same =
self.start == start && self.end == end && (end - start == 1 || self.endian.equals(endian));
if self.len > 0 && same { Some(self.ranges.split_at(self.len).0) } else { None }
}
}
#[derive(Copy, Clone, PartialEq, Eq)]
pub enum Checked {
No,
Marked,
All,
}
impl Cursor {
pub(crate) const fn new(
root: &'static Layout,
base: usize,
target: bool,
checked: Checked,
) -> Self {
let frame = Frame { layout: root, base, leaf: 0, field: 0 };
Self { stack: [frame; MAX_DEPTH], depth: 1, target, checked, known: Known::NONE }
}
const fn padding_is_read(&self, source: &'static Layout) -> bool {
let (mut i, mut marked) = (0, matches!(self.checked, Checked::All));
if matches!(self.checked, Checked::No) {
return false;
}
while i < self.depth {
let frame = &self.stack[i];
if !marked && covered(source, frame.base, frame.layout) {
return false;
}
if let Kind::Array(..) | Kind::Slice(_) = frame.layout.kind
&& (marked || !same_elements(source, frame.base, frame.layout))
{
marked = true;
}
if frame.layout.rules_read_bytes()
&& (marked || !proves_rules(source, frame.base, frame.layout))
{
return true;
}
i += 1;
}
false
}
const fn enumeration(&self) -> Option<(&'static Layout, usize, usize)> {
let frame = &self.stack[self.depth - 1];
match frame.layout.kind {
Kind::Enum(_) => Some((frame.layout, frame.base, frame.leaf)),
_ => None,
}
}
const fn push(&mut self, layout: &'static Layout, base: usize, leaf: usize) {
assert!(self.depth < MAX_DEPTH, "type is nested too deeply");
self.stack[self.depth] = Frame { layout, base, leaf, field: 0 };
self.depth += 1;
}
const fn run_at(&mut self, pos: usize) -> Run {
loop {
let frame = self.stack[self.depth - 1];
let (layout, end) = (frame.layout, frame.end());
if pos >= end {
assert!(self.depth > 1, "internal error: analysis out of the bounds of a type");
self.depth -= 1;
continue;
}
match layout.uniform {
Uniform::Pad => return Run { kind: RunKind::Pad, start: frame.base, end, leaf: 0 },
Uniform::Any => return Run { kind: RunKind::Any, start: frame.base, end, leaf: 0 },
Uniform::No => {}
}
match layout.kind {
Kind::Scalar(spec) => {
return Run { kind: RunKind::Atom(spec), start: frame.base, end, leaf: frame.leaf };
}
Kind::Array(elem, _) | Kind::Slice(elem) => {
let index = (pos - frame.base) / elem.size;
self.push(elem, frame.base + index * elem.size, frame.leaf);
}
Kind::Pattern(dfa) => {
return Run { kind: RunKind::Pattern(dfa), start: frame.base, end, leaf: frame.leaf };
}
Kind::Pointer(pointer) => {
let kind = RunKind::Pointer(pointer);
return Run { kind, start: frame.base, end, leaf: frame.leaf };
}
Kind::Enum(variants) => {
let Kind::Scalar(spec) = variants.tag.layout.kind else { panic!() };
let (offset, tag) = (pos - frame.base, variants.tag.offset);
if offset >= tag && offset < tag + spec.size {
let kind = if spec.is_constrained() { RunKind::Atom(spec) } else { RunKind::Any };
let (start, end) = (frame.base + tag, frame.base + tag + spec.size);
return Run { kind, start, end, leaf: frame.leaf };
}
let checked = !matches!(self.checked, Checked::No);
let (init, stop) = layout.segment(offset, !self.target, checked);
let kind = if init { RunKind::Any } else { RunKind::Pad };
return Run { kind, start: pos, end: frame.base + stop, leaf: 0 };
}
Kind::Struct(fields, _) => {
let mut i = frame.field;
while i < fields.len() {
let field = &fields[i];
let dynamic = field.layout.is_dynamic();
if dynamic || frame.base + field.offset + field.layout.size > pos {
break;
}
i += 1;
}
self.stack[self.depth - 1].field = i;
if i == fields.len() {
return Run { kind: RunKind::Pad, start: pos, end, leaf: 0 };
}
let start = frame.base + fields[i].offset;
if pos < start {
return Run { kind: RunKind::Pad, start: pos, end: start, leaf: 0 };
}
self.push(fields[i].layout, start, frame.leaf + fields[i].leaf);
}
}
}
}
const fn repeats(
&self,
pos: usize,
run: &Run,
aligned: bool,
out: &mut [Repeat; MAX_DEPTH + 1],
) -> usize {
let (mut len, mut i) = (0, 0);
while i + 1 < self.depth {
let frame = &self.stack[i];
let (elem, end) = match frame.layout.kind {
Kind::Array(elem, _) => (elem, frame.end()),
Kind::Slice(elem) => (elem, usize::MAX),
_ => {
i += 1;
continue;
}
};
if !aligned || self.stack[i + 1].base == pos {
out[len] = Repeat { stride: elem.size, end, run: false, id: (i, frame.base) };
len += 1;
}
i += 1;
}
if matches!(run.kind, RunKind::Pad | RunKind::Any) {
out[len] = Repeat { stride: 1, end: run.end, run: true, id: (usize::MAX, 0) };
len += 1;
}
len
}
}
#[derive(Copy, Clone)]
pub struct Marks {
bits: [u64; Self::CAPACITY / 64],
overflow: bool,
}
impl Marks {
const CAPACITY: usize = 1024;
pub(crate) const NONE: Self = Self { bits: [0; Self::CAPACITY / 64], overflow: false };
pub(crate) const ALL: Self = Self { bits: [!0; Self::CAPACITY / 64], overflow: true };
const fn set(&mut self, leaf: usize) {
if leaf < Self::CAPACITY {
self.bits[leaf / 64] |= 1 << (leaf % 64);
} else {
self.overflow = true;
}
}
pub(crate) const fn any(&self, first: usize, count: usize) -> bool {
let (mut i, end) = (first, first + count);
while i < end {
if i >= Self::CAPACITY {
return self.overflow;
}
if i % 64 == 0 && end - i >= 64 {
if self.bits[i / 64] != 0 {
return true;
}
i += 64;
} else {
if self.bits[i / 64] & (1 << (i % 64)) != 0 {
return true;
}
i += 1;
}
}
false
}
}
#[derive(Copy, Clone)]
pub struct Relation {
pub(crate) uninit: Option<usize>,
pub(crate) disjoint: Option<usize>,
pub(crate) partial: Option<usize>,
pub(crate) marks: Marks,
pub(crate) pointer: Option<usize>,
}
impl Relation {
const NEW: Self =
Self { uninit: None, disjoint: None, partial: None, marks: Marks::NONE, pointer: None };
const fn pointer(&mut self, pos: usize) {
if self.pointer.is_none() {
self.pointer = Some(pos);
}
}
const fn mark(&mut self, leaf: usize, pos: usize) {
self.marks.set(leaf);
if self.partial.is_none() {
self.partial = Some(pos);
}
}
const fn uninit(&mut self, pos: usize) {
if self.uninit.is_none() {
self.uninit = Some(pos);
}
}
pub(crate) const fn infallible(&self) -> bool {
self.uninit.is_none()
&& self.disjoint.is_none()
&& self.partial.is_none()
&& self.pointer.is_none()
}
}
pub const fn relate(
a: &'static Layout,
b: &'static Layout,
end: usize,
checked: Checked,
) -> Relation {
relate_at(a, 0, b, 0, 0, end, checked)
}
pub const fn relate_at(
a: &'static Layout,
base_a: usize,
b: &'static Layout,
base_b: usize,
start: usize,
end: usize,
checked: Checked,
) -> Relation {
assert!(base_a == 0 || matches!(checked, Checked::No), "internal error: shifted source");
let mut relation = Relation::NEW;
if !b.is_inhabited() && a.is_inhabited() {
relation.disjoint = Some(start);
return relation;
}
let mut a = Cursor::new(a, base_a, false, Checked::No);
let mut b = Cursor::new(b, base_b, true, checked);
relate_range(&mut a, &mut b, start, end, &mut relation);
relation
}
const fn relate_known(
a: &'static Layout,
b: &'static Layout,
end: usize,
checked: Checked,
known: &Known,
) -> Relation {
let mut relation = Relation::NEW;
if !b.is_inhabited() && a.is_inhabited() {
relation.disjoint = Some(0);
return relation;
}
let mut a = Cursor::new(a, 0, false, Checked::No);
let mut b = Cursor::new(b, 0, true, checked);
b.known = *known;
relate_range(&mut a, &mut b, 0, end, &mut relation);
relation
}
const fn relate_range(
a: &mut Cursor,
b: &mut Cursor,
mut pos: usize,
end: usize,
out: &mut Relation,
) -> bool {
while pos < end {
let (run_a, run_b) = (a.run_at(pos), b.run_at(pos));
if let RunKind::Pattern(dfa) = run_b.kind {
pattern_target(a, dfa, run_b.leaf, pos, end, out);
return true;
}
if let RunKind::Pattern(_) = run_a.kind {
let free = matches!(run_b.kind, RunKind::Pad | RunKind::Any) && run_b.end >= end;
if !free || b.enumeration().is_some() {
out.marks = Marks::ALL;
out.partial = Some(pos);
if b.stack[0].layout.has_pointers() {
out.pointer(pos);
}
}
return true;
}
match find_skip(a, b, pos, end, &run_a, &run_b) {
Skip::No => {}
Skip::To { period, next } => {
relate_range(a, b, pos, pos + period, out);
pos = next;
continue;
}
Skip::Forever { period } => {
relate_range(a, b, pos, pos + period, out);
return true;
}
}
if let Some((enum_b, base_b, leaf)) = b.enumeration() {
if let Some((enum_a, base_a, _)) = a.enumeration()
&& base_a == pos
&& base_b == pos
&& relate_enums(enum_a, enum_b, pos, leaf, out)
{
pos += enum_b.size;
continue;
}
if base_b == pos && pos + enum_b.size <= end && relate_union_from(a, enum_b, pos, leaf, out) {
pos += enum_b.size;
continue;
}
if base_b == pos
&& pos + enum_b.size <= end
&& !enum_b.has_pointers()
&& relate_enum_from(a, enum_b, pos, leaf, &b.known, out)
{
pos += enum_b.size;
continue;
}
out.mark(leaf, pos);
if enum_b.has_pointers() {
out.pointer(pos);
}
}
let stop = min(run_b.end, end);
match run_b.kind {
RunKind::Pad if b.padding_is_read(a.stack[0].layout) => {
if run_a.kind.may_be_uninit() && !b.known.covers(pos) {
out.uninit(pos);
}
pos = min(run_a.end, stop);
}
RunKind::Pad => pos = stop,
RunKind::Any => {
if run_a.kind.may_be_uninit() && !b.known.covers(pos) {
out.uninit(pos);
}
pos = min(run_a.end, stop);
}
RunKind::Atom(_) if run_b.start != pos || run_b.end > end => {
out.mark(run_b.leaf, pos);
pos = stop;
}
RunKind::Atom(spec) => {
let relation = if let Some(known) = b.known.of(run_b.start, run_b.end, spec.endian) {
let Valid::In(ranges) = spec.valid else { panic!("not an atom") };
Some(relate_ranges(known, ranges))
} else {
let (pieces, len) = gather(a, run_b.start, run_b.end);
atom_relation(&pieces, len, &spec)
};
match relation {
None => out.uninit(pos),
Some(Rel::Subset) => {}
Some(rel) => {
out.mark(run_b.leaf, pos);
if matches!(rel, Rel::Disjoint) && out.disjoint.is_none() {
out.disjoint = Some(pos);
}
}
}
pos = run_b.end;
}
RunKind::Pointer(to) => {
match run_a.kind {
RunKind::Pointer(from)
if run_a.start == pos && run_b.start == pos && run_b.end <= end =>
{
match from.reads_as(&to) {
Some(true) => {}
Some(false) => out.mark(run_b.leaf, pos),
None => out.pointer(pos),
}
}
_ => out.pointer(pos),
}
pos = stop;
}
RunKind::Pattern(_) => unreachable!(),
}
}
false
}
const fn relate_enums(
a: &'static Layout,
b: &'static Layout,
pos: usize,
leaf: usize,
out: &mut Relation,
) -> bool {
if a.equals(b) {
return true;
}
let (Kind::Enum(enum_a), Kind::Enum(enum_b)) = (a.kind, b.kind) else { panic!() };
if enum_a.union || enum_b.union {
return false;
}
let (Kind::Scalar(tag_a), Kind::Scalar(tag_b)) = (enum_a.tag.layout.kind, enum_b.tag.layout.kind)
else {
panic!()
};
if a.size < b.size
|| enum_a.tag.offset != enum_b.tag.offset
|| tag_a.size != tag_b.size
|| !tag_a.endian.equals(tag_b.endian)
{
return false;
}
let (mut some, mut all, mut i) = (false, true, 0);
let (tag, size) = (enum_b.tag.offset, tag_b.size);
while i < enum_a.variants.len() {
let from = &enum_a.variants[i];
i += 1;
if !from.is_present() {
continue;
}
let (tags, mut proven, mut j) = (from.tags(), false, 0);
while j < enum_b.variants.len() {
let to = &enum_b.variants[j];
j += 1;
if !tags.meets(&to.tags()) {
continue;
}
let known = Known::both(tag, size, tag_b.endian, &tags, &to.tags());
let mut relation = relate_known(from.layout, to.layout, b.size, Checked::All, &known);
mark_rules(from.layout, to.layout, 0, 0, &mut relation);
if let Some(offset) = relation.uninit {
out.uninit(pos + offset);
}
if let Some(offset) = relation.pointer {
out.pointer(pos + offset);
}
some |= relation.disjoint.is_none();
proven |= relation.infallible() && tags.within(&to.tags());
}
all &= proven;
}
if !all {
out.mark(leaf, pos);
}
if !some && out.disjoint.is_none() {
out.disjoint = Some(pos);
}
true
}
const fn relate_enum_from(
a: &Cursor,
b: &'static Layout,
pos: usize,
leaf: usize,
known: &Known,
out: &mut Relation,
) -> bool {
let Kind::Enum(layout) = b.kind else { panic!() };
let Kind::Scalar(tag) = layout.tag.layout.kind else { panic!() };
if layout.union {
return false;
}
let start = pos + layout.tag.offset;
let Some(values) = tag_values(a, start, &tag, known) else {
out.uninit(start);
return true;
};
let (mut some, mut all, mut i) = (false, true, 0);
while i < layout.variants.len() {
let variant = &layout.variants[i];
i += 1;
if !variant.is_present() || !values.meets(&variant.tags()) {
continue;
}
let known = Known::both(start, tag.size, tag.endian, &values, &variant.tags());
let mut relation = Relation::NEW;
let (mut from, mut to) = (*a, Cursor::new(variant.layout, pos, true, Checked::All));
to.known = known;
relate_range(&mut from, &mut to, pos, pos + b.size, &mut relation);
mark_rules(a.stack[0].layout, variant.layout, pos, 0, &mut relation);
if let Some(offset) = relation.uninit {
out.uninit(offset);
}
if let Some(offset) = relation.pointer {
out.pointer(offset);
}
some |= relation.disjoint.is_none();
all &= relation.infallible();
}
if !all || !all_tags(&values, layout.variants) {
out.mark(leaf, pos);
}
if !some && out.disjoint.is_none() {
out.disjoint = Some(pos);
}
true
}
const fn relate_union_from(
a: &Cursor,
b: &'static Layout,
pos: usize,
leaf: usize,
out: &mut Relation,
) -> bool {
let Kind::Enum(layout) = b.kind else { panic!() };
if !layout.union {
return false;
}
let (mut proven, mut some, mut uninit, mut i) = (false, false, None, 0);
while i < layout.variants.len() {
let field = &layout.variants[i];
i += 1;
if !field.is_present() {
continue;
}
let mut relation = Relation::NEW;
let (mut from, mut to) = (*a, Cursor::new(field.layout, pos, true, Checked::All));
relate_range(&mut from, &mut to, pos, pos + b.size, &mut relation);
mark_rules(a.stack[0].layout, field.layout, pos, 0, &mut relation);
if relation.uninit.is_none() {
proven |= relation.infallible();
some |= relation.disjoint.is_none();
} else if uninit.is_none() {
uninit = relation.uninit;
}
}
if proven {
return true;
}
if let Some(offset) = uninit {
out.uninit(offset);
} else {
out.mark(leaf, pos);
if !some && out.disjoint.is_none() {
out.disjoint = Some(pos);
}
}
true
}
const fn tag_values(a: &Cursor, start: usize, tag: &Spec, known: &Known) -> Option<Tags> {
if let Some(ranges) = known.of(start, start + tag.size, tag.endian) {
return Some(Tags::range(ranges[0].0, ranges[ranges.len() - 1].1));
}
let mut from = *a;
let (pieces, len) = gather(&mut from, start, start + tag.size);
let mut i = 0;
while i < len {
if pieces[i].kind.may_be_uninit() {
return None;
}
i += 1;
}
if len == 1
&& let RunKind::Atom(Spec { size, endian, known: Valid::In(ranges), .. }) = pieces[0].kind
&& pieces[0].skip == 0
&& size == tag.size
&& (size == 1 || endian.equals(tag.endian))
{
return Some(Tags::of(ranges));
}
Some(Tags::range(0, max_value(tag.size)))
}
const fn all_tags(values: &Tags, variants: &[crate::layout::Variant]) -> bool {
let mut r = 0;
while r < values.len() {
let (mut next, hi) = values.get(r);
r += 1;
loop {
let (mut found, mut i) = (None, 0);
while i < variants.len() && found.is_none() {
let tags = variants[i].tags();
let mut j = 0;
while variants[i].is_present() && j < tags.len() {
let (lo, up) = tags.get(j);
if lo <= next && next <= up {
found = Some(up);
}
j += 1;
}
i += 1;
}
match found {
None => return false,
Some(up) if up >= hi => break,
Some(up) => next = up + 1,
}
}
}
true
}
const NO: Repeat = Repeat { stride: 0, end: 0, run: false, id: (0, 0) };
enum Skip {
No,
To {
period: usize,
next: usize,
},
Forever {
period: usize,
},
}
const fn find_skip(
a: &Cursor,
b: &Cursor,
pos: usize,
end: usize,
run_a: &Run,
run_b: &Run,
) -> Skip {
let (mut repeats_a, mut repeats_b) = ([NO; MAX_DEPTH + 1], [NO; MAX_DEPTH + 1]);
let len_b = b.repeats(pos, run_b, true, &mut repeats_b);
if len_b == 0 {
return Skip::No;
}
let len_a = a.repeats(pos, run_a, false, &mut repeats_a);
let mut i = 0;
while i < len_b {
let mut j = 0;
while j < len_a {
let (ra, rb) = (repeats_a[j], repeats_b[i]);
j += 1;
if ra.run && rb.run {
continue;
}
let Some(period) = lcm(ra.stride, rb.stride) else { continue };
let until = min(min(ra.end, rb.end), end);
if until == usize::MAX {
return Skip::Forever { period };
}
let count = (until - pos) / period;
if count >= 2 {
return Skip::To { period, next: pos + count * period };
}
}
i += 1;
}
Skip::No
}
const fn min(a: usize, b: usize) -> usize {
if a < b { a } else { b }
}
const fn gcd(a: usize, b: usize) -> usize {
if b == 0 { a } else { gcd(b, a % b) }
}
const fn lcm(a: usize, b: usize) -> Option<usize> {
(a / gcd(a, b)).checked_mul(b)
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum Rel {
Subset,
Overlap,
Disjoint,
}
#[derive(Copy, Clone)]
struct Piece {
kind: RunKind,
from: usize,
to: usize,
skip: usize,
}
const fn gather(a: &mut Cursor, start: usize, end: usize) -> ([Piece; 16], usize) {
let mut pieces = [Piece { kind: RunKind::Any, from: 0, to: 0, skip: 0 }; 16];
let (mut len, mut pos) = (0, start);
while pos < end {
let mut run = a.run_at(pos);
if let RunKind::Pointer(_) = run.kind {
run.kind = RunKind::Any;
}
let to = min(run.end, end);
let skip = if matches!(run.kind, RunKind::Atom(_)) { pos - run.start } else { 0 };
pieces[len] = Piece { kind: run.kind, from: pos - start, to: to - start, skip };
(len, pos) = (len + 1, to);
}
(pieces, len)
}
const fn atom_relation(pieces: &[Piece; 16], len: usize, spec: &Spec) -> Option<Rel> {
let Valid::In(ranges) = spec.valid else { panic!("not an atom") };
let (mut known, soft) = (*pieces, spec.is_soft());
let (mut i, mut all_any) = (0, true);
while i < len {
match known[i].kind {
RunKind::Pad => return None,
RunKind::Any | RunKind::Pattern(_) | RunKind::Pointer(_) => {}
RunKind::Atom(from) if from.may_be_uninit() => return None,
RunKind::Atom(from) => match if soft { from.valid } else { from.known } {
valid @ Valid::In(_) => {
known[i].kind = RunKind::Atom(Spec { valid, ..from });
all_any = false;
}
_ => known[i].kind = RunKind::Any,
},
}
i += 1;
}
let pieces = &known;
if all_any {
return Some(Rel::Overlap);
}
if len == 1
&& let RunKind::Atom(Spec { size, endian, valid: Valid::In(from), .. }) = pieces[0].kind
&& pieces[0].skip == 0
&& size == spec.size
&& (size == 1 || endian.equals(spec.endian))
{
return Some(relate_ranges(from, ranges));
}
let mut boxes =
Boxes { pieces, len, spec, ranges, escapes: false, meets: false, budget: 1 << 14 };
boxes.explore(0, &mut [0; 16], &mut [0xff; 16]);
Some(match (boxes.escapes, boxes.meets) {
(false, _) => Rel::Subset,
(true, false) => Rel::Disjoint,
(true, true) => Rel::Overlap,
})
}
pub const fn relate_ranges(a: &[(u128, u128)], b: &[(u128, u128)]) -> Rel {
let (mut subset, mut meets, mut i) = (true, false, 0);
while i < a.len() {
let ((lo, hi), mut inside, mut j) = (a[i], false, 0);
while j < b.len() {
meets |= lo <= b[j].1 && b[j].0 <= hi;
inside |= b[j].0 <= lo && hi <= b[j].1;
j += 1;
}
subset &= inside;
i += 1;
}
match (subset, meets) {
(true, _) => Rel::Subset,
(false, true) => Rel::Overlap,
(false, false) => Rel::Disjoint,
}
}
struct Boxes<'a> {
pieces: &'a [Piece; 16],
len: usize,
spec: &'a Spec,
ranges: &'a [(u128, u128)],
escapes: bool,
meets: bool,
budget: usize,
}
impl Boxes<'_> {
const fn explore(&mut self, index: usize, lo: &mut [u8; 16], hi: &mut [u8; 16]) {
if self.escapes && self.meets {
return;
}
if index == self.len {
return self.check(lo, hi);
}
let piece = self.pieces[index];
let RunKind::Atom(Spec { size, endian, valid: Valid::In(ranges), .. }) = piece.kind else {
let mut i = piece.from;
while i < piece.to {
(lo[i], hi[i]) = (0, 0xff);
i += 1;
}
return self.explore(index + 1, lo, hi);
};
let mut r = 0;
while r < ranges.len() {
let (mut t, count) = (0, box_count(ranges[r].0, ranges[r].1, size));
while t < count {
if let Some((digits_lo, digits_hi)) = digit_box(ranges[r].0, ranges[r].1, size, t) {
let mut i = piece.from;
while i < piece.to {
let byte = piece.skip + (i - piece.from);
let digit = if endian.is_little() { size - 1 - byte } else { byte };
(lo[i], hi[i]) = (digits_lo[digit], digits_hi[digit]);
i += 1;
}
self.explore(index + 1, lo, hi);
}
t += 1;
}
r += 1;
}
}
const fn check(&mut self, lo: &[u8; 16], hi: &[u8; 16]) {
if self.budget == 0 {
(self.escapes, self.meets) = (true, true);
return;
}
self.budget -= 1;
let (size, little) = (self.spec.size, self.spec.endian.is_little());
let (mut digits_lo, mut digits_hi, mut i) = ([0; 16], [0; 16], 0);
while i < size {
let byte = if little { size - 1 - i } else { i };
(digits_lo[i], digits_hi[i]) = (lo[byte], hi[byte]);
i += 1;
}
let (mut i, mut gap) = (0, Some(0));
while i < self.ranges.len() {
let (start, end) = self.ranges[i];
self.meets = self.meets || box_meets(&digits_lo, &digits_hi, size, start, end);
if let Some(gap) = gap
&& gap < start
{
self.escapes = self.escapes || box_meets(&digits_lo, &digits_hi, size, gap, start - 1);
}
gap = if end < max_value(size) { Some(end + 1) } else { None };
i += 1;
}
if let Some(gap) = gap {
self.escapes = self.escapes || box_meets(&digits_lo, &digits_hi, size, gap, max_value(size));
}
}
}
const fn digit(value: u128, size: usize, index: usize) -> u8 {
(value >> (8 * (size - 1 - index))) as u8
}
const fn first_difference(lo: u128, hi: u128, size: usize) -> usize {
let mut i = 0;
while i < size && digit(lo, size, i) == digit(hi, size, i) {
i += 1;
}
i
}
const fn box_count(lo: u128, hi: u128, size: usize) -> usize {
let p = first_difference(lo, hi, size);
if p + 1 >= size { 1 } else { 1 + 2 * (size - 1 - p) }
}
const fn digit_box(lo: u128, hi: u128, size: usize, index: usize) -> Option<([u8; 16], [u8; 16])> {
let p = first_difference(lo, hi, size);
let (mut box_lo, mut box_hi) = ([0; 16], [0xff; 16]);
let (prefix, q, range);
if p + 1 >= size {
(prefix, q) = (lo, size - 1);
range = (digit(lo, size, q), digit(hi, size, q));
} else if index == 0 {
(prefix, q) = (lo, p);
if digit(hi, size, p) - digit(lo, size, p) < 2 {
return None;
}
range = (digit(lo, size, p) + 1, digit(hi, size, p) - 1);
} else if index <= size - 1 - p {
(prefix, q) = (lo, p + index);
let digit = digit(lo, size, q);
if q == size - 1 {
range = (digit, 0xff);
} else if digit == 0xff {
return None;
} else {
range = (digit + 1, 0xff);
}
} else {
(prefix, q) = (hi, p + index - (size - 1 - p));
let digit = digit(hi, size, q);
if q == size - 1 {
range = (0, digit);
} else if digit == 0 {
return None;
} else {
range = (0, digit - 1);
}
}
let mut i = 0;
while i < q {
(box_lo[i], box_hi[i]) = (digit(prefix, size, i), digit(prefix, size, i));
i += 1;
}
(box_lo[q], box_hi[q]) = range;
Some((box_lo, box_hi))
}
const fn box_meets(lo: &[u8; 16], hi: &[u8; 16], size: usize, start: u128, end: u128) -> bool {
let mut i = 0;
while i < size && lo[i] <= digit(start, size, i) && digit(start, size, i) <= hi[i] {
i += 1;
}
let bump = if i == size {
return true;
} else if digit(start, size, i) < lo[i] {
false
} else {
loop {
if i == 0 {
return false;
}
i -= 1;
if digit(start, size, i) < hi[i] {
break;
}
}
true
};
let (mut least, mut k) = (0u128, 0);
while k < size {
let digit = match () {
() if k < i => digit(start, size, k),
() if k == i && bump => digit(start, size, k) + 1,
() => lo[k],
};
least = (least << 8) | digit as u128;
k += 1;
}
least <= end
}
const fn pattern_target(
a: &mut Cursor,
dfa: &'static Dfa,
leaf: usize,
mut pos: usize,
end: usize,
out: &mut Relation,
) {
let mut set = 1u64;
let mut memo = [((0, 0), 0u64); MAX_DEPTH + 1];
let mut memo_len = 0;
let mut budget = 1usize << 12;
'runs: while pos < end {
if budget == 0 {
return out.mark(leaf, pos);
}
budget -= 1;
let run = a.run_at(pos);
let mut repeats = [NO; MAX_DEPTH + 1];
let (len, mut i) = (a.repeats(pos, &run, true, &mut repeats), 0);
while i < len {
let repeat = repeats[i];
i += 1;
if repeat.run {
continue;
}
if repeat.end == usize::MAX && !dfa.accepts(set) {
return out.mark(leaf, pos);
}
let mut j = 0;
while j < memo_len && !(memo[j].0.0 == repeat.id.0 && memo[j].0.1 == repeat.id.1) {
j += 1;
}
if j < memo_len && memo[j].1 == set {
pos = min(repeat.end, end);
continue 'runs;
}
memo[j] = (repeat.id, set);
if j == memo_len {
memo_len += 1;
}
}
let stop = min(run.end, end);
match run.kind {
RunKind::Pad => return out.uninit(pos),
RunKind::Any | RunKind::Pointer(_) => {
let mut steps = 0;
while steps < stop - pos {
let (next, total) = dfa.step(set, 0, 0xff);
if !total || steps > 256 || (end == usize::MAX && !dfa.accepts(next)) {
return out.mark(leaf, pos);
}
if next == set {
break;
}
(set, steps) = (next, steps + 1);
}
}
RunKind::Atom(spec) if spec.may_be_uninit() => return out.uninit(pos),
RunKind::Atom(spec) => {
let ranges: &[(u128, u128)] = match spec.known {
Valid::In(ranges) => ranges,
_ => &[(0, max_value(spec.size))],
};
let (mut result, mut r) = (0, 0);
while r < ranges.len() {
let (mut t, count) = (0, box_count(ranges[r].0, ranges[r].1, spec.size));
while t < count {
if let Some((lo, hi)) = digit_box(ranges[r].0, ranges[r].1, spec.size, t) {
let (mut states, mut byte) = (set, pos - run.start);
while byte < stop - run.start {
let digit = if spec.endian.is_little() { spec.size - 1 - byte } else { byte };
let (next, total) = dfa.step(states, lo[digit], hi[digit]);
if !total {
return out.mark(leaf, pos);
}
(states, byte) = (next, byte + 1);
}
result |= states;
}
t += 1;
}
r += 1;
}
set = result;
}
RunKind::Pattern(source) => {
let from = if run.start == pos { 1 } else { source.reachable() };
if !pattern_product(source, from, dfa, set) {
out.mark(leaf, pos);
}
return;
}
}
pos = stop;
}
if end != usize::MAX && !dfa.accepts(set) {
out.mark(leaf, pos);
}
}
const fn pattern_product(a: &Dfa, from_a: u64, b: &Dfa, from_b: u64) -> bool {
let (mut seen, mut done) = ([0u64; 64], [0u64; 64]);
let mut state = 0;
while state < a.states.len() {
if from_a & (1 << state) != 0 {
seen[state] = from_b;
}
state += 1;
}
loop {
let (mut changed, mut state) = (false, 0);
while state < a.states.len() {
let todo = seen[state] & !done[state];
if todo != 0 {
(done[state], changed) = (done[state] | todo, true);
if a.states[state].accept && !b.accepts(todo) {
return false;
}
let (edges, mut i) = (a.states[state].edges, 0);
while i < edges.len() {
let (next, total) = b.step(todo, edges[i].0, edges[i].1);
if !total {
return false;
}
seen[edges[i].2 as usize] |= next;
i += 1;
}
}
state += 1;
}
if !changed {
return true;
}
}
}
const fn mark_rules(
source: &'static Layout,
target: &'static Layout,
base: usize,
leaf: usize,
out: &mut Relation,
) {
if !target.has_rules || covered(source, base, target) {
return;
}
match target.kind {
Kind::Struct(fields, rules) => {
if !rules.is_empty() && !proves_rules(source, base, target) {
out.mark(leaf + target.leaves - 1, base);
}
let mut i = 0;
while i < fields.len() {
mark_rules(source, fields[i].layout, base + fields[i].offset, leaf + fields[i].leaf, out);
i += 1;
}
}
Kind::Array(elem, _) | Kind::Slice(elem) => {
if same_elements(source, base, target) {
mark_rules(source, elem, base, leaf, out);
} else {
mark_all_rules(elem, base, leaf, out);
}
}
Kind::Scalar(_) | Kind::Pattern(_) | Kind::Enum(_) | Kind::Pointer(_) => {}
}
}
const fn mark_all_rules(target: &'static Layout, base: usize, leaf: usize, out: &mut Relation) {
if !target.has_rules {
return;
}
match target.kind {
Kind::Struct(fields, rules) => {
if !rules.is_empty() {
out.mark(leaf + target.leaves - 1, base);
}
let mut i = 0;
while i < fields.len() {
mark_all_rules(fields[i].layout, base + fields[i].offset, leaf + fields[i].leaf, out);
i += 1;
}
}
Kind::Array(elem, _) | Kind::Slice(elem) => mark_all_rules(elem, base, leaf, out),
Kind::Scalar(_) | Kind::Pattern(_) | Kind::Enum(_) | Kind::Pointer(_) => {}
}
}
const fn proves_rules(source: &'static Layout, offset: usize, target: &'static Layout) -> bool {
if offset == 0 && source.same_rules(target) {
return true;
}
match source.kind {
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
let field = &fields[i];
let inside = field.layout.is_dynamic() || offset < field.offset + field.layout.size;
if offset >= field.offset
&& inside
&& proves_rules(field.layout, offset - field.offset, target)
{
return true;
}
i += 1;
}
false
}
Kind::Array(elem, len) => {
elem.size > 0 && offset / elem.size < len && proves_rules(elem, offset % elem.size, target)
}
Kind::Slice(elem) => elem.size > 0 && proves_rules(elem, offset % elem.size, target),
Kind::Scalar(_) | Kind::Pattern(_) | Kind::Enum(_) | Kind::Pointer(_) => false,
}
}
const fn same_elements(source: &'static Layout, offset: usize, target: &'static Layout) -> bool {
let same = match (source.kind, target.kind) {
(Kind::Array(a, n), Kind::Array(b, m)) => {
a.size == b.size && a.size > 0 && offset.is_multiple_of(a.size) && offset / a.size + m <= n
}
(Kind::Slice(a), Kind::Slice(b) | Kind::Array(b, _)) => {
a.size == b.size && (offset == 0 || a.size > 0 && offset.is_multiple_of(a.size))
}
_ => false,
};
if same {
return true;
}
match source.kind {
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
let field = &fields[i];
let inside = field.layout.is_dynamic() || offset < field.offset + field.layout.size;
if offset >= field.offset && inside {
return same_elements(field.layout, offset - field.offset, target);
}
i += 1;
}
false
}
Kind::Array(elem, len) => {
elem.size > 0 && offset / elem.size < len && same_elements(elem, offset % elem.size, target)
}
Kind::Slice(elem) => elem.size > 0 && same_elements(elem, offset % elem.size, target),
Kind::Scalar(_) | Kind::Pattern(_) | Kind::Enum(_) | Kind::Pointer(_) => false,
}
}
const fn covered(source: &'static Layout, offset: usize, target: &'static Layout) -> bool {
if offset == 0 {
if source.equals(target) {
return true;
}
let same = match (source.kind, target.kind) {
(Kind::Array(a, n), Kind::Array(b, m)) => n >= m && a.equals(b),
(Kind::Slice(a), Kind::Slice(b) | Kind::Array(b, _)) => a.equals(b),
_ => false,
};
if same {
return true;
}
}
match source.kind {
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
let field = &fields[i];
let inside = field.layout.is_dynamic() || offset < field.offset + field.layout.size;
if offset >= field.offset && inside {
return covered(field.layout, offset - field.offset, target);
}
i += 1;
}
false
}
Kind::Array(elem, len) => {
elem.size > 0 && offset / elem.size < len && covered(elem, offset % elem.size, target)
}
Kind::Slice(elem) => elem.size > 0 && covered(elem, offset % elem.size, target),
Kind::Scalar(_) | Kind::Pattern(_) | Kind::Enum(_) | Kind::Pointer(_) => false,
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum Exact {
Always,
Sometimes,
Never(&'static str),
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct Fit {
pub(crate) exact: Exact,
pub(crate) shrink: bool,
pub(crate) end: usize,
}
pub const TOO_SMALL: &str = "the source is smaller than the target";
pub const TOO_LARGE: &str = "the source is larger than the target";
pub const UNEVEN: &str =
"the size of the source cannot be reached with elements of the tail slice of the target";
pub const fn fit(a: &Layout, b: &Layout) -> Fit {
let ((sa, ya), (sb, yb)) = ((a.size, a.stride()), (b.size, b.stride()));
match (ya != 0, yb != 0) {
(false, false) => Fit {
exact: match () {
() if sa < sb => Exact::Never(TOO_SMALL),
() if sa > sb => Exact::Never(TOO_LARGE),
() => Exact::Always,
},
shrink: sa >= sb,
end: sb,
},
(false, true) => {
let elems = if sa >= sb { (sa - sb) / yb } else { 0 };
Fit {
exact: match () {
() if sa < sb => Exact::Never(TOO_SMALL),
() if (sa - sb) % yb != 0 => Exact::Never(UNEVEN),
() => Exact::Always,
},
shrink: sa >= sb,
end: sb + elems * yb,
}
}
(true, false) => Fit {
exact: match () {
() if sa > sb => Exact::Never(TOO_LARGE),
() if (sb - sa) % ya != 0 => Exact::Never(UNEVEN),
() => Exact::Sometimes,
},
shrink: sa >= sb,
end: sb,
},
(true, true) => Fit {
exact: match () {
() if sa.abs_diff(sb) % gcd(ya, yb) != 0 => Exact::Never(UNEVEN),
() if sa >= sb && (sa - sb) % yb == 0 && ya % yb == 0 => Exact::Always,
() => Exact::Sometimes,
},
shrink: sa >= sb,
end: usize::MAX,
},
}
}
#[derive(Copy, Clone)]
pub struct Analysis {
pub(crate) fit: Fit,
pub(crate) relation: Relation,
pub(crate) aligned: bool,
pub(crate) shift: usize,
}
pub const fn analyze(a: &'static Layout, b: &'static Layout) -> Analysis {
let fit = fit(a, b);
let hopeless = matches!(fit.exact, Exact::Never(_)) && !fit.shrink;
let mut relation = if hopeless { Relation::NEW } else { relate(a, b, fit.end, Checked::Marked) };
if !hopeless {
mark_rules(a, b, 0, 0, &mut relation);
}
Analysis { fit, relation, aligned: b.align <= a.align, shift: 0 }
}
pub const TAIL_UNSIZED_SOURCE: &str = "the source is unsized: where its last bytes start depends \
on its length, which is only known at run time.\nUse \
`from_tail` to take a value from the end of bytes";
pub const TAIL_UNSIZED_TARGET: &str =
"the target is unsized: its extent cannot be found from the end of the source";
pub const fn analyze_tail(a: &'static Layout, b: &'static Layout) -> Analysis {
if a.is_unsized() || b.is_unsized() || a.size < b.size {
let exact = Exact::Never(match () {
() if a.is_unsized() => TAIL_UNSIZED_SOURCE,
() if b.is_unsized() => TAIL_UNSIZED_TARGET,
() => TOO_SMALL,
});
let fit = Fit { exact, shrink: false, end: 0 };
return Analysis { fit, relation: Relation::NEW, aligned: false, shift: 0 };
}
let shift = a.size - b.size;
let exact = if shift == 0 { Exact::Always } else { Exact::Never(TOO_LARGE) };
let fit = Fit { exact, shrink: true, end: b.size };
let mut relation = relate_at(a, 0, b, shift, shift, a.size, Checked::Marked);
mark_rules(a, b, shift, 0, &mut relation);
let aligned = b.align <= a.align && shift.is_multiple_of(b.align);
Analysis { fit, relation, aligned, shift }
}
pub const fn mutable(a: &'static Layout, b: &'static Layout, fit: &Fit) -> bool {
!a.has_pointers()
&& !b.has_pointers()
&& !matches!(fit.exact, Exact::Never(_))
&& relate(b, a, fit.end, Checked::No).infallible()
}
pub const POINTER_MUT: &str = "the source or the target holds a self-relative pointer, which a \
`&mut` would let safe code overwrite, swap or move: a pointer is \
only read.\nEdit the value where it is, with what the crate that \
declares the pointer gives";
pub const MUTABLE: &str = "some values of the target are not valid for the source (or are padding \
where the source is not), and could be written through the `&mut`";
pub const PART_RULE: &str = "a rule of the source (a size, a length, an assertion, a region) \
holds over bytes that the `&mut` covers, and could stop holding when \
they are written";
pub const PART_ENUM: &str = "an enum of the source is only partly covered by the `&mut`: what its \
tag says of the bytes on one side depends on the other";
pub const PART_PATTERN: &str = "a string of the source is only partly covered by the `&mut`: what \
is written must be valid with what follows it";
pub const fn mutable_part(
a: &'static Layout,
b: &'static Layout,
fit: &Fit,
shift: usize,
) -> Option<&'static str> {
if !fit.shrink {
return Some(MUTABLE);
}
if a.has_pointers() || b.has_pointers() {
return Some(POINTER_MUT);
}
let end = shift.saturating_add(fit.end);
if let Some(why) = cut(a, 0, b, shift, end) {
return Some(why);
}
if end == usize::MAX && !matches!(fit.exact, Exact::Always) && is_tagged(a) {
return Some(PART_ENUM);
}
if relate_at(b, shift, a, 0, shift, end, Checked::No).infallible() { None } else { Some(MUTABLE) }
}
const CUT_ELEMENTS: usize = 64;
const fn cut(
layout: &'static Layout,
base: usize,
b: &'static Layout,
lo: usize,
hi: usize,
) -> Option<&'static str> {
let end = if layout.is_dynamic() { usize::MAX } else { base + layout.size };
if end <= lo || base >= hi || base == end {
return None;
}
let within = !layout.is_dynamic() && base >= lo && end <= hi;
match layout.kind {
Kind::Scalar(_) | Kind::Pointer(_) => None,
Kind::Struct(fields, rules) => {
let proven = within && proves_rules(b, base - lo, layout);
if !rules.is_empty() && !proven {
return Some(PART_RULE);
}
let mut i = 0;
while i < fields.len() {
if let Some(why) = cut(fields[i].layout, base + fields[i].offset, b, lo, hi) {
return Some(why);
}
i += 1;
}
None
}
Kind::Enum(enumeration) => {
if base < lo || end > hi {
return Some(PART_ENUM);
}
let mut i = 0;
while i < enumeration.variants.len() {
if has_rules(enumeration.variants[i].layout) {
return Some(PART_RULE);
}
i += 1;
}
None
}
Kind::Pattern(_) => {
if base < lo || hi != usize::MAX {
Some(PART_PATTERN)
} else {
None
}
}
Kind::Array(elem, _) | Kind::Slice(elem) => {
if elem.size == 0 {
return None;
}
if has_rules(elem) {
if within && same_elements(b, base - lo, layout) {
return cut(elem, base, b, lo, hi);
}
let count = match layout.kind {
Kind::Array(_, count) => count,
_ => usize::MAX,
};
let first = if lo > base { (lo - base) / elem.size } else { 0 };
if hi == usize::MAX || count == usize::MAX {
return Some(PART_RULE);
}
let last = (hi - 1 - base) / elem.size;
let last = if last < count { last } else { count - 1 };
if last - first >= CUT_ELEMENTS {
return Some(PART_RULE);
}
let mut k = first;
while k <= last {
if let Some(why) = cut(elem, base + k * elem.size, b, lo, hi) {
return Some(why);
}
k += 1;
}
return None;
}
if !is_tagged(elem) {
return None;
}
let count = match layout.kind {
Kind::Array(_, count) => count,
_ => usize::MAX,
};
let first = if lo > base { (lo - base) / elem.size } else { 0 };
if first < count
&& let Some(why) = cut(elem, base + first * elem.size, b, lo, hi)
{
return Some(why);
}
if hi != usize::MAX {
let last = (hi - 1 - base) / elem.size;
if last < count
&& last != first
&& let Some(why) = cut(elem, base + last * elem.size, b, lo, hi)
{
return Some(why);
}
}
None
}
}
}
const fn has_rules(layout: &'static Layout) -> bool {
match layout.kind {
_ if layout.has_rules => true,
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
if has_rules(fields[i].layout) {
return true;
}
i += 1;
}
false
}
Kind::Array(elem, _) | Kind::Slice(elem) => has_rules(elem),
Kind::Enum(enumeration) => {
let mut i = 0;
while i < enumeration.variants.len() {
if has_rules(enumeration.variants[i].layout) {
return true;
}
i += 1;
}
false
}
Kind::Scalar(_) | Kind::Pattern(_) | Kind::Pointer(_) => false,
}
}
const fn is_tagged(layout: &'static Layout) -> bool {
match layout.kind {
Kind::Enum(_) | Kind::Pattern(_) => true,
Kind::Struct(fields, _) => {
let mut i = 0;
while i < fields.len() {
if is_tagged(fields[i].layout) {
return true;
}
i += 1;
}
false
}
Kind::Array(elem, _) | Kind::Slice(elem) => is_tagged(elem),
Kind::Scalar(_) | Kind::Pointer(_) => false,
}
}