vj-codegen 0.1.0

//! The array manipulation methods (LRM 1800-2023 §7.12) on queues, dynamic
//! arrays, associative arrays and fixed-size one-dimensional unpacked
//! arrays: locators (`find`, `find_index`, `find_first[_index]`,
//! `find_last[_index]`, `min`, `max`, `unique`, `unique_index`), ordering
//! (`sort`, `rsort`, `reverse`, `shuffle`) and reductions (`sum`, `product`,
//! `and`, `or`, `xor`), each with its optional `with (expr)` clause.
//!
//! A method walks the elements in a loop emitted here, binding its iterator
//! (`item`, or a named one) to the current element and index
//! (`LowerCtx::iter`) while the `with` expression is lowered; results are
//! built with the collection store (`crate::collections`), whose runtime
//! also does the reordering (a sort by keys computed here).

use inkwell::IntPredicate;
use inkwell::basic_block::BasicBlock;
use inkwell::values::{BasicValueEnum, IntValue};
use sv_lang::{Expression, KnownSystemName, Symbol};
use sv_sim_runtime::collections_rt::CollOp;
use sv_sim_sim::symid::SymbolUid;

use crate::collections::{
    Args, Coll, call, coll_of, coll_of_expr, default_buf, elem_buf, handle_of, int, load_elem,
    load_key, op, set_handle, void,
};
use crate::error::LoweringError;
use crate::expr::{LowerCtx, LoweredValue, entry_alloca, lower_condition, lower_expr};
use crate::types::TypeWidth;
use crate::value::PackedValue;

/// The value an iterator variable stands for, if `sym` is one being bound.
pub(crate) fn iterator_value<'ctx>(
    cx: &LowerCtx<'ctx, '_, '_>,
    sym: &Symbol<'_>,
) -> Option<LoweredValue<'ctx>> {
    let id = sym.uid();
    cx.iter
        .borrow()
        .iter()
        .rev()
        .find(|(s, _, _)| *s == id)
        .map(|(_, item, _)| *item)
}

/// The elements an array method walks.
enum Source<'ctx, 'd> {
    /// A queue, dynamic or associative array (handle `h`).
    Coll { c: Coll<'d>, h: IntValue<'ctx> },
    /// A fixed-size unpacked array; a multi-dimensional one (locators,
    /// reductions with a row iterator and ordering methods, LRM 1800-2023
    /// 7.12.1-7.12.2) is walked by its first dimension, each element being
    /// the `inner` rows of the sub-array.
    Fixed {
        r: crate::arrays::ArrayRef<'ctx>,
        /// The element of the first dimension (a sub-array type when
        /// `inner > 1`).
        elem: sv_lang::Type<'d>,
        /// The innermost element type (one stored row).
        leaf: sv_lang::Type<'d>,
        /// Stored rows per element.
        inner: u64,
        low: i64,
        count: u64,
        /// `Some(member)` when `r` is a snapshot of a class property or
        /// struct member array (no row storage of its own): a reordering
        /// method packs the rows back into `member` afterwards.
        spilled: Option<Expression<'d>>,
    },
}

impl<'ctx, 'd> Source<'ctx, 'd> {
    /// The elements of `arr`. `read_only`: the caller never writes the
    /// elements back, so a member array (no row storage) may be walked
    /// through a snapshot copy.
    fn of(
        cx: &LowerCtx<'ctx, 'd, '_>,
        arr: Expression<'d>,
        read_only: bool,
        nd: bool,
    ) -> Result<Option<Self>, LoweringError> {
        if let Some(c) = coll_of_expr(&arr) {
            return Ok(Some(Source::Coll {
                c,
                h: handle_of(cx, arr)?,
            }));
        }
        if !arr.expr_type().is_some_and(|t| t.is_unpacked_array()) {
            return Ok(None);
        }
        let mut spilled = None;
        let (r, shape) = match crate::arrays::array_target(cx, arr)? {
            Some(t) => t,
            None => {
                let t = crate::arrays::spill_member_array(cx, arr)?.ok_or_else(|| {
                    LoweringError::unsupported_at(
                        "an array method on an array value that is not a variable",
                        &cx.fn_sym,
                    )
                })?;
                if !read_only {
                    spilled = Some(arr);
                }
                t
            }
        };
        if shape.dims.len() != 1 && !nd {
            return Err(LoweringError::unsupported_at(
                "min/max on a multi-dimensional \
                 unpacked array",
                &cx.fn_sym,
            ));
        }
        let (l, rr) = shape.dims[0];
        let inner = shape.stride(0);
        let elem = if shape.dims.len() == 1 {
            shape.elem
        } else {
            arr.expr_type()
                .and_then(|t| t.element_type())
                .ok_or_else(|| {
                    LoweringError::unsupported_at("an array method on an untyped array", &cx.fn_sym)
                })?
        };
        Ok(Some(Source::Fixed {
            r,
            elem,
            leaf: shape.elem,
            inner,
            low: l.min(rr),
            count: shape.size(0),
            spilled,
        }))
    }

    fn elem_type(&self) -> sv_lang::Type<'d> {
        match self {
            Source::Coll { c, .. } => c.elem,
            Source::Fixed { elem, .. } => *elem,
        }
    }

    /// The number of elements (`i64`).
    fn len(&self, cx: &LowerCtx<'ctx, 'd, '_>) -> IntValue<'ctx> {
        match self {
            Source::Coll { c, h } => call(cx, c, CollOp::Size, *h, Args::default()),
            Source::Fixed { count, .. } => cx.ctx.i64_type().const_int(*count, false),
        }
    }

    /// Element number `pos` (`i64`, in range) and its index.
    fn get(
        &self,
        cx: &LowerCtx<'ctx, 'd, '_>,
        pos: IntValue<'ctx>,
    ) -> Result<(LoweredValue<'ctx>, LoweredValue<'ctx>), LoweringError> {
        match self {
            Source::Coll { c, h } => {
                let val = entry_alloca(cx, op(cx).i_n(64 * c.words), "am_val");
                let dflt = default_buf(cx, c);
                if c.assoc {
                    let key = entry_alloca(cx, op(cx).i_n(64 * c.key_words()), "am_key");
                    call(
                        cx,
                        c,
                        CollOp::EntryAt,
                        *h,
                        Args {
                            index: Some(pos),
                            val: Some(val),
                            key: Some(key),
                            ..Args::default()
                        },
                    );
                    Ok((
                        load_elem(cx, c, val),
                        LoweredValue::Packed(load_key(cx, c, key)),
                    ))
                } else {
                    call(
                        cx,
                        c,
                        CollOp::Get,
                        *h,
                        Args {
                            index: Some(pos),
                            val: Some(val),
                            dflt: Some(dflt),
                            ..Args::default()
                        },
                    );
                    Ok((load_elem(cx, c, val), int(cx, pos)))
                }
            }
            Source::Fixed {
                r,
                elem,
                leaf,
                inner,
                low,
                ..
            } => {
                let pv = if *inner > 1 {
                    // A sub-array: its rows packed, row 0 in the lowest bits
                    // (the form of a collection's array element).
                    let first = cx
                        .b
                        .build_int_mul(pos, cx.ctx.i64_type().const_int(*inner, false), "am_row0")
                        .unwrap();
                    let o = op(cx);
                    let mut rows = Vec::new();
                    for j in 0..*inner {
                        let k = cx
                            .b
                            .build_int_add(first, cx.ctx.i64_type().const_int(j, false), "am_rowj")
                            .unwrap();
                        let v = crate::arrays::load_row(cx, r, k, leaf)?;
                        rows.push(crate::select::fit_width(&o, v, leaf.value_width()));
                    }
                    rows.reverse();
                    o.concat4(&rows)
                } else {
                    let e = crate::arrays::ElemRef {
                        backing: r.backing,
                        row: cx.b.build_int_add(r.base, pos, "am_row").unwrap(),
                        valid: r.valid,
                        width: elem.value_width(),
                        signed: elem.is_signed(),
                        default: crate::arrays::default_value(cx, elem),
                    };
                    crate::arrays::read_element(cx, &e)?
                };
                let item = if elem.is_floating() {
                    LoweredValue::Real(crate::real::bits_to_real(cx, pv))
                } else {
                    LoweredValue::Packed(pv)
                };
                let i64t = cx.ctx.i64_type();
                let idx =
                    cx.b.build_int_add(pos, i64t.const_int(*low as u64, true), "am_index")
                        .unwrap();
                Ok((item, int(cx, idx)))
            }
        }
    }
}

/// Emits `for pos in 0..n` (or `n-1 down to 0` when `backward`) around
/// `body`, which may branch to the block it is given to stop early.
pub(crate) fn each<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    n: IntValue<'ctx>,
    backward: bool,
    mut body: impl FnMut(IntValue<'ctx>, BasicBlock<'ctx>) -> Result<(), LoweringError>,
) -> Result<(), LoweringError> {
    let i64t = cx.ctx.i64_type();
    let f =
        cx.b.get_insert_block()
            .and_then(|bb| bb.get_parent())
            .expect("lowering happens inside a function");
    let pos = entry_alloca(cx, i64t, "am_pos");
    let one = i64t.const_int(1, false);
    let start = if backward {
        cx.b.build_int_sub(n, one, "am_last").unwrap()
    } else {
        i64t.const_zero()
    };
    cx.b.build_store(pos, start).unwrap();
    let header = cx.ctx.append_basic_block(f, "am_header");
    let body_bb = cx.ctx.append_basic_block(f, "am_body");
    let step = cx.ctx.append_basic_block(f, "am_step");
    let exit = cx.ctx.append_basic_block(f, "am_exit");
    cx.b.build_unconditional_branch(header).unwrap();
    cx.b.position_at_end(header);
    let p = cx.b.build_load(i64t, pos, "am_p").unwrap().into_int_value();
    let more = if backward {
        cx.b.build_int_compare(IntPredicate::SGE, p, i64t.const_zero(), "am_more")
    } else {
        cx.b.build_int_compare(IntPredicate::SLT, p, n, "am_more")
    }
    .unwrap();
    cx.b.build_conditional_branch(more, body_bb, exit).unwrap();
    cx.b.position_at_end(body_bb);
    body(p, exit)?;
    if cx
        .b
        .get_insert_block()
        .and_then(|b| b.get_terminator())
        .is_none()
    {
        cx.b.build_unconditional_branch(step).unwrap();
    }
    cx.b.position_at_end(step);
    let p =
        cx.b.build_load(i64t, pos, "am_p2")
            .unwrap()
            .into_int_value();
    let next = if backward {
        cx.b.build_int_sub(p, one, "am_next")
    } else {
        cx.b.build_int_add(p, one, "am_next")
    }
    .unwrap();
    cx.b.build_store(pos, next).unwrap();
    cx.b.build_unconditional_branch(header).unwrap();
    cx.b.position_at_end(exit);
    Ok(())
}

/// Runs `f` with `iter` bound to `(item, index)`.
fn with_iter<'ctx, 'd, T>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    iter: Option<Symbol<'d>>,
    item: LoweredValue<'ctx>,
    index: LoweredValue<'ctx>,
    f: impl FnOnce() -> Result<T, LoweringError>,
) -> Result<T, LoweringError> {
    let Some(sym) = iter else {
        return f();
    };
    cx.iter.borrow_mut().push((sym.uid(), item, index));
    let r = f();
    cx.iter.borrow_mut().pop();
    r
}

/// The iterator's `index` (`item.index`), for a `Call` to `index` on a
/// bound iterator.
fn iterator_index<'ctx>(
    cx: &LowerCtx<'ctx, '_, '_>,
    e: Expression<'_>,
) -> Option<LoweredValue<'ctx>> {
    let this = *e.operands().first()?;
    let id = this.referenced_symbol()?.uid();
    cx.iter
        .borrow()
        .iter()
        .rev()
        .find(|(s, _, _)| *s == id)
        .map(|(_, _, index)| *index)
}

