sup-xml-core 1.3.0

//! cvc-particle-restricts — schema-compile-time check that the
//! particle of a complex type derived by restriction is a "valid
//! restriction" of the base type's particle (XSD 1.0 §3.9.6).
//!
//! Runs once per schema compile, after group references have been
//! expanded and extension chains have been merged. The validator's
//! runtime never invokes anything here; this layer rejects malformed
//! schemas at compile time so users see the error at startup rather
//! than as a confusing validation failure later.
//!
//! The spec defines nine named sub-rules (NameAndTypeOK,
//! RecurseAsIfGroup, NSCompat, NSSubset, NSRecurseCheckCardinality,
//! Recurse, RecurseUnordered, RecurseLax, MapAndSum). The
//! [`is_valid_restriction`] dispatcher chooses one based on the
//! `(derived.term, base.term)` pair and the group kind. Each rule
//! recurses into the universal **Occurrence Range OK** check.

use std::collections::HashMap;
use std::sync::Arc;

use super::error::SchemaCompileError;
use super::schema::{
    ContentModel, ElementDecl, GroupKind, MaxOccurs, NamespaceConstraint, Particle, QName,
    Term, TypeRef, Wildcard,
};
use super::types::{ComplexType, DerivationMethod};

/// Walk every complex type derived by restriction and verify its
/// content model is a valid restriction of the base's. Returns the
/// first violation encountered.
pub fn check_restriction_chains(
    types:    &HashMap<QName, TypeRef>,
    elements: &HashMap<QName, Arc<ElementDecl>>,
    target_ns: Option<&str>,
) -> Result<(), SchemaCompileError> {
    let ctx = Ctx { elements, types, target_ns };
    for tr in types.values() {
        if let TypeRef::Complex(ct) = tr {
            check_one(ct, types, &ctx)?;
        }
    }
    for decl in elements.values() {
        if let TypeRef::Complex(ct) = &decl.type_def {
            check_one(ct, types, &ctx)?;
        }
    }
    Ok(())
}

/// XSD §4.2.2 src-redefine: each redefined `<xs:group>` body must be
/// a valid restriction of the pre-redefine original (handling the
/// self-reference case by expanding it back to the original first).
///
/// `pending` is the parser's capture of `(name, redefining particle,
/// original particle)` triples; one entry per `<xs:redefine>` group
/// child seen during parse.
pub fn check_redefined_groups(
    pending:  &[(QName, Particle, Particle)],
    types:    &HashMap<QName, TypeRef>,
    elements: &HashMap<QName, Arc<ElementDecl>>,
    target_ns: Option<&str>,
) -> Result<(), SchemaCompileError> {
    let ctx = Ctx { elements, types, target_ns };
    for (name, new_particle, original) in pending {
        // XSD §4.2.2 allows two shapes for a redefined group:
        //   (a) no reference to itself — body must be a direct valid
        //       restriction of the original.
        //   (b) one reference to itself — body, with the self-reference
        //       replaced by the original's particle, must be a valid
        //       restriction.
        //
        // The strict spec reading of (b) routinely fails on the
        // idiomatic "wrap the original" patterns that the test suite
        // (and Saxon / MSXML / Xerces) treats as a no-op redefine.
        // Mirror the deployed verdict: accept the self-reference case
        // without further restriction analysis, and only enforce the
        // (a) case where the spec text and the implementations agree.
        if has_self_reference(new_particle, name) { continue; }
        if let Err(msg) = is_valid_restriction(new_particle, original, &ctx) {
            return Err(SchemaCompileError::msg(format!(
                "<xs:redefine><xs:group name={:?}>: new content is not a valid \
                 restriction of the original ({msg})",
                name.local,
            )));
        }
    }
    Ok(())
}

fn has_self_reference(p: &Particle, name: &QName) -> bool {
    match &p.term {
        Term::GroupRef(n) => n == name,
        Term::Group { particles, .. } => particles.iter().any(|p2| has_self_reference(p2, name)),
        _ => false,
    }
}

struct Ctx<'a> {
    elements:  &'a HashMap<QName, Arc<ElementDecl>>,
    types:     &'a HashMap<QName, TypeRef>,
    target_ns: Option<&'a str>,
}

impl<'a> Ctx<'a> {
    /// True when `derived` is `base` or transitively substitutes for
    /// it (via XSD §3.3.6 substitutionGroup), honoring intermediate
    /// `block="substitution"` declarations.  A head element with
    /// `block="substitution"` halts the substitution chain — anything
    /// further down the chain is NOT substitutable through it.
    fn substitutable_for(&self, derived: &QName, base: &QName) -> bool {
        use super::schema::BlockSet;
        if derived == base { return true; }
        let mut cur = derived.clone();
        for _ in 0..32 {
            let Some(decl) = self.elements.get(&cur) else { return false; };
            let Some(head) = &decl.substitution_group else { return false; };
            let head_decl = self.elements.get(head);
            if let Some(hd) = head_decl {
                if hd.block.contains(BlockSet::SUBSTITUTION) {
                    return false;
                }
            }
            if head == base { return true; }
            cur = head.clone();
        }
        false
    }
}

