Rustにおけるトレイト実装を用いた関数の多重定義とコンパイラの振る舞いに関して


# 企図と実装に関して

お世話様です。

  * nightly-x86_64-pc-windows-msvc
  * rustc 1.74.0-nightly (bdb0fa3ee 2023-09-19)

を用いております。

RustのIteratorを拡張する場合どのようになるのか学ぶことを目的にしてfilter相当の機能を実装し、理解を深めようとしました。

そのコードが以下になります。

[code]

    pub struct WinnowIterator<I, P>(I, P);
    
    pub trait Winnow<I, P> {
        fn winnow(self, pred: P) -> WinnowIterator<I, P>;
    }
    
    impl<T, I: Iterator<Item = T>, P: Fn(&T) -> bool> Winnow<I, P> for I {
        fn winnow(self, pred: P) -> WinnowIterator<I, P> {
            WinnowIterator(self, pred)
        }
    }
    
    impl<T, I: Iterator<Item = T>, P: Fn(&T) -> bool> Iterator for WinnowIterator<I, P> {
        type Item = T;
    
        fn next(&mut self) -> Option<Self::Item> {
            for s in self.0.by_ref() {
                if (self.1)(&s) {
                    return Some(s);
                } else {
                    continue;
                }
            }
            None
        }
    }
    
    //Dispatchを確認するために追加した実装ここから
    pub enum WinnowTypes {
        Even,
        Odd,
    }
    
    impl<I: Iterator<Item = i32>> Winnow<I, WinnowTypes> for I {
        fn winnow(self, pred: WinnowTypes) -> WinnowIterator<I, WinnowTypes> {
            WinnowIterator(self, pred)
        }
    }
    
    impl<I: Iterator<Item = i32>> Iterator for WinnowIterator<I, WinnowTypes> {
        type Item = i32;
    
        fn next(&mut self) -> Option<Self::Item> {
            fn odd(i: &i32) -> bool {
                i & 1 == 1
            }
    
            fn even(i: &i32) -> bool {
                i & 1 == 0
            }
    
            for e in self.0.by_ref() {
                let tmp = match self.1 {
                    WinnowTypes::Even => even(&e),
                    WinnowTypes::Odd => odd(&e),
                };
    
                return if tmp { Some(e) } else { continue };
            }
    
            None
        }
    }
    
    //Dispatchを確認するために追加した実装ここまで
    
    #[cfg(test)]
    mod tests {
        use super::Winnow;
        use crate::winnow::WinnowTypes::{Even, Odd};
        use std::fmt::Debug;
    
        fn assert<T: PartialEq + Debug, E: Iterator<Item = T>, A: Iterator<Item = T>>(
            mut expected: E,
            mut actual: A,
        ) {
            for e in expected.by_ref() {
                match actual.by_ref().next() {
                    None => unreachable!(),
                    Some(a) => assert_eq!(e, a),
                }
            }
    
            match actual.by_ref().next() {
                None => assert!(true),
                Some(_) => unreachable!(),
            }
        }
        #[test]
        fn closure_test() {
            let expected = (0..10).filter(|i| i & 1 == 0);
    
            //ここで、|i| i & 1 == 0とすると、コンパイルエラーが発生する。
            let actual = (0..10).winnow(|i| i & 1 == 0);
    
            assert(expected, actual)
        }
    
        #[test]
        fn enum_test() {
            let actual = (0..10).winnow(Even);
            let expected = (0..10).filter(|x| x % 2 == 0);
            assert(expected, actual);
    
            let actual = (0..10).winnow(Odd);
            let expected = (0..10).filter(|x| x % 2 != 0);
            assert(expected, actual)
        }
    }
    
    
[/code]

# 発生したエラーと試してみたこと

概略、型Tを返却するイテレータに、PredicatorとなるClosureを指定したfilter関数と全く同じ働きを持つ実装と、i32のイテレータのみを対象とし、OddまたはEvenの列挙子を取る実装をそれぞれに配置してテストしている形になっています。

これらは概ね僕の意図通り動いてくれたのですが、`closure_test` の部分で、与えるべきClosureがfilter関数は`|x| x & 1 ==
0`で構わないのに対して、僕の自作したwinnowでは`|i: &_| i & 1 ==
0`のように引数が参照であることを明示する必要があり、これを明示しない場合、以下のようなコンパイルエラーが発生しました。

[code]

    error: implementation of `FnOnce` is not general enough
      --> src\winnow.rs:89:16
       |
    89 |         let actual = (0..10).winnow(|i| i & 1 == 0);
       |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `FnOnce` is not general enough
       |
       = note: closure with signature `fn(&'2 i32) -> bool` must implement `FnOnce<(&'1 i32,)>`, for any lifetime `'1`...
       = note: ...but it actually implements `FnOnce<(&'2 i32,)>`, for some specific lifetime `'2`
    
    