/// A packed value converted to `width` bits of `signed`ness.
fn fit<'ctx>(
    cx: &LowerCtx<'ctx, '_, '_>,
    v: LoweredValue<'ctx>,
    width: u32,
    signed: bool,
) -> Result<PackedValue<'ctx>, LoweringError> {
    let pv = crate::real::to_storage(cx, v, width, "a >128-bit array method value")?;
    let pv = PackedValue { signed, ..pv };
    Ok(crate::select::fit_width(&op(cx), pv, width))
}

/// An array manipulation method or an iterator's `index` (`None` for any
/// other call).
pub(crate) fn lower<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    name: KnownSystemName,
    e: Expression<'d>,
) -> Option<Result<LoweredValue<'ctx>, LoweringError>> {
    use KnownSystemName as K;
    if name == K::Index {
        return iterator_index(cx, e).map(Ok);
    }
    if !matches!(
        name,
        K::Sum
            | K::Product
            | K::And
            | K::Or
            | K::XOr
            | K::Find
            | K::FindIndex
            | K::FindFirst
            | K::FindFirstIndex
            | K::FindLast
            | K::FindLastIndex
            | K::Min
            | K::Max
            | K::Unique
            | K::UniqueIndex
            | K::Sort
            | K::Rsort
            | K::Reverse
            | K::Shuffle
            | K::Map
    ) {
        return None;
    }
    // The array (with a `with` clause, slang lists that expression first).
    let arr = e.operands().into_iter().find(|o| {
        o.expr_type()
            .is_some_and(|t| t.is_unpacked_array() || sv_sim_sim::state::storage::is_collection(&t))
    })?;
    Some((|| {
        let read_only = !matches!(name, K::Sort | K::Rsort | K::Reverse | K::Shuffle);
        let src = Source::of(
            cx,
            arr,
            read_only,
            // Min/max order the elements, which a row is not (LRM 7.12.3).
            !matches!(name, K::Min | K::Max),
        )?
        .ok_or_else(|| {
            LoweringError::unsupported_at("an array method on a non-array", &cx.fn_sym)
        })?;
        match name {
            K::Sum | K::Product | K::And | K::Or | K::XOr => reduce(cx, name, e, &src),
            K::Find
            | K::FindIndex
            | K::FindFirst
            | K::FindFirstIndex
            | K::FindLast
            | K::FindLastIndex => locate(cx, name, e, &src),
            K::Map => map(cx, e, &src),
            K::Min | K::Max => extreme(cx, name == K::Max, e, &src),
            K::Unique | K::UniqueIndex => unique(cx, name == K::UniqueIndex, e, &src),
            _ => reorder(cx, name, e, arr, &src),
        }
    })())
}

/// `sum`, `product`, `and`, `or`, `xor`: folded in the result type (the
/// `with` expression's, else the element's).
fn reduce<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    name: KnownSystemName,
    e: Expression<'d>,
    src: &Source<'ctx, 'd>,
) -> Result<LoweredValue<'ctx>, LoweringError> {
    use KnownSystemName as K;
    let rt = e
        .expr_type()
        .ok_or_else(|| LoweringError::unsupported_at("a reduction with no type", &cx.fn_sym))?;
    if !rt.is_integral() {
        return Err(LoweringError::unsupported_at(
            "a reduction method over non-integral values",
            &cx.fn_sym,
        ));
    }
    let width = rt.value_width();
    let signed = rt.is_signed();
    let o = op(cx);
    let ty = o.i_n(width);
    let start = match name {
        K::Product => ty.const_int(1, false),
        K::And => ty.const_all_ones(),
        _ => ty.const_zero(),
    };
    let init = o.pack(start, ty.const_zero(), width, cx.repr, signed);
    let acc = entry_alloca(cx, init.llvm.get_type(), "am_acc");
    cx.b.build_store(acc, init.llvm).unwrap();
    let with = e.iterator_expr();
    let iter = e.iterator_var();
    each(cx, src.len(cx), false, |pos, _| {
        let (item, index) = src.get(cx, pos)?;
        let v = match with {
            Some(w) => with_iter(cx, iter, item, index, || lower_expr(cx, w))?,
            None => item,
        };
        let v = fit(cx, v, width, signed)?;
        let cur = PackedValue {
            llvm: cx
                .b
                .build_load(init.llvm.get_type(), acc, "am_cur")
                .unwrap()
                .into_int_value(),
            ..init
        };
        let o = op(cx);
        let next = match name {
            K::Sum => o.add4(cur, v),
            K::Product => o.mul4(cur, v),
            K::And => o.and4(cur, v),
            K::Or => o.or4(cur, v),
            _ => o.xor4(cur, v),
        };
        cx.b.build_store(acc, next.llvm).unwrap();
        Ok(())
    })?;
    let v =
        cx.b.build_load(init.llvm.get_type(), acc, "am_result")
            .unwrap()
            .into_int_value();
    Ok(LoweredValue::Packed(PackedValue { llvm: v, ..init }))
}

/// The result queue type of a locator method.
fn result_coll<'d>(
    cx: &LowerCtx<'_, 'd, '_>,
    e: Expression<'d>,
) -> Result<Coll<'d>, LoweringError> {
    e.expr_type()
        .as_ref()
        .and_then(coll_of)
        .ok_or_else(|| LoweringError::unsupported_at("a locator method's result type", &cx.fn_sym))
}

