为何无法传递以trait表示的闭包？Rust解析组合器问题

背景 #

我正在实现解析组合器，每个解析组合器都是可变闭包，外部代码通过提供的blanket实现的Parser<T> trait来调用组合器函数。

代码示例 #

// 外部代码区域，不可修改

type ParseResult<I, T> = Result<(I, T), String>;

trait Parser<T> {
    fn parse<'a>(&mut self, input: &'a str) -> ParseResult<&'a str, T>;
}

// 解析组合器的blanket实现
impl<F, T> Parser<T> for F
where F: FnMut(&str) -> ParseResult<&str, T> {
    fn parse<'a>(&mut self, input: &'a str) -> ParseResult<&'a str, T> {
        self(input)
    }
}

// 外部组合器示例
fn external_combinator<P, T>(parser: P) -> impl FnMut(&str) -> ParseResult<&str, T>
where P: Parser<T> {
    preceded_by(char_parser('a'), parser)
}

// 我的代码开始

fn char_parser(c: char) -> impl Fn(&str) -> ParseResult<&str, char> {
    move |input: &str| {
        let Some(rest) = input.strip_prefix(c) else {
            return Err(format!("Input does not begin with {c}"));
        };
        Ok((rest, c))
    }
}

fn delimited_by<Extracted>(
    begin_char: char,
    final_char: char,
    mut parser: impl Parser<Extracted>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
    move |input: &str| {
        let parse_begin = char_parser(begin_char);

        // 为什么不能把parser传给preceded_by？          <-- 错误位置
        let precede = preceded_by(parse_begin, &mut parser);

        let parse_final = char_parser(final_char);
        followed_by(precede, parse_final)(input)
    }
}

fn followed_by<Extracted, _Discard>(
    mut parser_a: impl Parser<Extracted>,
    mut parser_b: impl Parser<_Discard>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
    move |input: &str| {
        let (rest, new_value) = parser_a.parse(input)?;
        let (rest, _) = parser_b.parse(rest)?;
        Ok((rest, new_value))
    }
}

fn preceded_by<Extracted, _Discard>(
    mut parser_a: impl Parser<_Discard>,
    mut parser_b: impl Parser<Extracted>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
    move |input: &str| {
        let (rest, _) = parser_a.parse(input)?;
        parser_b.parse(rest)
    }
}

// 外部代码区域，不可修改
fn main() {
    let my_combinator = delimited_by('a', 'b', char_parser('c'));
    let mut final_combinator = external_combinator(my_combinator);

    match final_combinator("data") {
        Ok(_) => println!("OK"),
        Err(_) => println!("Error")
    }
}

编译错误 #

error[E0277]: trait约束 `&mut impl Parser<Extracted>: Parser<_>` 未满足
  --> src/main.rs:43:48
   |
43 |         let precede = preceded_by(parse_begin, &mut parser);
   |                       -----------              ^^^^^^^^^^^ 类型`impl Parser<Extracted>`未实现trait `for<'a> FnMut(&'a str)`，而这是`&mut impl Parser<Extracted>: Parser<_>`所需的
   |                       |
   |                       此调用引入的约束要求
   |
   = note: 需要`&mut impl Parser<Extracted>`实现`for<'a> FnOnce(&'a str)`
note: 需要`&mut impl Parser<Extracted>`实现`Parser<_>`
  --> src/main.rs:10:12
   |
10 | impl<F, T> Parser<T> for F
   |            ^^^^^^^^^     ^
11 | where F: FnMut(&str) -> ParseResult<&str, T> {
   |                         -------------------- 未满足的trait约束在此处引入
note: 此约束由`preceded_by`中的要求定义
  --> src/main.rs:63:24
   |
61 | fn preceded_by<Extracted, _Discard>(
   |    ----------- 此函数中的约束要求
62 |     mut parser_a: impl Parser<_Discard>,
63 |     mut parser_b: impl Parser<Extracted>
   |                        ^^^^^^^^^^^^^^^^^ `preceded_by`中的此约束要求
help: 考虑进一步限制该约束
   |
37 |     mut parser: impl Parser<Extracted> + for<'a> FnMut(&'a str)
   |                                        ++++++++++++++++++++++++

问题咨询 #

尝试添加for<'a> FnMut(&'a str)约束后引发更多错误，且无法修改外部提供的Parser<T> trait。现提出以下问题：

1. 如何不使用dyn或Box将parser从delimited_by传递到preceded_by？
2. 若无法实现上述需求，如何改写代码以满足external_combinator的trait要求？（不可修改任何外部代码）
3. 请以入门友好的方式解释为何无法传递该parser参数。

问题解答 #

1. 不使用dyn/Box传递parser的方法 #

直接将parser的所有权转移给preceded_by即可，不需要传递可变引用。修改delimited_by的代码，移除参数的mut修饰（不需要在函数内部修改parser，只需转移所有权），并直接传递parser而非&mut parser：

fn delimited_by<Extracted>(
    begin_char: char,
    final_char: char,
    parser: impl Parser<Extracted>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
    move |input: &str| {
        let parse_begin = char_parser(begin_char);
        // 直接转移parser的所有权给preceded_by
        let precede = preceded_by(parse_begin, parser);
        let parse_final = char_parser(final_char);
        followed_by(precede, parse_final)(input)
    }
}

核心是利用Rust的move语义：delimited_by返回的闭包会持有parser的所有权，preceded_by再从闭包中获取parser的所有权，最终整个组合器链都合法持有所需的解析器，编译器可以正常推导类型约束。

2. 替代方案：手动实现组合逻辑 #

如果无法通过所有权转移传递parser，可以直接在delimited_by的闭包中手动实现组合逻辑，避免调用preceded_by和followed_by：

fn delimited_by<Extracted>(
    begin_char: char,
    final_char: char,
    mut parser: impl Parser<Extracted>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
    move |input: &str| {
        // 手动实现开头字符匹配
        let Some(rest) = input.strip_prefix(begin_char) else {
            return Err(format!("Expected '{}'", begin_char));
        };
        // 调用目标parser
        let (rest, value) = parser.parse(rest)?;
        // 手动实现结尾字符匹配
        let Some(rest) = rest.strip_prefix(final_char) else {
            return Err(format!("Expected '{}'", final_char));
        };
        Ok((rest, value))
    }
}

这种方式不需要传递parser给其他函数，直接在闭包内调用其parse方法，返回的闭包仍然是impl FnMut，满足external_combinator对Parser trait的要求（通过blanket impl自动实现）。

3. 为什么无法传递&mut parser的原因 #

问题出在trait约束的推导限制：

• 外部提供的Parser trait有一个「自动实现规则」：只要某个类型是FnMut(&str) -> ParseResult<&str, T>，就自动给它实现Parser<T>。但反过来，实现Parser<T>的类型不一定是FnMut——你完全可以手动给一个非闭包类型实现Parser。
• 当你传递&mut parser给preceded_by时，preceded_by要求参数是impl Parser，所以编译器需要证明&mut impl Parser<Extracted>这个类型也实现了Parser。但要满足自动实现规则，&mut impl Parser<Extracted>必须是FnMut类型。
• 但编译器只知道parser实现了Parser，不知道它是不是FnMut（因为可能是手动实现的Parser），所以无法推导出&mut parser满足FnMut的约束，也就无法通过自动实现规则获得Parser trait，最终报错。

简单说：你手里的parser是个「符合Parser规则的东西」，但编译器不确定它是不是闭包。当你取它的可变引用时，这个引用要想符合Parser规则，必须本身是闭包，但编译器没法证明这一点，所以不让你这么传。

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