dlsym 0.0.4

//! C front end: headers → [`ir`](super::ir), using libclang loaded at run
//! time through this crate's own [`library!`](crate::library).
//!
//! Declarations are *selected* when they come from one of the input headers,
//! from a header those include with `#include "..."` (or with
//! `#include <...>` when it stays in the library's own directory tree), or
//! from a file under one of [`Options::header_dirs`]. Selected functions, variables, types and
//! `#define` constants are emitted; types they reference from elsewhere
//! (system headers, other libraries) are pulled in as needed: in full when
//! used by value, as opaque types when only used behind pointers.
//!
//! C++ headers ([`Options::cpp`]) are supported for what has a C-like ABI:
//! functions and variables in namespaces, public static and non-virtual
//! member functions (`this` first), constructors and destructors, and
//! trivially copyable types (other classes keep only their size). Names are qualified with `_` (`ns::f` ->
//! `ns_f`), overloads get a suffix from their parameter types, and symbols
//! are looked up by their mangled names as clang computes them for the
//! target. Functions not declared `noexcept` use the `C-unwind` ABI.

use std::collections::{HashMap, HashSet};
use std::fmt;
use std::path::{Path, PathBuf};

use super::clang::{self, Cursor, LibClang, Tu, Type as CType};
use super::ir::{
    Abi, Const, ConstValue, Enum, Field, Function, Header, Item, MacroArg, MacroFn, Member,
    MemberKind, Param, Record, RecordBody, RecordKind, Type, Typedef, Var, Variant,
};

/// Options for [`parse`].
#[derive(Debug, Clone, Default)]
#[non_exhaustive]
pub struct Options {
    /// The headers to parse.
    pub headers: Vec<PathBuf>,
    /// Extra arguments for clang (`-I`, `-D`, `--target=`, ...).
    pub clang_args: Vec<String>,
    /// Also select every declaration from files under these directories.
    pub header_dirs: Vec<PathBuf>,
    /// If non-empty, only select items whose C name matches one of these
    /// glob patterns (`*` and `?`).
    pub allow: Vec<String>,
    /// Never select items whose C name matches one of these patterns.
    /// (Blocked types may still be emitted if a selected item needs them.)
    pub block: Vec<String>,
    /// Path to libclang, overriding the automatic search.
    pub libclang: Option<PathBuf>,
    /// Generate bindings even if clang reports errors.
    pub keep_going: bool,
    /// Generate for this Rust target triple instead of the host (passed to
    /// clang as `--target`; add `--sysroot` etc. to
    /// [`clang_args`](Options::clang_args) as needed).
    pub target: Option<String>,
    /// Parse the headers as C++ (`-x c++`). Enabled automatically when an
    /// input header ends in `.hpp`, `.hh`, `.hxx` or `.h++`.
    pub cpp: bool,
}

/// The result of [`parse`].
#[derive(Debug, Clone)]
#[non_exhaustive]
pub struct Parsed {
    /// The extracted declarations.
    pub header: Header,
    /// Non-fatal problems (skipped items, clang warnings).
    pub warnings: Vec<String>,
    /// The libclang version used.
    pub clang_version: String,
    /// The target triple clang parsed for (layouts are only valid there).
    pub target: Option<String>,
}

/// Errors produced while parsing headers.
#[derive(Debug)]
#[non_exhaustive]
pub enum Error {
    /// libclang could not be loaded.
    LibClang(String),
    /// libclang failed to parse the input.
    Parse(String),
    /// clang reported errors.
    Diagnostics(Vec<String>),
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Error::LibClang(e) | Error::Parse(e) => f.write_str(e),
            Error::Diagnostics(d) => {
                writeln!(
                    f,
                    "clang reported errors (use --keep-going to ignore them):"
                )?;
                for d in d {
                    writeln!(f, "  {d}")?;
                }
                Ok(())
            }
        }
    }
}

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

const UMBRELLA: &str = "dlsym-gen-umbrella.h";
const MACRO_PREFIX: &str = "__dlsym_gen_macro_";

/// Parses the headers described by `opts`.
pub fn parse(opts: &Options) -> Result<Parsed, Error> {
    let lib = clang::load(opts.libclang.as_deref()).map_err(Error::LibClang)?;
    let clang_version = clang::version(lib);

    let mut umbrella = String::new();
    let mut inputs = HashSet::new();
    for h in &opts.headers {
        let abs =
            std::fs::canonicalize(h).map_err(|e| Error::Parse(format!("{}: {e}", h.display())))?;
        // Windows' canonical paths start with `\\?\`, which clang does
        // not understand in an `#include`.
        let text = abs.to_string_lossy();
        let text = text.strip_prefix(r"\\?\").unwrap_or(&text);
        umbrella.push_str(&format!("#include \"{text}\"\n"));
        inputs.insert(abs.to_string_lossy().into_owned());
    }
    let mut user_args = opts.clang_args.clone();
    if let Some(t) = &opts.target {
        user_args.insert(0, format!("--target={}", clang_triple(t)));
    }
    let cpp = opts.cpp
        || opts.headers.iter().any(|h| {
            h.extension()
                .and_then(|e| e.to_str())
                .is_some_and(|e| matches!(e, "hpp" | "hh" | "hxx" | "h++" | "H"))
        });
    let args = clang_args(&user_args, cpp);

    let tu = Tu::parse(
        lib,
        UMBRELLA,
        &args,
        &[(UMBRELLA.into(), umbrella.clone())],
        true,
    )
    .map_err(Error::Parse)?;
    let mut warnings = Vec::new();
    let mut errors = Vec::new();
    for d in tu.diagnostics() {
        if d.is_error {
            errors.push(d.message);
        } else {
            warnings.push(d.message);
        }
    }
    if !errors.is_empty() && !opts.keep_going {
        if !cpp {
            errors.push("note: if these are C++ headers, parse them as C++ (--cpp)".into());
        }
        return Err(Error::Diagnostics(errors));
    }
    warnings.extend(errors);

    let target = tu.target_triple();
    let mut ctx = Ctx::new(&tu, opts, inputs);
    ctx.warnings = warnings;
    let top = ctx.top_level();
    ctx.select_files(&top);
    ctx.name_types(&top);
    let macros = ctx.roots(&top);
    ctx.finish_records();
    ctx.name_overloads();
    let mut consts = evaluate_macros(lib, &args, &umbrella, &macros, &mut ctx);
    consts.extend(ctx.macro_fns(&consts));
    let header = ctx.take_header(consts);
    Ok(Parsed {
        header,
        warnings: ctx.warnings,
        clang_version,
        target,
    })
}

/// Builds the clang command line: the user's arguments plus defaults.
fn clang_args(user: &[String], cpp: bool) -> Vec<String> {
    let mut args = vec![if cpp { "-xc++" } else { "-xc" }.to_owned()];
    if cfg!(target_vendor = "apple")
        && !user.iter().any(|a| a.starts_with("-isysroot"))
        && let Ok(out) = std::process::Command::new("xcrun")
            .arg("--show-sdk-path")
            .output()
        && out.status.success()
    {
        args.push("-isysroot".into());
        args.push(String::from_utf8_lossy(&out.stdout).trim().to_owned());
    }
    args.extend(user.iter().cloned());
    args
}

/// Maps a Rust target triple to clang's spelling where they differ.
fn clang_triple(rust: &str) -> String {
    let mut parts: Vec<&str> = rust.split('-').collect();
    let arch = match parts.first().copied() {
        Some(a) if a.starts_with("riscv64") => "riscv64",
        Some(a) if a.starts_with("riscv32") => "riscv32",
        Some(a) => a,
        None => return rust.to_owned(),
    };
    parts[0] = arch;
    parts.join("-")
}

/// Matches `name` against a glob with `*` and `?`.
fn glob(pattern: &str, name: &str) -> bool {
    let (p, n) = (pattern.as_bytes(), name.as_bytes());
    let (mut pi, mut ni) = (0, 0);
    let (mut star, mut mark) = (None, 0);
    while ni < n.len() {
        if pi < p.len() && (p[pi] == b'?' || p[pi] == n[ni]) {
            pi += 1;
            ni += 1;
        } else if pi < p.len() && p[pi] == b'*' {
            star = Some(pi);
            mark = ni;
            pi += 1;
        } else if let Some(s) = star {
            pi = s + 1;
            mark += 1;
            ni = mark;
        } else {
            return false;
        }
    }
    while pi < p.len() && p[pi] == b'*' {
        pi += 1;
    }
    pi == p.len()
}

/// Well-known typedefs mapped straight to Rust primitives.
fn well_known(name: &str) -> Option<Type> {
    Some(match name {
        "int8_t" => Type::Fixed(8, true),
        "int16_t" => Type::Fixed(16, true),
        "int32_t" => Type::Fixed(32, true),
        "int64_t" => Type::Fixed(64, true),
        "uint8_t" => Type::Fixed(8, false),
        "uint16_t" => Type::Fixed(16, false),
        "uint32_t" => Type::Fixed(32, false),
        "uint64_t" => Type::Fixed(64, false),
        "size_t" | "uintptr_t" => Type::USize,
        "ssize_t" | "ptrdiff_t" | "intptr_t" => Type::ISize,
        _ => return None,
    })
}

/// Orders items by the file they come from (in order of first appearance)
/// and their offset in it.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct SortKey(usize, u32);

struct RecordReq<'tu> {
    name: String,
    kind: RecordKind,
    decl: Cursor<'tu>,
    full: bool,
    key: SortKey,
    /// Size and alignment of a non-trivial C++ class.
    opaque_layout: Option<(u64, u64)>,
}