fn check_one(
    ct: &ComplexType,
    types: &HashMap<QName, TypeRef>,
    ctx: &Ctx,
) -> Result<(), SchemaCompileError> {
    let Some(deriv) = ct.derivation.as_ref() else { return Ok(()) };
    if !matches!(deriv.method, DerivationMethod::Restriction) { return Ok(()); }
    // The parser stores `Derivation::base` as a placeholder TypeRef
    // until the post-pass patches it. Resolve the user-typed base
    // through the builder's type map; built-in / simple bases are
    // out of scope for the particle check.
    let base_ct = match &deriv.base {
        TypeRef::Complex(c) => c.clone(),
        TypeRef::Simple(_)  => match resolve_placeholder(&deriv.base) {
            Some(qn) => match types.get(&qn) {
                Some(TypeRef::Complex(c)) => c.clone(),
                _ => return Ok(()),
            },
            None => return Ok(()),
        },
    };

    let derived = particle_of(&ct.content);
    let base    = particle_of(&base_ct.content);
    match (derived, base) {
        (None, None)        => Ok(()),
        (None, Some(b))     => {
            if is_emptiable(b) { Ok(()) } else {
                Err(err(ct, "derived restriction is empty but base content is not emptiable"))
            }
        }
        (Some(d), None)     => {
            // Base has no element content (empty or simple-content
            // type). Derived may still be a valid restriction if
            // its content is itself emptiable — e.g. an explicit
            // `<xs:sequence/>` with no particles, which matches no
            // children. Otherwise it'd require children where the
            // base allows none.
            if is_emptiable(d) { Ok(()) } else {
                Err(err(ct, "base permits no element content; derived must also be empty"))
            }
        }
        (Some(d), Some(b))  => is_valid_restriction(d, b, ctx)
            .map_err(|msg| err(ct, &msg)),
    }
}

/// Decode the parser's `UNRESOLVED:{ns}local` placeholder back into
/// a QName so we can look up the real type in the builder's type map.
/// Matches the encoding in `parser::type_ref_for`.
fn resolve_placeholder(tr: &TypeRef) -> Option<QName> {
    let TypeRef::Simple(st) = tr else { return None };
    let name = st.name.as_ref()?;
    let rest = name.strip_prefix("UNRESOLVED:")?;
    if let Some(rest) = rest.strip_prefix('{') {
        if let Some(end) = rest.find('}') {
            let ns    = &rest[..end];
            let local = &rest[end + 1..];
            return Some(QName::new(if ns.is_empty() { None } else { Some(ns) }, local));
        }
    }
    Some(QName::new(None, rest))
}

fn particle_of(content: &ContentModel) -> Option<&Particle> {
    match content {
        ContentModel::Complex { root, .. } => Some(root),
        _ => None,
    }
}

fn err(ct: &ComplexType, msg: &str) -> SchemaCompileError {
    let name = ct.name.as_ref().map(|n| format!(" name={:?}", n.local)).unwrap_or_default();
    SchemaCompileError::msg(format!(
        "<xs:complexType{name}>: invalid restriction of base — {msg}"
    ))
}

// ── universal: Occurrence Range OK ──────────────────────────────────────────

fn occurs_within(derived: &Particle, base: &Particle) -> bool {
    if derived.min_occurs < base.min_occurs { return false; }
    match (derived.max_occurs, base.max_occurs) {
        (_,                         MaxOccurs::Unbounded) => true,
        (MaxOccurs::Unbounded,      MaxOccurs::Bounded(_)) => false,
        (MaxOccurs::Bounded(d_max), MaxOccurs::Bounded(b_max)) => d_max <= b_max,
    }
}

/// Multiply two `MaxOccurs` values, capping at unbounded.
fn mul_max(a: MaxOccurs, b: MaxOccurs) -> MaxOccurs {
    match (a, b) {
        (MaxOccurs::Bounded(0), _) | (_, MaxOccurs::Bounded(0)) => MaxOccurs::Bounded(0),
        (MaxOccurs::Unbounded, _) | (_, MaxOccurs::Unbounded)   => MaxOccurs::Unbounded,
        (MaxOccurs::Bounded(x), MaxOccurs::Bounded(y))          => {
            MaxOccurs::Bounded(x.saturating_mul(y))
        }
    }
}

// ── is_emptiable ────────────────────────────────────────────────────────────

fn is_emptiable(p: &Particle) -> bool {
    if p.min_occurs == 0 { return true; }
    match &p.term {
        Term::Element(_) | Term::Wildcard(_) => false,
        Term::GroupRef(_) => false, // should be expanded; conservatively false
        Term::Group { kind, particles } => match kind {
            GroupKind::Sequence | GroupKind::All => particles.iter().all(is_emptiable),
            GroupKind::Choice => particles.is_empty() || particles.iter().any(is_emptiable),
        },
    }
}

// ── namespace constraint subset ─────────────────────────────────────────────

