rucc_ir/

parse.rs

//! The parser: text back into a module.
//!
//! Design: `spec/08-ir.md` section 8.8.
//!
//! The other half of the round trip. What the printer wrote, this reads, and printing the
//! result gives the same bytes back. That is what makes the IR testable without the front end,
//! what makes a dump worth trusting, and what lets a fuzzer make IR directly.
//!
//! # Forward references
//!
//! A branch names a block that has not been read yet, and, less obviously, an instruction can
//! use a value defined further down the text: the blocks are printed in layout order, and
//! layout order is not required to be an order in which every definition comes before its uses.
//!
//! Blocks are easy, because a block is an index and the index is the number in the text. Values
//! are not, because creating an instruction needs the types of the values it produces, and for
//! most opcodes that type is the type of the first operand, which may be one of the values that
//! have not been read yet.
//!
//! So a function is read in two passes. The first turns the text into a list of blocks holding
//! instructions whose operands are still just the numbers they were written as. The second
//! works out the type of every value and then builds the function. Working the types out
//! terminates because the only cycles in the definition graph run through block parameters, and
//! a block parameter has its type written at the block.
//!
//! # Numbering
//!
//! Values are numbered from zero in print order and so are blocks, so building the function in
//! print order gives every value and every block the index its number in the text says. The
//! parser checks that as it goes rather than assuming it, which is what catches a text whose
//! numbering does not add up.

use std::fmt;

use rucc_base::float::Format;
use rucc_base::{Idx, Interner, Symbol};
use rucc_diag::Span;
use rucc_target::{Slot, TargetInfo};
use rucc_tuple::TargetTuple;

use crate::attrs::{AttrSet, Attrs, FpContract};
use crate::func::Func;
use crate::inst::{
    Abi, AsmInfo, Block, BlockCall, CallInfo, Imm, Inst, InstData, MemInfo, Meta, MetaNode, Param,
    PlaneNode, Restrict, Signature, SwitchInfo, TbaaNode, VaInfo, Value,
};
use crate::module::{
    Alias, AliasKind, DataLayout, Datum, Global, Linkage, Module, Reloc, TlsModel, Visibility,
};
use crate::{
    Bounds, Extra, ExtraKind, FORMAT_VERSION, Facts, Flags, FloatPred, IntPred, MemOrder, Opcode,
    Owner, RmwOp, StorageClass, Type,
};

/// Why a module could not be read.
///
/// One error and then nothing, rather than a list. A malformed IR dump is a bug in whatever
/// wrote it or a file somebody edited by hand, and in both cases the first thing that does not
/// add up is the thing worth reporting.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ParseError {
    /// Which line of the text, counting from one.
    pub line: u32,
    /// What was wrong with it.
    pub message: String,
}

impl fmt::Display for ParseError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "line {}: {}", self.line, self.message)
    }
}

impl std::error::Error for ParseError {}

/// Reads a module from the text the printer writes.
///
/// Names are interned into `names`, which is the same interner the printer will be given when
/// the module is written back out.
///
/// # Errors
///
/// Gives back the first thing in the text that does not add up, with the line it is on.
pub fn parse(text: &str, names: &mut Interner) -> Result<Module, ParseError> {
    Parser::new(text, names).module()
}

/// Reading one text.
struct Parser<'a, 'n> {
    text: &'a str,
    pos: usize,
    line: u32,
    names: &'n mut Interner,
    /// The highest metadata node any instruction referred to, so that a reference to one that
    /// is never defined is caught rather than left as an index into nothing.
    meta_used: Option<(u32, u32)>,
}

/// A block, read but not yet built.
struct PendingBlock<'a> {
    params: Vec<(u32, Type)>,
    insts: Vec<PendingInst<'a>>,
}

/// What is known about one value, read but not yet built. Every value is still its number.
struct PendingFacts {
    line: u32,
    value: u32,
    bounds: Option<(u32, u32)>,
    init: Option<u64>,
    align: Option<u32>,
    live: bool,
}

impl PendingFacts {
    fn new(line: u32, value: u32) -> Self {
        Self { line, value, bounds: None, init: None, align: None, live: false }
    }
}

/// An instruction, read but not yet built. Every value is still the number it was written as.
struct PendingInst<'a> {
    opcode: Opcode,
    flags: Flags,
    results: Vec<u32>,
    /// The types written after the opcode, which is none when the operands say them.
    written: Vec<Type>,
    args: Vec<u32>,
    /// The version of memory it reads, written as `[mem %3]` at the end of the line. It is kept
    /// here as well as pushed onto `args`, because whether an instruction produces a new version
    /// is not something the text says twice: it follows from being on the chain and writing.
    mem: Option<u32>,
    extra: PendingExtra<'a>,
    line: u32,
}

/// A branch target, read but not yet built.
struct PendingCall {
    block: u32,
    args: Vec<u32>,
}

/// The payload of an instruction, read but not yet built.
enum PendingExtra<'a> {
    None,
    /// The text of the constant, which cannot be read until the result type is known.
    Imm(&'a str),
    Symbol(Symbol),
    IntPred(IntPred),
    FloatPred(FloatPred),
    Mem(MemInfo),
    /// The access, and the slots the object travelled in, which is empty for one that did not
    /// travel in registers.
    VaObject(MemInfo, Vec<Slot>),
    Rmw(RmwOp, MemInfo),
    Order(MemOrder),
    Class(StorageClass),
    Owner(Owner),
    Node(Meta),
    Reason(Symbol),
    Targets(Vec<PendingCall>),
    Call {
        callee: Option<Symbol>,
        signature: Signature,
        /// One entry for each argument, whether or not the signature names it, since the
        /// signature is written after the arguments and is not known yet.
        abis: Vec<Abi>,
    },
    Switch {
        targets: Vec<PendingCall>,
        cases: Vec<&'a str>,
    },
    Asm {
        template: Symbol,
        constraints: Symbol,
        clobbers: Symbol,
        targets: Vec<PendingCall>,
    },
}

impl<'a, 'n> Parser<'a, 'n> {
    fn new(text: &'a str, names: &'n mut Interner) -> Self {
        Parser { text, pos: 0, line: 1, names, meta_used: None }
    }

    // The whole module.

    fn module(mut self) -> Result<Module, ParseError> {
        let name = self.header_name()?;
        self.expect("; format ")?;
        let version = self.u32()?;
        if version != FORMAT_VERSION {
            return self.fail(format!(
                "this build reads format {FORMAT_VERSION} and the text says format {version}"
            ));
        }
        self.end_of_line()?;

        self.expect("target triple = ")?;
        let triple = self.quoted_str()?;
        let Ok(tuple) = triple.parse::<TargetTuple>() else {
            return self.fail(format!("`{triple}` is not a target triple"));
        };
        self.end_of_line()?;

        self.expect("target datalayout = ")?;
        let layout = self.quoted_str()?;
        let Some(datalayout) = DataLayout::parse(&layout) else {
            return self.fail(format!("`{layout}` is not a data layout"));
        };
        self.end_of_line()?;

        let name = self.names.intern(&name);
        let mut module = Module::new(name, &TargetInfo::for_tuple(tuple));
        module.datalayout = datalayout;

        loop {
            self.skip_blank_lines();
            if self.at_end() {
                break;
            }
            match self.peek_word() {
                "global" => self.global(&mut module)?,
                "alias" | "ifunc" => self.alias(&mut module)?,
                "func" => self.func(&mut module)?,
                _ if self.at("!") => self.meta(&mut module)?,
                other => return self.fail(format!("`{other}` does not start anything")),
            }
        }

        if let Some((used, line)) = self.meta_used {
            let count = module.counts().metadata as u32;
            if used >= count {
                self.line = line;
                return self.fail(format!("!{used} is used and never defined"));
            }
        }
        Ok(module)
    }

    /// The `; ModuleID = 'name'` line, whose name is not quoted the way everything else is.
    fn header_name(&mut self) -> Result<String, ParseError> {
        self.expect("; ModuleID = '")?;
        let start = self.pos;
        let Some(end) = self.text[start..].find('\'') else {
            return self.fail("the module name is not closed");
        };
        let name = self.text[start..start + end].to_string();
        self.pos = start + end + 1;
        self.end_of_line()?;
        Ok(name)
    }

    // Globals, aliases and metadata.

