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鈥檒l occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Bug][move-compiler-v2] recursive function type parameter checks are a little too conservative #12607

Open
brmataptos opened this issue Mar 20, 2024 · 1 comment
Assignees
Labels
bug Something isn't working compiler-v2 stale-exempt Prevents issues from being automatically marked and closed as stale

Comments

@brmataptos
Copy link
Contributor

brmataptos commented Mar 20, 2024

馃悰 Bug

Following #12360, cyclic instantiation checks are mostly right (so #12072 has been closed) but seem to have one remaining subtle problem.

The first test case in third_party/move/move-compiler-v2/tests/cyclic-instantiation-checker/v1-tests/complex_1.exp is not quite correct, as the code shifts type parameters around while traversing a recursive loop, but the types don't grow without bound.

Unless I'm wrong, the types go:

c<T1, T2> -> d<T2> -> b<u64, T2> -> c<M::S<T2>, bool> -> d<bool> -> b<u64, bool> -> c<M::S<bool>, bool> -> ...

so it stabilizes without growing much.

We could modify the error message to be more vague about why we prohibit it or ignore it for now (as obscure), but eventually should probably fix it, but it is probably nontrivial (will require some iteration and/or reasoning about the recursive type expression).

@fEst1ck
Copy link
Contributor

fEst1ck commented Mar 20, 2024

I see. Suppose we found f<T_1, T_2, ...> (T_1, T_2, are type variables) calling f<S_1, S_2, ...> (S_1, S_2, are types possibly containing the type variables). We currently use a heuristic that if any S_i properly contains any T_i, we consider it will lead to cyclic instantiations; and this is causing false positives like the one above.

The fix:
Construct a graph with nodes T_1, T_2, ...., edge T_i contains T iff S_i == T, edge T_i properly contains T iff S_i properly contains T. We then check if there is loop in the graph from T_i to itself, where at least one edge is a properly contains.

@fEst1ck fEst1ck self-assigned this Mar 21, 2024
@sausagee sausagee added the stale-exempt Prevents issues from being automatically marked and closed as stale label Mar 21, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working compiler-v2 stale-exempt Prevents issues from being automatically marked and closed as stale
Projects
Status: 馃搵 Backlog
Development

No branches or pull requests

3 participants