[/code]

エラーの内容を読み解くとどうやら所与のClosureがFnOnceとして評価されているように見受けられます。

但し、 **//Dispatchを確認するために追加した実装ここから** から **//Dispatchを確認するために追加した実装ここまで**
をコメントアウトし、

`fn enum_test()`もコメントアウトすると、問題なくコンパイルが通るのでFnとして評価されていると理解しました。

# 質問の趣旨

当該コンパイルエラーに関してはClosureの引数に参照で有ることを指定することで望む動作はしますから、実用上問題は無いと僕は現状考えています。

しかしながら、一見すると何の関係もない実装を追加した結果何故このようなコンパイルエラーが発生し、そして`＆＿`を明示することで解決できたのかがどうしても理解できません。

この件に関して何か知見をお持ちの方は何卒ご教授いただきますようよろしくお願い申し上げます。




<https://github.com/rust-lang/rust/issues/64373> に基づいて説明してみます。  
「特殊ケース」まではそこそこ自信ありますが、「本題」は挙動から見た推論になってしまったことをご了承ください。

## 高階トレイト境界 (HRTB)

既にご存じかもしれませんが一応。  
ご提示のコードに、 `P: Fn(&T) -> bool`
のようなトレイト境界がありますが、参照なので当然ライフタイムパラメータが省略されているはずです。これは内部的には `P: for<'a> Fn(&'a T)
-> bool` となっており、全ての `'a` に対して、 `Fn('a T) -> bool` であることを要求しています。これを高階トレイト境界
(HRTB) と呼びます。

参考： <https://doc.rust-jp.rs/rust-nomicon-ja/hrtb.html>

## クロージャの型推論

`let f = |a| foo(a);` と書いた場合と `let g = |a: &_| foo(a);`
と書いた場合では推論のされ方に違いがあり、前者は `fn(?A) -> ?B`、後者は `for<'a> fn(&'a ?C) -> ?D`
のように一旦解釈されるそうです。  
この後は、例えば `?A` が `&'a i32` のように推論されるだけで、後からHRTBを満たすようにはならないわけです。

実際、以下のようなコードを書くとコンパイルエラーになりますが、`|a: &_|` のように型注釈を入れるとコンパイルが通ります。

[code]

    fn hoge(_: impl Fn(&i32)) {}
    
    fn main() {
        // コンパイルエラー
        let f = |a| ();
        hoge(f);
    }
    
[/code]

## 特殊ケース

では、なぜ以下のようなコードがコンパイルできるのかというと、引数に直接渡したクロージャは、関数の引数の型情報を使った、特殊な推論が行われることがあるからです。

[code]

    (0..10).filter(|i| i & 1 == 0)
    
[/code]