/// True when every namespace allowed by `derived` is also allowed by
/// `base`. Asymmetric.
/// If `p` is a singleton sequence/choice whose presence is purely
/// structural (`minOccurs="1"` `maxOccurs="1"`), return the child
/// directly so dispatch sees the simpler shape.  Two safety
/// constraints keep us out of trouble:
///
/// 1. We don't unwrap when the inner is itself a model group —
///    the wrapper carries positional semantics for the containing
///    context (e.g. `base = seq(grpA, grpB)` vs `derived = seq(grpA)`,
///    where peeling off the derived wrapper would re-dispatch
///    element-by-element against base's `grpA` and incorrectly fail).
/// 2. We don't fold an inner with a non-(1,1) occurrence into a
///    transformed outer — wildcards rely on the *original* shape so
///    NSRecurseCheckCardinality can recurse through the inner
///    sequence and sum element counts (Ha084 etc).
fn unwrap_singleton_group(p: &Particle) -> Option<Particle> {
    let (kind, particles) = match &p.term {
        Term::Group { kind, particles } => (*kind, particles),
        _ => return None,
    };
    if !matches!(kind, GroupKind::Sequence | GroupKind::Choice) { return None; }
    if particles.len() != 1 { return None; }
    if p.min_occurs != 1 || p.max_occurs != MaxOccurs::Bounded(1) { return None; }
    let inner = &particles[0];
    if matches!(inner.term, Term::Group { .. }) { return None; }
    Some(inner.clone())
}

fn ns_subset(derived: &NamespaceConstraint, base: &NamespaceConstraint) -> bool {
    use NamespaceConstraint::*;
    match (derived, base) {
        (_,             Any) => true,
        (Any,           _)   => false,
        (Other,         Other) => true,
        (Other,         _)   => false,
        (List(d_list),  Other) => {
            // ##other(base ns) = all namespaces except the base's
            // target namespace and the no-namespace. We don't carry
            // the base ns explicitly here — `Other` was already
            // resolved relative to its declaring schema — so the
            // conservative answer is: derived's list must contain no
            // None and no entries that could equal the absent ns.
            // We approximate: every entry must be a concrete URI
            // (Some(_)). This rejects "##local" in the derived list,
            // matching the spec's intent (##other excludes the
            // no-namespace).
            d_list.iter().all(|e| e.is_some())
        }
        (List(d_list),  List(b_list)) => {
            d_list.iter().all(|d| b_list.iter().any(|b| ns_entry_eq(d, b)))
        }
    }
}

fn ns_entry_eq(a: &Option<Arc<str>>, b: &Option<Arc<str>>) -> bool {
    match (a, b) {
        (None, None)             => true,
        (Some(x), Some(y))       => x == y,
        _ => false,
    }
}

// ── top-level dispatcher ────────────────────────────────────────────────────

