Skip to main content

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}