Add a safe wrapper around `ptrEq`
@zwarich is already working on this.
Since May 19, 2025.
- Dominant language
- Lean
- Stars
- 9.2k
- Forks
- 990
- Avg merge
- 1d 17h
- Merged PRs (30d)
- 175
Description
We want to use pointer equality as a performance optimization. For example, as a first check in DecidableEq instances: if the two arguments are pointer-equal, then we can immediately return isTrue. However ptrEq is unsafe, and every time it is used via implementedBy we potentially introduce bugs. Therefore we want a safe wrapper around ptrEq. There are several issues to consider:
ptrEqis not compatible with equality.ptrEq a awill always return true, butptrEq a bmay return false even ifa = b. This is easy to address by either using a CPS-style definition or wrapping the result in a quotient likesafePtrEq (a b : α) : Squash Bool.- We need some information about the result of
ptrEqbeyond the fact that it is a Boolean, so that we can concludea = bifptrEq a breturns true. This is also straightforward to encode, e.g. withsafePtrEq (a b : α) : Squash { b : Bool // b → a = b }. - In general,
ptrEq a bdoes not implya = b.
Number (3) causes the withPtrEq function in core to be unsafe:
withPtrEq {α : Type u} (a b : α) (k : Unit → Bool) (h : a = b → k () = true) : Bool
The problem is that it is very easy to construct provably different Lean terms that evaluate to identical VM objects. In hindsight, this is an obvious effect of erasure and common subexpression elimination. The following are some concrete examples:
@[simp] theorem Bool_ne_Empty : Bool ≠ Empty :=
(Empty.rec <| · ▸ true)
-- 1) Types are erased, so ptrEq will always claim that they are equal:
def problem1 := withPtrEq Bool Empty (fun _ => false) (by simp)
#reduce problem1 -- false
#eval problem1 -- true
-- 2) This works even if we're not directly comparing types, but also when
-- they're nested in a heap value (due to CSE).
def problem2 := withPtrEq (Bool, 1) (Empty, 1) (fun _ => false) (by simp)
#reduce problem2 -- false
#eval problem2 -- true
Potential fixes:
- Cripple the compiler to never do CSE after erasure, and have
withPtrEqreturn false if one of the arguments isbox(0). (Only mentioned for completeness, I don't think this is a good idea.) - Add a type class
class InjectiveVMRepr (α : Sort u) : Prop where private mk ::, auto-generate instances for inductives and structures that are safe to compare withptrEq, and add an additional[InjectiveVMRepr α]argument towithPtrEq. Unfortunately it is not possible to useunsafefor such Rust-style "marker traits", because we need to proveNonempty (InjectiveVMRepr α)to define the safe instances. - Add a type class
SafePtrEqwith asafePtrEq (a b : α) : Squash { b : Bool // b → a = b }operation. This has the downside of increasing the compiled code size (due to monomorphization), and we can't define instances like[SafePtrEq α] → SafePtrEq (Array α).
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.