#include "py_list.h"
#include "py_dict.h"
#include "py_cast.h"
#include "py_errors.h"
#include "py_utils.h"

#include <yql/essentials/public/udf/udf_value.h>
#include <yql/essentials/public/udf/udf_value_builder.h>

using namespace NKikimr;

#if PY_MAJOR_VERSION >= 3
    #define SLICEOBJ(obj) obj
#else
    #define SLICEOBJ(obj) (reinterpret_cast<PySliceObject*>(obj))
    // See details about need for backports in ya.make
    #include "py27_backports.h"
#endif

namespace NPython {

namespace {
inline Py_ssize_t CastIndex(PyObject* key, const char* name)
{
    Py_ssize_t index = -1;
    if (PyIndex_Check(key)) {
        index = PyNumber_AsSsize_t(key, PyExc_IndexError);
    }
    if (index < 0) {
        const TPyObjectPtr value = PyUnicode_FromFormat("argument of %s must be positive integer or long", name);
        PyErr_SetObject(PyExc_IndexError, value.Get());
    }

    return index;
}
} // namespace

//////////////////////////////////////////////////////////////////////////////
// TPyLazyList interface
//////////////////////////////////////////////////////////////////////////////
struct TPyLazyList {
    using TPtr = NUdf::TRefCountedPtr<TPyLazyList, TPyPtrOps<TPyLazyList>>;

    PyObject_HEAD;
    TPyCastContext::TPtr CastCtx;
    const NUdf::TType* ItemType;
    TPyCleanupListItem<NUdf::IBoxedValuePtr> Value;
    TPyCleanupListItem<NUdf::IBoxedValuePtr> Dict;
    Py_ssize_t Step;
    Py_ssize_t CachedLength;

    inline static TPyLazyList* Cast(PyObject* o) {
        return reinterpret_cast<TPyLazyList*>(o);
    }

    inline static void Dealloc(PyObject* self) {
        delete Cast(self);
    }

    static PyObject* New(
        const TPyCastContext::TPtr& castCtx,
        const NUdf::TType* itemType,
        NUdf::IBoxedValuePtr value,
        Py_ssize_t step = 1,
        Py_ssize_t size = -1);