    fn global(&mut self, module: &mut Module) -> Result<(), ParseError> {
        self.expect("global")?;
        let name = self.symbol()?;
        self.expect(":")?;

        let mut global = Global::new(name, 0, 1);
        if self.eat_word("bytes") {
            global.size = self.u64()?;
            if self.eat("=") {
                self.expect("{")?;
                let mut data = Vec::new();
                // The brace is looked for before a piece is asked for, because an image with
                // nothing in it is a thing a zero sized object has and asking for a piece first
                // met the closing brace and called it a type that does not exist.
                if !self.eat("}") {
                    loop {
                        data.push(self.datum(module)?);
                        if !self.eat(",") {
                            break;
                        }
                    }
                    self.expect("}")?;
                }
                global.init = Some(module.push_data(&data));
            }
        } else {
            let ty = self.ty()?;
            self.expect("=")?;
            let text = self.imm_text()?;
            let value = self.imm(text, ty)?;
            let datum = Datum::Scalar { ty, value: module.add_imm(value) };
            global.size = datum.size(module);
            global.init = Some(module.push_data(&[datum]));
        }

        while self.eat(",") {
            match self.word() {
                "align" => global.align = self.u32()?,
                "linkage" => {
                    global.linkage = self.parenthesised(Linkage::from_name, "a linkage")?
                }
                "visibility" => {
                    global.visibility =
                        self.parenthesised(Visibility::from_name, "a visibility")?;
                }
                "tls" => {
                    global.tls =
                        Some(self.parenthesised(TlsModel::from_name, "a thread-local model")?);
                }
                "constant" => global.constant = true,
                "section" => global.section = Some(self.symbol_from_string()?),
                other => return self.fail(format!("a global has no `{other}`")),
            }
        }
        self.end_of_line()?;
        module.add_global(global);
        Ok(())
    }

    /// One piece of a global's image.
    fn datum(&mut self, module: &mut Module) -> Result<Datum, ParseError> {
        match self.peek_word() {
            "zero" => {
                self.expect("zero")?;
                Ok(Datum::Zero(self.u64()?))
            }
            "bytes" => {
                self.expect("bytes")?;
                let bytes = self.string()?;
                Ok(Datum::Bytes(module.push_bytes(&bytes)))
            }
            "addr" => {
                self.expect("addr")?;
                self.expect(".")?;
                let size = self.u32()?;
                let symbol = self.symbol()?;
                let addend = if self.eat("+") {
                    self.i64()?
                } else if self.eat("-") {
                    let amount = self.i64()?;
                    match amount.checked_neg() {
                        Some(negated) => negated,
                        None => return self.fail("that offset has no negative"),
                    }
                } else {
                    0
                };
                Ok(Datum::Addr(module.add_reloc(Reloc { symbol, addend, size })))
            }
            _ => {
                let ty = self.ty()?;
                let text = self.imm_text()?;
                let value = self.imm(text, ty)?;
                Ok(Datum::Scalar { ty, value: module.add_imm(value) })
            }
        }
    }

    fn alias(&mut self, module: &mut Module) -> Result<(), ParseError> {
        let word = self.word();
        let Some(kind) = AliasKind::from_name(word) else {
            return self.fail(format!("`{word}` is not a kind of alias"));
        };
        let name = self.symbol()?;
        self.expect("=")?;
        let target = self.symbol()?;
        let mut alias = Alias::new(name, target);
        alias.kind = kind;
        while self.eat(",") {
            match self.word() {
                "linkage" => alias.linkage = self.parenthesised(Linkage::from_name, "a linkage")?,
                "visibility" => {
                    alias.visibility = self.parenthesised(Visibility::from_name, "a visibility")?;
                }
                other => return self.fail(format!("an alias has no `{other}`")),
            }
        }
        self.end_of_line()?;
        module.add_alias(alias);
        Ok(())
    }

    fn meta(&mut self, module: &mut Module) -> Result<(), ParseError> {
        let index = self.meta_ref()?;
        let expected = module.counts().metadata as u32;
        if index.raw() != expected {
            return self.fail(format!("metadata is numbered in order and !{expected} comes next"));
        }
        self.expect("=")?;
        let node = match self.word() {
            "tbaa" => {
                let name = self.symbol_from_string()?;
                let mut node = TbaaNode { name, parent: None, offset: 0 };
                while self.eat(",") {
                    match self.word() {
                        "parent" => node.parent = Some(self.meta_ref()?),
                        "offset" => node.offset = self.u64()?,
                        other => return self.fail(format!("a metadata node has no `{other}`")),
                    }
                }
                MetaNode::Tbaa(node)
            }
            // A plane entry is one thing and not a list of fields, so it is written as that one
            // thing: the aliasing node of the type it is, or one of the three names document 09
            // section 9.1 gives the values that are not a type.
            "plane" => MetaNode::Plane(if self.peek_is("!") {
                PlaneNode::Type(self.meta_ref()?)
            } else {
                match self.word() {
                    "no_type" => PlaneNode::NoType,
                    "character" => PlaneNode::Character,
                    "pointer_slot" => {
                        let k = self.u32()?;
                        match u8::try_from(k) {
                            Ok(k) => PlaneNode::PointerSlot(k),
                            Err(_) => return self.fail(format!("no pointer has a byte {k}")),
                        }
                    }
                    other => return self.fail(format!("`{other}` is not a plane entry")),
                }
            }),
            other => return self.fail(format!("`{other}` is not a kind of metadata node")),
        };
        if node.points_at().is_some_and(|at| at.raw() >= index.raw()) {
            return self.fail("a metadata node names one that comes before it");
        }
        self.end_of_line()?;
        module.add_meta(node);
        Ok(())
    }

    // Functions.

    fn func(&mut self, module: &mut Module) -> Result<(), ParseError> {
        self.expect("func")?;
        let name = self.symbol()?;
        let signature = self.signature()?;
        let mut func = Func::new(name, signature);
        while self.eat(",") {
            match self.word() {
                "linkage" => func.linkage = self.parenthesised(Linkage::from_name, "a linkage")?,
                "visibility" => {
                    func.visibility = self.parenthesised(Visibility::from_name, "a visibility")?;
                }
                "attrs" => func.attrs = self.attrs()?,
                "section" => func.section = Some(self.symbol_from_string()?),
                other => return self.fail(format!("a function has no `{other}`")),
            }
        }
        if self.eat(";") {
            self.end_of_line()?;
            module.add_func(func);
            return Ok(());
        }
        self.expect("{")?;
        self.end_of_line()?;
        let (blocks, facts) = self.body()?;
        self.build(&mut func, &blocks, &facts)?;
        module.add_func(func);
        Ok(())
    }

    /// The parameter and result types, in parentheses and after an arrow.
    fn signature(&mut self) -> Result<Signature, ParseError> {
        self.expect("(")?;
        let mut signature = Signature::new();
        if !self.eat(")") {
            loop {
                if self.eat("...") {
                    signature.variadic = true;
                    break;
                }
                signature.params.push(self.param()?);
                if !self.eat(",") {
                    break;
                }
            }
            self.expect(")")?;
        }
        if self.eat("->") {
            if self.eat("(") {
                loop {
                    signature.returns.push(self.param()?);
                    if !self.eat(",") {
                        break;
                    }
                }
                self.expect(")")?;
            } else {
                signature.returns.push(self.param()?);
            }
        }
        Ok(signature)
    }

    /// One parameter: a type, and what the ABI asks of it when the text says anything.
    fn param(&mut self) -> Result<Param, ParseError> {
        let ty = self.ty()?;
        let abi = self.abi()?;
        Ok(Param { ty, abi })
    }

    /// What the ABI asks of a value, which is [`Abi::Plain`] when the text says nothing.
    fn abi(&mut self) -> Result<Abi, ParseError> {
        let abi = match self.peek_word() {
            "sext" => {
                self.word();
                Abi::Sext
            }
            "zext" => {
                self.word();
                Abi::Zext
            }
            word @ ("byval" | "sret") => {
                let indirect = word == "byval";
                self.word();
                self.expect("(")?;
                let size = self.u64()?;
                self.expect(",")?;
                self.expect("align")?;
                let align = self.u32()?;
                self.expect(")")?;
                if indirect { Abi::ByVal { size, align } } else { Abi::Sret { size, align } }
            }
            _ => Abi::Plain,
        };
        Ok(abi)
    }

    fn attrs(&mut self) -> Result<Attrs, ParseError> {
        self.expect("(")?;
        let mut attrs = Attrs::NONE;
        loop {
            let word = self.word();
            if self.eat("=") {
                let value = self.word();
                match word {
                    "fp_contract" => match FpContract::from_name(value) {
                        Some(contract) => attrs.fp_contract = contract,
                        None => return self.fail(format!("`{value}` is not a contraction")),
                    },
                    other => return self.fail(format!("`{other}` takes no value")),
                }
            } else {
                match AttrSet::from_name(word) {
                    Some(attr) => attrs.set |= attr,
                    None => return self.fail(format!("`{word}` is not an attribute")),
                }
            }
            if !self.eat(",") {
                break;
            }
        }
        self.expect(")")?;
        Ok(attrs)
    }

