Gates should advertise their use of lookup tables, not LookupInfo

[mimoo]

Looking at how the lookup selectors are created, I see this:

// we go through the circuit
for (row, gate) in gates.iter().enumerate().take(n) {
    use CurrOrNext::*;

    // we figure out how the gate affects the lookup selectors
    if let Some(selector_index) = self.kinds_map.get(&(gate.typ, Curr)) {
        // we use this to compute the lookup selectors
        selector_values[*selector_index][row] = F::one();
    }
    if let Some(selector_index) = self.kinds_map.get(&(gate.typ, Next)) {
        selector_values[*selector_index][row + 1] = F::one();
    }

    // we also keep track of the different tables used throughout the circuit in the `gate_tables` set
    if let Some(table_kind) = self.kinds_tables.get(&(gate.typ, Curr)) {
        gate_tables.insert(*table_kind);
    }
    if let Some(table_kind) = self.kinds_tables.get(&(gate.typ, Next)) {
        gate_tables.insert(*table_kind);
    }
}

What I don't understand, is why do we need to store the kinds_map and kinds_table hashmaps here? The gates themselves should tell us that information. It would be better to do something like this:

/// Each gate should implement the ApplyLookup trait if they use lookup tables
/// to tell us which lookup tables, and where, should we apply them
mod lookup {
    #[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
    pub enum LookupTable {
        Xor = 0
    }
    
    pub struct WhichRows {
        pub current: bool,
        pub next: bool,
    }
    
    pub trait ApplyLookup {
        fn where_to_apply_lookup() -> Vec<(LookupTable, WhichRows)>;
    }
}

mod gates {
    use super::generic::GenericGate;
    use super::lookup::{LookupTable, ApplyLookup, WhichRows};
    
    pub enum GateType {
        Generic,
        Poseidon
    }
    
    impl GateType {
        /// The GateType dispatches to the relevant function for each gate
        /// Since this is done manually, the trait ApplyLookup is not strictly necessary
        pub fn lookup(&self) -> Vec<(LookupTable, WhichRows)> {
            match self {
                Self::Generic => GenericGate::where_to_apply_lookup(),
                Self::Poseidon => vec![], // avoid implementation for example
            }
        }
    }
}

/// Let's imagine that the generic gate 
mod generic {
    use super::lookup::{LookupTable, ApplyLookup, WhichRows};
    
    pub struct GenericGate;
    
    impl ApplyLookup for GenericGate {
        fn where_to_apply_lookup() -> Vec<(LookupTable, WhichRows)> {
            vec![
                (LookupTable::Xor, WhichRows { current: true, next: true }),
                (LookupTable::Xor, WhichRows { current: true, next: true })
            ]
        }
    }
}

fn main() {
    use gates::GateType;
    // now let's imagine we're going through a circuit
    let circuit = vec![GateType::Generic, GateType::Generic, GateType::Poseidon];
    let mut lookup_selectors = vec![vec![0; circuit.len()]];
    let mut used_lookup_tables = std::collections::HashSet::new();
    
    for (row, gate) in circuit.iter().enumerate() {
        for (lookup_table, which_rows) in gate.lookup() {
            let lookup_selector = &mut lookup_selectors[lookup_table as usize];
            if which_rows.current {
                lookup_selector[row] = 1;
            }
            if which_rows.next {
                lookup_selector[row + 1] = 1;
            }
            used_lookup_tables.insert(lookup_table);
        }
    }
    
    println!("lookup selectors: {:?}", lookup_selectors);
    println!("used lookup tables: {:?}", used_lookup_tables);
}

playground if you want to play with it

[mimoo]

I think this is not going to work out of the box, need to spend more time understanding how to get rid of kinds_map and table_kinds

[mimoo]

there's a lot more machinery that can be moved to the gate that are making use of lookup (what's in lookup_kinds, for example). I think I'm going to spend some time digging into doing this refactor. @mrmr1993 is that OK? I know you had some refactors you wanted to push as well. Let me know.

[mrmr1993]

I agree, this is definitely the way to go.

One thing to consider: we should probably be using the existing selectors instead of generating fresh lookup selectors. This should also result in slightly simpler code overall.

[mimoo]

do you wanna create an issue on the existing selectors part? I'm not sure I understand at this point

[github-actions[bot]]

Stale issue message

[github-actions[bot]]

Stale issue message

[github-actions[bot]]

Stale issue message