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

-principal causes loop in type checker when compiling #7305

Closed
vicuna opened this issue Jul 26, 2016 · 9 comments

Comments

Projects
None yet
2 participants
@vicuna
Copy link

commented Jul 26, 2016

Original bug ID: 7305
Reporter: @avsm
Assigned to: @garrigue
Status: closed (set by @xavierleroy on 2017-09-24T15:33:17Z)
Resolution: fixed
Priority: normal
Severity: crash
Version: 4.03.0
Fixed in version: 4.04.0 +dev / +beta1 / +beta2
Category: typing

Bug description

When compiling Cohttp (which uses -principal, but several of its dependent libraries do not), the type checker goes into an infinite loop:

frame #44: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #45: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #46: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #47: 0x00000001000823c3 ocamlc.opt`camlBtype__iter_type_expr_5283 + 387
frame #48: 0x00000001000c1802 ocamlc.opt`camlCtype__closed_schema_rec_39833 + 306
frame #49: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #50: 0x00000001000823c3 ocamlc.opt`camlBtype__iter_type_expr_5283 + 387
frame #51: 0x00000001000c1802 ocamlc.opt`camlCtype__closed_schema_rec_39833 + 306
frame #52: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #53: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #54: 0x00000001000822c4 ocamlc.opt`camlBtype__iter_type_expr_5283 + 132
frame #55: 0x00000001000823c3 ocamlc.opt`camlBtype__iter_type_expr_5283 + 387
frame #56: 0x00000001000c1802 ocamlc.opt`camlCtype__closed_schema_rec_39833 + 306
frame #57: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #58: 0x00000001000823c3 ocamlc.opt`camlBtype__iter_type_expr_5283 + 387
frame #59: 0x00000001000c1802 ocamlc.opt`camlCtype__closed_schema_rec_39833 + 306
frame #60: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #61: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #62: 0x00000001000823c3 ocamlc.opt`camlBtype__iter_type_expr_5283 + 387
frame #63: 0x00000001000c1802 ocamlc.opt`camlCtype__closed_schema_rec_39833 + 306
frame #64: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #65: 0x00000001000823c3 ocamlc.opt`camlBtype__iter_type_expr_5283 + 387
frame #66: 0x00000001000c1802 ocamlc.opt`camlCtype__closed_schema_rec_39833 + 306
frame #67: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #68: 0x00000001000c198b ocamlc.opt`camlCtype__closed_schema_39842 + 123
frame #69: 0x00000001001467f1 ocamlc.opt`camlTypemod__check_nongen_scheme_9977 + 49
frame #70: 0x00000001001a4351 ocamlc.opt`camlList__iter_1258 + 33
frame #71: 0x000000010014911b ocamlc.opt`camlTypemod__type_implementation_15412 + 1099
frame #72: 0x0000000100027345 ocamlc.opt`camlTimings__time_1383 + 37
frame #73: 0x000000010001c169 ocamlc.opt`camlCompile__implementation_1807 + 569
frame #74: 0x0000000100004e1b ocamlc.opt`camlMain__process_implementation_file_1555 + 43
frame #75: 0x00000001001c978f ocamlc.opt`camlArg__parse_argv_dynamic_1326 + 1087
frame #76: 0x00000001001c9961 ocamlc.opt`camlArg__parse_2381 + 257
frame #77: 0x000000010000604e ocamlc.opt`camlMain__main_2319 + 110
frame #78: 0x0000000100027345 ocamlc.opt`camlTimings__time_1383 + 37
frame #79: 0x00000001000074db ocamlc.opt`camlMain__entry + 4315
frame #80: 0x0000000100001889 ocamlc.opt`caml_program + 1961
frame #81: 0x00000001001fd960 ocamlc.opt`caml_start_program + 92
frame #82: 0x00000001001e7ef7 ocamlc.opt`caml_main + 483
frame #83: 0x00000001001e7f3d ocamlc.opt`main + 12
frame #84: 0x00007fff942735ad libdyld.dylib`start + 1

It compiles fine when -principal is removed

Steps to reproduce

