課題4: 高度なライフタイムパターン

マンダトリー要件（80点）

問題1: Generic Associated Types (GATs)の実装（25点）

1.1 Lending Iteratorの基本実装（15点）

以下の仕様に従って、Lending Iteratorを実装しなさい：

trait LendingIterator {
    type Item<'a> where Self: 'a;

    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

/// スライディングウィンドウイテレータ
struct WindowsIter<'data, T> {
    data: &'data [T],
    window_size: usize,
    position: usize,
}

impl<'data, T> WindowsIter<'data, T> {
    fn new(data: &'data [T], window_size: usize) -> Self {
        // TODO: 実装
        todo!()
    }
}

impl<'data, T> LendingIterator for WindowsIter<'data, T> {
    type Item<'a> = &'a [T] where Self: 'a;

    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>> {
        // TODO: 実装
        // position をインクリメントしながら、window_size のスライスを返す
        todo!()
    }
}

#[test]
fn test_windows_iter() {
    let data = vec![1, 2, 3, 4, 5];
    let mut windows = WindowsIter::new(&data, 3);

    assert_eq!(windows.next(), Some(&[1, 2, 3][..]));
    assert_eq!(windows.next(), Some(&[2, 3, 4][..]));
    assert_eq!(windows.next(), Some(&[3, 4, 5][..]));
    assert_eq!(windows.next(), None);
}

要件：

WindowsIter::new()を実装（3点）
LendingIterator::next()を実装（7点）
テストをパス（5点）

1.2 可変参照を返すLending Iterator（10点）

可変参照を返すイテレータを実装しなさい：

/// チャンク化された可変参照イテレータ
struct ChunksMut<'data, T> {
    data: &'data mut [T],
    chunk_size: usize,
}

impl<'data, T> ChunksMut<'data, T> {
    fn new(data: &'data mut [T], chunk_size: usize) -> Self {
        // TODO: 実装
        todo!()
    }
}

impl<'data, T> LendingIterator for ChunksMut<'data, T> {
    type Item<'a> = &'a mut [T] where Self: 'a;

    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>> {
        // TODO: 実装
        // ヒント: std::mem::take と split_at_mut を使う
        todo!()
    }
}

#[test]
fn test_chunks_mut() {
    let mut data = vec![1, 2, 3, 4, 5, 6];
    let mut chunks = ChunksMut::new(&mut data, 2);

    if let Some(chunk) = chunks.next() {
        chunk[0] = 10;
    }
    if let Some(chunk) = chunks.next() {
        chunk[0] = 30;
    }

    assert_eq!(data, vec![10, 2, 30, 4, 5, 6]);
}

要件：

可変参照の正しい管理（5点）
std::mem::take()の適切な使用（3点）
テストをパス（2点）

ヒント：

// std::mem::take で一時的に所有権を移動
let data = std::mem::take(&mut self.data);
let (chunk, rest) = data.split_at_mut(self.chunk_size);
self.data = rest;

---

問題2: Streaming Iteratorパターン（20点）

2.1 Streaming Iterator Traitの実装（10点）

以下のStreaming Iterator traitを実装しなさい：

trait StreamingIterator {
    type Item;

    fn advance(&mut self);
    fn get(&self) -> Option<&Self::Item>;

    fn next(&mut self) -> Option<&Self::Item> {
        self.advance();
        self.get()
    }
}

/// ウィンドウストリーミングイテレータ
struct StreamWindows<'data, T> {
    data: &'data [T],
    window_size: usize,
    current: usize,
    // TODO: 必要に応じてフィールド追加
}

impl<'data, T> StreamWindows<'data, T> {
    fn new(data: &'data [T], window_size: usize) -> Self {
        // TODO: 実装
        todo!()
    }
}

impl<'data, T> StreamingIterator for StreamWindows<'data, T> {
    type Item = [T];

    fn advance(&mut self) {
        // TODO: 実装
        todo!()
    }

    fn get(&self) -> Option<&[T]> {
        // TODO: 実装
        todo!()
    }
}

