iridia 0.5.0

//! A program's WGSL as one pipeline binds it ([`wgsl_for`]): where its resources are bound, where a vertex program's
//! outputs land in the program that reads them, and what WebGPU without its optional features cannot take. Each is a
//! change to a copy of the program's module, written once it validates: the text is never edited, and the
//! [`Program`] keeps its own interface and bindings.
use std::collections::{BTreeMap, BTreeSet};

use naga::{
    Binding, Block, Expression, Handle, Interpolation, ResourceBinding, Span, Statement, StructMember, Type,
    TypeInner,
};

use crate::build::Width;
use crate::program::module_info;
use crate::{
    EntryIo, Interface, IoType, Label, Program, ProgramError as Error, ResourceId, ScalarType, Stage, Value,
    entry_io,
};

/// Clip distances carried as plain varyings: `count` scalars at the locations from `first`, interpolated
/// perspective-correct.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ClipVaryings {
    /// The location of the first clip distance varying.
    pub first: u32,
    /// How many clip distances there are.
    pub count: u32,
}

/// The pipeline a program's WGSL is written for. The default changes nothing: the text is [`super::wgsl`]'s.
#[derive(Clone, Debug, Default)]
pub struct Pipeline<'a> {
    /// The group and binding of each resource named here, in place of the program's own.
    pub bindings: BTreeMap<ResourceId, (u32, u32)>,
    /// The program a vertex program's outputs feed. Each output the consumer reads, matched as Direct3D links stages
    /// (by semantic: the label's name without case, and its index), takes the consumer's location and interpolation
    /// for it ([`entry_io`]); the others take the locations after the consumer's. A consumer input no output carries
    /// is an error. WebGPU links a location only between values of one type, where Direct3D links register lanes: an
    /// output the consumer reads as another value takes the consumer's type. Fewer lanes are the output's first
    /// ones; more lanes are the output's followed by zeros, which Direct3D leaves undefined (noted); another scalar
    /// kind is the same bits (Direct3D links bits). A boolean or 64-bit value of another type is refused.
    pub feeds: Option<&'a Interface>,
    /// A vertex program's clip distances as plain varyings ([`ClipVaryings`], after every other output), for a
    /// pipeline without WebGPU's `clip-distances` feature. A consumer discards where one is negative
    /// ([`Pipeline::clip_discard`]): a distance linear in the clip position interpolates perspective-correct to its
    /// value at the pixel, so this keeps what a clipper keeps, decided at pixel centres.
    pub clip_varyings: bool,
    /// A pixel program's inputs for its producer's [`ClipVaryings`], and a discard before each return where one of
    /// them is negative (last, after every sample the program takes: a derivative after a discard is not uniform).
    pub clip_discard: Option<ClipVaryings>,
    /// Each sampler heap (an array of samplers indexed at run time, WebGPU's binding arrays) as one sampler: every
    /// index reads the same sampler, so a program whose samplers differ by index is not drawn as written (noted).
    pub single_samplers: bool,
}

/// A program's WGSL for a [`Pipeline`], and where the pipeline finds what the text holds.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Written {
    /// The WGSL source.
    pub text: String,
    /// The group and binding of every resource of the program in the text.
    pub bindings: BTreeMap<ResourceId, (u32, u32)>,
    /// A vertex program's clip distances as varyings, when [`Pipeline::clip_varyings`] made them.
    pub clip: Option<ClipVaryings>,
    /// The first location after every one the text's outputs (a vertex program) or inputs (a pixel program) use.
    pub next_location: u32,
    /// What the text approximates of the program, each once.
    pub notes: Vec<String>,
}

