leanprover / leanprover/lean4

`BitVec.ofBoolListLE` stack overflow for large lists

Open
#13,561 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

P-low
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

BitVec.ofBoolListLE crashes due to stack overflow for large lists. The implementation seems not to be tail-recursive.

Reproduce

The following code BitVec.ofBoolListLE on a large arbitrary list of booleans and does a popcount to make sure no optimizations can affect the result. An alternative implementation of BitVec.ofBoolListLE is included, which does not crash, thus demonstrating that it's really BitVec.ofBoolListLE causing it.

import Init.Data.BitVec.Basic

/-- Tail-recursive version of `BitVec.ofBoolListLE` -/
def BitVec.ofBoolListLE' (bs : List Bool) : BitVec bs.length :=
  let val := bs.reverse.foldl (fun acc b => acc * 2 + if b then 1 else 0) 0
  BitVec.ofNat bs.length val

def someBitSeq (n : Nat) : Bool := (n * n + 3 * n) % 17 < 8

/-- Using `BitVec.ofBoolListLE` -/
def randomBitVec (n : Nat) : BitVec n :=
  let list := List.ofFn fun m : Fin n ↦ someBitSeq m.toNat
  have : list.length = n := by grind
  BitVec.cast this (.ofBoolListLE list)

/-- Using custom `BitVec.ofBoolListLE'` -/
def randomBitVec' (n : Nat) : BitVec n :=
  let list := List.ofFn fun m : Fin n ↦ someBitSeq m.toNat
  have : list.length = n := by grind
  BitVec.cast this (.ofBoolListLE' list)

def BitVec.popcount {n : Nat} (bv : BitVec n) : Nat :=
  Fin.foldl n (fun acc i => acc + if bv.getLsbD i.val then 1 else 0) 0

def main (args : List String) : IO Unit := do
  let primed  := args.contains "--primed"
  let numArgs := args.filter (· != "--primed")
  match numArgs with
  | [nStr] =>
    match nStr.toNat? with
    | none   => IO.eprintln s!"error: '{nStr}' is not a valid number"
    | some n =>
      -- Make sure result is used and cannot be optimized away
      let ones := if primed then (randomBitVec' n).popcount
                             else (randomBitVec  n).popcount
      IO.println s!"{ones}"
  | _ => IO.eprintln "usage: ofBoolListLE-SO-demo <n> [--primed]"
lean --run ofBoolListLE-SO-demo.lean 1000000

Stack overflow detected. Aborting.
Aborted (core dumped)

lean --run ofBoolListLE-SO-demo.lean 1000000 --primed
647060

lean --version
Lean (version 4.28.0, x86_64-unknown-linux-gnu, commit 7e01a1bf5c70fc6167d49c345d3bf80596e9a79b, Release)

Zulip discussion

I asked about this at #general > `BitVec.ofBoolListLE` is not tail-recursive?) but with no responses yet.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in Init.Data.BitVec.Basic and inspect the implementation of BitVec.ofBoolListLE, comparing it with the tail-recursive alternative shown in the issue. Reproduce with the provided ofBoolListLE-SO-demo.lean command using a list size of 1000000, then confirm the original behavior completes without stack overflow and produces the expected popcount.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.