Skip to content

Commit c91c8eb

Browse files
fix(layout): check list offsets before the list reader uses them (#68)
## Summary Closes #56. Part of #55. The list reader trusted the offsets it decoded. When offsets decrease, go negative or point past the elements, most reads return with no error, and a sparse read of decreasing offsets panics in `vortex-mask`. Readers now check offsets as they read them, so a malformed file fails the read with an error. ## Changes - `ListReader::fetch_raw_offsets` checks the offsets it returns. They must be the expected count, castable to `u64` (negative values fail), non-decreasing, and the last one can't be past the elements child's row count. Every read path gets its offsets from here, so the range arithmetic, `kept_elements` and `ListArray::new_unchecked` after it can rely on that. Only the offsets a read uses get checked, so pruning doesn't change and nothing scans the whole column on open. The `row_range.end + 1` there is now checked too. - `ListLayout::new` becomes `ListLayout::try_new`. It checks the children the way deserialization does: elements match the list's element dtype, offsets are non-nullable integers with at least one row, and validity is non-nullable bool with one row per list. Before, it used saturating subtraction and `vortex_expect`. - The writer adds each chunk's element count with `checked_add`. Not in this PR: which integer types the frozen format accepts for offsets. That's a #54 decision. Readers still accept any integer type that casts to `u64`. ## Testing - `malformed_offsets_fail_the_read` covers decreasing, past-the-end and negative offsets on full, bounded, sparse and length-only reads. Without the check, 8 of the 12 cases return with no error, 2 fail later with unrelated errors (an out-of-bounds slice and a filter length mismatch), and 1 panics. Only one, a sparse read of negative offsets, already failed cleanly. - `try_new_rejects_mismatched_children` covers the wrong elements dtype, float offsets, nullable offsets, no offsets and a validity row count that doesn't match. - `cargo test -p vortex-layout -p vortex-file` and `cargo clippy -p vortex-layout -p vortex-file --all-targets`. - Read a real list-layout file of nested event data through the data source with the check in place. The bytes read and rows came out the same as before. --------- Signed-off-by: Rasheed Khoshnaw <[email protected]> Signed-off-by: Christopher Wirt <[email protected]> Co-authored-by: Christopher Wirt <[email protected]>
1 parent 00130bd commit c91c8eb

4 files changed

Lines changed: 281 additions & 25 deletions

File tree

‎vortex-layout/src/layouts/list/mod.rs‎

Lines changed: 104 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -172,27 +172,56 @@ impl VTable for List {
172172
}
173173

174174
impl Layout<List> {
175-
/// Construct a list layout from its children.
176-
pub fn new(
175+
/// Construct a list layout from its children, checking them the way deserialization does: the
176+
/// elements match the list's element dtype, the offsets are non-nullable integers with one
177+
/// more row than the list, and a nullable list has a non-nullable bool validity child with one
178+
/// row per list.
179+
pub fn try_new(
177180
dtype: DType,
178181
elements: LayoutRef,
179182
offsets: LayoutRef,
180183
validity: Option<LayoutRef>,
181-
) -> Self {
182-
let row_count = offsets.row_count().saturating_sub(1);
183-
let offsets_ptype = offsets.dtype().as_ptype();
184+
) -> VortexResult<Self> {
185+
let elements_dtype = dtype
186+
.as_list_element_opt()
187+
.ok_or_else(|| vortex_err!("ListLayout requires a List dtype, got {dtype}"))?;
188+
vortex_ensure_eq!(
189+
elements.dtype(),
190+
elements_dtype.as_ref(),
191+
"ListLayout elements dtype does not match the list's element dtype"
192+
);
193+
let offsets_ptype = match offsets.dtype() {
194+
DType::Primitive(ptype, Nullability::NonNullable) if ptype.is_int() => *ptype,
195+
other => vortex_bail!("ListLayout offsets must be non-nullable integers, got {other}"),
196+
};
197+
let row_count = offsets
198+
.row_count()
199+
.checked_sub(1)
200+
.ok_or_else(|| vortex_err!("ListLayout offsets must have at least one row"))?;
201+
if let Some(validity) = &validity {
202+
vortex_ensure_eq!(
203+
validity.dtype(),
204+
&DType::Bool(Nullability::NonNullable),
205+
"ListLayout validity must be non-nullable bool"
206+
);
207+
vortex_ensure_eq!(
208+
validity.row_count(),
209+
row_count,
210+
"List validity row count does not match parent"
211+
);
212+
}
184213
let mut children = vec![elements, offsets];
185214
children.extend(validity);
186-
Self::validate_children(&dtype, children.len()).vortex_expect("invalid list children");
187-
LayoutParts::new(
215+
Self::validate_children(&dtype, children.len())?;
216+
Ok(LayoutParts::new(
188217
List,
189218
dtype,
190219
row_count,
191220
Vec::new(),
192221
OwnedLayoutChildren::layout_children(children),
193222
ListData { offsets_ptype },
194223
)
195-
.into_typed()
224+
.into_typed())
196225
}
197226

198227
/// Returns the elements child.
@@ -272,6 +301,7 @@ mod tests {
272301
use vortex_session::registry::ReadContext;
273302

274303
use super::List;
304+
use super::ListLayout;
275305
use super::ListLayoutMetadata;
276306
use crate::LayoutBuildContext;
277307
use crate::LayoutDeserialization;
@@ -345,6 +375,72 @@ mod tests {
345375
Ok(())
346376
}
347377

378+
/// `ListLayout::try_new` rejects children that deserialization would reject.
379+
#[rstest]
380+
#[case::elements_dtype(
381+
PType::I64,
382+
PType::U64,
383+
Nullability::NonNullable,
384+
4,
385+
None,
386+
"elements dtype"
387+
)]
388+
#[case::float_offsets(PType::I32, PType::F64, Nullability::NonNullable, 4, None, "integers")]
389+
#[case::nullable_offsets(PType::I32, PType::U64, Nullability::Nullable, 4, None, "integers")]
390+
#[case::no_offsets(
391+
PType::I32,
392+
PType::U64,
393+
Nullability::NonNullable,
394+
0,
395+
None,
396+
"at least one row"
397+
)]
398+
#[case::validity_rows(
399+
PType::I32,
400+
PType::U64,
401+
Nullability::NonNullable,
402+
4,
403+
Some(2),
404+
"validity row count"
405+
)]
406+
fn try_new_rejects_mismatched_children(
407+
#[case] elements_ptype: PType,
408+
#[case] offsets_ptype: PType,
409+
#[case] offsets_nullability: Nullability,
410+
#[case] offsets_rows: u64,
411+
#[case] validity_rows: Option<u64>,
412+
#[case] message: &str,
413+
) {
414+
let read_ctx = ReadContext::new([]);
415+
let list_nullability = Nullability::from(validity_rows.is_some());
416+
let dtype = DType::List(
417+
Arc::new(DType::Primitive(PType::I32, Nullability::NonNullable)),
418+
list_nullability,
419+
);
420+
let flat = |rows, dtype, segment: u32| {
421+
FlatLayout::new(rows, dtype, segment.into(), read_ctx.clone()).into_layout()
422+
};
423+
let elements = flat(
424+
0,
425+
DType::Primitive(elements_ptype, Nullability::NonNullable),
426+
0,
427+
);
428+
let offsets = flat(
429+
offsets_rows,
430+
DType::Primitive(offsets_ptype, offsets_nullability),
431+
1,
432+
);
433+
let validity =
434+
validity_rows.map(|rows| flat(rows, DType::Bool(Nullability::NonNullable), 2));
435+
let err = ListLayout::try_new(dtype, elements, offsets, validity)
436+
.err()
437+
.map(|err| err.to_string());
438+
assert!(
439+
err.as_ref().is_some_and(|err| err.contains(message)),
440+
"{err:?}"
441+
);
442+
}
443+
348444
#[test]
349445
fn test_build_rejects_unknown_offsets_ptype() -> VortexResult<()> {
350446
let dtype = DType::List(

‎vortex-layout/src/layouts/list/reader.rs‎

Lines changed: 161 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -26,13 +26,18 @@ use vortex_array::dtype::Nullability;
2626
use vortex_array::dtype::PType;
2727
use vortex_array::expr::BoundExpression;
2828
use vortex_array::expr::root;
29+
use vortex_array::match_each_signed_integer_ptype;
2930
use vortex_array::scalar_fn::fns::operators::Operator;
3031
use vortex_array::validity::Validity;
3132
use vortex_buffer::BitBufferMut;
3233
use vortex_buffer::Buffer;
3334
use vortex_buffer::BufferMut;
3435
use vortex_error::VortexExpect;
3536
use vortex_error::VortexResult;
37+
use vortex_error::vortex_bail;
38+
use vortex_error::vortex_ensure;
39+
use vortex_error::vortex_ensure_eq;
40+
use vortex_error::vortex_err;
3641
use vortex_mask::AllOr;
3742
use vortex_mask::Mask;
3843
use vortex_session::VortexSession;
@@ -353,16 +358,28 @@ impl ListReader {
353358
/// Fire the offsets read for `row_range` in list row space. The offsets child has an extra entry, so reading
354359
/// `row_range` maps to offsets in `[row_range.start..row_range.end + 1)`.
355360
///
356-
/// No mask or expression is applied.
361+
/// No mask or expression is applied. The offsets come back as `u64` and checked with
362+
/// [`check_offsets`], so every later range, subtraction and `ListArray::new_unchecked` can rely
363+
/// on them.
357364
fn fetch_raw_offsets(&self, row_range: &Range<u64>) -> VortexResult<ArrayFuture> {
358-
let offsets_range = row_range.start..(row_range.end + 1);
365+
let end = row_range.end.checked_add(1).ok_or_else(|| {
366+
vortex_err!("List row range {row_range:?} overflows its offsets range")
367+
})?;
368+
let offsets_range = row_range.start..end;
359369
let offsets_count = usize::try_from(offsets_range.end - offsets_range.start)?;
360370
let root = root().bind(self.offsets.dtype())?;
361-
self.offsets.projection_evaluation(
371+
let fut = self.offsets.projection_evaluation(
362372
&offsets_range,
363373
&root,
364374
MaskFuture::new_true(offsets_count),
365-
)
375+
)?;
376+
let elements_rows = self.elements.row_count();
377+
let session = self.session.clone();
378+
Ok(async move {
379+
let offsets = fut.await?;
380+
check_offsets(offsets, offsets_count, elements_rows, &session)
381+
}
382+
.boxed())
366383
}
367384

368385
/// Fire the read of `expr` over the elements of `row_range` that `mask` selects, in element
@@ -496,8 +513,9 @@ fn lists_over(
496513
fields: Option<&FieldNames>,
497514
ctx: &mut ExecutionCtx,
498515
) -> VortexResult<ArrayRef> {
499-
// SAFETY: the offsets are monotonically increasing and index into the elements read, which
500-
// give one value per element, and the validity covers the same lists.
516+
// SAFETY: `check_offsets` made the offsets non-decreasing and bounded by the elements child;
517+
// the read paths rebase or rebuild them over the elements read, which give one value per
518+
// element, and the validity covers the same lists.
501519
let Some(fields) = fields else {
502520
return Ok(unsafe { ListArray::new_unchecked(elements, offsets, validity) }.into_array());
503521
};
@@ -742,6 +760,53 @@ fn fetch_validity(
742760
.boxed())
743761
}
744762

763+
/// Decode `offsets` to `u64` and check what the readers rely on: `count` non-negative values, each
764+
/// no greater than the next, the last no greater than the elements child's `elements_rows`. A file
765+
/// whose offsets break this fails the read instead of panicking or building lists past the elements.
766+
fn check_offsets(
767+
offsets: ArrayRef,
768+
count: usize,
769+
elements_rows: u64,
770+
session: &VortexSession,
771+
) -> VortexResult<ArrayRef> {
772+
vortex_ensure_eq!(
773+
offsets.len(),
774+
count,
775+
"List offsets read returned the wrong number of offsets"
776+
);
777+
let mut ctx = session.create_execution_ctx();
778+
let offsets = offsets.execute::<PrimitiveArray>(&mut ctx)?;
779+
// Casting can trust persisted min/max statistics, so check the actual signed values first.
780+
if offsets.ptype().is_signed_int() {
781+
match_each_signed_integer_ptype!(offsets.ptype(), |P| {
782+
let values = offsets.as_slice::<P>();
783+
if let Some(i) = values.iter().position(|&value| value < 0) {
784+
vortex_bail!("List offset at index {i} is negative: {}", values[i]);
785+
}
786+
});
787+
}
788+
let offsets = offsets
789+
.into_array()
790+
.cast(DType::Primitive(PType::U64, Nullability::NonNullable))?
791+
.execute::<PrimitiveArray>(&mut ctx)?;
792+
let values = offsets.as_slice::<u64>();
793+
if let Some(i) = values.windows(2).position(|w| w[0] > w[1]) {
794+
vortex_bail!(
795+
"List offsets decrease at offset {}: {} > {}",
796+
i,
797+
values[i],
798+
values[i + 1]
799+
);
800+
}
801+
if let Some(&last) = values.last() {
802+
vortex_ensure!(
803+
last <= elements_rows,
804+
"List offset {last} is past the end of its {elements_rows} elements"
805+
);
806+
}
807+
Ok(offsets.into_array())
808+
}
809+
745810
/// Read `offsets[0]` and `offsets[-1]` and return the elements range they bound.
746811
fn elements_range_from_offsets(
747812
offsets: &ArrayRef,
@@ -835,7 +900,10 @@ mod tests {
835900
use vortex_array::expr::mask;
836901
use vortex_array::expr::pack;
837902
use vortex_array::expr::select;
903+
use vortex_array::expr::stats::Precision;
904+
use vortex_array::expr::stats::Stat;
838905
use vortex_array::expr::var;
906+
use vortex_array::match_each_signed_integer_ptype;
839907
use vortex_buffer::buffer;
840908
use vortex_io::session::RuntimeSession;
841909
use vortex_io::session::RuntimeSessionExt;
@@ -1128,6 +1196,90 @@ mod tests {
11281196
.into_array()
11291197
}
11301198

1199+
/// A non-nullable `list<i32>` of 3 lists over 5 elements with the given `offsets`, written
1200+
/// child by child so the offsets can break what the list writer guarantees.
1201+
async fn list_with_offsets(
1202+
offsets: ArrayRef,
1203+
) -> VortexResult<(Arc<dyn SegmentSource>, LayoutRef, VortexSession)> {
1204+
let session = layout_test_session().with_tokio();
1205+
let segments = Arc::new(TestSegments::default());
1206+
let mut children = Vec::new();
1207+
for array in [buffer![1i32, 2, 3, 4, 5].into_array(), offsets] {
1208+
let (ptr, eof) = SequenceId::root().split();
1209+
let stream = array.to_array_stream().sequenced(ptr);
1210+
let segment_sink = Arc::<TestSegments>::clone(&segments);
1211+
children.push(
1212+
FlatLayoutStrategy::default()
1213+
.write_stream(
1214+
ArrayContext::empty().into(),
1215+
segment_sink,
1216+
stream,
1217+
eof,
1218+
&session,
1219+
)
1220+
.await?,
1221+
);
1222+
}
1223+
let [elements, offsets] = <[LayoutRef; 2]>::try_from(children).expect("two children");
1224+
let dtype = DType::List(Arc::new(elements.dtype().clone()), Nullability::NonNullable);
1225+
let layout = ListLayout::try_new(dtype, elements, offsets, None)?.into_layout();
1226+
Ok((segments, layout, session))
1227+
}
1228+
1229+
#[rstest]
1230+
#[case::same_width_cast(buffer![-2i64, -1].into_array())]
1231+
#[case::widening_cast(buffer![-2i32, -1].into_array())]
1232+
fn negative_offsets_ignore_persisted_statistics(#[case] offsets: ArrayRef) {
1233+
match_each_signed_integer_ptype!(offsets.dtype().as_ptype(), |P| {
1234+
let min: P = 0;
1235+
let max: P = 1;
1236+
offsets.statistics().set(Stat::Min, Precision::exact(min));
1237+
offsets.statistics().set(Stat::Max, Precision::exact(max));
1238+
});
1239+
1240+
// The forged bounds let a statistics-based cast wrap negative offsets. A large logical
1241+
// elements count also makes the wrapped values pass the terminal-bound check.
1242+
let error = check_offsets(offsets, 2, u64::MAX, &SESSION)
1243+
.expect_err("negative offsets must fail even when persisted statistics say they fit");
1244+
assert!(error.to_string().contains("negative"), "{error}");
1245+
}
1246+
1247+
/// Offsets that decrease, run past the elements or are negative fail every read path with an
1248+
/// error, instead of panicking or building lists over elements that aren't there.
1249+
#[rstest]
1250+
#[tokio::test]
1251+
async fn malformed_offsets_fail_the_read(
1252+
#[values(
1253+
(buffer![0u64, 3, 2, 5].into_array(), "decrease"),
1254+
(buffer![0u64, 2, 4, 6].into_array(), "past the end"),
1255+
(buffer![0i64, 2, -4, 5].into_array(), "negative"),
1256+
)]
1257+
case: (ArrayRef, &str),
1258+
#[values("full", "bounded", "sparse", "lengths")] read: &str,
1259+
) -> VortexResult<()> {
1260+
let (offsets, message) = case;
1261+
let (segments, layout, session) = list_with_offsets(offsets).await?;
1262+
let reader =
1263+
layout.new_reader("".into(), segments, &session, &LayoutReaderContext::new())?;
1264+
let (range, expr, mask) = match read {
1265+
"full" => (0..3, root(), Mask::new_true(3)),
1266+
"bounded" => (1..3, root(), Mask::new_true(2)),
1267+
"sparse" => (0..3, root(), Mask::from_iter([true, false, true])),
1268+
_ => (0..3, list_length(root()), Mask::new_true(3)),
1269+
};
1270+
let expr = expr.bind(reader.dtype())?;
1271+
let result = match reader.projection_evaluation(&range, &expr, MaskFuture::ready(mask)) {
1272+
Ok(fut) => fut.await.map(drop),
1273+
Err(err) => Err(err),
1274+
};
1275+
let err = result.err().map(|err| err.to_string());
1276+
assert!(
1277+
err.as_ref().is_some_and(|err| err.contains(message)),
1278+
"{read}: {err:?}"
1279+
);
1280+
Ok(())
1281+
}
1282+
11311283
#[tokio::test]
11321284
async fn fetch_offsets_includes_extra_endpoint() -> VortexResult<()> {
11331285
let list = create_basic_list_array(false);
@@ -2059,7 +2211,9 @@ mod tests {
20592211
let list = create_ten_element_list_array(nullable);
20602212
let source = if as_list_view {
20612213
let mut ctx = SESSION.create_execution_ctx();
2062-
list.clone().execute::<ListViewArray>(&mut ctx)?.into_array()
2214+
list.clone()
2215+
.execute::<ListViewArray>(&mut ctx)?
2216+
.into_array()
20632217
} else {
20642218
list.clone()
20652219
};

0 commit comments

Comments
 (0)