[
https://issues.apache.org/jira/browse/GROOVY-12412?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Paul King updated GROOVY-12412:
-------------------------------
Description:
Range indexing behaves differently depending on the receiver, on which
{{Range}} implementation
the bounds happen to produce, and on whether the range is the only index or one
of several. The
differences are not documented anywhere and no test pins them. This issue
brings all of them into
line and adds the missing tests.
Six receivers support subscripting by index: {{List}}, {{ListWithDefault}},
object arrays,
primitive arrays, {{CharSequence}} and {{Matcher}}. Measured over eighteen
subscript forms, they
disagree on twelve of them today.
h3. The rule that should hold
A range used as an index has its bounds resolved against the size of the
receiver, whether it is
the only index or one of several: a negative bound counts back from the end,
both exclusive forms
drop the right element, a range written high to low reverses the result, and an
empty range
contributes nothing. Anything that is not a range, including a nested list of
indices, is walked
element by element, with negative values still counting from the end.
h3. Symptoms
{code:groovy}
def list = (1..8).toList()
def ints = (1..8) as int[]
def objs = (1..8) as Integer[]
def m = 'a1b2c3d4' =~ /[a-z]\d/
// 1. a nested range on a List ignores a negative bound (regression, 5.0.0)
assert list[0..2, 3..-1] == [1, 2, 3, 4, 5, 6, 7, 8] // actual [1, 2, 3, 4,
3, 2, 1, 8]
// 2. a primitive array resolves a sole range only when it is an IntRange
assert ints[3..-1] == [4, 5, 6, 7, 8] // ok
assert ints[3L..-1L] == [4, 5, 6, 7, 8] // actual [4, 3, 2, 1, 8]
assert ints[0, 3..-1] == [1, 4, 5, 6, 7, 8] // actual [1, 4, 3, 2,
1, 8]
// 3. a NumberRange cannot tell a negative bound from a reversed range
assert list[3L..-1L] == [4, 5, 6, 7, 8] // actual [8, 7, 6, 5, 4]
assert list[2L..0L] == [3, 2, 1] // actual [1, 2, 3]
// 4. Matcher loses an element on every exclusive form, ignores reversal,
// and rejects a nested collection of indices
assert m[1..<3] == ['b2', 'c3'] // actual ['b2']
assert m[3..1] == ['d4', 'c3', 'b2'] // actual ['b2', 'c3',
'd4']
m[0, [1, 3]] // GroovyCastException
// 5. a nested empty range adds a stray element on object arrays and strings
assert objs[0..1, 2..<2] == [1, 2] // actual [1, 2, 3]
assert 'abcdefgh'[0..2, 2..<2] == 'abc' // actual 'abcc'
{code}
h3. Root causes
*1. {{DefaultGroovyMethods.getAt(List, Collection)}} lost its dynamic
dispatch.* Commit
87b4109418 ("minor refactor - no need to funnel through InvokerHelper here",
2022-08-24, no JIRA
reference) replaced {{InvokerHelper.invokeMethod(self, "getAt", value)}} with a
direct call to the
{{Collection}} overload. The dynamic call let the MOP select {{getAt(List,
Range)}} for a nested
range; the direct call recurses and walks the range's own elements as indices.
This is the only
regression in this issue: it is not on {{GROOVY_4_0_X}} and first shipped in
5.0.0. The sibling
{{getAt(ListWithDefault, Collection)}} still uses the dynamic form, which is why
{{ListWithDefault}} was never affected.
*2. Primitive arrays resolve only an {{IntRange}}.* The sixteen
{{getAt(prim[], Range<?>)}} and {{getAt(prim[], ObjectRange)}} overloads, and
the shared helper
behind the {{Collection}} overloads, walk the range literally. Only the typed
{{getAt(prim[], IntRange)}} overloads resolve bounds. Present in every 4.x and
5.x release.
*3. {{NumberRange.subListBorders}} reads its normalised bounds.* The
constructor computes
{{reverse}} and stores {{from}} and {{to}} in ascending order, so by the time
borders are computed
{{3L..-1L}} is indistinguishable from {{-1L..3L}}. {{IntRange}} keeps the raw
order in its fields
and presents the normalised view through {{getFrom()}} and {{getTo()}}, which
is exactly why it
gets negative indexing right. Both then share {{IntRange.subListBorders}}. Any
bound that is not
an {{Integer}} produces a {{NumberRange}}, so this covers long, short, byte,
{{BigInteger}} and
decimal bounds. Present in every 4.x and 5.x release.
*4. {{StringGroovyMethods.getAt(Matcher, Collection)}} rebuilds a range from
resolved borders.*
It resolves borders only when the whole index argument is an {{IntRange}}, then
does
{{new IntRange(((IntRange) indices).getInclusive(), info.from, info.to - 1)}}.
Re-applying the
original inclusivity to an already resolved bound drops an element, and
{{info.reverse}} is
discarded. It also has no branch for a nested collection. Present in every 4.x
and 5.x release.
*5. {{EmptyRange}} implements {{Range}}, so a nested empty range reaches
{{subListBorders(int, Range)}}, which returns a one element window.* This
affects object arrays
and {{CharSequence}}. The {{List}} path avoided it only by accident of the code
in cause 1, so the
guard is needed there too once that is fixed.
h3. Fix
|| file || change ||
| {{groovy/lang/NumberRange.java}} | recover the written bound order from the
{{reverse}} flag before computing borders |
| {{runtime/ArrayGroovyMethods.java}} | new private {{primitiveArraySubList}}
resolves a range against the array length and handles {{EmptyRange}}; the
sixteen sole-index overloads and the nested path both use it |
| {{runtime/DefaultGroovyMethods.java}} | {{getAt(List, Collection)}}
dispatches a nested range to the {{Range}} overload, with an {{EmptyRange}}
guard |
| {{runtime/StringGroovyMethods.java}} | {{EmptyRange}} guard on the
{{CharSequence}} path; {{getAt(Matcher, Collection)}} rewritten to read the
resolved window and to accept nested collections |
The eight {{getAt(prim[], IntRange)}} overloads are untouched: they rebuild a
range through
{{subListRange}}, which does correctly undo the inclusivity flags, and they
handle an empty window
correctly.
The literal walk remains available on every receiver by passing a plain list of
indices, for
example {{a[(3..-1).toList()]}}, which still yields {{[4, 3, 2, 1, 8]}}.
h3. Behaviour changes that are not regression fixes
* A {{NumberRange}} index now behaves like the equivalent {{IntRange}} on every
receiver. Code
relying on {{list[3L..-1L]}} returning a reversed window changes.
* A sole {{NumberRange}} or {{ObjectRange}} index on a primitive array is now
resolved rather than
walked.
* {{matcher[0, [1, 2]]}} now returns a result. {{RegularExpressionsTest}}
carried
{{shouldFail \{ matcher[0, [1, 2]] \}}}, added in 2008 under GROOVY-3028,
which reads as
characterising the behaviour of the day rather than arguing the form should
be rejected. It has
been replaced with a positive assertion, since every other receiver accepts
it.
* The deprecated protected {{primitiveArrayGet}} helpers in
{{DefaultGroovyMethods}} still hold
the old literal logic. Nothing in Groovy calls them; they are kept for binary
compatibility.
h3. Verification
* Eighteen subscript forms measured against all six receivers, results
normalised to the positions
selected: twelve forms disagreed before, none disagree after.
* Core {{:test}}: 18342 passed, 68 skipped, 0 failed. All 37 module suites:
5691 passed, 0 failed.
* New tests: {{GroovyMethodsTest.testGetAtMultipleIndicesIncludingRanges}} and
{{testGetAtSingleRangeResolvesBoundsOnEveryReceiver}} cover {{List}},
{{ListWithDefault}},
{{Integer[]}}, all eight primitive array types and {{CharSequence}} over
negative, exclusive,
reversed, empty and {{ObjectRange}} bounds in both positions.
{{RegularExpressionsTest.testMatcherRangeIndicesMatchOtherAggregates}} does
the same for
{{Matcher}} and asserts that each index expression selects the same positions
as from a list of
the same size.
* New executed javadoc examples on {{getAt(int[], Collection)}}, {{getAt(int[],
Range)}} and
{{getAt(Matcher, Collection)}}, so the corrected behaviour is documented as
well as tested.
h3. Why this belongs in 6.0.0
Item 1 alone is a regression against 4.x and would justify a fix on its own.
The remaining items
are long standing, individually obscure, and each looked too marginal to
disturb an RC. Taken
together they are what makes the first item a regression rather than a quirk:
the same subscript
written three ways over the same eight elements returns three different
answers, and which answer
you get depends on whether a bound happened to be an {{int}} or a {{long}}, and
on whether the
range stood alone or sat beside another index. Fixing them as one change is
what produces a rule
that can be stated in a sentence and documented. Deferring the rest to 7 would
mean shipping 6
with the regression fixed and the surrounding inconsistencies intact, then
changing the same
methods again a major version later.
was:
In a subscript with several indices, a {{Range}} with a negative bound is no
longer resolved
against the size when the receiver is a {{List}}. The range is walked literally
instead.
{code:groovy}
assert (1..8)[3..-1] == [4, 5, 6, 7, 8] // single range:
still correct
assert 'abcdefgh'[0..2, 3..-1] == 'abcdefgh' // String: still
correct
assert (1..8)[0..2, 3..-1] == [1, 2, 3, 4, 5, 6, 7, 8] // fails from 5.0.0
// actual: [1, 2, 3, 4, 3, 2, 1, 8] -- 3..-1 walked as the indices 3, 2, 1, 0,
-1
{code}
An all-positive multi-index subscript is unaffected: {{(1..8)[0..2, 3..7]}}
still gives the
whole list.
h3. Scope
|| receiver || 4.0.33 || 6.0.0-RC-3 ||
| {{List}} | {{[1, 2, 3, 4, 5, 6, 7, 8]}} | {{[1, 2, 3, 4, 3, 2, 1, 8]}} |
| {{Integer[]}} | {{[1, 2, 3, 4, 5, 6, 7, 8]}} | {{[1, 2, 3, 4, 5, 6, 7, 8]}} |
| {{String}} | {{abcdefgh}} | {{abcdefgh}} |
| {{ListWithDefault}} | {{[1, 2, 3, 4, 5, 6, 7, 8]}} | {{[1, 2, 3, 4, 5, 6, 7,
8]}} |
| {{int[]}} | {{[1, 2, 3, 4, 3, 2, 1, 8]}} | {{[1, 2, 3, 4, 3, 2, 1, 8]}} |
Only the {{List}} row changed. 5.0.6 behaves the same as 6.0.0-RC-3. The
{{int[]}} row was
already inconsistent in 4.x through the primitive-array path, which looks like
a separate and
older problem.
h3. Cause
Commit 87b4109418 ("minor refactor - no need to funnel through InvokerHelper
here",
2022-08-24, no JIRA reference) changed one line in
{{DefaultGroovyMethods.getAt(List, Collection)}}:
{code:java}
- answer.addAll((List<T>) InvokerHelper.invokeMethod(self, "getAt", value));
+ answer.addAll(getAt(self, (Collection) value));
{code}
The dynamic call let the MOP select the most specific overload for the value's
runtime type, so
a {{Range}} element reached {{getAt(List, Range)}}, which resolves the bounds
through
{{subListBorders}}. The direct call binds {{getAt(List, Collection)}} at
compile time, so it
recurses and treats the range's own elements as indices.
The commit was never applied to {{GROOVY_4_0_X}}, so the 4.0.x line is
unaffected. It first
shipped in 5.0.0.
The sibling method immediately above it, {{getAt(ListWithDefault,
Collection)}}, still uses the
{{InvokerHelper.invokeMethod}} form, which is why {{ListWithDefault}} continues
to resolve
negative bounds. That asymmetry within the same file, together with the "minor
refactor"
wording, suggests the behaviour change was not intended.
h3. Suggested fix
Restore overload selection for {{Range}} values, either by reinstating the
dynamic call or by
testing for {{Range}} before the {{Collection}} branch, and add a test covering
a negative bound
in a multi-index subscript for {{List}}, {{Object[]}}, {{String}} and
{{ListWithDefault}}.
Found while re-testing the examples in the
[Using Gatherers with Groovy|https://groovy.apache.org/blog/groovy-gatherers]
blog post, where
{{assert (1..8)[0..2, 3..-1] == 1..8}} passes under Groovy 4 and fails from
5.0.0.
> Improve consistency of numerous Range indexing edge cases
> ---------------------------------------------------------
>
> Key: GROOVY-12412
> URL: https://issues.apache.org/jira/browse/GROOVY-12412
> Project: Groovy
> Issue Type: Bug
> Reporter: Paul King
> Assignee: Paul King
> Priority: Major
>
> Range indexing behaves differently depending on the receiver, on which
> {{Range}} implementation
> the bounds happen to produce, and on whether the range is the only index or
> one of several. The
> differences are not documented anywhere and no test pins them. This issue
> brings all of them into
> line and adds the missing tests.
> Six receivers support subscripting by index: {{List}}, {{ListWithDefault}},
> object arrays,
> primitive arrays, {{CharSequence}} and {{Matcher}}. Measured over eighteen
> subscript forms, they
> disagree on twelve of them today.
> h3. The rule that should hold
> A range used as an index has its bounds resolved against the size of the
> receiver, whether it is
> the only index or one of several: a negative bound counts back from the end,
> both exclusive forms
> drop the right element, a range written high to low reverses the result, and
> an empty range
> contributes nothing. Anything that is not a range, including a nested list of
> indices, is walked
> element by element, with negative values still counting from the end.
> h3. Symptoms
> {code:groovy}
> def list = (1..8).toList()
> def ints = (1..8) as int[]
> def objs = (1..8) as Integer[]
> def m = 'a1b2c3d4' =~ /[a-z]\d/
> // 1. a nested range on a List ignores a negative bound (regression, 5.0.0)
> assert list[0..2, 3..-1] == [1, 2, 3, 4, 5, 6, 7, 8] // actual [1, 2, 3, 4,
> 3, 2, 1, 8]
> // 2. a primitive array resolves a sole range only when it is an IntRange
> assert ints[3..-1] == [4, 5, 6, 7, 8] // ok
> assert ints[3L..-1L] == [4, 5, 6, 7, 8] // actual [4, 3, 2, 1,
> 8]
> assert ints[0, 3..-1] == [1, 4, 5, 6, 7, 8] // actual [1, 4, 3, 2,
> 1, 8]
> // 3. a NumberRange cannot tell a negative bound from a reversed range
> assert list[3L..-1L] == [4, 5, 6, 7, 8] // actual [8, 7, 6, 5,
> 4]
> assert list[2L..0L] == [3, 2, 1] // actual [1, 2, 3]
> // 4. Matcher loses an element on every exclusive form, ignores reversal,
> // and rejects a nested collection of indices
> assert m[1..<3] == ['b2', 'c3'] // actual ['b2']
> assert m[3..1] == ['d4', 'c3', 'b2'] // actual ['b2', 'c3',
> 'd4']
> m[0, [1, 3]] // GroovyCastException
> // 5. a nested empty range adds a stray element on object arrays and strings
> assert objs[0..1, 2..<2] == [1, 2] // actual [1, 2, 3]
> assert 'abcdefgh'[0..2, 2..<2] == 'abc' // actual 'abcc'
> {code}
> h3. Root causes
> *1. {{DefaultGroovyMethods.getAt(List, Collection)}} lost its dynamic
> dispatch.* Commit
> 87b4109418 ("minor refactor - no need to funnel through InvokerHelper here",
> 2022-08-24, no JIRA
> reference) replaced {{InvokerHelper.invokeMethod(self, "getAt", value)}} with
> a direct call to the
> {{Collection}} overload. The dynamic call let the MOP select {{getAt(List,
> Range)}} for a nested
> range; the direct call recurses and walks the range's own elements as
> indices. This is the only
> regression in this issue: it is not on {{GROOVY_4_0_X}} and first shipped in
> 5.0.0. The sibling
> {{getAt(ListWithDefault, Collection)}} still uses the dynamic form, which is
> why
> {{ListWithDefault}} was never affected.
> *2. Primitive arrays resolve only an {{IntRange}}.* The sixteen
> {{getAt(prim[], Range<?>)}} and {{getAt(prim[], ObjectRange)}} overloads, and
> the shared helper
> behind the {{Collection}} overloads, walk the range literally. Only the typed
> {{getAt(prim[], IntRange)}} overloads resolve bounds. Present in every 4.x
> and 5.x release.
> *3. {{NumberRange.subListBorders}} reads its normalised bounds.* The
> constructor computes
> {{reverse}} and stores {{from}} and {{to}} in ascending order, so by the time
> borders are computed
> {{3L..-1L}} is indistinguishable from {{-1L..3L}}. {{IntRange}} keeps the raw
> order in its fields
> and presents the normalised view through {{getFrom()}} and {{getTo()}}, which
> is exactly why it
> gets negative indexing right. Both then share {{IntRange.subListBorders}}.
> Any bound that is not
> an {{Integer}} produces a {{NumberRange}}, so this covers long, short, byte,
> {{BigInteger}} and
> decimal bounds. Present in every 4.x and 5.x release.
> *4. {{StringGroovyMethods.getAt(Matcher, Collection)}} rebuilds a range from
> resolved borders.*
> It resolves borders only when the whole index argument is an {{IntRange}},
> then does
> {{new IntRange(((IntRange) indices).getInclusive(), info.from, info.to -
> 1)}}. Re-applying the
> original inclusivity to an already resolved bound drops an element, and
> {{info.reverse}} is
> discarded. It also has no branch for a nested collection. Present in every
> 4.x and 5.x release.
> *5. {{EmptyRange}} implements {{Range}}, so a nested empty range reaches
> {{subListBorders(int, Range)}}, which returns a one element window.* This
> affects object arrays
> and {{CharSequence}}. The {{List}} path avoided it only by accident of the
> code in cause 1, so the
> guard is needed there too once that is fixed.
> h3. Fix
> || file || change ||
> | {{groovy/lang/NumberRange.java}} | recover the written bound order from the
> {{reverse}} flag before computing borders |
> | {{runtime/ArrayGroovyMethods.java}} | new private {{primitiveArraySubList}}
> resolves a range against the array length and handles {{EmptyRange}}; the
> sixteen sole-index overloads and the nested path both use it |
> | {{runtime/DefaultGroovyMethods.java}} | {{getAt(List, Collection)}}
> dispatches a nested range to the {{Range}} overload, with an {{EmptyRange}}
> guard |
> | {{runtime/StringGroovyMethods.java}} | {{EmptyRange}} guard on the
> {{CharSequence}} path; {{getAt(Matcher, Collection)}} rewritten to read the
> resolved window and to accept nested collections |
> The eight {{getAt(prim[], IntRange)}} overloads are untouched: they rebuild a
> range through
> {{subListRange}}, which does correctly undo the inclusivity flags, and they
> handle an empty window
> correctly.
> The literal walk remains available on every receiver by passing a plain list
> of indices, for
> example {{a[(3..-1).toList()]}}, which still yields {{[4, 3, 2, 1, 8]}}.
> h3. Behaviour changes that are not regression fixes
> * A {{NumberRange}} index now behaves like the equivalent {{IntRange}} on
> every receiver. Code
> relying on {{list[3L..-1L]}} returning a reversed window changes.
> * A sole {{NumberRange}} or {{ObjectRange}} index on a primitive array is now
> resolved rather than
> walked.
> * {{matcher[0, [1, 2]]}} now returns a result. {{RegularExpressionsTest}}
> carried
> {{shouldFail \{ matcher[0, [1, 2]] \}}}, added in 2008 under GROOVY-3028,
> which reads as
> characterising the behaviour of the day rather than arguing the form should
> be rejected. It has
> been replaced with a positive assertion, since every other receiver accepts
> it.
> * The deprecated protected {{primitiveArrayGet}} helpers in
> {{DefaultGroovyMethods}} still hold
> the old literal logic. Nothing in Groovy calls them; they are kept for
> binary compatibility.
> h3. Verification
> * Eighteen subscript forms measured against all six receivers, results
> normalised to the positions
> selected: twelve forms disagreed before, none disagree after.
> * Core {{:test}}: 18342 passed, 68 skipped, 0 failed. All 37 module suites:
> 5691 passed, 0 failed.
> * New tests: {{GroovyMethodsTest.testGetAtMultipleIndicesIncludingRanges}} and
> {{testGetAtSingleRangeResolvesBoundsOnEveryReceiver}} cover {{List}},
> {{ListWithDefault}},
> {{Integer[]}}, all eight primitive array types and {{CharSequence}} over
> negative, exclusive,
> reversed, empty and {{ObjectRange}} bounds in both positions.
> {{RegularExpressionsTest.testMatcherRangeIndicesMatchOtherAggregates}} does
> the same for
> {{Matcher}} and asserts that each index expression selects the same
> positions as from a list of
> the same size.
> * New executed javadoc examples on {{getAt(int[], Collection)}},
> {{getAt(int[], Range)}} and
> {{getAt(Matcher, Collection)}}, so the corrected behaviour is documented as
> well as tested.
> h3. Why this belongs in 6.0.0
> Item 1 alone is a regression against 4.x and would justify a fix on its own.
> The remaining items
> are long standing, individually obscure, and each looked too marginal to
> disturb an RC. Taken
> together they are what makes the first item a regression rather than a quirk:
> the same subscript
> written three ways over the same eight elements returns three different
> answers, and which answer
> you get depends on whether a bound happened to be an {{int}} or a {{long}},
> and on whether the
> range stood alone or sat beside another index. Fixing them as one change is
> what produces a rule
> that can be stated in a sentence and documented. Deferring the rest to 7
> would mean shipping 6
> with the regression fixed and the surrounding inconsistencies intact, then
> changing the same
> methods again a major version later.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