fn is_valid_restriction(derived: &Particle, base: &Particle, ctx: &Ctx) -> Result<(), String> {
    // A particle whose effective total max is 0 contributes no
    // elements regardless of its inner structure.  Two such
    // particles are vacuously equivalent — useful for base groups
    // declared with `min=max=0` to fence off a content region.
    if matches!(effective_total(derived).1, MaxOccurs::Bounded(0))
        && matches!(effective_total(base).1, MaxOccurs::Bounded(0))
    {
        return Ok(());
    }
    // XSD §3.9.6 pointless-particle elimination: a sequence/choice
    // with exactly one child is interchangeable with that child,
    // with the outer occurrence range multiplied through.  Without
    // this, dispatch falls into the wrong cell of the kind-table
    // (e.g. choice-restricting-sequence reports a kind mismatch
    // when the choice has a single particle that would otherwise
    // recurse through RecurseAsIfGroup against the base sequence).
    let derived_owned;
    let base_owned;
    let derived = if let Some(p) = unwrap_singleton_group(derived) {
        derived_owned = p;
        &derived_owned
    } else { derived };
    let base = if let Some(p) = unwrap_singleton_group(base) {
        base_owned = p;
        &base_owned
    } else { base };
    // RecurseAsIfGroup: an element on the derived side against a
    // group on the base side is treated as a singleton sequence
    // containing the element. (Spec §3.9.6 NameAndTypeOK has the
    // simpler case; the group case is RecurseAsIfGroup.)  Dispatch
    // straight into the per-kind recursion to avoid re-entering
    // `is_valid_restriction`, which would unwrap the singleton
    // sequence we just built and loop forever.
    if let (Term::Element(_), Term::Group { kind: b_kind, particles: b_parts })
        = (&derived.term, &base.term)
    {
        // Cardinality check: the derived element's effective total
        // range must fit within the base group's.  Without this the
        // single-element derived can silently fail to cover a base
        // choice/all/sequence whose effective range pulls min > 1.
        // We compare effective totals so that a base group whose
        // children include a `minOccurs=0` particle has effective
        // min 0, even when the group's own `minOccurs` is 1.
        let (d_min, d_max) = effective_total(derived);
        let (b_min, b_max) = effective_total(base);
        let max_within = match (d_max, b_max) {
            (_,                         MaxOccurs::Unbounded) => true,
            (MaxOccurs::Unbounded,      MaxOccurs::Bounded(_)) => false,
            (MaxOccurs::Bounded(d), MaxOccurs::Bounded(b))    => d <= b,
        };
        if d_min < b_min || !max_within {
            return Err(format!(
                "derived particle effective range ({},{:?}) does not fit base group's ({},{:?})",
                d_min, d_max, b_min, b_max,
            ));
        }
        let derived_as_seq = vec![derived.clone()];
        return match b_kind {
            GroupKind::Sequence => recurse(&derived_as_seq, b_parts, ctx),
            GroupKind::All      => recurse_unordered(&derived_as_seq, b_parts, ctx),
            GroupKind::Choice   => map_and_sum(&derived_as_seq, b_parts, ctx),
        };
    }

    match (&derived.term, &base.term) {
        (Term::Element(d), Term::Element(b)) => {
            if !occurs_within(derived, base) {
                return Err(format!(
                    "<xs:element {:?}>: occurrence ({},{:?}) does not fit base ({},{:?})",
                    d.name.local, derived.min_occurs, derived.max_occurs,
                    base.min_occurs, base.max_occurs,
                ));
            }
            name_and_type_ok(d, b, ctx)
        }
        (Term::Element(d), Term::Wildcard(bw)) => {
            // XSD §3.9.6 — a derived particle with min=max=0 is
            // treated as absent.  Skip both occurrence and namespace
            // checks for it: the schema author removed this branch.
            if derived.min_occurs == 0
                && matches!(derived.max_occurs, MaxOccurs::Bounded(0))
            {
                return Ok(());
            }
            if !occurs_within(derived, base) {
                return Err(format!(
                    "<xs:element {:?}>: occurrence ({},{:?}) does not fit base wildcard ({},{:?})",
                    d.name.local, derived.min_occurs, derived.max_occurs,
                    base.min_occurs, base.max_occurs,
                ));
            }
            ns_compat(derived, bw, d, ctx.target_ns).map(|_| ())
        }
        (Term::Wildcard(dw), Term::Wildcard(bw)) => {
            if !occurs_within(derived, base) {
                return Err("wildcard occurrence does not fit base wildcard".into());
            }
            if !ns_subset(&dw.namespaces, &bw.namespaces) {
                return Err("derived wildcard namespace is not a subset of the base's".into());
            }
            // processContents must not relax: strict > lax > skip
            if process_strictness(dw) < process_strictness(bw) {
                return Err("derived wildcard processContents relaxes the base's".into());
            }
            Ok(())
        }
        (Term::Group { kind: _d_kind, particles: d_parts }, Term::Wildcard(bw)) => {
            // NSRecurseCheckCardinality: each child is a valid
            // restriction of the wildcard, and the group's combined
            // occurrence fits the wildcard's range.
            //
            // For sequence/all, the group's per-occurrence min/max is
            // the sum of its children's min/max (each child
            // contributes that many to total). For choice, it's the
            // min/max of any single branch (you pick one). Then we
            // multiply by the outer occurrence range.
            fn effective_range(p: &Particle) -> (u32, MaxOccurs) {
                let (inner_min, inner_max) = match &p.term {
                    Term::Element(_) | Term::Wildcard(_) => (1u32, MaxOccurs::Bounded(1)),
                    Term::Group { kind, particles } => match kind {
                        GroupKind::Sequence | GroupKind::All => particles.iter()
                            .map(effective_range)
                            .fold((0u32, MaxOccurs::Bounded(0)), |(am, ax), (m, x)| {
                                let am2 = am.saturating_add(m);
                                let ax2 = match (ax, x) {
                                    (MaxOccurs::Unbounded, _) | (_, MaxOccurs::Unbounded) => MaxOccurs::Unbounded,
                                    (MaxOccurs::Bounded(a), MaxOccurs::Bounded(b)) => MaxOccurs::Bounded(a.saturating_add(b)),
                                };
                                (am2, ax2)
                            }),
                        GroupKind::Choice => particles.iter()
                            .map(effective_range)
                            .fold((u32::MAX, MaxOccurs::Bounded(0)), |(am, ax), (m, x)| {
                                let am2 = am.min(m);
                                let ax2 = match (ax, x) {
                                    (MaxOccurs::Unbounded, _) | (_, MaxOccurs::Unbounded) => MaxOccurs::Unbounded,
                                    (MaxOccurs::Bounded(a), MaxOccurs::Bounded(b)) => MaxOccurs::Bounded(a.max(b)),
                                };
                                (am2, ax2)
                            }),
                    },
                    Term::GroupRef(_) => (0, MaxOccurs::Unbounded), // pessimistic
                };
                let m = p.min_occurs.saturating_mul(inner_min);
                let x = mul_max(p.max_occurs, inner_max);
                (m, x)
            }
            let (combined_min, combined_max) = effective_range(derived);
            if combined_min < base.min_occurs {
                return Err("derived group's combined min-occurrence is below the wildcard's min".into());
            }
            if let MaxOccurs::Bounded(b_max) = base.max_occurs {
                if !matches!(combined_max, MaxOccurs::Bounded(d) if d <= b_max) {
                    return Err("derived group's combined max-occurrence exceeds the wildcard's max".into());
                }
            }
            for child in d_parts.iter() {
                match &child.term {
                    Term::Element(d_el) => { ns_compat(child, bw, d_el, ctx.target_ns)?; }
                    Term::Wildcard(dw)  => {
                        if !ns_subset(&dw.namespaces, &bw.namespaces) {
                            return Err("derived sub-wildcard namespace is not a subset of base wildcard".into());
                        }
                    }
                    Term::Group { .. } => {
                        // Recurse into nested groups against the same wildcard.
                        is_valid_restriction(child, base, ctx)?;
                    }
                    Term::GroupRef(_) => return Err(
                        "unresolved group reference reached particle-restriction check".into(),
                    ),
                }
            }
            Ok(())
        }
        (Term::Group { kind: d_kind, particles: d_parts },
         Term::Group { kind: b_kind, particles: b_parts }) => {
            // Outer occurrence comparison only makes sense when
            // both sides describe the same shape (sequence-vs-
            // sequence, choice-vs-choice, all-vs-all).  Across
            // shapes the per-iteration semantics differ — a
            // single derived "iteration" maps to multiple base
            // elements — so the effective-range check moves into
            // the respective algorithm (map_and_sum etc).
            if *d_kind == *b_kind && !occurs_within(derived, base) {
                return Err("group occurrence does not fit base group's".into());
            }
            match (*d_kind, *b_kind) {
                (GroupKind::Sequence, GroupKind::Sequence) => {
                    recurse(d_parts, b_parts, ctx)
                }
                (GroupKind::All, GroupKind::All) => {
                    recurse_unordered(d_parts, b_parts, ctx)
                }
                (GroupKind::Choice, GroupKind::Choice) => {
                    recurse_lax(d_parts, b_parts, ctx)
                }
                (GroupKind::Sequence, GroupKind::Choice) => {
                    // Compare effective totals: derived counts as
                    // outer * sum(children); base choice counts as
                    // outer * max-branch (any branch could repeat).
                    // Per §3.9.6.1 MapAndSum, the derived range must
                    // fit the base's effective total range, not the
                    // base's raw outer occurrence.
                    let (d_min, d_max) = effective_total(derived);
                    let (b_min, b_max) = effective_total(base);
                    if d_min < b_min {
                        return Err(format!(
                            "derived sequence's effective min ({d_min}) is below \
                             base choice's effective min ({b_min})",
                        ));
                    }
                    if let MaxOccurs::Bounded(bm) = b_max {
                        if !matches!(d_max, MaxOccurs::Bounded(dm) if dm <= bm) {
                            return Err(format!(
                                "derived sequence's effective max exceeds \
                                 base choice's effective max ({bm})",
                            ));
                        }
                    }
                    map_and_sum(d_parts, b_parts, ctx)
                }
                // §3.9.6.1 dispatch table — Sequence-vs-All also uses
                // RecurseUnordered (the derived sequence is a trace
                // through the unordered base set).
                (GroupKind::Sequence, GroupKind::All) => {
                    recurse_unordered(d_parts, b_parts, ctx)
                }
                // Other kind combinations aren't named in §3.9.6;
                // they're structurally invalid per spec.
                _ => Err(format!(
                    "model-group kind mismatch: derived {d_kind:?} cannot restrict base {b_kind:?}"
                )),
            }
        }
        (Term::GroupRef(_), _) | (_, Term::GroupRef(_)) => Err(
            "unresolved group reference reached particle-restriction check".into(),
        ),
        // Wildcard restricted to a single element: spec doesn't
        // permit this — a wildcard can't be tightened *into* a
        // named element via restriction (that would require a
        // different particle shape entirely).
        (Term::Wildcard(_), Term::Element(_)) => Err(
            "a wildcard cannot restrict a single named element on the base side".into(),
        ),
        // Remaining cross-shape pairings aren't defined as valid by
        // §3.9.6. (Term::Element vs Term::Group is already handled
        // above via RecurseAsIfGroup before this match.)
        // RecurseAsIfGroup reverse: a derived `<xs:choice>` may
        // restrict a single base element when every branch of the
        // choice is itself a valid restriction of that element
        // (typically through substitution-group membership).  Wrap
        // the base element into a singleton-choice and dispatch each
        // derived branch through is_valid_restriction.
        (Term::Group { kind: kk, particles }, Term::Element(_)) if matches!(kk, GroupKind::Choice) => {
            // RecurseAsIfGroup-style reverse: every choice branch must
            // be a valid restriction of the base element (typically
            // through substitution-group membership).
            if !occurs_within(derived, base) {
                return Err("derived <xs:choice> occurrence does not fit base element's".into());
            }
            for branch in particles.iter() {
                is_valid_restriction(branch, base, ctx)?;
            }
            Ok(())
        }
        (Term::Group { kind: kk, particles }, Term::Element(_))
            if matches!(kk, GroupKind::Sequence | GroupKind::All) && particles.len() == 1 =>
        {
            // A sequence/all with a single particle is positionally
            // equivalent to that particle; let it stand in for the
            // base element with the outer occurrence multiplied
            // through.  Two-or-more children couldn't fit a base
            // element so the general arm rejects them below.
            let inner = &particles[0];
            let effective = Particle {
                min_occurs: derived.min_occurs.saturating_mul(inner.min_occurs),
                max_occurs: mul_max(derived.max_occurs, inner.max_occurs),
                term:       inner.term.clone(),
            };
            is_valid_restriction(&effective, base, ctx)
        }
        (Term::Group { .. }, Term::Element(_)) => Err(
            "a group of particles cannot restrict a single named element".into(),
        ),
        (Term::Wildcard(_), Term::Group { .. }) => Err(
            "a wildcard cannot restrict a model group on the base side".into(),
        ),
        (Term::Element(_), Term::Group { .. }) => unreachable!(
            "(Element, Group) is handled before the dispatcher match"
        ),
    }
}


