Rob Pike正则表达式的地道Rust重写优化问询

AI 小北

2026-8-20

正则匹配移植到Rust的优化问题

背景

《编程实践》一书中Rob Pike实现的正则匹配C代码，经Brian W Kernighan扩展后，在Rust移植时遇到核心问题：原C代码依赖'\0'哨兵做长度匹配，但Rust不支持该机制。因此移植后的代码采用字节数组切片而非UTF-8字符串简化实现，包含re_match、match_here、match_star三个函数，但存在大量冗余的长度检查。

咨询问题

如何改写这些函数以减少大量长度检查？
是否应使用迭代器而非切片作为参数？二者该如何选择？

问题1：减少长度检查的优化方案

1. 用切片模式匹配替代显式长度判断

Rust切片支持直接解构头部元素，结合模式匹配可以自然拦截空切片场景，避免重复的if re.len() == 0或if s.len() == 0判断：

fn match_here(re: &[u8], s: &[u8]) -> bool {
    match (re, s) {
        // 正则为空，匹配完成
        (b"", _) => true,
        // 字符串为空但正则未耗尽，匹配失败
        (_, b"") => false,
        // 处理非空匹配逻辑
        (re, s) => {
            let (re_head, re_rest) = re.split_first().unwrap();
            let (s_head, s_rest) = s.split_first().unwrap();
            
            if re_head == &b'.' || re_head == s_head {
                match_here(re_rest, s_rest)
            } else if re.len() >= 2 && re[1] == b'*' {
                match_star(re[0], &re[2..], s)
            } else {
                false
            }
        }
    }
}

这里通过split_first()配合模式匹配，把空切片的判断提前，后续逻辑无需再重复检查边界。

2. 封装边界处理为辅助函数

把重复的“取切片头部+判断空值”逻辑抽成辅助函数，用Option返回值替代显式长度检查：

// 取出正则的第一个字符和剩余部分，空切片返回None
fn next_re(re: &[u8]) -> Option<(u8, &[u8])> {
    re.split_first().map(|(c, rest)| (*c, rest))
}

// 取出字符串的第一个字符和剩余部分，空切片返回None
fn next_s(s: &[u8]) -> Option<(u8, &[u8])> {
    s.split_first().map(|(c, rest)| (*c, rest))
}

在函数中用if let接收结果，自然处理空切片的情况：

fn match_here(re: &[u8], s: &[u8]) -> bool {
    if let Some((re_c, re_rest)) = next_re(re) {
        if let Some((s_c, s_rest)) = next_s(s) {
            // 处理非空匹配逻辑
            (re_c == b'.' || re_c == s_c) && match_here(re_rest, s_rest)
        } else {
            // 字符串为空，正则未耗尽，匹配失败
            false
        }
    } else {
        // 正则为空，匹配完成
        true
    }
}

3. 调整递归终止条件的优先级

把空切片的判断放在递归函数的最开头，作为优先分支处理，避免后续代码重复检查：

fn match_star(c: u8, re: &[u8], s: &[u8]) -> bool {
    // 先尝试用剩余正则匹配当前字符串
    if match_here(re, s) {
        return true;
    }
    // 字符串为空时直接返回false
    let Some((s_c, s_rest)) = next_s(s) else {
        return false;
    };
    // 匹配当前字符后递归
    if c == b'.' || c == s_c {
        match_star(c, re, s_rest)
    } else {
        false
    }
}

问题2：迭代器vs切片的选择

优先用切片的场景

需要回退或随机访问：比如match_star中需要尝试匹配多个字符后，用原字符串切片回退重试，切片的子切片操作是O(1)成本，远优于迭代器的回退操作。
依赖剩余长度判断：如果逻辑中需要知道还剩多少字符未匹配，切片的len()方法是O(1)的，迭代器无法直接获取该信息。
保持原逻辑对齐：原C代码基于指针移动（类似切片的子切片操作），用切片移植更容易保持逻辑一致性，降低出错概率。

优先用迭代器的场景

仅需顺序遍历：迭代器的next()方法自然处理遍历结束的情况（返回None），无需显式检查长度，代码更简洁。
追求函数式风格：可以配合take_while、all等适配器，把匹配逻辑写得更紧凑，比如匹配*时，用迭代器遍历所有符合条件的字符。
避免panic风险：迭代器的next()不会触发panic，而切片的[1..]在空切片时会panic，迭代器的边界处理更安全。

折中方案：结合两者优势

可以在入口函数接收切片，内部根据场景切换：比如在match_star中用Peekable迭代器遍历字符，需要匹配剩余正则时，通过as_slice()转回切片：

use std::iter::Peekable;

fn match_star(c: u8, re: &[u8], mut s: Peekable<impl Iterator<Item = u8>>) -> bool {
    loop {
        if match_here(re, s.as_slice()) {
            return true;
        }
        match s.next() {
            Some(ch) if ch == c || c == b'.' => continue,
            _ => return false,
        }
    }
}

这种方式既利用了迭代器处理顺序遍历的简洁性，又保留了切片在匹配剩余正则时的便利性。

内容的提问来源于stack exchange，提问作者Daniel Näslund