blob: 065d3aa7c3ca8b1c4656e3950e2f9a91960b6e1b [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
module
prelude
public import Lean.Elab.Command
public import Lean.Server.InfoUtils
import Lean.Linter.Basic
public section
set_option linter.missingDocs true -- keep it documented
/-!
This file defines style linters for the `List`/`Array`/`Vector` modules.
Currently, we do not anticipate that they will be useful elsewhere.
-/
namespace Lean.Linter.List
/--
`set_option linter.indexVariables true` enables a strict linter that
validates that the only variables appearing as an index (e.g. in `xs[i]` or `xs.take i`)
are `i`, `j`, or `k`,
and similarly that the only variables appearing as a width (e.g. in `List.replicate n a` or `Vector α n`)
are `n` or `m`.
-/
register_builtin_option linter.indexVariables : Bool := {
defValue := false
descr := "Validate that variables appearing as an index (e.g. in `xs[i]` or `xs.take i`) are only `i`, `j`, or `k`."
}
/--
`set_option linter.listVariables true` enables a strict linter that
validates that all `List`/`Array`/`Vector` variables use standardized names.
-/
register_builtin_option linter.listVariables : Bool := {
defValue := false
descr := "Validate that all `List`/`Array`/`Vector` variables use allowed names."
}
open Lean Elab Command
/--
Return the syntax for all expressions in which an `fvarId` appears as a "numerical index", along with the user name of that `fvarId`.
-/
def numericalIndices (t : InfoTree) : List (Syntax × Name) :=
(t.deepestNodes fun _ info _ => do
let stx := info.stx
if let .ofTermInfo info := info then
let idxs := match_expr info.expr with
| GetElem.getElem _ _ _ _ _ _ i _ => [i]
| GetElem?.getElem? _ _ _ _ _ _ i => [i]
| List.take _ i _ => [i]
| List.drop _ i _ => [i]
| List.set _ _ i _ => [i]
| List.insertIdx _ _ i _ => [i]
| List.eraseIdx _ _ i => [i]
| List.modify _ _ i _ => [i]
| List.zipIdx _ _ i => [i]
| Array.extract _ _ i j => [i, j]
| Array.take _ _ i => [i]
| Array.drop _ _ i => [i]
| Array.shrink _ _ i => [i]
| Array.set _ _ i _ _ => [i]
| Array.uset _ _ i _ _ => [i]
| Array.setIfInBounds _ _ i _ => [i]
| Array.insertIdx _ _ i _ _ => [i]
| Array.insertIdxIfInBounds _ _ i _ => [i]
| Array.insertIdx! _ _ i _ => [i]
| Array.eraseIdx _ _ i _ => [i]
| Array.eraseIdxIfInBounds _ _ i _ => [i]
| Array.eraseIdx! _ _ i => [i]
| Array.modify _ _ i _ => [i]
| Array.zipIdx _ _ i => [i]
| Array.swap _ _ i j _ => [i, j]
| Vector.extract _ _ _ i j => [i, j]
| Vector.take _ _ _ i => [i]
| Vector.drop _ _ _ i => [i]
| Vector.shrink _ _ _ i => [i]
| Vector.set _ _ _ i _ _ => [i]
| Vector.setIfInBounds _ _ _ i _ => [i]
| Vector.insertIdx _ _ _ i _ _ => [i]
| Vector.eraseIdx _ _ _ i _ => [i]
| Vector.insertIdx! _ _ _ i _ => [i]
| Vector.eraseIdx! _ _ _ i => [i]
| Vector.zipIdx _ _ _ i => [i]
| Vector.swap _ _ _ i j _ => [i, j]
| _ => []
match idxs with
| [] => none
| _ => idxs.filterMap fun i =>
match i with
| .fvar i =>
match info.lctx.find? i with
| some ldecl => some (stx, ldecl.userName)
| none => none
| _ => none
else
none).flatten
/--
Return the syntax for all expressions in which an `fvarId` appears as a "numerical width", along with the user name of that `fvarId`.
-/
def numericalWidths (t : InfoTree) : List (Syntax × Name) :=
(t.deepestNodes fun _ info _ => do
let stx := info.stx
if let .ofTermInfo info := info then
let idxs := match_expr info.expr with
| List.replicate _ n _ => [n]
| Array.replicate _ n _ => [n]
| Vector.replicate _ n _ => [n]
| List.range n => [n]
| List.range' _ n _ => [n]
| Array.range n => [n]
| Array.range' _ n _ => [n]
| Vector.range n => [n]
| Vector.range' _ n _ => [n]
| Vector _ n => [n]
| _ => []
match idxs with
| [] => none
| _ => idxs.filterMap fun i =>
match i with
| .fvar i =>
match info.lctx.find? i with
| some ldecl => some (stx, ldecl.userName)
| none => none
| _ => none
else
none).flatten
/--
Return the syntax for all expressions in which an `fvarId` appears as a "BitVec width", along with the user name of that `fvarId`.
-/
def bitVecWidths (t : InfoTree) : List (Syntax × Name) :=
(t.deepestNodes fun _ info _ => do
let stx := info.stx
if let .ofTermInfo info := info then
let idxs := match_expr info.expr with
| BitVec w => [w]
| _ => []
match idxs with
| [] => none
| _ => idxs.filterMap fun i =>
match i with
| .fvar i =>
match info.lctx.find? i with
| some ldecl => some (stx, ldecl.userName)
| none => none
| _ => none
else
none).flatten
/-- Strip optional suffixes from a binder name. -/
def stripBinderName (s : String) : String :=
s.dropSuffix "'" |>.dropSuffix "₁" |>.dropSuffix "₂" |>.dropSuffix "₃" |>.dropSuffix "₄" |>.copy
/-- Allowed names for index variables. -/
def allowedIndices : List String := ["i", "j", "k", "start", "stop", "step"]
/-- Allowed names for width variables. -/
def allowedWidths : List String := ["n", "m", "k", "l", "size"]
/-- Allowed names for BitVec width variables. -/
def allowedBitVecWidths : List String := ["w"]
/--
A linter which validates that the only variables used as "indices" (e.g. in `xs[i]` or `xs.take i`)
are `i`, `j`, or `k`.
-/
def indexLinter : Linter
where run := withSetOptionIn fun stx => do
-- We intentionally do not use `getLinterValue` here, as we do *not* want to opt in to `linter.all`.
unless (← getOptions).get linter.indexVariables.name false do return
if (← get).messages.hasErrors then return
if ! (← getInfoState).enabled then return
for t in ← getInfoTrees do
if let .context _ _ := t then -- Only consider info trees with top-level context
for (idxStx, n) in numericalIndices t do
if let .str _ n := n then
if !allowedIndices.contains (stripBinderName n) then
Linter.logLint linter.indexVariables idxStx
m!"Forbidden variable appearing as an index: use `i`, `j`, or `k`: {n}"
for (idxStx, n) in numericalWidths t do
if let .str _ n := n then
if !allowedWidths.contains (stripBinderName n) then
Linter.logLint linter.indexVariables idxStx
m!"Forbidden variable appearing as a width: use `n` or `m`: {n}"
for (idxStx, n) in bitVecWidths t do
if let .str _ n := n then
if !allowedBitVecWidths.contains (stripBinderName n) then
Linter.logLint linter.indexVariables idxStx
m!"Forbidden variable appearing as a BitVec width: use `w`: {n}"
builtin_initialize addLinter indexLinter
/-- Allowed names for `List` variables. -/
def allowedListNames : List String := ["l", "r", "s", "t", "tl", "ws", "xs", "ys", "zs", "as", "bs", "cs", "ds", "acc"]
/-- Allowed names for `Array` variables. -/
def allowedArrayNames : List String := ["ws", "xs", "ys", "zs", "as", "bs", "cs", "ds", "acc"]
/-- Allowed names for `Vector` variables. -/
def allowedVectorNames : List String := ["ws", "xs", "ys", "zs", "as", "bs", "cs", "ds", "acc"]
/-- Find all binders appearing in the given info tree. -/
def binders (t : InfoTree) (p : Expr → Bool := fun _ => true) : IO (List (Syntax × Name × Expr)) :=
t.collectTermInfoM fun ctx ti => do
if ti.isBinder then do
-- Something is wrong here: sometimes `inferType` fails with an unknown fvar error,
-- despite passing the local context here.
-- We fail quietly by returning a `Unit` type.
let ty ← ctx.runMetaM ti.lctx do instantiateMVars (← (Meta.inferType ti.expr) <|> pure (.const `Unit []))
if p ty.cleanupAnnotations then
if let .fvar i := ti.expr then
match ti.lctx.find? i with
| some ldecl => return some (ti.stx, ldecl.userName, ty)
| none => return none
else
return none
else
return none
else
return none
/--
A linter which validates that all `List`/`Array`/`Vector` variables use allowed names.
-/
def listVariablesLinter : Linter
where run := withSetOptionIn fun stx => do
unless (← getOptions).get linter.listVariables.name false do return
if (← get).messages.hasErrors then return
if ! (← getInfoState).enabled then return
for t in ← getInfoTrees do
if let .context _ _ := t then -- Only consider info trees with top-level context
let binders ← binders t
for (stx, n, ty) in binders.filter fun (_, _, ty) => ty.isAppOf `List do
if let .str _ n := n then
let n := stripBinderName n
if !allowedListNames.contains n then
-- Allow `L` or `xss` for `List (List α)` or `List (Array α)`
unless ((ty.getArg! 0).isAppOf `List || (ty.getArg! 0).isAppOf `Array) && (n == "L" || n == "xss") do
Linter.logLint linter.listVariables stx
m!"Forbidden variable appearing as a `List` name: {n}"
for (stx, n, ty) in binders.filter fun (_, _, ty) => ty.isAppOf `Array do
if let .str _ n := n then
let n := stripBinderName n
if !allowedArrayNames.contains n then
-- Allow `xss` for `Array (Array α)` or `Array (Vector α)`
unless ((ty.getArg! 0).isAppOf `Array || (ty.getArg! 0).isAppOf `Vector) && n == "xss" do
Linter.logLint linter.listVariables stx
m!"Forbidden variable appearing as a `Array` name: {n}"
for (stx, n, ty) in binders.filter fun (_, _, ty) => ty.isAppOf `Vector do
if let .str _ n := n then
let n := stripBinderName n
if !allowedVectorNames.contains n then
-- Allow `xss` for `Vector (Vector α)`
unless (ty.getArg! 0).isAppOf `Vector && n == "xss" do
Linter.logLint linter.listVariables stx
m!"Forbidden variable appearing as a `Vector` name: {n}"
builtin_initialize addLinter listVariablesLinter
end Lean.Linter.List