    static int Bool(PyObject* self);
    static PyObject* Repr(PyObject* self);
    static PyObject* Iter(PyObject* self);
    static Py_ssize_t Len(PyObject* self);
    static PyObject* Subscript(PyObject* self, PyObject* slice);
    static PyObject* ToIndexDict(PyObject* self, PyObject* /* arg */);
    static PyObject* Reversed(PyObject* self, PyObject* /* arg */);
    static PyObject* Take(PyObject* self, PyObject* arg);
    static PyObject* Skip(PyObject* self, PyObject* arg);
    static PyObject* HasFastLen(PyObject* self, PyObject* /* arg */);
    static PyObject* HasItems(PyObject* self, PyObject* /* arg */);
};

PyMappingMethods LazyListMapping = {
    INIT_MEMBER(mp_length, TPyLazyList::Len),
    INIT_MEMBER(mp_subscript, TPyLazyList::Subscript),
    INIT_MEMBER(mp_ass_subscript, nullptr),
};

PyNumberMethods LazyListNumbering = {
    INIT_MEMBER(nb_add, nullptr),
    INIT_MEMBER(nb_subtract, nullptr),
    INIT_MEMBER(nb_multiply, nullptr),
#if PY_MAJOR_VERSION < 3
    INIT_MEMBER(nb_divide, nullptr),
#endif
    INIT_MEMBER(nb_remainder, nullptr),
    INIT_MEMBER(nb_divmod, nullptr),
    INIT_MEMBER(nb_power, nullptr),
    INIT_MEMBER(nb_negative, nullptr),
    INIT_MEMBER(nb_positive, nullptr),
    INIT_MEMBER(nb_absolute, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(nb_bool, TPyLazyList::Bool),
#else
    INIT_MEMBER(nb_nonzero, TPyLazyList::Bool),
#endif
    INIT_MEMBER(nb_invert, nullptr),
    INIT_MEMBER(nb_lshift, nullptr),
    INIT_MEMBER(nb_rshift, nullptr),
    INIT_MEMBER(nb_and, nullptr),
    INIT_MEMBER(nb_xor, nullptr),
    INIT_MEMBER(nb_or, nullptr),
#if PY_MAJOR_VERSION < 3
    INIT_MEMBER(nb_coerce, nullptr),
#endif
    INIT_MEMBER(nb_int, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(nb_reserved, nullptr),
#else
    INIT_MEMBER(nb_long, nullptr),
#endif
    INIT_MEMBER(nb_float, nullptr),
#if PY_MAJOR_VERSION < 3
    INIT_MEMBER(nb_oct, nullptr),
    INIT_MEMBER(nb_hex, nullptr),
#endif

    INIT_MEMBER(nb_inplace_add, nullptr),
    INIT_MEMBER(nb_inplace_subtract, nullptr),
    INIT_MEMBER(nb_inplace_multiply, nullptr),
    INIT_MEMBER(nb_inplace_remainder, nullptr),
    INIT_MEMBER(nb_inplace_power, nullptr),
    INIT_MEMBER(nb_inplace_lshift, nullptr),
    INIT_MEMBER(nb_inplace_rshift, nullptr),
    INIT_MEMBER(nb_inplace_and, nullptr),
    INIT_MEMBER(nb_inplace_xor, nullptr),
    INIT_MEMBER(nb_inplace_or, nullptr),

    INIT_MEMBER(nb_floor_divide, nullptr),
    INIT_MEMBER(nb_true_divide, nullptr),
    INIT_MEMBER(nb_inplace_floor_divide, nullptr),
    INIT_MEMBER(nb_inplace_true_divide, nullptr),

    INIT_MEMBER(nb_index, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(nb_matrix_multiply, nullptr),
    INIT_MEMBER(nb_inplace_matrix_multiply, nullptr),
#endif
};

namespace {

PyDoc_STRVAR(reversed__doc__, "DEPRECATED: use reversed(list) or list[::-1] instead.");
PyDoc_STRVAR(take__doc__, "DEPRECATED: use slice list[:n] instead.");
PyDoc_STRVAR(skip__doc__, "DEPRECATED: use slice list[n:] instead.");
PyDoc_STRVAR(to_index_dict__doc__, "DEPRECATED: use list[n] instead.");
PyDoc_STRVAR(has_fast_len__doc__, "DEPRECATED: do not use.");
PyDoc_STRVAR(has_items__doc__, "DEPRECATED: test list as bool instead.");

// NOLINTNEXTLINE(modernize-avoid-c-arrays)
PyMethodDef TPyLazyListMethods[] = {
    {"__reversed__", TPyLazyList::Reversed, METH_NOARGS, nullptr},
    {"to_index_dict", TPyLazyList::ToIndexDict, METH_NOARGS, to_index_dict__doc__},
    {"reversed", TPyLazyList::Reversed, METH_NOARGS, reversed__doc__},
    {"take", TPyLazyList::Take, METH_O, take__doc__},
    {"skip", TPyLazyList::Skip, METH_O, skip__doc__},
    {"has_fast_len", TPyLazyList::HasFastLen, METH_NOARGS, has_fast_len__doc__},
    {"has_items", TPyLazyList::HasItems, METH_NOARGS, has_items__doc__},
    {nullptr, nullptr, 0, nullptr} /* sentinel */
};

} // namespace

#if PY_MAJOR_VERSION >= 3
    #define Py_TPFLAGS_HAVE_ITER 0 // NOLINT(readability-identifier-naming)
#endif

PyTypeObject PyLazyListType = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    // clang-format off
    INIT_MEMBER(tp_name, "yql.TList"),
    // clang-format on
    INIT_MEMBER(tp_basicsize, sizeof(TPyLazyList)),
    INIT_MEMBER(tp_itemsize, 0),
    INIT_MEMBER(tp_dealloc, TPyLazyList::Dealloc),
#if PY_VERSION_HEX < 0x030800b4
    INIT_MEMBER(tp_print, nullptr),
#else
    INIT_MEMBER(tp_vectorcall_offset, 0),
#endif
    INIT_MEMBER(tp_getattr, nullptr),
    INIT_MEMBER(tp_setattr, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(tp_as_async, nullptr),
#else
    INIT_MEMBER(tp_compare, nullptr),
#endif
    INIT_MEMBER(tp_repr, TPyLazyList::Repr),
    INIT_MEMBER(tp_as_number, &LazyListNumbering),
    INIT_MEMBER(tp_as_sequence, nullptr),
    INIT_MEMBER(tp_as_mapping, &LazyListMapping),
    INIT_MEMBER(tp_hash, nullptr),
    INIT_MEMBER(tp_call, nullptr),
    INIT_MEMBER(tp_str, nullptr),
    INIT_MEMBER(tp_getattro, nullptr),
    INIT_MEMBER(tp_setattro, nullptr),
    INIT_MEMBER(tp_as_buffer, nullptr),
    INIT_MEMBER(tp_flags, Py_TPFLAGS_HAVE_ITER),
    INIT_MEMBER(tp_doc, "yql.TList object"),
    INIT_MEMBER(tp_traverse, nullptr),
    INIT_MEMBER(tp_clear, nullptr),
    INIT_MEMBER(tp_richcompare, nullptr),
    INIT_MEMBER(tp_weaklistoffset, 0),
    INIT_MEMBER(tp_iter, TPyLazyList::Iter),
    INIT_MEMBER(tp_iternext, nullptr),
    INIT_MEMBER(tp_methods, TPyLazyListMethods),
    INIT_MEMBER(tp_members, nullptr),
    INIT_MEMBER(tp_getset, nullptr),
    INIT_MEMBER(tp_base, nullptr),
    INIT_MEMBER(tp_dict, nullptr),
    INIT_MEMBER(tp_descr_get, nullptr),
    INIT_MEMBER(tp_descr_set, nullptr),
    INIT_MEMBER(tp_dictoffset, 0),
    INIT_MEMBER(tp_init, nullptr),
    INIT_MEMBER(tp_alloc, nullptr),
    INIT_MEMBER(tp_new, nullptr),
    INIT_MEMBER(tp_free, nullptr),
    INIT_MEMBER(tp_is_gc, nullptr),
    INIT_MEMBER(tp_bases, nullptr),
    INIT_MEMBER(tp_mro, nullptr),
    INIT_MEMBER(tp_cache, nullptr),
    INIT_MEMBER(tp_subclasses, nullptr),
    INIT_MEMBER(tp_weaklist, nullptr),
    INIT_MEMBER(tp_del, nullptr),
    INIT_MEMBER(tp_version_tag, 0),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(tp_finalize, nullptr),
#endif
#if PY_VERSION_HEX >= 0x030800b1
    INIT_MEMBER(tp_vectorcall, nullptr),
#endif
#if PY_VERSION_HEX >= 0x030800b4 && PY_VERSION_HEX < 0x03090000
    INIT_MEMBER(tp_print, nullptr),
#endif
};

//////////////////////////////////////////////////////////////////////////////
// TPyLazyListIterator interface
//////////////////////////////////////////////////////////////////////////////
struct TPyLazyListIterator {
    PyObject_HEAD;
    TPyLazyList::TPtr List;
    TPyCleanupListItem<NUdf::TUnboxedValue> Iterator;
    Py_ssize_t Length;
    TPyCastContext::TPtr CastCtx;

    inline static TPyLazyListIterator* Cast(PyObject* o) {
        return reinterpret_cast<TPyLazyListIterator*>(o);
    }

    inline static void Dealloc(PyObject* self) {
        auto obj = Cast(self);
        auto ctx = obj->CastCtx;
        ctx->MemoryLock->Acquire();
        delete obj;
        ctx->MemoryLock->Release();
    }

    inline static PyObject* Repr(PyObject* self) {
        Y_UNUSED(self);
        return PyRepr("<yql.TListIterator>").Release();
    }

    static PyObject* New(TPyLazyList* list);
    static PyObject* Next(PyObject* self);
};

PyTypeObject PyLazyListIteratorType = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    // clang-format off
    INIT_MEMBER(tp_name, "yql.TListIterator"),
    // clang-format on
    INIT_MEMBER(tp_basicsize, sizeof(TPyLazyListIterator)),
    INIT_MEMBER(tp_itemsize, 0),
    INIT_MEMBER(tp_dealloc, TPyLazyListIterator::Dealloc),
#if PY_VERSION_HEX < 0x030800b4
    INIT_MEMBER(tp_print, nullptr),
#else
    INIT_MEMBER(tp_vectorcall_offset, 0),
#endif
    INIT_MEMBER(tp_getattr, nullptr),
    INIT_MEMBER(tp_setattr, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(tp_as_async, nullptr),
#else
    INIT_MEMBER(tp_compare, nullptr),
#endif
    INIT_MEMBER(tp_repr, TPyLazyListIterator::Repr),
    INIT_MEMBER(tp_as_number, nullptr),
    INIT_MEMBER(tp_as_sequence, nullptr),
    INIT_MEMBER(tp_as_mapping, nullptr),
    INIT_MEMBER(tp_hash, nullptr),
    INIT_MEMBER(tp_call, nullptr),
    INIT_MEMBER(tp_str, nullptr),
    INIT_MEMBER(tp_getattro, nullptr),
    INIT_MEMBER(tp_setattro, nullptr),
    INIT_MEMBER(tp_as_buffer, nullptr),
    INIT_MEMBER(tp_flags, Py_TPFLAGS_HAVE_ITER),
    INIT_MEMBER(tp_doc, "yql.ListIterator object"),
    INIT_MEMBER(tp_traverse, nullptr),
    INIT_MEMBER(tp_clear, nullptr),
    INIT_MEMBER(tp_richcompare, nullptr),
    INIT_MEMBER(tp_weaklistoffset, 0),
    INIT_MEMBER(tp_iter, PyObject_SelfIter),
    INIT_MEMBER(tp_iternext, TPyLazyListIterator::Next),
    INIT_MEMBER(tp_methods, nullptr),
    INIT_MEMBER(tp_members, nullptr),
    INIT_MEMBER(tp_getset, nullptr),
    INIT_MEMBER(tp_base, nullptr),
    INIT_MEMBER(tp_dict, nullptr),
    INIT_MEMBER(tp_descr_get, nullptr),
    INIT_MEMBER(tp_descr_set, nullptr),
    INIT_MEMBER(tp_dictoffset, 0),
    INIT_MEMBER(tp_init, nullptr),
    INIT_MEMBER(tp_alloc, nullptr),
    INIT_MEMBER(tp_new, nullptr),
    INIT_MEMBER(tp_free, nullptr),
    INIT_MEMBER(tp_is_gc, nullptr),
    INIT_MEMBER(tp_bases, nullptr),
    INIT_MEMBER(tp_mro, nullptr),
    INIT_MEMBER(tp_cache, nullptr),
    INIT_MEMBER(tp_subclasses, nullptr),
    INIT_MEMBER(tp_weaklist, nullptr),
    INIT_MEMBER(tp_del, nullptr),
    INIT_MEMBER(tp_version_tag, 0),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(tp_finalize, nullptr),
#endif
#if PY_VERSION_HEX >= 0x030800b1
    INIT_MEMBER(tp_vectorcall, nullptr),
#endif
#if PY_VERSION_HEX >= 0x030800b4 && PY_VERSION_HEX < 0x03090000
    INIT_MEMBER(tp_print, nullptr),
#endif
};

//////////////////////////////////////////////////////////////////////////////
// TPyLazyList implementation
//////////////////////////////////////////////////////////////////////////////
PyObject* TPyLazyList::New(
    const TPyCastContext::TPtr& castCtx,
    const NUdf::TType* itemType,
    NUdf::IBoxedValuePtr value,
    Py_ssize_t step,
    Py_ssize_t size)
{
    TPyLazyList* list = new TPyLazyList;
    PyObject_INIT(list, &PyLazyListType);

    list->CastCtx = castCtx;
    list->ItemType = itemType;
    list->Value.Set(castCtx->PyCtx, value);
    list->Step = step;
    list->CachedLength = size;

    return reinterpret_cast<PyObject*>(list);
}

PyObject* TPyLazyList::Repr(PyObject*)
{
    return PyRepr("<yql.TList>").Release();
}

PyObject* TPyLazyList::Iter(PyObject* self)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
return TPyLazyListIterator::New(list);
} // namespace NPython
PY_CATCH(nullptr)
}

Py_ssize_t TPyLazyList::Len(PyObject* self)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
if (list->CachedLength == -1) {
    list->CachedLength = static_cast<Py_ssize_t>(NUdf::TBoxedValueAccessor::GetListLength(*list->Value.Get()));
}
return (list->CachedLength + list->Step - 1) / list->Step;
}
PY_CATCH(-1)
}

