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

Incorrect FreeVars Type case for newtypes and enums #1773

Closed
RyanGlScott opened this issue Nov 19, 2024 · 0 comments · Fixed by #1774
Closed

Incorrect FreeVars Type case for newtypes and enums #1773

RyanGlScott opened this issue Nov 19, 2024 · 0 comments · Fixed by #1774
Labels
bug Something not working correctly enums Issues related to enums

Comments

@RyanGlScott
Copy link
Contributor

RyanGlScott commented Nov 19, 2024

While auditing the code in Cryptol.IR.FreeVars recently, @yav and I noticed a bug in the FreeVars Type instance involving TNominal (i.e., newtypes and enums):

TNominal nt ts -> freeVars nt <> freeVars ts

There are two things wrong here:

  1. This collects the free variables of nt (a NominalType), but the FreeVars NominalType does not return the name of the nominal type (intentionally so). As such, if you had newtype N = { x : Bit }, then freeVars N would not include N, which is a pretty serious bug.
  2. Less seriously, the code here overapproximates the set of free variables by collecting all of the free variables from the definition of nt. For example, freeVars N will include Bit because the FreeVars NominalType instance includes the free variables of N's fields, even though the type N doesn't directly mention Bit.

To fix both of these issues, we should modify the instance so that it only includes ntName nt (but no other parts of nt) in the Deps that this returns.

In practice, these issues are unlikely to cause anything bad to happen within Cryptol itself. This is because the FreeVars instances are primarily used for sorting declarations in dependency order, but we only sort top-level functions, not nominal type declarations. Still, it would be good to fix this so that Cryptol API users could sort nominal type declarations in dependency order if they wanted to.

@RyanGlScott RyanGlScott added bug Something not working correctly enums Issues related to enums labels Nov 19, 2024
@RyanGlScott RyanGlScott changed the title Incorrect FreeVars instances for newtypes and enums Incorrect FreeVars Type case for newtypes and enums Nov 19, 2024
RyanGlScott added a commit that referenced this issue Nov 19, 2024
Rather than computing the free variables of a `NominalType` definition, we only
include the name of the `NominalType` itself as a free variable.

Fixes #1773.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something not working correctly enums Issues related to enums
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant