FStarLang / FStarLang/FStar

String length lemma violation in the generate ocaml code !

Open
#3,296 3 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.