struct Ctx<'tu, 'o> {
    tu: &'tu Tu<'tu>,
    opts: &'o Options,
    selected: HashSet<String>,
    /// File stems of the input headers (`pcap` for `pcap.h`).
    input_stems: Vec<String>,
    header_dirs: Vec<PathBuf>,
    canon: HashMap<String, String>,
    file_rank: HashMap<String, usize>,
    /// Rust names for tag declarations, by USR.
    tag_names: HashMap<String, String>,
    /// Typedef names, mapped to the USR of the tag they alias (if any).
    typedef_targets: HashMap<String, Option<String>>,
    records: HashMap<String, RecordReq<'tu>>,
    record_work: Vec<String>,
    bodies: HashMap<String, RecordBody>,
    enums: HashMap<String, Option<String>>,
    /// Emitted typedefs, and whether their target is needed by value.
    typedefs: HashMap<String, bool>,
    types: Vec<(SortKey, Item)>,
    funcs: Vec<(SortKey, Item)>,
    /// Symbols of the functions and variables added so far.
    func_names: HashSet<String>,
    /// Whether each C++ record (by USR) can be passed by value like a C
    /// struct.
    trivial: HashMap<String, bool>,
    fn_macros: Vec<Cursor<'tu>>,
    value_names: HashSet<String>,
    warnings: Vec<String>,
    anon_count: usize,
}

impl<'tu, 'o> Ctx<'tu, 'o> {
    fn new(tu: &'tu Tu<'tu>, opts: &'o Options, inputs: HashSet<String>) -> Self {
        Ctx {
            tu,
            opts,
            selected: inputs,
            input_stems: opts
                .headers
                .iter()
                .filter_map(|h| h.file_stem()?.to_str().map(str::to_owned))
                .collect(),
            header_dirs: opts
                .header_dirs
                .iter()
                .map(|d| std::fs::canonicalize(d).unwrap_or_else(|_| d.clone()))
                .collect(),
            canon: HashMap::new(),
            file_rank: HashMap::new(),
            tag_names: HashMap::new(),
            typedef_targets: HashMap::new(),
            records: HashMap::new(),
            record_work: Vec::new(),
            bodies: HashMap::new(),
            enums: HashMap::new(),
            typedefs: HashMap::new(),
            types: Vec::new(),
            funcs: Vec::new(),
            func_names: HashSet::new(),
            trivial: HashMap::new(),
            fn_macros: Vec::new(),
            value_names: HashSet::new(),
            warnings: Vec::new(),
            anon_count: 0,
        }
    }

    fn warn(&mut self, msg: String) {
        self.warnings.push(msg);
    }

