Day 018 — カスタムイテレータの実装（DoubleEndedIterator/ExactSizeIteratorの境界バグ）

📚 背景知識（読んでから問題へ）

Day 017ではIterator（next()のみ）を自作しました。今日はその発展として、DoubleEndedIteratorとExactSizeIteratorという2つの追加トレイトを扱います。

📋 コピーpub trait DoubleEndedIterator: Iterator {
    fn next_back(&mut self) -> Option<Self::Item>; // 末尾側から1つ取り出す
}

pub trait ExactSizeIterator: Iterator {
    fn len(&self) -> usize {
        // デフォルト実装は size_hint() から算出されるが、正確な残数が
        // 分かっている場合は独自にオーバーライドできる
        self.size_hint().0
    }
}

• DoubleEndedIterator: next()（先頭から）に加えnext_back()（末尾から）を実装すると、.rev()で逆順走査ができるようになります。Vecのiter()やRange（0..10）は標準でこれを実装しています
• ExactSizeIterator: 「残りの要素数が正確に分かる」ことを型で表明するマーカー的トレイトです。Vec::with_capacityのような事前確保の最適化に使われ、collect()はExactSizeIteratorを実装したイテレータに対して再アロケーションなしでちょうどいいサイズのVecを1回で確保できます

この2つを同じ型に実装するとき、最も起こりやすいバグが「先頭カーソルと末尾カーソルが衝突したかどうか」の境界判定の誤りです。next()とnext_back()はそれぞれ独立したメソッドですが、両者は同じ内部状態（currentとendなど）を共有しながら「互いに反対方向から侵食していく」関係にあります。片方の終了条件だけ演算子を1文字間違えると、コンパイルは通ってしまうのに実行時に整数アンダーフローパニックや終わらないイテレータという深刻なバグを生みます。

以下のコードは、0..endの範囲を先頭・末尾どちらからでも取り出せるCountdownイテレータの実装です。一見正しく動きそうですが、next_back()に1箇所バグがあります。

📋 コピーstruct Countdown {
    current: u32,
    end: u32,
}

impl Countdown {
    fn new(start: u32, end: u32) -> Self {
        Countdown { current: start, end }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current == self.end {
            return None;
        }
        let value = self.current;
        self.current += 1;
        Some(value)
    }
}

impl DoubleEndedIterator for Countdown {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.current > self.end {
            // BUG: ここに問題がある
            return None;
        }
        self.end -= 1;
        Some(self.end)
    }
}

impl ExactSizeIterator for Countdown {
    fn len(&self) -> usize {
        (self.end - self.current) as usize
    }
}

📝 問題

上記のCountdownのコードにはnext_back()に1つ、境界判定の演算子の誤りによるバグがあります。以下の3つの要求に順番に答えてください。

要求1（バグの特定と原因説明）

next_back()内のif self.current > self.endという条件が誤りである理由を説明してください。Countdown::new(0, 3)に対してnext_back()を4回連続で呼んだとき、実際に何が起こるか（何回目の呼び出しでどんな問題が発生するか）をステップごとに追ってください。

要求2（修正版の実装）

next_back()の境界判定を正しい条件に修正した完全なCountdownの実装を書いてください。next()・next_back()を交互に呼んでも、.rev().collect()を呼んでも、必ずcurrent == endに到達した時点で正しくNoneを返し、要素の重複・欠落・パニックが起きないようにしてください。

要求3（回帰防止のテスト実装）

次の3つを検証するテストを書いてください。

1. Countdown::new(0, 5)に対してnext_back()だけを5回呼ぶと[4, 3, 2, 1, 0]が順に返り、6回目はNoneになる（修正前のバグでは6回目でパニックしていた箇所）
2. next()とnext_back()を交互に呼び、合計で元の要素数ぶんだけ値が返り、値の重複がない（Countdown::new(0, 5)なら{0,1,2,3,4}がちょうど1回ずつ）
3. Countdown::new(0, 5).rev().collect::<Vec<u32>>()がvec![4, 3, 2, 1, 0]になり、かつExactSizeIterator::len()が走査前に正しく5を返す