#[test]
fn test_stream_windows() {
    let data = vec![1, 2, 3, 4];
    let mut windows = StreamWindows::new(&data, 2);

    assert_eq!(windows.next(), Some(&[1, 2][..]));

    // get()で同じ要素を再度取得可能
    assert_eq!(windows.get(), Some(&[1, 2][..]));

    assert_eq!(windows.next(), Some(&[2, 3][..]));
    assert_eq!(windows.next(), Some(&[3, 4][..]));
}

要件：

advance()とget()の分離実装（5点）
同じ要素への複数回アクセスを実現（3点）
テストをパス（2点）

2.2 for_each実装（10点）

Streaming Iteratorにfor_eachメソッドを追加しなさい：

trait StreamingIterator {
    type Item;

    fn advance(&mut self);
    fn get(&self) -> Option<&Self::Item>;

    fn for_each<F>(mut self, mut f: F)
    where
        Self: Sized,
        F: FnMut(&Self::Item),
    {
        // TODO: 実装
        todo!()
    }
}

#[test]
fn test_for_each() {
    let data = vec![1, 2, 3, 4];
    let windows = StreamWindows::new(&data, 2);

    let mut count = 0;
    windows.for_each(|window| {
        count += 1;
        println!("{:?}", window);
    });

    assert_eq!(count, 3);
}

要件：

for_eachの正しい実装（6点）
Lending Iteratorでは不可能な理由を説明（2点）
テストをパス（2点）

---

問題3: Async Lifetimes（20点）

3.1 基本的なAsync Stream（10点）

以下のAsync Streamを実装しなさい：

use futures::Stream;
use std::pin::Pin;
use std::task::{Context, Poll};

/// カウントアップするストリーム
struct CounterStream {
    current: u32,
    max: u32,
}

impl CounterStream {
    fn new(max: u32) -> Self {
        // TODO: 実装
        todo!()
    }
}

impl Stream for CounterStream {
    type Item = u32;

    fn poll_next(
        mut self: Pin<&mut Self>,
        _cx: &mut Context<'_>,
    ) -> Poll<Option<Self::Item>> {
        // TODO: 実装
        todo!()
    }
}

#[tokio::test]
async fn test_counter_stream() {
    use futures::StreamExt;

    let stream = CounterStream::new(5);
    let items: Vec<u32> = stream.collect().await;

    assert_eq!(items, vec![0, 1, 2, 3, 4]);
}

要件：

poll_next()を正しく実装（5点）
Pin<&mut Self>の適切な使用（3点）
テストをパス（2点）

3.2 参照を返すAsync Stream（10点）

参照を持つAsync Streamを実装しなさい：

use async_stream::stream;
use futures::Stream;

fn line_stream<'a>(text: &'a str) -> impl Stream<Item = &'a str> + 'a {
    stream! {
        for line in text.lines() {
            yield line;
        }
    }
}

#[tokio::test]
async fn test_line_stream() {
    use futures::StreamExt;

    let text = "hello\nworld\nrust";
    let mut stream = line_stream(text);

    assert_eq!(stream.next().await, Some("hello"));
    assert_eq!(stream.next().await, Some("world"));
    assert_eq!(stream.next().await, Some("rust"));
    assert_eq!(stream.next().await, None);
}

要件：

ライフタイム'aの正しい伝播（5点）
async_stream::stream!マクロの使用（3点）
テストをパス（2点）

依存関係：

[dependencies]
async-stream = "0.3"
futures = "0.3"
tokio = { version = "1", features = ["full"] }

---

問題4: 高度なトレイト境界（15点）

4.1 HRTBsとGATsの組み合わせ（15点）

以下のフィルタ付きLending Iteratorを実装しなさい：

trait LendingIterator {
    type Item<'a> where Self: 'a;

    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;

    fn filter<F>(self, predicate: F) -> Filter<Self, F>
    where
        F: for<'a> FnMut(&Self::Item<'a>) -> bool,
        Self: Sized,
    {
        Filter {
            iter: self,
            predicate,
        }
    }
}

struct Filter<I, F> {
    iter: I,
    predicate: F,
}

impl<I, F> LendingIterator for Filter<I, F>
where
    I: LendingIterator,
    F: for<'a> FnMut(&I::Item<'a>) -> bool,
{
    type Item<'a> = I::Item<'a> where Self: 'a;

    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>> {
        // TODO: 実装
        // イテレータから次の要素を取得し、
        // predicateを満たすまでループ
        todo!()
    }
}

