Stack Effects 2.0

stack_effects.rs

use std::cell::RefCell;
use std::collections::HashSet;
use std::rc::Rc;

type Result<T> = std::result::Result<T, AlignError>;

#[derive(Debug, Clone, PartialEq)]
struct StackEffect {
    inputs: StackSequence,
    outputs: StackSequence,
}

impl StackEffect {
    pub fn new(inputs: Vec<ElementPtr>, outputs: Vec<ElementPtr>) -> Self {
        StackEffect {
            inputs: StackSequence::new(inputs),
            outputs: StackSequence::new(outputs),
        }
    }

    pub fn chain(mut self, mut other: Self) -> Result<Self> {
        let reps = align(&mut self.outputs, &mut other.inputs)?;
        for r in reps {
            self.inputs.apply_replacement(&r);
            other.outputs.apply_replacement(&r);
        }

        Ok(StackEffect {
            inputs: self.inputs,
            outputs: other.outputs,
        })
    }

    pub fn align(&mut self, other: &mut Self, check_self: bool, check_other: bool) -> Result<Vec<Replacement>> {
        println!("aligning...");
        println!("    {:?}", self);
        println!("    {:?}", other);

        let ddof_a = self.degrees_of_freedom();
        let ddof_b = other.degrees_of_freedom();

        let ir = align(&mut self.inputs, &mut other.inputs)?;
        for r in &ir {
            self.outputs.apply_replacement(r);
            other.outputs.apply_replacement(r);
        }

        let or = align(&mut self.outputs, &mut other.outputs)?;
        for r in &or {
            self.inputs.apply_replacement(r);
            other.inputs.apply_replacement(r);
        }

        if check_self && self.degrees_of_freedom() < ddof_a ||
            check_other && other.degrees_of_freedom() < ddof_b
        {
            return Err(AlignError::DdofLost);
        }

        let mut replacements = ir;
        replacements.extend(or);
        Ok(replacements)
    }

    fn reduce(mut self) -> Self {
        let out_counts: Vec<usize> = self
            .inputs
            .seq
            .iter()
            .map(|i| self.outputs.seq.iter().filter(|&o| o == i).count())
            .collect();

        let mut ins = self.inputs.seq.drain(..);
        let mut out = self.outputs.seq.drain(..);
        let mut out_counts = out_counts.into_iter();

        let (mut a, mut b) = (vec![], vec![]);
        loop {
            match (ins.next(), out.next()) {
                (Some(i), Some(o)) => {
                    let c = out_counts.next().unwrap();
                    let pred = i != o || c > 1;
                    if pred || i.is_ellipsis() && o.is_ellipsis() && i == o {
                        a.push(i);
                        b.push(o);
                    }
                    if pred {
                        break;
                    }
                }
                (None, Some(o)) => b.push(o),
                (Some(i), None) => a.push(i),
                (None, None) => break,
            }
        }

        a.extend(ins);
        b.extend(out);

        StackEffect::new(a, b)
    }

    fn degrees_of_freedom(&self) -> ExtNum<i32> {
        let mut non_free = HashSet::<*const Element>::new();
        let mut dof = ExtNum::finite(0);

        for i in self.inputs.seq.iter() {
            non_free.insert(&**i);
        }

        for o in self.outputs.seq.iter() {
            if non_free.insert(&**o) {
                match &**o {
                    Element::Item(_) => dof += ExtNum::finite(1),
                    Element::Ellipsis(_) => dof = ExtNum::inf(),
                    Element::SubEffect(_, se) => dof += se.borrow().degrees_of_freedom(),
                }
            }
        }

        dof
    }
}

#[derive(Debug, Copy, Clone, PartialOrd)]
enum ExtNum<T> {
    Finite(T),
    Inf,
}

impl<T> ExtNum<T> {
    fn finite(value: T) -> Self {
        ExtNum::Finite(value)
    }

    fn inf() -> Self {
        ExtNum::Inf
    }
}

impl<T: PartialEq> PartialEq for ExtNum<T> {
    fn eq(&self, rhs: &Self) -> bool {
        if let (ExtNum::Finite(a), ExtNum::Finite(b)) = (self, rhs) {
            a == b
        } else {
            false
        }
    }
}

impl<T: Copy> std::ops::AddAssign for ExtNum<T>
where
    T: std::ops::Add<T, Output = T>,
{
    fn add_assign(&mut self, rhs: Self) {
        match (self, rhs) {
            (ExtNum::Finite(ref mut a), ExtNum::Finite(ref b)) => *a = *a + *b,
            (s @ ExtNum::Finite(_), ExtNum::Inf)
            | (s @ ExtNum::Inf, ExtNum::Finite(_))
            | (s @ ExtNum::Inf, ExtNum::Inf) => *s = ExtNum::Inf,
        }
    }
}

impl<T: std::fmt::Display> std::fmt::Display for ExtNum<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            ExtNum::Finite(i) => write!(f, "{}", i),
            ExtNum::Inf => write!(f, "inf"),
        }
    }
}

type ElementPtr = Rc<Element>;

#[derive(Debug)]
enum Element {
    Ellipsis(String),
    Item(String),
    SubEffect(String, RefCell<StackEffect>),
}

impl Element {
    pub fn ellipsis(name: &str) -> ElementPtr {
        Rc::new(Element::Ellipsis(name.to_string()))
    }

    pub fn item(name: &str) -> ElementPtr {
        Rc::new(Element::Item(name.to_string()))
    }

    pub fn subeffect(name: &str, se: StackEffect) -> ElementPtr {
        Rc::new(Element::SubEffect(name.to_string(), RefCell::new(se)))
    }

    pub fn is_ellipsis(&self) -> bool {
        if let Element::Ellipsis(_) = self {
            true
        } else {
            false
        }
    }
}

impl std::cmp::PartialEq for Element {
    fn eq(&self, rhs: &Self) -> bool {
        self as *const _ == rhs as *const _
    }
}

#[derive(Debug, Clone, PartialEq)]
struct StackSequence {
    seq: Vec<ElementPtr>,
}

impl StackSequence {
    pub fn new(seq: Vec<ElementPtr>) -> Self {
        StackSequence { seq }
    }

    pub fn len(&self) -> usize {
        self.seq.len()
    }

    pub fn replace_seq(&mut self, item: &ElementPtr, seq: &[ElementPtr]) {
        // assumption: Ellipses are only allowed at index 0
        assert!(self.seq[0].is_ellipsis());

        if Rc::ptr_eq(&self.seq[0], item) {
            let mut seq = seq.to_vec();
            seq.extend(self.seq.drain(1..));
            self.seq = seq;
        }

        for x in &self.seq {
            if let Element::SubEffect(_, se) = &**x {
                se.borrow_mut().inputs.replace_seq(item, seq);
                se.borrow_mut().outputs.replace_seq(item, seq);
            }
        }
    }

    pub fn replace(&mut self, item: &ElementPtr, with: &ElementPtr) {
        for x in &mut self.seq {
            if Rc::ptr_eq(x, item) {
                *x = with.clone();
            }

            if let Element::SubEffect(_, se) = &**x {
                se.borrow_mut().inputs.replace(item, with);
                se.borrow_mut().outputs.replace(item, with);
            }
        }
    }

    fn apply_replacement(&mut self, r: &Replacement) {
        match r {
            Replacement::Single(item, with) => self.replace(item, with),
            Replacement::Multi(item, with) => self.replace_seq(item, with),
        }
    }
}

#[derive(Debug)]
enum AlignError {
    Incompatible,
    DdofLost,
}

#[derive(Debug)]
enum Replacement {
    Single(ElementPtr, ElementPtr),
    Multi(ElementPtr, Vec<ElementPtr>),
}

