[C++][Python] .take silently overflow on list array (when casting to large_list is needed)

[asfimport]

reproducer below

import numpy as np
import pyarrow as pa
arr = pa.array([np.arange(x).astype(np.int8) for x in range(6)])
nb_repeat = 2**32 // arr.offsets.to_numpy()[-1]
indices = pa.array(np.repeat(np.arange(len(arr)), nb_repeat))
big_arr = arr.take(indices)
print(big_arr.offsets[-5:])
big_arr.validate() # hopefully this can catch it 

[
 -21,
 -16,
 -11,
 -6,
 -1
]
---------------------------------------------------------------------------
ArrowInvalid Traceback (most recent call last)
<ipython-input-1-09503f9cbb04> in <module>
 6 big_arr = arr.take(indices)
 7 print(big_arr.offsets[-5:])
----> 8 big_arr.validate()

/opt/conda/envs/model/lib/python3.7/site-packages/pyarrow/array.pxi in pyarrow.lib.Array.validate()

/opt/conda/envs/model/lib/python3.7/site-packages/pyarrow/error.pxi in pyarrow.lib.check_status()

ArrowInvalid: Negative offsets in list array

and it works fine with large_array (as expected) :

import numpy as np
import pyarrow as pa
arr = pa.array([np.arange(x).astype(np.int8) for x in range(6)], type=pa.large_list(pa.int8()))
nb_repeat = 2**32 // arr.offsets.to_numpy()[-1]
indices = pa.array(np.repeat(np.arange(len(arr)), nb_repeat))
big_arr = arr.take(indices)
print(big_arr.offsets[-5:])
big_arr.validate()
[
 4294967275,
 4294967280,
 4294967285,
 4294967290,
 4294967295
]

Reporter: Artem KOZHEVNIKOV / @artemru

Related issues:

• [Python] pyarrow.concat_arrays segfaults if a resulting StringArray's capacity overflows (is related to)

_{Note: This issue was originally created as ARROW-10494. Please see the migration documentation for further details.}

[thisisnic]

Haven't fully tried reproducing as I've got an OOM-killer running on my machine and this requires 16GB+ of RAM to repro, but a quick analysis of the code shows that this might still be an issue. Needs properly reproducing to be sure. If it is an issue, a quick Claude analysis suggested the below fix (needs verifying).

---

ListSelectionImpl::GenerateOutput() accumulates offset as offset_type (which is int32_t for ListType) with no overflow check:

arrow/cpp/src/arrow/compute/kernels/vector_selection_internal.cc

Lines 572 to 579 in d091957

	offset_type offset = 0;
	Adapter adapter(this);
	RETURN_NOT_OK(adapter.Generate(
	[&](int64_t index) {
	offset_builder.UnsafeAppend(offset);
	offset_type value_offset = typed_values.value_offset(index);
	offset_type value_length = typed_values.value_length(index);
	offset += value_length;

Compare with VarBinarySelectionImpl which does check for overflow and returns Status::Invalid("Take operation overflowed binary array capacity"):

arrow/cpp/src/arrow/compute/kernels/vector_selection_internal.cc

Lines 520 to 523 in d091957

	if (Adapter::is_take &&
	ARROW_PREDICT_FALSE(static_cast<int64_t>(offset) +
	static_cast<int64_t>(val_size)) > kOffsetLimit) {
	return Status::Invalid("Take operation overflowed binary array capacity");

So the var-binary take path has overflow protection but the list take path doesn't. The fix would be adding the same overflow guard in ListSelectionImpl::GenerateOutput().