FStarLang / FStarLang/FStar

bitvector encoding brittle

Open
#3,903 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
F*
Stars
3.1k
Forks
266
Avg merge
21h 1m
Merged PRs (30d)
54

Description

```fstar
open FStar.BV

// let _ : bv_t 128 = bv_zero

let int2bv_uext_64_128 (x1 : nat) :
Lemma (requires x1 < pow2 64) // (FStar.UInt.size x1 64))
(ensures bv_uext #64 #64 (int2bv #64 x1) == int2bv #128 x1) =
admit ()
```
Gives:
```
* Error 276 at Basic.fst(10,0-14,10):
- Unexpected output from Z3:
"(error "line 11230 column 90: unknown function/constant BoxBitVec128")"

* Error 276 at Basic.fst(10,0-14,10):
- Unexpected output from Z3:
"(error "line 11284 column 90: unknown function/constant BoxBitVec128")"

* Error 276 at Basic.fst(10,0-14,10):
- Unexpected output from Z3:
"(error "line 11338 column 90: unknown function/constant BoxBitVec128")"

* Error 276 at Basic.fst(10,0-14,10):
- Unexpected output from Z3:
"(error "line 11394 column 90: unknown function/constant BoxBitVec128")"

* Error 276 at Basic.fst(10,0-14,10):
- Unexpected output from Z3:
"(error "line 11547 column 79: unknown function/constant BoxBitVec128")"

Verified module: Basic
5 errors were reported (see above)
```

Uncommenting the definition of that vector makes the encoding kick in.

Contributor guide

Open the contributing guide

Research direction

Start with the FStar.BV definitions and the reproducer in Basic.fst, then inspect the generated Z3 encoding around the reported BoxBitVec128 errors. Verify the case with the vector definition commented out and confirm that verification completes without unknown-function errors while preserving the stated bit-vector lemma.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.