regast-core 0.1.0

use crate::{IrId, IrKind, IrPool, Value, mkeps::mkeps};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct RectId(pub(crate) u32);

#[derive(Clone, Debug)]
pub enum Rect {
    Id,
    Alt(RectId, RectId),
    Seq(RectId, RectId),
    Star(RectId),
    IntoLeft(RectId),
    IntoRight(RectId),
    SeqPrepend(Value, RectId),
    SeqAppend(RectId, Value),
}

impl Rect {
    pub fn apply(&self, pool: &IrPool, value: Value) -> Value {
        match self {
            Self::Id => value,
            Self::Alt(left, right) => match value {
                Value::Left(value) => Value::Left(Box::new(pool.rect(*left).apply(pool, *value))),
                Value::Right(value) => {
                    Value::Right(Box::new(pool.rect(*right).apply(pool, *value)))
                }
                _ => unreachable!("Alt rectification requires branch value"),
            },
            Self::Seq(left, right) => {
                let Value::Seq(first, second) = value else {
                    unreachable!("Seq rectification requires sequence value")
                };
                Value::Seq(
                    Box::new(pool.rect(*left).apply(pool, *first)),
                    Box::new(pool.rect(*right).apply(pool, *second)),
                )
            }
            Self::Star(rect) => {
                let Value::Stars(values) = value else {
                    unreachable!("Star rectification requires repetition value")
                };
                Value::Stars(
                    values
                        .into_iter()
                        .map(|value| pool.rect(*rect).apply(pool, value))
                        .collect(),
                )
            }
            Self::IntoLeft(rect) => Value::Left(Box::new(pool.rect(*rect).apply(pool, value))),
            Self::IntoRight(rect) => Value::Right(Box::new(pool.rect(*rect).apply(pool, value))),
            Self::SeqPrepend(prefix, rect) => Value::Seq(
                Box::new(prefix.clone()),
                Box::new(pool.rect(*rect).apply(pool, value)),
            ),
            Self::SeqAppend(rect, suffix) => Value::Seq(
                Box::new(pool.rect(*rect).apply(pool, value)),
                Box::new(suffix.clone()),
            ),
        }
    }
}

pub fn simp(pool: &mut IrPool, root: IrId) -> (IrId, RectId) {
    match pool.kind(root).clone() {
        IrKind::Zero | IrKind::One | IrKind::Anchor(..) | IrKind::Class(..) => (root, RectId(0)),
        IrKind::Star(inner, prov, greedy) => {
            let (simple, rect) = simp(pool, inner);
            let result = pool.star(simple, prov, greedy);
            if rect.0 == 0 {
                (result, RectId(0))
            } else {
                let star_rect = pool.add_rect(Rect::Star(rect));
                (result, star_rect)
            }
        }
        IrKind::Alt(left, right, prov, ordered) => simplify_alt(pool, left, right, prov, ordered),
        IrKind::Seq(left, right, prov) => simplify_seq(pool, left, right, prov),
    }
}

fn simplify_alt(
    pool: &mut IrPool,
    left: IrId,
    right: IrId,
    prov: crate::Prov,
    ordered: bool,
) -> (IrId, RectId) {
    let (simple_left, left_rect) = simp(pool, left);
    let (simple_right, right_rect) = simp(pool, right);
    if simple_left == pool.zero() {
        let rect = pool.add_rect(Rect::IntoRight(right_rect));
        return (simple_right, rect);
    }
    if simple_right == pool.zero() {
        let rect = pool.add_rect(Rect::IntoLeft(left_rect));
        return (simple_left, rect);
    }
    if simple_left == simple_right {
        let rect = pool.add_rect(Rect::IntoLeft(left_rect));
        return (simple_left, rect);
    }
    let result = pool.alt(simple_left, simple_right, prov, ordered);
    let rect = if left_rect.0 == 0 && right_rect.0 == 0 {
        RectId(0)
    } else {
        pool.add_rect(Rect::Alt(left_rect, right_rect))
    };
    (result, rect)
}

fn simplify_seq(pool: &mut IrPool, left: IrId, right: IrId, prov: crate::Prov) -> (IrId, RectId) {
    let (simple_left, left_rect) = simp(pool, left);
    let (simple_right, right_rect) = simp(pool, right);
    if simple_left == pool.zero() || simple_right == pool.zero() {
        return (pool.zero(), RectId(0));
    }
    if simple_left == pool.one() {
        let prefix = mkeps(pool, left);
        let rect = pool.add_rect(Rect::SeqPrepend(prefix, right_rect));
        return (simple_right, rect);
    }
    if simple_right == pool.one() {
        let suffix = mkeps(pool, right);
        let rect = pool.add_rect(Rect::SeqAppend(left_rect, suffix));
        return (simple_left, rect);
    }
    let result = pool.seq(simple_left, simple_right, prov);
    let rect = if left_rect.0 == 0 && right_rect.0 == 0 {
        RectId(0)
    } else {
        pool.add_rect(Rect::Seq(left_rect, right_rect))
    };
    (result, rect)
}