Project

General

Profile

Backport #3708

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

Added by akai (Shumpei Akai) almost 9 years ago. Updated about 8 years ago.

Status:
Closed
Priority:
Normal

Description

=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

Associated revisions

Revision 4023ffa9
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (ary_make_shared), test/ruby/test_array.rb (test_permutation): always return the original array when it is shared. [ruby-dev:42067] [Bug #3708]

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@29037 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Revision 29037
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (ary_make_shared), test/ruby/test_array.rb (test_permutation): always return the original array when it is shared. [ruby-dev:42067] [Bug #3708]

Revision 29037
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (ary_make_shared), test/ruby/test_array.rb (test_permutation): always return the original array when it is shared. [ruby-dev:42067] [Bug #3708]

Revision 29037
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (ary_make_shared), test/ruby/test_array.rb (test_permutation): always return the original array when it is shared. [ruby-dev:42067] [Bug #3708]

Revision 29037
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (ary_make_shared), test/ruby/test_array.rb (test_permutation): always return the original array when it is shared. [ruby-dev:42067] [Bug #3708]

Revision 29037
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (ary_make_shared), test/ruby/test_array.rb (test_permutation): always return the original array when it is shared. [ruby-dev:42067] [Bug #3708]

Revision 29037
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (ary_make_shared), test/ruby/test_array.rb (test_permutation): always return the original array when it is shared. [ruby-dev:42067] [Bug #3708]

Revision 1d04aedb
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@29044 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Revision 29044
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

Revision 29044
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

Revision 29044
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

Revision 29044
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

Revision 29044
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

Revision 29044
Added by mrkn (Kenta Murata) almost 9 years ago

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

Revision 2fd98b1d
Added by yugui (Yuki Sonoda) almost 9 years ago

merges r29044 from trunk into ruby_1_9_2.

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_9_2@29370 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Revision 29370
Added by yugui (Yuki Sonoda) almost 9 years ago

merges r29044 from trunk into ruby_1_9_2.

  • array.c (rb_ary_permutation, rb_ary_repeated_permutation, rb_ary_repeated_combination, rb_ary_product): use ary_make_shared_copy instead of ary_make_substitution. [ruby-dev:42067] [Bug #3708]
  • test/ruby/test_array.rb (test_product, test_repeated_permutation, test_repeated_combination): append assertions against [Bug #3708].

History

#1

Updated by mrkn (Kenta Murata) almost 9 years ago

=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: mrkn@mrkn.jp
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

=end

#2

Updated by matz (Yukihiro Matsumoto) almost 9 years ago

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

In message "Re: [ruby-dev:42068] Re: [Bug #3708] Array#permutation がおかしな結果を返す"
on Wed, 18 Aug 2010 18:16:13 +0900, Kenta Murata muraken@gmail.com 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

#3

Updated by mrkn (Kenta Murata) almost 9 years ago

  • 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

#4

Updated by mrkn (Kenta Murata) almost 9 years ago

  • Status changed from Closed to Open

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

=end

#5

Updated by mrkn (Kenta Murata) almost 9 years ago

=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: mrkn@mrkn.jp
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

=end

#6

Updated by mrkn (Kenta Murata) almost 9 years ago

  • 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

#7

Updated by mrkn (Kenta Murata) almost 9 years ago

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

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

=end

#8

Updated by yugui (Yuki Sonoda) almost 9 years ago

  • 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

Also available in: Atom PDF