/// `find[_first|_last][_index] with (cond)`: the matching elements (or
/// their indices), in order; `_first`/`_last` stop at the first match
/// from their end.
fn locate<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    name: KnownSystemName,
    e: Expression<'d>,
    src: &Source<'ctx, 'd>,
) -> Result<LoweredValue<'ctx>, LoweringError> {
    use KnownSystemName as K;
    let rc = result_coll(cx, e)?;
    let cond = e.iterator_expr().ok_or_else(|| {
        LoweringError::unsupported_at("a find method with no `with` clause", &cx.fn_sym)
    })?;
    let iter = e.iterator_var();
    let want_index = matches!(name, K::FindIndex | K::FindFirstIndex | K::FindLastIndex);
    let once = !matches!(name, K::Find | K::FindIndex);
    let backward = matches!(name, K::FindLast | K::FindLastIndex);
    let i64t = cx.ctx.i64_type();
    let out = entry_alloca(cx, i64t, "am_out");
    cx.b.build_store(out, i64t.const_zero()).unwrap();
    let f =
        cx.b.get_insert_block()
            .and_then(|bb| bb.get_parent())
            .expect("lowering happens inside a function");
    each(cx, src.len(cx), backward, |pos, exit| {
        let (item, index) = src.get(cx, pos)?;
        let hit = with_iter(cx, iter, item, index, || lower_condition(cx, cond))?;
        let then_bb = cx.ctx.append_basic_block(f, "am_hit");
        let skip_bb = cx.ctx.append_basic_block(f, "am_skip");
        cx.b.build_conditional_branch(hit, then_bb, skip_bb)
            .unwrap();
        cx.b.position_at_end(then_bb);
        let picked = if want_index { index } else { item };
        crate::collections::retain_elem(cx, &rc, picked);
        let val = elem_buf(cx, &rc, picked)?;
        let h = cx.b.build_load(i64t, out, "am_h").unwrap().into_int_value();
        let h = call(
            cx,
            &rc,
            CollOp::Push,
            h,
            Args {
                val: Some(val),
                ..Args::default()
            },
        );
        cx.b.build_store(out, h).unwrap();
        if once {
            cx.b.build_unconditional_branch(exit).unwrap();
        } else {
            cx.b.build_unconditional_branch(skip_bb).unwrap();
        }
        cx.b.position_at_end(skip_bb);
        Ok(())
    })?;
    let h =
        cx.b.build_load(i64t, out, "am_found")
            .unwrap()
            .into_int_value();
    Ok(LoweredValue::Packed(crate::collections::handle_value(
        cx, h,
    )))
}

/// `map() with (expr)` (LRM 1800-2023 7.12.5): an array of the source's
/// shape (a dynamic array, queue or associative array with the same index
/// values) whose element at each index is `expr` evaluated with the iterator
/// bound to the source element there. The element type is the `with`
/// expression's self-determined type (slang computes the result type).
/// A fixed-size source goes through [`map_fixed_values`]; class-keyed associative
/// arrays are refused by name.
fn map<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    e: Expression<'d>,
    src: &Source<'ctx, 'd>,
) -> Result<LoweredValue<'ctx>, LoweringError> {
    let rc = e.expr_type().as_ref().and_then(coll_of).ok_or_else(|| {
        LoweringError::unsupported_at(
            "map() on a fixed-size unpacked array (its result is a fixed-size array)",
            &cx.fn_sym,
        )
    })?;
    if rc.obj
        || rc.leaky
        || rc.key_kind >= 3
        || sv_sim_sim::state::storage::is_collection(&rc.elem)
        || rc.elem.is_unpacked_array()
    {
        return Err(LoweringError::unsupported_at(
            "map() producing class-handle, aggregate or collection elements, or over a \
             class-keyed associative array",
            &cx.fn_sym,
        ));
    }
    let with = e
        .iterator_expr()
        .ok_or_else(|| LoweringError::unsupported_at("map() with no `with` clause", &cx.fn_sym))?;
    let iter = e.iterator_var();
    let i64t = cx.ctx.i64_type();
    let out = entry_alloca(cx, i64t, "am_out");
    cx.b.build_store(out, i64t.const_zero()).unwrap();
    each(cx, src.len(cx), false, |pos, _| {
        let (item, index) = src.get(cx, pos)?;
        let v = with_iter(cx, iter, item, index, || lower_expr(cx, with))?;
        let val = elem_buf(cx, &rc, v)?;
        let h = cx.b.build_load(i64t, out, "am_h").unwrap().into_int_value();
        let h = if rc.assoc {
            let LoweredValue::Packed(k) = index else {
                return Err(LoweringError::unsupported_at(
                    "map(): an associative index that is not integral",
                    &cx.fn_sym,
                ));
            };
            let key = crate::collections::words_buf(
                cx,
                rc.key_words(),
                crate::collections::four_state(cx, k),
                "am_mapkey",
            );
            call(
                cx,
                &rc,
                CollOp::Store,
                h,
                Args {
                    key: Some(key),
                    val: Some(val),
                    ..Args::default()
                },
            )
        } else {
            call(
                cx,
                &rc,
                CollOp::Push,
                h,
                Args {
                    val: Some(val),
                    ..Args::default()
                },
            )
        };
        cx.b.build_store(out, h).unwrap();
        Ok(())
    })?;
    let h =
        cx.b.build_load(i64t, out, "am_mapped")
            .unwrap()
            .into_int_value();
    Ok(LoweredValue::Packed(crate::collections::handle_value(
        cx, h,
    )))
}

/// `map() with (expr)` over a fixed-size unpacked array (LRM 1800-2023
/// 7.12.5: the result has the source's range, so it is a fixed-size array):
/// the per-row values of the result, lowest index first, for
/// `array_operand`. `None` when `e` is not such a call. Only integral
/// result elements are supported; any other is refused by name.
pub(crate) fn map_fixed_values<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    e: Expression<'d>,
) -> Option<Result<Vec<PackedValue<'ctx>>, LoweringError>> {
    if e.kind() != sv_lang::kinds::ExpressionKind::Call
        || e.is_system_call() != Some(true)
        || e.system_subroutine()?.known_name_id() != KnownSystemName::Map
    {
        return None;
    }
    let arr = e
        .operands()
        .into_iter()
        .find(|o| o.expr_type().is_some_and(|t| t.is_unpacked_array()))?;
    if coll_of_expr(&arr).is_some() {
        return None;
    }
    Some((|| {
        let src = Source::of(cx, arr, true, false)?.ok_or_else(|| {
            LoweringError::unsupported_at("an array method on a non-array", &cx.fn_sym)
        })?;
        let Source::Fixed { count, .. } = &src else {
            return Err(LoweringError::unsupported_at(
                "map() on a fixed-size unpacked array (its result is a fixed-size array)",
                &cx.fn_sym,
            ));
        };
        let with = e.iterator_expr().ok_or_else(|| {
            LoweringError::unsupported_at("map() with no `with` clause", &cx.fn_sym)
        })?;
        if !with.expr_type().is_some_and(|t| t.is_integral()) {
            return Err(LoweringError::unsupported_at(
                "map() over a fixed-size array producing non-integral elements",
                &cx.fn_sym,
            ));
        }
        let iter = e.iterator_var();
        let i64t = cx.ctx.i64_type();
        let mut out = Vec::new();
        for r in 0..*count {
            let (item, index) = src.get(cx, i64t.const_int(r, false))?;
            let v = with_iter(cx, iter, item, index, || lower_expr(cx, with))?;
            out.push(v.into_packed("a map() element", &cx.fn_sym)?);
        }
        Ok(out)
    })())
}

