Polars 底层 Arrow 数组模块设计解析：Array 与 MutableArray 的不变量、O(1) 切片与可互操作设计

本文以 polars 仓库中 polars-arrow 的 array 模块设计文档 为主体，系统讲解该模块的术语约定、不可变数组与可变数组的设计规范、try_new 校验语义、slot offset 与 O(1) 切片机制，并结合 trait 定义、PrimitiveArray 实现 等源码逐条印证设计文档中的每条 MUST/MAY 约束，帮助读者理解 Polars 底层列式数据的存储契约与性能保证的来源。

模块定位与术语约定

polars-arrow 是 polars 的底层列式存储层，array 模块提供"按照 Arrow 规范在内存中布局的、带可空值的定长容器"（fixed-length containers with optional values, laid in memory according to the Arrow specification），即 模块文档注释 所描述的核心职责。设计文档首先定义了三个关键术语，这是阅读整个模块源码的前提：

• "array"：指任何实现了 trait [Array] 的结构体（struct），即可不变量下的不可变数组；
• "mutable array"：指任何实现了 trait [MutableArray] 的结构体，即可原地（in-place）修改的数组；
• code 形式的词：指当前实现中真实存在的术语（trait、方法、类型名），而非泛指概念。

这一术语划分直接对应源码中两个核心 trait 对象：Array 是"不可变 Arrow 数组的 trait 对象，可通过 dtype 无失败地向下转型为具体类型"（见 trait Array 定义），MutableArray 则是"元素值可被修改、不可克隆但可原地操作"的 trait（见 trait MutableArray 定义）。

不可变数组（Array）的设计规范

设计文档对每一种物理表示不同的 Arrow 数组提出了一系列强制性（MUST）与允许性（MAY）规则。下面逐条展开，并给出源码级证据。

一物一型：每种物理表示必须有独立的 struct

"Every arrow array with a different physical representation MUST be implemented as a struct or generic struct." "An array MAY have its own module. E.g. primitive/mod.rs"

即不同的物理布局（primitive、boolean、utf8、list、struct……）不能共用一个泛型"万能数组"，而必须各有专门的结构体或泛型结构体；复杂数组类型建议拥有自己的模块目录。从 array 模块的目录组织 看，这一规范被严格遵循：binary/、boolean/、primitive/、utf8/、list/、struct_/、dictionary/、union/ 等各自成目录，而 PrimitiveArray 这类泛型结构体通过 Int32Array = PrimitiveArray<i32>、Float64Array = PrimitiveArray<f64> 等类型别名覆盖全部原生数值类型（见 类型别名定义）。

空值位图必须是 Option<Bitmap>

"An array with a null bitmap MUST implement it as Option<Bitmap>"

空值信息统一建模为"可选的位图"：None 表示整列有效，Some(bitmap) 表示存在空位。这一点在 trait 层就固化下来——Array::validity 的签名就是 fn validity(&self) -> Option<&Bitmap>，且文档明确"当 validity 为 None 时所有 slot 都有效"。具体数组同样如此，PrimitiveArray 的三个字段是：

#[derive(Clone)]
pub struct PrimitiveArray<T: NativeType> {
    dtype: ArrowDataType,
    values: Buffer<T>,
    validity: Option<Bitmap>,
}

null_count 也因此可以做到 O(1)：位图的未置位数量是预计算的（见 null_count 实现）。此外模块还规定每个数组 MUST 是 #[derive(Clone)]——这保证了 mod.rs 顶部注释 所述的"clone 和 slice 都是 O(1)"性能契约。

Array trait 只能由本模块的 struct 实现，子数组必须是 Box<dyn Array>

"The trait Array MUST only be implemented by structs in this module." "Every child array on the struct MUST be Box<dyn Array>."

第一条确保 trait 对象的封闭性：dyn Array 向下转型时只需覆盖有限的一组具体类型，clone 函数 中对 PhysicalType 的穷举 match 正是依赖这一封闭集合。第二条让嵌套类型（list、struct、map 等）通过 trait 对象持有子数组，例如 ListArray 的 values: Box<dyn Array> 字段，使得"数组的数组"这类递归结构（如 [[1,2], None, [], [None]]）可以直接表达，而无需为每种嵌套深度专门建模。

try_new：O(N) 校验的规范入口，new_unchecked 是快速路径

"An array MUST implement try_new(...) -> Self. This method MUST error iff the data does not follow the arrow specification, including any sentinel types such as utf8." "An array MAY implement unsafe try_new_unchecked that skips validation steps that are O(N)."