#[test]
fn test_filter() {
    let data = vec![1, 2, 3, 4, 5, 6];
    let windows = WindowsIter::new(&data, 2);

    let mut filtered = windows.filter(|w| w[0] % 2 == 0);

    assert_eq!(filtered.next(), Some(&[2, 3][..]));
    assert_eq!(filtered.next(), Some(&[4, 5][..]));
    assert_eq!(filtered.next(), Some(&[6][..]));  // window_size=2だが最後は1要素
}

要件：

Filter::next()の実装（8点）
HRTBs for<'a>の正しい使用（4点）
テストをパス（3点）

---

ボーナス要件（20点）

ボーナス1: データベースクエリビルダー（10点）

GATsを使ったクエリビルダーを実装しなさい：

trait QueryBuilder {
    type Query<'q>: Query where Self: 'q;

    fn select<'q>(&'q mut self, columns: &[&str]) -> Self::Query<'q>;
}

trait Query {
    fn where_clause(&mut self, condition: &str) -> &mut Self;
    fn limit(&mut self, n: usize) -> &mut Self;
    fn to_sql(&self) -> String;
}

struct SqlBuilder {
    table: String,
}

struct SqlQuery<'builder> {
    builder: &'builder SqlBuilder,
    columns: Vec<String>,
    conditions: Vec<String>,
    limit_val: Option<usize>,
}

impl SqlBuilder {
    fn new(table: &str) -> Self {
        SqlBuilder {
            table: table.to_string(),
        }
    }
}

impl QueryBuilder for SqlBuilder {
    type Query<'q> = SqlQuery<'q> where Self: 'q;

    fn select<'q>(&'q mut self, columns: &[&str]) -> SqlQuery<'q> {
        // TODO: 実装
        todo!()
    }
}

impl Query for SqlQuery<'_> {
    fn where_clause(&mut self, condition: &str) -> &mut Self {
        // TODO: 実装
        todo!()
    }

    fn limit(&mut self, n: usize) -> &mut Self {
        // TODO: 実装
        todo!()
    }

    fn to_sql(&self) -> String {
        // TODO: SQL文を生成
        // 例: "SELECT id, name FROM users WHERE age > 18 LIMIT 10"
        todo!()
    }
}

#[test]
fn test_query_builder() {
    let mut builder = SqlBuilder::new("users");

    let sql = builder
        .select(&["id", "name"])
        .where_clause("age > 18")
        .where_clause("active = true")
        .limit(10)
        .to_sql();

    assert_eq!(
        sql,
        "SELECT id, name FROM users WHERE age > 18 AND active = true LIMIT 10"
    );
}

要件：

GATsの実装（4点）
メソッドチェーンの実現（3点）
正しいSQL生成（3点）

---

ボーナス2: ゼロコピーパーサーコンビネータ（10点）

ライフタイムを活用したパーサーコンビネータを実装しなさい：

trait Parser<'input> {
    type Output;
    type Error;

    fn parse(&self, input: &'input str) -> Result<(Self::Output, &'input str), Self::Error>;

    fn map<F, O>(self, func: F) -> Map<Self, F>
    where
        Self: Sized,
        F: Fn(Self::Output) -> O,
    {
        Map {
            parser: self,
            func,
        }
    }
}

struct Map<P, F> {
    parser: P,
    func: F,
}

impl<'input, P, F, O> Parser<'input> for Map<P, F>
where
    P: Parser<'input>,
    F: Fn(P::Output) -> O,
{
    type Output = O;
    type Error = P::Error;

    fn parse(&self, input: &'input str) -> Result<(O, &'input str), P::Error> {
        // TODO: 実装
        todo!()
    }
}

// 文字列リテラルパーサー
struct Literal<'a> {
    expected: &'a str,
}

impl<'input, 'a> Parser<'input> for Literal<'a> {
    type Output = &'input str;
    type Error = &'static str;

    fn parse(&self, input: &'input str) -> Result<(&'input str, &'input str), Self::Error> {
        // TODO: 実装
        // input が expected で始まるかチェック
        todo!()
    }
}

