use super::hazard::{HazardLevel, HijackVerdict, StackHijackVerdict, StateHazard};
use super::{CONFLICT_ESCAPE, DecisionKind, DecisionOutcome, ESCAPE, GUARDED, StaticDfaTable};
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum EscapeResolution {
Guarded,
MinAlt,
MinViableAlt,
SyntaxError,
}
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub(crate) struct EscapeResolutions {
pub(crate) guarded: usize,
pub(crate) min_alt: usize,
pub(crate) min_viable_alt: usize,
pub(crate) syntax_error: usize,
pub(crate) guarded_witness: Option<Vec<i32>>,
pub(crate) guarded_danger: Vec<i32>,
pub(crate) min_alt_witness: Option<Vec<i32>>,
pub(crate) min_viable_alt_witness: Option<Vec<i32>>,
pub(crate) syntax_error_witness: Option<Vec<i32>>,
pub(crate) tie_breaks: Vec<TieBreak>,
pub(crate) guard_groups: Vec<GuardGroup>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct GuardGroup {
pub(crate) danger: Vec<i32>,
pub(crate) states: usize,
pub(crate) witness: Option<Vec<i32>>,
pub(crate) hazard: Option<StackHijackVerdict>,
}
impl GuardGroup {
pub(crate) fn level(&self) -> HazardLevel {
self.hazard
.as_ref()
.map_or(HazardLevel::Medium, StackHijackVerdict::level)
}
fn absorb(&mut self, other: Self) {
self.states += other.states;
self.hazard = worse_stack(self.hazard.take(), other.hazard);
let shorter = match (&self.witness, &other.witness) {
(None, Some(_)) => true,
(Some(known), Some(new)) => new.len() < known.len(),
_ => false,
};
if shorter {
self.witness = other.witness;
}
}
}
fn stack_outranks(left: &StackHijackVerdict, right: &StackHijackVerdict) -> bool {
let rank = |verdict: &StackHijackVerdict| match verdict {
StackHijackVerdict::Hijack { caller, extension } => (
verdict.level(),
std::cmp::Reverse(extension.len()),
std::cmp::Reverse(*caller),
),
_ => (verdict.level(), std::cmp::Reverse(0), std::cmp::Reverse(0)),
};
rank(left) > rank(right)
}
fn partial_stack(verdict: StackHijackVerdict) -> StackHijackVerdict {
match verdict {
StackHijackVerdict::Covered => StackHijackVerdict::Unknown,
verdict => verdict,
}
}
fn worse_stack(
left: Option<StackHijackVerdict>,
right: Option<StackHijackVerdict>,
) -> Option<StackHijackVerdict> {
match (left, right) {
(Some(left), Some(right)) => Some(if stack_outranks(&right, &left) {
right
} else {
left
}),
(Some(known), None) | (None, Some(known)) => Some(partial_stack(known)),
(None, None) => None,
}
}
fn add_guard_group(groups: &mut Vec<GuardGroup>, group: GuardGroup) {
match groups.iter_mut().find(|known| known.danger == group.danger) {
Some(known) => known.absorb(group),
None => groups.push(group),
}
}
fn sort_guard_groups(groups: &mut [GuardGroup]) {
groups.sort_by(|left, right| {
right
.level()
.cmp(&left.level())
.then_with(|| right.states.cmp(&left.states))
.then_with(|| left.danger.cmp(&right.danger))
});
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct TieBreak {
pub(crate) chosen: i32,
pub(crate) dropped: Vec<i32>,
pub(crate) states: usize,
pub(crate) witness: Option<Vec<i32>>,
pub(crate) hazard: Option<GroupHazard>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct GroupHazard {
pub(crate) level: HazardLevel,
pub(crate) verdict: HijackVerdict,
pub(crate) greedy: bool,
}
impl GroupHazard {
fn of(table: &StaticDfaTable, state: usize, hazard: &StateHazard) -> Self {
let unknown = StateHazard {
verdict: HijackVerdict::Unknown,
greedy: hazard.greedy,
};
let (verdict, hazard) = match (&hazard.verdict, table.witness(state)) {
(HijackVerdict::Hijack { alt, extension }, Some(path)) => (
HijackVerdict::Hijack {
alt: *alt,
extension: path.into_iter().chain(extension.iter().copied()).collect(),
},
hazard,
),
(HijackVerdict::Hijack { .. }, None) => (HijackVerdict::Unknown, &unknown),
(verdict, _) => (verdict.clone(), hazard),
};
Self {
level: hazard.level(),
verdict,
greedy: hazard.greedy,
}
}
fn partial(mut self) -> Self {
if self.verdict == HijackVerdict::Covered {
self.verdict = HijackVerdict::Unknown;
self.level = StateHazard {
verdict: HijackVerdict::Unknown,
greedy: self.greedy,
}
.level();
}
self
}
fn outranks(&self, other: &Self) -> bool {
let rank = |hazard: &Self| match &hazard.verdict {
HijackVerdict::Hijack { extension, .. } => (2, std::cmp::Reverse(extension.len())),
HijackVerdict::Unknown => (1, std::cmp::Reverse(0)),
HijackVerdict::Covered => (0, std::cmp::Reverse(0)),
};
(self.level, rank(self)) > (other.level, rank(other))
}
}
fn worse(left: Option<GroupHazard>, right: Option<GroupHazard>) -> Option<GroupHazard> {
match (left, right) {
(Some(left), Some(right)) => Some(if right.outranks(&left) { right } else { left }),
(Some(known), None) | (None, Some(known)) => Some(known.partial()),
(None, None) => None,
}
}
impl TieBreak {
fn key(&self) -> (i32, &[i32]) {
(self.chosen, &self.dropped)
}
pub(crate) fn level(&self) -> HazardLevel {
self.hazard
.as_ref()
.map_or(HazardLevel::Medium, |hazard| hazard.level)
}
fn absorb(&mut self, other: Self) {
self.states += other.states;
self.hazard = worse(self.hazard.take(), other.hazard.clone());
let shorter = match (&self.witness, &other.witness) {
(None, Some(_)) => true,
(Some(known), Some(new)) => new.len() < known.len(),
_ => false,
};
if shorter {
self.witness = other.witness;
}
}
}
type GroupBuild = (TieBreak, usize, Vec<(usize, StateHazard)>);
fn add_tie_break(groups: &mut Vec<TieBreak>, group: TieBreak) {
match groups.iter_mut().find(|known| known.key() == group.key()) {
Some(known) => known.absorb(group),
None => groups.push(group),
}
}
fn sort_tie_breaks(groups: &mut [TieBreak]) {
groups.sort_by(|left, right| {
right
.level()
.cmp(&left.level())
.then_with(|| right.states.cmp(&left.states))
.then_with(|| left.chosen.cmp(&right.chosen))
.then_with(|| left.dropped.cmp(&right.dropped))
});
}
impl EscapeResolutions {
fn merge(&mut self, other: Self) {
self.guarded += other.guarded;
self.min_alt += other.min_alt;
self.min_viable_alt += other.min_viable_alt;
self.syntax_error += other.syntax_error;
if self.guarded_witness.is_none() {
self.guarded_witness = other.guarded_witness;
self.guarded_danger = other.guarded_danger;
}
if self.min_alt_witness.is_none() {
self.min_alt_witness = other.min_alt_witness;
}
if self.min_viable_alt_witness.is_none() {
self.min_viable_alt_witness = other.min_viable_alt_witness;
}
if self.syntax_error_witness.is_none() {
self.syntax_error_witness = other.syntax_error_witness;
}
for group in other.tie_breaks {
add_tie_break(&mut self.tie_breaks, group);
}
sort_tie_breaks(&mut self.tie_breaks);
for group in other.guard_groups {
add_guard_group(&mut self.guard_groups, group);
}
sort_guard_groups(&mut self.guard_groups);
self.show_stack_hijack();
}
fn show_stack_hijack(&mut self) {
if let Some(group) = self.guard_groups.first()
&& matches!(group.hazard, Some(StackHijackVerdict::Hijack { .. }))
&& group.witness.is_some()
{
self.guarded_witness.clone_from(&group.witness);
self.guarded_danger.clone_from(&group.danger);
}
}
pub(crate) fn stack_hijacks(&self) -> impl Iterator<Item = &GuardGroup> {
self.guard_groups
.iter()
.filter(|group| group.level() == HazardLevel::High)
}
}
impl StaticDfaTable {
pub(crate) fn resolve_escapes(&mut self) -> EscapeResolutions {
let mut resolutions = EscapeResolutions::default();
let mut first_guarded = None;
let mut first_min_alt = None;
let mut first_min_viable_alt = None;
let mut first_syntax_error = None;
let depths = self.depths();
let mut groups: Vec<GroupBuild> = Vec::new();
let mut guards: Vec<(u32, usize, usize, Vec<StackHijackVerdict>)> = Vec::new();
for (index, state) in self.states.iter_mut().enumerate() {
if !matches!(state.accept, ESCAPE | CONFLICT_ESCAPE | GUARDED) {
continue;
}
if state.accept == GUARDED && state.guarded_alt > 0 && state.guard_defer_alt > 0 {
state.resolution = Some(EscapeResolution::Guarded);
resolutions.guarded += 1;
first_guarded.get_or_insert(index);
let verdict = state.stack_hazard.take();
match guards
.iter_mut()
.find(|(group, ..)| *group == state.guard_group)
{
Some((_, shallowest, states, verdicts)) => {
*states += 1;
if depths[index] < depths[*shallowest] {
*shallowest = index;
}
verdicts.extend(verdict);
}
None => {
guards.push((state.guard_group, index, 1, verdict.into_iter().collect()))
}
}
continue;
}
let conflict_alt = if state.accept == GUARDED && state.guarded_alt > 0 {
Some(state.guarded_alt)
} else {
state.conflicts.iter().copied().filter(|alt| *alt > 0).min()
};
let viable_alt = if state.predicated {
None
} else {
state.viable_alts.first().copied()
};
let mut dropped: Vec<i32> = if conflict_alt.is_some() {
state.conflicts.clone()
} else {
state.viable_alts.clone()
};
let resolution = if let Some(alt) = conflict_alt {
state.accept = alt;
resolutions.min_alt += 1;
first_min_alt.get_or_insert(index);
EscapeResolution::MinAlt
} else if let Some(alt) = viable_alt {
state.accept = alt;
resolutions.min_viable_alt += 1;
first_min_viable_alt.get_or_insert(index);
EscapeResolution::MinViableAlt
} else {
state.accept = 0;
state.fallback = 0;
state.edges.clear();
resolutions.syntax_error += 1;
first_syntax_error.get_or_insert(index);
EscapeResolution::SyntaxError
};
state.resolution = Some(resolution);
dropped.retain(|alt| *alt > 0 && *alt != state.accept);
dropped.sort_unstable();
dropped.dedup();
if resolution != EscapeResolution::SyntaxError && !dropped.is_empty() {
let hazard = state.hazard.as_ref().map(|hazard| (index, hazard.clone()));
let group = TieBreak {
chosen: state.accept,
dropped,
states: 1,
witness: None,
hazard: None,
};
match groups
.iter_mut()
.find(|(known, ..)| known.key() == group.key())
{
Some((known, shallowest, hazards)) => {
known.states += 1;
if depths[index] < depths[*shallowest] {
*shallowest = index;
}
hazards.extend(hazard);
}
None => groups.push((group, index, hazard.into_iter().collect())),
}
}
state.conflict_min_alt = 0;
state.guarded_alt = 0;
state.guard_defer_alt = 0;
state.guard_group = 0;
state.continuation = None;
state.hazard = None;
state.stack_hazard = None;
}
if resolutions.guarded == 0 {
self.guard_groups.clear();
self.guard_pass.clear();
}
resolutions.guarded_witness = first_guarded.and_then(|state| self.witness(state));
if resolutions.guarded_witness.is_some() {
resolutions.guarded_danger = first_guarded
.and_then(|state| {
self.guard_groups
.get(self.states[state].guard_group as usize)
})
.cloned()
.unwrap_or_default();
}
resolutions.min_alt_witness = first_min_alt.and_then(|state| self.witness(state));
resolutions.min_viable_alt_witness =
first_min_viable_alt.and_then(|state| self.witness(state));
resolutions.syntax_error_witness = first_syntax_error.and_then(|state| self.witness(state));
resolutions.tie_breaks = groups
.into_iter()
.map(|(mut group, shallowest, hazards)| {
group.witness = self.witness(shallowest);
let analyzed = hazards.len();
group.hazard = hazards
.iter()
.map(|(state, hazard)| GroupHazard::of(self, *state, hazard))
.reduce(|known, hazard| {
if hazard.outranks(&known) {
hazard
} else {
known
}
})
.map(|hazard| {
if analyzed < group.states {
hazard.partial()
} else {
hazard
}
});
group
})
.collect();
sort_tie_breaks(&mut resolutions.tie_breaks);
for (group, shallowest, states, verdicts) in guards {
let analyzed = verdicts.len();
let hazard = verdicts
.into_iter()
.reduce(|known, verdict| {
if stack_outranks(&verdict, &known) {
verdict
} else {
known
}
})
.map(|verdict| {
if analyzed < states {
partial_stack(verdict)
} else {
verdict
}
});
add_guard_group(
&mut resolutions.guard_groups,
GuardGroup {
danger: self
.guard_groups
.get(group as usize)
.cloned()
.unwrap_or_default(),
states,
witness: self.witness(shallowest),
hazard,
},
);
}
sort_guard_groups(&mut resolutions.guard_groups);
resolutions.show_stack_hijack();
resolutions
}
}
impl DecisionOutcome {
pub(crate) fn resolve_static_only(&mut self) -> bool {
let mut resolutions = EscapeResolutions::default();
match self.kind {
DecisionKind::Ll1 => {}
DecisionKind::Adaptive => return false,
DecisionKind::Static | DecisionKind::Hybrid => {
if let Some(precedence) = &mut self.precedence {
if precedence.adaptive_classes > 0 {
return false;
}
for table in precedence.tables.iter_mut().flatten() {
resolutions.merge(table.resolve_escapes());
}
precedence.escapes = 0;
} else if let Some(table) = &mut self.table {
resolutions.merge(table.resolve_escapes());
} else {
return false;
}
}
}
self.escapes = 0;
self.static_only = Some(resolutions);
true
}
}
#[cfg(test)]
mod tests {
use super::{EscapeResolutions, GuardGroup, StackHijackVerdict, TieBreak};
fn group(chosen: i32, dropped: &[i32], states: usize, witness: &[i32]) -> TieBreak {
TieBreak {
chosen,
dropped: dropped.to_vec(),
states,
witness: Some(witness.to_vec()),
hazard: None,
}
}
#[test]
fn tie_break_groups_merge_over_tables() {
let mut resolutions = EscapeResolutions {
tie_breaks: vec![group(1, &[2], 2, &[5, 6, 7]), group(3, &[4], 1, &[8])],
..EscapeResolutions::default()
};
resolutions.merge(EscapeResolutions {
tie_breaks: vec![group(1, &[2], 3, &[5]), group(1, &[3], 4, &[9])],
..EscapeResolutions::default()
});
assert_eq!(
resolutions.tie_breaks,
[
group(1, &[2], 5, &[5]),
group(1, &[3], 4, &[9]),
group(3, &[4], 1, &[8]),
]
);
}
fn guard(
danger: &[i32],
states: usize,
witness: &[i32],
hazard: Option<StackHijackVerdict>,
) -> GuardGroup {
GuardGroup {
danger: danger.to_vec(),
states,
witness: Some(witness.to_vec()),
hazard,
}
}
#[test]
fn guard_groups_merge_over_tables() {
let hijack = StackHijackVerdict::Hijack {
caller: 9,
extension: vec![5, 2],
};
let mut resolutions = EscapeResolutions {
guarded_witness: Some(vec![3]),
guarded_danger: vec![4],
guard_groups: vec![
guard(&[4], 3, &[3], Some(StackHijackVerdict::Covered)),
guard(&[9], 1, &[5, 6], Some(StackHijackVerdict::Covered)),
],
..EscapeResolutions::default()
};
resolutions.merge(EscapeResolutions {
guard_groups: vec![
guard(&[4], 2, &[7], None),
guard(&[9], 1, &[5], Some(hijack.clone())),
],
..EscapeResolutions::default()
});
assert_eq!(
resolutions.guard_groups,
[
guard(&[9], 2, &[5], Some(hijack)),
guard(&[4], 5, &[3], Some(StackHijackVerdict::Unknown)),
]
);
assert_eq!(resolutions.guarded_witness, Some(vec![5]));
assert_eq!(resolutions.guarded_danger, [9]);
assert_eq!(resolutions.stack_hijacks().count(), 1);
}
}