/// The program as WGSL for `pipeline` ([`Pipeline`]). The program is validated first and refused as
/// [`super::wgsl`] refuses it; a pipeline it cannot meet (a resource that is not the program's, two resources at
/// one binding, a link or clip option for a stage it does not apply to, a consumer input with no output) is an
/// [`Error::Pipeline`].
pub fn wgsl_for(program: &Program, pipeline: &Pipeline) -> Result<Written, Error> {
    super::writable(program)?;
    program.validated()?;
    let mut module = program.module.clone();
    let mut notes = Vec::new();
    rebind(program, &mut module, &pipeline.bindings)?;
    if pipeline.single_samplers {
        let heaps = single_samplers(&mut module);
        if heaps > 0 {
            // A heap written as one sampler leaves its binding-array type in the module, and the writer declares
            // `enable wgpu_binding_array;` for every binding-array type there, used or not: a WGSL front end that does
            // not know the extension then refuses a program that has no binding array. Drop the unused types. Every
            // global, function and named type stays in its place, so the program's handles hold.
            naga::compact::compact(&mut module, naga::compact::KeepUnused::Yes);
            notes.push(format!(
                "{heaps} sampler heap{} written as one sampler: every index reads the same sampler",
                if heaps == 1 { "" } else { "s" }
            ));
        }
    }
    let io = entry_io(&program.interface).map_err(Error::Invalid)?;
    let vertex = program.stage == Stage::Vertex;
    if !vertex && (pipeline.feeds.is_some() || pipeline.clip_varyings) {
        return Err(Error::Pipeline(format!(
            "a {:?} program feeds no consumer and has no clip distances to carry",
            program.stage
        )));
    }
    if program.stage != Stage::Pixel && pipeline.clip_discard.is_some() {
        return Err(Error::Pipeline(format!(
            "a {:?} program does not discard by clip distances",
            program.stage
        )));
    }
    let (clip, next_location) = if vertex {
        outputs(program, &io, &mut module, pipeline, &mut notes)?
    } else {
        let next = next_after(io.arguments.iter().map(|a| &a.binding));
        match pipeline.clip_discard {
            Some(clips) => (None, discard_clipped(&io, &mut module, clips, next)?),
            None => (None, next),
        }
    };
    let info = module_info(&module).map_err(|e| Error::Pipeline(format!("the lowered module: {e}")))?;
    let text = naga::back::wgsl::write_string(&module, &info, naga::back::wgsl::WriterFlags::empty())
        .map_err(|e| Error::Unsupported {
            writer: "wgsl",
            detail: e.to_string(),
        })?;
    let bindings = program
        .bindings
        .iter()
        .filter_map(|(id, g)| {
            let b = module.global_variables[*g].binding.as_ref()?;
            Some((*id, (b.group, b.binding)))
        })
        .collect();
    Ok(Written {
        text,
        bindings,
        clip,
        next_location,
        notes,
    })
}

/// A scalar kind as a note names it.
fn scalar_word(scalar: ScalarType) -> &'static str {
    match scalar {
        ScalarType::Float => "float",
        ScalarType::Uint => "uint",
        ScalarType::Sint => "int",
        ScalarType::Bool => "bool",
        ScalarType::Double => "double",
    }
}

/// An arena position as the u32 naga numbers them by (an arena of 2^32 expressions is more memory than a machine has).
fn arena_index(position: usize) -> u32 {
    u32::try_from(position).unwrap_or(u32::MAX)
}

/// The first location after the ones `bindings` use (0 when they use none).
fn next_after<'b>(bindings: impl Iterator<Item = &'b Binding>) -> u32 {
    bindings
        .filter_map(|b| match b {
            Binding::Location { location, .. } => Some(location.saturating_add(1)),
            Binding::BuiltIn(_) => None,
        })
        .max()
        .unwrap_or(0)
}

/// Each resource of `bindings` at its group and binding; two resources at one place are refused.
fn rebind(
    program: &Program,
    module: &mut naga::Module,
    bindings: &BTreeMap<ResourceId, (u32, u32)>,
) -> Result<(), Error> {
    for (id, &(group, binding)) in bindings {
        let g = program
            .global(*id)
            .ok_or_else(|| Error::Pipeline(format!("resource {} is not one of the program's", id.0)))?;
        module.global_variables[g].binding = Some(ResourceBinding { group, binding });
    }
    let mut taken: BTreeMap<(u32, u32), Option<String>> = BTreeMap::new();
    for (_, v) in module.global_variables.iter() {
        let Some(b) = &v.binding else { continue };
        if let Some(other) = taken.insert((b.group, b.binding), v.name.clone()) {
            return Err(Error::Pipeline(format!(
                "{} and {} are both at group {} binding {}",
                other.as_deref().unwrap_or("a global"),
                v.name.as_deref().unwrap_or("a global"),
                b.group,
                b.binding
            )));
        }
    }
    Ok(())
}

