feat: support signed `<<<` by a variable amount in `grind`'s bit-vector homomorphism rules This PR makes `grind` prove goals about the signed value of a bit vector shifted left by a variable amount, such as `(x <<< n).toInt = (x.toInt <<< n).bmod (2 ^ 16)`, and lets nested signed results compose, such as `((x <<< m) <<< n).toInt = (x.toInt * 2 ^ m * 2 ^ n).bmod (2 ^ 16)`, `((x + y) <<< n).toInt = ((x.toInt + y.toInt) * 2 ^ n).bmod (2 ^ 16)` and `((x * y) * z).toInt = (x.toInt * y.toInt * z.toInt).bmod (2 ^ 16)`. `BitVec.toInt_shiftLeft` was the only `toInt` homomorphism rule stated through the unsigned image, `(x.toNat <<< n : Int).bmod (2 ^ w)`, so the goal reduced to `(x.toNat * 2 ^ n).bmod (2 ^ 16) = (x.toInt * 2 ^ n).bmod (2 ^ 16)`, which needs the congruence between `x.toInt` and `x.toNat` multiplied by the nonlinear atom `2 ^ n`; `cutsat` cannot do that. The new lemma `BitVec.toInt_shiftLeft_eq_toInt_shiftLeft_bmod : (x <<< n).toInt = (x.toInt <<< n).bmod (2 ^ w)` replaces it in the hom set. `BitVec.toInt_setWidth` becomes a hom rule as well: with the pure form, `(x.setWidth v).toInt` (reached through `shiftLeftZeroExtend_eq`) is otherwise left as a stuck injected term that E-matching expands through the `msb` lemmas, which showed up in `#grind_lint`. The signed fragment also had no counterpart of the `%`-cleanup rules, so nested `bmod` wrappers never collapsed; the `Int.bmod_add_bmod`, `Int.bmod_mul_bmod`, `Int.bmod_bmod`, `Int.emod_bmod` family are hom rules now. Caveat: this changes the shape of the homomorphism rule set. `(t <<< n).toInt` now maps into the signed image `t.toInt` instead of the unsigned image `t.toNat`, so goals that relate a signed shift to `toNat` go through the same `toInt`/`toNat` bridge as `+`, `*` and the other signed operations, which is linear and works for literal shift amounts and for a single variable shift (`(x <<< n).toInt = (x.toNat * 2 ^ n : Int).bmod (2 ^ 16)` still closes, through the `[grind =]` copy of `toInt_shiftLeft`). Mixed-view goals with a nonlinear factor can regress: `((x <<< m) <<< n).toInt = (x.toNat * 2 ^ m * 2 ^ n : Int).bmod (2 ^ 16)` closed before and does not now, because the inner `toNat` is already in the E-graph when the E-matching instance is internalized, so the homomorphism rewriter stops there and `cutsat` sees an opaque product. The first goal of `grind_cutsat_reorder.lean` becomes a syntactic identity under the new rule and is replaced by its mixed-form counterpart, which still creates the late quotient variable the test pins. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
This is the repository for Lean 4.
See Install Lean.
Please read our Contribution Guidelines first.
See Building Lean.