/// `min` / `max`: a queue of the (first) extreme element, empty for an
/// empty array; with `with (expr)`, the element whose `expr` is extreme.
fn extreme<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    max: bool,
    e: Expression<'d>,
    src: &Source<'ctx, 'd>,
) -> Result<LoweredValue<'ctx>, LoweringError> {
    let rc = result_coll(cx, e)?;
    let with = e.iterator_expr();
    let iter = e.iterator_var();
    let kt = with
        .and_then(|w| w.expr_type())
        .unwrap_or_else(|| src.elem_type());
    // LRM 7.12.2: real elements order by `<` as any other (a NaN never wins).
    let real = kt.is_floating();
    // LRM 7.12.2/6.16.8: strings order by the lexicographic `<` (the
    // runtime's string compare); a `with` key is a temporary the loop
    // does not own, so only the element itself may be the string key.
    let stringy = kt.is_string();
    if stringy && with.is_some() {
        return Err(LoweringError::unsupported_at(
            "min/max with (expr) over string keys",
            &cx.fn_sym,
        ));
    }
    if !kt.is_integral() && !real && !stringy {
        return Err(LoweringError::unsupported_at(
            "min/max over aggregate values",
            &cx.fn_sym,
        ));
    }
    let kw = if real || stringy {
        64
    } else {
        kt.value_width()
    };
    let ks = kt.is_signed();
    let o = op(cx);
    let f64t = cx.ctx.f64_type();
    let kty: inkwell::types::BasicTypeEnum<'ctx> = if real {
        f64t.into()
    } else if stringy {
        cx.ctx.i64_type().into()
    } else {
        o.packed_type(kw, cx.repr).into()
    };
    let best_key = entry_alloca(cx, kty, "am_best_key");
    let best_item = entry_alloca(cx, o.i_n(64 * rc.words), "am_best_item");
    let have = entry_alloca(cx, cx.ctx.bool_type(), "am_have");
    cx.b.build_store(have, cx.ctx.bool_type().const_zero())
        .unwrap();
    // A null handle until an element is taken (an empty source pushes it
    // and discards the queue; the retain below must see a defined word).
    cx.b.build_store(best_item, o.i_n(64 * rc.words).const_zero())
        .unwrap();
    let f =
        cx.b.get_insert_block()
            .and_then(|bb| bb.get_parent())
            .expect("lowering happens inside a function");
    each(cx, src.len(cx), false, |pos, _| {
        let (item, index) = src.get(cx, pos)?;
        let key = match with {
            Some(w) => with_iter(cx, iter, item, index, || lower_expr(cx, w))?,
            None => item,
        };
        let (key_llvm, better): (BasicValueEnum<'ctx>, IntValue<'ctx>) = if stringy {
            // A string element is loaded as its 64-bit handle word.
            let k = match key {
                LoweredValue::Str(s) => s.llvm,
                LoweredValue::Packed(pv) => {
                    let o = op(cx);
                    o.lane_val(o.to_2state4(pv))
                }
                _ => {
                    return Err(LoweringError::unsupported_at(
                        "min/max: a string element did not lower to a handle",
                        &cx.fn_sym,
                    ));
                }
            };
            let cur =
                cx.b.build_load(cx.ctx.i64_type(), best_key, "am_bk")
                    .unwrap()
                    .into_int_value();
            let zero = cx.ctx.i64_type().const_zero();
            let c = crate::strings::str_op(cx, sv_sim_sim::strings::StrOp::Compare, k, cur, zero);
            let pred = if max {
                IntPredicate::SGT
            } else {
                IntPredicate::SLT
            };
            let better = cx.b.build_int_compare(pred, c, zero, "am_sbetter").unwrap();
            (k.into(), better)
        } else if real {
            let LoweredValue::Real(r) = key else {
                return Err(LoweringError::unsupported_at(
                    "min/max: a real element key did not lower to a real",
                    &cx.fn_sym,
                ));
            };
            let k = cx.b.build_float_cast(r.llvm, f64t, "am_kf").unwrap();
            let cur =
                cx.b.build_load(f64t, best_key, "am_bk")
                    .unwrap()
                    .into_float_value();
            let pred = if max {
                inkwell::FloatPredicate::OGT
            } else {
                inkwell::FloatPredicate::OLT
            };
            let better =
                cx.b.build_float_compare(pred, k, cur, "am_fbetter")
                    .unwrap();
            (k.into(), better)
        } else {
            let key = fit(cx, key, kw, ks)?;
            let o = op(cx);
            let cur = PackedValue {
                llvm: cx
                    .b
                    .build_load(kty, best_key, "am_bk")
                    .unwrap()
                    .into_int_value(),
                ..key
            };
            let better = match (max, ks) {
                (true, true) => o.sgt4(key, cur),
                (true, false) => o.ugt4(key, cur),
                (false, true) => o.slt4(key, cur),
                (false, false) => o.ult4(key, cur),
            };
            (
                key.llvm.into(),
                crate::ops::is_definitely_true(cx.ctx, &cx.b, better),
            )
        };
        let had =
            cx.b.build_load(cx.ctx.bool_type(), have, "am_had")
                .unwrap()
                .into_int_value();
        let first = cx.b.build_not(had, "am_first").unwrap();
        let take = cx.b.build_or(first, better, "am_take").unwrap();
        let then_bb = cx.ctx.append_basic_block(f, "am_take");
        let skip_bb = cx.ctx.append_basic_block(f, "am_keep");
        cx.b.build_conditional_branch(take, then_bb, skip_bb)
            .unwrap();
        cx.b.position_at_end(then_bb);
        cx.b.build_store(best_key, key_llvm).unwrap();
        let buf = elem_buf(cx, &rc, item)?;
        let words =
            cx.b.build_load(op(cx).i_n(64 * rc.words), buf, "am_item_words")
                .unwrap();
        cx.b.build_store(best_item, words).unwrap();
        cx.b.build_store(have, cx.ctx.bool_type().const_all_ones())
            .unwrap();
        cx.b.build_unconditional_branch(skip_bb).unwrap();
        cx.b.position_at_end(skip_bb);
        Ok(())
    })?;
    // The result: the best element, if there was one. The queue holds its
    // own reference on a class element (the source keeps its own; a
    // premature free comes only from a missing retain, LRM 8.29).
    let i64t = cx.ctx.i64_type();
    if rc.obj {
        let best =
            cx.b.build_load(i64t, best_item, "am_best_h")
                .unwrap()
                .into_int_value();
        crate::classes::retain_handle(cx, best);
    }
    let one = call(
        cx,
        &rc,
        CollOp::Push,
        i64t.const_zero(),
        Args {
            val: Some(best_item),
            ..Args::default()
        },
    );
    let had =
        cx.b.build_load(cx.ctx.bool_type(), have, "am_any")
            .unwrap()
            .into_int_value();
    let h =
        cx.b.build_select(had, one, i64t.const_zero(), "am_extreme")
            .unwrap()
            .into_int_value();
    Ok(LoweredValue::Packed(crate::collections::handle_value(
        cx, h,
    )))
}

