add ydb deps

1 files changed, 345 insertions, 0 deletions

diff --git a/contrib/tools/python/src/Objects/rangeobject.c b/contrib/tools/python/src/Objects/rangeobject.c
new file mode 100644
index 0000000000..888069a433
--- /dev/null
+++ b/contrib/tools/python/src/Objects/rangeobject.c
@@ -0,0 +1,345 @@
+/* Range object implementation */
+
+#include "Python.h"
+
+typedef struct {
+    PyObject_HEAD
+    long        start;
+    long        step;
+    long        len;
+} rangeobject;
+
+/* Return number of items in range (lo, hi, step).  step != 0
+ * required.  The result always fits in an unsigned long.
+ */
+static unsigned long
+get_len_of_range(long lo, long hi, long step)
+{
+    /* -------------------------------------------------------------
+    If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
+    Else for step > 0, if n values are in the range, the last one is
+    lo + (n-1)*step, which must be <= hi-1.  Rearranging,
+    n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
+    the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so
+    the RHS is non-negative and so truncation is the same as the
+    floor.  Letting M be the largest positive long, the worst case
+    for the RHS numerator is hi=M, lo=-M-1, and then
+    hi-lo-1 = M-(-M-1)-1 = 2*M.  Therefore unsigned long has enough
+    precision to compute the RHS exactly.  The analysis for step < 0
+    is similar.
+    ---------------------------------------------------------------*/
+    assert(step != 0);
+    if (step > 0 && lo < hi)
+        return 1UL + (hi - 1UL - lo) / step;
+    else if (step < 0 && lo > hi)
+        return 1UL + (lo - 1UL - hi) / (0UL - step);
+    else
+        return 0UL;
+}
+
+/* Return a stop value suitable for reconstructing the xrange from
+ * a (start, stop, step) triple.  Used in range_repr and range_reduce.
+ * Computes start + len * step, clipped to the range [LONG_MIN, LONG_MAX].
+ */
+static long
+get_stop_for_range(rangeobject *r)
+{
+    long last;
+
+    if (r->len == 0)
+        return r->start;
+
+    /* The tricky bit is avoiding overflow.  We first compute the last entry in
+       the xrange, start + (len - 1) * step, which is guaranteed to lie within
+       the range of a long, and then add step to it.  See the range_reverse
+       comments for an explanation of the casts below.
+    */
+    last = (long)(r->start + (unsigned long)(r->len - 1) * r->step);
+    if (r->step > 0)
+        return last > LONG_MAX - r->step ? LONG_MAX : last + r->step;
+    else
+        return last < LONG_MIN - r->step ? LONG_MIN : last + r->step;
+}
+
+static PyObject *
+range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
+{
+    rangeobject *obj;
+    long ilow = 0, ihigh = 0, istep = 1;
+    unsigned long n;
+
+    if (!_PyArg_NoKeywords("xrange()", kw))
+        return NULL;
+
+    if (PyTuple_Size(args) <= 1) {
+        if (!PyArg_ParseTuple(args,
+                        "l;xrange() requires 1-3 int arguments",
+                        &ihigh))
+            return NULL;
+    }
+    else {
+        if (!PyArg_ParseTuple(args,
+                        "ll|l;xrange() requires 1-3 int arguments",
+                        &ilow, &ihigh, &istep))
+            return NULL;
+    }
+    if (istep == 0) {
+        PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");
+        return NULL;
+    }
+    n = get_len_of_range(ilow, ihigh, istep);
+    if (n > (unsigned long)LONG_MAX || (long)n > PY_SSIZE_T_MAX) {
+        PyErr_SetString(PyExc_OverflowError,
+                        "xrange() result has too many items");
+        return NULL;
+    }
+
+    obj = PyObject_New(rangeobject, &PyRange_Type);
+    if (obj == NULL)
+        return NULL;
+    obj->start = ilow;
+    obj->len   = (long)n;
+    obj->step  = istep;
+    return (PyObject *) obj;
+}
+
+PyDoc_STRVAR(range_doc,
+"xrange(stop) -> xrange object\n\
+xrange(start, stop[, step]) -> xrange object\n\
+\n\
+Like range(), but instead of returning a list, returns an object that\n\
+generates the numbers in the range on demand.  For looping, this is \n\
+slightly faster than range() and more memory efficient.");
+
+static PyObject *
+range_item(rangeobject *r, Py_ssize_t i)
+{
+    if (i < 0 || i >= r->len) {
+        PyErr_SetString(PyExc_IndexError,
+                        "xrange object index out of range");
+        return NULL;
+    }
+    /* do calculation entirely using unsigned longs, to avoid
+       undefined behaviour due to signed overflow. */
+    return PyInt_FromLong((long)(r->start + (unsigned long)i * r->step));
+}
+
+static Py_ssize_t
+range_length(rangeobject *r)
+{
+    return (Py_ssize_t)(r->len);
+}
+
+static PyObject *
+range_repr(rangeobject *r)
+{
+    PyObject *rtn;
+
+    if (r->start == 0 && r->step == 1)
+        rtn = PyString_FromFormat("xrange(%ld)",
+                                  get_stop_for_range(r));
+
+    else if (r->step == 1)
+        rtn = PyString_FromFormat("xrange(%ld, %ld)",
+                                  r->start,
+                                  get_stop_for_range(r));
+
+    else
+        rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)",
+                                  r->start,
+                                  get_stop_for_range(r),
+                                  r->step);
+    return rtn;
+}
+
+/* Pickling support */
+static PyObject *
+range_reduce(rangeobject *r, PyObject *args)
+{
+    return Py_BuildValue("(O(lll))", Py_TYPE(r),
+                         r->start,
+                         get_stop_for_range(r),
+                         r->step);
+}
+
+static PySequenceMethods range_as_sequence = {
+    (lenfunc)range_length,      /* sq_length */
+    0,                          /* sq_concat */
+    0,                          /* sq_repeat */
+    (ssizeargfunc)range_item, /* sq_item */
+    0,                          /* sq_slice */
+};
+
+static PyObject * range_iter(PyObject *seq);
+static PyObject * range_reverse(PyObject *seq);
+
+PyDoc_STRVAR(reverse_doc,
+"Returns a reverse iterator.");
+
+static PyMethodDef range_methods[] = {
+    {"__reversed__",            (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
+    {"__reduce__",              (PyCFunction)range_reduce, METH_VARARGS},
+    {NULL,              NULL}           /* sentinel */
+};
+
+PyTypeObject PyRange_Type = {
+    PyVarObject_HEAD_INIT(&PyType_Type, 0)
+    "xrange",                   /* Name of this type */
+    sizeof(rangeobject),        /* Basic object size */
+    0,                          /* Item size for varobject */
+    (destructor)PyObject_Del, /* tp_dealloc */
+    0,                          /* tp_print */
+    0,                          /* tp_getattr */
+    0,                          /* tp_setattr */
+    0,                          /* tp_compare */
+    (reprfunc)range_repr,       /* tp_repr */
+    0,                          /* tp_as_number */
+    &range_as_sequence,         /* tp_as_sequence */
+    0,                          /* tp_as_mapping */
+    0,                          /* tp_hash */
+    0,                          /* tp_call */
+    0,                          /* tp_str */
+    PyObject_GenericGetAttr,  /* tp_getattro */
+    0,                          /* tp_setattro */
+    0,                          /* tp_as_buffer */
+    Py_TPFLAGS_DEFAULT,         /* tp_flags */
+    range_doc,                  /* tp_doc */
+    0,                          /* tp_traverse */
+    0,                          /* tp_clear */
+    0,                          /* tp_richcompare */
+    0,                          /* tp_weaklistoffset */
+    range_iter,                 /* tp_iter */
+    0,                          /* tp_iternext */
+    range_methods,              /* tp_methods */
+    0,                          /* tp_members */
+    0,                          /* tp_getset */
+    0,                          /* tp_base */
+    0,                          /* tp_dict */
+    0,                          /* tp_descr_get */
+    0,                          /* tp_descr_set */
+    0,                          /* tp_dictoffset */
+    0,                          /* tp_init */
+    0,                          /* tp_alloc */
+    range_new,                  /* tp_new */
+};
+
+/*********************** Xrange Iterator **************************/
+
+typedef struct {
+    PyObject_HEAD
+    long        index;
+    long        start;
+    long        step;
+    long        len;
+} rangeiterobject;
+
+static PyObject *
+rangeiter_next(rangeiterobject *r)
+{
+    if (r->index < r->len)
+        return PyInt_FromLong(r->start + (r->index++) * r->step);
+    return NULL;
+}
+
+static PyObject *
+rangeiter_len(rangeiterobject *r)
+{
+    return PyInt_FromLong(r->len - r->index);
+}
+
+PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
+
+static PyMethodDef rangeiter_methods[] = {
+    {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},
+    {NULL,              NULL}           /* sentinel */
+};
+
+static PyTypeObject Pyrangeiter_Type = {
+    PyVarObject_HEAD_INIT(&PyType_Type, 0)
+    "rangeiterator",                        /* tp_name */
+    sizeof(rangeiterobject),                /* tp_basicsize */
+    0,                                      /* tp_itemsize */
+    /* methods */
+    (destructor)PyObject_Del,                   /* tp_dealloc */
+    0,                                      /* tp_print */
+    0,                                      /* tp_getattr */
+    0,                                      /* tp_setattr */
+    0,                                      /* tp_compare */
+    0,                                      /* tp_repr */
+    0,                                      /* tp_as_number */
+    0,                                          /* tp_as_sequence */
+    0,                                      /* tp_as_mapping */
+    0,                                      /* tp_hash */
+    0,                                      /* tp_call */
+    0,                                      /* tp_str */
+    PyObject_GenericGetAttr,                /* tp_getattro */
+    0,                                      /* tp_setattro */
+    0,                                      /* tp_as_buffer */
+    Py_TPFLAGS_DEFAULT,                         /* tp_flags */
+    0,                                      /* tp_doc */
+    0,                                          /* tp_traverse */
+    0,                                      /* tp_clear */
+    0,                                      /* tp_richcompare */
+    0,                                      /* tp_weaklistoffset */
+    PyObject_SelfIter,                          /* tp_iter */
+    (iternextfunc)rangeiter_next,               /* tp_iternext */
+    rangeiter_methods,                          /* tp_methods */
+    0,
+};
+
+static PyObject *
+range_iter(PyObject *seq)
+{
+    rangeiterobject *it;
+
+    if (!PyRange_Check(seq)) {
+        PyErr_BadInternalCall();
+        return NULL;
+    }
+    it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
+    if (it == NULL)
+        return NULL;
+    it->index = 0;
+    it->start = ((rangeobject *)seq)->start;
+    it->step = ((rangeobject *)seq)->step;
+    it->len = ((rangeobject *)seq)->len;
+    return (PyObject *)it;
+}
+
+static PyObject *
+range_reverse(PyObject *seq)
+{
+    rangeiterobject *it;
+    long start, step, len;
+
+    if (!PyRange_Check(seq)) {
+        PyErr_BadInternalCall();
+        return NULL;
+    }
+    it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
+    if (it == NULL)
+        return NULL;
+
+    start = ((rangeobject *)seq)->start;
+    step = ((rangeobject *)seq)->step;
+    len = ((rangeobject *)seq)->len;
+
+    it->index = 0;
+    it->len = len;
+    /* the casts below guard against signed overflow by turning it
+       into unsigned overflow instead.  The correctness of this
+       code still depends on conversion from unsigned long to long
+       wrapping modulo ULONG_MAX+1, which isn't guaranteed (see
+       C99 6.3.1.3p3) but seems to hold in practice for all
+       platforms we're likely to meet.
+
+       If step == LONG_MIN then we still end up with LONG_MIN
+       after negation; but this works out, since we've still got
+       the correct value modulo ULONG_MAX+1, and the range_item
+       calculation is also done modulo ULONG_MAX+1.
+    */
+    it->start = (long)(start + (unsigned long)(len-1) * step);
+    it->step = (long)(0UL-step);
+
+    return (PyObject *)it;
+}