Check that the conditions for applicability of the selector combining optimization are correctly enforced, and document why

[daira]

From https://zcash.github.io/halo2/design/implementation/selector-combining.html :

Check (or ensure by construction) that all polynomial constraints involving each simple selector $s_i$​ are of the form $si \cdot t{i,j}​ = 0$ where $t_{i,j}$​ do not involve any simple selectors.

See also https://zcash.github.io/halo2/background/polynomials.html#lagrange-basis-functions .

[daira]

@therealyingtong and I reviewed the relevant code. It was correct, but not obviously correct!

Define a simple Expression to be one that contains any simple selector as a subterm.

Define the factors of an Expression to be the set of subterms that are combined only using Expression::{Product,Scaled,Negated}. (The factors can themselves be arbitrary Expressions.)

Define the maximal degree of a selector to be:

• 0, if the selector is non-simple or it is not used in any gate;
• the maximum degree of any gate in which the selector is used, otherwise.

The argument is:

• simple Expressions can only be constructed such that exactly one factor is a simple selector.
• contains_simple_selector() correctly identifies simple Expressions and only simple Expressions.
• extract_simple_selector() extracts the simple selector from a simple Expression, or returns None if its input is a non-simple Expression.
• the loop here correctly computes the max_degree of each SelectorDescription (in particular, it computes 0 for non-simple selectors).
• if the max_degree of a SelectorDescription is 0 at https://github.com/zcash/halo2/blob/61a1f63fcbc4792aaf1c285fd79a001495bd32f2/halo2_proofs/src/plonk/circuit/compress_selectors.rs#L76 then the selector will not be eligible for combining.

All of this should be documented in the code!