This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-go.git
The following commit(s) were added to refs/heads/main by this push:
new 22bec19f fix(array): validate run-end encoded invariants (#992)
22bec19f is described below
commit 22bec19f17a1311eba76797a1516b1eeeed79e7f
Author: Minh Vu <[email protected]>
AuthorDate: Fri Jul 24 19:44:23 2026 +0200
fix(array): validate run-end encoded invariants (#992)
## Summary
- add RunEndEncoded Validate and ValidateFull implementations
- validate parent and child invariants, logical coverage, and strict
run-end monotonicity
- add regression tests for short coverage and duplicate run ends
## Why
Run-end encoded helpers already assume that run ends are strictly
increasing and cover the logical range. Today malformed arrays can pass
validation even when those invariants do not hold.
## Validation
- go test ./arrow/array ./arrow/encoded
---
arrow/array/encoded.go | 88 ++++++++++++++++++++++++++++++++++
arrow/array/encoded_test.go | 113 ++++++++++++++++++++++++++++++++++++++++++++
arrow/encoded/ree_utils.go | 4 ++
3 files changed, 205 insertions(+)
diff --git a/arrow/array/encoded.go b/arrow/array/encoded.go
index 8d628ffc..05d5bda5 100644
--- a/arrow/array/encoded.go
+++ b/arrow/array/encoded.go
@@ -23,6 +23,7 @@ import (
"reflect"
"github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
"github.com/apache/arrow-go/v18/arrow/encoded"
"github.com/apache/arrow-go/v18/arrow/internal/debug"
"github.com/apache/arrow-go/v18/arrow/memory"
@@ -57,6 +58,14 @@ func NewRunEndEncodedData(data arrow.ArrayData)
*RunEndEncoded {
func (r *RunEndEncoded) Values() arrow.Array { return r.values }
func (r *RunEndEncoded) RunEndsArr() arrow.Array { return r.ends }
+func (r *RunEndEncoded) Validate() error {
+ return validateRunEndEncoded(r, false)
+}
+
+func (r *RunEndEncoded) ValidateFull() error {
+ return validateRunEndEncoded(r, true)
+}
+
func (r *RunEndEncoded) Retain() {
r.array.Retain()
r.values.Retain()
@@ -240,6 +249,85 @@ func (r *RunEndEncoded) String() string {
return buf.String()
}
+func validateRunEndEncoded(r *RunEndEncoded, full bool) error {
+ reeType := r.data.dtype.(*arrow.RunEndEncodedType)
+ runEndsData := r.data.childData[0].(*Data)
+ valuesData := r.data.childData[1]
+
+ if reeNullCount(r.data) != 0 {
+ return fmt.Errorf("arrow/array: run-end encoded array cannot
contain nulls")
+ }
+ if err := validateArrayData(runEndsData); err != nil {
+ return fmt.Errorf("arrow/array: run ends array invalid: %w",
err)
+ }
+ if !arrow.TypeEqual(runEndsData.DataType(), reeType.RunEnds()) {
+ return fmt.Errorf("arrow/array: run ends array must match
parent type %s, got %s", reeType.RunEnds(), runEndsData.DataType())
+ }
+ if !arrow.TypeEqual(valuesData.DataType(), reeType.Encoded()) {
+ return fmt.Errorf("arrow/array: values array must match parent
type %s, got %s", reeType.Encoded(), valuesData.DataType())
+ }
+ if r.ends.NullN() != 0 {
+ return fmt.Errorf("arrow/array: run ends array cannot contain
nulls")
+ }
+ if runEndsData.Len() > valuesData.Len() {
+ return fmt.Errorf("arrow/array: length of run ends array is
greater than length of values array (%d > %d)", runEndsData.Len(),
valuesData.Len())
+ }
+ if runEndsData.Len() == 0 {
+ if r.data.length == 0 {
+ return nil
+ }
+ return fmt.Errorf("arrow/array: run-end encoded array has
non-zero length %d, but run ends array has zero length", r.data.length)
+ }
+ if int64(r.data.offset)+int64(r.data.length) >
runEndTypeLimit(runEndsData.DataType().ID()) {
+ return fmt.Errorf("arrow/array: offset + length of a run-end
encoded array must fit in the run end type %s", runEndsData.DataType())
+ }
+
+ runEnds := encoded.GetRunEnds(runEndsData)
+ lastRunEnd := runEnds(int64(runEndsData.Len() - 1))
+ if lastRunEnd < int64(r.data.offset+r.data.length) {
+ return fmt.Errorf("arrow/array: last run end is %d but it
should cover %d", lastRunEnd, r.data.offset+r.data.length)
+ }
+
+ if !full {
+ return nil
+ }
+
+ firstRunEnd := runEnds(0)
+ if firstRunEnd < 1 {
+ return fmt.Errorf("arrow/array: first run end must be greater
than 0, got %d", firstRunEnd)
+ }
+ lastSeenRunEnd := firstRunEnd
+ for i := int64(1); i < int64(runEndsData.Len()); i++ {
+ runEnd := runEnds(i)
+ if runEnd <= lastSeenRunEnd {
+ return fmt.Errorf("arrow/array: run end at position %d
(%d) must be strictly greater than previous run end (%d)", i, runEnd,
lastSeenRunEnd)
+ }
+ lastSeenRunEnd = runEnd
+ }
+ return nil
+}
+
+func reeNullCount(data *Data) int {
+ if data.nulls != UnknownNullCount {
+ return data.nulls
+ }
+ if len(data.buffers) > 0 && data.buffers[0] != nil {
+ return data.length -
bitutil.CountSetBits(data.buffers[0].Bytes(), data.offset, data.length)
+ }
+ return 0
+}
+
+func runEndTypeLimit(id arrow.Type) int64 {
+ switch id {
+ case arrow.INT16:
+ return math.MaxInt16
+ case arrow.INT32:
+ return math.MaxInt32
+ default:
+ return math.MaxInt64
+ }
+}
+
func (r *RunEndEncoded) GetOneForMarshal(i int) interface{} {
return r.values.GetOneForMarshal(r.GetPhysicalIndex(i))
}
diff --git a/arrow/array/encoded_test.go b/arrow/array/encoded_test.go
index a7941414..7269f4fd 100644
--- a/arrow/array/encoded_test.go
+++ b/arrow/array/encoded_test.go
@@ -29,6 +29,14 @@ import (
"github.com/stretchr/testify/require"
)
+func makeRunEndEncodedArrayRaw(t *testing.T, dt *arrow.RunEndEncodedType,
logicalLength, nulls, offset int, buffers []*memory.Buffer, children
[]arrow.ArrayData) *array.RunEndEncoded {
+ t.Helper()
+ data := array.NewData(dt, logicalLength, buffers, children, nulls,
offset)
+ arr := array.NewRunEndEncodedData(data)
+ data.Release()
+ return arr
+}
+
var (
stringValues, _, _ = array.FromJSON(memory.DefaultAllocator,
arrow.BinaryTypes.String, strings.NewReader(`["Hello", "World", null]`))
int32Values, _, _ = array.FromJSON(memory.DefaultAllocator,
arrow.PrimitiveTypes.Int32, strings.NewReader(`[10, 20, 30]`))
@@ -77,6 +85,111 @@ func TestRLEFromRunEndsAndValues(t *testing.T) {
})
}
+func TestRunEndEncodedValidate(t *testing.T) {
+ mem := memory.NewCheckedAllocator(memory.DefaultAllocator)
+ defer mem.AssertSize(t, 0)
+
+ t.Run("valid array passes", func(t *testing.T) {
+ runEnds, _, _ := array.FromJSON(mem,
arrow.PrimitiveTypes.Int32, strings.NewReader(`[1, 3]`))
+ values, _, _ := array.FromJSON(mem, arrow.BinaryTypes.String,
strings.NewReader(`["a", "b"]`))
+ defer runEnds.Release()
+ defer values.Release()
+
+ arr := makeRunEndEncodedArrayRaw(t,
arrow.RunEndEncodedOf(arrow.PrimitiveTypes.Int32, arrow.BinaryTypes.String), 3,
0, 0,
+ []*memory.Buffer{nil},
[]arrow.ArrayData{runEnds.Data(), values.Data()})
+ defer arr.Release()
+
+ assert.NoError(t, arr.Validate())
+ assert.NoError(t, arr.ValidateFull())
+ })
+
+ t.Run("last run end shorter than logical length fails Validate", func(t
*testing.T) {
+ runEnds, _, _ := array.FromJSON(mem,
arrow.PrimitiveTypes.Int32, strings.NewReader(`[1, 2]`))
+ values, _, _ := array.FromJSON(mem, arrow.BinaryTypes.String,
strings.NewReader(`["a", "b"]`))
+ defer runEnds.Release()
+ defer values.Release()
+
+ arr := makeRunEndEncodedArrayRaw(t,
arrow.RunEndEncodedOf(arrow.PrimitiveTypes.Int32, arrow.BinaryTypes.String), 3,
0, 0,
+ []*memory.Buffer{nil},
[]arrow.ArrayData{runEnds.Data(), values.Data()})
+ defer arr.Release()
+
+ err := arr.Validate()
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "last run end")
+ })
+
+ t.Run("duplicate run ends pass Validate but fail ValidateFull", func(t
*testing.T) {
+ runEnds, _, _ := array.FromJSON(mem,
arrow.PrimitiveTypes.Int32, strings.NewReader(`[2, 2]`))
+ values, _, _ := array.FromJSON(mem, arrow.BinaryTypes.String,
strings.NewReader(`["first", "second"]`))
+ defer runEnds.Release()
+ defer values.Release()
+
+ arr := makeRunEndEncodedArrayRaw(t,
arrow.RunEndEncodedOf(arrow.PrimitiveTypes.Int32, arrow.BinaryTypes.String), 2,
0, 0,
+ []*memory.Buffer{nil},
[]arrow.ArrayData{runEnds.Data(), values.Data()})
+ defer arr.Release()
+
+ assert.NoError(t, arr.Validate())
+ err := arr.ValidateFull()
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "strictly greater")
+ })
+
+ t.Run("top level ValidateFull catches duplicate run ends", func(t
*testing.T) {
+ runEnds, _, _ := array.FromJSON(mem,
arrow.PrimitiveTypes.Int32, strings.NewReader(`[2, 2]`))
+ values, _, _ := array.FromJSON(mem, arrow.BinaryTypes.String,
strings.NewReader(`["first", "second"]`))
+ defer runEnds.Release()
+ defer values.Release()
+
+ arr := makeRunEndEncodedArrayRaw(t,
arrow.RunEndEncodedOf(arrow.PrimitiveTypes.Int32, arrow.BinaryTypes.String), 2,
0, 0,
+ []*memory.Buffer{nil},
[]arrow.ArrayData{runEnds.Data(), values.Data()})
+ defer arr.Release()
+
+ assert.NoError(t, array.Validate(arr))
+ err := array.ValidateFull(arr)
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "strictly greater")
+ })
+
+ t.Run("unknown null counts without bitmaps still validate", func(t
*testing.T) {
+ runEnds, _, _ := array.FromJSON(mem,
arrow.PrimitiveTypes.Int32, strings.NewReader(`[1, 3]`))
+ values, _, _ := array.FromJSON(mem, arrow.BinaryTypes.String,
strings.NewReader(`["a", "b"]`))
+ defer runEnds.Release()
+ defer values.Release()
+
+ runEndsData := runEnds.Data().(*array.Data).Copy()
+ runEndsData.SetNullN(array.UnknownNullCount)
+ defer runEndsData.Release()
+
+ valuesData := values.Data().(*array.Data).Copy()
+ defer valuesData.Release()
+
+ arr := makeRunEndEncodedArrayRaw(t,
arrow.RunEndEncodedOf(arrow.PrimitiveTypes.Int32, arrow.BinaryTypes.String), 3,
array.UnknownNullCount, 0,
+ []*memory.Buffer{nil}, []arrow.ArrayData{runEndsData,
valuesData})
+ defer arr.Release()
+
+ assert.NoError(t, arr.Validate())
+ assert.NoError(t, arr.ValidateFull())
+ })
+
+ t.Run("run ends with lazy null count fail Validate", func(t *testing.T)
{
+ validity := memory.NewBufferBytes([]byte{0x01})
+ valuesBuf :=
memory.NewBufferBytes(arrow.Int32Traits.CastToBytes([]int32{1, 3}))
+ runEndsData := array.NewData(arrow.PrimitiveTypes.Int32, 2,
[]*memory.Buffer{validity, valuesBuf}, nil, array.UnknownNullCount, 0)
+ defer runEndsData.Release()
+
+ values, _, _ := array.FromJSON(mem, arrow.BinaryTypes.String,
strings.NewReader(`["a", "b"]`))
+ defer values.Release()
+
+ arr := makeRunEndEncodedArrayRaw(t,
arrow.RunEndEncodedOf(arrow.PrimitiveTypes.Int32, arrow.BinaryTypes.String), 3,
0, 0,
+ []*memory.Buffer{nil}, []arrow.ArrayData{runEndsData,
values.Data()})
+ defer arr.Release()
+
+ err := arr.Validate()
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "run ends array cannot contain
nulls")
+ })
+}
+
func TestRunLengthEncodedOffsetLength(t *testing.T) {
mem := memory.NewCheckedAllocator(memory.DefaultAllocator)
defer mem.AssertSize(t, 0)
diff --git a/arrow/encoded/ree_utils.go b/arrow/encoded/ree_utils.go
index fd0c166b..eb1a3b82 100644
--- a/arrow/encoded/ree_utils.go
+++ b/arrow/encoded/ree_utils.go
@@ -125,6 +125,10 @@ func getRunEnds(arr arrow.ArrayData) func(int64) int64 {
}
}
+func GetRunEnds(arr arrow.ArrayData) func(int64) int64 {
+ return getRunEnds(arr)
+}
+
// MergedRuns is used to take two Run End Encoded arrays and iterate
// them, finding the correct physical indices to correspond with the
// runs.