    /// The blocks of a function, up to the closing brace.
    fn body(&mut self) -> Result<(Vec<PendingBlock<'a>>, Vec<PendingFacts>), ParseError> {
        let mut blocks: Vec<PendingBlock<'a>> = Vec::new();
        let mut facts: Vec<PendingFacts> = Vec::new();
        loop {
            self.skip_blank_lines();
            if self.eat("}") {
                self.end_of_line()?;
                return Ok((blocks, facts));
            }
            if self.at_end() {
                return self.fail("the function is not closed");
            }
            if self.peek_word() == "facts" {
                // The facts come after the last block and are the last thing in the body, so
                // this reads all of them and then goes back round to the closing brace.
                self.word();
                self.expect(":")?;
                self.end_of_line()?;
                loop {
                    self.skip_blank_lines();
                    if !self.peek_is("%") {
                        break;
                    }
                    facts.push(self.fact_line()?);
                }
                continue;
            }
            if self.peek_word().starts_with("block") {
                let number = self.block_ref()?;
                if number as usize != blocks.len() {
                    return self.fail(format!(
                        "blocks are numbered in order and block{} comes next",
                        blocks.len()
                    ));
                }
                let mut params = Vec::new();
                if self.eat("(") {
                    loop {
                        let value = self.value_ref()?;
                        self.expect(":")?;
                        params.push((value, self.ty()?));
                        if !self.eat(",") {
                            break;
                        }
                    }
                    self.expect(")")?;
                }
                self.expect(":")?;
                self.end_of_line()?;
                blocks.push(PendingBlock { params, insts: Vec::new() });
                continue;
            }
            let inst = self.inst()?;
            match blocks.last_mut() {
                Some(block) => block.insts.push(inst),
                None => return self.fail("an instruction before any block"),
            }
        }
    }

    /// One line of the facts section: a value, and what is known about it.
    fn fact_line(&mut self) -> Result<PendingFacts, ParseError> {
        let line = self.line;
        let value = self.value_ref()?;
        self.expect("=")?;
        let mut facts = PendingFacts::new(line, value);
        loop {
            self.expect("!")?;
            let word = self.word();
            match word {
                "bounds" => {
                    self.expect("(")?;
                    let lo = self.value_ref()?;
                    self.expect(",")?;
                    let ext = self.value_ref()?;
                    self.expect(")")?;
                    facts.bounds = Some((lo, ext));
                }
                "live" => facts.live = true,
                "init" => {
                    self.expect("(")?;
                    facts.init = Some(self.u64()?);
                    self.expect(")")?;
                }
                "aligned" => {
                    self.expect("(")?;
                    facts.align = Some(self.u32()?);
                    self.expect(")")?;
                }
                other => return self.fail(format!("`{other}` is not a fact")),
            }
            if !self.eat(",") {
                break;
            }
        }
        self.end_of_line()?;
        Ok(facts)
    }

    /// One instruction line.
    fn inst(&mut self) -> Result<PendingInst<'a>, ParseError> {
        let line = self.line;
        let mut results = Vec::new();
        if self.peek_is("%") {
            results = self.value_list()?;
            self.expect("=")?;
        }

        let word = self.word();
        let Some(opcode) = Opcode::from_name(word) else {
            return self.fail(format!("`{word}` is not an opcode"));
        };
        let (written, flags) = self.suffixes()?;

