libxml_rs/xml/automata/

mod.rs

//! Automata/state machine infrastructure (§85 Phase 7).
//!
//! UPSTREAM-PARITY: Corresponds to `xmlautomata.c` / `xmlautomata.h` in libxml2.
//!
//! libxml2's 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);
//! ```

use crate::abi::allocator::{xmlFreeImpl, xmlMallocImpl};
use crate::xml::regex::{
    xmlRegExecPushString, xmlRegFreeExecCtxt, xmlRegFreeRegexp, xmlRegNewExecCtxt,
    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.
#[repr(C)]
pub struct XmlAutomata {
    /// Compiled regex, set by xmlAutomataCompile.
    regexp: Option<Box<XmlRegexp>>,
    /// 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.
#[repr(C)]
pub struct XmlAutomataState {
    /// Transitions from this state.
    transitions: Vec<AutomataTransition>,
}

/// A transition in the automata.
#[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()`
#[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).regexp, None as Option<Box<XmlRegexp>>);
        core::ptr::write(&mut (*am).states, Vec::new());
        (*am).init_state = None;
        (*am).error = 0;
    }
    am
}

/// Free an automata.
///
/// UPSTREAM-PARITY: `xmlFreeAutomata()`
#[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);
        // Drop the compiled regexp if any
        let _ = (*am).regexp.take();
        xmlFreeImpl(am as *mut core::ffi::c_void);
    }
}

/// Create a new automata state.
///
/// UPSTREAM-PARITY: `xmlAutomataNewState()`
#[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()`
#[no_mangle]
pub 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()`
#[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()`
#[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()`
#[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-PARITY: `xmlAutomataNewCountTrans()`
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewCountTrans(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
    token: *const core::ffi::c_char,
    _data: *mut core::ffi::c_void,
    min: c_int,
    max: c_int,
) -> 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-PARITY: `xmlAutomataNewOnceTrans()`
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataNewOnceTrans(
    am: XmlAutomataPtr,
    from: XmlAutomataStatePtr,
    to: XmlAutomataStatePtr,
    token: *const core::ffi::c_char,
    _data: *mut core::ffi::c_void,
    min: c_int,
    max: c_int,
) -> 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()`
#[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()`
#[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()`
#[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()`
#[no_mangle]
pub 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-PARITY: `xmlAutomataCompile()`
///
/// This builds a regex pattern string from the automata's state machine and
/// compiles it using the regex engine.
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataCompile(am: XmlAutomataPtr) -> c_int {
    if am.is_null() {
        return -1;
    }
    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 0, // Empty automata — nothing to compile
        };

        // Walk the state machine to build a pattern.
        // For now, build a simple pattern from the transition chain.
        if build_pattern_from_automata(&*am, init, &mut pattern).is_err() {
            (*am).error = -1;
            return -1;
        }

        if pattern.is_empty() {
            return 0;
        }

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

        (*am).regexp = Some(Box::from_raw(compiled));
        0
    }
}

/// 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(
    am: &XmlAutomata,
    state: XmlAutomataStatePtr,
    pattern: &mut Vec<u8>,
) -> Result<(), ()> {
    if state.is_null() {
        return Ok(());
    }

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

    if transitions.len() == 1 {
        let t = &transitions[0];
        if t.epsilon {
            // Follow epsilon transition
            if let Some(to) = t.to {
                return build_pattern_from_automata(am, to, pattern);
            }
        } else if t.all {
            pattern.push(b'.');
            if let Some(to) = t.to {
                return build_pattern_from_automata(am, to, pattern);
            }
        } else if let Some(tok) = t.token {
            pattern.push(tok);
            if let Some(to) = t.to {
                return build_pattern_from_automata(am, 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();
                    let _ = build_pattern_from_automata(am, to, &mut sub);
                    pattern.extend(sub);
                }
            }
        }
        pattern.push(b')');
    }

    Ok(())
}

/// Check if the compiled automata is deterministic.
///
/// UPSTREAM-PARITY: `xmlAutomataIsDeterministic()`
#[no_mangle]
pub unsafe extern "C" fn xmlAutomataIsDeterministic(am: XmlAutomataPtr) -> c_int {
    if am.is_null() {
        return 0;
    }
    unsafe {
        match &(*am).regexp {
            Some(regexp) => xmlRegexpIsDeterministic(&**regexp as *const XmlRegexp),
            None => 1, // Not compiled yet — assume deterministic
        }
    }
}

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

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

    #[test]
    fn test_new_automata() {
        unsafe {
            let am = xmlNewAutomata();
            assert!(!am.is_null());
            xmlFreeAutomata(am);
        }
    }

    #[test]
    fn test_new_automata_null_safety() {
        unsafe {
            xmlFreeAutomata(ptr::null_mut());
            assert!(xmlAutomataGetInitState(ptr::null_mut()).is_null());
            assert_eq!(xmlAutomataCompile(ptr::null_mut()), -1);
        }
    }

    #[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]
    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]
    fn test_char_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let token = b"a\0".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]
    fn test_count_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let token = b"a\0".as_ptr() as *const core::ffi::c_char;
            let result = xmlAutomataNewCountTrans(am, s1, s2, token, ptr::null_mut(), 1, 5);
            assert!(!result.is_null());
            xmlFreeAutomata(am);
        }
    }

    #[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]
    fn test_once_transition() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let token = b"x\0".as_ptr() as *const core::ffi::c_char;
            let result = xmlAutomataNewOnceTrans(am, s1, s2, token, ptr::null_mut(), 0, 1);
            assert!(!result.is_null());
            xmlFreeAutomata(am);
        }
    }

    #[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]
    fn test_compile_empty() {
        unsafe {
            let am = xmlNewAutomata();
            let result = xmlAutomataCompile(am);
            assert_eq!(result, 0);
            xmlFreeAutomata(am);
        }
    }

    #[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]
    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]
    fn test_null_automata_returns_null_state() {
        unsafe {
            let state = xmlAutomataNewState(ptr::null_mut());
            assert!(state.is_null());
        }
    }

    #[test]
    fn test_null_automata_returns_null_init() {
        unsafe {
            assert!(xmlAutomataGetInitState(ptr::null_mut()).is_null());
        }
    }

    #[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]
    fn test_compile_simple_chain() {
        unsafe {
            let am = xmlNewAutomata();
            let s1 = xmlAutomataNewState(am);
            let s2 = xmlAutomataNewState(am);
            let s3 = xmlAutomataNewState(am);
            let token_a = b"a\0".as_ptr() as *const core::ffi::c_char;
            let token_b = b"b\0".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);
            assert_eq!(result, 0);
            xmlFreeAutomata(am);
        }
    }
}