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

"β t is less general than ∀α. α t" with trunk #13176

Closed
kit-ty-kate opened this issue May 16, 2024 · 14 comments
Closed

"β t is less general than ∀α. α t" with trunk #13176

kit-ty-kate opened this issue May 16, 2024 · 14 comments

Comments

@kit-ty-kate
Copy link
Member

A new error I'm seeing with trunk is this one:

#=== ERROR while compiling ocf.0.8.0 ==========================================#
# context              2.2.0~beta3~dev | linux/x86_64 | ocaml-variants.5.3.0+trunk | file:///home/opam/opam-repository
# path                 ~/.opam/5.3/.opam-switch/build/ocf.0.8.0
# command              ~/.opam/5.3/bin/dune build -p ocf -j 1 --promote-install-files=false @install
# exit-code            1
# env-file             ~/.opam/log/ocf-20-78462e.env
# output-file          ~/.opam/log/ocf-20-78462e.out
### output ###
# (cd _build/default && /home/opam/.opam/5.3/bin/ocamlopt.opt -g -w -40 -bin-annot -w -6-7-9-10-27-32-33-34-35-36-50-52 -no-strict-sequence -g -I lib/.ocf.objs/byte -I lib/.ocf.objs/native -I /home/opam/.opam/5.3/lib/seq -I /home/opam/.opam/5.3/lib/yojson -intf-suffix .ml -no-alias-deps -o lib/.ocf.objs/native/ocf.cmx -c -impl lib/ocf.ml)
# File "lib/ocf.ml", line 215, characters 16-33:
# 215 |     { wrapper = Obj.magic wrapper ;
#                       ^^^^^^^^^^^^^^^^^
# Error: This field value has type "'b wrapper" which is less general than
#          "'a. 'a wrapper"
# (cd _build/default && /home/opam/.opam/5.3/bin/ocamlc.opt -g -w -40 -bin-annot -w -6-7-9-10-27-32-33-34-35-36-50-52 -no-strict-sequence -g -bin-annot -I lib/.ocf.objs/byte -I /home/opam/.opam/5.3/lib/seq -I /home/opam/.opam/5.3/lib/yojson -intf-suffix .ml -no-alias-deps -o lib/.ocf.objs/byte/ocf.cmo -c -impl lib/ocf.ml)
# File "lib/ocf.ml", line 215, characters 16-33:
# 215 |     { wrapper = Obj.magic wrapper ;
#                       ^^^^^^^^^^^^^^^^^
# Error: This field value has type "'b wrapper" which is less general than
#          "'a. 'a wrapper"

I'm a bit surprised to see that Obj.magic is no longer the catch-all of the type-system. Is that expected?

@kit-ty-kate
Copy link
Member Author

another package typerep also fails the same way:

#=== ERROR while compiling typerep.v0.16.0 ====================================#
# context              2.2.0~beta3~dev | linux/x86_64 | ocaml-variants.5.3.0+trunk | file:///home/opam/opam-repository
# path                 ~/.opam/5.3/.opam-switch/build/typerep.v0.16.0
# command              ~/.opam/5.3/bin/dune build -p typerep -j 1
# exit-code            1
# env-file             ~/.opam/log/typerep-20-69595c.env
# output-file          ~/.opam/log/typerep-20-69595c.out
### output ###
# (cd _build/default && /home/opam/.opam/5.3/bin/ocamlopt.opt -w -40 -g -I lib/.typerep_lib.objs/byte -I lib/.typerep_lib.objs/native -I /home/opam/.opam/5.3/lib/base -I /home/opam/.opam/5.3/lib/base/base_internalhash_types -I /home/opam/.opam/5.3/lib/base/caml -I /home/opam/.opam/5.3/lib/base/shadow_stdlib -I /home/opam/.opam/5.3/lib/sexplib0 -intf-suffix .ml -no-alias-deps -open Typerep_lib -o lib/.typerep_lib.objs/native/typerep_lib__Typename.cmx -c -impl lib/typename.ml)
# File "lib/typename.ml", line 214, characters 41-66:
# 214 |     if Uid.equal uid_a uid_b then { eq = Obj.magic Type_equal.refl } else fail uid_a uid_b
#                                                ^^^^^^^^^^^^^^^^^^^^^^^^^
# Error: This field value has type "('b A.t, 'b B.t) Typerep_lib.Type_equal.t"
#        which is less general than
#          "'a. ('a A.t, 'a B.t) Typerep_lib.Type_equal.t"
# (cd _build/default && /home/opam/.opam/5.3/bin/ocamlc.opt -w -40 -g -bin-annot -I lib/.typerep_lib.objs/byte -I /home/opam/.opam/5.3/lib/base -I /home/opam/.opam/5.3/lib/base/base_internalhash_types -I /home/opam/.opam/5.3/lib/base/caml -I /home/opam/.opam/5.3/lib/base/shadow_stdlib -I /home/opam/.opam/5.3/lib/sexplib0 -intf-suffix .ml -no-alias-deps -open Typerep_lib -o lib/.typerep_lib.objs/byte/typerep_lib__Typename.cmo -c -impl lib/typename.ml)
# File "lib/typename.ml", line 214, characters 41-66:
# 214 |     if Uid.equal uid_a uid_b then { eq = Obj.magic Type_equal.refl } else fail uid_a uid_b
#                                                ^^^^^^^^^^^^^^^^^^^^^^^^^
# Error: This field value has type "('b A.t, 'b B.t) Typerep_lib.Type_equal.t"
#        which is less general than
#          "'a. ('a A.t, 'a B.t) Typerep_lib.Type_equal.t"

@Octachron
Copy link
Member

