regast_core/

pool.rs

use std::collections::HashMap;

use regast_syntax::{AnchorKind, ClassSet};

use crate::{IrId, IrKind, Prov, ir::ClassSetId, simp::Rect};

#[derive(Clone, Debug)]
pub struct IrPool {
    kinds: Vec<IrKind>,
    dedup: HashMap<IrKind, IrId>,
    class_sets: Vec<ClassSet>,
    class_dedup: HashMap<ClassSet, ClassSetId>,
    nullable: Vec<Option<bool>>,
    pub(crate) deriv_memo: HashMap<(IrId, char, bool, bool), IrId>,
    pub(crate) rects: Vec<Rect>,
}

impl Default for IrPool {
    fn default() -> Self {
        let mut pool = Self {
            kinds: Vec::new(),
            dedup: HashMap::new(),
            class_sets: Vec::new(),
            class_dedup: HashMap::new(),
            nullable: Vec::new(),
            deriv_memo: HashMap::new(),
            rects: vec![Rect::Id],
        };
        pool.intern(IrKind::Zero);
        pool.intern(IrKind::One);
        pool
    }
}

impl IrPool {
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    #[must_use]
    pub const fn zero(&self) -> IrId {
        IrId(0)
    }

    #[must_use]
    pub const fn one(&self) -> IrId {
        IrId(1)
    }

    /// Intern a normalized character set.
    ///
    /// # Panics
    ///
    /// Panics if more than `u32::MAX` distinct sets are interned.
    pub fn class_set(&mut self, set: ClassSet) -> ClassSetId {
        if let Some(id) = self.class_dedup.get(&set) {
            return *id;
        }
        let id = ClassSetId(u32::try_from(self.class_sets.len()).expect("class arena exceeds u32"));
        self.class_sets.push(set.clone());
        self.class_dedup.insert(set, id);
        id
    }

    #[must_use]
    pub fn get_class_set(&self, id: ClassSetId) -> &ClassSet {
        &self.class_sets[id.0 as usize]
    }

    pub fn class(&mut self, set: ClassSetId, prov: Prov) -> IrId {
        if self.get_class_set(set).is_empty() {
            return self.zero();
        }
        self.intern(IrKind::Class(set, prov))
    }

    pub fn anchor(&mut self, kind: AnchorKind, prov: Prov) -> IrId {
        self.intern(IrKind::Anchor(kind, prov))
    }

    pub fn alt(&mut self, left: IrId, right: IrId, prov: Prov, ordered: bool) -> IrId {
        self.intern(IrKind::Alt(left, right, prov, ordered))
    }

    pub fn seq(&mut self, left: IrId, right: IrId, prov: Prov) -> IrId {
        self.intern(IrKind::Seq(left, right, prov))
    }

    pub fn star(&mut self, inner: IrId, prov: Prov, greedy: bool) -> IrId {
        self.intern(IrKind::Star(inner, prov, greedy))
    }

    pub(crate) fn intern(&mut self, kind: IrKind) -> IrId {
        if let Some(id) = self.dedup.get(&kind) {
            return *id;
        }
        let id = IrId(u32::try_from(self.kinds.len()).expect("IR arena exceeds u32"));
        self.kinds.push(kind.clone());
        self.nullable.push(None);
        self.dedup.insert(kind, id);
        id
    }

    #[must_use]
    pub fn kind(&self, id: IrId) -> &IrKind {
        &self.kinds[id.0 as usize]
    }

    #[must_use]
    pub fn len(&self) -> usize {
        self.kinds.len()
    }

    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.kinds.is_empty()
    }

    /// Return whether `root` accepts the empty string, caching every visited result.
    ///
    /// # Panics
    ///
    /// Panics only if the IR arena's internal child-reference invariant is broken.
    pub fn nullable(&mut self, root: IrId) -> bool {
        if let Some(value) = self.nullable[root.0 as usize] {
            return value;
        }
        let mut stack = vec![(root, false)];
        while let Some((id, expanded)) = stack.pop() {
            if self.nullable[id.0 as usize].is_some() {
                continue;
            }
            if !expanded {
                stack.push((id, true));
                match self.kind(id) {
                    IrKind::Alt(left, right, _, _) | IrKind::Seq(left, right, _) => {
                        stack.push((*right, false));
                        stack.push((*left, false));
                    }
                    IrKind::Zero
                    | IrKind::One
                    | IrKind::Anchor(..)
                    | IrKind::Class(..)
                    | IrKind::Star(..) => {}
                }
                continue;
            }
            let value = match self.kind(id) {
                IrKind::Zero | IrKind::Anchor(..) | IrKind::Class(..) => false,
                IrKind::One | IrKind::Star(..) => true,
                IrKind::Alt(left, right, _, _) => {
                    self.nullable[left.0 as usize].expect("left computed")
                        || self.nullable[right.0 as usize].expect("right computed")
                }
                IrKind::Seq(left, right, _) => {
                    self.nullable[left.0 as usize].expect("left computed")
                        && self.nullable[right.0 as usize].expect("right computed")
                }
            };
            self.nullable[id.0 as usize] = Some(value);
        }
        self.nullable[root.0 as usize].expect("root computed")
    }

    pub(crate) fn prefers_empty(&mut self, root: IrId) -> bool {
        match self.kind(root).clone() {
            IrKind::One => true,
            IrKind::Star(_, _, greedy) => !greedy,
            IrKind::Alt(left, right, _, true) => {
                if self.nullable(left) {
                    self.prefers_empty(left)
                } else {
                    self.prefers_empty(right)
                }
            }
            IrKind::Seq(left, right, _) => self.prefers_empty(left) && self.prefers_empty(right),
            IrKind::Zero | IrKind::Anchor(..) | IrKind::Class(..) | IrKind::Alt(..) => false,
        }
    }

    pub(crate) fn add_rect(&mut self, rect: Rect) -> crate::simp::RectId {
        if matches!(rect, Rect::Id) {
            return crate::simp::RectId(0);
        }
        let id = crate::simp::RectId(
            u32::try_from(self.rects.len()).expect("rectification arena exceeds u32"),
        );
        self.rects.push(rect);
        id
    }

    #[must_use]
    pub(crate) fn rect(&self, id: crate::simp::RectId) -> &Rect {
        &self.rects[id.0 as usize]
    }

    #[must_use]
    pub fn display(&self, root: IrId) -> String {
        match self.kind(root) {
            IrKind::Zero => "0".into(),
            IrKind::One => "1".into(),
            IrKind::Anchor(kind, _) => format!("{kind:?}"),
            IrKind::Class(..) => "class".into(),
            IrKind::Alt(left, right, _, _) => {
                format!("({}+{})", self.display(*left), self.display(*right))
            }
            IrKind::Seq(left, right, _) => {
                format!("({}·{})", self.display(*left), self.display(*right))
            }
            IrKind::Star(inner, _, greedy) => format!(
                "({})*{}",
                self.display(*inner),
                if *greedy { "" } else { "?" }
            ),
        }
    }
}