/// Each global that is an array of samplers made one sampler, every access to it the sampler itself. Returns how
/// many there were.
fn single_samplers(module: &mut naga::Module) -> usize {
    let heaps: BTreeMap<Handle<naga::GlobalVariable>, Handle<Type>> = module
        .global_variables
        .iter()
        .filter_map(|(g, v)| match module.types[v.ty].inner {
            TypeInner::BindingArray { base, .. }
                if matches!(module.types[base].inner, TypeInner::Sampler { .. }) =>
            {
                Some((g, base))
            }
            _ => None,
        })
        .collect();
    if heaps.is_empty() {
        return 0;
    }
    for (g, base) in &heaps {
        module.global_variables[*g].ty = *base;
    }
    let functions = module
        .functions
        .iter_mut()
        .map(|(_, f)| f)
        .chain(module.entry_points.iter_mut().map(|e| &mut e.function));
    for function in functions {
        let accesses: Vec<(Handle<Expression>, Handle<Expression>)> = function
            .expressions
            .iter()
            .filter_map(|(h, e)| match e {
                Expression::Access { base, .. } | Expression::AccessIndex { base, .. } => matches!(
                    function.expressions[*base],
                    Expression::GlobalVariable(g) if heaps.contains_key(&g)
                )
                .then_some((h, *base)),
                _ => None,
            })
            .collect();
        if accesses.is_empty() {
            continue;
        }
        // an access becomes the global it accessed: a global is no emitted expression, so it leaves its emit range
        let mut flattened = BTreeSet::new();
        for (access, base) in accesses {
            function.expressions[access] = function.expressions[base].clone();
            function.named_expressions.shift_remove(&access);
            flattened.insert(access);
        }
        let body = std::mem::take(&mut function.body);
        function.body = unemit(body, &flattened, &function.expressions);
    }
    heaps.len()
}

/// `block` with the `removed` expressions left out of its emit ranges, in nested blocks too.
fn unemit(block: Block, removed: &BTreeSet<Handle<Expression>>, arena: &naga::Arena<Expression>) -> Block {
    let removed_index: BTreeSet<u32> = removed.iter().map(|h| arena_index(h.index())).collect();
    let nested = |b: Block| unemit(b, removed, arena);
    let mut out = Block::with_capacity(block.len());
    for (statement, span) in block.span_into_iter() {
        match statement {
            Statement::Emit(range) => {
                // the range in runs between the removed expressions
                let mut start = None;
                let indices = range.index_range();
                for i in indices.clone().chain([indices.end]) {
                    let kept = i < indices.end && !removed_index.contains(&i);
                    match (kept, start) {
                        (true, None) => start = Some(i),
                        (false, Some(s)) => {
                            out.push(Statement::Emit(naga::Range::from_index_range(s..i, arena)), span);
                            start = None;
                        }
                        _ => {}
                    }
                }
            }
            Statement::Block(b) => out.push(Statement::Block(nested(b)), span),
            Statement::If {
                condition,
                accept,
                reject,
            } => out.push(
                Statement::If {
                    condition,
                    accept: nested(accept),
                    reject: nested(reject),
                },
                span,
            ),
            Statement::Switch { selector, cases } => out.push(
                Statement::Switch {
                    selector,
                    cases: cases
                        .into_iter()
                        .map(|c| naga::SwitchCase {
                            body: nested(c.body),
                            ..c
                        })
                        .collect(),
                },
                span,
            ),
            Statement::Loop {
                body,
                continuing,
                break_if,
            } => out.push(
                Statement::Loop {
                    body: nested(body),
                    continuing: nested(continuing),
                    break_if,
                },
                span,
            ),
            other => out.push(other, span),
        }
    }
    out
}

