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
110
111
112

use crate::{AddGraph, CacheTrace, Ident, Node, COUNT};

#[derive(Default, Debug)]
pub struct Graph {
    pub nodes: Vec<Node>,
}

impl Graph {
    pub fn new() -> Self {
        Self { nodes: Vec::new() }
    }

    pub fn add(&mut self, len: usize, add_node: impl AddGraph) -> Node {
        add_node.add(self, len)
    }

    pub fn add_leaf(&mut self, len: usize) -> Node {
        Node {
            idx: -1,
            ident_idx: -1,
            deps: [-1, -1],
            len,
        }
    }

    pub fn add_node(&mut self, len: usize, lhs_idx: isize, rhs_idx: isize) -> Node {
        let idx = self.nodes.len() as isize;
        let node = COUNT.with(|count| {
            Node {
                // subtracting 1, because the count is increased beforehand.
                ident_idx: count.get() as isize,
                idx,
                deps: [lhs_idx, rhs_idx],
                len,
            }
        });
        self.nodes.push(node);
        node
    }

    pub fn cache_traces(&self) -> Vec<CacheTrace> {
        if self.nodes.is_empty() {
            return Vec::new();
        }

        let mut start = self.nodes[0];
        let mut traces = vec![];

        while let Some(trace) = self.trace_cache_path(&start) {
            let last_trace_node = *trace.last().unwrap();

            traces.push(CacheTrace {
                cache_idx: start.idx as usize,
                use_cache_idx: trace
                    .into_iter()
                    .map(|node| Ident {
                        idx: node.ident_idx as usize,
                        len: node.len,
                    })
                    .collect(),
            });

            // use better searching algorithm to find the next start node
            match self.nodes.get(last_trace_node.idx as usize + 1) {
                Some(next) => start = *next,
                None => return traces,
            }
        }
        traces
    }

    pub fn trace_cache_path(&self, trace_at: &Node) -> Option<Vec<Node>> {
        if !self.is_path_optimizable(trace_at) {
            return None;
        }

        let mut trace = vec![*trace_at];

        let mut idx = trace_at.idx;
        for check in &self.nodes[trace_at.idx as usize + 1..] {
            if trace_at.len != check.len || !self.is_path_optimizable(check) {
                continue;
            }

            if check.deps.contains(&idx) {
                idx = check.idx;
                trace.push(*check);
            }
        }
        Some(trace)
    }

    pub fn is_path_optimizable(&self, check_at: &Node) -> bool {
        if check_at.is_leaf() {
            return false;
        };

        let mut occurences = 0;

        for check in &self.nodes[check_at.idx as usize + 1..] {
            if check_at.len != check.len || !check.deps.contains(&check_at.idx) {
                continue;
            }

            if occurences >= 1 {
                return false;
            }
            occurences += 1;
        }
        true
    }
}