opam install js_of_ocaml cohttp
opam source cohttp
cd
make TESTS=--enable-tests
lldb ocamlc.optprocess launch -- -verbose -principal -I /Users/avsm/.opam/system/lib/bytes -I /Users/avsm/.opam/system/lib/js_of_ocaml -I /Users/avsm/.opam/system/lib/lwt -I /Users/avsm/.opam/system/lib/stringext -I /Users/avsm/.opam/system/lib/sexplib -I /Users/avsm/.opam/system/lib/re -I /Users/avsm/.opam/system/lib/uri -I /Users/avsm/.opam/system/lib/fieldslib -I /Users/avsm/.opam/system/lib/base64 -I /Users/avsm/.opam/system/lib/cohttp -ppx /Users/avsm/.opam/system/lib/js_of_ocaml/./ppx_js -ppx ppx_lwt lib_test/test_xhr.ml

@vicuna

This comment has been minimized.

Copy link
Author

commented Jul 26, 2016

Comment author: @avsm

More details at ocsigen/js_of_ocaml#503

@vicuna

This comment has been minimized.

Copy link
Author

commented Jul 26, 2016

Comment author: @avsm

Confirmed to only happen on 4.03.0 and not on 4.02.3

@vicuna

This comment has been minimized.

Copy link
Author

commented Jul 28, 2016

Comment author: @garrigue

Is it possible to get a reduction of this bug?

Debugging the typer on code involving large libraries is extremely painful.
Usually, the reason can be compressed into a few lines (in my experience, less than 20) of self-contained code.

@vicuna

This comment has been minimized.

Copy link
Author

commented Jul 28, 2016

Comment author: @mshinwell

Leo will investigate making a smaller reproduction case.

@vicuna

This comment has been minimized.

Copy link
Author

commented Aug 1, 2016

Comment author: @lpw25

This seems to be caused by the fix for #5663.

I haven't been able to pin down the exact cause, so I don't have a small reproduction case, but essentially the change for #5663 introduced expansion of type constructors when checking if a compilations unit's type was closed or not.

Doing expansion creates fresh types, which is why the check can loop forever. It normally doesn't because of the memoization of expansion, but that is not completely reliable so I don't think it is a good idea for the correctness of this function to depend on it.

This explains the difference between with -principal and without, since principal does less memoization of type expansion. Although even without -principal this check is very expensive on the large class types used in js_of_ocaml -- and seems completely unnecessary since the original type is something like:

string -> Dom.html_element Js.t

which is trivially closed.

@vicuna

This comment has been minimized.

Copy link
Author

commented Aug 2, 2016

Comment author: @garrigue

I have created a pull request with a fix.
#734
It only expands when there is a free variable (like for the occur check).

Leo, could you check that it indeed solves the problem?

Note that the fact it doesn't stop is disturbing, because memoization of expansions should be reliable (the correctness of the type checker relies on it). So there may be a deeper bug somewhere.

@vicuna

This comment has been minimized.

Copy link
Author

commented Aug 2, 2016

Comment author: @garrigue

By the way, this is a new example of a bug that could have been found early on if we had a way of tracking changes in execution performance of the compiler.

@vicuna

This comment has been minimized.

Copy link
Author

commented Aug 2, 2016

Comment author: @lpw25

memoization of expansions should be reliable (the correctness of the type checker relies on it)

Interesting, I had always assumed it was just an optimisation.

Having investigated further, I think that the code is not actually in an infinite loop. I think the algorithm is just exponential nested structural types. Which leads me to the following reproduction case:

type t1 =
< meth1: int;
meth2: int;
meth3: int;
meth4: int;
meth5: int;
meth6: int;
meth7: int;
meth8: int;
meth9: int;
meth10: int;
meth11: int;
meth12: int;
meth13: int;
meth14: int;
meth15: int;
meth16: int;
meth17: int;
meth18: int;
meth19: int;
meth20: int; >

type t2 =
< meth1: t1;
meth2: t1;
meth3: t1;
meth4: t1;
meth5: t1;
meth6: t1;
meth7: t1;
meth8: t1;
meth9: t1;
meth10: t1;
meth11: t1;
meth12: t1;
meth13: t1;
meth14: t1;
meth15: t1;
meth16: t1;
meth17: t1;
meth18: t1;
meth19: t1;
meth20: t1; >

