leanprover / leanprover/lean4

Matching on a constructor that takes an instance argument using swift notation wrongfully tries to synthesize the instance

Open
#2,626 2 comments 5 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug P-low
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

Prerequisites
  • Put an X between the brackets on this line if you have done all of the following:
    • Check that your issue is not already filed.
    • Reduce the issue to a minimal, self-contained, reproducible test case. Avoid dependencies to mathlib4 or std4.
Description

Matching on a .constructor that takes an instance argument wrongfully attempts to synthesize the instance.
When trying to match on a value of an inductive type that has a constructor taking an instance argument, Lean tries to synthesize the instance in the dot pattern, while it doesn't need to. The instance should be brought in scope in the corresponding branch, as it is contained in the value being matched on, but it doesn't make sense to synthesize the instance in the pattern itself.
Note that replacing the dot notation (.ctor) with a qualified constructor (Foo.ctor) or a bare constructor (open Foo then matching on ctor) fixes the issue.

Context

I was trying to reproduce something similar to Trees that Grow/Coq à la Carte to have an extensible inductive type, but using typeclasses to avoid syntactic overhead.

Steps to Reproduce
class Foo where

inductive Bar where
  | bar : [Foo] → Bar

example : Bar → True
  | .bar => .intro
/-  ^^^^
test.lean:7:4: error: failed to synthesize instance
  Foo
-/

-- works
example : Bar → True
  | Bar.bar => .intro

-- works
open Bar
example : Bar → True
  | bar => .intro

Expected behavior: Same as Bar.bar or open Bar then bar, i.e. bring the Foo instance in scope and don't try to synthesize the Foo instance in the pattern.

Actual behavior: Lean tries to synthesize the instance while it doesn't need to.

Versions
  • Lean (version 4.0.0-nightly-2023-06-10, commit bff612e59e48, Release)
  • Lean master at the time of writing this issue
  • Linux 5.15.111 # 1-NixOS SMP Thu May 11 14:00:40 UTC 2023 x86_64 GNU/Linux
Impact

Add 👍 to issues you consider important. If others are impacted by this issue, please ask them to add 👍 to it.

Fixing the bug

Trying to find the origin of the bug, grepping for dotIdent in the entire codebase only shows up four occurrences, only 1 being relevant from what I can tell: https://github.com/leanprover/lean4/blob/89b65c8f1d6fa7700d73f1bc12db0b140c728e32/src/Lean/Elab/PatternVar.lean#L216-L227

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the minimal reproducer in the issue and inspect src/Lean/Elab/PatternVar.lean around lines 216–227, the relevant dotIdent occurrence identified by the report. Run the example with the dot-pattern and qualified constructor forms. Done means the dot form no longer tries to synthesize Foo and behaves like the working forms.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.