1 use collections::{Map, Multimap, Set};
2 use ena::unify::InPlaceUnificationTable;
3 use lr1::core::{Action, LR1State, StateIndex};
4 use lr1::lane_table::construct::state_set::StateSet;
5 use lr1::lane_table::table::context_set::ContextSet;
6 use lr1::lane_table::table::LaneTable;
7 
8 /// The "merge" phase of the algorithm is described in "Step 3c" of
9 /// [the README][r].  It consists of walking through the various
10 /// states in the lane table and merging them into sets of states that
11 /// have compatible context sets; if we encounter a state S that has a
12 /// successor T but where the context set of S is not compatible with
13 /// T, then we will clone T into a new T2 (and hopefully the context
14 /// set of S will be compatible with the reduced context of T2).
15 ///
16 /// [r]: ../README.md
17 pub struct Merge<'m, 'grammar: 'm> {
18     table: &'m LaneTable<'grammar>,
19     states: &'m mut Vec<LR1State<'grammar>>,
20     visited: Set<StateIndex>,
21     original_indices: Map<StateIndex, StateIndex>,
22     clones: Multimap<StateIndex, Vec<StateIndex>>,
23     target_states: Vec<StateIndex>,
24     context_sets: ContextSets<'m>,
25 }
26 
27 impl<'m, 'grammar> Merge<'m, 'grammar> {
new( table: &'m LaneTable<'grammar>, unify: &'m mut InPlaceUnificationTable<StateSet>, states: &'m mut Vec<LR1State<'grammar>>, state_sets: &'m mut Map<StateIndex, StateSet>, inconsistent_state: StateIndex, ) -> Self28     pub fn new(
29         table: &'m LaneTable<'grammar>,
30         unify: &'m mut InPlaceUnificationTable<StateSet>,
31         states: &'m mut Vec<LR1State<'grammar>>,
32         state_sets: &'m mut Map<StateIndex, StateSet>,
33         inconsistent_state: StateIndex,
34     ) -> Self {
35         Merge {
36             table,
37             states,
38             visited: Set::new(),
39             original_indices: Map::new(),
40             clones: Multimap::new(),
41             target_states: vec![inconsistent_state],
42             context_sets: ContextSets { unify, state_sets },
43         }
44     }
45 
start(&mut self, beachhead_state: StateIndex) -> Result<(), (StateIndex, StateIndex)>46     pub fn start(&mut self, beachhead_state: StateIndex) -> Result<(), (StateIndex, StateIndex)> {
47         debug!("Merge::start(beachhead_state={:?})", beachhead_state);
48 
49         // Since we always start walks from beachhead states, and they
50         // are not reachable from anyone else, this state should not
51         // have been unioned with anything else yet.
52         self.walk(beachhead_state)
53     }
54 
patch_target_starts(mut self, actions: &Set<Action<'grammar>>)55     pub fn patch_target_starts(mut self, actions: &Set<Action<'grammar>>) {
56         debug!("Merge::patch_target_starts(actions={:?})", actions);
57 
58         for &target_state in &self.target_states {
59             debug!(
60                 "Merge::patch_target_starts: target_state={:?}",
61                 target_state
62             );
63             let context_set = self.context_sets.context_set(target_state);
64             debug!("Merge::patch_target_starts: context_set={:?}", context_set);
65             context_set.apply(&mut self.states[target_state.0], actions);
66         }
67     }
68 
69     /// If `state` is a cloned state, find its original index.  Useful
70     /// for indexing into the lane table and so forth.
original_index(&self, state: StateIndex) -> StateIndex71     fn original_index(&self, state: StateIndex) -> StateIndex {
72         *self.original_indices.get(&state).unwrap_or(&state)
73     }
74 
successors(&self, state: StateIndex) -> Option<&'m Set<StateIndex>>75     fn successors(&self, state: StateIndex) -> Option<&'m Set<StateIndex>> {
76         self.table.successors(self.original_index(state))
77     }
78 
walk(&mut self, state: StateIndex) -> Result<(), (StateIndex, StateIndex)>79     fn walk(&mut self, state: StateIndex) -> Result<(), (StateIndex, StateIndex)> {
80         debug!("Merge::walk(state={:?})", state);
81 
82         if !self.visited.insert(state) {
83             debug!("Merge::walk: visited already");
84             return Ok(());
85         }
86 
87         for &successor in self.successors(state).iter().flat_map(|&s| s) {
88             debug!("Merge::walk: state={:?} successor={:?}", state, successor);
89 
90             if self.context_sets.union(state, successor) {
91                 debug!(
92                     "Merge::walk: successful union, context-set = {:?}",
93                     self.context_sets.context_set(state)
94                 );
95                 self.walk(successor)?;
96             } else {
97                 // search for an existing clone with which we can merge
98                 debug!("Merge::walk: union failed, seek existing clone");
99                 let existing_clone = {
100                     let context_sets = &mut self.context_sets;
101                     self.clones
102                         .get(&successor)
103                         .into_iter()
104                         .flat_map(|clones| clones) // get() returns an Option<Set>
105                         .cloned()
106                         .find(|&successor1| context_sets.union(state, successor1))
107                 };
108 
109                 if let Some(successor1) = existing_clone {
110                     debug!("Merge::walk: found existing clone {:?}", successor1);
111                     self.patch_links(state, successor, successor1);
112                     self.walk(successor1)?;
113                 } else {
114                     // if we don't find one, we have to make a new clone
115                     debug!("Merge::walk: creating new clone of {:?}", successor);
116                     let successor1 = self.clone(successor);
117                     if self.context_sets.union(state, successor1) {
118                         self.patch_links(state, successor, successor1);
119                         self.walk(successor1)?;
120                     } else {
121                         debug!(
122                             "Merge::walk: failed to union {:?} with {:?}",
123                             state, successor1
124                         );
125                         debug!(
126                             "Merge::walk: state context = {:?}",
127                             self.context_sets.context_set(state)
128                         );
129                         debug!(
130                             "Merge::walk: successor context = {:?}",
131                             self.context_sets.context_set(successor1)
132                         );
133 
134                         return Err((self.original_index(state), self.original_index(successor1)));
135                     }
136                 }
137             }
138         }
139 
140         Ok(())
141     }
142 
clone(&mut self, state: StateIndex) -> StateIndex143     fn clone(&mut self, state: StateIndex) -> StateIndex {
144         // create a new state with same contents as the old one
145         let new_index = StateIndex(self.states.len());
146         let new_state = self.states[state.0].clone();
147         self.states.push(new_state);
148 
149         // track the original index and clones
150         let original_index = self.original_index(state);
151         self.original_indices.insert(new_index, original_index);
152         self.clones.push(original_index, new_index);
153 
154         // create a new unify key for this new state
155         let context_set = self.table.context_set(original_index).unwrap();
156         self.context_sets.new_state(new_index, context_set);
157 
158         // keep track of the clones of the target state
159         if original_index == self.target_states[0] {
160             self.target_states.push(new_index);
161         }
162 
163         debug!("Merge::clone: cloned {:?} to {:?}", state, new_index);
164         new_index
165     }
166 
patch_links( &mut self, predecessor: StateIndex, original_successor: StateIndex, cloned_successor: StateIndex, )167     fn patch_links(
168         &mut self,
169         predecessor: StateIndex,
170         original_successor: StateIndex,
171         cloned_successor: StateIndex,
172     ) {
173         let replace = |target_state: &mut StateIndex| {
174             if *target_state == original_successor {
175                 *target_state = cloned_successor;
176             }
177         };
178 
179         let state = &mut self.states[predecessor.0];
180         for target_state in state.shifts.values_mut() {
181             replace(target_state);
182         }
183         for target_state in state.gotos.values_mut() {
184             replace(target_state);
185         }
186     }
187 }
188 
189 struct ContextSets<'m> {
190     state_sets: &'m mut Map<StateIndex, StateSet>,
191     unify: &'m mut InPlaceUnificationTable<StateSet>,
192 }
193 
194 impl<'m> ContextSets<'m> {
context_set(&mut self, state: StateIndex) -> ContextSet195     fn context_set(&mut self, state: StateIndex) -> ContextSet {
196         let state_set = self.state_sets[&state];
197         self.unify.probe_value(state_set)
198     }
199 
union(&mut self, source: StateIndex, target: StateIndex) -> bool200     fn union(&mut self, source: StateIndex, target: StateIndex) -> bool {
201         let set1 = self.state_sets[&source];
202         let set2 = self.state_sets[&target];
203         let result = self.unify.unify_var_var(set1, set2).is_ok();
204         debug!(
205             "ContextSets::union: source={:?} target={:?} result={:?}",
206             source, target, result
207         );
208         result
209     }
210 
new_state(&mut self, new_index: StateIndex, context_set: ContextSet)211     fn new_state(&mut self, new_index: StateIndex, context_set: ContextSet) {
212         let state_set = self.unify.new_key(context_set);
213         self.state_sets.insert(new_index, state_set);
214     }
215 }
216