        let mut args = Vec::new();
        let extra = match opcode.extra_kind() {
            ExtraKind::None => {
                args = self.value_list()?;
                PendingExtra::None
            }
            ExtraKind::Imm => PendingExtra::Imm(self.imm_text()?),
            ExtraKind::Symbol => {
                let symbol = self.symbol()?;
                if self.eat("(") {
                    args = self.value_list()?;
                    self.expect(")")?;
                }
                PendingExtra::Symbol(symbol)
            }
            ExtraKind::IntPred => {
                let word = self.word();
                let Some(pred) = IntPred::from_name(word) else {
                    return self.fail(format!("`{word}` is not an integer comparison"));
                };
                args = self.value_list()?;
                PendingExtra::IntPred(pred)
            }
            ExtraKind::FloatPred => {
                let word = self.word();
                let Some(pred) = FloatPred::from_name(word) else {
                    return self.fail(format!("`{word}` is not a floating point comparison"));
                };
                args = self.value_list()?;
                PendingExtra::FloatPred(pred)
            }
            ExtraKind::Mem => {
                if matches!(opcode, Opcode::Store | Opcode::AtomicStore) {
                    // A store reads left to right like the assignment it came from.
                    let value = self.value_ref()?;
                    self.expect("->")?;
                    args = vec![value, self.value_ref()?];
                } else {
                    args = self.value_list()?;
                }
                PendingExtra::Mem(self.mem()?)
            }
            ExtraKind::VaObject => {
                args = self.value_list()?;
                let (info, slots) = self.va()?;
                PendingExtra::VaObject(info, slots)
            }
            ExtraKind::Rmw => {
                let word = self.word();
                let Some(op) = RmwOp::from_name(word) else {
                    return self.fail(format!("`{word}` is not a read-modify-write"));
                };
                args = self.value_list()?;
                PendingExtra::Rmw(op, self.mem()?)
            }
            ExtraKind::Order => {
                let word = self.word();
                let Some(order) = MemOrder::from_name(word) else {
                    return self.fail(format!("`{word}` is not an ordering"));
                };
                PendingExtra::Order(order)
            }
            // The plane writes. Each reads its range and then the one thing it needs beyond it,
            // written with a name in front the way the fields of an access are.
            ExtraKind::Class => {
                args = self.value_list()?;
                self.expect(",")?;
                self.expect("class")?;
                let word = self.word();
                let Some(class) = StorageClass::from_name(word) else {
                    return self.fail(format!("`{word}` is not a storage class"));
                };
                PendingExtra::Class(class)
            }
            ExtraKind::Owner => {
                args = self.value_list()?;
                self.expect(",")?;
                self.expect("to")?;
                let word = self.word();
                let Some(owner) = Owner::from_name(word) else {
                    return self.fail(format!("`{word}` is not somewhere a range can go"));
                };
                PendingExtra::Owner(owner)
            }
            ExtraKind::Node => {
                args = self.value_list()?;
                self.expect(",")?;
                self.expect("tbaa")?;
                PendingExtra::Node(self.meta_ref()?)
            }
            ExtraKind::Reason => PendingExtra::Reason(self.symbol_from_string()?),
            ExtraKind::Targets => {
                args = self.value_list()?;
                if !args.is_empty() {
                    self.expect(",")?;
                }
                let mut targets = Vec::new();
                loop {
                    targets.push(self.block_call()?);
                    if !self.eat(",") {
                        break;
                    }
                }
                PendingExtra::Targets(targets)
            }
            ExtraKind::Call => {
                let callee = if self.peek_is("@") {
                    Some(self.symbol()?)
                } else {
                    args.push(self.value_ref()?);
                    None
                };
                self.expect("(")?;
                let (values, abis) = self.call_args()?;
                args.extend(values);
                self.expect(")")?;
                self.expect(":")?;
                PendingExtra::Call { callee, signature: self.signature()?, abis }
            }
            ExtraKind::Switch => {
                args = self.value_list()?;
                let mut targets = Vec::new();
                let mut cases = Vec::new();
                if self.eat(",") {
                    targets.push(self.block_call()?);
                    self.expect(",")?;
                    self.expect("[")?;
                    if !self.eat("]") {
                        loop {
                            cases.push(self.imm_text()?);
                            self.expect("=>")?;
                            targets.push(self.block_call()?);
                            if !self.eat(",") {
                                break;
                            }
                        }
                        self.expect("]")?;
                    }
                }
                PendingExtra::Switch { targets, cases }
            }
            ExtraKind::Asm => {
                let template = self.symbol_from_string()?;
                self.expect(",")?;
                let constraints = self.symbol_from_string()?;
                self.expect(",")?;
                let clobbers = self.symbol_from_string()?;
                self.expect("(")?;
                args = self.value_list()?;
                self.expect(")")?;
                let mut targets = Vec::new();
                if self.eat(",") {
                    self.expect("labels")?;
                    self.expect("[")?;
                    loop {
                        targets.push(self.block_call()?);
                        if !self.eat(",") {
                            break;
                        }
                    }
                    self.expect("]")?;
                }
                PendingExtra::Asm { template, constraints, clobbers, targets }
            }
        };
        // The memory operand comes last and outside the operand list, with no comma before it,
        // so nothing above has to know it might be there.
        let mut mem = None;
        if self.eat("[") {
            self.expect("mem")?;
            let value = self.value_ref()?;
            self.expect("]")?;
            args.push(value);
            mem = Some(value);
        }
        self.end_of_line()?;
        Ok(PendingInst { opcode, flags, results, written, args, mem, extra, line })
    }

    /// The dotted things after an opcode: the result types, then the flags.
    fn suffixes(&mut self) -> Result<(Vec<Type>, Flags), ParseError> {
        let mut written = Vec::new();
        let mut flags = Flags::NONE;
        while self.at(".") {
            self.pos += 1;
            if self.at("(") {
                self.pos += 1;
                loop {
                    written.push(self.ty()?);
                    if !self.eat(",") {
                        break;
                    }
                }
                self.expect(")")?;
                continue;
            }
            let word = self.glued_word();
            if let Some(flag) = Flags::from_name(word) {
                flags |= flag;
            } else if let Some(ty) = Type::parse(word) {
                written.push(ty);
            } else {
                return self.fail(format!("`{word}` is neither a type nor a flag"));
            }
        }
        Ok((written, flags))
    }

    /// What an access carries beyond its address.
    fn mem(&mut self) -> Result<MemInfo, ParseError> {
        let mut info = MemInfo {
            size: 0,
            align: 1,
            order: MemOrder::NotAtomic,
            tbaa: None,
            owns: 0,
            restrict: Restrict::NONE,
        };
        while self.eat(",") {
            let word = self.word();
            if !self.mem_field(&mut info, word)? {
                return self.fail(format!("an access has no `{word}`"));
            }
        }
        Ok(info)
    }

    /// One `name value` pair of an access, and whether the name was one of them.
    fn mem_field(&mut self, info: &mut MemInfo, word: &str) -> Result<bool, ParseError> {
        match word {
            "size" => info.size = self.u64()?,
            "align" => info.align = self.u32()?,
            "tbaa" => info.tbaa = Some(self.meta_ref()?),
            "owns" => info.owns = self.u32()?,
            "restrict" => info.restrict = self.restrict()?,
            _ => match MemOrder::from_name(word) {
                Some(order) => info.order = order,
                None => return Ok(false),
            },
        }
        Ok(true)
    }

    /// The clique and the base of a `restrict` scope, as `restrict(clique, base)`.
    fn restrict(&mut self) -> Result<Restrict, ParseError> {
        self.expect("(")?;
        let clique = self.u16()?;
        self.expect(",")?;
        let base = self.u16()?;
        self.expect(")")?;
        Ok(Restrict { clique, base })
    }

    /// An access with the slots an object read off a variable argument list travelled in, which
    /// is an access and nothing else for one that travelled in memory.
    fn va(&mut self) -> Result<(MemInfo, Vec<Slot>), ParseError> {
        let mut info = MemInfo {
            size: 0,
            align: 1,
            order: MemOrder::NotAtomic,
            tbaa: None,
            owns: 0,
            restrict: Restrict::NONE,
        };
        let mut slots = Vec::new();
        while self.eat(",") {
            let word = self.word();
            if word == "in" {
                self.expect("(")?;
                loop {
                    slots.push(self.slot()?);
                    if !self.eat(",") {
                        break;
                    }
                }
                self.expect(")")?;
            } else if !self.mem_field(&mut info, word)? {
                return self
                    .fail(format!("an object off a variable argument list has no `{word}`"));
            }
        }
        Ok((info, slots))
    }

    /// One register's worth of an object, as what is read out of it and where its bytes are.
    fn slot(&mut self) -> Result<Slot, ParseError> {
        let word = self.word();
        let slot = match word {
            "int" => {
                let size = self.u32()?;
                self.expect("at")?;
                Slot::Integer { offset: self.u64()?, size }
            }
            "float" => {
                let name = self.word();
                let Some(format) = Format::from_name(name) else {
                    return self.fail(format!("`{name}` is not a floating point format"));
                };
                self.expect("at")?;
                Slot::Float { offset: self.u64()?, format }
            }
            _ => return self.fail(format!("`{word}` is not how a slot is written")),
        };
        Ok(slot)
    }

    /// A branch target and the values it passes.
    fn block_call(&mut self) -> Result<PendingCall, ParseError> {
        let block = self.block_ref()?;
        let mut args = Vec::new();
        if self.eat("(") {
            args = self.value_list()?;
            self.expect(")")?;
        }
        Ok(PendingCall { block, args })
    }

    // Building the function.

    /// Works out every value's type, then creates the blocks and instructions in print order.
    fn build(
        &mut self,
        func: &mut Func,
        blocks: &[PendingBlock<'a>],
        facts: &[PendingFacts],
    ) -> Result<(), ParseError> {
        let count = self.check_numbering(blocks)?;
        let types = self.value_types(blocks, count)?;

        let mut next = 0;
        for pending in blocks {
            let block = func.create_block();
            for &(number, ty) in &pending.params {
                if number != next {
                    self.line = self.line_of(blocks, number);
                    return self
                        .fail(format!("values are numbered in order and %{next} comes next"));
                }
                func.append_param(block, ty);
                next += 1;
            }
            for inst in &pending.insts {
                if inst.results.first().is_some_and(|&first| first != next) {
                    self.line = inst.line;
                    return self
                        .fail(format!("values are numbered in order and %{next} comes next"));
                }
                let built = self.build_inst(func, inst, &types)?;
                func.append_inst(block, built);
                next += inst.results.len() as u32;
            }
        }
        self.build_facts(func, facts, next)?;
        Ok(())
    }

    /// Puts what the facts section said onto the values it said it about.
    ///
    /// After the blocks, because a fact names values and every one of them has to exist before
    /// any of them can be looked up. The numbering is the same numbering the body uses, so a
    /// number here is a value index and nothing has to be mapped.
    fn build_facts(
        &mut self,
        func: &mut Func,
        facts: &[PendingFacts],
        count: u32,
    ) -> Result<(), ParseError> {
        for pending in facts {
            self.line = pending.line;
            for number in [
                Some(pending.value),
                pending.bounds.map(|(lo, _)| lo),
                pending.bounds.map(|(_, ext)| ext),
            ]
            .into_iter()
            .flatten()
            {
                if number >= count {
                    return self.fail(format!("%{number} is used and never defined"));
                }
            }
            let value = Value::from_usize(pending.value as usize);
            if !func.facts(value).is_empty() {
                return self.fail(format!("%{} is said twice", pending.value));
            }
            func.set_facts(
                value,
                Facts {
                    bounds: pending.bounds.map(|(lo, ext)| Bounds {
                        lo: Value::from_usize(lo as usize),
                        ext: Value::from_usize(ext as usize),
                    }),
                    init: pending.init,
                    align: pending.align,
                    live: pending.live,
                },
            );
        }
        Ok(())
    }

    /// Checks that every number the text uses is one the text also defines.
    ///
    /// The answer is how many values there are, which is what everything after this is sized by.
    fn check_numbering(&mut self, blocks: &[PendingBlock<'a>]) -> Result<u32, ParseError> {
        let mut count = 0;
        for pending in blocks {
            count += pending.params.len();
            for inst in &pending.insts {
                count += inst.results.len();
            }
        }
        let count = count as u32;
        let total = blocks.len() as u32;
        for pending in blocks {
            for inst in &pending.insts {
                self.line = inst.line;
                for &arg in &inst.args {
                    if arg >= count {
                        return self.fail(format!("%{arg} is used and never defined"));
                    }
                }
                for call in inst_calls(inst) {
                    if call.block >= total {
                        return self.fail(format!("block{} is used and never defined", call.block));
                    }
                    for &arg in &call.args {
                        if arg >= count {
                            return self.fail(format!("%{arg} is used and never defined"));
                        }
                    }
                }
            }
        }
        Ok(count)
    }

    /// The type of every value, worked out from the ones the text writes down.
    ///
    /// A block parameter has its type at the block and an instruction either has its written
    /// after the opcode or takes it from an operand, so this is a fixed point over a graph whose
    /// only cycles run through parameters. It converges in as many rounds as the longest chain
    /// of instructions each taking its type from the one below it in the text.
    fn value_types(
        &mut self,
        blocks: &[PendingBlock<'a>],
        count: u32,
    ) -> Result<Vec<Option<Type>>, ParseError> {
        let mut types = vec![None; count as usize];
        for pending in blocks {
            for &(number, ty) in &pending.params {
                types[number as usize] = Some(ty);
            }
        }
        loop {
            let mut progress = false;
            for pending in blocks {
                for inst in &pending.insts {
                    let Some(&first) = inst.results.first() else { continue };
                    if types[first as usize].is_some() {
                        continue;
                    }
                    let Some(resolved) = result_types(inst, &types) else { continue };
                    if resolved.len() != inst.results.len() {
                        self.line = inst.line;
                        return self.fail(format!(
                            "{} produces {} values and the text names {}",
                            inst.opcode.name(),
                            resolved.len(),
                            inst.results.len()
                        ));
                    }
                    for (&number, ty) in inst.results.iter().zip(resolved) {
                        types[number as usize] = Some(ty);
                    }
                    progress = true;
                }
            }
            if !progress {
                break;
            }
        }
        for pending in blocks {
            for inst in &pending.insts {
                if inst.results.first().is_some_and(|&first| types[first as usize].is_none()) {
                    self.line = inst.line;
                    return self.fail(format!(
                        "nothing in the text says what {} produces",
                        inst.opcode.name()
                    ));
                }
            }
        }
        Ok(types)
    }

    fn build_inst(
        &mut self,
        func: &mut Func,
        pending: &PendingInst<'a>,
        types: &[Option<Type>],
    ) -> Result<Inst, ParseError> {
        let results: Vec<Type> = pending
            .results
            .iter()
            .map(|&number| types[number as usize].unwrap_or(Type::VOID))
            .collect();
        let args: Vec<Value> =
            pending.args.iter().map(|&number| Value::from_usize(number as usize)).collect();
        let arg_list = func.push_values(&args);

        let extra = match &pending.extra {
            PendingExtra::None => Extra::None,
            PendingExtra::Imm(text) => {
                let ty = results.first().copied().unwrap_or(Type::VOID);
                self.line = pending.line;
                let imm = self.imm(text, ty)?;
                Extra::Imm(func.add_imm(imm))
            }
            PendingExtra::Symbol(symbol) => Extra::Symbol(*symbol),
            PendingExtra::IntPred(pred) => Extra::IntPred(*pred),
            PendingExtra::FloatPred(pred) => Extra::FloatPred(*pred),
            PendingExtra::Mem(info) => Extra::Mem(func.add_mem(*info)),
            PendingExtra::VaObject(info, slots) => {
                let mem = func.add_mem(*info);
                let slots = func.push_slots(slots);
                Extra::VaObject(func.add_va_object(VaInfo { mem, slots }))
            }
            PendingExtra::Rmw(op, info) => Extra::Rmw(*op, func.add_mem(*info)),
            PendingExtra::Order(order) => Extra::Order(*order),
            PendingExtra::Class(class) => Extra::Class(*class),
            PendingExtra::Owner(owner) => Extra::Owner(*owner),
            PendingExtra::Node(node) => Extra::Node(*node),
            PendingExtra::Reason(reason) => Extra::Reason(*reason),
            PendingExtra::Targets(targets) => {
                let calls = build_calls(func, targets);
                Extra::Targets(func.push_block_calls(&calls))
            }
            PendingExtra::Call { callee, signature, abis } => {
                let named = signature.params.len();
                if abis.iter().take(named).any(|&abi| abi != Abi::Plain) {
                    self.line = pending.line;
                    return self.fail(
                        "the signature is what says how an argument it names travels".to_string(),
                    );
                }
                let varargs = match abis.get(named.min(abis.len())..) {
                    Some(rest) if rest.iter().any(|&abi| abi != Abi::Plain) => rest,
                    _ => &[],
                };
                let varargs = func.push_abis(varargs);
                let sig = func.add_signature(signature.clone());
                Extra::Call(func.add_call(CallInfo { callee: *callee, signature: sig, varargs }))
            }
            PendingExtra::Switch { targets, cases } => {
                let ty = pending
                    .args
                    .first()
                    .and_then(|&number| types[number as usize])
                    .unwrap_or(Type::VOID);
                self.line = pending.line;
                let mut imms = Vec::with_capacity(cases.len());
                for case in cases {
                    imms.push(self.imm(case, ty)?);
                }
                let calls = build_calls(func, targets);
                let targets = func.push_block_calls(&calls);
                let cases = func.push_imms(&imms);
                Extra::Switch(func.add_switch(SwitchInfo { targets, cases }))
            }
            PendingExtra::Asm { template, constraints, clobbers, targets } => {
                let calls = build_calls(func, targets);
                let targets = func.push_block_calls(&calls);
                Extra::Asm(func.add_asm(AsmInfo {
                    template: *template,
                    constraints: *constraints,
                    clobbers: *clobbers,
                    targets,
                }))
            }
        };

        let data = InstData {
            opcode: pending.opcode,
            flags: pending.flags,
            args: arg_list,
            extra,
            ..InstData::new(pending.opcode)
        };
        Ok(func.create_inst(data, &results, Span::DUMMY))
    }

    /// The line a value number is defined on, for a message about the numbering.
    fn line_of(&self, blocks: &[PendingBlock<'a>], number: u32) -> u32 {
        for pending in blocks {
            for inst in &pending.insts {
                if inst.results.contains(&number) {
                    return inst.line;
                }
            }
        }
        self.line
    }

    // Tokens.

    /// A constant, read as the type it is a constant of.
    fn imm(&mut self, text: &str, ty: Type) -> Result<Imm, ParseError> {
        let scalar = if ty.is_vector() { ty.lane() } else { ty };
        if scalar.is_int() {
            match parse_i128(text) {
                Some(value) => Ok(Imm::int(value, scalar)),
                None => self.fail(format!("`{text}` is not an {scalar}")),
            }
        } else {
            match text.strip_prefix("0x").and_then(|rest| u128::from_str_radix(rest, 16).ok()) {
                Some(bits) => Ok(Imm::from_bits(bits)),
                None => self.fail(format!("`{text}` is not the bits of a {scalar}")),
            }
        }
    }

    /// The text of a constant, which is a sign, digits, and the letters a hexadecimal one has.
    fn imm_text(&mut self) -> Result<&'a str, ParseError> {
        self.spaces();
        let start = self.pos;
        if self.at("-") {
            self.pos += 1;
        }
        while self.peek().is_some_and(|byte| byte.is_ascii_alphanumeric()) {
            self.pos += 1;
        }
        if self.pos == start {
            return self.fail("a constant was expected");
        }
        Ok(&self.text[start..self.pos])
    }

    fn ty(&mut self) -> Result<Type, ParseError> {
        let word = self.word();
        match Type::parse(word) {
            Some(ty) => Ok(ty),
            None => self.fail(format!("`{word}` is not a type")),
        }
    }

    /// A `%n`, giving back the number.
    fn value_ref(&mut self) -> Result<u32, ParseError> {
        self.expect("%")?;
        self.u32()
    }

    /// A run of `%n` separated by commas, stopping at the first comma not followed by one.
    fn value_list(&mut self) -> Result<Vec<u32>, ParseError> {
        let mut values = Vec::new();
        if !self.peek_is("%") {
            return Ok(values);
        }
        loop {
            values.push(self.value_ref()?);
            let save = self.pos;
            if !self.eat(",") {
                return Ok(values);
            }
            if !self.peek_is("%") {
                self.pos = save;
                return Ok(values);
            }
        }
    }

    /// The same, where each may say how the ABI asks it to travel, which is what a call writes
    /// on an argument its signature does not name.
    fn call_args(&mut self) -> Result<(Vec<u32>, Vec<Abi>), ParseError> {
        let mut values = Vec::new();
        let mut abis = Vec::new();
        if !self.peek_is("%") {
            return Ok((values, abis));
        }
        loop {
            values.push(self.value_ref()?);
            abis.push(self.abi()?);
            let save = self.pos;
            if !self.eat(",") {
                return Ok((values, abis));
            }
            if !self.peek_is("%") {
                self.pos = save;
                return Ok((values, abis));
            }
        }
    }

    /// A `blockN`, giving back the number.
    fn block_ref(&mut self) -> Result<u32, ParseError> {
        let word = self.word();
        match word.strip_prefix("block").and_then(parse_u32) {
            Some(number) => Ok(number),
            None => self.fail(format!("`{word}` is not a block")),
        }
    }

    /// A `!n`, remembering it so that one nothing defines is reported.
    fn meta_ref(&mut self) -> Result<Meta, ParseError> {
        self.expect("!")?;
        let index = self.u32()?;
        let seen = self.meta_used.is_none_or(|(used, _)| index > used);
        if seen {
            self.meta_used = Some((index, self.line));
        }
        Ok(Idx::from_usize(index as usize))
    }

    /// An `@name`, interned.
    fn symbol(&mut self) -> Result<Symbol, ParseError> {
        self.expect("@")?;
        let start = self.pos;
        while self.peek().is_some_and(is_name_byte) {
            self.pos += 1;
        }
        if self.pos == start {
            return self.fail("a name was expected");
        }
        let name = &self.text[start..self.pos];
        Ok(self.names.intern(name))
    }

    /// A quoted string, interned, which is what a section and a template are.
    fn symbol_from_string(&mut self) -> Result<Symbol, ParseError> {
        let text = self.quoted_str()?;
        Ok(self.names.intern(&text))
    }

    /// A quoted string that has to be text rather than arbitrary bytes.
    fn quoted_str(&mut self) -> Result<String, ParseError> {
        let bytes = self.string()?;
        match String::from_utf8(bytes) {
            Ok(text) => Ok(text),
            Err(_) => self.fail("that string is not text"),
        }
    }

    /// A quoted string, which may hold any bytes at all.
    fn string(&mut self) -> Result<Vec<u8>, ParseError> {
        self.expect("\"")?;
        let mut bytes = Vec::new();
        loop {
            let Some(byte) = self.peek() else {
                return self.fail("that string is not closed");
            };
            self.pos += 1;
            match byte {
                b'"' => return Ok(bytes),
                b'\n' => return self.fail("that string is not closed"),
                b'\\' => {
                    let escape = match self.peek() {
                        Some(b'"') => b'"',
                        Some(b'\\') => b'\\',
                        _ => {
                            let hex = self.text.get(self.pos..self.pos + 2);
                            match hex.and_then(|hex| u8::from_str_radix(hex, 16).ok()) {
                                Some(byte) => {
                                    self.pos += 2;
                                    bytes.push(byte);
                                    continue;
                                }
                                None => return self.fail("that is not an escape"),
                            }
                        }
                    };
                    self.pos += 1;
                    bytes.push(escape);
                }
                _ => bytes.push(byte),
            }
        }
    }

    fn u32(&mut self) -> Result<u32, ParseError> {
        let word = self.word();
        match parse_u32(word) {
            Some(number) => Ok(number),
            None => self.fail(format!("`{word}` is not a number")),
        }
    }

    fn u16(&mut self) -> Result<u16, ParseError> {
        let word = self.word();
        match parse_u32(word).and_then(|number| u16::try_from(number).ok()) {
            Some(number) => Ok(number),
            None => self.fail(format!("`{word}` is not a small number")),
        }
    }

    fn u64(&mut self) -> Result<u64, ParseError> {
        let word = self.word();
        match parse_u64(word) {
            Some(number) => Ok(number),
            None => self.fail(format!("`{word}` is not a number")),
        }
    }

    fn i64(&mut self) -> Result<i64, ParseError> {
        let word = self.word();
        match parse_u64(word).and_then(|number| i64::try_from(number).ok()) {
            Some(number) => Ok(number),
            None => self.fail(format!("`{word}` is not an offset")),
        }
    }

    /// One of the keyword parenthesised after a name, as in `linkage(internal)`.
    fn parenthesised<T>(
        &mut self,
        from_name: impl Fn(&str) -> Option<T>,
        what: &str,
    ) -> Result<T, ParseError> {
        self.expect("(")?;
        let word = self.word();
        let Some(value) = from_name(word) else {
            return self.fail(format!("`{word}` is not {what}"));
        };
        self.expect(")")?;
        Ok(value)
    }

    // The cursor.

    fn fail<T>(&self, message: impl Into<String>) -> Result<T, ParseError> {
        Err(ParseError { line: self.line, message: message.into() })
    }

    fn peek(&self) -> Option<u8> {
        self.text.as_bytes().get(self.pos).copied()
    }

    fn at(&self, text: &str) -> bool {
        self.text[self.pos..].starts_with(text)
    }

    fn at_end(&self) -> bool {
        self.pos >= self.text.len()
    }

    /// Whether that text comes next, ignoring the spaces in front of it.
    fn peek_is(&self, text: &str) -> bool {
        self.text[self.pos..].trim_start_matches([' ', '\t']).starts_with(text)
    }

    fn spaces(&mut self) {
        while matches!(self.peek(), Some(b' ' | b'\t')) {
            self.pos += 1;
        }
    }

    fn eat(&mut self, text: &str) -> bool {
        self.spaces();
        if self.at(text) {
            self.pos += text.len();
            return true;
        }
        false
    }

    fn expect(&mut self, text: &str) -> Result<(), ParseError> {
        if self.eat(text) {
            return Ok(());
        }
        self.fail(format!("`{text}` was expected"))
    }

    /// A word of letters, digits and underscores, after the spaces in front of it.
    fn word(&mut self) -> &'a str {
        self.spaces();
        self.glued_word()
    }

    /// The same, with nothing skipped, which is what a suffix after a dot is.
    fn glued_word(&mut self) -> &'a str {
        let start = self.pos;
        while self.peek().is_some_and(|byte| byte.is_ascii_alphanumeric() || byte == b'_') {
            self.pos += 1;
        }
        &self.text[start..self.pos]
    }

    /// The next word without consuming it, for deciding what a line is.
    fn peek_word(&self) -> &'a str {
        let rest = self.text[self.pos..].trim_start_matches([' ', '\t']);
        let end =
            rest.find(|c: char| !(c.is_ascii_alphanumeric() || c == '_')).unwrap_or(rest.len());
        &rest[..end]
    }

    /// Whether that word comes next, consuming it if so.
    fn eat_word(&mut self, word: &str) -> bool {
        if self.peek_word() == word {
            self.word();
            return true;
        }
        false
    }

    fn end_of_line(&mut self) -> Result<(), ParseError> {
        self.spaces();
        if self.at_end() {
            return Ok(());
        }
        if self.at("\n") {
            self.pos += 1;
            self.line += 1;
            return Ok(());
        }
        let rest = &self.text[self.pos..];
        let end = rest.find('\n').unwrap_or(rest.len());
        self.fail(format!("`{}` is left over at the end of the line", &rest[..end]))
    }

    fn skip_blank_lines(&mut self) {
        loop {
            let save = self.pos;
            self.spaces();
            if self.at("\n") {
                self.pos += 1;
                self.line += 1;
            } else {
                self.pos = save;
                return;
            }
        }
    }
}

