graph.cpp

Go to the documentation of this file.

#include "./graph.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/stdlib_circuit_builders/ultra_circuit_builder.hpp"
#include <algorithm>
#include <array>
#include <stack>
 
using namespace bb::plookup;
using namespace bb;
 
namespace cdg {
 
template <typename FF>
size_t StaticAnalyzer_<FF>::find_block_index(UltraCircuitBuilder& ultra_builder, const UltraBlock& block)
{
    auto blocks_data = ultra_builder.blocks.get();
    size_t index = 0;
    for (size_t i = 0; i < blocks_data.size(); i++) {
        if ((void*)(&blocks_data[i]) == (void*)(&block)) {
            index = i;
            break;
        }
    }
    return index;
}
 
template <typename FF>
inline void StaticAnalyzer_<FF>::process_gate_variables(std::vector<uint32_t>& gate_variables,
                                                        size_t gate_index,
                                                        size_t block_idx)
{
    auto unique_variables = std::unique(gate_variables.begin(), gate_variables.end());
    gate_variables.erase(unique_variables, gate_variables.end());
    if (gate_variables.empty()) {
        return;
    }
    for (auto& var_idx : gate_variables) {
        KeyPair key = std::make_pair(var_idx, block_idx);
        variable_gates[key].emplace_back(gate_index);
    }
    for (const auto& variable_index : gate_variables) {
        variables_gate_counts[variable_index] += 1;
    }
}
 
template <typename FF>
inline std::vector<std::vector<uint32_t>> StaticAnalyzer_<FF>::get_arithmetic_gate_connected_component(
    bb::UltraCircuitBuilder& ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock& blk)
{
    auto q_arith = blk.q_arith()[index];
    std::vector<uint32_t> gate_variables;
    std::vector<uint32_t> minigate_variables;
    std::vector<std::vector<uint32_t>> all_gates_variables;
    if (q_arith.is_zero()) {
        return {};
    }
    auto q_m = blk.q_m()[index];
    auto q_1 = blk.q_1()[index];
    auto q_2 = blk.q_2()[index];
    auto q_3 = blk.q_3()[index];
    auto q_4 = blk.q_4()[index];
 
    uint32_t left_idx = blk.w_l()[index];
    uint32_t right_idx = blk.w_r()[index];
    uint32_t out_idx = blk.w_o()[index];
    uint32_t fourth_idx = blk.w_4()[index];
    if (q_m.is_zero() && q_1 == 1 && q_2.is_zero() && q_3.is_zero() && q_4.is_zero() && q_arith == FF::one()) {
        // this is fixed_witness gate. So, variable index contains in left wire. So, we have to take only it.
        fixed_variables.insert(this->to_real(ultra_circuit_builder, left_idx));
    } else if (!q_m.is_zero() || q_1 != FF::one() || !q_2.is_zero() || !q_3.is_zero() || !q_4.is_zero()) {
        //  this is not the gate for fix_witness, so we have to process this gate
        if (!q_m.is_zero()) {
            gate_variables.emplace_back(left_idx);
            gate_variables.emplace_back(right_idx);
        } else {
            if (!q_1.is_zero()) {
                gate_variables.emplace_back(left_idx);
            }
            if (!q_2.is_zero()) {
                gate_variables.emplace_back(right_idx);
            }
        }
 
        if (!q_3.is_zero()) {
            gate_variables.emplace_back(out_idx);
        }
        if (!q_4.is_zero()) {
            gate_variables.emplace_back(fourth_idx);
        }
        if (q_arith == FF(2)) {
            // We have to use w_4_shift from the next gate
            // if and only if the current gate isn't last, cause we can't
            // look into the next gate
            if (index != blk.size() - 1) {
                gate_variables.emplace_back(blk.w_4()[index + 1]);
            }
        }
        if (q_arith == FF(3)) {
            //  In this gate mini gate is enabled, we have 2 equations:
            //  q_1 * w_1 + q_2 * w_2 + q_3 * w_3 + q_4 * w_4 + q_c + 2 * w_4_omega = 0
            //  w_1 + w_4 - w_1_omega + q_m = 0
            minigate_variables.emplace_back(left_idx);
            minigate_variables.emplace_back(fourth_idx);
            if (index != blk.size() - 1) {
                gate_variables.emplace_back(blk.w_4()[index + 1]);
                minigate_variables.emplace_back(blk.w_l()[index + 1]);
            }
        }
    }
    gate_variables = this->to_real(ultra_circuit_builder, gate_variables);
    minigate_variables = this->to_real(ultra_circuit_builder, minigate_variables);
    this->process_gate_variables(gate_variables, index, block_idx);
    this->process_gate_variables(minigate_variables, index, block_idx);
    all_gates_variables.emplace_back(gate_variables);
    if (!minigate_variables.empty()) {
        all_gates_variables.emplace_back(minigate_variables);
    }
 
    return all_gates_variables;
}
 
template <typename FF>
inline std::vector<uint32_t> StaticAnalyzer_<FF>::get_elliptic_gate_connected_component(
    bb::UltraCircuitBuilder& ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock& blk)
{
    std::vector<uint32_t> gate_variables;
    if (!blk.q_elliptic()[index].is_zero()) {
        gate_variables.reserve(6);
        bool is_elliptic_add_gate = !blk.q_1()[index].is_zero() && blk.q_m()[index].is_zero();
        bool is_elliptic_dbl_gate = blk.q_1()[index].is_zero() && blk.q_m()[index] == FF::one();
        auto right_idx = blk.w_r()[index];
        auto out_idx = blk.w_o()[index];
        gate_variables.emplace_back(right_idx);
        gate_variables.emplace_back(out_idx);
        if (index != blk.size() - 1) {
            if (is_elliptic_add_gate) {
                // if this gate is ecc_add_gate, we have to get indices x2, x3, y3, y2 from the next gate
                gate_variables.emplace_back(blk.w_l()[index + 1]);
                gate_variables.emplace_back(blk.w_r()[index + 1]);
                gate_variables.emplace_back(blk.w_o()[index + 1]);
                gate_variables.emplace_back(blk.w_4()[index + 1]);
            }
            if (is_elliptic_dbl_gate) {
                // if this gate is ecc_dbl_gate, we have to indices x3, y3 from right and output wires
                gate_variables.emplace_back(blk.w_r()[index + 1]);
                gate_variables.emplace_back(blk.w_o()[index + 1]);
            }
        }
        gate_variables = this->to_real(ultra_circuit_builder, gate_variables);
        this->process_gate_variables(gate_variables, index, block_idx);
    }
    return gate_variables;
}
 
template <typename FF>
inline std::vector<uint32_t> StaticAnalyzer_<FF>::get_sort_constraint_connected_component(
    bb::UltraCircuitBuilder& ultra_circuit_builder, size_t index, size_t blk_idx, UltraBlock& block)
{
    std::vector<uint32_t> gate_variables = {};
    if (!block.q_delta_range()[index].is_zero()) {
        gate_variables.reserve(4);
        gate_variables.emplace_back(block.w_l()[index]);
        gate_variables.emplace_back(block.w_r()[index]);
        gate_variables.emplace_back(block.w_o()[index]);
        gate_variables.emplace_back(block.w_4()[index]);
    }
    gate_variables = this->to_real(ultra_circuit_builder, gate_variables);
    this->process_gate_variables(gate_variables, index, blk_idx);
    return gate_variables;
}
 
template <typename FF>
inline std::vector<uint32_t> StaticAnalyzer_<FF>::get_plookup_gate_connected_component(
    bb::UltraCircuitBuilder& ultra_circuit_builder, size_t index, size_t blk_idx, UltraBlock& block)
{
    std::vector<uint32_t> gate_variables;
    auto q_lookup_type = block.q_lookup_type()[index];
    if (!q_lookup_type.is_zero()) {
        gate_variables.reserve(6);
        auto q_2 = block.q_2()[index];
        auto q_m = block.q_m()[index];
        auto q_c = block.q_c()[index];
        gate_variables.emplace_back(block.w_l()[index]);
        gate_variables.emplace_back(block.w_r()[index]);
        gate_variables.emplace_back(block.w_o()[index]);
        if (index < block.size() - 1) {
            if (!q_2.is_zero()) {
                gate_variables.emplace_back(block.w_l()[index + 1]);
            }
            if (!q_m.is_zero()) {
                gate_variables.emplace_back(block.w_r()[index + 1]);
            }
            if (!q_c.is_zero()) {
                gate_variables.emplace_back(block.w_o()[index + 1]);
            }
        }
        gate_variables = this->to_real(ultra_circuit_builder, gate_variables);
        this->process_gate_variables(gate_variables, index, blk_idx);
    }
    return gate_variables;
}
 
template <typename FF>
inline std::vector<uint32_t> StaticAnalyzer_<FF>::get_poseido2s_gate_connected_component(
    bb::UltraCircuitBuilder& ultra_circuit_builder, size_t index, size_t blk_idx, UltraBlock& block)
{
    std::vector<uint32_t> gate_variables;
    auto internal_selector = block.q_poseidon2_internal()[index];
    auto external_selector = block.q_poseidon2_external()[index];
    if (!internal_selector.is_zero() || !external_selector.is_zero()) {
        gate_variables.reserve(8);
        gate_variables.emplace_back(block.w_l()[index]);
        gate_variables.emplace_back(block.w_r()[index]);
        gate_variables.emplace_back(block.w_o()[index]);
        gate_variables.emplace_back(block.w_4()[index]);
        if (index != block.size() - 1) {
            gate_variables.emplace_back(block.w_l()[index + 1]);
            gate_variables.emplace_back(block.w_r()[index + 1]);
            gate_variables.emplace_back(block.w_o()[index + 1]);
            gate_variables.emplace_back(block.w_4()[index + 1]);
        }
        gate_variables = this->to_real(ultra_circuit_builder, gate_variables);
        this->process_gate_variables(gate_variables, index, blk_idx);
    }
    return gate_variables;
}
 
template <typename FF>
inline std::vector<uint32_t> StaticAnalyzer_<FF>::get_memory_gate_connected_component(
    bb::UltraCircuitBuilder& ultra_builder, size_t index, size_t blk_idx, UltraBlock& block)
{
    std::vector<uint32_t> gate_variables;
    if (!block.q_memory()[index].is_zero()) {
        gate_variables.reserve(8);
        auto q_1 = block.q_1()[index];
        auto q_2 = block.q_2()[index];
        auto q_3 = block.q_3()[index];
        auto q_4 = block.q_4()[index];
        [[maybe_unused]] auto q_m = block.q_m()[index];
        [[maybe_unused]] auto q_c = block.q_c()[index];
 
        [[maybe_unused]] auto w_l = block.w_l()[index];
        [[maybe_unused]] auto w_r = block.w_r()[index];
        [[maybe_unused]] auto w_o = block.w_o()[index];
        [[maybe_unused]] auto w_4 = block.w_4()[index];
 
        if (q_1 == FF::one() && q_4 == FF::one()) {
            ASSERT(q_3.is_zero());
            // ram timestamp check
            if (index < block.size() - 1) {
                gate_variables.insert(gate_variables.end(),
                                      { block.w_r()[index + 1],
                                        block.w_r()[index],
                                        block.w_l()[index],
                                        block.w_l()[index + 1],
                                        block.w_o()[index] });
            }
        } else if (q_1 == FF::one() && q_2 == FF::one()) {
            ASSERT(q_3.is_zero());
            // rom constitency check
            if (index < block.size() - 1) {
                gate_variables.insert(
                    gate_variables.end(),
                    { block.w_l()[index], block.w_l()[index + 1], block.w_4()[index], block.w_4()[index + 1] });
            }
        } else {
            // ram constitency check
            if (!q_3.is_zero()) {
                if (index < block.size() - 1) {
                    gate_variables.insert(gate_variables.end(),
                                          { block.w_o()[index],
                                            block.w_4()[index],
                                            block.w_l()[index + 1],
                                            block.w_r()[index + 1],
                                            block.w_o()[index + 1],
                                            block.w_4()[index + 1] });
                }
            }
        }
    }
    gate_variables = this->to_real(ultra_builder, gate_variables);
    this->process_gate_variables(gate_variables, index, blk_idx);
    return gate_variables;
}
 
template <typename FF>
inline std::vector<uint32_t> StaticAnalyzer_<FF>::get_non_native_field_gate_connected_component(
    bb::UltraCircuitBuilder& ultra_builder, size_t index, size_t blk_idx, UltraBlock& block)
{
    std::vector<uint32_t> gate_variables;
    if (!block.q_nnf()[index].is_zero()) {
        gate_variables.reserve(8);
        [[maybe_unused]] auto q_1 = block.q_1()[index];
        auto q_2 = block.q_2()[index];
        auto q_3 = block.q_3()[index];
        auto q_4 = block.q_4()[index];
        auto q_m = block.q_m()[index];
        [[maybe_unused]] auto q_c = block.q_c()[index];
 
        auto w_l = block.w_l()[index];
        auto w_r = block.w_r()[index];
        auto w_o = block.w_o()[index];
        auto w_4 = block.w_4()[index];
        if (q_3 == FF::one() && q_4 == FF::one()) {
            // bigfield limb accumulation 1
            if (index < block.size() - 1) {
                gate_variables.insert(gate_variables.end(),
                                      { w_l, w_r, w_o, w_4, block.w_l()[index + 1], block.w_r()[index + 1] }); // 6
            }
        } else if (q_3 == FF::one() && q_m == FF::one()) {
            // bigfield limb accumulation 2
            if (index < block.size() - 1) {
                gate_variables.insert(gate_variables.end(),
                                      { w_o,
                                        w_4,
                                        block.w_l()[index + 1],
                                        block.w_r()[index + 1],
                                        block.w_o()[index + 1],
                                        block.w_4()[index + 1] });
            }
        } else if (q_2 == FF::one() && (q_3 == FF::one() || q_4 == FF::one() || q_m == FF::one())) {
            // bigfield product cases
            if (index < block.size() - 1) {
                std::vector<uint32_t> limb_subproduct_vars = {
                    w_l, w_r, block.w_l()[index + 1], block.w_r()[index + 1]
                };
                if (q_3 == FF::one()) {
                    // bigfield product 1
                    ASSERT(q_4.is_zero() && q_m.is_zero());
                    gate_variables.insert(
                        gate_variables.end(), limb_subproduct_vars.begin(), limb_subproduct_vars.end());
                    gate_variables.insert(gate_variables.end(), { w_o, w_4 });
                }
                if (q_4 == FF::one()) {
                    // bigfield product 2
                    ASSERT(q_3.is_zero() && q_m.is_zero());
                    std::vector<uint32_t> non_native_field_gate_2 = { w_l, w_4, w_r, w_o, block.w_o()[index + 1] };
                    gate_variables.insert(
                        gate_variables.end(), non_native_field_gate_2.begin(), non_native_field_gate_2.end());
                    gate_variables.emplace_back(block.w_4()[index + 1]);
                    gate_variables.insert(
                        gate_variables.end(), limb_subproduct_vars.begin(), limb_subproduct_vars.end());
                }
                if (q_m == FF::one()) {
                    // bigfield product 3
                    ASSERT(q_4.is_zero() && q_3.is_zero());
                    gate_variables.insert(
                        gate_variables.end(), limb_subproduct_vars.begin(), limb_subproduct_vars.end());
                    gate_variables.insert(gate_variables.end(),
                                          { w_4, block.w_o()[index + 1], block.w_4()[index + 1] });
                }
            }
        }
    }
    gate_variables = this->to_real(ultra_builder, gate_variables);
    this->process_gate_variables(gate_variables, index, blk_idx);
    return gate_variables;
}
 
template <typename FF>
inline std::vector<uint32_t> StaticAnalyzer_<FF>::get_rom_table_connected_component(
    bb::UltraCircuitBuilder& ultra_builder, const bb::RomTranscript& rom_array)
{
    size_t block_index = find_block_index(ultra_builder, ultra_builder.blocks.memory);
    BB_ASSERT_EQ(block_index, 5U);
 
    // Every RomTranscript data structure has 2 main components that are interested for static analyzer:
    // 1) records contains values that were put in the gate, we can use them to create connections between variables
    // 2) states contains values witness indexes that we can find in the ROM record in the RomTrascript, so we can
    // ignore state of the ROM transcript, because we still can connect all variables using variables from records.
    std::vector<uint32_t> rom_table_variables;
 
    for (const auto& record : rom_array.records) {
        std::vector<uint32_t> gate_variables;
        size_t gate_index = record.gate_index;
 
        auto q_1 = ultra_builder.blocks.memory.q_1()[gate_index];
        auto q_2 = ultra_builder.blocks.memory.q_2()[gate_index];
        auto q_3 = ultra_builder.blocks.memory.q_3()[gate_index];
        auto q_4 = ultra_builder.blocks.memory.q_4()[gate_index];
        auto q_m = ultra_builder.blocks.memory.q_m()[gate_index];
        auto q_c = ultra_builder.blocks.memory.q_c()[gate_index];
 
        auto index_witness = record.index_witness;
        auto vc1_witness = record.value_column1_witness; // state[0] from RomTranscript
        auto vc2_witness = record.value_column2_witness; // state[1] from RomTranscript
        auto record_witness = record.record_witness;
 
        if (q_1 == FF::one() && q_m == FF::one() && q_2.is_zero() && q_3.is_zero() && q_4.is_zero() && q_c.is_zero()) {
            // By default ROM read gate uses variables (w_1, w_2, w_3, w_4) = (index_witness, vc1_witness, vc2_witness,
            // record_witness) So we can update all of them
            gate_variables.emplace_back(index_witness);
            if (vc1_witness != ultra_builder.zero_idx) {
                gate_variables.emplace_back(vc1_witness);
            }
            if (vc2_witness != ultra_builder.zero_idx) {
                gate_variables.emplace_back(vc2_witness);
            }
            gate_variables.emplace_back(record_witness);
        }
        gate_variables = this->to_real(ultra_builder, gate_variables);
        this->process_gate_variables(gate_variables, gate_index, block_index);
        // after process_gate_variables function gate_variables constists of real variables indexes, so we can add all
        // this variables in the final vector to connect all of them
        if (!gate_variables.empty()) {
            rom_table_variables.insert(rom_table_variables.end(), gate_variables.begin(), gate_variables.end());
        }
    }
    return rom_table_variables;
}
 
template <typename FF>
inline std::vector<uint32_t> StaticAnalyzer_<FF>::get_ram_table_connected_component(
    bb::UltraCircuitBuilder& ultra_builder, const bb::RamTranscript& ram_array)
{
    size_t block_index = find_block_index(ultra_builder, ultra_builder.blocks.memory);
    BB_ASSERT_EQ(block_index, 5U);
    std::vector<uint32_t> ram_table_variables;
    for (const auto& record : ram_array.records) {
        std::vector<uint32_t> gate_variables;
        size_t gate_index = record.gate_index;
 
        auto q_1 = ultra_builder.blocks.memory.q_1()[gate_index];
        auto q_2 = ultra_builder.blocks.memory.q_2()[gate_index];
        auto q_3 = ultra_builder.blocks.memory.q_3()[gate_index];
        auto q_4 = ultra_builder.blocks.memory.q_4()[gate_index];
        auto q_m = ultra_builder.blocks.memory.q_m()[gate_index];
        auto q_c = ultra_builder.blocks.memory.q_c()[gate_index];
 
        auto index_witness = record.index_witness;
        auto timestamp_witness = record.timestamp_witness;
        auto value_witness = record.value_witness;
        auto record_witness = record.record_witness;
 
        if (q_1 == FF::one() && q_m == FF::one() && q_2.is_zero() && q_3.is_zero() && q_4.is_zero() &&
            (q_c.is_zero() || q_c == FF::one())) {
            // By default RAM read/write gate uses variables (w_1, w_2, w_3, w_4) = (index_witness, timestamp_witness,
            // value_witness, record_witness) So we can update all of them
            gate_variables.emplace_back(index_witness);
            if (timestamp_witness != ultra_builder.zero_idx) {
                gate_variables.emplace_back(timestamp_witness);
            }
            if (value_witness != ultra_builder.zero_idx) {
                gate_variables.emplace_back(value_witness);
            }
            gate_variables.emplace_back(record_witness);
        }
        gate_variables = this->to_real(ultra_builder, gate_variables);
        this->process_gate_variables(gate_variables, gate_index, block_index);
        // after process_gate_variables function gate_variables constists of real variables indexes, so we can add all
        // these variables in the final vector to connect all of them
        ram_table_variables.insert(ram_table_variables.end(), gate_variables.begin(), gate_variables.end());
    }
    return ram_table_variables;
}
 
template <typename FF>
StaticAnalyzer_<FF>::StaticAnalyzer_(bb::UltraCircuitBuilder& ultra_circuit_constructor, bool connect_variables)
{
    this->variables_gate_counts =
        std::unordered_map<uint32_t, size_t>(ultra_circuit_constructor.real_variable_index.size());
    this->variable_adjacency_lists =
        std::unordered_map<uint32_t, std::vector<uint32_t>>(ultra_circuit_constructor.real_variable_index.size());
    this->variables_degree = std::unordered_map<uint32_t, size_t>(ultra_circuit_constructor.real_variable_index.size());
    for (const auto& variable_index : ultra_circuit_constructor.real_variable_index) {
        variables_gate_counts[variable_index] = 0;
        variables_degree[variable_index] = 0;
        variable_adjacency_lists[variable_index] = {};
    }
 
    std::map<FF, uint32_t> constant_variable_indices = ultra_circuit_constructor.constant_variable_indices;
    auto block_data = ultra_circuit_constructor.blocks.get();
    for (size_t blk_idx = 1; blk_idx < block_data.size() - 1; blk_idx++) {
        if (block_data[blk_idx].size() == 0) {
            continue;
        }
        std::vector<uint32_t> sorted_variables;
        for (size_t gate_idx = 0; gate_idx < block_data[blk_idx].size(); gate_idx++) {
            auto arithmetic_gates_variables = get_arithmetic_gate_connected_component(
                ultra_circuit_constructor, gate_idx, blk_idx, block_data[blk_idx]);
            if (!arithmetic_gates_variables.empty() && connect_variables) {
                for (const auto& gate_variables : arithmetic_gates_variables) {
                    connect_all_variables_in_vector(ultra_circuit_constructor, gate_variables);
                }
            }
            auto elliptic_gate_variables = get_elliptic_gate_connected_component(
                ultra_circuit_constructor, gate_idx, blk_idx, block_data[blk_idx]);
            if (connect_variables) {
                connect_all_variables_in_vector(ultra_circuit_constructor, elliptic_gate_variables);
            }
            auto lookup_gate_variables =
                get_plookup_gate_connected_component(ultra_circuit_constructor, gate_idx, blk_idx, block_data[blk_idx]);
            if (connect_variables) {
                connect_all_variables_in_vector(ultra_circuit_constructor, lookup_gate_variables);
            }
            auto poseidon2_gate_variables = get_poseido2s_gate_connected_component(
                ultra_circuit_constructor, gate_idx, blk_idx, block_data[blk_idx]);
            if (connect_variables) {
                connect_all_variables_in_vector(ultra_circuit_constructor, poseidon2_gate_variables);
            }
            auto memory_gate_variables =
                get_memory_gate_connected_component(ultra_circuit_constructor, gate_idx, blk_idx, block_data[blk_idx]);
            if (connect_variables) {
                connect_all_variables_in_vector(ultra_circuit_constructor, memory_gate_variables);
            }
            auto nnf_gate_variables = get_non_native_field_gate_connected_component(
                ultra_circuit_constructor, gate_idx, blk_idx, block_data[blk_idx]);
            if (connect_variables) {
                connect_all_variables_in_vector(ultra_circuit_constructor, nnf_gate_variables);
            }
            if (arithmetic_gates_variables.empty() && elliptic_gate_variables.empty() &&
                lookup_gate_variables.empty() && poseidon2_gate_variables.empty() && memory_gate_variables.empty() &&
                nnf_gate_variables.empty()) {
                // if all vectors are empty it means that current block is delta range, and it needs another
                // processing method
                auto delta_range_gate_variables = get_sort_constraint_connected_component(
                    ultra_circuit_constructor, gate_idx, blk_idx, block_data[blk_idx]);
                if (delta_range_gate_variables.empty()) {
                    if (connect_variables) {
                        connect_all_variables_in_vector(ultra_circuit_constructor, sorted_variables);
                    }
                    sorted_variables.clear();
                } else {
                    sorted_variables.insert(
                        sorted_variables.end(), delta_range_gate_variables.begin(), delta_range_gate_variables.end());
                }
            }
        }
    }
 
    const auto& rom_arrays = ultra_circuit_constructor.rom_ram_logic.rom_arrays;
    if (!rom_arrays.empty()) {
        for (const auto& rom_array : rom_arrays) {
            std::vector<uint32_t> variable_indices =
                this->get_rom_table_connected_component(ultra_circuit_constructor, rom_array);
            if (connect_variables) {
                this->connect_all_variables_in_vector(ultra_circuit_constructor, variable_indices);
            }
        }
    }
 
    const auto& ram_arrays = ultra_circuit_constructor.rom_ram_logic.ram_arrays;
    if (!ram_arrays.empty()) {
        for (const auto& ram_array : ram_arrays) {
            std::vector<uint32_t> variable_indices =
                this->get_ram_table_connected_component(ultra_circuit_constructor, ram_array);
            if (connect_variables) {
                this->connect_all_variables_in_vector(ultra_circuit_constructor, variable_indices);
            }
        }
    }
}
 
template <typename FF>
bool StaticAnalyzer_<FF>::check_is_not_constant_variable(bb::UltraCircuitBuilder& ultra_circuit_builder,
                                                         const uint32_t& variable_index)
{
    bool is_not_constant = true;
    const auto& constant_variable_indices = ultra_circuit_builder.constant_variable_indices;
    for (const auto& pair : constant_variable_indices) {
        if (pair.second == ultra_circuit_builder.real_variable_index[variable_index]) {
            is_not_constant = false;
            break;
        }
    }
    return is_not_constant;
}
 
template <typename FF>
void StaticAnalyzer_<FF>::connect_all_variables_in_vector(bb::UltraCircuitBuilder& ultra_circuit_builder,
                                                          const std::vector<uint32_t>& variables_vector)
{
    if (variables_vector.empty()) {
        return;
    }
    std::vector<uint32_t> filtered_variables_vector;
    filtered_variables_vector.reserve(variables_vector.size());
    // Only copy non-zero and non-constant variables
    std::copy_if(variables_vector.begin(),
                 variables_vector.end(),
                 std::back_inserter(filtered_variables_vector),
                 [&](uint32_t variable_index) {
                     return variable_index != ultra_circuit_builder.zero_idx &&
                            this->check_is_not_constant_variable(ultra_circuit_builder, variable_index);
                 });
    // Remove duplicates
    auto unique_pointer = std::unique(filtered_variables_vector.begin(), filtered_variables_vector.end());
    filtered_variables_vector.erase(unique_pointer, filtered_variables_vector.end());
    if (filtered_variables_vector.size() < 2) {
        return;
    }
    for (size_t i = 0; i < filtered_variables_vector.size() - 1; i++) {
        this->add_new_edge(filtered_variables_vector[i], filtered_variables_vector[i + 1]);
    }
}
 
template <typename FF>
void StaticAnalyzer_<FF>::add_new_edge(const uint32_t& first_variable_index, const uint32_t& second_variable_index)
{
    variable_adjacency_lists[first_variable_index].emplace_back(second_variable_index);
    variable_adjacency_lists[second_variable_index].emplace_back(first_variable_index);
    variables_degree[first_variable_index] += 1;
    variables_degree[second_variable_index] += 1;
}
 
template <typename FF>
void StaticAnalyzer_<FF>::depth_first_search(const uint32_t& variable_index,
                                             std::unordered_set<uint32_t>& is_used,
                                             std::vector<uint32_t>& connected_component)
{
    std::stack<uint32_t> variable_stack;
    variable_stack.push(variable_index);
    while (!variable_stack.empty()) {
        uint32_t current_index = variable_stack.top();
        variable_stack.pop();
        if (!is_used.contains(current_index)) {
            is_used.insert(current_index);
            connected_component.emplace_back(current_index);
            for (const auto& it : variable_adjacency_lists[current_index]) {
                variable_stack.push(it);
            }
        }
    }
}
 
template <typename FF> std::vector<std::vector<uint32_t>> StaticAnalyzer_<FF>::find_connected_components()
{
    std::unordered_set<uint32_t> is_used;
    std::vector<std::vector<uint32_t>> connected_components;
    for (const auto& pair : variable_adjacency_lists) {
        if (pair.first != 0 && variables_degree[pair.first] > 0) {
            if (!is_used.contains(pair.first)) {
                std::vector<uint32_t> connected_component;
                this->depth_first_search(pair.first, is_used, connected_component);
                std::sort(connected_component.begin(), connected_component.end());
                connected_components.emplace_back(connected_component);
            }
        }
    }
    return connected_components;
}
 
template <typename FF>
inline size_t StaticAnalyzer_<FF>::process_current_decompose_chain(bb::UltraCircuitBuilder& ultra_circuit_constructor,
                                                                   std::unordered_set<uint32_t>& variables_in_one_gate,
                                                                   size_t index)
{
    auto& arithmetic_block = ultra_circuit_constructor.blocks.arithmetic;
    auto zero_idx = ultra_circuit_constructor.zero_idx;
    size_t current_index = index;
    std::vector<uint32_t> accumulators_indices;
    while (true) {
        // we have to remove left, right and output wires of the current gate, cause they'are new_limbs, and they are
        // useless for the analyzer
        auto fourth_idx = arithmetic_block.w_4()[current_index];
        accumulators_indices.emplace_back(this->to_real(ultra_circuit_constructor, fourth_idx));
        auto left_idx = arithmetic_block.w_l()[current_index];
        if (left_idx != zero_idx) {
            variables_in_one_gate.erase(this->to_real(ultra_circuit_constructor, left_idx));
        }
        auto right_idx = arithmetic_block.w_r()[current_index];
        if (right_idx != zero_idx) {
            variables_in_one_gate.erase(this->to_real(ultra_circuit_constructor, right_idx));
        }
        auto out_idx = arithmetic_block.w_o()[current_index];
        if (out_idx != zero_idx) {
            variables_in_one_gate.erase(this->to_real(ultra_circuit_constructor, out_idx));
        }
        auto q_arith = arithmetic_block.q_arith()[current_index];
        if (q_arith == 1 || current_index == arithmetic_block.size() - 1) {
            // this is the last gate in this chain, or we can't go next, so we have to stop a loop
            break;
        }
        current_index++;
    }
    for (size_t i = 0; i < accumulators_indices.size(); i++) {
        if (i == 0) {
            // the first variable in accumulators is the variable which decompose was created. So, we have to decrement
            // variable_gate_counts for this variable
            variables_gate_counts[accumulators_indices[i]] -= 1;
        } else {
            // next accumulators are useless variables that are not interested for the analyzer. So, for these variables
            // we can nullify variables_gate_counts
            variables_gate_counts[accumulators_indices[i]] = 0;
        }
    }
    // we don't want to make variables_gate_counts for intermediate variables negative, so, can go to the next gates
    return current_index;
}
 
template <typename FF>
inline void StaticAnalyzer_<FF>::remove_unnecessary_decompose_variables(
    bb::UltraCircuitBuilder& ultra_circuit_builder,
    std::unordered_set<uint32_t>& variables_in_one_gate,
    const std::unordered_set<uint32_t>& decompose_variables)
{
    auto is_power_two = [&](const uint256_t& number) { return number > 0 && ((number & (number - 1)) == 0); };
    auto find_position = [&](uint32_t variable_index) {
        return decompose_variables.contains(this->to_real(ultra_circuit_builder, variable_index));
    };
    auto& arithmetic_block = ultra_circuit_builder.blocks.arithmetic;
    if (arithmetic_block.size() > 0) {
        for (size_t i = 0; i < arithmetic_block.size(); i++) {
            auto q_1 = arithmetic_block.q_1()[i];
            auto q_2 = arithmetic_block.q_2()[i];
            auto q_3 = arithmetic_block.q_3()[i];
            // big addition gate from decompose has selectors, which have the next property:
            // q_1 = (1) << shifts[0], target_range_bitnum * (3 * i),
            // q_2 = (1) << shifts[1], target_range_bitnum * (3 * i + 1),
            // q_3 = (1) << shifts[2], target_range_bitnum * (3 * i + 2)
            // so, they are power of two and satisfying the following equality: q_2 * q_2 = q_1 * q_3
            // this way we can differ them from other arithmetic gates
            bool q_1_is_power_two = is_power_two(q_1);
            bool q_2_is_power_two = is_power_two(q_2);
            bool q_3_is_power_two = is_power_two(q_3);
            if (q_2 * q_2 == q_1 * q_3 && q_1_is_power_two && q_2_is_power_two && q_3_is_power_two) {
                uint32_t left_idx = arithmetic_block.w_l()[i];
                uint32_t right_idx = arithmetic_block.w_r()[i];
                uint32_t out_idx = arithmetic_block.w_o()[i];
                uint32_t fourth_idx = arithmetic_block.w_4()[i];
                bool find_left = find_position(left_idx);
                bool find_right = find_position(right_idx);
                bool find_out = find_position(out_idx);
                bool find_fourth = find_position(fourth_idx);
                if (((find_left && find_right && find_out) || (find_left && find_right && !find_out) ||
                     (find_left && find_right && !find_out) || (find_left && !find_right && !find_out)) &&
                    !find_fourth) {
                    i = this->process_current_decompose_chain(ultra_circuit_builder, variables_in_one_gate, i);
                }
            }
        }
    }
}
 
template <typename FF>
void StaticAnalyzer_<FF>::remove_unnecessary_range_constrains_variables(bb::UltraCircuitBuilder& ultra_builder)
{
    std::map<uint64_t, UltraCircuitBuilder::RangeList> range_lists = ultra_builder.range_lists;
    std::unordered_set<uint32_t> range_lists_tau_tags;
    std::unordered_set<uint32_t> range_lists_range_tags;
    std::vector<uint32_t> real_variable_tags = ultra_builder.real_variable_tags;
    for (const auto& pair : range_lists) {
        UltraCircuitBuilder::RangeList list = pair.second;
        range_lists_tau_tags.insert(list.tau_tag);
        range_lists_range_tags.insert(list.range_tag);
    }
    for (uint32_t real_index = 0; real_index < real_variable_tags.size(); real_index++) {
        if (variables_in_one_gate.contains(real_index)) {
            // this if helps us to remove variables from delta_range_constraints when finalize_circuit() function was
            // called
            if (range_lists_tau_tags.contains(real_variable_tags[real_index])) {
                variables_in_one_gate.erase(real_index);
            }
            // this if helps us to remove variables from range_constraints when range_constraint_into_two_limbs function
            // was called
            if (range_lists_range_tags.contains(real_variable_tags[real_index])) {
                variables_in_one_gate.erase(real_index);
            }
        }
    }
}
 
template <typename FF>
inline void StaticAnalyzer_<FF>::remove_unnecessary_aes_plookup_variables(
    std::unordered_set<uint32_t>& variables_in_one_gate,
    UltraCircuitBuilder& ultra_circuit_builder,
    BasicTableId& table_id,
    size_t gate_index)
{
 
    auto find_position = [&](uint32_t real_variable_index) {
        return variables_in_one_gate.contains(real_variable_index);
    };
    std::unordered_set<BasicTableId> aes_plookup_tables{ BasicTableId::AES_SBOX_MAP,
                                                         BasicTableId::AES_SPARSE_MAP,
                                                         BasicTableId::AES_SPARSE_NORMALIZE };
    auto& lookup_block = ultra_circuit_builder.blocks.lookup;
    if (aes_plookup_tables.contains(table_id)) {
        uint32_t real_out_idx = this->to_real(ultra_circuit_builder, lookup_block.w_o()[gate_index]);
        uint32_t real_right_idx = this->to_real(ultra_circuit_builder, lookup_block.w_r()[gate_index]);
        if (variables_gate_counts[real_out_idx] != 1 || variables_gate_counts[real_right_idx] != 1) {
            bool find_out = find_position(real_out_idx);
            auto q_c = lookup_block.q_c()[gate_index];
            if (q_c.is_zero()) {
                if (find_out) {
                    variables_in_one_gate.erase(real_out_idx);
                }
            }
        }
    }
}
 
template <typename FF>
inline void StaticAnalyzer_<FF>::remove_unnecessary_sha256_plookup_variables(
    std::unordered_set<uint32_t>& variables_in_one_gate,
    UltraCircuitBuilder& ultra_circuit_builder,
    BasicTableId& table_id,
    size_t gate_index)
{
 
    auto find_position = [&](uint32_t real_variable_index) {
        return variables_in_one_gate.contains(real_variable_index);
    };
    auto& lookup_block = ultra_circuit_builder.blocks.lookup;
    std::unordered_set<BasicTableId> sha256_plookup_tables{ BasicTableId::SHA256_WITNESS_SLICE_3,
                                                            BasicTableId::SHA256_WITNESS_SLICE_7_ROTATE_4,
                                                            BasicTableId::SHA256_WITNESS_SLICE_8_ROTATE_7,
                                                            BasicTableId::SHA256_WITNESS_SLICE_14_ROTATE_1,
                                                            BasicTableId::SHA256_BASE16,
                                                            BasicTableId::SHA256_BASE16_ROTATE2,
                                                            BasicTableId::SHA256_BASE16_ROTATE6,
                                                            BasicTableId::SHA256_BASE16_ROTATE7,
                                                            BasicTableId::SHA256_BASE16_ROTATE8,
                                                            BasicTableId::SHA256_BASE28,
                                                            BasicTableId::SHA256_BASE28_ROTATE3,
                                                            BasicTableId::SHA256_BASE28_ROTATE6 };
    if (sha256_plookup_tables.contains(table_id)) {
        uint32_t real_right_idx = this->to_real(ultra_circuit_builder, lookup_block.w_r()[gate_index]);
        uint32_t real_out_idx = this->to_real(ultra_circuit_builder, lookup_block.w_o()[gate_index]);
        if (variables_gate_counts[real_out_idx] != 1 || variables_gate_counts[real_right_idx] != 1) {
            // auto q_m = lookup_block.q_m()[gate_index];
            auto q_c = lookup_block.q_c()[gate_index];
            bool find_out = find_position(real_out_idx);
            // bool find_right = find_position(real_right_idx);
            if (q_c.is_zero()) {
                if (find_out) {
                    variables_in_one_gate.erase(real_out_idx);
                }
            }
            if (table_id == SHA256_BASE16_ROTATE2 || table_id == SHA256_BASE28_ROTATE6) {
                // we want to remove false cases for special tables even though their selectors != 0
                // because they are used in read_from_1_to_2_table function, and they aren't dangerous
                variables_in_one_gate.erase(real_out_idx);
            }
        }
    }
}
 
template <typename FF>
inline void StaticAnalyzer_<FF>::process_current_plookup_gate(bb::UltraCircuitBuilder& ultra_circuit_builder,
                                                              size_t gate_index)
{
    auto find_position = [&](uint32_t real_variable_index) {
        return variables_in_one_gate.contains(real_variable_index);
    };
    auto& lookup_block = ultra_circuit_builder.blocks.lookup;
    auto& lookup_tables = ultra_circuit_builder.lookup_tables;
    auto table_index = static_cast<size_t>(lookup_block.q_3()[gate_index]);
    for (const auto& table : lookup_tables) {
        if (table.table_index == table_index) {
            std::unordered_set<bb::fr> column_1(table.column_1.begin(), table.column_1.end());
            std::unordered_set<bb::fr> column_2(table.column_2.begin(), table.column_2.end());
            std::unordered_set<bb::fr> column_3(table.column_3.begin(), table.column_3.end());
            bb::plookup::BasicTableId table_id = table.id;
            // false cases for AES
            this->remove_unnecessary_aes_plookup_variables(
                variables_in_one_gate, ultra_circuit_builder, table_id, gate_index);
            // false cases for sha256
            this->remove_unnecessary_sha256_plookup_variables(
                variables_in_one_gate, ultra_circuit_builder, table_id, gate_index);
            // if the amount of unique elements from columns of plookup tables = 1, it means that
            // variable from this column aren't used and we can remove it.
            if (column_1.size() == 1) {
                uint32_t left_idx = lookup_block.w_l()[gate_index];
                uint32_t real_left_idx = this->to_real(ultra_circuit_builder, left_idx);
                bool find_left = find_position(real_left_idx);
                if (find_left) {
                    variables_in_one_gate.erase(real_left_idx);
                }
            }
            if (column_2.size() == 1) {
                uint32_t real_right_idx = this->to_real(ultra_circuit_builder, lookup_block.w_r()[gate_index]);
                bool find_right = find_position(real_right_idx);
                if (find_right) {
                    variables_in_one_gate.erase(real_right_idx);
                }
            }
            if (column_3.size() == 1) {
                uint32_t real_out_idx = this->to_real(ultra_circuit_builder, lookup_block.w_o()[gate_index]);
                bool find_out = find_position(real_out_idx);
                if (find_out) {
                    variables_in_one_gate.erase(real_out_idx);
                }
            }
        }
    }
}
 
template <typename FF>
inline void StaticAnalyzer_<FF>::remove_unnecessary_plookup_variables(bb::UltraCircuitBuilder& ultra_circuit_builder)
{
    auto& lookup_block = ultra_circuit_builder.blocks.lookup;
    if (lookup_block.size() > 0) {
        for (size_t i = 0; i < lookup_block.size(); i++) {
            this->process_current_plookup_gate(ultra_circuit_builder, i);
        }
    }
}
 
template <typename FF>
inline void StaticAnalyzer_<FF>::remove_record_witness_variables(bb::UltraCircuitBuilder& ultra_builder)
{
    auto block_data = ultra_builder.blocks.get();
    size_t blk_idx = find_block_index(ultra_builder, ultra_builder.blocks.memory);
    std::vector<uint32_t> to_remove;
    BB_ASSERT_EQ(blk_idx, 5U);
    for (const auto& var_idx : variables_in_one_gate) {
        KeyPair key = { var_idx, blk_idx };
        if (auto search = variable_gates.find(key); search != variable_gates.end()) {
            std::vector<size_t> gate_indexes = variable_gates[key];
            BB_ASSERT_EQ(gate_indexes.size(), 1U);
            size_t gate_idx = gate_indexes[0];
            auto q_1 = block_data[blk_idx].q_1()[gate_idx];
            auto q_2 = block_data[blk_idx].q_2()[gate_idx];
            auto q_3 = block_data[blk_idx].q_3()[gate_idx];
            auto q_4 = block_data[blk_idx].q_4()[gate_idx];
            auto q_m = block_data[blk_idx].q_m()[gate_idx];
            auto q_arith = block_data[blk_idx].q_arith()[gate_idx];
            if (q_1 == FF::one() && q_m == FF::one() && q_2.is_zero() && q_3.is_zero() && q_4.is_zero() &&
                q_arith.is_zero()) {
                // record witness can be in both ROM and RAM gates, so we can ignore q_c
                // record witness is written as 4th variable in RAM/ROM read/write gate, so we can get 4th wire value
                // and check it with our variable
                if (this->to_real(ultra_builder, block_data[blk_idx].w_4()[gate_idx]) == var_idx) {
                    to_remove.emplace_back(var_idx);
                }
            }
        }
    }
    for (const auto& elem : to_remove) {
        variables_in_one_gate.erase(elem);
    }
}
 
template <typename FF>
std::unordered_set<uint32_t> StaticAnalyzer_<FF>::show_variables_in_one_gate(
    bb::UltraCircuitBuilder& ultra_circuit_builder)
{
    for (const auto& pair : variables_gate_counts) {
        bool is_not_constant_variable = this->check_is_not_constant_variable(ultra_circuit_builder, pair.first);
        if (pair.second == 1 && pair.first != 0 && is_not_constant_variable) {
            this->variables_in_one_gate.insert(pair.first);
        }
    }
    auto range_lists = ultra_circuit_builder.range_lists;
    std::unordered_set<uint32_t> decompose_varialbes;
    for (auto& pair : range_lists) {
        for (auto& elem : pair.second.variable_indices) {
            bool is_not_constant_variable = this->check_is_not_constant_variable(ultra_circuit_builder, elem);
            if (variables_gate_counts[ultra_circuit_builder.real_variable_index[elem]] == 1 &&
                is_not_constant_variable) {
                decompose_varialbes.insert(ultra_circuit_builder.real_variable_index[elem]);
            }
        }
    }
    this->remove_unnecessary_decompose_variables(
        ultra_circuit_builder, this->variables_in_one_gate, decompose_varialbes);
    this->remove_unnecessary_plookup_variables(ultra_circuit_builder);
    this->remove_unnecessary_range_constrains_variables(ultra_circuit_builder);
    for (const auto& elem : this->fixed_variables) {
        this->variables_in_one_gate.erase(elem);
    }
    // we found variables that were in one gate and they are intended cases.
    // so we have to remove them from the scope
    for (const auto& elem : ultra_circuit_builder.get_used_witnesses()) {
        this->variables_in_one_gate.erase(elem);
    }
    this->remove_record_witness_variables(ultra_circuit_builder);
    return variables_in_one_gate;
}
 
std::pair<std::vector<uint32_t>, size_t> get_connected_component_with_index(
    const std::vector<std::vector<uint32_t>>& connected_components, size_t index)
{
    auto connected_component = connected_components[index];
    auto size = connected_component.size();
    return std::make_pair(connected_component, size);
}
 
template <typename FF> void StaticAnalyzer_<FF>::print_graph()
{
    for (const auto& elem : variable_adjacency_lists) {
        info("variable with index ", elem.first);
        if (variable_adjacency_lists[elem.first].empty()) {
            info("is isolated");
        } else {
            for (const auto& it : elem.second) {
                info(it);
            }
        }
    }
}
 
template <typename FF> void StaticAnalyzer_<FF>::print_connected_components()
{
    auto connected_components = find_connected_components();
    for (size_t i = 0; i < connected_components.size(); i++) {
        info("printing the ", i + 1, " connected component with size ", connected_components[i].size(), ":");
        for (const auto& it : connected_components[i]) {
            info(it, " ");
        }
    }
}
 
template <typename FF> void StaticAnalyzer_<FF>::print_variables_gate_counts()
{
    for (const auto& it : variables_gate_counts) {
        info("number of gates with variables ", it.first, " == ", it.second);
    }
}
 
template <typename FF>
void StaticAnalyzer_<FF>::print_variable_in_one_gate(bb::UltraCircuitBuilder& ultra_builder, const uint32_t real_idx)
{
    const auto& block_data = ultra_builder.blocks.get();
    for (const auto& [key, gates] : variable_gates) {
        if (key.first == real_idx) {
            BB_ASSERT_EQ(gates.size(), 1U);
            size_t gate_index = gates[0];
            UltraBlock block = block_data[key.second];
            info("---- printing variables in this gate");
            info("w_l == ",
                 block.w_l()[gate_index],
                 " w_r == ",
                 block.w_r()[gate_index],
                 " w_o == ",
                 block.w_o()[gate_index],
                 " w_4 == ",
                 block.w_4()[gate_index]);
            info("---- printing gate selectors where variable with index ", key.first, " was found ----");
            auto q_m = block.q_m()[gate_index];
            if (!q_m.is_zero()) {
                info("q_m == ", q_m);
            }
            auto q_1 = block.q_1()[gate_index];
            if (!q_1.is_zero()) {
                info("q1 == ", q_1);
            }
            auto q_2 = block.q_2()[gate_index];
            if (!q_2.is_zero()) {
                info("q2 == ", q_2);
            }
            auto q_3 = block.q_3()[gate_index];
            if (!q_3.is_zero()) {
                info("q3 == ", q_3);
            }
            auto q_4 = block.q_4()[gate_index];
            if (!q_4.is_zero()) {
                info("q4 == ", q_4);
            }
            auto q_c = block.q_c()[gate_index];
            if (!q_c.is_zero()) {
                info("q_c == ", q_c);
            }
            auto q_arith = block.q_arith()[gate_index];
            if (!q_arith.is_zero()) {
                info("q_arith == ", q_arith);
            }
            auto q_delta_range = block.q_delta_range()[gate_index];
            if (!q_delta_range.is_zero()) {
                info("q_delta_range == ", q_delta_range);
            }
            auto q_elliptic = block.q_elliptic()[gate_index];
            if (!q_elliptic.is_zero()) {
                info("q_elliptic == ", q_elliptic);
            }
            auto q_memory = block.q_memory()[gate_index];
            if (!q_memory.is_zero()) {
                info("q_memory == ", q_memory);
            }
            auto q_nnf = block.q_nnf()[gate_index];
            if (!q_nnf.is_zero()) {
                info("q_nnf == ", q_nnf);
            }
            auto q_lookup_type = block.q_lookup_type()[gate_index];
            if (!q_lookup_type.is_zero()) {
                info("q_lookup_type == ", q_lookup_type);
            }
            auto q_poseidon2_external = block.q_poseidon2_external()[gate_index];
            if (!q_poseidon2_external.is_zero()) {
                info("q_poseidon2_external == ", q_poseidon2_external);
            }
            auto q_poseidon2_internal = block.q_poseidon2_internal()[gate_index];
            if (!q_poseidon2_internal.is_zero()) {
                info("q_poseidon2_internal == ", q_poseidon2_internal);
            }
            info("---- finished printing ----");
        }
    }
}
 
template class StaticAnalyzer_<bb::fr>;
 
} // namespace cdg