ielr 0.1.1

/*
 * Copyright 2022 Arnaud Golfouse
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

//! Procedures related to conflict resolution.
//!
//! Those will be used during phase 3, to determine the dominant contribution in a state.

use super::GrammarData;
use crate::{
    indices::{ItemIdx, NonZero},
    input::{ConflictSolution, ConflictingAction, ProdIdx},
    output::{error::ConflictContributions, Lookahead},
    structures::{BitSet, Map},
};
use std::ops::{BitOr, BitOrAssign};

impl<'a> GrammarData<'a> {
    /// Check if a solution exists to the `action1` vs `action2` conflict.
    fn solution_exists(
        &self,
        cache: &mut ConflictResolutionCache,
        solutions_used: &mut BitSet,
        action1: ShiftOrReduce,
        action2: ShiftOrReduce,
        lookahead: Lookahead,
    ) -> Prefer {
        if self.grammar.conflict_solutions.len() < 10 {
            let mut prefer = Prefer::None;
            for (index, solution) in self.grammar.conflict_solutions.iter().enumerate() {
                if solution.prefer.matches(action1, lookahead)
                    && solution.over.matches(action2, lookahead)
                {
                    solutions_used.insert(index);
                    prefer |= Prefer::First;
                    if prefer == Prefer::Both {
                        return Prefer::Both;
                    }
                }
                if solution.prefer.matches(action2, lookahead)
                    && solution.over.matches(action1, lookahead)
                {
                    solutions_used.insert(index);
                    prefer |= Prefer::Second;
                    if prefer == Prefer::Both {
                        return Prefer::Both;
                    }
                }
            }
            prefer
        } else {
            cache.solution_exists(solutions_used, action1, action2, lookahead)
        }
    }

    /// Assuming all of `contributions` selected by `conflicting` have a conflict on
    /// `lookahead`, determine the dominant contribution.
    ///
    /// # Returns
    /// - `None` if there is no dominant contribution.
    /// - `Some(0)` if the dominant contribution is 'shift'.
    /// - `Some(i)` if the dominant contribution is the `i-1`th reduce.
    ///
    /// Also returns the indices of the conflict resolutions used.
    // TODO(perf): this is responsible for most of the runtime for a conflict resolution-heavy grammar.
    pub(crate) fn dominant_contribution(
        &self,
        solutions_used: &mut BitSet,
        cache: &mut ConflictResolutionCache,
        contributions: &ConflictContributions,
        // TODO(perf): a BitSet might be used instead.
        conflicting: &[ContributionIndex],
        lookahead: Lookahead,
    ) -> ContributionSelection {
        // j ∈ graph[i] ⇒ j is preferred over i
        for vector in &mut cache.dominant_contribution_dominee {
            vector.clear();
        }
        for _ in 0..conflicting
            .len()
            .saturating_sub(cache.dominant_contribution_dominee.len())
        {
            cache
                .dominant_contribution_dominee
                .push(Vec::with_capacity(16));
        }
        for (index1, &selected1) in conflicting.iter().enumerate() {
            let contrib1 = contributions.index(selected1).unwrap();
            for (index2, &selected2) in conflicting.iter().enumerate().skip(index1 + 1) {
                let contrib2 = contributions.index(selected2).unwrap();

                let (prefer, over) = match self.solution_exists(
                    cache,
                    solutions_used,
                    contrib1,
                    contrib2,
                    lookahead,
                ) {
                    Prefer::First => (index1, index2),
                    Prefer::Second => (index2, index1),
                    Prefer::Both => return ContributionSelection::ConflictingSolutions,
                    Prefer::None => return ContributionSelection::MissingSolution,
                };
                cache.dominant_contribution_dominee[over].push(prefer as ReduceIdx);
            }
        }

        if let Err(_handle_this) = graph_has_cycle(
            &cache.dominant_contribution_dominee[0..conflicting.len()],
            &mut cache.graph_has_cycle_visited,
            &mut cache.graph_has_cycle_rec_stack,
            &mut cache.graph_has_cycle_stack,
        ) {
            return ContributionSelection::ConflictingSolutions;
        }
        let mut dominant = 0;
        while let Some(x) = cache.dominant_contribution_dominee[dominant as usize].first() {
            dominant = *x;
        }

        ContributionSelection::Some(conflicting[dominant as usize])
    }
}

#[derive(Clone, Copy, Debug, PartialEq)]
enum Prefer {
    None = 0b00,
    First = 0b01,
    Second = 0b10,
    Both = 0b11,
}

impl BitOr for Prefer {
    type Output = Self;

    fn bitor(self, rhs: Self) -> Self::Output {
        match self as u8 | rhs as u8 {
            0b00 => Prefer::None,
            0b01 => Prefer::First,
            0b10 => Prefer::Second,
            _ => Prefer::Both,
        }
    }
}

impl BitOrAssign for Prefer {
    fn bitor_assign(&mut self, rhs: Self) {
        *self = *self | rhs;
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(crate) enum ContributionSelection {
    Some(ContributionIndex),
    MissingSolution,
    ConflictingSolutions,
}

/// One of 'shift' or 'reduce' action.
///
/// Does not contain the lookahead upon which this action might occur.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub(crate) enum ShiftOrReduce {
    /// A shift action.
    Shift,
    /// A reduce action: contains the production to reduce.
    Reduce(ProdIdx),
}

// Note: technically this should be NonZero<min<ItemIdx, ProdIdxRaw>>
pub(crate) type ReduceIdx = ItemIdx;

/// Index in [`ConflictContributions`].
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(crate) enum ContributionIndex {
    /// Indexes the shift action.
    Shift,
    /// Indexes the reduce actions.
    Reduce(NonZero<ReduceIdx>),
}

impl ContributionIndex {
    /// Creates a new `ContributionIndex` for the `index`-th reduce of a
    /// [`ConflictContributions`].
    pub(crate) fn new_reduce(index: ReduceIdx) -> Self {
        Self::Reduce(NonZero::<ReduceIdx>::new(index.saturating_add(1)).unwrap())
    }
}

impl ConflictContributions {
    /// Index `self` with `index`.
    ///
    /// If `self` does not contain the action corresponding with `index`, returns `None`.
    pub(crate) fn index(&self, index: ContributionIndex) -> Option<ShiftOrReduce> {
        match index {
            ContributionIndex::Shift => {
                if self.has_shift {
                    Some(ShiftOrReduce::Shift)
                } else {
                    None
                }
            }
            ContributionIndex::Reduce(index) => self
                .reduces
                .get(index.get() as usize - 1)
                .map(|prod| ShiftOrReduce::Reduce(*prod)),
        }
    }
}

/// A cache for data associated with conflict resolution.
///
/// This serves two purposes:
/// - Avoid recomputing already found conflict solutions.
/// - Keep some buffers around, so we don't allocate/deallocate a lot.
#[derive(Debug)]
pub(crate) struct ConflictResolutionCache {
    solutions_as_set: Map<ConflictSolution, usize>,
    preference_cache: Map<(ShiftOrReduce, ShiftOrReduce, Lookahead), Prefer>,
    /// Used in `graph_has_cycle`. Avoids dropping/creating the BitSet each time.
    graph_has_cycle_visited: BitSet<ReduceIdx>,
    /// Used in `graph_has_cycle`. Avoids dropping/creating the BitSet each time.
    graph_has_cycle_rec_stack: BitSet<ReduceIdx>,
    /// Used in `graph_has_cycle`. Avoids dropping/creating the Vec each time.
    graph_has_cycle_stack: Vec<(ReduceIdx, ReduceIdx)>,
    dominant_contribution_dominee: Vec<Vec<ReduceIdx>>,
}

impl ConflictResolutionCache {
    pub(crate) fn new(conflict_solutions: &[ConflictSolution]) -> Self {
        let mut solutions_as_set = Map::default();
        solutions_as_set.reserve(conflict_solutions.len());
        for (index, solution) in conflict_solutions.iter().copied().enumerate() {
            solutions_as_set.insert(solution, index);
        }
        Self {
            solutions_as_set,
            preference_cache: Map::default(),
            graph_has_cycle_visited: BitSet::with_capacity(64),
            graph_has_cycle_rec_stack: BitSet::with_capacity(64),
            graph_has_cycle_stack: Vec::with_capacity(16),
            dominant_contribution_dominee: Vec::with_capacity(16),
        }
    }

    /// Check if a solution exists to the `action1` vs `action2` conflict.
    fn solution_exists(
        &mut self,
        solutions_used: &mut BitSet,
        action1: ShiftOrReduce,
        action2: ShiftOrReduce,
        lookahead: Lookahead,
    ) -> Prefer {
        let cache_entry = match self.preference_cache.entry((action1, action2, lookahead)) {
            std::collections::hash_map::Entry::Occupied(occ) => return *occ.get(),
            std::collections::hash_map::Entry::Vacant(entry) => entry,
        };
        let to_try = |action| match action {
            ShiftOrReduce::Shift => [
                ConflictingAction::AnyShift,
                ConflictingAction::AnyShift,
                ConflictingAction::Shift(lookahead),
            ],
            ShiftOrReduce::Reduce(production) => [
                ConflictingAction::AnyReduce,
                ConflictingAction::Reduce(production),
                ConflictingAction::ReduceNode(production.lhs),
            ],
        };
        let to_try_1 = to_try(action1);
        let to_try_2 = to_try(action2);
        let mut prefer = Prefer::None;
        for action1 in to_try_1 {
            for action2 in to_try_2 {
                if let Some(&index) = self.solutions_as_set.get(&ConflictSolution {
                    prefer: action1,
                    over: action2,
                }) {
                    prefer |= Prefer::First;
                    solutions_used.insert(index);
                }
                if let Some(&index) = self.solutions_as_set.get(&ConflictSolution {
                    prefer: action2,
                    over: action1,
                }) {
                    prefer |= Prefer::Second;
                    solutions_used.insert(index);
                }
            }
        }
        *cache_entry.insert(prefer)
    }
}

impl ConflictingAction {
    /// Returns `true` if `(action, lookahead)` matches `self`.
    ///
    /// - [`Self::AnyShift`]: matches any [`ShiftOrReduce::Shift`] action, regardless of
    /// `lookahead`.
    /// - [`Self::AnyReduce`]: matches any [`ShiftOrReduce::Reduce`] action,
    /// regardless of `lookahead`.
    /// - [`Self::Shift`]`(l)`: matches any [`ShiftOrReduce::Shift`] action when
    /// `l == lookahead`.
    /// - [`Self::Reduce`]`(p)`: matches any [`ShiftOrReduce::Reduce`]`(p)` action,
    /// regardless of `lookahead`.
    fn matches(&self, action: ShiftOrReduce, lookahead: Lookahead) -> bool {
        match (*self, action) {
            (ConflictingAction::AnyShift, ShiftOrReduce::Shift) => true,
            (ConflictingAction::AnyReduce, ShiftOrReduce::Reduce(_)) => true,
            (ConflictingAction::Shift(l1), ShiftOrReduce::Shift) => l1 == lookahead,
            (ConflictingAction::Reduce(prod1), ShiftOrReduce::Reduce(prod2)) => prod1 == prod2,
            (ConflictingAction::ReduceNode(node), ShiftOrReduce::Reduce(prod)) => node == prod.lhs,
            _ => false,
        }
    }
}

fn graph_has_cycle(
    graph: &[Vec<ReduceIdx>],
    visited: &mut BitSet<ReduceIdx>,
    rec_stack: &mut BitSet<ReduceIdx>,
    stack: &mut Vec<(ReduceIdx, ReduceIdx)>,
) -> Result<(), Vec<ReduceIdx>> {
    visited.clear();
    for root_node in 0..graph.len() as ReduceIdx {
        if !visited.insert(root_node) {
            continue;
        }
        rec_stack.clear();
        rec_stack.insert(root_node);
        stack.clear();
        stack.push((root_node, 0));
        while let Some((node, index)) = stack.last_mut() {
            let neighbors = graph
                .get(*node as usize)
                .map(|n| n.as_slice())
                .unwrap_or_default();
            let next = match neighbors.get(*index as usize) {
                Some(next) => {
                    if rec_stack.contains(*next) {
                        return Err(stack
                            .iter()
                            .map(|(n, _)| *n)
                            .take_while(|n| !rec_stack.contains(*n))
                            .collect());
                    }
                    *index += 1;
                    *next
                }
                None => {
                    rec_stack.remove(*node);
                    stack.pop();
                    continue;
                }
            };
            if visited.insert(next) {
                rec_stack.insert(next);
                stack.push((next, 0))
            }
        }
    }
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        input::{ConflictSolution, Grammar},
        test_common::nodes::{N1, N2, N3},
    };

    #[test]
    fn prefer_bitor() {
        for prefer in [Prefer::None, Prefer::First, Prefer::Second, Prefer::Both] {
            assert_eq!(prefer | Prefer::None, prefer);
            assert_eq!(Prefer::None | prefer, prefer);
        }
        for prefer in [Prefer::None, Prefer::First, Prefer::Second, Prefer::Both] {
            assert_eq!(prefer | Prefer::Both, Prefer::Both);
            assert_eq!(Prefer::Both | prefer, Prefer::Both);
        }
        assert_eq!(Prefer::First | Prefer::First, Prefer::First);
        assert_eq!(Prefer::Second | Prefer::Second, Prefer::Second);
        assert_eq!(Prefer::First | Prefer::Second, Prefer::Both);
    }

    #[test]
    fn solution_exists() {
        let mut grammar = Grammar::new();
        let p1 = grammar.add_production(N1, vec![]).unwrap();
        let p2 = grammar.add_production(N2, vec![]).unwrap();
        let grammar_data = GrammarData::new(&grammar).unwrap();
        let mut conflicting_actions =
            ConflictResolutionCache::new(&grammar_data.conflict_solutions);
        assert_eq!(
            grammar_data.solution_exists(
                &mut conflicting_actions,
                &mut BitSet::new(),
                ShiftOrReduce::Reduce(p1),
                ShiftOrReduce::Reduce(p2),
                Lookahead::Eof,
            ),
            Prefer::None
        );
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::Reduce(p1),
            over: ConflictingAction::Reduce(p2),
        });
        let grammar_data = GrammarData::new(&grammar).unwrap();
        let mut conflicting_actions =
            ConflictResolutionCache::new(&grammar_data.conflict_solutions);
        assert_eq!(
            grammar_data.solution_exists(
                &mut conflicting_actions,
                &mut BitSet::new(),
                ShiftOrReduce::Reduce(p1),
                ShiftOrReduce::Reduce(p2),
                Lookahead::Eof,
            ),
            Prefer::First
        );
        assert_eq!(
            grammar_data.solution_exists(
                &mut conflicting_actions,
                &mut BitSet::new(),
                ShiftOrReduce::Reduce(p2),
                ShiftOrReduce::Reduce(p1),
                Lookahead::Eof,
            ),
            Prefer::Second
        );
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::Reduce(p2),
            over: ConflictingAction::Reduce(p1),
        });
        let grammar_data = GrammarData::new(&grammar).unwrap();
        let mut conflicting_actions =
            ConflictResolutionCache::new(&grammar_data.conflict_solutions);
        assert_eq!(
            grammar_data.solution_exists(
                &mut conflicting_actions,
                &mut BitSet::new(),
                ShiftOrReduce::Reduce(p2),
                ShiftOrReduce::Reduce(p1),
                Lookahead::Eof,
            ),
            Prefer::Both
        );
        assert_eq!(
            grammar_data.solution_exists(
                &mut conflicting_actions,
                &mut BitSet::new(),
                ShiftOrReduce::Reduce(p1),
                ShiftOrReduce::Reduce(p2),
                Lookahead::Eof,
            ),
            Prefer::Both
        );
        grammar.conflict_solutions = Vec::new();
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::AnyReduce,
            over: ConflictingAction::AnyShift,
        });
        let grammar_data = GrammarData::new(&grammar).unwrap();
        let mut conflicting_actions =
            ConflictResolutionCache::new(&grammar_data.conflict_solutions);
        assert_eq!(
            grammar_data.solution_exists(
                &mut conflicting_actions,
                &mut BitSet::new(),
                ShiftOrReduce::Reduce(p1),
                ShiftOrReduce::Reduce(p2),
                Lookahead::Eof,
            ),
            Prefer::None
        );
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::AnyReduce,
            over: ConflictingAction::AnyReduce,
        });
        let grammar_data = GrammarData::new(&grammar).unwrap();
        let mut conflicting_actions =
            ConflictResolutionCache::new(&grammar_data.conflict_solutions);
        assert_eq!(
            grammar_data.solution_exists(
                &mut conflicting_actions,
                &mut BitSet::new(),
                ShiftOrReduce::Reduce(p1),
                ShiftOrReduce::Reduce(p2),
                Lookahead::Eof,
            ),
            Prefer::Both
        );
    }

    #[test]
    fn cyclic_graphs() {
        // 0 -> 2 -> 3
        // |  7
        // v /
        // 1/
        let graph1 = vec![vec![1, 2], vec![2], vec![3], vec![]];
        assert!(graph_has_cycle(
            &graph1,
            &mut BitSet::new(),
            &mut BitSet::new(),
            &mut Vec::new()
        )
        .is_ok());

        // 0 <- 2 -> 3
        // |  7
        // v /
        // 1/
        let graph1 = vec![vec![1], vec![2], vec![0, 3], vec![]];
        assert!(graph_has_cycle(
            &graph1,
            &mut BitSet::new(),
            &mut BitSet::new(),
            &mut Vec::new()
        )
        .is_err());
    }

    #[test]
    fn cycle_in_dominant_contribution() {
        // short cycle
        let mut grammar = Grammar::new();
        let production1 = grammar.add_production(N1, vec![]).unwrap();
        let production2 = grammar.add_production(N2, vec![]).unwrap();
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::Reduce(production1),
            over: ConflictingAction::Reduce(production2),
        });
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::Reduce(production2),
            over: ConflictingAction::Reduce(production1),
        });
        let grammar_data = GrammarData::new(&grammar).unwrap();
        let mut conflicting_actions =
            ConflictResolutionCache::new(&grammar_data.conflict_solutions);
        let index = grammar_data.dominant_contribution(
            &mut BitSet::new(),
            &mut conflicting_actions,
            &ConflictContributions {
                has_shift: false,
                reduces: vec![production1, production2],
            },
            &[
                ContributionIndex::new_reduce(0),
                ContributionIndex::new_reduce(1),
            ],
            Lookahead::Eof,
        );
        assert_eq!(index, ContributionSelection::ConflictingSolutions);

        // long cycle
        let mut grammar = Grammar::new();
        let production1 = grammar.add_production(N1, vec![]).unwrap();
        let production2 = grammar.add_production(N2, vec![]).unwrap();
        let production3 = grammar.add_production(N3, vec![]).unwrap();
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::Reduce(production1),
            over: ConflictingAction::Reduce(production2),
        });
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::Reduce(production2),
            over: ConflictingAction::Reduce(production3),
        });
        grammar.add_conflict_solution(ConflictSolution {
            prefer: ConflictingAction::Reduce(production3),
            over: ConflictingAction::Reduce(production1),
        });
        let grammar_data = GrammarData::new(&grammar).unwrap();
        let mut conflicting_actions =
            ConflictResolutionCache::new(&grammar_data.conflict_solutions);
        let index = grammar_data.dominant_contribution(
            &mut BitSet::new(),
            &mut conflicting_actions,
            &ConflictContributions {
                has_shift: false,
                reduces: vec![production1, production2, production3],
            },
            &[
                ContributionIndex::new_reduce(0),
                ContributionIndex::new_reduce(1),
                ContributionIndex::new_reduce(2),
            ],
            Lookahead::Eof,
        );
        assert_eq!(index, ContributionSelection::ConflictingSolutions);
    }
}