Author: mattip <matti.pi...@gmail.com> Branch: ufuncapi Changeset: r73884:0587bee36e87 Date: 2014-10-10 17:07 +0300 http://bitbucket.org/pypy/pypy/changeset/0587bee36e87/
Log: merge default into branch diff too long, truncating to 2000 out of 10352 lines diff --git a/LICENSE b/LICENSE --- a/LICENSE +++ b/LICENSE @@ -367,3 +367,43 @@ Detailed license information is contained in the NOTICE file in the directory. + +Licenses and Acknowledgements for Incorporated Software +======================================================= + +This section is an incomplete, but growing list of licenses and +acknowledgements for third-party software incorporated in the PyPy +distribution. + +License for 'Tcl/Tk' +-------------------- + +This copy of PyPy contains library code that may, when used, result in +the Tcl/Tk library to be loaded. PyPy also includes code that may be +regarded as being a copy of some parts of the Tcl/Tk header files. +You may see a copy of the License for Tcl/Tk in the file +`lib_pypy/_tkinter/license.terms` included here. + +License for 'bzip2' +------------------- + +This copy of PyPy may be linked (dynamically or statically) with the +bzip2 library. You may see a copy of the License for bzip2/libbzip2 at + + http://www.bzip.org/1.0.5/bzip2-manual-1.0.5.html + +License for 'openssl' +--------------------- + +This copy of PyPy may be linked (dynamically or statically) with the +openssl library. You may see a copy of the License for OpenSSL at + + https://www.openssl.org/source/license.html + +License for 'gdbm' +------------------ + +The gdbm module includes code from gdbm.h, which is distributed under +the terms of the GPL license version 2 or any later version. Thus the +gdbm module, provided in the file lib_pypy/gdbm.py, is redistributed +under the terms of the GPL license as well. diff --git a/lib-python/2.7/test/test_select.py b/lib-python/2.7/test/test_select.py --- a/lib-python/2.7/test/test_select.py +++ b/lib-python/2.7/test/test_select.py @@ -62,7 +62,12 @@ # removes an item and at the middle the iteration stops. # PyPy: 'a' ends up empty, because the iteration is done on # a copy of the original list: fileno() is called 10 times. - self.assert_(len(result[1]) <= 5) + if test_support.check_impl_detail(cpython=True): + self.assertEqual(len(result[1]), 5) + self.assertEqual(len(a), 5) + if test_support.check_impl_detail(pypy=True): + self.assertEqual(len(result[1]), 10) + self.assertEqual(len(a), 0) def test_main(): test_support.run_unittest(SelectTestCase) diff --git a/pypy/doc/whatsnew-head.rst b/pypy/doc/whatsnew-head.rst --- a/pypy/doc/whatsnew-head.rst +++ b/pypy/doc/whatsnew-head.rst @@ -6,3 +6,12 @@ .. this is a revision shortly after release-2.4.x .. startrev: 7026746cbb1b +.. branch: win32-fixes5 +Fix c code generation for msvc so empty "{ }" are avoided in unions, +Avoid re-opening files created with NamedTemporaryFile, +Allocate by 4-byte chunks in rffi_platform, +Skip testing objdump if it does not exist, +and other small adjustments in own tests + +.. branch: rtyper-stuff +Small internal refactorings in the rtyper. diff --git a/pypy/doc/windows.rst b/pypy/doc/windows.rst --- a/pypy/doc/windows.rst +++ b/pypy/doc/windows.rst @@ -37,6 +37,13 @@ using a 32 bit Python and vice versa. By default pypy is built using the Multi-threaded DLL (/MD) runtime environment. +If you wish to override this detection method to use a different compiler +(mingw or a different version of MSVC): + +* set up the PATH and other environment variables as needed +* set the `CC` environment variable to compiler exe to be used, + for a different version of MSVC `SET CC=cl.exe`. + **Note:** PyPy is currently not supported for 64 bit Python, and translation will fail in this case. @@ -264,7 +271,7 @@ Since hacking on PyPy means running tests, you will need a way to specify the mingw compiler when hacking (as opposed to translating). As of March 2012, --cc is not a valid option for pytest.py. However if you set an -environment variable CC to the compliter exe, testing will use it. +environment variable CC to the compiler exe, testing will use it. .. _`mingw32 build`: http://sourceforge.net/projects/mingw-w64/files/Toolchains%20targetting%20Win32/Automated%20Builds .. _`mingw64 build`: http://sourceforge.net/projects/mingw-w64/files/Toolchains%20targetting%20Win64/Automated%20Builds diff --git a/pypy/module/_socket/__init__.py b/pypy/module/_socket/__init__.py --- a/pypy/module/_socket/__init__.py +++ b/pypy/module/_socket/__init__.py @@ -17,8 +17,6 @@ def startup(self, space): from rpython.rlib.rsocket import rsocket_startup rsocket_startup() - from pypy.module._socket.interp_func import State - space.fromcache(State).startup(space) def buildloaders(cls): from rpython.rlib import rsocket diff --git a/pypy/module/_socket/interp_func.py b/pypy/module/_socket/interp_func.py --- a/pypy/module/_socket/interp_func.py +++ b/pypy/module/_socket/interp_func.py @@ -1,5 +1,6 @@ from rpython.rlib import rsocket from rpython.rlib.rsocket import SocketError, INVALID_SOCKET +from rpython.rlib.rarithmetic import intmask from pypy.interpreter.error import OperationError from pypy.interpreter.gateway import unwrap_spec, WrappedDefault @@ -46,9 +47,8 @@ Return the true host name, a list of aliases, and a list of IP addresses, for a host. The host argument is a string giving a host name or IP number. """ - lock = space.fromcache(State).netdb_lock try: - res = rsocket.gethostbyname_ex(host, lock) + res = rsocket.gethostbyname_ex(host) except SocketError, e: raise converted_error(space, e) return common_wrapgethost(space, res) @@ -60,9 +60,8 @@ Return the true host name, a list of aliases, and a list of IP addresses, for a host. The host argument is a string giving a host name or IP number. """ - lock = space.fromcache(State).netdb_lock try: - res = rsocket.gethostbyaddr(host, lock) + res = rsocket.gethostbyaddr(host) except SocketError, e: raise converted_error(space, e) return common_wrapgethost(space, res) @@ -174,7 +173,7 @@ Convert a 16-bit integer from network to host byte order. """ - return space.wrap(rsocket.ntohs(x)) + return space.wrap(rsocket.ntohs(intmask(x))) @unwrap_spec(x="c_uint") def ntohl(space, x): @@ -190,7 +189,7 @@ Convert a 16-bit integer from host to network byte order. """ - return space.wrap(rsocket.htons(x)) + return space.wrap(rsocket.htons(intmask(x))) @unwrap_spec(x="c_uint") def htonl(space, x): @@ -319,10 +318,3 @@ raise OperationError(space.w_ValueError, space.wrap('Timeout value out of range')) rsocket.setdefaulttimeout(timeout) - -class State(object): - def __init__(self, space): - self.netdb_lock = None - - def startup(self, space): - self.netdb_lock = space.allocate_lock() diff --git a/pypy/module/_socket/interp_socket.py b/pypy/module/_socket/interp_socket.py --- a/pypy/module/_socket/interp_socket.py +++ b/pypy/module/_socket/interp_socket.py @@ -109,10 +109,11 @@ # XXX Hack to seperate rpython and pypy def make_ushort_port(space, port): + assert isinstance(port, int) if port < 0 or port > 0xffff: raise OperationError(space.w_OverflowError, space.wrap( "port must be 0-65535.")) - return rffi.cast(rffi.USHORT, port) + return port def make_unsigned_flowinfo(space, flowinfo): if flowinfo < 0 or flowinfo > 0xfffff: @@ -401,8 +402,10 @@ The value argument can either be an integer or a string. """ try: - optval = space.int_w(w_optval) - except: + optval = space.c_int_w(w_optval) + except OperationError, e: + if e.async(space): + raise optval = space.str_w(w_optval) try: self.sock.setsockopt(level, optname, optval) diff --git a/pypy/module/_socket/test/test_sock_app.py b/pypy/module/_socket/test/test_sock_app.py --- a/pypy/module/_socket/test/test_sock_app.py +++ b/pypy/module/_socket/test/test_sock_app.py @@ -498,6 +498,13 @@ s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) reuse = s.getsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR) assert reuse == 0 + # + raises(TypeError, s.setsockopt, socket.SOL_SOCKET, + socket.SO_REUSEADDR, 2 ** 31) + raises(TypeError, s.setsockopt, socket.SOL_SOCKET, + socket.SO_REUSEADDR, 2 ** 32 + 1) + assert s.getsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR) == 0 + # s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1) reuse = s.getsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR) assert reuse != 0 diff --git a/pypy/module/_winreg/interp_winreg.py b/pypy/module/_winreg/interp_winreg.py --- a/pypy/module/_winreg/interp_winreg.py +++ b/pypy/module/_winreg/interp_winreg.py @@ -266,10 +266,16 @@ buf = None if typ == rwinreg.REG_DWORD: - if space.isinstance_w(w_value, space.w_int): + if space.is_none(w_value) or ( + space.isinstance_w(w_value, space.w_int) or + space.isinstance_w(w_value, space.w_long)): + if space.is_none(w_value): + value = r_uint(0) + else: + value = space.c_uint_w(w_value) buflen = rffi.sizeof(rwin32.DWORD) buf1 = lltype.malloc(rffi.CArray(rwin32.DWORD), 1, flavor='raw') - buf1[0] = space.uint_w(w_value) + buf1[0] = value buf = rffi.cast(rffi.CCHARP, buf1) elif typ == rwinreg.REG_SZ or typ == rwinreg.REG_EXPAND_SZ: diff --git a/pypy/module/_winreg/test/test_winreg.py b/pypy/module/_winreg/test/test_winreg.py --- a/pypy/module/_winreg/test/test_winreg.py +++ b/pypy/module/_winreg/test/test_winreg.py @@ -40,7 +40,7 @@ cls.w_tmpfilename = space.wrap(str(udir.join('winreg-temp'))) test_data = [ - ("Int Value", 45, _winreg.REG_DWORD), + ("Int Value", 0xFEDCBA98, _winreg.REG_DWORD), ("Str Value", "A string Value", _winreg.REG_SZ), ("Unicode Value", u"A unicode Value", _winreg.REG_SZ), ("Str Expand", "The path is %path%", _winreg.REG_EXPAND_SZ), @@ -137,9 +137,11 @@ assert 0, "Did not raise" def test_SetValueEx(self): - from _winreg import CreateKey, SetValueEx, REG_BINARY + from _winreg import CreateKey, SetValueEx, REG_BINARY, REG_DWORD key = CreateKey(self.root_key, self.test_key_name) sub_key = CreateKey(key, "sub_key") + SetValueEx(sub_key, 'Int Value', 0, REG_DWORD, None) + SetValueEx(sub_key, 'Int Value', 0, REG_DWORD, 45) for name, value, type in self.test_data: SetValueEx(sub_key, name, 0, type, value) exc = raises(TypeError, SetValueEx, sub_key, 'test_name', None, diff --git a/pypy/module/cpyext/api.py b/pypy/module/cpyext/api.py --- a/pypy/module/cpyext/api.py +++ b/pypy/module/cpyext/api.py @@ -116,6 +116,8 @@ validate_fd(fileno(fp)) return _feof(fp) +def is_valid_fp(fp): + return is_valid_fd(fileno(fp)) constant_names = """ Py_TPFLAGS_READY Py_TPFLAGS_READYING Py_TPFLAGS_HAVE_GETCHARBUFFER diff --git a/pypy/module/cpyext/eval.py b/pypy/module/cpyext/eval.py --- a/pypy/module/cpyext/eval.py +++ b/pypy/module/cpyext/eval.py @@ -3,7 +3,7 @@ from rpython.rtyper.lltypesystem import rffi, lltype from pypy.module.cpyext.api import ( cpython_api, CANNOT_FAIL, CONST_STRING, FILEP, fread, feof, Py_ssize_tP, - cpython_struct) + cpython_struct, is_valid_fp) from pypy.module.cpyext.pyobject import PyObject, borrow_from from pypy.module.cpyext.pyerrors import PyErr_SetFromErrno from pypy.module.cpyext.funcobject import PyCodeObject @@ -154,6 +154,10 @@ source = "" filename = rffi.charp2str(filename) buf = lltype.malloc(rffi.CCHARP.TO, BUF_SIZE, flavor='raw') + if not is_valid_fp(fp): + lltype.free(buf, flavor='raw') + PyErr_SetFromErrno(space, space.w_IOError) + return None try: while True: count = fread(buf, 1, BUF_SIZE, fp) diff --git a/pypy/module/cpyext/test/test_eval.py b/pypy/module/cpyext/test/test_eval.py --- a/pypy/module/cpyext/test/test_eval.py +++ b/pypy/module/cpyext/test/test_eval.py @@ -89,12 +89,12 @@ rffi.free_charp(buf) assert 0 == run("42 * 43") - + assert -1 == run("4..3 * 43") - + assert api.PyErr_Occurred() api.PyErr_Clear() - + def test_run_string(self, space, api): def run(code, start, w_globals, w_locals): buf = rffi.str2charp(code) diff --git a/pypy/module/micronumpy/__init__.py b/pypy/module/micronumpy/__init__.py --- a/pypy/module/micronumpy/__init__.py +++ b/pypy/module/micronumpy/__init__.py @@ -20,6 +20,7 @@ 'concatenate': 'arrayops.concatenate', 'count_nonzero': 'arrayops.count_nonzero', 'dot': 'arrayops.dot', + 'result_type': 'arrayops.result_type', 'where': 'arrayops.where', 'set_string_function': 'appbridge.set_string_function', diff --git a/pypy/module/micronumpy/app_numpy.py b/pypy/module/micronumpy/app_numpy.py --- a/pypy/module/micronumpy/app_numpy.py +++ b/pypy/module/micronumpy/app_numpy.py @@ -16,9 +16,9 @@ dtype = test.dtype length = math.ceil((float(stop) - start) / step) length = int(length) - arr = _numpypy.multiarray.zeros(length, dtype=dtype) + arr = _numpypy.multiarray.empty(length, dtype=dtype) i = start - for j in range(arr.size): + for j in xrange(arr.size): arr[j] = i i += step return arr diff --git a/pypy/module/micronumpy/arrayops.py b/pypy/module/micronumpy/arrayops.py --- a/pypy/module/micronumpy/arrayops.py +++ b/pypy/module/micronumpy/arrayops.py @@ -1,3 +1,4 @@ +from rpython.rlib import jit from pypy.interpreter.error import OperationError, oefmt from pypy.interpreter.gateway import unwrap_spec from pypy.module.micronumpy import loop, descriptor, ufuncs, support, \ @@ -6,6 +7,7 @@ from pypy.module.micronumpy.converters import clipmode_converter from pypy.module.micronumpy.strides import Chunk, Chunks, shape_agreement, \ shape_agreement_multiple +from .boxes import W_GenericBox def where(space, w_arr, w_x=None, w_y=None): @@ -283,3 +285,28 @@ else: loop.diagonal_array(space, arr, out, offset, axis1, axis2, shape) return out + + +@jit.unroll_safe +def result_type(space, __args__): + args_w, kw_w = __args__.unpack() + if kw_w: + raise oefmt(space.w_TypeError, "result_type() takes no keyword arguments") + if not args_w: + raise oefmt(space.w_ValueError, "at least one array or dtype is required") + result = None + for w_arg in args_w: + if isinstance(w_arg, W_NDimArray): + dtype = w_arg.get_dtype() + elif isinstance(w_arg, W_GenericBox) or ( + space.isinstance_w(w_arg, space.w_int) or + space.isinstance_w(w_arg, space.w_float) or + space.isinstance_w(w_arg, space.w_complex) or + space.isinstance_w(w_arg, space.w_long) or + space.isinstance_w(w_arg, space.w_bool)): + dtype = ufuncs.find_dtype_for_scalar(space, w_arg) + else: + dtype = space.interp_w(descriptor.W_Dtype, + space.call_function(space.gettypefor(descriptor.W_Dtype), w_arg)) + result = ufuncs.find_binop_result_dtype(space, result, dtype) + return result diff --git a/pypy/module/micronumpy/compile.py b/pypy/module/micronumpy/compile.py --- a/pypy/module/micronumpy/compile.py +++ b/pypy/module/micronumpy/compile.py @@ -36,7 +36,7 @@ SINGLE_ARG_FUNCTIONS = ["sum", "prod", "max", "min", "all", "any", "unegative", "flat", "tostring","count_nonzero", "argsort"] -TWO_ARG_FUNCTIONS = ["dot", 'take'] +TWO_ARG_FUNCTIONS = ["dot", 'take', 'searchsorted'] TWO_ARG_FUNCTIONS_OR_NONE = ['view', 'astype'] THREE_ARG_FUNCTIONS = ['where'] @@ -109,6 +109,9 @@ if stop < 0: stop += size + 1 if step < 0: + start, stop = stop, start + start -= 1 + stop -= 1 lgt = (stop - start + 1) / step + 1 else: lgt = (stop - start - 1) / step + 1 @@ -475,7 +478,6 @@ class SliceConstant(Node): def __init__(self, start, stop, step): - # no negative support for now self.start = start self.stop = stop self.step = step @@ -582,6 +584,9 @@ w_res = arr.descr_dot(interp.space, arg) elif self.name == 'take': w_res = arr.descr_take(interp.space, arg) + elif self.name == "searchsorted": + w_res = arr.descr_searchsorted(interp.space, arg, + interp.space.wrap('left')) else: assert False # unreachable code elif self.name in THREE_ARG_FUNCTIONS: diff --git a/pypy/module/micronumpy/concrete.py b/pypy/module/micronumpy/concrete.py --- a/pypy/module/micronumpy/concrete.py +++ b/pypy/module/micronumpy/concrete.py @@ -19,6 +19,7 @@ 'strides[*]', 'backstrides[*]', 'order'] start = 0 parent = None + flags = 0 # JIT hints that length of all those arrays is a constant @@ -357,11 +358,11 @@ self.dtype = dtype def argsort(self, space, w_axis): - from pypy.module.micronumpy.sort import argsort_array + from .selection import argsort_array return argsort_array(self, space, w_axis) def sort(self, space, w_axis, w_order): - from pypy.module.micronumpy.sort import sort_array + from .selection import sort_array return sort_array(self, space, w_axis, w_order) def base(self): diff --git a/pypy/module/micronumpy/constants.py b/pypy/module/micronumpy/constants.py --- a/pypy/module/micronumpy/constants.py +++ b/pypy/module/micronumpy/constants.py @@ -65,6 +65,9 @@ FLOATINGLTR = 'f' COMPLEXLTR = 'c' +SEARCHLEFT = 0 +SEARCHRIGHT = 1 + ANYORDER = -1 CORDER = 0 FORTRANORDER = 1 @@ -74,6 +77,9 @@ WRAP = 1 RAISE = 2 +ARRAY_C_CONTIGUOUS = 0x0001 +ARRAY_F_CONTIGUOUS = 0x0002 + LITTLE = '<' BIG = '>' NATIVE = '=' diff --git a/pypy/module/micronumpy/converters.py b/pypy/module/micronumpy/converters.py --- a/pypy/module/micronumpy/converters.py +++ b/pypy/module/micronumpy/converters.py @@ -1,4 +1,4 @@ -from pypy.interpreter.error import OperationError +from pypy.interpreter.error import OperationError, oefmt from pypy.module.micronumpy import constants as NPY @@ -41,6 +41,23 @@ space.wrap("clipmode not understood")) +def searchside_converter(space, w_obj): + try: + s = space.str_w(w_obj) + except OperationError: + s = None + if not s: + raise oefmt(space.w_ValueError, + "expected nonempty string for keyword 'side'") + if s[0] == 'l' or s[0] == 'L': + return NPY.SEARCHLEFT + elif s[0] == 'r' or s[0] == 'R': + return NPY.SEARCHRIGHT + else: + raise oefmt(space.w_ValueError, + "'%s' is an invalid value for keyword 'side'", s) + + def order_converter(space, w_order, default): if space.is_none(w_order): return default diff --git a/pypy/module/micronumpy/ctors.py b/pypy/module/micronumpy/ctors.py --- a/pypy/module/micronumpy/ctors.py +++ b/pypy/module/micronumpy/ctors.py @@ -3,7 +3,7 @@ from rpython.rlib.buffer import SubBuffer from rpython.rlib.rstring import strip_spaces from rpython.rtyper.lltypesystem import lltype, rffi -from pypy.module.micronumpy import descriptor, loop +from pypy.module.micronumpy import descriptor, loop, support from pypy.module.micronumpy.base import ( W_NDimArray, convert_to_array, W_NumpyObject) from pypy.module.micronumpy.converters import shape_converter @@ -134,6 +134,15 @@ if dtype.is_str_or_unicode() and dtype.elsize < 1: dtype = descriptor.variable_dtype(space, dtype.char + '1') shape = shape_converter(space, w_shape, dtype) + for dim in shape: + if dim < 0: + raise OperationError(space.w_ValueError, space.wrap( + "negative dimensions are not allowed")) + try: + support.product(shape) + except OverflowError: + raise OperationError(space.w_ValueError, space.wrap( + "array is too big.")) return W_NDimArray.from_shape(space, shape, dtype=dtype, zero=zero) def empty(space, w_shape, w_dtype=None, w_order=None): diff --git a/pypy/module/micronumpy/flagsobj.py b/pypy/module/micronumpy/flagsobj.py --- a/pypy/module/micronumpy/flagsobj.py +++ b/pypy/module/micronumpy/flagsobj.py @@ -2,6 +2,46 @@ from pypy.interpreter.error import OperationError from pypy.interpreter.gateway import interp2app from pypy.interpreter.typedef import TypeDef, GetSetProperty +from pypy.module.micronumpy import constants as NPY + + +def enable_flags(arr, flags): + arr.flags |= flags + + +def clear_flags(arr, flags): + arr.flags &= ~flags + + +def _update_contiguous_flags(arr): + shape = arr.shape + strides = arr.strides + + is_c_contig = True + sd = arr.dtype.elsize + for i in range(len(shape) - 1, -1, -1): + dim = shape[i] + if strides[i] != sd: + is_c_contig = False + break + if dim == 0: + break + sd *= dim + if is_c_contig: + enable_flags(arr, NPY.ARRAY_C_CONTIGUOUS) + else: + clear_flags(arr, NPY.ARRAY_C_CONTIGUOUS) + + sd = arr.dtype.elsize + for i in range(len(shape)): + dim = shape[i] + if strides[i] != sd: + clear_flags(arr, NPY.ARRAY_F_CONTIGUOUS) + return + if dim == 0: + break + sd *= dim + enable_flags(arr, NPY.ARRAY_F_CONTIGUOUS) class W_FlagsObject(W_Root): diff --git a/pypy/module/micronumpy/flatiter.py b/pypy/module/micronumpy/flatiter.py --- a/pypy/module/micronumpy/flatiter.py +++ b/pypy/module/micronumpy/flatiter.py @@ -1,7 +1,10 @@ from pypy.interpreter.error import OperationError, oefmt +from pypy.interpreter.gateway import interp2app +from pypy.interpreter.typedef import TypeDef, GetSetProperty from pypy.module.micronumpy import loop -from pypy.module.micronumpy.base import W_NDimArray, convert_to_array +from pypy.module.micronumpy.base import convert_to_array from pypy.module.micronumpy.concrete import BaseConcreteArray +from .ndarray import W_NDimArray class FakeArrayImplementation(BaseConcreteArray): @@ -27,12 +30,22 @@ class W_FlatIterator(W_NDimArray): def __init__(self, arr): self.base = arr + self.iter, self.state = arr.create_iter() # this is needed to support W_NDimArray interface self.implementation = FakeArrayImplementation(self.base) - self.reset() - def reset(self): - self.iter, self.state = self.base.create_iter() + def descr_base(self, space): + return space.wrap(self.base) + + def descr_index(self, space): + return space.wrap(self.state.index) + + def descr_coords(self, space): + self.state = self.iter.update(self.state) + return space.newtuple([space.wrap(c) for c in self.state.indices]) + + def descr_iter(self): + return self def descr_len(self, space): return space.wrap(self.iter.size) @@ -44,40 +57,59 @@ self.state = self.iter.next(self.state) return w_res - def descr_index(self, space): - return space.wrap(self.state.index) - - def descr_coords(self, space): - return space.newtuple([space.wrap(c) for c in self.state.indices]) - def descr_getitem(self, space, w_idx): if not (space.isinstance_w(w_idx, space.w_int) or space.isinstance_w(w_idx, space.w_slice)): raise oefmt(space.w_IndexError, 'unsupported iterator index') - self.reset() - base = self.base - start, stop, step, length = space.decode_index4(w_idx, base.get_size()) - base_iter, base_state = base.create_iter() - base_state = base_iter.next_skip_x(base_state, start) - if length == 1: - return base_iter.getitem(base_state) - res = W_NDimArray.from_shape(space, [length], base.get_dtype(), - base.get_order(), w_instance=base) - return loop.flatiter_getitem(res, base_iter, base_state, step) + try: + start, stop, step, length = space.decode_index4(w_idx, self.iter.size) + state = self.iter.goto(start) + if length == 1: + return self.iter.getitem(state) + base = self.base + res = W_NDimArray.from_shape(space, [length], base.get_dtype(), + base.get_order(), w_instance=base) + return loop.flatiter_getitem(res, self.iter, state, step) + finally: + self.state = self.iter.reset(self.state) def descr_setitem(self, space, w_idx, w_value): if not (space.isinstance_w(w_idx, space.w_int) or space.isinstance_w(w_idx, space.w_slice)): raise oefmt(space.w_IndexError, 'unsupported iterator index') - base = self.base - start, stop, step, length = space.decode_index4(w_idx, base.get_size()) - arr = convert_to_array(space, w_value) - loop.flatiter_setitem(space, self.base, arr, start, step, length) + start, stop, step, length = space.decode_index4(w_idx, self.iter.size) + try: + state = self.iter.goto(start) + dtype = self.base.get_dtype() + if length == 1: + try: + val = dtype.coerce(space, w_value) + except OperationError: + raise oefmt(space.w_ValueError, "Error setting single item of array.") + self.iter.setitem(state, val) + return + arr = convert_to_array(space, w_value) + loop.flatiter_setitem(space, dtype, arr, self.iter, state, step, length) + finally: + self.state = self.iter.reset(self.state) - def descr_iter(self): - return self - def descr_base(self, space): - return space.wrap(self.base) +W_FlatIterator.typedef = TypeDef("numpy.flatiter", + base = GetSetProperty(W_FlatIterator.descr_base), + index = GetSetProperty(W_FlatIterator.descr_index), + coords = GetSetProperty(W_FlatIterator.descr_coords), -# typedef is in interp_ndarray, so we see the additional arguments + __iter__ = interp2app(W_FlatIterator.descr_iter), + __len__ = interp2app(W_FlatIterator.descr_len), + next = interp2app(W_FlatIterator.descr_next), + + __getitem__ = interp2app(W_FlatIterator.descr_getitem), + __setitem__ = interp2app(W_FlatIterator.descr_setitem), + + __eq__ = interp2app(W_FlatIterator.descr_eq), + __ne__ = interp2app(W_FlatIterator.descr_ne), + __lt__ = interp2app(W_FlatIterator.descr_lt), + __le__ = interp2app(W_FlatIterator.descr_le), + __gt__ = interp2app(W_FlatIterator.descr_gt), + __ge__ = interp2app(W_FlatIterator.descr_ge), +) diff --git a/pypy/module/micronumpy/iterators.py b/pypy/module/micronumpy/iterators.py --- a/pypy/module/micronumpy/iterators.py +++ b/pypy/module/micronumpy/iterators.py @@ -35,14 +35,11 @@ [x.strides[i] * (x.shape[i] - 1) for i in range(len(x.shape))] we can go faster. All the calculations happen in next() - -next_skip_x(steps) tries to do the iteration for a number of steps at once, -but then we cannot guarantee that we only overflow one single shape -dimension, perhaps we could overflow times in one big step. """ from rpython.rlib import jit -from pypy.module.micronumpy import support +from pypy.module.micronumpy import support, constants as NPY from pypy.module.micronumpy.base import W_NDimArray +from pypy.module.micronumpy.flagsobj import _update_contiguous_flags class PureShapeIter(object): @@ -80,7 +77,7 @@ class IterState(object): - _immutable_fields_ = ['iterator', 'index', 'indices[*]', 'offset'] + _immutable_fields_ = ['iterator', 'index', 'indices', 'offset'] def __init__(self, iterator, index, indices, offset): self.iterator = iterator @@ -90,11 +87,18 @@ class ArrayIter(object): - _immutable_fields_ = ['array', 'size', 'ndim_m1', 'shape_m1[*]', - 'strides[*]', 'backstrides[*]'] + _immutable_fields_ = ['contiguous', 'array', 'size', 'ndim_m1', 'shape_m1[*]', + 'strides[*]', 'backstrides[*]', 'factors[*]', + 'track_index'] + + track_index = True def __init__(self, array, size, shape, strides, backstrides): assert len(shape) == len(strides) == len(backstrides) + _update_contiguous_flags(array) + self.contiguous = (array.flags & NPY.ARRAY_C_CONTIGUOUS and + array.shape == shape and array.strides == strides) + self.array = array self.size = size self.ndim_m1 = len(shape) - 1 @@ -102,52 +106,79 @@ self.strides = strides self.backstrides = backstrides - def reset(self): - return IterState(self, 0, [0] * len(self.shape_m1), self.array.start) + ndim = len(shape) + factors = [0] * ndim + for i in xrange(ndim): + if i == 0: + factors[ndim-1] = 1 + else: + factors[ndim-i-1] = factors[ndim-i] * shape[ndim-i] + self.factors = factors + + @jit.unroll_safe + def reset(self, state=None): + if state is None: + indices = [0] * len(self.shape_m1) + else: + assert state.iterator is self + indices = state.indices + for i in xrange(self.ndim_m1, -1, -1): + indices[i] = 0 + return IterState(self, 0, indices, self.array.start) @jit.unroll_safe def next(self, state): assert state.iterator is self - index = state.index + 1 + index = state.index + if self.track_index: + index += 1 indices = state.indices offset = state.offset - for i in xrange(self.ndim_m1, -1, -1): - idx = indices[i] - if idx < self.shape_m1[i]: - indices[i] = idx + 1 - offset += self.strides[i] - break - else: - indices[i] = 0 - offset -= self.backstrides[i] + if self.contiguous: + offset += self.array.dtype.elsize + else: + for i in xrange(self.ndim_m1, -1, -1): + idx = indices[i] + if idx < self.shape_m1[i]: + indices[i] = idx + 1 + offset += self.strides[i] + break + else: + indices[i] = 0 + offset -= self.backstrides[i] return IterState(self, index, indices, offset) @jit.unroll_safe - def next_skip_x(self, state, step): + def goto(self, index): + offset = self.array.start + if self.contiguous: + offset += index * self.array.dtype.elsize + else: + current = index + for i in xrange(len(self.shape_m1)): + offset += (current / self.factors[i]) * self.strides[i] + current %= self.factors[i] + return IterState(self, index, None, offset) + + @jit.unroll_safe + def update(self, state): assert state.iterator is self - assert step >= 0 - if step == 0: + assert self.track_index + if not self.contiguous: return state - index = state.index + step + current = state.index indices = state.indices - offset = state.offset - for i in xrange(self.ndim_m1, -1, -1): - idx = indices[i] - if idx < (self.shape_m1[i] + 1) - step: - indices[i] = idx + step - offset += self.strides[i] * step - break + for i in xrange(len(self.shape_m1)): + if self.factors[i] != 0: + indices[i] = current / self.factors[i] + current %= self.factors[i] else: - rem_step = (idx + step) // (self.shape_m1[i] + 1) - cur_step = step - rem_step * (self.shape_m1[i] + 1) - indices[i] = idx + cur_step - offset += self.strides[i] * cur_step - step = rem_step - assert step > 0 - return IterState(self, index, indices, offset) + indices[i] = 0 + return IterState(self, state.index, indices, state.offset) def done(self, state): assert state.iterator is self + assert self.track_index return state.index >= self.size def getitem(self, state): diff --git a/pypy/module/micronumpy/loop.py b/pypy/module/micronumpy/loop.py --- a/pypy/module/micronumpy/loop.py +++ b/pypy/module/micronumpy/loop.py @@ -49,6 +49,7 @@ left_iter, left_state = w_lhs.create_iter(shape) right_iter, right_state = w_rhs.create_iter(shape) out_iter, out_state = out.create_iter(shape) + left_iter.track_index = right_iter.track_index = False shapelen = len(shape) while not out_iter.done(out_state): call2_driver.jit_merge_point(shapelen=shapelen, func=func, @@ -72,6 +73,7 @@ out = W_NDimArray.from_shape(space, shape, res_dtype, w_instance=w_obj) obj_iter, obj_state = w_obj.create_iter(shape) out_iter, out_state = out.create_iter(shape) + obj_iter.track_index = False shapelen = len(shape) while not out_iter.done(out_state): call1_driver.jit_merge_point(shapelen=shapelen, func=func, @@ -266,6 +268,9 @@ iter, state = y_iter, y_state else: iter, state = x_iter, x_state + out_iter.track_index = x_iter.track_index = False + arr_iter.track_index = y_iter.track_index = False + iter.track_index = True shapelen = len(shape) while not iter.done(state): where_driver.jit_merge_point(shapelen=shapelen, dtype=dtype, @@ -313,6 +318,7 @@ dtype=dtype) assert not arr_iter.done(arr_state) w_val = arr_iter.getitem(arr_state).convert_to(space, dtype) + out_state = out_iter.update(out_state) if out_state.indices[axis] == 0: if identity is not None: w_val = func(dtype, identity, w_val) @@ -382,6 +388,7 @@ assert left_shape[-1] == right_shape[right_critical_dim] assert result.get_dtype() == dtype outi, outs = result.create_iter() + outi.track_index = False lefti = AllButAxisIter(left_impl, len(left_shape) - 1) righti = AllButAxisIter(right_impl, right_critical_dim) lefts = lefti.reset() @@ -406,7 +413,7 @@ outi.setitem(outs, oval) outs = outi.next(outs) rights = righti.next(rights) - rights = righti.reset() + rights = righti.reset(rights) lefts = lefti.next(lefts) return result @@ -444,6 +451,7 @@ while not arr_iter.done(arr_state): nonzero_driver.jit_merge_point(shapelen=shapelen, dims=dims, dtype=dtype) if arr_iter.getitem_bool(arr_state): + arr_state = arr_iter.update(arr_state) for d in dims: res_iter.setitem(res_state, box(arr_state.indices[d])) res_state = res_iter.next(res_state) @@ -519,7 +527,7 @@ while not ri.done(rs): flatiter_getitem_driver.jit_merge_point(dtype=dtype) ri.setitem(rs, base_iter.getitem(base_state)) - base_state = base_iter.next_skip_x(base_state, step) + base_state = base_iter.goto(base_state.index + step) rs = ri.next(rs) return res @@ -527,11 +535,8 @@ greens = ['dtype'], reds = 'auto') -def flatiter_setitem(space, arr, val, start, step, length): - dtype = arr.get_dtype() - arr_iter, arr_state = arr.create_iter() +def flatiter_setitem(space, dtype, val, arr_iter, arr_state, step, length): val_iter, val_state = val.create_iter() - arr_state = arr_iter.next_skip_x(arr_state, start) while length > 0: flatiter_setitem_driver.jit_merge_point(dtype=dtype) val = val_iter.getitem(val_state) @@ -540,9 +545,10 @@ else: val = val.convert_to(space, dtype) arr_iter.setitem(arr_state, val) - # need to repeat i_nput values until all assignments are done - arr_state = arr_iter.next_skip_x(arr_state, step) + arr_state = arr_iter.goto(arr_state.index + step) val_state = val_iter.next(val_state) + if val_iter.done(val_state): + val_state = val_iter.reset(val_state) length -= 1 fromstring_driver = jit.JitDriver(name = 'numpy_fromstring', @@ -778,3 +784,43 @@ out_iter.setitem(out_state, arr.getitem_index(space, indexes)) iter.next() out_state = out_iter.next(out_state) + +def _new_binsearch(side, op_name): + binsearch_driver = jit.JitDriver(name='numpy_binsearch_' + side, + greens=['dtype'], + reds='auto') + + def binsearch(space, arr, key, ret): + assert len(arr.get_shape()) == 1 + dtype = key.get_dtype() + op = getattr(dtype.itemtype, op_name) + key_iter, key_state = key.create_iter() + ret_iter, ret_state = ret.create_iter() + ret_iter.track_index = False + size = arr.get_size() + min_idx = 0 + max_idx = size + last_key_val = key_iter.getitem(key_state) + while not key_iter.done(key_state): + key_val = key_iter.getitem(key_state) + if dtype.itemtype.lt(last_key_val, key_val): + max_idx = size + else: + min_idx = 0 + max_idx = max_idx + 1 if max_idx < size else size + last_key_val = key_val + while min_idx < max_idx: + binsearch_driver.jit_merge_point(dtype=dtype) + mid_idx = min_idx + ((max_idx - min_idx) >> 1) + mid_val = arr.getitem(space, [mid_idx]).convert_to(space, dtype) + if op(mid_val, key_val): + min_idx = mid_idx + 1 + else: + max_idx = mid_idx + ret_iter.setitem(ret_state, ret.get_dtype().box(min_idx)) + ret_state = ret_iter.next(ret_state) + key_state = key_iter.next(key_state) + return binsearch + +binsearch_left = _new_binsearch('left', 'lt') +binsearch_right = _new_binsearch('right', 'le') diff --git a/pypy/module/micronumpy/ndarray.py b/pypy/module/micronumpy/ndarray.py --- a/pypy/module/micronumpy/ndarray.py +++ b/pypy/module/micronumpy/ndarray.py @@ -16,9 +16,8 @@ ArrayArgumentException, wrap_impl from pypy.module.micronumpy.concrete import BaseConcreteArray from pypy.module.micronumpy.converters import multi_axis_converter, \ - order_converter, shape_converter + order_converter, shape_converter, searchside_converter from pypy.module.micronumpy.flagsobj import W_FlagsObject -from pypy.module.micronumpy.flatiter import W_FlatIterator from pypy.module.micronumpy.strides import get_shape_from_iterable, \ shape_agreement, shape_agreement_multiple @@ -475,10 +474,13 @@ return repeat(space, self, repeats, w_axis) def descr_set_flatiter(self, space, w_obj): + iter, state = self.create_iter() + dtype = self.get_dtype() arr = convert_to_array(space, w_obj) - loop.flatiter_setitem(space, self, arr, 0, 1, self.get_size()) + loop.flatiter_setitem(space, dtype, arr, iter, state, 1, iter.size) def descr_get_flatiter(self, space): + from .flatiter import W_FlatIterator return space.wrap(W_FlatIterator(self)) def descr_item(self, space, __args__): @@ -726,29 +728,22 @@ loop.round(space, self, calc_dtype, self.get_shape(), decimals, out) return out - @unwrap_spec(side=str, w_sorter=WrappedDefault(None)) - def descr_searchsorted(self, space, w_v, side='left', w_sorter=None): + @unwrap_spec(w_side=WrappedDefault('left'), w_sorter=WrappedDefault(None)) + def descr_searchsorted(self, space, w_v, w_side=None, w_sorter=None): if not space.is_none(w_sorter): raise OperationError(space.w_NotImplementedError, space.wrap( 'sorter not supported in searchsort')) - if not side or len(side) < 1: - raise OperationError(space.w_ValueError, space.wrap( - "expected nonempty string for keyword 'side'")) - elif side[0] == 'l' or side[0] == 'L': - side = 'l' - elif side[0] == 'r' or side[0] == 'R': - side = 'r' - else: - raise oefmt(space.w_ValueError, - "'%s' is an invalid value for keyword 'side'", side) - if len(self.get_shape()) > 1: + side = searchside_converter(space, w_side) + if len(self.get_shape()) != 1: raise oefmt(space.w_ValueError, "a must be a 1-d array") v = convert_to_array(space, w_v) - if len(v.get_shape()) > 1: - raise oefmt(space.w_ValueError, "v must be a 1-d array-like") ret = W_NDimArray.from_shape( space, v.get_shape(), descriptor.get_dtype_cache(space).w_longdtype) - app_searchsort(space, self, v, space.wrap(side), ret) + if side == NPY.SEARCHLEFT: + binsearch = loop.binsearch_left + else: + binsearch = loop.binsearch_right + binsearch(space, self, v, ret) if ret.is_scalar(): return ret.get_scalar_value() return ret @@ -1311,31 +1306,6 @@ return res """, filename=__file__).interphook('ptp') -app_searchsort = applevel(r""" - def searchsort(arr, v, side, result): - import operator - def func(a, op, val): - imin = 0 - imax = a.size - while imin < imax: - imid = imin + ((imax - imin) >> 1) - if op(a[imid], val): - imin = imid +1 - else: - imax = imid - return imin - if side == 'l': - op = operator.lt - else: - op = operator.le - if v.size < 2: - result[...] = func(arr, op, v) - else: - for i in range(v.size): - result[i] = func(arr, op, v[i]) - return result -""", filename=__file__).interphook('searchsort') - W_NDimArray.typedef = TypeDef("numpy.ndarray", __new__ = interp2app(descr_new_array), @@ -1423,6 +1393,7 @@ flags = GetSetProperty(W_NDimArray.descr_get_flags), fill = interp2app(W_NDimArray.descr_fill), + tobytes = interp2app(W_NDimArray.descr_tostring), tostring = interp2app(W_NDimArray.descr_tostring), mean = interp2app(W_NDimArray.descr_mean), @@ -1501,23 +1472,3 @@ def _reconstruct(space, w_subtype, w_shape, w_dtype): return descr_new_array(space, w_subtype, w_shape, w_dtype) - - -W_FlatIterator.typedef = TypeDef("numpy.flatiter", - __iter__ = interp2app(W_FlatIterator.descr_iter), - __getitem__ = interp2app(W_FlatIterator.descr_getitem), - __setitem__ = interp2app(W_FlatIterator.descr_setitem), - __len__ = interp2app(W_FlatIterator.descr_len), - - __eq__ = interp2app(W_FlatIterator.descr_eq), - __ne__ = interp2app(W_FlatIterator.descr_ne), - __lt__ = interp2app(W_FlatIterator.descr_lt), - __le__ = interp2app(W_FlatIterator.descr_le), - __gt__ = interp2app(W_FlatIterator.descr_gt), - __ge__ = interp2app(W_FlatIterator.descr_ge), - - next = interp2app(W_FlatIterator.descr_next), - base = GetSetProperty(W_FlatIterator.descr_base), - index = GetSetProperty(W_FlatIterator.descr_index), - coords = GetSetProperty(W_FlatIterator.descr_coords), -) diff --git a/pypy/module/micronumpy/nditer.py b/pypy/module/micronumpy/nditer.py --- a/pypy/module/micronumpy/nditer.py +++ b/pypy/module/micronumpy/nditer.py @@ -313,6 +313,7 @@ # create an iterator for each operand for i in range(len(self.seq)): it = get_iter(space, self.order, self.seq[i], iter_shape, self.dtypes[i]) + it.contiguous = False self.iters.append((it, it.reset())) def set_op_axes(self, space, w_op_axes): diff --git a/pypy/module/micronumpy/selection.py b/pypy/module/micronumpy/selection.py new file mode 100644 --- /dev/null +++ b/pypy/module/micronumpy/selection.py @@ -0,0 +1,355 @@ +from pypy.interpreter.error import oefmt +from rpython.rlib.listsort import make_timsort_class +from rpython.rlib.objectmodel import specialize +from rpython.rlib.rarithmetic import widen +from rpython.rlib.rawstorage import raw_storage_getitem, raw_storage_setitem, \ + free_raw_storage, alloc_raw_storage +from rpython.rlib.unroll import unrolling_iterable +from rpython.rtyper.lltypesystem import rffi, lltype +from pypy.module.micronumpy import descriptor, types, constants as NPY +from pypy.module.micronumpy.base import W_NDimArray +from pypy.module.micronumpy.iterators import AllButAxisIter + +INT_SIZE = rffi.sizeof(lltype.Signed) + +all_types = (types.all_float_types + types.all_complex_types + + types.all_int_types) +all_types = [i for i in all_types if not issubclass(i[0], types.Float16)] +all_types = unrolling_iterable(all_types) + + +def make_argsort_function(space, itemtype, comp_type, count=1): + TP = itemtype.T + step = rffi.sizeof(TP) + + class Repr(object): + def __init__(self, index_stride_size, stride_size, size, values, + indexes, index_start, start): + self.index_stride_size = index_stride_size + self.stride_size = stride_size + self.index_start = index_start + self.start = start + self.size = size + self.values = values + self.indexes = indexes + + def getitem(self, item): + if count < 2: + v = raw_storage_getitem(TP, self.values, item * self.stride_size + + self.start) + else: + v = [] + for i in range(count): + _v = raw_storage_getitem(TP, self.values, item * self.stride_size + + self.start + step * i) + v.append(_v) + if comp_type == 'int': + v = widen(v) + elif comp_type == 'float': + v = float(v) + elif comp_type == 'complex': + v = [float(v[0]),float(v[1])] + else: + raise NotImplementedError('cannot reach') + return (v, raw_storage_getitem(lltype.Signed, self.indexes, + item * self.index_stride_size + + self.index_start)) + + def setitem(self, idx, item): + if count < 2: + raw_storage_setitem(self.values, idx * self.stride_size + + self.start, rffi.cast(TP, item[0])) + else: + i = 0 + for val in item[0]: + raw_storage_setitem(self.values, idx * self.stride_size + + self.start + i*step, rffi.cast(TP, val)) + i += 1 + raw_storage_setitem(self.indexes, idx * self.index_stride_size + + self.index_start, item[1]) + + class ArgArrayRepWithStorage(Repr): + def __init__(self, index_stride_size, stride_size, size): + start = 0 + dtype = descriptor.get_dtype_cache(space).w_longdtype + indexes = dtype.itemtype.malloc(size * dtype.elsize) + values = alloc_raw_storage(size * stride_size, + track_allocation=False) + Repr.__init__(self, dtype.elsize, stride_size, + size, values, indexes, start, start) + + def __del__(self): + free_raw_storage(self.indexes, track_allocation=False) + free_raw_storage(self.values, track_allocation=False) + + def arg_getitem(lst, item): + return lst.getitem(item) + + def arg_setitem(lst, item, value): + lst.setitem(item, value) + + def arg_length(lst): + return lst.size + + def arg_getitem_slice(lst, start, stop): + retval = ArgArrayRepWithStorage(lst.index_stride_size, lst.stride_size, + stop-start) + for i in range(stop-start): + retval.setitem(i, lst.getitem(i+start)) + return retval + + if count < 2: + def arg_lt(a, b): + # Does numpy do <= ? + return a[0] < b[0] or b[0] != b[0] and a[0] == a[0] + else: + def arg_lt(a, b): + for i in range(count): + if b[0][i] != b[0][i] and a[0][i] == a[0][i]: + return True + elif b[0][i] == b[0][i] and a[0][i] != a[0][i]: + return False + for i in range(count): + if a[0][i] < b[0][i]: + return True + elif a[0][i] > b[0][i]: + return False + # Does numpy do True? + return False + + ArgSort = make_timsort_class(arg_getitem, arg_setitem, arg_length, + arg_getitem_slice, arg_lt) + + def argsort(arr, space, w_axis, itemsize): + if w_axis is space.w_None: + # note that it's fine ot pass None here as we're not going + # to pass the result around (None is the link to base in slices) + if arr.get_size() > 0: + arr = arr.reshape(None, [arr.get_size()]) + axis = 0 + elif w_axis is None: + axis = -1 + else: + axis = space.int_w(w_axis) + # create array of indexes + dtype = descriptor.get_dtype_cache(space).w_longdtype + index_arr = W_NDimArray.from_shape(space, arr.get_shape(), dtype) + storage = index_arr.implementation.get_storage() + if len(arr.get_shape()) == 1: + for i in range(arr.get_size()): + raw_storage_setitem(storage, i * INT_SIZE, i) + r = Repr(INT_SIZE, itemsize, arr.get_size(), arr.get_storage(), + storage, 0, arr.start) + ArgSort(r).sort() + else: + shape = arr.get_shape() + if axis < 0: + axis = len(shape) + axis + if axis < 0 or axis >= len(shape): + raise oefmt(space.w_IndexError, "Wrong axis %d", axis) + arr_iter = AllButAxisIter(arr, axis) + arr_state = arr_iter.reset() + index_impl = index_arr.implementation + index_iter = AllButAxisIter(index_impl, axis) + index_state = index_iter.reset() + stride_size = arr.strides[axis] + index_stride_size = index_impl.strides[axis] + axis_size = arr.shape[axis] + while not arr_iter.done(arr_state): + for i in range(axis_size): + raw_storage_setitem(storage, i * index_stride_size + + index_state.offset, i) + r = Repr(index_stride_size, stride_size, axis_size, + arr.get_storage(), storage, index_state.offset, arr_state.offset) + ArgSort(r).sort() + arr_state = arr_iter.next(arr_state) + index_state = index_iter.next(index_state) + return index_arr + + return argsort + + +def argsort_array(arr, space, w_axis): + cache = space.fromcache(ArgSortCache) # that populates ArgSortClasses + itemtype = arr.dtype.itemtype + for tp in all_types: + if isinstance(itemtype, tp[0]): + return cache._lookup(tp)(arr, space, w_axis, + itemtype.get_element_size()) + # XXX this should probably be changed + raise oefmt(space.w_NotImplementedError, + "sorting of non-numeric types '%s' is not implemented", + arr.dtype.get_name()) + + +def make_sort_function(space, itemtype, comp_type, count=1): + TP = itemtype.T + step = rffi.sizeof(TP) + + class Repr(object): + def __init__(self, stride_size, size, values, start): + self.stride_size = stride_size + self.start = start + self.size = size + self.values = values + + def getitem(self, item): + if count < 2: + v = raw_storage_getitem(TP, self.values, item * self.stride_size + + self.start) + else: + v = [] + for i in range(count): + _v = raw_storage_getitem(TP, self.values, item * self.stride_size + + self.start + step * i) + v.append(_v) + if comp_type == 'int': + v = widen(v) + elif comp_type == 'float': + v = float(v) + elif comp_type == 'complex': + v = [float(v[0]),float(v[1])] + else: + raise NotImplementedError('cannot reach') + return (v) + + def setitem(self, idx, item): + if count < 2: + raw_storage_setitem(self.values, idx * self.stride_size + + self.start, rffi.cast(TP, item)) + else: + i = 0 + for val in item: + raw_storage_setitem(self.values, idx * self.stride_size + + self.start + i*step, rffi.cast(TP, val)) + i += 1 + + class ArgArrayRepWithStorage(Repr): + def __init__(self, stride_size, size): + start = 0 + values = alloc_raw_storage(size * stride_size, + track_allocation=False) + Repr.__init__(self, stride_size, + size, values, start) + + def __del__(self): + free_raw_storage(self.values, track_allocation=False) + + def arg_getitem(lst, item): + return lst.getitem(item) + + def arg_setitem(lst, item, value): + lst.setitem(item, value) + + def arg_length(lst): + return lst.size + + def arg_getitem_slice(lst, start, stop): + retval = ArgArrayRepWithStorage(lst.stride_size, stop-start) + for i in range(stop-start): + retval.setitem(i, lst.getitem(i+start)) + return retval + + if count < 2: + def arg_lt(a, b): + # handles NAN and INF + return a < b or b != b and a == a + else: + def arg_lt(a, b): + for i in range(count): + if b[i] != b[i] and a[i] == a[i]: + return True + elif b[i] == b[i] and a[i] != a[i]: + return False + for i in range(count): + if a[i] < b[i]: + return True + elif a[i] > b[i]: + return False + # Does numpy do True? + return False + + ArgSort = make_timsort_class(arg_getitem, arg_setitem, arg_length, + arg_getitem_slice, arg_lt) + + def sort(arr, space, w_axis, itemsize): + if w_axis is space.w_None: + # note that it's fine to pass None here as we're not going + # to pass the result around (None is the link to base in slices) + arr = arr.reshape(None, [arr.get_size()]) + axis = 0 + elif w_axis is None: + axis = -1 + else: + axis = space.int_w(w_axis) + # create array of indexes + if len(arr.get_shape()) == 1: + r = Repr(itemsize, arr.get_size(), arr.get_storage(), + arr.start) + ArgSort(r).sort() + else: + shape = arr.get_shape() + if axis < 0: + axis = len(shape) + axis + if axis < 0 or axis >= len(shape): + raise oefmt(space.w_IndexError, "Wrong axis %d", axis) + arr_iter = AllButAxisIter(arr, axis) + arr_state = arr_iter.reset() + stride_size = arr.strides[axis] + axis_size = arr.shape[axis] + while not arr_iter.done(arr_state): + r = Repr(stride_size, axis_size, arr.get_storage(), arr_state.offset) + ArgSort(r).sort() + arr_state = arr_iter.next(arr_state) + + return sort + + +def sort_array(arr, space, w_axis, w_order): + cache = space.fromcache(SortCache) # that populates SortClasses + itemtype = arr.dtype.itemtype + if arr.dtype.byteorder == NPY.OPPBYTE: + raise oefmt(space.w_NotImplementedError, + "sorting of non-native byteorder not supported yet") + for tp in all_types: + if isinstance(itemtype, tp[0]): + return cache._lookup(tp)(arr, space, w_axis, + itemtype.get_element_size()) + # XXX this should probably be changed + raise oefmt(space.w_NotImplementedError, + "sorting of non-numeric types '%s' is not implemented", + arr.dtype.get_name()) + + +class ArgSortCache(object): + built = False + + def __init__(self, space): + if self.built: + return + self.built = True + cache = {} + for cls, it in all_types._items: + if it == 'complex': + cache[cls] = make_argsort_function(space, cls, it, 2) + else: + cache[cls] = make_argsort_function(space, cls, it) + self.cache = cache + self._lookup = specialize.memo()(lambda tp: cache[tp[0]]) + + +class SortCache(object): + built = False + + def __init__(self, space): + if self.built: + return + self.built = True + cache = {} + for cls, it in all_types._items: + if it == 'complex': + cache[cls] = make_sort_function(space, cls, it, 2) + else: + cache[cls] = make_sort_function(space, cls, it) + self.cache = cache + self._lookup = specialize.memo()(lambda tp: cache[tp[0]]) diff --git a/pypy/module/micronumpy/sort.py b/pypy/module/micronumpy/sort.py deleted file mode 100644 --- a/pypy/module/micronumpy/sort.py +++ /dev/null @@ -1,355 +0,0 @@ -from pypy.interpreter.error import oefmt -from rpython.rlib.listsort import make_timsort_class -from rpython.rlib.objectmodel import specialize -from rpython.rlib.rarithmetic import widen -from rpython.rlib.rawstorage import raw_storage_getitem, raw_storage_setitem, \ - free_raw_storage, alloc_raw_storage -from rpython.rlib.unroll import unrolling_iterable -from rpython.rtyper.lltypesystem import rffi, lltype -from pypy.module.micronumpy import descriptor, types, constants as NPY -from pypy.module.micronumpy.base import W_NDimArray -from pypy.module.micronumpy.iterators import AllButAxisIter - -INT_SIZE = rffi.sizeof(lltype.Signed) - -all_types = (types.all_float_types + types.all_complex_types + - types.all_int_types) -all_types = [i for i in all_types if not issubclass(i[0], types.Float16)] -all_types = unrolling_iterable(all_types) - - -def make_argsort_function(space, itemtype, comp_type, count=1): - TP = itemtype.T - step = rffi.sizeof(TP) - - class Repr(object): - def __init__(self, index_stride_size, stride_size, size, values, - indexes, index_start, start): - self.index_stride_size = index_stride_size - self.stride_size = stride_size - self.index_start = index_start - self.start = start - self.size = size - self.values = values - self.indexes = indexes - - def getitem(self, item): - if count < 2: - v = raw_storage_getitem(TP, self.values, item * self.stride_size - + self.start) - else: - v = [] - for i in range(count): - _v = raw_storage_getitem(TP, self.values, item * self.stride_size - + self.start + step * i) - v.append(_v) - if comp_type == 'int': - v = widen(v) - elif comp_type == 'float': - v = float(v) - elif comp_type == 'complex': - v = [float(v[0]),float(v[1])] - else: - raise NotImplementedError('cannot reach') - return (v, raw_storage_getitem(lltype.Signed, self.indexes, - item * self.index_stride_size + - self.index_start)) - - def setitem(self, idx, item): - if count < 2: - raw_storage_setitem(self.values, idx * self.stride_size + - self.start, rffi.cast(TP, item[0])) - else: - i = 0 - for val in item[0]: - raw_storage_setitem(self.values, idx * self.stride_size + - self.start + i*step, rffi.cast(TP, val)) - i += 1 - raw_storage_setitem(self.indexes, idx * self.index_stride_size + - self.index_start, item[1]) - - class ArgArrayRepWithStorage(Repr): - def __init__(self, index_stride_size, stride_size, size): - start = 0 - dtype = descriptor.get_dtype_cache(space).w_longdtype - indexes = dtype.itemtype.malloc(size * dtype.elsize) - values = alloc_raw_storage(size * stride_size, - track_allocation=False) - Repr.__init__(self, dtype.elsize, stride_size, - size, values, indexes, start, start) - - def __del__(self): - free_raw_storage(self.indexes, track_allocation=False) - free_raw_storage(self.values, track_allocation=False) - - def arg_getitem(lst, item): - return lst.getitem(item) - - def arg_setitem(lst, item, value): - lst.setitem(item, value) - - def arg_length(lst): - return lst.size - - def arg_getitem_slice(lst, start, stop): - retval = ArgArrayRepWithStorage(lst.index_stride_size, lst.stride_size, - stop-start) - for i in range(stop-start): - retval.setitem(i, lst.getitem(i+start)) - return retval - - if count < 2: - def arg_lt(a, b): - # Does numpy do <= ? - return a[0] < b[0] or b[0] != b[0] and a[0] == a[0] - else: - def arg_lt(a, b): - for i in range(count): - if b[0][i] != b[0][i] and a[0][i] == a[0][i]: - return True - elif b[0][i] == b[0][i] and a[0][i] != a[0][i]: - return False - for i in range(count): - if a[0][i] < b[0][i]: - return True - elif a[0][i] > b[0][i]: - return False - # Does numpy do True? - return False - - ArgSort = make_timsort_class(arg_getitem, arg_setitem, arg_length, - arg_getitem_slice, arg_lt) - - def argsort(arr, space, w_axis, itemsize): - if w_axis is space.w_None: - # note that it's fine ot pass None here as we're not going - # to pass the result around (None is the link to base in slices) - if arr.get_size() > 0: - arr = arr.reshape(None, [arr.get_size()]) - axis = 0 - elif w_axis is None: - axis = -1 - else: - axis = space.int_w(w_axis) - # create array of indexes - dtype = descriptor.get_dtype_cache(space).w_longdtype - index_arr = W_NDimArray.from_shape(space, arr.get_shape(), dtype) - storage = index_arr.implementation.get_storage() - if len(arr.get_shape()) == 1: - for i in range(arr.get_size()): - raw_storage_setitem(storage, i * INT_SIZE, i) - r = Repr(INT_SIZE, itemsize, arr.get_size(), arr.get_storage(), - storage, 0, arr.start) - ArgSort(r).sort() - else: - shape = arr.get_shape() - if axis < 0: - axis = len(shape) + axis - if axis < 0 or axis >= len(shape): - raise oefmt(space.w_IndexError, "Wrong axis %d", axis) - arr_iter = AllButAxisIter(arr, axis) - arr_state = arr_iter.reset() - index_impl = index_arr.implementation - index_iter = AllButAxisIter(index_impl, axis) - index_state = index_iter.reset() - stride_size = arr.strides[axis] - index_stride_size = index_impl.strides[axis] - axis_size = arr.shape[axis] - while not arr_iter.done(arr_state): - for i in range(axis_size): - raw_storage_setitem(storage, i * index_stride_size + - index_state.offset, i) - r = Repr(index_stride_size, stride_size, axis_size, - arr.get_storage(), storage, index_state.offset, arr_state.offset) - ArgSort(r).sort() - arr_state = arr_iter.next(arr_state) - index_state = index_iter.next(index_state) - return index_arr - - return argsort - - -def argsort_array(arr, space, w_axis): - cache = space.fromcache(ArgSortCache) # that populates ArgSortClasses - itemtype = arr.dtype.itemtype - for tp in all_types: - if isinstance(itemtype, tp[0]): - return cache._lookup(tp)(arr, space, w_axis, - itemtype.get_element_size()) - # XXX this should probably be changed - raise oefmt(space.w_NotImplementedError, - "sorting of non-numeric types '%s' is not implemented", - arr.dtype.get_name()) - - -def make_sort_function(space, itemtype, comp_type, count=1): - TP = itemtype.T - step = rffi.sizeof(TP) - - class Repr(object): - def __init__(self, stride_size, size, values, start): - self.stride_size = stride_size - self.start = start - self.size = size - self.values = values - - def getitem(self, item): - if count < 2: - v = raw_storage_getitem(TP, self.values, item * self.stride_size - + self.start) - else: - v = [] - for i in range(count): - _v = raw_storage_getitem(TP, self.values, item * self.stride_size - + self.start + step * i) - v.append(_v) - if comp_type == 'int': - v = widen(v) - elif comp_type == 'float': - v = float(v) - elif comp_type == 'complex': - v = [float(v[0]),float(v[1])] - else: - raise NotImplementedError('cannot reach') - return (v) - - def setitem(self, idx, item): - if count < 2: - raw_storage_setitem(self.values, idx * self.stride_size + - self.start, rffi.cast(TP, item)) - else: - i = 0 - for val in item: - raw_storage_setitem(self.values, idx * self.stride_size + - self.start + i*step, rffi.cast(TP, val)) - i += 1 - - class ArgArrayRepWithStorage(Repr): - def __init__(self, stride_size, size): - start = 0 - values = alloc_raw_storage(size * stride_size, - track_allocation=False) - Repr.__init__(self, stride_size, - size, values, start) - - def __del__(self): - free_raw_storage(self.values, track_allocation=False) - - def arg_getitem(lst, item): - return lst.getitem(item) - - def arg_setitem(lst, item, value): - lst.setitem(item, value) - - def arg_length(lst): - return lst.size - - def arg_getitem_slice(lst, start, stop): - retval = ArgArrayRepWithStorage(lst.stride_size, stop-start) - for i in range(stop-start): - retval.setitem(i, lst.getitem(i+start)) - return retval - - if count < 2: - def arg_lt(a, b): - # handles NAN and INF - return a < b or b != b and a == a - else: - def arg_lt(a, b): - for i in range(count): - if b[i] != b[i] and a[i] == a[i]: - return True - elif b[i] == b[i] and a[i] != a[i]: - return False - for i in range(count): - if a[i] < b[i]: - return True - elif a[i] > b[i]: - return False - # Does numpy do True? - return False - - ArgSort = make_timsort_class(arg_getitem, arg_setitem, arg_length, - arg_getitem_slice, arg_lt) - - def sort(arr, space, w_axis, itemsize): - if w_axis is space.w_None: - # note that it's fine to pass None here as we're not going - # to pass the result around (None is the link to base in slices) - arr = arr.reshape(None, [arr.get_size()]) - axis = 0 - elif w_axis is None: - axis = -1 - else: - axis = space.int_w(w_axis) - # create array of indexes - if len(arr.get_shape()) == 1: - r = Repr(itemsize, arr.get_size(), arr.get_storage(), - arr.start) - ArgSort(r).sort() - else: - shape = arr.get_shape() - if axis < 0: - axis = len(shape) + axis - if axis < 0 or axis >= len(shape): - raise oefmt(space.w_IndexError, "Wrong axis %d", axis) - arr_iter = AllButAxisIter(arr, axis) - arr_state = arr_iter.reset() - stride_size = arr.strides[axis] - axis_size = arr.shape[axis] - while not arr_iter.done(arr_state): - r = Repr(stride_size, axis_size, arr.get_storage(), arr_state.offset) - ArgSort(r).sort() - arr_state = arr_iter.next(arr_state) - - return sort - - -def sort_array(arr, space, w_axis, w_order): - cache = space.fromcache(SortCache) # that populates SortClasses - itemtype = arr.dtype.itemtype - if arr.dtype.byteorder == NPY.OPPBYTE: - raise oefmt(space.w_NotImplementedError, - "sorting of non-native byteorder not supported yet") - for tp in all_types: - if isinstance(itemtype, tp[0]): - return cache._lookup(tp)(arr, space, w_axis, - itemtype.get_element_size()) - # XXX this should probably be changed - raise oefmt(space.w_NotImplementedError, - "sorting of non-numeric types '%s' is not implemented", - arr.dtype.get_name()) - - -class ArgSortCache(object): - built = False - - def __init__(self, space): - if self.built: - return - self.built = True - cache = {} - for cls, it in all_types._items: - if it == 'complex': - cache[cls] = make_argsort_function(space, cls, it, 2) - else: - cache[cls] = make_argsort_function(space, cls, it) - self.cache = cache - self._lookup = specialize.memo()(lambda tp: cache[tp[0]]) - - -class SortCache(object): - built = False - - def __init__(self, space): - if self.built: - return - self.built = True - cache = {} - for cls, it in all_types._items: - if it == 'complex': - cache[cls] = make_sort_function(space, cls, it, 2) - else: - cache[cls] = make_sort_function(space, cls, it) - self.cache = cache - self._lookup = specialize.memo()(lambda tp: cache[tp[0]]) diff --git a/pypy/module/micronumpy/support.py b/pypy/module/micronumpy/support.py --- a/pypy/module/micronumpy/support.py +++ b/pypy/module/micronumpy/support.py @@ -1,5 +1,6 @@ from pypy.interpreter.error import OperationError, oefmt from rpython.rlib import jit +from rpython.rlib.rarithmetic import ovfcheck def issequence_w(space, w_obj): @@ -23,7 +24,7 @@ def product(s): i = 1 for x in s: - i *= x + i = ovfcheck(i * x) return i diff --git a/pypy/module/micronumpy/test/test_arrayops.py b/pypy/module/micronumpy/test/test_arrayops.py --- a/pypy/module/micronumpy/test/test_arrayops.py +++ b/pypy/module/micronumpy/test/test_arrayops.py @@ -199,3 +199,19 @@ a.put(23, -1, mode=1) # wrap assert (a == array([0, 1, -10, -1, -15])).all() raises(TypeError, "arange(5).put(22, -5, mode='zzzz')") # unrecognized mode + + def test_result_type(self): + import numpy as np + exc = raises(ValueError, np.result_type) + assert str(exc.value) == "at least one array or dtype is required" + exc = raises(TypeError, np.result_type, a=2) + assert str(exc.value) == "result_type() takes no keyword arguments" + assert np.result_type(True) is np.dtype('bool') + assert np.result_type(1) is np.dtype('int') + assert np.result_type(1.) is np.dtype('float64') + assert np.result_type(1+2j) is np.dtype('complex128') + assert np.result_type(1, 1.) is np.dtype('float64') + assert np.result_type(np.array([1, 2])) is np.dtype('int64') + assert np.result_type(np.array([1, 2]), 1, 1+2j) is np.dtype('complex128') + assert np.result_type(np.array([1, 2]), 1, 'float64') is np.dtype('float64') + assert np.result_type(np.array([1, 2]), 1, None) is np.dtype('float64') diff --git a/pypy/module/micronumpy/test/test_compile.py b/pypy/module/micronumpy/test/test_compile.py --- a/pypy/module/micronumpy/test/test_compile.py +++ b/pypy/module/micronumpy/test/test_compile.py @@ -330,3 +330,12 @@ results = interp.results[0] assert isinstance(results, W_NDimArray) assert results.get_dtype().is_int() + + def test_searchsorted(self): + interp = self.run(''' + a = [1, 4, 5, 6, 9] + b = |30| -> ::-1 + c = searchsorted(a, b) + c -> -1 + ''') + assert interp.results[0].value == 0 diff --git a/pypy/module/micronumpy/test/test_iterators.py b/pypy/module/micronumpy/test/test_iterators.py --- a/pypy/module/micronumpy/test/test_iterators.py +++ b/pypy/module/micronumpy/test/test_iterators.py @@ -3,7 +3,15 @@ class MockArray(object): - start = 0 + flags = 0 + + class dtype: + elsize = 1 + + def __init__(self, shape, strides, start=0): + self.shape = shape + self.strides = strides + self.start = start class TestIterDirect(object): @@ -14,19 +22,24 @@ strides = [5, 1] backstrides = [x * (y - 1) for x,y in zip(strides, shape)] assert backstrides == [10, 4] - i = ArrayIter(MockArray, support.product(shape), shape, + i = ArrayIter(MockArray(shape, strides), support.product(shape), shape, strides, backstrides) + assert i.contiguous s = i.reset() s = i.next(s) s = i.next(s) s = i.next(s) assert s.offset == 3 assert not i.done(s) + assert s.indices == [0,0] + s = i.update(s) assert s.indices == [0,3] #cause a dimension overflow s = i.next(s) s = i.next(s) assert s.offset == 5 + assert s.indices == [0,3] + s = i.update(s) assert s.indices == [1,0] #Now what happens if the array is transposed? strides[-1] != 1 @@ -34,8 +47,9 @@ strides = [1, 3] backstrides = [x * (y - 1) for x,y in zip(strides, shape)] assert backstrides == [2, 12] - i = ArrayIter(MockArray, support.product(shape), shape, + i = ArrayIter(MockArray(shape, strides), support.product(shape), shape, strides, backstrides) + assert not i.contiguous s = i.reset() s = i.next(s) _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
