nilang 0.4.1

A scripting language interpreter for Advent of Code
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

use super::super::block::{Block, BlockId};
use super::super::func::Func;
use alloc::collections::BTreeMap;

pub trait DFA: Sized {
    type Data;

    const BACKWARDS: bool = false;

    fn exec(&mut self, func: &Func) {
        let mut executor = DFAExecutor::<Self>::new(func);

        executor.init(self, func);
        executor.exec(self, func);

        self.complete(executor.inputs, executor.outputs);
    }
    fn init_block(&mut self, block: &Block, func: &Func) -> (Self::Data, Self::Data);
    fn complete(
        &mut self,
        _inputs: BTreeMap<BlockId, Self::Data>,
        _outputs: BTreeMap<BlockId, Self::Data>,
    );
    fn merge(&mut self, updating: &mut Self::Data, merge: &Self::Data, count: usize);
    fn transfer(&mut self, block: &Block, start: &Self::Data, end: &mut Self::Data) -> bool;
}

struct DFAExecutor<T>
where
    T: DFA,
{
    inputs: BTreeMap<BlockId, <T as DFA>::Data>,
    outputs: BTreeMap<BlockId, <T as DFA>::Data>,
    work_list: Vec<BlockId>,
}

impl<T: DFA> DFAExecutor<T> {
    fn new(func: &Func) -> Self {
        Self {
            inputs: BTreeMap::new(),
            outputs: BTreeMap::new(),
            work_list: func.get_block_ids(),
        }
    }

    fn init(&mut self, dfa: &mut T, func: &Func) {
        for block in func.get_blocks().iter() {
            let (init_input, init_output) = dfa.init_block(block, func);

            self.inputs.insert(block.get_id(), init_input);
            self.outputs.insert(block.get_id(), init_output);
        }
    }

    fn exec(&mut self, dfa: &mut T, func: &Func) {
        while let Some(block_id) = self.work_list.pop() {
            let block = func.get_block(block_id);

            if T::BACKWARDS {
                self.propagate_backward(dfa, block)
            } else {
                panic!("there aren't any forward propagations supported yet")
                //self.propagate_forward(dfa, block)
            }
        }
    }

    fn propagate_backward(&mut self, dfa: &mut T, block: &Block) {
        let id = block.get_id();
        let output = self.outputs.get_mut(&id).unwrap();
        for (i, succ_id) in block.get_successors().iter().enumerate() {
            let succ_input = self.inputs.get(succ_id).unwrap();

            dfa.merge(output, succ_input, i);
        }

        let input = self.inputs.get_mut(&id).unwrap();
        let output = self.outputs.get(&id).unwrap();
        let update_flag = dfa.transfer(block, output, input);

        if update_flag {
            for pred_id in block.get_predecessors().iter() {
                self.work_list.push(*pred_id);
            }
        }
    }

    /*
    fn propagate_forward(&mut self, dfa: &mut T, block: &Block) {
        let id = block.get_id();
        let input = self.inputs.get_mut(&id).unwrap();
        for (i, pred_id) in block.get_predecessors().iter().enumerate() {
            let pred_output = self.outputs.get(pred_id).unwrap();

            dfa.merge(input, pred_output, i);
        }

        let output = self.outputs.get_mut(&id).unwrap();
        let input = self.inputs.get(&id).unwrap();
        let update_flag = dfa.transfer(block, input, output);

        if update_flag {
            for succ_id in block.get_successors().iter() {
                self.work_list.push(*succ_id);
            }
        }
    }
    */
}