fn align(a: &mut StackSequence, b: &mut StackSequence) -> Result<Vec<Replacement>> {
    use Element::*;

    let mut replacements = vec![];

    let (mut i, mut j) = (a.len(), b.len());
    while i > 0 && j > 0 {
        i -= 1;
        j -= 1;
        match (&*a.seq[i], &*b.seq[j]) {
            (Ellipsis(_), Ellipsis(_)) => {
                let item = b.seq[j].clone();
                let with = a.seq[i].clone();
                if item != with {
                    a.replace(&item, &with);
                    b.replace(&item, &with);
                    replacements.push(Replacement::Single(item, with));
                }
                return Ok(replacements);
            }
            (_, Ellipsis(_)) => {
                let item = b.seq[j].clone();
                let with = a.seq[..=i].to_vec();

                if with.contains(&item) {
                    return Err(AlignError::Incompatible);
                }

                a.replace_seq(&item, &with);
                b.replace_seq(&item, &with);
                replacements.push(Replacement::Multi(item, with));
                return Ok(replacements);
            }
            (Ellipsis(_), _) => {
                let item = a.seq[i].clone();
                let with = b.seq[..=j].to_vec();

                if with.contains(&item) {
                    return Err(AlignError::Incompatible);
                }

                a.replace_seq(&item, &with);
                b.replace_seq(&item, &with);
                replacements.push(Replacement::Multi(item, with));
                return Ok(replacements);
            }
            (Item(_), Item(_)) => {
                let item = b.seq[j].clone();
                let with = a.seq[i].clone();
                if item != with {
                    a.replace(&item, &with);
                    b.replace(&item, &with);
                    replacements.push(Replacement::Single(item, with));
                }
            }
            (Item(_), SubEffect(_, _)) => {
                let item = a.seq[i].clone();
                let with = b.seq[j].clone();

                a.replace(&item, &with);
                b.replace(&item, &with);
                replacements.push(Replacement::Single(item, with));
            }
            (SubEffect(_, _), Item(_)) => {
                let item = b.seq[j].clone();
                let with = a.seq[i].clone();

                a.replace(&item, &with);
                b.replace(&item, &with);
                replacements.push(Replacement::Single(item, with));
            }
            (SubEffect(_, ase), SubEffect(_, bse)) => {
                if a.seq[i] != b.seq[j] {
                    let sub_replacements = ase.borrow_mut().align(&mut *bse.borrow_mut(), true, false)?;

                    for r in sub_replacements {
                        a.apply_replacement(&r);
                        b.apply_replacement(&r);
                        replacements.push(r);
                    }
                }
            }
        }
    }
    panic!();
    Err(AlignError::Incompatible)
}

macro_rules! se {
    ($($i:ident)* -- $($o:ident)*) => (StackEffect::new(vec![$($i.clone()),*], vec![$($o.clone()),*]))
}

fn reduction() {
    let a = Element::ellipsis("a");
    let b = Element::ellipsis("b");
    let x = Element::item("x");
    let y = Element::item("y");
    let z = Element::item("z");

    assert_eq!(se!(a - -a), se!(a - -a).reduce());
    assert_eq!(se!(a - -a), se!(a x -- a x).reduce());
    assert_eq!(se!(a - -a), se!(a x y -- a x y).reduce());
    assert_eq!(se!(a -- a x), se!(a -- a x).reduce());
    assert_eq!(se!(a y -- a z), se!(a x y -- a x z).reduce());
    assert_eq!(se!(a y -- a z), se!(a y -- a z).reduce());
    assert_eq!(se!(a y x -- a z x), se!(a y x -- a z x).reduce());
    assert_eq!(se!(a x y -- a x x), se!(a x y -- a x x).reduce());
    assert_eq!(se!(a - -b), se!(a - -b).reduce());
    assert_eq!(se!(a x -- b x), se!(a x -- b x).reduce());
}

fn simple_chaining() {
    println!();
    let a = Element::ellipsis("a");
    let b = Element::ellipsis("b");
    let w = Element::item("w");
    let x = Element::item("x");
    let y = Element::item("y");
    let z = Element::item("z");

    assert_eq!(
        se!(a x y -- a y y),
        se!(a x y -- a y x).chain(se!(b w z -- b w w)).unwrap()
    );
    assert_eq!(
        se!(a z -- a z z),
        se!(a z -- a z z).chain(se!(b x y -- b y x)).unwrap()
    );
}

fn advanced_chaining() {
    println!();
    let a = Element::ellipsis("a");
    let b = Element::ellipsis("b");
    let c = Element::ellipsis("c");
    let x = Element::item("x");
    let y = Element::item("y");
    let f = Element::subeffect("f", se!(b - -c));

    // swap  (..a x y -- ..a y x)
    // call  (..b f(..b -- ..c) -- ..c)
    let swap = se!(a x y -- a y x);
    let call = se!(b f -- c);

    println!("{:?}", swap);
    println!("{:?}", call);
    println!("-------------------------------------------------------------");

    let result = swap.chain(call).unwrap();

    println!("{:?}", result);

    assert_eq!(se!(a f y -- c), result);
    println!();
}