/// Every branch target an instruction has, whichever payload holds them.
fn inst_calls<'p>(inst: &'p PendingInst<'_>) -> &'p [PendingCall] {
    match &inst.extra {
        PendingExtra::Targets(targets)
        | PendingExtra::Switch { targets, .. }
        | PendingExtra::Asm { targets, .. } => targets,
        _ => &[],
    }
}

/// The branch targets of an instruction, with their arguments put in the function's pool.
fn build_calls(func: &mut Func, targets: &[PendingCall]) -> Vec<BlockCall> {
    targets
        .iter()
        .map(|call| {
            let args: Vec<Value> =
                call.args.iter().map(|&number| Value::from_usize(number as usize)).collect();
            BlockCall {
                block: Block::from_usize(call.block as usize),
                args: func.push_values(&args),
            }
        })
        .collect()
}

/// What an instruction produces, or `None` while an operand's type is still unknown.
///
/// This is the reading half of the rule the printer writes by, which is why the two of them
/// name the same opcodes: a type is in the text only where the operands do not say it.
fn result_types(inst: &PendingInst<'_>, types: &[Option<Type>]) -> Option<Vec<Type>> {
    let mem = gives_mem(inst);
    let mut written = ordinary_result_types(inst, types, mem)?;
    if mem {
        written.push(Type::MEM);
    }
    Some(written)
}