/// Whether two labels are one semantic, as Direct3D links stages: the name without case, and the index.
fn same_label(a: &Label, b: &Label) -> bool {
    a.index == b.index && a.name.eq_ignore_ascii_case(&b.name)
}

/// A vertex program's result bindings for `pipeline` (its consumer's locations, its clip distances as varyings),
/// the result structure rebuilt with them and every return made of it. Returns the clip varyings and the first location
/// after the outputs'.
fn outputs(
    program: &Program,
    io: &EntryIo,
    module: &mut naga::Module,
    pipeline: &Pipeline,
    notes: &mut Vec<String>,
) -> Result<(Option<ClipVaryings>, u32), Error> {
    let mut bindings: Vec<Binding> = io.results.iter().map(|r| r.binding.clone()).collect();
    // the output's own value and the one its consumer reads it as, where they differ
    let retyped: Vec<Option<(Value, Value)>> = match pipeline.feeds {
        Some(consumer) => link(program, io, consumer, &mut bindings)?,
        None => vec![None; bindings.len()],
    };
    let padded = retyped
        .iter()
        .flatten()
        .filter(|(from, to)| to.width > from.width)
        .count();
    if padded > 0 {
        notes.push(format!(
            "{padded} output{} read by the consumer with more lanes than written: the lanes past them are 0 (Direct3D \
             leaves them undefined)",
            if padded == 1 { "" } else { "s" }
        ));
    }
    // the other retypes: fewer lanes than written (the output's first ones are passed on), and another scalar kind (the
    // same bits)
    let narrowed = retyped
        .iter()
        .flatten()
        .filter(|(from, to)| to.width < from.width)
        .count();
    if narrowed > 0 {
        notes.push(format!(
            "{narrowed} output{} read by the consumer with fewer lanes than written: only the first lanes are passed on",
            if narrowed == 1 { "" } else { "s" }
        ));
    }
    let mut kinds: BTreeMap<(ScalarType, ScalarType), usize> = BTreeMap::new();
    for (from, to) in retyped.iter().flatten() {
        if from.scalar != to.scalar {
            let count = kinds.entry((from.scalar, to.scalar)).or_default();
            *count = count.saturating_add(1);
        }
    }
    for ((from, to), n) in kinds {
        notes.push(format!(
            "{n} output{} written as {} and read by the consumer as {}: the same bits, reinterpreted (Direct3D links bits)",
            if n == 1 { "" } else { "s" },
            scalar_word(from),
            scalar_word(to)
        ));
    }
    let mut next = next_after(bindings.iter());
    let clip_member = io
        .results
        .iter()
        .position(|r| matches!(r.ty, IoType::ClipDistances(_)))
        .filter(|_| pipeline.clip_varyings);
    let clip = clip_member.map(|k| {
        let count = match io.results.get(k).map(|r| r.ty) {
            Some(IoType::ClipDistances(count)) => count,
            _ => 0,
        };
        let clips = ClipVaryings { first: next, count };
        next = next.saturating_add(count);
        clips
    });
    let unchanged = clip.is_none()
        && retyped.iter().all(Option::is_none)
        && bindings.iter().zip(&io.results).all(|(b, r)| *b == r.binding);
    if unchanged {
        return Ok((None, next));
    }
    let entry = module
        .entry_points
        .first()
        .ok_or_else(|| Error::Invalid("no entry point".into()))?;
    let old = entry
        .function
        .result
        .as_ref()
        .ok_or_else(|| Error::Invalid("a vertex program with no result".into()))?
        .ty;
    let TypeInner::Struct { members, span } = module.types[old].inner.clone() else {
        return Err(Error::Invalid(
            "a vertex program's result is not a structure".into(),
        ));
    };
    if members.len() != bindings.len() {
        return Err(Error::Invalid(format!(
            "the result structure has {} members, the interface {}",
            members.len(),
            bindings.len()
        )));
    }
    let f32_ty = module.types.insert(
        Type {
            name: None,
            inner: TypeInner::Scalar(naga::Scalar::F32),
        },
        Span::UNDEFINED,
    );
    // the types and zeros a retyped output is made with: its new type, and a vector of its own scalar at the new
    // width where it is padded (a literal is no emitted expression: made here, outside the returns' emit ranges)
    let mut conversions: Vec<Option<Conversion>> = Vec::with_capacity(retyped.len());
    for change in &retyped {
        conversions.push(match change {
            None => None,
            Some((from, to)) => {
                let (from_scalar, to_scalar) = (naga_scalar(from.scalar)?, naga_scalar(to.scalar)?);
                let width = |v: &Value| {
                    Width::try_from(v.width).map_err(|e| Error::Pipeline(format!("a linked value of {e}")))
                };
                let (from_width, to_width) = (width(from)?, width(to)?);
                let ty = value_type(module, to_scalar, to_width);
                let padded = (to_width > from_width).then(|| value_type(module, from_scalar, to_width));
                Some(Conversion {
                    from: *from,
                    to: *to,
                    from_width,
                    to_width,
                    ty,
                    padded,
                    to_kind: to_scalar.kind,
                    zero: None,
                })
            }
        });
    }
    {
        let entry = module
            .entry_points
            .first_mut()
            .ok_or_else(|| Error::Invalid("no entry point".into()))?;
        for c in conversions.iter_mut().flatten() {
            if c.padded.is_some() {
                let literal = match c.from.scalar {
                    ScalarType::Float => naga::Literal::F32(0.0),
                    ScalarType::Uint => naga::Literal::U32(0),
                    ScalarType::Sint => naga::Literal::I32(0),
                    ScalarType::Bool | ScalarType::Double => unreachable!("refused by naga_scalar"),
                };
                c.zero = Some(
                    entry
                        .function
                        .expressions
                        .append(Expression::Literal(literal), Span::UNDEFINED),
                );
            }
        }
    }
    let member_count = members.len();
    let mut new_members = Vec::with_capacity(member_count);
    for (k, (member, binding)) in members.into_iter().zip(bindings).enumerate() {
        match clip {
            Some(clips) if Some(k) == clip_member => {
                // the array's elements, at its offsets
                for j in 0..clips.count {
                    new_members.push(StructMember {
                        name: Some(format!("clip_distance{j}")),
                        ty: f32_ty,
                        binding: Some(Binding::Location {
                            location: clips.first.saturating_add(j),
                            interpolation: Some(Interpolation::Perspective),
                            sampling: None,
                            blend_src: None,
                            per_primitive: false,
                        }),
                        offset: member.offset.saturating_add(j.saturating_mul(4)),
                    });
                }
            }
            _ => new_members.push(StructMember {
                binding: Some(binding),
                ty: conversions
                    .get(k)
                    .and_then(Option::as_ref)
                    .map_or(member.ty, |c| c.ty),
                ..member
            }),
        }
    }
    let name = module.types[old].name.clone();
    let new = module.types.insert(
        Type {
            name: name.clone(),
            inner: TypeInner::Struct {
                members: new_members,
                span,
            },
        },
        Span::UNDEFINED,
    );
    // the old structure stays as the value each return is made of, without its bindings: a built-in it binds (the
    // clip distances) would otherwise still be in the module, and in the text's `enable`s
    let TypeInner::Struct { members, span } = module.types[old].inner.clone() else {
        unreachable!("checked above")
    };
    let plain = Type {
        name,
        inner: TypeInner::Struct {
            members: members
                .into_iter()
                .map(|m| StructMember { binding: None, ..m })
                .collect(),
            span,
        },
    };
    if module.types.get(&plain).is_some() {
        return Err(Error::Pipeline(
            "the result structure without its bindings is already a type of the module".into(),
        ));
    }
    module.types.replace(old, plain);
    let entry = module
        .entry_points
        .first_mut()
        .ok_or_else(|| Error::Invalid("no entry point".into()))?;
    if let Some(result) = entry.function.result.as_mut() {
        result.ty = new;
    }
    // each return's value, member by member (each clip distance an element of the array), as the new structure
    let function = &mut entry.function;
    let body = std::mem::take(&mut function.body);
    function.body = returns(body, &mut function.expressions, &mut |value, expressions| {
        // a function with a result returns a value (the program validated)
        let Some(value) = value else {
            return (Vec::new(), None);
        };
        let start = expressions.len();
        let mut components = Vec::new();
        for (k, conversion) in conversions.iter().enumerate() {
            let part = expressions.append(
                Expression::AccessIndex {
                    base: value,
                    index: arena_index(k),
                },
                Span::UNDEFINED,
            );
            match clip {
                Some(clips) if Some(k) == clip_member => {
                    for j in 0..clips.count {
                        components.push(
                            expressions
                                .append(Expression::AccessIndex { base: part, index: j }, Span::UNDEFINED),
                        );
                    }
                }
                _ => components.push(match conversion {
                    Some(c) => c.apply(part, expressions),
                    None => part,
                }),
            }
        }
        let compose = expressions.append(Expression::Compose { ty: new, components }, Span::UNDEFINED);
        let emitted =
            naga::Range::from_index_range(arena_index(start)..arena_index(expressions.len()), expressions);
        (vec![Statement::Emit(emitted)], Some(compose))
    });
    Ok((clip, next))
}

