Changeset - 54917d00dfe6
[Not reviewed]
0 2 0
MH - 4 years ago 2021-11-08 12:32:57
contact@maxhenger.nl
WIP on matching local solutions to find global solution
2 files changed with 198 insertions and 7 deletions:
0 comments (0 inline, 0 general)
src/collections/sets.rs
Show inline comments
 
@@ -97,4 +97,9 @@ impl<T: Eq> VecSet<T> {
 
    pub fn is_empty(&self) -> bool {
 
        self.inner.is_empty()
 
    }
 

	
 
    #[inline]
 
    pub fn into_vec(self) -> Vec<T> {
 
        return self.inner;
 
    }
 
}
 
\ No newline at end of file
src/runtime2/consensus.rs
Show inline comments
 
@@ -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<usize>,
 
    match_indices: Vec<usize>, // of local solution in connector
 
}
 

	
 
struct ComponentPeer {
 
    target_id: ConnectorId,
 
    target_index: usize, // in array of global solution components
 
    involved_ports: Vec<PortIdLocal>,
 
}
 

	
 
struct ComponentLocalSolutions {
 
    component: ConnectorId,
 
    peers: Vec<ComponentPeer>,
 
    solutions: Vec<MatchedLocalSolution>,
 
    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<Vec<(ConnectorId, BranchId)>> {
 
        
 
    }
 

	
 
    /// 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;
 
    }
 
}
 

	
0 comments (0 inline, 0 general)