libreda-logic 0.0.3

// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Transform majority-inverter-graph nodes based on their associativity property:
//! `M(x, u, M(y, u, z)) == M(z, u, M(y, u, x))`

use crate::{
    network::EdgeWithInversion,
    networks::mig::{Maj3Node, Mig},
};

impl Mig {
    /// Match the pattern `M(x, u, M(y, u, z))`.
    ///
    /// Associativity: `M(x, u, M(y, u, z)) == M(z, u, M(y, u, x))`
    ///
    /// Return `((index of u, [index of child node, index of u in child node]))` for each match.
    fn match_associativity(
        &self,
        node: Maj3Node,
    ) -> impl Iterator<Item = (usize, [usize; 2])> + '_ {
        self.match_associativity_maybe_complementary(node, false)
    }

    /// Match the pattern `M(x, u, M(y, u', z))`.
    ///
    /// Complementary associativity: `M(x, u, M(y, u', z)) == M(x, u, M(y, x, z))`
    ///
    /// Return `((index of u, [index of child node, index of u in child node]))` for each match.
    fn match_complementary_associativity(
        &self,
        node: Maj3Node,
    ) -> impl Iterator<Item = (usize, [usize; 2])> + '_ {
        self.match_associativity_maybe_complementary(node, true)
    }

    /// Match the pattern
    /// * `M(x, u, M(y, u, z))` if `complementary == false`
    /// * or `M(x, u, M(y, u', z))`if `complementary == true`
    ///
    /// Return `((index of u, [index of child node, index of u in child node]))` for each match.
    fn match_associativity_maybe_complementary(
        &self,
        node: Maj3Node,
        complementary: bool,
    ) -> impl Iterator<Item = (usize, [usize; 2])> + '_ {
        // Find a child node which shares an input with the given node.
        let node_inputs = node.to_array();

        // Get the child nodes and associate them with their position.
        let child_nodes_with_index = node_inputs
            .into_iter()
            .enumerate()
            // Skip constants and primary inputs.
            .filter_map(|(idx, nid)| self.get_node(nid).to_logic_node().map(|n| (idx, n)));

        // Find a child node which shares an input with the parent node.
        child_nodes_with_index.flat_map(move |(child_node_index, child_node)| {
            // Get the other inputs of the parent node.
            let other_inputs = remove3(node_inputs, child_node_index);
            // Optionally search for inverted signals.
            let other_inputs = other_inputs.map(|i| i.invert_if(complementary));

            let other_inputs_indices = other_indices3(child_node_index);

            child_node
                .into_iter()
                .enumerate()
                .flat_map(move |(input2_idx, input2)| {
                    other_inputs
                        .into_iter()
                        .zip(other_inputs_indices)
                        .filter(move |(input1, _input1_idx)| input1 == &input2)
                        .map(move |(input1, input1_idx)| {
                            let shared_input = input1;
                            (input1_idx, [child_node_index, input2_idx])
                        })
                })
        })
    }
}

#[test]
fn test_match_associativity() {
    use crate::network::*;

    let mut mig = Mig::new();

    let [x, y, z, u] = mig.create_primary_inputs();

    // Create M(u, y, z)
    let m_child = mig.create_maj3(u, y, z);
    // Create M(x, u, M(u, y, z))
    let m = mig.create_maj3(x, u, m_child);

    let m_node = *mig.get_node(m).to_logic_node().unwrap();
    let m_child_node = *mig.get_node(m_child).to_logic_node().unwrap();

    let matches: Vec<_> = mig.match_associativity(m_node).collect();

    assert_eq!(matches.len(), 1);

    let m_inputs = m_node.to_array();
    let m_child_inputs = m_child_node.to_array();

    let (shared_input1_idx, [child_node_idx, shared_input2_idx]) = matches[0];

    // Test that the shared input is correctly identified.
    assert_eq!(m_inputs[shared_input1_idx], u);
    // Test that child node `M(u, y, z)` is correctly detected.
    assert_eq!(m_inputs[child_node_idx], m_child);
    // Test that the shared input is correctly identified.
    assert_eq!(m_child_inputs[shared_input2_idx], u);
}

#[test]
fn test_match_complementary_associativity() {
    use crate::network::*;

    let mut mig = Mig::new();

    let [x, y, z, u] = mig.create_primary_inputs();

    // Create M(u, y, z)
    let m_child = mig.create_maj3(u, y, z);
    // Create M(x, u, M(u', y, z))
    let m = mig.create_maj3(x, u.invert(), m_child);

    let m_node = *mig.get_node(m).to_logic_node().unwrap();
    let m_child_node = *mig.get_node(m_child).to_logic_node().unwrap();

    let matches: Vec<_> = mig.match_complementary_associativity(m_node).collect();

    assert_eq!(matches.len(), 1);

    let m_inputs = m_node.to_array();
    let m_child_inputs = m_child_node.to_array();

    let (shared_input1_idx, [child_node_idx, shared_input2_idx]) = matches[0];

    // Test that the shared input is correctly identified.
    assert_eq!(m_inputs[shared_input1_idx].non_inverted(), u);
    // Test that child node `M(u, y, z)` is correctly detected.
    assert_eq!(m_inputs[child_node_idx], m_child);
    // Test that the shared input is correctly identified.
    assert_eq!(m_child_inputs[shared_input2_idx].non_inverted(), u);
    assert_eq!(
        m_child_inputs[shared_input2_idx].invert(),
        m_inputs[shared_input1_idx]
    );
}

/// Remove an element from an array of length 3.
fn remove3<T: Copy>(arr: [T; 3], remove_idx: usize) -> [T; 2] {
    let [a, b] = other_indices3(remove_idx);
    [arr[a], arr[b]]
}

#[test]
fn test_remove3() {
    assert_eq!(remove3([10, 20, 30], 0), [20, 30]);
    assert_eq!(remove3([10, 20, 30], 1), [10, 30]);
    assert_eq!(remove3([10, 20, 30], 2), [10, 20]);
}

/// Return the indices [0, 1, 2] with the given index removed.
fn other_indices3(remove_idx: usize) -> [usize; 2] {
    match remove_idx {
        0 => [1, 2],
        1 => [0, 2],
        2 => [0, 1],
        _ => panic!("index out of bounds"),
    }
}