/// The elements of `src` gathered into a new queue of shape `c` (a fixed
/// array's rows, for the runtime's reordering).
fn gather<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    c: &Coll<'d>,
    src: &Source<'ctx, 'd>,
) -> Result<IntValue<'ctx>, LoweringError> {
    if let Source::Coll { c: sc, h } = src
        && !sc.assoc
    {
        return Ok(call(cx, sc, CollOp::Clone, *h, Args::default()));
    }
    let i64t = cx.ctx.i64_type();
    let out = entry_alloca(cx, i64t, "am_gather");
    cx.b.build_store(out, i64t.const_zero()).unwrap();
    each(cx, src.len(cx), false, |pos, _| {
        let (item, _) = src.get(cx, pos)?;
        crate::collections::retain_elem(cx, c, item);
        let val = elem_buf(cx, c, item)?;
        let h = cx.b.build_load(i64t, out, "am_g").unwrap().into_int_value();
        let h = call(
            cx,
            c,
            CollOp::Push,
            h,
            Args {
                val: Some(val),
                ..Args::default()
            },
        );
        cx.b.build_store(out, h).unwrap();
        Ok(())
    })?;
    Ok(cx
        .b
        .build_load(i64t, out, "am_gathered")
        .unwrap()
        .into_int_value())
}

/// A fixed-size array's elements (`arr`, in index order) as a new
/// collection of shape `c` (`q = fixed_array;`).
pub(crate) fn gather_fixed<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    c: &Coll<'d>,
    arr: Expression<'d>,
) -> Result<IntValue<'ctx>, LoweringError> {
    // A slice of a dynamic array or queue (`q = d[1:2]`, LRM 1800-2023
    // 7.4.3): slice the base collection, copy that, release the temporary.
    if arr.kind() == sv_lang::kinds::ExpressionKind::RangeSelect
        && let Some(base) = arr.select_value()
        && let Some(bc) = coll_of_expr(&base)
        && !bc.assoc
    {
        let h = handle_of(cx, base)?;
        let (lo, hi) = crate::collections::slice_bounds(cx, &bc, h, arr)?;
        let part = call(
            cx,
            &bc,
            CollOp::Slice,
            h,
            Args {
                index: Some(lo),
                index2: Some(hi),
                ..Args::default()
            },
        );
        let out = gather(cx, c, &Source::Coll { c: bc, h: part });
        call(cx, &bc, CollOp::Release, part, Args::default());
        return out;
    }
    // `q = fixed.map() with (..)` (LRM 7.12.5: the result is a fixed-size array,
    // assignable to a queue or dynamic array): push each mapped value in turn.
    if let Some(values) = map_fixed_values(cx, arr) {
        let i64t = cx.ctx.i64_type();
        let mut h = i64t.const_zero();
        for v in values? {
            let val = elem_buf(cx, c, LoweredValue::Packed(v))?;
            h = call(
                cx,
                c,
                CollOp::Push,
                h,
                Args {
                    val: Some(val),
                    ..Args::default()
                },
            );
        }
        return Ok(h);
    }
    // A named constant array of `string` (LRM 1800-2023 6.20.2): each element's literal,
    // lowest index first (the order a variable's elements copy in).
    if arr.kind() == sv_lang::kinds::ExpressionKind::NamedValue
        && let Some(sv_lang::ConstantValue::Array(elems)) = arr.constant_value()
        && c.elem.is_string()
        && arr
            .expr_type()
            .as_ref()
            .and_then(crate::arrays::array_shape)
            .is_some_and(|sh| sh.dims.len() == 1 && sh.elem.is_string())
    {
        let i64t = cx.ctx.i64_type();
        let mut h = i64t.const_zero();
        let descending = arr
            .expr_type()
            .and_then(|t| crate::arrays::array_shape(&t))
            .is_some_and(|sh| sh.dims[0].0 > sh.dims[0].1);
        let mut ordered: Vec<&sv_lang::ConstantValue> = elems.iter().collect();
        if descending {
            ordered.reverse();
        }
        for el in ordered {
            let sv_lang::ConstantValue::String(text) = el else {
                return Err(LoweringError::unsupported_at(
                    "a constant string array with an element of another kind",
                    &cx.fn_sym,
                ));
            };
            let lit = crate::strings::literal(cx, text.as_bytes());
            let val = elem_buf(cx, c, LoweredValue::Str(lit))?;
            h = call(
                cx,
                c,
                CollOp::Push,
                h,
                Args {
                    val: Some(val),
                    ..Args::default()
                },
            );
        }
        return Ok(h);
    }
    let src = Source::of(cx, arr, true, false)?.ok_or_else(|| {
        LoweringError::unsupported_at(
            "a fixed-size array value that is not a variable",
            &cx.fn_sym,
        )
    })?;
    gather(cx, c, &src)
}

