Backport #3708: Array#permutation がおかしな結果を返す

• Status: Closed
• Assignee: yugui (Yuki Sonoda)

[akai (Shumpei Akai)]

=begin
Array#permutationの結果に，配列に含まれていないはずの値が入っています

% ./ruby_head -e "p [0,1,2,3,4][1,4].permutation.to_a"
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]

[0,1,2,3,4][1,4] は [1, 2, 3, 4] なので0は含まれないはずです．

% ./ruby_head -e "p [0,1,2,3][1,3].permutation.to_a"
だと正しく動きます
=end

[mrkn (Kenta Murata)]

=begin
むらたです。

On 2010/08/18, at 16:33, Shumpei Akai wrote:

Array#permutationの結果に，配列に含まれていないはずの値が入っています

% ./ruby_head -e "p [0,1,2,3,4][1,4].permutation.to_a"
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]

[0,1,2,3,4][1,4] は [1, 2, 3, 4] なので0は含まれないはずです．

% ./ruby_head -e "p [0,1,2,3][1,3].permutation.to_a"
だと正しく動きます

ary_make_shared 関数を以下のように修正すると正常に動作します。

diff --git a/array.c b/array.c
index 51d3ad2..ea4fe43 100644
--- a/array.c
+++ b/array.c
@@ -409,10 +409,7 @@ static VALUE
ary_make_shared(VALUE ary)
{
assert(!ARY_EMBED_P(ary));

• if (ARY_SHARED_P(ary)) {

•   return ARY_SHARED(ary);
  

• }
• else if (ARY_SHARED_ROOT_P(ary)) {

• if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {
  return ary;
  }
  else if (OBJ_FROZEN(ary)) {
  diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb
  index e8edcc2..f2d723f 100644
  --- a/test/ruby/test_array.rb
  +++ b/test/ruby/test_array.rb
  @@ -1549,6 +1549,9 @@ class TestArray < Test::Unit::TestCase
  a.permutation {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }
  assert_equal(@cls[9, 8, 7, 6], a)
  assert_equal(@cls[1, 2, 3, 4].permutation.to_a, b)
• bug3708 = '[ruby-dev:42067]'
• assert_equal(b, @cls[0, 1, 2, 3, 4][1, 4].permutation.to_a, bug3708)
  end

def test_repeated_permutation

--
Kenta Murata
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

本を書きました!!
『Ruby 逆引きレシピ』 http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: [e-mail]
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

=end

[matz (Yukihiro Matsumoto)]

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:42068] Re: [Bug #3708] Array#permutation がおかしな結果を返す"
on Wed, 18 Aug 2010 18:16:13 +0900, Kenta Murata [e-mail] writes:

|On 2010/08/18, at 16:33, Shumpei Akai wrote:
|
|> Array#permutationの結果に，配列に含まれていないはずの値が入っています
|>
|> % ./ruby_head -e "p [0,1,2,3,4][1,4].permutation.to_a"
|> [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
|>
|>
|> [0,1,2,3,4][1,4] は [1, 2, 3, 4] なので0は含まれないはずです．
|>
|>
|> % ./ruby_head -e "p [0,1,2,3][1,3].permutation.to_a"
|> だと正しく動きます
|
|
|ary_make_shared 関数を以下のように修正すると正常に動作します。
|
|diff --git a/array.c b/array.c
|index 51d3ad2..ea4fe43 100644
|--- a/array.c
|+++ b/array.c
|@@ -409,10 +409,7 @@ static VALUE
| ary_make_shared(VALUE ary)
| {
| assert(!ARY_EMBED_P(ary));
|- if (ARY_SHARED_P(ary)) {
|- return ARY_SHARED(ary);
|- }
|- else if (ARY_SHARED_ROOT_P(ary)) {
|+ if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {
| return ary;
| }
| else if (OBJ_FROZEN(ary)) {

なるほど。コミットして下さい。

=end

[mrkn (Kenta Murata)]

• Status changed from Open to Closed
• % Done changed from 0 to 100

=begin
This issue was solved with changeset r29037.
Shumpei, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end

[mrkn (Kenta Murata)]

• Status changed from Closed to Open

=begin
r29037 では SEGV が発生することがあったため、一旦 revert して修正しなおします。

=end

[mrkn (Kenta Murata)]

=begin
むらたです。

On 2010/08/18, at 18:28, Yukihiro Matsumoto wrote:

|diff --git a/array.c b/array.c
|index 51d3ad2..ea4fe43 100644
|--- a/array.c
|+++ b/array.c
|@@ -409,10 +409,7 @@ static VALUE
| ary_make_shared(VALUE ary)
| {
| assert(!ARY_EMBED_P(ary));
|- if (ARY_SHARED_P(ary)) {
|- return ARY_SHARED(ary);
|- }
|- else if (ARY_SHARED_ROOT_P(ary)) {
|+ if (ARY_SHARED_P(ary) || ARY_SHARED_ROOT_P(ary)) {
| return ary;
| }
| else if (OBJ_FROZEN(ary)) {

なるほど。コミットして下さい。

一旦これでコミットしたのですが、SEGV が発生することがあったため revert しました。

なかださんに ary_make_shared_copy を教えてもらったので、もう一度修正案を提示します。
repeated_permutation、repeated_combination、product も対象です。

diff --git a/array.c b/array.c
index 51d3ad2..bca7956 100644
--- a/array.c
+++ b/array.c
@@ -4010,7 +4010,7 @@ rb_ary_permutation(int argc, VALUE *argv, VALUE ary)
long p = (long)RSTRING_PTR(t0);
volatile VALUE t1 = tmpbuf(n,sizeof(char));
char used = (char)RSTRING_PTR(t1);

•   VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
  

•   VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
    RBASIC(ary0)->klass = 0;
  
    MEMZERO(used, char, n); /* initialize array */
  

@@ -4180,7 +4180,7 @@ rb_ary_repeated_permutation(VALUE ary, VALUE num)
else { /* this is the general case */
volatile VALUE t0 = tmpbuf(r, sizeof(long));
long p = (long)RSTRING_PTR(t0);

•   VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
  

•   VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
    RBASIC(ary0)->klass = 0;
  
    rpermute0(n, r, p, 0, ary0); /* compute and yield repeated permutations */
  

@@ -4266,7 +4266,7 @@ rb_ary_repeated_combination(VALUE ary, VALUE num)
else {
volatile VALUE t0 = tmpbuf(n, sizeof(long));
long p = (long)RSTRING_PTR(t0);

•   VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
  

•   VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
    RBASIC(ary0)->klass = 0;
  
    rcombinate0(len, n, p, 0, n, ary0); /* compute and yield repeated combinations */
  

@@ -4325,7 +4325,7 @@ rb_ary_product(int argc, VALUE argv, VALUE ary)
/ Make defensive copies of arrays; exit if any is empty */
for (i = 0; i < n; i++) {
if (RARRAY_LEN(arrays[i]) == 0) goto done;

•       arrays[i] = ary_make_substitution(arrays[i]);
  

•       arrays[i] = ary_make_shared_copy(arrays[i]);
    }
  

  }
  else {
  --- a/test/ruby/test_array.rb
  +++ b/test/ruby/test_array.rb
  @@ -1528,6 +1528,10 @@ class TestArray < Test::Unit::TestCase
  acc = [1,2].product(*[o]*10)
  assert_equal([1,2].product([3,4], [3,4], [3,4], [3,4], [3,4], [3,4], [3,4], [3,4], [3,4], [3,4]),
  acc)
• a = []
• [1, 2].product([0, 1, 2, 3, 4][1, 4]) {|x| a << x }
• assert(a.all?{|x| !x.include?(0) })
  end

def test_permutation

@@ -1574,6 +1578,9 @@ class TestArray < Test::Unit::TestCase
a.repeated_permutation(4) {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }
assert_equal(@cls[9, 8, 7, 6], a)
assert_equal(@cls[1, 2, 3, 4].repeated_permutation(4).to_a, b)
+

• a = @cls[0, 1, 2, 3, 4][1, 4].repeated_permutation(2)
• assert(a.all?{|x| !x.include?(0) })
  end

def test_repeated_combination

@@ -1600,6 +1607,9 @@ class TestArray < Test::Unit::TestCase
a.repeated_combination(4) {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }
assert_equal(@cls[9, 8, 7, 6], a)
assert_equal(@cls[1, 2, 3, 4].repeated_combination(4).to_a, b)
+

• a = @cls[0, 1, 2, 3, 4][1, 4].repeated_combination(2)
• assert(a.all?{|x| !x.include?(0) })
  end

def test_take

--
Kenta Murata
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

本を書きました!!
『Ruby 逆引きレシピ』 http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: [e-mail]
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

=end

[mrkn (Kenta Murata)]

• Status changed from Open to Closed

=begin
This issue was solved with changeset r29044.
Shumpei, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end

[mrkn (Kenta Murata)]

• Category set to core
• Status changed from Closed to Assigned
• Assignee set to yugui (Yuki Sonoda)

=begin
1.9.2 へのバックポート対象です。

=end

[yugui (Yuki Sonoda)]

• Status changed from Assigned to Closed

=begin
This issue was solved with changeset r29370.
Shumpei, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end