type t3 =
< meth1: t2;
meth2: t2;
meth3: t2;
meth4: t2;
meth5: t2;
meth6: t2;
meth7: t2;
meth8: t2;
meth9: t2;
meth10: t2;
meth11: t2;
meth12: t2;
meth13: t2;
meth14: t2;
meth15: t2;
meth16: t2;
meth17: t2;
meth18: t2;
meth19: t2;
meth20: t2; >

type t4 =
< meth1: t3;
meth2: t3;
meth3: t3;
meth4: t3;
meth5: t3;
meth6: t3;
meth7: t3;
meth8: t3;
meth9: t3;
meth10: t3;
meth11: t3;
meth12: t3;
meth13: t3;
meth14: t3;
meth15: t3;
meth16: t3;
meth17: t3;
meth18: t3;
meth19: t3;
meth20: t3; >

type t5 =
< meth1: t4;
meth2: t4;
meth3: t4;
meth4: t4;
meth5: t4;
meth6: t4;
meth7: t4;
meth8: t4;
meth9: t4;
meth10: t4;
meth11: t4;
meth12: t4;
meth13: t4;
meth14: t4;
meth15: t4;
meth16: t4;
meth17: t4;
meth18: t4;
meth19: t4;
meth20: t4; >

type t6 =
< meth1: t5;
meth2: t5;
meth3: t5;
meth4: t5;
meth5: t5;
meth6: t5;
meth7: t5;
meth8: t5;
meth9: t5;
meth10: t5;
meth11: t5;
meth12: t5;
meth13: t5;
meth14: t5;
meth15: t5;
meth16: t5;
meth17: t5;
meth18: t5;
meth19: t5;
meth20: t5; >

type t7 =
< meth1: t6;
meth2: t6;
meth3: t6;
meth4: t6;
meth5: t6;
meth6: t6;
meth7: t6;
meth8: t6;
meth9: t6;
meth10: t6;
meth11: t6;
meth12: t6;
meth13: t6;
meth14: t6;
meth15: t6;
meth16: t6;
meth17: t6;
meth18: t6;
meth19: t6;
meth20: t6; >

type t8 =
< meth1: t7;
meth2: t7;
meth3: t7;
meth4: t7;
meth5: t7;
meth6: t7;
meth7: t7;
meth8: t7;
meth9: t7;
meth10: t7;
meth11: t7;
meth12: t7;
meth13: t7;
meth14: t7;
meth15: t7;
meth16: t7;
meth17: t7;
meth18: t7;
meth19: t7;
meth20: t7; >

let x : t8 list = []

The compiler is killed by the kernel for using too much memory when I try to compile this file with -principal.

@vicuna

This comment has been minimized.

Copy link
Author

commented Aug 3, 2016

Comment author: @garrigue

Fixed in 4.04 by commit b65078c.

Note that I only checked the effect by a small reduction test,
in tests/typing-module-bugs/pr7305_principal.ml.
You should check that it applies to the original code base.

pr7305_principal.ml:
type c1 = < c1: c1 >
type c2 = < c1: c1; c2: c1; c3: c1; c4: c1; c5: c1; c6: c1 >
type c3 = < c1: c2; c2: c2; c3: c2; c4: c2; c5: c2; c6: c2 >
type c4 = < c1: c3; c2: c3; c3: c3; c4: c3; c5: c3; c6: c3 >
type c5 = < c1: c4; c2: c4; c3: c4; c4: c4; c5: c4; c6: c4 >
type c6 = < c1: c5; c2: c5; c3: c5; c4: c5; c5: c5; c6: c5 >
type c7 = < c1: c6; c2: c6; c3: c6; c4: c6; c5: c6; c6: c6 >

let x = ref ([] : c7 list)

@vicuna vicuna closed this Sep 24, 2017

@vicuna vicuna added the typing label Mar 14, 2019

@vicuna vicuna added the bug label Mar 20, 2019

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.