`std::iter::Iterator` の [filter](https://doc.rust-
lang.org/stable/std/iter/trait.Iterator.html#method.filter) は以下のような引数を取ります。

[code]

    fn filter<P>(self, predicate: P) -> Filter<Self, P>
    where
        Self: Sized,
        P: FnMut(&Self::Item) -> bool,
    
[/code]

前述の通り、 `P: FnMut(&Self::Item) -> bool` は `P: for<'a> FnMut(&'a Self::Item) ->
bool` ですから、この情報から `|i| i & 1 == 0` もHRTBを満たすように推論できるというわけです。

とはいえ、例えば `Some` で包むだけでコンパイルが通らなくなりますし、常にいい感じに推論してくれるというわけでもないようです。

[code]

    fn hoge(_: impl Fn(&i32)) {}
    
    fn fuga(_: Option<impl Fn(&i32)>) {}
    
    fn main() {
        // OK
        hoge(|a| ());
    
        // コンパイルエラー
        fuga(Some(|a| ()));
    
        // OK
        fuga(Some(|a: &_| ()));
    }
    
[/code]

## 本題

長々と書きましたが、結局以下のコメントで大体あっていそうです。  
個人的には、これが問題というよりは、 `(0..10).filter(|i| i & 1 == 0)`
がコンパイル通る方が寧ろ例外的だという印象はありますが。

> <https://users.rust-lang.org/t/implementation-of-fnonce-is-not-general-
> enough/68294/2> これと同じ問題を踏み抜いた可能性があるかも

今回の件はおそらく、 `winnow`
の2つの実装のうちどちらを使うのかを、クロージャをHRTBにするか決定する段階ではまだ決定できていないためだと思われます。  
そういう意味だと、`Option<impl Fn(&i32)>` のケースは `Some` と `None`
のどちらに合わせるか決める必要があるという意味で、やはり似てるのかもしれません。

[code]

    impl<T, I: Iterator<Item = T>, P: Fn(&T) -> bool> Winnow<I, P> for I {
        fn winnow(self, pred: P) -> WinnowIterator<I, P> {
            WinnowIterator(self, pred)
        }
    }
    
    impl<I: Iterator<Item = i32>> Winnow<I, WinnowTypes> for I {
        fn winnow(self, pred: WinnowTypes) -> WinnowIterator<I, WinnowTypes> {
            WinnowIterator(self, pred)
        }
    }
    
[/code]




<https://github.com/rust-lang/rust/issues/64373> に基づいて説明してみます。  
「特殊ケース」まではそこそこ自信ありますが、「本題」は挙動から見た推論になってしまったことをご了承ください。

## 高階トレイト境界 (HRTB)

既にご存じかもしれませんが一応。  
ご提示のコードに、 `P: Fn(&T) -> bool`
のようなトレイト境界がありますが、参照なので当然ライフタイムパラメータが省略されているはずです。これは内部的には `P: for<'a> Fn(&'a T)
-> bool` となっており、全ての `'a` に対して、 `Fn('a T) -> bool` であることを要求しています。これを高階トレイト境界
(HRTB) と呼びます。

参考： <https://doc.rust-jp.rs/rust-nomicon-ja/hrtb.html>

## クロージャの型推論

`let f = |a| foo(a);` と書いた場合と `let g = |a: &_| foo(a);`
と書いた場合では推論のされ方に違いがあり、前者は `fn(?A) -> ?B`、後者は `for<'a> fn(&'a ?C) -> ?D`
のように一旦解釈されるそうです。  
この後は、例えば `?A` が `&'a i32` のように推論されるだけで、後からHRTBを満たすようにはならないわけです。

実際、以下のようなコードを書くとコンパイルエラーになりますが、`|a: &_|` のように型注釈を入れるとコンパイルが通ります。

[code]

    fn hoge(_: impl Fn(&i32)) {}
    
    fn main() {
        // コンパイルエラー
        let f = |a| ();
        hoge(f);
    }
    
[/code]

## 特殊ケース

では、なぜ以下のようなコードがコンパイルできるのかというと、引数に直接渡したクロージャは、関数の引数の型情報を使った、特殊な推論が行われることがあるからです。

[code]

    (0..10).filter(|i| i & 1 == 0)
    
[/code]

`std::iter::Iterator` の [filter](https://doc.rust-
lang.org/stable/std/iter/trait.Iterator.html#method.filter) は以下のような引数を取ります。

[code]

    fn filter<P>(self, predicate: P) -> Filter<Self, P>
    where
        Self: Sized,
        P: FnMut(&Self::Item) -> bool,
    
[/code]

前述の通り、 `P: FnMut(&Self::Item) -> bool` は `P: for<'a> FnMut(&'a Self::Item) ->
bool` ですから、この情報から `|i| i & 1 == 0` もHRTBを満たすように推論できるというわけです。

とはいえ、例えば `Some` で包むだけでコンパイルが通らなくなりますし、常にいい感じに推論してくれるというわけでもないようです。

[code]

    fn hoge(_: impl Fn(&i32)) {}
    
    fn fuga(_: Option<impl Fn(&i32)>) {}
    
    fn main() {
        // OK
        hoge(|a| ());
    
        // コンパイルエラー
        fuga(Some(|a| ()));
    
        // OK
        fuga(Some(|a: &_| ()));
    }
    
[/code]

## 本題

長々と書きましたが、結局以下のコメントで大体あっていそうです。  
個人的には、これが問題というよりは、 `(0..10).filter(|i| i & 1 == 0)`
がコンパイル通る方が寧ろ例外的だという印象はありますが。

> <https://users.rust-lang.org/t/implementation-of-fnonce-is-not-general-
> enough/68294/2> これと同じ問題を踏み抜いた可能性があるかも

今回の件はおそらく、 `winnow`
の2つの実装のうちどちらを使うのかを、クロージャをHRTBにするか決定する段階ではまだ決定できていないためだと思われます。  
そういう意味だと、`Option<impl Fn(&i32)>` のケースは `Some` と `None`
のどちらに合わせるか決める必要があるという意味で、やはり似てるのかもしれません。

[code]

    impl<T, I: Iterator<Item = T>, P: Fn(&T) -> bool> Winnow<I, P> for I {
        fn winnow(self, pred: P) -> WinnowIterator<I, P> {
            WinnowIterator(self, pred)
        }
    }
    
    impl<I: Iterator<Item = i32>> Winnow<I, WinnowTypes> for I {
        fn winnow(self, pred: WinnowTypes) -> WinnowIterator<I, WinnowTypes> {
            WinnowIterator(self, pred)
        }
    }
    
[/code]