/// Whether the instruction makes a new version of memory, which is its last result.
///
/// A `mem_entry` is where a chain starts and produces nothing else. Everything else produces one
/// where it is on the chain and it writes, which is the rule the verifier checks and the reason
/// the text does not say it a second time.
fn gives_mem(inst: &PendingInst<'_>) -> bool {
    inst.opcode == Opcode::MemEntry || (inst.mem.is_some() && inst.opcode.writes_memory())
}

/// What an instruction produces apart from memory.
fn ordinary_result_types(
    inst: &PendingInst<'_>,
    types: &[Option<Type>],
    mem: bool,
) -> Option<Vec<Type>> {
    if inst.results.len().saturating_sub(usize::from(mem)) == 0 {
        return Some(Vec::new());
    }
    if !inst.written.is_empty() {
        return Some(inst.written.clone());
    }
    match inst.opcode {
        Opcode::GlobalAddr | Opcode::BlockAddr | Opcode::Alloca => Some(vec![Type::PTR]),
        Opcode::CapOf
        | Opcode::CapLoad
        | Opcode::CapNull
        | Opcode::CapNarrow
        | Opcode::CapRecover => Some(vec![Type::CAP]),
        Opcode::ICmp | Opcode::FCmp => {
            let ty = arg_type(inst, types)?;
            Some(vec![ty.with_lane(Type::I1)])
        }
        Opcode::Call | Opcode::CallIndirect | Opcode::TailCall => match &inst.extra {
            PendingExtra::Call { signature, .. } => Some(signature.return_types().collect()),
            _ => None,
        },
        _ => Some(vec![arg_type(inst, types)?]),
    }
}

/// The type of an instruction's first operand, if it is known yet.
fn arg_type(inst: &PendingInst<'_>, types: &[Option<Type>]) -> Option<Type> {
    let &first = inst.args.first()?;
    *types.get(first as usize)?
}

/// A decimal number with no sign and no leading zero, which is the only form the printer writes.
fn parse_u64(text: &str) -> Option<u64> {
    if text.is_empty() || (text.starts_with('0') && text.len() > 1) {
        return None;
    }
    if !text.bytes().all(|byte| byte.is_ascii_digit()) {
        return None;
    }
    text.parse().ok()
}

fn parse_u32(text: &str) -> Option<u32> {
    parse_u64(text).and_then(|number| u32::try_from(number).ok())
}

