Skip to content

Commit

Permalink
[Truffle] Move Array#- to Ruby.
Browse files Browse the repository at this point in the history
@chrisseaton
chrisseaton committed Feb 6, 2015
1 parent 9f1ad0a commit da5e086
Showing 7 changed files with 389 additions and 146 deletions.
6 changes: 1 addition & 5 deletions spec/truffle/tags/core/array/minus_tags.txt
View file
Original file line number Diff line number Diff line change
@@ -1,5 +1 @@
fails:Array#- tries to convert the passed arguments to Arrays using #to_ary
fails:Array#- does not return subclass instance for Array subclasses
fails:Array#- does not call to_ary on array subclasses
fails:Array#- removes an item identified as equivalent via #hash and #eql?
fails:Array#- doesn't remove an item with the same hash but not #eql?
fails:Array#- properly handles recursive arrays
139 changes: 0 additions & 139 deletions truffle/src/main/java/org/jruby/truffle/nodes/core/ArrayNodes.java
View file
Original file line number Diff line number Diff line change
@@ -187,145 +187,6 @@ public RubyArray addEmptyObject(RubyArray a, RubyArray b) {

}

@CoreMethod(names = "-", required = 1)
public abstract static class SubNode extends ArrayCoreMethodNode {

public SubNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
}

public SubNode(SubNode prev) {
super(prev);
}

@Specialization(guards = "areBothIntegerFixnum")
public RubyArray subIntegerFixnum(RubyArray a, RubyArray b) {
notDesignedForCompilation();

final int[] as = (int[]) a.getStore();
final int[] bs = (int[]) b.getStore();

final int[] sub = new int[a.getSize()];

int i = 0;

for (int n = 0; n < a.getSize(); n++) {
if (!ArrayUtils.contains(bs, as[n])) {
sub[i] = as[n];
i++;
}
}

return new RubyArray(getContext().getCoreLibrary().getArrayClass(), sub, i);
}

@Specialization(guards = "areBothLongFixnum")
public RubyArray subLongFixnum(RubyArray a, RubyArray b) {
notDesignedForCompilation();

final long[] as = (long[]) a.getStore();
final long[] bs = (long[]) b.getStore();

final long[] sub = new long[a.getSize()];

int i = 0;

for (int n = 0; n < a.getSize(); n++) {
if (!ArrayUtils.contains(bs, as[n])) {
sub[i] = as[n];
i++;
}
}

return new RubyArray(getContext().getCoreLibrary().getArrayClass(), sub, i);
}

@Specialization(guards = "areBothFloat")
public RubyArray subDouble(RubyArray a, RubyArray b) {
notDesignedForCompilation();

final double[] as = (double[]) a.getStore();
final double[] bs = (double[]) b.getStore();

final double[] sub = new double[a.getSize()];

int i = 0;

for (int n = 0; n < a.getSize(); n++) {
if (!ArrayUtils.contains(bs, as[n])) {
sub[i] = as[n];
i++;
}
}

return new RubyArray(getContext().getCoreLibrary().getArrayClass(), sub, i);
}

@Specialization(guards = "areBothObject")
public RubyArray subObject(RubyArray a, RubyArray b) {
notDesignedForCompilation();

final Object[] as = (Object[]) a.getStore();
final Object[] bs = (Object[]) b.getStore();

final Object[] sub = new Object[a.getSize()];

int i = 0;

for (int n = 0; n < a.getSize(); n++) {
if (!ArrayUtils.contains(bs, b.getSize(), as[n])) {
sub[i] = as[n];
i++;
}
}

return new RubyArray(getContext().getCoreLibrary().getArrayClass(), sub, i);
}

@Specialization(guards = {"isObject", "isOtherIntegerFixnum"})
public RubyArray subObjectIntegerFixnum(RubyArray a, RubyArray b) {
notDesignedForCompilation();

final Object[] as = (Object[]) a.getStore();
final Object[] bs = ArrayUtils.box((int[]) b.getStore());

final Object[] sub = new Object[a.getSize()];

int i = 0;

for (int n = 0; n < a.getSize(); n++) {
if (!ArrayUtils.contains(bs, b.getSize(), as[n])) {
sub[i] = as[n];
i++;
}
}

return new RubyArray(getContext().getCoreLibrary().getArrayClass(), sub, i);
}

@Specialization
public RubyArray sub(RubyArray a, RubyArray b) {
notDesignedForCompilation();

final Object[] as = a.slowToArray();
final Object[] bs = b.slowToArray();

final Object[] sub = new Object[a.getSize()];

int i = 0;

for (int n = 0; n < a.getSize(); n++) {
if (!ArrayUtils.contains(bs, b.getSize(), as[n])) {
sub[i] = as[n];
i++;
}
}

return new RubyArray(getContext().getCoreLibrary().getArrayClass(), sub, i);
}

}

