blob: b75ad989254adce289e896770175b4233b4184b2 [file]
/-
Copyright (c) 2025 Amazon.com, Inc. or its affiliates. All Rights Reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
module
prelude
public import Lean.Meta.DiscrTree.Types
public import Lean.CoreM
import Init.Data.Range.Polymorphic.Iterators
import Init.Omega
public section
namespace Lean.Meta.DiscrTree
def mkNoindexAnnotation (e : Expr) : Expr :=
mkAnnotation `noindex e
def hasNoindexAnnotation (e : Expr) : Bool :=
annotation? `noindex e |>.isSome
instance : Inhabited (Trie α) where
default := .node #[] #[]
instance : Inhabited (DiscrTree α) where
default := {}
def empty : DiscrTree α := { root := {} }
instance : ToExpr Key where
toTypeExpr := mkConst ``Key
toExpr k := match k with
| .const n a => mkApp2 (mkConst ``Key.const) (toExpr n) (toExpr a)
| .fvar id a => mkApp2 (mkConst ``Key.fvar) (toExpr id) (toExpr a)
| .lit l => mkApp (mkConst ``Key.lit) (toExpr l)
| .star => mkConst ``Key.star
| .other => mkConst ``Key.other
| .arrow => mkConst ``Key.arrow
| .proj n i a => mkApp3 (mkConst ``Key.proj) (toExpr n) (toExpr i) (toExpr a)
def Key.lt : Key → Key → Bool
| .lit v₁, .lit v₂ => v₁ < v₂
| .fvar n₁ a₁, .fvar n₂ a₂ => Name.quickLt n₁.name n₂.name || (n₁ == n₂ && a₁ < a₂)
| .const n₁ a₁, .const n₂ a₂ => Name.quickLt n₁ n₂ || (n₁ == n₂ && a₁ < a₂)
| .proj s₁ i₁ a₁, .proj s₂ i₂ a₂ => Name.quickLt s₁ s₂ || (s₁ == s₂ && i₁ < i₂) || (s₁ == s₂ && i₁ == i₂ && a₁ < a₂)
| k₁, k₂ => k₁.ctorIdx < k₂.ctorIdx
instance : LT Key := ⟨fun a b => Key.lt a b⟩
instance (a b : Key) : Decidable (a < b) := inferInstanceAs (Decidable (Key.lt a b))
def Key.format : Key → Format
| .star => "*"
| .other => "◾"
| .lit (.natVal v) => Std.format v
| .lit (.strVal v) => repr v
| .const k _ => Std.format k
| .proj s i _ => Std.format s ++ "." ++ Std.format i
| .fvar k _ => Std.format k.name
| .arrow => "∀"
instance : ToFormat Key := ⟨Key.format⟩
partial def Trie.format [ToFormat α] : Trie α → Format
| .node vs cs => Format.group $ Format.paren $
"node" ++ (if vs.isEmpty then Format.nil else " " ++ Std.format vs)
++ Format.join (cs.toList.map fun ⟨k, c⟩ => Format.line ++ Format.paren (Std.format k ++ " => " ++ format c))
instance [ToFormat α] : ToFormat (Trie α) := ⟨Trie.format⟩
partial def format [ToFormat α] (d : DiscrTree α) : Format :=
let (_, r) := d.root.foldl
(fun (p : Bool × Format) k c =>
(false, p.2 ++ (if p.1 then Format.nil else Format.line) ++ Format.paren (Std.format k ++ " => " ++ Std.format c)))
(true, Format.nil)
Format.group r
instance [ToFormat α] : ToFormat (DiscrTree α) := ⟨format⟩
/--
Helper function for converting an entry (i.e., `Array Key`) to the discrimination tree into
`MessageData` that is more user-friendly. We use this function to implement diagnostic information.
-/
partial def keysAsPattern (keys : Array Key) : CoreM MessageData := do
go (parenIfNonAtomic := false) |>.run' keys.toList
where
next? : StateRefT (List Key) CoreM (Option Key) := do
let key :: keys ← get | return none
set keys
return some key
mkApp (f : MessageData) (args : Array MessageData) (parenIfNonAtomic : Bool) : CoreM MessageData := do
if args.isEmpty then
return f
else
let mut r := m!""
for arg in args do
r := r ++ Format.line ++ arg
r := f ++ .nest 2 r
if parenIfNonAtomic then
return .paren r
else
return .group r
go (parenIfNonAtomic := true) : StateRefT (List Key) CoreM MessageData := do
let some key ← next? | return .nil
match key with
| .const declName nargs =>
mkApp m!"{← mkConstWithLevelParams declName}" (← goN nargs) parenIfNonAtomic
| .fvar fvarId nargs =>
mkApp m!"{mkFVar fvarId}" (← goN nargs) parenIfNonAtomic
| .proj _ i nargs =>
mkApp m!"{← go}.{i+1}" (← goN nargs) parenIfNonAtomic
| .arrow =>
mkApp m!"∀ " (← goN 1) parenIfNonAtomic
| .star => return "_"
| .other => return "<other>"
| .lit (.natVal v) => return m!"{v}"
| .lit (.strVal v) => return m!"{v}"
goN (num : Nat) : StateRefT (List Key) CoreM (Array MessageData) := do
let mut r := #[]
for _ in *...num do
r := r.push (← go)
return r
private partial def createNodes (keys : Array Key) (v : α) (i : Nat) : Trie α :=
if h : i < keys.size then
let k := keys[i]
let c := createNodes keys v (i+1)
.node #[] #[(k, c)]
else
.node #[v] #[]
/--
If `vs` contains an element `v'` such that `v == v'`, then replace `v'` with `v`.
Otherwise, push `v`.
See issue #2155
Recall that `BEq α` may not be Lawful.
-/
private def insertVal [BEq α] (vs : Array α) (v : α) : Array α :=
loop 0
where
loop (i : Nat) : Array α :=
if h : i < vs.size then
if v == vs[i] then
vs.set i v
else
loop (i+1)
else
vs.push v
termination_by vs.size - i
private partial def insertAux [BEq α] (keys : Array Key) (v : α) : Nat → Trie α → Trie α
| i, .node vs cs =>
if h : i < keys.size then
let k := keys[i]
let c := Id.run $ cs.binInsertM
(fun a b => a.1 < b.1)
(fun ⟨_, s⟩ => let c := insertAux keys v (i+1) s; (k, c)) -- merge with existing
(fun _ => let c := createNodes keys v (i+1); (k, c))
(k, default)
.node vs c
else
.node (insertVal vs v) cs
def insertKeyValue [BEq α] (d : DiscrTree α) (keys : Array Key) (v : α) : DiscrTree α :=
if keys.isEmpty then panic! "invalid key sequence"
else
let k := keys[0]!
match d.root.find? k with
| none =>
let c := createNodes keys v 1
{ root := d.root.insert k c }
| some c =>
let c := insertAux keys v 1 c
{ root := d.root.insert k c }
@[deprecated insertKeyValue (since := "2026-01-02")]
def insertCore [BEq α] (d : DiscrTree α) (keys : Array Key) (v : α) : DiscrTree α :=
insertKeyValue d keys v
end Lean.Meta.DiscrTree