From: Tanaka Akira <akr@...>
Date: 2009-07-28T18:45:00+09:00
Subject: [ruby-dev:38932] Enumerator#peek

Enumerator#peek を新設するのはどうでしょうか。

Enumerator からデータを読み出すとき、先読みをしたくなることがあります。

たとえば、ソート済みの単語の列があったときに、各単語の数を求
めたいとすると、以下のように次の要素との比較をしたくなります。

a = %w[banana banana durian orange orange orange]  
e = a.to_enum
n = 0
loop {
  word = e.next
  n += 1
  if 次の要素が存在して word とは異なるか、存在しない
    puts "#{word} #{n}"
    word = nil
    n = 0
  end
}

しかし、ここで Enumerator#next は使えません。使ってしまうと、
ループの次の回で扱うべき要素を消費してしまいます。

かといって、ループの次の回で処理するようにすると、ループのひ
とまわりごとにひとつの要素を処理するという構造が壊れてわかり
にくくなります。また、最後の単語の処理をループが終わった後に
することになって、各単語毎に行う処理がループの中と後にふたつ
必要になってしまいます。たとえば、以下のように書けますが、
コードの重複が生じ、また難しくなっています。

% ./ruby -e '
a = %w[banana banana durian orange orange orange]
e = a.to_enum
n = 0
prev = nil
loop {
  word = e.next
  if prev && prev != word
    puts "#{prev} #{n}"
    n = 0
  end
  prev = word
  n += 1
}
if prev
  puts "#{prev} #{n}" 
end
'
banana 2
durian 1
orange 3

# 咳さんの発表で知ったんですが、こーゆーのってコントロールブ
# レークっていうんですね。

そこで、要素を消費せずに読み出す、つまり先読みをするメソッド
があれば、最初に書いた、ループのひとまわりごとにひとつの要素
を処理するという形で記述できます。そういうメソッドを
Enumerator#peek とすると、以下のように書けます。

% ./ruby -e '
a = %w[banana banana durian orange orange orange]  
e = a.to_enum
n = 0
loop {
  word = e.next
  n += 1
  if begin word != e.peek; rescue StopIteration; true end
    puts "#{word} #{n}"
    word = nil
    n = 0
  end
}
'
banana 2
durian 1
orange 3

まぁ、rescue するのは見苦しいので、引数を指定したら
StopIteration 例外のかわりに引数を返すようにしたらいいかな、
などということも考えられますが、基本的なアイデアとしてはどう
でしょうか。

ここで、要素の並びからこうやって情報をまとめていくというのは、
  %w[banana banana durian orange orange orange]
という平坦な構造から
  [%w[banana banana], %w[durian], %w[orange orange orange]]
という木構造を構成する構文解析ともみなせますので、先読みが必
要になるというのはよくあるものであると想定できます。そして、
構文解析からの類推として、先読みはひとつで済むことが多い、と
いうことも予想できます。つまり Enumerable#peek はひとつの先
読みを提供することから、よくある状況に対応でき、かつ、これよ
り (複数の先読みを提供するような) 一般化してもそれほど益はな
い、という仕様になっているといえるのではないでしょうか。

なお、ちょっとした副作用として、StopIteration が発生した後に、
Enumerator#next を呼んだ時、(繰り返しの最初に戻るのではなく)
ずっと StopIteration が発生するように変えてあります。

これは、以下のような理由があります。
* ARGF や tty な IO などの経験から終了は複数回検出できたほう
  が良い
* peek で発生した StopIteration で最初に戻られると困る
* IO を元に作った Enumerator ではもともとそうなる
* 1.8 の Generator ではそうなる
* 本当に繰り返しの最初に戻りたいなら rewind があり、それは
  IO でも (seek できれば) 動く


% svn diff --diff-cmd diff -x '-u -p'
Index: enumerator.c
===================================================================
--- enumerator.c	(revision 24304)
+++ enumerator.c	(working copy)
@@ -32,6 +32,7 @@ struct enumerator {
     VALUE args;
     VALUE fib;
     VALUE dst;
+    VALUE lookahead;
     VALUE no_next;
 };
 
@@ -59,6 +60,7 @@ enumerator_mark(void *p)
     rb_gc_mark(ptr->args);
     rb_gc_mark(ptr->fib);
     rb_gc_mark(ptr->dst);
+    rb_gc_mark(ptr->lookahead);
 }
 
 static struct enumerator *