PyObject* TPyLazyList::Subscript(PyObject* self, PyObject* slice)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
const auto vb = list->CastCtx->ValueBuilder;

if (PyIndex_Check(slice)) {
    Py_ssize_t index = PyNumber_AsSsize_t(slice, PyExc_IndexError);

    if (!list->Dict.IsSet()) {
        list->Dict.Set(list->CastCtx->PyCtx, vb->ToIndexDict(NUdf::TUnboxedValuePod(list->Value.Get().Get())).AsBoxed());
    }

    if (index < 0) {
        if (list->CachedLength == -1) {
            list->CachedLength = static_cast<Py_ssize_t>(NUdf::TBoxedValueAccessor::GetDictLength(*list->Dict.Get()));
        }

        ++index *= list->Step;
        --index += list->CachedLength;
    } else {
        index *= list->Step;
    }

    if (index < 0 || (list->CachedLength != -1 && index >= list->CachedLength)) {
        const TPyObjectPtr error = PyUnicode_FromFormat("index %zd out of bounds, list size: %zd", index, list->CachedLength);
        PyErr_SetObject(PyExc_IndexError, error.Get());
        return nullptr;
    }

    if (const auto item = NUdf::TBoxedValueAccessor::Lookup(*list->Dict.Get(), NUdf::TUnboxedValuePod(ui64(index)))) {
        return ToPyObject(list->CastCtx, list->ItemType, item.GetOptionalValue()).Release();
    }

    const TPyObjectPtr error = PyUnicode_FromFormat("index %zd out of bounds", index);
    PyErr_SetObject(PyExc_IndexError, error.Get());
    return nullptr;
}