🔍 ヒント（段階的開示）

📋 コピーimpl DoubleEndedIterator for Countdown {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.current == self.end {
            return None;
        }
        self.end -= 1;
        Some(self.end)
    }
}

✅ 模範解答

📋 コピーstruct Countdown {
    current: u32,
    end: u32,
}

impl Countdown {
    fn new(start: u32, end: u32) -> Self {
        Countdown { current: start, end }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current == self.end {
            return None;
        }
        let value = self.current;
        self.current += 1;
        Some(value)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = (self.end - self.current) as usize;
        (remaining, Some(remaining))
    }
}

// 修正版: 境界判定を `self.current == self.end` に統一する
impl DoubleEndedIterator for Countdown {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.current == self.end {
            return None;
        }
        self.end -= 1;
        Some(self.end)
    }
}

impl ExactSizeIterator for Countdown {
    fn len(&self) -> usize {
        (self.end - self.current) as usize
    }
}

fn main() {
    // 要求2の実行例: next_back() だけで末尾から辿る
    let backward: Vec<u32> = Countdown::new(0, 5).rev().collect();
    println!("backward = {:?}", backward);

    // 交互に next() / next_back() を呼ぶ例
    let mut it = Countdown::new(0, 5);
    let mut mixed = Vec::new();
    mixed.push(it.next().unwrap());      // 0
    mixed.push(it.next_back().unwrap()); // 4
    mixed.push(it.next().unwrap());      // 1
    mixed.push(it.next_back().unwrap()); // 3
    mixed.push(it.next().unwrap());      // 2
    println!("mixed = {:?}", mixed);
    println!("exhausted next() = {:?}", it.next());           // None
    println!("exhausted next_back() = {:?}", it.next_back()); // None

    // ExactSizeIterator の確認
    println!("len before consume = {}", Countdown::new(0, 5).len());
}

#[cfg(test)]
mod tests {
    use super::*;

    // 要求3-1: next_back() のみを5回呼ぶ回帰テスト
    // 修正前のバグでは6回目の呼び出しで `attempt to subtract with overflow` パニックしていた
    #[test]
    fn next_back_only_yields_reverse_order_then_none() {
        let mut it = Countdown::new(0, 5);
        assert_eq!(it.next_back(), Some(4));
        assert_eq!(it.next_back(), Some(3));
        assert_eq!(it.next_back(), Some(2));
        assert_eq!(it.next_back(), Some(1));
        assert_eq!(it.next_back(), Some(0));
        assert_eq!(it.next_back(), None); // ここでパニックせず None が返る
        assert_eq!(it.next_back(), None); // 何度呼んでも None のまま（FusedIterator相当の安定性）
    }

    // 要求3-2: next() / next_back() を交互に呼んでも重複・欠落がない
    #[test]
    fn interleaved_next_and_next_back_cover_all_elements_exactly_once() {
        let mut it = Countdown::new(0, 5);
        let mut collected = Vec::new();

        collected.push(it.next().unwrap());
        collected.push(it.next_back().unwrap());
        collected.push(it.next().unwrap());
        collected.push(it.next_back().unwrap());
        collected.push(it.next().unwrap());

        // 5要素すべて出尽くしたので、両方向とも None になる
        assert_eq!(it.next(), None);
        assert_eq!(it.next_back(), None);

        collected.sort();
        assert_eq!(collected, vec![0, 1, 2, 3, 4]);
    }

    // 要求3-3: rev().collect() と ExactSizeIterator::len() の整合性
    #[test]
    fn rev_collect_matches_expected_order_and_len_is_exact() {
        let it = Countdown::new(0, 5);
        assert_eq!(it.len(), 5);

        let reversed: Vec<u32> = Countdown::new(0, 5).rev().collect();
        assert_eq!(reversed, vec![4, 3, 2, 1, 0]);
    }

    #[test]
    fn empty_range_returns_none_immediately_from_both_ends() {
        let mut it = Countdown::new(3, 3);
        assert_eq!(it.next(), None);
        assert_eq!(it.next_back(), None);
        assert_eq!(it.len(), 0);
    }
}