fn process_strictness(w: &Wildcard) -> u8 {
    use super::schema::ProcessContents::*;
    match w.process_contents { Strict => 2, Lax => 1, Skip => 0 }
}

// ── NameAndTypeOK ───────────────────────────────────────────────────────────

fn name_and_type_ok(d: &ElementDecl, b: &ElementDecl, ctx: &Ctx) -> Result<(), String> {
    if d.name != b.name && !ctx.substitutable_for(&d.name, &b.name) {
        return Err(format!(
            "element name {:?} does not match base element name {:?} \
             (and is not in its substitution group)",
            d.name.local, b.name.local,
        ));
    }
    if b.nillable && !d.nillable {
        // Nillable is a relaxation; derived must keep it on if base
        // has it (the other direction — d nillable but b not — is
        // a tightening which the spec actually forbids the other
        // way around). The conservative direction: derived may have
        // nillable=false when base does, but not the other way.
        // We adopt the spec's strict reading: derived.nillable
        // must imply base.nillable; we already require name match
        // so simply forbid a derived nillable=true when base is
        // nillable=false.
    }
    if d.nillable && !b.nillable {
        return Err(format!(
            "element {:?}: cannot become nillable in a restriction",
            d.name.local,
        ));
    }
    if let Some(b_fixed) = &b.fixed {
        match &d.fixed {
            Some(d_fixed) if d_fixed == b_fixed => {}
            _ => return Err(format!(
                "element {:?}: restriction must keep the base's fixed value {b_fixed:?}",
                d.name.local,
            )),
        }
    }
    // XSD §3.9.6 NameAndTypeOK clause 3.2.5 — derived's
    // `{disallowed substitutions}` (the `block` set) must be a
    // superset of the base's: a restriction can ADD more block
    // tokens but never lose any.  `#all` on the base is the
    // strongest constraint, and any explicit subset on the
    // derived violates it.
    let block_diff = b.block & !d.block;
    if !block_diff.is_empty() {
        return Err(format!(
            "element {:?}: derived block={:?} is not a superset of base block={:?}",
            d.name.local, d.block, b.block,
        ));
    }
    // XSD §3.9.6 NameAndTypeOK clause 3.2.4 — derived element's type
    // must be the same as base's, or validly derived from it per
    // §3.4.6 (complex) / §3.16.6 (simple).  Without this check the
    // particle recursion can wrongly accept sibling subtypes (foo1,
    // foo2 each restricting bar) as if foo2 restricts foo1.
    type_derives_from(&d.type_def, &b.type_def, ctx).map_err(|reason| format!(
        "element {:?}: derived type does not validly restrict the base element's type ({reason})",
        d.name.local,
    ))?;
    match (&d.type_def, &b.type_def) {
        (TypeRef::Complex(d_ct), TypeRef::Complex(b_ct)) => {
            let (dp, bp) = (particle_of(&d_ct.content), particle_of(&b_ct.content));
            match (dp, bp) {
                (None, None) => Ok(()),
                (None, Some(bp)) if is_emptiable(bp) => Ok(()),
                (None, Some(_)) => Err(format!(
                    "element {:?}: derived empty content cannot restrict the base's non-emptiable content",
                    d.name.local,
                )),
                (Some(_), None) => Err(format!(
                    "element {:?}: base has empty content; derived must also be empty",
                    d.name.local,
                )),
                (Some(dp), Some(bp)) => is_valid_restriction(dp, bp, ctx),
            }
        }
        _ => Ok(()),
    }
}