if (PySlice_Check(slice)) {
    Py_ssize_t start;
    Py_ssize_t stop;
    Py_ssize_t step;
    Py_ssize_t size;

    if (list->CachedLength >= 0) {
        if (PySlice_GetIndicesEx(SLICEOBJ(slice), (list->CachedLength + list->Step - 1) / list->Step, &start, &stop, &step, &size) < 0) {
            return nullptr;
        }
    } else {
        if (PySlice_Unpack(slice, &start, &stop, &step) < 0) {
            return nullptr;
        }

        if (step < -1 || step > 1 || (start < 0 && start > PY_SSIZE_T_MIN) || (stop < 0 && stop > PY_SSIZE_T_MIN)) {
            list->CachedLength = static_cast<Py_ssize_t>(NUdf::TBoxedValueAccessor::GetListLength(*list->Value.Get()));
            size = PySlice_AdjustIndices((list->CachedLength + list->Step - 1) / list->Step, &start, &stop, step);
        } else {
            size = PySlice_AdjustIndices(PY_SSIZE_T_MAX, &start, &stop, step);
        }
    }

    if (!step) {
        PyErr_SetString(PyExc_ValueError, "slice step cannot be zero");
        return nullptr;
    }

    const Py_ssize_t hi = PY_SSIZE_T_MAX / list->Step;
    const Py_ssize_t lo = PY_SSIZE_T_MIN / list->Step;
    step = step > lo && step < hi ? step * list->Step : (step > 0 ? PY_SSIZE_T_MAX : PY_SSIZE_T_MIN);

    NUdf::TUnboxedValue newList;
    if (size > 0) {
        size = step > 0 ? (size < PY_SSIZE_T_MAX / step ? --size * step + 1 : PY_SSIZE_T_MAX) : (size < PY_SSIZE_T_MAX / -step ? --size * -step + 1 : PY_SSIZE_T_MAX);

        start = start < hi ? start * list->Step : PY_SSIZE_T_MAX;
        const Py_ssize_t skip = step > 0 ? start : start - size + 1;

        newList = NUdf::TUnboxedValuePod(list->Value.Get().Get());
        if (skip > 0) {
            newList = vb->SkipList(newList, skip);
        }

        if (size < PY_SSIZE_T_MAX && (list->CachedLength == -1 || list->CachedLength - skip > size)) {
            newList = vb->TakeList(newList, size);
        }

        if (step < 0) {
            step = -step;
            newList = vb->ReverseList(newList);
        }
    } else {
        newList = vb->NewEmptyList();
    }

    return New(list->CastCtx, list->ItemType, newList.AsBoxed(), step, size);
}

const TPyObjectPtr type = PyObject_Type(slice);
const TPyObjectPtr repr = PyObject_Repr(type.Get());
const TPyObjectPtr error = PyUnicode_FromFormat("Unsupported slice object type: %R", repr.Get());
PyErr_SetObject(PyExc_TypeError, error.Get());
return nullptr;
}
PY_CATCH(nullptr)
}

PyObject* TPyLazyList::ToIndexDict(PyObject* self, PyObject* /* arg */)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
if (!list->Dict.IsSet()) {
    list->Dict.Set(list->CastCtx->PyCtx, list->CastCtx->ValueBuilder->ToIndexDict(NUdf::TUnboxedValuePod(list->Value.Get().Get())).AsBoxed());
}

return ToPyLazyDict(list->CastCtx, nullptr, list->ItemType, NUdf::TUnboxedValuePod(list->Dict.Get().Get())).Release();
}
PY_CATCH(nullptr)
}

PyObject* TPyLazyList::Reversed(PyObject* self, PyObject* /* arg */)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
const auto newList = list->CastCtx->ValueBuilder->ReverseList(NUdf::TUnboxedValuePod(list->Value.Get().Get()));
return New(list->CastCtx, list->ItemType, newList.AsBoxed(), list->Step);
}
PY_CATCH(nullptr)
}

PyObject* TPyLazyList::Take(PyObject* self, PyObject* arg)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
Py_ssize_t count = CastIndex(arg, "take");
if (count < 0) {
    return nullptr;
}
count *= list->Step;

auto vb = list->CastCtx->ValueBuilder;
NUdf::TUnboxedValue value(NUdf::TUnboxedValuePod(list->Value.Get().Get()));
auto newList = vb->TakeList(value, static_cast<ui64>(count));
return New(list->CastCtx, list->ItemType, newList.AsBoxed(), list->Step);
}
PY_CATCH(nullptr)
}

PyObject* TPyLazyList::Skip(PyObject* self, PyObject* arg)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
Py_ssize_t count = CastIndex(arg, "skip");
if (count < 0) {
    return nullptr;
}
count *= list->Step;

NUdf::TUnboxedValue value(NUdf::TUnboxedValuePod(list->Value.Get().Get()));
const auto newList = list->CastCtx->ValueBuilder->SkipList(value, static_cast<ui64>(count));
return New(list->CastCtx, list->ItemType, newList.AsBoxed(), list->Step);
}
PY_CATCH(nullptr)
}

