blob: 3483eedf14db7d56aac0e1ccd82fdddcbcc5639e [file]
/-
Copyright (c) 2021 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura, Joachim Breitner
-/
module
prelude
public import Lean.Meta.ForEachExpr
public section
namespace Lean.Elab.Structural
structure State where
/-- As part of the inductive predicates case, we keep adding more and more discriminants from the
local context and build up a bigger matcher application until we reach a fixed point.
As a side-effect, this creates matchers. Here we capture all these side-effects, because
the construction rolls back any changes done to the environment and the side-effects
need to be replayed. -/
addMatchers : Array (MetaM Unit) := #[]
abbrev M := StateRefT State MetaM
instance : Inhabited (M α) where
default := throwError "failed"
def run (x : M α) (s : State := {}) : MetaM (α × State) :=
StateRefT'.run x s
/--
Return true iff `e` contains an application `recFnName .. t ..` where the term `t` is
the argument we are trying to recurse on, and it contains loose bound variables.
We use this test to decide whether we should process a matcher-application as a regular
application or not. That is, whether we should push the `below` argument should be affected by the matcher or not.
If `e` does not contain an application of the form `recFnName .. t ..`, then we know
the recursion doesn't depend on any pattern variable in this matcher.
-/
def recArgHasLooseBVarsAt (recFnName : Name) (recArgPos : Nat) (e : Expr) : Bool :=
let app? := e.find? fun e =>
e.isAppOf recFnName && e.getAppNumArgs > recArgPos && (e.getArg! recArgPos).hasLooseBVars
app?.isSome
/--
Lets say we have `n` mutually recursive functions whose recursive arguments are from a group
of `m` mutually inductive data types. This mapping does not have to be one-to-one: for one type
there can be zero, one or more functions. We use the logic in the `FunPacker` modules to combine
the bodies (and motives) of multiple such functions.
Therefore we have to take the `n` functions, group them by their recursive argument's type,
and for each such type, keep track of the order of the functions.
We represent these positions as an `Array (Array Nat)`. We have that
* `positions.size = indInfo.numTypeFormers`
* `positions.flatten` is a permutation of `[0:n]`, so each of the `n` functions has exactly one
position, and each position refers to one of the `n` functions.
* if `k ∈ positions[i]` then the recursive argument of function `k` is has type `indInfo.all[i]`
(or corresponding nested inductive type)
-/
abbrev Positions := Array (Array Nat)
/--
The number of indices in the array.
-/
def Positions.numIndices (positions : Positions) : Nat :=
positions.foldl (fun s poss => s + poss.size) 0
/--
Groups the `xs` by their `f` value, and puts these groups into the order given by `ys`.
-/
def Positions.groupAndSort {α β} [Inhabited α] [DecidableEq β]
(f : α → β) (xs : Array α) (ys : Array β) : Positions :=
let positions := ys.map fun y => (Array.range xs.size).filter fun i => f xs[i]! = y
-- Sanity check: is this really a grouped permutation of all the indices?
assert! Array.range xs.size == positions.flatten.qsort Nat.blt
positions
/--
Let `positions.size = ys.size` and `positions.numIndices = xs.size`. Maps `f` over each `y` in `ys`,
also passing in those elements `xs` that belong to that are those elements of `xs` that belong to
`y` according to `positions`.
-/
def Positions.mapMwith {α β m} [Monad m] [Inhabited β] (f : α → Array β → m γ)
(positions : Positions) (ys : Array α) (xs : Array β) : m (Array γ) := do
assert! positions.size = ys.size
assert! positions.numIndices = xs.size
ys.zipWithM (bs := positions) fun y poss => f y (poss.map (xs[·]!))
end Lean.Elab.Structural
builtin_initialize
Lean.registerTraceClass `Elab.definition.structural