Rust error[E0275]: overflow evaluating the requirement が解決できない

Question

実現したいこと

パーサコンビネータを実装しています。
このパーサコンビネータは、パースしたい対象にParserトレイトとその派生トレイトを実装することで汎用パーサを利用できるようにする形式です。例えば特定のパーサを５回繰り返すことを意味するrepeat関数は引数がrepeat(parser: impl Parser)->Repeatになっています。ここで、例えば&strはParserを実装しているのでrepeat("hello")とすることができます。また、RepeatもParserを実装しているので、repeatの結果もrepeatに渡すことができます。
Parserはパースする入力型、パーサが返す出力型、エラーの型と入力型に対するラッパ型であるInputを型引数で指定できます。例えば、「文字列をJsonという構造体にパースしたい。失敗したらJsonParseErrとしたい。入力型に追加情報はいらない」場合は、「Parse<&str, Json, JsonParseErr, SimpleInput<&str, JsonParseErr>>>」となります。Inputについては入力型のラッパ型です。例えば、「現在パースしている位置」を追加情報にしたい場合などに役立ちます。
Parserのスーパートレイトとして、TeminateParserトレイトがあります。これは、文脈自由文法でいう終端記号に対してパースを行います。ただしただの終端記号ではなく、Iterator的な終端記号のみ実装することができます。これが必要なのは、「x文字目でパースが失敗した」ということを表せるようにするためです。これを作ることで、「x文字目」という概念がない終端記号とを分類することができます。

発生している問題・分からないこと

提供しているコードで、タイトルのエラーが発生します。
一応このエラーについては調べて大枠は理解していますが、エラーの原因と回避策が思いつきませんでした。
特に私が理解できなかったのは、コード例のmain()内のケース１についてはエラーが出ますが、ケース２についてはエラーが出ないことです。
このエラーはケース２が実際にはエラーでもその前の行が同様にこのエラーだと、ケース２の診断を隠す場合があるので、ケース１をコメントアウトしてみましたが、それでもエラーは出ず、コンパイルが通りました。

エラーメッセージ

error[E0275]: overflow evaluating the requirement `SimpleInput<String, ()>: Input<String, ()>`
  --> src/main.rs:6:5
   |
6  |     <P as Parser<String, (), (), SimpleInput<String, ()>>>::parse(&mut P, &new::<String, (), SimpleInput<String, ()>>(format!("")));
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: required by a bound in `Parser::parse`
  --> src/main.rs:12:61
   |
