Type-checker fails unification unexpectedly for auto-implicit type

[DrBearhands]

Came across a situation I believe to be a bug, but might be my own error.

Steps to Reproduce

module Main

data PostS : (valType : Type) -> (stateType : Type) -> (valType -> stateType -> Type) -> Type where
  MkPostS
    :  (val : valType)
    -> (outState : stateType)
    -> {auto 0 prf : prop val outState}
    -> PostS valType stateType prop


data Foo = Bar | Baz

f : PostS Foo Foo Equal
f = MkPostS Bar Bar

Also asked on stackoverflow as I thought it may be my own error: https://stackoverflow.com/questions/68953988/idris2-compiler-tries-to-unify-type-values-unexpectedly

Expected Behavior

Compilation succeeds.

Observed Behavior

Error(s) building file [...]: While processing right hand side of f. When unifying Baz and Bar.
Mismatch between: Baz and Bar.

tests.HoareMonad2:14:5--14:20
 10 | 
 11 | data Foo = Bar | Baz
 12 | 
 13 | f : PostS Foo Foo (Equal)
 14 | f = MkPostS Bar Bar
          ^^^^^^^^^^^^^^^

MkPostS Baz Baz compiles correctly, as does MkPostS{prf=Refl} Bar Bar. Combinations of Bar and Baz correctly fail (even if given {prf=Refl}).

When replacing Foo with Nat, the value passed to MkPostS attempts (and fails to) match on 0.

[gallais]

This works so my guess is that the search is run in a different order
when using an auto-implicit and wrongly picks Refl {x = Baz} as the
proof.

  MkPostS                                                                         
    :  (val : valType)
    -> (outState : stateType)
    -> (prf : prop val outState)
    -> PostS valType stateType prop
 
 
data Foo = Bar | Baz
 
f : PostS Foo Foo Equal
f = MkPostS Bar Bar %search

[gallais]

Could be related to #1012 where auto was also too eager to pick a wrong solution.

[buzden]

This issue is definitely related to #814 since if you put the function f from the original example into a separate module, all typechecks finely.