$ cargo run
backward = [4, 3, 2, 1, 0]
mixed = [0, 4, 1, 3, 2]
exhausted next() = None
exhausted next_back() = None
len before consume = 5

$ cargo test
running 4 tests
test tests::empty_range_returns_none_immediately_from_both_ends ... ok
test tests::interleaved_next_and_next_back_cover_all_elements_exactly_once ... ok
test tests::next_back_only_yields_reverse_order_then_none ... ok
test tests::rev_collect_matches_expected_order_and_len_is_exact ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

🪜 Step-by-Step 解説

📋 コピーif self.current == self.end {  // 修正後: 衝突した瞬間に止める
    return None;
}

📋 コピーfn len(&self) -> usize {
    (self.end - self.current) as usize
}

💡 設計思想・なぜこう書くのか

🛑 パニックが出た場合（このバグはコンパイルは通る）

このバグはコンパイルは通ります。境界判定の演算子（> vs ==）はどちらもboolを返す正しい式であり、型システムはロジックの意味的な正しさまでは検査しないためです。問題はcargo test実行時、またはcargo run実行時にランタイムパニックとして表面化します。

読み方: attempt to subtract with overflowは、符号なし整数（u32など）の引き算・複合代入減算（-=）が、表現できる範囲の下限（0）を下回ろうとしたときにデバッグビルドで発生するパニックです。エラーメッセージ自体は「どの変数が」「なぜ」負になろうとしたかまでは教えてくれないため、行番号（self.end -= 1の行）からどの減算がアンダーフローしたかを特定し、その値がなぜ0未満になり得たのか（＝終了条件が正しく機能していなかったのはなぜか）を境界条件から逆算して調べるのが定石です。RUST_BACKTRACE=1 cargo testのように実行すると、パニックに至るまでの呼び出しスタックが表示され、どのテストのどの行が引き金になったかをより素早く特定できます。

🌐 他言語との比較

Goの符号なし整数はRustと同様にラップアラウンドしますが、デバッグビルドでの自動パニックという安全網が存在しないため、本問のようなバグはcargo testのような形で早期に検出されず、本番環境で初めて異常値として発覚するリスクがRustより高くなります。Rustの「デバッグ時はパニック・リリース時は定義済みラップアラウンド」という2段構えは、開発中に境界バグを見つけやすくしつつ、本番では未定義動作を出さないという、C++の未定義動作ともGoの沈黙したラップアラウンドとも異なる中間的な設計です。

🏆 実務での使いどころ

• ページャ/カーソルベースのAPIクライアント: 「先頭から順に取得」と「末尾から遡って取得」の両方が必要なUI（無限スクロール＋末尾ジャンプなど）でDoubleEndedIteratorを実装すると、片方向の走査ロジックを2重に書かずに済みます
• collect()のパフォーマンス最適化: ExactSizeIteratorを正しく実装すると、Vec::with_capacity相当の事前確保がcollect()内部で自動的に行われ、再アロケーションのコストを削減できます。逆にlen()が不正確な値を返すと、Vecが正しくないキャパシティで確保され、余計なメモリ確保やパニックにつながることがあります
• 境界値のプロパティベーステスト: 本問のようなカーソル共有型のバグは、0要素・1要素・偶数個・奇数個など要素数のパターンを網羅したテストでしか検出できません。実務でも「両端から消費する」データ構造（デック、スライディングウィンドウ、リングバッファ）を実装する際は、境界値テストを最初から用意するのが定石です

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: Day 017のSlidingWindowにも同じ要領でDoubleEndedIteratorを実装し、.rev()で末尾側からウィンドウを取り出せるようにしてみてください。front/backという2つのカーソルを使う場合、本問のcurrent/endよりも境界判定が複雑になる点に注意してください
• 次回予告: 自己評価で「完全理解」または「おおむね理解」が3回連続で記録された時点で、次のテーマスマートポインタ①（Box<T>）（ヒープ確保・再帰的データ構造）に進みます

🎯 自己評価

自分の回答

気づき・メモ