This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-11710-7168fa813aea5a0d9b4ba4115ed30c726376609c in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
commit dd6454d599d904616c5b6da558230a172fefac61 Author: Andrew Lamb <[email protected]> AuthorDate: Fri Oct 30 20:19:43 2026 +0000 docs: document RunArray logical offset/len and child array slicing (#11710) # Which issue does this PR close? - Related to #11587 and #11668 # Rationale for this change While reviewing #11668 I was unclear about the relationship between a `RunArray`'s logical `offset` / `len` and the contents of its `run_ends` child as it was not documented anywhere on `RunArray` itself # What changes are included in this PR? Documentation only, on `pub struct RunArray`: # Are these changes tested? Yes, by CI # Are there any significant user-facing changes? Only docs --------- Co-authored-by: Claude Fable 5.1 <[email protected]> Co-authored-by: RIchard Baah <[email protected]> --- arrow-array/src/array/run_array.rs | 86 ++++++++++++++++++++++++++++++++++++-- arrow-buffer/src/buffer/run.rs | 14 ++++++- arrow-data/src/data.rs | 9 +++- 3 files changed, 103 insertions(+), 6 deletions(-) diff --git a/arrow-array/src/array/run_array.rs b/arrow-array/src/array/run_array.rs index 6c64013865..e5bebc2309 100644 --- a/arrow-array/src/array/run_array.rs +++ b/arrow-array/src/array/run_array.rs @@ -64,7 +64,7 @@ macro_rules! ree_map { /// ┌─────────────────┐ ┌─────────┐ ┌─────────────────┐ /// │ │ A │ │ 2 │ │ │ A │ /// ├─────────────────┤ ├─────────┤ ├─────────────────┤ -/// │ │ D │ │ 3 │ │ │ A │ run length of 'A' = runs_ends[0] - 0 = 2 +/// │ │ D │ │ 3 │ │ │ A │ run length of 'A' = run_ends[0] - 0 = 2 /// ├─────────────────┤ ├─────────┤ ├─────────────────┤ /// │ │ B │ │ 6 │ │ │ D │ run length of 'D' = run_ends[1] - run_ends[0] = 1 /// └─────────────────┘ └─────────┘ ├─────────────────┤ @@ -73,12 +73,66 @@ macro_rules! ree_map { /// └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─┘ │ B │ /// ├─────────────────┤ /// RunArray │ B │ run length of 'B' = run_ends[2] - run_ends[1] = 3 -/// length = 3 └─────────────────┘ +/// offset = 0, len = 6 └─────────────────┘ /// /// Logical array /// Contents /// ``` /// +/// # `offset` and `len` +/// +/// The [`Array::len`] and [`Array::offset`] for a `RunArray` refer to the +/// **logical** length, not the `run_ends` and `values` child arrays. In the +/// example above the `RunArray` has length `6` even though `run_ends` and +/// `values` each contain `3` elements. +/// +/// The values in `run_ends` represent indexes of the *unsliced* logical array. +/// This allows zero-copy [`RunArray::slice`]: `run_ends` and `values` are left +/// untouched and only `offset` and `len` are adjusted. +/// +/// A [`RunArray`] must satisfy the following invariants: +/// +/// * every run end is greater than zero and `run_ends` is strictly increasing +/// * `run_ends` has no null values +/// * `run_ends` and `values` have the same length +/// * if `len > 0`, the last run end is greater than or equal to `offset + len`. +/// +/// Note an empty `RunArray` (`len == 0`) is valid even when `run_ends` is empty +/// or its last run end is less than `offset`. Note this is more permissive than +/// the Arrow C++ implementation. +/// +/// The example below shows the same array as above after calling `slice(1, 3)` +/// +/// ```text +/// ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─┐ +/// ┌─────────────────┐ ┌─────────┐ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ┐ +/// │ │ A │ │ 2 │ │ A logical index 0: before offset, not visible +/// ├─────────────────┤ ├─────────┤ ┌─────────────────┐ ◄── offset = 1 +/// │ │ D │ │ 3 │ │ │ A │ logical index 1 < run_ends[0] = 2, so 'A' +/// ├─────────────────┤ ├─────────┤ ├─────────────────┤ +/// │ │ B │ │ 6 │ │ │ D │ logical index 2 < run_ends[1] = 3, so 'D' +/// └─────────────────┘ └─────────┘ ├─────────────────┤ +/// │ values run_ends │ │ B │ logical index 3 < run_ends[2] = 6, so 'B' +/// └─────────────────┘ ◄── offset + len = 4 +/// └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─┘ B logical index 4: after offset + len, not visible +/// ├ ─ ─ ─ ─ ─ ─ ─ ─ ┤ +/// RunArray B logical index 5: after offset + len, not visible +/// offset = 1, len = 3 └ ─ ─ ─ ─ ─ ─ ─ ─ ┘ +/// +/// Logical array +/// Contents +/// ``` +/// +/// # Sliced child arrays +/// +/// [`RunArray::slice`] doesn't slice child arrays, but a `RunArray` may be +/// built (for example from [`ArrayData`]) from child arrays that are already +/// sliced. In that case each child's own `offset` and `len` are respected, +/// independently of the logical `offset` and `len` of the `RunArray`: +/// +/// * Run `i` ends at `run_ends.value(i)`, the `i`th (logical) element +/// * The value of run `i` is `values.value(i)`, the `i`th (logical) element +/// /// [run-end encoded values]: https://arrow.apache.org/docs/format/Columnar.html#run-end-encoded-layout /// [run-length encoding (RLE)]: https://en.wikipedia.org/wiki/Run-length_encoding pub struct RunArray<R: RunEndIndexType> { @@ -110,11 +164,18 @@ impl<R: RunEndIndexType> RunArray<R> { /// Attempts to create a [`RunArray`] using the given `run_ends` and `values`. /// + /// The resulting array is unsliced: its logical offset is `0` and its logical + /// length is the last value of `run_ends` (or `0` if `run_ends` is empty). + /// /// # Errors /// + /// Returns an error if the [`RunArray` invariants] are not satisfied: + /// /// - If `run_ends` and `values` have different lengths /// - If `run_ends` has any null values /// - If `run_ends` doesn't consist of strictly increasing positive integers + /// + /// [`RunArray` invariants]: RunArray#offset-and-len pub fn try_new(run_ends: &PrimitiveArray<R>, values: &dyn Array) -> Result<Self, ArrowError> { // 1. run_ends and values must have the same (physical) length. if run_ends.len() != values.len() { @@ -182,7 +243,10 @@ impl<R: RunEndIndexType> RunArray<R> { /// /// # Safety /// - /// Safe if [`Self::try_new`] would not error + /// Safe if [`Self::try_new`] would not error, that is if `run_ends` and + /// `values` satisfy the [`RunArray` invariants] + /// + /// [`RunArray` invariants]: RunArray#offset-and-len pub unsafe fn new_unchecked( data_type: DataType, run_ends: RunEndBuffer<R::Native>, @@ -405,6 +469,22 @@ impl<R: RunEndIndexType> RunArray<R> { } } +/// Converts an [`ArrayData`] into a [`RunArray`]. +/// +/// The `len` and `offset` of `data` become the logical length and offset of the +/// [`RunArray`]; see the [`RunArray`] documentation for how they relate to the +/// run ends. +/// +/// The `offset` and `len` of the `run_ends` child are respected: only the `len` +/// elements starting at `offset` are used as run ends. See [Sliced child +/// arrays]. +/// +/// [Sliced child arrays]: RunArray#sliced-child-arrays +/// +/// # Panics +/// +/// Panics if `data` is not a [`DataType::RunEndEncoded`] array with a `run_ends` +/// child of type `R`, or does not have exactly two children. impl<R: RunEndIndexType> From<ArrayData> for RunArray<R> { // The method assumes the caller already validated the data using `ArrayData::validate_data()` fn from(data: ArrayData) -> Self { diff --git a/arrow-buffer/src/buffer/run.rs b/arrow-buffer/src/buffer/run.rs index 6c9a4cb52e..05d32da75f 100644 --- a/arrow-buffer/src/buffer/run.rs +++ b/arrow-buffer/src/buffer/run.rs @@ -109,8 +109,13 @@ where /// /// # Panics /// + /// Panics if the [`RunArray` invariants] are not satisfied: + /// /// - `run_ends` does not contain strictly increasing values greater than zero - /// - The last value of `run_ends` is less than `logical_offset + logical_length` + /// - `logical_length` is not 0 and the last value of `run_ends` is less than + /// `logical_offset + logical_length` (an empty slice is always accepted) + /// + /// [`RunArray` invariants]: https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html#offset-and-len pub fn new(run_ends: ScalarBuffer<E>, logical_offset: usize, logical_length: usize) -> Self { assert!( run_ends.windows(2).all(|w| w[0] < w[1]), @@ -142,8 +147,13 @@ where /// /// # Safety /// + /// `run_ends` must satisfy the [`RunArray` invariants]: + /// /// - `run_ends` must contain strictly increasing values greater than zero - /// - The last value of `run_ends` must be greater than or equal to `logical_offset + logical_len` + /// - If `logical_length` is not 0, the last value of `run_ends` must be + /// greater than or equal to `logical_offset + logical_length` + /// + /// [`RunArray` invariants]: https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html#offset-and-len pub unsafe fn new_unchecked( run_ends: ScalarBuffer<E>, logical_offset: usize, diff --git a/arrow-data/src/data.rs b/arrow-data/src/data.rs index 3ccaa9101f..5eacdb18ef 100644 --- a/arrow-data/src/data.rs +++ b/arrow-data/src/data.rs @@ -1338,6 +1338,9 @@ impl ArrayData { } } DataType::RunEndEncoded(run_ends_field, values_field) => { + // See the `RunArray` invariants for the rules enforced here and + // in `check_run_ends`: + // https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html#offset-and-len self.validate_num_child_data(2)?; let run_ends_data = self.get_valid_child_data(0, run_ends_field.data_type())?; let values_data = self.get_valid_child_data(1, values_field.data_type())?; @@ -1853,7 +1856,11 @@ impl ArrayData { }) } - /// Validates that each value in run_ends array is positive and strictly increasing. + /// Validates that each value in run_ends array is positive and strictly + /// increasing, and that the last value covers the parent's `offset + len` + /// (when the parent is non-empty), as required by the [`RunArray` invariants]. + /// + /// [`RunArray` invariants]: https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html#offset-and-len fn check_run_ends<T>( &self, parent_len: usize,
