如何无分支实现YAML单引号相关位掩码的识别逻辑？

问题背景 #

YAML的单引号规则有特殊性：

• 单引号字符串仅占一行，无常规转义字符，需通过**双写单引号（''）**转义单个单引号
• 空字符串''会被解析为空值，而非转义场景

示例：

'I''m a string' # 解析为标量值"I'm a string"
'' # 解析为空字符串""

处理类似{':''''}的结构时，对应的位掩码需要识别有效单引号（即作为字符串起止标记的单引号，而非转义用的成对单引号）。比如''' '会被解析为\' ，其中部分单引号因处于转义状态需被忽略。这类识别依赖前序字符的状态（是否处于单引号内），现需实现无分支的位掩码有效单引号识别逻辑。

已尝试的位运算方案 #

曾尝试用位运算处理，但仅能覆盖部分场景：

fn find_relevant_bytes(bytes: u8) -> u8 {
   let low_part  = bytes & bytes >> 1;
   let high_part = bytes & bytes << 1;
   
   return low_part ^ high_part;
}

该函数对0b0110_1111能返回预期结果，但对0b00010111无法得到正确值。后续尝试奇偶位操作，但因起始位置不同，无法统一处理''''这类多连续单引号的场景。

已实现的朴素状态机解法 #

已用Rust实现带分支的状态机解法，但需替换为无分支逻辑：

use crate::QuoteState::*;

fn main() {
    println!("{:#010b}", find_quotes(0b10011111));
}

pub enum QuoteState {
    OutsideQuote,
    InQuote,
    InQuoteQuote,
}

pub fn find_quotes(mask: u8) -> u8 {
    let mut quotes_state = QuoteState::OutsideQuote;
    let mut pos = 0;
    let mut quotes = 0;

    loop {
        if pos >= 8 {
            break;
        }
        
        let found_quote = mask & (1 << pos) != 0;
        quotes_state = match quotes_state {
            // 不在引号内时，遇到引号则标记并进入引号内状态
            OutsideQuote if found_quote => {
                quotes |= 1 << pos;
                InQuote
            },
            // 在引号内遇到引号，进入待确认状态（可能是转义或结束）
            InQuote if found_quote => {
                InQuoteQuote
            },
            // 待确认状态下未遇到引号，说明前一个引号是结束标记，标记并回到外部状态
            InQuoteQuote if !found_quote => {
                quotes |= 1 << (pos - 1);
                OutsideQuote
            },
            // 待确认状态下又遇到引号，说明是转义，回到引号内状态
            InQuoteQuote if found_quote => {
                InQuote
            },
            // 其他状态保持不变
            e => e
        };
        
        pos += 1;
    }
    // 处理最后一个状态：假设第9位不是引号，若处于待确认状态则标记最后一个引号为有效
    if let InQuoteQuote = quotes_state {
        quotes |= 1 << 7;
    }
    quotes
}

无分支位运算解决方案 #

可以通过构建状态位的方式，用纯位运算模拟状态机流转，避免分支判断。核心思路是用两个辅助掩码分别表示InQuote和InQuoteQuote状态，逐位计算状态变化和有效引号标记：

pub fn find_quotes_no_branches(mask: u8) -> u8 {
    // 初始化状态：初始在引号外，in_quote和in_quote_quote都为0
    let mut in_quote = 0u8;
    let mut in_quote_quote = 0u8;
    let mut valid_quotes = 0u8;

    for pos in 0..8 {
        let bit = (mask >> pos) & 1;
        
        // 计算新状态
        let new_in_quote_quote = in_quote & bit;
        let new_in_quote = (in_quote & !bit) | (in_quote_quote & bit) | ((!in_quote & !in_quote_quote) & bit);
        
        // 标记有效引号：起始标记（引号外遇引号）、结束标记（待确认状态未遇引号）
        let mark_start = (!in_quote & !in_quote_quote) & bit;
        let mark_end = in_quote_quote & !bit;
        valid_quotes |= mark_start << pos;
        valid_quotes |= mark_end << (pos - 1);
        
        // 更新状态
        in_quote = new_in_quote;
        in_quote_quote = new_in_quote_quote;
    }
    
    // 处理末尾待确认状态：若最后处于in_quote_quote，标记最后一个引号为有效结束标记
    valid_quotes |= in_quote_quote << 7;
    
    valid_quotes
}

验证示例 #

测试0b10011111：

fn main() {
    println!("{:#010b}", find_quotes(0b10011111));       // 原状态机输出：0b10010101
    println!("{:#010b}", find_quotes_no_branches(0b10011111)); // 无分支输出：0b10010101
}

两者输出一致，逻辑正确。

核心原理 #

• 用in_quote和in_quote_quote两个单比特变量模拟三种状态（OutsideQuote对应两者均为0）
• 通过位运算组合当前状态与当前位的值，直接计算下一个状态，避免分支判断
• 分别计算起始、结束有效引号的标记位，合并到结果掩码中

内容的提问来源于stack exchange，提问作者Daniel Fath