// 数字パーサー
struct Digit;

impl<'input> Parser<'input> for Digit {
    type Output = u32;
    type Error = &'static str;

    fn parse(&self, input: &'input str) -> Result<(u32, &'input str), Self::Error> {
        // TODO: 実装
        // 先頭の数字をパース
        todo!()
    }
}

#[test]
fn test_parser_combinator() {
    let literal = Literal { expected: "hello" };
    assert_eq!(literal.parse("hello world"), Ok(("hello", " world")));

    let digit = Digit;
    assert_eq!(digit.parse("42 answer"), Ok((42, " answer")));

    // mapコンビネータ
    let doubled = digit.map(|n| n * 2);
    assert_eq!(doubled.parse("21 test"), Ok((42, " test")));
}

要件：

Map::parse()の実装（3点）
Literal::parse()の実装（3点）
Digit::parse()の実装（2点）
すべてのテストをパス（2点）

---

提出要件

プロジェクト構造：

   advanced-lifetimes/
   ├── Cargo.toml
   ├── src/
   │   ├── lib.rs
   │   ├── lending.rs     # 問題1-2
   │   ├── streaming.rs   # 問題2
   │   ├── async_stream.rs # 問題3
   │   └── parser.rs      # ボーナス2
   ├── tests/
   │   └── integration_tests.rs
   └── EXPLANATION.md

Cargo.toml：

   [package]
   name = "advanced-lifetimes"
   version = "0.1.0"
   edition = "2021"

   [dependencies]
   async-stream = "0.3"
   futures = "0.3"

   [dev-dependencies]
   tokio = { version = "1", features = ["full"] }

EXPLANATION.md：

- 各問題の解説 - GATsが必要な理由 - Lending vs Streamingの違い - HRTBsの役割

テスト：

- すべてのテストがパスすること - cargo testでエラーなし

---

評価基準

マンダトリー（80点）

問題1（25点）: GATsの実装
問題2（20点）: Streaming Iteratorの理解
問題3（20点）: Async Lifetimeの実装
問題4（15点）: HRTBsとGATsの組み合わせ

ボーナス（20点）

ボーナス1（10点）: 実用的なクエリビルダー
ボーナス2（10点）: パーサーコンビネータの実装

コード品質

ライフタイム注釈の正確性
トレイト境界の適切性
ドキュメンテーション

---

ヒントとリソース

GATsのデバッグ

// エラー: "the trait bound `Self: 'a` is not satisfied"
// 解決: where Self: 'a を追加

trait MyTrait {
    type Item<'a>
    where
        Self: 'a;  // ← これが必要
}

Lending Iteratorの制限

// これはできない！
let mut iter = WindowsIter::new(&data, 2);
let first = iter.next();
let second = iter.next();
// first と second のライフタイムが重複

// これはできる
let mut iter = WindowsIter::new(&data, 2);
if let Some(first) = iter.next() {
    println!("{:?}", first);
}
if let Some(second) = iter.next() {
    println!("{:?}", second);
}

Async Streamのテスト

use futures::StreamExt;

#[tokio::test]
async fn test() {
    let mut stream = my_stream();

    while let Some(item) = stream.next().await {
        // 処理
    }
}

参考リンク

GATs Stabilization
Lending Iterators
Async Stream
Streaming Iterator Crate

---

よくある質問

Q1: GATsなしでLending Iteratorは実装できるか？ A1: いいえ。関連型にライフタイムパラメータを追加する機能が必要です。

Q2: Lending IteratorとStreaming Iteratorの使い分けは？ A2:

Lending: 可変参照を返す、メモリ効率重視
Streaming: 不変参照を複数回取得、使いやすさ重視

Q3: HRTBsのfor<'a>はいつ必要か？ A3: クロージャやトレイトメソッドが、すべてのライフタイムに対して動作する必要がある場合。

Q4: Async Streamは通常のStreamと何が違うか？ A4: poll_next()が非同期コンテキストで実行され、await可能なアイテムを返せる。

---

頑張ってください！この課題を完成させれば、Rustのライフタイムシステムを完全にマスターしたと言えるでしょう。