@CoreMethod(names = "*", required = 1, lowerFixnumParameters = 0)
public abstract static class MulNode extends ArrayCoreMethodNode {

24 changes: 22 additions & 2 deletions truffle/src/main/java/org/jruby/truffle/nodes/rubinius/VMPrimitiveNodes.java
View file
Original file line number Diff line number Diff line change
@@ -109,8 +109,28 @@ public VMObjectEqualPrimitiveNode(VMObjectEqualPrimitiveNode prev) {
}

@Specialization
public Object vmObjectEqual(Object a, Object b) {
throw new UnsupportedOperationException("vm_object_equal");
public Object vmObjectEqual(boolean a, boolean b) {
return a == b;
}

@Specialization
public Object vmObjectEqual(int a, int b) {
return a == b;
}

@Specialization
public Object vmObjectEqual(long a, long b) {
return a == b;
}

@Specialization
public Object vmObjectEqual(double a, double b) {
return a == b;
}

@Specialization
public Object vmObjectEqual(RubyBasicObject a, RubyBasicObject b) {
return a == b;
}

}
2 changes: 2 additions & 0 deletions truffle/src/main/ruby/jruby/truffle/core.rb
View file
Original file line number Diff line number Diff line change
@@ -16,6 +16,7 @@
require_relative 'core/rubinius/api/shims/rubinius'
require_relative 'core/rubinius/api/shims/lookuptable'
require_relative 'core/rubinius/api/shims/thread'
require_relative 'core/rubinius/api/shims/tuple'
require_relative 'core/rubinius/api/shims/undefined'
require_relative 'core/rubinius/api/shims/metrics'

@@ -43,6 +44,7 @@
require_relative 'core/rubinius/kernel/common/kernel'
require_relative 'core/rubinius/kernel/common/comparable'
require_relative 'core/rubinius/kernel/common/numeric'
require_relative 'core/rubinius/kernel/common/identity_map'
require_relative 'core/rubinius/kernel/common/integer'
require_relative 'core/rubinius/kernel/common/fixnum'
require_relative 'core/rubinius/kernel/common/false'
22 changes: 22 additions & 0 deletions truffle/src/main/ruby/jruby/truffle/core/rubinius/api/shims/tuple.rb
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,22 @@
# Copyright (c) 2014 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

class Tuple < Array

def copy_from(other, start, length, dest)
# TODO CS 6-Feb-15 use higher level indexing when it works
length.times do |n|
self[dest + n] = other[start + n]
end
end

end

end
11 changes: 11 additions & 0 deletions truffle/src/main/ruby/jruby/truffle/core/rubinius/kernel/common/array.rb
View file
Original file line number Diff line number Diff line change
@@ -240,4 +240,15 @@ def <=>(other)
@total <=> total
end

def -(other)
other = Rubinius::Type.coerce_to other, Array, :to_ary

array = []
im = Rubinius::IdentityMap.from other

each { |x| array << x unless im.include? x }

array
end

end
331 changes: 331 additions & 0 deletions truffle/src/main/ruby/jruby/truffle/core/rubinius/kernel/common/identity_map.rb
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,331 @@
# Copyright (c) 2007-2014, Evan Phoenix and contributors
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#
# * Redistributions of source code must retain the above copyright notice, this
# list of conditions and the following disclaimer.
# * Redistributions in binary form must reproduce the above copyright notice
# this list of conditions and the following disclaimer in the documentation
# and/or other materials provided with the distribution.
# * Neither the name of Rubinius nor the names of its contributors
# may be used to endorse or promote products derived from this software
# without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

module Rubinius

# IdentityMap is customized for uniquely storing elements from an Array to
# implement the following Array methods: #&, #|, #-, #uniq, and #uniq!
#
# The algorithm used is double hashing with an overflow array. For each
# array element, the element, its hash value, and its ordinal in the
# sequence of elements added to the map are stored.
#
# Methods are provided to test an element for inclusion in the map and to
# delete an entry from the map. The contents of a map can be returned as an
# array in the order the elements were added to the map.

class IdentityMap
attr_reader :size

Row = Table = Rubinius::Tuple
MIN_CAPACITY = 64
MIN_ROW = 10
ROW_GROWTH = 9

# Converts one or more Enumerable instances to a single IdentityMap
def self.from(*arrays, &block)
im = allocate
Rubinius.privately { im.load(arrays, &block) }
im
end

def initialize
capacity = MIN_CAPACITY
@table = Table.new capacity
@mask = capacity - 4
@max = capacity
@size = 0
end

# Adds +item+ to the IdentityMap if it does not already exist. May cause
# a row to be added or enlarged. Returns +self+.
def insert(item, &block)
redistribute if @size > @max

if block_given?
item_hash = yield(item).hash
else
item_hash = item.hash
end

index = item_hash & @mask
table = @table

if num_entries = table[index]
index += 1

if num_entries == 1
return self if match?(table, index, item, item_hash, &block)

table[index-1] = 2
table[index] = promote_row table, index, item, item_hash, @size
else
i = 1
row = table[index]
total = row[0]

while i < total
return self if match?(row, i, item, item_hash, &block)
i += 3
end

if total == row.size
table[index] = enlarge_row row, item, item_hash, @size
else
i = row[0]
set_item row, i, item, item_hash, @size
row[0] = i + 3
end
end
else
table[index] = 1
set_item table, index+1, item, item_hash, @size
end
@size += 1

self
end

# Returns +true+ if +item+ is in the IdentityMap, +false+ otherwise.
def include?(item)
item_hash = item.hash

index = item_hash & @mask
table = @table
if num_entries = table[index]
index += 1

if num_entries == 1
return true if match? table, index, item, item_hash
else
row = table[index]
i = 1
total = row[0]
while i < total
return true if match? row, i, item, item_hash
i += 3
end
end
end

false
end

# If +item+ is in the IdentityMap, removes it and returns +true+.
# Otherwise, returns +false+.
def delete(item)
item_hash = item.hash

index = item_hash & @mask
table = @table

if num_entries = table[index]
index += 1
if num_entries == 1
if match? table, index, item, item_hash
table[index] = nil
@size -= 1
return true
end
else
row = table[index]
i = 1
total = row[0]
while i < total
if match? row, i, item, item_hash
row[i] = nil
@size -= 1
return true
end
i += 3
end
end
end

false
end

# Returns an Array containing all items in the IdentityMap in the order
# in which they were added to the IdentityMap.
def to_array
array = Array.new @size

i = 0
table = @table
total = table.size

while i < total
if num_entries = table[i]
if num_entries == 1
array[table[i+3]] = table[i+2] if table[i+1]
else
row = table[i+1]
k = row[0]
j = 1
while j < k
array[row[j+2]] = row[j+1] if row[j]
j += 3
end
end
end

i += 4
end

array
end

# Private implementation methods

def resize(total)
capacity = MIN_CAPACITY
while capacity < total
capacity <<= 2
end

@table = Table.new capacity
@mask = capacity - 4
@max = capacity
end
private :resize

def redistribute
table = @table
resize @size

i = 0
total = table.size

while i < total
if num_entries = table[i]
if num_entries == 1
if item_hash = table[i+1]
add_item table[i+2], item_hash, table[i+3]
end
else
row = table[i+1]
k = row[0]
j = 1
while j < k
if item_hash = row[j]
add_item row[j+1], item_hash, row[j+2]
end
j += 3
end
end
end

i += 4
end
end
private :redistribute

def add_item(item, item_hash, ordinal)
index = item_hash & @mask
table = @table

if num_entries = table[index]
index += 1

if num_entries == 1
table[index-1] = 2
table[index] = promote_row table, index, item, item_hash, ordinal
else
row = table[index]
i = row[0]

if i == row.size
table[index] = enlarge_row row, item, item_hash, ordinal
else
set_item row, i, item, item_hash, ordinal
row[0] = i + 3
end
end
else
table[index] = 1
set_item table, index+1, item, item_hash, ordinal
end
end
private :add_item

# Given an Array of Enumerable instances, computes a bounding set
# to contain them and then adds each item to the IdentityMap.
def load(arrays, &block)
resize(arrays.inject(0) { |sum, array| sum + array.size })
@size = 0

arrays.each do |array|
array.each { |item| insert(item, &block) }
end
end
private :load

def match?(table, index, item, item_hash)
return false unless table[index] == item_hash
other = table[index+1]
if block_given?
item = yield item
other = yield other
end
Rubinius::Type.object_equal(item, other) or item.eql?(other)
end
private :match?

def set_item(table, index, item, item_hash, ordinal)
table[index] = item_hash
table[index+1] = item
table[index+2] = ordinal
end
private :set_item

def promote_row(row, index, item, item_hash, ordinal)
new_row = Row.new MIN_ROW

new_row[0] = 7
new_row[1] = row[index]
new_row[2] = row[index+1]
new_row[3] = row[index+2]
new_row[4] = item_hash
new_row[5] = item
new_row[6] = ordinal

new_row
end
private :promote_row

def enlarge_row(row, item, item_hash, ordinal)
new_row = Row.new row.size + ROW_GROWTH
new_row.copy_from row, 1, row.size-1, 1

index = row[0]
new_row[0] = index + 3
set_item new_row, index, item, item_hash, ordinal

new_row
end
private :enlarge_row
end
end

0 comments on commit da5e086

Please sign in to comment.