this broke the pickling of enumerate: http://codespeak.net:8099/summary/longrepr?testname=AppTestInterpObjectPickling().test_pickle_enum&builder=own-linux-x86-32&build=541&mod=pypy.interpreter.test.test_zzpickle_and_slow
I suppose reversed should to be pickable too. [email protected] wrote: > Author: benjamin > Date: Sun Sep 6 22:28:16 2009 > New Revision: 67547 > > Modified: > pypy/trunk/pypy/module/__builtin__/__init__.py > pypy/trunk/pypy/module/__builtin__/app_functional.py > pypy/trunk/pypy/module/__builtin__/functional.py > Log: > reimplement min, max, reduce, sum, filter, map, zip, enumerate, and reversed > on > the interp level for speed > > > Modified: pypy/trunk/pypy/module/__builtin__/__init__.py > ============================================================================== > --- pypy/trunk/pypy/module/__builtin__/__init__.py (original) > +++ pypy/trunk/pypy/module/__builtin__/__init__.py Sun Sep 6 22:28:16 2009 > @@ -27,23 +27,11 @@ > 'raw_input' : 'app_io.raw_input', > 'input' : 'app_io.input', > > - 'sum' : 'app_functional.sum', > 'apply' : 'app_functional.apply', > - 'map' : 'app_functional.map', > - 'filter' : 'app_functional.filter', > - 'zip' : 'app_functional.zip', > - 'reduce' : 'app_functional.reduce', > #'range' : 'app_functional.range', > # redirected to functional.py, applevel version > # is still needed and should stay where it is. > - 'min' : 'app_functional.min', > - 'max' : 'app_functional.max', > - 'enumerate' : 'app_functional.enumerate', > 'sorted' : 'app_functional.sorted', > - 'reversed' : 'app_functional.reversed', > - '_install_pickle_support_for_reversed_iterator': > - 'app_functional._install_pickle_support_for_reversed_iterator', > - > 'globals' : 'app_inspect.globals', > 'locals' : 'app_inspect.locals', > 'vars' : 'app_inspect.vars', > @@ -106,8 +94,17 @@ > > 'range' : 'functional.range_int', > 'xrange' : 'functional.W_XRange', > + 'enumerate' : 'functional.W_Enumerate', > 'all' : 'functional.all', > 'any' : 'functional.any', > + 'min' : 'functional.min', > + 'max' : 'functional.max', > + 'sum' : 'functional.sum', > + 'map' : 'functional.map', > + 'zip' : 'functional.zip', > + 'reduce' : 'functional.reduce', > + 'reversed' : 'functional.reversed', > + 'filter' : 'functional.filter', > 'super' : 'descriptor.W_Super', > 'staticmethod' : 'descriptor.StaticMethod', > 'classmethod' : 'descriptor.ClassMethod', > > Modified: pypy/trunk/pypy/module/__builtin__/app_functional.py > ============================================================================== > --- pypy/trunk/pypy/module/__builtin__/app_functional.py (original) > +++ pypy/trunk/pypy/module/__builtin__/app_functional.py Sun Sep 6 > 22:28:16 2009 > @@ -3,151 +3,12 @@ > functional programming. > """ > > - > -def sum(sequence, total=0): > - """sum(sequence, start=0) -> value > - > -Returns the sum of a sequence of numbers (NOT strings) plus the value > -of parameter 'start'. When the sequence is empty, returns start.""" > - # must forbid "summing" strings, per specs of built-in 'sum' > - if isinstance(total, str): raise TypeError > - for item in sequence: > - total = total + item > - return total > - > # ____________________________________________________________ > > def apply(function, args=(), kwds={}): > """call a function (or other callable object) and return its result""" > return function(*args, **kwds) > > -def map(function, *collections): > - """does 3 separate things, hence this enormous docstring. > - 1. if function is None, return a list of tuples, each with one > - item from each collection. If the collections have different > - lengths, shorter ones are padded with None. > - > - 2. if function is not None, and there is only one collection, > - apply function to every item in the collection and return a > - list of the results. > - > - 3. if function is not None, and there are several collections, > - repeatedly call the function with one argument from each > - collection. If the collections have different lengths, > - shorter ones are padded with None > - """ > - > - if len(collections) == 0: > - raise TypeError, "map() requires at least one sequence" > - > - if len(collections) == 1: > - #it's the most common case, so make it faster > - if function is None: > - return list(collections[0]) > - return [function(x) for x in collections[0]] > - > - iterators = [ iter(collection) for collection in collections ] > - res = [] > - while 1: > - cont = False #is any collection not empty? > - args = [] > - for iterator in iterators: > - try: > - elem = iterator.next() > - cont = True > - except StopIteration: > - elem = None > - args.append(elem) > - if cont: > - if function is None: > - res.append(tuple(args)) > - else: > - res.append(function(*args)) > - else: > - return res > - > -def filterstring(function, collection, str_type): > - if function is None and type(collection) is str_type: > - return collection > - res = [] > - for i in xrange(len(collection)): > - c = collection[i] > - if function is None or function(c): > - if not isinstance(c, str_type): > - raise TypeError("can't filter %s to %s: __getitem__ returned > different type", str_type.__name__, str_type.__name__) > - res.append(c) > - return str_type().join(res) > - > -def filtertuple(function, collection): > - if function is None: > - function = bool > - res = [] > - for i in xrange(len(collection)): > - c = collection[i] > - if function(c): > - res.append(c) > - return tuple(res) > - > -def filter(function, collection): > - """construct a list of those elements of collection for which function > - is True. If function is None, then return the items in the sequence > - which are True.""" > - if isinstance(collection, str): > - return filterstring(function, collection, str) > - elif isinstance(collection, unicode): > - return filterstring(function, collection, unicode) > - elif isinstance(collection, tuple): > - return filtertuple(function, collection) > - > - if function is None: > - return [item for item in collection if item] > - else: > - return [item for item in collection if function(item)] > - > -def zip(*collections): > - """return a list of tuples, where the nth tuple contains every > - nth item of each collection. If the collections have different > - lengths, zip returns a list as long as the shortest collection, > - ignoring the trailing items in the other collections.""" > - > - if len(collections) == 0: > - import sys > - if sys.version_info < (2,4): > - raise TypeError("zip() requires at least one sequence") > - return [] > - res = [] > - iterators = [ iter(collection) for collection in collections ] > - while 1: > - try: > - elems = [] > - for iterator in iterators: > - elems.append(iterator.next()) > - res.append(tuple(elems)) > - except StopIteration: > - return res > - > -def reduce(function, seq, *initialt): > - """ Apply function of two arguments cumulatively to the items of > - sequence, from left to right, so as to reduce the sequence to a > - single value. Optionally begin with an initial value.""" > - > - seqiter = iter(seq) > - if initialt: > - initial, = initialt > - else: > - try: > - initial = seqiter.next() > - except StopIteration: > - raise TypeError, "reduce() of empty sequence with no initial value" > - while 1: > - try: > - arg = seqiter.next() > - except StopIteration: > - break > - initial = function(initial, arg) > - > - return initial > - > # ____________________________________________________________ > > """ > @@ -206,135 +67,10 @@ > > # ____________________________________________________________ > > - > -def _identity(arg): > - return arg > - > - > -def min(*arr, **kwargs): > - """return the smallest number in a list, > - or its smallest argument if more than one is given.""" > - from operator import gt > - > - return min_max(gt, "min", *arr, **kwargs) > - > -def min_max(comp, funcname, *arr, **kwargs): > - key = kwargs.pop("key", _identity) > - if len(kwargs): > - raise TypeError, '%s() got an unexpected keyword argument' % funcname > - > - if not arr: > - raise TypeError, '%s() takes at least one argument' % funcname > - > - if len(arr) == 1: > - arr = arr[0] > - > - iterator = iter(arr) > - try: > - min_max_val = iterator.next() > - except StopIteration: > - raise ValueError, '%s() arg is an empty sequence' % funcname > - > - keyed_min_max_val = key(min_max_val) > - > - for i in iterator: > - keyed = key(i) > - if comp(keyed_min_max_val, keyed): > - min_max_val = i > - keyed_min_max_val = keyed > - return min_max_val > - > -def max(*arr, **kwargs): > - """return the largest number in a list, > - or its largest argument if more than one is given.""" > - from operator import lt > - > - return min_max(lt, "max", *arr, **kwargs) > - > -class enumerate(object): > - """enumerate(iterable) -> iterator for (index, value) of iterable. > - > -Return an enumerate object. iterable must be an other object that supports > -iteration. The enumerate object yields pairs containing a count (from > -zero) and a value yielded by the iterable argument. enumerate is useful > -for obtaining an indexed list: (0, seq[0]), (1, seq[1]), (2, seq[2]), ...""" > - > - def __init__(self, collection): > - self._iter = iter(collection) > - self._index = 0 > - > - def next(self): > - try: > - next = self._iter.next > - except AttributeError: > - # CPython raises a TypeError when next() is not defined > - raise TypeError('%s object has no next() method' % > - (type(self._iter).__name__,)) > - result = self._index, next() > - self._index += 1 > - return result > - > - def __iter__(self): > - return self > - > - > -# ____________________________________________________________ > - > def sorted(lst, cmp=None, key=None, reverse=None): > "sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list" > sorted_lst = list(lst) > sorted_lst.sort(cmp, key, reverse) > return sorted_lst > > -def reversed(sequence): > - "reversed(sequence) -> reverse iterator over values of the sequence" > - if hasattr(sequence, '__reversed__'): > - return sequence.__reversed__() > - if not hasattr(sequence, '__getitem__'): > - raise TypeError("argument to reversed() must be a sequence") > - return reversed_iterator(sequence) > - > - > -class reversed_iterator(object): > - > - def __init__(self, seq): > - self.seq = seq > - self.remaining = len(seq) > - > - def __iter__(self): > - return self > - > - def next(self): > - if self.remaining > len(self.seq): > - self.remaining = 0 > - i = self.remaining > - if i > 0: > - i -= 1 > - item = self.seq[i] > - self.remaining = i > - return item > - raise StopIteration > - > -# XXX __length_hint__() > -## def __len__(self): > -## if self.remaining > len(self.seq): > -## self.remaining = 0 > -## return self.remaining > - > - def __reduce__(self): > - tup = (self.seq, self.remaining) > - return (make_reversed_iterator, tup) > - > -def make_reversed_iterator(seq, remaining): > - ri = reversed_iterator.__new__(reversed_iterator) > - ri.seq = seq > - #or "ri = reversed_iterator(seq)" but that executes len(seq) > - ri.remaining = remaining > - return ri > - > -def _install_pickle_support_for_reversed_iterator(): > - import _pickle_support > - make_reversed_iterator.__module__ = '_pickle_support' > - _pickle_support.make_reversed_iterator = make_reversed_iterator > - > > > Modified: pypy/trunk/pypy/module/__builtin__/functional.py > ============================================================================== > --- pypy/trunk/pypy/module/__builtin__/functional.py (original) > +++ pypy/trunk/pypy/module/__builtin__/functional.py Sun Sep 6 22:28:16 2009 > @@ -8,7 +8,9 @@ > from pypy.interpreter.gateway import interp2app > from pypy.interpreter.typedef import TypeDef > from pypy.interpreter.baseobjspace import Wrappable > +from pypy.interpreter.argument import Arguments > from pypy.rlib.rarithmetic import r_uint, intmask > +from pypy.rlib.objectmodel import specialize > from pypy.module.__builtin__.app_functional import range as app_range > from inspect import getsource, getfile > > @@ -100,7 +102,244 @@ > return W_ListMultiObject(space, impl) > > > [email protected](2) > +def min_max(space, arguments, implementation_of): > + if implementation_of == "max": > + compare = space.gt > + else: > + compare = space.lt > + args, kwargs = arguments.unpack() > + if len(args) > 1: > + w_sequence = space.newtuple(args) > + elif len(args): > + w_sequence = args[0] > + else: > + msg = "%s() expects at least one argument" % (implementation_of,) > + raise OperationError(space.w_TypeError, space.wrap(msg)) > + try: > + w_key = kwargs["key"] > + except KeyError: > + w_key = None > + else: > + del kwargs["key"] > + if kwargs: > + msg = "%s() got unexpected keyword argument" % (implementation_of,) > + raise OperationError(space.w_TypeError, space.wrap(msg)) > + w_iter = space.iter(w_sequence) > + w_max_item = None > + w_max_val = None > + while True: > + try: > + w_item = space.next(w_iter) > + except OperationError, e: > + if not e.match(space, space.w_StopIteration): > + raise > + break > + if w_key is not None: > + w_compare_with = space.call_function(w_key, w_item) > + else: > + w_compare_with = w_item > + if w_max_item is None or \ > + space.is_true(compare(w_compare_with, w_max_val)): > + w_max_item = w_item > + w_max_val = w_compare_with > + if w_max_item is None: > + msg = "arg is an empty sequence" > + raise OperationError(space.w_ValueError, space.wrap(msg)) > + return w_max_item > > +def max(space, __args__): > + """Return the largest item in a sequence. > + > + If more than one argument is passed, return the maximum of them. > + """ > + return min_max(space, __args__, "max") > +max.unwrap_spec = [ObjSpace, Arguments] > + > +def min(space, __args__): > + """Return the smallest item in a sequence. > + > + If more than one argument is passed, return the minimum of them. > + """ > + return min_max(space, __args__, "min") > +min.unwrap_spec = [ObjSpace, Arguments] > + > +def map(space, w_func, collections_w): > + """does 3 separate things, hence this enormous docstring. > + 1. if function is None, return a list of tuples, each with one > + item from each collection. If the collections have different > + lengths, shorter ones are padded with None. > + > + 2. if function is not None, and there is only one collection, > + apply function to every item in the collection and return a > + list of the results. > + > + 3. if function is not None, and there are several collections, > + repeatedly call the function with one argument from each > + collection. If the collections have different lengths, > + shorter ones are padded with None > + """ > + if not collections_w: > + msg = "map() requires at least two arguments" > + raise OperationError(space.w_TypeError, space.wrap(msg)) > + num_collections = len(collections_w) > + none_func = space.is_w(w_func, space.w_None) > + if none_func and num_collections == 1: > + return space.call_function(space.w_list, collections_w[0]) > + result_w = [] > + iterators_w = [space.iter(w_seq) for w_seq in collections_w] > + num_iterators = len(iterators_w) > + while True: > + cont = False > + args_w = [space.w_None] * num_iterators > + for i in range(len(iterators_w)): > + try: > + args_w[i] = space.next(iterators_w[i]) > + except OperationError, e: > + if not e.match(space, space.w_StopIteration): > + raise > + else: > + cont = True > + w_args = space.newtuple(args_w) > + if cont: > + if none_func: > + result_w.append(w_args) > + else: > + w_res = space.call(w_func, w_args) > + result_w.append(w_res) > + else: > + return space.newlist(result_w) > +map.unwrap_spec = [ObjSpace, W_Root, "args_w"] > + > +def sum(space, w_sequence, w_start=None): > + if space.is_w(w_start, space.w_None): > + w_start = space.wrap(0) > + elif space.is_true(space.isinstance(w_start, space.w_basestring)): > + msg = "sum() can't sum strings" > + raise OperationError(space.w_TypeError, space.wrap(msg)) > + w_iter = space.iter(w_sequence) > + w_last = w_start > + while True: > + try: > + w_next = space.next(w_iter) > + except OperationError, e: > + if not e.match(space, space.w_StopIteration): > + raise > + break > + w_last = space.add(w_last, w_next) > + return w_last > +sum.unwrap_spec = [ObjSpace, W_Root, W_Root] > + > +def zip(space, sequences_w): > + """Return a list of tuples, where the nth tuple contains every nth item > of > + each collection. > + > + If the collections have different lengths, zip returns a list as long as > the > + shortest collection, ignoring the trailing items in the other > collections. > + """ > + if not sequences_w: > + return space.newlist([]) > + result_w = [] > + iterators_w = [space.iter(w_seq) for w_seq in sequences_w] > + while True: > + try: > + items_w = [space.next(w_it) for w_it in iterators_w] > + except OperationError, e: > + if not e.match(space, space.w_StopIteration): > + raise > + return space.newlist(result_w) > + result_w.append(space.newtuple(items_w)) > +zip.unwrap_spec = [ObjSpace, "args_w"] > + > +def reduce(space, w_func, w_sequence, rest_w): > + """ Apply function of two arguments cumulatively to the items of > sequence, > + from left to right, so as to reduce the sequence to a single value. > + Optionally begin with an initial value. > + """ > + w_iter = space.iter(w_sequence) > + if rest_w: > + if len(rest_w) > 1: > + msg = "reduce() takes only 3 possible arguments" > + raise OperationError(space.w_TypeError, space.wrap(msg)) > + w_initial, = rest_w > + else: > + try: > + w_initial = space.next(w_iter) > + except OperationError, e: > + if e.match(space, space.w_StopIteration): > + msg = "reduce() of empty sequence with no initial value" > + raise OperationError(space.w_TypeError, space.wrap(msg)) > + raise > + w_result = w_initial > + while True: > + try: > + w_next = space.next(w_iter) > + except OperationError, e: > + if not e.match(space, space.w_StopIteration): > + raise > + break > + w_result = space.call_function(w_func, w_result, w_next) > + return w_result > +reduce.unwrap_spec = [ObjSpace, W_Root, W_Root, "args_w"] > + > +def filter(space, w_func, w_seq): > + """construct a list of those elements of collection for which function > + is True. If function is None, then return the items in the sequence > + which are True. > + """ > + if space.is_true(space.isinstance(w_seq, space.w_str)): > + return _filter_string(space, w_func, w_seq, space.w_str) > + if space.is_true(space.isinstance(w_seq, space.w_unicode)): > + return _filter_string(space, w_func, w_seq, space.w_unicode) > + if space.is_true(space.isinstance(w_seq, space.w_tuple)): > + return _filter_tuple(space, w_func, w_seq) > + w_iter = space.iter(w_seq) > + result_w = [] > + none_func = space.is_w(w_func, space.w_None) > + while True: > + try: > + w_next = space.next(w_iter) > + except OperationError, e: > + if not e.match(space, space.w_StopIteration): > + raise > + break > + if none_func: > + w_keep = w_next > + else: > + w_keep = space.call_function(w_func, w_next) > + if space.is_true(w_keep): > + result_w.append(w_next) > + return space.newlist(result_w) > + > +def _filter_tuple(space, w_func, w_tuple): > + none_func = space.is_w(w_func, space.w_None) > + length = space.int_w(space.len(w_tuple)) > + result_w = [] > + for i in range(length): > + w_item = space.getitem(w_tuple, space.wrap(i)) > + if none_func: > + w_keep = w_item > + else: > + w_keep = space.call_function(w_func, w_item) > + if space.is_true(w_keep): > + result_w.append(w_item) > + return space.newtuple(result_w) > + > +def _filter_string(space, w_func, w_string, w_str_type): > + none_func = space.is_w(w_func, space.w_None) > + if none_func and space.is_w(space.type(w_string), w_str_type): > + return w_string > + length = space.int_w(space.len(w_string)) > + result_w = [] > + for i in range(length): > + w_item = space.getitem(w_string, space.wrap(i)) > + if none_func or space.is_true(space.call_function(w_func, w_item)): > + if not space.is_true(space.isinstance(w_item, w_str_type)): > + msg = "__getitem__ returned a non-string type" > + raise OperationError(space.w_TypeError, space.wrap(msg)) > + result_w.append(w_item) > + w_empty = space.call_function(w_str_type) > + return space.call_method(w_empty, "join", space.newlist(result_w)) > > def all(space, w_S): > """all(iterable) -> bool > @@ -138,6 +377,77 @@ > any.unwrap_spec = [ObjSpace, W_Root] > > > +class W_Enumerate(Wrappable): > + > + def __init__(self, w_iter, w_start): > + self.w_iter = w_iter > + self.w_index = w_start > + > + def descr___new__(space, w_subtype, w_iterable): > + self = space.allocate_instance(W_Enumerate, w_subtype) > + self.__init__(space.iter(w_iterable), space.wrap(0)) > + return space.wrap(self) > + > + def descr___iter__(self, space): > + return space.wrap(self) > + descr___iter__.unwrap_spec = ["self", ObjSpace] > + > + def descr_next(self, space): > + w_item = space.next(self.w_iter) > + w_index = self.w_index > + self.w_index = space.add(w_index, space.wrap(1)) > + return space.newtuple([w_index, w_item]) > + descr_next.unwrap_spec = ["self", ObjSpace] > + > + > +W_Enumerate.typedef = TypeDef("enumerate", > + __new__=interp2app(W_Enumerate.descr___new__.im_func), > + __iter__=interp2app(W_Enumerate.descr___iter__), > + next=interp2app(W_Enumerate.descr_next), > +) > + > + > +def reversed(space, w_sequence): > + """Return a iterator that yields items of sequence in reverse.""" > + w_reversed_descr = space.lookup(w_sequence, "__reversed__") > + if w_reversed_descr is None: > + return space.wrap(W_ReversedIterator(space, w_sequence)) > + return space.get_and_call_function(w_reversed_descr, w_sequence) > +reversed.unwrap_spec = [ObjSpace, W_Root] > + > +class W_ReversedIterator(Wrappable): > + > + def __init__(self, space, w_sequence): > + self.remaining = space.int_w(space.len(w_sequence)) - 1 > + self.w_sequence = w_sequence > + > + def descr___iter__(self, space): > + return space.wrap(self) > + descr___iter__.unwrap_spec = ["self", ObjSpace] > + > + def descr_next(self, space): > + if self.remaining >= 0: > + w_index = space.wrap(self.remaining) > + try: > + w_item = space.getitem(self.w_sequence, w_index) > + except OperationError, e: > + if not e.match(space, space.w_StopIteration): > + raise > + else: > + self.remaining -= 1 > + return w_item > + > + # Done > + self.remaining = -1 > + raise OperationError(space.w_StopIteration, space.w_None) > + descr_next.unwrap_spec = ["self", ObjSpace] > + > +W_ReversedIterator.typedef = TypeDef("reversed", > + __iter__=interp2app(W_ReversedIterator.descr___iter__), > + next=interp2app(W_ReversedIterator.descr_next), > +) > + > + > class W_XRange(Wrappable): > def __init__(self, space, start, len, step): > self.space = space > _______________________________________________ > pypy-svn mailing list > [email protected] > http://codespeak.net/mailman/listinfo/pypy-svn > _______________________________________________ [email protected] http://codespeak.net/mailman/listinfo/pypy-dev