/// A decimal integer, with a minus sign for a negative one, as the printer writes them.
fn parse_i128(text: &str) -> Option<i128> {
    let (negative, digits) = match text.strip_prefix('-') {
        Some(rest) => (true, rest),
        None => (false, text),
    };
    if digits.is_empty() || (digits.starts_with('0') && digits.len() > 1) {
        return None;
    }
    if negative && digits == "0" {
        return None;
    }
    if !digits.bytes().all(|byte| byte.is_ascii_digit()) {
        return None;
    }
    let magnitude: u128 = digits.parse().ok()?;
    if negative {
        // The most negative number has no positive counterpart, so it is built by negating the
        // wrapped value rather than by converting first.
        (magnitude <= 1 << 127).then(|| (magnitude as i128).wrapping_neg())
    } else {
        i128::try_from(magnitude).ok()
    }
}

/// Whether a byte can appear in a symbol name.
///
/// Dots are in, because a compiler names things `hi.str` and `memcpy.resolve` and the assembler
/// takes them. So is every byte above ASCII: C23 allows an identifier to be written in any script
/// and gcc allowed it long before that, so a name the front end read has to come back out of the
/// printer and go back in. Nothing is decoded here, because a name is a run of bytes either way
/// and the file it was read from was checked for being UTF-8 when it was read.
fn is_name_byte(byte: u8) -> bool {
    byte.is_ascii_alphanumeric() || matches!(byte, b'_' | b'.' | b'$') || byte >= 0x80
}

#[cfg(test)]
mod tests {
    use rucc_base::Interner;

    use super::*;
    use crate::fixtures::{EXAMPLE, SAFETY, SYMBOLS, ZOO};
    use crate::print;

    /// Reads a module and writes it back out, which is the whole claim this file makes.
    fn round_trip(text: &str) -> String {
        let mut names = Interner::new();
        let module = match parse(text, &mut names) {
            Ok(module) => module,
            Err(error) => panic!("{error}"),
        };
        print(&module, &names)
    }

    fn error(text: &str) -> String {
        let mut names = Interner::new();
        match parse(text, &mut names) {
            Ok(_) => panic!("that was expected to be turned down"),
            Err(error) => error.to_string(),
        }
    }

    const HEADER: &str = "\
; ModuleID = 'example.c'
; format 0
target triple = \"x86_64-unknown-linux-gnu\"
target datalayout = \"e-p:64:64-i64:64-f80:128-S128\"
";

    #[test]
    fn the_example_in_the_spec_comes_back_byte_for_byte() {
        assert_eq!(round_trip(EXAMPLE), EXAMPLE);
    }

    #[test]
    fn one_of_almost_everything_comes_back_byte_for_byte() {
        assert_eq!(round_trip(ZOO), ZOO);
    }

    #[test]
    fn a_memory_chain_comes_back_byte_for_byte() {
        let text = format!(
            "{HEADER}
func @f(ptr, i1) -> i32, linkage(external) {{
block0(%0: ptr, %1: i1):
    %2 = mem_entry
    %3 = iconst.i32 7
    %4 = store %3 -> %0, align 4 [mem %2]
    br_if %1, block1(%4), block2(%4)

block1(%5: mem):
    %6 = load.i32 %0, align 4 [mem %5]
    %7 = memcpy %0, %0, size 4, align 4 [mem %5]
    return %6

block2(%8: mem):
    %9 = atomic_load.i32 %0, align 4, acquire [mem %8]
    return %9
}}
"
        );
        assert_eq!(round_trip(&text), text);
    }

    #[test]
    fn a_restrict_clique_and_base_come_back_byte_for_byte() {
        let text = format!(
            "{HEADER}
func @f(ptr, ptr), linkage(external) {{
block0(%0: ptr, %1: ptr):
    %2 = load.i32 %0, align 4, restrict(1, 1)
    store %2 -> %1, align 4, restrict(1, 2)
    return
}}
"
        );
        assert_eq!(round_trip(&text), text);
    }

    #[test]
    fn the_padding_a_member_owns_comes_back_byte_for_byte() {
        // The number `-fsafety-init=nopadding` puts on a store through a member of a record, which
        // is the member's width plus whatever padding follows it. A store that owns no more than
        // it writes says nothing, so every access in every other test here stays as it was.
        let text = format!(
            "{HEADER}
func @f(ptr), linkage(external) {{
block0(%0: ptr):
    %1 = iconst.i8 1
    store %1 -> %0, align 1, owns 4
    return
}}
"
        );
        assert_eq!(round_trip(&text), text);
    }

    #[test]
    fn a_restrict_base_in_no_clique_is_reported() {
        let text = format!(
            "{HEADER}
func @f(ptr), linkage(external) {{
block0(%0: ptr):
    %1 = load.i32 %0, align 4, restrict(0, 2)
    return
}}
"
        );
        // The parser reads it, because the shape is fine. The verifier is what turns it down,
        // and its test says so.
        assert!(round_trip(&text).contains("load.i32 %0, align 4\n"));
    }

    #[test]
    fn the_shapes_a_symbol_comes_in_come_back_byte_for_byte() {
        assert_eq!(round_trip(SYMBOLS), SYMBOLS);
    }

    #[test]
    fn every_safety_instruction_comes_back_byte_for_byte() {
        assert_eq!(round_trip(SAFETY), SAFETY);
    }

    #[test]
    fn a_storage_class_nobody_has_heard_of_is_turned_down() {
        let text = format!(
            "{HEADER}\nfunc @f(ptr, i64), linkage(external) {{\n\
             block0(%0: ptr, %1: i64):\n    meta_begin %0, %1, class heap\n    return\n}}\n"
        );
        assert_eq!(error(&text), "line 8: `heap` is not a storage class");
    }

    #[test]
    fn a_range_transferred_somewhere_there_is_no_name_for_is_turned_down() {
        let text = format!(
            "{HEADER}\nfunc @f(ptr, i64), linkage(external) {{\n\
             block0(%0: ptr, %1: i64):\n    meta_transfer %0, %1, to hardware\n    return\n}}\n"
        );
        assert_eq!(error(&text), "line 8: `hardware` is not somewhere a range can go");
    }

    #[test]
    fn a_fact_nobody_has_heard_of_is_turned_down() {
        // The four are closed, the way the flags are. Something the reader lets through is
        // something a later pass silently does not act on, which is a fact that costs nothing
        // and buys nothing.
        let text = format!(
            "{HEADER}\nfunc @f(ptr), linkage(external) {{\n\
             block0(%0: ptr):\n    return\n\nfacts:\n    %0 = !sorted\n}}\n"
        );
        assert_eq!(error(&text), "line 11: `sorted` is not a fact");
    }

    #[test]
    fn a_value_said_twice_is_turned_down() {
        // One line per value, so that what is known about a value is one thing to read rather
        // than something to be assembled out of however many lines happened to mention it.
        let text = format!(
            "{HEADER}\nfunc @f(ptr), linkage(external) {{\n\
             block0(%0: ptr):\n    return\n\nfacts:\n    %0 = !live\n    %0 = !aligned(4)\n}}\n"
        );
        assert_eq!(error(&text), "line 12: %0 is said twice");
    }

    #[test]
    fn a_fact_about_a_value_that_does_not_exist_is_turned_down() {
        let text = format!(
            "{HEADER}\nfunc @f(ptr), linkage(external) {{\n\
             block0(%0: ptr):\n    return\n\nfacts:\n    %3 = !live\n}}\n"
        );
        assert_eq!(error(&text), "line 11: %3 is used and never defined");
    }

    #[test]
    fn a_plane_entry_nobody_has_heard_of_is_turned_down() {
        let text = format!("{HEADER}\n!0 = plane unwritten\n");
        assert_eq!(error(&text), "line 6: `unwritten` is not a plane entry");
    }

    #[test]
    fn a_metadata_node_of_no_known_kind_is_turned_down() {
        let text = format!("{HEADER}\n!0 = scope \"outer\"\n");
        assert_eq!(error(&text), "line 6: `scope` is not a kind of metadata node");
    }

    #[test]
    fn a_plane_entry_naming_a_node_that_comes_later_is_turned_down() {
        // The table is read once from the top, so a node that looked forward would be a node
        // the reader could not resolve when it reached it.
        let text = format!("{HEADER}\n!0 = plane !1\n!1 = tbaa \"int\", offset 0\n");
        assert_eq!(error(&text), "line 6: a metadata node names one that comes before it");
    }

    #[test]
    fn a_name_that_is_not_ascii_comes_back_byte_for_byte() {
        // C23 says an identifier may be written in any script and gcc has taken them for far
        // longer, so a program that uses one has to survive the printer and the reader. The
        // reader used to stop at the first byte above ASCII and say a name was expected.
        let text = format!("{HEADER}\nglobal @été : i32 = 1, align 4, linkage(external)\n");
        assert_eq!(round_trip(&text), text);
    }

