defunctionalization

defunctionalization.rs

use std::{process::Output, usize};

use crate::st::Process;
fn main() {
  type T = Tree;
  let tree = T::branch(
    T::branch(T::Leaf, 1, T::Leaf),
    2,
    T::branch(T::branch(T::Leaf, 3, Tree::Leaf), 4, Tree::Leaf),
  );

  // println!("{:?}", tree.infix_flatten2());

  let mut process = st::infix_flatten2_init(&tree);

  loop {
    process = st::infix_flatten2_step(process);

    if let Process::Running((_, cont_stack)) = &process {
      if cont_stack.len() > 1 {
        break;
      }
    };
  }

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

  loop {
    process = st::infix_flatten2_step(process);

    if let Process::Done(d) = &process {
      println!("{:?}", d);
      break;
    }
  }
}

#[derive(Debug)]
enum Tree {
  Leaf,
  Branch(Box<(Tree, i32, Tree)>),
}

impl Tree {
  fn branch(left: Tree, value: i32, right: Tree) -> Tree {
    Tree::Branch(Box::new((left, value, right)))
  }

  fn infix_flatten(&self) -> Vec<i32> {
    match self {
      Tree::Leaf => Vec::new(),
      Tree::Branch(branch) => {
        let (l, v, r): &(_, _, _) = &branch;
        let mut left = Self::infix_flatten(l);

        let right = Self::infix_flatten(r);

        left.push(*v);
        left.extend(right);
        left
      }
    }
  }

  fn infix_flatten2(&self) -> Vec<i32> {
    enum State<'t> {
      Recurse(&'t Tree),
      Return(Vec<i32>),
    }
    enum Cont<'t> {
      LeftBranchDone(LeftBranchDone<'t>),
      RightBranchDone(RightBranchDone),
    }
    struct LeftBranchDone<'r> {
      value: i32,
      right: &'r Tree,
    }
    struct RightBranchDone {
      left: Vec<i32>,
      value: i32,
    }

    let mut state = State::Recurse(self);
    let mut cont_stack: Vec<Cont> = Vec::new();

    return 'exec: loop {
      state = match state {
        State::Return(ret) => {
          let Some(top) = cont_stack.pop() else {
            break 'exec ret;
          };
          match top {
            Cont::LeftBranchDone(LeftBranchDone { value, right }) => {
              cont_stack.extend([Cont::RightBranchDone(RightBranchDone { left: ret, value })]);
              State::Recurse(right)
            }
            Cont::RightBranchDone(RightBranchDone { mut left, value }) => {
              left.push(value);
              left.extend(ret);
              State::Return(left)
            }
          }
        }
        State::Recurse(Tree::Leaf) => State::Return(Vec::new()),
        State::Recurse(Tree::Branch(branch)) => {
          let (left, v, right): &(_, _, _) = &branch;
          let value = *v;
          cont_stack.push(Cont::LeftBranchDone(LeftBranchDone { value, right }));
          State::Recurse(left)
        }
      }
    };
  }
}

mod st {
  use super::Tree;
  #[derive(Debug)]
  pub enum State<'t> {
    Recurse(&'t Tree),
    Return(Vec<i32>),
  }
  #[derive(Debug)]
  pub enum Cont<'t> {
    LeftBranchDone(LeftBranchDone<'t>),
    RightBranchDone(RightBranchDone),
  }
  #[derive(Debug)]
  struct LeftBranchDone<'r> {
    value: i32,
    right: &'r Tree,
  }
  #[derive(Debug)]
  struct RightBranchDone {
    left: Vec<i32>,
    value: i32,
  }

  #[derive(Debug)]
  pub enum Process<'a> {
    Done(Vec<i32>),
    Running((State<'a>, Vec<Cont<'a>>)),
  }

  pub fn infix_flatten2_init(tree: &Tree) -> Process {
    Process::Running((State::Recurse(tree), Vec::new()))
  }

  pub fn infix_flatten2_step(process: Process) -> Process {
    let Process::Running((mut state, mut cont_stack)) = process else {
      return process;
    };

    state = match state {
      State::Return(ret) => {
        let Some(top) = cont_stack.pop() else {
          return Process::Done(ret);
        };
        match top {
          Cont::LeftBranchDone(LeftBranchDone { value, right }) => {
            cont_stack.extend([Cont::RightBranchDone(RightBranchDone { left: ret, value })]);
            State::Recurse(right)
          }
          Cont::RightBranchDone(RightBranchDone { mut left, value }) => {
            left.push(value);
            left.extend(ret);
            State::Return(left)
          }
        }
      }
      State::Recurse(Tree::Leaf) => State::Return(Vec::new()),
      State::Recurse(Tree::Branch(branch)) => {
        let (left, v, right): &(_, _, _) = &branch;
        let value = *v;
        cont_stack.push(Cont::LeftBranchDone(LeftBranchDone { value, right }));
        State::Recurse(left)
      }
    };
    Process::Running((state, cont_stack))
  }
}