PyObject* TPyLazyList::HasFastLen(PyObject* self, PyObject* /* arg */)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
if (NUdf::TBoxedValueAccessor::HasFastListLength(*list->Value.Get())) {
    Py_RETURN_TRUE;
}
Py_RETURN_FALSE;
}
PY_CATCH(nullptr)
}

PyObject* TPyLazyList::HasItems(PyObject* self, PyObject* /* arg */)
{
    PY_TRY {
        TPyLazyList* list = Cast(self);
        if (NUdf::TBoxedValueAccessor::HasListItems(*list->Value.Get())) {
            Py_RETURN_TRUE;
        }
        Py_RETURN_FALSE;
    }
    PY_CATCH(nullptr)
}

int TPyLazyList::Bool(PyObject* self)
    {
        PY_TRY{
            TPyLazyList* list = Cast(self);
if (list->CachedLength == -1) {
    return NUdf::TBoxedValueAccessor::HasListItems(*list->Value.Get()) ? 1 : 0;
} else {
    return list->CachedLength > 0 ? 1 : 0;
}
}
PY_CATCH(-1)
}

//////////////////////////////////////////////////////////////////////////////
// TPyLazyListIterator implementation
//////////////////////////////////////////////////////////////////////////////
PyObject* TPyLazyListIterator::New(TPyLazyList* list)
{
    TPyLazyListIterator* listIter = new TPyLazyListIterator;
    PyObject_INIT(listIter, &PyLazyListIteratorType);
    listIter->List.Reset(list);
    listIter->Iterator.Set(list->CastCtx->PyCtx, NUdf::TBoxedValueAccessor::GetListIterator(*list->Value.Get()));
    listIter->Length = 0;
    listIter->CastCtx = list->CastCtx;
    return reinterpret_cast<PyObject*>(listIter);
}

PyObject* TPyLazyListIterator::Next(PyObject* self)
{
    PY_TRY {
        TPyLazyListIterator* iter = Cast(self);
        TPyLazyList* list = iter->List.Get();

        NUdf::TUnboxedValue item;
        if (iter->Iterator.Get().Next(item)) {
            ++iter->Length;

            for (auto skip = list->Step; --skip && iter->Iterator.Get().Skip(); ++iter->Length) {
                continue;
            }

            return ToPyObject(list->CastCtx, list->ItemType, item).Release();
        }

        // store calculated list length after traverse over whole list
        if (list->CachedLength == -1) {
            list->CachedLength = iter->Length;
        }

        return nullptr;
    }
    PY_CATCH(nullptr)
}

//////////////////////////////////////////////////////////////////////////////
// TPyThinList interface
//////////////////////////////////////////////////////////////////////////////
struct TPyThinList {
    using TPtr = NUdf::TRefCountedPtr<TPyThinList, TPyPtrOps<TPyThinList>>;

    PyObject_HEAD;
    TPyCastContext::TPtr CastCtx;
    const NUdf::TType* ItemType;
    TPyCleanupListItem<NUdf::IBoxedValuePtr> Value;
    const NUdf::TUnboxedValue* Elements;
    Py_ssize_t Length;
    Py_ssize_t Step;

    inline static TPyThinList* Cast(PyObject* o) {
        return reinterpret_cast<TPyThinList*>(o);
    }

    inline static void Dealloc(PyObject* self) {
        delete Cast(self);
    }

    static PyObject* New(
        const TPyCastContext::TPtr& castCtx,
        const NUdf::TType* itemType,
        NUdf::IBoxedValuePtr value = NUdf::IBoxedValuePtr(),
        const NUdf::TUnboxedValue* elements = nullptr,
        Py_ssize_t length = 0,
        Py_ssize_t step = 1);

    static int Bool(PyObject* self);
    static PyObject* Repr(PyObject* self);
    static PyObject* Iter(PyObject* self);
    static Py_ssize_t Len(PyObject* self);
    static PyObject* Subscript(PyObject* self, PyObject* slice);
    static PyObject* ToIndexDict(PyObject* self, PyObject* /* arg */);
    static PyObject* Reversed(PyObject* self, PyObject* /* arg */);
    static PyObject* Take(PyObject* self, PyObject* arg);
    static PyObject* Skip(PyObject* self, PyObject* arg);
    static PyObject* HasFastLen(PyObject* self, PyObject* /* arg */);
    static PyObject* HasItems(PyObject* self, PyObject* /* arg */);
};

PyMappingMethods ThinListMapping = {
    INIT_MEMBER(mp_length, TPyThinList::Len),
    INIT_MEMBER(mp_subscript, TPyThinList::Subscript),
    INIT_MEMBER(mp_ass_subscript, nullptr),
};

