""" Compiler-side implementation of the Numba typed-list. """ import ctypes import operator from enum import IntEnum from llvmlite import ir from numba import cgutils from numba import _helperlib from numba.extending import ( overload, overload_method, register_jitable, intrinsic, register_model, models, lower_builtin, ) from numba.targets.imputils import iternext_impl from numba import types from numba.types import ( ListType, ListTypeIterableType, ListTypeIteratorType, Type, ) from numba.targets.imputils import impl_ret_borrowed, RefType from numba.errors import TypingError from numba import typing from numba.typedobjectutils import (_as_bytes, _cast, _nonoptional, _get_incref_decref, _container_get_data, _container_get_meminfo, ) from numba.targets import listobj ll_list_type = cgutils.voidptr_t ll_listiter_type = cgutils.voidptr_t ll_voidptr_type = cgutils.voidptr_t ll_status = cgutils.int32_t ll_ssize_t = cgutils.intp_t ll_bytes = cgutils.voidptr_t _meminfo_listptr = types.MemInfoPointer(types.voidptr) INDEXTY = types.intp index_types = types.integer_domain @register_model(ListType) class ListModel(models.StructModel): def __init__(self, dmm, fe_type): members = [ ('meminfo', _meminfo_listptr), ('data', types.voidptr), # ptr to the C list ] super(ListModel, self).__init__(dmm, fe_type, members) @register_model(ListTypeIterableType) @register_model(ListTypeIteratorType) class ListIterModel(models.StructModel): def __init__(self, dmm, fe_type): members = [ ('parent', fe_type.parent), # reference to the list ('state', types.voidptr), # iterator state in C code ] super(ListIterModel, self).__init__(dmm, fe_type, members) class ListStatus(IntEnum): """Status code for other list operations. """ LIST_OK = 0, LIST_ERR_INDEX = -1 LIST_ERR_NO_MEMORY = -2 LIST_ERR_MUTATED = -3 LIST_ERR_ITER_EXHAUSTED = -4 def _raise_if_error(context, builder, status, msg): """Raise an internal error depending on the value of *status* """ ok_status = status.type(int(ListStatus.LIST_OK)) with builder.if_then(builder.icmp_signed('!=', status, ok_status), likely=True): context.call_conv.return_user_exc(builder, RuntimeError, (msg,)) @intrinsic def _as_meminfo(typingctx, lstobj): """Returns the MemInfoPointer of a list. """ if not isinstance(lstobj, types.ListType): raise TypingError('expected *lstobj* to be a ListType') def codegen(context, builder, sig, args): [tl] = sig.args [l] = args # Incref context.nrt.incref(builder, tl, l) ctor = cgutils.create_struct_proxy(tl) lstruct = ctor(context, builder, value=l) # Returns the plain MemInfo return lstruct.meminfo sig = _meminfo_listptr(lstobj) return sig, codegen @intrinsic def _from_meminfo(typingctx, mi, listtyperef): """Recreate a list from a MemInfoPointer """ if mi != _meminfo_listptr: raise TypingError('expected a MemInfoPointer for list.') listtype = listtyperef.instance_type if not isinstance(listtype, ListType): raise TypingError('expected a {}'.format(ListType)) def codegen(context, builder, sig, args): [tmi, tdref] = sig.args td = tdref.instance_type [mi, _] = args ctor = cgutils.create_struct_proxy(td) dstruct = ctor(context, builder) data_pointer = context.nrt.meminfo_data(builder, mi) data_pointer = builder.bitcast(data_pointer, ll_list_type.as_pointer()) dstruct.data = builder.load(data_pointer) dstruct.meminfo = mi return impl_ret_borrowed( context, builder, listtype, dstruct._getvalue(), ) sig = listtype(mi, listtyperef) return sig, codegen @intrinsic def _list_set_method_table(typingctx, lp, itemty): """Wrap numba_list_set_method_table """ resty = types.void sig = resty(lp, itemty) def codegen(context, builder, sig, args): vtablety = ir.LiteralStructType([ ll_voidptr_type, # item incref ll_voidptr_type, # item decref ]) setmethod_fnty = ir.FunctionType( ir.VoidType(), [ll_list_type, vtablety.as_pointer()] ) setmethod_fn = ir.Function( builder.module, setmethod_fnty, name='numba_list_set_method_table', ) dp = args[0] vtable = cgutils.alloca_once(builder, vtablety, zfill=True) # install item incref/decref item_incref_ptr = cgutils.gep_inbounds(builder, vtable, 0, 0) item_decref_ptr = cgutils.gep_inbounds(builder, vtable, 0, 1) dm_item = context.data_model_manager[itemty.instance_type] if dm_item.contains_nrt_meminfo(): item_incref, item_decref = _get_incref_decref( context, builder.module, dm_item, "list" ) builder.store( builder.bitcast(item_incref, item_incref_ptr.type.pointee), item_incref_ptr, ) builder.store( builder.bitcast(item_decref, item_decref_ptr.type.pointee), item_decref_ptr, ) builder.call(setmethod_fn, [dp, vtable]) return sig, codegen @lower_builtin(operator.is_, types.ListType, types.ListType) def list_is(context, builder, sig, args): a_meminfo = _container_get_meminfo(context, builder, sig.args[0], args[0]) b_meminfo = _container_get_meminfo(context, builder, sig.args[1], args[1]) ma = builder.ptrtoint(a_meminfo, cgutils.intp_t) mb = builder.ptrtoint(b_meminfo, cgutils.intp_t) return builder.icmp_signed('==', ma, mb) def _call_list_free(context, builder, ptr): """Call numba_list_free(ptr) """ fnty = ir.FunctionType( ir.VoidType(), [ll_list_type], ) free = builder.module.get_or_insert_function(fnty, name='numba_list_free') builder.call(free, [ptr]) # FIXME: this needs a careful review def _imp_dtor(context, module): """Define the dtor for list """ llvoidptr = context.get_value_type(types.voidptr) llsize = context.get_value_type(types.uintp) fnty = ir.FunctionType( ir.VoidType(), [llvoidptr, llsize, llvoidptr], ) fname = '_numba_list_dtor' fn = module.get_or_insert_function(fnty, name=fname) if fn.is_declaration: # Set linkage fn.linkage = 'linkonce_odr' # Define builder = ir.IRBuilder(fn.append_basic_block()) lp = builder.bitcast(fn.args[0], ll_list_type.as_pointer()) l = builder.load(lp) _call_list_free(context, builder, l) builder.ret_void() return fn def new_list(item, allocated=0): """Construct a new list. (Not implemented in the interpreter yet) Parameters ---------- item: TypeRef Item type of the new list. allocated: int number of items to pre-allocate """ # With JIT disabled, ignore all arguments and return a Python list. return list() @intrinsic def _make_list(typingctx, itemty, ptr): """Make a list struct with the given *ptr* Parameters ---------- itemty: Type Type of the item. ptr : llvm pointer value Points to the list object. """ list_ty = types.ListType(itemty.instance_type) def codegen(context, builder, signature, args): [_, ptr] = args ctor = cgutils.create_struct_proxy(list_ty) lstruct = ctor(context, builder) lstruct.data = ptr alloc_size = context.get_abi_sizeof( context.get_value_type(types.voidptr), ) dtor = _imp_dtor(context, builder.module) meminfo = context.nrt.meminfo_alloc_dtor( builder, context.get_constant(types.uintp, alloc_size), dtor, ) data_pointer = context.nrt.meminfo_data(builder, meminfo) data_pointer = builder.bitcast(data_pointer, ll_list_type.as_pointer()) builder.store(ptr, data_pointer) lstruct.meminfo = meminfo return lstruct._getvalue() sig = list_ty(itemty, ptr) return sig, codegen @intrinsic def _list_new(typingctx, itemty, allocated): """Wrap numba_list_new. Allocate a new list object with zero capacity. Parameters ---------- itemty: Type Type of the items allocated: int number of items to pre-allocate """ resty = types.voidptr sig = resty(itemty, allocated) def codegen(context, builder, sig, args): fnty = ir.FunctionType( ll_status, [ll_list_type.as_pointer(), ll_ssize_t, ll_ssize_t], ) fn = builder.module.get_or_insert_function(fnty, name='numba_list_new') # Determine sizeof item types ll_item = context.get_data_type(itemty.instance_type) sz_item = context.get_abi_sizeof(ll_item) reflp = cgutils.alloca_once(builder, ll_list_type, zfill=True) status = builder.call( fn, [reflp, ll_ssize_t(sz_item), args[1]], ) _raise_if_error( context, builder, status, msg="Failed to allocate list", ) lp = builder.load(reflp) return lp return sig, codegen @overload(new_list) def impl_new_list(item, allocated=0): """Creates a new list. Parameters ---------- item: Numba type type of the list item. allocated: int number of items to pre-allocate """ if not isinstance(item, Type): raise TypeError("expecting *item* to be a numba Type") itemty = item def imp(item, allocated=0): if allocated < 0: raise RuntimeError("expecting *allocated* to be >= 0") lp = _list_new(itemty, allocated) _list_set_method_table(lp, itemty) l = _make_list(itemty, lp) return l return imp @overload(len) def impl_len(l): """len(list) """ if isinstance(l, types.ListType): def impl(l): return _list_length(l) return impl @intrinsic def _list_length(typingctx, l): """Wrap numba_list_length Returns the length of the list. """ resty = types.intp sig = resty(l) def codegen(context, builder, sig, args): fnty = ir.FunctionType( ll_ssize_t, [ll_list_type], ) fn = builder.module.get_or_insert_function(fnty, name='numba_list_length') [l] = args [tl] = sig.args lp = _container_get_data(context, builder, tl, l) n = builder.call(fn, [lp]) return n return sig, codegen @overload_method(types.ListType, "_allocated") def impl_allocated(l): """list._allocated() """ if isinstance(l, types.ListType): def impl(l): return _list_allocated(l) return impl @intrinsic def _list_allocated(typingctx, l): """Wrap numba_list_allocated Returns the allocation of the list. """ resty = types.intp sig = resty(l) def codegen(context, builder, sig, args): fnty = ir.FunctionType( ll_ssize_t, [ll_list_type], ) fn = builder.module.get_or_insert_function(fnty, name='numba_list_allocated') [l] = args [tl] = sig.args lp = _container_get_data(context, builder, tl, l) n = builder.call(fn, [lp]) return n return sig, codegen @intrinsic def _list_append(typingctx, l, item): """Wrap numba_list_append """ resty = types.int32 sig = resty(l, l.item_type) def codegen(context, builder, sig, args): fnty = ir.FunctionType( ll_status, [ll_list_type, ll_bytes], ) [l, item] = args [tl, titem] = sig.args fn = builder.module.get_or_insert_function(fnty, name='numba_list_append') dm_item = context.data_model_manager[titem] data_item = dm_item.as_data(builder, item) ptr_item = cgutils.alloca_once_value(builder, data_item) lp = _container_get_data(context, builder, tl, l) status = builder.call( fn, [ lp, _as_bytes(builder, ptr_item), ], ) return status return sig, codegen @overload_method(types.ListType, 'append') def impl_append(l, item): if not isinstance(l, types.ListType): return itemty = l.item_type def impl(l, item): casteditem = _cast(item, itemty) status = _list_append(l, casteditem) if status == ListStatus.LIST_OK: return elif status == ListStatus.LIST_ERR_NO_MEMORY: raise MemoryError('Unable to allocate memory to append item') else: raise RuntimeError('list.append failed unexpectedly') if l.is_precise(): # Handle the precise case. return impl else: # Handle the imprecise case. l = l.refine(item) # Re-bind the item type to match the arguments. itemty = l.item_type # Create the signature that we wanted this impl to have. sig = typing.signature(types.void, l, itemty) return sig, impl @register_jitable def handle_index(l, index): """Handle index. If the index is negative, convert it. If the index is out of range, raise an IndexError. """ # convert negative indices to positive ones if index < 0: # len(l) has always type 'int64' # while index can be an signed/unsigned integer index = type(index)(len(l) + index) # check that the index is in range if not (0 <= index < len(l)): raise IndexError("list index out of range") return index @register_jitable def handle_slice(l, s): """Handle slice. Convert a slice object for a given list into a range object that can be used to index the list. Many subtle caveats here, especially if the step is negative. """ if len(l) == 0: # ignore slice for empty list return range(0) ll, sa, so, se = len(l), s.start, s.stop, s.step if se > 0: start = max(ll + sa, 0) if s.start < 0 else min(ll, sa) stop = max(ll + so, 0) if so < 0 else min(ll, so) elif se < 0: start = max(ll + sa, -1) if s.start < 0 else min(ll - 1, sa) stop = max(ll + so, -1) if so < 0 else min(ll, so) else: # should be caught earlier, but isn't, so we raise here raise ValueError("slice step cannot be zero") return range(start, stop, s.step) @intrinsic def _list_getitem(typingctx, l, index): return _list_getitem_pop_helper(typingctx, l, index, 'getitem') @intrinsic def _list_pop(typingctx, l, index): return _list_getitem_pop_helper(typingctx, l, index, 'pop') def _list_getitem_pop_helper(typingctx, l, index, op): """Wrap numba_list_getitem and numba_list_pop Returns 2-tuple of (intp, ?item_type) This is a helper that is parametrized on the type of operation, which can be either 'pop' or 'getitem'. This is because, signature wise, getitem and pop and are the same. """ assert(op in ("pop", "getitem")) resty = types.Tuple([types.int32, types.Optional(l.item_type)]) sig = resty(l, index) def codegen(context, builder, sig, args): fnty = ir.FunctionType( ll_status, [ll_list_type, ll_ssize_t, ll_bytes], ) [tl, tindex] = sig.args [l, index] = args fn = builder.module.get_or_insert_function( fnty, name='numba_list_{}'.format(op)) dm_item = context.data_model_manager[tl.item_type] ll_item = context.get_data_type(tl.item_type) ptr_item = cgutils.alloca_once(builder, ll_item) lp = _container_get_data(context, builder, tl, l) status = builder.call( fn, [ lp, index, _as_bytes(builder, ptr_item), ], ) # Load item if output is available found = builder.icmp_signed('>=', status, status.type(int(ListStatus.LIST_OK))) out = context.make_optional_none(builder, tl.item_type) pout = cgutils.alloca_once_value(builder, out) with builder.if_then(found): item = dm_item.load_from_data_pointer(builder, ptr_item) context.nrt.incref(builder, tl.item_type, item) loaded = context.make_optional_value(builder, tl.item_type, item) builder.store(loaded, pout) out = builder.load(pout) return context.make_tuple(builder, resty, [status, out]) return sig, codegen @overload(operator.getitem) def impl_getitem(l, index): if not isinstance(l, types.ListType): return indexty = INDEXTY itemty = l.item_type if index in index_types: def integer_impl(l, index): index = handle_index(l, index) castedindex = _cast(index, indexty) status, item = _list_getitem(l, castedindex) if status == ListStatus.LIST_OK: return _nonoptional(item) else: raise AssertionError("internal list error during getitem") return integer_impl elif isinstance(index, types.SliceType): def slice_impl(l, index): newl = new_list(itemty) for i in handle_slice(l, index): newl.append(l[i]) return newl return slice_impl else: raise TypingError("list indices must be integers or slices") @intrinsic def _list_setitem(typingctx, l, index, item): """Wrap numba_list_setitem """ resty = types.int32 sig = resty(l, index, item) def codegen(context, builder, sig, args): fnty = ir.FunctionType( ll_status, [ll_list_type, ll_ssize_t, ll_bytes], ) [l, index, item] = args [tl, tindex, titem] = sig.args fn = builder.module.get_or_insert_function(fnty, name='numba_list_setitem') dm_item = context.data_model_manager[titem] data_item = dm_item.as_data(builder, item) ptr_item = cgutils.alloca_once_value(builder, data_item) lp = _container_get_data(context, builder, tl, l) status = builder.call( fn, [ lp, index, _as_bytes(builder, ptr_item), ], ) return status return sig, codegen @overload(operator.setitem) def impl_setitem(l, index, item): if not isinstance(l, types.ListType): return indexty = INDEXTY itemty = l.item_type if index in index_types: def impl_integer(l, index, item): index = handle_index(l, index) castedindex = _cast(index, indexty) casteditem = _cast(item, itemty) status = _list_setitem(l, castedindex, casteditem) if status == ListStatus.LIST_OK: return else: raise AssertionError("internal list error during settitem") return impl_integer elif isinstance(index, types.SliceType): if not isinstance(item, types.IterableType): raise TypingError("can only assign an iterable when using a slice " "with assignment/setitem") def impl_slice(l, index, item): # special case "a[i:j] = a", need to copy first if l is item: item = item.copy() slice_range = handle_slice(l, index) # non-extended (simple) slices if slice_range.step == 1: # replace if len(item) == len(slice_range): for i, j in zip(slice_range, item): l[i] = j # replace and insert if len(item) > len(slice_range): # do the replaces we can for i, j in zip(slice_range, item[:len(slice_range)]): l[i] = j # insert the remaining ones insert_range = range(slice_range.stop, slice_range.stop + len(item) - len(slice_range)) for i, k in zip(insert_range, item[len(slice_range):]): # FIXME: This may be slow. Each insert can incur a # memory copy of one or more items. l.insert(i, k) # replace and delete if len(item) < len(slice_range): # do the replaces we can replace_range = range(slice_range.start, slice_range.start + len(item)) for i,j in zip(replace_range, item): l[i] = j # delete remaining ones del l[slice_range.start + len(item):slice_range.stop] # Extended slices else: if len(slice_range) != len(item): raise ValueError("length mismatch for extended slice " "and sequence") # extended slice can only replace for i, j in zip(slice_range, item): l[i] = j return impl_slice else: raise TypingError("list indices must be integers or slices") @overload_method(types.ListType, 'pop') def impl_pop(l, index=-1): if not isinstance(l, types.ListType): return indexty = INDEXTY # FIXME: this type check works, but it isn't clear why and if it optimal if (isinstance(index, int) or index in index_types or isinstance(index, types.Omitted)): def impl(l, index=-1): if len(l) == 0: raise IndexError("pop from empty list") index = handle_index(l, index) castedindex = _cast(index, indexty) status, item = _list_pop(l, castedindex) if status == ListStatus.LIST_OK: return _nonoptional(item) else: raise AssertionError("internal list error during pop") return impl else: raise TypingError("argument for pop must be an integer") @intrinsic def _list_delete_slice(typingctx, l, start, stop, step): """Wrap numba_list_delete_slice """ resty = types.int32 sig = resty(l, start, stop, step) def codegen(context, builder, sig, args): fnty = ir.FunctionType( ll_status, [ll_list_type, ll_ssize_t, ll_ssize_t, ll_ssize_t], ) [l, start, stop, step] = args [tl, tstart, tstop, tstep] = sig.args fn = builder.module.get_or_insert_function( fnty, name='numba_list_delete_slice') lp = _container_get_data(context, builder, tl, l) status = builder.call( fn, [ lp, start, stop, step, ], ) return status return sig, codegen @overload(operator.delitem) def impl_delitem(l, index): if not isinstance(l, types.ListType): return if index in index_types: def integer_impl(l, index): l.pop(index) return integer_impl elif isinstance(index, types.SliceType): def slice_impl(l, index): slice_range = handle_slice(l, index) _list_delete_slice(l, slice_range.start, slice_range.stop, slice_range.step) return slice_impl else: raise TypingError("list indices must be integers or slices") @overload(operator.contains) def impl_contains(l, item): if not isinstance(l, types.ListType): return itemty = l.item_type def impl(l, item): casteditem = _cast(item, itemty) for i in l: if i == casteditem: return True else: return False return impl @overload_method(types.ListType, 'count') def impl_count(l, item): if not isinstance(l, types.ListType): return itemty = l.item_type def impl(l, item): casteditem = _cast(item, itemty) total = 0 for i in l: if i == casteditem: total += 1 return total return impl @overload_method(types.ListType, 'extend') def impl_extend(l, iterable): if not isinstance(l, types.ListType): return if not isinstance(iterable, types.IterableType): raise TypingError("extend argument must be iterable") def select_impl(): if isinstance(iterable, types.ListType): def impl(l, iterable): # guard against l.extend(l) if l is iterable: iterable = iterable.copy() for i in iterable: l.append(i) return impl else: def impl(l, iterable): for i in iterable: l.append(i) return impl if l.is_precise(): # Handle the precise case. return select_impl() else: # Handle the imprecise case, try to 'guess' the underlying type of the # values in the iterable. if hasattr(iterable, "dtype"): # tuples and arrays ty = iterable.dtype elif hasattr(iterable, "item_type"): # lists ty = iterable.item_type elif hasattr(iterable, "yield_type"): # iterators and generators ty = iterable.yield_type else: raise TypingError("unable to extend list, iterable is missing " "either *dtype*, *item_type* or *yield_type*.") l = l.refine(ty) # Create the signature that we wanted this impl to have sig = typing.signature(types.void, l, iterable) return sig, select_impl() @overload_method(types.ListType, 'insert') def impl_insert(l, index, item): if not isinstance(l, types.ListType): return if index in index_types: def impl(l, index, item): # If the index is larger than the size of the list or if the list is # empty, just append. if index >= len(l) or len(l) == 0: l.append(item) # Else, do the insert dance else: # convert negative indices if index < 0: # if the index is still negative after conversion, use 0 index = max(len(l) + index, 0) # grow the list by one, make room for item to insert l.append(l[0]) # reverse iterate over the list and shift all elements i = len(l) - 1 while(i > index): l[i] = l[i - 1] i -= 1 # finally, insert the item l[index] = item if l.is_precise(): # Handle the precise case. return impl else: # Handle the imprecise case l = l.refine(item) # Re-bind the item type to match the arguments. itemty = l.item_type # Create the signature that we wanted this impl to have. sig = typing.signature(types.void, l, INDEXTY, itemty) return sig, impl else: raise TypingError("list insert indices must be integers") @overload_method(types.ListType, 'remove') def impl_remove(l, item): if not isinstance(l, types.ListType): return itemty = l.item_type def impl(l, item): casteditem = _cast(item, itemty) for i, n in enumerate(l): if casteditem == n: l.pop(i) return else: raise ValueError("list.remove(x): x not in list") return impl @overload_method(types.ListType, 'clear') def impl_clear(l): if not isinstance(l, types.ListType): return def impl(l): while len(l): l.pop() return impl @overload_method(types.ListType, 'reverse') def impl_reverse(l): if not isinstance(l, types.ListType): return def impl(l): front = 0 back = len(l) - 1 while front < back: l[front], l[back] = l[back], l[front] front += 1 back -= 1 return impl @overload_method(types.ListType, 'copy') def impl_copy(l): itemty = l.item_type if isinstance(l, types.ListType): def impl(l): newl = new_list(itemty, len(l)) for i in l: newl.append(i) return newl return impl @overload_method(types.ListType, 'index') def impl_index(l, item, start=None, end=None): if not isinstance(l, types.ListType): return itemty = l.item_type def check_arg(arg, name): if not (arg is None or arg in index_types or isinstance(arg, (types.Omitted, types.NoneType))): raise TypingError("{} argument for index must be an integer" .format(name)) check_arg(start, "start") check_arg(end, "end") def impl(l, item, start=None, end=None): casteditem = _cast(item, itemty) for i in handle_slice(l, slice(start, end, 1)): if l[i] == casteditem: return i else: raise ValueError("item not in list") return impl @overload_method(types.ListType, "sort") def ol_list_sort(lst, key=None, reverse=False): # The following is mostly borrowed from listobj.ol_list_sort from numba.typed import List listobj._sort_check_key(key) listobj._sort_check_reverse(reverse) if cgutils.is_nonelike(key): KEY = False sort_f = listobj.sort_forwards sort_b = listobj.sort_backwards elif isinstance(key, types.Dispatcher): KEY = True sort_f = listobj.arg_sort_forwards sort_b = listobj.arg_sort_backwards def impl(lst, key=None, reverse=False): if KEY is True: # There's an unknown refct problem in reflected list. # Using an explicit loop with typedlist somehow "fixed" it. _lst = List() for x in lst: _lst.append(key(x)) else: _lst = lst if reverse is False or reverse == 0: tmp = sort_f(_lst) else: tmp = sort_b(_lst) if KEY is True: # There's an unknown refct problem in reflected list. # Using an explicit loop with typedlist somehow "fixed" it. ordered = List() for i in tmp: ordered.append(lst[i]) lst[:] = ordered return impl def _equals_helper(this, other, OP): if not isinstance(this, types.ListType): return if not isinstance(other, types.ListType): return lambda this, other: False def impl(this, other): def equals(this, other): if len(this) != len(other): return False for i in range(len(this)): if this[i] != other[i]: return False else: return True return OP(equals(this, other)) return impl @overload(operator.eq) def impl_equals(this, other): return _equals_helper(this, other, operator.truth) @overload(operator.ne) def impl_not_equals(this, other): return _equals_helper(this, other, operator.not_) @register_jitable def compare(this, other): """Oldschool (python 2.x) cmp. if this < other return -1 if this = other return 0 if this > other return 1 """ if len(this) != len(other): return -1 if len(this) < len(other) else 1 for i in range(len(this)): this_item, other_item = this[i], other[i] if this_item != other_item: return -1 if this_item < other_item else 1 else: return 0 def compare_helper(this, other, accepted): if not isinstance(this, types.ListType): return if not isinstance(other, types.ListType): return lambda this, other: False def impl(this, other): return compare(this, other) in accepted return impl @overload(operator.lt) def impl_less_than(this, other): return compare_helper(this, other, (-1, )) @overload(operator.le) def impl_less_than_or_equal(this, other): return compare_helper(this, other, (-1, 0)) @overload(operator.gt) def impl_greater_than(this, other): return compare_helper(this, other, (1,)) @overload(operator.ge) def impl_greater_than_or_equal(this, other): return compare_helper(this, other, (0, 1)) @lower_builtin('getiter', types.ListType) def impl_list_getiter(context, builder, sig, args): """Implement iter(List). """ [tl] = sig.args [l] = args iterablety = types.ListTypeIterableType(tl) it = context.make_helper(builder, iterablety.iterator_type) fnty = ir.FunctionType( ir.VoidType(), [ll_listiter_type, ll_list_type], ) fn = builder.module.get_or_insert_function(fnty, name='numba_list_iter') proto = ctypes.CFUNCTYPE(ctypes.c_size_t) listiter_sizeof = proto(_helperlib.c_helpers['list_iter_sizeof']) state_type = ir.ArrayType(ir.IntType(8), listiter_sizeof()) pstate = cgutils.alloca_once(builder, state_type, zfill=True) it.state = _as_bytes(builder, pstate) it.parent = l dp = _container_get_data(context, builder, iterablety.parent, args[0]) builder.call(fn, [it.state, dp]) return impl_ret_borrowed( context, builder, sig.return_type, it._getvalue(), ) @lower_builtin('iternext', types.ListTypeIteratorType) @iternext_impl(RefType.BORROWED) def impl_iterator_iternext(context, builder, sig, args, result): iter_type = sig.args[0] it = context.make_helper(builder, iter_type, args[0]) iternext_fnty = ir.FunctionType( ll_status, [ll_listiter_type, ll_bytes.as_pointer()] ) iternext = builder.module.get_or_insert_function( iternext_fnty, name='numba_list_iter_next', ) item_raw_ptr = cgutils.alloca_once(builder, ll_bytes) status = builder.call(iternext, (it.state, item_raw_ptr)) # check for list mutation mutated_status = status.type(int(ListStatus.LIST_ERR_MUTATED)) is_mutated = builder.icmp_signed('==', status, mutated_status) with builder.if_then(is_mutated, likely=False): context.call_conv.return_user_exc( builder, RuntimeError, ("list was mutated during iteration",)) # if the list wasn't mutated it is either fine or the iterator was # exhausted ok_status = status.type(int(ListStatus.LIST_OK)) is_valid = builder.icmp_signed('==', status, ok_status) result.set_valid(is_valid) with builder.if_then(is_valid, likely=True): item_ty = iter_type.parent.item_type dm_item = context.data_model_manager[item_ty] item_ptr = builder.bitcast( builder.load(item_raw_ptr), dm_item.get_data_type().as_pointer(), ) item = dm_item.load_from_data_pointer(builder, item_ptr) if isinstance(iter_type.iterable, ListTypeIterableType): result.yield_(item) else: # unreachable raise AssertionError('unknown type: {}'.format(iter_type.iterable))