prune_lang/sched/
path.rs

1use std::ops::Deref;
2use std::rc::Rc;
3
4use radix_trie::Trie;
5
6use super::*;
7
8#[derive(Clone, Debug)]
9pub struct Path {
10    pub pred: Ident,
11    pub idx: usize,
12    pub ctx: usize,
13    link: PathLink,
14}
15
16impl Path {
17    pub fn new(pred: Ident) -> Path {
18        Path {
19            pred,
20            idx: 0,
21            ctx: 0,
22            link: PathLink::new(pred),
23        }
24    }
25
26    pub fn jump(&self, idx: usize) -> Path {
27        let mut res = self.clone();
28        res.idx = idx;
29        res.link = res.link.link(self.pred, idx);
30        res
31    }
32
33    pub fn call(&self, pred: Ident, ctx: usize) -> Path {
34        let mut res = self.clone();
35        res.pred = pred;
36        res.idx = 0;
37        res.ctx = ctx;
38        res.link = res.link.link(pred, 0);
39        res
40    }
41}
42
43#[derive(Clone, Debug)]
44enum PathLinkData {
45    Nil,
46    Cons {
47        link: Rc<PathLinkData>,
48        pred: Ident,
49        idx: usize,
50    },
51}
52
53#[derive(Clone, Debug)]
54struct PathLink(Rc<PathLinkData>);
55
56impl PathLink {
57    fn new(pred: Ident) -> PathLink {
58        PathLink(Rc::new(PathLinkData::Cons {
59            link: Rc::new(PathLinkData::Nil),
60            pred,
61            idx: 0,
62        }))
63    }
64
65    fn link(&self, pred: Ident, idx: usize) -> PathLink {
66        PathLink(Rc::new(PathLinkData::Cons {
67            link: Rc::new(PathLinkData::Nil),
68            pred,
69            idx,
70        }))
71    }
72
73    fn to_usize_vec(&self) -> Vec<usize> {
74        let mut vec: Vec<usize> = Vec::new();
75        let mut path = self.0.clone();
76
77        while let PathLinkData::Cons { link, pred, idx } = path.deref() {
78            vec.push(*idx);
79            vec.push(pred.index);
80            path = link.clone();
81        }
82
83        vec.reverse();
84        vec
85    }
86}
87
88#[derive(Debug, Clone)]
89struct PathInfo {
90    counter: usize,
91    vsids_score: isize,
92    vsids_tmsp: usize,
93}
94
95const ALPHA: f32 = 0.95;
96
97impl PathInfo {
98    fn new(tmsp: usize) -> PathInfo {
99        PathInfo {
100            counter: 0,
101            vsids_score: 0,
102            vsids_tmsp: tmsp,
103        }
104    }
105
106    fn bump_score(&mut self, tmsp: usize, inc: isize) {
107        self.decay_update(tmsp);
108        self.vsids_score += inc;
109    }
110
111    fn decay_update(&mut self, tmsp: usize) {
112        let powered = ALPHA.powi((tmsp - self.vsids_tmsp) as i32);
113        self.vsids_score = ((self.vsids_score as f32) * powered) as isize;
114        self.vsids_tmsp = tmsp;
115    }
116}
117
118#[derive(Debug, Clone)]
119pub struct PathTree {
120    time_stamp: usize,
121    map: Trie<Vec<usize>, PathInfo>,
122}
123
124impl Default for PathTree {
125    fn default() -> Self {
126        Self::new()
127    }
128}
129
130impl PathTree {
131    pub fn new() -> PathTree {
132        PathTree {
133            time_stamp: 0,
134            map: Trie::new(),
135        }
136    }
137
138    pub fn conflict_update(&mut self, path: &Path) {
139        let mut vec = path.link.to_usize_vec();
140        assert_eq!(vec.len() % 2, 0);
141
142        let mut new_counter = 4;
143
144        while !vec.is_empty() {
145            let info = if let Some(info) = self.map.get_mut(&vec) {
146                info
147            } else {
148                let info = PathInfo::new(self.time_stamp);
149                self.map.insert(vec.clone(), info);
150                self.map.get_mut(&vec).unwrap()
151            };
152
153            info.counter = std::cmp::max(info.counter, new_counter);
154            info.bump_score(self.time_stamp, new_counter as isize * 100);
155
156            vec.pop().unwrap();
157            vec.pop().unwrap();
158
159            if new_counter == 1 {
160                break;
161            } else {
162                new_counter /= 2;
163            }
164        }
165    }
166
167    pub fn branch_update(&mut self, path: &Path) {
168        let vec = path.link.to_usize_vec();
169        assert_eq!(vec.len() % 2, 0);
170
171        let info = if let Some(info) = self.map.get_mut(&vec) {
172            info
173        } else {
174            let info = PathInfo::new(self.time_stamp);
175            self.map.insert(vec.clone(), info);
176            self.map.get_mut(&vec).unwrap()
177        };
178
179        info.counter = info.counter.saturating_sub(1);
180        info.bump_score(self.time_stamp, -200);
181
182        self.time_stamp += 1;
183    }
184
185    pub fn get_counter(&self, path: &Path) -> isize {
186        self.map
187            .get(&path.link.to_usize_vec())
188            .map(|info| info.counter)
189            .unwrap_or(0) as isize
190    }
191
192    pub fn get_mixed_vsids_score(&mut self, path: &Path) -> isize {
193        self.map
194            .get_mut(&path.link.to_usize_vec())
195            .map(|info| {
196                info.decay_update(self.time_stamp);
197                info.vsids_score
198            })
199            .unwrap_or(0)
200    }
201}
prune_lang/sched/path.rs

prune_lang/sched/
path.rs
