String length lemma violation in the generate ocaml code !
- Dominant language
- F*
- Stars
- 3.1k
- Forks
- 266
- Avg merge
- 21h 1m
- Merged PRs (30d)
- 54
Description
We were testing out some of the **ulib** ocaml library function for strings generated from its Fstar implementation. For [length](https://github.com/FStarLang/FStar/blob/60844c6deb4501d4808908a434f113a7800a722f/ulib/FStar.String.fsti#L55) and [concat](https://github.com/FStarLang/FStar/blob/60844c6deb4501d4808908a434f113a7800a722f/ulib/FStar.String.fsti#L76)(^) functions, we found a test input which violates the lemma "length (s1 ^ s2) = length s1 + length s2"
Below is an ocaml example to reproduce this. We tried running it on the latest FStar version.
```ocaml
open FStar_String
let target s1 s2 =
let s1_len = (FStar_String.length s1) in
let s2_len = (FStar_String.length s2) in
let s1s2_len = (FStar_String.strlen (FStar_String.strcat s1 s2)) in
Printf.printf "s1_len: %d\n" (Z.to_int s1_len);
Printf.printf "s2_len: %d\n" (Z.to_int s2_len);
Printf.printf "s1s2_len: %d\n" (Z.to_int s1s2_len);
if s1s2_len <> (Z.add s1_len s2_len) then
failwith "check failed: (strlen (concat s1 s2)) = (strlen s1) + (strlen s2)"
let () = target "{\163" "\004"
```
Output:
```txt
s1_len: 2
s2_len: 1
s1s2_len: 2
Fatal error: exception Failure("check failed: (strlen (concat s1 s2)) = (strlen s1) + (strlen s2)")
```
The length of the concated string should be 3 but instead it computes 2 which violates the lemma.
Contributor guide
Research direction
Read ulib/FStar.String.fsti at the linked length and concat definitions, then run the provided OCaml reproducer with the shown inputs. Trace how these functions are represented in generated OCaml and identify why the concatenated length is 2 instead of 3. Done means the reported lemma holds for this reproduction.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- ocaml
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100