diff --git a/src/collections/sets.rs b/src/collections/sets.rs index bdcf09861f8de3d733e72e0c6022236111c5916e..8f36093cb95fd90b450665ad0c501aff96abd1aa 100644 --- a/src/collections/sets.rs +++ b/src/collections/sets.rs @@ -97,4 +97,9 @@ impl VecSet { pub fn is_empty(&self) -> bool { self.inner.is_empty() } + + #[inline] + pub fn into_vec(self) -> Vec { + return self.inner; + } } \ No newline at end of file diff --git a/src/runtime2/consensus.rs b/src/runtime2/consensus.rs index 414eb41e010fd994845247ae6e8ce0fdeaee387a..6874153ced9b2acecb22a54535cbe6f60b427c0d 100644 --- a/src/runtime2/consensus.rs +++ b/src/runtime2/consensus.rs @@ -388,7 +388,7 @@ impl Consensus { debug_assert_ne!(self.highest_connector_id, ctx.id); if !self.local_solutions.is_empty() { - for local_solution in self.local_solutions.drain() { + for local_solution in self.local_solutions.drain(..) { let message = SyncMessageFancy{ sync_header: self.create_sync_header(ctx), target_component_id: self.highest_connector_id, @@ -413,13 +413,20 @@ struct MatchedLocalSolution { struct ComponentMatches { target_id: ConnectorId, target_index: usize, - match_indices: Vec, + match_indices: Vec, // of local solution in connector +} + +struct ComponentPeer { + target_id: ConnectorId, + target_index: usize, // in array of global solution components involved_ports: Vec, } struct ComponentLocalSolutions { component: ConnectorId, + peers: Vec, solutions: Vec, + all_peers_present: bool, } // TODO: Flatten? Flatten. Flatten everything. @@ -434,6 +441,9 @@ impl GlobalSolution { }; } + /// Adds a new local solution to the global solution storage. Will check the + /// new local solutions for matching against already stored local solutions + /// of peer connectors. fn add_solution(&mut self, solution: LocalSolution) { let component_id = solution.component; let solution = MatchedLocalSolution{ @@ -446,27 +456,203 @@ impl GlobalSolution { let component_exists = self.local.iter_mut() .enumerate() .find(|(_, v)| v.component == component_id); - let (component_index, solution_index) = match component_exists { + let (component_index, solution_index, new_component) = match component_exists { Some((component_index, storage)) => { // Entry for component exists, so add to solutions let solution_index = storage.solutions.len(); storage.solutions.push(solution); - (component_index, solution_index) + (component_index, solution_index, false) } None => { // Entry for component does not exist yet let component_index = self.local.len(); self.local.push(ComponentLocalSolutions{ component: component_id, + peers: Vec::new(), solutions: vec![solution], + all_peers_present: false, }); - (component_index, 0) + (component_index, 0, true) } }; - // Compare this new solution to other solutions of different components - // to see if we get a closed global solution. + // If this is a solution of a component that is new to us, then we check + // in the stored solutions which other components are peers of the new + // one. + if new_component { + let cur_ports = &self.local[component_index].solutions[0].port_mapping; + let mut component_peers = Vec::new(); + + // Find the matching components + for (other_index, other_component) in self.local.iter().enumerate() { + if other_index == component_index { + // Don't match against ourselves + continue; + } + + let mut matching_ports = Vec::new(); + for (cur_port_id, _) in cur_ports { + for (other_port_id, _) in &other_component.solutions[0].port_mapping { + if cur_port_id == other_port_id { + // We have a shared port + matching_ports.push(*port_id); + } + } + } + + if !matching_ports.is_empty() { + // We share some ports + component_peers.push(ComponentPeer{ + target_id: other_component.component, + target_index: other_index, + involved_ports: matching_ports, + }); + } + } + + let mut num_ports_in_peers = 0; + for peer in component_peers { + num_ports_in_peers += peer.involved_ports.len(); + } + + if num_ports_in_peers == cur_ports.len() { + // Newly added component has all required peers present + self.local[component_index].all_peers_present = true; + } + + // Add the found component pairing entries to the solution entries + // for the two involved components + for component_match in component_peers { + // Check the other component for having all peers present + let mut num_ports_in_peers = component_match.involved_ports.len(); + let other_component = &mut self.local[component_match.target_index]; + for existing_peer in &other_component.peers { + num_ports_in_peers += existing_peer.involved_ports.len(); + } + + if num_ports_in_peers == other_component.solutions[0].port_mapping.len() { + other_component.all_peers_present = true; + } + + other_component.peers.push(ComponentPeer{ + target_id: component_id, + target_index: component_index, + involved_ports: component_match.involved_ports.clone(), + }); + + let new_component = &mut self.local[component_index]; + new_component.peers.push(component_match); + } + } + + // We're now sure that we know which other components the currently + // considered component is linked up to. Now we need to check those + // entries (if any) to see if any pair of local solutions match + let mut new_component_matches = Vec::new(); + let cur_component = &self.local[component_index]; + let cur_solution = &cur_component.solutions[solution_index]; + + for peer in &cur_component.peers { + let mut new_solution_matches = Vec::new(); + + let other_component = &self.local[peer.target_index]; + for (other_solution_index, other_solution) in other_component.solutions.iter().enumerate() { + // Check the port mappings between the pair of solutions. + let mut all_matched = true; + + 'mapping_check_loop: for (cur_port, cur_branch) in &cur_solution.port_mapping { + for (other_port, other_branch) in &other_solution.port_mapping { + if cur_port == other_port { + if cur_branch == other_branch { + // Same port mapping, go to next port + break; + } else { + // Different port mapping, not a match + all_matched = false; + break 'mapping_check_loop; + } + } + } + } + + if !all_matched { + continue; + } + + // Port mapping between the component pair is the same, so they + // have agreeable local solutions + new_solution_matches.push(other_solution_index); + } + + new_component_matches.push(ComponentMatches{ + target_id: peer.target_id, + target_index: peer.target_index, + match_indices: new_solution_matches, + }); + } + + // And now that we have the new solution-to-solution matches, we need to + // add those in the appropriate storage. + for new_component_match in new_component_matches { + let other_component = &mut self.local[new_component_match.target_index]; + + for other_solution_index in new_component_match.match_indices.iter().copied() { + let other_solution = &mut other_component.solutions[other_solution_index]; + + // Add a completely new entry for the component, or add it to + // the existing component entry's matches + match other_solution.matches.iter_mut() + .find(|v| v.target_id == component_id) + { + Some(other_match) => { + other_match.match_indices.push(solution_index); + }, + None => { + other_solution.matches.push(ComponentMatches{ + target_id: component_id, + target_index: component_index, + match_indices: vec![solution_index], + }) + } + } + } + + let cur_component = &mut self.local[component_index]; + let cur_solution = &mut cur_component.solutions[solution_index]; + + match cur_solution.matches.iter_mut() + .find(|v| v.target_id == new_component_match.target_id) + { + Some(other_match) => { + // Already have an entry + debug_assert_eq!(other_match.target_index, new_component_match.target_index); + other_match.match_indices.extend(&new_component_match.match_indices); + }, + None => { + // Create a new entry + cur_solution.matches.push(new_component_match); + } + } + } + } + + /// Checks if, starting at the provided local solution, a global solution + /// can be formed. + fn check_new_solution(&self, component_idx: usize, solution_index: usize) -> Option> { + + } + + /// Simple test if a solution is at all possible. If this returns true it + /// does not mean there actually is a solution. + fn can_have_solution(&self) -> bool { + for component in &self.local { + if !component.all_peers_present { + return false; + } + } + + return true; } }