/// How an output becomes the value its consumer reads (see [`Pipeline::feeds`]).
#[derive(Clone, Copy, Debug)]
struct Conversion {
    from: Value,
    to: Value,
    /// The output's width and the consumer's.
    from_width: Width,
    to_width: Width,
    /// The consumer's type.
    ty: Handle<Type>,
    /// A vector of the output's scalar at the consumer's width, where that is wider.
    padded: Option<Handle<Type>>,
    to_kind: naga::ScalarKind,
    /// The zero of the output's scalar, where it is padded.
    zero: Option<Handle<Expression>>,
}

impl Conversion {
    /// `part` (the output's value) as the consumer's: its first lanes, or padded with zeros, then the same bits as the
    /// consumer's scalar.
    fn apply(
        &self,
        part: Handle<Expression>,
        expressions: &mut naga::Arena<Expression>,
    ) -> Handle<Expression> {
        let mut add = |e: Expression| expressions.append(e, Span::UNDEFINED);
        let (from, to) = (self.from_width, self.to_width);
        let mut value = part;
        if to < from {
            value = if let Some(size) = to.vector_size() {
                add(Expression::Swizzle {
                    size,
                    vector: value,
                    pattern: [
                        naga::SwizzleComponent::X,
                        naga::SwizzleComponent::Y,
                        naga::SwizzleComponent::Z,
                        naga::SwizzleComponent::W,
                    ],
                })
            } else {
                add(Expression::AccessIndex {
                    base: value,
                    index: 0,
                })
            };
        } else if to > from
            && let (Some(ty), Some(zero)) = (self.padded, self.zero)
        {
            let mut components: Vec<Handle<Expression>> = if from == Width::One {
                vec![value]
            } else {
                (0..u32::from(from))
                    .map(|i| {
                        add(Expression::AccessIndex {
                            base: value,
                            index: i,
                        })
                    })
                    .collect()
            };
            components.resize(usize::from(to), zero);
            value = add(Expression::Compose { ty, components });
        }
        if self.from.scalar != self.to.scalar {
            value = add(Expression::As {
                expr: value,
                kind: self.to_kind,
                convert: None,
            });
        }
        value
    }
}

