/*

Copyright (c) 2013-2015, Facebook, Inc.

All rights reserved.

Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are met:

 * Redistributions of source code must retain the above copyright notice,

   this list of conditions and the following disclaimer.

 * Redistributions in binary form must reproduce the above copyright notice,

   this list of conditions and the following disclaimer in the documentation

   and/or other materials provided with the distribution.

 * Neither the name Facebook nor the names of its contributors may be used to

   endorse or promote products derived from this software without specific

   prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE

FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR

SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER

CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,

OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*/

#include <Python.h>

#ifdef _MSC_VER

#define inline __inline

#include <stdint.h>

#endif

/* Return the smallest size int that can store the value */

#define INT_SIZE(x) (((x) == ((int8_t)x))  ? 1 :    \

                     ((x) == ((int16_t)x)) ? 2 :    \

                     ((x) == ((int32_t)x)) ? 4 : 8)

#define BSER_ARRAY     0x00

#define BSER_OBJECT    0x01

#define BSER_STRING    0x02

#define BSER_INT8      0x03

#define BSER_INT16     0x04

#define BSER_INT32     0x05

#define BSER_INT64     0x06

#define BSER_REAL      0x07

#define BSER_TRUE      0x08

#define BSER_FALSE     0x09

#define BSER_NULL      0x0a

#define BSER_TEMPLATE  0x0b

#define BSER_SKIP      0x0c

// An immutable object representation of BSER_OBJECT.

// Rather than build a hash table, key -> value are obtained

// by walking the list of keys to determine the offset into

// the values array.  The assumption is that the number of

// array elements will be typically small (~6 for the top

// level query result and typically 3-5 for the file entries)

// so that the time overhead for this is small compared to

// using a proper hash table.  Even with this simplistic

// approach, this is still faster for the mercurial use case

// as it helps to eliminate creating N other objects to

// represent the stat information in the hgwatchman extension

typedef struct {

  PyObject_HEAD

  PyObject *keys;   // tuple of field names

  PyObject *values; // tuple of values

} bserObject;

static Py_ssize_t bserobj_tuple_length(PyObject *o) {

  bserObject *obj = (bserObject*)o;

  return PySequence_Length(obj->keys);

}

static PyObject *bserobj_tuple_item(PyObject *o, Py_ssize_t i) {

  bserObject *obj = (bserObject*)o;

  return PySequence_GetItem(obj->values, i);

}

static PySequenceMethods bserobj_sq = {

  bserobj_tuple_length,      /* sq_length */

  0,                         /* sq_concat */

  0,                         /* sq_repeat */

  bserobj_tuple_item,        /* sq_item */

  0,                         /* sq_ass_item */

  0,                         /* sq_contains */

  0,                         /* sq_inplace_concat */

  0                          /* sq_inplace_repeat */

};

static void bserobj_dealloc(PyObject *o) {

  bserObject *obj = (bserObject*)o;

  Py_CLEAR(obj->keys);

  Py_CLEAR(obj->values);

  PyObject_Del(o);

}

static PyObject *bserobj_getattrro(PyObject *o, PyObject *name) {

  bserObject *obj = (bserObject*)o;

  Py_ssize_t i, n;

  const char *namestr;

  if (PyIndex_Check(name)) {

    i = PyNumber_AsSsize_t(name, PyExc_IndexError);

    if (i == -1 && PyErr_Occurred()) {

      return NULL;

    }

    return PySequence_GetItem(obj->values, i);

  }

  // hack^Wfeature to allow mercurial to use "st_size" to reference "size"

  namestr = PyString_AsString(name);

  if (!strncmp(namestr, "st_", 3)) {

    namestr += 3;

  }

  n = PyTuple_GET_SIZE(obj->keys);

  for (i = 0; i < n; i++) {

    const char *item_name = NULL;

    PyObject *key = PyTuple_GET_ITEM(obj->keys, i);

    item_name = PyString_AsString(key);

    if (!strcmp(item_name, namestr)) {

      return PySequence_GetItem(obj->values, i);

    }

  }

  PyErr_Format(PyExc_AttributeError,

              "bserobject has no attribute '%.400s'", namestr);

  return NULL;

}

