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