# iceberg.nested

> A module of iceberg's API.

Nested columns — struct, list and map — as Arrow trees.

parquet.mojo hands a nested column back as an `ArrayData` whose children are
*indices into an `ArrayArena`*, because Mojo cannot put a `List` of a struct
inside that same struct. A scan therefore has to carry a whole arena per
column, not one array, and every kernel `iceberg.kernels` provides for a flat
column needs a counterpart that walks children and offsets.

That is what this module is. A column is a `ColumnTree`: an arena plus the
index of its root. Each kernel reads one `(arena, node)` pair and writes its
result into another arena, appending children before their parent — which
keeps a subtree contiguous and ending at its root, the invariant
`read.mojo` relies on when it moves decoded columns out of a batch.

| kernel | flat counterpart |
|---|---|
| `cast_column` / `cast_tree` | `kernels.cast_array` |
| `filter_tree` | `kernels.filter_array` |
| `concat_tree` | `kernels.concat_into` |
| `null_tree` / `empty_tree` | `kernels.constant_array` / `empty_array` |
| `flatten_leaf` | — (a struct leaf, seen as a flat column) |
| `cell_json` | `Datum.to_json` |

**Buffer layouts** are Arrow's, exactly as parquet.mojo writes them: a struct
is a validity bitmap and N children of the struct's own length; a list is a
validity bitmap, `length + 1` 32-bit offsets and one child; a map is a list
whose child is a non-nullable two-field struct (`key`, `value`).

## Structs

### `ColumnType`

```mojo
struct ColumnType
```

One column's Iceberg type: an arena and the index of its root node.

Implements: `Copyable`, `Movable`

Fields:

- `store: TypeStore`
- `type: Int`

#### `none`

```mojo
def none() -> Self
```

#### `is_nested`

```mojo
def is_nested(self) -> Bool
```

### `ColumnTree`

```mojo
struct ColumnTree
```

One column's Arrow array, with the arena its children live in.

Implements: `Copyable`, `Defaultable`, `Movable`

Fields:

- `arena: ArrayArena`
- `root: Int`

#### `__init__`

```mojo
def __init__(out self)
```

```mojo
def __init__(out self, var a: ArrayData)
```

```mojo
def __init__(out self, var arena: ArrayArena, root: Int)
```

#### `node`

```mojo
def node(ref self) -> ref[self.arena.nodes["element"]] ArrayData
```

#### `length`

```mojo
def length(self) -> Int
```

#### `is_flat`

```mojo
def is_flat(self) -> Bool
```

#### `take_arena`

```mojo
def take_arena(deinit self) -> ArrayArena
```

The arena, moved out — read `root` before calling this.

## Functions

### `is_nested_arrow`

```mojo
def is_nested_arrow(t: ArrowType) -> Bool
```

### `subtree_copy`

```mojo
def subtree_copy(src: ArrayArena, node: Int, mut dst: ArrayArena) -> Int
```

Deep-copy `node` and everything under it into another arena.

### `subtree_lowest`

```mojo
def subtree_lowest(arena: ArrayArena, node: Int) -> Int
```

The smallest arena index in `node`'s subtree.

### `take_subtree`

```mojo
def take_subtree(mut src: ArrayArena, node: Int) -> ColumnTree
```

Move `node`'s subtree out of `src`, or copy it when it is not on top.

parquet.mojo appends every child before its parent, so a root is the last
node of its own subtree and the subtree occupies one contiguous range. A
column can therefore be lifted out of a decoded batch without copying a
single buffer, which is what keeps a flat scan free of per-batch copies.

### `move_tree_into`

```mojo
def move_tree_into(mut src: ArrayArena, root: Int, mut dst: ArrayArena) -> Int
```

Move every node of `src` into `dst`; returns the root's new index.

`src` must hold exactly one column's tree, which is what a `ScanColumn`
owns — nothing is copied, so handing a finished result to Arrow costs
nothing but the renumbering.

### `arrow_type_of`

```mojo
def arrow_type_of(store: TypeStore, i: Int) -> ArrowType
```

### `empty_tree`

