quack_rs/vector/list_builder.rs
1// SPDX-License-Identifier: MIT
2// Copyright 2026 Tom F. <https://github.com/tomtom215/>
3// My way of giving something small back to the open source community
4// and encouraging more Rust development!
5
6//! Safe construction of `LIST` and `MAP` output vectors.
7//!
8//! # The hazard this exists to remove
9//!
10//! A `LIST` vector stores a `{ offset, length }` entry per row, plus one flat
11//! child vector holding every row's elements end to end. Writing one means:
12//!
13//! 1. `duckdb_list_vector_reserve` — make room in the child,
14//! 2. write the elements into the child,
15//! 3. `duckdb_list_vector_set_size` — declare how many are valid,
16//! 4. write each parent row's `{ offset, length }` entry.
17//!
18//! Step 1 is the trap. `duckdb_list_vector_reserve` takes a **total** capacity,
19//! not an increment, and when it grows it calls `Vector::Resize`, which
20//! **reallocates the child's data buffer**. Any [`VectorWriter`] made from the
21//! child before that call now holds a dangling pointer — and the natural way to
22//! write a list row by row is to keep one writer and reserve as you go:
23//!
24//! ```rust,ignore
25//! // WRONG: `writer` dangles after the second reserve grows the child.
26//! let mut writer = unsafe { ListVector::child_writer(vec) };
27//! for (row, items) in rows.iter().enumerate() {
28//! unsafe { ListVector::reserve(vec, total + items.len()) }; // may realloc
29//! for (i, item) in items.iter().enumerate() {
30//! unsafe { writer.write_i64(total + i, *item) }; // use-after-free
31//! }
32//! total += items.len();
33//! }
34//! ```
35//!
36//! [`ListBuilder`] keeps one child writer, drops it after every reserve that
37//! grows the child (and fetches a fresh one on the next row), tracks the running
38//! offset, and writes the parent entries for you, so the sequence cannot be got
39//! wrong.
40//!
41//! # Example
42//!
43//! ```rust,no_run
44//! use quack_rs::vector::ListBuilder;
45//!
46//! # fn demo(list_vector: libduckdb_sys::duckdb_vector) {
47//! let rows = [vec![1_i64, 2, 3], vec![], vec![42]];
48//! // SAFETY: `list_vector` is a LIST output vector with BIGINT elements.
49//! let mut builder = unsafe { ListBuilder::new(list_vector) };
50//! for (row, items) in rows.iter().enumerate() {
51//! // SAFETY: the child vector holds BIGINT, and `row` is in bounds.
52//! unsafe {
53//! builder.push_row(row, items.len(), |writer, base| {
54//! for (i, item) in items.iter().enumerate() {
55//! writer.write_i64(base + i, *item);
56//! }
57//! });
58//! }
59//! }
60//! // SAFETY: every element promised by `push_row` was written.
61//! unsafe { builder.finish() };
62//! # }
63//! ```
64//!
65//! # `MAP`
66//!
67//! A `MAP` is a `LIST<STRUCT{key, value}>`, so the same builder drives it —
68//! [`push_map_row`][ListBuilder::push_map_row] hands the closure a writer for
69//! the key child and one for the value child.
70
71use libduckdb_sys::{
72 duckdb_list_entry, duckdb_logical_type, duckdb_vector, duckdb_vector_get_data,
73};
74
75use crate::types::{LogicalType, TypeId};
76use crate::vector::complex::{ListVector, MapVector, StructVector};
77use crate::vector::VectorWriter;
78
79/// `DuckDB`'s ceiling on one buffer of a child vector, **in bytes**
80/// (`DConstants::MAX_VECTOR_SIZE`).
81///
82/// `Vector::Resize` (`vector.cpp`, identical in 1.4.4 and 1.5.5) computes
83/// `capacity * element size * multiplier` for every buffer it grows — the
84/// child's own, each `STRUCT` field's, and each `ARRAY` child's, whose
85/// multiplier is the array size — and throws an `OutOfRangeException` when
86/// one exceeds this. `duckdb_list_vector_reserve` does not catch it, so the
87/// exception unwinds into Rust and the process aborts ("Rust cannot catch
88/// foreign exceptions"). `DuckDB` checks the capacity after rounding it up to
89/// a power of two (`VectorListBuffer::Reserve`). The element limit therefore
90/// depends on the child's type: 2^34 `BIGINT`s, 2^33 `VARCHAR`s, 2^37
91/// `BOOLEAN`s, 2^25 `INTEGER[1000]`s (not 2^37 / 4000).
92/// [`ListBuilder`] computes it from the child's type ([`max_child_capacity`])
93/// and refuses to make a call past it.
94///
95/// Until September 2026 this was documented, and applied, as an element
96/// count: a `BIGINT` list of 2^34 + 1 elements passed the check and aborted
97/// the process.
98///
99/// Staying below it is necessary, not sufficient: a reservation under the
100/// ceiling that the allocator cannot satisfy throws through the same uncaught
101/// path. Use [`ListBuilder::with_element_limit`] to bound lengths that come
102/// from untrusted input.
103///
104/// Typed `u64` to match `duckdb::DConstants::MAX_VECTOR_SIZE`, which is
105/// `1ULL << 37ULL` — an `idx_t`, not a pointer-sized value. It does not fit in a
106/// 32-bit `usize`, so typing it as one made the crate fail to compile for
107/// `wasm32`, which is a target `DuckDB`'s own extension CI builds.
108pub const MAX_LIST_CHILD_CAPACITY: u64 = 1 << 37;
109
110/// [`MAX_LIST_CHILD_CAPACITY`] clamped to this target's `usize`: no element
111/// count can exceed it, whatever the type (`BOOLEAN` and `TINYINT` elements are
112/// one byte each).
113///
114/// On a 64-bit target this is the ceiling itself. On a 32-bit target it is
115/// `usize::MAX`, which bounds the count but not the bytes: the limits
116/// themselves come from [`capacity_for`], which also respects
117/// [`MAX_ALLOCATION_BYTES`].
118#[allow(
119 clippy::cast_possible_truncation,
120 reason = "the branch above proves the value fits"
121)]
122pub(crate) const MAX_CHILD_CAPACITY_USIZE: usize = if MAX_LIST_CHILD_CAPACITY > usize::MAX as u64 {
123 usize::MAX
124} else {
125 MAX_LIST_CHILD_CAPACITY as usize
126};
127
128/// Bytes one element of a childless type occupies in its vector's data buffer
129/// (`GetTypeIdSize` of its physical type), for [`max_child_capacity`].
130///
131/// `DECIMAL` and `ENUM` count their widest storage (16 and 4 bytes), and a
132/// type this crate does not know counts 16, the widest any physical type is,
133/// so the limit errs low rather than high. `VARCHAR`, `BLOB`, `BIT`,
134/// `BIGNUM` and `GEOMETRY` are 16-byte string records; `LIST` and `MAP` are
135/// 16-byte entries (their own children are separate buffers).
136#[must_use]
137pub(crate) const fn element_bytes(id: Option<TypeId>) -> u64 {
138 match id {
139 Some(TypeId::Boolean | TypeId::TinyInt | TypeId::UTinyInt) => 1,
140 Some(TypeId::SmallInt | TypeId::USmallInt) => 2,
141 Some(TypeId::Integer | TypeId::UInteger | TypeId::Float | TypeId::Date | TypeId::Enum) => 4,
142 Some(
143 TypeId::BigInt
144 | TypeId::UBigInt
145 | TypeId::Double
146 | TypeId::Timestamp
147 | TypeId::TimestampTz
148 | TypeId::TimestampS
149 | TypeId::TimestampMs
150 | TypeId::TimestampNs
151 | TypeId::TimestampTzNs
152 | TypeId::Time
153 | TypeId::TimeTz
154 | TypeId::TimeNs,
155 ) => 8,
156 _ => 16,
157 }
158}
159
160/// The most elements a child vector of `bytes_per_element` bytes can be
161/// reserved for under [`MAX_LIST_CHILD_CAPACITY`], clamped to `usize`. `None`
162/// (the per-element size overflowed `u64`) allows nothing.
163///
164/// `DuckDB` rounds a reservation up to the next power of two before checking
165/// its size (`VectorListBuffer::Reserve`, `vector_buffer.cpp`), so the limit
166/// is the largest power of two whose bytes fit, not the ceiling divided by
167/// the element size: 2^25 for a 4000-byte `INTEGER[1000]`, where
168/// 2^37 / 4000 = 34,359,738 elements would be checked as 2^26.
169///
170/// On a 32-bit target the allocation is the tighter bound: see
171/// [`MAX_ALLOCATION_BYTES`].
172#[must_use]
173pub(crate) const fn capacity_for(bytes_per_element: Option<u64>) -> usize {
174 let elements = capacity_within(bytes_per_element, MAX_ALLOCATION_BYTES);
175 if elements > MAX_CHILD_CAPACITY_USIZE as u64 {
176 MAX_CHILD_CAPACITY_USIZE
177 } else {
178 // The branch above proves it fits.
179 #[allow(clippy::cast_possible_truncation)]
180 {
181 elements as usize
182 }
183 }
184}
185
186/// The most bytes one `DuckDB` allocation can hold on this target.
187///
188/// `DuckDB` computes a buffer's size as a 64-bit `idx_t` and hands it to
189/// `malloc` (`Allocator::DefaultAllocate`, `allocator_standard.cpp`), which
190/// takes a `size_t`: on a 32-bit target such as wasm32 the size is narrowed
191/// without a check, so a buffer of 2^32 bytes or more is allocated modulo
192/// 2^32 and comes back too small. `DuckDB`'s own limit
193/// (`Allocator::MAXIMUM_ALLOC_SIZE`, 2^48) is far above that.
194pub(crate) const MAX_ALLOCATION_BYTES: u64 = usize::MAX as u64;
195
196/// [`capacity_for`] for an allocation limit of `allocation_bytes`: the largest
197/// power of two whose elements fit both `DuckDB`'s 2^37-byte ceiling and the
198/// allocation, as a `u64`.
199#[must_use]
200pub(crate) const fn capacity_within(bytes_per_element: Option<u64>, allocation_bytes: u64) -> u64 {
201 let Some(bytes) = bytes_per_element else {
202 return 0;
203 };
204 let ceiling = if allocation_bytes < MAX_LIST_CHILD_CAPACITY {
205 allocation_bytes
206 } else {
207 MAX_LIST_CHILD_CAPACITY
208 };
209 let fitting = ceiling / if bytes == 0 { 1 } else { bytes };
210 if fitting == 0 {
211 return 0;
212 }
213 // The largest power of two not above `fitting`: a request up to it rounds
214 // up to at most it.
215 1_u64 << (u64::BITS - 1 - fitting.leading_zeros())
216}
217
218/// The widest buffer, in bytes per element, that `Vector::Resize` grows for a
219/// vector of type `ty`: its own element size; through `STRUCT` fields and
220/// `UNION` members (and a `UNION`'s one-byte tag) the widest of theirs; and
221/// through an `ARRAY` its child's times the array size. `None` if that
222/// overflows `u64`.
223///
224/// # Safety
225///
226/// `ty` must be a live logical type.
227unsafe fn resize_bytes_per_element(ty: duckdb_logical_type) -> Option<u64> {
228 use libduckdb_sys::{
229 duckdb_array_type_array_size, duckdb_array_type_child_type, duckdb_get_type_id,
230 duckdb_struct_type_child_count, duckdb_struct_type_child_type,
231 duckdb_union_type_member_count, duckdb_union_type_member_type,
232 DUCKDB_TYPE_DUCKDB_TYPE_ARRAY as ARRAY, DUCKDB_TYPE_DUCKDB_TYPE_STRUCT as STRUCT,
233 DUCKDB_TYPE_DUCKDB_TYPE_UNION as UNION,
234 };
235 // SAFETY: `ty` is live per the contract; each child handle below is owned
236 // and destroyed when its `LogicalType` drops.
237 unsafe {
238 let child = |raw: duckdb_logical_type| {
239 if raw.is_null() {
240 return Some(16);
241 }
242 let owned = LogicalType::from_raw(raw);
243 resize_bytes_per_element(owned.as_raw())
244 };
245 match duckdb_get_type_id(ty) {
246 STRUCT => {
247 let mut widest = 0;
248 for i in 0..duckdb_struct_type_child_count(ty) {
249 widest = widest.max(child(duckdb_struct_type_child_type(ty, i))?);
250 }
251 Some(widest)
252 }
253 UNION => {
254 let mut widest = 1;
255 for i in 0..duckdb_union_type_member_count(ty) {
256 widest = widest.max(child(duckdb_union_type_member_type(ty, i))?);
257 }
258 Some(widest)
259 }
260 ARRAY => duckdb_array_type_array_size(ty)
261 .checked_mul(child(duckdb_array_type_child_type(ty))?),
262 raw => Some(element_bytes(TypeId::try_from_duckdb_type(raw))),
263 }
264 }
265}
266
267/// The most child elements a `LIST` or `MAP` vector's child can be reserved
268/// for without `DuckDB` throwing through the C API.
269///
270/// That is the largest power of two whose elements fit in
271/// [`MAX_LIST_CHILD_CAPACITY`] bytes in the widest buffer the child's type
272/// grows (see [`MAX_LIST_CHILD_CAPACITY`]); `DuckDB` rounds a reservation up
273/// to a power of two before it checks the size. 2^34 for `BIGINT`, 2^33 for
274/// `VARCHAR`, 2^25 for `INTEGER[1000]`.
275///
276/// [`ListBuilder`] applies it by itself; call this before
277/// [`ListVector::reserve`] or [`MapVector::reserve`].
278///
279/// # Safety
280///
281/// `vector` must be a valid `LIST` or `MAP` vector.
282#[must_use]
283pub unsafe fn max_child_capacity(vector: duckdb_vector) -> usize {
284 // SAFETY: `vector` is valid per the contract; the returned types are owned
285 // and destroyed when their `LogicalType`s drop. `duckdb_list_type_child_type`
286 // accepts a MAP too (it returns the key/value STRUCT).
287 unsafe {
288 let list = LogicalType::from_raw(libduckdb_sys::duckdb_vector_get_column_type(vector));
289 let raw = libduckdb_sys::duckdb_list_type_child_type(list.as_raw());
290 if raw.is_null() {
291 return 0;
292 }
293 let child = LogicalType::from_raw(raw);
294 capacity_for(resize_bytes_per_element(child.as_raw()))
295 }
296}
297
298/// Incremental builder for a `LIST` (or `MAP`) output vector.
299///
300/// See the [module docs][crate::vector::list_builder] for why the manual
301/// sequence is easy to get wrong.
302#[derive(Debug)]
303pub struct ListBuilder {
304 vector: duckdb_vector,
305 /// Whether `written` has been initialised from the child's current size.
306 /// Deferred to the first write so that [`new`][Self::new] stays `const`
307 /// and makes no `DuckDB` call.
308 started: bool,
309 /// Elements in the child so far, including any already there when the
310 /// builder started — the offset of the next row.
311 written: usize,
312 /// Capacity most recently requested, so `push_row` only reserves when it
313 /// must (each reserve that grows is a reallocation plus a copy).
314 reserved: usize,
315 /// Most child elements this builder will reserve: [`MAX_LIST_CHILD_CAPACITY`]
316 /// unless lowered with [`with_element_limit`][Self::with_element_limit].
317 limit: usize,
318 /// `DuckDB`'s ceiling for the child's type, from [`start`][Self::start]
319 /// on ([`MAX_LIST_CHILD_CAPACITY`] before). Kept apart from `limit` so a
320 /// later `with_element_limit` cannot raise the limit past it.
321 ceiling: usize,
322 /// Set when a requested capacity exceeded `limit`; the builder then writes
323 /// every remaining row as NULL rather than letting `DuckDB` throw.
324 overflowed: bool,
325 /// The child writer, kept between rows so each row does not rebuild it (and,
326 /// for NULL elements, its NULL state). Dropped whenever a reserve grows the
327 /// child, because that reallocates the child's buffers.
328 child: Option<VectorWriter>,
329}
330
331/// What to reserve for `capacity` elements under `limit` (with
332/// `capacity <= limit`): the next power of two, so that growing row by row
333/// reallocates a logarithmic number of times, capped at `limit`. When the
334/// power of two does not fit a `usize` (past 2^31 on a 32-bit target, where
335/// `next_power_of_two` would return 0 in a release build and the closure
336/// would then write past the child), the limit is the reservation.
337const fn reservation(capacity: usize, limit: usize) -> usize {
338 match capacity.checked_next_power_of_two() {
339 Some(p) if p < limit => p,
340 _ => limit,
341 }
342}
343
344impl ListBuilder {
345 /// Starts building into `vector`.
346 ///
347 /// Rows are **appended** after any elements the vector's child already
348 /// holds, so several builders — or several calls of a callback — can fill
349 /// one vector in turn. `DuckDB` relies on this: it can call an
350 /// aggregate's `finalize` many times on the same result vector with an
351 /// increasing `offset`, one row per call (`agg(x ORDER BY y)` finalizes
352 /// through `SortedAggregateFunction` that way), and a builder that started
353 /// at child offset 0 each time would overwrite the earlier rows' elements.
354 /// A fresh output vector has an empty child, so for a scalar function this
355 /// makes no difference. The element limit counts the elements already
356 /// there.
357 ///
358 /// # Safety
359 ///
360 /// `vector` must be a valid, writable `LIST` or `MAP` output vector.
361 #[must_use]
362 pub const unsafe fn new(vector: duckdb_vector) -> Self {
363 Self {
364 vector,
365 started: false,
366 written: 0,
367 reserved: 0,
368 limit: MAX_CHILD_CAPACITY_USIZE,
369 ceiling: MAX_CHILD_CAPACITY_USIZE,
370 overflowed: false,
371 child: None,
372 }
373 }
374
375 /// Lowers the number of child elements this builder will reserve, in total
376 /// across all rows. Values above [`MAX_LIST_CHILD_CAPACITY`] are clamped to
377 /// it.
378 ///
379 /// # Why an extension needs this
380 ///
381 /// [`max_child_capacity`] is `DuckDB`'s own ceiling for the child's type
382 /// (2^37 bytes, rounded to a power-of-two element count), which the
383 /// builder applies by itself — far more memory than most machines have. A request below that ceiling
384 /// that the allocator cannot satisfy makes `DuckDB` throw from
385 /// `duckdb_list_vector_reserve`, which has no `try`/`catch` (`DuckDB`
386 /// 1.5.5, `src/main/capi/data_chunk-c.cpp`), so the exception unwinds into
387 /// Rust and the process aborts. Nothing in this crate can catch it. When
388 /// row lengths come from untrusted input, set a limit that fits in memory;
389 /// a row that would exceed it is written as NULL and
390 /// [`overflowed`][Self::overflowed] reports it.
391 #[must_use]
392 pub const fn with_element_limit(mut self, limit: usize) -> Self {
393 self.limit = if limit < self.ceiling {
394 limit
395 } else {
396 self.ceiling
397 };
398 self
399 }
400
401 /// Elements in the child vector so far: those this builder wrote, plus any
402 /// the vector already held when the builder started (see
403 /// [`new`][Self::new]).
404 #[must_use]
405 #[inline]
406 pub const fn element_count(&self) -> usize {
407 self.written
408 }
409
410 /// Returns `true` if a row would have taken the child vector past the
411 /// element limit ([`max_child_capacity`], or the one set with
412 /// [`with_element_limit`][Self::with_element_limit]).
413 ///
414 /// From that row on, the builder writes nothing into the child: that row
415 /// and every later [`push_row`][Self::push_row] /
416 /// [`push_map_row`][Self::push_map_row] row is set to NULL, with an empty
417 /// list entry. Rows written before it stay valid. Check this before
418 /// [`finish`][Self::finish] if the row lengths come from untrusted input,
419 /// and report an error if a NULL is not an acceptable answer.
420 #[must_use]
421 #[inline]
422 pub const fn overflowed(&self) -> bool {
423 self.overflowed
424 }
425
426 /// Grows the child vector to hold at least `capacity` elements in total.
427 ///
428 /// Returns `false` — writing nothing — if `capacity` exceeds the element
429 /// limit, or an earlier request already did.
430 ///
431 /// # Safety
432 ///
433 /// `self.vector` must still be a valid LIST/MAP vector.
434 unsafe fn ensure_capacity(&mut self, capacity: usize) -> bool {
435 if self.overflowed {
436 return false;
437 }
438 // `self.limit <= max_child_capacity(self.vector)`, DuckDB's ceiling for
439 // this child type, since `start` ran (on a 32-bit target no `usize`
440 // can reach it). It is a power of two or the caller's lower limit, so
441 // DuckDB's rounding of `target` stays within it.
442 if capacity > self.limit {
443 self.overflowed = true;
444 return false;
445 }
446 if capacity > self.reserved {
447 // Grow geometrically: each reserve that grows reallocates and copies
448 // the whole child, so doing it once per row is quadratic.
449 let target = reservation(capacity, self.limit);
450 // SAFETY: `self.vector` is valid per this function's contract, and
451 // `target` is within DuckDB's limit.
452 unsafe { ListVector::reserve(self.vector, target) };
453 self.reserved = target;
454 // The child's buffers may have moved; a cached writer would dangle.
455 self.child = None;
456 }
457 true
458 }
459
460 /// Appends `len` elements for parent row `row_idx`.
461 ///
462 /// The closure receives a [`VectorWriter`] for the child vector — obtained
463 /// *after* the last reserve, so it is never stale, and the same writer for
464 /// every row between two reserves — and `base`, the index the row's first
465 /// element occupies. Write indices `base..base + len`.
466 ///
467 /// If the row would exceed the element limit — or an earlier row already
468 /// did — the closure is not called and the row is written as NULL; see
469 /// [`overflowed`][Self::overflowed].
470 ///
471 /// # Safety
472 ///
473 /// - `row_idx` must be within the parent vector's capacity.
474 /// - The closure must only write child indices in `base..base + len`, using
475 /// accessors matching the child's type.
476 pub unsafe fn push_row<F>(&mut self, row_idx: usize, len: usize, write: F)
477 where
478 F: FnOnce(&mut VectorWriter, usize),
479 {
480 // SAFETY: `self.vector` is valid per the constructor's contract.
481 unsafe { self.start() };
482 let base = self.written;
483 // SAFETY: `self.vector` is valid per the constructor's contract.
484 if !unsafe { self.ensure_capacity(base.saturating_add(len)) } {
485 // SAFETY: `row_idx` is in bounds per the caller's contract.
486 unsafe { self.refuse_row(row_idx) };
487 return;
488 }
489 if len > 0 {
490 let vector = self.vector;
491 // SAFETY: `ensure_capacity` returned true, so the child holds at least
492 // `base + len` elements; it drops the cached writer whenever it grows
493 // the child, so a writer still cached was obtained after the last
494 // reserve and its buffer pointers are current.
495 let writer = self
496 .child
497 .get_or_insert_with(|| unsafe { ListVector::child_writer(vector) });
498 write(writer, base);
499 }
500 // SAFETY: `row_idx` is in bounds per the caller's contract.
501 unsafe { self.set_entry(row_idx, base, len) };
502 self.written = base + len;
503 }
504
505 /// Writes the `{offset, length}` entry of parent row `row_idx`.
506 ///
507 /// The entry array is fetched on every call, not cached: when this LIST is
508 /// itself inside the child of another LIST or MAP (a `LIST(LIST(T))`, a LIST
509 /// field of a list's STRUCT elements), a reserve on that outer list
510 /// reallocates this vector's data buffer (L18), and a builder kept across
511 /// the outer list's rows would write through a dangling pointer.
512 ///
513 /// # Safety
514 ///
515 /// `row_idx` must be within the parent vector's capacity.
516 unsafe fn set_entry(&mut self, row_idx: usize, offset: usize, length: usize) {
517 // SAFETY: `self.vector` is a valid LIST vector per the constructor's
518 // contract, and its data is the array of entries.
519 let entries = unsafe { duckdb_vector_get_data(self.vector) }.cast::<duckdb_list_entry>();
520 // SAFETY: `entries` addresses the parent's entry array, and `row_idx` is
521 // in bounds per this function's contract.
522 unsafe {
523 *entries.add(row_idx) = duckdb_list_entry {
524 offset: offset as u64,
525 length: length as u64,
526 };
527 }
528 }
529
530 /// Appends `len` key/value pairs for parent row `row_idx` of a `MAP`.
531 ///
532 /// The closure receives a writer for the key child, a writer for the value
533 /// child, and the base index. Write indices `base..base + len` in both.
534 ///
535 /// Past the element limit the row is written as NULL, exactly as for
536 /// [`push_row`][Self::push_row].
537 ///
538 /// # Safety
539 ///
540 /// - `self.vector` must be a `MAP` vector.
541 /// - `row_idx` must be within the parent vector's capacity.
542 /// - The closure must only write child indices in `base..base + len`.
543 pub unsafe fn push_map_row<F>(&mut self, row_idx: usize, len: usize, write: F)
544 where
545 F: FnOnce(&mut VectorWriter, &mut VectorWriter, usize),
546 {
547 // SAFETY: `self.vector` is valid per the constructor's contract.
548 unsafe { self.start() };
549 let base = self.written;
550 // SAFETY: `self.vector` is valid per the constructor's contract.
551 if !unsafe { self.ensure_capacity(base.saturating_add(len)) } {
552 // SAFETY: `row_idx` is in bounds per the caller's contract.
553 unsafe { self.refuse_row(row_idx) };
554 return;
555 }
556 if len > 0 {
557 // SAFETY: the child STRUCT was just reserved, so both writers are
558 // fresh. MAP children are always key at field 0, value at field 1.
559 let (mut keys, mut values) = unsafe {
560 let struct_child = MapVector::struct_child(self.vector);
561 (
562 VectorWriter::from_vector(StructVector::get_child(struct_child, 0)),
563 VectorWriter::from_vector(StructVector::get_child(struct_child, 1)),
564 )
565 };
566 write(&mut keys, &mut values, base);
567 }
568 // SAFETY: `row_idx` is in bounds per the caller's contract.
569 unsafe { self.set_entry(row_idx, base, len) };
570 self.written = base + len;
571 }
572
573 /// Picks up the child's current size on first use, so that rows are
574 /// appended after elements an earlier builder or callback wrote.
575 ///
576 /// # Safety
577 ///
578 /// `self.vector` must be a valid `LIST` or `MAP` vector.
579 unsafe fn start(&mut self) {
580 if !self.started {
581 // SAFETY: forwarded from this function's own contract.
582 let existing = unsafe { ListVector::get_size(self.vector) };
583 self.written = existing;
584 self.reserved = existing;
585 // SAFETY: as above. DuckDB's ceiling depends on the child's type.
586 self.ceiling = unsafe { max_child_capacity(self.vector) };
587 self.limit = self.limit.min(self.ceiling);
588 self.started = true;
589 }
590 }
591
592 /// Writes `row_idx` as a NULL with an empty entry.
593 ///
594 /// The entry matters as much as the NULL: `DuckDB` reuses output vectors
595 /// across chunks, so a row whose entry is never written keeps the
596 /// `{offset, length}` of an earlier chunk, pointing into child data this
597 /// chunk never wrote.
598 ///
599 /// # Safety
600 ///
601 /// `row_idx` must be within the parent vector's capacity.
602 unsafe fn refuse_row(&mut self, row_idx: usize) {
603 // SAFETY: `self.vector` is valid per the constructor's contract and
604 // `row_idx` is in bounds per this function's.
605 unsafe {
606 ListVector::set_entry(self.vector, row_idx, self.written as u64, 0);
607 VectorWriter::from_vector(self.vector).set_null(row_idx);
608 }
609 }
610
611 /// Declares how many child elements are valid, completing the vector.
612 ///
613 /// Forgetting this leaves `DuckDB` reading a child size of zero, so the
614 /// column comes back as empty lists with no error.
615 ///
616 /// # Safety
617 ///
618 /// Every element promised by a [`push_row`][Self::push_row] /
619 /// [`push_map_row`][Self::push_map_row] call must actually have been
620 /// written.
621 pub unsafe fn finish(mut self) {
622 // SAFETY: `self.vector` is valid per the constructor's contract. A
623 // builder that wrote nothing keeps the child's existing size.
624 unsafe { self.start() };
625 // SAFETY: `self.vector` is valid per the constructor's contract, and
626 // `self.written` counts exactly the elements the caller wrote.
627 unsafe { ListVector::set_size(self.vector, self.written) };
628 }
629}
630
631#[cfg(test)]
632mod tests {
633 use super::{
634 capacity_for, capacity_within, element_bytes, reservation, ListBuilder,
635 MAX_CHILD_CAPACITY_USIZE, MAX_LIST_CHILD_CAPACITY,
636 };
637
638 #[test]
639 fn the_reservation_is_a_power_of_two_capped_at_the_limit_even_past_usize() {
640 assert_eq!(reservation(1, 100), 1);
641 assert_eq!(reservation(3, 100), 4);
642 assert_eq!(reservation(64, 100), 64);
643 assert_eq!(reservation(65, 100), 100);
644 assert_eq!(reservation(100, 100), 100);
645 // Past the largest power of two a `usize` holds: what a 32-bit target
646 // meets from 2^31 + 1. `next_power_of_two` overflows there (0 in a
647 // release build), which reserved nothing and let the closure write
648 // past the child.
649 let past = (usize::MAX >> 1) + 2;
650 assert_eq!(reservation(past, usize::MAX), usize::MAX);
651 }
652 use crate::types::TypeId;
653
654 #[test]
655 #[cfg(target_pointer_width = "64")]
656 fn capacity_is_duckdbs_byte_ceiling_over_the_element_size() {
657 assert_eq!(capacity_for(Some(8)), 1 << 34);
658 assert_eq!(capacity_for(Some(16)), 1 << 33);
659 // `DuckDB` checks the reservation rounded up to a power of two, so the
660 // limit is a power of two too: 2^25, not 2^37 / 4000 = 34,359,738.
661 assert_eq!(capacity_for(Some(4000)), 1 << 25);
662 assert_eq!(capacity_for(Some(1)), MAX_CHILD_CAPACITY_USIZE);
663 assert_eq!(capacity_for(Some(0)), MAX_CHILD_CAPACITY_USIZE);
664 assert_eq!(
665 capacity_for(Some(3)),
666 1 << 35,
667 "2^37 / 3 rounded down to 2^35"
668 );
669 assert_eq!(capacity_for(Some(1 << 37)), 1);
670 assert_eq!(capacity_for(Some((1 << 37) + 1)), 0);
671 assert_eq!(capacity_for(None), 0);
672 assert_eq!(capacity_for(Some(u64::MAX)), 0);
673 }
674
675 /// `DuckDB` computes a buffer's size as a 64-bit `idx_t` and passes it to
676 /// `malloc`, which narrows it to a 32-bit `size_t` on wasm32: a limit
677 /// whose rounded-up reservation needs more bytes than a `usize` holds gets
678 /// a wrapped, undersized buffer. Run under Miri with `--target
679 /// i686-unknown-linux-gnu` for the 32-bit case.
680 #[test]
681 fn a_32_bit_allocation_bounds_the_capacity_in_bytes() {
682 let wasm32 = u64::from(u32::MAX);
683 assert_eq!(capacity_within(Some(16), wasm32), 1 << 27);
684 assert_eq!(capacity_within(Some(8), wasm32), 1 << 28);
685 assert_eq!(capacity_within(Some(4000), wasm32), 1 << 20);
686 assert_eq!(capacity_within(Some(1), wasm32), 1 << 31);
687 for bytes in [1_u64, 2, 3, 4, 8, 16, 4000] {
688 let reserved = capacity_within(Some(bytes), wasm32).saturating_mul(bytes);
689 assert!(
690 reserved <= wasm32,
691 "{bytes}-byte elements reserve {reserved}"
692 );
693 }
694 // On a 64-bit target `DuckDB`'s own 2^37-byte ceiling is the tighter.
695 assert_eq!(capacity_within(Some(16), u64::MAX), 1 << 33);
696 assert_eq!(capacity_within(Some(1), u64::MAX), 1 << 37);
697 }
698
699 #[test]
700 fn no_limit_asks_for_more_bytes_than_one_allocation_holds() {
701 for bytes in [1_u64, 2, 4, 8, 16, 3, 4000] {
702 let elements = capacity_for(Some(bytes)) as u64;
703 let reserved = elements.next_power_of_two().saturating_mul(bytes);
704 assert!(
705 usize::try_from(reserved).is_ok(),
706 "{bytes}-byte elements: {elements} reserve {reserved} bytes"
707 );
708 }
709 }
710
711 /// `GetTypeIdSize` of each type's physical type.
712 #[test]
713 fn element_sizes_are_duckdbs_physical_sizes() {
714 for (id, bytes) in [
715 (TypeId::Boolean, 1),
716 (TypeId::TinyInt, 1),
717 (TypeId::UTinyInt, 1),
718 (TypeId::SmallInt, 2),
719 (TypeId::USmallInt, 2),
720 (TypeId::Integer, 4),
721 (TypeId::UInteger, 4),
722 (TypeId::Float, 4),
723 (TypeId::Date, 4),
724 (TypeId::Enum, 4),
725 (TypeId::BigInt, 8),
726 (TypeId::UBigInt, 8),
727 (TypeId::Double, 8),
728 (TypeId::Timestamp, 8),
729 (TypeId::TimestampTz, 8),
730 (TypeId::TimestampS, 8),
731 (TypeId::TimestampMs, 8),
732 (TypeId::TimestampNs, 8),
733 (TypeId::TimestampTzNs, 8),
734 (TypeId::Time, 8),
735 (TypeId::TimeTz, 8),
736 (TypeId::TimeNs, 8),
737 (TypeId::HugeInt, 16),
738 (TypeId::UHugeInt, 16),
739 (TypeId::Uuid, 16),
740 (TypeId::Interval, 16),
741 (TypeId::Decimal, 16),
742 (TypeId::Varchar, 16),
743 (TypeId::Blob, 16),
744 (TypeId::List, 16),
745 ] {
746 assert_eq!(element_bytes(Some(id)), bytes, "{id:?}");
747 }
748 assert_eq!(element_bytes(None), 16, "an unknown type counts the widest");
749 }
750
751 #[test]
752 fn the_element_limit_defaults_to_and_is_clamped_by_duckdbs_ceiling() {
753 // SAFETY: `new` and `with_element_limit` only store the pointer; no
754 // DuckDB call is made, so a null vector is never dereferenced.
755 let fresh = unsafe { ListBuilder::new(std::ptr::null_mut()) };
756 assert_eq!(fresh.limit, MAX_CHILD_CAPACITY_USIZE);
757 assert!(!fresh.overflowed());
758 let lowered = fresh.with_element_limit(100);
759 assert_eq!(lowered.limit, 100);
760 // SAFETY: as above.
761 let raised =
762 unsafe { ListBuilder::new(std::ptr::null_mut()) }.with_element_limit(usize::MAX);
763 assert_eq!(raised.limit, MAX_CHILD_CAPACITY_USIZE);
764 }
765
766 /// A request past the element limit is refused before `DuckDB` is asked
767 /// for anything, and the refusal sticks: `overflowed` reports it and every
768 /// later request — however small — is refused too, so no row after the
769 /// first overflowing one is written.
770 #[test]
771 fn a_request_past_the_element_limit_is_refused_and_reported() {
772 // SAFETY: `ensure_capacity` makes no DuckDB call for a request of 0
773 // elements or one past the limit, so the null vector is never used.
774 let mut builder = unsafe { ListBuilder::new(std::ptr::null_mut()) }.with_element_limit(10);
775 // SAFETY: as above.
776 assert!(unsafe { builder.ensure_capacity(0) });
777 assert!(!builder.overflowed());
778 // SAFETY: as above.
779 assert!(!unsafe { builder.ensure_capacity(11) });
780 assert!(builder.overflowed());
781 // SAFETY: as above; the builder has overflowed, so nothing is reserved.
782 assert!(!unsafe { builder.ensure_capacity(0) });
783 assert!(builder.overflowed());
784 assert_eq!(builder.element_count(), 0);
785 }
786
787 #[test]
788 fn max_capacity_matches_duckdbs_constant() {
789 // duckdb::DConstants::MAX_VECTOR_SIZE = 1ULL << 37ULL. Above this,
790 // ListVector::Reserve throws a C++ exception that the C API does not
791 // catch, so it must never be reached from Rust.
792 assert_eq!(MAX_LIST_CHILD_CAPACITY, 137_438_953_472_u64);
793 // The ceiling is an `idx_t`, so it must not be pointer-sized: typing it
794 // `usize` made `1 << 37` a const-eval overflow on 32-bit targets and
795 // broke the wasm32 build outright.
796 assert_eq!(
797 MAX_CHILD_CAPACITY_USIZE,
798 usize::try_from(MAX_LIST_CHILD_CAPACITY).unwrap_or(usize::MAX)
799 );
800 }
801}