@@ -281,6 +283,7 @@ enumerator_init(VALUE enum_obj, VALUE ob
     if (argc) ptr->args = rb_ary_new4(argc, argv);
     ptr->fib = 0;
     ptr->dst = Qnil;
+    ptr->lookahead = Qundef;
     ptr->no_next = Qfalse;
 
     return enum_obj;
@@ -361,6 +364,7 @@ enumerator_init_copy(VALUE obj, VALUE or
     ptr1->meth = ptr0->meth;
     ptr1->args = ptr0->args;
     ptr1->fib  = 0;
+    ptr1->lookahead  = Qundef;
 
     return obj;
 }
@@ -519,6 +523,7 @@ next_init(VALUE obj, struct enumerator *
     VALUE curr = rb_fiber_current();
     e->dst = curr;
     e->fib = rb_fiber_new(next_i, obj);
+    e->lookahead = Qundef;
 }
 
 /*
@@ -526,8 +531,8 @@ next_init(VALUE obj, struct enumerator *
  *   e.next   => object
  *
  * Returns the next object in the enumerator, and move the internal
- * position forward.  When the position reached at the end, internal
- * position is rewound then StopIteration is raised.
+ * position forward.  When the position reached at the end, StopIteration
+ * is raised.
  *
  * Note that enumeration sequence by next method does not affect other
  * non-external enumeration methods, unless underlying iteration
@@ -540,6 +545,16 @@ enumerator_next(VALUE obj)
 {
     struct enumerator *e = enumerator_ptr(obj);
     VALUE curr, v;
+
+    if (e->lookahead != Qundef) {
+        v = e->lookahead;
+        e->lookahead = Qundef;
+        return v;
+    }
+
+    if (e->no_next)
+	rb_raise(rb_eStopIteration, "iteration reached at end");
+
     curr = rb_fiber_current();
 
     if (!e->fib || !rb_fiber_alive_p(e->fib)) {
@@ -550,7 +565,7 @@ enumerator_next(VALUE obj)
     if (e->no_next) {
 	e->fib = 0;
 	e->dst = Qnil;
-	e->no_next = Qfalse;
+	e->lookahead = Qundef;
 	rb_raise(rb_eStopIteration, "iteration reached at end");
     }
     return v;
@@ -558,6 +573,32 @@ enumerator_next(VALUE obj)
 
 /*
  * call-seq:
+ *   e.peek   => object
+ *
+ * Returns the next object in the enumerator, but don't move the internal
+ * position forward.  When the position reached at the end, StopIteration
+ * is raised.
+ *
+ */
+
+static VALUE
+enumerator_peek(VALUE obj)
+{
+    struct enumerator *e = enumerator_ptr(obj);
+    VALUE v;
+
+    if (e->lookahead != Qundef) {
+        v = e->lookahead;
+        return v;
+    }
+
+    v = enumerator_next(obj);
+    e->lookahead = v;
+    return v;
+}
+
+/*
+ * call-seq:
  *   e.rewind   => e
  *
  * Rewinds the enumeration sequence by the next method.
@@ -575,6 +616,7 @@ enumerator_rewind(VALUE obj)
 
     e->fib = 0;
     e->dst = Qnil;
+    e->lookahead = Qundef;
     e->no_next = Qfalse;
     return obj;
 }
@@ -868,6 +910,7 @@ Init_Enumerator(void)
     rb_define_method(rb_cEnumerator, "with_index", enumerator_with_index, -1);
     rb_define_method(rb_cEnumerator, "with_object", enumerator_with_object, 1);
     rb_define_method(rb_cEnumerator, "next", enumerator_next, 0);
+    rb_define_method(rb_cEnumerator, "peek", enumerator_peek, 0);
     rb_define_method(rb_cEnumerator, "rewind", enumerator_rewind, 0);
     rb_define_method(rb_cEnumerator, "inspect", enumerator_inspect, 0);
 
Index: test/ruby/test_enumerator.rb
===================================================================
--- test/ruby/test_enumerator.rb	(revision 24304)
+++ test/ruby/test_enumerator.rb	(working copy)
@@ -130,5 +130,27 @@ class TestEnumerator < Test::Unit::TestC
     assert_equal(3, e.next)
     assert_raise(StopIteration) { e.next }
   end
+
+  def test_peek
+    a = [1]
+    e = a.each
+    assert_equal(1, e.peek)
+    assert_equal(1, e.peek)
+    assert_equal(1, e.next)
+    assert_raise(StopIteration) { e.peek }
+    assert_raise(StopIteration) { e.peek }
+  end
+
+  def test_next_after_stopiteration
+    a = [1]
+    e = a.each
+    assert_equal(1, e.next)
+    assert_raise(StopIteration) { e.next }
+    assert_raise(StopIteration) { e.next }
+    e.rewind
+    assert_equal(1, e.next)
+    assert_raise(StopIteration) { e.next }
+    assert_raise(StopIteration) { e.next }
+  end
 end
 
-- 
[田中 哲][たなか あきら][Tanaka Akira]