Idris2 icon indicating copy to clipboard operation
Idris2 copied to clipboard

Incorrect handling of "shadowing" in LHS

Open spcfox opened this issue 1 month ago • 5 comments

Steps to Reproduce

foo : (n : Nat) -> Vect n a -> ()
foo Z [] = ()
foo n@(.(S n)) (_ :: xs) = foo _ xs

The hole should resolve to the inner n, but it is erased, and the outer one appears in its place. This results in an incorrect clause:

foo n@(.(S _)) (_ :: xs) = foo n xs

Expected Behavior

Error: While processing left hand side of foo. Can't match on ?n [no locals in scope] (Non linear pattern variable).

or

Error: While processing right hand side of foo. n is not accessible in this context.

Observed Behavior

Main> baz 2 [1, 2]
baz 2 []

spcfox avatar Nov 11 '25 09:11 spcfox

The problem is not in solving the hole, but in unification. If we explicitly write n, we will get the same result.

foo : (n : Nat) -> Vect n a -> ()
foo Z [] = ()
foo n@(.(S n)) (_ :: xs) = foo n xs

spcfox avatar Nov 12 '25 21:11 spcfox

At first I thought it was shadowing, but the two n are being treated as the same before it gets to the RHS.

foo : (n : Nat) -> Vect n a -> ()
foo Z [] = ()
foo n@(.(S n)) (_ :: xs) = ?hole

gives

> :ti hole
 0 a : Type
   n : Nat
   xs : Vect n a
------------------------------
hole : ()

dunhamsteve avatar Nov 12 '25 21:11 dunhamsteve

Yes, there is no shadowing of names in LHS because names have the form PV str functionId.

spcfox avatar Nov 12 '25 22:11 spcfox

This also works for conflicts with names in the other patterns

foo : Nat -> (n : Nat) -> Vect n a -> ()
foo _ Z [] = ()
foo n .(S n) (_ :: xs) = foo n n xs
Main> foo 42 2 [1, 2]
foo 42 42 []

spcfox avatar Nov 13 '25 06:11 spcfox

Such cases without a dot are discarded by adding dots to repeating names. https://github.com/idris-lang/Idris2/blob/c6788e5ce0f27436986f4a7bcb8845782ac11db5/src/TTImp/Elab/Ambiguity.idr#L37-L41

But we cannot use a dot inside a dotted pattern.

spcfox avatar Nov 13 '25 06:11 spcfox