Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

@tailcall annotation doesn't show warning for non-tailcall #7856

Open
vicuna opened this issue Sep 27, 2018 · 4 comments

Comments

Projects
None yet
3 participants
@vicuna
Copy link

commented Sep 27, 2018

Original bug ID: 7856
Reporter: @edwintorok
Status: new
Resolution: open
Priority: normal
Severity: minor
Platform: x86-64
OS: Ubuntu
OS Version: 18.04
Version: 4.07.0
Category: language features
Monitored by: @nojb @gasche @yallop

Bug description

When calling loop inside List.iter the compiler doesn't recognize that this call is not a tailcall, even when annotated with the @tailcall attribute.

Steps to reproduce

cat >testme.ml <<EOF
let rec loop () = List.iter (fun _ -> (loop[@tailcall]) ()) [1; 2];;
let rec loop2 () = try (loop2[@tailcall]) () with _ -> ();
EOF
ocamlc -w A testme.ml

Actual output:
File "testme.ml", line 2, characters 23-44:
Warning 51: expected tailcall

Expected output:
File "testme.ml", line 1, characters ...:
Warning 51: expected tailcall
File "testme.ml", line 2, characters 23-44:
Warning 51: expected tailcall

Additional information

Reproduced on OCaml 4.06.1 and OCaml 4.07.0

For a real life use case where this would've been useful see this pull request where we tried to add @tailcall to detect issues like this in the future but it didn't work:
xenserver/rrdd-plugins#51

@vicuna

This comment has been minimized.

Copy link
Author

commented Sep 27, 2018

Comment author: @nojb

I think current behavior is correct: in the first case loop is indeed in tail position: it is (fun _ -> ...) which is not.

@vicuna

This comment has been minimized.

Copy link
Author

commented Sep 27, 2018

Comment author: @edwintorok

Fair enough, what we actually wanted to know here is: is this recursive call guaranteed to not consume more stack space (including stack space already consumed by its immediate callers)?

Would be nice if there was another attribute that checked the tailcall property of all callers up to the recursive function itself: that might've helped catch bugs like this (we could manually add those annotations, but it would be error-prone when the code around it changes). This might not be easy to do, but if such an attribute is added it could err on the side of caution: if it cannot prove that the call doesn't consume more stack space, then it warns.

I think this would even work for recursive calls in Lwt, e.g.:
let rec foo =
some_action () >>= fun v ->
loop v

which would be equivalent to:
let rec foo =
(>>=) (some_action ()) (fun v -> (loop [@recnostack]) v)

(fun v -> (loop[@recnostack]) v) --> OK, tail position, adds [@recnostack] annotation to (>>=) internally
(>>=) ... ... ---> OK tail position
let rec foo = ... -> OK we reached the function itself

(Of course you can still have an infinite loop that doesn't overflow the stack, but that is outside of scope for a compiler warning)

What do you think?

@xavierleroy

This comment has been minimized.

Copy link
Contributor

commented Mar 16, 2019

As I understand it, the proposed @recnostack warning would need whole-program static analysis and can't be done with the information that the compiler has at its disposal. I move to close this feature wish, unless @edwintorok disagrees.

@edwintorok

This comment has been minimized.

Copy link
Contributor

commented Mar 16, 2019

Feel free to close this issue, perhaps a warning in the documentation would suffice:
"The tailcall attribute does not guarantee that stack usage has a finite upper bound. Indeed it is possible to have a stack overflow with a tailcall if there are other non-tail function calls inbetween."

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.