prune_lang/interp/
strategy.rs

1use itertools::Itertools;
2
3use super::*;
4use std::fmt;
5
6#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
7struct PathNode {
8    rule_idx: usize,
9    call_idx: usize,
10}
11
12#[derive(Clone, Debug, PartialEq, Eq)]
13pub struct Path(Vec<PathNode>);
14
15impl Path {
16    pub fn new() -> Path {
17        Path(Vec::new())
18    }
19
20    pub fn clear(&mut self) {
21        self.0.clear();
22    }
23
24    pub fn push(&mut self, rule_idx: usize, call_idx: usize) {
25        self.0.push(PathNode { rule_idx, call_idx });
26    }
27}
28
29impl PartialOrd for Path {
30    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
31        match self.0.len().cmp(&other.0.len()) {
32            std::cmp::Ordering::Less => {
33                for (node1, node2) in self.0.iter().zip(other.0.iter()) {
34                    if node1 != node2 {
35                        return None;
36                    }
37                }
38                Some(std::cmp::Ordering::Less)
39            }
40            std::cmp::Ordering::Equal => {
41                if self.0 == other.0 {
42                    Some(std::cmp::Ordering::Equal)
43                } else {
44                    None
45                }
46            }
47            std::cmp::Ordering::Greater => {
48                for (node1, node2) in self.0.iter().zip(other.0.iter()) {
49                    if node1 != node2 {
50                        return None;
51                    }
52                }
53                Some(std::cmp::Ordering::Greater)
54            }
55        }
56    }
57}
58
59impl std::fmt::Display for Path {
60    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61        let nodes = self.0.iter().format_with(", ", |node, f| {
62            f(&format_args!("({}, {})", node.rule_idx, node.call_idx))
63        });
64        write!(f, "[{}]", nodes)
65    }
66}
67
68#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
69struct HistoryNode {
70    pred: Ident,
71    args_size: Vec<usize>,
72}
73
74#[derive(Clone, Debug, PartialEq)]
75pub struct History(Vec<HistoryNode>);
76
77impl History {
78    pub fn new() -> History {
79        History(Vec::new())
80    }
81
82    pub fn clear(&mut self) {
83        self.0.clear();
84    }
85
86    pub fn push(&mut self, pred: Ident, args_size: Vec<usize>) {
87        self.0.push(HistoryNode { pred, args_size });
88    }
89
90    pub fn left_biased_strategy_pred(&self) -> bool {
91        true
92    }
93
94    pub fn naive_strategy_pred(&self, n: usize) -> bool {
95        self.0.len() < n
96    }
97
98    pub fn struct_recur_strategy_pred(&self, pred: Ident, args: &[TermVal<IdentCtx>]) -> bool {
99        let args_size: Vec<usize> = args.iter().map(|arg| arg.height()).collect();
100
101        for node in self.0.iter() {
102            if node.pred == pred
103                && node
104                    .args_size
105                    .iter()
106                    .zip(args_size.iter())
107                    .all(|(arg0, arg)| arg0 <= arg)
108            {
109                return false;
110            }
111        }
112
113        true
114    }
115}
116
117#[derive(Clone, Debug)]
118pub struct CallInfo {
119    // these two vector should have the same length, they are seperated for convenience.
120    pub history: History,
121    pub path: Path,
122}
123
124impl CallInfo {
125    pub fn new() -> CallInfo {
126        CallInfo {
127            history: History::new(),
128            path: Path::new(),
129        }
130    }
131}
132
133pub struct ConflitCache {
134    max_size: usize,
135    cache: Vec<Path>,
136    cursor: usize,
137}
138
139impl ConflitCache {
140    pub fn new(max_size: usize) -> ConflitCache {
141        ConflitCache {
142            max_size,
143            cache: std::iter::repeat_n(Path::new(), max_size).collect(),
144            cursor: 0,
145        }
146    }
147
148    pub fn lookup(&self, path: &Path) -> bool {
149        // println!("check: {}", path);
150        // for path in self.cache.iter() {
151        //     println!("{}", path);
152        // }
153        self.cache.iter().any(|path2| path <= path2)
154    }
155
156    pub fn update(&mut self, path: &Path) {
157        if !self.lookup(path) {
158            self.cache[self.cursor] = path.clone();
159            self.cursor = (self.cursor + 1) % self.max_size;
160        }
161    }
162}
163
164impl Default for CallInfo {
165    fn default() -> Self {
166        Self::new()
167    }
168}
169
170impl Default for History {
171    fn default() -> Self {
172        Self::new()
173    }
174}
175
176impl Default for Path {
177    fn default() -> Self {
178        Self::new()
179    }
180}
prune_lang/interp/strategy.rs

prune_lang/interp/
strategy.rs
