[
https://issues.apache.org/jira/browse/GROOVY-12156?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Paul King updated GROOVY-12156:
-------------------------------
Description:
TLDR this is a reproducibility (bytecode ordering) issue not a correctness
issue.
h2. Description
{{StaticTypeCheckingSupport.chooseBestMethod}} accumulates its result in a
{{HashSet}} and returns it as a list:
{code:java}
// StaticTypeCheckingSupport.java:1066
Set<MethodNode> bestMethods = new HashSet<>(); // choose best method(s) for
each possible receiver
for (ClassNode rcvr : duckType ? ((UnionTypeClassNode) receiver).getDelegates()
: new ClassNode[]{receiver}) {
...
bestMethods.addAll(view);
}
return new LinkedList<>(bestMethods); // assumes caller wants remove to be
inexpensive
{code}
{{MethodNode}} overrides neither {{equals()}} nor {{hashCode()}} (unlike
{{ClassNode}}, whose {{hashCode()}} is text-based and stable). The {{HashSet}}
therefore buckets by *identity hash code*, and the returned candidate order is
whatever identity hashing produces.
h3. Why this is not benign
HotSpot's default identity hash ({{-XX:hashCode=5}}) is a *thread-local
xorshift PRNG*. The value an object receives depends on how many identity
hashes that thread has already handed out, and each thread has its own state.
So the order is not random per run — it is _path-dependent_:
{noformat}
main thread, 0 prior hashes : [m5, m3, m1, m2, m4]
main thread, 3 prior hashes : [m5, m2, m4, m3, m1]
main thread, 7 prior hashes : [m2, m5, m4, m1, m3]
worker thread : [m1, m2, m3, m5, m4]
worker thread : [m5, m3, m1, m4, m2]
{noformat}
(5 objects with no {{hashCode()}} override, added to a {{HashSet}}, iterated.)
A fresh single-threaded JVM repeating identical work reproduces the same order
— but the candidate order changes when the compile runs on a different thread
or after a different amount of prior work. In practice that means a
*long-lived, reused Gradle daemon*, *parallel compile workers*, or simply *a
different set of classes compiled earlier in the same JVM* can each shift the
order. Reproducible builds require identical output from identical sources
regardless of that state. The nondeterministic reflection order in GROOVY-12149
also perturbs the sequence of {{hashCode()}} calls, so the two defects amplify
each other.
h3. Where the order reaches generated code
Most callers reduce to a single candidate and raise an ambiguity error
otherwise ({{StaticTypeCheckingVisitor:4397}}, {{:3581}},
{{findMethodOrFail:5694}}) — those are safe, since an ambiguity error emits no
bytecode. But three callers accept a multi-candidate list *without error*:
# *Union-type receiver (GROOVY-8965), {{StaticTypeCheckingVisitor:4385}}* — the
case that _deliberately_ fills the set with one best method per union delegate,
and so is a non-error path by construction:
{code:java}
if (mn.size() > 1 && obj instanceof UnionTypeClassNode) {
ClassNode returnType = mn.stream().map(MethodNode::getReturnType)
.reduce(WideningCategories::lowestUpperBound).get();
call.putNodeMetaData(DYNAMIC_RESOLUTION, returnType);
{code}
{{Stream.reduce}} folds in list order, and {{lowestUpperBound}} is not reliably
order-insensitive (folding interface types can build differing synthetic LUB
nodes). The resulting inferred type drives casts and return types in emitted
bytecode.
# *Method pointers / method references ({{::}}),
{{StaticTypeCheckingVisitor:3236-3268}}* — on more than one candidate it calls
{{extension.handleAmbiguousMethods}}, whose default implementation
({{TypeCheckingExtension:190}}) returns the list unchanged, then applies the
same order-sensitive {{lowestUpperBound}} fold to type the closure.
# *Macro dispatch, {{MacroCallTransformingVisitor:106-119}}* —
{{findMacroMethods}} returns {{chooseBestMethod(...)}} directly and the caller
loops over the candidates until one succeeds, so *the first candidate wins*.
When two macro methods both apply, identity-hash order decides which one
expands the call — a _different generated AST_, not merely a different byte
layout.
Ambiguity *error messages* also list candidates in this order, so diagnostics
are unstable too.
h3. Proposed fix
Use an insertion-ordered set:
{code:java}
Set<MethodNode> bestMethods = new LinkedHashSet<>();
{code}
{{MethodNode}} has identity {{equals}}/{{hashCode}}, so this is a
semantics-preserving drop-in — deduplication behaviour is unchanged. It yields
a _meaningful_ order rather than an arbitrary one: candidates follow the
{{duckType}} loop, i.e. the union's declared delegate order.
{{StaticTypeCheckingVisitor:671}} already uses {{LinkedHashSet<MethodNode>}}
for {{PV_METHODS_ACCESS}}, so this matches existing practice.
h3. Suggested test
A {{@CompileStatic}} union-type receiver (per GROOVY-8965) whose delegates
declare the same method with different return types, asserting the inferred
{{DYNAMIC_RESOLUTION}} type; and a macro case with two applicable macro
methods, asserting which expansion wins. To exercise the path-dependence, run
the compile on a worker thread and/or after a varying number of identity-hash
allocations — with the {{HashSet}} the selection shifts, with {{LinkedHashSet}}
it does not.
was:
h2. Description
{{StaticTypeCheckingSupport.chooseBestMethod}} accumulates its result in a
{{HashSet}} and returns it as a list:
{code:java}
// StaticTypeCheckingSupport.java:1066
Set<MethodNode> bestMethods = new HashSet<>(); // choose best method(s) for
each possible receiver
for (ClassNode rcvr : duckType ? ((UnionTypeClassNode) receiver).getDelegates()
: new ClassNode[]{receiver}) {
...
bestMethods.addAll(view);
}
return new LinkedList<>(bestMethods); // assumes caller wants remove to be
inexpensive
{code}
{{MethodNode}} overrides neither {{equals()}} nor {{hashCode()}} (unlike
{{ClassNode}}, whose {{hashCode()}} is text-based and stable). The {{HashSet}}
therefore buckets by *identity hash code*, and the returned candidate order is
whatever identity hashing produces.
h3. Why this is not benign
HotSpot's default identity hash ({{-XX:hashCode=5}}) is a *thread-local
xorshift PRNG*. The value an object receives depends on how many identity
hashes that thread has already handed out, and each thread has its own state.
So the order is not random per run — it is _path-dependent_:
{noformat}
main thread, 0 prior hashes : [m5, m3, m1, m2, m4]
main thread, 3 prior hashes : [m5, m2, m4, m3, m1]
main thread, 7 prior hashes : [m2, m5, m4, m1, m3]
worker thread : [m1, m2, m3, m5, m4]
worker thread : [m5, m3, m1, m4, m2]
{noformat}
(5 objects with no {{hashCode()}} override, added to a {{HashSet}}, iterated.)
A fresh single-threaded JVM repeating identical work reproduces the same order
— but the candidate order changes when the compile runs on a different thread
or after a different amount of prior work. In practice that means a
*long-lived, reused Gradle daemon*, *parallel compile workers*, or simply *a
different set of classes compiled earlier in the same JVM* can each shift the
order. Reproducible builds require identical output from identical sources
regardless of that state. The nondeterministic reflection order in GROOVY-12149
also perturbs the sequence of {{hashCode()}} calls, so the two defects amplify
each other.
h3. Where the order reaches generated code
Most callers reduce to a single candidate and raise an ambiguity error
otherwise ({{StaticTypeCheckingVisitor:4397}}, {{:3581}},
{{findMethodOrFail:5694}}) — those are safe, since an ambiguity error emits no
bytecode. But three callers accept a multi-candidate list *without error*:
# *Union-type receiver (GROOVY-8965), {{StaticTypeCheckingVisitor:4385}}* — the
case that _deliberately_ fills the set with one best method per union delegate,
and so is a non-error path by construction:
{code:java}
if (mn.size() > 1 && obj instanceof UnionTypeClassNode) {
ClassNode returnType = mn.stream().map(MethodNode::getReturnType)
.reduce(WideningCategories::lowestUpperBound).get();
call.putNodeMetaData(DYNAMIC_RESOLUTION, returnType);
{code}
{{Stream.reduce}} folds in list order, and {{lowestUpperBound}} is not reliably
order-insensitive (folding interface types can build differing synthetic LUB
nodes). The resulting inferred type drives casts and return types in emitted
bytecode.
# *Method pointers / method references ({{::}}),
{{StaticTypeCheckingVisitor:3236-3268}}* — on more than one candidate it calls
{{extension.handleAmbiguousMethods}}, whose default implementation
({{TypeCheckingExtension:190}}) returns the list unchanged, then applies the
same order-sensitive {{lowestUpperBound}} fold to type the closure.
# *Macro dispatch, {{MacroCallTransformingVisitor:106-119}}* —
{{findMacroMethods}} returns {{chooseBestMethod(...)}} directly and the caller
loops over the candidates until one succeeds, so *the first candidate wins*.
When two macro methods both apply, identity-hash order decides which one
expands the call — a _different generated AST_, not merely a different byte
layout.
Ambiguity *error messages* also list candidates in this order, so diagnostics
are unstable too.
h3. Proposed fix
Use an insertion-ordered set:
{code:java}
Set<MethodNode> bestMethods = new LinkedHashSet<>();
{code}
{{MethodNode}} has identity {{equals}}/{{hashCode}}, so this is a
semantics-preserving drop-in — deduplication behaviour is unchanged. It yields
a _meaningful_ order rather than an arbitrary one: candidates follow the
{{duckType}} loop, i.e. the union's declared delegate order.
{{StaticTypeCheckingVisitor:671}} already uses {{LinkedHashSet<MethodNode>}}
for {{PV_METHODS_ACCESS}}, so this matches existing practice.
h3. Suggested test
A {{@CompileStatic}} union-type receiver (per GROOVY-8965) whose delegates
declare the same method with different return types, asserting the inferred
{{DYNAMIC_RESOLUTION}} type; and a macro case with two applicable macro
methods, asserting which expansion wins. To exercise the path-dependence, run
the compile on a worker thread and/or after a varying number of identity-hash
allocations — with the {{HashSet}} the selection shifts, with {{LinkedHashSet}}
it does not.
> chooseBestMethod returns candidates in identity-hash order, making
> static-compilation output path-dependent
> -----------------------------------------------------------------------------------------------------------
>
> Key: GROOVY-12156
> URL: https://issues.apache.org/jira/browse/GROOVY-12156
> Project: Groovy
> Issue Type: Improvement
> Components: Static compilation
> Reporter: Paul King
> Assignee: Paul King
> Priority: Major
> Fix For: 5.0.8, 6.0.0-beta-1
>
>
> TLDR this is a reproducibility (bytecode ordering) issue not a correctness
> issue.
> h2. Description
> {{StaticTypeCheckingSupport.chooseBestMethod}} accumulates its result in a
> {{HashSet}} and returns it as a list:
> {code:java}
> // StaticTypeCheckingSupport.java:1066
> Set<MethodNode> bestMethods = new HashSet<>(); // choose best method(s) for
> each possible receiver
> for (ClassNode rcvr : duckType ? ((UnionTypeClassNode)
> receiver).getDelegates() : new ClassNode[]{receiver}) {
> ...
> bestMethods.addAll(view);
> }
> return new LinkedList<>(bestMethods); // assumes caller wants remove to be
> inexpensive
> {code}
> {{MethodNode}} overrides neither {{equals()}} nor {{hashCode()}} (unlike
> {{ClassNode}}, whose {{hashCode()}} is text-based and stable). The
> {{HashSet}} therefore buckets by *identity hash code*, and the returned
> candidate order is whatever identity hashing produces.
> h3. Why this is not benign
> HotSpot's default identity hash ({{-XX:hashCode=5}}) is a *thread-local
> xorshift PRNG*. The value an object receives depends on how many identity
> hashes that thread has already handed out, and each thread has its own state.
> So the order is not random per run — it is _path-dependent_:
> {noformat}
> main thread, 0 prior hashes : [m5, m3, m1, m2, m4]
> main thread, 3 prior hashes : [m5, m2, m4, m3, m1]
> main thread, 7 prior hashes : [m2, m5, m4, m1, m3]
> worker thread : [m1, m2, m3, m5, m4]
> worker thread : [m5, m3, m1, m4, m2]
> {noformat}
> (5 objects with no {{hashCode()}} override, added to a {{HashSet}},
> iterated.) A fresh single-threaded JVM repeating identical work reproduces
> the same order — but the candidate order changes when the compile runs on a
> different thread or after a different amount of prior work. In practice that
> means a *long-lived, reused Gradle daemon*, *parallel compile workers*, or
> simply *a different set of classes compiled earlier in the same JVM* can each
> shift the order. Reproducible builds require identical output from identical
> sources regardless of that state. The nondeterministic reflection order in
> GROOVY-12149 also perturbs the sequence of {{hashCode()}} calls, so the two
> defects amplify each other.
> h3. Where the order reaches generated code
> Most callers reduce to a single candidate and raise an ambiguity error
> otherwise ({{StaticTypeCheckingVisitor:4397}}, {{:3581}},
> {{findMethodOrFail:5694}}) — those are safe, since an ambiguity error emits
> no bytecode. But three callers accept a multi-candidate list *without error*:
> # *Union-type receiver (GROOVY-8965), {{StaticTypeCheckingVisitor:4385}}* —
> the case that _deliberately_ fills the set with one best method per union
> delegate, and so is a non-error path by construction:
> {code:java}
> if (mn.size() > 1 && obj instanceof UnionTypeClassNode) {
> ClassNode returnType = mn.stream().map(MethodNode::getReturnType)
>
> .reduce(WideningCategories::lowestUpperBound).get();
> call.putNodeMetaData(DYNAMIC_RESOLUTION, returnType);
> {code}
> {{Stream.reduce}} folds in list order, and {{lowestUpperBound}} is not
> reliably order-insensitive (folding interface types can build differing
> synthetic LUB nodes). The resulting inferred type drives casts and return
> types in emitted bytecode.
> # *Method pointers / method references ({{::}}),
> {{StaticTypeCheckingVisitor:3236-3268}}* — on more than one candidate it
> calls {{extension.handleAmbiguousMethods}}, whose default implementation
> ({{TypeCheckingExtension:190}}) returns the list unchanged, then applies the
> same order-sensitive {{lowestUpperBound}} fold to type the closure.
> # *Macro dispatch, {{MacroCallTransformingVisitor:106-119}}* —
> {{findMacroMethods}} returns {{chooseBestMethod(...)}} directly and the
> caller loops over the candidates until one succeeds, so *the first candidate
> wins*. When two macro methods both apply, identity-hash order decides which
> one expands the call — a _different generated AST_, not merely a different
> byte layout.
> Ambiguity *error messages* also list candidates in this order, so diagnostics
> are unstable too.
> h3. Proposed fix
> Use an insertion-ordered set:
> {code:java}
> Set<MethodNode> bestMethods = new LinkedHashSet<>();
> {code}
> {{MethodNode}} has identity {{equals}}/{{hashCode}}, so this is a
> semantics-preserving drop-in — deduplication behaviour is unchanged. It
> yields a _meaningful_ order rather than an arbitrary one: candidates follow
> the {{duckType}} loop, i.e. the union's declared delegate order.
> {{StaticTypeCheckingVisitor:671}} already uses {{LinkedHashSet<MethodNode>}}
> for {{PV_METHODS_ACCESS}}, so this matches existing practice.
> h3. Suggested test
> A {{@CompileStatic}} union-type receiver (per GROOVY-8965) whose delegates
> declare the same method with different return types, asserting the inferred
> {{DYNAMIC_RESOLUTION}} type; and a macro case with two applicable macro
> methods, asserting which expansion wins. To exercise the path-dependence, run
> the compile on a worker thread and/or after a varying number of identity-hash
> allocations — with the {{HashSet}} the selection shifts, with
> {{LinkedHashSet}} it does not.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