这是整个模块"规范即类型"思想的集中体现：构造函数返回 Result，当且仅当输入违反 Arrow 规范时出错。以两种代表性数组为例：

• PrimitiveArray::try_new 是 O(1) 的，校验项只有两条：validity 长度与 values 长度一致、dtype 的物理类型与 T 匹配；对应的 new_unchecked（L101-L115）跳过校验，但保留了 debug_assertions 下的断言检查。
• Utf8Array::try_new 则是 O(N) 的，因为它必须校验"相邻两个 offset 之间的字节是合法 UTF-8"（通过 try_check_utf8），这正是文档所说"including any sentinel types such as utf8"的含义——utf8 不是自由字节序列，是带哨兵约束的类型。

而 ListArray::try_new 展示了复合类型的校验层次：offset 末值不得超过 values 长度、validity 长度必须等于 offsets.len_proxy()、子数组 dtype 必须与父类型声明的内层 field 一致。

new_empty / new_null / value(i) 的统一构造与访问约定

"An array MUST implement either new_empty() or new_empty(DataType) …" "An array MUST implement either new_null(length) or new_null(DataType, length) …" "An array MAY implement value(i) that returns the value at slot i ignoring the validity bitmap."

前两条保证了"零长度数组"和"全 null 数组"在任意 dtype 下都可以廉价构造——模块层面通过 new_empty_array 与 new_null_array 两个工厂函数按 PhysicalType 分派到各具体实现。例如 PrimitiveArray::new_empty / new_null 中，new_null 用零填充的 values 加全零位图表达"全部为空"。

第三条是重要的 API 纪律：value(i) 只取物理值、忽略 validity 位图（空 slot 上的值是无意义的占位，读它不保证正确），需要空值语义时应走 is_null/get 一类的 API。PrimitiveArray::value 的文档注释明确写着"The value of a null slot is undetermined (it can be anything)"。

从原生 Rust 数据构造数组的命名规范

文档规定了一组固定的构造器命名，让调用方仅凭方法名就能判断输入形态与校验强度：

方法名	输入形态	示例（以 BooleanArray 为例）
from	可选值切片 AsRef<[Option<T>]>	从 [Some(true), None, ...] 构造
from_slice	非空值切片 AsRef<[T]>	从 [true, false, ...] 构造
from_trusted_len_iter	已知长度的可选值迭代器	从 TrustedLen<Item=Option<T>> 构造
from_trusted_len_values_iter	已知长度的非空值迭代器	从 TrustedLen<Item=T> 构造
try_from_trusted_len_iter	已知长度的可失败迭代器	元素构造本身可能返回错误

以 PrimitiveArray 为例，from_slice（O(N) 内存拷贝、无 validity）、from_trusted_len_values_iter、from_trusted_len_iter 全部就位，且底层统一委托给对应的 MutablePrimitiveArray 构造后转成不可变形式。这套命名在 static_array_collect 中以 ArrayFromIter / ArrayFromIterDtype trait 进一步抽象，成为各具体数组"从迭代器收集"的统一入口。

Slot offsets：为什么切片必须是 O(1)，又怎么实现

设计文档中"Slot offsets"一节是全模块最重要的性能契约：

"An array MUST have a offset: usize measuring the number of slots that the array is currently offsetted by if the specification requires." "An array MUST implement fn slice(&self, offset: usize, length: usize) -> Self … This function MUST increase the array's offset if it exists." "Conversely, offset MUST only be changed by slice." "The rational of the above is that it enable us to be fully interoperable with the offset logic supported by the C data interface, while at the same time easily perform array slices within Rust's type safety mechanism."

也就是说，切片（slice）绝不能复制数据，只能推进一个偏移量并缩短长度；并且偏移量的唯一合法修改入口就是 slice。这样既与 Arrow C Data Interface 的 offset 语义完全互操作（跨语言零拷贝传递时对方看到的 offset 是正确的），又能在 Rust 的类型安全体系内完成切片。

从当前源码看，这一契约落地为 trait 层的 Array::slice / slice_unchecked / sliced，文档注释明确标注"本操作对 len 是 O(1) 的"，sliced 的实现注释进一步说明它只是"两次引用计数增加 + 把 struct 移到堆上"。以 PrimitiveArray::slice_unchecked 为例，它对 values 和 validity 各做一次原位窗口裁剪（slice_in_place_unchecked），并顺手丢弃"裁剪后全为有效"的位图以省内存；变长类型 Utf8Array::slice 则额外把 offset 缓冲裁剪为 length + 1 个元素（每行一个 offset，首行起点保留）。