/// A queue shape for elements of type `elem`.
fn seq_of<'d>(elem: sv_lang::Type<'d>) -> Coll<'d> {
    let obj = elem.is_class();
    let width = if obj { 64 } else { elem.value_width().max(1) };
    Coll {
        elem,
        width,
        obj,
        words: (2 * width).div_ceil(64).max(1),
        assoc: false,
        queue: true,
        bound: 0,
        key_kind: 0,
        key_width: 0,
        leaky: false,
    }
}

/// The `with (expr)` key of every element of the queue `h` (shape `c`),
/// in order, as a new queue (the caller releases it) and the key type.
fn key_queue<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    c: &Coll<'d>,
    h: IntValue<'ctx>,
    e: Expression<'d>,
    w: Expression<'d>,
) -> Result<(IntValue<'ctx>, sv_lang::Type<'d>), LoweringError> {
    let i64t = cx.ctx.i64_type();
    let kt = w
        .expr_type()
        .ok_or_else(|| LoweringError::unsupported_at("a `with` key with no type", &cx.fn_sym))?;
    let kc = seq_of(kt);
    let iter = e.iterator_var();
    let out = entry_alloca(cx, i64t, "am_keys");
    cx.b.build_store(out, i64t.const_zero()).unwrap();
    let walk = Source::Coll { c: *c, h };
    each(cx, walk.len(cx), false, |pos, _| {
        let (item, index) = walk.get(cx, pos)?;
        let k = with_iter(cx, iter, item, index, || lower_expr(cx, w))?;
        let val = elem_buf(cx, &kc, k)?;
        let cur = cx.b.build_load(i64t, out, "am_k").unwrap().into_int_value();
        let cur = call(
            cx,
            &kc,
            CollOp::Push,
            cur,
            Args {
                val: Some(val),
                ..Args::default()
            },
        );
        cx.b.build_store(out, cur).unwrap();
        Ok(())
    })?;
    Ok((
        cx.b.build_load(i64t, out, "am_keys_h")
            .unwrap()
            .into_int_value(),
        kt,
    ))
}

/// `unique` / `unique_index`: each distinct value's first occurrence.
fn unique<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    index: bool,
    e: Expression<'d>,
    src: &Source<'ctx, 'd>,
) -> Result<LoweredValue<'ctx>, LoweringError> {
    // An associative array's `unique_index` yields the first occurrence's
    // key (LRM 7.12.1); the runtime reports walk positions, mapped to keys below.
    let assoc_src = index && matches!(src, Source::Coll { c, .. } if c.assoc);
    let c = seq_of(src.elem_type());
    let all = gather(cx, &c, src)?;
    let i64t = cx.ctx.i64_type();
    // `unique with (expr)`: elements are distinct by their key (LRM 7.12.1).
    let keys = match e.iterator_expr() {
        Some(w) => Some(key_queue(cx, &c, all, e, w)?.0),
        None => None,
    };
    let mut h = call(
        cx,
        &c,
        CollOp::Unique,
        all,
        Args {
            index2: Some(i64t.const_int(u64::from(index), false)),
            h2: keys,
            ..Args::default()
        },
    );
    if let Some(k) = keys {
        call(cx, &c, CollOp::Release, k, Args::default());
    }
    call(cx, &c, CollOp::Release, all, Args::default());
    if assoc_src {
        let rc = result_coll(cx, e)?;
        let pc = Coll {
            width: 32,
            words: 1,
            obj: false,
            ..seq_of(rc.elem)
        };
        let keyed = entry_alloca(cx, i64t, "am_ukeys");
        cx.b.build_store(keyed, i64t.const_zero()).unwrap();
        let n = call(cx, &pc, CollOp::Size, h, Args::default());
        let from = h;
        each(cx, n, false, |pos, _| {
            let (p, _) = (Source::Coll { c: pc, h: from }).get(cx, pos)?;
            let p = p.into_packed("an index", &cx.fn_sym)?;
            let at = cx.b.build_int_truncate(p.llvm, i64t, "am_upos").unwrap();
            let (_, key) = src.get(cx, at)?;
            crate::collections::retain_elem(cx, &rc, key);
            let val = elem_buf(cx, &rc, key)?;
            let cur =
                cx.b.build_load(i64t, keyed, "am_uk")
                    .unwrap()
                    .into_int_value();
            let cur = call(
                cx,
                &rc,
                CollOp::Push,
                cur,
                Args {
                    val: Some(val),
                    ..Args::default()
                },
            );
            cx.b.build_store(keyed, cur).unwrap();
            Ok(())
        })?;
        call(cx, &pc, CollOp::Release, from, Args::default());
        h =
            cx.b.build_load(i64t, keyed, "am_ukeys_h")
                .unwrap()
                .into_int_value();
    }
    // A fixed array's `unique_index` counts from its low bound.
    if index
        && let Source::Fixed { low, .. } = src
        && *low != 0
    {
        let rc = result_coll(cx, e)?;
        let shifted = entry_alloca(cx, i64t, "am_uidx");
        cx.b.build_store(shifted, i64t.const_zero()).unwrap();
        let n = call(cx, &rc, CollOp::Size, h, Args::default());
        let from = h;
        each(cx, n, false, |pos, _| {
            let (v, _) = (Source::Coll { c: rc, h: from }).get(cx, pos)?;
            let o = op(cx);
            let k = o.pack(
                cx.ctx.i32_type().const_int(*low as u64, true),
                cx.ctx.i32_type().const_zero(),
                32,
                cx.repr,
                true,
            );
            let v = o.add4(v.into_packed("an index", &cx.fn_sym)?, k);
            let val = elem_buf(cx, &rc, LoweredValue::Packed(v))?;
            let cur =
                cx.b.build_load(i64t, shifted, "am_u")
                    .unwrap()
                    .into_int_value();
            let cur = call(
                cx,
                &rc,
                CollOp::Push,
                cur,
                Args {
                    val: Some(val),
                    ..Args::default()
                },
            );
            cx.b.build_store(shifted, cur).unwrap();
            Ok(())
        })?;
        call(cx, &rc, CollOp::Release, from, Args::default());
        h =
            cx.b.build_load(i64t, shifted, "am_uidx_h")
                .unwrap()
                .into_int_value();
    }
    Ok(LoweredValue::Packed(crate::collections::handle_value(
        cx, h,
    )))
}