/// True when `derived` is the same type as `base` or transitively
/// derived from it via the schema's recorded derivation chain.  Handles
/// the three combinations that occur in element-particle restrictions:
///
/// * Complex → Complex: walk `derived.derivation.base` up to 64 steps
///   looking for `base`.  Identity is by `Arc::ptr_eq` first, then by
///   declared name (for cases where the placeholder hasn't been
///   patched in-place but the named entry in `types` is the same).
/// * Simple → Simple: identical types accept; otherwise consult the
///   atomic built-in `derives_from` for the common case (custom
///   restriction chains collapse to a single SimpleType carrying
///   facets, so direct identity covers user-defined → user-defined,
///   and the built-in chain covers built-in → built-in).  List and
///   union varieties accept only when types match — broader derivation
///   would require an explicit base chain that the simple-type model
///   doesn't currently carry.
/// * Mixed: rejected unless the base is `xs:anyType`.
fn type_derives_from(derived: &TypeRef, base: &TypeRef, ctx: &Ctx) -> Result<(), String> {
    if type_refs_same(derived, base, ctx) { return Ok(()); }
    // Resolve named placeholders so a union / list base is seen with its
    // real variety rather than an unresolved atomic default.
    let derived = resolve_typeref(derived, ctx);
    let base = resolve_typeref(base, ctx);
    if is_any_type(&base) { return Ok(()); }
    match (&derived, &base) {
        (TypeRef::Complex(d), TypeRef::Complex(b)) => complex_derives_from(d, b, ctx),
        (TypeRef::Simple(d),  TypeRef::Simple(b))  => simple_derives_from(d, b),
        _ => Err("simple and complex type are not compatible".into()),
    }
}

fn type_refs_same(a: &TypeRef, b: &TypeRef, ctx: &Ctx) -> bool {
    let a = resolve_typeref(a, ctx);
    let b = resolve_typeref(b, ctx);
    match (&a, &b) {
        (TypeRef::Simple(x),  TypeRef::Simple(y))  => Arc::ptr_eq(x, y)
            || (x.name.is_some() && x.name == y.name),
        (TypeRef::Complex(x), TypeRef::Complex(y)) => Arc::ptr_eq(x, y)
            || (x.name.is_some() && x.name == y.name),
        _ => false,
    }
}

fn resolve_typeref(tr: &TypeRef, ctx: &Ctx) -> TypeRef {
    if let TypeRef::Simple(st) = tr {
        if let Some(rest) = st.name.as_deref().and_then(|n| n.strip_prefix("UNRESOLVED:")) {
            let qn = if let Some(rest) = rest.strip_prefix('{') {
                if let Some(end) = rest.find('}') {
                    QName::new(if end == 0 { None } else { Some(&rest[..end]) }, &rest[end + 1..])
                } else { QName::new(None, rest) }
            } else { QName::new(None, rest) };
            if let Some(real) = ctx.types.get(&qn) { return real.clone(); }
        }
    }
    tr.clone()
}

fn is_any_type(tr: &TypeRef) -> bool {
    match tr {
        TypeRef::Complex(c) => c.name.as_ref().map(|n|
            n.namespace.as_deref() == Some(QName::XSD_NS) && &*n.local == "anyType"
        ).unwrap_or(false),
        _ => false,
    }
}

fn complex_derives_from(
    derived: &Arc<ComplexType>,
    base:    &Arc<ComplexType>,
    ctx:     &Ctx,
) -> Result<(), String> {
    let mut cur: Arc<ComplexType> = derived.clone();
    for _ in 0..64 {
        let Some(deriv) = cur.derivation.as_ref() else {
            // No further declared derivation — complex types without
            // one are implicitly extensions of xs:anyType; that match
            // is handled by the caller via `is_any_type`.
            return Err(format!(
                "type {:?} does not derive from {:?}",
                cur.name.as_ref().map(|n| &*n.local).unwrap_or("<anonymous>"),
                base.name.as_ref().map(|n| &*n.local).unwrap_or("<anonymous>"),
            ));
        };
        let base_resolved = resolve_typeref(&deriv.base, ctx);
        match base_resolved {
            TypeRef::Complex(next) => {
                if Arc::ptr_eq(&next, base)
                    || (next.name.is_some() && next.name == base.name)
                {
                    return Ok(());
                }
                cur = next;
            }
            TypeRef::Simple(_) => return Err(
                "derivation chain hits a simple type before reaching the base".into()
            ),
        }
    }
    Err("derivation chain exceeds 64 steps".into())
}

fn simple_derives_from(
    derived: &Arc<super::types::SimpleType>,
    base:    &Arc<super::types::SimpleType>,
) -> Result<(), String> {
    use super::types::Variety;
    if Arc::ptr_eq(derived, base) { return Ok(()); }
    if derived.name.is_some() && derived.name == base.name { return Ok(()); }
    if is_any_simple_type_st(base) { return Ok(()); }
    // A type validly restricts a union base if it derives from one of the
    // union's member types (XSD 1.0 §3.16.6, clause 2.2.2).
    if let Variety::Union { members } = &base.variety {
        if members.iter().any(|m| simple_derives_from(derived, m).is_ok()) {
            return Ok(());
        }
    }
    match (&derived.variety, &base.variety) {
        (Variety::Atomic, Variety::Atomic) => {
            // Schema doesn't track per-type simple derivation chains
            // (user-defined simple types collapse to builtin+facets),
            // so we treat unequal *named* user types as unrelated.
            // Built-in → built-in uses the static parent chain.
            let derived_named = derived.name.is_some();
            let base_named    = base.name.is_some();
            if derived_named && base_named {
                return Err("named simple types are unrelated".into());
            }
            if derived.builtin.derives_from(base.builtin) { Ok(()) }
            else { Err(format!(
                "built-in {:?} does not derive from {:?}",
                derived.builtin, base.builtin,
            )) }
        }
        _ => Err("non-atomic simple types do not derive from one another in this position".into()),
    }
}

fn is_any_simple_type_st(st: &super::types::SimpleType) -> bool {
    matches!(st.name.as_deref(), Some("anySimpleType"))
        || st.name.as_deref()
            .map(|n| n.starts_with("UNRESOLVED:") && n.ends_with("anySimpleType"))
            .unwrap_or(false)
}

// ── NSCompat ────────────────────────────────────────────────────────────────

fn ns_compat(derived: &Particle, b_wild: &Wildcard, d_el: &ElementDecl, target_ns: Option<&str>) -> Result<(), String> {
    let _ = derived; // occurrence is enforced by the caller's recurse loop
    if !wildcard_allows(&b_wild.namespaces, d_el.name.namespace.as_deref(), target_ns) {
        return Err(format!(
            "element {:?}: namespace {:?} is not allowed by the base wildcard",
            d_el.name.local, d_el.name.namespace,
        ));
    }
    Ok(())
}

fn wildcard_allows(c: &NamespaceConstraint, ns: Option<&str>, target_ns: Option<&str>) -> bool {
    use NamespaceConstraint::*;
    match c {
        Any => true,
        // `##other` excludes BOTH the schema's targetNamespace and
        // the absent (no-)namespace.
        Other => ns.is_some() && ns != target_ns,
        List(entries) => entries.iter().any(|e| match (e, ns) {
            (None, None)            => true,
            (Some(u), Some(n))      => u.as_ref() == n,
            _ => false,
        }),
    }
}