/// The naga scalar of a linked value; a boolean or 64-bit one is refused (its bits are not one 32-bit lane).
fn naga_scalar(s: ScalarType) -> Result<naga::Scalar, Error> {
    match s {
        ScalarType::Float => Ok(naga::Scalar::F32),
        ScalarType::Uint => Ok(naga::Scalar::U32),
        ScalarType::Sint => Ok(naga::Scalar::I32),
        ScalarType::Bool | ScalarType::Double => Err(Error::Pipeline(format!(
            "a {s:?} output read as another value: its bits are not a 32-bit lane"
        ))),
    }
}

/// The type of `width` lanes of `scalar`: the scalar itself for one.
fn value_type(module: &mut naga::Module, scalar: naga::Scalar, width: Width) -> Handle<Type> {
    let inner = match width.vector_size() {
        None => TypeInner::Scalar(scalar),
        Some(size) => TypeInner::Vector { size, scalar },
    };
    module.types.insert(Type { name: None, inner }, Span::UNDEFINED)
}

/// Link a vertex program's result `bindings` to `consumer`'s inputs (see [`Pipeline::feeds`]). Returns, per result
/// member, its value and the one the consumer reads it as, where they differ.
fn link(
    program: &Program,
    io: &EntryIo,
    consumer: &Interface,
    bindings: &mut [Binding],
) -> Result<Vec<Option<(Value, Value)>>, Error> {
    let mut retyped = vec![None; bindings.len()];
    let wanted = entry_io(consumer).map_err(|e| Error::Pipeline(format!("the consumer: {e}")))?;
    let mut consumed = vec![false; bindings.len()];
    let mut next = 0u32;
    for argument in &wanted.arguments {
        let Binding::Location { location, .. } = argument.binding else {
            continue;
        };
        next = next.max(location.saturating_add(1));
        let label = &argument
            .varyings
            .first()
            .and_then(|&v| consumer.inputs.get(v))
            .ok_or_else(|| {
                Error::Pipeline(format!("the consumer's input {} names no varying", argument.name))
            })?
            .label;
        let k = io
            .results
            .iter()
            .position(|r| {
                matches!(r.binding, Binding::Location { .. })
                    && r.varyings
                        .first()
                        .and_then(|&v| program.interface.outputs.get(v))
                        .is_some_and(|output| same_label(&output.label, label))
            })
            .ok_or_else(|| {
                let written: Vec<String> = io
                    .results
                    .iter()
                    .filter(|r| matches!(r.binding, Binding::Location { .. }))
                    .map(|r| r.name.clone())
                    .collect();
                Error::Pipeline(format!(
                    "the consumer reads {}{}, which the vertex program does not write (it writes {})",
                    label.name,
                    label.index,
                    written.join(", ")
                ))
            })?;
        if let Some(binding) = bindings.get_mut(k) {
            *binding = argument.binding.clone();
        }
        if let Some(taken) = consumed.get_mut(k) {
            *taken = true;
        }
        if let (Some(IoType::Value(from)), IoType::Value(to)) = (io.results.get(k).map(|r| r.ty), argument.ty)
            && from != to
        {
            if from.scalar != to.scalar {
                naga_scalar(from.scalar)?;
                naga_scalar(to.scalar)?;
            }
            if let Some(slot) = retyped.get_mut(k) {
                *slot = Some((from, to));
            }
        }
    }
    for (binding, consumed) in bindings.iter_mut().zip(consumed) {
        if let (Binding::Location { location, .. }, false) = (binding, consumed) {
            *location = next;
            next = next.saturating_add(1);
        }
    }
    Ok(retyped)
}