static PyMappingMethods bserobj_map = {

  bserobj_tuple_length,     /* mp_length */

  bserobj_getattrro,        /* mp_subscript */

  0                         /* mp_ass_subscript */

};

PyTypeObject bserObjectType = {

  PyVarObject_HEAD_INIT(NULL, 0)

  "bserobj_tuple",           /* tp_name */

  sizeof(bserObject),        /* tp_basicsize */

  0,                         /* tp_itemsize */

  bserobj_dealloc,           /* tp_dealloc */

  0,                         /* tp_print */

  0,                         /* tp_getattr */

  0,                         /* tp_setattr */

  0,                         /* tp_compare */

  0,                         /* tp_repr */

  0,                         /* tp_as_number */

  &bserobj_sq,               /* tp_as_sequence */

  &bserobj_map,              /* tp_as_mapping */

  0,                         /* tp_hash  */

  0,                         /* tp_call */

  0,                         /* tp_str */

  bserobj_getattrro,         /* tp_getattro */

  0,                         /* tp_setattro */

  0,                         /* tp_as_buffer */

  Py_TPFLAGS_DEFAULT,        /* tp_flags */

  "bserobj tuple",           /* tp_doc */

  0,                         /* tp_traverse */

  0,                         /* tp_clear */

  0,                         /* tp_richcompare */

  0,                         /* tp_weaklistoffset */

  0,                         /* tp_iter */

  0,                         /* tp_iternext */

  0,                         /* 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 */

  0,                         /* tp_new */

};

static PyObject *bser_loads_recursive(const char **ptr, const char *end,

    int mutable);

static const char bser_true = BSER_TRUE;

static const char bser_false = BSER_FALSE;

static const char bser_null = BSER_NULL;

static const char bser_string_hdr = BSER_STRING;

static const char bser_array_hdr = BSER_ARRAY;

static const char bser_object_hdr = BSER_OBJECT;

static inline uint32_t next_power_2(uint32_t n)

{

  n |= (n >> 16);

  n |= (n >> 8);

  n |= (n >> 4);

  n |= (n >> 2);

  n |= (n >> 1);

  return n + 1;

}

// A buffer we use for building up the serialized result

struct bser_buffer {

  char *buf;

  int wpos, allocd;

};

typedef struct bser_buffer bser_t;

static int bser_append(bser_t *bser, const char *data, uint32_t len)

{

  int newlen = next_power_2(bser->wpos + len);

  if (newlen > bser->allocd) {

    char *nbuf = realloc(bser->buf, newlen);

    if (!nbuf) {

      return 0;

    }

    bser->buf = nbuf;

    bser->allocd = newlen;

  }

  memcpy(bser->buf + bser->wpos, data, len);

  bser->wpos += len;

  return 1;

}

static int bser_init(bser_t *bser)

{

  bser->allocd = 8192;

  bser->wpos = 0;

  bser->buf = malloc(bser->allocd);

  if (!bser->buf) {

    return 0;

  }

  // Leave room for the serialization header, which includes

  // our overall length.  To make things simpler, we'll use an

  // int32 for the header

#define EMPTY_HEADER "\x00\x01\x05\x00\x00\x00\x00"

  bser_append(bser, EMPTY_HEADER, sizeof(EMPTY_HEADER)-1);

  return 1;

}

static void bser_dtor(bser_t *bser)

{

  free(bser->buf);

  bser->buf = NULL;

}

static int bser_long(bser_t *bser, int64_t val)

