projects.mako.cc - wikipedia-api-cdsw/blob - simplejson/_speedups.c

   1 /* -*- mode: C; c-file-style: "python"; c-basic-offset: 4 -*- */
   2 #include "Python.h"
   3 #include "structmember.h"
   4
   5 #if PY_MAJOR_VERSION >= 3
   6 #define PyInt_FromSsize_t PyLong_FromSsize_t
   7 #define PyInt_AsSsize_t PyLong_AsSsize_t
   8 #define PyString_Check PyBytes_Check
   9 #define PyString_GET_SIZE PyBytes_GET_SIZE
  10 #define PyString_AS_STRING PyBytes_AS_STRING
  11 #define PyString_FromStringAndSize PyBytes_FromStringAndSize
  12 #define PyInt_Check(obj) 0
  13 #define JSON_UNICHR Py_UCS4
  14 #define JSON_InternFromString PyUnicode_InternFromString
  15 #define JSON_Intern_GET_SIZE PyUnicode_GET_SIZE
  16 #define JSON_ASCII_Check PyUnicode_Check
  17 #define JSON_ASCII_AS_STRING PyUnicode_AsUTF8
  18 #define PyInt_Type PyLong_Type
  19 #define PyInt_FromString PyLong_FromString
  20 #define PY2_UNUSED
  21 #define PY3_UNUSED UNUSED
  22 #define JSON_NewEmptyUnicode() PyUnicode_New(0, 127)
  23 #else /* PY_MAJOR_VERSION >= 3 */
  24 #define PY2_UNUSED UNUSED
  25 #define PY3_UNUSED
  26 #define PyUnicode_READY(obj) 0
  27 #define PyUnicode_KIND(obj) (sizeof(Py_UNICODE))
  28 #define PyUnicode_DATA(obj) ((void *)(PyUnicode_AS_UNICODE(obj)))
  29 #define PyUnicode_READ(kind, data, index) ((JSON_UNICHR)((const Py_UNICODE *)(data))[(index)])
  30 #define PyUnicode_GetLength PyUnicode_GET_SIZE
  31 #define JSON_UNICHR Py_UNICODE
  32 #define JSON_ASCII_Check PyString_Check
  33 #define JSON_ASCII_AS_STRING PyString_AS_STRING
  34 #define JSON_InternFromString PyString_InternFromString
  35 #define JSON_Intern_GET_SIZE PyString_GET_SIZE
  36 #define JSON_NewEmptyUnicode() PyUnicode_FromUnicode(NULL, 0)
  37 #endif /* PY_MAJOR_VERSION < 3 */
  38
  39 #if PY_VERSION_HEX < 0x02070000
  40 #if !defined(PyOS_string_to_double)
  41 #define PyOS_string_to_double json_PyOS_string_to_double
  42 static double
  43 json_PyOS_string_to_double(const char *s, char **endptr, PyObject *overflow_exception);
  44 static double
  45 json_PyOS_string_to_double(const char *s, char **endptr, PyObject *overflow_exception)
  46 {
  47     double x;
  48     assert(endptr == NULL);
  49     assert(overflow_exception == NULL);
  50     PyFPE_START_PROTECT("json_PyOS_string_to_double", return -1.0;)
  51     x = PyOS_ascii_atof(s);
  52     PyFPE_END_PROTECT(x)
  53     return x;
  54 }
  55 #endif
  56 #endif /* PY_VERSION_HEX < 0x02070000 */
  57
  58 #if PY_VERSION_HEX < 0x02060000
  59 #if !defined(Py_TYPE)
  60 #define Py_TYPE(ob)     (((PyObject*)(ob))->ob_type)
  61 #endif
  62 #if !defined(Py_SIZE)
  63 #define Py_SIZE(ob)     (((PyVarObject*)(ob))->ob_size)
  64 #endif
  65 #if !defined(PyVarObject_HEAD_INIT)
  66 #define PyVarObject_HEAD_INIT(type, size) PyObject_HEAD_INIT(type) size,
  67 #endif
  68 #endif /* PY_VERSION_HEX < 0x02060000 */
  69
  70 #if PY_VERSION_HEX < 0x02050000
  71 #if !defined(PY_SSIZE_T_MIN)
  72 typedef int Py_ssize_t;
  73 #define PY_SSIZE_T_MAX INT_MAX
  74 #define PY_SSIZE_T_MIN INT_MIN
  75 #define PyInt_FromSsize_t PyInt_FromLong
  76 #define PyInt_AsSsize_t PyInt_AsLong
  77 #endif
  78 #if !defined(Py_IS_FINITE)
  79 #define Py_IS_FINITE(X) (!Py_IS_INFINITY(X) && !Py_IS_NAN(X))
  80 #endif
  81 #endif /* PY_VERSION_HEX < 0x02050000 */
  82
  83 #ifdef __GNUC__
  84 #define UNUSED __attribute__((__unused__))
  85 #else
  86 #define UNUSED
  87 #endif
  88
  89 #define DEFAULT_ENCODING "utf-8"
  90
  91 #define PyScanner_Check(op) PyObject_TypeCheck(op, &PyScannerType)
  92 #define PyScanner_CheckExact(op) (Py_TYPE(op) == &PyScannerType)
  93 #define PyEncoder_Check(op) PyObject_TypeCheck(op, &PyEncoderType)
  94 #define PyEncoder_CheckExact(op) (Py_TYPE(op) == &PyEncoderType)
  95
  96 #define JSON_ALLOW_NAN 1
  97 #define JSON_IGNORE_NAN 2
  98
  99 static PyTypeObject PyScannerType;
 100 static PyTypeObject PyEncoderType;
 101
 102 typedef struct {
 103     PyObject *large_strings;  /* A list of previously accumulated large strings */
 104     PyObject *small_strings;  /* Pending small strings */
 105 } JSON_Accu;
 106
 107 static int
 108 JSON_Accu_Init(JSON_Accu *acc);
 109 static int
 110 JSON_Accu_Accumulate(JSON_Accu *acc, PyObject *unicode);
 111 static PyObject *
 112 JSON_Accu_FinishAsList(JSON_Accu *acc);
 113 static void
 114 JSON_Accu_Destroy(JSON_Accu *acc);
 115
 116 #define ERR_EXPECTING_VALUE "Expecting value"
 117 #define ERR_ARRAY_DELIMITER "Expecting ',' delimiter or ']'"
 118 #define ERR_ARRAY_VALUE_FIRST "Expecting value or ']'"
 119 #define ERR_OBJECT_DELIMITER "Expecting ',' delimiter or '}'"
 120 #define ERR_OBJECT_PROPERTY "Expecting property name enclosed in double quotes"
 121 #define ERR_OBJECT_PROPERTY_FIRST "Expecting property name enclosed in double quotes or '}'"
 122 #define ERR_OBJECT_PROPERTY_DELIMITER "Expecting ':' delimiter"
 123 #define ERR_STRING_UNTERMINATED "Unterminated string starting at"
 124 #define ERR_STRING_CONTROL "Invalid control character %r at"
 125 #define ERR_STRING_ESC1 "Invalid \\X escape sequence %r"
 126 #define ERR_STRING_ESC4 "Invalid \\uXXXX escape sequence"
 127
 128 typedef struct _PyScannerObject {
 129     PyObject_HEAD
 130     PyObject *encoding;
 131     PyObject *strict;
 132     PyObject *object_hook;
 133     PyObject *pairs_hook;
 134     PyObject *parse_float;
 135     PyObject *parse_int;
 136     PyObject *parse_constant;
 137     PyObject *memo;
 138 } PyScannerObject;
 139
 140 static PyMemberDef scanner_members[] = {
 141     {"encoding", T_OBJECT, offsetof(PyScannerObject, encoding), READONLY, "encoding"},
 142     {"strict", T_OBJECT, offsetof(PyScannerObject, strict), READONLY, "strict"},
 143     {"object_hook", T_OBJECT, offsetof(PyScannerObject, object_hook), READONLY, "object_hook"},
 144     {"object_pairs_hook", T_OBJECT, offsetof(PyScannerObject, pairs_hook), READONLY, "object_pairs_hook"},
 145     {"parse_float", T_OBJECT, offsetof(PyScannerObject, parse_float), READONLY, "parse_float"},
 146     {"parse_int", T_OBJECT, offsetof(PyScannerObject, parse_int), READONLY, "parse_int"},
 147     {"parse_constant", T_OBJECT, offsetof(PyScannerObject, parse_constant), READONLY, "parse_constant"},
 148     {NULL}
 149 };
 150
 151 typedef struct _PyEncoderObject {
 152     PyObject_HEAD
 153     PyObject *markers;
 154     PyObject *defaultfn;
 155     PyObject *encoder;
 156     PyObject *indent;
 157     PyObject *key_separator;
 158     PyObject *item_separator;
 159     PyObject *sort_keys;
 160     PyObject *key_memo;
 161     PyObject *encoding;
 162     PyObject *Decimal;
 163     PyObject *skipkeys_bool;
 164     int skipkeys;
 165     int fast_encode;
 166     /* 0, JSON_ALLOW_NAN, JSON_IGNORE_NAN */
 167     int allow_or_ignore_nan;
 168     int use_decimal;
 169     int namedtuple_as_object;
 170     int tuple_as_array;
 171     int bigint_as_string;
 172     PyObject *item_sort_key;
 173     PyObject *item_sort_kw;
 174     int for_json;
 175 } PyEncoderObject;
 176
 177 static PyMemberDef encoder_members[] = {
 178     {"markers", T_OBJECT, offsetof(PyEncoderObject, markers), READONLY, "markers"},
 179     {"default", T_OBJECT, offsetof(PyEncoderObject, defaultfn), READONLY, "default"},
 180     {"encoder", T_OBJECT, offsetof(PyEncoderObject, encoder), READONLY, "encoder"},
 181     {"encoding", T_OBJECT, offsetof(PyEncoderObject, encoder), READONLY, "encoding"},
 182     {"indent", T_OBJECT, offsetof(PyEncoderObject, indent), READONLY, "indent"},
 183     {"key_separator", T_OBJECT, offsetof(PyEncoderObject, key_separator), READONLY, "key_separator"},
 184     {"item_separator", T_OBJECT, offsetof(PyEncoderObject, item_separator), READONLY, "item_separator"},
 185     {"sort_keys", T_OBJECT, offsetof(PyEncoderObject, sort_keys), READONLY, "sort_keys"},
 186     /* Python 2.5 does not support T_BOOl */
 187     {"skipkeys", T_OBJECT, offsetof(PyEncoderObject, skipkeys_bool), READONLY, "skipkeys"},
 188     {"key_memo", T_OBJECT, offsetof(PyEncoderObject, key_memo), READONLY, "key_memo"},
 189     {"item_sort_key", T_OBJECT, offsetof(PyEncoderObject, item_sort_key), READONLY, "item_sort_key"},
 190     {NULL}
 191 };
 192
 193 static PyObject *
 194 join_list_unicode(PyObject *lst);
 195 static PyObject *
 196 JSON_ParseEncoding(PyObject *encoding);
 197 static PyObject *
 198 JSON_UnicodeFromChar(JSON_UNICHR c);
 199 static PyObject *
 200 maybe_quote_bigint(PyObject *encoded, PyObject *obj);
 201 static Py_ssize_t
 202 ascii_char_size(JSON_UNICHR c);
 203 static Py_ssize_t
 204 ascii_escape_char(JSON_UNICHR c, char *output, Py_ssize_t chars);
 205 static PyObject *
 206 ascii_escape_unicode(PyObject *pystr);
 207 static PyObject *
 208 ascii_escape_str(PyObject *pystr);
 209 static PyObject *
 210 py_encode_basestring_ascii(PyObject* self UNUSED, PyObject *pystr);
 211 #if PY_MAJOR_VERSION < 3
 212 static PyObject *
 213 join_list_string(PyObject *lst);
 214 static PyObject *
 215 scan_once_str(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr);
 216 static PyObject *
 217 scanstring_str(PyObject *pystr, Py_ssize_t end, char *encoding, int strict, Py_ssize_t *next_end_ptr);
 218 static PyObject *
 219 _parse_object_str(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr);
 220 #endif
 221 static PyObject *
 222 scanstring_unicode(PyObject *pystr, Py_ssize_t end, int strict, Py_ssize_t *next_end_ptr);
 223 static PyObject *
 224 scan_once_unicode(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr);
 225 static PyObject *
 226 _build_rval_index_tuple(PyObject *rval, Py_ssize_t idx);
 227 static PyObject *
 228 scanner_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
 229 static int
 230 scanner_init(PyObject *self, PyObject *args, PyObject *kwds);
 231 static void
 232 scanner_dealloc(PyObject *self);
 233 static int
 234 scanner_clear(PyObject *self);
 235 static PyObject *
 236 encoder_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
 237 static int
 238 encoder_init(PyObject *self, PyObject *args, PyObject *kwds);
 239 static void
 240 encoder_dealloc(PyObject *self);
 241 static int
 242 encoder_clear(PyObject *self);
 243 static PyObject *
 244 encoder_stringify_key(PyEncoderObject *s, PyObject *key);
 245 static int
 246 encoder_listencode_list(PyEncoderObject *s, JSON_Accu *rval, PyObject *seq, Py_ssize_t indent_level);
 247 static int
 248 encoder_listencode_obj(PyEncoderObject *s, JSON_Accu *rval, PyObject *obj, Py_ssize_t indent_level);
 249 static int
 250 encoder_listencode_dict(PyEncoderObject *s, JSON_Accu *rval, PyObject *dct, Py_ssize_t indent_level);
 251 static PyObject *
 252 _encoded_const(PyObject *obj);
 253 static void
 254 raise_errmsg(char *msg, PyObject *s, Py_ssize_t end);
 255 static PyObject *
 256 encoder_encode_string(PyEncoderObject *s, PyObject *obj);
 257 static int
 258 _convertPyInt_AsSsize_t(PyObject *o, Py_ssize_t *size_ptr);
 259 static PyObject *
 260 _convertPyInt_FromSsize_t(Py_ssize_t *size_ptr);
 261 static PyObject *
 262 encoder_encode_float(PyEncoderObject *s, PyObject *obj);
 263 static int
 264 _is_namedtuple(PyObject *obj);
 265 static int
 266 _has_for_json_hook(PyObject *obj);
 267 static PyObject *
 268 moduleinit(void);
 269
 270 #define S_CHAR(c) (c >= ' ' && c <= '~' && c != '\\' && c != '"')
 271 #define IS_WHITESPACE(c) (((c) == ' ') || ((c) == '\t') || ((c) == '\n') || ((c) == '\r'))
 272
 273 #define MIN_EXPANSION 6
 274
 275 static int
 276 JSON_Accu_Init(JSON_Accu *acc)
 277 {
 278     /* Lazily allocated */
 279     acc->large_strings = NULL;
 280     acc->small_strings = PyList_New(0);
 281     if (acc->small_strings == NULL)
 282         return -1;
 283     return 0;
 284 }
 285
 286 static int
 287 flush_accumulator(JSON_Accu *acc)
 288 {
 289     Py_ssize_t nsmall = PyList_GET_SIZE(acc->small_strings);
 290     if (nsmall) {
 291         int ret;
 292         PyObject *joined;
 293         if (acc->large_strings == NULL) {
 294             acc->large_strings = PyList_New(0);
 295             if (acc->large_strings == NULL)
 296                 return -1;
 297         }
 298 #if PY_MAJOR_VERSION >= 3
 299         joined = join_list_unicode(acc->small_strings);
 300 #else /* PY_MAJOR_VERSION >= 3 */
 301         joined = join_list_string(acc->small_strings);
 302 #endif /* PY_MAJOR_VERSION < 3 */
 303         if (joined == NULL)
 304             return -1;
 305         if (PyList_SetSlice(acc->small_strings, 0, nsmall, NULL)) {
 306             Py_DECREF(joined);
 307             return -1;
 308         }
 309         ret = PyList_Append(acc->large_strings, joined);
 310         Py_DECREF(joined);
 311         return ret;
 312     }
 313     return 0;
 314 }
 315
 316 static int
 317 JSON_Accu_Accumulate(JSON_Accu *acc, PyObject *unicode)
 318 {
 319     Py_ssize_t nsmall;
 320 #if PY_MAJOR_VERSION >= 3
 321     assert(PyUnicode_Check(unicode));
 322 #else /* PY_MAJOR_VERSION >= 3 */
 323     assert(JSON_ASCII_Check(unicode) || PyUnicode_Check(unicode));
 324 #endif /* PY_MAJOR_VERSION < 3 */
 325
 326     if (PyList_Append(acc->small_strings, unicode))
 327         return -1;
 328     nsmall = PyList_GET_SIZE(acc->small_strings);
 329     /* Each item in a list of unicode objects has an overhead (in 64-bit
 330      * builds) of:
 331      *   - 8 bytes for the list slot
 332      *   - 56 bytes for the header of the unicode object
 333      * that is, 64 bytes.  100000 such objects waste more than 6MB
 334      * compared to a single concatenated string.
 335      */
 336     if (nsmall < 100000)
 337         return 0;
 338     return flush_accumulator(acc);
 339 }
 340
 341 static PyObject *
 342 JSON_Accu_FinishAsList(JSON_Accu *acc)
 343 {
 344     int ret;
 345     PyObject *res;
 346
 347     ret = flush_accumulator(acc);
 348     Py_CLEAR(acc->small_strings);
 349     if (ret) {
 350         Py_CLEAR(acc->large_strings);
 351         return NULL;
 352     }
 353     res = acc->large_strings;
 354     acc->large_strings = NULL;
 355     if (res == NULL)
 356         return PyList_New(0);
 357     return res;
 358 }
 359
 360 static void
 361 JSON_Accu_Destroy(JSON_Accu *acc)
 362 {
 363     Py_CLEAR(acc->small_strings);
 364     Py_CLEAR(acc->large_strings);
 365 }
 366
 367 static int
 368 IS_DIGIT(JSON_UNICHR c)
 369 {
 370     return c >= '0' && c <= '9';
 371 }
 372
 373 static PyObject *
 374 JSON_UnicodeFromChar(JSON_UNICHR c)
 375 {
 376 #if PY_MAJOR_VERSION >= 3
 377     PyObject *rval = PyUnicode_New(1, c);
 378     if (rval)
 379         PyUnicode_WRITE(PyUnicode_KIND(rval), PyUnicode_DATA(rval), 0, c);
 380     return rval;
 381 #else /* PY_MAJOR_VERSION >= 3 */
 382     return PyUnicode_FromUnicode(&c, 1);
 383 #endif /* PY_MAJOR_VERSION < 3 */
 384 }
 385
 386 static PyObject *
 387 maybe_quote_bigint(PyObject *encoded, PyObject *obj)
 388 {
 389     static PyObject *big_long = NULL;
 390     static PyObject *small_long = NULL;
 391     if (big_long == NULL) {
 392         big_long = PyLong_FromLongLong(1LL << 53);
 393         if (big_long == NULL) {
 394             Py_DECREF(encoded);
 395             return NULL;
 396         }
 397     }
 398     if (small_long == NULL) {
 399         small_long = PyLong_FromLongLong(-1LL << 53);
 400         if (small_long == NULL) {
 401             Py_DECREF(encoded);
 402             return NULL;
 403         }
 404     }
 405     if (PyObject_RichCompareBool(obj, big_long, Py_GE) ||
 406         PyObject_RichCompareBool(obj, small_long, Py_LE)) {
 407 #if PY_MAJOR_VERSION >= 3
 408         PyObject* quoted = PyUnicode_FromFormat("\"%U\"", encoded);
 409 #else
 410         PyObject* quoted = PyString_FromFormat("\"%s\"",
 411                                                PyString_AsString(encoded));
 412 #endif
 413         Py_DECREF(encoded);
 414         encoded = quoted;
 415     }
 416     return encoded;
 417 }
 418
 419 static int
 420 _is_namedtuple(PyObject *obj)
 421 {
 422     int rval = 0;
 423     PyObject *_asdict = PyObject_GetAttrString(obj, "_asdict");
 424     if (_asdict == NULL) {
 425         PyErr_Clear();
 426         return 0;
 427     }
 428     rval = PyCallable_Check(_asdict);
 429     Py_DECREF(_asdict);
 430     return rval;
 431 }
 432
 433 static int
 434 _has_for_json_hook(PyObject *obj)
 435 {
 436     int rval = 0;
 437     PyObject *for_json = PyObject_GetAttrString(obj, "for_json");
 438     if (for_json == NULL) {
 439         PyErr_Clear();
 440         return 0;
 441     }
 442     rval = PyCallable_Check(for_json);
 443     Py_DECREF(for_json);
 444     return rval;
 445 }
 446
 447 static int
 448 _convertPyInt_AsSsize_t(PyObject *o, Py_ssize_t *size_ptr)
 449 {
 450     /* PyObject to Py_ssize_t converter */
 451     *size_ptr = PyInt_AsSsize_t(o);
 452     if (*size_ptr == -1 && PyErr_Occurred())
 453         return 0;
 454     return 1;
 455 }
 456
 457 static PyObject *
 458 _convertPyInt_FromSsize_t(Py_ssize_t *size_ptr)
 459 {
 460     /* Py_ssize_t to PyObject converter */
 461     return PyInt_FromSsize_t(*size_ptr);
 462 }
 463
 464 static Py_ssize_t
 465 ascii_escape_char(JSON_UNICHR c, char *output, Py_ssize_t chars)
 466 {
 467     /* Escape unicode code point c to ASCII escape sequences
 468     in char *output. output must have at least 12 bytes unused to
 469     accommodate an escaped surrogate pair "\uXXXX\uXXXX" */
 470     if (S_CHAR(c)) {
 471         output[chars++] = (char)c;
 472     }
 473     else {
 474         output[chars++] = '\\';
 475         switch (c) {
 476             case '\\': output[chars++] = (char)c; break;
 477             case '"': output[chars++] = (char)c; break;
 478             case '\b': output[chars++] = 'b'; break;
 479             case '\f': output[chars++] = 'f'; break;
 480             case '\n': output[chars++] = 'n'; break;
 481             case '\r': output[chars++] = 'r'; break;
 482             case '\t': output[chars++] = 't'; break;
 483             default:
 484 #if defined(Py_UNICODE_WIDE) || PY_MAJOR_VERSION >= 3
 485                 if (c >= 0x10000) {
 486                     /* UTF-16 surrogate pair */
 487                     JSON_UNICHR v = c - 0x10000;
 488                     c = 0xd800 | ((v >> 10) & 0x3ff);
 489                     output[chars++] = 'u';
 490                     output[chars++] = "0123456789abcdef"[(c >> 12) & 0xf];
 491                     output[chars++] = "0123456789abcdef"[(c >>  8) & 0xf];
 492                     output[chars++] = "0123456789abcdef"[(c >>  4) & 0xf];
 493                     output[chars++] = "0123456789abcdef"[(c      ) & 0xf];
 494                     c = 0xdc00 | (v & 0x3ff);
 495                     output[chars++] = '\\';
 496                 }
 497 #endif
 498                 output[chars++] = 'u';
 499                 output[chars++] = "0123456789abcdef"[(c >> 12) & 0xf];
 500                 output[chars++] = "0123456789abcdef"[(c >>  8) & 0xf];
 501                 output[chars++] = "0123456789abcdef"[(c >>  4) & 0xf];
 502                 output[chars++] = "0123456789abcdef"[(c      ) & 0xf];
 503         }
 504     }
 505     return chars;
 506 }
 507
 508 static Py_ssize_t
 509 ascii_char_size(JSON_UNICHR c)
 510 {
 511     if (S_CHAR(c)) {
 512         return 1;
 513     }
 514     else if (c == '\\' ||
 515                c == '"'  ||
 516                c == '\b' ||
 517                c == '\f' ||
 518                c == '\n' ||
 519                c == '\r' ||
 520                c == '\t') {
 521         return 2;
 522     }
 523 #if defined(Py_UNICODE_WIDE) || PY_MAJOR_VERSION >= 3
 524     else if (c >= 0x10000U) {
 525         return 2 * MIN_EXPANSION;
 526     }
 527 #endif
 528     else {
 529         return MIN_EXPANSION;
 530     }
 531 }
 532
 533 static PyObject *
 534 ascii_escape_unicode(PyObject *pystr)
 535 {
 536     /* Take a PyUnicode pystr and return a new ASCII-only escaped PyString */
 537     Py_ssize_t i;
 538     Py_ssize_t input_chars;
 539     Py_ssize_t output_size;
 540     Py_ssize_t chars;
 541     PY2_UNUSED int kind;
 542     void *data;
 543     PyObject *rval;
 544     char *output;
 545
 546     if (PyUnicode_READY(pystr))
 547         return NULL;
 548
 549     kind = PyUnicode_KIND(pystr);
 550     data = PyUnicode_DATA(pystr);
 551     input_chars = PyUnicode_GetLength(pystr);
 552     output_size = 2;
 553     for (i = 0; i < input_chars; i++) {
 554         output_size += ascii_char_size(PyUnicode_READ(kind, data, i));
 555     }
 556 #if PY_MAJOR_VERSION >= 3
 557     rval = PyUnicode_New(output_size, 127);
 558     if (rval == NULL) {
 559         return NULL;
 560     }
 561     assert(PyUnicode_KIND(rval) == PyUnicode_1BYTE_KIND);
 562     output = (char *)PyUnicode_DATA(rval);
 563 #else
 564     rval = PyString_FromStringAndSize(NULL, output_size);
 565     if (rval == NULL) {
 566         return NULL;
 567     }
 568     output = PyString_AS_STRING(rval);
 569 #endif
 570     chars = 0;
 571     output[chars++] = '"';
 572     for (i = 0; i < input_chars; i++) {
 573         chars = ascii_escape_char(PyUnicode_READ(kind, data, i), output, chars);
 574     }
 575     output[chars++] = '"';
 576     assert(chars == output_size);
 577     return rval;
 578 }
 579
 580 #if PY_MAJOR_VERSION >= 3
 581
 582 static PyObject *
 583 ascii_escape_str(PyObject *pystr)
 584 {
 585     PyObject *rval;
 586     PyObject *input = PyUnicode_DecodeUTF8(PyString_AS_STRING(pystr), PyString_GET_SIZE(pystr), NULL);
 587     if (input == NULL)
 588         return NULL;
 589     rval = ascii_escape_unicode(input);
 590     Py_DECREF(input);
 591     return rval;
 592 }
 593
 594 #else /* PY_MAJOR_VERSION >= 3 */
 595
 596 static PyObject *
 597 ascii_escape_str(PyObject *pystr)
 598 {
 599     /* Take a PyString pystr and return a new ASCII-only escaped PyString */
 600     Py_ssize_t i;
 601     Py_ssize_t input_chars;
 602     Py_ssize_t output_size;
 603     Py_ssize_t chars;
 604     PyObject *rval;
 605     char *output;
 606     char *input_str;
 607
 608     input_chars = PyString_GET_SIZE(pystr);
 609     input_str = PyString_AS_STRING(pystr);
 610     output_size = 2;
 611
 612     /* Fast path for a string that's already ASCII */
 613     for (i = 0; i < input_chars; i++) {
 614         JSON_UNICHR c = (JSON_UNICHR)input_str[i];
 615         if (c > 0x7f) {
 616             /* We hit a non-ASCII character, bail to unicode mode */
 617             PyObject *uni;
 618             uni = PyUnicode_DecodeUTF8(input_str, input_chars, "strict");
 619             if (uni == NULL) {
 620                 return NULL;
 621             }
 622             rval = ascii_escape_unicode(uni);
 623             Py_DECREF(uni);
 624             return rval;
 625         }
 626         output_size += ascii_char_size(c);
 627     }
 628
 629     rval = PyString_FromStringAndSize(NULL, output_size);
 630     if (rval == NULL) {
 631         return NULL;
 632     }
 633     chars = 0;
 634     output = PyString_AS_STRING(rval);
 635     output[chars++] = '"';
 636     for (i = 0; i < input_chars; i++) {
 637         chars = ascii_escape_char((JSON_UNICHR)input_str[i], output, chars);
 638     }
 639     output[chars++] = '"';
 640     assert(chars == output_size);
 641     return rval;
 642 }
 643 #endif /* PY_MAJOR_VERSION < 3 */
 644
 645 static PyObject *
 646 encoder_stringify_key(PyEncoderObject *s, PyObject *key)
 647 {
 648     if (PyUnicode_Check(key)) {
 649         Py_INCREF(key);
 650         return key;
 651     }
 652     else if (PyString_Check(key)) {
 653 #if PY_MAJOR_VERSION >= 3
 654         return PyUnicode_Decode(
 655             PyString_AS_STRING(key),
 656             PyString_GET_SIZE(key),
 657             JSON_ASCII_AS_STRING(s->encoding),
 658             NULL);
 659 #else /* PY_MAJOR_VERSION >= 3 */
 660         Py_INCREF(key);
 661         return key;
 662 #endif /* PY_MAJOR_VERSION < 3 */
 663     }
 664     else if (PyFloat_Check(key)) {
 665         return encoder_encode_float(s, key);
 666     }
 667     else if (key == Py_True || key == Py_False || key == Py_None) {
 668         /* This must come before the PyInt_Check because
 669            True and False are also 1 and 0.*/
 670         return _encoded_const(key);
 671     }
 672     else if (PyInt_Check(key) || PyLong_Check(key)) {
 673         return PyObject_Str(key);
 674     }
 675     else if (s->use_decimal && PyObject_TypeCheck(key, (PyTypeObject *)s->Decimal)) {
 676         return PyObject_Str(key);
 677     }
 678     else if (s->skipkeys) {
 679         Py_INCREF(Py_None);
 680         return Py_None;
 681     }
 682     PyErr_SetString(PyExc_TypeError, "keys must be a string");
 683     return NULL;
 684 }
 685
 686 static PyObject *
 687 encoder_dict_iteritems(PyEncoderObject *s, PyObject *dct)
 688 {
 689     PyObject *items;
 690     PyObject *iter = NULL;
 691     PyObject *lst = NULL;
 692     PyObject *item = NULL;
 693     PyObject *kstr = NULL;
 694     static PyObject *sortfun = NULL;
 695     static PyObject *sortargs = NULL;
 696
 697     if (sortargs == NULL) {
 698         sortargs = PyTuple_New(0);
 699         if (sortargs == NULL)
 700             return NULL;
 701     }
 702
 703     if (PyDict_CheckExact(dct))
 704         items = PyDict_Items(dct);
 705     else
 706         items = PyMapping_Items(dct);
 707     if (items == NULL)
 708         return NULL;
 709     iter = PyObject_GetIter(items);
 710     Py_DECREF(items);
 711     if (iter == NULL)
 712         return NULL;
 713     if (s->item_sort_kw == Py_None)
 714         return iter;
 715     lst = PyList_New(0);
 716     if (lst == NULL)
 717         goto bail;
 718     while ((item = PyIter_Next(iter))) {
 719         PyObject *key, *value;
 720         if (!PyTuple_Check(item) || Py_SIZE(item) != 2) {
 721             PyErr_SetString(PyExc_ValueError, "items must return 2-tuples");
 722             goto bail;
 723         }
 724         key = PyTuple_GET_ITEM(item, 0);
 725         if (key == NULL)
 726             goto bail;
 727 #if PY_MAJOR_VERSION < 3
 728         else if (PyString_Check(key)) {
 729             /* item can be added as-is */
 730         }
 731 #endif /* PY_MAJOR_VERSION < 3 */
 732         else if (PyUnicode_Check(key)) {
 733             /* item can be added as-is */
 734         }
 735         else {
 736             PyObject *tpl;
 737             kstr = encoder_stringify_key(s, key);
 738             if (kstr == NULL)
 739                 goto bail;
 740             else if (kstr == Py_None) {
 741                 /* skipkeys */
 742                 Py_DECREF(kstr);
 743                 continue;
 744             }
 745             value = PyTuple_GET_ITEM(item, 1);
 746             if (value == NULL)
 747                 goto bail;
 748             tpl = PyTuple_Pack(2, kstr, value);
 749             if (tpl == NULL)
 750                 goto bail;
 751             Py_CLEAR(kstr);
 752             Py_DECREF(item);
 753             item = tpl;
 754         }
 755         if (PyList_Append(lst, item))
 756             goto bail;
 757         Py_DECREF(item);
 758     }
 759     Py_CLEAR(iter);
 760     if (PyErr_Occurred())
 761         goto bail;
 762     sortfun = PyObject_GetAttrString(lst, "sort");
 763     if (sortfun == NULL)
 764         goto bail;
 765     if (!PyObject_Call(sortfun, sortargs, s->item_sort_kw))
 766         goto bail;
 767     Py_CLEAR(sortfun);
 768     iter = PyObject_GetIter(lst);
 769     Py_CLEAR(lst);
 770     return iter;
 771 bail:
 772     Py_XDECREF(sortfun);
 773     Py_XDECREF(kstr);
 774     Py_XDECREF(item);
 775     Py_XDECREF(lst);
 776     Py_XDECREF(iter);
 777     return NULL;
 778 }
 779
 780 static void
 781 raise_errmsg(char *msg, PyObject *s, Py_ssize_t end)
 782 {
 783     /* Use JSONDecodeError exception to raise a nice looking ValueError subclass */
 784     static PyObject *JSONDecodeError = NULL;
 785     PyObject *exc;
 786     if (JSONDecodeError == NULL) {
 787         PyObject *scanner = PyImport_ImportModule("simplejson.scanner");
 788         if (scanner == NULL)
 789             return;
 790         JSONDecodeError = PyObject_GetAttrString(scanner, "JSONDecodeError");
 791         Py_DECREF(scanner);
 792         if (JSONDecodeError == NULL)
 793             return;
 794     }
 795     exc = PyObject_CallFunction(JSONDecodeError, "(zOO&)", msg, s, _convertPyInt_FromSsize_t, &end);
 796     if (exc) {
 797         PyErr_SetObject(JSONDecodeError, exc);
 798         Py_DECREF(exc);
 799     }
 800 }
 801
 802 static PyObject *
 803 join_list_unicode(PyObject *lst)
 804 {
 805     /* return u''.join(lst) */
 806     static PyObject *joinfn = NULL;
 807     if (joinfn == NULL) {
 808         PyObject *ustr = JSON_NewEmptyUnicode();
 809         if (ustr == NULL)
 810             return NULL;
 811
 812         joinfn = PyObject_GetAttrString(ustr, "join");
 813         Py_DECREF(ustr);
 814         if (joinfn == NULL)
 815             return NULL;
 816     }
 817     return PyObject_CallFunctionObjArgs(joinfn, lst, NULL);
 818 }
 819
 820 #if PY_MAJOR_VERSION >= 3
 821 #define join_list_string join_list_unicode
 822 #else /* PY_MAJOR_VERSION >= 3 */
 823 static PyObject *
 824 join_list_string(PyObject *lst)
 825 {
 826     /* return ''.join(lst) */
 827     static PyObject *joinfn = NULL;
 828     if (joinfn == NULL) {
 829         PyObject *ustr = PyString_FromStringAndSize(NULL, 0);
 830         if (ustr == NULL)
 831             return NULL;
 832
 833         joinfn = PyObject_GetAttrString(ustr, "join");
 834         Py_DECREF(ustr);
 835         if (joinfn == NULL)
 836             return NULL;
 837     }
 838     return PyObject_CallFunctionObjArgs(joinfn, lst, NULL);
 839 }
 840 #endif /* PY_MAJOR_VERSION < 3 */
 841
 842 static PyObject *
 843 _build_rval_index_tuple(PyObject *rval, Py_ssize_t idx)
 844 {
 845     /* return (rval, idx) tuple, stealing reference to rval */
 846     PyObject *tpl;
 847     PyObject *pyidx;
 848     /*
 849     steal a reference to rval, returns (rval, idx)
 850     */
 851     if (rval == NULL) {
 852         assert(PyErr_Occurred());
 853         return NULL;
 854     }
 855     pyidx = PyInt_FromSsize_t(idx);
 856     if (pyidx == NULL) {
 857         Py_DECREF(rval);
 858         return NULL;
 859     }
 860     tpl = PyTuple_New(2);
 861     if (tpl == NULL) {
 862         Py_DECREF(pyidx);
 863         Py_DECREF(rval);
 864         return NULL;
 865     }
 866     PyTuple_SET_ITEM(tpl, 0, rval);
 867     PyTuple_SET_ITEM(tpl, 1, pyidx);
 868     return tpl;
 869 }
 870
 871 #define APPEND_OLD_CHUNK \
 872     if (chunk != NULL) { \
 873         if (chunks == NULL) { \
 874             chunks = PyList_New(0); \
 875             if (chunks == NULL) { \
 876                 goto bail; \
 877             } \
 878         } \
 879         if (PyList_Append(chunks, chunk)) { \
 880             goto bail; \
 881         } \
 882         Py_CLEAR(chunk); \
 883     }
 884
 885 #if PY_MAJOR_VERSION < 3
 886 static PyObject *
 887 scanstring_str(PyObject *pystr, Py_ssize_t end, char *encoding, int strict, Py_ssize_t *next_end_ptr)
 888 {
 889     /* Read the JSON string from PyString pystr.
 890     end is the index of the first character after the quote.
 891     encoding is the encoding of pystr (must be an ASCII superset)
 892     if strict is zero then literal control characters are allowed
 893     *next_end_ptr is a return-by-reference index of the character
 894         after the end quote
 895
 896     Return value is a new PyString (if ASCII-only) or PyUnicode
 897     */
 898     PyObject *rval;
 899     Py_ssize_t len = PyString_GET_SIZE(pystr);
 900     Py_ssize_t begin = end - 1;
 901     Py_ssize_t next = begin;
 902     int has_unicode = 0;
 903     char *buf = PyString_AS_STRING(pystr);
 904     PyObject *chunks = NULL;
 905     PyObject *chunk = NULL;
 906     PyObject *strchunk = NULL;
 907
 908     if (len == end) {
 909         raise_errmsg(ERR_STRING_UNTERMINATED, pystr, begin);
 910         goto bail;
 911     }
 912     else if (end < 0 || len < end) {
 913         PyErr_SetString(PyExc_ValueError, "end is out of bounds");
 914         goto bail;
 915     }
 916     while (1) {
 917         /* Find the end of the string or the next escape */
 918         Py_UNICODE c = 0;
 919         for (next = end; next < len; next++) {
 920             c = (unsigned char)buf[next];
 921             if (c == '"' || c == '\\') {
 922                 break;
 923             }
 924             else if (strict && c <= 0x1f) {
 925                 raise_errmsg(ERR_STRING_CONTROL, pystr, next);
 926                 goto bail;
 927             }
 928             else if (c > 0x7f) {
 929                 has_unicode = 1;
 930             }
 931         }
 932         if (!(c == '"' || c == '\\')) {
 933             raise_errmsg(ERR_STRING_UNTERMINATED, pystr, begin);
 934             goto bail;
 935         }
 936         /* Pick up this chunk if it's not zero length */
 937         if (next != end) {
 938             APPEND_OLD_CHUNK
 939 #if PY_MAJOR_VERSION >= 3
 940             if (!has_unicode) {
 941                 chunk = PyUnicode_DecodeASCII(&buf[end], next - end, NULL);
 942             }
 943             else {
 944                 chunk = PyUnicode_Decode(&buf[end], next - end, encoding, NULL);
 945             }
 946             if (chunk == NULL) {
 947                 goto bail;
 948             }
 949 #else /* PY_MAJOR_VERSION >= 3 */
 950             strchunk = PyString_FromStringAndSize(&buf[end], next - end);
 951             if (strchunk == NULL) {
 952                 goto bail;
 953             }
 954             if (has_unicode) {
 955                 chunk = PyUnicode_FromEncodedObject(strchunk, encoding, NULL);
 956                 Py_DECREF(strchunk);
 957                 if (chunk == NULL) {
 958                     goto bail;
 959                 }
 960             }
 961             else {
 962                 chunk = strchunk;
 963             }
 964 #endif /* PY_MAJOR_VERSION < 3 */
 965         }
 966         next++;
 967         if (c == '"') {
 968             end = next;
 969             break;
 970         }
 971         if (next == len) {
 972             raise_errmsg(ERR_STRING_UNTERMINATED, pystr, begin);
 973             goto bail;
 974         }
 975         c = buf[next];
 976         if (c != 'u') {
 977             /* Non-unicode backslash escapes */
 978             end = next + 1;
 979             switch (c) {
 980                 case '"': break;
 981                 case '\\': break;
 982                 case '/': break;
 983                 case 'b': c = '\b'; break;
 984                 case 'f': c = '\f'; break;
 985                 case 'n': c = '\n'; break;
 986                 case 'r': c = '\r'; break;
 987                 case 't': c = '\t'; break;
 988                 default: c = 0;
 989             }
 990             if (c == 0) {
 991                 raise_errmsg(ERR_STRING_ESC1, pystr, end - 2);
 992                 goto bail;
 993             }
 994         }
 995         else {
 996             c = 0;
 997             next++;
 998             end = next + 4;
 999             if (end >= len) {
1000                 raise_errmsg(ERR_STRING_ESC4, pystr, next - 1);
1001                 goto bail;
1002             }
1003             /* Decode 4 hex digits */
1004             for (; next < end; next++) {
1005                 JSON_UNICHR digit = (JSON_UNICHR)buf[next];
1006                 c <<= 4;
1007                 switch (digit) {
1008                     case '0': case '1': case '2': case '3': case '4':
1009                     case '5': case '6': case '7': case '8': case '9':
1010                         c |= (digit - '0'); break;
1011                     case 'a': case 'b': case 'c': case 'd': case 'e':
1012                     case 'f':
1013                         c |= (digit - 'a' + 10); break;
1014                     case 'A': case 'B': case 'C': case 'D': case 'E':
1015                     case 'F':
1016                         c |= (digit - 'A' + 10); break;
1017                     default:
1018                         raise_errmsg(ERR_STRING_ESC4, pystr, end - 5);
1019                         goto bail;
1020                 }
1021             }
1022 #if (PY_MAJOR_VERSION >= 3 || defined(Py_UNICODE_WIDE))
1023             /* Surrogate pair */
1024             if ((c & 0xfc00) == 0xd800) {
1025                 if (end + 6 < len && buf[next] == '\\' && buf[next+1] == 'u') {
1026                     JSON_UNICHR c2 = 0;
1027                     end += 6;
1028                     /* Decode 4 hex digits */
1029                     for (next += 2; next < end; next++) {
1030                         c2 <<= 4;
1031                         JSON_UNICHR digit = buf[next];
1032                         switch (digit) {
1033                         case '0': case '1': case '2': case '3': case '4':
1034                         case '5': case '6': case '7': case '8': case '9':
1035                             c2 |= (digit - '0'); break;
1036                         case 'a': case 'b': case 'c': case 'd': case 'e':
1037                         case 'f':
1038                             c2 |= (digit - 'a' + 10); break;
1039                         case 'A': case 'B': case 'C': case 'D': case 'E':
1040                         case 'F':
1041                             c2 |= (digit - 'A' + 10); break;
1042                         default:
1043                             raise_errmsg(ERR_STRING_ESC4, pystr, end - 5);
1044                             goto bail;
1045                         }
1046                     }
1047                     if ((c2 & 0xfc00) != 0xdc00) {
1048                         /* not a low surrogate, rewind */
1049                         end -= 6;
1050                         next = end;
1051                     }
1052                     else {
1053                         c = 0x10000 + (((c - 0xd800) << 10) | (c2 - 0xdc00));
1054                     }
1055                 }
1056             }
1057 #endif /* PY_MAJOR_VERSION >= 3 || Py_UNICODE_WIDE */
1058         }
1059         if (c > 0x7f) {
1060             has_unicode = 1;
1061         }
1062         APPEND_OLD_CHUNK
1063 #if PY_MAJOR_VERSION >= 3
1064         chunk = JSON_UnicodeFromChar(c);
1065         if (chunk == NULL) {
1066             goto bail;
1067         }
1068 #else /* PY_MAJOR_VERSION >= 3 */
1069         if (has_unicode) {
1070             chunk = JSON_UnicodeFromChar(c);
1071             if (chunk == NULL) {
1072                 goto bail;
1073             }
1074         }
1075         else {
1076             char c_char = Py_CHARMASK(c);
1077             chunk = PyString_FromStringAndSize(&c_char, 1);
1078             if (chunk == NULL) {
1079                 goto bail;
1080             }
1081         }
1082 #endif
1083     }
1084
1085     if (chunks == NULL) {
1086         if (chunk != NULL)
1087             rval = chunk;
1088         else
1089             rval = JSON_NewEmptyUnicode();
1090     }
1091     else {
1092         APPEND_OLD_CHUNK
1093         rval = join_list_string(chunks);
1094         if (rval == NULL) {
1095             goto bail;
1096         }
1097         Py_CLEAR(chunks);
1098     }
1099
1100     *next_end_ptr = end;
1101     return rval;
1102 bail:
1103     *next_end_ptr = -1;
1104     Py_XDECREF(chunk);
1105     Py_XDECREF(chunks);
1106     return NULL;
1107 }
1108 #endif /* PY_MAJOR_VERSION < 3 */
1109
1110 static PyObject *
1111 scanstring_unicode(PyObject *pystr, Py_ssize_t end, int strict, Py_ssize_t *next_end_ptr)
1112 {
1113     /* Read the JSON string from PyUnicode pystr.
1114     end is the index of the first character after the quote.
1115     if strict is zero then literal control characters are allowed
1116     *next_end_ptr is a return-by-reference index of the character
1117         after the end quote
1118
1119     Return value is a new PyUnicode
1120     */
1121     PyObject *rval;
1122     Py_ssize_t begin = end - 1;
1123     Py_ssize_t next = begin;
1124     PY2_UNUSED int kind = PyUnicode_KIND(pystr);
1125     Py_ssize_t len = PyUnicode_GetLength(pystr);
1126     void *buf = PyUnicode_DATA(pystr);
1127     PyObject *chunks = NULL;
1128     PyObject *chunk = NULL;
1129
1130     if (len == end) {
1131         raise_errmsg(ERR_STRING_UNTERMINATED, pystr, begin);
1132         goto bail;
1133     }
1134     else if (end < 0 || len < end) {
1135         PyErr_SetString(PyExc_ValueError, "end is out of bounds");
1136         goto bail;
1137     }
1138     while (1) {
1139         /* Find the end of the string or the next escape */
1140         JSON_UNICHR c = 0;
1141         for (next = end; next < len; next++) {
1142             c = PyUnicode_READ(kind, buf, next);
1143             if (c == '"' || c == '\\') {
1144                 break;
1145             }
1146             else if (strict && c <= 0x1f) {
1147                 raise_errmsg(ERR_STRING_CONTROL, pystr, next);
1148                 goto bail;
1149             }
1150         }
1151         if (!(c == '"' || c == '\\')) {
1152             raise_errmsg(ERR_STRING_UNTERMINATED, pystr, begin);
1153             goto bail;
1154         }
1155         /* Pick up this chunk if it's not zero length */
1156         if (next != end) {
1157             APPEND_OLD_CHUNK
1158 #if PY_MAJOR_VERSION < 3
1159             chunk = PyUnicode_FromUnicode(&((const Py_UNICODE *)buf)[end], next - end);
1160 #else
1161             chunk = PyUnicode_Substring(pystr, end, next);
1162 #endif
1163             if (chunk == NULL) {
1164                 goto bail;
1165             }
1166         }
1167         next++;
1168         if (c == '"') {
1169             end = next;
1170             break;
1171         }
1172         if (next == len) {
1173             raise_errmsg(ERR_STRING_UNTERMINATED, pystr, begin);
1174             goto bail;
1175         }
1176         c = PyUnicode_READ(kind, buf, next);
1177         if (c != 'u') {
1178             /* Non-unicode backslash escapes */
1179             end = next + 1;
1180             switch (c) {
1181                 case '"': break;
1182                 case '\\': break;
1183                 case '/': break;
1184                 case 'b': c = '\b'; break;
1185                 case 'f': c = '\f'; break;
1186                 case 'n': c = '\n'; break;
1187                 case 'r': c = '\r'; break;
1188                 case 't': c = '\t'; break;
1189                 default: c = 0;
1190             }
1191             if (c == 0) {
1192                 raise_errmsg(ERR_STRING_ESC1, pystr, end - 2);
1193                 goto bail;
1194             }
1195         }
1196         else {
1197             c = 0;
1198             next++;
1199             end = next + 4;
1200             if (end >= len) {
1201                 raise_errmsg(ERR_STRING_ESC4, pystr, next - 1);
1202                 goto bail;
1203             }
1204             /* Decode 4 hex digits */
1205             for (; next < end; next++) {
1206                 JSON_UNICHR digit = PyUnicode_READ(kind, buf, next);
1207                 c <<= 4;
1208                 switch (digit) {
1209                     case '0': case '1': case '2': case '3': case '4':
1210                     case '5': case '6': case '7': case '8': case '9':
1211                         c |= (digit - '0'); break;
1212                     case 'a': case 'b': case 'c': case 'd': case 'e':
1213                     case 'f':
1214                         c |= (digit - 'a' + 10); break;
1215                     case 'A': case 'B': case 'C': case 'D': case 'E':
1216                     case 'F':
1217                         c |= (digit - 'A' + 10); break;
1218                     default:
1219                         raise_errmsg(ERR_STRING_ESC4, pystr, end - 5);
1220                         goto bail;
1221                 }
1222             }
1223 #if PY_MAJOR_VERSION >= 3 || defined(Py_UNICODE_WIDE)
1224             /* Surrogate pair */
1225             if ((c & 0xfc00) == 0xd800) {
1226                 JSON_UNICHR c2 = 0;
1227                 if (end + 6 < len &&
1228                     PyUnicode_READ(kind, buf, next) == '\\' &&
1229                     PyUnicode_READ(kind, buf, next + 1) == 'u') {
1230                     end += 6;
1231                     /* Decode 4 hex digits */
1232                     for (next += 2; next < end; next++) {
1233                         JSON_UNICHR digit = PyUnicode_READ(kind, buf, next);
1234                         c2 <<= 4;
1235                         switch (digit) {
1236                         case '0': case '1': case '2': case '3': case '4':
1237                         case '5': case '6': case '7': case '8': case '9':
1238                             c2 |= (digit - '0'); break;
1239                         case 'a': case 'b': case 'c': case 'd': case 'e':
1240                         case 'f':
1241                             c2 |= (digit - 'a' + 10); break;
1242                         case 'A': case 'B': case 'C': case 'D': case 'E':
1243                         case 'F':
1244                             c2 |= (digit - 'A' + 10); break;
1245                         default:
1246                             raise_errmsg(ERR_STRING_ESC4, pystr, end - 5);
1247                             goto bail;
1248                         }
1249                     }
1250                     if ((c2 & 0xfc00) != 0xdc00) {
1251                         /* not a low surrogate, rewind */
1252                         end -= 6;
1253                         next = end;
1254                     }
1255                     else {
1256                         c = 0x10000 + (((c - 0xd800) << 10) | (c2 - 0xdc00));
1257                     }
1258                 }
1259             }
1260 #endif
1261         }
1262         APPEND_OLD_CHUNK
1263         chunk = JSON_UnicodeFromChar(c);
1264         if (chunk == NULL) {
1265             goto bail;
1266         }
1267     }
1268
1269     if (chunks == NULL) {
1270         if (chunk != NULL)
1271             rval = chunk;
1272         else
1273             rval = JSON_NewEmptyUnicode();
1274     }
1275     else {
1276         APPEND_OLD_CHUNK
1277         rval = join_list_unicode(chunks);
1278         if (rval == NULL) {
1279             goto bail;
1280         }
1281         Py_CLEAR(chunks);
1282     }
1283     *next_end_ptr = end;
1284     return rval;
1285 bail:
1286     *next_end_ptr = -1;
1287     Py_XDECREF(chunk);
1288     Py_XDECREF(chunks);
1289     return NULL;
1290 }
1291
1292 PyDoc_STRVAR(pydoc_scanstring,
1293     "scanstring(basestring, end, encoding, strict=True) -> (str, end)\n"
1294     "\n"
1295     "Scan the string s for a JSON string. End is the index of the\n"
1296     "character in s after the quote that started the JSON string.\n"
1297     "Unescapes all valid JSON string escape sequences and raises ValueError\n"
1298     "on attempt to decode an invalid string. If strict is False then literal\n"
1299     "control characters are allowed in the string.\n"
1300     "\n"
1301     "Returns a tuple of the decoded string and the index of the character in s\n"
1302     "after the end quote."
1303 );
1304
1305 static PyObject *
1306 py_scanstring(PyObject* self UNUSED, PyObject *args)
1307 {
1308     PyObject *pystr;
1309     PyObject *rval;
1310     Py_ssize_t end;
1311     Py_ssize_t next_end = -1;
1312     char *encoding = NULL;
1313     int strict = 1;
1314     if (!PyArg_ParseTuple(args, "OO&|zi:scanstring", &pystr, _convertPyInt_AsSsize_t, &end, &encoding, &strict)) {
1315         return NULL;
1316     }
1317     if (encoding == NULL) {
1318         encoding = DEFAULT_ENCODING;
1319     }
1320     if (PyUnicode_Check(pystr)) {
1321         rval = scanstring_unicode(pystr, end, strict, &next_end);
1322     }
1323 #if PY_MAJOR_VERSION < 3
1324     /* Using a bytes input is unsupported for scanning in Python 3.
1325        It is coerced to str in the decoder before it gets here. */
1326     else if (PyString_Check(pystr)) {
1327         rval = scanstring_str(pystr, end, encoding, strict, &next_end);
1328     }
1329 #endif
1330     else {
1331         PyErr_Format(PyExc_TypeError,
1332                      "first argument must be a string, not %.80s",
1333                      Py_TYPE(pystr)->tp_name);
1334         return NULL;
1335     }
1336     return _build_rval_index_tuple(rval, next_end);
1337 }
1338
1339 PyDoc_STRVAR(pydoc_encode_basestring_ascii,
1340     "encode_basestring_ascii(basestring) -> str\n"
1341     "\n"
1342     "Return an ASCII-only JSON representation of a Python string"
1343 );
1344
1345 static PyObject *
1346 py_encode_basestring_ascii(PyObject* self UNUSED, PyObject *pystr)
1347 {
1348     /* Return an ASCII-only JSON representation of a Python string */
1349     /* METH_O */
1350     if (PyString_Check(pystr)) {
1351         return ascii_escape_str(pystr);
1352     }
1353     else if (PyUnicode_Check(pystr)) {
1354         return ascii_escape_unicode(pystr);
1355     }
1356     else {
1357         PyErr_Format(PyExc_TypeError,
1358                      "first argument must be a string, not %.80s",
1359                      Py_TYPE(pystr)->tp_name);
1360         return NULL;
1361     }
1362 }
1363
1364 static void
1365 scanner_dealloc(PyObject *self)
1366 {
1367     /* Deallocate scanner object */
1368     scanner_clear(self);
1369     Py_TYPE(self)->tp_free(self);
1370 }
1371
1372 static int
1373 scanner_traverse(PyObject *self, visitproc visit, void *arg)
1374 {
1375     PyScannerObject *s;
1376     assert(PyScanner_Check(self));
1377     s = (PyScannerObject *)self;
1378     Py_VISIT(s->encoding);
1379     Py_VISIT(s->strict);
1380     Py_VISIT(s->object_hook);
1381     Py_VISIT(s->pairs_hook);
1382     Py_VISIT(s->parse_float);
1383     Py_VISIT(s->parse_int);
1384     Py_VISIT(s->parse_constant);
1385     Py_VISIT(s->memo);
1386     return 0;
1387 }
1388
1389 static int
1390 scanner_clear(PyObject *self)
1391 {
1392     PyScannerObject *s;
1393     assert(PyScanner_Check(self));
1394     s = (PyScannerObject *)self;
1395     Py_CLEAR(s->encoding);
1396     Py_CLEAR(s->strict);
1397     Py_CLEAR(s->object_hook);
1398     Py_CLEAR(s->pairs_hook);
1399     Py_CLEAR(s->parse_float);
1400     Py_CLEAR(s->parse_int);
1401     Py_CLEAR(s->parse_constant);
1402     Py_CLEAR(s->memo);
1403     return 0;
1404 }
1405
1406 #if PY_MAJOR_VERSION < 3
1407 static PyObject *
1408 _parse_object_str(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr)
1409 {
1410     /* Read a JSON object from PyString pystr.
1411     idx is the index of the first character after the opening curly brace.
1412     *next_idx_ptr is a return-by-reference index to the first character after
1413         the closing curly brace.
1414
1415     Returns a new PyObject (usually a dict, but object_hook or
1416     object_pairs_hook can change that)
1417     */
1418     char *str = PyString_AS_STRING(pystr);
1419     Py_ssize_t end_idx = PyString_GET_SIZE(pystr) - 1;
1420     PyObject *rval = NULL;
1421     PyObject *pairs = NULL;
1422     PyObject *item;
1423     PyObject *key = NULL;
1424     PyObject *val = NULL;
1425     char *encoding = JSON_ASCII_AS_STRING(s->encoding);
1426     int strict = PyObject_IsTrue(s->strict);
1427     int has_pairs_hook = (s->pairs_hook != Py_None);
1428     int did_parse = 0;
1429     Py_ssize_t next_idx;
1430     if (has_pairs_hook) {
1431         pairs = PyList_New(0);
1432         if (pairs == NULL)
1433             return NULL;
1434     }
1435     else {
1436         rval = PyDict_New();
1437         if (rval == NULL)
1438             return NULL;
1439     }
1440
1441     /* skip whitespace after { */
1442     while (idx <= end_idx && IS_WHITESPACE(str[idx])) idx++;
1443
1444     /* only loop if the object is non-empty */
1445     if (idx <= end_idx && str[idx] != '}') {
1446         int trailing_delimiter = 0;
1447         while (idx <= end_idx) {
1448             PyObject *memokey;
1449             trailing_delimiter = 0;
1450
1451             /* read key */
1452             if (str[idx] != '"') {
1453                 raise_errmsg(ERR_OBJECT_PROPERTY, pystr, idx);
1454                 goto bail;
1455             }
1456             key = scanstring_str(pystr, idx + 1, encoding, strict, &next_idx);
1457             if (key == NULL)
1458                 goto bail;
1459             memokey = PyDict_GetItem(s->memo, key);
1460             if (memokey != NULL) {
1461                 Py_INCREF(memokey);
1462                 Py_DECREF(key);
1463                 key = memokey;
1464             }
1465             else {
1466                 if (PyDict_SetItem(s->memo, key, key) < 0)
1467                     goto bail;
1468             }
1469             idx = next_idx;
1470
1471             /* skip whitespace between key and : delimiter, read :, skip whitespace */
1472             while (idx <= end_idx && IS_WHITESPACE(str[idx])) idx++;
1473             if (idx > end_idx || str[idx] != ':') {
1474                 raise_errmsg(ERR_OBJECT_PROPERTY_DELIMITER, pystr, idx);
1475                 goto bail;
1476             }
1477             idx++;
1478             while (idx <= end_idx && IS_WHITESPACE(str[idx])) idx++;
1479
1480             /* read any JSON data type */
1481             val = scan_once_str(s, pystr, idx, &next_idx);
1482             if (val == NULL)
1483                 goto bail;
1484
1485             if (has_pairs_hook) {
1486                 item = PyTuple_Pack(2, key, val);
1487                 if (item == NULL)
1488                     goto bail;
1489                 Py_CLEAR(key);
1490                 Py_CLEAR(val);
1491                 if (PyList_Append(pairs, item) == -1) {
1492                     Py_DECREF(item);
1493                     goto bail;
1494                 }
1495                 Py_DECREF(item);
1496             }
1497             else {
1498                 if (PyDict_SetItem(rval, key, val) < 0)
1499                     goto bail;
1500                 Py_CLEAR(key);
1501                 Py_CLEAR(val);
1502             }
1503             idx = next_idx;
1504
1505             /* skip whitespace before } or , */
1506             while (idx <= end_idx && IS_WHITESPACE(str[idx])) idx++;
1507
1508             /* bail if the object is closed or we didn't get the , delimiter */
1509             did_parse = 1;
1510             if (idx > end_idx) break;
1511             if (str[idx] == '}') {
1512                 break;
1513             }
1514             else if (str[idx] != ',') {
1515                 raise_errmsg(ERR_OBJECT_DELIMITER, pystr, idx);
1516                 goto bail;
1517             }
1518             idx++;
1519
1520             /* skip whitespace after , delimiter */
1521             while (idx <= end_idx && IS_WHITESPACE(str[idx])) idx++;
1522             trailing_delimiter = 1;
1523         }
1524         if (trailing_delimiter) {
1525             raise_errmsg(ERR_OBJECT_PROPERTY, pystr, idx);
1526             goto bail;
1527         }
1528     }
1529     /* verify that idx < end_idx, str[idx] should be '}' */
1530     if (idx > end_idx || str[idx] != '}') {
1531         if (did_parse) {
1532             raise_errmsg(ERR_OBJECT_DELIMITER, pystr, idx);
1533         } else {
1534             raise_errmsg(ERR_OBJECT_PROPERTY_FIRST, pystr, idx);
1535         }
1536         goto bail;
1537     }
1538
1539     /* if pairs_hook is not None: rval = object_pairs_hook(pairs) */
1540     if (s->pairs_hook != Py_None) {
1541         val = PyObject_CallFunctionObjArgs(s->pairs_hook, pairs, NULL);
1542         if (val == NULL)
1543             goto bail;
1544         Py_DECREF(pairs);
1545         *next_idx_ptr = idx + 1;
1546         return val;
1547     }
1548
1549     /* if object_hook is not None: rval = object_hook(rval) */
1550     if (s->object_hook != Py_None) {
1551         val = PyObject_CallFunctionObjArgs(s->object_hook, rval, NULL);
1552         if (val == NULL)
1553             goto bail;
1554         Py_DECREF(rval);
1555         rval = val;
1556         val = NULL;
1557     }
1558     *next_idx_ptr = idx + 1;
1559     return rval;
1560 bail:
1561     Py_XDECREF(rval);
1562     Py_XDECREF(key);
1563     Py_XDECREF(val);
1564     Py_XDECREF(pairs);
1565     return NULL;
1566 }
1567 #endif /* PY_MAJOR_VERSION < 3 */
1568
1569 static PyObject *
1570 _parse_object_unicode(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr)
1571 {
1572     /* Read a JSON object from PyUnicode pystr.
1573     idx is the index of the first character after the opening curly brace.
1574     *next_idx_ptr is a return-by-reference index to the first character after
1575         the closing curly brace.
1576
1577     Returns a new PyObject (usually a dict, but object_hook can change that)
1578     */
1579     void *str = PyUnicode_DATA(pystr);
1580     Py_ssize_t end_idx = PyUnicode_GetLength(pystr) - 1;
1581     PY2_UNUSED int kind = PyUnicode_KIND(pystr);
1582     PyObject *rval = NULL;
1583     PyObject *pairs = NULL;
1584     PyObject *item;
1585     PyObject *key = NULL;
1586     PyObject *val = NULL;
1587     int strict = PyObject_IsTrue(s->strict);
1588     int has_pairs_hook = (s->pairs_hook != Py_None);
1589     int did_parse = 0;
1590     Py_ssize_t next_idx;
1591
1592     if (has_pairs_hook) {
1593         pairs = PyList_New(0);
1594         if (pairs == NULL)
1595             return NULL;
1596     }
1597     else {
1598         rval = PyDict_New();
1599         if (rval == NULL)
1600             return NULL;
1601     }
1602
1603     /* skip whitespace after { */
1604     while (idx <= end_idx && IS_WHITESPACE(PyUnicode_READ(kind, str, idx))) idx++;
1605
1606     /* only loop if the object is non-empty */
1607     if (idx <= end_idx && PyUnicode_READ(kind, str, idx) != '}') {
1608         int trailing_delimiter = 0;
1609         while (idx <= end_idx) {
1610             PyObject *memokey;
1611             trailing_delimiter = 0;
1612
1613             /* read key */
1614             if (PyUnicode_READ(kind, str, idx) != '"') {
1615                 raise_errmsg(ERR_OBJECT_PROPERTY, pystr, idx);
1616                 goto bail;
1617             }
1618             key = scanstring_unicode(pystr, idx + 1, strict, &next_idx);
1619             if (key == NULL)
1620                 goto bail;
1621             memokey = PyDict_GetItem(s->memo, key);
1622             if (memokey != NULL) {
1623                 Py_INCREF(memokey);
1624                 Py_DECREF(key);
1625                 key = memokey;
1626             }
1627             else {
1628                 if (PyDict_SetItem(s->memo, key, key) < 0)
1629                     goto bail;
1630             }
1631             idx = next_idx;
1632
1633             /* skip whitespace between key and : delimiter, read :, skip
1634                whitespace */
1635             while (idx <= end_idx && IS_WHITESPACE(PyUnicode_READ(kind, str, idx))) idx++;
1636             if (idx > end_idx || PyUnicode_READ(kind, str, idx) != ':') {
1637                 raise_errmsg(ERR_OBJECT_PROPERTY_DELIMITER, pystr, idx);
1638                 goto bail;
1639             }
1640             idx++;
1641             while (idx <= end_idx && IS_WHITESPACE(PyUnicode_READ(kind, str, idx))) idx++;
1642
1643             /* read any JSON term */
1644             val = scan_once_unicode(s, pystr, idx, &next_idx);
1645             if (val == NULL)
1646                 goto bail;
1647
1648             if (has_pairs_hook) {
1649                 item = PyTuple_Pack(2, key, val);
1650                 if (item == NULL)
1651                     goto bail;
1652                 Py_CLEAR(key);
1653                 Py_CLEAR(val);
1654                 if (PyList_Append(pairs, item) == -1) {
1655                     Py_DECREF(item);
1656                     goto bail;
1657                 }
1658                 Py_DECREF(item);
1659             }
1660             else {
1661                 if (PyDict_SetItem(rval, key, val) < 0)
1662                     goto bail;
1663                 Py_CLEAR(key);
1664                 Py_CLEAR(val);
1665             }
1666             idx = next_idx;
1667
1668             /* skip whitespace before } or , */
1669             while (idx <= end_idx && IS_WHITESPACE(PyUnicode_READ(kind, str, idx))) idx++;
1670
1671             /* bail if the object is closed or we didn't get the ,
1672                delimiter */
1673             did_parse = 1;
1674             if (idx > end_idx) break;
1675             if (PyUnicode_READ(kind, str, idx) == '}') {
1676                 break;
1677             }
1678             else if (PyUnicode_READ(kind, str, idx) != ',') {
1679                 raise_errmsg(ERR_OBJECT_DELIMITER, pystr, idx);
1680                 goto bail;
1681             }
1682             idx++;
1683
1684             /* skip whitespace after , delimiter */
1685             while (idx <= end_idx && IS_WHITESPACE(PyUnicode_READ(kind, str, idx))) idx++;
1686             trailing_delimiter = 1;
1687         }
1688         if (trailing_delimiter) {
1689             raise_errmsg(ERR_OBJECT_PROPERTY, pystr, idx);
1690             goto bail;
1691         }
1692     }
1693
1694     /* verify that idx < end_idx, str[idx] should be '}' */
1695     if (idx > end_idx || PyUnicode_READ(kind, str, idx) != '}') {
1696         if (did_parse) {
1697             raise_errmsg(ERR_OBJECT_DELIMITER, pystr, idx);
1698         } else {
1699             raise_errmsg(ERR_OBJECT_PROPERTY_FIRST, pystr, idx);
1700         }
1701         goto bail;
1702     }
1703
1704     /* if pairs_hook is not None: rval = object_pairs_hook(pairs) */
1705     if (s->pairs_hook != Py_None) {
1706         val = PyObject_CallFunctionObjArgs(s->pairs_hook, pairs, NULL);
1707         if (val == NULL)
1708             goto bail;
1709         Py_DECREF(pairs);
1710         *next_idx_ptr = idx + 1;
1711         return val;
1712     }
1713
1714     /* if object_hook is not None: rval = object_hook(rval) */
1715     if (s->object_hook != Py_None) {
1716         val = PyObject_CallFunctionObjArgs(s->object_hook, rval, NULL);
1717         if (val == NULL)
1718             goto bail;
1719         Py_DECREF(rval);
1720         rval = val;
1721         val = NULL;
1722     }
1723     *next_idx_ptr = idx + 1;
1724     return rval;
1725 bail:
1726     Py_XDECREF(rval);
1727     Py_XDECREF(key);
1728     Py_XDECREF(val);
1729     Py_XDECREF(pairs);
1730     return NULL;
1731 }
1732
1733 #if PY_MAJOR_VERSION < 3
1734 static PyObject *
1735 _parse_array_str(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr)
1736 {
1737     /* Read a JSON array from PyString pystr.
1738     idx is the index of the first character after the opening brace.
1739     *next_idx_ptr is a return-by-reference index to the first character after
1740         the closing brace.
1741
1742     Returns a new PyList
1743     */
1744     char *str = PyString_AS_STRING(pystr);
1745     Py_ssize_t end_idx = PyString_GET_SIZE(pystr) - 1;
1746     PyObject *val = NULL;
1747     PyObject *rval = PyList_New(0);
1748     Py_ssize_t next_idx;
1749     if (rval == NULL)
1750         return NULL;
1751
1752     /* skip whitespace after [ */
1753     while (idx <= end_idx && IS_WHITESPACE(str[idx])) idx++;
1754
1755     /* only loop if the array is non-empty */
1756     if (idx <= end_idx && str[idx] != ']') {
1757         int trailing_delimiter = 0;
1758         while (idx <= end_idx) {
1759             trailing_delimiter = 0;
1760             /* read any JSON term and de-tuplefy the (rval, idx) */
1761             val = scan_once_str(s, pystr, idx, &next_idx);
1762             if (val == NULL) {
1763                 goto bail;
1764             }
1765
1766             if (PyList_Append(rval, val) == -1)
1767                 goto bail;
1768
1769             Py_CLEAR(val);
1770             idx = next_idx;
1771
1772             /* skip whitespace between term and , */
1773             while (idx <= end_idx && IS_WHITESPACE(str[idx])) idx++;
1774
1775             /* bail if the array is closed or we didn't get the , delimiter */
1776             if (idx > end_idx) break;
1777             if (str[idx] == ']') {
1778                 break;
1779             }
1780             else if (str[idx] != ',') {
1781                 raise_errmsg(ERR_ARRAY_DELIMITER, pystr, idx);
1782                 goto bail;
1783             }
1784             idx++;
1785
1786             /* skip whitespace after , */
1787             while (idx <= end_idx && IS_WHITESPACE(str[idx])) idx++;
1788             trailing_delimiter = 1;
1789         }
1790         if (trailing_delimiter) {
1791             raise_errmsg(ERR_EXPECTING_VALUE, pystr, idx);
1792             goto bail;
1793         }
1794     }
1795
1796     /* verify that idx < end_idx, str[idx] should be ']' */
1797     if (idx > end_idx || str[idx] != ']') {
1798         if (PyList_GET_SIZE(rval)) {
1799             raise_errmsg(ERR_ARRAY_DELIMITER, pystr, idx);
1800         } else {
1801             raise_errmsg(ERR_ARRAY_VALUE_FIRST, pystr, idx);
1802         }
1803         goto bail;
1804     }
1805     *next_idx_ptr = idx + 1;
1806     return rval;
1807 bail:
1808     Py_XDECREF(val);
1809     Py_DECREF(rval);
1810     return NULL;
1811 }
1812 #endif /* PY_MAJOR_VERSION < 3 */
1813
1814 static PyObject *
1815 _parse_array_unicode(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr)
1816 {
1817     /* Read a JSON array from PyString pystr.
1818     idx is the index of the first character after the opening brace.
1819     *next_idx_ptr is a return-by-reference index to the first character after
1820         the closing brace.
1821
1822     Returns a new PyList
1823     */
1824     PY2_UNUSED int kind = PyUnicode_KIND(pystr);
1825     void *str = PyUnicode_DATA(pystr);
1826     Py_ssize_t end_idx = PyUnicode_GetLength(pystr) - 1;
1827     PyObject *val = NULL;
1828     PyObject *rval = PyList_New(0);
1829     Py_ssize_t next_idx;
1830     if (rval == NULL)
1831         return NULL;
1832
1833     /* skip whitespace after [ */
1834     while (idx <= end_idx && IS_WHITESPACE(PyUnicode_READ(kind, str, idx))) idx++;
1835
1836     /* only loop if the array is non-empty */
1837     if (idx <= end_idx && PyUnicode_READ(kind, str, idx) != ']') {
1838         int trailing_delimiter = 0;
1839         while (idx <= end_idx) {
1840             trailing_delimiter = 0;
1841             /* read any JSON term  */
1842             val = scan_once_unicode(s, pystr, idx, &next_idx);
1843             if (val == NULL) {
1844                 goto bail;
1845             }
1846
1847             if (PyList_Append(rval, val) == -1)
1848                 goto bail;
1849
1850             Py_CLEAR(val);
1851             idx = next_idx;
1852
1853             /* skip whitespace between term and , */
1854             while (idx <= end_idx && IS_WHITESPACE(PyUnicode_READ(kind, str, idx))) idx++;
1855
1856             /* bail if the array is closed or we didn't get the , delimiter */
1857             if (idx > end_idx) break;
1858             if (PyUnicode_READ(kind, str, idx) == ']') {
1859                 break;
1860             }
1861             else if (PyUnicode_READ(kind, str, idx) != ',') {
1862                 raise_errmsg(ERR_ARRAY_DELIMITER, pystr, idx);
1863                 goto bail;
1864             }
1865             idx++;
1866
1867             /* skip whitespace after , */
1868             while (idx <= end_idx && IS_WHITESPACE(PyUnicode_READ(kind, str, idx))) idx++;
1869             trailing_delimiter = 1;
1870         }
1871         if (trailing_delimiter) {
1872             raise_errmsg(ERR_EXPECTING_VALUE, pystr, idx);
1873             goto bail;
1874         }
1875     }
1876
1877     /* verify that idx < end_idx, str[idx] should be ']' */
1878     if (idx > end_idx || PyUnicode_READ(kind, str, idx) != ']') {
1879         if (PyList_GET_SIZE(rval)) {
1880             raise_errmsg(ERR_ARRAY_DELIMITER, pystr, idx);
1881         } else {
1882             raise_errmsg(ERR_ARRAY_VALUE_FIRST, pystr, idx);
1883         }
1884         goto bail;
1885     }
1886     *next_idx_ptr = idx + 1;
1887     return rval;
1888 bail:
1889     Py_XDECREF(val);
1890     Py_DECREF(rval);
1891     return NULL;
1892 }
1893
1894 static PyObject *
1895 _parse_constant(PyScannerObject *s, char *constant, Py_ssize_t idx, Py_ssize_t *next_idx_ptr)
1896 {
1897     /* Read a JSON constant from PyString pystr.
1898     constant is the constant string that was found
1899         ("NaN", "Infinity", "-Infinity").
1900     idx is the index of the first character of the constant
1901     *next_idx_ptr is a return-by-reference index to the first character after
1902         the constant.
1903
1904     Returns the result of parse_constant
1905     */
1906     PyObject *cstr;
1907     PyObject *rval;
1908     /* constant is "NaN", "Infinity", or "-Infinity" */
1909     cstr = JSON_InternFromString(constant);
1910     if (cstr == NULL)
1911         return NULL;
1912
1913     /* rval = parse_constant(constant) */
1914     rval = PyObject_CallFunctionObjArgs(s->parse_constant, cstr, NULL);
1915     idx += JSON_Intern_GET_SIZE(cstr);
1916     Py_DECREF(cstr);
1917     *next_idx_ptr = idx;
1918     return rval;
1919 }
1920
1921 #if PY_MAJOR_VERSION < 3
1922 static PyObject *
1923 _match_number_str(PyScannerObject *s, PyObject *pystr, Py_ssize_t start, Py_ssize_t *next_idx_ptr)
1924 {
1925     /* Read a JSON number from PyString pystr.
1926     idx is the index of the first character of the number
1927     *next_idx_ptr is a return-by-reference index to the first character after
1928         the number.
1929
1930     Returns a new PyObject representation of that number:
1931         PyInt, PyLong, or PyFloat.
1932         May return other types if parse_int or parse_float are set
1933     */
1934     char *str = PyString_AS_STRING(pystr);
1935     Py_ssize_t end_idx = PyString_GET_SIZE(pystr) - 1;
1936     Py_ssize_t idx = start;
1937     int is_float = 0;
1938     PyObject *rval;
1939     PyObject *numstr;
1940
1941     /* read a sign if it's there, make sure it's not the end of the string */
1942     if (str[idx] == '-') {
1943         if (idx >= end_idx) {
1944             raise_errmsg(ERR_EXPECTING_VALUE, pystr, idx);
1945             return NULL;
1946         }
1947         idx++;
1948     }
1949
1950     /* read as many integer digits as we find as long as it doesn't start with 0 */
1951     if (str[idx] >= '1' && str[idx] <= '9') {
1952         idx++;
1953         while (idx <= end_idx && str[idx] >= '0' && str[idx] <= '9') idx++;
1954     }
1955     /* if it starts with 0 we only expect one integer digit */
1956     else if (str[idx] == '0') {
1957         idx++;
1958     }
1959     /* no integer digits, error */
1960     else {
1961         raise_errmsg(ERR_EXPECTING_VALUE, pystr, idx);
1962         return NULL;
1963     }
1964
1965     /* if the next char is '.' followed by a digit then read all float digits */
1966     if (idx < end_idx && str[idx] == '.' && str[idx + 1] >= '0' && str[idx + 1] <= '9') {
1967         is_float = 1;
1968         idx += 2;
1969         while (idx <= end_idx && str[idx] >= '0' && str[idx] <= '9') idx++;
1970     }
1971
1972     /* if the next char is 'e' or 'E' then maybe read the exponent (or backtrack) */
1973     if (idx < end_idx && (str[idx] == 'e' || str[idx] == 'E')) {
1974
1975         /* save the index of the 'e' or 'E' just in case we need to backtrack */
1976         Py_ssize_t e_start = idx;
1977         idx++;
1978
1979         /* read an exponent sign if present */
1980         if (idx < end_idx && (str[idx] == '-' || str[idx] == '+')) idx++;
1981
1982         /* read all digits */
1983         while (idx <= end_idx && str[idx] >= '0' && str[idx] <= '9') idx++;
1984
1985         /* if we got a digit, then parse as float. if not, backtrack */
1986         if (str[idx - 1] >= '0' && str[idx - 1] <= '9') {
1987             is_float = 1;
1988         }
1989         else {
1990             idx = e_start;
1991         }
1992     }
1993
1994     /* copy the section we determined to be a number */
1995     numstr = PyString_FromStringAndSize(&str[start], idx - start);
1996     if (numstr == NULL)
1997         return NULL;
1998     if (is_float) {
1999         /* parse as a float using a fast path if available, otherwise call user defined method */
2000         if (s->parse_float != (PyObject *)&PyFloat_Type) {
2001             rval = PyObject_CallFunctionObjArgs(s->parse_float, numstr, NULL);
2002         }
2003         else {
2004             /* rval = PyFloat_FromDouble(PyOS_ascii_atof(PyString_AS_STRING(numstr))); */
2005             double d = PyOS_string_to_double(PyString_AS_STRING(numstr),
2006                                              NULL, NULL);
2007             if (d == -1.0 && PyErr_Occurred())
2008                 return NULL;
2009             rval = PyFloat_FromDouble(d);
2010         }
2011     }
2012     else {
2013         /* parse as an int using a fast path if available, otherwise call user defined method */
2014         if (s->parse_int != (PyObject *)&PyInt_Type) {
2015             rval = PyObject_CallFunctionObjArgs(s->parse_int, numstr, NULL);
2016         }
2017         else {
2018             rval = PyInt_FromString(PyString_AS_STRING(numstr), NULL, 10);
2019         }
2020     }
2021     Py_DECREF(numstr);
2022     *next_idx_ptr = idx;
2023     return rval;
2024 }
2025 #endif /* PY_MAJOR_VERSION < 3 */
2026
2027 static PyObject *
2028 _match_number_unicode(PyScannerObject *s, PyObject *pystr, Py_ssize_t start, Py_ssize_t *next_idx_ptr)
2029 {
2030     /* Read a JSON number from PyUnicode pystr.
2031     idx is the index of the first character of the number
2032     *next_idx_ptr is a return-by-reference index to the first character after
2033         the number.
2034
2035     Returns a new PyObject representation of that number:
2036         PyInt, PyLong, or PyFloat.
2037         May return other types if parse_int or parse_float are set
2038     */
2039     PY2_UNUSED int kind = PyUnicode_KIND(pystr);
2040     void *str = PyUnicode_DATA(pystr);
2041     Py_ssize_t end_idx = PyUnicode_GetLength(pystr) - 1;
2042     Py_ssize_t idx = start;
2043     int is_float = 0;
2044     JSON_UNICHR c;
2045     PyObject *rval;
2046     PyObject *numstr;
2047
2048     /* read a sign if it's there, make sure it's not the end of the string */
2049     if (PyUnicode_READ(kind, str, idx) == '-') {
2050         if (idx >= end_idx) {
2051             raise_errmsg(ERR_EXPECTING_VALUE, pystr, idx);
2052             return NULL;
2053         }
2054         idx++;
2055     }
2056
2057     /* read as many integer digits as we find as long as it doesn't start with 0 */
2058     c = PyUnicode_READ(kind, str, idx);
2059     if (c == '0') {
2060         /* if it starts with 0 we only expect one integer digit */
2061         idx++;
2062     }
2063     else if (IS_DIGIT(c)) {
2064         idx++;
2065         while (idx <= end_idx && IS_DIGIT(PyUnicode_READ(kind, str, idx))) {
2066             idx++;
2067         }
2068     }
2069     else {
2070         /* no integer digits, error */
2071         raise_errmsg(ERR_EXPECTING_VALUE, pystr, idx);
2072         return NULL;
2073     }
2074
2075     /* if the next char is '.' followed by a digit then read all float digits */
2076     if (idx < end_idx &&
2077         PyUnicode_READ(kind, str, idx) == '.' &&
2078         IS_DIGIT(PyUnicode_READ(kind, str, idx + 1))) {
2079         is_float = 1;
2080         idx += 2;
2081         while (idx <= end_idx && IS_DIGIT(PyUnicode_READ(kind, str, idx))) idx++;
2082     }
2083
2084     /* if the next char is 'e' or 'E' then maybe read the exponent (or backtrack) */
2085     if (idx < end_idx &&
2086         (PyUnicode_READ(kind, str, idx) == 'e' ||
2087             PyUnicode_READ(kind, str, idx) == 'E')) {
2088         Py_ssize_t e_start = idx;
2089         idx++;
2090
2091         /* read an exponent sign if present */
2092         if (idx < end_idx &&
2093             (PyUnicode_READ(kind, str, idx) == '-' ||
2094                 PyUnicode_READ(kind, str, idx) == '+')) idx++;
2095
2096         /* read all digits */
2097         while (idx <= end_idx && IS_DIGIT(PyUnicode_READ(kind, str, idx))) idx++;
2098
2099         /* if we got a digit, then parse as float. if not, backtrack */
2100         if (IS_DIGIT(PyUnicode_READ(kind, str, idx - 1))) {
2101             is_float = 1;
2102         }
2103         else {
2104             idx = e_start;
2105         }
2106     }
2107
2108     /* copy the section we determined to be a number */
2109 #if PY_MAJOR_VERSION >= 3
2110     numstr = PyUnicode_Substring(pystr, start, idx);
2111 #else
2112     numstr = PyUnicode_FromUnicode(&((Py_UNICODE *)str)[start], idx - start);
2113 #endif
2114     if (numstr == NULL)
2115         return NULL;
2116     if (is_float) {
2117         /* parse as a float using a fast path if available, otherwise call user defined method */
2118         if (s->parse_float != (PyObject *)&PyFloat_Type) {
2119             rval = PyObject_CallFunctionObjArgs(s->parse_float, numstr, NULL);
2120         }
2121         else {
2122 #if PY_MAJOR_VERSION >= 3
2123             rval = PyFloat_FromString(numstr);
2124 #else
2125             rval = PyFloat_FromString(numstr, NULL);
2126 #endif
2127         }
2128     }
2129     else {
2130         /* no fast path for unicode -> int, just call */
2131         rval = PyObject_CallFunctionObjArgs(s->parse_int, numstr, NULL);
2132     }
2133     Py_DECREF(numstr);
2134     *next_idx_ptr = idx;
2135     return rval;
2136 }
2137
2138 #if PY_MAJOR_VERSION < 3
2139 static PyObject *
2140 scan_once_str(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr)
2141 {
2142     /* Read one JSON term (of any kind) from PyString pystr.
2143     idx is the index of the first character of the term
2144     *next_idx_ptr is a return-by-reference index to the first character after
2145         the number.
2146
2147     Returns a new PyObject representation of the term.
2148     */
2149     char *str = PyString_AS_STRING(pystr);
2150     Py_ssize_t length = PyString_GET_SIZE(pystr);
2151     PyObject *rval = NULL;
2152     int fallthrough = 0;
2153     if (idx >= length) {
2154         raise_errmsg(ERR_EXPECTING_VALUE, pystr, idx);
2155         return NULL;
2156     }
2157     switch (str[idx]) {
2158         case '"':
2159             /* string */
2160             rval = scanstring_str(pystr, idx + 1,
2161                 JSON_ASCII_AS_STRING(s->encoding),
2162                 PyObject_IsTrue(s->strict),
2163                 next_idx_ptr);
2164             break;
2165         case '{':
2166             /* object */
2167             if (Py_EnterRecursiveCall(" while decoding a JSON object "
2168                                       "from a string"))
2169                 return NULL;
2170             rval = _parse_object_str(s, pystr, idx + 1, next_idx_ptr);
2171             Py_LeaveRecursiveCall();
2172             break;
2173         case '[':
2174             /* array */
2175             if (Py_EnterRecursiveCall(" while decoding a JSON array "
2176                                       "from a string"))
2177                 return NULL;
2178             rval = _parse_array_str(s, pystr, idx + 1, next_idx_ptr);
2179             Py_LeaveRecursiveCall();
2180             break;
2181         case 'n':
2182             /* null */
2183             if ((idx + 3 < length) && str[idx + 1] == 'u' && str[idx + 2] == 'l' && str[idx + 3] == 'l') {
2184                 Py_INCREF(Py_None);
2185                 *next_idx_ptr = idx + 4;
2186                 rval = Py_None;
2187             }
2188             else
2189                 fallthrough = 1;
2190             break;
2191         case 't':
2192             /* true */
2193             if ((idx + 3 < length) && str[idx + 1] == 'r' && str[idx + 2] == 'u' && str[idx + 3] == 'e') {
2194                 Py_INCREF(Py_True);
2195                 *next_idx_ptr = idx + 4;
2196                 rval = Py_True;
2197             }
2198             else
2199                 fallthrough = 1;
2200             break;
2201         case 'f':
2202             /* false */
2203             if ((idx + 4 < length) && str[idx + 1] == 'a' && str[idx + 2] == 'l' && str[idx + 3] == 's' && str[idx + 4] == 'e') {
2204                 Py_INCREF(Py_False);
2205                 *next_idx_ptr = idx + 5;
2206                 rval = Py_False;
2207             }
2208             else
2209                 fallthrough = 1;
2210             break;
2211         case 'N':
2212             /* NaN */
2213             if ((idx + 2 < length) && str[idx + 1] == 'a' && str[idx + 2] == 'N') {
2214                 rval = _parse_constant(s, "NaN", idx, next_idx_ptr);
2215             }
2216             else
2217                 fallthrough = 1;
2218             break;
2219         case 'I':
2220             /* Infinity */
2221             if ((idx + 7 < length) && str[idx + 1] == 'n' && str[idx + 2] == 'f' && str[idx + 3] == 'i' && str[idx + 4] == 'n' && str[idx + 5] == 'i' && str[idx + 6] == 't' && str[idx + 7] == 'y') {
2222                 rval = _parse_constant(s, "Infinity", idx, next_idx_ptr);
2223             }
2224             else
2225                 fallthrough = 1;
2226             break;
2227         case '-':
2228             /* -Infinity */
2229             if ((idx + 8 < length) && str[idx + 1] == 'I' && str[idx + 2] == 'n' && str[idx + 3] == 'f' && str[idx + 4] == 'i' && str[idx + 5] == 'n' && str[idx + 6] == 'i' && str[idx + 7] == 't' && str[idx + 8] == 'y') {
2230                 rval = _parse_constant(s, "-Infinity", idx, next_idx_ptr);
2231             }
2232             else
2233                 fallthrough = 1;
2234             break;
2235         default:
2236             fallthrough = 1;
2237     }
2238     /* Didn't find a string, object, array, or named constant. Look for a number. */
2239     if (fallthrough)
2240         rval = _match_number_str(s, pystr, idx, next_idx_ptr);
2241     return rval;
2242 }
2243 #endif /* PY_MAJOR_VERSION < 3 */
2244
2245
2246 static PyObject *
2247 scan_once_unicode(PyScannerObject *s, PyObject *pystr, Py_ssize_t idx, Py_ssize_t *next_idx_ptr)
2248 {
2249     /* Read one JSON term (of any kind) from PyUnicode pystr.
2250     idx is the index of the first character of the term
2251     *next_idx_ptr is a return-by-reference index to the first character after
2252         the number.
2253
2254     Returns a new PyObject representation of the term.
2255     */
2256     PY2_UNUSED int kind = PyUnicode_KIND(pystr);
2257     void *str = PyUnicode_DATA(pystr);
2258     Py_ssize_t length = PyUnicode_GetLength(pystr);
2259     PyObject *rval = NULL;
2260     int fallthrough = 0;
2261     if (idx >= length) {
2262         raise_errmsg(ERR_EXPECTING_VALUE, pystr, idx);
2263         return NULL;
2264     }
2265     switch (PyUnicode_READ(kind, str, idx)) {
2266         case '"':
2267             /* string */
2268             rval = scanstring_unicode(pystr, idx + 1,
2269                 PyObject_IsTrue(s->strict),
2270                 next_idx_ptr);
2271             break;
2272         case '{':
2273             /* object */
2274             if (Py_EnterRecursiveCall(" while decoding a JSON object "
2275                                       "from a unicode string"))
2276                 return NULL;
2277             rval = _parse_object_unicode(s, pystr, idx + 1, next_idx_ptr);
2278             Py_LeaveRecursiveCall();
2279             break;
2280         case '[':
2281             /* array */
2282             if (Py_EnterRecursiveCall(" while decoding a JSON array "
2283                                       "from a unicode string"))
2284                 return NULL;
2285             rval = _parse_array_unicode(s, pystr, idx + 1, next_idx_ptr);
2286             Py_LeaveRecursiveCall();
2287             break;
2288         case 'n':
2289             /* null */
2290             if ((idx + 3 < length) &&
2291                 PyUnicode_READ(kind, str, idx + 1) == 'u' &&
2292                 PyUnicode_READ(kind, str, idx + 2) == 'l' &&
2293                 PyUnicode_READ(kind, str, idx + 3) == 'l') {
2294                 Py_INCREF(Py_None);
2295                 *next_idx_ptr = idx + 4;
2296                 rval = Py_None;
2297             }
2298             else
2299                 fallthrough = 1;
2300             break;
2301         case 't':
2302             /* true */
2303             if ((idx + 3 < length) &&
2304                 PyUnicode_READ(kind, str, idx + 1) == 'r' &&
2305                 PyUnicode_READ(kind, str, idx + 2) == 'u' &&
2306                 PyUnicode_READ(kind, str, idx + 3) == 'e') {
2307                 Py_INCREF(Py_True);
2308                 *next_idx_ptr = idx + 4;
2309                 rval = Py_True;
2310             }
2311             else
2312                 fallthrough = 1;
2313             break;
2314         case 'f':
2315             /* false */
2316             if ((idx + 4 < length) &&
2317                 PyUnicode_READ(kind, str, idx + 1) == 'a' &&
2318                 PyUnicode_READ(kind, str, idx + 2) == 'l' &&
2319                 PyUnicode_READ(kind, str, idx + 3) == 's' &&
2320                 PyUnicode_READ(kind, str, idx + 4) == 'e') {
2321                 Py_INCREF(Py_False);
2322                 *next_idx_ptr = idx + 5;
2323                 rval = Py_False;
2324             }
2325             else
2326                 fallthrough = 1;
2327             break;
2328         case 'N':
2329             /* NaN */
2330             if ((idx + 2 < length) &&
2331                 PyUnicode_READ(kind, str, idx + 1) == 'a' &&
2332                 PyUnicode_READ(kind, str, idx + 2) == 'N') {
2333                 rval = _parse_constant(s, "NaN", idx, next_idx_ptr);
2334             }
2335             else
2336                 fallthrough = 1;
2337             break;
2338         case 'I':
2339             /* Infinity */
2340             if ((idx + 7 < length) &&
2341                 PyUnicode_READ(kind, str, idx + 1) == 'n' &&
2342                 PyUnicode_READ(kind, str, idx + 2) == 'f' &&
2343                 PyUnicode_READ(kind, str, idx + 3) == 'i' &&
2344                 PyUnicode_READ(kind, str, idx + 4) == 'n' &&
2345                 PyUnicode_READ(kind, str, idx + 5) == 'i' &&
2346                 PyUnicode_READ(kind, str, idx + 6) == 't' &&
2347                 PyUnicode_READ(kind, str, idx + 7) == 'y') {
2348                 rval = _parse_constant(s, "Infinity", idx, next_idx_ptr);
2349             }
2350             else
2351                 fallthrough = 1;
2352             break;
2353         case '-':
2354             /* -Infinity */
2355             if ((idx + 8 < length) &&
2356                 PyUnicode_READ(kind, str, idx + 1) == 'I' &&
2357                 PyUnicode_READ(kind, str, idx + 2) == 'n' &&
2358                 PyUnicode_READ(kind, str, idx + 3) == 'f' &&
2359                 PyUnicode_READ(kind, str, idx + 4) == 'i' &&
2360                 PyUnicode_READ(kind, str, idx + 5) == 'n' &&
2361                 PyUnicode_READ(kind, str, idx + 6) == 'i' &&
2362                 PyUnicode_READ(kind, str, idx + 7) == 't' &&
2363                 PyUnicode_READ(kind, str, idx + 8) == 'y') {
2364                 rval = _parse_constant(s, "-Infinity", idx, next_idx_ptr);
2365             }
2366             else
2367                 fallthrough = 1;
2368             break;
2369         default:
2370             fallthrough = 1;
2371     }
2372     /* Didn't find a string, object, array, or named constant. Look for a number. */
2373     if (fallthrough)
2374         rval = _match_number_unicode(s, pystr, idx, next_idx_ptr);
2375     return rval;
2376 }
2377
2378 static PyObject *
2379 scanner_call(PyObject *self, PyObject *args, PyObject *kwds)
2380 {
2381     /* Python callable interface to scan_once_{str,unicode} */
2382     PyObject *pystr;
2383     PyObject *rval;
2384     Py_ssize_t idx;
2385     Py_ssize_t next_idx = -1;
2386     static char *kwlist[] = {"string", "idx", NULL};
2387     PyScannerObject *s;
2388     assert(PyScanner_Check(self));
2389     s = (PyScannerObject *)self;
2390     if (!PyArg_ParseTupleAndKeywords(args, kwds, "OO&:scan_once", kwlist, &pystr, _convertPyInt_AsSsize_t, &idx))
2391         return NULL;
2392
2393     if (PyUnicode_Check(pystr)) {
2394         rval = scan_once_unicode(s, pystr, idx, &next_idx);
2395     }
2396 #if PY_MAJOR_VERSION < 3
2397     else if (PyString_Check(pystr)) {
2398         rval = scan_once_str(s, pystr, idx, &next_idx);
2399     }
2400 #endif /* PY_MAJOR_VERSION < 3 */
2401     else {
2402         PyErr_Format(PyExc_TypeError,
2403                  "first argument must be a string, not %.80s",
2404                  Py_TYPE(pystr)->tp_name);
2405         return NULL;
2406     }
2407     PyDict_Clear(s->memo);
2408     return _build_rval_index_tuple(rval, next_idx);
2409 }
2410
2411 static PyObject *
2412 scanner_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2413 {
2414     PyScannerObject *s;
2415     s = (PyScannerObject *)type->tp_alloc(type, 0);
2416     if (s != NULL) {
2417         s->encoding = NULL;
2418         s->strict = NULL;
2419         s->object_hook = NULL;
2420         s->pairs_hook = NULL;
2421         s->parse_float = NULL;
2422         s->parse_int = NULL;
2423         s->parse_constant = NULL;
2424     }
2425     return (PyObject *)s;
2426 }
2427
2428 static PyObject *
2429 JSON_ParseEncoding(PyObject *encoding)
2430 {
2431     if (encoding == NULL)
2432         return NULL;
2433     if (encoding == Py_None)
2434         return JSON_InternFromString(DEFAULT_ENCODING);
2435 #if PY_MAJOR_VERSION < 3
2436     if (PyUnicode_Check(encoding))
2437         return PyUnicode_AsEncodedString(encoding, NULL, NULL);
2438 #endif
2439     if (JSON_ASCII_Check(encoding)) {
2440         Py_INCREF(encoding);
2441         return encoding;
2442     }
2443     PyErr_SetString(PyExc_TypeError, "encoding must be a string");
2444     return NULL;
2445 }
2446
2447 static int
2448 scanner_init(PyObject *self, PyObject *args, PyObject *kwds)
2449 {
2450     /* Initialize Scanner object */
2451     PyObject *ctx;
2452     static char *kwlist[] = {"context", NULL};
2453     PyScannerObject *s;
2454     PyObject *encoding;
2455
2456     assert(PyScanner_Check(self));
2457     s = (PyScannerObject *)self;
2458
2459     if (!PyArg_ParseTupleAndKeywords(args, kwds, "O:make_scanner", kwlist, &ctx))
2460         return -1;
2461
2462     if (s->memo == NULL) {
2463         s->memo = PyDict_New();
2464         if (s->memo == NULL)
2465             goto bail;
2466     }
2467
2468     /* JSON_ASCII_AS_STRING is used on encoding */
2469     encoding = PyObject_GetAttrString(ctx, "encoding");
2470     s->encoding = JSON_ParseEncoding(encoding);
2471     Py_XDECREF(encoding);
2472     if (s->encoding == NULL)
2473         goto bail;
2474
2475     /* All of these will fail "gracefully" so we don't need to verify them */
2476     s->strict = PyObject_GetAttrString(ctx, "strict");
2477     if (s->strict == NULL)
2478         goto bail;
2479     s->object_hook = PyObject_GetAttrString(ctx, "object_hook");
2480     if (s->object_hook == NULL)
2481         goto bail;
2482     s->pairs_hook = PyObject_GetAttrString(ctx, "object_pairs_hook");
2483     if (s->pairs_hook == NULL)
2484         goto bail;
2485     s->parse_float = PyObject_GetAttrString(ctx, "parse_float");
2486     if (s->parse_float == NULL)
2487         goto bail;
2488     s->parse_int = PyObject_GetAttrString(ctx, "parse_int");
2489     if (s->parse_int == NULL)
2490         goto bail;
2491     s->parse_constant = PyObject_GetAttrString(ctx, "parse_constant");
2492     if (s->parse_constant == NULL)
2493         goto bail;
2494
2495     return 0;
2496
2497 bail:
2498     Py_CLEAR(s->encoding);
2499     Py_CLEAR(s->strict);
2500     Py_CLEAR(s->object_hook);
2501     Py_CLEAR(s->pairs_hook);
2502     Py_CLEAR(s->parse_float);
2503     Py_CLEAR(s->parse_int);
2504     Py_CLEAR(s->parse_constant);
2505     return -1;
2506 }
2507
2508 PyDoc_STRVAR(scanner_doc, "JSON scanner object");
2509
2510 static
2511 PyTypeObject PyScannerType = {
2512     PyVarObject_HEAD_INIT(NULL, 0)
2513     "simplejson._speedups.Scanner",       /* tp_name */
2514     sizeof(PyScannerObject), /* tp_basicsize */
2515     0,                    /* tp_itemsize */
2516     scanner_dealloc, /* tp_dealloc */
2517     0,                    /* tp_print */
2518     0,                    /* tp_getattr */
2519     0,                    /* tp_setattr */
2520     0,                    /* tp_compare */
2521     0,                    /* tp_repr */
2522     0,                    /* tp_as_number */
2523     0,                    /* tp_as_sequence */
2524     0,                    /* tp_as_mapping */
2525     0,                    /* tp_hash */
2526     scanner_call,         /* tp_call */
2527     0,                    /* tp_str */
2528     0,/* PyObject_GenericGetAttr, */                    /* tp_getattro */
2529     0,/* PyObject_GenericSetAttr, */                    /* tp_setattro */
2530     0,                    /* tp_as_buffer */
2531     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,   /* tp_flags */
2532     scanner_doc,          /* tp_doc */
2533     scanner_traverse,                    /* tp_traverse */
2534     scanner_clear,                    /* tp_clear */
2535     0,                    /* tp_richcompare */
2536     0,                    /* tp_weaklistoffset */
2537     0,                    /* tp_iter */
2538     0,                    /* tp_iternext */
2539     0,                    /* tp_methods */
2540     scanner_members,                    /* tp_members */
2541     0,                    /* tp_getset */
2542     0,                    /* tp_base */
2543     0,                    /* tp_dict */
2544     0,                    /* tp_descr_get */
2545     0,                    /* tp_descr_set */
2546     0,                    /* tp_dictoffset */
2547     scanner_init,                    /* tp_init */
2548     0,/* PyType_GenericAlloc, */        /* tp_alloc */
2549     scanner_new,          /* tp_new */
2550     0,/* PyObject_GC_Del, */              /* tp_free */
2551 };
2552
2553 static PyObject *
2554 encoder_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2555 {
2556     PyEncoderObject *s;
2557     s = (PyEncoderObject *)type->tp_alloc(type, 0);
2558     if (s != NULL) {
2559         s->markers = NULL;
2560         s->defaultfn = NULL;
2561         s->encoder = NULL;
2562         s->encoding = NULL;
2563         s->indent = NULL;
2564         s->key_separator = NULL;
2565         s->item_separator = NULL;
2566         s->key_memo = NULL;
2567         s->sort_keys = NULL;
2568         s->item_sort_key = NULL;
2569         s->item_sort_kw = NULL;
2570         s->Decimal = NULL;
2571     }
2572     return (PyObject *)s;
2573 }
2574
2575 static int
2576 encoder_init(PyObject *self, PyObject *args, PyObject *kwds)
2577 {
2578     /* initialize Encoder object */
2579     static char *kwlist[] = {"markers", "default", "encoder", "indent", "key_separator", "item_separator", "sort_keys", "skipkeys", "allow_nan", "key_memo", "use_decimal", "namedtuple_as_object", "tuple_as_array", "bigint_as_string", "item_sort_key", "encoding", "for_json", "ignore_nan", "Decimal", NULL};
2580
2581     PyEncoderObject *s;
2582     PyObject *markers, *defaultfn, *encoder, *indent, *key_separator;
2583     PyObject *item_separator, *sort_keys, *skipkeys, *allow_nan, *key_memo;
2584     PyObject *use_decimal, *namedtuple_as_object, *tuple_as_array;
2585     PyObject *bigint_as_string, *item_sort_key, *encoding, *for_json;
2586     PyObject *ignore_nan, *Decimal;
2587
2588     assert(PyEncoder_Check(self));
2589     s = (PyEncoderObject *)self;
2590
2591     if (!PyArg_ParseTupleAndKeywords(args, kwds, "OOOOOOOOOOOOOOOOOOO:make_encoder", kwlist,
2592         &markers, &defaultfn, &encoder, &indent, &key_separator, &item_separator,
2593         &sort_keys, &skipkeys, &allow_nan, &key_memo, &use_decimal,
2594         &namedtuple_as_object, &tuple_as_array, &bigint_as_string,
2595         &item_sort_key, &encoding, &for_json, &ignore_nan, &Decimal))
2596         return -1;
2597
2598     s->markers = markers;
2599     s->defaultfn = defaultfn;
2600     s->encoder = encoder;
2601     s->encoding = JSON_ParseEncoding(encoding);
2602     if (s->encoding == NULL)
2603         return -1;
2604     s->indent = indent;
2605     s->key_separator = key_separator;
2606     s->item_separator = item_separator;
2607     s->skipkeys_bool = skipkeys;
2608     s->skipkeys = PyObject_IsTrue(skipkeys);
2609     s->key_memo = key_memo;
2610     s->fast_encode = (PyCFunction_Check(s->encoder) && PyCFunction_GetFunction(s->encoder) == (PyCFunction)py_encode_basestring_ascii);
2611     s->allow_or_ignore_nan = (
2612         (PyObject_IsTrue(ignore_nan) ? JSON_IGNORE_NAN : 0) |
2613         (PyObject_IsTrue(allow_nan) ? JSON_ALLOW_NAN : 0));
2614     s->use_decimal = PyObject_IsTrue(use_decimal);
2615     s->namedtuple_as_object = PyObject_IsTrue(namedtuple_as_object);
2616     s->tuple_as_array = PyObject_IsTrue(tuple_as_array);
2617     s->bigint_as_string = PyObject_IsTrue(bigint_as_string);
2618     if (item_sort_key != Py_None) {
2619         if (!PyCallable_Check(item_sort_key))
2620             PyErr_SetString(PyExc_TypeError, "item_sort_key must be None or callable");
2621     }
2622     else if (PyObject_IsTrue(sort_keys)) {
2623         static PyObject *itemgetter0 = NULL;
2624         if (!itemgetter0) {
2625             PyObject *operator = PyImport_ImportModule("operator");
2626             if (!operator)
2627                 return -1;
2628             itemgetter0 = PyObject_CallMethod(operator, "itemgetter", "i", 0);
2629             Py_DECREF(operator);
2630         }
2631         item_sort_key = itemgetter0;
2632         if (!item_sort_key)
2633             return -1;
2634     }
2635     if (item_sort_key == Py_None) {
2636         Py_INCREF(Py_None);
2637         s->item_sort_kw = Py_None;
2638     }
2639     else {
2640         s->item_sort_kw = PyDict_New();
2641         if (s->item_sort_kw == NULL)
2642             return -1;
2643         if (PyDict_SetItemString(s->item_sort_kw, "key", item_sort_key))
2644             return -1;
2645     }
2646     s->sort_keys = sort_keys;
2647     s->item_sort_key = item_sort_key;
2648     s->Decimal = Decimal;
2649     s->for_json = PyObject_IsTrue(for_json);
2650
2651     Py_INCREF(s->markers);
2652     Py_INCREF(s->defaultfn);
2653     Py_INCREF(s->encoder);
2654     Py_INCREF(s->indent);
2655     Py_INCREF(s->key_separator);
2656     Py_INCREF(s->item_separator);
2657     Py_INCREF(s->key_memo);
2658     Py_INCREF(s->skipkeys_bool);
2659     Py_INCREF(s->sort_keys);
2660     Py_INCREF(s->item_sort_key);
2661     Py_INCREF(s->Decimal);
2662     return 0;
2663 }
2664
2665 static PyObject *
2666 encoder_call(PyObject *self, PyObject *args, PyObject *kwds)
2667 {
2668     /* Python callable interface to encode_listencode_obj */
2669     static char *kwlist[] = {"obj", "_current_indent_level", NULL};
2670     PyObject *obj;
2671     Py_ssize_t indent_level;
2672     PyEncoderObject *s;
2673     JSON_Accu rval;
2674     assert(PyEncoder_Check(self));
2675     s = (PyEncoderObject *)self;
2676     if (!PyArg_ParseTupleAndKeywords(args, kwds, "OO&:_iterencode", kwlist,
2677         &obj, _convertPyInt_AsSsize_t, &indent_level))
2678         return NULL;
2679     if (JSON_Accu_Init(&rval))
2680         return NULL;
2681     if (encoder_listencode_obj(s, &rval, obj, indent_level)) {
2682         JSON_Accu_Destroy(&rval);
2683         return NULL;
2684     }
2685     return JSON_Accu_FinishAsList(&rval);
2686 }
2687
2688 static PyObject *
2689 _encoded_const(PyObject *obj)
2690 {
2691     /* Return the JSON string representation of None, True, False */
2692     if (obj == Py_None) {
2693         static PyObject *s_null = NULL;
2694         if (s_null == NULL) {
2695             s_null = JSON_InternFromString("null");
2696         }
2697         Py_INCREF(s_null);
2698         return s_null;
2699     }
2700     else if (obj == Py_True) {
2701         static PyObject *s_true = NULL;
2702         if (s_true == NULL) {
2703             s_true = JSON_InternFromString("true");
2704         }
2705         Py_INCREF(s_true);
2706         return s_true;
2707     }
2708     else if (obj == Py_False) {
2709         static PyObject *s_false = NULL;
2710         if (s_false == NULL) {
2711             s_false = JSON_InternFromString("false");
2712         }
2713         Py_INCREF(s_false);
2714         return s_false;
2715     }
2716     else {
2717         PyErr_SetString(PyExc_ValueError, "not a const");
2718         return NULL;
2719     }
2720 }
2721
2722 static PyObject *
2723 encoder_encode_float(PyEncoderObject *s, PyObject *obj)
2724 {
2725     /* Return the JSON representation of a PyFloat */
2726     double i = PyFloat_AS_DOUBLE(obj);
2727     if (!Py_IS_FINITE(i)) {
2728         if (!s->allow_or_ignore_nan) {
2729             PyErr_SetString(PyExc_ValueError, "Out of range float values are not JSON compliant");
2730             return NULL;
2731         }
2732         if (s->allow_or_ignore_nan & JSON_IGNORE_NAN) {
2733             return _encoded_const(Py_None);
2734         }
2735         /* JSON_ALLOW_NAN is set */
2736         else if (i > 0) {
2737             static PyObject *sInfinity = NULL;
2738             if (sInfinity == NULL)
2739                 sInfinity = JSON_InternFromString("Infinity");
2740             if (sInfinity)
2741                 Py_INCREF(sInfinity);
2742             return sInfinity;
2743         }
2744         else if (i < 0) {
2745             static PyObject *sNegInfinity = NULL;
2746             if (sNegInfinity == NULL)
2747                 sNegInfinity = JSON_InternFromString("-Infinity");
2748             if (sNegInfinity)
2749                 Py_INCREF(sNegInfinity);
2750             return sNegInfinity;
2751         }
2752         else {
2753             static PyObject *sNaN = NULL;
2754             if (sNaN == NULL)
2755                 sNaN = JSON_InternFromString("NaN");
2756             if (sNaN)
2757                 Py_INCREF(sNaN);
2758             return sNaN;
2759         }
2760     }
2761     /* Use a better float format here? */
2762     return PyObject_Repr(obj);
2763 }
2764
2765 static PyObject *
2766 encoder_encode_string(PyEncoderObject *s, PyObject *obj)
2767 {
2768     /* Return the JSON representation of a string */
2769     if (s->fast_encode)
2770         return py_encode_basestring_ascii(NULL, obj);
2771     else
2772         return PyObject_CallFunctionObjArgs(s->encoder, obj, NULL);
2773 }
2774
2775 static int
2776 _steal_accumulate(JSON_Accu *accu, PyObject *stolen)
2777 {
2778     /* Append stolen and then decrement its reference count */
2779     int rval = JSON_Accu_Accumulate(accu, stolen);
2780     Py_DECREF(stolen);
2781     return rval;
2782 }
2783
2784 static int
2785 encoder_listencode_obj(PyEncoderObject *s, JSON_Accu *rval, PyObject *obj, Py_ssize_t indent_level)
2786 {
2787     /* Encode Python object obj to a JSON term, rval is a PyList */
2788     int rv = -1;
2789     do {
2790         if (obj == Py_None || obj == Py_True || obj == Py_False) {
2791             PyObject *cstr = _encoded_const(obj);
2792             if (cstr != NULL)
2793                 rv = _steal_accumulate(rval, cstr);
2794         }
2795         else if (PyString_Check(obj) || PyUnicode_Check(obj))
2796         {
2797             PyObject *encoded = encoder_encode_string(s, obj);
2798             if (encoded != NULL)
2799                 rv = _steal_accumulate(rval, encoded);
2800         }
2801         else if (PyInt_Check(obj) || PyLong_Check(obj)) {
2802             PyObject *encoded = PyObject_Str(obj);
2803             if (encoded != NULL) {
2804                 if (s->bigint_as_string) {
2805                     encoded = maybe_quote_bigint(encoded, obj);
2806                     if (encoded == NULL)
2807                         break;
2808                 }
2809                 rv = _steal_accumulate(rval, encoded);
2810             }
2811         }
2812         else if (PyFloat_Check(obj)) {
2813             PyObject *encoded = encoder_encode_float(s, obj);
2814             if (encoded != NULL)
2815                 rv = _steal_accumulate(rval, encoded);
2816         }
2817         else if (s->for_json && _has_for_json_hook(obj)) {
2818             PyObject *newobj;
2819             if (Py_EnterRecursiveCall(" while encoding a JSON object"))
2820                 return rv;
2821             newobj = PyObject_CallMethod(obj, "for_json", NULL);
2822             if (newobj != NULL) {
2823                 rv = encoder_listencode_obj(s, rval, newobj, indent_level);
2824                 Py_DECREF(newobj);
2825             }
2826             Py_LeaveRecursiveCall();
2827         }
2828         else if (s->namedtuple_as_object && _is_namedtuple(obj)) {
2829             PyObject *newobj;
2830             if (Py_EnterRecursiveCall(" while encoding a JSON object"))
2831                 return rv;
2832             newobj = PyObject_CallMethod(obj, "_asdict", NULL);
2833             if (newobj != NULL) {
2834                 rv = encoder_listencode_dict(s, rval, newobj, indent_level);
2835                 Py_DECREF(newobj);
2836             }
2837             Py_LeaveRecursiveCall();
2838         }
2839         else if (PyList_Check(obj) || (s->tuple_as_array && PyTuple_Check(obj))) {
2840             if (Py_EnterRecursiveCall(" while encoding a JSON object"))
2841                 return rv;
2842             rv = encoder_listencode_list(s, rval, obj, indent_level);
2843             Py_LeaveRecursiveCall();
2844         }
2845         else if (PyDict_Check(obj)) {
2846             if (Py_EnterRecursiveCall(" while encoding a JSON object"))
2847                 return rv;
2848             rv = encoder_listencode_dict(s, rval, obj, indent_level);
2849             Py_LeaveRecursiveCall();
2850         }
2851         else if (s->use_decimal && PyObject_TypeCheck(obj, (PyTypeObject *)s->Decimal)) {
2852             PyObject *encoded = PyObject_Str(obj);
2853             if (encoded != NULL)
2854                 rv = _steal_accumulate(rval, encoded);
2855         }
2856         else {
2857             PyObject *ident = NULL;
2858             PyObject *newobj;
2859             if (s->markers != Py_None) {
2860                 int has_key;
2861                 ident = PyLong_FromVoidPtr(obj);
2862                 if (ident == NULL)
2863                     break;
2864                 has_key = PyDict_Contains(s->markers, ident);
2865                 if (has_key) {
2866                     if (has_key != -1)
2867                         PyErr_SetString(PyExc_ValueError, "Circular reference detected");
2868                     Py_DECREF(ident);
2869                     break;
2870                 }
2871                 if (PyDict_SetItem(s->markers, ident, obj)) {
2872                     Py_DECREF(ident);
2873                     break;
2874                 }
2875             }
2876             if (Py_EnterRecursiveCall(" while encoding a JSON object"))
2877                 return rv;
2878             newobj = PyObject_CallFunctionObjArgs(s->defaultfn, obj, NULL);
2879             if (newobj == NULL) {
2880                 Py_XDECREF(ident);
2881                 Py_LeaveRecursiveCall();
2882                 break;
2883             }
2884             rv = encoder_listencode_obj(s, rval, newobj, indent_level);
2885             Py_LeaveRecursiveCall();
2886             Py_DECREF(newobj);
2887             if (rv) {
2888                 Py_XDECREF(ident);
2889                 rv = -1;
2890             }
2891             else if (ident != NULL) {
2892                 if (PyDict_DelItem(s->markers, ident)) {
2893                     Py_XDECREF(ident);
2894                     rv = -1;
2895                 }
2896                 Py_XDECREF(ident);
2897             }
2898         }
2899     } while (0);
2900     return rv;
2901 }
2902
2903 static int
2904 encoder_listencode_dict(PyEncoderObject *s, JSON_Accu *rval, PyObject *dct, Py_ssize_t indent_level)
2905 {
2906     /* Encode Python dict dct a JSON term */
2907     static PyObject *open_dict = NULL;
2908     static PyObject *close_dict = NULL;
2909     static PyObject *empty_dict = NULL;
2910     PyObject *kstr = NULL;
2911     PyObject *ident = NULL;
2912     PyObject *iter = NULL;
2913     PyObject *item = NULL;
2914     PyObject *items = NULL;
2915     PyObject *encoded = NULL;
2916     Py_ssize_t idx;
2917
2918     if (open_dict == NULL || close_dict == NULL || empty_dict == NULL) {
2919         open_dict = JSON_InternFromString("{");
2920         close_dict = JSON_InternFromString("}");
2921         empty_dict = JSON_InternFromString("{}");
2922         if (open_dict == NULL || close_dict == NULL || empty_dict == NULL)
2923             return -1;
2924     }
2925     if (PyDict_Size(dct) == 0)
2926         return JSON_Accu_Accumulate(rval, empty_dict);
2927
2928     if (s->markers != Py_None) {
2929         int has_key;
2930         ident = PyLong_FromVoidPtr(dct);
2931         if (ident == NULL)
2932             goto bail;
2933         has_key = PyDict_Contains(s->markers, ident);
2934         if (has_key) {
2935             if (has_key != -1)
2936                 PyErr_SetString(PyExc_ValueError, "Circular reference detected");
2937             goto bail;
2938         }
2939         if (PyDict_SetItem(s->markers, ident, dct)) {
2940             goto bail;
2941         }
2942     }
2943
2944     if (JSON_Accu_Accumulate(rval, open_dict))
2945         goto bail;
2946
2947     if (s->indent != Py_None) {
2948         /* TODO: DOES NOT RUN */
2949         indent_level += 1;
2950         /*
2951             newline_indent = '\n' + (_indent * _current_indent_level)
2952             separator = _item_separator + newline_indent
2953             buf += newline_indent
2954         */
2955     }
2956
2957     iter = encoder_dict_iteritems(s, dct);
2958     if (iter == NULL)
2959         goto bail;
2960
2961     idx = 0;
2962     while ((item = PyIter_Next(iter))) {
2963         PyObject *encoded, *key, *value;
2964         if (!PyTuple_Check(item) || Py_SIZE(item) != 2) {
2965             PyErr_SetString(PyExc_ValueError, "items must return 2-tuples");
2966             goto bail;
2967         }
2968         key = PyTuple_GET_ITEM(item, 0);
2969         if (key == NULL)
2970             goto bail;
2971         value = PyTuple_GET_ITEM(item, 1);
2972         if (value == NULL)
2973             goto bail;
2974
2975         encoded = PyDict_GetItem(s->key_memo, key);
2976         if (encoded != NULL) {
2977             Py_INCREF(encoded);
2978         } else {
2979             kstr = encoder_stringify_key(s, key);
2980             if (kstr == NULL)
2981                 goto bail;
2982             else if (kstr == Py_None) {
2983                 /* skipkeys */
2984                 Py_DECREF(item);
2985                 Py_DECREF(kstr);
2986                 continue;
2987             }
2988         }
2989         if (idx) {
2990             if (JSON_Accu_Accumulate(rval, s->item_separator))
2991                 goto bail;
2992         }
2993         if (encoded == NULL) {
2994             encoded = encoder_encode_string(s, kstr);
2995             Py_CLEAR(kstr);
2996             if (encoded == NULL)
2997                 goto bail;
2998             if (PyDict_SetItem(s->key_memo, key, encoded))
2999                 goto bail;
3000         }
3001         if (JSON_Accu_Accumulate(rval, encoded)) {
3002             goto bail;
3003         }
3004         Py_CLEAR(encoded);
3005         if (JSON_Accu_Accumulate(rval, s->key_separator))
3006             goto bail;
3007         if (encoder_listencode_obj(s, rval, value, indent_level))
3008             goto bail;
3009         Py_CLEAR(item);
3010         idx += 1;
3011     }
3012     Py_CLEAR(iter);
3013     if (PyErr_Occurred())
3014         goto bail;
3015     if (ident != NULL) {
3016         if (PyDict_DelItem(s->markers, ident))
3017             goto bail;
3018         Py_CLEAR(ident);
3019     }
3020     if (s->indent != Py_None) {
3021         /* TODO: DOES NOT RUN */
3022         indent_level -= 1;
3023         /*
3024             yield '\n' + (_indent * _current_indent_level)
3025         */
3026     }
3027     if (JSON_Accu_Accumulate(rval, close_dict))
3028         goto bail;
3029     return 0;
3030
3031 bail:
3032     Py_XDECREF(encoded);
3033     Py_XDECREF(items);
3034     Py_XDECREF(iter);
3035     Py_XDECREF(kstr);
3036     Py_XDECREF(ident);
3037     return -1;
3038 }
3039
3040
3041 static int
3042 encoder_listencode_list(PyEncoderObject *s, JSON_Accu *rval, PyObject *seq, Py_ssize_t indent_level)
3043 {
3044     /* Encode Python list seq to a JSON term */
3045     static PyObject *open_array = NULL;
3046     static PyObject *close_array = NULL;
3047     static PyObject *empty_array = NULL;
3048     PyObject *ident = NULL;
3049     PyObject *iter = NULL;
3050     PyObject *obj = NULL;
3051     int is_true;
3052     int i = 0;
3053
3054     if (open_array == NULL || close_array == NULL || empty_array == NULL) {
3055         open_array = JSON_InternFromString("[");
3056         close_array = JSON_InternFromString("]");
3057         empty_array = JSON_InternFromString("[]");
3058         if (open_array == NULL || close_array == NULL || empty_array == NULL)
3059             return -1;
3060     }
3061     ident = NULL;
3062     is_true = PyObject_IsTrue(seq);
3063     if (is_true == -1)
3064         return -1;
3065     else if (is_true == 0)
3066         return JSON_Accu_Accumulate(rval, empty_array);
3067
3068     if (s->markers != Py_None) {
3069         int has_key;
3070         ident = PyLong_FromVoidPtr(seq);
3071         if (ident == NULL)
3072             goto bail;
3073         has_key = PyDict_Contains(s->markers, ident);
3074         if (has_key) {
3075             if (has_key != -1)
3076                 PyErr_SetString(PyExc_ValueError, "Circular reference detected");
3077             goto bail;
3078         }
3079         if (PyDict_SetItem(s->markers, ident, seq)) {
3080             goto bail;
3081         }
3082     }
3083
3084     iter = PyObject_GetIter(seq);
3085     if (iter == NULL)
3086         goto bail;
3087
3088     if (JSON_Accu_Accumulate(rval, open_array))
3089         goto bail;
3090     if (s->indent != Py_None) {
3091         /* TODO: DOES NOT RUN */
3092         indent_level += 1;
3093         /*
3094             newline_indent = '\n' + (_indent * _current_indent_level)
3095             separator = _item_separator + newline_indent
3096             buf += newline_indent
3097         */
3098     }
3099     while ((obj = PyIter_Next(iter))) {
3100         if (i) {
3101             if (JSON_Accu_Accumulate(rval, s->item_separator))
3102                 goto bail;
3103         }
3104         if (encoder_listencode_obj(s, rval, obj, indent_level))
3105             goto bail;
3106         i++;
3107         Py_CLEAR(obj);
3108     }
3109     Py_CLEAR(iter);
3110     if (PyErr_Occurred())
3111         goto bail;
3112     if (ident != NULL) {
3113         if (PyDict_DelItem(s->markers, ident))
3114             goto bail;
3115         Py_CLEAR(ident);
3116     }
3117     if (s->indent != Py_None) {
3118         /* TODO: DOES NOT RUN */
3119         indent_level -= 1;
3120         /*
3121             yield '\n' + (_indent * _current_indent_level)
3122         */
3123     }
3124     if (JSON_Accu_Accumulate(rval, close_array))
3125         goto bail;
3126     return 0;
3127
3128 bail:
3129     Py_XDECREF(obj);
3130     Py_XDECREF(iter);
3131     Py_XDECREF(ident);
3132     return -1;
3133 }
3134
3135 static void
3136 encoder_dealloc(PyObject *self)
3137 {
3138     /* Deallocate Encoder */
3139     encoder_clear(self);
3140     Py_TYPE(self)->tp_free(self);
3141 }
3142
3143 static int
3144 encoder_traverse(PyObject *self, visitproc visit, void *arg)
3145 {
3146     PyEncoderObject *s;
3147     assert(PyEncoder_Check(self));
3148     s = (PyEncoderObject *)self;
3149     Py_VISIT(s->markers);
3150     Py_VISIT(s->defaultfn);
3151     Py_VISIT(s->encoder);
3152     Py_VISIT(s->encoding);
3153     Py_VISIT(s->indent);
3154     Py_VISIT(s->key_separator);
3155     Py_VISIT(s->item_separator);
3156     Py_VISIT(s->key_memo);
3157     Py_VISIT(s->sort_keys);
3158     Py_VISIT(s->item_sort_kw);
3159     Py_VISIT(s->item_sort_key);
3160     Py_VISIT(s->Decimal);
3161     return 0;
3162 }
3163
3164 static int
3165 encoder_clear(PyObject *self)
3166 {
3167     /* Deallocate Encoder */
3168     PyEncoderObject *s;
3169     assert(PyEncoder_Check(self));
3170     s = (PyEncoderObject *)self;
3171     Py_CLEAR(s->markers);
3172     Py_CLEAR(s->defaultfn);
3173     Py_CLEAR(s->encoder);
3174     Py_CLEAR(s->encoding);
3175     Py_CLEAR(s->indent);
3176     Py_CLEAR(s->key_separator);
3177     Py_CLEAR(s->item_separator);
3178     Py_CLEAR(s->key_memo);
3179     Py_CLEAR(s->skipkeys_bool);
3180     Py_CLEAR(s->sort_keys);
3181     Py_CLEAR(s->item_sort_kw);
3182     Py_CLEAR(s->item_sort_key);
3183     Py_CLEAR(s->Decimal);
3184     return 0;
3185 }
3186
3187 PyDoc_STRVAR(encoder_doc, "_iterencode(obj, _current_indent_level) -> iterable");
3188
3189 static
3190 PyTypeObject PyEncoderType = {
3191     PyVarObject_HEAD_INIT(NULL, 0)
3192     "simplejson._speedups.Encoder",       /* tp_name */
3193     sizeof(PyEncoderObject), /* tp_basicsize */
3194     0,                    /* tp_itemsize */
3195     encoder_dealloc, /* tp_dealloc */
3196     0,                    /* tp_print */
3197     0,                    /* tp_getattr */
3198     0,                    /* tp_setattr */
3199     0,                    /* tp_compare */
3200     0,                    /* tp_repr */
3201     0,                    /* tp_as_number */
3202     0,                    /* tp_as_sequence */
3203     0,                    /* tp_as_mapping */
3204     0,                    /* tp_hash */
3205     encoder_call,         /* tp_call */
3206     0,                    /* tp_str */
3207     0,                    /* tp_getattro */
3208     0,                    /* tp_setattro */
3209     0,                    /* tp_as_buffer */
3210     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,   /* tp_flags */
3211     encoder_doc,          /* tp_doc */
3212     encoder_traverse,     /* tp_traverse */
3213     encoder_clear,        /* tp_clear */
3214     0,                    /* tp_richcompare */
3215     0,                    /* tp_weaklistoffset */
3216     0,                    /* tp_iter */
3217     0,                    /* tp_iternext */
3218     0,                    /* tp_methods */
3219     encoder_members,      /* tp_members */
3220     0,                    /* tp_getset */
3221     0,                    /* tp_base */
3222     0,                    /* tp_dict */
3223     0,                    /* tp_descr_get */
3224     0,                    /* tp_descr_set */
3225     0,                    /* tp_dictoffset */
3226     encoder_init,         /* tp_init */
3227     0,                    /* tp_alloc */
3228     encoder_new,          /* tp_new */
3229     0,                    /* tp_free */
3230 };
3231
3232 static PyMethodDef speedups_methods[] = {
3233     {"encode_basestring_ascii",
3234         (PyCFunction)py_encode_basestring_ascii,
3235         METH_O,
3236         pydoc_encode_basestring_ascii},
3237     {"scanstring",
3238         (PyCFunction)py_scanstring,
3239         METH_VARARGS,
3240         pydoc_scanstring},
3241     {NULL, NULL, 0, NULL}
3242 };
3243
3244 PyDoc_STRVAR(module_doc,
3245 "simplejson speedups\n");
3246
3247 #if PY_MAJOR_VERSION >= 3
3248 static struct PyModuleDef moduledef = {
3249     PyModuleDef_HEAD_INIT,
3250     "_speedups",        /* m_name */
3251     module_doc,         /* m_doc */
3252     -1,                 /* m_size */
3253     speedups_methods,   /* m_methods */
3254     NULL,               /* m_reload */
3255     NULL,               /* m_traverse */
3256     NULL,               /* m_clear*/
3257     NULL,               /* m_free */
3258 };
3259 #endif
3260
3261 static PyObject *
3262 moduleinit(void)
3263 {
3264     PyObject *m;
3265     PyScannerType.tp_new = PyType_GenericNew;
3266     if (PyType_Ready(&PyScannerType) < 0)
3267         return NULL;
3268     PyEncoderType.tp_new = PyType_GenericNew;
3269     if (PyType_Ready(&PyEncoderType) < 0)
3270         return NULL;
3271
3272 #if PY_MAJOR_VERSION >= 3
3273     m = PyModule_Create(&moduledef);
3274 #else
3275     m = Py_InitModule3("_speedups", speedups_methods, module_doc);
3276 #endif
3277     Py_INCREF((PyObject*)&PyScannerType);
3278     PyModule_AddObject(m, "make_scanner", (PyObject*)&PyScannerType);
3279     Py_INCREF((PyObject*)&PyEncoderType);
3280     PyModule_AddObject(m, "make_encoder", (PyObject*)&PyEncoderType);
3281     return m;
3282 }
3283
3284 #if PY_MAJOR_VERSION >= 3
3285 PyMODINIT_FUNC
3286 PyInit__speedups(void)
3287 {
3288     return moduleinit();
3289 }
3290 #else
3291 void
3292 init_speedups(void)
3293 {
3294     moduleinit();
3295 }
3296 #endif