FStarLang / FStarLang/FStar

`tcresolve`: cannot infer in presence of universe variables

Open
#3,263 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
F*
Stars
3.1k
Forks
266
Avg merge
21h 1m
Merged PRs (30d)
54

Description

In the presence of universe variables, `tcresolve` doesn't work. Consider the following module:

```fstar
module Bug

class foo (t: Type0): Type = { u: Type }
// or this explicit version, same issue:
// class foo (t: Type0): Type u#(max 1 (n+1)) = { u: Type u#n }

let works {| foo u#m 't |}: foo u#m 't = _ by (FStar.Tactics.Typeclasses.tcresolve ())
[@expect_failure]
let fails {| foo 't |}: foo 't = _ by (FStar.Tactics.Typeclasses.tcresolve ())
```

The uvars of the top-level `fails` are basically infered as:
```fstar
let fails {| foo u#n 't |}: foo u#m 't = _ by (FStar.Tactics.Typeclasses.tcresolve ())
```
Thus the goal is impossible to fill.

Contributor guide

Open the contributing guide

Research direction

Start with the minimal F* module in the issue and the FStar.Tactics.Typeclasses.tcresolve entry point. Reproduce the successful and failing cases, then trace how universe variables are inferred during typeclass resolution. Done means the failing example resolves correctly without breaking the explicit-universe case.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.