Support `reverse` for ListView

[brancz]

Is your feature request related to a problem or challenge?

ListView, as opposed to List, is not supported by the reverse function, yet.

Describe the solution you'd like

Unless I'm misunderstanding the ListView spec, I think this should be possible by performing offset + size - 1 to compute the new offsets and just size * -1.

Hopefully, downstream usages use iterators and not regular for loops that assume strictly increasing indexes, but I'd call that a bug if they didn't.

Describe alternatives you've considered

Cast to List instead, however, based on some profiling we've done in the other direction (converting List to ListView), this is a terrible idea.

Additional context

No response

[vegarsti]

take

[vegarsti]

I don't think negative sizes would be possible currently, as sizes are ScalarBuffer<OffsetSize> where offsets rely on being usize, e.g. supports as_usize().
https://github.com/apache/arrow-rs/blob/cd61ead4f8f4365e9406f7f3d1056d195159e748/arrow-array/src/array/list_view_array.rs#L111

https://github.com/apache/arrow-rs/blob/cd61ead4f8f4365e9406f7f3d1056d195159e748/arrow-array/src/array/list_view_array.rs#L293-L294

[brancz]

@alamb could you chime in whether the implementation is in the spirit of the spec? As far as I understood the spec, size should be possible to be a signed integer, no?

[vegarsti]

In the meantime I might implement it using a less efficient approach, and then add a benchmark so that it will be satisfying to move to this better approach if we get the blessing to do so! But that requires some type changes and thus releases in arrow to be unblocked.

[vegarsti]

I've pushed a PR to implement reverse #18424 (using take over the values , not operations on offsets and sizes) and a PR with a benchmark #18425.

[vegarsti]

On second thought, maybe it's better that reverse is not supported for ListView until it can be done without materializing (which my PR does)?

[Jefffrey]

@alamb could you chime in whether the implementation is in the spirit of the spec? As far as I understood the spec, size should be possible to be a signed integer, no?

I think the spec allows signed integer for compatibility with Java (which doesn't have an unsigned integer type). Indeed if I try a negative size on pyarrow it sees the resultant array as invalid:

>>> import pyarrow as pa
>>> pa.__version__
'22.0.0'
>>> values = pa.array([1, 2, 3, 4])
>>> offsets = pa.array([0, 1, 2])
>>> sizes = pa.array([2, 2, -2])
>>> pa.ListViewArray.from_arrays(offsets, sizes, values)
<pyarrow.lib.ListViewArray object at 0x1023caa40>
[
  [
    1,
    2
  ],
  [
    2,
    3
  ],
<Invalid array: Array length is negative>
]

So I don't think it'll be as simple as negating the size.

[alamb]

Hopefully, downstream usages use iterators and not regular for loops that assume strictly increasing indexes, but I'd call that a bug if they didn't.

I think the whole point of ListView is that it has offset + length precisely so that the indexes do not have to be strictly increasing

List / LargeList require strictly increasing indexes as there are no separately encoded lengths