PyNumberMethods ThinListNumbering = {
    INIT_MEMBER(nb_add, nullptr),
    INIT_MEMBER(nb_subtract, nullptr),
    INIT_MEMBER(nb_multiply, nullptr),
#if PY_MAJOR_VERSION < 3
    INIT_MEMBER(nb_divide, nullptr),
#endif
    INIT_MEMBER(nb_remainder, nullptr),
    INIT_MEMBER(nb_divmod, nullptr),
    INIT_MEMBER(nb_power, nullptr),
    INIT_MEMBER(nb_negative, nullptr),
    INIT_MEMBER(nb_positive, nullptr),
    INIT_MEMBER(nb_absolute, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(nb_bool, TPyThinList::Bool),
#else
    INIT_MEMBER(nb_nonzero, TPyThinList::Bool),
#endif
    INIT_MEMBER(nb_invert, nullptr),
    INIT_MEMBER(nb_lshift, nullptr),
    INIT_MEMBER(nb_rshift, nullptr),
    INIT_MEMBER(nb_and, nullptr),
    INIT_MEMBER(nb_xor, nullptr),
    INIT_MEMBER(nb_or, nullptr),
#if PY_MAJOR_VERSION < 3
    INIT_MEMBER(nb_coerce, nullptr),
#endif
    INIT_MEMBER(nb_int, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(nb_reserved, nullptr),
#else
    INIT_MEMBER(nb_long, nullptr),
#endif
    INIT_MEMBER(nb_float, nullptr),
#if PY_MAJOR_VERSION < 3
    INIT_MEMBER(nb_oct, nullptr),
    INIT_MEMBER(nb_hex, nullptr),
#endif

    INIT_MEMBER(nb_inplace_add, nullptr),
    INIT_MEMBER(nb_inplace_subtract, nullptr),
    INIT_MEMBER(nb_inplace_multiply, nullptr),
    INIT_MEMBER(nb_inplace_remainder, nullptr),
    INIT_MEMBER(nb_inplace_power, nullptr),
    INIT_MEMBER(nb_inplace_lshift, nullptr),
    INIT_MEMBER(nb_inplace_rshift, nullptr),
    INIT_MEMBER(nb_inplace_and, nullptr),
    INIT_MEMBER(nb_inplace_xor, nullptr),
    INIT_MEMBER(nb_inplace_or, nullptr),

    INIT_MEMBER(nb_floor_divide, nullptr),
    INIT_MEMBER(nb_true_divide, nullptr),
    INIT_MEMBER(nb_inplace_floor_divide, nullptr),
    INIT_MEMBER(nb_inplace_true_divide, nullptr),

    INIT_MEMBER(nb_index, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(nb_matrix_multiply, nullptr),
    INIT_MEMBER(nb_inplace_matrix_multiply, nullptr),
#endif
};

namespace {

// NOLINTNEXTLINE(modernize-avoid-c-arrays)
PyMethodDef TPyThinListMethods[] = {
    {"__reversed__", TPyThinList::Reversed, METH_NOARGS, nullptr},
    {"to_index_dict", TPyThinList::ToIndexDict, METH_NOARGS, to_index_dict__doc__},
    {"reversed", TPyThinList::Reversed, METH_NOARGS, reversed__doc__},
    {"take", TPyThinList::Take, METH_O, take__doc__},
    {"skip", TPyThinList::Skip, METH_O, skip__doc__},
    {"has_fast_len", TPyThinList::HasFastLen, METH_NOARGS, has_fast_len__doc__},
    {"has_items", TPyThinList::HasItems, METH_NOARGS, has_items__doc__},
    {nullptr, nullptr, 0, nullptr} /* sentinel */
};

} // namespace

#if PY_MAJOR_VERSION >= 3
    #define Py_TPFLAGS_HAVE_ITER 0 // NOLINT(readability-identifier-naming)
#endif

PyTypeObject PyThinListType = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    // clang-format off
    INIT_MEMBER(tp_name, "yql.TList"),
    // clang-format on
    INIT_MEMBER(tp_basicsize, sizeof(TPyThinList)),
    INIT_MEMBER(tp_itemsize, 0),
    INIT_MEMBER(tp_dealloc, TPyThinList::Dealloc),
#if PY_VERSION_HEX < 0x030800b4
    INIT_MEMBER(tp_print, nullptr),
#else
    INIT_MEMBER(tp_vectorcall_offset, 0),
#endif
    INIT_MEMBER(tp_getattr, nullptr),
    INIT_MEMBER(tp_setattr, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(tp_as_async, nullptr),
#else
    INIT_MEMBER(tp_compare, nullptr),
#endif
    INIT_MEMBER(tp_repr, TPyThinList::Repr),
    INIT_MEMBER(tp_as_number, &ThinListNumbering),
    INIT_MEMBER(tp_as_sequence, nullptr),
    INIT_MEMBER(tp_as_mapping, &ThinListMapping),
    INIT_MEMBER(tp_hash, nullptr),
    INIT_MEMBER(tp_call, nullptr),
    INIT_MEMBER(tp_str, nullptr),
    INIT_MEMBER(tp_getattro, nullptr),
    INIT_MEMBER(tp_setattro, nullptr),
    INIT_MEMBER(tp_as_buffer, nullptr),
    INIT_MEMBER(tp_flags, Py_TPFLAGS_HAVE_ITER),
    INIT_MEMBER(tp_doc, "yql.TList object"),
    INIT_MEMBER(tp_traverse, nullptr),
    INIT_MEMBER(tp_clear, nullptr),
    INIT_MEMBER(tp_richcompare, nullptr),
    INIT_MEMBER(tp_weaklistoffset, 0),
    INIT_MEMBER(tp_iter, TPyThinList::Iter),
    INIT_MEMBER(tp_iternext, nullptr),
    INIT_MEMBER(tp_methods, TPyThinListMethods),
    INIT_MEMBER(tp_members, nullptr),
    INIT_MEMBER(tp_getset, nullptr),
    INIT_MEMBER(tp_base, nullptr),
    INIT_MEMBER(tp_dict, nullptr),
    INIT_MEMBER(tp_descr_get, nullptr),
    INIT_MEMBER(tp_descr_set, nullptr),
    INIT_MEMBER(tp_dictoffset, 0),
    INIT_MEMBER(tp_init, nullptr),
    INIT_MEMBER(tp_alloc, nullptr),
    INIT_MEMBER(tp_new, nullptr),
    INIT_MEMBER(tp_free, nullptr),
    INIT_MEMBER(tp_is_gc, nullptr),
    INIT_MEMBER(tp_bases, nullptr),
    INIT_MEMBER(tp_mro, nullptr),
    INIT_MEMBER(tp_cache, nullptr),
    INIT_MEMBER(tp_subclasses, nullptr),
    INIT_MEMBER(tp_weaklist, nullptr),
    INIT_MEMBER(tp_del, nullptr),
    INIT_MEMBER(tp_version_tag, 0),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(tp_finalize, nullptr),
#endif
#if PY_VERSION_HEX >= 0x030800b1
    INIT_MEMBER(tp_vectorcall, nullptr),
#endif
#if PY_VERSION_HEX >= 0x030800b4 && PY_VERSION_HEX < 0x03090000
    INIT_MEMBER(tp_print, nullptr),
#endif
};

//////////////////////////////////////////////////////////////////////////////
// TPyThinListIterator interface
//////////////////////////////////////////////////////////////////////////////
struct TPyThinListIterator {
    PyObject_HEAD;
    TPyThinList::TPtr List;
    const NUdf::TUnboxedValue* Elements;
    Py_ssize_t Count;

    inline static TPyThinListIterator* Cast(PyObject* o) {
        return reinterpret_cast<TPyThinListIterator*>(o);
    }

    inline static void Dealloc(PyObject* self) {
        delete Cast(self);
    }

    inline static PyObject* Repr(PyObject* self) {
        Y_UNUSED(self);
        return PyRepr("<yql.TListIterator>").Release();
    }

    static PyObject* New(TPyThinList* list);
    static PyObject* Next(PyObject* self);
};

PyTypeObject PyThinListIteratorType = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    // clang-format off
    INIT_MEMBER(tp_name, "yql.TListIterator"),
    // clang-format on
    INIT_MEMBER(tp_basicsize, sizeof(TPyThinListIterator)),
    INIT_MEMBER(tp_itemsize, 0),
    INIT_MEMBER(tp_dealloc, TPyThinListIterator::Dealloc),
#if PY_VERSION_HEX < 0x030800b4
    INIT_MEMBER(tp_print, nullptr),
#else
    INIT_MEMBER(tp_vectorcall_offset, 0),
#endif
    INIT_MEMBER(tp_getattr, nullptr),
    INIT_MEMBER(tp_setattr, nullptr),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(tp_as_async, nullptr),
#else
    INIT_MEMBER(tp_compare, nullptr),
#endif
    INIT_MEMBER(tp_repr, TPyThinListIterator::Repr),
    INIT_MEMBER(tp_as_number, nullptr),
    INIT_MEMBER(tp_as_sequence, nullptr),
    INIT_MEMBER(tp_as_mapping, nullptr),
    INIT_MEMBER(tp_hash, nullptr),
    INIT_MEMBER(tp_call, nullptr),
    INIT_MEMBER(tp_str, nullptr),
    INIT_MEMBER(tp_getattro, nullptr),
    INIT_MEMBER(tp_setattro, nullptr),
    INIT_MEMBER(tp_as_buffer, nullptr),
    INIT_MEMBER(tp_flags, Py_TPFLAGS_HAVE_ITER),
    INIT_MEMBER(tp_doc, "yql.ListIterator object"),
    INIT_MEMBER(tp_traverse, nullptr),
    INIT_MEMBER(tp_clear, nullptr),
    INIT_MEMBER(tp_richcompare, nullptr),
    INIT_MEMBER(tp_weaklistoffset, 0),
    INIT_MEMBER(tp_iter, PyObject_SelfIter),
    INIT_MEMBER(tp_iternext, TPyThinListIterator::Next),
    INIT_MEMBER(tp_methods, nullptr),
    INIT_MEMBER(tp_members, nullptr),
    INIT_MEMBER(tp_getset, nullptr),
    INIT_MEMBER(tp_base, nullptr),
    INIT_MEMBER(tp_dict, nullptr),
    INIT_MEMBER(tp_descr_get, nullptr),
    INIT_MEMBER(tp_descr_set, nullptr),
    INIT_MEMBER(tp_dictoffset, 0),
    INIT_MEMBER(tp_init, nullptr),
    INIT_MEMBER(tp_alloc, nullptr),
    INIT_MEMBER(tp_new, nullptr),
    INIT_MEMBER(tp_free, nullptr),
    INIT_MEMBER(tp_is_gc, nullptr),
    INIT_MEMBER(tp_bases, nullptr),
    INIT_MEMBER(tp_mro, nullptr),
    INIT_MEMBER(tp_cache, nullptr),
    INIT_MEMBER(tp_subclasses, nullptr),
    INIT_MEMBER(tp_weaklist, nullptr),
    INIT_MEMBER(tp_del, nullptr),
    INIT_MEMBER(tp_version_tag, 0),
#if PY_MAJOR_VERSION >= 3
    INIT_MEMBER(tp_finalize, nullptr),
#endif
#if PY_VERSION_HEX >= 0x030800b1
    INIT_MEMBER(tp_vectorcall, nullptr),
#endif
#if PY_VERSION_HEX >= 0x030800b4 && PY_VERSION_HEX < 0x03090000
    INIT_MEMBER(tp_print, nullptr),
#endif
};

//////////////////////////////////////////////////////////////////////////////
// TPyThinList implementation
//////////////////////////////////////////////////////////////////////////////
PyObject* TPyThinList::New(
    const TPyCastContext::TPtr& castCtx,
    const NUdf::TType* itemType,
    NUdf::IBoxedValuePtr value,
    const NUdf::TUnboxedValue* elements,
    Py_ssize_t length,
    Py_ssize_t step)
{
    TPyThinList* list = new TPyThinList;
    PyObject_INIT(list, &PyThinListType);

    list->CastCtx = castCtx;
    list->ItemType = itemType;
    list->Value.Set(castCtx->PyCtx, value);
    list->Elements = elements;
    list->Length = length;
    list->Step = step;

    return reinterpret_cast<PyObject*>(list);
}

PyObject* TPyThinList::Repr(PyObject*)
{
    return PyRepr("<yql.TList>").Release();
}

PyObject* TPyThinList::Iter(PyObject* self)
    {
        PY_TRY{
            TPyThinList* list = Cast(self);
return TPyThinListIterator::New(list);
}
PY_CATCH(nullptr)
}

Py_ssize_t TPyThinList::Len(PyObject* self)
{
    return Cast(self)->Length;
}

PyObject* TPyThinList::Subscript(PyObject* self, PyObject* slice)
    {
        PY_TRY{
            TPyThinList* list = Cast(self);
const auto vb = list->CastCtx->ValueBuilder;

if (PyIndex_Check(slice)) {
    Py_ssize_t index = PyNumber_AsSsize_t(slice, PyExc_IndexError);

    if (index < 0) {
        index += list->Length;
    }

    if (index < 0 || index >= list->Length) {
        const TPyObjectPtr error = PyUnicode_FromFormat("index %zd out of bounds, list size: %zd", index, list->Length);
        PyErr_SetObject(PyExc_IndexError, error.Get());
        return nullptr;
    }

    if (list->Step > 0) {
        index *= list->Step;
    } else {
        index = list->Length - ++index;
        index *= -list->Step;
    }

    return ToPyObject(list->CastCtx, list->ItemType, list->Elements[index]).Release();
}

if (PySlice_Check(slice)) {
    Py_ssize_t start;
    Py_ssize_t stop;
    Py_ssize_t step;
    Py_ssize_t size;

    if (PySlice_GetIndicesEx(SLICEOBJ(slice), list->Length, &start, &stop, &step, &size) < 0) {
        return nullptr;
    }

    if (!step) {
        PyErr_SetString(PyExc_ValueError, "slice step cannot be zero");
        return nullptr;
    }

    if (size > 0) {
        const Py_ssize_t skip = list->Step * (list->Step > 0 ? (step > 0 ? start : start + step * (size - 1)) : (step > 0 ? stop : start + 1) - list->Length);

        return New(list->CastCtx, list->ItemType, list->Value.Get(), list->Elements + skip, size, step * list->Step);
    } else {
        return New(list->CastCtx, list->ItemType, list->Value.Get());
    }
}

const TPyObjectPtr type = PyObject_Type(slice);
const TPyObjectPtr repr = PyObject_Repr(type.Get());
const TPyObjectPtr error = PyUnicode_FromFormat("Unsupported slice object type: %R", repr.Get());
PyErr_SetObject(PyExc_TypeError, error.Get());
return nullptr;
}
PY_CATCH(nullptr)
}

#undef SLICEOBJ

PyObject* TPyThinList::ToIndexDict(PyObject* self, PyObject* /* arg */)
    {
        PY_TRY{
            TPyThinList* list = Cast(self);
const auto dict = list->CastCtx->ValueBuilder->ToIndexDict(NUdf::TUnboxedValuePod(list->Value.Get().Get()));
return ToPyLazyDict(list->CastCtx, nullptr, list->ItemType, dict).Release();
}
PY_CATCH(nullptr)
}

PyObject* TPyThinList::Reversed(PyObject* self, PyObject* /* arg */)
    {
        PY_TRY{
            TPyThinList* list = Cast(self);
return New(list->CastCtx, list->ItemType, list->Value.Get(), list->Elements, list->Length, -list->Step);
}
PY_CATCH(nullptr)
}

PyObject* TPyThinList::Take(PyObject* self, PyObject* arg)
    {
        PY_TRY{
            TPyThinList* list = Cast(self);
const Py_ssize_t count = CastIndex(arg, "take");
if (count < 0) {
    return nullptr;
}

if (const auto size = std::min(count, list->Length)) {
    return New(list->CastCtx, list->ItemType, list->Value.Get(), list->Step > 0 ? list->Elements : list->Elements + list->Length + size * list->Step, size, list->Step);
} else {
    return New(list->CastCtx, list->ItemType, list->Value.Get());
}
}
PY_CATCH(nullptr)
}

PyObject* TPyThinList::Skip(PyObject* self, PyObject* arg)
    {
        PY_TRY{
            TPyThinList* list = Cast(self);
const Py_ssize_t count = CastIndex(arg, "skip");
if (count < 0) {
    return nullptr;
}

if (const auto size = std::max(list->Length - count, Py_ssize_t(0))) {
    return New(list->CastCtx, list->ItemType, list->Value.Get(), list->Step > 0 ? list->Elements + count * list->Step : list->Elements, size, list->Step);
} else {
    return New(list->CastCtx, list->ItemType);
}
}
PY_CATCH(nullptr)
}

PyObject* TPyThinList::HasFastLen(PyObject* self, PyObject* /* arg */)
{
    Py_RETURN_TRUE;
}

PyObject* TPyThinList::HasItems(PyObject* self, PyObject* /* arg */)
{
    if (Cast(self)->Length > 0) {
        Py_RETURN_TRUE;
    } else {
        Py_RETURN_FALSE;
    }
}

int TPyThinList::Bool(PyObject* self)
{
    return Cast(self)->Length > 0 ? 1 : 0;
}

//////////////////////////////////////////////////////////////////////////////
// TPyThinListIterator implementation
//////////////////////////////////////////////////////////////////////////////
PyObject* TPyThinListIterator::New(TPyThinList* list)
{
    TPyThinListIterator* listIter = new TPyThinListIterator;
    PyObject_INIT(listIter, &PyThinListIteratorType);
    listIter->List.Reset(list);
    listIter->Elements = list->Step > 0 ? list->Elements - list->Step : list->Elements - list->Length * list->Step;
    listIter->Count = list->Length;
    return reinterpret_cast<PyObject*>(listIter);
}

PyObject* TPyThinListIterator::Next(PyObject* self)
    {
        PY_TRY{
            TPyThinListIterator* iter = Cast(self);

if (iter->Count) {
    --iter->Count;
    TPyThinList* list = iter->List.Get();
    return ToPyObject(list->CastCtx, list->ItemType, *(iter->Elements += list->Step)).Release();
}

return nullptr;
}
PY_CATCH(nullptr)
}

TPyObjectPtr ToPyLazyList(
    const TPyCastContext::TPtr& castCtx,
    const NUdf::TType* itemType,
    const NUdf::TUnboxedValuePod& value)
{
    if (const auto elements = value.GetElements()) {
        return TPyThinList::New(castCtx, itemType, value.AsBoxed(), elements, value.GetListLength());
    } else {
        return TPyLazyList::New(castCtx, itemType, value.AsBoxed());
    }
}

} // namspace NPython