leanprover / lean4

Lean 4 programming language and theorem prover
https://lean-lang.org
Apache License 2.0
3.88k stars 329 forks source link

Confusing `split` error #3731

Closed hargoniX closed 2 weeks ago

hargoniX commented 2 months ago

Prerequisites

Description

In the following file:

import Std.Data.HashMap
open Std

/--
A circuit node declaration. These are not recursive but instead contain indices into an `Env`.
-/
inductive Decl where
  /--
  A node with a constant output value.
  -/
  | const (b : Bool)
  /--
  An input node to the circuit.
  -/
  | atom (idx : Nat)
  /--
  An AIG gate with configurable input nodes and polarity. `l` and `r` are the
  input node indices while `linv` and `rinv` say whether there is an inverter on
  the left or right input.
  -/
  | gate (l r : Nat) (linv rinv : Bool)
  deriving BEq, Hashable, DecidableEq

/--
A cache that is valid with respect to some `Array Decl`.
-/
def Cache (decls : Array Decl) := HashMap Decl Nat

/--
Lookup a `decl` in a `cache`.

If this returns `some i`, `Cache.find?_poperty` can be used to demonstrate: `decls[i] = decl`.
-/
@[irreducible]
def Cache.find? (cache : Cache decls) (decl : Decl) : Option Nat :=
  match cache.val.find? decl with
  | some hit =>
    if h1:hit < decls.size then
      if decls[hit]'h1 = decl then
        some hit
      else
        none
    else
      none
  | none => none

/--
This states that all indices, found in a `Cache` that is valid with respect to some `decls`,
are within bounds of `decls`.
-/
theorem Cache.find?_bounds {decls : Array Decl} {idx : Nat} (c : Cache decls) (decl : Decl)
    (h : c.find? decl = some idx) : idx < decls.size := by
  unfold find? at h
  split at h
  . split at h
    . split at h
      . injection h
        omega
      . contradiction
    . contradiction
  . contradiction

/--
This states that if `Cache.find? decl` returns `some i`, `decls[i] = decl`, holds.
-/
theorem Cache.find?_property {decls : Array Decl} {idx : Nat} (c : Cache decls) (decl : Decl)
    (h : c.find? decl = some idx) : decls[idx]'(Cache.find?_bounds c decl h) = decl := by
  unfold find? at h
  -- HERE HERE HERE HERE <<<<
  split at h
  . split at h
    . split at h
      . injection h
        omega
      . contradiction
    . contradiction
  . contradiction

split throws a confusing error in the last theorem:

tactic 'splitMatch' failed, nested error:
'applyMatchSplitter' failed, failed to generalize target

While it would be nice if this just worked, this is non trivial in the presence of dependent types like in this theorem. I thus propose that we at least improve the UX and present a better error than this.

Context

Verifying AIG implementations in LeanSAT

Steps to Reproduce

  1. Copy above file into live.lean-lang.org or a lake project with std dependency
  2. Observe error in split line

Expected behavior: Better error message, ideally the split works

Actual behavior: Confusing error message about split internals

Versions

"4.7.0-rc2"

Impact

Add :+1: to issues you consider important. If others are impacted by this issue, please ask them to add :+1: to it.

david-christiansen commented 2 months ago

Assuming it can't work, what about an error message like:

'split' could not generate a suitable proof because the types in the goal are too intricate.

In particular, 'split' failed because the type of $SUBTERM is:
  $TYPE