fn expert_chaining() {
    println!();
    let a = Element::ellipsis("a");
    let b = Element::ellipsis("b");
    let c = Element::ellipsis("c");
    let d = Element::ellipsis("d");
    let x = Element::item("x");
    let f = Element::subeffect("f", se!(b - -c));
    let q = Element::subeffect("q", se!(d -- d x));

    // [ 42 ]  (..a -- ..a q(..d -- ..d x))
    // call  (..b f(..b -- ..c) -- ..c)
    let quot = se!(a -- a q);
    let call = se!(b f -- c);

    println!("{:?}", quot);
    println!("{:?}", call);
    println!("-------------------------------------------------------------");

    let result = quot.chain(call).unwrap();

    println!("{:?}", result);

    assert_eq!(se!(a -- a x), result);
    println!();
}

fn invalid_chaining() {
    println!();
    let a = Element::ellipsis("a");
    let b = Element::ellipsis("b");
    let d = Element::ellipsis("d");
    let x = Element::item("x");
    let f = Element::subeffect("f", se!(b - -b));
    let q = Element::subeffect("q", se!(d -- d x));

    // [ 42 ]  (..a -- ..a q(..d -- ..d x))
    // call           (..b f(..b -- ..b) -- ..b)
    let quot = se!(a -- a q);
    let call = se!(b f -- b);

    println!("{:?}", quot);
    println!("{:?}", call);
    println!("-------------------------------------------------------------");

    let result = quot.chain(call).unwrap_err();

    println!("{:?}", result);
}

fn super_chaining() {
    println!();
    let a = Element::ellipsis("a");
    let b = Element::ellipsis("b");
    let c = Element::ellipsis("c");
    let d = Element::ellipsis("d");
    let e = Element::ellipsis("e");
    let f = Element::ellipsis("f");
    let x = Element::item("x");
    let z = Element::item("z");
    let y = Element::subeffect("y", se!(a - -b));
    let n = Element::subeffect("n", se!(a - -b));
    let q = Element::subeffect("q", se!(d -- d x));
    let r = Element::subeffect("r", se!(f z -- f z z));

    // [dup ]  (..e -- ..e r(..f z -- ..f z z))
    // [ 42 ]  (..c -- ..c q(..d -- ..d x))
    // branch  (..a y(..a -- ..b) n(..a -- ..b) -- ..b)
    let dup = se!(e -- e r);
    let quot = se!(c -- c q);
    let branch = se!(a y n -- b);

    println!("{:?}", quot);
    println!("{:?}", branch);
    println!("-------------------------------------------------------------");

    let result = dup.chain(quot).unwrap().chain(branch).unwrap();

    println!("{:?}", result);

    panic!("We should not get a result.
            Currently we can not detect the DDOF loss because after replacing (..a -- ..b) with (..d -- ..d x)
            the procedure thinks it is safe to replace (..d -- ..d x) with (..f z -- ..f z z).
            
            TODO:
            Implement some kind of guard flag that determines if a value is allowed to be adjusted.
            Some ideas:
                - values that are on the stack (outputs from first word) may not be adjusted. (they cannot lose DDOFs because otherwise they would no longer be able to match the input.
                - values that are popped from the stack (inputs from second word) may be adjusted to the value on the stack.
    ");

    println!();
}

fn alignment() {
    println!();
    let a = Element::ellipsis("a");
    let b = Element::ellipsis("b");
    let x = Element::item("x");
    let y = Element::item("y");

    //   (..b -- ..b y))
    // (..a x -- ..a x x))
    let mut first = se!(b -- b y);
    let mut secnd = se!(a x -- a x x);

    println!("{:?}", first);
    println!("{:?}", secnd);

    first.align(&mut secnd, true, false).unwrap_err();
    println!("DDOF lost");

    println!();
}

fn main() {
    assert!(ExtNum::finite(usize::max_value()) < ExtNum::Inf);
    assert!(ExtNum::finite(0) < ExtNum::finite(usize::max_value()));
    assert_ne!(ExtNum::<i32>::Inf, ExtNum::Inf);

    reduction();
    alignment();
    simple_chaining();
    advanced_chaining();
    expert_chaining();
    invalid_chaining();
    super_chaining();
}