[
https://issues.apache.org/jira/browse/GROOVY-12323?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Paul King updated GROOVY-12323:
-------------------------------
Description:
{{ChannelSelect}} (GROOVY-12320) selects among *receives*: input guards. A
process therefore cannot say "I will send {{ping}}, *or* take {{pong}} if my
peer sends first" — the _mixed choice_ of the session-type and CSP literature.
occam banned output guards because arbitrating them needs a commit protocol
(Buckley & Silberschatz, _An effective implementation for the generalized
input-output construct of CSP_, TOPLAS 1983); JCSP's {{Alternative}} kept the
same restriction. GROOVY-12320 already built half of the machinery a modern
runtime needs to lift it: the claim-based receive ({{receiveIfUnclaimed}}).
This proposes the other half: a send offer that can be claimed or retired, so a
select over mixed offers commits *exactly one*.
The observations behind this are runnable:
[MixedChoiceRepro.groovy|https://github.com/paulk-asert/groovy-verify/blob/main/repro/MixedChoiceRepro.groovy],
identical on 6.0.0-beta-3 and on a 6.0.0-SNAPSHOT carrying GROOVY-12320.
h2. Proposed API
{code:groovy}
import static groovy.concurrent.ChannelSelect.*
def r = await offers(send(ping, i), receive(pong)).select()
if (r.index == 0) { /* my open committed: continue the ping branch */ }
else { /* my peer's open won: r.value is the pong opener */ }
{code}
* {{send(chan, value)}} — an offer to transfer {{value}} into {{chan}}. (No
{{Supplier<V>}} form in v1: the commit happens under the channel lock, so a
supplier would run user code under that lock or be pre-evaluated, defeating its
purpose — the value is required up front.)
* {{receive(chan)}} — today's input guard, unchanged.
* {{select()}} commits exactly one offer of this select; committing any offer
atomically retires the others.
* {{Result}} defines its send-commit shape explicitly: {{getValue()}} (the sent
value) and a branch-kind accessor ({{isSend()}}), rather than callers inferring
from the index.
* A send offer to a *closed* channel fails that branch and counts toward the
all-closed {{ChannelClosedException}} fast-fail, mirroring the receive
behaviour.
* Policies compose: {{fair()}} / {{random()}} order the scan over offers
exactly as GROOVY-12320 does over branches.
* A committed send behaves exactly like {{chan.send(v)}}; a retired one has NO
effect on the channel — no buffered residue, mirroring the claim-based
receive's "losers untouched".
h2. The real work: a revertible claim
GROOVY-12320 built the easy half, and this should be said plainly. A claimable
_receive_ never needs pairing — the claim is tested when a value is provably
present under a single channel lock. A send offer meeting a receive offer is a
genuine TWO-party commit across two selects' claims, and the current
irreversible boolean claim ({{Winner.claim}}, an {{AtomicBoolean}}) cannot
express it: claim yourself first and a failed CAS on the peer leaves you
committed with no transfer (and no guaranteed rescan — plain receivers withdraw
lock-free from the {{ConcurrentLinkedDeque}}); claim the peer first and a
failed CAS on yourself has committed the peer to a transfer that never happens.
The claim must become a three-state machine — OPEN → PENDING(owner) →
COMMITTED, with PENDING revertible and pending acquisition ordered/tie-broken
against livelock between symmetric peers: Buckley–Silberschatz's actual
protocol. Every existing claim site then speaks that machine (the receive path,
{{deliverToWaitingReceiver}}, {{drainBufferToReceivers}}, and
{{Winner.cancel}}, whose CAS-based timeout/cancel race is currently
load-bearing — the "holding the claim, this cannot fail" invariant).
{{waitingSenders}} (a plain {{ArrayDeque}} whose removal takes the channel
lock) needs the same lock-free-withdrawal treatment as receivers, or a losing
send offer withdrawn from inside a winning channel's delivery hits exactly the
cross-channel-lock deadlock the class comment warns about.
The alternative discipline is Go's — lock all member channels in a global order
during the scan, so the active party self-commits and one CAS on the parked
peer suffices — but this class deliberately rejected multi-channel locking
(that is why {{waitingReceivers}} became a {{ConcurrentLinkedDeque}}).
Contained to two classes either way; it needs stress testing under real
contention, not just unit tests.
h2. The coherence caveat, stated up front
Arbitration restores SESSION coherence only where a send cannot complete
unilaterally — that is, over RENDEZVOUS (capacity-0) channels, which
{{DefaultAsyncChannel(0)}} already supports (a capacity-0 {{send}} returns a
pending promise that completes exactly when a receiver takes it). Run the mixed
choice over buffered channels with the proposed API and both send offers find
buffer space, commit under only their own select's claim, and the collision of
experiment 1 reproduces exactly, through the new feature. Each select's claim
arbitrates within that select; coherence BETWEEN two selects comes only from
the rendezvous itself. Go has the identical property — its mixed-choice idioms
use unbuffered channels. Send offers on buffered channels remain meaningful (a
space-driven select: "send when room frees, or take from the other branch") —
they just do not give cross-select session coherence, and the docs should say
so, or the collision will be filed as a bug against the new feature.
h2. Why the buffered workaround is not one
With buffered channels each peer can just {{send}} its opener unconditionally —
but then _both_ sends succeed, and each peer reads the other's opener as "your
choice": one session, two peers on different branches, each sure of its own
(experiment 1; the session-type literature's classic coherence failure). Making
one peer the designated opener works (experiment 2), but it is priority, not a
race. Two polite peers that only offer to receive never start at all
(experiment 3). A one-line CAS shows the semantics wanted: 1000 racing trials,
exactly one branch committed in every one, zero double-commits, zero
non-commits (experiment 4) — that claim, run inside the select over the
channel's own machinery, is this proposal.
h2. Observed (both runtimes, MixedChoiceRepro.groovy)
# Both peers open: both buffered sends succeed; left continues down the PONG
branch while right continues down the PING branch — the collision.
# One initiator: the mixed choice degenerates to that peer's choice — works
today.
# Both polite: {{select().orTimeoutMillis(500)}} times out — nobody opens.
# The CAS claim: 1000/1000 trials commit exactly one branch.
# A capacity-0 (rendezvous) send pends until a receiver takes it, while a
buffered send completes alone — where cross-select coherence must come from.
h2. Relation to GROOVY-12320 — and to the class's own stated model
Same design centre: selection must not disturb what it does not take.
GROOVY-12320 made the _receive_ side claimable (losers untouched, all-closed
fails fast, {{fair()}}/{{random()}}); send offers are its completion — the
harder half. And the precedent is closer to home than occam:
{{ChannelSelect}}'s own javadoc cites Go's {{select}} as its inspiration, and
Go's {{select}} supports send cases — so this completes parity with the class's
stated model, not just with the generalized CSP alternative. The occam/JCSP ban
on output guards was motivated by DISTRIBUTED commit cost (Buckley–Silberschatz
1983); in shared memory that cost does not apply, and Go proved the construct
tractable there. With it, a compile-time session checker can certify the racing
mixed choice (over rendezvous channels) instead of refusing it.
Timing is worth weighing: {{ChannelSelect}} is {{@since 6.0.0}} and still in
beta, so landing the API surface before GA avoids a 6.x addition — against
which sits the protocol risk, since the claim state-machine touches invariants
already shipped in beta; if it slips past GA it remains additive and safe in
6.x.
> ChannelSelect: add claimable send offers (output guards)
> --------------------------------------------------------
>
> Key: GROOVY-12323
> URL: https://issues.apache.org/jira/browse/GROOVY-12323
> Project: Groovy
> Issue Type: Improvement
> Reporter: Paul King
> Priority: Major
>
> {{ChannelSelect}} (GROOVY-12320) selects among *receives*: input guards. A
> process therefore cannot say "I will send {{ping}}, *or* take {{pong}} if my
> peer sends first" — the _mixed choice_ of the session-type and CSP
> literature. occam banned output guards because arbitrating them needs a
> commit protocol (Buckley & Silberschatz, _An effective implementation for the
> generalized input-output construct of CSP_, TOPLAS 1983); JCSP's
> {{Alternative}} kept the same restriction. GROOVY-12320 already built half of
> the machinery a modern runtime needs to lift it: the claim-based receive
> ({{receiveIfUnclaimed}}). This proposes the other half: a send offer that can
> be claimed or retired, so a select over mixed offers commits *exactly one*.
> The observations behind this are runnable:
> [MixedChoiceRepro.groovy|https://github.com/paulk-asert/groovy-verify/blob/main/repro/MixedChoiceRepro.groovy],
> identical on 6.0.0-beta-3 and on a 6.0.0-SNAPSHOT carrying GROOVY-12320.
> h2. Proposed API
> {code:groovy}
> import static groovy.concurrent.ChannelSelect.*
> def r = await offers(send(ping, i), receive(pong)).select()
> if (r.index == 0) { /* my open committed: continue the ping branch */ }
> else { /* my peer's open won: r.value is the pong opener */ }
> {code}
> * {{send(chan, value)}} — an offer to transfer {{value}} into {{chan}}. (No
> {{Supplier<V>}} form in v1: the commit happens under the channel lock, so a
> supplier would run user code under that lock or be pre-evaluated, defeating
> its purpose — the value is required up front.)
> * {{receive(chan)}} — today's input guard, unchanged.
> * {{select()}} commits exactly one offer of this select; committing any offer
> atomically retires the others.
> * {{Result}} defines its send-commit shape explicitly: {{getValue()}} (the
> sent value) and a branch-kind accessor ({{isSend()}}), rather than callers
> inferring from the index.
> * A send offer to a *closed* channel fails that branch and counts toward the
> all-closed {{ChannelClosedException}} fast-fail, mirroring the receive
> behaviour.
> * Policies compose: {{fair()}} / {{random()}} order the scan over offers
> exactly as GROOVY-12320 does over branches.
> * A committed send behaves exactly like {{chan.send(v)}}; a retired one has
> NO effect on the channel — no buffered residue, mirroring the claim-based
> receive's "losers untouched".
> h2. The real work: a revertible claim
> GROOVY-12320 built the easy half, and this should be said plainly. A
> claimable _receive_ never needs pairing — the claim is tested when a value is
> provably present under a single channel lock. A send offer meeting a receive
> offer is a genuine TWO-party commit across two selects' claims, and the
> current irreversible boolean claim ({{Winner.claim}}, an {{AtomicBoolean}})
> cannot express it: claim yourself first and a failed CAS on the peer leaves
> you committed with no transfer (and no guaranteed rescan — plain receivers
> withdraw lock-free from the {{ConcurrentLinkedDeque}}); claim the peer first
> and a failed CAS on yourself has committed the peer to a transfer that never
> happens. The claim must become a three-state machine — OPEN → PENDING(owner)
> → COMMITTED, with PENDING revertible and pending acquisition
> ordered/tie-broken against livelock between symmetric peers:
> Buckley–Silberschatz's actual protocol. Every existing claim site then speaks
> that machine (the receive path, {{deliverToWaitingReceiver}},
> {{drainBufferToReceivers}}, and {{Winner.cancel}}, whose CAS-based
> timeout/cancel race is currently load-bearing — the "holding the claim, this
> cannot fail" invariant). {{waitingSenders}} (a plain {{ArrayDeque}} whose
> removal takes the channel lock) needs the same lock-free-withdrawal treatment
> as receivers, or a losing send offer withdrawn from inside a winning
> channel's delivery hits exactly the cross-channel-lock deadlock the class
> comment warns about.
> The alternative discipline is Go's — lock all member channels in a global
> order during the scan, so the active party self-commits and one CAS on the
> parked peer suffices — but this class deliberately rejected multi-channel
> locking (that is why {{waitingReceivers}} became a
> {{ConcurrentLinkedDeque}}). Contained to two classes either way; it needs
> stress testing under real contention, not just unit tests.
> h2. The coherence caveat, stated up front
> Arbitration restores SESSION coherence only where a send cannot complete
> unilaterally — that is, over RENDEZVOUS (capacity-0) channels, which
> {{DefaultAsyncChannel(0)}} already supports (a capacity-0 {{send}} returns a
> pending promise that completes exactly when a receiver takes it). Run the
> mixed choice over buffered channels with the proposed API and both send
> offers find buffer space, commit under only their own select's claim, and the
> collision of experiment 1 reproduces exactly, through the new feature. Each
> select's claim arbitrates within that select; coherence BETWEEN two selects
> comes only from the rendezvous itself. Go has the identical property — its
> mixed-choice idioms use unbuffered channels. Send offers on buffered channels
> remain meaningful (a space-driven select: "send when room frees, or take from
> the other branch") — they just do not give cross-select session coherence,
> and the docs should say so, or the collision will be filed as a bug against
> the new feature.
> h2. Why the buffered workaround is not one
> With buffered channels each peer can just {{send}} its opener unconditionally
> — but then _both_ sends succeed, and each peer reads the other's opener as
> "your choice": one session, two peers on different branches, each sure of its
> own (experiment 1; the session-type literature's classic coherence failure).
> Making one peer the designated opener works (experiment 2), but it is
> priority, not a race. Two polite peers that only offer to receive never start
> at all (experiment 3). A one-line CAS shows the semantics wanted: 1000 racing
> trials, exactly one branch committed in every one, zero double-commits, zero
> non-commits (experiment 4) — that claim, run inside the select over the
> channel's own machinery, is this proposal.
> h2. Observed (both runtimes, MixedChoiceRepro.groovy)
> # Both peers open: both buffered sends succeed; left continues down the PONG
> branch while right continues down the PING branch — the collision.
> # One initiator: the mixed choice degenerates to that peer's choice — works
> today.
> # Both polite: {{select().orTimeoutMillis(500)}} times out — nobody opens.
> # The CAS claim: 1000/1000 trials commit exactly one branch.
> # A capacity-0 (rendezvous) send pends until a receiver takes it, while a
> buffered send completes alone — where cross-select coherence must come from.
> h2. Relation to GROOVY-12320 — and to the class's own stated model
> Same design centre: selection must not disturb what it does not take.
> GROOVY-12320 made the _receive_ side claimable (losers untouched, all-closed
> fails fast, {{fair()}}/{{random()}}); send offers are its completion — the
> harder half. And the precedent is closer to home than occam:
> {{ChannelSelect}}'s own javadoc cites Go's {{select}} as its inspiration, and
> Go's {{select}} supports send cases — so this completes parity with the
> class's stated model, not just with the generalized CSP alternative. The
> occam/JCSP ban on output guards was motivated by DISTRIBUTED commit cost
> (Buckley–Silberschatz 1983); in shared memory that cost does not apply, and
> Go proved the construct tractable there. With it, a compile-time session
> checker can certify the racing mixed choice (over rendezvous channels)
> instead of refusing it.
> Timing is worth weighing: {{ChannelSelect}} is {{@since 6.0.0}} and still in
> beta, so landing the API surface before GA avoids a 6.x addition — against
> which sits the protocol risk, since the claim state-machine touches
> invariants already shipped in beta; if it slips past GA it remains additive
> and safe in 6.x.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