```mojo
def empty_tree(mut dst: ArrayArena, store: TypeStore, ti: Int, name: String, field_id: Int, nullable: Bool) -> Int
```

A zero-row array of the Iceberg type at `ti`.

### `null_tree`

```mojo
def null_tree(mut dst: ArrayArena, store: TypeStore, ti: Int, name: String, field_id: Int, nullable: Bool, n: Int) -> Int
```

`n` null values of the Iceberg type at `ti`.

A null container still has to be shaped like one: a null struct carries
`n` (null) children so its columns line up, a null list carries `n + 1`
equal offsets over an empty element array.

### `default_tree`

```mojo
def default_tree(mut dst: ArrayArena, store: TypeStore, f: NestedField, n: Int) -> Int
```

A column a data file does not have: its `initial-default`, else null.

The spec's column-projection rules end at "return the default value if it
has a defined `initial-default`, otherwise null". A nested field with a
nested default is the one shape not built here — it falls through to
null, which is what a reader that does not understand the default must
do anyway.

### `cast_column`

```mojo
def cast_column(var src: ColumnTree, store: TypeStore, ti: Int, name: String, field_id: Int, nullable: Bool) -> ColumnTree
```

The file's column, produced at the table's current Iceberg type.

A flat column is *moved* through `kernels.cast_array`, which retags rather
than copies whenever the file's physical type already matches. A nested
one is rebuilt child by child, matching the file's children to the table's
fields **by field id** — which is what makes a field added, renamed,
reordered or promoted inside a struct come out right.

### `cast_tree`

```mojo
def cast_tree(src: ArrayArena, node: Int, store: TypeStore, ti: Int, name: String, field_id: Int, nullable: Bool, mut dst: ArrayArena) -> Int
```

### `filter_tree`

```mojo
def filter_tree(src: ArrayArena, node: Int, keep: List[Bool], n_keep: Int, mut dst: ArrayArena) -> Int
```

The rows of a nested column for which `keep` is true, in order.

### `concat_tree`

```mojo
def concat_tree(mut dst: ArrayArena, dnode: Int, src: ArrayArena, snode: Int)
```

Append every row of `src`'s subtree to `dst`'s; the shapes must match.

### `flatten_leaf`

```mojo
def flatten_leaf(arena: ArrayArena, node: Int, path: List[Int]) -> ArrayData
```

The leaf `path` names inside a struct, as a top-level array.

A struct's children are dense — one slot per row, whatever the struct's
own validity says — so the leaf's buffers already line up with the rows.
Only the validity has to be combined: a leaf under a null struct is null,
which is exactly what a predicate on `a.b` must see.

### `find_struct_path`

```mojo
def find_struct_path(store: TypeStore, ti: Int, id: Int, mut out: List[Int]) -> Bool
```

Child positions from type `ti` down to field `id`, through structs.

The path is relative to the *projected* type, not the table schema: a
scan that reads only some of a struct's fields renumbers the rest, and
the array it built follows the projection.

### `cell_json`

```mojo
def cell_json(arena: ArrayArena, node: Int, store: TypeStore, ti: Int, row: Int) -> String
```

One value of a nested column, in the spec's JSON shape.

Appendix D's single-value serialization, with one deliberate change: a
struct is keyed by **field name** rather than field id, because these are
rows a caller reads, not a default stored in metadata, and the row object
around them is keyed by name too. Lists are JSON arrays and a map is
`{"keys": [...], "values": [...]}`, both exactly as the spec says.

### `cell_datum`

```mojo
def cell_datum(arena: ArrayArena, node: Int, store: TypeStore, ti: Int, row: Int) -> Datum
```

One cell as a `Datum`: the value itself when the column is primitive, and the JSON text of `cell_json` when it is nested — `Datum` is a *tagged scalar*, so a struct, a list or a map arrives as its canonical JSON.

## Aliases

### `ELEMENT_NAME`

```mojo
comptime ELEMENT_NAME = String("element")
```

### `ENTRIES_NAME`

```mojo
comptime ENTRIES_NAME = String("entries")
```

### `KEY_NAME`

```mojo
comptime KEY_NAME = String("key")
```

### `VALUE_NAME`

```mojo
comptime VALUE_NAME = String("value")
```