[
https://issues.apache.org/jira/browse/GROOVY-12323?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Paul King resolved GROOVY-12323.
--------------------------------
Fix Version/s: 6.0.0-beta-4
Resolution: Fixed
> 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
> Assignee: Paul King
> Priority: Major
> Fix For: 6.0.0-beta-4
>
>
> {{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)