12 | trait Parser<I: Parser<I, I, E, Input>, O, E: Clone, Input: crate::Input<I, E>>: Clone {
   |                                                             ^^^^^^^^^^^^^^^^^^ required by this bound in `Parser::parse`
13 |     fn parse(&mut self, input: &Input);
   |        ----- required by a bound in this associated function

該当のソースコード

fn main() {
    // ケース１
    <P as Parser<String, (), (), SimpleInput<String, ()>>>::parse(&mut P, &new::<String, (), SimpleInput<String, ()>>(format!("")));
    // ケース２
    <P as Parser<String, (), WrapperErr<()>, WrapperInput<_, _>>>::parse(&mut P, &new(format!("")));
}
fn new<I: Parser<I, I, E, Input>, E: Clone, Input: crate::Input<I, E>>(input: I) -> Input {
    Input::new(input)
}
trait Parser<I: Parser<I, I, E, Input>, O, E: Clone, Input: crate::Input<I, E>>: Clone {
    fn parse(&mut self, input: &Input)->Result<(Input, O),()>;
}

trait Input<I: Parser<I, I, E, Self>, E: Clone>: Sized {
    fn new(input: I) -> Self;
    fn input(&self)->&I;
    fn errs(&self)->&Vec<E>;
}
trait TerminateParser<E: Clone>: Parser<Self, Self, WrapperErr<E>, WrapperInput<Self, E>> {}

struct SimpleInput<I: Parser<I, I, E, Self>, E: Clone> {
    input: I,
    errs: Vec<E>,
}
impl<I: Parser<I, I, E, Self>, E: Clone> Input<I, E> for SimpleInput<I, E> {
    fn new(input: I) -> Self {
        SimpleInput {
            input,
            errs: vec![],
        }
    }
    fn input(&self)->&I {
        &self.input
    }
    fn errs(&self)->&Vec<E> {
        &self.errs
    }
}

#[derive(Clone)]
struct WrapperErr<E: Clone>(E);
#[derive(Clone)]
struct WrapperInput<I: TerminateParser<E>, E: Clone> {
    source: I,
    index: usize,
    errs: Vec<WrapperErr<E>>,
}
impl<I: TerminateParser<E>, E: Clone> Input<I, WrapperErr<E>> for WrapperInput<I, E> {
    fn new(input: I) -> Self {
        WrapperInput {
            source: input,
            index: 0,
            errs: vec![],
        }
    }
    fn input(&self)->&I {
        todo!() //提示していないコードに依存した処理
    }
    fn errs(&self)->&Vec<WrapperErr<E>> {
        &self.errs
    }
}

//終端記号パーサの実装
impl<E: Clone, Input: crate::Input<String, E>> Parser<String, String, E, Input> for String {
    fn parse(&mut self, _input: &Input) -> Result<(Input, String), ()> {
        todo!()
    }
}
impl<E: Clone> TerminateParser<E> for String {}

#[derive(Clone)]
struct P;
impl<I: Parser<I, I, E, Input>, O, E: Clone, Input: crate::Input<I, E>> Parser<I, O, E, Input>
    for P
{
    fn parse(&mut self, _input: &Input) -> Result<(Input, O), ()> {
        todo!()
    }
}

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

Rustのエラー情報でエラーの理解を試みました。
しかし、私のコードにこのコード例を落とし込む方法と、このエラーの回避策はわかりませんでした。

補足

環境

>rustup --version
rustup 1.27.1 (54dd3d00f 2024-04-24)
info: This is the version for the rustup toolchain manager, not the rustc compiler.
info: The currently active `rustc` version is `rustc 1.82.0 (f6e511eec 2024-10-15)`

できれば回避したいこと

このエラーを解決するうえで、できれば回避したい設計の改変

• Parserのエラーのラッパ型を一律にすること。つまり、現状のSimpleInputのラッパ型がないEも、WrapperErrのエラー位置付きエラーもすべて一緒くたにErrorラッパとし、SimpleInputなどを使う場面でもOpiton<usize>でエラー位置情報を保持しなくてはならないタイプの設計。
• Parse::parseの引数をInputトレイトではなくすこと。「位置付きエラーを利用できない」とはそもそもWrapperInputの{source, index}で実装できないということでまた「位置付きエラーを実現する」ためには、SimpleInputでは実現できない。なので、Inputトレイトを用いた今の実装が一番表現力が高い実装と考えている。

これらを避けることができない場合は、エラー解決のほうを優先します。

Comments

[bsdfan]

Parser と Input で、トレイト境界が循環しているのが良くないと思います。
Input の I: Parser<I, I, E, Self> の境界については、今回の質問にあるコードだけみると不要に思います。

[tt-44]

コメントありがとうございます。返信遅れてすみません。
ご教示の通り、InputとSimpleInputのIの境界を削除したところ問題が解決しました！
自分は今まで型の境界を「想定していない型引数を拒否するもの」と考えていましたが、「実装に最低限必要な型引数の要件」を示すものに限定したほうがいい場合もあるのですね
ベストアンサーに選びたいので同じ内容を回答欄に投稿いただけますでしょうか？

Answer 1

Parser と Input で、トレイト境界が循環しているのが良くないと思います。
Input の I: Parser<I, I, E, Self> の境界については、今回の質問にあるコードだけみると不要に思います。

trait Input<I, E: Clone>: Sized {
    // snip
}

struct SimpleInput<I, E: Clone> {
    // snip
}

impl<I, E: Clone> Input<I, E> for SimpleInput<I, E> {
    // snip
}

自分は今まで型の境界を「想定していない型引数を拒否するもの」と考えていましたが、「実装に最低限必要な型引数の要件」を示すものに限定したほうがいい場合もあるのですね

「実装に最低限必要な型引数の要件」を示すものに限定したほうがいいというより、限定すべきに近いと思います。