Capture leak when using varargs?

Question
1

I’m writing the following code, where the interesting bit is in the capture set of oneOf.

//> using scala 3.nightly
//> using option -language:experimental.captureChecking -nowarn

import caps.*

trait Rand extends SharedCapability:
  def range(min: Int, max: Int): Int

def nextInt(max: Int): Rand ?-> Int =
  r ?=> r.range(0, max)

def oneOf[A](head: Rand ?=> A, tail: (Rand ?=> A)*): Rand ?->{head} A =
  val all: Seq[Rand ?->{head, tail*} A] = head +: tail

  all(nextInt(all.length))

Instinctively, I would expect oneOf to return Rand ?→{head, tail*} A, and am a little weirded out that the above code compiles. Isn’t this forgetting the fact that whatever is contained by tail is tracked?

I do need all to explicitly capture {head, tail*}, so my expectations seem at list a little reasonable…

1 Like
2

That’s indeed a bug in the implementation. In fact you could also have declaredoneOf to return a pure function Rand → A and this would have typechecked also, which is even more wrong than what you showed. Fix is forthcoming.

2 Likes
3

There’s now a PR that should fix this: Fix apply rule by odersky · Pull Request #24273 · scala/scala3 · GitHub

1 Like
4

Thank you so much - and sorry I keep running in all these corner cases…

1 Like
5

You should not be sorry at all! It’s a big help for us that you find these corner cases.

2 Likes
6

I’m still running in the same issue in 3.8.0-RC3 and 3.nightly, even though the PR linked by Martin was merged quite a while ago.

Is this a regression, or have my expectations become incorrect in the face of more developments / discoveries of how capture sets work?

7

I think you need to start the repl like this for this to work:

scala --scala-version 3.nightly -language:experimental.captureChecking

I don’t think the using //> work in this case. But they should report an error if they don’t work.

8

After various tests, it doesn’t appear to make a difference whether I use the //>… bits or the command line you suggested. However, I think I made a mistake when testing the nightly this morning.

Trying again tonight:

  • with 3.8.0-RC3: the problem is still the same.
  • with 3.nightly, I get a different problem.

To remove potential ambiguities, here’s the exact code I run:

import caps.*

trait Rand extends SharedCapability:
  def range(min: Int, max: Int): Int

object Rand:

  def nextInt(max: Int): Rand ?-> Int =
    r ?=> r.range(0, max)

  def oneOf[A](head: Rand ?=> A, tail: (Rand ?=> A)*): Rand ?->{head, tail*} A =
    val all: Seq[Rand ?->{head, tail*} A] = head +: tail

    all(nextInt(all.length))

This is invoked with:

scala --scala-version 3.nightly -language:experimental.captureChecking rep.scala

The error I get is:

Compiling project (Scala 3.8.1-RC1-bin-20251229-e73ff2c-NIGHTLY, JVM (21))
[error] ./rep.scala:14:5
[error] Local reach capability tail* leaks into capture scope of method oneOf.
[error] You could try to abstract the capabilities referred to by tail* in a capset variable.
[error]     all(nextInt(all.length))
[error]     ^^^^^^^^^^^^^^^^^^^^^^^^

This is a little confusing, because if I remove the tail* bit of the capture set of oneOf, I get:

Compiling project (Scala 3.8.1-RC1-bin-20251229-e73ff2c-NIGHTLY, JVM (21))
[error] ./rep.scala:12:5
[error] Found:    (contextual$1: Rand^'s1) ?->{head, tail*} A^'s2
[error] Required: (Rand^) ?->{head} A
[error] 
[error] Note that capability tail* is not included in capture set {head}.
[error] 
[error] where:    ^ refers to the universal root capability

Which feels a little like the compiler is contracting itself - if I don’t include tail*, it complains it’s not there. If I do include it, it complains it’s leaking (which, I’m not entirely sure what that means here).

Is there anything I can do to help decide whether this is a bug or slightly confusing error messages? I’m sure that test case can be reduced a little more, for example.

9

The error messages do give you a bit of a run-around. They are both correct, but not helpful since the obvious fix to the type mismatch causes the leakage error for the reach capability. I tried in Warn if reach capability in result will likely cause leakage by odersky · Pull Request #24860 · scala/scala3 · GitHub to give you a warning at the point where you try toi add the reach capability to the result. That now produces the following for your example:

-- Warning: tests/neg-custom-args/captures/nicolas2.scala:9:53 ---------------------------------------------------------
9 |def oneOf[A](head: Rand ?=> A, tail: (Rand ?=> A)*): Rand ?->{head, tail*} A =
  |                                                     ^^^^^^^^^^^^^^^^^^^^^^^
  |                             Reach capability tail* in function result refers to parameter tail.
  |                             To avoid errors of the form "Local reach capability tail* leaks into capture scope ..."
  |                             you should replace the reach capability with a new capset variable in method oneOf.
-- Error: tests/neg-custom-args/captures/nicolas2.scala:11:5 -----------------------------------------------------------
11 |  all(nextInt(all.length))  // error
   |  ^^^^^^^^^^^^^^^^^^^^^^^^
   |  Local reach capability tail* leaks into capture scope of method oneOf.
   |  You could try to abstract the capabilities referred to by tail* in a capset variable.

The correct way to fix the example is:

import caps.*

trait Rand extends SharedCapability:
  def range(min: Int, max: Int): Int

def nextInt(max: Int): Rand ?-> Int =
  r ?=> r.range(0, max)

def oneOf[A, B^](head: Rand ?=> A, tail: (Rand ?->{B} A)*): Rand ?->{head, B} A =
  val all: Seq[Rand ?->{head, B} A] = head +: tail // error
  all(nextInt(all.length))
10

Oh I see. I clearly misunderstood reach capabilities (and misunderstand them still!) because I honestly thought that, in this context, tail* was equivalent to your B.

Another thing I need to understand is how this actually ends up doing the right thing. I assumed it would get it wrong, but:

val i1: Rand ?->{a1} Int = ...
val i2: Rand ?->{a2} Int = ...
val i3: Rand ?->{a3} Int = ...

oneOf(i1, i2, i3) // correctly has type Rand ?->{i1, i2, i3} Int

Intuitively, B is inferred to be the union of the capture sets of all the elements of tail, but I’m not entirely sure how…

11

Yes, that would be nice, but unfortunately there are some fine distinctions that we need to make for soundness. The issue arises when we would call oneOf in a lambda like this:

val xs: List[A^{b, c}] = List(b, c)
() => oneOf(a, xs*)

Do we charge the deep capture set of the type of xs* to the closure, which would be {b, c}, or just the capture set, which would be empty? I.e. Should this expression have type () ->{a} A or () ->{a, b, c} A? The answer is that we always charge the capture set, not the deep set, so it would be () ->{a} A. But that means we cannot access a reach capability of a parameter unless we immediately box it again.

If you replace the reach capability with a capset variable B it’s the other way round. We always charge the deep capture set of the type argument passed to B, so referring to B anywhere in the function result is sound.

This is admittedly very tricky, and the best thiung to do here is follow the compiler’s advice. Maybe we should simply drop reach capabilities and always rely on capset variables for these cases. Then these issues would not arise, but we’d get some expressiveness issues elsewhere.

Yes, that’s correct. Inference is done with a constraint solver that effectively unions the argument sets passed into a capset variable.

12

Thanks for taking the time for this thorough explanation, it’s very much appreciated.

Yes, this is a little tricky, but that might be something that solves itself with conventions. If the convention becomes to use capset variables rather than reach capabilities, most people won’t even be aware of this difficulty.