变长数组的 offset 序列本身由 Offsets / OffsetsBuffer 这对类型封装，它们的文档声明了两条不变量：每个元素非负、单调不减。TryFrom<Vec<O>> 走 try_check_offsets 校验（该函数被刻意写成可自动向量化），unsafe new_unchecked 则在 debug 模式下保留单调性断言。OffsetsBuffer::slice（L500-L508）同样只做 Buffer 的原位窗口调整，维持了 O(1) 语义。

可变数组（MutableArray）：原地操作与 O(1) 冻结

设计文档的"Mutable Arrays"一节规定了构建期数据结构的行为边界：

"An array MAY have a mutable counterpart. E.g. MutablePrimitiveArray<T> …" "Arrays with mutable counterparts MUST have its own module, and have the mutable counterpart declared in {module}/mutable.rs." "A mutable array MUST be #[derive(Debug)]" "A mutable array with a null bitmap MUST implement it as Option<MutableBitmap>" "Converting a MutableArray to its immutable counterpart MUST be O(1). Specifically: it must not allocate; it must not cause O(N) data transformations. This is achieved by converting mutable versions to immutable counterparts (e.g. MutableBitmap -> Bitmap)."

对照 primitive/mutable.rs 的文件布局：MutablePrimitiveArray 确实声明在 primitive/mutable.rs，derive 了 Debug（也 derive 了 Clone），字段为 values: Vec<T> + validity: Option<MutableBitmap>，与规范逐条对应。

最关键的约束是"冻结"（mutable → immutable）必须 O(1)、零分配、零 O(N) 数据变换。看 MutableArray for MutablePrimitiveArray 的实现：as_box 用 std::mem::take 把 Vec<T> 和 MutableBitmap 原地"搬走"，Vec -> Buffer（本质是 Arc<Vec>）与 MutableBitmap -> Bitmap 都只是换包装、不拷贝数据。模块级文档注释 也直接声明"Converting a MutablePrimitiveArray into a PrimitiveArray is O(1)"。设计文档给出的动机是：mutable 数组的存在就是为了在 Arrow 规范下执行原地操作（in-place operations）——累加、过滤、聚合等数值计算不需要重新分配，算完一次性冻结成不可变数组进入下游流水线。

反向路径同样值得注意：PrimitiveArray::into_mut 以 copy-on-write 语义尝试把不可变数组"解冻"回 mutable 形式——只有当底层 Buffer 和 Bitmap 都是唯一引用时才能零拷贝复用内存（通过 Arc::get_mut），否则返回 Either::Left 保持不可变。这让"构建期原地修改"与"运行期共享引用"两种使用模式在同一个类型体系内共存。

设计规范的工程价值与源码验证清单

回过头看，这份设计文档实际上是 polars-arrow 数组层的"宪法"：它把 Arrow 内存规范翻译成一组可检查的 Rust 类型契约，并直接决定了 polars 的几项核心性能特性——

1. 克隆/切片 O(1)：#[derive(Clone)] + Buffer（Arc 语义）使任意数组的 clone 只是引用计数加一，slice 只移动窗口；mod.rs 顶部注释 与 clone 实现 的注释互相印证；
2. 校验前置到构造期：try_new 把 O(N) 的规范校验（utf8 合法性、offset 单调性、validity 长度匹配等）限制在数据入口，热路径上使用已校验的不可变数组；
3. 构建与执行分离：MutableArray 承担 O(1) 冻结前的全部原地计算，不可变 Array 只负责高效读取与共享，二者通过 as_box/into_mut 在唯一引用约束下低成本互换。

如需继续深入，可按以下路径对照阅读：Array 与 MutableArray trait 全貌、primitive 数组族、utf8 数组族、list 数组族、offset 封装与校验，以及设计文档本身 crates/polars-arrow/src/array/README.md。需要说明的是，文档中的规则是该模块的设计约定，个别表述（如数组持有显式 offset: usize 字段）描述的是设计原则；从当前源码结构看，O(1) 切片是通过底层 Buffer 的原位窗口裁剪直接实现的，效果与文档要求的"偏移只由 slice 修改、且可被 C data interface 的 offset 逻辑解释"一致。