/
statestack.rs
103 lines (88 loc) · 2.71 KB
/
statestack.rs
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
// Copyright 2017 The xi-editor Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
use std::hash::Hash;
use std::collections::HashMap;
/// An entire state stack is represented as a single integer.
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct State(usize);
impl State {
pub fn raw(self) -> usize {
self.0
}
}
struct Entry<T> {
tos: T,
prev: State,
}
pub trait NewState<T> {
fn new_state(&mut self, s: State, contents: &[T]);
}
/// All states are interpreted in a context.
pub struct Context<T, N> {
new_state: N,
// oddly enough, this is 1-based, as state 0 doesn't have an entry.
entries: Vec<Entry<T>>,
next: HashMap<(State, T), State>,
}
impl<T: Clone + Hash + Eq, N: NewState<T>> Context<T, N> {
pub fn new(new_state: N) -> Context<T, N> {
Context {
new_state: new_state,
entries: Vec::new(),
next: HashMap::new(),
}
}
pub fn get_new_state(&self) -> &N {
&self.new_state
}
fn entry(&self, s: State) -> Option<&Entry<T>> {
if s.0 == 0 {
None
} else {
Some(&self.entries[s.0 - 1])
}
}
/// The top of the stack for the given state.
pub fn tos(&self, s: State) -> Option<T> {
self.entry(s).map(|entry| entry.tos.clone())
}
pub fn pop(&self, s: State) -> Option<State> {
self.entry(s).map(|entry| entry.prev.clone())
}
pub fn push(&mut self, s: State, el: T) -> State {
let mut new = false;
let result = {
let entries = &mut self.entries;
self.next.entry((s, el.clone())).or_insert_with(|| {
new = true;
entries.push(Entry { tos: el, prev: s });
State(entries.len())
}).clone()
};
if new {
let contents = self.to_vec(result);
self.new_state.new_state(result, &contents)
}
result
}
pub fn to_vec(&self, mut s: State) -> Vec<T> {
let mut result = Vec::new();
while let Some(entry) = self.entry(s) {
result.push(entry.tos.clone());
s = entry.prev;
}
result.reverse();
result
}
}