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

Recursive modules do not correctly handle variance #6492

Open
vicuna opened this issue Jul 19, 2014 · 4 comments
Open

Recursive modules do not correctly handle variance #6492

vicuna opened this issue Jul 19, 2014 · 4 comments

Comments

@vicuna
Copy link

vicuna commented Jul 19, 2014

Original bug ID: 6492
Reporter: @lpw25
Status: acknowledged (set by @damiendoligez on 2014-07-30T20:39:06Z)
Resolution: open
Priority: normal
Severity: feature
Target version: later
Category: typing
Tags: recmod
Related to: #5984

Bug description

Variance calculation is done by looking up the variance of any used type constructors in the environment. When types in recursive modules depend on each other, the variance information only travels through one level of indirection.

For example, Bar.t is covariant but Baz.t is invariant in the following example:

# module rec Foo : sig type 'a t = Foo of 'a end = Foo
  and Bar : sig type 'a t = Bar of 'a Foo.t  end = Bar
  and Baz : sig type 'a t = Baz of 'a Bar.t end = Baz;;
    module rec Foo : sig type 'a t = Foo of 'a end
and Bar : sig type 'a t = Bar of 'a Foo.t end
and Baz : sig type 'a t = Baz of 'a Bar.t end

# let f x = (x : <m:int> Bar.t :> < > Bar.t);;
val f : < m : int > Bar.t -> <  > Bar.t = <fun>

# let f x = (x : <m:int> Baz.t :> < > Baz.t);;
Characters 10-42:
  let f x = (x : <m:int> Baz.t :> < > Baz.t);;
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: Type < m : int > Baz.t is not a subtype of <  > Baz.t 
       The second object type has no method m

whereas if the types had been defined recursively then baz would be covariant:

# type 'a foo = Foo of 'a
  and 'a bar = Bar of 'a foo
  and 'a baz = Baz of 'a baz;;
    type 'a foo = Foo of 'a
and 'a bar = Bar of 'a foo
and 'a baz = Baz of 'a baz

# let f x = (x : <m:int> baz :> < > baz);;
val f : < m : int > baz -> <  > baz = <fun>

Variance calculation is also overly conservative when using approximate type definitions from approx_type_decl, which means that variance annotations can lead to spurious errors. For example:

# module rec Foo : sig type +'a t end = Foo
  and Bar : sig type +'a t = Bar of 'a Foo.t  end = Bar;;
  Characters 63-86:
    and Bar : sig type +'a t = Bar of 'a Foo.t  end = Bar;;
                       ^^^^^^^^^^^^^^^^^^^^^^^
Error: In this definition, expected parameter variances are not satisfied.
       The 1st type parameter was expected to be covariant,
       but it is injective invariant.

If the covariance annotation is removed from Bar.t then there is no error, and Bar.t is considered covariant:

# module rec Foo : sig type +'a t end = Foo
  and Bar : sig type 'a t = Bar of 'a Foo.t  end = Bar;;
  module rec Foo : sig type +'a t end
and Bar : sig type 'a t = Bar of 'a Foo.t end

# let f x = (x : <m:int> Bar.t :> < > Bar.t);;
val f : < m : int > Bar.t -> <  > Bar.t = <fun>
@github-actions
Copy link

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

@github-actions github-actions bot added the Stale label May 11, 2020
@lpw25
Copy link
Contributor

lpw25 commented May 11, 2020

These issues still exist. I think that at some point we will need to change how variance is handled to fix other issues with it -- fundamentally that the annotations do not remain precise after substitution. When that happens it should be possible to fix this issue.

@github-actions github-actions bot removed the Stale label Jun 15, 2020
@github-actions
Copy link

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

@github-actions
Copy link

github-actions bot commented Oct 5, 2022

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

@github-actions github-actions bot added the Stale label Oct 5, 2022
@Octachron Octachron removed the Stale label Oct 5, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

6 participants