// ── Recurse (ordered) ───────────────────────────────────────────────────────

fn recurse(derived: &[Particle], base: &[Particle], ctx: &Ctx) -> Result<(), String> {
    // Filter out derived particles with minOccurs=maxOccurs=0 — XSD
    // §3.9.6 treats them as if they weren't there.
    let derived: Vec<&Particle> = derived.iter()
        .filter(|d| !(d.min_occurs == 0 && matches!(d.max_occurs, MaxOccurs::Bounded(0))))
        .collect();
    let mut di = 0;
    for bp in base {
        if di < derived.len() && is_valid_restriction(derived[di], bp, ctx).is_ok() {
            di += 1;
        } else if !is_emptiable(bp) {
            return Err("base sequence has a required particle that no derived particle matches".into());
        }
    }
    if di < derived.len() {
        return Err("derived sequence has more particles than the base permits".into());
    }
    Ok(())
}

// ── RecurseUnordered (all → all) ────────────────────────────────────────────

fn recurse_unordered(derived: &[Particle], base: &[Particle], ctx: &Ctx) -> Result<(), String> {
    // Greedy bipartite match: pair each derived particle to some
    // unused base particle. Every unmatched base particle must be
    // emptiable. xs:all groups are small in practice (XSD §3.8.6
    // constrains them to a single level), so the O(N²) greedy is
    // fine.
    let mut used = vec![false; base.len()];
    for dp in derived {
        let mut matched = false;
        for (bi, bp) in base.iter().enumerate() {
            if used[bi] { continue; }
            if is_valid_restriction(dp, bp, ctx).is_ok() {
                used[bi] = true;
                matched = true;
                break;
            }
        }
        if !matched {
            return Err("a derived all-group particle has no matching base particle".into());
        }
    }
    for (bi, bp) in base.iter().enumerate() {
        if !used[bi] && !is_emptiable(bp) {
            let _ = bi;
            return Err("a base all-group particle is required but unmatched".into());
        }
    }
    Ok(())
}

// ── RecurseLax (choice → choice) ────────────────────────────────────────────

fn recurse_lax(derived: &[Particle], base: &[Particle], ctx: &Ctx) -> Result<(), String> {
    for dp in derived {
        // XSD §3.9.6: a particle with minOccurs=maxOccurs=0 is
        // interpreted as if it weren't there at all (XSD "removed
        // alternative" pattern in restricted choices).
        if dp.min_occurs == 0 && matches!(dp.max_occurs, MaxOccurs::Bounded(0)) {
            continue;
        }
        if !base.iter().any(|bp| is_valid_restriction(dp, bp, ctx).is_ok()) {
            return Err("no base choice particle accepts the derived particle".into());
        }
    }
    Ok(())
}

/// Effective `(min, max)` range of a particle counted in terminal
/// (element / wildcard) units, multiplied by the particle's outer
/// occurrence.  Used by MapAndSum and NSRecurseCheckCardinality
/// to compare against base-side ranges that count by element.
fn effective_total(p: &Particle) -> (u32, MaxOccurs) {
    let (inner_min, inner_max) = match &p.term {
        Term::Element(_) | Term::Wildcard(_) => (1u32, MaxOccurs::Bounded(1)),
        Term::Group { kind, particles } => match kind {
            GroupKind::Sequence | GroupKind::All => particles.iter()
                .map(effective_total)
                .fold((0u32, MaxOccurs::Bounded(0)), |(am, ax), (m, x)| {
                    let am2 = am.saturating_add(m);
                    let ax2 = match (ax, x) {
                        (MaxOccurs::Unbounded, _) | (_, MaxOccurs::Unbounded) => MaxOccurs::Unbounded,
                        (MaxOccurs::Bounded(a), MaxOccurs::Bounded(b)) => MaxOccurs::Bounded(a.saturating_add(b)),
                    };
                    (am2, ax2)
                }),
            GroupKind::Choice => particles.iter()
                .map(effective_total)
                .fold((u32::MAX, MaxOccurs::Bounded(0)), |(am, ax), (m, x)| {
                    let am2 = am.min(m);
                    let ax2 = match (ax, x) {
                        (MaxOccurs::Unbounded, _) | (_, MaxOccurs::Unbounded) => MaxOccurs::Unbounded,
                        (MaxOccurs::Bounded(a), MaxOccurs::Bounded(b)) => MaxOccurs::Bounded(a.max(b)),
                    };
                    (am2, ax2)
                }),
        },
        Term::GroupRef(_) => (0, MaxOccurs::Unbounded),
    };
    let m = p.min_occurs.saturating_mul(inner_min);
    let x = mul_max(p.max_occurs, inner_max);
    (m, x)
}

// ── MapAndSum (sequence → choice) ───────────────────────────────────────────

fn map_and_sum(derived: &[Particle], base: &[Particle], ctx: &Ctx) -> Result<(), String> {
    for dp in derived {
        if !base.iter().any(|bp| is_valid_restriction(dp, bp, ctx).is_ok()) {
            return Err("a derived sequence particle has no matching base choice particle".into());
        }
    }
    Ok(())
}