/// Sort flags for the runtime (`CollOp::Sort`): 1 signed, 2 string, 4
/// real, 8 shortreal.
fn sort_flags(t: &sv_lang::Type<'_>) -> u64 {
    let mut f = u64::from(t.is_signed());
    if t.is_string() {
        f |= 2;
    } else if t.is_floating() {
        f |= if t.bit_width() == 32 { 8 } else { 4 };
    }
    f
}

/// `sort`, `rsort` (by element, or by `with (expr)`), `reverse`, `shuffle`:
/// in place.
fn reorder<'ctx, 'd>(
    cx: &LowerCtx<'ctx, 'd, '_>,
    name: KnownSystemName,
    e: Expression<'d>,
    arr: Expression<'d>,
    src: &Source<'ctx, 'd>,
) -> Result<LoweredValue<'ctx>, LoweringError> {
    use KnownSystemName as K;
    let c = match src {
        Source::Coll { c, .. } => *c,
        Source::Fixed { elem, .. } => seq_of(*elem),
    };
    if c.assoc {
        return Err(LoweringError::unsupported_at(
            "reordering an associative array",
            &cx.fn_sym,
        ));
    }
    let i64t = cx.ctx.i64_type();
    let h = match src {
        Source::Coll { h, .. } => *h,
        Source::Fixed { .. } => gather(cx, &c, src)?,
    };
    let new = match name {
        K::Reverse => call(cx, &c, CollOp::Reverse, h, Args::default()),
        K::Shuffle => call(cx, &c, CollOp::Shuffle, h, Args::default()),
        _ => {
            let desc = if name == K::Rsort { 16 } else { 0 };
            let (keys, kt) = match e.iterator_expr() {
                Some(w) => key_queue(cx, &c, h, e, w)?,
                None => (i64t.const_zero(), c.elem),
            };
            let sorted = call(
                cx,
                &c,
                CollOp::Sort,
                h,
                Args {
                    index: Some(i64t.const_int(u64::from(kt.value_width().max(1)), false)),
                    index2: Some(i64t.const_int(sort_flags(&kt) | desc, false)),
                    h2: Some(keys),
                    ..Args::default()
                },
            );
            call(cx, &c, CollOp::Release, keys, Args::default());
            sorted
        }
    };
    match src {
        Source::Coll { .. } => set_handle(cx, arr, new)?,
        Source::Fixed {
            r,
            elem,
            leaf,
            inner,
            spilled,
            ..
        } => {
            // Write the reordered elements back, then drop the copy.
            let walk = Source::Coll { c, h: new };
            each(cx, walk.len(cx), false, |pos, _| {
                let (item, _) = walk.get(cx, pos)?;
                let pv = fit(cx, item, elem.value_width(), elem.is_signed())?;
                for j in 0..*inner {
                    let first =
                        cx.b.build_int_mul(pos, i64t.const_int(*inner, false), "am_wrow0")
                            .unwrap();
                    let row = cx.b.build_int_add(r.base, first, "am_wrowb").unwrap();
                    let row =
                        cx.b.build_int_add(row, i64t.const_int(j, false), "am_wrow")
                            .unwrap();
                    let dst = crate::arrays::ElemRef {
                        backing: r.backing,
                        row,
                        valid: r.valid,
                        width: leaf.value_width(),
                        signed: leaf.is_signed(),
                        default: crate::arrays::default_value(cx, leaf),
                    };
                    let lw = leaf.value_width();
                    let part = if *inner > 1 {
                        crate::stream::bits(cx, pv, (j as u32) * lw, lw)
                    } else {
                        pv
                    };
                    crate::arrays::write_element(cx, &dst, part)?;
                }
                Ok(())
            })?;
            call(cx, &c, CollOp::Release, new, Args::default());
            if let Some(member) = spilled {
                // The rows were reordered in a snapshot: pack them (row 0 in
                // the lowest bits, the form `spill_member_array` cut) and
                // store the whole array back into the member.
                let op = crate::ops::OpBuilder {
                    ctx: cx.ctx,
                    b: &cx.b,
                };
                let (shape_rows, w) = (src_count(src), leaf.value_width());
                let mut rows = Vec::new();
                for i in 0..shape_rows {
                    let sr = *r;
                    let v = crate::arrays::load_row(cx, &sr, i64t.const_int(i, false), leaf)?;
                    rows.push(crate::select::fit_width(&op, v, w));
                }
                rows.reverse();
                crate::select::lower_assign_to(cx, *member, op.concat4(&rows))?;
            }
        }
    }
    Ok(void(cx))
}

/// The number of elements of a fixed source.
fn src_count(src: &Source<'_, '_>) -> u64 {
    match src {
        Source::Fixed { count, inner, .. } => *count * *inner,
        Source::Coll { .. } => 0,
    }
}