    #[test]
    fn a_value_defined_after_it_is_used() {
        // Block layout order is not required to put a definition before its uses, so the type
        // of %2 is only known after the whole function has been read. This is the case the two
        // passes exist for.
        let text = format!(
            "{HEADER}
func @late() -> i64, linkage(external) {{
block0:
    jump block2

block1(%0: i64):
    %1 = add %2, %0
    return %1

block2:
    %2 = iconst.i64 7
    jump block1(%2)
}}
"
        );
        assert_eq!(round_trip(&text), text);
    }

    #[test]
    fn what_the_abi_asks_of_a_parameter_comes_back_byte_for_byte() {
        // A `struct` return, a `struct` argument, and a `char` the callee may read a whole
        // register of. None of it is written on a type, because none of it is a fact about one.
        let text = format!(
            "{HEADER}
func @f(ptr sret(24, align 8), ptr byval(16, align 8), i8 zext), linkage(external) {{
block0(%0: ptr, %1: ptr, %2: i8):
    return
}}

func @g(i8 sext) -> i8 sext, linkage(external);
"
        );
        assert_eq!(round_trip(&text), text);
    }

    #[test]
    fn a_word_that_is_not_an_attribute_is_not_read_as_one() {
        let text = format!(
            "{HEADER}
func @f(ptr inreg), linkage(external);
"
        );
        assert_eq!(error(&text), "line 6: `)` was expected");
    }

    #[test]
    fn an_empty_module_is_its_header() {
        assert_eq!(round_trip(HEADER), HEADER);
    }

    #[test]
    fn the_format_version_is_checked_before_anything_else() {
        let text = "; ModuleID = 'a.c'\n; format 99\n";
        assert_eq!(error(text), "line 2: this build reads format 0 and the text says format 99");
    }

    #[test]
    fn an_opcode_nobody_has_is_reported_with_its_line() {
        let text = format!(
            "{HEADER}
func @f(), linkage(external) {{
block0:
    getelementptr %0
}}
"
        );
        assert_eq!(error(&text), "line 8: `getelementptr` is not an opcode");
    }

    /// The slots of an object read off a list are the one thing in the text with a shape of their
    /// own, so a word in the wrong place there says so rather than being read as something else.
    #[test]
    fn a_slot_written_as_something_that_is_not_one_is_reported() {
        let text = format!(
            "{HEADER}
func @f(ptr) -> ptr, linkage(external) {{
block0(%0: ptr):
    %1 = va_object %0, size 16, align 8, in(short 8 at 0)
    return %1
}}
"
        );
        assert_eq!(error(&text), "line 8: `short` is not how a slot is written");
    }

    #[test]
    fn an_abi_on_an_argument_the_signature_names_is_turned_down() {
        // It would be two answers to one question, and the signature's is the one the callee
        // reads, so the text is wrong rather than one of them winning.
        let text = format!(
            "{HEADER}
func @f(ptr), linkage(external) {{
block0(%0: ptr):
    call @p(%0 byval(8, align 8)) : (ptr, ...)
    return
}}
"
        );
        assert_eq!(
            error(&text),
            "line 8: the signature is what says how an argument it names travels"
        );
    }

    #[test]
    fn a_value_nothing_defines_is_reported() {
        let text = format!(
            "{HEADER}
func @f(i32) -> i32, linkage(external) {{
block0(%0: i32):
    %1 = add %0, %9
    return %1
}}
"
        );
        assert_eq!(error(&text), "line 8: %9 is used and never defined");
    }

    #[test]
    fn a_block_nothing_defines_is_reported() {
        let text = format!(
            "{HEADER}
func @f(), linkage(external) {{
block0:
    jump block7
}}
"
        );
        assert_eq!(error(&text), "line 8: block7 is used and never defined");
    }

    #[test]
    fn values_have_to_be_numbered_in_print_order() {
        let text = format!(
            "{HEADER}
func @f() -> i32, linkage(external) {{
block0:
    %1 = iconst.i32 0
    %0 = iconst.i32 1
    return %1
}}
"
        );
        assert_eq!(error(&text), "line 8: values are numbered in order and %0 comes next");
    }

    #[test]
    fn blocks_have_to_be_numbered_in_print_order() {
        let text = format!(
            "{HEADER}
func @f(), linkage(external) {{
block1:
    return
}}
"
        );
        assert_eq!(error(&text), "line 7: blocks are numbered in order and block0 comes next");
    }

    #[test]
    fn metadata_nobody_defines_is_reported() {
        let text = format!(
            "{HEADER}
func @f(ptr), linkage(external) {{
block0(%0: ptr):
    %1 = load.i32 %0, align 4, tbaa !3
    return
}}
"
        );
        assert_eq!(error(&text), "line 8: !3 is used and never defined");
    }

    #[test]
    fn a_type_nothing_says_is_reported_rather_than_guessed() {
        let text = format!(
            "{HEADER}
func @f(), linkage(external) {{
block0:
    %0 = add
    return
}}
"
        );
        assert_eq!(error(&text), "line 8: nothing in the text says what add produces");
    }

    #[test]
    fn a_line_with_something_left_on_it_is_turned_down() {
        let text = format!(
            "{HEADER}
global @x : i32 = 0, align 4, linkage(internal) and then some
"
        );
        assert_eq!(error(&text), "line 6: `and then some` is left over at the end of the line");
    }

    #[test]
    fn a_constant_that_is_not_one_is_turned_down() {
        let text = format!(
            "{HEADER}
global @x : i32 = 007, align 4, linkage(internal)
"
        );
        assert_eq!(error(&text), "line 6: `007` is not an i32");
    }

    #[test]
    fn an_image_that_holds_a_capability_is_turned_down() {
        // A capability has no bits the reader could take, per section 5.2 of
        // `spec/safe-memory/05-representation.md`, so there is nothing to write between the equals
        // sign and the comma. This is the one place a `cap` is refused before the verifier ever
        // sees the module.
        let text = format!(
            "{HEADER}
global @x : cap = 0, align 8, linkage(internal)
"
        );
        assert_eq!(error(&text), "line 6: `0` is not the bits of a cap");
    }

    #[test]
    fn a_number_is_read_the_way_the_printer_writes_it() {
        assert_eq!(parse_i128("-1"), Some(-1));
        assert_eq!(parse_i128("0"), Some(0));
        assert_eq!(parse_i128("-0"), None);
        assert_eq!(parse_i128("+1"), None);
        assert_eq!(parse_i128("01"), None);
        assert_eq!(parse_i128(""), None);
        assert_eq!(parse_i128("170141183460469231731687303715884105728"), None);
        assert_eq!(parse_i128("-170141183460469231731687303715884105728"), Some(i128::MIN));
    }

    #[test]
    fn every_opcode_says_which_payload_it_carries() {
        // A payload the parser does not expect for that opcode is text it cannot read back, so
        // the two of them agreeing is what this file rests on.
        for opcode in Opcode::all() {
            let kind = opcode.extra_kind();
            let expected = match opcode {
                Opcode::IConst | Opcode::FConst | Opcode::Splat => ExtraKind::Imm,
                Opcode::GlobalAddr | Opcode::TargetIntrinsic => ExtraKind::Symbol,
                Opcode::ICmp => ExtraKind::IntPred,
                Opcode::FCmp => ExtraKind::FloatPred,
                Opcode::Fence => ExtraKind::Order,
                Opcode::AtomicRmw => ExtraKind::Rmw,
                Opcode::Switch => ExtraKind::Switch,
                Opcode::InlineAsm => ExtraKind::Asm,
                Opcode::Jump | Opcode::BrIf | Opcode::BlockAddr | Opcode::IndirectBr => {
                    ExtraKind::Targets
                }
                Opcode::Call | Opcode::CallIndirect | Opcode::TailCall => ExtraKind::Call,
                Opcode::Alloca
                | Opcode::Load
                | Opcode::Store
                | Opcode::Memcpy
                | Opcode::Memmove
                | Opcode::Memset
                | Opcode::AtomicLoad
                | Opcode::AtomicStore
                | Opcode::Cmpxchg
                | Opcode::CheckBounds
                | Opcode::CheckType
                | Opcode::CheckInit
                | Opcode::CheckRestrictRead
                | Opcode::CheckRestrictWrite
                | Opcode::RestrictEnter => ExtraKind::Mem,
                Opcode::VaObject => ExtraKind::VaObject,
                Opcode::MetaBegin => ExtraKind::Class,
                Opcode::MetaTransfer => ExtraKind::Owner,
                Opcode::MetaType => ExtraKind::Node,
                Opcode::SafeRegionBegin => ExtraKind::Reason,
                _ => ExtraKind::None,
            };
            assert_eq!(kind, expected, "{}", opcode.name());
        }
    }
}