Nested implicit ambiguity error is not recovered from correctly

[LukaJCB]

Minimized code

trait Foo[F[_]]

trait Bar[F[_]] extends Foo[F]
trait Baz[F[_]] extends Foo[F]

case class Applied[F[_], A](a: F[A])


object Applied extends AppliedLowPrio {
  implicit def barApplied[F[_]: Baz]: Baz[[X] =>> Applied[F, X]] = ???
}

trait AppliedLowPrio {
  implicit def bazApplied[F[_]: Foo]: Foo[[X] =>> Applied[F, X]] = ???
}


object Test {
  def test[F[_]: Bar: Baz] = implicitly[Foo[[X] =>> Applied[F, X]]]
}

Output

-- Error: try/i9793.scala:19:67 ------------------------------------------------
19 |  def test[F[_]: Bar: Baz] = implicitly[Foo[[X] =>> Applied[F, X]]]
   |                                                                   ^
   |ambiguous implicit arguments of type Foo[[X] =>> Applied[F, X]] found for parameter ev of method implicitly in object DottyPredef.
   |I found:
   |
   |    Applied.bazApplied[F](
   |      /* ambiguous: both value evidence$4 and value evidence$3 match type Foo[F] */
   |        summon[Foo[F]]
   |    )
   |
   |But both value evidence$4 and value evidence$3 match type Foo[F].

Expectation

This should compile as it does in Scala 2.x

[smarter]

There's a related intentional change here but I think the implementation is incorrect, from http://dotty.epfl.ch/docs/reference/changed-features/implicit-resolution.html:

The treatment of ambiguity errors has changed. If an ambiguity is encountered in some recursive step of an implicit search, the ambiguity is propagated to the caller.

Now, that doesn't mean that an ambiguity is fatal: if there's some more specific alternative we should prefer it, but this doesn't work as expected. Concretely here we first try bazApplied, this fails with:

Applied.bazApplied[F](/* ambiguous: both value baz and value bar match type Foo[F] */summon[Foo[F])

Because the ambiguity is propagated, this is considered an ambiguous result so we end up in healAmbiguous:

https://github.com/lampepfl/dotty/blob/bd05d371b3eb2605f2382f2499f2cf422f3f32fa/compiler/src/dotty/tools/dotc/typer/Implicits.scala#L1162-L1172

The only thing in pending is barApplied, this should work since it's more specific than bazApplied, except we're not comparing it against bazApplied, instead we're comparing it against ambi.alt1 and ambi.alt2, those are the two ambiguous results from the previous search (in our case baz and bar), but this doesn't make sense since they were candidates from a different search!

Concretely, this call to healAmbiguous:
https://github.com/lampepfl/dotty/blob/bd05d371b3eb2605f2382f2499f2cf422f3f32fa/compiler/src/dotty/tools/dotc/typer/Implicits.scala#L1203
needs to be replaced by something like:

                    val newPending = pending
                      .filter(p => compareCandidate(cand, p.ref, p.level) < 0)
                    rank(newPending, fail, Nil).recoverWith(_ => fail)

(that doesn't work as-is because the first argument of compareCandidate has to be a SearchSuccess and not a Candidate, but that's easy to fix)