[Truffle] Implement Array#<=>, shim the Rubinius mirror, and move #pe…

…rmutation to Ruby.
jruby · Feb 6, 2015 · f8392f9 · chrisseaton · Feb 6, 2015 · eregon
1 parent 59b60b5
commit f8392f9
Showing 6 changed files with 135 additions and 75 deletions.
diff --git a/spec/truffle/tags/core/array/permutation_tags.txt b/spec/truffle/tags/core/array/permutation_tags.txt
diff --git a/truffle/src/main/java/org/jruby/truffle/nodes/core/ArrayNodes.java b/truffle/src/main/java/org/jruby/truffle/nodes/core/ArrayNodes.java
@@ -2892,68 +2892,6 @@ protected boolean formatIsLStar(RubyArray array, RubyString format) {
 
     }
 
-    @CoreMethod(names = "permutation", required = 1)
-    public abstract static class PermutationNode extends ArrayCoreMethodNode {
-
-        public PermutationNode(RubyContext context, SourceSection sourceSection) {
-            super(context, sourceSection);
-        }
-
-        public PermutationNode(PermutationNode prev) {
-            super(prev);
-        }
-
-        @Specialization
-        public RubyArray permutation(RubyArray array, int n) {
-            notDesignedForCompilation();
-
-            final List<RubyArray> permutations = new ArrayList<>();
-            permutationCommon(n, false, array.slowToArray(), permutations);
-            return new RubyArray(getContext().getCoreLibrary().getArrayClass(), permutations.toArray(), permutations.size());
-        }
-
-        // Apdapted from JRuby's RubyArray - see attribution there
-
-        private void permutationCommon(int r, boolean repeat, Object[] values, List<RubyArray> permutations) {
-            if (r == 0) {
-                permutations.add(new RubyArray(getContext().getCoreLibrary().getArrayClass(), null, 0));
-            } else if (r == 1) {
-                for (int i = 0; i < values.length; i++) {
-                    permutations.add(new RubyArray(getContext().getCoreLibrary().getArrayClass(), values[i], 1));
-                }
-            } else if (r >= 0) {
-                int n = values.length;
-                permute(n, r,
-                        new int[r], 0,
-                        new boolean[n],
-                        repeat,
-                        values, permutations);
-            }
-        }
-
-        private void permute(int n, int r, int[]p, int index, boolean[]used, boolean repeat, Object[] values, List<RubyArray> permutations) {
-            for (int i = 0; i < n; i++) {
-                if (repeat || !used[i]) {
-                    p[index] = i;
-                    if (index < r - 1) {
-                        used[i] = true;
-                        permute(n, r, p, index + 1, used, repeat, values, permutations);
-                        used[i] = false;
-                    } else {
-                        Object[] result = new Object[r];
-
-                        for (int j = 0; j < r; j++) {
-                            result[j] = values[p[j]];
-                        }
-
-                        permutations.add(new RubyArray(getContext().getCoreLibrary().getArrayClass(), result, r));
-                    }
-                }
-            }
-        }
-
-    }
-
     @CoreMethod(names = "pop")
     public abstract static class PopNode extends ArrayCoreMethodNode {
 

diff --git a/truffle/src/main/java/org/jruby/truffle/translator/BodyTranslator.java b/truffle/src/main/java/org/jruby/truffle/translator/BodyTranslator.java
@@ -1492,8 +1492,24 @@ public RubyNode visitInstAsgnNode(org.jruby.ast.InstAsgnNode node) {
     @Override
     public RubyNode visitInstVarNode(org.jruby.ast.InstVarNode node) {
         final SourceSection sourceSection = translate(node.getPosition());
+
+        // TODO CS 6-Feb-15 - this appears to be the name *with* sigil - need to clarify this
+
         final String nameWithoutSigil = node.getName();
 
+        /*
+         * Rubinius uses the instance variable @total to store the size of an array. In order to use code that
+         * expects that we'll replace it statically with a call to Array#size.
+         */
+
+        if (sourceSection.getSource().getPath().equals("core:/jruby/truffle/core/rubinius/kernel/common/array.rb") && nameWithoutSigil.equals("@total")) {
+            return new RubyCallNode(context, sourceSection,
+                    "size",
+                    new SelfNode(context, sourceSection),
+                    null,
+                    false);
+        }
+
         final RubyNode receiver = new SelfNode(context, sourceSection);
 
         return new ReadInstanceVariableNode(context, sourceSection, nameWithoutSigil, receiver, false);

diff --git a/truffle/src/main/ruby/jruby/truffle/core.rb b/truffle/src/main/ruby/jruby/truffle/core.rb
@@ -12,6 +12,7 @@
 require_relative 'core/rubinius/api/kernel/common/type'
 
 # Patch rubinius-core-api to make it work for us
+require_relative 'core/rubinius/api/shims/array'
 require_relative 'core/rubinius/api/shims/rubinius'
 require_relative 'core/rubinius/api/shims/lookuptable'
 require_relative 'core/rubinius/api/shims/thread'

diff --git a/truffle/src/main/ruby/jruby/truffle/core/rubinius/api/shims/array.rb b/truffle/src/main/ruby/jruby/truffle/core/rubinius/api/shims/array.rb
@@ -0,0 +1,27 @@
+# Copyright (c) 2015 Oracle and/or its affiliates. All rights reserved. This
+# code is released under a tri EPL/GPL/LGPL license. You can use it,
+# redistribute it and/or modify it under the terms of the:
+# 
+# Eclipse Public License version 1.0
+# GNU General Public License version 2
+# GNU Lesser General Public License version 2.1
+
+module Rubinius
+  module Mirror
+    class Array
+
+      def self.reflect(array)
+        Array.new(array)
+      end
+
+      def initialize(array)
+        @array = array
+      end
+
+      def total
+        @array.size
+      end
+
+    end
+  end
+end
diff --git a/truffle/src/main/ruby/jruby/truffle/core/rubinius/kernel/common/array.rb b/truffle/src/main/ruby/jruby/truffle/core/rubinius/kernel/common/array.rb
@@ -26,6 +26,9 @@
 
 # Only part of Rubinius' array.rb
 
+# Rubinius uses the instance variable @total to store the size. We replace this
+# in the translator with a call to size.
+
 class Array
 
   def self.[](*args)
@@ -150,4 +153,91 @@ def last(n=undefined)
     Array.new self[-n..-1]
   end
 
-end
+  def permutation(num=undefined, &block)
+    return to_enum(:permutation, num) unless block_given?
+
+    if undefined.equal? num
+      num = @total
+    else
+      num = Rubinius::Type.coerce_to_collection_index num
+    end
+
+    if num < 0 || @total < num
+      # no permutations, yield nothing
+    elsif num == 0
+      # exactly one permutation: the zero-length array
+      yield []
+    elsif num == 1
+      # this is a special, easy case
+      each { |val| yield [val] }
+    else
+      # this is the general case
+      perm = Array.new(num)
+      used = Array.new(@total, false)
+
+      if block
+        # offensive (both definitions) copy.
+        offensive = dup
+        Rubinius.privately do
+          offensive.__permute__(num, perm, 0, used, &block)
+        end
+      else
+        __permute__(num, perm, 0, used, &block)
+      end
+    end
+
+    self
+  end
+
+  def __permute__(num, perm, index, used, &block)
+    # Recursively compute permutations of r elements of the set [0..n-1].
+    # When we have a complete permutation of array indexes, copy the values
+    # at those indexes into a new array and yield that array.
+    #
+    # num: the number of elements in each permutation
+    # perm: the array (of size num) that we're filling in
+    # index: what index we're filling in now
+    # used: an array of booleans: whether a given index is already used
+    #
+    # Note: not as efficient as could be for big num.
+    @total.times do |i|
+      unless used[i]
+        perm[index] = i
+        if index < num-1
+          used[i] = true
+          __permute__(num, perm, index+1, used, &block)
+          used[i] = false
+        else
+          yield values_at(*perm)
+        end
+      end
+    end
+  end
+  private :__permute__
+
+  def <=>(other)
+    other = Rubinius::Type.check_convert_type other, Array, :to_ary
+    return 0 if equal? other
+    return nil if other.nil?
+
+    total = Rubinius::Mirror::Array.reflect(other).total
+
+    Thread.detect_recursion self, other do
+      i = 0
+      count = total < @total ? total : @total
+
+      while i < count
+        order = self[i] <=> other[i]
+        return order unless order == 0
+
+        i += 1
+      end
+    end
+
+    # subtle: if we are recursing on that pair, then let's
+    # no go any further down into that pair;
+    # any difference will be found elsewhere if need be
+    @total <=> total
+  end
+
+end