[
https://issues.apache.org/jira/browse/GROOVY-12324?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Paul King resolved GROOVY-12324.
--------------------------------
Fix Version/s: 6.0.0-beta-4
Resolution: Fixed
> ChannelSelect: add per-select preconditions so a guard can be masked off
> without renumbering branches
> -----------------------------------------------------------------------------------------------------
>
> Key: GROOVY-12324
> URL: https://issues.apache.org/jira/browse/GROOVY-12324
> Project: Groovy
> Issue Type: Improvement
> Reporter: Paul King
> Assignee: Paul King
> Priority: Major
> Fix For: 6.0.0-beta-4
>
>
> h2. Summary
> {{ChannelSelect}} has no way to disable one branch of a select. Every offer
> passed to
> {{ChannelSelect.from(...)}} / {{ChannelSelect.offers(...)}} is always live,
> so the classic guarded ALT --
> "take a PUT only while the buffer has room, take a GET only while it has
> content" -- cannot be written.
> In CSP terms {{ChannelSelect}} today has only the right-hand half of an ALT
> guard. occam's grammar is
> {{guard ::= input | boolean & input | boolean & SKIP}}; GROOVY-12323 added
> the send offers (output guards);
> the {{boolean &}} part is still missing.
> h2. Why the obvious workaround does not work
> The only way to express a guard today is to vary the argument list:
> {code:groovy}
> ChannelSelect alt = counter == 0 ? ChannelSelect.from(get)
> : counter == elements ? ChannelSelect.from(put)
> : ChannelSelect.from(put, get)
> ChannelSelect.Result r = await alt.select()
> if (r.index == 0) { /* which channel is this? */ }
> {code}
> {{Result.getIndex()}} is *positional*, so masking off anything other than the
> last branch renumbers the
> rest: {{get}} is branch 1 in one arm and branch 0 in another, and no
> branch-wise code or specification
> means anything. The workaround silently changes what {{index}} denotes rather
> than failing.
> This is not hypothetical -- it is the canonical teaching example. Jon
> Kerridge's _Using Concurrency and
> Parallelism Effectively_ c05 {{Queue.groovy}} is a bounded circular buffer
> that masks *both* guards, and
> JCSP's own {{Alternative}} javadoc uses the same shape (the "canteen").
> Neither can be ported.
> h2. Prior art
> The strongest precedent is Groovy's own previous concurrency library. *GPars
> shipped exactly this, called
> it "guards", and used the identical {index, value} result shape:*
> {code:java}
> // groovyx.gpars.dataflow.Select
> SelectResult<T> select(List<Boolean> mask)
> SelectResult<T> prioritySelect(List<Boolean> mask)
> Promise<SelectResult<T>> selectToPromise(List<Boolean> mask)
> // "Only the channels marked with 'true' in the supplied mask will be
> considered."
> {code}
> {{SelectResult}} is {{getIndex()}} + {{getValue()}} -- the same contract as
> {{ChannelSelect.Result}} -- and
> index stability is explicit in its implementation
> ({{GuardedSelectRequest.matchesMask(index)}};
> {{SelectBase}} reports the original position). So this reads as a regression
> against GPars, not a new idea.
> || System || Disable a branch? || How || Winner identified by || Index
> stable? ||
> | JCSP | yes | {{select/priSelect/fairSelect(boolean[] preCondition)}} |
> index | *yes* |
> | GPars | yes | {{select(List<Boolean> mask)}}, {{setGuard(i, b)}} | index |
> *yes* |
> | occam / occam-pi | yes | grammar: {{bool & c ? x}} | the alternative | no
> index |
> | Ada | yes | {{when Cond =>}}; entry barriers | the accept | no index |
> | Erlang / Elixir | yes | {{Pattern when Guard ->}} | the clause | no index |
> | Go | indirectly | {{nil}} channel never proceeds | the case body | no index
> |
> | Kotlin coroutines | yes | conditional clause registration in {{select \{
> \}}} | the lambda | no index |
> | Clojure core.async | yes | build the {{ports}} vector per call | *the port
> object* | not observable |
> | Concurrent ML / PyCSP | yes | omit, or {{never}} | value / channel end | no
> index |
> | Rust crossbeam | yes | {{Select::remove\(i)}}, ids never reused | index |
> *yes* |
> | C++CSP2 | *no mask* | only {{replaceGuard(i, g)}} | index | fixed slots |
> | Limbo (Inferno) | *no* | -- | {{(index, value)}} tuple | -- |
> | Groovy 6 today | *no* | -- | {{Result.getIndex()}} | breaks on rebuild |
> Limbo is the cautionary one: its array {{alt}} returns "a tuple containing
> the index of the channel over
> which a communication was received and the value received" -- Groovy 6's
> exact shape, with Groovy 6's exact
> gap. Go dropped the index and the problem disappeared. Groovy cannot drop it
> without breaking API, which is
> why the mask (which preserves a positional result) is the fitting approach
> here.
> h2. Proposal
> Add a per-call precondition mask:
> {code:java}
> public Awaitable<Result> select(boolean... enabled)
> {code}
> * {{enabled.length}} must equal {{offers.size()}}; otherwise
> {{IllegalArgumentException}} (JCSP does the
> same, with a message naming both lengths).
> * A branch whose flag is {{false}} is not registered for this selection.
> Indices are unchanged: the
> {{Result.index}} of an enabled branch is its position in the original offer
> list, exactly as today.
> * The mask is an argument to {{select()}}, *not* a builder step. This is
> deliberate: a {{disable\(i)}}
> returning a new instance would either shift indices (the bug being fixed)
> or discard the {{lastWinner}}
> rotation state that a held {{fair()}} instance carries -- and GROOVY-12320
> exists precisely so that
> rotation state is meaningful. JCSP and GPars both put the mask on the
> selection call for the same reason.
> * Applies to {{offers(...)}} as well as {{from(...)}}, so send offers can be
> guarded too. Keeping one
> offer-list + one mask (as JCSP keeps one {{Guard\[\]}} + one
> {{boolean\[\]}}) means a later timer, skip or
> barrier guard needs no second mechanism.
> h3. All branches disabled
> Raise, do not hang. Ada RM 9.7.1 specifies {{Program_Error}} "if all
> alternatives are closed and there is
> no else part". JCSP, read at source, instead leaves {{selected =
> NONE_SELECTED}} and waits on its monitor
> forever; that behaviour appears to be undocumented and is the one part of the
> JCSP design not worth
> copying. Suggested: complete the returned {{Awaitable}} exceptionally with
> {{IllegalStateException("no
> offer is enabled")}}.
> h2. Implementation sketch
> The class is already shaped for this; the change is contained to {{select()}}
> and {{registrationOrder()}}.
> * In the registration loop, skip {{k}} where {{!enabled\[order\[k\]\]}}.
> {{branches\[index\]}} simply stays
> {{null}} -- {{withdraw()}} is *already* null-tolerant ({{if (branch !=
> null) branch.cancel()}}), so
> nothing downstream changes.
> * {{closedCount.incrementAndGet() == count}} becomes {{== enabledCount}}, or
> an all-closed select over a
> partially enabled set never reports {{ChannelClosedException("all channels
> are closed")}}.
> * {{registrationOrder}} rotates over *enabled* indices only. {{lastWinner}}
> keeps storing the absolute
> index, so the {{FAIR}} start becomes "the next enabled index after
> {{lastWinner}}", and the
> {{PRIORITY}} and {{RANDOM}} orders are the same permutation restricted to
> the enabled set.
> * No change to {{Offer}}, {{Result}}, the claim protocol, or {{resend}}.
> The existing no-arg {{select()}} stays as {{select()}} = all enabled, so
> nothing existing changes.
> h3. Optional complement
> Additively, {{Result.getChannel()}} -- returning the {{AsyncChannel}} that
> committed. {{Offer}} already
> holds its channel and the winning offer is in scope at the {{new
> Result(...)}} call, so it is one field.
> That lets branch-wise code key on identity rather than position (the approach
> core.async, PyCSP and CML
> take), which makes a dynamically rebuilt {{from(...)}} safe even without a
> mask. Independent of the mask,
> and useful on its own.
> h2. Reproduction
> The gap was found by a static verifier for {{groovy.concurrent}} (the same
> tool that produced
> GROOVY-12320 and GROOVY-12323). It now refuses the c05 bounded buffer with
> the reason:
> {noformat}
> Skipped channel verification for queue (channel 'put' is a branch of a
> guarded ALT whose branch POSITIONS
> differ between the arms of its condition, so r.index would not name the same
> channel in every arm. Offer
> the branches in the same positions (a guarded ALT may drop a branch only from
> the END) --
> ChannelSelect.from(...) is positional, where JCSP's select(preCon) masks a
> guard while keeping its index;
> this API has no equivalent)
> {noformat}
> A guarded ALT that drops only its *last* branch verifies today, which is the
> whole of what can be
> expressed without this change.
> h2. Notes for reviewers
> * {{fair()}}'s javadoc currently guarantees that "every offer that is ready
> is taken within {{n}} calls,
> where {{n}} is the number of offers". Under a mask that wants one
> qualifier: {{n}} becomes the number of
> *enabled* offers, and an offer whose precondition is never true is never
> taken at all. This is inherent
> to guarded choice rather than a defect -- occam and Ada behave the same way
> -- but the sentence should be
> restated so the bound is not read as unconditional.
> * JCSP's {{select(boolean\[\])}} is literally {{fairSelect(preCondition)}};
> {{priSelect(boolean\[\])}}
> resets its favourite to 0. Groovy's policies are already explicit
> ({{fair()}} / {{random()}} / default
> priority), so the mask needs no policy-specific overloads.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
