Capture checking interferes with implicit search

[kyouko-taiga]

Compiler version

Scala compiler version 3.6.1 -- Copyright 2002-2024, LAMP/EPFL

Minimized code

import language.experimental.captureChecking
import language.experimental.modularity

trait Collection:
  me =>

  type Self
  type Position
  type Element

  extension (self: Self)

    def start: Position
    def end: Position
    def positionAfter(p: Position): Position
    def apply(p: Position): Element

    def withSlice[T](low: Position, high: Position)(
        action: Collection.Slice[Position, Element]^ => T
    ): T =
      action(Collection.Slice(using this)(self, low, high))

    def elementsEqual[C](other: C)(using
        C is Collection { type Element = me.Element }
    ): Boolean =
      ???

  end extension

object Collection:

  final class Slice[P, E](using C: Collection { type Position = P; type Element = E })(
      private val base: C.Self, val start: C.Position, val end: C.Position
  ):

    final def positionAfter(p: P): P =
      base.positionAfter(p)

    final def apply(p: P): E =
      base.apply(p)

  end Slice

given [P, E] => Collection.Slice[P, E] is Collection:

  type Position = P
  type Element = E

  extension (self: Self)
    def start: Position = self.start
    def end: Position = self.end
    def positionAfter(p: Position): Position = self.positionAfter(p)
    def apply(p: Position): Element = self.apply(p)

end given

given Long is Collection:

  type Element = Byte
  type Position = Int

  extension (self: Long)

    def start: Int = 0
    def end: Int = 8
    def positionAfter(p: Int): Int = p + 1
    def isWithin(p: Int, low: Int, high: Int): Boolean = (p >= 0) && (p < high)
    def apply(p: Int) = ((self >> (p * 8)) & 0xff).toByte

  end extension

end given

def main: Unit =
  val xs = 123L
  xs.withSlice(0, 8) { (ys) => ys.elementsEqual(ys) }

Output

-- [E007] Type Mismatch Error: main.scala:76:31 --------------------------------
76 |  xs.withSlice(0, 8) { (ys) => ys.elementsEqual(ys) }
   |                               ^^
   |                   Found:    (ys :
   |                     Collection.Slice[given_is_Long_Collection.Position,
   |                       given_is_Long_Collection.Element]^
   |                   )
   |                   Required: given_is_Slice_Collection[Int, Byte]#Self
   |
   | longer explanation available when compiling with `-explain`
-- [E007] Type Mismatch Error: main.scala:76:51 --------------------------------
76 |  xs.withSlice(0, 8) { (ys) => ys.elementsEqual(ys) }
   |                                                   ^
   |Found:    given_is_Slice_Collection[Int, Byte]
   |Required: box
   |  Collection.Slice[given_is_Long_Collection.Position,
   |    given_is_Long_Collection.Element]
   |^{ys} is
   |  Collection{type Element² = given_is_Slice_Collection[Int, Byte]#Element³}
   |
   |where:    Element  is a type in object given_is_Long_Collection which is an alias of Byte
   |          Element² is a type in trait Collection
   |          Element³ is a type in class given_is_Slice_Collection which is an alias of E
   |
   | longer explanation available when compiling with `-explain`

Expectation

The code should compile. Removing the ^ on the argument of Collection.elementsEqual makes the code compile as expected.

[kyouko-taiga]

Another occurrence of likely the same with a smaller reproducer:

final class Box[T](val contents: T):
  def borrowing[R](action: T^ => R): R = action(contents)

trait Copyable1[Self]:
  extension(self: Self) def copy1: Self

given Copyable1[Int] with
  extension(self: Int) def copy1: Int = self

given Copyable1[List[Int]] with
  extension(self: List[Int]) def copy1: List[Int] = self.map(x => x)

@main def Main =
  val b1 = Box(1)
  b1.borrowing { x => x.copy1 } // OK, as expected

  val b2 = Box(List(1))
  b2.borrowing { x => x.copy1 } // Fails

Error reported:

[error] -- [E007] Type Mismatch Error: main/scala/Main.scala:33:22 
[error] 33 |  b2.borrowing { x => x.copy1 }
[error]    |                      ^
[error]    |                      Found:    (x : List[Int]^)
[error]    |                      Required: List[Int]

Expected behavior:

Compiles without errors

[bracevac]

I don't think the second example is a bug: You declare the given for the untracked list type List[Int], and the borrowing extension method assumes a tracked list. You cannot just shake tracking status.

[bracevac]

I'm not sure about the first example, it needs further minimization.

Generally, implicits + captures is tricky, since capture checking is a recheck phase after typer + implicit resolution. Resolution involving captures will likely not behave according to intuitive expectations.