You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "fallintoplace (via GitHub)" <gi...@apache.org> on 2026/07/23 21:32:23 UTC
[PR] fix(array): validate run-end encoded invariants [arrow-go]
fallintoplace opened a new pull request, #992:
URL: https://github.com/apache/arrow-go/pull/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
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix(array): validate run-end encoded invariants [arrow-go]
Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade commented on code in PR #992:
URL: https://github.com/apache/arrow-go/pull/992#discussion_r3646600371
##########
arrow/array/encoded.go:
##########
@@ -240,6 +249,102 @@ 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]
+ valuesData := r.data.childData[1]
+
+ if reeNullCount(r.data) != 0 {
+ return fmt.Errorf("arrow/array: run-end encoded array cannot contain nulls")
+ }
+ 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 := getRunEnds64(runEndsData)
+ lastRunEnd := runEnds[len(runEnds)-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
+ }
+
+ if runEnds[0] < 1 {
+ return fmt.Errorf("arrow/array: first run end must be greater than 0, got %d", runEnds[0])
+ }
+ for i := 1; i < len(runEnds); i++ {
+ if runEnds[i] <= runEnds[i-1] {
+ return fmt.Errorf("arrow/array: run end at position %d (%d) must be strictly greater than previous run end (%d)", i, runEnds[i], runEnds[i-1])
+ }
+ }
+ 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 1<<15 - 1
+ case arrow.INT32:
+ return math.MaxInt32
+ default:
+ return math.MaxInt64
+ }
+}
+
+func getRunEnds64(data arrow.ArrayData) []int64 {
+ switch data.DataType().ID() {
+ case arrow.INT16:
+ runEnds := arrow.Int16Traits.CastFromBytes(data.Buffers()[1].Bytes())
+ runEnds = runEnds[data.Offset() : data.Offset()+data.Len()]
+ out := make([]int64, len(runEnds))
+ for i, v := range runEnds {
+ out[i] = int64(v)
+ }
+ return out
+ case arrow.INT32:
+ runEnds := arrow.Int32Traits.CastFromBytes(data.Buffers()[1].Bytes())
+ runEnds = runEnds[data.Offset() : data.Offset()+data.Len()]
+ out := make([]int64, len(runEnds))
+ for i, v := range runEnds {
+ out[i] = int64(v)
+ }
+ return out
+ default:
+ runEnds := arrow.Int64Traits.CastFromBytes(data.Buffers()[1].Bytes())
+ return runEnds[data.Offset() : data.Offset()+data.Len()]
+ }
Review Comment:
at this point we haven't validated the length/buffers yet, so we need to check `len(runEnds)` before you start slicing using `data.Offset()+data.Len()` otherwise we could panic on a corrupt buffer.
##########
arrow/array/encoded.go:
##########
@@ -240,6 +249,102 @@ 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]
+ valuesData := r.data.childData[1]
+
+ if reeNullCount(r.data) != 0 {
+ return fmt.Errorf("arrow/array: run-end encoded array cannot contain nulls")
+ }
+ 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 := getRunEnds64(runEndsData)
+ lastRunEnd := runEnds[len(runEnds)-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
+ }
Review Comment:
In the `!full` path, we're copying the entirety of the run ends only to read the single `runEnds[len-1]`. Instead for the `!full` path we should *only* check the last run end instead of doing the full copy loop
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix(array): validate run-end encoded invariants [arrow-go]
Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade merged PR #992:
URL: https://github.com/apache/arrow-go/pull/992
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix(array): validate run-end encoded invariants [arrow-go]
Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade commented on code in PR #992:
URL: https://github.com/apache/arrow-go/pull/992#discussion_r3646636750
##########
arrow/array/encoded.go:
##########
@@ -240,6 +249,102 @@ 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]
+ valuesData := r.data.childData[1]
+
+ if reeNullCount(r.data) != 0 {
+ return fmt.Errorf("arrow/array: run-end encoded array cannot contain nulls")
+ }
+ 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 := getRunEnds64(runEndsData)
+ lastRunEnd := runEnds[len(runEnds)-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
+ }
+
+ if runEnds[0] < 1 {
+ return fmt.Errorf("arrow/array: first run end must be greater than 0, got %d", runEnds[0])
+ }
+ for i := 1; i < len(runEnds); i++ {
+ if runEnds[i] <= runEnds[i-1] {
+ return fmt.Errorf("arrow/array: run end at position %d (%d) must be strictly greater than previous run end (%d)", i, runEnds[i], runEnds[i-1])
+ }
+ }
+ 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 1<<15 - 1
+ case arrow.INT32:
+ return math.MaxInt32
+ default:
+ return math.MaxInt64
+ }
+}
+
+func getRunEnds64(data arrow.ArrayData) []int64 {
Review Comment:
there's already a `encoded.getRunEnds` function at `ree_utils.go:109` which returns a non-allocating closure, could we use export/reuse that pattern instead of allocating a new []int64?
##########
arrow/array/encoded.go:
##########
@@ -240,6 +249,102 @@ 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]
+ valuesData := r.data.childData[1]
+
+ if reeNullCount(r.data) != 0 {
+ return fmt.Errorf("arrow/array: run-end encoded array cannot contain nulls")
+ }
+ 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 := getRunEnds64(runEndsData)
+ lastRunEnd := runEnds[len(runEnds)-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
+ }
+
+ if runEnds[0] < 1 {
+ return fmt.Errorf("arrow/array: first run end must be greater than 0, got %d", runEnds[0])
+ }
+ for i := 1; i < len(runEnds); i++ {
+ if runEnds[i] <= runEnds[i-1] {
+ return fmt.Errorf("arrow/array: run end at position %d (%d) must be strictly greater than previous run end (%d)", i, runEnds[i], runEnds[i-1])
+ }
+ }
+ 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 1<<15 - 1
Review Comment:
`math.MaxInt16` ?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org