Skip to content

Commit 300dbe3

Browse files
committed
fix(arrow/array): clamp the RunEndEncoded final run end before the overflow check
The logical-length clamp fixed the sliced-array overshoot but the overflow check still used the input's unclamped physical final run end, so a valid slice whose physical run end is near the run-end type limit was rejected before the clamp applied. Clamp the normalized final run end to the input's logical length up front and use it for both the overflow check and the written final run end. Adds a near-int16-limit boundary regression test. Signed-off-by: Madan Kumar <[email protected]>
1 parent bf271c1 commit 300dbe3

2 files changed

Lines changed: 61 additions & 24 deletions

File tree

‎arrow/array/concat.go‎

Lines changed: 31 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -861,44 +861,51 @@ func updateRuns[T int16 | int32 | int64](inputData []arrow.ArrayData, inputBuffe
861861
// can fold the end and beginning of each array we're concatenating
862862
// into a single run
863863
pos := 0
864-
logicalLen := T(0)
865864
for i, buf := range inputBuffers {
866865
if buf.Len() == 0 {
867866
continue
868867
}
869868
src := arrow.GetData[T](buf.Bytes())
870-
logicalLen += T(inputData[i].Len())
869+
offset := inputData[i].Offset()
870+
871+
// A slice can end in the middle of a run, leaving this input's final physical
872+
// run end past its logical length. Clamp the normalized final run end to the
873+
// input's logical length before both the overflow check and the output write:
874+
// otherwise a valid near-limit slice trips a false overflow, and the written
875+
// run end overshoots (shifting every following array's run ends).
876+
finalEnd := int(src[len(src)-1]) - offset
877+
if finalEnd > inputData[i].Len() {
878+
finalEnd = inputData[i].Len()
879+
}
880+
871881
if pos == 0 {
872882
pos += copy(output, src)
873883
// normalize the first run ends by subtracting the offset
874884
for j := 0; j < pos; j++ {
875-
output[j] -= T(inputData[i].Offset())
876-
}
877-
} else {
878-
lastEnd := output[pos-1]
879-
// we can check the last runEnd in the src and add it to the
880-
// last value that we're adjusting them all by to see if we
881-
// are going to overflow
882-
if uint64(lastEnd)+uint64(int(src[len(src)-1])-inputData[i].Offset()) > uint64(maxOf[T]()) {
883-
return fmt.Errorf("%w: overflow in run-length-encoded run ends concat", arrow.ErrInvalid)
885+
output[j] -= T(offset)
884886
}
887+
output[pos-1] = T(finalEnd)
888+
continue
889+
}
885890

886-
// adjust all of the run ends by first normalizing them (e - data[i].offset)
887-
// then adding the previous value we ended on. Since the offset
888-
// is a logical length offset it should be accurate to just subtract
889-
// it from each value.
890-
for j, e := range src {
891-
output[pos+j] = lastEnd + T(int(e)-inputData[i].Offset())
892-
}
893-
pos += len(src)
891+
lastEnd := output[pos-1]
892+
// check whether adding this input's clamped final run end to the previous
893+
// end will overflow the run-end type
894+
if uint64(lastEnd)+uint64(finalEnd) > uint64(maxOf[T]()) {
895+
return fmt.Errorf("%w: overflow in run-length-encoded run ends concat", arrow.ErrInvalid)
894896
}
895897

896-
// a slice can end in the middle of a run, so this input's final physical run end
897-
// can reach past its logical length; clamp it to keep the run ends within bounds and
898-
// stop the overshoot from shifting every following array's run ends.
899-
if output[pos-1] > logicalLen {
900-
output[pos-1] = logicalLen
898+
// adjust all of the run ends by first normalizing them (e - data[i].offset)
899+
// then adding the previous value we ended on. Since the offset
900+
// is a logical length offset it should be accurate to just subtract
901+
// it from each value.
902+
for j, e := range src {
903+
output[pos+j] = lastEnd + T(int(e)-offset)
901904
}
905+
pos += len(src)
906+
// the write above uses the unclamped physical end for the final run; set it
907+
// to the clamped logical end.
908+
output[pos-1] = lastEnd + T(finalEnd)
902909
}
903910
return nil
904911
}

‎arrow/array/concat_test.go‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -862,6 +862,36 @@ func TestConcatRunEndEncodedMidRunSlice(t *testing.T) {
862862
assert.Equal(t, []int64{100, 100, 200, 700, 700}, got)
863863
}
864864

865+
func TestConcatRunEndEncodedNearTypeLimitSlice(t *testing.T) {
866+
// A sliced input whose physical final run end is near the run-end type limit must
867+
// not trip a false overflow: the overflow check has to use the clamped logical end,
868+
// not the physical one. int16 prefix of 32760 + a 1-element slice of a physical
869+
// 32767-length run should yield 32761, not an overflow error.
870+
mem := memory.NewCheckedAllocator(memory.DefaultAllocator)
871+
defer mem.AssertSize(t, 0)
872+
873+
prefixBldr := array.NewRunEndEncodedBuilder(mem, arrow.PrimitiveTypes.Int16, arrow.PrimitiveTypes.Int64)
874+
defer prefixBldr.Release()
875+
prefixBldr.Append(32760)
876+
prefixBldr.ValueBuilder().(*array.Int64Builder).Append(1)
877+
prefix := prefixBldr.NewArray()
878+
defer prefix.Release()
879+
880+
bigBldr := array.NewRunEndEncodedBuilder(mem, arrow.PrimitiveTypes.Int16, arrow.PrimitiveTypes.Int64)
881+
defer bigBldr.Release()
882+
bigBldr.Append(32767)
883+
bigBldr.ValueBuilder().(*array.Int64Builder).Append(2)
884+
big := bigBldr.NewArray()
885+
defer big.Release()
886+
oneElem := array.NewSlice(big, 0, 1) // first element of the 32767-length run
887+
defer oneElem.Release()
888+
889+
result, err := array.Concatenate([]arrow.Array{prefix, oneElem}, mem)
890+
require.NoError(t, err)
891+
defer result.Release()
892+
assert.EqualValues(t, 32761, result.Len())
893+
}
894+
865895
func TestConcatAlmostOverflowRunEndEncoding(t *testing.T) {
866896
tests := []struct {
867897
offsetType arrow.DataType

0 commit comments

Comments
 (0)