/// A pixel program's inputs for `clips` and a discard before each return where one is negative. `next` is the first
/// location after the program's own inputs; the clip varyings must not be below it. Returns the first location after
/// them.
fn discard_clipped(
    io: &EntryIo,
    module: &mut naga::Module,
    clips: ClipVaryings,
    next: u32,
) -> Result<u32, Error> {
    if clips.first < next {
        return Err(Error::Pipeline(format!(
            "the clip varyings at {} meet the pixel program's own inputs (locations below {next})",
            clips.first
        )));
    }
    let f32_ty = module.types.insert(
        Type {
            name: None,
            inner: TypeInner::Scalar(naga::Scalar::F32),
        },
        Span::UNDEFINED,
    );
    let entry = module
        .entry_points
        .first_mut()
        .ok_or_else(|| Error::Invalid("no entry point".into()))?;
    let function = &mut entry.function;
    debug_assert_eq!(function.arguments.len(), io.arguments.len());
    let mut distances = Vec::with_capacity(clips.count.min(64) as usize);
    for j in 0..clips.count {
        let index = arena_index(function.arguments.len());
        function.arguments.push(naga::FunctionArgument {
            name: Some(format!("clip_distance{j}")),
            ty: f32_ty,
            binding: Some(Binding::Location {
                location: clips.first.saturating_add(j),
                interpolation: Some(Interpolation::Perspective),
                sampling: None,
                blend_src: None,
                per_primitive: false,
            }),
        });
        distances.push(
            function
                .expressions
                .append(Expression::FunctionArgument(index), Span::UNDEFINED),
        );
    }
    let zero = function
        .expressions
        .append(Expression::Literal(naga::Literal::F32(0.0)), Span::UNDEFINED);
    // the test, made afresh where it is used: an expression is emitted once in its scope
    let test = |expressions: &mut naga::Arena<Expression>| -> Vec<Statement> {
        let start = expressions.len();
        let mut condition = None;
        for &d in &distances {
            let below = expressions.append(
                Expression::Binary {
                    op: naga::BinaryOperator::Less,
                    left: d,
                    right: zero,
                },
                Span::UNDEFINED,
            );
            condition = Some(match condition {
                None => below,
                Some(earlier) => expressions.append(
                    Expression::Binary {
                        op: naga::BinaryOperator::LogicalOr,
                        left: earlier,
                        right: below,
                    },
                    Span::UNDEFINED,
                ),
            });
        }
        let Some(condition) = condition else {
            return Vec::new();
        };
        let emitted =
            naga::Range::from_index_range(arena_index(start)..arena_index(expressions.len()), expressions);
        vec![
            Statement::Emit(emitted),
            Statement::If {
                condition,
                accept: Block::from_vec(vec![Statement::Kill]),
                reject: Block::new(),
            },
        ]
    };
    let body = std::mem::take(&mut function.body);
    let mut body = returns(body, &mut function.expressions, &mut |value, expressions| {
        (test(expressions), value)
    });
    // a program with no result may end without a return: the end is one
    if function.result.is_none() && !matches!(body.last(), Some(Statement::Return { .. })) {
        for statement in test(&mut function.expressions) {
            body.push(statement, Span::UNDEFINED);
        }
    }
    function.body = body;
    Ok(clips.first.saturating_add(clips.count))
}

