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 fbf934fd fix(parquet/variant): validate compound value bounds (#1126)
fbf934fd is described below
commit fbf934fd7c1db26d5ed0bca543f1324e7ad74031
Author: Minh Vu <[email protected]>
AuthorDate: Thu Aug 27 18:59:31 2026 +0200
fix(parquet/variant): validate compound value bounds (#1126)
### Rationale for this change
NewWithMetadata accepts truncated arrays and objects because compound
values are validated lazily. Accessing one of those values can then
panic on a short offset table or an out-of-range child value.
### What changes are included in this PR?
Validate compound headers, offset tables, monotonic offsets, and nested
value boundaries before returning a value while keeping the existing
compound accessors lazy.
### Are these changes tested?
- `go test ./parquet/variant`
### Are there any user-facing changes?
Malformed compound variant values now return an error during
construction instead of panicking during access.
---
parquet/variant/large_value_test.go | 97 ++++++
parquet/variant/utils.go | 20 +-
parquet/variant/variant.go | 514 ++++++++++++++++++++++++++----
parquet/variant/variant_benchmark_test.go | 113 +++++++
parquet/variant/variant_test.go | 242 +++++++++++++-
5 files changed, 900 insertions(+), 86 deletions(-)
diff --git a/parquet/variant/large_value_test.go
b/parquet/variant/large_value_test.go
new file mode 100644
index 00000000..47f93169
--- /dev/null
+++ b/parquet/variant/large_value_test.go
@@ -0,0 +1,97 @@
+//go:build darwin || linux
+
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package variant_test
+
+import (
+ "encoding/binary"
+ "strconv"
+ "syscall"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/parquet/variant"
+ "github.com/stretchr/testify/require"
+)
+
+const maxEncodedOffset = uint64(1<<32 - 1)
+
+func mappedVariantValue(t *testing.T, dataStart uint64) []byte {
+ t.Helper()
+ if strconv.IntSize < 64 {
+ t.Skip("large variant values require 64-bit indexes")
+ }
+
+ value, err := syscall.Mmap(
+ -1,
+ 0,
+ int(dataStart+maxEncodedOffset),
+ syscall.PROT_READ|syscall.PROT_WRITE,
+ syscall.MAP_ANON|syscall.MAP_PRIVATE,
+ )
+ require.NoError(t, err)
+ t.Cleanup(func() { require.NoError(t, syscall.Munmap(value)) })
+ return value
+}
+
+func appendMaxSizeBinary(value []byte, dataStart int) {
+ value[dataStart] = byte(variant.PrimitiveBinary << 2)
+ binary.LittleEndian.PutUint32(value[dataStart+1:],
uint32(maxEncodedOffset-5))
+}
+
+func TestCompoundValueMayExceedUint32(t *testing.T) {
+ metaBytes := []byte{1, 1, 0, 1, 'a'}
+ meta, err := variant.NewMetadata(metaBytes)
+ require.NoError(t, err)
+
+ t.Run("array", func(t *testing.T) {
+ const dataStart = uint64(10)
+ value := mappedVariantValue(t, dataStart)
+ value[0] = byte(3<<2) | byte(variant.BasicArray)
+ value[1] = 1
+ binary.LittleEndian.PutUint32(value[2:6], 0)
+ binary.LittleEndian.PutUint32(value[6:10],
uint32(maxEncodedOffset))
+ appendMaxSizeBinary(value, int(dataStart))
+
+ parsed, err := variant.NewWithMetadata(meta, value)
+ require.NoError(t, err)
+ array := parsed.Value().(variant.ArrayValue)
+ child, err := array.Value(0)
+ require.NoError(t, err)
+ require.Equal(t, variant.Binary, child.Type())
+ require.Len(t, child.Bytes(), int(maxEncodedOffset))
+ })
+
+ t.Run("object", func(t *testing.T) {
+ const dataStart = uint64(11)
+ value := mappedVariantValue(t, dataStart)
+ value[0] = byte(3<<2) | byte(variant.BasicObject)
+ value[1] = 1
+ value[2] = 0
+ binary.LittleEndian.PutUint32(value[3:7], 0)
+ binary.LittleEndian.PutUint32(value[7:11],
uint32(maxEncodedOffset))
+ appendMaxSizeBinary(value, int(dataStart))
+
+ parsed, err := variant.NewWithMetadata(meta, value)
+ require.NoError(t, err)
+ object := parsed.Value().(variant.ObjectValue)
+ field, err := object.FieldAt(0)
+ require.NoError(t, err)
+ require.Equal(t, variant.Binary, field.Value.Type())
+ require.Len(t, field.Value.Bytes(), int(maxEncodedOffset))
+ })
+}
diff --git a/parquet/variant/utils.go b/parquet/variant/utils.go
index edeea2de..033dac93 100644
--- a/parquet/variant/utils.go
+++ b/parquet/variant/utils.go
@@ -120,13 +120,13 @@ func valueSize(v []byte) int {
}
sz := readLEU32(v[1 : 1+szBytes])
- idSize, offsetSize := ((typeInfo>>2)&0b11)+1,
uint32((typeInfo&0b11)+1)
- idStart := 1 + szBytes
- offsetStart := uint32(idStart) + sz*uint32(idSize)
- dataStart := offsetStart + (sz+1)*offsetSize
+ idSize, offsetSize := ((typeInfo>>2)&0b11)+1,
uint64((typeInfo&0b11)+1)
+ idStart := uint64(1 + szBytes)
+ offsetStart := idStart + uint64(sz)*uint64(idSize)
+ dataStart := offsetStart + (uint64(sz)+1)*offsetSize
- idx := offsetStart + sz*uint32(offsetSize)
- return int(dataStart + readLEU32(v[idx:idx+offsetSize]))
+ idx := offsetStart + uint64(sz)*offsetSize
+ return int(dataStart + uint64(readLEU32(v[idx:idx+offsetSize])))
case byte(BasicArray):
var szBytes uint8 = 1
if ((typeInfo >> 2) & 0x1) != 0 {
@@ -134,11 +134,11 @@ func valueSize(v []byte) int {
}
sz := readLEU32(v[1 : 1+szBytes])
- offsetSize, offsetStart := uint32((typeInfo&0b11)+1),
uint32(1+szBytes)
- dataStart := offsetStart + (sz+1)*offsetSize
+ offsetSize, offsetStart := uint64((typeInfo&0b11)+1),
uint64(1+szBytes)
+ dataStart := offsetStart + (uint64(sz)+1)*offsetSize
- idx := offsetStart + sz*uint32(offsetSize)
- return int(dataStart + readLEU32(v[idx:idx+offsetSize]))
+ idx := offsetStart + uint64(sz)*offsetSize
+ return int(dataStart + uint64(readLEU32(v[idx:idx+offsetSize])))
default:
switch PrimitiveType(typeInfo) {
case PrimitiveNull, PrimitiveBoolTrue, PrimitiveBoolFalse:
diff --git a/parquet/variant/variant.go b/parquet/variant/variant.go
index 70222234..a4557004 100644
--- a/parquet/variant/variant.go
+++ b/parquet/variant/variant.go
@@ -134,6 +134,7 @@ const (
supportedVersion = 1
maxShortStringSize = 0x3F
metadataMaxSizeLimit = 128 * 1024 * 1024 // 128MB
+ maxValidationDepth = 1024 // bounds memory used
while validating nested values.
)
var (
@@ -319,9 +320,9 @@ type ArrayValue struct {
meta Metadata
numElements uint32
- dataStart uint32
+ dataStart uint64
offsetSize uint8
- offsetStart uint8
+ offsetStart uint64
}
// MarshalJSON implements the json.Marshaler interface for ArrayValue.
@@ -338,14 +339,10 @@ func (v ArrayValue) Len() uint32 { return v.numElements }
func (v ArrayValue) Values() iter.Seq[Value] {
return func(yield func(Value) bool) {
for i := range v.numElements {
- idx := uint32(v.offsetStart) + i*uint32(v.offsetSize)
- offset := readLEU32(v.value[idx :
idx+uint32(v.offsetSize)])
+ idx := v.offsetStart + uint64(i)*uint64(v.offsetSize)
+ offset := readLEU32(v.value[idx :
idx+uint64(v.offsetSize)])
- val := v.value[v.dataStart+offset:]
- sz := valueSize(val)
- val = val[:sz] // trim to actual size
-
- if !yield(Value{value: val, meta: v.meta}) {
+ if !yield(trimValue(v.meta,
v.value[v.dataStart+uint64(offset):])) {
return
}
}
@@ -360,10 +357,10 @@ func (v ArrayValue) Value(i uint32) (Value, error) {
arrow.ErrIndex, i, v.numElements)
}
- idx := uint32(v.offsetStart) + i*uint32(v.offsetSize)
- offset := readLEU32(v.value[idx : idx+uint32(v.offsetSize)])
+ idx := v.offsetStart + uint64(i)*uint64(v.offsetSize)
+ offset := readLEU32(v.value[idx : idx+uint64(v.offsetSize)])
- return Value{meta: v.meta, value: v.value[v.dataStart+offset:]}, nil
+ return trimValue(v.meta, v.value[v.dataStart+uint64(offset):]), nil
}
// ObjectValue represents an object (map/dictionary) of key-value pairs.
@@ -372,11 +369,11 @@ type ObjectValue struct {
meta Metadata
numElements uint32
- offsetStart uint32
- dataStart uint32
+ offsetStart uint64
+ dataStart uint64
idSize uint8
offsetSize uint8
- idStart uint8
+ idStart uint64
}
// ObjectField represents a key-value pair in an object.
@@ -398,18 +395,18 @@ func (v ObjectValue) ValueByKey(key string) (ObjectField,
error) {
const binarySearchThreshold = 32
if n < binarySearchThreshold {
for i := range n {
- idx := uint32(v.idStart) + i*uint32(v.idSize)
- id := readLEU32(v.value[idx : idx+uint32(v.idSize)])
+ idx := v.idStart + uint64(i)*uint64(v.idSize)
+ id := readLEU32(v.value[idx : idx+uint64(v.idSize)])
k, err := v.meta.KeyAt(id)
if err != nil {
return ObjectField{}, fmt.Errorf("invalid
object value: fieldID at idx %d is not in metadata", idx)
}
if k == key {
- idx := uint32(v.offsetStart) +
uint32(v.offsetSize)*i
- offset := readLEU32(v.value[idx :
idx+uint32(v.offsetSize)])
+ idx := v.offsetStart +
uint64(v.offsetSize)*uint64(i)
+ offset := readLEU32(v.value[idx :
idx+uint64(v.offsetSize)])
return ObjectField{
Key: key,
- Value: Value{value:
v.value[v.dataStart+offset:], meta: v.meta}}, nil
+ Value: trimValue(v.meta,
v.value[v.dataStart+uint64(offset):])}, nil
}
}
return ObjectField{}, arrow.ErrNotFound
@@ -418,8 +415,8 @@ func (v ObjectValue) ValueByKey(key string) (ObjectField,
error) {
i, j := uint32(0), n
for i < j {
mid := (i + j) >> 1
- idx := uint32(v.idStart) + mid*uint32(v.idSize)
- id := readLEU32(v.value[idx : idx+uint32(v.idSize)])
+ idx := v.idStart + uint64(mid)*uint64(v.idSize)
+ id := readLEU32(v.value[idx : idx+uint64(v.idSize)])
k, err := v.meta.KeyAt(id)
if err != nil {
return ObjectField{}, fmt.Errorf("invalid object value:
fieldID at idx %d is not in metadata", idx)
@@ -429,12 +426,12 @@ func (v ObjectValue) ValueByKey(key string) (ObjectField,
error) {
case -1:
i = mid + 1
case 0:
- idx := uint32(v.offsetStart) + uint32(v.offsetSize)*mid
- offset := readLEU32(v.value[idx :
idx+uint32(v.offsetSize)])
+ idx := v.offsetStart + uint64(v.offsetSize)*uint64(mid)
+ offset := readLEU32(v.value[idx :
idx+uint64(v.offsetSize)])
return ObjectField{
Key: key,
- Value: Value{value:
v.value[v.dataStart+offset:], meta: v.meta}}, nil
+ Value: trimValue(v.meta,
v.value[v.dataStart+uint64(offset):])}, nil
case 1:
j = mid
}
@@ -451,38 +448,36 @@ func (v ObjectValue) FieldAt(i uint32) (ObjectField,
error) {
arrow.ErrIndex, i, v.numElements)
}
- idx := uint32(v.idStart) + i*uint32(v.idSize)
- id := readLEU32(v.value[idx : idx+uint32(v.idSize)])
+ idx := v.idStart + uint64(i)*uint64(v.idSize)
+ id := readLEU32(v.value[idx : idx+uint64(v.idSize)])
k, err := v.meta.KeyAt(id)
if err != nil {
return ObjectField{}, fmt.Errorf("invalid object value: fieldID
at idx %d is not in metadata", idx)
}
- offsetIdx := uint32(v.offsetStart) + i*uint32(v.offsetSize)
- offset := readLEU32(v.value[offsetIdx : offsetIdx+uint32(v.offsetSize)])
+ offsetIdx := v.offsetStart + uint64(i)*uint64(v.offsetSize)
+ offset := readLEU32(v.value[offsetIdx : offsetIdx+uint64(v.offsetSize)])
return ObjectField{
Key: k,
- Value: Value{value: v.value[v.dataStart+offset:], meta:
v.meta}}, nil
+ Value: trimValue(v.meta,
v.value[v.dataStart+uint64(offset):])}, nil
}
// Values returns an iterator over all key-value pairs in the object.
func (v ObjectValue) Values() iter.Seq2[string, Value] {
return func(yield func(string, Value) bool) {
for i := range v.numElements {
- idx := uint32(v.idStart) + i*uint32(v.idSize)
- id := readLEU32(v.value[idx : idx+uint32(v.idSize)])
+ idx := v.idStart + uint64(i)*uint64(v.idSize)
+ id := readLEU32(v.value[idx : idx+uint64(v.idSize)])
k, err := v.meta.KeyAt(id)
if err != nil {
return
}
- offsetIdx := uint32(v.offsetStart) +
i*uint32(v.offsetSize)
- offset := readLEU32(v.value[offsetIdx :
offsetIdx+uint32(v.offsetSize)])
+ offsetIdx := v.offsetStart +
uint64(i)*uint64(v.offsetSize)
+ offset := readLEU32(v.value[offsetIdx :
offsetIdx+uint64(v.offsetSize)])
- value := v.value[v.dataStart+offset:]
- sz := valueSize(value)
- if !yield(k, Value{value: value[:sz], meta: v.meta}) {
+ if !yield(k, trimValue(v.meta,
v.value[v.dataStart+uint64(offset):])) {
return
}
}
@@ -507,30 +502,34 @@ type Value struct {
meta Metadata
}
+func trimValue(meta Metadata, value []byte) Value {
+ return Value{value: value[:valueSize(value)], meta: meta}
+}
+
// NewWithMetadata creates a Value with the provided metadata and value bytes.
func NewWithMetadata(meta Metadata, value []byte) (Value, error) {
if len(value) == 0 {
return Value{}, errors.New("invalid variant value: empty")
}
- if err := validateScalarValue(value); err != nil {
+ if err := validateValueBytes(meta, value); err != nil {
return Value{}, err
}
return Value{value: value, meta: meta}, nil
}
-func validateScalarValue(value []byte) error {
- if basicTypeFromHeader(value[0]) == BasicShortString {
- want := 1 + int(value[0]>>basicTypeBits)
- if len(value) < want {
- return fmt.Errorf("invalid variant value: short string
requires %d bytes, got %d", want, len(value))
- }
- return nil
+func validateValueBytes(meta Metadata, value []byte) error {
+ size, err := validateValue(meta, value)
+ if err != nil {
+ return err
}
- if basicTypeFromHeader(value[0]) != BasicPrimitive {
- return nil
+ if size != len(value) {
+ return fmt.Errorf("invalid variant value: trailing bytes")
}
+ return nil
+}
+func validatePrimitiveValue(value []byte) (int, error) {
primitiveType := primitiveTypeFromHeader(value[0])
want := 0
switch primitiveType {
@@ -556,23 +555,406 @@ func validateScalarValue(value []byte) error {
want = 17
case PrimitiveBinary, PrimitiveString:
if len(value) < 5 {
- return fmt.Errorf("invalid variant value: %s length
prefix requires 5 bytes, got %d", primitiveType, len(value))
+ return 0, fmt.Errorf("invalid variant value: %s length
prefix requires 5 bytes, got %d", primitiveType, len(value))
}
dataLen := uint64(binary.LittleEndian.Uint32(value[1:5]))
if dataLen > uint64(len(value)-5) {
- return fmt.Errorf("invalid variant value: %s data
requires %d bytes, got %d", primitiveType, dataLen, len(value)-5)
+ return 0, fmt.Errorf("invalid variant value: %s data
requires %d bytes, got %d", primitiveType, dataLen, len(value)-5)
}
- return nil
+ return 5 + int(dataLen), nil
default:
- return fmt.Errorf("invalid variant value: unknown primitive
type %d", primitiveType)
+ return 0, fmt.Errorf("invalid variant value: unknown primitive
type %d", primitiveType)
}
if len(value) < want {
- return fmt.Errorf("invalid variant value: %s requires %d bytes,
got %d", primitiveType, want, len(value))
+ return 0, fmt.Errorf("invalid variant value: %s requires %d
bytes, got %d", primitiveType, want, len(value))
+ }
+ return want, nil
+}
+
+type validationRange struct {
+ start uint64
+ end uint64
+ field int
+}
+
+type validationFrame struct {
+ value []byte
+ size uint64
+ dataSize uint32
+ dataStart uint64
+ offsetStart uint64
+ numChildren uint32
+ nextChild uint32
+ pendingIndex uint32
+ pendingStart uint32
+ pendingExpectedSize uint32
+ rangeStart uint32
+ offsetSize uint8
+ kind uint8
+ initialized bool
+}
+
+const (
+ validationStackInlineCapacity = 32
+ // Values that exceed the inline stack commonly need only a modest
amount
+ // of additional depth, so avoid allocating the maximum stack for them.
+ validationStackIntermediateCapacity = 128
+ // The root value is at depth zero, so the stack needs one more frame
than
+ // the maximum allowed nesting depth. Keeping this storage fixed
prevents
+ // untrusted values from growing the validation stack on the heap.
+ validationStackCapacity = maxValidationDepth + 1
+ validationRangeInlineCapacity = 64
+)
+
+// validateValue walks compound values with an explicit stack so valid values
+// do not consume the Go call stack. Nesting is bounded to keep validation
+// memory usage independent of attacker-controlled input depth.
+func validateValue(meta Metadata, value []byte) (int, error) {
+ var stackStorage [validationStackInlineCapacity]validationFrame
+ stack := stackStorage[:1]
+ stack[0].value = value
+
+ var rangeStorage [validationRangeInlineCapacity]validationRange
+ ranges := rangeStorage[:0]
+ return validateValueLoop(meta, value, stack, ranges, 0)
+}
+
+func validateValueLoop(meta Metadata, value []byte, stack []validationFrame,
ranges []validationRange, rangeTop int) (int, error) {
+ var (
+ resultSize int
+ resultErr error
+ hasResult bool
+ )
+
+ for len(stack) > 0 {
+ frame := &stack[len(stack)-1]
+ if hasResult {
+ hasResult = false
+
+ if resultErr != nil {
+ switch BasicType(frame.kind) {
+ case BasicArray:
+ return 0, fmt.Errorf("invalid variant
value: array element %d: %w", frame.pendingIndex, resultErr)
+ case BasicObject:
+ return 0, fmt.Errorf("invalid variant
value: object field %d: %w", frame.pendingIndex, resultErr)
+ default:
+ return 0, resultErr
+ }
+ }
+
+ switch BasicType(frame.kind) {
+ case BasicArray:
+ if uint64(resultSize) !=
uint64(frame.pendingExpectedSize) {
+ return 0, fmt.Errorf("invalid variant
value: array element %d has trailing bytes", frame.pendingIndex)
+ }
+ case BasicObject:
+ end := uint64(frame.pendingStart) +
uint64(resultSize)
+ if end > uint64(frame.dataSize) {
+ return 0, fmt.Errorf("invalid variant
value: object field %d extends beyond data", frame.pendingIndex)
+ }
+ if rangeTop < len(ranges) {
+ ranges[rangeTop] = validationRange{
+ start:
uint64(frame.pendingStart),
+ end: end,
+ field: int(frame.pendingIndex),
+ }
+ } else {
+ ranges = append(ranges, validationRange{
+ start:
uint64(frame.pendingStart),
+ end: end,
+ field: int(frame.pendingIndex),
+ })
+ }
+ rangeTop++
+ }
+ continue
+ }
+
+ if !frame.initialized {
+ frame.initialized = true
+ if err := prepareValidationFrame(meta, frame); err !=
nil {
+ stack = stack[:len(stack)-1]
+ if len(stack) == 0 {
+ return 0, err
+ }
+ resultErr = err
+ hasResult = true
+ continue
+ }
+ if BasicType(frame.kind) == BasicObject {
+ frame.rangeStart = uint32(rangeTop)
+ }
+ }
+
+ if frame.kind == uint8(BasicArray) || frame.kind ==
uint8(BasicObject) {
+ if frame.nextChild < frame.numChildren {
+ if len(stack) == validationStackCapacity {
+ return 0, fmt.Errorf("invalid variant
value: maximum nesting depth exceeded")
+ }
+ if len(stack) == cap(stack) {
+ if cap(stack) ==
validationStackInlineCapacity {
+ return
validateValueIntermediate(meta, value, stack, ranges, rangeTop)
+ }
+ return validateValueDeep(meta, value,
stack, ranges, rangeTop)
+ }
+
+ child, index, start, expectedSize, err :=
nextValidationChild(frame)
+ if err != nil {
+ stack = stack[:len(stack)-1]
+ if len(stack) == 0 {
+ return 0, err
+ }
+ resultErr = err
+ hasResult = true
+ continue
+ }
+
+ frame.nextChild++
+ frame.pendingIndex = uint32(index)
+ frame.pendingStart = uint32(start)
+ frame.pendingExpectedSize = uint32(expectedSize)
+ stack = append(stack, validationFrame{value:
child})
+ continue
+ }
+
+ if err := finishValidationFrame(frame,
ranges[int(frame.rangeStart):rangeTop]); err != nil {
+ if BasicType(frame.kind) == BasicObject {
+ rangeTop = int(frame.rangeStart)
+ }
+ stack = stack[:len(stack)-1]
+ if len(stack) == 0 {
+ return 0, err
+ }
+ resultErr = err
+ hasResult = true
+ continue
+ }
+ if BasicType(frame.kind) == BasicObject {
+ rangeTop = int(frame.rangeStart)
+ }
+ }
+
+ resultSize = int(frame.size)
+ stack = stack[:len(stack)-1]
+ if len(stack) == 0 {
+ return resultSize, nil
+ }
+ hasResult = true
+ }
+
+ return 0, errors.New("invalid variant value: validation stack
exhausted")
+}
+
+func validateValueIntermediate(meta Metadata, value []byte, initialStack
[]validationFrame, ranges []validationRange, rangeTop int) (int, error) {
+ var stackStorage [validationStackIntermediateCapacity]validationFrame
+ stack := stackStorage[:len(initialStack)]
+ copy(stack, initialStack)
+ return validateValueLoop(meta, value, stack, ranges, rangeTop)
+}
+
+func validateValueDeep(meta Metadata, value []byte, initialStack
[]validationFrame, ranges []validationRange, rangeTop int) (int, error) {
+ var stackStorage [validationStackCapacity]validationFrame
+ stack := stackStorage[:len(initialStack)]
+ copy(stack, initialStack)
+ return validateValueLoop(meta, value, stack, ranges, rangeTop)
+}
+
+func finishValidationFrame(frame *validationFrame, ranges []validationRange)
error {
+ if BasicType(frame.kind) != BasicObject {
+ return nil
+ }
+
+ slices.SortFunc(ranges, func(a, b validationRange) int {
+ switch {
+ case a.start < b.start:
+ return -1
+ case a.start > b.start:
+ return 1
+ default:
+ return 0
+ }
+ })
+
+ var (
+ next uint64
+ previousField int
+ )
+ for _, child := range ranges {
+ switch {
+ case child.start < next:
+ return fmt.Errorf("invalid variant value: object fields
%d and %d overlap", previousField, child.field)
+ case child.start > next:
+ return fmt.Errorf("invalid variant value: object data
has a gap before field %d", child.field)
+ }
+ next = child.end
+ previousField = child.field
+ }
+ if next != uint64(frame.dataSize) {
+ return fmt.Errorf("invalid variant value: object data has
trailing bytes")
+ }
+ return nil
+}
+
+func prepareValidationFrame(meta Metadata, frame *validationFrame) error {
+ if len(frame.value) == 0 {
+ return errors.New("invalid variant value: empty")
+ }
+
+ frame.kind = uint8(basicTypeFromHeader(frame.value[0]))
+ switch BasicType(frame.kind) {
+ case BasicShortString:
+ want := 1 + int(frame.value[0]>>basicTypeBits)
+ if len(frame.value) < want {
+ return fmt.Errorf("invalid variant value: short string
requires %d bytes, got %d", want, len(frame.value))
+ }
+ frame.size = uint64(want)
+ case BasicObject:
+ return prepareObjectValidationFrame(meta, frame)
+ case BasicArray:
+ return prepareArrayValidationFrame(frame)
+ case BasicPrimitive:
+ size, err := validatePrimitiveValue(frame.value)
+ frame.size = uint64(size)
+ return err
+ default:
+ return fmt.Errorf("invalid variant value: unknown basic type
%d", BasicType(frame.kind))
}
return nil
}
+func prepareArrayValidationFrame(frame *validationFrame) error {
+ value := frame.value
+ typeInfo := value[0] >> basicTypeBits
+ offsetSize := uint8(typeInfo&0b11) + 1
+ isLarge := ((typeInfo >> 2) & 0x1) != 0
+
+ var (
+ numElements uint32
+ offsetStart uint64
+ )
+ if isLarge {
+ if len(value) < 5 {
+ return fmt.Errorf("invalid variant value: array size
requires 5 bytes, got %d", len(value))
+ }
+ numElements = readLEU32(value[1:5])
+ offsetStart = 5
+ } else {
+ if len(value) < 2 {
+ return fmt.Errorf("invalid variant value: array size
requires 2 bytes, got %d", len(value))
+ }
+ numElements = uint32(value[1])
+ offsetStart = 2
+ }
+
+ dataStart := offsetStart + (uint64(numElements)+1)*uint64(offsetSize)
+ if dataStart > uint64(len(value)) {
+ return fmt.Errorf("invalid variant value: array offset table
ends at %d, got %d bytes", dataStart, len(value))
+ }
+
+ var previousOffset uint32
+ for i := uint64(0); i <= uint64(numElements); i++ {
+ pos := offsetStart + uint64(i)*uint64(offsetSize)
+ offset := readLEU32(value[int(pos) : int(pos)+int(offsetSize)])
+ if i == 0 && offset != 0 {
+ return fmt.Errorf("invalid variant value: array first
offset must be zero, got %d", offset)
+ }
+ if i > 0 && offset < previousOffset {
+ return fmt.Errorf("invalid variant value: array offsets
are not monotonic")
+ }
+ if dataStart+uint64(offset) > uint64(len(value)) {
+ return fmt.Errorf("invalid variant value: array offset
%d is out of range", offset)
+ }
+ previousOffset = offset
+ }
+
+ frame.dataStart = dataStart
+ frame.offsetStart = offsetStart
+ frame.offsetSize = offsetSize
+ frame.numChildren = numElements
+ frame.size = dataStart + uint64(previousOffset)
+ return nil
+}
+
+func prepareObjectValidationFrame(meta Metadata, frame *validationFrame) error
{
+ value := frame.value
+ typeInfo := value[0] >> basicTypeBits
+ offsetSize := uint8(typeInfo&0b11) + 1
+ idSize := uint8((typeInfo>>2)&0b11) + 1
+ isLarge := ((typeInfo >> 4) & 0x1) != 0
+
+ var (
+ numElements uint32
+ elementSize uint64 = 1
+ )
+ if isLarge {
+ elementSize = 4
+ }
+ if uint64(len(value)) < 1+elementSize {
+ return fmt.Errorf("invalid variant value: object size requires
%d bytes, got %d", 1+elementSize, len(value))
+ }
+ numElements = readLEU32(value[1 : 1+elementSize])
+
+ idStart := 1 + elementSize
+ offsetStart := idStart + uint64(numElements)*uint64(idSize)
+ dataStart := offsetStart + (uint64(numElements)+1)*uint64(offsetSize)
+ if dataStart > uint64(len(value)) {
+ return fmt.Errorf("invalid variant value: object offset table
ends at %d, got %d bytes", dataStart, len(value))
+ }
+ finalOffsetPos := offsetStart + uint64(numElements)*uint64(offsetSize)
+ dataSize := readLEU32(value[int(finalOffsetPos) :
int(finalOffsetPos)+int(offsetSize)])
+ if dataStart+uint64(dataSize) > uint64(len(value)) {
+ return fmt.Errorf("invalid variant value: object data ends at
%d, got %d bytes", dataStart+uint64(dataSize), len(value))
+ }
+
+ var previousKey string
+ for i := range numElements {
+ idPos := idStart + uint64(i)*uint64(idSize)
+ id := readLEU32(value[int(idPos) : int(idPos)+int(idSize)])
+ key, err := meta.KeyAt(id)
+ if err != nil {
+ return fmt.Errorf("invalid variant value: object field
%d has invalid field ID %d: %w", i, id, err)
+ }
+ if i > 0 && strings.Compare(previousKey, key) >= 0 {
+ return fmt.Errorf("invalid variant value: object field
names are not strictly sorted at field %d", i)
+ }
+ previousKey = key
+
+ offsetPos := offsetStart + uint64(i)*uint64(offsetSize)
+ offset := readLEU32(value[int(offsetPos) :
int(offsetPos)+int(offsetSize)])
+ if uint64(offset) > uint64(dataSize) {
+ return fmt.Errorf("invalid variant value: object field
%d offset %d is out of range", i, offset)
+ }
+ }
+
+ frame.dataStart = dataStart
+ frame.offsetStart = offsetStart
+ frame.offsetSize = offsetSize
+ frame.numChildren = numElements
+ frame.dataSize = dataSize
+ frame.size = dataStart + uint64(dataSize)
+ return nil
+}
+
+func nextValidationChild(frame *validationFrame) ([]byte, int, uint64, uint64,
error) {
+ index := int(frame.nextChild)
+ position := frame.offsetStart +
uint64(frame.nextChild)*uint64(frame.offsetSize)
+ offset := readLEU32(frame.value[int(position) :
int(position)+int(frame.offsetSize)])
+ start := frame.dataStart + uint64(offset)
+
+ if BasicType(frame.kind) == BasicArray {
+ nextPosition := position + uint64(frame.offsetSize)
+ nextOffset := readLEU32(frame.value[int(nextPosition) :
int(nextPosition)+int(frame.offsetSize)])
+ end := frame.dataStart + uint64(nextOffset)
+ return frame.value[int(start):int(end)], index, 0, end - start,
nil
+ }
+
+ if uint64(offset) > uint64(frame.dataSize) {
+ return nil, index, 0, 0, fmt.Errorf("invalid variant value:
object field %d offset %d is out of range", index, offset)
+ }
+ return frame.value[int(start):], index, uint64(offset), 0, nil
+}
+
// New creates a Value by parsing both the metadata and value bytes.
func New(meta, value []byte) (Value, error) {
m, err := NewMetadata(meta)
@@ -755,11 +1137,11 @@ func (v Value) Value() any {
debug.Assert(len(v.value) >= int(1+nelemSize), "invalid object
value: too short")
numElements := readLEU32(v.value[1 : 1+nelemSize])
- idStart := uint32(1 + nelemSize)
- offsetStart := idStart + numElements*uint32(fieldIdSz)
- dataStart := offsetStart + (numElements+1)*uint32(fieldOffsetSz)
+ idStart := uint64(1 + nelemSize)
+ offsetStart := idStart + uint64(numElements)*uint64(fieldIdSz)
+ dataStart := offsetStart +
(uint64(numElements)+1)*uint64(fieldOffsetSz)
- debug.Assert(dataStart <= uint32(len(v.value)), "invalid object
value: dataStart out of range")
+ debug.Assert(dataStart <= uint64(len(v.value)), "invalid object
value: dataStart out of range")
return ObjectValue{
value: v.value,
meta: v.meta,
@@ -768,7 +1150,7 @@ func (v Value) Value() any {
dataStart: dataStart,
idSize: fieldIdSz,
offsetSize: fieldOffsetSz,
- idStart: uint8(idStart),
+ idStart: idStart,
}
case BasicArray:
valueHdr := (v.value[0] >> basicTypeBits)
@@ -776,25 +1158,25 @@ func (v Value) Value() any {
isLarge := ((valueHdr >> 2) & 0b1) == 1
var (
- sz int
- offsetStart, dataStart int
+ sz uint32
+ offsetStart uint64
)
if isLarge {
- sz, offsetStart = int(readLEU32(v.value[1:5])), 5
+ sz, offsetStart = readLEU32(v.value[1:5]), 5
} else {
- sz, offsetStart = int(v.value[1]), 2
+ sz, offsetStart = uint32(v.value[1]), 2
}
- dataStart = offsetStart + (sz+1)*int(fieldOffsetSz)
- debug.Assert(dataStart <= len(v.value), "invalid array value:
dataStart out of range")
+ dataStart := offsetStart + (uint64(sz)+1)*uint64(fieldOffsetSz)
+ debug.Assert(dataStart <= uint64(len(v.value)), "invalid array
value: dataStart out of range")
return ArrayValue{
value: v.value,
meta: v.meta,
- numElements: uint32(sz),
- dataStart: uint32(dataStart),
+ numElements: sz,
+ dataStart: dataStart,
offsetSize: fieldOffsetSz,
- offsetStart: uint8(offsetStart),
+ offsetStart: offsetStart,
}
}
diff --git a/parquet/variant/variant_benchmark_test.go
b/parquet/variant/variant_benchmark_test.go
new file mode 100644
index 00000000..63fe3093
--- /dev/null
+++ b/parquet/variant/variant_benchmark_test.go
@@ -0,0 +1,113 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package variant
+
+import (
+ "fmt"
+ "testing"
+)
+
+func benchmarkNewWithMetadata(b *testing.B, value Value) {
+ b.Helper()
+ b.ReportAllocs()
+ b.ResetTimer()
+
+ for range b.N {
+ if _, err := NewWithMetadata(value.Metadata(), value.Bytes());
err != nil {
+ b.Fatal(err)
+ }
+ }
+}
+
+func benchmarkObjectValue(b *testing.B, numFields int) Value {
+ b.Helper()
+
+ var builder Builder
+ start := builder.Offset()
+ fields := make([]FieldEntry, 0, numFields)
+ for i := range numFields {
+ key := fmt.Sprintf("field%02d", i)
+ fields = append(fields, builder.NextField(start, key))
+ if err := builder.AppendInt(int64(i)); err != nil {
+ b.Fatal(err)
+ }
+ }
+ if err := builder.FinishObject(start, fields); err != nil {
+ b.Fatal(err)
+ }
+
+ value, err := builder.Build()
+ if err != nil {
+ b.Fatal(err)
+ }
+ return value
+}
+
+func benchmarkArrayValue(b *testing.B, numElements int) Value {
+ b.Helper()
+
+ var builder Builder
+ start := builder.Offset()
+ offsets := make([]int, 0, numElements)
+ for i := range numElements {
+ offsets = append(offsets, builder.NextElement(start))
+ if err := builder.AppendInt(int64(i)); err != nil {
+ b.Fatal(err)
+ }
+ }
+ if err := builder.FinishArray(start, offsets); err != nil {
+ b.Fatal(err)
+ }
+
+ value, err := builder.Build()
+ if err != nil {
+ b.Fatal(err)
+ }
+ return value
+}
+
+func benchmarkNestedArrayValue(b *testing.B, depth int) Value {
+ b.Helper()
+
+ var nested any = int64(1)
+ for range depth {
+ nested = []any{nested}
+ }
+
+ var builder Builder
+ if err := builder.Append(nested); err != nil {
+ b.Fatal(err)
+ }
+
+ value, err := builder.Build()
+ if err != nil {
+ b.Fatal(err)
+ }
+ return value
+}
+
+func BenchmarkNewWithMetadataObject40Fields(b *testing.B) {
+ benchmarkNewWithMetadata(b, benchmarkObjectValue(b, 40))
+}
+
+func BenchmarkNewWithMetadataArray40Elements(b *testing.B) {
+ benchmarkNewWithMetadata(b, benchmarkArrayValue(b, 40))
+}
+
+func BenchmarkNewWithMetadataNestedArray1000(b *testing.B) {
+ benchmarkNewWithMetadata(b, benchmarkNestedArrayValue(b, 1000))
+}
diff --git a/parquet/variant/variant_test.go b/parquet/variant/variant_test.go
index 65d97000..89a5b03f 100644
--- a/parquet/variant/variant_test.go
+++ b/parquet/variant/variant_test.go
@@ -251,6 +251,30 @@ func primitiveHeader(p variant.PrimitiveType) uint8 {
return (uint8(p) << 2)
}
+func objectValueLayout(value []byte) (offsetStart, offsetSize, dataStart int) {
+ typeInfo := value[0] >> 2
+ numElements := int(value[1])
+ idSize := int((typeInfo>>2)&0b11) + 1
+ offsetSize = int(typeInfo&0b11) + 1
+ offsetStart = 2 + numElements*idSize
+ dataStart = offsetStart + (numElements+1)*offsetSize
+ return
+}
+
+func twoFieldObject(t *testing.T) variant.Value {
+ t.Helper()
+ var b variant.Builder
+ start := b.Offset()
+ fields := []variant.FieldEntry{b.NextField(start, "a")}
+ require.NoError(t, b.AppendInt(1))
+ fields = append(fields, b.NextField(start, "b"))
+ require.NoError(t, b.AppendInt(2))
+ require.NoError(t, b.FinishObject(start, fields))
+ v, err := b.Build()
+ require.NoError(t, err)
+ return v
+}
+
func TestNullValue(t *testing.T) {
emptyMeta := variant.EmptyMetadataBytes
nullChars := []byte{primitiveHeader(variant.PrimitiveNull)}
@@ -580,6 +604,45 @@ func TestArrayValues(t *testing.T) {
})
}
+func TestIndexedValueRoundTrip(t *testing.T) {
+ assertRoundTrip := func(t *testing.T, value variant.Value) {
+ t.Helper()
+
+ roundTripped, err := variant.NewWithMetadata(value.Metadata(),
value.Bytes())
+ require.NoError(t, err)
+ assert.Equal(t, value.Bytes(), roundTripped.Bytes())
+ }
+
+ t.Run("array values", func(t *testing.T) {
+ v, err := variant.ParseJSON(`[1, 2, {"nested": 3}]`, false)
+ require.NoError(t, err)
+
+ arr := v.Value().(variant.ArrayValue)
+ for i := range arr.Len() {
+ value, err := arr.Value(i)
+ require.NoError(t, err)
+ assertRoundTrip(t, value)
+ }
+ })
+
+ t.Run("object values", func(t *testing.T) {
+ v, err := variant.ParseJSON(`{"a": 1, "b": [2, 3]}`, false)
+ require.NoError(t, err)
+
+ obj := v.Value().(variant.ObjectValue)
+ for _, key := range []string{"a", "b"} {
+ field, err := obj.ValueByKey(key)
+ require.NoError(t, err)
+ assertRoundTrip(t, field.Value)
+ }
+ for i := range obj.NumElements() {
+ field, err := obj.FieldAt(i)
+ require.NoError(t, err)
+ assertRoundTrip(t, field.Value)
+ }
+ })
+}
+
func TestInvalidMetadata(t *testing.T) {
tests := []struct {
name string
@@ -700,6 +763,173 @@ func TestInvalidPrimitiveValue(t *testing.T) {
}
}
+func TestInvalidCompoundValue(t *testing.T) {
+ for _, input := range []string{`[1,2]`, `{"value":1}`} {
+ t.Run(input, func(t *testing.T) {
+ v, err := variant.ParseJSON(input, false)
+ require.NoError(t, err)
+
+ value := v.Bytes()
+ _, err = variant.NewWithMetadata(v.Metadata(),
value[:len(value)-1])
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "invalid variant value")
+ })
+ }
+}
+
+func TestValidateObjectPhysicalOffsets(t *testing.T) {
+ var b variant.Builder
+ start := b.Offset()
+ fields := []variant.FieldEntry{b.NextField(start, "c")}
+ require.NoError(t, b.AppendInt(3))
+ fields = append(fields, b.NextField(start, "a"))
+ require.NoError(t, b.AppendInt(1))
+ fields = append(fields, b.NextField(start, "b"))
+ require.NoError(t, b.AppendInt(2))
+ require.NoError(t, b.FinishObject(start, fields))
+ v, err := b.Build()
+ require.NoError(t, err)
+
+ // The fields are sorted by key, but their values were appended as c,
a, b.
+ // This produces offsets in key order of 2, 4, 0, which is valid
Variant data.
+ parsed, err := variant.NewWithMetadata(v.Metadata(), v.Bytes())
+ require.NoError(t, err)
+ obj := parsed.Value().(variant.ObjectValue)
+ for _, tt := range []struct {
+ key string
+ value int8
+ }{
+ {key: "a", value: 1},
+ {key: "b", value: 2},
+ {key: "c", value: 3},
+ } {
+ field, err := obj.ValueByKey(tt.key)
+ require.NoError(t, err)
+ assert.Equal(t, tt.value, field.Value.Value())
+ }
+}
+
+func TestValidateObjectMetadataAndRanges(t *testing.T) {
+ base := twoFieldObject(t)
+ offsetStart, offsetSize, dataStart := objectValueLayout(base.Bytes())
+
+ t.Run("invalid field ID", func(t *testing.T) {
+ value := append([]byte(nil), base.Bytes()...)
+ value[2] = 0xff
+ _, err := variant.NewWithMetadata(base.Metadata(), value)
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "invalid field ID")
+ })
+
+ t.Run("unsorted field names", func(t *testing.T) {
+ value := append([]byte(nil), base.Bytes()...)
+ value[2], value[3] = value[3], value[2]
+ _, err := variant.NewWithMetadata(base.Metadata(), value)
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "not strictly sorted")
+ })
+
+ t.Run("duplicate field names", func(t *testing.T) {
+ value := append([]byte(nil), base.Bytes()...)
+ value[3] = value[2]
+ _, err := variant.NewWithMetadata(base.Metadata(), value)
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "not strictly sorted")
+ })
+
+ t.Run("overlapping ranges", func(t *testing.T) {
+ value := append([]byte(nil), base.Bytes()...)
+ value[offsetStart+offsetSize] = 0
+ _, err := variant.NewWithMetadata(base.Metadata(), value)
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "overlap")
+ })
+
+ t.Run("gap between ranges", func(t *testing.T) {
+ var b variant.Builder
+ start := b.Offset()
+ fields := []variant.FieldEntry{b.NextField(start, "a")}
+ require.NoError(t, b.AppendInt(1))
+ fields = append(fields, b.NextField(start, "b"))
+ require.NoError(t, b.AppendInt(2))
+ // Leave an otherwise valid value in the physical data region
without
+ // assigning it to a field.
+ require.NoError(t, b.AppendInt(3))
+ require.NoError(t, b.FinishObject(start, fields))
+ v, err := b.Build()
+ require.NoError(t, err)
+
+ value := append([]byte(nil), v.Bytes()...)
+ offsetStart, offsetSize, _ := objectValueLayout(value)
+ value[offsetStart+offsetSize] = 4
+ _, err = variant.NewWithMetadata(v.Metadata(), value)
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "gap")
+ })
+
+ t.Run("offset into another value", func(t *testing.T) {
+ value := append([]byte(nil), base.Bytes()...)
+ value[offsetStart+offsetSize] = 1
+ _, err := variant.NewWithMetadata(base.Metadata(), value)
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "overlap")
+ })
+
+ t.Run("top-level trailing bytes", func(t *testing.T) {
+ value := append(append([]byte(nil), base.Bytes()...), 0)
+ _, err := variant.NewWithMetadata(base.Metadata(), value)
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "trailing bytes")
+ })
+
+ assert.Greater(t, dataStart, offsetStart)
+}
+
+func TestValidateDeeplyNestedValue(t *testing.T) {
+ var nested any = int64(1)
+ for range 1000 {
+ nested = []any{nested}
+ }
+
+ var b variant.Builder
+ require.NoError(t, b.Append(nested))
+ v, err := b.Build()
+ require.NoError(t, err)
+
+ _, err = variant.NewWithMetadata(v.Metadata(), v.Bytes())
+ require.NoError(t, err)
+}
+
+func TestRejectsExcessiveNesting(t *testing.T) {
+ var nested any = int64(1)
+ for range 1025 {
+ nested = []any{nested}
+ }
+
+ var b variant.Builder
+ require.NoError(t, b.Append(nested))
+ v, err := b.Build()
+ require.NoError(t, err)
+
+ _, err = variant.NewWithMetadata(v.Metadata(), v.Bytes())
+ require.Error(t, err)
+ assert.Contains(t, err.Error(), "maximum nesting depth exceeded")
+}
+
+func FuzzNewWithMetadataNeverPanics(f *testing.F) {
+ f.Add([]byte{byte(variant.PrimitiveNull << 2)})
+ f.Add([]byte{byte(variant.BasicShortString)})
+ f.Add([]byte{byte(variant.BasicArray), 0, 0})
+ f.Add([]byte{byte(variant.BasicObject), 0, 0})
+
+ meta, err := variant.NewMetadata(variant.EmptyMetadataBytes[:])
+ require.NoError(f, err)
+
+ f.Fuzz(func(t *testing.T, value []byte) {
+ _, _ = variant.NewWithMetadata(meta, value)
+ })
+}
+
func TestInvalidObjectAccess(t *testing.T) {
v := loadVariant(t, "object_primitive")
obj := v.Value().(variant.ObjectValue)
@@ -723,17 +953,9 @@ func TestInvalidObjectAccess(t *testing.T) {
// Set field ID to an invalid value
corruptBytes[idPosition] = 0xFF
- corrupt, err := variant.NewWithMetadata(v.Metadata(),
corruptBytes)
- require.NoError(t, err)
-
- corruptObj := corrupt.Value().(variant.ObjectValue)
- _, err = corruptObj.FieldAt(0)
- require.Error(t, err)
- assert.Contains(t, err.Error(), "fieldID")
-
- _, err = corruptObj.ValueByKey("int_field")
+ _, err := variant.NewWithMetadata(v.Metadata(), corruptBytes)
require.Error(t, err)
- assert.Contains(t, err.Error(), "fieldID")
+ assert.Contains(t, err.Error(), "invalid field ID")
})
}