{

  int8_t i8;

  int16_t i16;

  int32_t i32;

  int64_t i64;

  char sz;

  int size = INT_SIZE(val);

  char *iptr;

  switch (size) {

    case 1:

      sz = BSER_INT8;

      i8 = (int8_t)val;

      iptr = (char*)&i8;

      break;

    case 2:

      sz = BSER_INT16;

      i16 = (int16_t)val;

      iptr = (char*)&i16;

      break;

    case 4:

      sz = BSER_INT32;

      i32 = (int32_t)val;

      iptr = (char*)&i32;

      break;

    case 8:

      sz = BSER_INT64;

      i64 = (int64_t)val;

      iptr = (char*)&i64;

      break;

    default:

      PyErr_SetString(PyExc_RuntimeError,

          "Cannot represent this long value!?");

      return 0;

  }

  if (!bser_append(bser, &sz, sizeof(sz))) {

    return 0;

  }

  return bser_append(bser, iptr, size);

}

static int bser_string(bser_t *bser, PyObject *sval)

{

  char *buf = NULL;

  Py_ssize_t len;

  int res;

  PyObject *utf = NULL;

  if (PyUnicode_Check(sval)) {

    utf = PyUnicode_AsEncodedString(sval, "utf-8", "ignore");

    sval = utf;

  }

  res = PyString_AsStringAndSize(sval, &buf, &len);

  if (res == -1) {

    res = 0;

    goto out;

  }

  if (!bser_append(bser, &bser_string_hdr, sizeof(bser_string_hdr))) {

    res = 0;

    goto out;

  }

  if (!bser_long(bser, len)) {

    res = 0;

    goto out;

  }

  if (len > UINT32_MAX) {

    PyErr_Format(PyExc_ValueError, "string too big");

    res = 0;

    goto out;

  }

  res = bser_append(bser, buf, (uint32_t)len);

out:

  if (utf) {

    Py_DECREF(utf);

  }

  return res;

}

static int bser_recursive(bser_t *bser, PyObject *val)

{

  if (PyBool_Check(val)) {

    if (val == Py_True) {

      return bser_append(bser, &bser_true, sizeof(bser_true));

    }

    return bser_append(bser, &bser_false, sizeof(bser_false));

  }

  if (val == Py_None) {

    return bser_append(bser, &bser_null, sizeof(bser_null));

  }

  if (PyInt_Check(val)) {

    return bser_long(bser, PyInt_AS_LONG(val));

  }

  if (PyLong_Check(val)) {

    return bser_long(bser, PyLong_AsLongLong(val));

  }

  if (PyString_Check(val) || PyUnicode_Check(val)) {

    return bser_string(bser, val);

  }

  if (PyFloat_Check(val)) {

    double dval = PyFloat_AS_DOUBLE(val);

    char sz = BSER_REAL;

    if (!bser_append(bser, &sz, sizeof(sz))) {

      return 0;

    }

    return bser_append(bser, (char*)&dval, sizeof(dval));

  }

  if (PyList_Check(val)) {

    Py_ssize_t i, len = PyList_GET_SIZE(val);

    if (!bser_append(bser, &bser_array_hdr, sizeof(bser_array_hdr))) {

      return 0;

    }

    if (!bser_long(bser, len)) {

      return 0;

    }

    for (i = 0; i < len; i++) {

      PyObject *ele = PyList_GET_ITEM(val, i);

      if (!bser_recursive(bser, ele)) {

        return 0;

      }

    }

    return 1;

  }

  if (PyTuple_Check(val)) {

    Py_ssize_t i, len = PyTuple_GET_SIZE(val);

    if (!bser_append(bser, &bser_array_hdr, sizeof(bser_array_hdr))) {

      return 0;

    }

    if (!bser_long(bser, len)) {

      return 0;

    }

    for (i = 0; i < len; i++) {

      PyObject *ele = PyTuple_GET_ITEM(val, i);

      if (!bser_recursive(bser, ele)) {

        return 0;

      }

    }

    return 1;

  }

  if (PyMapping_Check(val)) {