/// `block` with each return (in nested blocks too) preceded by the statements `at` makes and returning the value it
/// gives, from the value it returned.
#[allow(clippy::type_complexity)]
fn returns(
    block: Block,
    expressions: &mut naga::Arena<Expression>,
    at: &mut dyn FnMut(
        Option<Handle<Expression>>,
        &mut naga::Arena<Expression>,
    ) -> (Vec<Statement>, Option<Handle<Expression>>),
) -> Block {
    let mut out = Block::with_capacity(block.len());
    for (statement, span) in block.span_into_iter() {
        match statement {
            Statement::Return { value } => {
                let (before, value) = at(value, expressions);
                for s in before {
                    out.push(s, span);
                }
                out.push(Statement::Return { value }, span);
            }
            Statement::Block(b) => out.push(Statement::Block(returns(b, expressions, at)), span),
            Statement::If {
                condition,
                accept,
                reject,
            } => {
                let accept = returns(accept, expressions, at);
                let reject = returns(reject, expressions, at);
                out.push(
                    Statement::If {
                        condition,
                        accept,
                        reject,
                    },
                    span,
                );
            }
            Statement::Switch { selector, cases } => {
                let cases = cases
                    .into_iter()
                    .map(|c| naga::SwitchCase {
                        body: returns(c.body, expressions, at),
                        ..c
                    })
                    .collect();
                out.push(Statement::Switch { selector, cases }, span);
            }
            Statement::Loop {
                body,
                continuing,
                break_if,
            } => {
                let body = returns(body, expressions, at);
                let continuing = returns(continuing, expressions, at);
                out.push(
                    Statement::Loop {
                        body,
                        continuing,
                        break_if,
                    },
                    span,
                );
            }
            other => out.push(other, span),
        }
    }
    out
}