    /// Top-level cursors, looking through `extern "C"` blocks and
    /// namespaces.
    fn top_level(&self) -> Vec<Cursor<'tu>> {
        fn walk<'tu>(c: Cursor<'tu>, out: &mut Vec<Cursor<'tu>>) {
            for c in c.children() {
                if matches!(c.kind(), clang::LINKAGE_SPEC | clang::NAMESPACE) {
                    walk(c, out);
                } else {
                    out.push(c);
                }
            }
        }
        let mut out = Vec::new();
        walk(self.tu.cursor(), &mut out);
        out
    }

    fn canonical_file(&mut self, file: &str) -> String {
        if let Some(c) = self.canon.get(file) {
            return c.clone();
        }
        let c = std::fs::canonicalize(file)
            .map(|p| p.to_string_lossy().into_owned())
            .unwrap_or_else(|_| file.to_owned());
        self.canon.insert(file.to_owned(), c.clone());
        c
    }

    fn key(&mut self, c: Cursor<'tu>) -> SortKey {
        let loc = c.location();
        let file = self.canonical_file(&loc.file);
        let n = self.file_rank.len();
        let rank = *self.file_rank.entry(file).or_insert(n);
        SortKey(rank, loc.offset)
    }

    fn is_selected(&mut self, c: Cursor<'tu>) -> bool {
        let file = c.location().file;
        if file.is_empty() {
            return false;
        }
        let file = self.canonical_file(&file);
        self.selected.contains(&file)
            || self
                .header_dirs
                .iter()
                .any(|d| Path::new(&file).starts_with(d))
    }

    fn name_allowed(&self, name: &str) -> bool {
        (self.opts.allow.is_empty() || self.opts.allow.iter().any(|p| glob(p, name)))
            && !self.opts.block.iter().any(|p| glob(p, name))
    }

    /// Adds files included with `#include "..."` from selected files.
    fn select_files(&mut self, top: &[Cursor<'tu>]) {
        for &c in top {
            if c.kind() != clang::INCLUSION_DIRECTIVE {
                continue;
            }
            let from = self.canonical_file(&c.location().file);
            if !self.selected.contains(&from) {
                continue;
            }
            let Some(file) = c.included_file() else {
                continue;
            };
            let file = self.canonical_file(&file);
            let quoted = self
                .tu
                .tokens(c)
                .iter()
                .any(|(literal, s)| *literal && s.starts_with('"'));
            if quoted || self.same_library(Path::new(&from), Path::new(&file)) {
                self.selected.insert(file);
            }
        }
    }

    /// Whether an `#include <...>` from `from` stays within the same
    /// library: the included file is in `from`'s directory tree, and that
    /// directory is not a system include root (then only a subdirectory
    /// named after an input header counts, e.g. `pcap.h` -> `<pcap/...>`).
    fn same_library(&self, from: &Path, file: &Path) -> bool {
        let Some(dir) = from.parent() else {
            return false;
        };
        if !file.starts_with(dir) {
            return false;
        }
        let is_root = ["stdio.h", "stddef.h", "stdlib.h"]
            .iter()
            .any(|h| dir.join(h).exists());
        !is_root
            || self.input_stems.iter().any(|stem| {
                file.strip_prefix(dir)
                    .ok()
                    .and_then(|rest| rest.components().next())
                    .is_some_and(|first| first.as_os_str() == stem.as_str())
            })
    }

    /// Assigns names to anonymous tags declared through a typedef, and
    /// records which tag each typedef aliases (to detect name clashes).
    fn name_types(&mut self, top: &[Cursor<'tu>]) {
        for c in top {
            if !matches!(c.kind(), clang::TYPEDEF_DECL | clang::TYPE_ALIAS_DECL) {
                continue;
            }
            let name = scoped_name(*c);
            let target = desugar(c.typedef_underlying());
            let usr = matches!(target.kind(), clang::TYPE_RECORD | clang::TYPE_ENUM)
                .then(|| target.declaration().canonical().usr());
            if let Some(usr) = &usr
                && target.declaration().is_anonymous()
            {
                self.tag_names
                    .entry(usr.clone())
                    .or_insert_with(|| name.clone());
            }
            self.typedef_targets.entry(name).or_insert(usr);
        }
    }

    fn tag_name(&mut self, decl: Cursor<'tu>, hint: Option<&str>) -> Option<String> {
        let decl = decl.canonical();
        let usr = decl.usr();
        if let Some(n) = self.tag_names.get(&usr) {
            return Some(n.clone());
        }
        let name = if decl.is_anonymous() {
            hint?.to_owned()
        } else {
            let mut name = scoped_name(decl);
            // Template specializations share their template's name:
            // `std::vector<int>` -> `std_vector_int`.
            let spelled = decl.cursor_type().spelling();
            if spelled.contains('<') {
                name = sanitize_name(&spelled);
            }
            // `typedef int foo; struct foo {..};` would clash in Rust.
            match self.typedef_targets.get(&name) {
                Some(target) if target.as_deref() != Some(usr.as_str()) => {
                    let prefix = match decl.kind() {
                        clang::UNION_DECL => "union",
                        clang::ENUM_DECL => "enum",
                        _ => "struct",
                    };
                    format!("{prefix}_{name}")
                }
                _ => name,
            }
        };
        self.tag_names.insert(usr, name.clone());
        Some(name)
    }

    /// Visits selected declarations. Returns the `#define`s to evaluate.
    fn roots(&mut self, top: &[Cursor<'tu>]) -> Vec<(String, Cursor<'tu>)> {
        let mut macros = Vec::new();
        for &c in top {
            let kind = c.kind();
            if kind == clang::INCLUSION_DIRECTIVE || !self.is_selected(c) {
                continue;
            }
            let name = qualified_name(c);
            match kind {
                clang::FUNCTION_DECL if self.name_allowed(&name) => self.add_function(c),
                clang::VAR_DECL if self.name_allowed(&name) => self.add_var(c),
                clang::STRUCT_DECL | clang::UNION_DECL | clang::CLASS_DECL
                    if !c.is_anonymous() && self.name_allowed(&name) =>
                {
                    // Non-trivial C++ classes are only usable behind
                    // pointers: a bitwise copy would skip their copy
                    // constructor and destructor.
                    let full = c.definition().is_some() && self.is_trivial(c);
                    self.require_record(c, full);
                    if c.is_definition() {
                        if !full {
                            let ty = c.cursor_type();
                            let usr = c.canonical().usr();
                            if let (Some(size), Some(align), Some(r)) =
                                (ty.size(), ty.align(), self.records.get_mut(&usr))
                            {
                                r.opaque_layout = Some((size, align));
                            }
                        }
                        self.add_members(c);
                    }
                }
                clang::ENUM_DECL
                    if (c.is_anonymous() || self.name_allowed(&name))
                        && c.definition().is_some() =>
                {
                    self.require_enum(c);
                }
                clang::TYPEDEF_DECL | clang::TYPE_ALIAS_DECL
                    if self.name_allowed(&name)
                        && !is_function_type(desugar(c.typedef_underlying())) =>
                {
                    self.require_typedef(c, true);
                }
                clang::MACRO_DEFINITION
                    if !c.is_builtin_macro()
                        && !name.starts_with("__")
                        && self.name_allowed(&name) =>
                {
                    if c.is_function_like_macro() {
                        self.fn_macros.push(c);
                    } else {
                        macros.push((name, c));
                    }
                }
                _ => {}
            }
        }
        macros
    }

    /// Adds the public members of a C++ class definition: static and
    /// non-virtual member functions, static variables, constructors (except
    /// copy and move ones, and for abstract classes) and the destructor.
    fn add_members(&mut self, class: Cursor<'tu>) {
        let abstract_class = class.is_abstract();
        for m in class.children() {
            if !m.is_public() || !self.name_allowed(&qualified_name(m)) {
                continue;
            }
            match m.kind() {
                clang::CXX_METHOD if !m.is_virtual_method() => self.add_function(m),
                clang::CONSTRUCTOR if !abstract_class && !m.is_copy_or_move_constructor() => {
                    self.add_function(m)
                }
                clang::DESTRUCTOR if !m.is_virtual_method() || !abstract_class => {
                    self.add_function(m)
                }
                clang::VAR_DECL => self.add_var(m),
                _ => {}
            }
        }
    }

    /// The Rust name and, for C++ declarations, the mangled symbol of a
    /// function or variable. `None` (with a warning) if libclang cannot
    /// mangle it.
    fn symbol_names(&mut self, c: Cursor<'tu>) -> Option<(String, Option<String>)> {
        let spelling = c.spelling();
        let rust = scoped_name(c);
        let mut mangled = c.mangling();
        // MSVC only emits a complete-object destructor (`??_D`) for classes
        // with virtual bases; the regular one (`??1`) is the base-object
        // variant, which libclang lists first.
        if c.kind() == clang::DESTRUCTOR
            && mangled.as_deref().is_some_and(|m| m.starts_with('?'))
            && let Some(base) = c.cxx_manglings().into_iter().next()
        {
            mangled = Some(base);
        }
        match mangled.as_deref().and_then(cpp_symbol) {
            Some(symbol) => Some((rust, Some(symbol.to_owned()))),
            None if rust != spelling => {
                self.warn(format!(
                    "skipped `{}`: this libclang cannot mangle C++ names",
                    qualified_name(c)
                ));
                None
            }
            None => Some((rust, None)),
        }
    }

    fn add_function(&mut self, c: Cursor<'tu>) {
        if c.linkage() != clang::LINKAGE_EXTERNAL || c.is_definition() || c.is_deleted() {
            return;
        }
        let Some((mut name, link_name)) = self.symbol_names(c) else {
            return;
        };
        let member_kind = match c.kind() {
            clang::CXX_METHOD if !c.is_static_method() => Some(MemberKind::Method),
            clang::CONSTRUCTOR => Some(MemberKind::Constructor),
            clang::DESTRUCTOR => Some(MemberKind::Destructor),
            _ => None,
        };
        match member_kind {
            Some(MemberKind::Constructor) => name = scope_prefix(c) + "new",
            Some(MemberKind::Destructor) => name = scope_prefix(c) + "destroy",
            _ => {}
        }
        // C++ inline functions are only exported if the library happens to
        // use them out of line.
        if link_name.is_some() && c.is_inline() {
            return;
        }
        let symbol = link_name.clone().unwrap_or_else(|| name.clone());
        if self.func_names.contains(&symbol) {
            return;
        }
        let ty = c.cursor_type();
        let mut params = Vec::new();
        let mut member = None;
        if let Some(kind) = member_kind {
            // `this` comes first; the class is needed by name only.
            let Type::Named(class) = self.require_record(c.semantic_parent(), false) else {
                return;
            };
            params.push(Param {
                name: Some("this".into()),
                ty: Type::Pointer {
                    pointee: Box::new(Type::Named(class.clone())),
                    is_const: kind == MemberKind::Method && c.is_const_method(),
                },
            });
            member = Some(Member { class, kind });
        }
        for a in c.arguments() {
            params.push(Param {
                name: Some(a.spelling()).filter(|n| !n.is_empty()),
                ty: self.convert_param(a.cursor_type()),
            });
        }
        // Constructors return `this` on some ABIs (MSVC, 32-bit ARM);
        // ignoring it is compatible.
        let ret = self.convert(c.result_type(), true);
        let mut abi = abi(ty.calling_convention());
        // A C++ exception unwinding through a `"C"` function aborts the
        // process; `"C-unwind"` lets it propagate as a panic would.
        // Destructors are implicitly `noexcept`.
        if link_name.is_some()
            && member_kind != Some(MemberKind::Destructor)
            && c.is_noexcept() != Some(true)
        {
            abi = match abi {
                Abi::C => Abi::CUnwind,
                Abi::Thiscall => Abi::ThiscallUnwind,
                other => other,
            };
        }
        let mut doc = c.comment();
        if link_name.is_some() {
            let sig = format!("C++: `{}`", qualified_name(c));
            doc = Some(match doc {
                Some(d) => format!("{d}\n\n{sig}"),
                None => sig,
            });
        }
        let f = Function {
            name: name.clone(),
            link_name,
            params,
            ret,
            variadic: ty.kind() == clang::TYPE_FUNCTION_PROTO && ty.is_variadic(),
            abi,
            doc,
            member,
        };
        let bad = f
            .params
            .iter()
            .map(|p| &p.ty)
            .chain([&f.ret])
            .find_map(Type::unsupported)
            .map(str::to_owned);
        if let Some(what) = bad {
            self.warn(format!(
                "skipped function `{name}`: unsupported type `{what}`"
            ));
            return;
        }
        self.func_names.insert(symbol);
        let key = self.key(c);
        self.funcs.push((key, Item::Function(f)));
    }

    fn add_var(&mut self, c: Cursor<'tu>) {
        let is_member = matches!(
            c.semantic_parent().kind(),
            clang::STRUCT_DECL | clang::CLASS_DECL | clang::UNION_DECL
        );
        if c.linkage() != clang::LINKAGE_EXTERNAL
            || (c.storage_class() == clang::STORAGE_STATIC && !is_member)
            || c.is_definition() && is_member
        {
            return;
        }
        let Some((name, link_name)) = self.symbol_names(c) else {
            return;
        };
        let symbol = link_name.clone().unwrap_or_else(|| name.clone());
        if self.func_names.contains(&symbol) {
            return;
        }
        let t = c.cursor_type();
        // An `extern T name[];` symbol is the address of its first element.
        let (ty, is_const) = if desugar(t).kind() == clang::TYPE_INCOMPLETE_ARRAY {
            let elem = desugar(t).element();
            (self.convert(elem, true), elem.is_const())
        } else {
            (self.convert(t, true), t.is_const())
        };
        if let Some(what) = ty.unsupported() {
            let what = what.to_owned();
            self.warn(format!(
                "skipped variable `{name}`: unsupported type `{what}`"
            ));
            return;
        }
        self.func_names.insert(symbol);
        let key = self.key(c);
        let doc = c.comment();
        self.funcs.push((
            key,
            Item::Var(Var {
                name,
                link_name,
                ty,
                is_const,
                doc,
            }),
        ));
    }

    fn convert_param(&mut self, t: CType<'tu>) -> Type {
        let d = desugar(t);
        match d.kind() {
            clang::TYPE_CONSTANT_ARRAY | clang::TYPE_INCOMPLETE_ARRAY => {
                let elem = d.element();
                Type::Pointer {
                    pointee: Box::new(self.convert(elem, false)),
                    is_const: elem.is_const(),
                }
            }
            clang::TYPE_FUNCTION_PROTO | clang::TYPE_FUNCTION_NO_PROTO => self.fn_ptr(d),
            _ => self.convert(t, true),
        }
    }

    fn convert(&mut self, t: CType<'tu>, by_value: bool) -> Type {
        match t.kind() {
            clang::TYPE_ELABORATED => self.convert(t.named(), by_value),
            clang::TYPE_ATTRIBUTED => match t.modified() {
                Some(m) => self.convert(m, by_value),
                None => self.convert(t.canonical(), by_value),
            },
            clang::TYPE_TYPEDEF => self.convert_typedef(t, by_value),
            clang::TYPE_RECORD => {
                if by_value && !self.is_trivial(t.declaration()) {
                    return Type::Unsupported(format!("non-trivial C++ type `{}`", t.spelling()));
                }
                self.require_record(t.declaration(), by_value)
            }
            clang::TYPE_LVALUE_REFERENCE | clang::TYPE_RVALUE_REFERENCE => {
                // References are passed as pointers.
                let pointee = t.pointee();
                Type::Pointer {
                    pointee: Box::new(self.convert(pointee, false)),
                    is_const: pointee.is_const(),
                }
            }
            clang::TYPE_ENUM => self.require_enum(t.declaration()),
            clang::TYPE_POINTER => {
                let pointee = t.pointee();
                if is_function_type(desugar(pointee)) {
                    return self.fn_ptr(desugar(pointee));
                }
                Type::Pointer {
                    pointee: Box::new(self.convert(pointee, false)),
                    is_const: pointee.is_const(),
                }
            }
            clang::TYPE_CONSTANT_ARRAY => Type::Array {
                elem: Box::new(self.convert(t.element(), by_value)),
                len: t.array_len().unwrap_or(0),
            },
            clang::TYPE_INCOMPLETE_ARRAY => Type::Array {
                elem: Box::new(self.convert(t.element(), by_value)),
                len: 0,
            },
            clang::TYPE_UNEXPOSED | clang::TYPE_INVALID => {
                let c = t.canonical();
                if c.kind() != clang::TYPE_UNEXPOSED && c.kind() != clang::TYPE_INVALID {
                    self.convert(c, by_value)
                } else {
                    Type::Unsupported(t.spelling())
                }
            }
            kind => builtin(kind, t),
        }
    }

    /// Whether a record can be passed by value like a C struct: a POD, or
    /// a class with no base classes, virtual functions, user-declared
    /// destructor or copy/move constructor, recursively through its fields.
    /// Other types are passed by hidden reference in C++ ABIs.
    /// Conservative: an explicitly defaulted destructor counts as
    /// non-trivial, and so does any non-POD template specialization (whose
    /// implicitly instantiated members libclang does not list).
    fn is_trivial(&mut self, decl: Cursor<'tu>) -> bool {
        let ty = decl.cursor_type();
        if ty.is_pod() {
            return true;
        }
        if ty.spelling().contains('<') {
            return false;
        }
        let Some(def) = decl.definition() else {
            return true;
        };
        let usr = def.usr();
        if let Some(&t) = self.trivial.get(&usr) {
            return t;
        }
        self.trivial.insert(usr.clone(), true);
        let trivial = def.children().into_iter().all(|c| match c.kind() {
            clang::CXX_BASE_SPECIFIER | clang::DESTRUCTOR => false,
            clang::CONSTRUCTOR => !c.is_copy_or_move_constructor(),
            clang::CXX_METHOD => !c.is_virtual_method(),
            clang::FIELD_DECL => {
                let mut t = desugar(c.cursor_type());
                while matches!(
                    t.kind(),
                    clang::TYPE_CONSTANT_ARRAY | clang::TYPE_INCOMPLETE_ARRAY
                ) {
                    t = desugar(t.element());
                }
                t.kind() != clang::TYPE_RECORD || self.is_trivial(t.declaration())
            }
            _ => true,
        });
        self.trivial.insert(usr, trivial);
        trivial
    }

    /// Gives overloaded C++ functions distinct Rust names, suffixed with
    /// their parameter types (`scale_int`, `scale_double`).
    fn name_overloads(&mut self) {
        let mut count: HashMap<String, usize> = HashMap::new();
        for (_, item) in &self.funcs {
            if let Item::Function(f) = item {
                *count.entry(f.name.clone()).or_default() += 1;
            }
        }
        let mut taken: HashSet<String> = self
            .funcs
            .iter()
            .filter_map(|(_, i)| match i {
                Item::Function(f) if count[&f.name] == 1 => Some(f.name.clone()),
                Item::Var(v) => Some(v.name.clone()),
                _ => None,
            })
            .collect();
        for (_, item) in &mut self.funcs {
            let Item::Function(f) = item else { continue };
            if count[&f.name] == 1 {
                continue;
            }
            let mut name = f.name.clone();
            let params = &f.params[usize::from(f.member.is_some())..];
            if params.is_empty() {
                name.push_str("_void");
            }
            for p in params {
                name.push('_');
                name.push_str(&type_suffix(&p.ty));
            }
            // `const` and non-`const` overloads of a method.
            if let Some(Param {
                ty: Type::Pointer { is_const: true, .. },
                ..
            }) = f.params.first().filter(|_| f.member.is_some())
            {
                name.push_str("_const");
            }
            let mut unique = name.clone();
            let mut n = 2;
            while !taken.insert(unique.clone()) {
                unique = format!("{name}_{n}");
                n += 1;
            }
            f.name = unique;
        }
    }

    fn fn_ptr(&mut self, ft: CType<'tu>) -> Type {
        let params = ft
            .args()
            .into_iter()
            .map(|a| self.convert_param(a))
            .collect();
        Type::FnPtr {
            params,
            ret: Box::new(self.convert(ft.result(), true)),
            variadic: ft.kind() == clang::TYPE_FUNCTION_PROTO && ft.is_variadic(),
            abi: abi(ft.calling_convention()),
        }
    }

    fn convert_typedef(&mut self, t: CType<'tu>, by_value: bool) -> Type {
        let decl = t.declaration();
        let name = decl.spelling();
        if let Some(prim) = well_known(&name) {
            return prim;
        }
        let under = desugar(t);
        if is_function_type(under) {
            return Type::Unsupported(format!("function type `{name}`"));
        }
        // Keep the names of the library's own typedefs, and of typedefs for
        // records and enums (`FILE`); inline other foreign ones (`off_t`).
        if self.is_selected(decl) || matches!(under.kind(), clang::TYPE_RECORD | clang::TYPE_ENUM) {
            self.require_typedef(decl, by_value)
        } else {
            self.convert(decl.typedef_underlying(), by_value)
        }
    }

    fn require_typedef(&mut self, decl: Cursor<'tu>, by_value: bool) -> Type {
        if let Some(prim) = well_known(&decl.spelling()) {
            return prim;
        }
        let name = scoped_name(decl);
        match self.typedefs.get(&name) {
            Some(&full) if full || !by_value => return Type::Named(name),
            Some(_) => {
                // A pointer-only use became a by-value one: the target must
                // now be complete.
                let ty = self.convert(decl.typedef_underlying(), true);
                if let Some(what) = ty.unsupported() {
                    return Type::Unsupported(what.to_owned());
                }
                self.typedefs.insert(name.clone(), true);
                return Type::Named(name);
            }
            None => {}
        }
        self.typedefs.insert(name.clone(), by_value);
        let ty = self.convert(decl.typedef_underlying(), by_value);
        // `typedef struct foo foo;` and `typedef struct {..} foo;` need no
        // alias: the record already has this name.
        if ty != Type::Named(name.clone()) {
            if let Some(what) = ty.unsupported() {
                let what = what.to_owned();
                self.warn(format!(
                    "skipped typedef `{name}`: unsupported type `{what}`"
                ));
                // Not emitted: later uses must not refer to it by name.
                self.typedefs.remove(&name);
                return Type::Unsupported(what);
            }
            let key = self.key(decl);
            let doc = decl.comment();
            self.types.push((
                key,
                Item::Typedef(Typedef {
                    name: name.clone(),
                    ty,
                    doc,
                }),
            ));
        }
        Type::Named(name)
    }

    fn require_record(&mut self, decl: Cursor<'tu>, by_value: bool) -> Type {
        let decl = decl.canonical();
        let usr = decl.usr();
        let name = match self.tag_name(decl, None) {
            Some(n) => n,
            None => {
                self.anon_count += 1;
                let n = format!("anon{}", self.anon_count);
                self.tag_names.insert(usr.clone(), n.clone());
                n
            }
        };
        if let Some(req) = self.records.get_mut(&usr) {
            if by_value && !req.full {
                req.full = true;
                self.record_work.push(usr);
            }
            return Type::Named(name);
        }
        let kind = if decl.kind() == clang::UNION_DECL {
            RecordKind::Union
        } else {
            RecordKind::Struct
        };
        let key = self.key(decl.definition().unwrap_or(decl));
        self.records.insert(
            usr.clone(),
            RecordReq {
                name: name.clone(),
                kind,
                decl,
                full: by_value,
                key,
                opaque_layout: None,
            },
        );
        if by_value {
            self.record_work.push(usr);
        }
        Type::Named(name)
    }

    fn require_enum(&mut self, decl: Cursor<'tu>) -> Type {
        let decl = decl.definition().unwrap_or(decl);
        let usr = decl.canonical().usr();
        let repr = integer_type(decl.enum_integer_type());
        if let Some(name) = self.enums.get(&usr) {
            return name.clone().map_or(repr, Type::Named);
        }
        let name = self.tag_name(decl, None);
        self.enums.insert(usr, name.clone());
        let unsigned = matches!(
            repr,
            Type::UChar
                | Type::UShort
                | Type::UInt
                | Type::ULong
                | Type::ULongLong
                | Type::Fixed(_, false)
        );
        // `enum class` constants are scoped by their enum, others by the
        // enclosing namespace or class.
        let prefix = match &name {
            Some(n) if decl.is_scoped_enum() => format!("{n}_"),
            _ => scope_prefix(decl),
        };
        let variants: Vec<Variant> = decl
            .children()
            .into_iter()
            .filter(|v| v.kind() == clang::ENUM_CONSTANT_DECL)
            .map(|v| Variant {
                name: format!("{prefix}{}", v.spelling()),
                value: v.enum_value(unsigned),
                doc: v.comment(),
            })
            .collect();
        self.value_names
            .extend(variants.iter().map(|v| v.name.clone()));
        self.value_names.extend(name.clone());
        let key = self.key(decl);
        self.types.push((
            key,
            Item::Enum(Enum {
                name: name.clone(),
                repr: repr.clone(),
                variants,
                doc: decl.comment(),
            }),
        ));
        name.map_or(repr, Type::Named)
    }

    /// Converts the fields of every record needed by value, until no new
    /// requirement appears.
    fn finish_records(&mut self) {
        let mut done = HashSet::new();
        while let Some(usr) = self.record_work.pop() {
            if !done.insert(usr.clone()) {
                continue;
            }
            let (decl, name) = {
                let r = &self.records[&usr];
                (r.decl, r.name.clone())
            };
            let Some(def) = decl.definition() else {
                continue;
            };
            let body = self.record_body(def, &name);
            if let Some(r) = self.records.get_mut(&usr) {
                r.decl = def;
            }
            if let Some(body) = body {
                self.bodies.insert(usr, body);
            }
        }
    }

    fn record_body(&mut self, def: Cursor<'tu>, parent: &str) -> Option<RecordBody> {
        let ty = def.cursor_type();
        let (size, align) = (ty.size()?, ty.align()?);
        let mut fields = Vec::new();
        let mut anon = 0;
        for c in def.children() {
            match c.kind() {
                clang::FIELD_DECL => {
                    let raw = c.spelling();
                    let fty = c.cursor_type();
                    let name = if raw.is_empty() {
                        anon += 1;
                        format!("__anon{anon}")
                    } else {
                        raw
                    };
                    self.name_anonymous(desugar(fty), &format!("{parent}_{name}"));
                    let ty = self.convert(fty, true);
                    fields.push(Field {
                        name,
                        ty,
                        offset_bits: c.field_offset_bits().unwrap_or(0),
                        bit_width: c.bit_width(),
                        layout: (fty.size().unwrap_or(0), fty.align().unwrap_or(1)),
                        is_private: !c.is_public(),
                        doc: c.comment(),
                    });
                }
                clang::STRUCT_DECL | clang::UNION_DECL if c.is_anonymous_member() => {
                    anon += 1;
                    let name = format!("__anon{anon}");
                    let rty = c.cursor_type();
                    self.name_anonymous(rty, &format!("{parent}_{name}"));
                    let offset = first_field_name(c)
                        .and_then(|n| ty.offset_of(&n))
                        .unwrap_or(0);
                    let fty = self.convert(rty, true);
                    fields.push(Field {
                        name,
                        ty: fty,
                        offset_bits: offset,
                        bit_width: None,
                        layout: (rty.size().unwrap_or(0), rty.align().unwrap_or(1)),
                        is_private: !c.is_public(),
                        doc: None,
                    });
                }
                _ => {}
            }
        }
        if let Some(bad) = fields.iter().find_map(|f| f.ty.unsupported()) {
            let bad = bad.to_owned();
            self.warn(format!(
                "`{parent}` is opaque: it has a field of unsupported type `{bad}`"
            ));
            return None;
        }
        Some(RecordBody {
            size,
            align,
            fields,
        })
    }

    fn name_anonymous(&mut self, t: CType<'tu>, hint: &str) {
        let t = match t.kind() {
            clang::TYPE_CONSTANT_ARRAY | clang::TYPE_INCOMPLETE_ARRAY => desugar(t.element()),
            _ => t,
        };
        if matches!(t.kind(), clang::TYPE_RECORD | clang::TYPE_ENUM)
            && t.declaration().is_anonymous()
        {
            self.tag_name(t.declaration(), Some(hint));
        }
    }

    /// Turns function-like macros that wrap a single call to a bound
    /// function into [`MacroFn`]s; others are ignored.
    fn macro_fns(&mut self, consts: &[Item]) -> Vec<Item> {
        let functions: HashSet<String> = self
            .funcs
            .iter()
            .filter_map(|(_, i)| match i {
                Item::Function(f) => Some(f.name.clone()),
                _ => None,
            })
            .collect();
        let consts: HashSet<&str> = consts
            .iter()
            .filter_map(|i| match i {
                Item::Const(c) => Some(c.name.as_str()),
                _ => None,
            })
            .collect();
        let mut types: HashSet<String> = self.typedefs.keys().cloned().collect();
        types.extend(self.records.values().map(|r| r.name.clone()));
        types.extend(self.enums.values().flatten().cloned());
        let mut out = Vec::new();
        let mut seen = HashSet::new();
        for c in std::mem::take(&mut self.fn_macros) {
            let tokens: Vec<String> = self.tu.tokens(c).into_iter().map(|(_, s)| s).collect();
            let name = c.spelling();
            if self.func_names.contains(&name) || !seen.insert(name.clone()) {
                continue;
            }
            if let Some(m) = parse_macro_fn(&name, &tokens, &functions, &consts, &types) {
                out.push(Item::MacroFn(m));
            }
        }
        out
    }

    fn take_header(&mut self, consts: Vec<Item>) -> Header {
        let mut types = std::mem::take(&mut self.types);
        for (usr, r) in self.records.drain() {
            let body = if r.full {
                self.bodies.remove(&usr)
            } else {
                None
            };
            types.push((
                r.key,
                Item::Record(Record {
                    name: r.name,
                    kind: r.kind,
                    opaque_layout: if body.is_none() {
                        r.opaque_layout
                    } else {
                        None
                    },
                    body,
                    doc: r.decl.comment(),
                }),
            ));
        }
        types.sort_by_key(|(k, _)| *k);
        let mut funcs = std::mem::take(&mut self.funcs);
        funcs.sort_by_key(|(k, _)| *k);
        Header {
            items: types
                .into_iter()
                .map(|(_, i)| i)
                .chain(consts)
                .chain(funcs.into_iter().map(|(_, i)| i))
                .collect(),
        }
    }
}

/// The names of the namespaces and classes enclosing `c`, outermost first
/// (anonymous ones left out).
fn scopes(c: Cursor<'_>) -> Vec<String> {
    let mut out = Vec::new();
    let mut p = c.semantic_parent();
    while !p.is_null()
        && matches!(
            p.kind(),
            clang::NAMESPACE | clang::STRUCT_DECL | clang::CLASS_DECL | clang::UNION_DECL
        )
    {
        if p.kind() != clang::NAMESPACE {
            // A template specialization's spelling includes its arguments
            // and enclosing scopes: `ns::info<float>` -> `ns_info_float`.
            let spelled = p.cursor_type().spelling();
            if spelled.contains('<') {
                out.push(sanitize_name(&spelled));
                break;
            }
        }
        if !p.is_anonymous() {
            out.push(p.spelling());
        }
        p = p.semantic_parent();
    }
    out.reverse();
    out
}

/// `ns_Class_` for a declaration in `ns::Class`, empty at file scope.
fn scope_prefix(c: Cursor<'_>) -> String {
    scopes(c).iter().map(|s| format!("{s}_")).collect()
}

/// The Rust name of a declaration: its name qualified with `_` (`ns_f` for
/// `ns::f`, just `f` in C).
fn scoped_name(c: Cursor<'_>) -> String {
    scope_prefix(c) + &operator_name(&c.spelling())
}

/// Spells C++ operator functions as identifiers: `operator<<` ->
/// `operator_shl`, `operator bool` -> `operator_bool`.
fn operator_name(spelling: &str) -> String {
    let Some(op) = spelling
        .strip_prefix("operator")
        .filter(|op| !op.starts_with(|c: char| c.is_ascii_alphanumeric() || c == '_'))
    else {
        return spelling.to_owned();
    };
    let op = op.trim();
    let name = match op {
        "+" => "add",
        "-" => "sub",
        "*" => "mul",
        "/" => "div",
        "%" => "rem",
        "^" => "bitxor",
        "&" => "bitand",
        "|" => "bitor",
        "~" => "bitnot",
        "!" => "not",
        "=" => "assign",
        "<" => "lt",
        ">" => "gt",
        "<=" => "le",
        ">=" => "ge",
        "==" => "eq",
        "!=" => "ne",
        "<=>" => "cmp",
        "<<" => "shl",
        ">>" => "shr",
        "&&" => "and",
        "||" => "or",
        "++" => "inc",
        "--" => "dec",
        "," => "comma",
        "->" => "arrow",
        "->*" => "arrow_star",
        "()" => "call",
        "[]" => "index",
        "+=" => "add_assign",
        "-=" => "sub_assign",
        "*=" => "mul_assign",
        "/=" => "div_assign",
        "%=" => "rem_assign",
        "^=" => "bitxor_assign",
        "&=" => "bitand_assign",
        "|=" => "bitor_assign",
        "<<=" => "shl_assign",
        ">>=" => "shr_assign",
        _ => return format!("operator_{}", sanitize_name(op)),
    };
    format!("operator_{name}")
}

/// The C++ name of a declaration (`ns::Class::f`), as matched by
/// [`Options::allow`] and [`Options::block`].
fn qualified_name(c: Cursor<'_>) -> String {
    let mut parts = scopes(c);
    parts.push(c.spelling());
    parts.join("::")
}

/// The symbol to look up for clang's mangling of a declaration, if it is a
/// mangled C++ name rather than a C one. Apple's assemblers prefix every
/// symbol with `_`, which `dlsym` does not want; 32-bit Windows decorates C
/// names (`_f`, `_f@8`), which only matter to the linker.
fn cpp_symbol(mangled: &str) -> Option<&str> {
    if mangled.starts_with("__Z") {
        Some(&mangled[1..])
    } else if mangled.starts_with("_Z") || mangled.starts_with('?') {
        Some(mangled)
    } else {
        None
    }
}

/// Turns a C++ type spelling into an identifier: `std::vector<int *>` ->
/// `std_vector_int_ptr`.
fn sanitize_name(spelled: &str) -> String {
    let spelled = spelled.replace('*', " ptr ").replace('&', " ref ");
    let words: Vec<&str> = spelled
        .split(|c: char| !c.is_ascii_alphanumeric() && c != '_')
        .filter(|w| !w.is_empty())
        .collect();
    words.join("_")
}

/// A short name for `t` in an overload suffix.
fn type_suffix(t: &Type) -> String {
    match t {
        Type::Void => "void".into(),
        Type::Bool => "bool".into(),
        Type::Char => "char".into(),
        Type::SChar => "schar".into(),
        Type::UChar => "uchar".into(),
        Type::Short => "short".into(),
        Type::UShort => "ushort".into(),
        Type::Int => "int".into(),
        Type::UInt => "uint".into(),
        Type::Long => "long".into(),
        Type::ULong => "ulong".into(),
        Type::LongLong => "longlong".into(),
        Type::ULongLong => "ulonglong".into(),
        Type::Float => "float".into(),
        Type::Double => "double".into(),
        Type::Fixed(bits, true) => format!("i{bits}"),
        Type::Fixed(bits, false) => format!("u{bits}"),
        Type::USize => "usize".into(),
        Type::ISize => "isize".into(),
        Type::Pointer { pointee, is_const } => {
            let c = if *is_const { "const_" } else { "" };
            format!("{c}{}_ptr", type_suffix(pointee))
        }
        Type::Array { elem, .. } => format!("{}_array", type_suffix(elem)),
        Type::FnPtr { .. } => "fn".into(),
        Type::Named(n) => n.clone(),
        Type::Unsupported(_) => "unsupported".into(),
    }
}

fn first_field_name(record: Cursor<'_>) -> Option<String> {
    for c in record.children() {
        match c.kind() {
            clang::FIELD_DECL if !c.spelling().is_empty() => return Some(c.spelling()),
            clang::STRUCT_DECL | clang::UNION_DECL if c.is_anonymous_member() => {
                if let Some(n) = first_field_name(c) {
                    return Some(n);
                }
            }
            _ => {}
        }
    }
    None
}

/// Converts an integer type, looking through typedefs.
fn integer_type(t: CType<'_>) -> Type {
    if t.kind() == clang::TYPE_TYPEDEF
        && let Some(prim) = well_known(&t.declaration().spelling())
    {
        return prim;
    }
    let c = t.canonical();
    builtin(c.kind(), c)
}

/// Strips typedefs, elaboration and attributes.
fn desugar(mut t: CType<'_>) -> CType<'_> {
    loop {
        t = match t.kind() {
            clang::TYPE_ELABORATED => t.named(),
            clang::TYPE_TYPEDEF => t.declaration().typedef_underlying(),
            clang::TYPE_ATTRIBUTED => t.modified().unwrap_or_else(|| t.canonical()),
            _ => return t,
        };
    }
}

fn is_function_type(t: CType<'_>) -> bool {
    matches!(
        t.kind(),
        clang::TYPE_FUNCTION_PROTO | clang::TYPE_FUNCTION_NO_PROTO
    )
}

fn abi(cc: std::ffi::c_int) -> Abi {
    match cc {
        clang::CALLCONV_X86_STDCALL => Abi::Stdcall,
        clang::CALLCONV_X86_FASTCALL => Abi::Fastcall,
        clang::CALLCONV_X86_THISCALL => Abi::Thiscall,
        clang::CALLCONV_X86_VECTORCALL => Abi::Vectorcall,
        _ => Abi::C,
    }
}

fn builtin(kind: std::ffi::c_int, t: CType<'_>) -> Type {
    match kind {
        clang::TYPE_VOID => Type::Void,
        clang::TYPE_BOOL => Type::Bool,
        clang::TYPE_CHAR_S | clang::TYPE_CHAR_U => Type::Char,
        clang::TYPE_SCHAR => Type::SChar,
        clang::TYPE_UCHAR => Type::UChar,
        clang::TYPE_SHORT => Type::Short,
        clang::TYPE_USHORT => Type::UShort,
        clang::TYPE_INT => Type::Int,
        clang::TYPE_UINT => Type::UInt,
        clang::TYPE_LONG => Type::Long,
        clang::TYPE_ULONG => Type::ULong,
        clang::TYPE_LONGLONG => Type::LongLong,
        clang::TYPE_ULONGLONG => Type::ULongLong,
        clang::TYPE_INT128 => Type::Fixed(128, true),
        clang::TYPE_UINT128 => Type::Fixed(128, false),
        clang::TYPE_FLOAT => Type::Float,
        clang::TYPE_DOUBLE => Type::Double,
        clang::TYPE_CHAR16 => Type::Fixed(16, false),
        clang::TYPE_CHAR32 => Type::Fixed(32, false),
        clang::TYPE_WCHAR => match t.size() {
            Some(2) => Type::Fixed(16, false),
            _ => Type::Fixed(32, true),
        },
        clang::TYPE_NULLPTR => Type::ptr(Type::Void),
        _ => Type::Unsupported(t.spelling()),
    }
}

/// Evaluates object-like macros.
///
/// String macros are decoded from their tokens. Others are evaluated by
/// appending `static const __auto_type PROBE = (NAME);` after the headers and
/// asking clang for each initializer's value and type; macros that are not
/// constant expressions simply fail to evaluate and are skipped.
fn evaluate_macros(
    lib: &LibClang,
    args: &[String],
    umbrella: &str,
    macros: &[(String, Cursor<'_>)],
    ctx: &mut Ctx<'_, '_>,
) -> Vec<Item> {
    let mut out = Vec::new();
    let mut probes = String::from(umbrella);
    let mut numeric = Vec::new();
    // C allows identical redefinitions (e.g. in gl.h and glext.h); keep the
    // first.
    let mut seen = HashSet::new();
    for (name, cursor) in macros {
        if ctx.value_names.contains(name) || !seen.insert(name.as_str()) {
            continue;
        }
        let tokens = ctx.tu.tokens(*cursor);
        let body = tokens.get(1..).unwrap_or_default();
        if body.is_empty() {
            continue;
        }
        if body.iter().all(|(lit, s)| *lit && s.starts_with('"')) {
            let bytes: Option<Vec<u8>> = body
                .iter()
                .map(|(_, s)| unescape_c_string(s))
                .collect::<Option<Vec<_>>>()
                .map(|parts| parts.concat());
            if let Some(bytes) = bytes.filter(|b| !b.contains(&0)) {
                ctx.value_names.insert(name.clone());
                out.push(Item::Const(Const {
                    name: name.clone(),
                    value: ConstValue::Str(bytes),
                    doc: None,
                }));
            }
            continue;
        }
        probes.push_str(&format!(
            "\nstatic const __auto_type {MACRO_PREFIX}{} = ({name});",
            numeric.len()
        ));
        numeric.push(name.clone());
    }
    if numeric.is_empty() {
        return out;
    }
    let Ok(tu) = Tu::parse(lib, UMBRELLA, args, &[(UMBRELLA.into(), probes)], false) else {
        return out;
    };
    for c in tu.cursor().children() {
        let spelling = c.spelling();
        let Some(i) = spelling
            .strip_prefix(MACRO_PREFIX)
            .and_then(|i| i.parse::<usize>().ok())
        else {
            continue;
        };
        let name = &numeric[i];
        let ty = integer_type(c.cursor_type());
        let value = match c.evaluate() {
            Some(clang::Evaluated::Int(v)) if is_integer(&ty) => ConstValue::Int(v, ty),
            Some(clang::Evaluated::Float(v)) if matches!(ty, Type::Float | Type::Double) => {
                ConstValue::Float(v, ty)
            }
            _ => continue,
        };
        ctx.value_names.insert(name.clone());
        out.push(Item::Const(Const {
            name: name.clone(),
            value,
            doc: None,
        }));
    }
    out
}

/// Parses `NAME(p1, p2) target(arg, ...)` from a macro's tokens, accepting
/// only arguments that are parameters, literals, known constants, `sizeof`
/// of a known type, or casts of those.
fn parse_macro_fn(
    name: &str,
    tokens: &[String],
    functions: &HashSet<String>,
    consts: &HashSet<&str>,
    types: &HashSet<String>,
) -> Option<MacroFn> {
    let t: Vec<&str> = tokens.iter().map(String::as_str).collect();
    if t.first() != Some(&name) || t.get(1) != Some(&"(") {
        return None;
    }
    let close = matching(&t, 1)?;
    let mut params = Vec::new();
    for group in split_commas(&t[2..close]) {
        match group {
            [p] if is_ident(p) => params.push((*p).to_owned()),
            [] if close == 2 => {}
            _ => return None,
        }
    }
    let body = strip_parens(&t[close + 1..]);
    let (target, rest) = body.split_first()?;
    if !functions.contains(*target)
        || rest.first() != Some(&"(")
        || matching(rest, 0)? != rest.len() - 1
    {
        return None;
    }
    let mut used = vec![false; params.len()];
    let mut args = Vec::new();
    for arg in split_commas(&rest[1..rest.len() - 1]) {
        let arg = macro_arg(arg, &params, consts, types)?;
        if let MacroArg::Param(i) = arg
            && std::mem::replace(&mut used[i], true)
        {
            return None;
        }
        args.push(arg);
    }
    if used.iter().any(|u| !u) {
        return None;
    }
    Some(MacroFn {
        name: name.to_owned(),
        params,
        target: (*target).to_owned(),
        args,
    })
}

fn macro_arg(
    t: &[&str],
    params: &[String],
    consts: &HashSet<&str>,
    types: &HashSet<String>,
) -> Option<MacroArg> {
    let t = strip_parens(t);
    match t {
        [id] if is_ident(id) => {
            if let Some(i) = params.iter().position(|p| p == id) {
                Some(MacroArg::Param(i))
            } else if consts.contains(id) {
                Some(MacroArg::Const((*id).to_owned()))
            } else {
                None
            }
        }
        [lit] if lit.starts_with('"') => unescape_c_string(lit).map(MacroArg::Str),
        [lit] => parse_c_int(lit).map(MacroArg::Int),
        ["-", lit] => parse_c_int(lit).map(|v| MacroArg::Int(-v)),
        ["sizeof", "(", ty @ .., ")"] => {
            let ty = match ty {
                [name] | ["struct" | "union" | "enum", name] => *name,
                _ => return None,
            };
            types.contains(ty).then(|| MacroArg::SizeOf(ty.to_owned()))
        }
        // A cast: the argument is converted to the parameter type anyway.
        ["(", ..] => {
            let close = matching(t, 0)?;
            let ty = &t[1..close];
            let looks_like_type = !ty.is_empty()
                && ty.iter().all(|s| is_ident(s) || *s == "*")
                && !(ty.len() == 1 && params.iter().any(|p| p == ty[0]));
            if !looks_like_type || close + 1 >= t.len() {
                return None;
            }
            macro_arg(&t[close + 1..], params, consts, types)
        }
        _ => None,
    }
}

/// Index of the bracket closing the one at `open`.
fn matching(t: &[&str], open: usize) -> Option<usize> {
    let mut depth = 0;
    for (i, s) in t.iter().enumerate().skip(open) {
        match *s {
            "(" => depth += 1,
            ")" => {
                depth -= 1;
                if depth == 0 {
                    return Some(i);
                }
            }
            _ => {}
        }
    }
    None
}

/// Removes parentheses enclosing the whole sequence.
fn strip_parens<'a, 'b>(mut t: &'a [&'b str]) -> &'a [&'b str] {
    while t.first() == Some(&"(") && matching(t, 0) == Some(t.len() - 1) {
        t = &t[1..t.len() - 1];
    }
    t
}

/// Splits on commas outside parentheses.
fn split_commas<'a, 'b>(t: &'a [&'b str]) -> Vec<&'a [&'b str]> {
    let mut out = Vec::new();
    let (mut depth, mut start) = (0, 0);
    for (i, s) in t.iter().enumerate() {
        match *s {
            "(" => depth += 1,
            ")" => depth -= 1,
            "," if depth == 0 => {
                out.push(&t[start..i]);
                start = i + 1;
            }
            _ => {}
        }
    }
    if !t.is_empty() {
        out.push(&t[start..]);
    }
    out
}

fn is_ident(s: &str) -> bool {
    s.starts_with(|c: char| c.is_ascii_alphabetic() || c == '_')
        && s.chars().all(|c| c.is_ascii_alphanumeric() || c == '_')
}

/// Parses a C integer literal (decimal, hex, octal, binary; any suffix).
fn parse_c_int(lit: &str) -> Option<i128> {
    let lit = lit.trim_end_matches(['u', 'U', 'l', 'L']);
    let (digits, radix) = if let Some(h) = lit.strip_prefix("0x").or_else(|| lit.strip_prefix("0X"))
    {
        (h, 16)
    } else if let Some(b) = lit.strip_prefix("0b").or_else(|| lit.strip_prefix("0B")) {
        (b, 2)
    } else if lit.len() > 1 && lit.starts_with('0') {
        (&lit[1..], 8)
    } else {
        (lit, 10)
    };
    i128::from_str_radix(&digits.replace('\'', ""), radix).ok()
}

fn is_integer(t: &Type) -> bool {
    matches!(
        t,
        Type::Bool
            | Type::Char
            | Type::SChar
            | Type::UChar
            | Type::Short
            | Type::UShort
            | Type::Int
            | Type::UInt
            | Type::Long
            | Type::ULong
            | Type::LongLong
            | Type::ULongLong
            | Type::Fixed(..)
            | Type::USize
            | Type::ISize
    )
}

/// Decodes a C string literal token (with quotes) into bytes.
fn unescape_c_string(token: &str) -> Option<Vec<u8>> {
    let inner = token.strip_prefix('"')?.strip_suffix('"')?.as_bytes();
    let mut out = Vec::with_capacity(inner.len());
    let mut i = 0;
    while i < inner.len() {
        let b = inner[i];
        i += 1;
        if b != b'\\' {
            out.push(b);
            continue;
        }
        let e = *inner.get(i)?;
        i += 1;
        out.push(match e {
            b'n' => b'\n',
            b't' => b'\t',
            b'r' => b'\r',
            b'a' => 7,
            b'b' => 8,
            b'f' => 12,
            b'v' => 11,
            b'e' => 27,
            b'\\' | b'\'' | b'"' | b'?' => e,
            b'x' => {
                let start = i;
                while i < inner.len() && inner[i].is_ascii_hexdigit() {
                    i += 1;
                }
                u8::from_str_radix(std::str::from_utf8(&inner[start..i]).ok()?, 16).ok()?
            }
            b'0'..=b'7' => {
                let start = i - 1;
                while i < inner.len() && i - start < 3 && (b'0'..=b'7').contains(&inner[i]) {
                    i += 1;
                }
                u8::from_str_radix(std::str::from_utf8(&inner[start..i]).ok()?, 8).ok()?
            }
            _ => return None,
        });
    }
    Some(out)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn globs() {
        assert!(glob("z*", "zlibVersion"));
        assert!(glob("*Init?", "deflateInit2"));
        assert!(!glob("z*", "deflate"));
        assert!(glob("*", ""));
        assert!(glob("a*b*c", "aXXbYYc"));
        assert!(!glob("a*b*c", "aXXbYY"));
    }

    #[test]
    fn macro_functions() {
        let tok = |s: &str| s.split(' ').map(str::to_owned).collect::<Vec<_>>();
        let functions: HashSet<String> = ["deflateInit_".to_owned()].into();
        let consts: HashSet<&str> = ["ZLIB_VERSION"].into();
        let types: HashSet<String> = ["z_stream".to_owned()].into();
        let m = parse_macro_fn(
            "deflateInit",
            &tok("deflateInit ( strm , level ) deflateInit_ ( ( strm ) , ( level ) , ZLIB_VERSION , ( int ) sizeof ( z_stream ) )"),
            &functions,
            &consts,
            &types,
        )
        .unwrap();
        assert_eq!(m.params, ["strm", "level"]);
        assert_eq!(
            m.args,
            [
                MacroArg::Param(0),
                MacroArg::Param(1),
                MacroArg::Const("ZLIB_VERSION".into()),
                MacroArg::SizeOf("z_stream".into()),
            ]
        );
        // Anything else is rejected.
        for body in [
            "f ( x ) other_fn ( x )",
            "f ( x ) deflateInit_ ( x , x )",
            "f ( x , y ) deflateInit_ ( x )",
            "f ( x ) deflateInit_ ( x + 1 )",
            "f ( x ) ( ( x ) -> have ? 1 : 0 )",
        ] {
            assert!(
                parse_macro_fn("f", &tok(body), &functions, &consts, &types).is_none(),
                "{body}"
            );
        }
        assert_eq!(parse_c_int("0x10UL"), Some(16));
        assert_eq!(parse_c_int("017"), Some(15));
        assert_eq!(parse_c_int("0"), Some(0));
    }

    #[test]
    fn cpp_names() {
        assert_eq!(cpp_symbol("_ZN3geo3addEii"), Some("_ZN3geo3addEii"));
        assert_eq!(cpp_symbol("__ZN3geo3addEii"), Some("_ZN3geo3addEii"));
        assert_eq!(cpp_symbol("?add@geo@@YAHHH@Z"), Some("?add@geo@@YAHHH@Z"));
        assert_eq!(cpp_symbol("_add"), None);
        assert_eq!(cpp_symbol("_add@8"), None);
        assert_eq!(cpp_symbol("add"), None);
        assert_eq!(
            sanitize_name("std::vector<const char *, std::allocator<int> >"),
            "std_vector_const_char_ptr_std_allocator_int"
        );
        assert_eq!(
            type_suffix(&Type::const_ptr(Type::Named("geo_point".into()))),
            "const_geo_point_ptr"
        );
        assert_eq!(type_suffix(&Type::Fixed(64, false)), "u64");
        assert_eq!(operator_name("operator<<"), "operator_shl");
        assert_eq!(operator_name("operator new[]"), "operator_new");
        assert_eq!(
            operator_name("operator unsigned int"),
            "operator_unsigned_int"
        );
        assert_eq!(operator_name("operators"), "operators");
    }

    #[test]
    fn triples() {
        assert_eq!(
            clang_triple("riscv64gc-unknown-linux-gnu"),
            "riscv64-unknown-linux-gnu"
        );
        assert_eq!(clang_triple("aarch64-apple-darwin"), "aarch64-apple-darwin");
    }

    #[test]
    fn c_strings() {
        assert_eq!(unescape_c_string(r#""1.3.2""#).unwrap(), b"1.3.2");
        assert_eq!(unescape_c_string(r#""a\n\x41\101\"""#).unwrap(), b"a\nAA\"");
        assert_eq!(unescape_c_string("\"\\q\""), None);
    }
}