The trunk behavior is correct: Obj.magic x is a computation and thus subject to the value restriction.
You can check that:

let ignore: _ -> unit = Obj.magic ignore

doesn't yield a polymorphic type in any version of OCaml.

@kit-ty-kate
Copy link
Member Author

ok good to know. What would be the best way to fix those packages?

@yallop
Copy link
Member

yallop commented May 16, 2024

The trunk behavior is correct

Right, and the pre-trunk behaviour is unsound (and has been for a long time). Here's a program showing the issue:

type t = {x : 'a. 'a list ref }
let {x} = {x = Obj.magic ref []}
let () = x := [0]; print_endline (List.hd !x)

This example is rejected by trunk, but produces a segmentation fault in 5.2.0 and earlier versions.

@Octachron
Copy link
Member

Well, the best way would be that they stop using Obj.magic, or at least review if they still need it.

The hackish way is to embrace their brokenness and simply extrudes the Obj.magic which creates a value of type 'a.'a which can be instantiated to the expected type:

type t = {x : 'a. 'a list ref }
let {x} = let x = Obj.magic ref [] in {x}

@gasche
Copy link
Member

gasche commented May 16, 2024

Out of curiosity, do we know what change in the type-checker resulted in this change in behavior on user code?

(Note: In some cases Obj.magic foo can still be generalized thanks to the relaxed value restriction -- covariant occurrences are generalized. None of the examples cited above are in this relaxed situation.)

@Octachron
Copy link
Member

Octachron commented May 16, 2024

This is the consequence of #12932 which removed a special treatment for typing record label.
For instance, taking the original example from #4862

type t = {f: 'a. ('a list -> int) Lazy.t}
let l : t = { f = lazy (raise Not_found)}

and adapting it to take in account that lazy is considered pure nowadays:

let not_lazy x = lazy x
let l : t = { f = not_lazy (raise Not_found)}

fails in trunk-only with

Error: This field value has type ('b list -> int) Lazy.t
       which is less general than 'a. ('a list -> int) Lazy.t

@gasche
Copy link
Member

gasche commented May 16, 2024

Hmm. Let me make sure I understand things correctly:

  • the PR Remove subsumed fix for #4862 #12932 by @garrigue was introduced as "removing type-checking logic that is now useless"
  • bad news! in fact it breaks code in the wild (so the logic we removed was doing something)
  • good news! in fact the code we break was unsound, the unexpected change in behavior silently fixed an unsoundness bug that we did not know about (... but that was used in the wild to avoid type-checking)

We should fire the reviewer of #12932 which did not catch any of this circus (let me explain the joke: I reviewed that PR), and maybe triple-check that the testsuite correctly covers both the desirable examples that we want to accept (from #4862) and the undesirable examples that we are now right to reject.

@yallop
Copy link
Member

yallop commented May 16, 2024

examples that we are now right to reject

We're right to reject them according to the generalization rules of the type checker, but those rules aren't doing anything valuable by rejecting the code in question. There's no additional safety gained by not generalizing the result of calls to Obj.magic because it's always possible to write code that behaves equivalently to the generalized version by first coercing to a polymorphic record type and then obtaining the polymorphic value via projection.

In other words, while the following code is prohibited:

let r : 'a. 'a list ref = Obj.magic (ref [])

the following essentially equivalent code is permitted:

type t = {x:'a.'a list ref}[@@unboxed]
let q = Obj.magic (ref [])
let r : 'a. 'a list ref = q.x

and it's probably possible to fix up the newly-broken opam packages in the PR description with a similar change.

@gasche
Copy link
Member

gasche commented May 16, 2024

In general I agree that it would soundness-preserving to treat Obj.magic <...> as pure/non-expansive. You did not exactly suggest that we should do it, but I am not sure that I would be convinced by the suggestion. Firstly, it requires changes in the compiler to special-case this primitive (which is currently just a call to an external function). More importantly, some use-cases that we see in the wild look a bit dubious to me, for example the usage in ocf.ml is probably code that should have been forced to be written differently in the first place: https://framagit.org/zoggy/ocf/-/blob/a2cbd35b02be88380746fa0dddd0cface8889298/lib/ocf.ml#L195-219 (The use-case in typerep makes more sense to me.)

In other words: I think that if the compiler had rejected this use-case in the first place, people would have written better code. So maybe it is not so bad to start rejecting it now, especially since people are already well aware that Obj.magic carries a certain amount of technical debt that will have to be paid later on.

@Octachron
Copy link
Member

Octachron commented May 17, 2024

@gasche , my summary of the history would be more:

type t = {f: 'a. ('a list -> int) Lazy.t}
let not_found () = raise Not_found
let l = { f = lazy (not_found ())};;

fails on trunk.

{ f = <body> }

into

let f = <body> in { f }

Taking in account that:

  1. the somewhat natural case has been fixed
  2. this is a weirdness of the relaxed value restriction when combined to "wildly polymorphic" value that can be tamed
  3. this weirdness may also happens outside of the label case
  4. OCaml users might be more familiar with the relaxed value restriction than in 2010

I would be in favour to keep the simplification of #12932 .

@gasche
Copy link
Member

gasche commented May 17, 2024

Yes, I am not in favor of removing #12932 either, just pointing out that its impact is larger than we had anticipated.

@gasche
Copy link
Member

gasche commented May 17, 2024

My impression so far is that "deal with it" is a reasonable response to users whose code has been broken in trunk, at least in all the cases that have been brought to our attention so far.

@gasche
Copy link
Member

gasche commented May 29, 2024

For now we decided to not change anything upstream. Feel free to add more information about existing breakages.

@gasche gasche closed this as completed May 29, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants