ppvm_pauli_word/pattern/

contains.rs

// SPDX-FileCopyrightText: 2026 The PPVM Authors
// SPDX-License-Identifier: Apache-2.0

use super::data::{Decorated, NotIdentity, OpPattern, PauliPattern};
use ppvm_traits::char::Pauli;
use ppvm_traits::traits::PauliIter;
use std::iter::Peekable;

/// Membership test for pattern types.
///
/// Implemented by Pauli patterns over symbols (`Contains<Pauli>`) and
/// over whole words (`Contains<W: PauliIter>`); used by the masking
/// machinery to ask "does this pattern accept this concrete word?"
pub trait Contains<T> {
    /// `true` if `item` matches this pattern.
    fn contains(&self, item: &T) -> bool;
}

impl Contains<Pauli> for NotIdentity {
    fn contains(&self, item: &Pauli) -> bool {
        (*self as u8) == (*item as u8)
    }
}

impl Contains<Pauli> for OpPattern {
    fn contains(&self, item: &Pauli) -> bool {
        match self {
            OpPattern::Identity => *item == Pauli::I,
            OpPattern::Single(op) => op.contains(item),
            OpPattern::Double(left, right) => left.contains(item) || right.contains(item),
            OpPattern::AnyNonIdentity => {
                *item == Pauli::X || *item == Pauli::Y || *item == Pauli::Z
            }
            OpPattern::SingleOrIdentity(op) => op.contains(item) || *item == Pauli::I,
            OpPattern::DoubleOrIdentity(left, right) => {
                left.contains(item) || right.contains(item) || *item == Pauli::I
            }
            OpPattern::AnyPauliOrIdentity => *item == Pauli::I,
        }
    }
}

enum Step {
    NextPattern,
    DontMatch,
}

fn match_position<I: Iterator<Item = (usize, Pauli)>>(
    chars: &mut Peekable<I>,
    pattern: &OpPattern,
    pos: &usize,
) -> Step {
    for (ch_pos, ch) in chars.by_ref() {
        if ch_pos == *pos {
            if pattern.contains(&ch) {
                return Step::NextPattern;
            } else {
                return Step::DontMatch;
            }
        } else if ch == Pauli::I {
            continue;
        } else {
            // there are non-identity
            // before matching this pattern
            return Step::DontMatch;
        }
    }
    // all identity and length < pos
    Step::DontMatch
}

fn match_star<I: Iterator<Item = (usize, Pauli)>>(
    chars: &mut Peekable<I>,
    pattern: &OpPattern,
) -> Step {
    while let Some((_, ch)) = chars.peek() {
        if pattern.contains(ch) {
            chars.next();
            continue;
        } else {
            // doesn't match but ok
            // match next pattern
            return Step::NextPattern;
        }
    }
    // exhausted all Pauli all matches
    Step::NextPattern
}

fn match_repeat<I: Iterator<Item = (usize, Pauli)>>(
    chars: &mut Peekable<I>,
    pattern: &OpPattern,
    count: usize,
) -> Step {
    let mut matched = 0;
    while let Some((_, ch)) = chars.peek() {
        if pattern.contains(ch) {
            chars.next();
            matched += 1;
            if matched == count {
                return Step::NextPattern;
            }
        } else {
            // doesn't match
            if matched < count {
                return Step::DontMatch;
            } else {
                return Step::NextPattern;
            }
        }
    }
    // exhausted all Pauli all matches
    if matched == count {
        Step::NextPattern
    } else {
        Step::DontMatch
    }
}

impl<W> Contains<W> for PauliPattern
where
    W: PauliIter,
{
    fn contains(&self, item: &W) -> bool {
        let mut chars = item.iter().enumerate().peekable();
        let patterns = self.iter();
        for current in patterns {
            let step = match current {
                Decorated::Position(op, pos) => match_position(&mut chars, op, pos),
                Decorated::Star(op) => match_star(&mut chars, op),
                Decorated::Repeat(op, count) => match_repeat(&mut chars, op, *count),
            };

            match step {
                Step::NextPattern => continue,
                Step::DontMatch => return false,
            }
        }

        // check if there are remaining non-ident in `item`
        for (_, ch) in chars {
            if ch == Pauli::I {
                continue;
            } else {
                // found a non-identity
                return false;
            }
        }
        true
    }
}

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

    #[test]
    fn test_match_not_ident() {
        assert!(NotIdentity::X.contains(&Pauli::X));
        assert!(NotIdentity::Y.contains(&Pauli::Y));
        assert!(NotIdentity::Z.contains(&Pauli::Z));
    }

    #[test]
    fn test_match() {
        let pat = PauliPattern::parse("X0Y1Z2").unwrap();
        let word: PauliWord<u64> = "XYZ".into();
        assert!(pat.contains(&word));

        let pat = PauliPattern::parse("X?0Y1Z2").unwrap();
        let word: PauliWord<u64> = "XYZ".into();
        assert!(pat.contains(&word));
        let word: PauliWord<u64> = "IYZ".into();
        assert!(pat.contains(&word));

        let pat = PauliPattern::parse("[XY]0Y1Z2").unwrap();
        let word: PauliWord<u64> = "XYZ".into();
        assert!(pat.contains(&word));
        let word: PauliWord<u64> = "YYZ".into();
        assert!(pat.contains(&word));

        let pat = PauliPattern::parse("[XY]?0Y1Z2").unwrap();
        let word: PauliWord<u64> = "XYZ".into();
        assert!(pat.contains(&word));
        let word: PauliWord<u64> = "YYZ".into();
        assert!(pat.contains(&word));
        let word: PauliWord<u64> = "IYZ".into();
        assert!(pat.contains(&word));

        let pat = PauliPattern::parse("[XY]?*").unwrap();
        let word: PauliWord<u64> = "XYX".into();
        assert!(pat.contains(&word));
        let word: PauliWord<u64> = "YYX".into();
        assert!(pat.contains(&word));
        let word: PauliWord<u64> = "IYX".into();
        assert!(pat.contains(&word));

        let pat = PauliPattern::parse("[XY]?{2}Z2").unwrap();
        let word: PauliWord<u64> = "XYZ".into();
        assert!(pat.contains(&word));
        let word: PauliWord<u64> = "YYZ".into();
        assert!(pat.contains(&word));
        let word: PauliWord<u64> = "IYZ".into();
        assert!(pat.contains(&word));
    }

    #[test]
    fn test_not_match() {
        let pat: PauliPattern = "Z?*".into();
        let word: PauliWord<u64> = "XYY".into();
        assert!(!pat.contains(&word));
    }
}