libxml_rs/xml/automata/

mod.rs

//! Automata/state machine infrastructure (§85 Phase 7).
//!
//! UPSTREAM-PARITY: Corresponds to `xmlautomata.c` / `xmlautomata.h` in libxml2.
//!
//! The libxml2 internal automata implementation is used primarily by the
//! schema/RELAX NG validation subsystems. It builds a state machine that
//! can be compiled into a regex for efficient validation.
//!
//! The automata API:
//!
//! ```c
//! xmlAutomataPtr xmlNewAutomata(void);
//! void xmlFreeAutomata(xmlAutomataPtr am);
//! int xmlAutomataSetFinalState(xmlAutomataPtr am, xmlAutomataStatePtr state);
//! xmlAutomataStatePtr xmlAutomataGetInitState(xmlAutomataPtr am);
//! int xmlAutomataCompile(xmlAutomataPtr am);
//! int xmlAutomataIsDeterministic(xmlAutomataPtr am);
//!
//! xmlAutomataStatePtr xmlAutomataNewState(xmlAutomataPtr am);
//! xmlAutomataStatePtr xmlAutomataNewTransition(xmlAutomataPtr am,
//!     xmlAutomataStatePtr from, xmlAutomataStatePtr to,
//!     const xmlChar *token, void *data);
//! xmlAutomataStatePtr xmlAutomataNewCountTrans(xmlAutomataPtr am,
//!     xmlAutomataStatePtr from, xmlAutomataStatePtr to,
//!     const xmlChar *token, void *data, int min, int max);
//! xmlAutomataStatePtr xmlAutomataNewOnceTrans(xmlAutomataPtr am,
//!     xmlAutomataStatePtr from, xmlAutomataStatePtr to,
//!     const xmlChar *token, void *data, int min, int max);
//! xmlAutomataStatePtr xmlAutomataNewAllTrans(xmlAutomataPtr am,
//!     xmlAutomataStatePtr from, xmlAutomataStatePtr to, int lax);
//! xmlAutomataStatePtr xmlAutomataNewEpsilon(xmlAutomataPtr am,
//!     xmlAutomataStatePtr from, xmlAutomataStatePtr to);
//! xmlAutomataStatePtr xmlAutomataNewCountedTrans(xmlAutomataPtr am,
//!     xmlAutomataStatePtr from, xmlAutomataStatePtr to, int counter);
//! xmlAutomataStatePtr xmlAutomataNewCounterTrans(xmlAutomataPtr am,
//!     xmlAutomataStatePtr from, xmlAutomataStatePtr to, int counter);
//! xmlAutomataStatePtr xmlAutomataNewCounter(xmlAutomataPtr am, int min, int max);
//! ```
//!
//! # Upstream contract
//!
//! Mirrors upstream `xmlautomata.c` / `xmlautomata.h`
//! (`SRC-LIBXML2-2.15.0-XMLAUTOMATA-C`, parity target libxml2 2.15.3
//! oracle): the automata builder API plus `xmlAutomataCompile` (compiles to
//! an xmlRegexp) and `xmlAutomataIsDeterministic`.
//!
//! # Conceptual behavior
//!
//! Implements a state-machine builder over the regexp engine: transitions
//! (epsilon, token, count, once, all, counter) grow an NFA that
//! `xmlAutomataCompile` lowers into an `XmlRegexp` for the schema / RELAX
//! NG validation subsystems. This is the constructor half of the regexp
//! subsystem, not an independent matcher.
//!
//! # Ownership & safety invariants
//!
//! The automata owns its state list and the compiled regexp (stored in
//! `am.regexp` on `xmlAutomataCompile`); `xmlFreeAutomata` drops both.
//! States are owned by the automata — callers hold borrowed pointers valid
//! until the automata is freed.
//!
//! # Historical quirks & epochs
//!
//! The automata/regexp pairing dates from the schema work in the 2.6
//! validation-era expansion and is stable through the 2.15.3 oracle; the
//! regexp side carries the CVE-2021-3541 fix lineage (SEC-0010), so the
//! compiled-output contract here inherits that hardening.
//!
//! # Deliberate oddities
//!
//! Counter transitions (xmlAutomataNewCountedTrans/CounterTrans) implement
//! the upstream bounded-repetition idiom that has no direct NFA analogue;
//! they are kept because schema facets compile through them.
//!
//! # Proving courts
//!
//! Schema/RELAX NG differential courts compile facets through this builder;
//! cargo test covers the automata unit suites (determinism checks and
//! compiled-regexp execution).
//!
//! # Tempting simplifications that would break parity
//!
//! Do not bypass the builder and construct regexes directly: the schema
//! layer calls the xmlAutomata* entry points and observes their state/
//! regexp behavior. Do not drop the determinism check — schema
//! compilation relies on it.

use crate::abi::allocator::{xmlFreeImpl, xmlMallocImpl};
use crate::xml::regex::{xmlRegFreeRegexp, xmlRegexpCompile, xmlRegexpIsDeterministic, XmlRegexp};
use core::ffi::c_int;
use core::ptr;

/// Opaque pointer to an automata state.
pub type XmlAutomataStatePtr = *mut XmlAutomataState;

/// Opaque pointer to an automata.
pub type XmlAutomataPtr = *mut XmlAutomata;

/// UPSTREAM-PARITY: Corresponds to `_xmlAutomata` in libxml2.
#[derive(Debug)]
#[repr(C)]
pub struct XmlAutomata {
    /// List of all states.
    states: Vec<*mut XmlAutomataState>,
    /// The initial state.
    init_state: Option<*mut XmlAutomataState>,
    /// Last error code.
    error: c_int,
}

/// UPSTREAM-PARITY: Corresponds to `_xmlAutomataState` in libxml2.
#[derive(Debug)]
#[repr(C)]
pub struct XmlAutomataState {
    /// Transitions from this state.
    transitions: Vec<AutomataTransition>,
}

/// A transition in the automata.
#[derive(Debug)]
#[repr(C)]
pub struct AutomataTransition {
    /// Token to match (null means epsilon/any).
    token: Option<u8>,
    /// Minimum count (for counted transitions).
    min: c_int,
    /// Maximum count (for counted transitions).
    max: c_int,
    /// Target state.
    to: Option<*mut XmlAutomataState>,
    /// Whether this is a "once" (consuming) transition.
    once: bool,
    /// Whether this is an "all" (any character) transition.
    all: bool,
    /// Whether this is an epsilon transition.
    epsilon: bool,
    /// Counter ID for counted transitions.
    counter: c_int,
    /// User data.
    data: *mut core::ffi::c_void,
}

// SAFETY: These types are only accessed through C-compatible raw pointers
// in the automata API. The internal Vecs are properly managed.
unsafe impl Send for XmlAutomata {}
unsafe impl Sync for XmlAutomata {}
unsafe impl Send for XmlAutomataState {}
unsafe impl Sync for XmlAutomataState {}

/// Create a new automata.
///
/// UPSTREAM-PARITY: `xmlNewAutomata()`
///
/// # SAFETY
///
/// The function touches crate-global state only; it is safe
/// as long as the caller respects the library's global
/// initialization/cleanup ordering (xmlInitParser before use,
/// xmlCleanupParser only after all users are done).
///
/// Violating the global lifecycle ordering, or calling this after
/// teardown or from a signal handler, is undefined behavior.
#[no_mangle]
pub unsafe extern "C" fn xmlNewAutomata() -> XmlAutomataPtr {
    let am = xmlMallocImpl(core::mem::size_of::<XmlAutomata>()) as XmlAutomataPtr;
    if am.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        core::ptr::write(&mut (*am).states, Vec::new());
        (*am).init_state = None;
        (*am).error = 0;
    }
    am
}

/// Free an automata.
///
/// UPSTREAM-PARITY: `xmlFreeAutomata()`
///
/// # SAFETY
///
/// - `am` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlFreeAutomata(am: XmlAutomataPtr) {
    if am.is_null() {
        return;
    }
    unsafe {
        // Free all states
        for &state in &(*am).states {
            if !state.is_null() {
                core::ptr::drop_in_place(&mut (*state).transitions);
                xmlFreeImpl(state as *mut core::ffi::c_void);
            }
        }
        // Drop the states Vec
        core::ptr::drop_in_place(&mut (*am).states);
        // Note: since 11.1-Z.2 (R-000176) the compiled regexp is returned
        // caller-owned by xmlAutomataCompile (upstream 2.15 xmlregexp.c), so
        // the automata no longer owns or frees it.
        xmlFreeImpl(am as *mut core::ffi::c_void);
    }
}

/// Create a new automata state.
///
/// UPSTREAM-PARITY: `xmlAutomataNewState()`
///
/// # SAFETY
///
/// - `am` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewState(am: XmlAutomataPtr) -> XmlAutomataStatePtr {
    if am.is_null() {
        return ptr::null_mut();
    }
    let state = xmlMallocImpl(core::mem::size_of::<XmlAutomataState>()) as XmlAutomataStatePtr;
    if state.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        core::ptr::write(&mut (*state).transitions, Vec::new());
        // Add to the automata's state list
        (*am).states.push(state);
        // Set as init state if first
        if (*am).init_state.is_none() {
            (*am).init_state = Some(state);
        }
    }
    state
}

/// Set a state as the final (accepting) state.
///
/// UPSTREAM-PARITY: `xmlAutomataSetFinalState()`
///
/// # SAFETY
///
/// - `_am`, `_state` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub const unsafe extern "C" fn xmlAutomataSetFinalState(
    _am: XmlAutomataPtr,
    _state: XmlAutomataStatePtr,
) -> c_int {
    // In our implementation, final states are determined by the compiled regex.
    // This is a no-op for the automata builder; final states are handled during
    // compilation.
    0
}

/// Get the initial state of the automata.
///
/// UPSTREAM-PARITY: `xmlAutomataGetInitState()`
///
/// # SAFETY
///
/// - `am` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataGetInitState(am: XmlAutomataPtr) -> XmlAutomataStatePtr {
    if am.is_null() {
        return ptr::null_mut();
    }
    unsafe { (*am).init_state.unwrap_or(ptr::null_mut()) }
}

/// Add an epsilon (empty) transition between two states.
///
/// UPSTREAM-PARITY: `xmlAutomataNewEpsilon()`
///
/// # SAFETY
///
/// - `am`, `from`, `to` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewEpsilon(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
) -> XmlAutomataStatePtr {
    if am.is_null() || from.is_null() || to.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        (*from).transitions.push(AutomataTransition {
            token: None,
            min: 0,
            max: 0,
            to: Some(to),
            once: false,
            all: false,
            epsilon: true,
            counter: -1,
            data: ptr::null_mut(),
        });
    }
    from
}

/// Add a character transition between two states.
///
/// UPSTREAM-PARITY: `xmlAutomataNewTransition()`
///
/// # SAFETY
///
/// - `am`, `from`, `to`, `token`, `_data` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewTransition(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
    token: *const core::ffi::c_char,
    _data: *mut core::ffi::c_void,
) -> XmlAutomataStatePtr {
    if am.is_null() || from.is_null() || to.is_null() {
        return ptr::null_mut();
    }
    let tok = if token.is_null() {
        None
    } else {
        // Take the first byte of the token string
        unsafe { Some(*token as u8) }
    };
    unsafe {
        (*from).transitions.push(AutomataTransition {
            token: tok,
            min: 0,
            max: 0,
            to: Some(to),
            once: false,
            all: false,
            epsilon: false,
            counter: -1,
            data: ptr::null_mut(),
        });
    }
    from
}

/// Add a counted transition with min/max bounds (upstream xmlautomata.h:
/// `(am, from, to, token, min, max, data)` — the candidate previously
/// swapped `min`/`max` with `data`, misreading five registers; R-000176).
///
/// UPSTREAM-PARITY: `xmlAutomataNewCountTrans()`
///
/// # SAFETY
///
/// - `am`, `from`, `to`, `token`, `data` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewCountTrans(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
    token: *const core::ffi::c_char,
    min: c_int,
    max: c_int,
    _data: *mut core::ffi::c_void,
) -> XmlAutomataStatePtr {
    if am.is_null() || from.is_null() || to.is_null() {
        return ptr::null_mut();
    }
    let tok = if token.is_null() {
        None
    } else {
        unsafe { Some(*token as u8) }
    };
    unsafe {
        (*from).transitions.push(AutomataTransition {
            token: tok,
            min,
            max,
            to: Some(to),
            once: false,
            all: false,
            epsilon: false,
            counter: -1,
            data: ptr::null_mut(),
        });
    }
    from
}

/// Add a "once" transition (consumes exactly once within bounds; upstream
/// order `(am, from, to, token, min, max, data)` — R-000176).
///
/// UPSTREAM-PARITY: `xmlAutomataNewOnceTrans()`
///
/// # SAFETY
///
/// - `am`, `from`, `to`, `token`, `data` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewOnceTrans(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
    token: *const core::ffi::c_char,
    min: c_int,
    max: c_int,
    _data: *mut core::ffi::c_void,
) -> XmlAutomataStatePtr {
    if am.is_null() || from.is_null() || to.is_null() {
        return ptr::null_mut();
    }
    let tok = if token.is_null() {
        None
    } else {
        unsafe { Some(*token as u8) }
    };
    unsafe {
        (*from).transitions.push(AutomataTransition {
            token: tok,
            min,
            max,
            to: Some(to),
            once: true,
            all: false,
            epsilon: false,
            counter: -1,
            data: ptr::null_mut(),
        });
    }
    from
}

/// Add a transition that matches any character.
///
/// UPSTREAM-PARITY: `xmlAutomataNewAllTrans()`
///
/// # SAFETY
///
/// - `am`, `from`, `to` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewAllTrans(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
    _lax: c_int,
) -> XmlAutomataStatePtr {
    if am.is_null() || from.is_null() || to.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        (*from).transitions.push(AutomataTransition {
            token: None,
            min: 0,
            max: 0,
            to: Some(to),
            once: false,
            all: true,
            epsilon: false,
            counter: -1,
            data: ptr::null_mut(),
        });
    }
    from
}

/// Add a transition associated with a counter.
///
/// UPSTREAM-PARITY: `xmlAutomataNewCountedTrans()`
///
/// # SAFETY
///
/// - `am`, `from`, `to` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewCountedTrans(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
    counter: c_int,
) -> XmlAutomataStatePtr {
    if am.is_null() || from.is_null() || to.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        (*from).transitions.push(AutomataTransition {
            token: None,
            min: 0,
            max: 0,
            to: Some(to),
            once: false,
            all: false,
            epsilon: false,
            counter,
            data: ptr::null_mut(),
        });
    }
    from
}

/// Add a transition gated by a counter value.
///
/// UPSTREAM-PARITY: `xmlAutomataNewCounterTrans()`
///
/// # SAFETY
///
/// - `am`, `from`, `to` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewCounterTrans(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
    counter: c_int,
) -> XmlAutomataStatePtr {
    if am.is_null() || from.is_null() || to.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        (*from).transitions.push(AutomataTransition {
            token: None,
            min: 0,
            max: 0,
            to: Some(to),
            once: false,
            all: false,
            epsilon: false,
            counter,
            data: ptr::null_mut(),
        });
    }
    from
}

/// Create a new counter with min/max bounds.
///
/// UPSTREAM-PARITY: `xmlAutomataNewCounter()`
///
/// # SAFETY
///
/// - `_am` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub const unsafe extern "C" fn xmlAutomataNewCounter(
    _am: XmlAutomataPtr,
    _min: c_int,
    _max: c_int,
) -> c_int {
    // Counters are tracked by the automata; return a simple counter ID.
    // In our simplified implementation, return 0 to indicate the first counter.
    0
}

/// Compile the automata into a regex (upstream xmlregexp.c 2.15:
/// caller-owned `xmlRegexp *` return — R-000176, the candidate previously
/// returned an int error code and boxed the regexp into the automata).
///
/// UPSTREAM-PARITY: `xmlAutomataCompile()`
///
/// This builds a regex pattern string from the automata's state machine and
/// compiles it using the regex engine. The returned regexp is owned by the
/// caller (free with `xmlRegFreeRegexp`), exactly as upstream.
///
/// # SAFETY
///
/// - `am` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataCompile(am: XmlAutomataPtr) -> *mut XmlRegexp {
    if am.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        // Build a regex pattern from the automata transitions.
        // This is a simplified implementation that handles linear chains
        // of character transitions.
        let mut pattern = Vec::new();
        let init = match (*am).init_state {
            Some(s) => s,
            None => return ptr::null_mut(), // Empty automata — nothing to compile
        };

        // Walk the state machine to build a pattern.
        build_pattern_from_automata(init, &mut pattern);

        if pattern.is_empty() {
            return ptr::null_mut();
        }

        // Compile the pattern
        pattern.push(0); // null-terminate
        let compiled = xmlRegexpCompile(pattern.as_ptr());
        if compiled.is_null() {
            (*am).error = -1;
            return ptr::null_mut();
        }

        compiled
    }
}

/// Build a regex pattern string from the automata state machine.
///
/// This walks the states starting from `state` and emits regex tokens
/// for each transition.
unsafe fn build_pattern_from_automata(state: XmlAutomataStatePtr, pattern: &mut Vec<u8>) {
    if state.is_null() {
        return;
    }

    let transitions = &(*state).transitions;
    if transitions.is_empty() {
        return;
    }

    if transitions.len() == 1 {
        let t = &transitions[0];
        if t.epsilon {
            // Follow epsilon transition
            if let Some(to) = t.to {
                build_pattern_from_automata(to, pattern);
            }
        } else if t.all {
            pattern.push(b'.');
            if let Some(to) = t.to {
                build_pattern_from_automata(to, pattern);
            }
        } else if let Some(tok) = t.token {
            pattern.push(tok);
            if let Some(to) = t.to {
                build_pattern_from_automata(to, pattern);
            }
        }
    } else {
        // Multiple transitions — this is an alternation
        pattern.push(b'(');
        for (i, t) in transitions.iter().enumerate() {
            if i > 0 {
                pattern.push(b'|');
            }
            if let Some(tok) = t.token {
                pattern.push(tok);
            } else if t.all {
                pattern.push(b'.');
            }
            if let Some(to) = t.to {
                // Check if target has further transitions
                if !(*to).transitions.is_empty() {
                    // Follow the chain
                    let mut sub = Vec::new();
                    build_pattern_from_automata(to, &mut sub);
                    pattern.extend(sub);
                }
            }
        }
        pattern.push(b')');
    }
}

/// Check if the compiled automata is deterministic.
///
/// Report whether the automata's language is deterministic (upstream
/// xmlregexp.c 2.15 `xmlAutomataIsDeterminist` — computed on the automata,
/// independent of a stored compiled regexp; the candidate compiles a
/// throwaway regexp and checks its determinism).
///
/// UPSTREAM-PARITY: `xmlAutomataIsDeterminist()`
///
/// Returns 1 if deterministic, 0 if not, -1 for a NULL automata (upstream
/// xmlregexp.c: `if (am == NULL) return(-1);`).
///
/// # SAFETY
///
/// - `am` must be valid pointers (or NULL
///   where the upstream C contract allows), obtained from the
///   matching constructor/owner and not yet freed; the callee may
///   take or keep ownership exactly as the C API specifies.
///
/// The caller must not race this call with concurrent mutation of the
/// same objects from other threads (per-object state is not internally
/// synchronized). Violating any of the above is undefined behavior.
///
/// Exercised by the C-API differential courts
/// (courts/suites/data-abi/*-family-probe.c) and the CLI differential
/// courts; those pass byte-for-byte against the upstream oracle.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataIsDeterministic(am: XmlAutomataPtr) -> c_int {
    if am.is_null() {
        return -1;
    }
    unsafe {
        let compiled = xmlAutomataCompile(am);
        if compiled.is_null() {
            // No accepting path — the (empty) language is trivially
            // deterministic.
            return 1;
        }
        let ret = xmlRegexpIsDeterministic(compiled as *const XmlRegexp);
        xmlRegFreeRegexp(compiled);
        ret
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Tests
// ═══════════════════════════════════════════════════════════════════════════════

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

    /// Test that a fresh automata is created and released.
    ///
    /// # Safety
    ///
    /// - `am` returned by `xmlNewAutomata` must be non-NULL (asserted) and
    ///   not yet freed; `xmlFreeAutomata` takes ownership, so it must be
    ///   called exactly once and never concurrently with other uses of `am`.
    #[test]
    fn test_new_automata() {
        unsafe {
            let am = xmlNewAutomata();
            assert!(!am.is_null());
            xmlFreeAutomata(am);
        }
    }

    /// Test that the free/get-init/compile entry points accept NULL.
    ///
    /// # Safety
    ///
    /// - `xmlFreeAutomata`, `xmlAutomataGetInitState` and `xmlAutomataCompile`
    ///   accept NULL per the upstream C contract.
    /// - `xmlAutomataCompile` returns NULL here; when it returns non-NULL the
    ///   caller owns the resulting regexp and must free it exactly once with
    ///   `xmlRegFreeRegexp`.
    #[test]
    fn test_new_automata_null_safety() {
        unsafe {
            xmlFreeAutomata(ptr::null_mut());
            assert!(xmlAutomataGetInitState(ptr::null_mut()).is_null());
            assert!(xmlAutomataCompile(ptr::null_mut()).is_null());
        }
    }

    /// Test that a new state becomes the automata init state.
    ///
    /// # Safety
    ///
    /// - `am` must be a non-NULL, not-yet-freed pointer from `xmlNewAutomata`.
    /// - The state pointer returned by `xmlAutomataNewState` is owned by the
    ///   automata: it is only borrowed here and must not be freed separately.
    /// - `xmlFreeAutomata(am)` releases the automata and all its states
    ///   exactly once, after all borrowed state pointers are dead.
    #[test]
    fn test_new_state() {
        unsafe {
            let am = xmlNewAutomata();
            let state = xmlAutomataNewState(am);
            assert!(!state.is_null());
            let init = xmlAutomataGetInitState(am);
            assert_eq!(init, state);
            xmlFreeAutomata(am);
        }
    }

    /// Test adding an epsilon transition between two states.
    ///
    /// # Safety
    ///
    /// - `am`, `s1`, `s2` must be non-NULL pointers obtained from
    ///   `xmlNewAutomata` and `xmlAutomataNewState` on the same automata and
    ///   not yet freed; the states are borrowed and owned by `am`.
    /// - The returned pointer aliases `s1` and must not be freed separately.
    /// - `xmlFreeAutomata(am)` runs exactly once at the end.
    #[test]
    fn test_epsilon_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let result = xmlAutomataNewEpsilon(am, s1, s2);
            assert!(!result.is_null());
            assert_eq!(result, s1);
            xmlFreeAutomata(am);
        }
    }

    /// Test adding a character transition with a one-byte token.
    ///
    /// # Safety
    ///
    /// - `am`, `s1`, `s2` must be valid, not-yet-freed pointers owned by the
    ///   automata as described for `test_epsilon_transition`.
    /// - `token` must point to a valid NUL-terminated C string that lives for
    ///   the duration of the call (only its first byte is read).
    /// - The result aliases `s1`; the automata is freed exactly once at the
    ///   end with `xmlFreeAutomata`.
    #[test]
    fn test_char_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let token = c"a".as_ptr() as *const core::ffi::c_char;
            let result = xmlAutomataNewTransition(am, s1, s2, token, ptr::null_mut());
            assert!(!result.is_null());
            assert_eq!(result, s1);
            xmlFreeAutomata(am);
        }
    }

    /// Test adding a counted transition with min/max bounds.
    ///
    /// # Safety
    ///
    /// - `am`, `s1`, `s2` must be valid, not-yet-freed pointers from the
    ///   automata constructors; `token` must point to a valid NUL-terminated
    ///   C string valid for the call (only its first byte is read).
    /// - The returned pointer aliases `s1`; `xmlFreeAutomata(am)` is the only
    ///   free and runs exactly once.
    #[test]
    fn test_count_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let token = c"a".as_ptr() as *const core::ffi::c_char;
            let result = xmlAutomataNewCountTrans(am, s1, s2, token, 1, 5, ptr::null_mut());
            assert!(!result.is_null());
            xmlFreeAutomata(am);
        }
    }

    /// Test adding an any-character transition.
    ///
    /// # Safety
    ///
    /// - `am`, `s1`, `s2` must be non-NULL, not-yet-freed automata-owned
    ///   pointers; the result aliases `s1` and must not be freed separately;
    ///   `xmlFreeAutomata(am)` runs exactly once at the end.
    #[test]
    fn test_all_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let result = xmlAutomataNewAllTrans(am, s1, s2, 0);
            assert!(!result.is_null());
            xmlFreeAutomata(am);
        }
    }

    /// Test adding a once (consuming) transition.
    ///
    /// # Safety
    ///
    /// - `am`, `s1`, `s2` must be valid non-NULL automata-owned pointers;
    ///   `token` must point to a valid NUL-terminated C string valid for the
    ///   call; the result aliases `s1`; `xmlFreeAutomata(am)` runs exactly
    ///   once at the end.
    #[test]
    fn test_once_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let token = c"x".as_ptr() as *const core::ffi::c_char;
            let result = xmlAutomataNewOnceTrans(am, s1, s2, token, 0, 1, ptr::null_mut());
            assert!(!result.is_null());
            xmlFreeAutomata(am);
        }
    }

    /// Test counter-based counted/counter transitions.
    ///
    /// # Safety
    ///
    /// - `am`, `s1`, `s2` must be valid non-NULL pointers owned by the
    ///   automata and not yet freed; the counter ID and the transition
    ///   pointers returned are owned by `am` (borrowed here) and must not be
    ///   freed separately; `xmlFreeAutomata(am)` frees everything exactly
    ///   once.
    #[test]
    fn test_counter_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let cid = xmlAutomataNewCounter(am, 0, 10);
            let r1 = xmlAutomataNewCountedTrans(am, s1, s2, cid);
            assert!(!r1.is_null());
            let r2 = xmlAutomataNewCounterTrans(am, s2, s1, cid);
            assert!(!r2.is_null());
            xmlFreeAutomata(am);
        }
    }

    /// Test that compiling an automata with no accepting path yields NULL.
    ///
    /// # Safety
    ///
    /// - `am` must be a non-NULL, not-yet-freed pointer from `xmlNewAutomata`.
    /// - `xmlAutomataCompile` returns NULL here, so no regexp is owned; when
    ///   it returns non-NULL the caller must free it exactly once with
    ///   `xmlRegFreeRegexp`.
    /// - `xmlFreeAutomata(am)` runs exactly once at the end.
    #[test]
    fn test_compile_empty() {
        unsafe {
            let am = xmlNewAutomata();
            let result = xmlAutomataCompile(am);
            // No accepting path — NULL (upstream xmlRegEpxFromParse has no
            // final-state path to compile).
            assert!(result.is_null());
            xmlFreeAutomata(am);
        }
    }

    /// Test that marking a state final returns 0 (no-op in this builder).
    ///
    /// # Safety
    ///
    /// - `am` and `state` must be valid, not-yet-freed automata-owned
    ///   pointers; `xmlAutomataSetFinalState` does not take ownership, and
    ///   the automata is freed exactly once with `xmlFreeAutomata` at the end.
    #[test]
    fn test_set_final_state() {
        unsafe {
            let am = xmlNewAutomata();
            let state = xmlAutomataNewState(am);
            let result = xmlAutomataSetFinalState(am, state);
            assert_eq!(result, 0);
            xmlFreeAutomata(am);
        }
    }

    /// Test that an uncompiled automata reports deterministic (1).
    ///
    /// # Safety
    ///
    /// - `am` must be a valid, not-yet-freed pointer from `xmlNewAutomata`;
    ///   `xmlAutomataIsDeterministic` borrows it, and `xmlFreeAutomata(am)`
    ///   runs exactly once at the end.
    #[test]
    fn test_is_deterministic_not_compiled() {
        unsafe {
            let am = xmlNewAutomata();
            // Before compilation, should return 1 (assumed deterministic)
            assert_eq!(xmlAutomataIsDeterministic(am), 1);
            xmlFreeAutomata(am);
        }
    }

    /// Test that `xmlAutomataNewState` returns NULL for a NULL automata.
    ///
    /// # Safety
    ///
    /// - Passing NULL to `xmlAutomataNewState` is accepted by the C contract
    ///   and returns NULL without dereferencing the argument.
    #[test]
    fn test_null_automata_returns_null_state() {
        unsafe {
            let state = xmlAutomataNewState(ptr::null_mut());
            assert!(state.is_null());
        }
    }

    /// Test that `xmlAutomataGetInitState` returns NULL for a NULL automata.
    ///
    /// # Safety
    ///
    /// - Passing NULL to `xmlAutomataGetInitState` is accepted and returns
    ///   NULL without dereferencing; the result is not dereferenced here.
    #[test]
    fn test_null_automata_returns_null_init() {
        unsafe {
            assert!(xmlAutomataGetInitState(ptr::null_mut()).is_null());
        }
    }

    /// Test that new states are appended to the automata state list.
    ///
    /// # Safety
    ///
    /// - `am` must be non-NULL and not yet freed; `(*am).states` is read
    ///   directly, so `am` must point to a live `XmlAutomata` (guaranteed by
    ///   `xmlNewAutomata` here) and must not be mutated concurrently.
    /// - `s1` and `s2` are owned by the automata and not freed separately;
    ///   `xmlFreeAutomata(am)` runs exactly once at the end.
    #[test]
    fn test_new_state_adds_to_list() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            assert!(!s1.is_null());
            assert!(!s2.is_null());
            assert_ne!(s1, s2);
            assert_eq!((*am).states.len(), 2);
            xmlFreeAutomata(am);
        }
    }

    /// Test that a two-transition chain compiles to a caller-owned regexp.
    ///
    /// # Safety
    ///
    /// - `am`, `s1`, `s2`, `s3` must be valid non-NULL automata-owned
    ///   pointers; `token_a` and `token_b` must point to valid NUL-terminated
    ///   strings valid for their respective calls.
    /// - `xmlAutomataCompile` returns a caller-owned regexp here: it must be
    ///   freed exactly once with `xmlRegFreeRegexp` before `xmlFreeAutomata`
    ///   releases the automata.
    #[test]
    fn test_compile_simple_chain() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let s3 = xmlAutomataNewState(am);
            let token_a = c"a".as_ptr() as *const core::ffi::c_char;
            let token_b = c"b".as_ptr() as *const core::ffi::c_char;
            xmlAutomataNewTransition(am, s1, s2, token_a, ptr::null_mut());
            xmlAutomataNewTransition(am, s2, s3, token_b, ptr::null_mut());
            let result = xmlAutomataCompile(am);
            // Caller-owned regexp (upstream 2.15): the chain compiles to a
            // non-NULL regexp.
            assert!(!result.is_null());
            xmlRegFreeRegexp(result);
            xmlFreeAutomata(am);
        }
    }
}