Skip to content

Instantly share code, notes, and snippets.

@rexim
Created November 21, 2021 18:58
Show Gist options
  • Save rexim/44393b151b1bdf7b68f092a61efaf7c1 to your computer and use it in GitHub Desktop.
Save rexim/44393b151b1bdf7b68f092a61efaf7c1 to your computer and use it in GitHub Desktop.
use std::io;
use std::io::Write;
use std::fs::File;
use std::process::Command;
#[derive(Debug, Clone, Copy)]
enum DataType {
Int,
Ptr,
Bool,
}
struct Frame {
data_type: DataType,
previous: Option<usize>,
}
type FrameIndex = usize;
#[derive(Default)]
struct FrameAtor {
frames: Vec<(Frame, usize)>,
free: Vec<FrameIndex>,
}
impl FrameAtor {
fn alloc(&mut self, init: Frame) -> FrameIndex {
if let Some(result) = self.free.pop() {
self.frames[result] = (init, 1);
result
} else {
let result = self.frames.len();
self.frames.push((init, 1));
result
}
}
fn acquire(&mut self, index: usize) {
self.frames[index].1 += 1
}
fn release(&mut self, index: usize) {
self.frames[index].1 -= 1;
if self.frames[index].1 == 0 {
if let Some(prev_index) = self.frames[index].0.previous {
self.release(prev_index)
}
self.free.push(index);
}
}
#[allow(dead_code)]
fn deref(&self, index: FrameIndex) -> Option<&Frame> {
self.frames.get(index).map(|x| &x.0)
}
fn deref_mut(&mut self, index: FrameIndex) -> Option<&mut Frame> {
self.frames.get_mut(index).map(|x| &mut x.0)
}
fn dump_dot(&self, sink: &mut impl Write) -> io::Result<()> {
writeln!(sink, "digraph Stacks {{")?;
for (index, (frame, ref_count)) in self.frames.iter().enumerate() {
if !self.free.contains(&index) {
writeln!(sink, " Node_{} [label=\"{:?} ({})\"]", index, frame.data_type, ref_count)?;
if let Some(prev_index) = frame.previous {
writeln!(sink, " Node_{} -> Node_{}", index, prev_index)?;
}
}
}
writeln!(sink, "}}")?;
Ok(())
}
}
#[derive(Default)]
struct TypeStack {
top: Option<FrameIndex>
}
impl TypeStack {
fn clone(&mut self, ator: &mut FrameAtor) -> Self {
if let Some(top_index) = self.top {
ator.acquire(top_index)
}
Self {top: self.top}
}
fn push(&mut self, ator: &mut FrameAtor, data_type: DataType) {
self.top = Some(ator.alloc(Frame{
data_type,
previous: self.top,
}))
}
fn pop(&mut self, ator: &mut FrameAtor) {
if let Some(top_index) = self.top {
let prev = ator.deref_mut(top_index).unwrap().previous;
if let Some(prev_index) = prev {
ator.acquire(prev_index)
}
ator.release(top_index);
self.top = prev;
}
}
fn dump(&self, ator: &FrameAtor) {
let mut top = self.top;
while let Some(index) = top {
let frame = ator.deref(index).unwrap();
println!("[{:?}]", frame.data_type);
top = frame.previous;
}
}
}
const RAND_A: u64 = 6364136223846793005;
const RAND_C: u64 = 1442695040888963407;
struct Rand {
seed: u64
}
impl Rand {
fn rand(&mut self) -> u32 {
self.seed = RAND_A.wrapping_mul(self.seed).wrapping_add(RAND_C);
(self.seed >> 32) as u32
}
}
fn rand_type(rand: &mut Rand) -> DataType {
match rand.rand() % 3 {
0 => DataType::Int,
1 => DataType::Ptr,
2 => DataType::Bool,
_ => unreachable!(),
}
}
fn generate_tree(rand: &mut Rand, ator: &mut FrameAtor, stack: &mut TypeStack, level: usize) {
if level == 0 {
return;
}
for _ in 0..3 {
stack.push(ator, rand_type(rand));
}
let mut stack0 = stack.clone(ator);
let mut stack1 = stack.clone(ator);
generate_tree(rand, ator, stack, level - 1);
generate_tree(rand, ator, &mut stack0, level - 1);
generate_tree(rand, ator, &mut stack1, level - 1);
}
fn main() {
let mut rand = Rand{seed:69};
let mut ator = FrameAtor::default();
let mut stack = TypeStack::default();
generate_tree(&mut rand, &mut ator, &mut stack, 4);
let output_filepath = "output.dot";
println!("[INFO] Generating {}", output_filepath);
ator.dump_dot(&mut File::create(output_filepath).unwrap()).unwrap();
Command::new("dot")
.args(["-Tsvg", "-O", output_filepath])
.output()
.expect("dot command should've executed successfully");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment