listobject.py

"""
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))